When we walk stmts to find always executed stmts with UB in the last
iteration to be able to reduce the iteration count by one we fail
to consider infinite subloops in the last iteration that would make
such stmt not execute. The following adds this and also changes
the DFS walk (which could end up stop iterating prematurely?) with
a walk over the DOM order of the loop body.
Bootstrap and regtest ongoing on x86_64-unknown-linux-gnu.
OK?
Thanks,
Richard.
PR tree-optimization/114052
* tree-ssa-loop-niter.cc (estimate_numbers_of_iterations):
Collect the loop body in DOM order.
(maybe_lower_iteration_bound): Walk the loop body in DOM
order. Check for infinite subloops we might not exit.
* gcc.dg/pr114052-1.c: New testcase.
---
gcc/testsuite/gcc.dg/pr114052-1.c | 41 +++++++++++++++++++++++++
gcc/tree-ssa-loop-niter.cc | 51 ++++++++++++++++++++-----------
2 files changed, 75 insertions(+), 17 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/pr114052-1.c
diff --git a/gcc/testsuite/gcc.dg/pr114052-1.c
b/gcc/testsuite/gcc.dg/pr114052-1.c
new file mode 100644
index 00000000000..98e93bf670d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr114052-1.c
@@ -0,0 +1,41 @@
+/* { dg-do run } */
+/* { dg-require-effective-target signal } */
+/* { dg-require-effective-target alarm } */
+/* { dg-options "-O2" } */
+
+#include <stdint.h>
+#include <unistd.h>
+#include <signal.h>
+#include <stdlib.h>
+
+volatile int y;
+void __attribute__((noipa)) put(int x)
+{
+ if (y)
+ __builtin_printf ("%i\n", x);
+}
+
+void __attribute__((noipa)) f(void)
+{
+ int counter = 0;
+ while (1) {
+ if (counter >= 2) continue;
+ put (counter++);
+ }
+}
+
+void do_exit (int i)
+{
+ exit (0);
+}
+
+int main()
+{
+ struct sigaction s;
+ sigemptyset (&s.sa_mask);
+ s.sa_handler = do_exit;
+ s.sa_flags = 0;
+ sigaction (SIGALRM, &s, NULL);
+ alarm (1);
+ f();
+}
diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index de8d5ae6233..4264d9acb44 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -4686,13 +4686,11 @@ discover_iteration_bound_by_body_walk (class loop *loop)
count by 1. */
static void
-maybe_lower_iteration_bound (class loop *loop)
+maybe_lower_iteration_bound (class loop *loop, basic_block *bbs)
{
hash_set<gimple *> *not_executed_last_iteration = NULL;
class nb_iter_bound *elt;
bool found_exit = false;
- auto_vec<basic_block> queue;
- bitmap visited;
/* Collect all statements with interesting (i.e. lower than
nb_iterations_upper_bound) bound on them.
@@ -4714,22 +4712,45 @@ maybe_lower_iteration_bound (class loop *loop)
if (!not_executed_last_iteration)
return;
- /* Start DFS walk in the loop header and see if we can reach the
+ /* Walk the loop body collected in DOM order and see if we can reach the
loop latch or any of the exits (including statements with side
effects that may terminate the loop otherwise) without visiting
any of the statements known to have undefined effect on the last
iteration. */
- queue.safe_push (loop->header);
- visited = BITMAP_ALLOC (NULL);
- bitmap_set_bit (visited, loop->header->index);
found_exit = false;
-
- do
+ class loop *inn_loop = loop;
+ for (unsigned i = 0; i < loop->num_nodes && !found_exit; ++i)
{
- basic_block bb = queue.pop ();
+ basic_block bb = bbs[i];
gimple_stmt_iterator gsi;
bool stmt_found = false;
+ if (!flow_bb_inside_loop_p (inn_loop, bb))
+ {
+ /* When we are leaving a possibly infinite inner loop
+ we have to stop processing. */
+ if (!finite_loop_p (inn_loop))
+ {
+ found_exit = true;
+ break;
+ }
+ /* If the loop was finite we can continue with processing
+ the loop we exited to. */
+ inn_loop = bb->loop_father;
+ }
+
+ if (bb->loop_father->header == bb)
+ /* Record that we enter into a subloop since it might not
+ be finite. */
+ inn_loop = bb->loop_father;
+
+ /* An irreducible region might be infinite. */
+ if (bb->flags & BB_IRREDUCIBLE_LOOP)
+ {
+ found_exit = true;
+ break;
+ }
+
/* Loop for possible exits and statements bounding the execution. */
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
@@ -4762,12 +4783,9 @@ maybe_lower_iteration_bound (class loop *loop)
found_exit = true;
break;
}
- if (bitmap_set_bit (visited, e->dest->index))
- queue.safe_push (e->dest);
}
}
}
- while (queue.length () && !found_exit);
/* If every path through the loop reach bounding statement before exit,
then we know the last iteration of the loop will have undefined effect
@@ -4783,7 +4801,6 @@ maybe_lower_iteration_bound (class loop *loop)
false, true);
}
- BITMAP_FREE (visited);
delete not_executed_last_iteration;
}
@@ -4885,7 +4902,7 @@ estimate_numbers_of_iterations (class loop *loop)
diagnose those loops with -Waggressive-loop-optimizations. */
number_of_latch_executions (loop);
- basic_block *body = get_loop_body (loop);
+ basic_block *body = get_loop_body_in_dom_order (loop);
auto_vec<edge> exits = get_loop_exit_edges (loop, body);
likely_exit = single_likely_exit (loop, exits);
FOR_EACH_VEC_ELT (exits, i, ex)
@@ -4925,11 +4942,11 @@ estimate_numbers_of_iterations (class loop *loop)
if (flag_aggressive_loop_optimizations)
infer_loop_bounds_from_undefined (loop, body);
- free (body);
discover_iteration_bound_by_body_walk (loop);
- maybe_lower_iteration_bound (loop);
+ maybe_lower_iteration_bound (loop, body);
+ free (body);
/* If we know the exact number of iterations of this loop, try to
not break code with undefined behavior by not recording smaller
--
2.43.0
