Re: fix opt/2960

[Richard Henderson <rth at redhat dot com>]

On Tue, Oct 08, 2002 at 01:51:55AM +0200, Ulrich Weigand wrote:
> The doloop code actually has code to recognize this
> particular situation; check the ??? comment in 
> doloop_modify_runtime.  However, this code is used
> only when the iteration count is not known at 
> compile time; when it is (like here), no such check 
> is performed.

Yes, I saw that.  I'm going to do two things here.

First, I'm going to fix the doloop bug.  I believe the following
will do that.  I do not believe this "execute half of the loop
one more time" trick is even remotely valid in general.  I've
added some commentary as to what I believe ought to be verified,
but past that, I'm going to fail the doloop conversion.

Second, I'm going to revert the optimize_size patch.  I should
have given this more thought at the time, but I'll claim it was
late.  ;-)  Anyway, the issue is that if we don't duplicate the
loop test, then we're never able to eliminate the beginning test
for trivial loops such as

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

I'll assert that this is far more common (and more important)
than loop tests that include global variables.

Really, the duplication of the loop condition ought to be under
the control of the loop optimizer, not some jump pass.  Something
to be fixed, perhaps, for 3.4 with a cfg based loop optimizer.

Would the two of you bootstrap the following on ppc and s390 to
verify that it (1) cures your current regressions, and (2) doesn't
do anything else strange.  I'll give it a whirl on ia64.


r~


	* doloop.c (maybe_adjust_doloop_iterations): Break out from ...
	(doloop_modify_runtime): ... here.
	(doloop_optimize): Use it here as well.

Index: doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.25
diff -c -p -d -r1.25 doloop.c
*** doloop.c	7 Oct 2002 17:55:46 -0000	1.25
--- doloop.c	7 Oct 2002 23:58:52 -0000
*************** static unsigned HOST_WIDE_INT doloop_ite
*** 62,67 ****
--- 62,69 ----
    PARAMS ((const struct loop_info *, enum machine_mode, int));
  static int doloop_valid_p
    PARAMS ((const struct loop *, rtx));
+ static int maybe_adjust_doloop_iterations
+   PARAMS ((const struct loop *));
  static int doloop_modify
    PARAMS ((const struct loop *, rtx, rtx, rtx, rtx, rtx));
  static int doloop_modify_runtime
*************** doloop_valid_p (loop, jump_insn)
*** 394,399 ****
--- 396,494 ----
    return 1;
  }
  
+ /* Some code transformations can result in code akin to
+ 
+ 	  tmp = i + 1;
+ 	  ...
+ 	  goto scan_start;
+ 	top:
+ 	  tmp = tmp + 1;
+ 	scan_start:
+ 	  i = tmp;
+ 	  if (i < n) goto top;
+ 
+    We'll have already detected this form of loop in scan_loop,
+    and set loop->top and loop->scan_start appropriately.
+ 
+    In this situation, we skip the increment the first time through
+    the loop, which results in an incorrect estimate of the number
+    of iterations.  Adjust the difference to compensate.
+ 
+    One might conclude that this belongs in loop_iterations.  However,
+    after the doloop transformation is applied, the bits after scan_start
+    will have run loop_iterations+1 times, not loop_iterations times.
+    Thus this transformation is not valid in general.  We must be sure
+    that (1) nothing after scan_start touches volatile memory, and 
+    (2) nothing after scan_start depends on values set before the loop
+    that are not also killed by the blocks before scan_start.  I.e.
+ 
+ 	  i = 0;
+ 	  goto scan_start;
+ 	top:
+ 	  i++;
+ 	scan_start:
+ 	  i4 = i << 2;
+ 	  ...
+ 	  if (i < n) goto top;
+ 
+    is ok, but
+ 
+ 	  i = j = 0;
+ 	  goto scan_start;
+ 	top:
+ 	  i++;
+ 	scan_start:
+ 	  j++;
+ 	  ...
+ 	  if (i < n) goto top;
+ 
+    is not.  Given that we don't have proper register life analysis
+    information at this stage (or even a proper CFG), point 2 is 
+    very hard to validate.  Therefore, for now, give up.
+ 
+    Return 1 if the number of iterations must be adjusted and is
+    known to be safe.  Return 0 if the number of iterations does
+    not need to be adjusted.  Otherwise return -1.  */
+ 
+ static int
+ maybe_adjust_doloop_iterations (loop)
+      const struct loop *loop;
+ {
+   const struct loop_info *loop_info = LOOP_INFO (loop);
+ 
+   if (loop->scan_start)
+     {
+       rtx iteration_var = loop_info->iteration_var;
+       struct loop_ivs *ivs = LOOP_IVS (loop);
+       struct iv_class *bl;
+ 
+       if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
+ 	bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
+       else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
+ 	{
+ 	  struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
+ 	  bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
+ 	}
+       else
+ 	/* Iteration var must be an induction variable to get here.  */
+ 	abort ();
+ 
+       if (INSN_UID (bl->biv->insn) < max_uid_for_loop
+ 	  && INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
+ 	{
+ 	  if (loop_dump_stream)
+ 	    fprintf (loop_dump_stream,
+ 	         "Doloop: Basic induction var skips initial incr.\n");
+ 
+ 	  /* ??? If we could do the life analysis, this would be
+ 	     where we'd do it.  */
+ 	  return -1;
+ 	}
+     }
+ 
+   return 0;
+ }
+ 
  
  /* Modify the loop to use the low-overhead looping insn where LOOP
     describes the loop, ITERATIONS is an RTX containing the desired
*************** doloop_modify_runtime (loop, iterations_
*** 622,677 ****
  			      copy_rtx (neg_inc ? final_value : initial_value),
  			      NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
  
!   /* Some code transformations can result in code akin to
! 
! 	  tmp = i + 1;
! 	  ...
! 	  goto scan_start;
! 	top:
! 	  tmp = tmp + 1;
! 	scan_start:
! 	  i = tmp;
! 	  if (i < n) goto top;
! 
!      We'll have already detected this form of loop in scan_loop,
!      and set loop->top and loop->scan_start appropriately.
! 
!      In this situation, we skip the increment the first time through
!      the loop, which results in an incorrect estimate of the number
!      of iterations.  Adjust the difference to compensate.  */
!   /* ??? Logically, it would seem this belongs in loop_iterations.
!      However, this causes regressions e.g. on x86 execute/20011008-3.c,
!      so I do not believe we've properly characterized the exact nature
!      of the problem.  In the meantime, this fixes execute/20011126-2.c
!      on ia64 and some Ada front end miscompilation on ppc.  */
! 
!   if (loop->scan_start)
      {
!       rtx iteration_var = loop_info->iteration_var;
!       struct loop_ivs *ivs = LOOP_IVS (loop);
!       struct iv_class *bl;
! 
!       if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
! 	bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
!       else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
! 	{
! 	  struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
! 	  bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
! 	}
!       else
! 	/* Iteration var must be an induction variable to get here.  */
! 	abort ();
! 
!       if (INSN_UID (bl->biv->insn) < max_uid_for_loop
! 	  && INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
! 	{
! 	  if (loop_dump_stream)
! 	    fprintf (loop_dump_stream,
! 	         "Doloop: Basic induction var skips initial incr.\n");
! 
! 	  diff = expand_simple_binop (mode, PLUS, diff, GEN_INT (abs_inc),
! 				      diff, unsigned_p, OPTAB_LIB_WIDEN);
! 	}
      }
  
    abs_loop_inc = abs_inc * loop_info->unroll_number;
--- 717,732 ----
  			      copy_rtx (neg_inc ? final_value : initial_value),
  			      NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
  
!   switch (maybe_adjust_doloop_iterations (loop))
      {
!     case 0:
!       break;
!     case 1:
!       diff = expand_simple_binop (mode, PLUS, diff, GEN_INT (abs_inc),
! 				  diff, unsigned_p, OPTAB_LIB_WIDEN);
!       break;
!     default:
!       return 0;
      }
  
    abs_loop_inc = abs_inc * loop_info->unroll_number;
*************** doloop_optimize (loop)
*** 883,892 ****
      }
  
    if (n_iterations != 0)
!     /* Handle the simpler case, where we know the iteration count at
!        compile time.  */
!     return doloop_modify (loop, iterations, iterations_max, doloop_seq,
! 			  start_label, condition);
    else
      /* Handle the harder case, where we must add additional runtime tests.  */
      return doloop_modify_runtime (loop, iterations_max, doloop_seq,
--- 938,964 ----
      }
  
    if (n_iterations != 0)
!     {
!       /* Handle the simpler case, where we know the iteration count at
!          compile time.  */
! 
!       switch (maybe_adjust_doloop_iterations (loop))
! 	{
! 	case 0:
! 	  break;
! 	case 1:
! 	  /* ??? Should validate that we don't wrap here.  */
! 	  n_iterations++;
! 	  iterations = GEN_INT (n_iterations);
! 	  iterations_max = iterations;
! 	  break;
! 	default:
! 	  return 0;
! 	}
!       
!       return doloop_modify (loop, iterations, iterations_max, doloop_seq,
! 			    start_label, condition);
!     }
    else
      /* Handle the harder case, where we must add additional runtime tests.  */
      return doloop_modify_runtime (loop, iterations_max, doloop_seq,