Re: Higher level RTL issues

[Daniel Berlin <dan@cgsoftware.com>]

On Wednesday, October 10, 2001, at 12:48  AM, Diego Novillo wrote:

> 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.
I'm not so sure, given what he said about value numbering, so i thought 
i'd just point it out. It certainly would not require a rewrite of the 
tree-ssa stuff.
And nascent has examples of most of the algorithms he wants to 
implement, implemented on factored representations, and they are 
comparable in implementation ease to the traditional versions.

> 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.
Yup.
>  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.
>
Same here.
> 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.
It's just as easy to relink a bunch of pointers, as  it is to rename a 
bunch of variables.
At least, it should be.
It's a data structures problem more than anything else.
> 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 :)
>
:)
In reality, the real problem with the two camps is that the "best" 
representation depends on external factors.
For ease of algorithms, speed, and memory usage, fud is probably better 
for backwards problems, traditional for forwards problems.
However, using both is not really an option, because who the heck wants 
two ssa representations to maintain?  Even if you were wacky, and 
decided you were going to fake one from the other, in your nice C++ 
compiler than only walked the IR using iterators, you'd still have a 
mess (probably even more so).

It's around this point in trying to weigh each that i usually give up on 
SSA and move on to looking at sparse evaluation graphs.

Trying to argue which of factored vs explicit SSA forms is best is 
comparable to arguing whether sparse bitmaps are better than dense ones, 
or adjacency lists are better for graphs than an adjacency matrix.
It's rather silly trying to make generalizations about it.
However, for the explicit purpose of SSA on trees, since you deal mostly 
with recursive algorithms already, a factored representation makes more 
sense, since the algorithms used on them tend to be recursive as well.
For an RTL form, where you tend to walk insns iteratively, an explicit 
representation makes more sense, but if we implement optimizations 
needing renamed uses, it might use too much memory.
If for_each_rtx becomes the preferred walking method, than a factored 
representation would be right there too.
Unless the plan was to only do SSA at the new IL level (IE not do 
tree-ssa, not do rtl-ssa), in which case it becomes a case of looking 
into a crystal ball and using tea leaves.

>> 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.
>
Cool.

>
> Diego.