[middle-end PATCH] Improve bitreverse expansion on x86_64 and cris.

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.


Thanks in advance,
Roger
--

diff --git a/gcc/optabs.cc b/gcc/optabs.cc
index 012c0e9736e..2d1bb979b09 100644
--- a/gcc/optabs.cc
+++ b/gcc/optabs.cc
@@ -2995,6 +2995,10 @@ expand_bitreverse (scalar_int_mode mode, rtx op0, rtx target)
 
   rtx x, lo, hi;
 
+  /* aop_optab is the preferred any_or_plus for mode MODE.  */
+  optab aop_optab = (mode == word_mode || mode == SImode)
+		    ? add_optab : ior_optab;
+
   /* Step 1: byte-swap (only meaningful for >= 16 bits).  */
   if (precision >= 16)
     {
@@ -3029,7 +3033,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 +3060,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 +3088,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/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" } } */