diff options
author | Wilco Dijkstra <wdijkstr@arm.com> | 2020-01-10 19:32:53 +0000 |
---|---|---|
committer | Wilco Dijkstra <wilco@gcc.gnu.org> | 2020-01-10 19:32:53 +0000 |
commit | b937050d302ba3984eec7c76381081ca8f5962aa (patch) | |
tree | f169a714f75186893d8fb45d460e280a09e4402e /gcc/match.pd | |
parent | 9869896730f3055850034c05c596828d517fa9a2 (diff) |
PR90838: Support ctz idioms
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 creates 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
gcc/
PR tree-optimization/90838
* tree-ssa-forwprop.c (check_ctz_array): Add new function.
(check_ctz_string): Likewise.
(optimize_count_trailing_zeroes): Likewise.
(simplify_count_trailing_zeroes): Likewise.
(pass_forwprop::execute): Try ctz simplification.
* match.pd: Add matching for ctz idioms.
testsuite/
PR tree-optimization/90838
* testsuite/gcc.target/aarch64/pr90838.c: New test.
From-SVN: r280132
Diffstat (limited to 'gcc/match.pd')
-rw-r--r-- | gcc/match.pd | 8 |
1 files changed, 8 insertions, 0 deletions
diff --git a/gcc/match.pd b/gcc/match.pd index a3badb2c44b..5fee394e7af 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -6152,3 +6152,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (simplify (vec_perm vec_same_elem_p@0 @0 @1) @0) + +/* Match count trailing zeroes for simplify_count_trailing_zeroes in fwprop. + 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. */ +(match (ctz_table_index @1 @2 @3) + (rshift (mult (bit_and:c (negate @1) @1) INTEGER_CST@2) INTEGER_CST@3)) |