Polaris: RangeComparator.cc Source File

RangeComparator.cc Go to the documentation of this file. /// /// /// \file RangeComparator.cc /// #include <limits.h> #include "../Expression/Expression.h" #include "../Expression/InfinityExpr.h" #include "../Expression/NonBinaryExpr.h" #include "../Collection/Iterator.h" #include "../Collection/Mutator.h" #include "../Collection/KeyIterator.h" #include "../Collection/RefSet.h" #include "../Collection/Set.h" #include "../Collection/RefList.h" #include "../utilities/switches_util.h" #include "../utilities/expression_util.h" #include "../Symtab.h" #include "../Timer.h" #include "RangeComparator.h" #include "RangeExpr.h" #include "range_util.h" #include "../Constant/constant.h" #define MAX_SUBST 1 /// ... Maximum number of times a variable should /// ... be substituted by the compare method. //static int _range_compare_accuracy = 1; /// Statistics collecting object. #define HIST_SIZE 64 /// Template instantiations template class TypedBaseMap<Symbol,CompareData>; template class ProtoMap<Symbol,CompareData>; template class Map<Symbol,CompareData>; template ostream & operator << (ostream &, const Map<Symbol,CompareData> &); template class KeyIterator<Symbol,CompareData>; class RangeComparatorStats { public: RangeComparatorStats(); RangeComparatorStats(const RangeComparatorStats &other); virtual ~RangeComparatorStats(); void reset(); /// ... Reset all my statistics; void start_compare(); /// ... Start a comparison operator. void making_a_var_subst(); /// ... Curlrent comparison is making a variable substitution. void end_compare(); /// ... End a comparison operator. void print(ostream &o); /// ... Print out all my statistics. private: int _compare_level; /// ... Current number of invocations of compare /// ... on the calling stack. int _num_compares; /// ... Number of compare() invocations. int _num_top_level_compares; /// ... Number of top level compares(). int _num_substs; /// ... Number of variable substitutions by current /// ... compare(), including recursive calls. Timer _compare_time; /// ... Time taken by current compare. int _num_subst_histogram[HIST_SIZE]; /// ... Histogram of number of compares with /// ... the given number of substitutions. Timer _time_histogram[HIST_SIZE]; /// ... Histogram of time taken by a /// ... comparison that made the given number /// ... of substitutions }; static RangeComparatorStats *_stats = 0; /// flip_sign EXPR_SIGN flip_sign(EXPR_SIGN sign) { if (sign == POS_EXPR) return NEG_EXPR; else if (sign == NEG_EXPR) return POS_EXPR; return sign; } /// CompareData methods CompareData::CompareData() { num_subst = 0; sign_cache = UNKNOWN_SIGN; /// ... use_the_big_guns = (range_compare_accuracy() >= 1); } CompareData::CompareData(const CompareData &other) { num_subst = other.num_subst; sign_cache = other.sign_cache; /// ... use_the_big_guns = other.use_the_big_guns; } CompareData::~CompareData() { /// ... Nothing to do } Listable * CompareData::listable_clone() const { return new CompareData(*this); } int CompareData::structures_OK() const { return 1; } void CompareData::print(ostream &o) const { o << "["; o << "ns=" << num_subst << ", "; o << "sc="; switch (sign_cache) { case POS_EXPR: o << "+"; break; case NEG_EXPR: o << "-"; break; case POS_NEG_EXPR: o << "+-"; break; case UNKNOWN_SIGN: o << "?"; break; case PENDING: o << "P"; break; default: break; } /// ... o << ", "; /// ... o << "ubg=" << use_the_big_guns; o << "]"; } /// RangeComparatorStats methods RangeComparatorStats::RangeComparatorStats() { reset(); } RangeComparatorStats::RangeComparatorStats(const RangeComparatorStats &other) { _compare_level = other._compare_level; _num_compares = other._num_compares; _num_top_level_compares = other._num_top_level_compares; _num_substs = other._num_substs; _compare_time = other._compare_time; for (int i = 0; i < HIST_SIZE; ++i) { _num_subst_histogram[i] = other._num_subst_histogram[i]; _time_histogram[i] = other._time_histogram[i]; } } RangeComparatorStats::~RangeComparatorStats() { /// ... Nothing to do. } void RangeComparatorStats::reset() { _compare_level = 0; _num_compares = 0; _num_top_level_compares = 0; _num_substs = 0; _compare_time.stop(); _compare_time.reset(); for (int i = 0; i < HIST_SIZE; ++i) { _num_subst_histogram[i] = 0; _time_histogram[i].stop(); _time_histogram[i].reset(); } } void RangeComparatorStats::start_compare() { ++_compare_level; ++_num_compares; if (_compare_level == 1) { ++_num_top_level_compares; _num_substs = 0; _compare_time.reset(); _compare_time.restart(); } } void RangeComparatorStats::making_a_var_subst() { if (_compare_level > 0) ++_num_substs; } void RangeComparatorStats::end_compare() { p_assert(_compare_level > 0, "There were more end_compare() invocations than start_compare() invocations."); if (_compare_level == 1) { _compare_time.stop(); if (_num_substs >= HIST_SIZE) _num_substs = HIST_SIZE - 1; ++_num_subst_histogram[_num_substs]; _time_histogram[_num_substs] += _compare_time; } --_compare_level; } static void _print_avg_time(ostream &o, const Timer &timer, int count) { if (count > 0) { double user, system, wallclock; timer.timings(user, system, wallclock); user /= count; system /= count; wallclock /= count; o <<user<<"\t" <<system<<"\t" <<wallclock; /// o << form("%.4fu %.4fs %.4fw", user, system, wallclock); } else o <<0<<"\t" <<0<<"\t" <<0; /// o << form("%.4fu %.4fs %.4fw", 0.0, 0.0, 0.0); } void RangeComparatorStats::print(ostream &o) { o << "Number of compare() invocations = " << _num_compares << endl; o << "Number of top-level compare() invocations = " << _num_top_level_compares << endl; o << endl; o << " Num. Substs Num. TL Compares Total time Time per subst.\n"; o << "------------------------------------------------------------------------\n"; int tot_substs = 0; Timer tot_time; tot_time.stop(); tot_time.reset(); for (int i = 0; i < HIST_SIZE; ++i) if (_num_subst_histogram[i] > 0) { o <<i<<"\t"<< _num_subst_histogram[i]; /// o << form(" %7d %10d ", /// i, _num_subst_histogram[i]); o << _time_histogram[i]; o << " "; _print_avg_time(o, _time_histogram[i], i * _num_subst_histogram[i]); o << endl; tot_substs += i * _num_subst_histogram[i]; tot_time += _time_histogram[i]; } o << "Total number of substitutions performed = " << tot_substs << endl; o << "Total time taken = " << tot_time << endl; o << "Total time per substitution = "; _print_avg_time(o, tot_time, tot_substs); o << endl; } /// collect_range_stats /// Tell the range comparator to collect statistics. void collect_range_stats() { _stats = new RangeComparatorStats(); } /// stop_range_stats /// Tell the range comparator to stop collecting statistics. void stop_range_stats() { if (_stats) { delete _stats; _stats = 0; } } /// print_range_stats /// Print out the statistics collected so far. void print_range_stats(ostream &o) { if (_stats) _stats->print(o); } /// _compare_data /// Return the comparison data collected for the given variable. CompareData & RangeComparator::_compare_data(const Symbol &var) { CompareData *data = _compare_info.find_ref(var); if (! data) { data = new CompareData; _compare_info.ins(var, data); } return *data; } /// RangeComparator RangeComparator::RangeComparator(const Symtab &symtab) { _symtab_ref = &symtab; debug_level(0); range_join_accuracy(switch_value("range_acc")); range_compare_accuracy(1); _cache_expr_signs = 0; } RangeComparator::RangeComparator(const RangeComparator &other) { *this = other; } /// ~RangeComparator RangeComparator::~RangeComparator() { /// ... nothing to do } /// 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. static int _skip_int_const_exprs(const Expression *& term) { int value = 0; while (term && is_integer_constant(*term)) { value += term->value(); term = (const Expression *) term->next_ref(); } return value; } /// 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. static bool _int_diff(const Expression &e1, const Expression &e2, int &diff) { if (is_integer_constant(e1) && is_integer_constant(e2)) { /// ... Both expressions are integers, so return true and their difference. diff = e1.value() - e2.value(); return true; } else if (e1.op() != ADD_OP && e2.op() != ADD_OP) { /// ... Neither expression are addition expressions, so return true /// ... if and only if the expressions equal each other. diff = 0; return (e1.compare(e2) == 0); } else if (e1.op() != ADD_OP || e2.op() != ADD_OP) { /// ... 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. const Expression *add_expr, *other_expr; if (e1.op() == ADD_OP) { add_expr = &e1; other_expr = &e2; } else { add_expr = &e2; other_expr = &e1; } const List<Expression> &add_args = add_expr->arg_list(); if (add_args.entries() != 2) return false; const Expression *add_term; if (is_integer_constant(*add_args.first_ref())) { diff = add_args.first_ref()->value(); add_term = add_args.last_ref(); } else if (is_integer_constant(*add_args.last_ref())) { diff = add_args.last_ref()->value(); add_term = add_args.first_ref(); } else return false; if (add_expr == &e2) diff = -diff; return (add_term->compare(*other_expr) == 0); } else { /// ... 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(); const Expression *e1_term = e1.arg_list().first_ref(); const Expression *e2_term = e2.arg_list().first_ref(); diff = 0; diff += _skip_int_const_exprs(e1_term); diff -= _skip_int_const_exprs(e2_term); while (e1_term && e2_term) { if (e1_term->compare(*e2_term) != 0) return false; e1_term = (Expression *) e1_term->next_ref(); e2_term = (Expression *) e2_term->next_ref(); diff += _skip_int_const_exprs(e1_term); diff -= _skip_int_const_exprs(e2_term); } return (! e1_term && ! e2_term); } } /// compare static bool contains_infinity(const Expression& e){ if (e.op()==INFINITY_OP){ return true; } else { for(Iterator<Expression> eit=e.arg_list(); eit.valid(); ++eit){ if (contains_infinity(eit.current())){ return true; } } } return false; } Relation RangeComparator::compare(const Expression &e1, const Expression &e2) { /// silvius: there seems to be an error: /// compare(N, Inf) results in <=, but it should be < if (e1.op() == INFINITY_OP && !contains_infinity(e2)){ if (e1.sign()==-1){ /// ... < return Relation(true, false, false); } else { /// ... > return Relation(false, false, true); } } if (e2.op() == INFINITY_OP && !contains_infinity(e1)){ if (e2.sign()==1){ /// ... < return Relation(true, false, false); } else { /// ... > return Relation(false, false, true); } } if (e1==e2){ return Relation(false, true, false); } /// ... The method compare determines relationships between two expressions /// ... by subtracting one expression from the other, and testing whether this /// ... difference is less than, equal, or greater than zero. if (_debug_level >= 10) cout << "Comparing (" << e1 << ") to (" << e2 << ") {\n"; if (_stats) _stats->start_compare(); _begin_caching_expr_signs(); Relation rel; if (is_empty_range(e1) || is_empty_range(e2)) ; // Do nothing else if (e1.op() == INFINITY_OP) { /// ... Set main part of relation rel = Relation(((InfinityExpr *) &e1)->sign() <= 0, true, ((InfinityExpr *) &e1)->sign() >= 0); /// ... Now test for circularity if e2 is non-constant switch (e2.op()) { case INFINITY_OP: case INTEGER_CONSTANT_OP: case REAL_CONSTANT_OP: case LOGICAL_CONSTANT_OP: break; default: { Relation rel2 = _compare(e2.clone()); rel.circular(rel2.is_circular()); } } } else if (e2.op() == INFINITY_OP) { /// ... Set main part of relation rel = Relation(((InfinityExpr *) &e2)->sign() >= 0, true, ((InfinityExpr *) &e2)->sign() <= 0); /// ... Now test for circularity if e1 is non-constant switch (e1.op()) { case INFINITY_OP: case INTEGER_CONSTANT_OP: case REAL_CONSTANT_OP: case LOGICAL_CONSTANT_OP: break; default: { Relation rel1 = _compare(e1.clone()); rel.circular(rel1.is_circular()); } } } else { int diff = 0; if (_int_diff(e1, e2, diff)) rel = Relation(diff < 0, diff == 0, diff > 0); else rel = _compare(_build_delta(e1, e2)); } _end_caching_expr_signs(); if (_stats) _stats->end_compare(); if (_debug_level >= 10) cout << "} result(compare): (" << e1 << ") " << rel << " (" << e2 << ")\n"; return rel; } Relation RangeComparator::compare(const Expression &e1, int value) { if (_debug_level >= 10) cout << "Comparing (" << e1 << ") to (" << value << ") {\n"; if (_stats) _stats->start_compare(); _begin_caching_expr_signs(); Relation rel; if (is_empty_range(e1)) ; else if (e1.op() == INFINITY_OP) rel = Relation(((InfinityExpr *) &e1)->sign() <= 0, true, ((InfinityExpr *) &e1)->sign() >= 0); else { Expression *delta; if (value != 0) { Expression *value_expr = constant(value); delta = _build_delta(e1, *value_expr); delete value_expr; } else { delta = expr_expand_substituted(e1.clone()); delta = simplify(delta); } rel = _compare(delta); } _end_caching_expr_signs(); if (_stats) _stats->end_compare(); if (_debug_level >= 10) cout << "} result(compare): (" << e1 << ") " << rel << " (" << value << ")\n"; return rel; } /// _build_delta /// Compute the symbolic difference between the two expressions. Expression * RangeComparator::_build_delta(const Expression &e1, const Expression &e2) { Expression *delta; if (is_integer_zero(e2)) delta = e1.clone(); else delta = sub(e1.clone(), e2.clone()); if (e1.op() == RANGE_OP || e1.op() == OMEGA_OP || e2.op() == RANGE_OP || e2.op() == OMEGA_OP) delta = pull_ranges_out(delta, *this); delta = expr_expand_substituted(delta); delta = simplify(delta); delta = pull_min_max_out(delta, *this); if (is_min_or_max(*delta)) delta = simplify(delta); return delta; } /// _is_pos_max /// Return true if the given expression is a positive MAX expression static bool _is_pos_max(const Expression &e) { if (is_max(e)) { Iterator<Expression> iter = e.parameters_guarded().arg_list(); for ( ; iter.valid(); ++iter) { const Expression &arg = iter.current(); if (arg.op() == INTEGER_CONSTANT_OP && arg.value() > 0) return true; } } return false; } /// _is_neg_min /// Return true if the given expression is a negative MIN expression static bool _is_neg_min(const Expression &e) { if (is_min(e)) { Iterator<Expression> iter = e.parameters_guarded().arg_list(); for ( ; iter.valid(); ++iter) { const Expression &arg = iter.current(); if (arg.op() == INTEGER_CONSTANT_OP && arg.value() < 0) return true; } } return false; } /// _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. static bool _is_comparable(const Expression &e) { if (e.op() == INTEGER_CONSTANT_OP || e.op() == OMEGA_OP) return true; /// ... <integer>**<expr> else if ((e.op() == EXP_OP) && (e.left_guarded().op() == INTEGER_CONSTANT_OP)) return true; /// ... for addition or multiplication, all terms must be comparable else if ((e.op() == MULT_OP) || (e.op() == ADD_OP)) { bool comp = true; for (Iterator<Expression> iter = e.arg_list(); iter.valid(); ++iter) { Expression & subexp = iter.current(); comp = comp && _is_comparable( subexp ); } return comp; } else if (e.op() == RANGE_OP) { RangeExpr &range = * (RangeExpr *) &e; if (is_empty_range(e)) return true; else if ((! range.has_lb() || range.lb().op() == INTEGER_CONSTANT_OP) && (! range.has_ub() || range.ub().op() == INTEGER_CONSTANT_OP)) return true; else if (range.has_lb() && ((range.lb().op() == INTEGER_CONSTANT_OP && range.lb().value() > 0) || _is_pos_max(range.lb()))) return true; else if (range.has_ub() && ((range.ub().op() == INTEGER_CONSTANT_OP && range.ub().value() < 0) || _is_neg_min(range.ub()))) return true; } return false; } /// _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 static Relation _determine_relation(const Expression &delta, bool dummy_range_just_substituted, RangeComparator * comp) { Relation relation; if (delta.op() == INTEGER_CONSTANT_OP) { if (delta.value() < 0) relation.less_than(true); else if (delta.value() > 0) relation.greater_than(true); else relation.equal(true); } else if ((delta.op() == EXP_OP) && (delta.left_guarded().op() == INTEGER_CONSTANT_OP)) { if (delta.left_guarded().value() >= 0) relation.greater_than(true); else if (delta.right_guarded().op() == INTEGER_CONSTANT_OP) { if ((abs(delta.right_guarded().value()) / 2 * 2) == abs(delta.right_guarded().value())) { relation.greater_than(true); } } } else if (delta.op() == MULT_OP) { int c=1; for (Iterator<Expression> iter = delta.arg_list(); iter.valid(); ++iter) { Expression & subexp = iter.current(); Relation r = _determine_relation(subexp, dummy_range_just_substituted, comp); if (r.is_less_than()) { c *= -1; } else if (r.is_equal()) { c = 0; } else if (r.is_greater_than()) { } else { /// ... unknown c *= 2; } } if (c == 0) { relation.equal(true); } else if (c == 1) { relation.greater_than(true); } else if (c == -1) { relation.less_than(true); } } else if (delta.op() == ADD_OP) { bool less = false; bool grtr = false; bool zero = false; bool unknown = false; int minus_one_count = 0; int pos_exp_count = 0; for (Iterator<Expression> iter = delta.arg_list(); iter.valid(); ++iter) { Expression & subexp = iter.current(); Relation r = _determine_relation(subexp, dummy_range_just_substituted, comp); if (r.is_less_than()) { less = true; if (is_integer_constant(subexp, -1)) { minus_one_count++; } } else if (r.is_greater_than()) { grtr = true; if (subexp.op() == EXP_OP) { pos_exp_count++; } } else if (r.is_equal()) { zero = true; } else { unknown = true; } } if (less && !grtr && !zero && !unknown) { relation.less_than(true); } else if (grtr && !less && !zero && !unknown) { relation.greater_than(true); } else if (zero && !less && !grtr && !unknown) { relation.equal(true); } else { /// ... if it's all (-1) and (x**y) terms, use fact that x**y is >=1 if (minus_one_count+pos_exp_count == delta.arg_list().entries()) { if (pos_exp_count>minus_one_count) { relation.greater_than(true); } else if (pos_exp_count == minus_one_count) { relation.greater_than(true); relation.equal(true); } } else /// ... Check for difference of 2 exponentials if ((delta.arg_list().entries() == 2) && less && grtr) { const Expression & left = delta.arg_list()[0]; const Expression & right = delta.arg_list()[1]; if ((left.op() == MULT_OP) && (left.arg_list()[0].op() == INTEGER_CONSTANT_OP) && (left.arg_list()[0].value() == -1) && (left.arg_list()[1].op() == EXP_OP) && (left.arg_list()[1].arg_list()[0].op() == INTEGER_CONSTANT_OP) && (right.op() == EXP_OP) && (right.arg_list()[0].op() == INTEGER_CONSTANT_OP)) { /// ... make sure the bases of the exponentials are equal if (left.arg_list()[1].arg_list()[0].value() == right.arg_list()[0].value()) { Relation r = comp->compare(right.arg_list()[1], left.arg_list()[1].arg_list()[1]); } } else if ((right.op() == MULT_OP) && (right.arg_list()[0].op() == INTEGER_CONSTANT_OP) && (right.arg_list()[0].value() == -1) && (right.arg_list()[1].op() == EXP_OP) && (right.arg_list()[1].arg_list()[0].op() == INTEGER_CONSTANT_OP) && (left.op() == EXP_OP) && (left.arg_list()[0].op() == INTEGER_CONSTANT_OP)) { /// ... make sure the bases of the exponentials are equal if (right.arg_list()[1].arg_list()[0].value() == left.arg_list()[0].value()) { Relation r = comp->compare(left.arg_list()[1], right.arg_list()[1].arg_list()[1]); relation = r; } } } } } else if (is_unbounded_range(delta)) { relation.circular(dummy_range_just_substituted); } else if (delta.op() != RANGE_OP || is_empty_range(delta)) ; // Return an undefined range. else { const RangeExpr &range = * (const RangeExpr *) &delta; int lb_val = INT_MIN; int ub_val = INT_MAX; if (range.has_lb()) if (range.lb().op() == INTEGER_CONSTANT_OP) lb_val = range.lb().value(); else if (_is_pos_max(range.lb())) lb_val = 1; if (range.has_ub()) if (range.ub().op() == INTEGER_CONSTANT_OP) ub_val = range.ub().value(); else if (_is_neg_min(range.ub())) ub_val = -1; if (lb_val > ub_val) ; /// ... Unknown relationship else if (lb_val < 0) { relation.less_than(true); relation.equal(ub_val >= 0); relation.greater_than(ub_val > 0); } else if (lb_val == 0) { relation.equal(true); relation.greater_than(ub_val > 0); } else relation.greater_than(true); } return relation; } /// vars_in_expr /// Return the set of variables that occur in the given expression. static void _vars_in_expr(RefSet<Symbol> &vars, const Expression &expr) { if (expr.op() == ID_OP) { if (expr.symbol().sym_class() == VARIABLE_CLASS) vars.ins(expr.symbol()); } else { Iterator<Expression> iter = expr.arg_list(); for ( ; iter.valid(); ++iter) _vars_in_expr(vars, iter.current()); } } /// _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. static void _find_visit_order(RefList<Symbol> &ordered_vars, const RefSet<Symbol> &vars, RangeComparator &comparator) { RefSet<Symbol> unconstrained; RefSet<Symbol> equal_ranges; RefSet<Symbol> simple_ranges; RefSet<Symbol> ranges; RefSet<Symbol> equal_min_max_ranges; RefSet<Symbol> min_max_ranges; Iterator<Symbol> var_iter = vars; for ( ; var_iter.valid(); ++var_iter) { Symbol &var = var_iter.current(); const Expression *range_expr = comparator.get_range_ref(var); if (! range_expr) unconstrained.ins(var); else if (range_expr->op() != RANGE_OP) { if (is_min_or_max(*range_expr)) equal_min_max_ranges.ins(var); else equal_ranges.ins(var); } else { const RangeExpr &range = * (const RangeExpr *) range_expr; if ((! range.has_lb() || range.lb().op() == INTEGER_CONSTANT_OP || range.lb().op() == ID_OP) && (! range.has_ub() || range.ub().op() == INTEGER_CONSTANT_OP || range.ub().op() == ID_OP)) simple_ranges.ins(var); else if ((range.has_lb() && is_min_or_max(range.lb())) || (range.has_lb() && is_min_or_max(range.lb()))) min_max_ranges.ins(var); else ranges.ins(var); } } for (var_iter = unconstrained; var_iter.valid(); ++var_iter) ordered_vars.ins_first(var_iter.current()); for (var_iter = equal_ranges; var_iter.valid(); ++var_iter) ordered_vars.ins_first(var_iter.current()); for (var_iter = simple_ranges; var_iter.valid(); ++var_iter) ordered_vars.ins_first(var_iter.current()); for (var_iter = ranges; var_iter.valid(); ++var_iter) ordered_vars.ins_first(var_iter.current()); for (var_iter = equal_min_max_ranges; var_iter.valid(); ++var_iter) ordered_vars.ins_first(var_iter.current()); for (var_iter = min_max_ranges; var_iter.valid(); ++var_iter) ordered_vars.ins_first(var_iter.current()); } /// _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. static void _generate_subst_order1(RefList<Symbol> &subst_order, const Expression &e, RangeComparator &comparator, RefSet<Symbol> &visited) { RefSet<Symbol> vars; _vars_in_expr(vars, e); RefList<Symbol> ordered_vars; _find_visit_order(ordered_vars, vars, comparator); Iterator<Symbol> var_iter = ordered_vars; for ( ;var_iter.valid(); ++var_iter) { Symbol &var = var_iter.current(); if (! visited.member(var)) { visited.ins(var); const Expression *range = comparator.get_range_ref(var); if (range) _generate_subst_order1(subst_order, *range, comparator, visited); subst_order.ins_first(var); } } } static void _generate_subst_order1(RefList<Symbol> &subst_order, const Expression &e, RangeComparator &comparator) { RefSet<Symbol> visited; _generate_subst_order1(subst_order, e, comparator, visited); } /// build_range_use_set /// For each variable, build a set all variables whose ranges contain /// that variable. static void _build_range_use_set(Map<Symbol, RefSet<Symbol> > &range_use_set, const RefList<Symbol> &candidate_vars, RangeComparator &comparator) { Iterator<Symbol> cand_iter = candidate_vars; for ( ; cand_iter.valid(); ++cand_iter) { Symbol &cand_var = cand_iter.current(); const Expression *range = comparator.get_range_ref(cand_var); if (range) { RefSet<Symbol> vars_used; _vars_in_expr(vars_used, *range); Iterator<Symbol> used_iter = vars_used; for ( ; used_iter.valid(); ++used_iter) { Symbol &used_var = used_iter.current(); RefSet<Symbol> *use_set = range_use_set.find_ref(used_var); if (! use_set) { use_set = new RefSet<Symbol>; range_use_set.ins(used_var, use_set); } use_set->ins(cand_var); } } } } /// _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. 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) { if (! scc.member(CASTAWAY(Symbol &) root_var)) { scc.ins(CASTAWAY(Symbol &) root_var); const RefSet<Symbol> *predecessors = reversed_edges.find_ref(root_var); if (predecessors) { Iterator<Symbol> pred_iter = *predecessors; for ( ; pred_iter.valid(); ++pred_iter) if (rev_topological_order.member(pred_iter.current())) _find_scc_from_list(scc, rev_topological_order, pred_iter.current(), reversed_edges); } } } 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) { RefSet<Symbol> scc_set; _find_scc_from_list(scc_set, rev_topological_order, root_var, reversed_edges); if (scc_set.entries() == 1) scc.ins_last(rev_topological_order.grab(scc_set.grab())); else { Mutator<Symbol> rto_iter = rev_topological_order; for ( ; rto_iter.valid(); ++rto_iter) if (scc_set.member(rto_iter.current())) scc.ins_last(rev_topological_order.grab(rto_iter.current())); } p_assert(scc.entries() > 0, "_grab_scc_from_list returned an empty SCC."); } /// _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. static void _generate_subst_order(RefList<Symbol> &subst_order, const Expression &e, RangeComparator &comparator) { RefList<Symbol> acyclic_subst_order; _generate_subst_order1(acyclic_subst_order, e, comparator); Map<Symbol, RefSet<Symbol> > range_use_set; _build_range_use_set(range_use_set, acyclic_subst_order, comparator); while (acyclic_subst_order.entries() > 0) { Symbol &var = acyclic_subst_order.grab(0); acyclic_subst_order.ins_first(var); RefList<Symbol> scc; _grab_scc_from_list(scc, acyclic_subst_order, var, range_use_set); if (scc.entries() == 1) subst_order.ins_last(scc.grab()); else { /// ... SCC has more than one variable, so add each variable in it /// ... twice. Iterator<Symbol> scc_iter = scc; for ( ; scc_iter.valid(); ++scc_iter) subst_order.ins_last(scc_iter.current()); for (scc_iter.reset(); scc_iter.valid(); ++scc_iter) subst_order.ins_last(scc_iter.current()); } } } /// _replace_vars_with_omega /// Replace all variables in the expresion with omega expressions. static Expression * _replace_vars_with_omega(Expression * e) { if (! e) return e; if (e->op() == ID_OP && (e->symbol().sym_class() == VARIABLE_CLASS || e->symbol().sym_class() == SYMBOLIC_CONSTANT_CLASS)) { delete e; return omega(); } else if (e->op() == ARRAY_REF_OP || e->op() == INTRINSIC_CALL_OP || e->op() == FUNCTION_CALL_OP) { Expression &params = *e->arg_list().last_ref(); Assign<Expression> eas(e->arg_list().assign(params)); eas = _replace_vars_with_omega(e->arg_list().pull(params)); } else { Mutator<Expression> iter(e->arg_list()); for ( ; iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); eas = _replace_vars_with_omega(iter.pull()); } } return e; } /// _num_var_occurrences_in_expr /// Return the number of times that the given variable occurs in the /// given expression. static int _num_var_occurrences_in_expr(const Expression &expr, const Symbol &var) { int num_occurrences = 0; if (expr.op() == ID_OP) { if (&var == &expr.symbol()) num_occurrences = 1; } else { Iterator<Expression> iter = expr.arg_list(); for ( ; iter.valid(); ++iter) num_occurrences += _num_var_occurrences_in_expr(iter.current(), var); } return num_occurrences; } /// _remove_truncates /// Replace all subexpressions of the form B*(A/B) with A - MOD(A, B) in /// the given expression. static Expression * _remove_truncates1(Expression *expr, const Symbol &var, bool &changed, Symtab &symtab) { /// ... Remove any truncates from my arguments. changed = false; Mutator<Expression> arg_iter = expr->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) { bool arg_changed; Assign<Expression> eas(arg_iter.assign()); eas = _remove_truncates1(arg_iter.pull(), var, arg_changed, symtab); changed = changed || arg_changed; } /// ... Remove any top-level truncates. if (expr->op() == MULT_OP) { /// ... Collect all divisions in the multiplication. List<Expression> div_args; Mutator<Expression> arg_iter = expr->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) if (arg_iter.current().op() == DIV_OP && is_var_in_expr(arg_iter.current(), var)) div_args.ins_last(arg_iter.grab()); /// ... Eliminate as many of these divisions as possible. if (expr->arg_list().entries() > 0) { bool merged_a_truncate = true; while (div_args.entries() > 0 && merged_a_truncate) { merged_a_truncate = false; Mutator<Expression> div_iter = div_args; for ( ; div_iter.valid(); ++div_iter) { Expression &curr_div = div_iter.current(); Expression *mod = mod_expr(expr->clone(), curr_div.right_guarded().clone(), symtab); mod = simplify(mod); if (is_integer_zero(*mod)) { expr = div(expr, curr_div.right_guarded().clone()); Expression *trunc_arg = curr_div.left_guarded().clone(); if (curr_div.right_guarded().op() != INTEGER_CONSTANT_OP || ! is_evenly_divisible(curr_div.left_guarded(), curr_div.right_guarded().value())) trunc_arg = sub(trunc_arg, mod_expr(curr_div.grab_left(), curr_div.grab_right(), symtab)); expr = mul(expr, trunc_arg); div_iter.del(); merged_a_truncate = true; changed = true; } delete mod; } } } /// ... Put the remaining divisions back into the multiplication expr. if (expr->op() != MULT_OP) expr = new NonBinaryExpr(MULT_OP, expr->type(), expr); while (div_args.entries() > 0) expr->arg_list().ins_last(div_args.grab(0)); } return expr; } Expression * RangeComparator::_remove_truncates(Expression *expr, const Symbol &var) { if (expr) { bool changed; expr = _remove_truncates1(expr, var, changed, (Symtab &) symtab()); if (changed) { expr = simplify(expr); if (debug_level() >= 20) cout << " delta = (" << *expr << ")" << " after eliminating truncations for " << var.name_ref() << endl; } } return expr; } /// _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. static Expression * _multiply_out_div(Expression *expr, Expression *& factor, RangeComparator &comparator) { p_assert(expr->op() == DIV_OP, "_multiply_out_div() expects a division expression."); factor = 0; EXPR_SIGN denom_sign = comparator.signz(expr->right_guarded()); if (denom_sign == POS_NEG_EXPR || denom_sign == ZERO_EXPR) return expr; Expression *new_expr = expr->grab_left(); factor = expr->grab_right(); delete expr; if (factor->op() != INTEGER_CONSTANT_OP || ! is_evenly_divisible(*new_expr, factor->value())) new_expr = sub(new_expr, mod_expr(new_expr->clone(), factor->clone(), (Symtab &) comparator.symtab())); if (denom_sign == NEG_EXPR) { new_expr = unary_minus(new_expr); factor = unary_minus(factor); } return new_expr; } /// _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. static Expression * _multiply_out_divs_for_var1(Expression *expr, const Symbol &var, Expression *& factor, bool multiply_out_divs, RangeComparator &comparator) { factor = 0; if (! expr) return expr; switch (expr->op()) { case DIV_OP: { if (multiply_out_divs && is_var_in_expr(*expr, var)) expr = _multiply_out_div(expr, factor, comparator); } break; case EXP_OP: { const Expression &power = expr->right_guarded(); if (expr->left_guarded().op() == DIV_OP && power.op() == INTEGER_CONSTANT_OP && power.value() > 0) { expr->left(_multiply_out_divs_for_var1(expr->grab_left(), var, factor, multiply_out_divs, comparator)); } if (factor) factor = exponent(factor, power.clone()); } break; case MULT_OP: { if (! multiply_out_divs) if (_num_var_occurrences_in_expr(*expr, var) >= 2) multiply_out_divs = true; else return expr; Mutator<Expression> term_iter = expr->arg_list(); for ( ; term_iter.valid(); ++term_iter) { Expression *term_factor = 0; Assign<Expression> eas(term_iter.assign()); eas = _multiply_out_divs_for_var1(term_iter.pull(), var, term_factor, multiply_out_divs, comparator); if (term_factor) if (factor) factor = mul(factor, term_factor); else factor = term_factor; } } break; case ADD_OP: case RANGE_OP: case INTRINSIC_CALL_OP: { if (expr->op() == INTRINSIC_CALL_OP && ! is_min_or_max(*expr)) return expr; if (! multiply_out_divs && expr->op() == ADD_OP) if (_num_var_occurrences_in_expr(*expr, var) >= 2) multiply_out_divs = true; else return expr; List<Expression> *args; if (expr->op() == INTRINSIC_CALL_OP) args = &expr->parameters_guarded().arg_list(); else args = &expr->arg_list(); RefList<Expression> visited_args; Mutator<Expression> arg_iter = *args; for ( ; arg_iter.valid(); ++arg_iter) { Assign<Expression> argas(arg_iter.assign()); Expression *arg = arg_iter.pull(); Expression *arg_factor = 0; arg = _multiply_out_divs_for_var1(arg, var, arg_factor, multiply_out_divs, comparator); /// ... If a new factor was generated by this argument, multiply all /// ... previously visited arguments with this new factor. if (factor) arg = mul(factor->clone(), arg); if (arg_factor) { Iterator<Expression> visited_iter = visited_args; for ( ; visited_iter.valid(); ++visited_iter) { Assign<Expression> eas(args->assign(visited_iter.current())); eas = mul(arg_factor->clone(), args->pull(visited_iter.current())); } if (factor) factor = mul(factor, arg_factor); else factor = arg_factor; } argas = arg; visited_args.ins_last(*arg); } } break; default: /// ... Do nothing; break; } return expr; } static Expression * _multiply_out_divs_for_var(Expression *expr, const Symbol &var, RangeComparator &comparator) { if (! expr) return expr; Expression *factor = 0; bool multiply_out_divs = false; expr = _multiply_out_divs_for_var1(expr, var, factor, multiply_out_divs, comparator); if (factor) { /// ... If factor is non-NULL, then at least one division expression was /// ... eliminated from the expression. So simplify it. delete factor; expr = simplify(expr); if (comparator.debug_level() >= 20) cout << " delta = (" << *expr << ")" << " after multiplying out divisions for " << var.name_ref() << endl; } return expr; } /// _compare Relation RangeComparator::_compare(Expression *delta) { if (_debug_level >= 20) cout << " delta = (" << *delta << ")\n"; bool dummy_range_just_substituted = false; if (! _is_comparable(*delta)) { /// ... Eliminate all constrained variables in the expression by /// ... repeatedly substituting a variable with its range, moving the /// ... ranges out so the expression containes no inner ranges /// ... and simplifying. RefList<Symbol> subst_order; _generate_subst_order(subst_order, *delta, *this); while(! _is_comparable(*delta) && subst_order.entries() > 0) { dummy_range_just_substituted = false; Symbol &var = subst_order[0]; subst_order.del(var); /// ... Substitute variable's range into the expression, move the /// ... ranges outwards so that there are no more inner ranges, /// ... then simplify. if (is_var_in_expr(*delta, var)) { const Expression *range = get_range_ref(var); CompareData &compare_data = _compare_data(var); if (range) { if (is_unbounded_range(*range)) { dummy_range_just_substituted = true; range = 0; } else { if (compare_data.num_subst >= MAX_SUBST) range = 0; } } ++compare_data.num_subst; if (range && range->op() == RANGE_OP) { delta = _remove_truncates(delta, var); delta = _multiply_out_divs_for_var(delta, var, *this); } delta = subst_var_and_simplify(delta, var, range); --compare_data.num_subst; if (_debug_level >= 20) { cout << " delta = (" << *delta << ")" << " after substituting " << var.name_ref() << " = ("; if (range) cout << *range; else cout << "[-Inf:Inf]"; cout << ")\n"; } } } if (! _is_comparable(*delta)) { /// ... Expression contains unconstrained variables. So, replace /// ... all variables with omega, bubble these omega expressions up /// ... through the expression, and simplify. delta = _replace_vars_with_omega(delta); delta = pull_ranges_out(delta, *this); delta = simplify(delta); if (_debug_level >= 20) cout << " delta = (" << *delta << ")" << " after eliminating vars\n"; } } /// ... Now, determine the relationships of the simplified expression. /// ... If the expression is omega and a dummy range was just substituted, /// ... indicate that a circular reference was found. Otherwise, if the /// ... the expression is omega or is still not comparable, the default /// ... relationship is returned. (By default, no relationship is known.) Relation rel = _determine_relation(*delta, dummy_range_just_substituted, this); delete delta; return rel; } /// sign EXPR_SIGN RangeComparator::sign(const Expression &e) { EXPR_SIGN sign = signz(e); if (sign == ZERO_EXPR) return POS_EXPR; return sign; } EXPR_SIGN RangeComparator::signz(const Expression &e) { EXPR_SIGN my_sign = POS_NEG_EXPR; switch (e.op()) { case ARRAY_REF_OP: my_sign = POS_NEG_EXPR; break; case RANGE_OP: { RangeExpr &range = * (RangeExpr *) &e; EXPR_SIGN lb_sign = signz(range.lb()); if (lb_sign == POS_EXPR) my_sign = POS_EXPR; else { EXPR_SIGN ub_sign = signz(range.ub()); if (ub_sign == NEG_EXPR) my_sign = NEG_EXPR; else if (lb_sign == ZERO_EXPR && ub_sign == ZERO_EXPR) my_sign = ZERO_EXPR; else if (lb_sign == ZERO_EXPR) my_sign = POS_EXPR; else if (ub_sign == ZERO_EXPR) my_sign = NEG_EXPR; } } break; case ID_OP: { const Expression *range = get_range_ref(e.symbol()); if (range) { CompareData &compare_data = _compare_data(e.symbol()); if (compare_data.sign_cache == PENDING) my_sign = POS_NEG_EXPR; else if (compare_data.sign_cache != UNKNOWN_SIGN) my_sign = compare_data.sign_cache; else { compare_data.sign_cache = PENDING; my_sign = signz(*range); compare_data.sign_cache = my_sign; } } } break; case INTEGER_CONSTANT_OP: if (e.value() > 0) my_sign = POS_EXPR; else if (e.value() == 0) my_sign = ZERO_EXPR; else my_sign = NEG_EXPR; break; case INFINITY_OP: my_sign = (((InfinityExpr *) &e)->sign() >= 0) ? POS_EXPR : NEG_EXPR; break; case MULT_OP: { my_sign = POS_EXPR; Iterator<Expression> arg_iter = e.arg_list(); for ( ; arg_iter.valid() && my_sign != POS_NEG_EXPR; ++arg_iter) { Expression &arg = arg_iter.current(); if (e.arg_list().next_ref(arg) && arg == *e.arg_list().next_ref(arg)) { /// ... Skip pairs of terms of the form N*N, since they are /// ... always positive. ++arg_iter; } else { EXPR_SIGN arg_sign = signz(arg); if (arg_sign == NEG_EXPR) my_sign = flip_sign(my_sign); else if (arg_sign == ZERO_EXPR) my_sign = ZERO_EXPR; else if (arg_sign == POS_NEG_EXPR) my_sign = POS_NEG_EXPR; } } } break; case DIV_OP: { my_sign = signz(e.left_guarded()); if (my_sign == POS_EXPR || my_sign == NEG_EXPR) { EXPR_SIGN denom_sign = signz(e.right_guarded()); if (denom_sign == POS_NEG_EXPR || denom_sign == ZERO_EXPR) my_sign = POS_NEG_EXPR; else if (denom_sign == NEG_EXPR) my_sign = flip_sign(my_sign); } } break; case EXP_OP: { if (e.right_guarded().op() == INTEGER_CONSTANT_OP) { if (e.right_guarded().value() == 0) my_sign = POS_EXPR; else { EXPR_SIGN base_sign = signz(e.left_guarded()); if (base_sign == ZERO_EXPR || base_sign == POS_EXPR) my_sign = base_sign; else if (e.right_guarded().value() % 2 == 0) my_sign = POS_EXPR; else my_sign = base_sign; } } } break; default: { if (is_max(e)) { my_sign = UNKNOWN_SIGN; Iterator<Expression> arg_iter = e.parameters_guarded().arg_list(); for ( ; arg_iter.valid() && my_sign != POS_EXPR; ++arg_iter) { EXPR_SIGN arg_sign = signz(arg_iter.current()); if (my_sign == UNKNOWN_SIGN || my_sign == NEG_EXPR) my_sign = arg_sign; else if (arg_sign == POS_EXPR) my_sign = POS_EXPR; else if (arg_sign == ZERO_EXPR) { if (my_sign == POS_NEG_EXPR) my_sign = POS_EXPR; } } if (my_sign == UNKNOWN_SIGN) my_sign = POS_NEG_EXPR; } else if (is_min(e)) { my_sign = UNKNOWN_SIGN; Iterator<Expression> arg_iter = e.parameters_guarded().arg_list(); for ( ; arg_iter.valid() && my_sign != NEG_EXPR; ++arg_iter) { EXPR_SIGN arg_sign = signz(arg_iter.current()); if (my_sign == UNKNOWN_SIGN || my_sign == POS_EXPR) my_sign = arg_sign; else if (arg_sign == NEG_EXPR) my_sign = NEG_EXPR; else if (arg_sign == ZERO_EXPR) { if (my_sign == POS_NEG_EXPR) my_sign = NEG_EXPR; } } if (my_sign == UNKNOWN_SIGN) my_sign = POS_NEG_EXPR; } else if (is_mod(e)) { my_sign = signz(e.parameters_guarded().arg_list()[0]); } else if (is_abs(e)) { my_sign = signz(e.parameters_guarded().arg_list()[0]); if (my_sign != ZERO_EXPR && my_sign != POS_EXPR) my_sign = POS_EXPR; } else { const Expression *cached_expr = _cached_sign_exprs.representative(CASTAWAY(Expression &) e); if (cached_expr) my_sign = (EXPR_SIGN) _cached_expr_signs[*cached_expr].value(); else { Relation rel = compare(e, 0); if (rel.is_equal()) my_sign = ZERO_EXPR; else if (rel.is_greater_equal()) my_sign = POS_EXPR; else if (rel.is_less_equal()) my_sign = NEG_EXPR; if (_cache_expr_signs > 0) { cached_expr = &_cached_sign_exprs.ins(e.clone()); _cached_expr_signs.ins(*cached_expr, new IntElem((int) my_sign)); } } } } break; } if (_debug_level >= 10) { cout << "Sign of (" << e << ") is "; switch (my_sign) { case POS_EXPR: cout << "positive\n"; break; case NEG_EXPR: cout << "negative\n"; break; case ZERO_EXPR: cout << "zero\n"; break; default: cout << "unknown\n"; break; } } return my_sign; } /// 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,...). static Expression * _forward_diff(const Expression &e, const Symbol &var) { Expression *var_plus_1 = add(constant(1), id(CASTAWAY(Symbol &) var)); Expression *expr_step = substitute_var(e.clone(), var, *var_plus_1); delete var_plus_1; return simplify(sub(expr_step, e.clone())); } /// var_power_in_expr /// Return the maximum power of the given variable in the given expression. static int _var_power_in_expr(const Expression &expr, const Symbol &var) { int var_power = 0; switch (expr.op()) { case ID_OP: if (&expr.symbol() == &var) var_power = 1; break; case MULT_OP: { Iterator<Expression> arg_iter = expr.arg_list(); for ( ; arg_iter.valid(); ++arg_iter) var_power += _var_power_in_expr(arg_iter.current(), var); } break; case EXP_OP: var_power = _var_power_in_expr(expr.left_guarded(), var); if (expr.right_guarded().op() == INTEGER_CONSTANT_OP) var_power = var_power * expr.right_guarded().value(); break; default: { Iterator<Expression> arg_iter = expr.arg_list(); for ( ; arg_iter.valid(); ++arg_iter) { int arg_power = _var_power_in_expr(arg_iter.current(), var); var_power = max(var_power, arg_power); } } break; } return var_power; } /// monotonicity_for_var /// Return whether the given expression is monotonically increasing or /// decreasing for the given variable. enum _MONO_STATE { _NON_MONO, /// ... Expression is not monotonic _MONO_DEC, /// ... Expression is monotonically decreasing _MONO_INC, /// ... Expression is monotonically increasing }; static _MONO_STATE _monotonicity_for_var(const Expression &expr, const Symbol &var, RangeComparator &comparator) { if (comparator.debug_level() >= 30) cout << " testing monotonicity of " << expr << " for " << var.name_ref() << endl; _MONO_STATE mono = _NON_MONO; int var_power = _var_power_in_expr(expr, var); Expression *diff = _forward_diff(expr, var); int diff_power = _var_power_in_expr(*diff, var); if (abs(diff_power) < abs(var_power)) { switch (comparator.sign(*diff)) { case POS_EXPR: mono = _MONO_INC; break; case NEG_EXPR: mono = _MONO_DEC; break; default: mono = _NON_MONO; break; } } delete diff; return mono; } /// 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. This method /// uses the given monotonicity information to substitute expressions /// containing mins and maxes at their top level more accurately. static Expression * _substitute_mono_var1(Expression *expr, const Symbol &var, const Expression &mono_function, bool var_is_mono_inc, const Symtab &symtab) { Expression *new_expr = 0; if (! is_min_or_max(*expr)) { new_expr = substitute_var(mono_function.clone(), var, *expr); delete expr; } else { if (! var_is_mono_inc) swap_min_max(*expr, symtab); Mutator<Expression> arg_iter = expr->parameters_guarded().arg_list(); for ( ; arg_iter.valid(); ++arg_iter) { Assign<Expression> eas(arg_iter.assign()); eas = _substitute_mono_var1(arg_iter.pull(), var, mono_function, var_is_mono_inc, symtab); } new_expr = expr; } return new_expr; } static Expression * _substitute_mono_var(Expression *expr, const Symbol &var, const Expression &subst_expr, bool var_is_mono_inc, const Symtab &symtab) { Expression *new_expr = 0; if (! is_min_or_max(subst_expr)) new_expr = substitute_var(expr, var, subst_expr); else { new_expr = _substitute_mono_var1(subst_expr.clone(), var, *expr, var_is_mono_inc, symtab); delete expr; } return new_expr; } /// solve_monotonic /// If the given expression is monotonically increasing or monotonically /// decreasing for the given variable, calculate the resulting range of /// the expression by substituting the lower and upper bounds of the /// variables range into the expression. If this function fails, it /// returns NULL. Expression * RangeComparator::_solve_monotonic(Expression *expr, const Symbol &var, const RangeExpr &subst_range) { Expression *new_expr = 0; CompareData &compare_data = _compare_data(var); --compare_data.num_subst; _MONO_STATE mono = _monotonicity_for_var(*expr, var, *this); ++compare_data.num_subst; if (mono != _NON_MONO) { if (_debug_level >= 30) cout << " solve_monotonic(expr=" << *expr << ", var=" << var.name_ref() << ", subst_range=" << subst_range << ") = "; Expression *bound1 = 0; Expression *bound2 = 0; if (subst_range.has_lb()) bound1 = _substitute_mono_var(expr->clone(), var, subst_range.lb(), mono == _MONO_INC, symtab()); if (subst_range.has_ub()) bound2 = _substitute_mono_var(expr, var, subst_range.ub(), mono == _MONO_INC, symtab()); else delete expr; if (mono == _MONO_INC) new_expr = new RangeExpr(bound1, bound2); else new_expr = new RangeExpr(bound2, bound1); if (_debug_level >= 30) cout << *new_expr << endl; } return new_expr; } /// subst_mods_with_var /// Replace the left hand side of modulo operations that contain the given /// variable with the given expression. Return true if the expression /// contained such a modulo operation static bool _subst_mods_with_var(Expression &expr, const Symbol &var, const Expression &subst_expr) { bool has_mods_with_var = false; if (expr.op() == INTRINSIC_CALL_OP && strcmp(expr.intrinsic().symbol().name_ref(), "MOD") == 0 && is_var_in_expr(expr.parameters_guarded(), var)) { Assign<Expression> eas(expr.parameters_guarded().arg_list().assign(0)); eas = substitute_var(expr.parameters_guarded().arg_list().pull(0), var, subst_expr); has_mods_with_var = true; } else { Iterator<Expression> arg_iter = expr.arg_list(); for ( ; arg_iter.valid(); ++arg_iter) { bool arg_has_mods_with_var = _subst_mods_with_var(arg_iter.current(), var, subst_expr); has_mods_with_var = has_mods_with_var || arg_has_mods_with_var; } } return has_mods_with_var; } /// remove_mods_with_var /// Transform all modulo operations that contain the given variable into /// ranges. static Expression * _remove_mods_with_var(Expression *expr, const Symbol &var, const Expression &subst_expr, RangeComparator &comparator) { bool has_mods_with_var = _subst_mods_with_var(*expr, var, subst_expr); if (has_mods_with_var) { expr = pull_ranges_out(expr, comparator); expr = pull_min_max_out(expr, comparator); expr = simplify(expr); } return expr; } /// _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. static Expression * _member_exp_ref(Expression &expr, const Symbol &var) { if (expr.op() == ID_OP && &expr.symbol() == &var) return &expr; else if (expr.op() == EXP_OP && expr.left_guarded().op() == ID_OP && &expr.left_guarded().symbol() == &var && expr.right_guarded().op() == INTEGER_CONSTANT_OP && expr.right_guarded().value() > 0) return &expr; else if (expr.op() == MULT_OP) { Iterator<Expression> iter = expr.arg_list(); for ( ; iter.valid(); ++iter) if (iter.current().op() != MULT_OP) { Expression *arg_member = _member_exp_ref(iter.current(), var); if (arg_member) return arg_member; } } return 0; } /// _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". static Expression * _factor_out_var_top(Expression *expr, const Symbol &var) { Expression *new_expr = expr; if (expr->op() == ADD_OP) { Set<Expression> args_with_var; Mutator<Expression> arg_iter = expr->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) if (_member_exp_ref(arg_iter.current(), var)) args_with_var.ins(arg_iter.grab()); if (args_with_var.entries() == 1) expr->arg_list().ins_last(args_with_var.grab()); else if (args_with_var.entries() > 1) { Expression *factored_expr = new NonBinaryExpr(ADD_OP, expr->type()); while (args_with_var.entries()) { Expression *arg = args_with_var.grab(); Expression *factored_arg = 0; if (arg->op() == ID_OP) { delete arg; factored_arg = constant(1); } else if (arg->op() == MULT_OP) { Expression *term = _member_exp_ref(*arg, var); p_assert(term, "Internal error."); if (term->op() == ID_OP) arg->arg_list().del(*term); else { p_assert(term->op() == EXP_OP, "Internal error."); int power = term->right_guarded().value(); -- power; term->right_guarded().value(power); if (power == 0) arg->arg_list().del(*term); else if (power == 1) arg->arg_list().modify(*term, term->grab_left()); } if (arg->arg_list().entries() == 1) { factored_arg = arg->arg_list().grab(*arg->arg_list().first_ref()); delete arg; } else factored_arg = arg; } else if (arg->op() == EXP_OP) { int power = arg->right_guarded().value(); --power; arg->right_guarded().value(power); if (power == 0) { delete arg; factored_arg = constant(1); } else if (power == 1) { factored_arg = arg->grab_left(); delete arg; } else factored_arg = arg; } else p_abort("_factor_out_var_top() attempted to factor a non-scalar variable."); factored_expr->arg_list().ins_last(factored_arg); } factored_expr = _factor_out_var_top(factored_expr, var); factored_expr = mul(id(CASTAWAY(Symbol &) var), factored_expr); if (expr->arg_list().entries() == 0) { delete expr; new_expr = factored_expr; } else expr->arg_list().ins_last(factored_expr); } } return new_expr; } /// _factor_out_var /// Factor out the given variable from the given expression. For example, /// the factored form of the expression "x*a + x*b + c" for variable x is /// "x*(a + b) + c". static Expression * _factor_out_var(Expression *expr, const Symbol &var) { if (! expr) return expr; Mutator<Expression> arg_iter = expr->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) { Assign<Expression> eas(arg_iter.assign()); eas = _factor_out_var(arg_iter.pull(), var); } return _factor_out_var_top(expr, var); } /// solve_linear_expr /// Solve the given expression for the given variable. The expression /// is assumed to be linear for the given variable. static Expression * _solve_linear_expr(Expression *e, const Symbol &var, RangeComparator &comparator) { /// ... Pull the terms containing var out of the expression. Expression *var_term = 0; if (e->op() != ADD_OP) { var_term = e; e = constant(0); } else { var_term = new NonBinaryExpr(ADD_OP, e->type()); Mutator<Expression> arg_iter = e->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) if (is_var_in_expr(arg_iter.current(), var)) var_term->arg_list().ins_last(arg_iter.grab()); if (e->arg_list().entries() == 0) { delete e; e = constant(0); } else if (e->arg_list().entries() == 1) { Expression *arg = e->arg_list().grab( *e->arg_list().first_ref()); delete e; e = arg; } p_assert(var_term->arg_list().entries() > 0, "Internal error: Expression doesn't contain variable."); if (var_term->arg_list().entries() == 1) { Expression *arg = var_term->arg_list().grab( *var_term->arg_list().first_ref()); delete var_term; var_term = arg; } } /// ... Factor out the variable from var_term. if (var_term->op() == ADD_OP) var_term = _factor_out_var(var_term, var); e = unary_minus(e); if (var_term->op() == ID_OP) { delete var_term; } else if (var_term->op() == MULT_OP) { /// ... Compute the divisor of the solution. Mutator <Expression> arg_iter = var_term->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) if (arg_iter.current().op() == ID_OP && &arg_iter.current().symbol() == &var) { arg_iter.del(); break; } if (is_var_in_expr(*var_term, var)) { delete e; delete var_term; return 0; } if (var_term->arg_list().entries() == 1) { Expression *arg = var_term->arg_list().grab( *var_term->arg_list().first_ref()); delete var_term; var_term = arg; } EXPR_SIGN term_sign = comparator.sign(*var_term); if (term_sign == POS_NEG_EXPR) { delete var_term; delete e; return 0; } EXPR_SIGN e_sign = comparator.sign(*e); if (e_sign == POS_NEG_EXPR) { delete var_term; delete e; return 0; } else if (e_sign == NEG_EXPR) term_sign = flip_sign(term_sign); e = div(e, var_term); /// ... We want e to be rounded upwards. So if e /// ... is positive, add one to it. if (term_sign == POS_EXPR) e = add(constant(1), e); e = simplify(e); } return e; } /// find_quad_range /// Try to find the exact range for the given expression, variable and /// substitution range, where the expression is quadratic in terms of the /// variable. If it can find it, it returns this exact range. /// Otherwise, it returns NULL Expression * RangeComparator::_find_quad_range(const Expression &e, const Symbol &var, const RangeExpr &subst_range) { int var_power = _var_power_in_expr(e, var); if (var_power != 2) return NULL; /// ... Take the forward difference of the expression. The forward difference /// ... is an approximation of the derivative of e. Expression *forward_diff = _forward_diff(e, var); int diff_var_power = _var_power_in_expr(*forward_diff, var); if (diff_var_power >= var_power) { delete forward_diff; return 0; } /// ... Solve forward_diff = 0 for var. Expression *root = _solve_linear_expr(forward_diff->clone(), var, *this); if (! root) { delete forward_diff; return 0; } /// ... Determine whether root falls within bounds of variable. If not, /// ... abort. if ((subst_range.has_lb() && ! compare(subst_range.lb(), *root).is_less_equal()) || (subst_range.has_ub() && ! compare(*root, subst_range.ub()).is_less_equal())) { delete forward_diff; delete root; return 0; } /// ... Determine whether the root is a minimum or maximum. Expression *forward_diff_diff = _forward_diff(*forward_diff, var); if (is_var_in_expr(*forward_diff_diff, var)) { delete forward_diff_diff; delete forward_diff; delete root; return 0; } bool root_is_min = (sign(*forward_diff_diff) == POS_EXPR); delete forward_diff_diff; delete forward_diff; /// ... Generate the new range from this root. Expression *border_lb, *border_ub; if (root_is_min) { border_lb = _substitute_mono_var(e.clone(), var, subst_range.lb(), false, symtab()); border_ub = _substitute_mono_var(e.clone(), var, subst_range.ub(), true, symtab()); } else { border_lb = _substitute_mono_var(e.clone(), var, subst_range.lb(), true, symtab()); border_ub = _substitute_mono_var(e.clone(), var, subst_range.ub(), false, symtab()); } border_lb = simplify(border_lb); border_ub = simplify(border_ub); Relation border_rel = compare(*border_lb, *border_ub); if (border_rel.is_greater_equal()) { Expression *temp = border_lb; border_lb = border_ub; border_ub = temp; } else if (border_rel.is_unknown()) { delete border_lb; delete border_ub; border_lb = 0; border_ub = 0; } Expression *root_bound = simplify(substitute_var(e.clone(), var, *root)); delete root; Expression *result; if (root_is_min) { result = new RangeExpr(root_bound, border_ub); if (border_lb) delete border_lb; } else { result = new RangeExpr(border_lb, root_bound); if (border_ub) delete border_ub; } return result; } /// num_args_with_var /// Return the number of arguments that contain the given variable. static int _num_args_with_var(const Expression &expr, const Symbol &var) { int num_args_with_var = 0; Iterator<Expression> iter = expr.arg_list(); for ( ; iter.valid(); ++iter) if (is_var_in_expr(iter.current(), var)) ++num_args_with_var; return num_args_with_var; } /// is_aritmetic_expr /// Return true if the top level expression is some sort of arithmetic /// operator. static bool _is_arithmetic_expr(const Expression &expr) { OP_TYPE op = expr.op(); return (op == ADD_OP || op == SUB_OP || op == MULT_OP || op == DIV_OP || op == EXP_OP); } /// eliminate_quads /// Eliminate any quadratic equations from the function. Expression * RangeComparator::_eliminate_quads(Expression *expr, const Symbol &var, const RangeExpr &subst_range) { if (! expr) return expr; int var_power = _var_power_in_expr(*expr, var); if (var_power < 2) return expr; int num_args_with_var = _num_args_with_var(*expr, var); if (var_power > 2 || num_args_with_var < 2 || ! _is_arithmetic_expr(*expr)) { if (var_power > 2 && num_args_with_var >= 2 && _is_arithmetic_expr(*expr)) expr = _factor_out_var(expr, var); Mutator<Expression> arg_iter = expr->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) { Assign<Expression> eas(arg_iter.assign()); eas = _eliminate_quads(arg_iter.pull(), var, subst_range); } } else { if (_debug_level >= 30) cout << " eliminate_quads(expr=" << *expr << ", var=" << var.name_ref() << ", subst_range=" << subst_range << ") {\n"; if (expr->op() == RANGE_OP) { RangeExpr &range = * (RangeExpr *) expr; Expression *new_lb = _find_quad_range(range.lb(), var, subst_range); if (new_lb) range.lb(new_lb); Expression *new_ub = _find_quad_range(range.ub(), var, subst_range); if (new_ub) range.ub(new_ub); } else { Expression *new_expr = _find_quad_range(*expr, var, subst_range); if (new_expr) { delete expr; expr = new_expr; } } if (_debug_level >= 30) cout << " } result(elim quads): " << *expr << endl; } return expr; } /// solve_for_range /// Try to determine the exact lower and upper bounds of the given /// expression for the given range of values taken by the given variable. Expression * RangeComparator::_solve_for_range(Expression *expr, const Symbol &var, const RangeExpr &subst_range) { if (! expr) return expr; if (! _is_arithmetic_expr(*expr)) { Mutator<Expression> arg_iter = expr->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) { Assign<Expression> eas(arg_iter.assign()); eas = _solve_for_range(arg_iter.pull(), var, subst_range); } /// ... Assume that the expression forming the range-op /// ... is monotonic (_solve_monotonic checks that). /// ... That means that we just have to check the two /// ... end-points of the range against the other expression. if (is_relational_op(expr->op()) && (expr->arg_list()[0].op() == RANGE_OP)) { Expression *new_expr; switch (expr->op()) { case LE_OP: new_expr = and(le(expr->arg_list()[0].arg_list()[0].clone(), expr->arg_list()[1].clone()), le(expr->arg_list()[0].arg_list()[1].clone(), expr->arg_list()[1].clone())); delete expr; expr = new_expr; break; case LT_OP: new_expr = and(lt(expr->arg_list()[0].arg_list()[0].clone(), expr->arg_list()[1].clone()), lt(expr->arg_list()[0].arg_list()[1].clone(), expr->arg_list()[1].clone())); delete expr; expr = new_expr; break; case GE_OP: new_expr = and(ge(expr->arg_list()[0].arg_list()[0].clone(), expr->arg_list()[1].clone()), ge(expr->arg_list()[0].arg_list()[1].clone(), expr->arg_list()[1].clone())); delete expr; expr = new_expr; break; case GT_OP: new_expr = and(gt(expr->arg_list()[0].arg_list()[0].clone(), expr->arg_list()[1].clone()), gt(expr->arg_list()[0].arg_list()[1].clone(), expr->arg_list()[1].clone())); delete expr; expr = new_expr; break; default: break; } } } else if (_num_var_occurrences_in_expr(*expr, var) > 1) { Expression *new_expr = _solve_monotonic(expr, var, subst_range); if (new_expr) expr = new_expr; else if (range_compare_accuracy() >= 2) expr = _eliminate_quads(expr, var, subst_range); } return expr; } /// subst_var_outside_array_refs /// Like substitute_var() except that variables inside array references /// cannot be substituted by a range. Expression * _subst_var_outside_array_refs(Expression *expr, const Symbol &var, const Expression &subst_expr) { if (expr->op() == ID_OP) { if (&expr->symbol() == &var) { delete expr; return subst_expr.clone(); } } else { Mutator<Expression> iter = expr->arg_list(); if (expr->op() == ARRAY_REF_OP && subst_expr.op() == RANGE_OP) { Assign<Expression> eas(iter.assign()); eas = _subst_var_outside_array_refs(iter.pull(), var, subst_expr); } else { for ( ; iter.valid(); ++iter) { Assign<Expression> eas2(iter.assign()); eas2 = _subst_var_outside_array_refs(iter.pull(), var, subst_expr); } } } return expr; } /// subst_var_and_simplify Expression * RangeComparator::subst_var_and_simplify(Expression *e, const Symbol &var, const Expression *subst_expr) { if (subst_expr && is_empty_range(*subst_expr)) { if (e) delete e; e = new RangeExpr(constant(1), constant(0)); } else if (e) { if (_debug_level >= 30) { cout << " subst_var_and_simplify(e=" << *e << ", var=" << var.name_ref() << ", subst_expr="; if (subst_expr) cout << *subst_expr << ");\n"; else cout << "NULL);\n"; } if (_stats) _stats->making_a_var_subst(); if (subst_expr) { if (subst_expr->op() == RANGE_OP && _use_the_big_guns) { if (range_compare_accuracy() < 3) _use_the_big_guns = false; e = _remove_mods_with_var(e, var, *subst_expr, *this); e = _solve_for_range(e, var, * (RangeExpr *) subst_expr); _use_the_big_guns = true; } e = substitute_var(e, var, *subst_expr); } else { Expression *om = omega(); e = substitute_var(e, var, *om); delete om; } if (_debug_level >= 30) cout << " e = " << *e << " after substituting\n"; if (! subst_expr || subst_expr->op() == RANGE_OP || subst_expr->op() == OMEGA_OP) { e = pull_ranges_out(e, *this); if (_debug_level >= 30) cout << " e = " << *e << " after pulling out ranges\n"; } e = pull_min_max_out(e, *this); if (_debug_level >= 30) cout << " e = " << *e << " after pulling out min/max\n"; e = expr_expand_substituted(e); e = simplify(e); if (_debug_level >= 30) cout << " e = " << *e << " after simplifying\n"; } return e; } /// remove_truncates_with_var Expression * RangeComparator::remove_truncates_with_var(Expression *e, const Symbol &var) { if (e) { e = _remove_truncates(e, var); const Expression *subst_range = get_range_ref(var); if (subst_range) e = _remove_mods_with_var(e, var, *subst_range, *this); else { Expression *om = omega(); e = _remove_mods_with_var(e, var, *om, *this); delete om; } } return e; } /// eliminate_vars Expression * RangeComparator::eliminate_vars(Expression *e, const RefSet<Symbol> *vars_to_eliminate) { if (vars_to_eliminate && vars_to_eliminate->entries() == 0) return e; e = expr_expand_substituted(e); e = simplify(e); if (_debug_level >= 1) { cout << "Eliminating vars {"; if (vars_to_eliminate) for(Iterator<Symbol> iter = vars_to_eliminate; iter.valid(); ++iter) cout << iter.current().name_ref() << ", "; else cout << "<all vars>"; cout << "} from (" << *e << ") {\n"; } RefList<Symbol> subst_order; _generate_subst_order(subst_order, *e, *this); while(subst_order.entries() > 0) { Symbol &var = subst_order.grab(0); if ((! vars_to_eliminate || vars_to_eliminate->member(var)) && is_var_in_expr(*e, var)) { const Expression *range = get_range_ref(var); if (range && range->op() == RANGE_OP) e = _remove_truncates(e, var); e = subst_var_and_simplify(e, var, range); if (_debug_level >= 20) { cout << " e = (" << *e << ")" << " after substituting " << var.name_ref() << " = ("; if (range) cout << *range; else cout << "[-Inf:Inf]"; cout << ")\n"; } } } /// ... Replace any remaining variables to eliminate with omega if (vars_to_eliminate) { Iterator<Symbol> elim_iter = vars_to_eliminate; Expression *om = omega(); bool ommed_a_var = false; for ( ; elim_iter.valid(); ++elim_iter) if (is_var_in_expr(*e, elim_iter.current())) { e = substitute_var(e, elim_iter.current(), *om); ommed_a_var = true; } delete om; if (ommed_a_var) e = simplify(pull_ranges_out(e, *this)); } if (_debug_level >= 1) cout << "} result(eliminate_vars): " << *e << endl; return e; } /// intersect_range void RangeComparator::intersect_range(const Symbol &var, const Expression &inter_expr) { const Expression *old_range_ref = get_range_ref(var); if (! old_range_ref) { /// ... This could establish a range SCC involving var... but /// ... such a cycle would not lose pre-existing information /// ... about var... there was none to lose set_range(var, inter_expr.clone()); return; } if (_debug_level >= 1) cout << "Intersecting (" << *old_range_ref << ") with (" << inter_expr << ") for " << var.name_ref() << " {\n"; /// ... Insert dummy range for var to signal self-reference if the /// ... replacement of var causes omega Expression *old_range = old_range_ref->clone(); set_range(var, new RangeExpr(new InfinityExpr(-1), new InfinityExpr(+1))); Expression *result = intersect_ranges(old_range, *this, &inter_expr, *this); delete old_range; set_range(var, result); if (_debug_level >= 1) { cout << "} result(intersect): "; if (result) cout << *result; else cout << "NULL"; cout << endl; } } /// union_range void RangeComparator::union_range(const Symbol &var, const Expression &union_expr, RangeComparator *union_comparator_ref GIV(0)) { const Expression *old_range_ref = get_range_ref(var); if (! old_range_ref || old_range_ref->op() == OMEGA_OP || old_range_ref->compare(union_expr) == 0) return; if (_debug_level >= 1) cout << "Unioning (" << *old_range_ref << ") with (" << union_expr << ") for " << var.name_ref() << " {\n"; Expression *result = 0; if (union_comparator_ref) result = union_ranges(old_range_ref, *this, &union_expr, *union_comparator_ref); else result = union_ranges(old_range_ref, *this, &union_expr, *this); set_range(var, result); if (_debug_level >= 1) { cout << "} result(union): "; if (result) cout << *result; else cout << "NULL"; cout << endl; } } /// operator = RangeComparator & RangeComparator::operator = (const RangeComparator &other) { if (this != &other) { _symtab_ref = other._symtab_ref; _compare_info = other._compare_info; _debug_level = other._debug_level; _range_join_accuracy = other._range_join_accuracy; _range_compare_accuracy = other._range_compare_accuracy; _use_the_big_guns = other._use_the_big_guns; _cache_expr_signs = other._cache_expr_signs; _cached_sign_exprs = other._cached_sign_exprs; _cached_expr_signs = other._cached_expr_signs; } return *this; } /// symtab const Symtab & RangeComparator::symtab() const { return *_symtab_ref; } /// range_join_accuracy int RangeComparator::range_join_accuracy() { return _range_join_accuracy; } void RangeComparator::range_join_accuracy(int acc) { _range_join_accuracy = acc; } /// range_compare_accuracy int RangeComparator::range_compare_accuracy() { return _range_compare_accuracy; } void RangeComparator::range_compare_accuracy(int acc) { _range_compare_accuracy = acc; _use_the_big_guns = (_range_compare_accuracy >= 1); } /// debug_level int RangeComparator::debug_level() const { return _debug_level; } void RangeComparator::debug_level(int level) { _debug_level = level; } /// _are_vars_in_expr /// Return true if the given expression uses any of the variables in the /// given set. static bool _are_vars_in_expr(const Expression &e, const RefSet<Symbol> &vars) { if (e.op() == ID_OP) return vars.member(e.symbol()); else { Iterator<Expression> iter = e.arg_list(); for ( ; iter.valid(); ++iter) if (_are_vars_in_expr(iter.current(), vars)) return true; } return false; } /// _begin_caching_expr_signs /// Start caching the signs of arbitrary expressions. void RangeComparator::_begin_caching_expr_signs() { ++_cache_expr_signs; } /// _end_caching_expr_signs /// Stop caching the signs of arbitrary expressions. void RangeComparator::_end_caching_expr_signs() { --_cache_expr_signs; if (_cache_expr_signs <= 0) { _cache_expr_signs = 0; _cached_sign_exprs.clear(); _cached_expr_signs.clear(); } } /// _flush_sign_caches void RangeComparator::_flush_sign_caches() { _cache_expr_signs = 0; _cached_sign_exprs.clear(); _cached_expr_signs.clear(); KeyIterator<Symbol,CompareData> compare_iter = _compare_info; for ( ; compare_iter.valid(); ++compare_iter) compare_iter.current_data().sign_cache = UNKNOWN_SIGN; } /// print void RangeComparator::print(ostream & o) const { o << "_compare_info={"; KeyIterator<Symbol,CompareData> compare_iter = _compare_info; for ( ; compare_iter.valid(); ++compare_iter) o << compare_iter.current_key().name_ref() << ": " << compare_iter.current_data() << ", "; o << "}"; o << ", ubg=" << _use_the_big_guns; } /// structures_OK int RangeComparator::structures_OK() const { return _compare_info.structures_OK(); }

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