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
