Infinite loop with OOM while testing Sparse on Wine code

Infinite loop with OOM while testing Sparse on Wine code

[Michael Stefaniuc]

Hello guys,

I thought I'll test the new sparse on the Wine source code, especially
as I remember to have gotten 1-2 of those famous "Crazy programmer" errors.

But I seem to get an infinite loop with a mem leak: 100% CPU with the
memory utilization increasing until this line triggers
sparse/allocate.c:105:                 die("out of memory");

I'm using sparse v0.5.1-rc4-8-g27f4502 which was the tip of spare-next
as of this morning.
Also this is for the 64bit Wine build as cgcc is not working as is for
the 32bit build.


make[1]: Entering directory '/j/wine/build/sparse64/dlls/user32/tests'
cgcc -c -o menu.o /home/michi/work/wine/dlls/user32/tests/menu.c -I. \
  -I/home/michi/work/wine/dlls/user32/tests -I../../../include
-I/home/michi/work/wine/include \
  -D__WINESRC__ -D_REENTRANT -fPIC -Wall -pipe -fno-strict-aliasing
-Wdeclaration-after-statement \
  -Wempty-body -Wignored-qualifiers -Wshift-overflow=2
-Wstrict-prototypes -Wtype-limits \
  -Wunused-but-set-parameter -Wvla -Wwrite-strings -Wpointer-arith
-Wlogical-op -gdwarf-2 \
  -gstrict-dwarf -g -O2
/home/michi/work/wine/include/winuser.h:1662:22: error: dubious one-bit
signed bitfield
/home/michi/work/wine/include/winuser.h:1663:19: error: dubious one-bit
signed bitfield
out of memory
Makefile:538: recipe for target 'menu.o' failed
make[1]: *** [menu.o] Error 1


To reproduce:
git clone git://source.winehq.org/git/wine.git
cd wine
./configure --enable-win64
make -j`getconf _NPROCESSORS_ONLN` CC=cgcc


Though I'm not sure that this qualifies as a blocker for the 0.5.1
release. The Wine code was pretty tough on sparse previously; it has
been years since I last tried. Crashes and mis-parses were normal back
then as Wine uses language features that are still unimplemented (wide
character string literals). But I do not remember to have encountered an
infinite loop with a mem leak.

thanks
bye
	michael

Re: Infinite loop with OOM while testing Sparse on Wine code

[Christopher Li]

On Tue, Jul 18, 2017 at 10:47 AM, Michael Stefaniuc
<mstefani@mykolab.com> wrote:
> But I seem to get an infinite loop with a mem leak: 100% CPU with the
> memory utilization increasing until this line triggers
> sparse/allocate.c:105:                 die("out of memory");

Thank you for the report. I will take a look at it.
> To reproduce:
> git clone git://source.winehq.org/git/wine.git
> cd wine
> ./configure --enable-win64
> make -j`getconf _NPROCESSORS_ONLN` CC=cgcc

I will try to reproduce it.

>
>
> Though I'm not sure that this qualifies as a blocker for the 0.5.1
> release. The Wine code was pretty tough on sparse previously; it has
> been years since I last tried. Crashes and mis-parses were normal back
> then as Wine uses language features that are still unimplemented (wide
> character string literals). But I do not remember to have encountered an
> infinite loop with a mem leak.

That sounds like a blocker to me. Hopefully it is not too hard to fix.

Chris

Re: Infinite loop with OOM while testing Sparse on Wine code

[Christopher Li]

On Tue, Jul 18, 2017 at 10:47 AM, Michael Stefaniuc
<mstefani@mykolab.com> wrote:
>
> make[1]: Entering directory '/j/wine/build/sparse64/dlls/user32/tests'
> cgcc -c -o menu.o /home/michi/work/wine/dlls/user32/tests/menu.c -I. \
>   -I/home/michi/work/wine/dlls/user32/tests -I../../../include
> -I/home/michi/work/wine/include \
>   -D__WINESRC__ -D_REENTRANT -fPIC -Wall -pipe -fno-strict-aliasing
> -Wdeclaration-after-statement \
>   -Wempty-body -Wignored-qualifiers -Wshift-overflow=2
> -Wstrict-prototypes -Wtype-limits \
>   -Wunused-but-set-parameter -Wvla -Wwrite-strings -Wpointer-arith
> -Wlogical-op -gdwarf-2 \
>   -gstrict-dwarf -g -O2

Adding CC of Luc,

It is much easier to reproduce the error from the command line as above.
Just update the wine directory name is good enough for me.

I can see how it is loop on the CSE phase. It is trying to simplify the
set_ne constant follow by a branch. However it did not change the
instruction and keep setting the CSE flag. Need more digging.

My gut feeling is that we should fix this before the release.

Chris

Re: Infinite loop with OOM while testing Sparse on Wine code

[Christopher Li]

On Tue, Jul 18, 2017 at 10:47 AM, Michael Stefaniuc
<mstefani@mykolab.com> wrote:
> Hello guys,
>
> I thought I'll test the new sparse on the Wine source code, especially
> as I remember to have gotten 1-2 of those famous "Crazy programmer" errors.
>
> But I seem to get an infinite loop with a mem leak: 100% CPU with the
> memory utilization increasing until this line triggers
> sparse/allocate.c:105:                 die("out of memory");


OK, I have shrink the test program into the following code.
It can still reproduce the dead loop. It is related to simplify
the phi source.

Unfortunately I need to go now.

Luc, you want to take a look?

Chris

==========================================

extern char *strcpy (char *__dest, const char *__src);

static void test_menu_iteminfo( void )
{
int ansi = 1;
void *init, *string;
char stringA[0x80];
do {
if(ansi)
string=stringA;
if(ansi)
strcpy( string, init );
} while( !(ansi = !ansi) );
}

Re: Infinite loop with OOM while testing Sparse on Wine code

[Christopher Li]

On Tue, Jul 18, 2017 at 7:12 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> OK, I have shrink the test program into the following code.
> It can still reproduce the dead loop. It is related to simplify
> the phi source.

So I add a show_entry() in side each of the CSE loop.
Here is what I have so far. Commends in <==========

Chris

====================== The original
test_menu_iteminfo:
.L0:
        <entry-point>
        phisrc.32   %phi3(ansi) <- $1
        br          .L1

.L1:
        phi.32      %r1(ansi) <- %phi3(ansi), %phi4(ansi)
        cbr         %r1(ansi), .L4, .L5

.L4:
        symaddr.64  %r2 <- stringA
        cast.64     %r3 <- (64) %r2
        br          .L5

.L5:
        cbr         %r1(ansi), .L6, .L7

.L6:
        ptrcast.64  %r6 <- (64) %r3
        ptrcast.64  %r8 <- (64) VOID
        call.64     %r9 <- strcpy, %r6, %r8
        br          .L7

.L7:
        br          .L2

.L2:
        seteq.32    %r11 <- %r1(ansi), $0
        phisrc.32   %phi4(ansi) <- %r11
        cbr         %r11, .L3, .L1

.L3:
        ret

======================
test_menu_iteminfo:
.L0:
        <entry-point>
        phisrc.32   %phi3(ansi) <- $1
        br          .L1

.L1:
        phi.32      %r1(ansi) <- %phi3(ansi), %phi4(ansi)
        cbr         %r1(ansi), .L4, .L5

.L4:
   ### <======= r2 getsymaddr get simplify away
        cast.64     %r3 <- (64) stringA
        br          .L5

.L5:
        cbr         %r1(ansi), .L6, .L7

.L6:
        ptrcast.64  %r6 <- (64) %r3
        ptrcast.64  %r8 <- (64) VOID
        call.64     %r9 <- strcpy, %r6, %r8
        br          .L7

.L7:
        br          .L2

.L2:
        seteq.32    %r11 <- %r1(ansi), $0
        phisrc.32   %phi4(ansi) <- %r11
        cbr         %r1(ansi), .L1, .L3

.L3:
        ret
======================
test_menu_iteminfo:
.L0:
        <entry-point>
        phisrc.32   %phi3(ansi) <- $1
        br          .L1

.L1:
        phi.32      %r1(ansi) <- %phi3(ansi), %phi4(ansi)
        cbr         %r1(ansi), .L4, .L5

.L4:
        cast.64     %r3 <- (64) stringA
        br          .L5

.L5:
        cbr         %r1(ansi), .L6, .L2

.L6:
        ptrcast.64  %r6 <- (64) %r3
        ptrcast.64  %r8 <- (64) VOID
        call.64     %r9 <- strcpy, %r6, %r8
        br          .L2   <=============== L2 merge with L7

.L2:
        seteq.32    %r11 <- %r1(ansi), $0
        phisrc.32   %phi4(ansi) <- %r11
        cbr         %r1(ansi), .L1, .L3

.L3:
        ret
======================
test_menu_iteminfo:
.L0:
        <entry-point>
        br          .L4 <========= phisrc3 get optimize away. This seems wrong

.L1:
        phi.32      %r1(ansi) <- VOID, %phi4(ansi) <======= this seems wrong.
        cbr         %r1(ansi), .L4, .L5

.L4:
        cast.64     %r3 <- (64) stringA
        br          .L5

.L5:
        cbr         %r1(ansi), .L6, .L3

.L6:
        ptrcast.64  %r6 <- (64) %r3
        ptrcast.64  %r8 <- (64) VOID
        call.64     %r9 <- strcpy, %r6, %r8
        br          .L2

.L2:
        seteq.32    %r11 <- %r1(ansi), $0
        phisrc.32   %phi4(ansi) <- %r11
        cbr         %r1(ansi), .L4, .L3

.L3:
        ret
======================
test_menu_iteminfo:
.L0:
        <entry-point>
        br          .L4

.L4:
        cast.64     %r3 <- (64) stringA
        br          .L5

.L5:
        cbr         %r11, .L3, .L6

.L6:
        ptrcast.64  %r6 <- (64) %r3
        ptrcast.64  %r8 <- (64) VOID
        call.64     %r9 <- strcpy, %r6, %r8
        br          .L2

.L2:
        setne.32    %r11 <- %r11, $0 <====== this seems very wrong
        cbr         %r11, .L4, .L3

.L3:
        ret

Re: Infinite loop with OOM while testing Sparse on Wine code

[Christopher Li]

On Tue, Jul 18, 2017 at 8:07 PM, Christopher Li <sparse@chrisli.org> wrote:
> ======================
> test_menu_iteminfo:
> .L0:
>         <entry-point>
>         phisrc.32   %phi3(ansi) <- $1
>         br          .L1
>
> .L1:
>         phi.32      %r1(ansi) <- %phi3(ansi), %phi4(ansi)
>         cbr         %r1(ansi), .L4, .L5
>
> .L4:
>         cast.64     %r3 <- (64) stringA
>         br          .L5
>
> .L5:
>         cbr         %r1(ansi), .L6, .L2
>
> .L6:
>         ptrcast.64  %r6 <- (64) %r3
>         ptrcast.64  %r8 <- (64) VOID
>         call.64     %r9 <- strcpy, %r6, %r8
>         br          .L2   <=============== L2 merge with L7
>
> .L2:
>         seteq.32    %r11 <- %r1(ansi), $0
>         phisrc.32   %phi4(ansi) <- %r11
>         cbr         %r1(ansi), .L1, .L3
>
> .L3:
>         ret
> ======================
> test_menu_iteminfo:
> .L0:
>         <entry-point>
>         br          .L4 <========= phisrc3 get optimize away. This seems wrong

I see more what is going on there now.
Basically we have %phi3 = 1, a constant.
There for when control flow go from L0->L1, %r1 = %phi3 = 1.
It will go to L4 for sure.

So L0 modify to goto L4 directly. That is fine.

>
> .L1:
>         phi.32      %r1(ansi) <- VOID, %phi4(ansi) <======= this seems wrong.
>         cbr         %r1(ansi), .L4, .L5

phisrc3 has only one usage on L1. phisrc3 can be optimize away
and replace it with value 1. Showing VOID there is wrong.
it should be:

phi.32 %r1(ansi) <- 1, %phi4(ansi)

This phi instruction can't be deleted. Even though the control flow
has skip L1 and go to L4 directly. Makes L1 seems unreachable.
But the %r1(ansi) inside L1 is still used.

I think that is the nature of this bug.

Once sparse mistakenly remove %r1(ansi), it goes all crazy.
It result in the
 "setne.32    %r11 <- %r11, $0 "

which does not make sense at all.

I have revert the change cause this problem on sparse-next.

Wine compile should be able to complete now.

Luc, do you have time to take a look at this? Without your input,
RC5 will be released with commit  11b1a83b disabled.

Chris

Re: Infinite loop with OOM while testing Sparse on Wine code

[Christopher Li]

On Wed, Jul 19, 2017 at 9:26 AM, Christopher Li <sparse@chrisli.org> wrote:
> I have revert the change cause this problem on sparse-next.
>
> Wine compile should be able to complete now.

Yes, I have single CPU build the wine package to a complete.
The test sparse is on the sparse-next branch.

cgcc -o wineserver async.o atom.o change.o class.o clipboard.o
completion.o console.o debugger.o device.o \
  directory.o event.o fd.o file.o handle.o hook.o mach.o mailslot.o
main.o mapping.o mutex.o \
  named_pipe.o object.o process.o procfs.o ptrace.o queue.o region.o
registry.o request.o \
  semaphore.o serial.o signal.o snapshot.o sock.o symlink.o thread.o
timer.o token.o trace.o \
  unicode.o user.o window.o winstation.o -Wl,--rpath,\$ORIGIN/../libs/wine \
  ../libs/port/libwine_port.a -lwine -L../libs/wine
make[1]: Leaving directory '/home/xxx/git/oss/wine/server'
Wine build complete.

Chris

Re: Infinite loop with OOM while testing Sparse on Wine code

[Michael Stefaniuc]

Hello Chris,

On 07/19/2017 05:25 PM, Christopher Li wrote:
> On Wed, Jul 19, 2017 at 9:26 AM, Christopher Li <sparse@chrisli.org> wrote:
>> I have revert the change cause this problem on sparse-next.
>>
>> Wine compile should be able to complete now.
> 
> Yes, I have single CPU build the wine package to a complete.
> The test sparse is on the sparse-next branch.
make -j12 works fine too. Thanks for the fix.

Btw. I don't see any "crazy programmer" left for Wine.


bye
	michael

> 
> cgcc -o wineserver async.o atom.o change.o class.o clipboard.o
> completion.o console.o debugger.o device.o \
>   directory.o event.o fd.o file.o handle.o hook.o mach.o mailslot.o
> main.o mapping.o mutex.o \
>   named_pipe.o object.o process.o procfs.o ptrace.o queue.o region.o
> registry.o request.o \
>   semaphore.o serial.o signal.o snapshot.o sock.o symlink.o thread.o
> timer.o token.o trace.o \
>   unicode.o user.o window.o winstation.o -Wl,--rpath,\$ORIGIN/../libs/wine \
>   ../libs/port/libwine_port.a -lwine -L../libs/wine
> make[1]: Leaving directory '/home/xxx/git/oss/wine/server'
> Wine build complete.
> 
> Chris
> 

Re: Infinite loop with OOM while testing Sparse on Wine code

[Luc Van Oostenryck]

> Luc, do you have time to take a look at this? Without your input,
> RC5 will be released with commit  11b1a83b disabled.

I'm not yet fully back but I'll be able to look at it later, probably
tomorrow (it's already evening here).

-- Luc

Re: Infinite loop with OOM while testing Sparse on Wine code

[Christopher Li]

On Wed, Jul 19, 2017 at 4:43 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> I'm not yet fully back but I'll be able to look at it later, probably
> tomorrow (it's already evening here).

That is fine. How about we temporary disable that in the 0.5.1 release.
Re-enable it with some proper fix of the phi domination problem. e.g.
0.5.2.

Right now I feel a little bit uncomfortable with 11b1a83b. Already two bugs
trigger in the field. The previous fix d7985338 is not a proper fix any way.
I think the right thing to do is just release 0.5.1 with 11b1a83b disabled.
Turn on 11b1a83b in sparse-next and do more fixing there. Release
0.5.2 when it settle down with other new merges.

Chris

Re: Infinite loop with OOM while testing Sparse on Wine code

[Luc Van Oostenryck]

On Wed, Jul 19, 2017 at 02:16:54PM -0700, Christopher Li wrote:
> On Wed, Jul 19, 2017 at 4:43 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > I'm not yet fully back but I'll be able to look at it later, probably
> > tomorrow (it's already evening here).
> 
> That is fine. How about we temporary disable that in the 0.5.1 release.
> Re-enable it with some proper fix of the phi domination problem. e.g.
> 0.5.2.
> 
> Right now I feel a little bit uncomfortable with 11b1a83b. Already two bugs
> trigger in the field. The previous fix d7985338 is not a proper fix any way.
> I think the right thing to do is just release 0.5.1 with 11b1a83b disabled.
> Turn on 11b1a83b in sparse-next and do more fixing there. Release
> 0.5.2 when it settle down with other new merges.

I can't run all the validation I had done for -rc4 but I have no objections
about the revert (I'm pretty sure there will be some side-effects though).

-- Luc

Re: Infinite loop with OOM while testing Sparse on Wine code

[Christopher Li]

On Thu, Jul 20, 2017 at 6:44 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> I can't run all the validation I had done for -rc4 but I have no objections
> about the revert (I'm pretty sure there will be some side-effects though).
>

OK. That is good to know.  Do you have any chance to take a closer
look at this bug or still be away yet?

Chris

Re: Infinite loop with OOM while testing Sparse on Wine code

[Luc Van Oostenryck]

On Wed, Jul 19, 2017 at 09:26:29AM -0400, Christopher Li wrote:

OK I finally had the time to look at this closely.

> On Tue, Jul 18, 2017 at 8:07 PM, Christopher Li <sparse@chrisli.org> wrote:
> > ======================
> > test_menu_iteminfo:
> > .L0:
> >         <entry-point>
> >         phisrc.32   %phi3(ansi) <- $1
> >         br          .L1
> >
> > .L1:
> >         phi.32      %r1(ansi) <- %phi3(ansi), %phi4(ansi)
> >         cbr         %r1(ansi), .L4, .L5
> >
> > .L4:
> >         cast.64     %r3 <- (64) stringA
> >         br          .L5
> >
> > .L5:
> >         cbr         %r1(ansi), .L6, .L2
> >
> > .L6:
> >         ptrcast.64  %r6 <- (64) %r3
> >         ptrcast.64  %r8 <- (64) VOID
> >         call.64     %r9 <- strcpy, %r6, %r8
> >         br          .L2   <=============== L2 merge with L7
> >
> > .L2:
> >         seteq.32    %r11 <- %r1(ansi), $0
> >         phisrc.32   %phi4(ansi) <- %r11
> >         cbr         %r1(ansi), .L1, .L3
> >
> > .L3:
> >         ret
> > ======================
> > test_menu_iteminfo:
> > .L0:
> >         <entry-point>
> >         br          .L4 <========= phisrc3 get optimize away. This seems wrong
> 
> I see more what is going on there now.
> Basically we have %phi3 = 1, a constant.
> There for when control flow go from L0->L1, %r1 = %phi3 = 1.
> It will go to L4 for sure.
> 
> So L0 modify to goto L4 directly. That is fine.

Indeed, it's fine.
 
> >
> > .L1:
> >         phi.32      %r1(ansi) <- VOID, %phi4(ansi) <======= this seems wrong.
> >         cbr         %r1(ansi), .L4, .L5
> 
> phisrc3 has only one usage on L1. phisrc3 can be optimize away
> and replace it with value 1. Showing VOID there is wrong.

No it's fine. It's the way of displaying that the element have been removed.

> it should be:
> 
> phi.32 %r1(ansi) <- 1, %phi4(ansi)

No, not really.
L1 has now only a single parent, the phi-node is now a trivial one,
not really a join anymore.
An explicit way of displaying it should simply be:
	phi.32      %r1(ansi) <- %phi4(ansi)
 
Everything is correct until:
	test_menu_iteminfo:
	.L0:
		<entry-point>
		br          .L4
	.L1:
		phi.32      %r1(ansi) <- VOID, %phi4(ansi)
		cbr         %r1(ansi), .L4, .L5
	.L4:
		cast.64     %r3 <- (64) stringA
		br          .L5
	.L5:
		cbr         %r1(ansi), .L6, .L3
	.L6:
		ptrcast.64  %r6 <- (64) %r3
		ptrcast.64  %r8 <- (64) VOID			<== wrong but unrelated
		call.64     %r9 <- strcpy, %r6, %r8
		br          .L2
	.L2:
		seteq.32    %r11 <- %r1(ansi), $0
		phisrc.32   %phi4(ansi) <- %r11
		cbr         %r1(ansi), .L1, .L3
	.L3:
		ret

Then simplify_branch_branch() is called on L2 -> L1
and wrongly succeed giving:
	.L0:
	        <entry-point>
	        br          .L4
	.L1:
	        phi.32      %r1(ansi) <- VOID, %phi4(ansi)	<== now dead
	        cbr         %r1(ansi), .L4, .L5
	.L4:
	        cast.64     %r3 <- (64) stringA
	        br          .L5
	.L5:
	        cbr         %r1(ansi), .L6, .L3
	.L6:
	        ptrcast.64  %r6 <- (64) %r3
		ptrcast.64  %r8 <- (64) VOID			<== wrong but unrelated
	        call.64     %r9 <- strcpy, %r6, %r8
	        br          .L2
	.L2:
	        seteq.32    %r11 <- %r1(ansi), $0
	        phisrc.32   %phi4(ansi) <- %r11
	        cbr         %r1(ansi), .L4, .L3			<== bad change
	.L3:
	        ret

This will then trigger the wrong simplifications:
	%phi4 <- %r11
and
	%r1   <- %r11
giving finally:
	        setne.32    %r11 <- %r11, $0

As far as I can see, simplify_branch_branch() needs something
like the bb_defines_phi() I had to add to try_to_simplify_bb()
(basically it's bb_depends_on() which is not 'strong' enough).

I'll need a bit more time to see exactly what is needed, for
example if we can simply reuse bb_defines_phi() or not, and
to test all this.

At this point I don't think anymore that the revert is the most
appropriate thing to do.

-- Luc

Re: Infinite loop with OOM while testing Sparse on Wine code

[Christopher Li]

On Sat, Jul 29, 2017 at 10:39 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> No it's fine. It's the way of displaying that the element have been removed.
>
>> it should be:
>>
>> phi.32 %r1(ansi) <- 1, %phi4(ansi)
>
> No, not really.
> L1 has now only a single parent, the phi-node is now a trivial one,
> not really a join anymore.
> An explicit way of displaying it should simply be:
>         phi.32      %r1(ansi) <- %phi4(ansi)

OK, Great. It seems my decode attempt did not go far at all :(
Nice try.
.
>
> Everything is correct until:
>         test_menu_iteminfo:
>         .L0:
>                 <entry-point>
>                 br          .L4
>         .L1:
>                 phi.32      %r1(ansi) <- VOID, %phi4(ansi)
>                 cbr         %r1(ansi), .L4, .L5
>         .L4:
>                 cast.64     %r3 <- (64) stringA
>                 br          .L5
>         .L5:
>                 cbr         %r1(ansi), .L6, .L3
>         .L6:
>                 ptrcast.64  %r6 <- (64) %r3
>                 ptrcast.64  %r8 <- (64) VOID                    <== wrong but unrelated
>                 call.64     %r9 <- strcpy, %r6, %r8
>                 br          .L2
>         .L2:
>                 seteq.32    %r11 <- %r1(ansi), $0
>                 phisrc.32   %phi4(ansi) <- %r11
>                 cbr         %r1(ansi), .L1, .L3
>         .L3:
>                 ret
>
> Then simplify_branch_branch() is called on L2 -> L1
> and wrongly succeed giving:

My original thinking was .L1:
Ophi.32      %r1(ansi) <- VOID, %phi4(ansi)

feeding the .L2:
cbr         %r1(ansi), .L1, .L3

Got the wrong result so I suspect some thing was wrong with
%r1(ansi).  I admit I don't know what exactly simplify_branch_branch()
was doing there.

.L5: also have
cbr         %r1(ansi), .L6, .L3
I don't know why this one is fine.


>                 seteq.32    %r11 <- %r1(ansi), $0
>                 phisrc.32   %phi4(ansi) <- %r11
>                 cbr         %r1(ansi), .L4, .L3                 <== bad change
>         .L3:
>                 ret
>
> This will then trigger the wrong simplifications:
>         %phi4 <- %r11
> and
>         %r1   <- %r11
> giving finally:
>                 setne.32    %r11 <- %r11, $0
>
> As far as I can see, simplify_branch_branch() needs something
> like the bb_defines_phi() I had to add to try_to_simplify_bb()
> (basically it's bb_depends_on() which is not 'strong' enough).

Thanks you so much for the excellent diagnose.

> At this point I don't think anymore that the revert is the most
> appropriate thing to do.

That is what I am looking for. I want to find out if there is any
thing else like this on -rc4+.

Thanks again.

Chris

Re: Infinite loop with OOM while testing Sparse on Wine code

[Luc Van Oostenryck]

On Wed, Jul 19, 2017 at 09:26:29AM -0400, Christopher Li wrote:
> On Tue, Jul 18, 2017 at 8:07 PM, Christopher Li <sparse@chrisli.org> wrote:
> > ======================
> > test_menu_iteminfo:
> > .L0:
> >         <entry-point>
> >         phisrc.32   %phi3(ansi) <- $1
> >         br          .L1
> >
> > .L1:
> >         phi.32      %r1(ansi) <- %phi3(ansi), %phi4(ansi)
> >         cbr         %r1(ansi), .L4, .L5
> >
> > .L4:
> >         cast.64     %r3 <- (64) stringA
> >         br          .L5
> >
> > .L5:
> >         cbr         %r1(ansi), .L6, .L2
> >
> > .L6:
> >         ptrcast.64  %r6 <- (64) %r3
> >         ptrcast.64  %r8 <- (64) VOID
> >         call.64     %r9 <- strcpy, %r6, %r8
> >         br          .L2   <=============== L2 merge with L7
> >
> > .L2:
> >         seteq.32    %r11 <- %r1(ansi), $0
> >         phisrc.32   %phi4(ansi) <- %r11
> >         cbr         %r1(ansi), .L1, .L3
> >
> > .L3:
> >         ret
> > ======================
> > test_menu_iteminfo:
> > .L0:
> >         <entry-point>
> >         br          .L4 <========= phisrc3 get optimize away. This seems wrong
> 
> I see more what is going on there now.
> Basically we have %phi3 = 1, a constant.
> There for when control flow go from L0->L1, %r1 = %phi3 = 1.
> It will go to L4 for sure.
> 
> So L0 modify to goto L4 directly. That is fine.

My first analysis was wrong, the real problem is closer from here.

As far as I can currently see, the problem is related to the fact that:
- the joint was at L1 (who had 2 parents: L0 & L2)
- L4 wasn't a joint (the only parent was L1)
but after the first call to try_to_simplify_bb() it's not true anymore:
- L1 is not a trivial joint, this is fine
- L4 become a *real* joint (it can receive %r1 value from L1 or
  implicitely from L0). This is still fine for L4 but not anymore
  for its successor L5.
One way to see the problem is that the fix 852801f8b is not enough.
My first guess would be that the simplification made by try_to_simplify_bb()
is valid only if the controlling pseudo is local to the current BB.

Still looking at this.

-- Luc

[PATCH] fix: try_to_simplify_bb eargerness part 2

[Luc Van Oostenryck]

This is a temptative patch for the wine infinitive loop.
---
 flow.c | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/flow.c b/flow.c
index d8198ce8d..fe16d78d4 100644
--- a/flow.c
+++ b/flow.c
@@ -79,6 +79,19 @@ static int bb_depends_on(struct basic_block *target, struct basic_block *src)
 	return 0;
 }
 
+/*
+ * This is only to be used by try_to_simplify_bb().
+ * It really should be handled by bb_depends_on(), only
+ * that there is no liveness done on OP_PHI/OP_PHISRC.
+ * bb_depends_on() should return true if a phi
+ * is defined by src and used by target but it doesn't.
+ * So for now we add the explicit check.
+ */
+static int bb_uses_phi(struct basic_block *target, pseudo_t phi)
+{
+	return pseudo_in_list(target->needs, phi);
+}
+
 /*
  * This is only to be used by try_to_simplify_bb().
  * It really should be handled by bb_depends_on(), only
@@ -152,6 +165,8 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 		target = true ? second->bb_true : second->bb_false;
 		if (bb_depends_on(target, bb))
 			continue;
+		if (bb_uses_phi(target, first->target))
+			continue;
 		if (bb_defines_phi(bb, first))
 			continue;
 		changed |= rewrite_branch(source, &br->bb_true, bb, target);
-- 
2.13.2

Re: [PATCH] fix: try_to_simplify_bb eargerness part 2

[Christopher Li]

On Sat, Jul 29, 2017 at 7:58 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> This is a temptative patch for the wine infinitive loop.

First thing first, is this patch for this RC5 release or after the release ?

I have no objection for this patch. If you want me to apply it, I am
happy to.

That being said, I am still not very comfortable with this situation
even with the patch applied. The patch is definitely an improvement, it
stop at least one bug situation. I am not able to reason this patch to make
sure that is enough.

Yes, we observe from there is a case simplify a branch with bb has
some phi cause problem.

Does all phi cause problem? Or only phi has uninitialized value cause
problem? Will adding this check enough for all possible input source code?
There is a lot of unknown we can't answer. There is not a good theory behind
it we can reason and prove it one way or the other. That is what I feel
uncomfortable about, the unknown.

This "try and error" process is very scary. The more I read on this
subject, what is the recommended best practices in the academia,
The more I realized sparse has been doing a lot of stuff relate to optimization
wrong. The phi node placement as you point out is a big one, there are others.
That is my general observation, not reason to against you patch though.
That is way beyond the scope of this patch any way.

I will apply it. My feel that it is still work in progress, not perfect yet.

Chris

Re: [PATCH] fix: try_to_simplify_bb eargerness part 2

[Luc Van Oostenryck]

On Sun, Jul 30, 2017 at 5:38 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Sat, Jul 29, 2017 at 7:58 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> This is a temptative patch for the wine infinitive loop.
>
> First thing first, is this patch for this RC5 release or after the release ?

It's was draft/temptative patch for -rc5.

> I have no objection for this patch. If you want me to apply it, I am
> happy to.

Please don't, I'm still working on it.

> That being said, I am still not very comfortable with this situation
> even with the patch applied. The patch is definitely an improvement, it
> stop at least one bug situation. I am not able to reason this patch to make
> sure that is enough.

I don't like at all this situation also.
The problem is quite complex and deep.

This patch seems to solve the problem and (at least something
similar) is needed but my first analysis was also right and thus something
similar is still needed for simplify_branch_branch().

Also, the revert would not be a good solution because it would
only avoid to trigger the problem on this input but won't solve anything.

> Yes, we observe from there is a case simplify a branch with bb has
> some phi cause problem.
>
> Does all phi cause problem? Or only phi has uninitialized value cause
> problem?

The problem is unrelated to undefined *var* but these wrong branch
simplification bypass some pseudo definition which, in a way,
become undefined on some paths which then create the problem
you saw with setne %r11, %r11, 0

> Will adding this check enough for all possible input source code?
> There is a lot of unknown we can't answer. There is not a good theory behind
> it we can reason and prove it one way or the other. That is what I feel
> uncomfortable about, the unknown.

You're not alone.

> This "try and error" process is very scary.

Well, I don't see things exactly the same.
For me, there is a code base, there are bugs in the code,
we discover the bugs and we fix them.

But yes, this is quite annoying, especially with try_to_simplify_bb()
on which I already spend many hours on it.

> The more I realized sparse has been doing a lot of stuff relate to optimization
> wrong. The phi node placement as you point out is a big one, there are others.
> That is my general observation, not reason to against you patch though.
> That is way beyond the scope of this patch any way.

The two big things that need to be fixed regarding optimization are:
- the placement of the phi-node
- associate each phi's source to the phi-node's parent
  (Linus may object on this, he at least objected 10 years ago)
The last point will then allow tfix some issues I'm aware of regarding
liveness and make things much easier when manipulating phis.

-- Luc

Re: [PATCH] fix: try_to_simplify_bb eargerness part 2

[Christopher Li]

On Sun, Jul 30, 2017 at 12:04 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> It's was draft/temptative patch for -rc5.
>
Thanks for the clarification.

>
> Please don't, I'm still working on it.

Of course, I don't apply it now. I will wait for your git pull to apply.

> I don't like at all this situation also.
> The problem is quite complex and deep.
>
> This patch seems to solve the problem and (at least something
> similar) is needed but my first analysis was also right and thus something
> similar is still needed for simplify_branch_branch().
>
> Also, the revert would not be a good solution because it would
> only avoid to trigger the problem on this input but won't solve anything.

I totally agree. The revert is temporary bandage to buy us more time to fix
the real problem. That is well understood. We still have the question to answer
will RC5 and follow up official release have the revert or not.

Currently I am leaning towards keep the revert for this release but I can
be convinced otherwise.

> The problem is unrelated to undefined *var* but these wrong branch
> simplification bypass some pseudo definition which, in a way,
> become undefined on some paths which then create the problem
> you saw with setne %r11, %r11, 0

Yes, we all know "setne %r11, %r11, 0" is the big offender.
We just don't have a clear picture why it get there.

> Well, I don't see things exactly the same.
> For me, there is a code base, there are bugs in the code,
> we discover the bugs and we fix them.

Sorry that came out wrong, I mean to said there is some more
deeper issue.

> But yes, this is quite annoying, especially with try_to_simplify_bb()
> on which I already spend many hours on it.

I also spend many hours on it haven't able to crack it yet. The best I can
do is make it simplify the original huge test input as a much smaller
test case.

"Help me, Obi-Wan Kenobi. You're my only hope."


> The two big things that need to be fixed regarding optimization are:
> - the placement of the phi-node
> - associate each phi's source to the phi-node's parent
>   (Linus may object on this, he at least objected 10 years ago)

We will revisit this after the release. I have my wish list as well.

Right now let's solve this bug first. At least come to a decision
what to do with it on the upcoming release.

Chris

Re: Infinite loop with OOM while testing Sparse on Wine code

[Luc Van Oostenryck]

On Sun, Jul 30, 2017 at 01:38:07AM +0200, Luc Van Oostenryck wrote:
> Still looking at this.

I just sent a patch.
At first sight it seems to be correct but it will need more testing.
I'll do that tomorrow as it is already quite late here.

-- Luc