Question about Sparse Linear form and pseudos

Question about Sparse Linear form and pseudos

[Dibyendu Majumdar]

Hi,

I am trying to get to grips with the Sparse Linear format and the use
of pseudos.

1) A Sparse document says that pseudos are akin to SSA variables. Is
that a true statement - i.e. do pseudos follow the discipline that
only one assignment to a pseudo is allowed. As pseudos have also
different sub-types - does this statement apply to all pseudo types or
only some sub types?

2) In a recent conversation it was stated that the baseline Linear
output from Sparse is already in SSA form. That implies that all
pseudos used are in SSA form already. However we know that in the
baseline line IR phi nodes may not be present. In LLVM the initial IR
lacks phi nodes too - instead local stack memory and load/store
sequences are used. However LLVM IR is still SSA at this stage. When
it is said that the baseline Linear IR is already SSA is it in this
sense?

Thanks and Regards
Dibyendu

Re: Question about Sparse Linear form and pseudos

[Luc Van Oostenryck]

On Sun, Aug 20, 2017 at 03:54:47PM +0100, Dibyendu Majumdar wrote:
> Hi,
> 
> I am trying to get to grips with the Sparse Linear format and the use
> of pseudos.
> 
> 1) A Sparse document says that pseudos are akin to SSA variables. Is
> that a true statement - i.e. do pseudos follow the discipline that
> only one assignment to a pseudo is allowed. As pseudos have also
> different sub-types - does this statement apply to all pseudo types or
> only some sub types?
> 
> 2) In a recent conversation it was stated that the baseline Linear
> output from Sparse is already in SSA form. That implies that all
> pseudos used are in SSA form already. However we know that in the
> baseline line IR phi nodes may not be present. In LLVM the initial IR
> lacks phi nodes too - instead local stack memory and load/store
> sequences are used. However LLVM IR is still SSA at this stage. When
> it is said that the baseline Linear IR is already SSA is it in this
> sense?

One way to answer this with few words is to look at what's happening
to a variable assigned in different paths in a simple example:

	int f(void);

	int foo(int p)
	{
		int a;

		if (p) {
			a = 0;
			a++;
		} else {
			a = f();
		}

		return a;
	}


Just after linearization:
	foo:
	.L0:
		<entry-point>
		store.32    %arg1 -> 0[p]
		load.32     %r1 <- 0[p]
		cbr         %r1, .L1, .L2

	.L1:
		store.32    $0 -> 0[a]
		load.32     %r2 <- 0[a]
		add.32      %r3 <- %r2, $1
		store.32    %r3 -> 0[a]
		br          .L3

	.L2:
		call.32     %r4 <- f
		store.32    %r4 -> 0[a]
		br          .L3

	.L3:
		load.32     %r5 <- 0[a]
		ret.32      %r5


After conversion to SSA form:
	foo:
	.L0:
		<entry-point>
		cbr         %arg1, .L1, .L2

	.L1:
		add.32      %r3(a) <- $0, $1
		phisrc.32   %phi2(a) <- %r3(a)
		br          .L3

	.L2:
		call.32     %r4 <- f
		phisrc.32   %phi3(a) <- %r4
		br          .L3

	.L3:
		phi.32      %r5 <- %phi2(a), %phi3(a)
		ret.32      %r5


After simplification:
	foo:
	.L0:
		<entry-point>
		cbr         %arg1, .L1, .L2

	.L1:
		phisrc.32   %phi2(a) <- $1
		br          .L3

	.L2:
		call.32     %r4 <- f
		phisrc.32   %phi3(a) <- %r4
		br          .L3

	.L3:
		phi.32      %r5 <- %phi2(a), %phi3(a)
		ret.32      %r5


After going out of SSA (currently not used):
	foo:
	.L0
		<entry-point>
		cbr         %arg1, .L1, .L2

	.L1
		copy.32     %r7 <- $1
		br          .L3

	.L2
		call.32     %r7 <- f
		br          .L3

	.L3
		ret.32      %r7


-- Luc

Re: Question about Sparse Linear form and pseudos

[Christopher Li]

On Sun, Aug 20, 2017 at 10:54 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi,
>
> I am trying to get to grips with the Sparse Linear format and the use
> of pseudos.
>
> 1) A Sparse document says that pseudos are akin to SSA variables. Is
> that a true statement - i.e. do pseudos follow the discipline that
> only one assignment to a pseudo is allowed. As pseudos have also
> different sub-types - does this statement apply to all pseudo types or
> only some sub types?

The pseudo should be SSA, it apply to all types of pseudo.
You can thing of pseudos are similar to LLVM virtual registers.

>
> 2) In a recent conversation it was stated that the baseline Linear
> output from Sparse is already in SSA form. That implies that all
> pseudos used are in SSA form already. However we know that in the
> baseline line IR phi nodes may not be present. In LLVM the initial IR
> lacks phi nodes too - instead local stack memory and load/store
> sequences are used. However LLVM IR is still SSA at this stage. When
> it is said that the baseline Linear IR is already SSA is it in this
> sense?

There are two different things happen here. For the IR that is
generated from linearizing, without the simplification, all the pseudo
is already SSA. It does not need phi node because all the internal
usage of the pseudo already dominated by the pseudo defines.

There is a separate phase, in simplify symbol access, will try to promote
the memory load/store into the SSA pseudo registers. That is where
the phi nodes come it.

LLVM is similar in that regard. The very first batch of the byte code
contain raw load/store on memory variables. You will not see the SSA
on the memory variable. Then there is a pass call "promote memory
to scalar". In this pass it will convert the memory access into SSA
virtual registers.

Chris

Re: Question about Sparse Linear form and pseudos

[Dibyendu Majumdar]

Hi Luc,

On 20 August 2017 at 16:15, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Sun, Aug 20, 2017 at 03:54:47PM +0100, Dibyendu Majumdar wrote:
>> I am trying to get to grips with the Sparse Linear format and the use
>> of pseudos.
>>
>> 1) A Sparse document says that pseudos are akin to SSA variables. Is
>> that a true statement - i.e. do pseudos follow the discipline that
>> only one assignment to a pseudo is allowed. As pseudos have also
>> different sub-types - does this statement apply to all pseudo types or
>> only some sub types?
>>
>> 2) In a recent conversation it was stated that the baseline Linear
>> output from Sparse is already in SSA form. That implies that all
>> pseudos used are in SSA form already. However we know that in the
>> baseline line IR phi nodes may not be present. In LLVM the initial IR
>> lacks phi nodes too - instead local stack memory and load/store
>> sequences are used. However LLVM IR is still SSA at this stage. When
>> it is said that the baseline Linear IR is already SSA is it in this
>> sense?
>
> One way to answer this with few words is to look at what's happening
> to a variable assigned in different paths in a simple example:

Thank you - it is always good to look at examples.

>
>         int f(void);
>
>         int foo(int p)
>         {
>                 int a;
>
>                 if (p) {
>                         a = 0;
>                         a++;
>                 } else {
>                         a = f();
>                 }
>
>                 return a;
>         }
>
>
> Just after linearization:
>         foo:
>         .L0:
>                 <entry-point>
>                 store.32    %arg1 -> 0[p]
>                 load.32     %r1 <- 0[p]
>                 cbr         %r1, .L1, .L2
>
>         .L1:
>                 store.32    $0 -> 0[a]
>                 load.32     %r2 <- 0[a]
>                 add.32      %r3 <- %r2, $1
>                 store.32    %r3 -> 0[a]
>                 br          .L3
>
>         .L2:
>                 call.32     %r4 <- f
>                 store.32    %r4 -> 0[a]
>                 br          .L3
>
>         .L3:
>                 load.32     %r5 <- 0[a]
>                 ret.32      %r5
>

Okay the linear output above seems SSA if we consider how it is shown
in the output. But in the code, access to 0[a] occurs via a pseudo -
of type PSEUDO_SYM. We see multiple stores happening to this pseudo.
So the question is each access generated through a different instance
of a pseudo? I see that in the code if a symbol already has a pseudo
then it is reused. So presumably then PSEUDO_SYMs are not SSA, but
PSEUDO_REGs are?

So then is it more accurate to say that PSEUDO_SYM and possibly
PSEUDO_ARG too - represent memory access, and are just a proxy for
stack allocated memory?

Regards
Dibyendu

Re: Question about Sparse Linear form and pseudos

[Dibyendu Majumdar]

Hi Chris,

On 20 August 2017 at 16:44, Christopher Li <sparse@chrisli.org> wrote:
> On Sun, Aug 20, 2017 at 10:54 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>> I am trying to get to grips with the Sparse Linear format and the use
>> of pseudos.
>>
>> 1) A Sparse document says that pseudos are akin to SSA variables. Is
>> that a true statement - i.e. do pseudos follow the discipline that
>> only one assignment to a pseudo is allowed. As pseudos have also
>> different sub-types - does this statement apply to all pseudo types or
>> only some sub types?
>
> The pseudo should be SSA, it apply to all types of pseudo.
> You can thing of pseudos are similar to LLVM virtual registers.
>

I am wondering if this is true - please see my reply to Luc. In
particular it seems that stores to local variables are represented by
PSEUDO_SYMs and multiple assignments can occur to these. Hence the
PSEUDO_SYMs and probably PSEUDO_ARGs too are not SSA?

>>
>> 2) In a recent conversation it was stated that the baseline Linear
>> output from Sparse is already in SSA form. That implies that all
>> pseudos used are in SSA form already. However we know that in the
>> baseline line IR phi nodes may not be present. In LLVM the initial IR
>> lacks phi nodes too - instead local stack memory and load/store
>> sequences are used. However LLVM IR is still SSA at this stage. When
>> it is said that the baseline Linear IR is already SSA is it in this
>> sense?
>
> There are two different things happen here. For the IR that is
> generated from linearizing, without the simplification, all the pseudo
> is already SSA. It does not need phi node because all the internal
> usage of the pseudo already dominated by the pseudo defines.
>
> There is a separate phase, in simplify symbol access, will try to promote
> the memory load/store into the SSA pseudo registers. That is where
> the phi nodes come it.
>
> LLVM is similar in that regard. The very first batch of the byte code
> contain raw load/store on memory variables. You will not see the SSA
> on the memory variable. Then there is a pass call "promote memory
> to scalar". In this pass it will convert the memory access into SSA
> virtual registers.
>

Agreed - however there is one difference it seems. LLVM explicits
outputs alloca instructions for each memory location - and then does
store/load on these. In Sparse though, a sub type of pseudo -
PSEUDO_SYM is used for the same, right?

Regards
Dibyendu

Re: Question about Sparse Linear form and pseudos

[Linus Torvalds]

On Sun, Aug 20, 2017 at 9:12 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> Okay the linear output above seems SSA if we consider how it is shown
> in the output. But in the code, access to 0[a] occurs via a pseudo -
> of type PSEUDO_SYM. We see multiple stores happening to this pseudo.

No. There are no stores _to_ the pseudo.

The PSEUDO_SYM is an *address*. It's not changed. A "store" does not
assign a value to a pseudo, it writes to *memory*, and the pseudo
gives the address. It's purely a read of the pseudo.

> So then is it more accurate to say that PSEUDO_SYM and possibly
> PSEUDO_ARG too - represent memory access, and are just a proxy for
> stack allocated memory?

No. All pseudos are strictly write-once (after the SSA conversion).
Memory operations don't write to pseudos. They only use pseudos for
addresses.

             Linus

Re: Question about Sparse Linear form and pseudos

[Christopher Li]

On Sun, Aug 20, 2017 at 12:12 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Okay the linear output above seems SSA if we consider how it is shown
> in the output. But in the code, access to 0[a] occurs via a pseudo -
> of type PSEUDO_SYM. We see multiple stores happening to this pseudo.
> So the question is each access generated through a different instance
> of a pseudo? I see that in the code if a symbol already has a pseudo

After promote the memory into pseudo, yes. each store is consider
a new "define" from the SSA point of  view. So it is a new pseudo,
or new number of the variable in some SSA book.

> then it is reused. So presumably then PSEUDO_SYMs are not SSA, but
> PSEUDO_REGs are?

PSEUDO_SYMS are static, you can think them as symbol address.
It never change. There for it does not need phi node to qualify as SSA.


> So then is it more accurate to say that PSEUDO_SYM and possibly
> PSEUDO_ARG too - represent memory access, and are just a proxy for
> stack allocated memory?

I am not sure I understand you. PSEUDO_SYM is the address of the symbol.
Load/Store is using this address to perform memory access.
After convert the memory content into pseudo, that new pseudo represent
the memory storage need to be SSA.

PSEUDO_ARG is just a pseudo receiving the function call arguments.
It will not change either. Any time some one assign a value to the arguments,
it will generate new instance of the pseudo.

Spare IR does not care if the argument is passing from stack or not.

Chris

Re: Question about Sparse Linear form and pseudos

[Dibyendu Majumdar]

Hi Linus,

On 20 August 2017 at 17:20, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Sun, Aug 20, 2017 at 9:12 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>
>> Okay the linear output above seems SSA if we consider how it is shown
>> in the output. But in the code, access to 0[a] occurs via a pseudo -
>> of type PSEUDO_SYM. We see multiple stores happening to this pseudo.
>
> No. There are no stores _to_ the pseudo.
>

Okay I see.

> The PSEUDO_SYM is an *address*. It's not changed. A "store" does not
> assign a value to a pseudo, it writes to *memory*, and the pseudo
> gives the address. It's purely a read of the pseudo.
>
>> So then is it more accurate to say that PSEUDO_SYM and possibly
>> PSEUDO_ARG too - represent memory access, and are just a proxy for
>> stack allocated memory?
>
> No. All pseudos are strictly write-once (after the SSA conversion).
> Memory operations don't write to pseudos. They only use pseudos for
> addresses.
>

Thanks. So does that mean that pseudos are SSA from the initial
linearization phase, and therefore the baseline linear output is
already SSA? By SSA conversion are you referring to the subsequent
phase when memory accesses are converted to pseudos where possible?

Regards
Dibyendu

Re: Question about Sparse Linear form and pseudos

[Linus Torvalds]

On Sun, Aug 20, 2017 at 9:26 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>>
>> No. All pseudos are strictly write-once (after the SSA conversion).
>> Memory operations don't write to pseudos. They only use pseudos for
>> addresses.
>
> Thanks. So does that mean that pseudos are SSA from the initial
> linearization phase, and therefore the baseline linear output is
> already SSA? By SSA conversion are you referring to the subsequent
> phase when memory accesses are converted to pseudos where possible?

I wouldn't guarantee it - I *think* it may be the case that even the
initial linearization is actually proper SSA (just with everything
going through memory), but I don't think it's necessarily a real
design choice. We do have a "non-SSA" mode that turns phi sources into
OP_COPY that is very much not SSA.

So our linearization form does support a non-SSA mode, although
honestly, I'm not sure how useful it is.

Luc knows this code much better than me by now.

                  Linus

Re: Question about Sparse Linear form and pseudos

[Dibyendu Majumdar]

Hi Chris,

On 20 August 2017 at 17:20, Christopher Li <sparse@chrisli.org> wrote:
> On Sun, Aug 20, 2017 at 12:12 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>> Okay the linear output above seems SSA if we consider how it is shown
>> in the output. But in the code, access to 0[a] occurs via a pseudo -
>> of type PSEUDO_SYM. We see multiple stores happening to this pseudo.
>> So the question is each access generated through a different instance
>> of a pseudo? I see that in the code if a symbol already has a pseudo
>
> After promote the memory into pseudo, yes. each store is consider
> a new "define" from the SSA point of  view. So it is a new pseudo,
> or new number of the variable in some SSA book.
>
>> then it is reused. So presumably then PSEUDO_SYMs are not SSA, but
>> PSEUDO_REGs are?
>
> PSEUDO_SYMS are static, you can think them as symbol address.
> It never change. There for it does not need phi node to qualify as SSA.
>

Okay thanks.

>
>> So then is it more accurate to say that PSEUDO_SYM and possibly
>> PSEUDO_ARG too - represent memory access, and are just a proxy for
>> stack allocated memory?
>
> I am not sure I understand you. PSEUDO_SYM is the address of the symbol.
> Load/Store is using this address to perform memory access.
> After convert the memory content into pseudo, that new pseudo represent
> the memory storage need to be SSA.
>
> PSEUDO_ARG is just a pseudo receiving the function call arguments.
> It will not change either. Any time some one assign a value to the arguments,
> it will generate new instance of the pseudo.
>
> Spare IR does not care if the argument is passing from stack or not.
>

Thanks, I understand this better now.

Regards
Dibyendu

Re: Question about Sparse Linear form and pseudos

[Luc Van Oostenryck]

On Sun, Aug 20, 2017 at 6:33 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> I wouldn't guarantee it - I *think* it may be the case that even the
> initial linearization is actually proper SSA (just with everything
> going through memory)

It's odd to me to talk about SSA when there is no phi-nodes
because all accesses are made via memory, but yes, I'm positively
sure that even before we call simplify_symbol_usage() (which
to me is where the real conversion to SSA is done) no pseudo
is defined at two different places. So yes, the SSA properties is
already true at the initial linearization.

> but I don't think it's necessarily a real
> design choice. We do have a "non-SSA" mode that turns phi sources into
> OP_COPY that is very much not SSA.
>
> So our linearization form does support a non-SSA mode, although
> honestly, I'm not sure how useful it is.
>
> Luc knows this code much better than me by now.

It's not really used. It was written to be used by a backend.
I wrote (a good part of) the backend's code selection (for ARM)
but never wrote the register allocator and glued things together.

-- Luc

Re: Question about Sparse Linear form and pseudos

[Dibyendu Majumdar]

Hi Linus,

On 20 August 2017 at 17:33, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Sun, Aug 20, 2017 at 9:26 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>>
>>> No. All pseudos are strictly write-once (after the SSA conversion).
>>> Memory operations don't write to pseudos. They only use pseudos for
>>> addresses.
>>
>> Thanks. So does that mean that pseudos are SSA from the initial
>> linearization phase, and therefore the baseline linear output is
>> already SSA? By SSA conversion are you referring to the subsequent
>> phase when memory accesses are converted to pseudos where possible?
>
> I wouldn't guarantee it - I *think* it may be the case that even the
> initial linearization is actually proper SSA (just with everything
> going through memory), but I don't think it's necessarily a real
> design choice.

I think that is really useful to know that the initial IR is already
SSA and correct.  Certainly in my testing I find that almost all the
IR issues are caused in subsequent phases.

Regards
Dibyendu

Re: Question about Sparse Linear form and pseudos

[Christopher Li]

On Sun, Aug 20, 2017 at 12:33 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> I wouldn't guarantee it - I *think* it may be the case that even the
> initial linearization is actually proper SSA (just with everything
> going through memory), but I don't think it's necessarily a real

I think the initial linearize byte code, the internal usage of pseudo
is SSA and that is by choice.

> design choice. We do have a "non-SSA" mode that turns phi sources into
> OP_COPY that is very much not SSA.

"non-SSA" should happen in a much later stage, when we done with
all the optimization transformation that require SSA. We can remove
SSA. When emit to real machine code, the real machine code does
not have any thing similar to the phi function, which select register
base one where it come from. So the SSA form need to be undo, at
very late stage. SSA is just a tool to help optimizations, not the final
goal.

> So our linearization form does support a non-SSA mode, although
> honestly, I'm not sure how useful it is.

I don't think there is any real use for non-SSA mode in sparse right
now.

Chris

Re: Question about Sparse Linear form and pseudos

[Luc Van Oostenryck]

On Sun, Aug 20, 2017 at 06:45:09PM +0200, Luc Van Oostenryck wrote:
> On Sun, Aug 20, 2017 at 6:33 PM, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
> >
> > I wouldn't guarantee it - I *think* it may be the case that even the
> > initial linearization is actually proper SSA (just with everything
> > going through memory)
> 
> It's odd to me to talk about SSA when there is no phi-nodes
> because all accesses are made via memory, but yes, I'm positively
> sure that even before we call simplify_symbol_usage() (which
> to me is where the real conversion to SSA is done) no pseudo
> is defined at two different places. So yes, the SSA properties is
> already true at the initial linearization.

There is at least one exceptional case, though:
	int foo(int c)
	{
		if (c)
			return 0;
	}

It's, of course, wrong code and should be somehow rejected but
currently, nothing wrong is detected and since returns are
linearized directly with phi-node, we end up with the exit
block having two parents but with a phi-node with a single
operands. It's annoying.

I don't know of any other situations at initial linearization.
So, nothing fundamental but some complications.

There is another whole class of problems concerning SSA correctness
other than the conversion to SSA. It's when correctness is destroyed
by some code transformations involving changes in the CFG:
- packing of BB
- branch simplification: insert_branch()
- possibly try_to_simplify_bb() too

-- Luc