Polaris: IPCPProcData.cc Source File

IPCPProcData.cc Go to the documentation of this file. /// /// /// /// \file IPCPProcData.cc /// #include "../Collection/Iterator.h" #include "../Collection/KeyIterator.h" #include "../Collection/RefSet.h" #include "../Statement/Statement.h" #include "../Symbol/Symbol.h" #include "../Symbol/VariableSymbol.h" #include "../Directive/AssertMayMod.h" #include "../utilities/expression_util.h" #include "../CommonBlock.h" #include "../ProgramUnit.h" #include "../Range/range_dict_util.h" #include "InterProcConstProp.h" #include "IPCPProcData.h" #include "JumpFunction.h" #include "constant.h" /// Template instantiations: template class TypedBaseMap<String, IPCPCallData>; template class ProtoDatabase<String, IPCPCallData>; template class Database<String, IPCPCallData>; template ostream & operator << (ostream &, const Database<String, IPCPCallData> &); template class KeyIterator<String, IPCPCallData>; template class TypedCollection<IPCPConstants>; template class List<IPCPConstants>; template ostream & operator << (ostream &, const List<IPCPConstants> &); template class Assign<IPCPConstants>; template class Iterator<IPCPConstants>; template class Mutator<IPCPConstants>; /// Constructors IPCPCallData::IPCPCallData(IPCPProcData *called_pgm_data) { _called_pgm_data = called_pgm_data; _jump_function = 0; } IPCPCallData::IPCPCallData(const IPCPCallData &other) { _called_pgm_data = other._called_pgm_data; if (other._jump_function) _jump_function = new JumpFunction(*other._jump_function); else _jump_function = 0; } /// Destructor IPCPCallData::~IPCPCallData() { jump_function(0); } /// jump_function void IPCPCallData::jump_function(JumpFunction *jump_func) { if (_jump_function) delete _jump_function; _jump_function = jump_func; } /// add_constant_set void IPCPCallData::add_constant_set(IPCPConstants *constants, const List<Expression> &param_values) { if (_called_pgm_data) _called_pgm_data->add_constant_set(constants, param_values); else delete constants; } /// compute_rtoporder void IPCPCallData::compute_rtoporder(int &max_visited_elems) { if (_called_pgm_data) _called_pgm_data->compute_rtoporder(max_visited_elems); } /// listable_clone Listable * IPCPCallData::listable_clone() const { return new IPCPCallData(*this); } /// print void IPCPCallData::print(ostream &o) const { o << "["; o << "_called_pgm_data="; if (_called_pgm_data) _called_pgm_data->entry().print_debug(o, 0); else o << "NULL"; o << ", _jump_function="; if (_jump_function) o << *_jump_function; else o << "NULL"; o << "]"; } /// structures_OK int IPCPCallData::structures_OK() const { return _called_pgm_data->structures_OK(); } /// proc_name /// Return the name of the subroutine or function called by the given /// statement. static const char * _proc_name(const Statement &call_stmt) { if (call_stmt.stmt_class() == CALL_STMT) return call_stmt.routine_guarded().symbol().name_ref(); else if (call_stmt.stmt_class() == ASSIGNMENT_STMT && call_stmt.rhs().op() == FUNCTION_CALL_OP) return call_stmt.rhs().function().symbol().name_ref(); else return 0; } /// call_arg_list /// Return a reference to the argument list of the given call site. static const List<Expression> & _call_arg_list(const Statement &call_site) { const List<Expression> *args = NULL; if (call_site.stmt_class() == CALL_STMT) args = &call_site.parameters_guarded().arg_list(); else if (call_site.stmt_class() == ASSIGNMENT_STMT && call_site.rhs().op() == FUNCTION_CALL_OP) args = &call_site.rhs().parameters_guarded().arg_list(); else p_abort("_call_arg_list(): Given statement is not a call statement or function call."); return *args; } /// mark_external_func_calls /// Mark all function calls in the given expression as executed /// externally. void IPCPProcData::_mark_external_func_calls(const Expression &expr) { if (expr.op() == ID_OP && expr.symbol().sym_class() == FUNCTION_CLASS) { IPCPProcData *called_proc_data = _ipcp_ref->_get_proc_data_ref(expr.symbol().name_ref()); if (called_proc_data) called_proc_data->called_externally(); } else { Iterator<Expression> arg_iter = expr.arg_list(); for ( ; arg_iter.valid(); ++arg_iter) _mark_external_func_calls(arg_iter.current()); } } /// init_call_sites /// Create a IPCPCallData object for each call site. void IPCPProcData::_init_call_sites() { Iterator<Statement> stmt_iter = _pgm_ref->stmts().iterator(); for ( ; stmt_iter.valid(); ++stmt_iter) { Statement &stmt = stmt_iter.current(); const char *proc_name = _proc_name(stmt); if (proc_name) { IPCPProcData *called_proc_data = _ipcp_ref->_get_proc_data_ref(proc_name); _call_data.ins(stmt.tag(), new IPCPCallData(called_proc_data)); if (called_proc_data && _call_arg_list(stmt).entries() != called_proc_data->param_list().entries()) { cout << "Error: The number of actual parameters of call to " << proc_name << " on line " << stmt.line() << endl; cout << " does not agree with the number of formal parameters for that routine.\n"; p_abort("Aborting."); } } else if (contains_func_call(stmt)) { Iterator<Expression> expr_iter = stmt.iterate_expressions(); for ( ; expr_iter.valid(); ++expr_iter) _mark_external_func_calls(expr_iter.current()); } } } /// convert_local_to_global /// Convert the given local variable into a global variable. const Symbol & IPCPProcData::_convert_local_to_global(const Symbol &local_var, const char *global_namespace) { Symbol *global_var = _local_to_global_vars.find_ref(local_var); if (! global_var) { String global_name = global_namespace; global_name += ":"; global_name += local_var.name_ref(); global_var = _ipcp_ref->_global_vars.find_ref(global_name); if (! global_var) { global_var = new VariableSymbol(global_name, local_var.type(), NOT_FORMAL, NOT_SAVED); /// ... VariableSymbol constructor erases dimensioning info in type, /// ... so set its type again to put the dimensioning info back in. global_var->type(local_var.type()); global_var = &_ipcp_ref->_global_vars.ins(global_var); } _local_to_global_vars.ins(local_var, *global_var); _global_to_local_vars.ins(*global_var, local_var); } return *global_var; } /// init_params /// Initialize the param_list and return_var fields. void IPCPProcData::_init_params() { p_assert(_entry->routine_guarded().op() == ID_OP, "Routine name for an entry statement is not a variable."); const char *entry_name = _entry->routine_guarded().symbol().name_ref(); Iterator<Expression> param_iter = _entry->parameters_guarded().arg_list(); for ( ; param_iter.valid(); ++param_iter) { p_assert(param_iter.current().op() == ID_OP, "An entry statement has a parameter that is not a variable."); const Symbol &global_var = _convert_local_to_global(param_iter.current().symbol(), entry_name); _param_list.ins_last(CASTAWAY(Symbol &) global_var); } if (_entry->routine_guarded().symbol().sym_class() == FUNCTION_CLASS) { const Symbol &global_var = _convert_local_to_global(_entry->routine_guarded().symbol(), entry_name); _return_var = &global_var; } else _return_var = 0; } /// add_params_to_set /// Add my entry's parameters to the given set of variables. void IPCPProcData::_add_params_to_set(RefSet<Symbol> &vars) const { Iterator<Symbol> param_iter = _param_list; for ( ; param_iter.valid(); ++param_iter) vars.ins(param_iter.current()); if (_return_var) vars.ins(* CASTAWAY(Symbol *) _return_var); } /// init_usable_global_vars /// Initialize the set of global variables used by this routine and /// all called subsroutines. void IPCPProcData::_init_usable_global_vars() { /// Collect the useable global variables for called subroutines. KeyIterator<String, IPCPCallData> call_iter = _call_data; for ( ; call_iter.valid(); ++call_iter) { const IPCPProcData *call_data = call_iter.current_data().data_ref(); if (call_data) { Iterator<Symbol> var_iter = call_data->usable_global_vars(); for ( ; var_iter.valid(); ++var_iter) if (! call_data->param_list().member(var_iter.current()) && &var_iter.current() != call_data->return_var()) _usable_global_vars.ins(var_iter.current()); } } /// Add my common variables to the set. DictionaryIter<Symbol> common_iter = _pgm_ref->symtab().iterator(); for ( ; common_iter.valid(); ++common_iter) { const Symbol &var = common_iter.current(); if (var.sym_class() == VARIABLE_CLASS && var.common_ref()) { const Symbol &global_var = _convert_local_to_global(var, var.common_ref()->name_ref()); _usable_global_vars.ins(CASTAWAY(Symbol &) global_var); } } /// Add my parameters to the set. _add_params_to_set(_usable_global_vars); } /// add_refs_to_globals - /// Add the given set of references to the given variable set. void IPCPProcData::_add_refs_to_globals(const RefSet<Expression> &refs) { Iterator<Expression> iter = refs; for ( ; iter.valid(); ++iter) { const Symbol *var = iter.current().base_variable_ref(); if (var && var->sym_class() == VARIABLE_CLASS && var->common_ref()) { const Symbol &global_var = _convert_local_to_global(*var, var->common_ref()->name_ref()); _used_global_vars.ins(CASTAWAY(Symbol &) global_var); } } } /// init_used_global_vars /// Initialize the set of global variables used by this routine and /// all called subsroutines. void IPCPProcData::_init_used_global_vars() { /// Collect the used global variables for called subroutines. KeyIterator<String, IPCPCallData> call_iter = _call_data; for ( ; call_iter.valid(); ++call_iter) { const IPCPProcData *call_data = call_iter.current_data().data_ref(); if (call_data) { Iterator<Symbol> var_iter = call_data->used_global_vars(); for ( ; var_iter.valid(); ++var_iter) if (! call_data->param_list().member(var_iter.current()) && &var_iter.current() != call_data->return_var()) _used_global_vars.ins(var_iter.current()); } } /// Add my common variables to the set. Iterator<Statement> stmt_iter = _pgm_ref->stmts().iterator(); for ( ; stmt_iter.valid(); ++stmt_iter) { const Statement &stmt = stmt_iter.current(); _add_refs_to_globals(stmt.in_refs()); _add_refs_to_globals(stmt.out_refs()); } /// Add my parameters to the set. _add_params_to_set(_used_global_vars); } /// add_refs - /// Add the given set of references to the given variable set. static void _add_refs(RefSet<Symbol> &vars, const RefSet<Expression> &refs) { Iterator<Expression> iter = refs; for ( ; iter.valid(); ++iter) if (iter.current().base_variable_ref()) vars.ins(*iter.current().base_variable_ref()); } /// local_vars RefSet<Symbol> * IPCPProcData::local_vars(const RefSet<Symbol> &vars) const { RefSet<Symbol> *local_ugvs = new RefSet<Symbol>; Iterator<Symbol> global_iter = vars; for ( ; global_iter.valid(); ++global_iter) { const Symbol *local_var = _global_to_local_vars.find_ref(global_iter.current()); if (local_var) local_ugvs->ins(*local_var); else local_ugvs->ins(global_iter.current()); } return local_ugvs; } /// add_vars_to_set /// Add the variables in the given expression to the given set. static void _add_vars_to_set(RefSet<Symbol> &var_set, const Expression &expr) { if (expr.op() == ID_OP && expr.symbol().sym_class() == VARIABLE_CLASS) var_set.ins(expr.symbol()); else { Iterator<Expression> iter = expr.arg_list(); for ( ; iter.valid(); ++iter) _add_vars_to_set(var_set, iter.current()); } } /// candidates /// Return the set of variables that are candidates for constant propagation. RefSet<Symbol> * IPCPProcData::_candidates() const { /// Copy usable_global_vars into candidates, converting global names to /// local names. RefSet<Symbol> *candidates = local_vars(usable_global_vars()); /// Add used local variables to candidates. Iterator<Statement> stmt_iter = _pgm_ref->stmts().iterator(); for ( ; stmt_iter.valid(); ++stmt_iter) { const Statement &stmt = stmt_iter.current(); if (stmt.stmt_class() == CALL_STMT || contains_func_call(stmt) || (stmt.stmt_class() == ASSIGNMENT_STMT && stmt.lhs().op() == ID_OP && _ipcp_ref->_is_substitutable(stmt.lhs().symbol()))) { if (stmt.stmt_class() == ASSIGNMENT_STMT) candidates->ins(stmt.lhs().symbol()); Iterator<Expression> ref_iter = stmt.in_refs(); for ( ; ref_iter.valid(); ++ref_iter) { Symbol *var = ref_iter.current().base_variable_ref(); if (var && _ipcp_ref->_is_substitutable(*var)) candidates->ins(*var); } } } /// Add all variables used in my sets of constants in my candidates. Iterator<IPCPConstants> const_set_iter = _consts_sets; for ( ; const_set_iter.valid(); ++const_set_iter) { KeyIterator<Symbol, Expression> const_iter = const_set_iter.current().constants(); for ( ; const_iter.valid(); ++const_iter) _add_vars_to_set(*candidates, const_iter.current_data()); } return candidates; } /// Constructors IPCPProcData::IPCPProcData(ProgramUnit &pgm, InterProcConstProp &ipcp, const Statement &entry, int debug GIV(0)) { if (debug > 0) { cout << "! Computing side effects for "; entry.print_debug(cout, 0); cout << endl; } _pgm_ref = &pgm; _ipcp_ref = &ipcp; _entry = &entry; _return_jump_function = 0; _rtoporder = -1; _called_externally = False; _init_call_sites(); _init_params(); _init_used_global_vars(); _init_usable_global_vars(); } IPCPProcData::IPCPProcData(ProgramUnit &cloned_proc, const Statement &clone_entry, IPCPProcData &orig_proc_data) { _pgm_ref = &cloned_proc; _ipcp_ref = orig_proc_data._ipcp_ref; _entry = &clone_entry; _rtoporder = -1; _called_externally = False; _call_data = orig_proc_data._call_data; _used_global_vars = orig_proc_data._used_global_vars; _usable_global_vars = orig_proc_data._usable_global_vars; _param_list = orig_proc_data._param_list; _return_var = orig_proc_data._return_var; if (orig_proc_data._return_jump_function) _return_jump_function = new ReturnJumpFunction(*orig_proc_data._return_jump_function); else _return_jump_function = 0; /// Initialize local_to_global_vars and global_to_local_vars. KeyIterator<Symbol,Symbol> ltog_iter = orig_proc_data._local_to_global_vars; for ( ; ltog_iter.valid(); ++ltog_iter) { const Symbol &global_var = ltog_iter.current_data(); const Symbol *local_var; if (&global_var == _return_var) local_var = &_entry->routine_guarded().symbol(); else local_var = &_pgm_ref->symtab()[ltog_iter.current_key().name_ref()]; _local_to_global_vars.ins(*local_var, global_var); _global_to_local_vars.ins(global_var, *local_var); } } /// Destructor IPCPProcData::~IPCPProcData() { if (_return_jump_function) delete _return_jump_function; } /// contains_local_vars /// Return true if the expression contains a variable not in /// used_global_vars. Boolean IPCPProcData::_contains_local_vars(const Expression &expr) const { if (expr.op() == ID_OP) { return (expr.symbol().sym_class() == VARIABLE_CLASS && ! _usable_global_vars.member(expr.symbol())); } else { Iterator<Expression> arg_iter = expr.arg_list(); for ( ; arg_iter.valid(); ++arg_iter) if (_contains_local_vars(arg_iter.current())) return True; } return False; } Boolean IPCPProcData::_contains_local_vars(const Expression &expr, const RefList<Symbol> &caller_formals) const { if (expr.op() == ID_OP) { return (expr.symbol().sym_class() == VARIABLE_CLASS && ! _usable_global_vars.member(expr.symbol()) && ! caller_formals.member(expr.symbol())); } else { Iterator<Expression> arg_iter = expr.arg_list(); for ( ; arg_iter.valid(); ++arg_iter) if (_contains_local_vars(arg_iter.current(), caller_formals)) return True; } return False; } /// filter_out_local_vars /// Filter out all local symbols from the given map. void IPCPProcData::_filter_out_local_vars(Map<Symbol, Expression> &var_mods) const { RefSet<Symbol> *mod_vars = modified_vars(var_mods); Iterator<Symbol> mod_var_iter = *mod_vars; for ( ; mod_var_iter.valid(); ++mod_var_iter) { Symbol &var = mod_var_iter.current(); if (! _usable_global_vars.member(var)) var_mods.del(var); else if (_contains_local_vars(var_mods[var])) var_mods.ins(var, omega()); } delete mod_vars; } void IPCPProcData::_filter_out_local_vars(Map<Symbol, Expression> &var_mods, const RefList<Symbol> &caller_formals) const { RefSet<Symbol> *mod_vars = modified_vars(var_mods); Iterator<Symbol> mod_var_iter = *mod_vars; for ( ; mod_var_iter.valid(); ++mod_var_iter) { Symbol &var = mod_var_iter.current(); if (! _usable_global_vars.member(var)) var_mods.del(var); else if (_contains_local_vars(var_mods[var], caller_formals)) var_mods.ins(var, omega()); } delete mod_vars; } /// _filter_out_entering_consts. /// Filter out any constants in new_consts that are not in old_const_mods. /// This can occur when a constant in new_consts originated from an /// entering interprocedural constant for the procedure. static void _filter_out_entering_consts(Map<Symbol,Expression> &new_consts, const Map<Symbol, Expression> &old_const_mods) { RefSet<Symbol> *mod_vars = modified_vars(new_consts); Iterator<Symbol> mod_var_iter = *mod_vars; for ( ; mod_var_iter.valid(); ++mod_var_iter) { Symbol &var = mod_var_iter.current(); if (! old_const_mods.member(var)) new_consts.del(var); } delete mod_vars; } /// create_return_jump_function void IPCPProcData::create_return_jump_function(Map<Symbol, Expression> *old_const_mods, Map<Symbol, Expression> *new_consts) { _filter_out_entering_consts(*new_consts, *old_const_mods); _rename_locals_to_globals(*old_const_mods); _filter_out_local_vars(*old_const_mods); _rename_locals_to_globals(*new_consts); _filter_out_local_vars(*new_consts); if (_return_jump_function) delete _return_jump_function; _return_jump_function = new ReturnJumpFunction(_param_list, _usable_global_vars, old_const_mods, new_consts); } /// call_data const IPCPCallData * IPCPProcData::call_data(const Statement &call_site) const { return _call_data.find_ref(call_site.tag()); } /// create_jump_function void IPCPProcData::create_jump_function(const Statement &call_site, Map<Symbol, Expression> *old_const_mods, Map<Symbol, Expression> *new_consts, List<Expression> *actuals) { _filter_out_entering_consts(*new_consts, *old_const_mods); IPCPCallData *cdata = _call_data.find_ref(call_site.tag()); if (cdata && cdata->data_ref()) { _rename_locals_to_globals(*old_const_mods); _rename_locals_to_globals(*new_consts); /// ... Add the parameter values to the jump function. p_assert(cdata->data_ref()->param_list().entries() == actuals->entries(), "IPCPProcData::create_jump_function(): The number of given actuals does not equal the number of formals."); Iterator<Symbol> formal_iter = cdata->data_ref()->param_list(); Mutator<Expression> actual_iter = *actuals; for ( ; formal_iter.valid(); ++formal_iter, ++actual_iter) { const Symbol &formal = formal_iter.current(); Expression *actual_expr = actual_iter.grab(); if (formal.type() == actual_expr->type() && (_ipcp_ref->_is_substitutable(formal) || actual_expr->base_variable_ref())) { _rename_locals_to_globals(*actual_expr); new_consts->ins(formal, actual_expr); } else { delete actual_expr; new_consts->ins(formal, omega()); } } cdata->data_ref()->_filter_out_local_vars(*old_const_mods, _param_list); cdata->data_ref()->_filter_out_local_vars(*new_consts, _param_list); RefSet<Symbol> *new_const_mods = modified_vars(*new_consts); Iterator<Symbol> new_const_iter = *new_const_mods; for ( ; new_const_iter.valid(); ++new_const_iter) { Symbol &var = new_const_iter.current(); if ((*new_consts)[var].op() == OMEGA_OP) if (old_const_mods->member(var)) new_consts->del(var); else old_const_mods->ins(var, new_consts->grab(var)); } delete new_const_mods; cdata->jump_function(new JumpFunction(_param_list, cdata->data_ref()->usable_global_vars(), old_const_mods, new_consts)); } delete actuals; } /// rename_locals_to_globals /// Rename all local variables in the given expression to their global /// names. void IPCPProcData::_rename_locals_to_globals(Expression &expr) const { if (expr.op() == ID_OP) { if (expr.symbol().sym_class() == VARIABLE_CLASS) { const Symbol *global_var = _local_to_global_vars.find_ref(expr.symbol()); if (global_var) expr.symbol(*global_var); } } else { Iterator<Expression> iter = expr.arg_list(); for ( ; iter.valid(); ++iter) _rename_locals_to_globals(iter.current()); } } void IPCPProcData::_rename_locals_to_globals(Map<Symbol,Expression> &var_mods) const { RefSet<Symbol> *mod_vars = modified_vars(var_mods); Iterator<Symbol> mod_var_iter = *mod_vars; for ( ; mod_var_iter.valid(); ++mod_var_iter) { Symbol &local_var = mod_var_iter.current(); const Symbol *global_var = _local_to_global_vars.find_ref(local_var); if (! global_var) global_var = &local_var; Expression *global_mod_expr = var_mods.grab(local_var); _rename_locals_to_globals(*global_mod_expr); var_mods.ins(*global_var, global_mod_expr); } delete mod_vars; } void IPCPProcData::_rename_locals_to_globals(List<Expression> &expr_list) const { Iterator<Expression> iter = expr_list; for ( ; iter.valid(); ++iter) _rename_locals_to_globals(iter.current()); } /// _rename_globals_to_locals /// Rename all global variables in the given expression to their local /// names. void IPCPProcData::_rename_globals_to_locals(Expression &expr) const { if (expr.op() == ID_OP) { if (expr.symbol().sym_class() == VARIABLE_CLASS) { const Symbol *local_var = _global_to_local_vars.find_ref(expr.symbol()); if (local_var) expr.symbol(*local_var); } } else { Iterator<Expression> iter = expr.arg_list(); for ( ; iter.valid(); ++iter) _rename_globals_to_locals(iter.current()); } } void IPCPProcData::_rename_globals_to_locals(Map<Symbol,Expression> &var_mods) const { RefSet<Symbol> *mod_vars = modified_vars(var_mods); Iterator<Symbol> mod_var_iter = *mod_vars; for ( ; mod_var_iter.valid(); ++mod_var_iter) { Symbol &global_var = mod_var_iter.current(); const Symbol *local_var = _global_to_local_vars.find_ref(global_var); if (! local_var) local_var = &global_var; Expression *local_mod_expr = var_mods.grab(global_var); _rename_globals_to_locals(*local_mod_expr); var_mods.ins(*local_var, local_mod_expr); } delete mod_vars; } /// local_old_const_mods Map<Symbol,Expression> * IPCPProcData::local_old_const_mods(const Statement &call_site, const ReturnJumpFunction &jump_function) const { List<Expression> global_arg_list(_call_arg_list(call_site)); _rename_locals_to_globals(global_arg_list); Map<Symbol, Expression> *var_mods = jump_function.const_mods(global_arg_list); _rename_globals_to_locals(*var_mods); return var_mods; } /// local_new_consts Map<Symbol,Expression> * IPCPProcData::local_new_consts(const Statement &call_site, const ReturnJumpFunction &jump_function) const { List<Expression> global_arg_list(_call_arg_list(call_site)); _rename_locals_to_globals(global_arg_list); Map<Symbol, Expression> *var_mods = jump_function.new_consts(global_arg_list); _rename_globals_to_locals(*var_mods); return var_mods; } /// add_constant_set void IPCPProcData::add_constant_set(IPCPConstants *constants, const List<Expression> &param_values) { constants->filter_out_vars_not_in_set(_used_global_vars, _usable_global_vars); /// If such a set of constants already exists in my sets of constants, /// return without updating. Iterator<IPCPConstants> consts_iter = _consts_sets; for ( ; consts_iter.valid(); ++consts_iter) if (*constants == consts_iter.current()) { consts_iter.current().merge_invocation_sites(constants); return; } /// The given constant set differs from my other constant sets, /// so add it to my constant sets. constants->proc_data_ref = this; if (constants->constants().entries() == 0) { /// ... Always make the empty constant set be first, so that when cloning /// ... occurs, the original program would receive the empty constant set. _consts_sets.ins_first(constants); } else _consts_sets.ins_last(constants); /// Update the constant sets of my call sites. KeyIterator<String, IPCPCallData> call_iter = _call_data; for ( ; call_iter.valid(); ++call_iter) { IPCPCallData &call_data = call_iter.current_data(); if (call_data.data_ref() && call_data.jump_function_valid()) { const Statement *call_site = _pgm_ref->stmts().find_ref(call_iter.current_key()); p_assert(call_site, "Couldn't find the call statement for one of the object's call sites."); List<Expression> global_arg_list(param_values); _rename_locals_to_globals(global_arg_list); IPCPConstants *call_constants = call_data.jump_function().constants(*constants, global_arg_list); call_constants->add_invocation_site( new CallSite(constants, call_site->tag())); call_data.add_constant_set(call_constants, _call_arg_list(*call_site)); } } } /// update_call_site /// Update my call site with the given tag to the given IPCPProcData object. /// Also rename the call itself to call the procedure owned by the /// given IPCPProcData object. void IPCPProcData::_update_call_site(const char *call_site_tag, IPCPProcData &new_call_proc_data) { IPCPCallData *call_data = _call_data.find_ref(call_site_tag); p_assert(call_data, "IPCPConstants::_update_call_site(): Couldn't find the given call site."); call_data->data_ref(&new_call_proc_data); Statement *call_site = _pgm_ref->stmts().find_ref(call_site_tag); const Symbol &entry_var = new_call_proc_data.entry().routine_guarded().symbol(); Symbol *call_site_symbol = _pgm_ref->symtab().find_ref(entry_var.name_ref()); if (! call_site_symbol) { call_site_symbol = entry_var.clone(); call_site_symbol->external(IS_EXTERNAL); _pgm_ref->symtab().ins(call_site_symbol); } if (call_site->stmt_class() == CALL_STMT) call_site->routine_guarded().symbol(*call_site_symbol); else if (call_site->stmt_class() == ASSIGNMENT_STMT && call_site->rhs().op() == FUNCTION_CALL_OP) { /// ... Make my call site symbol's type be the old call site symbol's /// ... type. This is needed to handle the CHARACTER*(*) /// ... --> CHARACTER*(80) problem in some program units. call_site_symbol->type(call_site->rhs().function().symbol().type()); call_site->rhs().function().symbol(*call_site_symbol); } else p_abort("Internal error: Given call site does not make a subroutine call."); } /// transfer_const_set void IPCPProcData::transfer_const_set(IPCPConstants &consts, IPCPProcData &other) { IPCPConstants *consts_obj = other._consts_sets.grab(consts); _consts_sets.ins_last(consts_obj); consts.proc_data_ref = this; /// Rename all calls to the original program unit with the given /// constant set to calls to the cloned program unit. Iterator<CallSite> caller_iter = consts.invocation_sites(); for ( ; caller_iter.valid(); ++caller_iter) { CallSite &call_site = caller_iter.current(); p_assert(call_site.caller_consts_ref(), "Internal error: main program unit was cloned."); call_site.caller_consts_ref()->proc_data_ref->_update_call_site(call_site.call_tag(), *this); } } /// local_consts /// Return the constants stored in IPCPConstants, where all /// variable references in the constant map are locally defined /// variables. Map<Symbol,Expression> * IPCPProcData::_local_consts(const IPCPConstants &consts) const { /// Filter out global variables not used in my program unit. RefSet<Symbol> locally_used_global_vars; RefSet<Symbol> locally_usable_global_vars; KeyIterator<Symbol,Symbol> global_iter = _global_to_local_vars; for ( ; global_iter.valid(); ++global_iter) { Symbol &global_var = global_iter.current_key(); locally_usable_global_vars.ins(global_var); if (_used_global_vars.member(global_var)) locally_used_global_vars.ins(global_var); } IPCPConstants my_consts(consts); my_consts.filter_out_vars_not_in_set(locally_used_global_vars, locally_usable_global_vars); Map<Symbol,Expression> *lconsts = new Map<Symbol,Expression>(my_consts.constants()); _rename_globals_to_locals(*lconsts); return lconsts; } /// add_consts_to_pgm void IPCPProcData::add_consts_to_pgm(const IPCPConstants &consts) { Map<Symbol,Expression> *const_map = _local_consts(consts); KeyIterator<Symbol, Expression> const_iter = *const_map; for ( ; const_iter.valid(); ++const_iter) if (! const_iter.current_key().is_array()) { /// ... silvius: do not do that as it messes up read-only common vars /// Statement *const_stmt /// = new AssignmentStmt(_pgm_ref->stmts().new_tag(), /// id(const_iter.current_key()), /// const_iter.current_data().clone()); /// _pgm_ref->stmts().ins_after(const_stmt, (Statement *) _entry); } delete const_map; } void IPCPProcData::add_consts_to_pgm() { p_assert(_consts_sets.entries() <= 1, "IPCPProcData::add_consts_to_pgm(): There are multiple number of sets of constants."); if (_consts_sets.entries() == 1) add_consts_to_pgm(_consts_sets[0]); } /// propagate_constants void IPCPProcData::build_jump_functions(int debug GIV(0)) { RefSet<Symbol> *use_candidates = _candidates(); RefSet<Symbol> *def_candidates = new RefSet<Symbol>(*use_candidates); Mutator<Symbol> cand_iter = *def_candidates; for ( ; cand_iter.valid(); ++cand_iter) if (! _ipcp_ref->_is_substitutable(cand_iter.current())) cand_iter.del(); KeyIterator<String,IPCPCallData> call_iter = _call_data; for ( ; call_iter.valid(); ++call_iter) call_iter.current_data().jump_function(0); Map<Symbol,Expression> *entering_constants; if (_consts_sets.entries() == 1) entering_constants = _local_consts(_consts_sets[0]); else entering_constants = new Map<Symbol, Expression>; _ipcp_build_jump_functions(*_pgm_ref, *this, *def_candidates, *use_candidates, *entering_constants, debug); delete entering_constants; delete def_candidates; delete use_candidates; } /// expr_del_global_substituted /// Delete or substitute all global variables in the given expression. Expression * IPCPProcData::_expr_del_global_substituted(Expression *expr) { if (expr) if (expr->op() == ID_OP) { expr->substituted(_expr_del_global_substituted(expr->grab_substituted())); if (_usable_global_vars.member(expr->symbol())) { Expression *new_expr = expr->grab_substituted(); delete expr; return new_expr; } } else { Mutator<Expression> arg_iter = expr->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) { Assign<Expression> eas(arg_iter.assign()); Expression *new_arg = _expr_del_global_substituted(arg_iter.pull()); if (new_arg) eas = new_arg; else { delete expr; delete new_arg; return 0; } } } return expr; } /// del_global_substituted /// Delete or substitute all global variables in my program unit. void IPCPProcData::_del_global_substituted() { Iterator<Statement> stmt_iter = _pgm_ref->stmts().iterator(); for ( ; stmt_iter.valid(); ++stmt_iter) { Mutator<Expression> expr_iter = stmt_iter.current().iterate_expressions(); for ( ; expr_iter.valid(); ++expr_iter) { Assign<Expression> eas(expr_iter.assign()); Expression *new_expr = _expr_del_global_substituted(expr_iter.pull()); p_assert(new_expr, "Internal error in IPCPProcData::_del_global_substituted()"); eas = new_expr; } } } /// propagate_constants void IPCPProcData::propagate_constants(PC_UNREACH_BOOL remove_unreachable, int debug GIV(0)) { RefSet<Symbol> *use_candidates = _candidates(); RefSet<Symbol> *def_candidates = new RefSet<Symbol>(*use_candidates); Mutator<Symbol> cand_iter = *def_candidates; for ( ; cand_iter.valid(); ++cand_iter) if (! _ipcp_ref->_is_substitutable(cand_iter.current())) cand_iter.del(); Map<Symbol,Expression> *entering_constants; if (_consts_sets.entries() == 1) entering_constants = _local_consts(_consts_sets[0]); else entering_constants = new Map<Symbol, Expression>; _ipcp_propagate_constants(*_pgm_ref, *this, *def_candidates, *use_candidates, remove_unreachable, *entering_constants, debug); delete entering_constants; delete def_candidates; delete use_candidates; _del_global_substituted(); } /// add_maymods void IPCPProcData::add_maymods() { KeyIterator<String, IPCPCallData> call_iter = _call_data; for ( ; call_iter.valid(); ++call_iter) { const IPCPProcData *call_data = call_iter.current_data().data_ref(); const Statement *call_site = _pgm_ref->stmts().find_ref(call_iter.current_key()); if (call_data && call_site) { /// ... Delete any old MAYMOD assertions. Mutator<Assertion> asrt_iter = call_site->assertions(); for ( ; asrt_iter.valid(); ++asrt_iter) if (asrt_iter.current().type() == AS_MAYMOD) asrt_iter.del(); /// ... Compute the set of possibly modified variables for this call /// ... site. Map<Symbol, Expression> *var_modifications = local_old_const_mods(*call_site, call_data->return_jump_function()); RefList<Symbol> maymods; KeyIterator<Symbol, Expression> mod_iter = *var_modifications; for ( ; mod_iter.valid(); ++mod_iter) { Symbol &var = mod_iter.current_key(); if (_pgm_ref->symtab().find_ref(var.name_ref()) == &var) maymods.ins_last(var); } delete var_modifications; sort_sym_list(maymods); /// ... Create a MAYMOD assertion with these variables. AssertMayMod *assert = new AssertMayMod(); Mutator<Symbol> mod_var_iter = maymods; for ( ; mod_var_iter.valid(); ++mod_var_iter) assert->arg_list_guarded().ins_last(id(mod_var_iter.current())); call_site->assertions().ins_last(assert); } } } /// expand_all_substituted //GUOBIN HE BEGIN Boolean constant_value(const Expression &expr) { if(expr.arg_list().entries()==0) return (expr.op() == INTEGER_CONSTANT_OP || expr.op() == LOGICAL_CONSTANT_OP); else if(expr.op() == INTRINSIC_CALL_OP) return constant_value(expr.parameters_guarded()); else { Iterator<Expression> iter = expr.arg_list(); for(; iter.valid(); ++iter) if(! constant_value(iter.current())) return false; } return true; } //GUOBIN HE END void IPCPProcData::expand_all_substituted() { //expand_substituted(*_pgm_ref, 0, 0); expand_substituted(*_pgm_ref, 0, constant_value); } /// make_consts_sets_old void IPCPProcData::make_consts_sets_old() { _old_consts_sets.clear(); while (_consts_sets.entries()) _old_consts_sets.ins_first(_consts_sets.grab(0)); } /// have_consts_sets_changed Boolean IPCPProcData::have_consts_sets_changed() const { if (_consts_sets.entries() != _old_consts_sets.entries()) return True; Iterator<IPCPConstants> new_consts_iter = _consts_sets; for ( ; new_consts_iter.valid(); ++new_consts_iter) { const IPCPConstants &new_consts = new_consts_iter.current(); Boolean is_consts_in_set = False; Iterator<IPCPConstants> old_consts_iter = _old_consts_sets; for ( ; old_consts_iter.valid() && ! is_consts_in_set; ++old_consts_iter) if (new_consts == old_consts_iter.current()) is_consts_in_set = True; if (! is_consts_in_set) return True; } return False; } /// listable_clone Listable * IPCPProcData::listable_clone() const { return new IPCPProcData(*this); } /// _print_var_map /// Print a mapping from variables to variables; static void _print_var_map(ostream &o, const RefMap<Symbol,Symbol> &var_map) { o << "{"; KeyIterator<Symbol,Symbol> iter = var_map; if (iter.valid()) { o << iter.current_key().name_ref() << "=" << iter.current_data().name_ref(); ++iter; for ( ; iter.valid(); ++iter) o << ", " << iter.current_key().name_ref() << "=" << iter.current_data().name_ref(); } o << "}"; } /// init_rtoporder void IPCPProcData::init_rtoporder() { _rtoporder = -1; } /// compute_rtoporder void IPCPProcData::compute_rtoporder(int &max_visited_elems) { if (_rtoporder < 0) { KeyIterator<String, IPCPCallData> call_iter = _call_data; for ( ; call_iter.valid(); ++call_iter) call_iter.current_data().compute_rtoporder(max_visited_elems); _rtoporder = max_visited_elems; ++max_visited_elems; } } /// _print_var_set /// Print a mapping from variables to variables; static void _print_var_set(ostream &o, const RefSet<Symbol> &var_map) { o << "{"; Iterator<Symbol> iter = var_map; if (iter.valid()) { o << iter.current().name_ref(); ++iter; for ( ; iter.valid(); ++iter) o << ", " << iter.current().name_ref(); } o << "}"; } /// print void IPCPProcData::print(ostream &o, Boolean pretty_print) const { o << "["; o << "pgm=" << _pgm_ref->routine_name_ref(); o << ", ipcp=" << _ipcp_ref; o << ", entry="; _entry->print_debug(o, 0); o << ", "; o << ", rtoporder=" << _rtoporder; o << ", "; if (pretty_print) o << "\n "; o << "used_global_vars={"; _print_var_set(o, _used_global_vars); o << "}, "; if (pretty_print) o << "\n "; o << "usable_global_vars={"; _print_var_set(o, _usable_global_vars); o << "}, "; if (pretty_print) o << "\n "; o << "local_to_global_vars="; _print_var_map(o, _local_to_global_vars); o << ", "; if (pretty_print) o << "\n "; o << "global_to_local_vars="; _print_var_map(o, _global_to_local_vars); o << ", "; if (pretty_print) o << "\n "; o << "param_list={"; Iterator<Symbol> param_iter = _param_list; if (param_iter.valid()) { o << param_iter.current().name_ref(); ++param_iter; for ( ; param_iter.valid(); ++param_iter) o << ", " << param_iter.current().name_ref(); } o << "}, "; if (pretty_print) o << "\n "; o << "return_var="; if (_return_var) o << _return_var->name_ref(); else o << "NULL"; o << ", "; if (pretty_print) o << "\n "; o << "return_jump_function="; if (_return_jump_function) o << *_return_jump_function; else o << "NULL"; o << ", "; if (pretty_print) o << "\n "; o << "consts_sets=" << _consts_sets; o << ", "; if (pretty_print) o << "\n "; o << "_call_data={"; KeyIterator<String,IPCPCallData> call_iter = _call_data; if (call_iter.valid()) { if (pretty_print) o << "\n "; o << call_iter.current_key() << ": " << call_iter.current_data(); ++call_iter; for ( ; call_iter.valid(); ++call_iter) { o << ", "; if (pretty_print) o << "\n "; o << call_iter.current_key() << ": " << call_iter.current_data(); } } o << "}"; o << "]"; if (pretty_print) o << "\n"; } void IPCPProcData::print(ostream &o) const { print(o, False); } /// structures_OK int IPCPProcData::structures_OK() const { return (_call_data.structures_OK() && _used_global_vars.structures_OK() && _local_to_global_vars.structures_OK() && _global_to_local_vars.structures_OK() && _param_list.structures_OK() && (! _return_jump_function || _return_jump_function->structures_OK())); }

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