Polaris: range_util.h Source File

range_util.h Go to the documentation of this file. #ifndef _RANGE_UTIL_H #define _RANGE_UTIL_H /// /// file range_util.h /// /// \class range_util /// \brief Routines for simplifying and manipulating ranges /// \defgroup Polaris /// \ingroup Polaris /// Range /// \see range_util.h /// \see range_util.h /// \see range_util.cc /// /// \endcode /// \section Overview Overview /// This file describes the interfaces to a variety of routines for /// simplifying and manipulating range expressions. These /// routines were designed to aid the implementation of the /// range propagation pass. However, many of them may also be useful /// to a user of the range propagation pass. /// /// By default, a NULL or omega expression are considered to be the /// unconstrained range ([-infinity:+infinity]). Because of this, /// routines that may return range expressions may also return NULL or /// Omega. /// class RangeAccessor; class StmtRanges; #include "../Collection/Map.h" #include "../Collection/Set.h" #include "../Expression/Expression.h" #include "../Symbol/Symbol.h" #include "RangeComparator.h" ///< Routines for combining and manipulating range expressions. ///< Description: ///< Compare the given pair of expressions, using the two given ///< comparators. Expression 1 is less than expression 2 if ///< it is indicated to be less than by both range comparaters. ///< Other relations are computed similarly. Relation compare(const Expression &expr1, RangeComparator &comparator1, const Expression &expr2, RangeComparator &comparator2); ///< Description ///< Extract and return all possible ranges from the given logical ///< expression. The given expression must be a logical expression ///< (i.e. made up of relation and .AND., .OR., and .NOT. operators) or ///< it will be ignored. If complement_expr is true, this method will ///< extract the ranges from the complement of this expression. Map< Symbol, Set<Expression> > * extract_ranges(const Expression &expr, bool complement_expr = False); ///< Description: ///< Return the intersection of the two ranges. That is, return the ///< range whose lower bound is the larger of the lower bounds of the ///< two given ranges, and whose upper bound is the smaller of the ///< upper bounds of the two given ranges. If one of the given ///< ranges is NULL, then that range is assumed to be [-Infinity:Infinity]. ///< Similarly, if the resulting range is the [-Infinity:Infinity], the ///< function returns NULL. Expression * intersect_ranges(const Expression *range1_ref, RangeComparator &comparator1, const Expression *range2_ref, RangeComparator &comparator2); ///< Description: ///< Return the union of the two ranges. That is, return the ///< range whose lower bound is the smaller of the lower bounds of the ///< two given ranges, and whose upper bound is the larger of the ///< upper bounds of the two given ranges. If one of the given ///< ranges is NULL, then that range is assumed to be [-Infinity:Infinity]. ///< Similarly, if the resulting range is the [-Infinity:Infinity], the ///< function returns NULL. Expression * union_ranges(const Expression *range1_ref, RangeComparator &comparator1, const Expression *range2_ref, RangeComparator &comparator2); ///< Description: ///< Perform a widening operator on the given expression and return the ///< result. If the lower bounds of the two given expressions are ///< equal, then the lower bound of the result will be this value, ///< otherwise the lower bound is -Infinity. The upper bound is ///< computed similarly. Expression * widen_range(const Expression *expr_ref, const Expression *widener_ref, RangeComparator &comparator); ///< Description: ///< Perform a narrowing operator on the given expression and return the ///< result. The lower and upper bounds will equal the lower and upper ///< bounds of the narrower_ref expression unless they are +-Infinity, ///< in which case would equal the lower and upper bounds of the given ///< expression. Expression * narrow_range(const Expression *expr_ref, const Expression *narrower_ref, RangeComparator &comparator); ///< Routines for handling intrinsic expressions. ///< Description: ///< Create a new MIN intrinsic with the given arguments. Expression * min_expr(Expression *e1, Expression *e2, const Symtab &symtab); ///< Description: ///< Create a new MAX intrinsic with the given arguments. Expression * max_expr(Expression *e1, Expression *e2, const Symtab &symtab); ///< Description: ///< Return true if the given expression is a MIN intrinsic bool is_min(const Expression &e); ///< Description: ///< Return true if the given expression is a MAX intrinsic bool is_max(const Expression &e); ///< Description: ///< Return true if the given expression is a MOD intrinsic bool is_mod(const Expression &e); ///< Description: ///< Return true if the given expression is a ABS intrinsic bool is_abs(const Expression &e); ///< Description: ///< Return true if the given expression is a MIN or MAX intrinsic bool is_min_or_max(const Expression &e); ///< Description: ///< Return true if the given expression contains a MIN or MAX intrinsic bool contains_min_or_max(const Expression &e); ///< Description: ///< Change a MIN intrinsic into a MAX intrinsic or vice_versa. void swap_min_max(Expression &e, const Symtab &symtab); ///< Description: ///< Convert any ABS expressions in the given expression to MAX expressions. Expression * abs_to_max(Expression *e, const Symtab &symtab); ///< Description: ///< Eliminate all terms of MIN or MAX subexpressions of the given ///< expression which can be proved to never be the minimum or maximum ///< value respectively. Expression * remove_redundant_min_max_terms(Expression *expr, RangeComparator &comparator); ///< Description: ///< Create a new MOD intrinsic with the given arguments. Expression * mod_expr(Expression *e1, Expression *e2, Symtab &symtab); ///< Printing out ranges. ///< Description: ///< Print the given range expression as an (in)equality for the ///< given variable void pretty_print_range(ostream &o, const Expression &expr, const Symbol &var); ///< Routines for simplifying expressions containing RangeExprs. ///< ///< Meant for internal use of RangeComparator. Shouldn't be used ///< externally. enum RANGE_HANDLING { TAKE_RANGE_MIN, TAKE_RANGE_MAX, KEEP_WHOLE_RANGE }; ///< Description: ///< Pull the range subexpressions out of the expression. The ///< range_handling argument describes exactly how this is done. ///< TAKE_RANGE_MIN: Generate the smallest possible value of the ///< expression. (e.g. 2*[1:A]+B --> 2+B) ///< TAKE_RANGE_MAX: Generate the largest possible value of the ///< expression. (e.g. 2*[1:A]+B --> 2*A+B) ///< KEEP_WHOLE_RANGE: Pull the ranges out so that they are outermost. ///< (e.g. 2*[1:A]+B --> [2+B:2*A+B]) ///< If ranges couldn't be pulled out by the expression, or if the ///< resulting expression becomes unconstrained, the returned ///< expression is omega. Warning, ownership of the given expression ///< is passed to this routine. Expression * pull_ranges_out(Expression * e, RangeComparator &comparator, RANGE_HANDLING range_handling = KEEP_WHOLE_RANGE); ///< Description: ///< Pull all MIN or MAX intrinsics to the top levels of the expression. Expression * pull_min_max_out(Expression *e, RangeComparator &comparator); Expression * elim_known_facts (Expression *e, RangeComparator &comparator); void copy_expr_ranges (Expression & expr, RangeAccessor & r_acc, StmtRanges & ranges); void apply_limits(Expression & expr, Expression * lower, Expression * upper, StmtRanges & ranges, RefSet<Symbol> &set); void set_ranges_for_symbol(Expression & expr, const Symbol & sym, StmtRanges & ranges); void tighten_lower_bound(Expression & expr, const Expression * lower, StmtRanges & ranges, RefSet<Symbol> & set); void tighten_upper_bound(Expression & expr, const Expression * upper, StmtRanges & ranges, RefSet<Symbol> & set); #endif

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