-/* jit/loop/graph.c - control flow graph
+/* vm/jit/loop/graph.c - control flow graph
- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
- R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser,
- M. Probst, S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck,
- P. Tomsich, J. Wenninger
+ Copyright (C) 1996-2005 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
+ C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
+ Institut f. Computersprachen - TU Wien
This file is part of CACAO.
Contains the functions which build a list, that represents the
control flow graph of the procedure, that is being analyzed.
- $Id: graph.c 557 2003-11-02 22:51:59Z twisti $
+ $Id: graph.c 1735 2004-12-07 14:33:27Z twisti $
*/
-#include <stdio.h>
-#include "graph.h"
-#include "loop.h"
-#include "jit.h"
-#include "toolbox/memory.h"
+#include "mm/memory.h"
+#include "vm/jit/jit.h"
+#include "vm/jit/loop/graph.h"
+#include "vm/jit/loop/loop.h"
-void LoopContainerInit(struct LoopContainer *lc, int i)
+void LoopContainerInit(methodinfo *m, struct LoopContainer *lc, int i)
{
struct LoopElement *le = DMNEW(struct LoopElement, 1);
lc->in_degree = 0;
le->node = lc->loop_head = i;
- le->block = &block[i];
+ le->block = &m->basicblocks[i];
- /* lc->nodes = (int *) malloc(sizeof(int)*block_count);
+ /* lc->nodes = (int *) malloc(sizeof(int)*m->basicblockcount);
lc->nodes[0] = i; */
lc->nodes = le;
depthFirst() builds the control flow graph out of the intermediate code of
the procedure, that is to be optimized and stores the list in the global
variable c_dTable
-*/
-void depthFirst()
+*/
+
+void depthFirst(methodinfo *m, loopdata *ld)
{
int i;
-/* allocate memory and init gobal variables needed by function dF(int, int) */
+/* allocate memory and init gobal variables needed by function dF(m, int, int) */
- if ((c_defnum = (int *) malloc(block_count * sizeof(int))) == NULL)
- c_mem_error();
- if ((c_numPre = (int *) malloc(block_count * sizeof(int))) == NULL)
- c_mem_error();
- if ((c_parent = (int *) malloc(block_count * sizeof(int))) == NULL)
- c_mem_error();
- if ((c_reverse = (int *) malloc(block_count * sizeof(int))) == NULL)
- c_mem_error();
-
- if ((c_pre = (int **) malloc(block_count * sizeof(int *))) == NULL)
- c_mem_error();
-
- if ((c_dTable = (struct depthElement **) malloc(block_count * sizeof(struct depthElement *))) == NULL)
- c_mem_error();
+ ld->c_defnum = DMNEW(int, m->basicblockcount);
+ ld->c_numPre = DMNEW(int, m->basicblockcount);
+ ld->c_parent = DMNEW(int, m->basicblockcount);
+ ld->c_reverse = DMNEW(int, m->basicblockcount);
+ ld->c_pre = DMNEW(int *, m->basicblockcount);
+ ld->c_dTable = DMNEW(struct depthElement *, m->basicblockcount);
- for (i = 0; i < block_count; ++i) {
- c_defnum[i] = c_parent[i] = -1;
- c_numPre[i] = c_reverse[i] = 0;
+ for (i = 0; i < m->basicblockcount; ++i) {
+ ld->c_defnum[i] = ld->c_parent[i] = -1;
+ ld->c_numPre[i] = ld->c_reverse[i] = 0;
- if ((c_pre[i] = (int *) malloc(block_count * sizeof(int))) == NULL)
- c_mem_error();
- c_dTable[i] = NULL;
- }
+ ld->c_pre[i] = DMNEW(int, m->basicblockcount);
+ ld->c_dTable[i] = NULL;
+ }
- c_globalCount = 0;
- c_allLoops = NULL;
+ ld->c_globalCount = 0;
+ ld->c_allLoops = NULL;
- dF(-1, 0); /* call helper function dF that traverses basic block structure */
+ dF(m, ld, -1, 0); /* call helper function dF that traverses basic block structure */
}
control flow graph in a depth-first order, thereby building up the adeacency
list c_dTable
*/
-void dF(int from, int blockIndex)
+
+void dF(methodinfo *m, loopdata *ld, int from, int blockIndex)
{
instruction *ip;
s4 *s4ptr;
if (from >= 0) {
/* the current basic block has a predecessor (ie. is not the first one) */
- if ((hp = (struct depthElement *) malloc(sizeof(struct depthElement))) == NULL)
- c_mem_error(); /* cretae new depth element */
+ hp = DNEW(struct depthElement);/* create new depth element */
- hp->next = c_dTable[from]; /* insert values */
+ hp->next = ld->c_dTable[from]; /* insert values */
hp->value = blockIndex;
hp->changes = NULL;
- c_dTable[from] = hp; /* insert into table */
- }
+ ld->c_dTable[from] = hp; /* insert into table */
+ }
if (from == blockIndex) { /* insert one node loops into loop container */
- if ((tmp = (struct LoopContainer *) malloc(sizeof(struct LoopContainer))) == NULL)
- c_mem_error();
- LoopContainerInit(tmp, blockIndex);
- tmp->next = c_allLoops;
- c_allLoops = tmp;
- }
+ tmp = DNEW(struct LoopContainer);
+ LoopContainerInit(m, tmp, blockIndex);
+ tmp->next = ld->c_allLoops;
+ ld->c_allLoops = tmp;
+ }
#ifdef C_DEBUG
- if (blockIndex > block_count) {
- fprintf(stderr, "DepthFirst: BlockIndex exceeded\n");
- exit(1);
- }
+ if (blockIndex > m->basicblockcount) {
+ panic("DepthFirst: BlockIndex exceeded\n");
+ }
#endif
- ip = block[blockIndex].iinstr + block[blockIndex].icount -1;
+ ip = m->basicblocks[blockIndex].iinstr + m->basicblocks[blockIndex].icount -1;
/* set ip to last instruction */
- if (c_defnum[blockIndex] == -1) { /* current block has not been visited */
- c_defnum[blockIndex] = c_globalCount; /* update global count */
- c_parent[blockIndex] = from; /* write parent block of current one */
- c_reverse[c_globalCount] = blockIndex;
- ++c_globalCount;
+ if (ld->c_defnum[blockIndex] == -1) { /* current block has not been visited */
+ ld->c_defnum[blockIndex] = ld->c_globalCount; /* update global count */
+ ld->c_parent[blockIndex] = from; /* write parent block of current one */
+ ld->c_reverse[ld->c_globalCount] = blockIndex;
+ ++ld->c_globalCount;
- if (!block[blockIndex].icount) {
+ if (!m->basicblocks[blockIndex].icount) {
/* block does not contain instructions */
- dF(blockIndex, blockIndex+1);
+ dF(m, ld, blockIndex, blockIndex+1);
}
else { /* for all successors, do */
switch (ip->opc) { /* check type of last instruction */
case ICMD_IF_ICMPGE:
case ICMD_IF_ICMPGT:
case ICMD_IF_ICMPLE:
+ case ICMD_IF_LEQ:
+ case ICMD_IF_LNE:
+ case ICMD_IF_LLT:
+ case ICMD_IF_LGE:
+ case ICMD_IF_LGT:
+ case ICMD_IF_LLE:
+ case ICMD_IF_LCMPEQ:
+ case ICMD_IF_LCMPNE:
+ case ICMD_IF_LCMPLT:
+ case ICMD_IF_LCMPGE:
+ case ICMD_IF_LCMPGT:
+ case ICMD_IF_LCMPLE:
case ICMD_IF_ACMPEQ:
case ICMD_IF_ACMPNE: /* branch -> check next block */
- dF(blockIndex, blockIndex + 1);
+ dF(m, ld, blockIndex, blockIndex + 1);
/* fall throu */
case ICMD_GOTO:
- dF(blockIndex, block_index[ip->op1]);
+ dF(m, ld, blockIndex, m->basicblockindex[ip->op1]);
break; /* visit branch (goto) target */
case ICMD_TABLESWITCH: /* switch statement */
s4ptr = ip->val.a;
- dF(blockIndex, block_index[*s4ptr]); /* default branch */
+ dF(m, ld, blockIndex, m->basicblockindex[*s4ptr]); /* default branch */
s4ptr++;
low = *s4ptr;
while (--count >= 0) {
s4ptr++;
- dF(blockIndex, block_index[*s4ptr]);
+ dF(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
}
break;
case ICMD_LOOKUPSWITCH: /* switch statement */
s4ptr = ip->val.a;
- dF(blockIndex, block_index[*s4ptr]); /* default branch */
+ dF(m, ld, blockIndex, m->basicblockindex[*s4ptr]); /* default branch */
++s4ptr;
count = *s4ptr++;
while (--count >= 0) {
- dF(blockIndex, block_index[s4ptr[1]]);
+ dF(m, ld, blockIndex, m->basicblockindex[s4ptr[1]]);
s4ptr += 2;
}
break;
case ICMD_JSR:
- c_last_jump = blockIndex;
- dF(blockIndex, block_index[ip->op1]);
+ ld->c_last_jump = blockIndex;
+ dF(m, ld, blockIndex, m->basicblockindex[ip->op1]);
break;
case ICMD_RET:
- dF(blockIndex, c_last_jump+1);
+ dF(m, ld, blockIndex, ld->c_last_jump+1);
break;
default:
- dF(blockIndex, blockIndex + 1);
+ dF(m, ld, blockIndex, blockIndex + 1);
break;
}
}
}
- for (ptr = c_pre[blockIndex], cnt = 0; cnt < c_numPre[blockIndex]; ++cnt, ++ptr)
+ for (ptr = ld->c_pre[blockIndex], cnt = 0; cnt < ld->c_numPre[blockIndex]; ++cnt, ++ptr)
{
if (*ptr == from)
break;
}
- if (cnt >= c_numPre[blockIndex]) {
- c_pre[blockIndex][c_numPre[blockIndex]] = from;
+ if (cnt >= ld->c_numPre[blockIndex]) {
+ ld->c_pre[blockIndex][ld->c_numPre[blockIndex]] = from;
/* add predeccessors to list c_pre */
- c_numPre[blockIndex]++; /* increase number of predecessors */
- }
+ ld->c_numPre[blockIndex]++; /* increase number of predecessors */
+ }
}
+
/*
- a slightly modified version of dF(int, int) that is used to traverse the part
+ a slightly modified version of dF(m, ld, int, int) that is used to traverse the part
of the control graph that is not reached by normal program flow but by the
raising of exceptions (code of catch blocks)
*/
-void dF_Exception(int from, int blockIndex)
+
+void dF_Exception(methodinfo *m, loopdata *ld, int from, int blockIndex)
{
instruction *ip;
s4 *s4ptr;
int high, low, count;
struct depthElement *hp;
- if (c_exceptionVisit[blockIndex] < 0) /* has block been visited, return */
- c_exceptionVisit[blockIndex] = 1;
+ if (ld->c_exceptionVisit[blockIndex] < 0) /* has block been visited, return */
+ ld->c_exceptionVisit[blockIndex] = 1;
else
return;
- if (c_dTable[blockIndex] != NULL) /* back to regular code section */
+ if (ld->c_dTable[blockIndex] != NULL) /* back to regular code section */
return;
if (from >= 0) { /* build exception graph (in c_exceptionGraph) */
- if ((hp = (struct depthElement *) malloc(sizeof(struct depthElement))) == NULL)
- c_mem_error();
-
- hp->next = c_exceptionGraph[from];
+ hp = DNEW(struct depthElement);
+ hp->next = ld->c_exceptionGraph[from];
hp->value = blockIndex;
hp->changes = NULL;
- c_exceptionGraph[from] = hp;
- }
+ ld->c_exceptionGraph[from] = hp;
+ }
#ifdef C_DEBUG
- if (blockIndex > block_count) {
- fprintf(stderr, "DepthFirst: BlockIndex exceeded\n");
- exit(1);
- }
+ if (blockIndex > m->basicblockcount) {
+ panic("DepthFirst: BlockIndex exceeded");
+ }
#endif
- ip = block[blockIndex].iinstr + block[blockIndex].icount -1;
+ ip = m->basicblocks[blockIndex].iinstr + m->basicblocks[blockIndex].icount -1;
- if (!block[blockIndex].icount)
- dF_Exception(blockIndex, blockIndex+1);
+ if (!m->basicblocks[blockIndex].icount)
+ dF_Exception(m, ld, blockIndex, blockIndex+1);
else {
switch (ip->opc) {
case ICMD_RETURN:
case ICMD_IF_ICMPGE:
case ICMD_IF_ICMPGT:
case ICMD_IF_ICMPLE:
+ case ICMD_IF_LEQ:
+ case ICMD_IF_LNE:
+ case ICMD_IF_LLT:
+ case ICMD_IF_LGE:
+ case ICMD_IF_LGT:
+ case ICMD_IF_LLE:
+ case ICMD_IF_LCMPEQ:
+ case ICMD_IF_LCMPNE:
+ case ICMD_IF_LCMPLT:
+ case ICMD_IF_LCMPGE:
+ case ICMD_IF_LCMPGT:
+ case ICMD_IF_LCMPLE:
case ICMD_IF_ACMPEQ:
- case ICMD_IF_ACMPNE:
- dF_Exception(blockIndex, blockIndex + 1);
+ case ICMD_IF_ACMPNE: /* branch -> check next block */
+ dF_Exception(m, ld, blockIndex, blockIndex + 1);
/* fall throu */
case ICMD_GOTO:
- dF_Exception(blockIndex, block_index[ip->op1]);
+ dF_Exception(m, ld, blockIndex, m->basicblockindex[ip->op1]);
break;
case ICMD_TABLESWITCH:
s4ptr = ip->val.a;
/* default branch */
- dF_Exception(blockIndex, block_index[*s4ptr]);
+ dF_Exception(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
s4ptr++;
low = *s4ptr;
while (--count >= 0) {
s4ptr++;
- dF_Exception(blockIndex, block_index[*s4ptr]);
+ dF_Exception(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
}
break;
s4ptr = ip->val.a;
/* default branch */
- dF_Exception(blockIndex, block_index[*s4ptr]);
+ dF_Exception(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
++s4ptr;
count = *s4ptr++;
while (--count >= 0) {
- dF_Exception(blockIndex, block_index[s4ptr[1]]);
+ dF_Exception(m, ld, blockIndex, m->basicblockindex[s4ptr[1]]);
s4ptr += 2;
}
break;
case ICMD_JSR:
- c_last_jump = blockIndex;
- dF_Exception(blockIndex, block_index[ip->op1]);
+ ld->c_last_jump = blockIndex;
+ dF_Exception(m, ld, blockIndex, m->basicblockindex[ip->op1]);
break;
case ICMD_RET:
- dF_Exception(blockIndex, c_last_jump+1);
+ dF_Exception(m, ld, blockIndex, ld->c_last_jump+1);
break;
default:
- dF_Exception(blockIndex, blockIndex + 1);
+ dF_Exception(m, ld, blockIndex, blockIndex + 1);
break;
}
}
}
+#if 0
/*
Test function -> will be removed in final release
*/
-void resultPass1()
+void resultPass1(methodinfo *m)
{
int i, j;
struct depthElement *hp;
-
+
printf("\n\n****** PASS 1 ******\n\n");
- printf("Number of Nodes: %d\n\n", c_globalCount);
+ printf("Number of Nodes: %d\n\n", ld->c_globalCount);
printf("Predecessors:\n");
- for (i=0; i<block_count; ++i) {
+ for (i=0; i<m->basicblockcount; ++i) {
printf("Block %d:\t", i);
- for (j=0; j<c_numPre[i]; ++j)
- printf("%d ", c_pre[i][j]);
+ for (j=0; j<ld->c_numPre[i]; ++j)
+ printf("%d ", ld->c_pre[i][j]);
printf("\n");
}
printf("\n");
printf("Graph:\n");
- for (i=0; i<block_count; ++i) {
+ for (i=0; i<m->basicblockcount; ++i) {
printf("Block %d:\t", i);
- hp = c_dTable[i];
+ hp = ld->c_dTable[i];
while (hp != NULL) {
printf("%d ", hp->value);
}
printf("\n");
}
+#endif
/*
* These are local overrides for various environment variables in Emacs.
projects / cacao.git / blobdiff