1 /* vm/jit/loop/graph.c - control flow graph
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
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
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.
34 $Id: graph.c 1735 2004-12-07 14:33:27Z twisti $
39 #include "mm/memory.h"
40 #include "vm/jit/jit.h"
41 #include "vm/jit/loop/graph.h"
42 #include "vm/jit/loop/loop.h"
45 void LoopContainerInit(methodinfo *m, struct LoopContainer *lc, int i)
47 struct LoopElement *le = DMNEW(struct LoopElement, 1);
53 lc->tree_right = NULL;
56 lc->exceptions = NULL;
59 le->node = lc->loop_head = i;
60 le->block = &m->basicblocks[i];
62 /* lc->nodes = (int *) malloc(sizeof(int)*m->basicblockcount);
70 depthFirst() builds the control flow graph out of the intermediate code of
71 the procedure, that is to be optimized and stores the list in the global
75 void depthFirst(methodinfo *m, loopdata *ld)
79 /* allocate memory and init gobal variables needed by function dF(m, int, int) */
81 ld->c_defnum = DMNEW(int, m->basicblockcount);
82 ld->c_numPre = DMNEW(int, m->basicblockcount);
83 ld->c_parent = DMNEW(int, m->basicblockcount);
84 ld->c_reverse = DMNEW(int, m->basicblockcount);
85 ld->c_pre = DMNEW(int *, m->basicblockcount);
86 ld->c_dTable = DMNEW(struct depthElement *, m->basicblockcount);
88 for (i = 0; i < m->basicblockcount; ++i) {
89 ld->c_defnum[i] = ld->c_parent[i] = -1;
90 ld->c_numPre[i] = ld->c_reverse[i] = 0;
92 ld->c_pre[i] = DMNEW(int, m->basicblockcount);
93 ld->c_dTable[i] = NULL;
96 ld->c_globalCount = 0;
97 ld->c_allLoops = NULL;
99 dF(m, ld, -1, 0); /* call helper function dF that traverses basic block structure */
104 dF starts from the first block of the given procedure and traverses the
105 control flow graph in a depth-first order, thereby building up the adeacency
109 void dF(methodinfo *m, loopdata *ld, int from, int blockIndex)
113 int high, low, count;
114 struct depthElement *hp;
115 struct LoopContainer *tmp;
119 /* the current basic block has a predecessor (ie. is not the first one) */
120 hp = DNEW(struct depthElement);/* create new depth element */
122 hp->next = ld->c_dTable[from]; /* insert values */
123 hp->value = blockIndex;
126 ld->c_dTable[from] = hp; /* insert into table */
129 if (from == blockIndex) { /* insert one node loops into loop container */
130 tmp = DNEW(struct LoopContainer);
131 LoopContainerInit(m, tmp, blockIndex);
132 tmp->next = ld->c_allLoops;
133 ld->c_allLoops = tmp;
137 if (blockIndex > m->basicblockcount) {
138 panic("DepthFirst: BlockIndex exceeded\n");
142 ip = m->basicblocks[blockIndex].iinstr + m->basicblocks[blockIndex].icount -1;
143 /* set ip to last instruction */
145 if (ld->c_defnum[blockIndex] == -1) { /* current block has not been visited */
146 ld->c_defnum[blockIndex] = ld->c_globalCount; /* update global count */
147 ld->c_parent[blockIndex] = from; /* write parent block of current one */
148 ld->c_reverse[ld->c_globalCount] = blockIndex;
151 if (!m->basicblocks[blockIndex].icount) {
152 /* block does not contain instructions */
153 dF(m, ld, blockIndex, blockIndex+1);
155 else { /* for all successors, do */
156 switch (ip->opc) { /* check type of last instruction */
164 break; /* function returns -> end of graph */
193 case ICMD_IF_ACMPNE: /* branch -> check next block */
194 dF(m, ld, blockIndex, blockIndex + 1);
198 dF(m, ld, blockIndex, m->basicblockindex[ip->op1]);
199 break; /* visit branch (goto) target */
201 case ICMD_TABLESWITCH: /* switch statement */
204 dF(m, ld, blockIndex, m->basicblockindex[*s4ptr]); /* default branch */
211 count = (high-low+1);
213 while (--count >= 0) {
215 dF(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
219 case ICMD_LOOKUPSWITCH: /* switch statement */
222 dF(m, ld, blockIndex, m->basicblockindex[*s4ptr]); /* default branch */
227 while (--count >= 0) {
228 dF(m, ld, blockIndex, m->basicblockindex[s4ptr[1]]);
234 ld->c_last_jump = blockIndex;
235 dF(m, ld, blockIndex, m->basicblockindex[ip->op1]);
239 dF(m, ld, blockIndex, ld->c_last_jump+1);
243 dF(m, ld, blockIndex, blockIndex + 1);
249 for (ptr = ld->c_pre[blockIndex], cnt = 0; cnt < ld->c_numPre[blockIndex]; ++cnt, ++ptr)
255 if (cnt >= ld->c_numPre[blockIndex]) {
256 ld->c_pre[blockIndex][ld->c_numPre[blockIndex]] = from;
257 /* add predeccessors to list c_pre */
258 ld->c_numPre[blockIndex]++; /* increase number of predecessors */
265 a slightly modified version of dF(m, ld, int, int) that is used to traverse the part
266 of the control graph that is not reached by normal program flow but by the
267 raising of exceptions (code of catch blocks)
270 void dF_Exception(methodinfo *m, loopdata *ld, int from, int blockIndex)
274 int high, low, count;
275 struct depthElement *hp;
277 if (ld->c_exceptionVisit[blockIndex] < 0) /* has block been visited, return */
278 ld->c_exceptionVisit[blockIndex] = 1;
282 if (ld->c_dTable[blockIndex] != NULL) /* back to regular code section */
285 if (from >= 0) { /* build exception graph (in c_exceptionGraph) */
286 hp = DNEW(struct depthElement);
287 hp->next = ld->c_exceptionGraph[from];
288 hp->value = blockIndex;
291 ld->c_exceptionGraph[from] = hp;
295 if (blockIndex > m->basicblockcount) {
296 panic("DepthFirst: BlockIndex exceeded");
300 ip = m->basicblocks[blockIndex].iinstr + m->basicblocks[blockIndex].icount -1;
302 if (!m->basicblocks[blockIndex].icount)
303 dF_Exception(m, ld, blockIndex, blockIndex+1);
342 case ICMD_IF_ACMPNE: /* branch -> check next block */
343 dF_Exception(m, ld, blockIndex, blockIndex + 1);
347 dF_Exception(m, ld, blockIndex, m->basicblockindex[ip->op1]);
350 case ICMD_TABLESWITCH:
354 dF_Exception(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
361 count = (high-low+1);
363 while (--count >= 0) {
365 dF_Exception(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
369 case ICMD_LOOKUPSWITCH:
373 dF_Exception(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
378 while (--count >= 0) {
379 dF_Exception(m, ld, blockIndex, m->basicblockindex[s4ptr[1]]);
385 ld->c_last_jump = blockIndex;
386 dF_Exception(m, ld, blockIndex, m->basicblockindex[ip->op1]);
390 dF_Exception(m, ld, blockIndex, ld->c_last_jump+1);
394 dF_Exception(m, ld, blockIndex, blockIndex + 1);
403 Test function -> will be removed in final release
405 void resultPass1(methodinfo *m)
408 struct depthElement *hp;
410 printf("\n\n****** PASS 1 ******\n\n");
411 printf("Number of Nodes: %d\n\n", ld->c_globalCount);
413 printf("Predecessors:\n");
414 for (i=0; i<m->basicblockcount; ++i) {
415 printf("Block %d:\t", i);
416 for (j=0; j<ld->c_numPre[i]; ++j)
417 printf("%d ", ld->c_pre[i][j]);
423 for (i=0; i<m->basicblockcount; ++i) {
424 printf("Block %d:\t", i);
425 hp = ld->c_dTable[i];
428 printf("%d ", hp->value);
438 * These are local overrides for various environment variables in Emacs.
439 * Please do not remove this and leave it at the end of the file, where
440 * Emacs will automagically detect them.
441 * ---------------------------------------------------------------------
444 * indent-tabs-mode: t