-/* 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: Edwin Steiner
-
*/
#include "config.h"
#include <assert.h>
-
-#include "vm/types.h"
+#include <stdint.h>
#include "mm/memory.h"
-#include "vm/jit/jit.h"
+
+#include "vm/global.h"
+
+#include "vm/jit/jit.hpp"
#include "vm/jit/stack.h"
static void cfg_insert_predecessors(basicblock *bptr, basicblock *pbptr)
{
basicblock **tbptr;
- s4 i;
+ int i;
tbptr = bptr->predecessors;
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 *******************************************************************
instruction *iptr;
branch_target_t *table;
lookup_target_t *lookup;
- s4 i;
+ int i;
+ bool has_fallthrough;
/* process all basic blocks to find the predecessor/successor counts */
bptr = jd->basicblocks;
for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
+
+ if (bptr->type == BBTYPE_EXH) {
+ /* predecessorcount for exception handlers is initialized to -1,
+ so we need to fix it to 0. */
+ bptr->predecessorcount += 1;
+ }
+
if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
continue;
iptr--;
}
- switch (iptr->opc) {
- case ICMD_RETURN:
- case ICMD_IRETURN:
- case ICMD_LRETURN:
- case ICMD_FRETURN:
- case ICMD_DRETURN:
- case ICMD_ARETURN:
- case ICMD_ATHROW:
+ 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 = iptr->dst.block;
- ntbptr = bptr->next;
-
tbptr->predecessorcount++;
- ntbptr->predecessorcount++;
+
+ if (has_fallthrough) {
+ ntbptr = bptr->next;
+ ntbptr->predecessorcount++;
+ }
break;
- case ICMD_JSR:
+ case CF_JSR:
bptr->successorcount++;
tbptr = iptr->sx.s23.s3.jsrtarget.block;
tbptr->predecessorcount++;
break;
- case ICMD_GOTO:
- case ICMD_RET:
+ case CF_GOTO:
+ case CF_RET:
bptr->successorcount++;
tbptr = iptr->dst.block;
tbptr->predecessorcount++;
break;
- case ICMD_TABLESWITCH:
+ case CF_TABLE:
table = iptr->dst.table;
bptr->successorcount++;
}
break;
- case ICMD_LOOKUPSWITCH:
+ case CF_LOOKUP:
lookup = iptr->dst.lookup;
bptr->successorcount++;
break;
default:
- bptr->successorcount++;
+ if (has_fallthrough) {
+ bptr->successorcount++;
- tbptr = bptr->next;
+ tbptr = bptr->next;
- /* An exception handler has no predecessors. */
+ /* An exception handler has no predecessors. */
- if (tbptr->type != BBTYPE_EXH)
- tbptr->predecessorcount++;
+ if (tbptr->type != BBTYPE_EXH)
+ tbptr->predecessorcount++;
+ }
break;
}
}
iptr--;
}
- switch (iptr->opc) {
- case ICMD_RETURN:
- case ICMD_IRETURN:
- case ICMD_LRETURN:
- case ICMD_FRETURN:
- case ICMD_DRETURN:
- case ICMD_ARETURN:
- case ICMD_ATHROW:
+ 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:
+ 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_JSR:
+ case CF_JSR:
tbptr = iptr->sx.s23.s3.jsrtarget.block;
goto goto_tail;
- case ICMD_GOTO:
- case ICMD_RET:
+ 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:
+ case CF_TABLE:
table = iptr->dst.table;
tbptr = table->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);
i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
tbptr = table->block;
table++;
- bptr->successors[bptr->successorcount] = tbptr;
- bptr->successorcount++;
+ cfg_insert_successors(bptr, tbptr);
cfg_allocate_predecessors(tbptr);
cfg_insert_predecessors(tbptr, bptr);
}
break;
- case ICMD_LOOKUPSWITCH:
+ case CF_LOOKUP:
lookup = iptr->dst.lookup;
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);
i = iptr->sx.s23.s2.lookupcount;
tbptr = lookup->target.block;
lookup++;
- bptr->successors[bptr->successorcount] = tbptr;
- bptr->successorcount++;
+ cfg_insert_successors(bptr, tbptr);
cfg_allocate_predecessors(tbptr);
cfg_insert_predecessors(tbptr, bptr);
break;
default:
- tbptr = bptr->next;
+ 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++;
- /* An exception handler has no predecessors. */
+ /* An exception handler has no predecessors. */
- if (tbptr->type != BBTYPE_EXH) {
- cfg_allocate_predecessors(tbptr);
+ if (tbptr->type != BBTYPE_EXH) {
+ cfg_allocate_predecessors(tbptr);
- tbptr->predecessors[tbptr->predecessorcount] = bptr;
- tbptr->predecessorcount++;
+ 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;
+ root->method = jd->m;
+
+ 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;
+ }
+}
+
+void cfg_remove_root(jitdata *jd) {
+ basicblock *root, *zero, *it;
+
+ root = jd->basicblocks;
+ zero = root->next;
+
+ zero->predecessorcount -= 1;
+
+ jd->basicblocks = zero;
+
+ for (it = zero; it; it = it->next) {
+ it->nr -= 1;
+ }
+}
+
+#if defined(ENABLE_SSA)
+
+static void cfg_eliminate_edges_to_unreachable(jitdata *jd);
+
+/* 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;
+ bool unreachable_exh = false;
+
+ /* Count the number of exceptional exits for every block.
+ * Every PEI is an exceptional out.
+ */
+
+ FOR_EACH_BASICBLOCK(jd, bptr) {
+
+ /* Prepare for reachability calculation. */
+ bptr->vp = NULL;
+
+ 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) {
+
+ if (ee->handler->expredecessorcount == 0) {
+ /* An exception handler that is unreachable.
+ This is inconsistent with the semantics of the CFG,
+ we need to recalculate reachability. */
+ unreachable_exh = true;
+ }
+
+ 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;
+ }
+ }
+ }
+
+ if (unreachable_exh) {
+
+ /* This is rare in ``normal'' compiler generated code.
+
+ The dead block [EXH] is a predecessor of [BB1],
+ but the edge [EXH] -> [BB1] will never be traversed.
+
+ [BB1] --[next]--> [BB2, no peis] ==[exhandler]==> [EXH] --[next]--+
+ ^ |
+ +---------------------------------------------------------------+
+ */
+
+ /*
+ fprintf(stderr, "Found unreachable exh, adjusting %s %s",
+ jd->m->klazz->name->text, jd->m->name->text);
+ fprintf(stderr, "<before>\n");
+ show_method(jd, 3);
+ fprintf(stderr, "</before>\n");
+ */
+
+ cfg_eliminate_edges_to_unreachable(jd);
+
+ /*
+ fprintf(stderr, "<after>\n");
+ show_method(jd, 3);
+ fprintf(stderr, "</after>\n");
+ */
+ }
+}
+
+static void cfg_calculate_reachability(basicblock *bptr) {
+ basicblock **itsucc;
+
+ /* Block not marked. */
+ assert(bptr->vp == NULL);
+
+ bptr->vp = bptr; /* Mark block */
+
+ FOR_EACH_SUCCESSOR(bptr, itsucc) {
+ if ((*itsucc)->vp == NULL) {
+ cfg_calculate_reachability(*itsucc);
+ }
+ }
+
+ if (bptr->exouts > 0) {
+ FOR_EACH_EXHANDLER(bptr, itsucc) {
+ if ((*itsucc)->vp == NULL) {
+ cfg_calculate_reachability(*itsucc);
+ }
+ }
+ }
+}
+
+static void cfg_remove_predecessors(basicblock *bptr, basicblock *pbptr) {
+ s4 i;
+
+ for (i = 0; i < bptr->predecessorcount; ++i) {
+ /* Search item. */
+ if (bptr->predecessors[i] == pbptr) {
+ if (i != (bptr->predecessorcount - 1)) {
+ /* If not last element, replace element with last element. */
+ bptr->predecessors[i] = bptr->predecessors[bptr->predecessorcount - 1];
+ }
+
+ /* Decrease element count. */
+ bptr->predecessorcount -= 1;
+
+ return;
+ }
+ }
+}
+
+static void cfg_eliminate_edges_to_unreachable(jitdata *jd) {
+ basicblock *it;
+ basicblock **itsucc;
+
+ cfg_calculate_reachability(jd->basicblocks);
+
+ FOR_EACH_BASICBLOCK(jd, it) {
+ if (it->vp == NULL) {
+
+ /* Mark as unreachable. */
+
+ it->flags = BBUNDEF;
+
+ /* As this block got unreachable, it is no more a predecessor
+ of its successors. */
+
+ FOR_EACH_SUCCESSOR(it, itsucc) {
+ cfg_remove_predecessors(*itsucc, it);
+ }
+
+ /* Eliminiate all CFG edges of this block. */
+
+ it->predecessorcount = 0;
+ it->successorcount = 0;
+ it->expredecessorcount = 0;
+ }
+ }
+}
+
+
+#endif
/*
* These are local overrides for various environment variables in Emacs.
projects / cacao.git / blobdiff