X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-vrp.c;h=5f9a3279aa3cb5df783a59c31ca747277736e273;hb=4e8c3ff8cad2efc5849b04d4a3f62187b77e2874;hp=d3fd911dbb1b6549a9270f5dc03ceab563aa04e8;hpb=659753d37a080ae530f05e08bcc549795a5386a2;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index d3fd911dbb1..5f9a3279aa3 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -6,7 +6,7 @@ This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) +the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, @@ -15,9 +15,8 @@ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to -the Free Software Foundation, 51 Franklin Street, Fifth Floor, -Boston, MA 02110-1301, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -95,6 +94,11 @@ static sbitmap blocks_visited; of values that SSA name N_I may take. */ static value_range_t **vr_value; +/* For a PHI node which sets SSA name N_I, VR_COUNTS[I] holds the + number of executable edges we saw the last time we visited the + node. */ +static int *vr_phi_edge_counts; + /* Return whether TYPE should use an overflow infinity distinct from TYPE_{MIN,MAX}_VALUE. We use an overflow infinity value to @@ -103,7 +107,7 @@ static value_range_t **vr_value; TYPE_{MIN,MAX}_VALUE. */ static inline bool -needs_overflow_infinity (tree type) +needs_overflow_infinity (const_tree type) { return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type); } @@ -115,7 +119,7 @@ needs_overflow_infinity (tree type) VARYING. */ static inline bool -supports_overflow_infinity (tree type) +supports_overflow_infinity (const_tree type) { #ifdef ENABLE_CHECKING gcc_assert (needs_overflow_infinity (type)); @@ -165,7 +169,7 @@ positive_overflow_infinity (tree type) /* Return whether VAL is a negative overflow infinity. */ static inline bool -is_negative_overflow_infinity (tree val) +is_negative_overflow_infinity (const_tree val) { return (needs_overflow_infinity (TREE_TYPE (val)) && CONSTANT_CLASS_P (val) @@ -176,7 +180,7 @@ is_negative_overflow_infinity (tree val) /* Return whether VAL is a positive overflow infinity. */ static inline bool -is_positive_overflow_infinity (tree val) +is_positive_overflow_infinity (const_tree val) { return (needs_overflow_infinity (TREE_TYPE (val)) && CONSTANT_CLASS_P (val) @@ -187,7 +191,7 @@ is_positive_overflow_infinity (tree val) /* Return whether VAL is a positive or negative overflow infinity. */ static inline bool -is_overflow_infinity (tree val) +is_overflow_infinity (const_tree val) { return (needs_overflow_infinity (TREE_TYPE (val)) && CONSTANT_CLASS_P (val) @@ -196,12 +200,63 @@ is_overflow_infinity (tree val) || operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0))); } +/* If VAL is now an overflow infinity, return VAL. Otherwise, return + the same value with TREE_OVERFLOW clear. This can be used to avoid + confusing a regular value with an overflow value. */ + +static inline tree +avoid_overflow_infinity (tree val) +{ + if (!is_overflow_infinity (val)) + return val; + + if (operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0)) + return TYPE_MAX_VALUE (TREE_TYPE (val)); + else + { +#ifdef ENABLE_CHECKING + gcc_assert (operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0)); +#endif + return TYPE_MIN_VALUE (TREE_TYPE (val)); + } +} + + +/* Return whether VAL is equal to the maximum value of its type. This + will be true for a positive overflow infinity. We can't do a + simple equality comparison with TYPE_MAX_VALUE because C typedefs + and Ada subtypes can produce types whose TYPE_MAX_VALUE is not == + to the integer constant with the same value in the type. */ + +static inline bool +vrp_val_is_max (const_tree val) +{ + tree type_max = TYPE_MAX_VALUE (TREE_TYPE (val)); + + return (val == type_max + || (type_max != NULL_TREE + && operand_equal_p (val, type_max, 0))); +} + +/* Return whether VAL is equal to the minimum value of its type. This + will be true for a negative overflow infinity. */ + +static inline bool +vrp_val_is_min (const_tree val) +{ + tree type_min = TYPE_MIN_VALUE (TREE_TYPE (val)); + + return (val == type_min + || (type_min != NULL_TREE + && operand_equal_p (val, type_min, 0))); +} + /* Return true if ARG is marked with the nonnull attribute in the current function signature. */ static bool -nonnull_arg_p (tree arg) +nonnull_arg_p (const_tree arg) { tree t, attrs, fntype; unsigned HOST_WIDE_INT arg_num; @@ -260,13 +315,14 @@ set_value_range (value_range_t *vr, enum value_range_type t, tree min, gcc_assert (min && max); if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE) - gcc_assert ((min != TYPE_MIN_VALUE (TREE_TYPE (min)) - && !is_negative_overflow_infinity (min)) - || (max != TYPE_MAX_VALUE (TREE_TYPE (max)) - && !is_positive_overflow_infinity (max))); + gcc_assert (!vrp_val_is_min (min) || !vrp_val_is_max (max)); cmp = compare_values (min, max); gcc_assert (cmp == 0 || cmp == -1 || cmp == -2); + + if (needs_overflow_infinity (TREE_TYPE (min))) + gcc_assert (!is_overflow_infinity (min) + || !is_overflow_infinity (max)); } if (t == VR_UNDEFINED || t == VR_VARYING) @@ -282,7 +338,8 @@ set_value_range (value_range_t *vr, enum value_range_type t, tree min, /* Since updating the equivalence set involves deep copying the bitmaps, only do it if absolutely necessary. */ - if (vr->equiv == NULL) + if (vr->equiv == NULL + && equiv != NULL) vr->equiv = BITMAP_ALLOC (NULL); if (equiv != vr->equiv) @@ -315,8 +372,21 @@ set_value_range_to_varying (value_range_t *vr) bitmap_clear (vr->equiv); } +/* Set value range VR to a single value. This function is only called + with values we get from statements, and exists to clear the + TREE_OVERFLOW flag so that we don't think we have an overflow + infinity when we shouldn't. */ + +static inline void +set_value_range_to_value (value_range_t *vr, tree val, bitmap equiv) +{ + gcc_assert (is_gimple_min_invariant (val)); + val = avoid_overflow_infinity (val); + set_value_range (vr, VR_RANGE, val, val, equiv); +} + /* Set value range VR to a non-negative range of type TYPE. - OVERFLOW_INFINITY indicates whether to use a overflow infinity + OVERFLOW_INFINITY indicates whether to use an overflow infinity rather than TYPE_MAX_VALUE; this should be true if we determine that the range is nonnegative based on the assumption that signed overflow does not occur. */ @@ -356,8 +426,7 @@ set_value_range_to_nonnull (value_range_t *vr, tree type) static inline void set_value_range_to_null (value_range_t *vr, tree type) { - tree zero = build_int_cst (type, 0); - set_value_range (vr, VR_RANGE, zero, zero, vr->equiv); + set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv); } @@ -393,7 +462,7 @@ set_value_range_to_undefined (value_range_t *vr) return NULL. Otherwise create an empty range if none existed for VAR. */ static value_range_t * -get_value_range (tree var) +get_value_range (const_tree var) { value_range_t *vr; tree sym; @@ -410,8 +479,8 @@ get_value_range (tree var) /* Create a default value range. */ vr_value[ver] = vr = XCNEW (value_range_t); - /* Allocate an equivalence set. */ - vr->equiv = BITMAP_ALLOC (NULL); + /* Defer allocating the equivalence set. */ + vr->equiv = NULL; /* If VAR is a default definition, the variable can take any value in VAR's type. */ @@ -435,7 +504,7 @@ get_value_range (tree var) /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ static inline bool -vrp_operand_equal_p (tree val1, tree val2) +vrp_operand_equal_p (const_tree val1, const_tree val2) { if (val1 == val2) return true; @@ -449,7 +518,7 @@ vrp_operand_equal_p (tree val1, tree val2) /* Return true, if the bitmaps B1 and B2 are equal. */ static inline bool -vrp_bitmap_equal_p (bitmap b1, bitmap b2) +vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2) { return (b1 == b2 || (b1 && b2 @@ -467,7 +536,7 @@ vrp_bitmap_equal_p (bitmap b1, bitmap b2) is the range object associated with another SSA name. */ static inline bool -update_value_range (tree var, value_range_t *new_vr) +update_value_range (const_tree var, value_range_t *new_vr) { value_range_t *old_vr; bool is_new; @@ -484,23 +553,25 @@ update_value_range (tree var, value_range_t *new_vr) new_vr->equiv); BITMAP_FREE (new_vr->equiv); - new_vr->equiv = NULL; return is_new; } -/* Add VAR and VAR's equivalence set to EQUIV. */ +/* Add VAR and VAR's equivalence set to EQUIV. This is the central + point where equivalence processing can be turned on/off. */ static void -add_equivalence (bitmap equiv, tree var) +add_equivalence (bitmap *equiv, const_tree var) { unsigned ver = SSA_NAME_VERSION (var); value_range_t *vr = vr_value[ver]; - bitmap_set_bit (equiv, ver); + if (*equiv == NULL) + *equiv = BITMAP_ALLOC (NULL); + bitmap_set_bit (*equiv, ver); if (vr && vr->equiv) - bitmap_ior_into (equiv, vr->equiv); + bitmap_ior_into (*equiv, vr->equiv); } @@ -535,7 +606,7 @@ symbolic_range_p (value_range_t *vr) || !is_gimple_min_invariant (vr->max)); } -/* Return true if value range VR uses a overflow infinity. */ +/* Return true if value range VR uses an overflow infinity. */ static inline bool overflow_infinity_range_p (value_range_t *vr) @@ -647,7 +718,12 @@ operand_less_p (tree val, tree val2) { tree tcmp; + fold_defer_overflow_warnings (); + tcmp = fold_binary_to_constant (LT_EXPR, boolean_type_node, val, val2); + + fold_undefer_and_ignore_overflow_warnings (); + if (!tcmp) return -2; @@ -689,6 +765,10 @@ compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p) both integers. */ gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1)) == POINTER_TYPE_P (TREE_TYPE (val2))); + /* Convert the two values into the same type. This is needed because + sizetype causes sign extension even for unsigned types. */ + val2 = fold_convert (TREE_TYPE (val1), val2); + STRIP_USELESS_TYPE_CONVERSION (val2); if ((TREE_CODE (val1) == SSA_NAME || TREE_CODE (val1) == PLUS_EXPR @@ -760,7 +840,9 @@ compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p) if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1))) return -2; - if (strict_overflow_p != NULL) + if (strict_overflow_p != NULL + && (code1 == SSA_NAME || !TREE_NO_WARNING (val1)) + && (code2 == SSA_NAME || !TREE_NO_WARNING (val2))) *strict_overflow_p = true; if (code1 == SSA_NAME) @@ -962,7 +1044,7 @@ range_includes_zero_p (value_range_t *vr) false otherwise or if no value range information is available. */ bool -ssa_name_nonnegative_p (tree t) +ssa_name_nonnegative_p (const_tree t) { value_range_t *vr = get_value_range (t); @@ -984,7 +1066,7 @@ ssa_name_nonnegative_p (tree t) false otherwise or if no value range information is available. */ bool -ssa_name_nonzero_p (tree t) +ssa_name_nonzero_p (const_tree t) { value_range_t *vr = get_value_range (t); @@ -1035,6 +1117,8 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) cond_code = swap_tree_comparison (TREE_CODE (cond)); } + limit = avoid_overflow_infinity (limit); + type = TREE_TYPE (limit); gcc_assert (limit != var); @@ -1064,8 +1148,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) predicates, we will need to trim the set of equivalences before we are done. */ gcc_assert (vr_p->equiv == NULL); - vr_p->equiv = BITMAP_ALLOC (NULL); - add_equivalence (vr_p->equiv, var); + add_equivalence (&vr_p->equiv, var); /* Extract a new range based on the asserted comparison for VAR and LIMIT's value range. Notice that if LIMIT has an anti-range, we @@ -1099,7 +1182,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) SSA name, the new range will also inherit the equivalence set from LIMIT. */ if (TREE_CODE (limit) == SSA_NAME) - add_equivalence (vr_p->equiv, limit); + add_equivalence (&vr_p->equiv, limit); } else if (cond_code == NE_EXPR) { @@ -1140,10 +1223,8 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) /* If MIN and MAX cover the whole range for their type, then just use the original LIMIT. */ if (INTEGRAL_TYPE_P (type) - && (min == TYPE_MIN_VALUE (type) - || is_negative_overflow_infinity (min)) - && (max == TYPE_MAX_VALUE (type) - || is_positive_overflow_infinity (max))) + && vrp_val_is_min (min) + && vrp_val_is_max (max)) min = max = limit; set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv); @@ -1176,6 +1257,8 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) { tree one = build_int_cst (type, 1); max = fold_build2 (MINUS_EXPR, type, max, one); + if (EXPR_P (max)) + TREE_NO_WARNING (max) = 1; } set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); @@ -1209,6 +1292,8 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) { tree one = build_int_cst (type, 1); min = fold_build2 (PLUS_EXPR, type, min, one); + if (EXPR_P (min)) + TREE_NO_WARNING (min) = 1; } set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); @@ -1378,7 +1463,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) { gcc_assert (!is_positive_overflow_infinity (anti_max)); if (needs_overflow_infinity (TREE_TYPE (anti_max)) - && anti_max == TYPE_MAX_VALUE (TREE_TYPE (anti_max))) + && vrp_val_is_max (anti_max)) { if (!supports_overflow_infinity (TREE_TYPE (var_vr->min))) { @@ -1387,10 +1472,13 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) } min = positive_overflow_infinity (TREE_TYPE (var_vr->min)); } - else + 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)); + else + min = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min), + anti_max, size_int (1)); max = real_max; set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); } @@ -1403,7 +1491,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) { gcc_assert (!is_negative_overflow_infinity (anti_min)); if (needs_overflow_infinity (TREE_TYPE (anti_min)) - && anti_min == TYPE_MIN_VALUE (TREE_TYPE (anti_min))) + && vrp_val_is_min (anti_min)) { if (!supports_overflow_infinity (TREE_TYPE (var_vr->min))) { @@ -1412,10 +1500,14 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) } max = negative_overflow_infinity (TREE_TYPE (var_vr->min)); } - else + 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)); + else + max = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min), + anti_min, + size_int (-1)); min = real_min; set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); } @@ -1447,7 +1539,7 @@ extract_range_from_ssa_name (value_range_t *vr, tree var) else set_value_range (vr, VR_RANGE, var, var, NULL); - add_equivalence (vr->equiv, var); + add_equivalence (&vr->equiv, var); } @@ -1569,6 +1661,12 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2) && (sgn1 >= 0 ? !is_positive_overflow_infinity (val2) : is_negative_overflow_infinity (val2))) + /* We only get in here with positive shift count, so the + overflow direction is the same as the sign of val1. + Actually rshift does not overflow at all, but we only + handle the case of shifting overflowed -INF and +INF. */ + || (code == RSHIFT_EXPR + && sgn1 >= 0) /* For division, the only case is -INF / -1 = +INF. */ || code == TRUNC_DIV_EXPR || code == FLOOR_DIV_EXPR @@ -1605,6 +1703,7 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr) meaningful way. Handle only arithmetic operations. */ if (code != PLUS_EXPR && code != MINUS_EXPR + && code != POINTER_PLUS_EXPR && code != MULT_EXPR && code != TRUNC_DIV_EXPR && code != FLOOR_DIV_EXPR @@ -1630,7 +1729,7 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr) if (TREE_CODE (op0) == SSA_NAME) vr0 = *(get_value_range (op0)); else if (is_gimple_min_invariant (op0)) - set_value_range (&vr0, VR_RANGE, op0, op0, NULL); + set_value_range_to_value (&vr0, op0, NULL); else set_value_range_to_varying (&vr0); @@ -1638,7 +1737,7 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr) if (TREE_CODE (op1) == SSA_NAME) vr1 = *(get_value_range (op1)); else if (is_gimple_min_invariant (op1)) - set_value_range (&vr1, VR_RANGE, op1, op1, NULL); + set_value_range_to_value (&vr1, op1, NULL); else set_value_range_to_varying (&vr1); @@ -1675,26 +1774,30 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr) || POINTER_TYPE_P (TREE_TYPE (op0)) || POINTER_TYPE_P (TREE_TYPE (op1))) { - /* For pointer types, we are really only interested in asserting - whether the expression evaluates to non-NULL. FIXME, we used - to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but - ivopts is generating expressions with pointer multiplication - in them. */ - if (code == PLUS_EXPR) + if (code == MIN_EXPR || code == MAX_EXPR) { - if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1)) + /* For MIN/MAX expressions with pointers, we only care about + nullness, if both are non null, then the result is nonnull. + If both are null, then the result is null. Otherwise they + are varying. */ + if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1)) set_value_range_to_nonnull (vr, TREE_TYPE (expr)); else if (range_is_null (&vr0) && range_is_null (&vr1)) set_value_range_to_null (vr, TREE_TYPE (expr)); else set_value_range_to_varying (vr); + + return; } + gcc_assert (code == POINTER_PLUS_EXPR); + /* For pointer types, we are really only interested in asserting + whether the expression evaluates to non-NULL. */ + if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1)) + set_value_range_to_nonnull (vr, TREE_TYPE (expr)); + else if (range_is_null (&vr0) && range_is_null (&vr1)) + set_value_range_to_null (vr, TREE_TYPE (expr)); else - { - /* Subtracting from a pointer, may yield 0, so just drop the - resulting range to varying. */ - set_value_range_to_varying (vr); - } + set_value_range_to_varying (vr); return; } @@ -1802,6 +1905,25 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr) return; } + /* 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 + SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl + shifts, and the operation at the tree level may be widened. */ + if (code == RSHIFT_EXPR) + { + if (vr1.type == VR_ANTI_RANGE + || !vrp_expr_computes_nonnegative (op1, &sop) + || (operand_less_p + (build_int_cst (TREE_TYPE (vr1.max), + TYPE_PRECISION (TREE_TYPE (expr)) - 1), + vr1.max) != 0)) + { + 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 @@ -1816,8 +1938,8 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr) the new range. */ /* Divisions by zero result in a VARYING value. */ - if (code != MULT_EXPR - && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1))) + else if (code != MULT_EXPR + && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1))) { set_value_range_to_varying (vr); return; @@ -1959,10 +2081,16 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr) return; } - if ((min == TYPE_MIN_VALUE (TREE_TYPE (min)) - || is_negative_overflow_infinity (min)) - && (max == TYPE_MAX_VALUE (TREE_TYPE (max)) - || is_positive_overflow_infinity (max))) + /* 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; @@ -2010,7 +2138,7 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) if (TREE_CODE (op0) == SSA_NAME) vr0 = *(get_value_range (op0)); else if (is_gimple_min_invariant (op0)) - set_value_range (&vr0, VR_RANGE, op0, op0, NULL); + set_value_range_to_value (&vr0, op0, NULL); else set_value_range_to_varying (&vr0); @@ -2095,6 +2223,8 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) && is_gimple_val (new_max) && tree_int_cst_equal (new_min, orig_min) && tree_int_cst_equal (new_max, orig_max) + && (!is_overflow_infinity (new_min) + || !is_overflow_infinity (new_max)) && (cmp = compare_values (new_min, new_max)) <= 0 && cmp >= -1) { @@ -2138,11 +2268,13 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) min = negative_overflow_infinity (TREE_TYPE (expr)); else if (is_negative_overflow_infinity (vr0.max)) min = positive_overflow_infinity (TREE_TYPE (expr)); - else if (vr0.max != TYPE_MIN_VALUE (TREE_TYPE (expr))) + else if (!vrp_val_is_min (vr0.max)) min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); else if (needs_overflow_infinity (TREE_TYPE (expr))) { - if (supports_overflow_infinity (TREE_TYPE (expr))) + if (supports_overflow_infinity (TREE_TYPE (expr)) + && !is_overflow_infinity (vr0.min) + && !vrp_val_is_min (vr0.min)) min = positive_overflow_infinity (TREE_TYPE (expr)); else { @@ -2157,7 +2289,7 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) max = negative_overflow_infinity (TREE_TYPE (expr)); else if (is_negative_overflow_infinity (vr0.min)) max = positive_overflow_infinity (TREE_TYPE (expr)); - else if (vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr))) + else if (!vrp_val_is_min (vr0.min)) max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); else if (needs_overflow_infinity (TREE_TYPE (expr))) { @@ -2196,9 +2328,9 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) useful range. */ if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (expr)) && ((vr0.type == VR_RANGE - && vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr))) + && vrp_val_is_min (vr0.min)) || (vr0.type == VR_ANTI_RANGE - && vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr)) + && !vrp_val_is_min (vr0.min) && !range_includes_zero_p (&vr0)))) { set_value_range_to_varying (vr); @@ -2209,7 +2341,7 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) included negative values. */ if (is_overflow_infinity (vr0.min)) min = positive_overflow_infinity (TREE_TYPE (expr)); - else if (vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr))) + else if (!vrp_val_is_min (vr0.min)) min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); else if (!needs_overflow_infinity (TREE_TYPE (expr))) min = TYPE_MAX_VALUE (TREE_TYPE (expr)); @@ -2223,7 +2355,7 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) if (is_overflow_infinity (vr0.max)) max = positive_overflow_infinity (TREE_TYPE (expr)); - else if (vr0.max != TYPE_MIN_VALUE (TREE_TYPE (expr))) + else if (!vrp_val_is_min (vr0.max)) max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); else if (!needs_overflow_infinity (TREE_TYPE (expr))) max = TYPE_MAX_VALUE (TREE_TYPE (expr)); @@ -2318,6 +2450,18 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) if (needs_overflow_infinity (TREE_TYPE (expr))) { 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)) @@ -2379,7 +2523,7 @@ extract_range_from_cond_expr (value_range_t *vr, tree expr) if (TREE_CODE (op0) == SSA_NAME) vr0 = *(get_value_range (op0)); else if (is_gimple_min_invariant (op0)) - set_value_range (&vr0, VR_RANGE, op0, op0, NULL); + set_value_range_to_value (&vr0, op0, NULL); else set_value_range_to_varying (&vr0); @@ -2387,7 +2531,7 @@ extract_range_from_cond_expr (value_range_t *vr, tree expr) if (TREE_CODE (op1) == SSA_NAME) vr1 = *(get_value_range (op1)); else if (is_gimple_min_invariant (op1)) - set_value_range (&vr1, VR_RANGE, op1, op1, NULL); + set_value_range_to_value (&vr1, op1, NULL); else set_value_range_to_varying (&vr1); @@ -2417,7 +2561,10 @@ extract_range_from_comparison (value_range_t *vr, tree expr) its type may be different from _Bool. Convert VAL to EXPR's type. */ val = fold_convert (TREE_TYPE (expr), val); - set_value_range (vr, VR_RANGE, val, val, vr->equiv); + if (is_gimple_min_invariant (val)) + set_value_range_to_value (vr, val, vr->equiv); + else + set_value_range (vr, VR_RANGE, val, val, vr->equiv); } else /* The result of a comparison is always true or false. */ @@ -2451,7 +2598,7 @@ extract_range_from_expr (value_range_t *vr, tree expr) else if (TREE_CODE_CLASS (code) == tcc_comparison) extract_range_from_comparison (vr, expr); else if (is_gimple_min_invariant (expr)) - set_value_range (vr, VR_RANGE, expr, expr, NULL); + set_value_range_to_value (vr, expr, NULL); else set_value_range_to_varying (vr); @@ -2489,7 +2636,22 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt, if (vr->type == VR_ANTI_RANGE) return; + /* Ensure that there are not values in the scev cache based on assumptions + on ranges of ssa names that were changed + (in set_value_range/set_value_range_to_varying). Preserve cached numbers + of iterations, that were computed before the start of VRP (we do not + recompute these each time to save the compile time). */ + scev_reset_except_niters (); + chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var)); + + /* Like in PR19590, scev can return a constant function. */ + if (is_gimple_min_invariant (chrec)) + { + set_value_range_to_value (vr, chrec, vr->equiv); + return; + } + if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) return; @@ -2571,6 +2733,13 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt, if (compare_values (min, max) == 1) return; } + + /* According to the loop information, the variable does not + overflow. If we think it does, probably because of an + overflow due to arithmetic on a different INF value, + reset now. */ + if (is_negative_overflow_infinity (min)) + min = tmin; } else { @@ -2583,12 +2752,60 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt, if (compare_values (min, max) == 1) return; } + + if (is_positive_overflow_infinity (max)) + max = tmax; } set_value_range (vr, VR_RANGE, min, max, vr->equiv); } } +/* Return true if VAR may overflow at STMT. This checks any available + loop information to see if we can determine that VAR does not + overflow. */ + +static bool +vrp_var_may_overflow (tree var, tree stmt) +{ + struct loop *l; + tree chrec, init, step; + + if (current_loops == NULL) + return true; + + l = loop_containing_stmt (stmt); + if (l == NULL) + return true; + + chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var)); + if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) + return true; + + init = initial_condition_in_loop_num (chrec, l->num); + step = evolution_part_in_loop_num (chrec, l->num); + + if (step == NULL_TREE + || !is_gimple_min_invariant (step) + || !valid_value_p (init)) + return true; + + /* If we get here, we know something useful about VAR based on the + loop information. If it wraps, it may overflow. */ + + if (scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec), + true)) + return true; + + if (dump_file && (dump_flags & TDF_DETAILS) != 0) + { + print_generic_expr (dump_file, var, 0); + fprintf (dump_file, ": loop information indicates does not overflow\n"); + } + + return false; +} + /* Given two numeric value ranges VR0, VR1 and a comparison code COMP: @@ -2907,24 +3124,22 @@ dump_value_range (FILE *file, value_range_t *vr) fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : ""); - if (INTEGRAL_TYPE_P (type) - && !TYPE_UNSIGNED (type) - && vr->min == TYPE_MIN_VALUE (type)) - fprintf (file, "-INF"); - else if (needs_overflow_infinity (type) - && is_negative_overflow_infinity (vr->min)) + if (is_negative_overflow_infinity (vr->min)) fprintf (file, "-INF(OVF)"); + else if (INTEGRAL_TYPE_P (type) + && !TYPE_UNSIGNED (type) + && vrp_val_is_min (vr->min)) + fprintf (file, "-INF"); else print_generic_expr (file, vr->min, 0); fprintf (file, ", "); - if (INTEGRAL_TYPE_P (type) - && vr->max == TYPE_MAX_VALUE (type)) - fprintf (file, "+INF"); - else if (needs_overflow_infinity (type) - && is_positive_overflow_infinity (vr->max)) + if (is_positive_overflow_infinity (vr->max)) fprintf (file, "+INF(OVF)"); + else if (INTEGRAL_TYPE_P (type) + && vrp_val_is_max (vr->max)) + fprintf (file, "+INF"); else print_generic_expr (file, vr->max, 0); @@ -3044,7 +3259,7 @@ build_assert_expr_for (tree cond, tree v) point values. */ static inline bool -fp_predicate (tree expr) +fp_predicate (const_tree expr) { return (COMPARISON_CLASS_P (expr) && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)))); @@ -3083,11 +3298,10 @@ infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p) non-NULL if -fdelete-null-pointer-checks is enabled. */ if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op))) { - bool is_store; - unsigned num_uses, num_derefs; + unsigned num_uses, num_loads, num_stores; - count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store); - if (num_derefs > 0) + count_uses_and_derefs (op, stmt, &num_uses, &num_loads, &num_stores); + if (num_loads + num_stores > 0) { *val_p = build_int_cst (TREE_TYPE (op), 0); *comp_code_p = NE_EXPR; @@ -3467,7 +3681,6 @@ register_edge_assert_for_1 (tree op, enum tree_code code, } else if (TREE_CODE (rhs) == NOP_EXPR || TREE_CODE (rhs) == CONVERT_EXPR - || TREE_CODE (rhs) == VIEW_CONVERT_EXPR || TREE_CODE (rhs) == NON_LVALUE_EXPR) { /* Recurse through the type conversion. */ @@ -3557,7 +3770,7 @@ static bool find_assert_locations (basic_block bb); /* Determine whether the outgoing edges of BB should receive an ASSERT_EXPR for each of the operands of BB's LAST statement. - The last statement of BB must be a COND_EXPR or a SWITCH_EXPR. + The last statement of BB must be a COND_EXPR. If any of the sub-graphs rooted at BB have an interesting use of the predicate operands, an assert location node is added to the @@ -3612,8 +3825,7 @@ find_conditional_asserts (basic_block bb, tree last) /* Traverse the strictly dominated sub-graph rooted at E->DEST to determine if any of the operands in the conditional predicate are used. */ - if (e->dest != bb) - need_assert |= find_assert_locations (e->dest); + need_assert |= find_assert_locations (e->dest); /* Register the necessary assertions for each operand in the conditional predicate. */ @@ -3630,6 +3842,131 @@ find_conditional_asserts (basic_block bb, tree last) return need_assert; } +/* Compare two case labels sorting first by the destination label uid + and then by the case value. */ + +static int +compare_case_labels (const void *p1, const void *p2) +{ + const_tree const case1 = *(const_tree const*)p1; + const_tree const case2 = *(const_tree const*)p2; + unsigned int uid1 = DECL_UID (CASE_LABEL (case1)); + unsigned int uid2 = DECL_UID (CASE_LABEL (case2)); + + if (uid1 < uid2) + return -1; + else if (uid1 == uid2) + { + /* Make sure the default label is first in a group. */ + if (!CASE_LOW (case1)) + return -1; + else if (!CASE_LOW (case2)) + return 1; + else + return tree_int_cst_compare (CASE_LOW (case1), CASE_LOW (case2)); + } + else + return 1; +} + +/* Determine whether the outgoing edges of BB should receive an + ASSERT_EXPR for each of the operands of BB's LAST statement. + The last statement of BB must be a SWITCH_EXPR. + + If any of the sub-graphs rooted at BB have an interesting use of + the predicate operands, an assert location node is added to the + list of assertions for the corresponding operands. */ + +static bool +find_switch_asserts (basic_block bb, tree last) +{ + bool need_assert; + block_stmt_iterator bsi; + tree op, cond; + edge e; + tree vec = SWITCH_LABELS (last), vec2; + size_t n = TREE_VEC_LENGTH (vec); + unsigned int idx; + + need_assert = false; + bsi = bsi_for_stmt (last); + op = TREE_OPERAND (last, 0); + if (TREE_CODE (op) != SSA_NAME) + return false; + + /* Build a vector of case labels sorted by destination label. */ + vec2 = make_tree_vec (n); + for (idx = 0; idx < n; ++idx) + TREE_VEC_ELT (vec2, idx) = TREE_VEC_ELT (vec, idx); + qsort (&TREE_VEC_ELT (vec2, 0), n, sizeof (tree), compare_case_labels); + + for (idx = 0; idx < n; ++idx) + { + tree min, max; + tree cl = TREE_VEC_ELT (vec2, idx); + + min = CASE_LOW (cl); + max = CASE_HIGH (cl); + + /* If there are multiple case labels with the same destination + we need to combine them to a single value range for the edge. */ + if (idx + 1 < n + && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx + 1))) + { + /* Skip labels until the last of the group. */ + do { + ++idx; + } while (idx < n + && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx))); + --idx; + + /* Pick up the maximum of the case label range. */ + if (CASE_HIGH (TREE_VEC_ELT (vec2, idx))) + max = CASE_HIGH (TREE_VEC_ELT (vec2, idx)); + else + max = CASE_LOW (TREE_VEC_ELT (vec2, idx)); + } + + /* Nothing to do if the range includes the default label until we + can register anti-ranges. */ + if (min == NULL_TREE) + continue; + + /* Find the edge to register the assert expr on. */ + e = find_edge (bb, label_to_block (CASE_LABEL (cl))); + + /* Remove the SWITCH_EXPR operand from the FOUND_IN_SUBGRAPH bitmap. + Otherwise, when we finish traversing each of the sub-graphs, we + won't know whether the variables were found in the sub-graphs or + if they had been found in a block upstream from BB. */ + RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); + + /* Traverse the strictly dominated sub-graph rooted at E->DEST + to determine if any of the operands in the conditional + predicate are used. */ + if (e->dest != bb) + need_assert |= find_assert_locations (e->dest); + + /* Register the necessary assertions for the operand in the + SWITCH_EXPR. */ + cond = build2 (max ? GE_EXPR : EQ_EXPR, boolean_type_node, + op, fold_convert (TREE_TYPE (op), min)); + need_assert |= register_edge_assert_for (op, e, bsi, cond); + if (max) + { + cond = build2 (LE_EXPR, boolean_type_node, + op, fold_convert (TREE_TYPE (op), max)); + need_assert |= register_edge_assert_for (op, e, bsi, cond); + } + } + + /* Finally, indicate that we have found the operand in the + SWITCH_EXPR. */ + SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); + + return need_assert; +} + /* Traverse all the statements in block BB looking for statements that may generate useful assertions for the SSA names in their operand. @@ -3692,9 +4029,7 @@ find_conditional_asserts (basic_block bb, tree last) If this function returns true, then it means that there are names for which we need to generate ASSERT_EXPRs. Those assertions are - inserted by process_assert_insertions. - - TODO. Handle SWITCH_EXPR. */ + inserted by process_assert_insertions. */ static bool find_assert_locations (basic_block bb) @@ -3817,6 +4152,11 @@ find_assert_locations (basic_block bb) && !ZERO_SSA_OPERANDS (last, SSA_OP_USE)) need_assert |= find_conditional_asserts (bb, last); + if (last + && TREE_CODE (last) == SWITCH_EXPR + && !ZERO_SSA_OPERANDS (last, SSA_OP_USE)) + need_assert |= find_switch_asserts (bb, last); + /* Recurse into the dominator children of BB. */ for (son = first_dom_son (CDI_DOMINATORS, bb); son; @@ -4005,7 +4345,7 @@ check_array_ref (tree ref, location_t* locus, bool ignore_off_by_one) low_sub = up_sub = TREE_OPERAND (ref, 1); - if (!up_bound || !locus || TREE_NO_WARNING (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 @@ -4064,6 +4404,36 @@ check_array_ref (tree ref, location_t* locus, bool ignore_off_by_one) } } +/* Searches if the expr T, located at LOCATION computes + address of an ARRAY_REF, and call check_array_ref on it. */ + +static void +search_for_addr_array(tree t, location_t* location) +{ + while (TREE_CODE (t) == SSA_NAME) + { + t = SSA_NAME_DEF_STMT (t); + if (TREE_CODE (t) != GIMPLE_MODIFY_STMT) + return; + t = GIMPLE_STMT_OPERAND (t, 1); + } + + + /* We are only interested in addresses of ARRAY_REF's. */ + if (TREE_CODE (t) != ADDR_EXPR) + return; + + /* Check each ARRAY_REFs in the reference chain. */ + do + { + if (TREE_CODE (t) == ARRAY_REF) + check_array_ref (t, location, true /*ignore_off_by_one*/); + + 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 @@ -4077,48 +4447,32 @@ check_array_bounds (tree *tp, int *walk_subtree, void *data) tree stmt = (tree)data; location_t *location = EXPR_LOCUS (stmt); + if (!EXPR_HAS_LOCATION (stmt)) + { + *walk_subtree = FALSE; + return NULL_TREE; + } + *walk_subtree = TRUE; if (TREE_CODE (t) == ARRAY_REF) check_array_ref (t, location, false /*ignore_off_by_one*/); - else if (TREE_CODE (t) == ADDR_EXPR) - { - use_operand_p op; - tree use_stmt; - t = TREE_OPERAND (t, 0); - - /* Don't warn on statements like - - ssa_name = 500 + &array[-200] - - or - - ssa_name = &array[-200] - other_name = ssa_name + 300; - - which are sometimes - produced by other optimizing passes. */ - - if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT - && BINARY_CLASS_P (GIMPLE_STMT_OPERAND (stmt, 1))) - *walk_subtree = FALSE; - if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT - && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME - && single_imm_use (GIMPLE_STMT_OPERAND (stmt, 0), &op, &use_stmt) - && TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT - && BINARY_CLASS_P (GIMPLE_STMT_OPERAND (use_stmt, 1))) - *walk_subtree = FALSE; + if (TREE_CODE (t) == INDIRECT_REF + || (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))) + search_for_addr_array (TREE_OPERAND (t, 0), location); + else if (TREE_CODE (t) == CALL_EXPR) + { + tree arg; + call_expr_arg_iterator iter; - while (*walk_subtree && handled_component_p (t)) - { - if (TREE_CODE (t) == ARRAY_REF) - check_array_ref (t, location, true /*ignore_off_by_one*/); - t = TREE_OPERAND (t, 0); - } - *walk_subtree = FALSE; + FOR_EACH_CALL_EXPR_ARG (arg, iter, t) + search_for_addr_array (arg, location); } + if (TREE_CODE (t) == ADDR_EXPR) + *walk_subtree = FALSE; + return NULL_TREE; } @@ -4269,6 +4623,7 @@ vrp_initialize (void) basic_block bb; vr_value = XCNEWVEC (value_range_t *, num_ssa_names); + vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names); FOR_EACH_BB (bb) { @@ -4369,6 +4724,27 @@ vrp_visit_assignment (tree stmt, tree *output_p) return SSA_PROP_VARYING; } +/* Helper that gets the value range of the SSA_NAME with version I + or a symbolic range containing the SSA_NAME only if the value range + is varying or undefined. */ + +static inline value_range_t +get_vr_for_comparison (int i) +{ + value_range_t vr = *(vr_value[i]); + + /* If name N_i does not have a valid range, use N_i as its own + range. This allows us to compare against names that may + have N_i in their ranges. */ + if (vr.type == VR_VARYING || vr.type == VR_UNDEFINED) + { + vr.type = VR_RANGE; + vr.min = ssa_name (i); + vr.max = ssa_name (i); + } + + return vr; +} /* Compare all the value ranges for names equivalent to VAR with VAL using comparison code COMP. Return the same value returned by @@ -4384,37 +4760,35 @@ compare_name_with_value (enum tree_code comp, tree var, tree val, bitmap e; tree retval, t; int used_strict_overflow; - - t = retval = NULL_TREE; + bool sop; + value_range_t equiv_vr; /* Get the set of equivalences for VAR. */ e = get_value_range (var)->equiv; - /* Add VAR to its own set of equivalences so that VAR's value range - is processed by this loop (otherwise, we would have to replicate - the body of the loop just to check VAR's value range). */ - bitmap_set_bit (e, SSA_NAME_VERSION (var)); - /* Start at -1. Set it to 0 if we do a comparison without relying on overflow, or 1 if all comparisons rely on overflow. */ used_strict_overflow = -1; - EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi) - { - bool sop; - - value_range_t equiv_vr = *(vr_value[i]); + /* Compare vars' value range with val. */ + equiv_vr = get_vr_for_comparison (SSA_NAME_VERSION (var)); + sop = false; + retval = compare_range_with_value (comp, &equiv_vr, val, &sop); + if (retval) + used_strict_overflow = sop ? 1 : 0; - /* If name N_i does not have a valid range, use N_i as its own - range. This allows us to compare against names that may - have N_i in their ranges. */ - if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED) - { - equiv_vr.type = VR_RANGE; - equiv_vr.min = ssa_name (i); - equiv_vr.max = ssa_name (i); - } + /* If the equiv set is empty we have done all work we need to do. */ + if (e == NULL) + { + if (retval + && used_strict_overflow > 0) + *strict_overflow_p = true; + return retval; + } + EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi) + { + equiv_vr = get_vr_for_comparison (i); sop = false; t = compare_range_with_value (comp, &equiv_vr, val, &sop); if (t) @@ -4438,18 +4812,11 @@ compare_name_with_value (enum tree_code comp, tree var, tree val, } } - /* Remove VAR from its own equivalence set. */ - bitmap_clear_bit (e, SSA_NAME_VERSION (var)); + if (retval + && used_strict_overflow > 0) + *strict_overflow_p = true; - if (retval) - { - if (used_strict_overflow > 0) - *strict_overflow_p = true; - return retval; - } - - /* We couldn't find a non-NULL value for the predicate. */ - return NULL_TREE; + return retval; } @@ -4469,12 +4836,27 @@ compare_names (enum tree_code comp, tree n1, tree n2, bitmap_iterator bi1, bi2; unsigned i1, i2; int used_strict_overflow; + static bitmap_obstack *s_obstack = NULL; + static bitmap s_e1 = NULL, s_e2 = NULL; /* Compare the ranges of every name equivalent to N1 against the ranges of every name equivalent to N2. */ e1 = get_value_range (n1)->equiv; e2 = get_value_range (n2)->equiv; + /* Use the fake bitmaps if e1 or e2 are not available. */ + if (s_obstack == NULL) + { + s_obstack = XNEW (bitmap_obstack); + bitmap_obstack_initialize (s_obstack); + s_e1 = BITMAP_ALLOC (s_obstack); + s_e2 = BITMAP_ALLOC (s_obstack); + } + if (e1 == NULL) + e1 = s_e1; + if (e2 == NULL) + e2 = s_e2; + /* Add N1 and N2 to their own set of equivalences to avoid duplicating the body of the loop just to check N1 and N2 ranges. */ @@ -4502,29 +4884,14 @@ compare_names (enum tree_code comp, tree n1, tree n2, of the loop just to check N1 and N2 ranges. */ EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1) { - value_range_t vr1 = *(vr_value[i1]); - - /* If the range is VARYING or UNDEFINED, use the name itself. */ - if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED) - { - vr1.type = VR_RANGE; - vr1.min = ssa_name (i1); - vr1.max = ssa_name (i1); - } + value_range_t vr1 = get_vr_for_comparison (i1); t = retval = NULL_TREE; EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2) { - bool sop; - - value_range_t vr2 = *(vr_value[i2]); + bool sop = false; - if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED) - { - vr2.type = VR_RANGE; - vr2.min = ssa_name (i2); - vr2.max = ssa_name (i2); - } + value_range_t vr2 = get_vr_for_comparison (i2); t = compare_ranges (comp, &vr1, &vr2, &sop); if (t) @@ -4723,8 +5090,7 @@ vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p) *taken_edge_p = NULL; - /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to - add ASSERT_EXPRs for them. */ + /* FIXME. Handle SWITCH_EXPRs. */ if (TREE_CODE (stmt) == SWITCH_EXPR) return SSA_PROP_VARYING; @@ -4929,6 +5295,12 @@ vrp_meet (value_range_t *vr0, value_range_t *vr1) else goto give_up; + /* Check for useless ranges. */ + if (INTEGRAL_TYPE_P (TREE_TYPE (min)) + && ((vrp_val_is_min (min) || is_overflow_infinity (min)) + && (vrp_val_is_max (max) || is_overflow_infinity (max)))) + goto give_up; + /* The resulting set of equivalences is the intersection of the two sets. */ if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) @@ -5022,7 +5394,7 @@ vrp_visit_phi_node (tree phi) tree lhs = PHI_RESULT (phi); value_range_t *lhs_vr = get_value_range (lhs); value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; - bool all_const = true; + int edges, old_edges; copy_value_range (&vr_result, lhs_vr); @@ -5032,6 +5404,7 @@ vrp_visit_phi_node (tree phi) print_generic_expr (dump_file, phi, dump_flags); } + edges = 0; for (i = 0; i < PHI_NUM_ARGS (phi); i++) { edge e = PHI_ARG_EDGE (phi, i); @@ -5049,13 +5422,20 @@ vrp_visit_phi_node (tree phi) tree arg = PHI_ARG_DEF (phi, i); value_range_t vr_arg; + ++edges; + if (TREE_CODE (arg) == SSA_NAME) { vr_arg = *(get_value_range (arg)); - all_const = false; } else { + if (is_overflow_infinity (arg)) + { + arg = copy_node (arg); + TREE_OVERFLOW (arg) = 0; + } + vr_arg.type = VR_RANGE; vr_arg.min = arg; vr_arg.max = arg; @@ -5081,11 +5461,16 @@ vrp_visit_phi_node (tree phi) if (vr_result.type == VR_VARYING) goto varying; + old_edges = vr_phi_edge_counts[SSA_NAME_VERSION (lhs)]; + vr_phi_edge_counts[SSA_NAME_VERSION (lhs)] = edges; + /* To prevent infinite iterations in the algorithm, derive ranges when the new value is slightly bigger or smaller than the - previous one. */ + previous one. We don't do this if we have seen a new executable + edge; this helps us avoid an overflow infinity for conditionals + which are not in a loop. */ if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE - && !all_const) + && edges <= old_edges) { if (!POINTER_TYPE_P (TREE_TYPE (lhs))) { @@ -5101,12 +5486,11 @@ vrp_visit_phi_node (tree phi) { /* If we will end up with a (-INF, +INF) range, set it to VARYING. */ - if (is_positive_overflow_infinity (vr_result.max) - || (vr_result.max - == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))) + if (vrp_val_is_max (vr_result.max)) goto varying; - if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))) + if (!needs_overflow_infinity (TREE_TYPE (vr_result.min)) + || !vrp_var_may_overflow (lhs, phi)) vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)); else if (supports_overflow_infinity (TREE_TYPE (vr_result.min))) vr_result.min = @@ -5121,12 +5505,11 @@ vrp_visit_phi_node (tree phi) { /* If we will end up with a (-INF, +INF) range, set it to VARYING. */ - if (is_negative_overflow_infinity (vr_result.min) - || (vr_result.min - == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)))) + if (vrp_val_is_min (vr_result.min)) goto varying; - if (!needs_overflow_infinity (TREE_TYPE (vr_result.max))) + if (!needs_overflow_infinity (TREE_TYPE (vr_result.max)) + || !vrp_var_may_overflow (lhs, phi)) vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)); else if (supports_overflow_infinity (TREE_TYPE (vr_result.max))) vr_result.max = @@ -5170,7 +5553,7 @@ simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code) { bool sop = false; - val = compare_range_with_value (GT_EXPR, vr, integer_zero_node, &sop); + val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop); if (val && sop @@ -5306,6 +5689,8 @@ test_for_singularity (enum tree_code cond_code, tree op0, { tree one = build_int_cst (TREE_TYPE (op0), 1); max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one); + if (EXPR_P (max)) + TREE_NO_WARNING (max) = 1; } } else if (cond_code == GE_EXPR || cond_code == GT_EXPR) @@ -5319,6 +5704,8 @@ test_for_singularity (enum tree_code cond_code, tree op0, { tree one = build_int_cst (TREE_TYPE (op0), 1); min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one); + if (EXPR_P (min)) + TREE_NO_WARNING (min) = 1; } } @@ -5595,13 +5982,7 @@ identify_jump_threads (void) static void finalize_jump_threads (void) { - bool cfg_altered = false; - cfg_altered = thread_through_all_blocks (); - - /* If we threaded jumps, then we need to recompute the dominance - information. */ - if (cfg_altered) - free_dominance_info (CDI_DOMINATORS); + thread_through_all_blocks (false); VEC_free (tree, heap, stack); } @@ -5664,12 +6045,28 @@ vrp_finalize (void) free (single_val_range); free (vr_value); + free (vr_phi_edge_counts); /* So that we can distinguish between VRP data being available and not available. */ vr_value = NULL; + vr_phi_edge_counts = NULL; } +/* Calculates number of iterations for all loops, to ensure that they are + cached. */ + +static void +record_numbers_of_iterations (void) +{ + loop_iterator li; + struct loop *loop; + + FOR_EACH_LOOP (li, loop, 0) + { + number_of_latch_executions (loop); + } +} /* Main entry point to VRP (Value Range Propagation). This pass is loosely based on J. R. C. Patterson, ``Accurate Static Branch @@ -5718,22 +6115,27 @@ vrp_finalize (void) static unsigned int execute_vrp (void) { + loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); + rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); + scev_initialize (); + insert_range_assertions (); - loop_optimizer_init (LOOPS_NORMAL); - if (current_loops) - scev_initialize (); + /* Compute the # of iterations for each loop before we start the VRP + analysis. The value ranges determined by VRP are used in expression + simplification, that is also used by the # of iterations analysis. + However, in the middle of the VRP analysis, the value ranges do not take + all the possible paths in CFG into account, so they do not have to be + correct, and the # of iterations analysis can obtain wrong results. + This is a problem, since the results of the # of iterations analysis + are cached, so these mistakes would not be corrected when the value + ranges are corrected. */ + record_numbers_of_iterations (); vrp_initialize (); ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node); vrp_finalize (); - if (current_loops) - { - scev_finalize (); - loop_optimizer_finalize (); - } - /* ASSERT_EXPRs must be removed before finalizing jump threads as finalizing jump threads calls the CFG cleanup code which does not properly handle ASSERT_EXPRs. */ @@ -5747,6 +6149,9 @@ execute_vrp (void) update_ssa (TODO_update_ssa); finalize_jump_threads (); + scev_finalize (); + loop_optimizer_finalize (); + return 0; }