expand: Add new clrsb fallback expansion [PR101950]

As suggested in the PR, the following patch adds two new clrsb
expansion possibilities if target doesn't have clrsb_optab for the
requested nor wider modes, but does have clz_optab for the requested
mode.
One expansion is
clrsb (op0)
expands as
clz (op0 ^ (((stype)op0) >> (prec-1))) - 1
which is usable if CLZ_DEFINED_VALUE_AT_ZERO is 2 with value
of prec, because the clz argument can be 0 and clrsb should give
prec-1 in that case.
The other expansion is
clz (((op0 << 1) ^ (((stype)op0) >> (prec-1))) | 1)
where the clz argument is never 0, but it is one operation longer.
E.g. on x86_64-linux with -O2 -mno-lzcnt, this results for
int foo (int x) { return __builtin_clrsb (x); }
in
-       subq    $8, %rsp
-       movslq  %edi, %rdi
-       call    __clrsbdi2
-       addq    $8, %rsp
-       subl    $32, %eax
+       leal    (%rdi,%rdi), %eax
+       sarl    $31, %edi
+       xorl    %edi, %eax
+       orl     $1, %eax
+       bsrl    %eax, %eax
+       xorl    $31, %eax
and with -O2 -mlzcnt:
+       movl    %edi, %eax
+       sarl    $31, %eax
+       xorl    %edi, %eax
+       lzcntl  %eax, %eax
+       subl    $1, %eax
On armv7hl-linux-gnueabi with -O2:
-       push    {r4, lr}
-       bl      __clrsbsi2
-       pop     {r4, pc}
+       @ link register save eliminated.
+       eor     r0, r0, r0, asr #31
+       clz     r0, r0
+       sub     r0, r0, #1
+       bx      lr
As it (at least usually) will make code larger, it is
disabled for -Os or cold instructions.

2021-08-19  Jakub Jelinek  <jakub@redhat.com>

	PR middle-end/101950
	* optabs.c (expand_clrsb_using_clz): New function.
	(expand_unop): Use it as another clrsb expansion fallback.

	* gcc.target/i386/pr101950-1.c: New test.
	* gcc.target/i386/pr101950-2.c: New test.

3 files changed, 118 insertions, 0 deletions

diff --git a/gcc/optabs.c b/gcc/optabs.c
index 14d8ad2..ebed78f 100644
--- a/gcc/optabs.c
+++ b/gcc/optabs.c
@@ -2600,6 +2600,82 @@ widen_leading (scalar_int_mode mode, rtx op0, rtx target, optab unoptab)
   return 0;
 }
 
+/* Attempt to emit (clrsb:mode op0) as
+   (plus:mode (clz:mode (xor:mode op0 (ashr:mode op0 (const_int prec-1))))
+	      (const_int -1))
+   if CLZ_DEFINED_VALUE_AT_ZERO (mode, val) is 2 and val is prec,
+   or as
+   (clz:mode (ior:mode (xor:mode (ashl:mode op0 (const_int 1))
+				 (ashr:mode op0 (const_int prec-1)))
+		       (const_int 1)))
+   otherwise.  */
+
+static rtx
+expand_clrsb_using_clz (scalar_int_mode mode, rtx op0, rtx target)
+{
+  if (optimize_insn_for_size_p ()
+      || optab_handler (clz_optab, mode) == CODE_FOR_nothing)
+    return NULL_RTX;
+
+  start_sequence ();
+  HOST_WIDE_INT val = 0;
+  if (CLZ_DEFINED_VALUE_AT_ZERO (mode, val) != 2
+      || val != GET_MODE_PRECISION (mode))
+    val = 0;
+  else
+    val = 1;
+
+  rtx temp2 = op0;
+  if (!val)
+    {
+      temp2 = expand_binop (mode, ashl_optab, op0, const1_rtx,
+			    NULL_RTX, 0, OPTAB_DIRECT);
+      if (!temp2)
+	{
+	fail:
+	  end_sequence ();
+	  return NULL_RTX;
+	}
+    }
+
+  rtx temp = expand_binop (mode, ashr_optab, op0,
+			   GEN_INT (GET_MODE_PRECISION (mode) - 1),
+			   NULL_RTX, 0, OPTAB_DIRECT);
+  if (!temp)
+    goto fail;
+
+  temp = expand_binop (mode, xor_optab, temp2, temp, NULL_RTX, 0,
+		       OPTAB_DIRECT);
+  if (!temp)
+    goto fail;
+
+  if (!val)
+    {
+      temp = expand_binop (mode, ior_optab, temp, const1_rtx,
+			   NULL_RTX, 0, OPTAB_DIRECT);
+      if (!temp)
+	goto fail;
+    }
+  temp = expand_unop_direct (mode, clz_optab, temp, val ? NULL_RTX : target,
+			     true);
+  if (!temp)
+    goto fail;
+  if (val)
+    {
+      temp = expand_binop (mode, add_optab, temp, constm1_rtx,
+			   target, 0, OPTAB_DIRECT);
+      if (!temp)
+	goto fail;
+    }
+
+  rtx_insn *seq = get_insns ();
+  end_sequence ();
+
+  add_equal_note (seq, temp, CLRSB, op0, NULL_RTX, mode);
+  emit_insn (seq);
+  return temp;
+}
+
 /* Try calculating clz of a double-word quantity as two clz's of word-sized
    quantities, choosing which based on whether the high word is nonzero.  */
 static rtx
@@ -3171,6 +3247,9 @@ expand_unop (machine_mode mode, optab unoptab, rtx op0, rtx target,
 	  temp = widen_leading (int_mode, op0, target, unoptab);
 	  if (temp)
 	    return temp;
+	  temp = expand_clrsb_using_clz (int_mode, op0, target);
+	  if (temp)
+	    return temp;
 	}
       goto try_libcall;
     }
diff --git a/gcc/testsuite/gcc.target/i386/pr101950-1.c b/gcc/testsuite/gcc.target/i386/pr101950-1.c
new file mode 100644
index 0000000..cc98064
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr101950-1.c
@@ -0,0 +1,20 @@
+/* PR middle-end/101950 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -mno-lzcnt" } */
+/* { dg-final { scan-assembler-not "call\[^\n\r]*__clrsb.i2" } } */
+/* { dg-final { scan-assembler-times "\tbsr\[ql]\t" 2 } } */
+/* { dg-final { scan-assembler-times "\txor\[ql]\t" 4 } } */
+/* { dg-final { scan-assembler-times "\tor\[ql]\t" 2 } } */
+/* { dg-final { scan-assembler-times "\tsar\[ql]\t|\tcltd" 2 } } */
+
+int
+foo (long x)
+{
+  return __builtin_clrsbl (x);
+}
+
+int
+bar (int x)
+{
+  return __builtin_clrsb (x);
+}
diff --git a/gcc/testsuite/gcc.target/i386/pr101950-2.c b/gcc/testsuite/gcc.target/i386/pr101950-2.c
new file mode 100644
index 0000000..896f1b4
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr101950-2.c
@@ -0,0 +1,19 @@
+/* PR middle-end/101950 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -mlzcnt" } */
+/* { dg-final { scan-assembler-not "call\[^\n\r]*__clrsb.i2" } } */
+/* { dg-final { scan-assembler-times "\tlzcnt\[ql]\t" 2 } } */
+/* { dg-final { scan-assembler-times "\txor\[ql]\t" 2 } } */
+/* { dg-final { scan-assembler-times "\tsar\[ql]\t|\tcltd" 2 } } */
+
+int
+foo (long x)
+{
+  return __builtin_clrsbl (x);
+}
+
+int
+bar (int x)
+{
+  return __builtin_clrsb (x);
+}