[PATCH take #2] PR middle-end/98865: Expand X*Y as X&-Y when Y is [0.1].

[PATCH take #2] PR middle-end/98865: Expand X*Y as X&-Y when Y is [0.1].

[Roger Sayle]

[-- Attachment #1: Type: text/plain, Size: 1851 bytes --]


The patch is a revised solution for PR middle-end/98865 incorporating
the feedback/suggestions from Richard Biener's review here:
https://gcc.gnu.org/pipermail/gcc-patches/2022-May/593928.html
Most significantly, this patch now performs the transformation/optimization
during RTL expansion, where the target's rtx_costs can be used to determine
whether the original multiplication (that may be possibly be implemented by
a shift or lea) is cheaper than a negation and a bit-wise and.

Previously the expression (x>>63)*y would be compiled with -O2 as
        shrq    $63, %rdi
        movq    %rdi, %rax
        imulq   %rsi, %rax

but with this patch now produces:
        sarq    $63, %rdi
        movq    %rdi, %rax
        andq    %rsi, %rax

Likewise the expression (x>>63)*135 [that appears in a hot-spot of the
Botan AES-128 benchmark] was previously:

        shrq    $63, %rdi
        leaq    (%rdi,%rdi,8), %rdx
        movq    %rdx, %rax
        salq    $4, %rax
        subq    %rdx, %rax

now becomes:
        movq    %rdi, %rax
        sarq    $63, %rax
        andl    $135, %eax


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.  Many thanks to Uros for the speedy review and approval of
my x86_rtx_costs patch that enables this transformation on -m32 using the
correct cost of DImode multiplication.  Ok for mainline?

2022-05-18  Roger Sayle  <roger@nextmovesoftware.com>

gcc/ChangeLog
	PR middle-end/98865
	* expr.cc (expand_expr_real_2) [MULT_EXPR]:  Expand X*Y as X&Y
	when both X and Y are [0, 1], X*Y as X&-Y when Y is [0,1] and
	likewise X*Y as -X&Y when X is [0,1] using tree_nonzero_bits.

gcc/testsuite/ChangeLog
	PR middle-end/98865
	* gcc.target/i386/pr98865.c: New test case.


Thanks in advance,
Roger
--


[-- Attachment #2: patchbmb.txt --]
[-- Type: text/plain, Size: 2614 bytes --]

diff --git a/gcc/expr.cc b/gcc/expr.cc
index 1806091..7197996 100644
--- a/gcc/expr.cc
+++ b/gcc/expr.cc
@@ -9541,6 +9541,38 @@ expand_expr_real_2 (sepops ops, rtx target, machine_mode tmode,
 	}
 
       expand_operands (treeop0, treeop1, subtarget, &op0, &op1, EXPAND_NORMAL);
+
+      /* Expand X*Y as X&-Y when Y must be zero or one.  */
+      if (SCALAR_INT_MODE_P (mode))
+	{
+	  bool bit0_p = tree_nonzero_bits (treeop0) == 1;
+	  bool bit1_p = tree_nonzero_bits (treeop1) == 1;
+
+	  /* Expand X*Y as X&Y when both X and Y must be zero or one.  */
+	  if (bit0_p && bit1_p)
+	    return REDUCE_BIT_FIELD (expand_and (mode, op0, op1, target));
+
+	  if (bit0_p || bit1_p)
+	    {
+	      bool speed = optimize_insn_for_speed_p ();
+	      int cost = add_cost (speed, mode) + neg_cost (speed, mode);
+	      struct algorithm algorithm;
+	      enum mult_variant variant;
+	      if (CONST_INT_P (op1)
+		  ? !choose_mult_variant (mode, INTVAL (op1),
+					  &algorithm, &variant, cost)
+		  : cost < mul_cost (speed, mode))
+		{
+		  target = bit0_p ? expand_and (mode, negate_rtx (mode, op0),
+						op1, target)
+				  : expand_and (mode, op0,
+						negate_rtx (mode, op1),
+						target);
+		  return REDUCE_BIT_FIELD (target);
+		}
+	    }
+	}
+
       return REDUCE_BIT_FIELD (expand_mult (mode, op0, op1, target, unsignedp));
 
     case TRUNC_MOD_EXPR:
diff --git a/gcc/testsuite/gcc.target/i386/pr98865.c b/gcc/testsuite/gcc.target/i386/pr98865.c
new file mode 100644
index 0000000..d047c4b
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr98865.c
@@ -0,0 +1,54 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+#if __SIZEOF_INT__ == 4
+unsigned int foo(unsigned int a, unsigned int b)
+{
+  return (a >> 31) * b;
+}
+
+int bar(int a, int b)
+{
+  return -(a >> 31) * b;
+}
+
+int baz(int a, int b)
+{
+  int c = a >> 31;
+  int d = -c;
+  return d * b;
+}
+
+unsigned int pin(int a, unsigned int b)
+{
+  unsigned int t = a & 1;
+  return t * b;
+}
+#endif
+
+#if __SIZEOF_LONG_LONG__ == 8
+unsigned long long fool(unsigned long long a, unsigned long long b)
+{
+  return (a >> 63) * b;
+}
+
+long long barl (long long a, long long b)
+{
+  return -(a >> 63) * b;
+}
+
+long long bazl (long long a, long long b)
+{
+  long long c = a >> 63;
+  long long d = -c;
+  return d * b;
+}
+
+unsigned long long pinl(long long a, unsigned long long b)
+{
+  unsigned long long t = a & 1;
+  return t * b;
+}
+#endif
+
+/* { dg-final { scan-assembler-not "imul" } } */

Re: [PATCH take #2] PR middle-end/98865: Expand X*Y as X&-Y when Y is [0.1].

[Richard Biener]

On Wed, May 18, 2022 at 6:55 PM Roger Sayle <roger@nextmovesoftware.com> wrote:
>
>
> The patch is a revised solution for PR middle-end/98865 incorporating
> the feedback/suggestions from Richard Biener's review here:
> https://gcc.gnu.org/pipermail/gcc-patches/2022-May/593928.html
> Most significantly, this patch now performs the transformation/optimization
> during RTL expansion, where the target's rtx_costs can be used to determine
> whether the original multiplication (that may be possibly be implemented by
> a shift or lea) is cheaper than a negation and a bit-wise and.
>
> Previously the expression (x>>63)*y would be compiled with -O2 as
>         shrq    $63, %rdi
>         movq    %rdi, %rax
>         imulq   %rsi, %rax
>
> but with this patch now produces:
>         sarq    $63, %rdi
>         movq    %rdi, %rax
>         andq    %rsi, %rax
>
> Likewise the expression (x>>63)*135 [that appears in a hot-spot of the
> Botan AES-128 benchmark] was previously:
>
>         shrq    $63, %rdi
>         leaq    (%rdi,%rdi,8), %rdx
>         movq    %rdx, %rax
>         salq    $4, %rax
>         subq    %rdx, %rax
>
> now becomes:
>         movq    %rdi, %rax
>         sarq    $63, %rax
>         andl    $135, %eax
>
>
> 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.  Many thanks to Uros for the speedy review and approval of
> my x86_rtx_costs patch that enables this transformation on -m32 using the
> correct cost of DImode multiplication.  Ok for mainline?

Looks good to me

Thanks,
Richard.

> 2022-05-18  Roger Sayle  <roger@nextmovesoftware.com>
>
> gcc/ChangeLog
>         PR middle-end/98865
>         * expr.cc (expand_expr_real_2) [MULT_EXPR]:  Expand X*Y as X&Y
>         when both X and Y are [0, 1], X*Y as X&-Y when Y is [0,1] and
>         likewise X*Y as -X&Y when X is [0,1] using tree_nonzero_bits.
>
> gcc/testsuite/ChangeLog
>         PR middle-end/98865
>         * gcc.target/i386/pr98865.c: New test case.
>
>
> Thanks in advance,
> Roger
> --
>