Re: Loop unroll fixes

[Zoltan Hidvegi <hzoli at hzoli dot 2y dot net>]

> The third one is a regression.  It fails at -O2 -funroll-loops in gcc-3.0.1,
> but works with the same options in gcc-2.95.2.  This testcase is
> void
> do_loop(unsigned long c, char *m)
> {
>     unsigned long i = 0;
> 
>     do {
>         m[i] = 0;
>     } while (++i != c);
> }
> This one is fixed by the small doloop.c patch, which happens to be the one
> patch that Bernd did review.  There is a rather nice review in
> 	http://gcc.gnu.org/ml/gcc-patches/2001-09/msg00596.html

I still think that patch should be OK, here is a patch on the top of that
to make it complete.  The testcases.  First is the one I mentioned in my
previous mail.  It fails because the exit condition holds initially, but
becomes false after the first iteration because of overflow.

---------------- BEGIN TESTCASE ------------
void abort(void);

int
foo(int final)
{
    int count = 0;
    int i = (~0u >> 1);
    do {
        count++;
        if (count > 8)
            abort();
        i += (~0u >> 3) + 1;
    } while (i < final);
    return count;
}

int
main(void)
{
    if (foo(~0u >> 1) != 8)
        abort();
    return 0;
}
-------------- END TESTCASE --------------

The second failure is because the test if the exit condition holds
initially is done using signed compares even for unsigned values.

---------------- BEGIN TESTCASE ------------
void abort(void);

unsigned
foo(unsigned final)
{
    unsigned count = 0;
    unsigned i = (~0u >> 1);
    do {
        count++;
        if (count > 8)
            abort();
        i++;
    } while (i < final);
    return count;
}

int
main(void)
{
    if (foo((~0u >> 1) + 8) != 8)
        abort();
    return 0;
}
-------------- END TESTCASE --------------

Most of the patch below fixes the first problem, it has to be done for
both count-register and non-count-register loops.  The testcase above
only covers the non-count-reg loops.  It's hard to write a good test
for the count-register, since, at least on PowerPC AIX any function call
invalidates the count register, so the compiler will only use it if there
are no function calls in the loop, and also, the loop cannot have
multiple exits (I do not know the reason for the later, but it is
excluded in doloop_valid_p).  These only affect bottom-test do-while
loops.  The correct test sould increment the initial value, and compare
that to the final value.  If the exit condition hold, the loop must be
executed exacyly once.  Note that the direction of the compare should be
the opposite of the compare in the while condition, because we test for
the exit condition.  The signedness is determined by the
comparision_code, that fixes the second testcase.

I did not have a chance to run regression on these patches.

Zoli


 *** unroll.c	2001/10/11 11:30:35	1.1
 --- unroll.c	2001/10/11 13:12:26
 *************** unroll_loop (loop, insn_count, strength_
 *** 900,905 ****
 --- 900,908 ----
 	   register rtx diff;
 	   rtx *labels;
 	   int abs_inc, neg_inc;
 + 	  enum rtx_code cc = loop_info->comparison_code;
 + 	  int less_p     = (cc == LE  || cc == LEU || cc == LT  || cc == LTU);
 + 	  int unsigned_p = (cc == LEU || cc == GEU || cc == LTU || cc == GTU);
   
 	   map->reg_map = (rtx *) xmalloc (maxregnum * sizeof (rtx));
   
 *************** unroll_loop (loop, insn_count, strength_
 *** 957,967 ****
 	      case.  This check does not apply if the loop has a NE
 	      comparison at the end.  */
   
 ! 	  if (loop_info->comparison_code != NE)
 	     {
 ! 	      emit_cmp_and_jump_insns (initial_value, final_value,
 ! 				       neg_inc ? LE : GE,
 ! 				       NULL_RTX, mode, 0, 0, labels[1]);
 	       JUMP_LABEL (get_last_insn ()) = labels[1];
 	       LABEL_NUSES (labels[1])++;
 	     }
 --- 960,974 ----
 	      case.  This check does not apply if the loop has a NE
 	      comparison at the end.  */
   
 ! 	  if (cc != NE)
 	     {
 ! 	      rtx incremented_initval;
 ! 	      incremented_initval = expand_binop (mode, add_optab,
 ! 						  initial_value, increment,
 ! 						  NULL_RTX,0, OPTAB_LIB_WIDEN);
 ! 	      emit_cmp_and_jump_insns (incremented_initval, final_value,
 ! 				       less_p ? GE : LE, NULL_RTX,
 ! 				       mode, unsigned_p, 0, labels[1]);
 	       JUMP_LABEL (get_last_insn ()) = labels[1];
 	       LABEL_NUSES (labels[1])++;
 	     }
 *** doloop.c	2001/10/11 13:00:32	1.3
 --- doloop.c	2001/10/11 13:00:46
 *************** doloop_modify_runtime (loop, iterations_
 *** 642,654 ****
 	  is guaranteed to execute at least once.  */
 	 if (loop_info->unroll_number == 1)
 	 {
 	   /*  Emit insns to test if the loop will immediately
 	       terminate and to set the iteration count to 1 if true.  */
 	   label = gen_label_rtx();
 ! 	  emit_cmp_and_jump_insns (copy_rtx (initial_value),
 				    copy_rtx (loop_info->comparison_value),
 ! 				   comparison_code, NULL_RTX, mode, 0, 0,
 ! 				   label);
 	   JUMP_LABEL (get_last_insn ()) = label;
 	   LABEL_NUSES (label)++;
 	   emit_move_insn (iterations, const1_rtx);
 --- 642,659 ----
 	  is guaranteed to execute at least once.  */
 	 if (loop_info->unroll_number == 1)
 	 {
 + 	  rtx incremented_initval;
 	   /*  Emit insns to test if the loop will immediately
 	       terminate and to set the iteration count to 1 if true.  */
 	   label = gen_label_rtx();
 ! 	  incremented_initval = expand_binop (mode, add_optab,
 ! 					      copy_rtx (initial_value),
 ! 					      increment, NULL_RTX, 0,
 ! 					      OPTAB_LIB_WIDEN);
 ! 	  emit_cmp_and_jump_insns (incremented_initval,
 				    copy_rtx (loop_info->comparison_value),
 ! 				   comparison_code, NULL_RTX, mode,
 ! 				   unsigned_p, 0, label);
 	   JUMP_LABEL (get_last_insn ()) = label;
 	   LABEL_NUSES (label)++;
 	   emit_move_insn (iterations, const1_rtx);