Polaris: InterProcConstProp.cc Source File

InterProcConstProp.cc Go to the documentation of this file. /// /// /// \file InterProcConstProp.cc /// #include "../Collection/KeyIterator.h" #include "../Collection/Mutator.h" #include "../Directive/Assertion.h" #include "../Symbol/Symbol.h" #include "../Symbol/VariableSymbol.h" #include "../Statement/Statement.h" #include "../Statement/AssignmentStmt.h" #include "../Statement/LabelStmt.h" #include "../Program.h" #include "../ProgramUnit.h" #include "../ProgramTag.h" #include "../EntryPoints.h" #include "../Symtab.h" #include "../Timer.h" #include "../utilities/expression_util.h" #include "../utilities/entry_util.h" #include "../utilities/program_util.h" #include "../utilities/stmt_util.h" #include "../utilities/loopMark.h" #include "InterProcConstProp.h" /// Template instantiations: template class TypedBaseMap<String, IPCPProcData>; template class ProtoDatabase<String, IPCPProcData>; template class Database<String, IPCPProcData>; template ostream & operator << (ostream &, const Database<String, IPCPProcData> &); template class KeyIterator<String, IPCPProcData>; template class Array<IPCPProcData *>; /// normalize_func_calls /// Normalize the structure of function calls so that they only occur /// in assignment statements at the top level. /// /// WARNING: This function assumes that all arguments in an expression /// and all expressions in a statement are executed left to right. static Expression * _norm_func_calls1(Expression *expr, Statement &stmt, ProgramUnit &pgm) { if (! expr) return expr; /// ... Don't normalize function calls inside implied DO statements. if (expr->op() == DO_OP) return expr; Mutator<Expression> arg_iter = expr->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) { Assign<Expression> eas(arg_iter.assign()); eas = _norm_func_calls1(arg_iter.pull(), stmt, pgm); } if (expr->op() == FUNCTION_CALL_OP) { Symbol *func_call_var = new VariableSymbol("tfc", expr->function().symbol().type(), NOT_FORMAL, NOT_SAVED); func_call_var = &pgm.symtab().rename_and_ins(func_call_var); Statement *func_call_stmt = new AssignmentStmt(pgm.stmts().new_tag(), id(*func_call_var), expr); Iterator<Assertion> as_iter = assertions_of_type(stmt, AS_SIDE_EFFECT_FREE); for ( ; as_iter.valid(); ++as_iter) { Assertion *assert = as_iter.current().clone(); func_call_stmt->assertions().ins_last(assert); } pgm.stmts().ins_before(func_call_stmt, &stmt); expr = id(*func_call_var); } return expr; } static void _normalize_func_calls(ProgramUnit &pgm) { Iterator<Statement> stmt_iter = pgm.stmts().iterator(); for ( ; stmt_iter.valid(); ++stmt_iter) { Statement &stmt = stmt_iter.current(); if (stmt.stmt_class() == CALL_STMT) { // Now, check the arguments passed to the CALL. If any are // integer constants, assign the constants to variables and // use the variables instead. This was done to prevent the // problem where a constant is passed and IPVP places an // assignment statement inside the routine, assigning the // constant to the formal parameter (which breaks in some // backend compilers). // e.g. CALL X(1) .... SUBROUTINE X(N) ; N = 1 ; ..... - jph for(Mutator<Expression> iter = stmt.parameters_guarded().arg_list(); iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); Expression * arg = iter.pull(); if (arg->op() == INTEGER_CONSTANT_OP) { Symbol *arg_var = new VariableSymbol("arg", INTEGER_TYPE, NOT_FORMAL, NOT_SAVED); arg_var = &pgm.symtab().rename_and_ins(arg_var); Statement *arg_stmt = new AssignmentStmt(pgm.stmts().new_tag(), id(*arg_var), arg->clone()); pgm.stmts().ins_before(arg_stmt, &stmt); delete arg; arg = id(*arg_var); } eas = arg; } } if (contains_func_call(stmt)) { if (stmt.stmt_class() == WHILE_STMT){ cerr<<stmt; } p_assert(stmt.pred().entries() <= 1 || stmt.stmt_class() == DO_STMT, "_normalize_func_calls() doesn't know how to move function calls out of statements with multiple predecessors."); Mutator<Expression> arg_iter = stmt.iterate_expressions(); Statement *prevstmt = stmt.prev_ref(); for ( ; arg_iter.valid(); ++arg_iter) { Assign<Expression> eas(arg_iter.assign()); eas = _norm_func_calls1(arg_iter.pull(), stmt, pgm); } /// ... Now, check the arguments passed to the function call. /// ... If any are integer constants, assign the constants to /// ... variables and use the variables instead. This was done /// ... to prevent the problem where a constant is passed and /// ... IPVP places an assignment statement inside the routine, /// ... assigning the constant to the formal parameter (which /// ... breaks in some backend compilers). /// ... e.g. A= X(1) .... FUNCTION X(N) ; N = 1 ; ..... - jph p_assert((stmt.prev_ref()->stmt_class() == ASSIGNMENT_STMT) && (stmt.prev_ref()->rhs().op() == FUNCTION_CALL_OP), "Prev stmt should be an assignment with an RHS of a function call"); for(Mutator<Expression> iter = stmt.prev_ref()->rhs().parameters_guarded().arg_list(); iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); Expression * arg = iter.pull(); if (arg->op() == INTEGER_CONSTANT_OP) { Symbol *arg_var = new VariableSymbol("arg", INTEGER_TYPE, NOT_FORMAL, NOT_SAVED); arg_var = &pgm.symtab().rename_and_ins(arg_var); Statement *arg_stmt = new AssignmentStmt(pgm.stmts().new_tag(), id(*arg_var), arg->clone()); pgm.stmts().ins_after(arg_stmt, prevstmt); delete arg; arg = id(*arg_var); } eas = arg; } stmt.build_refs(); } } } /// add_call_returns /// Add dummy statements, (represented by label statements), after each /// subroutine or function call. These statements are used by the /// constant propagator to hold any new constants generated by these /// calls. static void _add_call_returns(ProgramUnit &pgm) { Iterator<Statement> stmt_iter = pgm.stmts().iterator(); for ( ; stmt_iter.valid(); ++stmt_iter) { Statement &stmt = stmt_iter.current(); if (stmt.stmt_class() == CALL_STMT || contains_func_call(stmt)) pgm.stmts().ins_after(new LabelStmt(pgm.stmts().new_tag(), pgm.stmts().new_label()), &stmt); } } /// read_dummy_pgms /// Read in the program units from DUMMY_PGM_FILE and create IPCPProcData /// objects for them. void InterProcConstProp::_read_dummy_pgms(char *intrin_file_name) { _dummy_pgms = new Program; if (intrin_file_name == 0) { _dummy_pgms->read(DUMMY_PGM_FILE); } else { _dummy_pgms->read(intrin_file_name); } KeyIterator<String,ProgramUnit> pgm_iter = *_dummy_pgms; for ( ; pgm_iter.valid(); ++pgm_iter) { ProgramUnit &pgm = pgm_iter.current_data(); if (! _pgm_entries->member(pgm.routine_name_ref())) { _normalize_func_calls(pgm); _add_call_returns(pgm); Iterator<Statement> entry_iter = pgm.stmts().stmts_of_type(ENTRY_STMT); p_assert(entry_iter.valid(), "Given program unit does not have an entry statement."); const Statement &entry = entry_iter.current(); ++entry_iter; p_assert(! entry_iter.valid(), "InterProcConstProp cannot handle program units with multiple entries."); IPCPProcData *data = new IPCPProcData(pgm, *this, entry, _debug_level); _pgm_data.ins(pgm.routine_name_ref(), data); } } } /// compute_toporder /// Compute a topological ordering, in respect to the call graph, for /// all my program units with IPCPProcData objects. void InterProcConstProp::_compute_toporder() { KeyIterator<String, IPCPProcData> iter = _pgm_data; for ( ; iter.valid(); ++iter) iter.current_data().init_rtoporder(); int num_proc_datas = 0; for (iter.reset(); iter.valid(); ++iter) iter.current_data().compute_rtoporder(num_proc_datas); _pgm_data_toporder.resize(num_proc_datas); p_assert(num_proc_datas == _pgm_data.entries(), "Internal error in InterProcConstProp::_compute_toporder()."); for (int i = 0; i < num_proc_datas; ++i) _pgm_data_toporder[i] = 0; for (iter.reset(); iter.valid(); ++iter) { IPCPProcData &data = iter.current_data(); if (data.rtoporder() >= 0) _pgm_data_toporder[num_proc_datas - data.rtoporder() - 1] = &data; } } /// compute_constants /// Compute the sets of entering symbolic constants for all /// procedures in the program. void InterProcConstProp::_compute_constants() { Timer timer; /// ... Move the current constants sets as old constants sets fields. KeyIterator<String, IPCPProcData> iter = _pgm_data; for ( ; iter.valid(); ++iter) iter.current_data().make_consts_sets_old(); /// ... Compute the new constants sets. for (int i = 0; i < _pgm_data_toporder.entries(); ++i) { IPCPProcData &data = *_pgm_data_toporder[i]; if (data.is_called_externally()) { IPCPConstants *no_constants = new IPCPConstants(); List<Expression> non_const_params; for (int j = 0; j < data.param_list().entries(); ++j) non_const_params.ins_last(omega()); data.add_constant_set(no_constants, non_const_params); } } if (_debug_level > 0) cout << "! Computing interprocedural constants: " << timer << endl; } /// have_constants_changed /// Return True if the constants have changed for any constant set. Boolean InterProcConstProp::_have_constants_changed() const { KeyIterator<String, IPCPProcData> iter = _pgm_data; for ( ; iter.valid(); ++iter) if (iter.current_data().have_consts_sets_changed()) { if (_debug_level > 0) cout << "! Constants for routine " << iter.current_key() << " have changed.\n"; return True; } return False; } /// Constructor InterProcConstProp::InterProcConstProp(Program &pgms, PC_REAL_BOOL subst_reals, PC_ARRAY_BOOL subst_arrays, char *intrin_file_name, int debug GIV(0)) { _pgms = &pgms; _dummy_pgms = 0; _subst_reals = subst_reals; _subst_arrays = subst_arrays; _debug_level = debug; Timer timer; /// ... Normalize all the programs in pgms and determine the main program. ProgramUnit *main_pgm = 0; Program *entry_pgms = new Program; KeyIterator<String,ProgramUnit> pgm_iter = pgms; for ( ; pgm_iter.valid(); ++pgm_iter) { ProgramUnit &pgm = pgm_iter.current_data(); if (pgm.pu_class() == PROGRAM_PU_TYPE) { main_pgm = &pgm; p_assert(main_pgm->routine_name_ref(), "InterProcConstProp constructor requires that the main program unit have a name."); } move_saved_vars(pgm, *entry_pgms); _normalize_func_calls(pgm); _add_call_returns(pgm); substitute_parameters(pgm, _subst_reals); split_multiple_entries(pgm, *entry_pgms); } pgms.absorb(entry_pgms); _pgm_entries = pgms.entry_points(); /// ... Read in the set of dummy programs. _read_dummy_pgms(intrin_file_name); /// ... Build a IPCPProcData object for each program in pgms. for (pgm_iter.reset(); pgm_iter.valid(); ++pgm_iter) { ProgramUnit &pgm = pgm_iter.current_data(); if (pgm.pu_class() != BLOCK_DATA_PU_TYPE) (void) _get_proc_data_ref(pgm.routine_name_ref()); } /// ... Compute the topological order of the call graph of these programs. _compute_toporder(); /// ... If a main program unit is in the set of programs, mark it as the /// ... only externally called program. Otherwise, mark all program /// ... units as externally called. if (main_pgm) _get_proc_data_ref(main_pgm->routine_name_ref())->called_externally(); else pgms_can_be_called_externally(); if (debug > 0) { cout << "! Initializing data structures: " << timer << endl; timer.reset(); } /// ... Compute the side-effects of all procedures in the program. _build_jump_functions(); /// ... Compute the sets of entering symbolic constants for all /// ... procedures in the program. _compute_constants(); } /// Destructor InterProcConstProp::~InterProcConstProp() { delete _pgm_entries;; if (_dummy_pgms) delete _dummy_pgms; } /// pgms_can_be_called_externally void InterProcConstProp::pgms_can_be_called_externally() { for (int i = 0; i < _pgm_data_toporder.entries(); ++i) { IPCPProcData &data = *_pgm_data_toporder[i]; if (! _dummy_pgms || ! _dummy_pgms->member(data.pgm().tag_ref())) data.called_externally(); } } /// pgm_entry /// Return the entry statement for the given program unit. static Statement & _pgm_entry(ProgramUnit &pgm) { Iterator<Statement> entry_iter = pgm.stmts().stmts_of_type(ENTRY_STMT); p_assert(entry_iter.valid(), "Given program unit does not have an entry statement."); Statement &entry = entry_iter.current(); ++entry_iter; p_assert(! entry_iter.valid(), "Given program unit has multiple entries."); return entry; } /// get_proc_data_ref /// Get the IPCPProcData object associated with the program unit with /// the given name. If the object does not exist, it is created. /// If the program unit does not exist, the routine returns NULL. IPCPProcData * InterProcConstProp::_get_proc_data_ref(const char *proc_name) { IPCPProcData *data = _pgm_data.find_ref(proc_name); if (! data) { ProgramUnit *pgm_ref = _pgm_entries->find_ref(proc_name); if (pgm_ref) { data = new IPCPProcData(*pgm_ref, *this, _pgm_entry(*pgm_ref), _debug_level); _pgm_data.ins(proc_name, data); } } if (! data) { cerr << "WARNING: InterProcConstProp constructor could not find program unit\n" << " named " << proc_name << ".\n"; cerr << " Will assume program unit modifies all non-local variables.\n"; } return data; } /// _rename_pgm_entry /// Rename the entry statement for the given program unit. /// This is a little more complicated than it sounds, since we must /// make sure that this renamed variable does not conflict with any /// other variables in the program. void InterProcConstProp::_rename_pgm_entry(ProgramUnit &pgm) const { Statement &entry_stmt = _pgm_entry(pgm); Symbol &entry_var = entry_stmt.routine_guarded().symbol(); String old_entry_name = entry_var.name_ref(); String new_entry_name = old_entry_name; entry_var.renaming_suggestion(new_entry_name); Boolean is_name_unique = False; while (! is_name_unique) { is_name_unique = True; KeyIterator<String,IPCPProcData> iter = _pgm_data; for ( ; iter.valid(); ++iter) { const ProgramUnit &some_pgm = iter.current_data().pgm(); while (some_pgm.symtab().find_ref(new_entry_name)) { entry_var.renaming_suggestion(new_entry_name); is_name_unique = False; } } } /// ... Force the symbol table to update the entry variable to its new name. pgm.symtab().grab(entry_var.name_ref()); entry_var.name(new_entry_name); pgm.symtab().ins(&entry_var); reset_loop_labels(pgm, old_entry_name, new_entry_name); } /// build_jump_functions /// Build the jump functions for each program unit. void InterProcConstProp::_build_jump_functions() { Timer timer; for (int i = _pgm_data_toporder.entries() - 1; i >= 0; --i) { _pgm_data_toporder[i]->build_jump_functions(_debug_level); if (_debug_level > 1) { cout << "! IPCPProcData = "; _pgm_data_toporder[i]->print(cout, True); cout << endl << endl; } } if (_debug_level > 0) cout << "! Computing jump functions: " << timer << endl; } /// clone_all_pgms /// Clone each program unit with multiple constant sets. void InterProcConstProp::_clone_all_pgms() { Timer timer; /// ... silvius: let's see the const sets before cloning: /// cerr<<"\n\n\nCONSTANT SETS: "; /// print_consts_sets(cerr); for (int i = 0; i < _pgm_data_toporder.entries(); ++i) { IPCPProcData &data = *_pgm_data_toporder[i]; if ((! _dummy_pgms || ! _dummy_pgms->member(data.pgm().tag_ref())) && data.const_sets().entries() > 1) { Iterator<IPCPConstants> consts_iter = data.const_sets(); ++consts_iter; /// ... Let the original pgm keep the first const set for ( ; consts_iter.valid(); ++consts_iter) { if (_debug_level > 0) cout << "! Cloning program unit: " << data.pgm().routine_name_ref() << endl; ProgramUnit *pgm_clone = new ProgramUnit(data.pgm()); _rename_pgm_entry(*pgm_clone); ProgramTag clone_tag; pgm_clone->rename(clone_tag); _pgms->absorb(pgm_clone); IPCPProcData *cloned_data = new IPCPProcData(*pgm_clone, _pgm_entry(*pgm_clone), data); cloned_data->transfer_const_set(consts_iter.current(), data); _pgm_data.ins(pgm_clone->routine_name_ref(), cloned_data); } } } _compute_toporder(); if (_debug_level > 0) cout << "! Cloning program units: " << timer << endl; } /// propagate_constants /// Annotate each program unit with its constant values. This method /// assumes that each program unit has at most one constant set. void InterProcConstProp::_propagate_constants(PC_UNREACH_BOOL remove_unreachable) { Timer timer; KeyIterator<String, IPCPProcData> iter = _pgm_data; for ( ; iter.valid(); ++iter) { IPCPProcData &data = iter.current_data(); if (! _dummy_pgms || ! _dummy_pgms->member(data.pgm().tag_ref())) { data.add_consts_to_pgm(); data.propagate_constants(remove_unreachable); } } if (_debug_level > 0) cout << "! Propagating interprocedural constants: " << timer << endl; } /// add_maymods /// Add maymod assertions to every call site in the program. void InterProcConstProp::_add_maymods() { Timer timer; KeyIterator<String, IPCPProcData> iter = _pgm_data; for ( ; iter.valid(); ++iter) { IPCPProcData &data = iter.current_data(); if (! _dummy_pgms || ! _dummy_pgms->member(data.pgm().tag_ref())) data.add_maymods(); } if (_debug_level > 0) cout << "! Adding MAYMOD assertions: " << timer << endl; } /// clone_and_propagate void InterProcConstProp::clone_and_propagate(PC_UNREACH_BOOL remove_unreachable) { _clone_all_pgms(); _propagate_constants(remove_unreachable); _add_maymods(); } /// double_clone_and_propagate void InterProcConstProp::double_clone_and_propagate(PC_UNREACH_BOOL remove_unreachable) { _clone_all_pgms(); _build_jump_functions(); _compute_constants(); _clone_all_pgms(); _propagate_constants(remove_unreachable); _add_maymods(); } /// iter_clone_and_propagate void InterProcConstProp::iter_clone_and_propagate(PC_UNREACH_BOOL remove_unreachable) { if (_debug_level > 0) print_consts_sets(cout); do { _clone_all_pgms(); _build_jump_functions(); _compute_constants(); if (_debug_level > 0) print_consts_sets(cout); } while (_have_constants_changed()); _clone_all_pgms(); _propagate_constants(remove_unreachable); _add_maymods(); } /// expand_all_substituted void InterProcConstProp::expand_all_substituted() { KeyIterator<String, IPCPProcData> iter = _pgm_data; for ( ; iter.valid(); ++iter) { IPCPProcData &data = iter.current_data(); if (! _dummy_pgms || ! _dummy_pgms->member(data.pgm().tag_ref())) data.expand_all_substituted(); } } /// substitutable_type /// Returns true if the given type may be legally substituted Boolean InterProcConstProp::_is_substitutable(const Symbol &var) const { if (_subst_arrays == IGNORE_ARRAYS && var.is_array()) return False; EXPR_TYPE type = var.type().data_type(); if (type == INTEGER_TYPE || type == LOGICAL_TYPE || (_subst_reals == SUBST_REALS && (type == REAL_TYPE || type == DOUBLE_PRECISION_TYPE || type == COMPLEX_TYPE))) return True; return False; } /// print void InterProcConstProp::print(ostream &o) const { o << "["; o << "_pgm_data=" << &_pgm_data; o << ", _global_vars=" << _global_vars; o << "]"; } /// print_consts_sets void InterProcConstProp::print_consts_sets(ostream &o) const { KeyIterator<String,IPCPProcData> iter = _pgm_data; for ( ; iter.valid(); ++iter) { o << iter.current_key() << ": {"; Iterator<IPCPConstants> const_iter = iter.current_data().const_sets(); if (const_iter.valid()) { const_iter.current().print_constants(o); ++const_iter; for ( ; const_iter.valid(); ++const_iter) { o << ", "; const_iter.current().print_constants(o); } } o << "}\n"; } }

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