/* Support routines for Value Range Propagation (VRP).
- Copyright (C) 2005-2017 Free Software Foundation, Inc.
+ Copyright (C) 2005-2019 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>.
This file is part of GCC.
#include "attribs.h"
#include "vr-values.h"
#include "builtins.h"
+#include "range-op.h"
+
+static bool
+ranges_from_anti_range (const value_range_base *ar,
+ value_range_base *vr0, value_range_base *vr1,
+ bool handle_pointers = false);
/* Set of SSA names found live during the RPO traversal of the function
for still active basic-blocks. */
static sbitmap *live;
-/* Return true if the SSA name NAME is live on the edge E. */
-
-static bool
-live_on_edge (edge e, tree name)
-{
- return (live[e->dest->index]
- && bitmap_bit_p (live[e->dest->index], SSA_NAME_VERSION (name)));
-}
-
-/* Location information for ASSERT_EXPRs. Each instance of this
- structure describes an ASSERT_EXPR for an SSA name. Since a single
- SSA name may have more than one assertion associated with it, these
- locations are kept in a linked list attached to the corresponding
- SSA name. */
-struct assert_locus
+void
+value_range::set_equiv (bitmap equiv)
{
- /* Basic block where the assertion would be inserted. */
- basic_block bb;
-
- /* Some assertions need to be inserted on an edge (e.g., assertions
- generated by COND_EXPRs). In those cases, BB will be NULL. */
- edge e;
-
- /* Pointer to the statement that generated this assertion. */
- gimple_stmt_iterator si;
-
- /* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */
- enum tree_code comp_code;
-
- /* Value being compared against. */
- tree val;
-
- /* Expression to compare. */
- tree expr;
-
- /* Next node in the linked list. */
- assert_locus *next;
-};
-
-/* If bit I is present, it means that SSA name N_i has a list of
- assertions that should be inserted in the IL. */
-static bitmap need_assert_for;
+ if (undefined_p () || varying_p ())
+ equiv = NULL;
+ /* Since updating the equivalence set involves deep copying the
+ bitmaps, only do it if absolutely necessary.
-/* Array of locations lists where to insert assertions. ASSERTS_FOR[I]
- holds a list of ASSERT_LOCUS_T nodes that describe where
- ASSERT_EXPRs for SSA name N_I should be inserted. */
-static assert_locus **asserts_for;
+ All equivalence bitmaps are allocated from the same obstack. So
+ we can use the obstack associated with EQUIV to allocate vr->equiv. */
+ if (m_equiv == NULL
+ && equiv != NULL)
+ m_equiv = BITMAP_ALLOC (equiv->obstack);
-vec<edge> to_remove_edges;
-vec<switch_update> to_update_switch_stmts;
+ if (equiv != m_equiv)
+ {
+ if (equiv && !bitmap_empty_p (equiv))
+ bitmap_copy (m_equiv, equiv);
+ else
+ bitmap_clear (m_equiv);
+ }
+}
+/* Initialize value_range. */
-/* Return the maximum value for TYPE. */
+void
+value_range::set (enum value_range_kind kind, tree min, tree max,
+ bitmap equiv)
+{
+ value_range_base::set (kind, min, max);
+ set_equiv (equiv);
+ if (flag_checking)
+ check ();
+}
-tree
-vrp_val_max (const_tree type)
+value_range_base::value_range_base (value_range_kind kind, tree min, tree max)
{
- if (!INTEGRAL_TYPE_P (type))
- return NULL_TREE;
+ set (kind, min, max);
+}
- return TYPE_MAX_VALUE (type);
+value_range::value_range (value_range_kind kind, tree min, tree max,
+ bitmap equiv)
+{
+ m_equiv = NULL;
+ set (kind, min, max, equiv);
}
-/* Return the minimum value for TYPE. */
+value_range::value_range (const value_range_base &other)
+{
+ m_equiv = NULL;
+ set (other.kind (), other.min(), other.max (), NULL);
+}
-tree
-vrp_val_min (const_tree type)
+value_range_base::value_range_base (tree type)
{
- if (!INTEGRAL_TYPE_P (type))
- return NULL_TREE;
+ set_varying (type);
+}
- return TYPE_MIN_VALUE (type);
+value_range_base::value_range_base (enum value_range_kind kind,
+ tree type,
+ const wide_int &wmin,
+ const wide_int &wmax)
+{
+ tree min = wide_int_to_tree (type, wmin);
+ tree max = wide_int_to_tree (type, wmax);
+ gcc_checking_assert (kind == VR_RANGE || kind == VR_ANTI_RANGE);
+ set (kind, min, max);
}
-/* 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. */
+value_range_base::value_range_base (tree type,
+ const wide_int &wmin,
+ const wide_int &wmax)
+{
+ tree min = wide_int_to_tree (type, wmin);
+ tree max = wide_int_to_tree (type, wmax);
+ set (VR_RANGE, min, max);
+}
-bool
-vrp_val_is_max (const_tree val)
+value_range_base::value_range_base (tree min, tree max)
{
- tree type_max = vrp_val_max (TREE_TYPE (val));
- return (val == type_max
- || (type_max != NULL_TREE
- && operand_equal_p (val, type_max, 0)));
+ set (VR_RANGE, min, max);
}
-/* Return whether VAL is equal to the minimum value of its type. */
+/* Like set, but keep the equivalences in place. */
-bool
-vrp_val_is_min (const_tree val)
+void
+value_range::update (value_range_kind kind, tree min, tree max)
{
- tree type_min = vrp_val_min (TREE_TYPE (val));
- return (val == type_min
- || (type_min != NULL_TREE
- && operand_equal_p (val, type_min, 0)));
+ set (kind, min, max,
+ (kind != VR_UNDEFINED && kind != VR_VARYING) ? m_equiv : NULL);
}
+/* Copy value_range in FROM into THIS while avoiding bitmap sharing.
-/* Set value range VR to VR_UNDEFINED. */
+ Note: The code that avoids the bitmap sharing looks at the existing
+ this->m_equiv, so this function cannot be used to initalize an
+ object. Use the constructors for initialization. */
-static inline void
-set_value_range_to_undefined (value_range *vr)
+void
+value_range::deep_copy (const value_range *from)
{
- vr->type = VR_UNDEFINED;
- vr->min = vr->max = NULL_TREE;
- if (vr->equiv)
- bitmap_clear (vr->equiv);
+ set (from->m_kind, from->min (), from->max (), from->m_equiv);
}
-/* Set value range VR to VR_VARYING. */
-
void
-set_value_range_to_varying (value_range *vr)
+value_range::move (value_range *from)
{
- vr->type = VR_VARYING;
- vr->min = vr->max = NULL_TREE;
- if (vr->equiv)
- bitmap_clear (vr->equiv);
+ set (from->m_kind, from->min (), from->max ());
+ m_equiv = from->m_equiv;
+ from->m_equiv = NULL;
}
-/* Set value range VR to {T, MIN, MAX, EQUIV}. */
+/* Check the validity of the range. */
void
-set_value_range (value_range *vr, enum value_range_type t, tree min,
- tree max, bitmap equiv)
+value_range_base::check ()
{
- /* Check the validity of the range. */
- if (flag_checking
- && (t == VR_RANGE || t == VR_ANTI_RANGE))
- {
- int cmp;
-
- gcc_assert (min && max);
-
- gcc_assert (!TREE_OVERFLOW_P (min) && !TREE_OVERFLOW_P (max));
-
- if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
- gcc_assert (!vrp_val_is_min (min) || !vrp_val_is_max (max));
-
- cmp = compare_values (min, max);
- gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
- }
-
- if (flag_checking
- && (t == VR_UNDEFINED || t == VR_VARYING))
+ switch (m_kind)
{
- gcc_assert (min == NULL_TREE && max == NULL_TREE);
- gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
- }
+ case VR_RANGE:
+ case VR_ANTI_RANGE:
+ {
+ int cmp;
- vr->type = t;
- vr->min = min;
- vr->max = max;
+ gcc_assert (m_min && m_max);
- /* Since updating the equivalence set involves deep copying the
- bitmaps, only do it if absolutely necessary.
+ gcc_assert (!TREE_OVERFLOW_P (m_min) && !TREE_OVERFLOW_P (m_max));
- All equivalence bitmaps are allocated from the same obstack. So
- we can use the obstack associated with EQUIV to allocate vr->equiv. */
- if (vr->equiv == NULL
- && equiv != NULL)
- vr->equiv = BITMAP_ALLOC (equiv->obstack);
+ /* 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));
- if (equiv != vr->equiv)
- {
- if (equiv && !bitmap_empty_p (equiv))
- bitmap_copy (vr->equiv, equiv);
- else
- bitmap_clear (vr->equiv);
+ cmp = compare_values (m_min, m_max);
+ gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
+ break;
+ }
+ case VR_UNDEFINED:
+ gcc_assert (!min () && !max ());
+ break;
+ case VR_VARYING:
+ gcc_assert (m_min && m_max);
+ break;
+ default:
+ gcc_unreachable ();
}
}
-
-/* Set value range VR to the canonical form of {T, MIN, MAX, EQUIV}.
- This means adjusting T, 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
-set_and_canonicalize_value_range (value_range *vr, enum value_range_type t,
- tree min, tree max, bitmap equiv)
+value_range::check ()
{
- /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */
- if (t == VR_UNDEFINED)
- {
- set_value_range_to_undefined (vr);
- return;
- }
- else if (t == VR_VARYING)
+ value_range_base::check ();
+ switch (m_kind)
{
- set_value_range_to_varying (vr);
- return;
- }
-
- /* Nothing to canonicalize for symbolic ranges. */
- if (TREE_CODE (min) != INTEGER_CST
- || TREE_CODE (max) != INTEGER_CST)
- {
- set_value_range (vr, t, min, max, equiv);
- return;
+ case VR_UNDEFINED:
+ case VR_VARYING:
+ gcc_assert (!m_equiv || bitmap_empty_p (m_equiv));
+ default:;
}
+}
- /* 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_value_range_to_varying (vr);
- 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_value_range_to_varying (vr);
- return;
- }
-
- t = t == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
- }
+/* Equality operator. We purposely do not overload ==, to avoid
+ confusion with the equality bitmap in the derived value_range
+ class. */
- /* Anti-ranges that can be represented as ranges should be so. */
- if (t == VR_ANTI_RANGE)
- {
- bool is_min = vrp_val_is_min (min);
- bool is_max = vrp_val_is_max (max);
+bool
+value_range_base::equal_p (const value_range_base &other) const
+{
+ /* Ignore types for undefined. All undefines are equal. */
+ if (undefined_p ())
+ return m_kind == other.m_kind;
- if (is_min && is_max)
- {
- /* We cannot deal with empty ranges, drop to varying.
- ??? This could be VR_UNDEFINED instead. */
- set_value_range_to_varying (vr);
- 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));
- t = 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));
- t = 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));
- t = VR_RANGE;
- }
- }
+ return (m_kind == other.m_kind
+ && vrp_operand_equal_p (m_min, other.m_min)
+ && vrp_operand_equal_p (m_max, other.m_max));
+}
- /* 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. */
+/* Returns TRUE if THIS == OTHER. Ignores the equivalence bitmap if
+ IGNORE_EQUIVS is TRUE. */
- set_value_range (vr, t, min, max, equiv);
+bool
+value_range::equal_p (const value_range &other, bool ignore_equivs) const
+{
+ return (value_range_base::equal_p (other)
+ && (ignore_equivs
+ || vrp_bitmap_equal_p (m_equiv, other.m_equiv)));
}
-/* Copy value range FROM into value range TO. */
+/* Return TRUE if this is a symbolic range. */
-void
-copy_value_range (value_range *to, value_range *from)
+bool
+value_range_base::symbolic_p () const
{
- set_value_range (to, from->type, from->min, from->max, from->equiv);
+ return (!varying_p ()
+ && !undefined_p ()
+ && (!is_gimple_min_invariant (m_min)
+ || !is_gimple_min_invariant (m_max)));
}
-/* 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. */
+/* 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]. */
-void
-set_value_range_to_value (value_range *vr, tree val, bitmap equiv)
+bool
+value_range_base::constant_p () const
{
- gcc_assert (is_gimple_min_invariant (val));
- if (TREE_OVERFLOW_P (val))
- val = drop_tree_overflow (val);
- set_value_range (vr, VR_RANGE, val, val, equiv);
+ return (!varying_p ()
+ && !undefined_p ()
+ && TREE_CODE (m_min) == INTEGER_CST
+ && TREE_CODE (m_max) == INTEGER_CST);
}
-/* Set value range VR to a non-NULL range of type TYPE. */
-
void
-set_value_range_to_nonnull (value_range *vr, tree type)
+value_range_base::set_undefined ()
{
- tree zero = build_int_cst (type, 0);
- set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
+ m_kind = VR_UNDEFINED;
+ m_min = m_max = NULL;
}
-
-/* Set value range VR to a NULL range of type TYPE. */
-
void
-set_value_range_to_null (value_range *vr, tree type)
+value_range::set_undefined ()
{
- set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv);
+ set (VR_UNDEFINED, NULL, NULL, NULL);
}
-
-/* If abs (min) < abs (max), set VR to [-max, max], if
- abs (min) >= abs (max), set VR to [-min, min]. */
-
-static void
-abs_extent_range (value_range *vr, tree min, tree max)
+void
+value_range_base::set_varying (tree type)
{
- int cmp;
-
- gcc_assert (TREE_CODE (min) == INTEGER_CST);
- gcc_assert (TREE_CODE (max) == INTEGER_CST);
- gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (min)));
- gcc_assert (!TYPE_UNSIGNED (TREE_TYPE (min)));
- min = fold_unary (ABS_EXPR, TREE_TYPE (min), min);
- max = fold_unary (ABS_EXPR, TREE_TYPE (max), max);
- if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
- {
- set_value_range_to_varying (vr);
- return;
- }
- cmp = compare_values (min, max);
- if (cmp == -1)
- min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), max);
- else if (cmp == 0 || cmp == 1)
+ m_kind = VR_VARYING;
+ if (supports_type_p (type))
{
- max = min;
- min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), min);
+ m_min = vrp_val_min (type, true);
+ m_max = vrp_val_max (type, true);
}
else
- {
- set_value_range_to_varying (vr);
- return;
- }
- set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL);
+ /* We can't do anything range-wise with these types. */
+ m_min = m_max = error_mark_node;
}
-/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
-
-bool
-vrp_operand_equal_p (const_tree val1, const_tree val2)
+void
+value_range::set_varying (tree type)
{
- if (val1 == val2)
- return true;
- if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
- return false;
- return true;
+ value_range_base::set_varying (type);
+ equiv_clear ();
}
-/* Return true, if the bitmaps B1 and B2 are equal. */
+/* Return TRUE if it is possible that range contains VAL. */
bool
-vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
+value_range_base::may_contain_p (tree val) const
{
- return (b1 == b2
- || ((!b1 || bitmap_empty_p (b1))
- && (!b2 || bitmap_empty_p (b2)))
- || (b1 && b2
- && bitmap_equal_p (b1, b2)));
+ return value_inside_range (val) != 0;
}
-/* Return true if VR is ~[0, 0]. */
-
-bool
-range_is_nonnull (value_range *vr)
+void
+value_range::equiv_clear ()
{
- return vr->type == VR_ANTI_RANGE
- && integer_zerop (vr->min)
- && integer_zerop (vr->max);
+ if (m_equiv)
+ bitmap_clear (m_equiv);
}
+/* Add VAR and VAR's equivalence set (VAR_VR) to the equivalence
+ bitmap. If no equivalence table has been created, OBSTACK is the
+ obstack to use (NULL for the default obstack).
-/* Return true if VR is [0, 0]. */
-
-static inline bool
-range_is_null (value_range *vr)
-{
- return vr->type == VR_RANGE
- && integer_zerop (vr->min)
- && integer_zerop (vr->max);
-}
-
-/* Return true if max and min of VR are INTEGER_CST. It's not necessary
- a singleton. */
+ This is the central point where equivalence processing can be
+ turned on/off. */
-bool
-range_int_cst_p (value_range *vr)
+void
+value_range::equiv_add (const_tree var,
+ const value_range *var_vr,
+ bitmap_obstack *obstack)
{
- return (vr->type == VR_RANGE
- && TREE_CODE (vr->max) == INTEGER_CST
- && TREE_CODE (vr->min) == INTEGER_CST);
+ if (!m_equiv)
+ m_equiv = BITMAP_ALLOC (obstack);
+ unsigned ver = SSA_NAME_VERSION (var);
+ bitmap_set_bit (m_equiv, ver);
+ if (var_vr && var_vr->m_equiv)
+ bitmap_ior_into (m_equiv, var_vr->m_equiv);
}
-/* Return true if VR is a INTEGER_CST singleton. */
+/* 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
-range_int_cst_singleton_p (value_range *vr)
+value_range_base::singleton_p (tree *result) const
{
- return (range_int_cst_p (vr)
- && tree_int_cst_equal (vr->min, vr->max));
-}
+ if (m_kind == VR_ANTI_RANGE)
+ {
+ if (nonzero_p ())
+ {
+ if (TYPE_PRECISION (type ()) == 1)
+ {
+ if (result)
+ *result = m_max;
+ return true;
+ }
+ return false;
+ }
+ if (num_pairs () == 1)
+ {
+ value_range_base vr0, vr1;
+ ranges_from_anti_range (this, &vr0, &vr1, true);
+ return vr0.singleton_p (result);
+ }
+ }
+ if (m_kind == VR_RANGE
+ && vrp_operand_equal_p (min (), max ())
+ && is_gimple_min_invariant (min ()))
+ {
+ if (result)
+ *result = min ();
+ return true;
+ }
+ return false;
+}
+
+tree
+value_range_base::type () const
+{
+ gcc_checking_assert (m_min);
+ return TREE_TYPE (min ());
+}
+
+void
+value_range_base::dump (FILE *file) const
+{
+ if (undefined_p ())
+ fprintf (file, "UNDEFINED");
+ else if (m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE)
+ {
+ tree ttype = type ();
+
+ print_generic_expr (file, ttype);
+ fprintf (file, " ");
+
+ fprintf (file, "%s[", (m_kind == VR_ANTI_RANGE) ? "~" : "");
+
+ if (INTEGRAL_TYPE_P (ttype)
+ && !TYPE_UNSIGNED (ttype)
+ && vrp_val_is_min (min ())
+ && TYPE_PRECISION (ttype) != 1)
+ fprintf (file, "-INF");
+ else
+ print_generic_expr (file, min ());
+
+ fprintf (file, ", ");
+
+ if (supports_type_p (ttype)
+ && vrp_val_is_max (max (), true)
+ && TYPE_PRECISION (ttype) != 1)
+ fprintf (file, "+INF");
+ else
+ print_generic_expr (file, max ());
+
+ fprintf (file, "]");
+ }
+ else if (varying_p ())
+ {
+ print_generic_expr (file, type ());
+ fprintf (file, " VARYING");
+ }
+ else
+ gcc_unreachable ();
+}
+
+void
+value_range_base::dump () const
+{
+ dump (stderr);
+}
+
+void
+value_range::dump (FILE *file) const
+{
+ value_range_base::dump (file);
+ if ((m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE)
+ && m_equiv)
+ {
+ 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);
+ }
+}
+
+void
+value_range::dump () const
+{
+ dump (stderr);
+}
+
+void
+dump_value_range (FILE *file, const value_range *vr)
+{
+ if (!vr)
+ fprintf (file, "[]");
+ else
+ vr->dump (file);
+}
+
+void
+dump_value_range (FILE *file, const value_range_base *vr)
+{
+ if (!vr)
+ fprintf (file, "[]");
+ else
+ vr->dump (file);
+}
+
+DEBUG_FUNCTION void
+debug (const value_range_base *vr)
+{
+ dump_value_range (stderr, vr);
+}
+
+DEBUG_FUNCTION void
+debug (const value_range_base &vr)
+{
+ dump_value_range (stderr, &vr);
+}
+
+DEBUG_FUNCTION void
+debug (const value_range *vr)
+{
+ dump_value_range (stderr, vr);
+}
+
+DEBUG_FUNCTION void
+debug (const value_range &vr)
+{
+ dump_value_range (stderr, &vr);
+}
+
+/* Return true if the SSA name NAME is live on the edge E. */
+
+static bool
+live_on_edge (edge e, tree name)
+{
+ return (live[e->dest->index]
+ && bitmap_bit_p (live[e->dest->index], SSA_NAME_VERSION (name)));
+}
+
+/* Location information for ASSERT_EXPRs. Each instance of this
+ structure describes an ASSERT_EXPR for an SSA name. Since a single
+ SSA name may have more than one assertion associated with it, these
+ locations are kept in a linked list attached to the corresponding
+ SSA name. */
+struct assert_locus
+{
+ /* Basic block where the assertion would be inserted. */
+ basic_block bb;
+
+ /* Some assertions need to be inserted on an edge (e.g., assertions
+ generated by COND_EXPRs). In those cases, BB will be NULL. */
+ edge e;
+
+ /* Pointer to the statement that generated this assertion. */
+ gimple_stmt_iterator si;
+
+ /* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */
+ enum tree_code comp_code;
+
+ /* Value being compared against. */
+ tree val;
+
+ /* Expression to compare. */
+ tree expr;
+
+ /* Next node in the linked list. */
+ assert_locus *next;
+};
+
+/* If bit I is present, it means that SSA name N_i has a list of
+ assertions that should be inserted in the IL. */
+static bitmap need_assert_for;
+
+/* Array of locations lists where to insert assertions. ASSERTS_FOR[I]
+ holds a list of ASSERT_LOCUS_T nodes that describe where
+ 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, bool handle_pointers)
+{
+ if (INTEGRAL_TYPE_P (type))
+ return TYPE_MAX_VALUE (type);
+ if (POINTER_TYPE_P (type) && handle_pointers)
+ {
+ wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+ return wide_int_to_tree (const_cast<tree> (type), max);
+ }
+ return NULL_TREE;
+}
+
+/* Return the minimum value for TYPE. */
+
+tree
+vrp_val_min (const_tree type, bool handle_pointers)
+{
+ if (INTEGRAL_TYPE_P (type))
+ return TYPE_MIN_VALUE (type);
+ if (POINTER_TYPE_P (type) && handle_pointers)
+ return build_zero_cst (const_cast<tree> (type));
+ return NULL_TREE;
+}
+
+/* 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, bool handle_pointers)
+{
+ tree type_max = vrp_val_max (TREE_TYPE (val), handle_pointers);
+ 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, bool handle_pointers)
+{
+ tree type_min = vrp_val_min (TREE_TYPE (val), handle_pointers);
+ 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
+ return the new range type.
+
+ SGN gives the sign of the values described by the range. */
+
+enum value_range_kind
+intersect_range_with_nonzero_bits (enum value_range_kind vr_type,
+ wide_int *min, wide_int *max,
+ const wide_int &nonzero_bits,
+ signop sgn)
+{
+ if (vr_type == VR_ANTI_RANGE)
+ {
+ /* The VR_ANTI_RANGE is equivalent to the union of the ranges
+ A: [-INF, *MIN) and B: (*MAX, +INF]. First use NONZERO_BITS
+ to create an inclusive upper bound for A and an inclusive lower
+ bound for B. */
+ wide_int a_max = wi::round_down_for_mask (*min - 1, nonzero_bits);
+ wide_int b_min = wi::round_up_for_mask (*max + 1, nonzero_bits);
+
+ /* If the calculation of A_MAX wrapped, A is effectively empty
+ and A_MAX is the highest value that satisfies NONZERO_BITS.
+ Likewise if the calculation of B_MIN wrapped, B is effectively
+ empty and B_MIN is the lowest value that satisfies NONZERO_BITS. */
+ bool a_empty = wi::ge_p (a_max, *min, sgn);
+ bool b_empty = wi::le_p (b_min, *max, sgn);
+
+ /* If both A and B are empty, there are no valid values. */
+ if (a_empty && b_empty)
+ return VR_UNDEFINED;
+
+ /* If exactly one of A or B is empty, return a VR_RANGE for the
+ other one. */
+ if (a_empty || b_empty)
+ {
+ *min = b_min;
+ *max = a_max;
+ gcc_checking_assert (wi::le_p (*min, *max, sgn));
+ return VR_RANGE;
+ }
+
+ /* Update the VR_ANTI_RANGE bounds. */
+ *min = a_max + 1;
+ *max = b_min - 1;
+ gcc_checking_assert (wi::le_p (*min, *max, sgn));
+
+ /* Now check whether the excluded range includes any values that
+ satisfy NONZERO_BITS. If not, switch to a full VR_RANGE. */
+ if (wi::round_up_for_mask (*min, nonzero_bits) == b_min)
+ {
+ unsigned int precision = min->get_precision ();
+ *min = wi::min_value (precision, sgn);
+ *max = wi::max_value (precision, sgn);
+ vr_type = VR_RANGE;
+ }
+ }
+ if (vr_type == VR_RANGE)
+ {
+ *max = wi::round_down_for_mask (*max, nonzero_bits);
+
+ /* Check that the range contains at least one valid value. */
+ if (wi::gt_p (*min, *max, sgn))
+ return VR_UNDEFINED;
+
+ *min = wi::round_up_for_mask (*min, nonzero_bits);
+ gcc_checking_assert (wi::le_p (*min, *max, sgn));
+ }
+ return vr_type;
+}
+
+
+/* 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_base::set (enum value_range_kind kind, tree min, tree max)
+{
+ /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */
+ if (kind == VR_UNDEFINED)
+ {
+ set_undefined ();
+ return;
+ }
+ else if (kind == VR_VARYING)
+ {
+ gcc_assert (TREE_TYPE (min) == TREE_TYPE (max));
+ tree typ = TREE_TYPE (min);
+ if (supports_type_p (typ))
+ {
+ gcc_assert (vrp_val_min (typ, true));
+ gcc_assert (vrp_val_max (typ, true));
+ }
+ set_varying (typ);
+ return;
+ }
+
+ /* Convert POLY_INT_CST bounds into worst-case INTEGER_CST bounds. */
+ if (POLY_INT_CST_P (min))
+ {
+ tree type_min = vrp_val_min (TREE_TYPE (min), true);
+ widest_int lb
+ = constant_lower_bound_with_limit (wi::to_poly_widest (min),
+ wi::to_widest (type_min));
+ min = wide_int_to_tree (TREE_TYPE (min), lb);
+ }
+ if (POLY_INT_CST_P (max))
+ {
+ tree type_max = vrp_val_max (TREE_TYPE (max), true);
+ widest_int ub
+ = constant_upper_bound_with_limit (wi::to_poly_widest (max),
+ wi::to_widest (type_max));
+ max = wide_int_to_tree (TREE_TYPE (max), ub);
+ }
+
+ /* Nothing to canonicalize for symbolic ranges. */
+ if (TREE_CODE (min) != INTEGER_CST
+ || TREE_CODE (max) != INTEGER_CST)
+ {
+ m_kind = kind;
+ m_min = min;
+ m_max = max;
+ 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 (TREE_TYPE (min));
+ 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 (TREE_TYPE (min));
+ return;
+ }
+
+ kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
+ }
+
+ tree type = TREE_TYPE (min);
+
+ /* 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. */
+ 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 (type);
+ 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
+ /* Allow non-zero pointers to be normalized to [1,MAX]. */
+ || (POINTER_TYPE_P (TREE_TYPE (min))
+ && integer_zerop (min)))
+ {
+ tree one = build_int_cst (TREE_TYPE (max), 1);
+ min = int_const_binop (PLUS_EXPR, max, one);
+ max = vrp_val_max (TREE_TYPE (max), true);
+ 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;
+ }
+ }
+
+ /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
+
+ Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
+ restrict those to a subset of what actually fits in the type.
+ Instead use the extremes of the type precision which will allow
+ compare_range_with_value() to check if a value is inside a range,
+ whereas if we used TYPE_*_VAL, said function would just punt
+ upon seeing a VARYING. */
+ unsigned prec = TYPE_PRECISION (type);
+ signop sign = TYPE_SIGN (type);
+ if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign))
+ && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign)))
+ {
+ if (kind == VR_RANGE)
+ set_varying (type);
+ else if (kind == VR_ANTI_RANGE)
+ set_undefined ();
+ else
+ gcc_unreachable ();
+ return;
+ }
+
+ /* 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. */
+
+ m_kind = kind;
+ m_min = min;
+ m_max = max;
+ if (flag_checking)
+ check ();
+}
+
+void
+value_range_base::set (tree val)
+{
+ gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
+ if (TREE_OVERFLOW_P (val))
+ val = drop_tree_overflow (val);
+ set (VR_RANGE, val, val);
+}
+
+void
+value_range::set (tree val)
+{
+ gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
+ if (TREE_OVERFLOW_P (val))
+ val = drop_tree_overflow (val);
+ set (VR_RANGE, val, val, NULL);
+}
+
+/* Set value range VR to a nonzero range of type TYPE. */
+
+void
+value_range_base::set_nonzero (tree type)
+{
+ tree zero = build_int_cst (type, 0);
+ set (VR_ANTI_RANGE, zero, zero);
+}
+
+/* Set value range VR to a ZERO range of type TYPE. */
+
+void
+value_range_base::set_zero (tree type)
+{
+ set (build_int_cst (type, 0));
+}
+
+/* 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)));
+}
+
+static bool
+range_has_numeric_bounds_p (const value_range_base *vr)
+{
+ return (vr->min ()
+ && TREE_CODE (vr->min ()) == INTEGER_CST
+ && TREE_CODE (vr->max ()) == INTEGER_CST);
+}
+
+/* Return true if max and min of VR are INTEGER_CST. It's not necessary
+ a singleton. */
+
+bool
+range_int_cst_p (const value_range_base *vr)
+{
+ return (vr->kind () == VR_RANGE && range_has_numeric_bounds_p (vr));
+}
-/* Return true if value range VR involves at least one symbol. */
+/* Return true if VR is a INTEGER_CST singleton. */
bool
-symbolic_range_p (value_range *vr)
+range_int_cst_singleton_p (const value_range_base *vr)
{
- return (!is_gimple_min_invariant (vr->min)
- || !is_gimple_min_invariant (vr->max));
+ return (range_int_cst_p (vr)
+ && tree_int_cst_equal (vr->min (), vr->max ()));
}
/* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE
/* 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)
- return -2;
-
- if (!integer_zerop (tcmp))
+ int cmp = compare_values (val, val2);
+ if (cmp == -1)
return 1;
+ else if (cmp == 0 || cmp == 1)
+ return 0;
+ else
+ return -2;
}
return 0;
/* 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))
tree sym1 = get_single_symbol (val1, &neg1, &inv1);
tree sym2 = get_single_symbol (val2, &neg2, &inv2);
- /* If VAL1 and VAL2 are of the form '[-]NAME [+ CST]', return -1 or +1
- accordingly. If VAL1 and VAL2 don't use the same name, return -2. */
- if (sym1 && sym2)
- {
- /* Both values must use the same name with the same sign. */
- if (sym1 != sym2 || neg1 != neg2)
- return -2;
-
- /* [-]NAME + CST == [-]NAME + CST. */
- if (inv1 == inv2)
- return 0;
-
- /* If overflow is defined we cannot simplify more. */
- if (!overflow_undefined)
- return -2;
-
- if (strict_overflow_p != NULL
- /* Symbolic range building sets TREE_NO_WARNING to declare
- that overflow doesn't happen. */
- && (!inv1 || !TREE_NO_WARNING (val1))
- && (!inv2 || !TREE_NO_WARNING (val2)))
- *strict_overflow_p = true;
-
- if (!inv1)
- inv1 = build_int_cst (TREE_TYPE (val1), 0);
- if (!inv2)
- inv2 = build_int_cst (TREE_TYPE (val2), 0);
-
- return wi::cmp (wi::to_wide (inv1), wi::to_wide (inv2),
- TYPE_SIGN (TREE_TYPE (val1)));
- }
-
- const bool cst1 = is_gimple_min_invariant (val1);
- const bool cst2 = is_gimple_min_invariant (val2);
-
- /* If one is of the form '[-]NAME + CST' and the other is constant, then
- it might be possible to say something depending on the constants. */
- if ((sym1 && inv1 && cst2) || (sym2 && inv2 && cst1))
- {
- if (!overflow_undefined)
- return -2;
-
- if (strict_overflow_p != NULL
- /* Symbolic range building sets TREE_NO_WARNING to declare
- that overflow doesn't happen. */
- && (!sym1 || !TREE_NO_WARNING (val1))
- && (!sym2 || !TREE_NO_WARNING (val2)))
- *strict_overflow_p = true;
-
- const signop sgn = TYPE_SIGN (TREE_TYPE (val1));
- tree cst = cst1 ? val1 : val2;
- tree inv = cst1 ? inv2 : inv1;
-
- /* Compute the difference between the constants. If it overflows or
- underflows, this means that we can trivially compare the NAME with
- it and, consequently, the two values with each other. */
- wide_int diff = wi::to_wide (cst) - wi::to_wide (inv);
- if (wi::cmp (0, wi::to_wide (inv), sgn)
- != wi::cmp (diff, wi::to_wide (cst), sgn))
- {
- const int res = wi::cmp (wi::to_wide (cst), wi::to_wide (inv), sgn);
- return cst1 ? res : -res;
- }
-
- return -2;
- }
-
- /* We cannot say anything more for non-constants. */
- if (!cst1 || !cst2)
- return -2;
-
- if (!POINTER_TYPE_P (TREE_TYPE (val1)))
- {
- /* We cannot compare overflowed values. */
- if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
- return -2;
-
- return tree_int_cst_compare (val1, val2);
- }
- else
- {
- tree t;
-
- /* First see if VAL1 and VAL2 are not the same. */
- if (val1 == val2 || operand_equal_p (val1, val2, 0))
- return 0;
-
- /* If VAL1 is a lower address than VAL2, return -1. */
- if (operand_less_p (val1, val2) == 1)
- 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 (NE_EXPR, boolean_type_node, val1, val2);
- if (t && integer_onep (t))
- return 2;
- }
-
- return -2;
- }
-}
-
-/* Compare values like compare_values_warnv. */
-
-int
-compare_values (tree val1, tree val2)
-{
- bool sop;
- 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 value ranges VR0 and VR1 have a non-empty
- intersection.
-
- Benchmark compile/20001226-1.c compilation time after changing this
- function.
- */
-
-static inline bool
-value_ranges_intersect_p (value_range *vr0, value_range *vr1)
-{
- /* The value ranges do not intersect if the maximum of the first range is
- less than the minimum of the second range or vice versa.
- When those relations are unknown, we can't do any better. */
- if (operand_less_p (vr0->max, vr1->min) != 0)
- return false;
- if (operand_less_p (vr1->max, vr0->min) != 0)
- return false;
- return true;
-}
-
-
-/* Return 1 if [MIN, MAX] includes the value zero, 0 if it does not
- include the value zero, -2 if we cannot tell. */
-
-int
-range_includes_zero_p (tree min, tree max)
-{
- tree zero = build_int_cst (TREE_TYPE (min), 0);
- return value_inside_range (zero, min, max);
-}
-
-/* Return true if *VR is know to only contain nonnegative values. */
-
-static inline bool
-value_range_nonnegative_p (value_range *vr)
-{
- /* Testing for VR_ANTI_RANGE is not useful here as any anti-range
- which would return a useful value should be encoded as a
- VR_RANGE. */
- if (vr->type == VR_RANGE)
- {
- int result = compare_values (vr->min, integer_zero_node);
- return (result == 0 || result == 1);
- }
-
- return false;
-}
-
-/* If *VR has a value rante that is a single constant value return that,
- otherwise return NULL_TREE. */
-
-tree
-value_range_constant_singleton (value_range *vr)
-{
- if (vr->type == VR_RANGE
- && vrp_operand_equal_p (vr->min, vr->max)
- && is_gimple_min_invariant (vr->min))
- return vr->min;
-
- return NULL_TREE;
-}
-
-/* Wrapper around int_const_binop. Return true if we can compute the
- result; i.e. if the operation doesn't overflow or if the overflow is
- undefined. In the latter case (if the operation overflows and
- overflow is undefined), then adjust the result to be -INF or +INF
- depending on CODE, VAL1 and VAL2. Return the value in *RES.
-
- Return false for division by zero, for which the result is
- indeterminate. */
-
-static bool
-vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res)
-{
- bool overflow = false;
- signop sign = TYPE_SIGN (TREE_TYPE (val1));
-
- switch (code)
- {
- case RSHIFT_EXPR:
- case LSHIFT_EXPR:
- {
- wide_int wval2 = wi::to_wide (val2, TYPE_PRECISION (TREE_TYPE (val1)));
- if (wi::neg_p (wval2))
- {
- wval2 = -wval2;
- if (code == RSHIFT_EXPR)
- code = LSHIFT_EXPR;
- else
- code = RSHIFT_EXPR;
- }
-
- if (code == RSHIFT_EXPR)
- /* It's unclear from the C standard whether shifts can overflow.
- The following code ignores overflow; perhaps a C standard
- interpretation ruling is needed. */
- *res = wi::rshift (wi::to_wide (val1), wval2, sign);
- else
- *res = wi::lshift (wi::to_wide (val1), wval2);
- break;
- }
-
- case MULT_EXPR:
- *res = wi::mul (wi::to_wide (val1),
- wi::to_wide (val2), sign, &overflow);
- break;
-
- case TRUNC_DIV_EXPR:
- case EXACT_DIV_EXPR:
- if (val2 == 0)
- return false;
- else
- *res = wi::div_trunc (wi::to_wide (val1),
- wi::to_wide (val2), sign, &overflow);
- break;
-
- case FLOOR_DIV_EXPR:
- if (val2 == 0)
- return false;
- *res = wi::div_floor (wi::to_wide (val1),
- wi::to_wide (val2), sign, &overflow);
- break;
-
- case CEIL_DIV_EXPR:
- if (val2 == 0)
- return false;
- *res = wi::div_ceil (wi::to_wide (val1),
- wi::to_wide (val2), sign, &overflow);
- break;
-
- case ROUND_DIV_EXPR:
- if (val2 == 0)
- return false;
- *res = wi::div_round (wi::to_wide (val1),
- wi::to_wide (val2), sign, &overflow);
- break;
-
- default:
- gcc_unreachable ();
- }
-
- if (overflow
- && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
- {
- /* If the operation overflowed return -INF or +INF depending
- on the operation and the combination of signs of the operands. */
- int sgn1 = tree_int_cst_sgn (val1);
- int sgn2 = tree_int_cst_sgn (val2);
-
- /* Notice that we only need to handle the restricted set of
- operations handled by extract_range_from_binary_expr.
- Among them, only multiplication, addition and subtraction
- can yield overflow without overflown operands because we
- are working with integral types only... except in the
- case VAL1 = -INF and VAL2 = -1 which overflows to +INF
- for division too. */
-
- /* For multiplication, the sign of the overflow is given
- by the comparison of the signs of the operands. */
- if ((code == MULT_EXPR && sgn1 == sgn2)
- /* For addition, the operands must be of the same sign
- to yield an overflow. Its sign is therefore that
- of one of the operands, for example the first. */
- || (code == PLUS_EXPR && sgn1 >= 0)
- /* For subtraction, operands must be of
- different signs to yield an overflow. Its sign is
- therefore that of the first operand or the opposite of
- that of the second operand. A first operand of 0 counts
- as positive here, for the corner case 0 - (-INF), which
- overflows, but must yield +INF. */
- || (code == MINUS_EXPR && sgn1 >= 0)
- /* For division, the only case is -INF / -1 = +INF. */
- || code == TRUNC_DIV_EXPR
- || code == FLOOR_DIV_EXPR
- || code == CEIL_DIV_EXPR
- || code == EXACT_DIV_EXPR
- || code == ROUND_DIV_EXPR)
- *res = wi::max_value (TYPE_PRECISION (TREE_TYPE (val1)),
- TYPE_SIGN (TREE_TYPE (val1)));
- else
- *res = wi::min_value (TYPE_PRECISION (TREE_TYPE (val1)),
- TYPE_SIGN (TREE_TYPE (val1)));
- return true;
- }
-
- return !overflow;
-}
-
-
-/* For range VR compute two wide_int bitmasks. In *MAY_BE_NONZERO
- bitmask if some bit is unset, it means for all numbers in the range
- the bit is 0, otherwise it might be 0 or 1. In *MUST_BE_NONZERO
- bitmask if some bit is set, it means for all numbers in the range
- the bit is 1, otherwise it might be 0 or 1. */
-
-bool
-zero_nonzero_bits_from_vr (const tree expr_type,
- value_range *vr,
- wide_int *may_be_nonzero,
- wide_int *must_be_nonzero)
-{
- *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type));
- *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type));
- if (!range_int_cst_p (vr))
- return false;
-
- if (range_int_cst_singleton_p (vr))
- {
- *may_be_nonzero = wi::to_wide (vr->min);
- *must_be_nonzero = *may_be_nonzero;
- }
- else if (tree_int_cst_sgn (vr->min) >= 0
- || tree_int_cst_sgn (vr->max) < 0)
- {
- wide_int xor_mask = wi::to_wide (vr->min) ^ wi::to_wide (vr->max);
- *may_be_nonzero = wi::to_wide (vr->min) | wi::to_wide (vr->max);
- *must_be_nonzero = wi::to_wide (vr->min) & wi::to_wide (vr->max);
- if (xor_mask != 0)
- {
- wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
- may_be_nonzero->get_precision ());
- *may_be_nonzero = *may_be_nonzero | mask;
- *must_be_nonzero = wi::bit_and_not (*must_be_nonzero, mask);
- }
- }
-
- 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 (value_range *ar,
- value_range *vr0, value_range *vr1)
-{
- tree type = TREE_TYPE (ar->min);
-
- vr0->type = VR_UNDEFINED;
- vr1->type = VR_UNDEFINED;
-
- if (ar->type != 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->type = VR_RANGE;
- vr0->min = vrp_val_min (type);
- vr0->max = wide_int_to_tree (type, wi::to_wide (ar->min) - 1);
- }
- if (!vrp_val_is_max (ar->max))
- {
- vr1->type = VR_RANGE;
- vr1->min = wide_int_to_tree (type, wi::to_wide (ar->max) + 1);
- vr1->max = vrp_val_max (type);
- }
- if (vr0->type == VR_UNDEFINED)
- {
- *vr0 = *vr1;
- vr1->type = VR_UNDEFINED;
- }
-
- return vr0->type != VR_UNDEFINED;
-}
+ /* If VAL1 and VAL2 are of the form '[-]NAME [+ CST]', return -1 or +1
+ accordingly. If VAL1 and VAL2 don't use the same name, return -2. */
+ if (sym1 && sym2)
+ {
+ /* Both values must use the same name with the same sign. */
+ if (sym1 != sym2 || neg1 != neg2)
+ return -2;
-/* Helper to extract a value-range *VR for a multiplicative operation
- *VR0 CODE *VR1. */
+ /* [-]NAME + CST == [-]NAME + CST. */
+ if (inv1 == inv2)
+ return 0;
-static void
-extract_range_from_multiplicative_op_1 (value_range *vr,
- enum tree_code code,
- value_range *vr0, value_range *vr1)
-{
- enum value_range_type rtype;
- wide_int val, min, max;
- tree type;
-
- /* Multiplications, divisions and shifts are a bit tricky to handle,
- depending on the mix of signs we have in the two ranges, we
- need to operate on different values to get the minimum and
- maximum values for the new range. One approach is to figure
- out all the variations of range combinations and do the
- operations.
-
- However, this involves several calls to compare_values and it
- is pretty convoluted. It's simpler to do the 4 operations
- (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
- MAX1) and then figure the smallest and largest values to form
- the new range. */
- gcc_assert (code == MULT_EXPR
- || code == TRUNC_DIV_EXPR
- || code == FLOOR_DIV_EXPR
- || code == CEIL_DIV_EXPR
- || code == EXACT_DIV_EXPR
- || code == ROUND_DIV_EXPR
- || code == RSHIFT_EXPR
- || code == LSHIFT_EXPR);
- gcc_assert (vr0->type == VR_RANGE
- && vr0->type == vr1->type);
-
- rtype = vr0->type;
- type = TREE_TYPE (vr0->min);
- signop sgn = TYPE_SIGN (type);
-
- /* Compute the 4 cross operations and their minimum and maximum value. */
- if (!vrp_int_const_binop (code, vr0->min, vr1->min, &val))
- {
- set_value_range_to_varying (vr);
- return;
- }
- min = max = val;
+ /* If overflow is defined we cannot simplify more. */
+ if (!overflow_undefined)
+ return -2;
- if (vr1->max != vr1->min)
- {
- if (!vrp_int_const_binop (code, vr0->min, vr1->max, &val))
- {
- set_value_range_to_varying (vr);
- return;
- }
- if (wi::lt_p (val, min, sgn))
- min = val;
- else if (wi::gt_p (val, max, sgn))
- max = val;
- }
+ if (strict_overflow_p != NULL
+ /* Symbolic range building sets TREE_NO_WARNING to declare
+ that overflow doesn't happen. */
+ && (!inv1 || !TREE_NO_WARNING (val1))
+ && (!inv2 || !TREE_NO_WARNING (val2)))
+ *strict_overflow_p = true;
- if (vr0->max != vr0->min)
- {
- if (!vrp_int_const_binop (code, vr0->max, vr1->min, &val))
- {
- set_value_range_to_varying (vr);
- return;
- }
- if (wi::lt_p (val, min, sgn))
- min = val;
- else if (wi::gt_p (val, max, sgn))
- max = val;
- }
+ if (!inv1)
+ inv1 = build_int_cst (TREE_TYPE (val1), 0);
+ if (!inv2)
+ inv2 = build_int_cst (TREE_TYPE (val2), 0);
- if (vr0->min != vr0->max && vr1->min != vr1->max)
- {
- if (!vrp_int_const_binop (code, vr0->max, vr1->max, &val))
- {
- set_value_range_to_varying (vr);
- return;
- }
- if (wi::lt_p (val, min, sgn))
- min = val;
- else if (wi::gt_p (val, max, sgn))
- max = val;
+ return wi::cmp (wi::to_wide (inv1), wi::to_wide (inv2),
+ TYPE_SIGN (TREE_TYPE (val1)));
}
- /* 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. */
- if (wi::gt_p (min, max, sgn))
- {
- set_value_range_to_varying (vr);
- return;
- }
+ const bool cst1 = is_gimple_min_invariant (val1);
+ const bool cst2 = is_gimple_min_invariant (val2);
- /* 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 (wi::eq_p (min, wi::min_value (TYPE_PRECISION (type), sgn))
- && wi::eq_p (max, wi::max_value (TYPE_PRECISION (type), sgn)))
+ /* If one is of the form '[-]NAME + CST' and the other is constant, then
+ it might be possible to say something depending on the constants. */
+ if ((sym1 && inv1 && cst2) || (sym2 && inv2 && cst1))
{
- set_value_range_to_varying (vr);
- return;
- }
+ if (!overflow_undefined)
+ return -2;
- set_value_range (vr, rtype,
- wide_int_to_tree (type, min),
- wide_int_to_tree (type, max), NULL);
-}
+ if (strict_overflow_p != NULL
+ /* Symbolic range building sets TREE_NO_WARNING to declare
+ that overflow doesn't happen. */
+ && (!sym1 || !TREE_NO_WARNING (val1))
+ && (!sym2 || !TREE_NO_WARNING (val2)))
+ *strict_overflow_p = true;
-/* 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. */
+ const signop sgn = TYPE_SIGN (TREE_TYPE (val1));
+ tree cst = cst1 ? val1 : val2;
+ tree inv = cst1 ? inv2 : inv1;
-void
-extract_range_from_binary_expr_1 (value_range *vr,
- enum tree_code code, tree expr_type,
- value_range *vr0_, value_range *vr1_)
-{
- value_range vr0 = *vr0_, vr1 = *vr1_;
- value_range vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER;
- enum value_range_type type;
- tree min = NULL_TREE, max = NULL_TREE;
- int cmp;
+ /* Compute the difference between the constants. If it overflows or
+ underflows, this means that we can trivially compare the NAME with
+ it and, consequently, the two values with each other. */
+ wide_int diff = wi::to_wide (cst) - wi::to_wide (inv);
+ if (wi::cmp (0, wi::to_wide (inv), sgn)
+ != wi::cmp (diff, wi::to_wide (cst), sgn))
+ {
+ const int res = wi::cmp (wi::to_wide (cst), wi::to_wide (inv), sgn);
+ return cst1 ? res : -res;
+ }
- if (!INTEGRAL_TYPE_P (expr_type)
- && !POINTER_TYPE_P (expr_type))
- {
- set_value_range_to_varying (vr);
- return;
+ return -2;
}
- /* 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;
- }
+ /* We cannot say anything more for non-constants. */
+ if (!cst1 || !cst2)
+ return -2;
- /* If both ranges are UNDEFINED, so is the result. */
- if (vr0.type == VR_UNDEFINED && vr1.type == VR_UNDEFINED)
+ if (!POINTER_TYPE_P (TREE_TYPE (val1)))
{
- 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.type == VR_UNDEFINED)
- set_value_range_to_varying (&vr0);
- else if (vr1.type == VR_UNDEFINED)
- 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_meet. It's just
- easier to special case when vr0 is ~[0,0] for EXACT_DIV_EXPR. */
- if (code == EXACT_DIV_EXPR
- && vr0.type == VR_ANTI_RANGE
- && vr0.min == vr0.max
- && integer_zerop (vr0.min))
- {
- set_value_range_to_nonnull (vr, expr_type);
- return;
- }
+ /* We cannot compare overflowed values. */
+ if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
+ return -2;
- /* Now canonicalize anti-ranges to ranges when they are not symbolic
- and express ~[] op X as ([]' op X) U ([]'' op X). */
- if (vr0.type == VR_ANTI_RANGE
- && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
- {
- extract_range_from_binary_expr_1 (vr, code, expr_type, &vrtem0, vr1_);
- if (vrtem1.type != VR_UNDEFINED)
+ if (TREE_CODE (val1) == INTEGER_CST
+ && TREE_CODE (val2) == INTEGER_CST)
+ return tree_int_cst_compare (val1, val2);
+
+ if (poly_int_tree_p (val1) && poly_int_tree_p (val2))
{
- value_range vrres = VR_INITIALIZER;
- extract_range_from_binary_expr_1 (&vrres, code, expr_type,
- &vrtem1, vr1_);
- vrp_meet (vr, &vrres);
+ if (known_eq (wi::to_poly_widest (val1),
+ wi::to_poly_widest (val2)))
+ return 0;
+ if (known_lt (wi::to_poly_widest (val1),
+ wi::to_poly_widest (val2)))
+ return -1;
+ if (known_gt (wi::to_poly_widest (val1),
+ wi::to_poly_widest (val2)))
+ return 1;
}
- return;
+
+ return -2;
}
- /* Likewise for X op ~[]. */
- if (vr1.type == VR_ANTI_RANGE
- && ranges_from_anti_range (&vr1, &vrtem0, &vrtem1))
+ else
{
- extract_range_from_binary_expr_1 (vr, code, expr_type, vr0_, &vrtem0);
- if (vrtem1.type != VR_UNDEFINED)
+ if (TREE_CODE (val1) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST)
{
- value_range vrres = VR_INITIALIZER;
- extract_range_from_binary_expr_1 (&vrres, code, expr_type,
- vr0_, &vrtem1);
- vrp_meet (vr, &vrres);
+ /* We cannot compare overflowed values. */
+ if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
+ return -2;
+
+ return tree_int_cst_compare (val1, val2);
}
- return;
- }
- /* The type of the resulting value range defaults to VR0.TYPE. */
- type = vr0.type;
-
- /* 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
- && (vr0.type == VR_VARYING
- || vr1.type == VR_VARYING
- || vr0.type != vr1.type
- || symbolic_range_p (&vr0)
- || symbolic_range_p (&vr1)))
- {
- set_value_range_to_varying (vr);
- return;
- }
+ /* First see if VAL1 and VAL2 are not the same. */
+ if (operand_equal_p (val1, val2, 0))
+ return 0;
- /* Now evaluate the expression to determine the new range. */
- if (POINTER_TYPE_P (expr_type))
- {
- 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_is_nonnull (&vr0) && range_is_nonnull (&vr1))
- set_value_range_to_nonnull (vr, expr_type);
- else if (range_is_null (&vr0) && range_is_null (&vr1))
- set_value_range_to_null (vr, expr_type);
- else
- set_value_range_to_varying (vr);
- }
- else if (code == POINTER_PLUS_EXPR)
+ fold_defer_overflow_warnings ();
+
+ /* If VAL1 is a lower address than VAL2, return -1. */
+ tree t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val1, val2);
+ if (t && integer_onep (t))
{
- /* For pointer types, we are really only interested in asserting
- whether the expression evaluates to non-NULL. */
- if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
- set_value_range_to_nonnull (vr, expr_type);
- else if (range_is_null (&vr0) && range_is_null (&vr1))
- set_value_range_to_null (vr, expr_type);
- else
- set_value_range_to_varying (vr);
+ fold_undefer_and_ignore_overflow_warnings ();
+ return -1;
}
- else if (code == BIT_AND_EXPR)
+
+ /* If VAL1 is a higher address than VAL2, return +1. */
+ t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val2, val1);
+ if (t && integer_onep (t))
{
- /* For pointer types, we are really only interested in asserting
- whether the expression evaluates to non-NULL. */
- if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1))
- set_value_range_to_nonnull (vr, expr_type);
- else if (range_is_null (&vr0) || range_is_null (&vr1))
- set_value_range_to_null (vr, expr_type);
- else
- set_value_range_to_varying (vr);
+ fold_undefer_and_ignore_overflow_warnings ();
+ return 1;
}
- else
- set_value_range_to_varying (vr);
- return;
+ /* 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;
}
+}
- /* 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)
- {
- 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;
-
- /* 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.type == VR_RANGE && vr1.type == 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))))
- {
- const signop sgn = TYPE_SIGN (expr_type);
- const unsigned int prec = TYPE_PRECISION (expr_type);
- wide_int type_min, type_max, wmin, wmax;
- int min_ovf = 0;
- int max_ovf = 0;
-
- /* Get the lower and upper bounds of the type. */
- if (TYPE_OVERFLOW_WRAPS (expr_type))
- {
- type_min = wi::min_value (prec, sgn);
- type_max = wi::max_value (prec, sgn);
- }
- else
- {
- type_min = wi::to_wide (vrp_val_min (expr_type));
- type_max = wi::to_wide (vrp_val_max (expr_type));
- }
+/* Compare values like compare_values_warnv. */
- /* Combine the lower bounds, if any. */
- if (min_op0 && min_op1)
- {
- if (minus_p)
- {
- wmin = wi::to_wide (min_op0) - wi::to_wide (min_op1);
+int
+compare_values (tree val1, tree val2)
+{
+ bool sop;
+ return compare_values_warnv (val1, val2, &sop);
+}
- /* Check for overflow. */
- if (wi::cmp (0, wi::to_wide (min_op1), sgn)
- != wi::cmp (wmin, wi::to_wide (min_op0), sgn))
- min_ovf = wi::cmp (wi::to_wide (min_op0),
- wi::to_wide (min_op1), sgn);
- }
- else
- {
- wmin = wi::to_wide (min_op0) + wi::to_wide (min_op1);
- /* Check for overflow. */
- if (wi::cmp (wi::to_wide (min_op1), 0, sgn)
- != wi::cmp (wmin, wi::to_wide (min_op0), sgn))
- min_ovf = wi::cmp (wi::to_wide (min_op0), wmin, sgn);
- }
- }
- else if (min_op0)
- wmin = wi::to_wide (min_op0);
- else if (min_op1)
- {
- if (minus_p)
- {
- wmin = -wi::to_wide (min_op1);
-
- /* Check for overflow. */
- if (sgn == SIGNED
- && wi::neg_p (wi::to_wide (min_op1))
- && wi::neg_p (wmin))
- min_ovf = 1;
- else if (sgn == UNSIGNED && wi::to_wide (min_op1) != 0)
- min_ovf = -1;
- }
- else
- wmin = wi::to_wide (min_op1);
- }
- else
- wmin = wi::shwi (0, prec);
+/* Return 1 if VAL is inside value range.
+ 0 if VAL is not inside value range.
+ -2 if we cannot tell either way.
- /* Combine the upper bounds, if any. */
- if (max_op0 && max_op1)
- {
- if (minus_p)
- {
- wmax = wi::to_wide (max_op0) - wi::to_wide (max_op1);
+ Benchmark compile/20001226-1.c compilation time after changing this
+ function. */
- /* Check for overflow. */
- if (wi::cmp (0, wi::to_wide (max_op1), sgn)
- != wi::cmp (wmax, wi::to_wide (max_op0), sgn))
- max_ovf = wi::cmp (wi::to_wide (max_op0),
- wi::to_wide (max_op1), sgn);
- }
- else
- {
- wmax = wi::to_wide (max_op0) + wi::to_wide (max_op1);
+int
+value_range_base::value_inside_range (tree val) const
+{
+ int cmp1, cmp2;
- if (wi::cmp (wi::to_wide (max_op1), 0, sgn)
- != wi::cmp (wmax, wi::to_wide (max_op0), sgn))
- max_ovf = wi::cmp (wi::to_wide (max_op0), wmax, sgn);
- }
- }
- else if (max_op0)
- wmax = wi::to_wide (max_op0);
- else if (max_op1)
- {
- if (minus_p)
- {
- wmax = -wi::to_wide (max_op1);
-
- /* Check for overflow. */
- if (sgn == SIGNED
- && wi::neg_p (wi::to_wide (max_op1))
- && wi::neg_p (wmax))
- max_ovf = 1;
- else if (sgn == UNSIGNED && wi::to_wide (max_op1) != 0)
- max_ovf = -1;
- }
- else
- wmax = wi::to_wide (max_op1);
- }
- else
- wmax = wi::shwi (0, prec);
+ if (varying_p ())
+ return 1;
- /* Check for type overflow. */
- if (min_ovf == 0)
- {
- if (wi::cmp (wmin, type_min, sgn) == -1)
- min_ovf = -1;
- else if (wi::cmp (wmin, type_max, sgn) == 1)
- min_ovf = 1;
- }
- if (max_ovf == 0)
- {
- if (wi::cmp (wmax, type_min, sgn) == -1)
- max_ovf = -1;
- else if (wi::cmp (wmax, type_max, sgn) == 1)
- max_ovf = 1;
- }
+ if (undefined_p ())
+ return 0;
- /* If we have overflow for the constant part and the resulting
- range will be symbolic, drop to VR_VARYING. */
- if ((min_ovf && sym_min_op0 != sym_min_op1)
- || (max_ovf && sym_max_op0 != sym_max_op1))
- {
- set_value_range_to_varying (vr);
- return;
- }
+ cmp1 = operand_less_p (val, m_min);
+ if (cmp1 == -2)
+ return -2;
+ if (cmp1 == 1)
+ return m_kind != VR_RANGE;
- if (TYPE_OVERFLOW_WRAPS (expr_type))
- {
- /* If overflow wraps, truncate the values and adjust the
- range kind and bounds appropriately. */
- wide_int tmin = wide_int::from (wmin, prec, sgn);
- wide_int tmax = wide_int::from (wmax, prec, sgn);
- if (min_ovf == max_ovf)
- {
- /* No overflow or both overflow or underflow. The
- range kind stays VR_RANGE. */
- min = wide_int_to_tree (expr_type, tmin);
- max = wide_int_to_tree (expr_type, tmax);
- }
- else if ((min_ovf == -1 && max_ovf == 0)
- || (max_ovf == 1 && min_ovf == 0))
- {
- /* Min underflow or max overflow. The range kind
- changes to VR_ANTI_RANGE. */
- bool covers = false;
- wide_int tem = tmin;
- type = VR_ANTI_RANGE;
- tmin = tmax + 1;
- if (wi::cmp (tmin, tmax, sgn) < 0)
- covers = true;
- tmax = tem - 1;
- if (wi::cmp (tmax, tem, sgn) > 0)
- covers = true;
- /* If the anti-range would cover nothing, drop to varying.
- Likewise if the anti-range bounds are outside of the
- types values. */
- if (covers || wi::cmp (tmin, tmax, sgn) > 0)
- {
- set_value_range_to_varying (vr);
- return;
- }
- min = wide_int_to_tree (expr_type, tmin);
- max = wide_int_to_tree (expr_type, tmax);
- }
- else
- {
- /* Other underflow and/or overflow, drop to VR_VARYING. */
- set_value_range_to_varying (vr);
- return;
- }
- }
- else
- {
- /* If overflow does not wrap, saturate to the types min/max
- value. */
- if (min_ovf == -1)
- min = wide_int_to_tree (expr_type, type_min);
- else if (min_ovf == 1)
- min = wide_int_to_tree (expr_type, type_max);
- else
- min = wide_int_to_tree (expr_type, wmin);
+ cmp2 = operand_less_p (m_max, val);
+ if (cmp2 == -2)
+ return -2;
- if (max_ovf == -1)
- max = wide_int_to_tree (expr_type, type_min);
- else if (max_ovf == 1)
- max = wide_int_to_tree (expr_type, type_max);
- else
- max = wide_int_to_tree (expr_type, wmax);
- }
+ if (m_kind == VR_RANGE)
+ return !cmp2;
+ else
+ return !!cmp2;
+}
- /* If the result lower bound is constant, we're done;
- otherwise, build the symbolic lower bound. */
- if (sym_min_op0 == sym_min_op1)
- ;
- else if (sym_min_op0)
- min = build_symbolic_expr (expr_type, sym_min_op0,
- neg_min_op0, min);
- else if (sym_min_op1)
- {
- /* We may not negate if that might introduce
- undefined overflow. */
- if (! minus_p
- || neg_min_op1
- || TYPE_OVERFLOW_WRAPS (expr_type))
- min = build_symbolic_expr (expr_type, sym_min_op1,
- neg_min_op1 ^ minus_p, min);
- else
- min = NULL_TREE;
- }
+/* For range [LB, UB] compute two wide_int bit masks.
- /* Likewise for the upper bound. */
- if (sym_max_op0 == sym_max_op1)
- ;
- else if (sym_max_op0)
- max = build_symbolic_expr (expr_type, sym_max_op0,
- neg_max_op0, max);
- else if (sym_max_op1)
- {
- /* We may not negate if that might introduce
- undefined overflow. */
- if (! minus_p
- || neg_max_op1
- || TYPE_OVERFLOW_WRAPS (expr_type))
- max = build_symbolic_expr (expr_type, sym_max_op1,
- neg_max_op1 ^ minus_p, max);
- else
- max = NULL_TREE;
- }
- }
- 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;
- }
+ In the MAY_BE_NONZERO bit mask, if some bit is unset, it means that
+ for all numbers in the range the bit is 0, otherwise it might be 0
+ or 1.
+
+ In the MUST_BE_NONZERO bit mask, if some bit is set, it means that
+ for all numbers in the range the bit is 1, otherwise it might be 0
+ or 1. */
+
+static inline void
+wide_int_range_set_zero_nonzero_bits (signop sign,
+ const wide_int &lb, const wide_int &ub,
+ wide_int &may_be_nonzero,
+ wide_int &must_be_nonzero)
+{
+ may_be_nonzero = wi::minus_one (lb.get_precision ());
+ must_be_nonzero = wi::zero (lb.get_precision ());
+
+ if (wi::eq_p (lb, ub))
+ {
+ may_be_nonzero = lb;
+ must_be_nonzero = may_be_nonzero;
}
- else if (code == MIN_EXPR
- || code == MAX_EXPR)
+ else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
{
- if (vr0.type == VR_RANGE
- && !symbolic_range_p (&vr0))
- {
- type = VR_RANGE;
- if (vr1.type == VR_RANGE
- && !symbolic_range_p (&vr1))
- {
- /* For operations that make the resulting range directly
- proportional to the original ranges, apply the operation to
- the same end of each range. */
- min = int_const_binop (code, vr0.min, vr1.min);
- max = int_const_binop (code, vr0.max, vr1.max);
- }
- else if (code == MIN_EXPR)
- {
- min = vrp_val_min (expr_type);
- max = vr0.max;
- }
- else if (code == MAX_EXPR)
- {
- min = vr0.min;
- max = vrp_val_max (expr_type);
- }
- }
- else if (vr1.type == VR_RANGE
- && !symbolic_range_p (&vr1))
- {
- type = VR_RANGE;
- if (code == MIN_EXPR)
- {
- min = vrp_val_min (expr_type);
- max = vr1.max;
- }
- else if (code == MAX_EXPR)
- {
- min = vr1.min;
- max = vrp_val_max (expr_type);
- }
- }
- else
+ wide_int xor_mask = lb ^ ub;
+ may_be_nonzero = lb | ub;
+ must_be_nonzero = lb & ub;
+ if (xor_mask != 0)
{
- set_value_range_to_varying (vr);
- return;
+ wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
+ may_be_nonzero.get_precision ());
+ may_be_nonzero = may_be_nonzero | mask;
+ must_be_nonzero = wi::bit_and_not (must_be_nonzero, mask);
}
}
- else if (code == MULT_EXPR)
+}
+
+/* value_range wrapper for wide_int_range_set_zero_nonzero_bits above.
+
+ 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_base *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_base *ar,
+ value_range_base *vr0, value_range_base *vr1,
+ bool handle_pointers)
+{
+ 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, handle_pointers)
+ || !vrp_val_max (type, handle_pointers))
+ return false;
+
+ if (tree_int_cst_lt (vrp_val_min (type, handle_pointers), ar->min ()))
+ vr0->set (VR_RANGE,
+ vrp_val_min (type, handle_pointers),
+ wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1));
+ if (tree_int_cst_lt (ar->max (), vrp_val_max (type, handle_pointers)))
+ vr1->set (VR_RANGE,
+ wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1),
+ vrp_val_max (type, handle_pointers));
+ if (vr0->undefined_p ())
{
- /* Fancy code so that with unsigned, [-3,-1]*[-3,-1] does not
- drop to varying. This test requires 2*prec bits if both
- operands are signed and 2*prec + 2 bits if either is not. */
+ *vr0 = *vr1;
+ vr1->set_undefined ();
+ }
- signop sign = TYPE_SIGN (expr_type);
- unsigned int prec = TYPE_PRECISION (expr_type);
+ return !vr0->undefined_p ();
+}
- if (!range_int_cst_p (&vr0)
- || !range_int_cst_p (&vr1))
- {
- set_value_range_to_varying (vr);
- return;
- }
+/* If BOUND will include a symbolic bound, adjust it accordingly,
+ otherwise leave it as is.
- if (TYPE_OVERFLOW_WRAPS (expr_type))
- {
- typedef FIXED_WIDE_INT (WIDE_INT_MAX_PRECISION * 2) vrp_int;
- typedef generic_wide_int
- <wi::extended_tree <WIDE_INT_MAX_PRECISION * 2> > vrp_int_cst;
- vrp_int sizem1 = wi::mask <vrp_int> (prec, false);
- vrp_int size = sizem1 + 1;
-
- /* Extend the values using the sign of the result to PREC2.
- From here on out, everthing is just signed math no matter
- what the input types were. */
- vrp_int min0 = vrp_int_cst (vr0.min);
- vrp_int max0 = vrp_int_cst (vr0.max);
- vrp_int min1 = vrp_int_cst (vr1.min);
- vrp_int max1 = vrp_int_cst (vr1.max);
- /* Canonicalize the intervals. */
- if (sign == UNSIGNED)
- {
- if (wi::ltu_p (size, min0 + max0))
- {
- min0 -= size;
- max0 -= size;
- }
+ CODE is the original operation that combined the bounds (PLUS_EXPR
+ or MINUS_EXPR).
- if (wi::ltu_p (size, min1 + max1))
- {
- min1 -= size;
- max1 -= size;
- }
- }
+ TYPE is the type of the original operation.
- vrp_int prod0 = min0 * min1;
- vrp_int prod1 = min0 * max1;
- vrp_int prod2 = max0 * min1;
- vrp_int prod3 = max0 * max1;
+ SYM_OPn is the symbolic for OPn if it has a symbolic.
- /* Sort the 4 products so that min is in prod0 and max is in
- prod3. */
- /* min0min1 > max0max1 */
- if (prod0 > prod3)
- std::swap (prod0, prod3);
+ NEG_OPn is TRUE if the OPn was negated. */
- /* min0max1 > max0min1 */
- if (prod1 > prod2)
- std::swap (prod1, prod2);
+static void
+adjust_symbolic_bound (tree &bound, enum tree_code code, tree type,
+ tree sym_op0, tree sym_op1,
+ bool neg_op0, bool neg_op1)
+{
+ bool minus_p = (code == MINUS_EXPR);
+ /* If the result bound is constant, we're done; otherwise, build the
+ symbolic lower bound. */
+ if (sym_op0 == sym_op1)
+ ;
+ else if (sym_op0)
+ bound = build_symbolic_expr (type, sym_op0,
+ neg_op0, bound);
+ else if (sym_op1)
+ {
+ /* We may not negate if that might introduce
+ undefined overflow. */
+ if (!minus_p
+ || neg_op1
+ || TYPE_OVERFLOW_WRAPS (type))
+ bound = build_symbolic_expr (type, sym_op1,
+ neg_op1 ^ minus_p, bound);
+ else
+ bound = NULL_TREE;
+ }
+}
- if (prod0 > prod1)
- std::swap (prod0, prod1);
+/* Combine OP1 and OP1, which are two parts of a bound, into one wide
+ int bound according to CODE. CODE is the operation combining the
+ bound (either a PLUS_EXPR or a MINUS_EXPR).
- if (prod2 > prod3)
- std::swap (prod2, prod3);
+ TYPE is the type of the combine operation.
- /* diff = max - min. */
- prod2 = prod3 - prod0;
- if (wi::geu_p (prod2, sizem1))
- {
- /* the range covers all values. */
- set_value_range_to_varying (vr);
- return;
- }
+ WI is the wide int to store the result.
- /* The following should handle the wrapping and selecting
- VR_ANTI_RANGE for us. */
- min = wide_int_to_tree (expr_type, prod0);
- max = wide_int_to_tree (expr_type, prod3);
- set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL);
- return;
- }
+ OVF is -1 if an underflow occurred, +1 if an overflow occurred or 0
+ if over/underflow occurred. */
- /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
- drop to VR_VARYING. It would take more effort to compute a
- precise range for such a case. For example, if we have
- op0 == 65536 and op1 == 65536 with their ranges both being
- ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
- we cannot claim that the product is in ~[0,0]. Note that we
- are guaranteed to have vr0.type == vr1.type at this
- point. */
- if (vr0.type == VR_ANTI_RANGE
- && !TYPE_OVERFLOW_UNDEFINED (expr_type))
- {
- set_value_range_to_varying (vr);
- return;
- }
+static void
+combine_bound (enum tree_code code, wide_int &wi, wi::overflow_type &ovf,
+ tree type, tree op0, tree op1)
+{
+ bool minus_p = (code == MINUS_EXPR);
+ const signop sgn = TYPE_SIGN (type);
+ const unsigned int prec = TYPE_PRECISION (type);
- extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
- return;
+ /* Combine the bounds, if any. */
+ if (op0 && op1)
+ {
+ if (minus_p)
+ wi = wi::sub (wi::to_wide (op0), wi::to_wide (op1), sgn, &ovf);
+ else
+ wi = wi::add (wi::to_wide (op0), wi::to_wide (op1), sgn, &ovf);
}
- else if (code == RSHIFT_EXPR
- || code == LSHIFT_EXPR)
- {
- /* If we have a RSHIFT_EXPR with any shift values outside [0..prec-1],
- then drop to VR_VARYING. Outside of this range we get undefined
- behavior from the shift operation. We cannot even trust
- SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
- shifts, and the operation at the tree level may be widened. */
- if (range_int_cst_p (&vr1)
- && compare_tree_int (vr1.min, 0) >= 0
- && compare_tree_int (vr1.max, TYPE_PRECISION (expr_type)) == -1)
- {
- 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.type != VR_RANGE || symbolic_range_p (&vr0))
- {
- vr0.type = type = VR_RANGE;
- vr0.min = vrp_val_min (expr_type);
- vr0.max = vrp_val_max (expr_type);
- }
- extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
- return;
- }
- /* We can map lshifts by constants to MULT_EXPR handling. */
- else if (code == LSHIFT_EXPR
- && range_int_cst_singleton_p (&vr1))
- {
- bool saved_flag_wrapv;
- value_range vr1p = VR_INITIALIZER;
- vr1p.type = VR_RANGE;
- vr1p.min = (wide_int_to_tree
- (expr_type,
- wi::set_bit_in_zero (tree_to_shwi (vr1.min),
- TYPE_PRECISION (expr_type))));
- vr1p.max = vr1p.min;
- /* We have to use a wrapping multiply though as signed overflow
- on lshifts is implementation defined in C89. */
- saved_flag_wrapv = flag_wrapv;
- flag_wrapv = 1;
- extract_range_from_binary_expr_1 (vr, MULT_EXPR, expr_type,
- &vr0, &vr1p);
- flag_wrapv = saved_flag_wrapv;
- return;
- }
- else if (code == LSHIFT_EXPR
- && range_int_cst_p (&vr0))
- {
- int prec = TYPE_PRECISION (expr_type);
- int overflow_pos = prec;
- int bound_shift;
- wide_int low_bound, high_bound;
- bool uns = TYPE_UNSIGNED (expr_type);
- bool in_bounds = false;
-
- if (!uns)
- overflow_pos -= 1;
-
- bound_shift = overflow_pos - tree_to_shwi (vr1.max);
- /* If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
- overflow. However, for that to happen, vr1.max needs to be
- zero, which means vr1 is a singleton range of zero, which
- means it should be handled by the previous LSHIFT_EXPR
- if-clause. */
- wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
- wide_int complement = ~(bound - 1);
-
- if (uns)
- {
- low_bound = bound;
- high_bound = complement;
- if (wi::ltu_p (wi::to_wide (vr0.max), low_bound))
- {
- /* [5, 6] << [1, 2] == [10, 24]. */
- /* We're shifting out only zeroes, the value increases
- monotonically. */
- in_bounds = true;
- }
- else if (wi::ltu_p (high_bound, wi::to_wide (vr0.min)))
- {
- /* [0xffffff00, 0xffffffff] << [1, 2]
- == [0xfffffc00, 0xfffffffe]. */
- /* We're shifting out only ones, the value decreases
- monotonically. */
- in_bounds = true;
- }
- }
- else
- {
- /* [-1, 1] << [1, 2] == [-4, 4]. */
- low_bound = complement;
- high_bound = bound;
- if (wi::lts_p (wi::to_wide (vr0.max), high_bound)
- && wi::lts_p (low_bound, wi::to_wide (vr0.min)))
- {
- /* For non-negative numbers, we're shifting out only
- zeroes, the value increases monotonically.
- For negative numbers, we're shifting out only ones, the
- value decreases monotomically. */
- in_bounds = true;
- }
- }
+ else if (op0)
+ wi = wi::to_wide (op0);
+ else if (op1)
+ {
+ if (minus_p)
+ wi = wi::neg (wi::to_wide (op1), &ovf);
+ else
+ wi = wi::to_wide (op1);
+ }
+ else
+ wi = wi::shwi (0, prec);
+}
- if (in_bounds)
- {
- extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
- return;
- }
- }
- }
- set_value_range_to_varying (vr);
+/* Given a range in [WMIN, WMAX], adjust it for possible overflow and
+ put the result in VR.
+
+ TYPE is the type of the range.
+
+ MIN_OVF and MAX_OVF indicate what type of overflow, if any,
+ occurred while originally calculating WMIN or WMAX. -1 indicates
+ underflow. +1 indicates overflow. 0 indicates neither. */
+
+static void
+set_value_range_with_overflow (value_range_kind &kind, tree &min, tree &max,
+ tree type,
+ const wide_int &wmin, const wide_int &wmax,
+ wi::overflow_type min_ovf,
+ wi::overflow_type max_ovf)
+{
+ const signop sgn = TYPE_SIGN (type);
+ const unsigned int prec = TYPE_PRECISION (type);
+
+ /* For one bit precision if max < min, then the swapped
+ range covers all values. */
+ if (prec == 1 && wi::lt_p (wmax, wmin, sgn))
+ {
+ kind = VR_VARYING;
return;
}
- else if (code == TRUNC_DIV_EXPR
- || code == FLOOR_DIV_EXPR
- || code == CEIL_DIV_EXPR
- || code == EXACT_DIV_EXPR
- || code == ROUND_DIV_EXPR)
+
+ if (TYPE_OVERFLOW_WRAPS (type))
{
- if (vr0.type != VR_RANGE || symbolic_range_p (&vr0))
+ /* If overflow wraps, truncate the values and adjust the
+ range kind and bounds appropriately. */
+ wide_int tmin = wide_int::from (wmin, prec, sgn);
+ wide_int tmax = wide_int::from (wmax, prec, sgn);
+ if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE))
{
- /* For division, if op1 has VR_RANGE but op0 does not, something
- can be deduced just from that range. Say [min, max] / [4, max]
- gives [min / 4, max / 4] range. */
- if (vr1.type == VR_RANGE
- && !symbolic_range_p (&vr1)
- && range_includes_zero_p (vr1.min, vr1.max) == 0)
- {
- vr0.type = type = VR_RANGE;
- vr0.min = vrp_val_min (expr_type);
- vr0.max = vrp_val_max (expr_type);
- }
+ /* If the limits are swapped, we wrapped around and cover
+ the entire range. */
+ if (wi::gt_p (tmin, tmax, sgn))
+ kind = VR_VARYING;
else
{
- set_value_range_to_varying (vr);
- return;
+ kind = VR_RANGE;
+ /* No overflow or both overflow or underflow. The
+ range kind stays VR_RANGE. */
+ min = wide_int_to_tree (type, tmin);
+ max = wide_int_to_tree (type, tmax);
}
- }
-
- /* For divisions, if flag_non_call_exceptions is true, we must
- not eliminate a division by zero. */
- if (cfun->can_throw_non_call_exceptions
- && (vr1.type != VR_RANGE
- || range_includes_zero_p (vr1.min, vr1.max) != 0))
- {
- set_value_range_to_varying (vr);
return;
}
-
- /* For divisions, if op0 is VR_RANGE, we can deduce a range
- even if op1 is VR_VARYING, VR_ANTI_RANGE, symbolic or can
- include 0. */
- if (vr0.type == VR_RANGE
- && (vr1.type != VR_RANGE
- || range_includes_zero_p (vr1.min, vr1.max) != 0))
- {
- tree zero = build_int_cst (TREE_TYPE (vr0.min), 0);
- int cmp;
-
- min = NULL_TREE;
- max = NULL_TREE;
- if (TYPE_UNSIGNED (expr_type)
- || value_range_nonnegative_p (&vr1))
- {
- /* For unsigned division or when divisor is known
- to be non-negative, the range has to cover
- all numbers from 0 to max for positive max
- and all numbers from min to 0 for negative min. */
- cmp = compare_values (vr0.max, zero);
- if (cmp == -1)
- {
- /* When vr0.max < 0, vr1.min != 0 and value
- ranges for dividend and divisor are available. */
- if (vr1.type == VR_RANGE
- && !symbolic_range_p (&vr0)
- && !symbolic_range_p (&vr1)
- && compare_values (vr1.min, zero) != 0)
- max = int_const_binop (code, vr0.max, vr1.min);
- else
- max = zero;
- }
- else if (cmp == 0 || cmp == 1)
- max = vr0.max;
- else
- type = VR_VARYING;
- cmp = compare_values (vr0.min, zero);
- if (cmp == 1)
- {
- /* For unsigned division when value ranges for dividend
- and divisor are available. */
- if (vr1.type == VR_RANGE
- && !symbolic_range_p (&vr0)
- && !symbolic_range_p (&vr1)
- && compare_values (vr1.max, zero) != 0)
- min = int_const_binop (code, vr0.min, vr1.max);
- else
- min = zero;
- }
- else if (cmp == 0 || cmp == -1)
- min = vr0.min;
- else
- type = VR_VARYING;
- }
- else
+ else if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE)
+ || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE))
+ {
+ /* Min underflow or max overflow. The range kind
+ changes to VR_ANTI_RANGE. */
+ bool covers = false;
+ wide_int tem = tmin;
+ tmin = tmax + 1;
+ if (wi::cmp (tmin, tmax, sgn) < 0)
+ covers = true;
+ tmax = tem - 1;
+ if (wi::cmp (tmax, tem, sgn) > 0)
+ covers = true;
+ /* If the anti-range would cover nothing, drop to varying.
+ Likewise if the anti-range bounds are outside of the
+ types values. */
+ if (covers || wi::cmp (tmin, tmax, sgn) > 0)
{
- /* Otherwise the range is -max .. max or min .. -min
- depending on which bound is bigger in absolute value,
- as the division can change the sign. */
- abs_extent_range (vr, vr0.min, vr0.max);
- return;
- }
- if (type == VR_VARYING)
- {
- set_value_range_to_varying (vr);
+ kind = VR_VARYING;
return;
}
+ kind = VR_ANTI_RANGE;
+ min = wide_int_to_tree (type, tmin);
+ max = wide_int_to_tree (type, tmax);
+ return;
}
- else if (!symbolic_range_p (&vr0) && !symbolic_range_p (&vr1))
+ else
{
- extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
+ /* Other underflow and/or overflow, drop to VR_VARYING. */
+ kind = VR_VARYING;
return;
}
}
- else if (code == TRUNC_MOD_EXPR)
+ else
{
- if (range_is_null (&vr1))
- {
- set_value_range_to_undefined (vr);
- return;
- }
- /* ABS (A % B) < ABS (B) and either
- 0 <= A % B <= A or A <= A % B <= 0. */
- type = VR_RANGE;
- signop sgn = TYPE_SIGN (expr_type);
- unsigned int prec = TYPE_PRECISION (expr_type);
- wide_int wmin, wmax, tmp;
- if (vr1.type == VR_RANGE && !symbolic_range_p (&vr1))
- {
- wmax = wi::to_wide (vr1.max) - 1;
- if (sgn == SIGNED)
- {
- tmp = -1 - wi::to_wide (vr1.min);
- wmax = wi::smax (wmax, tmp);
- }
- }
+ /* If overflow does not wrap, saturate to the types min/max
+ value. */
+ wide_int type_min = wi::min_value (prec, sgn);
+ wide_int type_max = wi::max_value (prec, sgn);
+ kind = VR_RANGE;
+ if (min_ovf == wi::OVF_UNDERFLOW)
+ min = wide_int_to_tree (type, type_min);
+ else if (min_ovf == wi::OVF_OVERFLOW)
+ min = wide_int_to_tree (type, type_max);
else
- {
- wmax = wi::max_value (prec, sgn);
- /* X % INT_MIN may be INT_MAX. */
- if (sgn == UNSIGNED)
- wmax = wmax - 1;
- }
+ min = wide_int_to_tree (type, wmin);
- if (sgn == UNSIGNED)
- wmin = wi::zero (prec);
+ if (max_ovf == wi::OVF_UNDERFLOW)
+ max = wide_int_to_tree (type, type_min);
+ else if (max_ovf == wi::OVF_OVERFLOW)
+ max = wide_int_to_tree (type, type_max);
else
- {
- wmin = -wmax;
- if (vr0.type == VR_RANGE && TREE_CODE (vr0.min) == INTEGER_CST)
- {
- tmp = wi::to_wide (vr0.min);
- if (wi::gts_p (tmp, 0))
- tmp = wi::zero (prec);
- wmin = wi::smax (wmin, tmp);
- }
- }
+ max = wide_int_to_tree (type, wmax);
+ }
+}
- if (vr0.type == VR_RANGE && TREE_CODE (vr0.max) == INTEGER_CST)
- {
- tmp = wi::to_wide (vr0.max);
- if (sgn == SIGNED && wi::neg_p (tmp))
- tmp = wi::zero (prec);
- wmax = wi::min (wmax, tmp, sgn);
- }
+/* Fold two value range's of a POINTER_PLUS_EXPR into VR. */
- min = wide_int_to_tree (expr_type, wmin);
- max = wide_int_to_tree (expr_type, wmax);
- }
- else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR)
- {
- bool int_cst_range0, int_cst_range1;
- wide_int may_be_nonzero0, may_be_nonzero1;
- wide_int must_be_nonzero0, must_be_nonzero1;
+static void
+extract_range_from_pointer_plus_expr (value_range_base *vr,
+ enum tree_code code,
+ tree expr_type,
+ const value_range_base *vr0,
+ const value_range_base *vr1)
+{
+ 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);
+}
- int_cst_range0 = zero_nonzero_bits_from_vr (expr_type, &vr0,
- &may_be_nonzero0,
- &must_be_nonzero0);
- int_cst_range1 = zero_nonzero_bits_from_vr (expr_type, &vr1,
- &may_be_nonzero1,
- &must_be_nonzero1);
+/* Extract range information from a PLUS/MINUS_EXPR and store the
+ result in *VR. */
- if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
- {
- value_range *vr0p = NULL, *vr1p = NULL;
- if (range_int_cst_singleton_p (&vr1))
- {
- vr0p = &vr0;
- vr1p = &vr1;
- }
- else if (range_int_cst_singleton_p (&vr0))
- {
- vr0p = &vr1;
- vr1p = &vr0;
- }
- /* For op & or | attempt to optimize:
- [x, y] op z into [x op z, y op z]
- if z is a constant which (for op | its bitwise not) has n
- consecutive least significant bits cleared followed by m 1
- consecutive bits set immediately above it and either
- m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
- The least significant n bits of all the values in the range are
- cleared or set, the m bits above it are preserved and any bits
- above these are required to be the same for all values in the
- range. */
- if (vr0p && range_int_cst_p (vr0p))
- {
- wide_int w = wi::to_wide (vr1p->min);
- int m = 0, n = 0;
- if (code == BIT_IOR_EXPR)
- w = ~w;
- if (wi::eq_p (w, 0))
- n = TYPE_PRECISION (expr_type);
- else
- {
- n = wi::ctz (w);
- w = ~(w | wi::mask (n, false, w.get_precision ()));
- if (wi::eq_p (w, 0))
- m = TYPE_PRECISION (expr_type) - n;
- else
- m = wi::ctz (w) - n;
- }
- wide_int mask = wi::mask (m + n, true, w.get_precision ());
- if ((mask & wi::to_wide (vr0p->min))
- == (mask & wi::to_wide (vr0p->max)))
- {
- min = int_const_binop (code, vr0p->min, vr1p->min);
- max = int_const_binop (code, vr0p->max, vr1p->min);
- }
- }
- }
+static void
+extract_range_from_plus_minus_expr (value_range_base *vr,
+ enum tree_code code,
+ tree expr_type,
+ const value_range_base *vr0_,
+ const value_range_base *vr1_)
+{
+ gcc_checking_assert (code == PLUS_EXPR || code == MINUS_EXPR);
+
+ value_range_base vr0 = *vr0_, vr1 = *vr1_;
+ value_range_base vrtem0, vrtem1;
- type = VR_RANGE;
- if (min && max)
- /* Optimized above already. */;
- else if (code == BIT_AND_EXPR)
+ /* 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_plus_minus_expr (vr, code, expr_type, &vrtem0, vr1_);
+ if (!vrtem1.undefined_p ())
{
- min = wide_int_to_tree (expr_type,
- must_be_nonzero0 & must_be_nonzero1);
- wide_int wmax = may_be_nonzero0 & may_be_nonzero1;
- /* If both input ranges contain only negative values we can
- truncate the result range maximum to the minimum of the
- input range maxima. */
- if (int_cst_range0 && int_cst_range1
- && tree_int_cst_sgn (vr0.max) < 0
- && tree_int_cst_sgn (vr1.max) < 0)
- {
- wmax = wi::min (wmax, wi::to_wide (vr0.max),
- TYPE_SIGN (expr_type));
- wmax = wi::min (wmax, wi::to_wide (vr1.max),
- TYPE_SIGN (expr_type));
- }
- /* If either input range contains only non-negative values
- we can truncate the result range maximum to the respective
- maximum of the input range. */
- if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
- wmax = wi::min (wmax, wi::to_wide (vr0.max),
- TYPE_SIGN (expr_type));
- if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0)
- wmax = wi::min (wmax, wi::to_wide (vr1.max),
- TYPE_SIGN (expr_type));
- max = wide_int_to_tree (expr_type, wmax);
- cmp = compare_values (min, max);
- /* PR68217: In case of signed & sign-bit-CST should
- result in [-INF, 0] instead of [-INF, INF]. */
- if (cmp == -2 || cmp == 1)
- {
- wide_int sign_bit
- = wi::set_bit_in_zero (TYPE_PRECISION (expr_type) - 1,
- TYPE_PRECISION (expr_type));
- if (!TYPE_UNSIGNED (expr_type)
- && ((int_cst_range0
- && value_range_constant_singleton (&vr0)
- && !wi::cmps (wi::to_wide (vr0.min), sign_bit))
- || (int_cst_range1
- && value_range_constant_singleton (&vr1)
- && !wi::cmps (wi::to_wide (vr1.min), sign_bit))))
- {
- min = TYPE_MIN_VALUE (expr_type);
- max = build_int_cst (expr_type, 0);
- }
- }
+ value_range_base vrres;
+ extract_range_from_plus_minus_expr (&vrres, code, expr_type,
+ &vrtem1, vr1_);
+ vr->union_ (&vrres);
}
- else if (code == BIT_IOR_EXPR)
+ return;
+ }
+ /* Likewise for X op ~[]. */
+ if (vr1.kind () == VR_ANTI_RANGE
+ && ranges_from_anti_range (&vr1, &vrtem0, &vrtem1))
+ {
+ extract_range_from_plus_minus_expr (vr, code, expr_type, vr0_, &vrtem0);
+ if (!vrtem1.undefined_p ())
{
- max = wide_int_to_tree (expr_type,
- may_be_nonzero0 | may_be_nonzero1);
- wide_int wmin = must_be_nonzero0 | must_be_nonzero1;
- /* If the input ranges contain only positive values we can
- truncate the minimum of the result range to the maximum
- of the input range minima. */
- if (int_cst_range0 && int_cst_range1
- && tree_int_cst_sgn (vr0.min) >= 0
- && tree_int_cst_sgn (vr1.min) >= 0)
- {
- wmin = wi::max (wmin, wi::to_wide (vr0.min),
- TYPE_SIGN (expr_type));
- wmin = wi::max (wmin, wi::to_wide (vr1.min),
- TYPE_SIGN (expr_type));
- }
- /* If either input range contains only negative values
- we can truncate the minimum of the result range to the
- respective minimum range. */
- if (int_cst_range0 && tree_int_cst_sgn (vr0.max) < 0)
- wmin = wi::max (wmin, wi::to_wide (vr0.min),
- TYPE_SIGN (expr_type));
- if (int_cst_range1 && tree_int_cst_sgn (vr1.max) < 0)
- wmin = wi::max (wmin, wi::to_wide (vr1.min),
- TYPE_SIGN (expr_type));
- min = wide_int_to_tree (expr_type, wmin);
+ value_range_base vrres;
+ extract_range_from_plus_minus_expr (&vrres, code, expr_type,
+ vr0_, &vrtem1);
+ vr->union_ (&vrres);
+ }
+ return;
+ }
+
+ 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 ())
+ {
+ vr0_kind = VR_RANGE;
+ vr0_min = vrp_val_min (expr_type);
+ vr0_max = vrp_val_max (expr_type);
+ }
+ if (vr1.varying_p ())
+ {
+ vr1_kind = VR_RANGE;
+ vr1_min = vrp_val_min (expr_type);
+ vr1_max = 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 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)))
+ {
+ vr->set_varying (expr_type);
+ return;
}
- else if (code == BIT_XOR_EXPR)
+
+ /* 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)
{
- wide_int result_zero_bits = ((must_be_nonzero0 & must_be_nonzero1)
- | ~(may_be_nonzero0 | may_be_nonzero1));
- wide_int result_one_bits
- = (wi::bit_and_not (must_be_nonzero0, may_be_nonzero1)
- | wi::bit_and_not (must_be_nonzero1, may_be_nonzero0));
- max = wide_int_to_tree (expr_type, ~result_zero_bits);
- min = wide_int_to_tree (expr_type, result_one_bits);
- /* If the range has all positive or all negative values the
- result is better than VARYING. */
- if (tree_int_cst_sgn (min) < 0
- || tree_int_cst_sgn (max) >= 0)
- ;
- else
- max = min = NULL_TREE;
+ vr->set_varying (expr_type);
+ 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
- gcc_unreachable ();
+ {
+ /* 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;
+ }
/* If either MIN or MAX overflowed, then set the resulting range to
VARYING. */
|| max == NULL_TREE
|| TREE_OVERFLOW_P (max))
{
- set_value_range_to_varying (vr);
- 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);
+ vr->set_varying (expr_type);
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 (kind, min, max);
}
-/* 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. */
+/* Return the range-ops handler for CODE and EXPR_TYPE. If no
+ suitable operator is found, return NULL and set VR to VARYING. */
-void
-extract_range_from_unary_expr (value_range *vr,
- enum tree_code code, tree type,
- value_range *vr0_, tree op0_type)
+static const range_operator *
+get_range_op_handler (value_range_base *vr,
+ enum tree_code code,
+ tree expr_type)
{
- value_range vr0 = *vr0_, vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER;
-
- /* 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;
- }
+ const range_operator *op = range_op_handler (code, expr_type);
+ if (!op)
+ vr->set_varying (expr_type);
+ return op;
+}
- /* If VR0 is UNDEFINED, so is the result. */
- if (vr0.type == VR_UNDEFINED)
- {
- set_value_range_to_undefined (vr);
- return;
- }
+/* If the types passed are supported, return TRUE, otherwise set VR to
+ VARYING and return FALSE. */
- /* 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. */
- copy_value_range (vr, &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 = VR_INITIALIZER;
- 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)
+static bool
+supported_types_p (value_range_base *vr,
+ tree type0,
+ tree type1 = NULL)
+{
+ if (!value_range_base::supports_type_p (type0)
+ || (type1 && !value_range_base::supports_type_p (type1)))
{
- /* ~X is simply -1 - X, so re-use existing code that also handles
- anti-ranges fine. */
- value_range minusone = VR_INITIALIZER;
- 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;
+ vr->set_varying (type0);
+ return false;
}
+ return true;
+}
- /* Now canonicalize anti-ranges to ranges when they are not symbolic
- and express op ~[] as (op []') U (op []''). */
- if (vr0.type == VR_ANTI_RANGE
- && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
- {
- extract_range_from_unary_expr (vr, code, type, &vrtem0, op0_type);
- if (vrtem1.type != VR_UNDEFINED)
- {
- value_range vrres = VR_INITIALIZER;
- extract_range_from_unary_expr (&vrres, code, type,
- &vrtem1, op0_type);
- vrp_meet (vr, &vrres);
- }
- return;
- }
+/* If any of the ranges passed are defined, return TRUE, otherwise set
+ VR to UNDEFINED and return FALSE. */
- if (CONVERT_EXPR_CODE_P (code))
+static bool
+defined_ranges_p (value_range_base *vr,
+ const value_range_base *vr0,
+ const value_range_base *vr1 = NULL)
+{
+ if (vr0->undefined_p () && (!vr1 || vr1->undefined_p ()))
{
- tree inner_type = op0_type;
- tree outer_type = type;
-
- /* If the expression evaluates to a pointer, we are only interested in
- determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
- if (POINTER_TYPE_P (type))
- {
- if (range_is_nonnull (&vr0))
- set_value_range_to_nonnull (vr, type);
- else if (range_is_null (&vr0))
- set_value_range_to_null (vr, type);
- else
- set_value_range_to_varying (vr);
- return;
- }
-
- /* If VR0 is varying and we increase the type precision, assume
- a full range for the following transformation. */
- if (vr0.type == VR_VARYING
- && INTEGRAL_TYPE_P (inner_type)
- && TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type))
- {
- vr0.type = VR_RANGE;
- vr0.min = TYPE_MIN_VALUE (inner_type);
- vr0.max = TYPE_MAX_VALUE (inner_type);
- }
-
- /* If VR0 is a constant range or anti-range and the conversion is
- not truncating we can convert the min and max values and
- canonicalize the resulting range. Otherwise we can do the
- conversion if the size of the range is less than what the
- precision of the target type can represent and the range is
- not an anti-range. */
- if ((vr0.type == VR_RANGE
- || vr0.type == VR_ANTI_RANGE)
- && TREE_CODE (vr0.min) == INTEGER_CST
- && TREE_CODE (vr0.max) == INTEGER_CST
- && (TYPE_PRECISION (outer_type) >= TYPE_PRECISION (inner_type)
- || (vr0.type == VR_RANGE
- && integer_zerop (int_const_binop (RSHIFT_EXPR,
- int_const_binop (MINUS_EXPR, vr0.max, vr0.min),
- size_int (TYPE_PRECISION (outer_type)))))))
- {
- tree new_min, new_max;
- new_min = force_fit_type (outer_type, wi::to_widest (vr0.min),
- 0, false);
- new_max = force_fit_type (outer_type, wi::to_widest (vr0.max),
- 0, false);
- set_and_canonicalize_value_range (vr, vr0.type,
- new_min, new_max, NULL);
- return;
- }
-
- set_value_range_to_varying (vr);
- return;
+ vr->set_undefined ();
+ return false;
}
- else if (code == ABS_EXPR)
- {
- tree min, max;
- int cmp;
-
- /* Pass through vr0 in the easy cases. */
- if (TYPE_UNSIGNED (type)
- || value_range_nonnegative_p (&vr0))
- {
- copy_value_range (vr, &vr0);
- return;
- }
-
- /* For the remaining varying or symbolic ranges we can't do anything
- useful. */
- if (vr0.type == VR_VARYING
- || symbolic_range_p (&vr0))
- {
- set_value_range_to_varying (vr);
- return;
- }
-
- /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
- useful range. */
- if (!TYPE_OVERFLOW_UNDEFINED (type)
- && ((vr0.type == VR_RANGE
- && vrp_val_is_min (vr0.min))
- || (vr0.type == VR_ANTI_RANGE
- && !vrp_val_is_min (vr0.min))))
- {
- set_value_range_to_varying (vr);
- return;
- }
-
- /* ABS_EXPR may flip the range around, if the original range
- included negative values. */
- if (!vrp_val_is_min (vr0.min))
- min = fold_unary_to_constant (code, type, vr0.min);
- else
- min = TYPE_MAX_VALUE (type);
+ return true;
+}
- if (!vrp_val_is_min (vr0.max))
- max = fold_unary_to_constant (code, type, vr0.max);
- else
- max = TYPE_MAX_VALUE (type);
+static value_range_base
+drop_undefines_to_varying (const value_range_base *vr, tree expr_type)
+{
+ if (vr->undefined_p ())
+ return value_range_base (expr_type);
+ else
+ return *vr;
+}
- cmp = compare_values (min, max);
+/* If any operand is symbolic, perform a binary operation on them and
+ return TRUE, otherwise return FALSE. */
- /* If a VR_ANTI_RANGEs contains zero, then we have
- ~[-INF, min(MIN, MAX)]. */
- if (vr0.type == VR_ANTI_RANGE)
+static bool
+range_fold_binary_symbolics_p (value_range_base *vr,
+ tree_code code,
+ tree expr_type,
+ const value_range_base *vr0,
+ const value_range_base *vr1)
+{
+ if (vr0->symbolic_p () || vr1->symbolic_p ())
+ {
+ if ((code == PLUS_EXPR || code == MINUS_EXPR))
{
- if (range_includes_zero_p (vr0.min, vr0.max) == 1)
- {
- /* Take the lower of the two values. */
- if (cmp != 1)
- max = min;
-
- /* Create ~[-INF, min (abs(MIN), abs(MAX))]
- or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
- flag_wrapv is set and the original anti-range doesn't include
- TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */
- if (TYPE_OVERFLOW_WRAPS (type))
- {
- tree type_min_value = TYPE_MIN_VALUE (type);
-
- min = (vr0.min != type_min_value
- ? int_const_binop (PLUS_EXPR, type_min_value,
- build_int_cst (TREE_TYPE (type_min_value), 1))
- : type_min_value);
- }
- else
- min = TYPE_MIN_VALUE (type);
- }
- else
- {
- /* All else has failed, so create the range [0, INF], even for
- flag_wrapv since TYPE_MIN_VALUE is in the original
- anti-range. */
- vr0.type = VR_RANGE;
- min = build_int_cst (type, 0);
- max = TYPE_MAX_VALUE (type);
- }
+ extract_range_from_plus_minus_expr (vr, code, expr_type, vr0, vr1);
+ return true;
}
-
- /* If the range contains zero then we know that the minimum value in the
- range will be zero. */
- else if (range_includes_zero_p (vr0.min, vr0.max) == 1)
+ if (POINTER_TYPE_P (expr_type) && code == POINTER_PLUS_EXPR)
{
- if (cmp == 1)
- max = min;
- min = build_int_cst (type, 0);
+ extract_range_from_pointer_plus_expr (vr, code, expr_type, vr0, vr1);
+ return true;
}
- else
+ const range_operator *op = get_range_op_handler (vr, code, expr_type);
+ *vr = op->fold_range (expr_type,
+ vr0->normalize_symbolics (),
+ vr1->normalize_symbolics ());
+ return true;
+ }
+ 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_base *vr,
+ tree_code code,
+ tree expr_type,
+ const value_range_base *vr0)
+{
+ if (vr0->symbolic_p ())
+ {
+ if (code == NEGATE_EXPR)
{
- /* If the range was reversed, swap MIN and MAX. */
- if (cmp == 1)
- std::swap (min, max);
+ /* -X is simply 0 - X. */
+ value_range_base zero;
+ zero.set_zero (vr0->type ());
+ range_fold_binary_expr (vr, MINUS_EXPR, expr_type, &zero, vr0);
+ return true;
}
-
- cmp = compare_values (min, max);
- if (cmp == -2 || cmp == 1)
+ if (code == BIT_NOT_EXPR)
{
- /* 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);
+ /* ~X is simply -1 - X. */
+ value_range_base minusone;
+ minusone.set (build_int_cst (vr0->type (), -1));
+ range_fold_binary_expr (vr, MINUS_EXPR, expr_type, &minusone, vr0);
+ return true;
}
- else
- set_value_range (vr, vr0.type, min, max, NULL);
- return;
+ const range_operator *op = get_range_op_handler (vr, code, expr_type);
+ *vr = op->fold_range (expr_type,
+ vr0->normalize_symbolics (),
+ value_range_base (expr_type));
+ return true;
}
-
- /* For unhandled operations fall back to varying. */
- set_value_range_to_varying (vr);
- return;
+ return false;
}
-/* Debugging dumps. */
-
-void dump_value_range (FILE *, const value_range *);
-void debug_value_range (value_range *);
-void dump_all_value_ranges (FILE *);
-void dump_vr_equiv (FILE *, bitmap);
-void debug_vr_equiv (bitmap);
-
-
-/* Dump value range VR to FILE. */
+/* Perform a binary operation on a pair of ranges. */
void
-dump_value_range (FILE *file, const value_range *vr)
+range_fold_binary_expr (value_range_base *vr,
+ enum tree_code code,
+ tree expr_type,
+ const value_range_base *vr0_,
+ const value_range_base *vr1_)
{
- if (vr == NULL)
- fprintf (file, "[]");
- else if (vr->type == VR_UNDEFINED)
- fprintf (file, "UNDEFINED");
- else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
- {
- tree type = TREE_TYPE (vr->min);
-
- fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
-
- if (INTEGRAL_TYPE_P (type)
- && !TYPE_UNSIGNED (type)
- && vrp_val_is_min (vr->min))
- fprintf (file, "-INF");
- else
- print_generic_expr (file, vr->min);
-
- fprintf (file, ", ");
-
- if (INTEGRAL_TYPE_P (type)
- && vrp_val_is_max (vr->max))
- fprintf (file, "+INF");
- else
- print_generic_expr (file, vr->max);
-
- fprintf (file, "]");
-
- if (vr->equiv)
- {
- bitmap_iterator bi;
- unsigned i, c = 0;
-
- fprintf (file, " EQUIVALENCES: { ");
+ 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;
- EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
- {
- print_generic_expr (file, ssa_name (i));
- fprintf (file, " ");
- c++;
- }
+ value_range_base vr0 = drop_undefines_to_varying (vr0_, expr_type);
+ value_range_base vr1 = drop_undefines_to_varying (vr1_, expr_type);
+ if (range_fold_binary_symbolics_p (vr, code, expr_type, &vr0, &vr1))
+ return;
- fprintf (file, "} (%u elements)", c);
- }
- }
- else if (vr->type == VR_VARYING)
- fprintf (file, "VARYING");
- else
- fprintf (file, "INVALID RANGE");
+ *vr = op->fold_range (expr_type,
+ vr0.normalize_addresses (),
+ vr1.normalize_addresses ());
}
+/* Perform a unary operation on a range. */
-/* Dump value range VR to stderr. */
-
-DEBUG_FUNCTION void
-debug_value_range (value_range *vr)
+void
+range_fold_unary_expr (value_range_base *vr,
+ enum tree_code code, tree expr_type,
+ const value_range_base *vr0,
+ tree vr0_type)
{
- dump_value_range (stderr, vr);
- fprintf (stderr, "\n");
-}
+ 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;
+ *vr = op->fold_range (expr_type,
+ vr0->normalize_addresses (),
+ value_range_base (expr_type));
+}
/* 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
assert_info info;
info.comp_code = comp_code;
info.name = name;
+ if (TREE_OVERFLOW_P (val))
+ val = drop_tree_overflow (val);
info.val = val;
info.expr = expr;
asserts.safe_push (info);
+ if (dump_enabled_p ())
+ dump_printf (MSG_NOTE | MSG_PRIORITY_INTERNALS,
+ "Adding assert for %T from %T %s %T\n",
+ name, expr, op_symbol_code (comp_code), val);
}
/* If NAME doesn't have an ASSERT_EXPR registered for asserting
tmp = build1 (NOP_EXPR, TREE_TYPE (name), name3);
if (cst2 != NULL_TREE)
tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2);
-
- if (dump_file)
- {
- fprintf (dump_file, "Adding assert for ");
- print_generic_expr (dump_file, name3);
- fprintf (dump_file, " from ");
- print_generic_expr (dump_file, tmp);
- fprintf (dump_file, "\n");
- }
-
add_assert_info (asserts, name3, tmp, comp_code, val);
}
tmp = build1 (NOP_EXPR, TREE_TYPE (name), tmp);
if (cst2 != NULL_TREE)
tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2);
-
- if (dump_file)
- {
- fprintf (dump_file, "Adding assert for ");
- print_generic_expr (dump_file, name2);
- fprintf (dump_file, " from ");
- print_generic_expr (dump_file, tmp);
- fprintf (dump_file, "\n");
- }
-
add_assert_info (asserts, name2, tmp, comp_code, val);
}
}
{
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))
cst = fold_build2 (MINUS_EXPR, TREE_TYPE (name2), cst,
build_int_cst (TREE_TYPE (name2), 1));
}
-
- if (dump_file)
- {
- fprintf (dump_file, "Adding assert for ");
- print_generic_expr (dump_file, name2);
- fprintf (dump_file, " from ");
- print_generic_expr (dump_file, tmp);
- fprintf (dump_file, "\n");
- }
-
add_assert_info (asserts, name2, tmp, new_comp_code, cst);
}
}
}
if (new_val)
- {
- if (dump_file)
- {
- fprintf (dump_file, "Adding assert for ");
- print_generic_expr (dump_file, name2);
- fprintf (dump_file, " from ");
- print_generic_expr (dump_file, tmp);
- fprintf (dump_file, "\n");
- }
-
- add_assert_info (asserts, name2, tmp, new_comp_code, new_val);
- }
+ 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
{
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]))))
maxv2 = maxv - minv;
}
new_val = wide_int_to_tree (type, maxv2);
-
- if (dump_file)
- {
- fprintf (dump_file, "Adding assert for ");
- print_generic_expr (dump_file, names[i]);
- fprintf (dump_file, " from ");
- print_generic_expr (dump_file, tmp);
- fprintf (dump_file, "\n");
- }
-
add_assert_info (asserts, names[i], tmp, LE_EXPR, new_val);
}
}
Such comparison can yield assertions like
X >= XX...X00...0
X <= XX...X11...1
- in case of COND_OP being NE_EXPR or
+ in case of COND_OP being EQ_EXPR or
X < XX...X00...0
X > XX...X11...1
- in case of EQ_EXPR. */
+ in case of NE_EXPR. */
static bool
is_masked_range_test (tree name, tree valt, enum tree_code cond_code,
wi::tree_to_wide_ref mask = wi::to_wide (maskt);
wide_int inv_mask = ~mask;
+ /* Must have been removed by now so don't bother optimizing. */
+ if (mask == 0 || inv_mask == 0)
+ return false;
+
/* Assume VALT is INTEGER_CST. */
wi::tree_to_wide_ref val = wi::to_wide (valt);
*low = wide_int_to_tree (type, val);
*high = wide_int_to_tree (type, val | inv_mask);
- if (wi::neg_p (val, TYPE_SIGN (type)))
- std::swap (*low, *high);
-
return true;
}
for (idx = 0; idx < n; ++idx)
{
ci[idx].expr = gimple_switch_label (last, idx);
- ci[idx].bb = label_to_block (CASE_LABEL (ci[idx].expr));
+ ci[idx].bb = label_to_block (cfun, CASE_LABEL (ci[idx].expr));
}
edge default_edge = find_edge (bb, ci[0].bb);
qsort (ci, n, sizeof (struct case_info), compare_case_labels);
void vrp_initialize (void);
void vrp_finalize (bool);
void check_all_array_refs (void);
- void check_array_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 *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)
{ vr_values.extract_range_from_stmt (stmt, taken_edge_p, output_p, vr); }
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. */
+ IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR.
+ Returns true if a warning has been issued. */
-void
+bool
vrp_prop::check_array_ref (location_t location, tree ref,
bool ignore_off_by_one)
{
- value_range *vr = NULL;
+ const value_range *vr = NULL;
tree low_sub, up_sub;
tree low_bound, up_bound, up_bound_p1;
if (TREE_NO_WARNING (ref))
- return;
+ return false;
low_sub = up_sub = TREE_OPERAND (ref, 1);
up_bound = array_ref_up_bound (ref);
{
tree maxbound = TYPE_MAX_VALUE (ptrdiff_type_node);
tree arg = TREE_OPERAND (ref, 0);
- HOST_WIDE_INT off;
+ poly_int64 off;
- if (get_addr_base_and_unit_offset (arg, &off) && off > 0)
+ 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));
tree artype = TREE_TYPE (TREE_OPERAND (ref, 0));
+ bool warned = false;
+
/* Empty array. */
if (up_bound && tree_int_cst_equal (low_bound, up_bound_p1))
- {
- warning_at (location, OPT_Warray_bounds,
- "array subscript %E is above array bounds of %qT",
- low_bound, artype);
- TREE_NO_WARNING (ref) = 1;
- }
+ warned = warning_at (location, OPT_Warray_bounds,
+ "array subscript %E is above array bounds of %qT",
+ low_bound, artype);
if (TREE_CODE (low_sub) == SSA_NAME)
{
vr = get_value_range (low_sub);
- if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
+ if (!vr->undefined_p () && !vr->varying_p ())
{
- low_sub = vr->type == VR_RANGE ? vr->max : vr->min;
- up_sub = vr->type == VR_RANGE ? vr->min : vr->max;
+ low_sub = vr->kind () == VR_RANGE ? vr->max () : vr->min ();
+ up_sub = vr->kind () == VR_RANGE ? vr->min () : vr->max ();
}
}
- if (vr && vr->type == VR_ANTI_RANGE)
+ if (vr && vr->kind () == VR_ANTI_RANGE)
{
if (up_bound
&& TREE_CODE (up_sub) == INTEGER_CST
: tree_int_cst_le (up_bound, up_sub))
&& TREE_CODE (low_sub) == INTEGER_CST
&& tree_int_cst_le (low_sub, low_bound))
- {
- warning_at (location, OPT_Warray_bounds,
- "array subscript [%E, %E] is outside array bounds of %qT",
- low_sub, up_sub, artype);
- TREE_NO_WARNING (ref) = 1;
- }
+ warned = warning_at (location, OPT_Warray_bounds,
+ "array subscript [%E, %E] is outside "
+ "array bounds of %qT",
+ low_sub, up_sub, artype);
}
else if (up_bound
&& TREE_CODE (up_sub) == INTEGER_CST
dump_generic_expr (MSG_NOTE, TDF_SLIM, ref);
fprintf (dump_file, "\n");
}
- warning_at (location, OPT_Warray_bounds,
- "array subscript %E is above array bounds of %qT",
- up_sub, artype);
- TREE_NO_WARNING (ref) = 1;
+ 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))
dump_generic_expr (MSG_NOTE, TDF_SLIM, ref);
fprintf (dump_file, "\n");
}
- warning_at (location, OPT_Warray_bounds,
- "array subscript %E is below array bounds of %qT",
- low_sub, artype);
+ 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 (TREE_CODE (ref) == COMPONENT_REF)
+ ref = TREE_OPERAND (ref, 1);
+
+ if (DECL_P (ref))
+ inform (DECL_SOURCE_LOCATION (ref), "while referencing %qD", ref);
+
TREE_NO_WARNING (ref) = 1;
}
+
+ return warned;
+}
+
+/* Checks one MEM_REF in REF, located at LOCATION, for out-of-bounds
+ references to string constants. If VRP can determine that the 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 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).
+ 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 false;
+
+ tree arg = TREE_OPERAND (ref, 0);
+ /* The constant and variable offset of the reference. */
+ tree cstoff = TREE_OPERAND (ref, 1);
+ tree varoff = NULL_TREE;
+
+ const offset_int maxobjsize = tree_to_shwi (max_object_size ());
+
+ /* The array or string constant bounds in bytes. Initially set
+ to [-MAXOBJSIZE - 1, MAXOBJSIZE] until a tighter bound is
+ determined. */
+ offset_int arrbounds[2] = { -maxobjsize - 1, maxobjsize };
+
+ /* The minimum and maximum intermediate offset. For a reference
+ to be valid, not only does the final offset/subscript must be
+ in bounds but all intermediate offsets should be as well.
+ GCC may be able to deal gracefully with such out-of-bounds
+ offsets so the checking is only enbaled at -Warray-bounds=2
+ where it may help detect bugs in uses of the intermediate
+ offsets that could otherwise not be detectable. */
+ offset_int ioff = wi::to_offset (fold_convert (ptrdiff_type_node, cstoff));
+ offset_int extrema[2] = { 0, wi::abs (ioff) };
+
+ /* The range of the byte offset into the reference. */
+ offset_int offrange[2] = { 0, 0 };
+
+ const value_range *vr = NULL;
+
+ /* Determine the offsets and increment OFFRANGE for the bounds of each.
+ 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_VALUE (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))
+ break;
+
+ tree_code code = gimple_assign_rhs_code (def);
+ if (code == POINTER_PLUS_EXPR)
+ {
+ arg = gimple_assign_rhs1 (def);
+ varoff = gimple_assign_rhs2 (def);
+ }
+ else if (code == ASSERT_EXPR)
+ {
+ arg = TREE_OPERAND (gimple_assign_rhs1 (def), 0);
+ continue;
+ }
+ else
+ return false;
+
+ /* VAROFF should always be a SSA_NAME here (and not even
+ INTEGER_CST) but there's no point in taking chances. */
+ if (TREE_CODE (varoff) != SSA_NAME)
+ break;
+
+ vr = get_value_range (varoff);
+ if (!vr || vr->undefined_p () || vr->varying_p ())
+ break;
+
+ if (!vr->constant_p ())
+ break;
+
+ if (vr->kind () == VR_RANGE)
+ {
+ 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
+ {
+ /* 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];
+ }
+ }
+ else
+ {
+ /* For an anti-range, analogously to the above, conservatively
+ add [-MAXOBJSIZE -1, MAXOBJSIZE] to OFFRANGE. */
+ offrange[0] += arrbounds[0];
+ offrange[1] += arrbounds[1];
+ }
+
+ /* Keep track of the minimum and maximum offset. */
+ if (offrange[1] < 0 && offrange[1] < extrema[0])
+ extrema[0] = offrange[1];
+ if (offrange[0] > 0 && offrange[0] > extrema[1])
+ extrema[1] = offrange[0];
+
+ if (offrange[0] < arrbounds[0])
+ offrange[0] = arrbounds[0];
+
+ if (offrange[1] > arrbounds[1])
+ offrange[1] = arrbounds[1];
+ }
+
+ if (TREE_CODE (arg) == ADDR_EXPR)
+ {
+ arg = TREE_OPERAND (arg, 0);
+ if (TREE_CODE (arg) != STRING_CST
+ && TREE_CODE (arg) != VAR_DECL)
+ return false;
+ }
+ else
+ 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. */
+ 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 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])
+ arrbounds[1] = wi::lrshift (maxobjsize, wi::floor_log2 (eltsize));
+ else
+ arrbounds[1] = (wi::to_offset (bnds[1]) - wi::to_offset (bnds[0])
+ + 1) * eltsize;
+ }
+ else
+ arrbounds[1] = wi::lrshift (maxobjsize, wi::floor_log2 (eltsize));
+
+ if (TREE_CODE (ref) == MEM_REF)
+ {
+ /* For MEM_REF determine a tighter bound of the non-array
+ element type. */
+ tree eltype = TREE_TYPE (reftype);
+ while (TREE_CODE (eltype) == ARRAY_TYPE)
+ eltype = TREE_TYPE (eltype);
+ eltsize = wi::to_offset (TYPE_SIZE_UNIT (eltype));
+ }
+ }
+ else
+ {
+ eltsize = 1;
+ arrbounds[1] = wi::to_offset (TYPE_SIZE_UNIT (reftype));
+ }
+
+ offrange[0] += ioff;
+ offrange[1] += ioff;
+
+ /* Compute the more permissive upper bound when IGNORE_OFF_BY_ONE
+ is set (when taking the address of the one-past-last element
+ of an array) but always use the stricter bound in diagnostics. */
+ offset_int ubound = arrbounds[1];
+ if (ignore_off_by_one)
+ ubound += 1;
+
+ if (offrange[0] >= ubound || offrange[1] < arrbounds[0])
+ {
+ /* Treat a reference to a non-array object as one to an array
+ of a single element. */
+ if (TREE_CODE (reftype) != ARRAY_TYPE)
+ reftype = build_array_type_nelts (reftype, 1);
+
+ if (TREE_CODE (ref) == MEM_REF)
+ {
+ /* 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. 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);
+ if (tree size = TYPE_SIZE_UNIT (type))
+ {
+ offrange[0] = offrange[0] / wi::to_offset (size);
+ offrange[1] = offrange[1] / wi::to_offset (size);
+ }
+ }
+ else
+ {
+ /* For anything other than MEM_REF, compute the index to
+ print in the diagnostic as the offset over element size. */
+ offrange[0] = offrange[0] / eltsize;
+ offrange[1] = offrange[1] / eltsize;
+ }
+
+ bool warned;
+ if (offrange[0] == offrange[1])
+ warned = warning_at (location, OPT_Warray_bounds,
+ "array subscript %wi is outside array bounds "
+ "of %qT",
+ offrange[0].to_shwi (), reftype);
+ else
+ warned = warning_at (location, OPT_Warray_bounds,
+ "array subscript [%wi, %wi] is outside "
+ "array bounds of %qT",
+ offrange[0].to_shwi (),
+ offrange[1].to_shwi (), reftype);
+ if (warned && DECL_P (arg))
+ inform (DECL_SOURCE_LOCATION (arg), "while referencing %qD", arg);
+
+ if (warned)
+ TREE_NO_WARNING (ref) = 1;
+ return warned;
+ }
+
+ if (warn_array_bounds < 2)
+ return false;
+
+ /* At level 2 check also intermediate offsets. */
+ int i = 0;
+ if (extrema[i] < -arrbounds[1] || extrema[i = 1] > ubound)
+ {
+ HOST_WIDE_INT tmpidx = extrema[i].to_shwi () / eltsize.to_shwi ();
+
+ 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
void
vrp_prop::search_for_addr_array (tree t, location_t location)
{
- /* Check each ARRAY_REFs in the reference chain. */
+ /* 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)
+ warned = check_mem_ref (location, t, true /*ignore_off_by_one*/);
+
+ if (warned)
+ TREE_NO_WARNING (t) = true;
t = TREE_OPERAND (t, 0);
}
- while (handled_component_p (t));
+ while (handled_component_p (t) || TREE_CODE (t) == MEM_REF);
- if (TREE_CODE (t) == MEM_REF
- && TREE_CODE (TREE_OPERAND (t, 0)) == ADDR_EXPR
- && !TREE_NO_WARNING (t))
- {
- tree tem = TREE_OPERAND (TREE_OPERAND (t, 0), 0);
- tree low_bound, up_bound, el_sz;
- offset_int idx;
- if (TREE_CODE (TREE_TYPE (tem)) != ARRAY_TYPE
- || TREE_CODE (TREE_TYPE (TREE_TYPE (tem))) == ARRAY_TYPE
- || !TYPE_DOMAIN (TREE_TYPE (tem)))
- return;
+ if (TREE_CODE (t) != MEM_REF
+ || TREE_CODE (TREE_OPERAND (t, 0)) != ADDR_EXPR
+ || TREE_NO_WARNING (t))
+ return;
- low_bound = TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (tem)));
- up_bound = TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (tem)));
- el_sz = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (tem)));
- if (!low_bound
- || TREE_CODE (low_bound) != INTEGER_CST
- || !up_bound
- || TREE_CODE (up_bound) != INTEGER_CST
- || !el_sz
- || TREE_CODE (el_sz) != INTEGER_CST)
- return;
+ tree tem = TREE_OPERAND (TREE_OPERAND (t, 0), 0);
+ tree low_bound, up_bound, el_sz;
+ if (TREE_CODE (TREE_TYPE (tem)) != ARRAY_TYPE
+ || TREE_CODE (TREE_TYPE (TREE_TYPE (tem))) == ARRAY_TYPE
+ || !TYPE_DOMAIN (TREE_TYPE (tem)))
+ return;
+
+ low_bound = TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (tem)));
+ up_bound = TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (tem)));
+ el_sz = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (tem)));
+ if (!low_bound
+ || TREE_CODE (low_bound) != INTEGER_CST
+ || !up_bound
+ || TREE_CODE (up_bound) != INTEGER_CST
+ || !el_sz
+ || TREE_CODE (el_sz) != INTEGER_CST)
+ return;
+
+ offset_int idx;
+ if (!mem_ref_offset (t).is_constant (&idx))
+ return;
- idx = mem_ref_offset (t);
- idx = wi::sdiv_trunc (idx, wi::to_offset (el_sz));
- if (idx < 0)
+ bool warned = false;
+ idx = wi::sdiv_trunc (idx, wi::to_offset (el_sz));
+ if (idx < 0)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Array bound warning for ");
- dump_generic_expr (MSG_NOTE, TDF_SLIM, t);
- fprintf (dump_file, "\n");
- }
- warning_at (location, OPT_Warray_bounds,
- "array subscript %wi is below array bounds of %qT",
- idx.to_shwi (), TREE_TYPE (tem));
- TREE_NO_WARNING (t) = 1;
+ fprintf (dump_file, "Array bound warning for ");
+ dump_generic_expr (MSG_NOTE, TDF_SLIM, t);
+ fprintf (dump_file, "\n");
}
- else if (idx > (wi::to_offset (up_bound)
- - wi::to_offset (low_bound) + 1))
+ warned = warning_at (location, OPT_Warray_bounds,
+ "array subscript %wi is below "
+ "array bounds of %qT",
+ idx.to_shwi (), TREE_TYPE (tem));
+ }
+ else if (idx > (wi::to_offset (up_bound)
+ - wi::to_offset (low_bound) + 1))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Array bound warning for ");
- dump_generic_expr (MSG_NOTE, TDF_SLIM, t);
- fprintf (dump_file, "\n");
- }
- warning_at (location, OPT_Warray_bounds,
- "array subscript %wu is above array bounds of %qT",
- idx.to_uhwi (), TREE_TYPE (tem));
- TREE_NO_WARNING (t) = 1;
+ fprintf (dump_file, "Array bound warning for ");
+ dump_generic_expr (MSG_NOTE, TDF_SLIM, t);
+ fprintf (dump_file, "\n");
}
+ warned = warning_at (location, OPT_Warray_bounds,
+ "array subscript %wu is above "
+ "array bounds of %qT",
+ idx.to_uhwi (), TREE_TYPE (tem));
+ }
+
+ if (warned)
+ {
+ if (DECL_P (t))
+ inform (DECL_SOURCE_LOCATION (t), "while referencing %qD", t);
+
+ TREE_NO_WARNING (t) = 1;
}
}
else
location = gimple_location (wi->stmt);
- *walk_subtree = TRUE;
+ *walk_subtree = TRUE;
+
+ bool warned = false;
+ vrp_prop *vrp_prop = (class vrp_prop *)wi->info;
+ if (TREE_CODE (t) == ARRAY_REF)
+ warned = vrp_prop->check_array_ref (location, t, false/*ignore_off_by_one*/);
+ else if (TREE_CODE (t) == MEM_REF)
+ 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;
+}
+
+/* A dom_walker subclass for use by vrp_prop::check_all_array_refs,
+ to walk over all statements of all reachable BBs and call
+ check_array_bounds on them. */
+
+class check_array_bounds_dom_walker : public dom_walker
+{
+ public:
+ check_array_bounds_dom_walker (vrp_prop *prop)
+ : dom_walker (CDI_DOMINATORS,
+ /* Discover non-executable edges, preserving EDGE_EXECUTABLE
+ flags, so that we can merge in information on
+ non-executable edges from vrp_folder . */
+ REACHABLE_BLOCKS_PRESERVING_FLAGS),
+ m_prop (prop) {}
+ ~check_array_bounds_dom_walker () {}
+
+ edge before_dom_children (basic_block) FINAL OVERRIDE;
+
+ private:
+ vrp_prop *m_prop;
+};
+
+/* Implementation of dom_walker::before_dom_children.
- 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*/);
+ Walk over all statements of BB and call check_array_bounds on them,
+ and determine if there's a unique successor edge. */
- else if (TREE_CODE (t) == ADDR_EXPR)
+edge
+check_array_bounds_dom_walker::before_dom_children (basic_block bb)
+{
+ gimple_stmt_iterator si;
+ for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
{
- vrp_prop->search_for_addr_array (t, location);
- *walk_subtree = FALSE;
+ gimple *stmt = gsi_stmt (si);
+ struct walk_stmt_info wi;
+ if (!gimple_has_location (stmt)
+ || is_gimple_debug (stmt))
+ continue;
+
+ memset (&wi, 0, sizeof (wi));
+
+ wi.info = m_prop;
+
+ walk_gimple_op (stmt, check_array_bounds, &wi);
}
- return NULL_TREE;
+ /* Determine if there's a unique successor edge, and if so, return
+ that back to dom_walker, ensuring that we don't visit blocks that
+ became unreachable during the VRP propagation
+ (PR tree-optimization/83312). */
+ return find_taken_edge (bb, NULL_TREE);
}
/* Walk over all statements of all reachable BBs and call check_array_bounds
void
vrp_prop::check_all_array_refs ()
{
- basic_block bb;
- gimple_stmt_iterator si;
-
- FOR_EACH_BB_FN (bb, cfun)
- {
- edge_iterator ei;
- edge e;
- bool executable = false;
-
- /* Skip blocks that were found to be unreachable. */
- FOR_EACH_EDGE (e, ei, bb->preds)
- executable |= !!(e->flags & EDGE_EXECUTABLE);
- if (!executable)
- continue;
-
- for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
- {
- gimple *stmt = gsi_stmt (si);
- struct walk_stmt_info wi;
- if (!gimple_has_location (stmt)
- || is_gimple_debug (stmt))
- continue;
-
- memset (&wi, 0, sizeof (wi));
-
- wi.info = this;
-
- walk_gimple_op (gsi_stmt (si),
- check_array_bounds,
- &wi);
- }
- }
+ check_array_bounds_dom_walker w (this);
+ w.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
}
/* Return true if all imm uses of VAR are either in STMT, or
var is the x_3 var from ASSERT_EXPR, we can clear low 5 bits
from the non-zero bitmask. */
-static void
-maybe_set_nonzero_bits (basic_block bb, tree var)
+void
+maybe_set_nonzero_bits (edge e, tree var)
{
- edge e = single_pred_edge (bb);
basic_block cond_bb = e->src;
gimple *stmt = last_stmt (cond_bb);
tree cst;
set_range_info (var, SSA_NAME_RANGE_TYPE (lhs),
SSA_NAME_RANGE_INFO (lhs)->get_min (),
SSA_NAME_RANGE_INFO (lhs)->get_max ());
- maybe_set_nonzero_bits (bb, var);
+ maybe_set_nonzero_bits (single_pred_edge (bb), var);
}
}
}
}
-
/* Return true if STMT is interesting for VRP. */
bool
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
enum ssa_prop_result
vrp_prop::visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
{
- value_range vr = VR_INITIALIZER;
tree lhs = gimple_get_lhs (stmt);
+ value_range vr;
extract_range_from_stmt (stmt, taken_edge_p, output_p, &vr);
if (*output_p)
fprintf (dump_file, "\n");
}
- if (vr.type == VR_VARYING)
+ if (vr.varying_p ())
return SSA_PROP_VARYING;
return SSA_PROP_INTERESTING;
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)
{
SSA_PROP_NOT_INTERESTING. If there are no
{REAL,IMAG}PART_EXPR uses at all,
return SSA_PROP_VARYING. */
- value_range new_vr = VR_INITIALIZER;
+ value_range new_vr;
extract_range_basic (&new_vr, use_stmt);
- value_range *old_vr = get_value_range (use_lhs);
- if (old_vr->type != new_vr.type
- || !vrp_operand_equal_p (old_vr->min, new_vr.min)
- || !vrp_operand_equal_p (old_vr->max, new_vr.max)
- || !vrp_bitmap_equal_p (old_vr->equiv, new_vr.equiv))
+ const value_range *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;
- BITMAP_FREE (new_vr.equiv);
+ new_vr.equiv_clear ();
if (res == SSA_PROP_INTERESTING)
{
*output_p = lhs;
possible such range. The resulting range is not canonicalized. */
static void
-union_ranges (enum value_range_type *vr0type,
+union_ranges (enum value_range_kind *vr0type,
tree *vr0min, tree *vr0max,
- enum value_range_type vr1type,
+ 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);
+ int cmpmin = compare_values (*vr0min, vr1min);
+ int cmpmax = compare_values (*vr0max, vr1max);
+ bool mineq = cmpmin == 0;
+ bool maxeq = cmpmax == 0;
/* [] is vr0, () is vr1 in the following classification comments. */
if (mineq && maxeq)
else
gcc_unreachable ();
}
- else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1)
- && (mineq || operand_less_p (*vr0min, vr1min) == 1))
+ else if ((maxeq || cmpmax == 1)
+ && (mineq || cmpmin == -1))
{
/* [ ( ) ] or [( ) ] or [ ( )] */
if (*vr0type == VR_RANGE
else
gcc_unreachable ();
}
- else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
- && (mineq || operand_less_p (vr1min, *vr0min) == 1))
+ else if ((maxeq || cmpmax == -1)
+ && (mineq || cmpmin == 1))
{
/* ( [ ] ) or ([ ] ) or ( [ ]) */
if (*vr0type == VR_RANGE
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)
+ else if (cmpmin == -1
+ && cmpmax == -1
+ && (operand_less_p (vr1min, *vr0max) == 1
+ || operand_equal_p (vr1min, *vr0max, 0)))
{
/* [ ( ] ) or [ ]( ) */
if (*vr0type == VR_RANGE
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)
+ else if (cmpmin == 1
+ && cmpmax == 1
+ && (operand_less_p (*vr0min, vr1max) == 1
+ || operand_equal_p (*vr0min, vr1max, 0)))
{
/* ( [ ) ] or ( )[ ] */
if (*vr0type == VR_RANGE
if (TREE_CODE (*vr0min) == INTEGER_CST)
{
*vr0type = vr1type;
- *vr0min = vr1min;
*vr0max = int_const_binop (MINUS_EXPR, *vr0min,
build_int_cst (TREE_TYPE (*vr0min), 1));
+ *vr0min = vr1min;
}
else
goto give_up;
possible such range. The resulting range is not canonicalized. */
static void
-intersect_ranges (enum value_range_type *vr0type,
+intersect_ranges (enum value_range_kind *vr0type,
tree *vr0min, tree *vr0max,
- enum value_range_type vr1type,
+ enum value_range_kind vr1type,
tree vr1min, tree vr1max)
{
bool mineq = vrp_operand_equal_p (*vr0min, 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. */
+ 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 (ptr_type_node))
+ && ((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))
gcc_unreachable ();
}
+ /* If we know the intersection is empty, there's no need to
+ conservatively add anything else to the set. */
+ if (*vr0type == VR_UNDEFINED)
+ return;
+
/* 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
*vr0min = vr1min;
*vr0max = vr1max;
}
-
- return;
}
-/* Intersect the two value-ranges *VR0 and *VR1 and store the result
- in *VR0. This may not be the smallest possible such range. */
+/* Helper for the intersection operation for value ranges. Given two
+ value ranges VR0 and VR1, return the intersection of the two
+ ranges. This may not be the smallest possible such range. */
-static void
-vrp_intersect_ranges_1 (value_range *vr0, value_range *vr1)
+value_range_base
+value_range_base::intersect_helper (const value_range_base *vr0,
+ const value_range_base *vr1)
{
- value_range saved;
-
/* If either range is VR_VARYING the other one wins. */
- if (vr1->type == VR_VARYING)
- return;
- if (vr0->type == VR_VARYING)
- {
- copy_value_range (vr0, vr1);
- return;
- }
+ if (vr1->varying_p ())
+ return *vr0;
+ if (vr0->varying_p ())
+ return *vr1;
/* When either range is VR_UNDEFINED the resulting range is
VR_UNDEFINED, too. */
- if (vr0->type == VR_UNDEFINED)
- return;
- if (vr1->type == VR_UNDEFINED)
- {
- 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. */
- saved = *vr0;
- intersect_ranges (&vr0->type, &vr0->min, &vr0->max,
- vr1->type, vr1->min, vr1->max);
+ if (vr0->undefined_p ())
+ return *vr0;
+ if (vr1->undefined_p ())
+ return *vr1;
+
+ 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. */
- set_and_canonicalize_value_range (vr0, vr0->type,
- vr0->min, vr0->max, vr0->equiv);
+ VR_RANGE can still be a VR_RANGE. Work on a temporary so we can
+ fall back to vr0 when this turns things to varying. */
+ value_range_base tem;
+ if (vr0type == VR_UNDEFINED)
+ tem.set_undefined ();
+ else if (vr0type == VR_VARYING)
+ tem.set_varying (vr0->type ());
+ else
+ tem.set (vr0type, vr0min, vr0max);
/* If that failed, use the saved original VR0. */
- if (vr0->type == VR_VARYING)
+ if (tem.varying_p ())
+ return *vr0;
+
+ return tem;
+}
+
+void
+value_range_base::intersect (const value_range_base *other)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- *vr0 = saved;
- return;
+ fprintf (dump_file, "Intersecting\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\nand\n ");
+ dump_value_range (dump_file, other);
+ fprintf (dump_file, "\n");
}
- /* If the result is VR_UNDEFINED there is no need to mess with
- the equivalencies. */
- if (vr0->type == VR_UNDEFINED)
- return;
- /* The resulting set of equivalences for range intersection is the union of
- the two sets. */
- if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
- bitmap_ior_into (vr0->equiv, vr1->equiv);
- else if (vr1->equiv && !vr0->equiv)
+ *this = intersect_helper (this, other);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- /* All equivalence bitmaps are allocated from the same obstack. So
- we can use the obstack associated with VR to allocate vr0->equiv. */
- vr0->equiv = BITMAP_ALLOC (vr1->equiv->obstack);
- bitmap_copy (vr0->equiv, vr1->equiv);
+ fprintf (dump_file, "to\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\n");
}
}
void
-vrp_intersect_ranges (value_range *vr0, value_range *vr1)
+value_range::intersect (const value_range *other)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Intersecting\n ");
- dump_value_range (dump_file, vr0);
+ dump_value_range (dump_file, this);
fprintf (dump_file, "\nand\n ");
- dump_value_range (dump_file, vr1);
+ dump_value_range (dump_file, other);
fprintf (dump_file, "\n");
}
- vrp_intersect_ranges_1 (vr0, vr1);
+
+ /* 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_base tem = intersect_helper (this, other);
+ this->update (tem.kind (), tem.min (), tem.max ());
+
+ /* 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 ");
- dump_value_range (dump_file, vr0);
+ dump_value_range (dump_file, this);
fprintf (dump_file, "\n");
}
}
+/* Helper for meet operation for value ranges. Given two value ranges VR0 and
+ VR1, return a range that contains both VR0 and VR1. This may not be the
+ smallest possible such range. */
+
+value_range_base
+value_range_base::union_helper (const value_range_base *vr0,
+ const value_range_base *vr1)
+{
+ /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
+ if (vr1->undefined_p ()
+ || vr0->varying_p ())
+ return *vr0;
+
+ /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
+ if (vr0->undefined_p ()
+ || vr1->varying_p ())
+ return *vr1;
+
+ 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 ());
+
+ /* Work on a temporary so we can still use vr0 when union returns varying. */
+ value_range_base tem;
+ if (vr0type == VR_UNDEFINED)
+ tem.set_undefined ();
+ else if (vr0type == VR_VARYING)
+ tem.set_varying (vr0->type ());
+ else
+ tem.set (vr0type, vr0min, vr0max);
+
+ /* 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 (tem.varying_p ()
+ && range_includes_zero_p (vr0) == 0
+ && range_includes_zero_p (vr1) == 0)
+ {
+ tem.set_nonzero (vr0->type ());
+ return tem;
+ }
+
+ return tem;
+}
+
+
/* 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. */
-static void
-vrp_meet_1 (value_range *vr0, const value_range *vr1)
+void
+value_range_base::union_ (const value_range_base *other)
{
- value_range saved;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Meeting\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\nand\n ");
+ dump_value_range (dump_file, other);
+ fprintf (dump_file, "\n");
+ }
+
+ *this = union_helper (this, other);
- if (vr0->type == VR_UNDEFINED)
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr1->equiv);
- return;
+ fprintf (dump_file, "to\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\n");
}
+}
- if (vr1->type == VR_UNDEFINED)
+void
+value_range::union_ (const value_range *other)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- /* VR0 already has the resulting range. */
- return;
+ fprintf (dump_file, "Meeting\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\nand\n ");
+ dump_value_range (dump_file, other);
+ fprintf (dump_file, "\n");
}
- if (vr0->type == VR_VARYING)
+ /* 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
{
- /* Nothing to do. VR0 already has the resulting range. */
- return;
+ value_range_base tem = union_helper (this, other);
+ this->update (tem.kind (), tem.min (), tem.max ());
+
+ /* 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 (vr1->type == VR_VARYING)
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- set_value_range_to_varying (vr0);
- return;
+ fprintf (dump_file, "to\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\n");
+ }
+}
+
+/* Normalize addresses into constants. */
+
+value_range_base
+value_range_base::normalize_addresses () const
+{
+ if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
+ return *this;
+
+ if (!range_includes_zero_p (this))
+ {
+ gcc_checking_assert (TREE_CODE (m_min) == ADDR_EXPR
+ || TREE_CODE (m_max) == ADDR_EXPR);
+ return range_nonzero (type ());
}
+ return value_range_base (type ());
+}
- saved = *vr0;
- union_ranges (&vr0->type, &vr0->min, &vr0->max,
- vr1->type, vr1->min, vr1->max);
- if (vr0->type == VR_VARYING)
- {
- /* 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. FIXME, all this nonsense about distinguishing
- anti-ranges from ranges is necessary because of the odd
- semantics of range_includes_zero_p and friends. */
- if (((saved.type == VR_RANGE
- && range_includes_zero_p (saved.min, saved.max) == 0)
- || (saved.type == VR_ANTI_RANGE
- && range_includes_zero_p (saved.min, saved.max) == 1))
- && ((vr1->type == VR_RANGE
- && range_includes_zero_p (vr1->min, vr1->max) == 0)
- || (vr1->type == VR_ANTI_RANGE
- && range_includes_zero_p (vr1->min, vr1->max) == 1)))
- {
- set_value_range_to_nonnull (vr0, TREE_TYPE (saved.min));
+/* Normalize symbolics and addresses into constants. */
- /* Since this meet operation did not result from the meeting of
- two equivalent names, VR0 cannot have any equivalences. */
- if (vr0->equiv)
- bitmap_clear (vr0->equiv);
- return;
- }
+value_range_base
+value_range_base::normalize_symbolics () const
+{
+ if (varying_p () || undefined_p ())
+ return *this;
+ tree ttype = type ();
+ bool min_symbolic = !is_gimple_min_invariant (min ());
+ bool max_symbolic = !is_gimple_min_invariant (max ());
+ if (!min_symbolic && !max_symbolic)
+ return normalize_addresses ();
- set_value_range_to_varying (vr0);
- return;
+ // [SYM, SYM] -> VARYING
+ if (min_symbolic && max_symbolic)
+ {
+ value_range_base var;
+ var.set_varying (ttype);
+ return var;
}
- set_and_canonicalize_value_range (vr0, vr0->type, vr0->min, vr0->max,
- vr0->equiv);
- if (vr0->type == VR_VARYING)
- return;
+ if (kind () == VR_RANGE)
+ {
+ // [SYM, NUM] -> [-MIN, NUM]
+ if (min_symbolic)
+ return value_range_base (VR_RANGE, vrp_val_min (ttype, true), max ());
+ // [NUM, SYM] -> [NUM, +MAX]
+ return value_range_base (VR_RANGE, min (), vrp_val_max (ttype, true));
+ }
+ gcc_checking_assert (kind () == VR_ANTI_RANGE);
+ // ~[SYM, NUM] -> [NUM + 1, +MAX]
+ if (min_symbolic)
+ {
+ if (!vrp_val_is_max (max ()))
+ {
+ tree n = wide_int_to_tree (ttype, wi::to_wide (max ()) + 1);
+ return value_range_base (VR_RANGE, n, vrp_val_max (ttype, true));
+ }
+ value_range_base var;
+ var.set_varying (ttype);
+ return var;
+ }
+ // ~[NUM, SYM] -> [-MIN, NUM - 1]
+ if (!vrp_val_is_min (min ()))
+ {
+ tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1);
+ return value_range_base (VR_RANGE, vrp_val_min (ttype, true), n);
+ }
+ value_range_base var;
+ var.set_varying (ttype);
+ return var;
+}
+
+/* Return the number of sub-ranges in a range. */
- /* The resulting set of equivalences is always the intersection of
- the two sets. */
- if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
- bitmap_and_into (vr0->equiv, vr1->equiv);
- else if (vr0->equiv && !vr1->equiv)
- bitmap_clear (vr0->equiv);
+unsigned
+value_range_base::num_pairs () const
+{
+ if (undefined_p ())
+ return 0;
+ if (varying_p ())
+ return 1;
+ if (symbolic_p ())
+ return normalize_symbolics ().num_pairs ();
+ if (m_kind == VR_ANTI_RANGE)
+ {
+ // ~[MIN, X] has one sub-range of [X+1, MAX], and
+ // ~[X, MAX] has one sub-range of [MIN, X-1].
+ if (vrp_val_is_min (m_min, true) || vrp_val_is_max (m_max, true))
+ return 1;
+ return 2;
+ }
+ return 1;
}
-void
-vrp_meet (value_range *vr0, const value_range *vr1)
+/* Return the lower bound for a sub-range. PAIR is the sub-range in
+ question. */
+
+wide_int
+value_range_base::lower_bound (unsigned pair) const
{
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (symbolic_p ())
+ return normalize_symbolics ().lower_bound (pair);
+
+ gcc_checking_assert (!undefined_p ());
+ gcc_checking_assert (pair + 1 <= num_pairs ());
+ tree t = NULL;
+ if (m_kind == VR_ANTI_RANGE)
{
- fprintf (dump_file, "Meeting\n ");
- dump_value_range (dump_file, vr0);
- fprintf (dump_file, "\nand\n ");
- dump_value_range (dump_file, vr1);
- fprintf (dump_file, "\n");
+ tree typ = type ();
+ if (pair == 1 || vrp_val_is_min (m_min, true))
+ t = wide_int_to_tree (typ, wi::to_wide (m_max) + 1);
+ else
+ t = vrp_val_min (typ, true);
}
- vrp_meet_1 (vr0, vr1);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ else
+ t = m_min;
+ return wi::to_wide (t);
+}
+
+/* Return the upper bound for a sub-range. PAIR is the sub-range in
+ question. */
+
+wide_int
+value_range_base::upper_bound (unsigned pair) const
+{
+ if (symbolic_p ())
+ return normalize_symbolics ().upper_bound (pair);
+
+ gcc_checking_assert (!undefined_p ());
+ gcc_checking_assert (pair + 1 <= num_pairs ());
+ tree t = NULL;
+ if (m_kind == VR_ANTI_RANGE)
{
- fprintf (dump_file, "to\n ");
- dump_value_range (dump_file, vr0);
- fprintf (dump_file, "\n");
+ tree typ = type ();
+ if (pair == 1 || vrp_val_is_min (m_min, true))
+ t = vrp_val_max (typ, true);
+ else
+ t = wide_int_to_tree (typ, wi::to_wide (m_min) - 1);
}
+ else
+ t = m_max;
+ return wi::to_wide (t);
+}
+
+/* Return the highest bound in a range. */
+
+wide_int
+value_range_base::upper_bound () const
+{
+ unsigned pairs = num_pairs ();
+ gcc_checking_assert (pairs > 0);
+ return upper_bound (pairs - 1);
+}
+
+/* Return TRUE if range contains INTEGER_CST. */
+
+bool
+value_range_base::contains_p (tree cst) const
+{
+ gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST);
+ if (symbolic_p ())
+ return normalize_symbolics ().contains_p (cst);
+ return value_inside_range (cst) == 1;
+}
+
+/* Return the inverse of a range. */
+
+void
+value_range_base::invert ()
+{
+ if (m_kind == VR_RANGE)
+ m_kind = VR_ANTI_RANGE;
+ else if (m_kind == VR_ANTI_RANGE)
+ m_kind = VR_RANGE;
+ else
+ gcc_unreachable ();
+}
+
+/* Range union, but for references. */
+
+void
+value_range_base::union_ (const value_range_base &r)
+{
+ /* Disable details for now, because it makes the ranger dump
+ unnecessarily verbose. */
+ bool details = dump_flags & TDF_DETAILS;
+ if (details)
+ dump_flags &= ~TDF_DETAILS;
+ union_ (&r);
+ if (details)
+ dump_flags |= TDF_DETAILS;
+}
+
+/* Range intersect, but for references. */
+
+void
+value_range_base::intersect (const value_range_base &r)
+{
+ /* Disable details for now, because it makes the ranger dump
+ unnecessarily verbose. */
+ bool details = dump_flags & TDF_DETAILS;
+ if (details)
+ dump_flags &= ~TDF_DETAILS;
+ intersect (&r);
+ if (details)
+ dump_flags |= TDF_DETAILS;
+}
+
+/* Return TRUE if two types are compatible for range operations. */
+
+static bool
+range_compatible_p (tree t1, tree t2)
+{
+ if (POINTER_TYPE_P (t1) && POINTER_TYPE_P (t2))
+ return true;
+
+ return types_compatible_p (t1, t2);
}
+bool
+value_range_base::operator== (const value_range_base &r) const
+{
+ if (undefined_p ())
+ return r.undefined_p ();
+
+ if (num_pairs () != r.num_pairs ()
+ || !range_compatible_p (type (), r.type ()))
+ return false;
+
+ for (unsigned p = 0; p < num_pairs (); p++)
+ if (wi::ne_p (lower_bound (p), r.lower_bound (p))
+ || wi::ne_p (upper_bound (p), r.upper_bound (p)))
+ return false;
+
+ return true;
+}
/* Visit all arguments for PHI node PHI that flow through executable
edges. If a valid value range can be derived from all the incoming
vrp_prop::visit_phi (gphi *phi)
{
tree lhs = PHI_RESULT (phi);
- value_range vr_result = VR_INITIALIZER;
+ value_range vr_result;
extract_range_from_phi_node (phi, &vr_result);
if (update_value_range (lhs, &vr_result))
{
fprintf (dump_file, "\n");
}
- if (vr_result.type == VR_VARYING)
+ if (vr_result.varying_p ())
return SSA_PROP_VARYING;
return SSA_PROP_INTERESTING;
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 *);
op = lhs_of_dominating_assert (op, bb, stmt);
- value_range *vr = vr_values->get_value_range (op);
- if ((vr->type != VR_RANGE && vr->type != VR_ANTI_RANGE)
- || symbolic_range_p (vr))
+ const value_range *vr = vr_values->get_value_range (op);
+ if (vr->undefined_p ()
+ || vr->varying_p ()
+ || vr->symbolic_p ())
return NULL_TREE;
- if (vr->type == VR_RANGE)
+ if (vr->kind () == VR_RANGE)
{
size_t i, j;
/* Get the range of labels that contain a part of the operand's
value range. */
- find_case_label_range (switch_stmt, vr->min, vr->max, &i, &j);
+ find_case_label_range (switch_stmt, vr->min (), vr->max (), &i, &j);
/* Is there only one such label? */
if (i == j)
/* The i'th label will be taken only if the value range of the
operand is entirely within the bounds of this label. */
if (CASE_HIGH (label) != NULL_TREE
- ? (tree_int_cst_compare (CASE_LOW (label), vr->min) <= 0
- && tree_int_cst_compare (CASE_HIGH (label), vr->max) >= 0)
- : (tree_int_cst_equal (CASE_LOW (label), vr->min)
- && tree_int_cst_equal (vr->min, vr->max)))
+ ? (tree_int_cst_compare (CASE_LOW (label), vr->min ()) <= 0
+ && tree_int_cst_compare (CASE_HIGH (label),
+ vr->max ()) >= 0)
+ : (tree_int_cst_equal (CASE_LOW (label), vr->min ())
+ && tree_int_cst_equal (vr->min (), vr->max ())))
return label;
}
return gimple_switch_label (switch_stmt, 0);
}
- if (vr->type == VR_ANTI_RANGE)
+ if (vr->kind () == VR_ANTI_RANGE)
{
unsigned n = gimple_switch_num_labels (switch_stmt);
tree min_label = gimple_switch_label (switch_stmt, 1);
/* The default label will be taken only if the anti-range of the
operand is entirely outside the bounds of all the (non-default)
case labels. */
- if (tree_int_cst_compare (vr->min, CASE_LOW (min_label)) <= 0
+ if (tree_int_cst_compare (vr->min (), CASE_LOW (min_label)) <= 0
&& (CASE_HIGH (max_label) != NULL_TREE
- ? tree_int_cst_compare (vr->max, CASE_HIGH (max_label)) >= 0
- : tree_int_cst_compare (vr->max, CASE_LOW (max_label)) >= 0))
+ ? tree_int_cst_compare (vr->max (),
+ CASE_HIGH (max_label)) >= 0
+ : tree_int_cst_compare (vr->max (),
+ CASE_LOW (max_label)) >= 0))
return gimple_switch_label (switch_stmt, 0);
}
if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
{
- value_range new_vr = VR_INITIALIZER;
tree lhs = gimple_assign_lhs (assign_stmt);
-
if (TREE_CODE (lhs) == SSA_NAME
&& (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
- || POINTER_TYPE_P (TREE_TYPE (lhs))))
+ || POINTER_TYPE_P (TREE_TYPE (lhs)))
+ && stmt_interesting_for_vrp (stmt))
{
- vr_values->extract_range_from_assignment (&new_vr, assign_stmt);
- if (range_int_cst_singleton_p (&new_vr))
- return new_vr.min;
+ edge dummy_e;
+ tree dummy_tree;
+ value_range new_vr;
+ vr_values->extract_range_from_stmt (stmt, &dummy_e,
+ &dummy_tree, &new_vr);
+ tree singleton;
+ if (new_vr.singleton_p (&singleton))
+ return singleton;
}
}
vrp_dom_walker (cdi_direction direction,
class const_and_copies *const_and_copies,
class avail_exprs_stack *avail_exprs_stack)
- : dom_walker (direction, true),
+ : dom_walker (direction, REACHABLE_BLOCKS),
m_const_and_copies (const_and_copies),
m_avail_exprs_stack (avail_exprs_stack),
m_dummy_cond (NULL) {}
x_vr_values = vr_values;
thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies,
- m_avail_exprs_stack,
+ m_avail_exprs_stack, NULL,
simplify_stmt_for_jump_threading);
x_vr_values = NULL;
static void
identify_jump_threads (class vr_values *vr_values)
{
- int i;
- edge e;
-
/* Ugh. When substituting values earlier in this pass we can
wipe the dominance information. So rebuild the dominator
information as we need it within the jump threading code. */
recompute it. */
mark_dfs_back_edges ();
- /* Do not thread across edges we are about to remove. Just marking
- them as EDGE_IGNORE will do. */
- FOR_EACH_VEC_ELT (to_remove_edges, i, e)
- e->flags |= EDGE_IGNORE;
-
/* Allocate our unwinder stack to unwind any temporary equivalences
that might be recorded. */
const_and_copies *equiv_stack = new const_and_copies ();
walker.vr_values = vr_values;
walker.walk (cfun->cfg->x_entry_block_ptr);
- /* Clear EDGE_IGNORE. */
- FOR_EACH_VEC_ELT (to_remove_edges, i, e)
- e->flags &= ~EDGE_IGNORE;
-
/* We do not actually update the CFG or SSA graphs at this point as
ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet
handle ASSERT_EXPRs gracefully. */
{
size_t i;
- vr_values.values_propagated = true;
+ /* We have completed propagating through the lattice. */
+ vr_values.set_lattice_propagation_complete ();
if (dump_file)
{
if (!name)
continue;
- value_range *vr = get_value_range (name);
- if (!name
- || (vr->type == VR_VARYING)
- || (vr->type == VR_UNDEFINED)
- || (TREE_CODE (vr->min) != INTEGER_CST)
- || (TREE_CODE (vr->max) != INTEGER_CST))
+ const value_range *vr = get_value_range (name);
+ if (!name || !vr->constant_p ())
continue;
if (POINTER_TYPE_P (TREE_TYPE (name))
- && ((vr->type == VR_RANGE
- && range_includes_zero_p (vr->min, vr->max) == 0)
- || (vr->type == VR_ANTI_RANGE
- && range_includes_zero_p (vr->min, vr->max) == 1)))
+ && range_includes_zero_p (vr) == 0)
set_ptr_nonnull (name);
else if (!POINTER_TYPE_P (TREE_TYPE (name)))
- set_range_info (name, vr->type,
- 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
+ the executability of each edge between vrp_folder and the
+ check_array_bounds_dom_walker: each can clear the
+ EDGE_EXECUTABLE flag on edges, in different ways.
+
+ Hence, if we're going to call check_all_array_refs, set
+ the flag on every edge now, rather than in
+ check_array_bounds_dom_walker's ctor; vrp_folder may clear
+ it from some edges. */
+ if (warn_array_bounds && warn_array_bounds_p)
+ set_all_edges_as_executable (cfun);
+
class vrp_folder vrp_folder;
vrp_folder.vr_values = &vr_values;
vrp_folder.substitute_and_fold ();
static unsigned int
execute_vrp (bool warn_array_bounds_p)
{
- int i;
- edge e;
- switch_update *su;
loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
EDGE_DFS_BACK. */
insert_range_assertions ();
- to_remove_edges.create (10);
- to_update_switch_stmts.create (5);
threadedge_initialize_values ();
/* For visiting PHI nodes we need EDGE_DFS_BACK computed. */
processing by the pass manager. */
thread_through_all_blocks (false);
- /* Remove dead edges from SWITCH_EXPR optimization. This leaves the
- CFG in a broken state and requires a cfg_cleanup run. */
- FOR_EACH_VEC_ELT (to_remove_edges, i, e)
- remove_edge (e);
- /* Update SWITCH_EXPR case label vector. */
- FOR_EACH_VEC_ELT (to_update_switch_stmts, i, su)
- {
- size_t j;
- size_t n = TREE_VEC_LENGTH (su->vec);
- tree label;
- gimple_switch_set_num_labels (su->stmt, n);
- for (j = 0; j < n; j++)
- gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j));
- /* As we may have replaced the default label with a regular one
- make sure to make it a real default label again. This ensures
- optimal expansion. */
- label = gimple_switch_label (su->stmt, 0);
- CASE_LOW (label) = NULL_TREE;
- CASE_HIGH (label) = NULL_TREE;
- }
-
- if (to_remove_edges.length () > 0)
- {
- free_dominance_info (CDI_DOMINATORS);
- loops_state_set (LOOPS_NEED_FIXUP);
- }
-
- to_remove_edges.release ();
- to_update_switch_stmts.release ();
+ vrp_prop.vr_values.cleanup_edges_and_switches ();
threadedge_finalize_values ();
scev_finalize ();
{
return new pass_vrp (ctxt);
}
+
+
+/* Worker for determine_value_range. */
+
+static void
+determine_value_range_1 (value_range_base *vr, tree expr)
+{
+ if (BINARY_CLASS_P (expr))
+ {
+ value_range_base vr0, vr1;
+ determine_value_range_1 (&vr0, TREE_OPERAND (expr, 0));
+ determine_value_range_1 (&vr1, TREE_OPERAND (expr, 1));
+ range_fold_binary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr),
+ &vr0, &vr1);
+ }
+ else if (UNARY_CLASS_P (expr))
+ {
+ value_range_base vr0;
+ determine_value_range_1 (&vr0, 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)
+ vr->set (expr);
+ else
+ {
+ value_range_kind kind;
+ wide_int min, max;
+ /* For SSA names try to extract range info computed by VRP. Otherwise
+ fall back to varying. */
+ if (TREE_CODE (expr) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (expr))
+ && (kind = get_range_info (expr, &min, &max)) != VR_VARYING)
+ vr->set (kind, wide_int_to_tree (TREE_TYPE (expr), min),
+ wide_int_to_tree (TREE_TYPE (expr), max));
+ else
+ vr->set_varying (TREE_TYPE (expr));
+ }
+}
+
+/* Compute a value-range for EXPR and set it in *MIN and *MAX. Return
+ the determined range type. */
+
+value_range_kind
+determine_value_range (tree expr, wide_int *min, wide_int *max)
+{
+ value_range_base vr;
+ determine_value_range_1 (&vr, expr);
+ if (vr.constant_p ())
+ {
+ *min = wi::to_wide (vr.min ());
+ *max = wi::to_wide (vr.max ());
+ return vr.kind ();
+ }
+
+ return VR_VARYING;
+}
projects / platform / upstream / gcc.git / blobdiff