https://gcc.gnu.org/g:65b6b8d2063605aa0ccbfa1379b7c0d6033f8e5a
commit r17-5341-g65b6b8d2063605aa0ccbfa1379b7c0d6033f8e5a Author: Kyrylo Tkachov <[email protected]> Date: Mon Oct 12 05:51:15 2026 -0700 niter: Check that bit count loops test the recurrence PHI 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. 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]> Diff: --- gcc/testsuite/gcc.dg/torture/niter-bitcount-1.c | 66 +++++++++++++++++++++++++ gcc/tree-ssa-loop-niter.cc | 24 ++++++--- 2 files changed, 84 insertions(+), 6 deletions(-) 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 000000000000..09282525b317 --- /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 f9f8222e6311..796155369827 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. */
