Polaris: SSAControlRangeData.cc Source File

SSAControlRangeData.cc Go to the documentation of this file. /// /// /// \file SSAControlRangeData.cc /// #include "Collection/Iterator.h" #include "Collection/KeyIterator.h" #include "utilities/expression_util.h" #include "Symtab.h" #include "RangeAccessor.h" #include "SSAControlRangeData.h" #include "RangeExpr.h" #include "range_util.h" /// Template instantiations template class TypedBaseMap<Statement,SSAControlRangeData>; template class ProtoMap<Statement,SSAControlRangeData>; template class Map<Statement,SSAControlRangeData>; template ostream & operator << (ostream &, const Map<Statement,SSAControlRangeData> &); template class KeyIterator<Statement,SSAControlRangeData>; template class TypedBaseMap<Statement,Map<Symbol, Set<Expression> > >; template class ProtoMap<Statement,Map<Symbol, Set<Expression> > >; template class Map<Statement,Map<Symbol, Set<Expression> > >; template ostream & operator << (ostream &, const Map<Statement,Map<Symbol, Set<Expression> > > &); template class KeyIterator<Statement,Map<Symbol, Set<Expression> > >; /// Constructors SSAControlRangeData::SSAControlRangeData(const Statement &stmt, RangeDict &range_dict, ExprSet &range_values) { _range_dict_ref = &range_dict; _range_values_ref = &range_values; _stmt_ref = &stmt; _idom_ref = 0; clear(); } SSAControlRangeData::SSAControlRangeData(const SSAControlRangeData &other) { _range_dict_ref = other._range_dict_ref; _range_values_ref = other._range_values_ref; _stmt_ref = other._stmt_ref; _idom_ref = other._idom_ref; _icdom_ref = other._icdom_ref; _icdom_succ_ref = other._icdom_succ_ref; _icdom_valid = other._icdom_valid; _om_ref = other._om_ref; _local_ranges = other._local_ranges; _out_ranges = other._out_ranges; } /// Destructor SSAControlRangeData::~SSAControlRangeData() { } /// has_asserts /// Return true if the given statement has assertions. static bool _has_asserts(const Statement &stmt) { Iterator<Assertion> assert_iter = stmt.assertions(); for ( ; assert_iter.valid(); ++assert_iter) if (assert_iter.current().type() == AS_RELATION) return true; return false; } /// compute_icdom_ref /// Compute my immediate control dominator and its successor statement /// which dominates me. void SSAControlRangeData::_compute_icdom_ref() { SSAControlRangeData *dom = _idom_ref; const Statement *succ = 0; if (dom) { const Statement &dom_stmt = dom->stmt(); succ = &stmt(); /// ... My immediate dominator is my immediate control dominator only if: /// ... - My immediate dominator has ASSERT assertions. /// ... - My Immediate dominator is a DO or IF statement, where: /// ... - I'm a control flow successor of that DO or IF statement. /// ... - I'm not the destination of a DO loop exit. /// ... - I'm not the ENDIF of an IF () THEN ... ENDIF statement, /// ... where the flow control of the THEN case will reach me. if (! _has_asserts(dom_stmt) && ((dom_stmt.stmt_class() != IF_STMT && dom_stmt.stmt_class() != ELSEIF_STMT && dom_stmt.stmt_class() != DO_STMT) || ! dom_stmt.succ().member(* CASTAWAY(Statement *) succ) || (dom_stmt.stmt_class() == DO_STMT && succ->prev_ref()->stmt_class() == ENDDO_STMT) || (succ->stmt_class() == ENDIF_STMT && (succ->prev_ref()->stmt_class() != IMPLIED_GOTO_STMT || succ->prev_ref()->pred().entries() > 0)))){ succ = dom->icdom_succ_ref(); dom = dom->icdom_ref(); } } _icdom_ref = dom; _icdom_succ_ref = succ; _icdom_valid = true; } /// add_asserts_to_ranges /// Add any relation assertions for the given statement to /// the given set of ranges. static void _add_asserts_to_ranges(Map<Symbol, Set<Expression> > &var_ranges, const Statement &stmt) { Iterator<Assertion> assert_iter = stmt.assertions(); for ( ; assert_iter.valid(); ++assert_iter) { const Assertion &assert = assert_iter.current(); if (assert.type() == AS_RELATION) { Iterator<Expression> arg_iter = assert.arg_list_guarded(); for ( ; arg_iter.valid(); ++arg_iter) { Map<Symbol, Set<Expression> > *assert_ranges = extract_ranges(arg_iter.current(), false); KeyIterator<Symbol, Set<Expression> > range_iter = *assert_ranges; for ( ; range_iter.valid(); ++range_iter) { Set<Expression> *ranges = var_ranges.find_ref(range_iter.current_key()); if (! ranges) { ranges = new Set<Expression>; var_ranges.ins(range_iter.current_key(), ranges); } Mutator<Expression> elem_iter = range_iter.current_data(); for ( ; elem_iter.valid(); ++elem_iter) ranges->ins(elem_iter.grab()); } delete assert_ranges; } } } } /// get_local_ranges /// Return the set of new control ranges for the control-flow edge from /// this statement to the given statement. Map<Symbol, Set<Expression> > & SSAControlRangeData::_get_local_ranges(const Statement &succ_stmt) { Map<Symbol, Set<Expression> > *succ_local_ranges = _local_ranges.find_ref(succ_stmt); if (! succ_local_ranges) { if (! contains_func_call(stmt())){ if ((stmt().stmt_class() == IF_STMT || stmt().stmt_class() == ELSEIF_STMT) && stmt().next_ref() != stmt().follow_ref()) { if (&succ_stmt == stmt().next_ref()) succ_local_ranges = extract_ranges(stmt().expr(), false); else succ_local_ranges = extract_ranges(stmt().expr(), true); } else if (stmt().stmt_class() == DO_STMT && stmt().index().type().data_type() == INTEGER_TYPE && stmt().next_ref() != stmt().follow_ref() && &succ_stmt == stmt().next_ref()) { RangeAccessor accessor(*_range_dict_ref, stmt()); EXPR_SIGN step_sign = accessor.sign(stmt().step()); if (step_sign != POS_NEG_EXPR) { Expression *bound_cond, *index_range; if (step_sign == POS_EXPR) { bound_cond = le(stmt().init().clone(), stmt().limit().clone()); index_range = new RangeExpr(stmt().init().clone(), stmt().limit().clone()); } else { bound_cond = ge(stmt().init().clone(), stmt().limit().clone()); index_range = new RangeExpr(stmt().limit().clone(), stmt().init().clone()); } succ_local_ranges = extract_ranges(*bound_cond, false); delete bound_cond; index_range = simplify(index_range); const Symbol &index = stmt().index().symbol(); Set<Expression> *index_ranges = succ_local_ranges->find_ref(index); if (! index_ranges) { index_ranges = new Set<Expression>; succ_local_ranges->ins(index, index_ranges); } index_ranges->ins(index_range); } } } if (! succ_local_ranges) succ_local_ranges = new Map<Symbol, Set<Expression> >; _add_asserts_to_ranges(*succ_local_ranges, stmt()); _local_ranges.ins(succ_stmt, succ_local_ranges); } return *succ_local_ranges; } Set<Expression> * SSAControlRangeData::_get_local_ranges(const Symbol &var, const Statement &succ_stmt) { return _get_local_ranges(succ_stmt).find_ref(var); } /// get_succ_range_ref /// Get the control range associated with the given variable and exiting /// control-flow edge whose sink is the given statement. Expression * SSAControlRangeData::_get_succ_range_ref(const Symbol &var, const Statement &succ_stmt) { RefMap<Symbol, Expression> *edge_ranges = _out_ranges.find_ref(succ_stmt); if (! edge_ranges) { edge_ranges = new RefMap<Symbol, Expression>; _out_ranges.ins(succ_stmt, edge_ranges); } Expression *range = edge_ranges->find_ref(var); if (! range) { range = get_range_ref(var); /// ... This assignment must be here to prevent an infinite recursion /// ... originating from one the the intersect_ranges() operations /// ... below. if (range) edge_ranges->ins(var, *range); else { if (! _om_ref) _om_ref = &_range_values_ref->ins(omega()); edge_ranges->ins(var, *_om_ref); } Set<Expression> *local_ranges_ref = _get_local_ranges(var, succ_stmt); if (local_ranges_ref) { RangeAccessor accessor(*_range_dict_ref, stmt()); Iterator <Expression> local_range_iter = *local_ranges_ref; Expression *local_range = local_range_iter.current().clone(); ++local_range_iter; for ( ; local_range_iter.valid(); ++local_range_iter) { Expression *new_local_range = intersect_ranges(local_range, accessor, &local_range_iter.current(), accessor); delete local_range; local_range = new_local_range; } Expression *final_range = intersect_ranges(range, accessor, local_range, accessor); delete local_range; range = (Expression *) &_range_values_ref->ins(final_range); edge_ranges->ins(var, *range); } } if (range && range->op() == OMEGA_OP) range = 0; return range; } /// get_range_ref /// Get the control range associated with the given variable. Expression * SSAControlRangeData::get_range_ref(const Symbol &var) { SSAControlRangeData *icdom = icdom_ref(); if (! icdom) return 0; return icdom->_get_succ_range_ref(var, *icdom_succ_ref()); } /// num_computed_ranges int SSAControlRangeData::num_computed_ranges() const { int num_ranges = 0; KeyIterator<Statement, RefMap<Symbol, Expression> > iter = _out_ranges; for ( ; iter.valid(); ++iter) num_ranges += iter.current_data().entries(); return num_ranges; } /// range_vars RefSet<Symbol> * SSAControlRangeData::range_vars() { RefSet<Symbol> *my_range_vars = 0; SSAControlRangeData *icdom = icdom_ref(); if (icdom) { my_range_vars = icdom->range_vars(); Map<Symbol, Set<Expression> > &local_ranges = icdom->_get_local_ranges(*icdom_succ_ref()); KeyIterator<Symbol, Set<Expression> > iter = local_ranges; for ( ; iter.valid(); ++iter) my_range_vars->ins(iter.current_key()); } else my_range_vars = new RefSet<Symbol>; return my_range_vars; } /// clear void SSAControlRangeData::clear() { _icdom_ref = 0; _icdom_succ_ref = 0; _icdom_valid = false; _om_ref = 0; _local_ranges.clear(); _out_ranges.clear(); } /// clear void SSAControlRangeData::clear_ranges() { _om_ref = 0; _out_ranges.clear(); } /// listable_clone Listable * SSAControlRangeData::listable_clone() const { return new SSAControlRangeData(*this); } /// print_data_ref static void _print_data_ref(ostream &o, const SSAControlRangeData *data) { if (data) o << data->stmt().tag(); else o << "NULL"; } /// print void SSAControlRangeData::print(ostream &o) const { o << "["; o << "stmt=" << stmt().tag(); o << ", idom_ref="; _print_data_ref(o, _idom_ref); o << ", icdom_ref="; if (_icdom_valid) _print_data_ref(o, _icdom_ref); else o << "???"; o << ", ipdom_succ_ref="; if (_icdom_valid) if (_icdom_succ_ref) o << _icdom_succ_ref->tag(); else o << "NULL"; else o << "???"; o << ", local_ranges={"; KeyIterator<Statement, Map<Symbol, Set<Expression> > > local_succ_iter = _local_ranges; for ( ; local_succ_iter.valid(); ++local_succ_iter) { o << ", " << local_succ_iter.current_key().tag() << ":{"; KeyIterator<Symbol, Set<Expression> > local_var_iter = local_succ_iter.current_data(); for ( ; local_var_iter.valid(); ++local_var_iter) o << ", " << local_var_iter.current_key().name_ref() << ":" << local_var_iter.current_data() << ", "; o << "}, "; } o << "}"; o << ", out_ranges={"; KeyIterator<Statement, RefMap<Symbol, Expression> > out_succ_iter = _out_ranges; for ( ; out_succ_iter.valid(); ++out_succ_iter) { o << out_succ_iter.current_key().tag() << ":{"; KeyIterator<Symbol, Expression> out_var_iter = out_succ_iter.current_data(); for ( ; out_var_iter.valid(); ++out_var_iter) { pretty_print_range(o, out_var_iter.current_data(), out_var_iter.current_key()); o << ", "; } o << "}, "; } o << "}"; o << "]"; } /// structures_OK int SSAControlRangeData::structures_OK() const { return 1; }

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