[PATCH][committed][v2] match: fold two idioms built from the negation of a value

From: Kyrylo Tkachov <[email protected]>

X | -X has every bit from the lowest set bit of X upwards, so adding X to
it clears that bit, and masking with it isolates the padding needed to
round X up:

  X + (X | -X) -> X & (X - 1)
  X + ((-X) & (C - 1)) -> (X + C - 1) & -C   for a power of two C

The second is the alignment round up written with the padding computed
first, which is how allocators tend to spell it.

Neither needs a wrapping type.  X - 1 overflows only for the most
negative value, where the source already does, and rounding X up is
representable exactly when X + C - 1 is, because the largest multiple of
C below the maximum leaves room for C - 1.  Restrict both rules to integral
types.  The bitwise operations also accept fixed-point types, whose
saturating arithmetic does not have these integer semantics.

  int f (int x) { return x + ((-x) & 15); }

aarch64 -O2:

  before                          after
    neg   w1, w0                    add   w0, w0, 15
    and   w1, w1, 15                and   w0, w0, -16
    add   w0, w1, w0

The vector spelling folds too, a uniform vector constant is matched with
uniform_integer_cst_p.

Keep trapping and sanitized negations.  Also keep the source addition
of X + (X | -X) under overflow sanitization because the replacement
would remove one recoverable diagnostic.  Use :s on the consumed bitwise
expression.  This prevents new work when it remains live, but allows the
fold when the replacement arithmetic is already available.

Reuse the matched uniform constant and test its wide value directly.
This avoids rebuilding the same constant only to inspect it.

Bootstrapped and tested on aarch64-none-linux-gnu.
Committed as per Richard's approval.

gcc/ChangeLog:

        * match.pd (X + (X | -X)): New simplification.
        (X + ((-X) & (C - 1))): Likewise.

gcc/testsuite/ChangeLog:

        * gcc.dg/tree-ssa/signbit-1.c: New test.
        * gcc.dg/tree-ssa/alignup-2.c: New test.
        * gcc.dg/tree-ssa/vector-alignup-1.c: New test.
        * gcc.dg/tree-ssa/alignup-overflow-1.c: New test.
        * gcc.dg/tree-ssa/alignup-overflow-2.c: New test.
        * gcc.dg/tree-ssa/signbit-4.c: New test.

Signed-off-by: Kyrylo Tkachov <[email protected]>
---
 gcc/match.pd                                  | 23 +++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/alignup-2.c     | 29 +++++++++++++++++++
 .../gcc.dg/tree-ssa/alignup-overflow-1.c      | 10 +++++++
 .../gcc.dg/tree-ssa/alignup-overflow-2.c      | 10 +++++++
 gcc/testsuite/gcc.dg/tree-ssa/signbit-1.c     | 26 +++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/signbit-4.c     | 11 +++++++
 .../gcc.dg/tree-ssa/vector-alignup-1.c        | 15 ++++++++++
 7 files changed, 124 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/alignup-2.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-2.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/signbit-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/signbit-4.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vector-alignup-1.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 0bf2414b3f0..df6a179a848 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1985,6 +1985,29 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
        && !TYPE_SATURATING (type))
    (res @0 @1))))
 
+/* X + (X | -X) -> X & (X - 1).  X | -X has every bit from the lowest set
+   bit of X upwards, so adding it clears that bit.  */
+(simplify
+ (plus:c @0 (bit_ior:cs @0 (negate @0)))
+ (if (ANY_INTEGRAL_TYPE_P (type)
+      && !TYPE_OVERFLOW_SANITIZED (type))
+  (bit_and @0 (plus @0 { build_minus_one_cst (type); }))))
+
+/* X + ((-X) & (C - 1)) -> (X + C - 1) & -C for a power of two C, the
+   round up to a multiple of C written with the padding computed first.  */
+(simplify
+ (plus:c @0 (bit_and:cs (negate @0) uniform_integer_cst_p@1))
+ (with { tree cst = uniform_integer_cst_p (@1);
+	 tree etype = TREE_TYPE (cst);
+	 wide_int c = wi::to_wide (cst); }
+  (if (ANY_INTEGRAL_TYPE_P (type)
+       && !TYPE_OVERFLOW_TRAPS (type)
+       && !TYPE_OVERFLOW_SANITIZED (type)
+       && wi::popcount (c + 1) == 1)
+   (bit_and (plus @0 @1)
+	    { build_uniform_cst
+		(type, wide_int_to_tree (etype, wi::bit_not (c))); }))))
+
 /* (x | y) - y -> (x & ~y) */
 (simplify
  (minus (bit_ior:cs @0 @1) @1)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alignup-2.c b/gcc/testsuite/gcc.dg/tree-ssa/alignup-2.c
new file mode 100644
index 00000000000..e71af6dcddf
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/alignup-2.c
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target int32plus } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Rounding up by adding the padding is the same as rounding up with a
+   mask.  */
+
+unsigned int f1 (unsigned int x) { return x + ((-x) & 15u); }
+unsigned int f2 (unsigned int x) { return ((-x) & 4095u) + x; }
+unsigned long f3 (unsigned long x) { return x + ((-x) & 63ul); }
+
+/* The identity needs no wrapping type, a signed operand works too.  */
+int f5 (int x) { return x + ((-x) & 15); }
+
+unsigned int f6 (unsigned int x, unsigned int *p)
+{
+  unsigned int pad = (-x) & 15u;
+  *p = pad;
+  return x + pad;
+}
+
+/* Not a power of two, leave it alone.  */
+unsigned int f4 (unsigned int x) { return x + ((-x) & 14u); }
+
+/* { dg-final { scan-tree-dump-times " & 14;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " & 4294967280" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " & 4294963200" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " & -16" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " & 15" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-1.c b/gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-1.c
new file mode 100644
index 00000000000..f4995d08cc0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-1.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftrapv -fdump-tree-optimized" } */
+
+int
+f (int x)
+{
+  return x + ((-x) & 15);
+}
+
+/* { dg-final { scan-tree-dump " -x" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-2.c b/gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-2.c
new file mode 100644
index 00000000000..75e29d60189
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/alignup-overflow-2.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fsanitize=signed-integer-overflow -fdump-tree-optimized" } */
+
+int
+f (int x)
+{
+  return x + ((-x) & 15);
+}
+
+/* { dg-final { scan-tree-dump "UBSAN_CHECK_SUB" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/signbit-1.c b/gcc/testsuite/gcc.dg/tree-ssa/signbit-1.c
new file mode 100644
index 00000000000..d7bcd91173b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/signbit-1.c
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* X | -X has the sign bit set exactly when X is non-zero.  */
+
+int f1 (int x)
+{ return (x | -x) >> (__SIZEOF_INT__ * __CHAR_BIT__ - 1); }
+unsigned int f2 (unsigned int x)
+{ return (x | -x) >> (__SIZEOF_INT__ * __CHAR_BIT__ - 1); }
+long f3 (long x) { return (x | -x) >> (__SIZEOF_LONG__ * __CHAR_BIT__ - 1); }
+
+/* X + (X | -X) clears the lowest set bit of X.  The identity holds for a
+   signed operand too, X - 1 overflows only where the source does.  */
+unsigned int f4 (unsigned int x) { return x + (x | -x); }
+int f5 (int x) { return x + (x | -x); }
+
+unsigned int f6 (unsigned int x, unsigned int *p)
+{
+  unsigned int y = x | -x;
+  *p = y;
+  return x + y;
+}
+
+/* { dg-final { scan-tree-dump-times " \\| " 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " != 0" 3 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " & " 2 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/signbit-4.c b/gcc/testsuite/gcc.dg/tree-ssa/signbit-4.c
new file mode 100644
index 00000000000..8ed81a169d3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/signbit-4.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fsanitize=signed-integer-overflow -fdump-tree-optimized" } */
+
+int
+f (int x)
+{
+  return x + (x | -x);
+}
+
+/* { dg-final { scan-tree-dump "\\.UBSAN_CHECK_SUB" "optimized" } } */
+/* { dg-final { scan-tree-dump "\\.UBSAN_CHECK_ADD" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vector-alignup-1.c b/gcc/testsuite/gcc.dg/tree-ssa/vector-alignup-1.c
new file mode 100644
index 00000000000..fec5c5c6b93
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vector-alignup-1.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Rounding up by adding the padding, spelled with vectors.  */
+
+typedef unsigned int v4ui __attribute__((vector_size (16)));
+typedef int v4si __attribute__((vector_size (16)));
+
+v4ui f1 (v4ui x) { return x + ((-x) & 15); }
+v4si f2 (v4si x) { return x + ((-x) & 63); }
+
+/* { dg-final { scan-tree-dump-not "= -" "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\+ " 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " & " 2 "optimized" } } */
-- 
2.50.1 (Apple Git-155)