This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch] Speed up # of iterations analysis


Hello,

on some testcases, we spend large amount of time in # of iterations
analysis (about 3% on PR 18687).  There does not seem to be any
significant problem with the usage of the analysis (we call it about
three times per loop, from different optimization passes), just the
analysis by itself is slow.  This patch contains a few speedups:

1) makes tree-ssa-loop-niter use fold_build instead of
   fold (build (...))
2) Adds a special handling for loops with step 1.
3) Removes simplify_using_outer_evolutions.  This function does
   basically constant propagation in weird special cases,
   like

   for (i = 0; i < 50; i++)
     ...;
   for (; i < 100; i++)
     ...;

   to detect that the initial value of i in the second loop is 50.
   In practice, this just wastes time.

Bootstrapped & regtested on i686.

Zdenek

Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.88
diff -c -3 -p -r2.88 tree-flow.h
*** tree-flow.h	29 Mar 2005 11:45:49 -0000	2.88
--- tree-flow.h	3 Apr 2005 08:37:47 -0000
*************** void canonicalize_induction_variables (s
*** 697,704 ****
  void tree_unroll_loops_completely (struct loops *);
  void tree_ssa_iv_optimize (struct loops *);
  
- void number_of_iterations_cond (tree, tree, tree, enum tree_code, tree, tree,
- 				struct tree_niter_desc *);
  bool number_of_iterations_exit (struct loop *, edge,
  				struct tree_niter_desc *niter);
  tree find_loop_niter (struct loop *, edge *);
--- 697,702 ----
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.21
diff -c -3 -p -r2.21 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c	11 Mar 2005 09:05:11 -0000	2.21
--- tree-ssa-loop-niter.c	3 Apr 2005 08:37:47 -0000
*************** inverse (tree x, tree mask)
*** 137,143 ****
     In case we are unable to determine number of iterations, contents of
     this structure is unchanged.  */
  
! void
  number_of_iterations_cond (tree type, tree base0, tree step0,
  			   enum tree_code code, tree base1, tree step1,
  			   struct tree_niter_desc *niter)
--- 137,143 ----
     In case we are unable to determine number of iterations, contents of
     this structure is unchanged.  */
  
! static void
  number_of_iterations_cond (tree type, tree base0, tree step0,
  			   enum tree_code code, tree base1, tree step1,
  			   struct tree_niter_desc *niter)
*************** number_of_iterations_cond (tree type, tr
*** 221,244 ****
        if (zero_p (step0))
  	{
  	  if (mmax)
! 	    assumption = fold (build2 (EQ_EXPR, boolean_type_node, base0, mmax));
  	  else
  	    assumption = boolean_false_node;
  	  if (nonzero_p (assumption))
  	    goto zero_iter;
! 	  base0 = fold (build2 (PLUS_EXPR, type, base0,
! 				build_int_cst_type (type, 1)));
  	}
        else
  	{
  	  if (mmin)
! 	    assumption = fold (build2 (EQ_EXPR, boolean_type_node, base1, mmin));
  	  else
  	    assumption = boolean_false_node;
  	  if (nonzero_p (assumption))
  	    goto zero_iter;
! 	  base1 = fold (build2 (MINUS_EXPR, type, base1,
! 				build_int_cst_type (type, 1)));
  	}
        noloop_assumptions = assumption;
        code = LE_EXPR;
--- 221,244 ----
        if (zero_p (step0))
  	{
  	  if (mmax)
! 	    assumption = fold_build2 (EQ_EXPR, boolean_type_node, base0, mmax);
  	  else
  	    assumption = boolean_false_node;
  	  if (nonzero_p (assumption))
  	    goto zero_iter;
! 	  base0 = fold_build2 (PLUS_EXPR, type, base0,
! 			       build_int_cst_type (type, 1));
  	}
        else
  	{
  	  if (mmin)
! 	    assumption = fold_build2 (EQ_EXPR, boolean_type_node, base1, mmin);
  	  else
  	    assumption = boolean_false_node;
  	  if (nonzero_p (assumption))
  	    goto zero_iter;
! 	  base1 = fold_build2 (MINUS_EXPR, type, base1,
! 			       build_int_cst_type (type, 1));
  	}
        noloop_assumptions = assumption;
        code = LE_EXPR;
*************** number_of_iterations_cond (tree type, tr
*** 274,280 ****
        else
  	step = step0;
        delta = build2 (MINUS_EXPR, type, base1, base0);
!       delta = fold (build2 (FLOOR_MOD_EXPR, type, delta, step));
        may_xform = boolean_false_node;
  
        if (TREE_CODE (delta) == INTEGER_CST)
--- 274,280 ----
        else
  	step = step0;
        delta = build2 (MINUS_EXPR, type, base1, base0);
!       delta = fold_build2 (FLOOR_MOD_EXPR, type, delta, step);
        may_xform = boolean_false_node;
  
        if (TREE_CODE (delta) == INTEGER_CST)
*************** number_of_iterations_cond (tree type, tr
*** 305,312 ****
  						   mmin, step);
  		  bound = fold_binary_to_constant (MINUS_EXPR, type,
  						   bound, delta);
! 		  may_xform = fold (build2 (LE_EXPR, boolean_type_node,
! 					   bound, base0));
  		}
  	    }
  	  else
--- 305,312 ----
  						   mmin, step);
  		  bound = fold_binary_to_constant (MINUS_EXPR, type,
  						   bound, delta);
! 		  may_xform = fold_build2 (LE_EXPR, boolean_type_node,
! 					   bound, base0);
  		}
  	    }
  	  else
*************** number_of_iterations_cond (tree type, tr
*** 319,326 ****
  						   mmax, step);
  		  bound = fold_binary_to_constant (PLUS_EXPR, type,
  						   bound, delta);
! 		  may_xform = fold (build2 (LE_EXPR, boolean_type_node,
! 					   base1, bound));
  		}
  	    }
  	}
--- 319,326 ----
  						   mmax, step);
  		  bound = fold_binary_to_constant (PLUS_EXPR, type,
  						   bound, delta);
! 		  may_xform = fold_build2 (LE_EXPR, boolean_type_node,
! 					   base1, bound);
  		}
  	    }
  	}
*************** number_of_iterations_cond (tree type, tr
*** 335,352 ****
  
  	  if (zero_p (step0))
  	    {
! 	      base0 = fold (build2 (PLUS_EXPR, type, base0, delta));
! 	      base0 = fold (build2 (MINUS_EXPR, type, base0, step));
  	    }
  	  else
  	    {
! 	      base1 = fold (build2 (MINUS_EXPR, type, base1, delta));
! 	      base1 = fold (build2 (PLUS_EXPR, type, base1, step));
  	    }
  
! 	  assumption = fold (build2 (GT_EXPR, boolean_type_node, base0, base1));
! 	  noloop_assumptions = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
! 					    noloop_assumptions, assumption));
  	  code = NE_EXPR;
  	}
      }
--- 335,352 ----
  
  	  if (zero_p (step0))
  	    {
! 	      base0 = fold_build2 (PLUS_EXPR, type, base0, delta);
! 	      base0 = fold_build2 (MINUS_EXPR, type, base0, step);
  	    }
  	  else
  	    {
! 	      base1 = fold_build2 (MINUS_EXPR, type, base1, delta);
! 	      base1 = fold_build2 (PLUS_EXPR, type, base1, step);
  	    }
  
! 	  assumption = fold_build2 (GT_EXPR, boolean_type_node, base0, base1);
! 	  noloop_assumptions = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
! 					    noloop_assumptions, assumption);
  	  code = NE_EXPR;
  	}
      }
*************** number_of_iterations_cond (tree type, tr
*** 361,367 ****
  	 makes us able to do more involved computations of number of iterations
  	 than in other cases.  First transform the condition into shape
  	 s * i <> c, with s positive.  */
!       base1 = fold (build2 (MINUS_EXPR, type, base1, base0));
        base0 = NULL_TREE;
        if (!zero_p (step1))
    	step0 = fold_unary_to_constant (NEGATE_EXPR, type, step1);
--- 361,367 ----
  	 makes us able to do more involved computations of number of iterations
  	 than in other cases.  First transform the condition into shape
  	 s * i <> c, with s positive.  */
!       base1 = fold_build2 (MINUS_EXPR, type, base1, base0);
        base0 = NULL_TREE;
        if (!zero_p (step1))
    	step0 = fold_unary_to_constant (NEGATE_EXPR, type, step1);
*************** number_of_iterations_cond (tree type, tr
*** 369,375 ****
        if (!tree_expr_nonnegative_p (fold_convert (signed_niter_type, step0)))
  	{
  	  step0 = fold_unary_to_constant (NEGATE_EXPR, type, step0);
! 	  base1 = fold (build1 (NEGATE_EXPR, type, base1));
  	}
  
        base1 = fold_convert (niter_type, base1);
--- 369,375 ----
        if (!tree_expr_nonnegative_p (fold_convert (signed_niter_type, step0)))
  	{
  	  step0 = fold_unary_to_constant (NEGATE_EXPR, type, step0);
! 	  base1 = fold_build1 (NEGATE_EXPR, type, base1);
  	}
  
        base1 = fold_convert (niter_type, base1);
*************** number_of_iterations_cond (tree type, tr
*** 387,402 ****
  				   (TYPE_PRECISION (niter_type)
  				    - tree_low_cst (bits, 1)));
  
!       assumption = fold (build2 (FLOOR_MOD_EXPR, niter_type, base1, d));
!       assumption = fold (build2 (EQ_EXPR, boolean_type_node,
! 				 assumption,
! 				 build_int_cst (niter_type, 0)));
!       assumptions = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
! 				  assumptions, assumption));
! 
!       tmp = fold (build2 (EXACT_DIV_EXPR, niter_type, base1, d));
!       tmp = fold (build2 (MULT_EXPR, niter_type, tmp, inverse (s, bound)));
!       niter->niter = fold (build2 (BIT_AND_EXPR, niter_type, tmp, bound));
      }
    else
      {
--- 387,402 ----
  				   (TYPE_PRECISION (niter_type)
  				    - tree_low_cst (bits, 1)));
  
!       assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, base1, d);
!       assumption = fold_build2 (EQ_EXPR, boolean_type_node,
! 				assumption,
! 				build_int_cst (niter_type, 0));
!       assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
! 				 assumptions, assumption);
! 
!       tmp = fold_build2 (EXACT_DIV_EXPR, niter_type, base1, d);
!       tmp = fold_build2 (MULT_EXPR, niter_type, tmp, inverse (s, bound));
!       niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
      }
    else
      {
*************** number_of_iterations_cond (tree type, tr
*** 411,427 ****
  	  if (mmax)
  	    {
  	      bound = fold_binary_to_constant (MINUS_EXPR, type, mmax, step0);
! 	      assumption = fold (build2 (LE_EXPR, boolean_type_node,
! 					 base1, bound));
! 	      assumptions = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
! 					  assumptions, assumption));
  	    }
  
  	  step = step0;
! 	  tmp = fold (build2 (PLUS_EXPR, type, base1, step0));
! 	  assumption = fold (build2 (GT_EXPR, boolean_type_node, base0, tmp));
! 	  delta = fold (build2 (PLUS_EXPR, type, base1, step));
! 	  delta = fold (build2 (MINUS_EXPR, type, delta, base0));
  	  delta = fold_convert (niter_type, delta);
  	}
        else
--- 411,427 ----
  	  if (mmax)
  	    {
  	      bound = fold_binary_to_constant (MINUS_EXPR, type, mmax, step0);
! 	      assumption = fold_build2 (LE_EXPR, boolean_type_node,
! 					base1, bound);
! 	      assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
! 					 assumptions, assumption);
  	    }
  
  	  step = step0;
! 	  tmp = fold_build2 (PLUS_EXPR, type, base1, step0);
! 	  assumption = fold_build2 (GT_EXPR, boolean_type_node, base0, tmp);
! 	  delta = fold_build2 (PLUS_EXPR, type, base1, step);
! 	  delta = fold_build2 (MINUS_EXPR, type, delta, base0);
  	  delta = fold_convert (niter_type, delta);
  	}
        else
*************** number_of_iterations_cond (tree type, tr
*** 432,453 ****
  	  if (mmin)
  	    {
  	      bound = fold_binary_to_constant (MINUS_EXPR, type, mmin, step1);
! 	      assumption = fold (build2 (LE_EXPR, boolean_type_node,
! 					bound, base0));
! 	      assumptions = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
! 					 assumptions, assumption));
  	    }
! 	  step = fold (build1 (NEGATE_EXPR, type, step1));
! 	  tmp = fold (build2 (PLUS_EXPR, type, base0, step1));
! 	  assumption = fold (build2 (GT_EXPR, boolean_type_node, tmp, base1));
! 	  delta = fold (build2 (MINUS_EXPR, type, base0, step));
! 	  delta = fold (build2 (MINUS_EXPR, type, base1, delta));
  	  delta = fold_convert (niter_type, delta);
  	}
!       noloop_assumptions = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
! 					noloop_assumptions, assumption));
!       delta = fold (build2 (FLOOR_DIV_EXPR, niter_type, delta,
! 			    fold_convert (niter_type, step)));
        niter->niter = delta;
      }
  
--- 432,453 ----
  	  if (mmin)
  	    {
  	      bound = fold_binary_to_constant (MINUS_EXPR, type, mmin, step1);
! 	      assumption = fold_build2 (LE_EXPR, boolean_type_node,
! 					bound, base0);
! 	      assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
! 					 assumptions, assumption);
  	    }
! 	  step = fold_build1 (NEGATE_EXPR, type, step1);
! 	  tmp = fold_build2 (PLUS_EXPR, type, base0, step1);
! 	  assumption = fold_build2 (GT_EXPR, boolean_type_node, tmp, base1);
! 	  delta = fold_build2 (MINUS_EXPR, type, base0, step);
! 	  delta = fold_build2 (MINUS_EXPR, type, base1, delta);
  	  delta = fold_convert (niter_type, delta);
  	}
!       noloop_assumptions = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
! 					noloop_assumptions, assumption);
!       delta = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta,
! 			   fold_convert (niter_type, step));
        niter->niter = delta;
      }
  
*************** zero_iter:
*** 462,521 ****
    return;
  }
  
- /* 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 = build3 (code, boolean_type_node, e0, e1, e2);
  	  else
! 	    expr = build2 (code, boolean_type_node, e0, e1);
! 	  expr = fold (expr);
  	}
  
!       return expr;
!     }
  
!   e = instantiate_parameters (loop, expr);
!   if (is_gimple_min_invariant (e))
!     return e;
  
!   return expr;
  }
  
  /* Substitute NEW for OLD in EXPR and fold the result.  */
--- 462,592 ----
    return;
  }
  
  
! /* Similar to number_of_iterations_cond, but only handles the special
!    case of loops with step 1 or -1.  The meaning of the arguments
!    is the same as in number_of_iterations_cond.  The function
!    returns true if the special case was recognized, false otherwise.  */
! 
! static bool
! number_of_iterations_special (tree type, tree base0, tree step0,
! 			      enum tree_code code, tree base1, tree step1,
! 			      struct tree_niter_desc *niter)
  {
!   tree niter_type = unsigned_type_for (type), mmax, mmin;
  
!   /* Make < comparison from > ones.  */
!   if (code == GE_EXPR
!       || code == GT_EXPR)
!     {
!       SWAP (base0, base1);
!       SWAP (step0, step1);
!       code = swap_tree_comparison (code);
!     }
  
!   switch (code)
      {
!     case NE_EXPR:
!       if (zero_p (step0))
! 	{
! 	  if (zero_p (step1))
! 	    return false;
!     	  SWAP (base0, base1);
! 	  SWAP (step0, step1);
! 	}
!       else if (!zero_p (step1))
! 	return false;
  
!       if (integer_onep (step0))
! 	{
! 	  /* for (i = base0; i != base1; i++)  */
! 	  niter->assumptions = boolean_true_node;
! 	  niter->may_be_zero = boolean_false_node;
! 	  niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0);
! 	  niter->additional_info = boolean_true_node;
! 	}
!       else if (integer_all_onesp (step0))
! 	{
! 	  /* for (i = base0; i != base1; i--)  */
! 	  niter->assumptions = boolean_true_node;
! 	  niter->may_be_zero = boolean_false_node;
! 	  niter->niter = fold_build2 (MINUS_EXPR, type, base0, base1);
! 	}
!       else
! 	return false;
  
!       break;
  
!     case LT_EXPR:
!       if ((step0 && integer_onep (step0) && zero_p (step1))
! 	  || (step1 && integer_all_onesp (step1) && zero_p (step0)))
  	{
! 	  /* for (i = base0; i < base1; i++)
! 	     
! 	     or
! 
! 	     for (i = base1; i > base0; i--).
! 	     
! 	     In both cases # of iterations is base1 - base0.  */
! 
! 	  niter->assumptions = boolean_true_node;
! 	  niter->may_be_zero = fold_build2 (GT_EXPR, boolean_type_node,
! 					    base0, base1);
! 	  niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0);
  	}
        else
! 	return false;
!       break;
  
!     case LE_EXPR:
!       if (POINTER_TYPE_P (type))
  	{
! 	  /* We assume pointer arithmetic never overflows.  */
! 	  mmin = mmax = NULL_TREE;
! 	}
!       else
! 	{
! 	  mmin = TYPE_MIN_VALUE (type);
! 	  mmax = TYPE_MAX_VALUE (type);
! 	}
! 
!       if (step0 && integer_onep (step0) && zero_p (step1))
! 	{
! 	  /* for (i = base0; i <= base1; i++)  */
! 	  if (mmax)
! 	    niter->assumptions = fold_build2 (NE_EXPR, boolean_type_node,
! 					      base1, mmax);
! 	  else
! 	    niter->assumptions = boolean_true_node;
! 	  base1 = fold_build2 (PLUS_EXPR, type, base1,
! 			       build_int_cst_type (type, 1));
! 	}
!       else if (step1 && integer_all_onesp (step1) && zero_p (step0))
! 	{
! 	  /* for (i = base1; i >= base0; i--)  */
! 	  if (mmin)
! 	    niter->assumptions = fold_build2 (NE_EXPR, boolean_type_node,
! 					      base0, mmin);
  	  else
! 	    niter->assumptions = boolean_true_node;
! 	  base0 = fold_build2 (MINUS_EXPR, type, base0,
! 			       build_int_cst_type (type, 1));
  	}
+       else
+ 	return false;
  
!       niter->may_be_zero = fold_build2 (GT_EXPR, boolean_type_node,
! 					base0, base1);
!       niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0);
!       break;
  
!     default:
!       gcc_unreachable ();
!     }
  
!   niter->niter = fold_convert (niter_type, niter->niter);
!   niter->additional_info = boolean_true_node;
!   return true;
  }
  
  /* Substitute NEW for OLD in EXPR and fold the result.  */
*************** tree_simplify_using_condition (tree cond
*** 592,601 ****
        if (changed)
  	{
  	  if (code == COND_EXPR)
! 	    expr = build3 (code, boolean_type_node, e0, e1, e2);
  	  else
! 	    expr = build2 (code, boolean_type_node, e0, e1);
! 	  expr = fold (expr);
  	}
  
        return expr;
--- 663,671 ----
        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;
*************** tree_simplify_using_condition (tree cond
*** 648,661 ****
  
    /* Check whether COND ==> EXPR.  */
    notcond = invert_truthvalue (cond);
!   e = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
! 		   notcond, expr));
    if (nonzero_p (e))
      return e;
  
    /* Check whether COND ==> not EXPR.  */
!   e = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
! 		   cond, expr));
    if (zero_p (e))
      return e;
  
--- 718,731 ----
  
    /* Check whether COND ==> EXPR.  */
    notcond = invert_truthvalue (cond);
!   e = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
! 		   notcond, expr);
    if (nonzero_p (e))
      return e;
  
    /* Check whether COND ==> not EXPR.  */
!   e = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
! 		   cond, expr);
    if (zero_p (e))
      return e;
  
*************** simplify_using_initial_conditions (struc
*** 695,704 ****
        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;
      }
--- 765,774 ----
        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;
      }
*************** number_of_iterations_exit (struct loop *
*** 762,777 ****
      return false;
  
    niter->niter = NULL_TREE;
-   number_of_iterations_cond (type, base0, step0, code, base1, step1,
- 			     niter);
-   if (!niter->niter)
-     return false;
  
!   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
--- 832,850 ----
      return false;
  
    niter->niter = NULL_TREE;
  
!   /* Handle common special cases first, so that we do not need to use
!      generic (and slow) analysis very often.  */
!   if (!number_of_iterations_special (type, base0, step0, code, base1, step1,
! 				     niter))
!     {
! 
!       number_of_iterations_cond (type, base0, step0, code, base1, step1,
! 				 niter);
! 
!       if (!niter->niter)
! 	return false;
!     }
  
    niter->additional_info = boolean_true_node;
    niter->assumptions
*************** loop_niter_by_eval (struct loop *loop, e
*** 1046,1052 ****
        for (j = 0; j < 2; j++)
  	aval[j] = get_val_for (op[j], val[j]);
  
!       acnd = fold (build2 (cmp, boolean_type_node, aval[0], aval[1]));
        if (zero_p (acnd))
  	{
  	  if (dump_file && (dump_flags & TDF_DETAILS))
--- 1119,1125 ----
        for (j = 0; j < 2; j++)
  	aval[j] = get_val_for (op[j], val[j]);
  
!       acnd = fold_build2 (cmp, boolean_type_node, aval[0], aval[1]);
        if (zero_p (acnd))
  	{
  	  if (dump_file && (dump_flags & TDF_DETAILS))
*************** compare_trees (tree a, tree b)
*** 1203,1213 ****
    a = fold_convert (type, a);
    b = fold_convert (type, b);
  
!   if (nonzero_p (fold (build2 (EQ_EXPR, boolean_type_node, a, b))))
      return 0;
!   if (nonzero_p (fold (build2 (LT_EXPR, boolean_type_node, a, b))))
      return 1;
!   if (nonzero_p (fold (build2 (GT_EXPR, boolean_type_node, a, b))))
      return -1;
  
    return 2;
--- 1276,1286 ----
    a = fold_convert (type, a);
    b = fold_convert (type, b);
  
!   if (nonzero_p (fold_build2 (EQ_EXPR, boolean_type_node, a, b)))
      return 0;
!   if (nonzero_p (fold_build2 (LT_EXPR, boolean_type_node, a, b)))
      return 1;
!   if (nonzero_p (fold_build2 (GT_EXPR, boolean_type_node, a, b)))
      return -1;
  
    return 2;
*************** can_count_iv_in_wider_type_bound (tree t
*** 1271,1278 ****
  
    b = fold_convert (type, base);
    bplusstep = fold_convert (type,
! 			    fold (build2 (PLUS_EXPR, inner_type, base, step)));
!   new_step = fold (build2 (MINUS_EXPR, type, bplusstep, b));
    if (TREE_CODE (new_step) != INTEGER_CST)
      return NULL_TREE;
  
--- 1344,1351 ----
  
    b = fold_convert (type, base);
    bplusstep = fold_convert (type,
! 			    fold_build2 (PLUS_EXPR, inner_type, base, step));
!   new_step = fold_build2 (MINUS_EXPR, type, bplusstep, b);
    if (TREE_CODE (new_step) != INTEGER_CST)
      return NULL_TREE;
  
*************** can_count_iv_in_wider_type_bound (tree t
*** 1280,1293 ****
      {
      case -1:
        extreme = upper_bound_in_type (type, inner_type);
!       delta = fold (build2 (MINUS_EXPR, type, extreme, b));
        new_step_abs = new_step;
        break;
  
      case 1:
        extreme = lower_bound_in_type (type, inner_type);
!       new_step_abs = fold (build1 (NEGATE_EXPR, type, new_step));
!       delta = fold (build2 (MINUS_EXPR, type, b, extreme));
        break;
  
      case 0:
--- 1353,1366 ----
      {
      case -1:
        extreme = upper_bound_in_type (type, inner_type);
!       delta = fold_build2 (MINUS_EXPR, type, extreme, b);
        new_step_abs = new_step;
        break;
  
      case 1:
        extreme = lower_bound_in_type (type, inner_type);
!       new_step_abs = fold_build1 (NEGATE_EXPR, type, new_step);
!       delta = fold_build2 (MINUS_EXPR, type, b, extreme);
        break;
  
      case 0:
*************** can_count_iv_in_wider_type_bound (tree t
*** 1300,1307 ****
    unsigned_type = unsigned_type_for (type);
    delta = fold_convert (unsigned_type, delta);
    new_step_abs = fold_convert (unsigned_type, new_step_abs);
!   valid_niter = fold (build2 (FLOOR_DIV_EXPR, unsigned_type,
! 			     delta, new_step_abs));
  
    bound_type = TREE_TYPE (bound);
    if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type))
--- 1373,1380 ----
    unsigned_type = unsigned_type_for (type);
    delta = fold_convert (unsigned_type, delta);
    new_step_abs = fold_convert (unsigned_type, new_step_abs);
!   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
! 			     delta, new_step_abs);
  
    bound_type = TREE_TYPE (bound);
    if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type))
*************** can_count_iv_in_wider_type_bound (tree t
*** 1313,1336 ****
      {
        /* After the statement OF we know that anything is executed at most
  	 BOUND times.  */
!       cond = build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
      }
    else
      {
        /* Before the statement OF we know that anything is executed at most
  	 BOUND + 1 times.  */
!       cond = build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
      }
  
-   cond = fold (cond);
    if (nonzero_p (cond))
      return new_step;
  
    /* Try taking additional conditions into account.  */
!   cond = build2 (TRUTH_OR_EXPR, boolean_type_node,
! 		invert_truthvalue (additional),
! 		cond);
!   cond = fold (cond);
    if (nonzero_p (cond))
      return new_step;
  
--- 1386,1407 ----
      {
        /* After the statement OF we know that anything is executed at most
  	 BOUND times.  */
!       cond = fold_build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
      }
    else
      {
        /* Before the statement OF we know that anything is executed at most
  	 BOUND + 1 times.  */
!       cond = fold_build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
      }
  
    if (nonzero_p (cond))
      return new_step;
  
    /* Try taking additional conditions into account.  */
!   cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
! 		      invert_truthvalue (additional),
! 		      cond);
    if (nonzero_p (cond))
      return new_step;
  


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]