-/* src/vm/cfg.c - build a control-flow graph
+/* src/vm/jit/cfg.c - build a control-flow graph
- Copyright (C) 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ Copyright (C) 2006, 2007 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,
J. Wenninger, Institut f. Computersprachen - TU Wien
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.
- Contact: cacao@cacaojvm.org
-
- Authors: Christian Thalinger
-
- Changes:
-
- $Id: cacao.c 4357 2006-01-22 23:33:38Z twisti $
-
*/
#include "config.h"
#include <assert.h>
-
-#include "vm/types.h"
+#include <stdint.h>
#include "mm/memory.h"
+
+#include "vm/global.h"
+
#include "vm/jit/jit.h"
+#include "vm/jit/stack.h"
/* cfg_allocate_predecessors ***************************************************
}
+/* cfg_insert_predecessor ******************************************************
+
+ Inserts a predecessor into the array, but checks for duplicate
+ entries. This is used for TABLESWITCH and LOOKUPSWITCH.
+
+*******************************************************************************/
+
+static void cfg_insert_predecessors(basicblock *bptr, basicblock *pbptr)
+{
+ basicblock **tbptr;
+ int i;
+
+ tbptr = bptr->predecessors;
+
+ /* check if the predecessors is already stored in the array */
+
+ for (i = 0; i < bptr->predecessorcount; i++, tbptr++)
+ if (*tbptr == pbptr)
+ return;
+
+ /* not found, insert it */
+
+ bptr->predecessors[bptr->predecessorcount] = pbptr;
+ bptr->predecessorcount++;
+}
+
+static void cfg_insert_successors(basicblock *bptr, basicblock *pbptr)
+{
+ basicblock **tbptr;
+ int i;
+
+ tbptr = bptr->successors;
+
+ /* check if the successor is already stored in the array */
+
+ for (i = 0; i < bptr->successorcount; i++, tbptr++)
+ if (*tbptr == pbptr)
+ return;
+
+ /* not found, insert it */
+
+ bptr->successors[bptr->successorcount] = pbptr;
+ bptr->successorcount++;
+}
+
+
/* cfg_build *******************************************************************
Build a control-flow graph in finding all predecessors and
bool cfg_build(jitdata *jd)
{
- methodinfo *m;
- basicblock *bptr;
- basicblock *tbptr;
- basicblock *ntbptr;
- instruction *iptr;
- s4 *s4ptr;
- s4 i;
- s4 n;
+ basicblock *bptr;
+ basicblock *tbptr;
+ basicblock *ntbptr;
+ instruction *iptr;
+ branch_target_t *table;
+ lookup_target_t *lookup;
+ int i;
+ bool has_fallthrough;
- /* get required compiler data */
+ /* process all basic blocks to find the predecessor/successor counts */
- m = jd->m;
+ bptr = jd->basicblocks;
- /* process all basic blocks to find the predecessor/successor counts */
+ for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
- bptr = m->basicblocks;
+ if (bptr->type == BBTYPE_EXH) {
+ /* predecessorcount for exception handlers is initialized to -1,
+ so we need to fix it to 0. */
+ bptr->predecessorcount += 1;
+ }
- for (i = 0; i < m->basicblockcount; i++, bptr++) {
- if (bptr->icount == 0)
+ if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
continue;
iptr = bptr->iinstr + bptr->icount - 1;
- switch (iptr->opc) {
- case ICMD_RET:
- case ICMD_RETURN:
- case ICMD_IRETURN:
- case ICMD_LRETURN:
- case ICMD_FRETURN:
- case ICMD_DRETURN:
- case ICMD_ARETURN:
- case ICMD_ATHROW:
+ /* skip NOPs at the end of the block */
+
+ while (iptr->opc == ICMD_NOP) {
+ if (iptr == bptr->iinstr)
+ break;
+ iptr--;
+ }
+
+ if (iptr->opc == ICMD_GOTO) {
+
+ /*
+ This is needed for the following special case caused by
+ stack_reach_next_block:
+ I.e. there might be instructions causing control flow before
+ a GOTO:
+
+ ....
+ 129: 192: IFEQ Ti102 0 (0x00000000) --> L052
+ 131: 193: NOP
+ 0: 0: GOTO --> L060
+ */
+
+ bptr->successorcount++;
+
+ tbptr = iptr->dst.block;
+ tbptr->predecessorcount++;
+
+ if (iptr == bptr->iinstr) {
+ continue;
+ }
+
+ iptr--;
+
+ while (iptr->opc == ICMD_NOP) {
+ if (iptr == bptr->iinstr) {
+ break;
+ }
+ iptr--;
+ }
+
+ has_fallthrough = false;
+ } else {
+ has_fallthrough = true;
+ }
+
+ switch (icmd_table[iptr->opc].controlflow) {
+
+ case CF_END:
break;
- case ICMD_IFEQ:
- case ICMD_IFNE:
- case ICMD_IFLT:
- case ICMD_IFGE:
- case ICMD_IFGT:
- case ICMD_IFLE:
-
- case ICMD_IFNULL:
- case ICMD_IFNONNULL:
-
- case ICMD_IF_ICMPEQ:
- case ICMD_IF_ICMPNE:
- case ICMD_IF_ICMPLT:
- case ICMD_IF_ICMPGE:
- case ICMD_IF_ICMPGT:
- case ICMD_IF_ICMPLE:
-
- case ICMD_IF_ACMPEQ:
- case ICMD_IF_ACMPNE:
+ case CF_IF:
+
bptr->successorcount += 2;
- tbptr = m->basicblocks + m->basicblockindex[iptr->op1];
- ntbptr = bptr->next;
+ tbptr = iptr->dst.block;
+ tbptr->predecessorcount++;
+
+ if (has_fallthrough) {
+ ntbptr = bptr->next;
+ ntbptr->predecessorcount++;
+ }
+ break;
+ case CF_JSR:
+ bptr->successorcount++;
+
+ tbptr = iptr->sx.s23.s3.jsrtarget.block;
tbptr->predecessorcount++;
- ntbptr->predecessorcount++;
break;
- case ICMD_GOTO:
+ case CF_GOTO:
+ case CF_RET:
bptr->successorcount++;
- tbptr = m->basicblocks + m->basicblockindex[iptr->op1];
+ tbptr = iptr->dst.block;
tbptr->predecessorcount++;
break;
- case ICMD_TABLESWITCH:
- s4ptr = iptr->val.a;
+ case CF_TABLE:
+ table = iptr->dst.table;
bptr->successorcount++;
- tbptr = m->basicblocks + m->basicblockindex[*s4ptr++];
+ tbptr = table->block;
tbptr->predecessorcount++;
+ table++;
- n = *s4ptr++; /* low */
- n = *s4ptr++ - n + 1; /* high */
+ i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
- while (--n >= 0) {
+ while (--i >= 0) {
bptr->successorcount++;
- tbptr = m->basicblocks + m->basicblockindex[*s4ptr++];
+ tbptr = table->block;
tbptr->predecessorcount++;
+ table++;
}
break;
- case ICMD_LOOKUPSWITCH:
- s4ptr = iptr->val.a;
+ case CF_LOOKUP:
+ lookup = iptr->dst.lookup;
bptr->successorcount++;
- tbptr = m->basicblocks + m->basicblockindex[*s4ptr++];
+ tbptr = iptr->sx.s23.s3.lookupdefault.block;
tbptr->predecessorcount++;
- n = *s4ptr++; /* count */
+ i = iptr->sx.s23.s2.lookupcount;
- while (--n >= 0) {
+ while (--i >= 0) {
bptr->successorcount++;
- tbptr = m->basicblocks + m->basicblockindex[s4ptr[1]];
+ tbptr = lookup->target.block;
tbptr->predecessorcount++;
-
- s4ptr += 2;
+ lookup++;
}
break;
default:
- bptr->successorcount++;
+ if (has_fallthrough) {
+ bptr->successorcount++;
- tbptr = bptr + 1;
- tbptr->predecessorcount++;
+ tbptr = bptr->next;
+
+ /* An exception handler has no predecessors. */
+
+ if (tbptr->type != BBTYPE_EXH)
+ tbptr->predecessorcount++;
+ }
break;
}
}
/* Second iteration to allocate the arrays and insert the basic
block pointers. */
- bptr = m->basicblocks;
+ bptr = jd->basicblocks;
- for (i = 0; i < m->basicblockcount; i++, bptr++) {
- if (bptr->icount == 0)
+ for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
+ if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
continue;
iptr = bptr->iinstr + bptr->icount - 1;
- switch (iptr->opc) {
- case ICMD_RET:
- case ICMD_RETURN:
- case ICMD_IRETURN:
- case ICMD_LRETURN:
- case ICMD_FRETURN:
- case ICMD_DRETURN:
- case ICMD_ARETURN:
- case ICMD_ATHROW:
+ /* skip NOPs at the end of the block */
+
+ while (iptr->opc == ICMD_NOP) {
+ if (iptr == bptr->iinstr)
+ break;
+ iptr--;
+ }
+
+ if (iptr->opc == ICMD_GOTO) {
+ tbptr = iptr->dst.block;
+
+ cfg_allocate_successors(bptr);
+
+ cfg_insert_successors(bptr, tbptr);
+
+ cfg_allocate_predecessors(tbptr);
+
+ cfg_insert_predecessors(tbptr, bptr);
+
+ if (iptr == bptr->iinstr) {
+ continue;
+ }
+
+ iptr--;
+
+ while (iptr->opc == ICMD_NOP) {
+ if (iptr == bptr->iinstr) {
+ break;
+ }
+ iptr--;
+ }
+
+ has_fallthrough = false;
+
+ } else {
+ has_fallthrough = true;
+ }
+
+ switch (icmd_table[iptr->opc].controlflow) {
+
+ case CF_END:
break;
- case ICMD_IFEQ:
- case ICMD_IFNE:
- case ICMD_IFLT:
- case ICMD_IFGE:
- case ICMD_IFGT:
- case ICMD_IFLE:
-
- case ICMD_IFNULL:
- case ICMD_IFNONNULL:
-
- case ICMD_IF_ICMPEQ:
- case ICMD_IF_ICMPNE:
- case ICMD_IF_ICMPLT:
- case ICMD_IF_ICMPGE:
- case ICMD_IF_ICMPGT:
- case ICMD_IF_ICMPLE:
-
- case ICMD_IF_ACMPEQ:
- case ICMD_IF_ACMPNE:
- tbptr = m->basicblocks + m->basicblockindex[iptr->op1];
+ case CF_IF:
+
+ tbptr = iptr->dst.block;
ntbptr = bptr->next;
cfg_allocate_successors(bptr);
- bptr->successors[0] = tbptr;
- bptr->successors[1] = ntbptr;
- bptr->successorcount += 2;
+ cfg_insert_successors(bptr, tbptr);
+ if (has_fallthrough) {
+ cfg_insert_successors(bptr, ntbptr);
+ }
cfg_allocate_predecessors(tbptr);
- cfg_allocate_predecessors(ntbptr);
-
- tbptr->predecessors[tbptr->predecessorcount] = bptr;
- tbptr->predecessorcount++;
+ if (has_fallthrough) {
+ cfg_allocate_predecessors(ntbptr);
+ }
- ntbptr->predecessors[ntbptr->predecessorcount] = bptr;
- ntbptr->predecessorcount++;
+ cfg_insert_predecessors(tbptr, bptr);
+ if (has_fallthrough) {
+ cfg_insert_predecessors(ntbptr, bptr);
+ }
break;
- case ICMD_GOTO:
- tbptr = m->basicblocks + m->basicblockindex[iptr->op1];
+ case CF_JSR:
+ tbptr = iptr->sx.s23.s3.jsrtarget.block;
+ goto goto_tail;
+ case CF_GOTO:
+ case CF_RET:
+
+ tbptr = iptr->dst.block;
+goto_tail:
cfg_allocate_successors(bptr);
- bptr->successors[0] = tbptr;
- bptr->successorcount++;
+ cfg_insert_successors(bptr, tbptr);
cfg_allocate_predecessors(tbptr);
- tbptr->predecessors[tbptr->predecessorcount] = bptr;
- tbptr->predecessorcount++;
+ cfg_insert_predecessors(tbptr, bptr);
break;
- case ICMD_TABLESWITCH:
- s4ptr = iptr->val.a;
+ case CF_TABLE:
+ table = iptr->dst.table;
- tbptr = m->basicblocks + m->basicblockindex[*s4ptr++];
+ tbptr = table->block;
+ table++;
cfg_allocate_successors(bptr);
- bptr->successors[0] = tbptr;
- bptr->successorcount++;
+ cfg_insert_successors(bptr, tbptr);
cfg_allocate_predecessors(tbptr);
- tbptr->predecessors[tbptr->predecessorcount] = bptr;
- tbptr->predecessorcount++;
+ cfg_insert_predecessors(tbptr, bptr);
- n = *s4ptr++; /* low */
- n = *s4ptr++ - n + 1; /* high */
+ i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
- while (--n >= 0) {
- tbptr = m->basicblocks + m->basicblockindex[*s4ptr++];
+ while (--i >= 0) {
+ tbptr = table->block;
+ table++;
- bptr->successors[bptr->successorcount] = tbptr;
- bptr->successorcount++;
+ cfg_insert_successors(bptr, tbptr);
cfg_allocate_predecessors(tbptr);
-
- tbptr->predecessors[tbptr->predecessorcount] = bptr;
- tbptr->predecessorcount++;
+ cfg_insert_predecessors(tbptr, bptr);
}
break;
- case ICMD_LOOKUPSWITCH:
- s4ptr = iptr->val.a;
+ case CF_LOOKUP:
+ lookup = iptr->dst.lookup;
- tbptr = m->basicblocks + m->basicblockindex[*s4ptr++];
+ tbptr = iptr->sx.s23.s3.lookupdefault.block;
cfg_allocate_successors(bptr);
- bptr->successors[0] = tbptr;
- bptr->successorcount++;
+ cfg_insert_successors(bptr, tbptr);
cfg_allocate_predecessors(tbptr);
- tbptr->predecessors[tbptr->predecessorcount] = bptr;
- tbptr->predecessorcount++;
+ cfg_insert_predecessors(tbptr, bptr);
- n = *s4ptr++; /* count */
+ i = iptr->sx.s23.s2.lookupcount;
- while (--n >= 0) {
- tbptr = m->basicblocks + m->basicblockindex[s4ptr[1]];
+ while (--i >= 0) {
+ tbptr = lookup->target.block;
+ lookup++;
- bptr->successors[bptr->successorcount] = tbptr;
- bptr->successorcount++;
+ cfg_insert_successors(bptr, tbptr);
cfg_allocate_predecessors(tbptr);
-
- tbptr->predecessors[tbptr->predecessorcount] = bptr;
- tbptr->predecessorcount++;
-
- s4ptr += 2;
+ cfg_insert_predecessors(tbptr, bptr);
}
break;
default:
- tbptr = bptr + 1;
+ if (has_fallthrough) {
+ tbptr = bptr->next;
- cfg_allocate_successors(bptr);
+ cfg_allocate_successors(bptr);
- bptr->successors[0] = tbptr;
- bptr->successorcount++;
+ bptr->successors[0] = tbptr;
+ bptr->successorcount++;
- cfg_allocate_predecessors(tbptr);
+ /* An exception handler has no predecessors. */
- tbptr->predecessors[tbptr->predecessorcount] = bptr;
- tbptr->predecessorcount++;
+ if (tbptr->type != BBTYPE_EXH) {
+ cfg_allocate_predecessors(tbptr);
+
+ tbptr->predecessors[tbptr->predecessorcount] = bptr;
+ tbptr->predecessorcount++;
+ }
+ }
break;
}
}
return true;
}
+/* cfg_add_root ****************************************************************
+
+ Adds an empty root basicblock.
+ The numbers of all other basicblocks are set off by one.
+ Needed for some analyses that require the root basicblock to have no
+ predecessors and to perform special initializations.
+
+*******************************************************************************/
+
+void cfg_add_root(jitdata *jd) {
+ basicblock *root, *zero, *it;
+
+ zero = jd->basicblocks;
+
+ root = DNEW(basicblock);
+ MZERO(root, basicblock, 1);
+
+ root->successorcount = 1;
+ root->successors = DMNEW(basicblock *, 1);
+ root->successors[0] = zero;
+ root->next = zero;
+ root->nr = 0;
+ root->type = BBTYPE_STD;
+
+ if (zero->predecessorcount == 0) {
+ zero->predecessors = DNEW(basicblock *);
+ } else {
+ zero->predecessors = DMREALLOC(zero->predecessors, basicblock *, zero->predecessorcount, zero->predecessorcount + 1);
+ }
+ zero->predecessors[zero->predecessorcount] = root;
+ zero->predecessorcount += 1;
+
+ jd->basicblocks = root;
+ jd->basicblockcount += 1;
+
+ for (it = zero; it; it = it->next) {
+ it->nr += 1;
+ }
+}
+
+#if defined(ENABLE_SSA)
+
+/* cfg_add_exceptional_edges ***************************************************
+
+ Edges from basicblocks to their exception handlers and from exception
+ handlers to the blocks they handle exceptions for are added. Further
+ the number of potentially throwing instructions in the basicblocks are
+ counted.
+
+ We don't consider nor do we determine the types of exceptions thrown. Edges
+ are added from every block to every potential handler.
+
+*******************************************************************************/
+
+void cfg_add_exceptional_edges(jitdata *jd) {
+ basicblock *bptr;
+ instruction *iptr;
+ exception_entry *ee;
+
+ /* Count the number of exceptional exits for every block.
+ * Every PEI is an exceptional out.
+ */
+
+ FOR_EACH_BASICBLOCK(jd, bptr) {
+
+ if (bptr->flags == BBUNDEF) {
+ continue;
+ }
+
+ FOR_EACH_INSTRUCTION(bptr, iptr) {
+ if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
+ bptr->exouts += 1;
+ }
+ }
+ }
+
+ /* Count the number of exception handlers for every block. */
+
+ for (ee = jd->exceptiontable; ee; ee = ee->down) {
+ for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
+ /* Linking a block with a handler, even if there are no exceptional exits
+ breaks stuff in other passes. */
+ if (bptr->exouts > 0) {
+ bptr->exhandlercount += 1;
+ ee->handler->expredecessorcount += 1;
+ }
+ }
+ }
+
+ /* Allocate and fill exception handler arrays. */
+
+ for (ee = jd->exceptiontable; ee; ee = ee->down) {
+ for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
+ if (bptr->exouts > 0) {
+
+ if (bptr->exhandlers == NULL) {
+ bptr->exhandlers = DMNEW(basicblock *, bptr->exhandlercount);
+ /* Move pointer past the end of the array,
+ * It will be filled in the reverse order.
+ */
+ bptr->exhandlers += bptr->exhandlercount;
+ }
+
+ bptr->exhandlers -= 1;
+ *(bptr->exhandlers) = ee->handler;
+
+ if (ee->handler->expredecessors == NULL) {
+ ee->handler->expredecessors = DMNEW(basicblock *, ee->handler->expredecessorcount);
+ ee->handler->expredecessors += ee->handler->expredecessorcount;
+ }
+
+ ee->handler->expredecessors -= 1;
+ *(ee->handler->expredecessors) = bptr;
+ }
+ }
+ }
+}
+
+#endif
/*
* These are local overrides for various environment variables in Emacs.
projects / cacao.git / blobdiff