[PATCH] match.pd: Add new bitwise arithmetic pattern [PR98304]

[PATCH] match.pd: Add new bitwise arithmetic pattern [PR98304]

[Sam Feifer]

Hi!

This patch is meant to solve a missed optimization in match.pd. It optimizes the following expression: n - (((n > 63) ? n : 63) & -64) where the constant being negated (in this case -64) is a power of 2 and the sum of the two constants is -1. For the signed case, this gets optimized to (n <= 63) ? n : (n & 63). For the unsigned case, it gets optimized to (n & 63). In both scenarios, the number of instructions produced decreases.

There are also tests for this optimization making sure the optimization happens when it is supposed to, and does not happen when it isn't.

Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk?

	PR tree-optimization/98304

gcc/ChangeLog:

	* match.pd (n - (((n > C1) ? n : C1) & -C2)): New simplification.

gcc/testsuite/ChangeLog:

	* gcc.c-torture/execute/pr98304-2.c: New test.
	* gcc.dg/pr98304-1.c: New test.
---
 gcc/match.pd                                  | 12 ++++
 .../gcc.c-torture/execute/pr98304-2.c         | 37 ++++++++++++
 gcc/testsuite/gcc.dg/pr98304-1.c              | 57 +++++++++++++++++++
 3 files changed, 106 insertions(+)
 create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr98304-2.c
 create mode 100644 gcc/testsuite/gcc.dg/pr98304-1.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 88c6c414881..45aefd96688 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -7836,3 +7836,15 @@ and,
 (match (bitwise_induction_p @0 @2 @3)
  (bit_not
   (nop_convert1? (bit_xor@0 (convert2? (lshift integer_onep@1 @2)) @3))))
+
+/* n - (((n > C1) ? n : C1) & -C2) ->  n & C1 for unsigned case.
+   n - (((n > C1) ? n : C1) & -C2) ->  (n <= C1) ? n : (n & C1) for signed case.  */
+(simplify
+  (minus @0 (bit_and (max @0 INTEGER_CST@1) INTEGER_CST@2))
+  (with { auto i = wi::neg (wi::to_wide (@2)); }
+  /* Check if -C2 is a power of 2 and C1 = -C2 - 1.  */
+    (if (wi::popcount (i) == 1
+         && (wi::to_wide (@1)) == (i - 1))
+      (if (TYPE_UNSIGNED (TREE_TYPE (@0)))
+        (bit_and @0 @1)
+      (cond (le @0 @1) @0 (bit_and @0 @1))))))
diff --git a/gcc/testsuite/gcc.c-torture/execute/pr98304-2.c b/gcc/testsuite/gcc.c-torture/execute/pr98304-2.c
new file mode 100644
index 00000000000..114c612db3b
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr98304-2.c
@@ -0,0 +1,37 @@
+/* PR tree-optimization/98304 */
+
+#include "../../gcc.dg/pr98304-1.c"
+
+/* Runtime tests.  */
+int main() {
+
+    /* Signed tests.  */
+    if (foo(-42) != -42
+        || foo(0) != 0
+        || foo(63) != 63
+        || foo(64) != 0
+        || foo(65) != 1
+        || foo(99) != 35) {
+            __builtin_abort();
+        }
+    
+    /* Unsigned tests.  */
+    if (bar(42) != 42
+        || bar(0) != 0
+        || bar(63) != 63
+        || bar(64) != 0
+        || bar(65) != 1
+        || bar(99) != 35) {
+            __builtin_abort();
+        }
+
+    /* Should not simplify.  */
+    if (corge(13) != 13
+        || thud(13) != 13
+        || qux(13) != 13
+        || quux(13) != 13) {
+            __builtin_abort();
+        }
+
+    return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/pr98304-1.c b/gcc/testsuite/gcc.dg/pr98304-1.c
new file mode 100644
index 00000000000..dce54ddffe8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr98304-1.c
@@ -0,0 +1,57 @@
+/* PR tree-optimization/98304 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Signed test function.  */
+__attribute__((noipa)) int foo(int n) {
+    return n - (((n > 63) ? n : 63) & -64);
+}
+
+/* Unsigned test function.  */
+__attribute__((noipa)) unsigned int bar(unsigned int n) {
+    return n - (((n > 63) ? n : 63) & -64);
+}
+
+/* Different power of 2.  */
+__attribute__((noipa)) int goo(int n) {
+    return n - (((n > 31) ? n : 31) & -32);
+}
+
+/* Commutative property (should be identical to foo)  */
+__attribute__((noipa)) int baz(int n) {
+    return n - (((64 > n) ? 63 : n) & -64);
+}
+
+/* < instead of >.  */
+__attribute__((noipa)) int fred(int n) {
+    return n - (((63 < n) ? n : 63) & -64);
+}
+
+/* Constant is not a power of 2 so should not simplify.  */
+__attribute__((noipa)) int qux(int n) {
+    return n - (((n > 62) ? n : 62) & -63);
+}
+
+/* Constant is not a power of 2 so should not simplify.  */
+__attribute__((noipa)) unsigned int quux(unsigned int n) {
+    return n - (((n > 62) ? n : 62) & -63);
+}
+
+/* Constant is a variable so should not simplify.  */
+__attribute__((noipa)) int waldo(int n, int x) {
+    return n - (((n > 63) ? n : 63) & x);
+}
+
+/* Difference between constants is not -1.  */
+__attribute__((noipa)) int corge(int n) {
+    return n - (((n > 1) ? n : 1) & -64);
+}
+
+/* Difference between constants is not -1.  */
+__attribute__((noipa)) unsigned int thud(unsigned int n)
+{
+    return n - (((n > 1) ? n : 1) & -64);
+}
+
+/* { dg-final { scan-tree-dump-times " - " 5 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " <= " 4 "optimized" } } */

base-commit: a8b5d63503b8cf49de32d241218057409f8731ac
-- 
2.31.1

Re: [PATCH] match.pd: Add new bitwise arithmetic pattern [PR98304]

[Jeff Law]

On 7/7/2022 7:59 AM, Sam Feifer via Gcc-patches wrote:
> Hi!
>
> This patch is meant to solve a missed optimization in match.pd. It optimizes the following expression: n - (((n > 63) ? n : 63) & -64) where the constant being negated (in this case -64) is a power of 2 and the sum of the two constants is -1. For the signed case, this gets optimized to (n <= 63) ? n : (n & 63). For the unsigned case, it gets optimized to (n & 63). In both scenarios, the number of instructions produced decreases.
>
> There are also tests for this optimization making sure the optimization happens when it is supposed to, and does not happen when it isn't.
>
> Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk?
>
> 	PR tree-optimization/98304
>
> gcc/ChangeLog:
>
> 	* match.pd (n - (((n > C1) ? n : C1) & -C2)): New simplification.
>
> gcc/testsuite/ChangeLog:
>
> 	* gcc.c-torture/execute/pr98304-2.c: New test.
> 	* gcc.dg/pr98304-1.c: New test.
OK.   I'm going to assume Red Hat's assignment covers you and/or you 
want to contribute under the DCO.    Going forward, if you're part of 
the tools team for Red Hat and expect to be contributing regularly, 
you'll probably want to get authenticated write access so that you can 
commit  approved changes (anyone on the team should be able to help with 
that).

I'll go ahead and push this one to the trunk.

Thanks,
Jeff