range_util.cc File Reference
Go to the source code of this file.
|
Functions |
| static int | min (int a, int b) |
| static Expression * | _pull_min_max_out_top (Expression *e, RangeComparator &comparator) |
| | pull_min_max_out_top Pull all MIN or MAX intrinsics to the top levels of the expression.
|
| static Expression * | _elim_known_facts (Expression *e, RangeComparator &comparator) |
| | _elim_known_facts Recursive function that does most of the work of elim_known_facts above.
|
| static Expression * | _handle_range (RangeExpr *range, RANGE_HANDLING range_handling) |
| | _handle_range Return the desired component of the range, as indicated by the range_handling flag.
|
| static void | _swap_range_args (RangeExpr &range) |
| | _swap_range_args Swap the lower and upper bounds of the given range_expression
|
| static void | _negate_range (RangeExpr &range) |
| | _negate_range Negate the given range.
|
| static Expression * | _p_r_o_of_add (Expression *e) |
| | _p_r_o_of_add Convert an addition expression whose arguments contain ranges into a range expression.
|
| static Expression * | _range_bound_multiply (Expression *e1, Expression *e2) |
| | _range_bound_multiply Multiply the two expressions and return the result.
|
| static Expression * | _mult_range_with_expr (RangeExpr *r, Expression *e, RangeComparator &comparator) |
| | _mult_range_with_expr Multiply the given range with the given non-range Expression and return the result.
|
| static RangeExpr * | _merge_range_mult_terms (Expression &e, RangeComparator &comparator) |
| | _merge_range_mult_terms Pull all the range terms of the given multiply expression, multiply them togethor and return the result.
|
| static Expression * | _p_r_o_of_mult (Expression *e, RangeComparator &comparator) |
| | _p_r_o_of_mult Pull the range out of a multiply statement.
|
| static Expression * | _p_r_o_of_divide (Expression *e, RangeComparator &comparator) |
| | _p_r_o_of_divide Pull the range out of a divide statement.
|
| static Expression * | _p_r_o_of_exp (Expression *e, RangeComparator &comparator) |
| | _p_r_o_of_exp Pull the range out of an exponentiation statement.
|
| static Expression * | _p_r_o_of_range (Expression *e) |
| | _p_r_o_of_range Pull the range out of a range expression
|
| static Expression * | _p_r_o_of_min_max (Expression *e, bool is_min_op) |
| | _p_r_o_of_min_max(Expression *e) Pull the range out of the MIN or MAX intrinsic operator.
|
| static Expression * | _p_r_o_of_ifix (Expression *e) |
| | _p_r_o_of_ifix Convert an IFIX intrinsic expression whose argument is a range into a range expression.
|
| static Expression * | _min_abs_expr (const Expression &e, EXPR_SIGN sign) |
| | _min_abs_expr Calculate and return the smallest absolute value for the given range.
|
| static Expression * | _max_abs_expr (const Expression &e, EXPR_SIGN sign) |
| | _max_abs_expr Calculate and return the smallest absolute value for the given range.
|
| static Expression * | _handle_omega_in_mod (Expression *e, RangeComparator &comparator) |
| | _handle_omega_in_mod Generate the proper range for an MOD intrinsic that contains
|
| static Expression * | _p_r_o_of_mod (Expression *e, RangeComparator &comparator) |
| | _p_r_o_of_mod Pull ranges out of a MOD intrinsic expression.
|
| static Expression * | _p_r_o_of_abs (Expression *e, RangeComparator &comparator) |
| | _p_r_o_of_abs Pull ranges out of an ABS intrinsic expression.
|
| static Expression * | _pull_ranges_out (Expression *e, RangeComparator &comparator, RANGE_HANDLING range_handling) |
| | _pull_ranges_out Recursive function that does most of the work of pull_ranges_out above.
|
| Expression * | pull_ranges_out (Expression *e, RangeComparator &comparator, RANGE_HANDLING range_handling GIV(KEEP_WHOLE_RANGE)) |
| | pull_ranges_out Pull the range subexpressions out of the expression.
|
| 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.
|
| Expression * | mod_expr (Expression *e1, Expression *e2, Symtab &symtab) |
| | Description: Print the given range expression as an (in)equality for the given variable.
|
| 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.
|
| 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.
|
| void | swap_min_max (Expression &e, const Symtab &symtab) |
| | Description: Convert any ABS expressions in the given expression to MAX expressions.
|
| static void | _append_list (List< Expression > &to, List< Expression > &from) |
| | _append_to_list Grab and append all elements of list from to list to
|
| static Expression * | _join_nonbinary_exprs (OP_TYPE op, Expression *e1, Expression *e2) |
| | _join_nonbinary_exprs Create a new nonbinary expression of the given op type.
|
| static void | _pull_in_add_expr (Expression &min_or_max, const Expression &add_term) |
| | _pull_in_add_expr Add the given expression to the arguments of the given min or max intrinsic.
|
| static Expression * | _p_mm_o_of_add (Expression *e) |
| | _p_mm_o_of_add Pull the min or max expressions out to the top level of the add expression.
|
| static void | _pull_in_mult_expr (Expression &min_or_max, const Expression &mult_term, EXPR_SIGN mult_term_sign, RangeComparator &comparator) |
| | _pull_in_mult_expr Add the given expression to the arguments of the given min or max intrinsic.
|
| static Expression * | _p_mm_o_of_mult (Expression *e, RangeComparator &comparator) |
| | _p_mm_o_of_mult Pull the min or max intrinsics to the outermost part of the given multiplication expression.
|
| static void | _pull_in_div_expr (Expression &min_or_max, const Expression &denom, EXPR_SIGN denom_sign, const Symtab &symtab) |
| | _pull_in_div_expr Add the given expression to the arguments of the given min or max intrinsic.
|
| static Expression * | _p_mm_o_of_divide (Expression *e, RangeComparator &comparator) |
| | _p_mm_o_of_divide Pull the min/max intrinsics out of a divide statement.
|
| static void | _pull_in_exp_expr (Expression &min_or_max, int power, EXPR_SIGN base_sign, const Symtab &symtab) |
| | _pull_in_exp_expr Add the given expression to the arguments of the given min or max intrinsic.
|
| static Expression * | _p_mm_o_of_exp (Expression *e, RangeComparator &comparator) |
| | _p_mm_o_of_exp Pull the min/max intrinsics out of an exponentiation statement.
|
| Expression * | pull_min_max_out (Expression *e, RangeComparator &comparator) |
| | pull_min_max_out Pull all MIN or MAX intrinsics to the top levels of the expression.
|
| Expression * | remove_redundant_min_max_terms (Expression *expr, RangeComparator &comparator) |
| | Description: Create a new MOD intrinsic with the given arguments.
|
| static bool | _delete_expr_in_list (Expression &expr, List< Expression > &list) |
| | delete_expr_in_list Determine whether the given expression equals an expression in the given list.
|
| static Expression * | _pull_out_common_min_max1 (Expression *&expr1, Expression *&expr2, bool pull_out_max) |
| | _pull_out_common_min_max Pull out any common terms of the max expressions in the two range's lower bounds and pull out any common terms in the min expressions in the upper bounds and return the range containing these common terms.
|
| static RangeExpr * | _pull_out_common_min_max (RangeExpr &range1, RangeExpr &range2) |
| static RangeExpr * | _join_ranges (RangeExpr *range1, RangeExpr *range2, const Symtab &symtab) |
| | join_ranges Form the intersection of the two given ranges without any tests.
|
| Expression * | intersect_ranges (const Expression *range1_ref, RangeComparator &comparator1, const Expression *range2_ref, RangeComparator &comparator2) |
| | Description: Return the union of the two ranges.
|
| 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.
|
| 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.
|
| Expression * | narrow_range (const Expression *expr_ref, const Expression *narrow_ref, RangeComparator &comparator) |
| | Description: Create a new MIN intrinsic with the given arguments.
|
| Relation | compare (const Expression &e1, RangeComparator &c1, const Expression &e2, RangeComparator &c2) |
| | Description Extract and return all possible ranges from the given logical expression.
|
| static OP_TYPE | _negate_rel_op (OP_TYPE rel_op) |
| | _negate_rel_op Return the inverse of the given relational operator.
|
| static Expression * | _remove_div (Expression *expr, int &factor, bool take_max) |
| | _remove_divs_from_term -- Remove all integer divisions from the given expression and return the term.
|
| static Expression * | _remove_divs_from_term (Expression *expr, int &factor, bool take_max) |
| static void | _remove_divs_from_rel (Expression &expr) |
| | _remove_divs_from_rel -- Multiply out all integer divisions from the given comparison expression.
|
| static void | _extract_a_range (const Expression &var_term, OP_TYPE rel_op, const Expression *other_terms, Map< Symbol, Set< Expression > > &ranges) |
| | _extract_a_range -- Extract and returns a single range from a binary relation.
|
| static void | _extract_ranges_rel (Expression &expr, Map< Symbol, Set< Expression > > &ranges) |
| | _extract_ranges_rel -- Extract all ranges from a binary relation.
|
| void | _extract_ranges (Expression &expr, Map< Symbol, Set< Expression > > &ranges) |
| | _extract_ranges
|
| Map< Symbol, Set< Expression > > * | extract_ranges (const Expression &expr, bool complement_expr GIV(false)) |
| | extract_ranges
|
| void | pretty_print_range (ostream &o, const Expression &expr, const Symbol &var) |
| | Routines for simplifying expressions containing RangeExprs.
|
| Expression * | elim_known_facts (Expression *e, RangeComparator &comparator) |
| | elim_known_facts
|
| static Boolean | is_scalar_id (const Expression &expr) |
| void | copy_expr_ranges (Expression &expr, RangeAccessor &orig_ranges, StmtRanges &new_ranges) |
| static Boolean | is_ID_OP (const Expression &expr) |
| void | apply_limits (Expression &expr, Expression *lower, Expression *upper, StmtRanges &ranges, RefSet< Symbol > &set) |
| | This routine checks expr for containing exactly one variable, and if it does, applies the [lower:upper] range to it.
|
| void | set_ranges_for_symbol (Expression &expr, const Symbol &sym, StmtRanges &ranges) |
| | This routine extracts ranges for a particular symbol from an expression and sets them in the given StmtRanges object.
|
| void | tighten_upper_bound (Expression &expr, const Expression *upper, StmtRanges &ranges, RefSet< Symbol > &set) |
| void | tighten_lower_bound (Expression &expr, const Expression *lower, StmtRanges &ranges, RefSet< Symbol > &set) |
Detailed Description
Definition in file range_util.cc.
Function Documentation
| static int min |
( |
int |
a, |
|
|
int |
b |
|
) |
[inline, static] |
|
|
|
pull_min_max_out_top Pull all MIN or MAX intrinsics to the top levels of the expression.
... Handle the base cases. (Expression leaves and ranges.)
... Pull out the min's or max's from the expression's arguments.
... Pull out the min or max expressions from the expression itself.
... Do nothing
Definition at line 1847 of file range_util.cc.
References _p_mm_o_of_add(), _p_mm_o_of_divide(), _p_mm_o_of_exp(), _p_mm_o_of_mult(), ADD_OP, Expression::arg_list(), Iterator< T >::current(), DIV_OP, e, List< T >::entries(), EXP_OP, is_min_or_max(), MULT_OP, Expression::op(), and Iterator< T >::valid().
Referenced by _pull_ranges_out(), and pull_min_max_out(). |
|
|
_elim_known_facts Recursive function that does most of the work of elim_known_facts above.
This routine recursively examines the given expression and whenever it finds a piece that it can eliminate based on Range information, it does that.
Whenever it finds a relational expression, uses the RangeComparator to determine whether the expression is true or false or unknown. If it is true, the expression is replaced by .TRUE. Whenever it is false, the expression is replaced by .FALSE. . Whenever it is unknown, the expression is unchanged.
Whenever if finds a MAX or MIN expression inside, it compares the two arguments and if it can determine a clear relationship between the two (based on the Range info), it replaces the intrinsic call accordingly.
... Is this a MIN intrinsic?
... Is this a MAX intrinsic?
Definition at line 2799 of file range_util.cc.
References Expression::arg_list(), Mutator< T >::assign(), Expression::clone(), Expression::compare(), constant(), e, EQ_OP, GE_OP, GT_OP, Relation::is_equal(), Relation::is_greater_equal(), Relation::is_greater_than(), Relation::is_less_equal(), Relation::is_less_than(), is_max(), is_min(), Relation::is_not_equal(), is_relational_op(), LE_OP, LT_OP, NE_OP, Expression::op(), Expression::parameters_guarded(), Expression::parameters_valid(), Mutator< T >::pull(), and Iterator< T >::valid().
Referenced by elim_known_facts(). |
| static void _swap_range_args |
( |
RangeExpr & |
range |
) |
[static] |
|
| static void _negate_range |
( |
RangeExpr & |
range |
) |
[static] |
|
|
|
_p_r_o_of_add Convert an addition expression whose arguments contain ranges into a range expression.
silvius: not sure how to fix this cleanly, but it breaks on [0:Inf]+[0:Inf]
cerr<<"\n *e= "<<*e<<"\t*_u_f= "<<*_ugly_fix_l<<", "<<*_ugly_fix_u;
cerr<<"\nBug fix for function _p_r_o_of_add("<<*e<<").";
silvius: it also breaks on [0:Inf]+(-1)*ABS(biga)
cerr<<"\nBug fix for function _p_r_o_of_add("<<*e<<").";
silvius: it also breaks on 1+[-Inf:0]
... cerr<<"\nBug fix for function _p_r_o_of_add("<<*e<<").";
end silvius fix
Definition at line 116 of file range_util.cc.
References add(), ADD_OP, Expression::arg_list(), DistributeExpr::clone(), Expression::clone(), RangeExpr::clone(), constant(), Iterator< T >::current(), Type::data_type(), e, List< T >::entries(), RangeExpr::grab_lb(), RangeExpr::grab_ub(), RangeExpr::has_lb(), RangeExpr::has_ub(), infinity(), INFINITY_OP, INTEGER_TYPE, is_integer_one(), RangeExpr::lb(), Mutator< T >::modify(), Expression::op(), RANGE_OP, Expression::sign(), simplify(), Expression::type(), RangeExpr::ub(), and Iterator< T >::valid().
Referenced by _mult_range_with_expr(), and _pull_ranges_out(). |
|
|
_range_bound_multiply Multiply the two expressions and return the result.
Return 0 if the expression turns out to be infinite or undefined.
Definition at line 226 of file range_util.cc.
References Expression::arg_list(), List< T >::entries(), List< T >::grab(), INFINITY_OP, List< T >::ins_first(), List< T >::ins_last(), INTEGER_CONSTANT_OP, List< T >::last_ref(), mul(), MULT_OP, OMEGA_OP, and Expression::value().
Referenced by _merge_range_mult_terms(), and _mult_range_with_expr(). |
|
|
_mult_range_with_expr Multiply the given range with the given non-range Expression and return the result.
Return 0 if the result is infinite or undefined.
... Determine the sign of the expression.
... Quit if the sign of the non-range arguments cannot be determined.
... Handle folded expressions (e.g. [a:b]*(c+d)) as a special case. ... Rather than quitting, distribute the expression and try again.
... Couldn't determine sign, so give up.
... Multiply the range with the nonrange arguments.
Definition at line 274 of file range_util.cc.
References _p_r_o_of_add(), _range_bound_multiply(), _swap_range_args(), ADD_OP, Expression::arg_list(), Mutator< T >::assign(), DistributeExpr::clone(), e, INFINITY_OP, NEG_EXPR, OMEGA_OP, Expression::op(), POS_NEG_EXPR, Mutator< T >::pull(), RANGE_OP, Expression::sign(), and Iterator< T >::valid().
Referenced by _merge_range_mult_terms(), and _p_r_o_of_mult(). |
|
|
_merge_range_mult_terms Pull all the range terms of the given multiply expression, multiply them togethor and return the result.
Return 0 if the result turns out to be infinite or undefined.
... range_sign == NEG_EXPR
... range_prod_sign = NEG_EXPR
... range_sign == NEG_EXPR
Definition at line 349 of file range_util.cc.
References _mult_range_with_expr(), _range_bound_multiply(), Expression::arg_list(), RangeExpr::clone(), Iterator< T >::current(), e, Set< T >::entries(), flip_sign(), Set< T >::grab(), Mutator< T >::grab(), RangeExpr::grab_lb(), RangeExpr::grab_ub(), RangeExpr::has_lb(), RangeExpr::has_ub(), Set< T >::ins(), RangeExpr::lb(), MULT_OP, NEG_EXPR, Expression::op(), POS_EXPR, POS_NEG_EXPR, RANGE_OP, Expression::sign(), RangeExpr::ub(), and Iterator< T >::valid().
Referenced by _p_r_o_of_mult(). |
|
|
_p_r_o_of_divide Pull the range out of a divide statement.
... Couldn't determine sign, so give up.
... Couldn't determine sign, so give up.
Definition at line 499 of file range_util.cc.
References _swap_range_args(), Expression::clone(), constant(), div(), e, RangeExpr::grab_lb(), Expression::grab_left(), Expression::grab_right(), RangeExpr::grab_ub(), RangeExpr::has_lb(), RangeExpr::has_ub(), RangeExpr::lb(), Expression::left_guarded(), NEG_EXPR, Expression::op(), POS_EXPR, POS_NEG_EXPR, RANGE_OP, Expression::right_guarded(), Expression::sign(), RangeExpr::ub(), and ZERO_EXPR.
Referenced by _pull_ranges_out(). |
|
|
_p_r_o_of_exp Pull the range out of an exponentiation statement.
... Power is even.
... lb and ub are both positive, so abs(lb) <= abs(ub).
... lb and ub are both negative, so abs(lb) >= abs(ub).
... Compare abs(lb) == -lb with abs(ub) == ub.
... abs(lb) <= abs(ub).
... abs(lb) >= abs(ub).
Definition at line 578 of file range_util.cc.
References _swap_range_args(), add(), Expression::clone(), constant(), e, exponent(), RangeExpr::grab_lb(), Expression::grab_left(), RangeExpr::grab_ub(), RangeExpr::has_lb(), RangeExpr::has_ub(), INTEGER_CONSTANT_OP, RangeExpr::lb(), Expression::left_guarded(), NEG_EXPR, OMEGA_OP, Expression::op(), POS_EXPR, RANGE_OP, Expression::right_guarded(), Expression::sign(), simplify(), RangeExpr::ub(), and Expression::value().
Referenced by _pull_ranges_out(). |
|
|
_p_r_o_of_min_max(Expression *e) Pull the range out of the MIN or MAX intrinsic operator.
Definition at line 688 of file range_util.cc.
References Expression::arg_list(), DistributeExpr::clone(), Iterator< T >::current(), Mutator< T >::del(), e, List< T >::entries(), RangeExpr::grab_lb(), RangeExpr::grab_ub(), RangeExpr::has_lb(), RangeExpr::has_ub(), Mutator< T >::modify(), OMEGA_OP, Expression::op(), Expression::parameters_guarded(), RANGE_OP, and Iterator< T >::valid().
Referenced by _pull_ranges_out(). |
|
|
_min_abs_expr Calculate and return the smallest absolute value for the given range.
Definition at line 775 of file range_util.cc.
References DistributeExpr::clone(), Expression::clone(), constant(), e, RangeExpr::lb(), OMEGA_OP, Expression::op(), POS_EXPR, POS_NEG_EXPR, RANGE_OP, RangeExpr::ub(), and unary_minus().
Referenced by _p_r_o_of_mod(). |
|
|
_max_abs_expr Calculate and return the smallest absolute value for the given range.
... We don't want to do a compare() here because we may go into ... an infinite recursive loop.
Definition at line 803 of file range_util.cc.
References DistributeExpr::clone(), Expression::clone(), e, RangeExpr::has_lb(), RangeExpr::has_ub(), INTEGER_CONSTANT_OP, RangeExpr::lb(), NEG_EXPR, OMEGA_OP, Expression::op(), POS_EXPR, POS_NEG_EXPR, RANGE_OP, simplify(), sub(), RangeExpr::ub(), unary_minus(), and Expression::value().
Referenced by _handle_omega_in_mod(), _p_r_o_of_abs(), and _p_r_o_of_mod(). |
|
|
_handle_omega_in_mod Generate the proper range for an MOD intrinsic that contains
Definition at line 873 of file range_util.cc.
References _max_abs_expr(), add(), Expression::arg_list(), Expression::clone(), constant(), convert_to_range(), e, List< T >::entries(), List< T >::first_ref(), List< T >::grab(), INFINITY_OP, is_integer_zero(), List< T >::last_ref(), RangeExpr::lb(), OMEGA_OP, Expression::op(), Expression::parameters_guarded(), POS_EXPR, POS_NEG_EXPR, Expression::sign(), RangeExpr::ub(), and unary_minus().
Referenced by _p_r_o_of_mod(), and _pull_ranges_out(). |
|
|
_p_r_o_of_mod Pull ranges out of a MOD intrinsic expression.
... Return A if max(|A|) < min(|B|) for the expression mod(A, B) ... Note: mod(A, B) < 0 iff A < 0.
... Otherwise, return [0:B-1] for the expression mod(A, B).
Definition at line 936 of file range_util.cc.
References _handle_omega_in_mod(), _max_abs_expr(), _min_abs_expr(), Expression::arg_list(), Expression::compare(), constant(), e, List< T >::entries(), List< T >::first_ref(), List< T >::grab(), Relation::is_less_than(), List< T >::last_ref(), List< T >::modify(), omega(), Expression::op(), Expression::parameters_guarded(), POS_EXPR, POS_NEG_EXPR, RANGE_OP, Expression::sign(), sub(), unary_minus(), and ZERO_EXPR.
Referenced by _pull_ranges_out(). |
|
|
_p_r_o_of_abs Pull ranges out of an ABS intrinsic expression.
Definition at line 1003 of file range_util.cc.
References _max_abs_expr(), _negate_range(), Expression::arg_list(), constant(), e, List< T >::first_ref(), List< T >::grab(), NEG_EXPR, Expression::parameters_guarded(), POS_EXPR, POS_NEG_EXPR, and Expression::sign().
Referenced by _pull_ranges_out(). |
|
|
_pull_ranges_out Recursive function that does most of the work of pull_ranges_out above.
If ranges couldn't be pulled out by the expression, or if the resulting expression becomes unconstrained, this function returns 0.
... Determine whether ranges can be pulled out of the expression. If not, ... return 0. Otherwise, determine what range handling protocol should ... be used when pulling the ranges out of the expression's arguments.
... Pull out the ranges from the expression's arguments.
... Pull out the ranges from the expression itself.
... Don't pull ranges out of comma expressions.
Definition at line 1041 of file range_util.cc.
References _handle_omega_in_mod(), _handle_range(), _p_r_o_of_abs(), _p_r_o_of_add(), _p_r_o_of_divide(), _p_r_o_of_exp(), _p_r_o_of_ifix(), _p_r_o_of_min_max(), _p_r_o_of_mod(), _p_r_o_of_mult(), _p_r_o_of_range(), _pull_min_max_out_top(), ADD_OP, Expression::arg_list(), ARRAY_REF_OP, Mutator< T >::assign(), COMMA_OP, constant(), Iterator< T >::current(), Mutator< T >::del(), DIV_OP, e, List< T >::entries(), EXP_OP, Mutator< T >::grab(), RangeExpr::grab_lb(), RangeExpr::grab_ub(), Expression::intrinsic(), INTRINSIC_CALL_OP, is_empty_range(), KEEP_WHOLE_RANGE, RangeExpr::lb(), MULT_OP, Symbol::name_ref(), omega(), OMEGA_OP, Expression::op(), Expression::parameters_guarded(), Mutator< T >::pull(), RANGE_OP, Expression::symbol(), RangeExpr::ub(), and Iterator< T >::valid().
Referenced by pull_ranges_out(). |
|
|
pull_ranges_out 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, expression e is set to omega.
bool delete_expr = false;
Definition at line 1262 of file range_util.cc.
References _pull_ranges_out(), e, RangeExpr::grab_lb(), RangeExpr::grab_ub(), is_empty_range(), KEEP_WHOLE_RANGE, RangeExpr::lb(), omega(), Expression::op(), RANGE_OP, TAKE_RANGE_MAX, TAKE_RANGE_MIN, and RangeExpr::ub().
Referenced by _remove_mods_with_var(). |
|
|
Description: Print the given range expression as an (in)equality for the given variable.
Definition at line 1375 of file range_util.cc.
References comma(), INTEGER_TYPE, Symbol::intrinsic(), intrinsic_call(), IS_INTRINSIC, make_type(), mod_expr(), NOT_EXTERNAL, NOT_FORMAL, NOT_INTRINSIC, and Expression::type().
Referenced by _multiply_out_div(), _remove_truncates1(), and mod_expr(). |
|
|
Description: Return true if the given expression is a MOD intrinsic.
Definition at line 1413 of file range_util.cc.
References e, Expression::intrinsic(), INTRINSIC_CALL_OP, Symbol::name_ref(), Expression::op(), and Expression::symbol().
Referenced by _combine_min_max(), _elim_known_facts(), _is_pos_max(), _pull_out_common_min_max1(), remove_redundant_min_max_terms(), and RangeComparator::signz(). |
|
|
Description: Return true if the given expression contains a MIN or MAX intrinsic.
Definition at line 1448 of file range_util.cc.
References e, Expression::intrinsic(), INTRINSIC_CALL_OP, Symbol::name_ref(), Expression::op(), and Expression::symbol().
Referenced by _find_visit_order(), _multiply_out_divs_for_var1(), _p_mm_o_of_add(), _p_mm_o_of_divide(), _p_mm_o_of_exp(), _p_mm_o_of_mult(), _pull_in_add_expr(), _pull_in_div_expr(), _pull_in_exp_expr(), _pull_in_mult_expr(), _pull_min_max_out_top(), _substitute_mono_var(), _substitute_mono_var1(), contains_min_or_max(), remove_redundant_min_max_terms(), and swap_min_max(). |
|
|
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.
Definition at line 1485 of file range_util.cc.
References abs_to_max(), Expression::arg_list(), Mutator< T >::assign(), Expression::clone(), constant(), e, List< T >::grab(), List< T >::ins_first(), is_abs(), max_expr(), Expression::parameters_guarded(), Mutator< T >::pull(), simplify(), unary_minus(), and Iterator< T >::valid().
Referenced by abs_to_max(). |
|
|
_p_mm_o_of_add Pull the min or max expressions out to the top level of the add expression.
Definition at line 1594 of file range_util.cc.
References _pull_in_add_expr(), Expression::arg_list(), Iterator< T >::current(), e, List< T >::entries(), List< T >::first_ref(), List< T >::grab(), Mutator< T >::grab(), List< T >::ins_last(), is_min_or_max(), and Iterator< T >::valid().
Referenced by _pull_min_max_out_top(). |
|
|
_pull_in_mult_expr Add the given expression to the arguments of the given min or max intrinsic.
Definition at line 1629 of file range_util.cc.
References _join_nonbinary_exprs(), Expression::arg_list(), Mutator< T >::assign(), Expression::clone(), Iterator< T >::current(), is_min_or_max(), MULT_OP, NEG_EXPR, Expression::parameters_guarded(), POS_NEG_EXPR, Mutator< T >::pull(), swap_min_max(), and Iterator< T >::valid().
Referenced by _p_mm_o_of_mult(). |
|
|
_p_mm_o_of_mult Pull the min or max intrinsics to the outermost part of the given multiplication expression.
... Determine the sign of the non- min or max part
... Calculate the sign of result, if it hasn't already been done;
... intrinsic
Definition at line 1672 of file range_util.cc.
References _append_list(), _pull_in_mult_expr(), Expression::arg_list(), Iterator< T >::current(), e, List< T >::entries(), List< T >::first_ref(), List< T >::grab(), Mutator< T >::grab(), List< T >::ins_last(), is_min_or_max(), mul(), POS_NEG_EXPR, Expression::sign(), UNKNOWN_SIGN, and Iterator< T >::valid().
Referenced by _pull_min_max_out_top(). |
|
|
_pull_in_div_expr Add the given expression to the arguments of the given min or max intrinsic.
Definition at line 1743 of file range_util.cc.
References Expression::arg_list(), Mutator< T >::assign(), Expression::clone(), Iterator< T >::current(), div(), is_min_or_max(), NEG_EXPR, Expression::parameters_guarded(), Mutator< T >::pull(), swap_min_max(), and Iterator< T >::valid().
Referenced by _p_mm_o_of_divide(). |
|
|
_pull_in_exp_expr Add the given expression to the arguments of the given min or max intrinsic.
Definition at line 1792 of file range_util.cc.
References Expression::arg_list(), Mutator< T >::assign(), constant(), Iterator< T >::current(), exponent(), is_min_or_max(), NEG_EXPR, Expression::parameters_guarded(), Mutator< T >::pull(), swap_min_max(), and Iterator< T >::valid().
Referenced by _p_mm_o_of_exp(). |
|
|
_p_mm_o_of_exp Pull the min/max intrinsics out of an exponentiation statement.
Definition at line 1814 of file range_util.cc.
References _pull_in_exp_expr(), e, Expression::grab_left(), INTEGER_CONSTANT_OP, is_min_or_max(), Expression::left_guarded(), Expression::op(), POS_EXPR, POS_NEG_EXPR, Expression::right_guarded(), Expression::sign(), and Expression::value().
Referenced by _pull_min_max_out_top(). |
|
|
Description: Create a new MOD intrinsic with the given arguments.
Definition at line 1928 of file range_util.cc.
References Expression::arg_list(), Mutator< T >::assign(), Iterator< T >::current(), Mutator< T >::del(), List< T >::entries(), List< T >::first_ref(), List< T >::grab(), List< T >::ins_last(), Relation::is_greater_equal(), Relation::is_less_equal(), is_max(), is_min_or_max(), Expression::parameters_guarded(), Mutator< T >::pull(), remove_redundant_min_max_terms(), and Iterator< T >::valid().
Referenced by remove_redundant_min_max_terms(), and StmtRanges::simplify_min_max(). |
|
|
_pull_out_common_min_max Pull out any common terms of the max expressions in the two range's lower bounds and pull out any common terms in the min expressions in the upper bounds and return the range containing these common terms.
Definition at line 2013 of file range_util.cc.
References _delete_expr_in_list(), Expression::arg_list(), comma(), Iterator< T >::current(), List< T >::entries(), List< T >::first_ref(), List< T >::grab(), Mutator< T >::grab(), List< T >::ins_last(), intrinsic_call(), is_max(), is_min(), Expression::parameters_guarded(), and Iterator< T >::valid().
Referenced by _pull_out_common_min_max(). |
|
|
Description: Return the union of the two ranges.
... New range has one element.
... New range has no elements.
Definition at line 2165 of file range_util.cc.
References _join_ranges(), _pull_out_common_min_max(), Expression::clone(), compare(), Expression::compare(), constant(), convert_to_range(), expr_expand_substituted(), RangeExpr::grab_lb(), RangeExpr::grab_ub(), Relation::is_circular(), is_empty_range(), Relation::is_equal(), Relation::is_greater_equal(), Relation::is_greater_than(), Relation::is_less_equal(), Relation::is_unknown(), RangeExpr::lb(), max_expr(), min(), min_expr(), OMEGA_OP, simplify(), and RangeExpr::ub().
Referenced by SSAFullRangeDict::_get_range_ref(), GSAFullRangeDict::_get_range_ref(), and RangeAccessor::get_range_ref(). |
|
|
Description: Perform a widening operator on the given expression and return the result.
... New range has one element.
Definition at line 2250 of file range_util.cc.
References _join_ranges(), _pull_out_common_min_max(), Expression::clone(), compare(), convert_to_range(), expr_expand_substituted(), RangeExpr::grab_lb(), RangeExpr::grab_ub(), RangeExpr::has_lb(), RangeExpr::has_ub(), is_empty_range(), Relation::is_equal(), Relation::is_greater_equal(), Relation::is_less_equal(), RangeExpr::lb(), max_expr(), min(), min_expr(), OMEGA_OP, simplify(), and RangeExpr::ub().
Referenced by RangeAccessor::get_range_ref(). |
|
|
Description: Perform a narrowing operator on the given expression and return the result.
... New range has one element.
Definition at line 2318 of file range_util.cc.
References _join_ranges(), _pull_out_common_min_max(), Expression::clone(), convert_to_range(), RangeExpr::grab_lb(), RangeExpr::has_lb(), RangeExpr::has_ub(), is_empty_range(), RangeExpr::lb(), OMEGA_OP, RangeExpr::ub(), and widen_range().
Referenced by widen_range(). |
|
|
Description Extract and return all possible ranges from the given logical expression.
Expression 1 is less than expression 2 if it is indicated to be less than by both range comparaters. Other relations are computed similarly.
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.
Definition at line 2400 of file range_util.cc.
References Relation::is_unknown().
Referenced by intersect_ranges(), and union_ranges(). |
| static Expression* _remove_divs_from_term |
( |
Expression * |
expr, |
|
|
int & |
factor, |
|
|
bool |
take_max |
|
) |
[static] |
|
| static void _remove_divs_from_rel |
( |
Expression & |
expr |
) |
[static] |
|
|
|
_extract_a_range -- Extract and returns a single range from a binary relation.
The arguments assume that the relation: (var_term + other_terms) rel_op 0 holds.
... Determine the variable to constrain and its optional multiplicative ... factor
... Make sure that the variable doesn't occur on the right hand expression
... Calculate the constraint's bound
... Convert < to <= and > to >=
... Calculate the proper range expression from this bound
... Add this range to the set of ranges
Definition at line 2538 of file range_util.cc.
References _negate_rel_op(), add(), Expression::arg_list(), Expression::clone(), constant(), div(), EQ_OP, List< T >::first_ref(), GE_OP, GT_OP, ID_OP, Set< T >::ins(), INTEGER_CONSTANT_OP, is_var_in_expr(), List< T >::last_ref(), LE_OP, LT_OP, MULT_OP, Expression::op(), simplify(), Expression::symbol(), unary_minus(), and Expression::value().
Referenced by _extract_ranges_rel(), and _remove_divs_from_rel(). |
|
|
_extract_ranges_rel -- Extract all ranges from a binary relation.
Assumes that the relation has been simplified.
Definition at line 2646 of file range_util.cc.
References _extract_a_range(), ADD_OP, Expression::arg_list(), Iterator< T >::current(), GE_OP, List< T >::grab(), Expression::grab_left(), GT_OP, List< T >::ins_after(), INTEGER_TYPE, is_integer_zero(), LE_OP, Expression::left(), Expression::left_guarded(), LT_OP, Expression::op(), List< T >::prev_ref(), Expression::right(), and Iterator< T >::valid().
Referenced by _extract_ranges(). |
| 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.
Definition at line 2742 of file range_util.cc.
References RangeExpr::has_lb(), RangeExpr::has_ub(), RangeExpr::lb(), OMEGA_OP, RANGE_OP, and RangeExpr::ub().
Referenced by SSAFullRangeDict::pretty_print(), SSAControlRangeDict::pretty_print(), RangeAccessor::pretty_print(), GSAFullRangeDict::pretty_print(), GSAControlRangeDict::pretty_print(), ControlRangeDict::pretty_print(), BaseStmtRanges::pretty_print(), SSAControlRangeData::print(), and GSAControlRangeData::print(). |
|
|
This routine checks expr for containing exactly one variable, and if it does, applies the [lower:upper] range to it.
If the variable already has an upper or lower bound associated with it, then apply the limits to that bound.
... Now, if expr is just an ID_OP, assert that its range bounds are ... within the bounds of the declaration, or if one of its range bounds ... is an InfinityExpr, change that to the declaration bounds.
... Don't allow infinite recursion
... Check for Infinity in lower bound
... if not, constrain the lower bound to be within the declaration bound
... Check for infinity in upper bound
... if not, constrain the upper bound to be within the declaration bound
... Range is a single value - KDIM: kmax
Definition at line 3003 of file range_util.cc.
References and(), apply_limits(), RefSet< T >::clear(), Expression::clone(), ge(), ID_OP, INFINITY_OP, INTEGER_CONSTANT_OP, is_ID_OP(), le(), Expression::op(), RANGE_OP, set_ranges_for_symbol(), substitute_var(), tighten_lower_bound(), and tighten_upper_bound().
Referenced by _add_subscript_constraints_to_ranges(), and apply_limits(). |
|