1 /* graph.c *********************************************************************
3 Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
5 See file COPYRIGHT for information on usage and disclaimer of warranties.
7 Contains the functions which build a list, that represents the control
8 flow graph of the procedure, that is being analyzed.
10 Authors: Christopher Kruegel EMAIL: cacao@complang.tuwien.ac.at
12 Last Change: 1998/17/02
14 *******************************************************************************/
16 void dF(int from, int blockIndex);
18 void LoopContainerInit(struct LoopContainer *lc, int i)
20 struct LoopElement *le = DMNEW(struct LoopElement, 1);
26 lc->tree_right = NULL;
29 lc->exceptions = NULL;
32 le->node = lc->loop_head = i;
33 le->block = &block[i];
35 /* lc->nodes = (int *) malloc(sizeof(int)*block_count);
41 /* depthFirst() builds the control flow graph out of the intermediate code of
42 the procedure, that is to be optimized and stores the list in the global
48 struct depthElement *hp;
50 /* allocate memory and init gobal variables needed by function dF(int, int) */
52 if ((c_defnum = (int *) malloc(block_count * sizeof(int))) == NULL)
54 if ((c_numPre = (int *) malloc(block_count * sizeof(int))) == NULL)
56 if ((c_parent = (int *) malloc(block_count * sizeof(int))) == NULL)
58 if ((c_reverse = (int *) malloc(block_count * sizeof(int))) == NULL)
61 if ((c_pre = (int **) malloc(block_count * sizeof(int *))) == NULL)
64 if ((c_dTable = (struct depthElement **) malloc(block_count * sizeof(struct depthElement *))) == NULL)
67 for (i = 0; i < block_count; ++i) {
68 c_defnum[i] = c_parent[i] = -1;
69 c_numPre[i] = c_reverse[i] = 0;
71 if ((c_pre[i] = (int *) malloc(block_count * sizeof(int))) == NULL)
79 dF(-1, 0); /* call helper function dF that traverses basic block structure */
82 /* dF starts from the first block of the given procedure and traverses the
83 control flow graph in a depth-first order, thereby building up the adeacency
86 void dF(int from, int blockIndex)
91 struct depthElement *hp;
92 struct LoopContainer *tmp;
96 /* the current basic block has a predecessor (ie. is not the first one) */
97 if ((hp = (struct depthElement *) malloc(sizeof(struct depthElement))) == NULL)
98 c_mem_error(); /* cretae new depth element */
100 hp->next = c_dTable[from]; /* insert values */
101 hp->value = blockIndex;
104 c_dTable[from] = hp; /* insert into table */
107 if (from == blockIndex) { /* insert one node loops into loop container */
108 if ((tmp = (struct LoopContainer *) malloc(sizeof(struct LoopContainer))) == NULL)
110 LoopContainerInit(tmp, blockIndex);
111 tmp->next = c_allLoops;
116 if (blockIndex > block_count) {
117 fprintf(stderr, "DepthFirst: BlockIndex exceeded\n");
122 ip = block[blockIndex].iinstr + block[blockIndex].icount -1;
123 /* set ip to last instruction */
125 if (c_defnum[blockIndex] == -1) { /* current block has not been visited */
126 c_defnum[blockIndex] = c_globalCount; /* update global count */
127 c_parent[blockIndex] = from; /* write parent block of current one */
128 c_reverse[c_globalCount] = blockIndex;
131 if (!block[blockIndex].icount) {
132 /* block does not contain instructions */
133 dF(blockIndex, blockIndex+1);
135 else { /* for all successors, do */
136 switch (ip->opc) { /* check type of last instruction */
144 break; /* function returns -> end of graph */
161 case ICMD_IF_ACMPNE: /* branch -> check next block */
162 dF(blockIndex, blockIndex + 1);
166 dF(blockIndex, block_index[ip->op1]);
167 break; /* visit branch (goto) target */
169 case ICMD_TABLESWITCH: /* switch statement */
172 dF(blockIndex, block_index[*s4ptr]); /* default branch */
179 count = (high-low+1);
181 while (--count >= 0) {
183 dF(blockIndex, block_index[*s4ptr]);
187 case ICMD_LOOKUPSWITCH: /* switch statement */
190 dF(blockIndex, block_index[*s4ptr]); /* default branch */
195 while (--count >= 0) {
196 dF(blockIndex, block_index[s4ptr[1]]);
202 c_last_jump = blockIndex;
203 dF(blockIndex, block_index[ip->op1]);
207 dF(blockIndex, c_last_jump+1);
211 dF(blockIndex, blockIndex + 1);
217 for (ptr = c_pre[blockIndex], cnt = 0; cnt < c_numPre[blockIndex]; ++cnt, ++ptr)
223 if (cnt >= c_numPre[blockIndex]) {
224 c_pre[blockIndex][c_numPre[blockIndex]] = from;
225 /* add predeccessors to list c_pre */
226 c_numPre[blockIndex]++; /* increase number of predecessors */
231 /* a slightly modified version of dF(int, int) that is used to traverse the part
232 of the control graph that is not reached by normal program flow but by the
233 raising of exceptions (code of catch blocks)
235 void dF_Exception(int from, int blockIndex)
239 int high, low, count;
240 struct depthElement *hp;
241 struct LoopContainer *tmp;
243 if (c_exceptionVisit[blockIndex] < 0) /* has block been visited, return */
244 c_exceptionVisit[blockIndex] = 1;
248 if (c_dTable[blockIndex] != NULL) /* back to regular code section */
251 if (from >= 0) { /* build exception graph (in c_exceptionGraph) */
252 if ((hp = (struct depthElement *) malloc(sizeof(struct depthElement))) == NULL)
255 hp->next = c_exceptionGraph[from];
256 hp->value = blockIndex;
259 c_exceptionGraph[from] = hp;
263 if (blockIndex > block_count) {
264 fprintf(stderr, "DepthFirst: BlockIndex exceeded\n");
269 ip = block[blockIndex].iinstr + block[blockIndex].icount -1;
271 if (!block[blockIndex].icount)
272 dF_Exception(blockIndex, blockIndex+1);
300 dF_Exception(blockIndex, blockIndex + 1);
304 dF_Exception(blockIndex, block_index[ip->op1]);
307 case ICMD_TABLESWITCH:
311 dF_Exception(blockIndex, block_index[*s4ptr]);
318 count = (high-low+1);
320 while (--count >= 0) {
322 dF_Exception(blockIndex, block_index[*s4ptr]);
326 case ICMD_LOOKUPSWITCH:
330 dF_Exception(blockIndex, block_index[*s4ptr]);
335 while (--count >= 0) {
336 dF_Exception(blockIndex, block_index[s4ptr[1]]);
342 c_last_jump = blockIndex;
343 dF_Exception(blockIndex, block_index[ip->op1]);
347 dF_Exception(blockIndex, c_last_jump+1);
351 dF_Exception(blockIndex, blockIndex + 1);
357 /* Test function -> will be removed in final release
362 struct depthElement *hp;
364 printf("\n\n****** PASS 1 ******\n\n");
365 printf("Number of Nodes: %d\n\n", c_globalCount);
367 printf("Predecessors:\n");
368 for (i=0; i<block_count; ++i) {
369 printf("Block %d:\t", i);
370 for (j=0; j<c_numPre[i]; ++j)
371 printf("%d ", c_pre[i][j]);
377 for (i=0; i<block_count; ++i) {
378 printf("Block %d:\t", i);
382 printf("%d ", hp->value);
391 * These are local overrides for various environment variables in Emacs.
392 * Please do not remove this and leave it at the end of the file, where
393 * Emacs will automagically detect them.
394 * ---------------------------------------------------------------------
397 * indent-tabs-mode: t