[RFC] Introduce -finline-memset-loops
Richard Biener
richard.guenther@gmail.com
Thu Jan 19 11:58:24 GMT 2023
On Thu, Jan 19, 2023 at 12:25 PM Alexandre Oliva <oliva@adacore.com> wrote:
>
> On Jan 16, 2023, Richard Biener <richard.guenther@gmail.com> wrote:
>
> > On Sat, Jan 14, 2023 at 2:55 AM Alexandre Oliva <oliva@adacore.com> wrote:
> >> Target-specific code is great for tight optimizations, but the main
> >> purpose of this feature is not an optimization. AFAICT it actually
> >> slows things down in general (due to code growth, and to conservative
> >> assumptions about alignment), except perhaps for some microbenchmarks.
> >> It's rather a means to avoid depending on the C runtime, particularly
> >> due to compiler-introduced memset calls.
>
> > OK, that's what I guessed but you didn't spell out. So does it make sense
> > to mention -ffreestanding in the docs at least? My fear is that we'd get
> > complaints that -O3 -finline-memset-loops turns nicely optimized memset
> > loops into dumb ones (via loop distribution and then stupid re-expansion).
> > So does it also make sense to turn off -floop-distribute-patterns[-memset]
> > with -finline-memset-loops?
>
> I don't think they should be tied together. Verbose as it is, the
> expansion of memset is a sort of local optimum given what the compiler
> knows about length and alignment: minimizing what can be minimized,
> namely the compare count, by grouping stores in large straight-line
> blocks.
>
> Though an optimized memset could in theory perform better, whether
> through ifuncs or by bumping alignment, if you're tuning generated code
> for a specific target, and you know dest is aligned, the generated code
> can likely beat a general-purpose optimized memset, even if by a thin
> margin, such as the code that the general-purpose memset would have to
> run to detect the alignment and realize it doesn't need to be bumped,
> and to extend the byte value to be stored to wider modes.
>
> So I can envision cases in which -floop-distribute-patterns could turn
> highly inefficient stores into a memset with known-strict alignment and
> length multiplier, that could then be profitably expanded inline so as
> to take advantage of both for performance reasons.
>
> Indeed, when I started working on this, I thought the issue was
> performance, and this led me to pursue the store-by-multiple-pieces
> logic. It can indeed bring about performance improvements, both over
> generic-target and highly-optimized memset implementations. But it can
> also be put to use to avoid C runtime calls. So while I wouldn't
> suggest enabling it by default at any optimization level, I wouldn't tie
> it to the single purpose of freestanding environments either.
>
>
> >> My initial goal was to be able to show that inline expansion would NOT
> >> bring about performance improvements, but performance was not the
> >> concern that led to the request.
> >>
> >> If the approach seems generally acceptable, I may even end up extending
> >> it to other such builtins. I have a vague recollection that memcmp is
> >> also an issue for us.
>
> > The C/C++ runtime produce at least memmove, memcpy and memcmp as well.
>
> *nod*. The others are far more challenging to expand inline in a way
> that could potentially be more performant:
>
> - memcmp can only do by_pieces when testing for equality, presumably
> because grouping multiple bytes into larger words to speed things up
> won't always get you the expected result if you just subtract the larger
> words, endianness reversal prior to subtracting might be required, which
> would harm performance. I don't see that using similar
> power-of-two-sizes grouping strategies to minimize looping overheads
> would be so advantageous, if at all, given the need for testing and
> branching at every word.
>
> - memcpy seems doable, but all of the block moves other than cpymem
> assume non-overlapping memcpy. Even if we were to output a test for
> overlap that a naïve expansion would break, and an alternate block to go
> backwards, all of the block copying logic would have to be "oriented" to
> proceed explicitly forward, backward, or don't-care, where currently we
> only have don't-care.
>
> Though my initial plan, when posting this patch, was to see how well the
> general approach was received, before thinking much about how to apply
> it to the other builtins, now I am concerned that extending it to them
> is more than I can tackle.
>
> Would it make more sense to extend it, even constrained by the
> limitations mentioned above, or handle memset only? In the latter case,
> would it still make sense to adopt a command-line option that suggests a
> broader effect than it already has, even if it's only a hopeful future
> extension? -finline-all-stringops[={memset,memcpy,...}], that you
> suggested, seems to be a reasonable and extensible one to adopt.
Well, if the main intent is to avoid relying on a C runtime for calls
generated by the compiler then yes! Otherwise it would be incomplete.
In that light ...
> >> Is (optionally) tending to this (uncommon, I suppose) need (or
> >> preference?) not something GCC would like to do?
>
> > Sure, I think for the specific intended purpose that would be fine.
>
> Cool!
>
> > It should also only apply to __builtin_memset calls, not to memset
> > calls from user code?
>
> I suppose it could be argued both ways. The situations that I had in
> mind either already are or could be made __builtin_memset calls, but I
> can't think of reasons to prevent explicit memset calls from such
> expansion. Do you have any specific purpose in mind?
... when the user writes memcpy () then he's supposed to provide
a definition, even with -ffreestanding. But one could argue that with
-ffreestanding the compiler is responsible to provide memcpy () if
it itself is introducing calls to it.
> In favor of allowing non-__builtin_ memset to be so expanded, I'll
> mention that I caught a number of corner cases while developing the
> following improved version of the earlier patch (now handling even
> large-constant lengths) by bootstrapping the compiler with the option
> enabled by default. Without that, testcases would have to be a *lot*
> more thorough.
I can see that, the question is really what the option is targeted at.
For *-linux at least I can't see a reason to use it - performance
cannot be it because glibc is decent.
So the question really boils down to the intended audience. If
it's possibly extended to cover strcpy then for -ffreestanding
handling user calls to the functions might make sense, but
where do we stop there?
Richard.
>
> Introduce -finline-memset-loops
>
> From: Alexandre Oliva <oliva@adacore.com>
>
> try_store_by_multiple_pieces was added not long ago, enabling
> variable-sized memset to be expanded inline when the worst-case
> in-range constant length would, using conditional blocks with powers
> of two to cover all possibilities of length and alignment.
>
> This patch extends the memset expansion to start with a loop, so as to
> still take advantage of known alignment even with long lengths, but
> without necessarily adding store blocks for every power of two.
>
> This makes it possible for any memset call to be expanded, even if
> storing a single byte per iteration. Surely efficient implementations
> of memset can do better, with a pre-loop to increase alignment, but
> that would likely be excessive for inline expansions of memset.
>
> Still, in some cases, users prefer to inline memset, even if it's not
> as performant, or when it's known to be performant in ways the
> compiler can't tell, to avoid depending on a C runtime library.
>
> With this flag, global or per-function optimizations may enable inline
> expansion of memset to be selectively requested, while the
> infrastructure for that may enable us to introduce per-target tuning
> to enable such looping even advantageous, even if not explicitly
> requested.
>
>
> for gcc/ChangeLog
>
> * builtins.cc (try_store_by_multiple_pieces): Support starting
> with a loop.
> * common.opt (finline-memset-loops): New.
> * doc/invoke.texi (-finline-memset-loops): Add.
>
> for gcc/testsuite/ChangeLog
>
> * gcc.dg/torture/inline-mem-set-1.c: New.
> ---
> gcc/builtins.cc | 99 +++++++++++++++++++++--
> gcc/common.opt | 4 +
> gcc/doc/invoke.texi | 13 +++
> gcc/testsuite/gcc.dg/torture/inline-mem-set-1.c | 84 ++++++++++++++++++++
> 4 files changed, 192 insertions(+), 8 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/torture/inline-mem-set-1.c
>
> diff --git a/gcc/builtins.cc b/gcc/builtins.cc
> index af45829875e6c..733fe17ede622 100644
> --- a/gcc/builtins.cc
> +++ b/gcc/builtins.cc
> @@ -4322,6 +4322,10 @@ try_store_by_multiple_pieces (rtx to, rtx len, unsigned int ctz_len,
> int tst_bits = (max_bits != min_bits ? max_bits
> : floor_log2 (max_len ^ min_len));
>
> + /* Save the pre-blksize values. */
> + int orig_max_bits = max_bits;
> + int orig_tst_bits = tst_bits;
> +
> /* Check whether it's profitable to start by storing a fixed BLKSIZE
> bytes, to lower max_bits. In the unlikely case of a constant LEN
> (implied by identical MAX_LEN and MIN_LEN), we want to issue a
> @@ -4361,9 +4365,70 @@ try_store_by_multiple_pieces (rtx to, rtx len, unsigned int ctz_len,
> if (max_bits >= 0)
> xlenest += ((HOST_WIDE_INT_1U << max_bits) * 2
> - (HOST_WIDE_INT_1U << ctz_len));
> - if (!can_store_by_pieces (xlenest, builtin_memset_read_str,
> - &valc, align, true))
> - return false;
> + bool max_loop = false;
> + /* Skip the test in case of overflow in xlenest. It shouldn't
> + happen because of the way max_bits and blksize are related, but
> + it doesn't hurt to test. */
> + if (blksize > xlenest
> + || !can_store_by_pieces (xlenest, builtin_memset_read_str,
> + &valc, align, true))
> + {
> + if (!flag_inline_memset_loops)
> + return false;
> +
> + for (max_bits = orig_max_bits;
> + max_bits >= sctz_len;
> + --max_bits)
> + {
> + xlenest = ((HOST_WIDE_INT_1U << max_bits) * 2
> + - (HOST_WIDE_INT_1U << ctz_len));
> + /* Check that blksize plus the bits to be stored as blocks
> + sized at powers of two can be stored by pieces. This is
> + like the test above, but with smaller max_bits. Skip
> + orig_max_bits (it would be redundant). Also skip in case
> + of overflow. */
> + if (max_bits < orig_max_bits
> + && xlenest + blksize >= xlenest
> + && can_store_by_pieces (xlenest + blksize,
> + builtin_memset_read_str,
> + &valc, align, true))
> + {
> + max_loop = true;
> + break;
> + }
> + if (blksize
> + && can_store_by_pieces (xlenest,
> + builtin_memset_read_str,
> + &valc, align, true))
> + {
> + max_len += blksize;
> + min_len += blksize;
> + tst_bits = orig_tst_bits;
> + blksize = 0;
> + max_loop = true;
> + break;
> + }
> + if (max_bits == sctz_len)
> + {
> + --sctz_len;
> + --ctz_len;
> + }
> + }
> + if (!max_loop)
> + return false;
> + /* If the boundaries are such that min and max may run a
> + different number of trips in the initial loop, the remainder
> + needs not be between the moduli, so set tst_bits to cover all
> + bits. Otherwise, if the trip counts are the same, max_len
> + has the common prefix, and the previously-computed tst_bits
> + is usable. */
> + if (max_len >> max_bits > min_len >> max_bits)
> + tst_bits = max_bits;
> + }
> + /* ??? Do we have to check that all powers of two lengths from
> + max_bits down to ctz_len pass can_store_by_pieces? As in, could
> + it possibly be that xlenest passes while smaller power-of-two
> + sizes don't? */
>
> by_pieces_constfn constfun;
> void *constfundata;
> @@ -4405,7 +4470,9 @@ try_store_by_multiple_pieces (rtx to, rtx len, unsigned int ctz_len,
> the least significant bit possibly set in the length. */
> for (int i = max_bits; i >= sctz_len; i--)
> {
> + rtx_code_label *loop_label = NULL;
> rtx_code_label *label = NULL;
> +
> blksize = HOST_WIDE_INT_1U << i;
>
> /* If we're past the bits shared between min_ and max_len, expand
> @@ -4419,18 +4486,31 @@ try_store_by_multiple_pieces (rtx to, rtx len, unsigned int ctz_len,
> profile_probability::even ());
> }
> /* If we are at a bit that is in the prefix shared by min_ and
> - max_len, skip this BLKSIZE if the bit is clear. */
> - else if ((max_len & blksize) == 0)
> + max_len, skip the current BLKSIZE if the bit is clear, but do
> + not skip the loop, even if it doesn't require
> + prechecking. */
> + else if ((max_len & blksize) == 0
> + && !(max_loop && i == max_bits))
> continue;
>
> + if (max_loop && i == max_bits)
> + {
> + loop_label = gen_label_rtx ();
> + emit_label (loop_label);
> + /* Since we may run this multiple times, don't assume we
> + know anything about the offset. */
> + clear_mem_offset (to);
> + }
> +
> /* Issue a store of BLKSIZE bytes. */
> + bool update_needed = i != sctz_len || loop_label;
> to = store_by_pieces (to, blksize,
> constfun, constfundata,
> align, true,
> - i != sctz_len ? RETURN_END : RETURN_BEGIN);
> + update_needed ? RETURN_END : RETURN_BEGIN);
>
> /* Adjust REM and PTR, unless this is the last iteration. */
> - if (i != sctz_len)
> + if (update_needed)
> {
> emit_move_insn (ptr, force_operand (XEXP (to, 0), NULL_RTX));
> to = replace_equiv_address (to, ptr);
> @@ -4438,6 +4518,11 @@ try_store_by_multiple_pieces (rtx to, rtx len, unsigned int ctz_len,
> emit_move_insn (rem, force_operand (rem_minus_blksize, NULL_RTX));
> }
>
> + if (loop_label)
> + emit_cmp_and_jump_insns (rem, GEN_INT (blksize), GE, NULL,
> + ptr_mode, 1, loop_label,
> + profile_probability::likely ());
> +
> if (label)
> {
> emit_label (label);
> diff --git a/gcc/common.opt b/gcc/common.opt
> index d0371aec8db5f..5d28f054241ad 100644
> --- a/gcc/common.opt
> +++ b/gcc/common.opt
> @@ -1874,6 +1874,10 @@ finline-atomics
> Common Var(flag_inline_atomics) Init(1) Optimization
> Inline __atomic operations when a lock free instruction sequence is available.
>
> +finline-memset-loops
> +Common Var(flag_inline_memset_loops) Init(0) Optimization
> +Inline memset even if it requires loops.
> +
> fcf-protection
> Common RejectNegative Alias(fcf-protection=,full)
>
> diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
> index 631c00582bf85..8f8d52bbeef68 100644
> --- a/gcc/doc/invoke.texi
> +++ b/gcc/doc/invoke.texi
> @@ -548,7 +548,8 @@ Objective-C and Objective-C++ Dialects}.
> -fgcse-sm -fhoist-adjacent-loads -fif-conversion @gol
> -fif-conversion2 -findirect-inlining @gol
> -finline-functions -finline-functions-called-once -finline-limit=@var{n} @gol
> --finline-small-functions -fipa-modref -fipa-cp -fipa-cp-clone @gol
> +-finline-memset-loops -finline-small-functions @gol
> +-fipa-modref -fipa-cp -fipa-cp-clone @gol
> -fipa-bit-cp -fipa-vrp -fipa-pta -fipa-profile -fipa-pure-const @gol
> -fipa-reference -fipa-reference-addressable @gol
> -fipa-stack-alignment -fipa-icf -fira-algorithm=@var{algorithm} @gol
> @@ -11961,6 +11962,16 @@ in its own right.
> Enabled at levels @option{-O1}, @option{-O2}, @option{-O3} and @option{-Os},
> but not @option{-Og}.
>
> +@item -finline-memset-loops
> +@opindex finline-memset-loops
> +Expand @code{memset} calls inline, even when the length is variable or
> +big enough as to require looping. This may enable the compiler to take
> +advantage of known alignment and length multipliers, but it will often
> +generate code that is less efficient than performant implementations of
> +@code{memset}, and grow code size so much that even a less performant
> +@code{memset} may run faster due to better use of the code cache. This
> +option is disabled by default.
> +
> @item -fearly-inlining
> @opindex fearly-inlining
> Inline functions marked by @code{always_inline} and functions whose body seems
> diff --git a/gcc/testsuite/gcc.dg/torture/inline-mem-set-1.c b/gcc/testsuite/gcc.dg/torture/inline-mem-set-1.c
> new file mode 100644
> index 0000000000000..4de51df006ede
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/torture/inline-mem-set-1.c
> @@ -0,0 +1,84 @@
> +/* { dg-do compile } */
> +/* { dg-options "-finline-memset-loops -gno-record-gcc-switches -fno-lto" } */
> +
> +void *zero (unsigned long long (*p)[32], int n)
> +{
> + return __builtin_memset (p, 0, n * sizeof (*p));
> +}
> +
> +void *ones (char (*p)[128], int n)
> +{
> + return __builtin_memset (p, -1, n * sizeof (*p));
> +}
> +
> +void *opt2 (int *p, int i)
> +{
> + return __builtin_memset (p, 0, (i ? 1024 : 2) * sizeof (*p));
> +}
> +
> +void *opt8 (int *p, int i)
> +{
> + return __builtin_memset (p, 0, (i ? 1024 : 8) * sizeof (*p));
> +}
> +
> +void *opt32 (int *p, int i)
> +{
> + return __builtin_memset (p, 0, (i ? 1024 : 32) * sizeof (*p));
> +}
> +
> +void *opt128 (int *p, int i)
> +{
> + return __builtin_memset (p, 0, (i ? 1024 : 128) * sizeof (*p));
> +}
> +
> +void *opt512 (int *p, int i)
> +{
> + return __builtin_memset (p, 0, (i ? 1024 : 512) * sizeof (*p));
> +}
> +
> +void *opt_primes (int *p, int i)
> +{
> + return __builtin_memset (p, 0, (i ? 509 : 7) * sizeof (*p));
> +}
> +
> +void *opt_primes_blk (int *p, int i)
> +{
> + return __builtin_memset (p, 0, (i ? 521 : 9) * sizeof (*p));
> +}
> +
> +void *huge (long (*p)[16384])
> +{
> + return __builtin_memset (p, 0, sizeof (*p));
> +}
> +
> +void *hugep1 (long (*p)[16384+1])
> +{
> + return __builtin_memset (p, 0, sizeof (*p));
> +}
> +
> +void *hugep4 (long (*p)[16384+4])
> +{
> + return __builtin_memset (p, 0, sizeof (*p));
> +}
> +
> +void *hugep16 (long (*p)[16384+16])
> +{
> + return __builtin_memset (p, 0, sizeof (*p));
> +}
> +
> +void *hugep64 (long (*p)[16384+64])
> +{
> + return __builtin_memset (p, 0, sizeof (*p));
> +}
> +
> +void *hugep256 (long (*p)[16384+256])
> +{
> + return __builtin_memset (p, 0, sizeof (*p));
> +}
> +
> +void *hugep1024p256p64p16p4p1 (long (*p)[16384+1024+64+16+4+1])
> +{
> + return __builtin_memset (p, 0, sizeof (*p));
> +}
> +
> +/* { dg-final { scan-assembler-not "memset" } } */
>
>
> --
> Alexandre Oliva, happy hacker https://FSFLA.org/blogs/lxo/
> Free Software Activist GNU Toolchain Engineer
> Disinformation flourishes because many people care deeply about injustice
> but very few check the facts. Ask me about <https://stallmansupport.org>
More information about the Gcc-patches
mailing list