blob: 54623b97a1fba797cdcc3d04261abfcad2dd0b65 [file] [log] [blame]
/* Support routines for value ranges.
Copyright (C) 2019-2021 Free Software Foundation, Inc.
Contributed 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/>. */
#ifndef GCC_VALUE_RANGE_H
#define GCC_VALUE_RANGE_H
// Types of value ranges.
enum value_range_kind
{
/* Empty range. */
VR_UNDEFINED,
/* Range spans the entire domain. */
VR_VARYING,
/* Range is [MIN, MAX]. */
VR_RANGE,
/* Range is ~[MIN, MAX]. */
VR_ANTI_RANGE,
/* Range is a nice guy. */
VR_LAST
};
// Range of values that can be associated with an SSA_NAME.
//
// This is the base class without any storage.
class irange
{
friend class irange_allocator;
public:
// In-place setters.
void set (tree, tree, value_range_kind = VR_RANGE);
void set_nonzero (tree);
void set_zero (tree);
void set_varying (tree type);
void set_undefined ();
// Range types.
static bool supports_type_p (tree);
tree type () const;
// Iteration over sub-ranges.
unsigned num_pairs () const;
wide_int lower_bound (unsigned = 0) const;
wide_int upper_bound (unsigned) const;
wide_int upper_bound () const;
// Predicates.
bool zero_p () const;
bool nonzero_p () const;
bool undefined_p () const;
bool varying_p () const;
bool singleton_p (tree *result = NULL) const;
bool contains_p (tree) const;
// In-place operators.
void union_ (const irange &);
void intersect (const irange &);
void invert ();
// Operator overloads.
irange& operator= (const irange &);
bool operator== (const irange &) const;
bool operator!= (const irange &r) const { return !(*this == r); }
// Misc methods.
bool fits_p (const irange &r) { return m_max_ranges >= r.num_pairs (); }
void dump (FILE * = stderr) const;
// Deprecated legacy public methods.
enum value_range_kind kind () const; // DEPRECATED
tree min () const; // DEPRECATED
tree max () const; // DEPRECATED
bool symbolic_p () const; // DEPRECATED
bool constant_p () const; // DEPRECATED
void normalize_symbolics (); // DEPRECATED
void normalize_addresses (); // DEPRECATED
bool may_contain_p (tree) const; // DEPRECATED
void set (tree); // DEPRECATED
bool equal_p (const irange &) const; // DEPRECATED
void union_ (const class irange *); // DEPRECATED
void intersect (const irange *); // DEPRECATED
protected:
irange (tree *, unsigned);
// potential promotion to public?
tree tree_lower_bound (unsigned = 0) const;
tree tree_upper_bound (unsigned) const;
tree tree_upper_bound () const;
// In-place operators.
void irange_union (const irange &);
void irange_intersect (const irange &);
void irange_set (tree, tree);
void irange_set_anti_range (tree, tree);
void normalize_min_max ();
bool legacy_mode_p () const;
bool legacy_equal_p (const irange &) const;
void legacy_union (irange *, const irange *);
void legacy_intersect (irange *, const irange *);
void verify_range ();
unsigned legacy_num_pairs () const;
wide_int legacy_lower_bound (unsigned = 0) const;
wide_int legacy_upper_bound (unsigned) const;
int value_inside_range (tree) const;
bool maybe_anti_range () const;
void copy_to_legacy (const irange &);
void copy_legacy_to_multi_range (const irange &);
private:
void irange_set_1bit_anti_range (tree, tree);
unsigned char m_num_ranges;
unsigned char m_max_ranges;
ENUM_BITFIELD(value_range_kind) m_kind : 8;
tree *m_base;
};
// Here we describe an irange with N pairs of ranges. The storage for
// the pairs is embedded in the class as an array.
template<unsigned N>
class GTY((user)) int_range : public irange
{
public:
int_range ();
int_range (tree, tree, value_range_kind = VR_RANGE);
int_range (tree type, const wide_int &, const wide_int &,
value_range_kind = VR_RANGE);
int_range (tree type);
int_range (const int_range &);
int_range (const irange &);
int_range& operator= (const int_range &);
private:
template <unsigned X> friend void gt_ggc_mx (int_range<X> *);
template <unsigned X> friend void gt_pch_nx (int_range<X> *);
template <unsigned X> friend void gt_pch_nx (int_range<X> *,
gt_pointer_operator, void *);
// ?? hash-traits.h has its own extern for these, which is causing
// them to never be picked up by the templates. For now, define
// elsewhere.
//template<unsigned X> friend void gt_ggc_mx (int_range<X> *&);
//template<unsigned X> friend void gt_pch_nx (int_range<X> *&);
friend void gt_ggc_mx (int_range<1> *&);
friend void gt_pch_nx (int_range<1> *&);
tree m_ranges[N*2];
};
// This is a special int_range<1> with only one pair, plus
// VR_ANTI_RANGE magic to describe slightly more than can be described
// in one pair. It is described in the code as a "legacy range" (as
// opposed to multi-ranges which have multiple sub-ranges). It is
// provided for backward compatibility with code that has not been
// converted to multi-range irange's.
//
// There are copy operators to seamlessly copy to/fro multi-ranges.
typedef int_range<1> value_range;
// This is an "infinite" precision irange for use in temporary
// calculations.
typedef int_range<255> int_range_max;
// Returns true for an old-school value_range as described above.
inline bool
irange::legacy_mode_p () const
{
return m_max_ranges == 1;
}
extern bool range_has_numeric_bounds_p (const irange *);
extern bool ranges_from_anti_range (const value_range *,
value_range *, value_range *);
extern void dump_value_range (FILE *, const irange *);
extern bool vrp_val_is_min (const_tree);
extern bool vrp_val_is_max (const_tree);
extern bool vrp_operand_equal_p (const_tree, const_tree);
inline value_range_kind
irange::kind () const
{
if (legacy_mode_p ())
return m_kind;
if (undefined_p ())
return VR_UNDEFINED;
if (varying_p ())
return VR_VARYING;
return VR_RANGE;
}
// Number of sub-ranges in a range.
inline unsigned
irange::num_pairs () const
{
if (!legacy_mode_p ())
return m_num_ranges;
else
return legacy_num_pairs ();
}
inline tree
irange::type () const
{
gcc_checking_assert (!undefined_p ());
return TREE_TYPE (m_base[0]);
}
// Return the lower bound of a sub-range expressed as a tree. PAIR is
// the sub-range in question.
inline tree
irange::tree_lower_bound (unsigned pair) const
{
return m_base[pair * 2];
}
// Return the upper bound of a sub-range expressed as a tree. PAIR is
// the sub-range in question.
inline tree
irange::tree_upper_bound (unsigned pair) const
{
return m_base[pair * 2 + 1];
}
// Return the highest bound of a range expressed as a tree.
inline tree
irange::tree_upper_bound () const
{
gcc_checking_assert (m_num_ranges);
return tree_upper_bound (m_num_ranges - 1);
}
inline tree
irange::min () const
{
return tree_lower_bound (0);
}
inline tree
irange::max () const
{
if (m_num_ranges)
return tree_upper_bound ();
else
return NULL;
}
inline bool
irange::varying_p () const
{
if (legacy_mode_p ())
return m_kind == VR_VARYING;
if (m_num_ranges != 1)
return false;
tree l = m_base[0];
tree u = m_base[1];
tree t = TREE_TYPE (l);
unsigned prec = TYPE_PRECISION (t);
signop sign = TYPE_SIGN (t);
if (INTEGRAL_TYPE_P (t))
return (wi::to_wide (l) == wi::min_value (prec, sign)
&& wi::to_wide (u) == wi::max_value (prec, sign));
if (POINTER_TYPE_P (t))
return (wi::to_wide (l) == 0
&& wi::to_wide (u) == wi::max_value (prec, sign));
return true;
}
inline bool
irange::undefined_p () const
{
if (!legacy_mode_p ())
return m_num_ranges == 0;
if (CHECKING_P && legacy_mode_p ())
{
if (m_kind == VR_UNDEFINED)
gcc_checking_assert (m_num_ranges == 0);
else
gcc_checking_assert (m_num_ranges != 0);
}
return m_kind == VR_UNDEFINED;
}
inline bool
irange::zero_p () const
{
return (m_kind == VR_RANGE && m_num_ranges == 1
&& integer_zerop (tree_lower_bound (0))
&& integer_zerop (tree_upper_bound (0)));
}
inline bool
irange::nonzero_p () const
{
if (undefined_p ())
return false;
tree zero = build_zero_cst (type ());
return *this == int_range<1> (zero, zero, VR_ANTI_RANGE);
}
inline bool
irange::supports_type_p (tree type)
{
if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)))
return type;
return false;
}
inline bool
range_includes_zero_p (const irange *vr)
{
if (vr->undefined_p ())
return false;
if (vr->varying_p ())
return true;
return vr->may_contain_p (build_zero_cst (vr->type ()));
}
template<unsigned N>
inline void
gt_ggc_mx (int_range<N> *x)
{
for (unsigned i = 0; i < N; ++i)
{
gt_ggc_mx (x->m_ranges[i * 2]);
gt_ggc_mx (x->m_ranges[i * 2 + 1]);
}
}
template<unsigned N>
inline void
gt_pch_nx (int_range<N> *x)
{
for (unsigned i = 0; i < N; ++i)
{
gt_pch_nx (x->m_ranges[i * 2]);
gt_pch_nx (x->m_ranges[i * 2 + 1]);
}
}
template<unsigned N>
inline void
gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
{
for (unsigned i = 0; i < N; ++i)
{
op (&x->m_ranges[i * 2], cookie);
op (&x->m_ranges[i * 2 + 1], cookie);
}
}
// Constructors for irange
inline
irange::irange (tree *base, unsigned nranges)
{
m_base = base;
m_num_ranges = 0;
m_max_ranges = nranges;
if (legacy_mode_p ())
m_kind = VR_UNDEFINED;
else
m_kind = VR_RANGE;
}
// Constructors for int_range<>.
template<unsigned N>
inline
int_range<N>::int_range ()
: irange (m_ranges, N)
{
}
template<unsigned N>
int_range<N>::int_range (const int_range &other)
: irange (m_ranges, N)
{
irange::operator= (other);
}
template<unsigned N>
int_range<N>::int_range (tree min, tree max, value_range_kind kind)
: irange (m_ranges, N)
{
irange::set (min, max, kind);
}
template<unsigned N>
int_range<N>::int_range (tree type)
: irange (m_ranges, N)
{
set_varying (type);
}
template<unsigned N>
int_range<N>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
value_range_kind kind)
: irange (m_ranges, N)
{
tree min = wide_int_to_tree (type, wmin);
tree max = wide_int_to_tree (type, wmax);
set (min, max, kind);
}
template<unsigned N>
int_range<N>::int_range (const irange &other)
: irange (m_ranges, N)
{
irange::operator= (other);
}
template<unsigned N>
int_range<N>&
int_range<N>::operator= (const int_range &src)
{
irange::operator= (src);
return *this;
}
inline void
irange::set (tree val)
{
set (val, val);
}
inline void
irange::set_undefined ()
{
m_num_ranges = 0;
if (legacy_mode_p ())
m_kind = VR_UNDEFINED;
}
inline void
irange::set_varying (tree type)
{
if (legacy_mode_p ())
m_kind = VR_VARYING;
m_num_ranges = 1;
if (INTEGRAL_TYPE_P (type))
{
wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
m_base[0] = wide_int_to_tree (type, min);
m_base[1] = wide_int_to_tree (type, max);
}
else if (POINTER_TYPE_P (type))
{
m_base[0] = build_int_cst (type, 0);
m_base[1] = build_int_cst (type, -1);
}
else
m_base[0] = m_base[1] = error_mark_node;
}
inline bool
irange::operator== (const irange &r) const
{
return equal_p (r);
}
// Return the lower bound of a sub-range. PAIR is the sub-range in
// question.
inline wide_int
irange::lower_bound (unsigned pair) const
{
if (legacy_mode_p ())
return legacy_lower_bound (pair);
gcc_checking_assert (!undefined_p ());
gcc_checking_assert (pair + 1 <= num_pairs ());
return wi::to_wide (tree_lower_bound (pair));
}
// Return the upper bound of a sub-range. PAIR is the sub-range in
// question.
inline wide_int
irange::upper_bound (unsigned pair) const
{
if (legacy_mode_p ())
return legacy_upper_bound (pair);
gcc_checking_assert (!undefined_p ());
gcc_checking_assert (pair + 1 <= num_pairs ());
return wi::to_wide (tree_upper_bound (pair));
}
// Return the highest bound of a range.
inline wide_int
irange::upper_bound () const
{
unsigned pairs = num_pairs ();
gcc_checking_assert (pairs > 0);
return upper_bound (pairs - 1);
}
inline void
irange::union_ (const irange &r)
{
dump_flags_t m_flags = dump_flags;
dump_flags &= ~TDF_DETAILS;
irange::union_ (&r);
dump_flags = m_flags;
}
inline void
irange::intersect (const irange &r)
{
dump_flags_t m_flags = dump_flags;
dump_flags &= ~TDF_DETAILS;
irange::intersect (&r);
dump_flags = m_flags;
}
// Set value range VR to a nonzero range of type TYPE.
inline void
irange::set_nonzero (tree type)
{
tree zero = build_int_cst (type, 0);
if (legacy_mode_p ())
set (zero, zero, VR_ANTI_RANGE);
else
irange_set_anti_range (zero, zero);
}
// Set value range VR to a ZERO range of type TYPE.
inline void
irange::set_zero (tree type)
{
tree z = build_int_cst (type, 0);
if (legacy_mode_p ())
set (z);
else
irange_set (z, z);
}
// Normalize a range to VARYING or UNDEFINED if possible.
inline void
irange::normalize_min_max ()
{
gcc_checking_assert (legacy_mode_p ());
gcc_checking_assert (!undefined_p ());
unsigned prec = TYPE_PRECISION (type ());
signop sign = TYPE_SIGN (type ());
if (wi::eq_p (wi::to_wide (min ()), wi::min_value (prec, sign))
&& wi::eq_p (wi::to_wide (max ()), wi::max_value (prec, sign)))
{
if (m_kind == VR_RANGE)
set_varying (type ());
else if (m_kind == VR_ANTI_RANGE)
set_undefined ();
else
gcc_unreachable ();
}
}
// Return the maximum value for TYPE.
inline tree
vrp_val_max (const_tree type)
{
if (INTEGRAL_TYPE_P (type))
return TYPE_MAX_VALUE (type);
if (POINTER_TYPE_P (type))
{
wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
return wide_int_to_tree (const_cast<tree> (type), max);
}
return NULL_TREE;
}
// Return the minimum value for TYPE.
inline tree
vrp_val_min (const_tree type)
{
if (INTEGRAL_TYPE_P (type))
return TYPE_MIN_VALUE (type);
if (POINTER_TYPE_P (type))
return build_zero_cst (const_cast<tree> (type));
return NULL_TREE;
}
// This is the irange storage class. It is used to allocate the
// minimum amount of storage needed for a given irange. Storage is
// automatically freed at destruction of the storage class.
//
// It is meant for long term storage, as opposed to int_range_max
// which is meant for intermediate temporary results on the stack.
//
// The newly allocated irange is initialized to the empty set
// (undefined_p() is true).
class irange_allocator
{
public:
irange_allocator ();
~irange_allocator ();
// Return a new range with NUM_PAIRS.
irange *allocate (unsigned num_pairs);
// Return a copy of SRC with the minimum amount of sub-ranges needed
// to represent it.
irange *allocate (const irange &src);
void *get_memory (unsigned num_bytes);
private:
DISABLE_COPY_AND_ASSIGN (irange_allocator);
struct obstack m_obstack;
};
inline
irange_allocator::irange_allocator ()
{
obstack_init (&m_obstack);
}
inline
irange_allocator::~irange_allocator ()
{
obstack_free (&m_obstack, NULL);
}
// Provide a hunk of memory from the obstack
inline void *
irange_allocator::get_memory (unsigned num_bytes)
{
void *r = obstack_alloc (&m_obstack, num_bytes);
return r;
}
// Return a new range with NUM_PAIRS.
inline irange *
irange_allocator::allocate (unsigned num_pairs)
{
// Never allocate 0 pairs.
// Don't allocate 1 either, or we get legacy value_range's.
if (num_pairs < 2)
num_pairs = 2;
size_t nbytes = sizeof (tree) * 2 * num_pairs;
// Allocate the irange and required memory for the vector.
void *r = obstack_alloc (&m_obstack, sizeof (irange));
tree *mem = (tree *) obstack_alloc (&m_obstack, nbytes);
return new (r) irange (mem, num_pairs);
}
inline irange *
irange_allocator::allocate (const irange &src)
{
irange *r = allocate (src.num_pairs ());
*r = src;
return r;
}
#endif // GCC_VALUE_RANGE_H