Google Git
Sign in
gnu / gcc / 74f67ba3dcfd09209bed6265772d5fd9007ea605 / . / gcc / value-range.cc
blob: 70375f7abf9b5a0c94b3861f9b981484c6d890a7 [file] [log] [blame]
/* Support routines for value ranges.
Copyright (C) 2019-2024 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 "value-range-pretty-print.h"
#include "fold-const.h"
#include "gimple-range.h"
void
irange::accept (const vrange_visitor &v) const
{
v.visit (*this);
}
void
unsupported_range::accept (const vrange_visitor &v) const
{
v.visit (*this);
}
// Convenience function only available for integers and pointers.
wide_int
Value_Range::lower_bound () const
{
if (is_a <irange> (*m_vrange))
return as_a <irange> (*m_vrange).lower_bound ();
gcc_unreachable ();
}
// Convenience function only available for integers and pointers.
wide_int
Value_Range::upper_bound () const
{
if (is_a <irange> (*m_vrange))
return as_a <irange> (*m_vrange).upper_bound ();
gcc_unreachable ();
}
void
Value_Range::dump (FILE *out) const
{
if (m_vrange)
m_vrange->dump (out);
else
fprintf (out, "NULL");
}
DEBUG_FUNCTION void
debug (const Value_Range &r)
{
r.dump (stderr);
fprintf (stderr, "\n");
}
DEBUG_FUNCTION void
debug (const irange_bitmask &bm)
{
bm.dump (stderr);
fprintf (stderr, "\n");
}
// Default vrange definitions.
bool
vrange::contains_p (tree) const
{
return varying_p ();
}
bool
vrange::singleton_p (tree *) const
{
return false;
}
void
vrange::set (tree min, tree, value_range_kind)
{
set_varying (TREE_TYPE (min));
}
tree
vrange::type () const
{
return void_type_node;
}
bool
vrange::supports_type_p (const_tree) const
{
return false;
}
void
vrange::set_undefined ()
{
m_kind = VR_UNDEFINED;
}
void
vrange::set_varying (tree)
{
m_kind = VR_VARYING;
}
bool
vrange::union_ (const vrange &r)
{
if (r.undefined_p () || varying_p ())
return false;
if (undefined_p () || r.varying_p ())
{
operator= (r);
return true;
}
gcc_unreachable ();
return false;
}
bool
vrange::intersect (const vrange &r)
{
if (undefined_p () || r.varying_p ())
return false;
if (r.undefined_p ())
{
set_undefined ();
return true;
}
if (varying_p ())
{
operator= (r);
return true;
}
gcc_unreachable ();
return false;
}
bool
vrange::zero_p () const
{
return false;
}
bool
vrange::nonzero_p () const
{
return false;
}
void
vrange::set_nonzero (tree type)
{
set_varying (type);
}
void
vrange::set_zero (tree type)
{
set_varying (type);
}
void
vrange::set_nonnegative (tree type)
{
set_varying (type);
}
bool
vrange::fits_p (const vrange &) const
{
return true;
}
// Assignment operator for generic ranges. Copying incompatible types
// is not allowed.
vrange &
vrange::operator= (const vrange &src)
{
if (is_a <irange> (src))
as_a <irange> (*this) = as_a <irange> (src);
else if (is_a <frange> (src))
as_a <frange> (*this) = as_a <frange> (src);
else
{
gcc_checking_assert (is_a <unsupported_range> (src));
m_kind = src.m_kind;
}
return *this;
}
// Equality operator for generic ranges.
bool
vrange::operator== (const vrange &src) const
{
if (is_a <irange> (src))
return as_a <irange> (*this) == as_a <irange> (src);
if (is_a <frange> (src))
return as_a <frange> (*this) == as_a <frange> (src);
gcc_unreachable ();
}
// Wrapper for vrange_printer to dump a range to a file.
void
vrange::dump (FILE *file) const
{
pretty_printer buffer;
pp_needs_newline (&buffer) = true;
buffer.buffer->stream = file;
vrange_printer vrange_pp (&buffer);
this->accept (vrange_pp);
pp_flush (&buffer);
}
void
irange_bitmask::dump (FILE *file) const
{
char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p;
pretty_printer buffer;
pp_needs_newline (&buffer) = true;
buffer.buffer->stream = file;
pp_string (&buffer, "MASK ");
unsigned len_mask, len_val;
if (print_hex_buf_size (m_mask, &len_mask)
| print_hex_buf_size (m_value, &len_val))
p = XALLOCAVEC (char, MAX (len_mask, len_val));
else
p = buf;
print_hex (m_mask, p);
pp_string (&buffer, p);
pp_string (&buffer, " VALUE ");
print_hex (m_value, p);
pp_string (&buffer, p);
pp_flush (&buffer);
}
namespace inchash
{
void
add_vrange (const vrange &v, inchash::hash &hstate,
unsigned int)
{
if (v.undefined_p ())
{
hstate.add_int (VR_UNDEFINED);
return;
}
// Types are ignored throughout to inhibit two ranges being equal
// but having different hash values. This can happen when two
// ranges are equal and their types are different (but
// types_compatible_p is true).
if (is_a <irange> (v))
{
const irange &r = as_a <irange> (v);
if (r.varying_p ())
hstate.add_int (VR_VARYING);
else
hstate.add_int (VR_RANGE);
for (unsigned i = 0; i < r.num_pairs (); ++i)
{
hstate.add_wide_int (r.lower_bound (i));
hstate.add_wide_int (r.upper_bound (i));
}
irange_bitmask bm = r.get_bitmask ();
hstate.add_wide_int (bm.value ());
hstate.add_wide_int (bm.mask ());
return;
}
if (is_a <frange> (v))
{
const frange &r = as_a <frange> (v);
if (r.known_isnan ())
hstate.add_int (VR_NAN);
else
{
hstate.add_int (r.varying_p () ? VR_VARYING : VR_RANGE);
hstate.add_real_value (r.lower_bound ());
hstate.add_real_value (r.upper_bound ());
}
nan_state nan = r.get_nan_state ();
hstate.add_int (nan.pos_p ());
hstate.add_int (nan.neg_p ());
return;
}
gcc_unreachable ();
}
} //namespace inchash
bool
irange::nonnegative_p () const
{
return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
}
bool
irange::nonpositive_p () const
{
return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
}
bool
irange::supports_type_p (const_tree type) const
{
return supports_p (type);
}
// Return TRUE if R fits in THIS.
bool
irange::fits_p (const vrange &r) const
{
return m_max_ranges >= as_a <irange> (r).num_pairs ();
}
void
irange::set_nonnegative (tree type)
{
set (type,
wi::zero (TYPE_PRECISION (type)),
wi::to_wide (TYPE_MAX_VALUE (type)));
}
void
frange::accept (const vrange_visitor &v) const
{
v.visit (*this);
}
// Flush denormal endpoints to the appropriate 0.0.
void
frange::flush_denormals_to_zero ()
{
if (undefined_p () || known_isnan ())
return;
machine_mode mode = TYPE_MODE (type ());
// Flush [x, -DENORMAL] to [x, -0.0].
if (real_isdenormal (&m_max, mode) && real_isneg (&m_max))
{
if (HONOR_SIGNED_ZEROS (m_type))
m_max = dconstm0;
else
m_max = dconst0;
}
// Flush [+DENORMAL, x] to [+0.0, x].
if (real_isdenormal (&m_min, mode) && !real_isneg (&m_min))
m_min = dconst0;
}
// Setter for franges.
void
frange::set (tree type,
const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
const nan_state &nan, value_range_kind kind)
{
switch (kind)
{
case VR_UNDEFINED:
set_undefined ();
return;
case VR_VARYING:
case VR_ANTI_RANGE:
set_varying (type);
return;
case VR_RANGE:
break;
default:
gcc_unreachable ();
}
gcc_checking_assert (!real_isnan (&min) && !real_isnan (&max));
m_kind = kind;
m_type = type;
m_min = min;
m_max = max;
if (HONOR_NANS (m_type))
{
m_pos_nan = nan.pos_p ();
m_neg_nan = nan.neg_p ();
}
else
{
m_pos_nan = false;
m_neg_nan = false;
}
if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (m_type)))
{
if (real_iszero (&m_min, 1))
m_min.sign = 0;
if (real_iszero (&m_max, 1))
m_max.sign = 0;
}
else if (!HONOR_SIGNED_ZEROS (m_type))
{
if (real_iszero (&m_max, 1))
m_max.sign = 0;
if (real_iszero (&m_min, 0))
m_min.sign = 1;
}
// For -ffinite-math-only we can drop ranges outside the
// representable numbers to min/max for the type.
if (!HONOR_INFINITIES (m_type))
{
REAL_VALUE_TYPE min_repr = frange_val_min (m_type);
REAL_VALUE_TYPE max_repr = frange_val_max (m_type);
if (real_less (&m_min, &min_repr))
m_min = min_repr;
else if (real_less (&max_repr, &m_min))
m_min = max_repr;
if (real_less (&max_repr, &m_max))
m_max = max_repr;
else if (real_less (&m_max, &min_repr))
m_max = min_repr;
}
// Check for swapped ranges.
gcc_checking_assert (real_compare (LE_EXPR, &min, &max));
normalize_kind ();
}
// Setter for an frange defaulting the NAN possibility to +-NAN when
// HONOR_NANS.
void
frange::set (tree type,
const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
value_range_kind kind)
{
set (type, min, max, nan_state (true), kind);
}
void
frange::set (tree min, tree max, value_range_kind kind)
{
set (TREE_TYPE (min),
*TREE_REAL_CST_PTR (min), *TREE_REAL_CST_PTR (max), kind);
}
// Normalize range to VARYING or UNDEFINED, or vice versa. Return
// TRUE if anything changed.
//
// A range with no known properties can be dropped to VARYING.
// Similarly, a VARYING with any properties should be dropped to a
// VR_RANGE. Normalizing ranges upon changing them ensures there is
// only one representation for a given range.
bool
frange::normalize_kind ()
{
if (m_kind == VR_RANGE
&& frange_val_is_min (m_min, m_type)
&& frange_val_is_max (m_max, m_type))
{
if (!HONOR_NANS (m_type) || (m_pos_nan && m_neg_nan))
{
set_varying (m_type);
return true;
}
}
else if (m_kind == VR_VARYING)
{
if (HONOR_NANS (m_type) && (!m_pos_nan || !m_neg_nan))
{
m_kind = VR_RANGE;
m_min = frange_val_min (m_type);
m_max = frange_val_max (m_type);
if (flag_checking)
verify_range ();
return true;
}
}
else if (m_kind == VR_NAN && !m_pos_nan && !m_neg_nan)
set_undefined ();
return false;
}
// Union or intersect the zero endpoints of two ranges. For example:
// [-0, x] U [+0, x] => [-0, x]
// [ x, -0] U [ x, +0] => [ x, +0]
// [-0, x] ^ [+0, x] => [+0, x]
// [ x, -0] ^ [ x, +0] => [ x, -0]
//
// UNION_P is true when performing a union, or false when intersecting.
bool
frange::combine_zeros (const frange &r, bool union_p)
{
gcc_checking_assert (!undefined_p () && !known_isnan ());
bool changed = false;
if (real_iszero (&m_min) && real_iszero (&r.m_min)
&& real_isneg (&m_min) != real_isneg (&r.m_min))
{
m_min.sign = union_p;
changed = true;
}
if (real_iszero (&m_max) && real_iszero (&r.m_max)
&& real_isneg (&m_max) != real_isneg (&r.m_max))
{
m_max.sign = !union_p;
changed = true;
}
// If the signs are swapped, the resulting range is empty.
if (m_min.sign == 0 && m_max.sign == 1)
{
if (maybe_isnan ())
m_kind = VR_NAN;
else
set_undefined ();
changed = true;
}
return changed;
}
// Union two ranges when one is known to be a NAN.
bool
frange::union_nans (const frange &r)
{
gcc_checking_assert (known_isnan () || r.known_isnan ());
bool changed = false;
if (known_isnan () && m_kind != r.m_kind)
{
m_kind = r.m_kind;
m_min = r.m_min;
m_max = r.m_max;
changed = true;
}
if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
{
m_pos_nan |= r.m_pos_nan;
m_neg_nan |= r.m_neg_nan;
changed = true;
}
if (changed)
{
normalize_kind ();
return true;
}
return false;
}
bool
frange::union_ (const vrange &v)
{
const frange &r = as_a <frange> (v);
if (r.undefined_p () || varying_p ())
return false;
if (undefined_p () || r.varying_p ())
{
*this = r;
return true;
}
// Combine NAN info.
if (known_isnan () || r.known_isnan ())
return union_nans (r);
bool changed = false;
if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
{
m_pos_nan |= r.m_pos_nan;
m_neg_nan |= r.m_neg_nan;
changed = true;
}
// Combine endpoints.
if (real_less (&r.m_min, &m_min))
{
m_min = r.m_min;
changed = true;
}
if (real_less (&m_max, &r.m_max))
{
m_max = r.m_max;
changed = true;
}
if (HONOR_SIGNED_ZEROS (m_type))
changed |= combine_zeros (r, true);
changed |= normalize_kind ();
return changed;
}
// Intersect two ranges when one is known to be a NAN.
bool
frange::intersect_nans (const frange &r)
{
gcc_checking_assert (known_isnan () || r.known_isnan ());
m_pos_nan &= r.m_pos_nan;
m_neg_nan &= r.m_neg_nan;
if (maybe_isnan ())
m_kind = VR_NAN;
else
set_undefined ();
if (flag_checking)
verify_range ();
return true;
}
bool
frange::intersect (const vrange &v)
{
const frange &r = as_a <frange> (v);
if (undefined_p () || r.varying_p ())
return false;
if (r.undefined_p ())
{
set_undefined ();
return true;
}
if (varying_p ())
{
*this = r;
return true;
}
// Combine NAN info.
if (known_isnan () || r.known_isnan ())
return intersect_nans (r);
bool changed = false;
if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
{
m_pos_nan &= r.m_pos_nan;
m_neg_nan &= r.m_neg_nan;
changed = true;
}
// Combine endpoints.
if (real_less (&m_min, &r.m_min))
{
m_min = r.m_min;
changed = true;
}
if (real_less (&r.m_max, &m_max))
{
m_max = r.m_max;
changed = true;
}
// If the endpoints are swapped, the resulting range is empty.
if (real_less (&m_max, &m_min))
{
if (maybe_isnan ())
m_kind = VR_NAN;
else
set_undefined ();
if (flag_checking)
verify_range ();
return true;
}
if (HONOR_SIGNED_ZEROS (m_type))
changed |= combine_zeros (r, false);
changed |= normalize_kind ();
return changed;
}
frange &
frange::operator= (const frange &src)
{
m_kind = src.m_kind;
m_type = src.m_type;
m_min = src.m_min;
m_max = src.m_max;
m_pos_nan = src.m_pos_nan;
m_neg_nan = src.m_neg_nan;
if (flag_checking)
verify_range ();
return *this;
}
bool
frange::operator== (const frange &src) const
{
if (m_kind == src.m_kind)
{
if (undefined_p ())
return true;
if (varying_p ())
return types_compatible_p (m_type, src.m_type);
bool nan1 = known_isnan ();
bool nan2 = src.known_isnan ();
if (nan1 || nan2)
{
if (nan1 && nan2)
return (m_pos_nan == src.m_pos_nan
&& m_neg_nan == src.m_neg_nan);
return false;
}
return (real_identical (&m_min, &src.m_min)
&& real_identical (&m_max, &src.m_max)
&& m_pos_nan == src.m_pos_nan
&& m_neg_nan == src.m_neg_nan
&& types_compatible_p (m_type, src.m_type));
}
return false;
}
// Return TRUE if range contains R.
bool
frange::contains_p (const REAL_VALUE_TYPE &r) const
{
gcc_checking_assert (m_kind != VR_ANTI_RANGE);
if (undefined_p ())
return false;
if (varying_p ())
return true;
if (real_isnan (&r))
{
// No NAN in range.
if (!m_pos_nan && !m_neg_nan)
return false;
// Both +NAN and -NAN are present.
if (m_pos_nan && m_neg_nan)
return true;
return m_neg_nan == r.sign;
}
if (known_isnan ())
return false;
if (real_compare (GE_EXPR, &r, &m_min) && real_compare (LE_EXPR, &r, &m_max))
{
// Make sure the signs are equal for signed zeros.
if (HONOR_SIGNED_ZEROS (m_type) && real_iszero (&r))
return r.sign == m_min.sign || r.sign == m_max.sign;
return true;
}
return false;
}
// If range is a singleton, place it in RESULT and return TRUE. If
// RESULT is NULL, just return TRUE.
//
// A NAN can never be a singleton.
bool
frange::internal_singleton_p (REAL_VALUE_TYPE *result) const
{
if (m_kind == VR_RANGE && real_identical (&m_min, &m_max))
{
// Return false for any singleton that may be a NAN.
if (HONOR_NANS (m_type) && maybe_isnan ())
return false;
if (MODE_COMPOSITE_P (TYPE_MODE (m_type)))
{
// For IBM long doubles, if the value is +-Inf or is exactly
// representable in double, the other double could be +0.0
// or -0.0. Since this means there is more than one way to
// represent a value, return false to avoid propagating it.
// See libgcc/config/rs6000/ibm-ldouble-format for details.
if (real_isinf (&m_min))
return false;
REAL_VALUE_TYPE r;
real_convert (&r, DFmode, &m_min);
if (real_identical (&r, &m_min))
return false;
}
if (result)
*result = m_min;
return true;
}
return false;
}
bool
frange::singleton_p (tree *result) const
{
if (internal_singleton_p ())
{
if (result)
*result = build_real (m_type, m_min);
return true;
}
return false;
}
bool
frange::singleton_p (REAL_VALUE_TYPE &r) const
{
return internal_singleton_p (&r);
}
bool
frange::supports_type_p (const_tree type) const
{
return supports_p (type);
}
void
frange::verify_range ()
{
if (!undefined_p ())
gcc_checking_assert (HONOR_NANS (m_type) || !maybe_isnan ());
switch (m_kind)
{
case VR_UNDEFINED:
gcc_checking_assert (!m_type);
return;
case VR_VARYING:
gcc_checking_assert (m_type);
gcc_checking_assert (frange_val_is_min (m_min, m_type));
gcc_checking_assert (frange_val_is_max (m_max, m_type));
if (HONOR_NANS (m_type))
gcc_checking_assert (m_pos_nan && m_neg_nan);
else
gcc_checking_assert (!m_pos_nan && !m_neg_nan);
return;
case VR_RANGE:
gcc_checking_assert (m_type);
break;
case VR_NAN:
gcc_checking_assert (m_type);
gcc_checking_assert (m_pos_nan || m_neg_nan);
return;
default:
gcc_unreachable ();
}
// NANs cannot appear in the endpoints of a range.
gcc_checking_assert (!real_isnan (&m_min) && !real_isnan (&m_max));
// Make sure we don't have swapped ranges.
gcc_checking_assert (!real_less (&m_max, &m_min));
// [ +0.0, -0.0 ] is nonsensical.
gcc_checking_assert (!(real_iszero (&m_min, 0) && real_iszero (&m_max, 1)));
// If all the properties are clear, we better not span the entire
// domain, because that would make us varying.
if (m_pos_nan && m_neg_nan)
gcc_checking_assert (!frange_val_is_min (m_min, m_type)
|| !frange_val_is_max (m_max, m_type));
}
// We can't do much with nonzeros yet.
void
frange::set_nonzero (tree type)
{
set_varying (type);
}
// We can't do much with nonzeros yet.
bool
frange::nonzero_p () const
{
return false;
}
// Set range to [+0.0, +0.0] if honoring signed zeros, or [0.0, 0.0]
// otherwise.
void
frange::set_zero (tree type)
{
if (HONOR_SIGNED_ZEROS (type))
{
set (type, dconstm0, dconst0);
clear_nan ();
}
else
set (type, dconst0, dconst0);
}
// Return TRUE for any zero regardless of sign.
bool
frange::zero_p () const
{
return (m_kind == VR_RANGE
&& real_iszero (&m_min)
&& real_iszero (&m_max));
}
// Set the range to non-negative numbers, that is [+0.0, +INF].
//
// The NAN in the resulting range (if HONOR_NANS) has a varying sign
// as there are no guarantees in IEEE 754 wrt to the sign of a NAN,
// except for copy, abs, and copysign. It is the responsibility of
// the caller to set the NAN's sign if desired.
void
frange::set_nonnegative (tree type)
{
set (type, dconst0, frange_val_max (type));
}
// Here we copy between any two irange's.
irange &
irange::operator= (const irange &src)
{
int needed = src.num_pairs ();
maybe_resize (needed);
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_type = src.m_type;
m_kind = src.m_kind;
m_bitmask = src.m_bitmask;
if (m_max_ranges == 1)
normalize_kind ();
if (flag_checking)
verify_range ();
return *this;
}
value_range_kind
get_legacy_range (const irange &r, tree &min, tree &max)
{
if (r.undefined_p ())
{
min = NULL_TREE;
max = NULL_TREE;
return VR_UNDEFINED;
}
tree type = r.type ();
if (r.varying_p ())
{
min = wide_int_to_tree (type, r.lower_bound ());
max = wide_int_to_tree (type, r.upper_bound ());
return VR_VARYING;
}
unsigned int precision = TYPE_PRECISION (type);
signop sign = TYPE_SIGN (type);
if (r.num_pairs () > 1
&& precision > 1
&& r.lower_bound () == wi::min_value (precision, sign)
&& r.upper_bound () == wi::max_value (precision, sign))
{
int_range<3> inv (r);
inv.invert ();
min = wide_int_to_tree (type, inv.lower_bound (0));
max = wide_int_to_tree (type, inv.upper_bound (0));
return VR_ANTI_RANGE;
}
min = wide_int_to_tree (type, r.lower_bound ());
max = wide_int_to_tree (type, r.upper_bound ());
return VR_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 type, const wide_int &min, const wide_int &max,
value_range_kind kind)
{
unsigned prec = TYPE_PRECISION (type);
signop sign = TYPE_SIGN (type);
wide_int min_value = wi::min_value (prec, sign);
wide_int max_value = wi::max_value (prec, sign);
m_type = type;
m_bitmask.set_unknown (prec);
if (kind == VR_RANGE)
{
m_base[0] = min;
m_base[1] = max;
m_num_ranges = 1;
if (min == min_value && max == max_value)
m_kind = VR_VARYING;
else
m_kind = VR_RANGE;
}
else
{
gcc_checking_assert (kind == VR_ANTI_RANGE);
gcc_checking_assert (m_max_ranges > 1);
m_kind = VR_UNDEFINED;
m_num_ranges = 0;
wi::overflow_type ovf;
wide_int lim;
if (sign == SIGNED)
lim = wi::add (min, -1, sign, &ovf);
else
lim = wi::sub (min, 1, sign, &ovf);
if (!ovf)
{
m_kind = VR_RANGE;
m_base[0] = min_value;
m_base[1] = lim;
++m_num_ranges;
}
if (sign == SIGNED)
lim = wi::sub (max, -1, sign, &ovf);
else
lim = wi::add (max, 1, sign, &ovf);
if (!ovf)
{
m_kind = VR_RANGE;
m_base[m_num_ranges * 2] = lim;
m_base[m_num_ranges * 2 + 1] = max_value;
++m_num_ranges;
}
}
if (flag_checking)
verify_range ();
}
void
irange::set (tree min, tree max, value_range_kind kind)
{
if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max))
{
set_varying (TREE_TYPE (min));
return;
}
gcc_checking_assert (TREE_CODE (min) == INTEGER_CST);
gcc_checking_assert (TREE_CODE (max) == INTEGER_CST);
return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
}
// Check the validity of the range.
void
irange::verify_range ()
{
gcc_checking_assert (m_discriminator == VR_IRANGE);
if (m_kind == VR_UNDEFINED)
{
gcc_checking_assert (m_num_ranges == 0);
return;
}
gcc_checking_assert (m_num_ranges <= m_max_ranges);
// Legacy allowed these to represent VARYING for unknown types.
// Leave this in for now, until all users are converted. Eventually
// we should abort in set_varying.
if (m_kind == VR_VARYING && m_type == error_mark_node)
return;
unsigned prec = TYPE_PRECISION (m_type);
if (m_kind == VR_VARYING)
{
gcc_checking_assert (m_bitmask.unknown_p ());
gcc_checking_assert (m_num_ranges == 1);
gcc_checking_assert (varying_compatible_p ());
gcc_checking_assert (lower_bound ().get_precision () == prec);
gcc_checking_assert (upper_bound ().get_precision () == prec);
return;
}
gcc_checking_assert (m_num_ranges != 0);
gcc_checking_assert (!varying_compatible_p ());
for (unsigned i = 0; i < m_num_ranges; ++i)
{
wide_int lb = lower_bound (i);
wide_int ub = upper_bound (i);
gcc_checking_assert (lb.get_precision () == prec);
gcc_checking_assert (ub.get_precision () == prec);
int c = wi::cmp (lb, ub, TYPE_SIGN (m_type));
gcc_checking_assert (c == 0 || c == -1);
}
m_bitmask.verify_mask ();
}
bool
irange::operator== (const irange &other) const
{
if (m_num_ranges != other.m_num_ranges)
return false;
if (m_num_ranges == 0)
return true;
signop sign1 = TYPE_SIGN (type ());
signop sign2 = TYPE_SIGN (other.type ());
for (unsigned i = 0; i < m_num_ranges; ++i)
{
widest_int lb = widest_int::from (lower_bound (i), sign1);
widest_int ub = widest_int::from (upper_bound (i), sign1);
widest_int lb_other = widest_int::from (other.lower_bound (i), sign2);
widest_int ub_other = widest_int::from (other.upper_bound (i), sign2);
if (lb != lb_other || ub != ub_other)
return false;
}
irange_bitmask bm1 = get_bitmask ();
irange_bitmask bm2 = other.get_bitmask ();
widest_int tmp1 = widest_int::from (bm1.mask (), sign1);
widest_int tmp2 = widest_int::from (bm2.mask (), sign2);
if (tmp1 != tmp2)
return false;
if (bm1.unknown_p ())
return true;
tmp1 = widest_int::from (bm1.value (), sign1);
tmp2 = widest_int::from (bm2.value (), sign2);
return tmp1 == tmp2;
}
/* If range is a singleton, place it in RESULT and return TRUE. */
bool
irange::singleton_p (tree *result) const
{
if (num_pairs () == 1 && lower_bound () == upper_bound ())
{
if (result)
*result = wide_int_to_tree (type (), lower_bound ());
return true;
}
return false;
}
bool
irange::singleton_p (wide_int &w) const
{
if (num_pairs () == 1 && lower_bound () == upper_bound ())
{
w = lower_bound ();
return true;
}
return false;
}
/* Return 1 if CST is inside value range.
0 if CST is not inside value range.
Benchmark compile/20001226-1.c compilation time after changing this
function. */
bool
irange::contains_p (const wide_int &cst) const
{
if (undefined_p ())
return false;
// See if we can exclude CST based on the known 0 bits.
if (!m_bitmask.unknown_p ()
&& cst != 0
&& wi::bit_and (m_bitmask.get_nonzero_bits (), cst) == 0)
return false;
signop sign = TYPE_SIGN (type ());
for (unsigned r = 0; r < m_num_ranges; ++r)
{
if (wi::lt_p (cst, lower_bound (r), sign))
return false;
if (wi::le_p (cst, upper_bound (r), sign))
return true;
}
return false;
}
// Perform an efficient union with R when both ranges have only a single pair.
// Excluded are VARYING and UNDEFINED ranges.
bool
irange::irange_single_pair_union (const irange &r)
{
gcc_checking_assert (!undefined_p () && !varying_p ());
gcc_checking_assert (!r.undefined_p () && !varying_p ());
signop sign = TYPE_SIGN (m_type);
// Check if current lower bound is also the new lower bound.
if (wi::le_p (m_base[0], r.m_base[0], sign))
{
// If current upper bound is new upper bound, we're done.
if (wi::le_p (r.m_base[1], m_base[1], sign))
return union_bitmask (r);
// Otherwise R has the new upper bound.
// Check for overlap/touching ranges, or single target range.
if (m_max_ranges == 1
|| (widest_int::from (m_base[1], sign) + 1
>= widest_int::from (r.m_base[0], TYPE_SIGN (r.m_type))))
m_base[1] = r.m_base[1];
else
{
// This is a dual range result.
m_base[2] = r.m_base[0];
m_base[3] = r.m_base[1];
m_num_ranges = 2;
}
// The range has been altered, so normalize it even if nothing
// changed in the mask.
if (!union_bitmask (r))
normalize_kind ();
if (flag_checking)
verify_range ();
return true;
}
// Set the new lower bound to R's lower bound.
wide_int lb = m_base[0];
m_base[0] = r.m_base[0];
// If R fully contains THIS range, just set the upper bound.
if (wi::ge_p (r.m_base[1], m_base[1], sign))
m_base[1] = r.m_base[1];
// Check for overlapping ranges, or target limited to a single range.
else if (m_max_ranges == 1
|| (widest_int::from (r.m_base[1], TYPE_SIGN (r.m_type)) + 1
>= widest_int::from (lb, sign)))
;
else
{
// Left with 2 pairs.
m_num_ranges = 2;
m_base[2] = lb;
m_base[3] = m_base[1];
m_base[1] = r.m_base[1];
}
// The range has been altered, so normalize it even if nothing
// changed in the mask.
if (!union_bitmask (r))
normalize_kind ();
if (flag_checking)
verify_range ();
return true;
}
// Append R to this range, knowing that R occurs after all of these subranges.
// Return TRUE as something must have changed.
bool
irange::union_append (const irange &r)
{
// Check if the first range in R is an immmediate successor to the last
// range, ths requiring a merge.
signop sign = TYPE_SIGN (m_type);
wide_int lb = r.lower_bound ();
wide_int ub = upper_bound ();
unsigned start = 0;
if (widest_int::from (ub, sign) + 1
== widest_int::from (lb, sign))
{
m_base[m_num_ranges * 2 - 1] = r.m_base[1];
start = 1;
}
maybe_resize (m_num_ranges + r.m_num_ranges - start);
for ( ; start < r.m_num_ranges; start++)
{
// Merge the last ranges if it exceeds the maximum size.
if (m_num_ranges + 1 > m_max_ranges)
{
m_base[m_max_ranges * 2 - 1] = r.m_base[r.m_num_ranges * 2 - 1];
break;
}
m_base[m_num_ranges * 2] = r.m_base[start * 2];
m_base[m_num_ranges * 2 + 1] = r.m_base[start * 2 + 1];
m_num_ranges++;
}
if (!union_bitmask (r))
normalize_kind ();
if (flag_checking)
verify_range ();
return true;
}
// Return TRUE if anything changes.
bool
irange::union_ (const vrange &v)
{
const irange &r = as_a <irange> (v);
if (r.undefined_p ())
return false;
if (undefined_p ())
{
operator= (r);
if (flag_checking)
verify_range ();
return true;
}
if (varying_p ())
return false;
if (r.varying_p ())
{
set_varying (type ());
return true;
}
// Special case one range union one range.
if (m_num_ranges == 1 && r.m_num_ranges == 1)
return irange_single_pair_union (r);
signop sign = TYPE_SIGN (m_type);
// Check for an append to the end.
if (m_kind == VR_RANGE && wi::gt_p (r.lower_bound (), upper_bound (), sign))
return union_append (r);
// If this ranges fully contains R, then we need do nothing.
if (irange_contains_p (r))
return union_bitmask (r);
// 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
// constraint : -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<wide_int, 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 (widest_int::from (m_base[i], sign)
<= widest_int::from (r.m_base[j], sign))
{
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 (widest_int::from (res[i - 1], sign) + 1
>= widest_int::from (res[j], sign))
{
// New upper bounds is greater of current or the next one.
if (widest_int::from (res[j + 1], sign)
> widest_int::from (res[i - 1], sign))
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.
maybe_resize (i / 2);
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;
// The range has been altered, so normalize it even if nothing
// changed in the mask.
if (!union_bitmask (r))
normalize_kind ();
if (flag_checking)
verify_range ();
return true;
}
// Return TRUE if THIS fully contains R. No undefined or varying cases.
bool
irange::irange_contains_p (const irange &r) const
{
gcc_checking_assert (!undefined_p () && !varying_p ());
gcc_checking_assert (!r.undefined_p () && !varying_p ());
// In order for THIS to fully contain R, all of the pairs within R must
// be fully contained by the pairs in this object.
signop sign = TYPE_SIGN (m_type);
unsigned ri = 0;
unsigned i = 0;
wide_int rl = r.m_base[0];
wide_int ru = r.m_base[1];
wide_int l = m_base[0];
wide_int u = m_base[1];
while (1)
{
// If r is contained within this range, move to the next R
if (wi::ge_p (rl, l, sign)
&& wi::le_p (ru, u, sign))
{
// This pair is OK, Either done, or bump to the next.
if (++ri >= r.num_pairs ())
return true;
rl = r.m_base[ri * 2];
ru = r.m_base[ri * 2 + 1];
continue;
}
// Otherwise, check if this's pair occurs before R's.
if (wi::lt_p (u, rl, sign))
{
// There's still at least one pair of R left.
if (++i >= num_pairs ())
return false;
l = m_base[i * 2];
u = m_base[i * 2 + 1];
continue;
}
return false;
}
return false;
}
// Return TRUE if anything changes.
bool
irange::intersect (const vrange &v)
{
const irange &r = as_a <irange> (v);
gcc_checking_assert (undefined_p () || r.undefined_p ()
|| range_compatible_p (type (), r.type ()));
if (undefined_p ())
return false;
if (r.undefined_p ())
{
set_undefined ();
return true;
}
if (r.varying_p ())
return false;
if (varying_p ())
{
operator= (r);
return true;
}
if (r.num_pairs () == 1)
{
bool res = intersect (r.lower_bound (), r.upper_bound ());
if (undefined_p ())
return true;
res |= intersect_bitmask (r);
if (res)
normalize_kind ();
return res;
}
// If R fully contains this, then intersection will change nothing.
if (r.irange_contains_p (*this))
return intersect_bitmask (r);
// ?? We could probably come up with something smarter than the
// worst case scenario here.
int needed = num_pairs () + r.num_pairs ();
maybe_resize (needed);
signop sign = TYPE_SIGN (m_type);
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.
wide_int ru = r.m_base[i * 2 + 1];
wide_int r2l = r2.m_base[i2 * 2];
if (wi::lt_p (ru, r2l, sign))
{
i++;
continue;
}
// Likewise, skip r2's pair if its excluded.
wide_int r2u = r2.m_base[i2 * 2 + 1];
wide_int rl = r.m_base[i * 2];
if (wi::lt_p (r2u, 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 (rl, 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 (ru, 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;
if (m_num_ranges == 0)
{
set_undefined ();
return true;
}
m_kind = VR_RANGE;
// The range has been altered, so normalize it even if nothing
// changed in the mask.
if (!intersect_bitmask (r))
normalize_kind ();
if (flag_checking)
verify_range ();
return true;
}
// Multirange intersect for a specified wide_int [lb, ub] range.
// Return TRUE if intersect changed anything.
//
// NOTE: It is the caller's responsibility to intersect the mask.
bool
irange::intersect (const wide_int& lb, const wide_int& ub)
{
// Undefined remains undefined.
if (undefined_p ())
return false;
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));
// If this range is fully contained, then intersection will do nothing.
if (wi::ge_p (lower_bound (), lb, sign)
&& wi::le_p (upper_bound (), ub, sign))
return false;
unsigned bld_index = 0;
unsigned pair_lim = num_pairs ();
for (unsigned i = 0; i < pair_lim; i++)
{
wide_int pairl = m_base[i * 2];
wide_int pairu = m_base[i * 2 + 1];
// Once UB is less than a pairs lower bound, we're done.
if (wi::lt_p (ub, pairl, sign))
break;
// if LB is greater than this pairs upper, this pair is excluded.
if (wi::lt_p (pairu, lb, sign))
continue;
// Must be some overlap. Find the highest of the lower bounds,
// and set it
if (wi::gt_p (lb, pairl, sign))
m_base[bld_index * 2] = 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, pairu, sign))
{
m_base[bld_index++ * 2 + 1] = ub;
break;
}
else
m_base[bld_index++ * 2 + 1] = pairu;
}
m_num_ranges = bld_index;
if (m_num_ranges == 0)
{
set_undefined ();
return true;
}
m_kind = VR_RANGE;
// The caller must normalize and verify the range, as the bitmask
// still needs to be handled.
return true;
}
// 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 ()
{
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);
m_bitmask.set_unknown (prec);
// At this point, we need one extra sub-range to represent the
// inverse.
maybe_resize (m_num_ranges + 1);
// 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++] = type_min;
tmp = subtract_one (orig_range.lower_bound (), ttype, ovf);
m_base[nitems++] = 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 (orig_range.m_base[j], 1, sign, &ovf);
m_base[nitems++] = tmp;
tmp = subtract_one (orig_range.m_base[j + 1], ttype, ovf);
m_base[nitems++] = 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 != orig_range.m_base[i])
{
tmp = add_one (orig_range.m_base[i], ttype, ovf);
m_base[nitems++] = tmp;
m_base[nitems++] = 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 ();
}
// Return the bitmask inherent in the range.
irange_bitmask
irange::get_bitmask_from_range () const
{
unsigned prec = TYPE_PRECISION (type ());
wide_int min = lower_bound ();
wide_int max = upper_bound ();
// All the bits of a singleton are known.
if (min == max)
{
wide_int mask = wi::zero (prec);
wide_int value = lower_bound ();
return irange_bitmask (value, mask);
}
wide_int xorv = min ^ max;
if (xorv != 0)
xorv = wi::mask (prec - wi::clz (xorv), false, prec);
return irange_bitmask (wi::zero (prec), min | xorv);
}
// Remove trailing ranges that this bitmask indicates can't exist.
void
irange_bitmask::adjust_range (irange &r) const
{
if (unknown_p () || r.undefined_p ())
return;
int_range_max range;
tree type = r.type ();
int prec = TYPE_PRECISION (type);
// If there are trailing zeros, create a range representing those bits.
gcc_checking_assert (m_mask != 0);
int z = wi::ctz (m_mask);
if (z)
{
wide_int ub = (wi::one (prec) << z) - 1;
range = int_range<5> (type, wi::zero (prec), ub);
// Then remove the specific value these bits contain from the range.
wide_int value = m_value & ub;
range.intersect (int_range<2> (type, value, value, VR_ANTI_RANGE));
// Inverting produces a list of ranges which can be valid.
range.invert ();
// And finally select R from only those valid values.
r.intersect (range);
return;
}
}
// If the mask can be trivially converted to a range, do so and
// return TRUE.
bool
irange::set_range_from_bitmask ()
{
gcc_checking_assert (!undefined_p ());
if (m_bitmask.unknown_p ())
return false;
// If all the bits are known, this is a singleton.
if (m_bitmask.mask () == 0)
{
set (m_type, m_bitmask.value (), m_bitmask.value ());
return true;
}
unsigned popcount = wi::popcount (m_bitmask.get_nonzero_bits ());
// If we have only one bit set in the mask, we can figure out the
// range immediately.
if (popcount == 1)
{
// Make sure we don't pessimize the range.
if (!contains_p (m_bitmask.get_nonzero_bits ()))
return false;
bool has_zero = contains_zero_p (*this);
wide_int nz = m_bitmask.get_nonzero_bits ();
set (m_type, nz, nz);
m_bitmask.set_nonzero_bits (nz);
if (has_zero)
{
int_range<2> zero;
zero.set_zero (type ());
union_ (zero);
}
if (flag_checking)
verify_range ();
return true;
}
else if (popcount == 0)
{
set_zero (type ());
return true;
}
return false;
}
void
irange::update_bitmask (const irange_bitmask &bm)
{
gcc_checking_assert (!undefined_p ());
// Drop VARYINGs with known bits to a plain range.
if (m_kind == VR_VARYING && !bm.unknown_p ())
m_kind = VR_RANGE;
m_bitmask = bm;
if (!set_range_from_bitmask ())
normalize_kind ();
if (flag_checking)
verify_range ();
}
// Return the bitmask of known bits that includes the bitmask inherent
// in the range.
irange_bitmask
irange::get_bitmask () const
{
gcc_checking_assert (!undefined_p ());
// The mask inherent in the range is calculated on-demand. For
// example, [0,255] does not have known bits set by default. This
// saves us considerable time, because setting it at creation incurs
// a large penalty for irange::set. At the time of writing there
// was a 5% slowdown in VRP if we kept the mask precisely up to date
// at all times. Instead, we default to -1 and set it when
// explicitly requested. However, this function will always return
// the correct mask.
//
// This also means that the mask may have a finer granularity than
// the range and thus contradict it. Think of the mask as an
// enhancement to the range. For example:
//
// [3, 1000] MASK 0xfffffffe VALUE 0x0
//
// 3 is in the range endpoints, but is excluded per the known 0 bits
// in the mask.
//
// See also the note in irange_bitmask::intersect.
irange_bitmask bm = get_bitmask_from_range ();
if (!m_bitmask.unknown_p ())
bm.intersect (m_bitmask);
return bm;
}
// Set the nonzero bits in R into THIS. Return TRUE and
// normalize the range if anything changed.
void
irange::set_nonzero_bits (const wide_int &bits)
{
gcc_checking_assert (!undefined_p ());
irange_bitmask bm (wi::zero (TYPE_PRECISION (type ())), bits);
update_bitmask (bm);
}
// Return the nonzero bits in R.
wide_int
irange::get_nonzero_bits () const
{
gcc_checking_assert (!undefined_p ());
irange_bitmask bm = get_bitmask ();
return bm.value () | bm.mask ();
}
// Intersect the bitmask in R into THIS and normalize the range.
// Return TRUE if the intersection changed anything.
bool
irange::intersect_bitmask (const irange &r)
{
gcc_checking_assert (!undefined_p () && !r.undefined_p ());
if (m_bitmask == r.m_bitmask)
return false;
irange_bitmask bm = get_bitmask ();
irange_bitmask save = bm;
if (!bm.intersect (r.get_bitmask ()))
return false;
m_bitmask = bm;
// Updating m_bitmask may still yield a semantic bitmask (as
// returned by get_bitmask) which is functionally equivalent to what
// we originally had. In which case, there's still no change.
if (save == get_bitmask ())
return false;
if (!set_range_from_bitmask ())
normalize_kind ();
m_bitmask.adjust_range (*this);
if (flag_checking)
verify_range ();
return true;
}
// Union the bitmask in R into THIS. Return TRUE and normalize the
// range if anything changed.
bool
irange::union_bitmask (const irange &r)
{
gcc_checking_assert (!undefined_p () && !r.undefined_p ());
if (m_bitmask == r.m_bitmask)
return false;
irange_bitmask bm = get_bitmask ();
irange_bitmask save = bm;
if (!bm.union_ (r.get_bitmask ()))
return false;
m_bitmask = bm;
// Updating m_bitmask may still yield a semantic bitmask (as
// returned by get_bitmask) which is functionally equivalent to what
// we originally had. In which case, there's still no change.
if (save == get_bitmask ())
return false;
// No need to call set_range_from_mask, because we'll never
// narrow the range. Besides, it would cause endless recursion
// because of the union_ in set_range_from_mask.
normalize_kind ();
return true;
}
void
irange_bitmask::verify_mask () const
{
gcc_assert (m_value.get_precision () == m_mask.get_precision ());
}
void
dump_value_range (FILE *file, const vrange *vr)
{
vr->dump (file);
}
DEBUG_FUNCTION void
debug (const vrange *vr)
{
dump_value_range (stderr, vr);
fprintf (stderr, "\n");
}
DEBUG_FUNCTION void
debug (const vrange &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");
}
/* 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;
}
void
gt_ggc_mx (irange *x)
{
if (!x->undefined_p ())
gt_ggc_mx (x->m_type);
}
void
gt_pch_nx (irange *x)
{
if (!x->undefined_p ())
gt_pch_nx (x->m_type);
}
void
gt_pch_nx (irange *x, gt_pointer_operator op, void *cookie)
{
for (unsigned i = 0; i < x->m_num_ranges; ++i)
{
op (&x->m_base[i * 2], NULL, cookie);
op (&x->m_base[i * 2 + 1], NULL, cookie);
}
}
void
gt_ggc_mx (frange *x)
{
gt_ggc_mx (x->m_type);
}
void
gt_pch_nx (frange *x)
{
gt_pch_nx (x->m_type);
}
void
gt_pch_nx (frange *x, gt_pointer_operator op, void *cookie)
{
op (&x->m_type, NULL, cookie);
}
void
gt_ggc_mx (vrange *x)
{
if (is_a <irange> (*x))
return gt_ggc_mx ((irange *) x);
if (is_a <frange> (*x))
return gt_ggc_mx ((frange *) x);
gcc_unreachable ();
}
void
gt_pch_nx (vrange *x)
{
if (is_a <irange> (*x))
return gt_pch_nx ((irange *) x);
if (is_a <frange> (*x))
return gt_pch_nx ((frange *) x);
gcc_unreachable ();
}
void
gt_pch_nx (vrange *x, gt_pointer_operator op, void *cookie)
{
if (is_a <irange> (*x))
gt_pch_nx ((irange *) x, op, cookie);
else if (is_a <frange> (*x))
gt_pch_nx ((frange *) x, op, cookie);
else
gcc_unreachable ();
}
#define DEFINE_INT_RANGE_INSTANCE(N) \
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"
#define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
#define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
#define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
namespace selftest
{
static int_range<2>
range (tree type, int a, int b, value_range_kind kind = VR_RANGE)
{
wide_int w1, w2;
if (TYPE_UNSIGNED (type))
{
w1 = wi::uhwi (a, TYPE_PRECISION (type));
w2 = wi::uhwi (b, TYPE_PRECISION (type));
}
else
{
w1 = wi::shwi (a, TYPE_PRECISION (type));
w2 = wi::shwi (b, TYPE_PRECISION (type));
}
return int_range<2> (type, w1, w2, kind);
}
static int_range<2>
range_int (int a, int b, value_range_kind kind = VR_RANGE)
{
return range (integer_type_node, a, b, kind);
}
static int_range<2>
range_uint (int a, int b, value_range_kind kind = VR_RANGE)
{
return range (unsigned_type_node, a, b, kind);
}
static int_range<2>
range_uint128 (int a, int b, value_range_kind kind = VR_RANGE)
{
tree u128_type_node = build_nonstandard_integer_type (128, 1);
return range (u128_type_node, a, b, kind);
}
static int_range<2>
range_uchar (int a, int b, value_range_kind kind = VR_RANGE)
{
return range (unsigned_char_type_node, a, b, kind);
}
static int_range<2>
range_char (int a, int b, value_range_kind kind = VR_RANGE)
{
return range (signed_char_type_node, a, b, kind);
}
static int_range<3>
build_range3 (int a, int b, int c, int d, int e, int f)
{
int_range<3> i1 = range_int (a, b);
int_range<3> i2 = range_int (c, d);
int_range<3> i3 = range_int (e, f);
i1.union_ (i2);
i1.union_ (i3);
return i1;
}
static void
range_tests_irange3 ()
{
int_range<3> r0, r1, r2;
int_range<3> i1, i2, i3;
// ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
r0 = range_int (10, 20);
r1 = range_int (5, 8);
r0.union_ (r1);
r1 = range_int (1, 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 = range_int (-5, 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 = range_int (50, 60);
r0 = range_int (10, 20);
r0.union_ (range_int (30, 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 = range_int (70, 80);
r0.union_ (r1);
r2 = build_range3 (10, 20, 30, 40, 50, 60);
r2.union_ (range_int (70, 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 = range_int (6, 35);
r0.union_ (r1);
r1 = range_int (6, 40);
r1.union_ (range_int (50, 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 = range_int (6, 60);
r0.union_ (r1);
ASSERT_TRUE (r0 == range_int (6, 60));
// [10,20][30,40][50,60] U [6,70] => [6,70].
r0 = build_range3 (10, 20, 30, 40, 50, 60);
r1 = range_int (6, 70);
r0.union_ (r1);
ASSERT_TRUE (r0 == range_int (6, 70));
// [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
r0 = build_range3 (10, 20, 30, 40, 50, 60);
r1 = range_int (35, 70);
r0.union_ (r1);
r1 = range_int (10, 20);
r1.union_ (range_int (30, 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 = range_int (15, 35);
r0.union_ (r1);
r1 = range_int (10, 40);
r1.union_ (range_int (50, 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 = range_int (35, 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 = range_int (nrange*10, 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 = range_int (5, 37);
big.intersect (tmp);
ASSERT_TRUE (big.num_pairs () == 4);
// Test that [10,10][20,20] does NOT contain 15.
{
int_range_max i1 = range_int (10, 10);
int_range_max i2 = range_int (20, 20);
i1.union_ (i2);
ASSERT_FALSE (i1.contains_p (INT (15)));
}
}
// 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 = range (rtype, 0, 1);
int_range<1> vr2 = range (rtype, 2, 3);
vr1.union_ (vr2);
ASSERT_TRUE (vr1 == range (rtype, 0, 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<2> (rtype,
wi::to_wide (TYPE_MIN_VALUE (rtype)),
wi::to_wide (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<2> i1, i2, i3;
int_range<2> 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);
wide_int one_bit_min = irange_val_min (one_bit_type);
wide_int one_bit_max = irange_val_max (one_bit_type);
{
int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max);
max.union_ (min);
ASSERT_TRUE (max.varying_p ());
}
// Test that we can set a range of true+false for a 1-bit signed int.
r0 = range_true_and_false (one_bit_type);
// Test inversion of 1-bit signed integers.
{
int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
int_range<2> max = int_range<2> (one_bit_type, 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 = range_uchar (255, 255, VR_ANTI_RANGE);
ASSERT_TRUE (not_255 == range_uchar (0, 254));
// Test that NOT(0) is [1..255] in 8-bit land.
int_range<2> not_zero = range_nonzero (unsigned_char_type_node);
ASSERT_TRUE (not_zero == range_uchar (1, 255));
// Check that [0,127][0x..ffffff80,0x..ffffff]
// => ~[128, 0x..ffffff7f].
r0 = range_uint128 (0, 127);
wide_int high = wi::minus_one (128);
// low = -1 - 127 => 0x..ffffff80.
wide_int low = wi::sub (high, wi::uhwi (127, 128));
r1 = int_range<1> (u128_type, low, high); // [0x..ffffff80, 0x..ffffffff]
// r0 = [0,127][0x..ffffff80,0x..fffffff].
r0.union_ (r1);
// r1 = [128, 0x..ffffff7f].
r1 = int_range<1> (u128_type,
wi::uhwi (128, 128),
wi::sub (wi::minus_one (128), wi::uhwi (128, 128)));
r0.invert ();
ASSERT_TRUE (r0 == r1);
r0.set_varying (integer_type_node);
wide_int minint = r0.lower_bound ();
wide_int maxint = r0.upper_bound ();
r0.set_varying (short_integer_type_node);
r0.set_varying (unsigned_type_node);
wide_int maxuint = r0.upper_bound ();
// Check that ~[0,5] => [6,MAX] for unsigned int.
r0 = range_uint (0, 5);
r0.invert ();
ASSERT_TRUE (r0 == int_range<1> (unsigned_type_node,
wi::uhwi (6, TYPE_PRECISION (unsigned_type_node)),
maxuint));
// Check that ~[10,MAX] => [0,9] for unsigned int.
r0 = int_range<1> (unsigned_type_node,
wi::uhwi (10, TYPE_PRECISION (unsigned_type_node)),
maxuint);
r0.invert ();
ASSERT_TRUE (r0 == range_uint (0, 9));
// Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
r0 = range_uint128 (0, 5, VR_ANTI_RANGE);
r1 = int_range<1> (u128_type, wi::uhwi (6, 128), wi::minus_one (128));
ASSERT_TRUE (r0 == r1);
// Check that [~5] is really [-MIN,4][6,MAX].
r0 = range_int (5, 5, VR_ANTI_RANGE);
r1 = int_range<1> (integer_type_node, minint, INT (4));
r1.union_ (int_range<1> (integer_type_node, INT (6), maxint));
ASSERT_FALSE (r1.undefined_p ());
ASSERT_TRUE (r0 == r1);
r1 = range_int (5, 5);
int_range<2> r2 (r1);
ASSERT_TRUE (r1 == r2);
r1 = range_int (5, 10);
r1 = range_int (5, 10);
ASSERT_TRUE (r1.contains_p (INT (7)));
r1 = range_char (0, 20);
ASSERT_TRUE (r1.contains_p (SCHAR(15)));
ASSERT_FALSE (r1.contains_p (SCHAR(300)));
// NOT([10,20]) ==> [-MIN,9][21,MAX].
r0 = r1 = range_int (10, 20);
r2 = int_range<1> (integer_type_node, minint, INT(9));
r2.union_ (int_range<1> (integer_type_node, 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 == range_false ());
r0.invert ();
ASSERT_TRUE (r0 == range_true ());
// 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 = range_int (10, 20);
r1 = range_int (15, 30);
r0.union_ (r1);
ASSERT_TRUE (r0 == range_int (10, 30));
// [15,40] U [] => [15,40].
r0 = range_int (15, 40);
r1.set_undefined ();
r0.union_ (r1);
ASSERT_TRUE (r0 == range_int (15, 40));
// [10,20] U [10,10] => [10,20].
r0 = range_int (10, 20);
r1 = range_int (10, 10);
r0.union_ (r1);
ASSERT_TRUE (r0 == range_int (10, 20));
// [10,20] U [9,9] => [9,20].
r0 = range_int (10, 20);
r1 = range_int (9, 9);
r0.union_ (r1);
ASSERT_TRUE (r0 == range_int (9, 20));
// [10,20] ^ [15,30] => [15,20].
r0 = range_int (10, 20);
r1 = range_int (15, 30);
r0.intersect (r1);
ASSERT_TRUE (r0 == range_int (15, 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 = range_int (0, 0);
ASSERT_TRUE (r0.zero_p ());
// Test nonzero_p().
r0 = range_int (0, 0);
r0.invert ();
ASSERT_TRUE (r0.nonzero_p ());
// r0 = ~[1,1]
r0 = range_int (1, 1, VR_ANTI_RANGE);
// r1 = ~[3,3]
r1 = range_int (3, 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);
r0 = range_int (1, 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 (INT (2)));
}
static void
range_tests_nonzero_bits ()
{
int_range<2> r0, r1;
// Adding nonzero bits to a varying drops the varying.
r0.set_varying (integer_type_node);
r0.set_nonzero_bits (INT (255));
ASSERT_TRUE (!r0.varying_p ());
// Dropping the nonzero bits brings us back to varying.
r0.set_nonzero_bits (INT (-1));
ASSERT_TRUE (r0.varying_p ());
// Test contains_p with nonzero bits.
r0.set_zero (integer_type_node);
ASSERT_TRUE (r0.contains_p (INT (0)));
ASSERT_FALSE (r0.contains_p (INT (1)));
r0.set_nonzero_bits (INT (0xfe));
ASSERT_FALSE (r0.contains_p (INT (0x100)));
ASSERT_FALSE (r0.contains_p (INT (0x3)));
// Union of nonzero bits.
r0.set_varying (integer_type_node);
r0.set_nonzero_bits (INT (0xf0));
r1.set_varying (integer_type_node);
r1.set_nonzero_bits (INT (0xf));
r0.union_ (r1);
ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
// Intersect of nonzero bits.
r0 = range_int (0, 255);
r0.set_nonzero_bits (INT (0xfe));
r1.set_varying (integer_type_node);
r1.set_nonzero_bits (INT (0xf0));
r0.intersect (r1);
ASSERT_TRUE (r0.get_nonzero_bits () == 0xf0);
// Intersect where the mask of nonzero bits is implicit from the range.
r0.set_varying (integer_type_node);
r1 = range_int (0, 255);
r0.intersect (r1);
ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
// The union of a mask of 0xff..ffff00 with a mask of 0xff spans the
// entire domain, and makes the range a varying.
r0.set_varying (integer_type_node);
wide_int x = wi::shwi (0xff, TYPE_PRECISION (integer_type_node));
x = wi::bit_not (x);
r0.set_nonzero_bits (x); // 0xff..ff00
r1.set_varying (integer_type_node);
r1.set_nonzero_bits (INT (0xff));
r0.union_ (r1);
ASSERT_TRUE (r0.varying_p ());
// Test that setting a nonzero bit of 1 does not pessimize the range.
r0.set_zero (integer_type_node);
r0.set_nonzero_bits (INT (1));
ASSERT_TRUE (r0.zero_p ());
}
// Build an frange from string endpoints.
static inline frange
frange_float (const char *lb, const char *ub, tree type = float_type_node)
{
REAL_VALUE_TYPE min, max;
gcc_assert (real_from_string (&min, lb) == 0);
gcc_assert (real_from_string (&max, ub) == 0);
return frange (type, min, max);
}
static void
range_tests_nan ()
{
frange r0, r1;
REAL_VALUE_TYPE q, r;
bool signbit;
// Equal ranges but with differing NAN bits are not equal.
if (HONOR_NANS (float_type_node))
{
r1 = frange_float ("10", "12");
r0 = r1;
ASSERT_EQ (r0, r1);
r0.clear_nan ();
ASSERT_NE (r0, r1);
r0.update_nan ();
ASSERT_EQ (r0, r1);
// [10, 20] NAN ^ [30, 40] NAN = NAN.
r0 = frange_float ("10", "20");
r1 = frange_float ("30", "40");
r0.intersect (r1);
ASSERT_TRUE (r0.known_isnan ());
// [3,5] U [5,10] NAN = ... NAN
r0 = frange_float ("3", "5");
r0.clear_nan ();
r1 = frange_float ("5", "10");
r0.union_ (r1);
ASSERT_TRUE (r0.maybe_isnan ());
}
// [5,6] U NAN = [5,6] NAN.
r0 = frange_float ("5", "6");
r0.clear_nan ();
r1.set_nan (float_type_node);
r0.union_ (r1);
real_from_string (&q, "5");
real_from_string (&r, "6");
ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
ASSERT_TRUE (r0.maybe_isnan ());
// NAN U NAN = NAN
r0.set_nan (float_type_node);
r1.set_nan (float_type_node);
r0.union_ (r1);
ASSERT_TRUE (r0.known_isnan ());
// [INF, INF] NAN ^ NAN = NAN
r0.set_nan (float_type_node);
r1 = frange_float ("+Inf", "+Inf");
if (!HONOR_NANS (float_type_node))
r1.update_nan ();
r0.intersect (r1);
ASSERT_TRUE (r0.known_isnan ());
// NAN ^ NAN = NAN
r0.set_nan (float_type_node);
r1.set_nan (float_type_node);
r0.intersect (r1);
ASSERT_TRUE (r0.known_isnan ());
// +NAN ^ -NAN = UNDEFINED
r0.set_nan (float_type_node, false);
r1.set_nan (float_type_node, true);
r0.intersect (r1);
ASSERT_TRUE (r0.undefined_p ());
// VARYING ^ NAN = NAN.
r0.set_nan (float_type_node);
r1.set_varying (float_type_node);
r0.intersect (r1);
ASSERT_TRUE (r0.known_isnan ());
// [3,4] ^ NAN = UNDEFINED.
r0 = frange_float ("3", "4");
r0.clear_nan ();
r1.set_nan (float_type_node);
r0.intersect (r1);
ASSERT_TRUE (r0.undefined_p ());
// [-3, 5] ^ NAN = UNDEFINED
r0 = frange_float ("-3", "5");
r0.clear_nan ();
r1.set_nan (float_type_node);
r0.intersect (r1);
ASSERT_TRUE (r0.undefined_p ());
// Setting the NAN bit to yes does not make us a known NAN.
r0.set_varying (float_type_node);
r0.update_nan ();
ASSERT_FALSE (r0.known_isnan ());
// NAN is in a VARYING.
r0.set_varying (float_type_node);
real_nan (&r, "", 1, TYPE_MODE (float_type_node));
REAL_VALUE_TYPE nan = r;
ASSERT_TRUE (r0.contains_p (nan));
// -NAN is in a VARYING.
r0.set_varying (float_type_node);
q = real_value_negate (&r);
REAL_VALUE_TYPE neg_nan = q;
ASSERT_TRUE (r0.contains_p (neg_nan));
// Clearing the NAN on a [] NAN is the empty set.
r0.set_nan (float_type_node);
r0.clear_nan ();
ASSERT_TRUE (r0.undefined_p ());
// [10,20] NAN ^ [21,25] NAN = [NAN]
r0 = frange_float ("10", "20");
r0.update_nan ();
r1 = frange_float ("21", "25");
r1.update_nan ();
r0.intersect (r1);
ASSERT_TRUE (r0.known_isnan ());
// NAN U [5,6] should be [5,6] +-NAN.
r0.set_nan (float_type_node);
r1 = frange_float ("5", "6");
r1.clear_nan ();
r0.union_ (r1);
real_from_string (&q, "5");
real_from_string (&r, "6");
ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
ASSERT_TRUE (!r0.signbit_p (signbit));
ASSERT_TRUE (r0.maybe_isnan ());
// NAN U NAN shouldn't change anything.
r0.set_nan (float_type_node);
r1.set_nan (float_type_node);
ASSERT_FALSE (r0.union_ (r1));
// [3,5] NAN U NAN shouldn't change anything.
r0 = frange_float ("3", "5");
r1.set_nan (float_type_node);
ASSERT_FALSE (r0.union_ (r1));
// [3,5] U NAN *does* trigger a change.
r0 = frange_float ("3", "5");
r0.clear_nan ();
r1.set_nan (float_type_node);
ASSERT_TRUE (r0.union_ (r1));
}
static void
range_tests_signed_zeros ()
{
REAL_VALUE_TYPE zero = dconst0;
REAL_VALUE_TYPE neg_zero = zero;
neg_zero.sign = 1;
frange r0, r1;
bool signbit;
// [0,0] contains [0,0] but not [-0,-0] and vice versa.
r0 = frange_float ("0.0", "0.0");
r1 = frange_float ("-0.0", "-0.0");
ASSERT_TRUE (r0.contains_p (zero));
ASSERT_TRUE (!r0.contains_p (neg_zero));
ASSERT_TRUE (r1.contains_p (neg_zero));
ASSERT_TRUE (!r1.contains_p (zero));
// Test contains_p() when we know the sign of the zero.
r0 = frange_float ("0.0", "0.0");
ASSERT_TRUE (r0.contains_p (zero));
ASSERT_FALSE (r0.contains_p (neg_zero));
r0 = frange_float ("-0.0", "-0.0");
ASSERT_TRUE (r0.contains_p (neg_zero));
ASSERT_FALSE (r0.contains_p (zero));
r0 = frange_float ("-0.0", "0.0");
ASSERT_TRUE (r0.contains_p (neg_zero));
ASSERT_TRUE (r0.contains_p (zero));
r0 = frange_float ("-3", "5");
ASSERT_TRUE (r0.contains_p (neg_zero));
ASSERT_TRUE (r0.contains_p (zero));
// The intersection of zeros that differ in sign is a NAN (or
// undefined if not honoring NANs).
r0 = frange_float ("-0.0", "-0.0");
r1 = frange_float ("0.0", "0.0");
r0.intersect (r1);
if (HONOR_NANS (float_type_node))
ASSERT_TRUE (r0.known_isnan ());
else
ASSERT_TRUE (r0.undefined_p ());
// The union of zeros that differ in sign is a zero with unknown sign.
r0 = frange_float ("0.0", "0.0");
r1 = frange_float ("-0.0", "-0.0");
r0.union_ (r1);
ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
// [-0, +0] has an unknown sign.
r0 = frange_float ("-0.0", "0.0");
ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
// [-0, +0] ^ [0, 0] is [0, 0]
r0 = frange_float ("-0.0", "0.0");
r1 = frange_float ("0.0", "0.0");
r0.intersect (r1);
ASSERT_TRUE (r0.zero_p ());
r0 = frange_float ("+0", "5");
r0.clear_nan ();
ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
r0 = frange_float ("-0", "5");
r0.clear_nan ();
ASSERT_TRUE (!r0.signbit_p (signbit));
r0 = frange_float ("-0", "10");
r1 = frange_float ("0", "5");
r0.intersect (r1);
ASSERT_TRUE (real_iszero (&r0.lower_bound (), false));
r0 = frange_float ("-0", "5");
r1 = frange_float ("0", "5");
r0.union_ (r1);
ASSERT_TRUE (real_iszero (&r0.lower_bound (), true));
r0 = frange_float ("-5", "-0");
r0.update_nan ();
r1 = frange_float ("0", "0");
r1.update_nan ();
r0.intersect (r1);
if (HONOR_NANS (float_type_node))
ASSERT_TRUE (r0.known_isnan ());
else
ASSERT_TRUE (r0.undefined_p ());
r0.set_nonnegative (float_type_node);
if (HONOR_NANS (float_type_node))
ASSERT_TRUE (r0.maybe_isnan ());
// Numbers containing zero should have an unknown SIGNBIT.
r0 = frange_float ("0", "10");
r0.clear_nan ();
ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
}
static void
range_tests_signbit ()
{
frange r0, r1;
bool signbit;
// Negative numbers should have the SIGNBIT set.
r0 = frange_float ("-5", "-1");
r0.clear_nan ();
ASSERT_TRUE (r0.signbit_p (signbit) && signbit);
// Positive numbers should have the SIGNBIT clear.
r0 = frange_float ("1", "10");
r0.clear_nan ();
ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
// Numbers spanning both positive and negative should have an
// unknown SIGNBIT.
r0 = frange_float ("-10", "10");
r0.clear_nan ();
ASSERT_TRUE (!r0.signbit_p (signbit));
r0.set_varying (float_type_node);
ASSERT_TRUE (!r0.signbit_p (signbit));
}
static void
range_tests_floats ()
{
frange r0, r1;
if (HONOR_NANS (float_type_node))
range_tests_nan ();
range_tests_signbit ();
if (HONOR_SIGNED_ZEROS (float_type_node))
range_tests_signed_zeros ();
// A range of [-INF,+INF] is actually VARYING if no other properties
// are set.
r0 = frange_float ("-Inf", "+Inf");
ASSERT_TRUE (r0.varying_p ());
// ...unless it has some special property...
if (HONOR_NANS (r0.type ()))
{
r0.clear_nan ();
ASSERT_FALSE (r0.varying_p ());
}
// For most architectures, where float and double are different
// sizes, having the same endpoints does not necessarily mean the
// ranges are equal.
if (!types_compatible_p (float_type_node, double_type_node))
{
r0 = frange_float ("3.0", "3.0", float_type_node);
r1 = frange_float ("3.0", "3.0", double_type_node);
ASSERT_NE (r0, r1);
}
// [3,5] U [10,12] = [3,12].
r0 = frange_float ("3", "5");
r1 = frange_float ("10", "12");
r0.union_ (r1);
ASSERT_EQ (r0, frange_float ("3", "12"));
// [5,10] U [4,8] = [4,10]
r0 = frange_float ("5", "10");
r1 = frange_float ("4", "8");
r0.union_ (r1);
ASSERT_EQ (r0, frange_float ("4", "10"));
// [3,5] U [4,10] = [3,10]
r0 = frange_float ("3", "5");
r1 = frange_float ("4", "10");
r0.union_ (r1);
ASSERT_EQ (r0, frange_float ("3", "10"));
// [4,10] U [5,11] = [4,11]
r0 = frange_float ("4", "10");
r1 = frange_float ("5", "11");
r0.union_ (r1);
ASSERT_EQ (r0, frange_float ("4", "11"));
// [3,12] ^ [10,12] = [10,12].
r0 = frange_float ("3", "12");
r1 = frange_float ("10", "12");
r0.intersect (r1);
ASSERT_EQ (r0, frange_float ("10", "12"));
// [10,12] ^ [11,11] = [11,11]
r0 = frange_float ("10", "12");
r1 = frange_float ("11", "11");
r0.intersect (r1);
ASSERT_EQ (r0, frange_float ("11", "11"));
// [10,20] ^ [5,15] = [10,15]
r0 = frange_float ("10", "20");
r1 = frange_float ("5", "15");
r0.intersect (r1);
ASSERT_EQ (r0, frange_float ("10", "15"));
// [10,20] ^ [15,25] = [15,20]
r0 = frange_float ("10", "20");
r1 = frange_float ("15", "25");
r0.intersect (r1);
ASSERT_EQ (r0, frange_float ("15", "20"));
// [10,20] ^ [21,25] = []
r0 = frange_float ("10", "20");
r0.clear_nan ();
r1 = frange_float ("21", "25");
r1.clear_nan ();
r0.intersect (r1);
ASSERT_TRUE (r0.undefined_p ());
if (HONOR_INFINITIES (float_type_node))
{
// Make sure [-Inf, -Inf] doesn't get normalized.
r0 = frange_float ("-Inf", "-Inf");
ASSERT_TRUE (real_isinf (&r0.lower_bound (), true));
ASSERT_TRUE (real_isinf (&r0.upper_bound (), true));
}
// Test that reading back a global range yields the same result as
// what we wrote into it.
tree ssa = make_temp_ssa_name (float_type_node, NULL, "blah");
r0.set_varying (float_type_node);
r0.clear_nan ();
set_range_info (ssa, r0);
get_global_range_query ()->range_of_expr (r1, ssa);
ASSERT_EQ (r0, r1);
}
// Run floating range tests for various combinations of NAN and INF
// support.
static void
range_tests_floats_various ()
{
int save_finite_math_only = flag_finite_math_only;
// Test -ffinite-math-only.
flag_finite_math_only = 1;
range_tests_floats ();
// Test -fno-finite-math-only.
flag_finite_math_only = 0;
range_tests_floats ();
flag_finite_math_only = save_finite_math_only;
}
void
range_tests ()
{
range_tests_irange3 ();
range_tests_int_range_max ();
range_tests_strict_enum ();
range_tests_nonzero_bits ();
range_tests_floats_various ();
range_tests_misc ();
}
} // namespace selftest
#endif // CHECKING_P