fix linearization of nested logical expr

The linearization of nested logical expressions is not correct
regarding the phi-nodes and their phi-sources. For example, code like:
	extern int a(void); int b(void); int c(void);

	static int foo(void)
	{
		return (a() && b()) && c();
	}

gives (optimized) IR like:
	foo:
		phisrc.32   %phi1 <- $0
		call.32     %r1 <- a
		cbr         %r1, .L4, .L3
	.L4:
		call.32     %r3 <- b
		cbr         %r3, .L2, .L3
	.L2:
		call.32     %r5 <- c
		setne.32    %r7 <- %r5, $0
		phisrc.32   %phi2 <- %r7
		br          .L3
	.L3:
		phi.32      %r8 <- %phi2, %phi1
		ret.32      %r8

The problem can already be seen by the fact that the phi-node in L3
has 2 operands while L3 has 3 parents. There is no phi-value for L4.

The code is OK for non-nested logical expressions: linearize_cond_branch()
takes the sucess/failure BB as argument, generate the code for those
branches and there is a phi-node for each of them. However, with
nested logical expressions, one of the BB will be shared between
the inner and the outer expression. The phisrc will 'cover' one of
the BB but only one of them.

The solution is to add the phi-sources not before but after and add
one for each of the parent BB. This way, it can be guaranteed that
each parent BB has its phisrc, whatever the complexity of the sub-
expressions. With this change, the generated IR becomes:

	foo:
		call.32     %r2 <- a
		phisrc.32   %phi1 <- $0
		cbr         %r2, .L4, .L3
	.L4:
		call.32     %r4 <- b
		phisrc.32   %phi2 <- $0
		cbr         %r4, .L2, .L3
	.L2:
		call.32     %r6 <- c
		setne.32    %r8 <- %r6, $0
		phisrc.32   %phi3 <- %r8
		br          .L3
	.L3:
		phi.32      %r1 <- %phi1, %phi2, %phi3
		ret.32      %r1

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>

5 files changed, 121 insertions, 111 deletions

diff --git a/linearize.c b/linearize.c
index bdcb92c1..2c8b78c0 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1697,41 +1697,54 @@ static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *
 	return add_join_conditional(ep, expr, phi1, phi2);
 }
 
+static void insert_phis(struct basic_block *bb, pseudo_t src, struct symbol *ctype,
+	struct instruction *node)
+{
+	struct basic_block *parent;
+
+	FOR_EACH_PTR(bb->parents, parent) {
+		struct instruction *br = delete_last_instruction(&parent->insns);
+		pseudo_t phi = alloc_phi(parent, src, ctype);
+		add_instruction(&parent->insns, br);
+		use_pseudo(node, phi, add_pseudo(&node->phi_list, phi));
+	} END_FOR_EACH_PTR(parent);
+}
+
 static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr)
 {
+	struct symbol *ctype = expr->ctype;
 	struct basic_block *other, *merge;
-	pseudo_t phi1, phi2;
+	struct instruction *node;
+	pseudo_t src1, src2, phi2;
 
 	if (!ep->active || !expr->left || !expr->right)
 		return VOID;
 
 	other = alloc_basic_block(ep, expr->right->pos);
 	merge = alloc_basic_block(ep, expr->pos);
+	node = alloc_phi_node(merge, ctype, NULL);
 
+	// LHS and its shortcut
 	if (expr->op == SPECIAL_LOGICAL_OR) {
-		pseudo_t src2;
-
-		phi1 = alloc_phi(ep->active, value_pseudo(1), expr->ctype);
 		linearize_cond_branch(ep, expr->left, merge, other);
-
-		set_activeblock(ep, other);
-		src2 = linearize_expression_to_bool(ep, expr->right);
-		src2 = cast_pseudo(ep, src2, &bool_ctype, expr->ctype);
-		phi2 = alloc_phi(ep->active, src2, expr->ctype);
+		src1 = value_pseudo(1);
 	} else {
-		pseudo_t src1;
-
-		phi1 = alloc_phi(ep->active, value_pseudo(0), expr->ctype);
 		linearize_cond_branch(ep, expr->left, other, merge);
-
-		set_activeblock(ep, other);
-		src1 = linearize_expression_to_bool(ep, expr->right);
-		src1 = cast_pseudo(ep, src1, &bool_ctype, expr->ctype);
-		phi2 = alloc_phi(ep->active, src1, expr->ctype);
+		src1 = value_pseudo(0);
 	}
+	insert_phis(merge, src1, ctype, node);
 
+	// RHS
+	set_activeblock(ep, other);
+	src2 = linearize_expression_to_bool(ep, expr->right);
+	src2 = cast_pseudo(ep, src2, &bool_ctype, ctype);
+	phi2 = alloc_phi(ep->active, src2, ctype);
+	use_pseudo(node, phi2, add_pseudo(&node->phi_list, phi2));
+
+	// join
 	set_activeblock(ep, merge);
-	return add_join_conditional(ep, expr, phi1, phi2);
+	add_instruction(&merge->insns, node);
+	return node->target;
 }
 
 static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr)
diff --git a/validation/linear/logical-phi0.c b/validation/linear/logical-phi0.c
index 92ba3bc5..96a47dba 100644
--- a/validation/linear/logical-phi0.c
+++ b/validation/linear/logical-phi0.c
@@ -45,5 +45,4 @@ static int roo(void)
 /*
  * check-name: bad-logical-phi0
  * check-command: sparse -vir -flinearize=last $file
- * check-known-to-fail
  */
diff --git a/validation/linear/logical.c b/validation/linear/logical.c
index 2c9f43f8..b190f608 100644
--- a/validation/linear/logical.c
+++ b/validation/linear/logical.c
@@ -26,24 +26,24 @@ os:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	load.32     %r2 <- 0[i]
+	setne.1     %r3 <- %r2, $0
 	phisrc.32   %phi1 <- $1
-	load.32     %r1 <- 0[i]
-	setne.1     %r2 <- %r1, $0
-	cbr         %r2, .L3, .L2
+	cbr         %r3, .L3, .L2
 
 .L2:
-	load.64     %r3 <- 0[b]
-	load.32     %r4 <- 0[%r3]
-	lsr.32      %r5 <- %r4, $1
-	trunc.2     %r6 <- (32) %r5
-	setne.1     %r7 <- %r6, $0
-	zext.32     %r8 <- (1) %r7
-	phisrc.32   %phi2 <- %r8
+	load.64     %r4 <- 0[b]
+	load.32     %r5 <- 0[%r4]
+	lsr.32      %r6 <- %r5, $1
+	trunc.2     %r7 <- (32) %r6
+	setne.1     %r8 <- %r7, $0
+	zext.32     %r9 <- (1) %r8
+	phisrc.32   %phi2 <- %r9
 	br          .L3
 
 .L3:
-	phi.32      %r9 <- %phi1, %phi2
-	phisrc.32   %phi3(return) <- %r9
+	phi.32      %r1 <- %phi1, %phi2
+	phisrc.32   %phi3(return) <- %r1
 	br          .L1
 
 .L1:
@@ -56,24 +56,24 @@ ou:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	load.32     %r12 <- 0[i]
+	setne.1     %r13 <- %r12, $0
 	phisrc.32   %phi4 <- $1
-	load.32     %r11 <- 0[i]
-	setne.1     %r12 <- %r11, $0
-	cbr         %r12, .L7, .L6
+	cbr         %r13, .L7, .L6
 
 .L6:
-	load.64     %r13 <- 0[b]
-	load.32     %r14 <- 0[%r13]
-	lsr.32      %r15 <- %r14, $3
-	trunc.3     %r16 <- (32) %r15
-	setne.1     %r17 <- %r16, $0
-	zext.32     %r18 <- (1) %r17
-	phisrc.32   %phi5 <- %r18
+	load.64     %r14 <- 0[b]
+	load.32     %r15 <- 0[%r14]
+	lsr.32      %r16 <- %r15, $3
+	trunc.3     %r17 <- (32) %r16
+	setne.1     %r18 <- %r17, $0
+	zext.32     %r19 <- (1) %r18
+	phisrc.32   %phi5 <- %r19
 	br          .L7
 
 .L7:
-	phi.32      %r19 <- %phi4, %phi5
-	phisrc.32   %phi6(return) <- %r19
+	phi.32      %r11 <- %phi4, %phi5
+	phisrc.32   %phi6(return) <- %r11
 	br          .L5
 
 .L5:
@@ -86,22 +86,22 @@ ol:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	load.32     %r22 <- 0[i]
+	setne.1     %r23 <- %r22, $0
 	phisrc.32   %phi7 <- $1
-	load.32     %r21 <- 0[i]
-	setne.1     %r22 <- %r21, $0
-	cbr         %r22, .L11, .L10
+	cbr         %r23, .L11, .L10
 
 .L10:
-	load.64     %r23 <- 0[b]
-	load.64     %r24 <- 8[%r23]
-	setne.1     %r25 <- %r24, $0
-	zext.32     %r26 <- (1) %r25
-	phisrc.32   %phi8 <- %r26
+	load.64     %r24 <- 0[b]
+	load.64     %r25 <- 8[%r24]
+	setne.1     %r26 <- %r25, $0
+	zext.32     %r27 <- (1) %r26
+	phisrc.32   %phi8 <- %r27
 	br          .L11
 
 .L11:
-	phi.32      %r27 <- %phi7, %phi8
-	phisrc.32   %phi9(return) <- %r27
+	phi.32      %r21 <- %phi7, %phi8
+	phisrc.32   %phi9(return) <- %r21
 	br          .L9
 
 .L9:
@@ -114,23 +114,23 @@ od:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	load.32     %r30 <- 0[i]
+	setne.1     %r31 <- %r30, $0
 	phisrc.32   %phi10 <- $1
-	load.32     %r29 <- 0[i]
-	setne.1     %r30 <- %r29, $0
-	cbr         %r30, .L15, .L14
+	cbr         %r31, .L15, .L14
 
 .L14:
-	load.64     %r31 <- 0[b]
-	load.64     %r32 <- 16[%r31]
-	setfval.64  %r33 <- 0.000000e+00
-	fcmpune.1   %r34 <- %r32, %r33
-	zext.32     %r35 <- (1) %r34
-	phisrc.32   %phi11 <- %r35
+	load.64     %r32 <- 0[b]
+	load.64     %r33 <- 16[%r32]
+	setfval.64  %r34 <- 0.000000e+00
+	fcmpune.1   %r35 <- %r33, %r34
+	zext.32     %r36 <- (1) %r35
+	phisrc.32   %phi11 <- %r36
 	br          .L15
 
 .L15:
-	phi.32      %r36 <- %phi10, %phi11
-	phisrc.32   %phi12(return) <- %r36
+	phi.32      %r29 <- %phi10, %phi11
+	phisrc.32   %phi12(return) <- %r29
 	br          .L13
 
 .L13:
@@ -143,24 +143,24 @@ as:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	load.32     %r39 <- 0[i]
+	setne.1     %r40 <- %r39, $0
 	phisrc.32   %phi13 <- $0
-	load.32     %r38 <- 0[i]
-	setne.1     %r39 <- %r38, $0
-	cbr         %r39, .L18, .L19
+	cbr         %r40, .L18, .L19
 
 .L18:
-	load.64     %r40 <- 0[b]
-	load.32     %r41 <- 0[%r40]
-	lsr.32      %r42 <- %r41, $1
-	trunc.2     %r43 <- (32) %r42
-	setne.1     %r44 <- %r43, $0
-	zext.32     %r45 <- (1) %r44
-	phisrc.32   %phi14 <- %r45
+	load.64     %r41 <- 0[b]
+	load.32     %r42 <- 0[%r41]
+	lsr.32      %r43 <- %r42, $1
+	trunc.2     %r44 <- (32) %r43
+	setne.1     %r45 <- %r44, $0
+	zext.32     %r46 <- (1) %r45
+	phisrc.32   %phi14 <- %r46
 	br          .L19
 
 .L19:
-	phi.32      %r46 <- %phi13, %phi14
-	phisrc.32   %phi15(return) <- %r46
+	phi.32      %r38 <- %phi13, %phi14
+	phisrc.32   %phi15(return) <- %r38
 	br          .L17
 
 .L17:
@@ -173,24 +173,24 @@ au:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	load.32     %r49 <- 0[i]
+	setne.1     %r50 <- %r49, $0
 	phisrc.32   %phi16 <- $0
-	load.32     %r48 <- 0[i]
-	setne.1     %r49 <- %r48, $0
-	cbr         %r49, .L22, .L23
+	cbr         %r50, .L22, .L23
 
 .L22:
-	load.64     %r50 <- 0[b]
-	load.32     %r51 <- 0[%r50]
-	lsr.32      %r52 <- %r51, $3
-	trunc.3     %r53 <- (32) %r52
-	setne.1     %r54 <- %r53, $0
-	zext.32     %r55 <- (1) %r54
-	phisrc.32   %phi17 <- %r55
+	load.64     %r51 <- 0[b]
+	load.32     %r52 <- 0[%r51]
+	lsr.32      %r53 <- %r52, $3
+	trunc.3     %r54 <- (32) %r53
+	setne.1     %r55 <- %r54, $0
+	zext.32     %r56 <- (1) %r55
+	phisrc.32   %phi17 <- %r56
 	br          .L23
 
 .L23:
-	phi.32      %r56 <- %phi16, %phi17
-	phisrc.32   %phi18(return) <- %r56
+	phi.32      %r48 <- %phi16, %phi17
+	phisrc.32   %phi18(return) <- %r48
 	br          .L21
 
 .L21:
@@ -203,22 +203,22 @@ al:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	load.32     %r59 <- 0[i]
+	setne.1     %r60 <- %r59, $0
 	phisrc.32   %phi19 <- $0
-	load.32     %r58 <- 0[i]
-	setne.1     %r59 <- %r58, $0
-	cbr         %r59, .L26, .L27
+	cbr         %r60, .L26, .L27
 
 .L26:
-	load.64     %r60 <- 0[b]
-	load.64     %r61 <- 8[%r60]
-	setne.1     %r62 <- %r61, $0
-	zext.32     %r63 <- (1) %r62
-	phisrc.32   %phi20 <- %r63
+	load.64     %r61 <- 0[b]
+	load.64     %r62 <- 8[%r61]
+	setne.1     %r63 <- %r62, $0
+	zext.32     %r64 <- (1) %r63
+	phisrc.32   %phi20 <- %r64
 	br          .L27
 
 .L27:
-	phi.32      %r64 <- %phi19, %phi20
-	phisrc.32   %phi21(return) <- %r64
+	phi.32      %r58 <- %phi19, %phi20
+	phisrc.32   %phi21(return) <- %r58
 	br          .L25
 
 .L25:
@@ -231,23 +231,23 @@ ad:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	load.32     %r67 <- 0[i]
+	setne.1     %r68 <- %r67, $0
 	phisrc.32   %phi22 <- $0
-	load.32     %r66 <- 0[i]
-	setne.1     %r67 <- %r66, $0
-	cbr         %r67, .L30, .L31
+	cbr         %r68, .L30, .L31
 
 .L30:
-	load.64     %r68 <- 0[b]
-	load.64     %r69 <- 16[%r68]
-	setfval.64  %r70 <- 0.000000e+00
-	fcmpune.1   %r71 <- %r69, %r70
-	zext.32     %r72 <- (1) %r71
-	phisrc.32   %phi23 <- %r72
+	load.64     %r69 <- 0[b]
+	load.64     %r70 <- 16[%r69]
+	setfval.64  %r71 <- 0.000000e+00
+	fcmpune.1   %r72 <- %r70, %r71
+	zext.32     %r73 <- (1) %r72
+	phisrc.32   %phi23 <- %r73
 	br          .L31
 
 .L31:
-	phi.32      %r73 <- %phi22, %phi23
-	phisrc.32   %phi24(return) <- %r73
+	phi.32      %r66 <- %phi22, %phi23
+	phisrc.32   %phi24(return) <- %r66
 	br          .L29
 
 .L29:
diff --git a/validation/linear/phi-order02.c b/validation/linear/phi-order02.c
index 5dd4b38e..d217ae45 100644
--- a/validation/linear/phi-order02.c
+++ b/validation/linear/phi-order02.c
@@ -13,5 +13,4 @@ static int xuq(int a) { return fun() && 0; }
 /*
  * check-name: phi-order02
  * check-command: sparse -vir -flinearize=last $file
- * check-known-to-fail
  */
diff --git a/validation/linear/phi-order03.c b/validation/linear/phi-order03.c
index 316cfeeb..24ae10e7 100644
--- a/validation/linear/phi-order03.c
+++ b/validation/linear/phi-order03.c
@@ -5,5 +5,4 @@ static int foo(void) { return ((0 || fun()) && fun()); }
 /*
  * check-name: phi-order03
  * check-command: sparse -vir -flinearize=last $file
- * check-known-to-fail
  */