Re: Higher level RTL issues

[Diego Novillo <dnovillo at redhat dot com>]

On Wed, 10 Oct 2001, Daniel Berlin wrote:

> 
> On Tuesday, October 9, 2001, at 11:53  PM, Diego Novillo wrote:
> 
> > On Tue, 09 Oct 2001, Jeff Law wrote:
> >
> >> That model works fine for a class of optimization problems, but breaks 
> >> down
> >> with any optimization which potentially has two SSA names for the same
> >> variable live at the same point in the program.  GVN and dominator 
> >> based
> >> value numbering can create situations where we have two SSA names live 
> >> at
> >> the same time.
> >>
> > Sorry, you missed me here.  Would you have an example?  I agree
> > that we might find the FUD chains representation restricted for
> > some optimizations, but I'm not sure I follow this particular
> > case.  We can at least support most/all interesting loop
> > transformations with FUD chains.
> 
> There can exist no optimization that can be performed in a renamed SSA 
> form (with both *uses* and *defs* renamed to be unique) that can't be 
> performed on a factored representation where names point to the reaching 
                                               ^^^^^
					       references
> def/use.
> They are provably equivalent.
> 
I think Jeff was referring to ease of use, rather than actual
limitation.  The FUD chains camp usually goes on and on about the
advantages of not blowing up your symbol table to hell and back,
and also they dislike the idea of the compiler actually
re-writing the code to do analysis.  The renaming camp, argues
that you have to jump through hoops to maintain the two views of
the program. Both POVs seem valid to me.

I never really decided which one I like best.  I do find the FUD
chains less intrusive, but I'm not sure they are so easy to deal
with once you start doing incremental updates of your SSA form.
I never dealt with incremental updates, I just re-ran SSA all
over again.  Then again, I never had to worry about compile-time
performance :)

> You can just as easily do factored DU chains, and have an SSA
> form with explicit use-def chains through renaming. The main
> advantage to factored chains is that it doesn't require
> renaming. This matters a heck of a lot more for uses than defs,
> since there are a lot more uses than defs.
> 
We already have def-use chains and pretty soon we will also have
def-def chains for non-killing definitions like array assignments
and pointer dereferences.


Diego.