Re: Some random thoughts regarding the SSA paper

[Dibyendu Majumdar <mobile@majumdar.org.uk>]

Hi Chris,

On 16 August 2017 at 13:09, Christopher Li <sparse@chrisli.org> wrote:
> On Wed, Aug 16, 2017 at 5:55 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>> I would argue that the simplest possible solution is what we should
>> start with. The solution implemented based on this paper appears to be
>> simple and elegant - and if this works correctly then why go for more
>> complicated solutions? Theoretical scenarios are not very useful - in
>
> Because the paper "simple and elegant" only cover the reducible
> graph case. When you considering the irreducible graph source file
> input, say having "goto", all the sudden it is not simple and elegant
> any more. It is more like complex and ad-hoc.
>

The paper says that the algorithm creates correct SSA for all
programs. Specifically quoting:

<quote>
prove that the SSA construction algorithm constructs pruned SSA form
for all programs and minimal SSA form for programs with reducible
control flow
<endquote>

Secondly even for irreducible control flow, it provides an algorithm
for creating minimal SSA in section 3.2, right?

>> my view, if the solution works now with all known inputs then it is
>> good enough.
>
> Know input include "goto", period.
>

Luc's implementation seems to work fine with gotos? Have you tested
Luc's implementation? I think it is better to try out the solution and
see if there is a problem.

>>>
>>> - Cytron might still be worthwhile to implement due to the better
>>>    worse case complexity.
>>>
>>>
>>
>> Certainly you should prototype this - even if just to compare. But I
>> would suggest - lets merge the solution we have now. Additional
>> solutions are always good to have.
>
> Yes, I am doing the prototype as the side project. I start with building
> the dominator tree as I mention in the list earlier. Another way to
> evaluate the complexity of the code, just go take a look at the Clang,
> how it promote the memory access into SSA pesudo. That is the
> critical piece we are talking about here. It is actually not that complex
> at all.
>
> To fully evaluate the complexity suggest by this paper. I want to see
> the full implementations with "gotos".
>

In my tests Luc's implementation works fine with gotos. I have not
tested computed gotos, however. Yet the solution is simple and
elegant.

>
>> The great thing about Sparse I find is that it is smaller and simpler
>> than gcc or clang - and I would urge that this should be maintained.
>
> Exactly. I am totally agree with you. My worries are the hidden complexity
> dealing with gotos in that paper.
>

I am wondering if the complexity is only because Luc's implementation
creates SSA on the fly rather than as a second phase. I posted another
question on that topic.

Regards
Dibyendu