1 /* src/vm/jit/loop/graph.c - control flow graph
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 Contains the functions which build a list, that represents the
32 control flow graph of the procedure, that is being analyzed.
39 #include "mm/memory.h"
40 #include "toolbox/logging.h"
41 #include "vm/jit/jit.h"
42 #include "vm/jit/loop/graph.h"
43 #include "vm/jit/loop/loop.h"
46 void LoopContainerInit(methodinfo *m, struct LoopContainer *lc, int i)
48 struct LoopElement *le = DMNEW(struct LoopElement, 1);
54 lc->tree_right = NULL;
57 lc->exceptions = NULL;
60 le->node = lc->loop_head = i;
61 le->block = &m->basicblocks[i];
63 /* lc->nodes = (int *) malloc(sizeof(int)*m->basicblockcount);
71 depthFirst() builds the control flow graph out of the intermediate code of
72 the procedure, that is to be optimized and stores the list in the global
76 void depthFirst(jitdata *jd)
82 /* get required compiler data */
87 /* allocate memory and init gobal variables needed by function dF(m, int, int) */
89 ld->c_defnum = DMNEW(int, m->basicblockcount);
90 ld->c_numPre = DMNEW(int, m->basicblockcount);
91 ld->c_parent = DMNEW(int, m->basicblockcount);
92 ld->c_reverse = DMNEW(int, m->basicblockcount);
93 ld->c_pre = DMNEW(int *, m->basicblockcount);
94 ld->c_dTable = DMNEW(struct depthElement *, m->basicblockcount);
96 for (i = 0; i < m->basicblockcount; ++i) {
97 ld->c_defnum[i] = ld->c_parent[i] = -1;
98 ld->c_numPre[i] = ld->c_reverse[i] = 0;
100 ld->c_pre[i] = DMNEW(int, m->basicblockcount);
101 ld->c_dTable[i] = NULL;
104 ld->c_globalCount = 0;
105 ld->c_allLoops = NULL;
107 dF(m, ld, -1, 0); /* call helper function dF that traverses basic block structure */
112 dF starts from the first block of the given procedure and traverses the
113 control flow graph in a depth-first order, thereby building up the adeacency
117 void dF(methodinfo *m, loopdata *ld, int from, int blockIndex)
121 int high, low, count;
122 struct depthElement *hp;
123 struct LoopContainer *tmp;
127 /* the current basic block has a predecessor (ie. is not the first one) */
128 hp = DNEW(struct depthElement);/* create new depth element */
130 hp->next = ld->c_dTable[from]; /* insert values */
131 hp->value = blockIndex;
134 ld->c_dTable[from] = hp; /* insert into table */
137 if (from == blockIndex) { /* insert one node loops into loop container */
138 tmp = DNEW(struct LoopContainer);
139 LoopContainerInit(m, tmp, blockIndex);
140 tmp->next = ld->c_allLoops;
141 ld->c_allLoops = tmp;
145 if (blockIndex > m->basicblockcount) {
146 log_text("DepthFirst: BlockIndex exceeded\n");
151 ip = m->basicblocks[blockIndex].iinstr + m->basicblocks[blockIndex].icount -1;
152 /* set ip to last instruction */
154 if (ld->c_defnum[blockIndex] == -1) { /* current block has not been visited */
155 ld->c_defnum[blockIndex] = ld->c_globalCount; /* update global count */
156 ld->c_parent[blockIndex] = from; /* write parent block of current one */
157 ld->c_reverse[ld->c_globalCount] = blockIndex;
160 if (!m->basicblocks[blockIndex].icount) {
161 /* block does not contain instructions */
162 dF(m, ld, blockIndex, blockIndex+1);
164 else { /* for all successors, do */
165 switch (ip->opc) { /* check type of last instruction */
173 break; /* function returns -> end of graph */
202 case ICMD_IF_ACMPNE: /* branch -> check next block */
203 dF(m, ld, blockIndex, blockIndex + 1);
207 dF(m, ld, blockIndex, m->basicblockindex[ip->op1]);
208 break; /* visit branch (goto) target */
210 case ICMD_TABLESWITCH: /* switch statement */
213 dF(m, ld, blockIndex, m->basicblockindex[*s4ptr]); /* default branch */
220 count = (high-low+1);
222 while (--count >= 0) {
224 dF(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
228 case ICMD_LOOKUPSWITCH: /* switch statement */
231 dF(m, ld, blockIndex, m->basicblockindex[*s4ptr]); /* default branch */
236 while (--count >= 0) {
237 dF(m, ld, blockIndex, m->basicblockindex[s4ptr[1]]);
243 ld->c_last_jump = blockIndex;
244 dF(m, ld, blockIndex, m->basicblockindex[ip->op1]);
248 dF(m, ld, blockIndex, ld->c_last_jump+1);
252 dF(m, ld, blockIndex, blockIndex + 1);
258 for (ptr = ld->c_pre[blockIndex], cnt = 0; cnt < ld->c_numPre[blockIndex]; ++cnt, ++ptr)
264 if (cnt >= ld->c_numPre[blockIndex]) {
265 ld->c_pre[blockIndex][ld->c_numPre[blockIndex]] = from;
266 /* add predeccessors to list c_pre */
267 ld->c_numPre[blockIndex]++; /* increase number of predecessors */
274 a slightly modified version of dF(m, ld, int, int) that is used to traverse the part
275 of the control graph that is not reached by normal program flow but by the
276 raising of exceptions (code of catch blocks)
279 void dF_Exception(methodinfo *m, loopdata *ld, int from, int blockIndex)
283 int high, low, count;
284 struct depthElement *hp;
286 if (ld->c_exceptionVisit[blockIndex] < 0) /* has block been visited, return */
287 ld->c_exceptionVisit[blockIndex] = 1;
291 if (ld->c_dTable[blockIndex] != NULL) /* back to regular code section */
294 if (from >= 0) { /* build exception graph (in c_exceptionGraph) */
295 hp = DNEW(struct depthElement);
296 hp->next = ld->c_exceptionGraph[from];
297 hp->value = blockIndex;
300 ld->c_exceptionGraph[from] = hp;
304 if (blockIndex > m->basicblockcount) {
305 log_text("DepthFirst: BlockIndex exceeded");
310 ip = m->basicblocks[blockIndex].iinstr + m->basicblocks[blockIndex].icount -1;
312 if (!m->basicblocks[blockIndex].icount)
313 dF_Exception(m, ld, blockIndex, blockIndex+1);
352 case ICMD_IF_ACMPNE: /* branch -> check next block */
353 dF_Exception(m, ld, blockIndex, blockIndex + 1);
357 dF_Exception(m, ld, blockIndex, m->basicblockindex[ip->op1]);
360 case ICMD_TABLESWITCH:
364 dF_Exception(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
371 count = (high-low+1);
373 while (--count >= 0) {
375 dF_Exception(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
379 case ICMD_LOOKUPSWITCH:
383 dF_Exception(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
388 while (--count >= 0) {
389 dF_Exception(m, ld, blockIndex, m->basicblockindex[s4ptr[1]]);
395 ld->c_last_jump = blockIndex;
396 dF_Exception(m, ld, blockIndex, m->basicblockindex[ip->op1]);
400 dF_Exception(m, ld, blockIndex, ld->c_last_jump+1);
404 dF_Exception(m, ld, blockIndex, blockIndex + 1);
413 Test function -> will be removed in final release
415 void resultPass1(methodinfo *m)
418 struct depthElement *hp;
420 printf("\n\n****** PASS 1 ******\n\n");
421 printf("Number of Nodes: %d\n\n", ld->c_globalCount);
423 printf("Predecessors:\n");
424 for (i=0; i<m->basicblockcount; ++i) {
425 printf("Block %d:\t", i);
426 for (j=0; j<ld->c_numPre[i]; ++j)
427 printf("%d ", ld->c_pre[i][j]);
433 for (i=0; i<m->basicblockcount; ++i) {
434 printf("Block %d:\t", i);
435 hp = ld->c_dTable[i];
438 printf("%d ", hp->value);
448 * These are local overrides for various environment variables in Emacs.
449 * Please do not remove this and leave it at the end of the file, where
450 * Emacs will automagically detect them.
451 * ---------------------------------------------------------------------
454 * indent-tabs-mode: t