From: Kyrylo Tkachov <[email protected]>
Linux spells a power-of-two round up as:
((x - 1) | (2^k - 1)) + 1
For wrapping arithmetic, this is:
(x + (2^k - 1)) & -(2^k)
The latter form needs one fewer operation and exposes the zero low bits.
Apply the identity to scalar and vector integral types. Use :s on the
inclusive-or expression so the fold does not add work when that value
remains live.
unsigned long round_up (unsigned long x)
{
return ((x - 1) | 4095) + 1;
}
aarch64 -O2:
before:
round_up:
sub x0, x0, #1
orr x0, x0, 4095
add x0, x0, 1
ret
after:
round_up:
add x0, x0, 4095
and x0, x0, -4096
ret
Bootstrapped and tested on aarch64-none-linux-gnu.
Ok for trunk?
Thanks,
Kyrill
gcc/ChangeLog:
* match.pd (((X - 1) | C) + 1): New simplification.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/round-up-ior-1.c: New test.
* gcc.dg/tree-ssa/round-up-ior-2.c: Likewise.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
gcc/match.pd | 17 ++++++++++
.../gcc.dg/tree-ssa/round-up-ior-1.c | 34 +++++++++++++++++++
.../gcc.dg/tree-ssa/round-up-ior-2.c | 10 ++++++
3 files changed, 61 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-2.c
diff --git a/gcc/match.pd b/gcc/match.pd
index 0ba97b32cb1..40dcd886478 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2062,6 +2062,23 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(bit_and (plus @0 @1)
{ build_uniform_cst
(type, wide_int_to_tree (etype, wi::bit_not (c))); }))))
+
+/* ((X - 1) | C) + 1 -> (X + C) & ~C, for C a low mask 2^k - 1.
+ Both forms round X up to a multiple of 2^k. */
+(simplify
+ (plus (bit_ior:s (plus @0 integer_minus_onep)
+ uniform_integer_cst_p@1)
+ integer_onep)
+ (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_WRAPS (type)
+ && c != 0
+ && 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) - min (x, y) -> max (x, y)
(x + y) - max (x, y) -> min (x, y)
The sum of the minimum and the maximum is the sum of the operands. */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-1.c
new file mode 100644
index 00000000000..991a429742c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-1.c
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+typedef unsigned int v4ui __attribute__ ((vector_size (16)));
+
+unsigned long
+round_up (unsigned long x)
+{
+ return ((x - 1) | 4095) + 1;
+}
+
+unsigned long
+round_up_pages (unsigned long x)
+{
+ return (((x - 1) | 4095) + 1) >> 12;
+}
+
+v4ui
+round_up_vec (v4ui x)
+{
+ v4ui one = { 1, 1, 1, 1 };
+ v4ui mask = { 15, 15, 15, 15 };
+ return ((x - one) | mask) + one;
+}
+
+unsigned long
+keep (unsigned long x)
+{
+ return ((x - 1) | 4096) + 1;
+}
+
+/* { dg-final { scan-tree-dump-not "\\| 4095" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "\\|.*15" "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\| 4096" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-2.c
new file mode 100644
index 00000000000..014aeed4c61
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/round-up-ior-2.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fwrapv -fdump-tree-optimized" } */
+
+int
+round_up (int x)
+{
+ return ((x - 1) | 15) + 1;
+}
+
+/* { dg-final { scan-tree-dump-not " \\| " "optimized" } } */
--
2.50.1 (Apple Git-155)
