Polaris: RangeComparator.h Source File

RangeComparator.h Go to the documentation of this file. /// /// /// file ConstraintDict.h /// #ifndef _RANGE_COMPARATOR_H #define _RANGE_COMPARATOR_H /// /// \class RangeComparator /// \brief Base class implementing comparison methods. /// \defgroup Polaris /// \ingroup Polaris /// Range /// \see RangeComparator.h /// \see RangeComparator.h /// \see RangeComparator.cc /// /// \endcode /// \section Overview Overview /// A RangeComparator object implements most of the basic comparison /// and modification operators that are useful for using ranges. /// /// \endcode /// \section Description Description /// RangeComparator is an abstract class that offers a variety of /// methods for comparing expressions and for high level modifications /// of ranges. The two most important methods in this class is /// compare() and sign(), which compare expressions. The compare() /// method returns the inequality relationships that hold between the /// two given expressions, using the constraints imposed by the ranges /// "contained" within myself. The sign() method determines whether /// an expression is always positive or negative, again using these /// ranges. /// /// This class also offers some methods to modify expressions, using my /// ranges. All these methods eliminate undesirable variables or /// subexpressions by replacing them with ranges. Method /// subst_var_and_simplify() replaces a variable in the expression with /// its range and simplifies it down. Method eliminate_vars() is /// similar, except it replaces several variables. Method /// remove_truncates_with_var() is used to remove expressions of /// the form B*(A/B). /// /// Several functions are provided to access or modify ranges contained /// within myself. Method get_range_ref() gets the range for a /// given variable, method set_range() modifies the variable's range, /// and method del_range() deletes it. Methods union_range() and /// intersect_range() modify a given variable's range by unioning or /// intersecting it with the given range. /// /// By default, a NULL or omega expression are considered to be the /// unconstrained range ([-infinity:+infinity]). Because of this, /// methods that may return range expressions may also return NULL or /// Omega. /// /// A variety of functions that manipulate range expressions can be /// found in range_util.h. /// /// The RangeComparator class is abstract because the class does not /// specify how the ranges it uses are stored within it. A subclass /// of RangeComparator must declare such data structures as well /// as instantiate the pure methods set_range(), get_range_ref(), /// and del_range() to access these data structures. The subclass /// must also instantiate the method listable_clone(). /// /// The compare() method compares two expressions by taking the /// difference between the two expressions, then repeated substituting /// each variable in the difference with the variable's range until /// the lower bound of the difference is a positive integer or /// the upper bound is a negative integer. At this point, the /// inequality relationships between the two expressions can be /// determined by examining these integer bounds. A more complete /// description of the expression comparison algorithm can be found /// in Blume and Eigenmann "Symbolic Range Propagation". /// /// \endcode /// \section Known Known bugs or limitations /// Because this class creates expressions containing intrinsics /// (e.g., MIN, MAX, MOD), this class needs access to the symbol table /// to create symbols for these intrinsics. Because of this, the /// user must pass the symbol table to the constructors of this class. /// #include "../Listable.h" #include "../Collection/Map.h" #include "../Collection/RefSet.h" #include "../Symbol/Symbol.h" #include "../Expression/Expression.h" #include "../IntElem.h" /// class Symtab; class RangeExpr; #include "Relation.h" #include "ExprSet.h" enum EXPR_SIGN { POS_EXPR, ///< Expr. spans over only positive values NEG_EXPR, ///< Expr. spans over only negative values POS_NEG_EXPR, ///< Expr. spans over positive or negative values ZERO_EXPR, ///< Expr. is zero UNKNOWN_SIGN, ///< Sign is unknown (Used internally) PENDING ///< Sign is being calculated (Used internally) }; ///< Internal class used to collect information used by the compare ///< method. Each variable has its own CompareData object. class CompareData : public Listable { public: int num_subst; ///< Number of substitutions performed by ///< unfinished compares for this varianble. EXPR_SIGN sign_cache; ///< Cached sign of the variable. CompareData(); CompareData(const CompareData &other); virtual ~CompareData(); virtual Listable *listable_clone() const; virtual int structures_OK() const; virtual void print(ostream &o) const; }; class RangeComparator : public Listable { public: RangeComparator(const Symtab &symtab); RangeComparator(const RangeComparator &other); virtual ~RangeComparator(); ///< Methods for comparing expressions. virtual Relation compare(const Expression &e1, const Expression &e2); ///< Return the algebraic relationship between the two expressions, ///< taking my ranges into account. virtual Relation compare(const Expression &e1, int value); ///< Return the algebraic relationship between the given expression ///< and the integer value, taking Ranges into account. EXPR_SIGN sign(const Expression &e); ///< Return the sign of the expression. One of three values may be ///< returned: POS_EXPR, NEG_EXPR, and POS_NEG_EXPR, which means that ///< the sign is positive, negative, or unknown respectively. EXPR_SIGN signz(const Expression &e); ///< Like sign() but may also return ZERO_EXPR when the expression ///< equals zero. void subst_in_ranges(const Symbol &var, const Expression *subst_expr); ///< Replace all uses of variable var in all of the ranges in myself ///< with the given substitution expression. If subst_expr is NULL, ///< the variable references are instead replaced by an unconstrained ///< range. ([-Inf:Inf]) ///< Methods for modifying or accessing ranges inside myself. virtual void set_range(const Symbol &var, Expression *range) = 0; ///< Set the given variable to the given range. virtual void del_range(const Symbol &var) = 0; ///< Delete the range associated with the given variable. virtual const Expression *get_range_ref(const Symbol &var) = 0; ///< Return the range associated with the given variable. If the ///< variable doesn't have an associated range, return 0; void intersect_range(const Symbol &var, const Expression &inter_expr); ///< Intersect my range of the given variable with the given range. void union_range(const Symbol &var, const Expression &union_expr, RangeComparator *union_comparator_ref = 0); ///< Union my range of the given variable with the given range. ///< Methods for modifying given expressions, using my ranges. Expression *subst_var_and_simplify(Expression *e, const Symbol &var, const Expression *subst_expr); ///< Substitute all occurrences of the given variable in the given ///< expression with the given substitution expression. Then, simplify ///< the resulting expression using the constraint information within ///< myself. If subst_expr = NULL, use the unconstrained range ///< ([-Inf:Inf]) as the substitution expression. Expression *eliminate_vars(Expression *e, const RefSet<Symbol> *vars_to_eliminate); ///< Eliminate all variables in the given expression by replacing ///< these variables with their ranges. If vars_to_eliminate == NULL, ///< then all variables are eliminated. Expression * remove_truncates_with_var(Expression *e, const Symbol &var); ///< Remove all subexpressions of the form B*(A/B) and that contain ///< the given variable from the given expression. These expressions ///< are removed by replacing the expressions with a range, ///< (e.g., B*(A/B) --> [A-B+1:A] if B > 0), then simplifying the ///< resulting expressions down. ///< Methods that modify/access the way I function. void range_join_accuracy(int acc); ///< Determines the accuracy of unions or intersections of two ranges. ///< Suppose that B and C are not comparable for the two ranges [A:B] ///< and [A:C]. ///< range_join_accuracy union intersection ///< 0 [A:+Infty] [A:B] ///< 1 [A:+Infty] [A:min(B,C)] ///< 2 [A:max(B,C)] [A:min(B,C)] ///< Default is read from switch "range_acc" int range_join_accuracy(); ///< Return the range join accuracy. void range_compare_accuracy(int acc); ///< Determines the accuracy of the expression comparison routines. ///< The higher the number, the more powerful and more expensive range ///< substitution algorithm used. ///< Value Range substition algorithm ///< 0 Simple range substitution scheme. ///< 1 Exact lower/upper bounds determined for monotonic expressions. ///< 2 Exact lower/upper bounds determined for quadratic expressions. ///< 3 Exact subst. algs. above may be called recursively. ///< Default is 1. int range_compare_accuracy(); ///< Return the range compare accuracy. ///< Miscellaneous methods. RangeComparator &operator = (const RangeComparator &other); ///< Completely copy the contents of the other range comparator ///< into myself. const Symtab &symtab() const; ///< Return the symbol table associated with myself int debug_level() const; void debug_level(int level); ///< Access the debugging level of myself. Higher debugging levels ///< generate greater amounts of debugging output. A debug level of ///< 0, which is default, indicates no debugging output. virtual void print(ostream &o) const; virtual int structures_OK() const; ///< Support methods for Listable.h. Note: listable clone is ///< missing. Subclasses must provide it. protected: int _debug_level; void _flush_sign_caches(); ///< Flush out the saved sign for the all variables. Should be ///< called whenever a variable's range changes. private: Map<Symbol,CompareData> _compare_info; const Symtab *_symtab_ref; bool _use_the_big_guns; ///< Use the more powerful but more expensive ///< range substitution techniques. int _range_join_accuracy; ///< Accuracy to union and intersect ranges int _range_compare_accuracy; ///< Accuracy to perform comparisons. int _cache_expr_signs; ///< Nonzero if should cache computed expr signs ExprSet _cached_sign_exprs; ///< Set of exprs whose signs have been cached Map<Expression,IntElem> _cached_expr_signs; ///< Signs for previously tested exprs. CompareData &_compare_data(const Symbol &var); Expression *_build_delta(const Expression &e1, const Expression &e2); Relation _compare(Expression * delta); void _extract_ranges(Expression &expr); Expression *_solve_monotonic(Expression *expr, const Symbol &var, const RangeExpr &subst_range); Expression *_find_quad_range(const Expression &e, const Symbol &var, const RangeExpr &subst_range); Expression *_eliminate_quads(Expression *expr, const Symbol &var, const RangeExpr &subst_range); Expression *_solve_for_range(Expression *expr, const Symbol &var, const RangeExpr &subst_range); Expression *_remove_truncates(Expression *expr, const Symbol &var); void _begin_caching_expr_signs(); void _end_caching_expr_signs(); }; ///< Description: ///< Return the complement of the given sign. (POS_EXPR <--> NEG_EXPR). EXPR_SIGN flip_sign(EXPR_SIGN sign); ///< Description: ///< Tell the RangeComparator class to start collecting statistics. void collect_range_stats(); ///< Description: ///< Tell the RangeComparator class to stop collecting statistics. void stop_range_stats(); ///< Description: ///< Print out the statistics collected so far. void print_range_stats(ostream &o); #endif

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