[tree-ssa] RFC: Dropping INDIRECT_REF variables

[tree-ssa] RFC: Dropping INDIRECT_REF variables

[Diego Novillo]

Supporting INDIRECT_REF variables in the base framework is
getting to be increasingly annoying.  We have to handle several
corner cases and need additional support code that increases the
complexity of the implementation without giving us many benefits.

- To properly deal with INDIRECT_REF variables, we need to use
  shared tree nodes.  All the optimization and analysis passes
  rely on pointer equality for testing if two variables are the
  same.

- Sharing expressions is always a problem, particularly with
  passes like mudflap that need to instrument them.  Also, to
  properly support INDIRECT_REF variables we now need to rewrite
  both the INDIRECT_REF node (*P) and its base pointer (P).  This
  means that we have to selectively unshare INDIRECT_REF nodes.
  Not particularly hard, but brittle and annoying to maintain.

- More often than not, INDIRECT_REF variables represent aliased
  loads and stores.  This means that we don't really do anything
  interesting with them in the optimizers.  We just use them for
  liveness and alias analysis.

- The SSA->normal pass may also need to handle INDIRECT_REF
  variables with care.  Since an INDIRECT_REF variable has two
  SSA versions in it, overlapping live ranges of the base pointer
  or the INDIRECT_REF node may need extra supporting code (this
  is just a vague concern, Andrew?).


What I'm planning to do is stop renaming INDIRECT_REF nodes as if
they were variables.  This means that INDIRECT_REF nodes need not
be shared anymore and are treated as any other expression.  I'm
trying to think about the ramifications of this change.  So far:

- A whole chunk of code in the SSA/DFA passes would disappear.
  This can only be good.

- We disable the ability to treat non-aliased pointer
  dereferences as if they were variables.  We would lose the
  ability to do some optimizations like:

  foo ()                                 foo ()
  {                                      {
    char[7] * T.1;                          char[7] * T.1;
    char T.2;                               char T.2;
    char * s;                               char * s;

    T.1 = "string";                     |   return (int)100;
    s = (char *)T.1;                    <
    *s = 100;                           <
    T.2 = *s;                           <
    return (int)T.2;                    <
  }                                      }

  I can live with this loss.  I cannot say for sure if this is
  going to be a real problem because I still haven't implemented
  the change.  If it turns out to be a huge loss, then we should
  either reconsider or think of alternatives.

- Since INDIRECT_REF are unary expressions, they should probably
  be better handled by SSAPRE.  Daniel, do you think this is
  feasible?  The whole idea of SSAPRE is building an SSA web for
  expressions, so it seems to me that this would be a perfect fit
  for it.

- The type-based alias analysis pass needs to be modified to stop
  relying on INDIRECT_REF variables.  This should not be too
  hard.  We need to change it to keep track of indirect loads and
  stores.  The partial change I have is implementing that.


Thoughts?


Diego.

Re: [tree-ssa] RFC: Dropping INDIRECT_REF variables

[Timothy J. Wood]

On Wednesday, May 14, 2003, at 08:09  AM, Diego Novillo wrote:
> - We disable the ability to treat non-aliased pointer
>   dereferences as if they were variables.  We would lose the
>   ability to do some optimizations like:

   Please forgive me if I'm way off base here, but one example on PPC 
that your code snippet reminded me of was int->float conversion.  On 
PPC this happens by building storing a pair of 32-bit constructed ints 
on the stack, loading them as a double and then doing some more 
contortions with this.

   The current problem is that if you have float conversion in a loop:

void convert(int *input, float *output, unsigned int count)
{
     while (count--)
         *output++ = *input++;
}

   both words of the double on the stack are written on each loop even 
though the one 32-bit portion is always the same.  This store should be 
hoisted outside the loop (in the degenerate case above this can by a 
pretty big performance win).  I don't have a 3.3 compiler right now, 
but on Mac OS X 10.2 (3.1-based):

cc -mdynamic-no-pic -S -O2 foo.c

.data
.literal8
         .align 3
LC0:
         .long   1127219200
         .long   -2147483648
.text
         .align 2
         .globl _convert
_convert:
         cmpwi cr0,r5,0
         addi r5,r5,-1
         beqlr- cr0
         addi r5,r5,1
         lis r11,ha16(LC0)
         mtctr r5
         lfd f13,lo16(LC0)(r11)
         lis r9,0x4330
L8:
         lwz r0,0(r3)
         addi r3,r3,4
         stw r9,-16(r1)  <--- should be outside the loop
         xoris r0,r0,0x8000
         stw r0,-12(r1)
         lfd f0,-16(r1)
         fsub f0,f0,f13
         frsp f0,f0
         stfs f0,0(r4)
         addi r4,r4,4
         bdnz L8
         blr

   I'm not sure this applies to what you were talking about, but I 
thought I'd bring it up since it looks similar and we could benefit 
from having this optimization.

-tim

Re: [tree-ssa] RFC: Dropping INDIRECT_REF variables

[Daniel Berlin]

On Wednesday, May 14, 2003, at 11:09  AM, Diego Novillo wrote:

> Supporting INDIRECT_REF variables in the base framework is
> getting to be increasingly annoying.  We have to handle several
> corner cases and need additional support code that increases the
> complexity of the implementation without giving us many benefits.
>
> - To properly deal with INDIRECT_REF variables, we need to use
>   shared tree nodes.  All the optimization and analysis passes
>   rely on pointer equality for testing if two variables are the
>   same.
>
> - Sharing expressions is always a problem, particularly with
>   passes like mudflap that need to instrument them.  Also, to
>   properly support INDIRECT_REF variables we now need to rewrite
>   both the INDIRECT_REF node (*P) and its base pointer (P).  This
>   means that we have to selectively unshare INDIRECT_REF nodes.
>   Not particularly hard, but brittle and annoying to maintain.
>
> - More often than not, INDIRECT_REF variables represent aliased
>   loads and stores.  This means that we don't really do anything
>   interesting with them in the optimizers.  We just use them for
>   liveness and alias analysis.
>
> - The SSA->normal pass may also need to handle INDIRECT_REF
>   variables with care.  Since an INDIRECT_REF variable has two
>   SSA versions in it, overlapping live ranges of the base pointer
>   or the INDIRECT_REF node may need extra supporting code (this
>   is just a vague concern, Andrew?).
>
>
> What I'm planning to do is stop renaming INDIRECT_REF nodes as if
> they were variables.  This means that INDIRECT_REF nodes need not
> be shared anymore and are treated as any other expression.  I'm
> trying to think about the ramifications of this change.  So far:
>
> - A whole chunk of code in the SSA/DFA passes would disappear.
>   This can only be good.
>
> - We disable the ability to treat non-aliased pointer
>   dereferences as if they were variables.  We would lose the
>   ability to do some optimizations like:
>
>   foo ()                                 foo ()
>   {                                      {
>     char[7] * T.1;                          char[7] * T.1;
>     char T.2;                               char T.2;
>     char * s;                               char * s;
>
>     T.1 = "string";                     |   return (int)100;
>     s = (char *)T.1;                    <
>     *s = 100;                           <
>     T.2 = *s;                           <
>     return (int)T.2;                    <
>   }                                      }
>
>   I can live with this loss.  I cannot say for sure if this is
>   going to be a real problem because I still haven't implemented
>   the change.  If it turns out to be a huge loss, then we should
>   either reconsider or think of alternatives.
>
> - Since INDIRECT_REF are unary expressions, they should probably
>   be better handled by SSAPRE.  Daniel, do you think this is
>   feasible?  The whole idea of SSAPRE is building an SSA web for
>   expressions, so it seems to me that this would be a perfect fit
>   for it.

As long as the alias/pta info remains, i can do it there.
I just need to be able to tell aliasing relationships accurately so 
that i can determine when a store happens that may affect our load.
We also end up transforming the loads into temporaries through register 
promotion, so further passes only need to optimize the variables we've 
temp stored them in.

>
> - The type-based alias analysis pass needs to be modified to stop
>   relying on INDIRECT_REF variables.  This should not be too
>   hard.  We need to change it to keep track of indirect loads and
>   stores.  The partial change I have is implementing that.
>
>
> Thoughts?
>

We can always revisit this decision later if necessary, right?
It's not like we are making it impossible somehow for it to be 
implemented later, it's just something we aren't going to deal with at 
the moment.

>
> Diego.

Re: [tree-ssa] RFC: Dropping INDIRECT_REF variables

[Diego Novillo]

On Wed, 2003-05-14 at 11:31, Timothy J. Wood wrote:
> On Wednesday, May 14, 2003, at 08:09  AM, Diego Novillo wrote:
> > - We disable the ability to treat non-aliased pointer
> >   dereferences as if they were variables.  We would lose the
> >   ability to do some optimizations like:
> 
>    Please forgive me if I'm way off base here, but one example on PPC 
> that your code snippet reminded me of was int->float conversion.
>
Actually, it's my fault.  I wasn't clear enough.  My proposal is to drop
support on the base framework, only.  INDIRECT_REFs would need to be
supported by other passes like SSAPRE.


> void convert(int *input, float *output, unsigned int count)
> {
>      while (count--)
>          *output++ = *input++;
> }
> 
>    both words of the double on the stack are written on each loop even 
> though the one 32-bit portion is always the same.  This store should be 
> hoisted outside the loop (in the degenerate case above this can by a 
> pretty big performance win).  I don't have a 3.3 compiler right now, 
> but on Mac OS X 10.2 (3.1-based):
> 
Well, we never get to this level of detail on trees.  The code you quote
above is not optimizable at the tree level:

foo (input, output, count)
{
  int T.1;
  float T.2;

  while (1)
    {
      count = count - 1;
      if (count == 0ffffffff)
        {
          goto <ULe70>;
        };
      T.1 = *input;
      T.2 = (float)T.1;
      input = input + 4B;
      *output = T.2;
      output = output + 4B
    };
  <ULe70>:;
}

There's nothing in that loop that could be hoisted out.  If we knew the
value of 'count' we could probably unroll the loop, but that's about it.

It's important to note that there are many details that are not exposed
in the tree IL.  Essentially, if you have a target specific optimization
problem, you won't be able to fix it at the tree level.  The
optimizations we do on the trees help indirectly, of course.


Diego.

Re: [tree-ssa] RFC: Dropping INDIRECT_REF variables

[Diego Novillo]

On Wed, 2003-05-14 at 12:01, Daniel Berlin wrote:

> As long as the alias/pta info remains, i can do it there.
> I just need to be able to tell aliasing relationships accurately so 
> that i can determine when a store happens that may affect our load.
> We also end up transforming the loads into temporaries through register 
> promotion, so further passes only need to optimize the variables we've 
> temp stored them in.
> 
OK.  Once I have a working patch I will send it your way so that you can
test whether it's still usable for you.


> We can always revisit this decision later if necessary, right?
> It's not like we are making it impossible somehow for it to be 
> implemented later, it's just something we aren't going to deal with at 
> the moment.
> 
Absolutely.  I was thinking that we could even use the expression-SSA
engine in SSAPRE as a way of building the SSA web for INDIRECT_REF
nodes.  That would give passes that want to deal with pointers a
convenient way of building an SSA web just for them.  I was even
thinking of using it for arrays and structures, but that's just a vague
notion I started playing with today.  I'm still not sure if it's even
feasible.


Diego.

Re: [tree-ssa] RFC: Dropping INDIRECT_REF variables

[Andrew MacLeod]

On Wed, 2003-05-14 at 11:09, Diego Novillo wrote:

> - The SSA->normal pass may also need to handle INDIRECT_REF
>   variables with care.  Since an INDIRECT_REF variable has two
>   SSA versions in it, overlapping live ranges of the base pointer
>   or the INDIRECT_REF node may need extra supporting code (this
>   is just a vague concern, Andrew?).
> 

The SSA->Normal pass is in the process of ignoring INDIRECT_REF
variables anyway, but it does have to handle them when they occur as
real operands..

  ie
    T.14 = (*p_5)_8

needs to be recognized by the SSA->normal translator, and converted to
    T.14 = *p_5

So it requires a bunch of special casing during building, analyzing/ and
translation out.  Having them go away or at least never be a part of a
real operands is the way to go.


> - We disable the ability to treat non-aliased pointer
>   dereferences as if they were variables.  We would lose the
>   ability to do some optimizations like:
> 
>   foo ()                                 foo ()
>   {                                      {
>     char[7] * T.1;                          char[7] * T.1;
>     char T.2;                               char T.2;
>     char * s;                               char * s;
> 
>     T.1 = "string";                     |   return (int)100;
>     s = (char *)T.1;                    <
>     *s = 100;                           <
>     T.2 = *s;                           <
>     return (int)T.2;                    <
>   }                                      }
> 
>   I can live with this loss.  I cannot say for sure if this is
>   going to be a real problem because I still haven't implemented
>   the change.  If it turns out to be a huge loss, then we should
>   either reconsider or think of alternatives.
> 

All you were doing were taking unaliased dereferences, and replacing
them with a variable. It was basically a simple expression replacement
based on a single simple case... a dereference of a memory location that
wasn't alasied with anything. 

I find it hard to beleive that this isn't going to be caught by some
other optimization that handles expressions and looks at loads and
stores.

Andrew

Re: [tree-ssa] RFC: Dropping INDIRECT_REF variables

[Daniel Berlin]

>>
>
> All you were doing were taking unaliased dereferences, and replacing
> them with a variable. It was basically a simple expression replacement
> based on a single simple case... a dereference of a memory location 
> that
> wasn't alasied with anything.
>
> I find it hard to beleive that this isn't going to be caught by some
> other optimization that handles expressions and looks at loads and
> stores.
>

This is the job of SSAPRE load PRE.
As I said, as long as i have the PTA/alias info, i can do the right 
thing.

> Andrew
>

Re: [tree-ssa] RFC: Dropping INDIRECT_REF variables

[Dale Johannesen]

On Wednesday, May 14, 2003, at 08:31  AM, Timothy J. Wood wrote:
> On Wednesday, May 14, 2003, at 08:09  AM, Diego Novillo wrote:
>> - We disable the ability to treat non-aliased pointer
>>   dereferences as if they were variables.  We would lose the
>>   ability to do some optimizations like:
>
>   Please forgive me if I'm way off base here, but one example on PPC 
> that your code snippet reminded me of was int->float conversion.  On 
> PPC this happens by building storing a pair of 32-bit constructed ints 
> on the stack, loading them as a double and then doing some more 
> contortions with this.
>
>   The current problem is that if you have float conversion in a loop:
>
> void convert(int *input, float *output, unsigned int count)
> {
>     while (count--)
>         *output++ = *input++;
> }
>
>   both words of the double on the stack are written on each loop even 
> though the one 32-bit portion is always the same.  This store should 
> be hoisted outside the loop (in the degenerate case above this can by 
> a pretty big performance win).  I don't have a 3.3 compiler right now, 
> but on Mac OS X 10.2 (3.1-based):

3.3 does the same thing.  I have tried to fix it and given up, as have 
some
other people.

Re: [tree-ssa] RFC: Dropping INDIRECT_REF variables

[David Edelsohn]

>>>>> Dale Johannesen writes:

Dale> 3.3 does the same thing.  I have tried to fix it and given up, as have 
Dale> some other people.

	Yes, it is a very long-standing problem that unfortunately is
going to take some major GCC enhancements to fix.

David

Re: [tree-ssa] RFC: Dropping INDIRECT_REF variables

[tm_gccmail]

On Wed, 14 May 2003, Dale Johannesen wrote:

> On Wednesday, May 14, 2003, at 08:31  AM, Timothy J. Wood wrote:
> > On Wednesday, May 14, 2003, at 08:09  AM, Diego Novillo wrote:
> >> - We disable the ability to treat non-aliased pointer
> >>   dereferences as if they were variables.  We would lose the
> >>   ability to do some optimizations like:
> >
> >   Please forgive me if I'm way off base here, but one example on PPC 
> > that your code snippet reminded me of was int->float conversion.  On 
> > PPC this happens by building storing a pair of 32-bit constructed ints 
> > on the stack, loading them as a double and then doing some more 
> > contortions with this.
> >
> >   The current problem is that if you have float conversion in a loop:
> >
> > void convert(int *input, float *output, unsigned int count)
> > {
> >     while (count--)
> >         *output++ = *input++;
> > }
> >
> >   both words of the double on the stack are written on each loop even 
> > though the one 32-bit portion is always the same.  This store should 
> > be hoisted outside the loop (in the degenerate case above this can by 
> > a pretty big performance win).  I don't have a 3.3 compiler right now, 
> > but on Mac OS X 10.2 (3.1-based):
> 
> 3.3 does the same thing.  I have tried to fix it and given up, as have 
> some
> other people.

This is a bit tangential, but would stack-based pseudos help in this
instance? e.g. a pseudo which represents a stack location?
This sounds more friendly to the loop optimizer, as it doesn't need to
differentiate between registers and stack locations.

Toshi