/* src/vm/jit/optimizing/ssa.c - static single-assignment form Copyright (C) 2005, 2006, 2007, 2008 CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO 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. */ #include "config.h" #include #include #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/ir/bytecode.h" #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" #include "vm/jit/optimizing/ssa_phi.h" #include "vm/jit/python.h" #if defined(SSA_DEBUG_VERBOSE) #include "vm/options.h" /* compileverbose */ #endif /* function prototypes */ void ssa_set_local_def(lsradata *, int , int); void ssa_set_interface(jitdata *, basicblock *, s4 *); void dead_code_elimination(jitdata *jd, graphdata *gd); void copy_propagation(jitdata *jd, graphdata *gd); void ssa_replace_use_sites(jitdata *, graphdata *, struct lifetime *, int , worklist *); void ssa_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 *); #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 ************************************************************************ 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 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_place_phi_functions(jd, gd, dd); ssa_rename(jd, gd, dd); #ifdef SSA_DEBUG_VERBOSE if (compileverbose) { printf("Phi before Cleanup\n"); ssa_print_phi(ls, gd); ssa_print_lt(ls); } #endif lt_scanlifetimes(jd, gd, dd); #ifdef SSA_DEBUG_VERBOSE if (compileverbose) { ssa_print_lt(ls); } #endif 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); } #endif } 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 { int i, j, pred, in_d, out_d; graphiterator iter_pred; s4 *in, *out; bool phi_define; methodinfo *m; m = jd->m; for(i = 0; i < ls->basicblockcount; i++) { if (ls->basicblocks[i]->indepth != 0) { pred = graph_get_first_predecessor(gd, i, &iter_pred); for (; (pred != -1); pred = graph_get_next(&iter_pred)) { in_d = ls->basicblocks[i]->indepth - 1; in = ls->basicblocks[i]->invars; for (; in_d >= 0; in_d--) { phi_define = false; for (j = 0; (!phi_define) && (jssavarcount); j++) { if (ls->phi[i][j] != NULL) if (ls->phi[i][j][0] == in[in_d]) phi_define = true; } if (!phi_define) { /* in not defined in phi function -> check with */ /* outstack(s) of predecessor(s) */ out_d = ls->basicblocks[pred]->outdepth - 1; out = ls->basicblocks[pred]->outvars; _SSA_ASSERT(out_d >= in_d); for(; out_d > in_d; out_d--); if ((in[in_d] != out[out_d]) || (VAR(in[in_d])->flags != VAR(out[out_d])->flags)) { printf("Method: %s %s\n", m->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); /* else */ /* _SSA_ASSERT(0); */ } } } } } } } #endif #ifdef SSA_DEBUG_VERBOSE if (compileverbose) ssa_print_trees(jd, gd, dd); #endif } /* ssa_init ******************************************************************* Initialise data structures for ssa IOVARS of same stackdepth and same type are coalesced: interface_map[ 5 * stackdepth + type ] = new_varindex with 0 <= new_varindex < ls->ssavarcount TODO: check if coalescing of IOVARS of same stackdepth and type only of adjacent basic blocks could decrease the number of phi functions and so improve ssa analysis performance! All LOCALVARS and IOVARS get a new unique varindex: ls->new_varindex[0..jd->varcount[ = new_varindex with 0 <= new_varindex < ls->ssavarcount The jd->varcount bits long bitvectors ls->var_def[0..jd->basicblockindex+1[ are set to the definitions of LOCALVARS and IOVARS. (So the only the first ls->ssavarcount bits of each of these vectors contain valid data, but ls->ssavarcount is computed at the same time as the definitons are stored.) The basic block number used as index for the bitvector array ls->var_def is already shifted by one to make space for the new basic block 0 for parameter initialization. ******************************************************************************/ void ssa_init(jitdata *jd) { int p, t, v; methoddesc *md; int i, l, b_index, len; instruction *iptr; basicblock *bptr; s4 *interface_map; /* holds an new unique index for every used */ /* basic block inoutvar described by a dupel */ /*(depth,type). Used to coalesce the inoutvars*/ methodinfo *m; lsradata *ls; builtintable_entry *bte; ls = jd->ls; m = jd->m; md = m->parseddesc; #if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE) # if defined(SSA_DEBUG_VERBOSE) if (compileverbose) { printf("%s %s ",m->clazz->name->text, m->name->text); if (code_is_leafmethod(jd->code)) printf("**Leafmethod**"); printf("\n"); } # endif 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) printf("12-------------------12\n"); # else { int dummy=1; dummy++; } # endif #endif #ifdef SSA_DEBUG_VERBOSE if (compileverbose) printf("ssa_init: basicblockcount %3i localcount %3i\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->num_defs = DMNEW(int, jd->varcount); ls->new_varindex = DMNEW(int , jd->varcount); for(p = 0; p < jd->varcount; p++) { ls->num_defs[p] = 0; ls->new_varindex[p] = UNUSED; } /* init Var Definition bitvectors */ ls->var_def = DMNEW(int *, jd->basicblockcount + 1); for(i = 0; i < jd->basicblockcount + 1; i++) { ls->var_def[i] = bv_new(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 ed to start at block 1 */ /* don't look at already eliminated (not used) parameters (locals) */ for (p = 0, l = 0; p < md->paramcount; p++) { t = md->paramtypes[p].type; i = jd->local_map[l * 5 + t]; l++; if (IS_2_WORD_TYPE(t)) /* increment local counter a second time */ l++; /* for 2 word types */ if (i == UNUSED) continue; ssa_set_local_def(ls, -1, i); } _SSA_ASSERT(ls->ssavarcount < jd->varcount); /* coalesce bb in/out vars */ interface_map = DMNEW(s4, jd->stackcount * 5); for(i = 0; i < jd->stackcount * 5; i++) interface_map[i] = UNUSED; bptr = jd->basicblocks; for(; bptr != NULL; bptr = bptr->next) { #ifdef SSA_DEBUG_VERBOSE if (compileverbose) printf("ssa_init: BB %3i flags %3x\n",bptr->nr, bptr->flags); #endif if (bptr->flags >= BBREACHED) { /* 'valid' Basic Block */ b_index = bptr->nr; len = bptr->icount; iptr = bptr->iinstr; ssa_set_interface(jd, bptr, interface_map); /* !!!!!!!!! not true for now !!!!!!!!! */ /* All baseline optimizations from stack.c are turned off for */ /* SSA! */ for (; len > 0; len--, iptr++) { /* 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) { if (( v < jd->localcount) || ( VAR(v)->flags & INOUT )) { /* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */ 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++) { if ((i < jd->localcount) || ( VAR(i)->flags & INOUT)) { printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags); ssa_show_variable(jd, i, VAR(i),0); if (i < ls->ssavarcount) { printf(" -> %3i", ls->new_varindex[i]); } printf("\n"); } } } #endif } /* ssa_set_def **************************************************************** Helper for ssa_set_local_def and ssa_set_interface The definition of a var is stored in the bitvector array ls->var_def. The number of definitons of each var is counted, so the number of new vars with SSA is known. ******************************************************************************/ void ssa_set_def(lsradata *ls, int b_index, int varindex) { /* b_index + 1 to leave space for the param init block 0 */ bv_set_bit(ls->var_def[b_index + 1], varindex); /* count number of defs for every var since SSA */ /* will create a new var for every definition */ ls->num_defs[varindex]++; } /* ssa_set_local_def ********************************************************** Helper for ssa_init Assigns a new unique index for the local var varindex (if not already done so) and then calls ssa_set_def to remember the definition in the bitvector array ls->var_def ******************************************************************************/ void ssa_set_local_def(lsradata *ls, int b_index, int varindex) { if (ls->new_varindex[varindex] == UNUSED) { ls->new_varindex[varindex] = ls->ssavarcount++; } ssa_set_def(ls, b_index, ls->new_varindex[varindex]); } /* ssa_set_local_def ********************************************************** Helper for ssa_set_interface IN: ls pointer to lsradata structure iovar varindex of INOUTVAR to process map_index stackdepth * 5 + type, used for coalescing IOVARS. IN/OUT interface_map used for coalescing IOVARS. interface_map[map_index] == UNUSED, if this map_index (==stackdepth,type tupel) did not occur till now. Then interface_map[map_index] will be set to a new unique index. ls->new_varindex will be set to this new unique index to map the old varindizes to the new ones. Assigns a new unique index for the local var varindex (if not already done so) and then calls ssa_set_def to remember the definition in the bitvector array ls->var_def ******************************************************************************/ void ssa_set_iovar(lsradata *ls, s4 iovar, int map_index, s4 *interface_map) { if (interface_map[map_index] == UNUSED) interface_map[map_index] = ls->ssavarcount++; ls->new_varindex[iovar] = interface_map[map_index]; } /* ssa_set_interface *********************************************************** Helper for ssa_init IN: ls pointer to lsradata structure *bptr pointer to the basic block to be processed IN/OUT interface_map used for coalescing IOVARS. interface_map[map_index] == UNUSED, if this map_index (==stackdepth,type tupel) did not occur till now. Then interface_map[map_index] will be set to a new unique index. (see ssa_set_iovar) Searches the basic block given by *bptr for IN and OUTVARS and coalesces them for each unique stackdepth,type dupel. For each OUTVAR with a different or no INVAR at the same stackdepth the definition of this OUTVAR in this basic block is remembered in ls->var_def. (see ssa_set_def) ******************************************************************************/ void ssa_set_interface(jitdata *jd, basicblock *bptr, s4 *interface_map) { s4 *out, *in; int in_d, out_d; int o_map_index, i_map_index; lsradata *ls; ls = jd->ls; out = bptr->outvars; in = bptr->invars; in_d = bptr->indepth - 1; out_d = bptr->outdepth - 1; /* ignore top Stackelement of instack in case of EXH or SBR blocks */ /* These are no Interface stackslots! */ if ((bptr->type == BBTYPE_EXH) || (bptr->type == BBTYPE_SBR)) { in_d--; } /* invars with no corresponding outvars are not defined here */ /* just set up the interface_map */ for(;(in_d > out_d); in_d--) { i_map_index = in_d * 5 + VAR(in[in_d])->type; ssa_set_iovar(ls, in[in_d], i_map_index, interface_map); } while((out_d >= 0)) { /* set up interface_map */ o_map_index = out_d * 5 + VAR(out[out_d])->type; if (in_d >= 0) { i_map_index = in_d * 5 + VAR(in[in_d])->type; ssa_set_iovar(ls, in[in_d], i_map_index, interface_map); } ssa_set_iovar(ls, out[out_d], o_map_index, interface_map); if (in_d == out_d) { out_d--; in_d--; } else { out_d--; } } } #ifdef SSA_DEBUG_VERBOSE void ssa_print_trees(jitdata *jd, graphdata *gd, dominatordata *dd) { int i,j; lsradata *ls; ls = jd->ls; printf("ssa_printtrees: maxlocals %3i", jd->localcount); printf("Dominator Tree: \n"); for(i = 0; i < ls->basicblockcount; i++) { printf("%3i:",i); for(j = 0; j < ls->basicblockcount; j++) { if (dd->idom[j] == i) { printf(" %3i", j); } } printf("\n"); } printf("Dominator Forest:\n"); for(i = 0; i < ls->basicblockcount; i++) { printf("%3i:",i); for(j = 0; j < dd->num_DF[i]; j++) { printf(" %3i", dd->DF[i][j]); } printf("\n"); } #if 0 if (ls->ssavarcount > 0) { printf("Use Sites\n"); for(i = 0; i < ls->ssavarcount; i++) { printf("use_sites[%3i]=%p:",i,(void *)ls->use_sites[i]); for(j = 0; j < ls->basicblockcount; j++) { if ((j % 5) == 0) printf(" "); if (bv_get_bit(ls->use_sites[i], j)) printf("1"); else printf("0"); } printf("\n"); } } #endif printf("var Definitions:\n"); for(i = 0; i < jd->basicblockcount; i++) { printf("var_def[%3i]=%p:",i,(void *)ls->var_def[i]); for(j = 0; j < ls->ssavarcount; j++) { if ((j % 5) == 0) printf(" "); if (bv_get_bit(ls->var_def[i], j)) printf("1"); else printf("0"); } printf(" ("); for(j=0; j < ((((ls->ssavarcount * 5+7)/8) + sizeof(int) - 1)/sizeof(int)); j++) printf("%8x",ls->var_def[i][j]); printf(")\n"); } } #endif /**************************************************************************** Optimizations ****************************************************************************/ /**************************************************************************** Dead Code Elimination ****************************************************************************/ void dead_code_elimination(jitdata *jd, graphdata *gd) { int a, i, source; worklist *W; instruction *iptr; struct lifetime *lt, *s_lt; bool remove_statement; struct site *use; lsradata *ls; #ifdef SSA_DEBUG_VERBOSE methodinfo *m; m = jd->m; #endif ls = jd->ls; W = wl_new(ls->lifetimecount); if (ls->lifetimecount > 0) { /* put all lifetimes into Worklist W */ for(a = 0; a < ls->lifetimecount; a++) { 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 == UNUSED)) /* lifetime was already removed -> no defs anymore */ continue; /* 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) { remove_statement = remove_statement && (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 */ _SSA_ASSERT(ls->phi[lt->def->b_index][-lt->def->iindex-1] != 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) && (source != UNUSED)) { /* phi Argument was not already removed (already in because of "selfdefinition") */ s_lt = &(ls->lifetime[source]); /* remove it */ lt_remove_use_site(s_lt,lt->def->b_index, lt->def->iindex); /* put it on the Worklist */ 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 { /* "normal" Use by ICMD */ remove_statement = false; if (lt->def->b_index != 0) { /* do not look at artificial block 0 (parameter init) */ iptr = ls->basicblocks[lt->def->b_index]->iinstr + lt->def->iindex; if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) { /* if ICMD could throw an exception do not remove it! */ 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 } 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) { /* remove statement */ #ifdef SSA_DEBUG_VERBOSE if (compileverbose) 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 iptr->opc = ICMD_NOP; } } /* (lt->def->b_index != 0) */ } /* if (lt->def->iindex < 0 ) else */ /* remove definition of a */ #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 */ /**************************************************************************** Simple Constant Propagation ****************************************************************************/ void simple_constant_propagation() { } /**************************************************************************** Optimization *******************************************************************************/ void copy_propagation(jitdata *jd, graphdata *gd) { int a, i, source; int only_source; worklist *W; instruction *iptr; struct lifetime *lt, *s_lt; lsradata *ls; ls = jd->ls; W = wl_new(ls->lifetimecount); if (ls->lifetimecount > 0) { /* put all lifetimes on Worklist */ for(a = 0; a < ls->lifetimecount; a++) { if (ls->lifetime[a].type != UNUSED) { wl_add(W, a); } } } while(!wl_is_empty(W)) { /* take a var out of Worklist */ a = wl_get(W); lt = ls->lifetime + a; 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 */ /* look, if phi function degenerated to a x = phi(y) */ /* and if so, substitute y for every use of x */ _SSA_ASSERT(ls->phi[lt->def->b_index][-lt->def->iindex-1] != NULL); only_source = ls->varcount_with_indices; for (i = 1; i <= graph_get_num_predecessor(gd, lt->def->b_index); i++) { source = ls->phi[lt->def->b_index][-lt->def->iindex-1][i]; if ((source != ls->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 */ ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL; /* remove this deleted use site of s_lt */ 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); /* 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 ) */ /* def in argument passing - no propagation possible */ /* (there is no ICMD for this... */ if (lt->def->b_index == 0) continue; /* def in "normal" ICMD */ iptr = ls->basicblocks[lt->def->b_index]->iinstr + lt->def->iindex; switch(iptr->opc) { case ICMD_ISTORE: case ICMD_LSTORE: case ICMD_FSTORE: case ICMD_DSTORE: case ICMD_ASTORE: 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 %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 + iptr->s1.varindex; _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); /* this ICMD is not a PEI -> so no danger in deleting it! */ /* delete def of lt (ICMD_NOP) */ /* lt->def->iindex > 0 -> ICMD */ iptr->opc = ICMD_NOP; /* remove this deleted use site of s_lt */ lt_remove_use_site(s_lt, lt->def->b_index, lt->def->iindex); /* invalidate def site of lt */ 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 break; } } /* if (lt->def->iindex < 0 ) */ } /* while(!wl_is_empty(W)) */ } void ssa_replace_use_sites(jitdata *jd, graphdata *gd, struct lifetime *lt, int new_v_index, worklist *W) { struct site *s; int i, source; instruction *iptr; s4 *argp; methoddesc *md; builtintable_entry *bte; lsradata *ls; ls = jd->ls; md = jd->m->parseddesc; for(s = lt->use; s != NULL; s = s->next) { if (s->iindex < 0) { /* Use in phi function */ for (i = 1;i <= graph_get_num_predecessor(gd, s->b_index); i++) { source = ls->phi[s->b_index][-s->iindex-1][i]; 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, -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; } } } if (W != NULL) { /* Add var, which is defined by this phi function to */ /* the worklist */ source = ls->phi[s->b_index][-s->iindex-1][0]; wl_add(W, source); } } else { /* use in ICMD */ iptr = ls->basicblocks[s->b_index]->iinstr + s->iindex; /* check for use (s1, s2, s3 or special (argp) ) */ i = UNUSED; switch (icmd_table[iptr->opc].dataflow) { case DF_3_TO_0: case DF_3_TO_1: /* icmd has s1, s2 and s3 */ if (iptr->sx.s23.s3.varindex == lt->v_index) { #ifdef SSA_DEBUG_VERBOSE if (W != NULL) { if (compileverbose) printf("copy propagation loc3: BB %3i I %3i: %3i -> \ %3i\n", s->b_index, s->iindex, new_v_index, iptr->sx.s23.s3.varindex); } #endif iptr->sx.s23.s3.varindex = new_v_index; } /* now "fall through" for handling of s2 and s1 */ case DF_2_TO_0: case DF_2_TO_1: /* icmd has s1 and s2 */ if (iptr->sx.s23.s2.varindex == lt->v_index) { #ifdef SSA_DEBUG_VERBOSE if (W != NULL) { if (compileverbose) printf("copy propagation loc2: BB %3i I %3i: %3i -> \ %3i\n", s->b_index, s->iindex, new_v_index, iptr->sx.s23.s2.varindex); } #endif iptr->sx.s23.s2.varindex = new_v_index; } /* now "fall through" for handling of s1 */ case DF_1_TO_0: case DF_1_TO_1: case DF_MOVE: case DF_COPY: if (iptr->s1.varindex == lt->v_index) { #ifdef SSA_DEBUG_VERBOSE if (W != NULL) { if (compileverbose) 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; } break; /* TODO: */ /* ? really look at md->paramcount or iptr->s1.argcount */ /* has to be taken, so that pass-through stackslots get */ /* renamed, too? */ case DF_INVOKE: INSTRUCTION_GET_METHODDESC(iptr,md); i = md->paramcount; break; case DF_BUILTIN: bte = iptr->sx.s23.s3.bte; md = bte->md; i = md->paramcount; break; case DF_N_TO_1: i = iptr->s1.argcount; break; } if (i != UNUSED) { argp = iptr->sx.s23.s2.args; while (--i >= 0) { if (*argp == lt->v_index) { #ifdef SSA_DEBUG_VERBOSE if (W != NULL) { if (compileverbose) printf( "copy propagation locN: BB %3i I %3i: %3i -> %3i\n" , s->b_index, s->iindex, new_v_index, *argp); } #endif *argp = new_v_index; } argp++; } } } /* if (s->iindex < 0) */ } /* for(s = lt->use; s != NULL; s = s->next) */ } #ifdef SSA_DEBUG_VERBOSE void ssa_print_lt(lsradata *ls) { int i; struct lifetime *lt; printf("SSA LT Def/Use\n"); for(i = 0; i < ls->lifetimecount; i++) { lt = ls->lifetime + i; _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"); } } void ssa_show_variable(jitdata *jd, int index, varinfo *v, int stage) { char type; char kind; switch (v->type) { case TYPE_INT: type = 'i'; break; case TYPE_LNG: type = 'l'; break; case TYPE_FLT: type = 'f'; break; case TYPE_DBL: type = 'd'; break; case TYPE_ADR: type = 'a'; break; case TYPE_RET: type = 'r'; break; default: type = '?'; } if (index < jd->localcount) { kind = 'L'; if (v->flags & (PREALLOC | INOUT)) printf(""); } else { if (v->flags & PREALLOC) { kind = 'A'; if (v->flags & INOUT) printf(""); } else if (v->flags & INOUT) kind = 'I'; else kind = 'T'; } printf("%c%c%3d", kind, type, index); if (v->flags & SAVEDVAR) putchar('!'); putchar(' '); fflush(stdout); } #endif /**************************************************************************** Optimization ****************************************************************************/ /* * 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: */