src/vm/jit/loop/loop.c

   1 /* src/vm/jit/loop/loop.c - array bound removal
   2
   3    Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
   4    C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   5    E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   6    J. Wenninger, Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25    Contact: cacao@cacaojvm.org
  26
  27    Authors: Christopher Kruegel
  28
  29    Changes: Christian Thalinger
  30
  31    The loop detection is performed according to Lengauer-Tarjan
  32    algorithm that uses dominator trees (found eg. in modern compiler
  33    implementation by a.w. appel)
  34
  35
  36 */
  37
  38
  39 #include <assert.h>
  40 /*  #include <stdio.h> */
  41 #include <stdlib.h>
  42
  43 #include "mm/memory.h"
  44 #include "toolbox/logging.h"
  45 #include "vm/global.h"
  46 #include "vm/jit/jit.h"
  47 #include "vm/jit/loop/loop.h"
  48 #include "vm/jit/loop/graph.h"
  49 #include "vm/jit/loop/tracing.h"
  50
  51
  52 /*
  53    This function allocates and initializes variables, that are used by the
  54    loop detection algorithm
  55 */
  56 void setup(methodinfo *m, loopdata *ld)
  57 {
  58         int i;
  59
  60         ld->c_semi_dom = DMNEW(int, m->basicblockcount);
  61         ld->c_idom = DMNEW(int, m->basicblockcount);
  62         ld->c_same_dom = DMNEW(int, m->basicblockcount);
  63         ld->c_numBucket = DMNEW(int, m->basicblockcount);
  64         ld->c_ancestor = DMNEW(int, m->basicblockcount);
  65         ld->c_contains = DMNEW(int, m->basicblockcount);
  66         ld->c_stack = DMNEW(int, m->basicblockcount);
  67         ld->c_bucket = DMNEW(int*, m->basicblockcount);
  68
  69         for (i = 0; i < m->basicblockcount; ++i) {
  70                 ld->c_numBucket[i] = 0;
  71                 ld->c_stack[i] = ld->c_ancestor[i] = ld->c_semi_dom[i] = ld->c_same_dom[i] = ld->c_idom[i] = -1;
  72
  73                 ld->c_bucket[i] = DMNEW(int, m->basicblockcount);
  74         }
  75 }
  76
  77
  78 /*      This function is a helper function for dominators and has to find the
  79         ancestor of the node v in the control graph, which semi-dominator has the
  80         lowest def-num.
  81 */
  82
  83 int findLowAnc(loopdata *ld, int v)
  84 {
  85         int u = v;                      /* u is the node which has the current lowest semi-dom  */
  86
  87         while (ld->c_ancestor[v] != -1) {       /* as long as v has an ancestor, continue       */
  88                 if (ld->c_defnum[ld->c_semi_dom[v]] < ld->c_defnum[ld->c_semi_dom[u]])
  89                                                                         /* if v's semi-dom is smaller                           */
  90                         u = v;                                  /* it gets the new current node u                       */
  91                 v = ld->c_ancestor[v];                  /* climb one step up in the tree                        */
  92                 }
  93         return u;                       /* return node with the lowest semi-dominator def-num   */
  94 }
  95
  96
  97 /*      This function builds the dominator tree out of a given control flow graph and
  98         stores its results in c_idom[]. It first calculates the number of possible
  99         dominators in c_bucket and eventually determines the single dominator in a
 100         final pass.
 101 */
 102
 103 void dominators(loopdata *ld)
 104 {
 105         int i, j, semi, s, n, v, actual, p, y;
 106
 107         for (n=(ld->c_globalCount-1); n>0; --n) {       /* for all nodes (except last), do      */
 108                 actual = ld->c_reverse[n];
 109                 semi = p = ld->c_parent[actual];
 110
 111                 /* for all predecessors of current node, do                                                             */
 112                 for (i=0; i<ld->c_numPre[actual]; ++i) {
 113                         v = ld->c_pre[actual][i];
 114
 115                         if (ld->c_defnum[v] <= ld->c_defnum[actual])
 116                                 s = v;                  /* if predecessor has lower def-num     than node       */
 117                                                                 /* it becomes candidate for semi dominator              */
 118                         else
 119                                 s = ld->c_semi_dom[findLowAnc(ld, v)];
 120                                                                 /* else the semi-dominator of it's ancestor             */
 121                                                                 /* with lowest def-num becomes candidate                */
 122
 123                         if (ld->c_defnum[s] < ld->c_defnum[semi])
 124                                 semi = s;               /* if the def-num of the new candidate is lower */
 125                                                                 /* than old one, it gets new semi dominator             */
 126                         }
 127
 128                 /* write semi dominator -> according to SEMIDOMINATOR THEOREM                   */
 129                 ld->c_semi_dom[actual] = semi;
 130                 ld->c_ancestor[actual] = p;
 131
 132                 ld->c_bucket[semi][ld->c_numBucket[semi]] = actual;
 133                 ld->c_numBucket[semi]++;        /* defer calculation of dominator to final pass */
 134
 135
 136                 /* first clause of DOMINATOR THEOREM, try to find dominator now                 */
 137                 for (j=0; j<ld->c_numBucket[p]; ++j) {
 138                         v = ld->c_bucket[p][j];
 139                         y = findLowAnc(ld, v);
 140
 141                         if (ld->c_semi_dom[y] == ld->c_semi_dom[v])
 142                                 ld->c_idom[v] = p;                      /* if y's dominator is already known    */
 143                                                                                 /* found it and write to c_idom                 */
 144                         else
 145                                 ld->c_same_dom[v] = y;          /* wait till final pass                                 */
 146                         }
 147
 148                 ld->c_numBucket[p] = 0;
 149                 }
 150
 151         /* final pass to get missing dominators ->second clause of DOMINATOR THEORM     */
 152         for (j=1; j<(ld->c_globalCount-1); ++j) {
 153                 if (ld->c_same_dom[ld->c_reverse[j]] != -1)
 154                         ld->c_idom[ld->c_reverse[j]] = ld->c_idom[ld->c_same_dom[ld->c_reverse[j]]];
 155                 }
 156 }
 157
 158
 159 /*
 160    A helper function needed by detectLoops() that checks, whether a given
 161    connection between two nodes in the control flow graph is possibly part
 162    of a loop (is a backEdge).
 163 */
 164
 165 int isBackEdge(loopdata *ld, int from, int to)
 166 {
 167         int tmp = ld->c_idom[to];       /* speed optimization: if the to-node is dominated      */
 168         while (tmp != -1) {             /* by the from node as it is most of the time,          */
 169                 if (tmp == from)        /* there is no backEdge                                                         */
 170                         return 0;
 171                 tmp = ld->c_idom[tmp];
 172                 }
 173
 174         tmp = ld->c_idom[from];         /* if from-node doesn't dominate to-node, we have       */
 175         while (tmp != -1) {             /* to climb all the way up from the from-node to        */
 176                 if (tmp == to)          /* the top to check, whether it is dominated by to      */
 177                         return 1;               /* if so, return a backedge                                                     */
 178                 tmp = ld->c_idom[tmp];
 179                 }
 180
 181         return 0;                               /* else, there is no backedge                                           */
 182 }
 183
 184
 185 /*
 186    These stack functions are helper functions for createLoop(int, int)
 187    to manage the set of nodes in the current loop.
 188 */
 189
 190 void push(methodinfo *m, loopdata *ld, int i, struct LoopContainer *lc)
 191 {
 192         struct LoopElement *le = lc->nodes, *t;
 193
 194         if (!ld->c_contains[i]) {
 195                 t = DMNEW(struct LoopElement, 1);
 196
 197                 t->node = i;
 198                 t->block = &m->basicblocks[i];
 199
 200                 ld->c_contains[i] = 1;
 201
 202                 if (i < le->node)
 203                 {
 204                         t->next = lc->nodes;
 205                         lc->nodes = t;
 206                 }
 207                 else
 208                 {
 209                         while ((le->next != NULL) && (le->next->node < i))
 210                                 le = le->next;
 211
 212                         t->next = le->next;
 213                         le->next = t;
 214                 }
 215
 216                 ld->c_stack[ld->c_stackPointer++] = i;
 217         }
 218 }
 219
 220
 221 int pop(loopdata *ld)
 222 {
 223         return (ld->c_stack[--ld->c_stackPointer]);
 224 }
 225
 226
 227 int isFull(loopdata *ld)
 228 {
 229         return (ld->c_stackPointer);
 230 }
 231
 232
 233 /*
 234    This function is a helper function, that finds all nodes, that belong to
 235    the loop with a known header node and a member node of the loop (and a
 236    back edge between these two nodes).
 237 */
 238
 239 void createLoop(methodinfo *m, loopdata *ld, int header, int member)
 240 {
 241         int i, nextMember;
 242
 243         struct LoopContainer *currentLoop = (struct LoopContainer *) malloc(sizeof(struct LoopContainer));
 244         LoopContainerInit(m, currentLoop, header);              /* set up loop structure                */
 245
 246         for (i=0; i<m->basicblockcount; ++i)
 247                 ld->c_contains[i] = 0;
 248         ld->c_contains[header] = 1;
 249
 250         ld->c_stackPointer = 0;                         /* init stack with first node of the loop       */
 251         push(m, ld, member, currentLoop);
 252
 253         while (isFull(ld)) {                            /* while there are still unvisited nodes        */
 254                 nextMember = pop(ld);
 255
 256                 /* push all predecessors, while they are not equal to loop header               */
 257                 for (i=0; i<ld->c_numPre[nextMember]; ++i)
 258                         push(m, ld, ld->c_pre[nextMember][i], currentLoop);
 259                 }
 260
 261         currentLoop->next = ld->c_allLoops;
 262         ld->c_allLoops = currentLoop;
 263 }
 264
 265
 266 /*      After all dominators have been calculated, the loops can be detected and
 267          added to the global list c_allLoops.
 268 */
 269
 270 void detectLoops(methodinfo *m, loopdata *ld)
 271 {
 272         int i;
 273         struct depthElement *h;
 274
 275         /* for all edges in the control flow graph do                                                           */
 276         for (i=0; i<m->basicblockcount; ++i) {
 277                 h = ld->c_dTable[i];
 278
 279                 while (h != NULL) {
 280                         /* if it's a backedge, than add a new loop to list                                      */
 281                         if (isBackEdge(ld, i, h->value))
 282                                 createLoop(m, ld, h->value, i);
 283                         h = h->next;
 284                         }
 285                 }
 286 }
 287
 288
 289 /*
 290    This function is called by higher level routines to perform the loop
 291    detection and set up the c_allLoops list.
 292 */
 293
 294 void analyseGraph(jitdata *jd)
 295 {
 296         methodinfo *m;
 297         loopdata   *ld;
 298
 299         /* get required compiler data */
 300
 301         m  = jd->m;
 302         ld = jd->ld;
 303
 304         setup(m, ld);
 305         dominators(ld);
 306         detectLoops(m, ld);
 307 }
 308
 309
 310 /*
 311    Test function -> will be removed in final release
 312 */
 313
 314 void resultPass2(loopdata *ld)
 315 {
 316   int i;
 317   struct LoopContainer *lc = ld->c_allLoops;
 318   struct LoopElement *le;
 319
 320   printf("\n\n****** PASS 2 ******\n\n");
 321
 322   printf("Loops:\n\n");
 323
 324   i = 0;
 325   while (lc != NULL) {
 326           printf("Loop [%d]: ", ++i);
 327
 328           le = lc->nodes;
 329           while (le != NULL) {
 330             printf("%d ", le->node);
 331                 printf("\n");
 332                 le = le->next;
 333           }
 334
 335           lc = lc->next;
 336   }
 337
 338   printf("\n");
 339
 340 }
 341
 342
 343 void c_mem_error()
 344 {
 345         log_text("C_ERROR: Not enough memeory");
 346         assert(0);
 347 }
 348
 349
 350 /*
 351  * These are local overrides for various environment variables in Emacs.
 352  * Please do not remove this and leave it at the end of the file, where
 353  * Emacs will automagically detect them.
 354  * ---------------------------------------------------------------------
 355  * Local variables:
 356  * mode: c
 357  * indent-tabs-mode: t
 358  * c-basic-offset: 4
 359  * tab-width: 4
 360  * End:
 361  */