Polaris: guarded_values.cc Source File

guarded_values.cc Go to the documentation of this file. /// #include <vector> #include <map> #include <hash_map.h> #include "Statement/DoStmt.h" #include "Range/AIRangeDict.h" #include "Range/RangeExpr.h" #include "Range/RangeAccessor.h" #include "ip_ssa/trans_util.h" #include "Evolution/eg_utils.h" #include "Evolution/evolution_graph.h" #include "utilities/stmt_util.h" #include "predicates.h" typedef vector<pair<ProgramUnit*, Statement*> > CallStack; /*! These situations are recognized: 1. x .EQ. 0 2. x + exp .EQ. 0 (terms may be in reverse order) 3. x .LE. 0 4. x + exp .LE. 0 (terms may be in reverse order) 5. (-1)*x .LE. 0 6. (-1)*x + exp .LE. 0 (terms may be in reverse order) Returns values: eq = it recognized an .EQ. and not a .LE. sign = the LH value appears with this sign x = the LH value exp = the RH value */ static bool _recognize(Expression& conditional, bool& eq, int& sign, Symbol*& x, Expression*& exp){ eq=true; sign=-1; x=0; exp=0; switch (conditional.op()){ case EQ_OP: eq = true; break; case LE_OP: eq = false; break; default: return false; } /// Quick checks if (conditional.arg_list()[0].type().data_type()!=INTEGER_TYPE){ return false; } if (!is_integer_constant(conditional.arg_list()[1], 0)){ /// ... Not normalized. /// cerr<<"\nConditional expr should have been simplified: "<<conditional; return false; } sign=1; switch(conditional.arg_list()[0].op()){ case ID_OP: /// ... 1,3. x = &conditional.arg_list()[0].symbol(); exp = 0; return true; case MULT_OP: { Expression& mult=conditional.arg_list()[0]; if (mult.arg_list().entries()!=2){ return false; } if (is_integer_constant(mult.arg_list()[0], -1)){ if (mult.arg_list()[1].op()==ID_OP){ // 5. sign=-1; x=&mult.arg_list()[1].symbol(); exp=0; return true; } else { return false; } } else { return false; } } case ADD_OP: { Expression& aexpr=conditional.arg_list()[0]; if (aexpr.arg_list().entries()!=2){ return false; } else { if (aexpr.arg_list()[0].op()==ID_OP){ // 2, 4. x=&aexpr.arg_list()[0].symbol(); exp=&aexpr.arg_list()[1]; return true; } if (aexpr.arg_list()[1].op()==ID_OP){ // 2, 4 reversed. x=&aexpr.arg_list()[1].symbol(); exp=&aexpr.arg_list()[0]; return true; } if (aexpr.arg_list()[0].op()==MULT_OP){ Expression& mult=aexpr.arg_list()[0]; if (mult.arg_list().entries()==2){ if (is_integer_constant(mult.arg_list()[0], -1)){ /// ... 6. sign=-1; if (mult.arg_list()[1].op()==ID_OP){ x=&mult.arg_list()[1].symbol(); exp=&aexpr.arg_list()[1]; return true; } } } } if (aexpr.arg_list()[1].op()==MULT_OP){ Expression& mult=aexpr.arg_list()[1]; if (mult.arg_list().entries()==2){ if (is_integer_constant(mult.arg_list()[0], -1)){ /// ... 6 reversed. sign=-1; if (mult.arg_list()[1].op()==ID_OP){ x=&mult.arg_list()[1].symbol(); exp=&aexpr.arg_list()[0]; return true; } } } } /// ... If it gets here, something did not match. return false; } } default: return false; } } static RangeExpr* _make_range(bool eq, int sign, Expression* exp){ if (eq){ if (exp){ if (sign==-1){ /// ... -x + exp .EQ.0 ====> x = [exp:exp] return new RangeExpr(exp->clone(), exp->clone()); } else { Expression* neg=simplify(mul(constant(-1), exp->clone())); return new RangeExpr(neg->clone(), neg); } } else { return new RangeExpr(constant(0), constant(0)); } } else { if (exp){ if (sign==1){ Expression* neg=simplify(mul(constant(-1), exp->clone())); return new RangeExpr(infinity(-1), neg); } else { return new RangeExpr(exp->clone(), infinity(1)); } } else { if (sign==1){ return new RangeExpr(infinity(-1), constant(0)); } else { return new RangeExpr(constant(0), infinity(1)); } } } } void _print_range(const char* sname, const pair<RangeExpr*, bool>& r){ if (r.first){ cerr<<sname<<": "<<*r.first<<"<"<<r.second<<">"; } else { cerr<<sname<<": "<<"NULL"<<"<"<<r.second<<">"; } } /// Return 0 if ranges are incompatible. /// The boolean value tells us whether the complement of the range /// should be considered instead of the range (false value). /// The conservative approximation returns a superset of the intersection. static pair<RangeExpr*, bool> _intersect_ranges(ProgramUnit& pgm, Symbol& sym, pair<RangeExpr*, bool> range1, pair<RangeExpr*, bool> range2){ if (range1.first==0){ if (range2.first==0){ delete range2.first; } return range1; } if (range2.first==0){ if (range1.first==0){ delete range1.first; } return range2; } /// Get a comparison object. Statement* def=0; DefLocMap& deflocmap=pgm.gsa_deflocs_guarded(); DefLoc* defloc=deflocmap.find_ref(sym); if (defloc) { if (defloc->stmt_valid()){ def=&defloc->stmt_guarded(); } } if (def==0){ def=pgm.stmts().last_ref(); } if (!pgm.range_dict_valid()){ pgm.range_dict(new AIRangeDict(pgm)); } RangeAccessor ra(pgm.range_dict_guarded(), *range_stmt(*def)); /// cerr<<"\nEnter _intersect_ranges with "; /// cerr<<"\n\t"; /// _print_range(sym.name_ref(), range1); /// cerr<<"\n\t"; /// _print_range(sym.name_ref(), range2); /// Check for complementarity. if (range1.second && !range2.second){ /// ... Hope that range1 <= range2.true. if (p_greater_equal(range1.first->lb(), range2.first->lb(), &ra) && p_less_equal(range1.first->ub(), range2.first->ub(), &ra)){ delete range1.first; delete range2.first; return make_pair((RangeExpr*)0, true); } else { delete range2.first; return range1; } } if (!range1.second && range2.second){ /// ... Hope that range1.true => range2. if (p_less_equal(range1.first->lb(), range2.first->lb(), &ra) && p_greater_equal(range1.first->ub(), range2.first->ub(), &ra)){ delete range1.first; delete range2.first; return make_pair((RangeExpr*)0, true); } else { delete range2.first; return range1; } } if (!range1.second && !range2.second){ delete range2.first; return range1; } //silvius: could do better than this. /// At this point both ranges are for real (not complemented). Symbol* dummy=new VariableSymbol("DUMMY", make_type(INTEGER_TYPE), NOT_FORMAL, NOT_SAVED); ra.set_range(*dummy, range2.first); ra.intersect_range(*dummy, *range1.first); const Expression* inter=ra.get_range_ref(*dummy); delete dummy; if (inter==0){ /// ... Cannot intersect them. return range1; } else { delete range1.first; const Expression* lb=inter; if (inter->op()==RANGE_OP){ lb=&((const RangeExpr*)inter)->lb(); } const Expression* ub=inter; if (inter->op()==RANGE_OP){ ub=&((const RangeExpr*)inter)->ub(); } Relation r=ra.compare(*lb, *ub); if (r.is_greater_than()){ /// ... Incompatible ranges. return make_pair((RangeExpr*)0, true); } else { if (inter->op()==RANGE_OP){ return make_pair((RangeExpr*)inter->clone(), true); } else { return make_pair(new RangeExpr(inter->clone(), inter->clone()), true); } } } } /*! \brief Extracts values for integer scalars from boolean statements. Multiple comparisons are recognized as long as they are AND-ed together. */ void extract_ranges(ProgramUnit& pgm, Expression& conditional, map<Symbol*, pair<RangeExpr*, bool> >& ranges){ /// cerr<<"\nExtract ranges for "<<conditional; if (conditional.op()==AND_OP) { Iterator<Expression> expit = conditional.arg_list(); for ( ; expit.valid(); ++expit) { extract_ranges(pgm, expit.current(), ranges); } } else { /// ... Let's see what we've got. bool eq; /// ... Is it equality or inequality? int sign; /// ... What is the sign of the symbol? Symbol* x=0; /// ... What is the symbol? Expression* exp=0; /// ... What is the value? bool complementary_range; Expression* ncond=0; if (!_recognize(conditional, eq, sign, x, exp)){ /// ... Check for .NE. if (conditional.op()==NE_OP){ ncond=simplify(not(conditional.clone())); if (!_recognize(*ncond, eq, sign, x, exp)){ // Did not recognize anything. return; } else { // Recognized .NE. complementary_range=true; } } else { /// ... Did not recognize anything. return; } } else { /// ... Recognized .EQ. or .LE. complementary_range=false; } /// cerr<<"\neq: "<<eq<<", sign: "<<sign<<", exp: "<<*exp; /// ... If it gets here, the range was found. RangeExpr* newrange=_make_range(eq, sign, exp); /// cerr<<"\n\tAdding range "; /// _print_range(x->name_ref(), make_pair(newrange, complementary_range)); if (ranges.find(x)==ranges.end()){ ranges[x]=make_pair(newrange, complementary_range); } else { /// ... Intersect ranges. ranges[x]=_intersect_ranges(pgm, *x, make_pair(newrange, complementary_range), ranges[x]); } /// cerr<<"\n\tAfter addition: "; /// _print_range(x->name_ref(), ranges[x]); if (ncond) { delete ncond; } /// cerr<<"\nExtracted for symbol "<<x->name_ref() /// <<" range "<<*ranges[x].first; } } /// Returns 0 if the given expression evaluates to .FALSE. static Expression* _simplify_using_ranges(ProgramUnit& pgm, Expression& given, map<Symbol*, pair<RangeExpr*, bool> >& ranges){ Expression& conditional=given; if (conditional.op()==AND_OP) { Iterator<Expression> expit = conditional.arg_list(); for ( ; expit.valid(); ++expit) { if (_simplify_using_ranges(pgm, expit.current(), ranges)==0){ return 0; } } } else { /// ... Let's see what we've got. bool eq; int sign; Symbol* x; Expression* exp; bool complementary_range; Expression* ncond=0; if (!_recognize(conditional, eq, sign, x, exp)){ /// ... Check for .NE. if (conditional.op()==NE_OP){ ncond=simplify(not(conditional.clone())); if (!_recognize(*ncond, eq, sign, x, exp)){ // Did not recognize anything. return &given; } else { // Recognized .NE. complementary_range=true; } } else { /// ... Did not recognize anything. return &given; } } else { /// ... Recognized .EQ. or .LE. complementary_range=false; } /// ... If it gets here, the range was found. RangeExpr* newrange=_make_range(eq, sign, exp); if (ranges.find(x)==ranges.end()){ ranges[x]=make_pair(newrange, complementary_range); } else { /// ... Intersect ranges. pair<RangeExpr*, bool> ret= _intersect_ranges(pgm, *x, make_pair(newrange, complementary_range), ranges[x]); if (ret.first==0){ /// ... Found incompatible ranges. return 0; } ranges[x]=ret; } if (ncond) { delete ncond; } } /// Did not simplify. return &given; } Expression* simplify_using_ranges(ProgramUnit& pgm, Expression& given){ map<Symbol*, pair<RangeExpr*, bool> > ranges; return _simplify_using_ranges(pgm, given, ranges); } /// Returns true if the given range is outside the possible range of /// values for symbol cand in program pgm, at the loop level where it is /// defined. /// A returned value of false does not necessarily /// mean the ranges are compatible. static bool incompatible_range(ProgramUnit& pgm, Statement& def, Symbol& cand, pair<RangeExpr*, bool>& range){ if (!pgm.range_dict_valid()){ pgm.range_dict(new AIRangeDict(pgm)); } RangeAccessor ra(pgm.range_dict_guarded(), *range_stmt(def)); DoStmt* loop=def_loop(cand, pgm); Expression* ecand=id(cand); Expression* arange=eg_range(*ecand, pgm, loop); RangeExpr* actual_range=0; /// cerr<<"\nFor symbol "<<cand.name_ref(); /// cerr<<"\n\tactual_range = "<<*arange; if (arange->op()==RANGE_OP){ actual_range=(RangeExpr*)arange; } else { actual_range=new RangeExpr(arange->clone(), arange); } delete ecand; pair<RangeExpr*, bool>& range1=range; pair<RangeExpr*, bool> range2=make_pair(actual_range, false); /// Check for complementarity. if (!range1.second){ if (p_less_than(range2.first->ub(), range1.first->lb())){ delete actual_range; return true; } if (p_greater_than(range2.first->lb(), range1.first->ub())){ delete actual_range; return true; } /// ... Conservative. delete actual_range; return false; } else { /// ... Hope that complementary(range1) includes range2. /// cerr<<"\nr1 = "<<*range1.first; /// cerr<<"\nr2 = "<<*range2.first; if (p_less_equal(range1.first->lb(), range2.first->lb(), &ra) && p_greater_equal(range1.first->ub(), range2.first->ub(), &ra)){ delete range2.first; return true; } else { delete range2.first; return false; } } p_abort("Sanity check failed: control should have not gotten here."); } /// Discrimnate between possible origins of 'def': cand1 or cand2. /// Solution based on Evolution Graphs and given range. /// Return: /// 0 = could not dicriminate /// 1 = cand1 /// 2 = cand2 int discriminate_gamma(ProgramUnit& pgm, pair<RangeExpr*, bool>& range, Statement& stmt, Symbol& def, Symbol& cand1, Symbol& cand2){ /// cerr<<"\n\nIn pgm "<<pgm.routine_name_ref(); /// cerr<<"\n\tDef: "<<def.name_ref(); /// cerr<<"\n\tArg 1: "<<cand1.name_ref(); /// cerr<<"\n\tArg 2: "<<cand2.name_ref(); /// cerr<<"\n\tRange: "<<range; bool check1=incompatible_range(pgm, stmt, cand1, range); bool check2=incompatible_range(pgm, stmt, cand2, range); if (check1 && check2){ cerr<<"\n\nIn pgm "<<pgm.routine_name_ref(); cerr<<"\n\tDef: "<<def.name_ref(); cerr<<"\n\tArg 1: "<<cand1.name_ref(); cerr<<"\n\tArg 2: "<<cand2.name_ref(); cerr<<"\n\tRange: "<<*range.first; p_abort("None of the GAMMA args match query range."); } if (check1){ return 2; } if (check2){ return 1; } return 0; } /// Discrimnate between possible origins of 'def': cand1 or cand2. /// Solution based on Evolution Graphs and given range. /// Return: /// 0 = could not dicriminate /// 1 = cand1 /// 2 = cand2 int discriminate_eta(ProgramUnit& pgm, pair<RangeExpr*, bool>& range, Statement& stmt, Symbol& def, Symbol& cand1, Symbol& cand2){ /// cerr<<"\n\nIn pgm "<<pgm.routine_name_ref(); /// cerr<<"\n\tDef: "<<def.name_ref(); /// cerr<<"\n\tArg 1: "<<cand1.name_ref(); /// cerr<<"\n\tArg 2: "<<cand2.name_ref(); /// cerr<<"\n\tRange: "<<range; bool check1=incompatible_range(pgm, stmt, cand1, range); bool check2=incompatible_range(pgm, stmt, cand2, range); if (check1 && check2){ cerr<<"\n\nIn pgm "<<pgm.routine_name_ref(); cerr<<"\n\tDef: "<<def.name_ref(); cerr<<"\n\tArg 1: "<<cand1.name_ref(); cerr<<"\n\tArg 2: "<<cand2.name_ref(); cerr<<"\n\tRange: "<<*range.first; p_abort("None of the ETA args match query range."); } if (check1){ return 2; } if (check2){ return 1; } return 0; } /// Discriminate between possible origins of 'def': cand1 or cand2. /// Solution based on Evolution Graphs and given range. /// Return: /// 0 = could not dicriminate /// 1 = cand1 /// 2 = cand2 int discriminate_mu(ProgramUnit& pgm, pair<RangeExpr*, bool>& range, Statement& stmt, Symbol& def, Symbol& cand1, Symbol& cand2){ /// cerr<<"\n\nIn pgm "<<pgm.routine_name_ref(); /// cerr<<"\n\tDef: "<<def.name_ref(); /// cerr<<"\n\tArg 1: "<<cand1.name_ref(); /// cerr<<"\n\tArg 2: "<<cand2.name_ref(); /// cerr<<"\n\tRange: "<<*range.first<<": "<<range.second; bool check1=incompatible_range(pgm, stmt, cand1, range); bool check2=incompatible_range(pgm, stmt, cand2, range); /// cerr<<"\ncheck1 = "<<check1; /// cerr<<"\ncheck2 = "<<check2; if (check1 && check2){ cerr<<"\n\nIn pgm "<<pgm.routine_name_ref(); cerr<<"\n\tDef: "<<def.name_ref(); cerr<<"\n\tArg 1: "<<cand1.name_ref(); cerr<<"\n\tArg 2: "<<cand2.name_ref(); cerr<<"\n\tRange: "<<*range.first<<":"<<range.second; p_abort("None of the MU args match query range."); } if (check1){ return 2; } if (check2){ return 1; } return 0; } /// Discriminates MU and GAMMA reaching def based on given predicate set. int discriminate_phi(ProgramUnit& pgm, vector<pair<ProgramUnit*, pair<Statement*, int> > >& preds, Statement& stmt, Symbol& def, Symbol& cand1, Symbol& cand2){ /// cerr<<"\n\nIn pgm "<<pgm.routine_name_ref(); /// cerr<<"\n\tDef: "<<def.name_ref(); /// cerr<<"\n\tArg 1: "<<cand1.name_ref(); /// cerr<<"\n\tArg 2: "<<cand2.name_ref(); /// cerr<<"\n\tRange: "<<range; Statement* ps=&stmt; while(ps->stmt_class()==ASSIGNMENT_STMT) ps=ps->prev_ref(); vector<pair<ProgramUnit*, pair<Statement*, int> > >::iterator it; for (it=preds.begin(); it!=preds.end(); ++it){ if ((*it).first==&pgm && (*it).second.first==ps){ return 1+(*it).second.second; } } return 0; } void trace_defs(pair<RangeExpr*, bool>& range, DefTrace::DTrace& def_trace, DefTrace::TransMap& trans_map); /// Translates the last def in the trace into the callee and adds /// it to the trace. /// Then calls trace_defs until it gtes to the beginning of the callee. /// Return true if the trace got to the incoming value GSA id 0, /// and false if the trace stopped on the way back. bool trace_into_called_pgm(ProgramUnit& callee, Statement& callsite, pair<RangeExpr*, bool>& range, DefTrace::DTrace& def_trace, DefTrace::TransMap& trans_map){ DefTrace::DTrace::iterator lit=def_trace.end(); p_assert(lit!=def_trace.begin(), "Empty list given input to find_defs."); --lit; ProgramUnit& caller=*(*lit).first; Symbol& sym=*(*lit).second; /// cerr<<"\nCaller: "<<caller.routine_name_ref() /// <<"\nCallsite: "<<callsite /// <<"\nSymbol "<<sym; /// Translate symbol. RefList<Symbol> outs=untranslate_var((VariableSymbol&)sym, callee, caller, callsite); if (outs.entries()!=1){ return false; } Symbol& sym_callee=outs[0]; Symbol* symgsa_callee=last_gsa_symbol(callee, sym_callee); /// cerr<<"\nSym callee: "<<sym_callee /// <<"\ngsa callee: "<<*symgsa_callee; /// Translate range. Expression* range_callee=range.first->clone(); RefList<Symbol> syms; referred_symbols(*range.first, syms); for(Iterator<Symbol> sit=syms; sit.valid(); ++sit){ Symbol& s=sit.current(); RefList<Symbol> outs=untranslate_var(s, callee, caller, callsite); if (outs.entries()!=1){ delete range_callee; return false; } Symbol& s_callee=outs[0]; Symbol* sgsa_callee=last_gsa_symbol(callee, s_callee); substitute_var(*range_callee, s, *sgsa_callee); } /// Extend the trace. def_trace.push_back(make_pair(&callee, symgsa_callee)); /// Save call site in the trans map. lit=def_trace.end(); --lit; trans_map[lit-def_trace.begin()]=&callsite; /// Trace back into the callee. pair<RangeExpr*, bool> new_range= make_pair((RangeExpr*)range_callee, range.second); trace_defs(new_range, def_trace, trans_map); delete range_callee; lit=def_trace.end(); --lit; if (gsa_base(*(*lit).second)==(*lit).second){ return true; } else { return false; } } void trace_defs(vector<pair<ProgramUnit*, pair<Statement*, int> > >& preds, DefTrace::DTrace& def_trace, DefTrace::TransMap& trans_map); bool trace_into_called_pgm(ProgramUnit& callee, Statement& callsite, vector<pair<ProgramUnit*, pair<Statement*, int> > >& preds, DefTrace::DTrace& def_trace, DefTrace::TransMap& trans_map){ DefTrace::DTrace::iterator lit=def_trace.end(); p_assert(lit!=def_trace.begin(), "Empty list given input to find_defs."); --lit; ProgramUnit& caller=*(*lit).first; Symbol& sym=*(*lit).second; /// Translate symbol. RefList<Symbol> outs=untranslate_var((VariableSymbol&)sym, callee, caller, callsite); if (outs.entries()!=1){ return false; } Symbol& sym_callee=outs[0]; Symbol* symgsa_callee=last_gsa_symbol(callee, sym_callee); /// Extend the trace. def_trace.push_back(make_pair(&callee, symgsa_callee)); /// Save call site in the trans map. lit=def_trace.end(); --lit; trans_map[lit-def_trace.begin()]=&callsite; /// Trace back into the callee. trace_defs(preds, def_trace, trans_map); lit=def_trace.end(); --lit; if (gsa_base(*(*lit).second)==(*lit).second){ return true; } else { return false; } } /// Look back for definition and try to do better than just pick the /// GSA defloc. Try to narrow it down based on the given range. /// Stop when we cannot discriminate between two possible sources in a /// GAMMA, ETA, or MU. /// Return the definitions as pairs <ProgramUnit, GSA Name> void trace_defs(pair<RangeExpr*, bool>& range, DefTrace::DTrace& def_trace, DefTrace::TransMap& trans_map){ DefTrace::DTrace::iterator lit=def_trace.end(); p_assert(lit!=def_trace.begin(), "Empty list given input to find_defs."); --lit; ProgramUnit& pgm=*(*lit).first; Symbol& sym=*(*lit).second; DefLocMap& deflocmap=pgm.gsa_deflocs_guarded(); DefLoc* defloc=deflocmap.find_ref(sym); if (!defloc) { /// ... Must be either formal or common with GSA number=0. return; } if (!defloc->stmt_valid()){ /// ... Must be either formal or common with GSA number=0. return; } Statement& def=defloc->stmt_guarded(); switch(def.stmt_class()){ case ASSIGNMENT_STMT: { switch(def.rhs().op()){ case GAMMA_OP: { List<Expression>& params=def.rhs().parameters_guarded().arg_list(); int d=discriminate_gamma(pgm, range, def, def.lhs().symbol(), params[0].symbol(), params[1].symbol()); if (d>0){ def_trace.push_back(make_pair(&pgm, &params[d-1].symbol())); trace_defs(range, def_trace, trans_map); } } break; case ETA_OP: { List<Expression>& params=def.rhs().parameters_guarded().arg_list(); int d=discriminate_eta(pgm, range, def, def.lhs().symbol(), params[0].symbol(), params[1].symbol()); if (d>0){ def_trace.push_back(make_pair(&pgm, &params[d-1].symbol())); trace_defs(range, def_trace, trans_map); } } break; case MU_OP: { List<Expression>& params=def.rhs().parameters_guarded().arg_list(); int d=discriminate_mu(pgm, range, def, def.lhs().symbol(), params[0].symbol(), params[1].symbol()); if (d==2){ /// ... Loop-back value. That means it can only come from within the /// ... loop. It must come from an INPUT value in the EG for this loop. /// ... Get trace from EG. def_trace.push_back(make_pair(&pgm, &params[d-1].symbol())); eg_trace_from_input(pgm, (DoStmt*)def.outer_ref(), range, &params[d-1].symbol(), def_trace); } if (d==1){ /// ... Incoming value. Trace it. def_trace.push_back(make_pair(&pgm, &params[d-1].symbol())); trace_defs(range, def_trace, trans_map); } } break; case THETA_OP: { // Find call site. Statement* ps=&def; ProgramUnit* callee=0; while((callee=called_pgm(*ps))==0){ ps=ps->prev_ref(); } // Go into called subroutine. if (trace_into_called_pgm(*callee, *ps, range, def_trace, trans_map)){ /// ... Got back into pgm. Go after THETA param. Symbol* in; Symbol* out; get_in_out(pgm, *ps, *gsa_base(sym), in, out); def_trace.push_back(make_pair(&pgm, in)); trace_defs(range, def_trace, trans_map); } else { /// ... Have to stop here. return; } } break; case FUNCTION_CALL_OP: { // Go into called subroutine. if (trace_into_called_pgm(*called_pgm(def), def, range, def_trace, trans_map)){ /// ... Got back into pgm. Symbol* in; Symbol* out; get_in_out(pgm, def, *gsa_base(sym), in, out); def_trace.push_back(make_pair(&pgm, in)); trace_defs(range, def_trace, trans_map); } else { /// ... Have to stop here. return; } } break; default: /// ... Cannot do anything, the trace breaks here. return; } } break; case CALL_STMT: { if (trace_into_called_pgm(*called_pgm(def), def, range, def_trace, trans_map)){ /// ... Got back into pgm. Symbol* in; Symbol* out; get_in_out(pgm, def, *gsa_base(sym), in, out); def_trace.push_back(make_pair(&pgm, in)); trace_defs(range, def_trace, trans_map); } else { /// ... Have to stop here. return; } /// ... Go into called subprogram. } } } /// Look back for definition and try to do better than just pick the /// GSA defloc. Try to narrow it down based on the given range. /// Stop when we cannot discriminate between two possible sources in a /// GAMMA, or MU. /// Return the definitions as pairs <ProgramUnit, GSA Name> void trace_defs(vector<pair<ProgramUnit*, pair<Statement*, int> > >& preds, DefTrace::DTrace& def_trace, DefTrace::TransMap& trans_map){ DefTrace::DTrace::iterator lit=def_trace.end(); p_assert(lit!=def_trace.begin(), "Empty list given input to find_defs."); --lit; ProgramUnit& pgm=*(*lit).first; Symbol& sym=*(*lit).second; DefLocMap& deflocmap=pgm.gsa_deflocs_guarded(); DefLoc* defloc=deflocmap.find_ref(sym); if (!defloc) { /// ... Must be either formal or common with GSA number=0. return; } if (!defloc->stmt_valid()){ /// ... Must be either formal or common with GSA number=0. return; } Statement& def=defloc->stmt_guarded(); switch(def.stmt_class()){ case ASSIGNMENT_STMT: { switch(def.rhs().op()){ case GAMMA_OP: { List<Expression>& params=def.rhs().parameters_guarded().arg_list(); int d=discriminate_phi(pgm, preds, def, def.lhs().symbol(), params[0].symbol(), params[1].symbol()); if (d>0){ def_trace.push_back(make_pair(&pgm, &params[d-1].symbol())); trace_defs(preds, def_trace, trans_map); } } break; case ETA_OP: { List<Expression>& params=def.rhs().parameters_guarded().arg_list(); int d=discriminate_phi(pgm, preds, def, def.lhs().symbol(), params[0].symbol(), params[1].symbol()); if (d>0){ def_trace.push_back(make_pair(&pgm, &params[d-1].symbol())); trace_defs(preds, def_trace, trans_map); } } break; case MU_OP: { List<Expression>& params=def.rhs().parameters_guarded().arg_list(); int d=discriminate_phi(pgm, preds, def, def.lhs().symbol(), params[0].symbol(), params[1].symbol()); if (d>0){ /// ... Incoming value. Trace it. def_trace.push_back(make_pair(&pgm, &params[d-1].symbol())); trace_defs(preds, def_trace, trans_map); } } break; case THETA_OP: { // Find call site. Statement* ps=&def; ProgramUnit* callee=0; while((callee=called_pgm(*ps))==0){ ps=ps->prev_ref(); } // Go into called subroutine. if (trace_into_called_pgm(*callee, *ps, preds, def_trace, trans_map)){ /// ... Got back into pgm. Go after THETA param. Symbol* in; Symbol* out; get_in_out(pgm, *ps, *gsa_base(sym), in, out); def_trace.push_back(make_pair(&pgm, in)); trace_defs(preds, def_trace, trans_map); } else { /// ... Have to stop here. return; } } break; case FUNCTION_CALL_OP: { // Go into called subroutine. if (trace_into_called_pgm(*called_pgm(def), def, preds, def_trace, trans_map)){ /// ... Got back into pgm. Symbol* in; Symbol* out; get_in_out(pgm, def, *gsa_base(sym), in, out); def_trace.push_back(make_pair(&pgm, in)); trace_defs(preds, def_trace, trans_map); } else { /// ... Have to stop here. return; } } break; default: /// ... Cannot do anything, the trace breaks here. return; } } break; case CALL_STMT: { if (trace_into_called_pgm(*called_pgm(def), def, preds, def_trace, trans_map)){ /// ... Got back into pgm. Symbol* in; Symbol* out; get_in_out(pgm, def, *gsa_base(sym), in, out); def_trace.push_back(make_pair(&pgm, in)); trace_defs(preds, def_trace, trans_map); } else { /// ... Have to stop here. return; } /// ... Go into called subprogram. } } } Expression* translate(Expression* expr, CallStack& call_stack){ int sit=call_stack.size(); if (sit==0){ return expr; } --sit; for( ; sit>=0; --sit){ ProgramUnit& caller=*call_stack[sit].first; Statement& call_site=*call_stack[sit].second; ProgramUnit& callee=*called_pgm(call_site); /// cerr<<"\n\tCaller = "<<caller.routine_name_ref(); /// cerr<<"\n\tCallee = "<<callee.routine_name_ref(); Translator translator(caller, call_site); RefList<Symbol> syms, can, cannot; referred_symbols(*expr, syms); if (can_translate(syms, can, cannot, translator, callee, caller, call_site)){ expr=translate_and_reshape(translator, callee, caller, call_site, expr); if (expr==0){ return 0; } } else { /// ... Not translatable. delete expr; return 0; } } return expr; } void get_preds_from_trace(DefTrace::DTrace& def_trace, DefTrace::TransMap& trans_map, vector<pair<ProgramUnit*, pair<Statement*, int> > >& preds){ /// The first definition in the trace sets the initial context. DefTrace::DTrace::iterator lit=def_trace.begin(); p_assert(lit!=def_trace.end(), "Empty list given input to get_gates."); ProgramUnit& initial_pgm=*(*lit).first; /// Follow the trace and extract conditions from GAMMA statements. ProgramUnit* last_pgm=&initial_pgm; Symbol* last_sym=(*lit).second; for( ; lit!=def_trace.end(); ++lit){ ProgramUnit& pgm=*(*lit).first; Symbol& sym=*(*lit).second; if (&pgm==last_pgm){ /// ... Find the GSA gate associated with the current definition, if any. DefLocMap& deflocmap=pgm.gsa_deflocs_guarded(); DefLoc* defloc=deflocmap.find_ref(*last_sym); if (defloc) { if (defloc->stmt_valid()){ Statement& def=defloc->stmt_guarded(); if(def.stmt_class()==ASSIGNMENT_STMT){ if(def.rhs().op()==ETA_OP || def.rhs().op()==GAMMA_OP || def.rhs().op()==MU_OP){ Statement* ps=&def; while (ps->stmt_class()==ASSIGNMENT_STMT){ ps=ps->prev_ref(); } int tv=-1; List<Expression>& params= def.rhs().parameters_guarded().arg_list(); if (&params[0].symbol()==&sym){ tv=0; } else { if (&params[1].symbol()==&sym){ tv=1; } } if (tv>=0){ preds.push_back(make_pair(&pgm, make_pair(ps, tv))); } } } } } } last_pgm=&pgm; last_sym=&sym; } } /// Gets backwards definition trace based on the given GAMMA/MU disambiguation. /// silvius: for now return furthest def in the same pgm. pair<ProgramUnit*, Symbol*> get_backtrace_given_preds(ProgramUnit& pgm, Symbol& sym, vector<pair<ProgramUnit*, pair<Statement*, int> > >& preds){ DefTrace::DTrace def_trace; DefTrace::TransMap trans_map; def_trace.push_back(make_pair(&pgm, &sym)); trace_defs(preds, def_trace, trans_map); for(unsigned i=def_trace.size()-1; i>=0; --i){ if (def_trace[i].first==&pgm){ return def_trace[i]; } } return def_trace[0]; } void get_gates_from_trace(DefTrace::DTrace& def_trace, DefTrace::TransMap& trans_map, List<Expression>& gate_list){ /// Call stack. CallStack call_stack; /// cerr<<"\nDef trace: "; /// for(DefTrace::DTrace::iterator lit=def_trace.begin(); lit!=def_trace.end(); ++lit){ /// ProgramUnit& pgm=*(*lit).first; /// Symbol& sym=*(*lit).second; /// cerr<<"\n\t"<<pgm.routine_name_ref()<<" : "<<sym.name_ref(); /// if (trans_map.find(lit-def_trace.begin())!=trans_map.end()){ /// cerr<<"\n\t\tCS"; /// } /// } /// The first definition in the trace sets the initial context. DefTrace::DTrace::iterator lit=def_trace.begin(); p_assert(lit!=def_trace.end(), "Empty list given input to get_gates."); ProgramUnit& initial_pgm=*(*lit).first; /// Follow the trace and extract conditions from GAMMA statements. ProgramUnit* last_pgm=&initial_pgm; Symbol* last_sym=(*lit).second; for( ; lit!=def_trace.end(); ++lit){ ProgramUnit& pgm=*(*lit).first; Symbol& sym=*(*lit).second; if (&pgm!=last_pgm){ /// ... New subprogram. /// ... If it has an entry in trans_map, then it is a call site. /// ... Otherwise, it is a return site. DefTrace::TransMap::iterator mit=trans_map.find(lit-def_trace.begin()); if (mit!=trans_map.end()){ call_stack.push_back(make_pair(last_pgm, (*mit).second)); } else { call_stack.pop_back(); } } else { /// ... Same subprogram. /// ... Find the GSA gate associated with the current definition, if any. DefLocMap& deflocmap=pgm.gsa_deflocs_guarded(); DefLoc* defloc=deflocmap.find_ref(*last_sym); if (defloc) { if (defloc->stmt_valid()){ Statement& def=defloc->stmt_guarded(); if(def.stmt_class()==ASSIGNMENT_STMT){ if(def.rhs().op()==GAMMA_OP){ Expression* gate=def.rhs().gate().clone(); List<Expression>& params= def.rhs().parameters_guarded().arg_list(); if (&params[1].symbol()==&sym){ /// ... The gate must be negated, the second argument is /// ... the right one. gate=simplify(not(gate)); } /// cerr<<"\ngate = "<<*gate; /// cerr<<"\nEnter translate with "<<*gate; /// cerr<<"\nCall stack follows: "; for(unsigned int i=0; i<call_stack.size(); ++i){ /// ProgramUnit& caller=*call_stack[i].first; /// Statement& call_site=*call_stack[i].second; /// cerr<<"\n\tCaller = "<<caller.routine_name_ref(); /// cerr<<"\tCall site = "<<call_site; } Expression* translated_gate=translate(gate, call_stack); if (translated_gate){ gate_list.ins_last(translated_gate); } } } } } } last_pgm=&pgm; last_sym=&sym; } } /// Look back for definitions and try to do better than just pick the /// GSA defloc. Try to narrow them down based on the given ranges. void find_defs(ProgramUnit& pgm, map<Symbol*, pair<RangeExpr*, bool> >& ranges, vector<DefTrace::DTrace>& def_traces, vector<DefTrace::TransMap>& trans_maps){ for(map<Symbol*, pair<RangeExpr*, bool> >::iterator rit=ranges.begin(); rit!=ranges.end(); ++rit){ if ((*rit).second.first==0){ /// ... Incompatible ranges. continue; } /// ... Setup. def_traces.push_back(DefTrace::DTrace()); DefTrace::DTrace& def_trace=def_traces[def_traces.size()-1]; def_trace.push_back(make_pair(&pgm, (*rit).first)); trans_maps.push_back(DefTrace::TransMap()); DefTrace::TransMap& trans_map=trans_maps[trans_maps.size()-1]; /// ... Get trace. trace_defs((*rit).second, def_trace, trans_map); /// cerr<<"\n\n\nFor variable "<<(*rit).first->name_ref() /// <<" and range "<<*(*rit).second.first /// <<"("<<(*rit).second.second<<")" /// <<", def trace is: "; /// for(DefTrace::DTrace::iterator lit=def_trace.begin(); /// lit!=def_trace.end(); ++lit){ /// cerr<<"\n\t"<<(*lit).first->routine_name_ref() /// <<" : "<<(*lit).second->name_ref(); /// } } } typedef hash_map<Expression*, /// ... Condition. pair<vector<DefTrace::DTrace>, vector<DefTrace::TransMap> >, /// ... Definition traces for /// ... extracted variable ranges. expr_hash, expr_eq> GateInferences; /// Silvius: should clean this up once in a while. static map<ProgramUnit*, GateInferences> _gate_inferences; void cleanup_gate_inferences(ProgramUnit& pgm){ map<ProgramUnit*, GateInferences>::iterator found= _gate_inferences.find(&pgm); if (found!=_gate_inferences.end()){ GateInferences::iterator it; List<Expression> todel; /// ... Put the expression pointers in the list, the destructor will free them. for(it=(*found).second.begin(); it!=(*found).second.end(); ++it){ todel.ins_last((*it).first); } (*found).second.clear(); } } /// Find the definition var = expr, where 'var' has the same gsa base as 'sym'. Statement* trace_unique_def(ProgramUnit& pgm, Symbol& sym, Expression& expr){ Statement* def=0; DefLocMap& deflocmap=pgm.gsa_deflocs_guarded(); DefLoc* defloc=deflocmap.find_ref(sym); if (defloc) { if (defloc->stmt_valid()){ def=&defloc->stmt_guarded(); } } if (def){ if (def->stmt_class()==ASSIGNMENT_STMT){ switch (def->rhs().op()){ case MU_OP: case GAMMA_OP: case ETA_OP: { RefList<Symbol> entries; get_phinode_entries(def->rhs(), entries); for(Iterator<Symbol> sit=entries; sit.valid(); ++sit){ Statement* d=trace_unique_def(pgm, sit.current(), expr); if (d){ return d; } } } break; default: if (def->rhs()==expr){ return def; } else { return 0; } } } } return 0; } /// Find the definitions that must happen in order for gate to be true. void trace_defs(ProgramUnit& pgm, Expression& gate, vector<DefTrace::DTrace>*& pdt, vector<DefTrace::TransMap>*& ptm){ pdt=0; ptm=0; map<ProgramUnit*, GateInferences>::iterator found= _gate_inferences.find(&pgm); if (found!=_gate_inferences.end()){ GateInferences::iterator git=(*found).second.find(&gate); if (git!=(*found).second.end()){ /// ... Found it. pdt=&(*git).second.first; ptm=&(*git).second.second; } } if (pdt==0){ map<Symbol*, pair<RangeExpr*, bool> > ranges; extract_ranges(pgm, gate, ranges); vector<DefTrace::DTrace> def_trace; vector<DefTrace::TransMap> trans_map; pair<GateInferences::iterator, bool> git= _gate_inferences[&pgm].insert(make_pair(gate.clone(), make_pair(vector<DefTrace::DTrace>(), vector<DefTrace::TransMap>()))); p_assert(git.second, "Could not cache gate inferences."); pdt=&(*git.first).second.first; ptm=&(*git.first).second.second; /// ... Get definitions from ranges. find_defs(pgm, ranges, *pdt, *ptm); /// ... Clean-up. map<Symbol*, pair<RangeExpr*, bool> >::iterator it; for(it=ranges.begin(); it!=ranges.end(); ++it){ delete (*it).second.first; } } } void infer_gates(ProgramUnit& pgm, Expression& gate, List<Expression>& inferences){ /// Trace back. vector<DefTrace::DTrace>* pdt; vector<DefTrace::TransMap>* ptm; trace_defs(pgm, gate, pdt, ptm); /// Get gates. for(unsigned i=0; i<pdt->size(); ++i){ get_gates_from_trace((*pdt)[i], (*ptm)[i], inferences); } } void find_preds(ProgramUnit& pgm, Expression& gate, vector<pair<ProgramUnit*, pair<Statement*, int> > >& preds){ /// cerr<<"\nEnter find_preds "<<gate /// <<"\npgm = "<<pgm.routine_name_ref(); if (gate.op()==AND_OP){ Iterator<Expression> fit = gate.arg_list(); for ( ; fit.valid(); ++fit) { find_preds(pgm, fit.current(), preds); } } else { Symbol* var=0; bool truth=true; switch (gate.op()){ case ID_OP: var=&gate.symbol(); break; case NOT_OP: if (gate.expr_guarded().op()==ID_OP){ var=&gate.expr_guarded().symbol(); truth=false; } } if (var){ String ref("PE_FLAG"); String name(var->name_ref(), ref.len()); if (name==ref){ if (truth==false){ // Bingo. // This means the loop corresponding to pe_flag was not left // via a premature exit. That means the check IF (skip_flag) // was always .TRUE. // Add three things: // 1. The predicate that controls the def site for pe_flag=.FALSE. // 2. The DO after it. // 3. The IF right after the DO (skip_flag) with the .TRUE. branch. /// cerr<<"\n\nBINGO "<<var->name_ref(); Expression* f=constant(".FALSE."); Statement* def=trace_unique_def(pgm, *var, *f); delete f; // 1. // silvius: do it later // 2. Statement* ps=def; /// cerr<<"\nps= "<<*ps; while(ps->stmt_class()!=DO_STMT){ ps=ps->next_ref(); } /// cerr<<"\nAdding "<<*ps; preds.push_back(make_pair(&pgm, make_pair(ps, 0))); // 3. while(ps->stmt_class()!=IF_STMT){ ps=ps->next_ref(); } /// cerr<<"\nAdding "<<*ps; preds.push_back(make_pair(&pgm, make_pair(ps->matching_endif_ref(), 0))); } } } } } /// Add it to the pred list and return true if it is not already in. bool add_pred(pair<ProgramUnit*, pair<Statement*, int> >& given, vector<pair<ProgramUnit*, pair<Statement*, int> > >& preds){ vector<pair<ProgramUnit*, pair<Statement*, int> > >::iterator it; for(it=preds.begin(); it!=preds.end(); ++it){ pair<ProgramUnit*, pair<Statement*, int> >& pred=*it; if (pred==given){ return false; } } preds.push_back(given); return true; } void infer_preds(ProgramUnit& pgm, Expression& gate, vector<pair<ProgramUnit*, pair<Statement*, int> > >& preds){ List<Expression> gates; gates.ins_last(gate.clone()); do { /// cerr<<"\ngates = "<<gates; List<Expression> newgates; vector<pair<ProgramUnit*, pair<Statement*, int> > > newpreds; for(Iterator<Expression> eit=gates; eit.valid(); ++eit){ /// ... Trace back. vector<DefTrace::DTrace>* pdt; vector<DefTrace::TransMap>* ptm; trace_defs(pgm, eit.current(), pdt, ptm); /// ... Get preds using ranges. for(unsigned i=0; i<pdt->size(); ++i){ get_preds_from_trace((*pdt)[i], (*ptm)[i], newpreds); } /// cerr<<"\nnewpreds.size="<<newpreds.size(); /// ... Get preds using pe_exit flags. find_preds(pgm, eit.current(), newpreds); /// ... Collect gates for new predicates. vector<pair<ProgramUnit*, pair<Statement*, int> > >::iterator it; for(it=newpreds.begin(); it!=newpreds.end(); ++it){ pair<ProgramUnit*, pair<Statement*, int> >& pred=*it; /// ... silvius: for now, stay within the pgm. if (pred.first!=&pgm) continue; if (add_pred(pred, preds)){ // It is a new one. if (pred.second.first->stmt_class()==ENDIF_STMT){ Statement* ifstmt=pred.second.first->matching_if_ref(); Expression* e=ifstmt->expr().clone(); if (pred.second.second==1){ e=simplify(not(e)); } newgates.ins_last(e); } } } } gates=newgates; } while (gates.entries()); /// cerr<<"\nPred count for gate "<<gate<<" is "<<preds.size(); } static bool incompatible_gates(ProgramUnit& pgm, Expression& gate1, Expression& gate2){ /// cerr<<"\n\tleft = "<<gate1; /// cerr<<"\n\tright = "<<gate2; List<Expression>* inferences=new List<Expression>; infer_gates(pgm, gate1, *inferences); if (inferences->entries()){ Expression* anded=simplify(and(and(and(inferences), not(gate2.clone())), gate1.clone())); /// ... silvius: should do the same with right and left (in this order). if(simplify_using_ranges(pgm, *anded)){ return true; } else { return false; } } else { delete inferences; return false; } } static bool same_commutative(Expression& e1, Expression& e2){ if (e1.op()!=e2.op()){ return false; } if (!is_commutative(e1.op())){ return false; } map<int, Expression*> sorter1, sorter2; for(Iterator<Expression> eit=e1.arg_list(); eit.valid(); ++eit){ sorter1.insert(make_pair(get_hash(eit.current()), &eit.current())); } for(Iterator<Expression> eit=e2.arg_list(); eit.valid(); ++eit){ sorter2.insert(make_pair(get_hash(eit.current()), &eit.current())); } if (sorter1.size()!=sorter2.size()){ return false; } map<int, Expression*>::iterator it1=sorter1.begin(); map<int, Expression*>::iterator it2=sorter2.begin(); for( ; it1!=sorter1.end() && it2!=sorter2.end(); ++it1, ++it2){ if ((*it1).first!=(*it2).first){ return false; } if (! (*(*it1).second == *(*it2).second) ){ return false; } } return true; } bool same_gate(Expression& e1, Expression& e2){ if (e1==e2){ return true; } /// Check for commutative patterns. if (e1.op()==NE_OP && e2.op()==NE_OP || e1.op()==EQ_OP && e2.op()==EQ_OP){ if (e1.left_guarded().type().data_type()==INTEGER_TYPE && e2.left_guarded().type().data_type()==INTEGER_TYPE){ Expression* t1=simplify(sub(e1.left_guarded().clone(), e1.right_guarded().clone())); Expression* t2=simplify(sub(e2.left_guarded().clone(), e2.right_guarded().clone())); if (same_commutative(*t1, *t2)){ delete t1; delete t2; return true; } else { t1=simplify(mul(constant(-1), t1)); if (same_commutative(*t1, *t2)){ delete t1; delete t2; return true; } else { delete t1; delete t2; } } } } return false; } /// Returns true if e1==e3, and e2=....AND.e3.AND.... static bool included_gates(Expression& e1, Expression& e2){ if (same_gate(e1, e2)){ return true; } if (e2.op()!=AND_OP){ return false; } for(Iterator<Expression> eit=e2.arg_list(); eit.valid(); ++eit){ if (same_gate(e1, eit.current())){ return true; } } return false; } /// Returns true if gate1->gate2 /// Based on: /// a -> b <=> .NOT.a.OR.b <=> .NOT.(a.AND..NOT.b) bool implies(ProgramUnit& pgm, Expression& gate1, Expression& gate2){ Expression* not_gate2=not(gate2.clone()); bool result=incompatible_gates(pgm, gate1, *not_gate2); delete not_gate2; if (result){ /// ... We just proved .NOT.(a.AND..NOT.b) return true; } else { if (included_gates(gate2, gate1)){ /// ... gate2 is a part of gate1 return true; } } return false; }

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