Polaris: SSAFullRangeData.cc Source File

SSAFullRangeData.cc Go to the documentation of this file. /// /// /// \file SSAFullRangeData.cc /// #include "utilities/expression_util.h" #include "range_util.h" #include "RangeExpr.h" #include "SSAFullRangeData.h" #include "SSAFullRangeDict.h" /// Template instantiations template class TypedBaseMap<Symbol,SSARangeOrData>; template class ProtoMap<Symbol,SSARangeOrData>; template class Map<Symbol,SSARangeOrData>; template ostream & operator << (ostream &, const Map<Symbol,SSARangeOrData> &); template class KeyIterator<Symbol,SSARangeOrData>; template class TypedCollection<SSAFullRangeData>; template class RefList<SSAFullRangeData>; template ostream & operator << (ostream &, const RefList<SSAFullRangeData> &); template class RefSet<SSAFullRangeData>; template ostream & operator << (ostream &, const RefSet<SSAFullRangeData> &); template class Assign<SSAFullRangeData>; template class Iterator<SSAFullRangeData>; template class TypedBaseMap<Symbol,SSAFullRangeData>; template class ProtoMap<Symbol,SSAFullRangeData>; template class Map<Symbol,SSAFullRangeData>; template ostream & operator << (ostream &, const Map<Symbol,SSAFullRangeData> &); template class KeyIterator<Symbol,SSAFullRangeData>; /// SSARangeOrData::print /// Print out a SSARangeOrData object /// void SSARangeOrData::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 << "]"; } /// is_ssa_function /// Return true if the expression is one of the pseudo-functions inserted /// by SSA. static int _is_ssa_function( const Expression & ex ) { switch (ex.op()) { case ALPHA_OP: case ETA_OP: case GAMMA_OP: case GMU_OP: case MU_OP: case PHI_OP: return 1; } return 0; } /// Constructors SSAFullRangeData::SSAFullRangeData(const Statement &stmt, int timestamp, SSAFullRangeDict &range_dict, int debug GIV(0)) : _accessor(range_dict, stmt) { p_assert(stmt.stmt_class() == ASSIGNMENT_STMT, "The statement given to the SSAFullRangeData constructor was not an assignment statement."); _stmt_ref = &stmt; _timestamp = timestamp; _control_ranges_ref = &range_dict._control_ranges; is_phi_stmt = _is_ssa_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; } SSAFullRangeData::SSAFullRangeData(const SSAFullRangeData &other) : _accessor(other._accessor) { _stmt_ref = other._stmt_ref; _timestamp = other._timestamp; _control_ranges_ref = other._control_ranges_ref; if (other._range) _range = other._range->clone(); else _range = 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; } /// Destructor SSAFullRangeData::~SSAFullRangeData() { if (_range) delete _range; } /// modify_expr /// Modify the given expression with the new expression value, /// deleting the old expression if necessary. static inline void _modify_expr(Expression *& expr, Expression *new_expr) { if (expr) delete expr; expr = new_expr; } /// _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 * SSAFullRangeData::_arg_full_range(const Symbol &arg) { Expression *arg_full_range = 0; SSARangeOrData *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) _modify_expr(arg_full_range, intersect_ranges(arg_full_range, _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 && is_var_in_expr(*arg_full_range, var)) { Expression *subst_range; if (range_ref()) subst_range = range_ref()->clone(); else subst_range = 0; const Expression *my_control_range = control_accessor.get_range_ref(var); if (my_control_range && my_control_range->op() != OMEGA_OP) _modify_expr(subst_range, intersect_ranges(subst_range, _accessor, my_control_range, _accessor)); arg_full_range = _accessor.subst_var_and_simplify(arg_full_range, var, subst_range); if (subst_range) delete subst_range; } return arg_full_range; } /// 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 * SSAFullRangeData::_union_args(bool &new_all_args_are_defined) { Expression *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(); SSARangeOrData &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 { 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) cout << *new_range; else cout << "NULL"; cout << " with "; if (arg_full_range) cout << *arg_full_range; else cout << "NULL"; cout << endl; } if (arg_full_range && is_empty_range(*arg_full_range)) new_all_args_are_defined = false; else _modify_expr(new_range, union_ranges(new_range, _accessor, arg_full_range, _accessor)); if (arg_full_range) delete arg_full_range; } } return new_range; } /// update bool SSAFullRangeData::update(bool in_widening_phase GIV(true)) { bool changed = false; /// ... Update my is_poisoned and needs_iteration fields. KeyIterator<Symbol, SSARangeOrData> iter = arg_ranges_or_data; for ( ; iter.valid(); ++iter) if (iter.current_data().is_data()) { const SSAFullRangeData &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; Expression *new_range = _union_args(new_all_args_are_defined); if (! new_range && ! 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) _modify_expr(new_range, widen_range(new_range, _range, _accessor)); } else _modify_expr(new_range, narrow_range(new_range, _range, _accessor)); are_all_args_defined = new_all_args_are_defined; if ((! _range && new_range) || (_range && ! new_range) || (_range && _range->compare(*new_range) != 0)) { _modify_expr(_range, new_range); new_range = 0; changed = true; } if (new_range) delete new_range; } ++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<SSAFullRangeData> * SSAFullRangeData::succs() const { RefSet<SSAFullRangeData> *my_succs = new RefSet<SSAFullRangeData>; KeyIterator<Symbol, SSARangeOrData> 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 * SSAFullRangeData::listable_clone() const { return new SSAFullRangeData(*this); } /// print void SSAFullRangeData::print(ostream &o) const { o << "["; o << "stmt=" << _stmt_ref->tag(); o << ", ts=" << _timestamp; o << ", range="; if (_range) 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<SSAFullRangeData> 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 SSAFullRangeData::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:06:08 2005