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

[Sam Feifer <sfeifer@redhat.com>]

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