This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Add overflow infinity handling to VRP
Jan Hubicka <hubicka@ucw.cz> writes:
> Perhaps there is not a better way around, but I am bit concerned about
> making operand_less_p more complicated via all the inline magic.
> What compile time effect does the patch have on compile/20001226-1.c ?
Thanks for the pointer. The effects were bad--about a 40% slowdown.
This version of the patch brings the compilation time back to parity
with what it is today. I'm doing a bootstrap and testsuite run now.
Ian
2007-01-02 Ian Lance Taylor <iant@google.com>
* tree-vrp.c: Include "gt-tree-vrp.h".
(vrp_type_infinity_hash): New static variable.
(has_overflow_infinity): New static function.
(infinity_hash_entry): New static function.
(negative_infinity, positive_infinity): New static functions.
(is_negative_overflow_infinity): New static function.
(is_positive_overflow_infinity): New static function.
(is_overflow_infinity): New static function.
(overflow_infinity_range_p): New static function.
(set_value_range_to_nonnegative): Add overflow_infinity
parameter. Change caller.
(set_value_range): Change TYPE_{MIN,MAX}_VALUE to
{negative,positive}_infinity.
(extract_range_from_assert, vrp_int_const_binop): Likewise.
(extract_range_from_unary_expr): Likewise.
(adjust_range_with_scev): Likewise.
(dump_value_range): Likewise.
(vrp_visit_phi_node): Likewise.
(vrp_operand_equal_p): Check for overflow infinity.
(operand_less_p, compare_values): Likewise.
(extract_range_from_assert, vrp_int_const_binop): Likewise.
(extract_range_from_binary_expr): Likewise.
(extract_range_from_unary_expr): Likewise.
(extract_range_from_comparison): Likewise.
(test_for_singularity): Likewise.
(execute_vrp): Initialize vrp_type_infinity_hash.
* Makefile.in (tree-vrp.o): Depend upon gt-tree-vrp.h.
(GTFILES): Add $(srcdir)/tree-vrp.c.
(gt-tree-vrp.h): New target.
Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c (revision 120378)
+++ gcc/tree-vrp.c (working copy)
@@ -1,5 +1,5 @@
/* Support routines for Value Range Propagation (VRP).
- Copyright (C) 2005, 2006 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>.
This file is part of GCC.
@@ -90,6 +90,151 @@ static sbitmap blocks_visited;
of values that SSA name N_I may take. */
static value_range_t **vr_value;
+/* Hash table of minimum and maximum infinity values for types. */
+static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
+ htab_t vrp_type_infinity_hash;
+
+
+/* Return whether TYPE has an infinity distinct from
+ TYPE_{MIN,MAX}_VALUE. */
+
+static inline bool
+has_overflow_infinity (tree type)
+{
+ return INTEGRAL_TYPE_P (type) && !TYPE_UNSIGNED (type) && !flag_wrapv;
+}
+
+/* Return the entry for the minimum and maximum overflow infinities
+ for TYPE. The overflow infinity is simply a copy of TYPE_MAX_VALUE
+ or TYPE_MIN_VALUE. We use overflow infinities to record an
+ overflow in the positive or negative direction. We only use them
+ for signed types when -fwrapv is not being used. */
+
+static tree
+infinity_hash_entry (tree type)
+{
+ unsigned int hash;
+ struct tree_map in;
+ void **loc;
+ struct tree_map *h;
+ tree min, max;
+
+ hash = htab_hash_pointer (type);
+ in.from = type;
+ loc = htab_find_slot_with_hash (vrp_type_infinity_hash, &in, hash, INSERT);
+ if (*loc != NULL)
+ {
+ h = *(struct tree_map **) loc;
+ return h->to;
+ }
+
+ min = copy_node (TYPE_MIN_VALUE (type));
+ max = copy_node (TYPE_MAX_VALUE (type));
+
+ h = ggc_alloc (sizeof (struct tree_map));
+ h->hash = hash;
+ h->from = type;
+ h->to = tree_cons (min, max, NULL_TREE);
+ *(struct tree_map **) loc = h;
+
+ return h->to;
+}
+
+/* Return the negative infinity to use for TYPE. This is either a
+ overflow infinity or TYPE_MIN_VALUE. */
+
+static tree
+negative_infinity (tree type)
+{
+ if (!has_overflow_infinity (type))
+ {
+ if (INTEGRAL_TYPE_P (type) || SCALAR_FLOAT_TYPE_P (type))
+ return TYPE_MIN_VALUE (type);
+ return NULL_TREE;
+ }
+ return TREE_PURPOSE (infinity_hash_entry (type));
+}
+
+/* Return the positive infinity to use for TYPE. This is either a
+ overflow infinity or TYPE_MAX_VALUE. */
+
+static tree
+positive_infinity (tree type)
+{
+ if (!has_overflow_infinity (type))
+ {
+ if (INTEGRAL_TYPE_P (type) || SCALAR_FLOAT_TYPE_P (type))
+ return TYPE_MAX_VALUE (type);
+ return NULL_TREE;
+ }
+ return TREE_VALUE (infinity_hash_entry (type));
+}
+
+/* Return whether VAL is a negative overflow infinity. This tries to
+ avoid using the hash table. */
+
+static bool
+is_negative_overflow_infinity (tree val)
+{
+ tree type, type_min;
+
+ type = TREE_TYPE (val);
+ if (!has_overflow_infinity (type))
+ return false;
+
+ type_min = TYPE_MIN_VALUE (type);
+ if (TREE_CODE (type_min) == INTEGER_CST)
+ {
+ if (TREE_CODE (val) != INTEGER_CST
+ || !tree_int_cst_equal (val, type_min))
+ return false;
+ }
+ else
+ {
+ if (!operand_equal_p (val, type_min, 0))
+ return false;
+ }
+
+ return val == negative_infinity (type);
+}
+
+/* Return whether VAL is a positive overflow infinity. This tries to
+ avoid using the hash table. */
+
+static bool
+is_positive_overflow_infinity (tree val)
+{
+ tree type, type_max;
+
+ type = TREE_TYPE (val);
+ if (!has_overflow_infinity (type))
+ return false;
+
+ type_max = TYPE_MAX_VALUE (type);
+ if (TREE_CODE (type_max) == INTEGER_CST)
+ {
+ if (TREE_CODE (val) != INTEGER_CST
+ || !tree_int_cst_equal (val, type_max))
+ return false;
+ }
+ else
+ {
+ if (!operand_equal_p (val, type_max, 0))
+ return false;
+ }
+
+ return val == positive_infinity (type);
+}
+
+/* Return whether VAL is a positive or negative overflow infinity. */
+
+static bool
+is_overflow_infinity (tree val)
+{
+ return (is_positive_overflow_infinity (val)
+ || is_negative_overflow_infinity (val));
+}
+
/* Return true if ARG is marked with the nonnull attribute in the
current function signature. */
@@ -154,8 +299,8 @@ set_value_range (value_range_t *vr, enum
gcc_assert (min && max);
if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
- gcc_assert (min != TYPE_MIN_VALUE (TREE_TYPE (min))
- || max != TYPE_MAX_VALUE (TREE_TYPE (max)));
+ gcc_assert (min != negative_infinity (TREE_TYPE (min))
+ || max != positive_infinity (TREE_TYPE (max)));
cmp = compare_values (min, max);
gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
@@ -195,13 +340,21 @@ copy_value_range (value_range_t *to, val
set_value_range (to, from->type, from->min, from->max, from->equiv);
}
-/* Set value range VR to a non-negative range of type TYPE. */
+/* Set value range VR to a non-negative range of type TYPE.
+ OVERFLOW_INFINITY indicates whether to use a overflow infinity
+ rather than TYPE_MAX_VALUE; this should be true if we determine
+ that the range is nonnegative based on an overflow condition. */
static inline void
-set_value_range_to_nonnegative (value_range_t *vr, tree type)
+set_value_range_to_nonnegative (value_range_t *vr, tree type,
+ bool overflow_infinity)
{
tree zero = build_int_cst (type, 0);
- set_value_range (vr, VR_RANGE, zero, TYPE_MAX_VALUE (type), vr->equiv);
+ set_value_range (vr, VR_RANGE, zero,
+ (overflow_infinity
+ ? positive_infinity (type)
+ : TYPE_MAX_VALUE (type)),
+ vr->equiv);
}
/* Set value range VR to a non-NULL range of type TYPE. */
@@ -298,9 +451,15 @@ get_value_range (tree var)
static inline bool
vrp_operand_equal_p (tree val1, tree val2)
{
- return (val1 == val2
- || (val1 && val2
- && operand_equal_p (val1, val2, 0)));
+ if (val1 == val2)
+ return true;
+ if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
+ return false;
+ if (is_positive_overflow_infinity (val1))
+ return is_positive_overflow_infinity (val2);
+ if (is_negative_overflow_infinity (val1))
+ return is_negative_overflow_infinity (val2);
+ return true;
}
/* Return true, if the bitmaps B1 and B2 are equal. */
@@ -392,6 +551,16 @@ symbolic_range_p (value_range_t *vr)
|| !is_gimple_min_invariant (vr->max));
}
+/* Return true if value range VR uses a overflow infinity. */
+
+static inline bool
+overflow_infinity_range_p (value_range_t *vr)
+{
+ return (vr->type == VR_RANGE
+ && (is_overflow_infinity (vr->min)
+ || is_overflow_infinity (vr->max)));
+}
+
/* Like tree_expr_nonnegative_p, but this function uses value ranges
obtained so far. */
@@ -453,20 +622,36 @@ valid_value_p (tree expr)
static inline int
operand_less_p (tree val, tree val2)
{
- tree tcmp;
/* LT is folded faster than GE and others. Inline the common case. */
if (TREE_CODE (val) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST)
{
if (TYPE_UNSIGNED (TREE_TYPE (val)))
return INT_CST_LT_UNSIGNED (val, val2);
else
- return INT_CST_LT (val, val2);
+ {
+ if (INT_CST_LT (val, val2))
+ return 1;
+ }
}
else
- tcmp = fold_binary_to_constant (LT_EXPR, boolean_type_node, val, val2);
- if (!tcmp)
- return -2;
- return !integer_zerop (tcmp);
+ {
+ tree tcmp;
+
+ tcmp = fold_binary_to_constant (LT_EXPR, boolean_type_node, val, val2);
+ if (!tcmp)
+ return -2;
+
+ if (!integer_zerop (tcmp))
+ return 1;
+ }
+
+ /* val >= val2, not considering overflow infinity. */
+ if (is_negative_overflow_infinity (val))
+ return is_negative_overflow_infinity (val2) ? 0 : 1;
+ else if (is_positive_overflow_infinity (val2))
+ return is_positive_overflow_infinity (val) ? 0 : 1;
+
+ return 0;
}
/* Compare two values VAL1 and VAL2. Return
@@ -517,9 +702,15 @@ compare_values (tree val1, tree val2)
c1 = TREE_OPERAND (val1, 1);
if (tree_int_cst_sgn (c1) == -1)
{
- c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1), c1);
- if (!c1)
- return -2;
+ if (is_negative_overflow_infinity (c1))
+ c2 = positive_infinity (TREE_TYPE (c1));
+ else
+ {
+ c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1),
+ c1);
+ if (!c1)
+ return -2;
+ }
code1 = code1 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
}
}
@@ -537,9 +728,15 @@ compare_values (tree val1, tree val2)
c2 = TREE_OPERAND (val2, 1);
if (tree_int_cst_sgn (c2) == -1)
{
- c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2), c2);
- if (!c2)
- return -2;
+ if (is_negative_overflow_infinity (c2))
+ c2 = positive_infinity (TREE_TYPE (c2));
+ else
+ {
+ c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2),
+ c2);
+ if (!c2)
+ return -2;
+ }
code2 = code2 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
}
}
@@ -602,20 +799,53 @@ compare_values (tree val1, tree val2)
if (!POINTER_TYPE_P (TREE_TYPE (val1)))
{
+ int r;
+
/* We cannot compare overflowed values. */
if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
return -2;
- return tree_int_cst_compare (val1, val2);
+ r = tree_int_cst_compare (val1, val2);
+ if (r != 0)
+ return r;
+
+ /* VAL1 == VAL2, not considering overflow infinity. */
+
+ if (val1 == val2)
+ return 0;
+ else if (is_negative_overflow_infinity (val1))
+ return -1;
+ else if (is_negative_overflow_infinity (val2))
+ return 1;
+ else if (is_positive_overflow_infinity (val1))
+ return 1;
+ else if (is_positive_overflow_infinity (val2))
+ return -1;
+ else
+ return 0;
}
else
{
tree t;
/* First see if VAL1 and VAL2 are not the same. */
- if (val1 == val2 || operand_equal_p (val1, val2, 0))
+ if (val1 == val2)
return 0;
+ if (operand_equal_p (val1, val2, 0))
+ {
+ if (is_negative_overflow_infinity (val1))
+ return -1;
+ else if (is_negative_overflow_infinity (val2))
+ return 1;
+ else if (is_positive_overflow_infinity (val1))
+ return 1;
+ else if (is_positive_overflow_infinity (val2))
+ return -1;
+ else
+ return 0;
+ }
+
/* If VAL1 is a lower address than VAL2, return -1. */
if (operand_less_p (val1, val2) == 1)
return -1;
@@ -905,14 +1135,16 @@ extract_range_from_assert (value_range_t
/* If MIN and MAX cover the whole range for their type, then
just use the original LIMIT. */
if (INTEGRAL_TYPE_P (type)
- && min == TYPE_MIN_VALUE (type)
- && max == TYPE_MAX_VALUE (type))
+ && min == negative_infinity (type)
+ && max == positive_infinity (type))
min = max = limit;
set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
}
else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
{
+ /* This should not be negative infinity; there is no overflow
+ here. */
min = TYPE_MIN_VALUE (type);
if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
@@ -933,7 +1165,8 @@ extract_range_from_assert (value_range_t
else
{
/* For LT_EXPR, we create the range [MIN, MAX - 1]. */
- if (cond_code == LT_EXPR)
+ if (cond_code == LT_EXPR
+ && !is_positive_overflow_infinity (max))
{
tree one = build_int_cst (type, 1);
max = fold_build2 (MINUS_EXPR, type, max, one);
@@ -944,6 +1177,8 @@ extract_range_from_assert (value_range_t
}
else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
{
+ /* This should not be positive infinity; there is no overflow
+ here. */
max = TYPE_MAX_VALUE (type);
if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
@@ -964,7 +1199,8 @@ extract_range_from_assert (value_range_t
else
{
/* For GT_EXPR, we create the range [MIN + 1, MAX]. */
- if (cond_code == GT_EXPR)
+ if (cond_code == GT_EXPR
+ && !is_negative_overflow_infinity (min))
{
tree one = build_int_cst (type, 1);
min = fold_build2 (PLUS_EXPR, type, min, one);
@@ -1134,9 +1370,13 @@ extract_range_from_assert (value_range_t
|| compare_values (anti_max, real_min) == 0)
&& compare_values (anti_max, real_max) == -1)
{
- min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
- anti_max,
- build_int_cst (TREE_TYPE (var_vr->min), 1));
+ if (has_overflow_infinity (TREE_TYPE (anti_max))
+ && anti_max == TYPE_MAX_VALUE (TREE_TYPE (anti_max)))
+ min = positive_infinity (TREE_TYPE (var_vr->min));
+ else
+ min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
+ anti_max,
+ build_int_cst (TREE_TYPE (var_vr->min), 1));
max = real_max;
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
}
@@ -1147,9 +1387,13 @@ extract_range_from_assert (value_range_t
&& (compare_values (anti_min, real_max) == -1
|| compare_values (anti_min, real_max) == 0))
{
- max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
- anti_min,
- build_int_cst (TREE_TYPE (var_vr->min), 1));
+ if (has_overflow_infinity (TREE_TYPE (anti_min))
+ && anti_min == TYPE_MIN_VALUE (TREE_TYPE (anti_min)))
+ max = negative_infinity (TREE_TYPE (var_vr->min));
+ else
+ max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
+ anti_min,
+ build_int_cst (TREE_TYPE (var_vr->min), 1));
min = real_min;
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
}
@@ -1236,9 +1480,11 @@ vrp_int_const_binop (enum tree_code code
}
}
- else if (TREE_OVERFLOW (res)
- && !TREE_OVERFLOW (val1)
- && !TREE_OVERFLOW (val2))
+ else if ((TREE_OVERFLOW (res)
+ && !TREE_OVERFLOW (val1)
+ && !TREE_OVERFLOW (val2))
+ || is_overflow_infinity (val1)
+ || is_overflow_infinity (val2))
{
/* If the operation overflowed but neither VAL1 nor VAL2 are
overflown, return -INF or +INF depending on the operation
@@ -1274,9 +1520,9 @@ vrp_int_const_binop (enum tree_code code
|| code == CEIL_DIV_EXPR
|| code == EXACT_DIV_EXPR
|| code == ROUND_DIV_EXPR)
- return TYPE_MAX_VALUE (TREE_TYPE (res));
+ return positive_infinity (TREE_TYPE (res));
else
- return TYPE_MIN_VALUE (TREE_TYPE (res));
+ return negative_infinity (TREE_TYPE (res));
}
return res;
@@ -1430,7 +1676,9 @@ extract_range_from_binary_expr (value_ra
&& vr1.type != VR_VARYING
&& vr0.type == vr1.type
&& !symbolic_range_p (&vr0)
- && !symbolic_range_p (&vr1))
+ && !overflow_infinity_range_p (&vr0)
+ && !symbolic_range_p (&vr1)
+ && !overflow_infinity_range_p (&vr1))
{
/* Boolean expressions cannot be folded with int_const_binop. */
min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min);
@@ -1581,15 +1829,17 @@ extract_range_from_binary_expr (value_ra
if (vr0.type == VR_RANGE
&& vr0.min == vr0.max
&& tree_expr_nonnegative_p (vr0.max)
- && TREE_CODE (vr0.max) == INTEGER_CST)
+ && TREE_CODE (vr0.max) == INTEGER_CST
+ && !overflow_infinity_range_p (&vr0))
{
min = build_int_cst (TREE_TYPE (expr), 0);
max = vr0.max;
}
else if (vr1.type == VR_RANGE
- && vr1.min == vr1.max
- && tree_expr_nonnegative_p (vr1.max)
- && TREE_CODE (vr1.max) == INTEGER_CST)
+ && vr1.min == vr1.max
+ && tree_expr_nonnegative_p (vr1.max)
+ && TREE_CODE (vr1.max) == INTEGER_CST
+ && !overflow_infinity_range_p (&vr1))
{
type = VR_RANGE;
min = build_int_cst (TREE_TYPE (expr), 0);
@@ -1606,8 +1856,12 @@ extract_range_from_binary_expr (value_ra
/* If either MIN or MAX overflowed, then set the resulting range to
VARYING. */
- if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min)
- || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max))
+ if (!is_gimple_min_invariant (min)
+ || TREE_OVERFLOW (min)
+ || is_overflow_infinity (min)
+ || !is_gimple_min_invariant (max)
+ || TREE_OVERFLOW (max)
+ || is_overflow_infinity (max))
{
set_value_range_to_varying (vr);
return;
@@ -1720,12 +1974,25 @@ extract_range_from_unary_expr (value_ran
}
else
{
+ /* There is no overflow implied here, so we don't call
+ negative_infinity or positive_infinity. */
orig_min = TYPE_MIN_VALUE (inner_type);
orig_max = TYPE_MAX_VALUE (inner_type);
}
- new_min = fold_convert (outer_type, orig_min);
- new_max = fold_convert (outer_type, orig_max);
+ if (is_negative_overflow_infinity (orig_min))
+ new_min = negative_infinity (outer_type);
+ else if (is_positive_overflow_infinity (orig_min))
+ new_min = positive_infinity (outer_type);
+ else
+ new_min = fold_convert (outer_type, orig_min);
+
+ if (is_negative_overflow_infinity (orig_max))
+ new_max = negative_infinity (outer_type);
+ else if (is_positive_overflow_infinity (orig_max))
+ new_max = positive_infinity (outer_type);
+ else
+ new_max = fold_convert (outer_type, orig_max);
/* Verify the new min/max values are gimple values and
that they compare equal to the original input's
@@ -1777,16 +2044,30 @@ extract_range_from_unary_expr (value_ran
-~[MIN, MIN] == ~[MIN, MIN]
-[MIN, 0] == [0, MAX] for -fno-wrapv
-[MIN, 0] == [0, MIN] for -fwrapv (will be set to varying later) */
- min = vr0.max == TYPE_MIN_VALUE (TREE_TYPE (expr))
- ? TYPE_MIN_VALUE (TREE_TYPE (expr))
- : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
-
- max = vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr))
- ? (vr0.type == VR_ANTI_RANGE || flag_wrapv
- ? TYPE_MIN_VALUE (TREE_TYPE (expr))
- : TYPE_MAX_VALUE (TREE_TYPE (expr)))
- : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
-
+ if (!has_overflow_infinity (TREE_TYPE (expr)))
+ {
+ min = (vr0.max == TYPE_MIN_VALUE (TREE_TYPE (expr))
+ ? TYPE_MIN_VALUE (TREE_TYPE (expr))
+ : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max));
+
+ max = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr))
+ ? TYPE_MIN_VALUE (TREE_TYPE (expr))
+ : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min));
+ }
+ else
+ {
+ min = (is_positive_overflow_infinity (vr0.max)
+ ? negative_infinity (TREE_TYPE (expr))
+ : (vr0.max == TYPE_MIN_VALUE (TREE_TYPE (expr))
+ ? positive_infinity (TREE_TYPE (expr))
+ : fold_unary_to_constant (code, TREE_TYPE (expr),
+ vr0.max)));
+
+ max = ((is_negative_overflow_infinity (vr0.min)
+ || vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
+ ? positive_infinity (TREE_TYPE (expr))
+ : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min));
+ }
}
else if (code == NEGATE_EXPR
&& TYPE_UNSIGNED (TREE_TYPE (expr)))
@@ -1823,11 +2104,14 @@ extract_range_from_unary_expr (value_ran
/* ABS_EXPR may flip the range around, if the original range
included negative values. */
- min = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
- ? TYPE_MAX_VALUE (TREE_TYPE (expr))
- : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
-
- max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
+ min = ((is_overflow_infinity (vr0.min)
+ || vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
+ ? positive_infinity (TREE_TYPE (expr))
+ : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min));
+
+ max = (is_overflow_infinity (vr0.max)
+ ? positive_infinity (TREE_TYPE (expr))
+ : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max));
cmp = compare_values (min, max);
@@ -1837,8 +2121,6 @@ extract_range_from_unary_expr (value_ran
{
if (range_includes_zero_p (&vr0))
{
- tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr));
-
/* Take the lower of the two values. */
if (cmp != 1)
max = min;
@@ -1847,11 +2129,22 @@ extract_range_from_unary_expr (value_ran
or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
flag_wrapv is set and the original anti-range doesn't include
TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */
- min = (flag_wrapv && vr0.min != type_min_value
- ? int_const_binop (PLUS_EXPR,
- type_min_value,
- integer_one_node, 0)
- : type_min_value);
+ if (flag_wrapv)
+ {
+ tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr));
+
+ min = (vr0.min != type_min_value
+ ? int_const_binop (PLUS_EXPR, type_min_value,
+ integer_one_node, 0)
+ : type_min_value);
+ }
+ else
+ {
+ if (overflow_infinity_range_p (&vr0))
+ min = negative_infinity (TREE_TYPE (expr));
+ else
+ min = TYPE_MIN_VALUE (TREE_TYPE (expr));
+ }
}
else
{
@@ -1860,7 +2153,7 @@ extract_range_from_unary_expr (value_ran
anti-range. */
vr0.type = VR_RANGE;
min = build_int_cst (TREE_TYPE (expr), 0);
- max = TYPE_MAX_VALUE (TREE_TYPE (expr));
+ max = positive_infinity (TREE_TYPE (expr));
}
}
@@ -1888,6 +2181,39 @@ extract_range_from_unary_expr (value_ran
/* Otherwise, operate on each end of the range. */
min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
+
+ if (has_overflow_infinity (TREE_TYPE (expr)))
+ {
+ if (is_negative_overflow_infinity (vr0.min))
+ {
+ if (code == NEGATE_EXPR || code == ABS_EXPR)
+ min = positive_infinity (TREE_TYPE (expr));
+ else
+ min = vr0.min;
+ }
+ else if (is_positive_overflow_infinity (vr0.min))
+ {
+ if (code == NEGATE_EXPR)
+ min = negative_infinity (TREE_TYPE (expr));
+ else
+ min = vr0.min;
+ }
+
+ if (is_positive_overflow_infinity (vr0.max))
+ {
+ if (code == NEGATE_EXPR)
+ max = negative_infinity (TREE_TYPE (expr));
+ else
+ max = vr0.max;
+ }
+ else if (is_negative_overflow_infinity (vr0.max))
+ {
+ if (code == NEGATE_EXPR || code == ABS_EXPR)
+ max = positive_infinity (TREE_TYPE (expr));
+ else
+ max = vr0.max;
+ }
+ }
}
cmp = compare_values (min, max);
@@ -1910,7 +2236,7 @@ static void
extract_range_from_comparison (value_range_t *vr, tree expr)
{
tree val = vrp_evaluate_conditional (expr, false);
- if (val)
+ if (val && !is_overflow_infinity (val))
{
/* Since this expression was found on the RHS of an assignment,
its type may be different from _Bool. Convert VAL to EXPR's
@@ -1959,7 +2285,8 @@ extract_range_from_expr (value_range_t *
{
if (INTEGRAL_TYPE_P (TREE_TYPE (expr))
&& vrp_expr_computes_nonnegative (expr))
- set_value_range_to_nonnegative (vr, TREE_TYPE (expr));
+ set_value_range_to_nonnegative (vr, TREE_TYPE (expr),
+ is_overflow_infinity (expr));
else if (vrp_expr_computes_nonzero (expr))
set_value_range_to_nonnull (vr, TREE_TYPE (expr));
}
@@ -2010,11 +2337,11 @@ adjust_range_with_scev (value_range_t *v
if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
tmin = lower_bound_in_type (type, type);
else
- tmin = TYPE_MIN_VALUE (type);
+ tmin = negative_infinity (type);
if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
tmax = upper_bound_in_type (type, type);
else
- tmax = TYPE_MAX_VALUE (type);
+ tmax = positive_infinity (type);
if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
{
@@ -2348,7 +2675,7 @@ dump_value_range (FILE *file, value_rang
if (INTEGRAL_TYPE_P (type)
&& !TYPE_UNSIGNED (type)
- && vr->min == TYPE_MIN_VALUE (type))
+ && vr->min == negative_infinity (type))
fprintf (file, "-INF");
else
print_generic_expr (file, vr->min, 0);
@@ -2356,7 +2683,7 @@ dump_value_range (FILE *file, value_rang
fprintf (file, ", ");
if (INTEGRAL_TYPE_P (type)
- && vr->max == TYPE_MAX_VALUE (type))
+ && vr->max == positive_infinity (type))
fprintf (file, "+INF");
else
print_generic_expr (file, vr->max, 0);
@@ -4252,18 +4579,30 @@ vrp_visit_phi_node (tree phi)
other case to avoid infinite bouncing between different
minimums. */
if (cmp_min > 0 || cmp_min < 0)
- vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
+ {
+ vr_result.min = negative_infinity (TREE_TYPE (vr_result.min));
+
+ /* If we ended up with a (-INF, +INF) range, set it to
+ VARYING. */
+ if (is_positive_overflow_infinity (vr_result.max)
+ || (vr_result.max
+ == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max))))
+ goto varying;
+ }
/* Similarly, if the new maximum is smaller or larger than
the previous one, go all the way to +INF. */
if (cmp_max < 0 || cmp_max > 0)
- vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
+ {
+ vr_result.max = positive_infinity (TREE_TYPE (vr_result.max));
- /* If we ended up with a (-INF, +INF) range, set it to
- VARYING. */
- if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
- && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
- goto varying;
+ /* If we ended up with a (-INF, +INF) range, set it to
+ VARYING. */
+ if (is_negative_overflow_infinity (vr_result.min)
+ || (vr_result.min
+ == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))))
+ goto varying;
+ }
}
}
@@ -4390,10 +4729,12 @@ test_for_singularity (enum tree_code con
the conditional as it was written. */
if (cond_code == LE_EXPR || cond_code == LT_EXPR)
{
+ /* This should not be negative infinity; there is no overflow
+ here. */
min = TYPE_MIN_VALUE (TREE_TYPE (op0));
max = op1;
- if (cond_code == LT_EXPR)
+ if (cond_code == LT_EXPR && !is_overflow_infinity (max))
{
tree one = build_int_cst (TREE_TYPE (op0), 1);
max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
@@ -4401,10 +4742,12 @@ test_for_singularity (enum tree_code con
}
else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
{
+ /* This should not be positive infinity; there is no overflow
+ here. */
max = TYPE_MAX_VALUE (TREE_TYPE (op0));
min = op1;
- if (cond_code == GT_EXPR)
+ if (cond_code == GT_EXPR && !is_overflow_infinity (min))
{
tree one = build_int_cst (TREE_TYPE (op0), 1);
min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
@@ -4805,6 +5148,10 @@ vrp_finalize (void)
static unsigned int
execute_vrp (void)
{
+ if (vrp_type_infinity_hash == NULL && !flag_wrapv)
+ vrp_type_infinity_hash = htab_create_ggc (10, tree_map_hash, tree_map_eq,
+ NULL);
+
insert_range_assertions ();
loop_optimizer_init (LOOPS_NORMAL);
@@ -4864,3 +5211,5 @@ struct tree_opt_pass pass_vrp =
| TODO_update_smt_usage, /* todo_flags_finish */
0 /* letter */
};
+
+#include "gt-tree-vrp.h"
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in (revision 120378)
+++ gcc/Makefile.in (working copy)
@@ -1929,7 +1929,7 @@ tree-vn.o : tree-vn.c $(CONFIG_H) $(SYST
tree-vrp.o : tree-vrp.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
$(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H) $(DIAGNOSTIC_H) $(GGC_H) \
$(BASIC_BLOCK_H) tree-ssa-propagate.h $(FLAGS_H) $(TREE_DUMP_H) \
- $(CFGLOOP_H) $(SCEV_H) tree-chrec.h $(TIMEVAR_H)
+ $(CFGLOOP_H) $(SCEV_H) tree-chrec.h $(TIMEVAR_H) gt-tree-vrp.h
tree-cfg.o : tree-cfg.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) $(FLAGS_H) output.h \
$(DIAGNOSTIC_H) $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h \
@@ -2881,7 +2881,7 @@ GTFILES = $(srcdir)/input.h $(srcdir)/co
$(srcdir)/tree-ssa-operands.h \
$(srcdir)/tree-profile.c $(srcdir)/tree-nested.c \
$(srcdir)/ipa-reference.c $(srcdir)/tree-ssa-structalias.h \
- $(srcdir)/tree-ssa-structalias.c \
+ $(srcdir)/tree-ssa-structalias.c $(srcdir)/tree-vrp.c \
$(srcdir)/c-pragma.h $(srcdir)/omp-low.c $(srcdir)/varpool.c \
$(srcdir)/targhooks.c $(out_file) \
@all_gtfiles@
@@ -2914,7 +2914,7 @@ gt-tree-profile.h gt-tree-ssa-address.h
gt-tree-iterator.h gt-gimplify.h \
gt-tree-phinodes.h gt-tree-nested.h \
gt-tree-ssa-propagate.h gt-varpool.h \
-gt-tree-ssa-structalias.h gt-ipa-inline.h \
+gt-tree-ssa-structalias.h gt-ipa-inline.h gt-tree-vrp.h \
gt-stringpool.h gt-targhooks.h gt-omp-low.h : s-gtype ; @true
define echo_quoted_to_gtyp