Polaris: range_util.cc Source File

range_util.cc Go to the documentation of this file. /// /// /// \file range_util.cc /// #include "../Collection/Mutator.h" #include "../Collection/List.h" #include "../Collection/Set.h" #include "../Expression/Expression.h" #include "../Expression/InfinityExpr.h" #include "../Expression/NonBinaryExpr.h" #include "../Symbol/Symbol.h" #include "../Symbol/FunctionSymbol.h" #include "../utilities/switches_util.h" #include "../utilities/expression_util.h" #include "../Symtab.h" #include "../String.h" #include "../Traverser.h" #include "../macros.h" #include "range_util.h" #include "RangeAccessor.h" #include "RangeComparator.h" #include "RangeExpr.h" #include "StmtRanges.h" #include "../Constant/constant.h" static inline int min(int a, int b) { return (a < b) ? a : b; } static Expression *_pull_min_max_out_top(Expression *e, RangeComparator &comparator); static Expression * _elim_known_facts(Expression *e, RangeComparator &comparator); /// _handle_range /// Return the desired component of the range, as indicated by the /// range_handling flag. static Expression * _handle_range(RangeExpr *range, RANGE_HANDLING range_handling) { if (! range) return range; Expression *new_range = 0; switch (range_handling) { case TAKE_RANGE_MIN: if (range->has_lb()) new_range = range->grab_lb(); break; case TAKE_RANGE_MAX: if (range->has_ub()) new_range = range->grab_ub(); break; default: if (range->has_lb() || range->has_ub()) { new_range = range; range = 0; } break; } if (range) delete range; return new_range; } /// _swap_range_args /// Swap the lower and upper bounds of the given range_expression static void _swap_range_args(RangeExpr &range) { Expression *temp = range.grab_lb(); range.lb(range.grab_ub()); range.ub(temp); if (range.lb().op() == INFINITY_OP) ((InfinityExpr *) &range.lb())->sign(-1); if (range.ub().op() == INFINITY_OP) ((InfinityExpr *) &range.ub())->sign(+1); } /// _negate_range /// Negate the given range. static void _negate_range(RangeExpr &range) { if (range.has_lb()) range.lb(unary_minus(range.grab_lb())); if (range.has_ub()) range.ub(unary_minus(range.grab_ub())); _swap_range_args(range); } /// _p_r_o_of_add /// Convert an addition expression whose arguments contain ranges into /// a range expression. static Expression * _p_r_o_of_add(Expression *e) { /// silvius: not sure how to fix this cleanly, but it breaks /// on [0:Inf]+[0:Inf] static Expression* _ugly_fix_l=0; static Expression* _ugly_fix_u=0; if (_ugly_fix_l==0){ _ugly_fix_l=constant(0); _ugly_fix_u=infinity(); } /// cerr<<"\n *e= "<<*e<<"\t*_u_f= "<<*_ugly_fix_l<<", "<<*_ugly_fix_u; if (e->op()==ADD_OP){ if (e->arg_list().entries()==2){ if (e->arg_list()[0].op()==RANGE_OP){ if (e->arg_list()[1].op()==RANGE_OP){ RangeExpr& e0=(RangeExpr&)e->arg_list()[0]; RangeExpr& e1=(RangeExpr&)e->arg_list()[1]; if (e0.lb()==*_ugly_fix_l && e1.lb()==*_ugly_fix_l && e0.ub()==*_ugly_fix_u && e1.ub()==*_ugly_fix_u){ /// cerr<<"\nBug fix for function _p_r_o_of_add("<<*e<<")."; return new RangeExpr(constant(0), infinity()); } } } } } /// silvius: it also breaks on [0:Inf]+(-1)*ABS(biga@4) if (e->op()==ADD_OP){ if (e->arg_list().entries()==2){ if (e->arg_list()[0].op()==RANGE_OP){ if (e->arg_list()[1].op()!=RANGE_OP){ RangeExpr& e0=(RangeExpr&)e->arg_list()[0]; RangeExpr& e1=(RangeExpr&)e->arg_list()[1]; if (e0.lb()==*_ugly_fix_l && e0.ub()==*_ugly_fix_u){ /// cerr<<"\nBug fix for function _p_r_o_of_add("<<*e<<")."; if (e1.type().data_type()==INTEGER_TYPE){ return new RangeExpr(e1.clone(), infinity()); } else { return new RangeExpr(infinity(-1), infinity()); } } } } } } /// silvius: it also breaks on 1+[-Inf:0] if (e->op()==ADD_OP){ if (e->arg_list().entries()==2){ if (is_integer_one(e->arg_list()[0])){ if (e->arg_list()[1].op()==RANGE_OP){ RangeExpr& e1=(RangeExpr&)e->arg_list()[1]; if (e1.lb().op()==INFINITY_OP && e1.lb().sign()==-1){ /// ... cerr<<"\nBug fix for function _p_r_o_of_add("<<*e<<")."; return new RangeExpr(infinity(-1), simplify(add(e->arg_list()[1].clone(), e1.ub().clone()))); } } } } } /// end silvius fix RangeExpr *range = new RangeExpr(e, e->clone()); bool is_infinite = false; Mutator<Expression> arg_iter = range->lb().arg_list(); for ( ; arg_iter.valid() && ! is_infinite; ++arg_iter) if (arg_iter.current().op() == RANGE_OP) { RangeExpr &arg_range = * (RangeExpr *) &arg_iter.current(); if (arg_range.has_lb()) arg_iter.modify(arg_range.grab_lb()); else is_infinite = true; } if (is_infinite) range->lb(0); is_infinite = false; arg_iter = range->ub().arg_list(); for ( ; arg_iter.valid() && ! is_infinite; ++arg_iter) if (arg_iter.current().op() == RANGE_OP) { RangeExpr &arg_range = * (RangeExpr *) &arg_iter.current(); if (arg_range.has_ub()) arg_iter.modify(arg_range.grab_ub()); else is_infinite = true; } if (is_infinite) range->ub(0); return range; } /// _range_bound_multiply /// Multiply the two expressions and return the result. Return 0 if the /// expression turns out to be infinite or undefined. static Expression * _range_bound_multiply(Expression *e1, Expression *e2) { if (! e1 || e1->op() == OMEGA_OP || e1->op() == INFINITY_OP || ! e2 || e2->op() == OMEGA_OP || e2->op() == INFINITY_OP) { if (e1) delete e1; if (e2) delete e2; return 0; } else if (e1->op() == INTEGER_CONSTANT_OP && e2->op() == INTEGER_CONSTANT_OP) { e1->value(e1->value() * e2->value()); delete e2; return e1; } else if (e2->op() == MULT_OP) { if (e1->op() == MULT_OP) { List<Expression> &e1_args = e1->arg_list(); List<Expression> &e2_args = e2->arg_list(); while(e1_args.entries()) e2_args.ins_first(e1_args.grab(*e1_args.last_ref())); delete e1; } else e2->arg_list().ins_first(e1); return e2; } else if (e1->op() == MULT_OP) { e1->arg_list().ins_last(e2); return e1; } return mul(e1, e2); } /// _mult_range_with_expr /// Multiply the given range with the given non-range Expression and return /// the result. Return 0 if the result is infinite or undefined. static Expression * _mult_range_with_expr(RangeExpr *r, Expression *e, RangeComparator &comparator) { p_assert(r && e && r->op() == RANGE_OP && e->op() != RANGE_OP, "Invalid arguments passed to _mult_range_with_expr()."); if (e->op() == OMEGA_OP || e->op() == INFINITY_OP) { delete r; delete e; return 0; } /// ... Determine the sign of the expression. EXPR_SIGN e_sign = comparator.sign(*e); /// ... Quit if the sign of the non-range arguments cannot be determined. if (e_sign == POS_NEG_EXPR) { if (e->op() == ADD_OP) { /// ... Handle folded expressions (e.g. [a:b]*(c+d)) as a special case. /// ... Rather than quitting, distribute the expression and try again. Mutator<Expression> arg_iter = e->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) { Assign<Expression> eas(arg_iter.assign()); Expression *new_arg = _mult_range_with_expr((RangeExpr *) r->clone(), arg_iter.pull(), comparator); if (! new_arg) { delete r; delete e; return 0; } else eas = new_arg; } delete r; return _p_r_o_of_add(e); } else { delete r; delete e; return 0; /// ... Couldn't determine sign, so give up. } } /// ... Multiply the range with the nonrange arguments. if (e_sign == NEG_EXPR) _swap_range_args(*r); if (r->has_lb() && r->has_ub()) { r->lb(_range_bound_multiply(e->clone(), r->grab_lb())); r->ub(_range_bound_multiply(e, r->grab_ub())); } else if (r->has_lb()) r->lb(_range_bound_multiply(e, r->grab_lb())); else if (r->has_ub()) r->ub(_range_bound_multiply(e, r->grab_ub())); else delete e; return r; } /// _merge_range_mult_terms /// Pull all the range terms of the given multiply expression, multiply /// them togethor and return the result. Return 0 if the result turns out /// to be infinite or undefined. static RangeExpr * _merge_range_mult_terms(Expression &e, RangeComparator &comparator) { p_assert(e.op() == MULT_OP, "_merge_range_mult_terms() expected a multiply expression."); Set<RangeExpr> range_args; Mutator<Expression> arg_iter = e.arg_list(); for ( ; arg_iter.valid(); ++arg_iter) if (arg_iter.current().op() == RANGE_OP) range_args.ins((RangeExpr *) arg_iter.grab()); p_assert(range_args.entries() > 0, "_merge_range_mult_terms() was given an expression with no ranges"); RangeExpr *range_prod = 0; if (range_args.entries() == 1) range_prod = range_args.grab(); else { EXPR_SIGN range_prod_sign = POS_EXPR; Set<RangeExpr> pos_neg_range_args; while (range_args.entries() > 0) { RangeExpr *range = 0; EXPR_SIGN range_sign = POS_NEG_EXPR; while (! range && range_args.entries() > 0) { range = range_args.grab(); range_sign = comparator.sign(*range); if (range_sign == POS_NEG_EXPR) { pos_neg_range_args.ins(range); range = 0; } } if (range) { if (! range_prod) range_prod = range; else { Expression *rp_lb = range_prod->grab_lb(); Expression *rp_ub = range_prod->grab_ub(); Expression *r_lb = range->grab_lb(); Expression *r_ub = range->grab_ub(); delete range; if (range_prod_sign == POS_EXPR) if (range_sign == POS_EXPR) { range_prod->lb(_range_bound_multiply(rp_lb, r_lb)); range_prod->ub(_range_bound_multiply(rp_ub, r_ub)); } else { /// ... range_sign == NEG_EXPR range_prod->lb(_range_bound_multiply(rp_ub, r_lb)); range_prod->ub(_range_bound_multiply(rp_lb, r_ub)); } else { /// ... range_prod_sign = NEG_EXPR if (range_sign == POS_EXPR) { range_prod->lb(_range_bound_multiply(rp_lb, r_ub)); range_prod->ub(_range_bound_multiply(rp_ub, r_lb)); } else { /// ... range_sign == NEG_EXPR range_prod->lb(_range_bound_multiply(rp_ub, r_ub)); range_prod->ub(_range_bound_multiply(rp_lb, r_lb)); } } } if (range_sign == NEG_EXPR) range_prod_sign = flip_sign(range_prod_sign); } } if (pos_neg_range_args.entries() > 1) { if (range_prod) delete range_prod; return 0; } p_assert(range_prod, "Internal Error."); if (pos_neg_range_args.entries() == 1) { RangeExpr *pos_neg_range = pos_neg_range_args.grab(); pos_neg_range->lb(_mult_range_with_expr((RangeExpr *) range_prod->clone(), pos_neg_range->grab_lb(), comparator)); pos_neg_range->ub(_mult_range_with_expr(range_prod, pos_neg_range->grab_ub(), comparator)); if (pos_neg_range->has_lb() && pos_neg_range->lb().op() == RANGE_OP) pos_neg_range->lb( ((RangeExpr &) pos_neg_range->lb()).grab_lb()); if (pos_neg_range->has_ub() && pos_neg_range->ub().op() == RANGE_OP) pos_neg_range->ub( ((RangeExpr &) pos_neg_range->ub()).grab_ub()); if (! pos_neg_range->has_lb() && ! pos_neg_range->has_ub()) { delete pos_neg_range; pos_neg_range = 0; } range_prod = pos_neg_range; } } return range_prod; } /// _p_r_o_of_mult /// Pull the range out of a multiply statement. static Expression * _p_r_o_of_mult(Expression *e, RangeComparator &comparator) { /// ... Pull out and multiply all the range terms in the given expression. RangeExpr *range_prod = _merge_range_mult_terms(*e, comparator); if (! range_prod) { delete e; return 0; } if (e->arg_list().entries() == 0) { delete e; return range_prod; } else if (e->arg_list().entries() == 1) { Expression *new_e = e->arg_list().grab(*e->arg_list().first_ref()); delete e; e = new_e; } return _mult_range_with_expr(range_prod, e, comparator); } /// _p_r_o_of_divide /// Pull the range out of a divide statement. static Expression * _p_r_o_of_divide(Expression *e, RangeComparator &comparator) { RangeExpr *range = 0; if (e->right_guarded().op() != RANGE_OP) { p_assert (e->left_guarded().op() == RANGE_OP, "Expression passed to _p_r_o_of_divide has no ranges"); EXPR_SIGN sign = comparator.signz(e->right_guarded()); if (sign == POS_NEG_EXPR || sign == ZERO_EXPR) { delete e; return 0; /// ... Couldn't determine sign, so give up. } range = (RangeExpr *) e->grab_left(); Expression *denom = e->grab_right(); delete e; if (range->has_lb() && range->has_ub()) { range->lb(div(range->grab_lb(), denom->clone())); range->ub(div(range->grab_ub(), denom)); } else if (range->has_lb()) { range->lb(div(range->grab_lb(), denom)); range->ub(0); } else if (range->has_ub()) { range->lb(0); range->ub(div(range->grab_ub(), denom)); } else p_abort("Internal error in _p_r_o_of_divide()"); if (sign == NEG_EXPR) _swap_range_args(*range); } else if (e->left_guarded().op() != RANGE_OP) { p_assert (e->right_guarded().op() == RANGE_OP, "Expression passed to _p_r_o_of_divide has no ranges"); EXPR_SIGN numer_sign = comparator.sign(e->left_guarded()); EXPR_SIGN denom_sign = comparator.signz(e->right_guarded()); if (numer_sign == POS_NEG_EXPR || denom_sign == POS_NEG_EXPR || denom_sign == ZERO_EXPR) { delete e; return 0; /// ... Couldn't determine sign, so give up. } Expression *numer = e->grab_left(); range = (RangeExpr *) e->grab_right(); delete e; if (range->has_lb() && range->has_ub()) { range->lb(div(numer->clone(), range->grab_lb())); range->ub(div(numer, range->grab_ub())); } else if (range->has_lb()) { range->lb(div(numer, range->grab_lb())); range->ub(constant(0)); } else if (range->has_ub()) { range->lb(constant(0)); range->ub(div(numer, range->grab_ub())); } else p_abort("Internal error in _p_r_o_of_divide()"); if (numer_sign == POS_EXPR) _swap_range_args(*range); } else { delete e; return 0; } return range; } /// _p_r_o_of_exp /// Pull the range out of an exponentiation statement. static Expression * _p_r_o_of_exp(Expression *e, RangeComparator &comparator) { if (e->right_guarded().op() != INTEGER_CONSTANT_OP) { delete e; return 0; } int power = e->right_guarded().value(); if (e->left_guarded().op() == OMEGA_OP) { delete e; if (power % 2 == 0) return new RangeExpr(constant(0), 0); else return 0; } p_assert (e->left_guarded().op() == RANGE_OP, "Expression passed to _p_r_o_of_exp has no ranges"); RangeExpr *range = (RangeExpr *) e->grab_left(); delete e; if (power % 2 == 0) { /// ... Power is even. bool abs_lb_is_larger = false; EXPR_SIGN lb_sign = comparator.sign(range->lb()); if (lb_sign == POS_EXPR) { /// ... lb and ub are both positive, so abs(lb) <= abs(ub). } else { EXPR_SIGN ub_sign = comparator.sign(range->ub()); if (ub_sign == NEG_EXPR) { /// ... lb and ub are both negative, so abs(lb) >= abs(ub). abs_lb_is_larger = true; } else if (lb_sign == NEG_EXPR && ub_sign == POS_EXPR) { /// ... Compare abs(lb) == -lb with abs(ub) == ub. Expression *diff = simplify(add(range->lb().clone(), range->ub().clone())); EXPR_SIGN diff_sign = comparator.sign(*diff); delete diff; if (diff_sign == POS_EXPR) { /// ... abs(lb) <= abs(ub). } else if (diff_sign == NEG_EXPR) { /// ... abs(lb) >= abs(ub). abs_lb_is_larger = true; } else { delete range; return new RangeExpr(constant(0), 0); } } else { delete range; return new RangeExpr(constant(0), 0); } } if (abs_lb_is_larger) _swap_range_args(*range); } if (range->has_lb()) range->lb(exponent(range->grab_lb(), constant(power))); if (range->has_ub()) range->ub(exponent(range->grab_ub(), constant(power))); return range; } /// _p_r_o_of_range /// Pull the range out of a range expression static Expression * _p_r_o_of_range(Expression *e) { RangeExpr &range = * (RangeExpr *) e; if (range.lb().op() == OMEGA_OP) range.lb(0); else if (range.lb().op() == RANGE_OP) range.lb(((RangeExpr *) &range.lb())->grab_lb()); if (range.ub().op() == OMEGA_OP) range.ub(0); else if (range.ub().op() == RANGE_OP) range.ub(((RangeExpr *) &range.ub())->grab_ub()); if (! range.has_lb() && ! range.has_ub()) { delete e; return 0; } return e; } /// _p_r_o_of_min_max(Expression *e) /// Pull the range out of the MIN or MAX intrinsic operator. static Expression * _p_r_o_of_min_max(Expression *e, bool is_min_op) { Expression *lb = e; Expression *ub = e->clone(); Mutator<Expression> arg_iter = lb->parameters_guarded().arg_list(); bool is_infinite = false; for ( ; arg_iter.valid() && ! is_infinite; ++arg_iter) if (arg_iter.current().op() == RANGE_OP) { RangeExpr &range = * (RangeExpr *) &arg_iter.current(); if (range.has_lb()) arg_iter.modify(range.grab_lb()); else if (! is_min_op) arg_iter.del(); else is_infinite = true; } else if (arg_iter.current().op() == OMEGA_OP) if (! is_min_op) arg_iter.del(); else is_infinite = true; if (is_infinite || lb->parameters_guarded().arg_list().entries() == 0) { delete lb; lb = 0; } is_infinite = false; for (arg_iter = ub->parameters_guarded().arg_list(); arg_iter.valid() && ! is_infinite; ++arg_iter) if (arg_iter.current().op() == RANGE_OP) { RangeExpr &range = * (RangeExpr *) &arg_iter.current(); if (range.has_ub()) arg_iter.modify(range.grab_ub()); else if (is_min_op) arg_iter.del(); else is_infinite = true; } else if (arg_iter.current().op() == OMEGA_OP) if (is_min_op) arg_iter.del(); else is_infinite = true; if (is_infinite || ub->parameters_guarded().arg_list().entries() == 0) { delete ub; ub = 0; } return new RangeExpr(lb, ub); } /// _p_r_o_of_ifix /// Convert an IFIX intrinsic expression whose argument is a range into /// a range expression. static Expression * _p_r_o_of_ifix(Expression *e) { Expression *lb = e; Expression *ub = e->clone(); List<Expression> &lb_args = lb->parameters_guarded().arg_list(); RangeExpr &lb_range = * (RangeExpr *) lb_args.first_ref(); lb_args.modify(lb_range, lb_range.grab_lb()); List<Expression> &ub_args = ub->parameters_guarded().arg_list(); RangeExpr &ub_range = * (RangeExpr *) ub_args.first_ref(); ub_args.modify(ub_range, ub_range.grab_ub()); return new RangeExpr(lb, ub); } /// _min_abs_expr /// Calculate and return the smallest absolute value for the given range. static Expression * _min_abs_expr(const Expression &e, EXPR_SIGN sign) { Expression *min_abs_expr = 0; if (e.op() == OMEGA_OP || sign == POS_NEG_EXPR) min_abs_expr = constant(0); else if (e.op() == RANGE_OP) { const RangeExpr &range = * (RangeExpr *) &e; if (sign == POS_EXPR) min_abs_expr = range.lb().clone(); else min_abs_expr = unary_minus(range.ub().clone()); } else if (sign == POS_EXPR) min_abs_expr = e.clone(); else min_abs_expr = unary_minus(e.clone()); return min_abs_expr; } /// _max_abs_expr /// Calculate and return the smallest absolute value for the given range. static Expression * _max_abs_expr(const Expression &e, EXPR_SIGN sign) { Expression *max_abs_expr = 0; if (e.op() == OMEGA_OP) max_abs_expr = new InfinityExpr(+1); else if (e.op() == RANGE_OP) { const RangeExpr &range = * (RangeExpr *) &e; if (! range.has_lb() || ! range.has_ub()) max_abs_expr = new InfinityExpr(+1); else { switch (sign) { case POS_EXPR: max_abs_expr = range.ub().clone(); break; case NEG_EXPR: max_abs_expr = unary_minus(range.lb().clone()); break; case POS_NEG_EXPR: { /// ... We don't want to do a compare() here because we may go into /// ... an infinite recursive loop. Expression *delta = sub(unary_minus(range.lb().clone()), range.ub().clone()); delta = simplify(delta); if (delta->op() == INTEGER_CONSTANT_OP) if (delta->value() <= 0) max_abs_expr = range.ub().clone(); else max_abs_expr = unary_minus(range.lb().clone()); else max_abs_expr = new InfinityExpr(+1); delete delta; } default: break; } } } else { switch (sign) { case POS_EXPR: max_abs_expr = e.clone(); break; case NEG_EXPR: max_abs_expr = unary_minus(e.clone()); break; case POS_NEG_EXPR: max_abs_expr = new InfinityExpr(+1); break; default: break; } } return max_abs_expr; } /// _handle_omega_in_mod /// Generate the proper range for an MOD intrinsic that contains static Expression * _handle_omega_in_mod(Expression *e, RangeComparator &comparator) { List<Expression> &params = e->parameters_guarded().arg_list(); p_assert(params.entries() == 2, "Wrong number of arguments in MOD intrinsic"); Expression *left_ref = params.first_ref(); Expression *right_ref = params.last_ref(); if (left_ref->op() == OMEGA_OP && right_ref->op() == OMEGA_OP) { delete e; return 0; } else if (right_ref->op() == OMEGA_OP) { EXPR_SIGN left_sign = comparator.sign(*left_ref); if (left_sign == POS_NEG_EXPR) { Expression *bound = _max_abs_expr(*left_ref, left_sign); delete e; if (! bound || bound->op() == INFINITY_OP) { delete bound; return 0; } return new RangeExpr(unary_minus(bound->clone()), bound); } else { RangeExpr *result = convert_to_range(params.grab(*left_ref)); delete e; if (left_sign == POS_EXPR) result->lb(constant(0)); else result->ub(constant(0)); return result; } } else { p_assert(left_ref->op() == OMEGA_OP, "Expression passed to _handle_omega_in_mod has no omega expressions"); EXPR_SIGN right_sign = comparator.sign(*right_ref); Expression *bound = _max_abs_expr(*right_ref, right_sign); delete e; if (! bound || bound->op() == INFINITY_OP || is_integer_zero(*bound)) { delete bound; return 0; } bound = add(bound, constant(-1)); return new RangeExpr(unary_minus(bound->clone()), bound); } } /// _p_r_o_of_mod /// Pull ranges out of a MOD intrinsic expression. static Expression * _p_r_o_of_mod(Expression *e, RangeComparator &comparator) { List<Expression> &params = e->parameters_guarded().arg_list(); p_assert(params.entries() == 2, "Wrong number of arguments in MOD intrinsic"); Expression &left = *params.first_ref(); Expression &right = *params.last_ref(); EXPR_SIGN left_sign = comparator.sign(left); EXPR_SIGN right_sign = comparator.signz(right); if (right_sign == POS_NEG_EXPR || right_sign == ZERO_EXPR) { params.modify(right, omega()); return _handle_omega_in_mod(e, comparator); } Expression *max_abs_left = _max_abs_expr(left, left_sign); Expression *min_abs_right = _min_abs_expr(right, right_sign); Relation abs_rel = comparator.compare(*max_abs_left, *min_abs_right); delete max_abs_left; delete min_abs_right; Expression *result; /// ... Return A if max(|A|) < min(|B|) for the expression mod(A, B) /// ... Note: mod(A, B) < 0 iff A < 0. if (abs_rel.is_less_than()) { result = params.grab(left); } else { /// ... Otherwise, return [0:B-1] for the expression mod(A, B). if (left_sign == POS_NEG_EXPR) { params.modify(left, omega()); return _handle_omega_in_mod(e, comparator); } Expression *bound; if (right.op() == RANGE_OP) if (right_sign == POS_EXPR) bound = ((RangeExpr *) &right)->grab_ub(); else bound = ((RangeExpr *) &right)->grab_lb(); else bound = params.grab(right); if (right_sign == POS_EXPR) bound = sub(bound, constant(1)); else bound = sub(constant(-1), bound); if (left_sign == POS_EXPR) result = new RangeExpr(constant(0), bound); else result = new RangeExpr(unary_minus(bound), constant(0)); } delete e; return result; } /// _p_r_o_of_abs /// Pull ranges out of an ABS intrinsic expression. static Expression * _p_r_o_of_abs(Expression *e, RangeComparator &comparator) { List<Expression> &params = e->parameters_guarded().arg_list(); RangeExpr *range = (RangeExpr *) params.grab(*params.first_ref()); delete e; EXPR_SIGN sign = comparator.sign(*range); Expression *new_expr = 0; switch (sign) { case POS_EXPR: new_expr = range; break; case NEG_EXPR: _negate_range(*range); new_expr = range; break; case POS_NEG_EXPR: new_expr = new RangeExpr(constant(0), _max_abs_expr(*range, sign)); delete range; break; default: p_abort("bad value in switch stmt"); } return new_expr; } /// _pull_ranges_out /// Recursive function that does most of the work of pull_ranges_out above. /// If ranges couldn't be pulled out by the expression, or if the resulting /// expression becomes unconstrained, this function returns 0. static Expression * _pull_ranges_out(Expression *e, RangeComparator &comparator, RANGE_HANDLING range_handling) { if (!e || e->arg_list().entries() == 0) return e; if (comparator.debug_level() >= 50) cout << " pulling ranges out of " << *e << endl; /// ... Determine whether ranges can be pulled out of the expression. If not, /// ... return 0. Otherwise, determine what range handling protocol should /// ... be used when pulling the ranges out of the expression's arguments. RANGE_HANDLING arg_range_handling; switch (e->op()) { case ADD_OP: case COMMA_OP: arg_range_handling = range_handling; break; case INTRINSIC_CALL_OP: { String intr_name = e->intrinsic().symbol().name_ref(); if (intr_name == "MIN" || intr_name == "MAX") arg_range_handling = range_handling; else if (intr_name == "MOD" || intr_name == "ABS" || intr_name == "IABS" || intr_name == "DABS") arg_range_handling = KEEP_WHOLE_RANGE; else { delete e; return 0; } } break; case MULT_OP: case DIV_OP: case EXP_OP: case RANGE_OP: arg_range_handling = KEEP_WHOLE_RANGE; break; case ARRAY_REF_OP: // Added 5/12/98 jh delete e; return 0; default: arg_range_handling = KEEP_WHOLE_RANGE; break; } /// ... Pull out the ranges from the expression's arguments. Mutator<Expression> arg_iter = e->arg_list(); bool has_range_in_args = false; for ( ; arg_iter.valid(); ++arg_iter) { Assign<Expression> eas(arg_iter.assign()); Expression *new_arg = _pull_ranges_out(arg_iter.pull(), comparator, arg_range_handling); if (new_arg && new_arg->op() == OMEGA_OP) { delete new_arg; new_arg = 0; } if (! new_arg) if (e->op() == COMMA_OP) new_arg = omega(); else if (e->op() == EXP_OP || e->op() == RANGE_OP){ new_arg = omega(); has_range_in_args = true; } else { delete e; return 0; } if (new_arg->op() == RANGE_OP) { has_range_in_args = true; if (is_empty_range(*new_arg) && e->op() != COMMA_OP) { delete e; return new_arg; } } eas = new_arg; } /// ... Pull out the ranges from the expression itself. Expression *new_expr = e; if (has_range_in_args) { switch (e->op()) { case ADD_OP: new_expr = _p_r_o_of_add(e); break; case COMMA_OP: /// ... Don't pull ranges out of comma expressions. break; case MULT_OP: new_expr = _p_r_o_of_mult(e, comparator); break; case DIV_OP: new_expr = _p_r_o_of_divide(e, comparator); break; case EXP_OP: new_expr = _p_r_o_of_exp(e, comparator); break; case RANGE_OP: new_expr = _p_r_o_of_range(e); break; default: delete e; return 0; } } else if (e->op() == INTRINSIC_CALL_OP) { has_range_in_args = false; bool has_omega_in_args = false; Mutator<Expression> param_iter = e->parameters_guarded().arg_list(); for ( ; param_iter.valid() && ! has_range_in_args; ++param_iter) if (param_iter.current().op() == RANGE_OP) { has_range_in_args = true; if (is_empty_range(param_iter.current())) { String intr_name = e->intrinsic().symbol().name_ref(); if (intr_name == "MIN" || intr_name == "MAX") param_iter.del(); else { new_expr = param_iter.grab(); delete e; return new_expr; } } } else if (param_iter.current().op() == OMEGA_OP) has_omega_in_args = true; if (has_range_in_args || has_omega_in_args) { String intr_name = e->intrinsic().symbol().name_ref(); if (intr_name == "MIN" || intr_name == "MAX") { new_expr = _p_r_o_of_min_max(new_expr, intr_name == "MIN"); } else if (intr_name == "IFIX" || intr_name == "INT") { if (has_omega_in_args) { delete e; return 0; } new_expr = _p_r_o_of_ifix(e); } else if (intr_name == "MOD") { if (has_omega_in_args) new_expr = _handle_omega_in_mod(e, comparator); else new_expr = _p_r_o_of_mod(e, comparator); } else if (intr_name == "ABS" || intr_name == "IABS" || intr_name == "DABS") { if (has_omega_in_args) { delete e; new_expr = new RangeExpr(constant(0), 0); } else new_expr = _p_r_o_of_abs(e, comparator); } else { delete e; return 0; } } } if (new_expr && new_expr->op() == RANGE_OP) new_expr = _handle_range((RangeExpr *) new_expr, range_handling); if (new_expr) if (new_expr->op() == RANGE_OP) { RangeExpr &range = * (RangeExpr *) new_expr; range.lb(_pull_min_max_out_top(range.grab_lb(), comparator)); range.ub(_pull_min_max_out_top(range.grab_ub(), comparator)); } else new_expr = _pull_min_max_out_top(new_expr, comparator); if (comparator.debug_level() >= 50 && new_expr) cout << " result(pull ranges out): " << *new_expr << endl; return new_expr; } /// pull_ranges_out /// Pull the range subexpressions out of the expression. The range_handling /// argument describes exactly how this is done. /// TAKE_RANGE_MIN: Generate the smallest possible value of the /// expression. (e.g. 2*[1:A]+B --> 2+B) /// TAKE_RANGE_MAX: Generate the largest possible value of the /// expression. (e.g. 2*[1:A]+B --> 2*A+B) /// KEEP_WHOLE_RANGE: Pull the ranges out so that they are outermost. /// (e.g. 2*[1:A]+B --> [2+B:2*A+B]) /// If ranges couldn't be pulled out by the expression, or if the resulting /// expression becomes unconstrained, expression e is set to omega. Expression * pull_ranges_out(Expression * e, RangeComparator &comparator, RANGE_HANDLING range_handling GIV(KEEP_WHOLE_RANGE)) { Expression *new_expr = e; /// bool delete_expr = false; if (e->op() == RANGE_OP && range_handling == KEEP_WHOLE_RANGE) { RangeExpr &range = * (RangeExpr *) e; Expression *new_lb = _pull_ranges_out(range.grab_lb(), comparator, TAKE_RANGE_MIN); Expression *new_ub = _pull_ranges_out(range.grab_ub(), comparator, TAKE_RANGE_MAX); if (! new_lb && ! new_ub) { delete new_expr; new_expr = omega(); } else if (new_lb && is_empty_range(*new_lb)) { delete new_expr; if (new_ub) delete new_ub; return new_lb; } else if (new_ub && is_empty_range(*new_ub)) { delete new_expr; if (new_lb) delete new_lb; return new_ub; } else { range.lb(new_lb); range.ub(new_ub); } } else { new_expr = _pull_ranges_out(e, comparator, range_handling); if (! new_expr) new_expr = omega(); } return new_expr; } /// _min /// Create a new MIN intrinsic with the given arguments. Expression * min_expr(Expression *e1, Expression *e2, const Symtab &symtab) { if (! e1) return e2; if (! e2) return e1; if (e1->op() == OMEGA_OP || (e1->op() == INFINITY_OP && e1->sign() < 0) || (e2->op() == INFINITY_OP && e2->sign() > 0)) return e1; if (e2->op() == OMEGA_OP || (e2->op() == INFINITY_OP && e2->sign() < 0) || (e1->op() == INFINITY_OP && e1->sign() > 0)) return e2; Symbol *s = (Symbol*) symtab.find_ref("MIN"); p_assert(s, "MIN intrinsic is not in symbol table."); return intrinsic_call(id(*s), comma(e1, e2)); } /// max_expr /// Create a new MAX intrinsic with the given arguments. Expression * max_expr(Expression *e1, Expression *e2, const Symtab &symtab) { if (! e1) return e2; if (! e2) return e1; if (e1->op() == OMEGA_OP || (e1->op() == INFINITY_OP && e1->sign() > 0) || (e2->op() == INFINITY_OP && e2->sign() < 0)) return e1; if (e2->op() == OMEGA_OP || (e2->op() == INFINITY_OP && e2->sign() > 0) || (e1->op() == INFINITY_OP && e1->sign() < 0)) return e2; Symbol *s = (Symbol*) symtab.find_ref("MAX"); p_assert(s, "MAX intrinsic is not in symbol table."); return intrinsic_call(id(*s), comma(e1, e2)); } /// mod_expr /// Create a new MOD intrinsic with the given arguments. Expression * mod_expr(Expression *e1, Expression *e2, Symtab &symtab) { p_assert(e1 && e2, "A NULL argument was passed to mod_expr()."); Symbol *mod_sym = (Symbol*) symtab.find_ref("MOD"); if (mod_sym) { if (mod_sym->intrinsic() == NOT_INTRINSIC) { Symbol *mod_sym_var = symtab.grab("MOD"); mod_sym = new FunctionSymbol("MOD", make_type(INTEGER_TYPE), NOT_EXTERNAL, IS_INTRINSIC, NOT_FORMAL); symtab.rename_and_ins(mod_sym_var); } } else { mod_sym = new FunctionSymbol("MOD", make_type(INTEGER_TYPE), NOT_EXTERNAL, IS_INTRINSIC, NOT_FORMAL); symtab.ins(mod_sym); } Expression *mod_expr = intrinsic_call(id(*mod_sym), comma(e1, e2)); mod_expr->type(e1->type()); return mod_expr; } /// _is_min /// Return true if the given expression is a MIN intrinsic bool is_min(const Expression &e) { return (e.op() == INTRINSIC_CALL_OP && strcmp(e.intrinsic().symbol().name_ref(), "MIN") == 0); } /// _is_max /// Return true if the given expression is a MAX intrinsic bool is_max(const Expression &e) { return (e.op() == INTRINSIC_CALL_OP && strcmp(e.intrinsic().symbol().name_ref(), "MAX") == 0); } /// _is_mod /// Return true if the given expression is a MOD intrinsic bool is_mod(const Expression &e) { return (e.op() == INTRINSIC_CALL_OP && strcmp(e.intrinsic().symbol().name_ref(), "MOD") == 0); } /// _is_abs /// Return true if the given expression is a ABS intrinsic bool is_abs(const Expression &e) { return (e.op() == INTRINSIC_CALL_OP && (strcmp(e.intrinsic().symbol().name_ref(), "ABS") == 0 || strcmp(e.intrinsic().symbol().name_ref(), "IABS") == 0 || strcmp(e.intrinsic().symbol().name_ref(), "DABS") == 0)); } /// _is_min_max /// Return true if the given expression is a MIN or MAX intrinsic bool is_min_or_max(const Expression &e) { if (e.op() == INTRINSIC_CALL_OP) { const char *intr_name = e.intrinsic().symbol().name_ref(); return (strcmp(intr_name, "MIN") == 0 || strcmp(intr_name, "MAX") == 0); } return false; } /// _is_min_max /// Return true if the given expression is a MIN or MAX intrinsic bool contains_min_or_max(const Expression &e) { if (is_min_or_max(e)) return true; else { Iterator<Expression> iter = e.arg_list(); for ( ; iter.valid(); ++iter) if (contains_min_or_max(iter.current())) return true; } return false; } /// abs_to_max /// Convert any ABS expressions in the given expression to MAX expressions. Expression * abs_to_max(Expression *e, const Symtab &symtab) { if (! e) return e; if (is_abs(*e)) { Expression *arg = e->parameters_guarded().arg_list().grab(0); delete e; e = max_expr(arg, simplify(unary_minus(arg->clone())), symtab); e->parameters_guarded().arg_list().ins_first(constant(0)); } else { Mutator<Expression> iter = e->arg_list(); for ( ; iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); eas = abs_to_max(iter.pull(), symtab); } } return e; } /// swap_min_max /// Change a MIN intrinsic into a MAX intrinsic or vice_versa void swap_min_max(Expression &e, const Symtab &symtab) { p_assert(is_min_or_max(e), "Expression must be a MIN or MAX intrinsic"); const char *new_intrin; if (is_min(e)) new_intrin = "MAX"; else new_intrin = "MIN"; const Symbol *s = symtab.find_ref(new_intrin); p_assert(s, "Couldn't find MIN or MAX intrinsic in symbol table."); e.intrinsic().symbol(*s); } /// _append_to_list /// Grab and append all elements of list from to list to static void _append_list(List<Expression> &to, List<Expression> &from) { while (from.entries()) to.ins_last(from.grab(*from.first_ref())); } /// _join_nonbinary_exprs /// Create a new nonbinary expression of the given op type. static Expression * _join_nonbinary_exprs(OP_TYPE op, Expression *e1, Expression *e2) { if (e1->op() == op) { e1->arg_list().ins_last(e2); return e1; } else if (e2->op() == op) { e2->arg_list().ins_first(e1); return e2; } else return new NonBinaryExpr(op, e1->type(), e1, e2); } /// _pull_in_add_expr /// Add the given expression to the arguments of the given min or max /// intrinsic. static void _pull_in_add_expr(Expression &min_or_max, const Expression &add_term) { bool add_term_is_min_max = is_min_or_max(add_term); Mutator<Expression> arg_iter = min_or_max.parameters_guarded().arg_list(); for ( ; arg_iter.valid(); ++arg_iter) if (is_min_or_max(arg_iter.current())) _pull_in_add_expr(arg_iter.current(), add_term); else if (add_term_is_min_max) { Assign<Expression> eas(arg_iter.assign()); Expression *new_arg = add_term.clone(); _pull_in_add_expr(*new_arg, arg_iter.current()); delete arg_iter.pull(); eas = new_arg; } else { Assign<Expression> eas2(arg_iter.assign()); eas2 = _join_nonbinary_exprs(ADD_OP, arg_iter.pull(), add_term.clone()); } } /// _p_mm_o_of_add /// Pull the min or max expressions out to the top level of the add /// expression. static Expression * _p_mm_o_of_add(Expression *e) { List<Expression> min_max_args; Mutator<Expression> arg_iter = e->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) if (is_min_or_max(arg_iter.current())) min_max_args.ins_last(arg_iter.grab()); Expression *result = e; if (e->arg_list().entries() == 0) { delete e; result = min_max_args.grab(*min_max_args.first_ref()); } Mutator<Expression> mm_iter = min_max_args; for ( ; mm_iter.valid(); ++mm_iter) { Expression *min_or_max = mm_iter.grab(); _pull_in_add_expr(*min_or_max, *result); delete result; result = min_or_max; } return result; } /// _pull_in_mult_expr /// Add the given expression to the arguments of the given min or max /// intrinsic. static void _pull_in_mult_expr(Expression &min_or_max, const Expression &mult_term, EXPR_SIGN mult_term_sign, RangeComparator &comparator) { bool mult_term_is_min_max = is_min_or_max(mult_term); Mutator<Expression> arg_iter = min_or_max.parameters_guarded().arg_list(); if (mult_term_sign == NEG_EXPR) swap_min_max(min_or_max, comparator.symtab()); for ( ; arg_iter.valid(); ++arg_iter) if (is_min_or_max(arg_iter.current())) _pull_in_mult_expr(arg_iter.current(), mult_term, mult_term_sign, comparator); else if (mult_term_is_min_max) { EXPR_SIGN arg_sign = comparator.sign(arg_iter.current()); if (arg_sign == POS_NEG_EXPR) { Assign<Expression> eas(arg_iter.assign()); eas = _join_nonbinary_exprs(MULT_OP, arg_iter.pull(), mult_term.clone()); } else { Assign<Expression> eas2(arg_iter.assign()); Expression *new_arg = mult_term.clone(); _pull_in_mult_expr(*new_arg, arg_iter.current(), arg_sign, comparator); delete arg_iter.pull(); eas2 = new_arg; } } else { Assign<Expression> eas3(arg_iter.assign()); eas3 = _join_nonbinary_exprs(MULT_OP, arg_iter.pull(), mult_term.clone()); } } /// _p_mm_o_of_mult /// Pull the min or max intrinsics to the outermost part of the given /// multiplication expression. static Expression * _p_mm_o_of_mult(Expression *e, RangeComparator &comparator) { List<Expression> min_max_args; Mutator<Expression> arg_iter = e->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) if (is_min_or_max(arg_iter.current())) min_max_args.ins_last(arg_iter.grab()); /// ... Determine the sign of the non- min or max part Expression *result = e; EXPR_SIGN result_sign = UNKNOWN_SIGN; if (e->arg_list().entries()) { result_sign = comparator.sign(*e); if (result_sign == POS_NEG_EXPR) { _append_list(e->arg_list(), min_max_args); return e; } } else { result_sign = comparator.sign(*min_max_args.first_ref()); if (result_sign == POS_NEG_EXPR) { _append_list(e->arg_list(), min_max_args); return e; } delete e; result = min_max_args.grab(*min_max_args.first_ref()); } Mutator<Expression> mm_iter = min_max_args; bool first_iter = true; for ( ; mm_iter.valid(); ++mm_iter) { /// ... Calculate the sign of result, if it hasn't already been done; if (first_iter) first_iter = false; else { result_sign = comparator.sign(mm_iter.current()); if (result_sign == POS_NEG_EXPR) { result = mul(result, mm_iter.grab()); _append_list(result->arg_list(), min_max_args); return result; } } // Pull the multiplication terms of result into the current min/max /// ... intrinsic Expression *min_or_max = mm_iter.grab(); _pull_in_mult_expr(*min_or_max, *result, result_sign, comparator); delete result; result = min_or_max; } return result; } /// _pull_in_div_expr /// Add the given expression to the arguments of the given min or max /// intrinsic. static void _pull_in_div_expr(Expression &min_or_max, const Expression &denom, EXPR_SIGN denom_sign, const Symtab &symtab) { Mutator<Expression> arg_iter = min_or_max.parameters_guarded().arg_list(); if (denom_sign == NEG_EXPR) swap_min_max(min_or_max, symtab); for ( ; arg_iter.valid(); ++arg_iter) if (is_min_or_max(arg_iter.current())) _pull_in_div_expr(arg_iter.current(), denom, denom_sign, symtab); else { Assign<Expression> eas(arg_iter.assign()); eas = div(arg_iter.pull(), denom.clone()); } } /// _p_mm_o_of_divide /// Pull the min/max intrinsics out of a divide statement. /// This function will only pull min or max expressions out of the numerator static Expression * _p_mm_o_of_divide(Expression *e, RangeComparator &comparator) { if (! is_min_or_max(e->left_guarded())) return e; EXPR_SIGN denom_sign = comparator.signz(e->right_guarded()); if (denom_sign == POS_NEG_EXPR || denom_sign == ZERO_EXPR) return e; Expression *result = e->grab_left(); Expression *denom = e->grab_right(); delete e; _pull_in_div_expr(*result, *denom, denom_sign, comparator.symtab()); delete denom; return result; } /// _pull_in_exp_expr /// Add the given expression to the arguments of the given min or max /// intrinsic. static void _pull_in_exp_expr(Expression &min_or_max, int power, EXPR_SIGN base_sign, const Symtab &symtab) { Mutator<Expression> arg_iter = min_or_max.parameters_guarded().arg_list(); if (base_sign == NEG_EXPR) swap_min_max(min_or_max, symtab); for ( ; arg_iter.valid(); ++arg_iter) if (is_min_or_max(arg_iter.current())) _pull_in_exp_expr(arg_iter.current(), power, base_sign, symtab); else { Assign<Expression> eas(arg_iter.assign()); eas = exponent(arg_iter.pull(), constant(power)); } } /// _p_mm_o_of_exp /// Pull the min/max intrinsics out of an exponentiation statement. static Expression * _p_mm_o_of_exp(Expression *e, RangeComparator &comparator) { if (e->right_guarded().op() != INTEGER_CONSTANT_OP) return e; int power = e->right_guarded().value(); if (! is_min_or_max(e->left_guarded())) return e; EXPR_SIGN base_sign; if (power % 2 == 1) base_sign = POS_EXPR; else { base_sign = comparator.sign(e->left_guarded()); if (base_sign == POS_NEG_EXPR) return e; } Expression *result = e->grab_left(); delete e; _pull_in_exp_expr(*result, power, base_sign, comparator.symtab()); return result; } /// pull_min_max_out_top /// Pull all MIN or MAX intrinsics to the top levels of the expression. static Expression * _pull_min_max_out_top(Expression *e, RangeComparator &comparator) { /// ... Handle the base cases. (Expression leaves and ranges.) if (!e || e->arg_list().entries() == 0) return e; /// ... Pull out the min's or max's from the expression's arguments. Iterator<Expression> arg_iter = e->arg_list(); bool has_min_max_in_args = false; for ( ; arg_iter.valid(); ++arg_iter) if (is_min_or_max(arg_iter.current())) has_min_max_in_args = true; /// ... Pull out the min or max expressions from the expression itself. Expression *new_expr = e; if (has_min_max_in_args) { switch (e->op()) { case ADD_OP: new_expr = _p_mm_o_of_add(e); break; case MULT_OP: new_expr = _p_mm_o_of_mult(e, comparator); break; case DIV_OP: new_expr = _p_mm_o_of_divide(e, comparator); break; case EXP_OP: new_expr = _p_mm_o_of_exp(e, comparator); break; default: /// ... Do nothing break; } } return new_expr; } /// pull_min_max_out /// Pull all MIN or MAX intrinsics to the top levels of the expression. Expression * pull_min_max_out(Expression *e, RangeComparator &comparator) { /// ... Handle the base cases. (Expression leaves and ranges.) if (!e || e->arg_list().entries() == 0) return e; /// ... Pull out the min's or max's from the expression's arguments. Mutator<Expression> arg_iter = e->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) { Assign<Expression> eas(arg_iter.assign()); eas = pull_min_max_out(arg_iter.pull(), comparator); } /// ... Pull out the min or max expressions from the expression itself. return _pull_min_max_out_top(e, comparator); } /// remove_redundant_min_max_terms /// Eliminate all terms of MIN or MAX subexpressions of the given /// expression which can be proved to never be the minimum or maximum /// value respectively. Expression * remove_redundant_min_max_terms(Expression *expr, RangeComparator &comparator) { if (! expr) return expr; if (is_min_or_max(*expr)) { bool expr_is_max = is_max(*expr); List<Expression> &expr_terms = expr->parameters_guarded().arg_list(); List<Expression> examined_terms; while (expr_terms.entries() > 0) { Expression *term = expr_terms.grab(*expr_terms.first_ref()); Mutator<Expression> term_iter = expr_terms; for ( ; term_iter.valid() && term; ++term_iter) { Relation rel = comparator.compare(*term, term_iter.current()); if (rel.is_less_equal()) if (expr_is_max) { delete term; term = 0; } else term_iter.del(); else if (rel.is_greater_equal()) if (expr_is_max) term_iter.del(); else { delete term; term = 0; } } if (term) examined_terms.ins_last(term); } if (examined_terms.entries() == 1) { delete expr; expr = examined_terms.grab(0); } else while (examined_terms.entries()) expr_terms.ins_last(examined_terms.grab(0)); } else { Mutator<Expression> iter = expr->arg_list(); for ( ; iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); eas = remove_redundant_min_max_terms(iter.pull(), comparator); } } return expr; } /// delete_expr_in_list /// Determine whether the given expression equals an expression in the given /// list. If so, delete the expression in the list and return true. static bool _delete_expr_in_list(Expression &expr, List<Expression> &list) { Mutator<Expression> iter = list; for ( ; iter.valid(); ++iter) if (expr == iter.current()) { iter.del(); return true; } return false; } /// _pull_out_common_min_max /// Pull out any common terms of the max expressions in the two range's /// lower bounds and pull out any common terms in the min expressions /// in the upper bounds and return the range containing these common /// terms. static Expression * _pull_out_common_min_max1(Expression *& expr1, Expression *& expr2, bool pull_out_max) { Expression *common_bound = 0; if ((pull_out_max && is_max(*expr1) && is_max(*expr2)) || (! pull_out_max && is_min(*expr1) && is_min(*expr2))) { List<Expression> *common_terms = new List<Expression>; List<Expression> &expr1_args = expr1->parameters_guarded().arg_list(); List<Expression> &expr2_args = expr2->parameters_guarded().arg_list(); Symbol &min_max_symbol = expr1->intrinsic().symbol(); Mutator<Expression> iter = expr1_args; for ( ; iter.valid(); ++iter) if (_delete_expr_in_list(iter.current(), expr2_args)) common_terms->ins_last(iter.grab()); if (expr1_args.entries() == 0) { delete expr1; expr1 = 0; } else if (expr1_args.entries() == 1) { Expression *new_expr1 = expr1_args.grab(*expr1_args.first_ref()); delete expr1; expr1 = new_expr1; } if (expr2_args.entries() == 0) { delete expr2; expr2 = 0; } else if (expr1_args.entries() == 1) { Expression *new_expr2 = expr1_args.grab(*expr2_args.first_ref()); delete expr2; expr2 = new_expr2; } if (common_terms->entries() == 1) { common_bound = common_terms->grab(*common_terms->first_ref()); delete common_terms; } else if (common_terms->entries() >= 2) { common_bound = intrinsic_call(id(min_max_symbol), comma(common_terms)); } else delete common_terms; } else if ((pull_out_max && is_max(*expr1)) || (! pull_out_max && is_min(*expr1))) { List<Expression> &expr1_args = expr1->parameters_guarded().arg_list(); if (_delete_expr_in_list(*expr2, expr1_args)) { common_bound = expr2; expr2 = 0; if (expr1_args.entries() == 1) { Expression *new_expr1 = expr1_args.grab(*expr1_args.first_ref()); delete expr1; expr1 = new_expr1; } } } else if ((pull_out_max && is_max(*expr2)) || (! pull_out_max && is_min(*expr2))) { List<Expression> &expr2_args = expr2->parameters_guarded().arg_list(); if (_delete_expr_in_list(*expr1, expr2_args)) { common_bound = expr1; expr1 = 0; if (expr2_args.entries() == 1) { Expression *new_expr2 = expr2_args.grab(*expr2_args.first_ref()); delete expr2; expr2 = new_expr2; } } } return common_bound; } static RangeExpr * _pull_out_common_min_max(RangeExpr &range1, RangeExpr &range2) { Expression *common_lb = 0; Expression *common_ub = 0; if (range1.has_lb() && range2.has_lb()) { Expression *lb1 = range1.grab_lb(); Expression *lb2 = range2.grab_lb(); common_lb = _pull_out_common_min_max1(lb1, lb2, true); range1.lb(lb1); range2.lb(lb2); } if (range1.has_ub() && range2.has_ub()) { Expression *ub1 = range1.grab_ub(); Expression *ub2 = range2.grab_ub(); common_ub = _pull_out_common_min_max1(ub1, ub2, false); range1.ub(ub1); range2.ub(ub2); } if (common_lb || common_ub) return new RangeExpr(common_lb, common_ub); return 0; } /// join_ranges /// Form the intersection of the two given ranges without any tests. static RangeExpr * _join_ranges(RangeExpr *range1, RangeExpr *range2, const Symtab &symtab) { if (! range1) return range2; if (! range2) return range1; if (range1->has_lb()) { if (range2->has_lb()) range1->lb(max_expr(range1->grab_lb(), range2->grab_lb(), symtab)); } else range1->lb(range2->grab_lb()); if (range1->has_ub()) { if (range2->has_ub()) range1->ub(min_expr(range1->grab_ub(), range2->grab_ub(), symtab)); } else range1->ub(range2->grab_ub()); delete range2; range1->standardize(); return range1; } /// intersect_ranges Expression * intersect_ranges(const Expression *range1_ref, RangeComparator &comparator1, const Expression *range2_ref, RangeComparator &comparator2) { if (! range1_ref || range1_ref->op() == OMEGA_OP) if (range2_ref) return range2_ref->clone(); else return 0; else if (! range2_ref || range2_ref->op() == OMEGA_OP) return range1_ref->clone(); else if (is_empty_range(*range1_ref)) return range1_ref->clone(); else if (is_empty_range(*range2_ref)) return range2_ref->clone(); else if (range1_ref->compare(*range2_ref) == 0) return range1_ref->clone(); RangeExpr *range1 = convert_to_range(range1_ref->clone()); RangeExpr *range2 = convert_to_range(range2_ref->clone()); RangeExpr *common_range = _pull_out_common_min_max(*range1, *range2); bool range_modified = false; int range_join_acc = min(comparator1.range_join_accuracy(), comparator2.range_join_accuracy()); Relation lb_rel = compare(range1->lb(), comparator1, range2->lb(), comparator2); if (! lb_rel.is_equal() && lb_rel.is_less_equal() && ! lb_rel.is_circular()) { range1->lb(range2->grab_lb()); range_modified = true; } else if (lb_rel.is_unknown() && ! lb_rel.is_circular() && range_join_acc >= 1) { range1->lb(max_expr(range1->grab_lb(), range2->grab_lb(), comparator1.symtab())); range_modified = true; } Relation ub_rel = compare(range1->ub(), comparator1, range2->ub(), comparator2); if (! ub_rel.is_equal() && ub_rel.is_greater_equal() && ! ub_rel.is_circular()) { range1->ub(range2->grab_ub()); range_modified = true; } else if (ub_rel.is_unknown() && ! ub_rel.is_circular() && range_join_acc >= 1) { range1->ub(min_expr(range1->grab_ub(), range2->grab_ub(), comparator1.symtab())); range_modified = true; } delete range2; range1 = _join_ranges(range1, common_range, comparator1.symtab()); Expression *result = range1; if (range1->lb() == range1->ub()) { /// ... New range has one element. result = range1->grab_lb(); delete range1; } else if (range_modified && range1->compare(*range2_ref) != 0) { Relation lub_rel = compare(range1->lb(), comparator1, range1->ub(), comparator2); if (lub_rel.is_greater_than()) { /// ... New range has no elements. result = new RangeExpr(constant(1), constant(0)); delete range1; } } result = expr_expand_substituted(result); result = simplify(result); return result; } /// union_ranges Expression * union_ranges(const Expression *range1_ref, RangeComparator &comparator1, const Expression *range2_ref, RangeComparator &comparator2) { if (! range1_ref || range1_ref->op() == OMEGA_OP || ! range2_ref || range2_ref->op() == OMEGA_OP) return 0; else if (is_empty_range(*range1_ref)) return range2_ref->clone(); else if (is_empty_range(*range2_ref)) return range1_ref->clone(); else if (range1_ref->compare(*range2_ref) == 0) return range1_ref->clone(); RangeExpr *range1 = convert_to_range(range1_ref->clone()); RangeExpr *range2 = convert_to_range(range2_ref->clone()); RangeExpr *common_range = _pull_out_common_min_max(*range1, *range2); int range_join_acc = min(comparator1.range_join_accuracy(), comparator2.range_join_accuracy()); Relation lb_rel = compare(range1->lb(), comparator1, range2->lb(), comparator2); if (! lb_rel.is_equal() && lb_rel.is_greater_equal()) range1->lb(range2->grab_lb()); else if (! lb_rel.is_less_equal()) if (range_join_acc <= 1) range1->lb(0); else range1->lb(min_expr(range1->grab_lb(), range2->grab_lb(), comparator1.symtab())); Relation ub_rel = compare(range1->ub(), comparator1, range2->ub(), comparator2); if (! ub_rel.is_equal() && ub_rel.is_less_equal()) range1->ub(range2->grab_ub()); else if (! ub_rel.is_greater_equal()) if (range_join_acc <= 1) range1->ub(0); else range1->ub(max_expr(range1->grab_ub(), range2->grab_ub(), comparator1.symtab())); delete range2; range1 = _join_ranges(range1, common_range, comparator1.symtab()); Expression *result = range1; if (! range1->has_lb() && ! range1->has_ub()) { delete range1; result = 0; } else if (range1->lb() == range1->ub()) { /// ... New range has one element. result = range1->grab_lb(); delete range1; } result = expr_expand_substituted(result); result = simplify(result); return result; } /// widen_range Expression * widen_range(const Expression *expr_ref, const Expression *widener_ref, RangeComparator &comparator) { if (! expr_ref || expr_ref->op() == OMEGA_OP || ! widener_ref || widener_ref->op() == OMEGA_OP) return 0; else if (is_empty_range(*expr_ref)) return widener_ref->clone(); else if (is_empty_range(*widener_ref)) return expr_ref->clone(); RangeExpr *result = convert_to_range(expr_ref->clone()); RangeExpr *widen_range = convert_to_range(widener_ref->clone()); RangeExpr *common_range = _pull_out_common_min_max(*result, *widen_range); if (result->lb() != widen_range->lb()) result->lb(0); if (result->ub() != widen_range->ub()) result->ub(0); delete widen_range; result = _join_ranges(result, common_range, comparator.symtab()); if (! result->has_lb() && ! result->has_ub()) { delete result; result = 0; } else if (result->lb() == result->ub()) { /// ... New range has one element. Expression *temp = result->grab_lb(); delete result; return temp; } return result; } /// narrow_ranges Expression * narrow_range(const Expression *expr_ref, const Expression *narrow_ref, RangeComparator &comparator) { if (! narrow_ref || narrow_ref->op() == OMEGA_OP) { if (expr_ref) return expr_ref->clone(); else return 0; } else if (! expr_ref || expr_ref->op() == OMEGA_OP || narrow_ref->op() != RANGE_OP) return narrow_ref->clone(); RangeExpr *result = convert_to_range(expr_ref->clone()); RangeExpr *narrow_range = convert_to_range(narrow_ref->clone()); RangeExpr *common_range = _pull_out_common_min_max(*result, *narrow_range); if (narrow_range->has_lb()) result->lb(narrow_range->grab_lb()); if (narrow_range->has_ub()) result->ub(narrow_range->grab_ub()); delete narrow_range; result = _join_ranges(result, common_range, comparator.symtab()); if (result->lb() == result->ub()) { /// ... New range has one element. Expression *temp = result->grab_lb(); delete result; return temp; } return result; } /// compare Relation compare(const Expression &e1, RangeComparator &c1, const Expression &e2, RangeComparator &c2) { Relation rel = c1.compare(e1, e2); if (! rel.is_unknown() && &c1 != &c2) rel &= c2.compare(e1, e2); return rel; } /// _negate_rel_op /// Return the inverse of the given relational operator. static OP_TYPE _negate_rel_op(OP_TYPE rel_op) { switch(rel_op) { case LT_OP: return GT_OP; case LE_OP: return GE_OP; case GT_OP: return LT_OP; case GE_OP: return LE_OP; default: return rel_op; } } #if 0 /// _remove_divs_from_term -- /// Remove all integer divisions from the given expression and return /// the term. static Expression * _remove_div(Expression *expr, int &factor, bool take_max) { factor = expr->right_guarded().value(); Expresion *numer = expr->grab_left(); delete expr; if ((factor >= 0 && ! take_max) || (factor < 0 && take_max)) { int truncate = -factor; if (truncate >= 0) --truncate; else ++truncate; numer = add(constant(truncate), numer); } return numer; } static Expression * _remove_divs_from_term(Expression *expr, int &factor, bool take_max) { factor = 1; if (expr->op() == DIV_OP && expr->right_guarded().op() == INTEGER_CONSTANT_OP) { expr = _remove_div(expr, factor, take_max); } else if (expr->op() == MULT_OP && expr->arg_list().entries() == 2) { if (expr->arg_list()[1].op() == INTEGER_CONSTANT_OP) { Expression *swap = expr->arg_list().grab(1); expr->arg_list().ins_first(swap); } if (expr->arg_list()[0].op() == INTEGER_CONSTANT_OP && expr->arg_list()[1].op() == DIV_OP && expr->arg_list()[1].right_guarded().op() == INTEGER_CONSTANT_OP) { int term_factor = expr->arg_list()[0].value(); if (term_factor >= 0) expr->arg_list().ins(1, _remove_div(expr->arg_list().grab(1), factor, take_max)); else expr->arg_list().ins(1, _remove_div(expr->arg_list().grab(1), factor, ! take_max)); if (term_factor % factor == 0) { expr->arg_list()[0].value(term_factor / abs(factor)); factor = (factor >= 0) ? +1; -1; } else if (factor % term_factor == 0) { factor = factor / abs(term_factor); term_factor = (term_factor >= 0) ? +1; -1; } } } return expr; } /// _remove_divs_from_rel -- /// Multiply out all integer divisions from the given comparison expression. static void _remove_divs_from_rel(Expression &expr) { Expression &rel_expr = expr.left_guarded(); if (rel_expr.op() == ADD_OP) { List<Expression> &rel_args = rel_expr.arg_list(); Mutator<Expression> arg_iter = rel_args; for ( ; arg_iter.valid(); ++arg_iter) { Expression *prev = rel_args.prev_ref(arg_iter.current()); Expression *curr = rel_args.grab(arg_iter.current()); _extract_a_range(*curr, expr.op(), &rel_expr, ranges); rel_args.ins_after(curr, prev); } } } #endif /// _extract_a_range -- /// Extract and returns a single range from a binary relation. /// The arguments assume that the relation: /// (var_term + other_terms) rel_op 0 /// holds. static void _extract_a_range(const Expression &var_term, OP_TYPE rel_op, const Expression *other_terms, Map< Symbol, Set<Expression> > &ranges) { /// ... Determine the variable to constrain and its optional multiplicative /// ... factor int factor = 1; const Symbol *var = 0; if (var_term.op() == MULT_OP && var_term.arg_list().entries() == 2) { const Expression &left = *var_term.arg_list().first_ref(); const Expression &right = *var_term.arg_list().last_ref(); if (left.op() == INTEGER_CONSTANT_OP && right.op() == ID_OP) { factor = left.value(); var = &right.symbol(); } else if (left.op() == ID_OP && right.op() == INTEGER_CONSTANT_OP) { var = &left.symbol(); factor = right.value(); } } else if (var_term.op() == ID_OP) { var = &var_term.symbol(); } if (! var) return; /// ... Make sure that the variable doesn't occur on the right hand expression if (other_terms && is_var_in_expr(*other_terms, *var)) return; /// ... Calculate the constraint's bound Expression *bound; if (! other_terms) bound = constant(0); else bound = other_terms->clone(); if (factor >= 0) { bound = unary_minus(bound); } else { factor = -factor; rel_op = _negate_rel_op(rel_op); } if (factor != 1) bound = div(bound, constant(factor)); /// ... Convert < to <= and > to >= if (rel_op == LT_OP) { bound = add(bound, constant(-1)); rel_op = LE_OP; } else if (rel_op == GT_OP) { bound = add(bound, constant(1)); rel_op = GE_OP; } bound = simplify(bound); /// ... Calculate the proper range expression from this bound Expression *range = NULL; switch (rel_op) { case EQ_OP: range = bound; break; case LE_OP: range = new RangeExpr(0, bound); break; case GE_OP: range = new RangeExpr(bound, 0); break; default: p_abort("Internal error: _extract_a_range received a non relation EXPR_OP"); break; } /// ... Add this range to the set of ranges Set<Expression> *var_ranges = ranges.find_ref(*var); if (! var_ranges) { var_ranges = new Set<Expression>; ranges.ins(*var, var_ranges); } var_ranges->ins(range); } /// _extract_ranges_rel -- /// Extract all ranges from a binary relation. Assumes that the relation /// has been simplified. static void _extract_ranges_rel(Expression &expr, Map< Symbol, Set<Expression> > &ranges) { if (expr.left_guarded().type().data_type() != INTEGER_TYPE || expr.right_guarded().type().data_type() != INTEGER_TYPE) return; if (! is_integer_zero(expr.right_guarded())) if (is_integer_zero(expr.left_guarded())) { Expression *temp = expr.grab_left(); expr.left(expr.grab_right()); expr.right(temp); switch (expr.op()) { case LT_OP: expr.op(GT_OP); break; case GE_OP: expr.op(LE_OP); break; case LE_OP: expr.op(GE_OP); break; case GT_OP: expr.op(LT_OP); break; default: break; } } else p_abort("Internal Error: _extract_ranges_rel received an unsimplified relation expr"); Expression &rel_expr = expr.left_guarded(); if (rel_expr.op() == ADD_OP) { List<Expression> &rel_args = rel_expr.arg_list(); Mutator<Expression> arg_iter = rel_args; for ( ; arg_iter.valid(); ++arg_iter) { Expression *prev = rel_args.prev_ref(arg_iter.current()); Expression *curr = rel_args.grab(arg_iter.current()); _extract_a_range(*curr, expr.op(), &rel_expr, ranges); rel_args.ins_after(curr, prev); } } else _extract_a_range(rel_expr, expr.op(), 0, ranges); } /// _extract_ranges void _extract_ranges(Expression &expr, Map< Symbol, Set<Expression> > &ranges) { switch (expr.op()) { case AND_OP: case PAREN_OP: { Iterator<Expression> arg_iter = expr.arg_list(); for ( ; arg_iter.valid(); ++arg_iter) _extract_ranges(arg_iter.current(), ranges); } break; case EQ_OP: case LT_OP: case LE_OP: case GT_OP: case GE_OP: _extract_ranges_rel(expr, ranges); break; default: break; } } /// extract_ranges Map< Symbol, Set<Expression> > * extract_ranges(const Expression &expr, bool complement_expr GIV(false)) { Map< Symbol, Set<Expression> > *ranges = new Map< Symbol, Set<Expression> >; Expression *new_expr = expr.clone(); if (complement_expr) new_expr = not(new_expr); new_expr = expr_expand_substituted(new_expr); new_expr = simplify(new_expr); _extract_ranges(*new_expr, *ranges); delete new_expr; return ranges; } /// pretty_print_range void pretty_print_range(ostream &o, const Expression &expr, const Symbol &var) { if (expr.op() == RANGE_OP) { RangeExpr &range = * (RangeExpr *) &expr; if (range.has_lb() && range.has_ub()) o << range.lb() << "<=" << var.name_ref() << "<=" << range.ub(); else if (range.has_lb()) o << var.name_ref() << ">=" << range.lb(); else if (range.has_ub()) o << var.name_ref() << "<=" << range.ub(); else o << var.name_ref() << "=???"; } else if (expr.op() == OMEGA_OP) o << var.name_ref() << "=???"; else o << var.name_ref() << "=" << expr; } /// elim_known_facts /// /// This routine uses a static recursive routine to turn relational expressions /// inside the given expression into .TRUE. or .FALSE., based on the facts /// passed in the RangeComparator. If the truth of a given relational expression /// cannot be determined, it is unchanged by this routine. Expression * elim_known_facts (Expression *e, RangeComparator &comparator) { Expression * new_expr = _elim_known_facts (e, comparator); new_expr = simplify(new_expr); return new_expr; } /// _elim_known_facts /// Recursive function that does most of the work of elim_known_facts above. /// This routine recursively examines the given expression and /// whenever it finds a piece that it can eliminate based on Range /// information, it does that. /// /// Whenever it finds a relational expression, uses the RangeComparator /// to determine whether the expression is true or false or unknown. /// If it is true, the expression is replaced by .TRUE. Whenever it is /// false, the expression is replaced by .FALSE. . Whenever it is unknown, /// the expression is unchanged. /// /// Whenever if finds a MAX or MIN expression inside, it compares the /// two arguments and if it can determine a clear relationship between /// the two (based on the Range info), it replaces the intrinsic call /// accordingly. static Expression * _elim_known_facts(Expression *e, RangeComparator &comparator) { Expression * new_expr; if (is_relational_op(e->op())) { Relation relate = comparator.compare(e->arg_list()[0],e->arg_list()[1]); switch (e->op()) { case LT_OP: if (relate.is_less_than()) { new_expr = constant(".TRUE."); delete e; } else if (relate.is_greater_equal()) { new_expr = constant(".FALSE."); delete e; } else { new_expr = e; } break; case GT_OP: if (relate.is_greater_than()) { new_expr = constant(".TRUE."); delete e; } else if (relate.is_less_equal()) { new_expr = constant(".FALSE."); delete e; } else { new_expr = e; } break; case LE_OP: if (relate.is_less_equal()) { new_expr = constant(".TRUE."); delete e; } else if (relate.is_greater_than()) { new_expr = constant(".FALSE."); delete e; } else { new_expr = e; } break; case GE_OP: if (relate.is_greater_equal()) { new_expr = constant(".TRUE."); delete e; } else if (relate.is_less_than()) { new_expr = constant(".FALSE."); delete e; } else { new_expr = e; } break; case EQ_OP: if (relate.is_equal()) { new_expr = constant(".TRUE."); delete e; } else if (relate.is_not_equal()) { new_expr = constant(".FALSE."); delete e; } else { new_expr = e; } break; case NE_OP: if (relate.is_not_equal()) { new_expr = constant(".TRUE."); delete e; } else if (relate.is_equal()) { new_expr = constant(".FALSE."); delete e; } else { new_expr = e; } break; default: new_expr = e; break; } /// ... Is this a MIN intrinsic? } else if (is_min(*e)) { if (e->parameters_valid()) { Expression & expr_left = e->parameters_guarded().arg_list()[0]; Expression & expr_right = e->parameters_guarded().arg_list()[1]; Relation relate2 = comparator.compare(expr_left, expr_right); if (relate2.is_greater_than() || relate2.is_greater_equal() || relate2.is_equal()) { new_expr = expr_right.clone(); delete e; } else if (relate2.is_less_than() || relate2.is_less_equal()) { new_expr = expr_left.clone(); delete e; } else { new_expr = e; } } else { new_expr = e; } /// ... Is this a MAX intrinsic? } else if (is_max(*e)) { if (e->parameters_valid()) { Expression & expr_left = e->parameters_guarded().arg_list()[0]; Expression & expr_right = e->parameters_guarded().arg_list()[1]; Relation relate2 = comparator.compare(expr_left, expr_right); if (relate2.is_greater_than() || relate2.is_greater_equal() || relate2.is_equal()) { new_expr = expr_left.clone(); delete e; } else if (relate2.is_less_than() || relate2.is_less_equal()) { new_expr = expr_right.clone(); delete e; } else { new_expr = e; } } else { new_expr = e; } } else { Mutator<Expression> arg_iter = e->arg_list(); for ( ; arg_iter.valid(); ++arg_iter) { Assign<Expression> eas(arg_iter.assign()); Expression *new_arg = _elim_known_facts (arg_iter.pull(), comparator); eas = new_arg; } new_expr = e; } return new_expr; } static Boolean is_scalar_id (const Expression & expr) { if (expr.op() == ID_OP) { if (expr.symbol().is_scalar()) return True; } return False; } void copy_expr_ranges (Expression & expr, RangeAccessor & orig_ranges, StmtRanges & new_ranges) { Traverser tr(expr, is_scalar_id); for ( ; tr.valid(); ++tr) { const Symbol & sym = tr.current().symbol(); if (new_ranges.get_range_ref(sym)) continue; const Expression * old_range = orig_ranges.get_range_ref(sym); if (old_range) { Expression * new_range = old_range->clone(); new_ranges.set_range(tr.current().symbol(), new_range); copy_expr_ranges(*new_range, orig_ranges, new_ranges); } } } static Boolean is_ID_OP (const Expression & expr) { if (expr.op() == ID_OP) { return True; } else { return False; } } /// This routine checks expr for containing exactly one variable, and /// if it does, applies the [lower:upper] range to it. If the variable /// already has an upper or lower bound associated with it, then /// apply the limits to that bound. /// //Note: this routine does not take possesion of lower or upper void apply_limits(Expression & expr, Expression * lower, Expression * upper, StmtRanges & ranges, RefSet<Symbol> & set) { /// ... Now, if expr is just an ID_OP, assert that its range bounds are /// ... within the bounds of the declaration, or if one of its range bounds /// ... is an InfinityExpr, change that to the declaration bounds. int ids = 0; const Symbol * sym = 0; if (expr.op() == ID_OP) { sym = expr.base_variable_ref(); ids = 1; } else { Traverser exprtr(expr, is_ID_OP); for ( ; exprtr.valid(); ++exprtr) { ++ids; sym = exprtr.current().base_variable_ref(); } } if (ids == 1) { /// ... Don't allow infinite recursion if (set.member(*sym)) return; const Expression * expr_range1 = ranges.get_range_ref(*sym); if (expr_range1) { const Expression * expr_range = expr_range1->clone(); if (expr_range->op() == RANGE_OP) { if (lower) { /// ... Check for Infinity in lower bound if (((RangeExpr *)expr_range)->lb().op() == INFINITY_OP) { set_ranges_for_symbol(*(ge(expr.clone(),lower->clone())), *sym, ranges); } else { /// ... if not, constrain the lower bound to be within the declaration bound Expression *lb = substitute_var(expr.clone(), *sym, ((RangeExpr *)expr_range)->lb()); set.ins(*sym); apply_limits(*lb, lower, upper, ranges, set); delete lb; } } if (upper) { /// ... Check for infinity in upper bound if (((RangeExpr *)expr_range)->ub().op() == INFINITY_OP) { set_ranges_for_symbol(*(le(expr.clone(),upper->clone())), *sym, ranges); } else { /// ... if not, constrain the upper bound to be within the declaration bound Expression *ub = substitute_var(expr.clone(), *sym, ((RangeExpr *)expr_range)->ub()); set.ins(*sym); apply_limits(*ub, lower, upper, ranges, set); delete ub; } } } else { /// ... Range is a single value - KDIM: kmax Expression *ex = substitute_var(expr.clone(), *sym, *expr_range); set.ins(*sym); apply_limits(*ex, lower, upper, ranges, set); delete ex; } delete expr_range; } else { if (lower && upper) { set_ranges_for_symbol(*and(ge(expr.clone(),lower->clone()), le(expr.clone(),upper->clone())), *sym, ranges); } else if (lower) { set_ranges_for_symbol(*ge(expr.clone(),lower->clone()), *sym, ranges); } else if (upper) { set_ranges_for_symbol(*le(expr.clone(),upper->clone()), *sym, ranges); } } } else if (expr.op() == INTEGER_CONSTANT_OP) { RefSet<Symbol> tightset; if (upper) tighten_upper_bound(expr, upper, ranges, tightset); tightset.clear(); if (lower) tighten_lower_bound(expr, lower, ranges, tightset); } } /// This routine extracts ranges for a particular symbol from an expression /// and sets them in the given StmtRanges object. It doesn't disturb the /// ranges of any other variable in the StmtRanges object. void set_ranges_for_symbol(Expression & expr, const Symbol & sym, StmtRanges & ranges) { Map<Symbol, Set<Expression> > * map = extract_ranges(expr); Set<Expression> *set = map->find_ref(sym); if (set) { Iterator<Expression> iter = *set; Expression * new_lb = 0; Expression * new_ub = 0; const Expression * expr_range = 0; for ( ; iter.valid(); ++iter) { Expression & range = iter.current(); if (range.op() != RANGE_OP) { if (new_lb == 0) new_lb = range.clone(); if (new_ub == 0) new_ub = range.clone(); } else { if ((((RangeExpr &)range).lb().op() != INFINITY_OP) && (new_lb == 0)) { new_lb = ((RangeExpr &)range).lb().clone(); } else { /// ... Get the existing range if (expr_range == 0) expr_range = ranges.get_range_ref(sym); if (expr_range && (expr_range->op() == RANGE_OP)) { new_lb = ((RangeExpr *)expr_range)->lb().clone(); } } if ((((RangeExpr &)range).ub().op() != INFINITY_OP) && (new_ub == 0)) { new_ub = ((RangeExpr &)range).ub().clone(); } else { /// ... Get the existing range if (expr_range == 0) expr_range = ranges.get_range_ref(sym); if (expr_range && (expr_range->op() == RANGE_OP)) { new_ub = ((RangeExpr *)expr_range)->ub().clone(); } } } } RangeExpr * new_range = new RangeExpr(new_lb, new_ub); ranges.set_range(sym, new_range); } } void tighten_upper_bound(Expression & expr, const Expression *upper, StmtRanges & ranges, RefSet<Symbol> & set) { int ids = 0; const Symbol * sym = 0; if (upper->op() == ID_OP) { sym = upper->base_variable_ref(); ids = 1; } else { Traverser exprtr(*upper, is_ID_OP); for ( ; exprtr.valid(); ++exprtr) { ++ids; sym = exprtr.current().base_variable_ref(); } } if (ids == 1) { /// ... Don't allow infinite recursion if (set.member(*sym)) return; const Expression * expr_range = ranges.get_range_ref(*sym); if (expr_range) { if (expr_range->op() == RANGE_OP) { if (((RangeExpr *)expr_range)->lb().op() == INTEGER_CONSTANT_OP) { if (expr.value() > ((RangeExpr *)expr_range)->lb().value()) { ((RangeExpr *)expr_range)->lb(expr.clone()); } } if (((RangeExpr *)expr_range)->lb().op() != INFINITY_OP) { set.ins(*sym); tighten_lower_bound(expr, &(((RangeExpr *)expr_range)->lb()), ranges, set); } if (((RangeExpr *)expr_range)->ub().op() != INFINITY_OP) { set.ins(*sym); tighten_upper_bound(expr, &(((RangeExpr *)expr_range)->ub()), ranges, set); } } else { /// ... Range is a single value - KDIM: kmax set.ins(*sym); tighten_upper_bound(expr, expr_range, ranges, set); } } } } void tighten_lower_bound(Expression & expr, const Expression *lower, StmtRanges & ranges, RefSet<Symbol> & set) { int ids = 0; const Symbol * sym = 0; if (lower->op() == ID_OP) { sym = lower->base_variable_ref(); ids = 1; } else { Traverser exprtr(*lower, is_ID_OP); for ( ; exprtr.valid(); ++exprtr) { ++ids; sym = exprtr.current().base_variable_ref(); } } if (ids == 1) { /// ... Don't allow infinite recursion if (set.member(*sym)) return; const Expression * expr_range = ranges.get_range_ref(*sym); if (expr_range) { if (expr_range->op() == RANGE_OP) { if (((RangeExpr *)expr_range)->ub().op() == INTEGER_CONSTANT_OP) { if (expr.value() < ((RangeExpr *)expr_range)->ub().value()) { ((RangeExpr *)expr_range)->ub(expr.clone()); } } if (((RangeExpr *)expr_range)->lb().op() != INFINITY_OP) { set.ins(*sym); tighten_lower_bound(expr, &(((RangeExpr *)expr_range)->lb()), ranges, set); } if (((RangeExpr *)expr_range)->ub().op() != INFINITY_OP) { set.ins(*sym); tighten_upper_bound(expr, &(((RangeExpr *)expr_range)->ub()), ranges, set); } } else { /// ... Range is a single value - KDIM: kmax set.ins(*sym); tighten_lower_bound(expr, expr_range, ranges, set); } } } }

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