Polaris: DeadCodeElimWS.cc Source File

DeadCodeElimWS.cc Go to the documentation of this file. /// /// /// \file DeadCodeElimWS.cc /// #include "../Collection/Iterator.h" #include "../Statement/Statement.h" #include "../Directive/Assertion.h" #include "../utilities/equivalence_util.h" #include "DeadCodeElimWS.h" /// 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, Boolean only_id_exprs) { for (Iterator<Expression> iter = refs; iter.valid(); ++iter) { const Symbol *symbol = iter.current().base_variable_ref(); if (symbol && (! only_id_exprs || iter.current().op() == ID_OP)) { const IntElem *elem = candidates.find_ref(*symbol); if (elem) set.ins(elem->value()); if (! only_id_exprs) { /// ... 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; } } } } } /// assert_refs_to_set /// Convert a collection of Expression references from private or induction /// assertions into a set of symbol tags. static void _assert_refs_to_set(IntSet &set, Iterator<Expression> iter, const Map<Symbol,IntElem> &candidates) { for (; iter.valid(); ++iter) { Expression & expr = iter.current(); switch (expr.op()) { case ID_OP: { const Symbol &symbol = expr.symbol(); const IntElem *elem = candidates.find_ref(symbol); if (elem) set.ins(elem->value()); break; } default: _assert_refs_to_set(set, expr.arg_list(), candidates); } } } /// Constructors /// Build a new DeadCodeElimWS object. DeadCodeElimWS::DeadCodeElimWS(unsigned long pass_tag, const Statement &stmt, const Map<Symbol,IntElem> &candidates) : WorkSpace(pass_tag), use_set(candidates.entries()), kill_set(candidates.entries()), in_live_vars(candidates.entries()), out_live_vars(candidates.entries()) { _refs_to_set(use_set, stmt.in_refs(), candidates, False); if (stmt.stmt_class() != READ_STMT) { _refs_to_set(kill_set, stmt.out_refs(), candidates, True); kill_set -= use_set; } _is_eliminatable = False; _lhs_tag = -1; _private_kill_set = 0; if (stmt.stmt_class() == ASSIGNMENT_STMT) { const Symbol *lhs_var = stmt.lhs().base_variable_ref(); p_assert(lhs_var, "LHS of assignment statement is not an IDExpr or ArrayRefExpr"); const IntElem *tag_elem = candidates.find_ref(*lhs_var); if (tag_elem) { _lhs_tag = candidates[*lhs_var].value(); if (stmt.rhs().is_side_effect_free()) _is_eliminatable = True; } } for (Iterator<Assertion> dirs = stmt.assertions(); dirs.valid(); ++dirs) { const Assertion & ass = dirs.current(); switch (ass.type()) { // TODO: When a LOCAL assertion is added, check that instead // (and ignore PRIVATE assertions) case AS_PRIVATE: if (stmt.stmt_class()==BLOCK_ENTRY_STMT) _assert_refs_to_set(kill_set, ass.arg_list_guarded(), candidates); break; case AS_INDUCTION: { // Get an iterator for the overall induction expression Iterator<Expression> ass_iter1(ass.arg_list_guarded()); // Get an iterator for each individual induction expression Iterator<Expression> ass_iter2(ass_iter1.current().arg_list()); /* Skip over the first induction expression, an IDExpr for the former induction variable, when computing uses because it has been substituted out */ ++ass_iter2; _assert_refs_to_set(use_set, ass_iter2, candidates); break; } default: continue; } } _num_visits = 0; _visited = False; _toporder = -1; } DeadCodeElimWS::DeadCodeElimWS(const DeadCodeElimWS &other) : WorkSpace(other), use_set(other.use_set), kill_set(other.kill_set), in_live_vars(other.in_live_vars), out_live_vars(other.out_live_vars) { _is_eliminatable = other._is_eliminatable; _lhs_tag = other._lhs_tag; if (other._private_kill_set) _private_kill_set = new IntSet(*other._private_kill_set); else _private_kill_set = 0; _num_visits = other._num_visits; _visited = other._visited; _toporder = other._toporder; } DeadCodeElimWS::~DeadCodeElimWS() { private_kill_set(0); } /// update_out_live_vars Boolean DeadCodeElimWS::update_out_live_vars() { Boolean changed = False; if (! is_dead_code()) { IntSet new_out_live_vars(in_live_vars); new_out_live_vars -= kill_set; new_out_live_vars |= use_set; if (new_out_live_vars != out_live_vars) { out_live_vars = new_out_live_vars; changed = True; } } else if (out_live_vars != in_live_vars) { out_live_vars = in_live_vars; changed = True; } 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 DeadCodeElimWS::pretty_print(ostream &o, const Array<Symbol *> &tag_to_candidate) const { o << " is_eliminatable = " << _is_eliminatable; o << ", lhs_tag = " << _lhs_tag << endl; o << " num_visits = " << _num_visits; o << ", toporder = " << _toporder << endl; o << " use = {"; _pretty_print_set(o, use_set, tag_to_candidate); o << "}\n"; o << " kill = {"; _pretty_print_set(o, kill_set, tag_to_candidate); o << "}\n"; if (_private_kill_set) { o << " priv_kill = {"; _pretty_print_set(o, *_private_kill_set, tag_to_candidate); o << "}\n"; } o << " in_live_vars = {"; _pretty_print_set(o, in_live_vars, tag_to_candidate); o << "}\n"; o << " out_live_vars = {"; _pretty_print_set(o, out_live_vars, tag_to_candidate); o << "}\n"; } /// print /// Print out all of my fields in a rather terse and unreadable format void DeadCodeElimWS::print(ostream &o) const { o << "DeadCodeElimWS:{"; o << "is_elim=" << _is_eliminatable << ", "; o << "lhs_tag=" << _lhs_tag << ", "; o << "num_visits=" << _num_visits << ", "; o << "toporder=" << _toporder << ", "; o << "use=" << use_set << ", "; o << "kill=" << kill_set << ", "; o << "priv_kill="; if (_private_kill_set) o << *_private_kill_set; else o << "NULL"; o << ", "; o << "in_live_vars=" << in_live_vars << ", "; o << "out_live_vars=" << out_live_vars; o << "}"; } /// listable_clone /// Return a copy of myself. Listable * DeadCodeElimWS::listable_clone() const { return new DeadCodeElimWS(*this); } /// structures_OK /// Return true if all of my structures are OK. int DeadCodeElimWS::structures_OK() const { return (use_set.structures_OK() && kill_set.structures_OK() && in_live_vars.structures_OK() && out_live_vars.structures_OK()); }

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