#include "vm/global.h"
-#include "vm/jit/jit.h"
+#include "vm/jit/jit.hpp"
#include "vm/jit/stack.h"
branch_target_t *table;
lookup_target_t *lookup;
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--;
}
+ 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:
bptr->successorcount += 2;
tbptr = iptr->dst.block;
- ntbptr = bptr->next;
-
tbptr->predecessorcount++;
- ntbptr->predecessorcount++;
+
+ if (has_fallthrough) {
+ ntbptr = bptr->next;
+ ntbptr->predecessorcount++;
+ }
break;
case CF_JSR:
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--;
}
+ 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:
cfg_allocate_successors(bptr);
cfg_insert_successors(bptr, tbptr);
- cfg_insert_successors(bptr, ntbptr);
+ if (has_fallthrough) {
+ cfg_insert_successors(bptr, ntbptr);
+ }
cfg_allocate_predecessors(tbptr);
- cfg_allocate_predecessors(ntbptr);
+ if (has_fallthrough) {
+ cfg_allocate_predecessors(ntbptr);
+ }
cfg_insert_predecessors(tbptr, bptr);
- cfg_insert_predecessors(ntbptr, bptr);
+ if (has_fallthrough) {
+ cfg_insert_predecessors(ntbptr, bptr);
+ }
break;
case CF_JSR:
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;
}
root->next = zero;
root->nr = 0;
root->type = BBTYPE_STD;
+ root->method = jd->m;
if (zero->predecessorcount == 0) {
zero->predecessors = DNEW(basicblock *);
}
}
+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.
* Please do not remove this and leave it at the end of the file, where
projects / cacao.git / blobdiff