Re: birthpoints in rtl.

[Diego Novillo <dnovillo at google dot com>]

On 3/4/08 2:38 PM, Kenneth Zadeck wrote:
> Steven Bosscher wrote:
> > On Tue, Mar 4, 2008 at 7:58 PM, Diego Novillo <dnovillo@google.com> wrote:
> >   
> > >  Both PHIs and birthpoints are merely factoring devices that let you cut
> > >  down the number of UD links.  They don't need to be part of the IL, much
> > >  like none of the DF objects are part of the RTL IL.
> > >     
> > Maybe they don't need to be, but it may be useful to have them anyway.
> >
> >   
> > >  > What about keeping things up-to-date after applying some
> > >  > transformations? It is already hard to keep UD/DU chains up-to-date
> > >  > now (I don't think any pass successfully does so right now). This
> > >  > should be a lot easier if you fully factorize your UD chains, right?
> > >
> > >  In theory, yes.  Code for keeping these things up-to-date already exists
> > >  in GIMPLE SSA.
> > >     
> > That code is IMHO just awfully ugly. And slow too, last I checked.  I
> > don't know if  this is still true, but update_ssa used to walk a huge
> > part of the dominator tree even for seemingly trivial updates. We
> > should not want that on RTL.  I don't think we should allow
> > transformations on RTL that are too hard to manually update the FUD
> > chains somehow.
> >
> > Gr.
> > Steven
> >   
> There are many differences between fud/birthpoints and real ssa:
>
> 1) In ssa, the operands of the phis and the renaming contain
> information.   The operands are paired with the cfg edges that the
> values come in on.   In fud/birthpoints there is no such pairing or
> renaming.

Yes, there is in FUD chains.  They keep PHI nodes with arguments paired 
to their edges.  Bithpoints do not keep this pairing.


> 2) There are two "kinds" of ssa algorithms that are used in gcc.   There
> are dirty ssa algorithms and "clean" algorithms.  Dirty algorithms do
> not keep ssa up to date as you make the transformations.  Clean ones
> do.

Popular demand.

Passes are encouraged to keep SSA up-to-date themselves, but we also 
have mechanisms for: (1) an API to register SSA updates in a sub-graph, 
(2) a way of introducing new symbols and have them put in SSA form. 
When FUD chains are altered, they can be renamed from scratch by putting 
their symbols in the to-rename list, or they can be kept manually by 
each pass.  The latter is usually faster.


  I have never understood why it was necessary for gcc to use so many
> dirty ssa algorithms.  When NaturalBridge built our compiler, we were
> able to use almost exclusively clean algorithms.   Tricks like loop
> closed ssa form, help, but in general this is a matter of care on the
> algorithmic design side and implementation.   We never had something
> like rebuild ssa at naturalbridge.  
>
> I do not know how much this changes with memory ssa.

Memory SSA *is* FUD chains.

> I assume clean algorithms are harder here, but I have no experience with it.

Not all that harder, though it's generally easier to just mark the 
affected symbols for renaming.  That makes things slower, though.  The 
updater does not have to put the whole program in SSA form again, but it 
 does have to traverse the whole CFG looking for defs/uses of the 
affected symbols.


> I would love to see the rtl back end use phis and renaming rather than
> fuds/birthpoints.  The thing is that for phi functions to really be
> profitable, you need to have a large number passes in a row that are ssa
> clean.  So my plan was to basically start small and just use
> fud/birthpoints to control the space/time of the existing suite of passes. 

Makes sense.


Diego.