1 /* src/vm/jit/loop/loop.c - array bound removal
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
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., 51 Franklin Street, Fifth Floor, Boston, MA
25 Contact: cacao@cacaojvm.org
27 Authors: Christopher Kruegel
29 Changes: Christian Thalinger
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)
35 $Id: loop.c 4699 2006-03-28 14:52:32Z twisti $
41 /* #include <stdio.h> */
44 #include "mm/memory.h"
45 #include "toolbox/logging.h"
46 #include "vm/global.h"
47 #include "vm/jit/jit.h"
48 #include "vm/jit/loop/loop.h"
49 #include "vm/jit/loop/graph.h"
50 #include "vm/jit/loop/tracing.h"
54 This function allocates and initializes variables, that are used by the
55 loop detection algorithm
57 void setup(methodinfo *m, loopdata *ld)
61 ld->c_semi_dom = DMNEW(int, m->basicblockcount);
62 ld->c_idom = DMNEW(int, m->basicblockcount);
63 ld->c_same_dom = DMNEW(int, m->basicblockcount);
64 ld->c_numBucket = DMNEW(int, m->basicblockcount);
65 ld->c_ancestor = DMNEW(int, m->basicblockcount);
66 ld->c_contains = DMNEW(int, m->basicblockcount);
67 ld->c_stack = DMNEW(int, m->basicblockcount);
68 ld->c_bucket = DMNEW(int*, m->basicblockcount);
70 for (i = 0; i < m->basicblockcount; ++i) {
71 ld->c_numBucket[i] = 0;
72 ld->c_stack[i] = ld->c_ancestor[i] = ld->c_semi_dom[i] = ld->c_same_dom[i] = ld->c_idom[i] = -1;
74 ld->c_bucket[i] = DMNEW(int, m->basicblockcount);
79 /* This function is a helper function for dominators and has to find the
80 ancestor of the node v in the control graph, which semi-dominator has the
84 int findLowAnc(loopdata *ld, int v)
86 int u = v; /* u is the node which has the current lowest semi-dom */
88 while (ld->c_ancestor[v] != -1) { /* as long as v has an ancestor, continue */
89 if (ld->c_defnum[ld->c_semi_dom[v]] < ld->c_defnum[ld->c_semi_dom[u]])
90 /* if v's semi-dom is smaller */
91 u = v; /* it gets the new current node u */
92 v = ld->c_ancestor[v]; /* climb one step up in the tree */
94 return u; /* return node with the lowest semi-dominator def-num */
98 /* This function builds the dominator tree out of a given control flow graph and
99 stores its results in c_idom[]. It first calculates the number of possible
100 dominators in c_bucket and eventually determines the single dominator in a
104 void dominators(loopdata *ld)
106 int i, j, semi, s, n, v, actual, p, y;
108 for (n=(ld->c_globalCount-1); n>0; --n) { /* for all nodes (except last), do */
109 actual = ld->c_reverse[n];
110 semi = p = ld->c_parent[actual];
112 /* for all predecessors of current node, do */
113 for (i=0; i<ld->c_numPre[actual]; ++i) {
114 v = ld->c_pre[actual][i];
116 if (ld->c_defnum[v] <= ld->c_defnum[actual])
117 s = v; /* if predecessor has lower def-num than node */
118 /* it becomes candidate for semi dominator */
120 s = ld->c_semi_dom[findLowAnc(ld, v)];
121 /* else the semi-dominator of it's ancestor */
122 /* with lowest def-num becomes candidate */
124 if (ld->c_defnum[s] < ld->c_defnum[semi])
125 semi = s; /* if the def-num of the new candidate is lower */
126 /* than old one, it gets new semi dominator */
129 /* write semi dominator -> according to SEMIDOMINATOR THEOREM */
130 ld->c_semi_dom[actual] = semi;
131 ld->c_ancestor[actual] = p;
133 ld->c_bucket[semi][ld->c_numBucket[semi]] = actual;
134 ld->c_numBucket[semi]++; /* defer calculation of dominator to final pass */
137 /* first clause of DOMINATOR THEOREM, try to find dominator now */
138 for (j=0; j<ld->c_numBucket[p]; ++j) {
139 v = ld->c_bucket[p][j];
140 y = findLowAnc(ld, v);
142 if (ld->c_semi_dom[y] == ld->c_semi_dom[v])
143 ld->c_idom[v] = p; /* if y's dominator is already known */
144 /* found it and write to c_idom */
146 ld->c_same_dom[v] = y; /* wait till final pass */
149 ld->c_numBucket[p] = 0;
152 /* final pass to get missing dominators ->second clause of DOMINATOR THEORM */
153 for (j=1; j<(ld->c_globalCount-1); ++j) {
154 if (ld->c_same_dom[ld->c_reverse[j]] != -1)
155 ld->c_idom[ld->c_reverse[j]] = ld->c_idom[ld->c_same_dom[ld->c_reverse[j]]];
161 A helper function needed by detectLoops() that checks, whether a given
162 connection between two nodes in the control flow graph is possibly part
163 of a loop (is a backEdge).
166 int isBackEdge(loopdata *ld, int from, int to)
168 int tmp = ld->c_idom[to]; /* speed optimization: if the to-node is dominated */
169 while (tmp != -1) { /* by the from node as it is most of the time, */
170 if (tmp == from) /* there is no backEdge */
172 tmp = ld->c_idom[tmp];
175 tmp = ld->c_idom[from]; /* if from-node doesn't dominate to-node, we have */
176 while (tmp != -1) { /* to climb all the way up from the from-node to */
177 if (tmp == to) /* the top to check, whether it is dominated by to */
178 return 1; /* if so, return a backedge */
179 tmp = ld->c_idom[tmp];
182 return 0; /* else, there is no backedge */
187 These stack functions are helper functions for createLoop(int, int)
188 to manage the set of nodes in the current loop.
191 void push(methodinfo *m, loopdata *ld, int i, struct LoopContainer *lc)
193 struct LoopElement *le = lc->nodes, *t;
195 if (!ld->c_contains[i]) {
196 t = DMNEW(struct LoopElement, 1);
199 t->block = &m->basicblocks[i];
201 ld->c_contains[i] = 1;
210 while ((le->next != NULL) && (le->next->node < i))
217 ld->c_stack[ld->c_stackPointer++] = i;
222 int pop(loopdata *ld)
224 return (ld->c_stack[--ld->c_stackPointer]);
228 int isFull(loopdata *ld)
230 return (ld->c_stackPointer);
235 This function is a helper function, that finds all nodes, that belong to
236 the loop with a known header node and a member node of the loop (and a
237 back edge between these two nodes).
240 void createLoop(methodinfo *m, loopdata *ld, int header, int member)
244 struct LoopContainer *currentLoop = (struct LoopContainer *) malloc(sizeof(struct LoopContainer));
245 LoopContainerInit(m, currentLoop, header); /* set up loop structure */
247 for (i=0; i<m->basicblockcount; ++i)
248 ld->c_contains[i] = 0;
249 ld->c_contains[header] = 1;
251 ld->c_stackPointer = 0; /* init stack with first node of the loop */
252 push(m, ld, member, currentLoop);
254 while (isFull(ld)) { /* while there are still unvisited nodes */
255 nextMember = pop(ld);
257 /* push all predecessors, while they are not equal to loop header */
258 for (i=0; i<ld->c_numPre[nextMember]; ++i)
259 push(m, ld, ld->c_pre[nextMember][i], currentLoop);
262 currentLoop->next = ld->c_allLoops;
263 ld->c_allLoops = currentLoop;
267 /* After all dominators have been calculated, the loops can be detected and
268 added to the global list c_allLoops.
271 void detectLoops(methodinfo *m, loopdata *ld)
274 struct depthElement *h;
276 /* for all edges in the control flow graph do */
277 for (i=0; i<m->basicblockcount; ++i) {
281 /* if it's a backedge, than add a new loop to list */
282 if (isBackEdge(ld, i, h->value))
283 createLoop(m, ld, h->value, i);
291 This function is called by higher level routines to perform the loop
292 detection and set up the c_allLoops list.
295 void analyseGraph(jitdata *jd)
300 /* get required compiler data */
312 Test function -> will be removed in final release
315 void resultPass2(loopdata *ld)
318 struct LoopContainer *lc = ld->c_allLoops;
319 struct LoopElement *le;
321 printf("\n\n****** PASS 2 ******\n\n");
323 printf("Loops:\n\n");
327 printf("Loop [%d]: ", ++i);
331 printf("%d ", le->node);
346 log_text("C_ERROR: Not enough memeory");
352 * These are local overrides for various environment variables in Emacs.
353 * Please do not remove this and leave it at the end of the file, where
354 * Emacs will automagically detect them.
355 * ---------------------------------------------------------------------
358 * indent-tabs-mode: t