This patch adds the ability to resize ranges as needed, defaulting to no
resizing. int_range_max now defaults to 3 sub-ranges (instead of 255)
and grows to 255 when the range being calculated does not fit.
Bootstraps on x86_64-pc-linux-gnu with no regressions. Pushed.
Andrew
From 70639014a69cf50fe11dc1adbfe1db4c7760ce69 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacl...@redhat.com>
Date: Tue, 26 Sep 2023 09:44:39 -0400
Subject: [PATCH] Reduce the initial size of int_range_max.
This patch adds the ability to resize ranges as needed, defaulting to no
resizing. int_range_max now defaults to 3 sub-ranges (instead of 255)
and grows to 255 when the range being calculated does not fit.
PR tree-optimization/110315
* value-range-storage.h (vrange_allocator::alloc_irange): Adjust
new params.
* value-range.cc (irange::operator=): Resize range.
(irange::irange_union): Same.
(irange::irange_intersect): Same.
(irange::invert): Same.
* value-range.h (irange::maybe_resize): New.
(~int_range): New.
(int_range_max): Default to 3 sub-ranges and resize as needed.
(int_range::int_range): Adjust for resizing.
(int_range::operator=): Same.
---
gcc/value-range-storage.h | 2 +-
gcc/value-range.cc | 15 ++++++
gcc/value-range.h | 96 +++++++++++++++++++++++++++------------
3 files changed, 83 insertions(+), 30 deletions(-)
diff --git a/gcc/value-range-storage.h b/gcc/value-range-storage.h
index 6da377ebd2e..1ed6f1ccd61 100644
--- a/gcc/value-range-storage.h
+++ b/gcc/value-range-storage.h
@@ -184,7 +184,7 @@ vrange_allocator::alloc_irange (unsigned num_pairs)
// Allocate the irange and required memory for the vector.
void *r = alloc (sizeof (irange));
tree *mem = static_cast <tree *> (alloc (nbytes));
- return new (r) irange (mem, num_pairs);
+ return new (r) irange (mem, num_pairs, /*resizable=*/false);
}
inline frange *
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index ec826c2fe1b..753f5e8cc76 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -831,6 +831,10 @@ irange::operator= (const irange &src)
copy_to_legacy (src);
return *this;
}
+
+ int needed = src.num_pairs ();
+ maybe_resize (needed);
+
if (src.legacy_mode_p ())
{
copy_legacy_to_multi_range (src);
@@ -2506,6 +2510,7 @@ irange::irange_union (const irange &r)
// 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];
@@ -2605,6 +2610,11 @@ irange::irange_intersect (const irange &r)
if (r.irange_contains_p (*this))
return intersect_nonzero_bits (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 (TREE_TYPE(m_base[0]));
unsigned bld_pair = 0;
unsigned bld_lim = m_max_ranges;
@@ -2831,6 +2841,11 @@ irange::invert ()
m_num_ranges = 1;
return;
}
+
+ // 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].
//
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 969b2b68418..96e59ecfa72 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -172,7 +172,8 @@ public:
bool legacy_verbose_intersect (const irange *); // DEPRECATED
protected:
- irange (tree *, unsigned);
+ void maybe_resize (int needed);
+ irange (tree *, unsigned nranges, bool resizable);
// potential promotion to public?
tree tree_lower_bound (unsigned = 0) const;
tree tree_upper_bound (unsigned) const;
@@ -200,6 +201,8 @@ protected:
void copy_to_legacy (const irange &);
void copy_legacy_to_multi_range (const irange &);
+ // Hard limit on max ranges allowed.
+ static const int HARD_MAX_RANGES = 255;
private:
friend void gt_ggc_mx (irange *);
friend void gt_pch_nx (irange *);
@@ -214,15 +217,21 @@ private:
bool intersect (const wide_int& lb, const wide_int& ub);
unsigned char m_num_ranges;
+ bool m_resizable;
unsigned char m_max_ranges;
tree m_nonzero_mask;
+protected:
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.
+//
+// If RESIZABLE is true, the storage will be resized on the heap when
+// the number of ranges needed goes past N up to a max of
+// HARD_MAX_RANGES. This new storage is freed upon destruction.
-template<unsigned N>
+template<unsigned N, bool RESIZABLE = false>
class GTY((user)) int_range : public irange
{
public:
@@ -233,7 +242,7 @@ public:
int_range (tree type);
int_range (const int_range &);
int_range (const irange &);
- virtual ~int_range () = default;
+ virtual ~int_range ();
int_range& operator= (const int_range &);
private:
template <unsigned X> friend void gt_ggc_mx (int_range<X> *);
@@ -472,6 +481,38 @@ is_a <frange> (vrange &v)
return v.m_discriminator == VR_FRANGE;
}
+// For resizable ranges, resize the range up to HARD_MAX_RANGES if the
+// NEEDED pairs is greater than the current capacity of the range.
+
+inline void
+irange::maybe_resize (int needed)
+{
+ if (!m_resizable || m_max_ranges == HARD_MAX_RANGES)
+ return;
+
+ if (needed > m_max_ranges)
+ {
+ m_max_ranges = HARD_MAX_RANGES;
+ tree *newmem = new tree[m_max_ranges * 2];
+ memcpy (newmem, m_base, sizeof (tree) * num_pairs () * 2);
+ m_base = newmem;
+ }
+}
+
+template<unsigned N, bool RESIZABLE>
+inline
+int_range<N, RESIZABLE>::~int_range ()
+{
+ if (RESIZABLE && m_base != m_ranges)
+ delete m_base;
+}
+
+// This is an "infinite" precision irange for use in temporary
+// calculations. It starts with a sensible default covering 99% of
+// uses, and goes up to HARD_MAX_RANGES when needed. Any allocated
+// storage is freed upon destruction.
+typedef int_range<3, /*RESIZABLE=*/true> int_range_max;
+
class vrange_visitor
{
public:
@@ -490,10 +531,6 @@ public:
// 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;
-
// This is an "infinite" precision range object for use in temporary
// calculations for any of the handled types. The object can be
// transparently used as a vrange.
@@ -872,64 +909,65 @@ gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
// Constructors for irange
inline
-irange::irange (tree *base, unsigned nranges)
+irange::irange (tree *base, unsigned nranges, bool resizable)
{
m_discriminator = VR_IRANGE;
m_base = base;
m_max_ranges = nranges;
+ m_resizable = resizable;
set_undefined ();
}
// Constructors for int_range<>.
-template<unsigned N>
+template<unsigned N, bool RESIZABLE>
inline
-int_range<N>::int_range ()
- : irange (m_ranges, N)
+int_range<N, RESIZABLE>::int_range ()
+ : irange (m_ranges, N, RESIZABLE)
{
}
-template<unsigned N>
-int_range<N>::int_range (const int_range &other)
- : irange (m_ranges, N)
+template<unsigned N, bool RESIZABLE>
+int_range<N, RESIZABLE>::int_range (const int_range &other)
+ : irange (m_ranges, N, RESIZABLE)
{
irange::operator= (other);
}
-template<unsigned N>
-int_range<N>::int_range (tree min, tree max, value_range_kind kind)
- : irange (m_ranges, N)
+template<unsigned N, bool RESIZABLE>
+int_range<N, RESIZABLE>::int_range (tree min, tree max, value_range_kind kind)
+ : irange (m_ranges, N, RESIZABLE)
{
irange::set (min, max, kind);
}
-template<unsigned N>
-int_range<N>::int_range (tree type)
- : irange (m_ranges, N)
+template<unsigned N, bool RESIZABLE>
+int_range<N, RESIZABLE>::int_range (tree type)
+ : irange (m_ranges, N, RESIZABLE)
{
set_varying (type);
}
-template<unsigned N>
-int_range<N>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
+template<unsigned N, bool RESIZABLE>
+int_range<N, RESIZABLE>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
value_range_kind kind)
- : irange (m_ranges, N)
+ : irange (m_ranges, N, RESIZABLE)
{
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)
+template<unsigned N, bool RESIZABLE>
+int_range<N, RESIZABLE>::int_range (const irange &other)
+ : irange (m_ranges, N, RESIZABLE)
{
irange::operator= (other);
}
-template<unsigned N>
-int_range<N>&
-int_range<N>::operator= (const int_range &src)
+template<unsigned N, bool RESIZABLE>
+int_range<N, RESIZABLE>&
+int_range<N, RESIZABLE>::operator= (const int_range &src)
{
irange::operator= (src);
return *this;
--
2.41.0
