return (w->W_top == 0);
}
+/*******************************************************************************
+wl_reset
+
+Empties the worklist.
+
+IN: worklist *w pointer to worklist created with wl_new
+*******************************************************************************/
+void wl_reset(worklist *w, int size) {
+ w->W_top = 0;
+ bv_reset(w->W_bv, size);
+}
/*
* These are local overrides for various environment variables in Emacs.
void wl_add(worklist *w, int element);
int wl_get(worklist *w);
bool wl_is_empty(worklist *w);
+void wl_reset(worklist *w, int size);
#endif /* _BITVECTOR_H */
memory. All functions writing values into the data area return the offset
relative the begin of the code area (start of procedure).
- $Id: codegen-common.c 7864 2007-05-03 21:17:26Z twisti $
+ $Id: codegen-common.c 7908 2007-05-15 09:55:17Z christian $
*/
#include "vm/jit/jit.h"
#include "vm/jit/md.h"
#include "vm/jit/replace.h"
+#if defined(ENABLE_SSA)
+# include "vm/jit/optimizing/lsra.h"
+# include "vm/jit/optimizing/ssa.h"
+#endif
#include "vm/jit/stacktrace.h"
#if defined(ENABLE_INTRP)
}
+/* codegen_emit_phi_moves ****************************************************
+
+ Emits phi moves at the end of the basicblock.
+
+*******************************************************************************/
+
+#if defined(ENABLE_SSA)
+void codegen_emit_phi_moves(jitdata *jd, basicblock *bptr)
+{
+ int lt_d,lt_s,i;
+ lsradata *ls;
+ codegendata *cd;
+ varinfo *s, *d;
+ instruction tmp_i;
+
+ cd = jd->cd;
+ ls = jd->ls;
+
+ MCODECHECK(512);
+
+ /* Moves from phi functions with highest indices have to be */
+ /* inserted first, since this is the order as is used for */
+ /* conflict resolution */
+
+ for(i = ls->num_phi_moves[bptr->nr] - 1; i >= 0 ; i--) {
+ lt_d = ls->phi_moves[bptr->nr][i][0];
+ lt_s = ls->phi_moves[bptr->nr][i][1];
+#if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf("BB %3i Move %3i <- %3i ", bptr->nr, lt_d, lt_s);
+#endif
+ if (lt_s == UNUSED) {
+#if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf(" ... not processed \n");
+#endif
+ continue;
+ }
+
+ d = VAR(ls->lifetime[lt_d].v_index);
+ s = VAR(ls->lifetime[lt_s].v_index);
+
+
+ if (d->type == -1) {
+#if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf("...returning - phi lifetimes where joined\n");
+#endif
+ return;
+ }
+
+ if (s->type == -1) {
+#if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf("...returning - phi lifetimes where joined\n");
+#endif
+ return;
+ }
+
+ tmp_i.opc = 0;
+ tmp_i.s1.varindex = ls->lifetime[lt_s].v_index;
+ tmp_i.dst.varindex = ls->lifetime[lt_d].v_index;
+ emit_copy(jd, &tmp_i);
+
+#if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose) {
+ if (IS_INMEMORY(d->flags) && IS_INMEMORY(s->flags)) {
+ /* mem -> mem */
+ printf("M%3i <- M%3i",d->vv.regoff,s->vv.regoff);
+ }
+ else if (IS_INMEMORY(s->flags)) {
+ /* mem -> reg */
+ printf("R%3i <- M%3i",d->vv.regoff,s->vv.regoff);
+ }
+ else if (IS_INMEMORY(d->flags)) {
+ /* reg -> mem */
+ printf("M%3i <- R%3i",d->vv.regoff,s->vv.regoff);
+ }
+ else {
+ /* reg -> reg */
+ printf("R%3i <- R%3i",d->vv.regoff,s->vv.regoff);
+ }
+ printf("\n");
+ }
+#endif /* defined(SSA_DEBUG_VERBOSE) */
+ }
+}
+#endif /* defined(ENABLE_SSA) */
+
+
+
/*
* 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
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.
- $Id: codegen-common.h 7864 2007-05-03 21:17:26Z twisti $
+ $Id: codegen-common.h 7908 2007-05-15 09:55:17Z christian $
*/
/* machine dependent functions */
u1 *md_codegen_get_pv_from_pc(u1 *ra);
+
+#if defined(ENABLE_SSA)
+void codegen_emit_phi_moves(jitdata *jd, basicblock *bptr);
+#endif
+
#endif /* _CODEGEN_COMMON_H */
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.
- $Id: codegen.c 7865 2007-05-03 21:29:40Z twisti $
+ $Id: codegen.c 7908 2007-05-15 09:55:17Z christian $
*/
*******************************************************************************/
-#if defined(ENABLE_SSA)
-void cg_move(codegendata *cd, s4 type, s4 src_regoff, s4 src_flags,
- s4 dst_regoff, s4 dst_flags);
-void codegen_insert_phi_moves(jitdata *jd, basicblock *bptr);
-#endif
-
bool codegen_emit(jitdata *jd)
{
methodinfo *m;
for (p = 0, l = 0; p < md->paramcount; p++) {
t = md->paramtypes[p].type;
+ varindex = jd->local_map[l * 5 + t];
#if defined(ENABLE_SSA)
if ( ls != NULL ) {
- l = ls->local_0[p];
+ if (varindex != UNUSED)
+ varindex = ls->var_0[varindex];
+ if ((varindex != UNUSED) && (ls->lifetime[varindex].type == UNUSED))
+ varindex = UNUSED;
}
#endif
- varindex = jd->local_map[l * 5 + t];
l++;
if (IS_2_WORD_TYPE(t)) /* increment local counter for 2 word types */
l++;
}
#if defined(ENABLE_SSA)
- /* with SSA Header is Basic Block 0 - insert phi Moves if necessary */
+ /* with SSA the Header is Basic Block 0 - insert phi Moves if necessary */
if ( ls != NULL)
- codegen_insert_phi_moves(jd, ls->basicblocks[0]);
+ codegen_emit_phi_moves(jd, ls->basicblocks[0]);
#endif
/* end of header generation */
#if defined(ENABLE_SSA)
if ( ls != NULL ) {
last_cmd_was_goto = true;
+
/* In case of a Goto phimoves have to be inserted before the */
/* jump */
- codegen_insert_phi_moves(jd, bptr);
+
+ codegen_emit_phi_moves(jd, bptr);
}
#endif
emit_br(cd, iptr->dst.block);
if (d != TYPE_VOID) {
#if defined(ENABLE_SSA)
- if ((ls == NULL) || (!IS_TEMPVAR_INDEX(iptr->dst.varindex)) ||
- (ls->lifetime[-iptr->dst.varindex-1].type != -1))
+ if ((ls == NULL) /* || (!IS_TEMPVAR_INDEX(iptr->dst.varindex)) */ ||
+ (ls->lifetime[iptr->dst.varindex].type != UNUSED))
/* a "living" stackslot */
#endif
{
#endif
#if defined(ENABLE_SSA)
if ( ls != NULL ) {
+
/* by edge splitting, in Blocks with phi moves there can only */
/* be a goto as last command, no other Jump/Branch Command */
+
if (!last_cmd_was_goto)
- codegen_insert_phi_moves(jd, bptr);
+ codegen_emit_phi_moves(jd, bptr);
}
#endif
return true;
}
-#if defined(ENABLE_SSA)
-void codegen_insert_phi_moves(jitdata *jd, basicblock *bptr) {
- /* look for phi moves */
- int t_a,s_a,i, type;
- int t_lt, s_lt; /* lifetime indices of phi_moves */
- s4 t_regoff, s_regoff, s_flags, t_flags;
- codegendata *cd;
- lsradata *ls;
-
- MCODECHECK(512);
-
- ls = jd->ls;
- cd = jd->cd;
-
- /* Moves from phi functions with highest indices have to be */
- /* inserted first, since this is the order as is used for */
- /* conflict resolution */
- for(i = ls->num_phi_moves[bptr->nr] - 1; i >= 0 ; i--) {
- t_a = ls->phi_moves[bptr->nr][i][0];
- s_a = ls->phi_moves[bptr->nr][i][1];
-#if defined(SSA_DEBUG_VERBOSE)
- if (compileverbose)
- printf("BB %3i Move %3i <- %3i ", bptr->nr, t_a, s_a);
-#endif
- if (t_a >= 0) {
- /* local var lifetimes */
- t_lt = ls->maxlifetimes + t_a;
- type = ls->lifetime[t_lt].type;
- }
- else {
- t_lt = -t_a-1;
- type = ls->lifetime[t_lt].local_ss->s->type;
- /* stackslot lifetime */
- }
-
- if (type == -1) {
-#if defined(SSA_DEBUG_VERBOSE)
- if (compileverbose)
- printf("...returning - phi lifetimes where joined\n");
-#endif
- return;
- }
-
- if (s_a >= 0) {
- /* local var lifetimes */
- s_lt = ls->maxlifetimes + s_a;
- type = ls->lifetime[s_lt].type;
- }
- else {
- s_lt = -s_a-1;
- type = ls->lifetime[s_lt].type;
- /* stackslot lifetime */
- }
-
- if (type == -1) {
-#if defined(SSA_DEBUG_VERBOSE)
- if (compileverbose)
- printf("...returning - phi lifetimes where joined\n");
-#endif
- return;
- }
-
- if (t_a >= 0) {
- t_flags = VAR(t_a)->flags;
- t_regoff = VAR(t_a)->vv.regoff;
-
- }
- else {
- t_flags = ls->lifetime[t_lt].local_ss->s->flags;
- t_regoff = ls->lifetime[t_lt].local_ss->s->regoff;
- }
-
- if (s_a >= 0) {
- /* local var move */
- s_flags = VAR(s_a)->flags;
- s_regoff = VAR(s_a)->vv.regoff;
- } else {
- /* stackslot lifetime */
- s_flags = ls->lifetime[s_lt].local_ss->s->flags;
- s_regoff = ls->lifetime[s_lt].local_ss->s->regoff;
- }
-
- if (type == -1) {
-#if defined(SSA_DEBUG_VERBOSE)
- if (compileverbose)
- printf("...returning - phi lifetimes where joined\n");
-#endif
- return;
- }
-
- cg_move(cd, type, s_regoff, s_flags, t_regoff, t_flags);
-
-#if defined(SSA_DEBUG_VERBOSE)
- if (compileverbose) {
- if (IS_INMEMORY(t_flags) && IS_INMEMORY(s_flags)) {
- /* mem -> mem */
- printf("M%3i <- M%3i",t_regoff,s_regoff);
- }
- else if (IS_INMEMORY(s_flags)) {
- /* mem -> reg */
- printf("R%3i <- M%3i",t_regoff,s_regoff);
- }
- else if (IS_INMEMORY(t_flags)) {
- /* reg -> mem */
- printf("M%3i <- R%3i",t_regoff,s_regoff);
- }
- else {
- /* reg -> reg */
- printf("R%3i <- R%3i",t_regoff,s_regoff);
- }
- printf("\n");
- }
-#endif /* defined(SSA_DEBUG_VERBOSE) */
- }
-}
-
-void cg_move(codegendata *cd, s4 type, s4 src_regoff, s4 src_flags,
- s4 dst_regoff, s4 dst_flags) {
- if ((IS_INMEMORY(dst_flags)) && (IS_INMEMORY(src_flags))) {
- /* mem -> mem */
- if (dst_regoff != src_regoff) {
- if (!IS_2_WORD_TYPE(type)) {
- if (IS_FLT_DBL_TYPE(type)) {
- emit_flds_membase(cd, REG_SP, src_regoff * 4);
- emit_fstps_membase(cd, REG_SP, dst_regoff * 4);
- } else{
- emit_mov_membase_reg(cd, REG_SP, src_regoff * 4,
- REG_ITMP1);
- emit_mov_reg_membase(cd, REG_ITMP1, REG_SP, dst_regoff * 4);
- }
- } else { /* LONG OR DOUBLE */
- if (IS_FLT_DBL_TYPE(type)) {
- emit_fldl_membase( cd, REG_SP, src_regoff * 4);
- emit_fstpl_membase(cd, REG_SP, dst_regoff * 4);
- } else {
- emit_mov_membase_reg(cd, REG_SP, src_regoff * 4,
- REG_ITMP1);
- emit_mov_reg_membase(cd, REG_ITMP1, REG_SP, dst_regoff * 4);
- emit_mov_membase_reg(cd, REG_SP, src_regoff * 4 + 4,
- REG_ITMP1);
- emit_mov_reg_membase(cd, REG_ITMP1, REG_SP,
- dst_regoff * 4 + 4);
- }
- }
- }
- } else {
- if (IS_FLT_DBL_TYPE(type)) {
- log_text("cg_move: flt/dbl type have to be in memory\n");
-/* assert(0); */
- }
- if (IS_2_WORD_TYPE(type)) {
- log_text("cg_move: longs have to be in memory\n");
-/* assert(0); */
- }
- if (IS_INMEMORY(src_flags)) {
- /* mem -> reg */
- emit_mov_membase_reg(cd, REG_SP, src_regoff * 4, dst_regoff);
- } else if (IS_INMEMORY(dst_flags)) {
- /* reg -> mem */
- emit_mov_reg_membase(cd, src_regoff, REG_SP, dst_regoff * 4);
- } else {
- /* reg -> reg */
- /* only ints can be in regs on i386 */
- M_INTMOVE(src_regoff,dst_regoff);
- }
- }
-}
-#endif /* defined(ENABLE_SSA) */
-
-
/* codegen_emit_stub_compiler **************************************************
Emit a stub routine which calls the compiler.
#include "toolbox/bitvector.h"
+#include "vm/jit/jit.h"
+
#include "vm/jit/optimizing/graph.h"
#include "vm/jit/optimizing/dominators.h"
*/
+#include <stdlib.h>
+
+#include "config.h"
+
#include "mm/memory.h"
#include "toolbox/bitvector.h"
+#include "vm/jit/jit.h"
+
#include "vm/jit/optimizing/lsra.h"
#include "vm/jit/optimizing/ssa.h"
#include "vm/jit/optimizing/graph.h"
#ifdef GRAPH_DEBUG_VERBOSE
-#include "vm/options.h"
+#include "vmcore/options.h"
#endif
-
/* Helpers for graph_make_cfg */
-void graph_add_jsr( methodinfo *m, graphdata *gd, struct _sbr *sbr,int from,
- int to);
-void graph_add_cfg( methodinfo *m, graphdata *gd, int from, int to);
-void graph_add_exceptions(methodinfo *m, codegendata *cd, graphdata *gd);
-void graph_add_subs(methodinfo *m, graphdata *gd, struct _sbr *sbr);
+void graph_add_cfg( jitdata *jd, graphdata *gd, basicblock *, basicblock *);
+void graph_add_exceptions(jitdata *jd, graphdata *gd);
void graph_add_edge( graphdata *gd, int from, int to );
-/* Helper for graph_make_subs */
-void graph_add_sub( methodinfo *m, graphdata *gd, int b_index,
- graph_element *ret, bool *visited );
+
/* Helper for graph_get_first_* */
int graph_get_first_(graph_element *ge, graphiterator *i);
void transform_CFG(jitdata *, graphdata *);
gd->num_pred[to]++;
}
-/* split the edge from BB from shown by iterator i wiht new_block */
+/* split the edge from BB from shown by iterator i with new_block */
void graph_split_edge(graphdata *gd, int from, graphiterator *i, int new_block) {
graphiterator i_pred;
graph_element *n;
int l, succ;
/* i->value is the BB index of the "old" successor */
+
succ = (*i)->value;
+
/* search for iterator showing predecessor edge from BB succ back to */
/* from */
+
l = graph_get_first_predecessor(gd, succ, &i_pred);
for(; (l != -1) && (l != from); l = graph_get_next(&i_pred));
_GRAPH_ASSERT(l == from);
/* change CFG entries */
+
(*i)->value = new_block;
i_pred->value = new_block;
/* and insert the CFG successor and predecesser entries for new_block */
/* 2 entries needed */
+
n = DMNEW(graph_element, 2);
+
/* make the successor entry for new_block */
+
n->value = succ;
n->next = gd->successor[new_block];
gd->successor[new_block] = n;
gd->num_succ[new_block]++;
- n++;
/* make the predecessor entry for new_block */
+
+ n++;
n->value = from;
n->next = gd->predecessor[new_block];
gd->predecessor[new_block] = n;
( pred,succ,num_pred of lsradata structure)
************************************************/
void graph_make_cfg(jitdata *jd,graphdata *gd) {
- instruction *ip;
- s4 *s4ptr;
- int high, low, count;
- int b_index, len;
- bool fall_through;
- struct _sbr sbr; /* list of subroutines, sorted by header */
+ instruction *iptr;
+ lookup_target_t *lookup;
+ branch_target_t *table;
+ int len, i, l;
methodinfo *m;
codegendata *cd;
registerdata *rd;
lsradata *ls;
+ basicblock *bptr;
m = jd->m;
cd = jd->cd;
rd = jd->rd;
ls = jd->ls;
- sbr.next = NULL;
-
/* Add edge from new Basic Block 0 (parameter initialization) */
graph_add_edge(gd, 0, 1);
- b_index=0;
- while (b_index < m->basicblockcount ) {
- if (m->basicblocks[b_index].flags >= BBREACHED) {
- fall_through = false;
-
- if ((len = m->basicblocks[b_index].icount)) {
- /* set ip to last non NOP instruction */
- ip = m->basicblocks[b_index].iinstr +
- m->basicblocks[b_index].icount -1;
- while ((len>0) && (ip->opc == ICMD_NOP)) {
+ for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
+ if (bptr->flags >= BBREACHED) {
+ if ((len = bptr->icount)) {
+ /* set iptr to last non NOP instruction */
+ iptr = bptr->iinstr + bptr->icount -1;
+ while ((len>0) && (iptr->opc == ICMD_NOP)) {
len--;
- ip--;
+ iptr--;
}
/* block contains instructions */
- switch (ip->opc) { /* check type of last instruction */
+ switch (iptr->opc) { /* check type of last instruction */
case ICMD_RETURN:
case ICMD_IRETURN:
case ICMD_LRETURN:
case ICMD_DRETURN:
case ICMD_ARETURN:
case ICMD_ATHROW:
-/* graph_add_cfg(m, gd, b_index, m->basicblockcount); */
break; /* function returns -> end of graph */
case ICMD_IFNULL:
case ICMD_IF_LCMPLE:
case ICMD_IF_ACMPEQ:
case ICMD_IF_ACMPNE: /* branch -> add next block */
- fall_through = true;
-/* graph_add_cfg(m, gd, b_index, b_index+1); */
- /* fall throu -> add branch target */
+ /* Add branch target */
+ graph_add_cfg(jd, gd, bptr, iptr->dst.block);
+ /* Add fall through path */
+ graph_add_cfg(jd, gd, bptr, bptr->next);
+ break;
+
case ICMD_GOTO:
- graph_add_cfg(m, gd, b_index, m->basicblockindex[ip->op1]);
- if (fall_through)
- graph_add_cfg(m, gd, b_index, b_index+1);
+ graph_add_cfg(jd, gd, bptr, iptr->dst.block);
break; /* visit branch (goto) target */
case ICMD_TABLESWITCH: /* switch statement */
- s4ptr = ip->val.a;
-
- graph_add_cfg(m, gd, b_index, m->basicblockindex[*s4ptr]);
-
- s4ptr++;
- low = *s4ptr;
- s4ptr++;
- high = *s4ptr;
-
- count = (high-low+1);
-
- while (--count >= 0) {
- s4ptr++;
- graph_add_cfg(m, gd, b_index,
- m->basicblockindex[*s4ptr]);
- }
+ table = iptr->dst.table;
+ l = iptr->sx.s23.s2.tablelow;
+ i = iptr->sx.s23.s3.tablehigh;
+ i = i - l + 1;
+
+ /* Add default target */
+
+ graph_add_cfg(jd, gd, bptr, table[0].block);
+ table += i;
+
+ while (--i >= 0) {
+ graph_add_cfg(jd, gd, bptr, table->block);
+ --table;
+ }
break;
case ICMD_LOOKUPSWITCH: /* switch statement */
- s4ptr = ip->val.a;
-
- graph_add_cfg(m, gd, b_index, m->basicblockindex[*s4ptr]);
-
- ++s4ptr;
- count = *s4ptr++;
-
- while (--count >= 0) {
- graph_add_cfg(m, gd, b_index,
- m->basicblockindex[s4ptr[1]]);
- s4ptr += 2;
- }
- break;
+ lookup = iptr->dst.lookup;
+ i = iptr->sx.s23.s2.lookupcount;
+
+ while (--i >= 0) {
+ graph_add_cfg(jd, gd, bptr, lookup->target.block);
+ lookup++;
+ }
- case ICMD_JSR:
- graph_add_jsr(m, gd, &sbr, b_index, m->basicblockindex[ip->op1]);
+ graph_add_cfg(jd, gd, bptr, iptr->sx.s23.s3.lookupdefault.block);
break;
-
+
case ICMD_RET:
+ case ICMD_JSR:
+ assert(0);
break;
+
+ case ICMD_NOP:
+ assert(0);
default:
- graph_add_cfg(m, gd, b_index, b_index + 1 );
+ graph_add_cfg(jd, gd, bptr, bptr + 1 );
break;
- } /* switch (ip->opc)*/
- } /* if (m->basicblocks[blockIndex].icount) */
- } /* if (m->basicblocks[b_index].flags >= BBREACHED) */
- b_index++;
- } /* while (b_index < m->basicblockcount ) */
-
- /* add subroutines before exceptions! They "destroy" the CFG */
- graph_add_subs(m, gd, &sbr);
- graph_add_exceptions(m, cd, gd);
+ } /* switch (iptr->opc)*/
+ } /* if (bptr->icount) */
+ } /* if (bptr->flags >= BBREACHED) */
+ } /* for (bptr = ...; bptr != NULL; bptr = bptr->next) */
+
+ graph_add_exceptions(jd, gd);
transform_CFG(jd, gd);
+
#ifdef GRAPH_DEBUG_VERBOSE
if (compileverbose)
graph_print(ls, gd);
/*****************************************************************
add Edges from guarded Areas to Exception handlers in the CFG
*****************************************************************/
-void graph_add_exceptions(methodinfo *m, codegendata *cd, graphdata *gd) {
- int i;
+void graph_add_exceptions(jitdata *jd, graphdata *gd) {
+#if 0
+ basicblock *bptr;
+ raw_exception_entry *ex;
+ codegendata *cd;
+
+ cd = jd->cd;
/* add cfg edges from all bb of a try block to the start of the according */
/* exception handler to ensure the right order after depthfirst search */
- exceptiontable *ex;
+
ex=jd->exceptiontable;
+
#ifdef GRAPH_DEBUG_VERBOSE
if (compileverbose)
printf("ExTable(%i): ", jd->exceptiontablelength);
printf("[%i-%i]->%i ",ex->start->nr, ex->end->nr,
ex->handler->nr);
#endif
- _GRAPH_ASSERT(ex->handler->nr < m->basicblockcount);
- _GRAPH_ASSERT(m->basicblocks[ex->handler->nr].flags >= BBREACHED);
+
+ _GRAPH_ASSERT(ex->handler->nr < jd->new_basicblockcount);
+ _GRAPH_ASSERT(ex->handler->flags >= BBREACHED);
_GRAPH_ASSERT(ex->start->nr <= ex->end->nr);
/* loop all valid Basic Blocks of the guarded area and add CFG edges */
/* to the appropriate handler */
- for (i=ex->start->nr; (i <= ex->end->nr) &&
- (i < m->basicblockcount); i++)
- if (m->basicblocks[i].flags >= BBREACHED)
- graph_add_cfg(m, gd, i, ex->handler->nr);
+ for (bptr = ex->start; (bptr != NULL) && (bptr != ex->end); bptr = bptr->next)
+ if (bptr->flags >= BBREACHED)
+ graph_add_cfg(jd, gd, bptr, ex->handler);
+
+ _GRAPH_ASSERT((bptr != NULL)
+ && ((bptr->flags >=BBREACHED) || (bptr == ex->end)));
}
#ifdef GRAPH_DEBUG_VERBOSE
if (compileverbose)
printf("\n");
#endif
-}
-
-/**************************************************
-Add subroutines from ls->sbr list to CFG
-**************************************************/
-void graph_add_subs(methodinfo *m, graphdata *gd, struct _sbr *sbr) {
- struct _sbr *_sbr;
- bool *visited;
- int i;
-#ifdef GRAPH_DEBUG_VERBOSE
- graph_element *ret;
-#endif
-
- visited = (bool *)DMNEW(int, m->basicblockcount + 1);
- for (i=0; i <= m->basicblockcount; i++) visited[i] = false;
- for (_sbr = sbr->next; _sbr != NULL; _sbr=_sbr->next) {
-#ifdef GRAPH_DEBUG_VERBOSE
- if (compileverbose) {
- printf("Subroutine Header: %3i Return Adresses:",_sbr->header);
- for (ret = _sbr->ret; ret != NULL; ret = ret->next)
- printf(" %3i", ret->value);
- printf("\n");
- }
#endif
- graph_add_sub( m, gd, _sbr->header, _sbr->ret, visited );
-
- }
}
+
/******************************************************************
Add the CFG Edge into next und succ
******************************************************************/
-void graph_add_cfg( methodinfo *m, graphdata *gd, int from, int to) {
+void graph_add_cfg( jitdata *jd, graphdata *gd, basicblock *from,
+ basicblock *to) {
/* ignore Empty, Deleted,... Basic Blocks as target */
/* TODO: Setup BasicBlock array before to avoid this */
/* best together with using the basicblock list, so lsra works */
/* with opt_loops, too */
- for (;(to < m->basicblockcount) && (m->basicblocks[to].flags < BBREACHED);
- to++);
- /* add one to from and to, so the to be inserted Basic Block 0 is */
- /* already regarded */
- graph_add_edge( gd, from + 1, to + 1);
-}
+ for (; (to != NULL) && (to->flags < BBREACHED); to = to->next);
-/*******************************************************************
-Remember Subroutine "jumps" in ls->sbr and add the CFG Edge of the
-"jump" into succ and pred
-*******************************************************************/
-void graph_add_jsr( methodinfo *m, graphdata *gd, struct _sbr *sbr, int from,
- int to) {
- struct _sbr *_sbr, *n;
- graph_element *ret;
+ _GRAPH_ASSERT(to != NULL);
- /* ignore Empty, Deleted,... Basic Blocks as target */
- /* TODO: Setup BasicBlock array before to avoid this */
- /* best together with using the basicblock list, so lsra works */
- /* with opt_loops, too */
- for (; (to < m->basicblockcount) && (m->basicblocks[to].flags < BBREACHED);
- to++);
- _GRAPH_ASSERT( to != m->basicblockcount );
-
- graph_add_cfg(m, gd, from, to);
-
- /* from + 1 ist the return Basic Block Index */
- for (from++; (from < m->basicblockcount) &&
- (m->basicblocks[from].flags < BBREACHED); from++);
- _GRAPH_ASSERT(from != m->basicblockcount);
-
- /* add subroutine info in ls->sbr.next */
-
- /* search for right place to insert */
- for (_sbr = sbr; (_sbr->next != NULL) && (_sbr->next->header < to);
- _sbr=_sbr->next);
-
- if ((_sbr->next!= NULL) && (_sbr->next->header == to)) {
- /* Entry for this sub already exist */
- _sbr = _sbr->next;
- } else {
- /* make new Entry and insert it in ls->sbr.next */
- n = DNEW( struct _sbr );
- n->header = to;
- n->ret = NULL;
-
- n->next = _sbr->next;
- _sbr->next = n;
-
- _sbr = n;
- }
- /* now insert return adress in sbr->ret */
- ret = DNEW(graph_element);
- ret->value = from;
- ret->next = _sbr->ret;
- _sbr->ret = ret;
+ /* add one to from and to, so the to be inserted Basic Block 0 is */
+ /* already regarded */
+ graph_add_edge( gd, from->nr + 1, to->nr + 1);
}
-/**************************************************
-Add a subroutine to CFG
-**************************************************/
-void graph_add_sub(methodinfo *m, graphdata *gd, int b_index,
- graph_element *ret, bool *visited ) {
- graph_element *l;
- instruction *ip;
- bool next_block;
- graphiterator i;
- int s;
-
- /* break at virtual End Block */
- if (b_index != m->basicblockcount) {
- visited[b_index] = true;
- next_block = false;
-
- if (m->basicblocks[b_index].flags < BBREACHED)
- next_block = true;
- if (!next_block && !(m->basicblocks[b_index].icount))
- next_block = true;
-
- if (!next_block) {
- ip = m->basicblocks[b_index].iinstr +
- m->basicblocks[b_index].icount - 1;
-
- if (ip->opc == ICMD_JSR) /* nested Subroutines */
- next_block = true;
- }
-
- if (!next_block) {
- if (ip->opc == ICMD_RET) {
- /* subroutine return found -> add return adresses to CFG */
- for (l = ret; l != NULL; l = l->next)
- graph_add_cfg( m, gd, b_index, l->value);
- } else { /* follow CFG */
- s = graph_get_first_successor(gd, b_index, &i);
- for(; s != -1; s = graph_get_next(&i))
- if (!visited[s])
- graph_add_sub( m, gd, l->value, ret, visited);
- }
- } else { /* fall through to next block */
- if (b_index + 1 < m->basicblockcount)
- if (!visited[b_index + 1])
- graph_add_sub(m, gd, b_index + 1, ret, visited);
- }
- }
-}
/*****************************************************************
Sort Basic Blocks using Depth First search in reverse post order
}
-void graph_init_basicblock( basicblock *bptr, int b_index) {
+void graph_init_basicblock(jitdata *jd, basicblock *bptr, int b_index) {
bptr->nr = b_index;
bptr->icount = 0;
bptr->iinstr = NULL;
bptr->type = BBTYPE_STD;
bptr->flags = BBFINISHED;
- bptr->instack = NULL;
- bptr->outstack = NULL;
+ bptr->invars = NULL;
+ bptr->outvars = NULL;
bptr->indepth = 0;
bptr->outdepth = 0;
bptr->branchrefs = NULL;
bptr->mpc = -1;
bptr->next = NULL;
+ bptr->method = jd->m;
}
/*********************************************************************+
void transform_CFG(jitdata *jd, graphdata *gd) {
int i, j, k, n, num_new_blocks;
int **var_def;
- basicblock *tmp;
- stackptr in, out, new_stack;
+ basicblock *tmp, *bptr;
+ s4 *in, *out, *new_in_stack, *new_out_stack;
graphiterator iter;
int *num_succ;
struct graph_element **successor;
/* multiple predecessor -> if found insert a new block between to split */
/* this edge. As first step count how many blocks have to be inserted. */
- num_new_blocks = 0;
- for(i = 0; i< m->basicblockcount + 1; i++) {
+ num_new_blocks = 1;
+ for(i = 0; i< jd->basicblockcount + 1; i++) {
if (graph_has_multiple_successors(gd, i)) {
k = graph_get_first_successor(gd, i, &iter);
for(; k != -1; k = graph_get_next(&iter)) {
}
/* increase now basicblockcount accordingly. */
- ls->basicblockcount = m->basicblockcount + num_new_blocks + 1;
+ ls->basicblockcount = jd->basicblockcount + num_new_blocks;
ls->basicblocks = DMNEW(basicblock *, ls->basicblockcount);
+ for(i = 0; i< ls->basicblockcount; i++)
+ ls->basicblocks[i] = NULL;
+
/* copy Basic Block References to ls->basicblocks */
- for(i = 0; i< m->basicblockcount; i++) {
- ls->basicblocks[i+1] = &(m->basicblocks[i]);
- ls->basicblocks[i+1]->nr = i+1;
+
+ for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
+/* if (bptr->flags >= BBREACHED) { */
+ _GRAPH_ASSERT(bptr->nr < jd->basicblockcount);
+ ls->basicblocks[bptr->nr + 1] = bptr;
+ bptr->nr = bptr->nr+1;
+/* } */
}
- /* Create new Basic Blocks: 0, [m->basicblockcount..ls->basicblockcount[ */
- /* num_new_blocks + 1 have to be inserted*/
- tmp = DMNEW( basicblock, num_new_blocks + 1);
+ /* Create new Basic Blocks:
+ 0, [jd->new_basicblockcount..ls->basicblockcount[ */
+ /* num_new_blocks have to be inserted*/
+
+ tmp = DMNEW( basicblock, num_new_blocks);
ls->basicblocks[0] = tmp;
- graph_init_basicblock( tmp, 0);
+ graph_init_basicblock( jd, tmp, 0);
tmp++;
ls->basicblocks[0]->next = ls->basicblocks[1];
- if (ls->basicblockcount > m->basicblockcount + 1) {
+ if (ls->basicblockcount > jd->basicblockcount + 1) {
/* new Blocks have to be inserted */
num_succ = DMNEW(int, ls->basicblockcount);
successor = DMNEW(graph_element *, ls->basicblockcount);
num_pred = DMNEW(int, ls->basicblockcount);
predecessor = DMNEW(graph_element *, ls->basicblockcount);
- /* regard the + 1 for the already regarded new BB 0 */
+ /* regard the + 1 for the already inserted new BB 0 */
/* So recreate ls->var_def */
var_def = DMNEW(int *, ls->basicblockcount);
- for(i = 0; i < m->basicblockcount + 1; i++) {
+ for(i = 0; i < jd->basicblockcount + 1; i++) {
var_def[i] = ls->var_def[i];
num_succ[i] = gd->num_succ[i];
num_pred[i] = gd->num_pred[i];
successor[i] = gd->successor[i];
predecessor[i] = gd->predecessor[i];
}
- for(i = m->basicblockcount + 1; i < ls->basicblockcount; i++) {
- var_def[i] = bv_new(ls->max_vars);
- graph_init_basicblock( tmp, i);
+ for(i = jd->basicblockcount + 1; i < ls->basicblockcount; i++) {
+ var_def[i] = bv_new(jd->varcount);
+ graph_init_basicblock( jd, tmp, i);
ls->basicblocks[i] = tmp;
tmp++;
}
/* Now Split the edges */
- num_new_blocks = m->basicblockcount + 1; /* first free new block index */
- for(i = 0; i < m->basicblockcount + 1; i++) {
+ num_new_blocks = jd->basicblockcount + 1; /* first free new block index */
+ for(i = 0; i < jd->basicblockcount + 1; i++) {
if (graph_has_multiple_successors(gd, i)) {/* more than one successor */
j = graph_get_first_successor( gd, i, &iter);
for(; j != -1; j = graph_get_next(&iter)) {
ls->basicblocks[num_new_blocks]->indepth =
ls->basicblocks[i]->outdepth;
- out = ls->basicblocks[i]->outstack;
- ls->basicblocks[num_new_blocks]->instack = in = NULL;
+ out = ls->basicblocks[i]->outvars;
+ ls->basicblocks[num_new_blocks]->invars = in = NULL;
if (ls->basicblocks[num_new_blocks]->indepth > 0)
- new_stack = DMNEW( stackelement,
+ new_in_stack = DMNEW( s4,
+ ls->basicblocks[num_new_blocks]->indepth);
+ new_out_stack = DMNEW( s4,
ls->basicblocks[num_new_blocks]->indepth);
+
for(n=0; n<ls->basicblocks[num_new_blocks]->indepth; n++) {
- if (in == NULL) {
- in = new_stack++;
- } else {
- in->prev = new_stack++;
- in = in->prev;
- }
- in->type = out->type;
- in->varkind = STACKVAR;
- in->varnum = 0;
- in->regoff = 0;
- in->flags = 0;
- in->prev = NULL;
- /* Add Definition */
- if (n == 0)
- ls->basicblocks[num_new_blocks]->instack = in;
-
- out = out->prev;
+ new_in_stack[n] = out[n];
+ new_out_stack[n] = out[n];
}
+ ls->basicblocks[num_new_blocks]->invars = new_in_stack;
/* Create Outstack */
- ls->basicblocks[num_new_blocks]->outstack =
- ls->basicblocks[num_new_blocks]->instack;
+ ls->basicblocks[num_new_blocks]->outvars =
+ new_out_stack;
ls->basicblocks[num_new_blocks]->outdepth =
ls->basicblocks[num_new_blocks]->indepth;
_GRAPH_ASSERT(ls->basicblocks[num_new_blocks]->outdepth ==
- ls->basicblocks[j]->indepth );
+ ls->basicblocks[j]->indepth );
+
+#if 0
+ /* !!!! There can't be inoutvar definitions in one of these */
+ /* newly inserted basicblocks !!!! */
/* Add Definition */
/* decrease nr temporarly, because ssa_set_interface*/
/* adds 1 since it is called from stack.c, where there is */
/* no new BB 0 inserted like now */
+
ls->basicblocks[num_new_blocks]->nr--;
- ssa_set_interface(cd, ls, ls->basicblocks[num_new_blocks]);
+ ssa_set_interface(jd, ls->basicblocks[num_new_blocks]);
ls->basicblocks[num_new_blocks]->nr++;
+#endif
num_new_blocks++;
}
}
}
void transform_BB(jitdata *jd, graphdata *gd) {
- int i, len;
+ int n, len;
int pred, succ;
basicblock *last_block;
- instruction *ip;
+ instruction *iptr;
graphiterator iter;
methodinfo *m;
lsradata *ls;
/* the "real" last Block is always an empty block */
/* so take the one before, to insert new blocks after it */
- last_block = &(m->basicblocks[m->basicblockcount - 1]);
+ last_block = &(jd->basicblocks[jd->basicblockcount - 1]);
_GRAPH_ASSERT(last_block->next->next == NULL);
_GRAPH_ASSERT(last_block->next->flags <= BBREACHED);
last_block->next->nr = ls->basicblockcount;
/* look through new blocks */
- for(i = m->basicblockcount + 1; i < ls->basicblockcount ; i++) {
+ for(n = jd->basicblockcount + 1; n < ls->basicblockcount ; n++) {
/* if a phi move happens at this block, we need this block */
/* if not, remove him from the CFG */
- if (ls->num_phi_moves[i] > 0) {
+ if (ls->num_phi_moves[n] > 0) {
/* i can only have one predecessor and one successor! */
- _GRAPH_ASSERT( graph_has_multiple_predecessors(gd,i) == false);
- _GRAPH_ASSERT( graph_has_multiple_successors(gd,i) == false);
+ _GRAPH_ASSERT( graph_has_multiple_predecessors(gd, n) == false);
+ _GRAPH_ASSERT( graph_has_multiple_successors(gd, n) == false);
- succ = graph_get_first_successor(gd, i, &iter);
- pred = graph_get_first_predecessor(gd, i, &iter);
+ succ = graph_get_first_successor(gd, n, &iter);
+ pred = graph_get_first_predecessor(gd, n, &iter);
- /* set ip to last instruction */
+ /* set iptr to last instruction */
len = ls->basicblocks[pred]->icount;
- ip = ls->basicblocks[pred]->iinstr + len - 1;
- while ((len>0) && (ip->opc == ICMD_NOP)) {
+ iptr = ls->basicblocks[pred]->iinstr + len - 1;
+ while ((len>0) && (iptr->opc == ICMD_NOP)) {
len--;
- ip--;
+ iptr--;
}
/* with JSR there can not be multiple successors */
- _GRAPH_ASSERT(ip->opc != ICMD_JSR);
+ _GRAPH_ASSERT(iptr->opc != ICMD_JSR);
/* If the return Statment has more successors and */
/* one of these has more predecessor, we are in */
/* troubles - one would have to insert a new Block */
/* after the one which executes the ICMD_JSR */
/* !!TODO!! if subroutines will not be inlined */
- _GRAPH_ASSERT(ip->opc != ICMD_RET);
+ _GRAPH_ASSERT(iptr->opc != ICMD_RET);
/* link new block into basicblocks list */
/* if edge to split is the "fallthrough" path of the */
/* conditional, then link the new block inbetween */
/* and generate no ICMD */
/* else if edge to split is the branch, generate a */
- /* ICMD_GOTO and add new BB at and of BB List */
+ /* ICMD_GOTO and add new BB at the end of the BB List*/
if ((ls->basicblocks[pred]->next == ls->basicblocks[succ])
- && (ip->opc != ICMD_LOOKUPSWITCH)
- && (ip->opc != ICMD_TABLESWITCH)
- && (ip->opc != ICMD_GOTO)) {
+ && (iptr->opc != ICMD_LOOKUPSWITCH)
+ && (iptr->opc != ICMD_TABLESWITCH)
+ && (iptr->opc != ICMD_GOTO)) {
/* GOTO, *SWITCH have no fallthrough path */
/* link into fallthrough path */
- ls->basicblocks[i]->next =
+ ls->basicblocks[n]->next =
ls->basicblocks[pred]->next;
ls->basicblocks[pred]->next =
- ls->basicblocks[i];
+ ls->basicblocks[n];
/* generate no instructions */
- ls->basicblocks[i]->icount = 1;
- ls->basicblocks[i]->iinstr = NEW(instruction);
- ls->basicblocks[i]->iinstr[0].opc = ICMD_NOP;
+ ls->basicblocks[n]->icount = 1;
+ ls->basicblocks[n]->iinstr = NEW(instruction);
+ ls->basicblocks[n]->iinstr[0].opc = ICMD_NOP;
} else {
- /* Block i is in the Branch path */
+ /* Block n is in the Branch path */
/* link Block at the end */
- ls->basicblocks[i]->next =last_block->next;
- last_block->next = ls->basicblocks[i];
- last_block = ls->basicblocks[i];
+ ls->basicblocks[n]->next =last_block->next;
+ last_block->next = ls->basicblocks[n];
+ last_block = ls->basicblocks[n];
/* change the Branch Target to BB i */
- switch(ip->opc) {
+ switch(iptr->opc) {
case ICMD_LOOKUPSWITCH:
{
- s4 k, l, *s4ptr;
- void **tptr;
-
- tptr = (void **) ip->target;
- if ((basicblock*)tptr[0] == ls->basicblocks[succ]) {
- /* target found -> change*/
- tptr[0] = ls->basicblocks[i];
- }
+ s4 i;
+ lookup_target_t *lookup;
- s4ptr = ip->val.a;
- l = s4ptr[0]; /* default */
- k = s4ptr[1]; /* count */
-
- while (--k >= 0) {
- s4ptr += 2;
- ++tptr;
+ lookup = iptr->dst.lookup;
- if ((basicblock*)tptr[0] == ls->basicblocks[succ])
- {
+ i = iptr->sx.s23.s2.lookupcount;
+
+ while (--i >= 0) {
+ if (lookup->target.block == ls->basicblocks[succ])
/* target found -> change */
- tptr[0] = ls->basicblocks[i];
- }
+ lookup->target.block = ls->basicblocks[n];
+ lookup++;
}
+
+ if (iptr->sx.s23.s3.lookupdefault.block == ls->basicblocks[succ])
+ /* target found -> change */
+ iptr->sx.s23.s3.lookupdefault.block = ls->basicblocks[n];
}
break;
case ICMD_TABLESWITCH:
{
- s4 k, l, *s4ptr;
- void **tptr;
+ s4 i, l;
+ branch_target_t *table;
- tptr = (void **) ip->target;
-
- s4ptr = ip->val.a;
- l = s4ptr[1]; /* low */
- k = s4ptr[2]; /* high */
+ table = iptr->dst.table;
+
+ l = iptr->sx.s23.s2.tablelow;
+ i = iptr->sx.s23.s3.tablehigh;
- k = k - l + 1;
+ i = i - l + 1;
- if ((basicblock*)tptr[0] == ls->basicblocks[succ])
- {
+ if (table[0].block == ls->basicblocks[succ]) /* default target */
/* target found -> change*/
- tptr[0] = ls->basicblocks[i];
- }
- tptr += k;
-
- while (--k >= 0) {
- if ((basicblock*)tptr[0] == ls->basicblocks[succ])
- {
- /* target found -> change*/
- tptr[0] = ls->basicblocks[i];
- }
- --tptr;
+ table[0].block = ls->basicblocks[n];
+
+ table += i;
+
+ while (--i >= 0) {
+ if (table->block == ls->basicblocks[succ])
+ /* target found -> change */
+ table->block = ls->basicblocks[n];
+ --table;
}
}
break;
case ICMD_IF_ACMPEQ:
case ICMD_IF_ACMPNE:
case ICMD_GOTO:
- _GRAPH_ASSERT(ip->target == ls->basicblocks[succ]);
- ip->target = ls->basicblocks[i];
+ _GRAPH_ASSERT(iptr->dst.block == ls->basicblocks[succ]);
+ iptr->dst.block = ls->basicblocks[n];
break;
default:
/* Exception Edge to split */
}
/* Generate the ICMD_GOTO */
- ls->basicblocks[i]->icount = 1;
- ls->basicblocks[i]->iinstr =
+ ls->basicblocks[n]->icount = 1;
+ ls->basicblocks[n]->iinstr =
DNEW(instruction);
- ls->basicblocks[i]->iinstr->opc =
+ ls->basicblocks[n]->iinstr->opc =
ICMD_GOTO;
- ls->basicblocks[i]->iinstr->target =
+ ls->basicblocks[n]->iinstr->dst.block =
ls->basicblocks[succ];
- ls->basicblocks[i]->iinstr->op1 = succ;
}
- ls->basicblocks[i]->iinstr[0].dst =
- ls->basicblocks[i]->outstack;
}
}
}
# define _GRAPH_ASSERT(a)
#endif
+#if 0
struct _sbr {
int header; /* BB Index of subroutine start (SBR_HEADER) */
struct graph_element *ret; /* List of possible return BB indizes */
struct _sbr *next;
};
+#endif
struct graph_element {
int value;
#include "vm/jit/optimizing/lifetimes.h"
#ifdef LT_DEBUG_VERBOSE
-#include "vm/options.h"
+#include "vmcore/options.h"
#endif
#include <time.h>
#include <errno.h>
/* function prototypes */
-void _scan_lifetimes(registerdata *rd, lsradata *ls, graphdata *gd,
- basicblock *bptr);
-void _lsra_new_stack( lsradata *, stackptr , int , int, int);
-void _lsra_from_stack(lsradata *, stackptr , int , int, int);
-void lsra_usage_local(lsradata *, s4 , int , int , int , int );
+void _lt_scanlifetimes(jitdata *jd, graphdata *gd, basicblock *bptr, int);
+void lt_usage(jitdata *, s4 , int , int , int );
-void LifeOutAtBlock(lsradata *ls, graphdata *gd, int *M, int n,
- struct lifetime *lt);
-void LifeInAtStatement(lsradata *ls, graphdata *gd, int *M, int b_index,
+void lt_lifeoutatblock(lsradata *ls, graphdata *gd, int *M, int b_index,
+ struct lifetime *lt, worklist *W);
+void lt_lifeatstatement(lsradata *ls, graphdata *gd, int b_index,
+ int iindex, struct lifetime *lt, bool life_in,
+ worklist *W);
+#if 0
+void lt_lifeinatstatement(lsradata *ls, graphdata *gd, int *M, int b_index,
int iindex, struct lifetime *lt);
-void LifeOutAtStatement(lsradata *ls, graphdata *gd, int *M, int b_index,
+void lt_lifeoutatstatement(lsradata *ls, graphdata *gd, int *M, int b_index,
int iindex, struct lifetime *lt);
+#endif
#ifdef USAGE_COUNT
void lt_get_nesting(lsradata *ls, graphdata *gd, dominatordata *dd);
#endif
-void set_use_site(struct lifetime *lt, struct site *use_site) {
+void lt_set_use_site(struct lifetime *lt, struct site *use_site) {
}
-struct site *get_first_use_site(struct lifetime *lt, lt_iterator *iter) {
+struct site *lt_get_first_use_site(struct lifetime *lt, lt_iterator *iter) {
return ((*iter) = lt->use);
}
-struct site *get_next_site(lt_iterator *iter) {
+struct site *lt_get_next_site(lt_iterator *iter) {
if ((*iter) == NULL)
return NULL;
else
return ((*iter) = (*iter)->next);
}
-struct site *get_first_def_site(struct lifetime *lt, lt_iterator *iter) {
+struct site *lt_get_first_def_site(struct lifetime *lt, lt_iterator *iter) {
return ((*iter) = lt->def);
}
-bool v_is_defined_at_s(lsradata *ls, int b_index, int iindex,
+bool lt_v_is_defined_at_s(lsradata *ls, int b_index, int iindex,
struct lifetime * lt) {
struct site *def_site;
bool is_defined_at_s;
/****************************************************************************
Get Def & Use Sites
****************************************************************************/
-void scan_lifetimes(methodinfo *m, codegendata *cd, registerdata *rd,
- lsradata *ls, graphdata *gd, dominatordata *dd) {
- int i, p;
+void lt_scanlifetimes(jitdata *jd, graphdata *gd, dominatordata *dd) {
+ int i, l, p;
s4 t;
- methoddesc *md = m->parseddesc;
+ methodinfo *m;
+ lsradata *ls;
+ methoddesc *md;
+
+ ls = jd->ls;
+ m = jd->m;
+ md = m->parseddesc;
graph_DFS(ls, gd);
#if defined(LT_DEBUG_VERBOSE)
if (compileverbose) {
printf("Sorted: ");
- for (i=0; i < ls->basicblockcount; i++) printf("%3i ", ls->sorted[i]);
+ for (i=0; i < ls->basicblockcount; i++) {
+ l = ls->sorted[i];
+ if (l != -1)
+ l = ls->basicblocks[l]->nr;
+ printf("%3i(%3i) ", ls->sorted[i], l);
+ }
printf("\n");
printf("Sorted_rev: ");
for (i=0; i < ls->basicblockcount; i++)
printf("\n");
}
#endif
- if (ls->max_interfaces != -1) {
- /* init Interface Stackslot lifetimes -1.. */
- for (i = -1; i > -ls->interface_0[-ls->max_interfaces-1]-1; i--) {
- ls->lifetime[-i-1].v_index = i;
- ls->lifetime[-i-1].usagecount = 0;
- ls->lifetime[-i-1].bb_last_use = -1;
- ls->lifetime[-i-1].bb_first_def = -1;
- ls->lifetime[-i-1].local_ss = NULL;
- ls->lifetime[-i-1].savedvar = 0;
- ls->lifetime[-i-1].flags = 0;
- /* .type already set while ssa_Rename_, so we could save a */
- /* lookup table for the type information */
- }
- ls->v_index = -ls->interface_0[-ls->max_interfaces-1]-1;
- }
for(i = ls->basicblockcount - 1; i>= 0; i--)
if (ls->sorted[i] != -1)
- _scan_lifetimes(rd, ls, gd, ls->basicblocks[ls->sorted[i]]);
+ _lt_scanlifetimes(jd, gd, ls->basicblocks[ls->sorted[i]],
+ ls->sorted[i]);
/* Parameter initialisiation for locals [0 .. paramcount[ */
/* -> add local var write access at (bb=0,iindex=0) */
- for (p = 0; p < md->paramcount; p++) {
+ for (p = 0, l = 0; p < md->paramcount; p++) {
t = md->paramtypes[p].type;
- i = ls->local_0[p];
- _LT_ASSERT( i < jd->maxlocals);
+ i = jd->local_map[l * 5 + t];
+ l++;
+ if (IS_2_WORD_TYPE(t)) /* increment local counter for 2 word types */
+ l++;
+ if (i == UNUSED)
+ continue;
+ i = ls->var_0[i];
+/* _LT_ASSERT( i < jd->cd->maxlocals); */
#ifdef LT_DEBUG_VERBOSE
if (compileverbose)
printf("param %3i -> L %3i/%3i",p,i,t);
#endif
- if (rd->locals[i][t].type >= 0) {
- /* Param to Local init happens before normal Code */
-#ifdef LT_DEBUG_VERBOSE
- if (compileverbose)
- printf(" ok\n");
-#endif
- lsra_usage_local(ls, i, t, 0, 0, LSRA_STORE);
- }
+ _LT_ASSERT(t == VAR(i)->type);
+
+ /* Param to Local init happens before normal Code */
+
#ifdef LT_DEBUG_VERBOSE
- else
- if (compileverbose)
- printf(" .....\n");
+ if (compileverbose)
+ printf(" ok\n");
#endif
+ lt_usage(jd, i, 0, 0, LT_DEF);
} /* end for */
}
-bool is_simple_lt(struct lifetime *lt) {
+bool lt_is_simple_lt(struct lifetime *lt) {
lt_iterator i_def, i_use;
struct site *def, *use;
bool all_in_same_block;
- def = get_first_def_site(lt, &i_def);
- use = get_first_use_site(lt, &i_use);
+ def = lt_get_first_def_site(lt, &i_def);
+ use = lt_get_first_use_site(lt, &i_use);
all_in_same_block = true;
- for (; (all_in_same_block && (use != NULL)); use = get_next_site(&i_use)) {
+ for (; (all_in_same_block && (use != NULL));
+ use = lt_get_next_site(&i_use)) {
all_in_same_block =
(use->iindex >= 0) && (use->b_index == def->b_index);
}
lt_is_live(ls, lt, lt->def->b_index, lt->def->iindex);
/* get last use */
- use = get_first_use_site(lt, &i_use);
+ use = lt_get_first_use_site(lt, &i_use);
/* lt->bb_last_use = ls->sorted_rev[use->b_index]; */
/* lt->i_last_use = use->iindex; */
- for (; (use != NULL); use = get_next_site(&i_use))
+ for (; (use != NULL); use = lt_get_next_site(&i_use))
lt_is_live(ls, lt, use->b_index, use->iindex);
/* if (use->iindex > lt->i_last_use) */
/* lt->i_last_use = use->iindex; */
}
-#if defined(JOIN_PHI_LT)
-/******************************************************************************
-Set up data structures for a interference graphs of variables used in each phi
-function
-******************************************************************************/
-void lt_setup_phi_interference(lsradata *ls, graphdata *gd) {
- int a, b, i, j, t;
- int *stack, stack_top;
- struct igraph_lookup **lookup;
- struct igraph_lookup *tmp;
- int lookup_top, igraph_top;
- struct igraph_vars *new_var;
-
- lookup_top = igraph_top = 0;
- lookup = DMNEW(struct igraph_lookup *, ls->max_vars_with_indices*2);
- stack = DMNEW(int, ls->max_vars_with_indices);
- for(b = 0; b < ls->basicblockcount; b++) {
- for(a = 0; a < ls->max_vars; a++) {
- if (ls->phi[b][a] != NULL) {
-
-#if defined(LT_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("Phi(%3i, %3i): ", a, gd->num_pred[b]);
- }
-#endif
- stack_top = 0;
- /* loop for all vars in this phi function -> setup a interf graph */
- /* structure for it */
- for(j = 0; j < gd->num_pred[b] + 1; j++) {
- if (ls->phi[b][a][j] != ls->max_vars_with_indices) {
- /* used entry */
- stack[stack_top++] = ls->phi[b][a][j];
-#if defined(LT_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("%3i ",ls->phi[b][a][j]);
- }
-#endif
- }
- }
- _LT_ASSERT(stack_top <= ls->max_vars_with_indices);
-#if defined(LT_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("\n ");
- }
-#endif
- /* sort (insertion)*/
- /* TODO: make unique sort proc (see lsra_insertion...) */
- for (i = 1; i <= stack_top - 1; i++) {
- j = i;
- t = stack[j];
- while ((j > 0) && (stack[j-1] > t)) {
- stack[j] = stack[j-1];
- j--;
- }
- stack[j] = t;
- }
-#if defined(LT_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("Sorted: ");
- for(i=0; i < stack_top; i++)
- printf("%3i ",stack[i]);
- printf("\n");
- }
-#endif
- /* now remove duplicates */
- /* t ... new stack_top */
- /* i ... first of duplicate sequence */
- /* j ... next duplicate sequence */
- i = t = 0;
- while (i < stack_top) {
- stack[t] = stack[i];
- t++;
- for(j = i + 1; (j < stack_top)&&(stack[i]==stack[j]); j++);
- if (j == stack_top) {
- /* last duplicate entries */
- stack_top = t;
- break;
- }
- i = j;
- }
- _LT_ASSERT(stack_top <= ls->max_vars_with_indices);
-#if defined(LSRA_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("wo duplicates: ");
- for(i=0; i < stack_top; i++)
- printf("%3i ",stack[i]);
- printf("\n");
- }
-#endif
- /* setup lookuptable for vars stack[0..stack_top[ to */
- /* interference graph number & interference graph structure */
- for(i = 0; i < stack_top; i++) {
- _LT_ASSERT(lookup_top < ls->max_vars_with_indices*2);
- lookup[lookup_top] = DNEW(struct igraph_lookup);
- lookup[lookup_top]->var = stack[i]; /* var index */
- lookup[lookup_top]->igraph = igraph_top; /* igraph index */
- lookup_top++;
- }
- igraph_top++;
- }
- }
- }
- ls->igraph = DMNEW(struct igraph , igraph_top);
- ls->igraph_top = igraph_top;
- for(i = 0; i < igraph_top; i++) {
- ls->igraph[i].inter = NULL;
- ls->igraph[i].vars = NULL;
- }
-
- /* sort lookup */
-
- for (i = 1; i < lookup_top; i++) {
- j = i;
- t = lookup[j]->var;
- tmp = lookup[j];
- while ((j > 0) && (lookup[j-1]->var > t)) {
- lookup[j]=lookup[j-1];
- j--;
- }
- lookup[j] = tmp;
- }
-
- /* join igraphs for multiple vars */
- /* TODO: make this more efficient! */
- for (i = 1; i < lookup_top; i++) {
- if (lookup[i-1]->var == lookup[i]->var) {
- for(j = 0; j < lookup_top; j++)
- if (j != i)
- if (lookup[j]->igraph == lookup[i]->igraph)
- lookup[j]->igraph = lookup[i-1]->igraph;
- lookup[i]->igraph = lookup[i-1]->igraph;
- }
- }
-
- ls->igraph_lookup_top = lookup_top;
- ls->igraph_lookup = DMNEW(struct igraph_lookup *, lookup_top);
- for(i = 0; i < lookup_top; i++) {
- ls->igraph_lookup[i] = lookup[i];
- new_var = DNEW(struct igraph_vars);
- new_var->v = lookup[i]->var;
- new_var->next = ls->igraph[lookup[i]->igraph].vars;
- ls->igraph[lookup[i]->igraph].vars = new_var;
- }
-#if defined(LT_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("IGraph(%3i): ",igraph_top);
- for(i = 0; i < igraph_top; i++) {
- printf("%3i(",i);
- for(new_var = ls->igraph[i].vars; new_var != NULL; new_var = new_var->next)
- printf("%3i,",new_var->v);
- printf(") ");
- }
- printf("\n");
- for(i=0; i < lookup_top; i++)
- printf("(%3i->%3i) ",ls->igraph_lookup[i]->var, ls->igraph_lookup[i]->igraph);
- printf("\n");
- }
-#endif
-}
-
-int get_igraph_index(lsradata *ls, int var) {
- int i, i_max, i_min;
-
- if (ls->igraph_lookup == NULL)
- return -1;
-
- i_min = 0;
- i_max = ls->igraph_lookup_top;
-
- while (true) {
- i = (i_min + i_max)/2;
- if (ls->igraph_lookup[i]->var == var)
- return ls->igraph_lookup[i]->igraph;
- if ((i_max - i_min <= 1))
- return -1;
- if (var < ls->igraph_lookup[i]->var) {
- i_max = i;
- } else {
- i_min = i;
- }
- }
- /* prevent compiler warning */
- return -1;
-}
-
-void build_interference(lsradata *ls, int b_index, int iindex,
- struct lifetime *lt) {
- int igraph_index;
- struct igraph_vars *v;
- struct igraph_interference *i;
- struct lifetime *lt_i;
-
- if ((igraph_index = get_igraph_index(ls, lt->v_index)) == -1)
- return;
-
- _LT_ASSERT(ls->igraph[igraph_index].vars != NULL);
-
- for(v = ls->igraph[igraph_index].vars; v != NULL; v = v->next) {
- /* ignore interference with var itself */
- if (v->v != lt->v_index) {
- /* get lifetime of v->v */
- if (v->v >= 0) {
- lt_i = &(ls->lifetime[ls->maxlifetimes + v->v]);
- } else {
- lt_i = &(ls->lifetime[-v->v - 1]);
- }
- _LT_ASSERT(lt_i->v_index == v->v);
-
- if (v_is_defined_at_s(ls, b_index, iindex, lt_i)) {
- /* search if entry already exists */
- for(i = ls->igraph[igraph_index].inter; i != NULL; i = i->next)
- {
- if ((i->v1 == min(v->v, lt->v_index)) &&
- (i->v2 == max(v->v, lt->v_index)))
- break;
- }
- if (i == NULL) {
- i = DNEW(struct igraph_interference);
- i->v1 = min(v->v, lt->v_index);
- i->v2 = max(v->v, lt->v_index);
- i->next = ls->igraph[igraph_index].inter;
- ls->igraph[igraph_index].inter = i;
- }
- }
- }
- }
-
-}
-#endif
-
-void LifenessAnalysis(methodinfo *m, lsradata *ls, graphdata *gd) {
- int *M; /* bit_vecor of visited blocks */
- int *use; /* bit_vecor of blocks with use sites visited */
+void lt_lifeness_analysis(jitdata *jd, graphdata *gd) {
+ int *M; /* bit_vecor of visited blocks */
+ int *use; /* bit_vecor of blocks with use sites visited */
+ worklist *W; /* Worklist of Basic Blocks, where lt is life-out */
struct site *use_site, *u_site;
lt_iterator iter, iter1;
graphiterator pred_iter;
- int lt_index, i, pred, iindex, iindex1;
+ int lt_index, i, pred, iindex, iindex1, b_index;
struct lifetime *lt;
int *phi;
+/* #define MEASURE_RT */
+#ifdef MEASURE_RT
struct timespec time_start,time_end;
-#if 0
- bool measure = false;
#endif
-/* #define MEASURE_RT */
+ lsradata *ls;
+ methodinfo *m;
+
+ ls = jd->ls;
+ m = jd->m;
+
#ifdef MEASURE_RT
if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_start)) != 0) {
abort();
}
#endif
-#if 0
- if ((strcmp(m->class->name->text, "java/lang/Object")==0) &&
- (strcmp(m->name->text,"equals")==0)) {
- printf("----------------\n");
-/* measure = false; */
- }
-#endif
-#if defined(JOIN_PHI_LT)
- lt_setup_phi_interference(ls, gd);
-#endif
- M = bv_new(ls->basicblockcount);
+ M = bv_new(ls->basicblockcount);
use = bv_new(ls->basicblockcount);
+ W = wl_new(ls->basicblockcount);
#ifdef LT_DEBUG_VERBOSE
if (compileverbose)
printf("LT: %3i:", lt_index);
#endif
-#if 0
- if (measure)
- if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_start)) != 0) {
- fprintf(stderr,"could not get time: %s\n",strerror(errno));
- abort();
- }
-#endif
-
lt->savedvar = 0;
_LT_ASSERT(lt->def != NULL);
_LT_ASSERT(lt->def->next == NULL); /* SSA! */
- _LT_ASSERT(lt->use != NULL);
+/* _LT_ASSERT(lt->use != NULL); */
lt->bb_last_use = -1;
lt->bb_first_def = ls->basicblockcount;
bv_reset(M, ls->basicblockcount);
bv_reset(use, ls->basicblockcount);
+ wl_reset(W, ls->basicblockcount);
- use_site = get_first_use_site(lt, &iter);
- for (;use_site != NULL; use_site = get_next_site(&iter)) {
+ use_site = lt_get_first_use_site(lt, &iter);
+
+ /* Make unused Vars life at their Def Site */
+
+ if (use_site == NULL) {
+ lt_is_live(ls, lt, lt->def->b_index, lt->def->iindex);
+ if (lt->def->iindex < 0) {
+
+ /* def only in phi function */
+
+ lt_is_live(ls, lt, lt->def->b_index, 0);
+ }
+ }
+ for (;use_site != NULL; use_site = lt_get_next_site(&iter)) {
iindex = use_site->iindex;
if ((lt->def->b_index == use_site->b_index) &&
(iindex < 0) &&
(iindex <= lt->def->iindex)) {
- if (iindex == lt->def->iindex) /* check this */
- continue;
+
+/* bv_set_bit(use, use_site->b_index); */
/* do normal analysis */
/* there is a use in a phi function before def site */
- } else if (bv_get_bit(use, use_site->b_index)) {
+
+ }
+ else if (bv_get_bit(use, use_site->b_index)) {
continue;
- } else {
+ }
+ else {
bv_set_bit(use, use_site->b_index);
+
/* use sites of this basic block not visited till now */
- /* get use site of this bb with highest iindex (lower than def site)*/
+ /* get use site of this bb with highest iindex lower than */
+ /* def site */
+
iindex1 = -1;
u_site = use_site;
- for(iter1= iter; u_site != NULL; u_site = get_next_site(&iter1)) {
+ for(iter1= iter; u_site != NULL;
+ u_site = lt_get_next_site(&iter1)) {
if ((u_site->b_index == use_site->b_index) &&
(lt->def->b_index == use_site->b_index) &&
(u_site->iindex >= 0) &&
if (iindex1 != -1)
iindex = iindex1;
}
+
#ifdef LT_DEBUG_VERBOSE
if (compileverbose)
printf("(%3i,%3i)", use_site->b_index, iindex);
#endif
if (iindex < 0) {
+
/* use in phi function */
/* ls->phi[use_site->b_index][-use_site->iindex-1]*/
phi = ls->phi[use_site->b_index][-iindex-1];
_LT_ASSERT(phi != NULL);
-
- if (lt->v_index != phi[0]) { /* check this */
- /* ignore "Self use/def" in phi function */
-
pred = graph_get_first_predecessor(gd, use_site->b_index,
&pred_iter);
for(i = 1; (pred != -1); i++,pred =
graph_get_next(&pred_iter))
- if (lt->v_index == phi[i])
- LifeOutAtBlock(ls, gd, M, pred, lt);
- }
- } else
- LifeInAtStatement(ls, gd, M, use_site->b_index,
- iindex, lt);
+ if (lt->v_index == phi[i]) {
+
+ /* Add "Life out Basic Blocks to Worklist */
+
+ wl_add(W, pred);
+ }
+ }
+ else /* lt is live-in at this statement */
+ lt_lifeatstatement(ls, gd, use_site->b_index,
+ iindex, lt, true, W);
+ } /* for (;use_site != NULL; use_site = lt_get_next_site(&iter)) */
+
+ /* process Worklist */
+
+ while (!wl_is_empty(W)) {
+ b_index = wl_get(W);
+ lt_lifeoutatblock(ls, gd, M, b_index, lt, W);
}
+
+
#ifdef LT_DEBUG_VERBOSE
- if (compileverbose)
+ if (compileverbose)
printf("\n");
#endif
-#if 0
- if (measure) {
- if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_end)) != 0) {
- fprintf(stderr,"could not get time: %s\n",strerror(errno));
- abort();
- }
-
- {
- long diff;
- time_t atime;
+ } /* for(lt_index = 0; lt_index < ls->lifetimecount; lt_index++) */
- diff = (time_end.tv_nsec - time_start.tv_nsec) / 1000;
- atime = time_start.tv_sec;
- while (atime < time_end.tv_sec) {
- atime++;
- diff += 1000000;
- }
- printf("%8li %3i %s.%s.%s\n",diff, lt_index, m->class->name->text, m->name->text,
- m->descriptor->text);
- }
- }
-#endif
- }
#ifdef MEASURE_RT
if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_end)) != 0) {
fprintf(stderr,"could not get time: %s\n",strerror(errno));
m->descriptor->text);
}
#endif
+}
-#if defined(JOIN_PHI_LT)
-#if defined(LT_DEBUG_VERBOSE)
- if (compileverbose) {
- struct igraph_interference *inter;
- printf("Interferences: ");
- for(i = 0; i < ls->igraph_top; i++) {
- if (ls->igraph[i].inter != NULL) {
- for(inter = ls->igraph[i].inter; inter != NULL; inter = inter->next)
- printf("%3i(%3i,%3i) ",i,inter->v1,inter->v2);
- }
- }
- printf("\n");
- }
-#endif
+/*******************************************************************************
+lt_lifeatstatement
- {
- struct igraph_vars *var, *var1;
- struct igraph_interference *inter;
- struct lifetime *lt1, *lt2;
- struct stackslot *ss;
- struct site *s;
- int j, k, l;
- instruction *iptr;
+
+IN: lsradata *ls pointer to worklist created with wl_new
+ graphdata *gd
+ int b_index Basic block index of instruction
+ int iindex index of instruction in Basic Block
+ struct lifetime *lt Pointer to lifetime structure
+ bool life_in TRUE lifetime lt is life 'into' that instruction
+ FALSE lifetime lt is life 'out' of that instruction
+
+IN/OUT: worklist *W Worklist of Basic Blocks, where lt is life-out
+*******************************************************************************/
+void lt_lifeatstatement(lsradata *ls, graphdata *gd, int b_index,
+ int iindex, struct lifetime *lt, bool life_in,
+ worklist *W) {
+
+ int prev_iindex; /* Statement before iindex */
int pred;
- graphiterator iter;
+ graphiterator pred_iter;
+ instruction *iptr;
- /* join phi arguments that do not interfere */
- printf("this should not be seen \n");
- for(i = 0; i < ls->igraph_top; i++) {
- if (ls->igraph[i].inter == NULL) {
- lt1 = lt2 = NULL;
- for(var = ls->igraph[i].vars; var != NULL; var = var->next) {
- if (lt1 == NULL) {
- if (var->v >= 0) {
- lt1 = &(ls->lifetime[ls->maxlifetimes + var->v]);
- } else {
- lt1 = &(ls->lifetime[-var->v - 1]);
- }
- _LT_ASSERT(lt1->v_index == var->v);
- continue;
- } else {
- if (var->v >= 0) {
- lt2 = &(ls->lifetime[ls->maxlifetimes + var->v]);
- } else {
- lt2 = &(ls->lifetime[-var->v - 1]);
- }
- _LT_ASSERT(lt2->v_index == var->v);
- }
+ while (true) {
+ if (!life_in) {
+#ifdef LT_DEBUG_VERBOSE
+ if ((compileverbose) && (iindex >= 0))
+ printf("LO@ST: vi %3i bi %3i ii %3i\n",
+ lt->v_index, b_index, iindex);
+#endif
- if ((lt1->v_index < 0) && (lt2->v_index >=0)) {
- /* swap lt1 and lt2 - cannot join Stackslotlifetime */
- /* into Localvar lifetimes */
+ /* lt->v_index is life-out at statement at (b_index,iindex) */
- lt = lt1;
- lt1 = lt2;
- lt2 = lt;
- }
+ /* Once a interference graph is needed, add here an edge (v,w) */
+ /* to the ig, for each variable w defined at this instruction */
+ /* except v=lt->v_index */
- if ((lt1->v_index >=0) && (lt2->v_index >=0)) {
- for(s = lt2->def; s != NULL; s = s->next) {
- if ((s->b_index == 0) && (s->iindex ==0)) {
- /* swap lt1 and lt2 - lt2 is initialized by a param*/
+ if (!lt_v_is_defined_at_s(ls, b_index, iindex, lt)) {
- _LT_ASSERT((lt1->def->b_index != 0)
- || (lt1->def->iindex !=0));
- lt = lt1;
- lt1 = lt2;
- lt2 = lt;
- break;
- }
- }
- }
+ /* v is life in at out of statement -> check if the SAVEDVAR */
+ /* flag is needed to be set */
- /* already joined */
- if ((lt2->type == -1) || (lt1 == lt2))
- continue;
-#if defined(LT_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("Joining %3i into %3i\n",lt2->v_index, lt1->v_index);
- }
-#endif
+ if ((iindex >= 0) && (b_index != 0)) {
- /* copy local_ss from lt2 to lt1 & rename local_ss->s->varnum */
- while (lt2->local_ss != NULL) {
- if (lt1->v_index >= 0) {
- lt2->local_ss->s->varkind = LOCALVAR;
- }
- /* other direction not possible! (LOCALVAR->TEMPVAR) */
- /* see 'if' above */
- lt2->local_ss->s->varnum = lt1->v_index;
-
- ss = lt1->local_ss;
- lt1->local_ss = lt2->local_ss;
- lt2->local_ss = lt2->local_ss->next;
- lt1->local_ss->next = ss;
- }
+ /* real ICMD, no phi-function, no param initialisation */
- /* look at the use sites */
- for(s = lt2->use; s != NULL; s = s->next) {
- if (s->iindex < 0) {
- /* use in phi function -> change */
- pred=graph_get_first_predecessor(gd, s->b_index, &iter);
- for (j = 1; pred != -1; j++,
- pred = graph_get_next(&iter)) {
- if (ls->phi[s->b_index][-s->iindex-1][j] ==
- lt2->v_index) {
- ls->phi[s->b_index][-s->iindex-1][j]
- = lt1->v_index;
- /* change in appropriate phi_move, too */
- for(k=0; k<ls->num_phi_moves[pred]; k++) {
- if (ls->phi_moves[pred][k][1] ==
- lt2->v_index) {
- ls->phi_moves[pred][k][1]=lt1->v_index;
- }
-/* if (ls->phi_moves[pred][k][0] == */
-/* lt2->v_index) { */
-/* ls->phi_moves[pred][k][0]=lt1->v_index; */
-/* } */
- }
- }
- }
- /* change in appropriate phi_move, too */
- } else {
- if (lt2->v_index >= 0) {
- /* lt1&<2 are LOCALVAR, XSTORE,IINC and XLOAD */
- /* have to be changed */
- iptr = ls->basicblocks[s->b_index]->iinstr +
- s->iindex;
- if (iptr != NULL) {
- /* no edge splitting block from SSA */
- switch(iptr->opc) {
- case ICMD_ILOAD:
- case ICMD_LLOAD:
- case ICMD_FLOAD:
- case ICMD_DLOAD:
- case ICMD_ALOAD:/* iptr->op1 == USE */
- case ICMD_ISTORE:
- case ICMD_LSTORE:
- case ICMD_FSTORE:
- case ICMD_DSTORE:
- case ICMD_ASTORE:
- case ICMD_IINC: /* iptr->op1 == USE */
- if (iptr->op1 == lt2->v_index)
- iptr->op1 = lt1->v_index;
- break;
- /* default: */
- /* could be in another than the top stackslot */
- /* too! */
- /* _LT_ASSERT((iptr-1)->dst->varnum == */
- /* lt1->v_index); */
- }
- }
- }
- /* uses in stackslots are already changed above by */
- /* renameing and copying of local_ss */
- }
- } /* for(s = lt2->use; s != NULL; s = s->next) */
- if (lt2->v_index >= 0) {
- /* change def site */
- _LT_ASSERT(lt2->def != NULL);
- /* no SSA Anymore -> cyle through all def sites */
- /* _LT_ASSERT(lt2->def->next == NULL); */
-
- for(s = lt2->def; s != NULL; s = s->next) {
- if (s->iindex < 0) {
- /* change phi */
- if (ls->phi[s->b_index][-s->iindex-1][0] == lt2->v_index)
- ls->phi[s->b_index][-s->iindex-1][0] = lt1->v_index;
- pred=graph_get_first_predecessor(gd, s->b_index, &iter);
- for (; pred != -1; pred = graph_get_next(&iter)) {
- /* change in appropriate phi_move, too */
- for(k=0; k<ls->num_phi_moves[pred]; k++) {
- if (ls->phi_moves[pred][k][0] ==
- lt2->v_index) {
- ls->phi_moves[pred][k][0]=lt1->v_index;
- }
- }
- }
- } else {
- /* change ICMD */
-
- iptr = ls->basicblocks[s->b_index]->iinstr
- + s->iindex;
- switch(iptr->opc) {
- case ICMD_ILOAD:
- case ICMD_LLOAD:
- case ICMD_FLOAD:
- case ICMD_DLOAD:
- case ICMD_ALOAD:
- case ICMD_ISTORE:
- case ICMD_LSTORE:
- case ICMD_FSTORE:
- case ICMD_DSTORE:
- case ICMD_ASTORE: /* iptr->op1 == DEF */
- if(iptr->op1 == lt2->v_index)
- iptr->op1 = lt1->v_index;
- break;
- case ICMD_IINC: /* iptr->val._i.op1_t == DEF */
- if (iptr->val._i.op1_t == lt2->v_index)
- iptr->val._i.op1_t = lt1->v_index;
- break;
- /* default: */
- /* could be in another than the top stackslot */
- /* too! */
- /* _LT_ASSERT((iptr->dst->varnum == lt1->v_index)); */
- }
- }
- }
- }
-
- /* combine def sites (SSA is dead now)*/
- _LT_ASSERT(lt2->def != NULL);
- for(s = lt2->def; s->next != NULL; s = s->next);
- s->next = lt1->def;
- lt1->def = lt2->def;
-
- /* combine use sites */
- _LT_ASSERT(lt2->use != NULL);
- for(s = lt2->use; s->next != NULL; s = s->next);
- s->next = lt1->use;
- lt1->use = lt2->use;
-
- /* combine first_def and last_use */
- if (lt1->bb_first_def == lt2->bb_first_def) {
- lt1->i_first_def = min(lt1->i_first_def, lt2->i_first_def);
- } else if (lt1->bb_first_def > lt2->bb_first_def) {
- lt1->bb_first_def = lt2->bb_first_def;
- lt1->i_first_def = lt2->i_first_def;
- }
- if (lt1->bb_last_use == lt2->bb_last_use) {
- lt1->i_last_use = max(lt1->i_last_use, lt2->i_last_use);
- } else if (lt1->bb_last_use < lt2->bb_last_use) {
- lt1->bb_last_use = lt2->bb_last_use;
- lt1->i_last_use = lt2->i_last_use;
+ _LT_ASSERT(ls->basicblocks[b_index]->iinstr != NULL);
+ iptr = ls->basicblocks[b_index]->iinstr + iindex;
+ if (icmd_table[iptr->opc].flags & ICMDTABLE_CALLS)
+ lt->savedvar = SAVEDVAR;
}
- /* combine savedvar flags */
- lt1->savedvar |= lt2->savedvar;
- _LT_ASSERT(lt1->type == lt2->type);
- lt2->type = -1;
- /* change the var in all future references of ls->igraph */
- /* TODO: do something against this!! */
-/* for(j = i + 1; j < ls->igraph_top; j++) { */
-/* if (ls->igraph[j].inter == NULL) { */
-/* for(var1 = ls->igraph[j].vars; var1 != NULL; */
-/* var1 = var1->next) { */
-/* if (var1->v == lt2->v_index) */
-/* var1->v = lt1->v_index; */
-/* } */
-/* } */
-#if 0
- /* not needed by now, since only for phi functions */
- /* with absolutely no interference is checked */
- else {
- inter = ls->igraph[j].inter;
- for(;inter != NULL; inter = inter->next) {
- if (inter->v1 == lt2->v_index)
- inter->v1 = lt1->v_index;
- if (inter->v2 == lt2->v_index)
- inter->v2 = lt1->v_index;
- }
- }
-#endif
-/* } */
-
- /* look through all phi functions */
- for(j = 0; j < ls->basicblockcount; j++) {
- for(k = 0; k < ls->max_vars; k++) {
- if (ls->phi[j][k] != NULL) {
- if (ls->phi[j][k][0] == lt2->v_index)
- ls->phi[j][k][0] = lt1->v_index;
- for (l = 1; l < graph_get_num_predecessor(gd, j); l++) {
- if (ls->phi[j][k][l] == lt2->v_index)
- ls->phi[j][k][l] = lt1->v_index;
- }
- }
- }
- /* change in phi move, too */
- for(k = 0; k < ls->num_phi_moves[j]; k++) {
- if (ls->phi_moves[j][k][1] == lt2->v_index)
- ls->phi_moves[j][k][1] = lt1->v_index;
- if (ls->phi_moves[j][k][0] == lt2->v_index)
- ls->phi_moves[j][k][0] = lt1->v_index;
- }
- }
- } /* for(var = ls->igraph[i].vars; var != NULL; var = var->next) */
- } /* if (ls->igraph[i].inter == NULL) */
- } /* for(i = 0; i < ls->igraph_top; i++) */
- }
+ /* lt stays life-in at statement */
+
+ life_in = true;
+ } else {
+
+ /* print LO verbose message only for phi functions, which */
+ /* define this var */
+
+#ifdef LT_DEBUG_VERBOSE
+ if ((compileverbose) && (iindex < 0))
+ printf("LO@ST: vi %3i bi %3i ii %3i\n",
+ lt->v_index, b_index, iindex);
+ if ((compileverbose))
+ printf("--> definition\n");
#endif
-}
-void LifeOutAtBlock(lsradata *ls, graphdata *gd, int *M, int n,
- struct lifetime *lt) {
- /* lt->v_index is life at Block n */
- if (!bv_get_bit(M,n)) { /* n no Element of M */
- bv_set_bit(M,n);
+ lt_is_live(ls, lt, b_index, iindex);
- /* lt->v_index is life at last Statement of n */
- if (n != 0) {
- int i;
- i = ls->basicblocks[n]->icount - 1;
- for (;((i>0) && (ls->basicblocks[n]->iinstr+i == ICMD_NOP)); i--);
- LifeOutAtStatement(ls, gd, M, n, i,lt);
+ /* Stop - lt is defined and not life before this instruction */
+
+ break;
+ }
}
- else
- LifeOutAtStatement(ls, gd, M, n, 0, lt);
- }
-}
-void LifeInAtStatement(lsradata *ls, graphdata *gd, int *M, int b_index,
- int iindex, struct lifetime *lt) {
- /* lt->v_index is live-in at s */
- int prev_iindex; /* Statement before iindex */
- int pred;
- graphiterator pred_iter;
+ if (life_in) {
+
+ /* lt->v_index is live-in at statement (b_index,iindex) */
- lt_is_live(ls, lt, b_index, iindex);
-
- prev_iindex = iindex - 1;
- if (prev_iindex < 0)
- /* look through phi functions */
- for(; prev_iindex > -ls->max_vars-1;
- prev_iindex--)
- if (ls->phi[b_index][-prev_iindex-1] != NULL)
- break;
+#ifdef LT_DEBUG_VERBOSE
+ if ((compileverbose) && (iindex >= 0))
+ printf("LI@ST: vi %3i bi %3i ii %3i\n",
+ lt->v_index, b_index, iindex);
+#endif
- if (iindex == -ls->max_vars-1) {
- /* iindex is the first statement of b_index */
- /* Statements -ls->max_vars-1 .. -1 are possible phi functions */
- /* lt->v_index is live-in at b_index */
-
- pred = graph_get_first_predecessor(gd, b_index, &pred_iter);
- for(; pred != -1; pred = graph_get_next(&pred_iter))
- LifeOutAtBlock(ls, gd, M, pred, lt);
- } else
- LifeOutAtStatement(ls, gd, M, b_index, prev_iindex, lt);
-}
+ lt_is_live(ls, lt, b_index, iindex);
-void LifeOutAtStatement(lsradata *ls, graphdata *gd, int *M, int b_index,
- int iindex, struct lifetime *lt) {
- instruction *iptr;
- int igraph_index;
- int var;
- /* lt->v_index is life-out at s */
- /* for each variable w defined at s except v=lt->v_index, add a edge */
- /* (v,w) to the interference graph, once one is needed */
+ if (iindex == -ls->varcount-1) {
-#if defined(JOIN_PHI_LT)
- /* Build interference Graph for variables involved in phi functions */
- /* it is essential, that these variables get merged, if possible! */
- build_interference(ls, b_index, iindex, lt);
+#ifdef LT_DEBUG_VERBOSE
+ if ((compileverbose))
+ printf("LI@ST: vi %3i bi %3i ii %3i\n",
+ lt->v_index, b_index, iindex);
#endif
- if (!v_is_defined_at_s(ls, b_index, iindex, lt)) {
- /* v is life in at out of statement -> check if the SAVEDVAR */
- /* flag is needed to be set */
- if ((iindex >= 0) && (b_index != 0)) {
- /* real ICMD */
- _LT_ASSERT(ls->basicblocks[b_index]->iinstr != NULL);
- iptr = ls->basicblocks[b_index]->iinstr + iindex;
- if (icmd_table[iptr->opc].flags & ICMDTABLE_CALLS)
- lt->savedvar = SAVEDVAR;
- }
- LifeInAtStatement(ls, gd, M, b_index, iindex, lt);
- } else
- lt_is_live(ls, lt, b_index, iindex);
-}
+ /* iindex is the first statement of b_index */
+ /* Statements -ls->max_vars-1 .. -1 are possible phi functions*/
+ /* lt->v_index is live-in at b_index */
+
+ pred = graph_get_first_predecessor(gd, b_index, &pred_iter);
-struct stackslot *lsra_make_ss(stackptr s, int bb_index)
-{
- struct stackslot *ss;
+ /* Add "Life out Basic Blocks to Worklist */
- ss=DNEW(struct stackslot);
- ss->bb=bb_index;
- ss->s=s;
- return ss;
-}
+ for(; pred != -1; pred = graph_get_next(&pred_iter))
+ wl_add(W, pred);
-void lsra_add_ss(struct lifetime *lt, stackptr s) {
- struct stackslot *ss;
- bool insert_s;
- /* Stackslot noch nicht eingetragen? */
+ /* Stop here - beginning of Basic Block reached */
- insert_s = true;
+ break;
+ } else {
- for (ss = lt->local_ss; (!insert_s) && (ss != NULL); ss = ss->next)
- insert_s = (ss->s == s);
-
+ prev_iindex = iindex - 1;
+ if (prev_iindex < 0)
- /* local_ss == NULL -> stack lt was set in ssa -> create Stack entry */
- if ((lt->local_ss == NULL) || (insert_s)) {
- ss = DNEW(struct stackslot);
- ss->s = s;
- ss->s->varnum = lt->v_index;
- ss->next = lt->local_ss;
- lt->local_ss = ss;
- if (s != NULL) lt->savedvar |= s->flags & SAVEDVAR;
- if (s != NULL) lt->type = s->type;
- }
+ /* look through phi functions */
+
+ for(; prev_iindex > -ls->varcount-1; prev_iindex--)
+ if (ls->phi[b_index][-prev_iindex-1] != NULL)
+ break;
+
+ /* lt is live out at instruction prev_iindex */
+
+ iindex = prev_iindex;
+ life_in = false;
+ }
+ }
+ }
}
-void move_stackslots(struct lifetime *from, struct lifetime *to) {
- struct stackslot *ss;
-
- if (from->local_ss == NULL)
- /* nothing to move */
- return;
- for(ss = from->local_ss; ss->next != NULL; ss = ss->next);
+void lt_lifeoutatblock(lsradata *ls, graphdata *gd, int *M, int b_index,
+ struct lifetime *lt, worklist *W) {
+
+#if defined(LT_DEBUG_VERBOSE)
+ if (compileverbose) {
+ printf("V %3i LO at BB %3i\n",lt->v_index, b_index);
+ }
+#endif
+
+ /* lt->v_index is life out of Block b_index */
+ if (!bv_get_bit(M, b_index)) { /* BB b_index not visited till now */
+ bv_set_bit(M, b_index);
- ss->next = to->local_ss;
- to->local_ss = from->local_ss;
- from->local_ss = NULL;
+ /* lt->v_index is life out of last Statement of b_index */
+
+ if (b_index != 0) {
+ int i;
+ i = ls->basicblocks[b_index]->icount - 1;
+ for (;((i>0) && (ls->basicblocks[b_index]->iinstr+i == ICMD_NOP));
+ i--);
+ lt_lifeatstatement(ls, gd, b_index, i, lt, false, W);
+ }
+ else
+ lt_lifeatstatement(ls, gd, b_index, 0, lt, false, W);
+ }
}
-void move_use_sites(struct lifetime *from, struct lifetime *to) {
+
+void lt_move_use_sites(struct lifetime *from, struct lifetime *to) {
struct site *s;
_LT_ASSERT(from->use != NULL);
from->use = NULL;
}
-void add_use_site(struct lifetime *lt, int block, int iindex) {
+void lt_add_use_site(struct lifetime *lt, int block, int iindex) {
struct site *n;
n = DNEW(struct site);
/* CFG is analysed from the end to the start -> so first found use site */
/* is the last use of the Local Var */
+
if (lt->last_use == NULL)
lt->last_use = n;
}
-void remove_use_site(struct lifetime *lt, int block, int iindex) {
+void lt_remove_use_site(struct lifetime *lt, int block, int iindex) {
struct site *n;
/* check lt->use itself */
+
if ((lt->use->b_index == block) && (lt->use->iindex == iindex)) {
/* found */
lt->use = lt->use->next;
} else {
+
/* look through list */
+
for (n = lt->use; (n->next != NULL) && ((n->next->b_index != block) ||
(n->next->iindex != iindex)); n = n->next);
+
/* assert, that lt was found */
+
_LT_ASSERT(n->next != NULL);
_LT_ASSERT(n->next->b_index == block);
_LT_ASSERT(n->next->iindex == iindex);
}
}
-void add_def_site(struct lifetime *lt, int block, int iindex) {
+void lt_add_def_site(struct lifetime *lt, int block, int iindex) {
struct site *n;
/* SSA <-> only one definition per lifetime! */
+
_LT_ASSERT(lt->def == NULL);
n = DNEW(struct site);
n->b_index = block;
lt->def = n;
}
-struct lifetime *get_ss_lifetime(lsradata *ls, stackptr s) {
- struct lifetime *n;
-
- if (s->varnum >= 0) { /* new stackslot lifetime */
- if (-ls->v_index - 1 >= ls->maxlifetimes) {
- printf("%i %i\n", -ls->v_index - 1, ls->maxlifetimes);
- }
- _LT_ASSERT(-ls->v_index - 1 < ls->maxlifetimes);
-
- n = &(ls->lifetime[-ls->v_index - 1]);
- n->type = s->type;
- n->v_index = ls->v_index--;
- n->usagecount = 0;
-
- n->bb_last_use = -1;
- n->bb_first_def = -1;
- n->local_ss = NULL;
- n->savedvar = 0;
- n->flags = 0;
-
- n->use = NULL;
- n->def = NULL;
- n->last_use = NULL;
- } else {
- _LT_ASSERT(-s->varnum - 1 < ls->maxlifetimes);
- n = &(ls->lifetime[-s->varnum - 1]);
- }
-
- lsra_add_ss( n, s);
- return n;
-}
-
-#define lsra_new_stack(ls, s, block, instr) \
- if ((s)->varkind != ARGVAR) _lsra_new_stack(ls, s, block, instr, LSRA_STORE)
-void _lsra_new_stack(lsradata *ls, stackptr s, int block, int instr, int store)
-{
- struct lifetime *n;
-
- if (s->varkind == LOCALVAR) {
-/* _LT_ASSERT(0); */
- lsra_usage_local(ls, s->varnum, s->type, block, instr, LSRA_LOAD);
- } else {
-
-
- n=get_ss_lifetime( ls, s );
- if (store == LSRA_STORE) {
- /* for LSRA_BB_[IN|OUT] do not add a def site, just add s to */
- /* local_ss */
- add_def_site(n, block, instr);
- }
- }
-}
-
-#define lsra_from_stack(ls, s, block, instr) \
- if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_LOAD)
-#define lsra_pop_from_stack(ls, s, block, instr) \
- if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_POP)
-void _lsra_from_stack(lsradata *ls, stackptr s, int block, int instr, int store)
-{
- struct lifetime *n;
-
- if (s->varkind == LOCALVAR) {
-/* _LT_ASSERT(0); */
- lsra_usage_local(ls, s->varnum, s->type, block, instr, LSRA_LOAD);
- } else /* if (s->varkind != ARGVAR) */ {
- if (s->varkind == STACKVAR ) {
-/* _LT_ASSERT(0); */
- printf("---------STACKVAR left over! \n");
- /* No STACKVARS possible with lsra! */
- s->varkind = TEMPVAR;
- }
- }
-
- n=get_ss_lifetime( ls, s );
-
- /* LSRA_POP -> invalidate Stackslot ?! */
-#ifdef USAGE_COUNT
- n->usagecount += ls->nesting[block];
-#endif
-
- add_use_site(n, block, instr);
-
-}
-
-void lsra_usage_local(lsradata *ls, s4 v_index, int type, int block, int instr,
+void lt_usage(jitdata *jd,s4 v_index, int block, int instr,
int store)
{
struct lifetime *n;
+ lsradata *ls;
+
+ ls = jd->ls;
- n = &(ls->lifetime[ls->maxlifetimes + v_index]);
+ n = ls->lifetime + v_index;
if (n->type == -1) { /* new local lifetime */
- n->local_ss=NULL;
+ _LT_ASSERT(0);
n->v_index=v_index;
- n->type=type;
+ n->type=VAR(v_index)->type;
+ /* TODO: check!!!! */
+ /* All var are SAVEDVARS or this gets reset afterwards???? */
n->savedvar = SAVEDVAR;
n->flags = 0;
n->usagecount = 0;
n->def = NULL;
n->last_use = NULL;
}
- _LT_ASSERT(type == n->type);
+ _LT_ASSERT(VAR(v_index)->type == n->type);
/* add access at (block, instr) to instruction list */
/* remember last USE, so only write, if USE Field is undefined (==-1) */
/* count store as use, too -> defined and not used vars would overwrite */
/* other vars */
- if (store == LSRA_LOAD) {
+
+ if (store == LT_USE) {
#ifdef USAGE_COUNT
n->usagecount += ls->nesting[block];
#endif
- add_use_site(n, block, instr);
+ lt_add_use_site(n, block, instr);
}
- if (store == LSRA_STORE) {
- add_def_site(n, block, instr);
+ if (store == LT_DEF) {
+ lt_add_def_site(n, block, instr);
}
}
use sites: dead code elemination, LifenessAnalysis
def sites: dead code elemination
***************************************************************************/
-void _scan_lifetimes(registerdata *rd, lsradata *ls, graphdata *gd,
- basicblock *bptr)
+void _lt_scanlifetimes(jitdata *jd, graphdata *gd, basicblock *bptr,
+ int b_index)
{
/* methodinfo *lm; */
builtintable_entry *bte;
methoddesc *md;
int i, j, t, v;
- int opcode;
- int iindex, b_index;
- stackptr src;
- stackptr dst;
+ int iindex/*, b_index*/;
instruction *iptr;
-
- struct lifetime *lt;
+ s4 *argp;
+
+ lsradata *ls;
+
+ ls = jd->ls;
+#ifdef LT_DEBUG_VERBOSE
+ if (compileverbose)
+ printf("_lt_scanlifetimes: BB %3i flags %3i\n", b_index, bptr->flags);
+#endif
if (bptr->flags >= BBREACHED) {
- b_index = bptr->nr;
+/* b_index = bptr->nr; */
/* get instruction count for BB */
+
iindex = bptr->icount - 1;
- /* regard not setup new BB with maybee just in and outstack */
- if (iindex < 0) iindex = 0;
+
+ /* regard not setup new BB with maybe just in and outstack */
+
+ if (iindex < 0)
+ iindex = 0;
/* Regard phi_functions (Definition of target, Use of source) */
- for(i = 0; i < ls->max_vars; i++) {
+
+ for(i = 0; i < ls->ssavarcount; i++) {
if (ls->phi[b_index][i] != NULL) {
/* Phi Function for var i at b_index exists */
v = ls->phi[b_index][i][0];
- _LT_ASSERT( v != ls->max_vars_with_indices);
- if (v >= 0) {
- /* Local Var */
- for(t = 0;(t < 5) && (rd->locals[v][t].type==-1); t++);
- _LT_ASSERT(t != 5);
- /* Add definition of target add - phi index -1*/
- lsra_usage_local(ls, v, t, b_index, -i-1,
- LSRA_STORE);
- /* Add Use of sources */
- for (j = 1; j <= graph_get_num_predecessor(gd, b_index);
- j++) {
- if (ls->phi[b_index][i][j] != ls->max_vars_with_indices)
- lsra_usage_local(ls, ls->phi[b_index][i][j], t,
- b_index, -i-1, LSRA_LOAD);
- }
- } else {
- /* Interface Stackslot */
- /* Add definition of target */
- lt = &(ls->lifetime[-v-1]);
- add_def_site(lt, b_index, -i-1);
- /* add use of sources */
- for (j = 1; j <= graph_get_num_predecessor(gd, b_index);
- j++) {
- if (ls->phi[b_index][i][j] != ls->max_vars_with_indices)
- {
- lt = &(ls->lifetime[-ls->phi[b_index][i][j]-1]);
- add_use_site(lt, b_index, -i-1);
- }
- }
+ _LT_ASSERT( v != ls->varcount_with_indices);
+ t = VAR(i)->type;
+
+ /* Add definition of target add - phi index -1*/
+#ifdef LT_DEBUG_VERBOSE
+ if (compileverbose)
+ printf("_lt_scanlifetimes: phi_def: v: %3i\n i: %3i\n",
+ v, -i-1);
+#endif
+ lt_usage(jd, v, b_index, -i-1, LT_DEF);
+
+ /* Add Use of sources */
+
+ for (j = 1; j <= graph_get_num_predecessor(gd, b_index); j++) {
+ if (ls->phi[b_index][i][j] != ls->varcount_with_indices)
+ if (ls->phi[b_index][i][j] != UNUSED)
+ lt_usage(jd, ls->phi[b_index][i][j], b_index,
+ -i-1, LT_USE);
}
}
}
- src = bptr->instack;
- if (bptr->type != BBTYPE_STD) {
-#ifdef LT_DEBUG_CHECK
- if (src == NULL) {
- log_text("No Incoming Stackslot for Exception/Subroutine BB\n");
- _LT_ASSERT(0);
- }
-#endif
- _LT_ASSERT(src != NULL);
- lsra_new_stack(ls, src, b_index, 0);
- if (src->varkind == STACKVAR)
- src->varkind = TEMPVAR;
- src = src->prev;
- }
- for (;src != NULL; src=src->prev) {
- /* no ARGVAR possible at BB Boundaries with LSRA! */
- /* -> change to TEMPVAR */
-
- if (src->varkind == ARGVAR ) {
- src->varkind = TEMPVAR;
- /* On Architectures with own return registers a return */
- /* stackslot is marked as varkind=ARGVAR with varnum=-1 */
- /* but for lsra a varkind==TEMPVAR, varnum=-1 would mean, */
- /* that already a lifetime was allocated! */
- if (src->varnum < 0) src->varnum = 0;
- }
- else if (src->varkind == LOCALVAR )
- /* only allowed for topmost ss at sbr or exh entries! */
- { log_text("LOCALVAR at basicblock instack\n"); exit(1); }
- else {
- /* no Interfaces (STACKVAR) at BB Boundaries with LSRA! */
- /* -> change to TEMPVAR */
- if (src->varkind == STACKVAR )
- src->varkind = TEMPVAR;
-/* _lsra_new_stack(ls, src, b_index, 0, LSRA_BB_IN); */
- _lsra_from_stack(ls, src, b_index, 0, LSRA_BB_OUT);
- }
- }
- /* Should not be necessary to check out stackslots, too */
- /* either they are identical to the instacks or handled */
- /* by their phi functions */
- src = bptr->outstack;
- for (;src != NULL; src=src->prev) {
- if (src->varkind == ARGVAR )
- { log_text("ARGVAR at basicblock outstack\n"); exit(1); }
- else if (src->varkind == LOCALVAR )
- { log_text("LOCALVAR at basicblock outstack\n"); exit(1); }
- else {
- /* no Interfaces at BB Boundaries with LSRA! */
- /* -> change to TEMPVAR */
- if (src->varkind == STACKVAR )
- src->varkind = TEMPVAR;
-/* _lsra_from_stack(ls, src, b_index, iindex, LSRA_BB_OUT); */
- }
- }
if (bptr->iinstr != NULL) {
/* set iptr to last instruction of BB */
iindex = -1;
for (;iindex >= 0; iindex--, iptr--) {
- /* Get source and destination Stack for the current */
- /* instruction. Destination stack is available as iptr->dst */
- dst = iptr->dst;
- /* source stack is either the destination stack of the previos*/
- /* instruction, or the basicblock instack for the */
- /* first instruction */
- if (iindex) /* != 0 is > 0 here, since iindex ist always >= 0 */
- src=(iptr-1)->dst;
- else
- src=bptr->instack;
-
- opcode = iptr->opc;
- switch (opcode) {
-
- /* pop 0 push 0 */
- case ICMD_RET:
- /* local read (return adress) */
- lsra_usage_local(ls, iptr->op1, TYPE_ADR, b_index, iindex,
- LSRA_LOAD);
- break;
- case ICMD_NOP:
-/* case ICMD_ELSE_ICONST: */
- case ICMD_CHECKNULL:
- case ICMD_JSR:
- case ICMD_RETURN:
- case ICMD_GOTO:
- case ICMD_PUTSTATICCONST:
- case ICMD_INLINE_START:
- case ICMD_INLINE_END:
- case ICMD_INLINE_GOTO:
- break;
-
- case ICMD_IINC:
- /* local = local+<const> */
- lsra_usage_local(ls, iptr->op1, TYPE_INT, b_index, iindex,
- LSRA_LOAD);
- lsra_usage_local(ls, iptr->val._i.op1_t, TYPE_INT, b_index,
- iindex, LSRA_STORE);
- break;
+ i = UNUSED;
+ v = UNUSED;
- /* pop 0 push 1 const: const->stack */
- case ICMD_ICONST:
- case ICMD_LCONST:
- case ICMD_FCONST:
- case ICMD_DCONST:
- case ICMD_ACONST:
- /* new stack slot */
- lsra_new_stack(ls, dst, b_index, iindex);
- break;
-
- /* pop 0 push 1 load: local->stack */
- case ICMD_ILOAD:
- case ICMD_LLOAD:
- case ICMD_FLOAD:
- case ICMD_DLOAD:
- case ICMD_ALOAD:
- if (dst->varkind != LOCALVAR) {
- /* local->value on stack */
- lsra_usage_local(ls, iptr->op1, opcode - ICMD_ILOAD,
- b_index, iindex, LSRA_LOAD);
- lsra_new_stack(ls, dst, b_index, iindex);
- } else /* if (dst->varnum != iptr->op1) */ {
- /* local -> local */
- lsra_usage_local(ls, iptr->op1, opcode - ICMD_ILOAD,
- b_index, iindex,LSRA_LOAD);
- lsra_usage_local(ls, dst->varnum, opcode - ICMD_ILOAD,
- b_index, iindex, LSRA_STORE);
- }
-
- break;
-
- /* pop 2 push 1 */
- /* Stack(arrayref,index)->stack */
- case ICMD_IALOAD:
- case ICMD_LALOAD:
- case ICMD_FALOAD:
- case ICMD_DALOAD:
- case ICMD_AALOAD:
-
- case ICMD_BALOAD:
- case ICMD_CALOAD:
- case ICMD_SALOAD:
- /* stack->index */
- lsra_from_stack(ls, src, b_index, iindex);
- /* stack->arrayref */
- lsra_from_stack(ls, src->prev, b_index, iindex);
- /* arrayref[index]->stack */
- lsra_new_stack(ls, dst, b_index, iindex);
- break;
-
- /* pop 3 push 0 */
- /* stack(arrayref,index,value)->arrayref[index]=value */
- case ICMD_IASTORE:
- case ICMD_LASTORE:
- case ICMD_FASTORE:
- case ICMD_DASTORE:
- case ICMD_AASTORE:
-
- case ICMD_BASTORE:
- case ICMD_CASTORE:
- case ICMD_SASTORE:
-
- lsra_from_stack(ls, src,b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
- lsra_from_stack(ls, src->prev->prev, b_index, iindex);
- break;
-
- /* pop 1 push 0 store: stack -> local */
- case ICMD_ISTORE:
- case ICMD_LSTORE:
- case ICMD_FSTORE:
- case ICMD_DSTORE:
- case ICMD_ASTORE:
- if (src->varkind != LOCALVAR) {
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_usage_local(ls, iptr->op1, opcode-ICMD_ISTORE,
- b_index, iindex, LSRA_STORE);
- } else /* if (src->varnum != iptr->op1) */ {
- lsra_usage_local(ls, iptr->op1, opcode-ICMD_ISTORE,
- b_index, iindex, LSRA_STORE);
- lsra_usage_local(ls, src->varnum, opcode-ICMD_ISTORE,
- b_index, iindex, LSRA_LOAD);
- }
- break;
+ if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE)
+ v = iptr->dst.varindex;
- /* pop 1 push 0 */
- case ICMD_POP: /* throw away a stackslot */
- /* TODO: check if used anyway (DUP...) and change codegen */
- /* to ignore this stackslot */
-#if 0
- lsra_pop_from_stack(ls, src, b_index, iindex);
-#endif
- break;
-
- /* pop 1 push 0 */
- case ICMD_IRETURN:
- case ICMD_LRETURN:
- case ICMD_FRETURN:
- case ICMD_DRETURN:
- case ICMD_ARETURN: /* stack(value) -> [empty] */
-
- case ICMD_ATHROW: /* stack(objref) -> undefined */
-
- case ICMD_PUTSTATIC: /* stack(value) -> static_field */
- case ICMD_PUTFIELDCONST:
-
- /* pop 1 push 0 branch */
- case ICMD_IFNULL: /* stack(value) -> branch? */
- case ICMD_IFNONNULL:
-
- case ICMD_IFEQ:
- case ICMD_IFNE:
- case ICMD_IFLT:
- case ICMD_IFGE:
- case ICMD_IFGT:
- case ICMD_IFLE:
-
- case ICMD_IF_LEQ:
- case ICMD_IF_LNE:
- case ICMD_IF_LLT:
- case ICMD_IF_LGE:
- case ICMD_IF_LGT:
- case ICMD_IF_LLE:
-
- /* pop 1 push 0 table branch */
- case ICMD_TABLESWITCH:
- case ICMD_LOOKUPSWITCH:
-
- case ICMD_MONITORENTER:
- case ICMD_MONITOREXIT:
- lsra_from_stack(ls, src, b_index, iindex);
- break;
-
- /* pop 2 push 0 */
- case ICMD_POP2: /* throw away 2 stackslots */
-#if 0
- /* TODO: check if used anyway (DUP...) and change codegen */
- /* to ignore this stackslot */
- lsra_pop_from_stack(ls, src, b_index, iindex);
- lsra_pop_from_stack(ls, src->prev, b_index, iindex);
-#endif
- break;
-
- /* pop 2 push 0 branch */
-
- case ICMD_IF_ICMPEQ: /* stack (v1,v2) -> branch(v1,v2) */
- case ICMD_IF_ICMPNE:
- case ICMD_IF_ICMPLT:
- case ICMD_IF_ICMPGE:
- case ICMD_IF_ICMPGT:
- case ICMD_IF_ICMPLE:
-
- 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:
-
- /* pop 2 push 0 */
- case ICMD_PUTFIELD: /* stack(objref,value) -> objref = value */
-
- case ICMD_IASTORECONST:
- case ICMD_LASTORECONST:
- case ICMD_AASTORECONST:
- case ICMD_BASTORECONST:
- case ICMD_CASTORECONST:
- case ICMD_SASTORECONST:
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
- break;
+ /* check for use (s1, s2, s3 or special (argp) ) */
+ /* and definitions (dst) */
+ switch(icmd_table[iptr->opc].dataflow) {
+ case DF_3_TO_0:
+ case DF_3_TO_1: /* icmd has s1, s2 and s3 */
+ lt_usage(jd, iptr->sx.s23.s3.varindex, b_index, iindex, LT_USE);
- /* pop 0 push 1 dup */
- case ICMD_DUP:
- /* src == dst->prev */
- /* ---------------- */
- /* src -> dst */
+ /* now "fall through" for handling of s2 and s1 */
- /* Add the use site for src==dst */
- lsra_from_stack(ls, src, b_index, iindex);
+ case DF_2_TO_0:
+ case DF_2_TO_1: /* icmd has s1 and s2 */
+ lt_usage(jd, iptr->sx.s23.s2.varindex, b_index, iindex, LT_USE);
- lsra_new_stack(ls, dst, b_index, iindex);
+ /* now "fall through" for handling of s1 */
+ case DF_1_TO_0:
+ case DF_1_TO_1:
+ case DF_MOVE:
+ case DF_COPY: /* icmd has s1 */
+ lt_usage(jd, iptr->s1.varindex, b_index, iindex, LT_USE);
break;
- /* pop 0 push 2 dup */
- case ICMD_DUP2:
- /* src == dst->prev->prev */
- /* src->prev == dst->prev->prev->prev */
- /* ---------------- */
- /* src -> dst */
- /* src->prev -> dst->prev */
- /* src & src->prev "continue" living -> so no conflicts */
- /* with dst and dst->prec possible */
-
- /* add the use site for src == dst->prev->prev */
- lsra_from_stack(ls, src, b_index, iindex);
- /* add the use site for src->prev == dst->prev->prev->prev */
- lsra_from_stack(ls, src->prev, b_index, iindex);
-
-
- lsra_new_stack(ls, dst->prev, b_index, iindex);
- lsra_new_stack(ls, dst, b_index, iindex);
-
- break;
-
- /* pop 2 push 3 dup */
- case ICMD_DUP_X1:
- /* src -> dst */
- /* src->prev -> dst->prev */
- /* src -> dst->prev->prev */
- /* !!!!!!!!!!!!!!!!!!!!!!!!!!!! */
- /* Copy Conflicts possible! */
- /* -> instack [ t1 t0 ] */
- /* -> outstack[ t0 t1 t3 ] */
- /* -> t1->t0, t0->t1, t1->t3 !! */
- /* -> Remove src->prev on iindex+1 instead of iindex! */
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
- lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
- lsra_new_stack(ls, dst->prev, b_index, iindex);
- lsra_new_stack(ls, dst, b_index, iindex);
-
- break;
-
- /* pop 3 push 4 dup */
- case ICMD_DUP_X2:
- /* src -> dst */
- /* src -> dst->prev->prev->prev */
- /* src->prev -> dst->prev */
- /* src->prev->prev -> dst->prev->prev */
- /* Conflicts possible! -> remove srces at iindex + 1 */
- lsra_from_stack(ls, src,b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
- lsra_from_stack(ls, src->prev->prev, b_index, iindex);
- lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
- lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
- lsra_new_stack(ls, dst->prev, b_index, iindex);
- lsra_new_stack(ls, dst, b_index, iindex);
-
- break;
-
- /* pop 3 push 5 dup */
- case ICMD_DUP2_X1:
- /* src -> dst */
- /* src -> dst->prev->prev->prev */
- /* src->prev -> dst->prev->prev->prev->prev */
- /* src->prev -> dst->prev */
- /* src->prev->prev -> dst->prev->prev */
- /* Conflicts possible! -> remove srces at iindex + 1 */
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
- lsra_from_stack(ls, src->prev->prev, b_index, iindex);
- lsra_new_stack(ls, dst->prev->prev->prev->prev, b_index,
- iindex);
- lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
- lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
- lsra_new_stack(ls, dst->prev, b_index, iindex);
- lsra_new_stack(ls, dst, b_index, iindex);
-
-
- break;
-
- /* pop 4 push 6 dup */
- case ICMD_DUP2_X2:
- /* src -> dst */
- /* src -> dst->prev->prev->prev->prev */
- /* src->prev -> dst->prev->prev->prev->prev->prev */
- /* src->prev -> dst->prev */
- /* src->prev->prev -> dst->prev->prev */
- /* src->prev->prev->prev -> dst->prev->prev->prev */
- /* Conflicts possible! -> remove srcs at iindex + 1 */
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
- lsra_from_stack(ls, src->prev->prev, b_index, iindex);
- lsra_from_stack(ls, src->prev->prev->prev, b_index, iindex);
- lsra_new_stack(ls, dst->prev->prev->prev->prev->prev,
- b_index, iindex);
- lsra_new_stack(ls, dst->prev->prev->prev->prev, b_index,
- iindex);
- lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
- lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
- lsra_new_stack(ls, dst->prev, b_index, iindex);
- lsra_new_stack(ls, dst, b_index, iindex);
-
- break;
-
- /* pop 2 push 2 swap */
- case ICMD_SWAP:
- /* src -> dst->prev */
- /* src->prev -> dst */
- /* Conflicts possible -> remove src at iindex + 1 */
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
- lsra_new_stack(ls, dst->prev, b_index, iindex);
- lsra_new_stack(ls, dst, b_index, iindex);
- break;
-
- /* pop 2 push 1 */
-
- case ICMD_LADD:
- case ICMD_LSUB:
- case ICMD_LMUL:
-
- case ICMD_LOR:
- case ICMD_LAND:
- case ICMD_LXOR:
-
- case ICMD_LSHL:
- case ICMD_LSHR:
- case ICMD_LUSHR:
-
- case ICMD_IADD:
- case ICMD_IMUL:
-
- case ICMD_ISHL:
- case ICMD_ISHR:
- case ICMD_IUSHR:
- case ICMD_IAND:
- case ICMD_IOR:
- case ICMD_IXOR:
-
-
- case ICMD_FADD:
- case ICMD_FSUB:
- case ICMD_FMUL:
-
- case ICMD_DADD:
- case ICMD_DSUB:
- case ICMD_DMUL:
- case ICMD_DDIV:
- case ICMD_DREM:
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
- lsra_new_stack(ls, dst, b_index, iindex);
- break;
-
- case ICMD_ISUB:
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_from_stack(ls, src->prev,b_index,iindex);
- lsra_new_stack(ls, dst, b_index, iindex);
- break;
-
- case ICMD_LDIV:
- case ICMD_LREM:
-
- case ICMD_IDIV:
- case ICMD_IREM:
-
- case ICMD_FDIV:
- case ICMD_FREM:
-
- case ICMD_LCMP:
- case ICMD_FCMPL:
- case ICMD_FCMPG:
- case ICMD_DCMPL:
- case ICMD_DCMPG:
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
- lsra_new_stack(ls, dst, b_index, iindex);
- break;
-
- /* pop 1 push 1 */
- case ICMD_LADDCONST:
- case ICMD_LSUBCONST:
- case ICMD_LMULCONST:
- case ICMD_LMULPOW2:
- case ICMD_LDIVPOW2:
- case ICMD_LREMPOW2:
- case ICMD_LANDCONST:
- case ICMD_LORCONST:
- case ICMD_LXORCONST:
- case ICMD_LSHLCONST:
- case ICMD_LSHRCONST:
- case ICMD_LUSHRCONST:
-
- case ICMD_IADDCONST:
- case ICMD_ISUBCONST:
- case ICMD_IMULCONST:
- case ICMD_IMULPOW2:
- case ICMD_IDIVPOW2:
- case ICMD_IREMPOW2:
- case ICMD_IANDCONST:
- case ICMD_IORCONST:
- case ICMD_IXORCONST:
- case ICMD_ISHLCONST:
- case ICMD_ISHRCONST:
- case ICMD_IUSHRCONST:
-
-/* case ICMD_IFEQ_ICONST: */
-/* case ICMD_IFNE_ICONST: */
-/* case ICMD_IFLT_ICONST: */
-/* case ICMD_IFGE_ICONST: */
-/* case ICMD_IFGT_ICONST: */
-/* case ICMD_IFLE_ICONST: */
-
- case ICMD_INEG:
- case ICMD_INT2BYTE:
- case ICMD_INT2CHAR:
- case ICMD_INT2SHORT:
- case ICMD_LNEG:
- case ICMD_FNEG:
- case ICMD_DNEG:
-
- case ICMD_I2L:
- case ICMD_I2F:
- case ICMD_I2D:
- case ICMD_L2I:
- case ICMD_L2F:
- case ICMD_L2D:
- case ICMD_F2I:
- case ICMD_F2L:
- case ICMD_F2D:
- case ICMD_D2I:
- case ICMD_D2L:
- case ICMD_D2F:
-
- case ICMD_CHECKCAST:
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_new_stack(ls, dst, b_index, iindex);
- break;
-
- case ICMD_ARRAYLENGTH:
- case ICMD_INSTANCEOF:
-
- case ICMD_NEWARRAY:
- case ICMD_ANEWARRAY:
-
- case ICMD_GETFIELD:
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_new_stack(ls, dst, b_index, iindex);
- break;
-
- /* pop 0 push 1 */
- case ICMD_GETSTATIC:
-
- case ICMD_NEW:
- lsra_new_stack(ls, dst, b_index, iindex);
- break;
-
- /* pop many push any */
-
- case ICMD_INVOKESTATIC:
- case ICMD_INVOKESPECIAL:
- case ICMD_INVOKEVIRTUAL:
- case ICMD_INVOKEINTERFACE:
+ case DF_INVOKE:
INSTRUCTION_GET_METHODDESC(iptr,md);
i = md->paramcount;
- while (--i >= 0) {
- lsra_from_stack(ls, src, b_index, iindex);
- src = src->prev;
- }
- if (md->returntype.type != TYPE_VOID)
- lsra_new_stack(ls, dst, b_index, iindex);
+ if (md->returntype.type == TYPE_VOID)
+ v = UNUSED;
break;
- case ICMD_BUILTIN:
- bte = iptr->val.a;
+ case DF_BUILTIN:
+ bte = iptr->sx.s23.s3.bte;
md = bte->md;
i = md->paramcount;
- while (--i >= 0) {
- lsra_from_stack(ls, src, b_index, iindex);
- src = src->prev;
- }
- if (md->returntype.type != TYPE_VOID)
- lsra_new_stack(ls, dst, b_index, iindex);
+ if (md->returntype.type == TYPE_VOID)
+ v = UNUSED;
+ break;
+
+ case DF_N_TO_1:
+ i = iptr->s1.argcount;
break;
- case ICMD_MULTIANEWARRAY:
- i = iptr->op1;
+ }
+
+ if (i != UNUSED) {
+ argp = iptr->sx.s23.s2.args;
while (--i >= 0) {
- lsra_from_stack(ls, src, b_index, iindex);
- src = src->prev;
+ lt_usage(jd, *argp, b_index, iindex, LT_USE);
+ argp++;
}
- lsra_new_stack(ls, dst, b_index, iindex);
- break;
+ }
- default:
-/* assert(0); */
- throw_cacao_exception_exit(string_java_lang_InternalError,
- "Unknown ICMD %d during register allocation", iptr->opc);
- } /* switch */
+ if (v != UNUSED) {
+ lt_usage(jd, v, b_index, iindex, LT_DEF);
+ }
} /* for (;iindex >= 0; iindex--, iptr--) */
} /* if (bptr->flags >= BBREACHED) */
} /* scan_lifetimes */
#if !defined(NDEBUG)
# include <assert.h>
# define LT_DEBUG_CHECK
-# define LT_DEBUG_VERBOSE
+/* # define LT_DEBUG_VERBOSE */
#endif
#ifdef LT_DEBUG_CHECK
# define _LT_ASSERT(a)
#endif
-#define LSRA_BB_IN 3
-#define LSRA_BB_OUT 2
-#define LSRA_STORE 1
-#define LSRA_LOAD 0
-#define LSRA_POP -1
+#define LT_BB_IN 3
+#define LT_BB_OUT 2
+#define LT_DEF 1
+#define LT_USE 0
typedef struct site *lt_iterator;
-void scan_lifetimes(methodinfo *m, codegendata *cd, registerdata *rd,
- lsradata *ls, graphdata *gd, dominatordata *dd);
-void lsra_add_ss(struct lifetime *, stackptr );
-void remove_use_site(struct lifetime *lt, int block, int iindex);
-void move_use_sites(struct lifetime *from, struct lifetime *to);
-void move_stackslots(struct lifetime *from, struct lifetime *to);
-void LifenessAnalysis(methodinfo *m, lsradata *ls, graphdata *gd);
+void lt_scanlifetimes(jitdata *, graphdata *, dominatordata *);
+void lt_add_ss(struct lifetime *, stackptr );
+void lt_remove_use_site(struct lifetime *lt, int block, int iindex);
+void lt_move_use_sites(struct lifetime *from, struct lifetime *to);
+void lt_lifeness_analysis(jitdata *, graphdata *);
#endif /* _LIFETIMES_H */
/*
#include "toolbox/bitvector.h"
-#include "vm/statistics.h"
-#include "vm/options.h"
+#include "vmcore/statistics.h"
+#include "vmcore/options.h"
+#include "vmcore/method.h"
#include "vm/jit/abi.h"
#include "vm/jit/reg.h"
int *);
int lsra_getmem(struct lifetime *, struct freemem *, int *);
struct freemem *lsra_getnewmem(int *);
-void lsra_setflags(int *, int);
void lsra(jitdata *jd) {
methodinfo *m;
registerdata *rd;
lsradata *ls;
graphdata *gd;
-#if defined(STATISTICS)
+#if defined(ENABLE_STATISTICS)
int locals_start;
int i,j;
#endif
#if defined(LSRA_DEBUG_CHECK)
+#if 0
int b_index;
stackptr in,out;
int ind, outd;
+#endif
#endif
m = jd->m;
ls = jd->ls;
#if defined(LSRA_DEBUG_CHECK)
+#if 0
b_index = 0;
- while (b_index < m->basicblockcount ) {
+ while (b_index < jd->basicblockcount ) {
- if (m->basicblocks[b_index].flags >= BBREACHED) {
+ if (jd->basicblocks[b_index].flags >= BBREACHED) {
in=m->basicblocks[b_index].instack;
ind=m->basicblocks[b_index].indepth;
b_index++;
}
#endif
+#endif
#if defined(LSRA_DEBUG_CHECK) || defined(LSRA_DEBUG_VERBOSE)
#if defined(LSRA_DEBUG_VERBOSE)
#endif
lsra_init(jd);
-
-
gd = lsra_setup(jd);
#if defined(ENABLE_STATISTICS)
/* allocate lifetimes for all Basicblocks */
ls->v_index = -1;
-
-
}
graphdata *lsra_setup(jitdata *jd)
/* Generate the Control Flow Graph */
/* Add one for a Basic Block 0 to be inserted, so lateron */
/* with SSA Parameter initialization is handled right */
- gd = graph_init(m->basicblockcount + 1);
+ gd = graph_init(jd->basicblockcount + 1);
graph_make_cfg(jd, gd);
-
ssa(jd, gd);
-
- LifenessAnalysis(m, ls, gd);
+ lt_lifeness_analysis(jd, gd);
#ifdef LSRA_DEBUG_VERBOSE
if (compileverbose) {
#if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
if (IS_2_WORD_TYPE(md->paramtypes[i].type)) {
int_reg->sav_reg[--int_sav_top] =
- rd->argintregs[GET_HIGH_REG(md->params[i].regoff)];
+ GET_HIGH_REG(md->params[i].regoff);
intarg_used[GET_HIGH_REG(md->params[i].regoff)]=true;
/*used -> don't copy later on */
int_reg->sav_reg[--int_sav_top] =
- rd->argintregs[GET_LOW_REG(md->params[i].regoff)];
+ GET_LOW_REG(md->params[i].regoff);
intarg_used[GET_LOW_REG(md->params[i].regoff)]=true;
/*used -> don't copy later on */
} else
#endif
{ /* !IS_2_WORD_TYPE(md->paramtypes[i].type */
int_reg->sav_reg[--int_sav_top] =
- rd->argintregs[md->params[i].regoff];
+ md->params[i].regoff;
intarg_used[md->params[i].regoff]=true;
/*used -> don't copy later on */
}
/* still be used in the method! */
else { /* IS_FLT_DBL_TYPE(md->paramtypes[i].type */
flt_reg->sav_reg[--flt_sav_top] =
- rd->argfltregs[md->params[i].regoff];
+ md->params[i].regoff;
fltarg_used[md->params[i].regoff]=true;
}
#endif
/* int_reg->sav_reg; */
for (i=0; i < INT_ARG_CNT; i++)
if (!intarg_used[i])
- int_reg->sav_reg[--int_sav_top]=rd->argintregs[i];
+ int_reg->sav_reg[--int_sav_top]=i;
for (i=0; i < FLT_ARG_CNT; i++)
if (!fltarg_used[i])
- flt_reg->sav_reg[--flt_sav_top]=rd->argfltregs[i];
+ flt_reg->sav_reg[--flt_sav_top]=i;
/* copy temp registers to flt_reg->sav_reg and int_reg->sav_reg */
for (i=0; i < INT_TMP_CNT; i++)
/* with Locals as non SAVEDVAR, the used arg[int|flt] as in params */
/* of the method itself have to be regarded, or mismatch before */
/* block 0 with parameter copy could happen! */
+
argintreguse = max(rd->argintreguse, md->argintreguse);
argfltreguse = max(rd->argfltreguse, md->argfltreguse);
/* copy temp and unused argument registers to flt_reg->tmp_reg and */
/* int_reg->tmp_reg */
+
for (i=0; i < INT_TMP_CNT; i++)
int_reg->tmp_reg[i]=rd->tmpintregs[i];
+
+ /* quick and dirty patch for the drop of rd->argxxxreg[] - but will */
+ /* work anyhow on i386, !! has to be made "real" for other archs */
+
for (j = argintreguse; j < INT_ARG_CNT; j++, i++)
- int_reg->tmp_reg[i]=rd->argintregs[j];
+ int_reg->tmp_reg[i]=j;
for (i=0; i < FLT_TMP_CNT; i++)
flt_reg->tmp_reg[i]=rd->tmpfltregs[i];
+
+ /* quick and dirty patch for the drop of rd->argxxxreg[] - but will */
+ /* work anyhow on i386, !! has to be made "real" for other archs */
+
for (j = argfltreguse; j < FLT_ARG_CNT; j++, i++)
- flt_reg->tmp_reg[i]=rd->argfltregs[j];
+ flt_reg->tmp_reg[i]=j;
}
/* now copy saved registers to flt_reg->sav_reg and int_reg->sav_reg */
printf("Rest RA complete \n");
printf("Lifetimes after leftt:\n");
print_lifetimes(jd, ls->lt_mem, ls->lt_mem_count);
+
+ printf("jd->varcount: %i jd->vartop %i\n", jd->varcount, jd->vartop);
}
#endif
}
int flags,regoff;
struct lifetime *lt;
struct freemem *fmem;
- struct stackslot *n;
int lt_index;
#ifdef HAS_4BYTE_STACKSLOT
struct freemem *fmem_2;
#endif
for (lt_index = 0; lt_index < lifetimecount; lt_index ++) {
- lt = &(ls->lifetime[lifet[lt_index]]);
+ lt = ls->lifetime + lifet[lt_index];
#ifdef LSRA_MEMORY
lt->reg=-1;
#endif
- if (lt->reg==-1) {
- flags=INMEMORY;
+ if (lt->regoff == -1) {
+ flags = INMEMORY;
#ifdef HAS_4BYTE_STACKSLOT
if (IS_2_WORD_TYPE(lt->type))
- regoff=lsra_getmem(lt, fmem_2, mem_use);
+ regoff = lsra_getmem(lt, fmem_2, mem_use);
else
#endif
- regoff=lsra_getmem(lt, fmem, mem_use);
+ regoff = lsra_getmem(lt, fmem, mem_use);
} else {
- flags=lt->savedvar;
- regoff=lt->reg;
- }
-
- for (n=lt->local_ss; n!=NULL; n=n->next) {
- lsra_setflags( &(n->s->flags), flags);
- n->s->regoff=regoff;
- }
- if (lt->v_index >= 0) {
- if (rd->locals[lt->v_index][lt->type].type>=0) {
- rd->locals[lt->v_index][lt->type].flags= flags;
- rd->locals[lt->v_index][lt->type].regoff=regoff;
- } else { log_text("Type Data mismatch 1\n"); exit(1); }
+ flags = lt->savedvar;
+ regoff = lt->regoff;
}
- lt->reg = regoff;
+ lt->regoff = regoff;
+ VAR(lt->v_index)->vv.regoff = regoff;
+ VAR(lt->v_index)->flags = flags;
}
}
-void lsra_setflags(int *flags, int newflags)
-{
- if ( newflags & INMEMORY)
- *flags |= INMEMORY;
- else
- *flags &= ~INMEMORY;
-
- if (newflags & SAVEDVAR)
- *flags |= SAVEDVAR;
- else
- *flags &= ~SAVEDVAR;
-}
-
int lsra_getmem(struct lifetime *lt, struct freemem *fmem, int *mem_use)
{
struct freemem *fm, *p;
/* no registers available */
for (lt_index = 0; lt_index < lifetimecount; lt_index++)
- ls->lifetime[lifet[lt_index]].reg = -1;
+ ls->lifetime[lifet[lt_index]].regoff = -1;
return;
}
if (reg_index == -1) /* no reg is available anymore... -> spill */
spill_at_intervall(jd, lt);
else {
- lt->reg = reg_index;
+ lt->regoff = reg_index;
if (temp)
lsra_add_active(lt, ls->active_tmp, &(ls->active_tmp_top));
else {
reg->sav_reg[reg->sav_top++] = GET_HIGH_REG(active[i]->reg);
} else
#endif
- reg->sav_reg[reg->sav_top++] = active[i]->reg;
+ reg->sav_reg[reg->sav_top++] = active[i]->regoff;
} else {
/* no leafmethod -> distinguish between temp and saved register */
#if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
}
} else
#endif
- if ( reg->nregdesc[active[i]->reg] == REG_SAV) {
- reg->sav_reg[reg->sav_top++] = active[i]->reg;
+ if ( reg->nregdesc[active[i]->regoff] == REG_SAV) {
+ reg->sav_reg[reg->sav_top++] = active[i]->regoff;
} else {
- reg->tmp_reg[reg->tmp_top++] = active[i]->reg;
+ reg->tmp_reg[reg->tmp_top++] = active[i]->regoff;
}
}
}
_spill_at_intervall(lt, ls->active_sav, &(ls->active_sav_top));
} else {
_spill_at_intervall(lt, ls->active_tmp, &(ls->active_tmp_top));
- if (lt->reg == -1) { /* kein tmp mehr frei gewesen */
+ if (lt->regoff == -1) { /* kein tmp mehr frei gewesen */
_spill_at_intervall(lt, ls->active_sav, &(ls->active_sav_top));
}
}
#endif /* 0 */
if (*active_top == 0) {
- lt->reg=-1;
+ lt->regoff = -1;
return;
}
return;
#endif
- lt->reg=active[i]->reg;
- active[i]->reg=-1;
+ lt->regoff = active[i]->regoff;
+ active[i]->regoff = -1;
(*active_top)--;
for (j = i; j < *active_top; j++)
lsra_add_active(lt, active, active_top);
} else {
- lt->reg=-1;
+ lt->regoff = -1;
}
}
/* 1 INTREG -> ls->lt_int */
/* 2 FLTREG -> ls->lt_flt */
- instruction *iptr;
lsradata *ls;
ls = jd->ls;
for (i=1; i < ls->basicblockcount; i++) {
if (ls->sorted[i-1] != -1)
icount += ls->basicblocks[ls->sorted[i-1]]->icount + 1 +
- ls->max_vars_with_indices;
+ ls->varcount_with_indices;
if (ls->sorted[i] != -1)
icount_block[i] = icount;
}
/* i_last_use */
_LSRA_ASSERT(lt->def != NULL);
- _LSRA_ASSERT(lt->use != NULL);
-
- /* there are conflicts possible between in and outstacks of */
- /* DUP* ICMDs. So extend lifetime of outstacks by one */
- if (lt->i_first_def >= 0 && (lt->bb_first_def != 0)) {
- iptr = ls->basicblocks[ls->sorted[lt->bb_first_def]]->iinstr +
- lt->i_first_def;
- switch (iptr->opc) {
-/* case ICMD_DUP: */
- case ICMD_DUP2:
- case ICMD_DUP_X1:
- case ICMD_DUP_X2:
- case ICMD_DUP2_X1:
- case ICMD_DUP2_X2:
- case ICMD_SWAP:
-/* _LSRA_ASSERT(lt->i_first_def != 0); */
- lt->i_first_def--;
- }
- }
+ /* _LSRA_ASSERT(lt->use != NULL);*/
+ if (lt->use == NULL)
+ lt->use = lt->def;
#if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
/* prevent conflicts between lifetimes of type long by increasing */
/* distribute lifetimes to lt_int, lt_flt and lt_mem */
- lt->reg = -1;
+ lt->regoff = -1;
switch (lt->type) {
case TYPE_LNG:
lt->i_start = icount_block[lt->bb_first_def] + lt->i_first_def;
if (lt->bb_last_use == -1) {
- printf("--------- Warning: variable not used! --------------------vi: %i start: %i end: %i\n", lt->v_index, lt->i_start, lt->i_end);
+ /* unused Vars are not regarded by lifeness_analysis! */
+ _LSRA_ASSERT(lt->def != NULL)
+ _LSRA_ASSERT(lt->def->next == NULL)
+
+ if (compileverbose) {
+ printf("--------- Warning: variable not used! ---------");
+ printf("vi: %i start: %i end: %i\n", lt->v_index,
+ lt->i_start, lt->i_end);
+ }
lt->bb_last_use = lt->bb_first_def;
lt->i_last_use = lt->i_first_def;
}
{
struct lifetime *n;
int lt_index;
- int type,flags,regoff,varkind;
lsradata *ls;
registerdata *rd;
ls = jd->ls;
for (lt_index = 0; lt_index < lifetimecount; lt_index++) {
- n = &(ls->lifetime[lt[lt_index]]);
- if (n->v_index < 0) { /* stackslot */
- type = n->local_ss->s->type;
- flags=n->local_ss->s->flags;
- regoff=n->local_ss->s->regoff;
- varkind=n->local_ss->s->varkind;
- } else { /* local var */
- if (rd->locals[n->v_index][n->type].type>=0) {
- type = rd->locals[n->v_index][n->type].type;
- flags=rd->locals[n->v_index][n->type].flags;
- regoff=rd->locals[n->v_index][n->type].regoff;
- varkind=-1;
- } else
- { log_text("Type Data mismatch 3\n"); assert(0); }
- }
- printf("i_Start: %3i(%3i,%3i) i_stop: %3i(%3i,%3i) reg: %3i VI: %3i type: %3i flags: %3i varkind: %3i usage: %3li ltflags: %xi \n",n->i_start, ls->sorted[n->bb_first_def], n->i_first_def,n->i_end, ls->sorted[n->bb_last_use], n->i_last_use,regoff,n->v_index,type,flags, varkind, n->usagecount, n->flags);
+ n = ls->lifetime + lt[lt_index];
+ printf("i_Start: %3i(%3i,%3i) i_stop: %3i(%3i,%3i) reg: %3i VI: %3i type: %3i flags: %3i usage: %3li ltflags: %xi \n",n->i_start, ls->sorted[n->bb_first_def], n->i_first_def,n->i_end, ls->sorted[n->bb_last_use], n->i_last_use,n->regoff,n->v_index,n->type,n->flags, n->usagecount, n->flags);
}
printf( "%3i Lifetimes printed \n",lt_index);
}
{
struct lifetime *n;
int lt_index;
- int type,flags,regoff,varkind;
lsradata *ls;
registerdata *rd;
for (lt_index = 0; lt_index < ls->lifetimecount; lt_index++) {
n = &(ls->lifetime[lt_index]);
if (n->type != -1) {
- if (n->v_index < 0) { /* stackslot */
- type = n->local_ss->s->type;
- flags=n->local_ss->s->flags;
- regoff=n->local_ss->s->regoff;
- varkind=n->local_ss->s->varkind;
- } else { /* local var */
- if (rd->locals[n->v_index][n->type].type>=0) {
- type = rd->locals[n->v_index][n->type].type;
- flags=rd->locals[n->v_index][n->type].flags;
- regoff=rd->locals[n->v_index][n->type].regoff;
- varkind=-1;
- } else
- { log_text("Type Data mismatch 3\n"); assert(0); }
- }
- printf("i_Start: %3i(%3i,%3i) i_stop: %3i(%3i,%3i) VI: %3i type: %3i flags: %3i varkind: %3i usage: %3li ltflags: %xi \n",n->i_start, ls->sorted[n->bb_first_def], n->i_first_def,n->i_end, ls->sorted[n->bb_last_use], n->i_last_use,n->v_index,type,flags, varkind, n->usagecount, n->flags);
+ printf("i_Start: %3i(%3i,%3i) i_stop: %3i(%3i,%3i) VI: %3i type: %3i flags: %3i usage: %3li ltflags: %xi \n",n->i_start, ls->sorted[n->bb_first_def], n->i_first_def,n->i_end, ls->sorted[n->bb_last_use], n->i_last_use,n->v_index,n->type,n->flags, n->usagecount, n->flags);
}
}
printf( "%3i Lifetimes printed \n",lt_index);
#include "toolbox/bitvector.h"
+
#if !defined(NDEBUG)
# include <assert.h>
# define LSRA_DEBUG_CHECK
int v_index; /* local variable index or negative for stackslots */
int type; /* TYPE_XXX or -1 for unused lifetime */
long usagecount; /* number of references*/
- int reg; /* regoffset allocated by lsra*/
+ int regoff; /* regoffset allocated by lsra*/
int savedvar;
int flags;
- struct stackslot *local_ss; /* Stackslots for this Lifetime or NULL ( == */
+ /* struct stackslot *local_ss; */ /* Stackslots for this Lifetime or NULL ( == */
/* "pure" Local Var) */
int bb_last_use;
int i_last_use;
int nesting;
};
+/*
struct stackslot {
stackptr s;
int bb;
struct stackslot *next;
};
+*/
struct lsra_register {
int *sav_reg;
struct lsradata {
+ /* int *var; */ /* unused entries are set to UNUSED */
+ /* maps to jd->vars array */
+ int varcount; /* size of vars array */
+ int ssavarcount; /* ls->vars[0..ssavarcount[ are all locals and iovars */
+ /* they are regarded for ssa renaming */
+ /* the rest (ls->vars[ssavarcount..varcount[ are */
+ /* TEMP or PREALLOC vars with just on definition and */
+ /* use within one basicblock -> not of interest for */
+ /* ssa renaming procedures */
+ int vartop; /* next free var */
+ int varcount_with_indices;
+ int *new_varindex; /* new_varindex[0..jd->varcount[ points to the new */
+ /* unique index of ls->vars(maps jd->vars to ls->vars)*/
+
+ int *var_0; /* [0..ls->varcount] */
+ /* var_0[a] with a in [0..ls->varcount[ holds the */
+ /* index of La,0 */
+ /* var_0[ls->varcount] holds the number of vars with */
+ /*indices */
+
int *sorted; /* BB sorted in reverse post order */
int *sorted_rev; /* BB reverse lookup of sorted */
long *nesting; /* Nesting level of BB*/
- int maxlifetimes; /* copy from methodinfo to prevent passing methodinfo */
- /* as parameter */
-
struct lifetime *lifetime; /* array of lifetimes */
int lifetimecount; /* number of lifetimes */
int *lt_used; /* index to lifetimearray for used lifetimes */
/* SSA fields */
bitvector *var_def; /* LocalVar Definition Bitvector [0..ls->bbcount] */
- /* Bitvector holds ls->max_vars Bits */
+ /* Bitvector holds ls->max_vars Bits */
bitvector *use_sites; /* LocalVar Use Bitvector[0..ls->maxvars] */
int **num_var_use; /* count of var_use[bb][var_index] */
int **var; /* [0..cd->maxlocal+cd->maxstack[[0..4] */
#include "toolbox/bitvector.h"
#include "toolbox/worklist.h"
+#include "vm/builtin.h"
+
+#include "vm/jit/jit.h" /* icmd_table */
+
#include "vm/jit/optimizing/dominators.h"
#include "vm/jit/optimizing/graph.h"
#include "vm/jit/optimizing/lifetimes.h"
#include "vm/jit/optimizing/ssa.h"
#if defined(SSA_DEBUG_VERBOSE)
-#include "vm/options.h" /* compileverbose */
-#include "vm/jit/jit.h" /* icmd_table */
+#include "vmcore/options.h" /* compileverbose */
#endif
/* function prototypes */
-void dead_code_elimination(methodinfo *m, registerdata *rd, lsradata *ls,
- graphdata *gd);
-void copy_propagation(methodinfo *m,registerdata *rd, lsradata *ls,
- graphdata *gd);
-void replace_use_sites( lsradata *ls, graphdata *gd, struct lifetime *lt,
- int new_v_index, worklist *W);
-void ssa_place_phi_functions(codegendata *cd, lsradata *ls, graphdata *gd,
- dominatordata *dd);
-void ssa_Rename_init(methodinfo *m, codegendata *cd, lsradata *ls,
- graphdata *gd);
-void ssa_Rename(methodinfo *m, codegendata *cd, registerdata *rd, lsradata *ls,
- graphdata *gd, dominatordata *dd);
-void ssa_Rename_(codegendata *cd, lsradata *ls, graphdata *gd,
- dominatordata *dd, int n);
+void ssa_set_local_def(lsradata *, int , int);
+void ssa_set_interface(jitdata *, basicblock *, s4 *);
+
+void dead_code_elimination(jitdata *jd, graphdata *gd);
+void copy_propagation(jitdata *jd, graphdata *gd);
+void ssa_replace_use_sites(jitdata *, graphdata *, struct lifetime *,
+ int , worklist *);
+void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd);
+void ssa_rename_init(jitdata *jd, graphdata *gd);
+void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd);
+void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n);
+
+void ssa_set_def(lsradata *, int , int );
+void ssa_set_local_def(lsradata *, int , int );
+void ssa_set_iovar(lsradata *, s4 , int , s4 *);
+void ssa_set_interface(jitdata *, basicblock *, s4 *);
+
+void ssa_generate_phi_moves(jitdata *, graphdata *);
+int ssa_rename_def_(lsradata *ls, int a);
#ifdef SSA_DEBUG_VERBOSE
-void ssa_print_trees(methodinfo *m, codegendata *cd, lsradata *ls,
- graphdata *gd, dominatordata *dd);
+void ssa_print_trees(jitdata *jd, graphdata *gd, dominatordata *dd);
void ssa_print_lt(lsradata *ls);
+void ssa_show_variable(jitdata *jd, int index, varinfo *v, int stage);
+void ssa_print_phi(lsradata *, graphdata *);
#endif
-/*********************************************************
-Data Collection (Use/Definition) while analyze_stack:
-Basic Block indices of definition are needed for generation
-of the phi Functions.
-
-ssa_set_local_def
-ssa_set_interface
-ssa_set_use
-
-These two functions use the internal Helpers:
-ssa_set_def
-ssa_set_interface_
-*********************************************************/
-void ssa_set_use(lsradata *ls, int b_index, int local_index, int type) {
- /* just count uses to determine the needed max size for use def */
- /* data structures */
- ls->uses++;
-}
-void ssa_set_def(lsradata *ls, int b_index, int var_index) {
+/* ssa ************************************************************************
- /* b_index + 1 to leave space for the param init block 0 */
- bv_set_bit(ls->var_def[b_index + 1], var_index);
- /* count number of defs for every var since SSA */
- /* will create a new var for every definition */
- ls->num_defs[var_index]++;
-}
+SSA main procedure:
-void ssa_set_local_def(lsradata *ls, int b_index, int local_index, int type) {
+******************************************************************************/
- if (ls->var[local_index][type] == -1) {
- /* New Local Variable encountered -> create a new unique index */
- ls->var[local_index][type] = ls->max_vars;
- ls->var_to_index[ls->max_vars] = ls->max_locals++;
- ls->max_vars++;
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- printf("Local %3i,%3i -> Var %3i\n",local_index,type,ls->max_vars-1);
-#endif
- }
+void ssa(jitdata *jd, graphdata *gd) {
+ struct dominatordata *dd;
+ lsradata *ls;
- ssa_set_def(ls, b_index, ls->var[local_index][type]);
-}
+ ls = jd->ls;
-void ssa_set_interface_(codegendata *cd, lsradata *ls, basicblock *bptr,
- stackptr s, int depth) {
- int var_index;
+ dd = compute_Dominators(gd, ls->basicblockcount);
+ computeDF(gd, dd, ls->basicblockcount, 0);
- var_index = depth + jd->maxlocals;
- if (ls->var[var_index][s->type] == -1) {
- /* New Interface Stackslot encountered -> create a new unique index */
- ls->var[var_index][s->type] = ls->max_vars;
- ls->var_to_index[ls->max_vars] = ls->max_interfaces--;
- ls->max_vars++;
+ ssa_place_phi_functions(jd, gd, dd);
+ ssa_rename(jd, gd, dd);
#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- printf("Interface SS %3i,%3i -> Var %3i\n",bptr->nr+1,depth,ls->max_vars-1);
+ if (compileverbose) {
+ printf("Phi before Cleanup\n");
+ ssa_print_phi(ls, gd);
+ ssa_print_lt(ls);
+ }
#endif
+ lt_scanlifetimes(jd, gd, dd);
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ ssa_print_lt(ls);
}
- ssa_set_def(ls, bptr->nr, ls->var[var_index][s->type]);
-}
+#endif
+/* dead_code_elimination(jd, gd); */
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("Phi after dead code elemination\n");
+ ssa_print_phi(ls, gd);
+ ssa_print_lt(ls);
+ }
+#endif
+/* copy_propagation(jd, gd); */
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("Phi after copy propagation\n");
+ ssa_print_phi(ls, gd);
+ ssa_print_lt(ls);
+ }
+#endif
-void ssa_set_interface(codegendata *cd, lsradata *ls, basicblock *bptr) {
- stackptr out, in;
- int in_d, out_d;
+ ssa_generate_phi_moves(jd, gd);
+ transform_BB(jd, gd);
- out = bptr->outstack;
- in = bptr->instack;
- in_d = bptr->indepth;
- out_d = bptr->outdepth;
- /* ignore top Stackelement of instack in case of EXH or SBR blocks */
- /* These are no Interface stackslots! */
- if ((bptr->type == BBTYPE_EXH) ||
- (bptr->type == BBTYPE_SBR)) {
- in_d--;
- in = in->prev;
- }
+#ifdef SSA_DEBUG_CHECK
+ {
+ int i, j, pred, in_d, out_d;
+ graphiterator iter_pred;
+ s4 *in, *out;
+ bool phi_define;
+ methodinfo *m;
- for(;(in_d > out_d); in_d--, in = in->prev);
+ m = jd->m;
- while((out != NULL)) {
- if (in_d == out_d) {
- if (in != out) {
- /* out interface stackslot is defined in this basic block */
- ssa_set_interface_(cd, ls, bptr, out, out_d - 1);
+ for(i = 0; i < ls->basicblockcount; i++) {
+ if (ls->basicblocks[i]->indepth != 0) {
+ pred = graph_get_first_predecessor(gd, i, &iter_pred);
+ for (; (pred != -1); pred = graph_get_next(&iter_pred)) {
+ in_d = ls->basicblocks[i]->indepth - 1;
+ in = ls->basicblocks[i]->invars;
+ for (; in_d >= 0; in_d--) {
+ phi_define = false;
+ for (j = 0; (!phi_define) && (j<ls->ssavarcount); j++) {
+ if (ls->phi[i][j] != NULL)
+ if (ls->phi[i][j][0] == in[in_d])
+ phi_define = true;
+ }
+ if (!phi_define) {
+ /* in not defined in phi function -> check with */
+ /* outstack(s) of predecessor(s) */
+ out_d = ls->basicblocks[pred]->outdepth - 1;
+ out = ls->basicblocks[pred]->outvars;
+ _SSA_ASSERT(out_d >= in_d);
+ for(; out_d > in_d; out_d--);
+ if ((in[in_d] != out[out_d]) ||
+ (VAR(in[in_d])->flags != VAR(out[out_d])->flags)) {
+ printf("Method: %s %s\n",
+ m->class->name->text, m->name->text);
+ printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
+ if (compileverbose)
+ printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
+/* else */
+/* _SSA_ASSERT(0); */
+ }
+ }
+ }
+ }
}
- out = out->prev;
- out_d--;
- in = in->prev;
- in_d--;
- } else if (in_d < out_d ) {
- /* out interface stackslot is defined in this basic block */
- ssa_set_interface_(cd, ls, bptr, out, out_d - 1);
- out = out->prev;
- out_d--;
}
}
+
+#endif
+
+
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ ssa_print_trees(jd, gd, dd);
+#endif
}
-/*********************************************************************
-Initialise needed Data structures
-*********************************************************************/
+/* ssa_init *******************************************************************
+
+Initialise data structures for ssa
+
+IOVARS of same stackdepth and same type are coalesced:
+interface_map[ 5 * stackdepth + type ] = new_varindex with
+0 <= new_varindex < ls->ssavarcount
+
+TODO: check if coalescing of IOVARS of same stackdepth and type only of adjacent
+basic blocks could decrease the number of phi functions and so improve ssa
+analysis performance!
+
+All LOCALVARS and IOVARS get a new unique varindex:
+ls->new_varindex[0..jd->varcount[ = new_varindex with
+0 <= new_varindex < ls->ssavarcount
+
+The jd->varcount bits long bitvectors ls->var_def[0..jd->basicblockindex+1[
+ are set to the definitions of LOCALVARS and IOVARS. (So the only the first
+ls->ssavarcount bits of each of these vectors contain valid data, but
+ls->ssavarcount is computed at the same time as the definitons are stored.)
+
+The basic block number used as index for the bitvector array ls->var_def is
+already shifted by one to make space for the new basic block 0 for parameter
+initialization.
+
+******************************************************************************/
void ssa_init(jitdata *jd) {
- int p, t;
- methoddesc *md;
- int i, b_index, len;
- int lifetimes;
- stackptr src, dst, tmp;
+ int p, t, v;
+ methoddesc *md;
+ int i, l, b_index, len;
instruction *iptr;
basicblock *bptr;
+ s4 *interface_map; /* holds an new unique index for every used */
+ /* basic block inoutvar described by a dupel */
+ /*(depth,type). Used to coalesce the inoutvars*/
+ methodinfo *m;
+ lsradata *ls;
+ builtintable_entry *bte;
- methodinfo *m;
- codegendata *cd;
- registerdata *rd;
- lsradata *ls;
-
- m = jd->m;
- cd = jd->cd;
- rd = jd->rd;
ls = jd->ls;
+ m = jd->m;
md = m->parseddesc;
+
#if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE)
-#if defined(SSA_DEBUG_VERBOSE)
+# if defined(SSA_DEBUG_VERBOSE)
if (compileverbose) {
printf("%s %s ",m->class->name->text, m->name->text);
if (jd->isleafmethod)
printf("**Leafmethod**");
printf("\n");
}
-#endif
- if (strcmp(m->class->name->text,"java/util/Properties")==0)
- if (strcmp(m->name->text,"load")==0)
-#if defined(SSA_DEBUG_VERBOSE)
+# endif
+ if (strcmp(m->class->name->text,"spec/benchmarks/_213_javac/Parser")==0)
+ if (strcmp(m->name->text,"parseTerm")==0)
+# if defined(SSA_DEBUG_VERBOSE)
if (compileverbose)
printf("12-------------------12\n");
-#else
+# else
{ int dummy=1; dummy++; }
-#endif
+# endif
#endif
#ifdef SSA_DEBUG_VERBOSE
if (compileverbose)
- printf("ssa_init: basicblockcount %3i maxlocals %3i\n",
- m->basicblockcount, jd->maxlocals);
+ printf("ssa_init: basicblockcount %3i localcount %3i\n",
+ jd->basicblockcount, jd->localcount);
#endif
- ls->num_defs = DMNEW(int, jd->maxlocals * 5 + cd->maxstack * 5);
- ls->var_to_index = DMNEW(int, jd->maxlocals * 5 + cd->maxstack * 5);
- ls->var = DMNEW(int *, jd->maxlocals + cd->maxstack);
- t = 0;
- for(p = 0; p < jd->maxlocals + cd->maxstack; p++) {
- ls->var[p] = DMNEW(int, 5);
- for(i = 0; i < 5; i++) {
- ls->var[p][i] = -1;
- ls->num_defs[t++] = 0;
- }
+
+ /* As first step all definitions of local variables and in/out vars are */
+ /* gathered. in/outvars are coalesced for same type and depth */
+ /* "normal" tempvars (just living within one basicblock are) ignored */
+
+ /* ls->var holds the index to jd->vars */
+
+ ls->num_defs = DMNEW(int, jd->varcount);
+ ls->new_varindex = DMNEW(int , jd->varcount);
+
+ for(p = 0; p < jd->varcount; p++) {
+ ls->num_defs[p] = 0;
+ ls->new_varindex[p] = UNUSED;
}
+
/* init Var Definition bitvectors */
- ls->var_def = DMNEW(int *, m->basicblockcount + 1);
- for(i = 0; i <= m->basicblockcount; i++) {
- ls->var_def[i] = bv_new(jd->maxlocals * 5 + cd->maxstack * 5);
+
+ ls->var_def = DMNEW(int *, jd->basicblockcount + 1);
+ for(i = 0; i < jd->basicblockcount + 1; i++) {
+ ls->var_def[i] = bv_new(jd->varcount);
}
- ls->uses = 0;
- ls->max_vars = 0; /* no Vars seen till now */
- /* A new Var Index will be created by SSA */
- /* since locals[Index][Type] is a quite sparse array */
- /* and locals will be renamed anyway by SSA */
- ls->max_locals = 0; /* unique index for every local_var/type pair*/
- ls->max_interfaces = -1; /* unique index for every interface/type pair*/
- /* interfaces are < 0, locals > 0 */
+
+ ls->ssavarcount = 0;
+
/* Add parameters first in right order, so the new local indices */
/* 0..p will correspond to "their" parameters */
/* They get defined at the artificial Block 0, the real method bbs will be*/
/* moved to start at block 1 */
- for (p = 0, i = 0; p < md->paramcount; p++) {
- t = md->paramtypes[p].type;
- ssa_set_local_def(ls, -1, i, t);
- i++;
+ /* don't look at already eliminated (not used) parameters (locals) */
+
+ for (p = 0, l = 0; p < md->paramcount; p++) {
+ t = md->paramtypes[p].type;
+ i = jd->local_map[l * 5 + t];
+ l++;
if (IS_2_WORD_TYPE(t)) /* increment local counter a second time */
- i++; /* for 2 word types */
+ l++; /* for 2 word types */
+ if (i == UNUSED)
+ continue;
+ ssa_set_local_def(ls, -1, i);
}
- lifetimes = 0;
- bptr = m->basicblocks;
+ _SSA_ASSERT(ls->ssavarcount < jd->varcount);
+
+ /* coalesce bb in/out vars */
+
+ interface_map = DMNEW(s4, jd->stackcount * 5);
+ for(i = 0; i < jd->stackcount * 5; i++)
+ interface_map[i] = UNUSED;
+
+ bptr = jd->basicblocks;
for(; bptr != NULL; bptr = bptr->next) {
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ printf("ssa_init: BB %3i flags %3x\n",bptr->nr, bptr->flags);
+#endif
if (bptr->flags >= BBREACHED) {
+
/* 'valid' Basic Block */
+
b_index = bptr->nr;
- /* Scan Number of Stack Lifetimes */
- lifetimes += m->basicblocks[b_index].indepth;
+ len = bptr->icount;
+ iptr = bptr->iinstr;
+ ssa_set_interface(jd, bptr, interface_map);
- dst = m->basicblocks[b_index].instack;
- len = m->basicblocks[b_index].icount;
- iptr = m->basicblocks[b_index].iinstr;
- for (;len>0; len--, iptr++) {
- src = dst;
- dst = iptr->dst;
-
- /* Reset "leftover" LOCALVAR stackslots */
- switch(iptr->opc) {
- case ICMD_DUP:
- lifetimes +=1;
- if (dst->varkind != ARGVAR)
- dst->varkind = TEMPVAR;
- case ICMD_SWAP:
- case ICMD_DUP2:
- lifetimes += 2;
- for(i=0, tmp = dst; i < 2; i++, tmp = tmp->prev)
- if (tmp->varkind != ARGVAR)
- tmp->varkind = TEMPVAR;
- break;
- case ICMD_DUP_X1:
- lifetimes += 3;
- for(i=0, tmp = dst; i < 3; i++, tmp = tmp->prev)
- if (tmp->varkind != ARGVAR)
- tmp->varkind = TEMPVAR;
- break;
- case ICMD_DUP2_X1:
- lifetimes += 5;
- for(i=0, tmp = dst; i < 5; i++, tmp = tmp->prev)
- if (tmp->varkind != ARGVAR)
- tmp->varkind = TEMPVAR;
- break;
- case ICMD_DUP_X2:
- lifetimes += 4;
- for(i=0, tmp = dst; i < 4; i++, tmp = tmp->prev)
- if (tmp->varkind != ARGVAR)
- tmp->varkind = TEMPVAR;
- break;
- case ICMD_DUP2_X2:
- lifetimes += 6;
- for(i=0, tmp = dst; i < 6; i++, tmp = tmp->prev)
- if (tmp->varkind != ARGVAR)
- tmp->varkind = TEMPVAR;
- break;
+ /* !!!!!!!!! not true for now !!!!!!!!! */
+ /* All baseline optimizations from stack.c are turned off for */
+ /* SSA! */
- case ICMD_ILOAD:
- case ICMD_LLOAD:
- case ICMD_FLOAD:
- case ICMD_DLOAD:
- case ICMD_ALOAD:
- if (( dst != NULL) && (src != dst))
- lifetimes++;
- dst->varkind = TEMPVAR;
- if (dst->varnum < 0)
- dst->varnum = 0;
- ssa_set_use(ls, b_index, iptr->op1,
- iptr->opc - ICMD_ILOAD);
- break;
-
- case ICMD_IINC:
- if (( dst != NULL) && (src != dst))
- lifetimes++;
- /* For SSA IINC has to be handled as a seperate LOAD */
- /* and STORE. The target local index is held in */
- /* val._i.op1_t, The immediate val.i is held in */
- /* val._i.i */
- {
- int v;
- v = iptr->val.i;
- iptr->val._i.op1_t = iptr->op1;
- iptr->val._i.i = v;
- }
+ for (; len > 0; len--, iptr++) {
- ssa_set_use(ls, b_index, iptr->op1,TYPE_INT);
- ssa_set_local_def(ls, b_index,
- iptr->val._i.op1_t, TYPE_INT);
- break;
+ /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
+ /* an optional dst - so they to be checked first */
- case ICMD_ISTORE:
- case ICMD_LSTORE:
- case ICMD_FSTORE:
- case ICMD_DSTORE:
- case ICMD_ASTORE:
- src->varkind = TEMPVAR;
- if (src->varnum < 0)
- src->varnum =0;
- ssa_set_local_def(ls, b_index, iptr->op1,
- iptr->opc - ICMD_ISTORE);
- break;
+ v = UNUSED;
+ if (icmd_table[iptr->opc].dataflow == DF_INVOKE) {
+ INSTRUCTION_GET_METHODDESC(iptr,md);
+ if (md->returntype.type != TYPE_VOID)
+ v = iptr->dst.varindex;
+ }
+ else if (icmd_table[iptr->opc].dataflow == DF_BUILTIN) {
+ bte = iptr->sx.s23.s3.bte;
+ md = bte->md;
+ if (md->returntype.type != TYPE_VOID)
+ v = iptr->dst.varindex;
+ }
+ else if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE) {
+ v = iptr->dst.varindex;
+ }
+ if (v != UNUSED) {
+ if (( v < jd->localcount) || ( VAR(v)->flags & INOUT )) {
+ /* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */
+
+/* _SSA_ASSERT(ls->new_varindex[v] != UNUSED); */
+ ssa_set_local_def(ls, b_index, v);
+ }
+ }
+ }
+ }
+ }
+ _SSA_ASSERT(ls->ssavarcount < jd->varcount);
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
- default:
- if (( dst != NULL) && (src != dst))
- lifetimes++;
+ printf("ssa_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
+ ls->ssavarcount);
+ for(i = 0; i < jd->varcount; i++) {
+ if ((i < jd->localcount) || ( VAR(i)->flags & INOUT)) {
+ printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
+ ssa_show_variable(jd, i, VAR(i),0);
+ if (i < ls->ssavarcount) {
+ printf(" -> %3i", ls->new_varindex[i]);
}
+ printf("\n");
}
- ssa_set_interface(cd, ls, &(m->basicblocks[b_index]));
}
}
- ls->maxlifetimes = lifetimes;
- ls->lifetimecount = lifetimes + jd->maxlocals * (TYPE_ADR+1);
+#endif
+}
+
+/* ssa_set_def ****************************************************************
+
+Helper for ssa_set_local_def and ssa_set_interface
+
+The definition of a var is stored in the bitvector array ls->var_def.
+
+The number of definitons of each var is counted, so the number of new vars with
+SSA is known.
+
+******************************************************************************/
+
+void ssa_set_def(lsradata *ls, int b_index, int varindex) {
+
+ /* b_index + 1 to leave space for the param init block 0 */
+
+ bv_set_bit(ls->var_def[b_index + 1], varindex);
+
+ /* count number of defs for every var since SSA */
+ /* will create a new var for every definition */
+
+ ls->num_defs[varindex]++;
+}
+
+/* ssa_set_local_def **********************************************************
+
+Helper for ssa_init
+
+Assigns a new unique index for the local var varindex (if not already done so)
+and then calls ssa_set_def to remember the definition in the bitvector array
+ls->var_def
+
+******************************************************************************/
+
+void ssa_set_local_def(lsradata *ls, int b_index, int varindex) {
+
+ if (ls->new_varindex[varindex] == UNUSED) {
+ ls->new_varindex[varindex] = ls->ssavarcount++;
+ }
+
+ ssa_set_def(ls, b_index, ls->new_varindex[varindex]);
+}
+
+/* ssa_set_local_def **********************************************************
+
+Helper for ssa_set_interface
+
+IN: ls pointer to lsradata structure
+ iovar varindex of INOUTVAR to process
+ map_index stackdepth * 5 + type, used for coalescing IOVARS.
+
+IN/OUT
+ interface_map used for coalescing IOVARS. interface_map[map_index] ==
+ UNUSED, if this map_index (==stackdepth,type tupel) did not
+ occur till now. Then interface_map[map_index] will be set
+ to a new unique index.
+ ls->new_varindex will be set to this new unique index to map the old
+ varindizes to the new ones.
+
+Assigns a new unique index for the local var varindex (if not already done so)
+and then calls ssa_set_def to remember the definition in the bitvector array
+ls->var_def
+
+******************************************************************************/
+
+void ssa_set_iovar(lsradata *ls, s4 iovar, int map_index, s4 *interface_map) {
+ if (interface_map[map_index] == UNUSED)
+ interface_map[map_index] = ls->ssavarcount++;
+
+ ls->new_varindex[iovar] = interface_map[map_index];
+}
+
+
+/* ssa_set_interface ***********************************************************
+
+Helper for ssa_init
+
+IN: ls pointer to lsradata structure
+ *bptr pointer to the basic block to be processed
+
+IN/OUT
+ interface_map used for coalescing IOVARS. interface_map[map_index] ==
+ UNUSED, if this map_index (==stackdepth,type tupel) did not
+ occur till now. Then interface_map[map_index] will be set
+ to a new unique index. (see ssa_set_iovar)
+
+Searches the basic block given by *bptr for IN and OUTVARS and coalesces them
+for each unique stackdepth,type dupel. For each OUTVAR with a different or no
+INVAR at the same stackdepth the definition of this OUTVAR in this basic block
+is remembered in ls->var_def. (see ssa_set_def)
+
+******************************************************************************/
+
+void ssa_set_interface(jitdata *jd, basicblock *bptr, s4 *interface_map) {
+ s4 *out, *in;
+ int in_d, out_d;
+ int o_map_index, i_map_index;
+ lsradata *ls;
+
+ ls = jd->ls;
+
+ out = bptr->outvars;
+ in = bptr->invars;
+ in_d = bptr->indepth - 1;
+ out_d = bptr->outdepth - 1;
+
+ /* ignore top Stackelement of instack in case of EXH or SBR blocks */
+ /* These are no Interface stackslots! */
+ if ((bptr->type == BBTYPE_EXH) ||
+ (bptr->type == BBTYPE_SBR)) {
+ in_d--;
+ }
+
+ /* invars with no corresponding outvars are not defined here */
+ /* just set up the interface_map */
+
+ for(;(in_d > out_d); in_d--) {
+ i_map_index = in_d * 5 + VAR(in[in_d])->type;
+ ssa_set_iovar(ls, in[in_d], i_map_index, interface_map);
+ }
+
+ while((out_d >= 0)) {
+ /* set up interface_map */
+
+ o_map_index = out_d * 5 + VAR(out[out_d])->type;
+ if (in_d >= 0) {
+ i_map_index = in_d * 5 + VAR(in[in_d])->type;
+ ssa_set_iovar(ls, in[in_d], i_map_index, interface_map);
+ }
+ ssa_set_iovar(ls, out[out_d], o_map_index, interface_map);
+ if (in_d == out_d) {
+ if (in[in_d] != out[out_d]) {
+
+ /* out interface stackslot is defined in this basic block */
+
+/* ssa_set_def(ls, bptr->nr + 1, ls->new_varindex[out[out_d]]); */
+ }
+ out_d--;
+ in_d--;
+ }
+ else {
+ /* in_d < out_d */
+ /* out interface stackslot is defined in this basic block */
+
+/* ssa_set_def(ls, bptr->nr + 1, ls->new_varindex[out[out_d]]); */
+ out_d--;
+ }
+ }
}
+/* ssa_place_phi_functions *****************************************************
+
+ls->phi[n][a][p] is created and populated.
+
+For each basicblock Y in the dominance frontier of a basicblock n (0 <= n <
+ls->basicblockcount)in which a variable (0 <= a < ls->ssavarcount) is defined an
+entry in ls->phi[Y][a] is created.
+This entry is an array with the number of predecessors of Y elements + 1 elements.
+This elements are all set to the variable a and represent the phi function which
+will get ai = phi(ai1, ai2, ..., aip) after ssa_rename.
+
+*******************************************************************************/
+
-void ssa_place_phi_functions(codegendata *cd, lsradata *ls, graphdata *gd,
- dominatordata *dd)
+void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd)
{
int a,i,j,n,Y;
bitvector *def_sites;
- bitvector *A_phi; /* [0..ls->basicblockcount[ of ls->max_vars Bit */
+ bitvector *A_phi; /* [0..ls->basicblockcount[ of ls->ssavarcount Bit */
worklist *W;
int num_pred;
- bool add_phi;
- stackptr s;
+
+ lsradata *ls;
+
+ ls = jd->ls;
W = wl_new(ls->basicblockcount);
- def_sites = DMNEW(bitvector, ls->max_vars);
- for(a = 0; a < ls->max_vars; a++)
+ def_sites = DMNEW(bitvector, ls->ssavarcount);
+ for(a = 0; a < ls->ssavarcount; a++)
def_sites[a] = bv_new(ls->basicblockcount);
ls->phi = DMNEW(int **, ls->basicblockcount);
A_phi = DMNEW(bitvector, ls->basicblockcount);
for(i = 0; i < ls->basicblockcount; i++) {
- ls->phi[i] = DMNEW(int *, ls->max_vars);
- for(j = 0; j < ls->max_vars; j++)
+ ls->phi[i] = DMNEW(int *, ls->ssavarcount);
+ for(j = 0; j < ls->ssavarcount; j++)
ls->phi[i][j] = NULL;
- A_phi[i] = bv_new(ls->max_vars);
+ A_phi[i] = bv_new(ls->ssavarcount);
}
- for(n = 0; n < ls->basicblockcount; n++)
- for(a = 0; a < ls->max_vars; a++)
+ /* copy var_def to def_sites */
+ /* var_def is valid for 0.. jd->basicblockcount (bb 0 for param init) */
+
+ for(n = 0; n <= jd->basicblockcount; n++)
+ for(a = 0; a < ls->ssavarcount; a++)
if (bv_get_bit(ls->var_def[n], a))
bv_set_bit(def_sites[a], n);
#ifdef SSA_DEBUG_VERBOSE
if (compileverbose) {
printf("var Definitions:\n");
- for(i = 0; i < ls->max_vars; i++) {
+ for(i = 0; i < ls->ssavarcount; i++) {
printf("def_sites[%3i]=%p:",i,(void *)def_sites[i]);
for(j = 0; j < ls->basicblockcount; j++) {
if ((j % 5) == 0) printf(" ");
}
#endif
- for(a = 0; a < ls->max_vars; a++) {
+ for(a = 0; a < ls->ssavarcount; a++) {
+
/* W<-def_sites(a) */
+
for(n = 0; n < ls->basicblockcount; n++)
if (bv_get_bit(def_sites[a],n)) {
wl_add(W, n);
/* a is not a Element of A_phi[Y] */
/* a <- phi(a,a...,a) to be inserted at top of Block Y */
/* phi has as many arguments, as Y has predecessors */
-
+#if 0
#if 0
/* do not add a phi function for interface stackslots */
/* if a predecessor is not a def site of a <==> */
/* the block does not have the corresponding inslot*/
- if ((ls->var_to_index[a] >= 0) ||
- (bv_get_bit(def_sites[a],
- graph_get_first_predecessor(gd, Y, &iter))))
+
+/* if ((ls->var_to_index[a] >= 0) || */
+/* (bv_get_bit(def_sites[a], */
+/* graph_get_first_predecessor(gd, Y, &iter)))) */
+
#endif
/* for interface stackslots add a phi function only */
/* if the basicblock has the corresponding incoming */
/* stackslot -> it could be, that the stackslot is */
/* not live anymore at Y */
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- if (ls->var_to_index[a] < 0)
- printf("SS CHeck BB %3i ID %3i V2I %3i A %3i ML %3i\n",Y,
- ls->basicblocks[Y]->indepth,
- ls->var_to_index[a], a, jd->maxlocals);
-#endif
- /* Add Locals in any case */
- add_phi = (ls->var_to_index[a] >= 0);
- if (!add_phi) {
- /* Stackslot */
- s = ls->basicblocks[Y]->instack;
- for(i = ls->basicblocks[Y]->indepth-1; i>=0; i--, s = s->prev) {
- _SSA_ASSERT(s != 0);
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- if (ls->var_to_index[a] < 0)
- printf(" Depth %3i Var %3i\n",i,
- ls->var[i + jd->maxlocals][s->type]);
#endif
- if (ls->var[i + jd->maxlocals][s->type] == a) {
- add_phi=true;
- break;
- }
- }
- }
- if (add_phi)
- {
- num_pred = graph_get_num_predecessor(gd, Y);
- ls->phi[Y][a] = DMNEW(int, num_pred + 1);
- for (j = 0; j < num_pred + 1; j++)
- ls->phi[Y][a][j] = a;
- /* increment the number of definitions of a by one */
- /* for this phi function */
- ls->num_defs[a]++;
- }
-
+ num_pred = graph_get_num_predecessor(gd, Y);
+ ls->phi[Y][a] = DMNEW(int, num_pred + 1);
+ for (j = 0; j < num_pred + 1; j++)
+ ls->phi[Y][a][j] = a;
+ /* increment the number of definitions of a by one */
+ /* for this phi function */
+ ls->num_defs[a]++;
+
bv_set_bit(A_phi[Y], a);
if (bv_get_bit(ls->var_def[Y],a)==0) {
/* Iterated Dominance Frontier Criterion:*/
}
}
-void ssa_Rename_init(methodinfo *m, codegendata *cd, lsradata *ls, graphdata *gd)
+/* ssa_rename ******************************************************************
+
+Rename the variables a (0 <= a < ls->ssavarcount) so that each new variable
+has only one definition (SSA form).
+
+ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
+ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
+ definition of each old var.
+ls->varcount_with_indices will be se to the new maximum varcount of LOCAL
+ and IOVARS.
+
+All other vars (TEMPVAR and PREALLOC) will get a new unique index above
+ls->varcount_with_indices.
+
+jd->var and jd->varcount will be set for this renamed vars.
+
+*******************************************************************************/
+
+void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd)
{
+ int i, mi, l, j, p, t;
+ int type, flags;
+ methoddesc *md = jd->m->parseddesc;
+
+ varinfo *new_vars;
+ lsradata *ls;
+
+ ls = jd->ls;
+
+ ssa_rename_init(jd, gd);
+
+ /* Consider definition of Local Vars initialized with Arguments */
+ /* in Block 0 */
+ /* init is regarded as use too-> ssa_rename_use ->bullshit!!*/
+ for (p = 0, l= 0; p < md->paramcount; p++) {
+ t = md->paramtypes[p].type;
+ mi = l * 5 + t;
+ i = jd->local_map[mi];
+ l++;
+ if (IS_2_WORD_TYPE(t))
+ l++;
+ if (i == UNUSED)
+ continue;
+ /* !!!!! locals are now numbered as the parameters !!!! */
+ /* !!!!! no additional increment for 2 word types !!!!! */
+ /* this happens later on! here we still need the increment */
+ /* index of var can be in the range from 0 up to not including */
+ /* CD->maxlocals */
+
+ /* ignore return value, since first definition gives 0 -> */
+ /* no rename necessary */
- int a, i, t, p;
- int i_l, i_i;
+ i = ls->new_varindex[i];
+ j = ssa_rename_def_(ls, i);
+ _SSA_ASSERT(j == 0);
+ jd->local_map[mi] = i;
+ }
+ ssa_rename_(jd, gd, dd, 0);
+
+#if 0
+ /* DO _NOT_ DO THIS! Look at java.util.stringtokenizer.counttokens! */
+ /* if there is no use of the defined Var itself by the phi function */
+ /* for a loop path, in which this var is not used, it will not be life */
+ /* in this path and overwritten! */
+
+ /* Invalidate all xij from phi(xi0)=xi1,xi2,xi3,..,xin with xij == xi0 */
+ /* this happens if the phi function is the first definition of x or in a */
+ /* path with a backedge xi has no definition */
+ /* a phi(xij) = ...,xij,... with the only use and definition of xij by */
+ /* this phi function would otherwise "deadlock" the dead code elemination */
+ /* invalidate means set it to ls->max_vars_with_indices */
+ /* a phi function phi(xi0)=xi1,xi2,...xin wiht xij == xi0 for all j in */
+ /* [1,n] can be removed */
+
+ for(i = 0; i < ls->ssavarcount; i++) {
+ for(t = 0; t < ls->basicblockcount; t++) {
+ if (ls->phi[t][i] != 0) {
+ remove_phi = true;
+ for(p = 1; p <= graph_get_num_predecessor(gd, t); p++) {
+ if (ls->phi[t][i][0] == ls->phi[t][i][p])
+ ls->phi[t][i][p] = ls->varcount_with_indices;
+ else
+ remove_phi = false;
+ }
+ }
+ if (remove_phi)
+ ls->phi[t][i] = NULL;
+ }
+ }
+#endif
+
+#if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE)
+# if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose) {
+ printf("%s %s ",jd->m->class->name->text, jd->m->name->text);
+ if (jd->isleafmethod)
+ printf("**Leafmethod**");
+ printf("\n");
+ }
+# endif
+ if (strcmp(jd->m->class->name->text,"fp")==0)
+ if (strcmp(jd->m->name->text,"testfloat")==0)
+# if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf("12-------------------12\n");
+# else
+ { int dummy=1; dummy++; }
+# endif
+#endif
+ /* recreate rd->locals[][] */
+ /* now only one (local_index/type) pair exists anymore */
+ /* all var[t][i] with var_to_index[var[t][i]] >= 0 are locals */
+ /* max local index after SSA indexing is in ls->local_0[ls->max_locals] */
+
+ new_vars = DMNEW(varinfo, ls->vartop);
+ for(i = 0; i < ls->vartop ; i++)
+ new_vars[i].type = UNUSED;
+ for(i = 0; i < jd->varcount; i++) {
+ p = ls->new_varindex[i];
+ if (p != UNUSED) {
+ if (p < ls->ssavarcount)
+ p = ls->var_0[p];
+ new_vars[p].type = VAR(i)->type;
+ new_vars[p].flags = VAR(i)->flags;
+ ls->lifetime[p].v_index = p;
+ ls->lifetime[p].type = VAR(i)->type;
+ }
+ }
+
+ /* take care of newly indexed local & in/out vars */
+
+ for(i = 0; i < ls->ssavarcount; i++) {
+ j = ls->var_0[i];
+ type = new_vars[j].type;
+ flags = new_vars[j].flags;
+ j++;
+ for (; j < ls->var_0[i + 1]; j++) {
+ new_vars[j].type = type;
+ new_vars[j].flags = flags;
+ ls->lifetime[j].v_index = j;
+ ls->lifetime[j].type = type;
+ }
+ }
+
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+
+ printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
+ ls->ssavarcount);
+ for(i = 0; i < jd->varcount; i++) {
+ printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
+ ssa_show_variable(jd, i, VAR(i),0);
+ j = ls->new_varindex[i];
+ if ((j != UNUSED) && (j < ls->ssavarcount))
+ printf(" -> %3i ... %3i", ls->var_0[j], ls->var_0[j + 1] - 1);
+ else
+ printf(" -> %3i", j);
+ printf("\n");
+ }
+ }
+#endif
+
+ jd->var = new_vars;
+ jd->varcount = ls->vartop;
+ jd->vartop = ls->vartop;
+
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
+ ls->ssavarcount);
+ for(i = 0; i < jd->varcount; i++) {
+ printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
+ ssa_show_variable(jd, i, VAR(i),0);
+ printf("\n");
+ }
+ }
+#endif
+}
+
+/* ssa_rename_init *************************************************************
+
+Setup the data structure for ssa_rename
+
+ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
+ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
+ definition of each old var.
+ls->varcount_with_indices will be se to the new maximum varcount of LOCAL
+ and IOVARS.
+
+All other vars (TEMPVAR and PREALLOC) will get a new unique index above
+ls->varcount_with_indices.
+
+jd->var and jd->varcount will be set for this renamed vars.
+
+*******************************************************************************/
+
+void ssa_rename_init(jitdata *jd, graphdata *gd)
+{
+ int a, i, p;
+ lsradata *ls;
+
+ ls = jd->ls;
/* set up new locals */
- /* ls->var[index][type] holds the new unique index */
- /* in the range of [0..ls-max_vars[ */
+ /* ls->new_varindex[0..jd->varcount[ holds the new unique index */
+ /* for locals and iovars */
+
/* ls->num_defs[index] gives the number of indizes which will be created */
/* from SSA */
- /* -> vars will be numbered in this sequence: L0(0)..L0(i) L1(0)..L1(j).*/
- /* ls->var[index][type] will point to each LX(0) */
-
- /* as first step cummulate the num_defs array */
- /* for locals */
- /* last element is the maximum local count */
- ls->local_0 = DMNEW(int, ls->max_locals + 1);
- ls->interface_0 = DMNEW(int, -ls->max_interfaces);
- ls->local_0[0] = 0;
- ls->interface_0[0] = 0;
- ls->max_vars_with_indices = 0;
- for(i = 0, i_i = 1, i_l = 1; i < ls->max_vars; i++) {
- ls->max_vars_with_indices += ls->num_defs[i];
- if (ls->var_to_index[i] >= 0) {
- /* local var */
- ls->local_0[i_l] = ls->local_0[i_l-1] + ls->num_defs[i];
- ls->var_to_index[i] = ls->local_0[i_l-1];
- i_l++;
- } else {
- /* interface stackslot */
- ls->interface_0[i_i] = ls->interface_0[i_i-1] + ls->num_defs[i];
- ls->var_to_index[i] = -ls->interface_0[i_i-1] - 1;
- i_i++;
- }
+
+ /* -> vars will be numbered in this sequence: L0(0)..L0(i) L1(0)..L1(j) ..*/
+ /* ls->var_0[X] will point to each LX(0) */
+ /* ls->var_0[ls->ssavarcount] will hold ls->varcount_with_indices */
+
+ /* as first step cummulate the num_defs array for locals and iovars */
+ /* last element is the maximum var count */
+
+ ls->var_0 = DMNEW(int, max(1, ls->ssavarcount + 1));
+ ls->var_0[0] = 0;
+ ls->varcount_with_indices = 0;
+ for(i = 0; i < ls->ssavarcount; i++) {
+ ls->varcount_with_indices += ls->num_defs[i];
+ ls->var_0[i+1] = ls->var_0[i] + ls->num_defs[i];
}
+#if 0
/* Change the var indices in phi from La to La(0) */
+
for(i = 0; i < ls->basicblockcount; i++)
- for (t = 0; t < ls->max_vars; t++)
- if (ls->phi[i][t] != NULL)
+ for (a = 0; a < ls->ssavarcount; a++)
+ if (ls->phi[i][a] != NULL)
for(p = 0; p < graph_get_num_predecessor(gd, i) + 1; p++)
- ls->phi[i][t][p] = ls->var_to_index[t];
+ ls->phi[i][a][p] = ls->var_0[a];
+#endif
/* Initialization */
- ls->count = DMNEW(int, ls->max_vars);
- ls->stack = DMNEW(int *, ls->max_vars);
- ls->stack_top = DMNEW(int, ls->max_vars);
- for(a = 0; a < ls->max_vars; a++) {
+
+ ls->count = DMNEW(int, max(1, ls->ssavarcount));
+ ls->stack = DMNEW(int *, max(1, ls->ssavarcount));
+ ls->stack_top = DMNEW(int, max(1, ls->ssavarcount));
+ for(a = 0; a < ls->ssavarcount; a++) {
ls->count[a] = 0;
ls->stack_top[a] = 0;
+
/* stack a has to hold number of defs of a Elements + 1 */
+
ls->stack[a] = DMNEW(int, ls->num_defs[a] + 1);
ls->stack[a][ls->stack_top[a]++] = 0;
}
- if (ls->max_locals > 0) {
+
+ if (ls->ssavarcount > 0) {
+
/* Create the num_var_use Array */
+
ls->num_var_use = DMNEW(int *, ls->basicblockcount);
for(i = 0; i < ls->basicblockcount; i++) {
- ls->num_var_use[i] =DMNEW(int, max(1, ls->local_0[ls->max_locals]));
- for(a = 0; a < ls->local_0[ls->max_locals]; a++)
+ ls->num_var_use[i] =DMNEW(int, max(1, ls->varcount_with_indices));
+ for(a = 0; a < ls->varcount_with_indices; a++)
ls->num_var_use[i][a] = 0;
}
+
/* Create the use_sites Array of Bitvectors*/
/* use max(1,..), to ensure that the array is created! */
- ls->use_sites = DMNEW(bitvector, max(1, ls->local_0[ls->max_locals]));
- for(a = 0; a < ls->local_0[ls->max_locals]; a++)
+
+ ls->use_sites = DMNEW(bitvector, max(1, ls->varcount_with_indices));
+ for(a = 0; a < ls->varcount_with_indices; a++)
ls->use_sites[a] = bv_new(ls->basicblockcount);
}
+
/* init lifetimes */
+ /* count number of TEMPVARs */
+
+ ls->lifetimecount = 0;
+ for(i = 0; i < jd->varcount; i++)
+ if ((i >= jd->localcount) || (!(jd->var[i].flags & (INOUT | PREALLOC))))
+ ls->lifetimecount++;
- ls->maxlifetimes = /*m*/ ls->maxlifetimes + ls->basicblockcount * m->maxstack;
- ls->lifetimecount = ls->maxlifetimes + ls->local_0[ls->max_locals]
- + cd->maxstack * 5;
+ ls->varcount = ls->varcount_with_indices + ls->lifetimecount;
+
+ ls->lifetimecount = ls->varcount;
ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
ls->lt_used = DMNEW(int, ls->lifetimecount);
ls->lt_int = DMNEW(int, ls->lifetimecount);
ls->lt_flt_count = 0;
ls->lt_mem = DMNEW(int, ls->lifetimecount);
ls->lt_mem_count = 0;
- for (i=0; i < ls->lifetimecount; i++) ls->lifetime[i].type = -1;
+ for (i=0; i < ls->lifetimecount; i++) {
+ ls->lifetime[i].type = UNUSED;
+ ls->lifetime[i].savedvar = 0;
+ ls->lifetime[i].flags = 0;
+ ls->lifetime[i].usagecount = 0;
+ ls->lifetime[i].bb_last_use = -1;
+ ls->lifetime[i].bb_first_def = -1;
+ ls->lifetime[i].use = NULL;
+ ls->lifetime[i].def = NULL;
+ ls->lifetime[i].last_use = NULL;
+ }
+ /* for giving TEMP and PREALLOC vars a new unique index */
+
+ ls->vartop = ls->varcount_with_indices;
+
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("ssa_rename_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
+ ls->ssavarcount);
+ for(i = 0; i < jd->varcount; i++) {
+ if ((i < jd->localcount) || ( VAR(i)->flags & INOUT)) {
+ printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
+ ssa_show_variable(jd, i, VAR(i),0);
+ if ((i < ls->ssavarcount) || (VAR(i)->flags & INOUT)) {
+ printf(" -> %3i", ls->new_varindex[i]);
+ }
+ printf("\n");
+ }
+ }
+ ssa_print_phi(ls, gd);
+ }
+#endif
}
-int ssa_Rename_def(lsradata *ls, int n, int a) {
+int ssa_rename_def_(lsradata *ls, int a) {
int i;
- _SSA_CHECK_BOUNDS(a,0,ls->max_vars);
+ _SSA_CHECK_BOUNDS(a,0,ls->ssavarcount);
ls->count[a]++;
i = ls->count[a] - 1;
/* push i on stack[a] */
return i;
}
-void ssa_Rename_use(lsradata *ls, int n, int a) {
- if (ls->max_locals > 0) {
+int ssa_rename_def(jitdata *jd, int *def_count, int a) {
+ int i, a1, ret;
+ lsradata *ls;
+
+ ls = jd->ls;
+
+ a1 = ls->new_varindex[a];
+ _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
+ if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
+ /* local or inoutvar -> normal ssa renaming */
+ _SSA_ASSERT((a < jd->localcount) || (VAR(a)->flags & INOUT));
+ /* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */
+
+ def_count[a1]++;
+ i = ssa_rename_def_(ls, a1);
+ ret = ls->var_0[a1] + i;
+ }
+ else {
+ /* TEMP or PREALLOC var */
+ if (a1 == UNUSED) {
+ ls->new_varindex[a] = ls->vartop;
+ ret = ls->vartop;
+ ls->vartop++;
+ _SSA_ASSERT( ls->vartop < ls->varcount);
+ }
+ else
+ ret = a1;
+ }
+ return ret;
+}
+
+void ssa_rename_use_(lsradata *ls, int n, int a) {
+ _SSA_CHECK_BOUNDS(a, 0, ls->varcount_with_indices);
+ if (ls->ssavarcount > 0) {
bv_set_bit(ls->use_sites[a], n);
ls->num_var_use[n][a]++;
}
}
-void ssa_Rename_(codegendata *cd, lsradata *ls, graphdata *gd,
- dominatordata *dd, int n) {
- int a, i, j, k, iindex, Y;
+int ssa_rename_use(lsradata *ls, int n, int a) {
+ int a1, i;
+ int ret;
+
+ a1 = ls->new_varindex[a];
+ _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
+ if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
+ /* local or inoutvar -> normal ssa renaming */
+ /* i <- top(stack[a]) */
+
+ _SSA_CHECK_BOUNDS(ls->stack_top[a1]-1, 0, ls->num_defs[a1]+1);
+ i = ls->stack[a1][ls->stack_top[a1] - 1];
+ _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a1]);
+
+ ret = ls->var_0[a1] + i;
+ }
+ else {
+ /* TEMP or PREALLOC var */
+ if (a1 == UNUSED) {
+ ls->new_varindex[a] = ls->vartop;
+ ret = ls->vartop;
+ ls->vartop++;
+ _SSA_ASSERT( ls->vartop < ls->varcount);
+ }
+ else
+ ret = a1;
+ }
+
+ return ret;
+}
+
+#ifdef SSA_DEBUG_VERBOSE
+void ssa_rename_print(instruction *iptr, char *op, int from, int to) {
+ if (compileverbose) {
+ printf("ssa_rename_: ");
+ if (iptr != NULL)
+ printf("%s ", opcode_names[iptr->opc]);
+ else
+ printf(" ");
+
+ printf("%s: %3i->%3i\n", op, from, to);
+ }
+}
+#endif
+
+void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n) {
+ int a, i, j, k, iindex, Y, v;
int in_d, out_d;
- instruction *iptr;
- int *def_count;
- /* [0..ls->max_vars[ Number of Definitions of this var in this */
+ int *def_count;
+ /* [0..ls->varcount[ Number of Definitions of this var in this */
/* Basic Block. Used to remove the entries off the stack at the */
/* end of the function */
-
- stackptr in, out;
+ instruction *iptr;
+ s4 *in, *out, *argp;
graphiterator iter_succ, iter_pred;
struct lifetime *lt;
+ methoddesc *md;
+ methodinfo *m;
+ builtintable_entry *bte;
+ lsradata *ls;
+
+ ls = jd->ls;
+ m = jd->m;
+
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ printf("ssa_rename_: BB %i\n",n);
+#endif
+
_SSA_CHECK_BOUNDS(n, 0, ls->basicblockcount);
- def_count = DMNEW(int, ls->max_vars);
- for(i = 0; i < ls->max_vars; i++)
+ def_count = DMNEW(int, max(1, ls->ssavarcount));
+ for(i = 0; i < ls->ssavarcount; i++)
def_count[i] = 0;
- /* change Store of possible phi functions from a0 to ai*/
- for(a = 0; a < ls->max_vars; a++)
+ /* change Store of possible phi functions from a to ai*/
+
+ for(a = 0; a < ls->ssavarcount; a++)
if (ls->phi[n][a] != NULL) {
def_count[a]++;
/* do not mark this store as use - maybee this phi function */
/* can be removed for unused Vars*/
- if (ls->var_to_index[a] >= 0)
- /* local var */
- ls->phi[n][a][0] += ssa_Rename_def(ls, n, a);
- else
- /* interface */
- ls->phi[n][a][0] -= ssa_Rename_def(ls, n, a);
+ j = ls->var_0[a] + ssa_rename_def_(ls, a);
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( NULL, "phi-st", ls->phi[n][a][0], j);
+#endif
+ ls->phi[n][a][0] = j;
}
- in = ls->basicblocks[n]->instack;
- in_d = ls->basicblocks[n]->indepth;
+ in = ls->basicblocks[n]->invars;
+ in_d = ls->basicblocks[n]->indepth - 1;
+
/* change use of instack Interface stackslots except top SBR and EXH */
/* stackslots */
+
if ((ls->basicblocks[n]->type == BBTYPE_EXH) ||
(ls->basicblocks[n]->type == BBTYPE_SBR)) {
in_d--;
- in = in->prev;
}
- out = ls->basicblocks[n]->outstack;
- out_d = ls->basicblocks[n]->outdepth;
+/* out = ls->basicblocks[n]->outvars; */
+/* out_d = ls->basicblocks[n]->outdepth - 1; */
+
+/* for(; out_d > in_d; out_d--); */
- for(;out_d > in_d; out = out->prev, out_d--);
+ for (; in_d >= 0; in_d--) {
+ /* Possible Use of ls->new_varindex[jd->var[in_d]] */
+ _SSA_ASSERT(ls->new_varindex[in[in_d]] != UNUSED);
+
+ a = ls->new_varindex[in[in_d]];
+ _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
- for (;in != NULL; in = in->prev, in_d--) {
- /* Possible Use of */
- /* ls->var[in_d - 1 + jd->maxlocals][in->type] */
- _SSA_CHECK_BOUNDS(in_d - 1 + jd->maxlocals, 0, jd->maxlocals + cd->maxstack);
- a = ls->var[in_d - 1 + jd->maxlocals][in->type];
- _SSA_CHECK_BOUNDS(a, 0, ls->max_vars);
/* i <- top(stack[a]) */
+
_SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
i = ls->stack[a][ls->stack_top[a]-1];
_SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
+
/* Replace use of x with xi */
+
#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- printf("Ren Use:BB %3i: stackslot: depth %3i old val: %3i Var,0: %3i varind: %3i\n", n, in_d, in->varnum, ls->var_to_index[a], ls->var_to_index[a]-i);
+ ssa_rename_print( NULL, "invar", in[in_d], ls->var_0[a]+i);
#endif
- in->varnum = ls->var_to_index[a] - i;
- lt = &(ls->lifetime[-in->varnum-1]);
- lt->v_index = in->varnum;
+ in[in_d] = ls->var_0[a] + i;
+ lt = ls->lifetime + in[in_d];
+
+ lt->v_index = in[in_d];
lt->bb_last_use = -1;
- lsra_add_ss(lt, in);
- in->varkind = TEMPVAR;
}
- in = ls->basicblocks[n]->instack;
-
+
iptr = ls->basicblocks[n]->iinstr;
+
for(iindex = 0; iindex < ls->basicblocks[n]->icount; iindex++, iptr++) {
- switch(iptr->opc) {
- case ICMD_ILOAD:
- case ICMD_LLOAD:
- case ICMD_FLOAD:
- case ICMD_DLOAD:
- case ICMD_ALOAD:
- _SSA_CHECK_BOUNDS(iptr->op1, 0, jd->maxlocals);
- a = ls->var[iptr->op1][iptr->opc - ICMD_ILOAD];
- _SSA_CHECK_BOUNDS(a, 0, ls->max_vars);
- /* i <- top(stack[a]) */
- _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
- i = ls->stack[a][ls->stack_top[a]-1];
- _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
- /* Replace use of x with xi */
-#if 0
- /* there are no LOCALVAR Stackslots with SSA */
- if ((iptr->dst->varkind == LOCALVAR) &&
- (iptr->dst->varnum == iptr->op1))
- iptr->dst->varnum = ls->var_to_index[a] + i;
-#endif
- iptr->op1 = ls->var_to_index[a] + i;
- ssa_Rename_use(ls, n, ls->var_to_index[a] + i);
+ /* check for use (s1, s2, s3 or special (argp) ) */
- break;
- case ICMD_ISTORE:
- case ICMD_LSTORE:
- case ICMD_FSTORE:
- case ICMD_DSTORE:
- case ICMD_ASTORE:
- /* replace definition of a with def of ai */
- _SSA_CHECK_BOUNDS(iptr->op1, 0, jd->maxlocals);
- a = ls->var[iptr->op1][iptr->opc - ICMD_ISTORE];
- _SSA_CHECK_BOUNDS(a, 0, ls->max_vars);
- def_count[a]++;
+ switch (icmd_table[iptr->opc].dataflow) {
+ case DF_3_TO_0:
+ case DF_3_TO_1: /* icmd has s1, s2 and s3 */
+ j = ssa_rename_use(ls, n, iptr->sx.s23.s3.varindex);
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( iptr, "s3 ", iptr->sx.s23.s3.varindex, j);
+#endif
+ iptr->sx.s23.s3.varindex = j;
- i = ssa_Rename_def(ls, n, a);
- _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
+ /* now "fall through" for handling of s2 and s1 */
- iptr->op1 = ls->var_to_index[a] + i;
- /* Mark Def as use, too. Since param initialisation is in var_def */
- /* and this would not remove this locals, if not used elsewhere */
- ssa_Rename_use(ls, n, ls->var_to_index[a] + i);
- break;
- case ICMD_IINC:
-
- /* Load from iptr->op1 */
- _SSA_CHECK_BOUNDS(iptr->op1, 0, jd->maxlocals);
- a = ls->var[iptr->op1][TYPE_INT];
- _SSA_CHECK_BOUNDS(a, 0, ls->max_vars);
- /* i <- top(stack[a]) */
- _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
- i = ls->stack[a][ls->stack_top[a]-1];
- _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
- /* Replace use of x with xi */
- iptr->op1 = ls->var_to_index[a] + i;
-
- ssa_Rename_use(ls, n, ls->var_to_index[a] + i);
- /* Store new(iinced) value in iptr->val._i.opq_t */
-
- /* replace definition of a with def of ai */
- _SSA_CHECK_BOUNDS(iptr->val._i.op1_t, 0, jd->maxlocals);
- a = ls->var[iptr->val._i.op1_t][TYPE_INT];
- _SSA_CHECK_BOUNDS(a, 0, ls->max_vars);
- def_count[a]++;
+ case DF_2_TO_0:
+ case DF_2_TO_1: /* icmd has s1 and s2 */
+ j = ssa_rename_use(ls, n, iptr->sx.s23.s2.varindex);
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( iptr, "s2 ", iptr->sx.s23.s2.varindex, j);
+#endif
+ iptr->sx.s23.s2.varindex = j;
- i = ssa_Rename_def(ls, n, a);
- _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
+ /* now "fall through" for handling of s1 */
- iptr->val._i.op1_t = ls->var_to_index[a] + i;
- /* Mark Def as use, too. Since param initialisation is in var_def */
- /* and this would not remove this locals, if not used elsewhere */
- ssa_Rename_use(ls, n, ls->var_to_index[a] + i);
+ case DF_1_TO_0:
+ case DF_1_TO_1:
+ case DF_MOVE:
+ case DF_COPY:
+ j = ssa_rename_use(ls, n, iptr->s1.varindex);
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( iptr, "s1 ", iptr->s1.varindex, j);
+#endif
+ iptr->s1.varindex = j;
+ break;
+ case DF_INVOKE:
+ case DF_BUILTIN:
+ case DF_N_TO_1:
+ /* do not use md->paramcount, pass-through stackslots have */
+ /* to be renamed, too */
+ i = iptr->s1.argcount;
+ argp = iptr->sx.s23.s2.args;
+ while (--i >= 0) {
+ j = ssa_rename_use(ls, n, *argp);
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( iptr, "arg", *argp, j);
+#endif
+ *argp = j;
+ argp++;
+ }
break;
}
- in = iptr->dst;
- }
- /* change def of outstack Interface stackslots */
- in = ls->basicblocks[n]->instack;
- in_d = ls->basicblocks[n]->indepth;
- out = ls->basicblocks[n]->outstack;
- out_d = ls->basicblocks[n]->outdepth;
-
- for(;in_d > out_d; in = in->prev, in_d--);
-
- for (;out != NULL; out = out->prev, out_d--) {
- if ((in_d < out_d) || (out != in)) {
- /* Def of ls->var[out_d - 1 + jd->maxlocals][out->type] */
- _SSA_CHECK_BOUNDS(out_d - 1 + jd->maxlocals, 0, jd->maxlocals + cd->maxstack);
- a = ls->var[out_d - 1 + jd->maxlocals][out->type];
- _SSA_CHECK_BOUNDS(a, 0, ls->max_vars);
- def_count[a]++;
- i = ssa_Rename_def(ls, n, a);
- _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
- /* Replace use of x with xi */
- #ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- printf("Ren def:BB %3i: stackslot: depth %3i old val: %3i Var,0: %3i varind: %3i\n", n, in_d, out->varnum, ls->var_to_index[a], ls->var_to_index[a]-i);
-#endif
- out->varnum = ls->var_to_index[a] - i;
- lt = &(ls->lifetime[-out->varnum-1]);
- out->varkind = TEMPVAR;
- lt->v_index = out->varnum;
- lsra_add_ss(lt, out);
- ls->lifetime[-out->varnum-1].bb_last_use = -1;
- }
- if (out_d == in_d) {
- in_d--;
- in = in->prev;
- }
- }
-
- /* change phi Functions of Successors */
- Y = graph_get_first_successor(gd, n, &iter_succ);
- for(; Y != -1; Y = graph_get_next(&iter_succ)) {
- _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
- k = graph_get_first_predecessor(gd, Y, &iter_pred);
- for (j = 0; (k != -1) && (k != n); j++, k = graph_get_next(&iter_pred));
- _SSA_ASSERT(k == n);
- /* n is jth Predecessor of Y */
- for(a = 0; a < ls->max_vars; a++)
- if (ls->phi[Y][a] != NULL) {
- /* i <- top(stack[a]) */
- _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
- i = ls->stack[a][ls->stack_top[a]-1];
- _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
- /* change jth operand from a0 to ai */
- if (ls->var_to_index[a] >= 0) {
- /* local var */
- ls->phi[Y][a][j+1] += i;
- _SSA_CHECK_BOUNDS(ls->phi[Y][a][j+1], 0,
- ls->local_0[ls->max_locals]);
- /* use by phi function has to be remembered, too */
- ssa_Rename_use(ls, n, ls->phi[Y][a][j+1]);
- } else {
- /* interface */
- ls->phi[Y][a][j+1] -= i;
-/* _SSA_CHECK_BOUNDS(ls->phi[Y][a][j+1], */
-/* ls->interface_0[-ls->max_interfaces-1], 0); */
- }
- }
- }
-
- /* Call ssa_Rename_ for all Childs of n of the Dominator Tree */
- for(i = 0; i < ls->basicblockcount; i++)
- if (dd->idom[i] == n)
- ssa_Rename_(cd, ls, gd, dd, i);
- /* pop Stack[a] for each definition of a var a in the original S */
- for(a = 0; a < ls->max_vars; a++) {
- ls->stack_top[a] -= def_count[a];
- _SSA_ASSERT(ls->stack_top[a] >= 0);
- }
-}
+ /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
+ /* an optional dst - so they to be checked first */
-void ssa_Rename(methodinfo *m, codegendata *cd, registerdata *rd, lsradata *ls,
- graphdata *gd, dominatordata *dd)
-{
- int i, p, t, type, flags;
- methoddesc *md = m->parseddesc;
+ v = UNUSED;
+ if (icmd_table[iptr->opc].dataflow == DF_INVOKE) {
+ INSTRUCTION_GET_METHODDESC(iptr,md);
+ if (md->returntype.type != TYPE_VOID)
+ v = iptr->dst.varindex;
+ }
+ else if (icmd_table[iptr->opc].dataflow == DF_BUILTIN) {
+ bte = iptr->sx.s23.s3.bte;
+ md = bte->md;
+ if (md->returntype.type != TYPE_VOID)
+ v = iptr->dst.varindex;
+ }
+ else if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE) {
+ v = iptr->dst.varindex;
+ }
- varinfo5 *locals;
+ if (v != UNUSED) {
+ j = ssa_rename_def(jd, def_count, iptr->dst.varindex);
#ifdef SSA_DEBUG_VERBOSE
- int j;
+ ssa_rename_print( iptr, "dst", iptr->dst.varindex, j);
#endif
+ iptr->dst.varindex = j;
+ }
- if (ls->max_vars == 0) {
- /* no locals or interfaces to rename */
- /* init lifetimes */
+ /* ?????????????????????????????????????????????????????????? */
+ /* Mark Def as use, too. Since param initialisation is in */
+ /* var_def and this would not remove this locals, if not used */
+ /* elsewhere */
+ /* ?????????????????????????????????????????????????????????? */
- ls->maxlifetimes = /*m*/ ls->maxlifetimes + ls->basicblockcount * m->maxstack;
- ls->lifetimecount = ls->maxlifetimes + ls->max_locals + cd->maxstack *5;
- ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
- ls->lt_used = DMNEW(int, ls->lifetimecount);
- ls->lt_int = DMNEW(int, ls->lifetimecount);
- ls->lt_int_count = 0;
- ls->lt_flt = DMNEW(int, ls->lifetimecount);
- ls->lt_flt_count = 0;
- ls->lt_mem = DMNEW(int, ls->lifetimecount);
- ls->lt_mem_count = 0;
- for (i=0; i < ls->lifetimecount; i++) ls->lifetime[i].type = -1;
- return;
}
-
- ssa_Rename_init(m, cd, ls, gd);
- /* Consider definition of Local Vars initialized with Arguments */
- /* in Block 0 */
- /* init is regarded as use too-> ssa_Rename_use ->bullshit!!*/
- for (p = 0, i= 0; p < md->paramcount; p++) {
- t = md->paramtypes[p].type;
+ /* change outstack Interface stackslots */
+ out = ls->basicblocks[n]->outvars;
+ out_d = ls->basicblocks[n]->outdepth - 1;
- /* !!!!! locals are now numbered as the parameters !!!! */
- /* !!!!! no additional increment for 2 word types !!!!! */
- /* this happens later on! here we still need the increment */
- /* index of var can be in the range from 0 up to not including */
- /* jd->maxlocals */
- _SSA_CHECK_BOUNDS(i,0,jd->maxlocals);
- _SSA_CHECK_BOUNDS(ls->var[i][t], 0, ls->local_0[ls->max_locals]);
- ssa_Rename_def(ls, 0, ls->var[i][t]);
- i++;
- if (IS_2_WORD_TYPE(t))
- i++;
- }
- ssa_Rename_(cd, ls, gd, dd, 0);
+ for (;out_d >= 0; out_d--) {
+ /* Possible Use of ls->new_varindex[jd->var[out_d]] */
+ _SSA_ASSERT(ls->new_varindex[out[out_d]] != UNUSED);
-#if 0
- /* DO _NOT_ DO THIS! Look at java.util.stringtokenizer.counttokens! */
- /* if there is no use of the defined Var itself by the phi function */
- /* for an loop path, in which this var is not used, it will not be life */
- /* in this path and overwritten! */
+ a = ls->new_varindex[out[out_d]];
+ _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
- /* Invalidate all xij from phi(xi0)=xi1,xi2,xi3,..,xin with xij == xi0 */
- /* this happens if the phi function is the first definition of x or in a */
- /* path with a backedge xi has no definition */
- /* a phi(xij) = ...,xij,... with the only use and definition of xij by */
- /* this phi function would otherwise "deadlock" the dead code elemination */
- /* invalidate means set it to ls->max_vars_with_indices */
- /* a phi function phi(xi0)=xi1,xi2,...xin wiht xij == xi0 for all j in */
- /* [1,n] can be removed */
+ /* i <- top(stack[a]) */
- for(i = 0; i < ls->max_vars; i++) {
- for(t = 0; t < ls->basicblockcount; t++) {
- if (ls->phi[t][i] != 0) {
- remove_phi = true;
- for(p = 1; p <= graph_get_num_predecessor(gd, t); p++) {
- if (ls->phi[t][i][0] == ls->phi[t][i][p])
- ls->phi[t][i][p] = ls->max_vars_with_indices;
- else
- remove_phi = false;
- }
- }
- if (remove_phi)
- ls->phi[t][i] = NULL;
- }
- }
-#endif
+ _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
+ i = ls->stack[a][ls->stack_top[a]-1];
+ _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
+
+ /* Replace use of x with xi */
- /* recreate rd->locals[][] */
- /* now only one (local_index/type) pair exists anymore */
- /* all var[t][i] with var_to_index[var[t][i]] >= 0 are locals */
- /* max local index after SSA indexing is in ls->local_0[ls->max_locals] */
-
- locals = DMNEW(varinfo5, ls->local_0[ls->max_locals]);
- for(i = 0; i < ls->local_0[ls->max_locals] ; i++)
- for(t = 0; t < 5; t++)
- locals[i][t].type = -1;
- for(t = 0; t < 5; t++) {
- for(i = 0; i < jd->maxlocals; i++) {
- p = ls->var[i][t];
- if (p != -1) {
- _SSA_ASSERT(ls->var_to_index[p] >= 0);
- /* It's a local variable */
- p = ls->var_to_index[p];
- locals[p][t].type = t;
- locals[p][t].flags = rd->locals[i][t].flags;
#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- printf("locals %3i %3i .type = %3i\n",p,t,t);
+ ssa_rename_print( NULL, "outvar", out[out_d], ls->var_0[a]+i);
#endif
- }
- }
+ out[out_d] = ls->var_0[a] + i;
+ lt = ls->lifetime + out[out_d];
+
+ lt->v_index = out[out_d];
+ lt->bb_last_use = -1;
}
-
- type = -1;
- flags = -1;
+
+ /* change use in phi Functions of Successors */
+
+ Y = graph_get_first_successor(gd, n, &iter_succ);
+ for(; Y != -1; Y = graph_get_next(&iter_succ)) {
+ _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
+ k = graph_get_first_predecessor(gd, Y, &iter_pred);
+ for (j = 0; (k != -1) && (k != n); j++)
+ k = graph_get_next(&iter_pred);
+ _SSA_ASSERT(k == n);
+
+ /* n is jth Predecessor of Y */
+
+ for(a = 0; a < ls->ssavarcount; a++)
+ if (ls->phi[Y][a] != NULL) {
+
+ /* i <- top(stack[a]) */
+
+ if (ls->stack_top[a] == 1) {
+ /* no definition till now in controll flow */
#ifdef SSA_DEBUG_VERBOSE
- p = -1;
- j = 0;
+ if (compileverbose) {
+ printf("Succ %3i Arg %3i \n", Y, j);
+ ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], UNUSED);
+ }
#endif
- for(i = 0; i < ls->local_0[ls->max_locals]; i++) {
- for(t = 0; (t < 5) && (locals[i][t].type == -1); t++);
- if (t == 5) {
- _SSA_ASSERT(type != -1);
+ ls->phi[Y][a][j+1] = UNUSED;
+ }
+ else {
+ _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
+ i = ls->stack[a][ls->stack_top[a]-1];
+ _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
+
+ /* change jth operand from a0 to ai */
+
+ i = ls->var_0[a] + i;
#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- printf("L%3i=L%3i(%3i) type %3i\n",i,p,j,type);
- j++;
- }
+ if (compileverbose) {
+ printf("Succ %3i Arg %3i \n", Y, j);
+ ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], i);
+ }
#endif
- locals[i][type].type = type;
- locals[i][type].flags = flags;
- } else {
- type = locals[i][t].type;
- flags = locals[i][t].flags;
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- j=0;
- p++;
- printf("L%3i=L%3i(%3i) type %3i\n",i,p,j,type);
- j++;
+ ls->phi[Y][a][j+1] = i;
+ _SSA_CHECK_BOUNDS(ls->phi[Y][a][j+1], 0,
+ ls->varcount_with_indices);
+
+ /* use by phi function has to be remembered, too */
+
+ ssa_rename_use_(ls, n, ls->phi[Y][a][j+1]);
+ }
+
+ /* ????????????????????????????????????????????? */
+ /* why was this only for local vars before ? */
+ /* ????????????????????????????????????????????? */
+
}
-#endif
- }
}
- rd->locals = locals;
- jd->maxlocals = ls->local_0[ls->max_locals];
+
+ /* Call ssa_rename_ for all Childs of n of the Dominator Tree */
+ for(i = 0; i < ls->basicblockcount; i++)
+ if (dd->idom[i] == n)
+ ssa_rename_(jd, gd, dd, i);
+
+ /* pop Stack[a] for each definition of a var a in the original S */
+ for(a = 0; a < ls->ssavarcount; a++) {
+ ls->stack_top[a] -= def_count[a];
+ _SSA_ASSERT(ls->stack_top[a] >= 0);
+ }
}
+
+
#ifdef SSA_DEBUG_VERBOSE
-void ssa_print_trees(methodinfo *m, codegendata *cd, lsradata *ls,
- graphdata *gd, dominatordata *dd) {
+void ssa_print_trees(jitdata *jd, graphdata *gd, dominatordata *dd) {
int i,j;
- printf("ssa_printtrees: maxlocals %3i", jd->maxlocals);
+ lsradata *ls;
+
+ ls = jd->ls;
+
+ printf("ssa_printtrees: maxlocals %3i", jd->localcount);
printf("Dominator Tree: \n");
for(i = 0; i < ls->basicblockcount; i++) {
}
printf("\n");
}
-
- if (ls->max_locals > 0) {
+#if 0
+ if (ls->ssavarcount > 0) {
printf("Use Sites\n");
- for(i = 0; i < ls->max_locals; i++) {
+ for(i = 0; i < ls->ssavarcount; i++) {
printf("use_sites[%3i]=%p:",i,(void *)ls->use_sites[i]);
for(j = 0; j < ls->basicblockcount; j++) {
if ((j % 5) == 0) printf(" ");
printf("\n");
}
}
-
+#endif
printf("var Definitions:\n");
- for(i = 0; i < ls->basicblockcount; i++) {
+ for(i = 0; i < jd->basicblockcount; i++) {
printf("var_def[%3i]=%p:",i,(void *)ls->var_def[i]);
- for(j = 0; j < ls->max_vars; j++) {
+ for(j = 0; j < ls->ssavarcount; j++) {
if ((j % 5) == 0) printf(" ");
if (bv_get_bit(ls->var_def[i], j))
printf("1");
printf("0");
}
printf(" (");
- for(j=0; j < ((((ls->max_vars * 5+7)/8) + sizeof(int) - 1)/sizeof(int));
+ for(j=0; j < ((((ls->ssavarcount * 5+7)/8) + sizeof(int) - 1)/sizeof(int));
j++)
printf("%8x",ls->var_def[i][j]);
- printf("\n");
+ printf(")\n");
}
}
void ssa_print_phi(lsradata *ls, graphdata *gd) {
int i,j,k;
- printf("phi Functions (max_vars_with_indices: %3i):\n",
- ls->max_vars_with_indices);
+ printf("phi Functions (varcount_with_indices: %3i):\n",
+ ls->varcount_with_indices);
for(i = 0; i < ls->basicblockcount; i++) {
- for(j = 0; j < ls->max_vars; j++) {
+ for(j = 0; j < ls->ssavarcount; j++) {
if (ls->phi[i][j] != NULL) {
printf("BB %3i %3i = phi(", i, ls->phi[i][j][0]);
for(k = 1; k <= graph_get_num_predecessor(gd, i); k++)
#endif
-void ssa_generate_phi_moves(lsradata *ls, graphdata *gd) {
+void ssa_generate_phi_moves(jitdata *jd, graphdata *gd) {
int a, i, j, pred;
graphiterator iter;
+ lsradata *ls;
+
+ ls = jd->ls;
/* count moves to be inserted at the end of each block in moves[] */
ls->num_phi_moves = DMNEW(int, ls->basicblockcount);
for(i = 0; i < ls->basicblockcount; i++)
ls->num_phi_moves[i] = 0;
for(i = 0; i < ls->basicblockcount; i++)
- for(a = 0; a < ls->max_vars; a++)
+ for(a = 0; a < ls->ssavarcount; a++)
if (ls->phi[i][a] != NULL) {
- pred = graph_get_first_predecessor(gd, i, &iter);
- for(; pred != -1; pred = graph_get_next(&iter)) {
- ls->num_phi_moves[pred]++;
+#if 0
+ if (ls->lifetime[ls->phi[i][a][0]].use == NULL) {
+ /* Var defined (only <- SSA Form!) in this phi function */
+ /* and not used anywhere -> delete phi function and set */
+ /* var to unused */
+
+ /* TODO: first delete use sites of arguments of phi */
+ /* function */
+ VAR(ls->lifetime[ls->phi[i][a][0]].v_index)->type = UNUSED;
+ ls->lifetime[ls->phi[i][a][0]].def = NULL;
+ ls->phi[i][a] = NULL;
+ }
+ else
+#endif
+ {
+ pred = graph_get_first_predecessor(gd, i, &iter);
+ for(; pred != -1; pred = graph_get_next(&iter)) {
+ ls->num_phi_moves[pred]++;
+ }
}
}
ls->phi_moves[i] = DMNEW( int *, ls->num_phi_moves[i]);
for(j = 0; j <ls->num_phi_moves[i]; j++)
ls->phi_moves[i][j] = DMNEW(int, 2);
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ printf("ssa_generate_phi_moves: ls_num_phi_moves[%3i] = %3i\n",
+ i, ls->num_phi_moves[i]);
+#endif
}
/* populate ls->phi_moves */
for(i = 0; i < ls->basicblockcount; i++)
ls->num_phi_moves[i] = 0;
for(i = 0; i < ls->basicblockcount; i++)
- for(a = 0; a < ls->max_vars; a++)
+ for(a = 0; a < ls->ssavarcount; a++)
if (ls->phi[i][a] != NULL) {
pred = graph_get_first_predecessor(gd, i, &iter);
for(j = 0; pred != -1; j++, pred = graph_get_next(&iter)) {
/* target is phi[i][a][0] */
/* source is phi[i][a][j+1] */
- if (ls->phi[i][a][j+1] != ls->max_vars_with_indices) {
+ if (ls->phi[i][a][j+1] != ls->varcount_with_indices) {
/* valid move */
if (ls->phi[i][a][0] != ls->phi[i][a][j+1]) {
ls->phi_moves[pred][ls->num_phi_moves[pred]][0] =
ls->phi[i][a][0];
- ls->phi_moves[pred][(ls->num_phi_moves[pred])++][1] =
+ ls->phi_moves[pred][(ls->num_phi_moves[pred])++][1]=
ls->phi[i][a][j+1];
}
}
}
}
-
-void ssa(jitdata *jd, graphdata *gd) {
- struct dominatordata *dd;
- methodinfo *m;
- codegendata *cd;
- registerdata *rd;
- lsradata *ls;
-
- m = jd->m;
- cd = jd->cd;
- rd = jd->rd;
- ls = jd->ls;
-
- dd = compute_Dominators(gd, ls->basicblockcount);
- computeDF(gd, dd, ls->basicblockcount, 0);
-
- ssa_place_phi_functions(cd, ls, gd, dd);
- ssa_Rename(m, cd, rd, ls, gd, dd);
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- printf("Phi before Cleanup\n");
- ssa_print_phi(ls, gd);
- ssa_print_lt(ls);
- }
-#endif
- scan_lifetimes(m, cd, rd, ls, gd, dd);
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- ssa_print_lt(ls);
- }
-#endif
- dead_code_elimination(m, rd, ls, gd);
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- printf("Phi after dead code elemination\n");
- ssa_print_phi(ls, gd);
- ssa_print_lt(ls);
- }
-#endif
- copy_propagation(m, rd, ls, gd);
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- printf("Phi after copy propagation\n");
- ssa_print_phi(ls, gd);
- ssa_print_lt(ls);
- }
-#endif
-
- ssa_generate_phi_moves(ls, gd);
- transform_BB(jd, gd);
-
-
-#ifdef SSA_DEBUG_CHECK
- {
- int i, j, pred, in_d, out_d;
- graphiterator iter_pred;
- stackptr in, out;
- bool phi_define;
-
- for(i = 0; i < ls->basicblockcount; i++) {
- if (ls->basicblocks[i]->indepth != 0) {
- pred = graph_get_first_predecessor(gd, i, &iter_pred);
- for (; (pred != -1); pred = graph_get_next(&iter_pred)) {
- in_d = ls->basicblocks[i]->indepth;
- in = ls->basicblocks[i]->instack;
- for (;in_d > 0; in_d--, in = in->prev) {
- phi_define = false;
- for (j = 0; (!phi_define) && (j < ls->max_vars); j++) {
- if (ls->phi[i][j] != NULL)
- if (ls->phi[i][j][0] == in->varnum)
- phi_define = true;
- }
- if (!phi_define) {
- /* in not defined in phi function -> check with outstack(s) */
- /* of predecessor(s) */
- out_d = ls->basicblocks[pred]->outdepth;
- out = ls->basicblocks[pred]->outstack;
- _SSA_ASSERT(out_d >= in_d);
- for(; out_d > in_d; out_d--, out = out->prev);
- if ((in->varnum != out->varnum) ||
- (in->varkind != out->varkind)) {
- printf("Method: %s %s\n", m->class->name->text, m->name->text);
- printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
- if (compileverbose)
- printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
-/* else */
-/* _SSA_ASSERT(0); */
- }
- }
- }
- }
- }
- }
- }
-
-#endif
-
-
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- ssa_print_trees(m,cd,ls, gd, dd);
-#endif
-}
-
/****************************************************************************
-Optimization
+Optimizations
****************************************************************************/
/****************************************************************************
Dead Code Elimination
****************************************************************************/
-void dead_code_elimination(methodinfo *m,registerdata *rd, lsradata *ls, graphdata *gd) {
+void dead_code_elimination(jitdata *jd, graphdata *gd) {
int a, i, source;
worklist *W;
instruction *iptr;
- stackptr src;
struct lifetime *lt, *s_lt;
bool remove_statement;
struct site *use;
+ lsradata *ls;
+#ifdef SSA_DEBUG_VERBOSE
+ methodinfo *m;
+
+ m = jd->m;
+#endif
+ ls = jd->ls;
+
W = wl_new(ls->lifetimecount);
if (ls->lifetimecount > 0) {
/* put all lifetimes on Worklist */
for (i = 1;i <= graph_get_num_predecessor(gd, lt->def->b_index);
i++)
{
- source = ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
- if ((source != ls->max_vars_with_indices) &&
+ source =
+ ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
+ if ((source != ls->varcount_with_indices) &&
(source != lt->v_index)) {
+
/* phi Argument was not already removed (already in
because of selfdefinition) */
- if (source >= 0) {
- /* Local Var */
- s_lt = &(ls->lifetime[ls->maxlifetimes + source]);
- } else {
- /* Interface Stackslot */
- s_lt = &(ls->lifetime[-source-1]);
- }
+
+ s_lt = &(ls->lifetime[source]);
+
/* remove it */
- remove_use_site(s_lt,lt->def->b_index, lt->def->iindex);
+
+ lt_remove_use_site(s_lt,lt->def->b_index,
+ lt->def->iindex);
+
/* put it on the Worklist */
- if (source >= 0) {
- /* Local Var */
- wl_add(W, ls->maxlifetimes + source);
- } else {
- /* Interface Stackslot */
- wl_add(W, -source - 1);
- }
+
+ wl_add(W, source);
}
}
/* now delete phi function itself */
/* "normal" Use by ICMD */
remove_statement = false;
if (lt->def->b_index != 0) {
+
/* do not look at artificial block 0 (parameter init) */
+
iptr = ls->basicblocks[lt->def->b_index]->iinstr +
lt->def->iindex;
if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI)
remove_statement = false;
+
/* if ICMD could throw an exception do not remove it! */
- else {
- /* get src stack */
- if (lt->def->iindex == 0)
- src = ls->basicblocks[lt->def->b_index]->instack;
- else
- src = (iptr-1)->dst;
-
- remove_statement = true;
- /* Statement has side effects? (== ICMD_INVOKE*) */
- switch (iptr->opc) {
- case ICMD_INVOKEVIRTUAL:
- case ICMD_INVOKESPECIAL:
- case ICMD_INVOKESTATIC:
- case ICMD_INVOKEINTERFACE:
- case ICMD_BUILTIN:
- /* check if really a side effect is possible */
- case ICMD_MULTIANEWARRAY: /* here, too */
- /* side effects by Statement possible ->
- do not remove it */
- remove_statement = false;
- break;
- /* delete use of vars by these statments: */
-
- /* use of iptr->op1 */
- case ICMD_IINC:
- case ICMD_ILOAD:
- case ICMD_LLOAD:
- case ICMD_FLOAD:
- case ICMD_DLOAD:
- case ICMD_ALOAD:
- s_lt = &(ls->lifetime[ls->maxlifetimes + iptr->op1]);
- remove_use_site(s_lt,lt->def->b_index, lt->def->iindex);
- /* put it on the Worklist */
- wl_add(W, ls->maxlifetimes + iptr->op1);
- break;
+ else {
- /* remove src->prev and src */
- case ICMD_IALOAD:
- case ICMD_LALOAD:
- case ICMD_FALOAD:
- case ICMD_DALOAD:
- case ICMD_AALOAD:
-
- case ICMD_BALOAD:
- case ICMD_CALOAD:
- case ICMD_SALOAD:
-
- case ICMD_LADD:
- case ICMD_LSUB:
- case ICMD_LMUL:
-
- case ICMD_LOR:
- case ICMD_LAND:
- case ICMD_LXOR:
-
- case ICMD_LSHL:
- case ICMD_LSHR:
- case ICMD_LUSHR:
-
- case ICMD_IADD:
- case ICMD_IMUL:
-
- case ICMD_ISHL:
- case ICMD_ISHR:
- case ICMD_IUSHR:
- case ICMD_IAND:
- case ICMD_IOR:
- case ICMD_IXOR:
-
-
- case ICMD_FADD:
- case ICMD_FSUB:
- case ICMD_FMUL:
-
- case ICMD_DADD:
- case ICMD_DSUB:
- case ICMD_DMUL:
- case ICMD_DDIV:
- case ICMD_DREM:
- case ICMD_ISUB:
- case ICMD_LDIV:
- case ICMD_LREM:
-
- case ICMD_IDIV:
- case ICMD_IREM:
-
- case ICMD_FDIV:
- case ICMD_FREM:
-
- case ICMD_LCMP:
- case ICMD_FCMPL:
- case ICMD_FCMPG:
- case ICMD_DCMPL:
- case ICMD_DCMPG:
- /* Remove src->prev and then "fall through" for removal
- of src */
- s_lt = &(ls->lifetime[-src->prev->varnum-1]);
- remove_use_site(s_lt,lt->def->b_index, lt->def->iindex);
- /* put it on the Worklist */
- wl_add(W, -src->prev->varnum - 1);
- /* remove src */
- case ICMD_ISTORE:
- case ICMD_LSTORE:
- case ICMD_FSTORE:
- case ICMD_DSTORE:
- case ICMD_ASTORE:
- case ICMD_LADDCONST:
- case ICMD_LSUBCONST:
- case ICMD_LMULCONST:
- case ICMD_LMULPOW2:
- case ICMD_LDIVPOW2:
- case ICMD_LREMPOW2:
- case ICMD_LANDCONST:
- case ICMD_LORCONST:
- case ICMD_LXORCONST:
- case ICMD_LSHLCONST:
- case ICMD_LSHRCONST:
- case ICMD_LUSHRCONST:
-
- case ICMD_IADDCONST:
- case ICMD_ISUBCONST:
- case ICMD_IMULCONST:
- case ICMD_IMULPOW2:
- case ICMD_IDIVPOW2:
- case ICMD_IREMPOW2:
- case ICMD_IANDCONST:
- case ICMD_IORCONST:
- case ICMD_IXORCONST:
- case ICMD_ISHLCONST:
- case ICMD_ISHRCONST:
- case ICMD_IUSHRCONST:
-
- /* case ICMD_IFEQ_ICONST: */
- /* case ICMD_IFNE_ICONST: */
- /* case ICMD_IFLT_ICONST: */
- /* case ICMD_IFGE_ICONST: */
- /* case ICMD_IFGT_ICONST: */
- /* case ICMD_IFLE_ICONST: */
-
- case ICMD_INEG:
- case ICMD_INT2BYTE:
- case ICMD_INT2CHAR:
- case ICMD_INT2SHORT:
- case ICMD_LNEG:
- case ICMD_FNEG:
- case ICMD_DNEG:
-
- case ICMD_I2L:
- case ICMD_I2F:
- case ICMD_I2D:
- case ICMD_L2I:
- case ICMD_L2F:
- case ICMD_L2D:
- case ICMD_F2I:
- case ICMD_F2L:
- case ICMD_F2D:
- case ICMD_D2I:
- case ICMD_D2L:
- case ICMD_D2F:
- case ICMD_CHECKCAST:
- case ICMD_ARRAYLENGTH:
- case ICMD_INSTANCEOF:
-
- case ICMD_NEWARRAY:
- case ICMD_ANEWARRAY:
-
- case ICMD_GETFIELD:
- /* Remove src->prev and then "fall through" for removal
- of src */
- s_lt = &(ls->lifetime[-src->varnum-1]);
- remove_use_site(s_lt,lt->def->b_index, lt->def->iindex);
- /* put it on the Worklist */
- wl_add(W, -src->varnum - 1);
- break;
- /* ignore these for now */
- case ICMD_DUP:
- case ICMD_DUP2:
- case ICMD_DUP_X1:
- case ICMD_DUP_X2:
- case ICMD_DUP2_X1:
- case ICMD_DUP2_X2:
- case ICMD_SWAP:
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- printf("INFO2: ICMD_DUPX to be removed\n");
-#endif
- /* DUPX has sideefects - cannot be removed, only because
- one of the output vars is unused
- TODO: extend the dead code elimination, so that all
- output ss are checked*/
- remove_statement = false;
- break;
- } /* switch (iptr->opc) */
+ /* ICMD_INVOKE*, ICMD_BUILTIN and ICMD_MULTIANEWARRAY */
+ /* have possible sideeffects -> do not remove them */
+
+/* remove_statement = !(ICMD_HAS_SPECIAL(iptr->opc)); */
+
+ remove_statement = !(
+ (icmd_table[iptr->opc].dataflow == DF_INVOKE) ||
+ (icmd_table[iptr->opc].dataflow == DF_BUILTIN) ||
+ (icmd_table[iptr->opc].dataflow == DF_N_TO_1));
+
+ if (remove_statement) {
+ switch (icmd_table[iptr->opc].dataflow) {
+ case DF_3_TO_0:
+ case DF_3_TO_1: /* icmd has s1, s2 and s3 */
+ a = iptr->sx.s23.s3.varindex;
+ s_lt = ls->lifetime + a;
+ lt_remove_use_site(s_lt, lt->def->b_index,
+ lt->def->iindex);
+ wl_add(W, a);
+
+ /* now "fall through" for handling of s2 and s1 */
+
+ case DF_2_TO_0:
+ case DF_2_TO_1: /* icmd has s1 and s2 */
+ a = iptr->sx.s23.s2.varindex;
+ s_lt = ls->lifetime + a;
+ lt_remove_use_site(s_lt, lt->def->b_index,
+ lt->def->iindex);
+ wl_add(W, a);
+
+ /* now "fall through" for handling of s1 */
+
+ case DF_1_TO_0:
+ case DF_1_TO_1:
+ case DF_MOVE:
+ case DF_COPY:
+ a = iptr->s1.varindex;
+ s_lt = ls->lifetime + a;
+ lt_remove_use_site(s_lt, lt->def->b_index,
+ lt->def->iindex);
+ wl_add(W, a);
+ }
+ }
}
+
if (remove_statement) {
+
/* remove statement */
+
#ifdef SSA_DEBUG_VERBOSE
if (compileverbose)
printf("INFO: %s %s:at BB %3i II %3i NOP-<%s\n",
}
} /* (lt->def->b_index != 0) */
} /* if (lt->def->iindex < 0 ) else */
+
/* remove definition of a */
- if (lt->v_index >= 0) {
- /* local var */
- rd->locals[lt->v_index][lt->type].type = -1;
- }
+
+ VAR(lt->v_index)->type = -1;
lt->type = -1;
lt->def = NULL;
} /* if (lt->use == NULL) */
-
} /* while(!wl_is_empty(W)) */
} /* dead_code_elimination */
-
-
-#if 0
-void dead_code_elimination(registerdata *rd, lsradata *ls, graphdata *gd) {
- int A,a,i,n,t;
- bool is_empty;
-
- int *W_stack;
- int W_top;
-
- W_top = 0;
- if (ls->max_locals > 0) {
- W_stack = DMNEW(int, ls->max_vars);
- /* put unused local vars on Worklist */
- for(a = 0; a < ls->local_0[ls->max_locals]; a++) {
- if (bv_is_empty(ls->use_sites[a], ls->basicblockcount)) {
- /* a is not used */
- W_stack[W_top++] = a;
- }
- }
- }
- /* Remove unused local vars */
- while(W_top > 0) {
- /* take a var out of Worklist */
- a = W_stack[--W_top];
-
- if (bv_is_empty(ls->use_sites[a], ls->basicblockcount)) {
- for(t = 0; t < 5; t++)
- rd->locals[a][t].type = -1;
- }
- /* Change and if necessary delete phi functions */
- for(n = 0; n < ls->basicblockcount; n++) {
- for(A = 0; A < ls->max_vars; A++) {
- if (ls->var_to_index[A] >= 0) {
- if (ls->phi[n][A] != NULL) {
- is_empty = true;
- /* look through the arguments of the phi function */
- for(i = 1; i < (graph_get_num_predecessor(gd, n)+1); i++) {
- /* check if entry was not already removed */
- if (ls->phi[n][A][i] != -1) {
- if (bv_is_empty(ls->use_sites[ls->phi[n][A][i]],
- ls->basicblockcount))
- {
- ls->num_var_use[n][ls->phi[n][A][i]]--;
- if (ls->num_var_use[n][ls->phi[n][A][i]] ==
- 0) {
- /* this was the only use in this Basic Block */
- bv_reset_bit(
- ls->use_sites[ls->phi[n][A][i]],n);
- if (bv_is_empty(
- ls->use_sites[ls->phi[n][A][i]],
- ls->basicblockcount))
- {
- /* this was the only use in the whole Method */
- /* -> put this local var on the Worklist */
- W_stack[W_top++] =
- ls->phi[n][A][i];
- }
- }
- ls->phi[n][A][i] = -1;
- } else
- is_empty = false;
- }
- }
- /* look at the target of the phi function */
- /* Remove it,if target is not used or all arguments where */
- /* removed */
- if (bv_is_empty(ls->use_sites[ls->phi[n][A][0]],
- ls->basicblockcount) || is_empty) {
- /* phi function can be removed */
- ls->phi[n][A] = NULL;
- }
- } /* if (ls->phi[n][A] != NULL) */
- } /* if (ls->var_to_index[A] >= 0 */
- } /* for(li = 0; li < ls->max_locals; li++) */
- } /* for(n = 0; n < ls->basicblockcount; n++) */
- } /* while(W_top>0) */
- /* Remove unused Local Vars from rd->local */
- if (ls->max_locals > 0)
- for(a = 0; a < ls->local_0[ls->max_locals]; a++) {
- if (bv_is_empty(ls->use_sites[a], ls->basicblockcount)) {
- /* a is not used */
- for(t = 0; t < 5; t++)
- rd->locals[a][t].type = -1;
- }
- }
-}
-#endif
/****************************************************************************
Simple Constant Propagation
****************************************************************************/
void simple_constant_propagation() {
}
+
/****************************************************************************
Optimization
*******************************************************************************/
-void copy_propagation(methodinfo *m,registerdata *rd, lsradata *ls,
- graphdata *gd) {
+void copy_propagation(jitdata *jd, graphdata *gd) {
int a, i, source;
int only_source;
instruction *iptr;
struct lifetime *lt, *s_lt;
- struct stackslot *ss;
- stackptr in;
+ s4 *in;
+
+ lsradata *ls;
+
+ ls = jd->ls;
W = wl_new(ls->lifetimecount);
if (ls->lifetimecount > 0) {
/* take a var out of Worklist */
a = wl_get(W);
- lt = &(ls->lifetime[a]);
+ lt = ls->lifetime + a;
if (lt->type == -1)
continue;
_SSA_ASSERT(lt->def != NULL);
_SSA_ASSERT(lt->use != NULL);
if (lt->def->iindex < 0 ) {
+
/* phi function */
/* look, if phi function degenerated to a x = phi(y) */
/* and if so, substitute y for every use of x */
_SSA_ASSERT(ls->phi[lt->def->b_index][-lt->def->iindex-1] != NULL);
- only_source = ls->max_vars_with_indices;
+ only_source = ls->varcount_with_indices;
for (i = 1; i <= graph_get_num_predecessor(gd, lt->def->b_index);
i++) {
source = ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
- if (source != ls->max_vars_with_indices) {
- if (only_source == ls->max_vars_with_indices) {
+ if (source != ls->varcount_with_indices) {
+ if (only_source == ls->varcount_with_indices) {
/* first valid source argument of phi function */
only_source = source;
} else {
/* second valid source argument of phi function */
/* exit for loop */
- only_source = ls->max_vars_with_indices;
+ only_source = ls->varcount_with_indices;
break;
}
}
}
- if (only_source != ls->max_vars_with_indices) {
+ if (only_source != ls->varcount_with_indices) {
+
/* replace all use sites of lt with the var_index only_source */
- replace_use_sites( ls, gd, lt, only_source, W);
+
+ ssa_replace_use_sites( jd, gd, lt, only_source, W);
/* delete def of lt and replace uses of lt with "only_source" */
+
ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL;
- if (only_source >= 0) {
- /* Local Var */
- s_lt = &(ls->lifetime[ls->maxlifetimes + only_source]);
- rd->locals[lt->v_index][lt->type].type = -1;
- } else {
- /* Interface Stackslot */
- s_lt = &(ls->lifetime[-only_source-1]);
- }
- remove_use_site(s_lt, lt->def->b_index, lt->def->iindex);
+ s_lt = ls->lifetime + only_source;
+
+ VAR(lt->v_index)->type = -1;
+ lt_remove_use_site(s_lt, lt->def->b_index, lt->def->iindex);
lt->def = NULL;
/* move use sites from lt to s_lt */
- move_use_sites(lt, s_lt);
- move_stackslots(lt, s_lt);
+ lt_move_use_sites(lt, s_lt);
lt->type = -1;
- } /* if (only_source != ls->max_vars_with_indices) */
+ } /* if (only_source != ls->varcount_with_indices) */
} else { /* if (lt->def->iindex < 0 )*/
/* def in "normal" ICMD */
+#if 0
iptr = ls->basicblocks[lt->def->b_index]->iinstr +
lt->def->iindex;
- if (lt->v_index >= 0) {
+
+ if ( localvar ) {
if (lt->def->b_index == 0)
continue;
+
switch(iptr->opc) {
case ICMD_ISTORE:
case ICMD_LSTORE:
case ICMD_FSTORE:
case ICMD_DSTORE:
- case ICMD_ASTORE:
+ case ICMD_ASTORE:
if (lt->def->iindex == 0) {
/* first instruction in bb -> instack==bb->instack */
in = ls->basicblocks[lt->def->b_index]->instack;
printf("copy propagation xstore: BB %3i I %3i: %3i -> %3i\n", lt->def->b_index, lt->def->iindex, iptr->op1, in->varnum);
#endif
s_lt = &(ls->lifetime[-in->varnum-1]);
-
+
for (ss = s_lt->local_ss; ss != NULL; ss = ss->next) {
ss->s->varkind = LOCALVAR;
ss->s->varnum = iptr->op1;
}
-
+
/* replace all use sites of s_lt with the var_index */
/* iptr->op1 */
- replace_use_sites(ls, gd, s_lt, iptr->op1, W);
+ ssa_replace_use_sites(jd, gd, s_lt, iptr->op1, W);
/* s_lt->def is the new def site of lt */
/* the old ->def site will get a use site of def */
/* replace all use sites of lt with the var_index iptr->op1*/
- replace_use_sites( ls, gd, lt, iptr->op1, W);
+ ssa_replace_use_sites(jd, gd, lt, iptr->op1, W);
lt->def = NULL;
if (lt->local_ss->s->varnum != iptr->op1)
printf("copy propagation: ILOAD -> LOCALVAR ss BB %i II %i\n",
lt->def->b_index, lt->def->iindex);
-
+
break;
}
- }
- }
- }
+ } /* localvar or interface stackslot */
+#endif
+ } /* i(lt->def->iindex < 0 ) */
+
+ } /* while(!wl_is_empty(W)) */
}
-void replace_use_sites( lsradata *ls, graphdata *gd, struct lifetime *lt,
- int new_v_index, worklist *W) {
+void ssa_replace_use_sites(jitdata *jd, graphdata *gd, struct lifetime *lt,
+ int new_v_index, worklist *W) {
struct site *s;
int i, source;
instruction *iptr;
- struct stackslot *ss;
+ s4 *argp;
+
+ methoddesc *md;
+ builtintable_entry *bte;
+ lsradata *ls;
+
+ ls = jd->ls;
+ md = jd->m->parseddesc;
+
for(s = lt->use; s != NULL; s = s->next) {
if (s->iindex < 0) {
+
/* Use in phi function */
- for (i = 1;i <= graph_get_num_predecessor(gd,s->b_index);
- i++) {
+
+ for (i = 1;i <= graph_get_num_predecessor(gd, s->b_index); i++) {
source = ls->phi[s->b_index][-s->iindex-1][i];
if (source == lt->v_index) {
#ifdef SSA_DEBUG_VERBOSE
if (W != NULL) {
- if (compileverbose)
- printf("copy propagation phi: BB %3i I %3i: %3i -> \
+ if (compileverbose)
+ printf("copy propagation phi: BB %3i I %3i: %3i -> \
%3i\n", s->b_index, s->iindex,
- new_v_index, source);
+ new_v_index, source);
}
#endif
ls->phi[s->b_index][-s->iindex-1][i]
}
}
if (W != NULL) {
+
/* Add var, which is defined by this phi function to */
/* the worklist */
+
source = ls->phi[s->b_index][-s->iindex-1][0];
- if (source >= 0) {
- /* Local Var */
- wl_add(W, ls->maxlifetimes + source);
- } else {
- /* Interface Stackslot */
- wl_add(W, -source - 1);
- }
+ wl_add(W, source);
}
- } else {
- /* use in ICMD */
+ }
+ else { /* use in ICMD */
iptr = ls->basicblocks[s->b_index]->iinstr +
s->iindex;
- if (lt->v_index >= 0) {
- /* Local Var use */
- switch(iptr->opc) {
- case ICMD_ILOAD:
- case ICMD_LLOAD:
- case ICMD_FLOAD:
- case ICMD_DLOAD:
- case ICMD_ALOAD:
- case ICMD_ISTORE:
- case ICMD_LSTORE:
- case ICMD_FSTORE:
- case ICMD_DSTORE:
- case ICMD_ASTORE:
- case ICMD_IINC: /* iptr->op1 == USE */
- /* TODO: check if for XSTORE not src->varnum has */
- /* to be changed instead of iptr->op1 */
- _SSA_ASSERT(iptr->op1 == lt->v_index);
+
+ /* check for use (s1, s2, s3 or special (argp) ) */
+
+ i = UNUSED;
+ switch (icmd_table[iptr->opc].dataflow) {
+ case DF_3_TO_0:
+ case DF_3_TO_1: /* icmd has s1, s2 and s3 */
+ if (iptr->sx.s23.s3.varindex == lt->v_index) {
#ifdef SSA_DEBUG_VERBOSE
if (W != NULL) {
- if (compileverbose)
- printf("copy propagation loc: BB %3i I %3i: %3i -> \
+ if (compileverbose)
+ printf("copy propagation loc: BB %3i I %3i: %3i -> \
%3i\n", s->b_index, s->iindex,
- new_v_index, iptr->op1);
+ new_v_index, iptr->sx.s23.s3.varindex);
}
#endif
- iptr->op1 = new_v_index;
- break;
- default:
- exit(1);
+ iptr->sx.s23.s3.varindex = new_v_index;
}
- } else {
- /* Interface Stackslot Use */
+
+ /* now "fall through" for handling of s2 and s1 */
+
+ case DF_2_TO_0:
+ case DF_2_TO_1: /* icmd has s1 and s2 */
+ if (iptr->sx.s23.s2.varindex == lt->v_index) {
+#ifdef SSA_DEBUG_VERBOSE
+ if (W != NULL) {
+ if (compileverbose)
+ printf("copy propagation loc: BB %3i I %3i: %3i -> \
+ %3i\n", s->b_index, s->iindex,
+ new_v_index, iptr->sx.s23.s2.varindex);
+ }
+#endif
+ iptr->sx.s23.s2.varindex = new_v_index;
+ }
+
+ /* now "fall through" for handling of s1 */
+
+ case DF_1_TO_0:
+ case DF_1_TO_1:
+ case DF_MOVE:
+ case DF_COPY:
+ if (iptr->s1.varindex == lt->v_index) {
#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- printf("copy propagation int: BB %3i I %3i: %3i -> \
- %3i\n", s->b_index, s->iindex, new_v_index,
- lt->local_ss->s->varnum);
+ if (W != NULL) {
+ if (compileverbose)
+ printf("copy propagation loc: BB %3i I %3i: %3i -> \
+ %3i\n", s->b_index, s->iindex,
+ new_v_index, iptr->s1.varindex);
+ }
#endif
- for (ss = lt->local_ss; ss != NULL; ss = ss->next) {
- ss->s->varkind = LOCALVAR;
- ss->s->varnum = new_v_index;
+ iptr->s1.varindex = new_v_index;
}
+ break;
+
+ /* TODO: */
+ /* ? really look at md->paramcount or iptr->s1.argcount */
+ /* has to be taken, so that pass-through stackslots get */
+ /* renamed, too? */
+
+ case DF_INVOKE:
+ INSTRUCTION_GET_METHODDESC(iptr,md);
+ i = md->paramcount;
+ break;
+ case DF_BUILTIN:
+ bte = iptr->sx.s23.s3.bte;
+ md = bte->md;
+ i = md->paramcount;
+ break;
+ case DF_N_TO_1:
+ i = iptr->s1.argcount;
+ break;
+ }
+ if (i != UNUSED) {
+ argp = iptr->sx.s23.s2.args;
+ while (--i >= 0) {
+ if (*argp == lt->v_index) {
+#ifdef SSA_DEBUG_VERBOSE
+ if (W != NULL) {
+ if (compileverbose)
+ printf(
+ "copy propagation loc: BB %3i I %3i: %3i -> %3i\n"
+ , s->b_index, s->iindex, new_v_index, *argp);
+ }
+#endif
+ *argp = new_v_index;
- }
- }
+ }
+ argp++;
+ }
+ }
+
+ } /* if (s->iindex < 0) */
} /* for(s = lt->use; s != NULL; s = s->next) */
}
printf("SSA LT Def/Use\n");
for(i = 0; i < ls->lifetimecount; i++) {
- lt = &(ls->lifetime[i]);
- if (lt->type != -1) {
+ lt = ls->lifetime + i;
+ if (lt->type != UNUSED) {
printf("VI %3i Type %3i Def: ",lt->v_index, lt->type);
if (lt->def != NULL)
printf("%3i,%3i Use: ",lt->def->b_index, lt->def->iindex);
}
}
}
+
+void ssa_show_variable(jitdata *jd, int index, varinfo *v, int stage)
+{
+ char type;
+ char kind;
+
+ switch (v->type) {
+ case TYPE_INT: type = 'i'; break;
+ case TYPE_LNG: type = 'l'; break;
+ case TYPE_FLT: type = 'f'; break;
+ case TYPE_DBL: type = 'd'; break;
+ case TYPE_ADR: type = 'a'; break;
+ case TYPE_RET: type = 'r'; break;
+ default: type = '?';
+ }
+
+ if (index < jd->localcount) {
+ kind = 'L';
+ if (v->flags & (PREALLOC | INOUT))
+ printf("<INVALID FLAGS!>");
+ }
+ else {
+ if (v->flags & PREALLOC) {
+ kind = 'A';
+ if (v->flags & INOUT)
+ printf("<INVALID FLAGS!>");
+ }
+ else if (v->flags & INOUT)
+ kind = 'I';
+ else
+ kind = 'T';
+ }
+
+ printf("%c%c%3d", kind, type, index);
+
+ if (v->flags & SAVEDVAR)
+ putchar('!');
+
+ putchar(' ');
+ fflush(stdout);
+}
#endif
+
/****************************************************************************
Optimization
****************************************************************************/
# define _SSA_ASSERT(a)
#endif
-/* #define JOIN_PHI_LT */ /* build intereference graph for lt used in phi */
- /* funcs and try to merge them */
-
/* function prototypes */
void ssa_init(jitdata *);
-void ssa_set_local_def(lsradata *, int , int , int);
-void ssa_set_use(lsradata *, int , int , int );
-void ssa_set_interface(codegendata *, lsradata *, basicblock *);
void ssa(jitdata *, graphdata *);
#endif /* _SSA_H */
* Local variables:
* mode: c
* indent-tabs-mode: t
- * c-basic-offset: 4
- * tab-width: 4
+ * c-basic-offset): 4
+ * tab-width): 4
* End:
+ * vim:noexpandtab:sw=4:ts=4:
*/
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.
- $Id: stack.c 7766 2007-04-19 13:24:48Z michi $
+ $Id: stack.c 7908 2007-05-15 09:55:17Z christian $
*/
#include "vm/jit/jit.h"
#include "vm/jit/stack.h"
+#if 0
#if defined(ENABLE_SSA)
# include "vm/jit/optimizing/lsra.h"
# include "vm/jit/optimizing/ssa.h"
#elif defined(ENABLE_LSRA)
# include "vm/jit/allocator/lsra.h"
#endif
+#endif
#include "vmcore/options.h"
#include "vm/resolve.h"
methodinfo *m; /* method being analyzed */
registerdata *rd;
stackdata_t sd;
-#if defined(ENABLE_SSA)
- lsradata *ls;
-#endif
int stackdepth;
stackptr curstack; /* current stack top */
stackptr copy;
m = jd->m;
rd = jd->rd;
-#if defined(ENABLE_SSA)
- ls = jd->ls;
-#endif
/* initialize the stackdata_t struct */
sd.exstack.varnum = sd.localcount;
sd.var[sd.exstack.varnum].type = TYPE_ADR;
-#if defined(ENABLE_LSRA)
- m->maxlifetimes = 0;
-#endif
-
#if defined(ENABLE_STATISTICS)
iteration_count = 0;
#endif
return false;
}
#endif
-
-#if defined(ENABLE_SSA)
- if (ls != NULL) {
- GET_NEW_VAR(sd, new_index, type);
- DST(type, new_index);
- stackdepth++;
- }
- else
-
-#else
LOAD(type, varindex);
-#endif
break;
/* pop 2 push 1 */
case ICMD_IINC:
STATISTICS_STACKDEPTH_DISTRIBUTION(count_store_depth);
-#if defined(ENABLE_SSA)
- if (ls != NULL) {
- iptr->s1.varindex =
- jd->local_map[iptr->s1.varindex * 5 +TYPE_INT];
- }
- else {
-#endif
last_store_boundary[iptr->s1.varindex] = sd.new;
iptr->s1.varindex =
i--;
copy = copy->prev;
}
-#if defined(ENABLE_SSA)
- }
-#endif
iptr->dst.varindex = iptr->s1.varindex;
break;
}
#endif
-#if defined(ENABLE_SSA)
- if (ls != NULL) {
-#endif
/* check for conflicts as described in Figure 5.2 */
copy = curstack->prev;
/* remember the stack boundary at this store */
store_tail:
last_store_boundary[javaindex] = sd.new;
-#if defined(ENABLE_SSA)
- } /* if (ls != NULL) */
-#endif
if (opcode == ICMD_ASTORE && curstack->type == TYPE_RET)
STORE(TYPE_RET, varindex);
projects / cacao.git / commitdiff