#include "vm/jit/replace.h"
#include "vm/jit/stacktrace.h"
-#if defined(ENABLE_LSRA)
+#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
if (compileverbose)
printf("...returning - phi lifetimes where joined\n");
#endif
- return;
+ continue;
}
if (s->type == -1) {
if (compileverbose)
printf("...returning - phi lifetimes where joined\n");
#endif
- return;
+ continue;
}
tmp_i.opc = 0;
/* allocate registers */
if ((opt_lsra) && (jd->exceptiontablelength == 0)) {
jd->ls = DNEW(lsradata);
+ ssa(jd);
lsra(jd);
STATISTICS(count_methods_allocated_by_lsra++);
lsra.h \
ssa.c \
ssa.h \
+ ssa_phi.c \
+ ssa_phi.h \
+ ssa_rename.c \
+ ssa_rename.h \
graph.c \
graph.h \
dominators.c \
Authors: Christian Ullrich
+ $Id: graph.c$
*/
int graph_get_first_(graph_element *ge, graphiterator *i);
void transform_CFG(jitdata *, graphdata *);
+void graph_phi_moves(jitdata *jd, basicblock *bptr, basicblock *dst_goto);
+
#ifdef GRAPH_DEBUG_VERBOSE
void graph_print(lsradata *ls, graphdata *gd);
#endif
/*********************************************************************+
After the "original" CFG has been created, it has to be adopted for
-SSA. (inluding insertion of new Basic Blocks)
+SSA. (inluding insertion of new Basic Blocks - edge splitting)
-TODO: Do not insert blocks right now - just adopt the call graph!
- After the phi moves are determined create only the needed Blocks
**********************************************************************/
void transform_CFG(jitdata *jd, graphdata *gd) {
int i, j, k, n, num_new_blocks;
/* copy Basic Block References to ls->basicblocks */
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;
-/* } */
+ _GRAPH_ASSERT(bptr->nr < jd->basicblockcount);
+ ls->basicblocks[bptr->nr + 1] = bptr;
+ bptr->nr = bptr->nr+1;
}
/* Create new Basic Blocks:
- 0, [jd->new_basicblockcount..ls->basicblockcount[ */
+ 0, [jd->basicblockcount..ls->basicblockcount[ */
/* num_new_blocks have to be inserted*/
tmp = DMNEW( basicblock, num_new_blocks);
ls->basicblocks[0]->next = ls->basicblocks[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);
/* 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 < jd->basicblockcount + 1; i++) {
var_def[i] = ls->var_def[i];
}
/* Now Split the edges */
+
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 */
/* splite the edge from BB i to j with the new BB */
/* num_new_blocks ( i->j --> i->nnb->j)*/
/* iter_succ shows the edge from i to j */
+
graph_split_edge(gd, i, &iter, num_new_blocks);
ls->basicblocks[num_new_blocks]->indepth =
_GRAPH_ASSERT(ls->basicblocks[num_new_blocks]->outdepth ==
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(jd, ls->basicblocks[num_new_blocks]);
- ls->basicblocks[num_new_blocks]->nr++;
-#endif
num_new_blocks++;
}
}
ls->basicblocks[pred]->next;
ls->basicblocks[pred]->next =
ls->basicblocks[n];
+#if 1
/* generate no instructions */
ls->basicblocks[n]->icount = 1;
ls->basicblocks[n]->iinstr = NEW(instruction);
ls->basicblocks[n]->iinstr[0].opc = ICMD_NOP;
+#else
+ graph_phi_moves(jd, ls->basicblocks[n], NULL);
+#endif
} else {
/* Block n is in the Branch path */
/* link Block at the end */
/* change the Branch Target to BB i */
-
-
switch(iptr->opc) {
case ICMD_LOOKUPSWITCH:
{
/* not handled by now -> fallback to regalloc */
exit(1);
}
-
+#if 1
/* Generate the ICMD_GOTO */
ls->basicblocks[n]->icount = 1;
ls->basicblocks[n]->iinstr =
ICMD_GOTO;
ls->basicblocks[n]->iinstr->dst.block =
ls->basicblocks[succ];
+#else
+ graph_phi_moves(jd, ls->basicblocks[n], ls->basicblocks[succ]);
+#endif
}
}
}
}
+/* graph_phi_moves *************************************************************
+
+generate the instruction array for Basicblock n (== ls->basicblocks[n])
+
+IN:
+basicblock *bptr Basicblock to change with ->iinstr == NULL
+basicblock *dst_goto Destination Block for ICMD_GOTO at end of Block, or
+ NULL for no ICMD_GOTO
+
+OUT:
+bptr->iinstr points to a newly allocated instruction array containing
+ the phi moves, the optional ICMD_GOTO at the end.
+bptr->icount Count of instructions in bptr->iinstr
+
+*******************************************************************************/
+
+void graph_phi_moves(jitdata *jd, basicblock *bptr, basicblock *dst_goto) {
+ int lt_d,lt_s,i;
+ lsradata *ls;
+ instruction *iptr;
+
+ ls = jd->ls;
+
+ _GRAPH_ASSERT(ls->num_phi_moves[bptr->nr] > 0);
+ bptr->icount = ls->num_phi_moves[bptr->nr];
+ if (dst_goto != NULL)
+ bptr->icount++;
+ bptr->iinstr = iptr = DMNEW(instruction, bptr->icount);
+
+ _GRAPH_ASSERT(iptr != NULL);
+
+ /* 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(GRAPH_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf("graph_phi_moves: BB %3i Move %3i <- %3i\n", bptr->nr,
+ lt_d, lt_s);
+#endif
+ if (lt_s == UNUSED) {
+#if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf(" ... not processed \n");
+#endif
+ continue;
+ }
+
+ _GRAPH_ASSERT(d->type != -1);
+ _GRAPH_ASSERT(s->type == -1);
+
+ iptr->opc = ICMD_MOVE;
+ iptr->s1.varindex = ls->lifetime[lt_s].v_index;
+ iptr->dst.varindex = ls->lifetime[lt_d].v_index;
+ iptr++;
+ }
+
+ if (dst_goto != NULL) {
+ iptr->opc = ICMD_GOTO;
+ iptr->dst.block = dst_goto;
+ }
+}
+
#ifdef GRAPH_DEBUG_VERBOSE
void graph_print(lsradata *ls, graphdata *gd) {
int i,j;
Authors: Christian Ullrich
+ $Id: lifetimes.c $
*/
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
+/* printf("param %3i -> L %3i/%3i\n",p,i,t); */
_LT_ASSERT(t == VAR(i)->type);
/* Param to Local init happens before normal Code */
/* real ICMD, no phi-function, no param initialisation */
_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;
lt_is_live(ls, lt, b_index, iindex);
- if (iindex == -ls->varcount-1) {
+ if (iindex == -ls->ssavarcount-1) {
#ifdef LT_DEBUG_VERBOSE
if ((compileverbose))
lt->v_index, b_index, iindex);
#endif
/* iindex is the first statement of b_index */
- /* Statements -ls->max_vars-1 .. -1 are possible phi functions*/
+ /* Statements -ls->ssavarcounts-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);
/* look through phi functions */
- for(; prev_iindex > -ls->varcount-1; prev_iindex--)
+ for(; prev_iindex > -ls->ssavarcount-1; prev_iindex--)
if (ls->phi[b_index][-prev_iindex-1] != NULL)
break;
void lt_move_use_sites(struct lifetime *from, struct lifetime *to) {
struct site *s;
+#if 0
+ /* not anymore true for copy propagated lifetimes */
_LT_ASSERT(from->use != NULL);
+#endif
if (from->use == NULL)
return;
for(s = from->use; s->next != NULL; s = s->next);
}
}
-
if (bptr->iinstr != NULL) {
/* set iptr to last instruction of BB */
iptr = bptr->iinstr + iindex;
/* src/vm/jit/optimizing/lsra.inc - linear scan register allocator
- Copyright (C) 2005, 2006, 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
Institut f. Computersprachen - TU Wien
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.
-*/
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+ $Id: lsra.c $
+*/
#include "config.h"
#include <stdio.h>
#include "vm/jit/reg.h"
#include "vm/jit/jit.h"
-
#include "vm/jit/optimizing/graph.h"
#include "vm/jit/optimizing/lifetimes.h"
#include "vm/jit/optimizing/ssa.h"
#include "vm/jit/optimizing/lsra.h"
-#ifdef LSRA_TESTLT
-# include "vm/resolve.h"
-#include "vm/builtin.h"
-#endif
-
-
#include "toolbox/logging.h"
extern const char *string_java_lang_InternalError;
/* function prototypes */
-void lsra_init(jitdata *);
-graphdata *lsra_setup(jitdata *);
+void lsra_setup(jitdata *);
void lsra_main(jitdata *);
#ifdef LSRA_DEBUG_VERBOSE
void lsra_dump_stack(stackptr );
codegendata *cd;
registerdata *rd;
lsradata *ls;
- graphdata *gd;
#if defined(ENABLE_STATISTICS)
int locals_start;
int i,j;
#if defined(LSRA_DEBUG_VERBOSE)
if (compileverbose) {
printf("%s %s ",m->class->name->text, m->name->text);
- if (code_is_leafmethod(code))
+ if (code_is_leafmethod(jd->code))
printf("**Leafmethod**");
printf("\n");
}
{ int dummy=1; dummy++; }
#endif
#endif
-
- lsra_init(jd);
- gd = lsra_setup(jd);
+
+ lsra_setup(jd);
#if defined(ENABLE_STATISTICS)
/* find conflicts between locals for statistics */
#endif
/* Run LSRA */
lsra_main(jd);
-#ifdef LSRA_TESTLT
- test_lifetimes( jd, gd );
-#endif
+
fflush(stdout);
}
-void lsra_init(jitdata *jd)
-{
- lsradata *ls = jd->ls;
-
- /* Init LSRA Data Structures */
- /* allocate lifetimes for all Basicblocks */
-
- ls->v_index = -1;
-}
-
-graphdata *lsra_setup(jitdata *jd)
+void lsra_setup(jitdata *jd)
{
methodinfo *m;
codegendata *cd;
registerdata *rd;
lsradata *ls;
- graphdata *gd;
#if defined(ENABLE_LOOPS)
/* Loop optimization "destroys" the basicblock array */
rd = jd->rd;
ls = jd->ls;
- ssa_init(jd);
-
- /* Setup LSRA Data structures */
-
- /* 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(jd->basicblockcount + 1);
- graph_make_cfg(jd, gd);
- ssa(jd, gd);
- lt_lifeness_analysis(jd, gd);
-
#ifdef LSRA_DEBUG_VERBOSE
if (compileverbose) {
printf("Lifetimes after LifenessAnalyse: \n");
printf("Basicblockcount: %4i\n",ls->basicblockcount);
}
#endif
- return gd;
}
void lsra_reg_setup(jitdata *jd,
int_reg->nregdesc = nregdescint;
flt_reg->nregdesc = nregdescfloat;
- if (code_is_leafmethod(code)) {
+ if (code_is_leafmethod(jd->code)) {
/* Temp and Argumentregister can be used as saved registers */
int_reg->sav_top = INT_ARG_CNT + INT_TMP_CNT + INT_SAV_CNT;
int param_count;
int i,j,tmp;
- /* count number of parameters ( .i_start == -1) */
+ /* count number of parameters ( .i_start == 0) */
for (param_count=0; (param_count < lifetime_count) &&
-/* (ls->lifetime[lifetime[param_count]].i_start == -1); param_count++); */
(ls->lifetime[lifetime[param_count]].i_start == 0); param_count++);
if (param_count > 0) {
for (p=fmem; (p->next!=NULL) && (p->next->end < fm->end); p=p->next);
fm->next=p->next;
p->next=fm;
- return fm->off;
+ /* HACK: stackslots are 8 bytes on all architectures for now, I hope.
+ * -- pm
+ */
+ return fm->off * 8;
}
struct freemem *lsra_getnewmem(int *mem_use)
#ifdef LSRA_SAVEDVAR
lt->savedvar = SAVEDVAR;
#endif
- if (lt->savedvar || code_is_leafmethod(code)) {
+ if (lt->savedvar || code_is_leafmethod(jd->code)) {
/* use Saved Reg (in case of leafmethod all regs are saved regs) */
if (reg->sav_top > regsneeded) {
#if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
if (active[i]->i_end > lt->i_start) break;
/* make active[i]->reg available again */
- if (code_is_leafmethod(code)) {
+ if (code_is_leafmethod(jd->code)) {
/* leafmethod -> don't care about type -> put all again into */
/* reg->sav_reg */
#if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
ls = jd->ls;
- if (lt->savedvar || code_is_leafmethod(code)) {
+ if (lt->savedvar || code_is_leafmethod(jd->code)) {
_spill_at_intervall(lt, ls->active_sav, &(ls->active_sav_top));
} else {
_spill_at_intervall(lt, ls->active_tmp, &(ls->active_tmp_top));
switch (lt->type) {
case TYPE_LNG:
-#if defined(HAS_4BYTE_STACKSLOT) && !defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
+#if (defined(HAS_4BYTE_STACKSLOT) && !defined(SUPPORT_COMBINE_INTEGER_REGISTERS)) || defined (__I386__)
flags = 0;
#else
flags = 1;
Authors: Christian Ullrich
+ $Id: lsra.h,v 1.17 2005/11/22 14:36:16 christian Exp $
*/
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)<(b)?(b):(a))
-struct _backedge {
- int start;
- int end;
- int nesting;
- struct _backedge *next;
-};
-
struct site {
int b_index;
int iindex;
int nesting;
};
-/*
-struct stackslot {
- stackptr s;
- int bb;
- struct stackslot *next;
-};
-*/
-
struct lsra_register {
int *sav_reg;
int *tmp_reg;
int use;
};
-struct igraph_lookup {
- int var;
- int igraph;
-};
-
-struct igraph_interference {
- int v1;
- int v2;
- struct igraph_interference *next;
-};
-
-struct igraph_vars {
- int v;
- struct igraph_vars *next;
-};
-
-struct igraph {
- struct igraph_interference *inter;
- struct igraph_vars *vars;
-};
-
-
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 */
int *sorted; /* BB sorted in reverse post order */
int *sorted_rev; /* BB reverse lookup of sorted */
- struct _backedge **backedge; /* backedge data structure */
- int backedge_count; /* number of backedges */
-
long *nesting; /* Nesting level of BB*/
struct lifetime *lifetime; /* array of lifetimes */
int active_tmp_top, active_sav_top;
struct lsra_exceptiontable *ex;
- int v_index; /* next free index for stack slot lifetimes */
- /* decrements from -1 */
/* SSA fields */
bitvector *var_def; /* LocalVar Definition Bitvector [0..ls->bbcount] */
int **stack;
int *stack_top;
- /* structures for phi var interference graphs */
- struct igraph_lookup **igraph_lookup; /* var to igraph index */
- int igraph_lookup_top; /* number of entries in above table */
- struct igraph *igraph; /* interference graphs */
- int igraph_top;
};
/* src/vm/jit/optimizing/ssa.c - static single-assignment form
- Copyright (C) 2005, 2006, 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ Copyright (C) 2005 - 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
Institut f. Computersprachen - TU Wien
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.
-*/
+ Contact: cacao@complang.tuwien.ac.at
+ Authors: Christian Ullrich
-#include "config.h"
+ $Id: $
+*/
#include <stdio.h>
#include <stdlib.h>
#include "vm/jit/optimizing/lsra.h"
#include "vm/jit/optimizing/ssa.h"
+#include "vm/jit/optimizing/ssa_rename.h"
+#include "vm/jit/optimizing/ssa_phi.h"
#if defined(SSA_DEBUG_VERBOSE)
#include "vmcore/options.h" /* compileverbose */
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(jitdata *jd, graphdata *gd, dominatordata *dd);
void ssa_print_lt(lsradata *ls);
+void _ssa_print_lt(struct lifetime *lt);
void ssa_show_variable(jitdata *jd, int index, varinfo *v, int stage);
void ssa_print_phi(lsradata *, graphdata *);
#endif
SSA main procedure:
-******************************************************************************/
+SSA Algorithms are based on "modern compiler implementation in C" from andrew
+w. appel, edition 2004
+
+Corrections:
+page 441 Algorithm 19.6. Inserting phi-functions:
+
+...
+ for each Y in DF[n]
+- if Y not element of A phi [n]
++ if a not element of A phi [n]
+ insert the statment a <- ...
+...
+...
+- A phi [n] <- A phi [n] join {Y}
++ A phi [n] <- A phi [n] join {a}
+- if Y not element of A orig [n]
++ if a not element of A orig [Y]
+ W <- W join {Y}
-void ssa(jitdata *jd, graphdata *gd) {
+******************************************************************************/
+void ssa(jitdata *jd) {
struct dominatordata *dd;
lsradata *ls;
+ graphdata *gd;
+
+#if defined(ENABLE_LOOPS)
+ /* Loop optimization "destroys" the basicblock array */
+ /* TODO: work with the basicblock list */
+ if (opt_loops) {
+ log_text("lsra not possible with loop optimization\n");
+ exit(1);
+ }
+#endif
ls = jd->ls;
+ ssa_init(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(jd->basicblockcount + 1);
+ graph_make_cfg(jd, gd);
+
dd = compute_Dominators(gd, ls->basicblockcount);
computeDF(gd, dd, ls->basicblockcount, 0);
ssa_print_lt(ls);
}
#endif
-/* dead_code_elimination(jd, gd); */
+ if (opt_ssa_dce) {
+ 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);
- }
+ 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);
}
+ if (opt_ssa_cp) {
+ 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
+ }
ssa_generate_phi_moves(jd, gd);
transform_BB(jd, gd);
+ lt_lifeness_analysis(jd, gd);
#ifdef SSA_DEBUG_CHECK
{
#endif
-
#ifdef SSA_DEBUG_VERBOSE
if (compileverbose)
ssa_print_trees(jd, gd, dd);
#endif
+
}
/* ssa_init *******************************************************************
# if defined(SSA_DEBUG_VERBOSE)
if (compileverbose) {
printf("%s %s ",m->class->name->text, m->name->text);
- if (code_is_leafmethod(code))
+ if (code_is_leafmethod(jd->code))
printf("**Leafmethod**");
printf("\n");
}
jd->basicblockcount, jd->localcount);
#endif
- /* 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 */
+ /* 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->num_defs = DMNEW(int, jd->varcount);
ls->new_varindex = DMNEW(int , jd->varcount);
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 */
+ /* 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 ed to start at block 1 */
/* don't look at already eliminated (not used) parameters (locals) */
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) {
-
printf("ssa_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
ls->ssavarcount);
for(i = 0; i < jd->varcount; i++) {
}
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(jitdata *jd, graphdata *gd, dominatordata *dd)
-{
- int a,i,j,n,Y;
- bitvector *def_sites;
- bitvector *A_phi; /* [0..ls->basicblockcount[ of ls->ssavarcount Bit */
- worklist *W;
- int num_pred;
-
- lsradata *ls;
-
- ls = jd->ls;
-
- W = wl_new(ls->basicblockcount);
-
- 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->ssavarcount);
- for(j = 0; j < ls->ssavarcount; j++)
- ls->phi[i][j] = NULL;
- A_phi[i] = bv_new(ls->ssavarcount);
- }
-
- /* 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->ssavarcount; i++) {
- printf("def_sites[%3i]=%p:",i,(void *)def_sites[i]);
- for(j = 0; j < ls->basicblockcount; j++) {
- if ((j % 5) == 0) printf(" ");
- if (bv_get_bit(def_sites[i], j))
- printf("1");
- else
- printf("0");
- }
- printf(" (");
-
- printf("\n");
- }
- }
-#endif
-
- 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);
- }
-
- while (!wl_is_empty(W)) { /* W not empty */
- n = wl_get(W);
-
- for(i = 0; i < dd->num_DF[n]; i++) {
- Y = dd->DF[n][i];
- /* Node Y is in Dominance Frontier of n -> */
- /* insert phi function for a at top of Y*/
- _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
- if (bv_get_bit( A_phi[Y], a) == 0) {
- /* 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)))) */
-
-#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 */
-
-#endif
- 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:*/
- /* if Y had no definition for a insert it*/
- /* into the Worklist, since now it */
- /* defines a through the phi function */
- wl_add(W, Y);
- }
- }
- }
- }
- }
-}
-
-/* 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 */
-
- 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 (code_is_leafmethod(code))
- 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->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_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 (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][a][p] = ls->var_0[a];
-#endif
-
- /* Initialization */
-
- 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->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->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->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->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_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 = 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 a) {
- int i;
-
- _SSA_CHECK_BOUNDS(a,0,ls->ssavarcount);
- ls->count[a]++;
- i = ls->count[a] - 1;
- /* push i on stack[a] */
- _SSA_CHECK_BOUNDS(ls->stack_top[a], 0, ls->num_defs[a] + 1);
- ls->stack[a][ls->stack_top[a]++] = i;
- return i;
-}
-
-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]++;
- }
-}
-
-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;
- 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 */
- 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, max(1, ls->ssavarcount));
- for(i = 0; i < ls->ssavarcount; i++)
- def_count[i] = 0;
-
- /* 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*/
- 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]->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--;
- }
-/* out = ls->basicblocks[n]->outvars; */
-/* out_d = ls->basicblocks[n]->outdepth - 1; */
-
-/* for(; out_d > in_d; 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);
-
- /* 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
- ssa_rename_print( NULL, "invar", in[in_d], ls->var_0[a]+i);
-#endif
- 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;
- }
-
- iptr = ls->basicblocks[n]->iinstr;
-
- for(iindex = 0; iindex < ls->basicblocks[n]->icount; iindex++, iptr++) {
-
- /* check for use (s1, s2, s3 or special (argp) ) */
-
- 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;
-
- /* now "fall through" for handling of s2 and s1 */
-
- 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;
-
- /* now "fall through" for handling of s1 */
-
- 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;
- }
-
-
- /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
- /* an optional dst - so they to be checked first */
-
- 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) {
- j = ssa_rename_def(jd, def_count, iptr->dst.varindex);
-#ifdef SSA_DEBUG_VERBOSE
- ssa_rename_print( iptr, "dst", iptr->dst.varindex, j);
-#endif
- iptr->dst.varindex = j;
- }
-
- /* ?????????????????????????????????????????????????????????? */
- /* Mark Def as use, too. Since param initialisation is in */
- /* var_def and this would not remove this locals, if not used */
- /* elsewhere */
- /* ?????????????????????????????????????????????????????????? */
-
- }
-
- /* change outstack Interface stackslots */
- out = ls->basicblocks[n]->outvars;
- out_d = ls->basicblocks[n]->outdepth - 1;
-
- 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);
-
- a = ls->new_varindex[out[out_d]];
- _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
-
- /* 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
- 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;
- }
-
- /* 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
- if (compileverbose) {
- printf("Succ %3i Arg %3i \n", Y, j);
- ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], UNUSED);
- }
-#endif
- 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("Succ %3i Arg %3i \n", Y, j);
- ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], i);
- }
-#endif
- 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 ? */
- /* ????????????????????????????????????????????? */
-
- }
- }
-
- /* 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(jitdata *jd, graphdata *gd, dominatordata *dd) {
int i,j;
printf(")\n");
}
}
-
-void ssa_print_phi(lsradata *ls, graphdata *gd) {
- int i,j,k;
-
- printf("phi Functions (varcount_with_indices: %3i):\n",
- ls->varcount_with_indices);
- for(i = 0; i < ls->basicblockcount; i++) {
- 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++)
- printf("%3i ",ls->phi[i][j][k]);
- printf(")\n");
- }
- }
- }
-
-}
-
#endif
-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->ssavarcount; a++)
- if (ls->phi[i][a] != NULL) {
-#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]++;
- }
- }
- }
-
- /* allocate ls->phi_moves */
- ls->phi_moves = DMNEW( int **, ls->basicblockcount);
- for(i = 0; i < ls->basicblockcount; i++) {
- 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->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->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[i][a][j+1];
- }
- }
- }
- }
-}
/****************************************************************************
Optimizations
W = wl_new(ls->lifetimecount);
if (ls->lifetimecount > 0) {
- /* put all lifetimes on Worklist */
+
+ /* put all lifetimes into Worklist W */
+
for(a = 0; a < ls->lifetimecount; a++) {
- if (ls->lifetime[a].type != -1) {
+ if (ls->lifetime[a].type != UNUSED) {
wl_add(W, a);
}
}
}
/* Remove unused lifetimes */
+
while(!wl_is_empty(W)) {
+
/* take a var out of Worklist */
+
a = wl_get(W);
lt = &(ls->lifetime[a]);
- if ((lt->def == NULL) || (lt->type == -1))
+ if ((lt->def == NULL) || (lt->type == UNUSED))
+
/* lifetime was already removed -> no defs anymore */
+
continue;
- /* Remove lifetimes, which are only used in a phi function, which
- defines them! */
+ /* Remove lifetimes, which are only used in the phi function which */
+ /* defines them! */
+
remove_statement = (lt->use != NULL) && (lt->use->iindex < 0);
for(use = lt->use; (remove_statement && (use != NULL));
use = use->next)
(use->b_index == lt->def->b_index) &&
(use->iindex == lt->def->iindex);
}
+
if (remove_statement) {
#ifdef SSA_DEBUG_CHECK
+
/* def == use can only happen in phi functions */
+
if (remove_statement)
_SSA_ASSERT(lt->use->iindex < 0);
#endif
+
/* give it free for removal */
+
lt->use = NULL;
}
if (lt->use == NULL) {
+
/* Look at statement of definition of a and remove it, */
/* if the Statement has no sideeffects other than the assignemnt */
/* of a */
+
if (lt->def->iindex < 0 ) {
+
/* phi function */
/* delete use of sources , delete phi functions */
NULL);
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->varcount_with_indices) &&
- (source != lt->v_index)) {
+ i++) {
+ source =
+ ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
+ if ((source != ls->varcount_with_indices) &&
+ (source != lt->v_index) &&
+ (source != UNUSED)) {
- /* phi Argument was not already removed (already in
- because of selfdefinition) */
+ /* phi Argument was not already removed (already in
+ because of "selfdefinition") */
- s_lt = &(ls->lifetime[source]);
+ s_lt = &(ls->lifetime[source]);
- /* remove it */
+ /* remove it */
- lt_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 */
+ /* put it on the Worklist */
- wl_add(W, source);
- }
+ wl_add(W, source);
}
+ }
+
/* now delete phi function itself */
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("dce: BB%3i phi for var %3i=%3i removed \n",
+ lt->def->b_index, -lt->def->iindex - 1,
+ lt->v_index);
+ }
+#endif
+
ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL;
- } else {
+ }
+ else {
+
/* "normal" Use by ICMD */
+
remove_statement = false;
if (lt->def->b_index != 0) {
iptr = ls->basicblocks[lt->def->b_index]->iinstr +
lt->def->iindex;
- if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI)
- remove_statement = false;
+ if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
- /* if ICMD could throw an exception do not remove it! */
+ /* if ICMD could throw an exception do not remove it! */
- else {
+ remove_statement = false;
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("dce: PEI: BB%3i II%3i %s not removed \n",
+ lt->def->b_index, lt->def->iindex,
+ opcode_names[iptr->opc]);
+ }
+#endif
- /* 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);
- }
+ }
+ else {
+ remove_statement = true;
+
+ 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);
+
+ /* "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);
+
+ /* "fall through" for handling of s1 */
+
+ /* DF_{IINC,STORE,LOAD} are DF_{1_TO_1,MOVE,COPY} */
+
+ 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);
+ }
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("dce: BB%3i II%3i %s removed \n",
+ lt->def->b_index, lt->def->iindex,
+ opcode_names[iptr->opc]);
}
+#endif
}
if (remove_statement) {
#ifdef SSA_DEBUG_VERBOSE
if (compileverbose)
- printf("INFO: %s %s:at BB %3i II %3i NOP-<%s\n",
+ printf("dce: %s %s:at BB %3i II %3i NOP-<%s\n",
m->class->name->text, m->name->text,
lt->def->b_index, lt->def->iindex,
icmd_table[iptr->opc].name);
/* remove definition of a */
- VAR(lt->v_index)->type = -1;
- lt->type = -1;
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ printf("dce: var %3i removed\n", lt->v_index);
+#endif
+ VAR(lt->v_index)->type = UNUSED;
+ lt->type = UNUSED;
lt->def = NULL;
+/* jd->var */
} /* if (lt->use == NULL) */
} /* while(!wl_is_empty(W)) */
} /* dead_code_elimination */
instruction *iptr;
struct lifetime *lt, *s_lt;
- s4 *in;
lsradata *ls;
if (ls->lifetimecount > 0) {
/* put all lifetimes on Worklist */
for(a = 0; a < ls->lifetimecount; a++) {
- if (ls->lifetime[a].type != -1) {
+ if (ls->lifetime[a].type != UNUSED) {
wl_add(W, a);
}
}
a = wl_get(W);
lt = ls->lifetime + a;
- if (lt->type == -1)
+ if (lt->type == UNUSED)
continue;
_SSA_ASSERT(lt->def != NULL);
+#if 0
_SSA_ASSERT(lt->use != NULL);
+#endif
if (lt->def->iindex < 0 ) {
/* phi function */
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->varcount_with_indices) {
+ if ((source != ls->varcount_with_indices) &&
+ (source != UNUSED)) {
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->varcount_with_indices;
break;
}
}
}
+
if (only_source != ls->varcount_with_indices) {
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ printf(
+ "-- copy propagation phi-func: BB %3i II %3i: %3i -> %3i\n",
+ lt->def->b_index, lt->def->iindex,
+ only_source, lt->v_index);
+#endif
+ s_lt = ls->lifetime + only_source;
+
/* replace all use sites of lt with the var_index only_source */
ssa_replace_use_sites( jd, gd, lt, only_source, W);
- /* delete def of lt and replace uses of lt with "only_source" */
+ /* delete def of lt */
ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL;
- s_lt = ls->lifetime + only_source;
+ /* remove this deleted use site of s_lt */
- 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 */
+
lt_move_use_sites(lt, s_lt);
- lt->type = -1;
+
+ /* invalidate lt */
+
+ lt->type = UNUSED;
+ VAR(lt->v_index)->type = UNUSED;
+
+ /* add s_lt again to Worklist W */
+
+ wl_add(W, s_lt->v_index);
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ _ssa_print_lt(s_lt);
+#endif
} /* if (only_source != ls->varcount_with_indices) */
- } else { /* if (lt->def->iindex < 0 )*/
+ }
+ else { /* if (lt->def->iindex < 0 ) */
+
+ /* def in argument passing - no propagation possible */
+ /* (there is no ICMD for this... */
+
+ if (lt->def->b_index == 0)
+ continue;
+
/* def in "normal" ICMD */
-#if 0
+
iptr = ls->basicblocks[lt->def->b_index]->iinstr +
lt->def->iindex;
-
- if ( localvar ) {
- if (lt->def->b_index == 0)
- continue;
-
- switch(iptr->opc) {
- case ICMD_ISTORE:
- case ICMD_LSTORE:
- case ICMD_FSTORE:
- case ICMD_DSTORE:
+
+ switch(iptr->opc) {
+ case ICMD_ISTORE:
+ case ICMD_LSTORE:
+ case ICMD_FSTORE:
+ case ICMD_DSTORE:
case ICMD_ASTORE:
- if (lt->def->iindex == 0) {
- /* first instruction in bb -> instack==bb->instack */
- in = ls->basicblocks[lt->def->b_index]->instack;
- } else {
- /* instack is (iptr-1)->dst */
- in = (iptr-1)->dst;
- }
-
- if (in->varkind != LOCALVAR) {
+ case ICMD_ILOAD:
+ case ICMD_LLOAD:
+ case ICMD_FLOAD:
+ case ICMD_DLOAD:
+ case ICMD_ALOAD:
+ case ICMD_MOVE:
#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- printf("copy propagation xstore: BB %3i I %3i: %3i -> %3i\n", lt->def->b_index, lt->def->iindex, iptr->op1, in->varnum);
+ if (compileverbose)
+ printf(
+ "-- copy propagation %3i %s: BB %3i II %3i: %3i -> %3i\n",
+ iptr->opc, opcode_names[iptr->opc], lt->def->b_index,
+ lt->def->iindex, iptr->s1.varindex,
+ iptr->dst.varindex);
#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 */
-
- ssa_replace_use_sites(jd, gd, s_lt, iptr->op1, W);
+ s_lt = ls->lifetime + iptr->s1.varindex;
- /* s_lt->def is the new def site of lt */
- /* the old ->def site will get a use site of def */
- /* only one def site */
- _SSA_ASSERT(lt->def->next == NULL);
- _SSA_ASSERT(s_lt->def != NULL);
- _SSA_ASSERT(s_lt->def->next == NULL);
-
- /* replace def of s_lt with iptr->op1 */
- if (s_lt->def->iindex < 0) {
- /* phi function */
- _SSA_ASSERT(ls->phi[s_lt->def->b_index]
- [-s_lt->def->iindex-1]
- != NULL);
- ls->phi[s_lt->def->b_index][-s_lt->def->iindex-1][0]
- = iptr->op1;
- } else
- if (in->varnum != iptr->op1)
- printf("copy propagation: LOCALVAR ss->ISTORE BB %i II %i\n",
- lt->def->b_index, lt->def->iindex);
-
+ _SSA_ASSERT( lt->v_index == iptr->dst.varindex);
+
+ /* replace all use sites of lt with the var_index */
+ /* iptr->s1.varindex (==lt->v_index) */
+
+ ssa_replace_use_sites(jd, gd, lt, iptr->s1.varindex, W);
+
+ _SSA_ASSERT(lt->def->next == NULL);
+ _SSA_ASSERT(s_lt->def != NULL);
+ _SSA_ASSERT(s_lt->def->next == NULL);
- /* move def to use sites of lt */
- lt->def->next = lt->use;
- lt->use = lt->def;
-
- lt->def = s_lt->def;
+ /* this ICMD is not a PEI -> so no danger in deleting it! */
+ /* delete def of lt (ICMD_NOP) */
- s_lt->def = NULL;
+ /* lt->def->iindex > 0 -> ICMD */
+ iptr->opc = ICMD_NOP;
- /* move use sites from s_lt to lt */
- move_use_sites(s_lt, lt);
- move_stackslots(s_lt, lt);
- s_lt->type = -1;
- }
- break;
- }
- } else {
- /* Def Interface Stackslot */
-
- switch(iptr->opc) {
- case ICMD_ILOAD:
- case ICMD_LLOAD:
- case ICMD_FLOAD:
- case ICMD_DLOAD:
- case ICMD_ALOAD:
- only_source = lt->local_ss->s->varnum;
- if (lt->local_ss->s->varkind != LOCALVAR) {
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- printf("copy propagation xload: BB %3i I %3i: %3i -> %3i\n", lt->def->b_index, lt->def->iindex, iptr->op1, lt->local_ss->s->varnum);
-#endif
- _SSA_ASSERT(iptr->dst->varnum == lt->local_ss->s->varnum);
- for (ss = lt->local_ss; ss != NULL; ss = ss->next) {
- ss->s->varkind = LOCALVAR;
- ss->s->varnum = iptr->op1;
- }
+ /* remove this deleted use site of s_lt */
- /* replace all use sites of lt with the var_index iptr->op1*/
+ lt_remove_use_site(s_lt, lt->def->b_index, lt->def->iindex);
- ssa_replace_use_sites(jd, gd, lt, iptr->op1, W);
+ /* invalidate def site of lt */
- lt->def = NULL;
-
- s_lt = &(ls->lifetime[ls->maxlifetimes + iptr->op1]);
-
- /* move use sites from lt to s_lt */
- move_use_sites(lt, s_lt);
- move_stackslots(lt, s_lt);
- lt->type = -1;
- } else
- 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 */
+ lt->def = NULL;
+
+ /* move use sites from lt to s_lt */
+
+ lt_move_use_sites(lt, s_lt);
+
+ /* invalidate lt */
+
+ lt->type = UNUSED;
+ VAR(lt->v_index)->type = UNUSED;
+
+ /* add s_lt again to Worklist W */
+ wl_add(W, s_lt->v_index);
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ _ssa_print_lt(s_lt);
#endif
- } /* i(lt->def->iindex < 0 ) */
-
+ break;
+ }
+ } /* if (lt->def->iindex < 0 ) */
} /* while(!wl_is_empty(W)) */
}
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) {
+ if (source == lt->v_index) {
+
+ /* check if this use in this phi function is a */
+ /* "selfdefinition" (x = phi(...,x,...)) */
+ /* if so replace the use with -1 (x=phi(...,-1,...)*/
+
+ if (new_v_index == ls->phi[s->b_index][-s->iindex-1][0]) {
#ifdef SSA_DEBUG_VERBOSE
- if (W != NULL) {
- if (compileverbose)
- printf("copy propagation phi: BB %3i I %3i: %3i -> \
- %3i\n", s->b_index, s->iindex,
- new_v_index, source);
+ if (W != NULL) {
+ if (compileverbose)
+ printf(
+ "copy propagation phi: BB %3i I %3i: %3i -> %3i\n",
+ s->b_index, s->iindex, -1, source);
+ }
+#endif
+ ls->phi[s->b_index][-s->iindex-1][i] = -1;
+
+ /* remove this use site of use site */
+ lt_remove_use_site(lt, s->b_index, s->iindex);
}
+ else {
+#ifdef SSA_DEBUG_VERBOSE
+ if (W != NULL) {
+ if (compileverbose)
+ printf(
+ "copy propagation phi: BB %3i I %3i: %3i -> %3i\n",
+ s->b_index, s->iindex, new_v_index, source);
+ }
#endif
- ls->phi[s->b_index][-s->iindex-1][i]
- = new_v_index;
+ ls->phi[s->b_index][-s->iindex-1][i] = new_v_index;
+ }
}
}
if (W != NULL) {
#ifdef SSA_DEBUG_VERBOSE
if (W != NULL) {
if (compileverbose)
- printf("copy propagation loc: BB %3i I %3i: %3i -> \
+ printf("copy propagation loc3: BB %3i I %3i: %3i -> \
%3i\n", s->b_index, s->iindex,
new_v_index, iptr->sx.s23.s3.varindex);
}
#ifdef SSA_DEBUG_VERBOSE
if (W != NULL) {
if (compileverbose)
- printf("copy propagation loc: BB %3i I %3i: %3i -> \
+ printf("copy propagation loc2: BB %3i I %3i: %3i -> \
%3i\n", s->b_index, s->iindex,
new_v_index, iptr->sx.s23.s2.varindex);
}
#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->s1.varindex);
+ printf(
+ "copy propagation loc1: BB %3i I %3i: %3i -> %3i\n",
+ s->b_index, s->iindex, new_v_index,
+ iptr->s1.varindex);
}
#endif
iptr->s1.varindex = new_v_index;
if (W != NULL) {
if (compileverbose)
printf(
- "copy propagation loc: BB %3i I %3i: %3i -> %3i\n"
+ "copy propagation locN: BB %3i I %3i: %3i -> %3i\n"
, s->b_index, s->iindex, new_v_index, *argp);
}
#endif
void ssa_print_lt(lsradata *ls) {
int i;
struct lifetime *lt;
- struct site *use;
printf("SSA LT Def/Use\n");
for(i = 0; i < ls->lifetimecount; i++) {
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);
- else
- printf("%3i,%3i Use: ",0,0);
- for(use = lt->use; use != NULL; use = use->next)
- printf("%3i,%3i ",use->b_index, use->iindex);
- printf("\n");
- }
+ _ssa_print_lt(lt);
+ }
+}
+
+void _ssa_print_lt(struct lifetime *lt) {
+ struct site *use;
+
+ 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);
+ else
+ printf("%3i,%3i Use: ",0,0);
+ for(use = lt->use; use != NULL; use = use->next)
+ printf("%3i,%3i ",use->b_index, use->iindex);
+ printf("\n");
}
}
/* src/vm/jit/optimizing/ssa.h - static single assignment form header
- Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ Copyright (C) 2005 - 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
Institut f. Computersprachen - TU Wien
Authors: Christian Ullrich
+ $Id: ssa.h$
*/
/* function prototypes */
void ssa_init(jitdata *);
-void ssa(jitdata *, graphdata *);
+void ssa(jitdata */* , graphdata **/);
#endif /* _SSA_H */
--- /dev/null
+/* src/vm/jit/optimizing/ssa.c - static single-assignment form
+
+ Copyright (C) 2005 - 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
+ C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
+ Institut f. Computersprachen - TU Wien
+
+ This file is part of CACAO.
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2, or (at
+ your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+
+ $Id: $
+
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "mm/memory.h"
+
+#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/lsra.h"
+#include "vm/jit/optimizing/ssa.h"
+#include "vm/jit/optimizing/ssa_phi.h"
+
+#if defined(SSA_DEBUG_VERBOSE)
+#include "vmcore/options.h" /* compileverbose */
+#endif
+
+/* ssa_place_phi_functions *****************************************************
+
+Algorithm is based on "modern compiler implementation in C" from andrew
+w. appel, edition 2004
+
+Corrections:
+page 441 Algorithm 19.6. Inserting phi-functions:
+
+...
+ for each Y in DF[n]
+- if Y not element of A phi [n]
++ if a not element of A phi [n]
+ insert the statment a <- ...
+...
+...
+- A phi [n] <- A phi [n] join {Y}
++ A phi [n] <- A phi [n] join {a}
+- if Y not element of A orig [n]
++ if a not element of A orig [Y]
+ W <- W join {Y}
+
+
+ls->phi[n][a][p] is created and populated.
+
+n in [0..ls->basicblockcount[
+a in [0..ls->ssavarcount[
+p in [1..Count of Predecessors of Basicblock n]
+
+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.
+
+
+ls->phi[n][a] == NULL, if no phi function for Variable a for Basicblock n exists
+
+or
+
+ls->phi[n][a][0] == a, representing the result of the phi function and
+ls->phi[n][a][p] == a, representing the arguments of the phi function.
+
+*******************************************************************************/
+
+
+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->ssavarcount Bit */
+ worklist *W;
+ int num_pred;
+
+ lsradata *ls;
+
+ ls = jd->ls;
+
+ W = wl_new(ls->basicblockcount);
+
+ 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->ssavarcount);
+ for(j = 0; j < ls->ssavarcount; j++)
+ ls->phi[i][j] = NULL;
+ A_phi[i] = bv_new(ls->ssavarcount);
+ }
+
+ /* 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->ssavarcount; i++) {
+ printf("def_sites[%3i]=%p:",i,(void *)def_sites[i]);
+ for(j = 0; j < ls->basicblockcount; j++) {
+ if ((j % 5) == 0) printf(" ");
+ if (bv_get_bit(def_sites[i], j))
+ printf("1");
+ else
+ printf("0");
+ }
+ printf(" (");
+
+ printf("\n");
+ }
+ }
+#endif
+
+ 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);
+ }
+
+ while (!wl_is_empty(W)) { /* W not empty */
+ n = wl_get(W);
+
+ for(i = 0; i < dd->num_DF[n]; i++) {
+ Y = dd->DF[n][i];
+
+ /* Node Y is in Dominance Frontier of n -> */
+ /* insert phi function for a at top of Y*/
+
+ _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
+ if (bv_get_bit( A_phi[Y], a) == 0) {
+
+ /* 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 */
+
+ 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: */
+ /* if Y had no definition for a, insert it */
+ /* into the Worklist, since now it */
+ /* defines a through the phi function */
+
+ wl_add(W, Y);
+ }
+ }
+ }
+ }
+ }
+}
+
+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->ssavarcount; a++)
+ if (ls->phi[i][a] != NULL) {
+#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]++;
+ }
+ }
+ }
+
+ /* allocate ls->phi_moves */
+
+ ls->phi_moves = DMNEW( int **, ls->basicblockcount);
+ for(i = 0; i < ls->basicblockcount; i++) {
+ 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->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->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[i][a][j+1];
+ }
+ }
+ }
+ }
+}
+
+#ifdef SSA_DEBUG_VERBOSE
+void ssa_print_phi(lsradata *ls, graphdata *gd) {
+ int i,j,k;
+
+ printf("phi Functions (varcount_with_indices: %3i):\n",
+ ls->varcount_with_indices);
+ for(i = 0; i < ls->basicblockcount; i++) {
+ 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++)
+ printf("%3i ",ls->phi[i][j][k]);
+ printf(")\n");
+ }
+ }
+ }
+
+}
+#endif
+
+/*
+ * These are local overrides for various environment variables in Emacs.
+ * Please do not remove this and leave it at the end of the file, where
+ * Emacs will automagically detect them.
+ * ---------------------------------------------------------------------
+ * Local variables:
+ * mode: c
+ * indent-tabs-mode: t
+ * c-basic-offset: 4
+ * tab-width: 4
+ * End:
+ */
--- /dev/null
+/* src/vm/jit/optimizing/ssa.h - static single assignment form header
+
+ Copyright (C) 2005 - 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
+ C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
+ Institut f. Computersprachen - TU Wien
+
+ This file is part of CACAO.
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2, or (at
+ your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+
+ $Id: ssa.h$
+
+*/
+
+
+#ifndef _SSA_PHI_H
+#define _SSA_PHI_H
+
+#include "vm/jit/optimizing/graph.h"
+
+#if !defined(NDEBUG)
+# include <assert.h>
+#endif
+
+/* function prototypes */
+void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd);
+void ssa_generate_phi_moves(jitdata *, graphdata *);
+#ifdef SSA_DEBUG_VERBOSE
+void ssa_print_phi(lsradata *ls, graphdata *gd);
+#endif
+
+#endif /* _SSA_PHI_H */
+
+/*
+ * 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
+ * Emacs will automagically detect them.
+ * ---------------------------------------------------------------------
+ * Local variables:
+ * mode: c
+ * indent-tabs-mode: t
+ * c-basic-offset): 4
+ * tab-width): 4
+ * End:
+ * vim:noexpandtab:sw=4:ts=4:
+ */
--- /dev/null
+/* src/vm/jit/optimizing/ssa.c - static single-assignment form
+
+ Copyright (C) 2005 - 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
+ C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
+ Institut f. Computersprachen - TU Wien
+
+ This file is part of CACAO.
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2, or (at
+ your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+
+ $Id: $
+
+*/
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "mm/memory.h"
+
+#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/lsra.h"
+#include "vm/jit/optimizing/ssa.h"
+#include "vm/jit/optimizing/ssa_rename.h"
+
+#if defined(SSA_DEBUG_VERBOSE)
+#include "vmcore/options.h" /* compileverbose */
+#endif
+
+/* function prototypes */
+void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n);
+int ssa_rename_def_(lsradata *ls, int a);
+
+/* 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*/
+ /* jd->varcount */
+
+
+ i = ls->new_varindex[i];
+
+ /* ignore return value, since first definition gives 0 -> */
+ /* no rename necessary */
+
+ 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 xi0=phi(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 UNUSED) */
+ /* 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] = UNUSED;
+ 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 (code_is_leafmethod(jd->code))
+ 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;
+#if 0
+ int p;
+#endif
+ lsradata *ls;
+
+ ls = jd->ls;
+
+ /* set up new locals */
+ /* 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_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 (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][a][p] = ls->var_0[a];
+#endif
+
+ /* Initialization */
+
+ 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->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->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->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->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_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 = 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 a) {
+ int i;
+
+ _SSA_CHECK_BOUNDS(a,0,ls->ssavarcount);
+ ls->count[a]++;
+ i = ls->count[a] - 1;
+ /* push i on stack[a] */
+ _SSA_CHECK_BOUNDS(ls->stack_top[a], 0, ls->num_defs[a] + 1);
+ ls->stack[a][ls->stack_top[a]++] = i;
+ return i;
+}
+
+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]++;
+ }
+}
+
+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
+
+/* ssa_rename_ ****************************************************************
+
+Algorithm is based on "modern compiler implementation in C" from andrew
+w. appel, edition 2004
+
+page 443 Algorithm 19.7. Renaming Variables
+
+*******************************************************************************/
+
+void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n) {
+ int a, i, j, k, iindex, Y, v;
+ int in_d, out_d;
+ 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 */
+ 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, max(1, ls->ssavarcount));
+ for(i = 0; i < ls->ssavarcount; i++)
+ def_count[i] = 0;
+
+ /* 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 - maybe this phi function */
+ /* can be removed for unused Vars*/
+
+ 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]->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--;
+ }
+/* out = ls->basicblocks[n]->outvars; */
+/* out_d = ls->basicblocks[n]->outdepth - 1; */
+
+/* for(; out_d > in_d; 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);
+
+ /* 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
+ ssa_rename_print( NULL, "invar", in[in_d], ls->var_0[a]+i);
+#endif
+ 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;
+ }
+
+ iptr = ls->basicblocks[n]->iinstr;
+
+ for(iindex = 0; iindex < ls->basicblocks[n]->icount; iindex++, iptr++) {
+
+ /* check for use (s1, s2, s3 or special (argp) ) */
+
+ 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;
+
+ /* now "fall through" for handling of s2 and s1 */
+
+ 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;
+
+ /* now "fall through" for handling of s1 */
+
+ 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;
+ }
+
+
+ /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
+ /* an optional dst - so they to be checked first */
+
+ 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) {
+ j = ssa_rename_def(jd, def_count, iptr->dst.varindex);
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( iptr, "dst", iptr->dst.varindex, j);
+#endif
+ iptr->dst.varindex = j;
+ }
+
+ /* ?????????????????????????????????????????????????????????? */
+ /* Mark Def as use, too. Since param initialisation is in */
+ /* var_def and this would not remove this locals, if not used */
+ /* elsewhere */
+ /* ?????????????????????????????????????????????????????????? */
+
+ }
+
+ /* change outstack Interface stackslots */
+ out = ls->basicblocks[n]->outvars;
+ out_d = ls->basicblocks[n]->outdepth - 1;
+
+ 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);
+
+ a = ls->new_varindex[out[out_d]];
+ _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
+
+ /* 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
+ 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;
+ }
+
+ /* 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
+ if (compileverbose) {
+ printf("Succ %3i Arg %3i \n", Y, j);
+ ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], UNUSED);
+ }
+#endif
+ 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("Succ %3i Arg %3i \n", Y, j);
+ ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], i);
+ }
+#endif
+ 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 ? */
+ /* ????????????????????????????????????????????? */
+
+ }
+ }
+
+ /* 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);
+ }
+}
+
+/*
+ * 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
+ * Emacs will automagically detect them.
+ * ---------------------------------------------------------------------
+ * Local variables:
+ * mode: c
+ * indent-tabs-mode: t
+ * c-basic-offset: 4
+ * tab-width: 4
+ * End:
+ */
--- /dev/null
+/* src/vm/jit/optimizing/ssa.h - static single assignment form header
+
+ Copyright (C) 2005 - 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
+ C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
+ Institut f. Computersprachen - TU Wien
+
+ This file is part of CACAO.
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2, or (at
+ your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+
+ $Id: ssa.h$
+
+*/
+
+
+#ifndef _SSA_RENAME_H
+#define _SSA_RENAME_H
+
+#include "vm/jit/optimizing/graph.h"
+
+#if !defined(NDEBUG)
+# include <assert.h>
+#endif
+
+/* function prototypes */
+void ssa_rename_init(jitdata *jd, graphdata *gd);
+void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd);
+
+#endif /* _SSA_RENAME_H */
+
+/*
+ * 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
+ * Emacs will automagically detect them.
+ * ---------------------------------------------------------------------
+ * Local variables:
+ * mode: c
+ * indent-tabs-mode: t
+ * c-basic-offset): 4
+ * tab-width): 4
+ * End:
+ * vim:noexpandtab:sw=4:ts=4:
+ */
printf("\n");
+ if (irstage >= SHOW_CFG) {
+ printf("succs: %d [ ", bptr->successorcount);
+
+ for (i = 0; i < bptr->successorcount; i++)
+ printf("%d ", bptr->successors[i]->nr);
+
+ printf("]\n");
+ }
+
if (irstage >= SHOW_STACK) {
printf("IN: ");
show_variable_array(jd, bptr->invars, bptr->indepth, irstage);
#if defined(ENABLE_IFCONV)
{ "ifconv", false, OPT_IFCONV },
#endif
-#if defined(ENABLE_LSRA) || defined(ENABLE_SSA)
+#if defined(ENABLE_LSRA)
{ "lsra", false, OPT_LSRA },
#endif
+#if defined(ENABLE_SSA)
+ { "lsra", true, OPT_LSRA },
+#endif
#if defined(ENABLE_INTRP)
/* interpreter options */
puts(" -lsra use linear scan register allocation");
#endif
#if defined(ENABLE_SSA)
- puts(" -lsra use linear scan register allocation (with SSA)");
+ puts(" -lsra:... use linear scan register allocation (with SSA)");
+ puts(" (d)ead code elimination");
+ puts(" (c)opy propagation");
#endif
#if defined(ENABLE_DEBUG_FILTER)
puts(" -XXfi <regex> begin of dynamic scope for verbosecall filter");
break;
#endif
-#if defined(ENABLE_LSRA) || defined(ENABLE_SSA)
+#if defined(ENABLE_LSRA)
+ case OPT_LSRA:
+ opt_lsra = true;
+ break;
+#endif
+#if defined(ENABLE_SSA)
case OPT_LSRA:
opt_lsra = true;
+ for (i = 0; i < strlen(opt_arg); i++) {
+ switch (opt_arg[i]) {
+ case 'c':
+ opt_ssa_cp = true;
+ break;
+
+ case 'd':
+ opt_ssa_dce = true;
+ break;
+
+ case ':':
+ break;
+
+ default:
+ usage();
+ }
+ }
break;
#endif
#if defined(ENABLE_LSRA) || defined(ENABLE_SSA)
bool opt_lsra = false;
#endif
+#if defined(ENABLE_SSA)
+bool opt_ssa_dce = false; /* enable dead code elemination */
+bool opt_ssa_cp = false; /* enable copy propagation */
+#endif
/* interpreter options ********************************************************/
#if defined(ENABLE_LSRA) || defined(ENABLE_SSA)
extern bool opt_lsra;
#endif
-
+#if defined(ENABLE_SSA)
+extern bool opt_ssa_dce; /* enable dead code elemination */
+extern bool opt_ssa_cp; /* enable copy propagation */
+#endif
/* interpreter options ********************************************************/
projects / cacao.git / commitdiff