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.
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. */
--
2.54.0 (Apple Git-157)
