[PATCH] PR90838: Support ctz idioms
Wilco Dijkstra
Wilco.Dijkstra@arm.com
Tue Nov 12 14:39:00 GMT 2019
Hi,
Support common idioms for count trailing zeroes using an array lookup.
The canonical form is array[((x & -x) * C) >> SHIFT] where C is a magic
constant which when multiplied by a power of 2 contains a unique value
in the top 5 or 6 bits. This is then indexed into a table which maps it
to the number of trailing zeroes. When the table is valid, we emit a
sequence using the target defined value for ctz (0):
int ctz1 (unsigned x)
{
static const char table[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
return table[((unsigned)((x & -x) * 0x077CB531U)) >> 27];
}
Is optimized to:
rbit w0, w0
clz w0, w0
and w0, w0, 31
ret
Bootstrapped on AArch64. OK for commit?
ChangeLog:
2019-11-12 Wilco Dijkstra <wdijkstr@arm.com>
PR tree-optimization/90838
* generic-match-head.c (optimize_count_trailing_zeroes):
Add stub function.
* gimple-match-head.c (gimple_simplify): Add support for ARRAY_REF.
(optimize_count_trailing_zeroes): Add new function.
* match.pd: Add matching for ctz idioms.
* testsuite/gcc.target/aarch64/pr90838.c: New test.
--
diff --git a/gcc/generic-match-head.c b/gcc/generic-match-head.c
index fdc603977fc5b03a843944f75ce262f5d2256308..5a38bd233585225d60f0159c9042a16d9fdc9d80 100644
--- a/gcc/generic-match-head.c
+++ b/gcc/generic-match-head.c
@@ -88,3 +88,10 @@ optimize_successive_divisions_p (tree, tree)
{
return false;
}
+
+static bool
+optimize_count_trailing_zeroes (tree type, tree array_ref, tree input,
+ tree mulc, tree shift, tree &zero_val)
+{
+ return false;
+}
diff --git a/gcc/gimple-match-head.c b/gcc/gimple-match-head.c
index 53278168a59f5ac10ce6760f04fd42589a0792e7..2d3b305f8ea54e4ca31c64994af30b34bb7eff09 100644
--- a/gcc/gimple-match-head.c
+++ b/gcc/gimple-match-head.c
@@ -909,6 +909,24 @@ gimple_simplify (gimple *stmt, gimple_match_op *res_op, gimple_seq *seq,
res_op->set_op (TREE_CODE (op0), type, valueized);
return true;
}
+ else if (code == ARRAY_REF)
+ {
+ tree rhs1 = gimple_assign_rhs1 (stmt);
+ tree op1 = TREE_OPERAND (rhs1, 1);
+ tree op2 = TREE_OPERAND (rhs1, 2);
+ tree op3 = TREE_OPERAND (rhs1, 3);
+ tree op0 = TREE_OPERAND (rhs1, 0);
+ bool valueized = false;
+
+ op0 = do_valueize (op0, top_valueize, valueized);
+ op1 = do_valueize (op1, top_valueize, valueized);
+
+ if (op2 && op3)
+ res_op->set_op (code, type, op0, op1, op2, op3);
+ else
+ res_op->set_op (code, type, op0, op1);
+ return gimple_resimplify4 (seq, res_op, valueize) || valueized;
+ }
break;
case GIMPLE_UNARY_RHS:
{
@@ -1222,3 +1240,57 @@ optimize_successive_divisions_p (tree divisor, tree inner_div)
}
return true;
}
+
+/* Recognize count trailing zeroes idiom.
+ The canonical form is array[((x & -x) * C) >> SHIFT] where C is a magic
+ constant which when multiplied by a power of 2 contains a unique value
+ in the top 5 or 6 bits. This is then indexed into a table which maps it
+ to the number of trailing zeroes. Array[0] is returned so the caller can
+ emit an appropriate sequence depending on whether ctz (0) is defined on
+ the target. */
+static bool
+optimize_count_trailing_zeroes (tree type, tree array, tree x, tree mulc,
+ tree tshift, tree &zero_val)
+{
+ gcc_assert (TREE_CODE (mulc) == INTEGER_CST);
+ gcc_assert (TREE_CODE (tshift) == INTEGER_CST);
+
+ tree input_type = TREE_TYPE (x);
+
+ if (!direct_internal_fn_supported_p (IFN_CTZ, input_type, OPTIMIZE_FOR_BOTH))
+ return false;
+
+ unsigned HOST_WIDE_INT val = tree_to_uhwi (mulc);
+ unsigned shiftval = tree_to_uhwi (tshift);
+ unsigned input_bits = tree_to_shwi (TYPE_SIZE (input_type));
+
+ /* Check the array is not wider than integer type and the input is a 32-bit
+ or 64-bit type. The shift should extract the top 5..7 bits. */
+ if (TYPE_PRECISION (type) > 32)
+ return false;
+ if (input_bits != 32 && input_bits != 64)
+ return false;
+ if (shiftval < input_bits - 7 || shiftval > input_bits - 5)
+ return false;
+
+ tree t = build4 (ARRAY_REF, type, array, size_int (0), NULL_TREE, NULL_TREE);
+ t = fold_const_aggregate_ref (t);
+ if (t == NULL)
+ return false;
+
+ zero_val = build_int_cst (integer_type_node, tree_to_shwi (t));
+
+ for (unsigned i = 0; i < input_bits; i++, val <<= 1)
+ {
+ if (input_bits == 32)
+ val &= 0xffffffff;
+ t = build4 (ARRAY_REF, type, array, size_int ((int)(val >> shiftval)),
+ NULL_TREE, NULL_TREE);
+ t = fold_const_aggregate_ref (t);
+ if (t == NULL || tree_to_shwi (t) != i)
+ return false;
+ }
+
+ return true;
+}
+
diff --git a/gcc/match.pd b/gcc/match.pd
index 6edf54b80012d87dbe7330f5ee638cdba2f9c099..bbe935e1e2af35e8e953a776eb3ecfb83414b047 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -6060,3 +6060,33 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(simplify
(vec_perm vec_same_elem_p@0 @0 @1)
@0)
+
+/* Recognize count trailing zeroes idiom.
+ The canonical form is array[((x & -x) * C) >> SHIFT] where C is a magic
+ constant which when multiplied by a power of 2 contains a unique value
+ in the top 5 or 6 bits. This is then indexed into a table which maps it
+ to the number of trailing zeroes. If valid, emit an optimal sequence
+ depending on the result for zero.
+*/
+(simplify
+ (ARRAY_REF @0 (rshift (mult (bit_and (negate @1) @1) INTEGER_CST@2)
+ INTEGER_CST@3) @4 @5)
+ (with
+ { tree zero_val;
+ HOST_WIDE_INT val;
+ HOST_WIDE_INT type_size = tree_to_shwi (TYPE_SIZE (TREE_TYPE (@1)));
+ bool zero_ok = CTZ_DEFINED_VALUE_AT_ZERO (TYPE_MODE (TREE_TYPE (@1)), val);
+ }
+ (if (optimize_count_trailing_zeroes (type, @0, @1, @2, @3, zero_val))
+ (switch
+ (if (zero_ok && tree_to_shwi (zero_val) == val)
+ (convert (BUILT_IN_CTZ:integer_type_node @1)))
+
+ /* Emit ctz (x) & 31 if ctz (0) is 32 but we need to return 0. */
+ (if (zero_ok && val == type_size && integer_zerop (zero_val))
+ (convert (bit_and (BUILT_IN_CTZ:integer_type_node @1)
+ { build_int_cst (integer_type_node, type_size - 1); })))
+
+ /* Emit (x ? ctz (x) : zero_val). */
+ (if (true)
+ (convert (cond @1 (BUILT_IN_CTZ:integer_type_node @1) { zero_val; } )))))))
diff --git a/gcc/testsuite/gcc.target/aarch64/pr90838.c b/gcc/testsuite/gcc.target/aarch64/pr90838.c
new file mode 100644
index 0000000000000000000000000000000000000000..bff3144c0d1b3984016e5a404e986eae785c73ed
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr90838.c
@@ -0,0 +1,64 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+int ctz1 (unsigned x)
+{
+ static const char table[32] =
+ {
+ 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
+ 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
+ };
+
+ return table[((unsigned)((x & -x) * 0x077CB531U)) >> 27];
+}
+
+int ctz2 (unsigned x)
+{
+ const int u = 0;
+ static short table[64] =
+ {
+ 32, 0, 1,12, 2, 6, u,13, 3, u, 7, u, u, u, u,14,
+ 10, 4, u, u, 8, u, u,25, u, u, u, u, u,21,27,15,
+ 31,11, 5, u, u, u, u, u, 9, u, u,24, u, u,20,26,
+ 30, u, u, u, u,23, u,19,29, u,22,18,28,17,16, u
+ };
+
+ x = (x & -x) * 0x0450FBAF;
+ return table[x >> 26];
+}
+
+int ctz3 (unsigned x)
+{
+ static int table[32] =
+ {
+ 0, 1, 2,24, 3,19, 6,25, 22, 4,20,10,16, 7,12,26,
+ 31,23,18, 5,21, 9,15,11,30,17, 8,14,29,13,28,27
+ };
+
+ if (x == 0) return 32;
+ x = (x & -x) * 0x04D7651F;
+ return table[x >> 27];
+}
+
+static const unsigned long long magic = 0x03f08c5392f756cdULL;
+
+static const char table[64] = {
+ 0, 1, 12, 2, 13, 22, 17, 3,
+ 14, 33, 23, 36, 18, 58, 28, 4,
+ 62, 15, 34, 26, 24, 48, 50, 37,
+ 19, 55, 59, 52, 29, 44, 39, 5,
+ 63, 11, 21, 16, 32, 35, 57, 27,
+ 61, 25, 47, 49, 54, 51, 43, 38,
+ 10, 20, 31, 56, 60, 46, 53, 42,
+ 9, 30, 45, 41, 8, 40, 7, 6,
+};
+
+int ctz4 (unsigned long x)
+{
+ unsigned long lsb = x & -x;
+ return table[(lsb * magic) >> 58];
+}
+
+/* { dg-final { scan-assembler-times "clz\t" 4 } } */
+/* { dg-final { scan-assembler-times "and\t" 2 } } */
+/* { dg-final { scan-assembler-not "cmp\t.*0" } } */
More information about the Gcc-patches
mailing list