Polaris: ip_ssa.cc Source File

ip_ssa.cc Go to the documentation of this file. /// #include <set> #include "Statement/AssignmentStmt.h" #include "Statement/DoStmt.h" #include "utilities/gsa_util.h" #include "utilities/program_util.h" #include "Deadcode/deadcode.h" #include "simple_maymods.h" #include "ip_ssa.h" #include "trans_util.h" #include "optimize_ssa.h" #include "Expression/BinaryExpr.h" #include "Expression/UnaryExpr.h" #include "Expression/expr_funcs.h" static Database<ProgramUnit*, Database<Symbol*, RefList<Symbol> > > iomap; /*! \brief Global mapping per pgm, per base symbol, of subprogram calls into SSA names. */ static Database<ProgramUnit*, /// ... Every program unit. Database<Statement*, /// ... Every call site. RefDatabase<Symbol*, /// ... Every base symbol. Symbol> > > _gmap; /// ... SSA name. /*! \brief The reaching definitions list per pgm, per base symbol (for commons only). */ static Database<ProgramUnit*, /// ... Every program unit. Database<Symbol*, /// ... Every base common variable. List<GlobalDefSite> > > _dmap; /// ... Reaching defs. Database<ProgramUnit*, Database<Statement*, RefDatabase<Symbol*, Symbol> > >& ip_ssa_gmap(){ return _gmap; } Database<ProgramUnit*, Database<Symbol*, List<GlobalDefSite> > >& ip_ssa_dmap(){ return _dmap; } static void print_dmap(){ cerr<<"\n\n\nBEGIN DMAP: \n\n"; KeyIterator<ProgramUnit*, Database<Symbol*, List<GlobalDefSite> > > it1= _dmap; for (; it1.valid(); ++it1){ cerr<<"\nFor pgm. "<<it1.current_key()->routine_name_ref(); KeyIterator<Symbol*, List<GlobalDefSite> > it2=it1.current_data(); for(; it2.valid(); ++it2){ cerr<<"\n\tFor Sym. "<<it2.current_key()->name_ref()<< " "<<it2.current_data(); } } cerr<<"\n\n\nEND DMAP\n\n\n "; } static void print_gmap(ProgramUnit& pgm){ cerr<<"\n\n\nBEGIN GMAP: \n\n"; cerr<<"\nFor pgm. "<<pgm.routine_name_ref(); if (_gmap.find_ref(&pgm)!=0) { KeyIterator<Statement*, RefDatabase<Symbol*, Symbol> > it2= *_gmap.find_ref(&pgm); for(; it2.valid(); ++it2){ cerr<<"\nFor stmt: "; int w=1; it2.current_key()->write(cerr, w); KeyIterator<Symbol*, Symbol> it3=it2.current_data(); for(; it3.valid(); ++it3){ cerr<<"\n"<<it3.current_key(); cerr<<"\n\tFor Sym. "<<it3.current_key()->name_ref()<< ", mapped is: "<<it3.current_data().name_ref(); } } } cerr<<"\n\n\nEND GMAP\n\n\n "; } static void print_in_out_sets(Program& prog){ for (KeyIterator<ProgramUnit*, Database<Symbol*, RefList<Symbol> > > pssit= iomap; pssit.valid(); ++pssit){ cerr<<"\nIn pgm. "<<pssit.current_key()->routine_name_ref(); for (KeyIterator<Symbol*, RefList<Symbol> > ssit= pssit.current_data(); ssit.valid(); ++ssit){ cerr<<"\n\tFor output value "<<ssit.current_key()->name_ref()<<"\t:"; for (Iterator<Symbol> sit= ssit.current_data(); sit.valid(); ++sit){ cerr<<" "<<sit.current().name_ref(); } } } } void build_in_out_set(Symbol& out, IntraPCodeDomain& domain, RefList<Symbol>& in, ProgramUnit& pgm, Program& prog){ /// Go back on the use-def chains for all variables input to this one. RefList<Symbol> q; q.ins_last(out); Database<Symbol*, IntElem> seen; /// cerr<<"\n\n\nFor symbol: "<<out.name_ref(); while (q.entries()){ VariableSymbol& current=(VariableSymbol&)q.grab(0); /// cerr<<"\nDequeuing "<<current.name_ref(); VariableSymbol* base_current=&current; if (base_current->is_gsa_symbol()){ base_current=(VariableSymbol*)&base_current->gsa_base_symbol(); } if (seen.find_ref(&current)){ continue; } else { seen.ins(&current, new IntElem(0)); } if (current.intrinsic()){ continue; } String basename; int rank; gsa_details(current.name_ref(), basename, rank); if (rank==0){ bool is_data=false; /// ... It is an input to the whole routine or given in a DATA statement. for (Iterator<Data> dit=pgm.data(); dit.valid(); ++dit){ for(Iterator<Expression> eit=dit.current().variable_list().arg_list(); eit.valid(); ++eit){ if (eit.current().base_variable_ref()==base_current){ /// ... In a DATA. is_data=true; break; } } if (is_data) break; } if (is_data){ /// ... Do nothing, its value depends only on constants. } else { /// ... It is an input to the whole routine, it'd better be translatable. if (!in.member(current)){ in.ins_last(current); } } continue; } /// ... Not an input, proper GSA name (rank>=1). DefLoc* defloc=pgm.gsa_deflocs_guarded().find_ref(current); if (!defloc) { p_abort("Bad DefLoc map."); } if (!defloc->stmt_valid()) { p_abort("Bad DefLoc map."); } Statement& def=defloc->stmt_guarded(); /// ... Check whether definition site is within domain. if (!domain.contains(def)){ if (!in.member(current)){ in.ins_last(current); } continue; } Statement* call=0; ProgramUnit* callee=0; /// ... If this is a call site, then current value is either: /// ... 1. in a common modified inside. /// ... 2. passed as a formal parameter /// ... 3. returned by a function /// ... Find corresponding symbol in called routine. /// ... 1. THETA RefList<Symbol> corresponding_base_syms; if (def.stmt_class()==ASSIGNMENT_STMT){ if (def.rhs().op()==THETA_OP){ call=&def; while (call!=0){ if (called_pgm(*call)){ break; } call=call->prev_ref(); } p_assert(call, "Bad THETA placement."); callee=called_pgm(*call); Symbol* cbs=0; cbs=callee->symtab().find_ref(basename); p_assert(cbs, "Could not map common vars."); corresponding_base_syms.ins_last(*cbs); } } /// ... 2. Subroutine or function. if (!call){ callee=called_pgm(def); if (callee){ /// ... Subprogram call. call=&def; Translator translator(pgm, def); corresponding_base_syms=untranslate_var(current, *callee, pgm, *call); p_assert(corresponding_base_syms.entries(), "No suitable un-translation found."); /// ... Must also add corresponding symbol if it is also a common. if (current.common_ref()){ corresponding_base_syms.ins_last(*callee->symtab().find_ref(basename)); } } } /// ... Either THETA, function or subroutine. if (call){ Translator translator(pgm, *call); /// ... Find all inputs for this output. for(Iterator<Symbol> sit=corresponding_base_syms; sit.valid(); ++sit){ Symbol* corresponding_base_sym=&sit.current(); Database<Symbol*, RefList<Symbol> >* local_iomap=iomap.find_ref(callee); if (local_iomap==0){ cerr<<"\nFor routine: "<<callee->routine_name_ref(); p_abort("Could not find local in-out map."); } RefList<Symbol>* callee_iomap= local_iomap->find_ref(corresponding_base_sym); if (!callee_iomap){ cerr<<"\nFor routine: "<<callee->routine_name_ref() <<" and symbol "<<corresponding_base_sym->name_ref(); p_abort( "Could not find in-out map."); } for(Iterator<Symbol> csit=*callee_iomap; csit.valid(); ++csit){ /// cerr<<"\n\t\tcsit.current()="<<csit.current().name_ref() /// <<"\n iomap = "<<*callee_iomap; // Translate every input back to the caller. Expression* te=translate_var((VariableSymbol&)csit.current(), *callee, pgm, *call); /// cerr<<"\n\t\tactuals:"<<parameters(*call); if(te==0){ /// cerr<<"\nUse of possibly undefined variable " /// <<csit.current().name_ref() /// <<" in subprogram "<<callee->routine_name_ref(); /// p_warning(""); /// ... Do nothing else, it was probably an undefined local /// ... that will never need definition due to application logic. } else { te=simplify(te); if (te->op()==INTEGER_CONSTANT_OP || te->op()==REAL_CONSTANT_OP || te->op()==STRING_CONSTANT_OP || te->op()==LOGICAL_CONSTANT_OP || te->op()==HOLLERITH_CONSTANT_OP){ /// ... Do nothing } else { RefList<Symbol> referred; referred_symbols(*te, referred); /// cerr<<"\n\t\tte: "<<*te; for (Iterator<Symbol> ssit=referred; ssit.valid(); ++ssit){ /// cerr<<"\nQueuing "<<ts->name_ref(); q.ins_last(ssit.current()); } } delete te; } } } continue; } /// ... Regular definition site. Add input values. Iterator<Expression> sit=def.in_refs(); for( ; sit.valid(); ++sit){ switch(sit.current().op()){ case ID_OP: /// cerr<<"\nQueuing "<<sit.current().symbol().name_ref(); q.ins_last(sit.current().symbol()); break; case ARRAY_REF_OP: /// cerr<<"\nQueuing "<<sit.current().array().symbol().name_ref(); q.ins_last(sit.current().array().symbol()); } } } } Symbol* last_gsa_symbol(ProgramUnit& pgm, Symbol& sym){ /// Sanity check (make sure the symbol is in the symbol table. /// if (pgm.symtab().find_ref(sym.name_ref())!=&sym){ /// cerr<<"\nIn pgm. "<<pgm.routine_name_ref() /// <<" base symbol "<<sym.name_ref()<<" is not in the symbol table."; /// p_abort("Sanity check failure."); /// } /// silvius: this should be done on the CDG, for now assume restructured. Symbol* last_def_sym=0; for(Statement* stit=pgm.stmts().last_ref(); stit!=0; stit=stit->prev_ref()){ /// int dummy=1; /// stit->write(cerr, dummy); if (stit->stmt_class()==ENDDO_STMT){ /// ... If there is a MU for 'sym', return it. Statement* dostmt=stit->follow_ref(); Statement* ps=dostmt->next_ref(); while (ps){ if (ps->stmt_class()!=ASSIGNMENT_STMT){ break; } if (ps->rhs().op()!=MU_OP){ break; } if (gsa_base(ps->lhs().symbol())==&sym){ last_def_sym=&ps->lhs().symbol(); break; } ps=ps->next_ref(); } } if (last_def_sym) break; for(Iterator<Expression> sit=stit->out_refs(); sit.valid(); ++sit){ Expression& ce=sit.current(); VariableSymbol* candidate=0; switch (ce.op()){ case ID_OP: candidate=(VariableSymbol*)&ce.symbol(); break; case ARRAY_REF_OP: candidate=(VariableSymbol*)&ce.array().symbol(); break; default: cerr<<"\nIn statement: "<<*stit; cerr<<"\n "<<sit.current(); p_abort("Out ref. is not variable."); } /// cerr<<"\n\tCandidate: "<<candidate->name_ref() /// <<"\t sym: "<<sym; if (candidate->sym_class()==FUNCTION_CLASS){ /// ... There seems to be a bug with function names. /// ... better make sure. String basename; int rank; gsa_details(candidate->name_ref(), basename, rank); if (basename==sym.name_ref()){ last_def_sym=candidate; break; } } else { if (!candidate->is_gsa_symbol()){ if (has_maymod(*stit)){ if (is_var_in_maymod(*candidate, *stit)){ cerr<<"\n "<<candidate->name_ref() <<"\n in stmt "<<*stit; p_abort("Definition must refer to nontrivial GSA name."); } else { /// ... Do nothing, it is actually wrongly placed in out_refs(). continue; } } else { if (called_pgm(*stit)){ /// ... This one should be ok, even though it is missing its /// ... MAYMOD assertion. p_warning("Subprogram call statement has no MAYMOD assertions."); last_def_sym=candidate; break; } else { cerr<<"\n "<<candidate->name_ref() <<"\n in stmt "<<*stit; /// pgm.write(cerr); p_abort("Definition must refer to nontrivial GSA name."); } } } if (&candidate->gsa_base_symbol()==&sym){ last_def_sym=candidate; break; } } } if (last_def_sym) { break; } } return last_def_sym; } void build_in_out_sets(Program& prog, ProgramUnit& pgm, Symbol& sym, Database<Symbol*, RefList<Symbol> >& pgm_iomap){ RefList<Symbol>* in=new RefList<Symbol>; pgm_iomap.ins(&sym, in); /// Find gsa name corresponding to latest definition of this symbol. Symbol* last_def_sym=last_gsa_symbol(pgm, sym); if (last_def_sym==0){ /// ... Not defined in this routine. in->ins_last(sym); return; } IntraPCodeDomain domain(pgm); /// cerr<<"\n Running build_in_out_set 1 on "<<last_def_sym->name_ref(); build_in_out_set(*last_def_sym, domain, *in, pgm, prog); } void build_in_out_sets(Program& prog, ProgramUnit& pgm){ if (!is_code_pu(pgm)){ /// ... Data subprogram. return; } if (iomap.find_ref(&pgm)){ /// ... Already built. return; } Database<Symbol*, RefList<Symbol> >* pgm_iomap= new Database<Symbol*, RefList<Symbol> >; iomap.ins(&pgm, pgm_iomap); /// Make sure all children are already done. for(Iterator<ProgramUnit> pgmit=pgm.calls(); pgmit.valid(); ++pgmit){ /// cerr<<"\n "<<pgm.routine_name_ref() /// <<" CALLS "<<pgmit.current().routine_name_ref(); build_in_out_sets(prog, pgmit.current()); } /// ofstream before("before_bios"); /// prog.write(before); /// before.close(); /// Initialize OUT to all formals + commons + return value. /// First add formals. RefList<Symbol> out; Statement* entry=pgm.stmts().first_ref(); while (entry->stmt_class()!=ENTRY_STMT) { entry=entry->next_ref(); if(entry==0) break; } if(entry==0){ cerr<<"\nProgram without entry: "<<pgm.routine_name_ref(); p_abort(""); } List<Expression>& formals=parameters(*entry); for(Iterator<Expression> eit=formals; eit.valid(); ++eit){ if (eit.current().op()!=ID_OP){ cerr<<"Formal not ID_OP: "<<eit.current(); p_abort(""); } Symbol& sym=eit.current().symbol(); out.ins_last(sym); } /// Now add common vars. for(DictionaryIter<CommonBlock> cbit=pgm.common_blocks(); cbit.valid(); ++cbit){ for(Iterator<Symbol> sit=cbit.current().iterator(); sit.valid(); ++sit){ if (!out.member(sit.current())){ out.ins_last(sit.current()); } } } /// Now add return value. if (pgm.pu_class()==FUNCTION_PU_TYPE){ Symbol* fret=pgm.symtab().find_ref(pgm.routine_name_ref()); p_assert(fret, "Function did not declare return value."); out.ins_last(*fret); } /// For every symbol, execute the program unit in reverse symbolically /// following use-def chains of output variables. for(Iterator<Symbol> sit=out; sit.valid(); ++sit){ Symbol& sym=sit.current(); /// cerr<<"\n Running build_in_out_sets 0 on "<<sym.name_ref(); build_in_out_sets(prog, pgm, sym, *pgm_iomap); } } /// Builds, for every subprogram, the set of input values for every output. /// The output values are considered right before exiting the routine, /// and the input ones right after entry. void build_in_out_sets(Program& prog){ /// prog.write(cerr); prog.compute_call_lists(); /// Find top level routines. RefList<ProgramUnit> tops; for (KeyIterator<String, ProgramUnit> pgmit=prog; pgmit.valid(); ++pgmit){ ProgramUnit& pgm=pgmit.current_data(); if (pgm.called_by().entries()==0){ tops.ins_last(pgm); } } /// Iterate over top level routines. for(Iterator<ProgramUnit> pit=tops; pit.valid(); ++pit){ ProgramUnit& pgm=pit.current(); build_in_out_sets(prog, pgm); } /// Print them. /// print_in_out_sets(prog); } Expression* theta(Expression *parameters); /// ... from Expression.cc Expression* eta(Expression* gate, Expression* parameters); /// ... from Expression.cc static bool actual_out_param(Symbol& sym, Statement& stmt){ /// cerr<<"\n actual_out_param: "<<&sym; for(Iterator<Expression> eit=parameters(stmt); eit.valid(); ++eit){ /// cerr<<"\n\t eit: "<<eit.current(); if(eit.current().base_variable_ref()==&sym) return true; } return false; } static void remove_dummy_assignments(Program& prog){ /// Remove stmts like 'x = x'. KeyIterator<String,ProgramUnit> progiter = prog; for (progiter.reset(); progiter.valid(); ++progiter) { ProgramUnit& pgm=progiter.current_data(); Statement* ps=pgm.stmts().first_ref(); Statement* next=0; while (ps){ next=ps->next_ref(); if (ps->stmt_class()==ASSIGNMENT_STMT){ if (ps->lhs()==ps->rhs()){ pgm.stmts().del(*ps); } } ps=next; } } } static void add_dummy_global_assignments_at_calls(Program& prog){ /// The second major step is to insert dummy assignments after routine calls /// modifying commons. KeyIterator<String,ProgramUnit> progiter = prog; for (progiter.reset(); progiter.valid(); ++progiter) { ProgramUnit& pgm=progiter.current_data(); Statement* ps=pgm.stmts().first_ref(); Statement* next; while (ps){ next=ps->next_ref(); ProgramUnit* callee=called_pgm(*ps); if (callee) { Symbol* callee_sym; if (ps->stmt_class()==CALL_STMT){ callee_sym=&ps->routine_guarded().symbol(); } else { callee_sym=&ps->rhs().function().symbol(); } Iterator<Assertion> asrt_iter = ps->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){ Symbol* sym=aexpr_iter.current().base_variable_ref(); if (sym) { if (sym->common_ref() && /// ... Do not insert theta if it is also passed as parameter. !actual_out_param(*sym, *ps)){ if (sym->is_scalar()){ /// ... Insert dummy assignment to make GSA give it a distinctive name. AssignmentStmt* newstmt= new AssignmentStmt(pgm.stmts().new_tag(), id(*sym), theta(comma(id(*sym)))); pgm.stmts().ins_before(newstmt, next); } else { /// ... Insert dummy assignment to make GSA give it a distinctive name. AssignmentStmt* newstmt= new AssignmentStmt(pgm.stmts().new_tag(), id(*sym), theta(comma(id(*sym)))); pgm.stmts().ins_before(newstmt, next); } } } } } } } ps=next; } } } static void add_dummy_eta_assignments_after_loops(Program& prog){ /// The third major step is to insert dummy assignments after loops KeyIterator<String,ProgramUnit> progiter = prog; for(progiter.reset();progiter.valid();++progiter) { ProgramUnit& pgm=progiter.current_data(); Iterator<Statement> stmt_iter= pgm.stmts().stmts_of_type(DO_STMT,WHILE_STMT); for(stmt_iter.reset();stmt_iter.valid();++stmt_iter) { Statement& stmt=stmt_iter.current(); Expression * _condition; Type type(VOID_TYPE); RefList<Symbol> sym_list; Iterator<Statement> loop_body_iter; if(stmt.stmt_class()==DO_STMT) { Expression& lmt=stmt.limit(); if(lmt.op()!=INFINITY_OP) { _condition=at_least_one_iteration(pgm, (DoStmt&)stmt, false); } else { Statement * _if_stmt=stmt.next_ref(); if (_if_stmt->stmt_class()==ENDDO_STMT){ /// ... Empty DO i=1,Inf _condition=constant(".TRUE."); } else { p_assert(_if_stmt->stmt_class()==IF_STMT, "The next statement to the do statement" " should be IF statement\n"); Expression& if_condition=_if_stmt->expr(); _condition=simplify(not(if_condition.clone())); } }; loop_body_iter= pgm.stmts().iterate_loop_body(CASTAWAY(Statement *)&stmt); } else { Expression& while_condition=stmt.expr(); _condition=simplify(not(while_condition.clone())); /// ... guobin & silvius: this is not really right, change it if you /// ... have to deal with while loops. p_warning("Incomplete implementation."); loop_body_iter= pgm.stmts().iterator((Statement&)stmt,*stmt.follow_ref()); }; for(loop_body_iter.reset();loop_body_iter.valid();++loop_body_iter) { Statement& loop_body_stmt=loop_body_iter.current(); if(loop_body_stmt.stmt_class()==DO_STMT) continue; RefSet<Expression> out_exprs=loop_body_stmt.out_refs(); while(out_exprs.entries()>0) { Expression& out_expr=out_exprs.grab(); if(out_expr.op()==ARRAY_REF_OP||out_expr.op()==ID_OP) { Symbol * _out_sym=out_expr.base_variable_ref(); if(!sym_list.member(*_out_sym)) { sym_list.ins_last(*_out_sym); } } } }; Iterator<Symbol> sym_iter=sym_list; Statement * _stmt_ref=stmt.follow_ref(); for(sym_iter.reset();sym_iter.valid();++sym_iter) { Symbol& sym=sym_iter.current(); AssignmentStmt* newstmt= new AssignmentStmt(pgm.stmts().new_tag(), id(sym), eta(_condition->clone(), comma(id(sym),id(sym)))); pgm.stmts().ins_after(newstmt,_stmt_ref); } delete _condition; } } } static void modify_dummy_eta_assignments_after_loops(Program& prog){ /// The forth major step is to modify dummy assignments after loops KeyIterator<String,ProgramUnit> progiter = prog; for(progiter.reset();progiter.valid();++progiter) { ProgramUnit& pgm=progiter.current_data(); Iterator<Statement> stmt_iter=pgm.stmts().stmts_of_type(DO_STMT,WHILE_STMT); for(stmt_iter.reset();stmt_iter.valid();++stmt_iter) { Statement& stmt=stmt_iter.current(); RefMap<Symbol,Statement> mu_assignment; RefList<Statement> eta_assignment; bool keep_searching=true; Statement * _stmt_ptr=stmt.next_ref(); while(keep_searching) { if(_stmt_ptr->stmt_class()==ASSIGNMENT_STMT) { Expression& mu_expr=_stmt_ptr->rhs(); if(mu_expr.op()==MU_OP) { p_assert(_stmt_ptr->lhs().op()==ID_OP, "The left expression in mu" " statement should be an id expression\n"); Symbol& mu_sym=_stmt_ptr->lhs().symbol(); mu_assignment.ins(mu_sym,*_stmt_ptr); } else keep_searching=false; } else keep_searching=false; _stmt_ptr=_stmt_ptr->next_ref(); }; _stmt_ptr=stmt.follow_ref()->next_ref(); keep_searching=true; while(keep_searching) { if(_stmt_ptr->stmt_class()==ASSIGNMENT_STMT) { Expression& eta_expr=_stmt_ptr->rhs(); if(eta_expr.op()==ETA_OP) { eta_assignment.ins_last(*_stmt_ptr); } else { keep_searching=false; } } else { keep_searching=false; } _stmt_ptr=_stmt_ptr->next_ref(); }; Iterator<Statement> eta_iter=eta_assignment; for(eta_iter.reset();eta_iter.valid();++eta_iter) { Statement& eta_stmt=eta_iter.current(); Expression& eta_expr=eta_stmt.rhs(); p_assert(eta_expr.op()==ETA_OP, "The right expression in eta statement should be an eta expression\n"); Expression& first_eta_expr=eta_expr.parameters_guarded().arg_list()[1]; Symbol& first_sym=first_eta_expr.symbol(); /// ... p_assert(mu_assignment.member(first_sym), /// ... "The first symbol in an eta statement should be in a mu statement\n"); if(mu_assignment.member(first_sym)) { Statement& mu_stmt=mu_assignment[first_sym]; Expression& mu_expr=mu_stmt.rhs(); Expression& second_mu_expr=mu_expr.parameters_guarded().arg_list()[0]; Symbol& new_sym=second_mu_expr.symbol(); substitute_var(first_eta_expr,first_sym,new_sym); } } } } } /// Return the gsa name of the actual common var at a callsite. /// It only returns the value if the variable is modified during the call. static Symbol* def_call_gsa_name(Statement& callsite, Symbol& base){ if (!base.is_scalar() && !base.is_array()){ return 0; } p_assert(base.common_ref(), "Argument must be in a common."); p_assert(!((VariableSymbol&)base).is_gsa_symbol(), "Argument must NOT be a GSA symbol."); for (Statement* ps=callsite.next_ref(); ps; ps=ps->next_ref()){ if (ps->stmt_class()!=ASSIGNMENT_STMT) { break; } if (ps->rhs().op()!=THETA_OP){ break; } /// ... This is a THETA stmt. Expression& id=ps->rhs().parameters_guarded().arg_list()[0]; if (id.op()!=ARRAY_REF_OP && id.op()!=ID_OP){ continue; } VariableSymbol& sym=(VariableSymbol&)id.symbol(); Symbol* base_sym=&sym; if (sym.is_gsa_symbol()){ base_sym=&sym.gsa_base_symbol(); } if (base_sym==&base){ return &sym; } } /// No match, return given arg. return 0; } static Symbol* use_call_gsa_name(ProgramUnit& pgm, Statement& callsite, Symbol& base){ Database<Statement*, RefDatabase<Symbol*, Symbol> >* pgmap= _gmap.find_ref(&pgm); p_assert(pgmap, "Cannot find gmap for program unit."); RefDatabase<Symbol*, Symbol>* spgmap=pgmap->find_ref(&callsite); p_assert(spgmap, "Cannot find gmap for statement."); return spgmap->find_ref(&base); } /// Builds dmap given gmap for one pgm only. /// 'gmap' is a global mapping per pgm, per base symbol, of subprogram calls into SSA /// names. /// 'dmap' is the reaching definitions list per pgm, per base symbol (for /// commons only). void build_def_map(Program& prog, EntryPoints& ep, ProgramUnit& pgm){ static set<ProgramUnit*> processed; if (processed.find(&pgm)!=processed.end()){ return; } else { processed.insert(&pgm); } for (Iterator<Statement> stit=pgm.stmts().iterator(); stit.valid(); ++stit){ Statement& stmt=stit.current(); ProgramUnit* pcallee=called_pgm(stmt); if (pcallee) { /// int w=16; /// cerr<<"\nIn pgm. "<<pgm.routine_name_ref(); /// cerr<<"\n\tAt call site:"; /// stmt.write(cerr,w); ProgramUnit& callee=*pcallee; Statement& call_site=stmt; /// ... This is a call site. Database<Symbol*, List<GlobalDefSite> >* pdmap=_dmap.find_ref(&callee); if (!pdmap){ pdmap=new Database<Symbol*, List<GlobalDefSite> >; /// cerr<<"\nInserting DMAP for "<<callee.routine_name_ref(); _dmap.ins(&callee, pdmap); } /// ... Now go over all common base vars in pgm. for(DictionaryIter<Symbol> sit=pgm.symtab().iterator(); sit.valid(); ++sit){ Symbol& sym=sit.current(); if (sym.common_ref()){ if (!((VariableSymbol&)sym).is_gsa_symbol()){ Symbol* base=&sym; /// cerr<<"\n\t\tLooking at symbol "<<base->name_ref(); /// ... Find it in dmap, or create if not existent. Symbol* corresponding_sym= callee.symtab().find_ref(base->name_ref()); if (corresponding_sym==0){ prog.write(cerr); cerr<<"\nIn pgm. "<<callee.routine_name_ref(); cerr<<"\nIn common "<<base->common_ref()->name_ref(); cerr<<"\nSymbol "<<base->name_ref(); p_abort("Could not find corresponding symbol in symbol table."); } List<GlobalDefSite>* sdmap=pdmap->find_ref(corresponding_sym); if (!sdmap){ sdmap=new List<GlobalDefSite>; pdmap->ins(corresponding_sym, sdmap); } /// ... Find value, aka real SSA name while at this call site. Symbol* usedname=use_call_gsa_name(pgm, call_site, *base); p_assert(usedname, "Could not figure out name used at call site."); /// cerr<<"\n\t\tName used at callsite "<<usedname->name_ref(); /// ... Store this symbol's definition into the callee's dmap. DefLoc* defloc=pgm.gsa_deflocs_guarded().find_ref(*usedname); bool found_def=true; if (!defloc) { found_def=false; } else { if (!defloc->stmt_valid()) { found_def=false; } } if (found_def){ sdmap->ins_last(new GlobalDefSite(pgm, defloc->stmt_guarded())); } else { /// cerr<<"\n\t\tNot defined in "<<pgm.routine_name_ref(); /// ... Could not find def. Try to add the last known defs. Database<Symbol*, List<GlobalDefSite> >* own_pdmap= _dmap.find_ref(&pgm); if (own_pdmap==0){ cerr<<"\nFor program unit: "<<pgm.routine_name_ref(); p_abort("Nonexisting dmap object for this pgm."); } List<GlobalDefSite>* own_sdmap= own_pdmap->find_ref(base); /// ... cerr<<"\nOwn pdmap = "<<*own_pdmap; if (own_sdmap){ for(Iterator<GlobalDefSite> gdsit=*own_sdmap; gdsit.valid(); ++gdsit){ sdmap->ins_last(new GlobalDefSite(gdsit.current())); } } else { /// ... This symbol is not initialized yet. Hopefully this call /// ... is to a routine that will do it. /// ... Do nothing, there is nothing to insert. } } } } } /// ... Go recursively into the callee. build_def_map(prog, ep, callee); } } } /// Builds dmap given gmap. /// 'gmap' is a global mapping per pgm, per base symbol, of subprogram /// calls into SSA names. /// 'dmap' is the reaching definitions list per pgm, per base symbol (for /// commons only). /// silvius: do a DFS on the call graph in program order. void build_def_map(Program& prog){ /// Walk down the call dag adding defs to 'dmap'. EntryPoints* ep=prog.entry_points(); for(KeyIterator<String, ProgramUnit> kit=prog; kit.valid(); ++kit){ ProgramUnit& pgm=kit.current_data(); if (pgm.pu_class()==PROGRAM_PU_TYPE){ /// ... Must insert an empty list of defs for every common scalar. Database<Symbol*, List<GlobalDefSite> >* pdmap= new Database<Symbol*, List<GlobalDefSite> >; _dmap.ins(&pgm, pdmap); for (DictionaryIter<Symbol> sit=pgm.symtab().iterator(); sit.valid(); ++sit){ if (sit.current().common_ref()){ if (sit.current().is_array()){ continue; } pdmap->ins(&sit.current(), new List<GlobalDefSite>); build_def_map(prog, *ep, pgm); } } } } delete ep; /// print_dmap(); /// prog.write(cerr); /// exit(1); } /// Finds out whether the program is in SSA form. /// It does it by checking whether there are any symbols in /// the main subprogram that are SSA names. static bool already_ip_ssa(Program& prog){ ProgramUnit* main_pgm=find_main_pgm(prog); p_assert(main_pgm, "Could not find main pgm."); KeyIterator<String,ProgramUnit> myprogiter = prog; for(myprogiter.reset();myprogiter.valid();++myprogiter){ ProgramUnit& pgm=myprogiter.current_data(); for(DictionaryIter<Symbol> sit=pgm.symtab().iterator(); sit.valid();++sit){ String name=sit.current().name_ref(); if (name.index("@")!=-1){ return true; } } } return false; } void make_ip_ssa(Program& prog){ if (already_ip_ssa(prog)){ return; } /// Generate MAYMOD assertions. generate_maymods(prog, true, false); /// Insert dummy assignments for thetas. add_dummy_global_assignments_at_calls(prog); /// Insert dummy assignments for etas. add_dummy_eta_assignments_after_loops(prog); /// Translate to GSA. KeyIterator<String,ProgramUnit> progiter = prog; for (progiter.reset(); progiter.valid(); ++progiter) { ProgramUnit& pgm=progiter.current_data(); if (!is_code_pu(pgm)) continue; MakeGSA(pgm); } //Modify ETA statements to make them correct modify_dummy_eta_assignments_after_loops(prog); for (progiter.reset(); progiter.valid(); ++progiter) { ProgramUnit& pgm=progiter.current_data(); if (!is_code_pu(pgm)) continue; optimize_ssa(pgm, SSA_OPT_BETA | SSA_OPT_MU | SSA_OPT_GAMMA | SSA_OPT_ETA | SSA_OPT_ZERO ); } /// Build dmap given the gmap computed during MakeGSA. build_def_map(prog); /// Build global in-out structures. build_in_out_sets(prog); } void undo_ip_ssa(Program& prog){ if (!already_ip_ssa(prog)){ return; } KeyIterator<String,ProgramUnit> progiter = prog; for (progiter.reset(); progiter.valid(); ++progiter) { ProgramUnit& pgm=progiter.current_data(); if (!is_code_pu(pgm)) continue; DeGSA(pgm); /// ... eliminate_dead_code(pgm, DONT_DEADCODE_ARRAYS, 0); } remove_dummy_assignments(prog); _dmap.clear(); _gmap.clear(); }

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