Mercurial > hg > CbC > CbC_gcc
diff gcc/tree-vrp.c @ 145:1830386684a0
gcc-9.2.0
| author | anatofuz |
|---|---|
| date | Thu, 13 Feb 2020 11:34:05 +0900 |
| parents | 84e7813d76e9 |
| children |
line wrap: on
line diff
--- a/gcc/tree-vrp.c Thu Oct 25 07:37:49 2018 +0900 +++ b/gcc/tree-vrp.c Thu Feb 13 11:34:05 2020 +0900 @@ -1,5 +1,5 @@ /* Support routines for Value Range Propagation (VRP). - Copyright (C) 2005-2018 Free Software Foundation, Inc. + Copyright (C) 2005-2020 Free Software Foundation, Inc. Contributed by Diego Novillo <dnovillo@redhat.com>. This file is part of GCC. @@ -59,7 +59,6 @@ #include "omp-general.h" #include "target.h" #include "case-cfn-macros.h" -#include "params.h" #include "alloc-pool.h" #include "domwalk.h" #include "tree-cfgcleanup.h" @@ -67,22 +66,17 @@ #include "attribs.h" #include "vr-values.h" #include "builtins.h" -#include "wide-int-range.h" +#include "range-op.h" /* Set of SSA names found live during the RPO traversal of the function for still active basic-blocks. */ static sbitmap *live; -/* Initialize value_range. */ - void -value_range::set (enum value_range_kind kind, tree min, tree max, - bitmap equiv) +value_range_equiv::set_equiv (bitmap equiv) { - m_kind = kind; - m_min = min; - m_max = max; - + if (undefined_p () || varying_p ()) + equiv = NULL; /* Since updating the equivalence set involves deep copying the bitmaps, only do it if absolutely necessary. @@ -99,23 +93,40 @@ else bitmap_clear (m_equiv); } +} + +/* Initialize value_range. */ + +void +value_range_equiv::set (tree min, tree max, bitmap equiv, + value_range_kind kind) +{ + value_range::set (min, max, kind); + set_equiv (equiv); if (flag_checking) check (); } -value_range::value_range (value_range_kind kind, tree min, tree max, - bitmap equiv) +value_range_equiv::value_range_equiv (tree min, tree max, bitmap equiv, + value_range_kind kind) +{ + m_equiv = NULL; + set (min, max, equiv, kind); +} + +value_range_equiv::value_range_equiv (const value_range &other) { m_equiv = NULL; - set (kind, min, max, equiv); + set (other.min(), other.max (), NULL, other.kind ()); } -/* Like above, but keep the equivalences intact. */ +/* Like set, but keep the equivalences in place. */ void -value_range::update (value_range_kind kind, tree min, tree max) +value_range_equiv::update (tree min, tree max, value_range_kind kind) { - set (kind, min, max, m_equiv); + set (min, max, + (kind != VR_UNDEFINED && kind != VR_VARYING) ? m_equiv : NULL, kind); } /* Copy value_range in FROM into THIS while avoiding bitmap sharing. @@ -125,139 +136,71 @@ object. Use the constructors for initialization. */ void -value_range::deep_copy (const value_range *from) +value_range_equiv::deep_copy (const value_range_equiv *from) { - set (from->m_kind, from->min (), from->max (), from->m_equiv); + set (from->min (), from->max (), from->m_equiv, from->m_kind); } -/* Check the validity of the range. */ - void -value_range::check () +value_range_equiv::move (value_range_equiv *from) { + set (from->min (), from->max (), NULL, from->m_kind); + m_equiv = from->m_equiv; + from->m_equiv = NULL; +} + +void +value_range_equiv::check () +{ + value_range::check (); switch (m_kind) { - case VR_RANGE: - case VR_ANTI_RANGE: - { - int cmp; - - gcc_assert (m_min && m_max); - - gcc_assert (!TREE_OVERFLOW_P (m_min) && !TREE_OVERFLOW_P (m_max)); - - /* Creating ~[-MIN, +MAX] is stupid because that would be - the empty set. */ - if (INTEGRAL_TYPE_P (TREE_TYPE (m_min)) && m_kind == VR_ANTI_RANGE) - gcc_assert (!vrp_val_is_min (m_min) || !vrp_val_is_max (m_max)); - - cmp = compare_values (m_min, m_max); - gcc_assert (cmp == 0 || cmp == -1 || cmp == -2); - break; - } case VR_UNDEFINED: case VR_VARYING: - gcc_assert (!m_min && !m_max); gcc_assert (!m_equiv || bitmap_empty_p (m_equiv)); - break; - default: - gcc_unreachable (); + default:; } } +/* Return true if the bitmaps B1 and B2 are equal. */ + +static 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))); +} + /* Returns TRUE if THIS == OTHER. Ignores the equivalence bitmap if IGNORE_EQUIVS is TRUE. */ bool -value_range::equal_p (const value_range &other, bool ignore_equivs) const +value_range_equiv::equal_p (const value_range_equiv &other, + bool ignore_equivs) const { - return (m_kind == other.m_kind - && vrp_operand_equal_p (m_min, other.m_min) - && vrp_operand_equal_p (m_max, other.m_max) + return (value_range::equal_p (other) && (ignore_equivs || vrp_bitmap_equal_p (m_equiv, other.m_equiv))); } -/* Return equality while ignoring equivalence bitmap. */ - -bool -value_range::ignore_equivs_equal_p (const value_range &other) const -{ - return equal_p (other, /*ignore_equivs=*/true); -} - -bool -value_range::operator== (const value_range &other) const -{ - return equal_p (other, /*ignore_equivs=*/false); -} - -bool -value_range::operator!= (const value_range &other) const +void +value_range_equiv::set_undefined () { - return !(*this == other); -} - -/* Return TRUE if this is a symbolic range. */ - -bool -value_range::symbolic_p () const -{ - return (!varying_p () - && !undefined_p () - && (!is_gimple_min_invariant (m_min) - || !is_gimple_min_invariant (m_max))); -} - -/* NOTE: This is not the inverse of symbolic_p because the range - could also be varying or undefined. Ideally they should be inverse - of each other, with varying only applying to symbolics. Varying of - constants would be represented as [-MIN, +MAX]. */ - -bool -value_range::constant_p () const -{ - return (!varying_p () - && !undefined_p () - && TREE_CODE (m_min) == INTEGER_CST - && TREE_CODE (m_max) == INTEGER_CST); + set (NULL, NULL, NULL, VR_UNDEFINED); } void -value_range::set_undefined () +value_range_equiv::set_varying (tree type) { + value_range::set_varying (type); equiv_clear (); - *this = value_range (VR_UNDEFINED, NULL, NULL, NULL); } void -value_range::set_varying () -{ - equiv_clear (); - *this = value_range (VR_VARYING, NULL, NULL, NULL); -} - -/* Return TRUE if it is possible that range contains VAL. */ - -bool -value_range::may_contain_p (tree val) const -{ - if (varying_p ()) - return true; - - if (undefined_p ()) - return true; - - if (m_kind == VR_ANTI_RANGE) - { - int res = value_inside_range (val, m_min, m_max); - return res == 0 || res == -2; - } - return value_inside_range (val, m_min, m_max) != 0; -} - -void -value_range::equiv_clear () +value_range_equiv::equiv_clear () { if (m_equiv) bitmap_clear (m_equiv); @@ -271,9 +214,9 @@ turned on/off. */ void -value_range::equiv_add (const_tree var, - const value_range *var_vr, - bitmap_obstack *obstack) +value_range_equiv::equiv_add (const_tree var, + const value_range_equiv *var_vr, + bitmap_obstack *obstack) { if (!m_equiv) m_equiv = BITMAP_ALLOC (obstack); @@ -283,91 +226,54 @@ bitmap_ior_into (m_equiv, var_vr->m_equiv); } -/* If range is a singleton, place it in RESULT and return TRUE. - Note: A singleton can be any gimple invariant, not just constants. - So, [&x, &x] counts as a singleton. */ - -bool -value_range::singleton_p (tree *result) const +void +value_range_equiv::dump (FILE *file) const { - if (m_kind == VR_RANGE - && vrp_operand_equal_p (m_min, m_max) - && is_gimple_min_invariant (m_min)) - { - if (result) - *result = m_min; - return true; - } - return false; -} - -tree -value_range::type () const -{ - /* Types are only valid for VR_RANGE and VR_ANTI_RANGE, which are - known to have non-zero min/max. */ - gcc_assert (m_min); - return TREE_TYPE (m_min); -} - -/* Dump value range to FILE. */ - -void -value_range::dump (FILE *file) const -{ - if (undefined_p ()) - fprintf (file, "UNDEFINED"); - else if (m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE) + value_range::dump (file); + if ((m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE) + && m_equiv) { - tree type = TREE_TYPE (min ()); - - fprintf (file, "%s[", (m_kind == VR_ANTI_RANGE) ? "~" : ""); - - if (INTEGRAL_TYPE_P (type) - && !TYPE_UNSIGNED (type) - && vrp_val_is_min (min ())) - fprintf (file, "-INF"); - else - print_generic_expr (file, min ()); - - fprintf (file, ", "); - - if (INTEGRAL_TYPE_P (type) - && vrp_val_is_max (max ())) - fprintf (file, "+INF"); - else - print_generic_expr (file, max ()); - - fprintf (file, "]"); - - if (m_equiv) + bitmap_iterator bi; + unsigned i, c = 0; + + fprintf (file, " EQUIVALENCES: { "); + + EXECUTE_IF_SET_IN_BITMAP (m_equiv, 0, i, bi) { - bitmap_iterator bi; - unsigned i, c = 0; - - fprintf (file, " EQUIVALENCES: { "); - - EXECUTE_IF_SET_IN_BITMAP (m_equiv, 0, i, bi) - { - print_generic_expr (file, ssa_name (i)); - fprintf (file, " "); - c++; - } - - fprintf (file, "} (%u elements)", c); + print_generic_expr (file, ssa_name (i)); + fprintf (file, " "); + c++; } + + fprintf (file, "} (%u elements)", c); } - else if (varying_p ()) - fprintf (file, "VARYING"); - else - fprintf (file, "INVALID RANGE"); } void -value_range::dump () const +value_range_equiv::dump () const +{ + dump (stderr); +} + +void +dump_value_range (FILE *file, const value_range_equiv *vr) { - dump_value_range (stderr, this); - fprintf (stderr, "\n"); + if (!vr) + fprintf (file, "[]"); + else + vr->dump (file); +} + +DEBUG_FUNCTION void +debug (const value_range_equiv *vr) +{ + dump_value_range (stderr, vr); +} + +DEBUG_FUNCTION void +debug (const value_range_equiv &vr) +{ + dump_value_range (stderr, &vr); } /* Return true if the SSA name NAME is live on the edge E. */ @@ -418,53 +324,6 @@ ASSERT_EXPRs for SSA name N_I should be inserted. */ static assert_locus **asserts_for; -/* Return the maximum value for TYPE. */ - -tree -vrp_val_max (const_tree type) -{ - if (!INTEGRAL_TYPE_P (type)) - return NULL_TREE; - - return TYPE_MAX_VALUE (type); -} - -/* Return the minimum value for TYPE. */ - -tree -vrp_val_min (const_tree type) -{ - if (!INTEGRAL_TYPE_P (type)) - return NULL_TREE; - - return TYPE_MIN_VALUE (type); -} - -/* Return whether VAL is equal to the maximum value of its type. - 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. */ - -bool -vrp_val_is_max (const_tree val) -{ - tree type_max = vrp_val_max (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. */ - -bool -vrp_val_is_min (const_tree val) -{ - tree type_min = vrp_val_min (TREE_TYPE (val)); - return (val == type_min - || (type_min != NULL_TREE - && operand_equal_p (val, type_min, 0))); -} - /* VR_TYPE describes a range with mininum value *MIN and maximum value *MAX. Restrict the range to the set of values that have no bits set outside NONZERO_BITS. Update *MIN and *MAX and @@ -537,221 +396,13 @@ return vr_type; } -/* Set value range VR to VR_UNDEFINED. */ - -static inline void -set_value_range_to_undefined (value_range *vr) -{ - vr->set_undefined (); -} - -/* Set value range VR to VR_VARYING. */ - void -set_value_range_to_varying (value_range *vr) -{ - vr->set_varying (); -} - -/* Set value range VR to {T, MIN, MAX, EQUIV}. */ - -void -set_value_range (value_range *vr, enum value_range_kind kind, - tree min, tree max, bitmap equiv) -{ - *vr = value_range (kind, min, max, equiv); -} - - -/* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}. - This means adjusting VRTYPE, MIN and MAX representing the case of a - wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX] - as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges. - In corner cases where MAX+1 or MIN-1 wraps this will fall back - to varying. - This routine exists to ease canonicalization in the case where we - extract ranges from var + CST op limit. */ - -void -value_range::set_and_canonicalize (enum value_range_kind kind, - tree min, tree max, bitmap equiv) +value_range_equiv::set (tree val) { - /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */ - if (kind == VR_UNDEFINED) - { - set_undefined (); - return; - } - else if (kind == VR_VARYING) - { - set_varying (); - return; - } - - /* Nothing to canonicalize for symbolic ranges. */ - if (TREE_CODE (min) != INTEGER_CST - || TREE_CODE (max) != INTEGER_CST) - { - set_value_range (this, kind, min, max, equiv); - return; - } - - /* Wrong order for min and max, to swap them and the VR type we need - to adjust them. */ - if (tree_int_cst_lt (max, min)) - { - tree one, tmp; - - /* For one bit precision if max < min, then the swapped - range covers all values, so for VR_RANGE it is varying and - for VR_ANTI_RANGE empty range, so drop to varying as well. */ - if (TYPE_PRECISION (TREE_TYPE (min)) == 1) - { - set_varying (); - return; - } - - one = build_int_cst (TREE_TYPE (min), 1); - 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 - that again. But this represents an empty value range, so drop - to varying in this case. */ - if (tree_int_cst_lt (max, min)) - { - set_varying (); - return; - } - - kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE; - } - - /* Anti-ranges that can be represented as ranges should be so. */ - if (kind == VR_ANTI_RANGE) - { - /* For -fstrict-enums we may receive out-of-range ranges so consider - values < -INF and values > INF as -INF/INF as well. */ - tree type = TREE_TYPE (min); - bool is_min = (INTEGRAL_TYPE_P (type) - && tree_int_cst_compare (min, TYPE_MIN_VALUE (type)) <= 0); - bool is_max = (INTEGRAL_TYPE_P (type) - && tree_int_cst_compare (max, TYPE_MAX_VALUE (type)) >= 0); - - if (is_min && is_max) - { - /* We cannot deal with empty ranges, drop to varying. - ??? This could be VR_UNDEFINED instead. */ - set_varying (); - return; - } - else if (TYPE_PRECISION (TREE_TYPE (min)) == 1 - && (is_min || is_max)) - { - /* Non-empty boolean ranges can always be represented - as a singleton range. */ - if (is_min) - min = max = vrp_val_max (TREE_TYPE (min)); - else - min = max = vrp_val_min (TREE_TYPE (min)); - kind = VR_RANGE; - } - else if (is_min - /* As a special exception preserve non-null ranges. */ - && !(TYPE_UNSIGNED (TREE_TYPE (min)) - && integer_zerop (max))) - { - tree one = build_int_cst (TREE_TYPE (max), 1); - min = int_const_binop (PLUS_EXPR, max, one); - max = vrp_val_max (TREE_TYPE (max)); - kind = VR_RANGE; - } - else if (is_max) - { - tree one = build_int_cst (TREE_TYPE (min), 1); - max = int_const_binop (MINUS_EXPR, min, one); - min = vrp_val_min (TREE_TYPE (min)); - kind = VR_RANGE; - } - } - - /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky - to make sure VRP iteration terminates, otherwise we can get into - oscillations. */ - - set_value_range (this, kind, min, max, 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. */ - -void -set_value_range_to_value (value_range *vr, tree val, bitmap equiv) -{ - gcc_assert (is_gimple_min_invariant (val)); + gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val)); if (TREE_OVERFLOW_P (val)) val = drop_tree_overflow (val); - set_value_range (vr, VR_RANGE, val, val, equiv); -} - -/* Set value range VR to a non-NULL range of type TYPE. */ - -void -set_value_range_to_nonnull (value_range *vr, tree type) -{ - tree zero = build_int_cst (type, 0); - vr->update (VR_ANTI_RANGE, zero, zero); -} - - -/* Set value range VR to a NULL range of type TYPE. */ - -void -set_value_range_to_null (value_range *vr, tree type) -{ - set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv ()); -} - -/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ - -bool -vrp_operand_equal_p (const_tree val1, const_tree val2) -{ - if (val1 == val2) - return true; - if (!val1 || !val2 || !operand_equal_p (val1, val2, 0)) - return false; - return true; -} - -/* Return true, if the bitmaps B1 and B2 are equal. */ - -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))); -} - -/* Return true if VR is [0, 0]. */ - -static inline bool -range_is_null (const value_range *vr) -{ - return vr->null_p (); -} - -static inline bool -range_is_nonnull (const value_range *vr) -{ - return (vr->kind () == VR_ANTI_RANGE - && vr->min () == vr->max () - && integer_zerop (vr->min ())); + set (val, val); } /* Return true if max and min of VR are INTEGER_CST. It's not necessary @@ -760,18 +411,7 @@ bool range_int_cst_p (const value_range *vr) { - return (vr->kind () == VR_RANGE - && TREE_CODE (vr->min ()) == INTEGER_CST - && TREE_CODE (vr->max ()) == INTEGER_CST); -} - -/* Return true if VR is a INTEGER_CST singleton. */ - -bool -range_int_cst_singleton_p (const value_range *vr) -{ - return (range_int_cst_p (vr) - && tree_int_cst_equal (vr->min (), vr->max ())); + return (vr->kind () == VR_RANGE && range_has_numeric_bounds_p (vr)); } /* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE @@ -857,22 +497,17 @@ /* LT is folded faster than GE and others. Inline the common case. */ if (TREE_CODE (val) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST) return tree_int_cst_lt (val, val2); + else if (TREE_CODE (val) == SSA_NAME && TREE_CODE (val2) == SSA_NAME) + return val == val2 ? 0 : -2; else { - 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 - || TREE_CODE (tcmp) != INTEGER_CST) + int cmp = compare_values (val, val2); + if (cmp == -1) + return 1; + else if (cmp == 0 || cmp == 1) + return 0; + else return -2; - - if (!integer_zerop (tcmp)) - return 1; } return 0; @@ -906,8 +541,8 @@ /* 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 (!useless_type_conversion_p (TREE_TYPE (val1), TREE_TYPE (val2))) + val2 = fold_convert (TREE_TYPE (val1), val2); const bool overflow_undefined = INTEGRAL_TYPE_P (TREE_TYPE (val1)) @@ -1015,32 +650,43 @@ } else { - tree t; + if (TREE_CODE (val1) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST) + { + /* We cannot compare overflowed values. */ + if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2)) + return -2; + + return tree_int_cst_compare (val1, val2); + } /* First see if VAL1 and VAL2 are not the same. */ - if (val1 == val2 || operand_equal_p (val1, val2, 0)) + if (operand_equal_p (val1, val2, 0)) return 0; + fold_defer_overflow_warnings (); + /* If VAL1 is a lower address than VAL2, return -1. */ - if (operand_less_p (val1, val2) == 1) - return -1; + tree t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val1, val2); + if (t && integer_onep (t)) + { + fold_undefer_and_ignore_overflow_warnings (); + return -1; + } /* If VAL1 is a higher address than VAL2, return +1. */ - if (operand_less_p (val2, val1) == 1) - return 1; - - /* If VAL1 is different than VAL2, return +2. - For integer constants we either have already returned -1 or 1 - or they are equivalent. We still might succeed in proving - something about non-trivial operands. */ - if (TREE_CODE (val1) != INTEGER_CST - || TREE_CODE (val2) != INTEGER_CST) + t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val2, val1); + if (t && integer_onep (t)) { - t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2); - if (t && integer_onep (t)) - return 2; + fold_undefer_and_ignore_overflow_warnings (); + return 1; } + /* If VAL1 is different than VAL2, return +2. */ + t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2); + fold_undefer_and_ignore_overflow_warnings (); + if (t && integer_onep (t)) + return 2; + return -2; } } @@ -1054,191 +700,6 @@ return compare_values_warnv (val1, val2, &sop); } - -/* Return 1 if VAL is inside value range MIN <= VAL <= MAX, - 0 if VAL is not inside [MIN, MAX], - -2 if we cannot tell either way. - - Benchmark compile/20001226-1.c compilation time after changing this - function. */ - -int -value_inside_range (tree val, tree min, tree max) -{ - int cmp1, cmp2; - - cmp1 = operand_less_p (val, min); - if (cmp1 == -2) - return -2; - if (cmp1 == 1) - return 0; - - cmp2 = operand_less_p (max, val); - if (cmp2 == -2) - return -2; - - return !cmp2; -} - - -/* Return TRUE if *VR includes the value zero. */ - -bool -range_includes_zero_p (const value_range *vr) -{ - if (vr->varying_p () || vr->undefined_p ()) - return true; - tree zero = build_int_cst (vr->type (), 0); - return vr->may_contain_p (zero); -} - -/* If *VR has a value range that is a single constant value return that, - otherwise return NULL_TREE. - - ?? This actually returns TRUE for [&x, &x], so perhaps "constant" - is not the best name. */ - -tree -value_range_constant_singleton (const value_range *vr) -{ - tree result = NULL; - if (vr->singleton_p (&result)) - return result; - return NULL; -} - -/* Value range wrapper for wide_int_range_set_zero_nonzero_bits. - - Compute MAY_BE_NONZERO and MUST_BE_NONZERO bit masks for range in VR. - - Return TRUE if VR was a constant range and we were able to compute - the bit masks. */ - -bool -vrp_set_zero_nonzero_bits (const tree expr_type, - const value_range *vr, - wide_int *may_be_nonzero, - wide_int *must_be_nonzero) -{ - if (!range_int_cst_p (vr)) - { - *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type)); - *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type)); - return false; - } - wide_int_range_set_zero_nonzero_bits (TYPE_SIGN (expr_type), - wi::to_wide (vr->min ()), - wi::to_wide (vr->max ()), - *may_be_nonzero, *must_be_nonzero); - return true; -} - -/* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR - so that *VR0 U *VR1 == *AR. Returns true if that is possible, - false otherwise. If *AR can be represented with a single range - *VR1 will be VR_UNDEFINED. */ - -static bool -ranges_from_anti_range (const value_range *ar, - value_range *vr0, value_range *vr1) -{ - tree type = ar->type (); - - vr0->set_undefined (); - vr1->set_undefined (); - - /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U - [A+1, +INF]. Not sure if this helps in practice, though. */ - - if (ar->kind () != VR_ANTI_RANGE - || TREE_CODE (ar->min ()) != INTEGER_CST - || TREE_CODE (ar->max ()) != INTEGER_CST - || !vrp_val_min (type) - || !vrp_val_max (type)) - return false; - - if (!vrp_val_is_min (ar->min ())) - *vr0 = value_range (VR_RANGE, - vrp_val_min (type), - wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1)); - if (!vrp_val_is_max (ar->max ())) - *vr1 = value_range (VR_RANGE, - wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1), - vrp_val_max (type)); - if (vr0->undefined_p ()) - { - *vr0 = *vr1; - vr1->set_undefined (); - } - - return !vr0->undefined_p (); -} - -/* Extract the components of a value range into a pair of wide ints in - [WMIN, WMAX]. - - If the value range is anything but a VR_*RANGE of constants, the - resulting wide ints are set to [-MIN, +MAX] for the type. */ - -static void inline -extract_range_into_wide_ints (const value_range *vr, - signop sign, unsigned prec, - wide_int &wmin, wide_int &wmax) -{ - gcc_assert (vr->kind () != VR_ANTI_RANGE || vr->symbolic_p ()); - if (range_int_cst_p (vr)) - { - wmin = wi::to_wide (vr->min ()); - wmax = wi::to_wide (vr->max ()); - } - else - { - wmin = wi::min_value (prec, sign); - wmax = wi::max_value (prec, sign); - } -} - -/* Value range wrapper for wide_int_range_multiplicative_op: - - *VR = *VR0 .CODE. *VR1. */ - -static void -extract_range_from_multiplicative_op (value_range *vr, - enum tree_code code, - const value_range *vr0, - const value_range *vr1) -{ - gcc_assert (code == MULT_EXPR - || code == TRUNC_DIV_EXPR - || code == FLOOR_DIV_EXPR - || code == CEIL_DIV_EXPR - || code == EXACT_DIV_EXPR - || code == ROUND_DIV_EXPR - || code == RSHIFT_EXPR - || code == LSHIFT_EXPR); - gcc_assert (vr0->kind () == VR_RANGE - && vr0->kind () == vr1->kind ()); - - tree type = vr0->type (); - wide_int res_lb, res_ub; - wide_int vr0_lb = wi::to_wide (vr0->min ()); - wide_int vr0_ub = wi::to_wide (vr0->max ()); - wide_int vr1_lb = wi::to_wide (vr1->min ()); - wide_int vr1_ub = wi::to_wide (vr1->max ()); - bool overflow_undefined = TYPE_OVERFLOW_UNDEFINED (type); - unsigned prec = TYPE_PRECISION (type); - - if (wide_int_range_multiplicative_op (res_lb, res_ub, - code, TYPE_SIGN (type), prec, - vr0_lb, vr0_ub, vr1_lb, vr1_ub, - overflow_undefined)) - vr->set_and_canonicalize (VR_RANGE, - wide_int_to_tree (type, res_lb), - wide_int_to_tree (type, res_ub), NULL); - else - set_value_range_to_varying (vr); -} - /* If BOUND will include a symbolic bound, adjust it accordingly, otherwise leave it as is. @@ -1354,8 +815,7 @@ if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE)) { /* If the limits are swapped, we wrapped around and cover - the entire range. We have a similar check at the end of - extract_range_from_binary_expr_1. */ + the entire range. */ if (wi::gt_p (tmin, tmax, sgn)) kind = VR_VARYING; else @@ -1424,90 +884,71 @@ } } -/* Extract range information from a binary operation CODE based on - the ranges of each of its operands *VR0 and *VR1 with resulting - type EXPR_TYPE. The resulting range is stored in *VR. */ - -void -extract_range_from_binary_expr_1 (value_range *vr, - enum tree_code code, tree expr_type, - const value_range *vr0_, - const value_range *vr1_) +/* Fold two value range's of a POINTER_PLUS_EXPR into VR. */ + +static void +extract_range_from_pointer_plus_expr (value_range *vr, + enum tree_code code, + tree expr_type, + const value_range *vr0, + const value_range *vr1) { - signop sign = TYPE_SIGN (expr_type); - unsigned int prec = TYPE_PRECISION (expr_type); + gcc_checking_assert (POINTER_TYPE_P (expr_type) + && code == POINTER_PLUS_EXPR); + /* For pointer types, we are really only interested in asserting + whether the expression evaluates to non-NULL. + With -fno-delete-null-pointer-checks we need to be more + conservative. As some object might reside at address 0, + then some offset could be added to it and the same offset + subtracted again and the result would be NULL. + E.g. + static int a[12]; where &a[0] is NULL and + ptr = &a[6]; + ptr -= 6; + ptr will be NULL here, even when there is POINTER_PLUS_EXPR + where the first range doesn't include zero and the second one + doesn't either. As the second operand is sizetype (unsigned), + consider all ranges where the MSB could be set as possible + subtractions where the result might be NULL. */ + if ((!range_includes_zero_p (vr0) + || !range_includes_zero_p (vr1)) + && !TYPE_OVERFLOW_WRAPS (expr_type) + && (flag_delete_null_pointer_checks + || (range_int_cst_p (vr1) + && !tree_int_cst_sign_bit (vr1->max ())))) + vr->set_nonzero (expr_type); + else if (vr0->zero_p () && vr1->zero_p ()) + vr->set_zero (expr_type); + else + vr->set_varying (expr_type); +} + +/* Extract range information from a PLUS/MINUS_EXPR and store the + result in *VR. */ + +static void +extract_range_from_plus_minus_expr (value_range *vr, + enum tree_code code, + tree expr_type, + const value_range *vr0_, + const value_range *vr1_) +{ + gcc_checking_assert (code == PLUS_EXPR || code == MINUS_EXPR); + value_range vr0 = *vr0_, vr1 = *vr1_; value_range vrtem0, vrtem1; - enum value_range_kind type; - tree min = NULL_TREE, max = NULL_TREE; - int cmp; - - if (!INTEGRAL_TYPE_P (expr_type) - && !POINTER_TYPE_P (expr_type)) - { - set_value_range_to_varying (vr); - return; - } - - /* Not all binary expressions can be applied to ranges in a - meaningful way. Handle only arithmetic operations. */ - if (code != PLUS_EXPR - && code != MINUS_EXPR - && code != POINTER_PLUS_EXPR - && code != MULT_EXPR - && code != TRUNC_DIV_EXPR - && code != FLOOR_DIV_EXPR - && code != CEIL_DIV_EXPR - && code != EXACT_DIV_EXPR - && code != ROUND_DIV_EXPR - && code != TRUNC_MOD_EXPR - && code != RSHIFT_EXPR - && code != LSHIFT_EXPR - && code != MIN_EXPR - && code != MAX_EXPR - && code != BIT_AND_EXPR - && code != BIT_IOR_EXPR - && code != BIT_XOR_EXPR) - { - set_value_range_to_varying (vr); - return; - } - - /* If both ranges are UNDEFINED, so is the result. */ - if (vr0.undefined_p () && vr1.undefined_p ()) - { - set_value_range_to_undefined (vr); - return; - } - /* If one of the ranges is UNDEFINED drop it to VARYING for the following - code. At some point we may want to special-case operations that - have UNDEFINED result for all or some value-ranges of the not UNDEFINED - operand. */ - else if (vr0.undefined_p ()) - set_value_range_to_varying (&vr0); - else if (vr1.undefined_p ()) - set_value_range_to_varying (&vr1); - - /* We get imprecise results from ranges_from_anti_range when - code is EXACT_DIV_EXPR. We could mask out bits in the resulting - range, but then we also need to hack up vrp_union. It's just - easier to special case when vr0 is ~[0,0] for EXACT_DIV_EXPR. */ - if (code == EXACT_DIV_EXPR && range_is_nonnull (&vr0)) - { - set_value_range_to_nonnull (vr, expr_type); - return; - } /* Now canonicalize anti-ranges to ranges when they are not symbolic and express ~[] op X as ([]' op X) U ([]'' op X). */ if (vr0.kind () == VR_ANTI_RANGE && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1)) { - extract_range_from_binary_expr_1 (vr, code, expr_type, &vrtem0, vr1_); + extract_range_from_plus_minus_expr (vr, code, expr_type, &vrtem0, vr1_); if (!vrtem1.undefined_p ()) { value_range vrres; - extract_range_from_binary_expr_1 (&vrres, code, expr_type, &vrtem1, vr1_); + extract_range_from_plus_minus_expr (&vrres, code, expr_type, + &vrtem1, vr1_); vr->union_ (&vrres); } return; @@ -1516,408 +957,130 @@ if (vr1.kind () == VR_ANTI_RANGE && ranges_from_anti_range (&vr1, &vrtem0, &vrtem1)) { - extract_range_from_binary_expr_1 (vr, code, expr_type, vr0_, &vrtem0); + extract_range_from_plus_minus_expr (vr, code, expr_type, vr0_, &vrtem0); if (!vrtem1.undefined_p ()) { value_range vrres; - extract_range_from_binary_expr_1 (&vrres, code, expr_type, - vr0_, &vrtem1); + extract_range_from_plus_minus_expr (&vrres, code, expr_type, + vr0_, &vrtem1); vr->union_ (&vrres); } return; } - /* The type of the resulting value range defaults to VR0.TYPE. */ - type = vr0.kind (); - - /* Refuse to operate on VARYING ranges, ranges of different kinds - and symbolic ranges. As an exception, we allow BIT_{AND,IOR} - because we may be able to derive a useful range even if one of - the operands is VR_VARYING or symbolic range. Similarly for - divisions, MIN/MAX and PLUS/MINUS. - - TODO, we may be able to derive anti-ranges in some cases. */ - if (code != BIT_AND_EXPR - && code != BIT_IOR_EXPR - && code != TRUNC_DIV_EXPR - && code != FLOOR_DIV_EXPR - && code != CEIL_DIV_EXPR - && code != EXACT_DIV_EXPR - && code != ROUND_DIV_EXPR - && code != TRUNC_MOD_EXPR - && code != MIN_EXPR - && code != MAX_EXPR - && code != PLUS_EXPR - && code != MINUS_EXPR - && code != RSHIFT_EXPR - && code != POINTER_PLUS_EXPR - && (vr0.varying_p () - || vr1.varying_p () - || vr0.kind () != vr1.kind () - || vr0.symbolic_p () - || vr1.symbolic_p ())) - { - set_value_range_to_varying (vr); - return; - } - - /* Now evaluate the expression to determine the new range. */ - if (POINTER_TYPE_P (expr_type)) + value_range_kind kind; + value_range_kind vr0_kind = vr0.kind (), vr1_kind = vr1.kind (); + tree vr0_min = vr0.min (), vr0_max = vr0.max (); + tree vr1_min = vr1.min (), vr1_max = vr1.max (); + tree min = NULL_TREE, max = NULL_TREE; + + /* This will normalize things such that calculating + [0,0] - VR_VARYING is not dropped to varying, but is + calculated as [MIN+1, MAX]. */ + if (vr0.varying_p ()) { - if (code == MIN_EXPR || code == MAX_EXPR) - { - /* 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_includes_zero_p (&vr0) && !range_includes_zero_p (&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 == POINTER_PLUS_EXPR) - { - /* For pointer types, we are really only interested in asserting - whether the expression evaluates to non-NULL. */ - if (!range_includes_zero_p (&vr0) - || !range_includes_zero_p (&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_includes_zero_p (&vr0) && !range_includes_zero_p (&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); - - return; + vr0_kind = VR_RANGE; + vr0_min = vrp_val_min (expr_type); + vr0_max = vrp_val_max (expr_type); } - - /* For integer ranges, apply the operation to each end of the - range and see what we end up with. */ - if (code == PLUS_EXPR || code == MINUS_EXPR) + if (vr1.varying_p ()) { - /* This will normalize things such that calculating - [0,0] - VR_VARYING is not dropped to varying, but is - calculated as [MIN+1, MAX]. */ - if (vr0.varying_p ()) - vr0.update (VR_RANGE, - vrp_val_min (expr_type), - vrp_val_max (expr_type)); - if (vr1.varying_p ()) - vr1.update (VR_RANGE, - vrp_val_min (expr_type), - vrp_val_max (expr_type)); - - const bool minus_p = (code == MINUS_EXPR); - tree min_op0 = vr0.min (); - tree min_op1 = minus_p ? vr1.max () : vr1.min (); - tree max_op0 = vr0.max (); - tree max_op1 = minus_p ? vr1.min () : vr1.max (); - tree sym_min_op0 = NULL_TREE; - tree sym_min_op1 = NULL_TREE; - tree sym_max_op0 = NULL_TREE; - tree sym_max_op1 = NULL_TREE; - bool neg_min_op0, neg_min_op1, neg_max_op0, neg_max_op1; - - neg_min_op0 = neg_min_op1 = neg_max_op0 = neg_max_op1 = false; - - /* If we have a PLUS or MINUS with two VR_RANGEs, either constant or - single-symbolic ranges, try to compute the precise resulting range, - but only if we know that this resulting range will also be constant - or single-symbolic. */ - if (vr0.kind () == VR_RANGE && vr1.kind () == VR_RANGE - && (TREE_CODE (min_op0) == INTEGER_CST - || (sym_min_op0 - = get_single_symbol (min_op0, &neg_min_op0, &min_op0))) - && (TREE_CODE (min_op1) == INTEGER_CST - || (sym_min_op1 - = get_single_symbol (min_op1, &neg_min_op1, &min_op1))) - && (!(sym_min_op0 && sym_min_op1) - || (sym_min_op0 == sym_min_op1 - && neg_min_op0 == (minus_p ? neg_min_op1 : !neg_min_op1))) - && (TREE_CODE (max_op0) == INTEGER_CST - || (sym_max_op0 - = get_single_symbol (max_op0, &neg_max_op0, &max_op0))) - && (TREE_CODE (max_op1) == INTEGER_CST - || (sym_max_op1 - = get_single_symbol (max_op1, &neg_max_op1, &max_op1))) - && (!(sym_max_op0 && sym_max_op1) - || (sym_max_op0 == sym_max_op1 - && neg_max_op0 == (minus_p ? neg_max_op1 : !neg_max_op1)))) - { - wide_int wmin, wmax; - wi::overflow_type min_ovf = wi::OVF_NONE; - wi::overflow_type max_ovf = wi::OVF_NONE; - - /* Build the bounds. */ - combine_bound (code, wmin, min_ovf, expr_type, min_op0, min_op1); - combine_bound (code, wmax, max_ovf, expr_type, max_op0, max_op1); - - /* If we have overflow for the constant part and the resulting - range will be symbolic, drop to VR_VARYING. */ - if (((bool)min_ovf && sym_min_op0 != sym_min_op1) - || ((bool)max_ovf && sym_max_op0 != sym_max_op1)) - { - set_value_range_to_varying (vr); - return; - } - - /* Adjust the range for possible overflow. */ - min = NULL_TREE; - max = NULL_TREE; - set_value_range_with_overflow (type, min, max, expr_type, - wmin, wmax, min_ovf, max_ovf); - if (type == VR_VARYING) - { - set_value_range_to_varying (vr); - return; - } - - /* Build the symbolic bounds if needed. */ - adjust_symbolic_bound (min, code, expr_type, - sym_min_op0, sym_min_op1, - neg_min_op0, neg_min_op1); - adjust_symbolic_bound (max, code, expr_type, - sym_max_op0, sym_max_op1, - neg_max_op0, neg_max_op1); - } - else - { - /* For other cases, for example if we have a PLUS_EXPR with two - VR_ANTI_RANGEs, drop to VR_VARYING. It would take more effort - to compute a precise range for such a case. - ??? General even mixed range kind operations can be expressed - by for example transforming ~[3, 5] + [1, 2] to range-only - operations and a union primitive: - [-INF, 2] + [1, 2] U [5, +INF] + [1, 2] - [-INF+1, 4] U [6, +INF(OVF)] - though usually the union is not exactly representable with - a single range or anti-range as the above is - [-INF+1, +INF(OVF)] intersected with ~[5, 5] - but one could use a scheme similar to equivalences for this. */ - set_value_range_to_varying (vr); - return; - } + vr1_kind = VR_RANGE; + vr1_min = vrp_val_min (expr_type); + vr1_max = vrp_val_max (expr_type); } - else if (code == MIN_EXPR - || code == MAX_EXPR) + + const bool minus_p = (code == MINUS_EXPR); + tree min_op0 = vr0_min; + tree min_op1 = minus_p ? vr1_max : vr1_min; + tree max_op0 = vr0_max; + tree max_op1 = minus_p ? vr1_min : vr1_max; + tree sym_min_op0 = NULL_TREE; + tree sym_min_op1 = NULL_TREE; + tree sym_max_op0 = NULL_TREE; + tree sym_max_op1 = NULL_TREE; + bool neg_min_op0, neg_min_op1, neg_max_op0, neg_max_op1; + + neg_min_op0 = neg_min_op1 = neg_max_op0 = neg_max_op1 = false; + + /* If we have a PLUS or MINUS with two VR_RANGEs, either constant or + single-symbolic ranges, try to compute the precise resulting range, + but only if we know that this resulting range will also be constant + or single-symbolic. */ + if (vr0_kind == VR_RANGE && vr1_kind == VR_RANGE + && (TREE_CODE (min_op0) == INTEGER_CST + || (sym_min_op0 + = get_single_symbol (min_op0, &neg_min_op0, &min_op0))) + && (TREE_CODE (min_op1) == INTEGER_CST + || (sym_min_op1 + = get_single_symbol (min_op1, &neg_min_op1, &min_op1))) + && (!(sym_min_op0 && sym_min_op1) + || (sym_min_op0 == sym_min_op1 + && neg_min_op0 == (minus_p ? neg_min_op1 : !neg_min_op1))) + && (TREE_CODE (max_op0) == INTEGER_CST + || (sym_max_op0 + = get_single_symbol (max_op0, &neg_max_op0, &max_op0))) + && (TREE_CODE (max_op1) == INTEGER_CST + || (sym_max_op1 + = get_single_symbol (max_op1, &neg_max_op1, &max_op1))) + && (!(sym_max_op0 && sym_max_op1) + || (sym_max_op0 == sym_max_op1 + && neg_max_op0 == (minus_p ? neg_max_op1 : !neg_max_op1)))) { wide_int wmin, wmax; - wide_int vr0_min, vr0_max; - wide_int vr1_min, vr1_max; - extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max); - extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max); - if (wide_int_range_min_max (wmin, wmax, code, sign, prec, - vr0_min, vr0_max, vr1_min, vr1_max)) - vr->update (VR_RANGE, wide_int_to_tree (expr_type, wmin), - wide_int_to_tree (expr_type, wmax)); - else - set_value_range_to_varying (vr); - return; - } - else if (code == MULT_EXPR) - { - if (!range_int_cst_p (&vr0) - || !range_int_cst_p (&vr1)) + wi::overflow_type min_ovf = wi::OVF_NONE; + wi::overflow_type max_ovf = wi::OVF_NONE; + + /* Build the bounds. */ + combine_bound (code, wmin, min_ovf, expr_type, min_op0, min_op1); + combine_bound (code, wmax, max_ovf, expr_type, max_op0, max_op1); + + /* If the resulting range will be symbolic, we need to eliminate any + explicit or implicit overflow introduced in the above computation + because compare_values could make an incorrect use of it. That's + why we require one of the ranges to be a singleton. */ + if ((sym_min_op0 != sym_min_op1 || sym_max_op0 != sym_max_op1) + && ((bool)min_ovf || (bool)max_ovf + || (min_op0 != max_op0 && min_op1 != max_op1))) { - set_value_range_to_varying (vr); + vr->set_varying (expr_type); return; } - extract_range_from_multiplicative_op (vr, code, &vr0, &vr1); - return; - } - else if (code == RSHIFT_EXPR - || code == LSHIFT_EXPR) - { - if (range_int_cst_p (&vr1) - && !wide_int_range_shift_undefined_p - (TYPE_SIGN (TREE_TYPE (vr1.min ())), - prec, - wi::to_wide (vr1.min ()), - wi::to_wide (vr1.max ()))) + + /* Adjust the range for possible overflow. */ + set_value_range_with_overflow (kind, min, max, expr_type, + wmin, wmax, min_ovf, max_ovf); + if (kind == VR_VARYING) { - if (code == RSHIFT_EXPR) - { - /* Even if vr0 is VARYING or otherwise not usable, we can derive - useful ranges just from the shift count. E.g. - x >> 63 for signed 64-bit x is always [-1, 0]. */ - if (vr0.kind () != VR_RANGE || vr0.symbolic_p ()) - vr0.update (VR_RANGE, - vrp_val_min (expr_type), - vrp_val_max (expr_type)); - extract_range_from_multiplicative_op (vr, code, &vr0, &vr1); - return; - } - else if (code == LSHIFT_EXPR - && range_int_cst_p (&vr0)) - { - wide_int res_lb, res_ub; - if (wide_int_range_lshift (res_lb, res_ub, sign, prec, - wi::to_wide (vr0.min ()), - wi::to_wide (vr0.max ()), - wi::to_wide (vr1.min ()), - wi::to_wide (vr1.max ()), - TYPE_OVERFLOW_UNDEFINED (expr_type))) - { - min = wide_int_to_tree (expr_type, res_lb); - max = wide_int_to_tree (expr_type, res_ub); - vr->set_and_canonicalize (VR_RANGE, min, max, NULL); - return; - } - } - } - set_value_range_to_varying (vr); - return; - } - else if (code == TRUNC_DIV_EXPR - || code == FLOOR_DIV_EXPR - || code == CEIL_DIV_EXPR - || code == EXACT_DIV_EXPR - || code == ROUND_DIV_EXPR) - { - wide_int dividend_min, dividend_max, divisor_min, divisor_max; - wide_int wmin, wmax, extra_min, extra_max; - bool extra_range_p; - - /* Special case explicit division by zero as undefined. */ - if (range_is_null (&vr1)) - { - set_value_range_to_undefined (vr); + vr->set_varying (expr_type); return; } - /* First, normalize ranges into constants we can handle. Note - that VR_ANTI_RANGE's of constants were already normalized - before arriving here. - - NOTE: As a future improvement, we may be able to do better - with mixed symbolic (anti-)ranges like [0, A]. See note in - ranges_from_anti_range. */ - extract_range_into_wide_ints (&vr0, sign, prec, - dividend_min, dividend_max); - extract_range_into_wide_ints (&vr1, sign, prec, - divisor_min, divisor_max); - if (!wide_int_range_div (wmin, wmax, code, sign, prec, - dividend_min, dividend_max, - divisor_min, divisor_max, - TYPE_OVERFLOW_UNDEFINED (expr_type), - extra_range_p, extra_min, extra_max)) - { - set_value_range_to_varying (vr); - return; - } - set_value_range (vr, VR_RANGE, - wide_int_to_tree (expr_type, wmin), - wide_int_to_tree (expr_type, wmax), NULL); - if (extra_range_p) - { - value_range extra_range; - set_value_range (&extra_range, VR_RANGE, - wide_int_to_tree (expr_type, extra_min), - wide_int_to_tree (expr_type, extra_max), NULL); - vr->union_ (&extra_range); - } - return; + /* Build the symbolic bounds if needed. */ + adjust_symbolic_bound (min, code, expr_type, + sym_min_op0, sym_min_op1, + neg_min_op0, neg_min_op1); + adjust_symbolic_bound (max, code, expr_type, + sym_max_op0, sym_max_op1, + neg_max_op0, neg_max_op1); } - else if (code == TRUNC_MOD_EXPR) + else { - if (range_is_null (&vr1)) - { - set_value_range_to_undefined (vr); - return; - } - wide_int wmin, wmax, tmp; - wide_int vr0_min, vr0_max, vr1_min, vr1_max; - extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max); - extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max); - wide_int_range_trunc_mod (wmin, wmax, sign, prec, - vr0_min, vr0_max, vr1_min, vr1_max); - min = wide_int_to_tree (expr_type, wmin); - max = wide_int_to_tree (expr_type, wmax); - set_value_range (vr, VR_RANGE, min, max, NULL); + /* For other cases, for example if we have a PLUS_EXPR with two + VR_ANTI_RANGEs, drop to VR_VARYING. It would take more effort + to compute a precise range for such a case. + ??? General even mixed range kind operations can be expressed + by for example transforming ~[3, 5] + [1, 2] to range-only + operations and a union primitive: + [-INF, 2] + [1, 2] U [5, +INF] + [1, 2] + [-INF+1, 4] U [6, +INF(OVF)] + though usually the union is not exactly representable with + a single range or anti-range as the above is + [-INF+1, +INF(OVF)] intersected with ~[5, 5] + but one could use a scheme similar to equivalences for this. */ + vr->set_varying (expr_type); return; } - else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR) - { - wide_int may_be_nonzero0, may_be_nonzero1; - wide_int must_be_nonzero0, must_be_nonzero1; - wide_int wmin, wmax; - wide_int vr0_min, vr0_max, vr1_min, vr1_max; - vrp_set_zero_nonzero_bits (expr_type, &vr0, - &may_be_nonzero0, &must_be_nonzero0); - vrp_set_zero_nonzero_bits (expr_type, &vr1, - &may_be_nonzero1, &must_be_nonzero1); - extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max); - extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max); - if (code == BIT_AND_EXPR) - { - if (wide_int_range_bit_and (wmin, wmax, sign, prec, - vr0_min, vr0_max, - vr1_min, vr1_max, - must_be_nonzero0, - may_be_nonzero0, - must_be_nonzero1, - may_be_nonzero1)) - { - min = wide_int_to_tree (expr_type, wmin); - max = wide_int_to_tree (expr_type, wmax); - set_value_range (vr, VR_RANGE, min, max, NULL); - } - else - set_value_range_to_varying (vr); - return; - } - else if (code == BIT_IOR_EXPR) - { - if (wide_int_range_bit_ior (wmin, wmax, sign, - vr0_min, vr0_max, - vr1_min, vr1_max, - must_be_nonzero0, - may_be_nonzero0, - must_be_nonzero1, - may_be_nonzero1)) - { - min = wide_int_to_tree (expr_type, wmin); - max = wide_int_to_tree (expr_type, wmax); - set_value_range (vr, VR_RANGE, min, max, NULL); - } - else - set_value_range_to_varying (vr); - return; - } - else if (code == BIT_XOR_EXPR) - { - if (wide_int_range_bit_xor (wmin, wmax, sign, prec, - must_be_nonzero0, - may_be_nonzero0, - must_be_nonzero1, - may_be_nonzero1)) - { - min = wide_int_to_tree (expr_type, wmin); - max = wide_int_to_tree (expr_type, wmax); - set_value_range (vr, VR_RANGE, min, max, NULL); - } - else - set_value_range_to_varying (vr); - return; - } - } - else - gcc_unreachable (); /* If either MIN or MAX overflowed, then set the resulting range to VARYING. */ @@ -1926,208 +1089,191 @@ || max == NULL_TREE || TREE_OVERFLOW_P (max)) { - set_value_range_to_varying (vr); + vr->set_varying (expr_type); return; } - /* We punt for [-INF, +INF]. - We learn nothing when we have INF on both sides. - Note that we do accept [-INF, -INF] and [+INF, +INF]. */ - if (vrp_val_is_min (min) && vrp_val_is_max (max)) - { - set_value_range_to_varying (vr); - return; - } - - cmp = compare_values (min, max); + int cmp = compare_values (min, max); if (cmp == -2 || cmp == 1) { /* If the new range has its limits swapped around (MIN > MAX), then the operation caused one of them to wrap around, mark the new range VARYING. */ - set_value_range_to_varying (vr); + vr->set_varying (expr_type); } else - set_value_range (vr, type, min, max, NULL); + vr->set (min, max, kind); +} + +/* Return the range-ops handler for CODE and EXPR_TYPE. If no + suitable operator is found, return NULL and set VR to VARYING. */ + +static const range_operator * +get_range_op_handler (value_range *vr, + enum tree_code code, + tree expr_type) +{ + const range_operator *op = range_op_handler (code, expr_type); + if (!op) + vr->set_varying (expr_type); + return op; +} + +/* If the types passed are supported, return TRUE, otherwise set VR to + VARYING and return FALSE. */ + +static bool +supported_types_p (value_range *vr, + tree type0, + tree type1 = NULL) +{ + if (!value_range::supports_type_p (type0) + || (type1 && !value_range::supports_type_p (type1))) + { + vr->set_varying (type0); + return false; + } + return true; +} + +/* If any of the ranges passed are defined, return TRUE, otherwise set + VR to UNDEFINED and return FALSE. */ + +static bool +defined_ranges_p (value_range *vr, + const value_range *vr0, const value_range *vr1 = NULL) +{ + if (vr0->undefined_p () && (!vr1 || vr1->undefined_p ())) + { + vr->set_undefined (); + return false; + } + return true; +} + +static value_range +drop_undefines_to_varying (const value_range *vr, tree expr_type) +{ + if (vr->undefined_p ()) + return value_range (expr_type); + else + return *vr; } -/* Extract range information from a unary operation CODE based on - the range of its operand *VR0 with type OP0_TYPE with resulting type TYPE. - The resulting range is stored in *VR. */ +/* If any operand is symbolic, perform a binary operation on them and + return TRUE, otherwise return FALSE. */ + +static bool +range_fold_binary_symbolics_p (value_range *vr, + tree_code code, + tree expr_type, + const value_range *vr0, const value_range *vr1) +{ + if (vr0->symbolic_p () || vr1->symbolic_p ()) + { + if ((code == PLUS_EXPR || code == MINUS_EXPR)) + { + extract_range_from_plus_minus_expr (vr, code, expr_type, vr0, vr1); + return true; + } + if (POINTER_TYPE_P (expr_type) && code == POINTER_PLUS_EXPR) + { + extract_range_from_pointer_plus_expr (vr, code, expr_type, vr0, vr1); + return true; + } + const range_operator *op = get_range_op_handler (vr, code, expr_type); + value_range vr0_cst (*vr0), vr1_cst (*vr1); + vr0_cst.normalize_symbolics (); + vr1_cst.normalize_symbolics (); + return op->fold_range (*vr, expr_type, vr0_cst, vr1_cst); + } + return false; +} + +/* If operand is symbolic, perform a unary operation on it and return + TRUE, otherwise return FALSE. */ + +static bool +range_fold_unary_symbolics_p (value_range *vr, + tree_code code, + tree expr_type, + const value_range *vr0) +{ + if (vr0->symbolic_p ()) + { + if (code == NEGATE_EXPR) + { + /* -X is simply 0 - X. */ + value_range zero; + zero.set_zero (vr0->type ()); + range_fold_binary_expr (vr, MINUS_EXPR, expr_type, &zero, vr0); + return true; + } + if (code == BIT_NOT_EXPR) + { + /* ~X is simply -1 - X. */ + value_range minusone; + minusone.set (build_int_cst (vr0->type (), -1)); + range_fold_binary_expr (vr, MINUS_EXPR, expr_type, &minusone, vr0); + return true; + } + const range_operator *op = get_range_op_handler (vr, code, expr_type); + value_range vr0_cst (*vr0); + vr0_cst.normalize_symbolics (); + return op->fold_range (*vr, expr_type, vr0_cst, value_range (expr_type)); + } + return false; +} + +/* Perform a binary operation on a pair of ranges. */ void -extract_range_from_unary_expr (value_range *vr, - enum tree_code code, tree type, - const value_range *vr0_, tree op0_type) +range_fold_binary_expr (value_range *vr, + enum tree_code code, + tree expr_type, + const value_range *vr0_, + const value_range *vr1_) { - signop sign = TYPE_SIGN (type); - unsigned int prec = TYPE_PRECISION (type); - value_range vr0 = *vr0_; - value_range vrtem0, vrtem1; - - /* VRP only operates on integral and pointer types. */ - if (!(INTEGRAL_TYPE_P (op0_type) - || POINTER_TYPE_P (op0_type)) - || !(INTEGRAL_TYPE_P (type) - || POINTER_TYPE_P (type))) - { - set_value_range_to_varying (vr); - return; - } - - /* If VR0 is UNDEFINED, so is the result. */ - if (vr0.undefined_p ()) - { - set_value_range_to_undefined (vr); - return; - } - - /* Handle operations that we express in terms of others. */ - if (code == PAREN_EXPR || code == OBJ_TYPE_REF) - { - /* PAREN_EXPR and OBJ_TYPE_REF are simple copies. */ - vr->deep_copy (&vr0); - return; - } - else if (code == NEGATE_EXPR) - { - /* -X is simply 0 - X, so re-use existing code that also handles - anti-ranges fine. */ - value_range zero; - set_value_range_to_value (&zero, build_int_cst (type, 0), NULL); - extract_range_from_binary_expr_1 (vr, MINUS_EXPR, type, &zero, &vr0); - return; - } - else if (code == BIT_NOT_EXPR) - { - /* ~X is simply -1 - X, so re-use existing code that also handles - anti-ranges fine. */ - value_range minusone; - set_value_range_to_value (&minusone, build_int_cst (type, -1), NULL); - extract_range_from_binary_expr_1 (vr, MINUS_EXPR, - type, &minusone, &vr0); - return; - } - - /* Now canonicalize anti-ranges to ranges when they are not symbolic - and express op ~[] as (op []') U (op []''). */ - if (vr0.kind () == VR_ANTI_RANGE - && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1)) - { - extract_range_from_unary_expr (vr, code, type, &vrtem0, op0_type); - if (!vrtem1.undefined_p ()) - { - value_range vrres; - extract_range_from_unary_expr (&vrres, code, type, - &vrtem1, op0_type); - vr->union_ (&vrres); - } - return; - } - - if (CONVERT_EXPR_CODE_P (code)) - { - tree inner_type = op0_type; - tree outer_type = type; - - /* If the expression involves a pointer, we are only interested in - determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). - - This may lose precision when converting (char *)~[0,2] to - int, because we'll forget that the pointer can also not be 1 - or 2. In practice we don't care, as this is some idiot - storing a magic constant to a pointer. */ - if (POINTER_TYPE_P (type) || POINTER_TYPE_P (op0_type)) - { - if (!range_includes_zero_p (&vr0)) - set_value_range_to_nonnull (vr, type); - else if (range_is_null (&vr0)) - set_value_range_to_null (vr, type); - else - set_value_range_to_varying (vr); - return; - } - - /* The POINTER_TYPE_P code above will have dealt with all - pointer anti-ranges. Any remaining anti-ranges at this point - will be integer conversions from SSA names that will be - normalized into VARYING. For instance: ~[x_55, x_55]. */ - gcc_assert (vr0.kind () != VR_ANTI_RANGE - || TREE_CODE (vr0.min ()) != INTEGER_CST); - - /* NOTES: Previously we were returning VARYING for all symbolics, but - we can do better by treating them as [-MIN, +MAX]. For - example, converting [SYM, SYM] from INT to LONG UNSIGNED, - we can return: ~[0x8000000, 0xffffffff7fffffff]. - - We were also failing to convert ~[0,0] from char* to unsigned, - instead choosing to return VR_VARYING. Now we return ~[0,0]. */ - wide_int vr0_min, vr0_max, wmin, wmax; - signop inner_sign = TYPE_SIGN (inner_type); - signop outer_sign = TYPE_SIGN (outer_type); - unsigned inner_prec = TYPE_PRECISION (inner_type); - unsigned outer_prec = TYPE_PRECISION (outer_type); - extract_range_into_wide_ints (&vr0, inner_sign, inner_prec, - vr0_min, vr0_max); - if (wide_int_range_convert (wmin, wmax, - inner_sign, inner_prec, - outer_sign, outer_prec, - vr0_min, vr0_max)) - { - tree min = wide_int_to_tree (outer_type, wmin); - tree max = wide_int_to_tree (outer_type, wmax); - vr->set_and_canonicalize (VR_RANGE, min, max, NULL); - } - else - set_value_range_to_varying (vr); - return; - } - else if (code == ABS_EXPR) - { - wide_int wmin, wmax; - wide_int vr0_min, vr0_max; - extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max); - if (wide_int_range_abs (wmin, wmax, sign, prec, vr0_min, vr0_max, - TYPE_OVERFLOW_UNDEFINED (type))) - set_value_range (vr, VR_RANGE, - wide_int_to_tree (type, wmin), - wide_int_to_tree (type, wmax), NULL); - else - set_value_range_to_varying (vr); - return; - } - - /* For unhandled operations fall back to varying. */ - set_value_range_to_varying (vr); - return; + if (!supported_types_p (vr, expr_type) + || !defined_ranges_p (vr, vr0_, vr1_)) + return; + const range_operator *op = get_range_op_handler (vr, code, expr_type); + if (!op) + return; + + value_range vr0 = drop_undefines_to_varying (vr0_, expr_type); + value_range vr1 = drop_undefines_to_varying (vr1_, expr_type); + if (range_fold_binary_symbolics_p (vr, code, expr_type, &vr0, &vr1)) + return; + + vr0.normalize_addresses (); + vr1.normalize_addresses (); + op->fold_range (*vr, expr_type, vr0, vr1); } -/* Debugging dumps. */ - -void dump_value_range (FILE *, const value_range *); -void debug_value_range (const value_range *); -void dump_all_value_ranges (FILE *); -void dump_vr_equiv (FILE *, bitmap); -void debug_vr_equiv (bitmap); +/* Perform a unary operation on a range. */ void -dump_value_range (FILE *file, const value_range *vr) +range_fold_unary_expr (value_range *vr, + enum tree_code code, tree expr_type, + const value_range *vr0, + tree vr0_type) { - if (!vr) - fprintf (file, "[]"); - else - vr->dump (file); + if (!supported_types_p (vr, expr_type, vr0_type) + || !defined_ranges_p (vr, vr0)) + return; + const range_operator *op = get_range_op_handler (vr, code, expr_type); + if (!op) + return; + + if (range_fold_unary_symbolics_p (vr, code, expr_type, vr0)) + return; + + value_range vr0_cst (*vr0); + vr0_cst.normalize_addresses (); + op->fold_range (*vr, expr_type, vr0_cst, value_range (expr_type)); } -/* Dump value range VR to stderr. */ - -DEBUG_FUNCTION void -debug_value_range (const value_range *vr) -{ - vr->dump (); -} - - /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V, create a new SSA name N and return the assertion assignment 'N = ASSERT_EXPR <V, V OP W>'. */ @@ -2285,6 +1431,45 @@ dump_all_asserts (stderr); } +/* Dump assert_info structure. */ + +void +dump_assert_info (FILE *file, const assert_info &assert) +{ + fprintf (file, "Assert for: "); + print_generic_expr (file, assert.name); + fprintf (file, "\n\tPREDICATE: expr=["); + print_generic_expr (file, assert.expr); + fprintf (file, "] %s ", get_tree_code_name (assert.comp_code)); + fprintf (file, "val=["); + print_generic_expr (file, assert.val); + fprintf (file, "]\n\n"); +} + +DEBUG_FUNCTION void +debug (const assert_info &assert) +{ + dump_assert_info (stderr, assert); +} + +/* Dump a vector of assert_info's. */ + +void +dump_asserts_info (FILE *file, const vec<assert_info> &asserts) +{ + for (unsigned i = 0; i < asserts.length (); ++i) + { + dump_assert_info (file, asserts[i]); + fprintf (file, "\n"); + } +} + +DEBUG_FUNCTION void +debug (const vec<assert_info> &asserts) +{ + dump_asserts_info (stderr, asserts); +} + /* Push the assert info for NAME, EXPR, COMP_CODE and VAL to ASSERTS. */ static void @@ -2819,6 +2004,7 @@ { name2 = gimple_assign_rhs1 (def_stmt); if (CONVERT_EXPR_CODE_P (rhs_code) + && TREE_CODE (name2) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (name2)) && TYPE_UNSIGNED (TREE_TYPE (name2)) && prec == TYPE_PRECISION (TREE_TYPE (name2)) @@ -2908,6 +2094,39 @@ add_assert_info (asserts, name2, tmp, new_comp_code, new_val); } + /* If we have a conversion that doesn't change the value of the source + simply register the same assert for it. */ + if (CONVERT_EXPR_CODE_P (rhs_code)) + { + wide_int rmin, rmax; + tree rhs1 = gimple_assign_rhs1 (def_stmt); + if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) + && TREE_CODE (rhs1) == SSA_NAME + /* Make sure the relation preserves the upper/lower boundary of + the range conservatively. */ + && (comp_code == NE_EXPR + || comp_code == EQ_EXPR + || (TYPE_SIGN (TREE_TYPE (name)) + == TYPE_SIGN (TREE_TYPE (rhs1))) + || ((comp_code == LE_EXPR + || comp_code == LT_EXPR) + && !TYPE_UNSIGNED (TREE_TYPE (rhs1))) + || ((comp_code == GE_EXPR + || comp_code == GT_EXPR) + && TYPE_UNSIGNED (TREE_TYPE (rhs1)))) + /* And the conversion does not alter the value we compare + against and all values in rhs1 can be represented in + the converted to type. */ + && int_fits_type_p (val, TREE_TYPE (rhs1)) + && ((TYPE_PRECISION (TREE_TYPE (name)) + > TYPE_PRECISION (TREE_TYPE (rhs1))) + || (get_range_info (rhs1, &rmin, &rmax) == VR_RANGE + && wi::fits_to_tree_p (rmin, TREE_TYPE (name)) + && wi::fits_to_tree_p (rmax, TREE_TYPE (name))))) + add_assert_info (asserts, rhs1, rhs1, + comp_code, fold_convert (TREE_TYPE (rhs1), val)); + } + /* Add asserts for NAME cmp CST and NAME being defined as NAME = NAME2 & CST2. @@ -2947,6 +2166,7 @@ { names[1] = gimple_assign_rhs1 (def_stmt2); if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt2)) + || TREE_CODE (names[1]) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (names[1])) || (TYPE_PRECISION (TREE_TYPE (name2)) != TYPE_PRECISION (TREE_TYPE (names[1])))) @@ -3575,7 +2795,7 @@ /* Now register along the default label assertions that correspond to the anti-range of each label. */ - int insertion_limit = PARAM_VALUE (PARAM_MAX_VRP_SWITCH_ASSERTIONS); + int insertion_limit = param_max_vrp_switch_assertions; if (insertion_limit == 0) return; @@ -4224,24 +3444,26 @@ void vrp_initialize (void); void vrp_finalize (bool); void check_all_array_refs (void); - void check_array_ref (location_t, tree, bool); - void check_mem_ref (location_t, tree, bool); + bool check_array_ref (location_t, tree, bool); + bool check_mem_ref (location_t, tree, bool); void search_for_addr_array (tree, location_t); class vr_values vr_values; /* Temporary delegator to minimize code churn. */ - value_range *get_value_range (const_tree op) + const value_range_equiv *get_value_range (const_tree op) { return vr_values.get_value_range (op); } + void set_def_to_varying (const_tree def) + { vr_values.set_def_to_varying (def); } void set_defs_to_varying (gimple *stmt) - { return vr_values.set_defs_to_varying (stmt); } + { vr_values.set_defs_to_varying (stmt); } void extract_range_from_stmt (gimple *stmt, edge *taken_edge_p, - tree *output_p, value_range *vr) + tree *output_p, value_range_equiv *vr) { vr_values.extract_range_from_stmt (stmt, taken_edge_p, output_p, vr); } - bool update_value_range (const_tree op, value_range *vr) + bool update_value_range (const_tree op, value_range_equiv *vr) { return vr_values.update_value_range (op, vr); } - void extract_range_basic (value_range *vr, gimple *stmt) + void extract_range_basic (value_range_equiv *vr, gimple *stmt) { vr_values.extract_range_basic (vr, stmt); } - void extract_range_from_phi_node (gphi *phi, value_range *vr) + void extract_range_from_phi_node (gphi *phi, value_range_equiv *vr) { vr_values.extract_range_from_phi_node (phi, vr); } }; /* Checks one ARRAY_REF in REF, located at LOCUS. Ignores flexible arrays @@ -4249,21 +3471,27 @@ array subscript is a constant, check if it is outside valid range. If the array subscript is a RANGE, warn if it is non-overlapping with valid range. - IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR. */ - -void + IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR. + Returns true if a warning has been issued. */ + +bool vrp_prop::check_array_ref (location_t location, tree ref, bool ignore_off_by_one) { - const value_range *vr = NULL; - tree low_sub, up_sub; - tree low_bound, up_bound, up_bound_p1; - if (TREE_NO_WARNING (ref)) - return; - - low_sub = up_sub = TREE_OPERAND (ref, 1); - up_bound = array_ref_up_bound (ref); + return false; + + tree low_sub = TREE_OPERAND (ref, 1); + tree up_sub = low_sub; + tree up_bound = array_ref_up_bound (ref); + + /* Referenced decl if one can be determined. */ + tree decl = NULL_TREE; + + /* Set for accesses to interior zero-length arrays. */ + bool interior_zero_len = false; + + tree up_bound_p1; if (!up_bound || TREE_CODE (up_bound) != INTEGER_CST @@ -4285,28 +3513,61 @@ } else { - tree maxbound = TYPE_MAX_VALUE (ptrdiff_type_node); + tree ptrdiff_max = TYPE_MAX_VALUE (ptrdiff_type_node); + tree maxbound = ptrdiff_max; tree arg = TREE_OPERAND (ref, 0); - poly_int64 off; - - if (get_addr_base_and_unit_offset (arg, &off) && known_gt (off, 0)) - maxbound = wide_int_to_tree (sizetype, - wi::sub (wi::to_wide (maxbound), - off)); + + const bool compref = TREE_CODE (arg) == COMPONENT_REF; + if (compref) + { + /* Try to determine the size of the trailing array from + its initializer (if it has one). */ + if (tree refsize = component_ref_size (arg, &interior_zero_len)) + if (TREE_CODE (refsize) == INTEGER_CST) + maxbound = refsize; + } + + if (maxbound == ptrdiff_max) + { + /* Try to determine the size of the base object. Avoid + COMPONENT_REF already tried above. Using its DECL_SIZE + size wouldn't necessarily be correct if the reference is + to its flexible array member initialized in a different + translation unit. */ + poly_int64 off; + if (tree base = get_addr_base_and_unit_offset (arg, &off)) + { + if (!compref && DECL_P (base)) + if (tree basesize = DECL_SIZE_UNIT (base)) + if (TREE_CODE (basesize) == INTEGER_CST) + { + maxbound = basesize; + decl = base; + } + + if (known_gt (off, 0)) + maxbound = wide_int_to_tree (sizetype, + wi::sub (wi::to_wide (maxbound), + off)); + } + } else maxbound = fold_convert (sizetype, maxbound); up_bound_p1 = int_const_binop (TRUNC_DIV_EXPR, maxbound, eltsize); - up_bound = int_const_binop (MINUS_EXPR, up_bound_p1, - build_int_cst (ptrdiff_type_node, 1)); + if (up_bound_p1 != NULL_TREE) + up_bound = int_const_binop (MINUS_EXPR, up_bound_p1, + build_int_cst (ptrdiff_type_node, 1)); + else + up_bound = NULL_TREE; } } else up_bound_p1 = int_const_binop (PLUS_EXPR, up_bound, build_int_cst (TREE_TYPE (up_bound), 1)); - low_bound = array_ref_low_bound (ref); + tree low_bound = array_ref_low_bound (ref); tree artype = TREE_TYPE (TREE_OPERAND (ref, 0)); @@ -4315,9 +3576,10 @@ /* Empty array. */ if (up_bound && tree_int_cst_equal (low_bound, up_bound_p1)) warned = warning_at (location, OPT_Warray_bounds, - "array subscript %E is above array bounds of %qT", - low_bound, artype); - + "array subscript %E is outside array bounds of %qT", + low_sub, artype); + + const value_range_equiv *vr = NULL; if (TREE_CODE (low_sub) == SSA_NAME) { vr = get_value_range (low_sub); @@ -4328,7 +3590,9 @@ } } - if (vr && vr->kind () == VR_ANTI_RANGE) + if (warned) + ; /* Do nothing. */ + else if (vr && vr->kind () == VR_ANTI_RANGE) { if (up_bound && TREE_CODE (up_sub) == INTEGER_CST @@ -4347,6 +3611,25 @@ && (ignore_off_by_one ? !tree_int_cst_le (up_sub, up_bound_p1) : !tree_int_cst_le (up_sub, up_bound))) + warned = warning_at (location, OPT_Warray_bounds, + "array subscript %E is above array bounds of %qT", + up_sub, artype); + else if (TREE_CODE (low_sub) == INTEGER_CST + && tree_int_cst_lt (low_sub, low_bound)) + warned = warning_at (location, OPT_Warray_bounds, + "array subscript %E is below array bounds of %qT", + low_sub, artype); + + if (!warned && interior_zero_len) + warned = warning_at (location, OPT_Wzero_length_bounds, + (TREE_CODE (low_sub) == INTEGER_CST + ? G_("array subscript %E is outside the bounds " + "of an interior zero-length array %qT") + : G_("array subscript %qE is outside the bounds " + "of an interior zero-length array %qT")), + low_sub, artype); + + if (warned) { if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -4354,33 +3637,30 @@ dump_generic_expr (MSG_NOTE, TDF_SLIM, ref); fprintf (dump_file, "\n"); } - warned = warning_at (location, OPT_Warray_bounds, - "array subscript %E is above array bounds of %qT", - up_sub, artype); - } - else if (TREE_CODE (low_sub) == INTEGER_CST - && tree_int_cst_lt (low_sub, low_bound)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) + + ref = decl ? decl : TREE_OPERAND (ref, 0); + + tree rec = NULL_TREE; + if (TREE_CODE (ref) == COMPONENT_REF) { - fprintf (dump_file, "Array bound warning for "); - dump_generic_expr (MSG_NOTE, TDF_SLIM, ref); - fprintf (dump_file, "\n"); + /* For a reference to a member of a struct object also mention + the object if it's known. It may be defined in a different + function than the out-of-bounds access. */ + rec = TREE_OPERAND (ref, 0); + if (!VAR_P (rec)) + rec = NULL_TREE; + ref = TREE_OPERAND (ref, 1); } - warned = warning_at (location, OPT_Warray_bounds, - "array subscript %E is below array bounds of %qT", - low_sub, artype); - } - - if (warned) - { - ref = TREE_OPERAND (ref, 0); if (DECL_P (ref)) inform (DECL_SOURCE_LOCATION (ref), "while referencing %qD", ref); + if (rec && DECL_P (rec)) + inform (DECL_SOURCE_LOCATION (rec), "defined here %qD", rec); TREE_NO_WARNING (ref) = 1; } + + return warned; } /* Checks one MEM_REF in REF, located at LOCATION, for out-of-bounds @@ -4390,14 +3670,15 @@ with valid range. IGNORE_OFF_BY_ONE is true if the MEM_REF is inside an ADDR_EXPR (used to allow one-past-the-end indices for code that takes - the address of the just-past-the-end element of an array). */ - -void + the address of the just-past-the-end element of an array). + Returns true if a warning has been issued. */ + +bool vrp_prop::check_mem_ref (location_t location, tree ref, bool ignore_off_by_one) { if (TREE_NO_WARNING (ref)) - return; + return false; tree arg = TREE_OPERAND (ref, 0); /* The constant and variable offset of the reference. */ @@ -4424,13 +3705,14 @@ /* The range of the byte offset into the reference. */ offset_int offrange[2] = { 0, 0 }; - const value_range *vr = NULL; + const value_range_equiv *vr = NULL; /* Determine the offsets and increment OFFRANGE for the bounds of each. - The loop computes the the range of the final offset for expressions - such as (A + i0 + ... + iN)[CSTOFF] where i0 through iN are SSA_NAMEs - in some range. */ - while (TREE_CODE (arg) == SSA_NAME) + The loop computes the range of the final offset for expressions such + as (A + i0 + ... + iN)[CSTOFF] where i0 through iN are SSA_NAMEs in + some range. */ + const unsigned limit = param_ssa_name_def_chain_limit; + for (unsigned n = 0; TREE_CODE (arg) == SSA_NAME && n < limit; ++n) { gimple *def = SSA_NAME_DEF_STMT (arg); if (!is_gimple_assign (def)) @@ -4448,7 +3730,7 @@ continue; } else - return; + return false; /* VAROFF should always be a SSA_NAME here (and not even INTEGER_CST) but there's no point in taking chances. */ @@ -4464,26 +3746,21 @@ if (vr->kind () == VR_RANGE) { - if (tree_int_cst_lt (vr->min (), vr->max ())) + offset_int min + = wi::to_offset (fold_convert (ptrdiff_type_node, vr->min ())); + offset_int max + = wi::to_offset (fold_convert (ptrdiff_type_node, vr->max ())); + if (min < max) { - offset_int min - = wi::to_offset (fold_convert (ptrdiff_type_node, vr->min ())); - offset_int max - = wi::to_offset (fold_convert (ptrdiff_type_node, vr->max ())); - if (min < max) - { - offrange[0] += min; - offrange[1] += max; - } - else - { - offrange[0] += max; - offrange[1] += min; - } + offrange[0] += min; + offrange[1] += max; } else { - /* Conservatively add [-MAXOBJSIZE -1, MAXOBJSIZE] + /* When MIN >= MAX, the offset is effectively in a union + of two ranges: [-MAXOBJSIZE -1, MAX] and [MIN, MAXOBJSIZE]. + Since there is no way to represent such a range across + additions, conservatively add [-MAXOBJSIZE -1, MAXOBJSIZE] to OFFRANGE. */ offrange[0] += arrbounds[0]; offrange[1] += arrbounds[1]; @@ -4514,52 +3791,57 @@ { arg = TREE_OPERAND (arg, 0); if (TREE_CODE (arg) != STRING_CST + && TREE_CODE (arg) != PARM_DECL && TREE_CODE (arg) != VAR_DECL) - return; + return false; } else - return; + return false; /* The type of the object being referred to. It can be an array, string literal, or a non-array type when the MEM_REF represents a reference/subscript via a pointer to an object that is not - an element of an array. References to members of structs and - unions are excluded because MEM_REF doesn't make it possible - to identify the member where the reference originated. - Incomplete types are excluded as well because their size is - not known. */ + an element of an array. Incomplete types are excluded as well + because their size is not known. */ tree reftype = TREE_TYPE (arg); if (POINTER_TYPE_P (reftype) || !COMPLETE_TYPE_P (reftype) - || TREE_CODE (TYPE_SIZE_UNIT (reftype)) != INTEGER_CST - || RECORD_OR_UNION_TYPE_P (reftype)) - return; + || TREE_CODE (TYPE_SIZE_UNIT (reftype)) != INTEGER_CST) + return false; + + /* Except in declared objects, references to trailing array members + of structs and union objects are excluded because MEM_REF doesn't + make it possible to identify the member where the reference + originated. */ + if (RECORD_OR_UNION_TYPE_P (reftype) + && (!VAR_P (arg) + || (DECL_EXTERNAL (arg) && array_at_struct_end_p (ref)))) + return false; + + arrbounds[0] = 0; offset_int eltsize; if (TREE_CODE (reftype) == ARRAY_TYPE) { eltsize = wi::to_offset (TYPE_SIZE_UNIT (TREE_TYPE (reftype))); - if (tree dom = TYPE_DOMAIN (reftype)) { tree bnds[] = { TYPE_MIN_VALUE (dom), TYPE_MAX_VALUE (dom) }; - if (array_at_struct_end_p (arg) - || !bnds[0] || !bnds[1]) + if (TREE_CODE (arg) == COMPONENT_REF) { - arrbounds[0] = 0; - arrbounds[1] = wi::lrshift (maxobjsize, wi::floor_log2 (eltsize)); + offset_int size = maxobjsize; + if (tree fldsize = component_ref_size (arg)) + size = wi::to_offset (fldsize); + arrbounds[1] = wi::lrshift (size, wi::floor_log2 (eltsize)); } + else if (array_at_struct_end_p (arg) || !bnds[0] || !bnds[1]) + arrbounds[1] = wi::lrshift (maxobjsize, wi::floor_log2 (eltsize)); else - { - arrbounds[0] = wi::to_offset (bnds[0]) * eltsize; - arrbounds[1] = (wi::to_offset (bnds[1]) + 1) * eltsize; - } + arrbounds[1] = (wi::to_offset (bnds[1]) - wi::to_offset (bnds[0]) + + 1) * eltsize; } else - { - arrbounds[0] = 0; - arrbounds[1] = wi::lrshift (maxobjsize, wi::floor_log2 (eltsize)); - } + arrbounds[1] = wi::lrshift (maxobjsize, wi::floor_log2 (eltsize)); if (TREE_CODE (ref) == MEM_REF) { @@ -4574,8 +3856,13 @@ else { eltsize = 1; - arrbounds[0] = 0; - arrbounds[1] = wi::to_offset (TYPE_SIZE_UNIT (reftype)); + tree size = TYPE_SIZE_UNIT (reftype); + if (VAR_P (arg)) + if (tree initsize = DECL_SIZE_UNIT (arg)) + if (tree_int_cst_lt (size, initsize)) + size = initsize; + + arrbounds[1] = wi::to_offset (size); } offrange[0] += ioff; @@ -4588,7 +3875,9 @@ if (ignore_off_by_one) ubound += 1; - if (offrange[0] >= ubound || offrange[1] < arrbounds[0]) + if (arrbounds[0] == arrbounds[1] + || offrange[0] >= ubound + || offrange[1] < arrbounds[0]) { /* Treat a reference to a non-array object as one to an array of a single element. */ @@ -4599,13 +3888,16 @@ { /* Extract the element type out of MEM_REF and use its size to compute the index to print in the diagnostic; arrays - in MEM_REF don't mean anything. */ + in MEM_REF don't mean anything. A type with no size like + void is as good as having a size of 1. */ tree type = TREE_TYPE (ref); while (TREE_CODE (type) == ARRAY_TYPE) type = TREE_TYPE (type); - tree size = TYPE_SIZE_UNIT (type); - offrange[0] = offrange[0] / wi::to_offset (size); - offrange[1] = offrange[1] / wi::to_offset (size); + if (tree size = TYPE_SIZE_UNIT (type)) + { + offrange[0] = offrange[0] / wi::to_offset (size); + offrange[1] = offrange[1] / wi::to_offset (size); + } } else { @@ -4630,12 +3922,13 @@ if (warned && DECL_P (arg)) inform (DECL_SOURCE_LOCATION (arg), "while referencing %qD", arg); - TREE_NO_WARNING (ref) = 1; - return; + if (warned) + TREE_NO_WARNING (ref) = 1; + return warned; } if (warn_array_bounds < 2) - return; + return false; /* At level 2 check also intermediate offsets. */ int i = 0; @@ -4643,12 +3936,16 @@ { HOST_WIDE_INT tmpidx = extrema[i].to_shwi () / eltsize.to_shwi (); - warning_at (location, OPT_Warray_bounds, - "intermediate array offset %wi is outside array bounds " - "of %qT", - tmpidx, reftype); - TREE_NO_WARNING (ref) = 1; + if (warning_at (location, OPT_Warray_bounds, + "intermediate array offset %wi is outside array bounds " + "of %qT", tmpidx, reftype)) + { + TREE_NO_WARNING (ref) = 1; + return true; + } } + + return false; } /* Searches if the expr T, located at LOCATION computes @@ -4660,10 +3957,14 @@ /* Check each ARRAY_REF and MEM_REF in the reference chain. */ do { + bool warned = false; if (TREE_CODE (t) == ARRAY_REF) - check_array_ref (location, t, true /*ignore_off_by_one*/); + warned = check_array_ref (location, t, true /*ignore_off_by_one*/); else if (TREE_CODE (t) == MEM_REF) - check_mem_ref (location, t, true /*ignore_off_by_one*/); + warned = check_mem_ref (location, t, true /*ignore_off_by_one*/); + + if (warned) + TREE_NO_WARNING (t) = true; t = TREE_OPERAND (t, 0); } @@ -4755,16 +4056,20 @@ *walk_subtree = TRUE; + bool warned = false; vrp_prop *vrp_prop = (class vrp_prop *)wi->info; if (TREE_CODE (t) == ARRAY_REF) - vrp_prop->check_array_ref (location, t, false /*ignore_off_by_one*/); + warned = vrp_prop->check_array_ref (location, t, false/*ignore_off_by_one*/); else if (TREE_CODE (t) == MEM_REF) - vrp_prop->check_mem_ref (location, t, false /*ignore_off_by_one*/); + warned = vrp_prop->check_mem_ref (location, t, false /*ignore_off_by_one*/); else if (TREE_CODE (t) == ADDR_EXPR) { vrp_prop->search_for_addr_array (t, location); *walk_subtree = FALSE; } + /* Propagate the no-warning bit to the outer expression. */ + if (warned) + TREE_NO_WARNING (t) = true; return NULL_TREE; } @@ -5087,7 +4392,7 @@ if (!stmt_interesting_for_vrp (phi)) { tree lhs = PHI_RESULT (phi); - set_value_range_to_varying (get_value_range (lhs)); + set_def_to_varying (lhs); prop_set_simulate_again (phi, false); } else @@ -5242,7 +4547,7 @@ vrp_prop::visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) { tree lhs = gimple_get_lhs (stmt); - value_range vr; + value_range_equiv vr; extract_range_from_stmt (stmt, taken_edge_p, output_p, &vr); if (*output_p) @@ -5282,7 +4587,7 @@ use_operand_p use_p; enum ssa_prop_result res = SSA_PROP_VARYING; - set_value_range_to_varying (get_value_range (lhs)); + set_def_to_varying (lhs); FOR_EACH_IMM_USE_FAST (use_p, iter, lhs) { @@ -5311,10 +4616,10 @@ SSA_PROP_NOT_INTERESTING. If there are no {REAL,IMAG}PART_EXPR uses at all, return SSA_PROP_VARYING. */ - value_range new_vr; + value_range_equiv new_vr; extract_range_basic (&new_vr, use_stmt); - const value_range *old_vr = get_value_range (use_lhs); - if (*old_vr != new_vr) + const value_range_equiv *old_vr = get_value_range (use_lhs); + if (!old_vr->equal_p (new_vr, /*ignore_equivs=*/false)) res = SSA_PROP_INTERESTING; else res = SSA_PROP_NOT_INTERESTING; @@ -5340,661 +4645,8 @@ return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; } -/* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and - { VR1TYPE, VR0MIN, VR0MAX } and store the result - in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest - possible such range. The resulting range is not canonicalized. */ - -static void -union_ranges (enum value_range_kind *vr0type, - tree *vr0min, tree *vr0max, - enum value_range_kind vr1type, - tree vr1min, tree vr1max) -{ - bool mineq = vrp_operand_equal_p (*vr0min, vr1min); - bool maxeq = vrp_operand_equal_p (*vr0max, vr1max); - - /* [] is vr0, () is vr1 in the following classification comments. */ - if (mineq && maxeq) - { - /* [( )] */ - if (*vr0type == vr1type) - /* Nothing to do for equal ranges. */ - ; - else if ((*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - || (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE)) - { - /* For anti-range with range union the result is varying. */ - goto give_up; - } - else - gcc_unreachable (); - } - else if (operand_less_p (*vr0max, vr1min) == 1 - || operand_less_p (vr1max, *vr0min) == 1) - { - /* [ ] ( ) or ( ) [ ] - If the ranges have an empty intersection, result of the union - operation is the anti-range or if both are anti-ranges - it covers all. */ - if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - goto give_up; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - ; - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - else if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - { - /* The result is the convex hull of both ranges. */ - if (operand_less_p (*vr0max, vr1min) == 1) - { - /* If the result can be an anti-range, create one. */ - if (TREE_CODE (*vr0max) == INTEGER_CST - && TREE_CODE (vr1min) == INTEGER_CST - && vrp_val_is_min (*vr0min) - && vrp_val_is_max (vr1max)) - { - tree min = int_const_binop (PLUS_EXPR, - *vr0max, - build_int_cst (TREE_TYPE (*vr0max), 1)); - tree max = int_const_binop (MINUS_EXPR, - vr1min, - build_int_cst (TREE_TYPE (vr1min), 1)); - if (!operand_less_p (max, min)) - { - *vr0type = VR_ANTI_RANGE; - *vr0min = min; - *vr0max = max; - } - else - *vr0max = vr1max; - } - else - *vr0max = vr1max; - } - else - { - /* If the result can be an anti-range, create one. */ - if (TREE_CODE (vr1max) == INTEGER_CST - && TREE_CODE (*vr0min) == INTEGER_CST - && vrp_val_is_min (vr1min) - && vrp_val_is_max (*vr0max)) - { - tree min = int_const_binop (PLUS_EXPR, - vr1max, - build_int_cst (TREE_TYPE (vr1max), 1)); - tree max = int_const_binop (MINUS_EXPR, - *vr0min, - build_int_cst (TREE_TYPE (*vr0min), 1)); - if (!operand_less_p (max, min)) - { - *vr0type = VR_ANTI_RANGE; - *vr0min = min; - *vr0max = max; - } - else - *vr0min = vr1min; - } - else - *vr0min = vr1min; - } - } - else - gcc_unreachable (); - } - else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1) - && (mineq || operand_less_p (*vr0min, vr1min) == 1)) - { - /* [ ( ) ] or [( ) ] or [ ( )] */ - if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - ; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - /* Arbitrarily choose the right or left gap. */ - if (!mineq && TREE_CODE (vr1min) == INTEGER_CST) - *vr0max = int_const_binop (MINUS_EXPR, vr1min, - build_int_cst (TREE_TYPE (vr1min), 1)); - else if (!maxeq && TREE_CODE (vr1max) == INTEGER_CST) - *vr0min = int_const_binop (PLUS_EXPR, vr1max, - build_int_cst (TREE_TYPE (vr1max), 1)); - else - goto give_up; - } - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - /* The result covers everything. */ - goto give_up; - else - gcc_unreachable (); - } - else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1) - && (mineq || operand_less_p (vr1min, *vr0min) == 1)) - { - /* ( [ ] ) or ([ ] ) or ( [ ]) */ - if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - ; - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - *vr0type = VR_ANTI_RANGE; - if (!mineq && TREE_CODE (*vr0min) == INTEGER_CST) - { - *vr0max = int_const_binop (MINUS_EXPR, *vr0min, - build_int_cst (TREE_TYPE (*vr0min), 1)); - *vr0min = vr1min; - } - else if (!maxeq && TREE_CODE (*vr0max) == INTEGER_CST) - { - *vr0min = int_const_binop (PLUS_EXPR, *vr0max, - build_int_cst (TREE_TYPE (*vr0max), 1)); - *vr0max = vr1max; - } - else - goto give_up; - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - /* The result covers everything. */ - goto give_up; - else - gcc_unreachable (); - } - else if ((operand_less_p (vr1min, *vr0max) == 1 - || operand_equal_p (vr1min, *vr0max, 0)) - && operand_less_p (*vr0min, vr1min) == 1 - && operand_less_p (*vr0max, vr1max) == 1) - { - /* [ ( ] ) or [ ]( ) */ - if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - *vr0max = vr1max; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - *vr0min = vr1min; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - if (TREE_CODE (vr1min) == INTEGER_CST) - *vr0max = int_const_binop (MINUS_EXPR, vr1min, - build_int_cst (TREE_TYPE (vr1min), 1)); - else - goto give_up; - } - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - if (TREE_CODE (*vr0max) == INTEGER_CST) - { - *vr0type = vr1type; - *vr0min = int_const_binop (PLUS_EXPR, *vr0max, - build_int_cst (TREE_TYPE (*vr0max), 1)); - *vr0max = vr1max; - } - else - goto give_up; - } - else - gcc_unreachable (); - } - else if ((operand_less_p (*vr0min, vr1max) == 1 - || operand_equal_p (*vr0min, vr1max, 0)) - && operand_less_p (vr1min, *vr0min) == 1 - && operand_less_p (vr1max, *vr0max) == 1) - { - /* ( [ ) ] or ( )[ ] */ - if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - *vr0min = vr1min; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - *vr0max = vr1max; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - if (TREE_CODE (vr1max) == INTEGER_CST) - *vr0min = int_const_binop (PLUS_EXPR, vr1max, - build_int_cst (TREE_TYPE (vr1max), 1)); - else - goto give_up; - } - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - if (TREE_CODE (*vr0min) == INTEGER_CST) - { - *vr0type = vr1type; - *vr0max = int_const_binop (MINUS_EXPR, *vr0min, - build_int_cst (TREE_TYPE (*vr0min), 1)); - *vr0min = vr1min; - } - else - goto give_up; - } - else - gcc_unreachable (); - } - else - goto give_up; - - return; - -give_up: - *vr0type = VR_VARYING; - *vr0min = NULL_TREE; - *vr0max = NULL_TREE; -} - -/* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and - { VR1TYPE, VR0MIN, VR0MAX } and store the result - in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest - possible such range. The resulting range is not canonicalized. */ - -static void -intersect_ranges (enum value_range_kind *vr0type, - tree *vr0min, tree *vr0max, - enum value_range_kind vr1type, - tree vr1min, tree vr1max) -{ - bool mineq = vrp_operand_equal_p (*vr0min, vr1min); - bool maxeq = vrp_operand_equal_p (*vr0max, vr1max); - - /* [] is vr0, () is vr1 in the following classification comments. */ - if (mineq && maxeq) - { - /* [( )] */ - if (*vr0type == vr1type) - /* Nothing to do for equal ranges. */ - ; - else if ((*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - || (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE)) - { - /* For anti-range with range intersection the result is empty. */ - *vr0type = VR_UNDEFINED; - *vr0min = NULL_TREE; - *vr0max = NULL_TREE; - } - else - gcc_unreachable (); - } - else if (operand_less_p (*vr0max, vr1min) == 1 - || operand_less_p (vr1max, *vr0min) == 1) - { - /* [ ] ( ) or ( ) [ ] - If the ranges have an empty intersection, the result of the - intersect operation is the range for intersecting an - anti-range with a range or empty when intersecting two ranges. */ - if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - ; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - else if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - { - *vr0type = VR_UNDEFINED; - *vr0min = NULL_TREE; - *vr0max = NULL_TREE; - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - { - /* If the anti-ranges are adjacent to each other merge them. */ - if (TREE_CODE (*vr0max) == INTEGER_CST - && TREE_CODE (vr1min) == INTEGER_CST - && operand_less_p (*vr0max, vr1min) == 1 - && integer_onep (int_const_binop (MINUS_EXPR, - vr1min, *vr0max))) - *vr0max = vr1max; - else if (TREE_CODE (vr1max) == INTEGER_CST - && TREE_CODE (*vr0min) == INTEGER_CST - && operand_less_p (vr1max, *vr0min) == 1 - && integer_onep (int_const_binop (MINUS_EXPR, - *vr0min, vr1max))) - *vr0min = vr1min; - /* Else arbitrarily take VR0. */ - } - } - else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1) - && (mineq || operand_less_p (*vr0min, vr1min) == 1)) - { - /* [ ( ) ] or [( ) ] or [ ( )] */ - if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - { - /* If both are ranges the result is the inner one. */ - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - /* Choose the right gap if the left one is empty. */ - if (mineq) - { - if (TREE_CODE (vr1max) != INTEGER_CST) - *vr0min = vr1max; - else if (TYPE_PRECISION (TREE_TYPE (vr1max)) == 1 - && !TYPE_UNSIGNED (TREE_TYPE (vr1max))) - *vr0min - = int_const_binop (MINUS_EXPR, vr1max, - build_int_cst (TREE_TYPE (vr1max), -1)); - else - *vr0min - = int_const_binop (PLUS_EXPR, vr1max, - build_int_cst (TREE_TYPE (vr1max), 1)); - } - /* Choose the left gap if the right one is empty. */ - else if (maxeq) - { - if (TREE_CODE (vr1min) != INTEGER_CST) - *vr0max = vr1min; - else if (TYPE_PRECISION (TREE_TYPE (vr1min)) == 1 - && !TYPE_UNSIGNED (TREE_TYPE (vr1min))) - *vr0max - = int_const_binop (PLUS_EXPR, vr1min, - build_int_cst (TREE_TYPE (vr1min), -1)); - else - *vr0max - = int_const_binop (MINUS_EXPR, vr1min, - build_int_cst (TREE_TYPE (vr1min), 1)); - } - /* Choose the anti-range if the range is effectively varying. */ - else if (vrp_val_is_min (*vr0min) - && vrp_val_is_max (*vr0max)) - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - /* Else choose the range. */ - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - /* If both are anti-ranges the result is the outer one. */ - ; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - /* The intersection is empty. */ - *vr0type = VR_UNDEFINED; - *vr0min = NULL_TREE; - *vr0max = NULL_TREE; - } - else - gcc_unreachable (); - } - else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1) - && (mineq || operand_less_p (vr1min, *vr0min) == 1)) - { - /* ( [ ] ) or ([ ] ) or ( [ ]) */ - if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - /* Choose the inner range. */ - ; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - /* Choose the right gap if the left is empty. */ - if (mineq) - { - *vr0type = VR_RANGE; - if (TREE_CODE (*vr0max) != INTEGER_CST) - *vr0min = *vr0max; - else if (TYPE_PRECISION (TREE_TYPE (*vr0max)) == 1 - && !TYPE_UNSIGNED (TREE_TYPE (*vr0max))) - *vr0min - = int_const_binop (MINUS_EXPR, *vr0max, - build_int_cst (TREE_TYPE (*vr0max), -1)); - else - *vr0min - = int_const_binop (PLUS_EXPR, *vr0max, - build_int_cst (TREE_TYPE (*vr0max), 1)); - *vr0max = vr1max; - } - /* Choose the left gap if the right is empty. */ - else if (maxeq) - { - *vr0type = VR_RANGE; - if (TREE_CODE (*vr0min) != INTEGER_CST) - *vr0max = *vr0min; - else if (TYPE_PRECISION (TREE_TYPE (*vr0min)) == 1 - && !TYPE_UNSIGNED (TREE_TYPE (*vr0min))) - *vr0max - = int_const_binop (PLUS_EXPR, *vr0min, - build_int_cst (TREE_TYPE (*vr0min), -1)); - else - *vr0max - = int_const_binop (MINUS_EXPR, *vr0min, - build_int_cst (TREE_TYPE (*vr0min), 1)); - *vr0min = vr1min; - } - /* Choose the anti-range if the range is effectively varying. */ - else if (vrp_val_is_min (vr1min) - && vrp_val_is_max (vr1max)) - ; - /* Choose the anti-range if it is ~[0,0], that range is special - enough to special case when vr1's range is relatively wide. - At least for types bigger than int - this covers pointers - and arguments to functions like ctz. */ - else if (*vr0min == *vr0max - && integer_zerop (*vr0min) - && ((TYPE_PRECISION (TREE_TYPE (*vr0min)) - >= TYPE_PRECISION (integer_type_node)) - || POINTER_TYPE_P (TREE_TYPE (*vr0min))) - && TREE_CODE (vr1max) == INTEGER_CST - && TREE_CODE (vr1min) == INTEGER_CST - && (wi::clz (wi::to_wide (vr1max) - wi::to_wide (vr1min)) - < TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2)) - ; - /* Else choose the range. */ - else - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - { - /* If both are anti-ranges the result is the outer one. */ - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - else if (vr1type == VR_ANTI_RANGE - && *vr0type == VR_RANGE) - { - /* The intersection is empty. */ - *vr0type = VR_UNDEFINED; - *vr0min = NULL_TREE; - *vr0max = NULL_TREE; - } - else - gcc_unreachable (); - } - else if ((operand_less_p (vr1min, *vr0max) == 1 - || operand_equal_p (vr1min, *vr0max, 0)) - && operand_less_p (*vr0min, vr1min) == 1) - { - /* [ ( ] ) or [ ]( ) */ - if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - *vr0max = vr1max; - else if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - *vr0min = vr1min; - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - if (TREE_CODE (vr1min) == INTEGER_CST) - *vr0max = int_const_binop (MINUS_EXPR, vr1min, - build_int_cst (TREE_TYPE (vr1min), 1)); - else - *vr0max = vr1min; - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - *vr0type = VR_RANGE; - if (TREE_CODE (*vr0max) == INTEGER_CST) - *vr0min = int_const_binop (PLUS_EXPR, *vr0max, - build_int_cst (TREE_TYPE (*vr0max), 1)); - else - *vr0min = *vr0max; - *vr0max = vr1max; - } - else - gcc_unreachable (); - } - else if ((operand_less_p (*vr0min, vr1max) == 1 - || operand_equal_p (*vr0min, vr1max, 0)) - && operand_less_p (vr1min, *vr0min) == 1) - { - /* ( [ ) ] or ( )[ ] */ - if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - *vr0min = vr1min; - else if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - *vr0max = vr1max; - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - if (TREE_CODE (vr1max) == INTEGER_CST) - *vr0min = int_const_binop (PLUS_EXPR, vr1max, - build_int_cst (TREE_TYPE (vr1max), 1)); - else - *vr0min = vr1max; - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - *vr0type = VR_RANGE; - if (TREE_CODE (*vr0min) == INTEGER_CST) - *vr0max = int_const_binop (MINUS_EXPR, *vr0min, - build_int_cst (TREE_TYPE (*vr0min), 1)); - else - *vr0max = *vr0min; - *vr0min = vr1min; - } - else - gcc_unreachable (); - } - - /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as - result for the intersection. That's always a conservative - correct estimate unless VR1 is a constant singleton range - in which case we choose that. */ - if (vr1type == VR_RANGE - && is_gimple_min_invariant (vr1min) - && vrp_operand_equal_p (vr1min, vr1max)) - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } -} - - -/* Intersect the two value-ranges *VR0 and *VR1 and store the result - in *VR0. This may not be the smallest possible such range. */ - void -value_range::intersect_helper (value_range *vr0, const value_range *vr1) -{ - /* If either range is VR_VARYING the other one wins. */ - if (vr1->varying_p ()) - return; - if (vr0->varying_p ()) - { - vr0->deep_copy (vr1); - return; - } - - /* When either range is VR_UNDEFINED the resulting range is - VR_UNDEFINED, too. */ - if (vr0->undefined_p ()) - return; - if (vr1->undefined_p ()) - { - set_value_range_to_undefined (vr0); - return; - } - - /* Save the original vr0 so we can return it as conservative intersection - result when our worker turns things to varying. */ - value_range saved (*vr0); - - value_range_kind vr0type = vr0->kind (); - tree vr0min = vr0->min (); - tree vr0max = vr0->max (); - intersect_ranges (&vr0type, &vr0min, &vr0max, - vr1->kind (), vr1->min (), vr1->max ()); - /* Make sure to canonicalize the result though as the inversion of a - VR_RANGE can still be a VR_RANGE. */ - vr0->set_and_canonicalize (vr0type, vr0min, vr0max, vr0->m_equiv); - /* If that failed, use the saved original VR0. */ - if (vr0->varying_p ()) - { - *vr0 = saved; - return; - } - /* If the result is VR_UNDEFINED there is no need to mess with - the equivalencies. */ - if (vr0->undefined_p ()) - return; - - /* The resulting set of equivalences for range intersection is the union of - the two sets. */ - if (vr0->m_equiv && vr1->m_equiv && vr0->m_equiv != vr1->m_equiv) - bitmap_ior_into (vr0->m_equiv, vr1->m_equiv); - else if (vr1->m_equiv && !vr0->m_equiv) - { - /* All equivalence bitmaps are allocated from the same obstack. So - we can use the obstack associated with VR to allocate vr0->equiv. */ - vr0->m_equiv = BITMAP_ALLOC (vr1->m_equiv->obstack); - bitmap_copy (m_equiv, vr1->m_equiv); - } -} - -void -value_range::intersect (const value_range *other) +value_range_equiv::intersect (const value_range_equiv *other) { if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -6004,7 +4656,36 @@ dump_value_range (dump_file, other); fprintf (dump_file, "\n"); } - intersect_helper (this, other); + + /* If THIS is varying we want to pick up equivalences from OTHER. + Just special-case this here rather than trying to fixup after the + fact. */ + if (this->varying_p ()) + this->deep_copy (other); + else + { + value_range tem = intersect_helper (this, other); + this->update (tem.min (), tem.max (), tem.kind ()); + + /* If the result is VR_UNDEFINED there is no need to mess with + equivalencies. */ + if (!undefined_p ()) + { + /* The resulting set of equivalences for range intersection + is the union of the two sets. */ + if (m_equiv && other->m_equiv && m_equiv != other->m_equiv) + bitmap_ior_into (m_equiv, other->m_equiv); + else if (other->m_equiv && !m_equiv) + { + /* All equivalence bitmaps are allocated from the same + obstack. So we can use the obstack associated with + VR to allocate this->m_equiv. */ + m_equiv = BITMAP_ALLOC (other->m_equiv->obstack); + bitmap_copy (m_equiv, other->m_equiv); + } + } + } + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "to\n "); @@ -6013,79 +4694,8 @@ } } -/* Meet operation for value ranges. Given two value ranges VR0 and - VR1, store in VR0 a range that contains both VR0 and VR1. This - may not be the smallest possible such range. */ - void -value_range::union_helper (value_range *vr0, const value_range *vr1) -{ - if (vr1->undefined_p ()) - { - /* VR0 already has the resulting range. */ - return; - } - - if (vr0->undefined_p ()) - { - vr0->deep_copy (vr1); - return; - } - - if (vr0->varying_p ()) - { - /* Nothing to do. VR0 already has the resulting range. */ - return; - } - - if (vr1->varying_p ()) - { - set_value_range_to_varying (vr0); - return; - } - - value_range saved (*vr0); - value_range_kind vr0type = vr0->kind (); - tree vr0min = vr0->min (); - tree vr0max = vr0->max (); - union_ranges (&vr0type, &vr0min, &vr0max, - vr1->kind (), vr1->min (), vr1->max ()); - *vr0 = value_range (vr0type, vr0min, vr0max); - if (vr0->varying_p ()) - { - /* Failed to find an efficient meet. Before giving up and setting - the result to VARYING, see if we can at least derive a useful - anti-range. */ - if (range_includes_zero_p (&saved) == 0 - && range_includes_zero_p (vr1) == 0) - { - set_value_range_to_nonnull (vr0, saved.type ()); - - /* Since this meet operation did not result from the meeting of - two equivalent names, VR0 cannot have any equivalences. */ - if (vr0->m_equiv) - bitmap_clear (vr0->m_equiv); - return; - } - - set_value_range_to_varying (vr0); - return; - } - vr0->set_and_canonicalize (vr0->kind (), vr0->min (), vr0->max (), - vr0->equiv ()); - if (vr0->varying_p ()) - return; - - /* The resulting set of equivalences is always the intersection of - the two sets. */ - if (vr0->m_equiv && vr1->m_equiv && vr0->m_equiv != vr1->m_equiv) - bitmap_and_into (vr0->m_equiv, vr1->m_equiv); - else if (vr0->m_equiv && !vr1->m_equiv) - bitmap_clear (vr0->m_equiv); -} - -void -value_range::union_ (const value_range *other) +value_range_equiv::union_ (const value_range_equiv *other) { if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -6095,7 +4705,24 @@ dump_value_range (dump_file, other); fprintf (dump_file, "\n"); } - union_helper (this, other); + + /* If THIS is undefined we want to pick up equivalences from OTHER. + Just special-case this here rather than trying to fixup after the fact. */ + if (this->undefined_p ()) + this->deep_copy (other); + else + { + value_range tem = union_helper (this, other); + this->update (tem.min (), tem.max (), tem.kind ()); + + /* The resulting set of equivalences is always the intersection of + the two sets. */ + if (this->m_equiv && other->m_equiv && this->m_equiv != other->m_equiv) + bitmap_and_into (this->m_equiv, other->m_equiv); + else if (this->m_equiv && !other->m_equiv) + bitmap_clear (this->m_equiv); + } + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "to\n "); @@ -6112,7 +4739,7 @@ vrp_prop::visit_phi (gphi *phi) { tree lhs = PHI_RESULT (phi); - value_range vr_result; + value_range_equiv vr_result; extract_range_from_phi_node (phi, &vr_result); if (update_value_range (lhs, &vr_result)) { @@ -6138,6 +4765,7 @@ class vrp_folder : public substitute_and_fold_engine { public: + vrp_folder () : substitute_and_fold_engine (/* Fold all stmts. */ true) { } tree get_value (tree) FINAL OVERRIDE; bool fold_stmt (gimple_stmt_iterator *) FINAL OVERRIDE; bool fold_predicate_in (gimple_stmt_iterator *); @@ -6308,7 +4936,7 @@ op = lhs_of_dominating_assert (op, bb, stmt); - const value_range *vr = vr_values->get_value_range (op); + const value_range_equiv *vr = vr_values->get_value_range (op); if (vr->undefined_p () || vr->varying_p () || vr->symbolic_p ()) @@ -6374,7 +5002,7 @@ { edge dummy_e; tree dummy_tree; - value_range new_vr; + value_range_equiv new_vr; vr_values->extract_range_from_stmt (stmt, &dummy_e, &dummy_tree, &new_vr); tree singleton; @@ -6550,7 +5178,7 @@ if (!name) continue; - const value_range *vr = get_value_range (name); + const value_range_equiv *vr = get_value_range (name); if (!name || !vr->constant_p ()) continue; @@ -6558,9 +5186,7 @@ && range_includes_zero_p (vr) == 0) set_ptr_nonnull (name); else if (!POINTER_TYPE_P (TREE_TYPE (name))) - set_range_info (name, vr->kind (), - wi::to_wide (vr->min ()), - wi::to_wide (vr->max ())); + set_range_info (name, *vr); } /* If we're checking array refs, we want to merge information on @@ -6755,18 +5381,18 @@ value_range vr0, vr1; determine_value_range_1 (&vr0, TREE_OPERAND (expr, 0)); determine_value_range_1 (&vr1, TREE_OPERAND (expr, 1)); - extract_range_from_binary_expr_1 (vr, TREE_CODE (expr), TREE_TYPE (expr), - &vr0, &vr1); + range_fold_binary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr), + &vr0, &vr1); } else if (UNARY_CLASS_P (expr)) { value_range vr0; determine_value_range_1 (&vr0, TREE_OPERAND (expr, 0)); - extract_range_from_unary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr), - &vr0, TREE_TYPE (TREE_OPERAND (expr, 0))); + range_fold_unary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr), + &vr0, TREE_TYPE (TREE_OPERAND (expr, 0))); } else if (TREE_CODE (expr) == INTEGER_CST) - set_value_range_to_value (vr, expr, NULL); + vr->set (expr); else { value_range_kind kind; @@ -6776,10 +5402,11 @@ if (TREE_CODE (expr) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (expr)) && (kind = get_range_info (expr, &min, &max)) != VR_VARYING) - set_value_range (vr, kind, wide_int_to_tree (TREE_TYPE (expr), min), - wide_int_to_tree (TREE_TYPE (expr), max), NULL); + vr->set (wide_int_to_tree (TREE_TYPE (expr), min), + wide_int_to_tree (TREE_TYPE (expr), max), + kind); else - set_value_range_to_varying (vr); + vr->set_varying (TREE_TYPE (expr)); } }