Re: [RFC] sparse SSA construction

[Luc Van Oostenryck <luc.vanoostenryck@gmail.com>]

On Tue, Aug 15, 2017 at 01:43:15PM -0700, Linus Torvalds wrote:
> On Tue, Aug 15, 2017 at 1:14 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > For information, the current SSA construction is very broken,
> > both in simplify_one_symbol() (the main SSA construction)
> > and simplify_loads() (which also creates phi-nodes). They both
> > are 'load-driven' which is OK but they both put the phi-nodes
> > where the load is while phi-nodes need to placed where branches
> > meet. The loads are often placed in a BB following where the
> > join-point. Often this *seems* to be OK but in fact is very wrong
> > and create all sort of problems a bit everywhere
> 
> I do think you're too hung up about the placement of the phi nodes.
> 
> It may be an issue for simple models that just walk the linearized
> code directly and try to turn it into code. But the original intent of
> the existing phi node code was to just be as sources of the pseudo's -
> the location should be largely immaterial.

I somehow disagree here.
A:	B:	C:
Va = a;	Vb = b;	Vc = c;
  |	  |	  |
   \      |      / 
    \     |     / 
     \    |    / 
      \   |   / 
       \  |  / 
	M:
	  |
	  |
	  |
	  |
	N:
	  V = PHI(Va, Vb, Vc)

Now what must happen if B: has to be removed?

A:		C:
Va = a;		Vc = c;
  |	  	  |
   \             / 
    \           / 
     \         / 
      \       / 
       \     / 
	M:
	  |
	  |
	  |
	  |
	N:
	  V = PHI(Va, VOID, Vc)

where VOID represent here a non-present element. It's still 'correct'
You have to interpret the void as 'nothing here anymore'

One of the funnies begin if we now have to add a branch D to M

A:	C:	D:
Va = a;	Vc = c;	Vd = d;
  |	  |	  |
   \      |      / 
    \     |     / 
     \    |    / 
      \   |   / 
       \  |  / 
	M:
	  V' = PHI(Va, Vc, Vd)
	  |
	  |
	  |
	  |
	  |
	N:
	  V = PHI(Va, VOID, Vc)

What for V if we came from branch D?

You can also see things like:


     Vd   Vb   Ve 
       \  |  / 
	O:
     Va   |   Vc 
       \  |  / 
	M:
	  |
	  |
	  |
	N:
	  V = PHI(Va, Vc, Vd, Vb, Ve)

In others words,s a phi-nodes with much more sources/args than the first
branching parent has.

We also have (after BB packing)
     Va   Vb   Vc 
       \  |  / 
	M:
	  V = PHI(Va, Vb, Vc)
          .....
	  .....
	  F' = PHI(Fa, Fc)

THus a phi-node in the middle of a BB (it was at top first but
two BB have been joined).


At best, it's hard to see any kind of plausibly correct interpretation,
often you can't.
Thing becomes really messy when a new branch is inserted somewhere
in the middle of the chain.

But I also agree that there is two problmes here:
- having a correct SSA form (maybe not the same as what can always
  be found in the literature but we need one on which we can reason)
- once the SSA construction is done, we now have ti maintain it
  each time we make a change to the CFG. I doubt we do this
  correctly.

 
> IOW, you could think of the phi nodes as being "outside" the
> instruction flow entirely, and just being the definition of the pseudo
> they define.

Right, they are not really part of the normal instruction flow.
I think it's even best to *not* see them as part of the instruction.
They are more akin to arguments receive by a function at its start.
The phi-node are then: heer are the values we for this BB if
we come from this or this path.
They also must have the multi-assignement semantics (but in sparse,
we don't care because there is always  this layer of phi-source)
> They have to be placed somewhere, but the "somewhere" is
> somewhat arbitrary.

I disagree here.
IMO, the somwhere has to be at the top of the BB where others
BBs meet and there each phi-node has to have as much sources
as there the BB has parents.
This is the only sane semantic.

> That said, I like your new ssa construction -independently- of that
> issue - the old SSA constructor really was very ad-hoc. Look through
> the git history if you don't believe me ;)

Thank you. I would have liked that the ideas where mine though!
(in fact, when I foud the article, I had some related ideas in head
triggered by one of your replies to me wheer you said 'you can't
directly translate local var inti pseudo).


Best regards,
-- Luc