/* src/vm/jit/optimizing/ssa.c - static single-assignment form
- 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
+ Copyright (C) 2005, 2006, 2007, 2008
+ CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
This file is part of CACAO.
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.
- Contact: cacao@complang.tuwien.ac.at
+*/
- Authors: Christian Ullrich
+#include "config.h"
-*/
#include <stdio.h>
#include <stdlib.h>
-#include "mm/memory.h"
+#include "mm/memory.hpp"
#include "toolbox/bitvector.h"
#include "toolbox/worklist.h"
-#include "vm/builtin.h"
+#include "vm/jit/builtin.hpp"
-#include "vm/jit/jit.h" /* icmd_table */
+#include "vm/jit/jit.hpp" /* icmd_table */
-#include "vm/jit/optimizing/dominators.h"
+#include "vm/jit/ir/bytecode.h"
+
+#include "vm/jit/optimizing/dominators.hpp"
#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"
+#include "vm/jit/optimizing/ssa_phi.h"
+
+#include "vm/jit/python.h"
#if defined(SSA_DEBUG_VERBOSE)
-#include "vmcore/options.h" /* compileverbose */
+#include "vm/options.h" /* compileverbose */
#endif
/* function prototypes */
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 xssa(jitdata *jd);
+void yssa(jitdata *jd);
+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
+
+ cfg_add_root(jd);
+ cfg_add_exceptional_edges(jd);
+ /*pythonpass_run(jd, "foo", "cfg_print");*/
+ /*dominator_tree_validate(jd, dd);*/
+ /*pythonpass_run(jd, "ssa2", "main");*/
+ /*pythonpass_run(jd, "alt_ssa", "main");*/
+ /*pythonpass_run(jd, "foo", "before");*/
+
+ /*if (getenv("XSSA")) {
+ dominator_tree_build(jd);
+ dominance_frontier_build(jd);
+ xssa(jd);
+ } else */{
+ yssa(jd);
+ }
+ /*pythonpass_run(jd, "foo", "after");*/
+ cfg_remove_root(jd);
+ return;
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
{
if ((in[in_d] != out[out_d]) ||
(VAR(in[in_d])->flags != VAR(out[out_d])->flags)) {
printf("Method: %s %s\n",
- m->class->name->text, m->name->text);
+ m->clazz->name->text, m->name->text);
printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
if (compileverbose)
printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
#endif
-
#ifdef SSA_DEBUG_VERBOSE
if (compileverbose)
ssa_print_trees(jd, gd, dd);
#endif
+
}
/* ssa_init *******************************************************************
#if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE)
# if defined(SSA_DEBUG_VERBOSE)
if (compileverbose) {
- printf("%s %s ",m->class->name->text, m->name->text);
- if (jd->isleafmethod)
+ printf("%s %s ",m->clazz->name->text, m->name->text);
+ if (code_is_leafmethod(jd->code))
printf("**Leafmethod**");
printf("\n");
}
# endif
- if (strcmp(m->class->name->text,"spec/benchmarks/_213_javac/Parser")==0)
+ if (strcmp(m->clazz->name->text,"spec/benchmarks/_213_javac/Parser")==0)
if (strcmp(m->name->text,"parseTerm")==0)
# if defined(SSA_DEBUG_VERBOSE)
if (compileverbose)
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 (jd->isleafmethod)
- printf("**Leafmethod**");
- printf("\n");
- }
-# endif
- if (strcmp(jd->m->class->name->text,"fp")==0)
- if (strcmp(jd->m->name->text,"testfloat")==0)
-# if defined(SSA_DEBUG_VERBOSE)
- if (compileverbose)
- printf("12-------------------12\n");
-# else
- { int dummy=1; dummy++; }
-# endif
-#endif
- /* recreate rd->locals[][] */
- /* now only one (local_index/type) pair exists anymore */
- /* all var[t][i] with var_to_index[var[t][i]] >= 0 are locals */
- /* max local index after SSA indexing is in ls->local_0[ls->max_locals] */
-
- new_vars = DMNEW(varinfo, ls->vartop);
- for(i = 0; i < ls->vartop ; i++)
- new_vars[i].type = UNUSED;
- for(i = 0; i < jd->varcount; i++) {
- p = ls->new_varindex[i];
- if (p != UNUSED) {
- if (p < ls->ssavarcount)
- p = ls->var_0[p];
- new_vars[p].type = VAR(i)->type;
- new_vars[p].flags = VAR(i)->flags;
- ls->lifetime[p].v_index = p;
- ls->lifetime[p].type = VAR(i)->type;
- }
- }
-
- /* take care of newly indexed local & in/out vars */
-
- for(i = 0; i < ls->ssavarcount; i++) {
- j = ls->var_0[i];
- type = new_vars[j].type;
- flags = new_vars[j].flags;
- j++;
- for (; j < ls->var_0[i + 1]; j++) {
- new_vars[j].type = type;
- new_vars[j].flags = flags;
- ls->lifetime[j].v_index = j;
- ls->lifetime[j].type = type;
- }
- }
-
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
-
- printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
- ls->ssavarcount);
- for(i = 0; i < jd->varcount; i++) {
- printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
- ssa_show_variable(jd, i, VAR(i),0);
- j = ls->new_varindex[i];
- if ((j != UNUSED) && (j < ls->ssavarcount))
- printf(" -> %3i ... %3i", ls->var_0[j], ls->var_0[j + 1] - 1);
- else
- printf(" -> %3i", j);
- printf("\n");
- }
- }
-#endif
-
- jd->var = new_vars;
- jd->varcount = ls->vartop;
- jd->vartop = ls->vartop;
-
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
- ls->ssavarcount);
- for(i = 0; i < jd->varcount; i++) {
- printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
- ssa_show_variable(jd, i, VAR(i),0);
- printf("\n");
- }
- }
-#endif
-}
-
-/* ssa_rename_init *************************************************************
-
-Setup the data structure for ssa_rename
-
-ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
-ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
- definition of each old var.
-ls->varcount_with_indices will be se to the new maximum varcount of LOCAL
- and IOVARS.
-
-All other vars (TEMPVAR and PREALLOC) will get a new unique index above
-ls->varcount_with_indices.
-
-jd->var and jd->varcount will be set for this renamed vars.
-
-*******************************************************************************/
-
-void ssa_rename_init(jitdata *jd, graphdata *gd)
-{
- int a, i, p;
- lsradata *ls;
-
- ls = jd->ls;
-
- /* set up new locals */
- /* ls->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,
+ bytecode[iptr->opc].mnemonic);
+ }
+#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,
+ bytecode[iptr->opc].mnemonic);
+ }
+#endif
}
if (remove_statement) {
#ifdef SSA_DEBUG_VERBOSE
if (compileverbose)
- printf("INFO: %s %s:at BB %3i II %3i NOP-<%s\n",
- m->class->name->text, m->name->text,
+ printf("dce: %s %s:at BB %3i II %3i NOP-<%s\n",
+ m->clazz->name->text, m->name->text,
lt->def->b_index, lt->def->iindex,
icmd_table[iptr->opc].name);
#endif
/* 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, bytecode[iptr->opc].mnemonic,
+ 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");
}
}
projects / cacao.git / blobdiff