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