Polaris: GSAFullRangeDict.h Source File

GSAFullRangeDict.h Go to the documentation of this file. #ifndef _GSA_FULL_RANGE_DICT_H #define _GSA_FULL_RANGE_DICT_H /// /// file GSAFullRangeDict.h /// /// \class GSAFullRangeDict /// \brief Collection of ranges extracted from GSA program's control flow /// \defgroup Polaris /// \ingroup Polaris /// Range /// \see GSAFullRangeDict.h /// \see GSAFullRangeDict.h /// \see GSAFullRangeDict.cc /// /// \endcode /// \section Overview Overview /// An GSAFullRangeDict object is a repository for variable /// ranges for a program unit in GSA form. Ranges derived from /// both data flow and control flow are collected, (unlike /// GSAControlRangeDict.h). /// /// \endcode /// \section Description Description /// An GSAFullRangeDict object is a repository of the variable /// ranges for all points of a program unit in GSA 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. /// /// GSAFullRangeDict 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 GSA form can be found in Blume and Eigenmann, "Demand- /// Driven Symbolic Range Propagation". /// #ifdef POLARIS_GNU_PRAGMAS #pragma interface #endif /// #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 "GSAControlRangeDict.h" #include "GSAFullRangeData.h" #include "ExprSet.h" /// class IntSet; class GSAFullRangeDict : public RangeDict { friend class GSAFullRangeData; public: GSAFullRangeDict(ProgramUnit &pgm, int debug = 0); virtual ~GSAFullRangeDict(); 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. GSAControlRangeDict &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: ProgramUnit *_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. GSAControlRangeDict _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, GSAFullRangeData> _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(GSAFullRangeData &data) const; GSAFullRangeData *_create_data(const Statement &stmt, int &df_num, RefList<GSAFullRangeData> &scc_node_stack); void _mark_data_as_computed(GSAFullRangeData &data); void _commit_data(GSAFullRangeData &data); void _delete_data(GSAFullRangeData &data); GSARangeOrData _probe_data_ranges(const Symbol &var, int &df_num, RefList<GSAFullRangeData> &scc_node_stack); void _calc_iter_order1(GSAFullRangeData &data, RefList<GSAFullRangeData> &iter_order_list); Array<GSAFullRangeData *> *_calc_iter_order(GSAFullRangeData &root_node); void _iterate_to_fixed_point_phase(const Array<GSAFullRangeData *> &toporder_to_stmt, const IntSet &start_stmts, bool widening_phase); void _iterate_to_fixed_point(GSAFullRangeData &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:05:54 2005