Polaris: GSAFullRangeData.cc Source File

GSAFullRangeData.cc Go to the documentation of this file. /// /// /// \file GSAFullRangeData.cc /// #include "../Expression/expr_funcs.h" #include "../utilities/expression_util.h" #include "range_util.h" #include "RangeExpr.h" #include "GSAFullRangeData.h" #include "GSAFullRangeDict.h" /// Template instantiations template class TypedBaseMap<Symbol,GSARangeOrData>; template class ProtoMap<Symbol,GSARangeOrData>; template class Map<Symbol,GSARangeOrData>; template ostream & operator << (ostream &, const Map<Symbol,GSARangeOrData> &); template class KeyIterator<Symbol,GSARangeOrData>; template class TypedCollection<GSAFullRangeData>; template class RefList<GSAFullRangeData>; template ostream & operator << (ostream &, const RefList<GSAFullRangeData> &); template class RefSet<GSAFullRangeData>; template ostream & operator << (ostream &, const RefSet<GSAFullRangeData> &); template class Assign<GSAFullRangeData>; template class Iterator<GSAFullRangeData>; template class TypedBaseMap<Symbol,GSAFullRangeData>; template class ProtoMap<Symbol,GSAFullRangeData>; template class Map<Symbol,GSAFullRangeData>; template ostream & operator << (ostream &, const Map<Symbol,GSAFullRangeData> &); template class KeyIterator<Symbol,GSAFullRangeData>; /// GSARangeOrData::print /// Print out a GSARangeOrData object /// void GSARangeOrData::print(ostream &o) const { o << "["; if (_is_range) { o << "range="; if (_range_ref) o << *_range_ref; else o << "NULL"; } else o << "data=" << _data_ref->stmt().tag(); o << "]"; } /// Constructors GSAFullRangeData::GSAFullRangeData(const Statement &stmt, int timestamp, GSAFullRangeDict &range_dict, int debug GIV(0)) : _accessor(range_dict, stmt) { p_assert(stmt.stmt_class() == ASSIGNMENT_STMT, "The statement given to the GSAFullRangeData constructor was not an assignment statement."); _stmt_ref = &stmt; _timestamp = timestamp; _control_ranges_ref = &range_dict._control_ranges; is_phi_stmt = is_pseudo_function(stmt.rhs()); if (is_phi_stmt) _range = new RangeExpr(constant(1), constant(0)); else _range = simplify(stmt.rhs().clone()); is_poisoned = false; needs_iteration = false; needs_widening = false; are_all_args_defined = false; union_arg_ranges = false; toporder = -1; num_updates = 0; computed = false; df_order = -1; low_link = -1; _debug_level = debug; } GSAFullRangeData::GSAFullRangeData(const GSAFullRangeData &other) : _accessor(other._accessor) { _stmt_ref = other._stmt_ref; _timestamp = other._timestamp; _control_ranges_ref = other._control_ranges_ref; _range = other._range.valid() ? other._range->clone() : 0; is_phi_stmt = other.is_phi_stmt; is_poisoned = other.is_poisoned; needs_iteration = other.needs_iteration; needs_widening = other.needs_widening; arg_ranges_or_data = other.arg_ranges_or_data; arg_preds = other.arg_preds; are_all_args_defined = other.are_all_args_defined; toporder = other.toporder; num_updates = other.num_updates; computed = other.computed; df_order = other.df_order; low_link = other.low_link; _debug_level = other._debug_level; } /// _arg_full_range /// Return the range for the given argument. This range incorporates /// the control flow constraints for that variable as well as its current /// data flow range. This method also guarantees that the variable for /// this object does not occur in the returned range Expression * GSAFullRangeData::_arg_full_range(const Symbol &arg) { Element<Expression> arg_full_range; GSARangeOrData *range_or_data = arg_ranges_or_data.find_ref(arg); if (range_or_data) { const Expression *arg_range; if (range_or_data->is_range()) arg_range = range_or_data->range_ref(); else arg_range = range_or_data->data().range_ref(); if (arg_range) arg_full_range = arg_range->clone(); } /// Intersect the argument's range with constraints for its /// entering flow edge. const Statement *control_stmt = arg_preds.find_ref(arg); if (! control_stmt) control_stmt = &stmt(); RangeAccessor control_accessor(*_control_ranges_ref, *control_stmt); const Expression * arg_control_range = control_accessor.get_range_ref(arg); if (arg_control_range && arg_control_range->op() != OMEGA_OP) { arg_full_range = intersect_ranges(arg_full_range.valid() ? &(*arg_full_range) : 0, _accessor, arg_control_range, _accessor); /// ... Eliminate any references to my lhs variable from the argument. const Symbol &var = stmt().lhs().symbol(); if (arg_full_range.valid() && is_var_in_expr(*arg_full_range, var)) { Element<Expression> subst_range; if (range_ref()) subst_range = range_ref()->clone(); const Expression *my_control_range = control_accessor.get_range_ref(var); if (my_control_range && my_control_range->op() != OMEGA_OP) subst_range = intersect_ranges(subst_range.valid() ? &(*subst_range) : 0, _accessor, my_control_range, _accessor); arg_full_range = _accessor.subst_var_and_simplify(arg_full_range.grab(), var, subst_range.valid() ? &(*subst_range) : 0); } } return arg_full_range.valid() ? arg_full_range.grab() : 0; } /// union_args /// Union the ranges of my arguments togethor and return the result. /// The flag union_arg_ranges determines whether the arguments, or /// the range of the arguments should be used. Expression * GSAFullRangeData::_union_args(bool &new_all_args_are_defined) { Element<Expression> new_range; new_range = new RangeExpr(constant(1), constant(0)); new_all_args_are_defined = true; Iterator<Symbol> iter = args; for ( ; iter.valid(); ++iter) { Symbol &arg = iter.current(); GSARangeOrData &range_or_data = arg_ranges_or_data[arg]; const Expression *arg_range = 0; if (range_or_data.is_range()) arg_range = range_or_data.range_ref(); else arg_range = range_or_data.data().range_ref(); if (arg_range && is_empty_range(*arg_range)) new_all_args_are_defined = false; else { Element<Expression> arg_full_range; if (! union_arg_ranges && ( ! range_or_data.is_data() || range_or_data.data().toporder <= toporder)) arg_full_range = id(arg); else arg_full_range = _arg_full_range(arg); /// ... Union the argument's range to the lhs's range. if (_debug_level >= 30) { cout << "! unioning "; if (new_range.valid()) cout << *new_range; else cout << "NULL"; cout << " with "; if (arg_full_range.valid()) cout << *arg_full_range; else cout << "NULL"; cout << endl; } if (arg_full_range.valid() && is_empty_range(*arg_full_range)) new_all_args_are_defined = false; else new_range = union_ranges(new_range.valid() ? &(*new_range) : 0, _accessor, arg_full_range.valid() ? &(*arg_full_range) : 0, _accessor); } } return new_range.valid() ? new_range.grab() : 0; } /// update bool GSAFullRangeData::update(bool in_widening_phase GIV(true)) { bool changed = false; /// ... Update my is_poisoned and needs_iteration fields. KeyIterator<Symbol, GSARangeOrData> iter = arg_ranges_or_data; for ( ; iter.valid(); ++iter) if (iter.current_data().is_data()) { const GSAFullRangeData &arg_data = iter.current_data().data(); if (! is_poisoned && (arg_data.timestamp() != timestamp() || arg_data.is_poisoned)) { is_poisoned = true; changed = true; } } /// ... Update my range_ref field. if (is_phi_stmt) { bool new_all_args_are_defined; Element<Expression> new_range; new_range = _union_args(new_all_args_are_defined); if (! new_range.valid() && ! union_arg_ranges) { union_arg_ranges = true; new_range = _union_args(new_all_args_are_defined); } if (in_widening_phase) { if (needs_widening && are_all_args_defined) new_range = widen_range(new_range.valid() ? &(*new_range) : 0, _range.valid() ? &(*_range) : 0, _accessor); } else new_range = narrow_range(new_range.valid() ? &(*new_range) : 0, _range.valid() ? &(*_range) : 0, _accessor); are_all_args_defined = new_all_args_are_defined; if ((! _range.valid() && new_range.valid() ) || (_range.valid() && (! new_range.valid() || _range->compare(*new_range) != 0))) { _range = new_range.valid() ? new_range.grab() : 0; changed = true; } } ++num_updates; if (_debug_level >= 20) { cout << stmt().tag() << ": "; int zero = 0; stmt().write(cout, zero); cout << " " << *this << endl; } /// ... Ordinary assignment stmts always change when their arguments /// ... change. if (! is_phi_stmt) changed = true; return changed; } /// succs RefSet<GSAFullRangeData> * GSAFullRangeData::succs() const { RefSet<GSAFullRangeData> *my_succs = new RefSet<GSAFullRangeData>; KeyIterator<Symbol, GSARangeOrData> iter = arg_ranges_or_data; for ( ; iter.valid(); ++iter) if (iter.current_data().is_data() && ! iter.current_data().data().computed && iter.current_data().data().timestamp() == timestamp()) my_succs->ins(iter.current_data().data()); return my_succs; } /// listable_clone Listable * GSAFullRangeData::listable_clone() const { return new GSAFullRangeData(*this); } /// print void GSAFullRangeData::print(ostream &o) const { o << "["; o << "stmt=" << _stmt_ref->tag(); o << ", ts=" << _timestamp; o << ", range="; if (_range.valid()) o << *_range; else o << "NULL"; o << ", psnd=" << is_poisoned; o << ", iter=" << needs_iteration; o << ", wide=" << needs_widening; o << ", adef=" << are_all_args_defined; o << ", tord=" << toporder; o << ", nupd=" << num_updates; o << ", unar=" << union_arg_ranges; o << ", comp=" << computed; o << ", dfor=" << df_order; o << ", lwlk=" << low_link; o << ", args={"; Iterator<Symbol> arg_iter = args; if (arg_iter.valid()) { o << arg_iter.current().name_ref() << ":" << arg_ranges_or_data[arg_iter.current()]; ++arg_iter; for ( ; arg_iter.valid(); ++arg_iter) o << ", " << arg_iter.current().name_ref() << ":" << arg_ranges_or_data[arg_iter.current()]; } o << "}"; o << ", pred={"; KeyIterator<Symbol,Statement> pred_iter = arg_preds; if (pred_iter.valid()) { o << pred_iter.current_key().name_ref() << ":" << pred_iter.current_data().tag(); ++pred_iter; for ( ; pred_iter.valid(); ++pred_iter) o << ", " << pred_iter.current_key().name_ref() << ":" << pred_iter.current_data().tag(); } o << "}"; o << ", users={"; Iterator<GSAFullRangeData> user_iter = users; if (user_iter.valid()) { o << user_iter.current().stmt().tag(); ++user_iter; for ( ; user_iter.valid(); ++user_iter) o << ", " << user_iter.current().stmt().tag(); } o << "}"; o << "]"; } /// structures_OK int GSAFullRangeData::structures_OK() const { return (_stmt_ref->structures_OK() && arg_ranges_or_data.structures_OK()); }

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