[patch] for PR 25985

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

since recently, # of iteration analysis uses arguments of the following
type:  given loop for (int i = 0; i != n; i += 4) { something; },  we
know that i is signed, thus it cannot overflow, and the loop must be
finite.  This means that n must be divisible by 4 (or the loop would
never exit), and we can compute number of iterations as n/4.

This argument has a serious fault -- it is only correct if loop has
only one exit.  For example, in the following two testcases, this
is incorrect:

for (int i = 0; i != n; i += 4)
  {
    a[i] = i;
    if (i > 100)
      break;
  }

for (int i = 0; i != n; i += 4)
  {
    a[i] = i;
    may_exit (i);
  }

if say n == 1, we would in both cases derive that the loop is exited
immediately, but in fact it rolls until it is exited by the other exit
in the first case, or until may_exit does not return in the second case.

This patch makes us test whether there is only one exit before we use
information about that signed variables do not overflow in # of
iterations analysis.  loop_only_exit_p has linear time complexity in the
size of the loop (due to need to check whether there are any calls
inside the loop); however, this check is only needed if the loop has
single exit, so it is only called once per each loop and optimization
that calls # of iteration analysis, so hopefully this should not be a
problem (the alternatives is to have precomputed whether there is a
non-const function call inside the loop body).

Bootstrapped & regtested on i686 and ia64.

Zdenek

	PR tree-optimization/25985
	* tree-ssa-loop-niter.c (number_of_iterations_le,
	number_of_iterations_ne): Make comments more precise.
	(number_of_iterations_cond): Add only_exit argument.  Use the
	fact that signed variables do not overflow only when only_exit
	is true.
	(loop_only_exit_p): New.
	(number_of_iterations_exit): Pass result of loop_only_exit_p to
	number_of_iterations_cond.

Index: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c	(revision 112083)
--- tree-ssa-loop-niter.c	(working copy)
*************** inverse (tree x, tree mask)
*** 129,137 ****
  /* Determines number of iterations of loop whose ending condition
     is IV <> FINAL.  TYPE is the type of the iv.  The number of
     iterations is stored to NITER.  NEVER_INFINITE is true if
!    we know that the loop cannot be infinite (we derived this
!    earlier, and possibly set NITER->assumptions to make sure this
!    is the case.  */
  
  static bool
  number_of_iterations_ne (tree type, affine_iv *iv, tree final,
--- 129,137 ----
  /* Determines number of iterations of loop whose ending condition
     is IV <> FINAL.  TYPE is the type of the iv.  The number of
     iterations is stored to NITER.  NEVER_INFINITE is true if
!    we know that the exit must be taken eventually, i.e., that the IV
!    ever reaches the value FINAL (we derived this earlier, and possibly set
!    NITER->assumptions to make sure this is the case).  */
  
  static bool
  number_of_iterations_ne (tree type, affine_iv *iv, tree final,
*************** number_of_iterations_lt (tree type, affi
*** 492,500 ****
  /* Determines number of iterations of loop whose ending condition
     is IV0 <= IV1.  TYPE is the type of the iv.  The number of
     iterations is stored to NITER.  NEVER_INFINITE is true if
!    we know that the loop cannot be infinite (we derived this
     earlier, and possibly set NITER->assumptions to make sure this
!    is the case.  */
  
  static bool
  number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
--- 492,500 ----
  /* Determines number of iterations of loop whose ending condition
     is IV0 <= IV1.  TYPE is the type of the iv.  The number of
     iterations is stored to NITER.  NEVER_INFINITE is true if
!    we know that this condition must eventually become false  (we derived this
     earlier, and possibly set NITER->assumptions to make sure this
!    is the case).  */
  
  static bool
  number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
*************** number_of_iterations_le (tree type, affi
*** 538,543 ****
--- 538,548 ----
     is IV0, the right-hand side is IV1.  Both induction variables must have
     type TYPE, which must be an integer or pointer type.  The steps of the
     ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
+ 
+    ONLY_EXIT is true if we are sure this is the only way the loop could be
+    exited (including possibly non-returning function calls, exceptions, etc.)
+    -- in this case we can use the information whether the control induction
+    variables can overflow or not in a more efficient way.
     
     The results (number of iterations and assumptions as described in
     comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
*************** number_of_iterations_le (tree type, affi
*** 546,552 ****
  
  static bool
  number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code,
! 			   affine_iv *iv1, struct tree_niter_desc *niter)
  {
    bool never_infinite;
  
--- 551,558 ----
  
  static bool
  number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code,
! 			   affine_iv *iv1, struct tree_niter_desc *niter,
! 			   bool only_exit)
  {
    bool never_infinite;
  
*************** number_of_iterations_cond (tree type, af
*** 572,584 ****
        code = swap_tree_comparison (code);
      }
  
    if (POINTER_TYPE_P (type))
      {
        /* Comparison of pointers is undefined unless both iv0 and iv1 point
  	 to the same object.  If they do, the control variable cannot wrap
  	 (as wrap around the bounds of memory will never return a pointer
  	 that would be guaranteed to point to the same object, even if we
! 	 avoid undefined behavior by casting to size_t and back).  */
        iv0->no_overflow = true;
        iv1->no_overflow = true;
      }
--- 578,607 ----
        code = swap_tree_comparison (code);
      }
  
+   if (!only_exit)
+     {
+       /* If this is not the only possible exit from the loop, the information
+ 	 that the induction variables cannot overflow as derived from
+ 	 signedness analysis cannot be relied upon.  We use them e.g. in the
+ 	 following way:  given loop for (i = 0; i <= n; i++), if i is
+ 	 signed, it cannot overflow, thus this loop is equivalent to
+ 	 for (i = 0; i < n + 1; i++);  however, if n == MAX, but the loop
+ 	 is exited in some other way before i overflows, this transformation
+ 	 is incorrect (the new loop exits immediately).  */
+       iv0->no_overflow = false;
+       iv1->no_overflow = false;
+     }
+ 
    if (POINTER_TYPE_P (type))
      {
        /* Comparison of pointers is undefined unless both iv0 and iv1 point
  	 to the same object.  If they do, the control variable cannot wrap
  	 (as wrap around the bounds of memory will never return a pointer
  	 that would be guaranteed to point to the same object, even if we
! 	 avoid undefined behavior by casting to size_t and back).  The
! 	 restrictions on pointer arithmetics and comparisons of pointers
! 	 ensure that using the no-overflow assumptions is correct in this
! 	 case even if ONLY_EXIT is false.  */
        iv0->no_overflow = true;
        iv1->no_overflow = true;
      }
*************** simplify_using_outer_evolutions (struct 
*** 963,968 ****
--- 986,1022 ----
    return expr;
  }
  
+ /* Returns true if EXIT is the only possible exit from LOOP.  */
+ 
+ static bool
+ loop_only_exit_p (struct loop *loop, edge exit)
+ {
+   basic_block *body;
+   block_stmt_iterator bsi;
+   unsigned i;
+   tree call;
+ 
+   if (exit != loop->single_exit)
+     return false;
+ 
+   body = get_loop_body (loop);
+   for (i = 0; i < loop->num_nodes; i++)
+     {
+       for (bsi = bsi_start (body[0]); !bsi_end_p (bsi); bsi_next (&bsi))
+ 	{
+ 	  call = get_call_expr_in (bsi_stmt (bsi));
+ 	  if (call && TREE_SIDE_EFFECTS (call))
+ 	    {
+ 	      free (body);
+ 	      return false;
+ 	    }
+ 	}
+     }
+ 
+   free (body);
+   return true;
+ }
+ 
  /* Stores description of number of iterations of LOOP derived from
     EXIT (an exit edge of the LOOP) in NITER.  Returns true if some
     useful information could be derived (and fields of NITER has
*************** number_of_iterations_exit (struct loop *
*** 1023,1029 ****
  
    iv0.base = expand_simple_operations (iv0.base);
    iv1.base = expand_simple_operations (iv1.base);
!   if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter))
      return false;
  
    if (optimize >= 3)
--- 1077,1084 ----
  
    iv0.base = expand_simple_operations (iv0.base);
    iv1.base = expand_simple_operations (iv1.base);
!   if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter,
! 				  loop_only_exit_p (loop, exit)))
      return false;
  
    if (optimize >= 3)