X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-vrp.c;h=8fcf629addecac26ba0e8ba1508321b3ee7c1a48;hb=a2145c8fcd31ec4449cfd8bf9375c269c4627948;hp=81645485f8b2dd65da83e8e356d57a2855d0a89e;hpb=e1b11b0513310e407b46b1c7fe86dab97eba038c;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 81645485f8b..8fcf629adde 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -1,5 +1,6 @@ /* Support routines for Value Range Propagation (VRP). - Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc. + Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 + Free Software Foundation, Inc. Contributed by Diego Novillo . This file is part of GCC. @@ -30,15 +31,49 @@ along with GCC; see the file COPYING3. If not see #include "tree-pass.h" #include "tree-dump.h" #include "timevar.h" -#include "diagnostic.h" -#include "toplev.h" +#include "tree-pretty-print.h" +#include "gimple-pretty-print.h" +#include "diagnostic-core.h" #include "intl.h" #include "cfgloop.h" #include "tree-scalar-evolution.h" #include "tree-ssa-propagate.h" #include "tree-chrec.h" +#include "gimple-fold.h" +/* Type of value ranges. See value_range_d for a description of these + types. */ +enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING }; + +/* Range of values that can be associated with an SSA_NAME after VRP + has executed. */ +struct value_range_d +{ + /* Lattice value represented by this range. */ + enum value_range_type type; + + /* Minimum and maximum values represented by this range. These + values should be interpreted as follows: + + - If TYPE is VR_UNDEFINED or VR_VARYING then MIN and MAX must + be NULL. + + - If TYPE == VR_RANGE then MIN holds the minimum value and + MAX holds the maximum value of the range [MIN, MAX]. + + - If TYPE == ANTI_RANGE the variable is known to NOT + take any values in the range [MIN, MAX]. */ + tree min; + tree max; + + /* Set of SSA names whose value ranges are equivalent to this one. + This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */ + bitmap equiv; +}; + +typedef struct value_range_d value_range_t; + /* Set of SSA names found live during the RPO traversal of the function for still active basic-blocks. */ static sbitmap *live; @@ -208,9 +243,7 @@ supports_overflow_infinity (const_tree type) static inline tree make_overflow_infinity (tree val) { -#ifdef ENABLE_CHECKING - gcc_assert (val != NULL_TREE && CONSTANT_CLASS_P (val)); -#endif + gcc_checking_assert (val != NULL_TREE && CONSTANT_CLASS_P (val)); val = copy_node (val); TREE_OVERFLOW (val) = 1; return val; @@ -221,9 +254,7 @@ make_overflow_infinity (tree val) static inline tree negative_overflow_infinity (tree type) { -#ifdef ENABLE_CHECKING - gcc_assert (supports_overflow_infinity (type)); -#endif + gcc_checking_assert (supports_overflow_infinity (type)); return make_overflow_infinity (vrp_val_min (type)); } @@ -232,9 +263,7 @@ negative_overflow_infinity (tree type) static inline tree positive_overflow_infinity (tree type) { -#ifdef ENABLE_CHECKING - gcc_assert (supports_overflow_infinity (type)); -#endif + gcc_checking_assert (supports_overflow_infinity (type)); return make_overflow_infinity (vrp_val_max (type)); } @@ -297,9 +326,7 @@ avoid_overflow_infinity (tree val) return vrp_val_max (TREE_TYPE (val)); else { -#ifdef ENABLE_CHECKING - gcc_assert (vrp_val_is_min (val)); -#endif + gcc_checking_assert (vrp_val_is_min (val)); return vrp_val_min (TREE_TYPE (val)); } } @@ -334,7 +361,7 @@ nonnull_arg_p (const_tree arg) /* Get the position number for ARG in the function signature. */ for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl); t; - t = TREE_CHAIN (t), arg_num++) + t = DECL_CHAIN (t), arg_num++) { if (t == arg) break; @@ -445,8 +472,8 @@ set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, if (tree_int_cst_lt (max, min)) { tree one = build_int_cst (TREE_TYPE (min), 1); - tree tmp = int_const_binop (PLUS_EXPR, max, one, 0); - max = int_const_binop (MINUS_EXPR, min, one, 0); + tree tmp = int_const_binop (PLUS_EXPR, max, one); + max = int_const_binop (MINUS_EXPR, min, one); min = tmp; /* There's one corner case, if we had [C+1, C] before we now have @@ -479,14 +506,14 @@ set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, && integer_zerop (max))) { tree one = build_int_cst (TREE_TYPE (max), 1); - min = int_const_binop (PLUS_EXPR, max, one, 0); + min = int_const_binop (PLUS_EXPR, max, one); max = vrp_val_max (TREE_TYPE (max)); t = VR_RANGE; } else if (is_max) { tree one = build_int_cst (TREE_TYPE (min), 1); - max = int_const_binop (MINUS_EXPR, min, one, 0); + max = int_const_binop (MINUS_EXPR, min, one); min = vrp_val_min (TREE_TYPE (min)); t = VR_RANGE; } @@ -688,6 +715,8 @@ static inline bool vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2) { return (b1 == b2 + || ((!b1 || bitmap_empty_p (b1)) + && (!b2 || bitmap_empty_p (b2))) || (b1 && b2 && bitmap_equal_p (b1, b2))); } @@ -763,6 +792,27 @@ range_is_null (value_range_t *vr) && 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. */ @@ -842,6 +892,8 @@ gimple_assign_nonnegative_warnv_p (gimple stmt, bool *strict_overflow_p) gimple_assign_rhs1 (stmt), gimple_assign_rhs2 (stmt), strict_overflow_p); + case GIMPLE_TERNARY_RHS: + return false; case GIMPLE_SINGLE_RHS: return tree_single_nonnegative_warnv_p (gimple_assign_rhs1 (stmt), strict_overflow_p); @@ -913,6 +965,8 @@ gimple_assign_nonzero_warnv_p (gimple stmt, bool *strict_overflow_p) gimple_assign_rhs1 (stmt), gimple_assign_rhs2 (stmt), strict_overflow_p); + case GIMPLE_TERNARY_RHS: + return false; case GIMPLE_SINGLE_RHS: return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt), strict_overflow_p); @@ -960,7 +1014,7 @@ vrp_stmt_computes_nonzero (gimple stmt, bool *strict_overflow_p) tree base = get_base_address (TREE_OPERAND (expr, 0)); if (base != NULL_TREE - && TREE_CODE (base) == INDIRECT_REF + && TREE_CODE (base) == MEM_REF && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) { value_range_t *vr = get_value_range (TREE_OPERAND (base, 0)); @@ -1342,6 +1396,10 @@ ssa_name_nonnegative_p (const_tree t) { value_range_t *vr = get_value_range (t); + if (INTEGRAL_TYPE_P (t) + && TYPE_UNSIGNED (t)) + return true; + if (!vr) return false; @@ -1468,7 +1526,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) { min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (cond, 1)), TREE_OPERAND (cond, 1)); - max = int_const_binop (PLUS_EXPR, limit, min, 0); + max = int_const_binop (PLUS_EXPR, limit, min); cond = TREE_OPERAND (cond, 0); } else @@ -1480,10 +1538,10 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) /* Make sure to not set TREE_OVERFLOW on the final type conversion. We are willingly interpreting large positive unsigned values as negative singed values here. */ - min = force_fit_type_double (TREE_TYPE (var), TREE_INT_CST_LOW (min), - TREE_INT_CST_HIGH (min), 0, false); - max = force_fit_type_double (TREE_TYPE (var), TREE_INT_CST_LOW (max), - TREE_INT_CST_HIGH (max), 0, false); + min = force_fit_type_double (TREE_TYPE (var), tree_to_double_int (min), + 0, false); + max = force_fit_type_double (TREE_TYPE (var), tree_to_double_int (max), + 0, false); /* We can transform a max, min range to an anti-range or vice-versa. Use set_and_canonicalize_value_range which does @@ -1896,7 +1954,7 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2) { tree res; - res = int_const_binop (code, val1, val2, 0); + res = int_const_binop (code, val1, val2); /* If we are using unsigned arithmetic, operate symbolically on -INF and +INF as int_const_binop only handles signed overflow. */ @@ -1923,7 +1981,7 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2) { tree tmp = int_const_binop (TRUNC_DIV_EXPR, res, - val1, 0); + val1); int check = compare_values (tmp, val2); if (check != 0) @@ -2032,6 +2090,60 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2) } +/* For range VR compute two double_int bitmasks. In *MAY_BE_NONZERO + bitmask if some bit is unset, it means for all numbers in the range + the bit is 0, otherwise it might be 0 or 1. In *MUST_BE_NONZERO + bitmask if some bit is set, it means for all numbers in the range + the bit is 1, otherwise it might be 0 or 1. */ + +static bool +zero_nonzero_bits_from_vr (value_range_t *vr, double_int *may_be_nonzero, + double_int *must_be_nonzero) +{ + if (range_int_cst_p (vr)) + { + if (range_int_cst_singleton_p (vr)) + { + *may_be_nonzero = tree_to_double_int (vr->min); + *must_be_nonzero = *may_be_nonzero; + return true; + } + if (tree_int_cst_sgn (vr->min) >= 0) + { + double_int dmin = tree_to_double_int (vr->min); + double_int dmax = tree_to_double_int (vr->max); + double_int xor_mask = double_int_xor (dmin, dmax); + *may_be_nonzero = double_int_ior (dmin, dmax); + *must_be_nonzero = double_int_and (dmin, dmax); + if (xor_mask.high != 0) + { + unsigned HOST_WIDE_INT mask + = ((unsigned HOST_WIDE_INT) 1 + << floor_log2 (xor_mask.high)) - 1; + may_be_nonzero->low = ALL_ONES; + may_be_nonzero->high |= mask; + must_be_nonzero->low = 0; + must_be_nonzero->high &= ~mask; + } + else if (xor_mask.low != 0) + { + unsigned HOST_WIDE_INT mask + = ((unsigned HOST_WIDE_INT) 1 + << floor_log2 (xor_mask.low)) - 1; + may_be_nonzero->low |= mask; + must_be_nonzero->low &= ~mask; + } + return true; + } + } + may_be_nonzero->low = ALL_ONES; + may_be_nonzero->high = ALL_ONES; + must_be_nonzero->low = 0; + must_be_nonzero->high = 0; + return false; +} + + /* Extract range information from a binary expression EXPR based on the ranges of each of its operands and the expression code. */ @@ -2057,6 +2169,7 @@ extract_range_from_binary_expr (value_range_t *vr, && code != CEIL_DIV_EXPR && code != EXACT_DIV_EXPR && code != ROUND_DIV_EXPR + && code != TRUNC_MOD_EXPR && code != RSHIFT_EXPR && code != MIN_EXPR && code != MAX_EXPR @@ -2125,6 +2238,7 @@ extract_range_from_binary_expr (value_range_t *vr, && code != CEIL_DIV_EXPR && code != EXACT_DIV_EXPR && code != ROUND_DIV_EXPR + && code != TRUNC_MOD_EXPR && (vr0.type == VR_VARYING || vr1.type == VR_VARYING || vr0.type != vr1.type @@ -2155,15 +2269,30 @@ extract_range_from_binary_expr (value_range_t *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, expr_type); - else if (range_is_null (&vr0) && range_is_null (&vr1)) - set_value_range_to_null (vr, expr_type); + if (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, expr_type); + else if (range_is_null (&vr0) && range_is_null (&vr1)) + set_value_range_to_null (vr, expr_type); + else + set_value_range_to_varying (vr); + } + else if (code == BIT_AND_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, expr_type); + else if (range_is_null (&vr0) || range_is_null (&vr1)) + set_value_range_to_null (vr, expr_type); + else + set_value_range_to_varying (vr); + } else - set_value_range_to_varying (vr); + gcc_unreachable (); return; } @@ -2229,17 +2358,27 @@ extract_range_from_binary_expr (value_range_t *vr, op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0]. Note that we are guaranteed to have vr0.type == vr1.type at this point. */ - if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE) + if (vr0.type == VR_ANTI_RANGE) { - set_value_range_to_varying (vr); - return; + 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); } - - /* 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 @@ -2329,6 +2468,22 @@ extract_range_from_binary_expr (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 + && (vr1.type != VR_RANGE + || symbolic_range_p (&vr1) + || range_includes_zero_p (&vr1))) + { + 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. */ @@ -2475,6 +2630,31 @@ extract_range_from_binary_expr (value_range_t *vr, } } } + else if (code == TRUNC_MOD_EXPR) + { + bool sop = false; + if (vr1.type != VR_RANGE + || symbolic_range_p (&vr1) + || range_includes_zero_p (&vr1) + || vrp_val_is_min (vr1.min)) + { + set_value_range_to_varying (vr); + return; + } + type = VR_RANGE; + /* Compute MAX <|vr1.min|, |vr1.max|> - 1. */ + max = fold_unary_to_constant (ABS_EXPR, TREE_TYPE (vr1.min), vr1.min); + if (tree_int_cst_lt (max, vr1.max)) + max = vr1.max; + max = int_const_binop (MINUS_EXPR, max, integer_one_node); + /* If the dividend is non-negative the modulus will be + non-negative as well. */ + if (TYPE_UNSIGNED (TREE_TYPE (max)) + || (vrp_expr_computes_nonnegative (op0, &sop) && !sop)) + min = build_int_cst (TREE_TYPE (max), 0); + else + min = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (max), max); + } else if (code == MINUS_EXPR) { /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to @@ -2495,71 +2675,79 @@ extract_range_from_binary_expr (value_range_t *vr, min = vrp_int_const_binop (code, vr0.min, vr1.max); max = vrp_int_const_binop (code, vr0.max, vr1.min); } - else if (code == BIT_AND_EXPR) + else if (code == BIT_AND_EXPR || code == BIT_IOR_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) - { - 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) - && tree_int_cst_sgn (vr1.max) >= 0) - { - type = VR_RANGE; - min = build_int_cst (expr_type, 0); - max = vr1.max; - } - else + bool vr0_int_cst_singleton_p, vr1_int_cst_singleton_p; + bool int_cst_range0, int_cst_range1; + double_int may_be_nonzero0, may_be_nonzero1; + double_int must_be_nonzero0, must_be_nonzero1; + + vr0_int_cst_singleton_p = range_int_cst_singleton_p (&vr0); + vr1_int_cst_singleton_p = range_int_cst_singleton_p (&vr1); + int_cst_range0 = zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0, + &must_be_nonzero0); + int_cst_range1 = zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1, + &must_be_nonzero1); + + type = VR_RANGE; + if (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p) + min = max = int_const_binop (code, vr0.max, vr1.max); + else if (!int_cst_range0 && !int_cst_range1) { set_value_range_to_varying (vr); return; } - } - else if (code == BIT_IOR_EXPR) - { - if (vr0.type == VR_RANGE - && vr1.type == VR_RANGE - && TREE_CODE (vr0.min) == INTEGER_CST - && TREE_CODE (vr1.min) == INTEGER_CST - && TREE_CODE (vr0.max) == INTEGER_CST - && TREE_CODE (vr1.max) == INTEGER_CST - && 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) + else if (code == BIT_AND_EXPR) + { + min = double_int_to_tree (expr_type, + double_int_and (must_be_nonzero0, + must_be_nonzero1)); + max = double_int_to_tree (expr_type, + double_int_and (may_be_nonzero0, + may_be_nonzero1)); + if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0) + min = NULL_TREE; + if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0) + max = NULL_TREE; + if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0) { - ior_max.low = ~(unsigned HOST_WIDE_INT)0u; - ior_max.high |= ((HOST_WIDE_INT) 1 - << floor_log2 (ior_max.high)) - 1; + if (min == NULL_TREE) + min = build_int_cst (expr_type, 0); + if (max == NULL_TREE || tree_int_cst_lt (vr0.max, max)) + max = vr0.max; + } + if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0) + { + if (min == NULL_TREE) + min = build_int_cst (expr_type, 0); + if (max == NULL_TREE || tree_int_cst_lt (vr1.max, max)) + max = vr1.max; } - 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 + else if (!int_cst_range0 + || !int_cst_range1 + || tree_int_cst_sgn (vr0.min) < 0 + || tree_int_cst_sgn (vr1.min) < 0) { set_value_range_to_varying (vr); return; } + else + { + min = double_int_to_tree (expr_type, + double_int_ior (must_be_nonzero0, + must_be_nonzero1)); + max = double_int_to_tree (expr_type, + double_int_ior (may_be_nonzero0, + may_be_nonzero1)); + if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0) + min = vr0.min; + else + min = vrp_int_const_binop (MAX_EXPR, min, vr0.min); + if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0) + max = NULL_TREE; + min = vrp_int_const_binop (MAX_EXPR, min, vr1.min); + } } else gcc_unreachable (); @@ -2714,21 +2902,33 @@ extract_range_from_unary_expr (value_range_t *vr, enum tree_code code, || 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, - int_const_binop (MINUS_EXPR, vr0.max, vr0.min, 0), - size_int (TYPE_PRECISION (outer_type)), 0))))) + int_const_binop (MINUS_EXPR, vr0.max, vr0.min), + size_int (TYPE_PRECISION (outer_type))))))) { tree new_min, new_max; new_min = force_fit_type_double (outer_type, - TREE_INT_CST_LOW (vr0.min), - TREE_INT_CST_HIGH (vr0.min), 0, 0); + tree_to_double_int (vr0.min), + 0, false); new_max = force_fit_type_double (outer_type, - TREE_INT_CST_LOW (vr0.max), - TREE_INT_CST_HIGH (vr0.max), 0, 0); + tree_to_double_int (vr0.max), + 0, false); + 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; @@ -2883,7 +3083,7 @@ extract_range_from_unary_expr (value_range_t *vr, enum tree_code code, min = (vr0.min != type_min_value ? int_const_binop (PLUS_EXPR, type_min_value, - integer_one_node, 0) + integer_one_node) : type_min_value); } else @@ -3140,7 +3340,7 @@ static void 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 @@ -3161,7 +3361,13 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, 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 @@ -3196,6 +3402,43 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, else tmax = TYPE_MAX_VALUE (type); + /* Try to use estimated number of iterations for the loop to constrain the + final value in the evolution. + We are interested in the number of executions of the latch, while + nb_iterations_upper_bound includes the last execution of the exit test. */ + if (TREE_CODE (step) == INTEGER_CST + && loop->any_upper_bound + && !double_int_zero_p (loop->nb_iterations_upper_bound) + && is_gimple_val (init) + && (TREE_CODE (init) != SSA_NAME + || get_value_range (init)->type == VR_RANGE)) + { + value_range_t maxvr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; + double_int dtmp; + bool unsigned_p = TYPE_UNSIGNED (TREE_TYPE (step)); + int overflow = 0; + + dtmp = double_int_mul_with_sign (tree_to_double_int (step), + double_int_sub ( + loop->nb_iterations_upper_bound, + double_int_one), + unsigned_p, &overflow); + tem = double_int_to_tree (TREE_TYPE (init), dtmp); + /* If the multiplication overflowed we can't do a meaningful + adjustment. */ + if (!overflow && double_int_equal_p (dtmp, tree_to_double_int (tem))) + { + extract_range_from_binary_expr (&maxvr, PLUS_EXPR, + TREE_TYPE (init), init, tem); + /* Likewise if the addition did. */ + if (maxvr.type == VR_RANGE) + { + tmin = maxvr.min; + tmax = maxvr.max; + } + } + } + if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED) { min = tmin; @@ -3228,40 +3471,35 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, /* INIT is the maximum value. If INIT is lower than VR->MAX but no smaller than VR->MIN, set VR->MAX to INIT. */ if (compare_values (init, max) == -1) - { - max = init; - - /* If we just created an invalid range with the minimum - greater than the maximum, we fail conservatively. - This should happen only in unreachable - parts of code, or for invalid programs. */ - if (compare_values (min, max) == 1) - return; - } + max = init; /* 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)) + if (is_negative_overflow_infinity (min) + || compare_values (min, tmin) == -1) min = tmin; + } else { /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */ if (compare_values (init, min) == 1) - { - min = init; + min = init; - /* Again, avoid creating invalid range by failing. */ - if (compare_values (min, max) == 1) - return; - } - - if (is_positive_overflow_infinity (max)) + if (is_positive_overflow_infinity (max) + || compare_values (tmax, max) == -1) max = tmax; } + /* If we just created an invalid range with the minimum + greater than the maximum, we fail conservatively. + This should happen only in unreachable + parts of code, or for invalid programs. */ + if (compare_values (min, max) == 1) + return; + set_value_range (vr, VR_RANGE, min, max, vr->equiv); } } @@ -3280,7 +3518,8 @@ vrp_var_may_overflow (tree var, gimple stmt) 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)); @@ -3676,7 +3915,7 @@ dump_value_range (FILE *file, value_range_t *vr) /* Dump value range VR to stderr. */ -void +DEBUG_FUNCTION void debug_value_range (value_range_t *vr) { dump_value_range (stderr, vr); @@ -3708,7 +3947,7 @@ dump_all_value_ranges (FILE *file) /* Dump all value ranges to stderr. */ -void +DEBUG_FUNCTION void debug_all_value_ranges (void) { dump_all_value_ranges (stderr); @@ -3864,7 +4103,7 @@ dump_asserts_for (FILE *file, tree name) /* Dump all the registered assertions for NAME to stderr. */ -void +DEBUG_FUNCTION void debug_asserts_for (tree name) { dump_asserts_for (stderr, name); @@ -3888,7 +4127,7 @@ dump_all_asserts (FILE *file) /* Dump all the registered assertions for all the names to stderr. */ -void +DEBUG_FUNCTION void debug_all_asserts (void) { dump_all_asserts (stderr); @@ -3917,13 +4156,11 @@ register_new_assert_for (tree name, tree expr, assert_locus_t n, loc, last_loc; basic_block dest_bb; -#if defined ENABLE_CHECKING - gcc_assert (bb == NULL || e == NULL); + gcc_checking_assert (bb == NULL || e == NULL); if (e == NULL) - gcc_assert (gimple_code (gsi_stmt (si)) != GIMPLE_COND - && gimple_code (gsi_stmt (si)) != GIMPLE_SWITCH); -#endif + gcc_checking_assert (gimple_code (gsi_stmt (si)) != GIMPLE_COND + && gimple_code (gsi_stmt (si)) != GIMPLE_SWITCH); /* Never build an assert comparing against an integer constant with TREE_OVERFLOW set. This confuses our undefined overflow warning @@ -4436,28 +4673,35 @@ find_conditional_asserts (basic_block bb, gimple last) return need_assert; } -/* Compare two case labels sorting first by the destination label uid +struct case_info +{ + tree expr; + basic_block bb; +}; + +/* Compare two case labels sorting first by the destination bb index 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)); + const struct case_info *ci1 = (const struct case_info *) p1; + const struct case_info *ci2 = (const struct case_info *) p2; + int idx1 = ci1->bb->index; + int idx2 = ci2->bb->index; - if (uid1 < uid2) + if (idx1 < idx2) return -1; - else if (uid1 == uid2) + else if (idx1 == idx2) { /* Make sure the default label is first in a group. */ - if (!CASE_LOW (case1)) + if (!CASE_LOW (ci1->expr)) return -1; - else if (!CASE_LOW (case2)) + else if (!CASE_LOW (ci2->expr)) return 1; else - return tree_int_cst_compare (CASE_LOW (case1), CASE_LOW (case2)); + return tree_int_cst_compare (CASE_LOW (ci1->expr), + CASE_LOW (ci2->expr)); } else return 1; @@ -4478,8 +4722,8 @@ find_switch_asserts (basic_block bb, gimple last) gimple_stmt_iterator bsi; tree op; edge e; - tree vec2; - size_t n = gimple_switch_num_labels(last); + struct case_info *ci; + size_t n = gimple_switch_num_labels (last); #if GCC_VERSION >= 4000 unsigned int idx; #else @@ -4494,36 +4738,38 @@ find_switch_asserts (basic_block bb, gimple last) return false; /* Build a vector of case labels sorted by destination label. */ - vec2 = make_tree_vec (n); + ci = XNEWVEC (struct case_info, n); for (idx = 0; idx < n; ++idx) - TREE_VEC_ELT (vec2, idx) = gimple_switch_label (last, idx); - qsort (&TREE_VEC_ELT (vec2, 0), n, sizeof (tree), compare_case_labels); + { + ci[idx].expr = gimple_switch_label (last, idx); + ci[idx].bb = label_to_block (CASE_LABEL (ci[idx].expr)); + } + qsort (ci, n, sizeof (struct case_info), compare_case_labels); for (idx = 0; idx < n; ++idx) { tree min, max; - tree cl = TREE_VEC_ELT (vec2, idx); + tree cl = ci[idx].expr; + basic_block cbb = ci[idx].bb; 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))) + if (idx + 1 < n && cbb == ci[idx + 1].bb) { /* Skip labels until the last of the group. */ do { ++idx; - } while (idx < n - && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx))); + } while (idx < n && cbb == ci[idx].bb); --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)); + if (CASE_HIGH (ci[idx].expr)) + max = CASE_HIGH (ci[idx].expr); else - max = CASE_LOW (TREE_VEC_ELT (vec2, idx)); + max = CASE_LOW (ci[idx].expr); } /* Nothing to do if the range includes the default label until we @@ -4532,7 +4778,7 @@ find_switch_asserts (basic_block bb, gimple last) continue; /* Find the edge to register the assert expr on. */ - e = find_edge (bb, label_to_block (CASE_LABEL (cl))); + e = find_edge (bb, cbb); /* Register the necessary assertions for the operand in the SWITCH_EXPR. */ @@ -4550,6 +4796,7 @@ find_switch_asserts (basic_block bb, gimple last) } } + XDELETEVEC (ci); return need_assert; } @@ -4835,16 +5082,19 @@ process_assert_insertions_for (tree name, assert_locus_t loc) 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) { /* We have been asked to insert the assertion on an edge. This is used only by COND_EXPR and SWITCH_EXPR assertions. */ -#if defined ENABLE_CHECKING - gcc_assert (gimple_code (gsi_stmt (loc->si)) == GIMPLE_COND - || gimple_code (gsi_stmt (loc->si)) == GIMPLE_SWITCH); -#endif + gcc_checking_assert (gimple_code (gsi_stmt (loc->si)) == GIMPLE_COND + || (gimple_code (gsi_stmt (loc->si)) + == GIMPLE_SWITCH)); gsi_insert_on_edge (loc->e, assert_stmt); return true; @@ -4980,23 +5230,45 @@ 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 && TREE_CODE (base) == MEM_REF) + { + 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 = DECL_CHAIN (TREE_OPERAND (cref, 1)); + next && TREE_CODE (next) != FIELD_DECL; + next = DECL_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); if (TREE_CODE (low_sub) == SSA_NAME) { @@ -5021,14 +5293,11 @@ check_array_ref (location_t location, tree ref, bool ignore_off_by_one) } } 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))) + && (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"); @@ -5077,6 +5346,51 @@ search_for_addr_array (tree t, location_t location) t = TREE_OPERAND (t, 0); } while (handled_component_p (t)); + + if (TREE_CODE (t) == MEM_REF + && TREE_CODE (TREE_OPERAND (t, 0)) == ADDR_EXPR + && !TREE_NO_WARNING (t)) + { + tree tem = TREE_OPERAND (TREE_OPERAND (t, 0), 0); + tree low_bound, up_bound, el_sz; + double_int idx; + if (TREE_CODE (TREE_TYPE (tem)) != ARRAY_TYPE + || TREE_CODE (TREE_TYPE (TREE_TYPE (tem))) == ARRAY_TYPE + || !TYPE_DOMAIN (TREE_TYPE (tem))) + return; + + low_bound = TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (tem))); + up_bound = TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (tem))); + el_sz = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (tem))); + if (!low_bound + || TREE_CODE (low_bound) != INTEGER_CST + || !up_bound + || TREE_CODE (up_bound) != INTEGER_CST + || !el_sz + || TREE_CODE (el_sz) != INTEGER_CST) + return; + + idx = mem_ref_offset (t); + idx = double_int_sdiv (idx, tree_to_double_int (el_sz), TRUNC_DIV_EXPR); + if (double_int_scmp (idx, double_int_zero) < 0) + { + warning_at (location, OPT_Warray_bounds, + "array subscript is below array bounds"); + TREE_NO_WARNING (t) = 1; + } + else if (double_int_scmp (idx, + double_int_add + (double_int_add + (tree_to_double_int (up_bound), + double_int_neg + (tree_to_double_int (low_bound))), + double_int_one)) > 0) + { + warning_at (location, OPT_Warray_bounds, + "array subscript is above array bounds"); + TREE_NO_WARNING (t) = 1; + } + } } /* walk_tree() callback that checks if *TP is @@ -5105,7 +5419,7 @@ check_array_bounds (tree *tp, int *walk_subtree, void *data) if (TREE_CODE (t) == ARRAY_REF) check_array_ref (location, t, false /*ignore_off_by_one*/); - if (TREE_CODE (t) == INDIRECT_REF + if (TREE_CODE (t) == MEM_REF || (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))) search_for_addr_array (TREE_OPERAND (t, 0), location); @@ -5321,6 +5635,21 @@ vrp_initialize (void) } } +/* Return the singleton value-range for NAME or NAME. */ + +static inline tree +vrp_valueize (tree name) +{ + if (TREE_CODE (name) == SSA_NAME) + { + value_range_t *vr = get_value_range (name); + if (vr->type == VR_RANGE + && (vr->min == vr->max + || operand_equal_p (vr->min, vr->max, 0))) + return vr->min; + } + return name; +} /* Visit assignment STMT. If it produces an interesting range, record the SSA name in *OUTPUT_P. */ @@ -5342,20 +5671,18 @@ vrp_visit_assignment_or_call (gimple stmt, tree *output_p) && 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) + /* Try folding the statement to a constant first. */ + tree tem = gimple_fold_stmt_to_constant (stmt, vrp_valueize); + if (tem && !is_overflow_infinity (tem)) + set_value_range (&new_vr, VR_RANGE, tem, tem, NULL); + /* Then dispatch to value-range extracting functions. */ + else if (code == GIMPLE_CALL) extract_range_basic (&new_vr, stmt); 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; @@ -5953,7 +6280,7 @@ find_case_label_range (gimple stmt, tree min, tree max, size_t *min_idx, for (k = i + 1; k <= j; ++k) { low = CASE_LOW (gimple_switch_label (stmt, k)); - if (!integer_onep (int_const_binop (MINUS_EXPR, low, high, 0))) + if (!integer_onep (int_const_binop (MINUS_EXPR, low, high))) { take_default = true; break; @@ -6080,7 +6407,6 @@ vrp_visit_stmt (gimple stmt, edge *taken_edge_p, tree *output_p) /* In general, assignments with virtual operands are not useful for deriving ranges, with the obvious exception of calls to builtin functions. */ - if ((is_gimple_call (stmt) && gimple_call_fndecl (stmt) != NULL_TREE && DECL_IS_BUILTIN (gimple_call_fndecl (stmt))) @@ -6259,8 +6585,7 @@ vrp_visit_phi_node (gimple phi) 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; - - copy_value_range (&vr_result, lhs_vr); + struct loop *l; if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -6333,67 +6658,81 @@ vrp_visit_phi_node (gimple phi) 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 - && edges <= old_edges) - { - if (!POINTER_TYPE_P (TREE_TYPE (lhs))) - { - int cmp_min = compare_values (lhs_vr->min, vr_result.min); - int cmp_max = compare_values (lhs_vr->max, vr_result.max); - - /* If the new minimum is smaller or larger than the previous - one, go all the way to -INF. In the first case, to avoid - iterating millions of times to reach -INF, and in the - other case to avoid infinite bouncing between different - minimums. */ - if (cmp_min > 0 || cmp_min < 0) - { - /* 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)) - || !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 = - negative_overflow_infinity (TREE_TYPE (vr_result.min)); - else - goto varying; - } - - /* Similarly, if the new maximum is smaller or larger than - the previous one, go all the way to +INF. */ - if (cmp_max < 0 || cmp_max > 0) - { - /* 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)) - || !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 = - positive_overflow_infinity (TREE_TYPE (vr_result.max)); - else - goto varying; - } - } + if (edges > 0 + && gimple_phi_num_args (phi) > 1 + && edges == old_edges) + { + int cmp_min = compare_values (lhs_vr->min, vr_result.min); + int cmp_max = compare_values (lhs_vr->max, vr_result.max); + + /* For non VR_RANGE or for pointers fall back to varying if + the range changed. */ + if ((lhs_vr->type != VR_RANGE || vr_result.type != VR_RANGE + || POINTER_TYPE_P (TREE_TYPE (lhs))) + && (cmp_min != 0 || cmp_max != 0)) + goto varying; + + /* If the new minimum is smaller or larger than the previous + one, go all the way to -INF. In the first case, to avoid + iterating millions of times to reach -INF, and in the + other case to avoid infinite bouncing between different + minimums. */ + if (cmp_min > 0 || cmp_min < 0) + { + 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 = + negative_overflow_infinity (TREE_TYPE (vr_result.min)); + } + + /* Similarly, if the new maximum is smaller or larger than + the previous one, go all the way to +INF. */ + if (cmp_max < 0 || cmp_max > 0) + { + 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 = + positive_overflow_infinity (TREE_TYPE (vr_result.max)); + } + + /* If we dropped either bound to +-INF then if this is a loop + PHI node SCEV may known more about its value-range. */ + if ((cmp_min > 0 || cmp_min < 0 + || cmp_max < 0 || cmp_max > 0) + && current_loops + && (l = loop_containing_stmt (phi)) + && l->header == gimple_bb (phi)) + adjust_range_with_scev (&vr_result, l, phi, lhs); + + /* 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 end up with vr_result.min > vr_result.max. */ + if ((vrp_val_is_max (vr_result.max) + && vrp_val_is_min (vr_result.min)) + || compare_values (vr_result.min, + vr_result.max) > 0) + goto varying; } /* 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; @@ -6590,7 +6929,7 @@ simplify_div_or_mod_using_ranges (gimple stmt) if (rhs_code == TRUNC_DIV_EXPR) { - t = build_int_cst (NULL_TREE, tree_log2 (op1)); + t = build_int_cst (integer_type_node, tree_log2 (op1)); gimple_assign_set_rhs_code (stmt, RSHIFT_EXPR); gimple_assign_set_rhs1 (stmt, op0); gimple_assign_set_rhs2 (stmt, t); @@ -6598,7 +6937,7 @@ simplify_div_or_mod_using_ranges (gimple stmt) else { t = build_int_cst (TREE_TYPE (op1), 1); - t = int_const_binop (MINUS_EXPR, op1, t, 0); + t = int_const_binop (MINUS_EXPR, op1, t); t = fold_convert (TREE_TYPE (op0), t); gimple_assign_set_rhs_code (stmt, BIT_AND_EXPR); @@ -6678,6 +7017,85 @@ simplify_abs_using_ranges (gimple stmt) return false; } +/* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR. + If all the bits that are being cleared by & are already + known to be zero from VR, or all the bits that are being + set by | are already known to be one from VR, the bit + operation is redundant. */ + +static bool +simplify_bit_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt) +{ + tree op0 = gimple_assign_rhs1 (stmt); + tree op1 = gimple_assign_rhs2 (stmt); + tree op = NULL_TREE; + value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; + value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; + double_int may_be_nonzero0, may_be_nonzero1; + double_int must_be_nonzero0, must_be_nonzero1; + double_int mask; + + if (TREE_CODE (op0) == SSA_NAME) + vr0 = *(get_value_range (op0)); + else if (is_gimple_min_invariant (op0)) + set_value_range_to_value (&vr0, op0, NULL); + else + return false; + + if (TREE_CODE (op1) == SSA_NAME) + vr1 = *(get_value_range (op1)); + else if (is_gimple_min_invariant (op1)) + set_value_range_to_value (&vr1, op1, NULL); + else + return false; + + if (!zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0, &must_be_nonzero0)) + return false; + if (!zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1, &must_be_nonzero1)) + return false; + + switch (gimple_assign_rhs_code (stmt)) + { + case BIT_AND_EXPR: + mask = double_int_and_not (may_be_nonzero0, must_be_nonzero1); + if (double_int_zero_p (mask)) + { + op = op0; + break; + } + mask = double_int_and_not (may_be_nonzero1, must_be_nonzero0); + if (double_int_zero_p (mask)) + { + op = op1; + break; + } + break; + case BIT_IOR_EXPR: + mask = double_int_and_not (may_be_nonzero0, must_be_nonzero1); + if (double_int_zero_p (mask)) + { + op = op1; + break; + } + mask = double_int_and_not (may_be_nonzero1, must_be_nonzero0); + if (double_int_zero_p (mask)) + { + op = op0; + break; + } + break; + default: + gcc_unreachable (); + } + + if (op == NULL_TREE) + return false; + + gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op, NULL); + update_stmt (gsi_stmt (*gsi)); + return true; +} + /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has a known value range VR. @@ -6963,6 +7381,15 @@ simplify_stmt_using_ranges (gimple_stmt_iterator *gsi) return simplify_abs_using_ranges (stmt); break; + case BIT_AND_EXPR: + case BIT_IOR_EXPR: + /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR + if all the bits being cleared are already cleared or + all the bits being set are already set. */ + if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))) + return simplify_bit_ops_using_ranges (gsi, stmt); + break; + default: break; } @@ -7115,7 +7542,7 @@ identify_jump_threads (void) /* Do not thread across edges we are about to remove. Just marking them as EDGE_DFS_BACK will do. */ - for (i = 0; VEC_iterate (edge, to_remove_edges, i, e); ++i) + FOR_EACH_VEC_ELT (edge, to_remove_edges, i, e) e->flags |= EDGE_DFS_BACK; /* Allocate our unwinder stack to unwind any temporary equivalences @@ -7148,23 +7575,25 @@ identify_jump_threads (void) may be some value in handling SWITCH_EXPR here, I doubt it's terribly important. */ last = gsi_stmt (gsi_last_bb (bb)); - if (gimple_code (last) != GIMPLE_COND) - continue; - /* We're basically looking for any kind of conditional with - integral type arguments. */ - if (TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME - && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last))) - && (TREE_CODE (gimple_cond_rhs (last)) == SSA_NAME - || is_gimple_min_invariant (gimple_cond_rhs (last))) - && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_rhs (last)))) + /* We're basically looking for a switch or any kind of conditional with + integral or pointer type arguments. Note the type of the second + argument will be the same as the first argument, so no need to + check it explicitly. */ + if (gimple_code (last) == GIMPLE_SWITCH + || (gimple_code (last) == GIMPLE_COND + && TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME + && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last))) + || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (last)))) + && (TREE_CODE (gimple_cond_rhs (last)) == SSA_NAME + || is_gimple_min_invariant (gimple_cond_rhs (last))))) { edge_iterator ei; /* We've got a block with multiple predecessors and multiple - successors which also ends in a suitable conditional. For - each predecessor, see if we can thread it to a specific - successor. */ + successors which also ends in a suitable conditional or + switch statement. For each predecessor, see if we can thread + it to a specific successor. */ FOR_EACH_EDGE (e, ei, bb->preds) { /* Do not thread across back edges or abnormal edges @@ -7203,8 +7632,7 @@ static void vrp_finalize (void) { size_t i; - prop_value_t *single_val_range; - bool do_value_subst_p; + unsigned num = num_ssa_names; if (dump_file) { @@ -7213,31 +7641,8 @@ vrp_finalize (void) fprintf (dump_file, "\n"); } - /* We may have ended with ranges that have exactly one value. Those - values can be substituted as any other const propagated - value using substitute_and_fold. */ - single_val_range = XCNEWVEC (prop_value_t, num_ssa_names); - - do_value_subst_p = false; - 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 - && is_gimple_min_invariant (vr_value[i]->min)) - { - single_val_range[i].value = vr_value[i]->min; - do_value_subst_p = true; - } - - if (!do_value_subst_p) - { - /* We found no single-valued ranges, don't waste time trying to - do single value substitution in substitute_and_fold. */ - free (single_val_range); - single_val_range = NULL; - } - - substitute_and_fold (single_val_range, vrp_fold_stmt); + substitute_and_fold (op_with_constant_singleton_value_range, + vrp_fold_stmt, false); if (warn_array_bounds) check_all_array_refs (); @@ -7247,14 +7652,13 @@ vrp_finalize (void) identify_jump_threads (); /* Free allocated memory. */ - for (i = 0; i < num_ssa_names; i++) + for (i = 0; i < num; i++) if (vr_value[i]) { BITMAP_FREE (vr_value[i]->equiv); free (vr_value[i]); } - free (single_val_range); free (vr_value); free (vr_phi_edge_counts); @@ -7320,6 +7724,12 @@ execute_vrp (void) rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); scev_initialize (); + /* Estimate number of iterations - but do not use undefined behavior + for this. We can't do this lazily as other functions may compute + this using undefined behavior. */ + free_numbers_of_iterations_estimates (); + estimate_numbers_of_iterations (false); + insert_range_assertions (); to_remove_edges = VEC_alloc (edge, heap, 10); @@ -7346,10 +7756,10 @@ execute_vrp (void) /* Remove dead edges from SWITCH_EXPR optimization. This leaves the CFG in a broken state and requires a cfg_cleanup run. */ - for (i = 0; VEC_iterate (edge, to_remove_edges, i, e); ++i) + FOR_EACH_VEC_ELT (edge, to_remove_edges, i, e) remove_edge (e); /* Update SWITCH_EXPR case label vector. */ - for (i = 0; VEC_iterate (switch_update, to_update_switch_stmts, i, su); ++i) + FOR_EACH_VEC_ELT (switch_update, to_update_switch_stmts, i, su) { size_t j; size_t n = TREE_VEC_LENGTH (su->vec); @@ -7399,9 +7809,10 @@ struct gimple_opt_pass pass_vrp = 0, /* properties_destroyed */ 0, /* todo_flags_start */ TODO_cleanup_cfg - | TODO_ggc_collect + | TODO_update_ssa | TODO_verify_ssa + | TODO_verify_flow | TODO_dump_func - | TODO_update_ssa /* todo_flags_finish */ + | TODO_ggc_collect /* todo_flags_finish */ } };