RangeComparator.cc File Reference
Go to the source code of this file.
|
Enumerations |
| enum | _MONO_STATE {
_NON_MONO,
_MONO_DEC,
_MONO_INC
} |
| | monotonicity_for_var Return whether the given expression is monotonically increasing or decreasing for the given variable. More...
|
Functions |
| template ostream & | operator<< (ostream &, const Map< Symbol, CompareData > &) |
| EXPR_SIGN | flip_sign (EXPR_SIGN sign) |
| | Description: Tell the RangeComparator class to start collecting statistics.
|
| static void | _print_avg_time (ostream &o, const Timer &timer, int count) |
| 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) |
| | print_range_stats Print out the statistics collected so far.
|
| static int | _skip_int_const_exprs (const Expression *&term) |
| | skip_int_const_exprs Set the given argument to the next expression of the list, skipping over any integer constants.
|
| static bool | _int_diff (const Expression &e1, const Expression &e2, int &diff) |
| | int_diff If expression e1 differs from expression e2 by an integer value, return true and this integer difference.
|
| static bool | contains_infinity (const Expression &e) |
| | compare
|
| static bool | _is_pos_max (const Expression &e) |
| | _is_pos_max Return true if the given expression is a positive MAX expression
|
| static bool | _is_neg_min (const Expression &e) |
| | _is_neg_min Return true if the given expression is a negative MIN expression
|
| static bool | _is_comparable (const Expression &e) |
| | _is_comparable Return true if the given expression is comparable without further transformations.
|
| static Relation | _determine_relation (const Expression &delta, bool dummy_range_just_substituted, RangeComparator *comp) |
| | _determine_relation Determine the proper relationship from the given delta expression.
|
| static void | _vars_in_expr (RefSet< Symbol > &vars, const Expression &expr) |
| | vars_in_expr Return the set of variables that occur in the given expression.
|
| static void | _find_visit_order (RefList< Symbol > &ordered_vars, const RefSet< Symbol > &vars, RangeComparator &comparator) |
| | _find_visit_order Use heuristics to decide the ordering of the given expressions.
|
| static void | _generate_subst_order1 (RefList< Symbol > &subst_order, const Expression &e, RangeComparator &comparator, RefSet< Symbol > &visited) |
| | _generate_subst_order1 Determine an ordering of variable substitution for the given expression that will maximize the cancellation of common terms.
|
| static void | _generate_subst_order1 (RefList< Symbol > &subst_order, const Expression &e, RangeComparator &comparator) |
| static void | _build_range_use_set (Map< Symbol, RefSet< Symbol > > &range_use_set, const RefList< Symbol > &candidate_vars, RangeComparator &comparator) |
| | build_range_use_set For each variable, build a set all variables whose ranges contain that variable.
|
| static void | _find_scc_from_list (RefSet< Symbol > &scc, const RefList< Symbol > &rev_topological_order, const Symbol &root_var, const Map< Symbol, RefSet< Symbol > > &reversed_edges) |
| | _grab_scc_from_list This function grabs all variables in rev_topological_order that are in a strongly connected component (SCC) containing root_var, and returns them in scc.
|
| static void | _grab_scc_from_list (RefList< Symbol > &scc, RefList< Symbol > &rev_topological_order, const Symbol &root_var, const Map< Symbol, RefSet< Symbol > > &reversed_edges) |
| static void | _generate_subst_order (RefList< Symbol > &subst_order, const Expression &e, RangeComparator &comparator) |
| | _generate_subst_order Determine an ordering of variable substitution for the given expression that will maximize the cancellation of common terms.
|
| static Expression * | _replace_vars_with_omega (Expression *e) |
| | _replace_vars_with_omega Replace all variables in the expresion with omega expressions.
|
| static int | _num_var_occurrences_in_expr (const Expression &expr, const Symbol &var) |
| | _num_var_occurrences_in_expr Return the number of times that the given variable occurs in the given expression.
|
| static Expression * | _remove_truncates1 (Expression *expr, const Symbol &var, bool &changed, Symtab &symtab) |
| | _remove_truncates Replace all subexpressions of the form B*(A/B) with A - MOD(A, B) in the given expression.
|
| static Expression * | _multiply_out_div (Expression *expr, Expression *&factor, RangeComparator &comparator) |
| | _multiply_out_div Multiply out the given division expression, if possible.
|
| static Expression * | _multiply_out_divs_for_var1 (Expression *expr, const Symbol &var, Expression *&factor, bool multiply_out_divs, RangeComparator &comparator) |
| | _multiply_out_divs_for_var If the given var occurs in at least twice in the given expression, and at least one of the subexpressions it occurs in is a divide, remove these division expressions by multiplying the entire expression by the denominators of these subexpressions.
|
| static Expression * | _multiply_out_divs_for_var (Expression *expr, const Symbol &var, RangeComparator &comparator) |
| static Expression * | _forward_diff (const Expression &e, const Symbol &var) |
| | forward_diff Return the forward difference of the given expression for the given value.
|
| static int | _var_power_in_expr (const Expression &expr, const Symbol &var) |
| | var_power_in_expr Return the maximum power of the given variable in the given expression.
|
| static _MONO_STATE | _monotonicity_for_var (const Expression &expr, const Symbol &var, RangeComparator &comparator) |
| static Expression * | _substitute_mono_var1 (Expression *expr, const Symbol &var, const Expression &mono_function, bool var_is_mono_inc, const Symtab &symtab) |
| | substitute_mono_var Substitute the given substitution expression for the given variable in the given expression, where the given expression is either monotonically increasing or monotonically decreasing.
|
| static Expression * | _substitute_mono_var (Expression *expr, const Symbol &var, const Expression &subst_expr, bool var_is_mono_inc, const Symtab &symtab) |
| static bool | _subst_mods_with_var (Expression &expr, const Symbol &var, const Expression &subst_expr) |
| | subst_mods_with_var Replace the left hand side of modulo operations that contain the given variable with the given expression.
|
| static Expression * | _remove_mods_with_var (Expression *expr, const Symbol &var, const Expression &subst_expr, RangeComparator &comparator) |
| | remove_mods_with_var Transform all modulo operations that contain the given variable into ranges.
|
| static Expression * | _member_exp_ref (Expression &expr, const Symbol &var) |
| | _member_exp_ref If the variable, or a power of it, is the given expression or is a term of a multiplication expression, return the term.
|
| static Expression * | _factor_out_var_top (Expression *expr, const Symbol &var) |
| | _factor_out_var Factor out the given variable from the top level ofgiven expression.
|
| static Expression * | _factor_out_var (Expression *expr, const Symbol &var) |
| | _factor_out_var Factor out the given variable from the given expression.
|
| static Expression * | _solve_linear_expr (Expression *e, const Symbol &var, RangeComparator &comparator) |
| | solve_linear_expr Solve the given expression for the given variable.
|
| static int | _num_args_with_var (const Expression &expr, const Symbol &var) |
| | num_args_with_var Return the number of arguments that contain the given variable.
|
| static bool | _is_arithmetic_expr (const Expression &expr) |
| | is_aritmetic_expr Return true if the top level expression is some sort of arithmetic operator.
|
| Expression * | _subst_var_outside_array_refs (Expression *expr, const Symbol &var, const Expression &subst_expr) |
| | subst_var_outside_array_refs Like substitute_var() except that variables inside array references cannot be substituted by a range.
|
| static bool | _are_vars_in_expr (const Expression &e, const RefSet< Symbol > &vars) |
| | _are_vars_in_expr Return true if the given expression uses any of the variables in the given set.
|
Variables |
| static RangeComparatorStats * | _stats = 0 |
Detailed Description
Definition in file RangeComparator.cc.
Enumeration Type Documentation
|
|
monotonicity_for_var Return whether the given expression is monotonically increasing or decreasing for the given variable.
- Enumeration values:
-
| _NON_MONO |
|
| _MONO_DEC |
... Expression is not monotonic |
| _MONO_INC |
... Expression is monotonically decreasing |
Definition at line 2028 of file RangeComparator.cc. |
Function Documentation
| static void _print_avg_time |
( |
ostream & |
o, |
|
|
const Timer & |
timer, |
|
|
int |
count |
|
) |
[static] |
|
| void collect_range_stats |
( |
|
) |
|
|
| void stop_range_stats |
( |
|
) |
|
|
| void print_range_stats |
( |
ostream & |
o |
) |
|
|
| static int _skip_int_const_exprs |
( |
const Expression *& |
term |
) |
[static] |
|
|
|
skip_int_const_exprs Set the given argument to the next expression of the list, skipping over any integer constants.
The sum of the values of these skipped integer constants is returned.
Definition at line 377 of file RangeComparator.cc.
References is_integer_constant().
Referenced by _int_diff(). |
|
|
int_diff If expression e1 differs from expression e2 by an integer value, return true and this integer difference.
Else, return false.
This function assumes that e1 and e2 have been simplified (i.e., all integer constants have been folded, they are in in sum-of-products form, etc.). This function will also take unsimplified expressions, but is more likely to fail (i.e., return false.) This function may reorder the arguments of commutative subexpressions within these expressions.
This function was designed to be a much quicker alternative to the performing "simplify(sub(e1.clone(), e2.clone()))", which is often used for expression comparison. When doing such comparisons, it is suggested to try this function first. If it fails, apply the code fragment above.
... Both expressions are integers, so return true and their difference.
... Neither expression are addition expressions, so return true ... if and only if the expressions equal each other.
... Exactly one expression is an addition expression. So return ... true with the difference C if and only if the expressions ... are of the form A+C and A.
... Both expressions are addition expressions. So return ... true with the difference C1-C2 if and only if the expressions ... are of the form A1+A2+...+AN+C1 and A1+A2+...AN+C2.
... e1.standardize(); ... e2.standardize();
Definition at line 408 of file RangeComparator.cc.
References _skip_int_const_exprs(), ADD_OP, Expression::arg_list(), Expression::compare(), List< T >::entries(), List< T >::first_ref(), is_integer_constant(), List< T >::last_ref(), Listable::next_ref(), and Expression::value().
Referenced by RangeComparator::compare(). |
| static bool contains_infinity |
( |
const Expression & |
e |
) |
[static] |
|
| static bool _is_pos_max |
( |
const Expression & |
e |
) |
[static] |
|
| static bool _is_neg_min |
( |
const Expression & |
e |
) |
[static] |
|
| static bool _is_comparable |
( |
const Expression & |
e |
) |
[static] |
|
|
|
_is_comparable Return true if the given expression is comparable without further transformations.
An expression is comparable if it is omega, an integer, or a range bounded by omegas or integers.
... <integer>**<expr>
... for addition or multiplication, all terms must be comparable
Definition at line 729 of file RangeComparator.cc.
References _is_neg_min(), _is_pos_max(), ADD_OP, Expression::arg_list(), e, EXP_OP, RangeExpr::has_lb(), RangeExpr::has_ub(), INTEGER_CONSTANT_OP, is_empty_range(), RangeExpr::lb(), Expression::left_guarded(), MULT_OP, OMEGA_OP, Expression::op(), RANGE_OP, RangeExpr::ub(), List< T >::valid(), and Expression::value(). |
|
|
_determine_relation Determine the proper relationship from the given delta expression.
This method will return an unknown relationship if it is not comparable, (i.e. _is_comparable(delta) returns false.)
An omega or totally unbounded delta expression is assumed to be from a circular reference if a dummy range was just substituted, otherwise an unknown value
... unknown
... if it's all (-1) and (x**y) terms, use fact that x**y is >=1
... Check for difference of 2 exponentials
... make sure the bases of the exponentials are equal
... make sure the bases of the exponentials are equal
... Unknown relationship
Definition at line 787 of file RangeComparator.cc.
References _is_neg_min(), _is_pos_max(), ADD_OP, Expression::arg_list(), Relation::circular(), List< T >::entries(), Relation::equal(), EXP_OP, Relation::greater_than(), RangeExpr::has_lb(), RangeExpr::has_ub(), INTEGER_CONSTANT_OP, is_empty_range(), Relation::is_equal(), Relation::is_greater_than(), is_integer_constant(), Relation::is_less_than(), is_unbounded_range(), RangeExpr::lb(), Expression::left_guarded(), Relation::less_than(), MULT_OP, Expression::op(), RANGE_OP, Expression::right_guarded(), RangeExpr::ub(), List< T >::valid(), and Expression::value(). |
|
|
_find_visit_order Use heuristics to decide the ordering of the given expressions.
These heuristics attempt to insert variables whose ranges are more difficult to manipulate before variables whose ranges are more simple to manipulate.
Definition at line 998 of file RangeComparator.cc.
References Iterator< T >::current(), RangeExpr::has_lb(), RangeExpr::has_ub(), ID_OP, RefSet< T >::ins(), INTEGER_CONSTANT_OP, is_min_or_max(), RangeExpr::lb(), Expression::op(), RANGE_OP, RangeExpr::ub(), and Iterator< T >::valid().
Referenced by _generate_subst_order1(). |
|
|
_generate_subst_order1 Determine an ordering of variable substitution for the given expression that will maximize the cancellation of common terms.
This ordering is returned in the list subst_order.
Since this problem is at least NP-Complete, a heuristic is used to calculate the ordering. Essentially, this algorithm traverses the depth first tree of the graph of variable dependences. (Each node is labeled with a variable name , and there is an edge A-->B if the substitutable value of variable A contains variable B.) In this tree, the parent occurs earlier in the list than its children. Thus, if the graph is a DAG, the assigned order would be a topological order, which can be shown as an optimal order.
Definition at line 1073 of file RangeComparator.cc.
References _find_visit_order(), _vars_in_expr(), Iterator< T >::current(), e, and Iterator< T >::valid().
Referenced by _generate_subst_order(), and _generate_subst_order1(). |
|
|
_grab_scc_from_list This function grabs all variables in rev_topological_order that are in a strongly connected component (SCC) containing root_var, and returns them in scc.
The variables rev_topological_order are assumed to be ordered in reverse topological order (ignoring back edges) of the variable dependency graph (see _generate_subst_order1). The map reversed_edges contains the edges of the variable dependency graph in reverse order. The order of the variables in scc is guarantteed to be the same as their order in rev_topological_order. The algorithm for identifying SCCs was adapted from "Introduction of Algorithms" by Cormen, Leiserson, and Rivest.
Definition at line 1158 of file RangeComparator.cc.
References Iterator< T >::current(), and Iterator< T >::valid().
Referenced by _grab_scc_from_list(). |
|
|
_generate_subst_order Determine an ordering of variable substitution for the given expression that will maximize the cancellation of common terms.
This ordering is returned in the list subst_order.
This function is essentially an extension of _generate_subst_order1. The order is identical to _generate_subst_order1 except that all variables in strongly connected components (SCC) are visited twice.
... SCC has more than one variable, so add each variable in it ... twice.
Definition at line 1213 of file RangeComparator.cc.
References _build_range_use_set(), _generate_subst_order1(), _grab_scc_from_list(), Iterator< T >::current(), e, RefList< T >::entries(), RefList< T >::grab(), RefList< T >::ins_first(), RefList< T >::ins_last(), Iterator< T >::reset(), and Iterator< T >::valid(). |
|
|
_replace_vars_with_omega Replace all variables in the expresion with omega expressions.
Definition at line 1250 of file RangeComparator.cc.
References Expression::arg_list(), ARRAY_REF_OP, List< T >::assign(), e, FUNCTION_CALL_OP, ID_OP, INTRINSIC_CALL_OP, List< T >::last_ref(), omega(), Expression::op(), List< T >::pull(), DistributeExpr::symbol(), SYMBOLIC_CONSTANT_CLASS, and VARIABLE_CLASS. |
| static int _num_var_occurrences_in_expr |
( |
const Expression & |
expr, |
|
|
const Symbol & |
var |
|
) |
[static] |
|
|
|
_remove_truncates Replace all subexpressions of the form B*(A/B) with A - MOD(A, B) in the given expression.
... Remove any truncates from my arguments.
... Remove any top-level truncates.
... Collect all divisions in the multiplication.
... Eliminate as many of these divisions as possible.
... Put the remaining divisions back into the multiplication expr.
Definition at line 1309 of file RangeComparator.cc.
References Expression::arg_list(), Mutator< T >::assign(), Expression::clone(), Iterator< T >::current(), Mutator< T >::del(), div(), DIV_OP, List< T >::entries(), List< T >::grab(), Mutator< T >::grab(), Expression::grab_left(), Expression::grab_right(), List< T >::ins_last(), INTEGER_CONSTANT_OP, is_evenly_divisible(), is_integer_zero(), is_var_in_expr(), Expression::left_guarded(), mod_expr(), mul(), MULT_OP, Expression::op(), Mutator< T >::pull(), Expression::right_guarded(), simplify(), sub(), Iterator< T >::valid(), and Expression::value(). |
|
|
_multiply_out_div Multiply out the given division expression, if possible.
If successful, the factor used to eliminate the division is multiplied to the given factor argument and passed back. More specifically, if the given expression and factor is A/B and F respectively, where B >= 0, the returned expression would be A - (A mod B) and the returned factor would be F*B. If B < 0, the returned results would be (A mod B) - A and -F*B.
Definition at line 1421 of file RangeComparator.cc.
References Expression::clone(), DIV_OP, Expression::grab_left(), Expression::grab_right(), INTEGER_CONSTANT_OP, is_evenly_divisible(), mod_expr(), NEG_EXPR, POS_NEG_EXPR, sub(), unary_minus(), Expression::value(), and ZERO_EXPR.
Referenced by _multiply_out_divs_for_var1(). |
|
|
_multiply_out_divs_for_var If the given var occurs in at least twice in the given expression, and at least one of the subexpressions it occurs in is a divide, remove these division expressions by multiplying the entire expression by the denominators of these subexpressions.
Only division expressions that occur at the top level, sum-of-products expressions and whose denominator is evenly divisible are considered. Integer division expressions are handled by transforming B*(A/B) into A - (A mod B).
You may ask why such a function exists, especially with such a strange decision procedure for application. Essentially, the purpose of this procedure is to collapse expressions like (A/B) - A, where B > 0, down to A mod B, allowing one to prove that A/B < A if A > 0. Another case that this procedure handles is B*(100/B) - 100.
... If a new factor was generated by this argument, multiply all ... previously visited arguments with this new factor.
... Do nothing;
Definition at line 1469 of file RangeComparator.cc.
References _multiply_out_div(), _num_var_occurrences_in_expr(), ADD_OP, Expression::arg_list(), List< T >::assign(), Mutator< T >::assign(), Expression::clone(), Iterator< T >::current(), DIV_OP, EXP_OP, exponent(), RefList< T >::ins_last(), INTEGER_CONSTANT_OP, INTRINSIC_CALL_OP, is_min_or_max(), is_var_in_expr(), Expression::left(), mul(), MULT_OP, Expression::op(), List< T >::pull(), Mutator< T >::pull(), RANGE_OP, Expression::right_guarded(), Iterator< T >::valid(), and Expression::value().
Referenced by _multiply_out_divs_for_var(). |
|
|
forward_diff Return the forward difference of the given expression for the given value.
That is, if the expression can be represented as a function f(i,j,k,...), where i,j,k,... are variables, then the forward difference for j is f(i,j+1,k,...) - f(i,j,k,...).
Definition at line 1966 of file RangeComparator.cc.
References add(), DistributeExpr::clone(), constant(), e, simplify(), sub(), and substitute_var().
Referenced by _monotonicity_for_var(). |
| static int _var_power_in_expr |
( |
const Expression & |
expr, |
|
|
const Symbol & |
var |
|
) |
[static] |
|
|
|
_member_exp_ref If the variable, or a power of it, is the given expression or is a term of a multiplication expression, return the term.
Otherwise, return NULL.
Definition at line 2227 of file RangeComparator.cc.
References Expression::arg_list(), Iterator< T >::current(), EXP_OP, ID_OP, INTEGER_CONSTANT_OP, MULT_OP, Expression::op(), and Iterator< T >::valid().
Referenced by _factor_out_var_top(). |
|
|
_factor_out_var Factor out the given variable from the top level ofgiven expression.
For example, the factored form of the expression "x*a + x*b + c" for variable x is "x*(a + b) + c".
Definition at line 2261 of file RangeComparator.cc.
References _member_exp_ref(), ADD_OP, Expression::arg_list(), constant(), Iterator< T >::current(), List< T >::del(), List< T >::entries(), Set< T >::entries(), EXP_OP, List< T >::first_ref(), List< T >::grab(), Set< T >::grab(), Mutator< T >::grab(), Expression::grab_left(), ID_OP, Set< T >::ins(), List< T >::ins_last(), List< T >::modify(), mul(), MULT_OP, Expression::op(), Expression::right_guarded(), Iterator< T >::valid(), and Expression::value().
Referenced by _factor_out_var(). |
|
|
solve_linear_expr Solve the given expression for the given variable.
The expression is assumed to be linear for the given variable.
... Pull the terms containing var out of the expression.
... Factor out the variable from var_term.
... Compute the divisor of the solution.
... We want e to be rounded upwards. So if e ... is positive, add one to it.
Definition at line 2377 of file RangeComparator.cc.
References _factor_out_var(), add(), ADD_OP, Expression::arg_list(), constant(), Iterator< T >::current(), Mutator< T >::del(), div(), e, List< T >::entries(), List< T >::first_ref(), flip_sign(), List< T >::grab(), Mutator< T >::grab(), ID_OP, List< T >::ins_last(), is_var_in_expr(), MULT_OP, NEG_EXPR, Expression::op(), POS_EXPR, POS_NEG_EXPR, Expression::sign(), simplify(), Expression::type(), unary_minus(), and Iterator< T >::valid(). |
| static int _num_args_with_var |
( |
const Expression & |
expr, |
|
|
const Symbol & |
var |
|
) |
[static] |
|
| static bool _is_arithmetic_expr |
( |
const Expression & |
expr |
) |
[static] |
|
|
|
_are_vars_in_expr Return true if the given expression uses any of the variables in the given set.
Definition at line 3163 of file RangeComparator.cc. |
Variable Documentation
|