Polaris: gsa_util.cc Source File

gsa_util.cc Go to the documentation of this file. /// #include "../ProgramUnit.h" #include "../HeapStats.h" #include "../Timer.h" #include "../TranslateObject.h" #include "../Traverser.h" #include "../Expression/expr_funcs.h" #include "../Expression/IDExpr.h" #include "../Statement/AssignmentStmt.h" #include "../Symbol/FunctionSymbol.h" #include "../Symbol/SymbolicConstantSymbol.h" #include "../Symbol/VariableSymbol.h" #include "../GSAPathExpr.h" #include "../GSAPathMap.h" #include "../GSAWorkSpace.h" #include "../PhiPlaceDef.h" #include "ip_ssa/trans_util.h" #include "ip_ssa/ip_ssa.h" #include "dominator_util.h" #include "lambda_util.h" #include "stmt_util.h" #include "switches_util.h" #include "gsa_util.h" inline void avoid_arrays_substitute_var(Expression &e, const Symbol & var, const Symbol & new_var){ /// if (var.is_array()) return; substitute_var(e,var,new_var); } static Statement * make_phi_function(ProgramUnit & pgm, Symbol & v, int fan_in, OP_TYPE op) { p_assert(fan_in > 1, "GSA fail due to only one incoming variable"); List<Expression> *list = new List<Expression>; for (int i = 1; i <= fan_in; ++i) list->ins_last(id(v)); Expression * rhs_expr = NULL; switch(op) { case GAMMA_OP: rhs_expr = gamma(NULL, comma(list)); break; case MU_OP: rhs_expr = mu(comma(list)); break; default: p_abort("Illegal expression op passed to make_phi_function"); } return new AssignmentStmt(pgm.stmts().new_tag(), id(v), rhs_expr); } static Statement * make_phi_function(ProgramUnit & pgm, Symbol & v, Expression &ex) { return new AssignmentStmt(pgm.stmts().new_tag(), id(v), ex.clone()); } /// COMPRESS, EVAL and LINK for building dominator tree static void COMPRESS_S(Statement & v, unsigned int pass) { GSAWorkSpace & v_ws = *(GSAWorkSpace *) v.work_stack().top_ref(pass); GSAWorkSpace & anc_v_ws = *(GSAWorkSpace *) v_ws.ancestor->work_stack().top_ref(pass); if (anc_v_ws.ancestor) { COMPRESS_S(*v_ws.ancestor, pass); GSAWorkSpace & label_anc_v_ws = *(GSAWorkSpace *)anc_v_ws.label->work_stack().top_ref(pass); GSAWorkSpace & label_v_ws = *(GSAWorkSpace *) v_ws.label->work_stack().top_ref(pass); if (label_anc_v_ws.semi<label_v_ws.semi) v_ws.label = anc_v_ws.label; /// ... Link the definition information from the root down. GSAWorkSpace & anc_anc_v_ws = *(GSAWorkSpace *) anc_v_ws.ancestor->work_stack().top_ref(pass); *anc_v_ws._b_label_def |= *anc_anc_v_ws._b_label_def; v_ws.ancestor = anc_v_ws.ancestor; } /// ... Link the definition information from its ancestor. *v_ws._b_label_def |= *anc_v_ws._b_label_def; } static Statement & EVAL_S(Statement & stmt, unsigned int pass, IntSet & EVALDEF) { /// Check to see if statement has work space (unreachable code /// does not) GSAWorkSpace * stmt_ws_ptr = (GSAWorkSpace *) stmt.work_stack().top_ref(pass); if (!stmt_ws_ptr || !stmt_ws_ptr->ancestor) { EVALDEF.clear(); return stmt; } COMPRESS_S(stmt, pass); if (stmt_ws_ptr->_b_label_def) EVALDEF = *(stmt_ws_ptr->_b_label_def); return *stmt_ws_ptr->label; } static void LINK_S(Statement * v, Statement & w, unsigned int pass) { GSAWorkSpace & w_ws = *(GSAWorkSpace *) w.work_stack().top_ref(pass); /// ... Update w's label_def to include its sdef and def /// ... since it is no longer the root in the forest. *w_ws._b_label_def |= *w_ws._b_sdef; if (w_ws._i_b_def >= 0) w_ws._b_label_def->ins(w_ws._i_b_def); else *w_ws._b_label_def |= *w_ws._b_def; w_ws.ancestor = v; } static void DFS_S(Statement & first_stmt, Array<Statement *> &vertex, unsigned int pass, Dictionary<PhiPlaceDef> *V, const Map<Symbol,IntElem> &candidates, int size) { /// Originally, first statement is on top of stack Statement * stack_stmt_ptr = &first_stmt; GSAWorkSpace * stack_stmt_ws_ptr = 0; /// Initialize vertex array pointer int array_index = -1; /// First statement has no parent Statement * parent_stmt_ptr = 0; /// Loop until stack is empty while (1) { /// ... Check to see if our object is on workspace stack if (!stack_stmt_ws_ptr) { /// ... No, this must be a newly pushed item /// ... Allocate workspace for top of stack stack_stmt_ws_ptr = new GSAWorkSpace(pass, size); /// ... Put top of stack into vertex array vertex[++array_index] = stack_stmt_ptr; /// ... Put workspace onto top of stack stack_stmt_ptr->work_stack().push(stack_stmt_ws_ptr); /// ... Set semi field stack_stmt_ws_ptr->semi = array_index + 1; /// ... Set parent pointer to parent stack_stmt_ws_ptr->parent = parent_stmt_ptr; /// ... initialize the def(s) stack_stmt_ws_ptr->_b_sdef = new IntSet(size); stack_stmt_ws_ptr->_b_idef = new IntSet(size); stack_stmt_ws_ptr->_b_label_def = new IntSet(size); if (stack_stmt_ptr->stmt_class() == ASSIGNMENT_STMT){ Expression &d = stack_stmt_ptr->lhs(); if (d.op() == ID_OP || d.op() == ARRAY_REF_OP || d.op() == SUBSTRING_OP) { Symbol *sym = d.base_variable_ref(); stack_stmt_ws_ptr->_i_b_def = *candidates.find_ref(*sym); PhiPlaceDef *v = V->find_ref(sym->name_ref()); v->involved = 1; } } else { stack_stmt_ws_ptr->_b_def = new IntSet(size); for (Iterator<Expression> def = stack_stmt_ptr->out_refs(); def.valid(); ++def) { Expression &d = def.current(); if (d.op() == ID_OP || d.op() == ARRAY_REF_OP || d.op() == SUBSTRING_OP) { Symbol *sym = d.base_variable_ref(); if (sym->sym_class() != SYMBOLIC_CONSTANT_CLASS) stack_stmt_ws_ptr->_b_def->ins(*candidates.find_ref(*sym)); PhiPlaceDef *v = V->find_ref(sym->name_ref()); v->involved = 1; } } } } /// ... Indicate that no push has occurred parent_stmt_ptr = 0; /// ... Examine each successor which has not been seen before if (!stack_stmt_ws_ptr->label) { Iterator<Statement> succ_iter(stack_stmt_ptr->succ(), stack_stmt_ws_ptr->ancestor, 0); while (succ_iter.valid()) { /// ... Get reference to successor Statement & succ_stmt = succ_iter.current(); /// ... Increment iterator now, so we can resume at next successor ++succ_iter; /// ... Process successor next if it does not have our workspace GSAWorkSpace * succ_stmt_ws_ptr = (GSAWorkSpace *) succ_stmt.work_stack().top_ref(pass); if (!succ_stmt_ws_ptr) { // Check for continuation if (succ_iter.valid()) { // Continue processing with next successor stack_stmt_ws_ptr->ancestor = &succ_iter.current(); } else { /// ... Set label field to signal no more successor processing stack_stmt_ws_ptr->label = stack_stmt_ptr; } // Push successor onto top of stack parent_stmt_ptr = stack_stmt_ptr; stack_stmt_ptr = &succ_stmt; stack_stmt_ws_ptr = 0; break; } } /// ... Skip cleanup processing if push if (parent_stmt_ptr) continue; /// ... Set label field to signal no more successor processing stack_stmt_ws_ptr->label = stack_stmt_ptr; } /// ... Clean up ancestor pointer stack_stmt_ws_ptr->ancestor = 0; /// ... Pop statement off stack and point to new top of stack stack_stmt_ptr = stack_stmt_ws_ptr->parent; /// ... If stack is empty, no more processing if (!stack_stmt_ptr) break; /// ... Look up workspace pointer stack_stmt_ws_ptr = (GSAWorkSpace *) stack_stmt_ptr->work_stack().top_ref(pass); } /// If we skipped over unreachable code, resize array if (array_index + 1< vertex.entries()) vertex.resize(array_index+1); } static void Dominator_S(ProgramUnit & pgm, Array<Statement *> & vertex, unsigned int pass, Dictionary<PhiPlaceDef> *V, const Map<Symbol,IntElem> &candidates, const Array<Symbol *> & NOTUSED(tag_to_candidate), int size) { DFS_S(*pgm.stmts().first_ref(), vertex, pass, V, candidates, size); IntSet EVALDEF(size); int i; for (i = vertex.entries() - 1; i > 0; i--) { Statement & w = *vertex[i]; GSAWorkSpace & w_ws = *(GSAWorkSpace *) w.work_stack().top_ref(pass); { for (Iterator<Statement>v = w.pred(); v.valid(); ++v) { Statement & u = EVAL_S(v.current(), pass, EVALDEF); GSAWorkSpace * u_ws_ptr = (GSAWorkSpace *) u.work_stack().top_ref(pass); if (u_ws_ptr) { if (u_ws_ptr->semi<w_ws.semi) w_ws.semi = u_ws_ptr->semi; *w_ws._b_sdef |= EVALDEF; } } Statement & t = *vertex[w_ws.semi - 1]; /* Debugging statement cout << "Statement: " << w.tag() << ", Bucket Statement: " << t.tag() << '\n'; */ GSAWorkSpace & ws_t = *(GSAWorkSpace *) t.work_stack().top_ref(pass); ws_t.bucket.ins_last(w); LINK_S(w_ws.parent, w, pass); } { GSAWorkSpace & p_ws = *(GSAWorkSpace *) w_ws.parent->work_stack().top_ref(pass); /* Debugging statement cout << "Statement: " << w.tag() << ", Parent Statement: " << w_ws.parent->tag() << '\n'; */ for (Mutator<Statement> v = p_ws.bucket; v.valid(); ++v) { Statement & vc = v.current(); /* Debugging statement cout << "Bucket Statement: " << vc.tag() << '\n'; */ Statement & u = EVAL_S(vc, pass, EVALDEF); GSAWorkSpace & u_ws = *(GSAWorkSpace *) u.work_stack().top_ref(pass); GSAWorkSpace & v_ws = *(GSAWorkSpace *) vc.work_stack().top_ref(pass); v_ws.idom = ((u_ws.semi < v_ws.semi) ? &u : w_ws.parent); EVAL_S(*v_ws.parent, pass, EVALDEF); /* Debugging statement cout << "Before or statements: " << *v_ws._b_idef << '\n'; */ *v_ws._b_idef |= *v_ws._b_sdef; /* Debugging statement cout << "After 1st or statement: " << *v_ws._b_idef << '\n'; */ *v_ws._b_idef |= EVALDEF; /* Debugging statement cout << "After 2nd or statement: " << *v_ws._b_idef << '\n'; */ v.del(); } } EVALDEF.clear(); } for (i = 1; i < vertex.entries(); ++i) { Statement & w = *vertex[i]; /* Debugging statement cout << "Statement: " << w.tag() << '\n'; */ GSAWorkSpace & w_ws = *(GSAWorkSpace *) w.work_stack().top_ref(pass); if (w_ws.idom && w_ws.idom != vertex[w_ws.semi - 1]) { GSAWorkSpace & d_ws = *(GSAWorkSpace *) w_ws.idom->work_stack().top_ref(pass); w_ws.idom = d_ws.idom; /* Debugging statement cout << "Before or statement: " << *w_ws._b_idef << '\n'; */ *w_ws._b_idef |= *d_ws._b_idef; /* Debugging statement cout << "After or statement: " << *w_ws._b_idef << '\n'; */ } } for (i = 1; i < vertex.entries(); ++i) { Statement & w = *vertex[i]; GSAWorkSpace & w_ws = *(GSAWorkSpace *) w.work_stack().top_ref(pass); w_ws.ancestor = NULL; Statement & p = *w_ws.idom; GSAWorkSpace & p_ws = *(GSAWorkSpace *) p.work_stack().top_ref(pass); p_ws.bucket.ins_last(w); } if (switch_value("gsa_prt_dom") == 1) write_idom(vertex, cout, pass); } static Dictionary<PhiPlaceDef> * Variable_set_new(const ProgramUnit & pgm, Map<Symbol,IntElem> &candidates, Array<Symbol *> &tag_to_candidate, int &tag) { Dictionary<PhiPlaceDef> *V = new Dictionary<PhiPlaceDef>; tag_to_candidate.resize(pgm.symtab().entries()); for (DictionaryIter<Symbol> sym = pgm.symtab().iterator(); sym.valid(); ++sym) { Symbol &sb = sym.current(); if (sb.sym_class() == VARIABLE_CLASS || sb.sym_class() == FUNCTION_CLASS || sb.sym_class() == SYMBOLIC_CONSTANT_CLASS){ V->ins(new PhiPlaceDef(sb)); tag_to_candidate[tag] = &sb; candidates.ins(sb, new IntElem(tag++)); } } tag_to_candidate.resize(tag); return V; } static void insert_pseudo_assignment_stmts(ProgramUnit &pgm, Array<Statement *> &vertex, Array<Symbol *> &tag_to_candidate, unsigned int pass) { for (int i = 0; i < vertex.entries(); i++) { Statement &w = *vertex[i]; GSAWorkSpace &ws = *(GSAWorkSpace *) w.work_stack().top_ref(pass); switch (w.stmt_class()) { case DO_STMT: { for (int elem = ws._b_idef->first(); elem != -1; elem = ws._b_idef->next(elem)){ Symbol *sym = tag_to_candidate[elem]; if (sym != w.index().base_variable_ref()){ ws.PHI_name.ins_last(*sym); #if 0 if (ws.path_star && ws.path_star->expr) ws.PHI->ins_last(make_phi_function(pgm, *sym, *(ws.path_star->expr))); else ws.PHI->ins_last(make_phi_function(pgm, *sym, w.pred().entries(), MU_OP)); #endif ws.PHI->ins_last(make_phi_function(pgm, *sym, w.pred().entries(), MU_OP)); } } } break; default: for (int elem = ws._b_idef->first(); elem != -1; elem = ws._b_idef->next(elem)){ Symbol *sym = tag_to_candidate[elem]; ws.PHI_name.ins_last(*sym); ws.PHI->ins_last(make_phi_function(pgm, *sym, w.pred().entries(), GAMMA_OP)); } } delete ws._b_def; ws._b_def = NULL; delete ws._b_label_def; ws._b_label_def = NULL; delete ws._b_idef; ws._b_idef = NULL; delete ws._b_sdef; ws._b_sdef = NULL; } } static void array_in_subscript(RefSet<Symbol>&all, List<Expression>&args) { for (Iterator<Expression>iter = args; iter.valid(); ++iter) { if (iter.current().op() == ARRAY_REF_OP) all.ins(*iter.current().base_variable_ref()); else if (iter.current().arg_list().entries()) array_in_subscript(all, iter.current().arg_list()); } } static String integer_to_string(int i) { String result; char number[] = "0123456789"; String t = " "; do { t[0] = number[i % 10]; result = t + result; i = i / 10; } while (i > 0); return result; } static void InitializeGSAStack(TranslateObject & trans_obj, Dictionary<PhiPlaceDef>*V) { ProgramUnit & pgm = trans_obj.pgm_main(); for (DictionaryIter<PhiPlaceDef> v = *V; v.valid(); ++v) { if (v.current().involved) { Symbol & old_var = *v.current().var; String var(old_var.name_ref()); var += "@"; var += integer_to_string(0); Symbol *t; if (old_var.sym_class() == VARIABLE_CLASS){ t = new VariableSymbol(var, old_var.type(), old_var.formal(), old_var.saved() ); t->dim() = old_var.dim(); t->shared_dim() = old_var.shared_dim(); VariableSymbol & new_var = (VariableSymbol &)pgm.symtab().ins(t); new_var.gsa_base_symbol( old_var ); } else if (old_var.sym_class() == FUNCTION_CLASS) { t = new FunctionSymbol(var, old_var.type(), old_var.external(), old_var.intrinsic(), old_var.formal(), old_var.entry_ref() ); pgm.symtab().ins(t); } else { /// ... SYMBOLIC_CONSTANT_CLASS t = new SymbolicConstantSymbol(var, old_var.expr_ref()->clone()); pgm.symtab().ins(t); } v.current().syms.push(*t); trans_obj.GSA_mapping(*t,old_var); } } } static int occurs(Expression &expr, int pos) { if (is_pseudo_function(expr)) { Mutator<Expression> iter = expr.parameters_guarded().arg_list(); for ( ; iter.valid(); ++iter) if (occurs(iter.current(), pos)) return 1; return 0; } else if (expr.op() == INTEGER_CONSTANT_OP && expr.value() == pos) return 1; return 0; } static Expression * substitute_argument(Expression *expr, int pos, Expression &subs) { if (is_pseudo_function(*expr)) { Mutator<Expression> iter = expr->parameters_guarded().arg_list(); for ( ; iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); eas = substitute_argument(iter.pull(), pos, subs); } return expr; } else if (((pos<0) && (expr->op()==OMEGA_OP)) || ((expr->op() == INTEGER_CONSTANT_OP) && (expr->value() == pos))) { delete expr; return subs.clone(); } else return expr; } static void get_variable_clone(Expression & expr, List<Expression>*l) { if (expr.op() == ID_OP || expr.op() == ARRAY_REF_OP || expr.op() == SUBSTRING_OP) l->ins_last(expr.clone()); else if (expr.op() == FUNCTION_CALL_OP) get_variable_clone(expr.parameters_guarded(), l); else { for (Iterator<Expression>iter = expr.arg_list(); iter.valid(); ++iter) { if (iter.current().op() == FUNCTION_CALL_OP) get_variable_clone(iter.current(), l); } } } static void fix_substituted(Expression& expr, Symbol& n, Symbol& s){ /// cerr<<"\nNow in expr "<<expr; if (expr.op()==ID_OP){ if (expr.symbol().is_array() || expr.symbol().is_scalar()){ /// cerr<<"\nIt is ID."; IDExpr& idexpr=(IDExpr&)expr; if (idexpr.substituted_valid()){ /// cerr<<"\nBefore substitution: "<<idexpr.substituted_guarded(); avoid_arrays_substitute_var(idexpr.substituted_guarded(), n, s); /// cerr<<"\nAfter substitution: "<<idexpr.substituted_guarded(); } } } else { /// cerr<<"\nIt is NOT ID."; Iterator<Expression> expit=expr.arg_list(); for ( expit.reset() ; expit.valid(); ++expit){ fix_substituted(expit.current(), n, s); } } } static void find_id_exprs(Expression& expr, RefList<Symbol>& all){ if (expr.op()==ID_OP){ if (expr.symbol().is_array() || expr.symbol().is_scalar()){ all.ins_first(expr.symbol()); } } else { Iterator<Expression> expit=expr.arg_list(); for ( expit.reset() ; expit.valid(); ++expit){ find_id_exprs(expit.current(), all); } } } static void find_substituted_id_exprs(Expression& expr, RefList<Symbol>& all){ if (expr.op()==ID_OP){ IDExpr& idexpr=(IDExpr&)expr; if (idexpr.substituted_valid()){ find_id_exprs(idexpr.substituted_guarded(), all); } } else { Iterator<Expression> expit=expr.arg_list(); for ( expit.reset() ; expit.valid(); ++expit){ find_substituted_id_exprs(expit.current(), all); } } } static void print_substituted(Expression& expr){ if (expr.op()==ID_OP){ cerr<<"\nOriginal expression: "<<expr <<"\tsubstituted: "; if (expr.substituted_valid()){ cerr<<expr.substituted_guarded(); } else { cerr<<"NULL"; } } else { Iterator<Expression> expit=expr.arg_list(); for ( expit.reset() ; expit.valid(); ++expit){ print_substituted(expit.current()); } } } static void SEARCH(TranslateObject & trans_obj, Statement & X, Dictionary<PhiPlaceDef>&V, unsigned int pass, Symbol * beta) { #if 0 cout << X << "\n"; #endif ProgramUnit & pgm = trans_obj.pgm_main(); RefStack<Symbol> oldLHS; RefList<Symbol> old_name; RefList<Symbol> subst; #if 0 X.in_refs().print(cout); cout << "\n"; #endif for (Iterator<Expression> use = X.in_refs(); use.valid(); ++use) { PhiPlaceDef *v = V.find_ref(use.current().base_variable_ref()->name_ref()); if (v->involved && !old_name.member(*v->var)) { old_name.ins_last(*v->var); subst.ins_last(v->syms.top_guarded()); } } /// ... Get the variables for each of the parameter; List<Expression> new_p; if (X.stmt_class() == CALL_STMT) { for (Iterator<Expression> iter = X.parameters_guarded().arg_list(); iter.valid(); ++iter) { List<Expression> *t = new List<Expression>; get_variable_clone(iter.current(), t); new_p.ins_last(comma(t)); } } Iterator<Symbol> iter_n = old_name; Iterator<Symbol> iter_s = subst; Mutator<Expression> iter_e = X.iterate_expressions(); #if 0 /// ... Replace the names in the INDUCTION assertion with the GSA version for (Iterator<Assertion> a_iter2 = X.assertions(); a_iter2.valid(); ++a_iter2) { if (a_iter2.current().type() == AS_INDUCTION) { if (a_iter2.current().arg_list_valid()) { for (Mutator<Expression> ex_iter = a_iter2.current().arg_list_guarded(); ex_iter.valid(); ++ex_iter) { Expression & assert_expr = ex_iter.current(); for (iter_n.reset(),iter_s.reset(); iter_s.valid(); ++iter_s, ++iter_n) avoid_arrays_substitute_var(assert_expr, iter_n.current(), iter_s.current()); } } } } #endif switch (X.stmt_class()) { case ASSIGNMENT_STMT: { ++iter_e; Expression &rhs_t = iter_e.current(); for (iter_n.reset(),iter_s.reset(); iter_s.valid(); ++iter_s, ++iter_n) avoid_arrays_substitute_var(rhs_t, iter_n.current(), iter_s.current()); break; } case READ_STMT: case WRITE_STMT: break; default: { for ( ; iter_e.valid(); ++iter_e) { Expression &rhs_t = iter_e.current(); for (iter_n.reset(),iter_s.reset(); iter_s.valid(); ++iter_s, ++iter_n) avoid_arrays_substitute_var(rhs_t,iter_n.current(),iter_s.current()); } break; } } /// ... Make BETA assignment to subroutine call parameters if (X.stmt_class() == CALL_STMT) { Mutator<Expression> iter_1 = new_p; for (Mutator<Expression> iter = X.parameters_guarded().arg_list(); iter.valid() && iter_1.valid(); ++iter, ++iter_1) { Expression *t = iter_1.grab(); if (t->arg_list().entries()) { t->arg_list().ins_first(alpha(comma(iter.current().clone()))); iter.modify(function_call(id(*beta), t)); } else { delete t; } } } /// ... Make a PHI assignment for an array assignment if (X.stmt_class() == ASSIGNMENT_STMT && (X.lhs().op() == ARRAY_REF_OP || X.lhs().op() == SUBSTRING_OP)) { PhiPlaceDef *v = V.find_ref(X.lhs().base_variable_ref()->name_ref()); if (v->involved) { iter_e.set_to_last(); Assign<Expression> eas(iter_e.assign()); eas = alpha(comma(id(v->syms.top_guarded()), iter_e.pull())); } } X.build_refs(); #if 0 cout << X << "\n"; X.out_refs().print(cout); cout << "\n"; #endif { RefList<Symbol> old_name; RefList<Symbol> subst; for (Iterator<Expression> def = X.out_refs(); def.valid(); ++def) { Expression &dc = def.current(); PhiPlaceDef *v = V.find_ref(dc.base_variable_ref()->name_ref()); if (v && v->involved && (!old_name.member(*v->var))) { Symbol & old_var = *v->var; oldLHS.push(*dc.base_variable_ref()); v->C += 1; int i = v->C; String var_i(old_var.name_ref()); var_i += "@"; var_i += integer_to_string(i); Symbol *t; if (old_var.sym_class() == VARIABLE_CLASS){ t = new VariableSymbol(var_i, old_var.type(), old_var.formal(), old_var.saved() ); t->dim() = old_var.dim(); t->shared_dim() = old_var.shared_dim(); VariableSymbol & new_var = (VariableSymbol &)pgm.symtab().ins(t); new_var.gsa_base_symbol( old_var ); } else if (old_var.sym_class() == FUNCTION_CLASS) { t = new FunctionSymbol(var_i, old_var.type(), old_var.external(), old_var.intrinsic(), old_var.formal(), old_var.entry_ref() ); pgm.symtab().ins(t); } else { /// ... SYMBOLIC_CONSTANT_CLASS t = new SymbolicConstantSymbol(var_i,old_var.expr_ref()->clone()); pgm.symtab().ins(t); } v->syms.push(*t); trans_obj.GSA_mapping(*t,old_var); old_name.ins_last(old_var); subst.ins_last(*t); } } Iterator<Symbol> iter_n = old_name; Iterator<Symbol> iter_s = subst; Mutator<Expression> iter_e = X.iterate_expressions(); switch (X.stmt_class()) { case ASSIGNMENT_STMT: case DO_STMT: { Expression &lhs_t = iter_e.current(); for ( ; iter_s.valid(); ++iter_s, ++iter_n) avoid_arrays_substitute_var(lhs_t, iter_n.current(), iter_s.current()); break; } default: { for ( ; iter_e.valid(); ++iter_e) { Expression &lhs_t = iter_e.current(); for (iter_n.reset(),iter_s.reset(); iter_s.valid(); ++iter_s, ++iter_n) avoid_arrays_substitute_var(lhs_t,iter_n.current(),iter_s.current()); } break; } } old_name.clear(); subst.clear(); } /// ... Replace variable uses on the left hand side of the assignment iter_e.reset(); switch (X.stmt_class()) { case ASSIGNMENT_STMT: { Expression &lhs_t = iter_e.current(); for ( iter_n.reset(),iter_s.reset(); iter_s.valid(); ++iter_s, ++iter_n) avoid_arrays_substitute_var(lhs_t, iter_n.current(), iter_s.current()); break; } case READ_STMT: case WRITE_STMT: { for ( ; iter_e.valid(); ++iter_e) { Expression &rhs_t = iter_e.current(); for (iter_n.reset(),iter_s.reset(); iter_s.valid(); ++iter_s, ++iter_n) avoid_arrays_substitute_var(rhs_t,iter_n.current(),iter_s.current()); } } default: break; } old_name.clear(); subst.clear(); /// ... Handle PHI function assignment statements GSAWorkSpace & X_ws = *(GSAWorkSpace *) X.work_stack().top_ref(pass); Iterator<Statement> p_stmt = *X_ws.PHI; Iterator<Symbol> p_name = X_ws.PHI_name; for ( ; p_name.valid(); ++p_name, ++p_stmt) { Symbol &pn = p_name.current(); oldLHS.push(pn); PhiPlaceDef *v = V.find_ref(pn.name_ref()); Symbol & old_var = *v->var; v->C += 1; int i = v->C; String var_i(old_var.name_ref()); var_i += "@"; var_i += integer_to_string(i); Symbol *t; if (old_var.sym_class() == VARIABLE_CLASS){ t = new VariableSymbol(var_i, old_var.type(), old_var.formal(), old_var.saved() ); t->dim() = old_var.dim(); t->shared_dim() = old_var.shared_dim(); VariableSymbol & new_var = (VariableSymbol &)pgm.symtab().ins(t); new_var.gsa_base_symbol( old_var ); } else if (old_var.sym_class() == FUNCTION_CLASS) { t = new FunctionSymbol(var_i, old_var.type(), old_var.external(), old_var.intrinsic(), old_var.formal(), old_var.entry_ref() ); pgm.symtab().ins(t); } else { /// ... SYMBOLIC_CONSTANT_CLASS t = new SymbolicConstantSymbol(var_i,old_var.expr_ref()->clone()); pgm.symtab().ins(t); } v->syms.push(*t); trans_obj.GSA_mapping(*t,old_var); Expression &lhs_t = p_stmt.current().lhs(); avoid_arrays_substitute_var(lhs_t, old_var, *t); } for (Iterator<Statement> Y = X.succ(); Y.valid(); ++Y) { GSAWorkSpace & Y_ws = *(GSAWorkSpace *) Y.current().work_stack().top_ref(pass); int i ; if (Y.current().stmt_class() == DO_STMT){ if (Y.current().follow_ref() == &X) i = 1; else i = 0; } else i = Y.current().pred()._member(X); p_assert(i >= 0, "X is not a predecessor of Y"); Iterator<Symbol> p_n = Y_ws.PHI_name; Iterator<Statement> phi = *Y_ws.PHI; for ( ; phi.valid(); ++phi, ++p_n) { PhiPlaceDef *v = V.find_ref(p_n.current().name_ref()); avoid_arrays_substitute_var(phi.current().rhs().parameters_guarded().arg_list()[i], p_n.current(), v->syms.top_guarded()); } } /// ... Silvius /// ... Replace the names in the 'substituted' fields /// ... First collect all ids that need to be replaced with their gsa names RefList<Symbol> id_exprs_in_subst; Iterator<Expression> expit=X.iterate_expressions(); for ( ; expit.valid(); ++expit){ find_substituted_id_exprs(expit.current(), id_exprs_in_subst); } RefList<Symbol> s_old_name; RefList<Symbol> s_new_name; for (Iterator<Symbol> use = id_exprs_in_subst; use.valid(); ++use) { PhiPlaceDef *v = V.find_ref(use.current().name_ref()); if (v->involved && !old_name.member(*v->var)) { s_old_name.ins_last(*v->var); s_new_name.ins_last(v->syms.top_guarded()); } } Iterator<Symbol> in=s_old_name; Iterator<Symbol> is=s_new_name; /// ... Now go through the 'substituted' and update them for ( ; is.valid(); ++is, ++in) { for (expit=X.iterate_expressions(); expit.valid(); ++expit){ fix_substituted(expit.current(), in.current(), is.current()); } } // Silvius: gmap is part of the interprocedural ssa pass (base/ip_ssa) /// ... Build database containing common variables values at call sites. if (called_pgm(X)){ /// ... This is a call site. Database<Statement*, RefDatabase<Symbol*, Symbol> >* lmap= ip_ssa_gmap().find_ref(&pgm); if (!lmap) { lmap=new Database<Statement*, RefDatabase<Symbol*, Symbol> >; ip_ssa_gmap().ins(&pgm, lmap); } RefDatabase<Symbol*, Symbol>* smap=lmap->find_ref(&X); if (!smap) { smap=new RefDatabase<Symbol*, Symbol>; lmap->ins(&X, smap); } for (DictionaryIter<Symbol> sit=pgm.symtab().iterator(); sit.valid(); ++sit){ Symbol& sym=sit.current(); if (sym.common_ref()){ PhiPlaceDef *v = V.find_ref(sym.name_ref()); p_assert(v, "Could not find ref in GSA::SEARCH."); if (v->involved){ if (v->var){ smap->ins(v->var, v->syms.top_guarded()); } } else { if (v->var){ smap->ins(v->var, *v->var); } } } } } { for (Iterator<Statement> Y = X_ws.bucket; Y.valid(); ++Y) SEARCH(trans_obj, Y.current(), V, pass, beta); } while (oldLHS.entries()) { Symbol &top = oldLHS.pop(); PhiPlaceDef *v = V.find_ref(top.name_ref()); v->syms.pop(); } X.build_refs(); } static void InsertPhiStmt(ProgramUnit & pgm, Array<Statement *> &vertex, unsigned int pass, int GSA) { if (GSA) { /// ... Fill the gating functions for (int i = 0; i<vertex.entries(); ++i) { Statement & w = *vertex[i]; GSAWorkSpace & w_ws = *(GSAWorkSpace *) w.work_stack().top_ref(pass); if (w_ws.PHI->entries() && w.stmt_class() != FLOW_EXIT_STMT) { w_ws.path_idom->fill_expr(); if (w_ws.path_star) { if (w.pred().entries()>2){ if (w.stmt_class()==DO_STMT) w_ws.path_star->fill_expr(w_ws.path_idom->expr); else w_ws.path_star->fill_expr(w_ws.path_idom->expr); } else { delete w_ws.path_idom->expr; if (w.stmt_class()==DO_STMT) w_ws.path_star->fill_expr(NULL); else w_ws.path_star->fill_expr(NULL); } w_ws.path_idom->expr = NULL; } for (Iterator<Statement> iter = *w_ws.PHI; iter.valid(); ++iter) { Statement &s = iter.current(); Expression &rhs = s.rhs(); Expression *rhs_new; if (w_ws.path_star && w_ws.path_star->expr){ rhs_new = w_ws.path_star->expr->clone(); } else { rhs_new = w_ws.path_idom->expr->clone(); } int i = 0; for (Iterator<Expression> subs(rhs.parameters_guarded().arg_list()); subs.valid(); ++subs, ++i) { if (occurs(*rhs_new,i)) rhs_new = substitute_argument(rhs_new, i, subs.current()); else rhs_new = substitute_argument(rhs_new, -1, subs.current()); } s.rhs(rhs_new); } if (w_ws.path_idom) delete w_ws.path_idom; if (w_ws.path_label) delete w_ws.path_label; if (w_ws.path_star) delete w_ws.path_star; w_ws.path_idom = w_ws.path_star = w_ws.path_label = NULL; } } } for (int i = 0; i<vertex.entries(); ++i) { Statement & w = *vertex[i]; GSAWorkSpace & w_ws = *(GSAWorkSpace *) w.work_stack().top_ref(pass); if (w_ws.PHI->entries()) { // Fix the Idom and Dominance Frontier for the list of the Phi // assignments Statement *idom = &w; for (Iterator<Statement>iter = *w_ws.PHI; iter.valid(); ++iter) { Statement & u = iter.current(); GSAWorkSpace * u_ws = new GSAWorkSpace(pass); u_ws->DF = w_ws.DF; u_ws->idom = idom; idom = &u; u.work_stack().push(u_ws); } /// ... Fix the idom for the children of w in the dominator tree for (Iterator<Statement>iter1 = w_ws.bucket; iter1.valid(); ++iter1) { Statement & v = iter1.current(); GSAWorkSpace & v_ws = *(GSAWorkSpace *) v.work_stack().top_ref(pass); v_ws.idom = idom; } /// ... Now, the ins_after will do the hard work to fix the control /// ... flow graph if (w.stmt_class() == FLOW_EXIT_STMT && w_ws.PHI->entries()) { /// ... Some redundant PHI assignments could be created at the /// ... FLOW EXIT statement because all the RETURN statements /// ... artificially have the FLOW EXIT statement as their successor. /// ... The PHI assignments will never be executed since the subroutine /// ... already returned. They may still be useful for interprocedural /// ... analysis as a summary for the subroutine. That requires us to /// ... change all the RETURN statements to GOTO statements to the /// ... FLOW EXIT and the FLOW EXIT to its sole RETURN. /// ... For now, we just ignore the PHI assignments. /// ... for (Iterator<Statement> iter = *w_ws.PHI; iter.valid(); --iter) /// ... pgm.stmts().ins_before(iter.grab(), &w); delete w_ws.PHI; w_ws.PHI = NULL; } else { pgm.stmts().ins_after(w_ws.PHI, &w); w_ws.PHI = NULL; /// ... Iterator<Statement> iter = w_ws.PHI; /// ... for (iter.set_to_last(); iter.valid(); --iter) /// ... pgm.stmts().ins_after(iter.grab(), &w); } } } } static unsigned int build_pidom(ProgramUnit & pgm) { unsigned int pass = create_pass_tag(); Array<Statement *> vertex(pgm.stmts().entries()); /// ... build post-dominator tree using Tarjan's algorithm pDominator(pgm, vertex, new pDominatorWorkSpace(pass), (switch_value("gsa_prt_pdom") == 1)); return pass; } static void get_all_variable_clone(Expression & expr, RefList<Symbol>*l) { if (expr.op() == ID_OP) l->ins_last(*expr.base_variable_ref()); else if (expr.op() == ARRAY_REF_OP) { l->ins_last(*expr.base_variable_ref()); get_all_variable_clone(expr.subscript(), l); } else if (expr.op() == SUBSTRING_OP){ l->ins_last(*expr.base_variable_ref()); get_all_variable_clone(expr.bound(), l); } else if (expr.op() == FUNCTION_CALL_OP) get_all_variable_clone(expr.parameters_guarded(), l); else for (Iterator<Expression>iter = expr.arg_list(); iter.valid(); ++iter) get_all_variable_clone(iter.current(), l); } void DeGSA(ProgramUnit & pgm) { if (pgm.pu_class() == BLOCK_DATA_PU_TYPE) return; p_assert(pgm.gsa_valid(), "DeGSA called for a non-GSA ProgramUnit"); pgm.gsa_names_guarded().translate_GSA_symbol_refs(); pgm.gsa_names(0); pgm.gsa_deflocs(0); } /// COMPRESS_PATH, EVAL_PATH and LINK_PATH for building path expr. static void COMPRESS_PATH(Statement & v, Statement &tail, unsigned int pass) { GSAWorkSpace & v_ws = *(GSAWorkSpace *) v.work_stack().top_ref(pass); GSAWorkSpace & anc_v_ws = *(GSAWorkSpace *) v_ws.ancestor->work_stack().top_ref(pass); if (anc_v_ws.ancestor) { COMPRESS_PATH(*v_ws.ancestor, tail, pass); /// ... Link the path expression from the root down. GSAWorkSpace & anc_anc_v_ws = *(GSAWorkSpace *) anc_v_ws.ancestor->work_stack().top_ref(pass); if (anc_anc_v_ws.path_label) *anc_v_ws.path_label /= *anc_anc_v_ws.path_label; v_ws.ancestor = anc_v_ws.ancestor; } else anc_v_ws.tails.ins_last(tail); /// ... Link the path expression from its ancestor. if (anc_v_ws.path_label) *v_ws.path_label /= *anc_v_ws.path_label; } static GSAPathExpr * EVAL_PATH(Statement &v, Statement & tail, unsigned int pass) { GSAWorkSpace &v_ws = *(GSAWorkSpace *) v.work_stack().top_ref(pass); if (!v_ws.ancestor){ v_ws.tails.ins_last(tail); return NULL; } COMPRESS_PATH(v, tail, pass); return v_ws.path_label->clone(); } static void LINK_PATH(Statement * v, Statement & w, unsigned int pass, unsigned int pidom_pass) { GSAWorkSpace & w_ws = *(GSAWorkSpace *) w.work_stack().top_ref(pass); w_ws.ancestor = v; pDominatorWorkSpace & v_ws = *(pDominatorWorkSpace *) v->work_stack().find_ref(pidom_pass); if (v_ws.idom == &w) w_ws.path_label = new GSAPathExpr(*v,w); else w_ws.path_label = w_ws.path_idom->clone(); } /// This algorithm is a modification of Tarjan's fast algorithms in /// "Fast Algorithms for Solving Path Problems", Journal of ACM, Vol 28, /// No. 3, July 1981, 594-614. /// Let idom(v) = u. The algorithm finds all the paths from u to v /// containing only proper descendants of u as intermediate vertices. /// We use it to construct the gating functions. static void gating(ProgramUnit & NOTUSED(pgm), Array<Statement *> & vertex, unsigned int pass, unsigned int pidom_pass) { for (int i = vertex.entries() - 1; i >= 0; --i) { Statement & u = *vertex[i]; GSAWorkSpace & u_ws = *(GSAWorkSpace *) u.work_stack().top_ref(pass); /// ... u is a branch st. RefList<Statement> top_sorted; { for (Iterator<Statement> children = u_ws.bucket; children.valid(); ++children) { Statement & v = children.current(); GSAWorkSpace & v_ws = *(GSAWorkSpace *) v.work_stack().top_ref(pass); /// ... Compute every path starting from a sibling s of v containing only /// ... the proper descendants of s. for (Iterator<Statement> edges = v.pred(); edges.valid(); ++edges) { Statement &e = edges.current(); /* Exclude edges originating from an unreachable node by checking if it is in the dominator tree (extending the original check, which only handled one Polaris-generated case of this: an IMPLIED_GOTO_STMT with no predecessors) */ if (!e.work_stack().top_ref(pass)) continue; if (&e != &u) { GSAPathExpr *P = EVAL_PATH(e,v,pass); if (P==NULL) { int b = e.succ()._member(v); p_assert(b >= 0, "v is not a successor of e"); v_ws.path.ins_last(new GSAPathExpr(e,v,b)); ++v_ws.number_of_predecessors; } else if (P->head == &v) { /// ... a loop with v as its entrance int b = e.succ()._member(v); p_assert(b >= 0, "v is not a successor of e"); *P *= GSAPathExpr(e,v,b); if (v_ws.path_star) { *v_ws.path_star |= *P; delete P; } else { v_ws.path_star = P; } } else { /// ... an ordinary path from a sibling int b = e.succ()._member(v); p_assert(b >= 0, "v is not a successor of e"); *P *= GSAPathExpr(e,v,b); v_ws.path.ins_last(P); ++v_ws.number_of_predecessors; } } else { /// ... Compute the path from u to v int b = u.succ()._member(v); p_assert(b >= 0, "v is not a successor of u"); if (v_ws.path_idom) v_ws.path_idom->add_edge(u,v,b); else v_ws.path_idom = new GSAPathExpr(u,v,b); } } if (v_ws.number_of_predecessors == 0) top_sorted.ins_last(v); } } { int done = 0; Iterator<Statement> siblings = top_sorted; do { for ( ; siblings.valid(); ++siblings) { Statement & v = siblings.current(); GSAWorkSpace & v_ws = *(GSAWorkSpace *) v.work_stack().top_ref(pass); if (v_ws.path.entries()) for (Iterator<GSAPathExpr> iter=v_ws.path; iter.valid(); ++iter) { GSAPathExpr &path = iter.current(); Statement * w = path.head; GSAWorkSpace & w_ws = *(GSAWorkSpace *) w->work_stack().top_ref(pass); if (w_ws.path_idom) { path /= *w_ws.path_idom; /// ... UPDATE(v): set the v_ws.pathall be all the paths from u to v /// ... containing only the proper descendants of u if (v_ws.path_idom) *v_ws.path_idom |= path; else v_ws.path_idom = path.clone(); } } #if 0 if (v.pred().entries()>1) v_ws.path_idom->fill_expr() if (v_ws.path_star) { if (v.stmt_class()==DO_STMT) v_ws.path_star->fill_expr(v_ws.path_idom->expr); else v_ws.path_star->fill_expr(v_ws.path_idom->expr); v_ws.path_idom->expr = NULL; } #endif LINK_PATH(&u,v,pass,pidom_pass); for (Iterator<Statement> iter1 = v_ws.tails; iter1.valid(); ++iter1) { Statement &v1 = iter1.current(); /// ... if it is not a self cycle if (&v1 != &v){ GSAWorkSpace & t_ws = *(GSAWorkSpace *) v1.work_stack().top_ref(pass); --t_ws.number_of_predecessors; if (t_ws.number_of_predecessors==0) top_sorted.ins_last(v1); } } } if (top_sorted.entries() != u_ws.bucket.entries()) { cout << "Irreducible flow graph encounted!" << endl; for (Iterator<Statement> iter = u_ws.bucket; iter.valid(); ++iter) { Statement &v1 = iter.current(); if (!top_sorted.member(v1)) { top_sorted.ins_last(v1); GSAWorkSpace & t_ws = *(GSAWorkSpace *) v1.work_stack().top_ref(pass); t_ws.number_of_predecessors = 0; siblings.set_to_last(); break; } } } else done = 1; } while (!done); } } } /// MakeDefMap must be externally visible because it is a friend of /// DefLoc and DefLocMap... it should NOT be called from other source files DefLocMap * MakeDefMap(ProgramUnit & pgm) { DefLocMap *V = new DefLocMap; for (DictionaryIter<Symbol> sym = pgm.symtab().iterator(); sym.valid(); ++sym) { /// cout << sym.current() << endl; if (sym.current().sym_class() == VARIABLE_CLASS || sym.current().sym_class() == FUNCTION_CLASS || sym.current().sym_class() == SYMBOLIC_CONSTANT_CLASS) { // The following is a PRIVATE member access V->_map.ins(sym.current(),new DefLoc()); } } for (Iterator<Statement> iter = pgm.stmts().iterator(); iter.valid(); ++iter) { Statement & s = iter.current(); if (s.stmt_class() == ASSIGNMENT_STMT || s.stmt_class() == DO_STMT || s.stmt_class() == CALL_STMT || s.stmt_class() == READ_STMT || s.stmt_class() == WRITE_STMT) { for (Iterator<Expression> def_iter = s.out_refs(); def_iter.valid(); ++def_iter) { Expression & def = def_iter.current(); DefLoc *v = V->find_ref(*def.base_variable_ref()); if (v == 0) { cerr << "warning: DefDict: base variable not found" << def << endl; } /// ... The following is a PRIVATE member access else if (!v->_st.valid()) { /// ... The following is a PRIVATE member access v->_st = s; } else if (s.stmt_class() == ASSIGNMENT_STMT && s.lhs().base_variable_ref() == def.base_variable_ref()) { /// ... The following is a PRIVATE member access Statement &t = *v->_st; if (!(t.stmt_class() == ASSIGNMENT_STMT && t.lhs().base_variable_ref() == def.base_variable_ref())) { /// ... The following is a PRIVATE member access v->_st = s; } else { cout << def << "\n"; /// ... The following is a PRIVATE member access cout << *v->_st << "\n" << s << "\n"; p_abort("More than one definition for a GSA variable"); } } } } } return V; } void MakeGSA(ProgramUnit & pgm) { if (pgm.pu_class() == BLOCK_DATA_PU_TYPE) return; p_assert(!pgm.gsa_valid(), "MakeGSA called for a GSA ProgramUnit"); pgm.gsa_names(new TranslateObject(pgm)); TranslateObject & trans_obj = pgm.gsa_names_guarded(); /// ... The following function is used to avoid irreduciable flow graph remove_assigned_goto_stmts(pgm); /// ... Find the post dominator unsigned int pidom_pass = build_pidom(pgm); Timer time; Map<Symbol,IntElem> candidates; Array<Symbol *> tag_to_candidate; int tag = 0; int gsa_debug = switch_value("gsa_debug"); Dictionary<PhiPlaceDef> *V = Variable_set_new(pgm,candidates,tag_to_candidate,tag); unsigned int pass = create_pass_tag(); Array<Statement *> vertex(pgm.stmts().entries()); Dominator_S(pgm, vertex, pass, V, candidates, tag_to_candidate, tag); if (gsa_debug) cerr << "Time for placement: " << time << endl; time.reset(); /// ... Declare BETA pseudo function (others are now integrated in base) Symbol *beta = new FunctionSymbol("<BETA>", UNKNOWN_TYPE, NOT_EXTERNAL, NOT_INTRINSIC, NOT_FORMAL); pgm.symtab().ins(beta); trans_obj.GSA_mapping(*beta); gating(pgm, vertex, pass, pidom_pass); if (gsa_debug) cerr << "Time for gating: " << time << endl; /// ... Insert pseudo assignment statements into the program time.reset(); insert_pseudo_assignment_stmts(pgm, vertex, tag_to_candidate, pass); InitializeGSAStack(trans_obj, V); if (gsa_debug) cerr << "Time for GSA stack: " << time << endl; time.reset(); SEARCH(trans_obj, *pgm.stmts().first_ref(), *V, pass, beta); if (gsa_debug) cerr << "Time for renaming: " << time << endl; time.reset(); delete V; if (gsa_debug) cerr << "Time for deleting GSA stack: " << time << endl; time.reset(); InsertPhiStmt(pgm, vertex, pass, 1); if (gsa_debug) cerr << "Time for inserting PHIs: " << time << endl; pgm.clean_workspace(pass); pgm.clean_workspace(pidom_pass); pgm.gsa_deflocs(MakeDefMap(pgm)); } void MakeGSA_test(TranslateObject & trans_obj) { ProgramUnit & pgm = trans_obj.pgm_main(); if (pgm.pu_class() == BLOCK_DATA_PU_TYPE) return; /// ... The following function is used to avoid irreduciable flow graph remove_assigned_goto_stmts(pgm); /// ... Find the post dominator unsigned int pidom_pass = build_pidom(pgm); Map<Symbol,IntElem> candidates; Array<Symbol *> tag_to_candidate; int tag = 0; Dictionary<PhiPlaceDef> *V = Variable_set_new(pgm,candidates,tag_to_candidate,tag); unsigned int pass = create_pass_tag(); Array<Statement *> vertex(pgm.stmts().entries()); Dominator_S(pgm, vertex, pass, V, candidates, tag_to_candidate, tag); /// ... Declare BETA pseudo function (all others integrated into base) Symbol *beta = new FunctionSymbol("<BETA>", UNKNOWN_TYPE, NOT_EXTERNAL, NOT_INTRINSIC, NOT_FORMAL); pgm.symtab().ins(beta); trans_obj.GSA_mapping(*beta); /// gating(pgm, vertex, pass, pidom_pass); /// ... Insert pseudo assignment statements into the program insert_pseudo_assignment_stmts(pgm, vertex, tag_to_candidate, pass); InitializeGSAStack(trans_obj, V); SEARCH(trans_obj, *pgm.stmts().first_ref(), *V, pass, beta); delete V; InsertPhiStmt(pgm, vertex, pass, 0); pgm.clean_workspace(pass); pgm.clean_workspace(pidom_pass); } Expression * trans_update_expr(InlineObject * tobj, Expression * expr) { Expression * return_expr = expr; extern Boolean is_leaf(const Expression & expr); if (is_leaf(*expr)) { Symbol * oldsym = expr->base_variable_ref(); if (oldsym == 0) return expr; Expression * xlate = tobj->translate_GSA_refs_expr(expr); Symbol * xlatesym = xlate->base_variable_ref(); if (oldsym == xlatesym) { if (oldsym->sym_class() != VARIABLE_CLASS) { return_expr = xlate; } else { Symbol & newsym = trans_update_symbol(tobj, *(VariableSymbol *) oldsym); xlate->symbol(newsym); return_expr = xlate; } } else { return_expr = xlate; } } 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); tobj->remap_expr(&epull, lambda, IN_REF_EXPR); eas = epull; } return_expr = expr; } return return_expr; } Symbol & trans_update_symbol( TranslateObject * tobj, VariableSymbol & sym) { VariableSymbol * trans_sym = (VariableSymbol *)(&sym); if (trans_sym->is_gsa_symbol()) { trans_sym = (VariableSymbol *) (&(trans_sym->gsa_base_symbol())); } Symbol * symclone = trans_sym->clone(); Symbol & newsym = tobj->pgm_main().symtab().rename_and_ins(symclone); tobj->GSA_mapping(sym, newsym); return newsym; } /* * Guobin: Make a new gsa variable whose index is C */ VariableSymbol* make_gsa_var(ProgramUnit& pgm, VariableSymbol& old_var, int C) { TranslateObject & trans_obj = pgm.gsa_names_guarded(); int i = C; String var_i(old_var.name_ref()); var_i += "@"; var_i += integer_to_string(i); VariableSymbol* _t = new VariableSymbol(var_i, old_var.type(), old_var.formal(), old_var.saved() ); _t->dim() = old_var.dim(); _t->shared_dim() = old_var.shared_dim(); VariableSymbol & new_var = (VariableSymbol &)pgm.symtab().ins(_t); new_var.gsa_base_symbol( old_var ); trans_obj.GSA_mapping(*_t,old_var); return &new_var; } VariableSymbol* get_gsa_var(ProgramUnit& pgm, VariableSymbol& base_var, int C) { Symtab& st=pgm.symtab(); String var_c(base_var.name_ref()); var_c+="@"; var_c+=integer_to_string(C); Symbol* _new_sym=st.find_ref(var_c); return (VariableSymbol*)_new_sym; }

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