Polaris: eg_utils.cc Source File

eg_utils.cc Go to the documentation of this file. /// #include <set> #include <vector> #include "ProgramUnit.h" #include "eg_utils.h" #include "Range/AIRangeDict.h" #include "utilities/stmt_util.h" #include "ip_ssa/ip_ssa.h" static DoStmt* LOOP_ROOT=0; /// first contained in second. bool inner(DoStmt* first, DoStmt* second){ if (first==second){ return true; } while(first){ if (first==second){ return true; } first=(DoStmt*)first->outer_ref(); } if (first==second){ return true; } return false; } /// first contains second. bool outer(DoStmt* first, DoStmt* second){ return inner(second, first); } DoStmt* common_outer(DoStmt* first, DoStmt* second){ /// Quick test. if (first==LOOP_ROOT || second==LOOP_ROOT){ return LOOP_ROOT; } /// Store all loops outer to 'first'. set<DoStmt*> outer_first; while(first){ if (first==second){ /// ... Second is outer to first. return first; } outer_first.insert(first); first=(DoStmt*)first->outer_ref(); } while(second){ if (outer_first.find(second)!=outer_first.end()){ /// ... One of 'first's parents is a parent of second. return second; } second=(DoStmt*)second->outer_ref(); } /// Both are first level loops. return LOOP_ROOT; } DoStmt* common_outer(set<DoStmt*>& loops){ set<DoStmt*>::iterator it=loops.begin(); if (it==loops.end()){ return LOOP_ROOT; } DoStmt* toret=*it; for( ; it!=loops.end(); ++it){ DoStmt* second=*it; toret=common_outer(toret, second); if (toret==LOOP_ROOT){ return toret; } } return toret; } /*! \brief Returns loop header if the given symbol appears in the LHS of a MU. */ DoStmt* loop(const Symbol& sym, ProgramUnit& pgm){ 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){ return (DoStmt*)&def; } if (def.stmt_class()==ASSIGNMENT_STMT){ if (def.rhs().op()==MU_OP){ Statement* ps=&def; while (ps->stmt_class()!=DO_STMT){ ps=ps->prev_ref(); p_assert(ps, "No DO before MU assignment."); } return (DoStmt*)ps; } } } } return (DoStmt*)0; } /*! \brief Returns header of innermost loop where this symbol is defined. */ DoStmt* def_loop(const Symbol& sym, ProgramUnit& pgm){ DefLoc* defloc=pgm.gsa_deflocs_guarded().find_ref(sym); if (defloc){ if (defloc->stmt_valid()){ Statement* ps=&defloc->stmt_guarded(); if (ps->stmt_class()==DO_STMT){ return (DoStmt*)ps; } else { return (DoStmt*)ps->outer_ref(); } } } return (DoStmt*)0; } Expression* iteration_count(DoStmt& loop, ProgramUnit& pgm){ Expression* toret=simplify(div(add(sub(loop.limit().clone(), loop.init().clone()), loop.step().clone()), loop.step().clone())); if (!pgm.range_dict_valid()){ pgm.range_dict(new AIRangeDict(pgm)); } RangeAccessor ra(pgm.range_dict_guarded(), *range_stmt(loop)); switch (ra.signz(*toret)){ case POS_EXPR: return toret; case ZERO_EXPR: delete toret; return constant(0); case NEG_EXPR: return simplify(sub(constant(0), toret)); case POS_NEG_EXPR: default: { Symbol *max_sym = pgm.symtab().find_ref("MAX"); p_assert(max_sym, "MAX intrinsic not in symbol table"); toret=intrinsic_call(id(*max_sym), comma(toret, constant(0))); return toret; } } } Expression* last_value(DoStmt& loop, ProgramUnit& pgm){ return simplify(add(loop.init().clone(), mul(sub(iteration_count(loop, pgm), constant(1)), loop.step().clone()))); } void sort_loops_preorder_lr(Statement& first, Statement& last, DoStmt* outer, vector<DoStmt*>& sorted){ sorted.push_back(outer); for(Statement* ps=&first; ps && ps!=&last; ps=ps->next_ref()){ if(ps->stmt_class()==DO_STMT){ sort_loops_preorder_lr(*ps->next_ref(), *ps->follow_ref(), (DoStmt*)ps, sorted); ps=ps->follow_ref(); } } } void sort_loops_postorder_lr(Statement& first, Statement& last, DoStmt* outer, vector<DoStmt*>& sorted){ for(Statement* ps=&first; ps && ps!=&last; ps=ps->next_ref()){ if(ps->stmt_class()==DO_STMT){ sort_loops_postorder_lr(*ps->next_ref(), *ps->follow_ref(), (DoStmt*)ps, sorted); ps=ps->follow_ref(); } } sorted.push_back(outer); } bool p_less_equal(const Expression& e1, const Expression& e2, RangeAccessor* ra){ if (e1==e2){ return true; } if (ra) { Relation rel=ra->compare(e1, e2); if (rel.is_less_equal()){ return true; } } Expression* diff=simplify(sub(e1.clone(), e2.clone())); if (diff->op()==INTEGER_CONSTANT_OP){ if (diff->value()<=0){ delete diff; return true; } } else { if (diff->op()==INFINITY_OP){ bool toret=(diff->sign()==-1); delete diff; return toret; } } delete diff; /// Be conservative. return false; } bool p_greater_equal(const Expression& e1, const Expression& e2, RangeAccessor* ra){ if (e1==e2){ return true; } if (ra) { Relation rel=ra->compare(e1, e2); if (rel.is_greater_equal()){ return true; } } Expression* diff=simplify(sub(e1.clone(), e2.clone())); if (diff->op()==INTEGER_CONSTANT_OP){ if (diff->value()>=0){ delete diff; return true; } } else { if (diff->op()==INFINITY_OP){ bool toret=(diff->sign()==1); delete diff; return toret; } } delete diff; /// Be conservative. return false; } bool p_less_than(const Expression& e1, const Expression& e2, RangeAccessor* ra){ /// cerr<<"\n"<<e1.op()<<" "<<e2.op(); if (ra) { Relation rel=ra->compare(e1, e2); if (rel.is_less_than()){ return true; } } Expression* diff=simplify(sub(e1.clone(), e2.clone())); if (diff->op()==INTEGER_CONSTANT_OP){ if (diff->value()<0){ delete diff; return true; } } else { if (diff->op()==INFINITY_OP){ bool toret=(diff->sign()==-1); delete diff; return toret; } } delete diff; /// Be conservative. return false; } bool p_greater_than(const Expression& e1, const Expression& e2, RangeAccessor* ra){ if (ra) { Relation rel=ra->compare(e1, e2); if (rel.is_greater_than()){ return true; } } /// if (!(e1.type().data_type()==e2.type().data_type())){ /// cerr<<"\ne1 = "<<e1<<"\ne2 = "<<e2; /// cerr<<"\ne1.op = "<<e1.op(); /// } Expression* diff=simplify(sub(e1.clone(), e2.clone())); if (diff->op()==INTEGER_CONSTANT_OP){ if (diff->value()>0){ delete diff; return true; } } else { if (diff->op()==INFINITY_OP){ bool toret=(diff->sign()==1); delete diff; return toret; } } delete diff; /// Be conservative. return false; } void get_phinode_entries(const Expression& phinode, RefList<Symbol>& entries){ Iterator<Expression> eit=phinode.parameters_guarded().arg_list(); for( ; eit.valid(); ++eit){ switch(eit.current().op()){ case ID_OP: if (!entries.member(eit.current().symbol())){ entries.ins_last(eit.current().symbol()); } break; case MU_OP: case GAMMA_OP: case ETA_OP: case THETA_OP: get_phinode_entries(eit.current(), entries); break; case OMEGA_OP: for(Iterator<Expression> oit=eit.current().arg_list(); oit.valid(); ++oit){ get_phinode_entries(oit.current(), entries); } break; default: cerr<<"\nExpression = "<<eit.current().op(); p_abort("Unsupported expression type in a PHI node."); } } } DoStmt* find_loop_same_level(ProgramUnit& pgm, Symbol& sym, DoStmt& l){ DefLoc* defloc=pgm.gsa_deflocs_guarded().find_ref(sym); if (defloc){ if (defloc->stmt_valid()){ Statement* ps=&defloc->stmt_guarded(); while (ps){ if (ps->outer_ref()==l.outer_ref()){ break; } /// ... Get out. ps=ps->outer_ref(); } if (ps){ /// ... Found it. return (DoStmt*)ps; } } } return 0; } /// If loop is a DoStmt, return whether the given symbol is loop variant. /// If loop is a null pointer, return whether the given symbol is a /// modified variable (SSA number > 0). bool loop_variant(Symbol& s, Statement* loop, ProgramUnit& pgm){ if (loop==0){ p_abort("'loop_variant' called with NULL argument."); } else { DefLoc* defloc=pgm.gsa_deflocs_guarded().find_ref(s); if (!defloc){ /// ... Predefined. return false; } if (!defloc->stmt_valid()){ /// ... Predefined. return false; } Statement* ps=&defloc->stmt_guarded(); while(ps && ps!=loop){ ps=ps->outer_ref(); } if (ps==loop){ /// ... Definition inside _loop. return true; } else { return false; } } }

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