Polaris: optimize_ssa.cc Source File

optimize_ssa.cc Go to the documentation of this file. /// #include <set> #include <map> #include "Expression/FunctionCallExpr.h" #include "Expression/IDExpr.h" #include "Evolution/eg_utils.h" #include "Program.h" #include "trans_util.h" #include "optimize_ssa.h" #include "ip_ssa.h" /*! \brief Returns 1 iff 'ex' is a BETA function call. */ int is_beta(Expression& ex){ if (ex.op()!=FUNCTION_CALL_OP) return 0; String fname=ex.function().symbol().name_ref(); if (fname=="<BETA>") return 1; return 0; } /// /// has_maymod /// Return true if the given statement has a maymod assertion. int has_maymod(const Statement &stmt){ Iterator<Assertion> asrt_iter = stmt.assertions(); for ( ; asrt_iter.valid(); ++asrt_iter) if (asrt_iter.current().type() == AS_MAYMOD) return 1; return 0; } /// is_var_in_maymod /// Return true if the given int is_var_in_maymod(const Symbol &var, const Statement &stmt){ Iterator<Assertion> asrt_iter = stmt.assertions(); for ( ; asrt_iter.valid(); ++asrt_iter) if (asrt_iter.current().type() == AS_MAYMOD) { Iterator<Expression> aexpr_iter = asrt_iter.current().arg_list_guarded(); for ( ; aexpr_iter.valid(); ++aexpr_iter) if (aexpr_iter.current().base_variable_ref() == &var) return 1; } return 0; } void gsa_details(const char* gsaname, String& basename, int& rank){ rank=0; basename=""; String gsa=gsaname; int at_sign=gsa.index("@"); if (at_sign!=-1) { new (&basename) String(gsa, 0, at_sign-1); String srank(gsa, at_sign+1, gsa.len()-1); if (srank.len()>0){ istrstream str(srank); str>>rank; } } else { basename=gsaname; rank=0; } } inline void gsa_details(Symbol& sym, String& basename, int& rank){ gsa_details(sym.name_ref(), basename, rank); } /// Returns the name of the gsa symbol with same base name but rank-=1 as 'gsasym' void prev_gsa_rank_name(Symbol& gsasym, String& name){ String base_name; int rank; gsa_details(gsasym.name_ref(), base_name, rank); ostrstream str; str<<rank-1<<'\0'; name=base_name+"@"+str.str(); str.freeze(0); } static void fix_substituted(Expression& expr, Symbol& n, Symbol& s){ if (expr.op()==ID_OP){ IDExpr& idexpr=(IDExpr&)expr; if (idexpr.substituted_valid()){ substitute_var(idexpr.substituted_guarded(), n, s); } } else { Iterator<Expression> expit=expr.arg_list(); for ( expit.reset() ; expit.valid(); ++expit){ fix_substituted(expit.current(), n, s); } } } /// Adjusts gmap to reflect symbol remapping as given by 'final' static void adjust_gmap(ProgramUnit& pgm, Database<String, StringElem>& final_table, bool remove_from_symtab=false){ Database<Statement*, RefDatabase<Symbol*, Symbol> >* lmap= ip_ssa_gmap().find_ref(&pgm); if (!lmap) return; for (KeyIterator<Statement*, RefDatabase<Symbol*, Symbol> > stit=*lmap; stit.valid(); ++stit){ for (KeyIterator<String, StringElem> sit=final_table; sit.valid(); ++sit){ VariableSymbol* vs= (VariableSymbol*)pgm.symtab().find_ref(sit.current_key()); Symbol* base=vs; if (vs->is_gsa_symbol()){ base=&vs->gsa_base_symbol(); } Symbol* mapped=stit.current_data().find_ref(base); /// ... Checked whether old mapped gsa symbol was renamed, and replace it /// ... in case it was. if (mapped==vs){ Symbol* newsym=pgm.symtab().find_ref(sit.current_data()); Symbol* key=&vs->gsa_base_symbol(); if (key!=0){ stit.current_data().del(key); stit.current_data().ins(key, *newsym); } } } } /// Also remove final symbols from symbol table. for (KeyIterator<String, StringElem> sit=final_table; sit.valid(); ++sit){ if (sit.current_key()!=sit.current_data()){ Symbol* found=pgm.symtab().find_ref(sit.current_key()); if (found){ if (found->is_scalar() || found->is_array()){ // Remove from deflocmap. pgm.gsa_deflocs_guarded().remove_invalid_defloc(*found); // Remove from symbol table. if (remove_from_symtab){ pgm.symtab().del(sit.current_key()); } } } } } } /*! \brief Reduces the SSA name count by replacing a@0 with a. */ static bool optimize_ssa_zero(ProgramUnit& pgm){ /// First go through all statements and find all unnecessary MU's. map<String, String> final; Database<String, StringElem> old_style_final; for (DictionaryIter<Symbol> symit=pgm.symtab().iterator(); symit.valid(); ++symit){ Symbol& sym=symit.current(); int rank; String base; gsa_details(sym, base, rank); if (rank==0){ final.insert(make_pair(sym.name_ref(), base)); old_style_final.ins(sym.name_ref(), new StringElem(base)); } } /// For all statements Iterator<Statement> stit; for (stit=pgm.stmts().iterator(); stit.valid(); ++stit){ Statement& stmt=stit.current(); stmt.build_refs(); /// ... For all symbols accessed in this statement. Mutator<Expression> allrefs=stmt.in_refs(); for ( ; allrefs.valid(); ++allrefs){ Symbol* sym=0; switch(allrefs.current().op()){ case ID_OP: sym=&allrefs.current().symbol(); break; case ARRAY_REF_OP: sym=&allrefs.current().array().symbol(); break; default: continue; } map<String, String>::iterator found=final.find(sym->name_ref()); if (found!=final.end()) { Symbol* first=pgm.symtab().find_ref((*found).second); Mutator<Expression> expmut=stmt.iterate_expressions(); for ( ; expmut.valid(); ++expmut ){ substitute_var(expmut.current(), *sym, *first); } } } allrefs=stmt.out_refs(); for ( ; allrefs.valid(); ++allrefs){ if (allrefs.current().op()!=ID_OP) continue; map<String, String>::iterator found= final.find(allrefs.current().symbol().name_ref()); if (found!=final.end()) { Symbol* first=pgm.symtab().find_ref((*found).second); Iterator<Expression> expmut=stmt.iterate_expressions(); for ( ; expmut.valid(); ++expmut ){ substitute_var(expmut.current(), allrefs.current().symbol(), *first); } } } /// ... Need to update 'substituted' fields map<String, String>::iterator kit=final.begin(); for ( ; kit!=final.end(); ++kit){ const String& key=(*kit).first; String& value=(*kit).second; Symbol* sk=pgm.symtab().find_ref(key); p_assert(sk, "Could not find gsa symbol to replace."); Symbol* sv=pgm.symtab().find_ref(value); p_assert(sv, "Could not find gsa symbol to replace with."); Iterator<Expression> expit=stmt.iterate_expressions(); for (expit=stmt.iterate_expressions(); expit.valid(); ++expit){ fix_substituted(expit.current(), *sk, *sv); } } /// ... Re-build references. stmt.build_refs(); } /// Adjust gmap. /// silvius: do not remove them from symtab, otherwise DeGSA will crash. adjust_gmap(pgm, old_style_final, false); return true; } /*! \brief Reduces the SSA name count by removing MU functions where unnecessary. MU functions are unnecessary when of this form: x@5 = MU(x@4, x@5) */ static bool optimize_ssa_mu(ProgramUnit& pgm){ /// First go through all CALL statements and find all unnecessary MU's. bool global_change=false; RefList<Symbol> unnecessary_syms; RefSet<Statement> unnecessary_mu; Iterator<Statement> stit; Database<String, StringElem> final; for (stit=pgm.stmts().iterator(); stit.valid(); ++stit){ /// ... Skip all statements except for CALL and x = func() Statement& stmt=stit.current(); if (stmt.stmt_class()!=ASSIGNMENT_STMT) continue; Expression& rhs=stmt.rhs(); if (rhs.op()!=MU_OP) continue; /// ... It is a MU statement Expression& lhs=stmt.lhs(); Expression& first=rhs.parameters_guarded().arg_list()[0]; Expression& second=rhs.parameters_guarded().arg_list()[1]; if (first.op()!=ID_OP || second.op()!=ID_OP) continue; int rank1, rank2, rank; String base1, base2, base; gsa_details(lhs.symbol(), base, rank); gsa_details(first.symbol(), base1, rank1); gsa_details(second.symbol(), base2, rank2); if (rank==rank2){ final.ins(lhs.symbol().name_ref(), new StringElem(first.symbol().name_ref())); unnecessary_mu.ins(stmt); unnecessary_syms.ins_last(lhs.symbol()); global_change=true; } } /// Remove unnecessary statements. pgm.stmts().del(unnecessary_mu); /// Replace the symbols that have been removed. /// It may happen that a@6 is to be replaced with a@5, but a@5 is to /// be replaced with a@4. We must first find for every symbol which is /// the final symbol to be replaced with (thus we avoid iterating over the /// whole replacing procedure, and do it beforehand). if (final.entries()==0) return false; /// ... made no change. /// Iterate until no change. int change; do { change=0; KeyIterator<String, StringElem> kit=final; for ( ; kit.valid(); ++kit){ StringElem& value=kit.current_data(); /// ... Look for transitivity. StringElem* found=final.find_ref(value); if (found){ change=1; value=*found; } } } while (change); /// At this time, the map should have converged. /// For all statements for (stit=pgm.stmts().iterator(); stit.valid(); ++stit){ Statement& stmt=stit.current(); stmt.build_refs(); /// ... For all symbols accessed in this statement. Mutator<Expression> allrefs=stmt.in_refs(); for ( ; allrefs.valid(); ++allrefs){ if (allrefs.current().op()!=ID_OP && allrefs.current().op()!=ARRAY_REF_OP) continue; StringElem* found; if (allrefs.current().op()==ID_OP){ found=final.find_ref(allrefs.current().symbol().name_ref()); } else { found=final.find_ref(allrefs.current().array().symbol().name_ref()); } if (found) { Symbol* first=pgm.symtab().find_ref(*found); Mutator<Expression> expmut=stmt.iterate_expressions(); for ( ; expmut.valid(); ++expmut ){ if (allrefs.current().op()==ID_OP){ substitute_var(expmut.current(), allrefs.current().symbol(), *first); } else { substitute_var(expmut.current(), allrefs.current().array().symbol(), *first); } } } } allrefs=stmt.out_refs(); for ( ; allrefs.valid(); ++allrefs){ if (allrefs.current().op()!=ID_OP) continue; StringElem* found=final.find_ref(allrefs.current().symbol().name_ref()); if (found) { Symbol* first=pgm.symtab().find_ref(*found); Iterator<Expression> expmut=stmt.iterate_expressions(); for ( ; expmut.valid(); ++expmut ){ substitute_var(expmut.current(), allrefs.current().symbol(), *first); } } } /// ... Need to update 'substituted' fields KeyIterator<String, StringElem> kit=final; for ( ; kit.valid(); ++kit){ String& key=kit.current_key(); StringElem& value=kit.current_data(); Symbol* sk=pgm.symtab().find_ref(key); p_assert(sk, "Could not find gsa symbol to replace."); Symbol* sv=pgm.symtab().find_ref(value); p_assert(sv, "Could not find gsa symbol to replace with."); Iterator<Expression> expit=stmt.iterate_expressions(); for (expit=stmt.iterate_expressions(); expit.valid(); ++expit){ fix_substituted(expit.current(), *sk, *sv); } } /// ... Re-build references. stmt.build_refs(); } /// Adjust gmap. adjust_gmap(pgm, final); return true; } /*! \brief Reduces the SSA name count by removing GAMMA functions where unnecessary. GAMMA functions are unnecessary when of this form: x@5 = GAMMA(condition, x@8, x@8) */ static bool optimize_ssa_gamma(ProgramUnit& pgm){ /// First go through all statements and find all unnecessary GAMMA's. bool global_change=false; RefList<Symbol> unnecessary_syms; RefSet<Statement> unnecessary_gamma; Iterator<Statement> stit; Database<String, StringElem> final; for (stit=pgm.stmts().iterator(); stit.valid(); ++stit){ /// ... Skip all statements except for CALL and x = func() Statement& stmt=stit.current(); if (stmt.stmt_class()!=ASSIGNMENT_STMT) continue; Expression& rhs=stmt.rhs(); if (rhs.op()!=GAMMA_OP) continue; /// ... It is a GAMMA statement RefList<Symbol> entries; get_phinode_entries(rhs, entries); p_assert(entries.entries()>0, "Wrong output from 'get_phinode_entries'."); Symbol* usym=&entries[0]; for(Iterator<Symbol> sit=entries; sit.valid(); ++sit){ if (usym!=&sit.current()){ usym=0; break; } } if (usym==0) continue; /// ... It is unnecessary. Expression& lhs=stmt.lhs(); final.ins(lhs.symbol().name_ref(), new StringElem(usym->name_ref())); unnecessary_gamma.ins(stmt); unnecessary_syms.ins_last(lhs.symbol()); global_change=true; } /// Remove unnecessary statements. pgm.stmts().del(unnecessary_gamma); /// Replace the symbols that have been removed. /// It may happen that a@6 is to be replaced with a@5, but a@5 is to /// be replaced with a@4. We must first find for every symbol which is /// the final symbol to be replaced with (thus we avoid iterating over the /// whole replacing procedure, and do it beforehand). if (final.entries()==0) return false; /// ... made no change. /// Iterate until no change. int change; do { change=0; KeyIterator<String, StringElem> kit=final; for ( ; kit.valid(); ++kit){ StringElem& value=kit.current_data(); /// ... Look for transitivity. StringElem* found=final.find_ref(value); if (found){ change=1; value=*found; } } } while (change); /// At this time, the map should have converged. /// For all statements for (stit=pgm.stmts().iterator(); stit.valid(); ++stit){ Statement& stmt=stit.current(); stmt.build_refs(); /// ... For all symbols accessed in this statement. Mutator<Expression> allrefs=stmt.in_refs(); for ( ; allrefs.valid(); ++allrefs){ if (allrefs.current().op()!=ID_OP && allrefs.current().op()!=ARRAY_REF_OP) continue; StringElem* found; if (allrefs.current().op()==ID_OP){ found=final.find_ref(allrefs.current().symbol().name_ref()); } else { found=final.find_ref(allrefs.current().array().symbol().name_ref()); } if (found) { Symbol* first=pgm.symtab().find_ref(*found); Mutator<Expression> expmut=stmt.iterate_expressions(); for ( ; expmut.valid(); ++expmut ){ if (allrefs.current().op()==ID_OP){ substitute_var(expmut.current(), allrefs.current().symbol(), *first); } else { substitute_var(expmut.current(), allrefs.current().array().symbol(), *first); } } } } allrefs=stmt.out_refs(); for ( ; allrefs.valid(); ++allrefs){ if (allrefs.current().op()!=ID_OP) continue; StringElem* found=final.find_ref(allrefs.current().symbol().name_ref()); if (found) { Symbol* first=pgm.symtab().find_ref(*found); Iterator<Expression> expmut=stmt.iterate_expressions(); for ( ; expmut.valid(); ++expmut ){ substitute_var(expmut.current(), allrefs.current().symbol(), *first); } } } /// ... Need to update 'substituted' fields KeyIterator<String, StringElem> kit=final; for ( ; kit.valid(); ++kit){ String& key=kit.current_key(); StringElem& value=kit.current_data(); Symbol* sk=pgm.symtab().find_ref(key); p_assert(sk, "Could not find gsa symbol to replace."); Symbol* sv=pgm.symtab().find_ref(value); p_assert(sv, "Could not find gsa symbol to replace with."); Iterator<Expression> expit=stmt.iterate_expressions(); for (expit=stmt.iterate_expressions(); expit.valid(); ++expit){ fix_substituted(expit.current(), *sk, *sv); } } /// ... Re-build references. stmt.build_refs(); } /// Adjust gmap. adjust_gmap(pgm, final); return true; } /*! \brief Reduces the SSA name count by removing ETA functions where unnecessary. ETA functions are unnecessary when of this form: x@5 = ETA(condition, x@8, x@8) */ static bool optimize_ssa_eta(ProgramUnit& pgm){ /// First go through all statements and find all unnecessary ETA's. bool global_change=false; RefList<Symbol> unnecessary_syms; RefSet<Statement> unnecessary_eta; Iterator<Statement> stit; Database<String, StringElem> final; for (stit=pgm.stmts().iterator(); stit.valid(); ++stit){ /// ... Skip all statements except for CALL and x = func() Statement& stmt=stit.current(); if (stmt.stmt_class()!=ASSIGNMENT_STMT) continue; Expression& rhs=stmt.rhs(); if (rhs.op()!=ETA_OP) continue; /// ... It is a ETA statement Expression& lhs=stmt.lhs(); Expression& first=rhs.parameters_guarded().arg_list()[0]; Expression& second=rhs.parameters_guarded().arg_list()[1]; if (first.op()!=ID_OP || second.op()!=ID_OP) continue; int rank1, rank2, rank; String base1, base2, base; gsa_details(lhs.symbol(), base, rank); gsa_details(first.symbol(), base1, rank1); gsa_details(second.symbol(), base2, rank2); if (rank1==rank2){ final.ins(lhs.symbol().name_ref(), new StringElem(first.symbol().name_ref())); unnecessary_eta.ins(stmt); unnecessary_syms.ins_last(lhs.symbol()); global_change=true; } } /// Remove unnecessary statements. pgm.stmts().del(unnecessary_eta); /// Replace the symbols that have been removed. /// It may happen that a@6 is to be replaced with a@5, but a@5 is to /// be replaced with a@4. We must first find for every symbol which is /// the final symbol to be replaced with (thus we avoid iterating over the /// whole replacing procedure, and do it beforehand). if (final.entries()==0) return false; /// ... made no change. /// Iterate until no change. int change; do { change=0; KeyIterator<String, StringElem> kit=final; for ( ; kit.valid(); ++kit){ StringElem& value=kit.current_data(); /// ... Look for transitivity. StringElem* found=final.find_ref(value); if (found){ change=1; value=*found; } } } while (change); /// At this time, the map should have converged. /// For all statements for (stit=pgm.stmts().iterator(); stit.valid(); ++stit){ Statement& stmt=stit.current(); stmt.build_refs(); /// ... For all symbols accessed in this statement. Mutator<Expression> allrefs=stmt.in_refs(); for ( ; allrefs.valid(); ++allrefs){ if (allrefs.current().op()!=ID_OP && allrefs.current().op()!=ARRAY_REF_OP) continue; StringElem* found; if (allrefs.current().op()==ID_OP){ found=final.find_ref(allrefs.current().symbol().name_ref()); } else { found=final.find_ref(allrefs.current().array().symbol().name_ref()); } if (found) { Symbol* first=pgm.symtab().find_ref(*found); Mutator<Expression> expmut=stmt.iterate_expressions(); for ( ; expmut.valid(); ++expmut ){ if (allrefs.current().op()==ID_OP){ substitute_var(expmut.current(), allrefs.current().symbol(), *first); } else { substitute_var(expmut.current(), allrefs.current().array().symbol(), *first); } } } } allrefs=stmt.out_refs(); for ( ; allrefs.valid(); ++allrefs){ if (allrefs.current().op()!=ID_OP) continue; StringElem* found=final.find_ref(allrefs.current().symbol().name_ref()); if (found) { Symbol* first=pgm.symtab().find_ref(*found); Iterator<Expression> expmut=stmt.iterate_expressions(); for ( ; expmut.valid(); ++expmut ){ substitute_var(expmut.current(), allrefs.current().symbol(), *first); } } } /// ... Need to update 'substituted' fields KeyIterator<String, StringElem> kit=final; for ( ; kit.valid(); ++kit){ String& key=kit.current_key(); StringElem& value=kit.current_data(); Symbol* sk=pgm.symtab().find_ref(key); p_assert(sk, "Could not find gsa symbol to replace."); Symbol* sv=pgm.symtab().find_ref(value); p_assert(sv, "Could not find gsa symbol to replace with."); Iterator<Expression> expit=stmt.iterate_expressions(); for (expit=stmt.iterate_expressions(); expit.valid(); ++expit){ fix_substituted(expit.current(), *sk, *sv); } } /// ... Re-build references. stmt.build_refs(); } /// Adjust gmap. adjust_gmap(pgm, final); return true; } /*! \brief Reduces the SSA name count by removing BETA functions where unnecessary. BETA functions are unnecessary when a routine argument is of type IN, i.e. not modified inside the called routine. It uses the IPCP MAYMOD assertions to check for parameter type. */ static void optimize_ssa_beta(ProgramUnit& pgm){ /// First go through all CALL statements and find all BETA calls. /// For every BETA call, find whether its pre-SSA argument has a MAYMOD /// assertion. If not, put it in 'unnecessary_syms'. RefList<Symbol> unnecessary_syms; RefList<Expression> unnecessary_betas; RefList<Expression> unnecessary_beta_sites; Iterator<Statement> stit; Database<String, StringElem> final; for (stit=pgm.stmts().iterator(); stit.valid(); ++stit){ /// ... Skip all statements except for CALL and x = func() Statement& stmt=stit.current(); Expression* params=0; if (stmt.stmt_class()==CALL_STMT) { params=&stmt.parameters_guarded(); } else { if (stmt.stmt_class()==ASSIGNMENT_STMT){ if (stmt.rhs().op()==FUNCTION_CALL_OP) { if (!is_pseudo_function(stmt.rhs())){ params=&stmt.rhs().parameters_guarded(); } else continue; } else continue; } else continue; } /// ... Check if it has a MAYMOD assertion associated with it. /// ... If not, we cannot do anything about it. if (!has_maymod(stmt)) continue; /// ... If we got here, 'params' points to the list of arguments. if (params->op()==OMEGA_OP) continue; for (Iterator<Expression> expit=params->arg_list(); expit.valid(); ++expit){ Expression& arg=expit.current(); if (!is_beta(arg)) continue; /// ... Get its base symbol. Symbol* oldvalue; Expression* last_arg=arg.parameters_guarded().arg_list().last_ref(); Expression* first_arg=arg.parameters_guarded().arg_list().first_ref(); Expression* alpha_arg= first_arg->parameters_guarded().arg_list().first_ref(); /// cerr<<"\nlast_arg= "<<*last_arg<<" = "<<*first_arg /// <<" = "<<*alpha_arg; Symbol* basesym; VariableSymbol* varsym; if (last_arg->op()==ARRAY_REF_OP){ varsym=(VariableSymbol*)&last_arg->array().symbol(); basesym=varsym; if (varsym->is_gsa_symbol()) basesym=&varsym->gsa_base_symbol(); oldvalue=&alpha_arg->array().symbol(); } else { varsym=(VariableSymbol*)&last_arg->symbol(); basesym=varsym; if (varsym->is_gsa_symbol()) basesym=&varsym->gsa_base_symbol(); oldvalue=&alpha_arg->symbol(); } /// ... Check if it has a MAYMOD assertion associated with this particular sym. if (!is_var_in_maymod(*basesym, stmt)){ unnecessary_syms.ins_last(*varsym); unnecessary_betas.ins_last(arg); unnecessary_beta_sites.ins_last(*params); final.ins(varsym->name_ref(), new StringElem(oldvalue->name_ref())); } } } /// The second step consists of replacing all symbols in 'unnecessary' /// with their ssa-base-equivalent symbol of previous rank: /// (such as a@7 will be replaced by a@6). /// Also, the BETA call where this happens will be replaced by a simple /// variable expression. /// cerr<<"\n final: "<<final; /// Start removing BETA calls. Iterator<Expression> beta_site=unnecessary_beta_sites; Iterator<Expression> beta=unnecessary_betas; Iterator<Symbol> sym=unnecessary_syms; for ( ; beta_site.valid() && beta.valid() && sym.valid(); ++beta_site, ++beta, ++sym){ List<Expression>& exlist=beta_site.current().arg_list(); Expression& ex=beta.current(); Symbol* newsym=0; String bname; int rank; gsa_details(sym.current(), bname, rank); if (rank==0){ /// ... Do nothing, this is a CALL p(1) type of statement. /// ... Gets transformed into arg=1; CALL p(BETA(ALPHA(arg), arg)) newsym=&sym.current(); } else { String prevgsa; prev_gsa_rank_name(sym.current(), prevgsa); newsym=pgm.symtab().find_ref(prevgsa); if (newsym==0){ cerr<<"\nCould not find previous GSA rank for this symbol: " <<sym.current(); cerr<<"\nBeta: "<<ex; cerr<<"\nBeta site: "<<beta_site.current(); p_abort(""); } } FunctionCallExpr& func=(FunctionCallExpr&)ex; Expression* first_arg=func.parameters_guarded().arg_list().first_ref(); /// ... first_arg points now to ALPHA. first_arg=first_arg->parameters_guarded().arg_list().first_ref(); Expression* newex=first_arg->clone(); Expression* grabbed=0; if (newex->op()==ID_OP){ if (newex->substituted_valid()){ grabbed=first_arg->grab_substituted(); } } substitute_var(*newex, sym.current(), *newsym); if (newex->op()==ID_OP){ if (newex->substituted_valid()){ newex->substituted(grabbed); } } exlist.modify(ex, newex); } /// Replace the symbols that have been removed. /// It may happen that a@6 is to be replaced with a@5, but a@5 is to /// be replaced with a@4. We must first find for every symbol which is /// the final symbol to be replaced with (thus we avoid iterating over the /// whole replacing procedure, and do it beforehand). /// cerr<<"\n final: "<<final; /// Iterate until no change. int change; do { change=0; KeyIterator<String, StringElem> kit=final; for ( ; kit.valid(); ++kit){ StringElem& value=kit.current_data(); /// ... Look for transitivity. StringElem* found=final.find_ref(value); if (found==&value) continue; if (found){ change=1; value=*found; } } } while (change); /// cerr<<"\n final: "<<final; /// At this time, the map should have converged. /// For all statements for (stit=pgm.stmts().iterator(); stit.valid(); ++stit){ Statement& stmt=stit.current(); stmt.build_refs(); /// ... For all symbols accessed in this statement. Mutator<Expression> allrefs=stmt.in_refs(); for ( ; allrefs.valid(); ++allrefs){ if (allrefs.current().op()!=ID_OP && allrefs.current().op()!=ARRAY_REF_OP) continue; StringElem* found; if (allrefs.current().op()==ID_OP){ found=final.find_ref(allrefs.current().symbol().name_ref()); } else { found=final.find_ref(allrefs.current().array().symbol().name_ref()); } if (found) { Symbol* first=pgm.symtab().find_ref(*found); Mutator<Expression> expmut=stmt.iterate_expressions(); for ( ; expmut.valid(); ++expmut ){ if (allrefs.current().op()==ID_OP){ substitute_var(expmut.current(), allrefs.current().symbol(), *first); } else { substitute_var(expmut.current(), allrefs.current().array().symbol(), *first); } } } } allrefs=stmt.out_refs(); for ( ; allrefs.valid(); ++allrefs){ if (allrefs.current().op()!=ID_OP) continue; StringElem* found=final.find_ref(allrefs.current().symbol().name_ref()); if (found) { Symbol* first=pgm.symtab().find_ref(*found); Iterator<Expression> expmut=stmt.iterate_expressions(); for ( ; expmut.valid(); ++expmut ){ substitute_var(expmut.current(), allrefs.current().symbol(), *first); } } } /// ... Need to update 'substituted' fields /// cerr<<"\n final: "<<final; KeyIterator<String, StringElem> kit=final; for ( ; kit.valid(); ++kit){ String& key=kit.current_key(); StringElem& value=kit.current_data(); Symbol* sk=pgm.symtab().find_ref(key); p_assert(sk, "Could not find gsa symbol to replace."); Symbol* sv=pgm.symtab().find_ref(value); p_assert(sv, "Could not find gsa symbol to replace with."); Iterator<Expression> expit=stmt.iterate_expressions(); for (expit=stmt.iterate_expressions(); expit.valid(); ++expit){ fix_substituted(expit.current(), *sk, *sv); } } /// ... Re-build references. stmt.build_refs(); } /// Adjust gmap. adjust_gmap(pgm, final); } void optimize_ssa(ProgramUnit& pgm, SSA_OptFlags flags){ if ( flags & SSA_OPT_BETA) { optimize_ssa_beta(pgm); } /// Iterate until convergence. bool change; int iter_count=0; do { change=false; if ( flags & SSA_OPT_MU) { change=change || optimize_ssa_mu(pgm); } if ( flags & SSA_OPT_GAMMA) { change=change || optimize_ssa_gamma(pgm); } if ( flags & SSA_OPT_ETA) { change=change || optimize_ssa_eta(pgm); } ++iter_count; } while (change); if (flags & SSA_OPT_ZERO){ /// cerr<<"\nOptimize_ssa_zero: "<<pgm.routine_name_ref(); optimize_ssa_zero(pgm); } cout<<"\n\tOptimize_ssa "<<pgm.routine_name_ref() <<" converged after "<<iter_count<<" iterations."; /// if (iter_count>1){ /// cout<<"\n\t\tSSA prune converged after "<<iter_count<< /// " iterations for pgm "<<pgm.routine_name_ref(); /// } else { /// cout<<"\n\t\tSSA prune converged after an iteration for pgm " /// <<pgm.routine_name_ref(); /// } /// Re-build refs. pgm.stmts().build_all_refs(); }

© 1995-2005 University of Illinois, Urbana-Champaign. All rights reserved.  Fri Mar 25 23:05:59 2005