From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id A8E933857B96 for ; Fri, 1 Jul 2022 18:26:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A8E933857B96 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 7F20D143D; Fri, 1 Jul 2022 11:26:25 -0700 (PDT) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.37]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 9D2C43F5A1; Fri, 1 Jul 2022 11:26:24 -0700 (PDT) From: Richard Sandiford To: Aldy Hernandez via Gcc-patches Mail-Followup-To: Aldy Hernandez via Gcc-patches , Aldy Hernandez , Jakub Jelinek , richard.sandiford@arm.com Cc: Aldy Hernandez , Jakub Jelinek Subject: Re: [RFC] trailing_wide_ints with runtime variable lengths References: <20220629092157.230287-1-aldyh@redhat.com> Date: Fri, 01 Jul 2022 19:26:23 +0100 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") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Status: No, score=-55.6 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_NONE, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, KAM_SHORT, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 01 Jul 2022 18:26:28 -0000 Aldy Hernandez via Gcc-patches 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 {}; > } > > -/* 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 > 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 > inline void > -trailing_wide_ints ::set_precision (unsigned int precision) > +trailing_wide_ints ::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 ::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 > inline size_t > -trailing_wide_ints ::extra_size (unsigned int precision) > +trailing_wide_ints ::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