Polaris: eg_traces.cc Source File

eg_traces.cc Go to the documentation of this file. /// /// /// /// /// #include "EvolutionGraph.h" #include "eg_utils.h" #include "affine.h" #include "BackTrace.h" #include "ip_ssa/trans_util.h" #include "ip_ssa/optimize_ssa.h" #include "guarded_values.h" EvolutionGraph* _get_eg(ProgramUnit* pgm, Statement* loop); /*! \brief Find all possible traces from input values to given node so that the input value + evolutions on the road are within the given range. */ void eg_trace_from_input(ProgramUnit& pgm, DoStmt* loop, pair<RangeExpr*, bool>& range, Symbol* node, DefTrace::DTrace& dt){ list<Symbol*> trace; _get_eg(&pgm, loop)->trace_from_input(node, range, trace); for(list<Symbol*>::iterator it=trace.begin(); it!=trace.end(); ++it){ dt.push_back(make_pair(&pgm, *it)); } } /*! \brief Performs forward substitution on demand. x -> y, ev=[1,1] ==> y = x+1 \warning Returns 0 if no proper substitution can be found (rather than returning id(*given) as would seem fit). */ Expression* eg_forward_substitute(ProgramUnit& pgm, Symbol& sym){ EvolutionGraph* eg=_get_eg(&pgm, def_loop(sym, pgm)); return eg->substitute(&sym); } /*! \brief Performs forward substitution on demand. */ Expression* eg_forward_substitute(ProgramUnit& pgm, DoStmt* loop, Expression* expr){ EvolutionGraph* eg=_get_eg(&pgm, loop); RefList<Symbol> syms; referred_symbols(*expr, syms); for(Iterator<Symbol> sit=syms; sit.valid(); ++sit){ Symbol& sym=sit.current(); Expression* s=eg->substitute(&sym); if (s){ expr=simplify(substitute_var(expr, sym, *s)); delete s; } } return expr; } static Statement* is_mu_sym(Symbol& sym, ProgramUnit& pgm){ DefLoc* defloc=pgm.gsa_deflocs_guarded().find_ref(sym); if (defloc->stmt_valid()) { Statement& def=defloc->stmt_guarded(); if (def.stmt_class()==ASSIGNMENT_STMT){ if(def.rhs().op()==MU_OP){ if (&def.lhs().symbol()==&sym){ return def.outer_ref(); } } } } return 0; } static Symbol& get_back_sym(Symbol& sym, ProgramUnit& pgm){ /// 'sym' must be MU symbol. DefLoc* defloc=pgm.gsa_deflocs_guarded().find_ref(sym); if (defloc->stmt_valid()) { Statement& def=defloc->stmt_guarded(); if (def.stmt_class()==ASSIGNMENT_STMT){ if(def.rhs().op()==MU_OP){ if (&def.lhs().symbol()==&sym){ return def.rhs().parameters_guarded().arg_list()[1].symbol(); } } } } p_abort("Could not find BACK for given MU."); } static Evolution<Expression> get_evolution(EvolutionGraph& veg, Symbol* source, Symbol* dest){ /// cerr<<"\ns = "<<source->name_ref() /// <<", d = "<<dest->name_ref(); const Evolution<Expression>* found=veg.get_edge(source, dest); if (found!=0){ return *found; } else { p_abort("Edge not in graph."); } } static pair<RangeExpr*, bool> subtract_evolution(pair<RangeExpr*, bool>& range, const Evolution<Expression>& ev){ pair<RangeExpr*, bool> toret; if (*ev.min_difference()==*ev.max_difference()){ toret=make_pair(new RangeExpr(simplify(sub(range.first->lb().clone(), ev.min_difference()->clone())), simplify(sub(range.first->ub().clone(), ev.min_difference()->clone()))), range.second); delete range.first; } else { if (range.second==false){ toret= make_pair(new RangeExpr(simplify(sub(range.first->lb().clone(), ev.max_difference()->clone())), simplify(sub(range.first->ub().clone(), ev.min_difference()->clone()))), false); delete range.first; } else { p_abort("Not implemented"); } } return toret; } static Statement* callsite(ProgramUnit& pgm, Symbol& sym){ DefLoc* defloc=pgm.gsa_deflocs_guarded().find_ref(sym); p_assert(defloc, "Could not find definition for symbol."); if (defloc->stmt_valid()){ ProgramUnit* callee=called_pgm(defloc->stmt_guarded()); if (callee){ return &defloc->stmt_guarded(); } if (defloc->stmt_guarded().stmt_class()==ASSIGNMENT_STMT){ if (defloc->stmt_guarded().rhs().op()==THETA_OP){ Statement* ps=&defloc->stmt_guarded(); while(ps->stmt_class()==ASSIGNMENT_STMT){ if (ps->rhs().op()!=THETA_OP){ return ps; } ps=ps->prev_ref(); } return ps; } } } return 0; } void _print_range(const char* sname, const pair<RangeExpr*, bool>& r); static pair<RangeExpr*, bool> _translate_range(const pair<RangeExpr*, bool>& range, ProgramUnit& callee, ProgramUnit& caller, Statement& callsite){ Expression* range_callee=range.first->clone(); RefList<Symbol> syms; referred_symbols(*range.first, syms); for(Iterator<Symbol> sit=syms; sit.valid(); ++sit){ Symbol& s=sit.current(); RefList<Symbol> outs=untranslate_var(s, callee, caller, callsite); if (outs.entries()!=1){ delete range_callee; return make_pair((RangeExpr*)0, false); } Symbol& s_callee=outs[0]; Symbol* sgsa_callee=last_gsa_symbol(callee, s_callee); substitute_var(*range_callee, s, *sgsa_callee); } return make_pair((RangeExpr*)range_callee, range.second); } static Symbol* symgsa_callee(Symbol& sym, ProgramUnit& callee, ProgramUnit& caller, Statement& callsite){ RefList<Symbol> outs=untranslate_var((VariableSymbol&)sym, callee, caller, callsite); if (outs.entries()!=1){ return 0; } Symbol& sym_callee=outs[0]; return last_gsa_symbol(callee, sym_callee); } /*! \brief Finds the full backwards trace. \warning Will consume 'range.first'. */ void eg_backtrack(ProgramUnit& pgm, Symbol& sym, pair<RangeExpr*, bool> range, BackTrace& trace){ /// First find the VEG where 'sym' is defined. Statement* loop=0; DefLoc* defloc=pgm.gsa_deflocs_guarded().find_ref(sym); if (defloc->stmt_valid()) { Statement& def=defloc->stmt_guarded(); if (def.stmt_class()==DO_STMT){ return; } loop=def.outer_ref(); } EvolutionGraph* veg=_get_eg(&pgm, loop); /// Find the trace at this level. list<Symbol*> basic_trace; cerr<<"\nCalling veg::backtrack: "; _print_range(sym.name_ref(), range); veg->backtrack(&sym, range, basic_trace); if (basic_trace.size()==0){ basic_trace.push_back(&sym); } cerr<<"\nBasic trace: "; /// Copy the trace information in multi-level format. for(list<Symbol*>::iterator it=basic_trace.begin(); it!=basic_trace.end(); ++it){ TraceSite ts; cerr<<"\t"<<(*it)->name_ref(); ts.sym=*it; ts.inner=0; trace.push_back(ts); } /// Extend the trace to inner levels. if (trace.size()==1){ /// ... This can only be useful if we are at a callsite. /// ... Check for call sites; Statement* cs=callsite(pgm, *(*trace.begin()).sym); if (cs){ BackTrace::iterator btit=trace.begin(); ProgramUnit* callee=called_pgm(*cs); Symbol* csym=symgsa_callee(*(*btit).sym, *callee, pgm, *cs); pair<RangeExpr*, bool> range_callee= _translate_range(range, *callee, pgm, *cs); if (csym==0 || range_callee.first==0){ delete range.first; return; } InnerTrace* inner=new InnerTrace; eg_backtrack(*callee, *csym, range_callee, inner->trace); delete range.first; if (inner->trace.size()>0){ (*btit).inner=inner; (*btit).inner->context=make_pair(&pgm, cs); (*btit).inner->type=LTT_UNKNOWN; } else { delete inner; trace.clear(); } return; } else { trace.clear(); delete range.first; return; } } BackTrace::iterator btit=trace.begin(); Symbol* current=(*btit).sym; ++btit; Statement* inner_loop=is_mu_sym(*current, pgm); if (inner_loop){ if (inner_loop==loop){ p_abort("'backtrack' on a MU symbol is undefined."); } } Symbol* last=current; do { current=(*btit).sym; /// cerr<<"\nCurrent = "<<current->name_ref(); /// cerr<<", last = "<<last->name_ref(); range=subtract_evolution(range, get_evolution(*veg, current, last)); /// ... Check for MU symbol. inner_loop=is_mu_sym(*current, pgm); if (inner_loop){ if (inner_loop!=loop){ /// cerr<<"\n\tInner loop: "<<inner_loop->get_loop_name(); InnerTrace* inner=new InnerTrace; pair<RangeExpr*, bool> copy=range; copy.first=(RangeExpr*)copy.first->clone(); eg_backtrack(pgm, get_back_sym(*current, pgm), copy, inner->trace); if (inner->trace.size()>0){ (*btit).inner=inner; (*btit).inner->context=make_pair(&pgm, inner_loop); (*btit).inner->type=LTT_UNKNOWN; } else { delete inner; } } else { /// ... Got to the MU in this loop. /// ... Extend the trace to the outer level. p_warning("Outer loops not implemented."); } } else { /// ... Check for call sites; Statement* cs=callsite(pgm, *current); if (cs){ cerr<<"\nAt callsite: "<<*cs; p_warning("Call sites not implemented."); } } last=current; ++btit; } while(btit!=trace.end()); if (range.first){ delete range.first; } }

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