Patchwork Non-dominating loop bounds in tree-ssa-loop-niter 1/4

login
register
mail settings
Submitter Jan Hubicka
Date Oct. 30, 2012, 2:51 p.m.
Message ID <20121030145122.GB2803@kam.mff.cuni.cz>
Download mbox | patch
Permalink /patch/195510/
State New
Headers show

Comments

Jan Hubicka - Oct. 30, 2012, 2:51 p.m.
Hi,
this is first patch of change of tree-ssa-loop-niter to consider bounds that are
not in block dominating latch.  This patch makes them to be recorded and they
are not used.  I plan to followup with:

1) patch to add simple shortest path walk at the end of estimate_numbers_of_iterations_loop
   determining bound of i.e.
   int a[10];
   int b[10];
   for (i=0;i<n;i++)
     if (t())
       q(a[i]);
     else
       q(a[i]);
2) make complette loop unrolling to kill all statements known to not be executed
   in the last iteration by __builtin_unreachable to silence part of -Warray-bounds
   warnings currently breaking bootstrap with -O3
3) make duplicate_loop_to_header_edge in peeling mode to do the same silencing
   the rest of warnings
4) make branch prediction code to drop the prediction on exits not dominating
   latch.

Bootstrapped/regtested x86_64-linux, OK?

	* tree-ssa-loop-niter.c (number_of_iterations_exit): New parameter
	EVERY_ITERATION with implicit value of true.
	(record_estimate): Check dominance relationship of the basic block
	we are estimating on instead of relying on UPPER to be false.
	(struct ilb_data): Drop RELIABLE.
	(idx_infer_loop_bounds): Update.
	(infer_loop_bounds_from_ref): Drop parameter RELIABLE.
	(infer_loop_bounds_from_array): Drop parameter RELIABLE.
	(infer_loop_bounds_from_undefined): Update comments and handling
	of RELIABLE.
	(estimate_numbers_of_iterations_loop): Record all bounds.
Richard Guenther - Oct. 30, 2012, 3:01 p.m.
On Tue, 30 Oct 2012, Jan Hubicka wrote:

> Hi,
> this is first patch of change of tree-ssa-loop-niter to consider bounds that are
> not in block dominating latch.  This patch makes them to be recorded and they
> are not used.  I plan to followup with:
> 
> 1) patch to add simple shortest path walk at the end of estimate_numbers_of_iterations_loop
>    determining bound of i.e.
>    int a[10];
>    int b[10];
>    for (i=0;i<n;i++)
>      if (t())
>        q(a[i]);
>      else
>        q(a[i]);
> 2) make complette loop unrolling to kill all statements known to not be executed
>    in the last iteration by __builtin_unreachable to silence part of -Warray-bounds
>    warnings currently breaking bootstrap with -O3
> 3) make duplicate_loop_to_header_edge in peeling mode to do the same silencing
>    the rest of warnings
> 4) make branch prediction code to drop the prediction on exits not dominating
>    latch.
> 
> Bootstrapped/regtested x86_64-linux, OK?

Ok.

Thanks,
Richard.

> 	* tree-ssa-loop-niter.c (number_of_iterations_exit): New parameter
> 	EVERY_ITERATION with implicit value of true.
> 	(record_estimate): Check dominance relationship of the basic block
> 	we are estimating on instead of relying on UPPER to be false.
> 	(struct ilb_data): Drop RELIABLE.
> 	(idx_infer_loop_bounds): Update.
> 	(infer_loop_bounds_from_ref): Drop parameter RELIABLE.
> 	(infer_loop_bounds_from_array): Drop parameter RELIABLE.
> 	(infer_loop_bounds_from_undefined): Update comments and handling
> 	of RELIABLE.
> 	(estimate_numbers_of_iterations_loop): Record all bounds.
> Index: tree-ssa-loop-niter.c
> ===================================================================
> --- tree-ssa-loop-niter.c	(revision 192986)
> +++ tree-ssa-loop-niter.c	(working copy)
> @@ -1793,12 +1793,15 @@ loop_only_exit_p (const struct loop *loo
>     meaning described in comments at struct tree_niter_desc
>     declaration), false otherwise.  If WARN is true and
>     -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
> -   potentially unsafe assumptions.  */
> +   potentially unsafe assumptions.  
> +   When EVERY_ITERATION is true, only tests that are known to be executed
> +   every iteration are considered (i.e. only test that alone bounds the loop). 
> + */
>  
>  bool
>  number_of_iterations_exit (struct loop *loop, edge exit,
>  			   struct tree_niter_desc *niter,
> -			   bool warn)
> +			   bool warn, bool every_iteration)
>  {
>    gimple stmt;
>    tree type;
> @@ -1806,7 +1809,8 @@ number_of_iterations_exit (struct loop *
>    enum tree_code code;
>    affine_iv iv0, iv1;
>  
> -  if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
> +  if (every_iteration
> +      && !dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
>      return false;
>  
>    niter->assumptions = boolean_false_node;
> @@ -2568,6 +2572,11 @@ record_estimate (struct loop *loop, tree
>        loop->bounds = elt;
>      }
>  
> +  /* If statement is executed on every path to the loop latch, we can directly
> +     infer the upper bound on the # of iterations of the loop.  */
> +  if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt)))
> +    return;
> +
>    /* Update the number of iteration estimates according to the bound.
>       If at_stmt is an exit then the loop latch is executed at most BOUND times,
>       otherwise it can be executed BOUND + 1 times.  We will lower the estimate
> @@ -2651,7 +2660,6 @@ struct ilb_data
>  {
>    struct loop *loop;
>    gimple stmt;
> -  bool reliable;
>  };
>  
>  static bool
> @@ -2660,7 +2668,7 @@ idx_infer_loop_bounds (tree base, tree *
>    struct ilb_data *data = (struct ilb_data *) dta;
>    tree ev, init, step;
>    tree low, high, type, next;
> -  bool sign, upper = data->reliable, at_end = false;
> +  bool sign, upper = true, at_end = false;
>    struct loop *loop = data->loop;
>  
>    if (TREE_CODE (base) != ARRAY_REF)
> @@ -2737,14 +2745,12 @@ idx_infer_loop_bounds (tree base, tree *
>     STMT is guaranteed to be executed in every iteration of LOOP.*/
>  
>  static void
> -infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref,
> -			    bool reliable)
> +infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref)
>  {
>    struct ilb_data data;
>  
>    data.loop = loop;
>    data.stmt = stmt;
> -  data.reliable = reliable;
>    for_each_index (&ref, idx_infer_loop_bounds, &data);
>  }
>  
> @@ -2753,7 +2759,7 @@ infer_loop_bounds_from_ref (struct loop 
>     executed in every iteration of LOOP.  */
>  
>  static void
> -infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable)
> +infer_loop_bounds_from_array (struct loop *loop, gimple stmt)
>  {
>    if (is_gimple_assign (stmt))
>      {
> @@ -2763,10 +2769,10 @@ infer_loop_bounds_from_array (struct loo
>        /* For each memory access, analyze its access function
>  	 and record a bound on the loop iteration domain.  */
>        if (REFERENCE_CLASS_P (op0))
> -	infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
> +	infer_loop_bounds_from_ref (loop, stmt, op0);
>  
>        if (REFERENCE_CLASS_P (op1))
> -	infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
> +	infer_loop_bounds_from_ref (loop, stmt, op1);
>      }
>    else if (is_gimple_call (stmt))
>      {
> @@ -2775,13 +2781,13 @@ infer_loop_bounds_from_array (struct loo
>  
>        lhs = gimple_call_lhs (stmt);
>        if (lhs && REFERENCE_CLASS_P (lhs))
> -	infer_loop_bounds_from_ref (loop, stmt, lhs, reliable);
> +	infer_loop_bounds_from_ref (loop, stmt, lhs);
>  
>        for (i = 0; i < n; i++)
>  	{
>  	  arg = gimple_call_arg (stmt, i);
>  	  if (REFERENCE_CLASS_P (arg))
> -	    infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
> +	    infer_loop_bounds_from_ref (loop, stmt, arg);
>  	}
>      }
>  }
> @@ -2910,14 +2916,15 @@ infer_loop_bounds_from_undefined (struct
>  
>        /* If BB is not executed in each iteration of the loop, we cannot
>  	 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.  */
> +	 # 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);
>  
>        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);
> +	  infer_loop_bounds_from_array (loop, stmt);
>  
>  	  if (reliable)
>              {
> @@ -3078,7 +3085,7 @@ estimate_numbers_of_iterations_loop (str
>    likely_exit = single_likely_exit (loop);
>    FOR_EACH_VEC_ELT (edge, exits, i, ex)
>      {
> -      if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
> +      if (!number_of_iterations_exit (loop, ex, &niter_desc, false, false))
>  	continue;
>  
>        niter = niter_desc.niter;
> 
>

Patch

Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c	(revision 192986)
+++ tree-ssa-loop-niter.c	(working copy)
@@ -1793,12 +1793,15 @@  loop_only_exit_p (const struct loop *loo
    meaning described in comments at struct tree_niter_desc
    declaration), false otherwise.  If WARN is true and
    -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
-   potentially unsafe assumptions.  */
+   potentially unsafe assumptions.  
+   When EVERY_ITERATION is true, only tests that are known to be executed
+   every iteration are considered (i.e. only test that alone bounds the loop). 
+ */
 
 bool
 number_of_iterations_exit (struct loop *loop, edge exit,
 			   struct tree_niter_desc *niter,
-			   bool warn)
+			   bool warn, bool every_iteration)
 {
   gimple stmt;
   tree type;
@@ -1806,7 +1809,8 @@  number_of_iterations_exit (struct loop *
   enum tree_code code;
   affine_iv iv0, iv1;
 
-  if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
+  if (every_iteration
+      && !dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
     return false;
 
   niter->assumptions = boolean_false_node;
@@ -2568,6 +2572,11 @@  record_estimate (struct loop *loop, tree
       loop->bounds = elt;
     }
 
+  /* If statement is executed on every path to the loop latch, we can directly
+     infer the upper bound on the # of iterations of the loop.  */
+  if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt)))
+    return;
+
   /* Update the number of iteration estimates according to the bound.
      If at_stmt is an exit then the loop latch is executed at most BOUND times,
      otherwise it can be executed BOUND + 1 times.  We will lower the estimate
@@ -2651,7 +2660,6 @@  struct ilb_data
 {
   struct loop *loop;
   gimple stmt;
-  bool reliable;
 };
 
 static bool
@@ -2660,7 +2668,7 @@  idx_infer_loop_bounds (tree base, tree *
   struct ilb_data *data = (struct ilb_data *) dta;
   tree ev, init, step;
   tree low, high, type, next;
-  bool sign, upper = data->reliable, at_end = false;
+  bool sign, upper = true, at_end = false;
   struct loop *loop = data->loop;
 
   if (TREE_CODE (base) != ARRAY_REF)
@@ -2737,14 +2745,12 @@  idx_infer_loop_bounds (tree base, tree *
    STMT is guaranteed to be executed in every iteration of LOOP.*/
 
 static void
-infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref,
-			    bool reliable)
+infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref)
 {
   struct ilb_data data;
 
   data.loop = loop;
   data.stmt = stmt;
-  data.reliable = reliable;
   for_each_index (&ref, idx_infer_loop_bounds, &data);
 }
 
@@ -2753,7 +2759,7 @@  infer_loop_bounds_from_ref (struct loop 
    executed in every iteration of LOOP.  */
 
 static void
-infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable)
+infer_loop_bounds_from_array (struct loop *loop, gimple stmt)
 {
   if (is_gimple_assign (stmt))
     {
@@ -2763,10 +2769,10 @@  infer_loop_bounds_from_array (struct loo
       /* For each memory access, analyze its access function
 	 and record a bound on the loop iteration domain.  */
       if (REFERENCE_CLASS_P (op0))
-	infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
+	infer_loop_bounds_from_ref (loop, stmt, op0);
 
       if (REFERENCE_CLASS_P (op1))
-	infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
+	infer_loop_bounds_from_ref (loop, stmt, op1);
     }
   else if (is_gimple_call (stmt))
     {
@@ -2775,13 +2781,13 @@  infer_loop_bounds_from_array (struct loo
 
       lhs = gimple_call_lhs (stmt);
       if (lhs && REFERENCE_CLASS_P (lhs))
-	infer_loop_bounds_from_ref (loop, stmt, lhs, reliable);
+	infer_loop_bounds_from_ref (loop, stmt, lhs);
 
       for (i = 0; i < n; i++)
 	{
 	  arg = gimple_call_arg (stmt, i);
 	  if (REFERENCE_CLASS_P (arg))
-	    infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
+	    infer_loop_bounds_from_ref (loop, stmt, arg);
 	}
     }
 }
@@ -2910,14 +2916,15 @@  infer_loop_bounds_from_undefined (struct
 
       /* If BB is not executed in each iteration of the loop, we cannot
 	 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.  */
+	 # 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);
 
       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);
+	  infer_loop_bounds_from_array (loop, stmt);
 
 	  if (reliable)
             {
@@ -3078,7 +3085,7 @@  estimate_numbers_of_iterations_loop (str
   likely_exit = single_likely_exit (loop);
   FOR_EACH_VEC_ELT (edge, exits, i, ex)
     {
-      if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
+      if (!number_of_iterations_exit (loop, ex, &niter_desc, false, false))
 	continue;
 
       niter = niter_desc.niter;