On Tue, 13 Oct 2026, [email protected] wrote: > 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.
LGTM. Richard. > 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; > +} > -- Richard Biener <[email protected]> SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Stefan Gaiser, Jochen Jaser, Abhinav Puri; (HRB 36809, AG Nuernberg)
