Re: Non-dominating loop bounds in tree-ssa-loop-niter 3/4

[Richard Biener <rguenther@suse.de>]

On Wed, 31 Oct 2012, Jan Hubicka wrote:

> Hi,
> this patch implements the logic to remove statements that are known to be
> undefined and thus expected to not be executed after unrolling.  It also
> removes redundant exits that I originally tried to do at once, but it
> does not fly, since the peeling confuse number_of_iterations_exit
> and it no longer understands the ivs.
> 
> So now we
> 1) always remove exits that are known to be redundant by the bounds found
> 2) try to peel/unroll
> 3) if success remove statemnts from the last iteration
> 
> This silence the array-bounds warnings in my testcase and many cases of
> -O3 bootstrap (I am running it now).
> Still if one construct testcase touching out of bound in more than one
> iteration we will produce false warning, I will do that incrementally
> by similar logic in loop copying.
> 
> Bootstrapped/regtested x86_64-linux, OK?
> 
> Honza
> 
> 	* tree-ssa-loop-niter.c (free_loop_bounds): Break out from ...
> 	(free_numbers_of_iterations_estimates_loop): ... here.
> 	* tree-ssa-loop-ivcanon.c (remove_exits_and_undefined_stmts): New
> 	function.
> 	(remove_redundant_iv_test): New function.
> 	(try_unroll_loop_completely): Pass in MAXITER; use
> 	remove_exits_and_undefined_stmts
> 	(canonicalize_loop_induction_variables): Compute MAXITER;
> 	use remove_redundant_iv_test.
> 	* cfgloop.h (free_loop_bounds): New function.
> 
> 	* gcc.dg/tree-ssa/cunroll-10.c: New testcase.
> 	* gcc.dg/tree-ssa/cunroll-9.c: New testcase.
> Index: tree-ssa-loop-niter.c
> ===================================================================
> --- tree-ssa-loop-niter.c	(revision 192989)
> @@ -3505,15 +3737,11 @@ scev_probably_wraps_p (tree base, tree s
>    return true;
>  }
>  
> -/* Frees the information on upper bounds on numbers of iterations of LOOP.  */
> -

Needs a comment.

>  void
> -free_numbers_of_iterations_estimates_loop (struct loop *loop)
> +free_loop_bounds (struct loop *loop)
>  {
>    struct nb_iter_bound *bound, *next;
>  
> -  loop->nb_iterations = NULL;
> -  loop->estimate_state = EST_NOT_COMPUTED;
>    for (bound = loop->bounds; bound; bound = next)
>      {
>        next = bound->next;
> @@ -3523,6 +3751,16 @@ free_numbers_of_iterations_estimates_loo
>    loop->bounds = NULL;
>  }
>  
> +/* Frees the information on upper bounds on numbers of iterations of LOOP.  */
> +
> +void
> +free_numbers_of_iterations_estimates_loop (struct loop *loop)
> +{
> +  loop->nb_iterations = NULL;
> +  loop->estimate_state = EST_NOT_COMPUTED;
> +  free_loop_bounds (loop);
> +}
> +
>  /* Frees the information on upper bounds on numbers of iterations of loops.  */
>  
>  void
> Index: tree-ssa-loop-ivcanon.c
> ===================================================================
> --- tree-ssa-loop-ivcanon.c	(revision 192989)
> +++ tree-ssa-loop-ivcanon.c	(working copy)
> @@ -389,6 +389,116 @@ loop_edge_to_cancel (struct loop *loop)
>    return NULL;
>  }
>  
> +/* Remove all tests for exits that are known to be taken after LOOP was
> +   peeled NPEELED times. Put gcc_unreachable before every statement
> +   known to not be executed.  */
> +
> +static bool
> +remove_exits_and_undefined_stmts (struct loop *loop, unsigned int npeeled)
> +{
> +  struct nb_iter_bound *elt;
> +  bool changed = false;
> +
> +  for (elt = loop->bounds; elt; elt = elt->next)
> +    {
> +      /* If statement is known to be undefined after peeling, turn it
> +	 into unreachable (or trap when debugging experience is supposed
> +	 to be good).  */
> +      if (!elt->is_exit
> +	  && elt->bound.ule (double_int::from_uhwi (npeeled)))
> +	{
> +	  gimple_stmt_iterator gsi = gsi_for_stmt (elt->stmt);
> +	  gimple stmt = gimple_build_call
> +	      (builtin_decl_implicit (optimize_debug
> +				      ? BUILT_IN_TRAP : BUILT_IN_UNREACHABLE),

I'm not sure we should do different things for -Og here.  In fact there
is no unrolling done for -Og at all, so just use unreachable.

> +	       0);
> +
> +	  gimple_set_location (stmt, gimple_location (elt->stmt));
> +	  gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
> +	  changed = true;
> +	  if (dump_file && (dump_flags & TDF_DETAILS))
> +	    {
> +	      fprintf (dump_file, "Forced statement unreachable: ");
> +	      print_gimple_stmt (dump_file, elt->stmt, 0, 0);
> +	    }
> +	}
> +      /* If we know the exit will be taken after peeling, update.  */
> +      else if (elt->is_exit
> +	       && elt->bound.ule (double_int::from_uhwi (npeeled)))
> +	{
> +	  basic_block bb = gimple_bb (elt->stmt);
> +	  edge exit_edge = EDGE_SUCC (bb, 0);
> +
> +	  if (dump_file && (dump_flags & TDF_DETAILS))
> +	    {
> +	      fprintf (dump_file, "Forced exit to be taken: ");
> +	      print_gimple_stmt (dump_file, elt->stmt, 0, 0);
> +	    }
> +	  if (!loop_exit_edge_p (loop, exit_edge))
> +	    exit_edge = EDGE_SUCC (bb, 1);
> +	  if (exit_edge->flags & EDGE_TRUE_VALUE)

I think we can have abnormal/eh exit edges.  So I'm not sure you
can, without checking, assume the block ends in a GIMPLE_COND.

> +	    gimple_cond_make_true (elt->stmt);
> +	  else
> +	    gimple_cond_make_false (elt->stmt);
> +	  update_stmt (elt->stmt);
> +	  changed = true;
> +	}
> +    }
> +  return changed;
> +}
> +
> +/* Remove all exits that are known to be never taken because of the loop bound
> +   discovered.  */
> +
> +static bool
> +remove_redundant_iv_test (struct loop *loop)
> +{
> +  struct nb_iter_bound *elt;
> +  bool changed = false;
> +
> +  if (!loop->any_upper_bound)
> +    return false;
> +  for (elt = loop->bounds; elt; elt = elt->next)
> +    {
> +      /* Exit is pointless if it won't be taken before loop reaches
> +	 upper bound.  */
> +      if (elt->is_exit && loop->any_upper_bound
> +          && loop->nb_iterations_upper_bound.ult (elt->bound))
> +	{
> +	  basic_block bb = gimple_bb (elt->stmt);
> +	  edge exit_edge = EDGE_SUCC (bb, 0);
> +	  struct tree_niter_desc niter;
> +	  
> +	  if (!loop_exit_edge_p (loop, exit_edge))
> +	    exit_edge = EDGE_SUCC (bb, 1);
> +
> +	  /* Only when we know the actual number of iterations, not
> +	     just a bound, we can remove the exit.  */
> +	  if (!number_of_iterations_exit (loop, exit_edge,
> +					  &niter, false, false))
> +	    gcc_unreachable ();
> +	  if (!integer_onep (niter.assumptions)
> +	      || !integer_zerop (niter.may_be_zero)
> +	      || !niter.niter
> +	      || TREE_CODE (niter.niter) != INTEGER_CST)
> +	    continue;
> +
> +	  if (dump_file && (dump_flags & TDF_DETAILS))
> +	    {
> +	      fprintf (dump_file, "Removed pointless exit: ");
> +	      print_gimple_stmt (dump_file, elt->stmt, 0, 0);
> +	    }
> +	  if (exit_edge->flags & EDGE_TRUE_VALUE)
> +	    gimple_cond_make_false (elt->stmt);
> +	  else
> +	    gimple_cond_make_true (elt->stmt);

See above.  Otherwise the overall idea sounds fine.

Richard.

> +	  update_stmt (elt->stmt);
> +	  changed = true;
> +	}
> +    }
> +  return changed;
> +}
> +
>  /* Tries to unroll LOOP completely, i.e. NITER times.
>     UL determines which loops we are allowed to unroll.
>     EXIT is the exit of the loop that should be eliminated.  
> @@ -396,20 +511,22 @@ loop_edge_to_cancel (struct loop *loop)
>     irreducible regions may become invalid as a result
>     of the transformation.  
>     LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
> -   when we need to go into loop closed SSA form.  */
> +   when we need to go into loop closed SSA form. 
> +   MAXITER specfy bound on number of iterations, -1 if it is
> +   not known or too large for HOST_WIDE_INT.  */
>  
>  static bool
>  try_unroll_loop_completely (struct loop *loop,
>  			    edge exit, tree niter,
>  			    enum unroll_level ul,
>  			    bool *irred_invalidated,
> -			    bitmap loop_closed_ssa_invalidated)
> +			    bitmap loop_closed_ssa_invalidated,
> +			    HOST_WIDE_INT maxiter)
>  {
>    unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
>    gimple cond;
>    struct loop_size size;
>    bool n_unroll_found = false;
> -  HOST_WIDE_INT maxiter;
>    basic_block latch;
>    edge latch_edge;
>    location_t locus;
> @@ -445,7 +562,6 @@ try_unroll_loop_completely (struct loop 
>      exit = NULL;
>  
>    /* See if we can improve our estimate by using recorded loop bounds.  */
> -  maxiter = max_loop_iterations_int (loop);
>    if (maxiter >= 0
>        && (!n_unroll_found || (unsigned HOST_WIDE_INT)maxiter < n_unroll))
>      {
> @@ -545,6 +661,8 @@ try_unroll_loop_completely (struct loop 
>        free_original_copy_tables ();
>      }
>  
> +  remove_exits_and_undefined_stmts (loop, n_unroll);
> +
>    /* Remove the conditional from the last copy of the loop.  */
>    if (edge_to_cancel)
>      {
> @@ -627,6 +745,8 @@ canonicalize_loop_induction_variables (s
>  {
>    edge exit = NULL;
>    tree niter;
> +  HOST_WIDE_INT maxiter;
> +  bool modified = false;
>  
>    niter = number_of_latch_executions (loop);
>    if (TREE_CODE (niter) == INTEGER_CST)
> @@ -657,6 +777,8 @@ canonicalize_loop_induction_variables (s
>    if (niter && TREE_CODE (niter) == INTEGER_CST)
>      record_niter_bound (loop, tree_to_double_int (niter), false, true);
>  
> +  maxiter = max_loop_iterations_int (loop);
> +
>    if (dump_file && (dump_flags & TDF_DETAILS)
>        && TREE_CODE (niter) == INTEGER_CST)
>      {
> @@ -665,21 +787,28 @@ canonicalize_loop_induction_variables (s
>        fprintf (dump_file, " times.\n");
>      }
>    if (dump_file && (dump_flags & TDF_DETAILS)
> -      && max_loop_iterations_int (loop) >= 0)
> +      && maxiter >= 0)
>      {
>        fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num,
> -	       (int)max_loop_iterations_int (loop));
> +	       (int)maxiter);
>      }
>  
> +  /* Remove exits that are known to be never taken based on loop bound.
> +     Needs to be called after compilation of max_loop_iterations_int that
> +     populates the loop bounds.  */
> +  modified |= remove_redundant_iv_test (loop);
> +
>    if (try_unroll_loop_completely (loop, exit, niter, ul, irred_invalidated,
> -				  loop_closed_ssa_invalidated))
> +				  loop_closed_ssa_invalidated, maxiter))
>      return true;
>  
>    if (create_iv
>        && niter && !chrec_contains_undetermined (niter))
>      create_canonical_iv (loop, exit, niter);
>  
> -  return false;
> +  if (modified)
> +    free_loop_bounds (loop);
> +  return modified;
>  }
>  
>  /* The main entry point of the pass.  Adds canonical induction variables
> Index: cfgloop.h
> ===================================================================
> --- cfgloop.h	(revision 192989)
> +++ cfgloop.h	(working copy)
> @@ -286,6 +286,7 @@ extern unsigned expected_loop_iterations
>  extern rtx doloop_condition_get (rtx);
>  
>  void estimate_numbers_of_iterations_loop (struct loop *);
> +void free_loop_bounds (struct loop *);
>  void record_niter_bound (struct loop *, double_int, bool, bool);
>  bool estimated_loop_iterations (struct loop *, double_int *);
>  bool max_loop_iterations (struct loop *, double_int *);
> Index: testsuite/gcc.dg/tree-ssa/cunroll-10.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/cunroll-10.c	(revision 0)
> +++ testsuite/gcc.dg/tree-ssa/cunroll-10.c	(revision 0)
> @@ -0,0 +1,13 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -Warray-bounds -fdump-tree-cunroll" } */
> +int a[3];
> +int b[4];
> +main()
> +{
> +  int i;
> +  for (i=0;i<4;i++)
> +    if (b[i]==2)
> +     a[i]++;
> +}
> +/* { dg-final { scan-tree-dump-times 2 "Forced statement unreachable:" "cunroll" } } */
> +/* { dg-final { cleanup-tree-dump "cunroll" } } */
> Index: testsuite/gcc.dg/tree-ssa/cunroll-9.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/cunroll-9.c	(revision 0)
> +++ testsuite/gcc.dg/tree-ssa/cunroll-9.c	(revision 0)
> @@ -0,0 +1,21 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-cunrolli" } */
> +int a[10];
> +int b[11];
> +t (int n)
> +{
> +  int i;
> +  int sum = 0;
> +  for (i = 0; i < n; i++)
> +    {
> +      if (i > 1000)
> +	abort ();
> +      if (q ())
> +	sum += a[i];
> +      else
> +	sum += b[i];
> +    }
> +  return sum;
> +}
> +/* { dg-final { scan-tree-dump-times 1 "Removed pointless exit:" "cunroli" } } */
> +/* { dg-final { cleanup-tree-dump "cunroli" } } */
> 
> 

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