[RFC] trailing_wide_ints with runtime variable lengths

[Aldy Hernandez]

FYI...if no one has anything to say, I'd like to formally post this for
review.

So.... OK for trunk?
Aldy

On Wed, Jun 29, 2022, 11:22 Aldy Hernandez <aldyh@redhat.com> wrote:

> Currently global ranges are stored in SSA_NAME_RANGE_INFO as a pair of
> wide_int-like objects along with the nonzero bits.  We frequently lose
> precision when streaming out our higher resolution iranges.  The plan
> was always to store the full irange between passes.  However, as was
> originally discussed eons ago:
>
>         https://gcc.gnu.org/pipermail/gcc-patches/2017-May/475139.html
>
> ...we need a memory efficient way of saving iranges, preferably using
> the trailing_wide_ints idiom.
>
> The problem with doing so is that trailing_wide_ints assume a
> compile-time specified number of elements.  For irange, we need to
> determine the size at run-time.
>
> One solution is to adapt trailing_wide_ints such that N is the maximum
> number of elements allowed, and allow setting the actual number at
> run-time (defaulting to N).  The attached patch does this, while
> requiring no changes to existing users.
>
> It uses a byte to store the number of elements in the
> trailing_wide_ints control word.  The control word is currently a
> 16-bit precision, an 8-bit max-length, and the rest is used for
> m_len[N].  On a 64-bit architecture, this allows for 5 elements in
> m_len without having to use an extra word.  With this patch, m_len[]
> would be smaller by one byte (4) before consuming the padding.  This
> shouldn't be a problem as the only users of trailing_wide_ints use N=2
> for NUM_POLY_INT_COEFFS in aarch64, and N=3 for range_info_def.
>
> For irange, my plan is to use one more word to fit a maximum of 12
> elements (the above 4 plus 8 more).  This would allow for 6 pairs of
> sub-ranges which would be more than adequate for our needs.  In
> previous tests we found that 99% of ranges fit within 3-4 pairs.  More
> precisely, this would allow for 5 pairs, plus the nonzero bits, plus a
> spare wide-int for future development.
>
> Ultimately this means that streaming an irange would consume one more
> word than what we currently do for range_info_def.  IMO this is a nice
> trade-off considering we started storing a slew of wide-ints directly
> ;-).
>
> I'm not above rolling an altogether different approach, but would
> prefer to use the existing trailing infrastructure since it's mostly
> what we need.
>
> Thoughts?
>
> p.s. Tested and benchmarked on x86-64 Linux.  There was no discernible
> performance change in our benchmark suite.
>
> gcc/ChangeLog:
>
>         * wide-int.h (struct trailing_wide_ints): Add m_num_elements.
>         (trailing_wide_ints::set_precision): Add num_elements argument.
>         (trailing_wide_ints::extra_size): Same.
> ---
>  gcc/wide-int.h | 42 +++++++++++++++++++++++++++++-------------
>  1 file changed, 29 insertions(+), 13 deletions(-)
>
> diff --git a/gcc/wide-int.h b/gcc/wide-int.h
> index 8041b6104f9..f68ccf0a0c5 100644
> --- a/gcc/wide-int.h
> +++ b/gcc/wide-int.h
> @@ -1373,10 +1373,13 @@ namespace wi
>      : public int_traits <wide_int_storage> {};
>  }
>
> -/* An array of N wide_int-like objects that can be put at the end of
> -   a variable-sized structure.  Use extra_size to calculate how many
> -   bytes beyond the sizeof need to be allocated.  Use set_precision
> -   to initialize the structure.  */
> +/* A variable-lengthed array of wide_int-like objects that can be put
> +   at the end of a variable-sized structure.  The number of objects is
> +   at most N and can be set at runtime by using set_precision().
> +
> +   Use extra_size to calculate how many bytes beyond the
> +   sizeof need to be allocated.  Use set_precision to initialize the
> +   structure.  */
>  template <int N>
>  struct GTY((user)) trailing_wide_ints
>  {
> @@ -1387,6 +1390,9 @@ private:
>    /* The shared maximum length of each number.  */
>    unsigned char m_max_len;
>
> +  /* The number of elements.  */
> +  unsigned char m_num_elements;
> +
>    /* The current length of each number.
>       Avoid char array so the whole structure is not a typeless storage
>       that will, in turn, turn off TBAA on gimple, trees and RTL.  */
> @@ -1399,12 +1405,15 @@ private:
>  public:
>    typedef WIDE_INT_REF_FOR (trailing_wide_int_storage) const_reference;
>
> -  void set_precision (unsigned int);
> +  void set_precision (unsigned int precision, unsigned int num_elements =
> N);
>    unsigned int get_precision () const { return m_precision; }
> +  unsigned int num_elements () const { return m_num_elements; }
>    trailing_wide_int operator [] (unsigned int);
>    const_reference operator [] (unsigned int) const;
> -  static size_t extra_size (unsigned int);
> -  size_t extra_size () const { return extra_size (m_precision); }
> +  static size_t extra_size (unsigned int precision,
> +                           unsigned int num_elements = N);
> +  size_t extra_size () const { return extra_size (m_precision,
> +                                                 m_num_elements); }
>  };
>
>  inline trailing_wide_int_storage::
> @@ -1457,11 +1466,14 @@ trailing_wide_int_storage::operator = (const T &x)
>  }
>
>  /* Initialize the structure and record that all elements have precision
> -   PRECISION.  */
> +   PRECISION.  NUM_ELEMENTS can be no more than N.  */
>  template <int N>
>  inline void
> -trailing_wide_ints <N>::set_precision (unsigned int precision)
> +trailing_wide_ints <N>::set_precision (unsigned int precision,
> +                                      unsigned int num_elements)
>  {
> +  gcc_checking_assert (num_elements <= N);
> +  m_num_elements = num_elements;
>    m_precision = precision;
>    m_max_len = ((precision + HOST_BITS_PER_WIDE_INT - 1)
>                / HOST_BITS_PER_WIDE_INT);
> @@ -1484,15 +1496,19 @@ trailing_wide_ints <N>::operator [] (unsigned int
> index) const
>                           m_len[index].len, m_precision);
>  }
>
> -/* Return how many extra bytes need to be added to the end of the
> structure
> -   in order to handle N wide_ints of precision PRECISION.  */
> +/* Return how many extra bytes need to be added to the end of the
> +   structure in order to handle N wide_ints of precision PRECISION.
> +   NUM_ELEMENTS is the number of elements, or N if none specified.  */
>  template <int N>
>  inline size_t
> -trailing_wide_ints <N>::extra_size (unsigned int precision)
> +trailing_wide_ints <N>::extra_size (unsigned int precision,
> +                                   unsigned int num_elements)
>  {
>    unsigned int max_len = ((precision + HOST_BITS_PER_WIDE_INT - 1)
>                           / HOST_BITS_PER_WIDE_INT);
> -  return (N * max_len - 1) * sizeof (HOST_WIDE_INT);
> +  if (num_elements > N)
> +    num_elements = N;
> +  return (num_elements * max_len - 1) * sizeof (HOST_WIDE_INT);
>  }
>
>  /* This macro is used in structures that end with a trailing_wide_ints
> field
> --
> 2.36.1
>
>