This is the mail archive of the gcc@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]

Re: Higher level RTL issues



On Tuesday, October 9, 2001, at 11:53  PM, Diego Novillo wrote:

> On Tue, 09 Oct 2001, Jeff Law wrote:
>
>> I don't think there's any significant disagreement that a higher level
>> IL would be useful.  What is a subject of debate is whether we have
>> a lower tree form, higher RTL form or some other form.  I think if we
>>
> Or both.  The tree form is still too high-level for some
> transformations.  We can still lower the tree representation
> without actually creating a new IL.  This lowering would preserve
> full symbolic and array information while simplifying the
> expression trees to remove most of the language semantics
> (side-effects, sequence points, etc).
>
> I'm thinking of trees that ressemble three-address ILs.  They
> would look just like trees to the tree-to-RTL pass and more
> importantly they would provide a high-level IL that is more
> language-independent than the current trees.
This is a much better idea than a high level rtl, IMHO, having had to 
implement it for the vectorization stuff i did.

>
>> 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 
def/use.
They are provably equivalent.

The perceived difference could be caused by the fact that Wolfe's paper 
covers Factored UD chains, while traditional SSA is only renaming defs, 
giving you *explicit* def-use chains.

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.

There is a picture of what factored du chains would look like in wolfe's 
paper. It's just FUD with the pointers reversed (obviously).

Factored chains tend to use recursive algorithms (walking the chains for 
the variables), rather than iterative ones (walking the explicitly 
renamed variables), but you could do it either way.


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