[PATCH 3/3] tree-optimization/114052 - niter analysis from undefined behavior

[Richard Biener <rguenther@suse.de>]

The following makes sure to only compute upper bounds for the number
of iterations of loops from undefined behavior invoked by stmts when
those are executed in each loop iteration, in particular also in the
last one.  The latter cannot be guaranteed if there's possible
infinite loops or calls with side-effects possibly executed before
the stmt.  Rather than adjusting the bound by one or using the bound as
estimate the following for now gives up.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

	PR tree-optimization/114052
	* tree-ssa-loop-niter.cc (infer_loop_bounds_from_undefined):
	When we enter a possibly infinite loop or when we come across
	a call with side-effects record the last iteration might not
	execute all stmts.  Consider bounds as unreliable in that case.

	* gcc.dg/tree-ssa/pr114052-1.c: New testcase.
---
 gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c | 16 ++++++++++
 gcc/tree-ssa-loop-niter.cc                 | 35 ++++++++++++++++++----
 2 files changed, 45 insertions(+), 6 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c
new file mode 100644
index 00000000000..54a2181e67e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int foo(void)
+{
+  int counter = 0;
+  while (1)
+    {
+      if (counter >= 2)
+	continue;
+      __builtin_printf("%i\n", counter++);
+    }
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-not "unreachable" "optimized" } } */
diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index 0a77c1bb544..52a39eb3500 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -4397,7 +4397,7 @@ infer_loop_bounds_from_undefined (class loop *loop, basic_block *bbs)
   unsigned i;
   gimple_stmt_iterator bsi;
   basic_block bb;
-  bool reliable;
+  bool may_have_exited = false;
 
   for (i = 0; i < loop->num_nodes; i++)
     {
@@ -4407,21 +4407,44 @@ infer_loop_bounds_from_undefined (class loop *loop, basic_block *bbs)
 	 use the operations in it to infer reliable upper bound on the
 	 # of iterations of the loop.  However, we can use it as a guess. 
 	 Reliable guesses come only from array bounds.  */
-      reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
+      bool reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
+
+      /* A possibly infinite inner loop makes further blocks not always
+	 executed.  Key on the entry of such a loop as that avoids RPO
+	 issues with where the exits of that loop are.  Any block
+	 inside an irreducible sub-region is problematic as well.
+	 ???  Note this technically only makes the last iteration
+	 possibly partially executed.  */
+      if (!may_have_exited
+	  && bb != loop->header
+	  && (!loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
+	      || bb->flags & BB_IRREDUCIBLE_LOOP
+	      || (bb->loop_father->header == bb
+		  && !finite_loop_p (bb->loop_father))))
+	may_have_exited = true;
 
       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 	{
 	  gimple *stmt = gsi_stmt (bsi);
 
-	  infer_loop_bounds_from_array (loop, stmt, reliable);
+	  /* When there's a call that might not return the last iteration
+	     is possibly partial.  This matches what we check in invariant
+	     motion.
+	     ???  For the call argument evaluation it would be still OK.  */
+	  if (!may_have_exited
+	      && is_gimple_call (stmt)
+	      && gimple_has_side_effects (stmt))
+	    may_have_exited = true;
+
+	  infer_loop_bounds_from_array (loop, stmt,
+					reliable && !may_have_exited);
 
-	  if (reliable)
+	  if (reliable && !may_have_exited)
             {
               infer_loop_bounds_from_signedness (loop, stmt);
               infer_loop_bounds_from_pointer_arith (loop, stmt);
             }
   	}
-
     }
 }
 
@@ -4832,7 +4855,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_rpo (cfun, 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)
-- 
2.35.3