From mboxrd@z Thu Jan 1 00:00:00 1970 From: Daniel Berlin To: Diego Novillo Cc: law@redhat.com, gcc@gcc.gnu.org Subject: Re: Higher level RTL issues Date: Tue, 09 Oct 2001 21:27:00 -0000 Message-id: <1B5A94CB-BD37-11D5-867A-0030657B5340@cgsoftware.com> References: <20011009235348.A2183@tornado.cygnus.com> X-SW-Source: 2001-10/msg00633.html 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.