Polaris: SSAFullRangeDict.h Source File

SSAFullRangeDict.h Go to the documentation of this file. #ifndef _SSA_FULL_RANGE_DICT_H #define _SSA_FULL_RANGE_DICT_H /// /// file SSAFullRangeDict.h /// /// \class SSAFullRangeDict /// \brief Collection of ranges extracted from SSA program's control flow /// \defgroup Polaris /// \ingroup Polaris /// Range /// \see SSAFullRangeDict.h /// \see SSAFullRangeDict.h /// \see SSAFullRangeDict.cc /// /// \endcode /// \section Overview Overview /// An SSAFullRangeDict object is a repository for variable /// ranges for a program unit in SSA form. Ranges derived from /// both data flow and control flow are collected, (unlike /// SSAControlRangeDict.h). /// /// \endcode /// \section Description Description /// An SSAFullRangeDict object is a repository of the variable /// ranges for all points of a program unit in SSA form. These ranges /// are extracted from the data flow and control flow of the program; /// that is, they are taken from IF conditional tests, DO statements, /// and CSRD$ ASSERT statements, assignment statements, and phi /// statements. /// /// SSAFullRangeDict objects are demand-driven. That is, they /// compute the ranges for a particular statement only when they /// are asked for. If instead, the user wishes to have all the /// program unit's ranges to be computed at once, the user can /// call the touch() method.. /// /// The algorithm for computing the ranges of a program on demand /// using SSA form can be found in Blume and Eigenmann, "Demand- /// Driven Symbolic Range Propagation". /// #include "Collection/Map.h" #include "Collection/RefMap.h" #include "Collection/Database.h" #include "Symbol/Symbol.h" #include "Expression/Expression.h" #include "Statement/Statement.h" #include "Array.h" #include "String.h" #include "IntElem.h" /// #include "RangeDict.h" #include "SSAControlRangeDict.h" #include "SSAFullRangeData.h" #include "ExprSet.h" /// class IntSet; class SSAProgramUnit; class SSAFullRangeDict : public RangeDict { friend SSAFullRangeData; public: SSAFullRangeDict(SSAProgramUnit &pgm, int debug = 0); virtual ~SSAFullRangeDict(); void touch(); ///< Force this object to compute the ranges for each statement ///< in the program unit. void control_touch(); ///< Force this object to compute the ranges for each statement ///< in the program unit. Only ranges derived from control flow ///< is touched. void data_touch(); ///< Force this object to compute the ranges for each statement ///< in the program unit. Only ranges derived from data flow ///< is touched. (However, touching these data ranges may ///< cause some control ranges to be computed.) void clear(); ///< Clear all saved data and control ranges stored within myself. void clear_ranges(); ///< Clear all saved data and control ranges stored within myself. ///< Like clear() except some control range information is still ///< kept. SSAControlRangeDict &control_range_dict(); ///< Return my control range dictionary. int num_data_ranges() const; ///< Return the number of data ranges created since my construction ///< or the last call to clear(). int num_poisoned_ranges() const; ///< Return the number of poisoned ranges created during the ///< last invocation of _get_range_ref(). virtual void print(ostream & o) const; ///< Print out the range dictionary. This operation is ///< essentially just a dump of the data structures of the ///< range dictionary. virtual void pretty_print(ostream & o, const Statement &stmt) const; ///< Print out the range dictionary in a more user-readable ///< manner. virtual Listable *listable_clone(void) const; virtual int structures_OK() const; ///< Methods required by Listable protected: virtual void _set_range(const Symbol &var, const Statement &stmt, Expression *range); ///< Not implemented. Will p_assert if called. virtual void _del_range(const Symbol &var, const Statement &stmt); ///< Not implemented. Will p_assert if called. virtual const Expression *_get_range_ref(const Symbol &var, const Statement &stmt); ///< Return the range associated with the given variable. If the ///< variable doesn't have an associated range, return 0; private: SSAProgramUnit *_pgm_ref; ///< Program unit for this range dict. Database<String, IntElem> *_stmt_toporder; ///< Topological ordering of the pgm's stmts. ExprSet _range_values; ///< All the values that ranges may take. Map<Statement, RefMap<Symbol, Expression> > _pgm_ranges; ///< Variable ranges for each statement ///< in the program. SSAControlRangeDict _control_ranges; ///< The control ranges of the program. Map<Symbol, Expression> _data_ranges; ///< Data ranges holding for each statement. ExprSet _poisoned_ranges; ///< Poisoned ranges holding for each ///< statement. Used only as a receptacle ///< for ownership of the poisoned ranges, ///< which are temporary. Map<Symbol, SSAFullRangeData> _pending_ranges; ///< Info on ranges currently being computed. int _timestamp; ///< Timestamp indicating current invocation ///< of _get_data_range_ref(). int _num_poisoned_ranges; ///< Number of poisoned ranges created ///< during last call to _get_range_ref. const Expression &_ins_data_range(const Symbol &var, Expression *range); void _order_args(SSAFullRangeData &data) const; SSAFullRangeData *_create_data(const Statement &stmt, int &df_num, RefList<SSAFullRangeData> &scc_node_stack); void _mark_data_as_computed(SSAFullRangeData &data); void _commit_data(SSAFullRangeData &data); void _delete_data(SSAFullRangeData &data); SSARangeOrData _probe_data_ranges(const Symbol &var, int &df_num, RefList<SSAFullRangeData> &scc_node_stack); void _calc_iter_order1(SSAFullRangeData &data, RefList<SSAFullRangeData> &iter_order_list); Array<SSAFullRangeData *> *_calc_iter_order(SSAFullRangeData &root_node); void _iterate_to_fixed_point_phase(const Array<SSAFullRangeData *> &toporder_to_stmt, const IntSet &start_stmts, bool widening_phase); void _iterate_to_fixed_point(SSAFullRangeData &root_node); const Expression *_get_data_range_ref(const Symbol &var, bool &is_poisoned); }; #endif

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