This is the mail archive of the
mailing list for the GCC project.
Re: Higher level RTL issues
- To: Diego Novillo <dnovillo at redhat dot com>
- Subject: Re: Higher level RTL issues
- From: Daniel Berlin <dan at cgsoftware dot com>
- Date: Wed, 10 Oct 2001 00:27:25 -0400
- Cc: law at redhat dot com, gcc at gcc dot gnu dot org
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
>> with any optimization which potentially has two SSA names for the same
>> variable live at the same point in the program. GVN and dominator
>> value numbering can create situations where we have two SSA names live
>> 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
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
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.