https://gcc.gnu.org/g:37c4ef28f7e636d7fca5270d1323553eb30b8e5a
commit r17-5396-g37c4ef28f7e636d7fca5270d1323553eb30b8e5a Author: Kyrylo Tkachov <[email protected]> Date: Mon Oct 19 11:57:44 2026 -0700 internal-fn: Implement the C[LT]Z value at zero for scalar calls [PR111280] 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 four 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. - Since r17-5342 niter analysis counts the iterations of a loop that shifts T before the test with .CLZ (T >> 1, PREC) or .CTZ (T << 1, PREC). On x86_64 without LZCNT, .CLZ expands to bsr with no zero test, so gcc.dg/tree-ssa/pr111280.c fails at run time. Jakub Jelinek 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. If C?Z_DEFINED_VALUE_AT_ZERO returns 1 or 2, the instruction gives a value for zero, so count first and then select V. Otherwise execute the instruction only for a nonzero argument. 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. 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-112.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]> Diff: --- gcc/doc/ifn.texi | 20 ++- gcc/internal-fn.cc | 71 +++++++++- gcc/testsuite/gcc.dg/torture/bitint-112.c | 62 ++++++++ .../gcc.dg/torture/clz-ctz-value-at-zero-1.c | 157 +++++++++++++++++++++ .../gcc.target/aarch64/clz-ctz-value-at-zero-1.c | 61 ++++++++ .../gcc.target/i386/clzg-target-clones-1.c | 20 +++ 6 files changed, 380 insertions(+), 11 deletions(-) diff --git a/gcc/doc/ifn.texi b/gcc/doc/ifn.texi index d80e089685a3..afe8a977f70a 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 45ad08d2cf61..94a601d34d6d 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,73 @@ 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. If it is not the value that the instruction gives + for zero, test the first argument for zero and use the second argument + as the result. If the target does not define the instruction for zero, + execute it only for a nonzero first 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)); + int val = 0, defined = 0; + if (gimple_call_num_args (stmt) == 2) + defined = (fn == IFN_CLZ + ? CLZ_DEFINED_VALUE_AT_ZERO (mode, val) + : CTZ_DEFINED_VALUE_AT_ZERO (mode, val)); + if (gimple_call_num_args (stmt) == 1 + || (defined == 2 && wi::to_widest (gimple_call_arg (stmt, 1)) == val)) + { + expand_unary_optab_fn (fn, stmt, optab); + return; + } + /* The vectorizer creates vector calls only with the value of the + target. */ + gcc_checking_assert (!VECTOR_TYPE_P (TREE_TYPE (arg))); + + tree lhs = gimple_call_lhs (stmt); + rtx op0 = force_reg (mode, expand_normal (arg)); + rtx zero_val = expand_normal (fold_convert (TREE_TYPE (lhs), + gimple_call_arg (stmt, 1))); + rtx res = gen_reg_rtx (TYPE_MODE (TREE_TYPE (lhs))); + rtx_code_label *done = gen_label_rtx (); + if (defined) + { + convert_move (res, expand_unop (mode, optab, op0, NULL_RTX, 1), 1); + emit_cmp_and_jump_insns (op0, const0_rtx, NE, NULL_RTX, mode, true, + done, profile_probability::likely ()); + emit_move_insn (res, zero_val); + } + else + { + emit_move_insn (res, zero_val); + emit_cmp_and_jump_insns (op0, const0_rtx, EQ, NULL_RTX, mode, true, + done, profile_probability::unlikely ()); + convert_move (res, expand_unop (mode, optab, op0, NULL_RTX, 1), 1); + } + emit_label (done); + rtx target = expand_expr (lhs, NULL_RTX, VOIDmode, EXPAND_WRITE); + if (GET_CODE (target) == SUBREG && SUBREG_PROMOTED_VAR_P (target)) + convert_move (SUBREG_REG (target), res, SUBREG_PROMOTED_SIGN (target)); + else + emit_move_insn (target, res); +} + 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-112.c b/gcc/testsuite/gcc.dg/torture/bitint-112.c new file mode 100644 index 000000000000..4d4dab67b890 --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/bitint-112.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 000000000000..57381d8204c4 --- /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 clzsi } */ +/* { dg-require-effective-target ctzsi } */ +/* { 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 000000000000..466d9757aef6 --- /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 000000000000..de52ba5f8666 --- /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; +}
