This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [tree-ssa] Speedup alias analysis [patch]


On Tue, 2003-06-24 at 10:30, Andrew MacLeod wrote:
> On Tue, 2003-06-24 at 09:43, Diego Novillo wrote:
> > On Tue, 2003-06-24 at 08:12, Andrew MacLeod wrote:
> 
> I have to go to the dentist <drill, whirl, buzz> I'll think about it
> whilst Im out.
> 
> Andrew
> 
Part of the problem with mixing Virtual operands and real operands is
that you dont know which vritual ones are important up front. If you
haven't decided which ones are important before you build the conflict
graph, you wont have interference information on them, and that makes
safe coalescing impossible.

So you could decide that we figure out all the variables we care about
like we do now. Then you look at each one of them, and if they have a
virtual def, you add the RHS of the VDEF to the list of interesting
variables we care about. If that one has a VDEF, you'll need to add it's
RHS... etc.

This will typically result in the entire chain being included as
significant.. ie, all the a_'s are bound to be considered once one of
them is.

Will that end up resulting in everything except GLOBAL_VAR being in the
list of interesting objects? So we'd be back to all virtual and real
operands have to be considered.
 
what we need is a way to break that chain of dependancies.

The only place we see real uses of a_ is where there are actual
references to the original 'a' right?  all the rest of them are pointers
and may-aliases... So maybe we can get away with only adding significant
copies *before* we enter the SSA->Normal phase.  a 'flattening' of the
virtual chain, if you will:

p = &a
*p = 6
<...>
= *p
*p = 10;
  = a;

if'n I remember corerctly, should look something like:

p_1 = &a_2  (I dont want this to be a VUSE...)

#a_3 = VDEF <a_2>
*p_1 = 6
<...>
# VUSE <a_3>
 = *p_1

#a_5 = VDEF <a_3>
*p_4 = 10;
  
  = a_5

correct?

And a_2 will have a DEF of 'a' or however you were planning to do the
live on entry stuff, so it'll be seen as a REAL def which forces a
coalesce with 'a'.

So... there are no real uses of a_3, so I dont think SSA->Normal cares
about it. In order to make the code correct tho, we have to figure out
what a_5 is defined as (it'll be a copy of something)..

So we follow the VDEF chains back..

a_5 is VDEF'd by a_3.  
a_3 is VDEF'd by a_2;
a_2 has a real def,    a_2 = a  or something like that.

So if we insert a copy 
a_5 = a_2
immediately following the VDEF, and everything should work, right? This
seems to be true for anything I can think of at the moment. The virtual
defs and uses exist to prevent code motion, etc of pointers, not to
represent new instances of a_... just that the value of the previous a_
might be different now.   Anwyay, so we'd see:

p_1 = &a_2  

*p_1 = 6
<...>

 = *p_1

*p_4 = 10;
a_5 = a_2
  
  = a_5

There are no more optimizations, so no one is going to move  *p_4 = and
a_5 = apart.

So what happens when we have a PHI:

p = &a
if (x) 
 *p = 10;
else
 *p = 12;

return a

we have:

p_1 = &a_2
if (x_3)
  a = a 
  # a_4 = VDEF <a_2>
  *p_5 = 10
else
  # a_6 = VDEF <a_2>
  *p_7 = 12;

#a_8 = PHI <a_4(2), a_6(4)>
return a_8

Well, a_8 is a real use, so the def of a_8 is considered a PHI of real
operands.
that means a_6 and a_4 have to be made real., so we insert copies via
the same scheme:

p_1 = &a_2
if (x_3)
  *p_5 = 10
  a_4 = a_2
else
  *p_7 = 12;
  a_6 = a_2

#a_8 = PHI <a_4(2), a_6(4)>
return a_8

Then we do SSA->normal and coalescing will do its best to make those
copies go away.  

Clearly these are simple cases... more complex ones could have many many
version of a_ which do not have any real uses, and this would prevent
them from causing the live range tables and conflict graphs, etc from
growing unnecessarily. 

So really, its a quick pass looking for the latest real defintion of a
virtual def, and inserting a copy for that. It should be quite quick.

This could be done by the SSA->normal pass first thing. I'd consider
doing it on the same pass through the IL which determines which
variables are interesting... Im undecided at the moment. 

Even this simple example above could benefit from having this done just
before copy-prop... copy-prop would clean that up pretty nicely. SO
flatten_virtual_ops, copy_prop, SSA->normal would be the exit strategy.

Anyway, Im still pondering this. I understand why you want/need to mix
real and virtual operands.. so this is what occurs to me so far :-)

Andrew



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]