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

[Richard Biener <rguenther@suse.de>]

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)