[PATCH] 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.  The inclusive or and the
conjunction already force an integral type.

  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.
Require the consumed padding value to become dead so that the fold cannot add work.

Bootstrapped and tested on aarch64-none-linux-gnu.
Ok for trunk?
Thanks,
Kyrill

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.

Signed-off-by: Kyrylo Tkachov <[email protected]>
---
 gcc/match.pd                                  | 21 ++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/alignup-2.c     | 28 +++++++++++++++++++
 .../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.dg/tree-ssa/vector-alignup-1.c        | 15 ++++++++++
 6 files changed, 110 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/vector-alignup-1.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 2d172b5f5a0..800864ce9e2 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2088,6 +2088,27 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
        && !TYPE_OVERFLOW_SANITIZED (type) && !TYPE_OVERFLOW_TRAPS (type))
    (maxmin @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:c@2 @0 (negate @0)))
+ (if (single_use (@2))
+  (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:c@2 (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 (single_use (@2)
+       && !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..eb9212e728c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/alignup-2.c
@@ -0,0 +1,28 @@
+/* { dg-do compile } */
+/* { 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/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)