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)
