src/vm/jit/loop/loop.c

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