Polaris: PropConstWS.cc Source File

PropConstWS.cc Go to the documentation of this file. /// /// /// \file PropConstWS.cc /// #include "../Collection/Iterator.h" #include "../Statement/Statement.h" #include "../utilities/equivalence_util.h" #include "../utilities/expression_util.h" #include "PropConstWS.h" #include "IPCPProcData.h" /// Template instantiations: template class TypedCollection<PropConstValue>; template class List<PropConstValue>; template ostream & operator << (ostream &, const List<PropConstValue> &); template class Assign<PropConstValue>; template class Iterator<PropConstValue>; template class Mutator<PropConstValue>; /// refs_to_set /// Convert a collection of Expression references (e.g. in_refs or out_refs) /// into a set of symbol tags. static void _refs_to_set(IntSet &set, const RefSet<Expression> &refs, const Map<Symbol,IntElem> &candidates) { for (Iterator<Expression> iter = refs; iter.valid(); ++iter) { const Symbol *symbol = iter.current().base_variable_ref(); if (symbol) { const IntElem *elem = candidates.find_ref(*symbol); if (elem) set.ins(elem->value()); /// ... Also place any aliased variables in the set. RefSet<Symbol> *aliases = equiv_aliases(*symbol); if (aliases) { Iterator<Symbol> alias_iter = *aliases; for ( ; alias_iter.valid(); ++alias_iter) { const IntElem *alias_elem = candidates.find_ref(alias_iter.current()); if (alias_elem) set.ins(alias_elem->value()); } delete aliases; } } } } /// refs_are_candidates /// Return true if all Expression references (e.g. in_refs or out_refs) /// are either parameters or contained in the candidates Dictionary. static Boolean _refs_are_candidates(const RefSet<Expression> &refs, const Map<Symbol,IntElem> &candidates) { for (Iterator<Expression> iter = refs; iter.valid(); ++iter) { const Symbol *symbol = iter.current().base_variable_ref(); if (symbol && (symbol->sym_class() != SYMBOLIC_CONSTANT_CLASS && ! candidates.member(*symbol))) return False; } return True; } /// ok_to_substitute /// Return true if it is ok to substitute the given statement. A statement /// is substitutable if it is an assignment statement which only uses /// variables in the candidates set, and whose right hand side is free of /// side effects. static Boolean _ok_to_substitute(const Statement &stmt, const Map<Symbol,IntElem> &def_candidates, const Map<Symbol,IntElem> &use_candidates) { if (stmt.stmt_class() == ASSIGNMENT_STMT && stmt.lhs().op() == ID_OP && def_candidates.member(stmt.lhs().symbol()) && stmt.rhs().is_side_effect_free() && (int) _refs_are_candidates(stmt.in_refs(), use_candidates) && (int) _refs_are_candidates(stmt.out_refs(), use_candidates) && (int) _refs_are_candidates(stmt.act_refs(), use_candidates) && ! (stmt.lhs().type().data_type() == INTEGER_TYPE && stmt.rhs().type().data_type() != INTEGER_TYPE)) return True; return False; } /// init_const_map /// Initialize the constant mapping. void PropConstWS::_init_const_map(const Statement &stmt) { int sym_tag; for (sym_tag = mod_set.first(); sym_tag != -1; sym_tag = mod_set.next(sym_tag)) { if (sym_tag != _lhs_tag) { out_const_map[sym_tag].non_const(stmt); out_const_map.int_non_const(sym_tag); } } } void PropConstWS::_init_const_map(const Statement &call_site, const IPCPProcData &call_proc_data, const IPCPProcData &proc_data, Boolean use_old_const_mods) { Map<Symbol, Expression> *var_modifications; if (use_old_const_mods) var_modifications = proc_data.local_old_const_mods(call_site, call_proc_data.return_jump_function()); else var_modifications = proc_data.local_new_consts(call_site, call_proc_data.return_jump_function()); /// ... Update the constant map to take the variable modifications into account. add_consts(*var_modifications); /// ... Update the constant map to handle a function return. if (call_site.stmt_class() == ASSIGNMENT_STMT) { const Symbol &lhs_var = *call_site.lhs().base_variable_ref(); const Expression *lhs_expr = var_modifications->find_ref(*call_proc_data.return_var()); p_assert(lhs_expr || ! use_old_const_mods, "Internal Error: Function return value is marked as unmodified."); if (lhs_expr) _add_const(lhs_var, *lhs_expr); } delete var_modifications; } /// Constructors /// Build a new PropConstWS object. PropConstWS::PropConstWS(unsigned long pass_tag, const Statement &stmt, const Map<Symbol,IntElem> &def_candidates, const Map<Symbol,IntElem> &use_candidates, const Array<Symbol *> &tag_to_candidate) : WorkSpace(pass_tag), mod_set(use_candidates.entries()), poisoned_vars(use_candidates.entries()), in_const_map(use_candidates.entries(), tag_to_candidate), out_const_map(use_candidates.entries(), tag_to_candidate) { _stmt = &stmt; _refs_to_set(mod_set, stmt.out_refs(), use_candidates); _is_substitutable = _ok_to_substitute(stmt, def_candidates, use_candidates); _def_candidates = &def_candidates; _use_candidates = &use_candidates; if (_is_substitutable) { _add_const(*stmt.lhs().base_variable_ref(), stmt.rhs()); _lhs_tag = def_candidates[*stmt.lhs().base_variable_ref()].value(); } else { _lhs_tag = -1; } _init_const_map(stmt); pred = stmt.pred(); succ = stmt.succ(); const_cond = True; unknown_call = (stmt.stmt_class() == CALL_STMT || contains_func_call(stmt)); _num_visits = 0; _visited = False; _toporder = -1; } PropConstWS::PropConstWS(unsigned long pass_tag, const Statement &stmt, const Statement &call_site, const IPCPProcData &call_proc_data, const IPCPProcData &proc_data, Boolean use_old_const_mods, const Map<Symbol,IntElem> &def_candidates, const Map<Symbol,IntElem> &use_candidates, const Array<Symbol *> &tag_to_candidate) : WorkSpace(pass_tag), mod_set(use_candidates.entries()), poisoned_vars(use_candidates.entries()), in_const_map(use_candidates.entries(), tag_to_candidate), out_const_map(use_candidates.entries(), tag_to_candidate) { _stmt = &stmt; _is_substitutable = False; _lhs_tag = -1; _def_candidates = &def_candidates; _use_candidates = &use_candidates; _init_const_map(call_site, call_proc_data, proc_data, use_old_const_mods); pred = stmt.pred(); succ = stmt.succ(); const_cond = True; unknown_call = (stmt.stmt_class() != CALL_STMT && stmt.stmt_class() != ASSIGNMENT_STMT && contains_func_call(stmt)); _num_visits = 0; _visited = False; _toporder = -1; } PropConstWS::PropConstWS(const PropConstWS &other) : WorkSpace(other), mod_set(other.mod_set), poisoned_vars(other.poisoned_vars), in_const_map(other.in_const_map), out_const_map(other.out_const_map) { _stmt = other._stmt; _const_values = other._const_values; _is_substitutable = other._is_substitutable; _lhs_tag = other._lhs_tag; pred = other.pred; succ = other.succ; const_cond = other.const_cond; unknown_call = other.unknown_call; _num_visits = other._num_visits; _visited = other._visited; _toporder = other._toporder; } PropConstWS::~PropConstWS() { /// ... Nothing to do } void PropConstWS::toporder(int val) { _toporder = val; Iterator<PropConstValue> iter = _const_values; for ( ; iter.valid(); ++iter) iter.current().stmt_toporder(val); } Boolean PropConstWS::update_out_const_map() { Boolean changed = False; for (int sym_tag = 0; sym_tag < in_const_map.entries(); ++sym_tag) if (! mod_set[sym_tag]) { if (out_const_map[sym_tag] != in_const_map[sym_tag]) { out_const_map[sym_tag] = in_const_map[sym_tag]; changed = True; } if (out_const_map.int_state(sym_tag) != in_const_map.int_state(sym_tag) || (out_const_map.int_state(sym_tag) == CONST && (out_const_map.int_const_val(sym_tag) != in_const_map.int_const_val(sym_tag)))) { switch (in_const_map.int_state(sym_tag)) { case CONST: out_const_map.int_const(sym_tag, in_const_map.int_const_val(sym_tag)); break; case NON_CONST: case MAY_BE_CONST: out_const_map.int_non_const(sym_tag); break; default: p_abort("Internal error: PropConstWS::update_out_const_map()."); break; } changed = True; } } if (_update_int_consts()) changed = True; return changed; } /// add_const void PropConstWS::_add_const(const Symbol &const_var, const Expression &const_expr) { const IntElem *elem = _use_candidates->find_ref(const_var); if (elem) { int sym_tag = elem->value(); mod_set.ins(sym_tag); if (const_expr.op() == OMEGA_OP || ! _def_candidates->member(const_var)) { out_const_map[sym_tag].non_const(stmt()); out_const_map.int_non_const(sym_tag); } else { PropConstValue *const_val = new PropConstValue(const_expr, stmt(), -1, *_use_candidates); _const_values.ins_last(const_val); out_const_map[sym_tag].constant(*const_val); if (const_val->expr().op() == INTEGER_CONSTANT_OP) out_const_map.int_const(sym_tag, const_val->expr().value()); else if (const_val->expr().op() == LOGICAL_CONSTANT_OP) if (strcmp(const_val->expr().data_ref(), ".TRUE.") == 0) out_const_map.int_const(sym_tag, 1); else if (strcmp(const_val->expr().data_ref(), ".FALSE.") == 0) out_const_map.int_const(sym_tag, 0); else out_const_map.int_non_const(sym_tag); else out_const_map.int_non_const(sym_tag); } } } /// add_consts void PropConstWS::add_consts(const Map<Symbol, Expression> &constants) { KeyIterator<Symbol, Expression> const_iter = constants; for ( ; const_iter.valid(); ++const_iter) _add_const(const_iter.current_key(), const_iter.current_data()); } /// subst_ints_in_expr /// Substitute all variables in the given expression with their integer /// values. If this could not be done, return NULL. static Expression * _subst_ints_in_expr(Expression *expr, const PropConstMap &entering_consts, const Map<Symbol,IntElem> &candidates) { if (! expr) return expr; else if (expr->op() == ID_OP && expr->symbol().sym_class() == VARIABLE_CLASS) { const Symbol &var = expr->symbol(); delete expr; const IntElem *elem = candidates.find_ref(var); if (elem) { int sym_tag = elem->value(); if (entering_consts.int_state(sym_tag) == CONST) if (var.type().data_type() == LOGICAL_TYPE) if (entering_consts.int_const_val(sym_tag) == 0) return constant(".FALSE."); else return constant(".TRUE."); else return constant(entering_consts.int_const_val(sym_tag)); } return 0; } else { Mutator<Expression> iter = expr->arg_list(); for ( ; iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); Expression *new_arg = _subst_ints_in_expr(iter.pull(), entering_consts, candidates); if (new_arg) eas = new_arg; else { delete expr; return 0; } } } return expr; } /// int_constval; Boolean int_const_val(const Expression &expr, const PropConstMap &entering_consts, const Map<Symbol, IntElem> &candidates, int &int_const) { int_const = -9999; Boolean success = False; Expression *int_expr = _subst_ints_in_expr(expr.clone(), entering_consts, candidates); if (int_expr) { int_expr = simplify(int_expr); if (int_expr->op() == INTEGER_CONSTANT_OP) { int_const = int_expr->value(); success = True; } else if (int_expr->op() == LOGICAL_CONSTANT_OP) { success = True; if (strcmp(int_expr->data_ref(), ".TRUE.") == 0) int_const = 1; else if (strcmp(int_expr->data_ref(), ".FALSE.") == 0) int_const = 0; else success = False; } delete int_expr; } return success; } /// update_int_consts Boolean PropConstWS::_update_int_consts() { Boolean changed = False; for (int sym_tag = mod_set.first(); sym_tag != -1; sym_tag = mod_set.next(sym_tag)) { PropConstElem &elem = out_const_map[sym_tag]; if (elem.state() == CONST && _const_values.member((PropConstValue &) elem.const_val())) { int constant; if (int_const_val(elem.expr(), in_const_map, *_use_candidates, constant)) { if (out_const_map.int_state(sym_tag) != CONST || out_const_map.int_const_val(sym_tag) != constant) changed = True; out_const_map.int_const(sym_tag, constant); } else { if (out_const_map.int_state(sym_tag) != NON_CONST) changed = True; out_const_map.int_non_const(sym_tag); } } } return changed; } /// pretty_print_set /// Print out a IntSet using symbol names rather than their integer tags. static void _pretty_print_set(ostream &o, const IntSet &set, const Array<Symbol *> &tag_to_candidate) { int sym_tag = set.first(); if (sym_tag != -1) { o << tag_to_candidate[sym_tag]->name_ref(); while ((sym_tag = set.next(sym_tag)) != -1) o << ", " << tag_to_candidate[sym_tag]->name_ref(); } } /// pretty_print /// Print out all of my fields in a nice, readable format void PropConstWS::pretty_print(ostream &o) const { o << " stmt = " << _stmt->tag(); o << ", is_substitutable = " << _is_substitutable; o << ", lhs_tag = " << _lhs_tag << endl; o << " num_visits = " << _num_visits; o << ", toporder = " << _toporder; o << ", const_cond = " << const_cond << endl; o << " pred = {"; print_stmt_tags(o, (RefSet<Statement> &) pred); o << "}, succ = {"; print_stmt_tags(o, (RefSet<Statement> &) succ); o << "}\n"; o << " mod = {"; _pretty_print_set(o, mod_set, in_const_map.tag_to_candidate()); o << "}\n"; o << " in_const_map = "; in_const_map.pretty_print(o); o << endl; o << " out_const_map = "; out_const_map.pretty_print(o); o << endl; o << " const_values = {" << _const_values << "}\n"; } /// print /// Print out all of my fields in a rather terse and unreadable format void PropConstWS::print(ostream &o) const { o << "PropConstWS:{"; o << "mod=" << mod_set << ", "; o << "is_subst=" << _is_substitutable << ", "; o << "lhs_tag=" << _lhs_tag << ", "; o << "num_visits=" << _num_visits << ", "; o << "const_cond=" << const_cond << ", "; o << "unknown_call=" << unknown_call << ", "; o << "toporder=" << _toporder << ", "; o << "pred = "; print_stmt_tags(o, (RefSet<Statement> &) pred); o << ", "; o << "succ = "; print_stmt_tags(o, (RefSet<Statement> &) succ); o << ", "; o << "in_const_map={" << in_const_map << "}" << ", "; o << "out_const_map={" << out_const_map << "}" << ", "; o << "const_values={" << _const_values << "}"; o << "}"; } /// listable_clone /// Return a copy of myself. Listable * PropConstWS::listable_clone() const { return new PropConstWS(*this); } /// structures_OK /// Return true if all of my structures are OK. int PropConstWS::structures_OK() const { return (mod_set.structures_OK() && poisoned_vars.structures_OK() && in_const_map.structures_OK() && out_const_map.structures_OK()); }

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