Some random thoughts regarding the SSA paper

Some random thoughts regarding the SSA paper

[Christopher Li]

I have spend some time reading the paper

http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf

"Simple and Efficient SSA Construction". Which is luc's SSA
conversion is based on:

Here is some random thoughts about the paper I might just
share with you guys. If I make a mistake some where along
the line, I am very glad if some one can point it out to me.

- I think the main point of the paper doing SSA without
  the CFG is not particular useful to us. We need to generate
  CFG *anyway*.

- The "Simple and Efficient" part has obvious limitation on
  reducible graph. Once go over the fence of irreducible graph,
   the solution is no longer simple nor efficient. For irreducible
   graph it do need the CFG. That means the CFG is actuall
   unavoidable consider source can have irreducible graph.

-  It is actually not fair to compare the fast and simple part
   with Cytron et al because
   - Cytron etc al can handle irreducible graph without extra
     complication.

   - For reducible graph, Cytron el has fast way to do it as well.
     "A Simple, Fast Dominance Algorithm" can find dominator for
      reducible graph in O(N). Once having the dominator tree,
      finding DF and inserting phi node is very straight forward.

   - For handling irreducible graph, the "Simple" paper need to
     do extra steps to clean up unneeded phi nodes.
     which runs on O(P + B ·(B + E)· V*V), so basiclly O(B*B*V*V)
     I think that is worse than Cytron's method.

     Because sparse need to handle irreducible graph. The worse
     case behavior need to be considered.

      BTW that is I think why the paper don't discuss handle of
      "goto" statement. "goto" can lead to irreducible graph.

- We might have a way to tell if function contain goto before
   linearized the function.

- Cytron might still be worthwhile to implement due to the better
   worse case complexity.


Chris

Re: Some random thoughts regarding the SSA paper

[Luc Van Oostenryck]

On Wed, Aug 16, 2017 at 02:33:30AM -0400, Christopher Li wrote:
> I have spend some time reading the paper
> 
> http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf
> 
> "Simple and Efficient SSA Construction". Which is luc's SSA
> conversion is based on:
> 
> Here is some random thoughts about the paper I might just
> share with you guys. If I make a mistake some where along
> the line, I am very glad if some one can point it out to me.
> 
> - I think the main point of the paper doing SSA without
>   the CFG is not particular useful to us. We need to generate
>   CFG *anyway*.

I think you mis-understnd the point.
Of course the CFG is needed at the end. The point of the article
is that with their method you don't have to *first* build
a CFG and a non-SSA representation and *then directly convert*
this into the SSA form (and maybe having to throw away most of
what was previously build) because their method construct
the CFG and the SSA form at once, directly from the AST.

In short it does the SSA construction directly during
the linearization. OTOH, with the current method (and the
traditional ones) we have first to linearize and do all
access to local vars as memory access and what all of this
is done, we need another pass which will create the SSA form
and destroy most load & write to these local vars.

-- Luc

Re: Some random thoughts regarding the SSA paper

[Dibyendu Majumdar]

Hi Chris,

On 16 August 2017 at 07:33, Christopher Li <sparse@chrisli.org> wrote:
> I have spend some time reading the paper
>
> http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf
>
> "Simple and Efficient SSA Construction". Which is luc's SSA
> conversion is based on:
>
> Here is some random thoughts about the paper I might just
> share with you guys. If I make a mistake some where along
> the line, I am very glad if some one can point it out to me.
>
> - I think the main point of the paper doing SSA without
>   the CFG is not particular useful to us. We need to generate
>   CFG *anyway*.
>
> - The "Simple and Efficient" part has obvious limitation on
>   reducible graph. Once go over the fence of irreducible graph,
>    the solution is no longer simple nor efficient. For irreducible
>    graph it do need the CFG. That means the CFG is actuall
>    unavoidable consider source can have irreducible graph.
>

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
my view, if the solution works now with all known inputs then it is
good enough.

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

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.

Regards
Dibyendu

Re: Some random thoughts regarding the SSA paper

[Christopher Li]

On Wed, Aug 16, 2017 at 3:15 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Wed, Aug 16, 2017 at 02:33:30AM -0400, Christopher Li wrote:
>> I have spend some time reading the paper
>>
>> http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf
>>
>> "Simple and Efficient SSA Construction". Which is luc's SSA
>> conversion is based on:
>>
>> Here is some random thoughts about the paper I might just
>> share with you guys. If I make a mistake some where along
>> the line, I am very glad if some one can point it out to me.
>>
>> - I think the main point of the paper doing SSA without
>>   the CFG is not particular useful to us. We need to generate
>>   CFG *anyway*.
>
> I think you mis-understnd the point.
> Of course the CFG is needed at the end. The point of the article
> is that with their method you don't have to *first* build
> a CFG and a non-SSA representation and *then directly convert*
> this into the SSA form (and maybe having to throw away most of
> what was previously build) because their method construct
> the CFG and the SSA form at once, directly from the AST.

For our purpose, yes.
The paper did make some claim is towards making SSA
on the AST level without going to CFG, don't need dominator
analyze etc.. Claim that as an advantage. I don't want to go
there. It is not your patch are about.

>
> In short it does the SSA construction directly during
> the linearization. OTOH, with the current method (and the
> traditional ones) we have first to linearize and do all
> access to local vars as memory access and what all of this
> is done, we need another pass which will create the SSA form
> and destroy most load & write to these local vars.

I still think that directly build from AST without the CFG is
overrated  in this paper.

First of all, you can't actually avoid CFG if you are considering
"goto". The whole reason of having "goto" as the ugly case is
exactly due the the paper try to avoid CFG. My impression is
that, the solution of handling of the "goto" is actually very ad-hoc.

Second, local vars as memory access is actually done in the
AST level. Source code "a = b;" at AST level before linearization
it is already become "* (&a) = * (&b);", due to C language syntax.
So you are actually not saving the memory access stage.
You can not because only after pointer alias analyse you can remove
the pointer. You can't do effective do pointer alias analyse due
to you don't have CFG. (consider the "goto" case).

You just convert the memory access into the pseudo slightly
earlier. But considering complexity to plug the "goto" hole,
and the cleanup stage after it. The complexity is much higher
(both in code and execution time) than the paper suggested,
which is the simple reducible graph case .

To sum up. I think my point is still valid.
- The CFG stage is not actually avoidable (considering "goto").
- There is hidden complexity considering "goto" and irreducible graph.
   BTW, Does your branch handle "goto" and irreducible graph yet?
   I only take a brief scroll of it, I can't really tell.


Chris

Re: Some random thoughts regarding the SSA paper

[Christopher Li]

On Wed, Aug 16, 2017 at 5:55 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi Chris,
>
> 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.

> my view, if the solution works now with all known inputs then it is
> good enough.

Know input include "goto", period.

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


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

Chris

Re: Some random thoughts regarding the SSA paper

[Dibyendu Majumdar]

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

Re: Some random thoughts regarding the SSA paper

[Luc Van Oostenryck]

On Wed, Aug 16, 2017 at 2:09 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> 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.

You mix two things together, Chris.

> Exactly. I am totally agree with you. My worries are the hidden complexity
> dealing with gotos in that paper.

The code is there and running.

-- Luc

Re: Some random thoughts regarding the SSA paper

[Christopher Li]

On Wed, Aug 16, 2017 at 8:33 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Wed, Aug 16, 2017 at 2:09 PM, Christopher Li <sparse@chrisli.org> wrote:
>>
>> 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.
>
> You mix two things together, Chris.
>
>> Exactly. I am totally agree with you. My worries are the hidden complexity
>> dealing with gotos in that paper.
>
> The code is there and running.

Ok, thanks for the clarification.

Chris

Re: Some random thoughts regarding the SSA paper

[Christopher Li]

On Wed, Aug 16, 2017 at 8:24 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> 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?

It do provide a solution. and the price is high. The complexity is
O(B*B*V*V).  Go look at page 15 of the paper.

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

I haven't, as I said I try to finish reading the paper before looking that
the implementation. If  Luc is the paper suggestion to fix up the irreducible
case. , then we are down the road for O(B*B*V*V) complexity.

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

My way of seeing it, the complexity is introduced when you have input
source contain irreducible grahy. This paper doe not have good way to
deal with it. It can solve it, but that is O(B*B*V*V) complexity.

In other words, we can some input source that cause the method describe
in this paper quadruple to the size of the input.

Chris

Re: Some random thoughts regarding the SSA paper

[Dibyendu Majumdar]

Hi Chris,

On 16 August 2017 at 13:42, Christopher Li <sparse@chrisli.org> wrote:
> On Wed, Aug 16, 2017 at 8:24 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>
>> 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?
>
> It do provide a solution. and the price is high. The complexity is
> O(B*B*V*V).  Go look at page 15 of the paper.
>

That is only if you want a minimal SSA right? Do you need one? Again I
suggest you try out Luc's implementation which appears to work fine -
and it doesn't do this extra pass I believe.

Regards
Dibyendu

Re: Some random thoughts regarding the SSA paper

[Christopher Li]

On Wed, Aug 16, 2017 at 8:47 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> That is only if you want a minimal SSA right? Do you need one? Again I
> suggest you try out Luc's implementation which appears to work fine -
> and it doesn't do this extra pass I believe.

If it does not do this extra pass then it will leave redundant phi node around.
Base on my understanding of the paper.

Yes, I would like to have minimal phi node SSA. Other than the code size,
the extra redundant phi node will have impact on later stage of the
optimization.
It make the define and usage chain less clear, having the middle man phi node
might or might not be needed.

Chris