Polaris: EvolutionGraph.cc Source File

EvolutionGraph.cc Go to the documentation of this file. /// /// #include <queue> #include <algorithm> #include "EvolutionGraph.h" #include "eg_utils.h" #include "utilities/stmt_util.h" #include "ip_ssa/prog_info.h" #include "ip_ssa/trans_util.h" #include "ip_ssa/ip_ssa.h" #include "ip_ssa/optimize_ssa.h" #include "BackTrace.h" //////////////////////////////////////////////////////////////////////////// /// BEGIN local constants and simple defs. //////////////////////////////////////////////////////////////////////////// static Symbol* ZERO=0; inline const char* node_name(const Symbol* s){ if (s){ return s->name_ref(); } else { return "ZERO"; } } inline Expression* node_value(const Symbol* s){ if (s){ return id(*s); } else { return constant(0); } } inline String loop_name(Statement* loop){ if (loop){ String l=loop->get_loop_name(); for(int i=0; i<l.len(); i++){ if (l[i]=='#'){ l[i]='_'; } } return l; } else { return String("ROOT"); } } /// Find the incoming value for given mu symbol. static void get_imu(const Symbol& mu, ProgramUnit& pgm, Symbol*& imu, bool& is_defined){ imu=0; is_defined=false; DefLoc* defloc=pgm.gsa_deflocs_guarded().find_ref(mu); if (!defloc->stmt_valid()) { cerr<<"\nFor MU sym. "<<mu.name_ref(); p_abort("Cannot find MU definition site."); } Statement& def=defloc->stmt_guarded(); if (def.stmt_class()==ASSIGNMENT_STMT){ imu=&def.rhs().parameters_guarded().arg_list()[0].symbol(); if (gsa_base(*imu)!=imu){ is_defined=true; } else { /// ... Formals and commons may be defined for subprograms other /// ... than the main one. /// ... silvius: We assume here that the 'remove_data_statements' filter /// ... was run previously. if (find_main_pgm(program())!=&pgm){ if (imu->formal() || imu->common_ref()){ is_defined=true; } } } } } //////////////////////////////////////////////////////////////////////////// /// END local constants and simple defs. //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// /// BEGIN EG repository management. //////////////////////////////////////////////////////////////////////////// static map<ProgramUnit*, map<Statement*, EvolutionGraph*> > _egs; static void _add_eg(ProgramUnit* pgm, Statement* loop, EvolutionGraph* eg){ EvolutionGraph*& current=_egs[pgm][loop]; if (current){ delete current; } current=eg; } static void _remove_eg(ProgramUnit* pgm, Statement* loop){ map<ProgramUnit*, map<Statement*,EvolutionGraph*> >::iterator found_pgm= _egs.find(pgm); if (found_pgm!=_egs.end()){ map<Statement*,EvolutionGraph*>::iterator found_loop= (*found_pgm).second.find(loop); if (found_loop!=(*found_pgm).second.end()){ delete (*found_loop).second; (*found_pgm).second.erase(found_loop); } } } static void _remove_egs(ProgramUnit* pgm){ if (pgm==0){ /// ... Remove all. map<ProgramUnit*, map<Statement*,EvolutionGraph*> >::iterator found_pgm= _egs.begin(); for(; found_pgm!=_egs.end(); ++found_pgm){ map<Statement*,EvolutionGraph*>::iterator found_loop= (*found_pgm).second.begin(); for(; found_loop!=(*found_pgm).second.end(); ++found_loop){ delete (*found_loop).second; } } _egs.clear(); } else { map<ProgramUnit*, map<Statement*,EvolutionGraph*> >::iterator found_pgm= _egs.find(pgm); if (found_pgm!=_egs.end()){ map<Statement*,EvolutionGraph*>::iterator found_loop= (*found_pgm).second.begin(); for(; found_loop!=(*found_pgm).second.end(); ++found_loop){ delete (*found_loop).second; } _egs.erase(found_pgm); } } } void remove_egs(ProgramUnit& pgm){ _remove_egs(&pgm); } EvolutionGraph* _get_eg(ProgramUnit* pgm, Statement* loop){ map<ProgramUnit*, map<Statement*,EvolutionGraph*> >::iterator found_pgm= _egs.find(pgm); if (found_pgm!=_egs.end()){ map<Statement*,EvolutionGraph*>::iterator found_loop= (*found_pgm).second.find(loop); if (found_loop!=(*found_pgm).second.end()){ EvolutionGraph* toret=(*found_loop).second; p_assert(toret, "'_get_eg' failed."); return toret; } else { p_assert(pgm, "Null pgm pointer."); EvolutionGraph* veg=new EvolutionGraph(*pgm, loop); EvolutionGraph* toret=_egs[pgm][loop]=veg; p_assert(toret, "'_get_eg' failed."); return toret; } } else { p_assert(pgm, "Null pgm pointer."); EvolutionGraph* veg=new EvolutionGraph(*pgm, loop); EvolutionGraph* toret=_egs[pgm][loop]=veg; p_assert(toret, "'_get_eg' failed."); return toret; } } //////////////////////////////////////////////////////////////////////////// /// END EG repository management. //////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////// /// BEGIN Shortest path computation. ////////////////////////////////////////////////////////////////////////// bool EvolutionGraph::_relax(unsigned int nleft, unsigned int nright, const EdgeType& ev, RELAX_OP op, vector<Expression*>& best_path){ /// First check whether there is a path to nleft. Otherwise we will not /// perform the relaxation in order to avoid operations like (-Inf + Inf). Expression* best_left=best_path[nleft]; Expression* best_right=best_path[nright]; if (best_left->op()==INFINITY_OP){ if (op==MAX_OP && best_left->sign()==-1){ return false; } if (op==MIN_OP && best_left->sign()==1){ return false; } } /// Get range information. const Symbol& sym=*nodes()[nright]; Statement* stmt=0; DefLoc* defloc=_pgm->gsa_deflocs_guarded().find_ref(sym); if (defloc){ if (defloc->stmt_valid()){ Statement& def=defloc->stmt_guarded(); if (def.stmt_class()==DO_STMT){ stmt=&def; } } } if (!stmt){ stmt=_pgm->stmts().last_ref(); } RangeAccessor ra(_pgm->range_dict_guarded(), *range_stmt(*stmt)); /// At this time we have best_left, best_right, and weight. bool has_relaxed=false; /// ... Path through nleft is better. bool has_not_relaxed=false; /// ... Previous path is better. /// has_relaxed==false && has_not_relaxed==false => cannot compare. Expression* path_with_edge=0; Expression* conservative_best=0; switch(op){ case MIN_OP: path_with_edge=simplify(add(best_left->clone(), ev.min_difference()->clone())); has_relaxed=::p_less_than(*path_with_edge, *best_right, &ra); if (!has_relaxed){ has_not_relaxed=::p_less_equal(*best_right, *path_with_edge, &ra); } break; case MAX_OP: path_with_edge=simplify(add(best_left->clone(), ev.max_difference()->clone())); has_relaxed=::p_greater_than(*path_with_edge, *best_right, &ra); if (!has_relaxed){ has_not_relaxed=::p_greater_equal(*best_right, *path_with_edge, &ra); } break; default: p_abort("Unknown operator in relaxation."); } if (has_relaxed){ /// ... Did relax. delete best_path[nright]; best_path[nright]=path_with_edge; return true; } else { if (has_not_relaxed){ /// ... Did not relax. delete path_with_edge; return false; } else { /// ... We cannot tell which is shorter, will take the best. conservative_best=make_best(*best_right, *path_with_edge, op, *_pgm); delete path_with_edge; delete best_path[nright]; best_path[nright]=conservative_best; return true; } } } void EvolutionGraph::_bellman_ford(unsigned int source, vector<Evolution<Expression> >& best, vector<unsigned int>& topsorted, bool forward){ /// Clear result list just in case. best.clear(); /// Initialize shortest/longest path for every destination node. vector<Expression*> shortest_path(nodes().size(), 0); vector<Expression*> longest_path(nodes().size(), 0); for(unsigned int cn=0; cn!=nodes().size(); ++cn){ if (cn==source){ shortest_path[cn]=constant(0); longest_path[cn]=constant(0); } else { shortest_path[cn]=infinity(); longest_path[cn]=infinity(-1); } } /// Now chew it up. for (unsigned int i=0; i<topsorted.size(); ++i){ unsigned int ifirst=topsorted[i]; const EdgeList* pedges; if (forward){ pedges=&get_edges(ifirst); } else { pedges=&get_reversed_edges(ifirst); } /// ... For each incident edge. for (EdgeList::const_iterator cit=pedges->begin(); cit!=pedges->end(); ++cit){ unsigned int isecond=(*cit).first; /// ... Relaxation. _relax(ifirst, isecond, (*cit).second, MIN_OP, shortest_path); _relax(ifirst, isecond, (*cit).second, MAX_OP, longest_path); } } /// Save result. for (unsigned int i=0; i<topsorted.size(); ++i){ best.push_back(evolution(shortest_path[i], longest_path[i])); } /// Sanity check. p_assert(best.size()==nodes().size(), "Wrong output from bellman_ford."); } ////////////////////////////////////////////////////////////////////////// /// END Shortest path computation. ////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////// /// BEGIN Topology Information and Transformation. ////////////////////////////////////////////////////////////////////////// bool EvolutionGraph::_back_edge(const Symbol* left, const Symbol* right){ /// Check for loop index. if (_loop){ if (left==right){ if (left==&_loop->index().symbol()){ return true; } } } /// General. map<const Symbol*, const Symbol*>::iterator beit=_back_edges.find(left); if (beit!=_back_edges.end()){ if ((*beit).second==right){ return true; } } return false; } void EvolutionGraph::_topsort(vector<unsigned int>& topsorted, bool forward){ topsorted.clear(); /// First compute the in-degrees for every node. map<unsigned int, unsigned int> indegrees; for (unsigned int left=0; left<nodes().size(); ++left){ indegrees.insert(make_pair(left, 0)); } for (unsigned int left=0; left<nodes().size(); ++left){ const EdgeList* pedges; if (forward){ pedges=&get_edges(left); } else { pedges=&get_reversed_edges(left); } /// ... For each outgoing edge. for (EdgeList::const_iterator cit=pedges->begin(); cit!=pedges->end(); ++cit){ unsigned int right=(*cit).first; if (forward){ if (_back_edge(nodes()[left], nodes()[right])){ // Skip back edge. continue; } } else { if (_back_edge(nodes()[right], nodes()[left])){ // Skip back edge. continue; } } indegrees[right]++; } } /// Now start at root nodes and add nodes to 'topsort' as they are available. /// Use indegrees as consumable dependency DAG. queue<unsigned int> ready; for (unsigned int left=0; left<nodes().size(); ++left){ if(indegrees[left]==0){ ready.push(left); } } while (ready.size()>0){ unsigned int left=ready.front(); topsorted.push_back(left); ready.pop(); const EdgeList* pedges; if (forward){ pedges=&get_edges(left); } else { pedges=&get_reversed_edges(left); } /// ... For each outgoing edge. for (EdgeList::const_iterator cit=pedges->begin(); cit!=pedges->end(); ++cit){ unsigned int right=(*cit).first; if (forward){ if (_back_edge(nodes()[left], nodes()[right])){ // Skip back edge. continue; } } else { if (_back_edge(nodes()[right], nodes()[left])){ // Skip back edge. continue; } } (*indegrees.find(right)).second--; if ((*indegrees.find(right)).second==0){ ready.push(right); } } } /// Sanity check. if(topsorted.size()!=nodes().size()){ p_abort("Error in topsort."); } } static void print_evolutions(map<const Symbol*, map<const Symbol*, Evolution<Expression> > >& evs, const char* type, ostream& o){ o<<"\n\nEvolutions ("<<type<<"):"; map<const Symbol*, map<const Symbol*, Evolution<Expression> > >::iterator allit; for(allit=evs.begin(); allit!=evs.end(); ++allit){ o<<"\n\tDestination = "<<node_name((*allit).first); map<const Symbol*, Evolution<Expression> >::iterator it; for(it=(*allit).second.begin(); it!=(*allit).second.end(); ++it){ o<<"\n\t\tSource = "<<node_name((*it).first) <<", Evolution = "<<(*it).second; } } } static void print_input_values(map<const Symbol*, Evolution<Expression> >& ivs, const char* type, ostream& o){ o<<"\n\nInput values ("<<type<<"):"; map<const Symbol*, Evolution<Expression> >::iterator allit; for(allit=ivs.begin(); allit!=ivs.end(); ++allit){ o<<"\n\tDestination = "<<node_name((*allit).first) <<", Value = "<<(*allit).second; } } Expression* _eg_forward_substitute(EvolutionGraph* eg, ProgramUnit& pgm, DoStmt* loop, Expression* expr){ 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 void remove_source(EvolutionGraph::EvolutionMap& em, Symbol* source){ EvolutionGraph::EvolutionMap::iterator it; vector<EvolutionGraph::EvolutionMap::iterator> todel; for(it=em.begin(); it!=em.end(); ++it){ map<const Symbol*, Evolution<Expression> >::iterator found= (*it).second.find(source); if (found!=(*it).second.end()){ (*it).second.erase(found); } if ((*it).second.size()==0){ /// ... Erased them all. todel.push_back(it); } } for(vector<EvolutionGraph::EvolutionMap::iterator>::iterator vit=todel.begin(); vit!=todel.end(); ++vit){ em.erase(*vit); } } /*! \brief Add approximations for evolutions of this type: var1 = var2 + var3 At this point, we have set the value of var1 as [-Inf:Inf]. In case we know the range for var3, add an evolution from var2 to var1 with value range(var3). Same goes for when we know the range of the expression (var2 + var3). */ bool EvolutionGraph::_add_approximations(){ /// if (_loop){ /// cerr<<"\nEnter add_approx for "<<loop_name(_loop); /// } bool toret=false; Statement* first=0; Statement* last=0; if (_loop){ first=_loop->next_ref(); last=_loop->follow_ref(); } else { first=_pgm->stmts().first_ref(); last=_pgm->stmts().last_ref(); } for(Statement* stit=first; stit!=last; stit=stit->next_ref()){ if (stit->stmt_class()!=ASSIGNMENT_STMT) { if (stit->stmt_class()==DO_STMT || stit->stmt_class()==WHILE_STMT){ stit=stit->follow_ref(); } else { if (stit->stmt_class()==IF_STMT){ stit=stit->matching_endif_ref(); } } continue; } if (stit->lhs().op()!=ID_OP) continue; if (stit->lhs().type().data_type()!=INTEGER_TYPE) continue; if (stit->rhs().op()!=ADD_OP) continue; Symbol* to=&stit->lhs().symbol(); List<Expression>& args=stit->rhs().arg_list(); if (args.first_ref()->op()==ID_OP && args.last_ref()->op()==ID_OP){ /// cerr<<"\n\nrhs: "<<stit->rhs(); /// cerr<<"\n\tto = "<<to->name_ref(); /// ... They are both loop variants. Will pick one that we can get a /// ... range for and replace it with the range. const Symbol& first=args.first_ref()->symbol(); const Symbol& second=args.last_ref()->symbol(); /// ... Since we have not built the VEG yet, the best chance is that /// ... one of them is produced in a subroutine or inner loop. Expression* lr=0; if (contains((Symbol*)&first) && contains((Symbol*)&second)){ /// ... They are both defined here. /// ... Get range for 'second'. lr=_local_range(second); /// cerr<<"\n\tlr = "<<*lr; /// ... Make sure it is nontrivial. if (lr->op()==RANGE_OP){ if (((RangeExpr*)lr)->lb().op()==INFINITY_OP && ((RangeExpr*)lr)->ub().op()==INFINITY_OP){ delete lr; continue; } } /// ... Remove the input value of [-Inf:Inf] from 'to'. map<const Symbol*, Evolution<Expression> >::iterator found= _input_values.find(to); if (found!=_input_values.end()){ Evolution<Expression> ev=(*found).second; if (ev.min_difference()->op()!=INFINITY_OP || ev.max_difference()->op()!=INFINITY_OP){ p_abort("Bad logic."); } else { /// ... OK, add it. /// cerr<<"\n\tAdding evolution "<<*lr<<" from "<<first.name_ref() /// <<" to "<<to->name_ref(); _add_evolution(&first, to, evolution(lr)); /// cerr<<"\n\tErased iv."; _input_values.erase(found); input_this_loop.erase(index(to)); toret=true; } } else { // We must have seen it in a previous iteration of // compute_acyclic + add_approximations. } } } else { /// ... Look for var1 = var2 + (-1)*var3 if (args.first_ref()->op()==ID_OP && args.last_ref()->op()==MULT_OP){ List<Expression>& args3=args.last_ref()->arg_list(); if (args3.entries()==2){ if (args3.first_ref()->op()==INTEGER_CONSTANT_OP){ if (args3.first_ref()->value()==-1){ Expression* e1=_eg_forward_substitute(this, *_pgm, (DoStmt*)_loop, args.first_ref()->clone()); Expression* e2=_eg_forward_substitute(this, *_pgm, (DoStmt*)_loop, args3.last_ref()->clone()); if (e1->op()==ID_OP && e2->op()==ID_OP){ /// ... See if we can find the minimum distance between them. unsigned int source=index(&e1->symbol()); vector<Evolution<Expression> > evs; vector<unsigned int> topsorted; _topsort(topsorted, true); _bellman_ford(source, evs, topsorted, true); Evolution<Expression>& ev=evs[index(&e2->symbol())]; delete e1; delete e2; EXPR_SIGN s=_ra->sign(*ev.min_difference()); if (s==POS_EXPR){ /// cerr<<"\n\tBINGO."; map<const Symbol*, Evolution<Expression> >::iterator found= _input_values.find(to); if (found!=_input_values.end()){ Evolution<Expression> ev=(*found).second; if (ev.min_difference()->op()==INFINITY_OP || ev.max_difference()->op()==INFINITY_OP){ _input_values[to]=evolution(constant(0), infinity()); toret=true; } } } } } } } } } } return toret; } void EvolutionGraph::_build(){ /// cerr<<"\nGenerating EG for "<<_pgm->routine_name_ref() /// <<" and loop "<<loop_name(_loop); /// _pgm->write(cerr); /// Mark domain. Statement* first=0; Statement* last=0; if (_loop){ first=_loop->next_ref(); last=_loop->follow_ref(); } else { first=_pgm->stmts().first_ref(); last=_pgm->stmts().last_ref(); } /// Add nodes. /// Add integer scalars and arrays only. if (_loop){ Symbol* ind=&_loop->index().symbol(); add_node(ind); } Statement* stit=first; while(stit!=0 && stit!=last){ if (stit->stmt_class()==ASSIGNMENT_STMT){ if (stit->rhs().op()==FUNCTION_CALL_OP){ Symbol* sym=stit->lhs().base_variable_ref(); if (sym->is_scalar()){ if (sym->type().data_type()==INTEGER_TYPE){ add_node(sym); } } } } if (stit->stmt_class()==DO_STMT){ /// ... Add only MU values for inner DO stmts. add_node(&stit->index().symbol()); Statement* mudef=stit->next_ref(); while (mudef){ if (mudef->stmt_class()!=ASSIGNMENT_STMT){ break; } if (mudef->rhs().op()!=MU_OP){ break; } Symbol* sym=&mudef->lhs().symbol(); if (sym->is_scalar()){ if (sym->type().data_type()==INTEGER_TYPE){ add_node(sym); } } mudef=mudef->next_ref(); } stit=stit->follow_ref()->next_ref(); } else { /// cerr<<"\nAt statement: "<<*stit; for(Iterator<Expression> eit=stit->out_refs(); eit.valid(); ++eit){ Symbol* sym=eit.current().base_variable_ref(); if (sym){ if (sym->is_scalar()){ if (sym->type().data_type()==INTEGER_TYPE){ /// ... If this is a call site, do not add the ones that will not /// ... be modified based on MAYMODs. if (has_maymod(*stit)){ if (!is_var_in_maymod(*gsa_base(*sym), *stit)){ /// ... Not modified. continue; } } /// cerr<<"\n\tAdding "<<node_name(sym); add_node(sym); } } } } stit=stit->next_ref(); } } /// If it is the whole program unit, add base gsa symbols for all commons /// and formals that may be defined in this subprogram. /// silvius: actually, add them all even if they are not defined because /// they may carry values in. if (_loop==0){ for(DictionaryIter<Symbol> sit=_pgm->symtab().iterator(); sit.valid(); ++sit){ Symbol* base=gsa_base(sit.current()); if (base){ if (base->formal() || base->common_ref()){ if (base->is_scalar() && base->type().data_type()==INTEGER_TYPE){ add_node(base); } } } } } /// Set mu nodes. if (_loop){ /// ... Find MU nodes defined in this loop. for(vector<Symbol*>::const_iterator it=nodes().begin(); it!=nodes().end(); ++it){ if (loop(**it, *_pgm)==_loop){ unsigned int imu=index((Symbol*)*it); mu_this_loop.insert(imu); } } } else { /// cerr<<"\n\nIn routine "<<_pgm->routine_name_ref(); /// ... Set as MU all symbols that may carry a definition outside the routine. for(vector<Symbol*>::const_iterator it=nodes().begin(); it!=nodes().end(); ++it){ if ((*it)->formal() || (*it)->common_ref()){ if (gsa_base(**it)==*it){ /// cerr<<"\n\tAdding mu node "<<(*it)->name_ref(); unsigned int imu=index((Symbol*)gsa_base(**it)); /// cerr<<" with index value "<<imu; mu_this_loop.insert(imu); } } } } /// Add back edges. if (_loop){ Symbol* ind=&_loop->index().symbol(); _back_edges.insert(make_pair(ind, ind)); _back_edges_reversed.insert(make_pair(ind, ind)); back_this_loop.insert(index(ind)); for(Statement* ps=first; ps && ps!=last; ps=ps->next_ref()){ if (ps->stmt_class()!=ASSIGNMENT_STMT) break; if (ps->rhs().op()!=MU_OP) break; if (ps->lhs().type().data_type()!=INTEGER_TYPE) continue; if (!ps->lhs().symbol().is_scalar()) continue; Symbol* to=&ps->lhs().symbol(); Symbol& besym=ps->rhs().parameters_guarded().arg_list()[1].symbol(); _back_edges.insert(make_pair(&besym, to)); _back_edges_reversed.insert(make_pair(to, &besym)); unsigned int back=index(&besym); back_this_loop.insert(back); } } else { for(set<unsigned int>::iterator def_it=mu_this_loop.begin(); def_it!=mu_this_loop.end(); ++def_it){ unsigned int incoming=*def_it; Symbol* outgoing_sym=last_gsa_symbol(*_pgm, *nodes()[incoming]); if (outgoing_sym){ /// cerr<<"\n\tAdding back edge from "; /// cerr<<node_name(outgoing_sym)<<" to "; /// cerr<<node_name(nodes()[incoming])<<endl; unsigned int outgoing=index(outgoing_sym); _back_edges.insert(make_pair(outgoing_sym, nodes()[incoming])); _back_edges_reversed.insert(make_pair(nodes()[incoming], outgoing_sym)); back_this_loop.insert(outgoing); /// cerr<<"\n\tAdding back node "<<outgoing_sym->name_ref(); } } } /// Add evolutions. _add_evolutions(*first, *last); /// Store indices of all nodes. for(vector<Symbol*>::const_iterator it=nodes().begin(); it!=nodes().end(); ++it){ unsigned int ind=index((Symbol*)*it); nodes_this_loop.insert(ind); } /// Set as input all nodes that have an input value AND are not MU. for(vector<Symbol*>::const_iterator it=nodes().begin(); it!=nodes().end(); ++it){ if (_input_values.find(*it)!=_input_values.end()){ unsigned int iin=index((Symbol*)*it); if (mu_this_loop.find(iin)==mu_this_loop.end()){ input_this_loop.insert(iin); } } } do { /// ... Compute evolutions. _compute_acyclic_evolutions(); /// ... Add approximations. if (!_add_approximations()){ break; } else { /// ... We have to recompute. _mu_evolutions.clear(); _evolutions_from_mu.clear(); _input2mu_evolutions.clear(); _evolutions_from_input.clear(); _evolutions_to_mu.clear(); } } while(1); /// Draw the graph. String cmd="mkdir -p ./.polaris/pgm_sources/"; system(cmd); String gname=".polaris/pgm_sources/"; if (_loop){ gname+=_loop->get_loop_name(); } else { gname+=_pgm->routine_name_ref(); } gname+=".dot"; print_graph(gname); } void EvolutionGraph::_add_evolutions(const Expression& rhs, const Symbol* to){ /// If rhs is loop invariant, then no evolution is added, but the node must /// be marked as input. if (_loop){ if (_loop_invariant(rhs)){ /// cerr<<"\n1. in loop "<<loop_name(_loop) /// <<", set input value for "<<to->name_ref()<<" to "<<rhs; _input_values[to]=evolution(rhs); return; } } else { if (rhs.op()==INTEGER_CONSTANT_OP){ _input_values[to]=evolution(rhs); return; } } /// If rhs contains any loop variants that are not scalar integers, then /// this node is marked as input with an initial value of Infinity. if (rhs.op()!=MU_OP && rhs.op()!=GAMMA_OP && rhs.op()!=ETA_OP && rhs.op()!=THETA_OP){ if (_contains_unknown_variants(rhs)){ _input_values[to]=evolution(); /// cerr<<"\n\tIS UNKNOWN"; return; } } /// When it gets here: /// 1. All symbols in rhs are either loop invariant or evgraph nodes. /// 2. There is at least an evgraph node in rhs. const Symbol* from=ZERO; switch(rhs.op()){ case ID_OP: /// ... Check for special case: x = i if (_loop){ if (&rhs.symbol()==&_loop->index().symbol()){ /// ... silvius: assume the loop has been normalized. /// _input_values[to]=evolution(_loop->init(), _loop->limit()); _add_evolution(&_loop->index().symbol(), to, evolution(0)); break; } } /// ... 0 edge. from=&rhs.symbol(); /// cerr<<"\n to = "<<to->name_ref()<<", rhs = "<<rhs; _add_evolution(from, to, evolution(0)); break; case MU_OP: /// ... Skip back edge. Input value is considered only when we compute /// ... the aggregated cyclic evolutions. break; case ETA_OP: /// cerr<<"\neta gate: "<<rhs; if (is_true(rhs.gate())){ _add_evolution(&rhs.parameters_guarded().arg_list()[0].symbol(), to, evolution(0)); break; } else { if (is_logical_false(rhs.gate())){ _add_evolution(&rhs.parameters_guarded().arg_list()[1].symbol(), to, evolution(0)); } else { /// ... Let it be treated as a regular PHI node. } } case GAMMA_OP: case THETA_OP: { /// ... 0 edges. RefList<Symbol> entries; get_phinode_entries(rhs, entries); /// cerr<<"\n\tto = "<<node_name(to) /// <<", rhs = "<<rhs /// <<", phi entries = "<<entries; Iterator<Symbol> sit=entries; for( ; sit.valid(); ++sit){ /// if (gsa_base(sit.current())!=&sit.current()){ _add_evolution(&sit.current(), to, evolution(0)); /// } } break; } case ADD_OP: { const List<Expression>& args=rhs.arg_list(); if (args.entries()==2){ if (args.first_ref()->op()==ID_OP && args.last_ref()->op()==INTEGER_CONSTANT_OP){ from=&args.first_ref()->symbol(); int add_offset=args.last_ref()->value(); _add_evolution(from, to, evolution(add_offset)); break; } if (args.last_ref()->op()==ID_OP && args.first_ref()->op()==INTEGER_CONSTANT_OP){ from=&args.last_ref()->symbol(); int add_offset=args.first_ref()->value(); _add_evolution(from, to, evolution(add_offset)); break; } /// ... For x = y + exp, add y -> x. if (args.first_ref()->op()==ID_OP){ from=&args.first_ref()->symbol(); if (contains((Symbol*)from)){ if (_loop){ if (_loop_invariant(*args.last_ref())){ _add_evolution(from, to, evolution(*args.last_ref())); break; } } else { if (args.last_ref()->op()==INTEGER_CONSTANT_OP){ _add_evolution(from, to, evolution(*args.last_ref())); break; } } } } if (args.last_ref()->op()==ID_OP){ from=&args.last_ref()->symbol(); if (contains((Symbol*)from)){ if (_loop){ if (_loop_invariant(*args.first_ref())){ _add_evolution(from, to, evolution(*args.first_ref())); break; } } else { if (args.last_ref()->op()==INTEGER_CONSTANT_OP){ _add_evolution(from, to, evolution(*args.first_ref())); break; } } } } } /// ... If it gets here, we could not analyze it well. /// cerr<<"\n2. in loop "<<loop_name(_loop) /// <<", set input value for "<<to->name_ref()<<" to "<<rhs; _input_values[to]=evolution(); break; } case SUB_OP: { const List<Expression>& args=rhs.arg_list(); if (args.first_ref()->op()==ID_OP && args.last_ref()->op()==INTEGER_CONSTANT_OP){ from=&args.first_ref()->symbol(); int add_offset=-args.last_ref()->value(); _add_evolution(from, to, evolution(add_offset)); break; } /// ... For x = y - exp, add y -> x. if (args.first_ref()->op()==ID_OP){ from=&args.first_ref()->symbol(); if (contains((Symbol*)from)){ if (_loop_invariant(*args.last_ref())){ Expression* neg=simplify(mul(constant(-1), args.last_ref()->clone())); _add_evolution(from, to, evolution(neg)); break; } } } /// ... If it gets here, we could not analyze it well. _input_values[to]=evolution(); break; } default: /// ... Unknown. _input_values[to]=evolution(); } } void EvolutionGraph::_add_evolution(const Symbol* from, const Symbol* to, const Evolution<Expression>& ev){ /// cerr<<"\nAdd evolution from "<<from->name_ref() /// <<" to "<<to->name_ref(); if (!contains((Symbol*)to)){ p_abort("Destination node not in graph."); } if (!contains((Symbol*)from)){ /// cerr<<"\n\n\tBOO!"; return; } add_edge((Symbol*)from, (Symbol*)to, ev); } bool EvolutionGraph::_loop_invariant(const Expression& expr){ RefList<Symbol> syms; referred_symbols(expr, syms); for(Iterator<Symbol> sit=syms; sit.valid(); ++sit){ Symbol& s=sit.current(); if (loop_variant(s, _loop, *_pgm)){ return false; } } return true; } /// Returns whether given expression contains at least one symbol /// that is loop variant and is not scalar or is not integer. bool EvolutionGraph::_contains_unknown_variants(const Expression& expr){ RefList<Symbol> syms; referred_symbols(expr, syms); for(Iterator<Symbol> sit=syms; sit.valid(); ++sit){ Symbol& s=sit.current(); bool unknown=false; if (!s.is_scalar()){ unknown=true; } else { if (s.type().data_type()!=INTEGER_TYPE) { unknown=true; } } if (unknown){ if (_loop){ if (loop_variant(s, _loop, *_pgm)){ return true; } } else { return true; } } } return false; } /*! \brief Add evolutions from inner loop. */ void EvolutionGraph::_add_evolutions(DoStmt& loop){ /// Get graph for inner loop. EvolutionGraph* egloop=_get_eg(_pgm, &loop); /// Get overall evolutions for the inner loop. EvolutionMap inner_evs; map<const Symbol*, Evolution<Expression> > inner_ivs; egloop->_compute_cyclic_evolutions(inner_evs, inner_ivs); /// cerr<<"\ninner_ivs: "; /// print_input_values(inner_ivs, "", cerr); /// Copy evolutions to outer domain. for(EvolutionMap::iterator it=inner_evs.begin(); it!=inner_evs.end(); ++it){ const Symbol* inner_mu_input=(*it).first; for(map<const Symbol*, Evolution<Expression> >::iterator it2= (*it).second.begin(); it2!=(*it).second.end(); ++it2){ const Symbol* inner_mu=(*it2).first; _add_evolution(inner_mu_input, inner_mu, (*it2).second); } } /// Add input relations. for(map<const Symbol*, Evolution<Expression> >::iterator it= inner_ivs.begin(); it!=inner_ivs.end(); ++it){ _input_values[(*it).first]=(*it).second; } } /*! \brief Add evolutions from given assignment. */ void EvolutionGraph::_add_evolutions(AssignmentStmt& stmt){ Expression& lhs=stmt.lhs(); Expression& rhs=stmt.rhs(); /// cerr<<"\n\nlhs="<<lhs<<", rhs="<<rhs; Symbol* to=0; if (lhs.op()==ID_OP){ if (lhs.symbol().type().data_type()==INTEGER_TYPE){ to=&lhs.symbol(); } } if (to){ if (to->is_scalar()){ _add_evolutions(rhs, to); } } } inline Evolution<Expression> get_translated_evolution(Translator& trans, ProgramUnit& caller, ProgramUnit& callee, Statement& callsite, Evolution<Expression>& original){ Expression* mind=original.min_difference()->clone(); Expression* maxd=original.max_difference()->clone(); if (can_translate(*mind, trans, callee, caller, callsite)){ mind=translate_and_reshape(trans, callee, caller, callsite, mind); } else { delete mind; mind=infinity(-1); } if (can_translate(*maxd, trans, callee, caller, callsite)){ maxd=translate_and_reshape(trans, callee, caller, callsite, maxd); } else { delete maxd; maxd=infinity(1); } return evolution(mind, maxd); } /*! 1. There is a path from MU to BACK. (T/F) 2. There is a path from INPUT to BACK (T/F) */ void EvolutionGraph::_add_evolutions(Statement& callsite, ProgramUnit& callee){ /// Get graph for called subprogram. EvolutionGraph* egloop=_get_eg(&callee, 0); /// For now, the return value is set to [-Inf:+Inf]. if (callsite.stmt_class()==ASSIGNMENT_STMT){ if (callsite.rhs().op()==FUNCTION_CALL_OP){ Symbol* sym=callsite.lhs().base_variable_ref(); if (sym->is_scalar()){ if (sym->type().data_type()==INTEGER_TYPE){ _input_values[sym]=evolution(); } } } } /// silvius: must check here for a particular case: when a scalar integer /// is passed to a routine that sees it as something else. /// If so, we need to add unknown evolutions for them. /// Forall MU symbols in called routine. for(set<unsigned int>::iterator muit=egloop->mu_this_loop.begin(); muit!=egloop->mu_this_loop.end(); ++muit){ Symbol* mu=egloop->nodes()[*muit]; /// cerr<<"\n\nMU = "<<node_name(mu); /// ... Find corresponding symbol in caller. Expression* actual=translate_var((VariableSymbol&)*mu, callee, *_pgm, callsite); Symbol* actualsym=0; if(actual->op()==ID_OP){ actualsym=&actual->symbol(); if (!actualsym->is_scalar() || !actualsym->type().data_type()==INTEGER_TYPE){ actualsym=0; } } if (actualsym!=0){ /// cerr<<"\nActual = "<<actualsym->name_ref() /// <<" at call site: "<<callsite; } /// if (actualsym==0){ /// /// ... This is just an IN argument, cannot carry an evolution. /// cerr<<"\nStmt: "<<callsite /// <<"\nactual: "<<*actual; /// } EvolutionMap::iterator found_mu2mu=egloop->_mu_evolutions.find(mu); if (found_mu2mu!=egloop->_mu_evolutions.end()){ EvolutionMap::data_type::iterator it=(*found_mu2mu).second.begin(); for( ; it!=(*found_mu2mu).second.end(); ++it){ /// ... There is a path from incoming((*it).first) to outgoing(mu). Translator trans(*_pgm, callsite); Symbol* incoming; Symbol* outgoing; if (actualsym==0){ p_abort("Cannot deal with this translation type yet."); } /// cerr<<"\n\n\npgm = "<<_pgm->routine_name_ref(); /// cerr<<"\ncallsite = "<<callsite; /// cerr<<"\nact = "<<*actualsym; get_out(*_pgm, callsite, *gsa_base(*actualsym), outgoing); Expression* actual_source=translate_var((VariableSymbol&)*(*it).first, callee, *_pgm, callsite); Symbol* actualsym_source=0; if(actual_source->op()==ID_OP){ actualsym_source=&actual_source->symbol(); if (!actualsym_source->is_scalar() || !actualsym_source->type().data_type()==INTEGER_TYPE){ actualsym_source=0; } } if (actualsym_source!=0){ /// cerr<<"\nActual = "<<actualsym->name_ref() /// <<" at call site: "<<callsite; } get_in(*_pgm, callsite, *gsa_base(*actualsym_source), incoming); _add_evolution(incoming, outgoing, get_translated_evolution(trans, *_pgm, callee, callsite, (*it).second)); } } EvolutionMap::iterator found_input2mu= egloop->_input2mu_evolutions.find(mu); if (found_input2mu!=egloop->_input2mu_evolutions.end()){ /// print_evolutions(egloop->_input2mu_evolutions, "I2MU", cerr); /// ... There is a path from an input node to an outgoing. Translator trans(*_pgm, callsite); Symbol* incoming; Symbol* outgoing; if (actualsym==0){ p_abort("Cannot deal with this translation type yet."); } get_in_out(*_pgm, callsite, *gsa_base(*actualsym), incoming, outgoing); /// ... Get first evolution from input. const Symbol* sym=(*egloop->_input2mu_evolutions[mu].begin()).first; Evolution<Expression> ivtotal=egloop->_input_values[sym]; ivtotal+=(*egloop->_input2mu_evolutions[mu].begin()).second; /// ... Merge it with any other evolutions from other input nodes. map<const Symbol*, Evolution<Expression> >::iterator iit; iit=egloop->_input2mu_evolutions[mu].begin(); ++iit; for( ; iit!=egloop->_input2mu_evolutions[mu].end(); ++iit){ const Symbol* sym=(*iit).first; Evolution<Expression> total=egloop->_input_values[sym]; total+=(*iit).second; ivtotal=merge_unite(ivtotal, total, *_pgm, egloop->_ra); } _input_values[outgoing]= get_translated_evolution(trans, *_pgm, callee, callsite, ivtotal); } } } /*! \brief Add evolutions for this loop level. */ void EvolutionGraph::_add_evolutions(Statement& first, Statement& last){ /// Add evolutions. Statement* stit=&first; while(stit!=0 && stit!=&last){ Statement& stmt=*stit; ProgramUnit* callee=called_pgm(stmt); if (callee){ /// ... Call site, must import evolutions from called subprogram. _add_evolutions(stmt, *callee); /// ... Skip THETA assignments, they have been handled by now. stit=stit->next_ref(); while (stit){ if (stit->stmt_class()==ASSIGNMENT_STMT){ if (stit->rhs().op()==THETA_OP){ stit=stit->next_ref(); continue; } } break; } } else { switch(stmt.stmt_class()){ case DO_STMT: _add_evolutions((DoStmt&)stmt); stit=stit->follow_ref()->next_ref(); break; case ASSIGNMENT_STMT: _add_evolutions((AssignmentStmt&)stmt); stit=stit->next_ref(); break; default: /// ... Will add unknown input values for all definitions. for(Iterator<Expression> eit=stmt.out_refs(); eit.valid(); ++eit){ Expression& e=eit.current(); if (e.type().data_type()==INTEGER_TYPE){ Symbol* to=e.base_variable_ref(); if (to){ if (to->is_scalar()){ _input_values[to]=evolution(); } } } } stit=stit->next_ref(); } } /// ... tmp results /// cerr<<*stit<<flush; /// print_graph("eg.dot"); /// system("dot -Tps -o t.ps eg.dot"); /// int tmp; /// cin>>tmp; } } void EvolutionGraph::_verify_preconditions(){ /// Our current preconditions are: /// 1. There is no path between any two different MUs. /// 2. There is at most one INPUT per MU other than its incoming value. for(EvolutionMap::iterator it=_mu_evolutions.begin(); it!=_mu_evolutions.end(); ++it){ const Symbol* mu1=(*it).first; for(map<const Symbol*, Evolution<Expression> >::iterator it2= (*it).second.begin(); it2!=(*it).second.end(); ++it2){ const Symbol* mu2=(*it2).first; if(mu1!=mu2){ /// ... Cross-MU definitions are not supported yet. /// ... Add an UNKNOWN input to this MU. /// ... But first, let us see whether we are in a special case: /// ... Check whether the only way to get values to this MU is /// ... through the coupled recurrence. Symbol* imu; bool imu_is_defined; get_imu(*mu1, *_pgm, imu, imu_is_defined); if (imu==0 || !imu_is_defined){ parasites.insert(index((Symbol*)mu1)); } else { _input_values[mu1]=evolution(); } } } } /// silvius: I don't think this is necessary anymore. /// for(EvolutionMap::iterator it=_input2mu_evolutions.begin(); /// it!=_input2mu_evolutions.end(); ++it){ /// if((*it).second.size()>1){ /// /// ... More than one INPUT may get to a MU. /// cerr<<"\n3. in loop "<<loop_name(_loop) /// <<", set input value for "<<(*it).first->name_ref()<<" to INF"; /// _input_values[(*it).first]=evolution(); /// } /// } } void EvolutionGraph::_compact_zero_paths(){ /// For now, only if they start at ZERO. bool change; do { change=false; unsigned int n=index(ZERO); const EdgeList& edges=get_edges(n); for(EdgeList::const_iterator eit=edges.begin(); eit!=edges.end(); ++eit){ unsigned int t1=(*eit).first; if (loop(*nodes()[t1], *_pgm)==0){ const EdgeList& edges2=get_edges(t1); vector<int> todel; for(EdgeList::const_iterator e2it=edges2.begin(); e2it!=edges2.end(); ++e2it){ unsigned int t2=(*e2it).first; EdgeType final=(*eit).second; final+=(*e2it).second; _add_evolution(nodes()[n], nodes()[t2], final); change=true; } remove_edges(t1); } } } while (change); } /*! \brief Computes all the evolutions for one trip of the given loop for all MU definitions at this loop level. Assumes that all inner loops have been processed. Reads/writes from/to _mu_step. */ void EvolutionGraph::_compute_acyclic_evolutions(){ Symbol* ind=0; if (_loop){ ind=&_loop->index().symbol(); } /// Topsort the nodes. vector<unsigned int> topsorted; _topsort(topsorted, true); /// Find root nodes. set<unsigned int> starters; set_union(mu_this_loop.begin(), mu_this_loop.end(), input_this_loop.begin(), input_this_loop.end(), inserter(starters, starters.begin())); /// print_evolutions(_mu_evolutions, "MU", cerr); /// Chew them up. for(set<unsigned int>::iterator stit=starters.begin(); stit!=starters.end(); ++stit){ unsigned int source=*stit; bool is_mu_node=(mu_this_loop.find(source)!=mu_this_loop.end()); vector<Evolution<Expression> > evs; _bellman_ford(source, evs, topsorted, true); for(set<unsigned int>::iterator it=nodes_this_loop.begin(); it!=nodes_this_loop.end(); ++it){ const Symbol* to=nodes()[*it]; /// ... Check whether 'to' is reachable from 'from' const Expression& md=*evs[*it].min_difference(); if (md.op()==INFINITY_OP){ if (md.sign()==1){ /// ... Unreachable. continue; } } if (is_mu_node){ /// ... MU Node. /// ... Set evolutions from mu. const Symbol* mu_from=nodes()[source]; _evolutions_from_mu[to][mu_from]=evs[*it]; /// ... Set mu evolutions. map<const Symbol*, const Symbol*>::iterator be= _back_edges.find(nodes()[*it]); if (be!=_back_edges.end()){ // Save this evolution as from MU to MU. const Symbol* mu_to=(*be).second; const Symbol* mu_from=nodes()[source]; _mu_evolutions[mu_to][mu_from]=evs[*it]; } } else { /// ... INPUT node. const Symbol* input_from=nodes()[source]; _evolutions_from_input[to][input_from]=evs[*it]; /// ... Set INPUT-to-MU evolutions. map<const Symbol*, const Symbol*>::iterator be= _back_edges.find(nodes()[*it]); if (be!=_back_edges.end()){ // Save this evolution as from INPUT to MU. const Symbol* mu_to=(*be).second; _input2mu_evolutions[mu_to][input_from]=evs[*it]; } } } } if (_loop){ /// ... Manual reset for loop index. /// ... This is needed because our logic would otherwise detect a zero-length /// ... pass between 'ind' and 'ind' and overwrite the real step. _mu_evolutions[ind][ind]=evolution(_loop->step()); } /// Now build _evolutions_to_mu. topsorted.clear(); _topsort(topsorted, false); for(set<unsigned int>::iterator stit=back_this_loop.begin(); stit!=back_this_loop.end(); ++stit){ unsigned int source=*stit; vector<Evolution<Expression> > evs; _bellman_ford(source, evs, topsorted, false); for(set<unsigned int>::iterator it=nodes_this_loop.begin(); it!=nodes_this_loop.end(); ++it){ const Symbol* to=nodes()[*it]; /// ... Check whether 'to' is reachable from 'from' const Expression& md=*evs[*it].min_difference(); if (md.op()==INFINITY_OP){ if (md.sign()==1){ // Unreachable. continue; } } const Symbol* mu=_back_edges[nodes()[source]]; p_assert(mu, "Could not find MU symbol."); _evolutions_to_mu[to][mu]=evs[*it]; } } /// cerr<<"\nACYCLIC evs for loop "<<loop_name(_loop); /// print_evolutions(_evolutions_from_mu, "MU", cerr); /// print_evolutions(_mu_evolutions, "MU", cerr); /// print_evolutions(_input2mu_evolutions, "INPUT2MU", cerr); /// print_input_values(_input_values, "INPUT", cerr); } static bool has_known_iteration_space(DoStmt& dostmt){ if (dostmt.limit().op()==INFINITY_OP){ /// ... Really a WHILE statement, the iteration space is unknown. return false; } Statement* ps=dostmt.prev_ref(); while(ps){ switch(ps->stmt_class()){ case ASSIGNMENT_STMT: if (ps->lhs().op()==ID_OP){ String name(ps->lhs().symbol().name_ref()); if (name.index("SKIP_FLAG")==0){ // DO statement with premature exit. return false; } } break; case LABEL_STMT: break; default: /// ... Found no flag assignment before the loop. return true; } ps=ps->prev_ref(); } return true; } /*! Consider the following: We have a MU that may have an incoming value, and may also be reached by another loop-invariant definition from within the loop body through the loop-back arc (BACK, MU). Let us denote by IMU the incoming value for the MU node and by INPUT the other input value. Consider the following events: 1. There is a path from MU to BACK. (T/F) 2. The loop has at least 1 iteration. (T/F) 3. IMU is defined. (T/F) 4. There is a path from INPUT to BACK (T/F) Here is a table describing the cyclic evolutions: ???F: MU = IMU + IC *muev T?TT: MU = INPUT + i2mu + (IC-1)*muev MU = IMU + IC *muev T?FT: MU = INPUT + i2mu + (IC-1)*muev FT?T: MU = INPUT + i2mu FFTT: MU = INPUT + i2mu MU = IMU FFFT: MU = INPUT + i2mu */ void EvolutionGraph::_compute_cyclic_evolutions(EvolutionMap& evs, map<const Symbol*, Evolution<Expression> >& ivs){ /// if (_cyclic_evs_computed) { /// return; /// } /// _cyclic_evs_computed=true; if (_loop==0) { evs=_mu_evolutions; return; } /// Check preconditions. _verify_preconditions(); Expression* ic=iteration_count((DoStmt&)*_loop, *_pgm); bool the_loop_has_at_least_1_iteration; if (_ra->signz(*ic)==POS_EXPR){ the_loop_has_at_least_1_iteration=true; } else { the_loop_has_at_least_1_iteration=false; } /// Forall MU symbols. for(set<unsigned int>::iterator muit=mu_this_loop.begin(); muit!=mu_this_loop.end(); ++muit){ Symbol* mu=nodes()[*muit]; /// ... Check for loop index. if (mu==&_loop->index().symbol()){ /// ... Check whether the loop has premature exits. if (has_known_iteration_space((DoStmt&)*_loop)){ /// ... Iteration space limit. ivs[mu]=evolution(last_value((DoStmt&)*_loop, *_pgm)); } else { /// ... Premature exit value. ivs[mu]=evolution(_loop->index()); } continue; } /// ... Check whether this is a parasite. if (parasites.find(index(mu))!=parasites.end()){ continue; } /// ... Check whether this MU was marked as not computable. if (_input_values.find(mu)!=_input_values.end()){ ivs[mu]=evolution(); continue; } bool there_is_a_path_from_mu_to_back; Evolution<Expression> muev; EvolutionMap::iterator found_mu2mu=_mu_evolutions.find(mu); if (found_mu2mu!=_mu_evolutions.end()){ there_is_a_path_from_mu_to_back=true; muev=_mu_evolutions[mu][mu]; } else { there_is_a_path_from_mu_to_back=false; } bool there_is_a_path_from_input_to_back; Evolution<Expression> i2mu, input; const Symbol* isym=0; EvolutionMap::iterator found_input2mu=_input2mu_evolutions.find(mu); if (found_input2mu!=_input2mu_evolutions.end()){ there_is_a_path_from_input_to_back=true; i2mu=(*_input2mu_evolutions[mu].begin()).second; const Symbol* sym=(*_input2mu_evolutions[mu].begin()).first; /// cerr<<"\nAt pgm "<<_pgm->routine_name_ref(); /// cerr<<"\nAt loop "<<loop_name(_loop); /// cerr<<"\n\tFor MU symbol "<<node_name(mu)<<" : "; /// cerr<<"\n\tInput symbol "<<node_name(sym); /// print_evolutions(_input2mu_evolutions, "I2MUs", cerr); input=_input_values[sym]; /// if (input.min_difference()==0){ /// p_abort("ERROR"); /// } if (*input.min_difference()==*input.max_difference()){ if (input.min_difference()->op()==ID_OP){ isym=&input.min_difference()->symbol(); } } if (isym){ if (isym->type().data_type()!=INTEGER_TYPE){ isym=0; } else { if (!isym->is_scalar()){ isym=0; } } } } else { there_is_a_path_from_input_to_back=false; } Symbol* imu; bool imu_is_defined; get_imu(*mu, *_pgm, imu, imu_is_defined); /// cerr<<"\nAt loop "<<loop_name(_loop); /// cerr<<"\n\tFor MU symbol "<<node_name(mu)<<" : "; /// if (there_is_a_path_from_mu_to_back) cerr<<"T"; else cerr<<"F"; /// if (the_loop_has_at_least_1_iteration) cerr<<"T"; else cerr<<"F"; /// if (imu_is_defined) cerr<<"T"; else cerr<<"F"; /// if (there_is_a_path_from_input_to_back) cerr<<"T"; else cerr<<"F"; /// ... Let's roll. /// ... ???F if (!there_is_a_path_from_input_to_back){ if (imu_is_defined){ if (there_is_a_path_from_mu_to_back){ // T?TF evs[imu][mu]=muev; evs[imu][mu]*=ic->clone(); } else { // F?TF // There is no incoming value (input or mu). // Signal logic error. cerr<<"\nAt loop "<<loop_name(_loop); cerr<<"\n\tFor MU symbol "<<node_name(mu)<<" : "; if (there_is_a_path_from_mu_to_back) cerr<<"T"; else cerr<<"F"; if (the_loop_has_at_least_1_iteration) cerr<<"T"; else cerr<<"F"; if (imu_is_defined) cerr<<"T"; else cerr<<"F"; if (there_is_a_path_from_input_to_back) cerr<<"T"; else cerr<<"F"; p_abort("Cannot compute cyclic evolution, no incoming value."); } } else { /// ... ??FF cerr<<endl<<node_name(mu); p_warning("Possibly undefined variable."); } } /// ... T??T if (there_is_a_path_from_mu_to_back && there_is_a_path_from_input_to_back){ if(imu_is_defined){ /// ... T?TT evs[imu][mu]=muev; evs[imu][mu]*=ic->clone(); } else { /// ... T?FT } Evolution<Expression> ev=muev; /// cerr<<"\n\t1 ev = "<<ev; /// cerr<<"\n\t ic = "<<*ic; if (ev.max_difference()->op()==INFINITY_OP && ev.min_difference()->op()!=INFINITY_OP){ /// ... silvius: there are problems multiplying Inf with possibly negative /// ... numbers. ev=evolution(simplify(mul(ev.min_difference()->clone(), simplify(sub(ic->clone(), constant(1))))), infinity()); } else { ev*=simplify(sub(ic->clone(), constant(1))); } /// cerr<<"\n\t2 ev = "<<ev; ev+=i2mu; /// cerr<<"\n\t3 ev = "<<ev; if (isym){ evs[isym][mu]=ev; } else { /// cerr<<"\nev = "<<ev; /// cerr<<"\ninput = "<<input; ev+=input; /// cerr<<"\n1. setting "<<ev; ivs[mu]=ev; } } /// ... FT?T if (!there_is_a_path_from_mu_to_back && the_loop_has_at_least_1_iteration && there_is_a_path_from_input_to_back){ /// ... Since the loop has an iteration and there is no way to get the BACK /// ... value from IMU (no path from MU to BACK), the only value possible /// ... is the INPUT one. /// cerr<<"\n2. setting "<<input; ivs[mu]=input; } /// ... FFTT if (!there_is_a_path_from_mu_to_back && !the_loop_has_at_least_1_iteration && imu_is_defined && there_is_a_path_from_input_to_back){ if (isym){ evs[isym][mu]=i2mu; } else { /// cerr<<"\n3. setting "<<input; ivs[mu]=input; } evs[imu][mu]=evolution(0); } /// ... FFFT if (!there_is_a_path_from_mu_to_back && !the_loop_has_at_least_1_iteration && !imu_is_defined && there_is_a_path_from_input_to_back){ if (isym){ evs[isym][mu]=i2mu; } else { /// cerr<<"\n4. setting "<<input; ivs[mu]=input; } } } delete ic; /// For the parasites. for(set<unsigned int>::iterator muit=mu_this_loop.begin(); muit!=mu_this_loop.end(); ++muit){ Symbol* mu=nodes()[*muit]; if (parasites.find(index(mu))!=parasites.end()){ /// ... silvius: for now, do it for parasites only if the SCC that contains /// ... the parasite MU contains only 0-evolutions and has a single entry /// ... which is a MU itself. const Symbol* host_mu=_verify_parasites_preconditions(mu); if(host_mu){ /// cerr<<"\nFound host_mu: "<<host_mu->name_ref(); if (ivs.find(host_mu)!=ivs.end()){ // Copy input from host MU. /// cerr<<"\n5. setting "<<ivs[host_mu]; ivs[mu]=ivs[host_mu]; } for(EvolutionMap::iterator it=evs.begin(); it!=evs.end(); ++it){ map<const Symbol*, Evolution<Expression> >::iterator found=(*it).second.find(host_mu); if (found!=(*it).second.end()){ /// ... Copy evolution from host MU. evs[(*it).first][mu]=(*found).second; } } } else { /// cerr<<"\nCould not find host_mu for parasite_mu "<<mu->name_ref(); ivs[mu]=evolution(); } } } /// cerr<<"\nCYCLIC evs for loop "<<loop_name(_loop); /// print_evolutions(evs, "MU", cerr); /// print_input_values(ivs, "CYCLIC", cerr); } /*! \brief Checks whether the given parasite MU is in an SCC which consists of only 0-evolutions and has a single entry which is a MU node. This node is the return value, otherwise 0. */ const Symbol* EvolutionGraph::_verify_parasites_preconditions(Symbol* parasite_mu){ /// print_evolutions(_evolutions_from_mu, "PARASITE", cerr); /// First, find the SCC. /// Collect all nodes reachable from parasite_mu. set<const Symbol*> reachable; reachable.insert(parasite_mu); for(EvolutionMap::iterator emit=_evolutions_from_mu.begin(); emit!=_evolutions_from_mu.end(); ++emit){ map<const Symbol*, Evolution<Expression> >& evs=(*emit).second; map<const Symbol*, Evolution<Expression> >::iterator found= evs.find(parasite_mu); if (found!=evs.end()){ reachable.insert((*emit).first); } } /// Go through all the reachable nodes and make sure all the links between /// them are 0-valued. Also, make sure the BACK nodes come back to /// parasite_mu. for(set<const Symbol*>::iterator it=reachable.begin(); it!=reachable.end(); ++it){ if (back_this_loop.find(index((Symbol*)*it))!=back_this_loop.end()){ /// ... Back node. if (_back_edges[*it]!=parasite_mu){ return 0; } } const EdgeList& edges=get_edges(index((Symbol*)*it)); for(EdgeList::const_iterator elit=edges.begin(); elit!=edges.end(); ++elit){ if (reachable.find(nodes()[(*elit).first])!=reachable.end()){ /// ... Edge between two reachable nodes. if (!is_integer_zero(*(*elit).second.min_difference()) || !is_integer_zero(*(*elit).second.max_difference())){ /// cerr<<"\nRET 1"; return 0; } } } } /// Look for the entries in this SCC. const Symbol* entry=0; for(set<const Symbol*>::iterator it=reachable.begin(); it!=reachable.end(); ++it){ /// cerr<<"\n\tREACHABLE: "<<(*it)->name_ref(); const EdgeList& edges=get_reversed_edges(index((Symbol*)*it)); for(EdgeList::const_iterator elit=edges.begin(); elit!=edges.end(); ++elit){ const Symbol* candidate=nodes()[(*elit).first]; if (reachable.find(candidate)==reachable.end()){ /// cerr<<"\n\t\tCANDIDATE: "<<candidate->name_ref(); /// ... Entry. if (entry){ if (entry!=candidate){ /// ... Multiple entries /// cerr<<"\nRET 2"; return 0; } } else { entry=candidate; } } } } /// Check whether this single entry is a MU node. /// Backtrack to a MU if possible. while(entry){ /// cerr<<"\n\tENTRY: "<<entry->name_ref(); if (_loop){ if (&_loop->index().symbol()==(Symbol*)entry){ return entry; } } if (mu_this_loop.find(index((Symbol*)entry))!=mu_this_loop.end()){ return entry; } const EdgeList& edges=get_reversed_edges(index((Symbol*)entry)); if (edges.size()==1){ if (!is_integer_zero(*(*edges.begin()).second.min_difference()) || !is_integer_zero(*(*edges.begin()).second.max_difference())){ /// cerr<<"\nRET 3"; return 0; } entry=nodes()[(*edges.begin()).first]; continue; } else { break; } } /// cerr<<"\nRET 4"; return 0; } /* Dumps the graph in DOT format. */ void EvolutionGraph::print_graph(const char* filename){ ofstream f(filename); f<<"\n/* Automatically generated by Polaris */" <<"\n\ndigraph EvolutionGraph { "; vector<Symbol*>::const_iterator sit=nodes().begin(); for( ; sit!=nodes().end(); ++sit){ unsigned n=index((Symbol*)*sit); /// ... Node info. /// ... Is it an INPUT node? if (_input_values.find(*sit)!=_input_values.end()){ f<<"\n\t\t\""<<n<<"\" [label=\""<<node_name(*sit) <<":"<<_input_values[*sit]<<"\", shape=\"box\", color=\"green\"" <<"];"; } else { /// ... Is it a MU node? if (mu_this_loop.find(n)!=mu_this_loop.end()){ f<<"\n\t\t\""<<n<<"\" [label=\""<<node_name(*sit) <<"\", shape=\"doublecircle\", color=\"red\"" <<"];"; } else { /// ... Or is it a BACK node? if (back_this_loop.find(n)!=back_this_loop.end()){ f<<"\n\t\t\""<<n<<"\" [label=\""<<node_name(*sit) <<"\", shape=\"hexagon\", color=\"brown\"" <<"];"; } else { // Regular node. f<<"\n\t\t\""<<n<<"\" [label=\""<<node_name(*sit) <<"\", shape=\"ellipse\", color=\"black\"" <<"];"; } } } } /// Edges. for(unsigned int n=0; n<nodes().size(); ++n){ const EdgeList& edges=get_edges(n); for(EdgeList::const_iterator eit=edges.begin(); eit!=edges.end(); ++eit){ unsigned int target=(*eit).first; if (*(*eit).second.min_difference()==*(*eit).second.max_difference()){ f<<"\n\t\""<<n<<"\" -> \""<<target<<"\" [label=\"" <<*(*eit).second.max_difference()<<"\""; } else { f<<"\n\t\""<<n<<"\" -> \""<<target<<"\" [label=\"[" <<*(*eit).second.min_difference()<<", " <<*(*eit).second.max_difference()<<"]\""; } f<<"];"; } /// ... Look for back edges. map<const Symbol*, const Symbol*>::iterator beit= _back_edges.find(nodes()[n]); if (beit!=_back_edges.end()){ f<<"\n\t\""<<n<<"\" -> \""<<index((Symbol*)(*beit).second) <<"\" [label=\"0\", style=dotted];"; } } f<<"\n}\n/* End of file */"; } static RangeExpr* _range(const Evolution<Expression>& ev){ if (ev.min_difference() && ev.max_difference()){ return new RangeExpr(ev.min_difference()->clone(), ev.max_difference()->clone()); } return new RangeExpr(infinity(-1), infinity(+1)); } /*! \brief There are three ways to compute the value: 1. input + input_2_value 2. mu_input + mu_acyclic*(ic-1) + mu_2_value 3. input + input2mu + mu_acyclic*(ic-2) + mu_2_value If this VEG corresponds to a whole routine, just case 1 is considered. \warning Only works if given symbol is a node in this evolution graph. */ void EvolutionGraph::_possible_ranges(const Symbol& sym, list<pair<list<Symbol*>, RangeExpr*> >& result){ /// Only do it if &sym is a node in *this. if (!contains((Symbol*)&sym)){ return; } Symbol* nsym=(Symbol*)&sym; if (sym.is_array()){ cerr<<"\nNode not scalar: "<<sym.name_ref(); p_warning(""); return; } if (_loop){ if (&sym==&_loop->index().symbol()){ /// ... silvius: check for negative step! list<Symbol*> path; path.push_back(nsym); result.push_back(make_pair(path, new RangeExpr(_loop->init().clone(), _loop->limit().clone()))); return; } } /// Find total values in first class. /// First check whether it is an input itself. map<const Symbol*, Evolution<Expression> >::iterator found= _input_values.find(&sym); if (found!=_input_values.end()){ Evolution<Expression> ev=(*found).second; list<Symbol*> path; path.push_back((Symbol*)&sym); result.push_back(make_pair(path, _range(ev))); } EvolutionMap::iterator it=_evolutions_from_input.find(&sym); if (it!=_evolutions_from_input.end()){ for(map<const Symbol*, Evolution<Expression> >::iterator it2= (*it).second.begin(); it2!=(*it).second.end(); ++it2){ const Symbol* isym=(*it2).first; list<Symbol*> path; path.push_back((Symbol*)isym); Evolution<Expression> ev=_input_values[isym]; ev+=(*it2).second; result.push_back(make_pair(path, _range(ev))); } } if (_loop){ /// ... Find total values in second and third class. it=_evolutions_from_mu.find(&sym); if (it!=_evolutions_from_mu.end()){ for(map<const Symbol*, Evolution<Expression> >::iterator it2= (*it).second.begin(); it2!=(*it).second.end(); ++it2){ const Symbol* mu=(*it2).first; if (parasites.find(index((Symbol*)mu))!=parasites.end()){ Evolution<Expression> ev=evolution(); list<Symbol*> path; path.push_back((Symbol*)mu); result.push_back(make_pair(path, _range(ev))); continue; } /// ... Second class. Symbol* imu; bool imu_is_defined; get_imu((Symbol&)*mu, *_pgm, imu, imu_is_defined); if (imu==0){ // This better be the loop index. if (_loop){ if (mu==&_loop->index().symbol()){ /// ... silvius: check for negative step! Evolution<Expression> ev=(*it2).second; ev+=evolution(_loop->init().clone(), _loop->limit().clone()); list<Symbol*> path; path.push_back((Symbol*)mu); result.push_back(make_pair(path, _range(ev))); } } cerr<<"\nFor MU node: "<<mu->name_ref(); p_abort("No input to MU node."); } if (imu_is_defined){ // Second class. Evolution<Expression> current=evolution(id(*imu)); Evolution<Expression> cyclic; if (_mu_evolutions.find(mu)!=_mu_evolutions.end()){ /// ... There is a cycle from mu to itself. cyclic=_mu_evolutions[mu][mu]; } else { cyclic=evolution(constant(0)); } cyclic*=simplify(sub(iteration_count((DoStmt&)*_loop, *_pgm), constant(1))); current+=cyclic; current+=(*it2).second; list<Symbol*> path; path.push_back((Symbol*)mu); result.push_back(make_pair(path, _range(current))); } /// ... Third class. /// ... This only makes sense if there are inputs reaching mu. EvolutionMap::iterator iit=_input2mu_evolutions.find(mu); if (iit!=_input2mu_evolutions.end()){ for(map<const Symbol*, Evolution<Expression> >::iterator iit2= (*iit).second.begin(); iit2!=(*iit).second.end(); ++iit2){ const Symbol* isym=(*iit2).first; Evolution<Expression> current=_input_values[isym]; current+=(*iit2).second; Evolution<Expression> cyclic; if (_mu_evolutions.find(mu)!=_mu_evolutions.end()){ /// ... There is a cycle from mu to itself. cyclic=_mu_evolutions[mu][mu]; } else { cyclic=evolution(constant(0)); } cyclic*=simplify(sub(iteration_count((DoStmt&)*_loop, *_pgm), constant(2))); current+=cyclic; current+=(*it2).second; list<Symbol*> path; path.push_back((Symbol*)isym); path.push_back((Symbol*)mu); result. push_back(make_pair(path, _range(current))); } } } } } } /*! There are three ways to compute the value: 1. input + input_2_value 2. mu_input + mu_acyclic*(ic-1) + mu_2_value 3. input + input2mu + mu_acyclic*(ic-2) + mu_2_value If this VEG corresponds to a whole routine, just case 1 is considered. \warning Only works if given symbol is a node in this evolution graph. */ Expression* EvolutionGraph::_local_range(const Symbol& sym){ /// cerr<<"\n\nEnter local_range in loop "<<loop_name(_loop) /// <<", for symbol "<<sym.name_ref(); /// For now, only do it if &sym is a node in *this. if (!contains((Symbol*)&sym)){ cerr<<"\nNode not in graph: "<<sym.name_ref(); p_warning(""); return new RangeExpr(infinity(-1), infinity(1)); } if (sym.is_array()){ cerr<<"\nNode not scalar: "<<sym.name_ref(); p_warning(""); return new RangeExpr(infinity(-1), infinity(1)); } if (_loop){ if (&sym==&_loop->index().symbol()){ /// ... silvius: check for negative step! return new RangeExpr(_loop->init().clone(), _loop->limit().clone()); } } Evolution<Expression> ev; bool ev_is_initialized=false; /// Find total values in first class. /// First check whether it is an input itself. map<const Symbol*, Evolution<Expression> >::iterator found= _input_values.find(&sym); if (found!=_input_values.end()){ ev=(*found).second; ev_is_initialized=true; /// ... Return now, all other reaching values will be overwritten. /// cerr<<"\n\tearly return."; /// print_input_values(_input_values, "INPUT", cerr); return new RangeExpr(ev.min_difference()->clone(), ev.max_difference()->clone()); } EvolutionMap::iterator it=_evolutions_from_input.find(&sym); if (it!=_evolutions_from_input.end()){ for(map<const Symbol*, Evolution<Expression> >::iterator it2= (*it).second.begin(); it2!=(*it).second.end(); ++it2){ const Symbol* isym=(*it2).first; Evolution<Expression> this_ev=_input_values[isym]; this_ev+=(*it2).second; if (ev_is_initialized){ ev=merge_unite(ev, this_ev, *_pgm, _ra); } else { ev=this_ev; ev_is_initialized=true; } } } if (_loop){ /// ... Find total values in second and third class. it=_evolutions_from_mu.find(&sym); if (it!=_evolutions_from_mu.end()){ for(map<const Symbol*, Evolution<Expression> >::iterator it2= (*it).second.begin(); it2!=(*it).second.end(); ++it2){ const Symbol* mu=(*it2).first; if (parasites.find(index((Symbol*)mu))!=parasites.end()){ // silvius: for now, don't do anything about parasites. /// cerr<<"\n\tparasite."; ev=evolution(); return new RangeExpr(ev.min_difference()->clone(), ev.max_difference()->clone()); } /// cerr<<"\n\t mu = "<<mu->name_ref(); /// ... Second class. Symbol* imu; bool imu_is_defined; get_imu((Symbol&)*mu, *_pgm, imu, imu_is_defined); if (imu==0){ // This better be the loop index. if (_loop){ if (mu==&_loop->index().symbol()){ /// ... silvius: check for negative step! Evolution<Expression> from_mu=(*it2).second; from_mu+=evolution(_loop->init().clone(), _loop->limit().clone()); return new RangeExpr(from_mu.min_difference()->clone(), from_mu.max_difference()->clone()); } } cerr<<"\nFor MU node: "<<mu->name_ref(); p_abort("No input to MU node."); } if (imu_is_defined){ // Second class. Evolution<Expression> current=evolution(id(*imu)); Evolution<Expression> cyclic; if (_mu_evolutions.find(mu)!=_mu_evolutions.end()){ /// ... There is a cycle from mu to itself. cyclic=_mu_evolutions[mu][mu]; } else { cyclic=evolution(constant(0)); } cyclic*=simplify(sub(iteration_count((DoStmt&)*_loop, *_pgm), constant(1))); current+=cyclic; current+=(*it2).second; if (ev_is_initialized){ ev=merge_unite(ev, current, *_pgm, _ra); /// cerr<<"\n\t2. ev = "<<ev; } else { ev=current; /// cerr<<"\n\t3. ev = "<<ev; ev_is_initialized=true; } } /// ... Third class. /// ... This only makes sense if there are inputs reaching mu. EvolutionMap::iterator iit=_input2mu_evolutions.find(mu); if (iit!=_input2mu_evolutions.end()){ for(map<const Symbol*, Evolution<Expression> >::iterator iit2= (*iit).second.begin(); iit2!=(*iit).second.end(); ++iit2){ const Symbol* isym=(*iit2).first; Evolution<Expression> current=_input_values[isym]; current+=(*iit2).second; Evolution<Expression> cyclic; if (_mu_evolutions.find(mu)!=_mu_evolutions.end()){ /// ... There is a cycle from mu to itself. cyclic=_mu_evolutions[mu][mu]; } else { cyclic=evolution(constant(0)); } cyclic*=simplify(sub(iteration_count((DoStmt&)*_loop, *_pgm), constant(2))); current+=cyclic; current+=(*it2).second; if (ev_is_initialized){ ev=merge_unite(ev, current, *_pgm, _ra); /// cerr<<"\n\t4. ev = "<<ev; } else { ev=current; /// cerr<<"\n\t5. ev = "<<ev; ev_is_initialized=true; } } } } } } if (ev_is_initialized){ /// cerr<<"\n\t6. ev = "<<ev; return new RangeExpr(ev.min_difference()->clone(), ev.max_difference()->clone()); } else { /// cerr<<"\n\t7. ev = OMEGA"; return new RangeExpr(infinity(-1), infinity()); } } /*! \brief Computes the range of the given expression over _loop. \warning All symbols referenced by the given expression must be defined in _loop. \warning We will take ownership over expr. */ Expression* EvolutionGraph::_eliminate_vars(Expression* expr, set<Symbol*>& syms){ /// Eliminate all symbols defined here. RangeAccessor ra(*_ra); RefSet<Symbol> vars_to_eliminate; for(set<Symbol*>::iterator sit=syms.begin(); sit!=syms.end(); ++sit){ Expression* lr=_local_range(**sit); /// cerr<<"\n\t\tSetting local range for "<<(*sit)->name_ref() /// <<" to "<<*lr; /// ... Optimization. Try to detect (-Inf:+Inf) early. if (lr->op()==RANGE_OP){ if (((RangeExpr*)lr)->lb().op()==INFINITY_OP){ if ((((RangeExpr*)lr)->lb().sign()==-1)){ if (((RangeExpr*)lr)->ub().op()==INFINITY_OP){ if ((((RangeExpr*)lr)->ub().sign()==1)){ return lr; } } } } } ra.set_range(**sit, lr); vars_to_eliminate.ins(**sit); } return ra.eliminate_vars(expr, &vars_to_eliminate); } static Expression* _embed_symbolic_range(Expression* range, ProgramUnit& pgm, RangeAccessor* ra, set<Symbol*>& dummies){ Symbol& dummy= pgm.symtab().rename_and_ins(new VariableSymbol("DUMMY", make_type(INTEGER_TYPE), NOT_FORMAL, NOT_SAVED)); dummies.insert(&dummy); ra->set_range(dummy, range); return id(dummy); } /// Embeds the tightest known range for array references. static Expression* _filter_arrays(Expression* expr, ProgramUnit& pgm, Statement* loop, set<Symbol*>& dummies, RangeAccessor* ra){ if (expr==0){ return 0; } if (expr->op()==ARRAY_REF_OP){ if (gsa_base(expr->array().symbol())->formal() || gsa_base(expr->array().symbol())->common_ref()){ Expression* toret=new RangeExpr(infinity(-1), infinity()); delete expr; /// cerr<<"\nReturn 1"; return _embed_symbolic_range(toret, pgm, ra, dummies); } Expression* eg_range_array_1_to_i(Expression& e, ProgramUnit& pgm, Statement* loop); Statement* last=loop; while(loop){ last=loop; loop=loop->outer_ref(); } if (last==0){ Expression* toret=new RangeExpr(infinity(-1), infinity()); delete expr; /// cerr<<"\nReturn 2"; return _embed_symbolic_range(toret, pgm, ra, dummies); } Expression* toret=eg_range_array_1_to_i(*expr, pgm, last); delete expr; if (toret->op()==RANGE_OP){ /// cerr<<"\nReturn 3: "<<*toret; return _embed_symbolic_range(toret, pgm, ra, dummies); } else { /// cerr<<"\nReturn 4"; return toret; } } for(Mutator<Expression> expit=expr->arg_list(); expit.valid(); ++expit) { Assign<Expression> a = expit.assign(); a=_filter_arrays(expit.pull(), pgm, loop, dummies, ra); } /// cerr<<"\nReturn 5"; return expr; } static Expression* _filter_arrays(Expression* expr, ProgramUnit& pgm, Statement* loop){ Statement* rs=&quick_pgm_entry(pgm); if (loop){ rs=loop->next_ref(); } /// cerr<<"\nEnter filter_arrays: "<<*expr; RangeAccessor* ra=new RangeAccessor(pgm.range_dict_guarded(), *rs); set<Symbol*> dummies; Expression* toret=_filter_arrays(expr, pgm, loop, dummies, ra); /// cerr<<"\n\tLevel 1 before subst:"<<*toret; /// cerr<<"\nra = "<<*ra; set<Symbol*>::iterator sit; RefSet<Symbol> vars_to_eliminate; bool found_infinity=false; for(sit=dummies.begin(); sit!=dummies.end(); ++sit){ const Expression* r=ra->get_range_ref(**sit); if (r->op()==RANGE_OP){ if (((const RangeExpr*)r)->lb().op()==INFINITY_OP || ((const RangeExpr*)r)->ub().op()==INFINITY_OP){ found_infinity=true; break; } } vars_to_eliminate.ins(**sit); } if (found_infinity){ delete ra; for(sit=dummies.begin(); sit!=dummies.end(); ++sit){ pgm.symtab().del((*sit)->name_ref()); } delete toret; toret=new RangeExpr(infinity(-1), infinity()); } else { toret=ra->eliminate_vars(toret, &vars_to_eliminate); delete ra; for(sit=dummies.begin(); sit!=dummies.end(); ++sit){ pgm.symtab().del((*sit)->name_ref()); } } if (toret->op()==OMEGA_OP){ /// ... Probably some undefined operation such as ( -Inf + Inf ). delete toret; toret=new RangeExpr(infinity(-1), infinity()); } /// cerr<<"\nExit filter_arrays: "<<*toret; return toret; } /// Finds the range of expr across the given domain. /// If the given domain is 0, the range across the whole program unit /// is returned. Expression* EvolutionGraph::_global_range_per_iteration(Expression* expr, DoStmt* domain){ /// cerr<<"\n\n\nEntering EvolutionGraph::_global_range " /// <<"\n\texpr = "<<*expr /// <<"\n\tdomain = "<<loop_name(domain); expr=_filter_arrays(expr, *_pgm, domain); /// Iterate until we have no symbols defined in a loop within domain. do { DoStmt* ci=0; set<Symbol*> syms_in_innermost; RefList<Symbol> syms; referred_symbols(*expr, syms); if (syms.entries()==0){ /// ... No variables in expr. return expr; } for(Iterator<Symbol> sit=syms; sit.valid(); ++sit){ DoStmt* current=def_loop(sit.current(), *_pgm); if (inner(current, ci)){ /// ... current <= ci if (current==ci){ // At this point we think we are in the innermost. syms_in_innermost.insert(&sit.current()); } else { // This is a new innermost. ci=current; syms_in_innermost.clear(); syms_in_innermost.insert(&sit.current()); } } } /// cerr<<"\n\tin loop "<<loop_name(ci); /// cerr<<"\n\tEG::rs: "<<syms; /// ... This test is a valid termination condition because we are going outer. if (inner(domain, ci)){ break; } else { /// cerr<<"\n\tbefore elimination in loop "<<loop_name(ci)<<": "<<*expr; expr=_get_eg(_pgm, ci)->_eliminate_vars(expr, syms_in_innermost); /// cerr<<"\n\t result = "<<*expr; } } while (1); /// if (expr){ /// cerr<<"\n\tfrom EvolutionGraph::_global_range: "<<*expr; /// } /// silvius: optimization if (expr->op()==ID_OP){ Symbol* value=&expr->symbol(); if (contains(value)){ map<const Symbol*, Evolution<Expression> >::iterator found= _input_values.find(value); if (found!=_input_values.end()){ /// ... Does have an input value. delete expr; return new RangeExpr((*found).second.min_difference()->clone(), (*found).second.max_difference()->clone()); } } } expr=_filter_arrays(expr, *_pgm, domain); /// if (expr){ /// cerr<<"\n\tfrom EvolutionGraph::_global_range: "<<*expr; /// } return expr; } /// Finds the range of expr across the given domain. /// If the given domain is 0, the range across the whole program unit /// is returned. Expression* EvolutionGraph::_global_range(Expression* expr, DoStmt* domain){ /// if (domain){ /// if (domain->outer_ref()){ /// cerr<<"\n\n\nEntering EvolutionGraph::_global_range " /// <<"\n\texpr = "<<*expr /// <<"\n\tdomain = "<<loop_name(domain); /// } /// } expr=_filter_arrays(expr, *_pgm, domain); /// cerr<<"\nAfter _filter_arrays : "<<*expr; /// cerr<<"\nDomain = "<<loop_name(domain); /// Iterate until we have no symbols defined in a loop within domain. do { DoStmt* ci=0; set<Symbol*> syms_in_innermost; RefList<Symbol> syms; referred_symbols(*expr, syms); if (syms.entries()==0){ /// ... No variables in expr. return expr; } for(Iterator<Symbol> sit=syms; sit.valid(); ++sit){ DoStmt* current=def_loop(sit.current(), *_pgm); if (inner(current, ci)){ /// ... current <= ci if (current==ci){ // At this point we think we are in the innermost. syms_in_innermost.insert(&sit.current()); } else { // This is a new innermost. ci=current; syms_in_innermost.clear(); syms_in_innermost.insert(&sit.current()); } } } /// cerr<<"\n\tin loop "<<loop_name(ci); /// cerr<<"\n\tEG::rs: "<<syms; /// ... This test is a valid termination condition because we are going outer. if (inner(domain, ci)){ break; } else { /// cerr<<"\n\tbefore elimination in loop "<<loop_name(ci)<<": "<<*expr; expr=_get_eg(_pgm, ci)->_eliminate_vars(expr, syms_in_innermost); /// cerr<<"\n\t result = "<<*expr; } } while (1); /// if (expr){ /// cerr<<"\n\tfrom EvolutionGraph::_global_range: "<<*expr; /// } /// silvius: optimization if (expr->op()==ID_OP){ Symbol* value=&expr->symbol(); if (contains(value)){ map<const Symbol*, Evolution<Expression> >::iterator found= _input_values.find(value); if (found!=_input_values.end()){ /// ... Does have an input value. delete expr; return new RangeExpr((*found).second.min_difference()->clone(), (*found).second.max_difference()->clone()); } } } /// We are at the outermost level within domain. if (domain==0){ } else { set<Symbol*> syms_in_domain; RefList<Symbol> syms; referred_symbols(*expr, syms); for(Iterator<Symbol> sit=syms; sit.valid(); ++sit){ DoStmt* current=def_loop(sit.current(), *_pgm); if (current==domain){ syms_in_domain.insert(&sit.current()); } } expr= _get_eg(_pgm, domain)->_eliminate_vars(expr, syms_in_domain); } if (domain){ expr=_filter_arrays(expr, *_pgm, domain->outer_ref()); } else { expr=_filter_arrays(expr, *_pgm, domain); } /// if (expr){ /// if (domain){ /// if (domain->outer_ref()){ /// cerr<<"\n\tfrom EvolutionGraph::_global_range: "<<*expr; /// } /// } /// } return expr; } Expression* EvolutionGraph::_global_range(Expression* expr){ /// Find the outermost loop. DoStmt* co=0; RefList<Symbol> syms; referred_symbols(*expr, syms); Iterator<Symbol> sit=syms; if (!sit.valid()){ /// ... No variables. return expr; } else { co=def_loop(sit.current(), *_pgm); ++sit; } for(; sit.valid(); ++sit){ DoStmt* current=def_loop(sit.current(), *_pgm); if (outer(current, co)){ co=current; } } return _global_range(expr, co); } /*! We try to prove that: value_2_mu + mu_2_value > 0 */ bool EvolutionGraph::increasing(const Symbol& value){ /// For now, only do it if &sym is a node in *this. Expression* dist=min_distance(value, value); cerr<<"\nEnd of implementation: TODO: compare "<<*dist<<" to 0."; p_abort(""); } /*! We look at: value_2_mu + mu_2_value > 0 Also, we make sure that there are no input values. */ EvolutionGraph::SequenceType EvolutionGraph::sequence_type(const Symbol& value){ if (_loop==0){ return ST_UNKNOWN; } /// Let us bring the problem into our own domain. Symbol* node=(Symbol*)&value; if (!contains(node)){ /// ... Let us get its range for the outermost domain within this loop. DoStmt* loop=def_loop(*node, *_pgm); if (!inner(loop, (DoStmt*)_loop)){ /// ... Defined within outer loop, it is invariant here. return ST_UNKNOWN; } /// ... silvius: for now, return ST_UNKNOWN at this point. return ST_UNKNOWN; } /// If it gets here, 'node' was defined at this level. /// Make sure there are no reaching input values. if (_evolutions_from_input.find(node)!=_evolutions_from_input.end()){ return ST_UNKNOWN; } /// Find value_2_mu and mu_2_value. EvolutionMap::iterator v2mit=_evolutions_to_mu.find(node); if (v2mit==_evolutions_to_mu.end()){ return ST_UNKNOWN; } EvolutionMap::iterator m2vit=_evolutions_from_mu.find(node); if (m2vit==_evolutions_from_mu.end()){ return ST_UNKNOWN; } /// For now, do it only if they have exactly one fromMU and exactly one /// toMU, and it is the same. if ((*m2vit).second.size()!=1){ return ST_UNKNOWN; } const Symbol* mu=(*(*m2vit).second.begin()).first; EvolutionMap::data_type::iterator v2mitit=(*v2mit).second.find(mu); if (v2mitit==(*v2mit).second.end()){ return ST_UNKNOWN; } /// Let us compute the aggregated evolution from 'node' to itself. Evolution<Expression> value2mu=(*v2mitit).second; Evolution<Expression> mu2value=(*(*m2vit).second.begin()).second; Evolution<Expression> total=value2mu; total+=mu2value; /// Let us see where this evolution goes. Expression* zero=constant(0); List<Expression> automatic_destructor; automatic_destructor.ins_last(zero); if (p_greater_than(*total.min_difference(), *zero, _ra)){ return ST_INCREASING; } if (p_greater_equal(*total.min_difference(), *zero, _ra)){ return ST_NONDECREASING; } if (p_less_than(*total.max_difference(), *zero, _ra)){ return ST_DECREASING; } if (p_less_equal(*total.max_difference(), *zero, _ra)){ return ST_NONINCREASING; } /// Just could not figure it out. return ST_UNKNOWN; } static void _cleanup_map(map<Symbol*, Expression*>& m){ /// Cleanup. map<Symbol*, Expression*>::iterator mit; for(mit=m.begin(); mit!=m.end(); ++mit){ delete (*mit).second; } } Expression* EvolutionGraph::min_distance(const Symbol& left, const Symbol& right){ /// Sanity checks. p_assert(_loop, "Cannot compute distance for contexts other than loops."); DoStmt* loop_left=def_loop(left, *_pgm); DoStmt* loop_right=def_loop(left, *_pgm); p_assert(outer((DoStmt*)_loop, loop_left), "Symbol not defined in loop."); p_assert(outer((DoStmt*)_loop, loop_right), "Symbol not defined in loop."); /// cerr<<"\n\n\n_loop = "<<_loop->get_loop_name(); /// cerr<<"\n\tSyms = "<<left.name_ref()<<", "<<right.name_ref(); /// First compute the minimum distance from 'left' to all the MU(_loop) that /// it reaches. map<Symbol*, Expression*> min_dist_from_left; min_dist_from_left.insert(make_pair((Symbol*)&left, constant(0))); /// Add the distances from all the MUs that may be reached by left. /// Do it for all the EGs from loop_left to _loop inclussively. DoStmt* loop=loop_left; do { EvolutionGraph* eg=_get_eg(_pgm, loop); /// cerr<<"\n\nLEFT loop = "<<loop->get_loop_name(); map<Symbol*, Expression*> new_dists; map<Symbol*, Expression*>::iterator mit; /// for(mit=min_dist_from_left.begin(); mit!=min_dist_from_left.end(); ++mit){ /// Symbol* sym=(*mit).first; /// Expression* dist=(*mit).second; /// cerr<<"\n\tsym = "<<sym->name_ref()<<" : "<<*dist; /// } for(mit=min_dist_from_left.begin(); mit!=min_dist_from_left.end(); ++mit){ Symbol* sym=(*mit).first; Expression* dist=(*mit).second; EvolutionMap::iterator found=eg->_evolutions_to_mu.find(sym); if (found!=eg->_evolutions_to_mu.end()){ /// ... Found a MU that sym goes into. for(map<const Symbol*, Evolution<Expression> >::iterator it2= (*found).second.begin(); it2!=(*found).second.end(); ++it2){ Expression* newdist= simplify(add(dist->clone(), (*it2).second.min_difference()->clone())); new_dists.insert(make_pair((Symbol*)(*it2).first, newdist)); } } } loop=(DoStmt*)loop->outer_ref(); min_dist_from_left.swap(new_dists); _cleanup_map(new_dists); } while (loop!=_loop->outer_ref()); /// Now compute the minimum distance from all the MU(_loop) that reach 'right' /// to 'right'. map<Symbol*, Expression*> min_dist_to_right; min_dist_to_right.insert(make_pair((Symbol*)&right, constant(0))); loop=loop_right; do { EvolutionGraph* eg=_get_eg(_pgm, loop); /// cerr<<"\n\nRIGHT loop = "<<loop->get_loop_name(); map<Symbol*, Expression*> new_dists; map<Symbol*, Expression*>::iterator mit; /// for(mit=min_dist_to_right.begin(); mit!=min_dist_to_right.end(); ++mit){ /// Symbol* sym=(*mit).first; /// Expression* dist=(*mit).second; /// cerr<<"\n\tsym = "<<sym->name_ref()<<" : "<<*dist; /// } for(mit=min_dist_to_right.begin(); mit!=min_dist_to_right.end(); ++mit){ Symbol* sym=(*mit).first; Expression* dist=(*mit).second; EvolutionMap::iterator found=eg->_evolutions_from_input.find(sym); if (found!=eg->_evolutions_from_input.end()){ /// ... Found an INPUT that goes into sym. /// ... silvius: we could do a little better. _cleanup_map(min_dist_from_left); _cleanup_map(min_dist_to_right); _cleanup_map(new_dists); return constant(0); } found=eg->_evolutions_from_mu.find(sym); if (found!=eg->_evolutions_from_mu.end()){ /// ... Found a MU that goes into sym. for(map<const Symbol*, Evolution<Expression> >::iterator it2= (*found).second.begin(); it2!=(*found).second.end(); ++it2){ Expression* newdist= simplify(add(dist->clone(), (*it2).second.min_difference()->clone())); new_dists.insert(make_pair((Symbol*)(*it2).first, newdist)); } } } loop=(DoStmt*)loop->outer_ref(); min_dist_to_right.swap(new_dists); _cleanup_map(new_dists); } while (loop!=_loop->outer_ref()); /// By default set the distance to Infinity since we do not know whether /// they are connected. Expression* toret=infinity(); /// Now add the distances for all the common MU(_loop). map<Symbol*, Expression*>::iterator mit, found; for(mit=min_dist_to_right.begin(); mit!=min_dist_to_right.end(); ++mit){ Symbol* mu=(*mit).first; Expression* dright=(*mit).second; found=min_dist_from_left.find(mu); if (found!=min_dist_from_left.end()){ Expression* dleft=(*found).second; Expression* candidate=simplify(add(dleft->clone(), dright->clone())); if (*candidate==*toret){ /// ... Discard candidate. delete candidate; } else { if (p_less_than(*candidate, *toret, _ra)){ // Keep candidate. delete toret; toret=candidate; } else { if (p_greater_than(*candidate, *toret, _ra)){ /// ... Discard candidate. delete candidate; } else { /// ... Incomparable, keep MIN. Symbol* best_op_sym=_pgm->symtab().find_ref("MIN"); p_assert(best_op_sym, "MIN intrinsic not in symbol table"); toret=intrinsic_call(id(*best_op_sym), comma(toret, candidate)); } } } } else { /// ... There is a MU that can reach right but there is no path from /// ... left to it. delete toret; _cleanup_map(min_dist_from_left); _cleanup_map(min_dist_to_right); return constant(0); } } /// Return. if (toret->op()==INFINITY_OP){ /// ... The values are not related, report distance conservatively. delete toret; return constant(0); } else { return toret; } } /// Returns true if ev1 is included in ev2*complementary. static bool included(Evolution<Expression>& ev1, Evolution<Expression>& ev2, bool complementary, ProgramUnit& pgm, RangeAccessor* ra){ /// cerr<<"\nenter included with "<<ev1<<", "<<ev2<<", and "<<complementary; if (complementary==false){ if (included(ev1, ev2, pgm, ra)){ /// cerr<<"\n\treturn true 1"; return true; } } else { /// ... Complementary range. Evolution<Expression> below= evolution(infinity(-1), simplify(sub(ev2.min_difference()->clone(), constant(1)))); if (included(ev1, below, pgm, ra)){ /// cerr<<"\n\treturn true 2"; return true; } Evolution<Expression> above= evolution(simplify(add(ev2.max_difference()->clone(), constant(1))), infinity(1)); if (included(ev1, above, pgm, ra)){ /// cerr<<"\n\treturn true 3"; return true; } } /// cerr<<"\n\treturn false"; return false; } /// Returns true if ev1 may be disjoint from ev2*complementary. static bool disjoint(Evolution<Expression>& ev1, Evolution<Expression>& ev2, bool complementary, ProgramUnit& pgm, RangeAccessor* ra){ return included(ev1, ev2, !complementary, pgm, ra); } static void print_trace(pair<list<Symbol*>, Evolution<Expression> >& trace){ for(list<Symbol*>::iterator it=trace.first.begin(); it!=trace.first.end(); ++it){ cerr<<(*it)->name_ref()<<","; } cerr<<": "<<trace.second; } void EvolutionGraph::traces_from_mu(Symbol* node, pair<RangeExpr*, bool>& range, map<Symbol*, list<list<Symbol*> > >& trace){ Evolution<Expression> given=evolution(*range.first); EvolutionMap::iterator it=_evolutions_from_mu.find(node); if (it!=_evolutions_from_mu.end()){ for(map<const Symbol*, Evolution<Expression> >::iterator itmu= (*it).second.begin(); itmu!=(*it).second.end(); ++itmu){ const Symbol* mu=(*itmu).first; /// ... Initialize the traces. list<pair<list<Symbol*>, Evolution<Expression> > > tlist; list<Symbol*> initial_trace; initial_trace.push_back(node); tlist.push_back(make_pair(initial_trace, evolution(constant(0)))); while(tlist.size()>0){ list<pair<list<Symbol*>, Evolution<Expression> > > new_tlist; /// ... For all old partial traces. for(list<pair<list<Symbol*>, Evolution<Expression> > >::iterator llit=tlist.begin(); llit!=tlist.end(); ++llit){ /// cerr<<"\n\tPartial trace: "; /// print_trace(*llit); list<Symbol*>& clist=(*llit).first; // Get the last element in the trace. list<Symbol*>::iterator lit=clist.end(); --lit; // Check whether it is a complete trace. if (*lit==mu){ if (!disjoint((*llit).second, given, range.second, *_pgm, _ra)){ /// ... BINGO, got a valid trace. /// cerr<<"\n\t\tCOMPLETE."; trace[(Symbol*)mu].push_back((*llit).first); } } // Check whether it is a valid trace. EvolutionMap::iterator it1=_evolutions_from_mu.find(*lit); if (it1==_evolutions_from_mu.end()){ /// ... No path to any MU. Discard partial trace, leads nowhere. /// cerr<<"\n\t\tNo path to any MU. Discard."; continue; } map<const Symbol*, Evolution<Expression> >::iterator it2= (*it1).second.find(mu); if (it2==(*it1).second.end()){ /// cerr<<"\n\t\tNo path to current MU. Discard."; /// ... No path to current MU. Discard partial trace. continue; } Evolution<Expression> total=(*it2).second; total+=(*llit).second; if (disjoint(total, given, range.second, *_pgm, _ra)){ /// ... Cannot extend trace, it cannot be within the given range. /// cerr<<"\n\t\ttotal = "<<total; /// cerr<<"\n\t\tgiven = "<<given; /// cerr<<"\n\t\tOutside given range. Discard."; continue; } // Extend traces to all predecessors. set<Symbol*> candidates; const EdgeList& edges=get_reversed_edges(index(*lit)); for (EdgeList::const_iterator cit=edges.begin(); cit!=edges.end(); ++cit){ /// ... Pick up a predecessor. Symbol* cand=(Symbol*)nodes()[(*cit).first]; /// cerr<<"\n\t\t\tExtend trace to "<<cand->name_ref(); /// ... Make up new trace by cloning the old one. pair<list<Symbol*>, Evolution<Expression> > newtrace; newtrace.first=(*llit).first; /// ... Extend new trace. newtrace.first.push_back(cand); newtrace.second=(*llit).second; newtrace.second+=(*cit).second; /// ... Add new trace to candidates. new_tlist.push_back(newtrace); } } // Swap old/new lists. tlist.swap(new_tlist); } } } } /// Get the bacwards trace from 'node' towards 'mu' assuming that /// the length of the path must be exactly 'given_length'. void EvolutionGraph::perfect_trace_from_mu(Symbol* mu, Symbol* node, const Expression& given_length, list<Symbol*>& trace){ if (node==mu){ trace.push_back(mu); return; } Statement* stmt=_loop; if (!stmt){ stmt=&quick_pgm_entry(*_pgm); } RangeAccessor ra(_pgm->range_dict_guarded(), *range_stmt(*stmt)); const EdgeList& edges=get_reversed_edges(index(node)); /// cerr<<"\nnode = "<<node->name_ref(); /// cerr<<"\nmu = "<<mu->name_ref(); Symbol* prev=0; Expression* newlength=0; for (EdgeList::const_iterator cit=edges.begin(); cit!=edges.end(); ++cit){ Symbol* cand=(Symbol*)nodes()[(*cit).first]; /// cerr<<"\ncand = "<<cand->name_ref(); Evolution<Expression> edge=(*cit).second; EvolutionMap::iterator muevit=_evolutions_from_mu.find(cand); if (muevit==_evolutions_from_mu.end()){ /// ... No MU evs for this node. continue; } EvolutionMap::data_type::iterator it=(*muevit).second.find(mu); if (it==(*muevit).second.end()){ /// ... No path from 'mu'. continue; } if (!(*edge.min_difference()==*edge.max_difference())){ /// ... Cannot go on edges with nontrivial range. continue; } Evolution<Expression> muev=(*it).second; Evolution<Expression> total=muev; total+=edge; /// cerr<<"\ntotal = "<<total; /// cerr<<"\ngiven = "<<given_length; /// ... Let us see whether 'total' may contain 'given_length' if ( (! ::p_less_than(given_length, *total.min_difference(), _ra)) && (! ::p_greater_than(given_length, *total.max_difference(), _ra)) ){ if (prev){ /// ... Ambiguous. delete newlength; return; /// p_abort("Ambiguous trace from MU."); } else { prev=cand; newlength=simplify(sub(given_length.clone(), edge.min_difference()->clone())); } } } trace.push_back(node); perfect_trace_from_mu(mu, prev, *newlength, trace); } void EvolutionGraph::perfect_trace_from_mu(Symbol* node, pair<RangeExpr*, bool>& range, list<Symbol*>& trace){ if (back_this_loop.find(index(node))==back_this_loop.end()){ p_abort("Perfect traces only start at BACK nodes."); } /// cerr<<"\nEnter perfect_trace_from_mu : "<<node->name_ref(); /// First, let us find whether there is a unique MU node that can reach /// 'node' such that the range of 'node' through that MU is within 'range'. EvolutionMap::iterator musit=_evolutions_from_mu.find(node); p_assert(musit!=_evolutions_from_mu.end(), "No reaching MU for given node."); EvolutionMap::data_type& mus=(*musit).second; /// silvius: for now, only do it if it is reachable by exactly one MU. if (mus.size()!=1){ return; } const Symbol* mu=(*mus.begin()).first; Symbol* imu; bool imu_is_defined; get_imu(*mu, *_pgm, imu, imu_is_defined); if (!imu_is_defined){ /// ... Unknown definition. No INPUT, no IMU, something is wrong. cerr<<*mu; p_warning("Undefined imu value."); return; } /// For now, only do it if this MU is reachable by itself, and not by /// any other MU. EvolutionMap::iterator mu_mus_it=_mu_evolutions.find(mu); if (mu_mus_it==_mu_evolutions.end()){ return; } EvolutionMap::data_type& mu_mus=(*mu_mus_it).second; if (mu_mus.size()!=1){ return; } if ((*mu_mus.begin()).first!=mu){ return; } /// For now, the only thing we do is check the given range (less the mu input) /// against the extremes of the possible range. For instance, if the possible /// range for an iteration (muev) is [0:1], the iteration count is 10, /// and the given range is [0:0], then the range for each iteration is /// actually [0:0], so only paths made entirely of 0-edges are possible. Evolution<Expression> muev=(*mu_mus.begin()).second; Evolution<Expression> allev=muev; if (_loop){ allev*=iteration_count((DoStmt&)*_loop, *_pgm); } allev+=evolution(id(*imu)); Evolution<Expression> r1,r2; if (range.second){ r1=evolution(infinity(-1), simplify(sub(range.first->lb().clone(), constant(1)))); r2=evolution(simplify(add(range.first->ub().clone(), constant(1))), infinity(+1)); p_warning("Incomplete implementation."); } else { Statement* rs; if (_loop){ rs=_loop; } else { rs=_pgm->stmts().last_ref(); } RangeAccessor ra(_pgm->range_dict_guarded(), *rs); r1=evolution(range.first->lb().clone(), range.first->ub().clone()); /// cerr<<"\nallev = "<<allev /// <<", r1 = "<<r1; Relation r=ra.compare(*r1.min_difference(),*allev.max_difference()); /// cerr<<"\n\tr = "<<r; if (r.is_equal()){ /// ... Got it. perfect_trace_from_mu((Symbol*)mu, node, *muev.max_difference(), trace); } else { r=ra.compare(*r1.max_difference(), *allev.min_difference()); /// cerr<<"\n\tr = "<<r; if (r.is_equal()){ /// ... Got it. perfect_trace_from_mu((Symbol*)mu, node, *muev.min_difference(), trace); } } } } /// Return true only if sure. /// Return false when either compatible or unsure. static bool _incompatible_ranges(const pair<RangeExpr*, bool>& range1, const pair<RangeExpr*, bool>& range2, RangeAccessor& ra){ if (range1.second==false && range2.second==false){ /// ... [.......] /// ... [.......] return (p_less_than(range2.first->ub(), range1.first->lb(), &ra) || p_less_than(range1.first->ub(), range2.first->lb(), &ra)); } if (range1.second==true && range2.second==false){ /// ... .......] [............... /// ... [.......] return (p_greater_equal(range2.first->lb(), range1.first->lb(), &ra) && p_less_equal(range2.first->ub(), range1.first->ub(), &ra)); } if (range1.second==false && range2.second==true){ /// ... [.......] /// ... .......] [............... return (p_greater_equal(range1.first->lb(), range2.first->lb(), &ra) && p_less_equal(range1.first->ub(), range2.first->ub(), &ra)); } if (range1.second==true && range2.second==true){ return false; } p_abort("Sanity check failed: control should have not gotten here."); } /// Execute the program backwards and remember the trace. /// The final value of 'node' must stay within 'range'. /// Stop at the first ambiguity. /// Stop at this loop level (either MU or INPUT site). /// Skip called subprograms and inner loops. void EvolutionGraph::backtrack(Symbol* node, pair<RangeExpr*, bool>& range, list<Symbol*>& trace){ bool from_mu=false; bool from_input=false; /// First, let us find all the possible values for the given node, /// together with their sources (INPUT and MU). list<pair< list<Symbol*>, /// ... E.g. INPUT1, MU1, MU2, ..., MUn, [node] RangeExpr* > > basic_sources, valid_sources; _possible_ranges(*node, basic_sources); list<pair<list<Symbol*>, RangeExpr* > >::iterator it; /// cerr<<"\n\n\nSOURCES for "<<node->name_ref()<<" in "<< /// loop_name(_loop)<<": "; for(it=basic_sources.begin(); it!=basic_sources.end(); ++it){ /// cerr<<"\n\t"; list<Symbol*>::iterator sit; for(sit=(*it).first.begin(); sit!=(*it).first.end(); ++sit){ cerr<<(*sit)->name_ref()<<" "; } /// cerr<<"\t:\t"<<*(*it).second; if (_incompatible_ranges(make_pair((*it).second, false), range, *_ra)){ /// cerr<<"\n\t\tINCOMPATIBLE"; delete (*it).second; } else { /// cerr<<"\n\t\tCOMPATIBLE"; valid_sources.push_back(*it); if (mu_this_loop.find(index(*(*it).first.begin()))!=mu_this_loop.end()){ from_mu=true; } else { from_input=true; } } } /// silvius: for now, do nothing if the loop contains both MU and INPUT /// sources for the given node. if (from_mu && from_input){ /// cerr<<"\nBoth from_mu && from_input."; return; } if (from_mu){ /// ... Trace from MU. /// ... First look for perfect traces. if (back_this_loop.find(index(node))!=back_this_loop.end()){ perfect_trace_from_mu(node, range, trace); if (trace.size()>0){ return; } } /// ... Now look for other traces. map<Symbol*, list<list<Symbol*> > > all_traces; traces_from_mu(node, range, all_traces); if (all_traces.size()!=1){ /// ... Traces from more than one MU. /// cerr<<"\nTraces from more than one MU."; return; } list<list<Symbol*> >& traces=(*all_traces.begin()).second; if (traces.size()!=1){ /// ... Multiple paths from this MU. /// cerr<<"\nMultiple paths from this MU."; return; } trace=*(traces.begin()); } if (from_input){ /// ... Trace from INPUT. trace_from_input(node, range, trace); if (trace.size()>0){ trace.push_front(node); } } } void _print_range(const char* sname, const pair<RangeExpr*, bool>& r); void EvolutionGraph::trace_from_input(Symbol* node, pair<RangeExpr*, bool>& range, list<Symbol*>& trace){ /// cerr<<"\n\n\tEnter trace_from_input ("; /// _print_range(node->name_ref(), range); /// cerr<<") in loop "<<loop_name(_loop); /// print_evolutions(_evolutions_from_input, "from input", cerr); Evolution<Expression> given=evolution(*range.first); set<const Symbol*> solutions; EvolutionMap::iterator it=_evolutions_from_input.find(node); if (it!=_evolutions_from_input.end()){ for(map<const Symbol*, Evolution<Expression> >::iterator it2= (*it).second.begin(); it2!=(*it).second.end(); ++it2){ const Symbol* isym=(*it2).first; Evolution<Expression> ev=_input_values[isym]; ev+=(*it2).second; /// cerr<<"\n\t\t\tLooking at input: "<<isym->name_ref() /// <<" with total range "<<ev; RangeExpr* rev=_range(ev); if (!_incompatible_ranges(range, make_pair(rev, false), *_ra)){ solutions.insert(isym); } delete rev; } /// cerr<<"\nsolution count: "<<solutions.size(); if (solutions.size()==0){ /// ... Could not find any trace for sure. return; } /// cerr<<"\n\t"<<(*solutions.begin())->name_ref(); /// ... Find all edges on all the paths from 'solutions' to 'node' then /// ... go backwards until the first fork. /// ... silvius: will take a shortcut. This hopes that all the edges are 0 /// ... (but is conservative as it may only report more paths). Symbol* current=node; while (1) { /// cerr<<"\n\t\tNow at current "<<current->name_ref(); const EdgeList& edges=get_reversed_edges(index(current)); Symbol* pred=0; for (EdgeList::const_iterator cit=edges.begin(); cit!=edges.end(); ++cit){ /// ... Pick up a parent. Symbol* cand=(Symbol*)nodes()[(*cit).first]; /// cerr<<"\n\t\t\tcand= "<<cand->name_ref(); EvolutionMap::iterator found_ivs=_evolutions_from_input.find(cand); if (found_ivs!=_evolutions_from_input.end()){ // There is a path from an input node to it. for(map<const Symbol*, Evolution<Expression> >::iterator it2= (*found_ivs).second.begin(); it2!=(*found_ivs).second.end(); ++it2){ const Symbol* icand=(*it2).first; /// cerr<<"\n\t\t\t\ticand = "<<icand->name_ref(); /// ... Check whether any of its reaching ivs is in 'solutions' if (solutions.find(icand)!=solutions.end()){ /// cerr<<"\n\t\t\t\thas reaching input with valid path."; /// ... It is on the path to an ivs. if (pred){ /// ... Dichotomy. return; } else { pred=(Symbol*)cand; break; } } } } } if (pred){ /// ... Found a predecessor towards the ivs. /// cerr<<"\n\t\t\t\tadd to trace: "<<pred->name_ref(); trace.push_back(pred); current=pred; } else { /// ... Nowhere to go. return; } } } } void EvolutionGraph::get_trace_details(list<Symbol*>& trace, Evolution<Expression>& ev, Expression*& length, List<Expression>& preds){ /// Initialize results. ev=evolution(constant(0)); length=constant(0); preds.clear(); /// Applicability check. if (trace.size()<2){ return; } /// Chew it up. list<Symbol*>::iterator it1=trace.begin(); list<Symbol*>::iterator it2=it1; ++it2; do { const Evolution<Expression>* edge=get_reversed_edge(*it1, *it2); p_assert(edge, "The given trace contains an edge that is not in the graph."); /// ... Update evolution. ev+=*edge; /// cerr<<"\n\tAt edge: "<<*edge; /// ... Update length. if (*edge->min_difference()==*edge->max_difference()){ length=simplify(add(length, edge->min_difference()->clone())); } else { length=simplify(add(length, sub(id(**it1),id(**it2)))); } /// ... Update predicate list. DefLoc* defloc=_pgm->gsa_deflocs_guarded().find_ref(**it1); if (defloc->stmt_valid()) { Statement& def=defloc->stmt_guarded(); if (def.stmt_class()==ASSIGNMENT_STMT){ if (def.rhs().op()==GAMMA_OP){ List<Expression>& args=def.rhs().parameters_guarded().arg_list(); if (&args[0].symbol()==*it2){ preds.ins_last(def.rhs().gate().clone()); } else { if (&args[1].symbol()==*it1){ preds.ins_last(simplify(not(def.rhs().gate().clone()))); } } } } } /// ... Next, please. it1=it2; ++it2; } while (it2!=trace.end()); } /// Performs forward substitution on demand such as: /// x -> y, ev=[1,1] ==> y = x+1 Expression* EvolutionGraph::substitute(Symbol* given){ /// If it is not here, return. if (!contains(given)){ return 0; } /// If it is a MU, return. if (mu_this_loop.find(index(given))!=mu_this_loop.end()){ return 0; } const EdgeList& edges=get_reversed_edges(index(given)); if (edges.size()!=1){ return 0; } Symbol* pred=nodes()[(*edges.begin()).first]; const Evolution<Expression>& edge=(*edges.begin()).second; if (*edge.min_difference()==*edge.max_difference()){ Expression* predvalue=substitute(pred); if (predvalue==0){ predvalue=id(*pred); } return simplify(add(predvalue, edge.min_difference()->clone())); } return 0; } /*! \brief Return the reaching MU and BACK for this intermediate symbol and return TRUE if they are unique. Also, only return TRUE if MU cannot be reached from any other MU. Also, only return TRUE if MU cannot be reached from any input. */ bool EvolutionGraph::find_unique_mu(Symbol* node, Symbol*& mu, Symbol*& back){ mu=back=0; EvolutionMap::iterator it=_evolutions_from_mu.find(node); /// Find the unique reaching MU. if (it!=_evolutions_from_mu.end()){ /// ... Reaching MUs. if ((*it).second.size()==1){ /// ... GOOD. mu=(Symbol*)(*(*it).second.begin()).first; } else { /// cerr<<"\nRET 1"; return false; } } else { /// ... Cannot be reached by any MU /// cerr<<"\nRET 2"; return false; } /// Make sure that MU can be reached by itself, but no other MUs. it=_mu_evolutions.find(mu); if (it!=_mu_evolutions.end()){ if ((*it).second.size()==1){ if (mu==(*(*it).second.begin()).first){ /// ... GOOD. back=(Symbol*)_back_edges_reversed[mu]; } else { /// ... MU can be reached by another MU. /// cerr<<"\nRET 3"; return false; } } else { /// cerr<<"\nRET 4"; return false; } } else { /// ... MU cannot be reached by any other MU. /// cerr<<"\nRET 5"; return false; } /// Make sure that MU cannot be reached by any INPUT. it=_input2mu_evolutions.find(mu); if (it==_input2mu_evolutions.end()){ /// ... BINGO. return true; } else { /// ... MU can be reached by an INPUT. /// cerr<<"\nRET 6"; return false; } } void EvolutionGraph::enhance(map<Symbol*, Symbol*>& imposed_edges){ p_abort("Not implemented."); } void EvolutionGraph::undo_enhancement(){ p_abort("Not implemented."); } void EvolutionGraph::_p_abort(const char *file, int line, const char *str){ cerr<<"\nEvolutionGraph fatal message follows (see files 'error.veg.f' " <<"and 'error.veg.dot'):" <<"\nIn pgm. "<<_pgm->routine_name_ref() <<", at loop "<<loop_name(_loop); ofstream err("error.veg.f"); program().write(err); err.close(); print_graph("error.veg.dot"); ::_p_abort(file, line, str); } /*! \brief Compute the range of the given expression if it can be inferred from input values only. If so, do not express the input values using RangeDictionary. Otherwise, return 0. */ Expression* EvolutionGraph::range_from_input(Symbol& s){ /// Quick check. If there are any MU nodes reaching this symbol, return 0. if (_evolutions_from_mu.find(&s)!=_evolutions_from_mu.end()){ return 0; } map<const Symbol*, Evolution<Expression> > todo, result; if (!contains(&s)){ /// ... Symbol not in this VEG. return 0; } todo[(const Symbol*)&s]=evolution(0); while(todo.size()>0){ const Symbol* n=(*todo.begin()).first; Evolution<Expression> sofar=(*todo.begin()).second; todo.erase(todo.begin()); if (input_this_loop.find(index((Symbol*)n))!=input_this_loop.end()){ /// ... Made it to the input. sofar+=_input_values[n]; result[n]=sofar; continue; } if (mu_this_loop.find(index((Symbol*)n))!=mu_this_loop.end()){ /// ... Got to a MU, get out. return 0; } /// ... Go on. const EdgeList& edges=get_reversed_edges(index((Symbol*)n)); for (EdgeList::const_iterator cit=edges.begin(); cit!=edges.end(); ++cit){ /// ... Pick up a parent. Symbol* cand=(Symbol*)nodes()[(*cit).first]; Evolution<Expression> ev=sofar; ev+=(*cit).second; todo.insert(make_pair(cand, ev)); } } /// Merge results. p_assert(result.size()>0, "Logic error in EvolutionGraph::range_from_input."); map<const Symbol*, Evolution<Expression> >::iterator it=result.begin(); Evolution<Expression> toret=(*it).second; ++it; for(; it!=result.end(); ++it){ Evolution<Expression> ev=(*it).second; toret=merge_unite(toret, ev, *_pgm, _ra); } return new RangeExpr(toret.min_difference()->clone(), toret.max_difference()->clone()); } /// Export evolution knowledge for a node. void EvolutionGraph:: export_evolutions(Symbol* node, map<const Symbol*, Evolution<Expression> >& muevs, list<pair<const Symbol*, Evolution<Expression> > >& ievs){ if (!contains(node)){ return; } /// MU evs. EvolutionMap::iterator it=_evolutions_from_mu.find(node); if (it!=_evolutions_from_mu.end()){ muevs=(*it).second; } /// INPUT evs. it=_evolutions_from_input.find(node); if (it!=_evolutions_from_input.end()){ for(map<const Symbol*, Evolution<Expression> >::iterator it2= (*it).second.begin(); it2!=(*it).second.end(); ++it2){ const Symbol* isym=(*it2).first; Evolution<Expression> ev=_input_values[isym]; ev+=(*it2).second; ievs.push_back(make_pair(isym, ev)); } } }

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