limit = avoid_overflow_infinity (limit);
- type = TREE_TYPE (limit);
+ type = TREE_TYPE (var);
gcc_assert (limit != var);
/* For pointer arithmetic, we only keep track of pointer equality
/* For LT_EXPR, we create the range [MIN, MAX - 1]. */
if (cond_code == LT_EXPR)
{
- tree one = build_int_cst (type, 1);
- max = fold_build2 (MINUS_EXPR, type, max, one);
+ if (TYPE_PRECISION (TREE_TYPE (max)) == 1
+ && !TYPE_UNSIGNED (TREE_TYPE (max)))
+ max = fold_build2 (PLUS_EXPR, TREE_TYPE (max), max,
+ build_int_cst (TREE_TYPE (max), -1));
+ else
+ max = fold_build2 (MINUS_EXPR, TREE_TYPE (max), max,
+ build_int_cst (TREE_TYPE (max), 1));
if (EXPR_P (max))
TREE_NO_WARNING (max) = 1;
}
/* For GT_EXPR, we create the range [MIN + 1, MAX]. */
if (cond_code == GT_EXPR)
{
- tree one = build_int_cst (type, 1);
- min = fold_build2 (PLUS_EXPR, type, min, one);
+ if (TYPE_PRECISION (TREE_TYPE (min)) == 1
+ && !TYPE_UNSIGNED (TREE_TYPE (min)))
+ min = fold_build2 (MINUS_EXPR, TREE_TYPE (min), min,
+ build_int_cst (TREE_TYPE (min), -1));
+ else
+ min = fold_build2 (PLUS_EXPR, TREE_TYPE (min), min,
+ build_int_cst (TREE_TYPE (min), 1));
if (EXPR_P (min))
TREE_NO_WARNING (min) = 1;
}
min = positive_overflow_infinity (TREE_TYPE (var_vr->min));
}
else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
- min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
- anti_max,
- build_int_cst (TREE_TYPE (var_vr->min), 1));
+ {
+ if (TYPE_PRECISION (TREE_TYPE (var_vr->min)) == 1
+ && !TYPE_UNSIGNED (TREE_TYPE (var_vr->min)))
+ min = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
+ anti_max,
+ build_int_cst (TREE_TYPE (var_vr->min),
+ -1));
+ else
+ min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
+ anti_max,
+ build_int_cst (TREE_TYPE (var_vr->min),
+ 1));
+ }
else
min = fold_build_pointer_plus_hwi (anti_max, 1);
max = real_max;
max = negative_overflow_infinity (TREE_TYPE (var_vr->min));
}
else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
- max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
- anti_min,
- build_int_cst (TREE_TYPE (var_vr->min), 1));
+ {
+ if (TYPE_PRECISION (TREE_TYPE (var_vr->min)) == 1
+ && !TYPE_UNSIGNED (TREE_TYPE (var_vr->min)))
+ max = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
+ anti_min,
+ build_int_cst (TREE_TYPE (var_vr->min),
+ -1));
+ else
+ max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
+ anti_min,
+ build_int_cst (TREE_TYPE (var_vr->min),
+ 1));
+ }
else
max = fold_build_pointer_plus_hwi (anti_min, -1);
min = real_min;
return true;
}
+/* Helper to extract a value-range *VR for a multiplicative operation
+ *VR0 CODE *VR1. */
+
+static void
+extract_range_from_multiplicative_op_1 (value_range_t *vr,
+ enum tree_code code,
+ value_range_t *vr0, value_range_t *vr1)
+{
+ enum value_range_type type;
+ tree val[4];
+ size_t i;
+ tree min, max;
+ bool sop;
+ int cmp;
+
+ /* Multiplications, divisions and shifts 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
+ maximum values for the new range. One approach is to figure
+ out all the variations of range combinations and do the
+ operations.
+
+ However, this involves several calls to compare_values and it
+ is pretty convoluted. It's simpler to do the 4 operations
+ (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. */
+ gcc_assert (code == MULT_EXPR
+ || code == TRUNC_DIV_EXPR
+ || code == FLOOR_DIV_EXPR
+ || code == CEIL_DIV_EXPR
+ || code == EXACT_DIV_EXPR
+ || code == ROUND_DIV_EXPR
+ || code == RSHIFT_EXPR);
+ gcc_assert ((vr0->type == VR_RANGE
+ || (code == MULT_EXPR && vr0->type == VR_ANTI_RANGE))
+ && vr0->type == vr1->type);
+
+ type = vr0->type;
+
+ /* 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;
+ }
+
+ 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;
+ }
+
+ 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;
+ }
+
+ /* 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 (val[i])
+ {
+ 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], max) == 1)
+ max = val[i];
+ }
+ }
+
+ /* If either MIN or MAX overflowed, then set the resulting range to
+ 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))
+ || max == NULL_TREE
+ || !is_gimple_min_invariant (max)
+ || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ /* We punt if:
+ 1) [-INF, +INF]
+ 2) [-INF, +-INF(OVF)]
+ 3) [+-INF(OVF), +INF]
+ 4) [+-INF(OVF), +-INF(OVF)]
+ We learn nothing when we have INF and INF(OVF) on both sides.
+ Note that we do accept [-INF, -INF] and [+INF, +INF] without
+ overflow. */
+ if ((vrp_val_is_min (min) || is_overflow_infinity (min))
+ && (vrp_val_is_max (max) || is_overflow_infinity (max)))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ cmp = compare_values (min, max);
+ if (cmp == -2 || cmp == 1)
+ {
+ /* If the new range has its limits swapped around (MIN > MAX),
+ then the operation caused one of them to wrap around, mark
+ the new range VARYING. */
+ set_value_range_to_varying (vr);
+ }
+ else
+ set_value_range (vr, type, min, max, NULL);
+}
/* Extract range information from a binary operation CODE based on
the ranges of each of its operands, *VR0 and *VR1 with resulting
{
value_range_t vr0 = *vr0_, vr1 = *vr1_;
enum value_range_type type;
- tree min, max;
+ tree min = NULL_TREE, max = NULL_TREE;
int cmp;
+ if (!INTEGRAL_TYPE_P (expr_type)
+ && !POINTER_TYPE_P (expr_type))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
/* Not all binary expressions can be applied to ranges in a
meaningful way. Handle only arithmetic operations. */
if (code != PLUS_EXPR
/* For integer ranges, apply the operation to each end of the
range and see what we end up with. */
- if (code == PLUS_EXPR
- || code == MIN_EXPR
- || code == MAX_EXPR)
+ if (code == PLUS_EXPR)
{
/* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
VR_VARYING. It would take more effort to compute a precise
this point. */
if (vr0.type == VR_ANTI_RANGE)
{
- if (code == PLUS_EXPR)
- {
- set_value_range_to_varying (vr);
- return;
- }
- /* For MIN_EXPR and MAX_EXPR with two VR_ANTI_RANGEs,
- the resulting VR_ANTI_RANGE is the same - intersection
- of the two ranges. */
- min = vrp_int_const_binop (MAX_EXPR, vr0.min, vr1.min);
- max = vrp_int_const_binop (MIN_EXPR, vr0.max, vr1.max);
- }
- else
- {
- /* For operations that make the resulting range directly
- proportional to the original ranges, apply the operation to
- 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);
+ set_value_range_to_varying (vr);
+ return;
}
+ /* For operations that make the resulting range directly
+ proportional to the original ranges, apply the operation to
+ 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))
+ if ((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_HIGH (max));
}
}
- else if (code == MULT_EXPR
- || code == TRUNC_DIV_EXPR
- || code == FLOOR_DIV_EXPR
- || code == CEIL_DIV_EXPR
- || code == EXACT_DIV_EXPR
- || code == ROUND_DIV_EXPR
- || code == RSHIFT_EXPR)
+ else if (code == MIN_EXPR
+ || code == MAX_EXPR)
+ {
+ if (vr0.type == VR_ANTI_RANGE)
+ {
+ /* For MIN_EXPR and MAX_EXPR with two VR_ANTI_RANGEs,
+ the resulting VR_ANTI_RANGE is the same - intersection
+ of the two ranges. */
+ min = vrp_int_const_binop (MAX_EXPR, vr0.min, vr1.min);
+ max = vrp_int_const_binop (MIN_EXPR, vr0.max, vr1.max);
+ }
+ else
+ {
+ /* For operations that make the resulting range directly
+ proportional to the original ranges, apply the operation to
+ 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);
+ }
+ }
+ else if (code == MULT_EXPR)
{
- tree val[4];
- size_t i;
- bool sop;
-
/* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
drop to VR_VARYING. It would take more effort to compute a
precise range for such a case. For example, if we have
we cannot claim that the product is in ~[0,0]. Note that we
are guaranteed to have vr0.type == vr1.type at this
point. */
- if (code == MULT_EXPR
- && vr0.type == VR_ANTI_RANGE
+ if (vr0.type == VR_ANTI_RANGE
&& !TYPE_OVERFLOW_UNDEFINED (expr_type))
{
set_value_range_to_varying (vr);
return;
}
+ extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
+ return;
+ }
+ else if (code == RSHIFT_EXPR)
+ {
/* If we have a RSHIFT_EXPR with any shift values outside [0..prec-1],
then drop to VR_VARYING. Outside of this range we get undefined
behavior from the shift operation. We cannot even trust
}
}
- 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)))
+ extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
+ return;
+ }
+ else if (code == TRUNC_DIV_EXPR
+ || code == FLOOR_DIV_EXPR
+ || code == CEIL_DIV_EXPR
+ || code == EXACT_DIV_EXPR
+ || code == ROUND_DIV_EXPR)
+ {
+ if (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]
/* For divisions, if flag_non_call_exceptions is true, we must
not eliminate a division by zero. */
- if ((code == TRUNC_DIV_EXPR
- || code == FLOOR_DIV_EXPR
- || code == CEIL_DIV_EXPR
- || code == EXACT_DIV_EXPR
- || code == ROUND_DIV_EXPR)
- && cfun->can_throw_non_call_exceptions
+ if (cfun->can_throw_non_call_exceptions
&& (vr1.type != VR_RANGE
|| symbolic_range_p (&vr1)
|| range_includes_zero_p (&vr1)))
/* 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
+ if (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 (TYPE_UNSIGNED (expr_type)
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
- maximum values for the new range. One approach is to figure
- out all the variations of range combinations and do the
- operations.
-
- However, this involves several calls to compare_values and it
- is pretty convoluted. It's simpler to do the 4 operations
- (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. */
else
{
- gcc_assert ((vr0.type == VR_RANGE
- || (code == MULT_EXPR && vr0.type == VR_ANTI_RANGE))
- && vr0.type == vr1.type);
-
- /* 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;
- }
-
- 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;
- }
-
- 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;
- }
-
- /* 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 (val[i])
- {
- 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], max) == 1)
- max = val[i];
- }
- }
+ extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
+ return;
}
}
else if (code == TRUNC_MOD_EXPR)
else
max = min = NULL_TREE;
}
- else
- {
- set_value_range_to_varying (vr);
- return;
- }
}
else
gcc_unreachable ();
determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
if (POINTER_TYPE_P (type))
{
- if (CONVERT_EXPR_CODE_P (code))
- {
- if (range_is_nonnull (&vr0))
- set_value_range_to_nonnull (vr, type);
- else if (range_is_null (&vr0))
- set_value_range_to_null (vr, type);
- else
- set_value_range_to_varying (vr);
- }
+ if (range_is_nonnull (&vr0))
+ set_value_range_to_nonnull (vr, type);
+ else if (range_is_null (&vr0))
+ set_value_range_to_null (vr, type);
else
set_value_range_to_varying (vr);
return;
}
-/* Extract range information from a conditional expression EXPR based on
+/* Extract range information from a conditional expression STMT based on
the ranges of each of its operands and the expression code. */
static void
-extract_range_from_cond_expr (value_range_t *vr, tree expr)
+extract_range_from_cond_expr (value_range_t *vr, gimple stmt)
{
tree op0, op1;
value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
/* Get value ranges for each operand. For constant operands, create
a new value range with the operand to simplify processing. */
- op0 = COND_EXPR_THEN (expr);
+ op0 = gimple_assign_rhs2 (stmt);
if (TREE_CODE (op0) == SSA_NAME)
vr0 = *(get_value_range (op0));
else if (is_gimple_min_invariant (op0))
else
set_value_range_to_varying (&vr0);
- op1 = COND_EXPR_ELSE (expr);
+ op1 = gimple_assign_rhs3 (stmt);
if (TREE_CODE (op1) == SSA_NAME)
vr1 = *(get_value_range (op1));
else if (is_gimple_min_invariant (op1))
gimple_expr_type (stmt),
gimple_assign_rhs1 (stmt));
else if (code == COND_EXPR)
- extract_range_from_cond_expr (vr, gimple_assign_rhs1 (stmt));
+ extract_range_from_cond_expr (vr, stmt);
else if (TREE_CODE_CLASS (code) == tcc_comparison)
extract_range_from_comparison (vr, gimple_assign_rhs_code (stmt),
gimple_expr_type (stmt),
tree innerop, middleop, finaltype;
gimple def_stmt;
value_range_t *innervr;
- double_int innermin, innermax, middlemin, middlemax;
+ bool inner_unsigned_p, middle_unsigned_p, final_unsigned_p;
+ unsigned inner_prec, middle_prec, final_prec;
+ double_int innermin, innermed, innermax, middlemin, middlemed, middlemax;
finaltype = TREE_TYPE (gimple_assign_lhs (stmt));
if (!INTEGRAL_TYPE_P (finaltype))
the middle conversion is removed. */
innermin = tree_to_double_int (innervr->min);
innermax = tree_to_double_int (innervr->max);
- middlemin = double_int_ext (innermin, TYPE_PRECISION (TREE_TYPE (middleop)),
- TYPE_UNSIGNED (TREE_TYPE (middleop)));
- middlemax = double_int_ext (innermax, TYPE_PRECISION (TREE_TYPE (middleop)),
- TYPE_UNSIGNED (TREE_TYPE (middleop)));
- /* If the middle values do not represent a proper range fail. */
- if (double_int_cmp (middlemin, middlemax,
- TYPE_UNSIGNED (TREE_TYPE (middleop))) > 0)
+
+ inner_prec = TYPE_PRECISION (TREE_TYPE (innerop));
+ middle_prec = TYPE_PRECISION (TREE_TYPE (middleop));
+ final_prec = TYPE_PRECISION (finaltype);
+
+ /* If the first conversion is not injective, the second must not
+ be widening. */
+ if (double_int_cmp (double_int_sub (innermax, innermin),
+ double_int_mask (middle_prec), true) > 0
+ && middle_prec < final_prec)
return false;
+ /* We also want a medium value so that we can track the effect that
+ narrowing conversions with sign change have. */
+ inner_unsigned_p = TYPE_UNSIGNED (TREE_TYPE (innerop));
+ if (inner_unsigned_p)
+ innermed = double_int_rshift (double_int_mask (inner_prec),
+ 1, inner_prec, false);
+ else
+ innermed = double_int_zero;
+ if (double_int_cmp (innermin, innermed, inner_unsigned_p) >= 0
+ || double_int_cmp (innermed, innermax, inner_unsigned_p) >= 0)
+ innermed = innermin;
+
+ middle_unsigned_p = TYPE_UNSIGNED (TREE_TYPE (middleop));
+ middlemin = double_int_ext (innermin, middle_prec, middle_unsigned_p);
+ middlemed = double_int_ext (innermed, middle_prec, middle_unsigned_p);
+ middlemax = double_int_ext (innermax, middle_prec, middle_unsigned_p);
+
+ /* Require that the final conversion applied to both the original
+ and the intermediate range produces the same result. */
+ final_unsigned_p = TYPE_UNSIGNED (finaltype);
if (!double_int_equal_p (double_int_ext (middlemin,
- TYPE_PRECISION (finaltype),
- TYPE_UNSIGNED (finaltype)),
+ final_prec, final_unsigned_p),
double_int_ext (innermin,
- TYPE_PRECISION (finaltype),
- TYPE_UNSIGNED (finaltype)))
+ final_prec, final_unsigned_p))
+ || !double_int_equal_p (double_int_ext (middlemed,
+ final_prec, final_unsigned_p),
+ double_int_ext (innermed,
+ final_prec, final_unsigned_p))
|| !double_int_equal_p (double_int_ext (middlemax,
- TYPE_PRECISION (finaltype),
- TYPE_UNSIGNED (finaltype)),
+ final_prec, final_unsigned_p),
double_int_ext (innermax,
- TYPE_PRECISION (finaltype),
- TYPE_UNSIGNED (finaltype))))
+ final_prec, final_unsigned_p)))
return false;
gimple_assign_set_rhs1 (stmt, innerop);
OSDN Git Service
