linearize bug?

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

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

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

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

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

index 2a1574531993..2aabb65785f0 100644
@@ -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.
 	 */

index f2034ce93572..06128ed5b5ee 100644
@@ -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;
 	}

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

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

index 30e0c9d..9e4b6a4 100644
@@ -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;

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

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

index 2a1574531993..2aabb65785f0 100644
@@ -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.
 	 */

index f2034ce93572..4b4916340859 100644
@@ -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;
 	}

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

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

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/

[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

The attached patch solves the dangling PHI nodes and does not seem to break anything at first glance. It is probably not the most efficient solution, but it might at least show where to look for the problem.

Kamil

From 7024fcdfba9fce20569f86e2a279c76cb94cbfd8 Mon Sep 17 00:00:00 2001
From: Kamil Dudka <[email protected]>
Date: Sun, 28 Aug 2011 01:29:13 +0200
Subject: [PATCH] cse: update PHI users when throwing away an instruction

---
 cse.c |   13 +++++++++++++
 1 files changed, 13 insertions(+), 0 deletions(-)

index 2a15745..1b63c0e 100644
@@ -250,6 +250,19 @@ static void sort_instruction_list(struct instruction_list **list)
 static struct instruction * cse_one_instruction(struct instruction *insn, struct instruction *def)
 {
 	convert_instruction_target(insn, def->target);
+
+	if (insn->opcode == OP_PHI) {
+		/* Remove the instruction from PHI users */
+		pseudo_t phi;
+		FOR_EACH_PTR(insn->phi_list, phi) {
+			struct pseudo_user *pu;
+			FOR_EACH_PTR(phi->users, pu) {
+				if (pu->insn == insn)
+					DELETE_CURRENT_PTR(pu);
+			} END_FOR_EACH_PTR(pu);
+		} END_FOR_EACH_PTR(phi);
+	}
+
 	insn->opcode = OP_NOP;
 	insn->bb = NULL;
 	repeat_phase |= REPEAT_CSE;

1.7.6

Hmm. From a quick look, looks fine to me. And checks the kernel, and does indeed get rid of the extraneous phi nodes in the test-case.

Ack.

Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Applied.

Chris
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

I applied both patches to sparse-llvm.git. Jeff, do they cure all loop related issues?

Pekka
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

They look promising... Currently loops are stuck due to issues unrelated to core sparse: OP_PHI does not show successor phi's due to ->priv==NULL. Loops definitely will not work without both predecessors and successors both having a correct ->priv pointing to LLVM data.

Jeff

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

@@ -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