diff options
Diffstat (limited to 'gcc/tree-vrp.c')
-rw-r--r-- | gcc/tree-vrp.c | 553 |
1 files changed, 283 insertions, 270 deletions
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index df7a9a251ca..df19cbbfdd1 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -1398,16 +1398,14 @@ range_includes_zero_p (value_range_t *vr) static inline bool value_range_nonnegative_p (value_range_t *vr) { + /* Testing for VR_ANTI_RANGE is not useful here as any anti-range + which would return a useful value should be encoded as a + VR_RANGE. */ if (vr->type == VR_RANGE) { int result = compare_values (vr->min, integer_zero_node); return (result == 0 || result == 1); } - else if (vr->type == VR_ANTI_RANGE) - { - int result = compare_values (vr->max, integer_zero_node); - return result == -1; - } return false; } @@ -2183,6 +2181,158 @@ zero_nonzero_bits_from_vr (value_range_t *vr, 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 @@ -2195,9 +2345,16 @@ extract_range_from_binary_expr_1 (value_range_t *vr, { 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 @@ -2309,9 +2466,7 @@ extract_range_from_binary_expr_1 (value_range_t *vr, /* 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 @@ -2322,32 +2477,21 @@ extract_range_from_binary_expr_1 (value_range_t *vr, 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), @@ -2358,18 +2502,28 @@ extract_range_from_binary_expr_1 (value_range_t *vr, 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 @@ -2378,14 +2532,18 @@ extract_range_from_binary_expr_1 (value_range_t *vr, 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 @@ -2404,12 +2562,16 @@ extract_range_from_binary_expr_1 (value_range_t *vr, } } - 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] @@ -2431,12 +2593,7 @@ extract_range_from_binary_expr_1 (value_range_t *vr, /* 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))) @@ -2448,12 +2605,7 @@ extract_range_from_binary_expr_1 (value_range_t *vr, /* 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))) @@ -2461,7 +2613,6 @@ extract_range_from_binary_expr_1 (value_range_t *vr, 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) @@ -2500,96 +2651,10 @@ extract_range_from_binary_expr_1 (value_range_t *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 - 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) @@ -2735,11 +2800,6 @@ extract_range_from_binary_expr_1 (value_range_t *vr, else max = min = NULL_TREE; } - else - { - set_value_range_to_varying (vr); - return; - } } else gcc_unreachable (); @@ -2826,61 +2886,51 @@ extract_range_from_unary_expr_1 (value_range_t *vr, value_range_t *vr0_, tree op0_type) { value_range_t vr0 = *vr0_; - tree min, max; - int cmp; - /* If VR0 is UNDEFINED, so is the result. */ - if (vr0.type == VR_UNDEFINED) - { - set_value_range_to_undefined (vr); - return; - } - - /* Refuse to operate on certain unary expressions for which we - cannot easily determine a resulting range. */ - if (code == FIX_TRUNC_EXPR - || code == FLOAT_EXPR - || code == CONJ_EXPR) + /* VRP only operates on integral and pointer types. */ + if (!(INTEGRAL_TYPE_P (op0_type) + || POINTER_TYPE_P (op0_type)) + || !(INTEGRAL_TYPE_P (type) + || POINTER_TYPE_P (type))) { set_value_range_to_varying (vr); return; } - /* Refuse to operate on symbolic ranges, or if neither operand is - a pointer or integral type. */ - if ((!INTEGRAL_TYPE_P (op0_type) - && !POINTER_TYPE_P (op0_type)) - || (vr0.type != VR_VARYING - && symbolic_range_p (&vr0))) - { - set_value_range_to_varying (vr); - return; - } - - /* If the expression involves pointers, we are only interested in - determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */ - if (POINTER_TYPE_P (type) || POINTER_TYPE_P (op0_type)) + /* If VR0 is UNDEFINED, so is the result. */ + if (vr0.type == VR_UNDEFINED) { - 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); + set_value_range_to_undefined (vr); return; } - /* Handle unary expressions on integer ranges. */ - if (CONVERT_EXPR_CODE_P (code) - && INTEGRAL_TYPE_P (type) - && INTEGRAL_TYPE_P (op0_type)) + if (CONVERT_EXPR_CODE_P (code)) { tree inner_type = op0_type; tree outer_type = type; + /* If the expression evaluates to a pointer, we are only interested in + 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); + } + else + set_value_range_to_varying (vr); + return; + } + /* If VR0 is varying and we increase the type precision, assume a full range for the following transformation. */ if (vr0.type == VR_VARYING + && INTEGRAL_TYPE_P (inner_type) && TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type)) { vr0.type = VR_RANGE; @@ -2933,20 +2983,7 @@ extract_range_from_unary_expr_1 (value_range_t *vr, set_value_range_to_varying (vr); return; } - - /* Conversion of a VR_VARYING value to a wider type can result - in a usable range. So wait until after we've handled conversions - before dropping the result to VR_VARYING if we had a source - operand that is VR_VARYING. */ - if (vr0.type == VR_VARYING) - { - set_value_range_to_varying (vr); - return; - } - - /* Apply the operation to each end of the range and see what we end - up with. */ - if (code == NEGATE_EXPR) + else if (code == NEGATE_EXPR) { /* -X is simply 0 - X, so re-use existing code that also handles anti-ranges fine. */ @@ -2955,17 +2992,35 @@ extract_range_from_unary_expr_1 (value_range_t *vr, extract_range_from_binary_expr_1 (vr, MINUS_EXPR, type, &zero, &vr0); return; } - else if (code == ABS_EXPR - && !TYPE_UNSIGNED (type)) + else if (code == ABS_EXPR) { + tree min, max; + int cmp; + + /* Pass through vr0 in the easy cases. */ + if (TYPE_UNSIGNED (type) + || value_range_nonnegative_p (&vr0)) + { + copy_value_range (vr, &vr0); + return; + } + + /* For the remaining varying or symbolic ranges we can't do anything + useful. */ + if (vr0.type == VR_VARYING + || symbolic_range_p (&vr0)) + { + set_value_range_to_varying (vr); + return; + } + /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a useful range. */ if (!TYPE_OVERFLOW_UNDEFINED (type) && ((vr0.type == VR_RANGE && vrp_val_is_min (vr0.min)) || (vr0.type == VR_ANTI_RANGE - && !vrp_val_is_min (vr0.min) - && !range_includes_zero_p (&vr0)))) + && !vrp_val_is_min (vr0.min)))) { set_value_range_to_varying (vr); return; @@ -3077,6 +3132,18 @@ extract_range_from_unary_expr_1 (value_range_t *vr, max = t; } } + + 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, vr0.type, min, max, NULL); + return; } else if (code == BIT_NOT_EXPR) { @@ -3088,69 +3155,15 @@ extract_range_from_unary_expr_1 (value_range_t *vr, type, &minusone, &vr0); return; } - else + else if (code == PAREN_EXPR) { - /* Otherwise, operate on each end of the range. */ - min = fold_unary_to_constant (code, type, vr0.min); - max = fold_unary_to_constant (code, type, vr0.max); - - if (needs_overflow_infinity (type)) - { - gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR); - - /* If both sides have overflowed, we don't know - anything. */ - if ((is_overflow_infinity (vr0.min) - || TREE_OVERFLOW (min)) - && (is_overflow_infinity (vr0.max) - || TREE_OVERFLOW (max))) - { - set_value_range_to_varying (vr); - return; - } - - if (is_overflow_infinity (vr0.min)) - min = vr0.min; - else if (TREE_OVERFLOW (min)) - { - if (supports_overflow_infinity (type)) - min = (tree_int_cst_sgn (min) >= 0 - ? positive_overflow_infinity (TREE_TYPE (min)) - : negative_overflow_infinity (TREE_TYPE (min))); - else - { - set_value_range_to_varying (vr); - return; - } - } - - if (is_overflow_infinity (vr0.max)) - max = vr0.max; - else if (TREE_OVERFLOW (max)) - { - if (supports_overflow_infinity (type)) - max = (tree_int_cst_sgn (max) >= 0 - ? positive_overflow_infinity (TREE_TYPE (max)) - : negative_overflow_infinity (TREE_TYPE (max))); - else - { - set_value_range_to_varying (vr); - return; - } - } - } + copy_value_range (vr, &vr0); + 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, vr0.type, min, max, NULL); + /* For unhandled operations fall back to varying. */ + set_value_range_to_varying (vr); + return; } |