diff mbox series

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

Message ID 20240405131334.85979139F1@imap2.dmz-prg2.suse.org
State New
Headers show
Series [1/3] Pass reliable down to infer_loop_bounds_from_array | expand

Commit Message

Richard Biener April 5, 2024, 1:13 p.m. UTC 
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

Comments

Jan Hubicka April 5, 2024, 7:47 p.m. UTC | #1 
> +	  /* 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;

I think you are missing here non-call EH, volatile asms and traps.
 We have stmt_may_terminate_function_p which tests there.

Honza
> +
> +	  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
Richard Biener April 8, 2024, 11:31 a.m. UTC | #2 
On Fri, 5 Apr 2024, Jan Hubicka wrote:

> > +	  /* 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;
> 
> I think you are missing here non-call EH, volatile asms and traps.
>  We have stmt_may_terminate_function_p which tests there.

That returns true for all variable array accesses, I think we want
to catch traps explicitly here.  I'm going to do

          if (!may_have_exited
              && (gimple_has_side_effects (stmt)
                  || stmt_can_throw_external (cfun, stmt)))
            may_have_exited = true;

that should cover all but the generic trapping and not use IPA info
to prove no side-effects.

Richard.

> Honza
> > +
> > +	  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
>
Richard Biener April 8, 2024, 11:48 a.m. UTC | #3 
On Mon, 8 Apr 2024, Richard Biener wrote:

> On Fri, 5 Apr 2024, Jan Hubicka wrote:
> 
> > > +	  /* 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;
> > 
> > I think you are missing here non-call EH, volatile asms and traps.
> >  We have stmt_may_terminate_function_p which tests there.
> 
> That returns true for all variable array accesses, I think we want
> to catch traps explicitly here.  I'm going to do
> 
>           if (!may_have_exited
>               && (gimple_has_side_effects (stmt)
>                   || stmt_can_throw_external (cfun, stmt)))
>             may_have_exited = true;
> 
> that should cover all but the generic trapping and not use IPA info
> to prove no side-effects.

Hum.  Maybe I'm a bit confused but we seem to "properly" take things
into account via maybe_lower_iteration_bound and are not directly using
the recorded bounds?  The function does a DFS walk though, not
reliably finding exits via calls early enough (it also lacks external
EH).  Oddly enough it seems to handle(?) gcc.dg/tree-ssa/cunroll-9.c
"correctly", but not gcc.dg/tree-ssa/cunroll-10.c which has the
number of iterations wrongly computed.

Maybe we should really record all the bounds properly but merge them
to a loop upper bound at one place?  gcc.dg/tree-ssa/cunroll-11.c
needs to see the g_x[i] bound is enforced in all paths to the latch
for example.

I'm most definitely defering this to GCC 15 now, I wonder if you
have any preferences here (and maybe want to pick this up also
for cleanup - it's mostly your code).

Richard.

> Richard.
> 
> > Honza
> > > +
> > > +	  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
> > 
> 
>
diff mbox series

Patch

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)