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

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

[Richard Biener]

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

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

[Jan Hubicka]

> +	  /* 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

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

[Richard Biener]

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 <rguenther@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)

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

[Richard Biener]

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
> > 
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)

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

[Richard Biener]

On Fri, 5 Apr 2024, Richard Biener wrote:

> 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.

It FAILs

    FAIL: gcc.dg/pr53265.c  at line 91 (test for warnings, line 90)
    FAIL: gcc.dg/pr53265.c  at line 92 (test for warnings, line 90)
    
    for diagnostic purposes we'd need to treat the call as not terminating
    
    FAIL: gcc.dg/tree-ssa/cunroll-10.c scan-tree-dump-times cunroll 
"Forced statement unreachable" 2
    FAIL: gcc.dg/tree-ssa/cunroll-11.c scan-tree-dump cunroll "Loop 1 
iterates at most 3 times"
    FAIL: gcc.dg/tree-ssa/cunroll-9.c scan-tree-dump-times cunrolli 
"Removed pointless exit:" 1
    FAIL: gcc.dg/tree-ssa/loop-38.c scan-tree-dump cunrolli "Loop 1 
iterates at most 11 times"
    FAIL: gcc.dg/tree-ssa/pr68234.c scan-tree-dump vrp2 ">> 6"
    FAIL: c-c++-common/ubsan/unreachable-3.c   -O0   scan-tree-dump 
optimized "__builtin___ubsan_handle_builtin_unreachable"
    ...
    FAIL: c-c++-common/ubsan/unreachable-3.c   -Os   scan-tree-dump 
optimized "__builtin___ubsan_handle_builtin_unreachable"


> 	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)
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)