Re: [middle-end PATCH v2] Improve bitreverse expansion on x86_64 and cris.
Georg-Johann Lay <[email protected]>
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
Am 20.08.26 um 00:51 schrieb Roger Sayle:
>
> This patch is a revision of my previous patch to use add_optab in
> the expansion of bitreverse which improves code generation on x86,
> cris, riscv, parisc, sh and possibly other targets.
> https://gcc.gnu.org/pipermail/gcc-patches/2026-August/726901.html
>
> This patch addresses Jeff Law's (and Georg-Johann Lay's earlier)
> concerns that targets without a shift-add instruction don't benefit
> from the use of PLUS, and may potentially hurt optimization. Alas
> it's not sufficient to check whether a target supports an addsi3
> optab, and even (the default) rtx_costs can't be relied upon.
> The solution here is to introduce an aop_optab (for any_or_plus)
> to allow a backend complete control over choices of PLUS vs. IOR
> vs. XOR. For example, x86_64 would prefer IOR (or XOR) over PLUS
> for V1TImode. As a worked example, this patch defines an aop_optab
> for AVR to always use PLUS.
>
> Interestingly, testing this functionality on AVR is fairly difficult,
> as the backend provides expansions for bitreverse, bswap and rotate,
> i.e. all the obvious places where aop_optab would be used. Fortunately,
> I was able to identify an optimization in store_fixed_bitfield_1 that
> affects code generation (on avr-elf).
>
> Consider the test case:
>
> typedef struct {
> int a : 1;
> int b : 1;
> int c : 16;
> int d : 14;
> } S;
>
> S foo(S x, unsigned char y)
> {
> x.c = y;
> return x;
> }
>
> Currently, with -O2 x86_64 generates (both sall and orl):
>
> foo: andl $-262141, %edi
> movzbl %sil, %esi
> sall $2, %esi
> movl %edi, %eax
> orl %esi, %eax
> ret
>
> with this revised patch to make use of aop_optab, we now get:
>
> foo: movzbl %sil, %esi
> andl $-262141, %edi
> leal (%rdi,%rsi,4), %eax
> ret
>
> On avr-elf, without the avr.md change we would get (a PLUS):
>
> foo: mov r18,r20
> lsl r18
> lsl r18
> andi r22,lo8(3)
> add r22,r18
> clr r23
> bst r20,6
> bld r23,0
> bst r20,7
> bld r23,1
> andi r24,lo8(-4)
> ret
>
> But with avr.md's define_expand for aop<mode>3 we restore the original:
>
> foo: mov r18,r20
> lsl r18
> lsl r18
> andi r22,lo8(3)
> or r22,r18
> clr r23
> bst r20,6
> bld r23,0
> bst r20,7
> bld r23,1
> andi r24,lo8(-4)
> ret
Hi Roger,
I think the change is ok for avr, though I am not a maintainer
and hence I can't approve.
In the above avr code, AND and OR have exactly the same resource
consumption and operand capabilities.
Johann
> This patch has been tested on x86_64-pc-linux-gnu with make bootstrap
> and make -k check, both with and without --target_board=unix{-m32}
> with no new failures. Ok for mainline?
>
> If (this approach/patch is) approved, I can document AOP and aop
> in a follow-up pach to rtl.texi, but these are currently an internal
> detail (work in progress).
>
> 2026-08-19 Roger Sayle <[email protected]>
>
> gcc/ChangeLog
> * config/avr/avr.md (aop<mode>3): New define_expand to specify
> that IOR should always be used to implement any_or_plus (AOP).
> * expmed.cc (store_fixed_bit_field_1): Use new aop_optab when
> writing a value into a fixed size bitfield of a structure.
> * optabs.cc (expand_binop): If target doesn't provide a suitable
> aop<mode>3 instruction, intelligently use PLUS or IOR instead.
> (expand_binop): For rotations, use aop_optab to select AOP
> implementation instead of hard-coding add_optab.
> (expand_bitreverse): Likwise, Use aop_optab instead of ior_optab
> when composing swapped bits and nibbles (allows use of shift_add).
> * optabs.def (aop_optab): New named optab for any_or_plus.
> * rtl.def (AOP): New RTX code to capture any_or_plus semantics.
> * simplify-rtx.cc (simplify_unary_operation_1) <case BSWAP>:
> Canonicalize (BSWAP (BITREVERSE x)) as (BITREVERSE (BSWAP x)).
>
> gcc/testsuite/ChangeLog
> * gcc.target/i386/builtin-bitreverse-1.c: New test case.
>
> Thanks again.
> Roger
> --
>
>> -----Original Message-----
>> From: Jeffrey Law <[email protected]>
>> Sent: 10 August 2026 00:19
>> To: Roger Sayle <[email protected]>; 'Patches GCC' <gcc-
>> [email protected]>
>> Subject: Re: [middle-end PATCH] Improve bitreverse expansion on x86_64 and
>> cris.
>>
>> On 8/8/2026 9:24 AM, Roger Sayle wrote:
>>> My recent patch to improve bitreverse support on cris, posted at
>>> https://gcc.gnu.org/pipermail/gcc-patches/2026-August/726384.html
>>> revealed an optimization opportunity. If you look closely GCC's
>>> expansion of bitreverse (in optabs.cc) generates a left shift followed
>>> by an IOR in several places. In these instances, its possible to use
>>> "any_or_plus", and in fact using PLUS would allow cris to use its addi
>>> instruction, and the x86 to use its lea instruction. I believe PLUS
>>> is always as efficient as IOR for SImode/wordmode, even on processors
>>> that have to use add with carry, i.e. addc[qh]i3. For other (longer)
>>> modes (such as vector modes), it's better to use IOR, and for shorter
>>> modes I'm not sure there's any advantage to using PLUS. If I'm wrong
>>> for some targets, we can make aop_optab a real optab.
>>>
>>>
>>> Previously on x86_64, with -O2 the following function:
>>>
>>> unsigned int foo(unsigned int x)
>>> {
>>> return __builtin_bitreverse32 (x);
>>> }
>>>
>>> used to generate:
>>>
>>> foo: movl %edi, %eax
>>> bswap %eax
>>> movl %eax, %edi
>>> andl $252645135, %eax
>>> shrl $4, %edi
>>> sall $4, %eax
>>> andl $252645135, %edi
>>> orl %eax, %edi
>>> movl %edi, %edx
>>> andl $858993459, %edi
>>> shrl $2, %edx
>>> sall $2, %edi
>>> andl $858993459, %edx
>>> orl %edi, %edx
>>> movl %edx, %eax
>>> andl $1431655765, %edx
>>> shrl $1, %eax
>>> addl %edx, %edx
>>> andl $1431655765, %eax
>>> orl %edx, %eax
>>> ret
>>>
>>> with this patch we instead generate:
>>>
>>> foo: bswap %edi
>>> movl %edi, %eax
>>> andl $252645135, %edi
>>> shrl $4, %eax
>>> sall $4, %edi
>>> andl $252645135, %eax
>>> addl %edi, %eax
>>> movl %eax, %edx
>>> andl $858993459, %eax
>>> shrl $2, %edx
>>> andl $858993459, %edx
>>> leal (%rdx,%rax,4), %eax
>>> movl %eax, %edx
>>> andl $1431655765, %eax
>>> shrl $1, %edx
>>> andl $1431655765, %edx
>>> leal (%rdx,%rax,2), %eax
>>> ret
>>>
>>> which is three instructions shorter. This patch also contains another
>>> transformation (to help bitreverse on cris) which is for simplify-rtx
>>> and combine to canonicalize bswap(bitreverse x) as bitreverse(bswap x).
>>> The two forms are equivalent, so canonicalizing simplifies machine
>>> descriptions. The (otherwise arbitrary) choice to perform BSWAP
>>> first, is (1) to aid targets like powerpc that can perform bswap on
>>> load and
>>> (2) to place bswap next to bswap on targets that RTL split bitreverse
>>> in a similar order to GCC's default optab expansion above.
>>>
>>> This patch has been tested on x86_64-pc-linux-gnu with make bootstrap
>>> and make -k check, both with and without --target_board=unix{-m32}
>>> with no new failures. Ok for mainline?
>>>
>>>
>>> 2026-08-08 Roger Sayle <[email protected]>
>>>
>>> gcc/ChangeLog
>>> * optab.cc (expand_bitreverse): Use PLUS instead of IOR when
>>> composing swapped bits and nibbles (allows use of shift_add).
>>> * simplify-rtx.cc (simplify_unary_operation_1) <case BSWAP>:
>>> Canonicalize (BSWAP (BITREVERSE x)) as (BITREVERSE (BSWAP x)).
>>>
>>> gcc/testsuite/ChangeLog
>>> * gcc.target/i386/builtin-bitreverse-1.c: New test case.
>>>
>>
>> So the only concern I have is the special casing of SImode in the optabs.cc
>> change. I wonder if we could query if we have addsi?
>>
>> FWIW, it saves an instruction on RISC-V as well as the new sequence exposes a
>> sh2add instead of slliw+or. Which means this likely helps other targets with
>> shNadd insns.
>>
>> jeff