Polaris: JumpFunction.cc Source File

JumpFunction.cc Go to the documentation of this file. /// /// /// \file JumpFunction.cc /// #include "../Collection/KeyIterator.h" #include "../Collection/Iterator.h" #include "../Collection/Mutator.h" #include "../Collection/RefSet.h" #include "../Collection/RefList.h" #include "../Collection/Map.h" #include "../Collection/RefMap.h" #include "../Symbol/Symbol.h" #include "../Expression/Expression.h" #include "JumpFunction.h" #include "AliasSets.h" #include "IPCPConstants.h" /// simplify_var_mods /// Simplify the given mapping of variable modifications. static void _simplify_var_mods(Map<Symbol, Expression> &var_mods) { 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(); Expression *simplified_mod = var_mods.grab(var); Boolean mod_is_ref = (simplified_mod->base_variable_ref() != 0); simplified_mod = simplify(simplified_mod); if (simplified_mod->op() == ID_OP && &simplified_mod->symbol() == &var) delete simplified_mod; else { if (simplified_mod->base_variable_ref() && ! mod_is_ref) simplified_mod = paren(simplified_mod); var_mods.ins(var, simplified_mod); } } delete mod_vars; } /// Constructors ReturnJumpFunction::ReturnJumpFunction(const RefList<Symbol> &param_list, const RefSet<Symbol> &used_global_vars, Map<Symbol, Expression> *old_const_mods, Map<Symbol, Expression> *new_consts) { _param_list = param_list; _used_global_vars = used_global_vars; _simplify_var_mods(*new_consts); _simplify_var_mods(*old_const_mods); _old_const_mods = old_const_mods; _new_consts = new_consts; } ReturnJumpFunction::ReturnJumpFunction(const ReturnJumpFunction &other) { _param_list = other._param_list; _used_global_vars = other._used_global_vars; _old_const_mods = new Map<Symbol,Expression>(*other._old_const_mods); _new_consts = new Map<Symbol,Expression>(*other._new_consts); } /// Destructor ReturnJumpFunction::~ReturnJumpFunction() { delete _old_const_mods; delete _new_consts; } /// _are_vars_in_expr /// Return true if the given expression uses any of the variables in the /// given set. static Boolean _are_vars_in_expr(const Expression &e, const RefSet<Symbol> &vars) { if (e.op() == ID_OP) return vars.member(e.symbol()); else { Iterator<Expression> iter = e.arg_list(); for ( ; iter.valid(); ++iter) if (_are_vars_in_expr(iter.current(), vars)) return True; } return False; } /// subst_vars_in_expr /// Substitute all variables in the given expression and in the /// substitution mapping with their mapped values. static Expression * _subst_vars_in_expr1(Expression *expr, RefSet<Symbol> &subst_vars, const Map<Symbol, Expression> &subst_map) { p_assert(expr, "_subst_vars_in_expr was given a NULL expression."); if (expr->op() == ID_OP) { Symbol &var = expr->symbol(); const Expression *subst_expr = subst_map.find_ref(var); if (subst_expr) { delete expr; if (! subst_vars.member(var)) { subst_vars.ins(var); expr = _subst_vars_in_expr1(subst_expr->clone(), subst_vars, subst_map); subst_vars.del(var); } else expr = omega(); } } else { Mutator<Expression> arg_iter = expr->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) { Assign<Expression> eas(arg_iter.assign()); eas = _subst_vars_in_expr1(arg_iter.pull(), subst_vars, subst_map); if (arg_iter.current().op() == OMEGA_OP) { Expression *om = arg_iter.grab(); delete expr; return om; } } } return expr; } Expression * subst_vars_in_expr(Expression *expr, const Map<Symbol, Expression> &subst_map) { RefSet<Symbol> subst_vars; return _subst_vars_in_expr1(expr, subst_vars, subst_map); } /// subst_vars_in_map /// Substitute the given variables in the expressions of the given map. void subst_vars_in_map(Map<Symbol, Expression> &var_mods, const Map<Symbol, Expression> &subst_map) { if (subst_map.entries() > 0) { 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(); var_mods.ins(var, subst_vars_in_expr(var_mods.grab(var), subst_map)); } delete mod_vars; } } /// modified_aliases /// Return the set of aliased variables whose alias is modified. RefSet<Symbol> * ReturnJumpFunction::_modified_aliases(AliasSets &alias_sets) const { RefSet<Symbol> *modified_aliases = new RefSet<Symbol>; KeyIterator<Symbol, Expression> var_mod_iter = *_old_const_mods; for ( ; var_mod_iter.valid(); ++var_mod_iter) { RefSet<Symbol> *aliased_vars = alias_sets.aliases(var_mod_iter.current_key(), _used_global_vars); Iterator<Symbol> alias_iter = *aliased_vars; for ( ; alias_iter.valid(); ++alias_iter) modified_aliases->ins(alias_iter.current()); delete aliased_vars; } return modified_aliases; } /// modified_vars RefSet<Symbol> * modified_vars(const Map<Symbol, Expression> &var_mods) { RefSet<Symbol> *modified_vars = new RefSet<Symbol>; KeyIterator<Symbol, Expression> var_mod_iter = var_mods; for ( ; var_mod_iter.valid(); ++var_mod_iter) modified_vars->ins(var_mod_iter.current_key()); return modified_vars; } /// eliminate_modified_aliases /// Make all variables that are aliased to a modified variables or /// whose constant map contains a modified alias variable to be non-constant. void ReturnJumpFunction::_eliminate_modified_aliases(Map<Symbol, Expression> &var_mods, AliasSets &alias_sets) const { RefSet<Symbol> *modified_aliases = _modified_aliases(alias_sets); if (modified_aliases->entries()) { /// ... Make all aliased variables whose aliases are modified to be /// ... non-constant in the modification map. Iterator<Symbol> alias_iter = *modified_aliases; for ( ; alias_iter.valid(); ++alias_iter) var_mods.ins(alias_iter.current(), omega()); /// ... Make all variables whose constant expressions contain aliased /// ... variables whose aliases are modified to be non-constant in the /// ... given modification map. RefSet<Symbol> *mod_vars = modified_vars(var_mods); Iterator<Symbol> mod_var_iter = *mod_vars; for ( ; mod_var_iter.valid(); ++mod_var_iter) { const Symbol &var = mod_var_iter.current(); if (_are_vars_in_expr(var_mods[var], *modified_aliases)) var_mods.ins(var, omega()); } delete mod_vars; } delete modified_aliases; } /// rename_formals /// Rename formal parameters to their aliased actual names. void ReturnJumpFunction::_rename_formals(Map<Symbol, Expression> &var_mods, const List<Expression> &param_values) const { p_assert(_param_list.entries() == param_values.entries(), "ReturnJumpFunction::new_values(): The number of formals does not equal the number of actuals."); Iterator<Symbol> formal_iter = _param_list; Iterator<Expression> actual_iter = param_values; for ( ; formal_iter.valid(); ++formal_iter, ++actual_iter) { Symbol &formal = formal_iter.current(); Expression &actual_expr = actual_iter.current(); if (var_mods.member(formal)) { const Symbol *actual = actual_expr.base_variable_ref(); if (actual) { if (actual_expr.op() == ID_OP && formal.type() == actual->type()) var_mods.ins(*actual, var_mods.grab(formal)); else { var_mods.del(formal); var_mods.ins(*actual, omega()); } } else var_mods.del(formal); } } } /// param_map /// Build a mapping from formal parameters to actual expressions. Map<Symbol, Expression> * ReturnJumpFunction::_param_map(const List<Expression> &param_values) const { p_assert(_param_list.entries() == param_values.entries(), "ReturnJumpFunction::_param_map(): The number of formals does not equal the number of actuals."); Map<Symbol, Expression> *param_map = new Map<Symbol, Expression>; Iterator<Symbol> formal_iter = _param_list; Iterator<Expression> actual_iter = param_values; for ( ; formal_iter.valid(); ++formal_iter, ++actual_iter) { const Symbol &formal = formal_iter.current(); Expression &actual_expr = actual_iter.current(); if (formal.type() == actual_expr.type()) param_map->ins(formal, actual_expr.clone()); else param_map->ins(formal, omega()); } return param_map; } /// const_mods Map<Symbol, Expression> * ReturnJumpFunction::const_mods(const List<Expression> &param_values, AliasSets &alias_sets) const { Map<Symbol, Expression> *new_const_mods = new Map<Symbol, Expression>(*_old_const_mods); _eliminate_modified_aliases(*new_const_mods, alias_sets); _rename_formals(*new_const_mods, param_values); Map<Symbol, Expression> *param_map = _param_map(param_values); subst_vars_in_map(*new_const_mods, *param_map); delete param_map; return new_const_mods; } Map<Symbol, Expression> * ReturnJumpFunction::const_mods(const List<Expression> &param_values) const { AliasSets alias_sets; alias_sets.alias(_param_list, param_values); Map<Symbol, Expression> *new_const_mods = const_mods(param_values, alias_sets); _simplify_var_mods(*new_const_mods); return new_const_mods; } /// filter_out_mod_params /// Replace all modified parameters with omega, with the exception to /// parameters whose actual is a scalar or array reference. /// This exception is allowed because aliasing of formal to actual /// would guarantee that the substitution of actual for formal would /// still be correct. static void _filter_out_mod_params(Map<Symbol,Expression> &param_map, const Map<Symbol,Expression> &var_mods) { RefSet<Symbol> *mod_vars = modified_vars(param_map); Iterator<Symbol> mod_var_iter = *mod_vars; for ( ; mod_var_iter.valid(); ++mod_var_iter) { const Symbol &var = mod_var_iter.current(); if (var_mods.member(var) && ! param_map[var].base_variable_ref()) param_map.ins(var, omega()); } delete mod_vars; } /// delete_non_consts /// Delete all non-constant variables from the given mapping. static void _delete_non_consts(Map<Symbol, Expression> &var_mods) { 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 (var_mods[var].op() == OMEGA_OP) var_mods.del(var); } delete mod_vars; } /// new_consts Map<Symbol, Expression> * ReturnJumpFunction::new_consts(const List<Expression> &param_values, AliasSets &alias_sets) const { Map<Symbol, Expression> *new_consts = new Map<Symbol, Expression>(*_new_consts); _eliminate_modified_aliases(*new_consts, alias_sets); _rename_formals(*new_consts, param_values); Map<Symbol, Expression> *param_map = _param_map(param_values); _filter_out_mod_params(*param_map, *new_consts); subst_vars_in_map(*new_consts, *param_map); delete param_map; _delete_non_consts(*new_consts); return new_consts; } Map<Symbol, Expression> * ReturnJumpFunction::new_consts(const List<Expression> &param_values) const { AliasSets alias_sets; alias_sets.alias(_param_list, param_values); Map<Symbol, Expression> *consts = new_consts(param_values, alias_sets); _simplify_var_mods(*consts); return consts; } /// listable_clone Listable * ReturnJumpFunction::listable_clone() const { return new ReturnJumpFunction(*this); } /// print void _print(ostream &o, const Map<Symbol, Expression> &var_mods) { KeyIterator<Symbol,Expression> mod_iter = var_mods; if (mod_iter.valid()) { o << mod_iter.current_key().name_ref() << "=" << mod_iter.current_data(); ++mod_iter; for ( ; mod_iter.valid(); ++mod_iter) o << ", " << mod_iter.current_key().name_ref() << "=" << mod_iter.current_data(); } } void ReturnJumpFunction::print(ostream &o) const { o << "["; 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 << ")"; o << ", old_const_mods={"; _print(o, *_old_const_mods); o << "}"; o << ", new_consts={"; _print(o, *_new_consts); o << "}"; o << "]"; } /// structures_OK int ReturnJumpFunction::structures_OK() const { return (_param_list.structures_OK() && _old_const_mods && _old_const_mods->structures_OK() && _new_consts && _new_consts->structures_OK()); } /// Constructors JumpFunction::JumpFunction(const RefList<Symbol> &param_list, const RefSet<Symbol> &used_global_vars, Map<Symbol, Expression> *old_const_mods, Map<Symbol, Expression> *new_consts) : ReturnJumpFunction(param_list, used_global_vars, old_const_mods, new_consts) { /// ... Nothing to do } JumpFunction::JumpFunction(const JumpFunction &other) : ReturnJumpFunction(other) { /// ... Nothing to do } /// Destructor JumpFunction::~JumpFunction() { /// ... Nothing to do } /// const_param_values /// Generate a constant formal list from the given map of globals to /// constant expressions. List<Expression> * JumpFunction::_const_param_values(const Map<Symbol,Expression> &const_map) const { List<Expression> *actuals = new List<Expression>; Iterator<Symbol> formal_iter = _param_list; for ( ; formal_iter.valid(); ++formal_iter) { const Symbol &formal = formal_iter.current(); const Expression *actual_expr = const_map.find_ref(formal); if (actual_expr && actual_expr->type() == formal.type()) actuals->ins_last(actual_expr->clone()); else actuals->ins_last(omega()); } return actuals; } /// add_map_to_map /// Add all the values in the second map to the first map static void _add_map_to_map(Map<Symbol,Expression> &dest_map, Map<Symbol,Expression> *source_map) { RefSet<Symbol> *mod_vars = modified_vars(*source_map); Iterator<Symbol> mod_var_iter = *mod_vars; for ( ; mod_var_iter.valid(); ++mod_var_iter) { Symbol &var = mod_var_iter.current(); dest_map.ins(var, source_map->grab(var)); } delete mod_vars; delete source_map; } /// update_old_consts /// Update the given set of constants to take the side-effects of the /// routine into account. static void _update_old_consts(Map<Symbol,Expression> &consts, Map<Symbol,Expression> *var_mods) { /// ... Build a set of all modified constants. Map<Symbol,Expression> modified_consts; KeyIterator<Symbol,Expression> var_mod_iter = *var_mods; for ( ; var_mod_iter.valid(); ++var_mod_iter) { const Symbol &var = var_mod_iter.current_key(); const Expression *const_expr = consts.find_ref(var); if (const_expr) modified_consts.ins(var, const_expr->clone()); else modified_consts.ins(var, omega()); } /// ... Add the updated consts to the constant set. _add_map_to_map(consts, var_mods); /// ... Eliminate all modified variables from the set of constants. subst_vars_in_map(consts, modified_consts); /// ... Filter out the OMs from the constant set. _delete_non_consts(consts); } /// constants IPCPConstants * JumpFunction::constants(IPCPConstants &consts, const List<Expression> &param_values) const { AliasSets *alias_sets = new AliasSets(consts.alias_sets()); alias_sets->alias(_param_list, param_values); List<Expression> *const_param_values = _const_param_values(consts.constants()); Map<Symbol, Expression> *new_const_mods = const_mods(*const_param_values, *alias_sets); Map<Symbol, Expression> *updated_consts = new Map<Symbol,Expression>(consts.constants()); _update_old_consts(*updated_consts, new_const_mods); Map<Symbol, Expression> *generated_consts = new_consts(*const_param_values, *alias_sets); delete const_param_values; _add_map_to_map(*updated_consts, generated_consts); _simplify_var_mods(*updated_consts); return new IPCPConstants(updated_consts, alias_sets); } /// listable_clone Listable * JumpFunction::listable_clone() const { return new JumpFunction(*this); }

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