From: Kyrylo Tkachov <[email protected]>
A double-word count of trailing or leading zeros written as
lo ? ctz (lo) : 32 + ctz (hi)
with lo and hi the low and high halves of X equals a single wide ctzll (X),
and likewise for clz, but GCC kept the branch and two narrow counts.
Recognize the idiom in phiopt diamond handling and emit one .CTZ/.CLZ on the
double-word value. As __builtin_c[lt]z is undefined at zero, so is the
result, so a one-argument .CTZ/.CLZ is used.
Based on a prototype by Andrea, refactored into helpers and extended
to handle clz as well as ctz, with testcases added.
Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux.
PR tree-optimization/126035
gcc/ChangeLog:
* tree-ssa-phiopt.cc (clzctz_match_arm): New function.
(clzctz_decode_half): New function.
(clzctz_combine_replacement): New function.
(pass_phiopt::execute): Call it for the diamond case.
gcc/testsuite/ChangeLog:
* gcc.target/aarch64/pr126035.c: New test.
* gcc.target/aarch64/pr126035-clz.c: New test.
* gcc.target/aarch64/pr126035-run.c: New test.
* gcc.target/aarch64/pr126035-debug.c: New test.
* gcc.target/aarch64/pr126035-extra-pred.c: New test.
* gcc.target/aarch64/pr126035-narrow.c: New test.
Co-authored-by: Andrew Pinski <[email protected]>
Signed-off-by: Andrew Pinski <[email protected]>
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
.../gcc.target/aarch64/pr126035-clz.c | 19 ++
.../gcc.target/aarch64/pr126035-debug.c | 19 ++
.../gcc.target/aarch64/pr126035-extra-pred.c | 35 +++
.../gcc.target/aarch64/pr126035-narrow.c | 33 +++
.../gcc.target/aarch64/pr126035-run.c | 50 ++++
gcc/testsuite/gcc.target/aarch64/pr126035.c | 26 ++
gcc/tree-ssa-phiopt.cc | 263 ++++++++++++++++++
7 files changed, 445 insertions(+)
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr126035-clz.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr126035-debug.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr126035-extra-pred.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr126035-narrow.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr126035-run.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr126035.c
diff --git a/gcc/testsuite/gcc.target/aarch64/pr126035-clz.c
b/gcc/testsuite/gcc.target/aarch64/pr126035-clz.c
new file mode 100644
index 00000000000..933668b6592
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr126035-clz.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+#include <stdint.h>
+
+static inline unsigned clz32 (uint32_t v) { return (unsigned) __builtin_clz
(v); }
+
+/* The symmetric split CLZ32 idiom should be combined into a single double-word
+ clz, with no conditional select left over. */
+unsigned
+clz64_split (uint64_t val)
+{
+ uint32_t hi = (uint32_t) (val >> 32);
+ uint32_t lo = (uint32_t) val;
+ return hi ? clz32 (hi) : 32u + clz32 (lo);
+}
+
+/* { dg-final { scan-assembler-not {\tcsel\t} } } */
+/* { dg-final { scan-assembler-times {\tclz\t} 1 } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/pr126035-debug.c
b/gcc/testsuite/gcc.target/aarch64/pr126035-debug.c
new file mode 100644
index 00000000000..aae4c25c3ac
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr126035-debug.c
@@ -0,0 +1,19 @@
+/* The combined count is inserted at the head of the merge block; with a named
+ intermediate a debug bind for it is present there under -g. Check we do not
+ ICE in verify_ssa. */
+/* { dg-do compile } */
+/* { dg-options "-O2 -g" } */
+
+#include <stdint.h>
+
+unsigned
+f (uint64_t val)
+{
+ uint32_t hi = (uint32_t) (val >> 32), lo = (uint32_t) val;
+ unsigned r;
+ if (lo)
+ r = (unsigned) __builtin_ctz (lo);
+ else
+ r = 32u + (unsigned) __builtin_ctz (hi);
+ return r;
+}
diff --git a/gcc/testsuite/gcc.target/aarch64/pr126035-extra-pred.c
b/gcc/testsuite/gcc.target/aarch64/pr126035-extra-pred.c
new file mode 100644
index 00000000000..36db23aec81
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr126035-extra-pred.c
@@ -0,0 +1,35 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+/* The merge block has a third incoming path; the split count must not be
+ combined and the value arriving on that path must be preserved. */
+
+unsigned __attribute__((noipa))
+f (unsigned long long x, int c, unsigned other)
+{
+ unsigned r;
+ unsigned lo = x, hi = x >> 32;
+ if (c)
+ {
+ r = other;
+ goto out;
+ }
+ if (lo)
+ r = __builtin_ctz (lo);
+ else
+ r = 32 + __builtin_ctz (hi);
+ out:
+ return r;
+}
+
+int
+main (void)
+{
+ if (f (4ULL, 1, 77) != 77)
+ __builtin_abort ();
+ if (f (4ULL, 0, 77) != 2)
+ __builtin_abort ();
+ if (f (1ULL << 52, 0, 77) != 52)
+ __builtin_abort ();
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.target/aarch64/pr126035-narrow.c
b/gcc/testsuite/gcc.target/aarch64/pr126035-narrow.c
new file mode 100644
index 00000000000..3258da2d0a5
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr126035-narrow.c
@@ -0,0 +1,33 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+/* The high-half count is truncated by a narrow signed intermediate before
+ the word offset is added, so this is not the split double-word idiom and
+ must not be combined. */
+
+struct S { signed int c : 4; };
+
+unsigned __attribute__((noipa))
+f (unsigned long long x)
+{
+ struct S s;
+ unsigned lo = x, hi = x >> 32;
+ unsigned r;
+ if (lo)
+ r = __builtin_ctz (lo);
+ else
+ {
+ s.c = __builtin_ctz (hi);
+ r = s.c + 32;
+ }
+ return r;
+}
+
+int
+main (void)
+{
+ /* ctz (hi) == 20 truncates to 4 in the 4-bit field: 36, not 52. */
+ if (f (1ULL << 52) != 36)
+ __builtin_abort ();
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.target/aarch64/pr126035-run.c
b/gcc/testsuite/gcc.target/aarch64/pr126035-run.c
new file mode 100644
index 00000000000..0ff1a536313
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr126035-run.c
@@ -0,0 +1,50 @@
+/* { dg-do run } */
+/* { dg-require-effective-target ctz } */
+/* { dg-options "-O2" } */
+
+#include <stdint.h>
+
+static inline unsigned ctz32 (uint32_t v) { return (unsigned) __builtin_ctz
(v); }
+static inline unsigned clz32 (uint32_t v) { return (unsigned) __builtin_clz
(v); }
+
+unsigned __attribute__((noipa))
+ctz64_split (uint64_t val)
+{
+ uint32_t hi = (uint32_t) (val >> 32);
+ uint32_t lo = (uint32_t) val;
+ return lo ? ctz32 (lo) : 32u + ctz32 (hi);
+}
+
+unsigned __attribute__((noipa))
+clz64_split (uint64_t val)
+{
+ uint32_t hi = (uint32_t) (val >> 32);
+ uint32_t lo = (uint32_t) val;
+ return hi ? clz32 (hi) : 32u + clz32 (lo);
+}
+
+int
+main (void)
+{
+ uint64_t v = 0x9E3779B97F4A7C15ULL;
+ for (int i = 0; i < 200000; i++)
+ {
+ v = v * 6364136223846793005ULL + 1442695040888963407ULL;
+ uint64_t x = v;
+ switch (i & 7)
+ {
+ case 0: x = 1ULL << (v % 64); break;
+ case 1: x = (uint32_t) v; break;
+ case 2: x = ((uint64_t) (uint32_t) 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.c
b/gcc/testsuite/gcc.target/aarch64/pr126035.c
new file mode 100644
index 00000000000..33d481d3469
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr126035.c
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+#include <stdint.h>
+
+static inline unsigned ctz32 (uint32_t v) { return (unsigned) __builtin_ctz
(v); }
+
+unsigned
+ctz64_split (uint64_t val)
+{
+ uint32_t hi = (uint32_t) (val >> 32);
+ uint32_t lo = (uint32_t) val;
+ return lo ? ctz32 (lo) : 32u + ctz32 (hi);
+}
+
+const unsigned char *
+match_extend (const unsigned char *p, uint64_t x)
+{
+ return p + (ctz64_split (x) >> 3);
+}
+
+/* The split CTZ32 idiom should be combined into a single double-word ctz
+ (rbit + clz), with no conditional select left over. */
+/* { dg-final { scan-assembler-not {\tcsel\t} } } */
+/* { dg-final { scan-assembler-times {\trbit\t} 2 } } */
+/* { dg-final { scan-assembler-times {\tclz\t} 2 } } */
diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index e12dc7a8b0c..faf954d2b42 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -2555,6 +2555,265 @@ 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. */
+
+static bool
+clzctz_match_arm (tree arg, combined_fn *pcfn, tree *phalf,
+ unsigned HOST_WIDE_INT *poffset)
+{
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (arg)))
+ return false;
+
+ unsigned HOST_WIDE_INT offset = 0;
+ unsigned min_ebits = HOST_BITS_PER_WIDE_INT;
+ tree t = arg;
+
+ for (int limit = 0; limit < 8 && TREE_CODE (t) == SSA_NAME; limit++)
+ {
+ 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 (!is_gimple_assign (def))
+ break;
+ if (gimple_assign_cast_p (def)
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (def))))
+ t = gimple_assign_rhs1 (def);
+ else if (gimple_assign_rhs_code (def) == PLUS_EXPR
+ && tree_fits_uhwi_p (gimple_assign_rhs2 (def)))
+ {
+ offset += tree_to_uhwi (gimple_assign_rhs2 (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)
+ return false;
+ combined_fn cfn = gimple_call_combined_fn (call);
+ switch (cfn)
+ {
+ CASE_CFN_CLZ:
+ CASE_CFN_CTZ:
+ break;
+ default:
+ return false;
+ }
+
+ tree half = gimple_call_arg (call, 0);
+ if (TREE_CODE (half) != SSA_NAME)
+ return false;
+
+ /* Every type the count passes through must represent the count plus the
+ accumulated offset unchanged. A narrower signed intermediate (a signed
+ bit-field, say) is not canonicalized to a mask and would change the
+ value. */
+ unsigned prec = TYPE_PRECISION (TREE_TYPE (half));
+ if (min_ebits < HOST_BITS_PER_WIDE_INT
+ && offset + prec > (HOST_WIDE_INT_1U << min_ebits) - 1)
+ return false;
+
+ *pcfn = cfn;
+ *phalf = half;
+ *poffset = offset;
+ return true;
+}
+
+/* Helper for clzctz_combine_replacement. Decode HALF as the low or high half
+ of a double-word value: `(NARROW) X' (low half) or `(NARROW) (X >> W)' (high
+ half), where W == TYPE_PRECISION (NARROW) and X is an unsigned value of
+ precision 2 * W. On success return true and set *PBASE to X, *PWIDTH to W,
+ *PIS_HIGH to whether it is the high half and, if PINNER is non-null,
+ *PINNER to the value feeding the final truncation (X for the low half,
+ X >> W for the high half). */
+
+static bool
+clzctz_decode_half (tree half, tree *pbase, unsigned *pwidth, bool *pis_high,
+ tree *pinner)
+{
+ if (TREE_CODE (half) != SSA_NAME)
+ return false;
+ unsigned narrow_prec = TYPE_PRECISION (TREE_TYPE (half));
+ gimple *def = SSA_NAME_DEF_STMT (half);
+ if (!gimple_assign_cast_p (def))
+ return false;
+ tree inner = gimple_assign_rhs1 (def);
+ if (TREE_CODE (inner) != SSA_NAME
+ || !INTEGRAL_TYPE_P (TREE_TYPE (inner))
+ || !TYPE_UNSIGNED (TREE_TYPE (inner))
+ || TYPE_PRECISION (TREE_TYPE (inner)) != 2 * narrow_prec)
+ return false;
+
+ if (pinner)
+ *pinner = inner;
+ *pwidth = narrow_prec;
+
+ /* High half: inner == X >> W. */
+ gimple *idef = SSA_NAME_DEF_STMT (inner);
+ if (is_gimple_assign (idef)
+ && gimple_assign_rhs_code (idef) == RSHIFT_EXPR
+ && tree_fits_uhwi_p (gimple_assign_rhs2 (idef))
+ && tree_to_uhwi (gimple_assign_rhs2 (idef)) == narrow_prec)
+ {
+ *pbase = gimple_assign_rhs1 (idef);
+ *pis_high = true;
+ return true;
+ }
+
+ /* Otherwise the low half: inner == X. */
+ *pbase = inner;
+ *pis_high = false;
+ return true;
+}
+
+/* Attempt to combine a split clz/ctz idiom across a diamond into a single
+ double-word clz/ctz.
+
+ With LO = (NARROW) X and HI = (NARROW) (X >> W), W the precision of NARROW
+ and X a double-word value, the ctz form
+
+ if (LO != 0)
+ _a = (T) __builtin_ctz (LO);
+ else
+ _b = (T) (__builtin_ctz (HI) + W);
+ # res = PHI <_a, _b>
+
+ computes res = (T) ctzll (X), and the symmetric clz form
+
+ if (HI != 0)
+ _a = (T) __builtin_clz (HI);
+ else
+ _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.
+
+ 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
+ ARG0/ARG1 the corresponding PHI arguments. */
+
+static bool
+clzctz_combine_replacement (basic_block cond_bb, basic_block middle_bb,
+ basic_block middle_bb_alt, edge e0, edge e1,
+ gphi *phi, tree arg0, tree arg1)
+{
+ gcc_checking_assert (e0->dest == gimple_bb (phi)
+ && e1->dest == gimple_bb (phi)
+ && single_pred_p (middle_bb)
+ && single_pred_p (middle_bb_alt));
+
+ /* The merge block must have no other incoming edges: the PHI is replaced
+ by the combined count on all paths. */
+ if (EDGE_COUNT (gimple_bb (phi)->preds) != 2)
+ return false;
+
+ gcond *stmt = as_a <gcond *> (*gsi_last_bb (cond_bb));
+ tree_code cmp = gimple_cond_code (stmt);
+ tree cmp0 = gimple_cond_lhs (stmt);
+
+ if ((cmp != EQ_EXPR && cmp != NE_EXPR)
+ || !integer_zerop (gimple_cond_rhs (stmt))
+ || TREE_CODE (cmp0) != SSA_NAME
+ || !INTEGRAL_TYPE_P (TREE_TYPE (cmp0)))
+ return false;
+
+ if (TREE_CODE (arg0) != SSA_NAME || TREE_CODE (arg1) != SSA_NAME)
+ return false;
+
+ /* Find the arm reached when `cmp0 != 0' (the directly-counted half) and the
+ arm reached when `cmp0 == 0' (the other half plus the word offset). */
+ edge true_edge, false_edge;
+ extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
+ basic_block nz_bb = (cmp == NE_EXPR) ? true_edge->dest : false_edge->dest;
+ tree arg_nz = (nz_bb == middle_bb) ? arg0 : arg1;
+ tree arg_z = (nz_bb == middle_bb) ? arg1 : arg0;
+
+ 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)
+ || cfn_nz != cfn_z
+ || off_nz != 0)
+ return false;
+
+ bool is_clz;
+ switch (cfn_nz)
+ {
+ CASE_CFN_CTZ:
+ is_clz = false;
+ break;
+ CASE_CFN_CLZ:
+ is_clz = true;
+ break;
+ default:
+ return false;
+ }
+
+ tree base_nz, base_z, inner_nz;
+ unsigned w_nz, w_z;
+ bool high_nz, high_z;
+ if (!clzctz_decode_half (half_nz, &base_nz, &w_nz, &high_nz, &inner_nz)
+ || !clzctz_decode_half (half_z, &base_z, &w_z, &high_z, NULL)
+ || w_nz != w_z
+ || high_nz == high_z
+ || base_nz != base_z
+ || off_z != w_nz)
+ return false;
+
+ /* For ctz the directly-counted half is the low half; for clz it is the high
+ half. */
+ if (high_nz != is_clz)
+ return false;
+
+ /* The condition must test the nonzero-ness of the directly-counted half: the
+ half itself, or - for the high half - its pre-truncation value X >> W,
+ since (X >> W) != 0 iff (NARROW) (X >> W) != 0. */
+ if (cmp0 != half_nz
+ && !(high_nz && cmp0 == inner_nz))
+ return false;
+
+ tree fullvar = base_nz;
+ internal_fn ifn = is_clz ? IFN_CLZ : IFN_CTZ;
+ if (!direct_internal_fn_supported_p (ifn, TREE_TYPE (fullvar),
+ OPTIMIZE_FOR_BOTH))
+ return false;
+
+ 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));
+ gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
+ gsi_insert_before (&gsi, call, GSI_SAME_STMT);
+
+ auto_bitmap exprs_maybe_dce;
+ bitmap_set_bit (exprs_maybe_dce, SSA_NAME_VERSION (arg0));
+ bitmap_set_bit (exprs_maybe_dce, SSA_NAME_VERSION (arg1));
+ gsi = gsi_for_stmt (phi);
+ remove_phi_node (&gsi, false);
+ simple_dce_from_worklist (exprs_maybe_dce);
+
+ statistics_counter_event (cfun, "double-word clz/ctz combined", 1);
+ return true;
+}
+
/* Optimize x ? __builtin_fun (x) : C, where C is __builtin_fun (0).
Convert
@@ -4497,6 +4756,10 @@ pass_phiopt::execute (function *)
&& !diamond_p
&& spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
cfgchanged = true;
+ else if (diamond_p
+ && clzctz_combine_replacement (bb, bb1, bb2, e1, e2, phi,
+ arg0, arg1))
+ cfgchanged = true;
};
execute_over_cond_phis (phiopt_exec);
--
2.50.1 (Apple Git-155)
