Re: Fix array bound niter estimate (PR middle-end/54937)

[Richard Biener <rguenther at suse dot de>]

On Fri, 19 Oct 2012, Jan Hubicka wrote:

> Hi,
> this patch fixes off-by-one error in the testcase attached.  The problem is that
> dominance based test used by record_estimate to check whether the given statement
> must be executed at last iteration of the loop is wrong ignoring the side effect
> of other statements that may terminate the program.
> It also does not work for mulitple exits as excercised by cunroll-2.c testcase.
> 
> This patch makes simple approach of computing set of all statements that must
> by executed last iteration first time record_estimate is executed this way.
> The set is computed conservatively walking header BB and its signle successors
> (possibly diving into nested loop) stopping on first BB with multiple exits.
> 
> Better result can be computed by
> 1) estimating what loops are known to be finite
> 2) inserting fake edges for all infinite loop and all statements with side effect
>    that may terminate the execution
> 3) using the post dominance info.

would using post-dom info even work?  That only says that _if_ the
dominated stmt executed then it came through the dominator.  It
doesn't deal with functions that may not return.

> But that seems too expensive for something that is executed several times per
> function compilation. In fact I am thinking about making recrod-estimate to happen
> at ivcanon time only and then making the loop_max_iterations and loop_estimated_iterations
> to simply return the bound instead of trying to recompute it all the time.
> 
> Still I do not see us to care about very precise bound for loops having complex
> control flow since we do not really want to completely unroll them and elsewhere
> the off-by-one error in conservative direction for iteration estimate is not big
> deal.
> 
> Bootstrapped/regtested x86_64-linux, seems sane?
> 
> Honza
> 
> 	PR middle-end/54937
> 	* tree-ssa-loop-niter.c (compute_stmts_executed_last_iteration): New
> 	function.
> 	(record_estimate): Use it; remove confused dominance test.
> 	(estimate_numbers_of_iterations_loop): Free stmts_executed_last_iteration.
> 	* gcc.c-torture/execute/pr54937.c: Ne wtestcase.
> 	* testsuite/gcc.dg/tree-ssa/cunroll-2.c: Tighten.
> Index: tree-ssa-loop-niter.c
> ===================================================================
> *** tree-ssa-loop-niter.c	(revision 192537)
> --- tree-ssa-loop-niter.c	(working copy)
> *************** record_niter_bound (struct loop *loop, d
> *** 2523,2528 ****
> --- 2523,2580 ----
>       loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
>   }
>   
> + /* Compute pointer set of statements in currently analyzed loop that are known
> +    to be executed at last iteration and store it into AUX.  
> +    We do very simple job of recording statements in the superblock
> +    starsting in loop header until reaching first statement with side effect.
> + 
> +    We can compute post-dominance after inserting fake edges to CFG
> +    for all statements possibly terminating CFG and for all possibly
> +    infinite subloops, but we really care about precise estimates
> +    of simple loops with little control flow in it.  */
> + static void
> + compute_stmts_executed_last_iteration (struct loop *loop)
> + {
> +   basic_block bb = loop->header;
> +   pointer_set_t *visited = NULL;
> +   gimple_stmt_iterator gsi;
> +   pointer_set_t *stmts_executed_last_iteration;
> + 
> +   loop->aux = stmts_executed_last_iteration = pointer_set_create ();
> +   while (true)
> +     {
> +       for (gsi = gsi_start_bb (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
> + 	{
> + 	  if (gimple_has_side_effects (gsi_stmt (gsi)))
> + 	    {
> + 	      if (visited)
> + 	        pointer_set_destroy (visited);
> + 	      return;
> + 	    }
> + 	  pointer_set_insert (stmts_executed_last_iteration, gsi_stmt (gsi));
> + 	}
> +       if (single_succ_p (bb))
> + 	{
> + 	  /* Deal with the rare case that there is an infintie loop inside the
> + 	     loop examined.  */
> + 	  if (!visited)
> + 	    {
> +               visited = pointer_set_create ();
> +               pointer_set_insert (visited, bb);
> + 	    }
> + 	  bb = single_succ_edge (bb)->dest;
> +           if (pointer_set_insert (visited, bb))
> + 	    break;
> + 	}
> +       else
> + 	break;
> +     }
> +   if (visited)
> +     pointer_set_destroy (visited);
> +   return;
> + }
> + 
> + 
>   /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP.  IS_EXIT
>      is true if the loop is exited immediately after STMT, and this exit
>      is taken at last when the STMT is executed BOUND + 1 times.
> *************** record_estimate (struct loop *loop, tree
> *** 2535,2541 ****
>   		 gimple at_stmt, bool is_exit, bool realistic, bool upper)
>   {
>     double_int delta;
> -   edge exit;
>   
>     if (dump_file && (dump_flags & TDF_DETAILS))
>       {
> --- 2587,2592 ----
> *************** record_estimate (struct loop *loop, tree
> *** 2573,2586 ****
>        If at_stmt is an exit or dominates the single exit from the loop,
>        then the loop latch is executed at most BOUND times, otherwise
>        it can be executed BOUND + 1 times.  */
> !   exit = single_exit (loop);
> !   if (is_exit
> !       || (exit != NULL
> ! 	  && dominated_by_p (CDI_DOMINATORS,
> ! 			     exit->src, gimple_bb (at_stmt))))
>       delta = double_int_zero;
>     else
> !     delta = double_int_one;
>     i_bound += delta;
>   
>     /* If an overflow occurred, ignore the result.  */
> --- 2624,2641 ----
>        If at_stmt is an exit or dominates the single exit from the loop,
>        then the loop latch is executed at most BOUND times, otherwise
>        it can be executed BOUND + 1 times.  */
> !   if (is_exit)
>       delta = double_int_zero;
>     else
> !     {
> !       if (!loop->aux)
> ! 	compute_stmts_executed_last_iteration (loop);
> !       if (pointer_set_contains ((pointer_set_t *)loop->aux,
> ! 				at_stmt))
> !         delta = double_int_zero;
> !       else
> !         delta = double_int_one;
> !     }

What about the conservative variant of simply

      else
        delta = double_int_one;

?  I don't like all the code you add, nor the use of ->aux.

>     i_bound += delta;

Another alternative would be to not use i_bound for the
strong upper bound but only the estimate (thus conservatively
use i_bound + 1 for the upper bound if !is_exit).

Richard.

>     /* If an overflow occurred, ignore the result.  */
> *************** estimate_numbers_of_iterations_loop (str
> *** 2971,2976 ****
> --- 3026,3033 ----
>     if (loop->estimate_state != EST_NOT_COMPUTED)
>       return;
>   
> +   gcc_assert (!loop->aux);
> + 
>     loop->estimate_state = EST_AVAILABLE;
>     /* Force estimate compuation but leave any existing upper bound in place.  */
>     loop->any_estimate = false;
> *************** estimate_numbers_of_iterations_loop (str
> *** 3004,3009 ****
> --- 3061,3071 ----
>         bound = gcov_type_to_double_int (nit);
>         record_niter_bound (loop, bound, true, false);
>       }
> +   if (loop->aux)
> +     {
> +       pointer_set_destroy ((pointer_set_t *)loop->aux);
> +       loop->aux = NULL;
> +     }
>   }
>   
>   /* Sets NIT to the estimated number of executions of the latch of the
> Index: testsuite/gcc.c-torture/execute/pr54937.c
> ===================================================================
> --- testsuite/gcc.c-torture/execute/pr54937.c	(revision 0)
> +++ testsuite/gcc.c-torture/execute/pr54937.c	(revision 0)
> @@ -0,0 +1,22 @@
> +
> +void exit (int);
> +void abort (void);
> +int a[1];
> +void (*terminate_me)(int);
> +
> +__attribute__((noinline,noclone))
> +t(int c)
> +{ int i;
> +  for (i=0;i<c;i++)
> +    {
> +      if (i)
> +       terminate_me(0);
> +      a[i]=0;
> +    }
> +}
> +main()
> +{
> +  terminate_me = exit;
> +  t(100);
> +  abort();
> +}
> Index: testsuite/gcc.dg/tree-ssa/cunroll-2.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/cunroll-2.c	(revision 192608)
> +++ testsuite/gcc.dg/tree-ssa/cunroll-2.c	(working copy)
> @@ -12,5 +12,5 @@ test(int c)
>      }
>  }
>  /* We are not able to get rid of the final conditional because the loop has two exits.  */
> -/* { dg-final { scan-tree-dump "Unrolled loop 1 completely .duplicated 2 times.." "cunroll"} } */
> +/* { dg-final { scan-tree-dump "Unrolled loop 1 completely .duplicated 1 times.." "cunroll"} } */
>  /* { dg-final { cleanup-tree-dump "cunroll" } } */
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend