2567 lines
68 KiB
C++
2567 lines
68 KiB
C++
/* Support routines for value ranges.
|
|
Copyright (C) 2019-2022 Free Software Foundation, Inc.
|
|
Major hacks by Aldy Hernandez <aldyh@redhat.com> and
|
|
Andrew MacLeod <amacleod@redhat.com>.
|
|
|
|
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"
|
|
#include "gimple-range.h"
|
|
|
|
// Here we copy between any two irange's. The ranges can be legacy or
|
|
// multi-ranges, and copying between any combination works correctly.
|
|
|
|
irange &
|
|
irange::operator= (const irange &src)
|
|
{
|
|
if (legacy_mode_p ())
|
|
{
|
|
copy_to_legacy (src);
|
|
return *this;
|
|
}
|
|
if (src.legacy_mode_p ())
|
|
{
|
|
copy_legacy_to_multi_range (src);
|
|
return *this;
|
|
}
|
|
|
|
unsigned x;
|
|
unsigned lim = src.m_num_ranges;
|
|
if (lim > m_max_ranges)
|
|
lim = m_max_ranges;
|
|
|
|
for (x = 0; x < lim * 2; ++x)
|
|
m_base[x] = src.m_base[x];
|
|
|
|
// If the range didn't fit, the last range should cover the rest.
|
|
if (lim != src.m_num_ranges)
|
|
m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1];
|
|
|
|
m_num_ranges = lim;
|
|
m_kind = src.m_kind;
|
|
return *this;
|
|
}
|
|
|
|
// Return TRUE if range is a multi-range that can be represented as a
|
|
// VR_ANTI_RANGE.
|
|
|
|
bool
|
|
irange::maybe_anti_range () const
|
|
{
|
|
tree ttype = type ();
|
|
unsigned int precision = TYPE_PRECISION (ttype);
|
|
signop sign = TYPE_SIGN (ttype);
|
|
return (num_pairs () > 1
|
|
&& precision > 1
|
|
&& lower_bound () == wi::min_value (precision, sign)
|
|
&& upper_bound () == wi::max_value (precision, sign));
|
|
}
|
|
|
|
void
|
|
irange::copy_legacy_to_multi_range (const irange &src)
|
|
{
|
|
gcc_checking_assert (src.legacy_mode_p ());
|
|
gcc_checking_assert (!legacy_mode_p ());
|
|
if (src.undefined_p ())
|
|
set_undefined ();
|
|
else if (src.varying_p ())
|
|
set_varying (src.type ());
|
|
else
|
|
{
|
|
if (range_has_numeric_bounds_p (&src))
|
|
set (src.min (), src.max (), src.kind ());
|
|
else
|
|
{
|
|
value_range cst (src);
|
|
cst.normalize_symbolics ();
|
|
gcc_checking_assert (cst.varying_p () || cst.kind () == VR_RANGE);
|
|
set (cst.min (), cst.max ());
|
|
}
|
|
}
|
|
}
|
|
|
|
// Copy any type of irange into a legacy.
|
|
|
|
void
|
|
irange::copy_to_legacy (const irange &src)
|
|
{
|
|
gcc_checking_assert (legacy_mode_p ());
|
|
// Handle legacy to legacy and other things that are easy to copy.
|
|
if (src.legacy_mode_p () || src.varying_p () || src.undefined_p ())
|
|
{
|
|
m_num_ranges = src.m_num_ranges;
|
|
m_base[0] = src.m_base[0];
|
|
m_base[1] = src.m_base[1];
|
|
m_kind = src.m_kind;
|
|
return;
|
|
}
|
|
// Copy multi-range to legacy.
|
|
if (src.maybe_anti_range ())
|
|
{
|
|
int_range<3> r (src);
|
|
r.invert ();
|
|
// Use tree variants to save on tree -> wi -> tree conversions.
|
|
set (r.tree_lower_bound (0), r.tree_upper_bound (0), VR_ANTI_RANGE);
|
|
}
|
|
else
|
|
set (src.tree_lower_bound (), src.tree_upper_bound ());
|
|
}
|
|
|
|
// Swap MIN/MAX if they are out of order and adjust KIND appropriately.
|
|
|
|
static void
|
|
swap_out_of_order_endpoints (tree &min, tree &max, value_range_kind &kind)
|
|
{
|
|
gcc_checking_assert (kind != VR_UNDEFINED);
|
|
if (kind == VR_VARYING)
|
|
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)
|
|
{
|
|
kind = VR_VARYING;
|
|
return;
|
|
}
|
|
|
|
one = build_int_cst (TREE_TYPE (min), 1);
|
|
tmp = int_const_binop (PLUS_EXPR, max, one);
|
|
max = int_const_binop (MINUS_EXPR, min, one);
|
|
min = tmp;
|
|
|
|
/* There's one corner case, if we had [C+1, C] before we now have
|
|
that again. But this represents an empty value range, so drop
|
|
to varying in this case. */
|
|
if (tree_int_cst_lt (max, min))
|
|
{
|
|
kind = VR_VARYING;
|
|
return;
|
|
}
|
|
kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
|
|
}
|
|
}
|
|
|
|
void
|
|
irange::irange_set (tree min, tree max)
|
|
{
|
|
gcc_checking_assert (!POLY_INT_CST_P (min));
|
|
gcc_checking_assert (!POLY_INT_CST_P (max));
|
|
|
|
m_base[0] = min;
|
|
m_base[1] = max;
|
|
m_num_ranges = 1;
|
|
m_kind = VR_RANGE;
|
|
normalize_kind ();
|
|
|
|
if (flag_checking)
|
|
verify_range ();
|
|
}
|
|
|
|
void
|
|
irange::irange_set_1bit_anti_range (tree min, tree max)
|
|
{
|
|
tree type = TREE_TYPE (min);
|
|
gcc_checking_assert (TYPE_PRECISION (type) == 1);
|
|
|
|
if (operand_equal_p (min, max))
|
|
{
|
|
// Since these are 1-bit quantities, they can only be [MIN,MIN]
|
|
// or [MAX,MAX].
|
|
if (vrp_val_is_min (min))
|
|
min = max = vrp_val_max (type);
|
|
else
|
|
min = max = vrp_val_min (type);
|
|
set (min, max);
|
|
}
|
|
else
|
|
{
|
|
// The only alternative is [MIN,MAX], which is the empty range.
|
|
gcc_checking_assert (vrp_val_is_min (min));
|
|
gcc_checking_assert (vrp_val_is_max (max));
|
|
set_undefined ();
|
|
}
|
|
if (flag_checking)
|
|
verify_range ();
|
|
}
|
|
|
|
void
|
|
irange::irange_set_anti_range (tree min, tree max)
|
|
{
|
|
gcc_checking_assert (!POLY_INT_CST_P (min));
|
|
gcc_checking_assert (!POLY_INT_CST_P (max));
|
|
|
|
if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
|
|
{
|
|
irange_set_1bit_anti_range (min, max);
|
|
return;
|
|
}
|
|
|
|
// set an anti-range
|
|
tree type = TREE_TYPE (min);
|
|
signop sign = TYPE_SIGN (type);
|
|
int_range<2> type_range (type);
|
|
// Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
|
|
m_num_ranges = 0;
|
|
wi::overflow_type ovf;
|
|
|
|
wide_int w_min = wi::to_wide (min);
|
|
if (wi::ne_p (w_min, type_range.lower_bound ()))
|
|
{
|
|
wide_int lim1 = wi::sub (w_min, 1, sign, &ovf);
|
|
gcc_checking_assert (ovf != wi::OVF_OVERFLOW);
|
|
m_base[0] = type_range.tree_lower_bound (0);
|
|
m_base[1] = wide_int_to_tree (type, lim1);
|
|
m_num_ranges = 1;
|
|
}
|
|
wide_int w_max = wi::to_wide (max);
|
|
if (wi::ne_p (w_max, type_range.upper_bound ()))
|
|
{
|
|
wide_int lim2 = wi::add (w_max, 1, sign, &ovf);
|
|
gcc_checking_assert (ovf != wi::OVF_OVERFLOW);
|
|
m_base[m_num_ranges * 2] = wide_int_to_tree (type, lim2);
|
|
m_base[m_num_ranges * 2 + 1] = type_range.tree_upper_bound (0);
|
|
++m_num_ranges;
|
|
}
|
|
|
|
m_kind = VR_RANGE;
|
|
normalize_kind ();
|
|
|
|
if (flag_checking)
|
|
verify_range ();
|
|
}
|
|
|
|
/* 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
|
|
irange::set (tree min, tree max, value_range_kind kind)
|
|
{
|
|
if (kind != VR_UNDEFINED)
|
|
{
|
|
if (TREE_OVERFLOW_P (min))
|
|
min = drop_tree_overflow (min);
|
|
if (TREE_OVERFLOW_P (max))
|
|
max = drop_tree_overflow (max);
|
|
}
|
|
|
|
if (!legacy_mode_p ())
|
|
{
|
|
if (kind == VR_RANGE)
|
|
irange_set (min, max);
|
|
else
|
|
{
|
|
gcc_checking_assert (kind == VR_ANTI_RANGE);
|
|
irange_set_anti_range (min, max);
|
|
}
|
|
return;
|
|
}
|
|
if (kind == VR_UNDEFINED)
|
|
{
|
|
set_undefined ();
|
|
return;
|
|
}
|
|
|
|
if (kind == VR_VARYING
|
|
|| POLY_INT_CST_P (min)
|
|
|| POLY_INT_CST_P (max))
|
|
{
|
|
set_varying (TREE_TYPE (min));
|
|
return;
|
|
}
|
|
|
|
// Nothing to canonicalize for symbolic ranges.
|
|
if (TREE_CODE (min) != INTEGER_CST
|
|
|| TREE_CODE (max) != INTEGER_CST)
|
|
{
|
|
m_kind = kind;
|
|
m_base[0] = min;
|
|
m_base[1] = max;
|
|
m_num_ranges = 1;
|
|
return;
|
|
}
|
|
|
|
swap_out_of_order_endpoints (min, max, kind);
|
|
if (kind == VR_VARYING)
|
|
{
|
|
set_varying (TREE_TYPE (min));
|
|
return;
|
|
}
|
|
|
|
// Anti-ranges that can be represented as ranges should be so.
|
|
if (kind == VR_ANTI_RANGE)
|
|
{
|
|
bool is_min = vrp_val_is_min (min);
|
|
bool is_max = vrp_val_is_max (max);
|
|
|
|
if (is_min && is_max)
|
|
{
|
|
// Fall through. This will either be normalized as
|
|
// VR_UNDEFINED if the anti-range spans the entire
|
|
// precision, or it will remain an VR_ANTI_RANGE in the case
|
|
// of an -fstrict-enum where [MIN,MAX] is less than the span
|
|
// of underlying precision.
|
|
}
|
|
else if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
|
|
{
|
|
irange_set_1bit_anti_range (min, max);
|
|
return;
|
|
}
|
|
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;
|
|
}
|
|
}
|
|
|
|
m_kind = kind;
|
|
m_base[0] = min;
|
|
m_base[1] = max;
|
|
m_num_ranges = 1;
|
|
normalize_kind ();
|
|
if (flag_checking)
|
|
verify_range ();
|
|
}
|
|
|
|
// Check the validity of the range.
|
|
|
|
void
|
|
irange::verify_range ()
|
|
{
|
|
if (m_kind == VR_UNDEFINED)
|
|
{
|
|
gcc_checking_assert (m_num_ranges == 0);
|
|
return;
|
|
}
|
|
if (m_kind == VR_VARYING)
|
|
{
|
|
gcc_checking_assert (m_num_ranges == 1);
|
|
gcc_checking_assert (varying_compatible_p ());
|
|
return;
|
|
}
|
|
if (!legacy_mode_p ())
|
|
{
|
|
gcc_checking_assert (m_num_ranges != 0);
|
|
gcc_checking_assert (!varying_compatible_p ());
|
|
for (unsigned i = 0; i < m_num_ranges; ++i)
|
|
{
|
|
tree lb = tree_lower_bound (i);
|
|
tree ub = tree_upper_bound (i);
|
|
int c = compare_values (lb, ub);
|
|
gcc_checking_assert (c == 0 || c == -1);
|
|
}
|
|
return;
|
|
}
|
|
if (m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE)
|
|
{
|
|
gcc_checking_assert (m_num_ranges == 1);
|
|
int cmp = compare_values (tree_lower_bound (0), tree_upper_bound (0));
|
|
gcc_checking_assert (cmp == 0 || cmp == -1 || cmp == -2);
|
|
}
|
|
}
|
|
|
|
// Return the lower bound for a sub-range. PAIR is the sub-range in
|
|
// question.
|
|
|
|
wide_int
|
|
irange::legacy_lower_bound (unsigned pair) const
|
|
{
|
|
gcc_checking_assert (legacy_mode_p ());
|
|
if (symbolic_p ())
|
|
{
|
|
value_range numeric_range (*this);
|
|
numeric_range.normalize_symbolics ();
|
|
return numeric_range.legacy_lower_bound (pair);
|
|
}
|
|
gcc_checking_assert (m_num_ranges > 0);
|
|
gcc_checking_assert (pair + 1 <= num_pairs ());
|
|
if (m_kind == VR_ANTI_RANGE)
|
|
{
|
|
tree typ = type (), t;
|
|
if (pair == 1 || vrp_val_is_min (min ()))
|
|
t = wide_int_to_tree (typ, wi::to_wide (max ()) + 1);
|
|
else
|
|
t = vrp_val_min (typ);
|
|
return wi::to_wide (t);
|
|
}
|
|
return wi::to_wide (tree_lower_bound (pair));
|
|
}
|
|
|
|
// Return the upper bound for a sub-range. PAIR is the sub-range in
|
|
// question.
|
|
|
|
wide_int
|
|
irange::legacy_upper_bound (unsigned pair) const
|
|
{
|
|
gcc_checking_assert (legacy_mode_p ());
|
|
if (symbolic_p ())
|
|
{
|
|
value_range numeric_range (*this);
|
|
numeric_range.normalize_symbolics ();
|
|
return numeric_range.legacy_upper_bound (pair);
|
|
}
|
|
gcc_checking_assert (m_num_ranges > 0);
|
|
gcc_checking_assert (pair + 1 <= num_pairs ());
|
|
if (m_kind == VR_ANTI_RANGE)
|
|
{
|
|
tree typ = type (), t;
|
|
if (pair == 1 || vrp_val_is_min (min ()))
|
|
t = vrp_val_max (typ);
|
|
else
|
|
t = wide_int_to_tree (typ, wi::to_wide (min ()) - 1);
|
|
return wi::to_wide (t);
|
|
}
|
|
return wi::to_wide (tree_upper_bound (pair));
|
|
}
|
|
|
|
bool
|
|
irange::legacy_equal_p (const irange &other) const
|
|
{
|
|
gcc_checking_assert (legacy_mode_p () && other.legacy_mode_p ());
|
|
|
|
if (m_kind != other.m_kind)
|
|
return false;
|
|
if (m_kind == VR_UNDEFINED)
|
|
return true;
|
|
if (m_kind == VR_VARYING)
|
|
return range_compatible_p (type (), other.type ());
|
|
return (vrp_operand_equal_p (tree_lower_bound (0),
|
|
other.tree_lower_bound (0))
|
|
&& vrp_operand_equal_p (tree_upper_bound (0),
|
|
other.tree_upper_bound (0)));
|
|
}
|
|
|
|
bool
|
|
irange::equal_p (const irange &other) const
|
|
{
|
|
if (legacy_mode_p ())
|
|
{
|
|
if (other.legacy_mode_p ())
|
|
return legacy_equal_p (other);
|
|
value_range tmp (other);
|
|
return legacy_equal_p (tmp);
|
|
}
|
|
if (other.legacy_mode_p ())
|
|
{
|
|
value_range tmp2 (*this);
|
|
return tmp2.legacy_equal_p (other);
|
|
}
|
|
|
|
if (m_num_ranges != other.m_num_ranges)
|
|
return false;
|
|
|
|
for (unsigned i = 0; i < m_num_ranges; ++i)
|
|
{
|
|
tree lb = tree_lower_bound (i);
|
|
tree ub = tree_upper_bound (i);
|
|
tree lb_other = other.tree_lower_bound (i);
|
|
tree ub_other = other.tree_upper_bound (i);
|
|
if (!operand_equal_p (lb, lb_other, 0)
|
|
|| !operand_equal_p (ub, ub_other, 0))
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/* Return TRUE if this is a symbolic range. */
|
|
|
|
bool
|
|
irange::symbolic_p () const
|
|
{
|
|
return (m_num_ranges > 0
|
|
&& (!is_gimple_min_invariant (min ())
|
|
|| !is_gimple_min_invariant (max ())));
|
|
}
|
|
|
|
/* Return TRUE if this is a constant range. */
|
|
|
|
bool
|
|
irange::constant_p () const
|
|
{
|
|
return (m_num_ranges > 0
|
|
&& TREE_CODE (min ()) == INTEGER_CST
|
|
&& TREE_CODE (max ()) == INTEGER_CST);
|
|
}
|
|
|
|
/* 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
|
|
irange::singleton_p (tree *result) const
|
|
{
|
|
if (!legacy_mode_p ())
|
|
{
|
|
if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
|
|
== wi::to_wide (tree_upper_bound ())))
|
|
{
|
|
if (result)
|
|
*result = tree_lower_bound ();
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
if (m_kind == VR_ANTI_RANGE)
|
|
{
|
|
if (nonzero_p ())
|
|
{
|
|
if (TYPE_PRECISION (type ()) == 1)
|
|
{
|
|
if (result)
|
|
*result = max ();
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
if (num_pairs () == 1)
|
|
{
|
|
value_range vr0, vr1;
|
|
ranges_from_anti_range ((const value_range *) this, &vr0, &vr1);
|
|
return vr0.singleton_p (result);
|
|
}
|
|
}
|
|
// Catches non-numeric extremes as well.
|
|
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
|
|
irange::value_inside_range (tree val) const
|
|
{
|
|
if (varying_p ())
|
|
return 1;
|
|
|
|
if (undefined_p ())
|
|
return 0;
|
|
|
|
if (!legacy_mode_p () && TREE_CODE (val) == INTEGER_CST)
|
|
return contains_p (val);
|
|
|
|
int cmp1 = operand_less_p (val, min ());
|
|
if (cmp1 == -2)
|
|
return -2;
|
|
if (cmp1 == 1)
|
|
return m_kind != VR_RANGE;
|
|
|
|
int cmp2 = operand_less_p (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
|
|
irange::may_contain_p (tree val) const
|
|
{
|
|
return value_inside_range (val) != 0;
|
|
}
|
|
|
|
/* Return TRUE if range contains INTEGER_CST. */
|
|
/* Return 1 if VAL is inside value range.
|
|
0 if VAL is not inside value range.
|
|
|
|
Benchmark compile/20001226-1.c compilation time after changing this
|
|
function. */
|
|
|
|
|
|
bool
|
|
irange::contains_p (tree cst) const
|
|
{
|
|
if (undefined_p ())
|
|
return false;
|
|
|
|
if (legacy_mode_p ())
|
|
{
|
|
gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST);
|
|
if (symbolic_p ())
|
|
{
|
|
value_range numeric_range (*this);
|
|
numeric_range.normalize_symbolics ();
|
|
return numeric_range.contains_p (cst);
|
|
}
|
|
return value_inside_range (cst) == 1;
|
|
}
|
|
|
|
gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST);
|
|
signop sign = TYPE_SIGN (TREE_TYPE (cst));
|
|
wide_int v = wi::to_wide (cst);
|
|
for (unsigned r = 0; r < m_num_ranges; ++r)
|
|
{
|
|
if (wi::lt_p (v, lower_bound (r), sign))
|
|
return false;
|
|
if (wi::le_p (v, upper_bound (r), sign))
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
|
|
/* Normalize addresses into constants. */
|
|
|
|
void
|
|
irange::normalize_addresses ()
|
|
{
|
|
if (undefined_p ())
|
|
return;
|
|
|
|
if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
|
|
return;
|
|
|
|
if (!range_includes_zero_p (this))
|
|
{
|
|
gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
|
|
|| TREE_CODE (max ()) == ADDR_EXPR);
|
|
set_nonzero (type ());
|
|
return;
|
|
}
|
|
set_varying (type ());
|
|
}
|
|
|
|
/* Normalize symbolics and addresses into constants. */
|
|
|
|
void
|
|
irange::normalize_symbolics ()
|
|
{
|
|
if (varying_p () || undefined_p ())
|
|
return;
|
|
|
|
tree ttype = type ();
|
|
bool min_symbolic = !is_gimple_min_invariant (min ());
|
|
bool max_symbolic = !is_gimple_min_invariant (max ());
|
|
if (!min_symbolic && !max_symbolic)
|
|
{
|
|
normalize_addresses ();
|
|
return;
|
|
}
|
|
|
|
// [SYM, SYM] -> VARYING
|
|
if (min_symbolic && max_symbolic)
|
|
{
|
|
set_varying (ttype);
|
|
return;
|
|
}
|
|
if (kind () == VR_RANGE)
|
|
{
|
|
// [SYM, NUM] -> [-MIN, NUM]
|
|
if (min_symbolic)
|
|
{
|
|
set (vrp_val_min (ttype), max ());
|
|
return;
|
|
}
|
|
// [NUM, SYM] -> [NUM, +MAX]
|
|
set (min (), vrp_val_max (ttype));
|
|
return;
|
|
}
|
|
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);
|
|
set (n, vrp_val_max (ttype));
|
|
return;
|
|
}
|
|
set_varying (ttype);
|
|
return;
|
|
}
|
|
// ~[NUM, SYM] -> [-MIN, NUM - 1]
|
|
if (!vrp_val_is_min (min ()))
|
|
{
|
|
tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1);
|
|
set (vrp_val_min (ttype), n);
|
|
return;
|
|
}
|
|
set_varying (ttype);
|
|
}
|
|
|
|
/* 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
|
|
&& operand_less_p (*vr0max, vr1max) == 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
|
|
&& operand_less_p (vr1max, *vr0max) == 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
|
|
ranges VR0 and VR1, set VR0 to the intersection of both ranges.
|
|
This may not be the smallest possible such range. */
|
|
|
|
void
|
|
irange::legacy_intersect (irange *vr0, const irange *vr1)
|
|
{
|
|
gcc_checking_assert (vr0->legacy_mode_p ());
|
|
gcc_checking_assert (vr1->legacy_mode_p ());
|
|
/* If either range is VR_VARYING the other one wins. */
|
|
if (vr1->varying_p ())
|
|
return;
|
|
if (vr0->varying_p ())
|
|
{
|
|
vr0->set (vr1->min (), vr1->max (), vr1->kind ());
|
|
return;
|
|
}
|
|
|
|
/* When either range is VR_UNDEFINED the resulting range is
|
|
VR_UNDEFINED, too. */
|
|
if (vr0->undefined_p ())
|
|
return;
|
|
if (vr1->undefined_p ())
|
|
{
|
|
vr0->set_undefined ();
|
|
return;
|
|
}
|
|
|
|
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. */
|
|
if (vr0kind == VR_UNDEFINED)
|
|
vr0->set_undefined ();
|
|
else if (vr0kind == VR_VARYING)
|
|
{
|
|
/* If we failed, use the original VR0. */
|
|
return;
|
|
}
|
|
else
|
|
vr0->set (vr0min, vr0max, vr0kind);
|
|
}
|
|
|
|
/* 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 ranges VR0
|
|
and VR1, set VR0 to the union of both ranges. This may not be the
|
|
smallest possible such range. */
|
|
|
|
void
|
|
irange::legacy_union (irange *vr0, const irange *vr1)
|
|
{
|
|
gcc_checking_assert (vr0->legacy_mode_p ());
|
|
gcc_checking_assert (vr1->legacy_mode_p ());
|
|
|
|
/* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
|
|
if (vr1->undefined_p ()
|
|
|| vr0->varying_p ())
|
|
return;
|
|
|
|
/* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
|
|
if (vr0->undefined_p ())
|
|
{
|
|
vr0->set (vr1->min (), vr1->max (), vr1->kind ());
|
|
return;
|
|
}
|
|
|
|
if (vr1->varying_p ())
|
|
{
|
|
vr0->set_varying (vr1->type ());
|
|
return;
|
|
}
|
|
|
|
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 ());
|
|
|
|
if (vr0kind == VR_UNDEFINED)
|
|
vr0->set_undefined ();
|
|
else if (vr0kind == VR_VARYING)
|
|
{
|
|
/* Failed to find an efficient meet. Before giving up and
|
|
setting the result to VARYING, see if we can at least derive
|
|
a non-zero range. */
|
|
if (range_includes_zero_p (vr0) == 0
|
|
&& range_includes_zero_p (vr1) == 0)
|
|
vr0->set_nonzero (vr0->type ());
|
|
else
|
|
vr0->set_varying (vr0->type ());
|
|
}
|
|
else
|
|
vr0->set (vr0min, vr0max, vr0kind);
|
|
}
|
|
|
|
/* 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
|
|
irange::union_ (const irange *other)
|
|
{
|
|
if (legacy_mode_p ())
|
|
{
|
|
if (!other->legacy_mode_p ())
|
|
{
|
|
int_range<1> tmp = *other;
|
|
legacy_union (this, &tmp);
|
|
return;
|
|
}
|
|
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");
|
|
}
|
|
|
|
legacy_union (this, other);
|
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
|
{
|
|
fprintf (dump_file, "to\n ");
|
|
dump_value_range (dump_file, this);
|
|
fprintf (dump_file, "\n");
|
|
}
|
|
return;
|
|
}
|
|
|
|
if (other->legacy_mode_p ())
|
|
{
|
|
int_range<2> wider = *other;
|
|
irange_union (wider);
|
|
}
|
|
else
|
|
irange_union (*other);
|
|
}
|
|
|
|
void
|
|
irange::intersect (const irange *other)
|
|
{
|
|
if (legacy_mode_p ())
|
|
{
|
|
if (!other->legacy_mode_p ())
|
|
{
|
|
int_range<1> tmp = *other;
|
|
legacy_intersect (this, &tmp);
|
|
return;
|
|
}
|
|
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");
|
|
}
|
|
|
|
legacy_intersect (this, other);
|
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
|
{
|
|
fprintf (dump_file, "to\n ");
|
|
dump_value_range (dump_file, this);
|
|
fprintf (dump_file, "\n");
|
|
}
|
|
return;
|
|
}
|
|
|
|
if (other->legacy_mode_p ())
|
|
{
|
|
int_range<2> wider;
|
|
wider = *other;
|
|
irange_intersect (wider);
|
|
}
|
|
else
|
|
irange_intersect (*other);
|
|
}
|
|
|
|
// union_ for multi-ranges.
|
|
|
|
void
|
|
irange::irange_union (const irange &r)
|
|
{
|
|
gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ());
|
|
|
|
if (r.undefined_p () || varying_p ())
|
|
return;
|
|
|
|
if (undefined_p () || r.varying_p ())
|
|
{
|
|
operator= (r);
|
|
return;
|
|
}
|
|
|
|
// Do not worry about merging and such by reserving twice as many
|
|
// pairs as needed, and then simply sort the 2 ranges into this
|
|
// intermediate form.
|
|
//
|
|
// The intermediate result will have the property that the beginning
|
|
// of each range is <= the beginning of the next range. There may
|
|
// be overlapping ranges at this point. I.e. this would be valid
|
|
// [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
|
|
// contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
|
|
// the merge is performed.
|
|
//
|
|
// [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
|
|
auto_vec<tree, 20> res (m_num_ranges * 2 + r.m_num_ranges * 2);
|
|
unsigned i = 0, j = 0, k = 0;
|
|
|
|
while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2)
|
|
{
|
|
// lower of Xi and Xj is the lowest point.
|
|
if (wi::to_widest (m_base[i]) <= wi::to_widest (r.m_base[j]))
|
|
{
|
|
res.quick_push (m_base[i]);
|
|
res.quick_push (m_base[i + 1]);
|
|
k += 2;
|
|
i += 2;
|
|
}
|
|
else
|
|
{
|
|
res.quick_push (r.m_base[j]);
|
|
res.quick_push (r.m_base[j + 1]);
|
|
k += 2;
|
|
j += 2;
|
|
}
|
|
}
|
|
for ( ; i < m_num_ranges * 2; i += 2)
|
|
{
|
|
res.quick_push (m_base[i]);
|
|
res.quick_push (m_base[i + 1]);
|
|
k += 2;
|
|
}
|
|
for ( ; j < r.m_num_ranges * 2; j += 2)
|
|
{
|
|
res.quick_push (r.m_base[j]);
|
|
res.quick_push (r.m_base[j + 1]);
|
|
k += 2;
|
|
}
|
|
|
|
// Now normalize the vector removing any overlaps.
|
|
i = 2;
|
|
for (j = 2; j < k ; j += 2)
|
|
{
|
|
// Current upper+1 is >= lower bound next pair, then we merge ranges.
|
|
if (wi::to_widest (res[i - 1]) + 1 >= wi::to_widest (res[j]))
|
|
{
|
|
// New upper bounds is greater of current or the next one.
|
|
if (wi::to_widest (res[j + 1]) > wi::to_widest (res[i - 1]))
|
|
res[i - 1] = res[j + 1];
|
|
}
|
|
else
|
|
{
|
|
// This is a new distinct range, but no point in copying it
|
|
// if it is already in the right place.
|
|
if (i != j)
|
|
{
|
|
res[i++] = res[j];
|
|
res[i++] = res[j + 1];
|
|
}
|
|
else
|
|
i += 2;
|
|
}
|
|
}
|
|
|
|
// At this point, the vector should have i ranges, none overlapping.
|
|
// Now it simply needs to be copied, and if there are too many
|
|
// ranges, merge some. We wont do any analysis as to what the
|
|
// "best" merges are, simply combine the final ranges into one.
|
|
if (i > m_max_ranges * 2)
|
|
{
|
|
res[m_max_ranges * 2 - 1] = res[i - 1];
|
|
i = m_max_ranges * 2;
|
|
}
|
|
|
|
for (j = 0; j < i ; j++)
|
|
m_base[j] = res [j];
|
|
m_num_ranges = i / 2;
|
|
|
|
m_kind = VR_RANGE;
|
|
normalize_kind ();
|
|
|
|
if (flag_checking)
|
|
verify_range ();
|
|
}
|
|
|
|
// intersect for multi-ranges.
|
|
|
|
void
|
|
irange::irange_intersect (const irange &r)
|
|
{
|
|
gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ());
|
|
gcc_checking_assert (undefined_p () || r.undefined_p ()
|
|
|| range_compatible_p (type (), r.type ()));
|
|
|
|
if (undefined_p () || r.varying_p ())
|
|
return;
|
|
if (r.undefined_p ())
|
|
{
|
|
set_undefined ();
|
|
return;
|
|
}
|
|
if (varying_p ())
|
|
{
|
|
operator= (r);
|
|
return;
|
|
}
|
|
|
|
if (r.num_pairs () == 1)
|
|
{
|
|
// R cannot be undefined, use more efficent pair routine.
|
|
intersect (r.lower_bound(), r.upper_bound ());
|
|
return;
|
|
}
|
|
|
|
signop sign = TYPE_SIGN (TREE_TYPE(m_base[0]));
|
|
unsigned bld_pair = 0;
|
|
unsigned bld_lim = m_max_ranges;
|
|
int_range_max r2 (*this);
|
|
unsigned r2_lim = r2.num_pairs ();
|
|
unsigned i2 = 0;
|
|
for (unsigned i = 0; i < r.num_pairs (); )
|
|
{
|
|
// If r1's upper is < r2's lower, we can skip r1's pair.
|
|
tree ru = r.m_base[i * 2 + 1];
|
|
tree r2l = r2.m_base[i2 * 2];
|
|
if (wi::lt_p (wi::to_wide (ru), wi::to_wide (r2l), sign))
|
|
{
|
|
i++;
|
|
continue;
|
|
}
|
|
// Likewise, skip r2's pair if its excluded.
|
|
tree r2u = r2.m_base[i2 * 2 + 1];
|
|
tree rl = r.m_base[i * 2];
|
|
if (wi::lt_p (wi::to_wide (r2u), wi::to_wide (rl), sign))
|
|
{
|
|
i2++;
|
|
if (i2 < r2_lim)
|
|
continue;
|
|
// No more r2, break.
|
|
break;
|
|
}
|
|
|
|
// Must be some overlap. Find the highest of the lower bounds,
|
|
// and set it, unless the build limits lower bounds is already
|
|
// set.
|
|
if (bld_pair < bld_lim)
|
|
{
|
|
if (wi::ge_p (wi::to_wide (rl), wi::to_wide (r2l), sign))
|
|
m_base[bld_pair * 2] = rl;
|
|
else
|
|
m_base[bld_pair * 2] = r2l;
|
|
}
|
|
else
|
|
// Decrease and set a new upper.
|
|
bld_pair--;
|
|
|
|
// ...and choose the lower of the upper bounds.
|
|
if (wi::le_p (wi::to_wide (ru), wi::to_wide (r2u), sign))
|
|
{
|
|
m_base[bld_pair * 2 + 1] = ru;
|
|
bld_pair++;
|
|
// Move past the r1 pair and keep trying.
|
|
i++;
|
|
continue;
|
|
}
|
|
else
|
|
{
|
|
m_base[bld_pair * 2 + 1] = r2u;
|
|
bld_pair++;
|
|
i2++;
|
|
if (i2 < r2_lim)
|
|
continue;
|
|
// No more r2, break.
|
|
break;
|
|
}
|
|
// r2 has the higher lower bound.
|
|
}
|
|
|
|
// At the exit of this loop, it is one of 2 things:
|
|
// ran out of r1, or r2, but either means we are done.
|
|
m_num_ranges = bld_pair;
|
|
|
|
m_kind = VR_RANGE;
|
|
normalize_kind ();
|
|
|
|
if (flag_checking)
|
|
verify_range ();
|
|
}
|
|
|
|
// Multirange intersect for a specified wide_int [lb, ub] range.
|
|
|
|
void
|
|
irange::intersect (const wide_int& lb, const wide_int& ub)
|
|
{
|
|
// Undefined remains undefined.
|
|
if (undefined_p ())
|
|
return;
|
|
|
|
if (legacy_mode_p ())
|
|
{
|
|
intersect (int_range<1> (type (), lb, ub));
|
|
return;
|
|
}
|
|
|
|
tree range_type = type();
|
|
signop sign = TYPE_SIGN (range_type);
|
|
|
|
gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (lb));
|
|
gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (ub));
|
|
|
|
unsigned bld_index = 0;
|
|
unsigned pair_lim = num_pairs ();
|
|
for (unsigned i = 0; i < pair_lim; i++)
|
|
{
|
|
tree pairl = m_base[i * 2];
|
|
tree pairu = m_base[i * 2 + 1];
|
|
// Once UB is less than a pairs lower bound, we're done.
|
|
if (wi::lt_p (ub, wi::to_wide (pairl), sign))
|
|
break;
|
|
// if LB is greater than this pairs upper, this pair is excluded.
|
|
if (wi::lt_p (wi::to_wide (pairu), lb, sign))
|
|
continue;
|
|
|
|
// Must be some overlap. Find the highest of the lower bounds,
|
|
// and set it
|
|
if (wi::gt_p (lb, wi::to_wide (pairl), sign))
|
|
m_base[bld_index * 2] = wide_int_to_tree (range_type, lb);
|
|
else
|
|
m_base[bld_index * 2] = pairl;
|
|
|
|
// ...and choose the lower of the upper bounds and if the base pair
|
|
// has the lower upper bound, need to check next pair too.
|
|
if (wi::lt_p (ub, wi::to_wide (pairu), sign))
|
|
{
|
|
m_base[bld_index++ * 2 + 1] = wide_int_to_tree (range_type, ub);
|
|
break;
|
|
}
|
|
else
|
|
m_base[bld_index++ * 2 + 1] = pairu;
|
|
}
|
|
|
|
m_num_ranges = bld_index;
|
|
|
|
m_kind = VR_RANGE;
|
|
normalize_kind ();
|
|
|
|
if (flag_checking)
|
|
verify_range ();
|
|
}
|
|
// Signed 1-bits are strange. You can't subtract 1, because you can't
|
|
// represent the number 1. This works around that for the invert routine.
|
|
|
|
static wide_int inline
|
|
subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow)
|
|
{
|
|
if (TYPE_SIGN (type) == SIGNED)
|
|
return wi::add (x, -1, SIGNED, &overflow);
|
|
else
|
|
return wi::sub (x, 1, UNSIGNED, &overflow);
|
|
}
|
|
|
|
// The analogous function for adding 1.
|
|
|
|
static wide_int inline
|
|
add_one (const wide_int &x, tree type, wi::overflow_type &overflow)
|
|
{
|
|
if (TYPE_SIGN (type) == SIGNED)
|
|
return wi::sub (x, -1, SIGNED, &overflow);
|
|
else
|
|
return wi::add (x, 1, UNSIGNED, &overflow);
|
|
}
|
|
|
|
// Return the inverse of a range.
|
|
|
|
void
|
|
irange::invert ()
|
|
{
|
|
if (legacy_mode_p ())
|
|
{
|
|
// 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 (min (), max (), VR_ANTI_RANGE);
|
|
else if (m_kind == VR_ANTI_RANGE)
|
|
*this = value_range (min (), max ());
|
|
else
|
|
gcc_unreachable ();
|
|
return;
|
|
}
|
|
|
|
gcc_checking_assert (!undefined_p () && !varying_p ());
|
|
|
|
// We always need one more set of bounds to represent an inverse, so
|
|
// if we're at the limit, we can't properly represent things.
|
|
//
|
|
// For instance, to represent the inverse of a 2 sub-range set
|
|
// [5, 10][20, 30], we would need a 3 sub-range set
|
|
// [-MIN, 4][11, 19][31, MAX].
|
|
//
|
|
// In this case, return the most conservative thing.
|
|
//
|
|
// However, if any of the extremes of the range are -MIN/+MAX, we
|
|
// know we will not need an extra bound. For example:
|
|
//
|
|
// INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
|
|
// INVERT([-MIN,20][30,MAX]) => [21,29]
|
|
tree ttype = type ();
|
|
unsigned prec = TYPE_PRECISION (ttype);
|
|
signop sign = TYPE_SIGN (ttype);
|
|
wide_int type_min = wi::min_value (prec, sign);
|
|
wide_int type_max = wi::max_value (prec, sign);
|
|
if (m_num_ranges == m_max_ranges
|
|
&& lower_bound () != type_min
|
|
&& upper_bound () != type_max)
|
|
{
|
|
m_base[1] = wide_int_to_tree (ttype, type_max);
|
|
m_num_ranges = 1;
|
|
return;
|
|
}
|
|
// The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
|
|
// generate [-MIN, a-1][b+1, c-1][d+1, MAX].
|
|
//
|
|
// If there is an over/underflow in the calculation for any
|
|
// sub-range, we eliminate that subrange. This allows us to easily
|
|
// calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
|
|
// we eliminate the underflow, only [6, MAX] remains.
|
|
unsigned i = 0;
|
|
wi::overflow_type ovf;
|
|
// Construct leftmost range.
|
|
int_range_max orig_range (*this);
|
|
unsigned nitems = 0;
|
|
wide_int tmp;
|
|
// If this is going to underflow on the MINUS 1, don't even bother
|
|
// checking. This also handles subtracting one from an unsigned 0,
|
|
// which doesn't set the underflow bit.
|
|
if (type_min != orig_range.lower_bound ())
|
|
{
|
|
m_base[nitems++] = wide_int_to_tree (ttype, type_min);
|
|
tmp = subtract_one (orig_range.lower_bound (), ttype, ovf);
|
|
m_base[nitems++] = wide_int_to_tree (ttype, tmp);
|
|
if (ovf)
|
|
nitems = 0;
|
|
}
|
|
i++;
|
|
// Construct middle ranges if applicable.
|
|
if (orig_range.num_pairs () > 1)
|
|
{
|
|
unsigned j = i;
|
|
for (; j < (orig_range.num_pairs () * 2) - 1; j += 2)
|
|
{
|
|
// The middle ranges cannot have MAX/MIN, so there's no need
|
|
// to check for unsigned overflow on the +1 and -1 here.
|
|
tmp = wi::add (wi::to_wide (orig_range.m_base[j]), 1, sign, &ovf);
|
|
m_base[nitems++] = wide_int_to_tree (ttype, tmp);
|
|
tmp = subtract_one (wi::to_wide (orig_range.m_base[j + 1]),
|
|
ttype, ovf);
|
|
m_base[nitems++] = wide_int_to_tree (ttype, tmp);
|
|
if (ovf)
|
|
nitems -= 2;
|
|
}
|
|
i = j;
|
|
}
|
|
// Construct rightmost range.
|
|
//
|
|
// However, if this will overflow on the PLUS 1, don't even bother.
|
|
// This also handles adding one to an unsigned MAX, which doesn't
|
|
// set the overflow bit.
|
|
if (type_max != wi::to_wide (orig_range.m_base[i]))
|
|
{
|
|
tmp = add_one (wi::to_wide (orig_range.m_base[i]), ttype, ovf);
|
|
m_base[nitems++] = wide_int_to_tree (ttype, tmp);
|
|
m_base[nitems++] = wide_int_to_tree (ttype, type_max);
|
|
if (ovf)
|
|
nitems -= 2;
|
|
}
|
|
m_num_ranges = nitems / 2;
|
|
|
|
// We disallow undefined or varying coming in, so the result can
|
|
// only be a VR_RANGE.
|
|
gcc_checking_assert (m_kind == VR_RANGE);
|
|
|
|
if (flag_checking)
|
|
verify_range ();
|
|
}
|
|
|
|
static void
|
|
dump_bound_with_infinite_markers (FILE *file, tree bound)
|
|
{
|
|
tree type = TREE_TYPE (bound);
|
|
wide_int type_min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
|
|
wide_int type_max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
|
|
|
|
if (INTEGRAL_TYPE_P (type)
|
|
&& !TYPE_UNSIGNED (type)
|
|
&& TREE_CODE (bound) == INTEGER_CST
|
|
&& wi::to_wide (bound) == type_min
|
|
&& TYPE_PRECISION (type) != 1)
|
|
fprintf (file, "-INF");
|
|
else if (TREE_CODE (bound) == INTEGER_CST
|
|
&& wi::to_wide (bound) == type_max
|
|
&& TYPE_PRECISION (type) != 1)
|
|
fprintf (file, "+INF");
|
|
else
|
|
print_generic_expr (file, bound);
|
|
}
|
|
|
|
void
|
|
irange::dump (FILE *file) const
|
|
{
|
|
if (undefined_p ())
|
|
{
|
|
fprintf (file, "UNDEFINED");
|
|
return;
|
|
}
|
|
print_generic_expr (file, type ());
|
|
fprintf (file, " ");
|
|
if (varying_p ())
|
|
{
|
|
fprintf (file, "VARYING");
|
|
return;
|
|
}
|
|
if (legacy_mode_p ())
|
|
{
|
|
fprintf (file, "%s[", (m_kind == VR_ANTI_RANGE) ? "~" : "");
|
|
dump_bound_with_infinite_markers (file, min ());
|
|
fprintf (file, ", ");
|
|
dump_bound_with_infinite_markers (file, max ());
|
|
fprintf (file, "]");
|
|
return;
|
|
}
|
|
for (unsigned i = 0; i < m_num_ranges; ++i)
|
|
{
|
|
tree lb = m_base[i * 2];
|
|
tree ub = m_base[i * 2 + 1];
|
|
fprintf (file, "[");
|
|
dump_bound_with_infinite_markers (file, lb);
|
|
fprintf (file, ", ");
|
|
dump_bound_with_infinite_markers (file, ub);
|
|
fprintf (file, "]");
|
|
}
|
|
}
|
|
|
|
void
|
|
irange::debug () const
|
|
{
|
|
dump (stderr);
|
|
fprintf (stderr, "\n");
|
|
}
|
|
|
|
void
|
|
dump_value_range (FILE *file, const irange *vr)
|
|
{
|
|
vr->dump (file);
|
|
}
|
|
|
|
DEBUG_FUNCTION void
|
|
debug (const irange *vr)
|
|
{
|
|
dump_value_range (stderr, vr);
|
|
fprintf (stderr, "\n");
|
|
}
|
|
|
|
DEBUG_FUNCTION void
|
|
debug (const irange &vr)
|
|
{
|
|
debug (&vr);
|
|
}
|
|
|
|
DEBUG_FUNCTION void
|
|
debug (const value_range *vr)
|
|
{
|
|
dump_value_range (stderr, vr);
|
|
fprintf (stderr, "\n");
|
|
}
|
|
|
|
DEBUG_FUNCTION void
|
|
debug (const value_range &vr)
|
|
{
|
|
dump_value_range (stderr, &vr);
|
|
fprintf (stderr, "\n");
|
|
}
|
|
|
|
/* 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 irange *vr)
|
|
{
|
|
return (!vr->undefined_p ()
|
|
&& TREE_CODE (vr->min ()) == INTEGER_CST
|
|
&& TREE_CODE (vr->max ()) == INTEGER_CST);
|
|
}
|
|
|
|
/* 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;
|
|
}
|
|
|
|
// ?? These stubs are for ipa-prop.cc which use a value_range in a
|
|
// hash_traits. hash-traits.h defines an extern of gt_ggc_mx (T &)
|
|
// instead of picking up the gt_ggc_mx (T *) version.
|
|
void
|
|
gt_pch_nx (int_range<1> *&x)
|
|
{
|
|
return gt_pch_nx ((irange *) x);
|
|
}
|
|
|
|
void
|
|
gt_ggc_mx (int_range<1> *&x)
|
|
{
|
|
return gt_ggc_mx ((irange *) x);
|
|
}
|
|
|
|
#define DEFINE_INT_RANGE_INSTANCE(N) \
|
|
template int_range<N>::int_range(tree, tree, value_range_kind); \
|
|
template int_range<N>::int_range(tree_node *, \
|
|
const wide_int &, \
|
|
const wide_int &, \
|
|
value_range_kind); \
|
|
template int_range<N>::int_range(tree); \
|
|
template int_range<N>::int_range(const irange &); \
|
|
template int_range<N>::int_range(const int_range &); \
|
|
template int_range<N>& int_range<N>::operator= (const int_range &);
|
|
|
|
DEFINE_INT_RANGE_INSTANCE(1)
|
|
DEFINE_INT_RANGE_INSTANCE(2)
|
|
DEFINE_INT_RANGE_INSTANCE(3)
|
|
DEFINE_INT_RANGE_INSTANCE(255)
|
|
|
|
#if CHECKING_P
|
|
#include "selftest.h"
|
|
|
|
namespace selftest
|
|
{
|
|
#define INT(N) build_int_cst (integer_type_node, (N))
|
|
#define UINT(N) build_int_cstu (unsigned_type_node, (N))
|
|
#define UINT128(N) build_int_cstu (u128_type, (N))
|
|
#define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
|
|
#define SCHAR(N) build_int_cst (signed_char_type_node, (N))
|
|
|
|
static int_range<3>
|
|
build_range3 (int a, int b, int c, int d, int e, int f)
|
|
{
|
|
int_range<3> i1 (INT (a), INT (b));
|
|
int_range<3> i2 (INT (c), INT (d));
|
|
int_range<3> i3 (INT (e), INT (f));
|
|
i1.union_ (i2);
|
|
i1.union_ (i3);
|
|
return i1;
|
|
}
|
|
|
|
static void
|
|
range_tests_irange3 ()
|
|
{
|
|
typedef int_range<3> int_range3;
|
|
int_range3 r0, r1, r2;
|
|
int_range3 i1, i2, i3;
|
|
|
|
// ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
|
|
r0 = int_range3 (INT (10), INT (20));
|
|
r1 = int_range3 (INT (5), INT (8));
|
|
r0.union_ (r1);
|
|
r1 = int_range3 (INT (1), INT (3));
|
|
r0.union_ (r1);
|
|
ASSERT_TRUE (r0 == build_range3 (1, 3, 5, 8, 10, 20));
|
|
|
|
// [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
|
|
r1 = int_range3 (INT (-5), INT (0));
|
|
r0.union_ (r1);
|
|
ASSERT_TRUE (r0 == build_range3 (-5, 3, 5, 8, 10, 20));
|
|
|
|
// [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
|
|
r1 = int_range3 (INT (50), INT (60));
|
|
r0 = int_range3 (INT (10), INT (20));
|
|
r0.union_ (int_range3 (INT (30), INT (40)));
|
|
r0.union_ (r1);
|
|
ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
|
|
// [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
|
|
r1 = int_range3 (INT (70), INT (80));
|
|
r0.union_ (r1);
|
|
|
|
r2 = build_range3 (10, 20, 30, 40, 50, 60);
|
|
r2.union_ (int_range3 (INT (70), INT (80)));
|
|
ASSERT_TRUE (r0 == r2);
|
|
|
|
// [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
|
|
r0 = build_range3 (10, 20, 30, 40, 50, 60);
|
|
r1 = int_range3 (INT (6), INT (35));
|
|
r0.union_ (r1);
|
|
r1 = int_range3 (INT (6), INT (40));
|
|
r1.union_ (int_range3 (INT (50), INT (60)));
|
|
ASSERT_TRUE (r0 == r1);
|
|
|
|
// [10,20][30,40][50,60] U [6,60] => [6,60].
|
|
r0 = build_range3 (10, 20, 30, 40, 50, 60);
|
|
r1 = int_range3 (INT (6), INT (60));
|
|
r0.union_ (r1);
|
|
ASSERT_TRUE (r0 == int_range3 (INT (6), INT (60)));
|
|
|
|
// [10,20][30,40][50,60] U [6,70] => [6,70].
|
|
r0 = build_range3 (10, 20, 30, 40, 50, 60);
|
|
r1 = int_range3 (INT (6), INT (70));
|
|
r0.union_ (r1);
|
|
ASSERT_TRUE (r0 == int_range3 (INT (6), INT (70)));
|
|
|
|
// [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
|
|
r0 = build_range3 (10, 20, 30, 40, 50, 60);
|
|
r1 = int_range3 (INT (35), INT (70));
|
|
r0.union_ (r1);
|
|
r1 = int_range3 (INT (10), INT (20));
|
|
r1.union_ (int_range3 (INT (30), INT (70)));
|
|
ASSERT_TRUE (r0 == r1);
|
|
|
|
// [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
|
|
r0 = build_range3 (10, 20, 30, 40, 50, 60);
|
|
r1 = int_range3 (INT (15), INT (35));
|
|
r0.union_ (r1);
|
|
r1 = int_range3 (INT (10), INT (40));
|
|
r1.union_ (int_range3 (INT (50), INT (60)));
|
|
ASSERT_TRUE (r0 == r1);
|
|
|
|
// [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
|
|
r0 = build_range3 (10, 20, 30, 40, 50, 60);
|
|
r1 = int_range3 (INT (35), INT (35));
|
|
r0.union_ (r1);
|
|
ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
|
|
}
|
|
|
|
static void
|
|
range_tests_int_range_max ()
|
|
{
|
|
int_range_max big;
|
|
unsigned int nrange;
|
|
|
|
// Build a huge multi-range range.
|
|
for (nrange = 0; nrange < 50; ++nrange)
|
|
{
|
|
int_range<1> tmp (INT (nrange*10), INT (nrange*10 + 5));
|
|
big.union_ (tmp);
|
|
}
|
|
ASSERT_TRUE (big.num_pairs () == nrange);
|
|
|
|
// Verify that we can copy it without loosing precision.
|
|
int_range_max copy (big);
|
|
ASSERT_TRUE (copy.num_pairs () == nrange);
|
|
|
|
// Inverting it should produce one more sub-range.
|
|
big.invert ();
|
|
ASSERT_TRUE (big.num_pairs () == nrange + 1);
|
|
|
|
int_range<1> tmp (INT (5), INT (37));
|
|
big.intersect (tmp);
|
|
ASSERT_TRUE (big.num_pairs () == 4);
|
|
|
|
// Test that [10,10][20,20] does NOT contain 15.
|
|
{
|
|
int_range_max i1 (build_int_cst (integer_type_node, 10),
|
|
build_int_cst (integer_type_node, 10));
|
|
int_range_max i2 (build_int_cst (integer_type_node, 20),
|
|
build_int_cst (integer_type_node, 20));
|
|
i1.union_ (i2);
|
|
ASSERT_FALSE (i1.contains_p (build_int_cst (integer_type_node, 15)));
|
|
}
|
|
}
|
|
|
|
static void
|
|
range_tests_legacy ()
|
|
{
|
|
// Test truncating copy to int_range<1>.
|
|
int_range<3> big = build_range3 (10, 20, 30, 40, 50, 60);
|
|
int_range<1> small = big;
|
|
ASSERT_TRUE (small == int_range<1> (INT (10), INT (60)));
|
|
|
|
// Test truncating copy to int_range<2>.
|
|
int_range<2> medium = big;
|
|
ASSERT_TRUE (!medium.undefined_p ());
|
|
|
|
// Test that a truncating copy of [MIN,20][22,40][80,MAX]
|
|
// ends up as a conservative anti-range of ~[21,21].
|
|
big = int_range<3> (vrp_val_min (integer_type_node), INT (20));
|
|
big.union_ (int_range<1> (INT (22), INT (40)));
|
|
big.union_ (int_range<1> (INT (80), vrp_val_max (integer_type_node)));
|
|
small = big;
|
|
ASSERT_TRUE (small == int_range<1> (INT (21), INT (21), VR_ANTI_RANGE));
|
|
|
|
// Copying a legacy symbolic to an int_range should normalize the
|
|
// symbolic at copy time.
|
|
{
|
|
tree ssa = make_ssa_name (integer_type_node);
|
|
value_range legacy_range (ssa, INT (25));
|
|
int_range<2> copy = legacy_range;
|
|
ASSERT_TRUE (copy == int_range<2> (vrp_val_min (integer_type_node),
|
|
INT (25)));
|
|
|
|
// Test that copying ~[abc_23, abc_23] to a multi-range yields varying.
|
|
legacy_range = value_range (ssa, ssa, VR_ANTI_RANGE);
|
|
copy = legacy_range;
|
|
ASSERT_TRUE (copy.varying_p ());
|
|
}
|
|
|
|
// VARYING of different sizes should not be equal.
|
|
tree big_type = build_nonstandard_integer_type (32, 1);
|
|
tree small_type = build_nonstandard_integer_type (16, 1);
|
|
int_range_max r0 (big_type);
|
|
int_range_max r1 (small_type);
|
|
ASSERT_TRUE (r0 != r1);
|
|
value_range vr0 (big_type);
|
|
int_range_max vr1 (small_type);
|
|
ASSERT_TRUE (vr0 != vr1);
|
|
}
|
|
|
|
// Simulate -fstrict-enums where the domain of a type is less than the
|
|
// underlying type.
|
|
|
|
static void
|
|
range_tests_strict_enum ()
|
|
{
|
|
// The enum can only hold [0, 3].
|
|
tree rtype = copy_node (unsigned_type_node);
|
|
TYPE_MIN_VALUE (rtype) = build_int_cstu (rtype, 0);
|
|
TYPE_MAX_VALUE (rtype) = build_int_cstu (rtype, 3);
|
|
|
|
// Test that even though vr1 covers the strict enum domain ([0, 3]),
|
|
// it does not cover the domain of the underlying type.
|
|
int_range<1> vr1 (build_int_cstu (rtype, 0), build_int_cstu (rtype, 1));
|
|
int_range<1> vr2 (build_int_cstu (rtype, 2), build_int_cstu (rtype, 3));
|
|
vr1.union_ (vr2);
|
|
ASSERT_TRUE (vr1 == int_range<1> (build_int_cstu (rtype, 0),
|
|
build_int_cstu (rtype, 3)));
|
|
ASSERT_FALSE (vr1.varying_p ());
|
|
|
|
// Test that copying to a multi-range does not change things.
|
|
int_range<2> ir1 (vr1);
|
|
ASSERT_TRUE (ir1 == vr1);
|
|
ASSERT_FALSE (ir1.varying_p ());
|
|
|
|
// The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
|
|
vr1 = int_range<1> (TYPE_MIN_VALUE (rtype), TYPE_MAX_VALUE (rtype));
|
|
ir1 = vr1;
|
|
ASSERT_TRUE (ir1 == vr1);
|
|
ASSERT_FALSE (ir1.varying_p ());
|
|
}
|
|
|
|
static void
|
|
range_tests_misc ()
|
|
{
|
|
tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
|
|
int_range<1> i1, i2, i3;
|
|
int_range<1> r0, r1, rold;
|
|
|
|
// Test 1-bit signed integer union.
|
|
// [-1,-1] U [0,0] = VARYING.
|
|
tree one_bit_type = build_nonstandard_integer_type (1, 0);
|
|
tree one_bit_min = vrp_val_min (one_bit_type);
|
|
tree one_bit_max = vrp_val_max (one_bit_type);
|
|
{
|
|
int_range<2> min (one_bit_min, one_bit_min);
|
|
int_range<2> max (one_bit_max, one_bit_max);
|
|
max.union_ (min);
|
|
ASSERT_TRUE (max.varying_p ());
|
|
}
|
|
|
|
// Test inversion of 1-bit signed integers.
|
|
{
|
|
int_range<2> min (one_bit_min, one_bit_min);
|
|
int_range<2> max (one_bit_max, one_bit_max);
|
|
int_range<2> t;
|
|
t = min;
|
|
t.invert ();
|
|
ASSERT_TRUE (t == max);
|
|
t = max;
|
|
t.invert ();
|
|
ASSERT_TRUE (t == min);
|
|
}
|
|
|
|
// Test that NOT(255) is [0..254] in 8-bit land.
|
|
int_range<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE);
|
|
ASSERT_TRUE (not_255 == int_range<1> (UCHAR (0), UCHAR (254)));
|
|
|
|
// Test that NOT(0) is [1..255] in 8-bit land.
|
|
int_range<1> not_zero = range_nonzero (unsigned_char_type_node);
|
|
ASSERT_TRUE (not_zero == int_range<1> (UCHAR (1), UCHAR (255)));
|
|
|
|
// Check that [0,127][0x..ffffff80,0x..ffffff]
|
|
// => ~[128, 0x..ffffff7f].
|
|
r0 = int_range<1> (UINT128 (0), UINT128 (127));
|
|
tree high = build_minus_one_cst (u128_type);
|
|
// low = -1 - 127 => 0x..ffffff80.
|
|
tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127));
|
|
r1 = int_range<1> (low, high); // [0x..ffffff80, 0x..ffffffff]
|
|
// r0 = [0,127][0x..ffffff80,0x..fffffff].
|
|
r0.union_ (r1);
|
|
// r1 = [128, 0x..ffffff7f].
|
|
r1 = int_range<1> (UINT128(128),
|
|
fold_build2 (MINUS_EXPR, u128_type,
|
|
build_minus_one_cst (u128_type),
|
|
UINT128(128)));
|
|
r0.invert ();
|
|
ASSERT_TRUE (r0 == r1);
|
|
|
|
r0.set_varying (integer_type_node);
|
|
tree minint = wide_int_to_tree (integer_type_node, r0.lower_bound ());
|
|
tree maxint = wide_int_to_tree (integer_type_node, r0.upper_bound ());
|
|
|
|
r0.set_varying (short_integer_type_node);
|
|
|
|
r0.set_varying (unsigned_type_node);
|
|
tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ());
|
|
|
|
// Check that ~[0,5] => [6,MAX] for unsigned int.
|
|
r0 = int_range<1> (UINT (0), UINT (5));
|
|
r0.invert ();
|
|
ASSERT_TRUE (r0 == int_range<1> (UINT(6), maxuint));
|
|
|
|
// Check that ~[10,MAX] => [0,9] for unsigned int.
|
|
r0 = int_range<1> (UINT(10), maxuint);
|
|
r0.invert ();
|
|
ASSERT_TRUE (r0 == int_range<1> (UINT (0), UINT (9)));
|
|
|
|
// Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
|
|
r0 = int_range<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE);
|
|
r1 = int_range<1> (UINT128(6), build_minus_one_cst (u128_type));
|
|
ASSERT_TRUE (r0 == r1);
|
|
|
|
// Check that [~5] is really [-MIN,4][6,MAX].
|
|
r0 = int_range<1> (INT (5), INT (5), VR_ANTI_RANGE);
|
|
r1 = int_range<1> (minint, INT (4));
|
|
r1.union_ (int_range<1> (INT (6), maxint));
|
|
ASSERT_FALSE (r1.undefined_p ());
|
|
ASSERT_TRUE (r0 == r1);
|
|
|
|
r1 = int_range<1> (INT (5), INT (5));
|
|
int_range<1> r2 (r1);
|
|
ASSERT_TRUE (r1 == r2);
|
|
|
|
r1 = int_range<1> (INT (5), INT (10));
|
|
|
|
r1 = int_range<1> (integer_type_node,
|
|
wi::to_wide (INT (5)), wi::to_wide (INT (10)));
|
|
ASSERT_TRUE (r1.contains_p (INT (7)));
|
|
|
|
r1 = int_range<1> (SCHAR (0), SCHAR (20));
|
|
ASSERT_TRUE (r1.contains_p (SCHAR(15)));
|
|
ASSERT_FALSE (r1.contains_p (SCHAR(300)));
|
|
|
|
// NOT([10,20]) ==> [-MIN,9][21,MAX].
|
|
r0 = r1 = int_range<1> (INT (10), INT (20));
|
|
r2 = int_range<1> (minint, INT(9));
|
|
r2.union_ (int_range<1> (INT(21), maxint));
|
|
ASSERT_FALSE (r2.undefined_p ());
|
|
r1.invert ();
|
|
ASSERT_TRUE (r1 == r2);
|
|
// Test that NOT(NOT(x)) == x.
|
|
r2.invert ();
|
|
ASSERT_TRUE (r0 == r2);
|
|
|
|
// Test that booleans and their inverse work as expected.
|
|
r0 = range_zero (boolean_type_node);
|
|
ASSERT_TRUE (r0 == int_range<1> (build_zero_cst (boolean_type_node),
|
|
build_zero_cst (boolean_type_node)));
|
|
r0.invert ();
|
|
ASSERT_TRUE (r0 == int_range<1> (build_one_cst (boolean_type_node),
|
|
build_one_cst (boolean_type_node)));
|
|
|
|
// Make sure NULL and non-NULL of pointer types work, and that
|
|
// inverses of them are consistent.
|
|
tree voidp = build_pointer_type (void_type_node);
|
|
r0 = range_zero (voidp);
|
|
r1 = r0;
|
|
r0.invert ();
|
|
r0.invert ();
|
|
ASSERT_TRUE (r0 == r1);
|
|
|
|
// [10,20] U [15, 30] => [10, 30].
|
|
r0 = int_range<1> (INT (10), INT (20));
|
|
r1 = int_range<1> (INT (15), INT (30));
|
|
r0.union_ (r1);
|
|
ASSERT_TRUE (r0 == int_range<1> (INT (10), INT (30)));
|
|
|
|
// [15,40] U [] => [15,40].
|
|
r0 = int_range<1> (INT (15), INT (40));
|
|
r1.set_undefined ();
|
|
r0.union_ (r1);
|
|
ASSERT_TRUE (r0 == int_range<1> (INT (15), INT (40)));
|
|
|
|
// [10,20] U [10,10] => [10,20].
|
|
r0 = int_range<1> (INT (10), INT (20));
|
|
r1 = int_range<1> (INT (10), INT (10));
|
|
r0.union_ (r1);
|
|
ASSERT_TRUE (r0 == int_range<1> (INT (10), INT (20)));
|
|
|
|
// [10,20] U [9,9] => [9,20].
|
|
r0 = int_range<1> (INT (10), INT (20));
|
|
r1 = int_range<1> (INT (9), INT (9));
|
|
r0.union_ (r1);
|
|
ASSERT_TRUE (r0 == int_range<1> (INT (9), INT (20)));
|
|
|
|
// [10,20] ^ [15,30] => [15,20].
|
|
r0 = int_range<1> (INT (10), INT (20));
|
|
r1 = int_range<1> (INT (15), INT (30));
|
|
r0.intersect (r1);
|
|
ASSERT_TRUE (r0 == int_range<1> (INT (15), INT (20)));
|
|
|
|
// Test the internal sanity of wide_int's wrt HWIs.
|
|
ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node),
|
|
TYPE_SIGN (boolean_type_node))
|
|
== wi::uhwi (1, TYPE_PRECISION (boolean_type_node)));
|
|
|
|
// Test zero_p().
|
|
r0 = int_range<1> (INT (0), INT (0));
|
|
ASSERT_TRUE (r0.zero_p ());
|
|
|
|
// Test nonzero_p().
|
|
r0 = int_range<1> (INT (0), INT (0));
|
|
r0.invert ();
|
|
ASSERT_TRUE (r0.nonzero_p ());
|
|
|
|
// test legacy interaction
|
|
// r0 = ~[1,1]
|
|
r0 = int_range<1> (UINT (1), UINT (1), VR_ANTI_RANGE);
|
|
// r1 = ~[3,3]
|
|
r1 = int_range<1> (UINT (3), UINT (3), VR_ANTI_RANGE);
|
|
|
|
// vv = [0,0][2,2][4, MAX]
|
|
int_range<3> vv = r0;
|
|
vv.intersect (r1);
|
|
|
|
ASSERT_TRUE (vv.contains_p (UINT (2)));
|
|
ASSERT_TRUE (vv.num_pairs () == 3);
|
|
|
|
// create r0 as legacy [1,1]
|
|
r0 = int_range<1> (UINT (1), UINT (1));
|
|
// And union it with [0,0][2,2][4,MAX] multi range
|
|
r0.union_ (vv);
|
|
// The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
|
|
ASSERT_TRUE (r0.contains_p (UINT (2)));
|
|
}
|
|
|
|
void
|
|
range_tests ()
|
|
{
|
|
range_tests_legacy ();
|
|
range_tests_irange3 ();
|
|
range_tests_int_range_max ();
|
|
range_tests_strict_enum ();
|
|
range_tests_misc ();
|
|
}
|
|
|
|
} // namespace selftest
|
|
|
|
#endif // CHECKING_P
|