linearize bug?

linearize bug?

[Jeff Garzik]

Given the following C code:
#include <stdlib.h>

int foo(void)
{
         int i;

         i = 42;
         i += rand();

         return i;
}

test-linearize seems to give me the following output, which indicates 
that pseudo %r1 is "dead" immediately before it is used:

foo:
.L0x2b52beecd010:
         <entry-point>
         call.32     %r1 <- rand
         dead        %r1
         add.32      %r4 <- %r1, $42
         dead        %r4
         ret.32      %r4

Am I just confused about the meaning of "dead"?   :)

	Jeff

Re: linearize bug?

[Linus Torvalds]

On Sat, 11 Nov 2006, Jeff Garzik wrote:
> Given the following C code:
>
> #include <stdlib.h>
> 
> int foo(void)
> {
>         int i;
> 
>         i = 42;
>         i += rand();
> 
>         return i;
> }
> 
> test-linearize seems to give me the following output, which indicates that
> pseudo %r1 is "dead" immediately before it is used:

That is normal.

"dead X" means that X is dead after the _next_ (non-deathnote) 
instruction.

So every single death-note should always show up _before_ an instruction 
that uses that register, or something is wrong.

This is actually very useful. It means that for a code generator that 
keeps track of hardware registers, it knows that a register content can be 
re-used as the _destination_ of a code sequence when it sees the 
death-note.

So for example:

> foo:
> .L0x2b52beecd010:
>         <entry-point>
>         call.32     %r1 <- rand
>         dead        %r1
>         add.32      %r4 <- %r1, $42
>         dead        %r4
>         ret.32      %r4

Here, the compiler back-end might, for example, look at

	call.32 %r1 <- rand

and decide to use register %eax for %r1.

Now, the "dead %r1" that follows will tell the back-end that the value in 
%r1 will be used _only_ by the following instruction, and never again, so 
when it sees the

	add.32 %r4 <- r1, $42

the back-end can trivially decide to _reuse_ %eax for %r4 too, and 
generate just a simple

	addl $42,%eax

for that instruction, without worrying at all about the fact that it 
over-writes the register that contains %r1.

The same thing foes for the next two instructions: "dead %r4" means that 
r4 (which we hold in %eax) will be dead after the next instruction (the 
return), so again it knows that it can re-use %eax for the result. Of 
course, for a return that's trivial anyway, but..

My "example" back-end actually does all this. It's buggy as hell, but try

	./example file.c

on your input file, and at least I get:

	.globl foo
	foo:
	        call rand               # generate_call
	        add.32 $42,%eax         # do_binop
	        ret             # generate_ret

which actually is correct (and re-uses %eax all the time). It even gets a 
few more complicated cases right, but there are certainly trivial ways to 
confuse it too (it doesn't really do any stack slot allocation, so 
anything that generates a spill - which it _will_ try to do - will 
actually generate completely broken code that just overwrites the stack).

			Linus

linearize bug?

[Jeff Garzik]

While trying to implement loops in LLVM, the following testcase appears 
to have some strange behavior:

int foo(int x)
{
	int i;

	for (i = 0; i < 10; i++)
		x += 42;
	
	return x;
}

when run through test-linearize produces

foo.c:1:5: warning: symbol 'foo' was not declared. Should it be static?
foo:
.L0x7f4c095ae010:
	<entry-point>
	phisrc.32   %phi2(x) <- %arg1
	phisrc.32   %phi4(x) <- %arg1
	phisrc.32   %phi7(i) <- $0
	br          .L0x7f4c095ae150

.L0x7f4c095ae150:
	phi.32      %r1(i) <- %phi7(i), %phi8(i)
	setlt.32    %r2 <- %r1(i), $10
	br          %r2, .L0x7f4c095ae060, .L0x7f4c095ae100

.L0x7f4c095ae060:
	add.32      %r5 <- %r9, $42
	phisrc.32   %phi3(x) <- %r5
	phisrc.32   %phi5(x) <- %r5
	add.32      %r8 <- %r1(i), $1
	phisrc.32   %phi8(i) <- %r8
	br          .L0x7f4c095ae150

.L0x7f4c095ae100:
	phi.32      %r9 <- %phi2(x), %phi3(x)
	ret.32      %r9

So...  WTF did %r9 come from, in the third basic block?

Re: linearize bug?

[Kamil Dudka]

On Saturday 27 August 2011 08:29:12 Jeff Garzik wrote:
> While trying to implement loops in LLVM, the following testcase appears
> to have some strange behavior:
>
> int foo(int x)
> {
> 	int i;
>
> 	for (i = 0; i < 10; i++)
> 		x += 42;
>
> 	return x;
> }
>
> when run through test-linearize produces
>
> foo.c:1:5: warning: symbol 'foo' was not declared. Should it be static?
> foo:
> .L0x7f4c095ae010:
> 	<entry-point>
> 	phisrc.32   %phi2(x) <- %arg1
> 	phisrc.32   %phi4(x) <- %arg1
> 	phisrc.32   %phi7(i) <- $0
> 	br          .L0x7f4c095ae150
>
> .L0x7f4c095ae150:
> 	phi.32      %r1(i) <- %phi7(i), %phi8(i)
> 	setlt.32    %r2 <- %r1(i), $10
> 	br          %r2, .L0x7f4c095ae060, .L0x7f4c095ae100
>
> .L0x7f4c095ae060:
> 	add.32      %r5 <- %r9, $42
> 	phisrc.32   %phi3(x) <- %r5
> 	phisrc.32   %phi5(x) <- %r5
> 	add.32      %r8 <- %r1(i), $1
> 	phisrc.32   %phi8(i) <- %r8
> 	br          .L0x7f4c095ae150
>
> .L0x7f4c095ae100:
> 	phi.32      %r9 <- %phi2(x), %phi3(x)
> 	ret.32      %r9
>
> So...  WTF did %r9 come from, in the third basic block?

Two years ago I proposed a patch that I believe would solve your problem:

https://patchwork.kernel.org/patch/40307/

Kamil

Re: linearize bug?

[Linus Torvalds]

On Sat, Aug 27, 2011 at 4:34 AM, Kamil Dudka <kdudka@redhat.com> wrote:
>
> Two years ago I proposed a patch that I believe would solve your problem:
>
> https://patchwork.kernel.org/patch/40307/

Ack.

The sparse output still looks like sh*t, because when linearizing
loops sparse doesn't treat the first conditional specially, so instead
of noticing that "0 < 10" and getting rid of the first jump, it will
generate the loop with the (general) conditional at the end, which
will then result in lots of phi-nodes etc.

I guess some trivial loop optimizations might be a good idea. But
Kamil's patch looks correct, and the PHI-node cross-bb optimization
does look bogus.

                              Linus

Re: linearize bug?

[Jeff Garzik]

On 08/27/2011 11:29 AM, Linus Torvalds wrote:
> On Sat, Aug 27, 2011 at 4:34 AM, Kamil Dudka<kdudka@redhat.com>  wrote:
>>
>> Two years ago I proposed a patch that I believe would solve your problem:
>>
>> https://patchwork.kernel.org/patch/40307/
>
> Ack.
>
> The sparse output still looks like sh*t, because when linearizing
> loops sparse doesn't treat the first conditional specially, so instead
> of noticing that "0<  10" and getting rid of the first jump, it will
> generate the loop with the (general) conditional at the end, which
> will then result in lots of phi-nodes etc.
>
> I guess some trivial loop optimizations might be a good idea. But
> Kamil's patch looks correct, and the PHI-node cross-bb optimization
> does look bogus.


On our point of view, we probably prefer to simply turn off as many 
transformations as possible.  They just waste time, when an optimizing 
LLVM backend is going to perform the same transformations anyway.

	Jeff

Re: linearize bug?

[Linus Torvalds]

[-- Attachment #1: Type: text/plain, Size: 2006 bytes --]

On Sat, Aug 27, 2011 at 8:37 AM, Jeff Garzik <jeff@garzik.org> wrote:
>
> On our point of view, we probably prefer to simply turn off as many
> transformations as possible.  They just waste time, when an optimizing LLVM
> backend is going to perform the same transformations anyway.

I disagree - mainly because I don't think we're interested in the back
end, are we?

If we were doing LLVM hacking, then I'd agree. But as it is, we're
supposed to improve sparse, not LLVM, so we should make sure that the
_sparse_ output makes sense, and LLVM is just a code generator, no?

Also, I suspect LLVM has an easier time of it if we were to generate
straightforward code rather than the extra basic blocks we do now.

So with the attached patch, your test-case turns into

  t.c:1:5: warning: symbol 'foo' was not declared. Should it be static?
  foo:
  .L0x7fc91affa010:
	<entry-point>
	phisrc.32   %phi2(x) <- %arg1
	phisrc.32   %phi4(x) <- %arg1
	phisrc.32   %phi6(i) <- $0
	br          .L0x7fc91affa058

  .L0x7fc91affa058:
	phi.32      %r3 <- %phi4(x), %phi5(x)
	add.32      %r5 <- %r3, $42
	phisrc.32   %phi3(x) <- %r5
	phisrc.32   %phi5(x) <- %r5
	phi.32      %r7 <- %phi6(i), %phi7(i)
	add.32      %r8 <- %r7, $1
	setlt.32    %r10 <- %r8, $10
	phisrc.32   %phi7(i) <- %r8
	br          %r10, .L0x7fc91affa058, .L0x7fc91affa130

  .L0x7fc91affa130:
	ret.32      %r3

which looks messy due to all the phi's (that we don't combine - the
patch includes Kamil's "don't combine" thing), but looks simpler
otherwise. Now sparse has optimized away the entry conditional (simply
because it got linearized separately and then the optimization was a
trivial constant one).

phi2/phi3 are both dead, but theor 'phisrc' instructions haven't been
killed. Ugly.

The attached patch is ENTIRELY UNTESTED. The only thing I tested it on
is your test-case. Running "make test" requires stuff that I don't
even have installed, and I'm lazy ;^o

                   Linus

[-- Attachment #2: patch.diff --]
[-- Type: text/x-patch, Size: 2017 bytes --]

 cse.c       |    7 -------
 linearize.c |   14 +++++---------
 2 files changed, 5 insertions(+), 16 deletions(-)

diff --git a/cse.c b/cse.c
index 2a1574531993..2aabb65785f0 100644
--- a/cse.c
+++ b/cse.c
@@ -317,13 +317,6 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction
 	b2 = i2->bb;
 
 	/*
-	 * PHI-nodes do not care where they are - the only thing that matters
-	 * are the PHI _sources_.
-	 */
-	if (i1->opcode == OP_PHI)
-		return cse_one_instruction(i1, i2);
-
-	/*
 	 * Currently we only handle the uninteresting degenerate case where
 	 * the CSE is inside one basic-block.
 	 */
diff --git a/linearize.c b/linearize.c
index f2034ce93572..06128ed5b5ee 100644
--- a/linearize.c
+++ b/linearize.c
@@ -2060,16 +2060,10 @@ pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
 		concat_symbol_list(stmt->iterator_syms, &ep->syms);
 		linearize_statement(ep, pre_statement);
 
- 		loop_body = loop_top = alloc_basic_block(ep, stmt->pos);
+		loop_body = alloc_basic_block(ep, stmt->pos);
  		loop_continue = alloc_basic_block(ep, stmt->pos);
  		loop_end = alloc_basic_block(ep, stmt->pos);
  
-		/* An empty post-condition means that it's the same as the pre-condition */
-		if (!post_condition) {
-			loop_top = alloc_basic_block(ep, stmt->pos);
-			set_activeblock(ep, loop_top);
-		}
-
 		if (pre_condition) 
  			linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
 
@@ -2082,10 +2076,12 @@ pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
 
 		set_activeblock(ep, loop_continue);
 		linearize_statement(ep, post_statement);
+
+		/* No post-condition means that it's the same as the pre-condition */
 		if (!post_condition)
-			add_goto(ep, loop_top);
+			linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
 		else
- 			linearize_cond_branch(ep, post_condition, loop_top, loop_end);
+			linearize_cond_branch(ep, post_condition, loop_body, loop_end);
 		set_activeblock(ep, loop_end);
 		break;
 	}

Re: linearize bug?

[Kamil Dudka]

[-- Attachment #1: Type: text/plain, Size: 660 bytes --]

On Saturday 27 August 2011 17:53:23 Linus Torvalds wrote:
> The attached patch is ENTIRELY UNTESTED. The only thing I tested it on
> is your test-case. Running "make test" requires stuff that I don't
> even have installed, and I'm lazy ;^o

It seems to break loops with no conditions.  The following piece of code:

#include <stdio.h>

int main()
{
    for(;;)
        printf("");
}

... translates into:

main:
.L0x7f233ed67010:
        <entry-point>
        call.32     %r2 <- printf, ""
        ret.32

... which is obviously wrong.  I am not sure if handling that special case 
separately (as done in the attached patch) is a correct way to fix it.

Kamil

[-- Attachment #2: follow-up.diff --]
[-- Type: text/x-diff, Size: 1314 bytes --]

 linearize.c |   11 +++++++----
 1 files changed, 7 insertions(+), 4 deletions(-)

diff --git a/linearize.c b/linearize.c
index 30e0c9d..9e4b6a4 100644
--- a/linearize.c
+++ b/linearize.c
@@ -2055,7 +2055,7 @@ pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
 		struct statement  *statement = stmt->iterator_statement;
 		struct statement  *post_statement = stmt->iterator_post_statement;
 		struct expression *post_condition = stmt->iterator_post_condition;
-		struct basic_block *loop_top, *loop_body, *loop_continue, *loop_end;
+		struct basic_block *loop_body, *loop_continue, *loop_end;
 
 		concat_symbol_list(stmt->iterator_syms, &ep->syms);
 		linearize_statement(ep, pre_statement);
@@ -2078,9 +2078,12 @@ pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
 		linearize_statement(ep, post_statement);
 
 		/* No post-condition means that it's the same as the pre-condition */
-		if (!post_condition)
-			linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
-		else
+		if (!post_condition) {
+			if (pre_condition)
+				linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
+			else
+				add_goto(ep, loop_body);
+		} else
 			linearize_cond_branch(ep, post_condition, loop_body, loop_end);
 		set_activeblock(ep, loop_end);
 		break;

Re: linearize bug?

[Linus Torvalds]

[-- Attachment #1: Type: text/plain, Size: 431 bytes --]

On Sat, Aug 27, 2011 at 9:54 AM, Kamil Dudka <kdudka@redhat.com> wrote:
>
> It seems to break loops with no conditions.  The following piece of code:

Yeah, good catch.

I think it would be nicer to just teach "linearize_cond_branch()" that
an empty condition is the same thing as an unconditional branch, that
seems to be the most straightforward approach.

But your patch is fine too.

                        Linus

[-- Attachment #2: patch.diff --]
[-- Type: text/x-patch, Size: 2690 bytes --]

 cse.c       |    7 -------
 linearize.c |   23 ++++++++++++-----------
 2 files changed, 12 insertions(+), 18 deletions(-)

diff --git a/cse.c b/cse.c
index 2a1574531993..2aabb65785f0 100644
--- a/cse.c
+++ b/cse.c
@@ -317,13 +317,6 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction
 	b2 = i2->bb;
 
 	/*
-	 * PHI-nodes do not care where they are - the only thing that matters
-	 * are the PHI _sources_.
-	 */
-	if (i1->opcode == OP_PHI)
-		return cse_one_instruction(i1, i2);
-
-	/*
 	 * Currently we only handle the uninteresting degenerate case where
 	 * the CSE is inside one basic-block.
 	 */
diff --git a/linearize.c b/linearize.c
index f2034ce93572..4b4916340859 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1419,9 +1419,14 @@ pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, s
 {
 	pseudo_t cond;
 
-	if (!expr || !bb_reachable(ep->active))
+	if (!bb_reachable(ep->active))
 		return VOID;
 
+	if (!expr) {
+		add_goto(ep, bb_true);
+		return VOID;
+	}
+
 	switch (expr->type) {
 
 	case EXPR_STRING:
@@ -2055,21 +2060,15 @@ pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
 		struct statement  *statement = stmt->iterator_statement;
 		struct statement  *post_statement = stmt->iterator_post_statement;
 		struct expression *post_condition = stmt->iterator_post_condition;
-		struct basic_block *loop_top, *loop_body, *loop_continue, *loop_end;
+		struct basic_block *loop_body, *loop_continue, *loop_end;
 
 		concat_symbol_list(stmt->iterator_syms, &ep->syms);
 		linearize_statement(ep, pre_statement);
 
- 		loop_body = loop_top = alloc_basic_block(ep, stmt->pos);
+		loop_body = alloc_basic_block(ep, stmt->pos);
  		loop_continue = alloc_basic_block(ep, stmt->pos);
  		loop_end = alloc_basic_block(ep, stmt->pos);
  
-		/* An empty post-condition means that it's the same as the pre-condition */
-		if (!post_condition) {
-			loop_top = alloc_basic_block(ep, stmt->pos);
-			set_activeblock(ep, loop_top);
-		}
-
 		if (pre_condition) 
  			linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
 
@@ -2082,10 +2081,12 @@ pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
 
 		set_activeblock(ep, loop_continue);
 		linearize_statement(ep, post_statement);
+
+		/* No post-condition means that it's the same as the pre-condition */
 		if (!post_condition)
-			add_goto(ep, loop_top);
+			linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
 		else
- 			linearize_cond_branch(ep, post_condition, loop_top, loop_end);
+			linearize_cond_branch(ep, post_condition, loop_body, loop_end);
 		set_activeblock(ep, loop_end);
 		break;
 	}

Re: linearize bug?

[Linus Torvalds]

On Sat, Aug 27, 2011 at 10:13 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> But your patch is fine too.

Hmm. There's badness going on with that patch: I can't check the
kernel source tree, I get a

  CHECK   arch/x86/kernel/process_64.c
  sparse: simplify.c:82: if_convert_phi: Assertion `br->cond' failed.

so clearly something is screwed up. It happens with your version too,
it seems to have gotten triggered by the loop rewriting change.

Which *should* have been semantically no difference what-so-ever. But
it's been so long, I can't recall all the rules. It may be that trying
to linearize the same expression twice (once for the entry condition,
once for the loop end) was just something invalid.

So the patch is just broken. Never mind.

                        Linus

Re: linearize bug?

[Linus Torvalds]

On Sat, Aug 27, 2011 at 10:27 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> Which *should* have been semantically no difference what-so-ever. But
> it's been so long, I can't recall all the rules. It may be that trying
> to linearize the same expression twice (once for the entry condition,
> once for the loop end) was just something invalid.
>
> So the patch is just broken. Never mind.

Yes indeed.

The reason we cannot linearize the same expression twice is that we
associate some state with the expression. For example, label symbols
in statement expressions are associated with the basic block they get
linearized to. If you linearize the same expression twice, that kind
of thing will completely screw things up..

So throw away my patch to linearize.c. It was fundamentally broken. I
suspect we don't want to duplicate the conditional for anything but
simple expressions anyway, so if I get a big spurt of energy, I might
add some logic to say "if it's a really simple conditional, then
duplicate it", since then we won't have issues with statement
expressions etc anyway.

                    Linus

Re: linearize bug?

[Jeff Garzik]

On 08/27/2011 11:53 AM, Linus Torvalds wrote:
> On Sat, Aug 27, 2011 at 8:37 AM, Jeff Garzik<jeff@garzik.org>  wrote:
>>
>> On our point of view, we probably prefer to simply turn off as many
>> transformations as possible.  They just waste time, when an optimizing LLVM
>> backend is going to perform the same transformations anyway.
>
> I disagree - mainly because I don't think we're interested in the back
> end, are we?
>
> If we were doing LLVM hacking, then I'd agree. But as it is, we're
> supposed to improve sparse, not LLVM, so we should make sure that the
> _sparse_ output makes sense, and LLVM is just a code generator, no?

No idea Pekka's interest...

In general, my own decade-long goal has been to be able to play with a 
kernel compiler other than gcc.  That's why I wrote compile-i386 so long 
ago, that's why the kernel got a bunch of LLVM-related bug fixes and C 
cleanups, that's why I wrote the original sparse LLVM backend[1], and 
why I'm working on Pekka's now.

So I'm definitely more interested in the backend side of things, and 
tend to see simplifications and optimizations performed on the 
linearized form as wasted work.  sparse makes a great C front-end to a 
compiler.

Obviously that's not the only PoV or use case of sparse, and is arguably 
a crazy, unattainable goal in general... :)

	Jeff


[1] https://patchwork.kernel.org/patch/19923/

Re: linearize bug?

[Pekka Enberg]

On Sat, Aug 27, 2011 at 11:03 PM, Jeff Garzik <jeff@garzik.org> wrote:
>> I disagree - mainly because I don't think we're interested in the back
>> end, are we?
>>
>> If we were doing LLVM hacking, then I'd agree. But as it is, we're
>> supposed to improve sparse, not LLVM, so we should make sure that the
>> _sparse_ output makes sense, and LLVM is just a code generator, no?
>
> No idea Pekka's interest...
>
> In general, my own decade-long goal has been to be able to play with a
> kernel compiler other than gcc.

[snip]

I'm also interested in hopefully being able to eventually compile the
kernel with sparse.

I'm not that interested in LLVM and really only picked it because it
seems to be simplest solution for now. I do agree with Linus that we
should improve sparse rather than rely on LLVM for everything.

                        Pekka

Re: linearize bug?

[Jeff Garzik]

------------------------------------------
--- a/cse.c
+++ b/cse.c
@@ -316,12 +316,14 @@ static struct instruction * try_to_cse(struct 
entrypoint *
         b1 = i1->bb;
         b2 = i2->bb;

+#if 0
         /*
          * PHI-nodes do not care where they are - the only thing that 
matters
          * are the PHI _sources_.
          */
         if (i1->opcode == OP_PHI)
                 return cse_one_instruction(i1, i2);
+#endif

--------------------------------------


That patch definitely gets much farther along in terms of handling loops.

	Jeff