/* Support routines for Value Range Propagation (VRP).
- Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
+ Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>.
This file is part of GCC.
static int compare_values_warnv (tree val1, tree val2, bool *);
static void vrp_meet (value_range_t *, value_range_t *);
static tree vrp_evaluate_conditional_warnv_with_ops (enum tree_code,
- tree, tree, bool, bool *);
+ tree, tree, bool, bool *,
+ bool *);
/* Location information for ASSERT_EXPRs. Each instance of this
structure describes an ASSERT_EXPR for an SSA name. Since a single
static VEC (switch_update, heap) *to_update_switch_stmts;
-/* Return the maximum value for TYPEs base type. */
+/* Return the maximum value for TYPE. */
static inline tree
vrp_val_max (const_tree type)
if (!INTEGRAL_TYPE_P (type))
return NULL_TREE;
- /* For integer sub-types the values for the base type are relevant. */
- if (TREE_TYPE (type))
- type = TREE_TYPE (type);
-
return TYPE_MAX_VALUE (type);
}
-/* Return the minimum value for TYPEs base type. */
+/* Return the minimum value for TYPE. */
static inline tree
vrp_val_min (const_tree type)
if (!INTEGRAL_TYPE_P (type))
return NULL_TREE;
- /* For integer sub-types the values for the base type are relevant. */
- if (TREE_TYPE (type))
- type = TREE_TYPE (type);
-
return TYPE_MIN_VALUE (type);
}
static inline bool
needs_overflow_infinity (const_tree type)
{
- return (INTEGRAL_TYPE_P (type)
- && !TYPE_OVERFLOW_WRAPS (type)
- /* Integer sub-types never overflow as they are never
- operands of arithmetic operators. */
- && !(TREE_TYPE (type) && TREE_TYPE (type) != type));
+ return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type);
}
/* Return whether TYPE can support our overflow infinity
}
-/* Return value range information for VAR.
+/* If abs (min) < abs (max), set VR to [-max, max], if
+ abs (min) >= abs (max), set VR to [-min, min]. */
+
+static void
+abs_extent_range (value_range_t *vr, tree min, tree max)
+{
+ int cmp;
+
+ gcc_assert (TREE_CODE (min) == INTEGER_CST);
+ gcc_assert (TREE_CODE (max) == INTEGER_CST);
+ gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (min)));
+ gcc_assert (!TYPE_UNSIGNED (TREE_TYPE (min)));
+ min = fold_unary (ABS_EXPR, TREE_TYPE (min), min);
+ max = fold_unary (ABS_EXPR, TREE_TYPE (max), max);
+ if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+ cmp = compare_values (min, max);
+ if (cmp == -1)
+ min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), max);
+ else if (cmp == 0 || cmp == 1)
+ {
+ max = min;
+ min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), min);
+ }
+ else
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+ set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL);
+}
+
+
+/* Return value range information for VAR.
If we have no values ranges recorded (ie, VRP is not running), then
return NULL. Otherwise create an empty range if none existed for VAR. */
&& integer_zerop (vr->max);
}
+/* Return true if max and min of VR are INTEGER_CST. It's not necessary
+ a singleton. */
+
+static inline bool
+range_int_cst_p (value_range_t *vr)
+{
+ return (vr->type == VR_RANGE
+ && TREE_CODE (vr->max) == INTEGER_CST
+ && TREE_CODE (vr->min) == INTEGER_CST
+ && !TREE_OVERFLOW (vr->max)
+ && !TREE_OVERFLOW (vr->min));
+}
+
+/* Return true if VR is a INTEGER_CST singleton. */
+
+static inline bool
+range_int_cst_singleton_p (value_range_t *vr)
+{
+ return (range_int_cst_p (vr)
+ && tree_int_cst_equal (vr->min, vr->max));
+}
/* Return true if value range VR involves at least one symbol. */
|| TREE_CODE (expr) == MINUS_EXPR)
return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
&& TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST);
-
+
return is_gimple_min_invariant (expr);
}
-/* Return
+/* Return
1 if VAL < VAL2
0 if !(VAL < VAL2)
-2 if those are incomparable. */
}
/* Compare two values VAL1 and VAL2. Return
-
+
-2 if VAL1 and VAL2 cannot be compared at compile-time,
-1 if VAL1 < VAL2,
0 if VAL1 == VAL2,
{
tree n1, c1, n2, c2;
enum tree_code code1, code2;
-
+
/* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
same name, return -2. */
/* First see if VAL1 and VAL2 are not the same. */
if (val1 == val2 || operand_equal_p (val1, val2, 0))
return 0;
-
+
/* If VAL1 is a lower address than VAL2, return -1. */
if (operand_less_p (val1, val2) == 1)
return -1;
This also applies to value_ranges_intersect_p and
range_includes_zero_p. The semantics of VR_RANGE and
VR_ANTI_RANGE should be encoded here, but that also means
- adapting the users of these functions to the new semantics.
+ adapting the users of these functions to the new semantics.
Benchmark compile/20001226-1.c compilation time after changing this
function. */
/* Return true if value ranges VR0 and VR1 have a non-empty
- intersection.
-
+ intersection.
+
Benchmark compile/20001226-1.c compilation time after changing this
function.
*/
{
value_range_t *vr = get_value_range (t);
+ if (INTEGRAL_TYPE_P (t)
+ && TYPE_UNSIGNED (t))
+ return true;
+
if (!vr)
return false;
return false;
}
-/* Return true if T, an SSA_NAME, is known to be nonzero. Return
- false otherwise or if no value range information is available. */
+/* If OP has a value range with a single constant value return that,
+ otherwise return NULL_TREE. This returns OP itself if OP is a
+ constant. */
-bool
-ssa_name_nonzero_p (const_tree t)
+static tree
+op_with_constant_singleton_value_range (tree op)
{
- value_range_t *vr = get_value_range (t);
+ value_range_t *vr;
- if (!vr)
- return false;
+ if (is_gimple_min_invariant (op))
+ return op;
- /* A VR_RANGE which does not include zero is a nonzero value. */
- if (vr->type == VR_RANGE && !symbolic_range_p (vr))
- return ! range_includes_zero_p (vr);
+ if (TREE_CODE (op) != SSA_NAME)
+ return NULL_TREE;
- /* A VR_ANTI_RANGE which does include zero is a nonzero value. */
- if (vr->type == VR_ANTI_RANGE && !symbolic_range_p (vr))
- return range_includes_zero_p (vr);
+ vr = get_value_range (op);
+ if (vr->type == VR_RANGE
+ && operand_equal_p (vr->min, vr->max, 0)
+ && is_gimple_min_invariant (vr->min))
+ return vr->min;
- return false;
+ return NULL_TREE;
}
The only situation in which we can build a valid
anti-range is when LIMIT_VR is a single-valued range
- (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
+ (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
if (limit_vr
&& limit_vr->type == VR_RANGE
all should be optimized away above us. */
if ((cond_code == LT_EXPR
&& compare_values (max, min) == 0)
- || is_overflow_infinity (max))
+ || (CONSTANT_CLASS_P (max) && TREE_OVERFLOW (max)))
set_value_range_to_varying (vr_p);
else
{
all should be optimized away above us. */
if ((cond_code == GT_EXPR
&& compare_values (min, max) == 0)
- || is_overflow_infinity (min))
+ || (CONSTANT_CLASS_P (min) && TREE_OVERFLOW (min)))
set_value_range_to_varying (vr_p);
else
{
there are three cases to consider.
- 1. The VR_ANTI_RANGE range is completely within the
+ 1. The VR_ANTI_RANGE range is completely within the
VR_RANGE and the endpoints of the ranges are
different. In that case the resulting range
should be whichever range is more precise.
res = int_const_binop (code, val1, val2, 0);
- /* If we are not using wrapping arithmetic, operate symbolically
- on -INF and +INF. */
- if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
+ /* If we are using unsigned arithmetic, operate symbolically
+ on -INF and +INF as int_const_binop only handles signed overflow. */
+ if (TYPE_UNSIGNED (TREE_TYPE (val1)))
{
int checkz = compare_values (res, val1);
bool overflow = false;
}
}
+ else if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
+ /* If the singed operation wraps then int_const_binop has done
+ everything we want. */
+ ;
else if ((TREE_OVERFLOW (res)
&& !TREE_OVERFLOW (val1)
&& !TREE_OVERFLOW (val2))
&& code != CEIL_DIV_EXPR
&& code != EXACT_DIV_EXPR
&& code != ROUND_DIV_EXPR
+ && code != TRUNC_MOD_EXPR
+ && code != FLOOR_MOD_EXPR
+ && code != CEIL_MOD_EXPR
+ && code != ROUND_MOD_EXPR
&& code != RSHIFT_EXPR
&& code != MIN_EXPR
&& code != MAX_EXPR
&& code != BIT_AND_EXPR
+ && code != BIT_IOR_EXPR
&& code != TRUTH_AND_EXPR
&& code != TRUTH_OR_EXPR)
{
+ /* We can still do constant propagation here. */
+ tree const_op0 = op_with_constant_singleton_value_range (op0);
+ tree const_op1 = op_with_constant_singleton_value_range (op1);
+ if (const_op0 || const_op1)
+ {
+ tree tem = fold_binary (code, expr_type,
+ const_op0 ? const_op0 : op0,
+ const_op1 ? const_op1 : op1);
+ if (tem
+ && is_gimple_min_invariant (tem)
+ && !is_overflow_infinity (tem))
+ {
+ set_value_range (vr, VR_RANGE, tem, tem, NULL);
+ return;
+ }
+ }
set_value_range_to_varying (vr);
return;
}
/* Refuse to operate on VARYING ranges, ranges of different kinds
and symbolic ranges. As an exception, we allow BIT_AND_EXPR
because we may be able to derive a useful range even if one of
- the operands is VR_VARYING or symbolic range. TODO, we may be
- able to derive anti-ranges in some cases. */
+ the operands is VR_VARYING or symbolic range. Similarly for
+ divisions. TODO, we may be able to derive anti-ranges in
+ some cases. */
if (code != BIT_AND_EXPR
&& code != TRUTH_AND_EXPR
&& code != TRUTH_OR_EXPR
+ && code != TRUNC_DIV_EXPR
+ && code != FLOOR_DIV_EXPR
+ && code != CEIL_DIV_EXPR
+ && code != EXACT_DIV_EXPR
+ && code != ROUND_DIV_EXPR
+ && code != TRUNC_MOD_EXPR
+ && code != FLOOR_MOD_EXPR
+ && code != CEIL_MOD_EXPR
+ && code != ROUND_MOD_EXPR
&& (vr0.type == VR_VARYING
|| vr1.type == VR_VARYING
|| vr0.type != vr1.type
the same end of each range. */
min = vrp_int_const_binop (code, vr0.min, vr1.min);
max = vrp_int_const_binop (code, vr0.max, vr1.max);
+
+ /* If both additions overflowed the range kind is still correct.
+ This happens regularly with subtracting something in unsigned
+ arithmetic.
+ ??? See PR30318 for all the cases we do not handle. */
+ if (code == PLUS_EXPR
+ && (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
+ && (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
+ {
+ min = build_int_cst_wide (TREE_TYPE (min),
+ TREE_INT_CST_LOW (min),
+ TREE_INT_CST_HIGH (min));
+ max = build_int_cst_wide (TREE_TYPE (max),
+ TREE_INT_CST_LOW (max),
+ TREE_INT_CST_HIGH (max));
+ }
}
else if (code == MULT_EXPR
|| code == TRUNC_DIV_EXPR
}
}
+ else if ((code == TRUNC_DIV_EXPR
+ || code == FLOOR_DIV_EXPR
+ || code == CEIL_DIV_EXPR
+ || code == EXACT_DIV_EXPR
+ || code == ROUND_DIV_EXPR)
+ && (vr0.type != VR_RANGE || symbolic_range_p (&vr0)))
+ {
+ /* For division, if op1 has VR_RANGE but op0 does not, something
+ can be deduced just from that range. Say [min, max] / [4, max]
+ gives [min / 4, max / 4] range. */
+ if (vr1.type == VR_RANGE
+ && !symbolic_range_p (&vr1)
+ && !range_includes_zero_p (&vr1))
+ {
+ vr0.type = type = VR_RANGE;
+ vr0.min = vrp_val_min (TREE_TYPE (op0));
+ vr0.max = vrp_val_max (TREE_TYPE (op1));
+ }
+ else
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+ }
+
+ /* For divisions, if op0 is VR_RANGE, we can deduce a range
+ even if op1 is VR_VARYING, VR_ANTI_RANGE, symbolic or can
+ include 0. */
+ if ((code == TRUNC_DIV_EXPR
+ || code == FLOOR_DIV_EXPR
+ || code == CEIL_DIV_EXPR
+ || code == EXACT_DIV_EXPR
+ || code == ROUND_DIV_EXPR)
+ && vr0.type == VR_RANGE
+ && (vr1.type != VR_RANGE
+ || symbolic_range_p (&vr1)
+ || range_includes_zero_p (&vr1)))
+ {
+ tree zero = build_int_cst (TREE_TYPE (vr0.min), 0);
+ int cmp;
+
+ sop = false;
+ min = NULL_TREE;
+ max = NULL_TREE;
+ if (vrp_expr_computes_nonnegative (op1, &sop) && !sop)
+ {
+ /* For unsigned division or when divisor is known
+ to be non-negative, the range has to cover
+ all numbers from 0 to max for positive max
+ and all numbers from min to 0 for negative min. */
+ cmp = compare_values (vr0.max, zero);
+ if (cmp == -1)
+ max = zero;
+ else if (cmp == 0 || cmp == 1)
+ max = vr0.max;
+ else
+ type = VR_VARYING;
+ cmp = compare_values (vr0.min, zero);
+ if (cmp == 1)
+ min = zero;
+ else if (cmp == 0 || cmp == -1)
+ min = vr0.min;
+ else
+ type = VR_VARYING;
+ }
+ else
+ {
+ /* Otherwise the range is -max .. max or min .. -min
+ depending on which bound is bigger in absolute value,
+ as the division can change the sign. */
+ abs_extent_range (vr, vr0.min, vr0.max);
+ return;
+ }
+ if (type == VR_VARYING)
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+ }
+
/* Multiplications and divisions are a bit tricky to handle,
depending on the mix of signs we have in the two ranges, we
need to operate on different values to get the minimum and
(MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
MAX1) and then figure the smallest and largest values to form
the new range. */
-
- /* Divisions by zero result in a VARYING value. */
- else if (code != MULT_EXPR
- && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
- {
- set_value_range_to_varying (vr);
- return;
- }
-
- /* Compute the 4 cross operations. */
- sop = false;
- val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
- if (val[0] == NULL_TREE)
- sop = true;
-
- if (vr1.max == vr1.min)
- val[1] = NULL_TREE;
else
{
- val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
- if (val[1] == NULL_TREE)
- sop = true;
- }
+ gcc_assert ((vr0.type == VR_RANGE
+ || (code == MULT_EXPR && vr0.type == VR_ANTI_RANGE))
+ && vr0.type == vr1.type);
- if (vr0.max == vr0.min)
- val[2] = NULL_TREE;
- else
- {
- val[2] = vrp_int_const_binop (code, vr0.max, vr1.min);
- if (val[2] == NULL_TREE)
+ /* Compute the 4 cross operations. */
+ sop = false;
+ val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
+ if (val[0] == NULL_TREE)
sop = true;
- }
- if (vr0.min == vr0.max || vr1.min == vr1.max)
- val[3] = NULL_TREE;
- else
- {
- val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
- if (val[3] == NULL_TREE)
- sop = true;
- }
+ if (vr1.max == vr1.min)
+ val[1] = NULL_TREE;
+ else
+ {
+ val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
+ if (val[1] == NULL_TREE)
+ sop = true;
+ }
- if (sop)
- {
- set_value_range_to_varying (vr);
- return;
- }
+ if (vr0.max == vr0.min)
+ val[2] = NULL_TREE;
+ else
+ {
+ val[2] = vrp_int_const_binop (code, vr0.max, vr1.min);
+ if (val[2] == NULL_TREE)
+ sop = true;
+ }
- /* Set MIN to the minimum of VAL[i] and MAX to the maximum
- of VAL[i]. */
- min = val[0];
- max = val[0];
- for (i = 1; i < 4; i++)
- {
- 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)))
- break;
+ if (vr0.min == vr0.max || vr1.min == vr1.max)
+ val[3] = NULL_TREE;
+ else
+ {
+ val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
+ if (val[3] == NULL_TREE)
+ sop = true;
+ }
+
+ if (sop)
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
- if (val[i])
+ /* Set MIN to the minimum of VAL[i] and MAX to the maximum
+ of VAL[i]. */
+ min = val[0];
+ max = val[0];
+ for (i = 1; i < 4; i++)
{
- if (!is_gimple_min_invariant (val[i])
- || (TREE_OVERFLOW (val[i])
- && !is_overflow_infinity (val[i])))
+ 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)))
+ break;
+
+ if (val[i])
{
- /* If we found an overflowed value, set MIN and MAX
- to it so that we set the resulting range to
- VARYING. */
- min = max = val[i];
- break;
- }
+ if (!is_gimple_min_invariant (val[i])
+ || (TREE_OVERFLOW (val[i])
+ && !is_overflow_infinity (val[i])))
+ {
+ /* If we found an overflowed value, set MIN and MAX
+ to it so that we set the resulting range to
+ VARYING. */
+ min = max = val[i];
+ break;
+ }
- if (compare_values (val[i], min) == -1)
- min = val[i];
+ if (compare_values (val[i], min) == -1)
+ min = val[i];
- if (compare_values (val[i], max) == 1)
- max = val[i];
+ if (compare_values (val[i], max) == 1)
+ max = val[i];
+ }
}
}
}
+ else if (code == TRUNC_MOD_EXPR
+ || code == FLOOR_MOD_EXPR
+ || code == CEIL_MOD_EXPR
+ || code == ROUND_MOD_EXPR)
+ {
+ bool sop = false;
+ if (vr0.type == VR_ANTI_RANGE
+ || vr1.type != VR_RANGE
+ || symbolic_range_p (&vr1)
+ || range_includes_zero_p (&vr1))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+ type = VR_RANGE;
+ max = int_const_binop (MINUS_EXPR, vr1.max, integer_one_node, 0);
+ if (vrp_expr_computes_nonnegative (op0, &sop)
+ && vrp_expr_computes_nonnegative (op1, &sop) && !sop)
+ min = build_int_cst (TREE_TYPE (vr1.max), 0);
+ else
+ min = fold_unary (NEGATE_EXPR, TREE_TYPE (max), max);
+ }
else if (code == MINUS_EXPR)
{
/* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
}
else if (code == BIT_AND_EXPR)
{
- if (vr0.type == VR_RANGE
- && vr0.min == vr0.max
- && TREE_CODE (vr0.max) == INTEGER_CST
- && !TREE_OVERFLOW (vr0.max)
- && tree_int_cst_sgn (vr0.max) >= 0)
+ bool vr0_int_cst_singleton_p, vr1_int_cst_singleton_p;
+
+ vr0_int_cst_singleton_p = range_int_cst_singleton_p (&vr0);
+ vr1_int_cst_singleton_p = range_int_cst_singleton_p (&vr1);
+
+ if (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p)
+ min = max = int_const_binop (code, vr0.max, vr1.max, 0);
+ else if (vr0_int_cst_singleton_p
+ && tree_int_cst_sgn (vr0.max) >= 0)
{
min = build_int_cst (expr_type, 0);
max = vr0.max;
}
- else if (vr1.type == VR_RANGE
- && vr1.min == vr1.max
- && TREE_CODE (vr1.max) == INTEGER_CST
- && !TREE_OVERFLOW (vr1.max)
+ else if (vr1_int_cst_singleton_p
&& tree_int_cst_sgn (vr1.max) >= 0)
{
type = VR_RANGE;
return;
}
}
+ else if (code == BIT_IOR_EXPR)
+ {
+ if (range_int_cst_p (&vr0)
+ && range_int_cst_p (&vr1)
+ && tree_int_cst_sgn (vr0.min) >= 0
+ && tree_int_cst_sgn (vr1.min) >= 0)
+ {
+ double_int vr0_max = tree_to_double_int (vr0.max);
+ double_int vr1_max = tree_to_double_int (vr1.max);
+ double_int ior_max;
+
+ /* Set all bits to the right of the most significant one to 1.
+ For example, [0, 4] | [4, 4] = [4, 7]. */
+ ior_max.low = vr0_max.low | vr1_max.low;
+ ior_max.high = vr0_max.high | vr1_max.high;
+ if (ior_max.high != 0)
+ {
+ ior_max.low = ~(unsigned HOST_WIDE_INT)0u;
+ ior_max.high |= ((HOST_WIDE_INT) 1
+ << floor_log2 (ior_max.high)) - 1;
+ }
+ else if (ior_max.low != 0)
+ ior_max.low |= ((unsigned HOST_WIDE_INT) 1u
+ << floor_log2 (ior_max.low)) - 1;
+
+ /* Both of these endpoints are conservative. */
+ min = vrp_int_const_binop (MAX_EXPR, vr0.min, vr1.min);
+ max = double_int_to_tree (expr_type, ior_max);
+ }
+ else
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+ }
else
gcc_unreachable ();
|| code == BIT_NOT_EXPR
|| code == CONJ_EXPR)
{
+ /* We can still do constant propagation here. */
+ if ((op0 = op_with_constant_singleton_value_range (op0)) != NULL_TREE)
+ {
+ tree tem = fold_unary (code, type, op0);
+ if (tem
+ && is_gimple_min_invariant (tem)
+ && !is_overflow_infinity (tem))
+ {
+ set_value_range (vr, VR_RANGE, tem, tem, NULL);
+ return;
+ }
+ }
set_value_range_to_varying (vr);
return;
}
tree inner_type = TREE_TYPE (op0);
tree outer_type = type;
- /* Always use base-types here. This is important for the
- correct signedness. */
- if (TREE_TYPE (inner_type))
- inner_type = TREE_TYPE (inner_type);
- if (TREE_TYPE (outer_type))
- outer_type = TREE_TYPE (outer_type);
-
/* If VR0 is varying and we increase the type precision, assume
a full range for the following transformation. */
if (vr0.type == VR_VARYING
|| vr0.type == VR_ANTI_RANGE)
&& TREE_CODE (vr0.min) == INTEGER_CST
&& TREE_CODE (vr0.max) == INTEGER_CST
- && !is_overflow_infinity (vr0.min)
- && !is_overflow_infinity (vr0.max)
+ && (!is_overflow_infinity (vr0.min)
+ || (vr0.type == VR_RANGE
+ && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)
+ && needs_overflow_infinity (outer_type)
+ && supports_overflow_infinity (outer_type)))
+ && (!is_overflow_infinity (vr0.max)
+ || (vr0.type == VR_RANGE
+ && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)
+ && needs_overflow_infinity (outer_type)
+ && supports_overflow_infinity (outer_type)))
&& (TYPE_PRECISION (outer_type) >= TYPE_PRECISION (inner_type)
|| (vr0.type == VR_RANGE
&& integer_zerop (int_const_binop (RSHIFT_EXPR,
new_max = force_fit_type_double (outer_type,
TREE_INT_CST_LOW (vr0.max),
TREE_INT_CST_HIGH (vr0.max), 0, 0);
+ if (is_overflow_infinity (vr0.min))
+ new_min = negative_overflow_infinity (outer_type);
+ if (is_overflow_infinity (vr0.max))
+ new_max = positive_overflow_infinity (outer_type);
set_and_canonicalize_value_range (vr, vr0.type,
new_min, new_max, NULL);
return;
set_value_range_to_varying (vr);
return;
}
-
+
/* ABS_EXPR may flip the range around, if the original range
included negative values. */
if (is_overflow_infinity (vr0.min))
max = fold_unary_to_constant (code, type, vr0.max);
else if (!needs_overflow_infinity (type))
max = TYPE_MAX_VALUE (type);
- else if (supports_overflow_infinity (type))
+ else if (supports_overflow_infinity (type)
+ /* We shouldn't generate [+INF, +INF] as set_value_range
+ doesn't like this and ICEs. */
+ && !is_positive_overflow_infinity (min))
max = positive_overflow_infinity (type);
else
{
/* If a VR_ANTI_RANGEs contains zero, then we have
~[-INF, min(MIN, MAX)]. */
if (vr0.type == VR_ANTI_RANGE)
- {
+ {
if (range_includes_zero_p (&vr0))
{
/* Take the lower of the two values. */
{
bool sop = false;
tree val;
-
- val = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, false, &sop);
+
+ val = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, false, &sop,
+ NULL);
/* A disadvantage of using a special infinity as an overflow
representation is that we lose the ability to record overflow
adjust_range_with_scev (value_range_t *vr, struct loop *loop,
gimple stmt, tree var)
{
- tree init, step, chrec, tmin, tmax, min, max, type;
+ tree init, step, chrec, tmin, tmax, min, max, type, tem;
enum ev_direction dir;
/* TODO. Don't adjust anti-ranges. An anti-range may provide
return;
init = initial_condition_in_loop_num (chrec, loop->num);
+ tem = op_with_constant_singleton_value_range (init);
+ if (tem)
+ init = tem;
step = evolution_part_in_loop_num (chrec, loop->num);
+ tem = op_with_constant_singleton_value_range (step);
+ if (tem)
+ step = tem;
/* If STEP is symbolic, we can't know whether INIT will be the
minimum or maximum value in the range. Also, unless INIT is
return true;
l = loop_containing_stmt (stmt);
- if (l == NULL)
+ if (l == NULL
+ || !loop_outer (l))
return true;
chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var));
/* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
-
+
- Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
all the values in the ranges.
/* Otherwise, we don't know. */
return NULL_TREE;
}
-
+
gcc_unreachable ();
}
if (COMPARISON_CLASS_P (cond))
{
- tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
+ tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
assertion = gimple_build_assign (n, a);
}
else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
gimple_stmt_iterator si)
{
assert_locus_t n, loc, last_loc;
- bool found;
basic_block dest_bb;
#if defined ENABLE_CHECKING
&& gimple_code (gsi_stmt (si)) != GIMPLE_SWITCH);
#endif
+ /* Never build an assert comparing against an integer constant with
+ TREE_OVERFLOW set. This confuses our undefined overflow warning
+ machinery. */
+ if (TREE_CODE (val) == INTEGER_CST
+ && TREE_OVERFLOW (val))
+ val = build_int_cst_wide (TREE_TYPE (val),
+ TREE_INT_CST_LOW (val), TREE_INT_CST_HIGH (val));
+
/* The new assertion A will be inserted at BB or E. We need to
determine if the new location is dominated by a previously
registered location for A. If we are doing an edge insertion,
assume that A will be inserted at E->DEST. Note that this is not
necessarily true.
-
+
If E is a critical edge, it will be split. But even if E is
split, the new block will dominate the same set of blocks that
E->DEST dominates.
-
+
The reverse, however, is not true, blocks dominated by E->DEST
will not be dominated by the new block created to split E. So,
if the insertion location is on a critical edge, we will not use
COMP_CODE and VAL could be implemented. */
loc = asserts_for[SSA_NAME_VERSION (name)];
last_loc = loc;
- found = false;
while (loc)
{
if (loc->comp_code == comp_code
/* OP is an operand of a truth value expression which is known to have
a particular value. Register any asserts for OP and for any
- operands in OP's defining statement.
+ operands in OP's defining statement.
If CODE is EQ_EXPR, then we want to register OP is zero (false),
if CODE is NE_EXPR, then we want to register OP is nonzero (true). */
return false;
/* We know that OP will have a zero or nonzero value. If OP is used
- more than once go ahead and register an assert for OP.
+ more than once go ahead and register an assert for OP.
The FOUND_IN_SUBGRAPH support is not helpful in this situation as
it will always be set for OP (because OP is used in a COND_EXPR in
code, e, bsi);
}
else if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (op_def)))
- {
+ {
/* Recurse through the type conversion. */
retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
code, e, bsi);
edge e;
tree vec2;
size_t n = gimple_switch_num_labels(last);
+#if GCC_VERSION >= 4000
unsigned int idx;
+#else
+ /* Work around GCC 3.4 bug (PR 37086). */
+ volatile unsigned int idx;
+#endif
need_assert = false;
bsi = gsi_for_stmt (last);
If a statement produces a useful assertion A for name N_i, then the
list of assertions already generated for N_i is scanned to
determine if A is actually needed.
-
+
If N_i already had the assertion A at a location dominating the
current location, then nothing needs to be done. Otherwise, the
new location for A is recorded instead.
4- If BB does not end in a conditional expression, then we recurse
into BB's dominator children.
-
+
At the end of the recursive traversal, every SSA name will have a
list of locations where ASSERT_EXPRs should be added. When a new
location for name N is found, it is registered by calling
stmt = gsi_stmt (si);
+ if (is_gimple_debug (stmt))
+ continue;
+
/* See if we can derive an assertion for any of STMT's operands. */
FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
{
{
tree t = op;
gimple def_stmt = SSA_NAME_DEF_STMT (t);
-
+
while (is_gimple_assign (def_stmt)
&& gimple_assign_rhs_code (def_stmt) == NOP_EXPR
&& TREE_CODE
edge_iterator ei;
edge e;
+ /* If we have X <=> X do not insert an assert expr for that. */
+ if (loc->expr == loc->val)
+ return false;
+
cond = build2 (loc->comp_code, boolean_type_node, loc->expr, loc->val);
assert_stmt = build_assert_expr_for (cond, name);
if (loc->e)
IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR. */
static void
-check_array_ref (tree ref, const location_t *location, bool ignore_off_by_one)
+check_array_ref (location_t location, tree ref, bool ignore_off_by_one)
{
value_range_t* vr = NULL;
tree low_sub, up_sub;
- tree low_bound, up_bound = array_ref_up_bound (ref);
+ tree low_bound, up_bound, up_bound_p1;
+ tree base;
+
+ if (TREE_NO_WARNING (ref))
+ return;
low_sub = up_sub = TREE_OPERAND (ref, 1);
+ up_bound = array_ref_up_bound (ref);
- if (!up_bound || TREE_NO_WARNING (ref)
- || TREE_CODE (up_bound) != INTEGER_CST
- /* Can not check flexible arrays. */
- || (TYPE_SIZE (TREE_TYPE (ref)) == NULL_TREE
- && TYPE_DOMAIN (TREE_TYPE (ref)) != NULL_TREE
- && TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (ref))) == NULL_TREE)
- /* Accesses after the end of arrays of size 0 (gcc
- extension) and 1 are likely intentional ("struct
- hack"). */
- || compare_tree_int (up_bound, 1) <= 0)
+ /* Can not check flexible arrays. */
+ if (!up_bound
+ || TREE_CODE (up_bound) != INTEGER_CST)
return;
+ /* Accesses to trailing arrays via pointers may access storage
+ beyond the types array bounds. */
+ base = get_base_address (ref);
+ if (base
+ && INDIRECT_REF_P (base))
+ {
+ tree cref, next = NULL_TREE;
+
+ if (TREE_CODE (TREE_OPERAND (ref, 0)) != COMPONENT_REF)
+ return;
+
+ cref = TREE_OPERAND (ref, 0);
+ if (TREE_CODE (TREE_TYPE (TREE_OPERAND (cref, 0))) == RECORD_TYPE)
+ for (next = TREE_CHAIN (TREE_OPERAND (cref, 1));
+ next && TREE_CODE (next) != FIELD_DECL;
+ next = TREE_CHAIN (next))
+ ;
+
+ /* If this is the last field in a struct type or a field in a
+ union type do not warn. */
+ if (!next)
+ return;
+ }
+
low_bound = array_ref_low_bound (ref);
+ up_bound_p1 = int_const_binop (PLUS_EXPR, up_bound, integer_one_node, 0);
if (TREE_CODE (low_sub) == SSA_NAME)
{
&& TREE_CODE (low_sub) == INTEGER_CST
&& tree_int_cst_lt (low_sub, low_bound))
{
- warning (OPT_Warray_bounds,
- "%Harray subscript is outside array bounds", location);
+ warning_at (location, OPT_Warray_bounds,
+ "array subscript is outside array bounds");
TREE_NO_WARNING (ref) = 1;
}
}
else if (TREE_CODE (up_sub) == INTEGER_CST
- && tree_int_cst_lt (up_bound, up_sub)
- && !tree_int_cst_equal (up_bound, up_sub)
- && (!ignore_off_by_one
- || !tree_int_cst_equal (int_const_binop (PLUS_EXPR,
- up_bound,
- integer_one_node,
- 0),
- up_sub)))
- {
- warning (OPT_Warray_bounds, "%Harray subscript is above array bounds",
- location);
+ && (ignore_off_by_one
+ ? (tree_int_cst_lt (up_bound, up_sub)
+ && !tree_int_cst_equal (up_bound_p1, up_sub))
+ : (tree_int_cst_lt (up_bound, up_sub)
+ || tree_int_cst_equal (up_bound_p1, up_sub))))
+ {
+ warning_at (location, OPT_Warray_bounds,
+ "array subscript is above array bounds");
TREE_NO_WARNING (ref) = 1;
}
else if (TREE_CODE (low_sub) == INTEGER_CST
&& tree_int_cst_lt (low_sub, low_bound))
{
- warning (OPT_Warray_bounds, "%Harray subscript is below array bounds",
- location);
+ warning_at (location, OPT_Warray_bounds,
+ "array subscript is below array bounds");
TREE_NO_WARNING (ref) = 1;
}
}
address of an ARRAY_REF, and call check_array_ref on it. */
static void
-search_for_addr_array(tree t, const location_t *location)
+search_for_addr_array (tree t, location_t location)
{
while (TREE_CODE (t) == SSA_NAME)
{
if (gimple_code (g) != GIMPLE_ASSIGN)
return;
- if (get_gimple_rhs_class (gimple_assign_rhs_code (g)) !=
- GIMPLE_SINGLE_RHS)
+ if (get_gimple_rhs_class (gimple_assign_rhs_code (g))
+ != GIMPLE_SINGLE_RHS)
return;
t = gimple_assign_rhs1 (g);
/* We are only interested in addresses of ARRAY_REF's. */
- if (TREE_CODE (t) != ADDR_EXPR)
+ if (TREE_CODE (t) != ADDR_EXPR)
return;
/* Check each ARRAY_REFs in the reference chain. */
- do
+ do
{
if (TREE_CODE (t) == ARRAY_REF)
- check_array_ref (t, location, true /*ignore_off_by_one*/);
+ check_array_ref (location, t, true /*ignore_off_by_one*/);
- t = TREE_OPERAND(t,0);
+ t = TREE_OPERAND (t, 0);
}
while (handled_component_p (t));
}
/* walk_tree() callback that checks if *TP is
an ARRAY_REF inside an ADDR_EXPR (in which an array
subscript one outside the valid range is allowed). Call
- check_array_ref for each ARRAY_REF found. The location is
+ check_array_ref for each ARRAY_REF found. The location is
passed in DATA. */
static tree
{
tree t = *tp;
struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
- const location_t *location = (const location_t *) wi->info;
+ location_t location;
+
+ if (EXPR_HAS_LOCATION (t))
+ location = EXPR_LOCATION (t);
+ else
+ {
+ location_t *locp = (location_t *) wi->info;
+ location = *locp;
+ }
*walk_subtree = TRUE;
if (TREE_CODE (t) == ARRAY_REF)
- check_array_ref (t, location, false /*ignore_off_by_one*/);
+ check_array_ref (location, t, false /*ignore_off_by_one*/);
if (TREE_CODE (t) == INDIRECT_REF
|| (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)))
FOR_EACH_BB (bb)
{
- /* Skip bb's that are clearly unreachable. */
- if (single_pred_p (bb))
- {
- basic_block pred_bb = EDGE_PRED (bb, 0)->src;
- gimple ls = NULL;
+ edge_iterator ei;
+ edge e;
+ bool executable = false;
- if (!gsi_end_p (gsi_last_bb (pred_bb)))
- ls = gsi_stmt (gsi_last_bb (pred_bb));
+ /* Skip blocks that were found to be unreachable. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ executable |= !!(e->flags & EDGE_EXECUTABLE);
+ if (!executable)
+ continue;
- if (ls && gimple_code (ls) == GIMPLE_COND
- && ((gimple_cond_false_p (ls)
- && (EDGE_PRED (bb, 0)->flags & EDGE_TRUE_VALUE))
- || (gimple_cond_true_p (ls)
- && (EDGE_PRED (bb, 0)->flags & EDGE_FALSE_VALUE))))
- continue;
- }
for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
{
gimple stmt = gsi_stmt (si);
- const location_t *location = gimple_location_ptr (stmt);
struct walk_stmt_info wi;
if (!gimple_has_location (stmt))
continue;
for (i = 0; i < n; i++)
{
tree arg = gimple_call_arg (stmt, i);
- search_for_addr_array (arg, location);
+ search_for_addr_array (arg, gimple_location (stmt));
}
}
else
{
memset (&wi, 0, sizeof (wi));
- wi.info = CONST_CAST (void *, (const void *) location);
+ wi.info = CONST_CAST (void *, (const void *)
+ gimple_location_ptr (stmt));
walk_gimple_op (gsi_stmt (si),
check_array_bounds,
/* Convert range assertion expressions into the implied copies and
copy propagate away the copies. Doing the trivial copy propagation
here avoids the need to run the full copy propagation pass after
- VRP.
-
+ VRP.
+
FIXME, this will eventually lead to copy propagation removing the
names that had useful range information attached to them. For
instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
then N_i will have the range [3, +INF].
-
+
However, by converting the assertion into the implied copy
operation N_i = N_j, we will then copy-propagate N_j into the uses
of N_i and lose the range information. We may want to hold on to
ASSERT_EXPRs a little while longer as the ranges could be used in
things like jump threading.
-
+
The problem with keeping ASSERT_EXPRs around is that passes after
- VRP need to handle them appropriately.
+ VRP need to handle them appropriately.
Another approach would be to make the range information a first
class property of the SSA_NAME so that it can be queried from
/* And finally, remove the copy, it is not needed. */
gsi_remove (&si, true);
- release_defs (stmt);
+ release_defs (stmt);
}
else
gsi_next (&si);
&& ((is_gimple_call (stmt)
&& gimple_call_fndecl (stmt) != NULL_TREE
&& DECL_IS_BUILTIN (gimple_call_fndecl (stmt)))
- || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)))
+ || !gimple_vuse (stmt)))
return true;
}
else if (gimple_code (stmt) == GIMPLE_COND
{
gimple stmt = gsi_stmt (si);
- if (!stmt_interesting_for_vrp (stmt))
+ /* If the statement is a control insn, then we do not
+ want to avoid simulating the statement once. Failure
+ to do so means that those edges will never get added. */
+ if (stmt_ends_bb_p (stmt))
+ prop_set_simulate_again (stmt, true);
+ else if (!stmt_interesting_for_vrp (stmt))
{
ssa_op_iter i;
tree def;
prop_set_simulate_again (stmt, false);
}
else
- {
- prop_set_simulate_again (stmt, true);
- }
+ prop_set_simulate_again (stmt, true);
}
}
}
&& TYPE_MAX_VALUE (TREE_TYPE (lhs)))
|| POINTER_TYPE_P (TREE_TYPE (lhs))))
{
- struct loop *l;
value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
if (code == GIMPLE_CALL)
else
extract_range_from_assignment (&new_vr, stmt);
- /* If STMT is inside a loop, we may be able to know something
- else about the range of LHS by examining scalar evolution
- information. */
- if (current_loops && (l = loop_containing_stmt (stmt)))
- adjust_range_with_scev (&new_vr, l, stmt, lhs);
-
if (update_value_range (lhs, &new_vr))
{
*output_p = lhs;
return SSA_PROP_NOT_INTERESTING;
}
-
+
/* Every other statement produces no useful ranges. */
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
set_value_range_to_varying (get_value_range (def));
return NULL_TREE;
}
+/* Helper function for vrp_evaluate_conditional_warnv. */
+
+static tree
+vrp_evaluate_conditional_warnv_with_ops_using_ranges (enum tree_code code,
+ tree op0, tree op1,
+ bool * strict_overflow_p)
+{
+ value_range_t *vr0, *vr1;
+
+ vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
+ vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
+
+ if (vr0 && vr1)
+ return compare_ranges (code, vr0, vr1, strict_overflow_p);
+ else if (vr0 && vr1 == NULL)
+ return compare_range_with_value (code, vr0, op1, strict_overflow_p);
+ else if (vr0 == NULL && vr1)
+ return (compare_range_with_value
+ (swap_tree_comparison (code), vr1, op0, strict_overflow_p));
+ return NULL;
+}
+
/* Helper function for vrp_evaluate_conditional_warnv. */
static tree
vrp_evaluate_conditional_warnv_with_ops (enum tree_code code, tree op0,
tree op1, bool use_equiv_p,
- bool *strict_overflow_p)
+ bool *strict_overflow_p, bool *only_ranges)
{
+ tree ret;
+ if (only_ranges)
+ *only_ranges = true;
+
/* We only deal with integral and pointer types. */
if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
&& !POINTER_TYPE_P (TREE_TYPE (op0)))
if (use_equiv_p)
{
+ if (only_ranges
+ && (ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges
+ (code, op0, op1, strict_overflow_p)))
+ return ret;
+ *only_ranges = false;
if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
return compare_names (code, op0, op1, strict_overflow_p);
else if (TREE_CODE (op0) == SSA_NAME)
(swap_tree_comparison (code), op1, op0, strict_overflow_p));
}
else
- {
- value_range_t *vr0, *vr1;
-
- vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
- vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
-
- if (vr0 && vr1)
- return compare_ranges (code, vr0, vr1, strict_overflow_p);
- else if (vr0 && vr1 == NULL)
- return compare_range_with_value (code, vr0, op1, strict_overflow_p);
- else if (vr0 == NULL && vr1)
- return (compare_range_with_value
- (swap_tree_comparison (code), vr1, op0, strict_overflow_p));
- }
+ return vrp_evaluate_conditional_warnv_with_ops_using_ranges (code, op0, op1,
+ strict_overflow_p);
return NULL_TREE;
}
based on undefined signed overflow, issue a warning if
appropriate. */
-tree
+static tree
vrp_evaluate_conditional (enum tree_code code, tree op0, tree op1, gimple stmt)
{
bool sop;
tree ret;
+ bool only_ranges;
+
+ /* Some passes and foldings leak constants with overflow flag set
+ into the IL. Avoid doing wrong things with these and bail out. */
+ if ((TREE_CODE (op0) == INTEGER_CST
+ && TREE_OVERFLOW (op0))
+ || (TREE_CODE (op1) == INTEGER_CST
+ && TREE_OVERFLOW (op1)))
+ return NULL_TREE;
sop = false;
- ret = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, true, &sop);
+ ret = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, true, &sop,
+ &only_ranges);
if (ret && sop)
{
location = input_location;
else
location = gimple_location (stmt);
- warning (OPT_Wstrict_overflow, "%H%s", &location, warnmsg);
+ warning_at (location, OPT_Wstrict_overflow, "%s", warnmsg);
}
}
if (warn_type_limits
- && ret
+ && ret && only_ranges
&& TREE_CODE_CLASS (code) == tcc_comparison
&& TREE_CODE (op0) == SSA_NAME)
{
the natural range of OP0's type, then the predicate will
always fold regardless of the value of OP0. If -Wtype-limits
was specified, emit a warning. */
- const char *warnmsg = NULL;
tree type = TREE_TYPE (op0);
value_range_t *vr0 = get_value_range (op0);
&& vrp_val_is_max (vr0->max)
&& is_gimple_min_invariant (op1))
{
- if (integer_zerop (ret))
- warnmsg = G_("comparison always false due to limited range of "
- "data type");
- else
- warnmsg = G_("comparison always true due to limited range of "
- "data type");
- }
-
- if (warnmsg)
- {
location_t location;
if (!gimple_has_location (stmt))
else
location = gimple_location (stmt);
- warning (OPT_Wtype_limits, "%H%s", &location, warnmsg);
+ warning_at (location, OPT_Wtype_limits,
+ integer_zerop (ret)
+ ? G_("comparison always false "
+ "due to limited range of data type")
+ : G_("comparison always true "
+ "due to limited range of data type"));
}
}
fprintf (dump_file, "\nVisiting conditional with predicate: ");
print_gimple_stmt (dump_file, stmt, 0, 0);
fprintf (dump_file, "\nWith known ranges\n");
-
+
FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
{
fprintf (dump_file, "\t");
/* Compute the value of the predicate COND by checking the known
ranges of each of its operands.
-
+
Note that we cannot evaluate all the equivalent ranges here
because those ranges may not yet be final and with the current
propagation strategy, we cannot determine when the value ranges
val = vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt),
gimple_cond_lhs (stmt),
gimple_cond_rhs (stmt),
- false, &sop);
+ false, &sop, NULL);
if (val)
{
if (!sop)
If there is a CASE_LABEL for VAL, its index is placed in IDX and true is
returned.
- If there is no CASE_LABEL for VAL and the is one that is larger than VAL,
+ If there is no CASE_LABEL for VAL and there is one that is larger than VAL,
it is placed in IDX and false is returned.
If VAL is larger than any CASE_LABEL, n is placed on IDX and false is
&& min_take_default
&& max_take_default)
{
- /* Only the default case label reached.
+ /* Only the default case label reached.
Return an empty range. */
*min_idx = 1;
*max_idx = 0;
{
tree op, val;
value_range_t *vr;
- size_t i = 0, j = 0, n;
+ size_t i = 0, j = 0;
bool take_default;
*taken_edge_p = NULL;
return SSA_PROP_VARYING;
/* Find the single edge that is taken from the switch expression. */
- n = gimple_switch_num_labels (stmt);
-
take_default = !find_case_label_range (stmt, vr->min, vr->max, &i, &j);
/* Check if the range spans no CASE_LABEL. If so, we only reach the default
fprintf (dump_file, "\n");
}
- if (is_gimple_assign (stmt) || is_gimple_call (stmt))
+ if (!stmt_interesting_for_vrp (stmt))
+ gcc_assert (stmt_ends_bb_p (stmt));
+ else if (is_gimple_assign (stmt) || is_gimple_call (stmt))
{
/* In general, assignments with virtual operands are not useful
for deriving ranges, with the obvious exception of calls to
if ((is_gimple_call (stmt)
&& gimple_call_fndecl (stmt) != NULL_TREE
&& DECL_IS_BUILTIN (gimple_call_fndecl (stmt)))
- || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
+ || !gimple_vuse (stmt))
return vrp_visit_assignment_or_call (stmt, output_p);
}
else if (gimple_code (stmt) == GIMPLE_COND)
value_range_t *lhs_vr = get_value_range (lhs);
value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
int edges, old_edges;
+ struct loop *l;
copy_value_range (&vr_result, lhs_vr);
}
}
+ /* If this is a loop PHI node SCEV may known more about its
+ value-range. */
+ if (current_loops
+ && (l = loop_containing_stmt (phi))
+ && l->header == gimple_bb (phi))
+ adjust_range_with_scev (&vr_result, l, phi, lhs);
+
if (vr_result.type == VR_VARYING)
goto varying;
minimums. */
if (cmp_min > 0 || cmp_min < 0)
{
- /* If we will end up with a (-INF, +INF) range, set it
- to VARYING. */
- if (vrp_val_is_max (vr_result.max))
+ /* If we will end up with a (-INF, +INF) range, set it to
+ VARYING. Same if the previous max value was invalid for
+ the type and we'd end up with vr_result.min > vr_result.max. */
+ if (vrp_val_is_max (vr_result.max)
+ || compare_values (TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)),
+ vr_result.max) > 0)
goto varying;
if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))
the previous one, go all the way to +INF. */
if (cmp_max < 0 || cmp_max > 0)
{
- /* If we will end up with a (-INF, +INF) range, set it
- to VARYING. */
- if (vrp_val_is_min (vr_result.min))
+ /* If we will end up with a (-INF, +INF) range, set it to
+ VARYING. Same if the previous min value was invalid for
+ the type and we'd end up with vr_result.max < vr_result.min. */
+ if (vrp_val_is_min (vr_result.min)
+ || compare_values (TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)),
+ vr_result.min) < 0)
goto varying;
if (!needs_overflow_infinity (TREE_TYPE (vr_result.max))
/* If the new range is different than the previous value, keep
iterating. */
if (update_value_range (lhs, &vr_result))
- return SSA_PROP_INTERESTING;
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Found new range for ");
+ print_generic_expr (dump_file, lhs, 0);
+ fprintf (dump_file, ": ");
+ dump_value_range (dump_file, &vr_result);
+ fprintf (dump_file, "\n\n");
+ }
+
+ return SSA_PROP_INTERESTING;
+ }
/* Nothing changed, don't add outgoing edges. */
return SSA_PROP_NOT_INTERESTING;
return SSA_PROP_VARYING;
}
+/* Simplify boolean operations if the source is known
+ to be already a boolean. */
+static bool
+simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
+{
+ enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
+ tree val = NULL;
+ tree op0, op1;
+ value_range_t *vr;
+ bool sop = false;
+ bool need_conversion;
+
+ op0 = gimple_assign_rhs1 (stmt);
+ if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
+ {
+ if (TREE_CODE (op0) != SSA_NAME)
+ return false;
+ vr = get_value_range (op0);
+
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+
+ if (rhs_code == TRUTH_NOT_EXPR)
+ {
+ rhs_code = NE_EXPR;
+ op1 = build_int_cst (TREE_TYPE (op0), 1);
+ }
+ else
+ {
+ op1 = gimple_assign_rhs2 (stmt);
+
+ /* Reduce number of cases to handle. */
+ if (is_gimple_min_invariant (op1))
+ {
+ /* Exclude anything that should have been already folded. */
+ if (rhs_code != EQ_EXPR
+ && rhs_code != NE_EXPR
+ && rhs_code != TRUTH_XOR_EXPR)
+ return false;
+
+ if (!integer_zerop (op1)
+ && !integer_onep (op1)
+ && !integer_all_onesp (op1))
+ return false;
+
+ /* Limit the number of cases we have to consider. */
+ if (rhs_code == EQ_EXPR)
+ {
+ rhs_code = NE_EXPR;
+ op1 = fold_unary (TRUTH_NOT_EXPR, TREE_TYPE (op1), op1);
+ }
+ }
+ else
+ {
+ /* Punt on A == B as there is no BIT_XNOR_EXPR. */
+ if (rhs_code == EQ_EXPR)
+ return false;
+
+ if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
+ {
+ vr = get_value_range (op1);
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+ }
+ }
+
+ if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
+ {
+ location_t location;
+
+ if (!gimple_has_location (stmt))
+ location = input_location;
+ else
+ location = gimple_location (stmt);
+
+ if (rhs_code == TRUTH_AND_EXPR || rhs_code == TRUTH_OR_EXPR)
+ warning_at (location, OPT_Wstrict_overflow,
+ _("assuming signed overflow does not occur when "
+ "simplifying && or || to & or |"));
+ else
+ warning_at (location, OPT_Wstrict_overflow,
+ _("assuming signed overflow does not occur when "
+ "simplifying ==, != or ! to identity or ^"));
+ }
+
+ need_conversion =
+ !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
+ TREE_TYPE (op0));
+
+ /* Make sure to not sign-extend -1 as a boolean value. */
+ if (need_conversion
+ && !TYPE_UNSIGNED (TREE_TYPE (op0))
+ && TYPE_PRECISION (TREE_TYPE (op0)) == 1)
+ return false;
+
+ switch (rhs_code)
+ {
+ case TRUTH_AND_EXPR:
+ rhs_code = BIT_AND_EXPR;
+ break;
+ case TRUTH_OR_EXPR:
+ rhs_code = BIT_IOR_EXPR;
+ break;
+ case TRUTH_XOR_EXPR:
+ case NE_EXPR:
+ if (integer_zerop (op1))
+ {
+ gimple_assign_set_rhs_with_ops (gsi,
+ need_conversion ? NOP_EXPR : SSA_NAME,
+ op0, NULL);
+ update_stmt (gsi_stmt (*gsi));
+ return true;
+ }
+
+ rhs_code = BIT_XOR_EXPR;
+ break;
+ default:
+ gcc_unreachable ();
+ }
+
+ if (need_conversion)
+ return false;
+
+ gimple_assign_set_rhs_with_ops (gsi, rhs_code, op0, op1);
+ update_stmt (gsi_stmt (*gsi));
+ return true;
+}
+
/* Simplify a division or modulo operator to a right shift or
bitwise and if the first operand is unsigned or is greater
than zero and the second operand is an exact power of two. */
-static void
+static bool
simplify_div_or_mod_using_ranges (gimple stmt)
{
enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
location = input_location;
else
location = gimple_location (stmt);
- warning (OPT_Wstrict_overflow,
- ("%Hassuming signed overflow does not occur when "
- "simplifying / or %% to >> or &"),
- &location);
+ warning_at (location, OPT_Wstrict_overflow,
+ "assuming signed overflow does not occur when "
+ "simplifying %</%> or %<%%%> to %<>>%> or %<&%>");
}
}
}
update_stmt (stmt);
+ return true;
}
+
+ return false;
}
/* If the operand to an ABS_EXPR is >= 0, then eliminate the
ABS_EXPR. If the operand is <= 0, then simplify the
ABS_EXPR into a NEGATE_EXPR. */
-static void
+static bool
simplify_abs_using_ranges (gimple stmt)
{
tree val = NULL;
location = input_location;
else
location = gimple_location (stmt);
- warning (OPT_Wstrict_overflow,
- ("%Hassuming signed overflow does not occur when "
- "simplifying abs (X) to X or -X"),
- &location);
+ warning_at (location, OPT_Wstrict_overflow,
+ "assuming signed overflow does not occur when "
+ "simplifying %<abs (X)%> to %<X%> or %<-X%>");
}
gimple_assign_set_rhs1 (stmt, op);
else
gimple_assign_set_rhs_code (stmt, SSA_NAME);
update_stmt (stmt);
+ return true;
}
}
+
+ return false;
}
/* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
value range information we have for op0. */
if (min && max)
{
- if (compare_values (vr->min, min) == -1)
- min = min;
- else
+ if (compare_values (vr->min, min) == 1)
min = vr->min;
- if (compare_values (vr->max, max) == 1)
- max = max;
- else
+ if (compare_values (vr->max, max) == -1)
max = vr->max;
/* If the new min/max values have converged to a single value,
test if the range information indicates only one value can satisfy
the original conditional. */
-static void
+static bool
simplify_cond_using_ranges (gimple stmt)
{
tree op0 = gimple_cond_lhs (stmt);
&& is_gimple_min_invariant (op1))
{
value_range_t *vr = get_value_range (op0);
-
+
/* If we have range information for OP0, then we might be
able to simplify this conditional. */
if (vr->type == VR_RANGE)
print_gimple_stmt (dump_file, stmt, 0, 0);
fprintf (dump_file, "\n");
}
- return;
+ return true;
}
/* Try again after inverting the condition. We only deal
print_gimple_stmt (dump_file, stmt, 0, 0);
fprintf (dump_file, "\n");
}
- return;
+ return true;
}
}
}
+
+ return false;
}
/* Simplify a switch statement using the value range of the switch
argument. */
-static void
+static bool
simplify_switch_using_ranges (gimple stmt)
{
tree op = gimple_switch_index (stmt);
tree vec2;
switch_update su;
- if (TREE_CODE (op) != SSA_NAME)
- return;
+ if (TREE_CODE (op) == SSA_NAME)
+ {
+ vr = get_value_range (op);
- vr = get_value_range (op);
+ /* We can only handle integer ranges. */
+ if (vr->type != VR_RANGE
+ || symbolic_range_p (vr))
+ return false;
- /* We can only handle integer ranges. */
- if (vr->type != VR_RANGE
- || symbolic_range_p (vr))
- return;
+ /* Find case label for min/max of the value range. */
+ take_default = !find_case_label_range (stmt, vr->min, vr->max, &i, &j);
+ }
+ else if (TREE_CODE (op) == INTEGER_CST)
+ {
+ take_default = !find_case_label_index (stmt, 1, op, &i);
+ if (take_default)
+ {
+ i = 1;
+ j = 0;
+ }
+ else
+ {
+ j = i;
+ }
+ }
+ else
+ return false;
- /* Find case label for min/max of the value range. */
n = gimple_switch_num_labels (stmt);
- take_default = !find_case_label_range (stmt, vr->min, vr->max, &i, &j);
/* Bail out if this is just all edges taken. */
if (i == 1
&& j == n - 1
&& take_default)
- return;
+ return false;
/* Build a new vector of taken case labels. */
vec2 = make_tree_vec (j - i + 1 + (int)take_default);
fprintf (dump_file, "removing unreachable case label\n");
}
VEC_safe_push (edge, heap, to_remove_edges, e);
+ e->flags &= ~EDGE_EXECUTABLE;
}
/* And queue an update for the stmt. */
su.stmt = stmt;
su.vec = vec2;
VEC_safe_push (switch_update, heap, to_update_switch_stmts, &su);
+ return false;
}
/* Simplify STMT using ranges if possible. */
-void
-simplify_stmt_using_ranges (gimple stmt)
+static bool
+simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
{
+ gimple stmt = gsi_stmt (*gsi);
if (is_gimple_assign (stmt))
{
enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
+ switch (rhs_code)
+ {
+ case EQ_EXPR:
+ case NE_EXPR:
+ case TRUTH_NOT_EXPR:
+ case TRUTH_AND_EXPR:
+ case TRUTH_OR_EXPR:
+ case TRUTH_XOR_EXPR:
+ /* Transform EQ_EXPR, NE_EXPR, TRUTH_NOT_EXPR into BIT_XOR_EXPR
+ or identity if the RHS is zero or one, and the LHS are known
+ to be boolean values. Transform all TRUTH_*_EXPR into
+ BIT_*_EXPR if both arguments are known to be boolean values. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
+ return simplify_truth_ops_using_ranges (gsi, stmt);
+ break;
+
/* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
and BIT_AND_EXPR respectively if the first operand is greater
than zero and the second operand is an exact power of two. */
- if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
- && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))
- && integer_pow2p (gimple_assign_rhs2 (stmt)))
- simplify_div_or_mod_using_ranges (stmt);
+ case TRUNC_DIV_EXPR:
+ case TRUNC_MOD_EXPR:
+ if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))
+ && integer_pow2p (gimple_assign_rhs2 (stmt)))
+ return simplify_div_or_mod_using_ranges (stmt);
+ break;
/* Transform ABS (X) into X or -X as appropriate. */
- if (rhs_code == ABS_EXPR
- && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
- && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
- simplify_abs_using_ranges (stmt);
+ case ABS_EXPR:
+ if (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
+ return simplify_abs_using_ranges (stmt);
+ break;
+
+ default:
+ break;
+ }
}
else if (gimple_code (stmt) == GIMPLE_COND)
- simplify_cond_using_ranges (stmt);
+ return simplify_cond_using_ranges (stmt);
else if (gimple_code (stmt) == GIMPLE_SWITCH)
- simplify_switch_using_ranges (stmt);
+ return simplify_switch_using_ranges (stmt);
+
+ return false;
+}
+
+/* If the statement pointed by SI has a predicate whose value can be
+ computed using the value range information computed by VRP, compute
+ its value and return true. Otherwise, return false. */
+
+static bool
+fold_predicate_in (gimple_stmt_iterator *si)
+{
+ bool assignment_p = false;
+ tree val;
+ gimple stmt = gsi_stmt (*si);
+
+ if (is_gimple_assign (stmt)
+ && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
+ {
+ assignment_p = true;
+ val = vrp_evaluate_conditional (gimple_assign_rhs_code (stmt),
+ gimple_assign_rhs1 (stmt),
+ gimple_assign_rhs2 (stmt),
+ stmt);
+ }
+ else if (gimple_code (stmt) == GIMPLE_COND)
+ val = vrp_evaluate_conditional (gimple_cond_code (stmt),
+ gimple_cond_lhs (stmt),
+ gimple_cond_rhs (stmt),
+ stmt);
+ else
+ return false;
+
+ if (val)
+ {
+ if (assignment_p)
+ val = fold_convert (gimple_expr_type (stmt), val);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Folding predicate ");
+ print_gimple_expr (dump_file, stmt, 0, 0);
+ fprintf (dump_file, " to ");
+ print_generic_expr (dump_file, val, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ if (is_gimple_assign (stmt))
+ gimple_assign_set_rhs_from_tree (si, val);
+ else
+ {
+ gcc_assert (gimple_code (stmt) == GIMPLE_COND);
+ if (integer_zerop (val))
+ gimple_cond_make_false (stmt);
+ else if (integer_onep (val))
+ gimple_cond_make_true (stmt);
+ else
+ gcc_unreachable ();
+ }
+
+ return true;
+ }
+
+ return false;
+}
+
+/* Callback for substitute_and_fold folding the stmt at *SI. */
+
+static bool
+vrp_fold_stmt (gimple_stmt_iterator *si)
+{
+ if (fold_predicate_in (si))
+ return true;
+
+ return simplify_stmt_using_ranges (si);
}
/* Stack of dest,src equivalency pairs that need to be restored after
- each attempt to thread a block's incoming edge to an outgoing edge.
+ each attempt to thread a block's incoming edge to an outgoing edge.
A NULL entry is used to mark the end of pairs which need to be
restored. */
Unlike DOM, we do not iterate VRP if jump threading was successful.
While iterating may expose new opportunities for VRP, it is expected
those opportunities would be very limited and the compile time cost
- to expose those opportunities would be significant.
+ to expose those opportunities would be significant.
As jump threading opportunities are discovered, they are registered
for later realization. */
}
/* We may have ended with ranges that have exactly one value. Those
- values can be substituted as any other copy/const propagated
+ values can be substituted as any other const propagated
value using substitute_and_fold. */
single_val_range = XCNEWVEC (prop_value_t, num_ssa_names);
for (i = 0; i < num_ssa_names; i++)
if (vr_value[i]
&& vr_value[i]->type == VR_RANGE
- && vr_value[i]->min == vr_value[i]->max)
+ && vr_value[i]->min == vr_value[i]->max
+ && is_gimple_min_invariant (vr_value[i]->min))
{
single_val_range[i].value = vr_value[i]->min;
do_value_subst_p = true;
single_val_range = NULL;
}
- substitute_and_fold (single_val_range, true);
+ substitute_and_fold (single_val_range, vrp_fold_stmt);
if (warn_array_bounds)
- check_all_array_refs ();
+ check_all_array_refs ();
/* We must identify jump threading opportunities before we release
the datastructures built by VRP. */
4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
5 endif
6 if (q_2)
-
+
In the code above, pointer p_5 has range [q_2, q_2], but from the
code we can also determine that p_5 cannot be NULL and, if q_2 had
a non-varying range, p_5's range should also be compatible with it.
between names so that we can take advantage of information from
multiple ranges when doing final replacement. Note that this
equivalency relation is transitive but not symmetric.
-
+
In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
cannot assert that q_2 is equivalent to p_5 because q_2 may be used
in contexts where that assertion does not hold (e.g., in line 6).
to_remove_edges = VEC_alloc (edge, heap, 10);
to_update_switch_stmts = VEC_alloc (switch_update, heap, 5);
+ threadedge_initialize_values ();
vrp_initialize ();
ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
{
size_t j;
size_t n = TREE_VEC_LENGTH (su->vec);
+ tree label;
gimple_switch_set_num_labels (su->stmt, n);
for (j = 0; j < n; j++)
gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j));
+ /* As we may have replaced the default label with a regular one
+ make sure to make it a real default label again. This ensures
+ optimal expansion. */
+ label = gimple_switch_default_label (su->stmt);
+ CASE_LOW (label) = NULL_TREE;
+ CASE_HIGH (label) = NULL_TREE;
}
if (VEC_length (edge, to_remove_edges) > 0)
VEC_free (edge, heap, to_remove_edges);
VEC_free (switch_update, heap, to_update_switch_stmts);
+ threadedge_finalize_values ();
scev_finalize ();
loop_optimizer_finalize ();
NULL, /* next */
0, /* static_pass_number */
TV_TREE_VRP, /* tv_id */
- PROP_ssa | PROP_alias, /* properties_required */
+ PROP_ssa, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
OSDN Git Service
