commit 8ccfc09bf5b663b1a309ea5f404b92d6bcfa0f0b
Author: Aldy Hernandez <aldyh@redhat.com>
Date: Wed Nov 13 17:17:21 2019 +0100
Move plain value_range things to value-range.[hc]*.
@@ -1,5 +1,26 @@
2019-11-13 Aldy Hernandez <aldyh@redhat.com>
+ * Makefile.in (OBJS): Add value-range.o.
+ (GTFILES): Add value-range.h.
+ * gengtype.c (open_base_files): Add value-range.h to list of
+ header files.
+ * tree-vrp.c: Move the following value_range related functions:
+ ranges_from_anti_range, value_range, check, equal_p, symbolic_p,
+ constant_p, set_undefined, set_varying, may_contain_p,
+ singleton_p, type, dump, dump_value_range, debug, vrp_val_max,
+ vrp_val_min, vrp_val_is_min, vrp_val_is_max, set, set_nonzero,
+ set_zero, vrp_operand_equal_p, range_has_numeric_bounds_p,
+ value_inside_range, ranges_from_anti_range, union_ranges,
+ intersect_ranges, intersect_helper, union_helper, union_,
+ normalize_addresses, normalize_symbolics, num_pairs, lower_bound,
+ upper_bound, contains_p, invert, intersect...
+ * value-range.cc: ...to here.
+ * tree-vrp.h: Move class value_range, enum_value_range_kind, and
+ associated inline methods from here...
+ * value-range.h: ...to here.
+
+(2019-11-13 Aldy Hernandez <aldyh@redhat.com>
+
* gimple-fold.c (size_must_be_zero_p): Rewrite use of value_range
constructors and set methods so value_range_kind is the last
argument and defaults to VR_RANGE.
@@ -1602,6 +1602,7 @@ OBJS = \
typed-splay-tree.o \
unique-ptr-tests.o \
valtrack.o \
+ value-range.o \
value-prof.o \
var-tracking.o \
varasm.o \
@@ -2589,6 +2590,7 @@ GTFILES = $(CPPLIB_H) $(srcdir)/input.h $(srcdir)/coretypes.h \
$(srcdir)/target-globals.h \
$(srcdir)/ipa-predicate.h \
$(srcdir)/ipa-fnsummary.h \
+ $(srcdir)/value-range.h \
$(srcdir)/vtable-verify.c \
$(srcdir)/asan.c \
$(srcdir)/ubsan.c \
@@ -1717,6 +1717,7 @@ open_base_files (void)
"explow.h", "calls.h", "memmodel.h", "emit-rtl.h", "varasm.h",
"stmt.h", "expr.h", "alloc-pool.h", "cselib.h", "insn-addr.h",
"optabs.h", "libfuncs.h", "debug.h", "internal-fn.h", "gimple-fold.h",
+ "value-range.h",
"tree-eh.h", "gimple-iterator.h", "gimple-ssa.h", "tree-cfg.h",
"tree-vrp.h", "tree-phinodes.h", "ssa-iterators.h", "stringpool.h",
"tree-ssanames.h", "tree-ssa-loop.h", "tree-ssa-loop-ivopts.h",
@@ -68,10 +68,6 @@ along with GCC; see the file COPYING3. If not see
#include "builtins.h"
#include "range-op.h"
-static bool
-ranges_from_anti_range (const value_range *ar,
- value_range *vr0, value_range *vr1);
-
/* Set of SSA names found live during the RPO traversal of the function
for still active basic-blocks. */
static sbitmap *live;
@@ -111,11 +107,6 @@ value_range_equiv::set (tree min, tree max, bitmap equiv,
check ();
}
-value_range::value_range (tree min, tree max, value_range_kind kind)
-{
- set (min, max, kind);
-}
-
value_range_equiv::value_range_equiv (tree min, tree max, bitmap equiv,
value_range_kind kind)
{
@@ -129,21 +120,6 @@ value_range_equiv::value_range_equiv (const value_range &other)
set (other.min(), other.max (), NULL, other.kind ());
}
-value_range::value_range (tree type)
-{
- set_varying (type);
-}
-
-value_range::value_range (tree type,
- const wide_int &wmin, const wide_int &wmax,
- enum value_range_kind kind)
-{
- 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 (min, max, kind);
-}
-
/* Like set, but keep the equivalences in place. */
void
@@ -173,42 +149,6 @@ value_range_equiv::move (value_range_equiv *from)
from->m_equiv = NULL;
}
-/* Check the validity of the range. */
-
-void
-value_range::check ()
-{
- switch (m_kind)
- {
- case VR_RANGE:
- case VR_ANTI_RANGE:
- {
- int cmp;
-
- gcc_assert (m_min && m_max);
-
- gcc_assert (!TREE_OVERFLOW_P (m_min) && !TREE_OVERFLOW_P (m_max));
-
- /* Creating ~[-MIN, +MAX] is stupid because that would be
- the empty set. */
- if (INTEGRAL_TYPE_P (TREE_TYPE (m_min)) && m_kind == VR_ANTI_RANGE)
- gcc_assert (!vrp_val_is_min (m_min) || !vrp_val_is_max (m_max));
-
- cmp = compare_values (m_min, m_max);
- gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
- break;
- }
- case VR_UNDEFINED:
- gcc_assert (!min () && !max ());
- break;
- case VR_VARYING:
- gcc_assert (m_min && m_max);
- break;
- default:
- gcc_unreachable ();
- }
-}
-
void
value_range_equiv::check ()
{
@@ -222,22 +162,6 @@ value_range_equiv::check ()
}
}
-/* Equality operator. We purposely do not overload ==, to avoid
- confusion with the equality bitmap in the derived value_range
- class. */
-
-bool
-value_range::equal_p (const value_range &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));
-}
-
/* Return true if the bitmaps B1 and B2 are equal. */
static bool
@@ -262,58 +186,12 @@ value_range_equiv::equal_p (const value_range_equiv &other,
|| vrp_bitmap_equal_p (m_equiv, other.m_equiv)));
}
-/* Return TRUE if this is a symbolic range. */
-
-bool
-value_range::symbolic_p () const
-{
- return (!varying_p ()
- && !undefined_p ()
- && (!is_gimple_min_invariant (m_min)
- || !is_gimple_min_invariant (m_max)));
-}
-
-/* NOTE: This is not the inverse of symbolic_p because the range
- could also be varying or undefined. Ideally they should be inverse
- of each other, with varying only applying to symbolics. Varying of
- constants would be represented as [-MIN, +MAX]. */
-
-bool
-value_range::constant_p () const
-{
- return (!varying_p ()
- && !undefined_p ()
- && TREE_CODE (m_min) == INTEGER_CST
- && TREE_CODE (m_max) == INTEGER_CST);
-}
-
-void
-value_range::set_undefined ()
-{
- m_kind = VR_UNDEFINED;
- m_min = m_max = NULL;
-}
-
void
value_range_equiv::set_undefined ()
{
set (NULL, NULL, NULL, VR_UNDEFINED);
}
-void
-value_range::set_varying (tree type)
-{
- m_kind = VR_VARYING;
- if (supports_type_p (type))
- {
- m_min = vrp_val_min (type);
- m_max = vrp_val_max (type);
- }
- else
- /* We can't do anything range-wise with these types. */
- m_min = m_max = error_mark_node;
-}
-
void
value_range_equiv::set_varying (tree type)
{
@@ -321,14 +199,6 @@ value_range_equiv::set_varying (tree type)
equiv_clear ();
}
-/* Return TRUE if it is possible that range contains VAL. */
-
-bool
-value_range::may_contain_p (tree val) const
-{
- return value_inside_range (val) != 0;
-}
-
void
value_range_equiv::equiv_clear ()
{
@@ -356,98 +226,6 @@ value_range_equiv::equiv_add (const_tree var,
bitmap_ior_into (m_equiv, var_vr->m_equiv);
}
-/* If range is a singleton, place it in RESULT and return TRUE.
- Note: A singleton can be any gimple invariant, not just constants.
- So, [&x, &x] counts as a singleton. */
-
-bool
-value_range::singleton_p (tree *result) const
-{
- 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 vr0, vr1;
- ranges_from_anti_range (this, &vr0, &vr1);
- 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::type () const
-{
- gcc_checking_assert (m_min);
- return TREE_TYPE (min ());
-}
-
-void
-value_range::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 ())
- && 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::dump () const
-{
- dump (stderr);
-}
-
void
value_range_equiv::dump (FILE *file) const
{
@@ -486,27 +264,6 @@ dump_value_range (FILE *file, const value_range_equiv *vr)
vr->dump (file);
}
-void
-dump_value_range (FILE *file, const value_range *vr)
-{
- if (!vr)
- fprintf (file, "[]");
- else
- vr->dump (file);
-}
-
-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);
-}
-
DEBUG_FUNCTION void
debug (const value_range_equiv *vr)
{
@@ -567,58 +324,6 @@ static bitmap need_assert_for;
ASSERT_EXPRs for SSA name N_I should be inserted. */
static assert_locus **asserts_for;
-/* Return the maximum value for TYPE. */
-
-tree
-vrp_val_max (const_tree type)
-{
- if (INTEGRAL_TYPE_P (type))
- return TYPE_MAX_VALUE (type);
- if (POINTER_TYPE_P (type))
- {
- 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)
-{
- if (INTEGRAL_TYPE_P (type))
- return TYPE_MIN_VALUE (type);
- if (POINTER_TYPE_P (type))
- return build_zero_cst (const_cast<tree> (type));
- return NULL_TREE;
-}
-
-/* Return whether VAL is equal to the maximum value of its type.
- We can't do a simple equality comparison with TYPE_MAX_VALUE because
- C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
- is not == to the integer constant with the same value in the type. */
-
-bool
-vrp_val_is_max (const_tree val)
-{
- tree type_max = vrp_val_max (TREE_TYPE (val));
- return (val == type_max
- || (type_max != NULL_TREE
- && operand_equal_p (val, type_max, 0)));
-}
-
-/* Return whether VAL is equal to the minimum value of its type. */
-
-bool
-vrp_val_is_min (const_tree val)
-{
- tree type_min = vrp_val_min (TREE_TYPE (val));
- return (val == type_min
- || (type_min != NULL_TREE
- && operand_equal_p (val, type_min, 0)));
-}
-
/* VR_TYPE describes a range with mininum value *MIN and maximum
value *MAX. Restrict the range to the set of values that have
no bits set outside NONZERO_BITS. Update *MIN and *MAX and
@@ -691,184 +396,6 @@ intersect_range_with_nonzero_bits (enum value_range_kind vr_type,
return vr_type;
}
-
-/* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
- This means adjusting VRTYPE, MIN and MAX representing the case of a
- wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
- as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
- In corner cases where MAX+1 or MIN-1 wraps this will fall back
- to varying.
- This routine exists to ease canonicalization in the case where we
- extract ranges from var + CST op limit. */
-
-void
-value_range::set (tree min, tree max, value_range_kind kind)
-{
- /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */
- if (kind == VR_UNDEFINED)
- {
- set_undefined ();
- return;
- }
- else if (kind == VR_VARYING)
- {
- gcc_assert (TREE_TYPE (min) == TREE_TYPE (max));
- tree typ = TREE_TYPE (min);
- if (supports_type_p (typ))
- {
- gcc_assert (vrp_val_min (typ));
- gcc_assert (vrp_val_max (typ));
- }
- 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));
- 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));
- widest_int ub
- = constant_upper_bound_with_limit (wi::to_poly_widest (max),
- wi::to_widest (type_max));
- max = wide_int_to_tree (TREE_TYPE (max), ub);
- }
-
- /* Nothing to canonicalize for symbolic ranges. */
- if (TREE_CODE (min) != INTEGER_CST
- || TREE_CODE (max) != INTEGER_CST)
- {
- m_kind = kind;
- m_min = min;
- m_max = max;
- return;
- }
-
- /* Wrong order for min and max, to swap them and the VR type we need
- to adjust them. */
- if (tree_int_cst_lt (max, min))
- {
- tree one, tmp;
-
- /* For one bit precision if max < min, then the swapped
- range covers all values, so for VR_RANGE it is varying and
- for VR_ANTI_RANGE empty range, so drop to varying as well. */
- if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
- {
- set_varying (TREE_TYPE (min));
- return;
- }
-
- one = build_int_cst (TREE_TYPE (min), 1);
- tmp = int_const_binop (PLUS_EXPR, max, one);
- max = int_const_binop (MINUS_EXPR, min, one);
- min = tmp;
-
- /* There's one corner case, if we had [C+1, C] before we now have
- that again. But this represents an empty value range, so drop
- to varying in this case. */
- if (tree_int_cst_lt (max, min))
- {
- set_varying (TREE_TYPE (min));
- return;
- }
-
- kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
- }
-
- tree type = TREE_TYPE (min);
-
- /* Anti-ranges that can be represented as ranges should be so. */
- if (kind == VR_ANTI_RANGE)
- {
- /* For -fstrict-enums we may receive out-of-range ranges so consider
- values < -INF and values > INF as -INF/INF as well. */
- bool is_min = vrp_val_is_min (min);
- bool is_max = vrp_val_is_max (max);
-
- if (is_min && is_max)
- {
- /* We cannot deal with empty ranges, drop to varying.
- ??? This could be VR_UNDEFINED instead. */
- set_varying (type);
- return;
- }
- else if (TYPE_PRECISION (TREE_TYPE (min)) == 1
- && (is_min || is_max))
- {
- /* Non-empty boolean ranges can always be represented
- as a singleton range. */
- if (is_min)
- min = max = vrp_val_max (TREE_TYPE (min));
- else
- min = max = vrp_val_min (TREE_TYPE (min));
- kind = VR_RANGE;
- }
- else if (is_min)
- {
- tree one = build_int_cst (TREE_TYPE (max), 1);
- min = int_const_binop (PLUS_EXPR, max, one);
- max = vrp_val_max (TREE_TYPE (max));
- kind = VR_RANGE;
- }
- else if (is_max)
- {
- tree one = build_int_cst (TREE_TYPE (min), 1);
- max = int_const_binop (MINUS_EXPR, min, one);
- min = vrp_val_min (TREE_TYPE (min));
- kind = VR_RANGE;
- }
- }
-
- /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
-
- Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
- restrict those to a subset of what actually fits in the type.
- Instead use the extremes of the type precision which will allow
- compare_range_with_value() to check if a value is inside a range,
- whereas if we used TYPE_*_VAL, said function would just punt
- upon seeing a VARYING. */
- unsigned prec = TYPE_PRECISION (type);
- signop sign = TYPE_SIGN (type);
- if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign))
- && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign)))
- {
- if (kind == VR_RANGE)
- set_varying (type);
- else if (kind == VR_ANTI_RANGE)
- set_undefined ();
- else
- gcc_unreachable ();
- return;
- }
-
- /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky
- to make sure VRP iteration terminates, otherwise we can get into
- oscillations. */
-
- m_kind = kind;
- m_min = min;
- m_max = max;
- if (flag_checking)
- check ();
-}
-
-void
-value_range::set (tree val)
-{
- gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
- if (TREE_OVERFLOW_P (val))
- val = drop_tree_overflow (val);
- set (val, val);
-}
-
void
value_range_equiv::set (tree val)
{
@@ -878,43 +405,6 @@ value_range_equiv::set (tree val)
set (val, val);
}
-/* Set value range VR to a nonzero range of type TYPE. */
-
-void
-value_range::set_nonzero (tree type)
-{
- tree zero = build_int_cst (type, 0);
- set (zero, zero, VR_ANTI_RANGE);
-}
-
-/* Set value range VR to a ZERO range of type TYPE. */
-
-void
-value_range::set_zero (tree type)
-{
- set (build_int_cst (type, 0));
-}
-
-/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
-
-bool
-vrp_operand_equal_p (const_tree val1, const_tree val2)
-{
- if (val1 == val2)
- return true;
- if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
- return false;
- return true;
-}
-
-static bool
-range_has_numeric_bounds_p (const value_range *vr)
-{
- return (vr->min ()
- && TREE_CODE (vr->min ()) == INTEGER_CST
- && TREE_CODE (vr->max ()) == INTEGER_CST);
-}
-
/* Return true if max and min of VR are INTEGER_CST. It's not necessary
a singleton. */
@@ -1210,91 +700,17 @@ compare_values (tree val1, tree val2)
return compare_values_warnv (val1, val2, &sop);
}
+/* If BOUND will include a symbolic bound, adjust it accordingly,
+ otherwise leave it as is.
-/* 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_range::value_inside_range (tree val) const
-{
- int cmp1, cmp2;
+ CODE is the original operation that combined the bounds (PLUS_EXPR
+ or MINUS_EXPR).
- if (varying_p ())
- return 1;
+ TYPE is the type of the original operation.
- if (undefined_p ())
- return 0;
+ SYM_OPn is the symbolic for OPn if it has a symbolic.
- cmp1 = operand_less_p (val, m_min);
- if (cmp1 == -2)
- return -2;
- if (cmp1 == 1)
- return m_kind != VR_RANGE;
-
- cmp2 = operand_less_p (m_max, val);
- if (cmp2 == -2)
- return -2;
-
- if (m_kind == VR_RANGE)
- return !cmp2;
- else
- return !!cmp2;
-}
-
-/* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
- so that *VR0 U *VR1 == *AR. Returns true if that is possible,
- false otherwise. If *AR can be represented with a single range
- *VR1 will be VR_UNDEFINED. */
-
-static bool
-ranges_from_anti_range (const value_range *ar,
- value_range *vr0, value_range *vr1)
-{
- tree type = ar->type ();
-
- vr0->set_undefined ();
- vr1->set_undefined ();
-
- /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
- [A+1, +INF]. Not sure if this helps in practice, though. */
-
- if (ar->kind () != VR_ANTI_RANGE
- || TREE_CODE (ar->min ()) != INTEGER_CST
- || TREE_CODE (ar->max ()) != INTEGER_CST
- || !vrp_val_min (type)
- || !vrp_val_max (type))
- return false;
-
- if (tree_int_cst_lt (vrp_val_min (type), ar->min ()))
- vr0->set (vrp_val_min (type),
- wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1));
- if (tree_int_cst_lt (ar->max (), vrp_val_max (type)))
- vr1->set (wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1),
- vrp_val_max (type));
- if (vr0->undefined_p ())
- {
- *vr0 = *vr1;
- vr1->set_undefined ();
- }
-
- return !vr0->undefined_p ();
-}
-
-/* If BOUND will include a symbolic bound, adjust it accordingly,
- otherwise leave it as is.
-
- CODE is the original operation that combined the bounds (PLUS_EXPR
- or MINUS_EXPR).
-
- TYPE is the type of the original operation.
-
- SYM_OPn is the symbolic for OPn if it has a symbolic.
-
- NEG_OPn is TRUE if the OPn was negated. */
+ NEG_OPn is TRUE if the OPn was negated. */
static void
adjust_symbolic_bound (tree &bound, enum tree_code code, tree type,
@@ -5224,669 +4640,6 @@ vrp_prop::visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
}
-/* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
- { VR1TYPE, VR0MIN, VR0MAX } and store the result
- in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
- possible such range. The resulting range is not canonicalized. */
-
-static void
-union_ranges (enum value_range_kind *vr0type,
- tree *vr0min, tree *vr0max,
- enum value_range_kind vr1type,
- tree vr1min, tree vr1max)
-{
- 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)
- {
- /* [( )] */
- if (*vr0type == vr1type)
- /* Nothing to do for equal ranges. */
- ;
- else if ((*vr0type == VR_RANGE
- && vr1type == VR_ANTI_RANGE)
- || (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_RANGE))
- {
- /* For anti-range with range union the result is varying. */
- goto give_up;
- }
- else
- gcc_unreachable ();
- }
- else if (operand_less_p (*vr0max, vr1min) == 1
- || operand_less_p (vr1max, *vr0min) == 1)
- {
- /* [ ] ( ) or ( ) [ ]
- If the ranges have an empty intersection, result of the union
- operation is the anti-range or if both are anti-ranges
- it covers all. */
- if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_ANTI_RANGE)
- goto give_up;
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_RANGE)
- ;
- else if (*vr0type == VR_RANGE
- && vr1type == VR_ANTI_RANGE)
- {
- *vr0type = vr1type;
- *vr0min = vr1min;
- *vr0max = vr1max;
- }
- else if (*vr0type == VR_RANGE
- && vr1type == VR_RANGE)
- {
- /* The result is the convex hull of both ranges. */
- if (operand_less_p (*vr0max, vr1min) == 1)
- {
- /* If the result can be an anti-range, create one. */
- if (TREE_CODE (*vr0max) == INTEGER_CST
- && TREE_CODE (vr1min) == INTEGER_CST
- && vrp_val_is_min (*vr0min)
- && vrp_val_is_max (vr1max))
- {
- tree min = int_const_binop (PLUS_EXPR,
- *vr0max,
- build_int_cst (TREE_TYPE (*vr0max), 1));
- tree max = int_const_binop (MINUS_EXPR,
- vr1min,
- build_int_cst (TREE_TYPE (vr1min), 1));
- if (!operand_less_p (max, min))
- {
- *vr0type = VR_ANTI_RANGE;
- *vr0min = min;
- *vr0max = max;
- }
- else
- *vr0max = vr1max;
- }
- else
- *vr0max = vr1max;
- }
- else
- {
- /* If the result can be an anti-range, create one. */
- if (TREE_CODE (vr1max) == INTEGER_CST
- && TREE_CODE (*vr0min) == INTEGER_CST
- && vrp_val_is_min (vr1min)
- && vrp_val_is_max (*vr0max))
- {
- tree min = int_const_binop (PLUS_EXPR,
- vr1max,
- build_int_cst (TREE_TYPE (vr1max), 1));
- tree max = int_const_binop (MINUS_EXPR,
- *vr0min,
- build_int_cst (TREE_TYPE (*vr0min), 1));
- if (!operand_less_p (max, min))
- {
- *vr0type = VR_ANTI_RANGE;
- *vr0min = min;
- *vr0max = max;
- }
- else
- *vr0min = vr1min;
- }
- else
- *vr0min = vr1min;
- }
- }
- else
- gcc_unreachable ();
- }
- else if ((maxeq || cmpmax == 1)
- && (mineq || cmpmin == -1))
- {
- /* [ ( ) ] or [( ) ] or [ ( )] */
- if (*vr0type == VR_RANGE
- && vr1type == VR_RANGE)
- ;
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_ANTI_RANGE)
- {
- *vr0type = vr1type;
- *vr0min = vr1min;
- *vr0max = vr1max;
- }
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_RANGE)
- {
- /* Arbitrarily choose the right or left gap. */
- if (!mineq && TREE_CODE (vr1min) == INTEGER_CST)
- *vr0max = int_const_binop (MINUS_EXPR, vr1min,
- build_int_cst (TREE_TYPE (vr1min), 1));
- else if (!maxeq && TREE_CODE (vr1max) == INTEGER_CST)
- *vr0min = int_const_binop (PLUS_EXPR, vr1max,
- build_int_cst (TREE_TYPE (vr1max), 1));
- else
- goto give_up;
- }
- else if (*vr0type == VR_RANGE
- && vr1type == VR_ANTI_RANGE)
- /* The result covers everything. */
- goto give_up;
- else
- gcc_unreachable ();
- }
- else if ((maxeq || cmpmax == -1)
- && (mineq || cmpmin == 1))
- {
- /* ( [ ] ) or ([ ] ) or ( [ ]) */
- if (*vr0type == VR_RANGE
- && vr1type == VR_RANGE)
- {
- *vr0type = vr1type;
- *vr0min = vr1min;
- *vr0max = vr1max;
- }
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_ANTI_RANGE)
- ;
- else if (*vr0type == VR_RANGE
- && vr1type == VR_ANTI_RANGE)
- {
- *vr0type = VR_ANTI_RANGE;
- if (!mineq && TREE_CODE (*vr0min) == INTEGER_CST)
- {
- *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
- build_int_cst (TREE_TYPE (*vr0min), 1));
- *vr0min = vr1min;
- }
- else if (!maxeq && TREE_CODE (*vr0max) == INTEGER_CST)
- {
- *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
- build_int_cst (TREE_TYPE (*vr0max), 1));
- *vr0max = vr1max;
- }
- else
- goto give_up;
- }
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_RANGE)
- /* The result covers everything. */
- goto give_up;
- else
- gcc_unreachable ();
- }
- else if (cmpmin == -1
- && cmpmax == -1
- && (operand_less_p (vr1min, *vr0max) == 1
- || operand_equal_p (vr1min, *vr0max, 0)))
- {
- /* [ ( ] ) or [ ]( ) */
- if (*vr0type == VR_RANGE
- && vr1type == VR_RANGE)
- *vr0max = vr1max;
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_ANTI_RANGE)
- *vr0min = vr1min;
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_RANGE)
- {
- if (TREE_CODE (vr1min) == INTEGER_CST)
- *vr0max = int_const_binop (MINUS_EXPR, vr1min,
- build_int_cst (TREE_TYPE (vr1min), 1));
- else
- goto give_up;
- }
- else if (*vr0type == VR_RANGE
- && vr1type == VR_ANTI_RANGE)
- {
- if (TREE_CODE (*vr0max) == INTEGER_CST)
- {
- *vr0type = vr1type;
- *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
- build_int_cst (TREE_TYPE (*vr0max), 1));
- *vr0max = vr1max;
- }
- else
- goto give_up;
- }
- else
- gcc_unreachable ();
- }
- else if (cmpmin == 1
- && cmpmax == 1
- && (operand_less_p (*vr0min, vr1max) == 1
- || operand_equal_p (*vr0min, vr1max, 0)))
- {
- /* ( [ ) ] or ( )[ ] */
- if (*vr0type == VR_RANGE
- && vr1type == VR_RANGE)
- *vr0min = vr1min;
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_ANTI_RANGE)
- *vr0max = vr1max;
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_RANGE)
- {
- if (TREE_CODE (vr1max) == INTEGER_CST)
- *vr0min = int_const_binop (PLUS_EXPR, vr1max,
- build_int_cst (TREE_TYPE (vr1max), 1));
- else
- goto give_up;
- }
- else if (*vr0type == VR_RANGE
- && vr1type == VR_ANTI_RANGE)
- {
- if (TREE_CODE (*vr0min) == INTEGER_CST)
- {
- *vr0type = vr1type;
- *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
- build_int_cst (TREE_TYPE (*vr0min), 1));
- *vr0min = vr1min;
- }
- else
- goto give_up;
- }
- else
- gcc_unreachable ();
- }
- else
- goto give_up;
-
- return;
-
-give_up:
- *vr0type = VR_VARYING;
- *vr0min = NULL_TREE;
- *vr0max = NULL_TREE;
-}
-
-/* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
- { VR1TYPE, VR0MIN, VR0MAX } and store the result
- in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
- possible such range. The resulting range is not canonicalized. */
-
-static void
-intersect_ranges (enum value_range_kind *vr0type,
- tree *vr0min, tree *vr0max,
- enum value_range_kind vr1type,
- tree vr1min, tree vr1max)
-{
- bool mineq = vrp_operand_equal_p (*vr0min, vr1min);
- bool maxeq = vrp_operand_equal_p (*vr0max, vr1max);
-
- /* [] is vr0, () is vr1 in the following classification comments. */
- if (mineq && maxeq)
- {
- /* [( )] */
- if (*vr0type == vr1type)
- /* Nothing to do for equal ranges. */
- ;
- else if ((*vr0type == VR_RANGE
- && vr1type == VR_ANTI_RANGE)
- || (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_RANGE))
- {
- /* For anti-range with range intersection the result is empty. */
- *vr0type = VR_UNDEFINED;
- *vr0min = NULL_TREE;
- *vr0max = NULL_TREE;
- }
- else
- gcc_unreachable ();
- }
- else if (operand_less_p (*vr0max, vr1min) == 1
- || operand_less_p (vr1max, *vr0min) == 1)
- {
- /* [ ] ( ) or ( ) [ ]
- If the ranges have an empty intersection, the result of the
- intersect operation is the range for intersecting an
- anti-range with a range or empty when intersecting two ranges. */
- if (*vr0type == VR_RANGE
- && vr1type == VR_ANTI_RANGE)
- ;
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_RANGE)
- {
- *vr0type = vr1type;
- *vr0min = vr1min;
- *vr0max = vr1max;
- }
- else if (*vr0type == VR_RANGE
- && vr1type == VR_RANGE)
- {
- *vr0type = VR_UNDEFINED;
- *vr0min = NULL_TREE;
- *vr0max = NULL_TREE;
- }
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_ANTI_RANGE)
- {
- /* If the anti-ranges are adjacent to each other merge them. */
- if (TREE_CODE (*vr0max) == INTEGER_CST
- && TREE_CODE (vr1min) == INTEGER_CST
- && operand_less_p (*vr0max, vr1min) == 1
- && integer_onep (int_const_binop (MINUS_EXPR,
- vr1min, *vr0max)))
- *vr0max = vr1max;
- else if (TREE_CODE (vr1max) == INTEGER_CST
- && TREE_CODE (*vr0min) == INTEGER_CST
- && operand_less_p (vr1max, *vr0min) == 1
- && integer_onep (int_const_binop (MINUS_EXPR,
- *vr0min, vr1max)))
- *vr0min = vr1min;
- /* Else arbitrarily take VR0. */
- }
- }
- else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1)
- && (mineq || operand_less_p (*vr0min, vr1min) == 1))
- {
- /* [ ( ) ] or [( ) ] or [ ( )] */
- if (*vr0type == VR_RANGE
- && vr1type == VR_RANGE)
- {
- /* If both are ranges the result is the inner one. */
- *vr0type = vr1type;
- *vr0min = vr1min;
- *vr0max = vr1max;
- }
- else if (*vr0type == VR_RANGE
- && vr1type == VR_ANTI_RANGE)
- {
- /* Choose the right gap if the left one is empty. */
- if (mineq)
- {
- if (TREE_CODE (vr1max) != INTEGER_CST)
- *vr0min = vr1max;
- else if (TYPE_PRECISION (TREE_TYPE (vr1max)) == 1
- && !TYPE_UNSIGNED (TREE_TYPE (vr1max)))
- *vr0min
- = int_const_binop (MINUS_EXPR, vr1max,
- build_int_cst (TREE_TYPE (vr1max), -1));
- else
- *vr0min
- = int_const_binop (PLUS_EXPR, vr1max,
- build_int_cst (TREE_TYPE (vr1max), 1));
- }
- /* Choose the left gap if the right one is empty. */
- else if (maxeq)
- {
- if (TREE_CODE (vr1min) != INTEGER_CST)
- *vr0max = vr1min;
- else if (TYPE_PRECISION (TREE_TYPE (vr1min)) == 1
- && !TYPE_UNSIGNED (TREE_TYPE (vr1min)))
- *vr0max
- = int_const_binop (PLUS_EXPR, vr1min,
- build_int_cst (TREE_TYPE (vr1min), -1));
- else
- *vr0max
- = int_const_binop (MINUS_EXPR, vr1min,
- build_int_cst (TREE_TYPE (vr1min), 1));
- }
- /* Choose the anti-range if the range is effectively varying. */
- else if (vrp_val_is_min (*vr0min)
- && vrp_val_is_max (*vr0max))
- {
- *vr0type = vr1type;
- *vr0min = vr1min;
- *vr0max = vr1max;
- }
- /* Else choose the range. */
- }
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_ANTI_RANGE)
- /* If both are anti-ranges the result is the outer one. */
- ;
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_RANGE)
- {
- /* The intersection is empty. */
- *vr0type = VR_UNDEFINED;
- *vr0min = NULL_TREE;
- *vr0max = NULL_TREE;
- }
- else
- gcc_unreachable ();
- }
- else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
- && (mineq || operand_less_p (vr1min, *vr0min) == 1))
- {
- /* ( [ ] ) or ([ ] ) or ( [ ]) */
- if (*vr0type == VR_RANGE
- && vr1type == VR_RANGE)
- /* Choose the inner range. */
- ;
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_RANGE)
- {
- /* Choose the right gap if the left is empty. */
- if (mineq)
- {
- *vr0type = VR_RANGE;
- if (TREE_CODE (*vr0max) != INTEGER_CST)
- *vr0min = *vr0max;
- else if (TYPE_PRECISION (TREE_TYPE (*vr0max)) == 1
- && !TYPE_UNSIGNED (TREE_TYPE (*vr0max)))
- *vr0min
- = int_const_binop (MINUS_EXPR, *vr0max,
- build_int_cst (TREE_TYPE (*vr0max), -1));
- else
- *vr0min
- = int_const_binop (PLUS_EXPR, *vr0max,
- build_int_cst (TREE_TYPE (*vr0max), 1));
- *vr0max = vr1max;
- }
- /* Choose the left gap if the right is empty. */
- else if (maxeq)
- {
- *vr0type = VR_RANGE;
- if (TREE_CODE (*vr0min) != INTEGER_CST)
- *vr0max = *vr0min;
- else if (TYPE_PRECISION (TREE_TYPE (*vr0min)) == 1
- && !TYPE_UNSIGNED (TREE_TYPE (*vr0min)))
- *vr0max
- = int_const_binop (PLUS_EXPR, *vr0min,
- build_int_cst (TREE_TYPE (*vr0min), -1));
- else
- *vr0max
- = int_const_binop (MINUS_EXPR, *vr0min,
- build_int_cst (TREE_TYPE (*vr0min), 1));
- *vr0min = vr1min;
- }
- /* Choose the anti-range if the range is effectively varying. */
- else if (vrp_val_is_min (vr1min)
- && vrp_val_is_max (vr1max))
- ;
- /* Choose the anti-range if it is ~[0,0], that range is special
- enough to special case when vr1's range is relatively wide.
- At least for types bigger than int - this covers pointers
- and arguments to functions like ctz. */
- else if (*vr0min == *vr0max
- && integer_zerop (*vr0min)
- && ((TYPE_PRECISION (TREE_TYPE (*vr0min))
- >= TYPE_PRECISION (integer_type_node))
- || POINTER_TYPE_P (TREE_TYPE (*vr0min)))
- && TREE_CODE (vr1max) == INTEGER_CST
- && TREE_CODE (vr1min) == INTEGER_CST
- && (wi::clz (wi::to_wide (vr1max) - wi::to_wide (vr1min))
- < TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2))
- ;
- /* Else choose the range. */
- else
- {
- *vr0type = vr1type;
- *vr0min = vr1min;
- *vr0max = vr1max;
- }
- }
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_ANTI_RANGE)
- {
- /* If both are anti-ranges the result is the outer one. */
- *vr0type = vr1type;
- *vr0min = vr1min;
- *vr0max = vr1max;
- }
- else if (vr1type == VR_ANTI_RANGE
- && *vr0type == VR_RANGE)
- {
- /* The intersection is empty. */
- *vr0type = VR_UNDEFINED;
- *vr0min = NULL_TREE;
- *vr0max = NULL_TREE;
- }
- else
- gcc_unreachable ();
- }
- else if ((operand_less_p (vr1min, *vr0max) == 1
- || operand_equal_p (vr1min, *vr0max, 0))
- && operand_less_p (*vr0min, vr1min) == 1)
- {
- /* [ ( ] ) or [ ]( ) */
- if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_ANTI_RANGE)
- *vr0max = vr1max;
- else if (*vr0type == VR_RANGE
- && vr1type == VR_RANGE)
- *vr0min = vr1min;
- else if (*vr0type == VR_RANGE
- && vr1type == VR_ANTI_RANGE)
- {
- if (TREE_CODE (vr1min) == INTEGER_CST)
- *vr0max = int_const_binop (MINUS_EXPR, vr1min,
- build_int_cst (TREE_TYPE (vr1min), 1));
- else
- *vr0max = vr1min;
- }
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_RANGE)
- {
- *vr0type = VR_RANGE;
- if (TREE_CODE (*vr0max) == INTEGER_CST)
- *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
- build_int_cst (TREE_TYPE (*vr0max), 1));
- else
- *vr0min = *vr0max;
- *vr0max = vr1max;
- }
- else
- gcc_unreachable ();
- }
- else if ((operand_less_p (*vr0min, vr1max) == 1
- || operand_equal_p (*vr0min, vr1max, 0))
- && operand_less_p (vr1min, *vr0min) == 1)
- {
- /* ( [ ) ] or ( )[ ] */
- if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_ANTI_RANGE)
- *vr0min = vr1min;
- else if (*vr0type == VR_RANGE
- && vr1type == VR_RANGE)
- *vr0max = vr1max;
- else if (*vr0type == VR_RANGE
- && vr1type == VR_ANTI_RANGE)
- {
- if (TREE_CODE (vr1max) == INTEGER_CST)
- *vr0min = int_const_binop (PLUS_EXPR, vr1max,
- build_int_cst (TREE_TYPE (vr1max), 1));
- else
- *vr0min = vr1max;
- }
- else if (*vr0type == VR_ANTI_RANGE
- && vr1type == VR_RANGE)
- {
- *vr0type = VR_RANGE;
- if (TREE_CODE (*vr0min) == INTEGER_CST)
- *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
- build_int_cst (TREE_TYPE (*vr0min), 1));
- else
- *vr0max = *vr0min;
- *vr0min = vr1min;
- }
- else
- gcc_unreachable ();
- }
-
- /* 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
- in which case we choose that. */
- if (vr1type == VR_RANGE
- && is_gimple_min_invariant (vr1min)
- && vrp_operand_equal_p (vr1min, vr1max))
- {
- *vr0type = vr1type;
- *vr0min = vr1min;
- *vr0max = vr1max;
- }
-}
-
-
-/* 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. */
-
-value_range
-value_range::intersect_helper (const value_range *vr0, const value_range *vr1)
-{
- /* If either range is VR_VARYING the other one wins. */
- 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->undefined_p ())
- return *vr0;
- if (vr1->undefined_p ())
- return *vr1;
-
- value_range_kind vr0kind = vr0->kind ();
- tree vr0min = vr0->min ();
- tree vr0max = vr0->max ();
- intersect_ranges (&vr0kind, &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. Work on a temporary so we can
- fall back to vr0 when this turns things to varying. */
- value_range tem;
- if (vr0kind == VR_UNDEFINED)
- tem.set_undefined ();
- else if (vr0kind == VR_VARYING)
- tem.set_varying (vr0->type ());
- else
- tem.set (vr0min, vr0max, vr0kind);
- /* If that failed, use the saved original VR0. */
- if (tem.varying_p ())
- return *vr0;
-
- return tem;
-}
-
-void
-value_range::intersect (const value_range *other)
-{
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- 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");
- }
-
- *this = intersect_helper (this, other);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "to\n ");
- dump_value_range (dump_file, this);
- fprintf (dump_file, "\n");
- }
-}
-
void
value_range_equiv::intersect (const value_range_equiv *other)
{
@@ -5936,79 +4689,6 @@ value_range_equiv::intersect (const value_range_equiv *other)
}
}
-/* 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
-value_range::union_helper (const value_range *vr0, const value_range *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 vr0kind = vr0->kind ();
- tree vr0min = vr0->min ();
- tree vr0max = vr0->max ();
- union_ranges (&vr0kind, &vr0min, &vr0max,
- vr1->kind (), vr1->min (), vr1->max ());
-
- /* Work on a temporary so we can still use vr0 when union returns varying. */
- value_range tem;
- if (vr0kind == VR_UNDEFINED)
- tem.set_undefined ();
- else if (vr0kind == VR_VARYING)
- tem.set_varying (vr0->type ());
- else
- tem.set (vr0min, vr0max, vr0kind);
-
- /* 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. */
-
-void
-value_range::union_ (const value_range *other)
-{
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Meeting\n ");
- dump_value_range (dump_file, this);
- fprintf (dump_file, "\nand\n ");
- dump_value_range (dump_file, other);
- fprintf (dump_file, "\n");
- }
-
- *this = union_helper (this, other);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "to\n ");
- dump_value_range (dump_file, this);
- fprintf (dump_file, "\n");
- }
-}
-
void
value_range_equiv::union_ (const value_range_equiv *other)
{
@@ -6046,222 +4726,6 @@ value_range_equiv::union_ (const value_range_equiv *other)
}
}
-/* Normalize addresses into constants. */
-
-value_range
-value_range::normalize_addresses () const
-{
- if (undefined_p ())
- return *this;
-
- if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
- return *this;
-
- if (!range_includes_zero_p (this))
- {
- gcc_checking_assert (TREE_CODE (m_min) == ADDR_EXPR
- || TREE_CODE (m_max) == ADDR_EXPR);
- return range_nonzero (type ());
- }
- return value_range (type ());
-}
-
-/* Normalize symbolics and addresses into constants. */
-
-value_range
-value_range::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 var;
- var.set_varying (ttype);
- return var;
- }
- if (kind () == VR_RANGE)
- {
- // [SYM, NUM] -> [-MIN, NUM]
- if (min_symbolic)
- return value_range (vrp_val_min (ttype), max ());
- // [NUM, SYM] -> [NUM, +MAX]
- return value_range (min (), vrp_val_max (ttype));
- }
- 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 (n, vrp_val_max (ttype));
- }
- value_range var;
- var.set_varying (ttype);
- return var;
- }
- // ~[NUM, SYM] -> [-MIN, NUM - 1]
- if (!vrp_val_is_min (min ()))
- {
- tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1);
- return value_range (vrp_val_min (ttype), n);
- }
- value_range var;
- var.set_varying (ttype);
- return var;
-}
-
-/* Return the number of sub-ranges in a range. */
-
-unsigned
-value_range::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) || vrp_val_is_max (m_max))
- return 1;
- return 2;
- }
- return 1;
-}
-
-/* Return the lower bound for a sub-range. PAIR is the sub-range in
- question. */
-
-wide_int
-value_range::lower_bound (unsigned pair) const
-{
- 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)
- {
- tree typ = type ();
- if (pair == 1 || vrp_val_is_min (m_min))
- t = wide_int_to_tree (typ, wi::to_wide (m_max) + 1);
- else
- t = vrp_val_min (typ);
- }
- 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::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)
- {
- tree typ = type ();
- if (pair == 1 || vrp_val_is_min (m_min))
- t = vrp_val_max (typ);
- 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::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::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::invert ()
-{
- /* We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
- create non-canonical ranges. Use the constructors instead. */
- if (m_kind == VR_RANGE)
- *this = value_range (m_min, m_max, VR_ANTI_RANGE);
- else if (m_kind == VR_ANTI_RANGE)
- *this = value_range (m_min, m_max);
- else
- gcc_unreachable ();
-}
-
-/* Range union, but for references. */
-
-void
-value_range::union_ (const value_range &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::intersect (const value_range &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;
-}
-
-bool
-value_range::operator== (const value_range &r) const
-{
- return equal_p (r);
-}
-
/* Visit all arguments for PHI node PHI that flow through executable
edges. If a valid value range can be derived from all the incoming
value ranges, set a new range for the LHS of PHI. */
@@ -20,103 +20,7 @@ along with GCC; see the file COPYING3. If not see
#ifndef GCC_TREE_VRP_H
#define GCC_TREE_VRP_H
-/* Types of value ranges. */
-enum value_range_kind
-{
- /* Empty range. */
- VR_UNDEFINED,
- /* Range spans the entire domain. */
- VR_VARYING,
- /* Range is [MIN, MAX]. */
- VR_RANGE,
- /* Range is ~[MIN, MAX]. */
- VR_ANTI_RANGE,
- /* Range is a nice guy. */
- VR_LAST
-};
-
-/* Range of values that can be associated with an SSA_NAME after VRP
- has executed. */
-class GTY((for_user)) value_range
-{
- friend void range_tests ();
-public:
- value_range ();
- value_range (tree, tree, value_range_kind = VR_RANGE);
- value_range (tree type, const wide_int &, const wide_int &,
- value_range_kind = VR_RANGE);
- value_range (tree type);
-
- void set (tree, tree, value_range_kind = VR_RANGE);
- void set (tree);
- void set_nonzero (tree);
- void set_zero (tree);
-
- enum value_range_kind kind () const;
- tree min () const;
- tree max () const;
-
- /* Types of value ranges. */
- bool symbolic_p () const;
- bool constant_p () const;
- bool undefined_p () const;
- bool varying_p () const;
- void set_varying (tree type);
- void set_undefined ();
-
- void union_ (const value_range *);
- void intersect (const value_range *);
- void union_ (const value_range &);
- void intersect (const value_range &);
-
- bool operator== (const value_range &) const;
- bool operator!= (const value_range &) const /* = delete */;
- bool equal_p (const value_range &) const;
-
- /* Misc methods. */
- tree type () const;
- bool may_contain_p (tree) const;
- bool zero_p () const;
- bool nonzero_p () const;
- bool singleton_p (tree *result = NULL) const;
- void dump (FILE *) const;
- void dump () const;
-
- static bool supports_type_p (tree);
- value_range normalize_symbolics () const;
- value_range normalize_addresses () const;
-
- static const unsigned int m_max_pairs = 2;
- bool contains_p (tree) const;
- unsigned num_pairs () const;
- wide_int lower_bound (unsigned = 0) const;
- wide_int upper_bound (unsigned) const;
- wide_int upper_bound () const;
- void invert ();
-
-protected:
- void check ();
- static value_range union_helper (const value_range *, const value_range *);
- static value_range intersect_helper (const value_range *,
- const value_range *);
-
- enum value_range_kind m_kind;
-
- tree m_min;
- tree m_max;
-
- friend void gt_ggc_mx_value_range (void *);
- friend void gt_pch_p_11value_range (void *, void *,
- gt_pointer_operator, void *);
- friend void gt_pch_nx_value_range (void *);
- friend void gt_ggc_mx (value_range &);
- friend void gt_ggc_mx (value_range *&);
- friend void gt_pch_nx (value_range &);
- friend void gt_pch_nx (value_range *, gt_pointer_operator, void *);
-
-private:
- int value_inside_range (tree) const;
-};
+#include "value-range.h"
/* Note value_range_equiv cannot currently be used with GC memory,
only value_range is fully set up for this. */
@@ -173,13 +77,6 @@ class GTY((user)) value_range_equiv : public value_range
bitmap m_equiv;
};
-inline
-value_range::value_range ()
-{
- m_kind = VR_UNDEFINED;
- m_min = m_max = NULL;
-}
-
inline
value_range_equiv::value_range_equiv ()
: value_range ()
@@ -187,64 +84,13 @@ value_range_equiv::value_range_equiv ()
m_equiv = NULL;
}
-/* Return the kind of this range. */
-
-inline value_range_kind
-value_range::kind () const
-{
- return m_kind;
-}
-
inline bitmap
value_range_equiv::equiv () const
{
return m_equiv;
}
-/* Return the lower bound. */
-
-inline tree
-value_range::min () const
-{
- return m_min;
-}
-
-/* Return the upper bound. */
-
-inline tree
-value_range::max () const
-{
- return m_max;
-}
-
-/* Return TRUE if range spans the entire possible domain. */
-
-inline bool
-value_range::varying_p () const
-{
- return m_kind == VR_VARYING;
-}
-
-/* Return TRUE if range is undefined (essentially the empty set). */
-
-inline bool
-value_range::undefined_p () const
-{
- return m_kind == VR_UNDEFINED;
-}
-
-/* Return TRUE if range is the constant zero. */
-
-inline bool
-value_range::zero_p () const
-{
- return (m_kind == VR_RANGE
- && integer_zerop (m_min)
- && integer_zerop (m_max));
-}
-
extern void dump_value_range (FILE *, const value_range_equiv *);
-extern void dump_value_range (FILE *, const value_range *);
struct assert_info
{
@@ -261,17 +107,6 @@ struct assert_info
tree expr;
};
-// Return true if TYPE is a valid type for value_range to operate on.
-// Otherwise return FALSE.
-
-inline bool
-value_range::supports_type_p (tree type)
-{
- if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)))
- return type;
- return false;
-}
-
extern void register_edge_assert_for (tree, edge, enum tree_code,
tree, tree, vec<assert_info> &);
extern bool stmt_interesting_for_vrp (gimple *);
@@ -282,18 +117,12 @@ extern bool range_int_cst_p (const value_range *);
extern int compare_values (tree, tree);
extern int compare_values_warnv (tree, tree, bool *);
extern int operand_less_p (tree, tree);
-extern bool vrp_val_is_min (const_tree);
-extern bool vrp_val_is_max (const_tree);
-
-extern tree vrp_val_min (const_tree);
-extern tree vrp_val_max (const_tree);
void range_fold_unary_expr (value_range *, enum tree_code, tree type,
const value_range *, tree op0_type);
void range_fold_binary_expr (value_range *, enum tree_code, tree type,
const value_range *, const value_range *);
-extern bool vrp_operand_equal_p (const_tree, const_tree);
extern enum value_range_kind intersect_range_with_nonzero_bits
(enum value_range_kind, wide_int *, wide_int *, const wide_int &, signop);
@@ -304,35 +133,4 @@ extern tree get_single_symbol (tree, bool *, tree *);
extern void maybe_set_nonzero_bits (edge, tree);
extern value_range_kind determine_value_range (tree, wide_int *, wide_int *);
-/* Return TRUE if range is nonzero. */
-
-inline bool
-value_range::nonzero_p () const
-{
- if (m_kind == VR_ANTI_RANGE
- && !TYPE_UNSIGNED (type ())
- && integer_zerop (m_min)
- && integer_zerop (m_max))
- return true;
-
- return (m_kind == VR_RANGE
- && TYPE_UNSIGNED (type ())
- && integer_onep (m_min)
- && vrp_val_is_max (m_max));
-}
-
-/* Return TRUE if *VR includes the value zero. */
-
-inline bool
-range_includes_zero_p (const value_range *vr)
-{
- if (vr->undefined_p ())
- return false;
-
- if (vr->varying_p ())
- return true;
-
- return vr->may_contain_p (build_zero_cst (vr->type ()));
-}
-
#endif /* GCC_TREE_VRP_H */
new file mode 100644
@@ -0,0 +1,1541 @@
+/* Support routines for value ranges.
+ Copyright (C) 2019 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "gimple.h"
+#include "ssa.h"
+#include "tree-pretty-print.h"
+#include "fold-const.h"
+
+value_range::value_range (tree min, tree max, value_range_kind kind)
+{
+ set (min, max, kind);
+}
+
+value_range::value_range (tree type)
+{
+ set_varying (type);
+}
+
+value_range::value_range (tree type,
+ const wide_int &wmin, const wide_int &wmax,
+ enum value_range_kind kind)
+{
+ 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 (min, max, kind);
+}
+
+void
+value_range::set_undefined ()
+{
+ m_kind = VR_UNDEFINED;
+ m_min = m_max = NULL;
+}
+
+void
+value_range::set_varying (tree type)
+{
+ m_kind = VR_VARYING;
+ if (supports_type_p (type))
+ {
+ m_min = vrp_val_min (type);
+ m_max = vrp_val_max (type);
+ }
+ else
+ /* We can't do anything range-wise with these types. */
+ m_min = m_max = error_mark_node;
+}
+
+/* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
+ This means adjusting VRTYPE, MIN and MAX representing the case of a
+ wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
+ as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
+ In corner cases where MAX+1 or MIN-1 wraps this will fall back
+ to varying.
+ This routine exists to ease canonicalization in the case where we
+ extract ranges from var + CST op limit. */
+
+void
+value_range::set (tree min, tree max, value_range_kind kind)
+{
+ /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */
+ if (kind == VR_UNDEFINED)
+ {
+ set_undefined ();
+ return;
+ }
+ else if (kind == VR_VARYING)
+ {
+ gcc_assert (TREE_TYPE (min) == TREE_TYPE (max));
+ tree typ = TREE_TYPE (min);
+ if (supports_type_p (typ))
+ {
+ gcc_assert (vrp_val_min (typ));
+ gcc_assert (vrp_val_max (typ));
+ }
+ 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));
+ 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));
+ widest_int ub
+ = constant_upper_bound_with_limit (wi::to_poly_widest (max),
+ wi::to_widest (type_max));
+ max = wide_int_to_tree (TREE_TYPE (max), ub);
+ }
+
+ /* Nothing to canonicalize for symbolic ranges. */
+ if (TREE_CODE (min) != INTEGER_CST
+ || TREE_CODE (max) != INTEGER_CST)
+ {
+ m_kind = kind;
+ m_min = min;
+ m_max = max;
+ return;
+ }
+
+ /* Wrong order for min and max, to swap them and the VR type we need
+ to adjust them. */
+ if (tree_int_cst_lt (max, min))
+ {
+ tree one, tmp;
+
+ /* For one bit precision if max < min, then the swapped
+ range covers all values, so for VR_RANGE it is varying and
+ for VR_ANTI_RANGE empty range, so drop to varying as well. */
+ if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
+ {
+ set_varying (TREE_TYPE (min));
+ return;
+ }
+
+ one = build_int_cst (TREE_TYPE (min), 1);
+ tmp = int_const_binop (PLUS_EXPR, max, one);
+ max = int_const_binop (MINUS_EXPR, min, one);
+ min = tmp;
+
+ /* There's one corner case, if we had [C+1, C] before we now have
+ that again. But this represents an empty value range, so drop
+ to varying in this case. */
+ if (tree_int_cst_lt (max, min))
+ {
+ set_varying (TREE_TYPE (min));
+ return;
+ }
+
+ kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
+ }
+
+ tree type = TREE_TYPE (min);
+
+ /* Anti-ranges that can be represented as ranges should be so. */
+ if (kind == VR_ANTI_RANGE)
+ {
+ /* For -fstrict-enums we may receive out-of-range ranges so consider
+ values < -INF and values > INF as -INF/INF as well. */
+ bool is_min = vrp_val_is_min (min);
+ bool is_max = vrp_val_is_max (max);
+
+ if (is_min && is_max)
+ {
+ /* We cannot deal with empty ranges, drop to varying.
+ ??? This could be VR_UNDEFINED instead. */
+ set_varying (type);
+ return;
+ }
+ else if (TYPE_PRECISION (TREE_TYPE (min)) == 1
+ && (is_min || is_max))
+ {
+ /* Non-empty boolean ranges can always be represented
+ as a singleton range. */
+ if (is_min)
+ min = max = vrp_val_max (TREE_TYPE (min));
+ else
+ min = max = vrp_val_min (TREE_TYPE (min));
+ kind = VR_RANGE;
+ }
+ else if (is_min)
+ {
+ tree one = build_int_cst (TREE_TYPE (max), 1);
+ min = int_const_binop (PLUS_EXPR, max, one);
+ max = vrp_val_max (TREE_TYPE (max));
+ kind = VR_RANGE;
+ }
+ else if (is_max)
+ {
+ tree one = build_int_cst (TREE_TYPE (min), 1);
+ max = int_const_binop (MINUS_EXPR, min, one);
+ min = vrp_val_min (TREE_TYPE (min));
+ kind = VR_RANGE;
+ }
+ }
+
+ /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
+
+ Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
+ restrict those to a subset of what actually fits in the type.
+ Instead use the extremes of the type precision which will allow
+ compare_range_with_value() to check if a value is inside a range,
+ whereas if we used TYPE_*_VAL, said function would just punt
+ upon seeing a VARYING. */
+ unsigned prec = TYPE_PRECISION (type);
+ signop sign = TYPE_SIGN (type);
+ if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign))
+ && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign)))
+ {
+ if (kind == VR_RANGE)
+ set_varying (type);
+ else if (kind == VR_ANTI_RANGE)
+ set_undefined ();
+ else
+ gcc_unreachable ();
+ return;
+ }
+
+ /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky
+ to make sure VRP iteration terminates, otherwise we can get into
+ oscillations. */
+
+ m_kind = kind;
+ m_min = min;
+ m_max = max;
+ if (flag_checking)
+ check ();
+}
+
+void
+value_range::set (tree val)
+{
+ gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
+ if (TREE_OVERFLOW_P (val))
+ val = drop_tree_overflow (val);
+ set (val, val);
+}
+
+/* Set value range VR to a nonzero range of type TYPE. */
+
+void
+value_range::set_nonzero (tree type)
+{
+ tree zero = build_int_cst (type, 0);
+ set (zero, zero, VR_ANTI_RANGE);
+}
+
+/* Set value range VR to a ZERO range of type TYPE. */
+
+void
+value_range::set_zero (tree type)
+{
+ set (build_int_cst (type, 0));
+}
+
+/* Check the validity of the range. */
+
+void
+value_range::check ()
+{
+ switch (m_kind)
+ {
+ case VR_RANGE:
+ case VR_ANTI_RANGE:
+ {
+ 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));
+
+ int 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 ();
+ }
+}
+
+/* Return the number of sub-ranges in a range. */
+
+unsigned
+value_range::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) || vrp_val_is_max (m_max))
+ return 1;
+ return 2;
+ }
+ return 1;
+}
+
+/* Return the lower bound for a sub-range. PAIR is the sub-range in
+ question. */
+
+wide_int
+value_range::lower_bound (unsigned pair) const
+{
+ 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)
+ {
+ tree typ = type ();
+ if (pair == 1 || vrp_val_is_min (m_min))
+ t = wide_int_to_tree (typ, wi::to_wide (m_max) + 1);
+ else
+ t = vrp_val_min (typ);
+ }
+ 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::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)
+ {
+ tree typ = type ();
+ if (pair == 1 || vrp_val_is_min (m_min))
+ t = vrp_val_max (typ);
+ 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::upper_bound () const
+{
+ unsigned pairs = num_pairs ();
+ gcc_checking_assert (pairs > 0);
+ return upper_bound (pairs - 1);
+}
+
+bool
+value_range::equal_p (const value_range &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));
+}
+
+bool
+value_range::operator== (const value_range &r) const
+{
+ return equal_p (r);
+}
+
+/* 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. */
+/* Return TRUE if this is a symbolic range. */
+
+bool
+value_range::symbolic_p () const
+{
+ return (!varying_p ()
+ && !undefined_p ()
+ && (!is_gimple_min_invariant (m_min)
+ || !is_gimple_min_invariant (m_max)));
+}
+
+/* NOTE: This is not the inverse of symbolic_p because the range
+ could also be varying or undefined. Ideally they should be inverse
+ of each other, with varying only applying to symbolics. Varying of
+ constants would be represented as [-MIN, +MAX]. */
+
+bool
+value_range::constant_p () const
+{
+ return (!varying_p ()
+ && !undefined_p ()
+ && TREE_CODE (m_min) == INTEGER_CST
+ && TREE_CODE (m_max) == INTEGER_CST);
+}
+
+bool
+value_range::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 vr0, vr1;
+ ranges_from_anti_range (this, &vr0, &vr1);
+ 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;
+}
+
+/* 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_range::value_inside_range (tree val) const
+{
+ int cmp1, cmp2;
+
+ 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 m_kind != VR_RANGE;
+
+ cmp2 = operand_less_p (m_max, val);
+ if (cmp2 == -2)
+ return -2;
+
+ if (m_kind == VR_RANGE)
+ return !cmp2;
+ else
+ return !!cmp2;
+}
+
+/* Return TRUE if it is possible that range contains VAL. */
+
+bool
+value_range::may_contain_p (tree val) const
+{
+ return value_inside_range (val) != 0;
+}
+
+/* Return TRUE if range contains INTEGER_CST. */
+
+bool
+value_range::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;
+}
+
+/* Normalize addresses into constants. */
+
+value_range
+value_range::normalize_addresses () const
+{
+ if (undefined_p ())
+ return *this;
+
+ if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
+ return *this;
+
+ if (!range_includes_zero_p (this))
+ {
+ gcc_checking_assert (TREE_CODE (m_min) == ADDR_EXPR
+ || TREE_CODE (m_max) == ADDR_EXPR);
+ return range_nonzero (type ());
+ }
+ return value_range (type ());
+}
+
+/* Normalize symbolics and addresses into constants. */
+
+value_range
+value_range::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 var;
+ var.set_varying (ttype);
+ return var;
+ }
+ if (kind () == VR_RANGE)
+ {
+ // [SYM, NUM] -> [-MIN, NUM]
+ if (min_symbolic)
+ return value_range (vrp_val_min (ttype), max ());
+ // [NUM, SYM] -> [NUM, +MAX]
+ return value_range (min (), vrp_val_max (ttype));
+ }
+ 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 (n, vrp_val_max (ttype));
+ }
+ value_range var;
+ var.set_varying (ttype);
+ return var;
+ }
+ // ~[NUM, SYM] -> [-MIN, NUM - 1]
+ if (!vrp_val_is_min (min ()))
+ {
+ tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1);
+ return value_range (vrp_val_min (ttype), n);
+ }
+ value_range var;
+ var.set_varying (ttype);
+ return var;
+}
+
+/* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
+ { VR1TYPE, VR0MIN, VR0MAX } and store the result
+ in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
+ possible such range. The resulting range is not canonicalized. */
+
+static void
+intersect_ranges (enum value_range_kind *vr0type,
+ tree *vr0min, tree *vr0max,
+ enum value_range_kind vr1type,
+ tree vr1min, tree vr1max)
+{
+ bool mineq = vrp_operand_equal_p (*vr0min, vr1min);
+ bool maxeq = vrp_operand_equal_p (*vr0max, vr1max);
+
+ /* [] is vr0, () is vr1 in the following classification comments. */
+ if (mineq && maxeq)
+ {
+ /* [( )] */
+ if (*vr0type == vr1type)
+ /* Nothing to do for equal ranges. */
+ ;
+ else if ((*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ || (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE))
+ {
+ /* For anti-range with range intersection the result is empty. */
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if (operand_less_p (*vr0max, vr1min) == 1
+ || operand_less_p (vr1max, *vr0min) == 1)
+ {
+ /* [ ] ( ) or ( ) [ ]
+ If the ranges have an empty intersection, the result of the
+ intersect operation is the range for intersecting an
+ anti-range with a range or empty when intersecting two ranges. */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ ;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ /* If the anti-ranges are adjacent to each other merge them. */
+ if (TREE_CODE (*vr0max) == INTEGER_CST
+ && TREE_CODE (vr1min) == INTEGER_CST
+ && operand_less_p (*vr0max, vr1min) == 1
+ && integer_onep (int_const_binop (MINUS_EXPR,
+ vr1min, *vr0max)))
+ *vr0max = vr1max;
+ else if (TREE_CODE (vr1max) == INTEGER_CST
+ && TREE_CODE (*vr0min) == INTEGER_CST
+ && operand_less_p (vr1max, *vr0min) == 1
+ && integer_onep (int_const_binop (MINUS_EXPR,
+ *vr0min, vr1max)))
+ *vr0min = vr1min;
+ /* Else arbitrarily take VR0. */
+ }
+ }
+ else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1)
+ && (mineq || operand_less_p (*vr0min, vr1min) == 1))
+ {
+ /* [ ( ) ] or [( ) ] or [ ( )] */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ {
+ /* If both are ranges the result is the inner one. */
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ /* Choose the right gap if the left one is empty. */
+ if (mineq)
+ {
+ if (TREE_CODE (vr1max) != INTEGER_CST)
+ *vr0min = vr1max;
+ else if (TYPE_PRECISION (TREE_TYPE (vr1max)) == 1
+ && !TYPE_UNSIGNED (TREE_TYPE (vr1max)))
+ *vr0min
+ = int_const_binop (MINUS_EXPR, vr1max,
+ build_int_cst (TREE_TYPE (vr1max), -1));
+ else
+ *vr0min
+ = int_const_binop (PLUS_EXPR, vr1max,
+ build_int_cst (TREE_TYPE (vr1max), 1));
+ }
+ /* Choose the left gap if the right one is empty. */
+ else if (maxeq)
+ {
+ if (TREE_CODE (vr1min) != INTEGER_CST)
+ *vr0max = vr1min;
+ else if (TYPE_PRECISION (TREE_TYPE (vr1min)) == 1
+ && !TYPE_UNSIGNED (TREE_TYPE (vr1min)))
+ *vr0max
+ = int_const_binop (PLUS_EXPR, vr1min,
+ build_int_cst (TREE_TYPE (vr1min), -1));
+ else
+ *vr0max
+ = int_const_binop (MINUS_EXPR, vr1min,
+ build_int_cst (TREE_TYPE (vr1min), 1));
+ }
+ /* Choose the anti-range if the range is effectively varying. */
+ else if (vrp_val_is_min (*vr0min)
+ && vrp_val_is_max (*vr0max))
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ /* Else choose the range. */
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ /* If both are anti-ranges the result is the outer one. */
+ ;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ /* The intersection is empty. */
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
+ && (mineq || operand_less_p (vr1min, *vr0min) == 1))
+ {
+ /* ( [ ] ) or ([ ] ) or ( [ ]) */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ /* Choose the inner range. */
+ ;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ /* Choose the right gap if the left is empty. */
+ if (mineq)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0max) != INTEGER_CST)
+ *vr0min = *vr0max;
+ else if (TYPE_PRECISION (TREE_TYPE (*vr0max)) == 1
+ && !TYPE_UNSIGNED (TREE_TYPE (*vr0max)))
+ *vr0min
+ = int_const_binop (MINUS_EXPR, *vr0max,
+ build_int_cst (TREE_TYPE (*vr0max), -1));
+ else
+ *vr0min
+ = int_const_binop (PLUS_EXPR, *vr0max,
+ build_int_cst (TREE_TYPE (*vr0max), 1));
+ *vr0max = vr1max;
+ }
+ /* Choose the left gap if the right is empty. */
+ else if (maxeq)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0min) != INTEGER_CST)
+ *vr0max = *vr0min;
+ else if (TYPE_PRECISION (TREE_TYPE (*vr0min)) == 1
+ && !TYPE_UNSIGNED (TREE_TYPE (*vr0min)))
+ *vr0max
+ = int_const_binop (PLUS_EXPR, *vr0min,
+ build_int_cst (TREE_TYPE (*vr0min), -1));
+ else
+ *vr0max
+ = int_const_binop (MINUS_EXPR, *vr0min,
+ build_int_cst (TREE_TYPE (*vr0min), 1));
+ *vr0min = vr1min;
+ }
+ /* Choose the anti-range if the range is effectively varying. */
+ else if (vrp_val_is_min (vr1min)
+ && vrp_val_is_max (vr1max))
+ ;
+ /* Choose the anti-range if it is ~[0,0], that range is special
+ enough to special case when vr1's range is relatively wide.
+ At least for types bigger than int - this covers pointers
+ and arguments to functions like ctz. */
+ else if (*vr0min == *vr0max
+ && integer_zerop (*vr0min)
+ && ((TYPE_PRECISION (TREE_TYPE (*vr0min))
+ >= TYPE_PRECISION (integer_type_node))
+ || POINTER_TYPE_P (TREE_TYPE (*vr0min)))
+ && TREE_CODE (vr1max) == INTEGER_CST
+ && TREE_CODE (vr1min) == INTEGER_CST
+ && (wi::clz (wi::to_wide (vr1max) - wi::to_wide (vr1min))
+ < TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2))
+ ;
+ /* Else choose the range. */
+ else
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ /* If both are anti-ranges the result is the outer one. */
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (vr1type == VR_ANTI_RANGE
+ && *vr0type == VR_RANGE)
+ {
+ /* The intersection is empty. */
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if ((operand_less_p (vr1min, *vr0max) == 1
+ || operand_equal_p (vr1min, *vr0max, 0))
+ && operand_less_p (*vr0min, vr1min) == 1)
+ {
+ /* [ ( ] ) or [ ]( ) */
+ if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ *vr0max = vr1max;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ *vr0min = vr1min;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ if (TREE_CODE (vr1min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, vr1min,
+ build_int_cst (TREE_TYPE (vr1min), 1));
+ else
+ *vr0max = vr1min;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
+ build_int_cst (TREE_TYPE (*vr0max), 1));
+ else
+ *vr0min = *vr0max;
+ *vr0max = vr1max;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if ((operand_less_p (*vr0min, vr1max) == 1
+ || operand_equal_p (*vr0min, vr1max, 0))
+ && operand_less_p (vr1min, *vr0min) == 1)
+ {
+ /* ( [ ) ] or ( )[ ] */
+ if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ *vr0min = vr1min;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ *vr0max = vr1max;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ if (TREE_CODE (vr1max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, vr1max,
+ build_int_cst (TREE_TYPE (vr1max), 1));
+ else
+ *vr0min = vr1max;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
+ build_int_cst (TREE_TYPE (*vr0min), 1));
+ else
+ *vr0max = *vr0min;
+ *vr0min = vr1min;
+ }
+ else
+ gcc_unreachable ();
+ }
+
+ /* 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
+ in which case we choose that. */
+ if (vr1type == VR_RANGE
+ && is_gimple_min_invariant (vr1min)
+ && vrp_operand_equal_p (vr1min, vr1max))
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+}
+
+/* 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. */
+
+value_range
+value_range::intersect_helper (const value_range *vr0, const value_range *vr1)
+{
+ /* If either range is VR_VARYING the other one wins. */
+ 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->undefined_p ())
+ return *vr0;
+ if (vr1->undefined_p ())
+ return *vr1;
+
+ value_range_kind vr0kind = vr0->kind ();
+ tree vr0min = vr0->min ();
+ tree vr0max = vr0->max ();
+ intersect_ranges (&vr0kind, &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. Work on a temporary so we can
+ fall back to vr0 when this turns things to varying. */
+ value_range tem;
+ if (vr0kind == VR_UNDEFINED)
+ tem.set_undefined ();
+ else if (vr0kind == VR_VARYING)
+ tem.set_varying (vr0->type ());
+ else
+ tem.set (vr0min, vr0max, vr0kind);
+ /* If that failed, use the saved original VR0. */
+ if (tem.varying_p ())
+ return *vr0;
+
+ return tem;
+}
+
+/* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
+ { VR1TYPE, VR0MIN, VR0MAX } and store the result
+ in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
+ possible such range. The resulting range is not canonicalized. */
+
+static void
+union_ranges (enum value_range_kind *vr0type,
+ tree *vr0min, tree *vr0max,
+ enum value_range_kind vr1type,
+ tree vr1min, tree vr1max)
+{
+ 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)
+ {
+ /* [( )] */
+ if (*vr0type == vr1type)
+ /* Nothing to do for equal ranges. */
+ ;
+ else if ((*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ || (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE))
+ {
+ /* For anti-range with range union the result is varying. */
+ goto give_up;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if (operand_less_p (*vr0max, vr1min) == 1
+ || operand_less_p (vr1max, *vr0min) == 1)
+ {
+ /* [ ] ( ) or ( ) [ ]
+ If the ranges have an empty intersection, result of the union
+ operation is the anti-range or if both are anti-ranges
+ it covers all. */
+ if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ goto give_up;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ ;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ {
+ /* The result is the convex hull of both ranges. */
+ if (operand_less_p (*vr0max, vr1min) == 1)
+ {
+ /* If the result can be an anti-range, create one. */
+ if (TREE_CODE (*vr0max) == INTEGER_CST
+ && TREE_CODE (vr1min) == INTEGER_CST
+ && vrp_val_is_min (*vr0min)
+ && vrp_val_is_max (vr1max))
+ {
+ tree min = int_const_binop (PLUS_EXPR,
+ *vr0max,
+ build_int_cst (TREE_TYPE (*vr0max), 1));
+ tree max = int_const_binop (MINUS_EXPR,
+ vr1min,
+ build_int_cst (TREE_TYPE (vr1min), 1));
+ if (!operand_less_p (max, min))
+ {
+ *vr0type = VR_ANTI_RANGE;
+ *vr0min = min;
+ *vr0max = max;
+ }
+ else
+ *vr0max = vr1max;
+ }
+ else
+ *vr0max = vr1max;
+ }
+ else
+ {
+ /* If the result can be an anti-range, create one. */
+ if (TREE_CODE (vr1max) == INTEGER_CST
+ && TREE_CODE (*vr0min) == INTEGER_CST
+ && vrp_val_is_min (vr1min)
+ && vrp_val_is_max (*vr0max))
+ {
+ tree min = int_const_binop (PLUS_EXPR,
+ vr1max,
+ build_int_cst (TREE_TYPE (vr1max), 1));
+ tree max = int_const_binop (MINUS_EXPR,
+ *vr0min,
+ build_int_cst (TREE_TYPE (*vr0min), 1));
+ if (!operand_less_p (max, min))
+ {
+ *vr0type = VR_ANTI_RANGE;
+ *vr0min = min;
+ *vr0max = max;
+ }
+ else
+ *vr0min = vr1min;
+ }
+ else
+ *vr0min = vr1min;
+ }
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if ((maxeq || cmpmax == 1)
+ && (mineq || cmpmin == -1))
+ {
+ /* [ ( ) ] or [( ) ] or [ ( )] */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ ;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ /* Arbitrarily choose the right or left gap. */
+ if (!mineq && TREE_CODE (vr1min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, vr1min,
+ build_int_cst (TREE_TYPE (vr1min), 1));
+ else if (!maxeq && TREE_CODE (vr1max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, vr1max,
+ build_int_cst (TREE_TYPE (vr1max), 1));
+ else
+ goto give_up;
+ }
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ /* The result covers everything. */
+ goto give_up;
+ else
+ gcc_unreachable ();
+ }
+ else if ((maxeq || cmpmax == -1)
+ && (mineq || cmpmin == 1))
+ {
+ /* ( [ ] ) or ([ ] ) or ( [ ]) */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ ;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ *vr0type = VR_ANTI_RANGE;
+ if (!mineq && TREE_CODE (*vr0min) == INTEGER_CST)
+ {
+ *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
+ build_int_cst (TREE_TYPE (*vr0min), 1));
+ *vr0min = vr1min;
+ }
+ else if (!maxeq && TREE_CODE (*vr0max) == INTEGER_CST)
+ {
+ *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
+ build_int_cst (TREE_TYPE (*vr0max), 1));
+ *vr0max = vr1max;
+ }
+ else
+ goto give_up;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ /* The result covers everything. */
+ goto give_up;
+ else
+ gcc_unreachable ();
+ }
+ else if (cmpmin == -1
+ && cmpmax == -1
+ && (operand_less_p (vr1min, *vr0max) == 1
+ || operand_equal_p (vr1min, *vr0max, 0)))
+ {
+ /* [ ( ] ) or [ ]( ) */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ *vr0max = vr1max;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ *vr0min = vr1min;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ if (TREE_CODE (vr1min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, vr1min,
+ build_int_cst (TREE_TYPE (vr1min), 1));
+ else
+ goto give_up;
+ }
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ if (TREE_CODE (*vr0max) == INTEGER_CST)
+ {
+ *vr0type = vr1type;
+ *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
+ build_int_cst (TREE_TYPE (*vr0max), 1));
+ *vr0max = vr1max;
+ }
+ else
+ goto give_up;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if (cmpmin == 1
+ && cmpmax == 1
+ && (operand_less_p (*vr0min, vr1max) == 1
+ || operand_equal_p (*vr0min, vr1max, 0)))
+ {
+ /* ( [ ) ] or ( )[ ] */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ *vr0min = vr1min;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ *vr0max = vr1max;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ if (TREE_CODE (vr1max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, vr1max,
+ build_int_cst (TREE_TYPE (vr1max), 1));
+ else
+ goto give_up;
+ }
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ if (TREE_CODE (*vr0min) == INTEGER_CST)
+ {
+ *vr0type = vr1type;
+ *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
+ build_int_cst (TREE_TYPE (*vr0min), 1));
+ *vr0min = vr1min;
+ }
+ else
+ goto give_up;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else
+ goto give_up;
+
+ return;
+
+give_up:
+ *vr0type = VR_VARYING;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+}
+
+/* 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
+value_range::union_helper (const value_range *vr0, const value_range *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 vr0kind = vr0->kind ();
+ tree vr0min = vr0->min ();
+ tree vr0max = vr0->max ();
+ union_ranges (&vr0kind, &vr0min, &vr0max,
+ vr1->kind (), vr1->min (), vr1->max ());
+
+ /* Work on a temporary so we can still use vr0 when union returns varying. */
+ value_range tem;
+ if (vr0kind == VR_UNDEFINED)
+ tem.set_undefined ();
+ else if (vr0kind == VR_VARYING)
+ tem.set_varying (vr0->type ());
+ else
+ tem.set (vr0min, vr0max, vr0kind);
+
+ /* 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. */
+
+void
+value_range::union_ (const value_range *other)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Meeting\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\nand\n ");
+ dump_value_range (dump_file, other);
+ fprintf (dump_file, "\n");
+ }
+
+ *this = union_helper (this, other);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "to\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\n");
+ }
+}
+
+/* Range union, but for references. */
+
+void
+value_range::union_ (const value_range &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;
+}
+
+void
+value_range::intersect (const value_range *other)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ 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");
+ }
+
+ *this = intersect_helper (this, other);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "to\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\n");
+ }
+}
+
+/* Range intersect, but for references. */
+
+void
+value_range::intersect (const value_range &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 the inverse of a range. */
+
+void
+value_range::invert ()
+{
+ /* We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
+ create non-canonical ranges. Use the constructors instead. */
+ if (m_kind == VR_RANGE)
+ *this = value_range (m_min, m_max, VR_ANTI_RANGE);
+ else if (m_kind == VR_ANTI_RANGE)
+ *this = value_range (m_min, m_max);
+ else
+ gcc_unreachable ();
+}
+
+void
+value_range::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 ())
+ && 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::dump () const
+{
+ dump (stderr);
+}
+
+void
+dump_value_range (FILE *file, const value_range *vr)
+{
+ if (!vr)
+ fprintf (file, "[]");
+ else
+ vr->dump (file);
+}
+
+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);
+}
+
+/* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
+ so that *VR0 U *VR1 == *AR. Returns true if that is possible,
+ false otherwise. If *AR can be represented with a single range
+ *VR1 will be VR_UNDEFINED. */
+
+bool
+ranges_from_anti_range (const value_range *ar,
+ value_range *vr0, value_range *vr1)
+{
+ tree type = ar->type ();
+
+ vr0->set_undefined ();
+ vr1->set_undefined ();
+
+ /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
+ [A+1, +INF]. Not sure if this helps in practice, though. */
+
+ if (ar->kind () != VR_ANTI_RANGE
+ || TREE_CODE (ar->min ()) != INTEGER_CST
+ || TREE_CODE (ar->max ()) != INTEGER_CST
+ || !vrp_val_min (type)
+ || !vrp_val_max (type))
+ return false;
+
+ if (tree_int_cst_lt (vrp_val_min (type), ar->min ()))
+ vr0->set (vrp_val_min (type),
+ wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1));
+ if (tree_int_cst_lt (ar->max (), vrp_val_max (type)))
+ vr1->set (wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1),
+ vrp_val_max (type));
+ if (vr0->undefined_p ())
+ {
+ *vr0 = *vr1;
+ vr1->set_undefined ();
+ }
+
+ return !vr0->undefined_p ();
+}
+
+bool
+range_has_numeric_bounds_p (const value_range *vr)
+{
+ return (vr->min ()
+ && TREE_CODE (vr->min ()) == INTEGER_CST
+ && TREE_CODE (vr->max ()) == INTEGER_CST);
+}
+
+/* Return the maximum value for TYPE. */
+
+tree
+vrp_val_max (const_tree type)
+{
+ if (INTEGRAL_TYPE_P (type))
+ return TYPE_MAX_VALUE (type);
+ if (POINTER_TYPE_P (type))
+ {
+ 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)
+{
+ if (INTEGRAL_TYPE_P (type))
+ return TYPE_MIN_VALUE (type);
+ if (POINTER_TYPE_P (type))
+ return build_zero_cst (const_cast<tree> (type));
+ return NULL_TREE;
+}
+
+/* Return whether VAL is equal to the maximum value of its type.
+ We can't do a simple equality comparison with TYPE_MAX_VALUE because
+ C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
+ is not == to the integer constant with the same value in the type. */
+
+bool
+vrp_val_is_max (const_tree val)
+{
+ tree type_max = vrp_val_max (TREE_TYPE (val));
+ return (val == type_max
+ || (type_max != NULL_TREE
+ && operand_equal_p (val, type_max, 0)));
+}
+
+/* Return whether VAL is equal to the minimum value of its type. */
+
+bool
+vrp_val_is_min (const_tree val)
+{
+ tree type_min = vrp_val_min (TREE_TYPE (val));
+ return (val == type_min
+ || (type_min != NULL_TREE
+ && operand_equal_p (val, type_min, 0)));
+}
+
+/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
+
+bool
+vrp_operand_equal_p (const_tree val1, const_tree val2)
+{
+ if (val1 == val2)
+ return true;
+ if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
+ return false;
+ return true;
+}
new file mode 100644
@@ -0,0 +1,216 @@
+/* Support routines for value ranges.
+ Copyright (C) 2019 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#ifndef GCC_VALUE_RANGE_H
+#define GCC_VALUE_RANGE_H
+
+/* Types of value ranges. */
+enum value_range_kind
+{
+ /* Empty range. */
+ VR_UNDEFINED,
+ /* Range spans the entire domain. */
+ VR_VARYING,
+ /* Range is [MIN, MAX]. */
+ VR_RANGE,
+ /* Range is ~[MIN, MAX]. */
+ VR_ANTI_RANGE,
+ /* Range is a nice guy. */
+ VR_LAST
+};
+
+// Range of values that can be associated with an SSA_NAME.
+
+class GTY((for_user)) value_range
+{
+ friend void range_tests ();
+public:
+ value_range ();
+ value_range (tree, tree, value_range_kind = VR_RANGE);
+ value_range (tree type, const wide_int &, const wide_int &,
+ value_range_kind = VR_RANGE);
+ value_range (tree type);
+
+ void set (tree, tree, value_range_kind = VR_RANGE);
+ void set (tree);
+ void set_nonzero (tree);
+ void set_zero (tree);
+
+ enum value_range_kind kind () const;
+ tree min () const;
+ tree max () const;
+
+ /* Types of value ranges. */
+ bool symbolic_p () const;
+ bool constant_p () const;
+ bool undefined_p () const;
+ bool varying_p () const;
+ void set_varying (tree type);
+ void set_undefined ();
+
+ void union_ (const value_range *);
+ void intersect (const value_range *);
+ void union_ (const value_range &);
+ void intersect (const value_range &);
+
+ bool operator== (const value_range &) const;
+ bool operator!= (const value_range &) const /* = delete */;
+ bool equal_p (const value_range &) const;
+
+ /* Misc methods. */
+ tree type () const;
+ bool may_contain_p (tree) const;
+ bool zero_p () const;
+ bool nonzero_p () const;
+ bool singleton_p (tree *result = NULL) const;
+ void dump (FILE *) const;
+ void dump () const;
+
+ static bool supports_type_p (tree);
+ value_range normalize_symbolics () const;
+ value_range normalize_addresses () const;
+
+ static const unsigned int m_max_pairs = 2;
+ bool contains_p (tree) const;
+ unsigned num_pairs () const;
+ wide_int lower_bound (unsigned = 0) const;
+ wide_int upper_bound (unsigned) const;
+ wide_int upper_bound () const;
+ void invert ();
+
+protected:
+ void check ();
+ static value_range union_helper (const value_range *, const value_range *);
+ static value_range intersect_helper (const value_range *,
+ const value_range *);
+
+ friend void gt_ggc_mx_value_range (void *);
+ friend void gt_pch_p_11value_range (void *, void *,
+ gt_pointer_operator, void *);
+ friend void gt_pch_nx_value_range (void *);
+ friend void gt_ggc_mx (value_range &);
+ friend void gt_ggc_mx (value_range *&);
+ friend void gt_pch_nx (value_range &);
+ friend void gt_pch_nx (value_range *, gt_pointer_operator, void *);
+
+ enum value_range_kind m_kind;
+ tree m_min;
+ tree m_max;
+
+private:
+ int value_inside_range (tree) const;
+};
+
+extern bool range_has_numeric_bounds_p (const value_range *);
+extern bool ranges_from_anti_range (const value_range *,
+ value_range *, value_range *);
+extern void dump_value_range (FILE *, const value_range *);
+extern bool vrp_val_is_min (const_tree);
+extern bool vrp_val_is_max (const_tree);
+extern tree vrp_val_min (const_tree);
+extern tree vrp_val_max (const_tree);
+extern bool vrp_operand_equal_p (const_tree, const_tree);
+
+inline
+value_range::value_range ()
+{
+ m_kind = VR_UNDEFINED;
+ m_min = m_max = NULL;
+}
+
+inline value_range_kind
+value_range::kind () const
+{
+ return m_kind;
+}
+
+inline tree
+value_range::type () const
+{
+ return TREE_TYPE (min ());
+}
+
+inline tree
+value_range::min () const
+{
+ return m_min;
+}
+
+inline tree
+value_range::max () const
+{
+ return m_max;
+}
+
+inline bool
+value_range::varying_p () const
+{
+ return m_kind == VR_VARYING;
+}
+
+inline bool
+value_range::undefined_p () const
+{
+ return m_kind == VR_UNDEFINED;
+}
+
+inline bool
+value_range::zero_p () const
+{
+ return (m_kind == VR_RANGE
+ && integer_zerop (m_min)
+ && integer_zerop (m_max));
+}
+
+inline bool
+value_range::nonzero_p () const
+{
+ if (m_kind == VR_ANTI_RANGE
+ && !TYPE_UNSIGNED (type ())
+ && integer_zerop (m_min)
+ && integer_zerop (m_max))
+ return true;
+
+ return (m_kind == VR_RANGE
+ && TYPE_UNSIGNED (type ())
+ && integer_onep (m_min)
+ && vrp_val_is_max (m_max));
+}
+
+inline bool
+value_range::supports_type_p (tree type)
+{
+ if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)))
+ return type;
+ return false;
+}
+
+inline bool
+range_includes_zero_p (const value_range *vr)
+{
+ if (vr->undefined_p ())
+ return false;
+
+ if (vr->varying_p ())
+ return true;
+
+ return vr->may_contain_p (build_zero_cst (vr->type ()));
+}
+
+#endif // GCC_VALUE_RANGE_H