> I'd say we still handle "basic" symbolic range ops in
> extract_range_from_binary_1
> but in extract_range_from_binary_expr for a symbolic op0 we try to simplify
> it with both [op1, op1] and with the value-range of op1 until we get a
> non-varying range as result. Not sure if it's worth restricting that
> to the case
> where op0s value-range refers to op1 or vice versa, and eventually only
> use op1 symbolically then.
Patch along these lines attached. A bit heavy as expected, but it's VRP...
It deals with my pet problem, you might want to check it does so with yours.
Tested on x86_64-suse-linux with no regressions.
2014-05-30 Eric Botcazou <ebotca...@adacore.com>
* tree-vrp.c (get_single_symbol): New function.
(build_symbolic_expr): Likewise.
(symbolic_range_based_on_p): New predicate.
(extract_range_from_binary_expr_1): Deal with single-symbolic ranges
for PLUS and MINUS. Do not drop symbolic ranges at the end.
(extract_range_from_binary_expr): Try harder for PLUS and MINUS if
operand is symbolic and based on the other operand.
2014-05-30 Eric Botcazou <ebotca...@adacore.com>
* gcc.dg/tree-ssa/vrp93.c: New test.
* gnat.dg/opt38.adb: Likewise.
--
Eric BotcazouIndex: tree-vrp.c
===================================================================
--- tree-vrp.c (revision 211019)
+++ tree-vrp.c (working copy)
@@ -916,6 +916,93 @@ symbolic_range_p (value_range_t *vr)
|| !is_gimple_min_invariant (vr->max));
}
+/* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE
+ otherwise. We only handle additive operations and set NEG to true if the
+ symbol is negated and INV to the invariant part, if any. */
+
+static tree
+get_single_symbol (tree t, bool *neg, tree *inv)
+{
+ if (TREE_CODE (t) == PLUS_EXPR
+ || TREE_CODE (t) == POINTER_PLUS_EXPR
+ || TREE_CODE (t) == MINUS_EXPR)
+ {
+ if (is_gimple_min_invariant (TREE_OPERAND (t, 0)))
+ {
+ *inv = TREE_OPERAND (t, 0);
+ *neg = (TREE_CODE (t) == MINUS_EXPR);
+ t = TREE_OPERAND (t, 1);
+ }
+ else if (is_gimple_min_invariant (TREE_OPERAND (t, 1)))
+ {
+ *inv = TREE_OPERAND (t, 1);
+ *neg = false;
+ t = TREE_OPERAND (t, 0);
+ }
+ else
+ return NULL_TREE;
+ }
+ else
+ {
+ *inv = NULL_TREE;
+ *neg = false;
+ }
+
+ if (TREE_CODE (t) == NEGATE_EXPR)
+ {
+ t = TREE_OPERAND (t, 0);
+ *neg = true;
+ }
+
+ if (TREE_CODE (t) != SSA_NAME)
+ return NULL_TREE;
+
+ return t;
+}
+
+/* The reverse operation: build a symbolic expression with TYPE
+ from symbol SYM, negated according to NEG, and invariant INV. */
+
+static tree
+build_symbolic_expr (tree type, tree sym, bool neg, tree inv)
+{
+ const bool pointer_p = POINTER_TYPE_P (type);
+ tree t = sym;
+
+ if (neg)
+ t = build1 (NEGATE_EXPR, type, t);
+
+ if (integer_zerop (inv))
+ return t;
+
+ return build2 (pointer_p ? POINTER_PLUS_EXPR : PLUS_EXPR, type, t, inv);
+}
+
+/* Return true if value range VR involves exactly one symbol SYM. */
+
+static bool
+symbolic_range_based_on_p (value_range_t *vr, const_tree sym)
+{
+ bool neg, min_has_symbol, max_has_symbol;
+ tree inv;
+
+ if (is_gimple_min_invariant (vr->min))
+ min_has_symbol = false;
+ else if (get_single_symbol (vr->min, &neg, &inv) == sym)
+ min_has_symbol = true;
+ else
+ return false;
+
+ if (is_gimple_min_invariant (vr->max))
+ max_has_symbol = false;
+ else if (get_single_symbol (vr->max, &neg, &inv) == sym)
+ max_has_symbol = true;
+ else
+ return false;
+
+ return (min_has_symbol || max_has_symbol);
+}
+
/* Return true if value range VR uses an overflow infinity. */
static inline bool
@@ -2209,7 +2296,7 @@ extract_range_from_multiplicative_op_1 (
}
/* Extract range information from a binary operation CODE based on
- the ranges of each of its operands, *VR0 and *VR1 with resulting
+ the ranges of each of its operands *VR0 and *VR1 with resulting
type EXPR_TYPE. The resulting range is stored in *VR. */
static void
@@ -2303,11 +2390,12 @@ extract_range_from_binary_expr_1 (value_
type = vr0.type;
/* Refuse to operate on VARYING ranges, ranges of different kinds
- and symbolic ranges. As an exception, we allow BIT_AND_EXPR
+ and symbolic ranges. As an exception, we allow BIT_{AND,IOR}
because we may be able to derive a useful range even if one of
the operands is VR_VARYING or symbolic range. Similarly for
- divisions. TODO, we may be able to derive anti-ranges in
- some cases. */
+ divisions, MIN/MAX and PLUS/MINUS.
+
+ TODO, we may be able to derive anti-ranges in some cases. */
if (code != BIT_AND_EXPR
&& code != BIT_IOR_EXPR
&& code != TRUNC_DIV_EXPR
@@ -2318,6 +2406,8 @@ extract_range_from_binary_expr_1 (value_
&& code != TRUNC_MOD_EXPR
&& code != MIN_EXPR
&& code != MAX_EXPR
+ && code != PLUS_EXPR
+ && code != MINUS_EXPR
&& (vr0.type == VR_VARYING
|| vr1.type == VR_VARYING
|| vr0.type != vr1.type
@@ -2376,50 +2466,115 @@ extract_range_from_binary_expr_1 (value_
range and see what we end up with. */
if (code == PLUS_EXPR || code == MINUS_EXPR)
{
- /* If we have a PLUS_EXPR with two VR_RANGE integer constant
- ranges compute the precise range for such case if possible. */
- if (range_int_cst_p (&vr0)
- && range_int_cst_p (&vr1))
- {
- signop sgn = TYPE_SIGN (expr_type);
- unsigned int prec = TYPE_PRECISION (expr_type);
- wide_int type_min = wi::min_value (TYPE_PRECISION (expr_type), sgn);
- wide_int type_max = wi::max_value (TYPE_PRECISION (expr_type), sgn);
- wide_int wmin, wmax;
+ const bool minus_p = (code == MINUS_EXPR);
+ tree min_op0 = vr0.min;
+ tree min_op1 = minus_p ? vr1.max : vr1.min;
+ tree max_op0 = vr0.max;
+ tree max_op1 = minus_p ? vr1.min : vr1.max;
+ tree sym_min_op0 = NULL_TREE;
+ tree sym_min_op1 = NULL_TREE;
+ tree sym_max_op0 = NULL_TREE;
+ tree sym_max_op1 = NULL_TREE;
+ bool neg_min_op0, neg_min_op1, neg_max_op0, neg_max_op1;
+
+ /* If we have a PLUS or MINUS with two VR_RANGEs, either constant or
+ single-symbolic ranges, try to compute the precise resulting range,
+ but only if we know that this resulting range will also be constant
+ or single-symbolic. */
+ if (vr0.type == VR_RANGE && vr1.type == VR_RANGE
+ && (TREE_CODE (min_op0) == INTEGER_CST
+ || (sym_min_op0
+ = get_single_symbol (min_op0, &neg_min_op0, &min_op0)))
+ && (TREE_CODE (min_op1) == INTEGER_CST
+ || (sym_min_op1
+ = get_single_symbol (min_op1, &neg_min_op1, &min_op1)))
+ && (!(sym_min_op0 && sym_min_op1)
+ || (sym_min_op0 == sym_min_op1
+ && neg_min_op0 == (minus_p ? neg_min_op1 : !neg_min_op1)))
+ && (TREE_CODE (max_op0) == INTEGER_CST
+ || (sym_max_op0
+ = get_single_symbol (max_op0, &neg_max_op0, &max_op0)))
+ && (TREE_CODE (max_op1) == INTEGER_CST
+ || (sym_max_op1
+ = get_single_symbol (max_op1, &neg_max_op1, &max_op1)))
+ && (!(sym_max_op0 && sym_max_op1)
+ || (sym_max_op0 == sym_max_op1
+ && neg_max_op0 == (minus_p ? neg_max_op1 : !neg_max_op1))))
+ {
+ const signop sgn = TYPE_SIGN (expr_type);
+ const unsigned int prec = TYPE_PRECISION (expr_type);
+ wide_int type_min, type_max, wmin, wmax;
int min_ovf = 0;
int max_ovf = 0;
- if (code == PLUS_EXPR)
+ /* Get the lower and upper bounds of the type. */
+ if (TYPE_OVERFLOW_WRAPS (expr_type))
{
- wmin = wi::add (vr0.min, vr1.min);
- wmax = wi::add (vr0.max, vr1.max);
-
- /* Check for overflow. */
- if (wi::cmp (vr1.min, 0, sgn) != wi::cmp (wmin, vr0.min, sgn))
- min_ovf = wi::cmp (vr0.min, wmin, sgn);
- if (wi::cmp (vr1.max, 0, sgn) != wi::cmp (wmax, vr0.max, sgn))
- max_ovf = wi::cmp (vr0.max, wmax, sgn);
+ type_min = wi::min_value (prec, sgn);
+ type_max = wi::max_value (prec, sgn);
}
- else /* if (code == MINUS_EXPR) */
+ else
{
- wmin = wi::sub (vr0.min, vr1.max);
- wmax = wi::sub (vr0.max, vr1.min);
+ type_min = vrp_val_min (expr_type);
+ type_max = vrp_val_max (expr_type);
+ }
- if (wi::cmp (0, vr1.max, sgn) != wi::cmp (wmin, vr0.min, sgn))
- min_ovf = wi::cmp (vr0.min, vr1.max, sgn);
- if (wi::cmp (0, vr1.min, sgn) != wi::cmp (wmax, vr0.max, sgn))
- max_ovf = wi::cmp (vr0.max, vr1.min, sgn);
+ /* Combine the lower bounds, if any. */
+ if (min_op0 && min_op1)
+ {
+ if (minus_p)
+ {
+ wmin = wi::sub (min_op0, min_op1);
+
+ /* Check for overflow. */
+ if (wi::cmp (0, min_op1, sgn)
+ != wi::cmp (wmin, min_op0, sgn))
+ min_ovf = wi::cmp (min_op0, min_op1, sgn);
+ }
+ else
+ {
+ wmin = wi::add (min_op0, min_op1);
+
+ /* Check for overflow. */
+ if (wi::cmp (min_op1, 0, sgn)
+ != wi::cmp (wmin, min_op0, sgn))
+ min_ovf = wi::cmp (min_op0, wmin, sgn);
+ }
}
+ else if (min_op0)
+ wmin = min_op0;
+ else if (min_op1)
+ wmin = minus_p ? wi::neg (min_op1) : min_op1;
+ else
+ wmin = wi::shwi (0, prec);
- /* For non-wrapping arithmetic look at possibly smaller
- value-ranges of the type. */
- if (!TYPE_OVERFLOW_WRAPS (expr_type))
+ /* Combine the upper bounds, if any. */
+ if (max_op0 && max_op1)
{
- if (vrp_val_min (expr_type))
- type_min = vrp_val_min (expr_type);
- if (vrp_val_max (expr_type))
- type_max = vrp_val_max (expr_type);
+ if (minus_p)
+ {
+ wmax = wi::sub (max_op0, max_op1);
+
+ /* Check for overflow. */
+ if (wi::cmp (0, max_op1, sgn)
+ != wi::cmp (wmax, max_op0, sgn))
+ max_ovf = wi::cmp (max_op0, max_op1, sgn);
+ }
+ else
+ {
+ wmax = wi::add (max_op0, max_op1);
+
+ if (wi::cmp (max_op1, 0, sgn)
+ != wi::cmp (wmax, max_op0, sgn))
+ max_ovf = wi::cmp (max_op0, wmax, sgn);
+ }
}
+ else if (max_op0)
+ wmax = max_op0;
+ else if (max_op1)
+ wmax = minus_p ? wi::neg (max_op1) : max_op1;
+ else
+ wmax = wi::shwi (0, prec);
/* Check for type overflow. */
if (min_ovf == 0)
@@ -2437,6 +2592,15 @@ extract_range_from_binary_expr_1 (value_
max_ovf = 1;
}
+ /* If we have overflow for the constant part and the resulting
+ range will be symbolic, drop to VR_VARYING. */
+ if ((min_ovf && sym_min_op0 != sym_min_op1)
+ || (max_ovf && sym_max_op0 != sym_max_op1))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
if (TYPE_OVERFLOW_WRAPS (expr_type))
{
/* If overflow wraps, truncate the values and adjust the
@@ -2450,8 +2614,7 @@ extract_range_from_binary_expr_1 (value_
min = wide_int_to_tree (expr_type, tmin);
max = wide_int_to_tree (expr_type, tmax);
}
- else if (min_ovf == -1
- && max_ovf == 1)
+ else if (min_ovf == -1 && max_ovf == 1)
{
/* Underflow and overflow, drop to VR_VARYING. */
set_value_range_to_varying (vr);
@@ -2526,20 +2689,44 @@ extract_range_from_binary_expr_1 (value_
else
max = wide_int_to_tree (expr_type, wmax);
}
+
if (needs_overflow_infinity (expr_type)
&& supports_overflow_infinity (expr_type))
{
- if (is_negative_overflow_infinity (vr0.min)
- || (code == PLUS_EXPR
- ? is_negative_overflow_infinity (vr1.min)
- : is_positive_overflow_infinity (vr1.max)))
+ if ((min_op0 && is_negative_overflow_infinity (min_op0))
+ || (min_op1
+ && (minus_p
+ ? is_positive_overflow_infinity (min_op1)
+ : is_negative_overflow_infinity (min_op1))))
min = negative_overflow_infinity (expr_type);
- if (is_positive_overflow_infinity (vr0.max)
- || (code == PLUS_EXPR
- ? is_positive_overflow_infinity (vr1.max)
- : is_negative_overflow_infinity (vr1.min)))
+ if ((max_op0 && is_positive_overflow_infinity (max_op0))
+ || (max_op1
+ && (minus_p
+ ? is_negative_overflow_infinity (max_op1)
+ : is_positive_overflow_infinity (max_op1))))
max = positive_overflow_infinity (expr_type);
}
+
+ /* If the result lower bound is constant, we're done;
+ otherwise, build the symbolic lower bound. */
+ if (sym_min_op0 == sym_min_op1)
+ ;
+ else if (sym_min_op0)
+ min = build_symbolic_expr (expr_type, sym_min_op0,
+ neg_min_op0, min);
+ else if (sym_min_op1)
+ min = build_symbolic_expr (expr_type, sym_min_op1,
+ neg_min_op1 ^ minus_p, min);
+
+ /* Likewise for the upper bound. */
+ if (sym_max_op0 == sym_max_op1)
+ ;
+ else if (sym_max_op0)
+ max = build_symbolic_expr (expr_type, sym_max_op0,
+ neg_max_op0, max);
+ else if (sym_max_op1)
+ max = build_symbolic_expr (expr_type, sym_max_op1,
+ neg_max_op1 ^ minus_p, max);
}
else
{
@@ -3024,14 +3211,11 @@ extract_range_from_binary_expr_1 (value_
gcc_unreachable ();
/* If either MIN or MAX overflowed, then set the resulting range to
- VARYING. But we do accept an overflow infinity
- representation. */
+ VARYING. But we do accept an overflow infinity representation. */
if (min == NULL_TREE
- || !is_gimple_min_invariant (min)
- || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
+ || (TREE_OVERFLOW_P (min) && !is_overflow_infinity (min))
|| max == NULL_TREE
- || !is_gimple_min_invariant (max)
- || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
+ || (TREE_OVERFLOW_P (max) && !is_overflow_infinity (max)))
{
set_value_range_to_varying (vr);
return;
@@ -3093,6 +3277,58 @@ extract_range_from_binary_expr (value_ra
set_value_range_to_varying (&vr1);
extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1);
+
+ /* Try harder for PLUS and MINUS if the range of one operand is symbolic
+ and based on the other operand. */
+ if (vr->type == VR_VARYING
+ && (code == PLUS_EXPR || code == MINUS_EXPR)
+ && TREE_CODE (op1) == SSA_NAME
+ && vr0.type == VR_RANGE
+ && symbolic_range_based_on_p (&vr0, op1))
+ {
+ value_range_t new_vr1 = VR_INITIALIZER;
+
+ /* Try with VR0 and [-INF, OP1]. */
+ set_value_range (&new_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL);
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1);
+ if (vr->type != VR_VARYING)
+ return;
+
+ /* Try with VR0 and [OP1, +INF]. */
+ set_value_range (&new_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL);
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1);
+ if (vr->type != VR_VARYING)
+ return;
+
+ /* Try with VR0 and [OP1, OP1]. */
+ set_value_range (&new_vr1, VR_RANGE, op1, op1, NULL);
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1);
+ }
+
+ if (vr->type == VR_VARYING
+ && (code == PLUS_EXPR || code == MINUS_EXPR)
+ && TREE_CODE (op0) == SSA_NAME
+ && vr1.type == VR_RANGE
+ && symbolic_range_based_on_p (&vr1, op0))
+ {
+ value_range_t new_vr0 = VR_INITIALIZER;
+
+ /* Try with [-INF, OP0] and VR1. */
+ set_value_range (&new_vr0, VR_RANGE, vrp_val_min (expr_type), op0, NULL);
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &new_vr0, &vr1);
+ if (vr->type != VR_VARYING)
+ return;
+
+ /* Try with [OP0, +INF] and VR1. */
+ set_value_range (&new_vr0, VR_RANGE, op0, vrp_val_max (expr_type), NULL);
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &new_vr0, &vr1);
+ if (vr->type != VR_VARYING)
+ return;
+
+ /* Try with [OP0, OP0] and VR1. */
+ set_value_range (&new_vr0, VR_RANGE, op0, op0, NULL);
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &new_vr0, &vr1);
+ }
}
/* Extract range information from a unary operation CODE based on
