Polaris: evolution_graph.cc Source File

evolution_graph.cc Go to the documentation of this file. /// /// #include "EvolutionGraph.h" #include "eg_utils.h" #include "evolution_graph.h" #include "affine.h" #include "BackTrace.h" #include "ip_ssa/trans_util.h" #include "ip_ssa/optimize_ssa.h" #include "guarded_values.h" EvolutionGraph* _get_eg(ProgramUnit* pgm, Statement* loop); bool _is_useless(const Evolution<Expression>& ev){ if (ev.min_difference()->op()==INFINITY_OP && ev.max_difference()->op()==INFINITY_OP){ if (ev.min_difference()->value()==-1 && ev.max_difference()->value()==1){ return true; } } return false; } bool _is_useless(const Expression& e){ if (e.op()!=RANGE_OP){ return false; } const RangeExpr& ev=(const RangeExpr&)e; if (ev.lb().op()==INFINITY_OP && ev.ub().op()==INFINITY_OP){ if (ev.lb().sign()==-1 && ev.ub().sign()==1){ return true; } } return false; } /// Will not return the range over the whole loop, but for just an iteration. /// Will only return a range if input values are the only way to generate 'e'. Expression* eg_range_from_input(Expression& e, ProgramUnit& pgm, Statement* loop){ RefList<Symbol> syms; referred_symbols(e, syms); RangeAccessor ra(pgm.range_dict_guarded(), *pgm.stmts().first_ref()); RefSet<Symbol> vars_to_eliminate; for(Iterator<Symbol> sit=syms; sit.valid(); ++sit){ Expression* r=_get_eg(&pgm, loop)->range_from_input(sit.current()); if (r){ ra.set_range(sit.current(), r); vars_to_eliminate.ins(sit.current()); } } /// cerr<<"\nBEFORE subst: "<<e; Expression* toret=e.clone(); if (vars_to_eliminate.entries()){ toret=ra.eliminate_vars(toret, &vars_to_eliminate); } /// cerr<<"\nAFTER subst: "<<*toret; return toret; } /// 'sym' is the gsa base of a symbol. bool is_defined(Symbol& sym, Statement& stmt){ if (called_pgm(stmt)){ /// ... Call or entry site. if (stmt.stmt_class()==ENTRY_STMT){ return false; } if (!has_maymod(stmt)){ return true; } if (is_var_in_maymod(sym, stmt)){ return true; } if (stmt.stmt_class()==ASSIGNMENT_STMT){ if (&sym==gsa_base(*stmt.lhs().base_variable_ref())){ return true; } else { return false; } } else { return false; } } else { /// ... Not a call site. for(Iterator<Expression> eit=stmt.out_refs(); eit.valid(); ++eit){ if (&sym==gsa_base(*eit.current().base_variable_ref())){ return true; } else { return false; } } return false; } } /// Find all scalar sources for the given array. /// Return true only if all its value sources are scalar. /// Return values relative to the body of the given loop. /// Since this is an array, must take into account all iterations /// from 1 to i. /// silvius: for now, this is intraprocedural. /// Also, when we extend the VEG to /// array references, this function should not be needed anymore. bool _find_scalar_sources(ProgramUnit& pgm, Statement* loop, Expression& expr, List<Expression>& sources){ p_assert(expr.op()==ARRAY_REF_OP, "Not an array."); if (loop){ p_assert(loop->stmt_class()==DO_STMT, "Not a loop."); } Symbol* sym=gsa_base(expr.array().symbol()); /// 1. The array must not be defined outside the loop. if (loop!=0){ for (Statement* ps=pgm.stmts().first_ref(); ps!=loop; ps=ps->next_ref()){ if (is_defined(*sym, *ps)){ /// cerr<<"\n\t"<<sym->name_ref()<<" "<<*ps; /// cerr<<"\n\tRET 1"; return false; } } for (Statement* ps=loop->follow_ref(); ps; ps=ps->next_ref()){ if (is_defined(*sym, *ps)){ /// ... It is OK only if it is an ETA. if (ps->stmt_class()==ASSIGNMENT_STMT){ if (ps->rhs().op()==ETA_OP){ continue; } } /// cerr<<"\nDefined at stmt "<<*ps; /// cerr<<"\n\tRET 2"; return false; } } } /// 2. If the array is defined within the loop, make sure it is defined /// in an assignement statement, and that RHS is made only of scalars. RefList<Expression> primary_sources; Statement* begin; Statement* end; if (loop){ begin=loop->next_ref(); end=loop->follow_ref(); } else { begin=pgm.stmts().first_ref(); end=pgm.stmts().last_ref(); } for (Statement* ps=begin; ps!=end; ps=ps->next_ref()){ if (is_defined(*sym, *ps)){ if (ps->stmt_class()!=ASSIGNMENT_STMT){ /// cerr<<"\n\tRET 3"; return false; } switch (ps->rhs().op()){ case MU_OP: case GAMMA_OP: case THETA_OP: case ETA_OP: continue; } /// cerr<<"\n\t\talpha = "<<ps->rhs(); Expression& rhs=ps->rhs().parameters_guarded().arg_list()[1]; /// cerr<<"\n\t\tnoalpha = "<<ps->rhs(); if (rhs.op()==FUNCTION_CALL_OP){ /// cerr<<"\n\tRET 4"; return false; } RefList<Symbol> syms; referred_symbols(rhs, syms); for(Iterator<Symbol> sit=syms; sit.valid(); ++sit){ /// cerr<<"\n\t"<<sit.current().name_ref(); if (!sit.current().is_scalar()){ /// cerr<<"\n\tRET 5"; return false; } } /// ... Add rhs to the preliminary list. primary_sources.ins_last(rhs); } } /// cerr<<"\n\tps = "<<primary_sources; /// Go through all the sources and find their ranges at the level of the body /// of the given loop. List<Expression> per_iteration; EvolutionGraph* eg=_get_eg(&pgm, (DoStmt*)loop); for(Iterator<Expression> eit=primary_sources; eit.valid(); ++eit){ Expression* epi=eit.current().clone(); epi=eg->_global_range_per_iteration(epi, (DoStmt*)loop); per_iteration.ins_last(epi); } /// Now expand the per-iteration descriptors over interval [1:i]. /// silvius: take a shortcut here. p_warning("Incomplete implementation."); sources=per_iteration; return true; } /// Will not return the range over the whole loop, but for iterations 1 to i. /// Will only return a range if input values are the only way to generate 'e'. Expression* eg_range_array_1_to_i(Expression& expr, ProgramUnit& pgm, Statement* loop){ /// For now, this will only work if the array is a parasite of /// some scalars. p_assert(expr.op()==ARRAY_REF_OP, "Not an array."); Symbol& sym=expr.array().symbol(); /// cerr<<"\nLooking for ss for "<<sym.name_ref(); List<Expression> sources; bool found=_find_scalar_sources(pgm, loop, expr, sources); if (!found){ /// cerr<<"\n\t_find_scalar_sources = false"; return new RangeExpr(infinity(-1), infinity(+1)); } Statement* rs=loop; if (rs==0){ rs=pgm.stmts().last_ref(); } else { rs=rs->follow_ref(); } RangeAccessor ra(pgm.range_dict_guarded(), *rs); if (sources.entries()==0){ /// ... Not defined in this pgm. return new RangeExpr(infinity(-1), infinity(+1)); } Expression* e=sources.grab(0); ra.set_range(sym, e); while(sources.entries()){ e=sources.grab(0); ra.union_range(sym, *e); delete e; } return ra.get_range_ref(sym)->clone(); } /// Return the range over the whole loop. Expression* eg_range(Expression& e, ProgramUnit& pgm, Statement* loop){ Expression* toret=e.clone(); if (loop==0){ /// ... Go back to the inputs if given. RefList<Symbol> syms; referred_symbols(*toret, syms); if (!pgm.range_dict_valid()){ pgm.range_dict(new AIRangeDict(pgm)); } RangeAccessor ra(pgm.range_dict_guarded(), *pgm.stmts().first_ref()); RefSet<Symbol> vars_to_eliminate; for(Iterator<Symbol> sit=syms; sit.valid(); ++sit){ Expression* r=_get_eg(&pgm, loop)->range_from_input(sit.current()); if (r){ ra.set_range(sit.current(), r); vars_to_eliminate.ins(sit.current()); } } toret=ra.eliminate_vars(toret, &vars_to_eliminate); if (toret->op()==OMEGA_OP){ delete toret; toret=new RangeExpr(infinity(-1), infinity()); } } if (_is_useless(*toret)){ /// ... Use the original, we did not do better. delete toret; toret=e.clone(); } EvolutionGraph* global=_get_eg(&pgm, loop); toret=global->_global_range(toret, (DoStmt*)loop); if (toret->op()==OMEGA_OP){ delete toret; /// cerr<<"\n2. eg_range Return INF: "; return new RangeExpr(infinity(-1), infinity()); } else { /// cerr<<"\n3. eg_range Return "<<*toret; return toret; } } static RangeAccessor* _get_ra(ProgramUnit& pgm, Statement* domain, Expression& e1, Expression& e2){ RefList<Symbol> syms; referred_symbols(e1, syms); referred_symbols(e2, syms); RefList<Symbol> vars; for (Iterator<Symbol> sit=syms; sit.valid(); ++sit){ if (sit.current().sym_class()==VARIABLE_CLASS){ vars.ins_last(sit.current()); } } /// cerr<<"\n\n\tvars = "<<vars; RangeAccessor* ra=0; switch(vars.entries()){ case 1: { DefLoc* defloc=pgm.gsa_deflocs_guarded().find_ref(vars[0]); /// ... p_assert(defloc, "Could not find definition for symbol."); if(defloc) { if (defloc->stmt_valid()){ Statement* rs=&defloc->stmt_guarded(); ra=new RangeAccessor(pgm.range_dict_guarded(), *rs); } } } break; case 2: { Statement* rs1=0; Statement* rs2=0; DefLoc* defloc=pgm.gsa_deflocs_guarded().find_ref(vars[0]); /// ... p_assert(defloc, "Could not find definition for symbol."); if(defloc) { if (defloc->stmt_valid()){ rs1=&defloc->stmt_guarded(); } defloc=pgm.gsa_deflocs_guarded().find_ref(vars[1]); if(defloc) { p_assert(defloc, "Could not find definition for symbol."); if (defloc->stmt_valid()){ rs2=&defloc->stmt_guarded(); } if (rs1 && rs2){ /// cerr<<"\n\t\t\tcase 2"; ra=new RangeAccessor(pgm.range_dict_guarded(), *rs1->next_ref(), *rs2->next_ref(), false); } else { if (rs1) { /// cerr<<"\n\t\t\tcase 2.1"; ra=new RangeAccessor(pgm.range_dict_guarded(), *rs1->next_ref()); } else { if (rs2){ /// cerr<<"\n\t\t\tcase 2.2"; ra=new RangeAccessor(pgm.range_dict_guarded(), *rs2->next_ref()); } } } } } } break; case 0: break; default: break; } if (ra==0){ Statement* rs; if (domain){ /// ... Matching ENDDO. rs=domain->follow_ref(); } else { /// ... FLOWEXIT. rs=pgm.stmts().last_ref(); } ra=new RangeAccessor(pgm.range_dict_guarded(), *rs); } return ra; } static Relation _eg_compare(Expression* r1, Expression* r2, ProgramUnit& pgm, Statement* domain){ /// Find out the best place to compare them. /// silvius: I think this is somewhere after all the definitions of the /// symbols contained in the two expressions. /// only do it if integer exprs. if (r1->type().data_type()!=INTEGER_TYPE || r2->type().data_type()!=INTEGER_TYPE){ return Relation(false, false, false); } /// Perform the comparison. Expression* l; if (r1->op()==RANGE_OP){ l=&((RangeExpr*)r1)->lb(); } else { l=r1; } Expression* u; if (r2->op()==RANGE_OP){ u=&((RangeExpr*)r2)->ub(); } else { u=r2; } /// cerr<<"\n\t\tcomparing: "<<*l<<", "<<*u<<"\n"; RangeAccessor* ra = _get_ra(pgm, domain, *l, *u); Relation toret=ra->compare(*l, *u); delete ra; /// cerr<<"\n\t\ttresult = "<<toret; if (toret.is_greater_than()){ /// ... r1 > r2 /// cerr<<"\n\treturning "<<toret; return toret; } if (toret.is_greater_equal()){ /// cerr<<"\n\treturning "<<toret; return toret; } /// Try it the other way. if (r2->op()==RANGE_OP){ l=&((RangeExpr*)r2)->lb(); } else { l=r2; } if (r1->op()==RANGE_OP){ u=&((RangeExpr*)r1)->ub(); } else { u=r1; } ra = _get_ra(pgm, domain, *l, *u); toret=ra->compare(*l, *u); delete ra; /// cerr<<"\n\t\tcomparing: "<<*l<<", "<<*u; /// cerr<<"\n\t\tresult = "<<toret; if (toret.is_greater_than()){ /// ... r2 > r1, so return r1 < r2 /// cerr<<"\n\t\treturning <"; return Relation(true, false, false); } if (toret.is_greater_equal()){ /// ... r2 > r1, so return r1 < r2 /// cerr<<"\n\t\treturning <"; return Relation(true, true, false); } /// Could not find any useful result. /// cerr<<"\n\t\treturning UNKNOWN"; return Relation(false, false, false); } Relation eg_compare(Expression& e1, Expression& e2, ProgramUnit& pgm){ /// Find the innermost loop that contains all the definitions /// of all the variables in e1 and e2. RefList<Symbol> syms; referred_symbols(e1, syms); /// cerr<<"\n\te1: "<<e1; referred_symbols(e2, syms); /// cerr<<"\te2: "<<e2; set<DoStmt*> loops; for(Iterator<Symbol> sit=syms; sit.valid(); ++sit){ loops.insert(def_loop(sit.current(), pgm)); } DoStmt* domain=common_outer(loops); Expression* r1=e1.clone(); Expression* r2=e2.clone(); /// cerr<<"\n\tr1: "<<*r1; /// cerr<<"\tr2: "<<*r2; while (1){ /// cerr<<"\n\tdomain is "; /// if (domain){ /// cerr<<domain->get_loop_name(); /// } else { /// cerr<<pgm.routine_name_ref(); /// } /// ... Now get ranges over the domain for the expressions. EvolutionGraph* eg=_get_eg(&pgm, domain); r1=eg_forward_substitute(pgm, domain, r1); r2=eg_forward_substitute(pgm, domain, r2); /// cerr<<"\n\t\texprs are: "<<*r1<<", "<<*r2; r1=eg->_global_range(r1, domain); r2=eg->_global_range(r2, domain); if (r1==0 || r2==0){ return Relation(); } /// cerr<<"\n\t\tranges are: "<<*r1<<", "<<*r2; Relation toret=_eg_compare(r1, r2, pgm, domain); if (!toret.is_unknown()){ /// ... Found a relation. /// cerr<<"\nReturning 1 "<<toret; delete r1; delete r2; return toret; } if (domain==0){ /// ... Found no relation. delete r1; delete r2; /// cerr<<"\nReturning 2 "<<toret; if (toret.is_unknown()){ /// ... Try comparison using regular ranges. /// cerr<<"\ne1 = "<<e1<<", e2 = "<<e2; RangeAccessor* ra = _get_ra(pgm, domain, e1, e2); if (e1.type().data_type()==INTEGER_TYPE && e1.type().data_type()==INTEGER_TYPE){ toret=ra->compare(e1, e2); delete ra; return toret; } else { return Relation(); } } return toret; } else { /// ... Try outer domains. domain=(DoStmt*)domain->outer_ref(); } } } Expression* eg_distance(ProgramUnit& pgm, DoStmt& loop, Symbol& left, Symbol& right){ /// Compute it. EvolutionGraph* eg_both=_get_eg(&pgm, &loop); Expression* toret=eg_both->min_distance(left, right); return toret; } /// Measures the distance between sets of expressions across an iteration, /// such as: {3+5*x, 2+5*y} to {6+5*z, 1+5*t} static Expression* eg_distance_1_dim(ProgramUnit& pgm, DoStmt& loop, RangeAccessor& ra, vector<vector<Symbol*> >& args_left, vector<vector<Expression*> >& coeffs_left, vector<vector<Symbol*> >& args_right, vector<vector<Expression*> >& coeffs_right){ /// First check that they all have the same coefficients. Expression& model=*coeffs_left[0][0]; unsigned int i,j; for(i=1; i<args_left.size(); ++i){ if (!(*coeffs_left[i][0]==model)){ return constant(0); } } for(i=0; i<args_right.size(); ++i){ if (!(*coeffs_right[i][0]==model)){ return constant(0); } } /// Put together the result. Expression* toret=infinity(1); for(i=0; i<args_left.size(); ++i){ for(j=0; j<args_right.size(); ++j){ /// ... May have different free terms. Expression* candidate=simplify(sub(coeffs_right[j][1]->clone(), coeffs_left[i][1]->clone())); /// ... May have different variables. Expression* sym_dist=eg_distance(pgm, loop, *args_left[i][0], *args_right[j][0]); /// ... Have the same coefficient. candidate=simplify(add(candidate, mul(sym_dist, model.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 MAX. 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)); } } } } } if (toret->op()==INFINITY_OP){ /// ... Report distance conservatively. delete toret; return constant(0); } else { return toret; } } static void _cleanup_coeffs(vector<vector<Expression*> >& coeffs_left, vector<vector<Expression*> >& coeffs_right){ unsigned int i,j; for(i=0; i<coeffs_left.size(); ++i){ for(j=0; j<coeffs_left[i].size(); ++j){ delete coeffs_left[i][j]; } } for(i=0; i<coeffs_right.size(); ++i){ for(j=0; j<coeffs_right[i].size(); ++j){ delete coeffs_right[i][j]; } } } /*! \brief Returns the minimum distance between two elements in left and right. Conservative result: constant(0). Will only compute it for affine functions with identical linear coefficients. */ Expression* eg_distance(ProgramUnit& pgm, DoStmt& loop, List<Expression>& left, List<Expression>& right, set<Symbol*>& variants){ /// silvius: for now do it only if /// the linear coefficients of the affine expression correspond for a /// one-to-one correspondence of the variants. /// Handle cases like: 3+5*y+x and x+4+5*y. /// silvius: in the future, make some repository of symbol distances to /// solve the general problem efficiently. if (left.entries()==0 || right.entries()==0){ return constant(0); } /// cerr<<"\nleft = "<<left; /// cerr<<"\nright = "<<right; /// Check that all symbols are scalar integers and that /// all expresssions are affine functions of loop variants. vector<vector<Symbol*> > args_left, args_right; vector<vector<Expression*> > coeffs_left, coeffs_right; if (!check_scalars_affine(left, pgm, loop, args_left, coeffs_left)){ _cleanup_coeffs(coeffs_left, coeffs_right); return constant(0); } if (!check_scalars_affine(right, pgm, loop, args_right, coeffs_right)){ _cleanup_coeffs(coeffs_left, coeffs_right); return constant(0); } RangeAccessor ra(pgm.range_dict_guarded(), *loop.follow_ref()); /// silvius: consider first the case when they each have exactly one /// variable (possibly not the same). unsigned int i,j; bool all_1_dim=true; for(i=0; i<args_left.size(); ++i){ if (args_left[i].size()!=1){ all_1_dim=false; break; } } if (all_1_dim){ for(i=0; i<args_right.size(); ++i){ if (args_right[i].size()!=1){ all_1_dim=false; break; } } } if (all_1_dim){ Expression* toret= eg_distance_1_dim(pgm, loop, ra, args_left, coeffs_left, args_right, coeffs_right); _cleanup_coeffs(coeffs_left, coeffs_right); return toret; } /// Check that they have the same vars and coeffs (except for the free term). map<Symbol*, Expression*> args_coeffs; vector<Symbol*> args_model=args_left[0]; vector<Expression*> coeffs_model=coeffs_left[0]; args_model=args_left[0]; for(j=0; j<args_model.size(); ++j){ variants.insert(args_model[j]); args_coeffs[args_model[j]]=coeffs_model[j]; } for(i=0; i<args_left.size(); ++i){ /// ... First check the number of variables. if (args_left[i].size()!=args_model.size()){ _cleanup_coeffs(coeffs_left, coeffs_right); return constant(0); } else { for(j=0; j<args_left[i].size(); ++j){ map<Symbol*, Expression*>::iterator found= args_coeffs.find(args_left[i][j]); if (found==args_coeffs.end()){ // Variable not found in model. _cleanup_coeffs(coeffs_left, coeffs_right); return constant(0); } else { if (!(*(*found).second==*coeffs_left[i][j])){ _cleanup_coeffs(coeffs_left, coeffs_right); return constant(0); } } } } } for(i=0; i<args_right.size(); ++i){ /// ... First check the number of variables. if (args_right[i].size()!=args_model.size()){ _cleanup_coeffs(coeffs_left, coeffs_right); return constant(0); } else { for(j=0; j<args_right[i].size(); ++j){ map<Symbol*, Expression*>::iterator found= args_coeffs.find(args_right[i][j]); if (found==args_coeffs.end()){ // Variable not found in model. _cleanup_coeffs(coeffs_left, coeffs_right); return constant(0); } else { if (!(*(*found).second==*coeffs_right[i][j])){ _cleanup_coeffs(coeffs_left, coeffs_right); return constant(0); } } } } } /// Find largest free term in 'left' Expression* toret=infinity(-1); for(i=0; i<args_left.size(); ++i){ Expression& candidate=*coeffs_left[i][coeffs_left[i].size()-1]; if (candidate==*toret){ /// ... Discard candidate. } else { if (p_greater_than(candidate, *toret, &ra)){ /// ... Keep candidate. delete toret; toret=candidate.clone(); } else { if (p_less_than(candidate, *toret, &ra)){ // Discard candidate. } else { // Incomparable, keep MAX. Symbol* best_op_sym=pgm.symtab().find_ref("MAX"); p_assert(best_op_sym, "MAX intrinsic not in symbol table"); toret=intrinsic_call(id(*best_op_sym), comma(toret, candidate.clone())); } } } } Expression* max_ftl=toret; /// Find smallest free term in 'right' toret=infinity(1); for(i=0; i<args_right.size(); ++i){ Expression& candidate=*coeffs_right[i][coeffs_right[i].size()-1]; if (candidate==*toret){ /// ... Discard candidate. } else { if (p_less_than(candidate, *toret, &ra)){ /// ... Keep candidate. delete toret; toret=candidate.clone(); } else { if (p_greater_than(candidate, *toret, &ra)){ // Discard candidate. } else { // Incomparable, keep MAX. 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.clone())); } } } } Expression* min_ftr=toret; /// Make up the total distance. toret=simplify(sub(min_ftr, max_ftl)); for(unsigned int i=0; i<args_model.size(); ++i){ Symbol& arg=*args_model[i]; Expression& coeff=*coeffs_model[i]; Expression* sym_dist=eg_distance(pgm, loop, arg, arg); toret=simplify(add(toret, mul(sym_dist, coeff.clone()))); } /// Return. _cleanup_coeffs(coeffs_left, coeffs_right); if (toret->op()==INFINITY_OP){ /// ... Report distance conservatively. delete toret; return constant(0); } else { /// cerr<<"\nRETURNING: "<<*toret; return toret; } } bool eg_contradictory_gate(Expression& gate, ProgramUnit& pgm){ /// cerr<<"\nEnter contradictory gate with "<<gate; if (gate.op()==AND_OP){ for(Iterator<Expression> eit=gate.arg_list(); eit.valid(); ++eit){ if (eg_contradictory_gate(eit.current(), pgm)){ return true; } } } else { switch (gate.op()){ case NE_OP: case EQ_OP: case LT_OP: case GT_OP: case LE_OP: case GE_OP: { /// cerr<<"\n\tcomparing "<<gate.arg_list()[0] /// <<" and "<<gate.arg_list()[1]; Relation lr=eg_compare(gate.arg_list()[0], gate.arg_list()[1], pgm); /// cerr<<"\n\t\tRelation = "<<lr; if (lr.is_less_than() && (gate.op()==GT_OP || gate.op()==GE_OP || gate.op()==EQ_OP )){ /// cerr<<"\n\tTRUE."; return true; } if (lr.is_greater_than() && (gate.op()==LT_OP || gate.op()==LE_OP || gate.op()==EQ_OP )){ /// cerr<<"\n\tTRUE."; return true; } if (lr.is_less_equal() && gate.op()==GT_OP){ /// cerr<<"\n\tTRUE."; return true; } if (lr.is_greater_equal() && gate.op()==LT_OP){ /// cerr<<"\n\tTRUE."; return true; } if (lr.is_equal() && (gate.op()==GT_OP || gate.op()==LT_OP || gate.op()==NE_OP )){ /// cerr<<"\n\tTRUE."; return true; } if (lr.is_not_equal() && gate.op()==EQ_OP){ /// cerr<<"\n\tTRUE."; return true; } /// cerr<<"\n\t\tfailed"; } } } /// cerr<<"\n\tFAILED."; return false; } bool eg_redundant_gate(Expression& gate, ProgramUnit& pgm){ Expression* g=simplify(not(gate.clone())); bool toret=eg_contradictory_gate(*g, pgm); delete g; return toret; } /*! \brief Get the evolution summaries for all evolutions from a MU to a BACK node that pass through sym in loop dostmt in pgm. All evolutions that MAY be in the given range are reported. */ void eg_get_ev_summary(ProgramUnit& pgm, DoStmt* dostmt, Symbol& sym, pair<RangeExpr*, bool>& range, vector<pair<List<Expression>, pair<RangeExpr*, Expression*> > >& evs, Symbol*& mu){ EvolutionGraph* eg=_get_eg(&pgm, dostmt); /// silvius: for now only do it if the given sym is only reachable from /// one MU which has exactly one BACK. mu=0; Symbol* back=0; if (!eg->find_unique_mu(&sym, mu, back)){ /// cerr<<"\n\t\tfind_unique_mu = FALSE."; return; } /// cerr<<"\nmu = "<<mu->name_ref(); /// cerr<<"\nback = "<<back->name_ref(); /// Get traces. map<Symbol*, list<list<Symbol*> > > traces; eg->traces_from_mu(back, range, traces); /// Get details for every trace originating from MU. list<list<Symbol*> >& trace=traces[mu]; list<list<Symbol*> >::iterator it; for(it=trace.begin(); it!=trace.end(); ++it){ evs.push_back(make_pair(List<Expression>(), make_pair((RangeExpr*)0, (Expression*)0))); pair<List<Expression>, pair<RangeExpr*, Expression*> >& top= evs[evs.size()-1]; Evolution<Expression> ev; eg->get_trace_details(*it, ev, top.second.second, top.first); top.second.first=new RangeExpr(ev.min_difference()->clone(), ev.max_difference()->clone()); } } /*! \brief Returns true if the given sym forms a nondecreasing sequence within the given loop. */ bool eg_nondecreasing(ProgramUnit& pgm, DoStmt& dostmt, Symbol& sym){ EvolutionGraph* eg=_get_eg(&pgm, &dostmt); return eg->sequence_type(sym) == EvolutionGraph::ST_NONDECREASING; } static void _find_call_sites(ProgramUnit& callee, vector<pair<ProgramUnit*, Statement*> >&call_sites){ RefSet<ProgramUnit>& callers=callee.called_by(); for(Iterator<ProgramUnit> pit=callers; pit.valid(); ++pit){ ProgramUnit& pgm=pit.current(); Iterator<Statement> stit=pgm.stmts().iterator(); for( ; stit.valid(); ++stit){ Statement& stmt=stit.current(); if (called_pgm(stmt)==&callee){ call_sites.push_back(make_pair(&pgm, &stmt)); } } } } RangeExpr* program_wide_range(ProgramUnit& pgm, Expression& expr){ /// cerr<<"\nComputing local pgm range in pgm. "<<pgm.routine_name_ref() /// <<"for "<<expr; Expression* local_pgm_range=eg_range(expr, pgm, 0); /// cerr<<"\nLocal pgm range in pgm. "<<pgm.routine_name_ref() /// <<"for "<<expr<<" is "<<*local_pgm_range; /// Express it using only translatable symbols (GSA number == 0) RefSet<Symbol> vars_to_eliminate; RangeAccessor ra(pgm.range_dict_guarded(), *pgm.stmts().last_ref()); RefList<Symbol> syms; referred_symbols(*local_pgm_range, syms); for(Iterator<Symbol> sit=syms; sit.valid(); ++sit){ Symbol& sym=sit.current(); bool range_is_set= (ra.get_range_ref(sym)!=0); vars_to_eliminate.ins(sym); List<RangeExpr> sym_ranges; /// cerr<<"\n\tFor symbol "<<sym.name_ref(); map<const Symbol*, Evolution<Expression> > muevs; list<pair<const Symbol*, Evolution<Expression> > > ievs; _get_eg(&pgm, 0)->export_evolutions(&sym, muevs, ievs); map<const Symbol*, Evolution<Expression> >::iterator muit; list<pair<const Symbol*, Evolution<Expression> > >::iterator iit; for(muit=muevs.begin(); muit!=muevs.end(); ++muit){ /// cerr<<"\n\t\tMU: "<<(*muit).first->name_ref()<<" : "<<(*muit).second; /// ... Must trace it within all callers. vector<pair<ProgramUnit*, Statement*> > call_sites; _find_call_sites(pgm, call_sites); vector<pair<ProgramUnit*, Statement*> >::iterator it; for(it=call_sites.begin(); it!=call_sites.end(); ++it){ ProgramUnit& caller=*(*it).first; Statement& callsite=*(*it).second; Translator trans(caller, callsite); /// ... Translate the MU. Expression* t=translate_and_reshape(trans, pgm, caller, callsite, id(*(*muit).first)); /// cerr<<"\n\t\tt = "<<*t; /// ... Find its global range recursively. RangeExpr* trange=program_wide_range(caller, *t); /// cerr<<"\n\t\ttrange = "<<*trange; delete t; /// ... Add the range from MU to the global range of MU. RangeExpr* total= new RangeExpr(simplify(add((*muit).second.min_difference()->clone(), trange->lb().clone())), simplify(add((*muit).second.max_difference()->clone(), trange->ub().clone()))); /// cerr<<"\n\t\ttotal = "<<*total; delete trange; /// ... Save contribution of 'total'. if (range_is_set){ ra.union_range(sym, *total); delete total; } else { ra.set_range(sym, total); range_is_set=true; } } } for(iit=ievs.begin(); iit!=ievs.end(); ++iit){ /// cerr<<"\n\t\tINPUT: "<<(*iit).first->name_ref()<<" : "<<(*iit).second; /// ... Insert range. RangeExpr r((*iit).second.min_difference()->clone(), (*iit).second.max_difference()->clone()); ra.union_range(sym, r); } /// cerr<<"\n\tGlobal range: "; const Expression* r=ra.get_range_ref(sym); /// if (r){ /// cerr<<*r; /// } } /// cerr<<"\nTo eliminate: "<<vars_to_eliminate; /// cerr<<"\nra = "<<ra; Expression* toret=ra.eliminate_vars(local_pgm_range, &vars_to_eliminate); /// cerr<<"\nReturning: "<<*toret; /// cerr<<"\nProgram wide range in pgm. "<<pgm.routine_name_ref() /// <<"for "<<expr<<" is "<<*toret; if(toret->op()!=RANGE_OP){ return new RangeExpr(toret, toret->clone()); } return (RangeExpr*)toret; }

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