From: Kyrylo Tkachov <[email protected]>
Counts of trailing and leading zeros of a double-word X are often
computed from its halves LO and HI:
LO != 0 ? ctz (LO) : 32 + ctz (HI)
HI != 0 ? clz (HI) : 32 + clz (LO)
GCC keeps the branch and the two narrow counts, although one count of X
gives the same result for a nonzero X. On aarch64
unsigned
ctz64_split (uint64_t val)
{
uint32_t hi = val >> 32, lo = val;
return lo ? __builtin_ctz (lo) : 32u + __builtin_ctz (hi);
}
compiles to eight instructions with two rbit and clz pairs and a csel.
Add a match.pd pattern for the COND_EXPR that phiopt builds for the PHI.
The halves are (N) X and (N) (X >> W), the test can also be
X & (2^W - 1) or X >> W, and the counts can be converted. The counts of
the halves are undefined at zero, so a one-argument .CTZ or .CLZ of X
replaces them. phiopt removes both arms, although they have several
statements:
_1 = val_6(D) >> 32;
hi_7 = (uint32_t) _1;
lo_8 = (uint32_t) val_6(D);
if (lo_8 != 0) goto <bb 3>; else goto <bb 4>;
<bb 3>:
_2 = __builtin_ctz (lo_8);
_10 = (unsigned int) _2;
goto <bb 5>;
<bb 4>:
_3 = __builtin_ctz (hi_7);
_4 = (unsigned int) _3;
_9 = _4 + 32;
<bb 5>:
# _5 = PHI <_9(4), _10(3)>
becomes
_12 = .CTZ (val_6(D));
_13 = (unsigned int) _12;
which is rbit and clz on aarch64.
The idiom is often in a small inline function. After inlining, jump
threading can copy a test of the count into the arms, and then late
phiopt no longer sees the two counts. So allow counts in early phiopt.
Then early phiopt also folds the select of the _BitInt count in
phi-opt-63.c.
Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux.
Cc: Andrea Pinski <[email protected]>
gcc/ChangeLog:
PR tree-optimization/126035
* match.pd (double_word_low, double_word_high)
(double_word_low_test, double_word_high_test, ctz_nonzero)
(clz_nonzero): New predicates.
(LO != 0 ? ctz (LO) : W + ctz (HI) -> ctz (X)): New pattern.
(HI != 0 ? clz (HI) : W + clz (LO) -> clz (X)): Likewise.
* tree-ssa-phiopt.cc (phiopt_early_allow): Allow counts of
leading and trailing zeros, possibly converted.
gcc/testsuite/ChangeLog:
PR tree-optimization/126035
* gcc.dg/torture/pr126035-1.c: New test.
* gcc.dg/torture/pr126035-2.c: New test.
* gcc.dg/tree-ssa/phi-opt-63.c: Expect phiopt1 to remove both
branches.
* gcc.dg/tree-ssa/pr126035-1.c: New test.
* gcc.dg/tree-ssa/pr126035-2.c: New test.
* gcc.dg/tree-ssa/pr126035-3.c: New test.
* gcc.dg/tree-ssa/pr126035-4.c: New test.
* gcc.target/aarch64/pr126035-1.c: New test.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
gcc/match.pd | 64 ++++++++
gcc/testsuite/gcc.dg/torture/pr126035-1.c | 142 ++++++++++++++++++
gcc/testsuite/gcc.dg/torture/pr126035-2.c | 12 ++
gcc/testsuite/gcc.dg/tree-ssa/phi-opt-63.c | 4 +-
gcc/testsuite/gcc.dg/tree-ssa/pr126035-1.c | 89 +++++++++++
gcc/testsuite/gcc.dg/tree-ssa/pr126035-2.c | 69 +++++++++
gcc/testsuite/gcc.dg/tree-ssa/pr126035-3.c | 63 ++++++++
gcc/testsuite/gcc.dg/tree-ssa/pr126035-4.c | 31 ++++
gcc/testsuite/gcc.target/aarch64/pr126035-1.c | 48 ++++++
gcc/tree-ssa-phiopt.cc | 13 +-
10 files changed, 532 insertions(+), 3 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/torture/pr126035-1.c
create mode 100644 gcc/testsuite/gcc.dg/torture/pr126035-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126035-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126035-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126035-3.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126035-4.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr126035-1.c
diff --git a/gcc/match.pd b/gcc/match.pd
index 6d037daa991..d07c555baa6 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -11838,6 +11838,70 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
}
(if (ifn == IFN_CTZ && tree_int_cst_equal (@2, uniform_integer_cst_p (@4)))
(IFN_CTZ @3 @2)))))
+
+/* The low half (N) @0 and the high half (N) (@0 >> W) of a double-word
+ integer @0, where N has precision W, half the precision of @0. */
+(match (double_word_low @0)
+ (convert @0)
+ (if (INTEGRAL_TYPE_P (type)
+ && INTEGRAL_TYPE_P (TREE_TYPE (@0))
+ && TYPE_PRECISION (TREE_TYPE (@0)) == 2 * TYPE_PRECISION (type))))
+(match (double_word_high @0)
+ (convert (rshift (nop_convert? @0) INTEGER_CST@1))
+ (if (INTEGRAL_TYPE_P (type)
+ && INTEGRAL_TYPE_P (TREE_TYPE (@0))
+ && TYPE_PRECISION (TREE_TYPE (@0)) == 2 * TYPE_PRECISION (type)
+ && wi::to_widest (@1) == TYPE_PRECISION (type))))
+
+/* A value that is zero exactly when the low half of the double-word
+ integer @0 is zero: the low half or @0 & (2^W - 1). */
+(match (double_word_low_test @0)
+ (convert @0)
+ (if (INTEGRAL_TYPE_P (type)
+ && INTEGRAL_TYPE_P (TREE_TYPE (@0))
+ && TYPE_PRECISION (TREE_TYPE (@0)) == 2 * TYPE_PRECISION (type))))
+(match (double_word_low_test @0)
+ (bit_and @0 INTEGER_CST@1)
+ (if (INTEGRAL_TYPE_P (type)
+ && wi::to_wide (@1) == wi::mask (TYPE_PRECISION (type) / 2, false,
+ TYPE_PRECISION (type)))))
+
+/* A value that is zero exactly when the high half of the double-word
+ integer @0 is zero: @0 >> W, possibly converted to W or more bits. */
+(match (double_word_high_test @0)
+ (convert1? (rshift (nop_convert? @0) INTEGER_CST@1))
+ (if (INTEGRAL_TYPE_P (type)
+ && INTEGRAL_TYPE_P (TREE_TYPE (@0))
+ && 2 * wi::to_widest (@1) == TYPE_PRECISION (TREE_TYPE (@0))
+ && TYPE_PRECISION (type) >= wi::to_widest (@1))))
+
+/* Counts of the trailing and leading zeros of @0 that are exact for a
+ nonzero @0. */
+(match (ctz_nonzero @0)
+ (CTZ @0))
+(match (clz_nonzero @0)
+ (CLZ @0))
+
+/* LO != 0 ? ctz (LO) : W + ctz (HI) is ctz (X) for a nonzero X, where LO
+ and HI are the low and high halves of the double-word integer X and W
+ is their precision. Likewise HI != 0 ? clz (HI) : W + clz (LO) is
+ clz (X). */
+(for cnt (ctz_nonzero clz_nonzero)
+ tst (double_word_low_test double_word_high_test)
+ nzh (double_word_low double_word_high)
+ zh (double_word_high double_word_low)
+ ifn (IFN_CTZ IFN_CLZ)
+ (simplify
+ (cond (ne (tst @0) integer_zerop)
+ (convert1? (cnt (nzh @0)))
+ (plus (convert? (cnt (zh@1 @0))) INTEGER_CST@2))
+ (with { int w = TYPE_PRECISION (TREE_TYPE (@1)); }
+ (if (wi::to_widest (@2) == w && 2 * w <= MAX_FIXED_MODE_SIZE)
+ (with { tree utype = build_nonstandard_integer_type (2 * w, 1); }
+ (if (type_has_mode_precision_p (utype)
+ && direct_internal_fn_supported_p (as_internal_fn (ifn), utype,
+ OPTIMIZE_FOR_BOTH))
+ (convert (ifn:integer_type_node (convert:utype @0)))))))))
#endif
/* Common POPCOUNT/PARITY simplifications. */
diff --git a/gcc/testsuite/gcc.dg/torture/pr126035-1.c
b/gcc/testsuite/gcc.dg/torture/pr126035-1.c
new file mode 100644
index 00000000000..378403e9bfb
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr126035-1.c
@@ -0,0 +1,142 @@
+/* PR tree-optimization/126035 */
+/* { dg-do run } */
+/* { dg-require-effective-target int32plus } */
+
+/* Check the combined counts of a double-word value against the
+ double-word builtins, and that near misses keep their own value. */
+
+typedef __UINT64_TYPE__ U64;
+typedef __UINT32_TYPE__ U32;
+typedef __INT64_TYPE__ S64;
+
+#define N __attribute__((noipa))
+
+N unsigned
+ctz1 (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ return lo ? __builtin_ctz (lo) : 32 + __builtin_ctz (hi);
+}
+
+N int
+ctz2 (S64 x)
+{
+ int lo = x, hi = (U64) x >> 32;
+ return lo ? __builtin_ctz (lo) : 32 | __builtin_ctz (hi);
+}
+
+N unsigned char
+ctz3 (U64 x)
+{
+ return ((x & 0xffffffff) ? (unsigned char) __builtin_ctz ((U32) x)
+ : (unsigned char) (32 + __builtin_ctz ((U32) (x >> 32))));
+}
+
+/* A named intermediate: with -g its debug bind is at the merge. */
+N unsigned
+ctz4 (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ unsigned r;
+ if (lo)
+ r = __builtin_ctz (lo);
+ else
+ r = 32 + __builtin_ctz (hi);
+ return r;
+}
+
+N unsigned
+clz1 (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ return hi ? __builtin_clz (hi) : 32 + __builtin_clz (lo);
+}
+
+N long
+clz2 (S64 x)
+{
+ if ((x >> 32) == 0)
+ return 32 + __builtin_clz ((U32) x);
+ return __builtin_clz ((U32) (x >> 32));
+}
+
+/* A third path into the merge keeps its value. */
+N unsigned
+extra (U64 x, int c, unsigned other)
+{
+ unsigned r;
+ U32 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;
+}
+
+/* The count of the high half is truncated by a narrow signed
+ intermediate before the offset is added. */
+struct S { signed int c : 4; };
+
+N unsigned
+narrow (U64 x)
+{
+ struct S s;
+ U32 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;
+}
+
+/* Wrong offset. */
+N unsigned
+wrong (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ return lo ? __builtin_ctz (lo) : 31 + __builtin_ctz (hi);
+}
+
+int
+main (void)
+{
+ U64 v = 0x9E3779B97F4A7C15ULL;
+ for (int i = 0; i < 100000; 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;
+ unsigned t = __builtin_ctzll (x), l = __builtin_clzll (x);
+ if (ctz1 (x) != t || ctz2 (x) != (int) t || ctz3 (x) != t
+ || ctz4 (x) != t || clz1 (x) != l || clz2 (x) != l
+ || extra (x, 0, 77) != t)
+ __builtin_abort ();
+ if ((U32) x == 0 && wrong (x) != t - 1)
+ __builtin_abort ();
+ }
+ if (extra (4, 1, 77) != 77)
+ __builtin_abort ();
+ /* ctz (hi) == 20 is truncated to 4 in the 4-bit field: 36, not 52. */
+ if (narrow (1ULL << 52) != 36)
+ __builtin_abort ();
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/torture/pr126035-2.c
b/gcc/testsuite/gcc.dg/torture/pr126035-2.c
new file mode 100644
index 00000000000..1e0d34d3655
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr126035-2.c
@@ -0,0 +1,12 @@
+/* PR tree-optimization/126035 */
+/* { dg-do compile { target bitint65535 } } */
+/* { dg-options "-std=c23" } */
+
+/* The double-word value is wider than any mode with a count. */
+
+int
+f (unsigned _BitInt(1024) x)
+{
+ unsigned _BitInt(512) lo = x, hi = x >> 512;
+ return lo ? __builtin_ctzg (lo) : 512 + __builtin_ctzg (hi);
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-63.c
b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-63.c
index e0f7facaa7f..8c6797bef3e 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-63.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-63.c
@@ -21,5 +21,5 @@ g (signed _BitInt(192) x)
return r;
}
-/* { dg-final { scan-tree-dump-times "to straightline code" 1 "phiopt1" } } */
-/* { dg-final { scan-tree-dump-times "to straightline code" 1 "phiopt2" } } */
+/* { dg-final { scan-tree-dump-times "to straightline code" 2 "phiopt1" } } */
+/* { dg-final { scan-tree-dump-not "to straightline code" "phiopt2" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr126035-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr126035-1.c
new file mode 100644
index 00000000000..0177e57089f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr126035-1.c
@@ -0,0 +1,89 @@
+/* PR tree-optimization/126035 */
+/* { dg-do compile { target aarch64*-*-* i?86-*-* x86_64-*-* } } */
+/* { dg-require-effective-target lp64 } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Counts of trailing and leading zeros of a double-word value that are
+ computed from its halves are combined into one count. */
+
+typedef __UINT64_TYPE__ U64;
+typedef __UINT32_TYPE__ U32;
+typedef __INT64_TYPE__ S64;
+
+unsigned
+ctz1 (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ return lo ? __builtin_ctz (lo) : 32 + __builtin_ctz (hi);
+}
+
+unsigned
+ctz2 (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ if (lo == 0)
+ return 32 + __builtin_ctz (hi);
+ return __builtin_ctz (lo);
+}
+
+unsigned
+ctz3 (U64 x)
+{
+ return ((x & 0xffffffff) ? __builtin_ctz ((U32) x)
+ : 32 + __builtin_ctz ((U32) (x >> 32)));
+}
+
+int
+ctz4 (S64 x)
+{
+ int lo = x, hi = x >> 32;
+ return lo ? __builtin_ctz (lo) : 32 + __builtin_ctz (hi);
+}
+
+unsigned long long
+ctz5 (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ return (lo ? (unsigned long long) __builtin_ctz (lo)
+ : 32 + (unsigned long long) __builtin_ctz (hi));
+}
+
+int
+ctz6 (S64 x)
+{
+ U32 lo = x, hi = (U64) x >> 32;
+ return lo ? __builtin_ctz (lo) : 32 + __builtin_ctz (hi);
+}
+
+unsigned
+clz1 (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ return hi ? __builtin_clz (hi) : 32 + __builtin_clz (lo);
+}
+
+unsigned
+clz2 (U64 x)
+{
+ if ((x >> 32) == 0)
+ return 32 + __builtin_clz ((U32) x);
+ return __builtin_clz ((U32) (x >> 32));
+}
+
+int
+clz3 (S64 x)
+{
+ int lo = x, hi = x >> 32;
+ return hi ? __builtin_clz (hi) : 32 + __builtin_clz (lo);
+}
+
+int
+clz4 (S64 x)
+{
+ U32 lo = x, hi = (U64) x >> 32;
+ return hi ? __builtin_clz (hi) : 32 + __builtin_clz (lo);
+}
+
+/* { dg-final { scan-tree-dump-not "__builtin_c\[lt\]z " "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\.CTZ \\(" 6 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\.CLZ \\(" 4 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr126035-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr126035-2.c
new file mode 100644
index 00000000000..f76342cfbbc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr126035-2.c
@@ -0,0 +1,69 @@
+/* PR tree-optimization/126035 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Forms that do not compute the count of a double-word value must not be
+ combined. */
+
+typedef __UINT64_TYPE__ U64;
+typedef __UINT32_TYPE__ U32;
+
+/* Wrong offset. */
+unsigned
+f1 (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ return lo ? __builtin_ctz (lo) : 31 + __builtin_ctz (hi);
+}
+
+/* The condition tests the wrong half. */
+unsigned
+f2 (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ return hi ? __builtin_ctz (lo) : 32 + __builtin_ctz (hi);
+}
+
+/* The condition tests only part of the high half. */
+unsigned
+f3 (U64 x)
+{
+ unsigned char t = x >> 32;
+ return t ? __builtin_clz ((U32) (x >> 32)) : 32 + __builtin_clz ((U32) x);
+}
+
+/* The count of the high half wraps around. */
+unsigned
+f4 (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ return lo ? __builtin_ctz (lo) : (32 + __builtin_ctz (hi)) & 31;
+}
+
+/* The IOR overlaps the count. */
+unsigned
+f5 (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ return lo ? __builtin_ctz (lo) : 16 | __builtin_ctz (hi);
+}
+
+/* The high half is narrower than half of X. */
+unsigned
+f6 (U64 x)
+{
+ U32 lo = x;
+ unsigned short hi = x >> 32;
+ return lo ? __builtin_ctz (lo) : 32 + __builtin_ctz (hi);
+}
+
+/* Counts of leading zeros of the halves in the order of ctz. */
+unsigned
+f7 (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ return lo ? __builtin_clz (lo) : 32 + __builtin_clz (hi);
+}
+
+/* { dg-final { scan-tree-dump-not "\\.CTZ \\(" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "\\.CLZ \\(" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr126035-3.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr126035-3.c
new file mode 100644
index 00000000000..e975ba5dbea
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr126035-3.c
@@ -0,0 +1,63 @@
+/* PR tree-optimization/126035 */
+/* { dg-do compile { target aarch64*-*-* i?86-*-* x86_64-*-* } } */
+/* { dg-require-effective-target lp64 } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Early phiopt combines the split counts in the out-of-line bodies before
+ inlining. After inlining, jump threading copies the test of the result
+ into the arms and late phiopt no longer sees the two counts. */
+
+typedef __UINT64_TYPE__ U64;
+typedef __UINT32_TYPE__ U32;
+
+static inline int
+ctz64 (U64 val)
+{
+ U32 msw = val >> 32, lsw = val;
+ if (lsw == 0)
+ return 32 + __builtin_ctz (msw);
+ return __builtin_ctz (lsw);
+}
+
+static inline int
+clz64 (U64 val)
+{
+ U32 msw = val >> 32, lsw = val;
+ if (msw == 0)
+ return 32 + __builtin_clz (lsw);
+ return __builtin_clz (msw);
+}
+
+static inline unsigned char
+ctz64_uc (U64 val)
+{
+ U32 msw = val >> 32, lsw = val;
+ if (lsw == 0)
+ return 32 + (unsigned char) __builtin_ctz (msw);
+ return __builtin_ctz (lsw);
+}
+
+int
+f1 (U64 d)
+{
+ int l = ctz64 (d);
+ return l > 40 ? 0 : l;
+}
+
+int
+f2 (U64 d)
+{
+ int l = clz64 (d);
+ return l > 40 ? 0 : l;
+}
+
+int
+f3 (U64 d)
+{
+ int l = ctz64_uc (d);
+ return l > 40 ? 0 : l;
+}
+
+/* { dg-final { scan-tree-dump-not "__builtin_c\[lt\]z " "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\.CTZ \\(" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\.CLZ \\(" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr126035-4.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr126035-4.c
new file mode 100644
index 00000000000..ee41a90828d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr126035-4.c
@@ -0,0 +1,31 @@
+/* PR tree-optimization/126035 */
+/* { dg-do compile { target aarch64*-*-* i?86-*-* x86_64-*-* } } */
+/* { dg-require-effective-target lp64 } */
+/* { dg-options "-O2 -g -fdump-tree-phiopt1" } */
+
+/* Both arms of the diamond are removed and their debug binds are reset,
+ so that WHICH does not get the value of one arm on both paths. */
+
+typedef __UINT64_TYPE__ U64;
+typedef __UINT32_TYPE__ U32;
+
+unsigned
+f (U64 x)
+{
+ U32 lo = x, hi = x >> 32;
+ unsigned which, r;
+ if (lo != 0)
+ {
+ which = 111;
+ r = __builtin_ctz (lo);
+ }
+ else
+ {
+ which = hi;
+ r = 32 + __builtin_ctz (hi);
+ }
+ return r;
+}
+
+/* { dg-final { scan-tree-dump "\\.CTZ \\(" "phiopt1" } } */
+/* { dg-final { scan-tree-dump-not "which => \[^N\]" "phiopt1" } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/pr126035-1.c
b/gcc/testsuite/gcc.target/aarch64/pr126035-1.c
new file mode 100644
index 00000000000..c138d554df3
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr126035-1.c
@@ -0,0 +1,48 @@
+/* PR tree-optimization/126035 */
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+#pragma GCC target "+nocssc"
+
+typedef __UINT64_TYPE__ uint64_t;
+typedef __UINT32_TYPE__ uint32_t;
+
+static inline unsigned
+ctz32 (uint32_t v)
+{
+ return __builtin_ctz (v);
+}
+
+static inline unsigned
+clz32 (uint32_t v)
+{
+ return __builtin_clz (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);
+}
+
+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);
+}
+
+const unsigned char *
+match_extend (const unsigned char *p, uint64_t x)
+{
+ return p + (ctz64_split (x) >> 3);
+}
+
+/* One double-word rbit + clz for each ctz and one clz for the clz, with
+ no conditional select. */
+/* { dg-final { scan-assembler-not {\tcsel\t} } } */
+/* { dg-final { scan-assembler-times {\trbit\tx[0-9]+, x[0-9]+} 2 } } */
+/* { dg-final { scan-assembler-times {\tclz\tx[0-9]+, x[0-9]+} 3 } } */
diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index f3ab9fdac96..91f0d331b40 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -682,10 +682,21 @@ factor_out_conditional_operation (edge e0, edge e1,
basic_block merge,
/* Return TRUE if SEQ/OP pair should be allowed during early phiopt.
- Currently this is to allow MIN/MAX and ABS/NEGATE and constants. */
+ Currently this is to allow MIN/MAX and ABS/NEGATE, constants and
+ counts of leading or trailing zeros. */
static bool
phiopt_early_allow (gimple_seq &seq, gimple_match_op &op)
{
+ /* Allow a count of leading or trailing zeros, possibly converted. */
+ if (op.code == CFN_CLZ || op.code == CFN_CTZ)
+ return true;
+ if (op.code == NOP_EXPR)
+ for (gimple_stmt_iterator gsi = gsi_start (seq); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ if (gimple_call_internal_p (gsi_stmt (gsi), IFN_CLZ)
+ || gimple_call_internal_p (gsi_stmt (gsi), IFN_CTZ))
+ return true;
+
/* Don't allow functions. */
if (!op.code.is_tree_code ())
return false;
--
2.54.0 (Apple Git-157)
