Polaris: AIRangeDict.h Source File

AIRangeDict.h Go to the documentation of this file. #ifndef _AI_RANGE_DICT_H #define _AI_RANGE_DICT_H /// /// file AIRangeDict.h /// /// \class AIRangeDict /// \brief Collection of ranges that were generated by abstract interpretation /// \defgroup Polaris /// \ingroup Polaris /// Range /// \see AIRangeDict.h /// \see AIRangeDict.h /// \see AIRangeDict.cc /// /// \endcode /// \section Overview Overview /// A AIRangeDict object is a repository for variable /// ranges for a program unit. AI stands for Abstract Interpretation, /// which is the method used to generate these ranges from the given /// program unit. /// /// \endcode /// \section Description Description /// A AIRangeDict object is a repository of the variable ranges /// for all points of a program unit. Abstract interpretation is /// used to compute these ranges. Abstract interpretation is a /// generalization of data flow analysis techniques. It computes the /// ranges by "executing" the given program unit at compile time, /// by following the control flow paths of the program, updating the /// current ranges to reflect the side effects of the statements /// encountered along these paths, until a fixed point is reached. /// See Blume and Eigenmann, "Symbolic Range Propagation", for more /// details. /// /// The computed ranges are stored in a collection of StmtRanges /// objects. Each StmtRanges object holds all the variable constraints /// for a single Statement in the program. /// /// \endcode /// \section Switches Switches /// By setting "range_block" to 1, the AIRangeDict constructor /// would automatically clear all ranges whenever it sees a BEGIN /// BLOCK or END BLOCK assertion when it is computing ranges. /// This switch should approximate the ranges computed for uninlined /// programs when run on a partially or fully inlined program. /// Basically, this switch causes the AIRangeDict to compute less /// accurate ranges for the sake of speed and memory used. /// /// Setting switch "pc_call_mods" to 1 causes the AIRangeDict /// constructor to assume that subroutine and function calls only /// modify thier arguments. That is, global varaibles and subroutine /// parameters are assumed to be unmodified by a subroutine call unless /// they also appear in that call's arguments. Results in more /// accurate ranges. May also result in incorrect ranges, if this /// assumption does not hold in actuality. /// /// \endcode /// \section Known Known bugs or limitations /// AIRangeDict objects can consume large amounts of time and large /// amounts of memory. This is because the time and space requirements /// are O(V*S), where S is the number of statements in a program and /// V is the number of integer variables in a program. (In actuality, /// V can be improved to be the average number of integer variables /// that have constraints.) /// #include "../Collection/Database.h" #include "../String.h" /// #include "RangeDict.h" #include "StmtRanges.h" /// class AIRangeDict : public RangeDict { friend class AbstractAccess; public: AIRangeDict(ProgramUnit &pgm, int debug = 0); AIRangeDict(const AIRangeDict &other); virtual ~AIRangeDict(); virtual AIRangeDict &operator = (const AIRangeDict &other); ///< Completely copy the contents of the other range dictionary ///< into myself. RefSet<Symbol> *range_vars(const String & tag) const; ///< Return the set of variables that have ranges for a ///< particular statement. virtual StmtRanges & _s_ranges(const String & tag); ///< Return a reference to the StmtRanges object associated with ///< the given statement tag. Expression * elim_known_facts(const String &, Expression *); ///< Accept a statement tag and a conditional expression ///< and use the range dictionary attached to the Statement ///< to eliminate tests from the conditional which are ///< known to be true within the dictionary. Works for ///< Fortran logical operators (.LE., .GT., etc) and for ///< MIN and MAX. 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); ///< Set the given variable to the given range. virtual void _del_range(const Symbol &var, const Statement &stmt); ///< Delete the range associated with the given variable. 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: Database<String,StmtRanges> _stmt_ranges; void _add_safe_cond_ranges(const ProgramUnit &pgm); void _generate_map(const ProgramUnit &pgm); }; #endif

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