Authors: Christian Thalinger
- Changes:
-
- $Id: cacao.c 4357 2006-01-22 23:33:38Z twisti $
+ Changes: Edwin Steiner
*/
#include "mm/memory.h"
#include "vm/jit/jit.h"
+#include "vm/jit/stack.h"
+
+
+/* cfg_allocate_predecessors ***************************************************
+
+ Allocates the predecessor array, if there is none, and resets the
+ predecessor count.
+
+*******************************************************************************/
+
+static void cfg_allocate_predecessors(basicblock *bptr)
+{
+ if (bptr->predecessors == NULL) {
+ bptr->predecessors = DMNEW(basicblock*, bptr->predecessorcount);
+
+ bptr->predecessorcount = 0;
+ }
+}
+
+
+/* cfg_allocate_successors *****************************************************
+
+ Allocates the succecessor array, if there is none, and resets the
+ predecessor count.
+
+*******************************************************************************/
+
+static void cfg_allocate_successors(basicblock *bptr)
+{
+ if (bptr->successors == NULL) {
+ bptr->successors = DMNEW(basicblock*, bptr->successorcount);
+
+ bptr->successorcount = 0;
+ }
+}
+
+
+/* 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;
+ s4 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++;
+}
/* cfg_build *******************************************************************
bool cfg_build(jitdata *jd)
{
- methodinfo *m;
- basicblock *bptr;
- basicblock *tbptr;
- basicblock *ntbptr;
- instruction *iptr;
- s4 *s4ptr;
- s4 i;
-
- /* get required compiler data */
-
- m = jd->m;
+ basicblock *bptr;
+ basicblock *tbptr;
+ basicblock *ntbptr;
+ instruction *iptr;
+ branch_target_t *table;
+ lookup_target_t *lookup;
+ s4 i;
/* process all basic blocks to find the predecessor/successor counts */
- 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;
+ /* skip NOPs at the end of the block */
+
+ while (iptr->opc == ICMD_NOP) {
+ if (iptr == bptr->iinstr)
+ break;
+ iptr--;
+ }
+
switch (iptr->opc) {
- case ICMD_RET:
case ICMD_RETURN:
case ICMD_IRETURN:
case ICMD_LRETURN:
case ICMD_IF_ACMPNE:
bptr->successorcount += 2;
- tbptr = m->basicblocks + m->basicblockindex[iptr->op1];
+ tbptr = iptr->dst.block;
ntbptr = bptr->next;
tbptr->predecessorcount++;
ntbptr->predecessorcount++;
break;
+ case ICMD_JSR:
+ bptr->successorcount++;
+
+ tbptr = iptr->sx.s23.s3.jsrtarget.block;
+ tbptr->predecessorcount++;
+ break;
+
case ICMD_GOTO:
+ case ICMD_RET:
bptr->successorcount++;
- tbptr = m->basicblocks + m->basicblockindex[iptr->op1];
+ tbptr = iptr->dst.block;
tbptr->predecessorcount++;
break;
case ICMD_TABLESWITCH:
- s4ptr = iptr->val.a;
+ table = iptr->dst.table;
bptr->successorcount++;
- tbptr = m->basicblocks + m->basicblockindex[*s4ptr++];
+ tbptr = table->block;
tbptr->predecessorcount++;
+ table++;
- i = *s4ptr++; /* low */
- i = *s4ptr++ - i + 1; /* high */
+ i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
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;
+ lookup = iptr->dst.lookup;
bptr->successorcount++;
- tbptr = m->basicblocks + m->basicblockindex[*s4ptr++];
+ tbptr = iptr->sx.s23.s3.lookupdefault.block;
tbptr->predecessorcount++;
- i = *s4ptr++; /* count */
+ i = iptr->sx.s23.s2.lookupcount;
while (--i >= 0) {
bptr->successorcount++;
- bptr = m->basicblocks + m->basicblockindex[s4ptr[1]];
+ tbptr = lookup->target.block;
tbptr->predecessorcount++;
-
- s4ptr += 2;
+ lookup++;
}
break;
default:
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;
+ /* skip NOPs at the end of the block */
+
+ while (iptr->opc == ICMD_NOP) {
+ if (iptr == bptr->iinstr)
+ break;
+ iptr--;
+ }
+
switch (iptr->opc) {
- case ICMD_RET:
case ICMD_RETURN:
case ICMD_IRETURN:
case ICMD_LRETURN:
case ICMD_IF_ACMPEQ:
case ICMD_IF_ACMPNE:
- tbptr = m->basicblocks + m->basicblockindex[iptr->op1];
+ tbptr = iptr->dst.block;
ntbptr = bptr->next;
+ cfg_allocate_successors(bptr);
+
bptr->successors[0] = tbptr;
bptr->successors[1] = ntbptr;
+ bptr->successorcount += 2;
- if (tbptr->predecessors == NULL) {
- tbptr->predecessors =
- DMNEW(basicblock*, tbptr->predecessorcount);
-
- tbptr->predecessorcount = 0;
- }
-
- if (ntbptr == NULL) {
- ntbptr->predecessors =
- DMNEW(basicblock*, ntbptr->predecessorcount);
-
- ntbptr->predecessorcount = 0;
- }
+ cfg_allocate_predecessors(tbptr);
+ cfg_allocate_predecessors(ntbptr);
tbptr->predecessors[tbptr->predecessorcount] = bptr;
tbptr->predecessorcount++;
ntbptr->predecessorcount++;
break;
+ case ICMD_JSR:
+ tbptr = iptr->sx.s23.s3.jsrtarget.block;
+ goto goto_tail;
+
case ICMD_GOTO:
- tbptr = m->basicblocks + m->basicblockindex[iptr->op1];
+ case ICMD_RET:
+ tbptr = iptr->dst.block;
+goto_tail:
+ cfg_allocate_successors(bptr);
bptr->successors[0] = tbptr;
+ bptr->successorcount++;
- if (tbptr->predecessors == NULL) {
- tbptr->predecessors =
- DMNEW(basicblock*, tbptr->predecessorcount);
-
- tbptr->predecessorcount = 0;
- }
+ cfg_allocate_predecessors(tbptr);
tbptr->predecessors[tbptr->predecessorcount] = bptr;
tbptr->predecessorcount++;
break;
case ICMD_TABLESWITCH:
- s4ptr = iptr->val.a;
+ table = iptr->dst.table;
+ tbptr = table->block;
+ table++;
+
+ cfg_allocate_successors(bptr);
+
+ bptr->successors[0] = tbptr;
bptr->successorcount++;
- tbptr = m->basicblocks + m->basicblockindex[*s4ptr++];
+ cfg_allocate_predecessors(tbptr);
+
+ tbptr->predecessors[tbptr->predecessorcount] = bptr;
tbptr->predecessorcount++;
- i = *s4ptr++; /* low */
- i = *s4ptr++ - i + 1; /* high */
+ i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
while (--i >= 0) {
+ tbptr = table->block;
+ table++;
+
+ bptr->successors[bptr->successorcount] = tbptr;
bptr->successorcount++;
- tbptr = m->basicblocks + m->basicblockindex[*s4ptr++];
- tbptr->predecessorcount++;
+ cfg_allocate_predecessors(tbptr);
+ cfg_insert_predecessors(tbptr, bptr);
}
break;
case ICMD_LOOKUPSWITCH:
- s4ptr = iptr->val.a;
+ lookup = iptr->dst.lookup;
+
+ tbptr = iptr->sx.s23.s3.lookupdefault.block;
+
+ cfg_allocate_successors(bptr);
+ bptr->successors[0] = tbptr;
bptr->successorcount++;
- tbptr = m->basicblocks + m->basicblockindex[*s4ptr++];
+ cfg_allocate_predecessors(tbptr);
+
+ tbptr->predecessors[tbptr->predecessorcount] = bptr;
tbptr->predecessorcount++;
- i = *s4ptr++; /* count */
+ i = iptr->sx.s23.s2.lookupcount;
while (--i >= 0) {
- bptr->successorcount++;
+ tbptr = lookup->target.block;
+ lookup++;
- bptr = m->basicblocks + m->basicblockindex[s4ptr[1]];
- tbptr->predecessorcount++;
+ bptr->successors[bptr->successorcount] = tbptr;
+ bptr->successorcount++;
- s4ptr += 2;
+ cfg_allocate_predecessors(tbptr);
+ cfg_insert_predecessors(tbptr, bptr);
}
break;
default:
- tbptr = bptr + 1;
+ tbptr = bptr->next;
+
+ cfg_allocate_successors(bptr);
bptr->successors[0] = tbptr;
+ bptr->successorcount++;
- if (tbptr->predecessors == NULL) {
- tbptr->predecessors =
- DMNEW(basicblock*, tbptr->predecessorcount);
+ /* An exception handler has no predecessors. */
- tbptr->predecessorcount = 0;
- }
+ if (tbptr->type != BBTYPE_EXH) {
+ cfg_allocate_predecessors(tbptr);
- tbptr->predecessors[tbptr->predecessorcount] = bptr;
- tbptr->predecessorcount++;
+ tbptr->predecessors[tbptr->predecessorcount] = bptr;
+ tbptr->predecessorcount++;
+ }
break;
}
}