On Tue, 13 Oct 2026, [email protected] wrote: > From: Kyrylo Tkachov <[email protected]> > > 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 29 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. > > Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux.
OK. Thanks, Richard. > 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]> > --- > gcc/testsuite/gcc.dg/tree-ssa/pr111280.c | 63 ++++++++++++++++++++++++ > gcc/tree-ssa-loop-niter.cc | 61 ++++++++++++----------- > 2 files changed, 95 insertions(+), 29 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr111280.c > > 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 00000000000..a1f5e821043 > --- /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 clz_ifn } */ > +/* { dg-require-effective-target ctz_ifn } */ > +/* { 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 6c368acb99b..4a1fc779f05 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) > -- 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)
