From: Richard Sandiford <richard.sandiford@arm.com>
To: Aldy Hernandez via Gcc-patches <gcc-patches@gcc.gnu.org>
Cc: Aldy Hernandez <aldyh@redhat.com>, Jakub Jelinek <jakub@redhat.com>
Subject: Re: [RFC] trailing_wide_ints with runtime variable lengths
Date: Fri, 01 Jul 2022 19:26:23 +0100 [thread overview]
Message-ID: <mpth740665s.fsf@arm.com> (raw)
In-Reply-To: <20220629092157.230287-1-aldyh@redhat.com> (Aldy Hernandez via Gcc-patches's message of "Wed, 29 Jun 2022 11:21:57 +0200")
Aldy Hernandez via Gcc-patches <gcc-patches@gcc.gnu.org> writes:
> 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.
Thanks for the discussion downthread. I had some of the same questions
as Jakub, but you've answered them :-)
> 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
s/lengthed/length/
> + 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.
s/N/NUM_ELEMENTS/
> + NUM_ELEMENTS is the number of elements, or N if none specified. */
and here maybe just "NUM_ELEMENTS defaults to N."
> 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;
Can we gcc_checking_assert that num_elements <= N instead, like above?
Otherwise we'd get GIGO.
OK with those changes, thanks.
Richard
> + return (num_elements * max_len - 1) * sizeof (HOST_WIDE_INT);
> }
>
> /* This macro is used in structures that end with a trailing_wide_ints field
prev parent reply other threads:[~2022-07-01 18:26 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
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 [this message]
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=mpth740665s.fsf@arm.com \
--to=richard.sandiford@arm.com \
--cc=aldyh@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=jakub@redhat.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).