https://gcc.gnu.org/g:bbac87391e456997bd389bcbda8f2fcb734f922d
commit r17-5342-gbbac87391e456997bd389bcbda8f2fcb734f922d Author: Kyrylo Tkachov <[email protected]> Date: Mon Oct 12 04:14:47 2026 -0700 niter: Give the complement counts a value at zero [PR111280] number_of_iterations_cltz_complement handles loops that shift an IV until it is zero. If the start value T of the IV can be zero and the target does not define .CLZ at zero, build_cltz_expr builds T != 0 ? .CLZ (T) : PREC. The final value replacement gimplifies the count before the select, so .CLZ (T) is also evaluated for a zero T, where its result is undefined. For sqrtllu in gcc.c-torture/execute/920501-6.c, sccp on x86_64 emits _28 = t_10(D) != 0; _27 = .CLZ (t_10(D)); _22 = (unsigned int) _27; _29 = 64 - _22; _23 = (long long unsigned int) _29; b_30 = _28 ? _23 : 1; The expansion now implements any value at zero. As Richard Biener suggested in PR111280 comment 6, build .CLZ (T, PREC) instead of the select. The loop in sqrtllu modifies the IV before the exit test. For such loops the number of iterations was PREC - 1 - .CLZ (T), with another select for a zero T. The first value that the loop tests is T >> 1 (T << 1 for CTZ), and PREC minus the count of that value is right for all T. Use it and drop the select: _27 = t_10(D) >> 1; _28 = .CLZ (_27, 64); _39 = 65 - _28; b_30 = (long long unsigned int) _39; If the conditions on entry to the loop show that T is not zero, the count needs no value at zero. simplify_using_initial_conditions removed the select in that case, so ask it before the count is built. Guarded loops, which include while loops after header copying, keep their code. sqrtllu has 17 instead of 19 instructions on aarch64 and 23 instead of 25 on x86_64 with -march=x86-64-v3. Without LZCNT it has 26 instead of 22 on x86_64, because the expansion of .CLZ (_27, 64) tests _27. Types without a .CLZ or .CTZ internal function use the builtins with a select, as before. The argument can now be a shift, so unshare it in the select, because final value replacement rejects shared trees. Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux. gcc/ChangeLog: PR tree-optimization/111280 * tree-ssa-loop-niter.cc (build_cltz_expr): Pass the precision as the value at zero of the internal function instead of a select. Unshare SRC in the select of the builtins. (number_of_iterations_cltz_complement): Ask for a value at zero only if SRC can be zero on entry. If the IV is modified before the test and SRC can be zero, count the zeros of the first value tested. gcc/testsuite/ChangeLog: PR tree-optimization/111280 * gcc.dg/tree-ssa/pr111280.c: New test. Signed-off-by: Kyrylo Tkachov <[email protected]> Diff: --- gcc/testsuite/gcc.dg/tree-ssa/pr111280.c | 63 ++++++++++++++++++++++++++++++++ gcc/tree-ssa-loop-niter.cc | 61 ++++++++++++++++--------------- 2 files changed, 95 insertions(+), 29 deletions(-) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr111280.c b/gcc/testsuite/gcc.dg/tree-ssa/pr111280.c new file mode 100644 index 000000000000..4174804a12a1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr111280.c @@ -0,0 +1,63 @@ +/* PR tree-optimization/111280 */ +/* { dg-do run } */ +/* { dg-require-effective-target int32 } */ +/* { dg-require-effective-target clzsi } */ +/* { dg-require-effective-target ctzsi } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* The first value that the loops test is T shifted by one. It can be + zero, so its count needs a value at zero. */ + +__attribute__((noipa)) int +clz_loop (unsigned int t) +{ + int b = 0; + do + b++; + while ((t >>= 1) != 0); + return b; +} + +__attribute__((noipa)) int +ctz_loop (unsigned int t) +{ + int b = 0; + do + b++; + while ((t <<= 1) != 0); + return b; +} + +/* The loop is entered only with a nonzero T, so the count needs no value + at zero. */ + +__attribute__((noipa)) int +clz_guarded (unsigned int t) +{ + int b = 0; + while (t) + { + t >>= 1; + b++; + } + return b; +} + +int +main () +{ + if (clz_loop (0) != 1 || clz_loop (1) != 1 || clz_loop (6) != 3 + || clz_loop (0x80000000u) != 32) + __builtin_abort (); + if (ctz_loop (0) != 1 || ctz_loop (0x80000000u) != 1 || ctz_loop (6) != 31 + || ctz_loop (1) != 32) + __builtin_abort (); + if (clz_guarded (0) != 0 || clz_guarded (6) != 3 + || clz_guarded (0x80000000u) != 32) + __builtin_abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times {\.CLZ \(_\d+, 32\)} 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times {\.CTZ \(_\d+, 32\)} 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times {\.CLZ \(t_\d+\(D\)\)} 1 "optimized" } } */ diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc index 796155369827..871bd1bdf2a8 100644 --- a/gcc/tree-ssa-loop-niter.cc +++ b/gcc/tree-ssa-loop-niter.cc @@ -2191,10 +2191,9 @@ number_of_iterations_popcount (loop_p loop, edge exit, /* Return an expression that counts the leading/trailing zeroes of src. If define_at_zero is true, then the built expression will be defined to - return the precision of src when src == 0 (using either a conditional - expression or a suitable internal function). - Otherwise, we can elide the conditional expression and let src = 0 invoke - undefined behaviour. */ + return the precision of src when src == 0 (using the second argument of + the internal function or a conditional expression). + Otherwise, the result for src == 0 is undefined. */ static tree build_cltz_expr (tree src, bool leading, bool define_at_zero) @@ -2227,24 +2226,11 @@ build_cltz_expr (tree src, bool leading, bool define_at_zero) tree call; if (use_ifn) { - int val; - int optab_defined_at_zero - = (leading - ? CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (utype), val) - : CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (utype), val)); - tree arg2 = NULL_TREE; - if (define_at_zero && optab_defined_at_zero == 2 && val == prec) - arg2 = build_int_cst (integer_type_node, val); + tree arg2 = (define_at_zero + ? build_int_cst (integer_type_node, prec) : NULL_TREE); call = build_call_expr_internal_loc (UNKNOWN_LOCATION, ifn, integer_type_node, arg2 ? 2 : 1, src, arg2); - if (define_at_zero && arg2 == NULL_TREE) - { - tree is_zero = fold_build2 (NE_EXPR, boolean_type_node, src, - build_zero_cst (TREE_TYPE (src))); - call = fold_build3 (COND_EXPR, integer_type_node, is_zero, call, - build_int_cst (integer_type_node, prec)); - } } else if (fn == NULL_TREE) return NULL_TREE; @@ -2287,7 +2273,9 @@ build_cltz_expr (tree src, bool leading, bool define_at_zero) build_int_cst (integer_type_node, i_prec - prec)); if (define_at_zero) { - tree is_zero = fold_build2 (NE_EXPR, boolean_type_node, src, + /* SRC can be a shift, so do not share it with the call. */ + tree is_zero = fold_build2 (NE_EXPR, boolean_type_node, + unshare_expr (src), build_zero_cst (TREE_TYPE (src))); call = fold_build3 (COND_EXPR, integer_type_node, is_zero, call, build_int_cst (integer_type_node, prec)); @@ -2679,8 +2667,26 @@ number_of_iterations_cltz_complement (loop_p loop, edge exit, int src_precision = TYPE_PRECISION (TREE_TYPE (src)); - /* Get the corresponding c[lt]z builtin. */ - tree expr = build_cltz_expr (src, !left_shift, true); + tree src_zero = fold_build2 (EQ_EXPR, boolean_type_node, src, + build_zero_cst (TREE_TYPE (src))); + bool src_nonzero + = integer_zerop (simplify_using_initial_conditions (loop, src_zero)); + + /* If the IV is modified before the test, the first value tested is SRC + shifted by one. If SRC can be zero, count the zeros of that value + instead of subtracting one from the count of SRC. Then the result is + also right for a zero SRC. */ + tree count_src = src; + if (modify_before_test && !src_nonzero) + { + tree utype = unsigned_type_for (TREE_TYPE (src)); + count_src = fold_build2 (left_shift ? LSHIFT_EXPR : RSHIFT_EXPR, utype, + fold_convert (utype, src), integer_one_node); + } + + /* Get the corresponding c[lt]z builtin. It needs a value at zero only + if its argument can be zero. */ + tree expr = build_cltz_expr (count_src, !left_shift, !src_nonzero); if (!expr) return false; @@ -2691,21 +2697,18 @@ number_of_iterations_cltz_complement (loop_p loop, edge exit, max = src_precision; - tree may_be_zero = boolean_false_node; - if (modify_before_test) { - expr = fold_build2 (MINUS_EXPR, integer_type_node, expr, - integer_one_node); + if (src_nonzero) + expr = fold_build2 (MINUS_EXPR, integer_type_node, expr, + integer_one_node); max = max - 1; - may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src, - build_zero_cst (TREE_TYPE (src))); } expr = fold_convert (unsigned_type_node, expr); niter->assumptions = boolean_true_node; - niter->may_be_zero = simplify_using_initial_conditions (loop, may_be_zero); + niter->may_be_zero = boolean_false_node; niter->niter = simplify_using_initial_conditions (loop, expr); if (TREE_CODE (niter->niter) == INTEGER_CST)
