SUBREG GIVs - Suggestion for a quick hack.

SUBREG GIVs - Suggestion for a quick hack.

[Toon Moene]

L.S.,

The more I look into the problem of getting SUBREG general  
induction variables being recognised by general_induction_var and  
simplify_giv_expr, the less I believe this will ever be possible  
without the grant-rewrite-of-loop-we-all-learned-to-fear.

However, for the performance problems on the Alpha, a quick hack  
seems to suggest itself.

The problematic induction variables are invariably ;-) part of the  
following sequence:

(set (subreg:DI (reg:SI x)) (<some construct<))
(set (reg:DI y) (sign_extend:DI (reg:SI x)))

Now, IMNSHO, this is equivalent to (whether this subreg variable is  
promoted or not and modulo overflow of `x', which leads to  
undefined behaviour anyway):

(set (subreg:DI (reg:SI x)) (<some construct>))
(set (reg:DI y) (<some construct>))

[ This only works if <some construct> doesn't have side effects ]

If <some construct> will make `y' a GIV, this will be recognised.   
Later optimisation passes like flow will eliminate the redundant  
store into a part of register `x', because it won't be used.

So it seems a quickie scan over the INSNs in the loop to `combine'  
these pairs would have all other strength reduction proceed  
normally.

Please comment on this, before I start out to try it (I would  
especially be interested in how to change the second of the two  
set's, i.e. how to `CONS' <some construct> into it ;-).

Regards,
Toon.

Re: SUBREG GIVs - Suggestion for a quick hack.

[Richard Henderson]

> Please comment on this, before I start out to try it (I would  
> especially be interested in how to change the second of the two  
> set's, i.e. how to `CONS' <some construct> into it ;-).

I've been trying to reproduce this in C, and I can't.  Correct me
if I'm wrong about this C translation:

  void daxpy(int *_n, double dx[], double dy[], double *_da)
  {
    double da = *_da;
    int i, n = *_n, in;
    for (i = 1, in = n-1; in >= 0; ++i, --in)
      dy[i-1] = dy[i-1] + da*dx[i-1];
  }

because with this, I get 

        ldt $f1,0($17)
        mult $f11,$f1,$f1
        ldt $f10,0($18)
        addt $f10,$f1,$f10
        subl $1,1,$1
        addq $17,8,$17
        stt $f10,0($18)
        addq $18,8,$18
        bge $1,$37

which, other than scheduling, is perfect.   The difference I see in 
the initial RTL is this:

	C				Fortran
	-----------			--------------
	r81 = i				r89 = i - 1
	r82 = r81 * 8			r90 = sign_extend(r89)
	r83 = r82 + dy			r91 = r90 
	r84 = r83 - 8			r92 = r91 * 8
					r93 = r92 + dy

I.e:	a = (dy + i*8) - 8		a = (i - 1) * 8 + y

I wonder how much effort it would be to get Fortran to emit its
accesses in this way.  If the answer is not too much, it would be 
a quick way to determine if this form is generally more recognizable
by the backend.


r~

Re: SUBREG GIVs - Suggestion for a quick hack.

[Richard Henderson]

I wrote:

> I wonder how much effort it would be to get Fortran to emit its
> accesses in this way.  If the answer is not too much, it would be 
> a quick way to determine if this form is generally more recognizable
> by the backend.

Hmm.. FFECOM_FASTER_ARRAY_REFS seems to do the right thing for
the simple case, off to try out the others you posted.


r~

Re: SUBREG GIVs - Suggestion for a quick hack.

[Craig Burley]

>Hmm.. FFECOM_FASTER_ARRAY_REFS seems to do the right thing for
>the simple case, off to try out the others you posted.

It's been a long time since I added that, so beware of possible
bugs -- I haven't maintained that, and had forgotten about it
entirely until you mentioned it!  But it could indeed work just
fine.

        tq vm, (burley)

Re: SUBREG GIVs - Suggestion for a quick hack.

[Toon Moene]

Richard Henderson wrote:

>  Hmm.. FFECOM_FASTER_ARRAY_REFS seems to do the right
>  thing for the simple case, off to try out the others you
>  posted.

Indeed it does ... Also for rank > 1.

When FFECOM_FASTER_ARRAY_REFS is defined, the Fortran frontend goes  
to greater lengths to spell out address computations resulting from  
array indexing (instead of leaving it up to `expand_expr' in  
expr.c).  Apparently, this somehow circumvents the mode conversions  
between the index variable(s) and the addresses themselves.

I first thought this was caused by the following code in expr.c  
(line 4350):

          if (TYPE_PRECISION (index_type) != TYPE_PRECISION (sizetype))
            {
              index = convert (type_for_size (TYPE_PRECISION  
(sizetype), 0),
                               index);
              index_type = TREE_TYPE (index);
            }

but commenting it out is not a good idea (compiler runs into an  
abort at explow.c:628 ...).

Still, I think this is the correct lead:  The  
`FFECOM_FASTER_ARRAY_REFS' code results in all address computation  
being done in one mode, therefore circumventing the subreg ...  
sign_extend trouble.

However, there probably is a more correct way of solving this.

BTW, the rank-3 benchmark code I previously talked about (10.2  
seconds with an unmodified g77/egcs) now clocks in at 3.9, i.e. over  
a factor of 2.5 better.

HTH,
Toon.

PS:  The `FFECOM_FASTER_ARRAY_REFS' code is a hack that dates back  
to April 1995, when g77 was just out for two months.  We were  
desperately trying to solve the inefficient array indexing code and  
this was one of the "solutions", which was relegated to history a  
month later, because for some architectures, it actually slowed  
things down.  Of course, this was before we knew the real problem  
was the CEIL_DIV_EXPR in {int_}size_in_bytes ;-)

Re: SUBREG GIVs - Suggestion for a quick hack.

[Thomas Koenig]

Toon Moene wrote:

>However, there probably is a more correct way of solving this.

>BTW, the rank-3 benchmark code I previously talked about (10.2  
>seconds with an unmodified g77/egcs) now clocks in at 3.9, i.e. over  
>a factor of 2.5 better.

WOW.

If this stabilizes, quite a number of people will discard their
vendor's Fortran compilers in favour of g77 :-)
-- 
Thomas Koenig, Thomas.Koenig@ciw.uni-karlsruhe.de, ig25@dkauni2.bitnet.
The joy of engineering is to find a straight line on a double
logarithmic diagram.

Re: SUBREG GIVs - Suggestion for a quick hack.

[Richard Henderson]

> >a factor of 2.5 better.
> If this stabilizes, quite a number of people will discard their
> vendor's Fortran compilers in favour of g77 :-)

Actually, that's more a measure of how badly it was sucking before.

Even with that enabled, we do at best 80% the speed of Digital's
Fortran on Alpha EV5, and at worse less than 50%.


r~

Re: SUBREG GIVs - Suggestion for a quick hack.

[Richard Henderson]

> I first thought this was caused by the following code in expr.c (line 4350):
> 
>           if (TYPE_PRECISION (index_type) != TYPE_PRECISION (sizetype))
>             {
>               index = convert (type_for_size (TYPE_PRECISION (sizetype), 0),
>                                index);
>               index_type = TREE_TYPE (index);
>             }

Hah.  Good eyes.  It is that bit of code.  It is needed, yes, but
it needs to be done earlier, before the array index bias is removed.


r~



Wed Oct  1 17:47:48 1997  Richard Henderson  <rth@cygnus.com>

	* expr.c (get_inner_reference): Remove the array bias after 
	converting the index to Pmode.
	

Index: expr.c
===================================================================
RCS file: /cvs/cvsfiles/egcs/gcc/expr.c,v
retrieving revision 1.10
diff -u -p -d -r1.10 expr.c
--- expr.c	1997/09/22 17:41:29	1.10
+++ expr.c	1997/10/02 00:48:20
@@ -4344,15 +4344,15 @@ get_inner_reference (exp, pbitsize, pbit
 	    = domain ? TYPE_MIN_VALUE (domain) : integer_zero_node;
 	  tree index_type = TREE_TYPE (index);
 
-	  if (! integer_zerop (low_bound))
-	    index = fold (build (MINUS_EXPR, index_type, index, low_bound));
-
 	  if (TYPE_PRECISION (index_type) != TYPE_PRECISION (sizetype))
 	    {
 	      index = convert (type_for_size (TYPE_PRECISION (sizetype), 0),
 			       index);
 	      index_type = TREE_TYPE (index);
 	    }
+
+	  if (! integer_zerop (low_bound))
+	    index = fold (build (MINUS_EXPR, index_type, index, low_bound));
 
 	  index = fold (build (MULT_EXPR, index_type, index,
 			       convert (index_type,

Re: SUBREG GIVs - Suggestion for a quick hack.

[Toon Moene]

I wrote:

> >a factor of 2.5 better.

Thomas Koenig:

> If this stabilizes, quite a number of people will discard their
> vendor's Fortran compilers in favour of g77 :-)

Yeah, I had to be more careful with this - this little (750 line)  
program is extremely dependent on strength reduction; not all  
Fortran code will see a 2.5 time speedup ;-)

It's bs3dvw.f (the 21x21x21 case) from:

http://perso.club-internet.fr/queutey/Linux/Bench/bench.html

Richard Henderson:

>  Actually, that's more a measure of how badly it was
>  sucking before.
>
>  Even with that enabled, we do at best 80% the speed of
>  Digital's Fortran on Alpha EV5, and at worse less than
>  50%.

Aah, but I did two other things:

First I applied the following patch by Jeff Law that fixes the  
suboptimal recognition of GIVs due to removal of some special case  
ARRAY_REF code from expand_expr (see my mail dd 14th of September):

Index: loop.c
===================================================================
RCS file: /cvs/cvsfiles/egcs/gcc/loop.c,v
retrieving revision 1.11
diff -c -3 -p -r1.11 loop.c
*** loop.c	1997/09/11 17:08:01	1.11
--- loop.c	1997/09/18 05:31:23
*************** simplify_giv_expr (x, benefit)
*** 5368,5383 ****
  	  case CONST_INT:
  	  case USE:
  	    /* Both invariant.  Only valid if sum is machine operand.
! 	       First strip off possible USE on first operand.  */
  	    if (GET_CODE (arg0) == USE)
  	      arg0 = XEXP (arg0, 0);

  	    tem = 0;
  	    if (CONSTANT_P (arg0) && GET_CODE (arg1) == CONST_INT)
  	      {
  		tem = plus_constant (arg0, INTVAL (arg1));
  		if (GET_CODE (tem) != CONST_INT)
  		  tem = gen_rtx (USE, mode, tem);
  	      }

  	    return tem;
--- 5368,5394 ----
  	  case CONST_INT:
  	  case USE:
  	    /* Both invariant.  Only valid if sum is machine operand.
! 	       First strip off possible USE on the operands.  */
  	    if (GET_CODE (arg0) == USE)
  	      arg0 = XEXP (arg0, 0);

+ 	    if (GET_CODE (arg1) == USE)
+ 	      arg1 = XEXP (arg1, 0);
+
  	    tem = 0;
  	    if (CONSTANT_P (arg0) && GET_CODE (arg1) == CONST_INT)
  	      {
  		tem = plus_constant (arg0, INTVAL (arg1));
  		if (GET_CODE (tem) != CONST_INT)
  		  tem = gen_rtx (USE, mode, tem);
+ 	      }
+ 	    else
+ 	      {
+ 		/* Adding two invariants must result in an invariant,
+ 		   so enclose addition operation inside a USE and
+ 		   return it.  I have no clue what might break because
+ 		   of this.  */
+ 		tem = gen_rtx (USE, mode, gen_rtx (PLUS, mode,  
arg0, arg1));
  	      }

  	    return tem;

and, of course, I run loop_optimize twice.

I'll try your expr.c patch tonight (that's tomorrow morning for you :-)

Cheers,
Toon.

Re: SUBREG GIVs - Suggestion for a quick hack.

[Richard Henderson]

> First I applied the following patch by Jeff Law that fixes the  
> suboptimal recognition of GIVs due to removal of some special case  
> ARRAY_REF code from expand_expr (see my mail dd 14th of September):

Actually, Jeff checked that patch in, so I was using it as well.

> and, of course, I run loop_optimize twice.

Doesn't appear to make much difference in the cases I'm trying.

> I'll try your expr.c patch tonight (that's tomorrow morning for you :-)

Ho hum..  while it was sufficient for rank 1 daxpy, it didn't do
well at all on rank 2 resid.  Perhaps tomorrow I'll map out what
is being done differently.



r~

Re: SUBREG GIVs - Suggestion for a quick hack.

[Jeffrey A Law]

  In message < 199710020052.RAA18941@dot.cygnus.com >you write:
  > Wed Oct  1 17:47:48 1997  Richard Henderson  <rth@cygnus.com>
  > 
  > 	* expr.c (get_inner_reference): Remove the array bias after 
  > 	converting the index to Pmode.
I've installed this patch (yippie!)

jeff