On Tue, 13 Oct 2026, [email protected] wrote: > From: Kyrylo Tkachov <[email protected]> > > number_of_iterations_popcount, number_of_iterations_cltz and > number_of_iterations_cltz_complement accept an exit test on a header > PHI whose latch value is the modified IV, and take the start value from > the PHI of the IV. They do not check that the two PHIs are the same. > Two header PHIs can have the same latch value and different start > values: > > int > f (unsigned x, unsigned y) > { > unsigned t = x, u = y; > int b = 0; > for (;;) > { > t >>= 1; > b++; > if (u == 0) > break; > u = t; > } > return b; > } > > The loop exits when U is zero, and U starts with Y, but sccp computes > the number of iterations from X: > > _10 = .CLZ (x_4(D), 32); > _11 = (unsigned int) _10; > _12 = 33 - _11; > b_9 = (int) _12; > > so f (0, 1) returns 1 instead of 2. The popcount form (t &= t - 1) and > the CTZ form (if (u & 1) break) are wrong in the same way. GCC 11 > already miscompiles the popcount form. > > If the test comes before the modification, require that it tests the > PHI of the recurrence. > > Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux.
OK. It would be nice to have bugzillas for the wrong-code issues, it's going to be difficult to track required backports without those? Thanks, Richard. > gcc/ChangeLog: > > * tree-ssa-loop-niter.cc (number_of_iterations_popcount): Fail if > the exit test uses another header PHI than the recurrence. > (number_of_iterations_cltz): Likewise. > (number_of_iterations_cltz_complement): Likewise. > > gcc/testsuite/ChangeLog: > > * gcc.dg/torture/niter-bitcount-1.c: New test. > > Signed-off-by: Kyrylo Tkachov <[email protected]> > --- > .../gcc.dg/torture/niter-bitcount-1.c | 66 +++++++++++++++++++ > gcc/tree-ssa-loop-niter.cc | 24 +++++-- > 2 files changed, 84 insertions(+), 6 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/torture/niter-bitcount-1.c > > diff --git a/gcc/testsuite/gcc.dg/torture/niter-bitcount-1.c > b/gcc/testsuite/gcc.dg/torture/niter-bitcount-1.c > new file mode 100644 > index 00000000000..09282525b31 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/torture/niter-bitcount-1.c > @@ -0,0 +1,66 @@ > +/* { dg-do run } */ > + > +/* The loops exit on a header PHI whose latch value is the modified IV, but > + whose start value is not the start value of the IV. */ > + > +__attribute__((noipa)) int > +clz_complement (unsigned x, unsigned y) > +{ > + unsigned t = x, u = y; > + int b = 0; > + for (;;) > + { > + t >>= 1; > + b++; > + if (u == 0) > + break; > + u = t; > + } > + return b; > +} > + > +__attribute__((noipa)) int > +popcount (unsigned x, unsigned y) > +{ > + unsigned t = x, u = y; > + int b = 0; > + for (;;) > + { > + t &= t - 1; > + b++; > + if (u == 0) > + break; > + u = t; > + } > + return b; > +} > + > +__attribute__((noipa)) int > +ctz (unsigned x, unsigned y) > +{ > + if (x == 0) > + return -1; > + unsigned t = x, u = y; > + int b = 0; > + for (;;) > + { > + t >>= 1; > + b++; > + if (u & 1) > + break; > + u = t; > + } > + return b; > +} > + > +int > +main () > +{ > + if (clz_complement (0, 1) != 2 || clz_complement (8, 0) != 1) > + __builtin_abort (); > + if (popcount (0, 1) != 2 || popcount (7, 0) != 1) > + __builtin_abort (); > + if (ctz (4, 1) != 1 || ctz (4, 2) != 3) > + __builtin_abort (); > + return 0; > +} > diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc > index bbfa16c6d6b..6c368acb99b 100644 > --- a/gcc/tree-ssa-loop-niter.cc > +++ b/gcc/tree-ssa-loop-niter.cc > @@ -2104,6 +2104,7 @@ number_of_iterations_popcount (loop_p loop, edge exit, > > tree iv_2 = gimple_cond_lhs (cond_stmt); > gimple *iv_2_stmt = SSA_NAME_DEF_STMT (iv_2); > + gimple *test_phi = NULL; > > /* If the test comes before the iv modification, then these will actually > be > iv_1 and a phi node. */ > @@ -2115,6 +2116,7 @@ number_of_iterations_popcount (loop_p loop, edge exit, > == SSA_NAME)) > { > /* iv_2 is actually one of the inputs to the phi. */ > + test_phi = iv_2_stmt; > iv_2 = gimple_phi_arg_def (iv_2_stmt, loop_latch_edge > (loop)->dest_idx); > iv_2_stmt = SSA_NAME_DEF_STMT (iv_2); > modify_before_test = false; > @@ -2138,11 +2140,13 @@ number_of_iterations_popcount (loop_p loop, edge exit, > else > return false; > > - /* Check the recurrence. */ > + /* Check the recurrence. A test before the modification must test the > + PHI of the recurrence. */ > gimple *phi = SSA_NAME_DEF_STMT (iv_1); > if (gimple_code (phi) != GIMPLE_PHI > || (gimple_bb (phi) != loop_latch_edge (loop)->dest) > - || (iv_2 != gimple_phi_arg_def (phi, loop_latch_edge > (loop)->dest_idx))) > + || (iv_2 != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx)) > + || (test_phi && phi != test_phi)) > return false; > > /* We found a match. */ > @@ -2444,6 +2448,7 @@ number_of_iterations_cltz (loop_p loop, edge exit, > } > > gimple *iv_2_stmt = SSA_NAME_DEF_STMT (iv_2); > + gimple *test_phi = NULL; > > /* If the test comes before the iv modification, then these will actually > be > iv_1 and a phi node. */ > @@ -2455,6 +2460,7 @@ number_of_iterations_cltz (loop_p loop, edge exit, > == SSA_NAME)) > { > /* iv_2 is actually one of the inputs to the phi. */ > + test_phi = iv_2_stmt; > iv_2 = gimple_phi_arg_def (iv_2_stmt, loop_latch_edge > (loop)->dest_idx); > iv_2_stmt = SSA_NAME_DEF_STMT (iv_2); > modify_before_test = false; > @@ -2471,11 +2477,13 @@ number_of_iterations_cltz (loop_p loop, edge exit, > > tree iv_1 = gimple_assign_rhs1 (iv_2_stmt); > > - /* Check the recurrence. */ > + /* Check the recurrence. A test before the modification must test the > + PHI of the recurrence. */ > gimple *phi = SSA_NAME_DEF_STMT (iv_1); > if (gimple_code (phi) != GIMPLE_PHI > || (gimple_bb (phi) != loop_latch_edge (loop)->dest) > - || (iv_2 != gimple_phi_arg_def (phi, loop_latch_edge > (loop)->dest_idx))) > + || (iv_2 != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx)) > + || (test_phi && phi != test_phi)) > return false; > > /* We found a match. */ > @@ -2616,6 +2624,7 @@ number_of_iterations_cltz_complement (loop_p loop, edge > exit, > > tree iv_2 = gimple_cond_lhs (cond_stmt); > gimple *iv_2_stmt = SSA_NAME_DEF_STMT (iv_2); > + gimple *test_phi = NULL; > > /* If the test comes before the iv modification, then these will actually > be > iv_1 and a phi node. */ > @@ -2627,6 +2636,7 @@ number_of_iterations_cltz_complement (loop_p loop, edge > exit, > == SSA_NAME)) > { > /* iv_2 is actually one of the inputs to the phi. */ > + test_phi = iv_2_stmt; > iv_2 = gimple_phi_arg_def (iv_2_stmt, loop_latch_edge > (loop)->dest_idx); > iv_2_stmt = SSA_NAME_DEF_STMT (iv_2); > modify_before_test = false; > @@ -2643,11 +2653,13 @@ number_of_iterations_cltz_complement (loop_p loop, > edge exit, > > tree iv_1 = gimple_assign_rhs1 (iv_2_stmt); > > - /* Check the recurrence. */ > + /* Check the recurrence. A test before the modification must test the > + PHI of the recurrence. */ > gimple *phi = SSA_NAME_DEF_STMT (iv_1); > if (gimple_code (phi) != GIMPLE_PHI > || (gimple_bb (phi) != loop_latch_edge (loop)->dest) > - || (iv_2 != gimple_phi_arg_def (phi, loop_latch_edge > (loop)->dest_idx))) > + || (iv_2 != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx)) > + || (test_phi && phi != test_phi)) > return false; > > /* We found a match. */ > -- 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)
