1 /* jit/loop/loop.c - array bound removal
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
8 This file is part of CACAO.
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.
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.
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
25 Contact: cacao@complang.tuwien.ac.at
27 Authors: Christopher Kruegel EMAIL: cacao@complang.tuwien.ac.at
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)
33 $Id: loop.c 557 2003-11-02 22:51:59Z twisti $
43 #include "toolbox/loging.h"
44 #include "toolbox/memory.h"
49 int c_debug_nr; /* a counter to number all BB with an unique */
52 /* modified by graph.c */
54 int *c_defnum; /* array that stores a number for each node when*/
55 /* control flow graph is traveres depth first */
56 int *c_parent; /* for each node that array stores its parent */
57 int *c_reverse; /* for each def number that array stores the */
58 /* corresponding node */
59 int c_globalCount; /* counter for def numbering */
60 int *c_numPre; /* array that stores for each node its number */
62 int **c_pre; /* array of array that stores predecessors */
63 int c_last_jump; /* stores the source node of the last jsr instr */
64 basicblock *c_last_target; /* stores the source BB of the last jsr instr */
66 struct depthElement **c_dTable; /* adjacency list for control flow graph */
67 struct depthElement **c_exceptionGraph; /* adjacency list for exception graph */
69 struct LoopContainer *c_allLoops; /* list of all loops */
70 struct LoopContainer *c_loop_root; /* root of loop hierarchie tree */
72 int *c_exceptionVisit; /* array that stores a flag for each node part */
73 /* of the exception graph */
75 /* modified by loop.c */
77 int *c_semi_dom; /* store for each node its semi dominator */
78 int *c_idom; /* store for each node its dominator */
79 int *c_same_dom; /* temp array to hold nodes with same dominator */
80 int *c_ancestor; /* store for each node its ancestor with lowest */
85 int *c_contains; /* store for each node whether it's part of loop*/
86 int *c_stack; /* a simple stack as array */
87 int c_stackPointer; /* stackpointer */
90 /* modified by analyze.c */
92 struct LoopContainer *root; /* the root pointer for the hierarchie tree of */
93 /* all loops in that procedure */
95 int c_needed_instr; /* number of instructions that have to be */
96 /* inserted before loop header to make sure */
97 /* array optimization is legal */
98 int c_rs_needed_instr; /* number of instructions needed to load the */
99 /* value ofthe right side of the loop condition */
100 int *c_nestedLoops; /* store for each node the header node of the */
101 /* loop this node belongs to, -1 for none */
102 int *c_hierarchie; /* store a loop hierarchie */
103 int *c_toVisit; /* set for each node that is part of the loop */
105 int *c_current_loop; /* for each node: */
106 /* store 0: node is not part of loop */
107 /* store 1: node is loop header */
108 /* store 2: node is in loop but not part of any */
110 /* store 3: node is part of nested loop */
112 int c_current_head; /* store number of node that is header of loop */
113 int *c_var_modified; /* store for each local variable whether its */
114 /* value is changed in the loop */
116 struct Trace *c_rightside; /* right side of loop condition */
117 struct Constraint **c_constraints;
118 /* array that stores for each variable a list */
119 /* static tests (constraints) that have to be */
120 /* performed before loop entry */
121 /* IMPORTANT: c_constraints[maxlocals] stores */
122 /* the tests for constants and the */
123 /* right side of loop condition */
125 struct LoopVar *c_loopvars; /* a list of all intersting variables of the */
126 /* current loop (variables that are modified or */
127 /* used as array index */
129 basicblock *c_first_block_copied; /* pointer to the first block, that is copied */
130 /* during loop duplication */
132 basicblock *c_last_block_copied; /* last block, that is copied during loop */
135 int *c_null_check; /* array to store for local vars, whether they */
136 /* need to be checked against the null reference*/
137 /* in the loop head */
139 bool c_needs_redirection; /* if a loop header is inserted as first block */
140 /* into the global BB list, this is set to true */
142 basicblock *c_newstart; /* if a loop header is inserted as first block */
143 /* into the gloal BB list, this pointer is the */
145 int c_old_xtablelength; /* used to store the original tablelength */
151 /* declare statistic variables */
154 int c_stat_num_loops; /* number of loops */
156 /* statistics per loop */
157 int c_stat_array_accesses; /* number of array accesses */
159 int c_stat_full_opt; /* number of fully optimized accesses */
160 int c_stat_no_opt; /* number of not optimized accesses */
161 int c_stat_lower_opt; /* number of accesses where check against zero */
163 int c_stat_upper_opt; /* number of accesses where check against array */
164 /* lengh is removed */
165 int c_stat_or; /* set if optimization is cancelled because of */
166 /* or in loop condition */
167 int c_stat_exception; /* set if optimization is cancelled because of */
168 /* index var modified in catch block */
170 /* statistics per procedure */
171 int c_stat_sum_accesses; /* number of array accesses */
173 int c_stat_sum_full; /* number of fully optimized accesses */
174 int c_stat_sum_no; /* number of not optimized accesses */
175 int c_stat_sum_lower; /* number of accesses where check against zero */
177 int c_stat_sum_upper; /* number of accesses where check against array */
178 /* lengh is removed */
179 int c_stat_sum_or; /* set if optimization is cancelled because of */
180 /* or in loop condition */
181 int c_stat_sum_exception; /* set if optimization is cancelled because of */
187 This function allocates and initializes variables, that are used by the
188 loop detection algorithm
194 c_semi_dom = DMNEW(int, block_count);
195 c_idom = DMNEW(int, block_count);
196 c_same_dom = DMNEW(int, block_count);
197 c_numBucket = DMNEW(int, block_count);
198 c_ancestor = DMNEW(int, block_count);
199 c_contains = DMNEW(int, block_count);
200 c_stack = DMNEW(int, block_count);
201 c_bucket = DMNEW(int*, block_count);
203 for (i = 0; i < block_count; ++i) {
205 c_stack[i] = c_ancestor[i] = c_semi_dom[i] = c_same_dom[i] = c_idom[i] = -1;
207 c_bucket[i] = DMNEW(int, block_count);
212 /* This function is a helper function for dominators and has to find the
213 ancestor of the node v in the control graph, which semi-dominator has the
216 int findLowAnc(int v)
218 int u = v; /* u is the node which has the current lowest semi-dom */
220 while (c_ancestor[v] != -1) { /* as long as v has an ancestor, continue */
221 if (c_defnum[c_semi_dom[v]] < c_defnum[c_semi_dom[u]])
222 /* if v's semi-dom is smaller */
223 u = v; /* it gets the new current node u */
224 v = c_ancestor[v]; /* climb one step up in the tree */
226 return u; /* return node with the lowest semi-dominator def-num */
230 /* This function builds the dominator tree out of a given control flow graph and
231 stores its results in c_idom[]. It first calculates the number of possible
232 dominators in c_bucket and eventually determines the single dominator in a
237 int i, j, semi, s, n, v, actual, p, y;
239 for (n=(c_globalCount-1); n>0; --n) { /* for all nodes (except last), do */
240 actual = c_reverse[n];
241 semi = p = c_parent[actual];
243 /* for all predecessors of current node, do */
244 for (i=0; i<c_numPre[actual]; ++i) {
245 v = c_pre[actual][i];
247 if (c_defnum[v] <= c_defnum[actual])
248 s = v; /* if predecessor has lower def-num than node */
249 /* it becomes candidate for semi dominator */
251 s = c_semi_dom[findLowAnc(v)];
252 /* else the semi-dominator of it's ancestor */
253 /* with lowest def-num becomes candidate */
255 if (c_defnum[s] < c_defnum[semi])
256 semi = s; /* if the def-num of the new candidate is lower */
257 /* than old one, it gets new semi dominator */
260 /* write semi dominator -> according to SEMIDOMINATOR THEOREM */
261 c_semi_dom[actual] = semi;
262 c_ancestor[actual] = p;
264 c_bucket[semi][c_numBucket[semi]] = actual;
265 c_numBucket[semi]++; /* defer calculation of dominator to final pass */
268 /* first clause of DOMINATOR THEOREM, try to find dominator now */
269 for (j=0; j<c_numBucket[p]; ++j) {
273 if (c_semi_dom[y] == c_semi_dom[v])
274 c_idom[v] = p; /* if y's dominator is already known */
275 /* found it and write to c_idom */
277 c_same_dom[v] = y; /* wait till final pass */
283 /* final pass to get missing dominators ->second clause of DOMINATOR THEORM */
284 for (j=1; j<(c_globalCount-1); ++j) {
285 if (c_same_dom[c_reverse[j]] != -1)
286 c_idom[c_reverse[j]] = c_idom[c_same_dom[c_reverse[j]]];
292 A helper function needed by detectLoops() that checks, whether a given
293 connection between two nodes in the control flow graph is possibly part
294 of a loop (is a backEdge).
296 int isBackEdge(int from, int to)
298 int tmp = c_idom[to]; /* speed optimization: if the to-node is dominated */
299 while (tmp != -1) { /* by the from node as it is most of the time, */
300 if (tmp == from) /* there is no backEdge */
305 tmp = c_idom[from]; /* if from-node doesn't dominate to-node, we have */
306 while (tmp != -1) { /* to climb all the way up from the from-node to */
307 if (tmp == to) /* the top to check, whether it is dominated by to */
308 return 1; /* if so, return a backedge */
312 return 0; /* else, there is no backedge */
317 These stack functions are helper functions for createLoop(int, int)
318 to manage the set of nodes in the current loop.
320 void push(int i, struct LoopContainer *lc)
322 struct LoopElement *le = lc->nodes, *t;
324 if (!c_contains[i]) {
325 t = DMNEW(struct LoopElement, 1);
328 t->block = &block[i];
339 while ((le->next != NULL) && (le->next->node < i))
346 c_stack[c_stackPointer++] = i;
353 return (c_stack[--c_stackPointer]);
359 return (c_stackPointer);
364 This function is a helper function, that finds all nodes, that belong to
365 the loop with a known header node and a member node of the loop (and a
366 back edge between these two nodes).
368 void createLoop(int header, int member)
372 struct LoopContainer *currentLoop = (struct LoopContainer *) malloc(sizeof(struct LoopContainer));
373 LoopContainerInit(currentLoop, header); /* set up loop structure */
375 for (i=0; i<block_count; ++i)
377 c_contains[header] = 1;
379 c_stackPointer = 0; /* init stack with first node of the loop */
380 push(member, currentLoop);
382 while (isFull()) { /* while there are still unvisited nodes */
385 /* push all predecessors, while they are not equal to loop header */
386 for (i=0; i<c_numPre[nextMember]; ++i)
387 push(c_pre[nextMember][i], currentLoop);
390 currentLoop->next = c_allLoops;
391 c_allLoops = currentLoop;
395 /* After all dominators have been calculated, the loops can be detected and
396 added to the global list c_allLoops.
401 struct depthElement *h;
403 /* for all edges in the control flow graph do */
404 for (i=0; i<block_count; ++i) {
408 /* if it's a backedge, than add a new loop to list */
409 if (isBackEdge(i, h->value))
410 createLoop(h->value, i);
418 This function is called by higher level routines to perform the loop
419 detection and set up the c_allLoops list.
430 Test function -> will be removed in final release
435 struct LoopContainer *lc = c_allLoops;
436 struct LoopElement *le;
438 printf("\n\n****** PASS 2 ******\n\n");
440 printf("Loops:\n\n");
444 printf("Loop [%d]: ", ++i);
448 printf("%d ", le->node);
463 panic("C_ERROR: Not enough memeory");
468 * These are local overrides for various environment variables in Emacs.
469 * Please do not remove this and leave it at the end of the file, where
470 * Emacs will automagically detect them.
471 * ---------------------------------------------------------------------
474 * indent-tabs-mode: t