src/vm/jit/loop/loop.c

   1 /* jit/loop/loop.c - array bound removal
   2
   3    Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
   4    R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser,
   5    M. Probst, S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck,
   6    P. Tomsich, J. Wenninger
   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 1203 2004-06-22 23:14:55Z twisti $
  34
  35 */
  36
  37
  38 #include <stdio.h>
  39 #include <stdlib.h>
  40 #include "global.h"
  41 #include "jit/jit.h"
  42 #include "jit/loop/loop.h"
  43 #include "jit/loop/graph.h"
  44 #include "jit/loop/tracing.h"
  45 #include "toolbox/logging.h"
  46 #include "toolbox/memory.h"
  47
  48 /* GLOBAL VARS                                                                                                                          */
  49
  50 int c_debug_nr;                 /* a counter to number all BB with an unique    */
  51                                 /* value                                        */
  52
  53 /* modified by graph.c                                                                                                                  */
  54
  55 int *c_defnum;                                  /* array that stores a number for each node     when*/
  56                                                                 /* control flow graph is traveres depth first   */
  57 int *c_parent;                                  /* for each node that array stores its parent   */
  58 int *c_reverse;                                 /* for each def number that array stores the    */
  59                                                                 /* corresponding node                                                   */
  60 int c_globalCount;                              /* counter for def numbering                                    */
  61 int *c_numPre;                                  /* array that stores for each node its number   */
  62                                                                 /* predecessors                                                                 */
  63 int **c_pre;                                    /* array of array that stores predecessors              */
  64 int c_last_jump;                                /* stores the source node of the last jsr instr */
  65 struct basicblock *c_last_target;      /* stores the source BB of the last jsr instr    */
  66
  67 struct depthElement **c_dTable; /* adjacency list for control flow graph                */
  68 struct depthElement **c_exceptionGraph; /* adjacency list for exception graph   */
  69
  70 struct LoopContainer *c_allLoops;               /* list of all loops                                    */
  71 struct LoopContainer *c_loop_root;              /* root of loop hierarchie tree                 */
  72
  73 int *c_exceptionVisit;                  /* array that stores a flag for each node part  */
  74                                                                 /* of the exception graph                                               */
  75
  76 /* modified by loop.c                                                                                                                   */
  77
  78 int *c_semi_dom;                                /* store for each node its semi dominator               */
  79 int *c_idom;                                    /* store for each node its dominator                    */
  80 int *c_same_dom;                                /* temp array to hold nodes with same dominator */
  81 int *c_ancestor;                                /* store for each node its ancestor with lowest */
  82                                                                 /* semi dominator                                                               */
  83 int *c_numBucket;
  84 int **c_bucket;
  85
  86 int *c_contains;                                /* store for each node whether it's part of loop*/
  87 int *c_stack;                                   /* a simple stack as array                                              */
  88 int c_stackPointer;                             /* stackpointer                                                                 */
  89
  90
  91 /* modified by analyze.c                                                                                                                */
  92
  93 struct LoopContainer *root;     /* the root pointer for the hierarchie tree of  */
  94                                 /* all loops in that procedure                  */
  95
  96 int c_needed_instr;                             /* number of instructions that have to be               */
  97                                                                 /* inserted before loop header to make sure             */
  98                                                                 /* array optimization is legal                                  */
  99 int c_rs_needed_instr;                  /* number of instructions needed to load the    */
 100                                                                 /* value ofthe right side of the loop condition */
 101 int *c_nestedLoops;                             /* store for each node the header node of the   */
 102                                                                 /* loop this node belongs to, -1 for none               */
 103 int *c_hierarchie;              /* store a loop hierarchie                      */
 104 int *c_toVisit;                                 /* set for each node that is part of the loop   */
 105
 106 int *c_current_loop;                    /* for each node:                               */
 107                                                                 /* store 0:     node is not part of loop                        */
 108                                                                 /* store 1:     node is loop header                                     */
 109                                                                 /* store 2:     node is in loop but not part of any     */
 110                                                                 /*                      nested loop                         */
 111                                                                 /* store 3:     node is part of nested loop                     */
 112
 113 int c_current_head;                             /* store number of node that is header of loop  */
 114 int *c_var_modified;                    /* store for each local variable whether its    */
 115                                                                 /* value is changed in the loop                                 */
 116
 117 struct Trace *c_rightside;              /* right side of loop condition                                 */
 118 struct Constraint **c_constraints;
 119                                                                 /* array that stores for each variable a list   */
 120                                                                 /* static tests (constraints) that have to be   */
 121                                                                 /* performed before loop entry                                  */
 122                                                                 /* IMPORTANT: c_constraints[maxlocals] stores   */
 123                                                                 /*                        the tests for constants and the       */
 124                                                                 /*                        right side of loop condition          */
 125
 126 struct LoopVar *c_loopvars;             /* a list of all intersting variables of the    */
 127                                                                 /* current loop (variables that are modified or */
 128                                                                 /* used as array index                                                  */
 129
 130 struct basicblock *c_first_block_copied; /* pointer to the first block, that is copied */
 131                                   /* during loop duplication                    */
 132
 133 struct basicblock *c_last_block_copied;  /* last block, that is copied during loop     */
 134                                   /* duplication                                */
 135
 136 int *c_null_check;              /* array to store for local vars, whether they  */
 137                                 /* need to be checked against the null reference*/
 138                                 /* in the loop head                             */
 139
 140 bool c_needs_redirection;       /* if a loop header is inserted as first block  */
 141                                 /* into the global BB list, this is set to true */
 142
 143 struct basicblock *c_newstart;         /* if a loop header is inserted as first block  */
 144                                 /* into the gloal BB list, this pointer is the  */
 145                                 /* new start                                    */
 146 int c_old_xtablelength;         /* used to store the original tablelength       */
 147
 148 /* set debug mode                                                                                                                               */
 149 #define C_DEBUG
 150
 151
 152 /* declare statistic variables                                                                                                  */
 153 #ifdef STATISTICS
 154
 155 int c_stat_num_loops;                   /* number of loops                                                              */
 156
 157 /* statistics per loop                                                                                                                  */
 158 int c_stat_array_accesses;              /* number of array accesses                                             */
 159
 160 int c_stat_full_opt;                    /* number of fully optimized accesses                   */
 161 int c_stat_no_opt;                              /* number of not optimized accesses                             */
 162 int c_stat_lower_opt;                   /* number of accesses where check against zero  */
 163                                                                 /* is removed                                                                   */
 164 int c_stat_upper_opt;                   /* number of accesses where check against array */
 165                                                                 /* lengh is removed                                                             */
 166 int c_stat_or;                                  /* set if optimization is cancelled because of  */
 167                                                                 /* or in loop condition                                                 */
 168 int c_stat_exception;                   /* set if optimization is cancelled because of  */
 169                                                                 /* index var modified in catch block                    */
 170
 171 /* statistics per procedure                                                                                                             */
 172 int c_stat_sum_accesses;                /* number of array accesses                                             */
 173
 174 int c_stat_sum_full;                    /* number of fully optimized accesses                   */
 175 int c_stat_sum_no;                              /* number of not optimized accesses                             */
 176 int c_stat_sum_lower;                   /* number of accesses where check against zero  */
 177                                                                 /* is removed                                                                   */
 178 int c_stat_sum_upper;                   /* number of accesses where check against array */
 179                                                                 /* lengh is removed                                                             */
 180 int c_stat_sum_or;                              /* set if optimization is cancelled because of  */
 181                                                                 /* or in loop condition                                                 */
 182 int c_stat_sum_exception;               /* set if optimization is cancelled because of  */
 183
 184 #endif
 185
 186
 187 /*
 188    This function allocates and initializes variables, that are used by the
 189    loop detection algorithm
 190 */
 191 void setup(methodinfo *m)
 192 {
 193         int i;
 194
 195         c_semi_dom = DMNEW(int, m->basicblockcount);
 196         c_idom = DMNEW(int, m->basicblockcount);
 197         c_same_dom = DMNEW(int, m->basicblockcount);
 198         c_numBucket = DMNEW(int, m->basicblockcount);
 199         c_ancestor = DMNEW(int, m->basicblockcount);
 200         c_contains = DMNEW(int, m->basicblockcount);
 201         c_stack = DMNEW(int, m->basicblockcount);
 202         c_bucket = DMNEW(int*, m->basicblockcount);
 203
 204         for (i = 0; i < m->basicblockcount; ++i) {
 205                 c_numBucket[i] = 0;
 206                 c_stack[i] = c_ancestor[i] = c_semi_dom[i] = c_same_dom[i] = c_idom[i] = -1;
 207
 208                 c_bucket[i] = DMNEW(int, m->basicblockcount);
 209         }
 210 }
 211
 212
 213 /*      This function is a helper function for dominators and has to find the
 214         ancestor of the node v in the control graph, which semi-dominator has the
 215         lowest def-num.
 216 */
 217 int findLowAnc(int v)
 218 {
 219         int u = v;                      /* u is the node which has the current lowest semi-dom  */
 220
 221         while (c_ancestor[v] != -1) {   /* as long as v has an ancestor, continue       */
 222                 if (c_defnum[c_semi_dom[v]] < c_defnum[c_semi_dom[u]])
 223                                                                         /* if v's semi-dom is smaller                           */
 224                         u = v;                                  /* it gets the new current node u                       */
 225                 v = c_ancestor[v];                      /* climb one step up in the tree                        */
 226                 }
 227         return u;                       /* return node with the lowest semi-dominator def-num   */
 228 }
 229
 230
 231 /*      This function builds the dominator tree out of a given control flow graph and
 232         stores its results in c_idom[]. It first calculates the number of possible
 233         dominators in c_bucket and eventually determines the single dominator in a
 234         final pass.
 235 */
 236 void dominators()
 237 {
 238         int i, j, semi, s, n, v, actual, p, y;
 239
 240         for (n=(c_globalCount-1); n>0; --n) {   /* for all nodes (except last), do      */
 241                 actual = c_reverse[n];
 242                 semi = p = c_parent[actual];
 243
 244                 /* for all predecessors of current node, do                                                             */
 245                 for (i=0; i<c_numPre[actual]; ++i) {
 246                         v = c_pre[actual][i];
 247
 248                         if (c_defnum[v] <= c_defnum[actual])
 249                                 s = v;                  /* if predecessor has lower def-num     than node       */
 250                                                                 /* it becomes candidate for semi dominator              */
 251                         else
 252                                 s = c_semi_dom[findLowAnc(v)];
 253                                                                 /* else the semi-dominator of it's ancestor             */
 254                                                                 /* with lowest def-num becomes candidate                */
 255
 256                         if (c_defnum[s] < c_defnum[semi])
 257                                 semi = s;               /* if the def-num of the new candidate is lower */
 258                                                                 /* than old one, it gets new semi dominator             */
 259                         }
 260
 261                 /* write semi dominator -> according to SEMIDOMINATOR THEOREM                   */
 262                 c_semi_dom[actual] = semi;
 263                 c_ancestor[actual] = p;
 264
 265                 c_bucket[semi][c_numBucket[semi]] = actual;
 266                 c_numBucket[semi]++;    /* defer calculation of dominator to final pass */
 267
 268
 269                 /* first clause of DOMINATOR THEOREM, try to find dominator now                 */
 270                 for (j=0; j<c_numBucket[p]; ++j) {
 271                         v = c_bucket[p][j];
 272                         y = findLowAnc(v);
 273
 274                         if (c_semi_dom[y] == c_semi_dom[v])
 275                                 c_idom[v] = p;                  /* if y's dominator is already known    */
 276                                                                                 /* found it and write to c_idom                 */
 277                         else
 278                                 c_same_dom[v] = y;              /* wait till final pass                                 */
 279                         }
 280
 281                 c_numBucket[p] = 0;
 282                 }
 283
 284         /* final pass to get missing dominators ->second clause of DOMINATOR THEORM     */
 285         for (j=1; j<(c_globalCount-1); ++j) {
 286                 if (c_same_dom[c_reverse[j]] != -1)
 287                         c_idom[c_reverse[j]] = c_idom[c_same_dom[c_reverse[j]]];
 288                 }
 289 }
 290
 291
 292 /*
 293    A helper function needed by detectLoops() that checks, whether a given
 294    connection between two nodes in the control flow graph is possibly part
 295    of a loop (is a backEdge).
 296 */
 297 int isBackEdge(int from, int to)
 298 {
 299         int tmp = c_idom[to];   /* speed optimization: if the to-node is dominated      */
 300         while (tmp != -1) {             /* by the from node as it is most of the time,          */
 301                 if (tmp == from)        /* there is no backEdge                                                         */
 302                         return 0;
 303                 tmp = c_idom[tmp];
 304                 }
 305
 306         tmp = c_idom[from];             /* if from-node doesn't dominate to-node, we have       */
 307         while (tmp != -1) {             /* to climb all the way up from the from-node to        */
 308                 if (tmp == to)          /* the top to check, whether it is dominated by to      */
 309                         return 1;               /* if so, return a backedge                                                     */
 310                 tmp = c_idom[tmp];
 311                 }
 312
 313         return 0;                               /* else, there is no backedge                                           */
 314 }
 315
 316
 317 /*
 318    These stack functions are helper functions for createLoop(int, int)
 319    to manage the set of nodes in the current loop.
 320 */
 321 void push(methodinfo *m, int i, struct LoopContainer *lc)
 322 {
 323         struct LoopElement *le = lc->nodes, *t;
 324
 325         if (!c_contains[i])     {
 326                 t = DMNEW(struct LoopElement, 1);
 327
 328                 t->node = i;
 329                 t->block = &m->basicblocks[i];
 330
 331                 c_contains[i] = 1;
 332
 333                 if (i < le->node)
 334                 {
 335                         t->next = lc->nodes;
 336                         lc->nodes = t;
 337                 }
 338                 else
 339                 {
 340                         while ((le->next != NULL) && (le->next->node < i))
 341                                 le = le->next;
 342
 343                         t->next = le->next;
 344                         le->next = t;
 345                 }
 346
 347                 c_stack[c_stackPointer++] = i;
 348         }
 349 }
 350
 351
 352 int pop()
 353 {
 354         return (c_stack[--c_stackPointer]);
 355 }
 356
 357
 358 int isFull()
 359 {
 360         return (c_stackPointer);
 361 }
 362
 363
 364 /*
 365    This function is a helper function, that finds all nodes, that belong to
 366    the loop with a known header node and a member node of the loop (and a
 367    back edge between these two nodes).
 368 */
 369 void createLoop(methodinfo *m, int header, int member)
 370 {
 371         int i, nextMember;
 372
 373         struct LoopContainer *currentLoop = (struct LoopContainer *) malloc(sizeof(struct LoopContainer));
 374         LoopContainerInit(m, currentLoop, header);              /* set up loop structure                */
 375
 376         for (i=0; i<m->basicblockcount; ++i)
 377                 c_contains[i] = 0;
 378         c_contains[header] = 1;
 379
 380         c_stackPointer = 0;                             /* init stack with first node of the loop       */
 381         push(m, member, currentLoop);
 382
 383         while (isFull()) {                              /* while there are still unvisited nodes        */
 384                 nextMember = pop();
 385
 386                 /* push all predecessors, while they are not equal to loop header               */
 387                 for (i=0; i<c_numPre[nextMember]; ++i)
 388                         push(m, c_pre[nextMember][i], currentLoop);
 389                 }
 390
 391         currentLoop->next = c_allLoops;
 392         c_allLoops = currentLoop;
 393 }
 394
 395
 396 /*      After all dominators have been calculated, the loops can be detected and
 397          added to the global list c_allLoops.
 398 */
 399 void detectLoops(methodinfo *m)
 400 {
 401         int i;
 402         struct depthElement *h;
 403
 404         /* for all edges in the control flow graph do                                                           */
 405         for (i=0; i<m->basicblockcount; ++i) {
 406                 h = c_dTable[i];
 407
 408                 while (h != NULL) {
 409                         /* if it's a backedge, than add a new loop to list                                      */
 410                         if (isBackEdge(i, h->value))
 411                                 createLoop(m, h->value, i);
 412                         h = h->next;
 413                         }
 414                 }
 415 }
 416
 417
 418 /*
 419    This function is called by higher level routines to perform the loop
 420    detection and set up the c_allLoops list.
 421 */
 422 void analyseGraph(methodinfo *m)
 423 {
 424   setup(m);
 425   dominators();
 426   detectLoops(m);
 427 }
 428
 429
 430 /*
 431    Test function -> will be removed in final release
 432 */
 433 void resultPass2()
 434 {
 435   int i;
 436   struct LoopContainer *lc = c_allLoops;
 437   struct LoopElement *le;
 438
 439   printf("\n\n****** PASS 2 ******\n\n");
 440
 441   printf("Loops:\n\n");
 442
 443   i = 0;
 444   while (lc != NULL) {
 445           printf("Loop [%d]: ", ++i);
 446
 447           le = lc->nodes;
 448           while (le != NULL) {
 449             printf("%d ", le->node);
 450                 printf("\n");
 451                 le = le->next;
 452           }
 453
 454           lc = lc->next;
 455   }
 456
 457   printf("\n");
 458
 459 }
 460
 461
 462 void c_mem_error()
 463 {
 464   panic("C_ERROR: Not enough memeory");
 465 }
 466
 467
 468 /*
 469  * These are local overrides for various environment variables in Emacs.
 470  * Please do not remove this and leave it at the end of the file, where
 471  * Emacs will automagically detect them.
 472  * ---------------------------------------------------------------------
 473  * Local variables:
 474  * mode: c
 475  * indent-tabs-mode: t
 476  * c-basic-offset: 4
 477  * tab-width: 4
 478  * End:
 479  */