[PATCH] Handle strange loops in unroller

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

Hello,

this patch adds handling of strange loops of type
for (i = 6; i > 5; i++)
to new loop unroller.  Not really important except for passing
weird benchmarks, but cool.

Zdenek

	* cfgloopanal.c (count_strange_loop_iterations): New static function.
	(constant_iterations, count_loop_iterations, simple_loop_exit_p):
	Handle strange loops.

Index: cfgloopanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopanal.c,v
retrieving revision 1.1.6.4
diff -c -3 -p -r1.1.6.4 cfgloopanal.c
*** cfgloopanal.c	11 Jun 2003 11:04:15 -0000	1.1.6.4
--- cfgloopanal.c	17 Jun 2003 23:02:38 -0000
*************** static bool simple_condition_p PARAMS ((
*** 48,53 ****
--- 48,55 ----
  					regset, struct loop_desc *));
  static basic_block simple_increment PARAMS ((struct loops *, struct loop *,
  					     rtx *, struct loop_desc *));
+ static rtx count_strange_loop_iterations (rtx, rtx, enum rtx_code,
+ 					  int, rtx, enum machine_mode);
  
  /* Checks whether BB is executed exactly once in each LOOP iteration.  */
  bool
*************** constant_iterations (desc, niter, may_be
*** 465,471 ****
      {
        alim = XEXP (desc->lim_alts, 0);
        if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), alim)))
! 	abort ();
        if (GET_CODE (expr) == CONST_INT)
  	{
  	  *niter = INTVAL (expr);
--- 467,473 ----
      {
        alim = XEXP (desc->lim_alts, 0);
        if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), alim)))
! 	continue;
        if (GET_CODE (expr) == CONST_INT)
  	{
  	  *niter = INTVAL (expr);
*************** constant_iterations (desc, niter, may_be
*** 476,482 ****
      {
        ainit = XEXP (desc->var_alts, 0);
        if (!(expr = count_loop_iterations (desc, ainit, XEXP (alim, 0))))
! 	abort ();
        if (GET_CODE (expr) == CONST_INT)
  	{
  	  *niter = INTVAL (expr);
--- 478,484 ----
      {
        ainit = XEXP (desc->var_alts, 0);
        if (!(expr = count_loop_iterations (desc, ainit, XEXP (alim, 0))))
! 	continue;
        if (GET_CODE (expr) == CONST_INT)
  	{
  	  *niter = INTVAL (expr);
*************** constant_iterations (desc, niter, may_be
*** 487,492 ****
--- 489,611 ----
    return false;
  }
  
+ /* Attempts to determine a number of iterations of a "strange" loop.
+    Its induction variable starts with value INIT, is compared by COND
+    with LIM.  If POSTINCR, it is incremented after the test.  It is incremented
+    by STRIDE each iteration and iterates in MODE.
+ 
+    By "strange" we mean loops where induction variable increases in the wrong
+    direction wrto comparison, i.e. for (i = 6; i > 5; i++).  */
+ static rtx
+ count_strange_loop_iterations (rtx init, rtx lim, enum rtx_code cond,
+ 			       int postincr, rtx stride, enum machine_mode mode)
+ {
+   rtx rqmt, n_to_wrap, before_wrap, after_wrap;
+   rtx mode_min, mode_max;
+   int size;
+ 
+   if (!postincr)
+     init = simplify_gen_binary (PLUS, mode, init, stride);
+ 
+   /* If we are able to prove that we don't pass the first test, we are
+      done.  */
+   rqmt = simplify_gen_relational (cond, SImode, mode, init, lim);
+   if (rqmt == const0_rtx)
+     return const0_rtx;
+ 
+   /* And if we don't know we pass it, the things are too complicated for us.  */
+   if (rqmt != const_true_rtx)
+     return NULL_RTX;
+ 
+   switch (cond)
+     {
+     case GE:
+     case GT:
+     case LE:
+     case LT:
+       size = GET_MODE_BITSIZE (mode);
+       mode_min = GEN_INT (-((unsigned HOST_WIDEST_INT) 1 << (size - 1)));
+       mode_max = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1)) - 1);
+ 			      
+       break;
+ 
+     case GEU:
+     case GTU:
+     case LEU:
+     case LTU:
+     case EQ:
+       mode_min = const0_rtx;
+       mode_max = constm1_rtx;
+       break;
+ 
+     default:
+       abort ();
+     }
+ 
+   switch (cond)
+     {
+     case EQ:
+       /* This iterates once, as init == lim.  */
+       return const1_rtx;
+ 
+       /* The behavior is undefined in signed cases.  Never mind, we still
+ 	 try to behave sanely.  */
+     case GE:
+     case GT:
+     case GEU:
+     case GTU:
+       if (INTVAL (stride) <= 0)
+ 	abort ();
+       n_to_wrap = simplify_gen_binary (MINUS, mode, mode_max, copy_rtx (init));
+       n_to_wrap = simplify_gen_binary (UDIV, mode, n_to_wrap, stride);
+       before_wrap = simplify_gen_binary (MULT, mode,
+ 					 copy_rtx (n_to_wrap), stride);
+       before_wrap = simplify_gen_binary (PLUS, mode,
+ 					 before_wrap, copy_rtx (init));
+       after_wrap = simplify_gen_binary (PLUS, mode,
+ 					before_wrap, stride);
+       if (GET_CODE (after_wrap) != CONST_INT)
+ 	{
+ 	  after_wrap = simplify_gen_binary (PLUS, mode, mode_min, stride);
+ 	  after_wrap = simplify_gen_binary (MINUS, mode, after_wrap, const1_rtx);
+ 	}
+       break;
+ 
+     case LE:
+     case LT:
+     case LEU:
+     case LTU:
+       if (INTVAL (stride) >= 0)
+ 	abort ();
+       stride = simplify_gen_unary (NEG, mode, stride, mode);
+       n_to_wrap = simplify_gen_binary (MINUS, mode, copy_rtx (init), mode_min);
+       n_to_wrap = simplify_gen_binary (UDIV, mode, n_to_wrap, stride);
+       before_wrap = simplify_gen_binary (MULT, mode,
+ 					 copy_rtx (n_to_wrap), stride);
+       before_wrap = simplify_gen_binary (MINUS, mode,
+ 					 copy_rtx (init), before_wrap);
+       after_wrap = simplify_gen_binary (MINUS, mode,
+ 					before_wrap, stride);
+       if (GET_CODE (after_wrap) != CONST_INT)
+ 	{
+ 	  after_wrap = simplify_gen_binary (MINUS, mode, mode_max, stride);
+ 	  after_wrap = simplify_gen_binary (PLUS, mode, after_wrap, const1_rtx);
+ 	}
+       break;
+     default:
+       abort ();
+     }
+ 
+   /* If this is const_true_rtx and we did not take a conservative aproximation
+      of after_wrap above, we might iterate the calculation (but of course we
+      would have to take care about infinite cases).  Ignore this for now.  */
+   rqmt = simplify_gen_relational (cond, SImode, mode, after_wrap, lim);
+   if (rqmt != const0_rtx)
+     return NULL_RTX;
+ 
+   return simplify_gen_binary (PLUS, mode, n_to_wrap, const1_rtx);
+ }
+ 
  /* Return RTX expression representing number of iterations of loop as bounded
     by test described by DESC (in the case loop really has multiple exit
     edges, fewer iterations may happen in the practice).  
*************** count_loop_iterations (desc, init, lim)
*** 524,542 ****
    /* Compute absolute value of the difference of initial and final value.  */
    if (INTVAL (stride) > 0)
      {
!       /* Bypass nonsential tests.  */
        if (cond == EQ || cond == GE || cond == GT || cond == GEU
  	  || cond == GTU)
! 	return NULL;
        exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
  				 lim, init);
      }
    else
      {
-       /* Bypass nonsential tests.  */
        if (cond == EQ || cond == LE || cond == LT || cond == LEU
  	  || cond == LTU)
! 	return NULL;
        exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
  				 init, lim);
        stride = simplify_gen_unary (NEG, GET_MODE (desc->var),
--- 643,662 ----
    /* Compute absolute value of the difference of initial and final value.  */
    if (INTVAL (stride) > 0)
      {
!       /* Handle strange tests specially.  */
        if (cond == EQ || cond == GE || cond == GT || cond == GEU
  	  || cond == GTU)
! 	return count_strange_loop_iterations (init, lim, cond, desc->postincr,
! 					      stride, GET_MODE (desc->var));
        exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
  				 lim, init);
      }
    else
      {
        if (cond == EQ || cond == LE || cond == LT || cond == LEU
  	  || cond == LTU)
! 	return count_strange_loop_iterations (init, lim, cond, desc->postincr,
! 					      stride, GET_MODE (desc->var));
        exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
  				 init, lim);
        stride = simplify_gen_unary (NEG, GET_MODE (desc->var),
*************** simple_loop_exit_p (loops, loop, exit_ed
*** 723,732 ****
    desc->lim_alts = variable_initial_values (e, desc->lim);
  
    /* Number of iterations. */
-   if (!count_loop_iterations (desc, NULL, NULL))
-     return false;
    desc->const_iter =
      constant_iterations (desc, &desc->niter, &desc->may_be_zero);
    return true;
  }
  
--- 843,852 ----
    desc->lim_alts = variable_initial_values (e, desc->lim);
  
    /* Number of iterations. */
    desc->const_iter =
      constant_iterations (desc, &desc->niter, &desc->may_be_zero);
+   if (!desc->const_iter && !count_loop_iterations (desc, NULL, NULL))
+     return false;
    return true;
  }