From: Kyrylo Tkachov <[email protected]>
Extend the double-word clz/ctz combine to the software De Bruijn ctz/clz
fallbacks (as used by zstd when hardware count instructions are disabled).
GCC recognizes each 32-bit fallback as a two-argument .C[LT]Z (HALF, W)
defined at zero, optionally followed by an "AND (W - 1)" mask or a
"HALF == 0 ? C : ..." select that sets the value at zero. Match those
per-half forms, compute the combined value at zero (the word offset plus the
offset arm value there) and emit a single wide count, preserving that value
with a two-argument .C[LT]Z when the target already produces it, or an
explicit "X == 0 ? value : count" otherwise.
Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux.
This patch gives ~3% on the zstd benchmark in SPEC2026 on my aarch64
system.
PR tree-optimization/126035
gcc/ChangeLog:
* tree-ssa-phiopt.cc (clzctz_match_arm): Handle a two-argument
.C[LT]Z and an optional zero-only mask or select.
(clzctz_combine_replacement): Preserve a defined value at zero.
gcc/testsuite/ChangeLog:
* gcc.target/aarch64/pr126035-debruijn.c: New test.
* gcc.target/aarch64/pr126035-debruijn-run.c: New test.
* gcc.target/aarch64/pr126035-debruijn-g.c: New test.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
.../gcc.target/aarch64/pr126035-debruijn-g.c | 30 +++
.../aarch64/pr126035-debruijn-run.c | 78 +++++++
.../gcc.target/aarch64/pr126035-debruijn.c | 50 ++++
gcc/tree-ssa-phiopt.cc | 220 ++++++++++++++++--
4 files changed, 358 insertions(+), 20 deletions(-)
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr126035-debruijn-g.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr126035-debruijn-run.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr126035-debruijn.c
diff --git a/gcc/testsuite/gcc.target/aarch64/pr126035-debruijn-g.c
b/gcc/testsuite/gcc.target/aarch64/pr126035-debruijn-g.c
new file mode 100644
index 00000000000..539fdf48275
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr126035-debruijn-g.c
@@ -0,0 +1,30 @@
+/* Like the plain-builtin -g test but for the De Bruijn (defined-at-zero)
+ select-fixup path of the combine; check we do not ICE in verify_ssa under
+ -g. */
+/* { dg-do compile } */
+/* { dg-options "-O2 -g" } */
+
+#include <stdint.h>
+typedef uint32_t U32;
+typedef uint64_t U64;
+
+static inline unsigned
+ctz32_fallback (U32 val)
+{
+ static const U32 T[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 T[((U32) ((val & -(U32) val) * 0x077CB531U)) >> 27];
+}
+
+unsigned
+f (U64 val)
+{
+ U32 hi = (U32) (val >> 32), lo = (U32) val;
+ unsigned r;
+ if (lo == 0)
+ r = 32 + ctz32_fallback (hi);
+ else
+ r = ctz32_fallback (lo);
+ return r;
+}
diff --git a/gcc/testsuite/gcc.target/aarch64/pr126035-debruijn-run.c
b/gcc/testsuite/gcc.target/aarch64/pr126035-debruijn-run.c
new file mode 100644
index 00000000000..90353537a4a
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr126035-debruijn-run.c
@@ -0,0 +1,78 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+/* Run-time check of the De Bruijn split clz/ctz combine, including the
+ values the fallbacks define at zero (ctz: 32, clz: 63), which the combine
+ must preserve. */
+
+#include <stdint.h>
+typedef uint32_t U32;
+typedef uint64_t U64;
+
+static inline unsigned
+ctz32_fallback (U32 val)
+{
+ static const U32 T[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 T[((U32) ((val & -(U32) val) * 0x077CB531U)) >> 27];
+}
+
+static inline unsigned
+clz32_fallback (U32 val)
+{
+ static const U32 T[32] = {
+ 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
+ 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 };
+ val |= val >> 1; val |= val >> 2; val |= val >> 4;
+ val |= val >> 8; val |= val >> 16;
+ return 31 - T[(val * 0x07C4ACDDU) >> 27];
+}
+
+unsigned __attribute__((noipa))
+ctz64_split (U64 val)
+{
+ U32 msw = (U32) (val >> 32);
+ U32 lsw = (U32) val;
+ return lsw == 0 ? 32 + ctz32_fallback (msw) : ctz32_fallback (lsw);
+}
+
+unsigned __attribute__((noipa))
+clz64_split (U64 val)
+{
+ U32 msw = (U32) (val >> 32);
+ U32 lsw = (U32) val;
+ return msw == 0 ? 32 + clz32_fallback (lsw) : clz32_fallback (msw);
+}
+
+int
+main (void)
+{
+ /* Values defined by the fallbacks at zero must be preserved. */
+ if (ctz64_split (0) != 32)
+ __builtin_abort ();
+ if (clz64_split (0) != 63)
+ __builtin_abort ();
+
+ U64 v = 0x9E3779B97F4A7C15ULL;
+ for (int i = 0; i < 200000; i++)
+ {
+ v = v * 6364136223846793005ULL + 1442695040888963407ULL;
+ U64 x = v;
+ switch (i & 7)
+ {
+ case 0: x = 1ULL << (v % 64); break;
+ case 1: x = (U32) v; break;
+ case 2: x = ((U64) (U32) v) << 32; break;
+ case 3: x = ~0ULL; break;
+ default: break;
+ }
+ if (x == 0)
+ x = 1;
+ if (ctz64_split (x) != (unsigned) __builtin_ctzll (x))
+ __builtin_abort ();
+ if (clz64_split (x) != (unsigned) __builtin_clzll (x))
+ __builtin_abort ();
+ }
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.target/aarch64/pr126035-debruijn.c
b/gcc/testsuite/gcc.target/aarch64/pr126035-debruijn.c
new file mode 100644
index 00000000000..64277a24758
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr126035-debruijn.c
@@ -0,0 +1,50 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* The De Bruijn software ctz/clz fallbacks are recognized as defined-at-zero
+ .CTZ/.CLZ. The split double-word forms should still be combined into a
+ single wide .CTZ/.CLZ (with the defined value at zero preserved by a
+ select). */
+
+#include <stdint.h>
+typedef uint32_t U32;
+typedef uint64_t U64;
+
+static inline unsigned
+ctz32_fallback (U32 val)
+{
+ static const U32 T[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 T[((U32) ((val & -(U32) val) * 0x077CB531U)) >> 27];
+}
+
+static inline unsigned
+clz32_fallback (U32 val)
+{
+ static const U32 T[32] = {
+ 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
+ 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 };
+ val |= val >> 1; val |= val >> 2; val |= val >> 4;
+ val |= val >> 8; val |= val >> 16;
+ return 31 - T[(val * 0x07C4ACDDU) >> 27];
+}
+
+unsigned
+ctz64_split (U64 val)
+{
+ U32 msw = (U32) (val >> 32);
+ U32 lsw = (U32) val;
+ return lsw == 0 ? 32 + ctz32_fallback (msw) : ctz32_fallback (lsw);
+}
+
+unsigned
+clz64_split (U64 val)
+{
+ U32 msw = (U32) (val >> 32);
+ U32 lsw = (U32) val;
+ return msw == 0 ? 32 + clz32_fallback (lsw) : clz32_fallback (msw);
+}
+
+/* { dg-final { scan-tree-dump-times {= \.CTZ } 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times {= \.CLZ } 1 "optimized" } } */
diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index faf954d2b42..0ae525bd070 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -2555,16 +2555,23 @@ spaceship_replacement (basic_block cond_bb, basic_block
middle_bb,
return true;
}
-/* Helper for clzctz_combine_replacement. Match ARG as
- (T) __builtin_c[lt]z (HALF)
- with an optional integer constant added (the high-half word offset) and
- integer conversions wrapped around it. On success return true and set *PCFN
- to the combined_fn of the (single-argument) clz/ctz call, *PHALF to its
- argument and *POFFSET to the added constant. */
+/* Helper for clzctz_combine_replacement. Match ARG as a per-half count
+
+ (T) [ __builtin_c[lt]z (HALF) | .C[LT]Z (HALF[, Z]) ]
+
+ with an optional integer constant added (the high-half word offset), an
+ optional zero-only correction (a `& (W - 1)' mask or a
+ `HALF == 0 ? C : count' select, as emitted for the De Bruijn software
+ fallbacks) and integer conversions wrapped around it. On success return
+ true and set *PCFN to the call's combined_fn, *PHALF to its argument and
+ *POFFSET to the added constant. If PZERO_KNOWN/PZERO_VAL are non-null they
+ receive whether the count's value at HALF == 0 is known and, if so, that
+ value (undefined for the plain one-argument builtins). */
static bool
clzctz_match_arm (tree arg, combined_fn *pcfn, tree *phalf,
- unsigned HOST_WIDE_INT *poffset)
+ unsigned HOST_WIDE_INT *poffset, bool *pzero_known,
+ unsigned HOST_WIDE_INT *pzero_val)
{
if (!INTEGRAL_TYPE_P (TREE_TYPE (arg)))
return false;
@@ -2573,6 +2580,7 @@ clzctz_match_arm (tree arg, combined_fn *pcfn, tree
*phalf,
unsigned min_ebits = HOST_BITS_PER_WIDE_INT;
tree t = arg;
+ /* Peel integer conversions and the constant word offset. */
for (int limit = 0; limit < 8 && TREE_CODE (t) == SSA_NAME; limit++)
{
unsigned ebits
@@ -2594,10 +2602,70 @@ clzctz_match_arm (tree arg, combined_fn *pcfn, tree
*phalf,
break;
}
+ /* Peel an optional zero-only correction: a `& M' mask or a
+ `HALF == 0 ? C : count' select. */
+ bool have_mask = false, have_select = false;
+ unsigned HOST_WIDE_INT mask = 0;
+ tree sel_cond = NULL_TREE, sel_const = NULL_TREE;
+ bool sel_true_is_const = false;
+ if (TREE_CODE (t) == SSA_NAME)
+ {
+ gimple *def = SSA_NAME_DEF_STMT (t);
+ if (is_gimple_assign (def)
+ && gimple_assign_rhs_code (def) == BIT_AND_EXPR
+ && tree_fits_uhwi_p (gimple_assign_rhs2 (def)))
+ {
+ have_mask = true;
+ mask = tree_to_uhwi (gimple_assign_rhs2 (def));
+ t = gimple_assign_rhs1 (def);
+ }
+ else if (is_gimple_assign (def)
+ && gimple_assign_rhs_code (def) == COND_EXPR)
+ {
+ tree tv = gimple_assign_rhs2 (def);
+ tree fv = gimple_assign_rhs3 (def);
+ if (TREE_CODE (tv) == INTEGER_CST && TREE_CODE (fv) == SSA_NAME)
+ {
+ sel_const = tv;
+ sel_true_is_const = true;
+ t = fv;
+ }
+ else if (TREE_CODE (fv) == INTEGER_CST && TREE_CODE (tv) == SSA_NAME)
+ {
+ sel_const = fv;
+ sel_true_is_const = false;
+ t = tv;
+ }
+ else
+ return false;
+ if (!tree_fits_uhwi_p (sel_const))
+ return false;
+ have_select = true;
+ sel_cond = gimple_assign_rhs1 (def);
+ }
+ }
+
+ /* Peel conversions before the call. */
+ while (TREE_CODE (t) == SSA_NAME)
+ {
+ unsigned ebits
+ = TYPE_PRECISION (TREE_TYPE (t)) - !TYPE_UNSIGNED (TREE_TYPE (t));
+ min_ebits = MIN (min_ebits, ebits);
+ gimple *def = SSA_NAME_DEF_STMT (t);
+ if (gimple_assign_cast_p (def)
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (def))))
+ t = gimple_assign_rhs1 (def);
+ else
+ break;
+ }
+
if (TREE_CODE (t) != SSA_NAME)
return false;
gimple *call = SSA_NAME_DEF_STMT (t);
- if (!is_gimple_call (call) || gimple_call_num_args (call) != 1)
+ if (!is_gimple_call (call))
+ return false;
+ unsigned nargs = gimple_call_num_args (call);
+ if (nargs != 1 && nargs != 2)
return false;
combined_fn cfn = gimple_call_combined_fn (call);
switch (cfn)
@@ -2622,9 +2690,71 @@ clzctz_match_arm (tree arg, combined_fn *pcfn, tree
*phalf,
&& offset + prec > (HOST_WIDE_INT_1U << min_ebits) - 1)
return false;
+ /* Value of the bare call at HALF == 0: the explicit operand of a
+ two-argument .C[LT]Z, otherwise undefined. */
+ bool zero_known = false;
+ unsigned HOST_WIDE_INT zero_val = 0;
+ if (nargs == 2)
+ {
+ tree z = gimple_call_arg (call, 1);
+ if (TREE_CODE (z) != INTEGER_CST || !tree_fits_uhwi_p (z))
+ return false;
+ zero_known = true;
+ zero_val = tree_to_uhwi (z);
+ }
+
+ if (have_mask)
+ {
+ /* The mask must leave any valid count in [0, prec - 1] unchanged. */
+ if ((mask & (prec - 1)) != prec - 1)
+ return false;
+ zero_val &= mask;
+ }
+ else if (have_select)
+ {
+ /* The select must read `HALF == 0 ? C : count', overriding only the
+ value at zero. */
+ tree_code rel;
+ tree l, r;
+ if (TREE_CODE (sel_cond) == SSA_NAME
+ && is_gimple_assign (SSA_NAME_DEF_STMT (sel_cond))
+ && (TREE_CODE_CLASS (gimple_assign_rhs_code
+ (SSA_NAME_DEF_STMT (sel_cond)))
+ == tcc_comparison))
+ {
+ gimple *cdef = SSA_NAME_DEF_STMT (sel_cond);
+ rel = gimple_assign_rhs_code (cdef);
+ l = gimple_assign_rhs1 (cdef);
+ r = gimple_assign_rhs2 (cdef);
+ }
+ else if (COMPARISON_CLASS_P (sel_cond))
+ {
+ rel = TREE_CODE (sel_cond);
+ l = TREE_OPERAND (sel_cond, 0);
+ r = TREE_OPERAND (sel_cond, 1);
+ }
+ else
+ return false;
+ if ((rel != EQ_EXPR && rel != NE_EXPR)
+ || l != half
+ || !integer_zerop (r))
+ return false;
+ /* The value at HALF == 0 must be the constant, not the count. */
+ bool picks_const_at_zero
+ = (rel == EQ_EXPR) ? sel_true_is_const : !sel_true_is_const;
+ if (!picks_const_at_zero)
+ return false;
+ zero_known = true;
+ zero_val = tree_to_uhwi (sel_const);
+ }
+
*pcfn = cfn;
*phalf = half;
*poffset = offset;
+ if (pzero_known)
+ *pzero_known = zero_known;
+ if (pzero_val)
+ *pzero_val = zero_val;
return true;
}
@@ -2695,9 +2825,14 @@ clzctz_decode_half (tree half, tree *pbase, unsigned
*pwidth, bool *pis_high,
_b = (T) (__builtin_clz (LO) + W);
# res = PHI <_a, _b>
- computes res = (T) clzll (X). As the original __builtin_c[lt]z calls are
- undefined at zero, X == 0 is undefined in both the idiom and the result, so
- the combined count is emitted as a one-argument .CTZ/.CLZ.
+ computes res = (T) clzll (X). The per-half counts are either plain
+ __builtin_c[lt]z (undefined at zero) or, for the De Bruijn software
+ fallbacks GCC recognizes, a `.C[LT]Z (HALF, W)' optionally wrapped in a
+ `& (W - 1)' mask or `HALF == 0 ? C : ...' select that defines the value at
+ zero. When the result is undefined at X == 0 a one-argument .C[LT]Z is
+ emitted; when it is defined, the value at zero is reproduced either by a
+ two-argument .C[LT]Z (if the target already yields it) or by an explicit
+ `X == 0 ? value : count'.
COND_BB ends in `cmp0 [!=|==] 0'; MIDDLE_BB and MIDDLE_BB_ALT are the two
arms, E0/E1 the edges from them into the merge block holding PHI, and
@@ -2742,8 +2877,10 @@ clzctz_combine_replacement (basic_block cond_bb,
basic_block middle_bb,
combined_fn cfn_nz, cfn_z;
tree half_nz, half_z;
unsigned HOST_WIDE_INT off_nz, off_z;
- if (!clzctz_match_arm (arg_nz, &cfn_nz, &half_nz, &off_nz)
- || !clzctz_match_arm (arg_z, &cfn_z, &half_z, &off_z)
+ bool zk_z;
+ unsigned HOST_WIDE_INT zv_z;
+ if (!clzctz_match_arm (arg_nz, &cfn_nz, &half_nz, &off_nz, NULL, NULL)
+ || !clzctz_match_arm (arg_z, &cfn_z, &half_z, &off_z, &zk_z, &zv_z)
|| cfn_nz != cfn_z
|| off_nz != 0)
return false;
@@ -2790,18 +2927,61 @@ clzctz_combine_replacement (basic_block cond_bb,
basic_block middle_bb,
OPTIMIZE_FOR_BOTH))
return false;
+ /* When the counts are defined at zero (the De Bruijn fallbacks) the
+ combined count must keep the idiom's value at X == 0, OFF_Z + ZV_Z: with
+ a two-argument .C[LT]Z when the target already yields it, or an explicit
+ "X == 0 ? value : count" otherwise. */
+ unsigned HOST_WIDE_INT zero_at = 0;
+ bool zero_matches_hw = false;
+ if (zk_z)
+ {
+ zero_at = off_z + zv_z;
+ if (zero_at > TYPE_PRECISION (TREE_TYPE (fullvar)))
+ return false;
+ int hwz = 0;
+ scalar_int_mode mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (fullvar));
+ int defined = (is_clz
+ ? CLZ_DEFINED_VALUE_AT_ZERO (mode, hwz)
+ : CTZ_DEFINED_VALUE_AT_ZERO (mode, hwz));
+ zero_matches_hw = (defined == 2
+ && (unsigned HOST_WIDE_INT) hwz == zero_at);
+ }
+
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Combining double-word %s in block %d.\n",
is_clz ? "clz" : "ctz", cond_bb->index);
- /* Replace the PHI with a single wide clz/ctz of the full value defining the
- PHI result. As __builtin_c[lt]z is undefined at zero, a one-argument
- .C[LT]Z is used. Insert it at the head of the merge block, before any
- leading debug bind of the PHI result. */
- gcall *call = gimple_build_call_internal (ifn, 1, fullvar);
- gimple_call_set_lhs (call, gimple_phi_result (phi));
+ /* Build the wide count to replace the PHI, defining the PHI result.
+ Insert it at the head of the merge block, before any leading debug bind
+ of that result. */
+ tree res = gimple_phi_result (phi);
+ gimple_seq seq = NULL;
+ gimple *def;
+ if (!zk_z || zero_matches_hw)
+ {
+ gcall *call
+ = zk_z
+ ? gimple_build_call_internal (ifn, 2, fullvar,
+ build_int_cst (integer_type_node,
+ zero_at))
+ : gimple_build_call_internal (ifn, 1, fullvar);
+ gimple_call_set_lhs (call, res);
+ def = call;
+ }
+ else
+ {
+ /* res = (fullvar == 0) ? zero_at : .C[LT]Z (fullvar). */
+ tree cnt = gimple_build (&seq, as_combined_fn (ifn), TREE_TYPE (res),
+ fullvar);
+ tree zerop = gimple_build (&seq, EQ_EXPR, boolean_type_node, fullvar,
+ build_zero_cst (TREE_TYPE (fullvar)));
+ def = gimple_build_assign (res, COND_EXPR, zerop,
+ build_int_cst (TREE_TYPE (res), zero_at),
+ cnt);
+ }
gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
- gsi_insert_before (&gsi, call, GSI_SAME_STMT);
+ gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
+ gsi_insert_before (&gsi, def, GSI_SAME_STMT);
auto_bitmap exprs_maybe_dce;
bitmap_set_bit (exprs_maybe_dce, SSA_NAME_VERSION (arg0));
--
2.50.1 (Apple Git-155)
