From: Aldy Hernandez <aldyh@redhat.com>
To: GCC patches <gcc-patches@gcc.gnu.org>
Cc: Andrew MacLeod <amacleod@redhat.com>,
Richard Sandiford <richard.sandiford@arm.com>,
Jakub Jelinek <jakub@redhat.com>
Subject: Re: [RFC] trailing_wide_ints with runtime variable lengths
Date: Fri, 1 Jul 2022 16:12:55 +0200 [thread overview]
Message-ID: <CAGm3qMVocvOtASigzLotdCM5tk92TDm=RmbMXLw3cO0d7W=iUA@mail.gmail.com> (raw)
In-Reply-To: <20220629092157.230287-1-aldyh@redhat.com>
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
>
>
next prev parent reply other threads:[~2022-07-01 14:13 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-06-29 9:21 Aldy Hernandez
2022-07-01 14:12 ` Aldy Hernandez [this message]
2022-07-01 14:58 ` Jakub Jelinek
2022-07-01 16:47 ` Aldy Hernandez
2022-07-01 16:58 ` Jakub Jelinek
2022-07-01 17:43 ` Aldy Hernandez
2022-07-01 18:53 ` Jakub Jelinek
2022-07-01 20:31 ` Aldy Hernandez
2022-07-01 20:40 ` Aldy Hernandez
2022-07-01 18:26 ` Richard Sandiford
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAGm3qMVocvOtASigzLotdCM5tk92TDm=RmbMXLw3cO0d7W=iUA@mail.gmail.com' \
--to=aldyh@redhat.com \
--cc=amacleod@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=jakub@redhat.com \
--cc=richard.sandiford@arm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).