Re: [PATCH] Add auto-resizing capability to irange's [PR109695]

[Richard Biener <richard.guenther@gmail.com>]

On Mon, May 15, 2023 at 12:35 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> <tldr>
> We can now have int_range<N, RESIZABLE=false> for automatically
> resizable ranges.  int_range_max is now int_range<3, true>
> for a 69X reduction in size from current trunk, and 6.9X reduction from
> GCC12.  This incurs a 5% performance penalty for VRP that is more than
> covered by our > 13% improvements recently.
> </tldr>
>
> int_range_max is the temporary range object we use in the ranger for
> integers.  With the conversion to wide_int, this structure bloated up
> significantly because wide_ints are huge (80 bytes a piece) and are
> about 10 times as big as a plain tree.  Since the temporary object
> requires 255 sub-ranges, that's 255 * 80 * 2, plus the control word.
> This means the structure grew from 4112 bytes to 40912 bytes.
>
> This patch adds the ability to resize ranges as needed, defaulting to
> no resizing, while int_range_max now defaults to 3 sub-ranges (instead
> of 255) and grows to 255 when the range being calculated does not fit.
>
> For example:
>
> int_range<1> foo;       // 1 sub-range with no resizing.
> int_range<5> foo;       // 5 sub-ranges with no resizing.
> int_range<5, true> foo; // 5 sub-ranges with resizing.
>
> I ran some tests and found that 3 sub-ranges cover 99% of cases, so
> I've set the int_range_max default to that:
>
>         typedef int_range<3, /*RESIZABLE=*/true> int_range_max;
>
> We don't bother growing incrementally, since the default covers most
> cases and we have a 255 hard-limit.  This hard limit could be reduced
> to 128, since my tests never saw a range needing more than 124, but we
> could do that as a follow-up if needed.
>
> With 3-subranges, int_range_max is now 592 bytes versus 40912 for
> trunk, and versus 4112 bytes for GCC12!  The penalty is 5.04% for VRP
> and 3.02% for threading, with no noticeable change in overall
> compilation (0.27%).  This is more than covered by our 13.26%
> improvements for the legacy removal + wide_int conversion.

Thanks for doing this.

> I think this approach is a good alternative, while providing us with
> flexibility going forward.  For example, we could try defaulting to a
> 8 sub-ranges for a noticeable improvement in VRP.  We could also use
> large sub-ranges for switch analysis to avoid resizing.
>
> Another approach I tried was always resizing.  With this, we could
> drop the whole int_range<N> nonsense, and have irange just hold a
> resizable range.  This simplified things, but incurred a 7% penalty on
> ipa_cp.  This was hard to pinpoint, and I'm not entirely convinced
> this wasn't some artifact of valgrind.  However, until we're sure,
> let's avoid massive changes, especially since IPA changes are coming
> up.
>
> For the curious, a particular hot spot for IPA in this area was:
>
> ipcp_vr_lattice::meet_with_1 (const value_range *other_vr)
> {
> ...
> ...
>   value_range save (m_vr);
>   m_vr.union_ (*other_vr);
>   return m_vr != save;
> }
>
> The problem isn't the resizing (since we do that at most once) but the
> fact that for some functions with lots of callers we end up a huge
> range that gets copied and compared for every meet operation.  Maybe
> the IPA algorithm could be adjusted somehow??.

Well, the above just wants to know whether the union_ operation changed
the range.  I suppose that would be an interesting (and easy to compute?)
secondary output of union_ and it seems it already computes that (but
maybe not correctly?).  So I suggest to change the above to

  bool res;
  if (flag_checking)
   {
      value_range save (m_vr);
      res = m_vr.union_ (*other_vr);
      gcc_assert (res == (m_vr != save));
   }
 else
    res = m_vr.union (*other_vr);
 return res;

Btw, why's there a trailing underscore for union but not intersect?

Richard.

> Anywhooo... for now there is nothing to worry about, since value_range
> still has 2 subranges and is not resizable.  But we should probably
> think what if anything we want to do here, as I envision IPA using
> infinite ranges here (well, int_range_max) and handling frange's, etc.
>
> I'll hold off a day or two, as I'd appreciate feedback here.
>
> gcc/ChangeLog:
>
>         PR tree-optimization/109695
>         * value-range.cc (irange::operator=): Resize range.
>         (irange::union_): Same.
>         (irange::intersect): Same.
>         (irange::invert): Same.
>         (int_range_max): Default to 3 sub-ranges and resize as needed.
>         * value-range.h (irange::maybe_resize): New.
>         (~int_range): New.
>         (int_range::int_range): Adjust for resizing.
>         (int_range::operator=): Same.
> ---
>  gcc/value-range.cc | 14 +++++++
>  gcc/value-range.h  | 98 ++++++++++++++++++++++++++++++++--------------
>  2 files changed, 82 insertions(+), 30 deletions(-)
>
> diff --git a/gcc/value-range.cc b/gcc/value-range.cc
> index def9299dc0e..cea4ff59254 100644
> --- a/gcc/value-range.cc
> +++ b/gcc/value-range.cc
> @@ -901,6 +901,9 @@ frange::set_nonnegative (tree type)
>  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)
> @@ -1340,6 +1343,7 @@ irange::union_ (const vrange &v)
>    // 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];
> @@ -1439,6 +1443,11 @@ irange::intersect (const vrange &v)
>    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 (m_type);
>    unsigned bld_pair = 0;
>    unsigned bld_lim = m_max_ranges;
> @@ -1646,6 +1655,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 22b0250b11b..0da2a42764a 100644
> --- a/gcc/value-range.h
> +++ b/gcc/value-range.h
> @@ -167,9 +167,10 @@ public:
>    void set_nonzero_bits (const wide_int &bits);
>
>  protected:
> +  void maybe_resize (int needed);
>    virtual void set (tree, tree, value_range_kind = VR_RANGE) override;
>    virtual bool contains_p (tree cst) const override;
> -  irange (wide_int *, unsigned);
> +  irange (wide_int *, unsigned nranges, bool resizable);
>
>     // In-place operators.
>    bool irange_contains_p (const irange &) const;
> @@ -179,6 +180,8 @@ protected:
>
>    void verify_range ();
>
> +  // 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 *);
> @@ -192,16 +195,22 @@ private:
>
>    bool intersect (const wide_int& lb, const wide_int& ub);
>    unsigned char m_num_ranges;
> -  const unsigned char m_max_ranges;
> +  bool m_resizable;
> +  unsigned char m_max_ranges;
>    tree m_type;
>    wide_int m_nonzero_mask;
> +protected:
>    wide_int *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:
> @@ -211,7 +220,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 &);
>  protected:
>    int_range (tree, tree, value_range_kind = VR_RANGE);
> @@ -451,6 +460,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;
> +      wide_int *newmem = new wide_int[m_max_ranges * 2];
> +      memcpy (newmem, m_base, sizeof (wide_int) * 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:
> @@ -461,10 +502,6 @@ public:
>
>  typedef int_range<2> 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.
> @@ -757,8 +794,9 @@ gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
>  // Constructors for irange
>
>  inline
> -irange::irange (wide_int *base, unsigned nranges)
> +irange::irange (wide_int *base, unsigned nranges, bool resizable)
>    : vrange (VR_IRANGE),
> +    m_resizable (resizable),
>      m_max_ranges (nranges)
>  {
>    m_base = base;
> @@ -767,52 +805,52 @@ irange::irange (wide_int *base, unsigned nranges)
>
>  // 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)
>  {
>    set (type, wmin, wmax, 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.40.0
>