Re: -freduce-all-givs and fortran

Re: -freduce-all-givs and fortran

[Toon Moene]

Andreas wrote:

>    168.wupwise       1600     418         382*     1600     417         384*
>    171.swim          3100    1213         256*     3100    1040         298*
>    172.mgrid         1800    1017         177*     1800    1117         161*
>    173.applu         2100     759         277*     2100     813         258*
>    200.sixtrack      1100     577         191*     1100     534         206*

vs:

168.wupwise    444      360
171.swim      1012      306
172.mgrid     1036      174
173.applu      816      258
200.sixtrack   556      198

OK, so swim indeed gets most optimised "without" loop optimisation.

:-)

Someone who shall remain nameless showed me a (small) part of swim that
should fall wholly within the "fair use" clause.  I mailed it home to
study it there (where I actually have access to g77 :-)

However, I think I already know what's wrong ...

Sixtrack is more complicated, but as its source code is available
online, it might be possible to track that one down too.

"Back ... in the USSR !"

--
Toon Moene, KNMI, PO Box 201, 3730 AE De Bilt, The Netherlands.
Tel. +31302206443, Fax +31302210407,  e-mail moene@knmi.nl
URL: http://www.knmi.nl/hirlam

Re: -freduce-all-givs and fortran

[Toon Moene]

I wrote:

> OK, so swim indeed gets most optimised "without" loop optimisation.
> 
> :-)
> 
> Someone who shall remain nameless showed me a (small) part of swim that
> should fall wholly within the "fair use" clause.  I mailed it home to
> study it there (where I actually have access to g77 :-)
> 
> However, I think I already know what's wrong ...

The problem is easily exemplified by the following code:

$ cat swim.f
      SUBROUTINE SWIM
      PARAMETER(N=100)
      COMMON /COM/ A(N), B(N), C(N)
      COMMON /INT/ M
      DO I = 1, M
         A(I) = B(I) + C(I)
      ENDDO
      END

Because giv-combining should notice that any reference to A, B and C is
simply addr(COMMON) + constant, the final number of registers needed in
the loop is just 2: One for that base address and one for the loop
counter.  However, this is what we get from g77 -O2 -S swim.f when using
the latest snapshot (on alphaev6-unknown-linux-gnu):

$L5:
        lds $f10,0($3)
        lds $f11,0($2)
        mov $6,$1
        lda $3,4($3)
        addl $1,$31,$5
        lda $2,4($2)
        lda $6,-1($6)
        adds $f10,$f11,$f10
        sts $f10,0($4)
        lda $4,4($4)
        bge $5,$L5

which uses 6 integer registers ($1 .. $6) [I get the feeling Alpha is
even worse off than all other architectures here] but at least it's
clear that the three registers for addressing $3, $2 and $4 is overdone
by 2.

More arrays in this common block make this worse (the original swim code
had 7, which means 8 registers in the inner loop, 2 more than available
to a Pentium I/II/III/IV or Athlon).

Somehow, the giv-combine code doesn't examine the base addresses of
these arrays [quoting swim.f.11.loop]:

Giv 78: insn 38 src reg 69 benefit 4 lifetime 1 replaceable ncav
 mult (4)
 add  (0)
Giv 79: insn 39 src reg 69 benefit 8 lifetime 5 replaceable
 mult (4)
 add  (-4)
Giv 80: insn 40 src reg 69 benefit 4 lifetime 8 replaceable
 mult (4)
 add  (const (plus (symbol_ref ("com_")) (-4)))
Giv 88: insn 51 src reg 69 benefit 4 lifetime 3 replaceable
 mult (4)
 add  (const (plus (symbol_ref ("com_")) (396)))
Giv 96: insn 62 src reg 69 benefit 4 lifetime 2 replaceable
 mult (4)
 add  (const (plus (symbol_ref ("com_")) (796)))
Dest address: insn 64 src reg 69 benefit 4 lifetime 1 replaceable
 mult (4)
 add  (const (plus (symbol_ref ("com_")) (396)))
Dest address: insn 66 src reg 69 benefit 4 lifetime 1 replaceable
 mult (4)
 add  (const (plus (symbol_ref ("com_")) (796)))
Dest address: insn 69 src reg 69 benefit 4 lifetime 1 replaceable
 mult (4)
 add  (const (plus (symbol_ref ("com_")) (-4)))
Giv 101: insn 75 src reg 69 benefit 4 lifetime 1 replaceable
 mult (1)                                                   
 add  (1)                                                   
Giv 74: insn 22 src reg 70 benefit 4 lifetime 1 replaceable
 mult (1)                                                  
 add  (-1)                                                 
Loop iterations: Initial value not constant (reg 70).
Final biv value for 70, biv dead after loop exit.
Cannot eliminate biv 70: biv used in insn 27.
Sorted combine statistics:
 {22, 0}
giv at 22 reduced to (reg 108)
biv 69 can be eliminated.
Sorted combine statistics:
 {39, 8} {69, 4} {66, 4} {64, 4} {75, 0} {62, 0} {51, 0} {40, 0} {38, 0}

Note that it *does* notice that register 69 is the source of all these
base addresses.

Perhaps I find time during the weekend to dig into this.

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
Join GNU Fortran 95: http://g95.sourceforge.net/ (under construction)

Re: -freduce-all-givs and fortran

[Richard Henderson]

On Thu, Sep 06, 2001 at 10:28:08PM +0200, Toon Moene wrote:
> Somehow, the giv-combine code doesn't examine the base addresses of
> these arrays [quoting swim.f.11.loop]:
[...]
> Giv 80: insn 40 src reg 69 benefit 4 lifetime 8 replaceable
>  mult (4)
>  add  (const (plus (symbol_ref ("com_")) (-4)))
> Giv 88: insn 51 src reg 69 benefit 4 lifetime 3 replaceable
>  mult (4)
>  add  (const (plus (symbol_ref ("com_")) (396)))

Whee.


r~



Index: simplify-rtx.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/simplify-rtx.c,v
retrieving revision 1.41.2.3
diff -c -p -d -r1.41.2.3 simplify-rtx.c
*** simplify-rtx.c	2001/04/05 00:52:19	1.41.2.3
--- simplify-rtx.c	2001/09/06 21:45:16
*************** simplify_binary_operation (code, mode, o
*** 1110,1115 ****
--- 1110,1137 ----
  	       return simplify_gen_binary (AND, mode, op0,
  					   gen_rtx_NOT (mode, XEXP (op1, 0)));
  	   }
+ 
+ 	  /* Simplify operations with constants containing embedded offsets.  */
+ 	  if (GET_CODE (op0) == CONST)
+ 	    {
+ 	      tem = simplify_binary_operation (code, mode, XEXP (op0, 0), op1);
+ 	      if (tem)
+ 		{
+ 		  if (CONSTANT_P (op1) && ! CONSTANT_P (tem))
+ 		    tem = gen_rtx_CONST (mode, tem);
+ 		  return tem;
+ 		}
+ 	    }
+ 	  if (GET_CODE (op1) == CONST)
+ 	    {
+ 	      tem = simplify_binary_operation (code, mode, op0, XEXP (op1, 0));
+ 	      if (tem)
+ 		{
+ 		  if (CONSTANT_P (op0) && ! CONSTANT_P (tem))
+ 		    tem = gen_rtx_CONST (mode, tem);
+ 		  return tem;
+ 		}
+ 	    }
  	  break;
  
  	case MULT:

Re: -freduce-all-givs and fortran

[Dan Nicolaescu]

How about the following code?

It shows another issue that occurs in swim from SPEC
(for the people that have access to SPEC, look at subroutine calc1)

      SUBROUTINE TEST
      PARAMETER(N=100,M=113)
      COMMON /COM/ A(N,M), B(N,M), C(N,M), D(N,M)
      DO I = 1, N
         DO J = 1, M
            A(I,J) = B(I+1,J) + C(I,J)
            D(I,J) = B(I+1,J) + C(I,J)
         ENDDO
      ENDDO
      END


      SUBROUTINE TEST2
      PARAMETER(N=100,M=113)
      COMMON /COM/ A(N,M), B(N,M), C(N,M), D(N,M)
      DO I = 1, N
         DO J = 1, M
            A(I,J) = B(I,J) + C(I,J)
            D(I,J) = B(I,J) + C(I,J)
         ENDDO
      ENDDO
      END


The innner loop for both functions as compiled by 3.0 -O2 on SPARC:

In the first subroutine:

.LL9:
        ld      [%i5], %f2
        addcc   %g1, -1, %g1
        ld      [%i2], %f3
        add     %i5, 400, %i5
        fadds   %f3, %f2, %f3
        st      %f3, [%i4]         <- after this store
        ld      [%i2], %f4         <- this is reloaded
        add     %i4, 400, %i4
        fadds   %f4, %f2, %f4
        add     %i2, 400, %i2
        st      %f4, [%i3]
        bpos    .LL9
        add     %i3, 400, %i3




In the second one everything is fine:


.LL22:
        ld      [%i5], %f2
        addcc   %g1, -1, %g1
        ld      [%i4], %f3
        add     %i5, 400, %i5
        fadds   %f2, %f3, %f2
        add     %i4, 400, %i4
        st      %f2, [%i3]
        st      %f2, [%i2]
        add     %i2, 400, %i2
        bpos    .LL22
        add     %i3, 400, %i3

Re: -freduce-all-givs and fortran

[Andreas Jaeger]

Andreas Jaeger <aj@suse.de> writes:

> Just for reference, I've run the SPECfp2000 Fortran77 tests once with
> these flags on an AMD Athlon 1.133 Ghz system:
>
> Base: -O2 -march=athlon -malign-double
> Peak: -O2 -march=athlon -malign-double -fno-move-all-movables  -fno-reduce-all-givs
>
> Here're the results:
>                                     Estimated                     Estimated
>                    Base      Base      Base      Peak      Peak      Peak
>    Benchmarks    Ref Time  Run Time   Ratio    Ref Time  Run Time   Ratio
>    ------------  --------  --------  --------  --------  --------  --------
>    168.wupwise       1600     418         382*     1600     417         384*
>    171.swim          3100    1213         256*     3100    1040         298*
>    172.mgrid         1800    1017         177*     1800    1117         161*
>    173.applu         2100     759         277*     2100     813         258*
>    200.sixtrack      1100     577         191*     1100     534         206*
>
> 301.apsi had some errors and couldn't be tested.
>
> Using -fno-move-all-movables  -fno-reduce-all-givs is a performance
> gain for 171.swim and 200.sixtrack but pessimizes 172.grid and
> 173.app, 168.wupwise is indifferent.

Toon Moene asked:
|> Fascinating ... Do 171.swim and 200.sixtrack profit from loop
|> optimization *at all* ?  What happens if you use
|> 
|> -O2 -march=athlon -malign-double -fno-strength-reduce

The numbers with -O2 -march=athlon -malign-double -fno-strength-reduce
are:
             Run Time  Ratio
168.wupwise    444      360
171.swim      1012      306
172.mgrid     1036      174
173.applu      816      258
200.sixtrack   556      198

Andreas
-- 
 Andreas Jaeger
  SuSE Labs aj@suse.de
   private aj@arthur.inka.de
    http://www.suse.de/~aj

Re: -freduce-all-givs and fortran

[Toon Moene]

Andreas Jaeger wrote:

> Toon Moene <moene@knmi.nl> writes:

> >> Using -fno-move-all-movables  -fno-reduce-all-givs is a
> >> performance gain for 171.swim and 200.sixtrack but pessimizes
> >> 172.[m]grid and 173.app[lu], 168.wupwise is indifferent.
> >
> > Fascinating ... Do 171.swim and 200.sixtrack profit from loop
> > optimization *at all* ?  What happens if you use
> >
> > -O2 -march=athlon -malign-double -fno-strength-reduce

> I'll run some tests later.

Thanks.

> Anything else you like to see tested for
> those two?

Nothing that comes to mind now.  The problem is, for further
experimentation I need the source code, and shelling out $500 to SPEC
just for the pleasure of being able to look at 171.swim and 200.sixtrack
is a bit overdone, as far as I am concerned ...

However, it looks like there is a correlation between "getting a strong
boost from Jakub's giv-combine fix" and "doing bad with aggressive giv
strength reduction" (both 171.swim and 200.sixtrack).

It could be that both programs need a lot of extra registers for givs,
while somehow they are impossible to combine.  Unfortunately, I cannot
come up with example code that has this property, off hand.

--
Toon Moene, KNMI, PO Box 201, 3730 AE De Bilt, The Netherlands.
Tel. +31302206443, Fax +31302210407,  e-mail moene@knmi.nl
URL: http://www.knmi.nl/hirlam

Re: -freduce-all-givs and fortran

[Andreas Jaeger]

Toon Moene <moene@knmi.nl> writes:

>> Using -fno-move-all-movables  -fno-reduce-all-givs is a 
>> performance gain for 171.swim and 200.sixtrack but pessimizes 
>> 172.[m]grid and 173.app[lu], 168.wupwise is indifferent.
>
> Fascinating ... Do 171.swim and 200.sixtrack profit from loop
> optimization *at all* ?  What happens if you use
>
> -O2 -march=athlon -malign-double -fno-strength-reduce

I'll run some tests later.  Anything else you like to see tested for
those two?

Andreas
-- 
 Andreas Jaeger
  SuSE Labs aj@suse.de
   private aj@arthur.inka.de
    http://www.suse.de/~aj

Re: -freduce-all-givs and fortran

[Toon Moene]

> Using -fno-move-all-movables  -fno-reduce-all-givs is a 
> performance gain for 171.swim and 200.sixtrack but pessimizes 
> 172.[m]grid and 173.app[lu], 168.wupwise is indifferent.

Fascinating ... Do 171.swim and 200.sixtrack profit from loop
optimization *at all* ?  What happens if you use

-O2 -march=athlon -malign-double -fno-strength-reduce

?

--
Toon Moene, KNMI, PO Box 201, 3730 AE De Bilt, The Netherlands.
Tel. +31302206443, Fax +31302210407,  e-mail moene@knmi.nl
URL: http://www.knmi.nl/hirlam

Re: -freduce-all-givs and fortran

[Andreas Jaeger]

Just for reference, I've run the SPECfp2000 Fortran77 tests once with
these flags on an AMD Athlon 1.133 Ghz system:

Base: -O2 -march=athlon -malign-double
Peak: -O2 -march=athlon -malign-double -fno-move-all-movables  -fno-reduce-all-givs

Here're the results:
                                    Estimated                     Estimated
                   Base      Base      Base      Peak      Peak      Peak
   Benchmarks    Ref Time  Run Time   Ratio    Ref Time  Run Time   Ratio
   ------------  --------  --------  --------  --------  --------  --------
   168.wupwise       1600     418         382*     1600     417         384*
   171.swim          3100    1213         256*     3100    1040         298*
   172.mgrid         1800    1017         177*     1800    1117         161*
   173.applu         2100     759         277*     2100     813         258*
   200.sixtrack      1100     577         191*     1100     534         206*

301.apsi had some errors and couldn't be tested.

Using -fno-move-all-movables  -fno-reduce-all-givs is a performance
gain for 171.swim and 200.sixtrack but pessimizes 172.grid and
173.app, 168.wupwise is indifferent.

Andreas
-- 
 Andreas Jaeger
  SuSE Labs aj@suse.de
   private aj@arthur.inka.de
    http://www.suse.de/~aj

Re: -freduce-all-givs and fortran

[Toon Moene]

Jan Hubicka wrote:

> Can you please show me simple testcase?  It probably makes sense to
> reorganize loop optimizer - I am thinking about separating BIV/GIV
> discovery code to separate library, as it has more usage than just
> strength reducing and loop unrolling and then we can think about
> larger changes in this area.

Here's an example:

      SUBROUTINE SUB(A, B, C, D, N, M)
      INTEGER N, M
      REAL A(N, M), B(N, M), C(N, M), D(N, M)
      DO J = 1, M
         DO I = 1, N
            A(I, J) = B(I, J) + C(I, J) * D(I, J)
         ENDDO
      ENDDO
      END

If you do not reduce any givs, you need 7 integer registers in the inner
loop: one for A, B, C, D, I, J and N (because addr(A(I,J)) = addr(A) + I
- 1 + (J - 1) * N, etc.)

If you reduce all givs *and* move all loop invariants, you'll only need
5 registers: one for A, B, C, D and I.  This is also the minimum.

[ This analysis is slightly simplified w.r.t. the real result
  when you compile this with g77, because I is *not* the loop
  count in the g77-compiled assembler ]

The difference will get larger for higher-rank arrays.

Hope this helps,

--
Toon Moene, KNMI, PO Box 201, 3730 AE De Bilt, The Netherlands.
Tel. +31302206443, Fax +31302210407,  e-mail moene@knmi.nl
URL: http://www.knmi.nl/hirlam

Re: -freduce-all-givs and fortran

[Jan Hubicka]

> > the fortran fontend enables by default -freduce-all-gics and
> > -fmove-all-movables.  This causes important problem on i386, where 
> > reducing all givs brings too many temporary registers causing too 
> > many spills.
> 
> That depends.  Lots of Fortran code is written in a way that would lead
> to a *reduction* in the use of (integer) registers if you apply
> -freduce-all-givs *and* fmove-all-movables.
> 
> The examples I have at home, but in general:
> 
> 1. If you're dealing with nested loops over multi-rank arrays
> 
> and
> 
> 2. The arrays are passed as actual arguments to the subroutine
>    where the computation take place

Can you please show me simple testcase?  It probably makes sense to
reorganize loop optimizer - I am thinking about separating BIV/GIV
discovery code to separate library, as it has more usage than just
strength reducing and loop unrolling and then we can think about
larger changes in this area.

Honza

Re: -freduce-all-givs and fortran

[Toon Moene]

> the fortran fontend enables by default -freduce-all-gics and
> -fmove-all-movables.  This causes important problem on i386, where 
> reducing all givs brings too many temporary registers causing too 
> many spills.

That depends.  Lots of Fortran code is written in a way that would lead
to a *reduction* in the use of (integer) registers if you apply
-freduce-all-givs *and* fmove-all-movables.

The examples I have at home, but in general:

1. If you're dealing with nested loops over multi-rank arrays

and

2. The arrays are passed as actual arguments to the subroutine
   where the computation take place

then the combination -freduce-all-givs *and* fmove-all-movables is a win
(in number of integer registers used).

Of course, it would be better if loop.c contained code to detect this
itself, but this has turned out to be too hard (i.e. without a rewrite
of the loop optimising code).

Hope this helps,

--
Toon Moene, KNMI, PO Box 201, 3730 AE De Bilt, The Netherlands.
Tel. +31302206443, Fax +31302210407,  e-mail moene@knmi.nl
URL: http://www.knmi.nl/hirlam

-freduce-all-givs and fortran

[Jan Hubicka]

Hi,
the fortran fontend enables by default -freduce-all-gics and
-fmove-all-movables.  This causes important problem on i386, where reducing all
givs brings too many temporary registers causing too many spills.

I don't follow the philosophy behind this decision.  What makes code generated
from fortran different?  It may be well possible that these options were
believed to help numeric code and waste integer one, but then it should be
documented and different option should be made for that, as numeric
programs are not limited to fortran.

Whats about simply dropping this?

Honza

Wed Sep  5 15:54:47 CEST 2001  Jan Hubicka  <jh@suse.cz>
	* com.c (ffe_init_options): Do not default reducle_all_givs and
	move_all_movables.
	* invoke.texi (reduct-all-givs): No longer mention it is enabled
	by default.

Index: com.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/f/com.c,v
retrieving revision 1.127
diff -c -3 -p -r1.127 com.c
*** com.c	2001/07/20 13:27:40	1.127
--- com.c	2001/09/05 13:52:24
*************** static void
*** 14654,14661 ****
  ffe_init_options ()
  {
    /* Set default options for Fortran.  */
-   flag_move_all_movables = 1;
-   flag_reduce_all_givs = 1;
    flag_argument_noalias = 2;
    flag_errno_math = 0;
    flag_complex_divide_method = 1;
--- 14654,14659 ----
Index: invoke.texi
===================================================================
RCS file: /cvs/gcc/egcs/gcc/doc/invoke.texi,v
retrieving revision 1.51
diff -c -3 -p -r1.51 invoke.texi
*** invoke.texi	2001/09/05 08:30:35	1.51
--- invoke.texi	2001/09/05 13:53:34
*************** outside the loop.
*** 3570,3579 ****
  Forces all general-induction variables in loops to be
  strength-reduced.
  
- @emph{Note:} When compiling programs written in Fortran,
- @option{-fmove-all-movables} and @option{-freduce-all-givs} are enabled
- by default when you use the optimizer.
- 
  These options may generate better or worse code; results are highly
  dependent on the structure of loops within the source code.
  
--- 3570,3575 ----