From: Kyrylo Tkachov <[email protected]>
A two-argument .CLZ (x, V) or .CTZ (x, V) is valid only if V is the
value of the target at zero, because the expansion ignores V. Ranger,
match.pd and fold_const_call use V as the result for zero. Calls with
another V reach the expansion in three cases:
- The host makes such calls before offload streaming. The C front end
folds __builtin_clzg (x, 32) to .CLZ (x, 32), and forwprop1 creates
table based counts. gcn defines -1 at zero, and the amdgcn offload
compiler expands .CTZ (x, 32) to s_ff1_i32_b32, which gives -1 for 0.
- With x86 target_clones, a TU with -mlzcnt folds
__builtin_clzg (x, 32) to .CLZ (x, 32). The arch=x86-64 clone
expands it to bsr with no zero test, so f (0) does not return 32.
- match.pd and phiopt fold x != 0 ? .CTZ (x) : CST to .CTZ (x, CST)
for any CST if X is a _BitInt, because bitint lowering implements
the second argument. It does this only for _BitInt wider than
MAX_FIXED_MODE_SIZE. With an unsigned _BitInt(64) X,
return x ? tab[((x & -x) * 0x03f79d71b4cb0a89uwb) >> 58] : 32;
does not return 32 for a zero X on aarch64 and x86_64.
Jakub proposed in PR111280 comment 4 to compare V with the value
of the target at expansion, and to test the argument against 0 if they
differ. Richard Biener agreed in comment 6. Do this for scalar calls
in the new function expand_clz_ctz. Since r17-5047 the vectorizer
creates vector calls only with the value of the target for the vector
mode, so assert that for vector calls. When the first argument is
constant, fold the call with both arguments.
On AArch64 at -O2,
_1 = .CLZ (x_2(D), 5);
now expands to
clz w1, w0
cmp w0, 0
mov w0, 5
csel w0, w1, w0, ne
instead of a single clz. .CLZ (x_2(D), 32) is still a single clz.
Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux.
Cc: Jakub Jelinek <[email protected]>
gcc/ChangeLog:
PR tree-optimization/111280
* doc/ifn.texi (IFN_CLZ, IFN_CTZ): Document the second argument
for scalar and vector calls.
* internal-fn.cc (expand_bitquery): Use both arguments to fold a
two-argument .CLZ or .CTZ of a constant.
(expand_clz_ctz): New function.
(expand_CLZ, expand_CTZ): Use it.
gcc/testsuite/ChangeLog:
PR tree-optimization/111280
* gcc.dg/torture/bitint-111.c: New test.
* gcc.dg/torture/clz-ctz-value-at-zero-1.c: New test.
* gcc.target/aarch64/clz-ctz-value-at-zero-1.c: New test.
* gcc.target/i386/clzg-target-clones-1.c: New test.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
gcc/doc/ifn.texi | 20 ++-
gcc/internal-fn.cc | 55 +++++-
gcc/testsuite/gcc.dg/torture/bitint-111.c | 62 +++++++
.../gcc.dg/torture/clz-ctz-value-at-zero-1.c | 157 ++++++++++++++++++
.../aarch64/clz-ctz-value-at-zero-1.c | 61 +++++++
.../gcc.target/i386/clzg-target-clones-1.c | 20 +++
6 files changed, 364 insertions(+), 11 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/torture/bitint-111.c
create mode 100644 gcc/testsuite/gcc.dg/torture/clz-ctz-value-at-zero-1.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/clz-ctz-value-at-zero-1.c
create mode 100644 gcc/testsuite/gcc.target/i386/clzg-target-clones-1.c
diff --git a/gcc/doc/ifn.texi b/gcc/doc/ifn.texi
index d80e089685a..afe8a977f70 100644
--- a/gcc/doc/ifn.texi
+++ b/gcc/doc/ifn.texi
@@ -1088,18 +1088,26 @@ instruction pattern for integer and integer vector
modes.
@cindex @code{IFN_CLZ} internal function
@item @samp{IFN_CLZ}
The @code{IFN_CLZ} internal function directly maps to the @code{clz}
-instruction pattern for integer and integer vector modes. In case the value
-for zero is defined, then this is recorded in the optional second argument.
+instruction pattern for integer and integer vector modes. The optional
+second argument is an @code{int} constant that gives the result for zero.
Note, this is always a scalar value even for vector modes where it represents
-the scalar value of a lane.
+the scalar value of a lane. For a scalar call it can be any value. If the
+instruction gives another value for zero, the expansion compares the first
+argument with zero. For a vector call it must be the value for which
+@code{CLZ_DEFINED_VALUE_AT_ZERO} returns 2 for the vector mode. Without
+the second argument the result for zero is undefined.
@cindex @code{IFN_CTZ} internal function
@item @samp{IFN_CTZ}
The @code{IFN_CTZ} internal function directly maps to the @code{ctz}
-instruction pattern for integer and integer vector modes. In case the value
-for zero is defined, then this is recorded in the optional second argument.
+instruction pattern for integer and integer vector modes. The optional
+second argument is an @code{int} constant that gives the result for zero.
Note, this is always a scalar value even for vector modes where it represents
-the scalar value of a lane.
+the scalar value of a lane. For a scalar call it can be any value. If the
+instruction gives another value for zero, the expansion compares the first
+argument with zero. For a vector call it must be the value for which
+@code{CTZ_DEFINED_VALUE_AT_ZERO} returns 2 for the vector mode. Without
+the second argument the result for zero is undefined.
@cindex @code{IFN_FFS} internal function
@item @samp{IFN_FFS}
diff --git a/gcc/internal-fn.cc b/gcc/internal-fn.cc
index 45ad08d2cf6..a05991f087d 100644
--- a/gcc/internal-fn.cc
+++ b/gcc/internal-fn.cc
@@ -5764,7 +5764,13 @@ expand_bitquery (internal_fn fn, gcall *stmt)
tree arg = gimple_call_arg (stmt, 0);
if (TREE_CODE (arg) == INTEGER_CST)
{
- tree ret = fold_const_call (as_combined_fn (fn), TREE_TYPE (arg), arg);
+ tree ret;
+ /* A second argument of IFN_CLZ or IFN_CTZ is the result for zero. */
+ if ((fn == IFN_CLZ || fn == IFN_CTZ) && gimple_call_num_args (stmt) == 2)
+ ret = fold_const_call (as_combined_fn (fn), TREE_TYPE (lhs), arg,
+ gimple_call_arg (stmt, 1));
+ else
+ ret = fold_const_call (as_combined_fn (fn), TREE_TYPE (arg), arg);
gcc_checking_assert (ret && TREE_CODE (ret) == INTEGER_CST);
expand_assignment (lhs, ret, false);
return false;
@@ -5779,18 +5785,57 @@ expand_CLRSB (internal_fn fn, gcall *stmt)
expand_unary_optab_fn (fn, stmt, clrsb_optab);
}
+/* Expand STMT, a call to the IFN_CLZ or IFN_CTZ internal function FN,
+ using OPTAB. The optional second argument of STMT is the result for a
+ zero first argument. For a scalar call, if the instruction can give
+ another value for zero, test the first argument for zero and set the
+ result to the second argument. */
+
+static void
+expand_clz_ctz (internal_fn fn, gcall *stmt, direct_optab optab)
+{
+ if (!expand_bitquery (fn, stmt))
+ return;
+ tree arg = gimple_call_arg (stmt, 0);
+ machine_mode mode = TYPE_MODE (TREE_TYPE (arg));
+ rtx op0 = NULL_RTX;
+ if (gimple_call_num_args (stmt) == 2)
+ {
+ int val;
+ int defined = (fn == IFN_CLZ
+ ? CLZ_DEFINED_VALUE_AT_ZERO (mode, val)
+ : CTZ_DEFINED_VALUE_AT_ZERO (mode, val));
+ bool target_val_p = (defined == 2
+ && wi::to_widest (gimple_call_arg (stmt, 1)) == val);
+ /* The vectorizer creates vector calls only with the value of the
+ target. */
+ gcc_checking_assert (target_val_p || !VECTOR_TYPE_P (TREE_TYPE (arg)));
+ if (!target_val_p)
+ /* Copy the argument because the count can overwrite its register. */
+ op0 = copy_to_mode_reg (mode, expand_normal (arg));
+ }
+ expand_unary_optab_fn (fn, stmt, optab);
+ if (!op0)
+ return;
+ rtx_code_label *done = gen_label_rtx ();
+ emit_cmp_and_jump_insns (op0, const0_rtx, NE, NULL_RTX, mode, true, done,
+ profile_probability::likely ());
+ tree lhs = gimple_call_lhs (stmt);
+ expand_assignment (lhs, fold_convert (TREE_TYPE (lhs),
+ gimple_call_arg (stmt, 1)), false);
+ emit_label (done);
+}
+
void
expand_CLZ (internal_fn fn, gcall *stmt)
{
- if (expand_bitquery (fn, stmt))
- expand_unary_optab_fn (fn, stmt, clz_optab);
+ expand_clz_ctz (fn, stmt, clz_optab);
}
void
expand_CTZ (internal_fn fn, gcall *stmt)
{
- if (expand_bitquery (fn, stmt))
- expand_unary_optab_fn (fn, stmt, ctz_optab);
+ expand_clz_ctz (fn, stmt, ctz_optab);
}
void
diff --git a/gcc/testsuite/gcc.dg/torture/bitint-111.c
b/gcc/testsuite/gcc.dg/torture/bitint-111.c
new file mode 100644
index 00000000000..4d4dab67b89
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/bitint-111.c
@@ -0,0 +1,62 @@
+/* { dg-do run { target bitint } } */
+/* { dg-options "-std=c23 -pedantic-errors" } */
+
+/* Counts of _BitInt not wider than MAX_FIXED_MODE_SIZE are expanded like
+ counts of other integers, also with a value at zero that the target
+ does not produce. */
+
+#if __BITINT_MAXWIDTH__ >= 64
+typedef unsigned _BitInt(64) U64;
+typedef signed _BitInt(64) S64;
+typedef unsigned _BitInt(32) U32;
+
+static const unsigned char tab64[64] = {
+ 0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4,
+ 62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5,
+ 63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11,
+ 46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6 };
+
+static const unsigned char clztab[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 };
+
+[[gnu::noipa]] int
+f (U64 x)
+{
+ return x ? tab64[((x & -x) * 0x03f79d71b4cb0a89uwb) >> 58] : 32;
+}
+
+/* The test is on the signed value, the count on the unsigned one. */
+[[gnu::noipa]] int
+g (S64 x)
+{
+ U64 u = x;
+ return x ? tab64[((u & -u) * 0x03f79d71b4cb0a89uwb) >> 58] : 32;
+}
+
+[[gnu::noipa]] int
+h (U32 x)
+{
+ U32 v = x;
+ v |= v >> 1;
+ v |= v >> 2;
+ v |= v >> 4;
+ v |= v >> 8;
+ v |= v >> 16;
+ return x ? 31 - clztab[(v * 0x07C4ACDDuwb) >> 27] : 5;
+}
+#endif
+
+int
+main ()
+{
+#if __BITINT_MAXWIDTH__ >= 64
+ if (f (0) != 32 || f (8) != 3 || f ((U64) 1 << 63) != 63)
+ __builtin_abort ();
+ if (g (0) != 32 || g (-4) != 2)
+ __builtin_abort ();
+ if (h (0) != 5 || h (1) != 31 || h ((U32) 1 << 31) != 0)
+ __builtin_abort ();
+#endif
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/torture/clz-ctz-value-at-zero-1.c
b/gcc/testsuite/gcc.dg/torture/clz-ctz-value-at-zero-1.c
new file mode 100644
index 00000000000..c2dddaa1097
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/clz-ctz-value-at-zero-1.c
@@ -0,0 +1,157 @@
+/* Two-argument .CLZ and .CTZ give their second argument for zero, also
+ when the instruction of the target gives another value. */
+/* { dg-do run } */
+/* { dg-require-effective-target int32 } */
+/* { dg-require-effective-target clz_ifn } */
+/* { dg-require-effective-target ctz_ifn } */
+/* { dg-additional-options "-fgimple" } */
+
+int __GIMPLE (ssa) __attribute__((noipa))
+clz5 (unsigned int x)
+{
+ int _1;
+
+ __BB(2):
+ _1 = .CLZ (x_2(D), 5);
+ return _1;
+}
+
+int __GIMPLE (ssa) __attribute__((noipa))
+ctzm7 (unsigned int x)
+{
+ int _1;
+
+ __BB(2):
+ _1 = .CTZ (x_2(D), -7);
+ return _1;
+}
+
+int __GIMPLE (ssa) __attribute__((noipa))
+ctz5eq32 (unsigned int x)
+{
+ int _1;
+ _Bool _3;
+ int _4;
+
+ __BB(2):
+ _1 = .CTZ (x_2(D), 5);
+ _3 = _1 == 32;
+ _4 = (int) _3;
+ return _4;
+}
+
+int __GIMPLE (ssa) __attribute__((noipa))
+clzconst (void)
+{
+ int _1;
+
+ __BB(2):
+ _1 = .CLZ (0u, 5);
+ return _1;
+}
+
+int __GIMPLE (ssa) __attribute__((noipa))
+clzand (unsigned int a, unsigned int b)
+{
+ unsigned int _3;
+ int _4;
+
+ __BB(2):
+ _3 = a_1(D) & b_2(D);
+ _4 = .CLZ (_3, 5);
+ return _4;
+}
+
+int __GIMPLE (ssa) __attribute__((noipa))
+ctztab (unsigned int x)
+{
+ int _1;
+ int _2;
+
+ __BB(2):
+ _1 = .CTZ (x_3(D), 32);
+ _2 = _1 & 31;
+ return _2;
+}
+
+int __GIMPLE (ssa) __attribute__((noipa))
+clz32 (unsigned int x)
+{
+ int _1;
+
+ __BB(2):
+ _1 = .CLZ (x_2(D), 32);
+ return _1;
+}
+
+/* The MIN of .CLZ (0, -1) and .CLZ (5, -1) is -1. */
+
+int __GIMPLE (ssa) __attribute__((noipa))
+minclzm1 (unsigned int x, unsigned int y)
+{
+ int _1;
+ int _2;
+ int _3;
+
+ __BB(2):
+ _1 = .CLZ (x_4(D), -1);
+ _2 = .CLZ (y_5(D), -1);
+ _3 = __MIN (_1, _2);
+ return _3;
+}
+
+/* .CTZ (0, -1) is -1, which is smaller than 3 and not equal to 3. */
+
+int __GIMPLE (ssa) __attribute__((noipa))
+ctzgem1 (unsigned int x)
+{
+ int _1;
+ _Bool _2;
+ int _3;
+
+ __BB(2):
+ _1 = .CTZ (x_4(D), -1);
+ _2 = _1 >= 3;
+ _3 = (int) _2;
+ return _3;
+}
+
+int __GIMPLE (ssa) __attribute__((noipa))
+ctzeqm1 (unsigned int x)
+{
+ int _1;
+ _Bool _2;
+ int _3;
+
+ __BB(2):
+ _1 = .CTZ (x_4(D), -1);
+ _2 = _1 == 3;
+ _3 = (int) _2;
+ return _3;
+}
+
+int
+main (void)
+{
+ if (clz5 (0) != 5 || clz5 (1) != 31 || clz5 (0x80000000u) != 0)
+ __builtin_abort ();
+ if (ctzm7 (0) != -7 || ctzm7 (8) != 3)
+ __builtin_abort ();
+ if (ctz5eq32 (0) != 0 || ctz5eq32 (1) != 0)
+ __builtin_abort ();
+ if (clzconst () != 5)
+ __builtin_abort ();
+ if (clzand (0xf0, 0x0f) != 5 || clzand (3, 1) != 31)
+ __builtin_abort ();
+ if (ctztab (0) != 0 || ctztab (8) != 3)
+ __builtin_abort ();
+ if (clz32 (0) != 32 || clz32 (1) != 31)
+ __builtin_abort ();
+ if (minclzm1 (0, 5) != -1 || minclzm1 (4, 5) != 29)
+ __builtin_abort ();
+ if (ctzgem1 (0) != 0 || ctzgem1 (8) != 1 || ctzgem1 (4) != 0)
+ __builtin_abort ();
+ if (ctzeqm1 (0) != 0 || ctzeqm1 (8) != 1)
+ __builtin_abort ();
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.target/aarch64/clz-ctz-value-at-zero-1.c
b/gcc/testsuite/gcc.target/aarch64/clz-ctz-value-at-zero-1.c
new file mode 100644
index 00000000000..466d9757aef
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/clz-ctz-value-at-zero-1.c
@@ -0,0 +1,61 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgimple" } */
+/* { dg-final { check-function-bodies "**" "" "" } } */
+
+/* 32 is the value of CLZ at zero for SImode, so the CLZ instruction
+ gives the result. */
+
+/*
+** clz32:
+** clz w0, w0
+** ret
+*/
+int __GIMPLE (ssa)
+clz32 (unsigned int x)
+{
+ int _1;
+
+ __BB(2):
+ _1 = .CLZ (x_2(D), 32);
+ return _1;
+}
+
+/* Another value at zero needs a test of the argument. */
+
+/*
+** clz5:
+** clz (w[0-9]+), w0
+** cmp w0, 0
+** mov (w[0-9]+), 5
+** csel w0, \1, \2, ne
+** ret
+*/
+int __GIMPLE (ssa)
+clz5 (unsigned int x)
+{
+ int _1;
+
+ __BB(2):
+ _1 = .CLZ (x_2(D), 5);
+ return _1;
+}
+
+/* The same for DImode. */
+
+/*
+** clz64:
+** clz x([0-9]+), x0
+** cmp x0, 0
+** mov (w[0-9]+), 7
+** csel w0, w\1, \2, ne
+** ret
+*/
+int __GIMPLE (ssa)
+clz64 (unsigned long long x)
+{
+ int _1;
+
+ __BB(2):
+ _1 = .CLZ (x_2(D), 7);
+ return _1;
+}
diff --git a/gcc/testsuite/gcc.target/i386/clzg-target-clones-1.c
b/gcc/testsuite/gcc.target/i386/clzg-target-clones-1.c
new file mode 100644
index 00000000000..de52ba5f866
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/clzg-target-clones-1.c
@@ -0,0 +1,20 @@
+/* { dg-do run { target { ! ia32 } } } */
+/* { dg-require-ifunc "" } */
+/* { dg-options "-O2 -mlzcnt" } */
+
+/* With -mlzcnt __builtin_clzg (x, 32) becomes .CLZ (x, 32). The
+ arch=x86-64 clone has no LZCNT and must still return 32 for 0. */
+
+__attribute__((target_clones ("arch=x86-64", "default"))) int
+f (unsigned int x)
+{
+ return __builtin_clzg (x, 32);
+}
+
+int
+main (void)
+{
+ if (f (0) != 32 || f (1) != 31)
+ __builtin_abort ();
+ return 0;
+}
--
2.54.0 (Apple Git-157)
