SSSA and some C pointer manipulation.

SSSA and some C pointer manipulation.

[Christopher Li]

Hi Luc,

I have done the first round of reading your 29 patches.
It is actually very nice organized. Thanks for the effort
to make this review so easy to digest.

One thing I notices is that, if the use site is very far
from define, there are a lot of blocks in between. That
will cause a lot of possible phi node to be created.
That plus the ptrmap will have some memory allocation
over head. Might explain the 2% slow down.
Compare to classic way to convert to SSA. The expansive
part is doing the dominator tree. However that is mostly
read, very few write. The SSA is doing a lot of write
(creating phi node just in case it is needed.)

Another thing I just realized is that, this SSSA conversion
only works for *local* variable, not C pointers?
I want to construct some test source to verify.
However it is not even working for the base case:

================test 1.c=========
int a, b, c, d, e;

static void foo(void)
{
if (a)
b = c;
else
b = d;
if (c)
a = b;
if (b)
e = a;
}

for this test, none of the global variable access has
been promote to SSA. In this regard, it is different
in master. The master branch at least try to promote
a, b, c, d, e content pseudot to ssa.

This is from sssa-mini-v1
foo:
.L0:
<entry-point>
load.32     %r1 <- 0[a]
cbr         %r1, .L1, .L2

.L1:
load.32     %r2 <- 0[c]
store.32    %r2 -> 0[b]
br          .L3

.L2:
load.32     %r3 <- 0[d]
store.32    %r3 -> 0[b]
br          .L3

.L3:
load.32     %r4 <- 0[c]
cbr         %r4, .L4, .L5

.L4:
load.32     %r5 <- 0[b]
store.32    %r5 -> 0[a]
br          .L5

.L5:
load.32     %r6 <- 0[b]
cbr         %r6, .L6, .L8

.L6:
load.32     %r7 <- 0[a]
store.32    %r7 -> 0[e]
br          .L8

.L8:
ret

No phi at all.

============== test 2.c ==========
int a, c, d;

static int foo(void)
{
int b, e;
if (a)
b = c;
else
b = d;
if (c)
a = b;
if (b)
e = a;
return e;
}

static int foo_ptr(void)
{
int b, *bp = &b;
int e, *ep = &e;

if (a)
*bp = c;
else
*bp = d;
if (c)
a = *bp;
if (b)
e = a;
return e;
}
==============
There are two functions foo() and foo_ptr(),
The are exactly the same, except foo_ptr() is using
ptr to access the variable. The pointer is not used
for another other purpose.

You can see in the foo base, the variable b
has been promote to SSA. However, in foo_ptr()
the variable b has not been promote to SSA.

I look back the paper, the paper actually did not
discuss pointer at all. However pointer usage is
a big part of C. So in this regard, the previous master
branch actually try to promote the variable used by
pointers, because it first convert the symbol to symbol
address and using load and store to access them.

That I see as another big draw back the paper
haven't cover, (other than goto. ) The pointers.
It can't effectively deal with pointer because it
does not have the CFG yet. In that regard, this
series functionally is less than what is in the previous
master branch does. Given the previous master does
it incorrectly. I think fixing them wouldn't be much
bigger than what is needed for SSSA.

If we want to deal with pointer, I suspect it will need
to do more or less the SSSA paper  trying to avoid.
Do the CFG route and promote memory access to
pseudo. That means we can't remove that code in
patch 29 and also need to make it work as well.

Any idea how to make the above two test case
work?

Chris

Re: SSSA and some C pointer manipulation.

[Dibyendu Majumdar]

Hi Chris,

On 19 August 2017 at 03:46, Christopher Li <sparse@chrisli.org> wrote:
> Another thing I just realized is that, this SSSA conversion
> only works for *local* variable, not C pointers?
> I want to construct some test source to verify.
> However it is not even working for the base case:

I think it is an excellent idea to create a bunch of careful tests to
assess / validate the changes. Perhaps the tests should cover various
scenarios including switch statements, gotos, computed gotos, looping
constructs, etc. And specific uses of globals, pointers, locals etc.

Thanks and Regards
Dibyendu

Re: SSSA and some C pointer manipulation.

[Christopher Li]

On 8/19/17, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> I think it is an excellent idea to create a bunch of careful tests to
> assess / validate the changes. Perhaps the tests should cover various
> scenarios including switch statements, gotos, computed gotos, looping
> constructs, etc. And specific uses of globals, pointers, locals etc.
>

That is the idea for the test suite. To test how sparse handle
different source code.

There is also the idea of the debug version of sparse. Instead
having the fix input source. It will do dynamic verification
of sparse at run time. e.g. If there is a slow and reliable way
to generate SSA conversion. Then in the debug version will do
both the slow and reliable way and the new fast and optimal way.
Then compare notes to draw conclusion that the new way *is* better.
AT least not worse than the old way. In this case I want to verify
that, the new method at least cover all the variable converted
by the old method. Including variable used by pointers.

Chris

Re: SSSA and some C pointer manipulation.

[Dibyendu Majumdar]

Hi Chris,

On 19 August 2017 at 11:56, Christopher Li <sparse@chrisli.org> wrote:
> On 8/19/17, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
>> I think it is an excellent idea to create a bunch of careful tests to
>> assess / validate the changes. Perhaps the tests should cover various
>> scenarios including switch statements, gotos, computed gotos, looping
>> constructs, etc. And specific uses of globals, pointers, locals etc.
>>
>
> That is the idea for the test suite. To test how sparse handle
> different source code.
>

Yes. I have a growing set of tests but I only check the final result
is correct - i.e. the code can be run (both with and without
simplifications) and will produce expected results. I do not check
whether the Sparse IR is optimum or not, as I have been more focussed
on getting the right outcome.

> There is also the idea of the debug version of sparse. Instead
> having the fix input source. It will do dynamic verification
> of sparse at run time. e.g. If there is a slow and reliable way
> to generate SSA conversion. Then in the debug version will do
> both the slow and reliable way and the new fast and optimal way.
> Then compare notes to draw conclusion that the new way *is* better.
> AT least not worse than the old way. In this case I want to verify
> that, the new method at least cover all the variable converted
> by the old method. Including variable used by pointers.
>

Sure but this is kind of hard to do - because to validate something
you need a definition of what is "good" or "expected". Ideally of
course the output will be correct and at least as optimum as before -
but I would rather it is correct first.

Regards
Dibyendu

Re: SSSA and some C pointer manipulation.

[Christopher Li]

On Sat, Aug 19, 2017 at 7:57 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi Chris,
>
> On 19 August 2017 at 11:56, Christopher Li <sparse@chrisli.org> wrote:
>> On 8/19/17, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
>>> I think it is an excellent idea to create a bunch of careful tests to
>>> assess / validate the changes. Perhaps the tests should cover various
>>> scenarios including switch statements, gotos, computed gotos, looping
>>> constructs, etc. And specific uses of globals, pointers, locals etc.
>>>
>>
>> That is the idea for the test suite. To test how sparse handle
>> different source code.
>>
>
> Yes. I have a growing set of tests but I only check the final result
> is correct - i.e. the code can be run (both with and without
> simplifications) and will produce expected results. I do not check
> whether the Sparse IR is optimum or not, as I have been more focussed
> on getting the right outcome.

Yes, w can extend that.


>
>> There is also the idea of the debug version of sparse. Instead
>> having the fix input source. It will do dynamic verification
>> of sparse at run time. e.g. If there is a slow and reliable way
>> to generate SSA conversion. Then in the debug version will do
>> both the slow and reliable way and the new fast and optimal way.
>> Then compare notes to draw conclusion that the new way *is* better.
>> AT least not worse than the old way. In this case I want to verify
>> that, the new method at least cover all the variable converted
>> by the old method. Including variable used by pointers.
>>
>
> Sure but this is kind of hard to do - because to validate something
> you need a definition of what is "good" or "expected". Ideally of
> course the output will be correct and at least as optimum as before -
> but I would rather it is correct first.

For SSA it is actually not hard to define what is good:
1) Phi node place at the DF.
2) For each incoming edge,  phi node has a source define dominate the
parent block.
2) define dominate use.

For SSSA I would like to add:
3) Cover the variable that converted in previous code.

All can express in code.

Chris

Re: SSSA and some C pointer manipulation.

[Luc Van Oostenryck]

On Sat, Aug 19, 2017 at 1:57 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> Yes. I have a growing set of tests but I only check the final result
> is correct - i.e. the code can be run (both with and without
> simplifications) and will produce expected results.

While I'm all in favour of such tests, I also think that at the current
stage of sparse's development, such tests are not what we
need because:
1) to be able to run/execute the code you need a whole machinery
    we don't have yet
2) they are dependent on implementation details, kinda architecture/
    machine specific
3) they are dependent on the correctness of the backend used
4) they are dependent on run-time support (like printf()
    implementation, for example.
4) they don't help at all to debug

So, this kind of tests makes a lot of sense to you because you're
developing a backend. They will certainly be useful later if/when
sparse will have a backend. But currently, small, specific, more
unit-like tests are much more useful to me.

-- Luc

Re: SSSA and some C pointer manipulation.

[Dibyendu Majumdar]

Hi Luc,

On 20 August 2017 at 01:08, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Sat, Aug 19, 2017 at 1:57 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>
>> Yes. I have a growing set of tests but I only check the final result
>> is correct - i.e. the code can be run (both with and without
>> simplifications) and will produce expected results.
>
> While I'm all in favour of such tests, I also think that at the current
> stage of sparse's development, such tests are not what we
> need because:
> 1) to be able to run/execute the code you need a whole machinery
>     we don't have yet
> 2) they are dependent on implementation details, kinda architecture/
>     machine specific
> 3) they are dependent on the correctness of the backend used
> 4) they are dependent on run-time support (like printf()
>     implementation, for example.
> 4) they don't help at all to debug
>
> So, this kind of tests makes a lot of sense to you because you're
> developing a backend. They will certainly be useful later if/when
> sparse will have a backend. But currently, small, specific, more
> unit-like tests are much more useful to me.
>

I think you are raising a deeply philosophical issue. I firmly believe
all tests are good and needed, and take the pragmatic view that I will
use whatever tests I can lay my hands on. Sure we want unit tests as
these help debug problems. But these need to be written by whoever is
developing a feature or enhancement. Perhaps Sparse should adopt the
contribution policy that no changes should be accepted without
accompanying unit tests.

Regards
Dibyendu

Re: SSSA and some C pointer manipulation.

[Luc Van Oostenryck]

On Sun, Aug 20, 2017 at 2:33 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> I think you are raising a deeply philosophical issue.

It was only a pragmatic issue.

> I firmly believe
> all tests are good and needed, and take the pragmatic view that I will
> use whatever tests I can lay my hands on.

Of course.

> Sure we want unit tests as
> these help debug problems. But these need to be written by whoever is
> developing a feature or enhancement. Perhaps Sparse should adopt the
> contribution policy that no changes should be accepted without
> accompanying unit tests.

Patches for the test suite are certainly most welcome.

-- Luc

Re: SSSA and some C pointer manipulation.

[Luc Van Oostenryck]

On Sat, Aug 19, 2017 at 4:46 AM, Christopher Li <sparse@chrisli.org> wrote:
Hi Chris,

> One thing I notices is that, if the use site is very far
> from define, there are a lot of blocks in between. That
> will cause a lot of possible phi node to be created.

That's not what's happenning or what should happening.
I know that in such situation the current SSA may
creates fewer phi-nodes because the creation of phi-nodes
are delayed to the point where the value is effectively
used, but the's precisely why this method is wrong.

On the other hand, I have some very nice examples
where you have N if-statements and the current SSA
method creates N^2 phi-nodes while only N are needed
and the new method only creates these N ones.

It's really dangerous to compare the new method with
the old one because the old one does it wrongly.

> Another thing I just realized is that, this SSSA conversion
> only works for *local* variable, not C pointers?

It's very confusing to use the word 'C pointer' here.
A pointer is just a value like any other. What's you're
talking about, I think, is variables accessed through a
pointer.

> ...
> There are two functions foo() and foo_ptr(),
> The are exactly the same, except foo_ptr() is using
> ptr to access the variable. The pointer is not used
> for another other purpose.
>
> You can see in the foo base, the variable b
> has been promote to SSA. However, in foo_ptr()
> the variable b has not been promote to SSA.

It's indeed a difference between the current method
and the new one. The new one simply hasn't yet enough
information to prove that these global vars can't be
modified by some external way between the
accesses.

You must also not forget that the current method also
can't convert all possible global vars to pseudo
during the SSA conversion (simplify_symbol_usage()).
Simplify_loads() which is called *after* the 'general' SSA
conversion convert some such accesses after (and do it
wrongly too!).

What I mean here is that it's normal to not be able to
convert all possible accesses directly. But yes, for sure,
the most we can convert early, the best it is.

> I look back the paper, the paper actually did not
> discuss pointer at all.

Of course, because this topic is unrelated to the method.
What's your talking about is:
1) decide/select which vars will be promoted to pseudos
    (and this will be concerned witht he SSA)
2) alias analysis
These are topics orthogonal to the conversion *method*
(which doesn't mean that all methods offer the same possibilities).

You must also not forget that the paper is an academic paper
about a method. It's not a step-by-step guide on how
you must engineer your compiler.


-- Luc

Re: SSSA and some C pointer manipulation.

[Christopher Li]

On Sun, Aug 20, 2017 at 12:18 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> One thing I notices is that, if the use site is very far
>> from define, there are a lot of blocks in between. That
>> will cause a lot of possible phi node to be created.
>
> That's not what's happenning or what should happening.
> I know that in such situation the current SSA may
> creates fewer phi-nodes because the creation of phi-nodes
> are delayed to the point where the value is effectively
> used, but the's precisely why this method is wrong.

I am more on the line of thinking comparing the SSSA vs
fixing the previous SSA method, place the phi node in DF.

> On the other hand, I have some very nice examples
> where you have N if-statements and the current SSA
> method creates N^2 phi-nodes while only N are needed
> and the new method only creates these N ones.
>
> It's really dangerous to compare the new method with
> the old one because the old one does it wrongly.

Yes, the current method does it wrong. I am trying
to evaluate what doe it take to get it right, fixing it
vs having the new rewrite of SSSA.

> It's very confusing to use the word 'C pointer' here.
> A pointer is just a value like any other. What's you're
> talking about, I think, is variables accessed through a
> pointer.

No necessary variables. It can be just memory objects
like link->next, link->prev etc. Those object are not
declare in the function. The pointer might be.

> It's indeed a difference between the current method
> and the new one. The new one simply hasn't yet enough
> information to prove that these global vars can't be
> modified by some external way between the
> accesses.
>
> You must also not forget that the current method also
> can't convert all possible global vars to pseudo
> during the SSA conversion (simplify_symbol_usage()).
> Simplify_loads() which is called *after* the 'general' SSA
> conversion convert some such accesses after (and do it
> wrongly too!).
>
> What I mean here is that it's normal to not be able to
> convert all possible accesses directly. But yes, for sure,
> the most we can convert early, the best it is.

What I am trying to evaluate is that, can SSSA satisify
all our need to promote memory access into pseudo.
If seems the answer is no, we still need to other other
means to promote memory into pseudo, e.g. the memory
storage access by pointers. That is actually a very common case.

>
>> I look back the paper, the paper actually did not
>> discuss pointer at all.
>
> Of course, because this topic is unrelated to the method.
> What's your talking about is:
> 1) decide/select which vars will be promoted to pseudos
>     (and this will be concerned witht he SSA)
> 2) alias analysis
> These are topics orthogonal to the conversion *method*
> (which doesn't mean that all methods offer the same possibilities).
>
> You must also not forget that the paper is an academic paper
> about a method. It's not a step-by-step guide on how
> you must engineer your compiler.

Right. Back to sparse. first of all. Let's agree on promoting
memory access into SSA pseudo is some thing we need.
It other words, we need more than just SSA convert local
variables. We want other type of memory access as well.

If SSSA does not support that easily. We need to have other
means to support memory access into SSA pseudo, one
of the possibility just doing the classic SSA conversion for
the case that SSSA does not support (memory access
through pointers).

For merging SSSA to master, I want to make two request:

1) instead of delete the old code and lost feature of promoting
    memory (other than local variable) to pseudo. Leave the
    previous code in and control by some debug options.
    When the option is turn on, it will use the old code path
    to promote the memory not cover by SSSA into pseudo.
    I understand currently the old code path does it wrong,
    I am trying to figure out what it takes to fix it. It is a lot
    harder try to fix it if the code is removed. This option can
    be off by default.

2) Have some option for SSSA to disable the SSSA promotion
    variable to pseudo without extra execution cost. This is
    can get us the current pre-simplify linearization byte code.
    This has two purpose.  The first one is just one debugging
    checkpoint. If we have bug in SSA,  we can find out if the
    linearization has bug or the bug was introduce in SSSA.
    The second purpose is that, if we fix the SSA promotion on
    existing code path, by  implementing some of the classic SSA.
    I am curious to find out what is the running number comparing
    again SSSA. We can turn SSSA off and let the alternative
    SSA conversion do all the work. And see how well it perform.
    This option can be on by default.

If you have other ways to make SSSA works with memory
accessed by pointers, we can add that later as well. As of the
current SSSA patches, this part of the feature is missing.

Chris

Re: SSSA and some C pointer manipulation.

[Christopher Li]

On Sun, Aug 20, 2017 at 11:29 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Sun, Aug 20, 2017 at 12:18 PM, Luc Van Oostenryck

>     again SSSA. We can turn SSSA off and let the alternative
>     SSA conversion do all the work. And see how well it perform.
>     This option can be on by default.

Sorry I mean we can leave the SSSA method on by default.

Chris

Re: SSSA and some C pointer manipulation.

[Luc Van Oostenryck]

On Fri, Aug 18, 2017 at 10:46:13PM -0400, Christopher Li wrote:
> Hi Luc,
> 
> I have done the first round of reading your 29 patches.
> It is actually very nice organized. Thanks for the effort
> to make this review so easy to digest.
> 
> One thing I notices is that, if the use site is very far
> from define, there are a lot of blocks in between. That
> will cause a lot of possible phi node to be created.
> That plus the ptrmap will have some memory allocation
> over head. Might explain the 2% slow down.
> Compare to classic way to convert to SSA. The expansive
> part is doing the dominator tree. However that is mostly
> read, very few write. The SSA is doing a lot of write
> (creating phi node just in case it is needed.)
> 
> Another thing I just realized is that, this SSSA conversion
> only works for *local* variable, not C pointers?
> I want to construct some test source to verify.
> However it is not even working for the base case:
> 
> ================test 1.c=========

int a, b, c, d, e;

void foo(void)
{
	if (a)
		b = c;
	else
		b = d;
	if (c)
		a = b;
	if (b)
		e = a;
}

We should idealy have:
- loads of a, c & d
- store(s) of b
- load of c
- resue b's value
- the store of a = b
- reuse b's value
- resue a's value
- store e = a

What I have now for this is:
	foo:
	.L0:
		<entry-point>
		load.32     %r1(a) <- 0[a]
		cbr         %r1(a), .L1, .L2

	.L1:
		load.32     %r2(b) <- 0[c]
		store.32    %r2(b) -> 0[b]
		phisrc.32   %phi3 <- %r2(b)
		br          .L3

	.L2:
		load.32     %r3 <- 0[d]
		store.32    %r3 -> 0[b]
		phisrc.32   %phi4 <- %r3
		br          .L3

	.L3:
		phi.32      %r9(b) <- %phi3, %phi4
		load.32     %r4 <- 0[c]
		select.32   %r8(a) <- %r4, %r9(b), %r1(a)
		cbr         %r4, .L4, .L5

	.L4:
		store.32    %r9(b) -> 0[a]
		br          .L5

	.L5:
		cbr         %r9(b), .L6, .L8

	.L6:
		store.32    %r8(a) -> 0[e]
		br          .L8

	.L8:
		ret


For comparison, what -rc5 gives is:
	foo:
	.L0:
		<entry-point>
		load.32     %r1(a) <- 0[a]
		phisrc.32   %phi1(a) <- %r1(a)
		cbr         %r1(a), .L1, .L2

	.L1:
		load.32     %r2(b) <- 0[c]
		store.32    %r2(b) -> 0[b]
		phisrc.32   %phi3(c) <- %r2(b)
		phisrc.32   %phi4(b) <- %r2(b)
		phisrc.32   %phi7(b) <- %r2(b)
		phisrc.32   %phi9(b) <- %r2(b)
		br          .L3

	.L2:
		load.32     %r3 <- 0[d]
		store.32    %r3 -> 0[b]
		phisrc.32   %phi5(b) <- %r3
		phisrc.32   %phi8(b) <- %r3
		br          .L3

	.L3:
		load.32     %r4 <- 0[c]
		cbr         %r4, .L4, .L5

	.L4:
		phi.32      %r5 <- %phi7(b), %phi8(b)
		store.32    %r5 -> 0[a]
		phisrc.32   %phi2(a) <- %r5
		phisrc.32   %phi6(b) <- %r5
		br          .L5

	.L5:
		phi.32      %r6 <- %phi4(b), %phi5(b), %phi6(b)
		cbr         %r6, .L6, .L7

	.L6:
		phi.32      %r7 <- %phi1(a), %phi2(a)
		store.32    %r7 -> 0[e]
		br          .L7

	.L7:
		ret


-- Luc