Patch: fix SPEC regressions

Patch: fix SPEC regressions

[Dale Johannesen]

This patch fixes the problems I ran into building SPEC on darwin last 
week.
(see description here):
http://gcc.gnu.org/ml/gcc-patches/2002-10/msg01588.html
Bootstrapped and tested with no regressions.

Index: doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.25
diff -u -d -b -w -c -3 -p -r1.25 doloop.c
cvs server: conflicting specifications of output style
*** doloop.c    7 Oct 2002 17:55:46 -0000       1.25
--- doloop.c    28 Oct 2002 19:34:04 -0000
*************** doloop_modify_runtime (loop, iterations_
*** 683,694 ****
         if (shift_count < 0)
         abort ();

!       if (!loop_info->preconditioned)
         diff = expand_simple_binop (GET_MODE (diff), PLUS,
!                                   diff, GEN_INT (abs_loop_inc - 1),
                                     diff, 1, OPTAB_LIB_WIDEN);

!       /* (abs (final - initial) + abs_inc * unroll_number - 1)
          / (abs_inc * unroll_number)  */
         diff = expand_simple_binop (GET_MODE (diff), LSHIFTRT,
                                   diff, GEN_INT (shift_count),
--- 683,698 ----
         if (shift_count < 0)
         abort ();

!       /* (abs (final - initial) + abs_inc - 1) */
         diff = expand_simple_binop (GET_MODE (diff), PLUS,
!                                 diff, GEN_INT (abs_inc - 1),
                                   diff, 1, OPTAB_LIB_WIDEN);

!       diff = expand_simple_binop (GET_MODE (diff), PLUS,
!                                 diff, GEN_INT (abs_loop_inc - 
abs_inc),
!                                 diff, 1, OPTAB_LIB_WIDEN);
!
!       /* (abs (final - initial) + abs_inc - 1 + abs_inc * 
unroll_number - abs_inc)
          / (abs_inc * unroll_number)  */
         diff = expand_simple_binop (GET_MODE (diff), LSHIFTRT,
                                   diff, GEN_INT (shift_count),
Index: loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.429
diff -u -d -b -w -c -3 -p -r1.429 loop.c
cvs server: conflicting specifications of output style
*** loop.c      15 Oct 2002 14:38:10 -0000      1.429
--- loop.c      28 Oct 2002 19:34:04 -0000
*************** loop_invariant_p (loop, x)
*** 3273,3278 ****
--- 3273,3285 ----
           && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO 
(x)])
         return 0;

+       /* Out-of-range regs can occur when we are called from 
unrolling.
+        These have always been created by the unroller and are set in
+        the loop, hence are never invariant. */
+
+       if (REGNO (x) >= regs->num)
+       return 0;
+
         if (regs->array[REGNO (x)].set_in_loop < 0)
         return 2;
  

Re: Patch: fix SPEC regressions

[Richard Henderson]

On Mon, Oct 28, 2002 at 11:40:27AM -0800, Dale Johannesen wrote:
> !       /* (abs (final - initial) + abs_inc - 1 + abs_inc * 
> unroll_number - abs_inc)
>          / (abs_inc * unroll_number)  */

Surely this simplifies to 

	(abs(final-initial) + abs_inc*unroll_number - 1) / ...


> +       if (REGNO (x) >= regs->num)
> +       return 0;

Ok.


r~

Re: Patch: fix SPEC regressions

[Dale Johannesen]

On Tuesday, October 29, 2002, at 07:46  AM, Richard Henderson wrote:

> On Mon, Oct 28, 2002 at 11:40:27AM -0800, Dale Johannesen wrote:
>> !       /* (abs (final - initial) + abs_inc - 1 + abs_inc *
>> unroll_number - abs_inc)
>>          / (abs_inc * unroll_number)  */
>
> Surely this simplifies to
>
> 	(abs(final-initial) + abs_inc*unroll_number - 1) / ...

Sure, I left it this way to make reading it easier.  Not that's
it's easy anyway.

>> +       if (REGNO (x) >= regs->num)
>> +       return 0;
>
> Ok.

Does this apply to the whole patch, or just the second part?

Re: Patch: fix SPEC regressions

[Richard Henderson]

On Tue, Oct 29, 2002 at 09:40:32AM -0800, Dale Johannesen wrote:
> Sure, I left it this way to make reading it easier.  Not that's
> it's easy anyway.

Err, but why?  Why are we computing it this way?


> Does this apply to the whole patch, or just the second part?

Just the second part for now.


r~

Re: Patch: fix SPEC regressions

[Dale Johannesen]

On Tuesday, October 29, 2002, at 10:38  AM, Richard Henderson wrote:

> On Tue, Oct 29, 2002 at 09:40:32AM -0800, Dale Johannesen wrote:
>> Sure, I left it this way to make reading it easier.  Not that's
>> it's easy anyway.
>
> Err, but why?  Why are we computing it this way?

Ah, that's a different question.  I deliberately didn't explain, in the
hope that somebody would derive it independently, thus giving us more
assurance we've finally gotten this right.  However:

We have a loop running from 'initial' to 'final' with increment 
'abs_inc',
and we're going to make 'unroll_number' copies of it.  Typically the
number of iterations of the original loop will not be exactly divisible
by unroll_number, and in that case we'll need to add an extra iteration
of the unrolled loop which is only partially executed.  As I said 
already,
preconditioning is expected to (and does) increment 'initial' 
appropriately
if any preiterations were done, so we don't have to worry about that.
Also, we assume that a runtime check for zero iterations was generated 
elsewhere
if needed, so we don't have to do anything special for that.

Note that 'final' is the expected value of the index after the loop; 
for the
common C form of loop for(i=0; i<final; i+=abs_inc) the loop body is 
not to be
executed with i=='final', the max value is final-abs_inc.  This form is 
used
in examples.

The increment for the unrolled loop will obviously be 
abs_inc*unroll_number,
which we define as t1.  For a given value of 'initial', it should be 
evident
that there are t1 different values of 'final' for which the number of
fully executed iterations are the same.  For example, suppose abs_inc=3,
initial=3, unroll_number=4.  Any value of 'final' between 13 and 24 
inclusive
requires 1 full iteration.  To round up the edge cases correctly we 
need to adjust
final-initial by abs_inc-1; thus,
   (final-initial+abs_inc-1)/t1
or ((13..24-3) + 2)/(3*4) in the example.

Of the t1 different values of 'final' for a given number of fully 
executed
iterations, there are from 0..unroll_number-1  possible extra 
iterations (of
the original loop) necessary (call this t2); we only care whether t2 is 
0 or not.
Evidently abs_inc different values of 'final' correspond to each t2 (in 
particular
to t2==0), and t2 is computed straightforwardly as
   ((final-initial+abs_inc-1)%t1)/abs_inc,
reducing the range first to 0..t1-1 then to 0..unroll_loops-1.  We only 
care
that t2!=0, which happens when
   ((final-initial+abs_inc-1)%t1) >= abs_inc
or for 15..24 in the example.  That is, the bottom abs_inc values of 
the t1 'final'
values do not require a second iteration, the rest do.

As you point out this simplifies to
    (abs(final-initial) + abs_inc*unroll_number - 1) / t1

Re: Patch: fix SPEC regressions

[Richard Henderson]

On Tue, Oct 29, 2002 at 03:10:20PM -0800, Dale Johannesen wrote:
> As you point out this simplifies to
>    (abs(final-initial) + abs_inc*unroll_number - 1) / t1

Thanks for the detailed explanation, but that still begs the
question of why we don't simplify the expression before 
computing it.


r~

Re: Patch: fix SPEC regressions

[Dale Johannesen]

On Thursday, October 31, 2002, at 03:18  PM, Richard Henderson wrote:

> On Tue, Oct 29, 2002 at 03:10:20PM -0800, Dale Johannesen wrote:
>> As you point out this simplifies to
>>    (abs(final-initial) + abs_inc*unroll_number - 1) / t1
>
> Thanks for the detailed explanation, but that still begs the
> question of why we don't simplify the expression before
> computing it.

So the code would correspond better to the algorithmic explanation
in the comments; not a great reason, I agree.  I'll rewrite it
simplified if you prefer.  Are you comfortable with the algorithm?

Re: Patch: fix SPEC regressions

[Richard Henderson]

On Thu, Oct 31, 2002 at 03:22:19PM -0800, Dale Johannesen wrote:
> I'll rewrite it simplified if you prefer.

Thanks.

> Are you comfortable with the algorithm?

Yes.  


r~

Re: Patch: fix SPEC regressions (rewrite)

[Dale Johannesen]

On Thursday, October 31, 2002, at 05:41  PM, Richard Henderson wrote:

> On Thu, Oct 31, 2002 at 03:22:19PM -0800, Dale Johannesen wrote:
>> I'll rewrite it simplified if you prefer.
> Thanks.

Here you go.   Bootstrapped and tested on Darwin; spec and PR 7130 work.

Index: doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.25
diff -u -d -b -w -c -3 -p -r1.25 doloop.c
*** doloop.c    7 Oct 2002 17:55:46 -0000       1.25
--- doloop.c    1 Nov 2002 20:32:40 -0000
*************** doloop_modify_runtime (loop, iterations_
*** 600,614 ****
        If the loop has been unrolled, the full calculation is

          t1 = abs_inc * unroll_number;          increment per loop
!        n = abs (final - initial) / t1;                full loops
!        n += (abs (final - initial) % t1) != 0;        partial loop

!      However, in certain cases the unrolled loop will be 
preconditioned
!      by emitting copies of the loop body with conditional branches,
!      so that the unrolled loop is always a full loop and thus needs
!      no exit tests.  In this case we don't want to add the partial
!      loop count.  As above, when t1 is a power of two we don't need to
!      worry about overflow.

        The division and modulo operations can be avoided by requiring
        that the increment is a power of 2 (precondition_loop_p enforces
--- 600,617 ----
        If the loop has been unrolled, the full calculation is

          t1 = abs_inc * unroll_number;                  increment per 
loop
!        n = (abs (final - initial) + abs_inc - 1) / t1;    full loops
!        n += (abs (final - initial) + abs_inc - 1) % t1) >= abs_inc;
!                                                           partial loop
!      which works out to be equivalent to

!        n = (abs (final - initial) + t1 - 1) / t1;
!
!      In the case where the loop was preconditioned, a few iterations
!      may have been executed earlier; but 'initial' was adjusted as 
they
!      were executed, so we don't need anything special for that case 
here.
!      As above, when t1 is a power of two we don't need to worry about
!      overflow.

        The division and modulo operations can be avoided by requiring
        that the increment is a power of 2 (precondition_loop_p enforces
*************** doloop_modify_runtime (loop, iterations_
*** 683,689 ****
         if (shift_count < 0)
         abort ();

!       if (!loop_info->preconditioned)
         diff = expand_simple_binop (GET_MODE (diff), PLUS,
                                     diff, GEN_INT (abs_loop_inc - 1),
                                     diff, 1, OPTAB_LIB_WIDEN);
--- 686,692 ----
         if (shift_count < 0)
         abort ();

!       /* (abs (final - initial) + abs_inc * unroll_number - 1) */
         diff = expand_simple_binop (GET_MODE (diff), PLUS,
                                   diff, GEN_INT (abs_loop_inc - 1),
                                   diff, 1, OPTAB_LIB_WIDEN);

Re: Patch: fix SPEC regressions (rewrite)

[Richard Henderson]

On Fri, Nov 01, 2002 at 03:55:42PM -0800, Dale Johannesen wrote:
> Here you go.   Bootstrapped and tested on Darwin; spec and PR 7130 work.

Ok.


r~

Re: Patch: fix SPEC regressions

[Eric Botcazou]

On Monday 28 October 2002 20:40, Dale Johannesen wrote:
> This patch fixes the problems I ran into building SPEC on darwin last
> week.

The installed version of that patch (btw, Dale, you should put the complete 
ChangeLog entry

	* doloop.c (doloop_modify_runtime):  Fix loop count computation
	for unrolled loops.
	* loop.c (loop_invariant_p):  Support calling from unroller.

as the commit message, this makes it much easier to grab the modifications) 
fixes PR optimization/8599, which is a regression from gcc 3.2 present on 
gcc-3_2-branch.

Bootstrapped/regtested on i586-redhat-linux-gnu (c,c++,objc,f77). OK to 
install once the branch is reopen ? OK to install the testcase on mainline as 
well ?

-- 
Eric Botcazou


2002-11-21  Eric Botcazou  <ebotcazou@libertysurf.fr>

	PR optimization/8599

	2002-11-04  Dale Johannesen  <dalej@apple.com>

	* doloop.c (doloop_modify_runtime):  Fix loop count computation
	for unrolled loops.
	* loop.c (loop_invariant_p):  Support calling from unroller.


2002-11-21  Eric Botcazou  <ebotcazou@libertysurf.fr>

	* gcc.dg/i386-unroll-1.c: New test.


/* PR optimization/8599 */
/* { dg-do run { target i?86-*-* } } */
/* { dg-options "-mcpu=k6 -O2 -funroll-loops" } */

void *array[4];

int main ()
{
 int i;

 for (i = 0; i < 4; i++)
   array[i] = 0;
 
 exit (0);
}

Re: Patch: fix SPEC regressions

[Richard Henderson]

On Thu, Nov 21, 2002 at 07:18:08PM +0100, Eric Botcazou wrote:
> Bootstrapped/regtested on i586-redhat-linux-gnu (c,c++,objc,f77). OK to 
> install once the branch is reopen ? OK to install the testcase on mainline as 
> well ?

Yes and yes.



r~

Re: Patch: fix SPEC regressions

[Eric Botcazou]

> 	* doloop.c (doloop_modify_runtime):  Fix loop count computation
> 	for unrolled loops.
> 	* loop.c (loop_invariant_p):  Support calling from unroller.

I'm asking permission to remove the backport of that patch from the 3.2 branch 
because, while fixing the computation for 4 iterations, it breaks it for any 
other number of iterations :-(

The original bug occurs because we start with 4 iterations, then lose the 
value through BIV elimination, then pre-condition the loop before unrolling 
it 4 times (the default setting), hence the subtil clash.

-- 
Eric Botcazou

Re: Patch: fix SPEC regressions

[Eric Botcazou]

> I'm asking permission to remove the backport of that patch from the 3.2
> branch because, while fixing the computation for 4 iterations, it breaks it
> for any other number of iterations :-(

And to commit this one instead, which gives the correct computation in all 
cases on K6 with -O2 -funroll-loops. It passed bootstrapping/regtesting on 
i586-redhat-linux-gnu and I've asked Franz Sirl to test it on powerpc too.

I think Dale's analysis
	http://gcc.gnu.org/ml/gcc-patches/2002-10/msg01815.html
is correct only for non-preconditioned loops on the 3.2 branch. For 
preconditioned loops, Alan's analysis is correct (quoted from doloop.c):

     However, in certain cases the unrolled loop will be preconditioned
     by emitting copies of the loop body with conditional branches,
     so that the unrolled loop is always a full loop and thus needs
     no exit tests.  In this case we don't want to add the partial
     loop count.

That is, we don't have to run the unrolled loop an additional time in order to 
run the few remaining loop iterations because preconditioning just handles 
this case.

Alan simply forgot to add the abs_inc-1 correction factor needed for every 
doloop loop.

> The original bug occurs because we start with 4 iterations, then lose the
> value through BIV elimination, then pre-condition the loop before unrolling
> it 4 times (the default setting), hence the subtil clash.

The original bug actually occurs for every multiple of 4: the loop is unrolled 
4 times and the resulting loop is executed (n/4-1) times instead of n/4 times 
when (n%4 == 0, n>0).

-- 
Eric Botcazou


2002-12-17  Eric Botcazou  <ebotcazou@libertysurf.fr>

	PR optimization/8599
	* doloop.c (doloop_modify_runtime): Fix loop count computation
	for preconditioned unrolled loops.

2002-12-17  Eric Botcazou  <ebotcazou@libertysurf.fr>

	* gcc.dg/i386-unroll-2.c: New test.


Index: doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.16.8.2
diff -u -r1.16.8.2 doloop.c
--- doloop.c	26 Sep 2002 23:10:38 -0000	1.16.8.2
+++ doloop.c	15 Dec 2002 18:44:55 -0000
@@ -598,9 +598,13 @@
 
      If the loop has been unrolled, the full calculation is
 
-       t1 = abs_inc * unroll_number;		increment per loop
-       n = abs (final - initial) / t1;		full loops
-       n += (abs (final - initial) % t1) != 0;	partial loop
+       t1 = abs_inc * unroll_number;		        increment per loop
+       n = (abs (final - initial) + abs_inc - 1) / t1;    full loops
+       n += ((abs (final - initial) + abs_inc - 1) % t1) >= abs_inc;
+                                                          partial loop
+     which works out to be equivalent to
+
+       n = (abs (final - initial) + t1 - 1) / t1;
 
      However, in certain cases the unrolled loop will be preconditioned
      by emitting copies of the loop body with conditional branches,
@@ -682,13 +686,15 @@
       if (shift_count < 0)
 	abort ();
 
-      if (!loop_info->preconditioned)
+      if (loop_info->preconditioned)
+	diff = expand_simple_binop (GET_MODE (diff), PLUS,
+				    diff, GEN_INT (abs_inc - 1),
+				    diff, 1, OPTAB_LIB_WIDEN);
+      else
 	diff = expand_simple_binop (GET_MODE (diff), PLUS,
 				    diff, GEN_INT (abs_loop_inc - 1),
 				    diff, 1, OPTAB_LIB_WIDEN);
 
-      /* (abs (final - initial) + abs_inc * unroll_number - 1)
-	 / (abs_inc * unroll_number)  */
       diff = expand_simple_binop (GET_MODE (diff), LSHIFTRT,
 				  diff, GEN_INT (shift_count),
 				  diff, 1, OPTAB_LIB_WIDEN);


/* PR optimization/8599 */
/* { dg-do run { target i?86-*-* } } */
/* { dg-options "-mcpu=k6 -O2 -funroll-loops" } */

extern void exit (int);

void *array[5];

int main ()
{
  int i;

  for (i = 0; i < 5; i++)
    array[i] = 0;

  exit (0);
}

Re: Patch: fix SPEC regressions

[Richard Henderson]

On Tue, Dec 17, 2002 at 02:30:16PM +0100, Eric Botcazou wrote:
> And to commit this one instead, which gives the correct computation in all 
> cases on K6 with -O2 -funroll-loops. It passed bootstrapping/regtesting on 
> i586-redhat-linux-gnu and I've asked Franz Sirl to test it on powerpc too.

Why doesn't this test case fail on mainline?


r~

Re: Patch: fix SPEC regressions

[Richard Henderson]

On Tue, Dec 17, 2002 at 02:30:16PM +0100, Eric Botcazou wrote:
> int main ()
> {
>   int i;
> 
>   for (i = 0; i < 5; i++)
>     array[i] = 0;
> 
>   exit (0);
> }

Incidentally, the following is a better test case because it 
actually fails visibly, and is tested on all targets.


r~


/* PR optimization/8599 */
/* { dg-do run } */
/* { dg-options "-O2 -funroll-loops" } */
/* { dg-options "-mcpu=k6 -O2 -funroll-loops" { target i?86-*-* } } */

extern void abort (void);

int array[6] = { 1,2,3,4,5,6 };

void foo()
{
  int i;

  for (i = 0; i < 5; i++)
    array[i] = 0;
}

int main()
{
  foo();
  if (array[0] || array [1] || array[2] || array[3] || array[4])
    abort ();
  if (array[5] != 6)
    abort ();
  return 0;
}

Re: Patch: fix SPEC regressions

[Eric Botcazou]

> Why doesn't this test case fail on mainline?

Because of your patch on mainline:

2002-07-21  Richard Henderson  <rth@redhat.com>

	* loop.h (LOOP_AUTO_UNROLL): Rename from LOOP_FIRST_PASS.
	* loop.c (strength_reduce): Update.
	* toplev.c (rest_of_compilation): Do unrolling in the first
	loop pass, not the second.

On the 3.2 branch, we generate very bad code for

  for (i = 0; i < 4; i++)
    array[i] = 0;

on K6 at -O2 -funroll-loops: we first strength-reduce, which makes us lose the 
number of iterations, then unroll using the default number of iterations (8), 
which is later changed to 4 because we are preconditioning the loop. Then we 
generate a runtime calculation of the number of iterations really needed (!).

With your patch we unroll 4 times, period.

-- 
Eric Botcazou

Re: Patch: fix SPEC regressions

[Eric Botcazou]

> And to commit this one instead, which gives the correct computation in all
> cases on K6 with -O2 -funroll-loops. It passed bootstrapping/regtesting on
> i586-redhat-linux-gnu and I've asked Franz Sirl to test it on powerpc too.

Franz reported that the patch regtested fine on powerpc and i686.

-- 
Eric Botcazou

Re: Patch: fix SPEC regressions

[Richard Henderson]

On Tue, Dec 17, 2002 at 02:30:16PM +0100, Eric Botcazou wrote:
> 	PR optimization/8599
> 	* doloop.c (doloop_modify_runtime): Fix loop count computation
> 	for preconditioned unrolled loops.

Ok.


r~

Re: Patch: fix SPEC regressions

[Eric Botcazou]

> Incidentally, the following is a better test case because it
> actually fails visibly, and is tested on all targets.

Thanks. Now gcc.dg/unroll-1.c on the branch.

-- 
Eric Botcazou