[middle-end PATCH v2] Improve bitreverse expansion on x86_64 and cris.
"Roger Sayle" <[email protected]>
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
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
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
patchop2.txt
(text/plain, 5.5 KB)
diff --git a/gcc/config/avr/avr.md b/gcc/config/avr/avr.md
index 7fa07622c91d..23007d02cf82 100644
--- a/gcc/config/avr/avr.md
+++ b/gcc/config/avr/avr.md
@@ -4541,6 +4541,17 @@
[(set_attr "length" "4,8,8,8")
(set_attr "adjust_len" "*,out_bitop,out_bitop,out_bitop")])
+;; aop (any_or_plus) a.k.a. pixop. Always use IOR.
+(define_expand "aop<mode>3"
+ [(set (match_operand:QISI 0 "register_operand")
+ (ior:QISI (match_operand:QISI 1 "register_operand")
+ (match_operand:QISI 2 "nonmemory_operand")))]
+ ""
+ {
+ emit_insn (gen_ior<mode>3 (operands[0], operands[1], operands[2]));
+ DONE;
+ }
+)
(define_split
[(set (match_operand:SPLIT34 0 "register_operand")
diff --git a/gcc/expmed.cc b/gcc/expmed.cc
index b87d06bc9a4..1e3a338c129 100644
--- a/gcc/expmed.cc
+++ b/gcc/expmed.cc
@@ -1365,7 +1365,7 @@ store_fixed_bit_field_1 (rtx op0, scalar_int_mode mode,
if (! all_zero)
{
- temp = expand_binop (mode, ior_optab, temp, value,
+ temp = expand_binop (mode, aop_optab, temp, value,
NULL_RTX, 1, OPTAB_LIB_WIDEN);
temp = force_reg (mode, temp);
}
diff --git a/gcc/optabs.cc b/gcc/optabs.cc
index 012c0e9736e..fb9ecef8bcc 100644
--- a/gcc/optabs.cc
+++ b/gcc/optabs.cc
@@ -1632,6 +1632,16 @@ expand_binop (machine_mode mode, optab binoptab, rtx op0, rtx op1,
}
}
+ /* If backend's machine description doesn't specify an any_or_plus
+ (AOP) preference, choose for it. */
+ if (binoptab == aop_optab)
+ {
+ binoptab = (mode == word_mode || mode == SImode) ? add_optab
+ : ior_optab;
+ return expand_binop (mode, binoptab, op0, op1,
+ target, unsignedp, methods);
+ }
+
/* If this is a vector shift by a scalar, see if we can do a vector
shift by a vector. If so, broadcast the scalar into a vector. */
if (mclass == MODE_VECTOR_INT)
@@ -1975,7 +1985,7 @@ expand_binop (machine_mode mode, optab binoptab, rtx op0, rtx op1,
NULL_RTX, unsignedp, next_methods);
if (into_temp1 != 0 && into_temp2 != 0)
- inter = expand_binop (word_mode, add_optab, into_temp1, into_temp2,
+ inter = expand_binop (word_mode, aop_optab, into_temp1, into_temp2,
into_target, unsignedp, next_methods);
else
inter = 0;
@@ -1991,7 +2001,7 @@ expand_binop (machine_mode mode, optab binoptab, rtx op0, rtx op1,
NULL_RTX, unsignedp, next_methods);
if (inter != 0 && outof_temp1 != 0 && outof_temp2 != 0)
- inter = expand_binop (word_mode, add_optab,
+ inter = expand_binop (word_mode, aop_optab,
outof_temp1, outof_temp2,
outof_target, unsignedp, next_methods);
@@ -3029,7 +3039,7 @@ expand_bitreverse (scalar_int_mode mode, rtx op0, rtx target)
NULL_RTX, true, OPTAB_LIB_WIDEN);
if (lo == NULL_RTX) goto fail;
- x = expand_binop (mode, ior_optab, hi, lo,
+ x = expand_binop (mode, aop_optab, hi, lo,
NULL_RTX, true, OPTAB_LIB_WIDEN);
if (x == NULL_RTX) goto fail;
}
@@ -3056,7 +3066,7 @@ expand_bitreverse (scalar_int_mode mode, rtx op0, rtx target)
NULL_RTX, true, OPTAB_LIB_WIDEN);
if (lo == NULL_RTX) goto fail;
- x = expand_binop (mode, ior_optab, hi, lo,
+ x = expand_binop (mode, aop_optab, hi, lo,
NULL_RTX, true, OPTAB_LIB_WIDEN);
if (x == NULL_RTX) goto fail;
}
@@ -3084,7 +3094,7 @@ expand_bitreverse (scalar_int_mode mode, rtx op0, rtx target)
NULL_RTX, true, OPTAB_LIB_WIDEN);
if (lo == NULL_RTX) goto fail;
- x = expand_binop (mode, ior_optab, hi, lo,
+ x = expand_binop (mode, aop_optab, hi, lo,
target, true, OPTAB_LIB_WIDEN);
if (x == NULL_RTX) goto fail;
}
diff --git a/gcc/optabs.def b/gcc/optabs.def
index 7ccea18543f..72341dc3777 100644
--- a/gcc/optabs.def
+++ b/gcc/optabs.def
@@ -573,3 +573,4 @@ OPTAB_D (mask_len_strided_load_optab, "mask_len_strided_load_$a")
OPTAB_D (mask_len_strided_store_optab, "mask_len_strided_store_$a")
OPTAB_D (andn_optab, "andn$a3")
OPTAB_D (iorn_optab, "iorn$a3")
+OPTAB_DC (aop_optab, "aop$a3", AOP)
diff --git a/gcc/rtl.def b/gcc/rtl.def
index ae757929de2..cec11d83207 100644
--- a/gcc/rtl.def
+++ b/gcc/rtl.def
@@ -490,6 +490,7 @@ DEF_RTL_EXPR(UMOD, "umod", "ee", RTX_BIN_ARITH)
DEF_RTL_EXPR(AND, "and", "ee", RTX_COMM_ARITH)
DEF_RTL_EXPR(IOR, "ior", "ee", RTX_COMM_ARITH)
DEF_RTL_EXPR(XOR, "xor", "ee", RTX_COMM_ARITH)
+DEF_RTL_EXPR(AOP, "aop", "ee", RTX_COMM_ARITH)
DEF_RTL_EXPR(NOT, "not", "e", RTX_UNARY)
/* Operand:
diff --git a/gcc/simplify-rtx.cc b/gcc/simplify-rtx.cc
index 6f8ee53f209..ec67165101e 100644
--- a/gcc/simplify-rtx.cc
+++ b/gcc/simplify-rtx.cc
@@ -1505,6 +1505,12 @@ simplify_context::simplify_unary_operation_1 (rtx_code code, machine_mode mode,
/* (bswap (bswap x)) -> x. */
if (GET_CODE (op) == BSWAP)
return XEXP (op, 0);
+ /* Canonicalize (bswap (bitreverse x)) as (bitreverse (bswap x)). */
+ if (GET_CODE (op) == BITREVERSE)
+ return simplify_gen_unary (BITREVERSE, mode,
+ simplify_gen_unary (BSWAP, mode,
+ XEXP (op, 0), mode),
+ mode);
break;
case BITREVERSE:
diff --git a/gcc/testsuite/gcc.target/i386/builtin-bitreverse-1.c b/gcc/testsuite/gcc.target/i386/builtin-bitreverse-1.c
new file mode 100644
index 00000000000..797f9018cd6
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/builtin-bitreverse-1.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -mno-gfni" } */
+
+unsigned int foo(unsigned int x)
+{
+ return __builtin_bitreverse32 (x);
+}
+
+/* { dg-final { scan-assembler-times "leal" 2 } } */
+/* { dg-final { scan-assembler-not "orl" } } */