sparse-next and preview of 0.5.1-rc5

sparse-next and preview of 0.5.1-rc5

[Christopher Li]

I have push a preview version of 0.5.1-rc5 to sparse-next.

https://git.kernel.org/pub/scm/devel/sparse/sparse.git/log/?h=sparse-next

If no big surprise, I will push RC5 to master and tag it tomorrow.

The preview of RC5 contain the fix to the nested loop delete bug
report by Luc and other one report by the ptrlist ref count patch. The
nested loop delete bug is really happening with normal kernel checking.
I am glad that is under control now.

There is also one update from gcc attribute.

I have run the following project compilation with sparse and I haven't see
"crazy programmer" error. Linux kernel, git and gcc (for 64 bit).

Chris

Re: sparse-next and preview of 0.5.1-rc5

[Luc Van Oostenryck]

On Fri, Jul 14, 2017 at 10:48:57AM -0700, Christopher Li wrote:
> I have push a preview version of 0.5.1-rc5 to sparse-next.
> 
> https://git.kernel.org/pub/scm/devel/sparse/sparse.git/log/?h=sparse-next
> 
> If no big surprise, I will push RC5 to master and tag it tomorrow.

[Sorry, I'm on vacation and very little computer access].

I still object to the kill_unreachable_bbs() patch and I ask
to reconsider it in favor of the original one.

Since this has already been discussed, I can only invite to read
again the original patch and the one it fixes where the situation
is explained, I think, clearly.

-- Luc

Re: sparse-next and preview of 0.5.1-rc5

[Christopher Li]

On Sat, Jul 15, 2017 at 2:22 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> [Sorry, I'm on vacation and very little computer access].

I am very glad to heard that you are back.

>
> I still object to the kill_unreachable_bbs() patch and I ask
> to reconsider it in favor of the original one.

Of course.  I will hold the RC5 for you. I haven't push the change to
master yet. It is only in sparse-next, I can still roll back the change in we
wants to.

Can you show me some C input file that your original patch will do the
right thing and current one will miss the opportunity to simplify?
Even for the case it is just a suspect of producing worse code is fine.
Just point me to some test case, I will investigate and compare the
results.

My guess is that, there is a good chance some where missing a simplify
opportunity. If it does make a difference and I can't fix it in a timely manner.
Let's use your patch and deal with it after the release. In the long run, I
would prefer not using the two pass deletion of the dead bb, if they can
produce the similar level of optimized result.

> Since this has already been discussed, I can only invite to read
> again the original patch and the one it fixes where the situation
> is explained, I think, clearly.

The original patch does not have test case showing the byte code
difference with this two approach. I need some test examples :-)

Again, glad to know that you are back.

Chris

Re: sparse-next and preview of 0.5.1-rc5

[Christopher Li]

On Sat, Jul 15, 2017 at 10:34 PM, Christopher Li <sparse@chrisli.org> wrote:

> Of course.  I will hold the RC5 for you. I haven't push the change to
> master yet. It is only in sparse-next, I can still roll back the change in we
> wants to.
>
> Can you show me some C input file that your original patch will do the
> right thing and current one will miss the opportunity to simplify?
> Even for the case it is just a suspect of producing worse code is fine.
> Just point me to some test case, I will investigate and compare the
> results.

Ping. I am still waiting for your test source to compare the two
approach of kill_unreachable_bb(). If both generate the equivalent result,
I prefer the simpler approach.

I will hold the RC5 until Wednesday if I don't have additional input.

Thanks

Chris

Re: sparse-next and preview of 0.5.1-rc5

[Luc Van Oostenryck]

On Sat, Jul 15, 2017 at 10:34:46PM -0400, Christopher Li wrote:
> On Sat, Jul 15, 2017 at 2:22 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > [Sorry, I'm on vacation and very little computer access].
> 
> I am very glad to heard that you are back.

Even now, I'm not really back. Just taking time to reply here
while I have the opportunity to.
 
> > I still object to the kill_unreachable_bbs() patch and I ask
> > to reconsider it in favor of the original one.
> 
> Of course.  I will hold the RC5 for you. I haven't push the change to
> master yet. It is only in sparse-next, I can still roll back the change in we
> wants to.
> 
> Can you show me some C input file that your original patch will do the
> right thing and current one will miss the opportunity to simplify?
> Even for the case it is just a suspect of producing worse code is fine.
> Just point me to some test case, I will investigate and compare the
> results.
> 
> My guess is that, there is a good chance some where missing a simplify
> opportunity. If it does make a difference and I can't fix it in a timely manner.
> Let's use your patch and deal with it after the release. In the long run, I
> would prefer not using the two pass deletion of the dead bb, if they can
> produce the similar level of optimized result.
> 
> > Since this has already been discussed, I can only invite to read
> > again the original patch and the one it fixes where the situation
> > is explained, I think, clearly.
> 
> The original patch does not have test case showing the byte code
> difference with this two approach. I need some test examples :-)

Test cases are test cases and code is code.

I'll copy here verbatim the commit message of the patch that was fixed
by the original patch (the one that had "Fixes: 51cfbc90a5e1462fcd624a1598ecd985a508a5d6
 
	commit 51cfbc90a5e1462fcd624a1598ecd985a508a5d6
	Author: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
	Date:   2017-04-26 12:21:21 +0200
	
	    fix: kill unreachable BBs after killing a child
	    
	    When simplifying a switch into a simple branch all the now
	    unused children of the current BB must be removed.
	    If one of these children become now orphaned, it is directly
	    killed (it will need to be killed soon or later since it is
	    unreachable).
	    
	    However, if one of the killed children is the header of a loop
	    where some variables are updated this may cause problems.
	    Indeed, by killing the header (which contains the phisrc of
	    the entry value of the variable) the whole loop may become
	    unreachable but is not killed yet, OTOH simplification of
	    the associated OP_PHI may create a cycle which may then be
	    detected later by simplify_one_memop() which will issue a
	    "crazy programmer" warning while the programmer was innocent.
	    
	    This situation can be seen in code like:
	            int *p;
	            switch (i - i) {        // will be optimized to 0
	            case 0:                 // will be the simple branch
	                    return 0;
	            case 1:                 // will be optimized away
	                    p = ptr;
	                    do {            // will be an unreachable loop
	                            *p++ = 123;
	                    } while (--i);
	            }
	    
	    Fix this by calling kill_unreachable_bbs() after having
	    simplified the switch into a branch. This will avoid to
	    create a cycle with because of the removed phisrc in the
	    header and as an added benefit will avoid to waste time
	    trying to simplify BBs that are unreachable.
	    
	    In addition, it's now useless to call kill_bb() for each
	    removed switch's children as kill_unreachable_bbs() will
	    do that too.
	    
	    Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>

So, in short, the problem that was solved then (the "crazy programmer"
problem) was that incorrect phi-node simplification was done in 
simplify_one_memop() if the phi-node was part of a loop that was
in fact unreachable (in this case, the situation is exactly as if
the phi-node was for some undefined variable, thus the
"crazy programmer" warning).

The unreachable loop was created by insert_branch() (which can be 
called by simplify_instruction()) and simplify_one_memop() is also
called by simplify_instruction(), in our case here, for an OP_LOAD).

So the only way, you can have the assurance that the problem cannot
happen is to call kill_unreachable_bbs() between call to insert_branch()
which delete a branch *and* the next call to simplify_one_memop().

Calling kill_unreachable_bbs() only *after* clean_up_insns() is
too late.

It's not at all a problem of some missing optimization opportunity.
It's a problem of applying some optimization (OP_PHI simplification)
and then giving a warning for the consequence of this optimization
(the "crazy programmer" warning) in incorrect conditions/wrong
assumption (a variable must not be considered as undefined if it
is part of an unreachable BB, it should just be ignored).

I hope it is clear enough now.

Is it annoying that we have to call kill_unreachable_bbs() there?
Yes, clearly it is.
Wouldn't it be nice if we could move the kill_unreachable_bbs() in
the cleanup_and_cse() loop?
Yes, it is (but then in this case, it should be done between the
clean_up_insns() and the CSE loop).
This would need some fundamental change in the way simplification
are done (like maybe moving the simplification of OP_LOADs out of
the clean_up_insns() loop), nothing for an -rc5.


I also assure that instead of quickly rewriting someone's patch
(because you don't like it and think you can do better) it would
be so much better to simply:
- *say* what you don't like in the patch
- *ask* why things are done like this way
- *ask* if things couldn't be done this other way instead.
It would be much less painfull, save a lot of time, you would look much
wiser and it would be much more respectuous of other's work & time.

-- Luc

Re: sparse-next and preview of 0.5.1-rc5

[Christopher Li]

On Wed, Jul 19, 2017 at 3:17 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Even now, I'm not really back. Just taking time to reply here
> while I have the opportunity to.

OK. Good to know then guessing


>> Can you show me some C input file that your original patch will do the
>> right thing and current one will miss the opportunity to simplify?
>> Even for the case it is just a suspect of producing worse code is fine.
>> Just point me to some test case, I will investigate and compare the
>> results.
>
> Test cases are test cases and code is code.
>
> I'll copy here verbatim the commit message of the patch that was fixed
> by the original patch (the one that had "Fixes: 51cfbc90a5e1462fcd624a1598ecd985a508a5d6

I still don't have a valid test case to difference sparse-next
and your patch series.

If your test case is that switch statement, I make a test case
out of it. Sparse-next and yoru patch show the same result
bytecode wise:

int *ptr;
int foo(int *p, int i)
{

switch (i - i) {        // will be optimized to 0
case 0:                 // will be the simple branch
return 0;
case 1:                 // will be optimized away
p = ptr;
do {            // will be an unreachable loop
   *p++ = 123;
} while (--i);
}
return 1;
}

$ ./test-linearize /tmp/d.c
/tmp/d.c:1:5: warning: symbol 'ptr' was not declared. Should it be static?
/tmp/d.c:2:5: warning: symbol 'foo' was not declared. Should it be static?
foo:
.L0:
<entry-point>
ret.32      $0

You know what I want. I want the test case can show sparse-next
have bug or less optimal than your series. If every thing else is
the same, the one in sparse-next is simpler.

>
>         commit 51cfbc90a5e1462fcd624a1598ecd985a508a5d6
>         Author: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
>         Date:   2017-04-26 12:21:21 +0200
>
>             fix: kill unreachable BBs after killing a child
>
>             When simplifying a switch into a simple branch all the now
>             unused children of the current BB must be removed.
>             If one of these children become now orphaned, it is directly
>             killed (it will need to be killed soon or later since it is
>             unreachable).
>
>             However, if one of the killed children is the header of a loop
>             where some variables are updated this may cause problems.
>             Indeed, by killing the header (which contains the phisrc of
>             the entry value of the variable) the whole loop may become
>             unreachable but is not killed yet, OTOH simplification of
>             the associated OP_PHI may create a cycle which may then be
>             detected later by simplify_one_memop() which will issue a
>             "crazy programmer" warning while the programmer was innocent.

That sounds very much like the wine dead loop case recently report on
the mailing list. I think you are likely having a bug elsewhere make you
believe that you have to kill instruction there. I just tested, your patches
will do the dead loop on the wine test C file as well. We might talking about
the same bug.
>
>             This situation can be seen in code like:
>                     int *p;
>                     switch (i - i) {        // will be optimized to 0
>                     case 0:                 // will be the simple branch
>                             return 0;
>                     case 1:                 // will be optimized away
>                             p = ptr;
>                             do {            // will be an unreachable loop
>                                     *p++ = 123;
>                             } while (--i);
>                     }
>
>             Fix this by calling kill_unreachable_bbs() after having
>             simplified the switch into a branch. This will avoid to
>             create a cycle with because of the removed phisrc in the
>             header and as an added benefit will avoid to waste time
>             trying to simplify BBs that are unreachable.
>
>             In addition, it's now useless to call kill_bb() for each
>             removed switch's children as kill_unreachable_bbs() will
>             do that too.

The simple patch in sparse-next has the same output result

> It's not at all a problem of some missing optimization opportunity.
> It's a problem of applying some optimization (OP_PHI simplification)
> and then giving a warning for the consequence of this optimization
> (the "crazy programmer" warning) in incorrect conditions/wrong
> assumption (a variable must not be considered as undefined if it
> is part of an unreachable BB, it should just be ignored).
>
> I hope it is clear enough now.

Can you show me a test C code trigger the problem?

> I also assure that instead of quickly rewriting someone's patch
> (because you don't like it and think you can do better) it would
> be so much better to simply:
I did.
> - *say* what you don't like in the patch

Might have simpler way.

> - *ask* why things are done like this way

I also did. I repeatedly ask for the test C code that show the bug
if I don't immediately remove the dead code.

> - *ask* if things couldn't be done this other way instead.

Same as above. Show me the code please. I would much rather
looking at the test C code that demo the problem than arguing here.

Chris

Re: sparse-next and preview of 0.5.1-rc5

[Luc Van Oostenryck]

On Wed, Jul 19, 2017 at 08:19:02PM -0700, Christopher Li wrote:
> On Wed, Jul 19, 2017 at 3:17 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > Even now, I'm not really back. Just taking time to reply here
> > while I have the opportunity to.
> 
> OK. Good to know then guessing
> 
> 
> >> Can you show me some C input file that your original patch will do the
> >> right thing and current one will miss the opportunity to simplify?
> >> Even for the case it is just a suspect of producing worse code is fine.
> >> Just point me to some test case, I will investigate and compare the
> >> results.
> >
> > Test cases are test cases and code is code.
> >
> > I'll copy here verbatim the commit message of the patch that was fixed
> > by the original patch (the one that had "Fixes: 51cfbc90a5e1462fcd624a1598ecd985a508a5d6
> 
> I still don't have a valid test case to difference sparse-next
> and your patch series.

You don't need a test case to *think* about the code or simply read
the explanation I wrote here under.
 
> If your test case is that switch statement, I make a test case
> out of it. Sparse-next and yoru patch show the same result
> bytecode wise:

Of course, it does.
 
> >         commit 51cfbc90a5e1462fcd624a1598ecd985a508a5d6
> >         Author: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> >         Date:   2017-04-26 12:21:21 +0200
> >
> >             fix: kill unreachable BBs after killing a child
> >
> >             When simplifying a switch into a simple branch all the now
> >             unused children of the current BB must be removed.
> >             If one of these children become now orphaned, it is directly
> >             killed (it will need to be killed soon or later since it is
> >             unreachable).
> >
> >             However, if one of the killed children is the header of a loop
> >             where some variables are updated this may cause problems.
> >             Indeed, by killing the header (which contains the phisrc of
> >             the entry value of the variable) the whole loop may become
> >             unreachable but is not killed yet, OTOH simplification of
> >             the associated OP_PHI may create a cycle which may then be
> >             detected later by simplify_one_memop() which will issue a
> >             "crazy programmer" warning while the programmer was innocent.
> 
> That sounds very much like the wine dead loop case recently report on
> the mailing list.

These two cases are not at all related.

> >             This situation can be seen in code like:
> >                     int *p;
> >                     switch (i - i) {        // will be optimized to 0
> >                     case 0:                 // will be the simple branch
> >                             return 0;
> >                     case 1:                 // will be optimized away
> >                             p = ptr;
> >                             do {            // will be an unreachable loop
> >                                     *p++ = 123;
> >                             } while (--i);
> >                     }
> >
> >             Fix this by calling kill_unreachable_bbs() after having
> >             simplified the switch into a branch. This will avoid to
> >             create a cycle with because of the removed phisrc in the
> >             header and as an added benefit will avoid to waste time
> >             trying to simplify BBs that are unreachable.
> >
> >             In addition, it's now useless to call kill_bb() for each
> >             removed switch's children as kill_unreachable_bbs() will
> >             do that too.
> 
> The simple patch in sparse-next has the same output result
> 
> > It's not at all a problem of some missing optimization opportunity.
> > It's a problem of applying some optimization (OP_PHI simplification)
> > and then giving a warning for the consequence of this optimization
> > (the "crazy programmer" warning) in incorrect conditions/wrong
> > assumption (a variable must not be considered as undefined if it
> > is part of an unreachable BB, it should just be ignored).
> >
> > I hope it is clear enough now.
> 
> Can you show me a test C code trigger the problem?

OK, it wasn't clear enough.

It will be a few more days before I can access to my usual dev stuff
where my tests and tests results are.

However, using the description here above, it's not very hard to imagine
a situation where the two patch will behave differently.
You can even create a test case from the old test case here above
and removing a single line, the one "p = ptr;". It's also very easy
to create all sort of variants of it.
 
-- Luc

Re: sparse-next and preview of 0.5.1-rc5

[Christopher Li]

On Thu, Jul 20, 2017 at 6:35 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> You don't need a test case to *think* about the code or simply read
> the explanation I wrote here under.

It is very hard to reason the bug from the description. At most I can kind
of see how we get to that bad spot. It is very hard for me to think is there
other ways to fix it from the description. If you have the code, that is a lot
easier for me to understand the problem and how to approach the fix.

Thank you from your description below, I can construct a program
to show sparse-next has the "crazy programmer" and your patch
did not. I will take a closer look tomorrow.
> OK, it wasn't clear enough.
>
> It will be a few more days before I can access to my usual dev stuff
> where my tests and tests results are.

I have the test C code follow:

int *ptr;
int foo( int i)
{
int *p;
switch (i - i) {        // will be optimized to 0
case 0:                 // will be the simple branch
return 0;
case 1:                 // will be optimized away
do {            // will be an unreachable loop
   *p++ = 123;
} while (--i);
}
return 1;
}

Which will show "crazy programmer" in sparse-next but not your patch.

The crazy programmer error message deserve a better description.
I will take a closer look tomorrow. For now I am happy, I get what
I ask for.  A test program.

Thanks again.

Chris

Re: sparse-next and preview of 0.5.1-rc5

[Christopher Li]

On Thu, Jul 20, 2017 at 11:40 PM, Christopher Li <sparse@chrisli.org> wrote:
> int *ptr;
> int foo( int i)
> {
> int *p;
> switch (i - i) {        // will be optimized to 0
> case 0:                 // will be the simple branch
> return 0;
> case 1:                 // will be optimized away
> do {            // will be an unreachable loop
>    *p++ = 123;
> } while (--i);
> }
> return 1;
> }
>
> Which will show "crazy programmer" in sparse-next but not your patch.

I dig out more, before it is showing the crazy programmer. This is the
IR it is working on:

Notice the "add.64      %r6 <- %r6, $4", that is very wrong.
Not valid SSA form at all.

I believe that is the one of the condition triggering the crazy programmer
bug.

This error actually reminds me the wine dead loop bug.
In the wine dead loop IR we have:

 setne.32    %r11 <- %r11, $0

This two bugs might actually be related.

We shouldn't have
"add.64      %r6 <- %r6, $4"
That already screw up very badly.
I confirm that "add.64      %r6 <- %r6, $4" was in your purpose
patch as well. It is just you pack the BB early so it does not
trigger the "crazy programmer".

I think your patch pack the BB early to avoid the "crazy programmer".
That sounds more like a cover up rather than a proper fix up.

If we have the proper SSA form, the "crazy programmer" shouldn't
pop up at all.

BTW, that is exactly why I want to get a test C test file to expose
the bug. From the description of the bug does not show as much
detail as the test C code. Different people will have different
views of how the bug happen and how to fix it. Given enough eye
ball, all the bug will be obvious.

Chris


<entry-point>
phisrc.32   %phi3(i) <- %arg1
br          .L2

.L2:
phisrc.32   %phi1(return) <- $0
br          .L4

.L3:
br          .L5

.L5:
add.64      %r6 <- %r6, $4 <============ this is very wrong
store.32    $123 -> 0[%r6] <========== cause crazy programmer here.
br          .L6

.L6:
phi.32      %r7 <- %phi3(i), %phi4(i)
sub.32      %r8 <- %r7, $1
phisrc.32   %phi4(i) <- %r8
cbr         %r8, .L5, .L7

.L7:
br          .L1

.L1:
phisrc.32   %phi2(return) <- $1
br          .L4

.L4:
phi.32      %r4 <- %phi1(return), %phi2(return)
ret.32      %r4

Re: sparse-next and preview of 0.5.1-rc5

[Luc Van Oostenryck]

On Fri, Jul 21, 2017 at 11:55:09PM -0400, Christopher Li wrote:
> Notice the "add.64      %r6 <- %r6, $4", that is very wrong.
> Not valid SSA form at all.

This is typical of situations where undefined pseudos are involved.
For example this is what Linus wrote on the subject some months ago:

	       and.32      %r3 <- %r4, $-65
	        or.32       %r4 <- %r3, $64
	
	which *initializes* the pseudo %r4 in the second instruction, but uses
	it in the first one. That's a classic pattern of uninitialized pseudos
	in sparse exactly because of the SSA logic.
	
	But it is all internally consistent, and the simplification is
	"correct". The simplification phase very much has a "garbage in,
	garbage out" model.

> I believe that is the one of the condition triggering the crazy programmer
> bug.

Of course, again this is explained in the original patch description.
The "crazy programmer" warning is all about this condition,
either in a single instruction or a chain producing such a cycle.

> It is just you pack the BB early so it does not
> trigger the "crazy programmer".

Yes, this is what was explained in the original patch description.

> I think your patch pack the BB early to avoid the "crazy programmer".
> That sounds more like a cover up rather than a proper fix up.

Like explained in the original patch description, this situation with
a self-defined pseudo can happen in unreachable code *even* if the
pseudo was in fact defined if:
- the definition was done in a loop header
- the loop header was deleted by insert_branch()
  * the definition is then removed, the pseudo become undefined
  * it shouldn't matter since all it's use is now in dead code
  * we don't know the that the loop is now dead code before
    kill_unreachable_bbs() is called.
  * therefore, kill_unreachable_bbs() must be called:
    - after a branch have been deleted
    - before simplify_one_memop() is called and is about to issue the
      "crazy programmer" warning 
      BECAUSE THE "crazy programmer" WARNING SHOULD NOT BE ISSUED
      IF THE CONCERNED CODE IS IN FACT DEAD CODE.

So, if you really prefer, you can call kill_unreachable_bbs() just before
the "crazy programmer" check instead of just after the branch delete
like it was done in my patch but calling kill_unreachable_bbs()
only after clean_up_insn() like done in your patch is wrong.

> If we have the proper SSA form, the "crazy programmer" shouldn't
> pop up at all.

See Linus explanation here above.


I found absolutely incredible the amount of time already wasted
on this issue and it is even not closed yet.
I feel really tired and totally disgusted by all this.

-- Luc

Re: sparse-next and preview of 0.5.1-rc5

[Christopher Li]

On Wed, Jul 26, 2017 at 5:00 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> This is typical of situations where undefined pseudos are involved.
> For example this is what Linus wrote on the subject some months ago:
>
>                and.32      %r3 <- %r4, $-65
>                 or.32       %r4 <- %r3, $64
>
>         which *initializes* the pseudo %r4 in the second instruction, but uses
>         it in the first one. That's a classic pattern of uninitialized pseudos
>         in sparse exactly because of the SSA logic.
>
>         But it is all internally consistent, and the simplification is
>         "correct". The simplification phase very much has a "garbage in,
>         garbage out" model.

I think that model is wrong. It is not only "garbage in, garbage out".
It cause sparse freak out due to incorrect SSA form like the wine dead
loop bug. In the above example, %r4 was used *before* it's define,
so there must exist an execution flow loop back to the beginning of
this block. So the proper way should be some thing like:

phi.32 %phi4 <- %phisrc1(VOID), %phisrc2(%r4)
and.32 %r3 <- %phi4, $-65
or.32 %r4 <- %r3, $64
phisrc.32 %phiscrc2 <- %r4

Luc, are you fully back yet?

If you are, please take a look at the wine compile dead loop bug. I
already simplify the test source into minimal form. My guess is that it
is cause by this invalid SSA form as well.

BTW, gcc does not do this kind of invalid SSA form in their IR.

We really should change this model.
>
> Yes, this is what was explained in the original patch description.

OK we are on the same page on cause of the crazy programmer.
Only different view on the SSA form.

 the BB early to avoid the "crazy programmer".
>> That sounds more like a cover up rather than a proper fix up.
>
> Like explained in the original patch description, this situation with
> a self-defined pseudo can happen in unreachable code *even* if the
> pseudo was in fact defined if:
> - the definition was done in a loop header
> - the loop header was deleted by insert_branch()
>   * the definition is then removed, the pseudo become undefined
>   * it shouldn't matter since all it's use is now in dead code
>   * we don't know the that the loop is now dead code before
>     kill_unreachable_bbs() is called.
>   * therefore, kill_unreachable_bbs() must be called:
>     - after a branch have been deleted
>     - before simplify_one_memop() is called and is about to issue the
>       "crazy programmer" warning
>       BECAUSE THE "crazy programmer" WARNING SHOULD NOT BE ISSUED
>       IF THE CONCERNED CODE IS IN FACT DEAD CODE.

I totally get that part. My point is that, the crazy programmer warning
is an ill form of SSA to begin with. We might need to address that illegal
SSA form as well. My impression is that the illegal SSA from cause the
wine dead loop bug as well.

> So, if you really prefer, you can call kill_unreachable_bbs() just before
> the "crazy programmer" check instead of just after the branch delete
> like it was done in my patch but calling kill_unreachable_bbs()
> only after clean_up_insn() like done in your patch is wrong.

I don't think it is wrong. Because even with your patch, there is
other ways to get into "crazy programmer" situation. We need to
address that.

My point is that, "crazy programmer" is an ill form of  SSA it shouldn't
exist in the first place.

>
>> If we have the proper SSA form, the "crazy programmer" shouldn't
>> pop up at all.
>
> See Linus explanation here above.

I am not convinced that is a good enough reason to allow this
kind of ill form of SSA. It save a phi instruction but cost a lot of
trouble down the road.

> I found absolutely incredible the amount of time already wasted
> on this issue and it is even not closed yet.
> I feel really tired and totally disgusted by all this.

Luc, I hope you have a good rest during your time off sparse.

Getting the compiler back end optimization right is hard and
tedious.

Chris

Re: sparse-next and preview of 0.5.1-rc5

[Luc Van Oostenryck]

On Wed, Jul 26, 2017 at 12:10:20PM -0400, Christopher Li wrote:
> On Wed, Jul 26, 2017 at 5:00 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > This is typical of situations where undefined pseudos are involved.
> > For example this is what Linus wrote on the subject some months ago:
> >
> >                and.32      %r3 <- %r4, $-65
> >                 or.32       %r4 <- %r3, $64
> >
> >         which *initializes* the pseudo %r4 in the second instruction, but uses
> >         it in the first one. That's a classic pattern of uninitialized pseudos
> >         in sparse exactly because of the SSA logic.
> >
> >         But it is all internally consistent, and the simplification is
> >         "correct". The simplification phase very much has a "garbage in,
> >         garbage out" model.
> 
> I think that model is wrong.

I'm not fond of it myself, far from it, but for the moment
it's how sparse is working.

> It is not only "garbage in, garbage out".
> It cause sparse freak out due to incorrect SSA form like the wine dead
> loop bug. In the above example, %r4 was used *before* it's define,
> so there must exist an execution flow loop back to the beginning of
> this block.

I hadn't time to look closely to the wine bug but I'm very aware
of what can happen to undefined pseudos *coupled* to the optimization
that are done on them (basically they are essentially ignored as
phi-sources, this coupled with CSE make that once loops are involved
you have this sort of self-defined pseudos, directly or indirectly).

> So the proper way should be some thing like:
> 
> phi.32 %phi4 <- %phisrc1(VOID), %phisrc2(%r4)
> and.32 %r3 <- %phi4, $-65
> or.32 %r4 <- %r3, $64
> phisrc.32 %phiscrc2 <- %r4
> 
> Luc, are you fully back yet?
> 
> If you are, please take a look at the wine compile dead loop bug. I
> already simplify the test source into minimal form. My guess is that it
> is cause by this invalid SSA form as well.

I had the impression it was something else but as I said I
haven't really looked at it.

> BTW, gcc does not do this kind of invalid SSA form in their IR.

GCC has a very different optimization architecture, for example,
they don't try to reach a fix-point as this would be way too costly.
They simply have a number of passes, in a fixed order, and some of them
can be (optionally) repeadted at some stages (-frerun-cse-after-loop,
-fgcse, -fgcse-after-reload, ...).
 
GCC is also very bad at giving good warnings for undefined variables
(cfr., for example, https://gcc.gnu.org/bugzilla/show_bug.cgi?id=18501)

> We really should change this model.

The patch series I have to solve the problem of misplaced phi-nodes
use an explicit PSEUDO_UNDEF type don't try to do anything with them
(on pupose, so that 1) we can given some warnings about undef vars,
2) we can *decide* to do optimization on them or not).
This is of course not material for a -rc5.

> OK we are on the same page on cause of the crazy programmer.
> Only different view on the SSA form.
> 
>  the BB early to avoid the "crazy programmer".
> >> That sounds more like a cover up rather than a proper fix up.
> >
> > Like explained in the original patch description, this situation with
> > a self-defined pseudo can happen in unreachable code *even* if the
> > pseudo was in fact defined if:
> > - the definition was done in a loop header
> > - the loop header was deleted by insert_branch()
> >   * the definition is then removed, the pseudo become undefined
> >   * it shouldn't matter since all it's use is now in dead code
> >   * we don't know the that the loop is now dead code before
> >     kill_unreachable_bbs() is called.
> >   * therefore, kill_unreachable_bbs() must be called:
> >     - after a branch have been deleted
> >     - before simplify_one_memop() is called and is about to issue the
> >       "crazy programmer" warning
> >       BECAUSE THE "crazy programmer" WARNING SHOULD NOT BE ISSUED
> >       IF THE CONCERNED CODE IS IN FACT DEAD CODE.
> 
> I totally get that part. My point is that, the crazy programmer warning
> is an ill form of SSA to begin with. We might need to address that illegal
> SSA form as well.

OK. In short, undefined pseudos cause this SSA you call illegal and that
Linus call typical of uninitialized pseudos. Different nomenclatures, fine.

But the whole thing about all this discussion is that
- after some optimizations
- in dead/unreachable code
- you *can* have uninitialized pseudos that *were* perfectly initialized
  in the initial code.
- and doing further optimization on this dead code wil then create real
  problems like this false "crazy programmer" warning.

It's of course an unpleasant situation, one that is present since
a long time, sort of at the core of sparse. I can be solved in
severals ways but the only simple one, adequate for an -rc5 is
to avoid doing optimization on those unreachable BBs, like my
patch insure to do in all cases and your version do only some cases.

> My impression is that the illegal SSA from cause the
> wine dead loop bug as well.

I'll take a look at it.

> > So, if you really prefer, you can call kill_unreachable_bbs() just before
> > the "crazy programmer" check instead of just after the branch delete
> > like it was done in my patch but calling kill_unreachable_bbs()
> > only after clean_up_insn() like done in your patch is wrong.
> 
> I don't think it is wrong. Because even with your patch, there is
> other ways to get into "crazy programmer" situation. We need to
> address that.
> 
> My point is that, "crazy programmer" is an ill form of  SSA it shouldn't
> exist in the first place.

The "crazy programmer" warning is a very valid warning.
It has a very bad description but it is simply a warning for
vars. Try on some code like:
	void bad0(void)
	{
		int *a;
		*a++;
	}

It will very legitimately give you one of such "crazy programmer"
warning, which really should be something like:
	warning: (possibly) undefined variable 'a'
In others words, what you call 'illegal SSA form' is, very much
by design, the symptoms of undefined vars and it's the only one we
currently have. It's also fo form of self-consistency check that will
need to stay independently of how undefined vars are treated.

Of course, once we get this situation and this warning on perfectly
valid and defined code because we try to apply some optimizations
on code that have been partially optimized away (the initialization
have been removed but the uses have not), things are very different.

> > I found absolutely incredible the amount of time already wasted
> > on this issue and it is even not closed yet.
> > I feel really tired and totally disgusted by all this.
> 
> Luc, I hope you have a good rest during your time off sparse.
> 
> Getting the compiler back end optimization right is hard and
> tedious.

Absolutely, and I would really appreciate to spend my time on
useful work rather than on these discussions.

-- Luc