[patch] Test assumptions in # of iterations analysis immediatelly

Zdenek Dvorak rakdver@atrey.karlin.mff.cuni.cz
Wed Apr 12 09:59:00 GMT 2006


Hello,

currently, # of iterations analysis gathers the assumptions under that
the number of iterations is valid (e.g., in
for (unsigned i = 0; i <= n; i++) the assumption that n != ~0) to a
the structure containing the result; afterwards, it tries to prove that
they are satisfied using other information gathered from the program
(conditions before the loop, etc.).

The idea behind this is that some optimizations might want to version
the loop based on these assumptions, then optimize just the copy in that
they are guaranteed to be satisfied.  However, no optimization so far
uses this possibility -- if we are unable to eliminate the assumptions,
we just fail.

This patch makes us to try to eliminate the assumptions directly
instead, failing immediatelly if this is unsuccesful.  This is more
efficient (we do not build the trees for other assumptions and # of
iterations).  It also enables us to provide more precise warnings for
-Wunsafe-loop-optimizations (and potentially gives more flexibility in what
assumptions we check).  If some optimization starts to need the old behavior,
it should be easy to add it as an option.

Bootstrapped & regtested on i686 and ia64.

Zdenek

	* tree-ssa-loop-niter.c (number_of_iterations_ne,
	number_of_iterations_lt_to_ne, assert_no_overflow_lt,
	assert_loop_rolls_lt, number_of_iterations_lt, number_of_iterations_le,
	number_of_iterations_cond): Take the loop and warn arguments.  Test the
	assumptions directly.
	(simplify_by_external_information, adjust_by_unsafe_loop_opts_flag):
	New functions.
	(number_of_iterations_exit): Do not set and eliminate assumptions.
	Do not warn for -Wunsafe-loop-optimizations.
	* tree-flow.h (struct tree_niter_desc): Remove assumptions field.

	* gcc.dg/tree-ssa/pr19210-1.c: Update warning tests.

Index: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c	(revision 112854)
--- tree-ssa-loop-niter.c	(working copy)
*************** inverse (tree x, tree mask)
*** 126,989 ****
    return rslt;
  }
  
! /* 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,
! 			 struct tree_niter_desc *niter, bool never_infinite)
  {
!   tree niter_type = unsigned_type_for (type);
!   tree s, c, d, bits, assumption, tmp, bound;
  
!   niter->control = *iv;
!   niter->bound = final;
!   niter->cmp = NE_EXPR;
  
!   /* Rearrange the terms so that we get inequality s * i <> c, with s
!      positive.  Also cast everything to the unsigned type.  */
!   if (tree_int_cst_sign_bit (iv->step))
!     {
!       s = fold_convert (niter_type,
! 			fold_build1 (NEGATE_EXPR, type, iv->step));
!       c = fold_build2 (MINUS_EXPR, niter_type,
! 		       fold_convert (niter_type, iv->base),
! 		       fold_convert (niter_type, final));
!     }
!   else
!     {
!       s = fold_convert (niter_type, iv->step);
!       c = fold_build2 (MINUS_EXPR, niter_type,
! 		       fold_convert (niter_type, final),
! 		       fold_convert (niter_type, iv->base));
!     }
  
!   /* First the trivial cases -- when the step is 1.  */
!   if (integer_onep (s))
      {
!       niter->niter = c;
!       return true;
!     }
  
!   /* Let nsd (step, size of mode) = d.  If d does not divide c, the loop
!      is infinite.  Otherwise, the number of iterations is
!      (inverse(s/d) * (c/d)) mod (size of mode/d).  */
!   bits = num_ending_zeros (s);
!   bound = build_low_bits_mask (niter_type,
! 			       (TYPE_PRECISION (niter_type)
! 				- tree_low_cst (bits, 1)));
  
!   d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
! 			       build_int_cst (niter_type, 1), bits);
!   s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
  
!   if (!never_infinite)
!     {
!       /* If we cannot assume that the loop is not infinite, record the
! 	 assumptions for divisibility of c.  */
!       assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
!       assumption = fold_build2 (EQ_EXPR, boolean_type_node,
! 				assumption, build_int_cst (niter_type, 0));
!       if (!nonzero_p (assumption))
! 	niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
! 					  niter->assumptions, assumption);
      }
!       
!   c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
!   tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
!   niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
!   return true;
  }
  
! /* Checks whether we can determine the final value of the control variable
!    of the loop with ending condition IV0 < IV1 (computed in TYPE).
!    DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
!    of the step.  The assumptions necessary to ensure that the computation
!    of the final value does not overflow are recorded in NITER.  If we
!    find the final value, we adjust DELTA and return TRUE.  Otherwise
!    we return false.  */
  
! static bool
! number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
! 			       struct tree_niter_desc *niter,
! 			       tree *delta, tree step)
  {
!   tree niter_type = TREE_TYPE (step);
!   tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
!   tree tmod;
!   tree assumption = boolean_true_node, bound, noloop;
  
!   if (TREE_CODE (mod) != INTEGER_CST)
!     return false;
!   if (nonzero_p (mod))
!     mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
!   tmod = fold_convert (type, mod);
  
!   if (nonzero_p (iv0->step))
!     {
!       /* The final value of the iv is iv1->base + MOD, assuming that this
! 	 computation does not overflow, and that
! 	 iv0->base <= iv1->base + MOD.  */
!       if (!iv1->no_overflow && !zero_p (mod))
! 	{
! 	  bound = fold_build2 (MINUS_EXPR, type,
! 			       TYPE_MAX_VALUE (type), tmod);
! 	  assumption = fold_build2 (LE_EXPR, boolean_type_node,
! 				    iv1->base, bound);
! 	  if (zero_p (assumption))
! 	    return false;
! 	}
!       noloop = fold_build2 (GT_EXPR, boolean_type_node,
! 			    iv0->base,
! 			    fold_build2 (PLUS_EXPR, type,
! 					 iv1->base, tmod));
!     }
!   else
      {
!       /* The final value of the iv is iv0->base - MOD, assuming that this
! 	 computation does not overflow, and that
! 	 iv0->base - MOD <= iv1->base. */
!       if (!iv0->no_overflow && !zero_p (mod))
! 	{
! 	  bound = fold_build2 (PLUS_EXPR, type,
! 			       TYPE_MIN_VALUE (type), tmod);
! 	  assumption = fold_build2 (GE_EXPR, boolean_type_node,
! 				    iv0->base, bound);
! 	  if (zero_p (assumption))
! 	    return false;
! 	}
!       noloop = fold_build2 (GT_EXPR, boolean_type_node,
! 			    fold_build2 (MINUS_EXPR, type,
! 					 iv0->base, tmod),
! 			    iv1->base);
      }
  
!   if (!nonzero_p (assumption))
!     niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
! 				      niter->assumptions,
! 				      assumption);
!   if (!zero_p (noloop))
!     niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
! 				      niter->may_be_zero,
! 				      noloop);
!   *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
!   return true;
  }
  
! /* Add assertions to NITER that ensure that the control variable of the loop
!    with ending condition IV0 < IV1 does not overflow.  Types of IV0 and IV1
!    are TYPE.  Returns false if we can prove that there is an overflow, true
!    otherwise.  STEP is the absolute value of the step.  */
  
! static bool
! assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
! 		       struct tree_niter_desc *niter, tree step)
  {
!   tree bound, d, assumption, diff;
!   tree niter_type = TREE_TYPE (step);
  
!   if (nonzero_p (iv0->step))
      {
!       /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
!       if (iv0->no_overflow)
! 	return true;
  
!       /* If iv0->base is a constant, we can determine the last value before
! 	 overflow precisely; otherwise we conservatively assume
! 	 MAX - STEP + 1.  */
  
!       if (TREE_CODE (iv0->base) == INTEGER_CST)
  	{
! 	  d = fold_build2 (MINUS_EXPR, niter_type,
! 			   fold_convert (niter_type, TYPE_MAX_VALUE (type)),
! 			   fold_convert (niter_type, iv0->base));
! 	  diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
  	}
        else
! 	diff = fold_build2 (MINUS_EXPR, niter_type, step,
! 			    build_int_cst (niter_type, 1));
!       bound = fold_build2 (MINUS_EXPR, type,
! 			   TYPE_MAX_VALUE (type), fold_convert (type, diff));
!       assumption = fold_build2 (LE_EXPR, boolean_type_node,
! 				iv1->base, bound);
!     }
!   else
!     {
!       /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
!       if (iv1->no_overflow)
! 	return true;
  
!       if (TREE_CODE (iv1->base) == INTEGER_CST)
  	{
! 	  d = fold_build2 (MINUS_EXPR, niter_type,
! 			   fold_convert (niter_type, iv1->base),
! 			   fold_convert (niter_type, TYPE_MIN_VALUE (type)));
! 	  diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
  	}
!       else
! 	diff = fold_build2 (MINUS_EXPR, niter_type, step,
! 			    build_int_cst (niter_type, 1));
!       bound = fold_build2 (PLUS_EXPR, type,
! 			   TYPE_MIN_VALUE (type), fold_convert (type, diff));
!       assumption = fold_build2 (GE_EXPR, boolean_type_node,
! 				iv0->base, bound);
      }
  
!   if (zero_p (assumption))
!     return false;
!   if (!nonzero_p (assumption))
!     niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
! 				      niter->assumptions, assumption);
!     
!   iv0->no_overflow = true;
!   iv1->no_overflow = true;
!   return true;
  }
  
! /* Add an assumption to NITER that a loop whose ending condition
!    is IV0 < IV1 rolls.  TYPE is the type of the control iv.  */
  
! static void
! assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
! 		      struct tree_niter_desc *niter)
  {
!   tree assumption = boolean_true_node, bound, diff;
!   tree mbz, mbzl, mbzr;
  
!   if (nonzero_p (iv0->step))
!     {
!       diff = fold_build2 (MINUS_EXPR, type,
! 			  iv0->step, build_int_cst (type, 1));
  
!       /* We need to know that iv0->base >= MIN + iv0->step - 1.  Since
! 	 0 address never belongs to any object, we can assume this for
! 	 pointers.  */
!       if (!POINTER_TYPE_P (type))
! 	{
! 	  bound = fold_build2 (PLUS_EXPR, type,
! 			       TYPE_MIN_VALUE (type), diff);
! 	  assumption = fold_build2 (GE_EXPR, boolean_type_node,
! 				    iv0->base, bound);
! 	}
  
!       /* And then we can compute iv0->base - diff, and compare it with
! 	 iv1->base.  */      
!       mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff);
!       mbzr = iv1->base;
!     }
!   else
      {
!       diff = fold_build2 (PLUS_EXPR, type,
! 			  iv1->step, build_int_cst (type, 1));
  
!       if (!POINTER_TYPE_P (type))
! 	{
! 	  bound = fold_build2 (PLUS_EXPR, type,
! 			       TYPE_MAX_VALUE (type), diff);
! 	  assumption = fold_build2 (LE_EXPR, boolean_type_node,
! 				    iv1->base, bound);
! 	}
  
!       mbzl = iv0->base;
!       mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff);
!     }
  
!   mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
  
!   if (!nonzero_p (assumption))
!     niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
! 				      niter->assumptions, assumption);
!   if (!zero_p (mbz))
!     niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
! 				      niter->may_be_zero, mbz);
  }
  
! /* 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.  */
  
! static bool
! number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
! 			 struct tree_niter_desc *niter,
! 			 bool never_infinite ATTRIBUTE_UNUSED)
  {
!   tree niter_type = unsigned_type_for (type);
!   tree delta, step, s;
! 
!   if (nonzero_p (iv0->step))
!     {
!       niter->control = *iv0;
!       niter->cmp = LT_EXPR;
!       niter->bound = iv1->base;
!     }
!   else
!     {
!       niter->control = *iv1;
!       niter->cmp = GT_EXPR;
!       niter->bound = iv0->base;
!     }
  
!   delta = fold_build2 (MINUS_EXPR, niter_type,
! 		       fold_convert (niter_type, iv1->base),
! 		       fold_convert (niter_type, iv0->base));
  
!   /* First handle the special case that the step is +-1.  */
!   if ((iv0->step && integer_onep (iv0->step)
!        && zero_p (iv1->step))
!       || (iv1->step && integer_all_onesp (iv1->step)
! 	  && zero_p (iv0->step)))
      {
!       /* for (i = iv0->base; i < iv1->base; i++)
! 
! 	 or
  
! 	 for (i = iv1->base; i > iv0->base; i--).
! 	     
! 	 In both cases # of iterations is iv1->base - iv0->base, assuming that
! 	 iv1->base >= iv0->base.  */
!       niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
! 					iv1->base, iv0->base);
!       niter->niter = delta;
!       return true;
!     }
  
!   if (nonzero_p (iv0->step))
!     step = fold_convert (niter_type, iv0->step);
!   else
!     step = fold_convert (niter_type,
! 			 fold_build1 (NEGATE_EXPR, type, iv1->step));
  
!   /* If we can determine the final value of the control iv exactly, we can
!      transform the condition to != comparison.  In particular, this will be
!      the case if DELTA is constant.  */
!   if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step))
!     {
!       affine_iv zps;
  
!       zps.base = build_int_cst (niter_type, 0);
!       zps.step = step;
!       /* number_of_iterations_lt_to_ne will add assumptions that ensure that
! 	 zps does not overflow.  */
!       zps.no_overflow = true;
  
!       return number_of_iterations_ne (type, &zps, delta, niter, true);
      }
  
!   /* Make sure that the control iv does not overflow.  */
!   if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
!     return false;
! 
!   /* We determine the number of iterations as (delta + step - 1) / step.  For
!      this to work, we must know that iv1->base >= iv0->base - step + 1,
!      otherwise the loop does not roll.  */
!   assert_loop_rolls_lt (type, iv0, iv1, niter);
  
!   s = fold_build2 (MINUS_EXPR, niter_type,
! 		   step, build_int_cst (niter_type, 1));
!   delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
!   niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
!   return true;
  }
  
! /* 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,
! 			 struct tree_niter_desc *niter, bool never_infinite)
  {
!   tree assumption;
  
!   /* Say that IV0 is the control variable.  Then IV0 <= IV1 iff
!      IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
!      value of the type.  This we must know anyway, since if it is
!      equal to this value, the loop rolls forever.  */
  
!   if (!never_infinite)
!     {
!       if (nonzero_p (iv0->step))
! 	assumption = fold_build2 (NE_EXPR, boolean_type_node,
! 				  iv1->base, TYPE_MAX_VALUE (type));
!       else
! 	assumption = fold_build2 (NE_EXPR, boolean_type_node,
! 				  iv0->base, TYPE_MIN_VALUE (type));
  
!       if (zero_p (assumption))
! 	return false;
!       if (!nonzero_p (assumption))
! 	niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
! 					  niter->assumptions, assumption);
      }
  
!   if (nonzero_p (iv0->step))
!     iv1->base = fold_build2 (PLUS_EXPR, type,
! 			     iv1->base, build_int_cst (type, 1));
    else
!     iv0->base = fold_build2 (MINUS_EXPR, type,
! 			     iv0->base, build_int_cst (type, 1));
!   return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
  }
  
! /* Determine the number of iterations according to condition (for staying
!    inside loop) which compares two induction variables using comparison
!    operator CODE.  The induction variable on left side of the comparison
!    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.
!    Returns false if it fails to determine number of iterations, true if it
!    was determined (possibly with some assumptions).  */
  
  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;
! 
!   /* The meaning of these assumptions is this:
!      if !assumptions
!        then the rest of information does not have to be valid
!      if may_be_zero then the loop does not roll, even if
!        niter != 0.  */
!   niter->assumptions = boolean_true_node;
!   niter->may_be_zero = boolean_false_node;
!   niter->niter = NULL_TREE;
!   niter->additional_info = boolean_true_node;
  
!   niter->bound = NULL_TREE;
!   niter->cmp = ERROR_MARK;
  
!   /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
!      the control variable is on lhs.  */
!   if (code == GE_EXPR || code == GT_EXPR
!       || (code == NE_EXPR && zero_p (iv0->step)))
      {
!       SWAP (iv0, iv1);
!       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;
      }
  
!   /* If the control induction variable does not overflow, the loop obviously
!      cannot be infinite.  */
!   if (!zero_p (iv0->step) && iv0->no_overflow)
!     never_infinite = true;
!   else if (!zero_p (iv1->step) && iv1->no_overflow)
!     never_infinite = true;
!   else
!     never_infinite = false;
  
!   /* We can handle the case when neither of the sides of the comparison is
!      invariant, provided that the test is NE_EXPR.  This rarely occurs in
!      practice, but it is simple enough to manage.  */
!   if (!zero_p (iv0->step) && !zero_p (iv1->step))
      {
!       if (code != NE_EXPR)
! 	return false;
  
!       iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
! 					   iv0->step, iv1->step);
!       iv0->no_overflow = false;
!       iv1->step = NULL_TREE;
!       iv1->no_overflow = true;
      }
  
!   /* If the result of the comparison is a constant,  the loop is weird.  More
!      precise handling would be possible, but the situation is not common enough
!      to waste time on it.  */
!   if (zero_p (iv0->step) && zero_p (iv1->step))
      return false;
  
!   /* Ignore loops of while (i-- < 10) type.  */
!   if (code != NE_EXPR)
      {
!       if (iv0->step && tree_int_cst_sign_bit (iv0->step))
! 	return false;
  
!       if (!zero_p (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
! 	return false;
      }
! 
!   /* If the loop exits immediately, there is nothing to do.  */
!   if (zero_p (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
      {
!       niter->niter = build_int_cst (unsigned_type_for (type), 0);
!       return true;
!     }
  
!   /* OK, now we know we have a senseful loop.  Handle several cases, depending
!      on what comparison operator is used.  */
!   switch (code)
!     {
!     case NE_EXPR:
!       gcc_assert (zero_p (iv1->step));
!       return number_of_iterations_ne (type, iv0, iv1->base, niter, never_infinite);
!     case LT_EXPR:
!       return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
!     case LE_EXPR:
!       return number_of_iterations_le (type, iv0, iv1, niter, never_infinite);
!     default:
!       gcc_unreachable ();
      }
  }
  
! /* Substitute NEW for OLD in EXPR and fold the result.  */
  
! static tree
! simplify_replace_tree (tree expr, tree old, tree new)
! {
!   unsigned i, n;
!   tree ret = NULL_TREE, e, se;
  
!   if (!expr)
!     return NULL_TREE;
  
!   if (expr == old
!       || operand_equal_p (expr, old, 0))
!     return unshare_expr (new);
  
!   if (!EXPR_P (expr))
!     return expr;
  
!   n = TREE_CODE_LENGTH (TREE_CODE (expr));
!   for (i = 0; i < n; i++)
      {
!       e = TREE_OPERAND (expr, i);
!       se = simplify_replace_tree (e, old, new);
!       if (e == se)
! 	continue;
  
!       if (!ret)
! 	ret = copy_node (expr);
  
!       TREE_OPERAND (ret, i) = se;
!     }
  
!   return (ret ? fold (ret) : expr);
  }
  
! /* Expand definitions of ssa names in EXPR as long as they are simple
!    enough, and return the new expression.  */
! 
! tree
! expand_simple_operations (tree expr)
! {
!   unsigned i, n;
!   tree ret = NULL_TREE, e, ee, stmt;
!   enum tree_code code;
  
!   if (expr == NULL_TREE)
!     return expr;
  
!   if (is_gimple_min_invariant (expr))
!     return expr;
  
!   code = TREE_CODE (expr);
!   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
      {
!       n = TREE_CODE_LENGTH (code);
!       for (i = 0; i < n; i++)
  	{
! 	  e = TREE_OPERAND (expr, i);
! 	  ee = expand_simple_operations (e);
! 	  if (e == ee)
! 	    continue;
  
! 	  if (!ret)
! 	    ret = copy_node (expr);
  
! 	  TREE_OPERAND (ret, i) = ee;
  	}
  
!       return (ret ? fold (ret) : expr);
      }
  
!   if (TREE_CODE (expr) != SSA_NAME)
!     return expr;
  
!   stmt = SSA_NAME_DEF_STMT (expr);
!   if (TREE_CODE (stmt) != MODIFY_EXPR)
!     return expr;
  
!   e = TREE_OPERAND (stmt, 1);
!   if (/* Casts are simple.  */
!       TREE_CODE (e) != NOP_EXPR
!       && TREE_CODE (e) != CONVERT_EXPR
!       /* Copies are simple.  */
!       && TREE_CODE (e) != SSA_NAME
!       /* Assignments of invariants are simple.  */
!       && !is_gimple_min_invariant (e)
!       /* And increments and decrements by a constant are simple.  */
!       && !((TREE_CODE (e) == PLUS_EXPR
! 	    || TREE_CODE (e) == MINUS_EXPR)
! 	   && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
!     return expr;
  
!   return expand_simple_operations (e);
  }
  
! /* Tries to simplify EXPR using the condition COND.  Returns the simplified
!    expression (or EXPR unchanged, if no simplification was possible).  */
  
! static tree
! tree_simplify_using_condition_1 (tree cond, tree expr)
! {
!   bool changed;
!   tree e, te, e0, e1, e2, notcond;
!   enum tree_code code = TREE_CODE (expr);
  
!   if (code == INTEGER_CST)
!     return expr;
  
!   if (code == TRUTH_OR_EXPR
!       || code == TRUTH_AND_EXPR
!       || code == COND_EXPR)
      {
!       changed = false;
! 
!       e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
!       if (TREE_OPERAND (expr, 0) != e0)
! 	changed = true;
  
!       e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
!       if (TREE_OPERAND (expr, 1) != e1)
! 	changed = true;
  
!       if (code == COND_EXPR)
! 	{
! 	  e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
! 	  if (TREE_OPERAND (expr, 2) != e2)
! 	    changed = true;
! 	}
!       else
! 	e2 = NULL_TREE;
  
!       if (changed)
! 	{
! 	  if (code == COND_EXPR)
! 	    expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
! 	  else
! 	    expr = fold_build2 (code, boolean_type_node, e0, e1);
! 	}
  
!       return expr;
      }
  
!   /* In case COND is equality, we may be able to simplify EXPR by copy/constant
!      propagation, and vice versa.  Fold does not handle this, since it is
!      considered too expensive.  */
!   if (TREE_CODE (cond) == EQ_EXPR)
      {
!       e0 = TREE_OPERAND (cond, 0);
!       e1 = TREE_OPERAND (cond, 1);
  
!       /* We know that e0 == e1.  Check whether we cannot simplify expr
! 	 using this fact.  */
!       e = simplify_replace_tree (expr, e0, e1);
!       if (zero_p (e) || nonzero_p (e))
! 	return e;
  
!       e = simplify_replace_tree (expr, e1, e0);
!       if (zero_p (e) || nonzero_p (e))
! 	return e;
      }
-   if (TREE_CODE (expr) == EQ_EXPR)
-     {
-       e0 = TREE_OPERAND (expr, 0);
-       e1 = TREE_OPERAND (expr, 1);
  
!       /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true.  */
!       e = simplify_replace_tree (cond, e0, e1);
!       if (zero_p (e))
! 	return e;
!       e = simplify_replace_tree (cond, e1, e0);
!       if (zero_p (e))
! 	return e;
!     }
!   if (TREE_CODE (expr) == NE_EXPR)
!     {
!       e0 = TREE_OPERAND (expr, 0);
!       e1 = TREE_OPERAND (expr, 1);
  
!       /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true.  */
!       e = simplify_replace_tree (cond, e0, e1);
!       if (zero_p (e))
! 	return boolean_true_node;
!       e = simplify_replace_tree (cond, e1, e0);
!       if (zero_p (e))
! 	return boolean_true_node;
!     }
  
!   te = expand_simple_operations (expr);
  
!   /* Check whether COND ==> EXPR.  */
!   notcond = invert_truthvalue (cond);
!   e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
!   if (nonzero_p (e))
!     return e;
  
!   /* Check whether COND ==> not EXPR.  */
!   e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
!   if (e && zero_p (e))
!     return e;
  
!   return expr;
  }
  
! /* Tries to simplify EXPR using the condition COND.  Returns the simplified
!    expression (or EXPR unchanged, if no simplification was possible).
!    Wrapper around tree_simplify_using_condition_1 that ensures that chains
!    of simple operations in definitions of ssa names in COND are expanded,
!    so that things like casts or incrementing the value of the bound before
!    the loop do not cause us to fail.  */
! 
! static tree
! tree_simplify_using_condition (tree cond, tree expr)
! {
!   cond = expand_simple_operations (cond);
  
!   return tree_simplify_using_condition_1 (cond, expr);
! }
!      
! /* Tries to simplify EXPR using the conditions on entry to LOOP.
!    Record the conditions used for simplification to CONDS_USED.
!    Returns the simplified expression (or EXPR unchanged, if no
!    simplification was possible).*/
  
! static tree
! simplify_using_initial_conditions (struct loop *loop, tree expr,
! 				   tree *conds_used)
  {
!   edge e;
!   basic_block bb;
!   tree exp, cond;
! 
!   if (TREE_CODE (expr) == INTEGER_CST)
!     return expr;
  
!   for (bb = loop->header;
!        bb != ENTRY_BLOCK_PTR;
!        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
!     {
!       if (!single_pred_p (bb))
! 	continue;
!       e = single_pred_edge (bb);
  
!       if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
! 	continue;
  
!       cond = COND_EXPR_COND (last_stmt (e->src));
!       if (e->flags & EDGE_FALSE_VALUE)
! 	cond = invert_truthvalue (cond);
!       exp = tree_simplify_using_condition (cond, expr);
  
!       if (exp != expr)
! 	*conds_used = fold_build2 (TRUTH_AND_EXPR,
! 				   boolean_type_node,
! 				   *conds_used,
! 				   cond);
  
!       expr = exp;
      }
  
!   return expr;
! }
  
! /* Tries to simplify EXPR using the evolutions of the loop invariants
!    in the superloops of LOOP.  Returns the simplified expression
!    (or EXPR unchanged, if no simplification was possible).  */
  
! static tree
! simplify_using_outer_evolutions (struct loop *loop, tree expr)
! {
!   enum tree_code code = TREE_CODE (expr);
!   bool changed;
!   tree e, e0, e1, e2;
  
!   if (is_gimple_min_invariant (expr))
!     return expr;
  
!   if (code == TRUTH_OR_EXPR
!       || code == TRUTH_AND_EXPR
!       || code == COND_EXPR)
      {
!       changed = false;
  
!       e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
!       if (TREE_OPERAND (expr, 0) != e0)
! 	changed = true;
  
!       e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
!       if (TREE_OPERAND (expr, 1) != e1)
! 	changed = true;
  
!       if (code == COND_EXPR)
! 	{
! 	  e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
! 	  if (TREE_OPERAND (expr, 2) != e2)
! 	    changed = true;
! 	}
!       else
! 	e2 = NULL_TREE;
  
!       if (changed)
! 	{
! 	  if (code == COND_EXPR)
! 	    expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
! 	  else
! 	    expr = fold_build2 (code, boolean_type_node, e0, e1);
! 	}
  
!       return expr;
      }
  
!   e = instantiate_parameters (loop, expr);
!   if (is_gimple_min_invariant (e))
!     return e;
  
!   return expr;
  }
  
  /* Returns true if EXIT is the only possible exit from LOOP.  */
--- 126,1126 ----
    return rslt;
  }
  
! /* Expand definitions of ssa names in EXPR as long as they are simple
!    enough, and return the new expression.  */
  
! tree
! expand_simple_operations (tree expr)
  {
!   unsigned i, n;
!   tree ret = NULL_TREE, e, ee, stmt;
!   enum tree_code code;
  
!   if (expr == NULL_TREE)
!     return expr;
  
!   if (is_gimple_min_invariant (expr))
!     return expr;
  
!   code = TREE_CODE (expr);
!   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
      {
!       n = TREE_CODE_LENGTH (code);
!       for (i = 0; i < n; i++)
! 	{
! 	  e = TREE_OPERAND (expr, i);
! 	  ee = expand_simple_operations (e);
! 	  if (e == ee)
! 	    continue;
  
! 	  if (!ret)
! 	    ret = copy_node (expr);
  
! 	  TREE_OPERAND (ret, i) = ee;
! 	}
  
!       return (ret ? fold (ret) : expr);
      }
! 
!   if (TREE_CODE (expr) != SSA_NAME)
!     return expr;
! 
!   stmt = SSA_NAME_DEF_STMT (expr);
!   if (TREE_CODE (stmt) != MODIFY_EXPR)
!     return expr;
! 
!   e = TREE_OPERAND (stmt, 1);
!   if (/* Casts are simple.  */
!       TREE_CODE (e) != NOP_EXPR
!       && TREE_CODE (e) != CONVERT_EXPR
!       /* Copies are simple.  */
!       && TREE_CODE (e) != SSA_NAME
!       /* Assignments of invariants are simple.  */
!       && !is_gimple_min_invariant (e)
!       /* And increments and decrements by a constant are simple.  */
!       && !((TREE_CODE (e) == PLUS_EXPR
! 	    || TREE_CODE (e) == MINUS_EXPR)
! 	   && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
!     return expr;
! 
!   return expand_simple_operations (e);
  }
  
! /* Substitute NEW for OLD in EXPR and fold the result.  */
  
! static tree
! simplify_replace_tree (tree expr, tree old, tree new)
  {
!   unsigned i, n;
!   tree ret = NULL_TREE, e, se;
  
!   if (!expr)
!     return NULL_TREE;
  
!   if (expr == old
!       || operand_equal_p (expr, old, 0))
!     return unshare_expr (new);
! 
!   if (!EXPR_P (expr))
!     return expr;
! 
!   n = TREE_CODE_LENGTH (TREE_CODE (expr));
!   for (i = 0; i < n; i++)
      {
!       e = TREE_OPERAND (expr, i);
!       se = simplify_replace_tree (e, old, new);
!       if (e == se)
! 	continue;
! 
!       if (!ret)
! 	ret = copy_node (expr);
! 
!       TREE_OPERAND (ret, i) = se;
      }
  
!   return (ret ? fold (ret) : expr);
  }
  
! /* Tries to simplify EXPR using the condition COND.  Returns the simplified
!    expression (or EXPR unchanged, if no simplification was possible).  */
  
! static tree
! tree_simplify_using_condition_1 (tree cond, tree expr)
  {
!   bool changed;
!   tree e, te, e0, e1, e2, notcond;
!   enum tree_code code = TREE_CODE (expr);
  
!   if (code == INTEGER_CST)
!     return expr;
! 
!   if (code == TRUTH_OR_EXPR
!       || code == TRUTH_AND_EXPR
!       || code == COND_EXPR)
      {
!       changed = false;
  
!       e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
!       if (TREE_OPERAND (expr, 0) != e0)
! 	changed = true;
  
!       e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
!       if (TREE_OPERAND (expr, 1) != e1)
! 	changed = true;
! 
!       if (code == COND_EXPR)
  	{
! 	  e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
! 	  if (TREE_OPERAND (expr, 2) != e2)
! 	    changed = true;
  	}
        else
! 	e2 = NULL_TREE;
  
!       if (changed)
  	{
! 	  if (code == COND_EXPR)
! 	    expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
! 	  else
! 	    expr = fold_build2 (code, boolean_type_node, e0, e1);
  	}
! 
!       return expr;
!     }
! 
!   /* In case COND is equality, we may be able to simplify EXPR by copy/constant
!      propagation, and vice versa.  Fold does not handle this, since it is
!      considered too expensive.  */
!   if (TREE_CODE (cond) == EQ_EXPR)
!     {
!       e0 = TREE_OPERAND (cond, 0);
!       e1 = TREE_OPERAND (cond, 1);
! 
!       /* We know that e0 == e1.  Check whether we cannot simplify expr
! 	 using this fact.  */
!       e = simplify_replace_tree (expr, e0, e1);
!       if (zero_p (e) || nonzero_p (e))
! 	return e;
! 
!       e = simplify_replace_tree (expr, e1, e0);
!       if (zero_p (e) || nonzero_p (e))
! 	return e;
!     }
!   if (TREE_CODE (expr) == EQ_EXPR)
!     {
!       e0 = TREE_OPERAND (expr, 0);
!       e1 = TREE_OPERAND (expr, 1);
! 
!       /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true.  */
!       e = simplify_replace_tree (cond, e0, e1);
!       if (zero_p (e))
! 	return e;
!       e = simplify_replace_tree (cond, e1, e0);
!       if (zero_p (e))
! 	return e;
      }
+   if (TREE_CODE (expr) == NE_EXPR)
+     {
+       e0 = TREE_OPERAND (expr, 0);
+       e1 = TREE_OPERAND (expr, 1);
+ 
+       /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true.  */
+       e = simplify_replace_tree (cond, e0, e1);
+       if (zero_p (e))
+ 	return boolean_true_node;
+       e = simplify_replace_tree (cond, e1, e0);
+       if (zero_p (e))
+ 	return boolean_true_node;
+     }
+ 
+   te = expand_simple_operations (expr);
+ 
+   /* Check whether COND ==> EXPR.  */
+   notcond = invert_truthvalue (cond);
+   e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
+   if (nonzero_p (e))
+     return e;
  
!   /* Check whether COND ==> not EXPR.  */
!   e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
!   if (e && zero_p (e))
!     return e;
! 
!   return expr;
  }
  
! /* Tries to simplify EXPR using the condition COND.  Returns the simplified
!    expression (or EXPR unchanged, if no simplification was possible).
!    Wrapper around tree_simplify_using_condition_1 that ensures that chains
!    of simple operations in definitions of ssa names in COND are expanded,
!    so that things like casts or incrementing the value of the bound before
!    the loop do not cause us to fail.  */
  
! static tree
! tree_simplify_using_condition (tree cond, tree expr)
  {
!   cond = expand_simple_operations (cond);
  
!   return tree_simplify_using_condition_1 (cond, expr);
! }
!      
! /* Tries to simplify EXPR using the conditions on entry to LOOP.
!    Record the conditions used for simplification to CONDS_USED.
!    Returns the simplified expression (or EXPR unchanged, if no
!    simplification was possible).*/
  
! static tree
! simplify_using_initial_conditions (struct loop *loop, tree expr,
! 				   tree *conds_used)
! {
!   edge e;
!   basic_block bb;
!   tree exp, cond;
  
!   if (TREE_CODE (expr) == INTEGER_CST)
!     return expr;
! 
!   for (bb = loop->header;
!        bb != ENTRY_BLOCK_PTR;
!        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
      {
!       if (!single_pred_p (bb))
! 	continue;
!       e = single_pred_edge (bb);
  
!       if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
! 	continue;
  
!       cond = COND_EXPR_COND (last_stmt (e->src));
!       if (e->flags & EDGE_FALSE_VALUE)
! 	cond = invert_truthvalue (cond);
!       exp = tree_simplify_using_condition (cond, expr);
  
!       if (exp != expr)
! 	*conds_used = fold_build2 (TRUTH_AND_EXPR,
! 				   boolean_type_node,
! 				   *conds_used,
! 				   cond);
  
!       expr = exp;
!     }
! 
!   return expr;
  }
  
! /* Tries to simplify EXPR using the evolutions of the loop invariants
!    in the superloops of LOOP.  Returns the simplified expression
!    (or EXPR unchanged, if no simplification was possible).  */
  
! static tree
! simplify_using_outer_evolutions (struct loop *loop, tree expr)
  {
!   enum tree_code code = TREE_CODE (expr);
!   bool changed;
!   tree e, e0, e1, e2;
  
!   if (is_gimple_min_invariant (expr))
!     return expr;
  
!   if (code == TRUTH_OR_EXPR
!       || code == TRUTH_AND_EXPR
!       || code == COND_EXPR)
      {
!       changed = false;
  
!       e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
!       if (TREE_OPERAND (expr, 0) != e0)
! 	changed = true;
  
!       e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
!       if (TREE_OPERAND (expr, 1) != e1)
! 	changed = true;
  
!       if (code == COND_EXPR)
! 	{
! 	  e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
! 	  if (TREE_OPERAND (expr, 2) != e2)
! 	    changed = true;
! 	}
!       else
! 	e2 = NULL_TREE;
  
!       if (changed)
! 	{
! 	  if (code == COND_EXPR)
! 	    expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
! 	  else
! 	    expr = fold_build2 (code, boolean_type_node, e0, e1);
! 	}
  
!       return expr;
      }
  
!   e = instantiate_parameters (loop, expr);
!   if (is_gimple_min_invariant (e))
!     return e;
  
!   return expr;
  }
  
! /* Attempts to simplify condition EXPR using conditions before LOOP,
!    and possibly also using evolutions in the outer loops.  The conditions
!    used are recorded in ADDITIONAL_INFO.  */
  
! static void
! simplify_by_external_information (struct loop *loop, tree *expr,
! 				  tree *additional_info)
  {
!   if (TREE_CODE (*expr) == INTEGER_CST)
!     return;
  
!   if (TREE_TYPE (*expr) == boolean_type_node)
!     *expr = simplify_using_initial_conditions (loop, *expr, additional_info);
  
!   if (optimize < 3 || TREE_CODE (*expr) == INTEGER_CST)
!     return;
  
!   *expr = simplify_using_outer_evolutions (loop, *expr);
! }
! 
! /* With -funsafe-loop-optimizations, set EXPR to true unless it is always
!    false.  If we replaced (or could replace) a nontrivial condition this
!    way, and WARN is not NULL, issue the appropriate warning, using the
!    MESSAGE_PERFORMED wording if -funsafe-loop-optimizations and
!    MESSAGE_BLOCKED wording if -fno-unsafe-loop-optimizations.  */
! 
! static void
! adjust_by_unsafe_loop_opts_flag (tree *expr, tree warn,
! 				 const char *message_blocked,
! 				 const char *message_performed)
! {
!   const char *wording;
!   location_t loc;
!   if (!warn || zero_p (*expr) || nonzero_p (*expr))
!     return;
!  
!   loc = EXPR_LOCATION (warn);
!   if (flag_unsafe_loop_optimizations)
!     {
!       *expr = boolean_true_node;
!       wording = message_performed;
      }
+   else
+     wording = message_blocked;
  
!   if (!wording)
!     return;
! 
!   if (LOCATION_LINE (loc) > 0)
!     warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
    else
!     warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
  }
  
! /* 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
!    the assumptions to make sure this is the case).  LOOP is the
!    loop in that the condition appears.
  
!    WARN is the statement for that we should issue warning about usage of
!    unsafe assumptions, or NULL if we should not issue this warning.  */
  
  static bool
! number_of_iterations_ne (struct loop *loop, tree type, affine_iv *iv,
! 			 tree final, struct tree_niter_desc *niter,
! 			 bool never_infinite, tree warn)
  {
!   tree niter_type = unsigned_type_for (type);
!   tree s, c, d, bits, assumption, tmp, bound;
  
!   niter->control = *iv;
!   niter->bound = final;
!   niter->cmp = NE_EXPR;
  
!   /* Rearrange the terms so that we get inequality s * i <> c, with s
!      positive.  Also cast everything to the unsigned type.  */
!   if (tree_int_cst_sign_bit (iv->step))
      {
!       s = fold_convert (niter_type,
! 			fold_build1 (NEGATE_EXPR, type, iv->step));
!       c = fold_build2 (MINUS_EXPR, niter_type,
! 		       fold_convert (niter_type, iv->base),
! 		       fold_convert (niter_type, final));
      }
!   else
      {
!       s = fold_convert (niter_type, iv->step);
!       c = fold_build2 (MINUS_EXPR, niter_type,
! 		       fold_convert (niter_type, final),
! 		       fold_convert (niter_type, iv->base));
      }
  
!   /* First the trivial cases -- when the step is 1.  */
!   if (integer_onep (s))
      {
!       niter->niter = c;
!       return true;
      }
  
!   /* Let nsd (step, size of mode) = d.  If d does not divide c, the loop
!      is infinite.  Otherwise, the number of iterations is
!      (inverse(s/d) * (c/d)) mod (size of mode/d).  */
!   bits = num_ending_zeros (s);
!   bound = build_low_bits_mask (niter_type,
! 			       (TYPE_PRECISION (niter_type)
! 				- tree_low_cst (bits, 1)));
  
!   d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
! 			       build_int_cst (niter_type, 1), bits);
!   s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
! 
!   if (!never_infinite)
      {
!       /* If we cannot assume that the loop is not infinite, check the
! 	 assumptions for divisibility of c.  */
!       assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
!       assumption = fold_build2 (EQ_EXPR, boolean_type_node,
! 				assumption, build_int_cst (niter_type, 0));
!       simplify_by_external_information (loop, &assumption,
! 					&niter->additional_info);
!       adjust_by_unsafe_loop_opts_flag (
! 	&assumption, warn,
! 	N_("cannot optimize loop as the control variable may miss the final value"),
! 	N_("assuming that the control variable of the loop does not miss the final value"));
  
!       if (!nonzero_p (assumption))
! 	return false;
      }
+       
+   c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
+   tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
+   niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
+   return true;
+ }
  
! /* Checks whether we can determine the final value of the control variable
!    of the LOOP with ending condition IV0 < IV1 (computed in TYPE).
!    DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
!    of the step.  The assumptions necessary to ensure that the computation
!    of the final value does not overflow are recorded in NITER.  If we
!    find the final value, we adjust DELTA and return TRUE.  Otherwise
!    we return false.
! 
!    WARN is the statement for that we should issue warning about usage of
!    unsafe assumptions, or NULL if we should not issue this warning.  */
! 
! static bool
! number_of_iterations_lt_to_ne (struct loop *loop,
! 			       tree type, affine_iv *iv0, affine_iv *iv1,
! 			       struct tree_niter_desc *niter,
! 			       tree *delta, tree step, tree warn)
! {
!   tree niter_type = TREE_TYPE (step);
!   tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
!   tree tmod;
!   tree assumption = boolean_true_node, bound, noloop;
! 
!   if (TREE_CODE (mod) != INTEGER_CST)
      return false;
+   if (nonzero_p (mod))
+     mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
+   tmod = fold_convert (type, mod);
  
!   if (nonzero_p (iv0->step))
      {
!       /* The final value of the iv is iv1->base + MOD, assuming that this
! 	 computation does not overflow, and that
! 	 iv0->base <= iv1->base + MOD.  */
!       if (!iv1->no_overflow && !zero_p (mod))
! 	{
! 	  bound = fold_build2 (MINUS_EXPR, type,
! 			       TYPE_MAX_VALUE (type), tmod);
! 	  assumption = fold_build2 (LE_EXPR, boolean_type_node,
! 				    iv1->base, bound);
  
! 	  simplify_by_external_information (loop, &assumption,
! 					    &niter->additional_info);
! 	  adjust_by_unsafe_loop_opts_flag (
! 	    &assumption, warn,
! 	    NULL,
! 	    N_("assuming that the control variable of the loop does not overflow"));
! 	  if (!nonzero_p (assumption))
! 	    return false;
! 	}
!       noloop = fold_build2 (GT_EXPR, boolean_type_node,
! 			    iv0->base,
! 			    fold_build2 (PLUS_EXPR, type,
! 					 iv1->base, tmod));
      }
!   else
      {
!       /* The final value of the iv is iv0->base - MOD, assuming that this
! 	 computation does not overflow, and that
! 	 iv0->base - MOD <= iv1->base. */
!       if (!iv0->no_overflow && !zero_p (mod))
! 	{
! 	  bound = fold_build2 (PLUS_EXPR, type,
! 			       TYPE_MIN_VALUE (type), tmod);
! 	  assumption = fold_build2 (GE_EXPR, boolean_type_node,
! 				    iv0->base, bound);
  
! 	  simplify_by_external_information (loop, &assumption,
! 					    &niter->additional_info);
! 	  adjust_by_unsafe_loop_opts_flag (
! 	    &assumption, warn,
! 	    NULL,
! 	    N_("assuming that the control variable of the loop does not overflow"));
! 	  if (!nonzero_p (assumption))
! 	    return false;
! 	}
!       noloop = fold_build2 (GT_EXPR, boolean_type_node,
! 			    fold_build2 (MINUS_EXPR, type,
! 					 iv0->base, tmod),
! 			    iv1->base);
      }
+ 
+ 	  
+   simplify_by_external_information (loop, &noloop, &niter->additional_info);
+   if (!zero_p (noloop))
+     niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
+ 				      niter->may_be_zero,
+ 				      noloop);
+   *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
+   return true;
  }
  
! /* Verify conditions (and record them in NITER) that ensure that the control
!    variable of the LOOP with ending condition IV0 < IV1 does not overflow.
!    Types of IV0 and IV1 are TYPE.  Returns false if we can prove that there is
!    an overflow, true otherwise.  STEP is the absolute value of the step.
  
!    WARN is the statement for that we should issue warning about usage of
!    unsafe assumptions, or NULL if we should not issue this warning.  */
  
! static bool
! assert_no_overflow_lt (struct loop *loop, struct tree_niter_desc *niter,
! 		       tree type, affine_iv *iv0, affine_iv *iv1,
! 		       tree step, tree warn)
! {
!   tree bound, d, assumption, diff;
!   tree niter_type = TREE_TYPE (step);
  
!   if (nonzero_p (iv0->step))
!     {
!       /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
!       if (iv0->no_overflow)
! 	return true;
  
!       /* If iv0->base is a constant, we can determine the last value before
! 	 overflow precisely; otherwise we conservatively assume
! 	 MAX - STEP + 1.  */
  
!       if (TREE_CODE (iv0->base) == INTEGER_CST)
! 	{
! 	  d = fold_build2 (MINUS_EXPR, niter_type,
! 			   fold_convert (niter_type, TYPE_MAX_VALUE (type)),
! 			   fold_convert (niter_type, iv0->base));
! 	  diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
! 	}
!       else
! 	diff = fold_build2 (MINUS_EXPR, niter_type, step,
! 			    build_int_cst (niter_type, 1));
!       bound = fold_build2 (MINUS_EXPR, type,
! 			   TYPE_MAX_VALUE (type), fold_convert (type, diff));
!       assumption = fold_build2 (LE_EXPR, boolean_type_node,
! 				iv1->base, bound);
!     }
!   else
      {
!       /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
!       if (iv1->no_overflow)
! 	return true;
! 
!       if (TREE_CODE (iv1->base) == INTEGER_CST)
! 	{
! 	  d = fold_build2 (MINUS_EXPR, niter_type,
! 			   fold_convert (niter_type, iv1->base),
! 			   fold_convert (niter_type, TYPE_MIN_VALUE (type)));
! 	  diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
! 	}
!       else
! 	diff = fold_build2 (MINUS_EXPR, niter_type, step,
! 			    build_int_cst (niter_type, 1));
!       bound = fold_build2 (PLUS_EXPR, type,
! 			   TYPE_MIN_VALUE (type), fold_convert (type, diff));
!       assumption = fold_build2 (GE_EXPR, boolean_type_node,
! 				iv0->base, bound);
!     }
  
!   simplify_by_external_information (loop, &assumption, &niter->additional_info);
!   adjust_by_unsafe_loop_opts_flag (
!     &assumption, warn,
!     N_("cannot optimize loop as the control variable might overflow"),
!     N_("assuming that the control variable of the loop does not overflow"));
  
!   if (!nonzero_p (assumption))
!     return false;
  
!   iv0->no_overflow = true;
!   iv1->no_overflow = true;
!   return true;
  }
  
! /* Add an assumption to NITER that a loop whose ending condition
!    is IV0 < IV1 rolls.  TYPE is the type of the control iv.
  
!    WARN is the statement for that we should issue warning about usage of
!    unsafe assumptions, or NULL if we should not issue this warning.  */
  
! static bool
! assert_loop_rolls_lt (struct loop *loop, tree type, affine_iv *iv0, affine_iv *iv1,
! 		      struct tree_niter_desc *niter, tree warn)
! {
!   tree assumption = boolean_true_node, bound, diff;
!   tree mbz, mbzl, mbzr;
  
!   if (nonzero_p (iv0->step))
      {
!       diff = fold_build2 (MINUS_EXPR, type,
! 			  iv0->step, build_int_cst (type, 1));
! 
!       /* We need to know that iv0->base >= MIN + iv0->step - 1.  Since
! 	 0 address never belongs to any object, we can assume this for
! 	 pointers.  */
!       if (!POINTER_TYPE_P (type))
  	{
! 	  bound = fold_build2 (PLUS_EXPR, type,
! 			       TYPE_MIN_VALUE (type), diff);
! 	  assumption = fold_build2 (GE_EXPR, boolean_type_node,
! 				    iv0->base, bound);
! 	}
  
!       /* And then we can compute iv0->base - diff, and compare it with
! 	 iv1->base.  */      
!       mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff);
!       mbzr = iv1->base;
!     }
!   else
!     {
!       diff = fold_build2 (PLUS_EXPR, type,
! 			  iv1->step, build_int_cst (type, 1));
  
!       if (!POINTER_TYPE_P (type))
! 	{
! 	  bound = fold_build2 (PLUS_EXPR, type,
! 			       TYPE_MAX_VALUE (type), diff);
! 	  assumption = fold_build2 (LE_EXPR, boolean_type_node,
! 				    iv1->base, bound);
  	}
  
!       mbzl = iv0->base;
!       mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff);
      }
  
!   mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
  
!   simplify_by_external_information (loop, &assumption, &niter->additional_info);
!   adjust_by_unsafe_loop_opts_flag (
!     &assumption, warn,
!     N_("cannot optimize the loop as we are unable to verify whether it rolls"),
!     N_("assuming that the difference of bounds plus step of the loop does not overflow"));
  
!   if (!nonzero_p (assumption))
!     return false;
  
!   simplify_by_external_information (loop, &mbz, &niter->additional_info);
!   if (!zero_p (mbz))
!     niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
! 				      niter->may_be_zero, mbz);
! 
!   return true;
  }
  
! /* 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.  
  
!    WARN is the statement for that we should issue warning about usage of
!    unsafe assumptions, or NULL if we should not issue this warning.  */
  
! static bool
! number_of_iterations_lt (struct loop *loop, tree type,
! 			 affine_iv *iv0, affine_iv *iv1,
! 			 struct tree_niter_desc *niter,
! 			 bool never_infinite ATTRIBUTE_UNUSED, tree warn)
! {
!   tree niter_type = unsigned_type_for (type);
!   tree delta, step, s;
  
!   if (nonzero_p (iv0->step))
      {
!       niter->control = *iv0;
!       niter->cmp = LT_EXPR;
!       niter->bound = iv1->base;
!     }
!   else
!     {
!       niter->control = *iv1;
!       niter->cmp = GT_EXPR;
!       niter->bound = iv0->base;
!     }
  
!   delta = fold_build2 (MINUS_EXPR, niter_type,
! 		       fold_convert (niter_type, iv1->base),
! 		       fold_convert (niter_type, iv0->base));
  
!   /* First handle the special case that the step is +-1.  */
!   if ((iv0->step && integer_onep (iv0->step)
!        && zero_p (iv1->step))
!       || (iv1->step && integer_all_onesp (iv1->step)
! 	  && zero_p (iv0->step)))
!     {
!       /* for (i = iv0->base; i < iv1->base; i++)
  
! 	 or
  
! 	 for (i = iv1->base; i > iv0->base; i--).
! 	     
! 	 In both cases # of iterations is iv1->base - iv0->base, assuming that
! 	 iv1->base >= iv0->base.  */
!       niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
! 					iv1->base, iv0->base);
!       simplify_by_external_information (loop, &niter->may_be_zero,
! 					&niter->additional_info);
!       niter->niter = delta;
!       return true;
      }
  
!   if (nonzero_p (iv0->step))
!     step = fold_convert (niter_type, iv0->step);
!   else
!     step = fold_convert (niter_type,
! 			 fold_build1 (NEGATE_EXPR, type, iv1->step));
! 
!   /* If we can determine the final value of the control iv exactly, we can
!      transform the condition to != comparison.  In particular, this will be
!      the case if DELTA is constant.  */
!   if (number_of_iterations_lt_to_ne (loop, type, iv0, iv1, niter,
! 				     &delta, step, warn))
      {
!       affine_iv zps;
  
!       zps.base = build_int_cst (niter_type, 0);
!       zps.step = step;
!       /* number_of_iterations_lt_to_ne will check assumptions that ensure that
! 	 zps does not overflow.  */
!       zps.no_overflow = true;
  
!       return number_of_iterations_ne (loop, type, &zps, delta, niter,
! 				      true, warn);
      }
  
!   /* Make sure that the control iv does not overflow.  */
!   if (!assert_no_overflow_lt (loop, niter, type, iv0, iv1, step, warn))
!     return false;
  
!   /* We determine the number of iterations as (delta + step - 1) / step.  For
!      this to work, we must know that iv1->base >= iv0->base - step + 1,
!      otherwise the loop does not roll.  */
!   if (!assert_loop_rolls_lt (loop, type, iv0, iv1, niter, warn))
!     return false;
! 
!   s = fold_build2 (MINUS_EXPR, niter_type,
! 		   step, build_int_cst (niter_type, 1));
!   delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
!   niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
!   return true;
! }
! 
! /* 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 the assumptions to make sure this
!    is the case).  LOOP is the loop in that the condition appears.
! 
!    WARN is the statement for that we should issue warning about usage of
!    unsafe assumptions, or NULL if we should not issue this warning.  */
! 
! static bool
! number_of_iterations_le (struct loop *loop, tree type,
! 			 affine_iv *iv0, affine_iv *iv1,
! 			 struct tree_niter_desc *niter,
! 			 bool never_infinite, tree warn)
! {
!   tree assumption;
  
!   /* Say that IV0 is the control variable.  Then IV0 <= IV1 iff
!      IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
!      value of the type.  This we must know anyway, since if it is
!      equal to this value, the loop rolls forever.  */
  
!   if (!never_infinite)
!     {
!       if (nonzero_p (iv0->step))
! 	assumption = fold_build2 (NE_EXPR, boolean_type_node,
! 				  iv1->base, TYPE_MAX_VALUE (type));
!       else
! 	assumption = fold_build2 (NE_EXPR, boolean_type_node,
! 				  iv0->base, TYPE_MIN_VALUE (type));
!       
!       simplify_by_external_information (loop, &assumption,
! 					&niter->additional_info);
!       adjust_by_unsafe_loop_opts_flag (
! 	&assumption, warn,
! 	N_("cannot optimize the loop as it might be infinite"),
! 	N_("assuming that the loop is not infinite"));
  
!       if (!nonzero_p (assumption))
! 	return false;
!     }
  
!   if (nonzero_p (iv0->step))
!     iv1->base = fold_build2 (PLUS_EXPR, type,
! 			     iv1->base, build_int_cst (type, 1));
!   else
!     iv0->base = fold_build2 (MINUS_EXPR, type,
! 			     iv0->base, build_int_cst (type, 1));
!   return number_of_iterations_lt (loop, type, iv0, iv1, niter, never_infinite,
! 				  warn);
  }
  
! /* Determine the number of iterations according to condition (for staying
!    inside LOOP) which compares two induction variables using comparison
!    operator CODE.  The induction variable on left side of the comparison
!    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.
!    Returns false if it fails to determine number of iterations, true if it
!    was determined (possibly with some assumptions).
!  
!    WARN is the statement for that we should issue warning about usage of
!    unsafe assumptions, or NULL if we should not issue this warning.  */
  
! static bool
! number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code,
! 			   affine_iv *iv1, struct tree_niter_desc *niter,
! 			   struct loop *loop, bool only_exit, tree warn)
  {
!   bool never_infinite, ret;
  
!   /* The meaning of these assumptions is this:
!      if !assumptions
!        then the rest of information does not have to be valid
!      if may_be_zero then the loop does not roll, even if
!        niter != 0.  */
!   niter->may_be_zero = boolean_false_node;
!   niter->niter = NULL_TREE;
!   niter->additional_info = boolean_true_node;
  
!   niter->bound = NULL_TREE;
!   niter->cmp = ERROR_MARK;
  
!   /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
!      the control variable is on lhs.  */
!   if (code == GE_EXPR || code == GT_EXPR
!       || (code == NE_EXPR && zero_p (iv0->step)))
!     {
!       SWAP (iv0, iv1);
!       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;
      }
  
!   /* If the control induction variable does not overflow, the loop obviously
!      cannot be infinite.  */
!   if (!zero_p (iv0->step) && iv0->no_overflow)
!     never_infinite = true;
!   else if (!zero_p (iv1->step) && iv1->no_overflow)
!     never_infinite = true;
!   else
!     never_infinite = false;
  
!   /* We can handle the case when neither of the sides of the comparison is
!      invariant, provided that the test is NE_EXPR.  This rarely occurs in
!      practice, but it is simple enough to manage.  */
!   if (!zero_p (iv0->step) && !zero_p (iv1->step))
!     {
!       if (code != NE_EXPR)
! 	return false;
  
!       iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
! 					   iv0->step, iv1->step);
!       iv0->no_overflow = false;
!       iv1->step = NULL_TREE;
!       iv1->no_overflow = true;
!     }
  
!   /* If the result of the comparison is a constant,  the loop is weird.  More
!      precise handling would be possible, but the situation is not common enough
!      to waste time on it.  */
!   if (zero_p (iv0->step) && zero_p (iv1->step))
!     return false;
  
!   /* Ignore loops of while (i-- < 10) type.  */
!   if (code != NE_EXPR)
      {
!       if (iv0->step && tree_int_cst_sign_bit (iv0->step))
! 	return false;
  
!       if (!zero_p (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
! 	return false;
!     }
  
!   /* If the loop exits immediately, there is nothing to do.  */
!   if (zero_p (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
!     {
!       niter->niter = build_int_cst (unsigned_type_for (type), 0);
!       return true;
!     }
  
!   /* OK, now we know we have a senseful loop.  Handle several cases, depending
!      on what comparison operator is used.  */
!   switch (code)
!     {
!     case NE_EXPR:
!       gcc_assert (zero_p (iv1->step));
!       ret = number_of_iterations_ne (loop, type, iv0, iv1->base, niter,
! 				     never_infinite, warn);
!       break;
! 	
!     case LT_EXPR:
!       ret = number_of_iterations_lt (loop, type, iv0, iv1, niter,
! 					    never_infinite, warn);
!       break;
  
!     case LE_EXPR:
!       ret = number_of_iterations_le (loop, type, iv0, iv1, niter,
! 				     never_infinite, warn);
!       break;
  
!     default:
!       gcc_unreachable ();
      }
  
!   if (!ret)
!     return false;
  
!   simplify_by_external_information (loop, &niter->niter,
! 				    &niter->additional_info);
!   return true;
  }
  
  /* Returns true if EXIT is the only possible exit from LOOP.  */
*************** number_of_iterations_exit (struct loop *
*** 1038,1044 ****
    if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
      return false;
  
-   niter->assumptions = boolean_false_node;
    stmt = last_stmt (exit->src);
    if (!stmt || TREE_CODE (stmt) != COND_EXPR)
      return false;
--- 1175,1180 ----
*************** number_of_iterations_exit (struct loop *
*** 1077,1146 ****
  
    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)
!     {
!       niter->assumptions = simplify_using_outer_evolutions (loop,
! 							    niter->assumptions);
!       niter->may_be_zero = simplify_using_outer_evolutions (loop,
! 							    niter->may_be_zero);
!       niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
!     }
! 
!   niter->additional_info = boolean_true_node;
!   niter->assumptions
! 	  = simplify_using_initial_conditions (loop,
! 					       niter->assumptions,
! 					       &niter->additional_info);
!   niter->may_be_zero
! 	  = simplify_using_initial_conditions (loop,
! 					       niter->may_be_zero,
! 					       &niter->additional_info);
! 
!   if (integer_onep (niter->assumptions))
!     return true;
! 
!   /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
!      But if we can prove that there is overflow or some other source of weird
!      behavior, ignore the loop even with -funsafe-loop-optimizations.  */
!   if (integer_zerop (niter->assumptions))
!     return false;
! 
!   if (flag_unsafe_loop_optimizations)
!     niter->assumptions = boolean_true_node;
! 
!   if (warn)
!     {
!       const char *wording;
!       location_t loc = EXPR_LOCATION (stmt);
!   
!       /* We can provide a more specific warning if one of the operator is
! 	 constant and the other advances by +1 or -1.  */
!       if (!zero_p (iv1.step)
! 	  ? (zero_p (iv0.step)
! 	     && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
! 	  : (iv0.step
! 	     && (integer_onep (iv0.step) || integer_all_onesp (iv0.step))))
!         wording =
!           flag_unsafe_loop_optimizations
!           ? N_("assuming that the loop is not infinite")
!           : N_("cannot optimize possibly infinite loops");
!       else
! 	wording = 
! 	  flag_unsafe_loop_optimizations
! 	  ? N_("assuming that the loop counter does not overflow")
! 	  : N_("cannot optimize loop, the loop counter may overflow");
! 
!       if (LOCATION_LINE (loc) > 0)
! 	warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
!       else
! 	warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
!     }
! 
!   return flag_unsafe_loop_optimizations;
  }
  
  /* Try to determine the number of iterations of LOOP.  If we succeed,
--- 1213,1221 ----
  
    iv0.base = expand_simple_operations (iv0.base);
    iv1.base = expand_simple_operations (iv1.base);
!   return number_of_iterations_cond (type, &iv0, code, &iv1, niter,
! 				    loop, loop_only_exit_p (loop, exit),
! 				    warn ? stmt : NULL);
  }
  
  /* Try to determine the number of iterations of LOOP.  If we succeed,
Index: testsuite/gcc.dg/tree-ssa/pr19210-1.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/pr19210-1.c	(revision 112854)
--- testsuite/gcc.dg/tree-ssa/pr19210-1.c	(working copy)
*************** void
*** 6,12 ****
  f (unsigned n)
  {
    unsigned k;
!   for(k = 0;k <= n;k++) /* { dg-warning "cannot optimize.*infinite loops" } */
      g();
  
    for(k = 0;k <= n;k += 4) /* { dg-warning "cannot optimize.*overflow" } */
--- 6,12 ----
  f (unsigned n)
  {
    unsigned k;
!   for(k = 0;k <= n;k++) /* { dg-warning "cannot optimize.*infinite" } */
      g();
  
    for(k = 0;k <= n;k += 4) /* { dg-warning "cannot optimize.*overflow" } */
*************** f (unsigned n)
*** 27,29 ****
--- 27,30 ----
    for(k = 15;k >= n;k--) /* { dg-warning "cannot optimize.*infinite" } */
      g();
  }
+ 
Index: tree-flow.h
===================================================================
*** tree-flow.h	(revision 112854)
--- tree-flow.h	(working copy)
*************** typedef struct
*** 674,683 ****
  
  struct tree_niter_desc
  {
-   tree assumptions;	/* The boolean expression.  If this expression evaluates
- 			   to false, then the other fields in this structure
- 			   should not be used; there is no guarantee that they
- 			   will be correct.  */
    tree may_be_zero;	/* The boolean expression.  If it evaluates to true,
  			   the loop will exit in the first iteration (i.e.
  			   its latch will not be executed), even if the niter
--- 674,679 ----



More information about the Gcc-patches mailing list