/* Support routines for Value Range Propagation (VRP).
- Copyright (C) 2005-2018 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 "wide-int-range.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;
+void
+value_range::set_equiv (bitmap equiv)
+{
+ if (undefined_p () || varying_p ())
+ equiv = NULL;
+ /* Since updating the equivalence set involves deep copying the
+ bitmaps, only do it if absolutely necessary.
+
+ 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);
+
+ if (equiv != m_equiv)
+ {
+ if (equiv && !bitmap_empty_p (equiv))
+ bitmap_copy (m_equiv, equiv);
+ else
+ bitmap_clear (m_equiv);
+ }
+}
+
+/* Initialize value_range. */
+
+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 ();
+}
+
+value_range_base::value_range_base (value_range_kind kind, tree min, tree max)
+{
+ set (kind, min, max);
+}
+
+value_range::value_range (value_range_kind kind, tree min, tree max,
+ bitmap equiv)
+{
+ m_equiv = NULL;
+ set (kind, min, max, equiv);
+}
+
+value_range::value_range (const value_range_base &other)
+{
+ m_equiv = NULL;
+ set (other.kind (), other.min(), other.max (), NULL);
+}
+
+value_range_base::value_range_base (tree type)
+{
+ set_varying (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);
+}
+
+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);
+}
+
+value_range_base::value_range_base (tree min, tree max)
+{
+ set (VR_RANGE, min, max);
+}
+
+/* Like set, but keep the equivalences in place. */
+
+void
+value_range::update (value_range_kind kind, tree min, tree max)
+{
+ set (kind, min, max,
+ (kind != VR_UNDEFINED && kind != VR_VARYING) ? m_equiv : NULL);
+}
+
+/* Copy value_range in FROM into THIS while avoiding bitmap sharing.
+
+ 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. */
+
+void
+value_range::deep_copy (const value_range *from)
+{
+ set (from->m_kind, from->min (), from->max (), from->m_equiv);
+}
+
+void
+value_range::move (value_range *from)
+{
+ set (from->m_kind, from->min (), from->max ());
+ m_equiv = from->m_equiv;
+ from->m_equiv = NULL;
+}
+
+/* Check the validity of the range. */
+
+void
+value_range_base::check ()
+{
+ switch (m_kind)
+ {
+ case VR_RANGE:
+ case VR_ANTI_RANGE:
+ {
+ int cmp;
+
+ gcc_assert (m_min && m_max);
+
+ gcc_assert (!TREE_OVERFLOW_P (m_min) && !TREE_OVERFLOW_P (m_max));
+
+ /* Creating ~[-MIN, +MAX] is stupid because that would be
+ the empty set. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (m_min)) && m_kind == VR_ANTI_RANGE)
+ gcc_assert (!vrp_val_is_min (m_min) || !vrp_val_is_max (m_max));
+
+ cmp = compare_values (m_min, m_max);
+ gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
+ break;
+ }
+ case VR_UNDEFINED:
+ gcc_assert (!min () && !max ());
+ break;
+ case VR_VARYING:
+ gcc_assert (m_min && m_max);
+ break;
+ default:
+ gcc_unreachable ();
+ }
+}
+
+void
+value_range::check ()
+{
+ value_range_base::check ();
+ switch (m_kind)
+ {
+ case VR_UNDEFINED:
+ case VR_VARYING:
+ gcc_assert (!m_equiv || bitmap_empty_p (m_equiv));
+ default:;
+ }
+}
+
+/* Equality operator. We purposely do not overload ==, to avoid
+ confusion with the equality bitmap in the derived value_range
+ class. */
+
+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;
+
+ return (m_kind == other.m_kind
+ && vrp_operand_equal_p (m_min, other.m_min)
+ && vrp_operand_equal_p (m_max, other.m_max));
+}
+
+/* Returns TRUE if THIS == OTHER. Ignores the equivalence bitmap if
+ IGNORE_EQUIVS is TRUE. */
+
+bool
+value_range::equal_p (const value_range &other, bool ignore_equivs) const
+{
+ return (value_range_base::equal_p (other)
+ && (ignore_equivs
+ || vrp_bitmap_equal_p (m_equiv, other.m_equiv)));
+}
+
+/* Return TRUE if this is a symbolic range. */
+
+bool
+value_range_base::symbolic_p () const
+{
+ return (!varying_p ()
+ && !undefined_p ()
+ && (!is_gimple_min_invariant (m_min)
+ || !is_gimple_min_invariant (m_max)));
+}
+
+/* NOTE: This is not the inverse of symbolic_p because the range
+ could also be varying or undefined. Ideally they should be inverse
+ of each other, with varying only applying to symbolics. Varying of
+ constants would be represented as [-MIN, +MAX]. */
+
+bool
+value_range_base::constant_p () const
+{
+ return (!varying_p ()
+ && !undefined_p ()
+ && TREE_CODE (m_min) == INTEGER_CST
+ && TREE_CODE (m_max) == INTEGER_CST);
+}
+
+void
+value_range_base::set_undefined ()
+{
+ m_kind = VR_UNDEFINED;
+ m_min = m_max = NULL;
+}
+
+void
+value_range::set_undefined ()
+{
+ set (VR_UNDEFINED, NULL, NULL, NULL);
+}
+
+void
+value_range_base::set_varying (tree type)
+{
+ m_kind = VR_VARYING;
+ if (supports_type_p (type))
+ {
+ m_min = vrp_val_min (type, true);
+ m_max = vrp_val_max (type, true);
+ }
+ else
+ /* We can't do anything range-wise with these types. */
+ m_min = m_max = error_mark_node;
+}
+
+void
+value_range::set_varying (tree type)
+{
+ value_range_base::set_varying (type);
+ equiv_clear ();
+}
+
+/* Return TRUE if it is possible that range contains VAL. */
+
+bool
+value_range_base::may_contain_p (tree val) const
+{
+ return value_inside_range (val) != 0;
+}
+
+void
+value_range::equiv_clear ()
+{
+ 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).
+
+ This is the central point where equivalence processing can be
+ turned on/off. */
+
+void
+value_range::equiv_add (const_tree var,
+ const value_range *var_vr,
+ bitmap_obstack *obstack)
+{
+ 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);
+}
+
+/* If range is a singleton, place it in RESULT and return TRUE.
+ Note: A singleton can be any gimple invariant, not just constants.
+ So, [&x, &x] counts as a singleton. */
+
+bool
+value_range_base::singleton_p (tree *result) const
+{
+ 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
ASSERT_EXPRs for SSA name N_I should be inserted. */
static assert_locus **asserts_for;
-vec<edge> to_remove_edges;
-vec<switch_update> to_update_switch_stmts;
-
-
/* Return the maximum value for TYPE. */
tree
-vrp_val_max (const_tree type)
+vrp_val_max (const_tree type, bool handle_pointers)
{
- if (!INTEGRAL_TYPE_P (type))
- return NULL_TREE;
-
- return TYPE_MAX_VALUE (type);
+ 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)
+vrp_val_min (const_tree type, bool handle_pointers)
{
- if (!INTEGRAL_TYPE_P (type))
- return NULL_TREE;
-
- return TYPE_MIN_VALUE (type);
+ 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.
is not == to the integer constant with the same value in the type. */
bool
-vrp_val_is_max (const_tree val)
+vrp_val_is_max (const_tree val, bool handle_pointers)
{
- tree type_max = vrp_val_max (TREE_TYPE (val));
+ 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)
+vrp_val_is_min (const_tree val, bool handle_pointers)
{
- tree type_min = vrp_val_min (TREE_TYPE (val));
+ 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)));
SGN gives the sign of the values described by the range. */
-enum value_range_type
-intersect_range_with_nonzero_bits (enum value_range_type vr_type,
+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)
return vr_type;
}
-/* Set value range VR to VR_UNDEFINED. */
-
-static inline void
-set_value_range_to_undefined (value_range *vr)
-{
- vr->type = VR_UNDEFINED;
- vr->min = vr->max = NULL_TREE;
- if (vr->equiv)
- bitmap_clear (vr->equiv);
-}
-
-/* Set value range VR to VR_VARYING. */
-
-void
-set_value_range_to_varying (value_range *vr)
-{
- vr->type = VR_VARYING;
- vr->min = vr->max = NULL_TREE;
- if (vr->equiv)
- bitmap_clear (vr->equiv);
-}
-
-/* Set value range VR to {T, MIN, MAX, EQUIV}. */
-
-void
-set_value_range (value_range *vr, enum value_range_type t, tree min,
- tree max, bitmap equiv)
-{
- /* 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))
- {
- gcc_assert (min == NULL_TREE && max == NULL_TREE);
- gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
- }
-
- vr->type = t;
- vr->min = min;
- vr->max = max;
-
- /* Since updating the equivalence set involves deep copying the
- bitmaps, only do it if absolutely necessary.
-
- 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);
-
- if (equiv != vr->equiv)
- {
- if (equiv && !bitmap_empty_p (equiv))
- bitmap_copy (vr->equiv, equiv);
- else
- bitmap_clear (vr->equiv);
- }
-}
-
-
-/* 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
+/* 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
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_base::set (enum value_range_kind kind, tree min, tree max)
{
/* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */
- if (t == VR_UNDEFINED)
+ if (kind == VR_UNDEFINED)
{
- set_value_range_to_undefined (vr);
+ set_undefined ();
return;
}
- else if (t == VR_VARYING)
+ else if (kind == VR_VARYING)
{
- set_value_range_to_varying (vr);
+ 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)
{
- set_value_range (vr, t, min, max, equiv);
+ m_kind = kind;
+ m_min = min;
+ m_max = max;
return;
}
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);
+ set_varying (TREE_TYPE (min));
return;
}
to varying in this case. */
if (tree_int_cst_lt (max, min))
{
- set_value_range_to_varying (vr);
+ set_varying (TREE_TYPE (min));
return;
}
- t = t == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
+ 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 (t == VR_ANTI_RANGE)
+ if (kind == VR_ANTI_RANGE)
{
/* For -fstrict-enums we may receive out-of-range ranges so consider
values < -INF and values > INF as -INF/INF as well. */
- tree type = TREE_TYPE (min);
bool is_min = (INTEGRAL_TYPE_P (type)
&& tree_int_cst_compare (min, TYPE_MIN_VALUE (type)) <= 0);
bool is_max = (INTEGRAL_TYPE_P (type)
{
/* We cannot deal with empty ranges, drop to varying.
??? This could be VR_UNDEFINED instead. */
- set_value_range_to_varying (vr);
+ set_varying (type);
return;
}
else if (TYPE_PRECISION (TREE_TYPE (min)) == 1
min = max = vrp_val_max (TREE_TYPE (min));
else
min = max = vrp_val_min (TREE_TYPE (min));
- t = VR_RANGE;
+ kind = VR_RANGE;
}
else if (is_min
- /* As a special exception preserve non-null ranges. */
- && !(TYPE_UNSIGNED (TREE_TYPE (min))
- && integer_zerop (max)))
+ /* 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));
- t = VR_RANGE;
+ 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));
- t = VR_RANGE;
+ 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. */
- set_value_range (vr, t, min, max, equiv);
+ m_kind = kind;
+ m_min = min;
+ m_max = max;
+ if (flag_checking)
+ check ();
}
-/* Copy value range FROM into value range TO. */
-
void
-copy_value_range (value_range *to, const value_range *from)
+value_range_base::set (tree val)
{
- set_value_range (to, from->type, from->min, from->max, from->equiv);
+ 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);
}
-/* Set value range VR to a single value. This function is only called
- with values we get from statements, and exists to clear the
- TREE_OVERFLOW flag. */
-
void
-set_value_range_to_value (value_range *vr, tree val, bitmap equiv)
+value_range::set (tree val)
{
- gcc_assert (is_gimple_min_invariant (val));
+ gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
if (TREE_OVERFLOW_P (val))
val = drop_tree_overflow (val);
- set_value_range (vr, VR_RANGE, val, val, equiv);
+ set (VR_RANGE, val, val, NULL);
}
-/* Set value range VR to a non-NULL range of type TYPE. */
+/* Set value range VR to a nonzero range of type TYPE. */
void
-set_value_range_to_nonnull (value_range *vr, tree type)
+value_range_base::set_nonzero (tree type)
{
tree zero = build_int_cst (type, 0);
- set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
+ set (VR_ANTI_RANGE, zero, zero);
}
-
-/* Set value range VR to a NULL range of type TYPE. */
+/* Set value range VR to a ZERO range of type TYPE. */
void
-set_value_range_to_null (value_range *vr, tree type)
+value_range_base::set_zero (tree type)
{
- set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv);
+ set (build_int_cst (type, 0));
}
/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
&& bitmap_equal_p (b1, b2)));
}
-/* Return true if VR is [0, 0]. */
-
-static inline bool
-range_is_null (const value_range *vr)
+static bool
+range_has_numeric_bounds_p (const value_range_base *vr)
{
- return vr->type == VR_RANGE
- && integer_zerop (vr->min)
- && integer_zerop (vr->max);
+ 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 *vr)
+range_int_cst_p (const value_range_base *vr)
{
- return (vr->type == VR_RANGE
- && TREE_CODE (vr->max) == INTEGER_CST
- && TREE_CODE (vr->min) == INTEGER_CST);
+ return (vr->kind () == VR_RANGE && range_has_numeric_bounds_p (vr));
}
/* Return true if VR is a INTEGER_CST singleton. */
bool
-range_int_cst_singleton_p (const value_range *vr)
+range_int_cst_singleton_p (const value_range_base *vr)
{
return (range_int_cst_p (vr)
- && tree_int_cst_equal (vr->min, vr->max));
-}
-
-/* Return true if value range VR involves at least one symbol. */
-
-bool
-symbolic_range_p (const value_range *vr)
-{
- return (!is_gimple_min_invariant (vr->min)
- || !is_gimple_min_invariant (vr->max));
+ && 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))
}
else
{
- tree t;
+ if (TREE_CODE (val1) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST)
+ {
+ /* We cannot compare overflowed values. */
+ if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
+ return -2;
+
+ return tree_int_cst_compare (val1, val2);
+ }
/* First see if VAL1 and VAL2 are not the same. */
- if (val1 == val2 || operand_equal_p (val1, val2, 0))
+ if (operand_equal_p (val1, val2, 0))
return 0;
+ fold_defer_overflow_warnings ();
+
/* If VAL1 is a lower address than VAL2, return -1. */
- if (operand_less_p (val1, val2) == 1)
- return -1;
+ tree t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val1, val2);
+ if (t && integer_onep (t))
+ {
+ fold_undefer_and_ignore_overflow_warnings ();
+ return -1;
+ }
/* If VAL1 is a higher address than VAL2, return +1. */
- if (operand_less_p (val2, val1) == 1)
- return 1;
-
- /* If VAL1 is different than VAL2, return +2.
- For integer constants we either have already returned -1 or 1
- or they are equivalent. We still might succeed in proving
- something about non-trivial operands. */
- if (TREE_CODE (val1) != INTEGER_CST
- || TREE_CODE (val2) != INTEGER_CST)
+ t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val2, val1);
+ if (t && integer_onep (t))
{
- t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2);
- if (t && integer_onep (t))
- return 2;
+ fold_undefer_and_ignore_overflow_warnings ();
+ return 1;
}
+ /* If VAL1 is different than VAL2, return +2. */
+ t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2);
+ fold_undefer_and_ignore_overflow_warnings ();
+ if (t && integer_onep (t))
+ return 2;
+
return -2;
}
}
}
-/* Return 1 if VAL is inside value range MIN <= VAL <= MAX,
- 0 if VAL is not inside [MIN, MAX],
+/* Return 1 if VAL is inside value range.
+ 0 if VAL is not inside value range.
-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)
+value_range_base::value_inside_range (tree val) const
{
int cmp1, cmp2;
- cmp1 = operand_less_p (val, min);
+ if (varying_p ())
+ return 1;
+
+ if (undefined_p ())
+ return 0;
+
+ cmp1 = operand_less_p (val, m_min);
if (cmp1 == -2)
return -2;
if (cmp1 == 1)
- return 0;
+ return m_kind != VR_RANGE;
- cmp2 = operand_less_p (max, val);
+ cmp2 = operand_less_p (m_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 (const value_range *vr0, const 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 TRUE if *VR includes the value zero. */
-
-bool
-range_includes_zero_p (const value_range *vr)
-{
- if (vr->type == VR_VARYING)
- return true;
-
- /* Ughh, we don't know. We choose not to optimize. */
- if (vr->type == VR_UNDEFINED)
- return true;
-
- tree zero = build_int_cst (TREE_TYPE (vr->min), 0);
- if (vr->type == VR_ANTI_RANGE)
- {
- int res = value_inside_range (zero, vr->min, vr->max);
- return res == 0 || res == -2;
- }
- return value_inside_range (zero, vr->min, vr->max) != 0;
+ if (m_kind == VR_RANGE)
+ return !cmp2;
+ else
+ return !!cmp2;
}
-/* Return true if *VR is know to only contain nonnegative values. */
+/* For range [LB, UB] compute two wide_int bit masks.
-static inline bool
-value_range_nonnegative_p (const 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;
-}
+ 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.
-/* If *VR has a value rante that is a single constant value return that,
- otherwise return NULL_TREE. */
+ 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. */
-tree
-value_range_constant_singleton (const value_range *vr)
+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)
{
- 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;
-}
+ may_be_nonzero = wi::minus_one (lb.get_precision ());
+ must_be_nonzero = wi::zero (lb.get_precision ());
-/* Value range wrapper for wide_int_range_set_zero_nonzero_bits.
+ if (wi::eq_p (lb, ub))
+ {
+ may_be_nonzero = lb;
+ must_be_nonzero = may_be_nonzero;
+ }
+ else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
+ {
+ wide_int xor_mask = lb ^ ub;
+ may_be_nonzero = lb | ub;
+ must_be_nonzero = lb & ub;
+ 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);
+ }
+ }
+}
- Compute MAY_BE_NONZERO and MUST_BE_NONZERO bit masks for range in VR.
+/* 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 *vr,
+ const value_range_base *vr,
wide_int *may_be_nonzero,
wide_int *must_be_nonzero)
{
return false;
}
wide_int_range_set_zero_nonzero_bits (TYPE_SIGN (expr_type),
- wi::to_wide (vr->min),
- wi::to_wide (vr->max),
+ wi::to_wide (vr->min ()),
+ wi::to_wide (vr->max ()),
*may_be_nonzero, *must_be_nonzero);
return true;
}
*VR1 will be VR_UNDEFINED. */
static bool
-ranges_from_anti_range (const value_range *ar,
- value_range *vr0, value_range *vr1)
+ranges_from_anti_range (const value_range_base *ar,
+ value_range_base *vr0, value_range_base *vr1,
+ bool handle_pointers)
{
- tree type = TREE_TYPE (ar->min);
+ tree type = ar->type ();
- vr0->type = VR_UNDEFINED;
- vr1->type = VR_UNDEFINED;
+ 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->type != VR_ANTI_RANGE
- || TREE_CODE (ar->min) != INTEGER_CST
- || TREE_CODE (ar->max) != INTEGER_CST
- || !vrp_val_min (type)
- || !vrp_val_max (type))
+ 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 (!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)
+ 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 ())
{
*vr0 = *vr1;
- vr1->type = VR_UNDEFINED;
- }
-
- return vr0->type != VR_UNDEFINED;
-}
-
-/* Extract the components of a value range into a pair of wide ints in
- [WMIN, WMAX].
-
- If the value range is anything but a VR_*RANGE of constants, the
- resulting wide ints are set to [-MIN, +MAX] for the type. */
-
-static void inline
-extract_range_into_wide_ints (const value_range *vr,
- signop sign, unsigned prec,
- wide_int &wmin, wide_int &wmax)
-{
- if ((vr->type == VR_RANGE
- || vr->type == VR_ANTI_RANGE)
- && TREE_CODE (vr->min) == INTEGER_CST
- && TREE_CODE (vr->max) == INTEGER_CST)
- {
- wmin = wi::to_wide (vr->min);
- wmax = wi::to_wide (vr->max);
- }
- else
- {
- wmin = wi::min_value (prec, sign);
- wmax = wi::max_value (prec, sign);
+ vr1->set_undefined ();
}
-}
-
-/* Value range wrapper for wide_int_range_multiplicative_op:
- *VR = *VR0 .CODE. *VR1. */
-
-static void
-extract_range_from_multiplicative_op (value_range *vr,
- enum tree_code code,
- const value_range *vr0,
- const value_range *vr1)
-{
- gcc_assert (code == MULT_EXPR
- || code == TRUNC_DIV_EXPR
- || code == FLOOR_DIV_EXPR
- || code == CEIL_DIV_EXPR
- || code == EXACT_DIV_EXPR
- || code == ROUND_DIV_EXPR
- || code == RSHIFT_EXPR
- || code == LSHIFT_EXPR);
- gcc_assert (vr0->type == VR_RANGE && vr0->type == vr1->type);
-
- tree type = TREE_TYPE (vr0->min);
- wide_int res_lb, res_ub;
- wide_int vr0_lb = wi::to_wide (vr0->min);
- wide_int vr0_ub = wi::to_wide (vr0->max);
- wide_int vr1_lb = wi::to_wide (vr1->min);
- wide_int vr1_ub = wi::to_wide (vr1->max);
- bool overflow_undefined = TYPE_OVERFLOW_UNDEFINED (type);
- bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type);
- unsigned prec = TYPE_PRECISION (type);
-
- if (wide_int_range_multiplicative_op (res_lb, res_ub,
- code, TYPE_SIGN (type), prec,
- vr0_lb, vr0_ub, vr1_lb, vr1_ub,
- overflow_undefined, overflow_wraps))
- set_and_canonicalize_value_range (vr, VR_RANGE,
- wide_int_to_tree (type, res_lb),
- wide_int_to_tree (type, res_ub), NULL);
- else
- set_value_range_to_varying (vr);
+ return !vr0->undefined_p ();
}
/* If BOUND will include a symbolic bound, adjust it accordingly,
underflow. +1 indicates overflow. 0 indicates neither. */
static void
-set_value_range_with_overflow (value_range &vr,
+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,
{
const signop sgn = TYPE_SIGN (type);
const unsigned int prec = TYPE_PRECISION (type);
- vr.type = VR_RANGE;
- vr.equiv = NULL;
+
+ /* 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;
+ }
+
if (TYPE_OVERFLOW_WRAPS (type))
{
/* If overflow wraps, truncate the values and adjust the
wide_int tmax = wide_int::from (wmax, prec, sgn);
if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE))
{
- /* No overflow or both overflow or underflow. The
- range kind stays VR_RANGE. */
- vr.min = wide_int_to_tree (type, tmin);
- vr.max = wide_int_to_tree (type, tmax);
+ /* If the limits are swapped, we wrapped around and cover
+ the entire range. */
+ if (wi::gt_p (tmin, tmax, sgn))
+ kind = VR_VARYING;
+ else
+ {
+ 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);
+ }
+ return;
}
else if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE)
|| (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE))
changes to VR_ANTI_RANGE. */
bool covers = false;
wide_int tem = tmin;
- vr.type = VR_ANTI_RANGE;
tmin = tmax + 1;
if (wi::cmp (tmin, tmax, sgn) < 0)
covers = true;
types values. */
if (covers || wi::cmp (tmin, tmax, sgn) > 0)
{
- set_value_range_to_varying (&vr);
+ kind = VR_VARYING;
return;
}
- vr.min = wide_int_to_tree (type, tmin);
- vr.max = wide_int_to_tree (type, tmax);
+ kind = VR_ANTI_RANGE;
+ min = wide_int_to_tree (type, tmin);
+ max = wide_int_to_tree (type, tmax);
+ return;
}
else
{
/* Other underflow and/or overflow, drop to VR_VARYING. */
- set_value_range_to_varying (&vr);
+ kind = VR_VARYING;
return;
}
}
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)
- vr.min = wide_int_to_tree (type, type_min);
+ min = wide_int_to_tree (type, type_min);
else if (min_ovf == wi::OVF_OVERFLOW)
- vr.min = wide_int_to_tree (type, type_max);
+ min = wide_int_to_tree (type, type_max);
else
- vr.min = wide_int_to_tree (type, wmin);
+ min = wide_int_to_tree (type, wmin);
if (max_ovf == wi::OVF_UNDERFLOW)
- vr.max = wide_int_to_tree (type, type_min);
+ max = wide_int_to_tree (type, type_min);
else if (max_ovf == wi::OVF_OVERFLOW)
- vr.max = wide_int_to_tree (type, type_max);
+ max = wide_int_to_tree (type, type_max);
else
- vr.max = wide_int_to_tree (type, wmax);
+ max = wide_int_to_tree (type, wmax);
}
}
-/* 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. */
+/* Fold two value range's of a POINTER_PLUS_EXPR into VR. */
-void
-extract_range_from_binary_expr_1 (value_range *vr,
- enum tree_code code, tree expr_type,
- const value_range *vr0_,
- const value_range *vr1_)
-{
- signop sign = TYPE_SIGN (expr_type);
- unsigned int prec = TYPE_PRECISION (expr_type);
- 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;
+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);
+}
- if (!INTEGRAL_TYPE_P (expr_type)
- && !POINTER_TYPE_P (expr_type))
- {
- set_value_range_to_varying (vr);
- return;
- }
+/* Extract range information from a PLUS/MINUS_EXPR and store the
+ result in *VR. */
- /* 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;
- }
+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);
- /* If both ranges are UNDEFINED, so is the result. */
- if (vr0.type == VR_UNDEFINED && vr1.type == VR_UNDEFINED)
- {
- 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;
- }
+ value_range_base vr0 = *vr0_, vr1 = *vr1_;
+ value_range_base vrtem0, vrtem1;
/* 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
+ if (vr0.kind () == VR_ANTI_RANGE
&& ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
{
- extract_range_from_binary_expr_1 (vr, code, expr_type, &vrtem0, vr1_);
- if (vrtem1.type != VR_UNDEFINED)
+ extract_range_from_plus_minus_expr (vr, code, expr_type, &vrtem0, vr1_);
+ if (!vrtem1.undefined_p ())
{
- value_range vrres = VR_INITIALIZER;
- extract_range_from_binary_expr_1 (&vrres, code, expr_type,
- &vrtem1, vr1_);
- vrp_meet (vr, &vrres);
+ value_range_base vrres;
+ extract_range_from_plus_minus_expr (&vrres, code, expr_type,
+ &vrtem1, vr1_);
+ vr->union_ (&vrres);
}
return;
}
/* Likewise for X op ~[]. */
- if (vr1.type == VR_ANTI_RANGE
+ if (vr1.kind () == VR_ANTI_RANGE
&& ranges_from_anti_range (&vr1, &vrtem0, &vrtem1))
{
- extract_range_from_binary_expr_1 (vr, code, expr_type, vr0_, &vrtem0);
- if (vrtem1.type != VR_UNDEFINED)
- {
- value_range vrres = VR_INITIALIZER;
- extract_range_from_binary_expr_1 (&vrres, code, expr_type,
- vr0_, &vrtem1);
- vrp_meet (vr, &vrres);
- }
- 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
- && code != POINTER_PLUS_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;
- }
-
- /* 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_includes_zero_p (&vr0) && !range_includes_zero_p (&vr1))
- set_value_range_to_nonnull (vr, expr_type);
- else if (range_is_null (&vr0) && range_is_null (&vr1))
- set_value_range_to_null (vr, expr_type);
- else
- set_value_range_to_varying (vr);
- }
- else if (code == POINTER_PLUS_EXPR)
- {
- /* For pointer types, we are really only interested in asserting
- whether the expression evaluates to non-NULL. */
- if (!range_includes_zero_p (&vr0)
- || !range_includes_zero_p (&vr1))
- set_value_range_to_nonnull (vr, expr_type);
- else if (range_is_null (&vr0) && range_is_null (&vr1))
- set_value_range_to_null (vr, expr_type);
- else
- set_value_range_to_varying (vr);
- }
- else if (code == BIT_AND_EXPR)
+ extract_range_from_plus_minus_expr (vr, code, expr_type, vr0_, &vrtem0);
+ if (!vrtem1.undefined_p ())
{
- /* For pointer types, we are really only interested in asserting
- whether the expression evaluates to non-NULL. */
- if (!range_includes_zero_p (&vr0) && !range_includes_zero_p (&vr1))
- set_value_range_to_nonnull (vr, expr_type);
- else if (range_is_null (&vr0) || range_is_null (&vr1))
- set_value_range_to_null (vr, expr_type);
- else
- set_value_range_to_varying (vr);
+ value_range_base vrres;
+ extract_range_from_plus_minus_expr (&vrres, code, expr_type,
+ vr0_, &vrtem1);
+ vr->union_ (&vrres);
}
- else
- set_value_range_to_varying (vr);
-
return;
}
- /* 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)
- {
- /* 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.type == VR_VARYING)
- {
- vr0.type = VR_RANGE;
- vr0.min = vrp_val_min (expr_type);
- vr0.max = vrp_val_max (expr_type);
- }
- if (vr1.type == VR_VARYING)
- {
- vr1.type = 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.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))))
- {
- wide_int wmin, wmax;
- wi::overflow_type min_ovf = wi::OVF_NONE;
- wi::overflow_type max_ovf = wi::OVF_NONE;
-
- /* Build the bounds. */
- combine_bound (code, wmin, min_ovf, expr_type, min_op0, min_op1);
- combine_bound (code, wmax, max_ovf, expr_type, max_op0, max_op1);
-
- /* If we have overflow for the constant part and the resulting
- range will be symbolic, drop to VR_VARYING. */
- if (((bool)min_ovf && sym_min_op0 != sym_min_op1)
- || ((bool)max_ovf && sym_max_op0 != sym_max_op1))
- {
- set_value_range_to_varying (vr);
- return;
- }
+ 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;
- /* Adjust the range for possible overflow. */
- set_value_range_with_overflow (*vr, expr_type,
- wmin, wmax, min_ovf, max_ovf);
- if (vr->type == VR_VARYING)
- return;
-
- /* Build the symbolic bounds if needed. */
- adjust_symbolic_bound (vr->min, code, expr_type,
- sym_min_op0, sym_min_op1,
- neg_min_op0, neg_min_op1);
- adjust_symbolic_bound (vr->max, code, expr_type,
- sym_max_op0, sym_max_op1,
- neg_max_op0, neg_max_op1);
- /* ?? It would probably be cleaner to eliminate min/max/type
- entirely and hold these values in VR directly. */
- min = vr->min;
- max = vr->max;
- type = vr->type;
- }
- 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;
- }
- }
- else if (code == MIN_EXPR
- || code == MAX_EXPR)
+ /* 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;
- wide_int vr0_min, vr0_max;
- wide_int vr1_min, vr1_max;
- extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
- extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max);
- if (wide_int_range_min_max (wmin, wmax, code, sign, prec,
- vr0_min, vr0_max, vr1_min, vr1_max))
- set_value_range (vr, VR_RANGE,
- wide_int_to_tree (expr_type, wmin),
- wide_int_to_tree (expr_type, wmax), NULL);
- else
- set_value_range_to_varying (vr);
- return;
- }
- else if (code == MULT_EXPR)
- {
- if (!range_int_cst_p (&vr0)
- || !range_int_cst_p (&vr1))
+ wi::overflow_type min_ovf = wi::OVF_NONE;
+ wi::overflow_type max_ovf = wi::OVF_NONE;
+
+ /* Build the bounds. */
+ combine_bound (code, wmin, min_ovf, expr_type, min_op0, min_op1);
+ combine_bound (code, wmax, max_ovf, expr_type, max_op0, max_op1);
+
+ /* If the resulting range will be symbolic, we need to eliminate any
+ explicit or implicit overflow introduced in the above computation
+ because compare_values could make an incorrect use of it. That's
+ why we require one of the ranges to be a singleton. */
+ if ((sym_min_op0 != sym_min_op1 || sym_max_op0 != sym_max_op1)
+ && ((bool)min_ovf || (bool)max_ovf
+ || (min_op0 != max_op0 && min_op1 != max_op1)))
{
- set_value_range_to_varying (vr);
+ vr->set_varying (expr_type);
return;
}
- extract_range_from_multiplicative_op (vr, code, &vr0, &vr1);
- return;
- }
- else if (code == RSHIFT_EXPR
- || code == LSHIFT_EXPR)
- {
- if (range_int_cst_p (&vr1)
- && !wide_int_range_shift_undefined_p (prec,
- wi::to_wide (vr1.min),
- wi::to_wide (vr1.max)))
- {
- 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 (vr, code, &vr0, &vr1);
- return;
- }
- else if (code == LSHIFT_EXPR
- && range_int_cst_p (&vr0))
- {
- wide_int res_lb, res_ub;
- if (wide_int_range_lshift (res_lb, res_ub, sign, prec,
- wi::to_wide (vr0.min),
- wi::to_wide (vr0.max),
- wi::to_wide (vr1.min),
- wi::to_wide (vr1.max),
- TYPE_OVERFLOW_UNDEFINED (expr_type),
- TYPE_OVERFLOW_WRAPS (expr_type)))
- {
- min = wide_int_to_tree (expr_type, res_lb);
- max = wide_int_to_tree (expr_type, res_ub);
- set_and_canonicalize_value_range (vr, VR_RANGE,
- min, max, NULL);
- return;
- }
- }
- }
- set_value_range_to_varying (vr);
- return;
- }
- else if (code == TRUNC_DIV_EXPR
- || code == FLOOR_DIV_EXPR
- || code == CEIL_DIV_EXPR
- || code == EXACT_DIV_EXPR
- || code == ROUND_DIV_EXPR)
- {
- wide_int dividend_min, dividend_max, divisor_min, divisor_max;
- wide_int wmin, wmax, extra_min, extra_max;
- bool extra_range_p;
- /* Special case explicit division by zero as undefined. */
- if (range_is_null (&vr1))
+ /* 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)
{
- set_value_range_to_undefined (vr);
+ vr->set_varying (expr_type);
return;
}
- /* First, normalize ranges into constants we can handle. Note
- that VR_ANTI_RANGE's of constants were already normalized
- before arriving here.
-
- NOTE: As a future improvement, we may be able to do better
- with mixed symbolic (anti-)ranges like [0, A]. See note in
- ranges_from_anti_range. */
- extract_range_into_wide_ints (&vr0, sign, prec,
- dividend_min, dividend_max);
- extract_range_into_wide_ints (&vr1, sign, prec,
- divisor_min, divisor_max);
- if (!wide_int_range_div (wmin, wmax, code, sign, prec,
- dividend_min, dividend_max,
- divisor_min, divisor_max,
- TYPE_OVERFLOW_UNDEFINED (expr_type),
- TYPE_OVERFLOW_WRAPS (expr_type),
- extra_range_p, extra_min, extra_max))
- {
- set_value_range_to_varying (vr);
- return;
- }
- set_value_range (vr, VR_RANGE,
- wide_int_to_tree (expr_type, wmin),
- wide_int_to_tree (expr_type, wmax), NULL);
- if (extra_range_p)
- {
- value_range extra_range = VR_INITIALIZER;
- set_value_range (&extra_range, VR_RANGE,
- wide_int_to_tree (expr_type, extra_min),
- wide_int_to_tree (expr_type, extra_max), NULL);
- vrp_meet (vr, &extra_range);
- }
- return;
+ /* Build the symbolic bounds if needed. */
+ adjust_symbolic_bound (min, code, expr_type,
+ sym_min_op0, sym_min_op1,
+ neg_min_op0, neg_min_op1);
+ adjust_symbolic_bound (max, code, expr_type,
+ sym_max_op0, sym_max_op1,
+ neg_max_op0, neg_max_op1);
}
- else if (code == TRUNC_MOD_EXPR)
+ else
{
- if (range_is_null (&vr1))
- {
- set_value_range_to_undefined (vr);
- return;
- }
- wide_int wmin, wmax, tmp;
- wide_int vr0_min, vr0_max, vr1_min, vr1_max;
- extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
- extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max);
- wide_int_range_trunc_mod (wmin, wmax, sign, prec,
- vr0_min, vr0_max, vr1_min, vr1_max);
- min = wide_int_to_tree (expr_type, wmin);
- max = wide_int_to_tree (expr_type, wmax);
- set_value_range (vr, VR_RANGE, min, max, NULL);
+ /* For other cases, for example if we have a PLUS_EXPR with two
+ VR_ANTI_RANGEs, drop to VR_VARYING. It would take more effort
+ to compute a precise range for such a case.
+ ??? General even mixed range kind operations can be expressed
+ by for example transforming ~[3, 5] + [1, 2] to range-only
+ operations and a union primitive:
+ [-INF, 2] + [1, 2] U [5, +INF] + [1, 2]
+ [-INF+1, 4] U [6, +INF(OVF)]
+ though usually the union is not exactly representable with
+ a single range or anti-range as the above is
+ [-INF+1, +INF(OVF)] intersected with ~[5, 5]
+ but one could use a scheme similar to equivalences for this. */
+ vr->set_varying (expr_type);
return;
}
- else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR)
- {
- wide_int may_be_nonzero0, may_be_nonzero1;
- wide_int must_be_nonzero0, must_be_nonzero1;
- wide_int wmin, wmax;
- wide_int vr0_min, vr0_max, vr1_min, vr1_max;
- vrp_set_zero_nonzero_bits (expr_type, &vr0,
- &may_be_nonzero0, &must_be_nonzero0);
- vrp_set_zero_nonzero_bits (expr_type, &vr1,
- &may_be_nonzero1, &must_be_nonzero1);
- extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
- extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max);
- if (code == BIT_AND_EXPR)
- {
- if (wide_int_range_bit_and (wmin, wmax, sign, prec,
- vr0_min, vr0_max,
- vr1_min, vr1_max,
- must_be_nonzero0,
- may_be_nonzero0,
- must_be_nonzero1,
- may_be_nonzero1))
- {
- min = wide_int_to_tree (expr_type, wmin);
- max = wide_int_to_tree (expr_type, wmax);
- set_value_range (vr, VR_RANGE, min, max, NULL);
- }
- else
- set_value_range_to_varying (vr);
- return;
- }
- else if (code == BIT_IOR_EXPR)
- {
- if (wide_int_range_bit_ior (wmin, wmax, sign,
- vr0_min, vr0_max,
- vr1_min, vr1_max,
- must_be_nonzero0,
- may_be_nonzero0,
- must_be_nonzero1,
- may_be_nonzero1))
- {
- min = wide_int_to_tree (expr_type, wmin);
- max = wide_int_to_tree (expr_type, wmax);
- set_value_range (vr, VR_RANGE, min, max, NULL);
- }
- else
- set_value_range_to_varying (vr);
- return;
- }
- else if (code == BIT_XOR_EXPR)
- {
- if (wide_int_range_bit_xor (wmin, wmax, sign, prec,
- must_be_nonzero0,
- may_be_nonzero0,
- must_be_nonzero1,
- may_be_nonzero1))
- {
- min = wide_int_to_tree (expr_type, wmin);
- max = wide_int_to_tree (expr_type, wmax);
- set_value_range (vr, VR_RANGE, min, max, NULL);
- }
- else
- set_value_range_to_varying (vr);
- return;
- }
- }
- else
- gcc_unreachable ();
/* If either MIN or MAX overflowed, then set the resulting range to
VARYING. */
|| 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,
- const 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)
{
- signop sign = TYPE_SIGN (type);
- unsigned int prec = TYPE_PRECISION (type);
- value_range vr0 = *vr0_, vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER;
+ const range_operator *op = range_op_handler (code, expr_type);
+ if (!op)
+ vr->set_varying (expr_type);
+ return op;
+}
- /* VRP only operates on integral and pointer types. */
- if (!(INTEGRAL_TYPE_P (op0_type)
- || POINTER_TYPE_P (op0_type))
- || !(INTEGRAL_TYPE_P (type)
- || POINTER_TYPE_P (type)))
- {
- set_value_range_to_varying (vr);
- return;
- }
+/* If the types passed are supported, return TRUE, otherwise set VR to
+ VARYING and return FALSE. */
- /* If VR0 is UNDEFINED, so is the result. */
- if (vr0.type == VR_UNDEFINED)
+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)))
{
- set_value_range_to_undefined (vr);
- return;
+ vr->set_varying (type0);
+ return false;
}
+ return true;
+}
- /* 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)
- {
- /* ~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;
- }
+/* If any of the ranges passed are defined, return TRUE, otherwise set
+ VR to UNDEFINED and return FALSE. */
- /* 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))
+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 ()))
{
- 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;
+ vr->set_undefined ();
+ return false;
}
+ return true;
+}
- if (CONVERT_EXPR_CODE_P (code))
- {
- tree inner_type = op0_type;
- tree outer_type = 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;
+}
- /* 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_includes_zero_p (&vr0))
- set_value_range_to_nonnull (vr, type);
- else if (range_is_null (&vr0))
- set_value_range_to_null (vr, type);
- else
- set_value_range_to_varying (vr);
- return;
- }
+/* If any operand is symbolic, perform a binary operation on them and
+ return TRUE, otherwise return FALSE. */
- /* We normalize everything to a VR_RANGE, but for constant
- anti-ranges we must handle them by leaving the final result
- as an anti range. This allows us to convert things like
- ~[0,5] seamlessly. */
- value_range_type vr_type = VR_RANGE;
- if (vr0.type == VR_ANTI_RANGE
- && TREE_CODE (vr0.min) == INTEGER_CST
- && TREE_CODE (vr0.max) == INTEGER_CST)
- vr_type = VR_ANTI_RANGE;
-
- /* NOTES: Previously we were returning VARYING for all symbolics, but
- we can do better by treating them as [-MIN, +MAX]. For
- example, converting [SYM, SYM] from INT to LONG UNSIGNED,
- we can return: ~[0x8000000, 0xffffffff7fffffff].
-
- We were also failing to convert ~[0,0] from char* to unsigned,
- instead choosing to return VR_VARYING. Now we return ~[0,0]. */
- wide_int vr0_min, vr0_max, wmin, wmax;
- signop inner_sign = TYPE_SIGN (inner_type);
- signop outer_sign = TYPE_SIGN (outer_type);
- unsigned inner_prec = TYPE_PRECISION (inner_type);
- unsigned outer_prec = TYPE_PRECISION (outer_type);
- extract_range_into_wide_ints (&vr0, inner_sign, inner_prec,
- vr0_min, vr0_max);
- if (wide_int_range_convert (wmin, wmax,
- inner_sign, inner_prec,
- outer_sign, outer_prec,
- vr0_min, vr0_max))
+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))
{
- tree min = wide_int_to_tree (outer_type, wmin);
- tree max = wide_int_to_tree (outer_type, wmax);
- set_and_canonicalize_value_range (vr, vr_type, min, max, NULL);
+ extract_range_from_plus_minus_expr (vr, code, expr_type, vr0, vr1);
+ return true;
}
- else
- set_value_range_to_varying (vr);
- return;
- }
- else if (code == ABS_EXPR)
- {
- if (vr0.type != VR_RANGE || symbolic_range_p (&vr0))
+ if (POINTER_TYPE_P (expr_type) && code == POINTER_PLUS_EXPR)
{
- set_value_range_to_varying (vr);
- return;
+ extract_range_from_pointer_plus_expr (vr, code, expr_type, vr0, vr1);
+ return true;
}
- wide_int wmin, wmax;
- wide_int vr0_min, vr0_max;
- extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
- if (wide_int_range_abs (wmin, wmax, sign, prec, vr0_min, vr0_max,
- TYPE_OVERFLOW_UNDEFINED (type)))
- set_value_range (vr, VR_RANGE,
- wide_int_to_tree (type, wmin),
- wide_int_to_tree (type, wmax), NULL);
- else
- set_value_range_to_varying (vr);
- return;
+ 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;
}
-
- /* 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 (const 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. */
+/* If operand is symbolic, perform a unary operation on it and return
+ TRUE, otherwise return FALSE. */
-void
-dump_value_range (FILE *file, const value_range *vr)
+static bool
+range_fold_unary_symbolics_p (value_range_base *vr,
+ tree_code code,
+ tree expr_type,
+ const value_range_base *vr0)
{
- 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)
+ if (vr0->symbolic_p ())
{
- 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)
+ if (code == NEGATE_EXPR)
{
- bitmap_iterator bi;
- unsigned i, c = 0;
-
- fprintf (file, " EQUIVALENCES: { ");
-
- EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
- {
- print_generic_expr (file, ssa_name (i));
- fprintf (file, " ");
- c++;
- }
-
- fprintf (file, "} (%u elements)", c);
+ /* -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;
+ }
+ if (code == BIT_NOT_EXPR)
+ {
+ /* ~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;
}
+ 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;
}
- else if (vr->type == VR_VARYING)
- fprintf (file, "VARYING");
- else
- fprintf (file, "INVALID RANGE");
+ return false;
}
+/* Perform a binary operation on a pair of ranges. */
-/* Dump value range VR to stderr. */
-
-DEBUG_FUNCTION void
-debug_value_range (const value_range *vr)
+void
+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_)
{
- dump_value_range (stderr, vr);
- fprintf (stderr, "\n");
+ if (!supported_types_p (vr, expr_type)
+ || !defined_ranges_p (vr, vr0_, vr1_))
+ return;
+ const range_operator *op = get_range_op_handler (vr, code, expr_type);
+ if (!op)
+ return;
+
+ value_range_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;
+
+ *vr = op->fold_range (expr_type,
+ vr0.normalize_addresses (),
+ vr1.normalize_addresses ());
}
+/* Perform a unary operation on a range. */
+
void
-value_range::dump () const
+range_fold_unary_expr (value_range_base *vr,
+ enum tree_code code, tree expr_type,
+ const value_range_base *vr0,
+ tree vr0_type)
{
- debug_value_range (this);
-}
+ 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
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);
}
}
void vrp_initialize (void);
void vrp_finalize (bool);
void check_all_array_refs (void);
- void check_array_ref (location_t, tree, bool);
- void check_mem_ref (location_t, tree, bool);
+ bool check_array_ref (location_t, tree, bool);
+ bool check_mem_ref (location_t, tree, bool);
void search_for_addr_array (tree, location_t);
class vr_values vr_values;
/* Temporary delegator to minimize code churn. */
- value_range *get_value_range (const_tree op)
+ const value_range *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)
{
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);
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
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
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). */
+ the address of the just-past-the-end element of an array).
+ Returns true if a warning has been issued. */
-void
+bool
vrp_prop::check_mem_ref (location_t location, tree ref,
bool ignore_off_by_one)
{
if (TREE_NO_WARNING (ref))
- return;
+ return false;
tree arg = TREE_OPERAND (ref, 0);
/* The constant and variable offset of the reference. */
const value_range *vr = NULL;
/* Determine the offsets and increment OFFRANGE for the bounds of each.
- The loop computes the the range of the final offset for expressions
- such as (A + i0 + ... + iN)[CSTOFF] where i0 through iN are SSA_NAMEs
- in some range. */
- while (TREE_CODE (arg) == SSA_NAME)
+ The loop computes the range of the final offset for expressions such
+ as (A + i0 + ... + iN)[CSTOFF] where i0 through iN are SSA_NAMEs in
+ some range. */
+ const unsigned limit = PARAM_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))
continue;
}
else
- return;
+ return false;
/* VAROFF should always be a SSA_NAME here (and not even
INTEGER_CST) but there's no point in taking chances. */
break;
vr = get_value_range (varoff);
- if (!vr || vr->type == VR_UNDEFINED || !vr->min || !vr->max)
+ if (!vr || vr->undefined_p () || vr->varying_p ())
break;
- if (TREE_CODE (vr->min) != INTEGER_CST
- || TREE_CODE (vr->max) != INTEGER_CST)
+ if (!vr->constant_p ())
break;
- if (vr->type == VR_RANGE)
+ if (vr->kind () == VR_RANGE)
{
- if (tree_int_cst_lt (vr->min, vr->max))
+ offset_int min
+ = wi::to_offset (fold_convert (ptrdiff_type_node, vr->min ()));
+ offset_int max
+ = wi::to_offset (fold_convert (ptrdiff_type_node, vr->max ()));
+ if (min < max)
{
- offset_int min
- = wi::to_offset (fold_convert (ptrdiff_type_node, vr->min));
- offset_int max
- = wi::to_offset (fold_convert (ptrdiff_type_node, vr->max));
- if (min < max)
- {
- offrange[0] += min;
- offrange[1] += max;
- }
- else
- {
- offrange[0] += max;
- offrange[1] += min;
- }
+ offrange[0] += min;
+ offrange[1] += max;
}
else
{
- /* Conservatively add [-MAXOBJSIZE -1, MAXOBJSIZE]
+ /* When MIN >= MAX, the offset is effectively in a union
+ of two ranges: [-MAXOBJSIZE -1, MAX] and [MIN, MAXOBJSIZE].
+ Since there is no way to represent such a range across
+ additions, conservatively add [-MAXOBJSIZE -1, MAXOBJSIZE]
to OFFRANGE. */
offrange[0] += arrbounds[0];
offrange[1] += arrbounds[1];
arg = TREE_OPERAND (arg, 0);
if (TREE_CODE (arg) != STRING_CST
&& TREE_CODE (arg) != VAR_DECL)
- return;
+ return false;
}
else
- return;
+ return false;
/* The type of the object being referred to. It can be an array,
string literal, or a non-array type when the MEM_REF represents
|| !COMPLETE_TYPE_P (reftype)
|| TREE_CODE (TYPE_SIZE_UNIT (reftype)) != INTEGER_CST
|| RECORD_OR_UNION_TYPE_P (reftype))
- return;
+ 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[0] = 0;
- arrbounds[1] = wi::lrshift (maxobjsize, wi::floor_log2 (eltsize));
- }
+ if (array_at_struct_end_p (arg) || !bnds[0] || !bnds[1])
+ arrbounds[1] = wi::lrshift (maxobjsize, wi::floor_log2 (eltsize));
else
- {
- arrbounds[0] = wi::to_offset (bnds[0]) * eltsize;
- arrbounds[1] = (wi::to_offset (bnds[1]) + 1) * eltsize;
- }
+ arrbounds[1] = (wi::to_offset (bnds[1]) - wi::to_offset (bnds[0])
+ + 1) * eltsize;
}
else
- {
- arrbounds[0] = 0;
- arrbounds[1] = wi::lrshift (maxobjsize, wi::floor_log2 (eltsize));
- }
+ arrbounds[1] = wi::lrshift (maxobjsize, wi::floor_log2 (eltsize));
if (TREE_CODE (ref) == MEM_REF)
{
else
{
eltsize = 1;
- arrbounds[0] = 0;
arrbounds[1] = wi::to_offset (TYPE_SIZE_UNIT (reftype));
}
{
/* Extract the element type out of MEM_REF and use its size
to compute the index to print in the diagnostic; arrays
- in MEM_REF don't mean anything. */
+ in MEM_REF don't mean anything. A type with no size like
+ void is as good as having a size of 1. */
tree type = TREE_TYPE (ref);
while (TREE_CODE (type) == ARRAY_TYPE)
type = TREE_TYPE (type);
- tree size = TYPE_SIZE_UNIT (type);
- offrange[0] = offrange[0] / wi::to_offset (size);
- offrange[1] = offrange[1] / wi::to_offset (size);
+ if (tree size = TYPE_SIZE_UNIT (type))
+ {
+ offrange[0] = offrange[0] / wi::to_offset (size);
+ offrange[1] = offrange[1] / wi::to_offset (size);
+ }
}
else
{
if (warned && DECL_P (arg))
inform (DECL_SOURCE_LOCATION (arg), "while referencing %qD", arg);
- TREE_NO_WARNING (ref) = 1;
- return;
+ if (warned)
+ TREE_NO_WARNING (ref) = 1;
+ return warned;
}
if (warn_array_bounds < 2)
- return;
+ return false;
/* At level 2 check also intermediate offsets. */
int i = 0;
{
HOST_WIDE_INT tmpidx = extrema[i].to_shwi () / eltsize.to_shwi ();
- warning_at (location, OPT_Warray_bounds,
- "intermediate array offset %wi is outside array bounds "
- "of %qT",
- tmpidx, reftype);
- TREE_NO_WARNING (ref) = 1;
+ if (warning_at (location, OPT_Warray_bounds,
+ "intermediate array offset %wi is outside array bounds "
+ "of %qT", tmpidx, reftype))
+ {
+ TREE_NO_WARNING (ref) = 1;
+ return true;
+ }
}
+
+ return false;
}
/* Searches if the expr T, located at LOCATION computes
/* Check each ARRAY_REF and MEM_REF in the reference chain. */
do
{
+ bool warned = false;
if (TREE_CODE (t) == ARRAY_REF)
- check_array_ref (location, t, true /*ignore_off_by_one*/);
+ warned = check_array_ref (location, t, true /*ignore_off_by_one*/);
else if (TREE_CODE (t) == MEM_REF)
- check_mem_ref (location, t, true /*ignore_off_by_one*/);
+ warned = check_mem_ref (location, t, true /*ignore_off_by_one*/);
+
+ if (warned)
+ TREE_NO_WARNING (t) = true;
t = TREE_OPERAND (t, 0);
}
*walk_subtree = TRUE;
+ bool warned = false;
vrp_prop *vrp_prop = (class vrp_prop *)wi->info;
if (TREE_CODE (t) == ARRAY_REF)
- vrp_prop->check_array_ref (location, t, false /*ignore_off_by_one*/);
+ warned = vrp_prop->check_array_ref (location, t, false/*ignore_off_by_one*/);
else if (TREE_CODE (t) == MEM_REF)
- vrp_prop->check_mem_ref (location, t, false /*ignore_off_by_one*/);
+ warned = vrp_prop->check_mem_ref (location, t, false /*ignore_off_by_one*/);
else if (TREE_CODE (t) == ADDR_EXPR)
{
vrp_prop->search_for_addr_array (t, location);
*walk_subtree = FALSE;
}
+ /* Propagate the no-warning bit to the outer expression. */
+ if (warned)
+ TREE_NO_WARNING (t) = true;
return NULL_TREE;
}
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);
const 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))
+ 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
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);
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, const 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, const 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");
+ }
- if (vr0->type == VR_UNDEFINED)
+ *this = union_helper (this, other);
+
+ 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;
- saved = *vr0;
- union_ranges (&vr0->type, &vr0->min, &vr0->max,
- vr1->type, vr1->min, vr1->max);
- if (vr0->type == VR_VARYING)
+ if (!range_includes_zero_p (this))
{
- /* Failed to find an efficient meet. Before giving up and setting
- the result to VARYING, see if we can at least derive a useful
- anti-range. */
- if (range_includes_zero_p (&saved) == 0
- && range_includes_zero_p (vr1) == 0)
- {
- set_value_range_to_nonnull (vr0, TREE_TYPE (saved.min));
+ gcc_checking_assert (TREE_CODE (m_min) == ADDR_EXPR
+ || TREE_CODE (m_max) == ADDR_EXPR);
+ return range_nonzero (type ());
+ }
+ return value_range_base (type ());
+}
- /* 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;
- }
+/* Normalize symbolics and addresses into constants. */
- set_value_range_to_varying (vr0);
- 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 ();
+
+ // [SYM, SYM] -> VARYING
+ if (min_symbolic && max_symbolic)
+ {
+ value_range_base var;
+ var.set_varying (ttype);
+ return var;
+ }
+ 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;
}
- set_and_canonicalize_value_range (vr0, vr0->type, vr0->min, vr0->max,
- vr0->equiv);
- if (vr0->type == VR_VARYING)
- return;
+ // ~[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);
const value_range *vr = vr_values->get_value_range (op);
- if ((vr->type != VR_RANGE && vr->type != VR_ANTI_RANGE)
- || symbolic_range_p (vr))
+ 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);
}
{
edge dummy_e;
tree dummy_tree;
- value_range new_vr = VR_INITIALIZER;
+ value_range new_vr;
vr_values->extract_range_from_stmt (stmt, &dummy_e,
&dummy_tree, &new_vr);
- if (range_int_cst_singleton_p (&new_vr))
- return new_vr.min;
+ tree singleton;
+ if (new_vr.singleton_p (&singleton))
+ return singleton;
}
}
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. */
continue;
const 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))
+ if (!name || !vr->constant_p ())
continue;
if (POINTER_TYPE_P (TREE_TYPE (name))
&& 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
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 ();
/* Worker for determine_value_range. */
static void
-determine_value_range_1 (value_range *vr, tree expr)
+determine_value_range_1 (value_range_base *vr, tree expr)
{
if (BINARY_CLASS_P (expr))
{
- value_range vr0 = VR_INITIALIZER, vr1 = VR_INITIALIZER;
+ value_range_base vr0, vr1;
determine_value_range_1 (&vr0, TREE_OPERAND (expr, 0));
determine_value_range_1 (&vr1, TREE_OPERAND (expr, 1));
- extract_range_from_binary_expr_1 (vr, TREE_CODE (expr), TREE_TYPE (expr),
- &vr0, &vr1);
+ range_fold_binary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr),
+ &vr0, &vr1);
}
else if (UNARY_CLASS_P (expr))
{
- value_range vr0 = VR_INITIALIZER;
+ value_range_base vr0;
determine_value_range_1 (&vr0, TREE_OPERAND (expr, 0));
- extract_range_from_unary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr),
- &vr0, TREE_TYPE (TREE_OPERAND (expr, 0)));
+ range_fold_unary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr),
+ &vr0, TREE_TYPE (TREE_OPERAND (expr, 0)));
}
else if (TREE_CODE (expr) == INTEGER_CST)
- set_value_range_to_value (vr, expr, NULL);
+ vr->set (expr);
else
{
- value_range_type kind;
+ 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)
- set_value_range (vr, kind, wide_int_to_tree (TREE_TYPE (expr), min),
- wide_int_to_tree (TREE_TYPE (expr), max), NULL);
+ vr->set (kind, wide_int_to_tree (TREE_TYPE (expr), min),
+ wide_int_to_tree (TREE_TYPE (expr), max));
else
- set_value_range_to_varying (vr);
+ 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_type
+value_range_kind
determine_value_range (tree expr, wide_int *min, wide_int *max)
{
- value_range vr = VR_INITIALIZER;
+ value_range_base vr;
determine_value_range_1 (&vr, expr);
- if ((vr.type == VR_RANGE
- || vr.type == VR_ANTI_RANGE)
- && !symbolic_range_p (&vr))
+ if (vr.constant_p ())
{
- *min = wi::to_wide (vr.min);
- *max = wi::to_wide (vr.max);
- return vr.type;
+ *min = wi::to_wide (vr.min ());
+ *max = wi::to_wide (vr.max ());
+ return vr.kind ();
}
return VR_VARYING;
projects / platform / upstream / gcc.git / blobdiff