Polaris: trans_util.cc Source File

trans_util.cc Go to the documentation of this file. /// /// /*! \brief Translates variables in commons across subroutine boundaries. \author Silvius Rus */ /// #include "Traverser.h" #include <set> #include <map> #include <queue> #include <algorithm> #include "Symbol/FunctionSymbol.h" #include "Expression/ArrayRefExpr.h" #include "Expression/FunctionCallExpr.h" #include "Range/AIRangeDict.h" #include "utilities/lambda_util.h" #include "utilities/stmt_util.h" #include "prog_info.h" #include "trans_util.h" #include "optimize_ssa.h" Translator::Translator(ProgramUnit& caller, Statement& callsite){ _caller=&caller; _callsite=&callsite; _callee=called_pgm(callsite); p_assert(_callee, "Cannot build translator for statements that are not call sites."); } Translator::~Translator(){ } Expression* Translator::translate(Symbol& sym){ if (sym.sym_class()==VARIABLE_CLASS) { return translate_var((VariableSymbol&)sym, *_callee, *_caller, *_callsite); } else { p_abort("Cannot translate symbols that are not variables."); return 0; } } Expression* Translator::actual(Symbol& sym){ if (sym.sym_class()!=VARIABLE_CLASS){ cerr<<"\n sym: "<<sym.name_ref() <<" in routine "<<_callee->routine_name_ref(); p_warning("Non-variable symbol cannot be formal."); return 0; } String sbase; int rank; gsa_details(sym.name_ref(), sbase, rank); /// No translation if this is a non-zero gsa rank. if (rank!=0) { cerr<<"\n sym: "<<sym.name_ref() <<" in routine "<<_callee->routine_name_ref(); p_warning("Can not translate non-entry value."); return 0; } VariableSymbol* base=(VariableSymbol*)&sym; if (base->is_gsa_symbol()){ base=(VariableSymbol*)&base->gsa_base_symbol(); } if (sym.formal()){ Statement* entry=_callee->stmts().first_ref(); while (entry->stmt_class()!=ENTRY_STMT) { entry=entry->next_ref(); p_assert(entry, "Could not find entry to program unit."); } List<Expression>& actuals=parameters(*_callsite); List<Expression>& formals=parameters(*entry); Iterator<Expression> ait=actuals; Iterator<Expression> fit=formals; for ( ; ait.valid() && fit.valid(); ++ait, ++fit){ if (&fit.current().symbol()==base){ if (is_beta(ait.current())){ return ait.current().parameters_guarded().arg_list().last_ref(); } else { return &ait.current(); } } } } else { /// cerr<<"\n sym: "<<sym.name_ref() /// <<" in routine "<<_callee->routine_name_ref(); /// p_warning("Cannot find mapping for a non-formal symbol."); return 0; } return 0; } void display_translation_error(VariableSymbol& sym, ProgramUnit& from, ProgramUnit& to, Statement& callsite){ cerr<<"\nVariable "<<&sym<<":"<<sym.name_ref() <<" upon entry to program unit "<<from.routine_name_ref() <<" when called from program unit "<<to.routine_name_ref() <<" at the callsite at line "<<callsite.line(); static int dummy=1; callsite.write(cerr,dummy); } void display_translation_error(Expression& e, ProgramUnit& from, ProgramUnit& to, Statement& callsite){ cerr<<"Variable "<<e <<" upon entry to program unit "<<from.routine_name_ref() <<" when called from program unit "<<to.routine_name_ref() <<" at the callsite at line "<<callsite.line(); int dummy=1; callsite.write(cerr,dummy); } ProgramUnit* called_pgm(Statement& stmt){ const char* callee_tag=0; if (stmt.stmt_class()==CALL_STMT){ callee_tag=stmt.routine_guarded().symbol().tag_ref(); } else { if (stmt.stmt_class()==ASSIGNMENT_STMT){ if (stmt.rhs().op()==FUNCTION_CALL_OP) { callee_tag=stmt.rhs().function().symbol().tag_ref(); } } } if (!callee_tag) return 0; return entry_points().find_ref(callee_tag); } /*! \brief This function just checks for: - same common block - same position It gives a warning if the resulting name is different. \warning It does not check for the real offset inside the common. */ VariableSymbol* translate_common_var(VariableSymbol& sym, ProgramUnit& from, ProgramUnit& to, Statement& callsite){ if (!sym.common_ref()) return 0; Database<ProgramUnit*, Database<Statement*, RefDatabase<Symbol*, Symbol> > >* gmap=&ip_ssa_gmap(); Database<Statement*, RefDatabase<Symbol*, Symbol> >* lmap= gmap->find_ref(&to); if (!lmap){ display_translation_error(sym, from, to, callsite); p_abort("gmap not set."); } RefDatabase<Symbol*, Symbol>* smap=lmap->find_ref(&callsite); if (!smap){ display_translation_error(sym, from, to, callsite); p_abort("gmap not set."); } VariableSymbol* base=&sym; if (base->is_gsa_symbol()) base=(VariableSymbol*)&base->gsa_base_symbol(); Symbol* trans=to.symtab().find_ref(base->name_ref()); if (trans==0){ display_translation_error(sym, from, to, callsite); p_abort("Commons must be unified before attempting translations."); } VariableSymbol* toret=(VariableSymbol*)smap->find_ref(trans); if (toret==0){ display_translation_error(sym, from, to, callsite); p_abort("Could not translate common name properly."); } return toret; } static Expression* reshape_array(Expression& formal, VariableSymbol& actual_array_sym, Translator& translator, ProgramUnit& from, ProgramUnit& to, Statement& callsite){ /// Use each other. if (formal.op()!=ARRAY_REF_OP) { p_abort("Wrong argument to reshape_array"); } VariableSymbol *formal_symbol=(VariableSymbol *) formal.base_variable_ref(); Expression& subscript_formal=formal.subscript(); Expression* subscript_actual=constant(0); Expression* stride=constant(1); for (int i=0; i<formal_symbol->dim().entries(); i++) { /// ... Compute contribution by dimension (i) Expression* this_dim= translate_and_reshape(translator, from, to, callsite, subscript_formal.arg_list()[i].clone()); this_dim=mul(stride->clone(), this_dim); ; subscript_actual=simplify(add(subscript_actual, this_dim)); /// ... If this is the highest dimension we are done if (i==formal_symbol->dim().entries()-1) { break; } /// ... Compute stride for next dimension. ArrayBounds & formal_bounds = formal_symbol->dim()[i]; Expression * lower; Expression * upper; if (!(formal_bounds.lower_exists())) { lower = constant(1); } else { lower = translate_and_reshape(translator, from, to, callsite, formal_bounds.lower_guarded().clone()); } if (!formal_bounds.upper_exists()) { p_abort("Cannot reshape array because dimensions are not given."); } upper=translate_and_reshape(translator, from, to, callsite, formal_bounds.upper_guarded().clone()); Expression* diff=add(sub(upper, lower), constant(1)); stride=simplify(mul(stride, diff)); } delete stride; List<Expression>* new_sub=new List<Expression>; new_sub->ins_first(subscript_actual); VariableSymbol& actual_symbol=actual_array_sym; for (int i=1; i<actual_symbol.dim().entries(); i++) { new_sub->ins_last(constant(1)); } CommaExpr* new_subscript=new CommaExpr(new_sub); return new ArrayRefExpr(formal.array().symbol().type(), id(actual_array_sym), new_subscript); } /// Checks whether actual parameter is an integer. bool is_actual_integer_constant(VariableSymbol& sym, Translator& translator){ Expression* new_const=0; VariableSymbol* base=0; if (sym.is_gsa_symbol()){ base=(VariableSymbol*)&sym.gsa_base_symbol(); } else { base=&sym; } new_const=translator.actual(*base); if (new_const) { if (new_const->op()==INTEGER_CONSTANT_OP){ return true; } } return false; } Symbol* symbol(Expression* e){ if (!e) return 0; if (e->op()==ID_OP) return &e->symbol(); if (e->op()==ARRAY_REF_OP) return &e->array().symbol(); return 0; } /// Translate from actuals to formals. RefList<Symbol> untranslate_var(Symbol& sym, ProgramUnit& callee, ProgramUnit& caller, Statement& callsite){ RefList<Symbol> toret; switch (sym.sym_class()){ case UNDEFINED_CLASS: p_abort("Cannot translate symbol of undefined type."); case PROGRAM_CLASS: p_abort("Cannot have more than one main subprogram in a program."); case BLOCK_DATA_CLASS: p_abort("Cannot have more than one block data subprogram in a program."); case FUNCTION_CLASS: case SUBROUTINE_CLASS: case SYMBOLIC_CONSTANT_CLASS: { Symbol* found=callee.symtab().find_ref(sym.name_ref()); if (found){ /// ... silvius: should make sure they are the same. toret.ins_last(*found); return toret; } else { Symbol* callee_sym=sym.clone(); callee.symtab().rename_and_ins(callee_sym); } } case VARIABLE_CLASS: break; /// ... See code after this switch statement. case NAMELIST_CLASS: default: p_abort("Unhandled case in untranslate_var."); } /// First check whether this is a function and sym is the return value. if (callsite.stmt_class()==ASSIGNMENT_STMT){ if (callsite.lhs().base_variable_ref()==&sym){ Symbol* fret=callee.symtab().find_ref(callee.routine_name_ref()); p_assert(fret, "Function did not declare return value."); toret.ins_last(*fret); return toret; } } Statement& entry=quick_pgm_entry(callee); List<Expression>& actuals=parameters(callsite); List<Expression>& formals=parameters(entry); Iterator<Expression> ait=actuals; Iterator<Expression> fit=formals; for ( ; ait.valid() && fit.valid(); ++ait, ++fit){ Expression& expr=ait.current(); Symbol* actual=0; if (is_beta(ait.current())){ /// ... Get its base symbol. Expression* last_arg=expr.parameters_guarded().arg_list().last_ref(); if (last_arg->op()==ARRAY_REF_OP){ actual=(VariableSymbol*)&last_arg->array().symbol(); } else { if (last_arg->op()==ID_OP){ actual=(VariableSymbol*)&last_arg->symbol(); } else { p_abort("Expression not supported as actual."); } } } else { actual=symbol(&ait.current()); } /// cerr<<"\nactual = "<<actual->name_ref(); if (actual!=&sym) continue; Symbol* formal=symbol(&fit.current()); p_assert(formal, "Expression not supported as formal."); toret.ins_last(*formal); } /// Check for commons. if (sym.common_ref()){ Symbol* trans=callee.symtab().find_ref(sym.name_ref()); p_assert(trans, "Commons not unified."); p_assert(trans->common_ref(), "Commons not unified."); if (!toret.member(*trans)){ toret.ins_last(*trans); } } return toret; } /// Translate from formals to actuals. Expression* translate_var(VariableSymbol& sym, ProgramUnit& from, ProgramUnit& to, Statement& callsite){ if (!sym.formal() && !sym.common_ref() && sym.sym_class()!=FUNCTION_CLASS){ /// display_translation_error(sym, from, to, callsite); /// p_warning("Cannot translate local."); return 0; } /// Check whether it is an intrinsic. if (sym.intrinsic()){ Symbol* trans=to.symtab().find_ref(sym.name_ref()); if (!trans) { /// ... This intrinsic not in the other symbol table. /// ... Create it. trans=&to.symtab().ins(new FunctionSymbol(sym.name_ref(), sym.type(), NOT_EXTERNAL, IS_INTRINSIC, NOT_FORMAL)); } else { /// ... Check whether it is an intrinsic function. if (!trans->intrinsic()){ display_translation_error(sym, from, to, callsite); p_abort("This variable has an intrinsic name."); } } /// ... If it gets here, trans is the corresponding symbol. return id(*trans); } String sbase; int rank; gsa_details(sym.name_ref(), sbase, rank); /// No translation if this is a non-zero gsa rank. if (rank!=0) { display_translation_error(sym, from, to, callsite); p_warning("Can not translate non-entry value."); return 0; } VariableSymbol* base=0; if (sym.is_gsa_symbol()){ base=(VariableSymbol*)&sym.gsa_base_symbol(); } else { base=&sym; } if (sym.formal()){ /// ... If it gets here it must be formal. Statement* entry=from.stmts().first_ref(); while (entry->stmt_class()!=ENTRY_STMT) { entry=entry->next_ref(); if(entry==0) break; } p_assert(entry, "Could not find program unit entry."); List<Expression>& actuals=parameters(callsite); List<Expression>& formals=parameters(*entry); Iterator<Expression> ait=actuals; Iterator<Expression> fit=formals; for ( ; ait.valid() && fit.valid(); ++ait, ++fit){ KeyIterator<String,ProgramUnit> progiter = program(); if (&fit.current().symbol()==base){ Expression* a=0; if (is_beta(ait.current())){ a=ait.current().parameters_guarded().arg_list().first_ref(); } else { a=ait.current().clone(); } if (a->op()==ALPHA_OP){ return a->parameters_guarded().arg_list()[0].clone(); } else { return a->clone(); } } } display_translation_error(sym, from, to, callsite); p_abort("Formal could not be matched to an actual."); } if (sym.common_ref()){ /// ... Hope this is in a common. VariableSymbol* ct=translate_common_var(sym, from, to, callsite); if (ct) { return id(*ct); } else { p_abort("Failed to translate common ref."); } } display_translation_error(sym, from, to, callsite); p_abort("Translation failed: cause unknown."); return 0; } /// Returns the dimension of this array as number of elements. /// It assumes that the last dimension is defined (not an assumed size array). Expression* array_element_count(Symbol& sym){ Expression* stride=constant(1); for (Iterator<ArrayBounds> abit=sym.dim(); abit.valid(); ++abit){ /// ... Compute new stride. ArrayBounds& ab=abit.current(); Expression* diff=0; if (ab.lower_exists()){ if (ab.upper_exists()){ diff=add(constant(1), sub(ab.upper_guarded().clone(), ab.lower_guarded().clone())); } else { diff=ab.lower_guarded().clone(); } } else { if (ab.upper_exists()){ diff=ab.upper_guarded().clone(); } else { p_abort("Cannot understand array declaration."); } } if (diff==0){ p_abort("'array_element_count' called on assumed size array."); } stride=simplify(mul(stride, diff)); } return stride; } /// Returns the linearized offset of an array expression. /// DIMENSION a(M,N) /// For a(j, i) /// It returns j + i*N Expression* base_offset(Expression* expr){ if (!expr) return 0; if (expr->op()!=ARRAY_REF_OP) return 0; VariableSymbol * newsym = (VariableSymbol *) &expr->array().symbol(); Expression* start_offset=constant(0); int dims=newsym->dim().entries(); int dim=0; Expression* stride=constant(1); Iterator<Expression> actit=expr->subscript().arg_list(); for (Iterator<ArrayBounds> abit=newsym->dim(); abit.valid() && dim<dims; ++abit, ++actit, ++dim){ /// ... Compute offset start_offset=add(start_offset, mul(sub(actit.current().clone(), constant(1)), stride->clone())); if (dim==dims-1) { delete stride; break; /// ... Don't need stride anymore. } /// ... Compute new stride. ArrayBounds& ab=abit.current(); Expression* diff=0; if (ab.lower_exists()){ if (ab.upper_exists()){ diff=add(constant(1), sub(ab.upper_guarded().clone(), ab.lower_guarded().clone())); } else { diff=ab.lower_guarded().clone(); } } else { if (ab.upper_exists()){ diff=ab.upper_guarded().clone(); } else { p_abort("Cannot understand array declaration."); } } stride=simplify(mul(stride, diff)); } start_offset=simplify(start_offset); return start_offset; } Expression* trans_update_expr(Translator& translator, Expression* expr){ if (is_leaf(*expr)) { Symbol * oldsym = expr->base_variable_ref(); if (oldsym == 0) { return expr; } else { return translator.translate(*oldsym); } } else { Traverser tr(*expr, is_leaf); for ( ; tr.valid(); ++tr) { if (tr.current().op() != ID_OP) continue; Assign<Expression> eas = tr.assign(); Expression * epull = tr.pull(); static LambdaInfo lambda(0, 0, INLINE_CALL); /// ... remap_expr while (1) { /// ... Nothing replaced so far Expression* changed = trans_update_expr(translator, epull); if (changed!=epull) { // If this expression was replaced, remove lambda // calls and check the expression again. epull = remove_lambda_calls(changed, lambda); } else { break; } } eas = epull; } return expr; } } Expression* translate_and_reshape( Translator& translator, ProgramUnit& from, ProgramUnit& to, Statement& callsite, Expression* expr){ if (!expr) return 0; if (is_leaf(*expr)){ Expression* new_leaf=0; if (expr->op()==ID_OP){ /// ... If it is an intrinsic, get corresponding one. if (expr->symbol().intrinsic()){ Symbol* tosym=to.symtab().find_ref(expr->symbol().name_ref()); if(tosym==0){ tosym=&to.symtab().ins_intrinsic(expr->symbol().name_ref()); } return id(*tosym); } VariableSymbol& vs=(VariableSymbol&)expr->symbol(); /// ... The symbol must have the GSA rank 0, or no rank at all. /// ... Otherwise, it should not be translated, as it represents a /// ... different value. VariableSymbol* base=(VariableSymbol*)gsa_base(vs); if (base!=&vs){ cerr<<"\n in routine "<<from.routine_name_ref(); cerr<<"\n expr."<<*expr; p_abort("Could not translate name in translate_and_reshape."); } const Expression* new_const=0; VariableSymbol* tovar=0; new_const=translator.actual(*base); if (!new_const) { /// ... Hope this is in a common tovar=translate_common_var(*base, from, to, callsite); if (!tovar){ p_abort("Could not translate name in translate_and_reshape."); return 0; } else { new_leaf=id(*tovar); } } else { new_leaf=new_const->clone(); } } else { /// ... Don't know how to do it, use Jay's version. new_leaf=trans_update_expr(translator, expr); } return new_leaf; } if (expr->op() == ARRAY_REF_OP) { Expression& array=expr->array(); /// ... The symbol must have the GSA rank 0, or no rank at all. /// ... Otherwise, it should not be translated, as it represents a /// ... different value. VariableSymbol& vs=(VariableSymbol&)array.symbol(); VariableSymbol* base=(VariableSymbol*)gsa_base(vs); if (base!=&array.symbol()){ cerr<<"\n in routine "<<from.routine_name_ref(); cerr<<"\n expr."<<*expr; p_abort("Could not translate name in translate_and_reshape."); } Expression* new_array=0; const Expression* new_array_const=0; new_array_const=translator.actual(*base); if (!new_array_const) { /// ... Hope this is in a common VariableSymbol* tovar=translate_common_var(*base, from, to, callsite); if (!tovar){ p_abort("Could not translate name in translate_and_reshape."); return 0; } new_array=id(*tovar); } else { new_array=new_array_const->clone(); } Expression* new_expr=0; if (new_array->op()==ARRAY_REF_OP){ new_expr=reshape_array(*expr, (VariableSymbol&)new_array->array().symbol(), translator, from, to, callsite); /// ... Add actual base offset. Expression* start_offset=base_offset(new_array); Mutator<Expression> mut=new_expr->subscript().arg_list(); Assign<Expression> a = mut.assign(); a=simplify(add(start_offset, mut.pull())); } else { if (new_array->op()==ID_OP){ new_expr=reshape_array(*expr, (VariableSymbol&)new_array->symbol(), translator, from, to, callsite); } else { p_abort("Could not translate array in translate_and_reshape."); } } return new_expr; } else { Mutator<Expression> expit = expr->arg_list(); for ( ; expit.valid(); ++expit) { Assign<Expression> a = expit.assign(); a=translate_and_reshape(translator, from, to, callsite, expit.pull()); } } return expr; } static bool same_base_name(VariableSymbol& sym1, VariableSymbol& sym2){ Symbol* s1=&sym1; Symbol* s2=&sym2; if (sym1.is_gsa_symbol()){ s1=&sym1.gsa_base_symbol(); } if (sym2.is_gsa_symbol()){ s2=&sym2.gsa_base_symbol(); } if (s1==s2) { return true; } return false; } Symbol* syms_in_expr(RefSet<Symbol>& syms, Expression& expr){ if (expr.op() == ID_OP) { Iterator<Symbol> sit=syms; for (sit.reset(); sit.valid(); ++sit){ Symbol& sym=sit.current(); if (same_base_name((VariableSymbol&)expr.symbol(), (VariableSymbol&)sym)) { return &sym; } } } else { Iterator<Expression> expit = expr.arg_list(); for ( ; expit.valid(); ++expit) { Symbol* variant=syms_in_expr(syms, expit.current()); if (variant) return variant; } } return (Symbol*)0; } void referred_symbols(const Expression& expr, RefList<Symbol>& syms){ if (expr.op() == ID_OP) { if (expr.symbol().name_ref()!=String("<BETA>")) { if (expr.symbol().name_ref()!=String("INF")){ if (!syms.member(expr.symbol())){ syms.ins_last(expr.symbol()); } } } } else { Iterator<Expression> expit = expr.arg_list(); for ( ; expit.valid(); ++expit) { referred_symbols(expit.current(), syms); } } } void referred_symbols(const List<AbstractAccess>& lmads, RefList<Symbol>& syms){ for (Iterator<AbstractAccess> aait=lmads; aait.valid(); ++aait){ AbstractAccess& aa=aait.current(); if ( aa.start_exists() ){ referred_symbols(aa.start_guarded(), syms); } Iterator<AccessDimension> adit=aa.iter_dims(); for (adit.reset(); adit.valid(); ++adit){ AccessDimension& ad=adit.current(); if (ad.stride_exists()){ referred_symbols(ad.stride_guarded(), syms); } if (ad.span_exists()){ referred_symbols(ad.span_guarded(), syms); } } } } void referred_symbols(AbstractAccess& aa, RefList<Symbol>& syms){ if ( aa.start_exists() ){ referred_symbols(aa.start_guarded(), syms); } Iterator<AccessDimension> adit=aa.iter_dims(); for (adit.reset(); adit.valid(); ++adit){ AccessDimension& ad=adit.current(); if (ad.stride_exists()){ referred_symbols(ad.stride_guarded(), syms); } if (ad.span_exists()){ referred_symbols(ad.span_guarded(), syms); } } } /*! \brief Separates the given symbol list into two: the ones that can be, ant the ones that cannot be translated between the two given contexts. If there is at least a symbol that cannot be translated, it returns right when it finds it if 'return_asap' is 1 (default). */ bool can_translate(const RefList<Symbol>& given, RefList<Symbol>& can, RefList<Symbol>& cannot, Translator& translator, ProgramUnit& callee, ProgramUnit& caller, Statement& callsite, int return_asap){ for (Iterator<Symbol> sit=given; sit.valid(); ++sit){ /// ... First check whether GSA rank is 0. String name; int rank; gsa_details(sit.current().name_ref(), name, rank); if (rank!=0){ cannot.ins_last(sit.current()); if (return_asap) return false; } /// ... If it gets here, the rank is 0. /// ... Let it go if it is an intrinsic. if (sit.current().intrinsic()){ can.ins_last(sit.current()); continue; } /// ... Let it go if it is an integer constant. bool actual_is_const= is_actual_integer_constant((VariableSymbol&)sit.current(), translator); if (actual_is_const){ can.ins_last(sit.current()); continue; } /// ... Do not even attempt to translate if it is a dummy index. String sname=sit.current().name_ref(); if (sname.index_case("DUMMY_J")!=-1){ cannot.ins_last(sit.current()); if (return_asap) { return false; } else { continue; } } /// ... Try to translate it. Expression* t=translate_var((VariableSymbol&)sit.current(), callee, caller, callsite); if (t){ delete t; can.ins_last(sit.current()); } else { /// ... Cannot translate this symbol, it must be an uninitialized local. display_translation_error((VariableSymbol&)sit.current(), callee, caller, callsite); p_warning("Uninitialized variable may define memory access."); cannot.ins_last(sit.current()); if (return_asap) return false; } } if (cannot.entries()==0) { return true; } else { return false; } } List<Expression>& parameters(Statement& stmt){ if (stmt.stmt_class()==CALL_STMT) return stmt.parameters_guarded().arg_list(); if (stmt.stmt_class()==ASSIGNMENT_STMT) if (stmt.rhs().op()==FUNCTION_CALL_OP) return stmt.rhs().parameters_guarded().arg_list(); if (stmt.stmt_class()==ENTRY_STMT) return stmt.parameters_guarded().arg_list(); p_abort("Statement has no parameters."); } static map<VariableSymbol*, GlobalDefSite> _explicitly_declared_defs; void add_new_definition(VariableSymbol& sym, ProgramUnit& pgm, Statement& stmt){ _explicitly_declared_defs.insert(make_pair(&sym, GlobalDefSite(pgm, stmt))); } void find_defs(VariableSymbol& sym, ProgramUnit& pgm, List<GlobalDefSite>& defs){ /// First loog for a match in the directory of explicitly declared /// definitions. map<VariableSymbol*, GlobalDefSite>::iterator found_def= _explicitly_declared_defs.find(&sym); if (found_def!=_explicitly_declared_defs.end()){ defs.ins_last(new GlobalDefSite((*found_def).second)); return; } Database<ProgramUnit*, Database<Symbol*, List<GlobalDefSite> > >* dmap= &ip_ssa_dmap(); /// silvius: for now treat arrays as scalars. /// Scalar, definition site is known. if (sym.is_scalar() || sym.is_array()){ VariableSymbol* base=&sym; if (sym.is_gsa_symbol()) { base=(VariableSymbol*)&sym.gsa_base_symbol(); String sbase; int rank; gsa_details(sym.name_ref(), sbase, rank); if (rank>0) { DefLoc* defloc=pgm.gsa_deflocs_guarded().find_ref(sym); if (!defloc) { p_abort("Unknown definition site for GSA symbol."); } if (!defloc->stmt_valid()) { p_abort("Invalid definition site for GSA symbol."); } defs.ins_last(new GlobalDefSite(pgm, defloc->stmt_guarded())); return; } } /// ... If it gets here it is either GSA rank 0 or not GSA. /// ... It must be either in a common or formal. if (base->common_ref()){ Database<Symbol*, List<GlobalDefSite> >* lmap=dmap->find_ref(&pgm); if (!lmap) { cerr<<"\nUndefined global variable "<<sym.name_ref() <<" in pgm "<<pgm.routine_name_ref(); p_warning(""); return; } List<GlobalDefSite>* gdsl=lmap->find_ref(base); if (!gdsl) { cerr<<"\nUndefined global variable "<<sym.name_ref() <<" in pgm "<<pgm.routine_name_ref(); p_warning(""); return; } defs=*gdsl; } else { if (base->formal()){ /// ... Return empty set. return; } else { if (base->is_array()){ /// cerr<<"\nPossibly undefined local variable "<<sym.name_ref() /// <<" in pgm "<<pgm.routine_name_ref(); /// p_warning(""); } else { cerr<<"\nUndefined local variable "<<sym.name_ref() <<" in pgm "<<pgm.routine_name_ref(); p_abort(""); } } } } } /// Computes the maximum range for memory accesses based on the DIMENSION /// declaration AbstractAccess* compute_top(Symbol& sym){ AbstractAccess* toret=0; if (sym.is_scalar()) { List<AccessDimension> dims; toret=new AbstractAccess(sym, dims, constant(0)); } else { if (sym.is_array()){ List<AccessDimension> dims; List<Expression>* factors=new List<Expression>; Iterator<ArrayBounds> abit=sym.dim(); bool found_all_bounds=true; for ( ; abit.valid(); ++abit){ ArrayBounds& ab=abit.current(); if (ab.lower_exists()){ if (ab.upper_exists()){ Expression* abup=0; if (ab.upper_guarded().substituted_valid()){ abup=ab.upper_guarded().substituted_guarded().clone(); } else { abup=ab.upper_guarded().clone(); } factors->ins_last(simplify(add(constant(1), sub(abup, ab.lower_guarded().clone())))); } else { factors->ins_last(ab.lower_guarded().clone()); } } else { if (ab.upper_exists()){ Expression* abup=0; if (ab.upper_guarded().substituted_valid()){ abup=ab.upper_guarded().substituted_guarded().clone(); } else { abup=ab.upper_guarded().clone(); } factors->ins_last(abup); } else { found_all_bounds=false; break; } } } if (found_all_bounds){ AccessDimension* ad=new AccessDimension(constant(1), simplify(sub(mul(factors), constant(1)))); dims.ins_first(ad); toret=new AbstractAccess(sym, dims, constant(0), ACCU_EXACT, AR_READ); } else { delete factors; } } } return toret; } /// Computes TOP range based on the Fortran 77 Standard assumption: /// call p(a(i1), a(i2)) /// If p modifies its arguments and i1<i2, then write access in /// subroutine p(b1, b2) /// is upper bounded for b1 by b1(i1:i2-1). /// Otherwise, two formals would be aliased and written (against the standard). void compute_top_range_from_actuals(Program& prog, ProgramUnit& pgm, Statement& callsite, Database<Symbol*, List<Expression> >& arrays){ ProgramUnit* callee=called_pgm(callsite); if (!callee) return; /// ... Not a call site. List<Expression>& actuals=parameters(callsite); Iterator<Expression> ait=actuals; /// First find arrays that are passed to the routine. for (ait=actuals; ait.valid(); ++ait){ VariableSymbol* basesym=0; Expression* index=0; Expression& expr=ait.current(); /// ... Array expr, i.e. call p(a(i)) if (expr.op()==ARRAY_REF_OP){ basesym=(VariableSymbol*)&expr.array().symbol(); index=base_offset(&expr); } /// ... Array symbol, i.e. call p(a) if (expr.op()==ID_OP){ if (expr.symbol().is_array()){ basesym=(VariableSymbol*)&expr.symbol(); index=constant(0); } } /// ... Beta if (is_beta(expr)){ /// ... Get its base symbol. Expression* last_arg=expr.parameters_guarded().arg_list().last_ref(); if (last_arg->op()==ARRAY_REF_OP){ basesym=(VariableSymbol*)&last_arg->array().symbol(); index=base_offset(last_arg); } if (last_arg->op()==ID_OP){ if (last_arg->symbol().is_array()){ basesym=(VariableSymbol*)&last_arg->symbol(); index=constant(0); } } } if (!basesym){ /// ... This is not an array or an array referrence. continue; } if (basesym->is_gsa_symbol()) { basesym=(VariableSymbol*)&basesym->gsa_base_symbol(); } List<Expression>* this_array=arrays.find_ref(basesym); if (!this_array){ this_array=new List<Expression>; arrays.ins(basesym, this_array); } /// ... Find position to insert them sorted. if (!pgm.range_dict_valid()){ cerr<<"\nFor program unit: "<<pgm.routine_name_ref(); p_warning("Range Dictionary is missing or invalid."); pgm.range_dict(new AIRangeDict(pgm)); } RangeAccessor range_acc(pgm.range_dict_guarded(), *(range_stmt(callsite))); int pos=0; /// ... Assume it is the first. bool found_pos=false; if (this_array->entries()==0){ this_array->ins_last(index); } else { for (Iterator<Expression> expit=*this_array; expit.valid(); ++expit, ++pos){ Expression* simple=simplify(expit.current().clone()); Relation comp = range_acc.compare(*index, *simple); if (comp.is_less_than()){ this_array->ins_before(index, &expit.current()); found_pos=true; break; } } if (!found_pos){ Expression* simple=simplify(this_array->last_ref()->clone()); Relation comp = range_acc.compare(*index, *simple); delete simple; if (comp.is_greater_equal()){ this_array->ins_last(index); } else { this_array->ins_last(index); /// cerr<<"\nSubscript "<<*index; /// cerr<<"\nCallsite "<<callsite; /// cerr<<"\nThis array "<<*this_array; /// p_warning("Could not find sorted subscript position at callsite."); } } } } } /// Builds the diamond-shaped structure that contains the call DAG between /// 'to' and 'from'. static void _build_call_diamond(ProgramUnit& from, ProgramUnit& to, set<ProgramUnit*>& pgms){ /// Build upward cone starting from 'from' set<ProgramUnit*> upwards; RefList<ProgramUnit> q; q.ins_first(from); while (q.entries()){ ProgramUnit& pgm=q.grab(0); upwards.insert(&pgm); RefSet<ProgramUnit>& callers=pgm.called_by(); for(Iterator<ProgramUnit> pit=callers; pit.valid(); ++pit){ if (upwards.find(&pit.current())!=upwards.end()){ /// ... Already seen. continue; } else { q.ins_last(pit.current()); } } } /// Build downward cone starting from 'to' set<ProgramUnit*> downward; q.ins_first(to); while (q.entries()){ ProgramUnit& pgm=q.grab(0); downward.insert(&pgm); RefSet<ProgramUnit>& callees=pgm.calls(); for(Iterator<ProgramUnit> pit=callees; pit.valid(); ++pit){ if (downward.find(&pit.current())!=downward.end()){ /// ... Already seen. continue; } else { q.ins_last(pit.current()); } } } /// Get intersection. set_intersection(upwards.begin(), upwards.end(), downward.begin(), downward.end(), inserter(pgms, pgms.begin())); } static void _find_call_sites(ProgramUnit& callee, set<ProgramUnit*>& all_pgms, vector<pair<ProgramUnit*, Statement*> >&call_sites){ RefSet<ProgramUnit>& callers=callee.called_by(); for(Iterator<ProgramUnit> pit=callers; pit.valid(); ++pit){ ProgramUnit& pgm=pit.current(); if (all_pgms.find(&pgm)==all_pgms.end()){ /// ... Skip subprograms not in the given set. continue; } 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)); } } } } /// Translate the given list of symbols. /// This translation may span multiple subprograms but it must /// be unique. For instance, 'from' may be called at different call sites /// on the way to 'to', but all of them must finally correspond to the same /// value in 'to'. const Symbol* translate_sym(ProgramUnit& from, ProgramUnit& to, const Symbol& sym){ set<ProgramUnit*> all_pgms; _build_call_diamond(from, to, all_pgms); queue<pair<const Symbol*, ProgramUnit*> > q; q.push(make_pair(&sym, &from)); const Symbol* target=0; while (q.size()>0){ pair<const Symbol*, ProgramUnit*> current=q.front(); q.pop(); ProgramUnit& pgm=*current.second; const Symbol* s=current.first; if (&pgm==&to){ /// ... This is the final value. if (target){ /// ... Make sure all values are actually the same. /// ... This makes it slower, but could be helpful for debugging. if (target!=s){ p_warning("Two translations found for same symbol."); return 0; } } else { target=s; } } else { /// ... This is just an intermediate value. /// ... Find call sites within the diamond and translate the symbol /// ... upwards. vector<pair<ProgramUnit*, Statement*> > call_sites; _find_call_sites(pgm, all_pgms, call_sites); /// ... Translate upwards. vector<pair<ProgramUnit*, Statement*> >::iterator csit; for (csit=call_sites.begin(); csit!=call_sites.end(); ++csit){ ProgramUnit& current_to=*(*csit).first; Statement& call_site=*(*csit).second; ProgramUnit& current_from=pgm; Expression* t=translate_var((VariableSymbol&)*s, current_from, current_to, call_site); p_assert(t, "Cannot translate input value."); if (t->op()!=ID_OP){ p_warning("Translation of input values - only simple values for now."); // silvius: for now, just return 0 return 0; } /// ... Put translation in queue. q.push(make_pair(&t->symbol(), &current_to)); } } } p_assert(target, "Could not find a suitable translation."); return target; } ProgramUnit* find_main_pgm(Program& prog){ for(KeyIterator<String, ProgramUnit> pit=prog; pit.valid(); ++pit){ ProgramUnit& pgm=pit.current_data(); if (pgm.pu_class()==PROGRAM_PU_TYPE){ return &pgm; } } return 0; } ProgramUnit* find_pgm(Program& prog,const char * routine_name){ for(KeyIterator<String, ProgramUnit> pit=prog; pit.valid(); ++pit){ ProgramUnit& pgm=pit.current_data(); if (strcmp(pgm.routine_name_ref(),routine_name)==0){ return &pgm; } } return 0; } /*! \brief Traverse the callgraph in postorder to produce a reverse topsort ordering of the nodes. */ static void postorder(ProgramUnit& source, vector<ProgramUnit*>& ordered, set<ProgramUnit*>& processed){ /// Check whether already processed. if (processed.find(&source)!=processed.end()){ return; } else { for (Iterator<ProgramUnit> pit=source.calls(); pit.valid(); ++pit){ ProgramUnit& pgm=pit.current(); postorder(pgm, ordered, processed); } processed.insert(&source); ordered.push_back(&source); } } /*! \brief Produce a reverse topsort ordering of the subprograms. */ void topsort_call_dag(Program& prog, vector<ProgramUnit*>& ordered){ prog.compute_call_lists(); set<ProgramUnit*> processed; ProgramUnit* main=find_main_pgm(prog); if (!main){ p_abort("IPA Bottom-up could not find main program."); } postorder(*main, ordered, processed); } Statement* matching_else(Statement* if_stmt){ Statement* stit; for (stit=if_stmt; stit!=0 && stit !=if_stmt->matching_endif_ref(); stit=stit->next_ref()){ if (stit->stmt_class()==ELSE_STMT){ if (stit->lead_ref()==if_stmt){ return stit; } } } return 0; } void get_in_out(ProgramUnit& caller, Statement& callsite, Symbol& sym, Symbol*& incoming, Symbol*& outgoing){ incoming=outgoing=0; /// First check whether it was passed as an actual parameter. for(Iterator<Expression> eit=callsite.act_refs(); eit.valid(); ++eit){ if (eit.current().op()==ID_OP){ if (gsa_base(eit.current().symbol())==&sym){ outgoing=&eit.current().symbol(); } } } if (outgoing){ for(Iterator<Expression> eit=callsite.in_refs(); eit.valid(); ++eit){ if (eit.current().op()==ID_OP){ if (gsa_base(eit.current().symbol())==&sym){ if (&eit.current().symbol()!=outgoing){ incoming=&eit.current().symbol(); } } } } if (incoming==0){ display_translation_error((VariableSymbol&)sym, *called_pgm(callsite), caller, callsite); p_abort("Could not find IN parameter for a given OUT."); } } else { p_assert(sym.common_ref(), "Symbol is neither passed as parameter nor in a common."); Statement* ps=callsite.next_ref(); while (ps){ if (ps->stmt_class()!=ASSIGNMENT_STMT){ break; } if (ps->rhs().op()!=THETA_OP){ break; } if (gsa_base(ps->lhs().symbol())==&sym){ outgoing=&ps->lhs().symbol(); incoming=&ps->rhs().parameters_guarded().arg_list()[0].symbol(); return; } else { ps=ps->next_ref(); } } } } void get_out(ProgramUnit& caller, Statement& callsite, Symbol& sym, Symbol*& outgoing){ outgoing=0; /// First check whether it was passed as an actual parameter. for(Iterator<Expression> eit=callsite.act_refs(); eit.valid(); ++eit){ if (eit.current().op()==ID_OP){ if (gsa_base(eit.current().symbol())==&sym){ outgoing=&eit.current().symbol(); } } } if (outgoing==0){ p_assert(sym.common_ref(), "Symbol is neither passed as parameter nor in a common."); Statement* ps=callsite.next_ref(); while (ps){ if (ps->stmt_class()!=ASSIGNMENT_STMT){ break; } if (ps->rhs().op()!=THETA_OP){ break; } if (gsa_base(ps->lhs().symbol())==&sym){ outgoing=&ps->lhs().symbol(); return; } else { ps=ps->next_ref(); } } } } void get_in(ProgramUnit& caller, Statement& callsite, Symbol& sym, Symbol*& incoming){ ProgramUnit& callee=*called_pgm(callsite); incoming=0; /// First check whether it was passed as an actual parameter. for(Iterator<Expression> eit=callsite.act_refs(); eit.valid(); ++eit){ if (eit.current().op()==ID_OP){ if (gsa_base(eit.current().symbol())==&sym){ incoming=&eit.current().symbol(); } } } if (incoming){ for(Iterator<Expression> eit=callsite.in_refs(); eit.valid(); ++eit){ if (eit.current().op()==ID_OP){ if (gsa_base(eit.current().symbol())==&sym){ if (&eit.current().symbol()!=incoming){ incoming=&eit.current().symbol(); break; } } } } if (incoming==0){ display_translation_error((VariableSymbol&)sym, *called_pgm(callsite), caller, callsite); p_abort("Could not find IN parameter."); } } else { p_assert(sym.common_ref(), "Symbol is neither passed as parameter nor in a common."); Statement* ps=callsite.next_ref(); while (ps){ if (ps->stmt_class()!=ASSIGNMENT_STMT){ break; } if (ps->rhs().op()!=THETA_OP){ break; } if (gsa_base(ps->lhs().symbol())==&sym){ incoming=&ps->rhs().parameters_guarded().arg_list()[0].symbol(); return; } else { ps=ps->next_ref(); } } /// ... Maybe it is just passed in via a common. incoming=translate_common_var((VariableSymbol&)sym, callee, caller, callsite); } } /// Replaces first with second everywhere in given. Expression* replace_expression(Expression* given, Expression& first, /// ... Must be ARRAY_REF or ID Expression& second){ if (first.op()!=ID_OP && first.op()!=ARRAY_REF_OP){ p_abort("First expression must be ID or ARRAY_REF to perform substitution."); } if (!given) return 0; if (given->op()==ID_OP || given->op()==ARRAY_REF_OP){ if (*given==first){ return second.clone(); } else { return given; } } Mutator<Expression> expit = given->arg_list(); for ( ; expit.valid(); ++expit) { Assign<Expression> a = expit.assign(); a=replace_expression(expit.pull(), first, second); } return given; } void replace_expression(AbstractAccess& aa, Expression& first, Expression& second){ if ( aa.start_exists() ){ Expression* tmp=simplify(aa.start_guarded().clone()); tmp=replace_expression(tmp, first, second); aa.start(simplify(tmp)); } Iterator<AccessDimension> adit=aa.iter_dims(); for (adit.reset(); adit.valid(); ++adit){ AccessDimension& ad=adit.current(); if (ad.stride_exists()){ Expression* tmp=simplify(ad.stride_guarded().clone()); tmp=replace_expression(tmp, first, second); ad.stride(simplify(tmp)); } if (ad.span_exists()){ Expression* tmp=simplify(ad.span_guarded().clone()); tmp=replace_expression(tmp, first, second); ad.span(simplify(tmp)); } } } void replace_expression(List<AbstractAccess>& aalist, Expression& first, Expression& second){ for (Iterator<AbstractAccess> aait=aalist; aait.valid(); ++aait){ AbstractAccess& aa=aait.current(); replace_expression(aa, first, second); } } void replace_symbol(AbstractAccess& aa, Symbol& first, Symbol& second){ if ( aa.start_exists() ){ substitute_var(aa.start_guarded(), first, second); } Iterator<AccessDimension> adit=aa.iter_dims(); for (adit.reset(); adit.valid(); ++adit){ AccessDimension& ad=adit.current(); if (ad.stride_exists()){ substitute_var(ad.span_guarded(), first, second); } if (ad.span_exists()){ substitute_var(ad.stride_guarded(), first, second); } } } void replace_symbol(AbstractAccess& aa, Symbol& first, Expression& second){ if ( aa.start_exists() ){ Expression* tmp=aa.start_guarded().clone(); aa.start(simplify(substitute_var(tmp, first, second))); } Iterator<AccessDimension> adit=aa.iter_dims(); for (adit.reset(); adit.valid(); ++adit){ AccessDimension& ad=adit.current(); if (ad.stride_exists()){ Expression* tmp=ad.stride_guarded().clone(); ad.stride(simplify(substitute_var(tmp, first, second))); } if (ad.span_exists()){ Expression* tmp=ad.span_guarded().clone(); ad.span(simplify(substitute_var(tmp, first, second))); } } } void simplify_expressions(AbstractAccess& aa){ if ( aa.start_exists() ){ Expression* tmp=aa.start_guarded().clone(); aa.start(simplify(tmp)); } Iterator<AccessDimension> adit=aa.iter_dims(); for (adit.reset(); adit.valid(); ++adit){ AccessDimension& ad=adit.current(); if (ad.stride_exists()){ Expression* tmp=ad.stride_guarded().clone(); ad.stride(simplify(tmp)); } if (ad.span_exists()){ Expression* tmp=ad.span_guarded().clone(); ad.span(simplify(tmp)); } } } void replace_symbol(List<AbstractAccess>& aalist, Symbol& first, Expression& second){ for (Iterator<AbstractAccess> aait=aalist; aait.valid(); ++aait){ AbstractAccess& aa=aait.current(); if ( aa.start_exists() ){ Expression* tmp=aa.start_guarded().clone(); aa.start(simplify(substitute_var(tmp, first, second))); } Iterator<AccessDimension> adit=aa.iter_dims(); for (adit.reset(); adit.valid(); ++adit){ AccessDimension& ad=adit.current(); if (ad.stride_exists()){ Expression* tmp=ad.stride_guarded().clone(); ad.stride(simplify(substitute_var(tmp, first, second))); } if (ad.span_exists()){ Expression* tmp=ad.span_guarded().clone(); ad.span(simplify(substitute_var(tmp, first, second))); } } } } void replace_symbol(List<AbstractAccess>& aalist, Symbol& first, Symbol& second){ if (&first==&second) return; for (Iterator<AbstractAccess> aait=aalist; aait.valid(); ++aait){ AbstractAccess& aa=aait.current(); replace_symbol(aa, first, second); } } /// Returns whether the given loop executes at least one iteration. Expression* at_least_one_iteration(ProgramUnit& pgm, DoStmt& loop, bool use_range_dict){ if (!use_range_dict){ Expression* toret=or(and(gt(loop.step().clone(), constant(0)), ge(loop.limit().clone(), loop.init().clone())), and(lt(loop.step().clone(), constant(0)), lt(loop.limit().clone(), loop.init().clone()))); return simplify(toret); } if (!pgm.range_dict_valid()){ pgm.range_dict(new AIRangeDict(pgm)); } RangeAccessor ra(pgm.range_dict_guarded(), loop); Relation r=ra.compare(loop.limit(), loop.init()); if (ra.signz(loop.step())==POS_EXPR){ if (r.is_greater_equal()){ return constant(".TRUE."); } else { if (r.is_less_than()){ return constant(".FALSE."); } else { return simplify(ge(loop.limit().clone(), loop.init().clone())); } } } else { if (ra.signz(loop.step())==NEG_EXPR){ if (r.is_less_equal()){ return constant(".TRUE."); } else { if (r.is_greater_than()){ return constant(".FALSE."); } else { return simplify(le(loop.limit().clone(), loop.init().clone())); } } } else { if (r.is_greater_equal()){ return simplify(gt(loop.step().clone(), constant(0))); } else { if (r.is_less_equal()){ return simplify(lt(loop.step().clone(), constant(0))); } else { Expression* toret=or(and(gt(loop.step().clone(), constant(0)), ge(loop.limit().clone(), loop.init().clone())), and(lt(loop.step().clone(), constant(0)), lt(loop.limit().clone(), loop.init().clone()))); return simplify(toret); } } } } } //Guobin: Find out the sub-expressions in expr whose OP_TYPE is the same as //the specified. RefSet<Expression> search_expression(Expression& expr,OP_TYPE o) { RefSet<Expression> results; if(expr.op() == ID_OP) { if(o==ID_OP) { results.ins(expr); return results; } } else { if(expr.op()==o) results.ins(expr); for(Iterator<Expression> iter=expr.arg_list();iter.valid();++iter) { Expression& sub_expr=iter.current(); if(o!=BETA_OP) { if(sub_expr.op()==o) results.ins(sub_expr); } else if(is_beta(sub_expr)) results.ins(sub_expr); RefSet<Expression> sub_results; sub_results=search_expression(sub_expr,o); results+=sub_results; } } return results; } //Guobin: Find out the sub-expressions in stmt whose OP_TYPE is the same as //the specified. RefSet<Expression> search_expression(Statement& stmt,OP_TYPE o) { RefSet<Expression> results; Iterator<Expression> iter=stmt.iterate_expressions(); for(;iter.valid();++iter) { RefSet<Expression> sub_results; Expression& sub_expr=iter.current(); sub_results=search_expression(sub_expr,o); results+=sub_results; } return results; }

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