From 1bd9ba3272b269a43be02ee380576e77652a563a Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Tue, 16 Mar 2021 23:18:00 +0100
Subject: Revert "simplify CBR-CBR on the same condition"

The commit 7cd2ce022575 ("simplify CBR-CBR on the same condition")
added a generalization of the existing CBR-CBR simplification
using the dominance tree.

The problem is that as soon as a change is made to the CFG, the
dominance tree become invalid and should be rebuilt (which is costly
to do for each CFG changes) or updated (which is quite complex).

So, for now, revert this commit.

Reverts: 7cd2ce022575fbd383bb39b54f1e0fa402919da2.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c | 106 -----------------------------------------------------------------
 1 file changed, 106 deletions(-)

diff --git a/flow.c b/flow.c
index c5319ae3..6d77453a 100644
--- a/flow.c
+++ b/flow.c
@@ -19,7 +19,6 @@
 #include "simplify.h"
 #include "flow.h"
 #include "target.h"
-#include "flowgraph.h"
 
 unsigned long bb_generation;
 
@@ -69,34 +68,6 @@ static int pseudo_truth_value(pseudo_t pseudo)
 	}
 }
 
-///
-// check if the BB is empty or only contains phi-sources
-static int bb_is_trivial(struct basic_block *bb)
-{
-	struct instruction *insn;
-	int n = 0;
-
-	FOR_EACH_PTR(bb->insns, insn) {
-		if (!insn->bb)
-			continue;
-		switch (insn->opcode) {
-		case OP_TERMINATOR ... OP_TERMINATOR_END:
-			return n ? -1 : 1;
-		case OP_NOP:
-		case OP_INLINED_CALL:
-			continue;
-		case OP_PHISOURCE:
-			n++;
-			continue;
-		default:
-			goto out;
-		}
-	} END_FOR_EACH_PTR(insn);
-
-out:
-	return 0;
-}
-
 /*
  * Does a basic block depend on the pseudos that "src" defines?
  */
@@ -158,81 +129,6 @@ out:
 	return false;
 }
 
-///
-// do jump threading in dominated BBs
-// @dom: the BB which must dominate the modified BBs.
-// @old: the old target BB
-// @new: the new target BB
-// @return: 0 if no chnages have been made, 1 otherwise.
-//
-// In all BB dominated by @dom, rewrite branches to @old into branches to @new
-static int retarget_bb(struct basic_block *dom, struct basic_block *old, struct basic_block *new)
-{
-	struct basic_block *bb;
-	int changed = 0;
-
-	if (new == old)
-		return 0;
-
-restart:
-	FOR_EACH_PTR(old->parents, bb) {
-		struct instruction *last;
-		struct multijmp *jmp;
-
-		if (!domtree_dominates(dom, bb))
-			continue;
-		last = last_instruction(bb->insns);
-		switch (last->opcode) {
-		case OP_BR:
-			changed |= rewrite_branch(bb, &last->bb_true,  old, new);
-			break;
-		case OP_CBR:
-			changed |= rewrite_branch(bb, &last->bb_true,  old, new);
-			changed |= rewrite_branch(bb, &last->bb_false, old, new);
-			break;
-		case OP_SWITCH:
-		case OP_COMPUTEDGOTO:
-			FOR_EACH_PTR(last->multijmp_list, jmp) {
-				changed |= rewrite_branch(bb, &jmp->target, old, new);
-			} END_FOR_EACH_PTR(jmp);
-			break;
-		default:
-			continue;
-		}
-
-		// since rewrite_branch() will modify old->parents() the list
-		// iteration won't work correctly. Several solution exist for
-		// this but in this case the simplest is to restart the loop.
-		goto restart;
-	} END_FOR_EACH_PTR(bb);
-	return changed;
-}
-
-static int simplify_cbr_cbr(struct instruction *insn)
-{
-	struct instruction *last;
-	struct basic_block *bot = insn->bb;
-	struct basic_block *top = bot->idom;
-	int changed = 0;
-	int trivial;
-
-	if (!top)
-		return 0;
-
-	trivial = bb_is_trivial(bot);
-	if (trivial == 0)
-		return 0;
-	if (trivial < 0)
-		return 0;
-	last = last_instruction(top->insns);
-	if (last->opcode != OP_CBR || last->cond != insn->cond)
-		return 0;
-
-	changed |= retarget_bb(last->bb_true , bot, insn->bb_true);
-	changed |= retarget_bb(last->bb_false, bot, insn->bb_false);
-	return changed;
-}
-
 /*
  * When we reach here, we have:
  *  - a basic block that ends in a conditional branch and
@@ -380,8 +276,6 @@ static int simplify_one_branch(struct basic_block *bb, struct instruction *br)
 {
 	if (simplify_phi_branch(bb, br))
 		return 1;
-	if (simplify_cbr_cbr(br))
-		return 1;
 	return simplify_branch_branch(bb, br, &br->bb_true, 1) |
 	       simplify_branch_branch(bb, br, &br->bb_false, 0);
 }
-- 
cgit 1.2.3-korg


From 52f02114bad02a2a705ecc3fe5904ff449196f50 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Wed, 17 Mar 2021 00:00:23 +0100
Subject: add testcases to check if phi-sources from removed targets are
 removed too

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/optim/bad-phisrc1.c  | 16 ++++++++++++++++
 validation/optim/bad-phisrc1a.c | 24 ++++++++++++++++++++++++
 validation/optim/bad-phisrc2.c  | 17 +++++++++++++++++
 validation/optim/bad-phisrc3.c  | 21 +++++++++++++++++++++
 4 files changed, 78 insertions(+)
 create mode 100644 validation/optim/bad-phisrc1.c
 create mode 100644 validation/optim/bad-phisrc1a.c
 create mode 100644 validation/optim/bad-phisrc2.c
 create mode 100644 validation/optim/bad-phisrc3.c

diff --git a/validation/optim/bad-phisrc1.c b/validation/optim/bad-phisrc1.c
new file mode 100644
index 00000000..59c5e4f1
--- /dev/null
+++ b/validation/optim/bad-phisrc1.c
@@ -0,0 +1,16 @@
+void foo(int a, int b)
+{
+	if (b)
+		while ((a += 5) > a)
+			;
+}
+
+/*
+ * check-name: bad-phisrc1
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-excludes: phi\\.
+ * check-output-excludes: phisource\\.
+ */
diff --git a/validation/optim/bad-phisrc1a.c b/validation/optim/bad-phisrc1a.c
new file mode 100644
index 00000000..cf07573b
--- /dev/null
+++ b/validation/optim/bad-phisrc1a.c
@@ -0,0 +1,24 @@
+int def(void);
+
+int fun4(struct xfrm_state *net, int cnt)
+{
+	int err = 0;
+	if (err)
+		goto out;
+	for (; net;)
+		err = def();
+	if (cnt)
+out:
+		return err;
+	return 0;
+}
+
+/*
+ * check-name: bad-phisrc1a
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: select\\.
+ */
+
diff --git a/validation/optim/bad-phisrc2.c b/validation/optim/bad-phisrc2.c
new file mode 100644
index 00000000..3eade688
--- /dev/null
+++ b/validation/optim/bad-phisrc2.c
@@ -0,0 +1,17 @@
+int bad_phisrc2(int p, int a, int r)
+{
+	if (p)
+		r = a;
+	else if (r)
+		;
+	return r;
+}
+
+/*
+ * check-name: bad-phisrc2
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: select\\.
+ */
diff --git a/validation/optim/bad-phisrc3.c b/validation/optim/bad-phisrc3.c
new file mode 100644
index 00000000..6e437771
--- /dev/null
+++ b/validation/optim/bad-phisrc3.c
@@ -0,0 +1,21 @@
+void foo(void)
+{
+	int c = 1;
+	switch (3) {
+	case 0:
+		do {
+			;
+	case 3:	;
+		} while (c++);
+	}
+}
+
+/*
+ * check-name: bad-phisrc3
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-pattern(2): phisrc\\.
+ * check-output-pattern(1): phi\\.
+ */
-- 
cgit 1.2.3-korg


From 26353a45ce03553c176cab553c3df36844e439fc Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 29 Mar 2020 18:22:50 +0200
Subject: remove insert_branch() redundant arg

insert_branch()'s first argument must be the BB of the instruction
given in the second argument.

So, remove it from the argument and simply use insn->bb instead.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c      | 2 +-
 linearize.c | 3 ++-
 linearize.h | 2 +-
 simplify.c  | 8 ++++----
 4 files changed, 8 insertions(+), 7 deletions(-)

diff --git a/flow.c b/flow.c
index 6d77453a..f85c2a30 100644
--- a/flow.c
+++ b/flow.c
@@ -268,7 +268,7 @@ try_to_rewrite_target:
 	 */
 	if (bb_list_size(target->parents) != 1)
 		return retval;
-	insert_branch(target, insn, final);
+	insert_branch(insn, final);
 	return 1;
 }
 
diff --git a/linearize.c b/linearize.c
index 7248fa56..ebb03217 100644
--- a/linearize.c
+++ b/linearize.c
@@ -700,8 +700,9 @@ static void remove_parent(struct basic_block *child, struct basic_block *parent)
 }
 
 /* Change a "switch" or a conditional branch into a branch */
-void insert_branch(struct basic_block *bb, struct instruction *jmp, struct basic_block *target)
+void insert_branch(struct instruction *jmp, struct basic_block *target)
 {
+	struct basic_block *bb = jmp->bb;
 	struct instruction *br, *old;
 	struct basic_block *child;
 
diff --git a/linearize.h b/linearize.h
index 7909b01f..1bb9d77e 100644
--- a/linearize.h
+++ b/linearize.h
@@ -319,7 +319,7 @@ struct entrypoint {
 };
 
 extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false);
-extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target);
+extern void insert_branch(struct instruction *br, struct basic_block *target);
 
 struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type);
 struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident);
diff --git a/simplify.c b/simplify.c
index 207af8ed..930c0fa7 100644
--- a/simplify.c
+++ b/simplify.c
@@ -2441,7 +2441,7 @@ static int simplify_branch(struct instruction *insn)
 
 	/* Constant conditional */
 	if (constant(cond)) {
-		insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
+		insert_branch(insn, cond->value ? insn->bb_true : insn->bb_false);
 		return REPEAT_CSE;
 	}
 
@@ -2473,11 +2473,11 @@ static int simplify_branch(struct instruction *insn)
 				long long val1 = def->src2->value;
 				long long val2 = def->src3->value;
 				if (!val1 && !val2) {
-					insert_branch(insn->bb, insn, insn->bb_false);
+					insert_branch(insn, insn->bb_false);
 					return REPEAT_CSE;
 				}
 				if (val1 && val2) {
-					insert_branch(insn->bb, insn, insn->bb_true);
+					insert_branch(insn, insn->bb_true);
 					return REPEAT_CSE;
 				}
 				if (val2) {
@@ -2515,7 +2515,7 @@ static int simplify_switch(struct instruction *insn)
 	return 0;
 
 found:
-	insert_branch(insn->bb, insn, jmp->target);
+	insert_branch(insn, jmp->target);
 	return REPEAT_CSE;
 }
 
-- 
cgit 1.2.3-korg


From f18c259989463f9a15270f3584bdeeaae4bd9fb0 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 29 Mar 2020 18:42:50 +0200
Subject: simplify remove_parent()

remove_parent() is a simple wrapper around remove_bb_from_list()
which also set REPEAT_CFG_CLEANUP if the list becomes empty.
But its only user, insert_branch(), doesn't need REPEAT_CFG_CLEANUP
to be set.

So, simplify this wrapper by keeping only the call to remove_bb_from_list().
---
 linearize.c | 2 --
 1 file changed, 2 deletions(-)

diff --git a/linearize.c b/linearize.c
index ebb03217..6bb1287e 100644
--- a/linearize.c
+++ b/linearize.c
@@ -695,8 +695,6 @@ static void set_activeblock(struct entrypoint *ep, struct basic_block *bb)
 static void remove_parent(struct basic_block *child, struct basic_block *parent)
 {
 	remove_bb_from_list(&child->parents, parent, 1);
-	if (!child->parents)
-		repeat_phase |= REPEAT_CFG_CLEANUP;
 }
 
 /* Change a "switch" or a conditional branch into a branch */
-- 
cgit 1.2.3-korg


From 701775cdf99d737aeaed00419eaff65d05ef1b57 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 29 Mar 2020 18:42:50 +0200
Subject: fold remove_parent() into insert_branch()

Fold remove_parent() into its only user, insert_branch(), since it's
now just a wrapper around remove_bb_from_list().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c | 7 +------
 1 file changed, 1 insertion(+), 6 deletions(-)

diff --git a/linearize.c b/linearize.c
index 6bb1287e..2268b095 100644
--- a/linearize.c
+++ b/linearize.c
@@ -692,11 +692,6 @@ static void set_activeblock(struct entrypoint *ep, struct basic_block *bb)
 		add_bb(&ep->bbs, bb);
 }
 
-static void remove_parent(struct basic_block *child, struct basic_block *parent)
-{
-	remove_bb_from_list(&child->parents, parent, 1);
-}
-
 /* Change a "switch" or a conditional branch into a branch */
 void insert_branch(struct instruction *jmp, struct basic_block *target)
 {
@@ -720,7 +715,7 @@ void insert_branch(struct instruction *jmp, struct basic_block *target)
 			continue;
 		}
 		DELETE_CURRENT_PTR(child);
-		remove_parent(child, bb);
+		remove_bb_from_list(&child->parents, bb, 1);
 	} END_FOR_EACH_PTR(child);
 	PACK_PTR_LIST(&bb->children);
 	repeat_phase |= REPEAT_CFG_CLEANUP;
-- 
cgit 1.2.3-korg


From b2dc8031654a536313fe77951ee04c74a3017e0b Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 29 Mar 2020 18:49:54 +0200
Subject: let insert_branch() reuse the terminating instruction

insert_branch() changes a switch or a conditional branch into a jump.
This is implemented by deleting the old instruction and allocating
the new one. This is not needed here since no reference to the
old instruction is kept.

So, simply reuse the terminating instruction and change it.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c | 16 ++++++----------
 1 file changed, 6 insertions(+), 10 deletions(-)

diff --git a/linearize.c b/linearize.c
index 2268b095..1d85cf2b 100644
--- a/linearize.c
+++ b/linearize.c
@@ -696,18 +696,14 @@ static void set_activeblock(struct entrypoint *ep, struct basic_block *bb)
 void insert_branch(struct instruction *jmp, struct basic_block *target)
 {
 	struct basic_block *bb = jmp->bb;
-	struct instruction *br, *old;
 	struct basic_block *child;
 
-	/* Remove the switch */
-	old = delete_last_instruction(&bb->insns);
-	assert(old == jmp);
-	kill_instruction(old);
-
-	br = alloc_instruction(OP_BR, 0);
-	br->bb = bb;
-	br->bb_true = target;
-	add_instruction(&bb->insns, br);
+	kill_use(&jmp->cond);
+	jmp->bb_true = target;
+	jmp->bb_false = NULL;
+	jmp->cond = NULL;
+	jmp->size = 0;
+	jmp->opcode = OP_BR;
 
 	FOR_EACH_PTR(bb->children, child) {
 		if (child == target) {
-- 
cgit 1.2.3-korg


From 1331214c003027c7b8af0af9bb9d8e040f8e3b4e Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 29 Mar 2020 18:49:54 +0200
Subject: move insert_branch() to flow.c

Now that insert_branch() doesn't need to allocate a new instruction,
there is no more reasons to have it defined in linearize.c

So move it to flow.c which is more concerned with CFG changes.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c      | 26 ++++++++++++++++++++++++++
 flow.h      |  1 +
 linearize.c | 26 --------------------------
 linearize.h |  1 -
 4 files changed, 27 insertions(+), 27 deletions(-)

diff --git a/flow.c b/flow.c
index f85c2a30..1f4b4ff0 100644
--- a/flow.c
+++ b/flow.c
@@ -709,6 +709,32 @@ void vrfy_flow(struct entrypoint *ep)
 	assert(!entry);
 }
 
+///
+// change a switch or a conditional branch into a branch
+void insert_branch(struct instruction *insn, struct basic_block *target)
+{
+	struct basic_block *bb = insn->bb;
+	struct basic_block *child;
+
+	kill_use(&insn->cond);
+	insn->bb_true = target;
+	insn->bb_false = NULL;
+	insn->cond = NULL;
+	insn->size = 0;
+	insn->opcode = OP_BR;
+
+	FOR_EACH_PTR(bb->children, child) {
+		if (child == target) {
+			target = NULL;	// leave first occurence
+			continue;
+		}
+		DELETE_CURRENT_PTR(child);
+		remove_bb_from_list(&child->parents, bb, 1);
+	} END_FOR_EACH_PTR(child);
+	PACK_PTR_LIST(&bb->children);
+	repeat_phase |= REPEAT_CFG_CLEANUP;
+}
+
 static int retarget_parents(struct basic_block *bb, struct basic_block *target)
 {
 	struct basic_block *parent;
diff --git a/flow.h b/flow.h
index 46d76a78..f9213306 100644
--- a/flow.h
+++ b/flow.h
@@ -18,6 +18,7 @@ extern void simplify_symbol_usage(struct entrypoint *ep);
 extern void simplify_memops(struct entrypoint *ep);
 extern void pack_basic_blocks(struct entrypoint *ep);
 extern int simplify_cfg_early(struct entrypoint *ep);
+extern void insert_branch(struct instruction *insn, struct basic_block *target);
 
 extern void convert_instruction_target(struct instruction *insn, pseudo_t src);
 extern void remove_dead_insns(struct entrypoint *);
diff --git a/linearize.c b/linearize.c
index 1d85cf2b..e6aa01f1 100644
--- a/linearize.c
+++ b/linearize.c
@@ -692,32 +692,6 @@ static void set_activeblock(struct entrypoint *ep, struct basic_block *bb)
 		add_bb(&ep->bbs, bb);
 }
 
-/* Change a "switch" or a conditional branch into a branch */
-void insert_branch(struct instruction *jmp, struct basic_block *target)
-{
-	struct basic_block *bb = jmp->bb;
-	struct basic_block *child;
-
-	kill_use(&jmp->cond);
-	jmp->bb_true = target;
-	jmp->bb_false = NULL;
-	jmp->cond = NULL;
-	jmp->size = 0;
-	jmp->opcode = OP_BR;
-
-	FOR_EACH_PTR(bb->children, child) {
-		if (child == target) {
-			target = NULL;	/* Trigger just once */
-			continue;
-		}
-		DELETE_CURRENT_PTR(child);
-		remove_bb_from_list(&child->parents, bb, 1);
-	} END_FOR_EACH_PTR(child);
-	PACK_PTR_LIST(&bb->children);
-	repeat_phase |= REPEAT_CFG_CLEANUP;
-}
-	
-
 void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi_node, pseudo_t if_true, pseudo_t if_false)
 {
 	pseudo_t target;
diff --git a/linearize.h b/linearize.h
index 1bb9d77e..b6c8bf13 100644
--- a/linearize.h
+++ b/linearize.h
@@ -319,7 +319,6 @@ struct entrypoint {
 };
 
 extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false);
-extern void insert_branch(struct instruction *br, struct basic_block *target);
 
 struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type);
 struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident);
-- 
cgit 1.2.3-korg


From ffa92f53257da38844e9f6f7ffbd71a777c6e54c Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 29 Mar 2020 18:42:50 +0200
Subject: let insert_branch() return a status

insert_branch() modifies the CFG and the usage of pseudos so these
changes must be, in a way or another, notify to the upper layers.
Currently this is done by setting 'repeat_phase' in the function
itself.

Let this function to also report the changes via its return value
since this is usually useful for the caller to know and tend to
leaner code too.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c     |  7 +++++--
 flow.h     |  2 +-
 simplify.c | 21 +++++++--------------
 3 files changed, 13 insertions(+), 17 deletions(-)

diff --git a/flow.c b/flow.c
index 1f4b4ff0..38e0ccad 100644
--- a/flow.c
+++ b/flow.c
@@ -711,10 +711,11 @@ void vrfy_flow(struct entrypoint *ep)
 
 ///
 // change a switch or a conditional branch into a branch
-void insert_branch(struct instruction *insn, struct basic_block *target)
+int insert_branch(struct instruction *insn, struct basic_block *target)
 {
 	struct basic_block *bb = insn->bb;
 	struct basic_block *child;
+	int changed = REPEAT_CSE;
 
 	kill_use(&insn->cond);
 	insn->bb_true = target;
@@ -730,9 +731,11 @@ void insert_branch(struct instruction *insn, struct basic_block *target)
 		}
 		DELETE_CURRENT_PTR(child);
 		remove_bb_from_list(&child->parents, bb, 1);
+		changed |= REPEAT_CFG_CLEANUP;
 	} END_FOR_EACH_PTR(child);
 	PACK_PTR_LIST(&bb->children);
-	repeat_phase |= REPEAT_CFG_CLEANUP;
+	repeat_phase |= changed;
+	return changed;
 }
 
 static int retarget_parents(struct basic_block *bb, struct basic_block *target)
diff --git a/flow.h b/flow.h
index f9213306..cad1de77 100644
--- a/flow.h
+++ b/flow.h
@@ -18,7 +18,7 @@ extern void simplify_symbol_usage(struct entrypoint *ep);
 extern void simplify_memops(struct entrypoint *ep);
 extern void pack_basic_blocks(struct entrypoint *ep);
 extern int simplify_cfg_early(struct entrypoint *ep);
-extern void insert_branch(struct instruction *insn, struct basic_block *target);
+extern int insert_branch(struct instruction *insn, struct basic_block *target);
 
 extern void convert_instruction_target(struct instruction *insn, pseudo_t src);
 extern void remove_dead_insns(struct entrypoint *);
diff --git a/simplify.c b/simplify.c
index 930c0fa7..0bc201e8 100644
--- a/simplify.c
+++ b/simplify.c
@@ -2440,10 +2440,8 @@ static int simplify_branch(struct instruction *insn)
 	pseudo_t cond = insn->cond;
 
 	/* Constant conditional */
-	if (constant(cond)) {
-		insert_branch(insn, cond->value ? insn->bb_true : insn->bb_false);
-		return REPEAT_CSE;
-	}
+	if (constant(cond))
+		return insert_branch(insn, cond->value ? insn->bb_true : insn->bb_false);
 
 	/* Same target? */
 	if (insn->bb_true == insn->bb_false) {
@@ -2472,14 +2470,10 @@ static int simplify_branch(struct instruction *insn)
 			if (constant(def->src2) && constant(def->src3)) {
 				long long val1 = def->src2->value;
 				long long val2 = def->src3->value;
-				if (!val1 && !val2) {
-					insert_branch(insn, insn->bb_false);
-					return REPEAT_CSE;
-				}
-				if (val1 && val2) {
-					insert_branch(insn, insn->bb_true);
-					return REPEAT_CSE;
-				}
+				if (!val1 && !val2)
+					return insert_branch(insn, insn->bb_false);
+				if (val1 && val2)
+					return insert_branch(insn, insn->bb_true);
 				if (val2) {
 					struct basic_block *tmp = insn->bb_true;
 					insn->bb_true = insn->bb_false;
@@ -2515,8 +2509,7 @@ static int simplify_switch(struct instruction *insn)
 	return 0;
 
 found:
-	insert_branch(insn, jmp->target);
-	return REPEAT_CSE;
+	return insert_branch(insn, jmp->target);
 }
 
 static struct basic_block *is_label(pseudo_t pseudo)
-- 
cgit 1.2.3-korg


From 4ac342d1efdbeda4c8cd3b79d53ae6b15f1f5cfc Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 14 Mar 2021 15:12:21 +0100
Subject: rename insert_branch() to convert_to_jump()

Since the existing branch is now reused, nothing is inserted anymore.

So, rename this function to the more explanatory: convert_to_jump().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c     | 4 ++--
 flow.h     | 2 +-
 simplify.c | 8 ++++----
 3 files changed, 7 insertions(+), 7 deletions(-)

diff --git a/flow.c b/flow.c
index 38e0ccad..8106cfc0 100644
--- a/flow.c
+++ b/flow.c
@@ -268,7 +268,7 @@ try_to_rewrite_target:
 	 */
 	if (bb_list_size(target->parents) != 1)
 		return retval;
-	insert_branch(insn, final);
+	convert_to_jump(insn, final);
 	return 1;
 }
 
@@ -711,7 +711,7 @@ void vrfy_flow(struct entrypoint *ep)
 
 ///
 // change a switch or a conditional branch into a branch
-int insert_branch(struct instruction *insn, struct basic_block *target)
+int convert_to_jump(struct instruction *insn, struct basic_block *target)
 {
 	struct basic_block *bb = insn->bb;
 	struct basic_block *child;
diff --git a/flow.h b/flow.h
index cad1de77..2103a10f 100644
--- a/flow.h
+++ b/flow.h
@@ -18,7 +18,7 @@ extern void simplify_symbol_usage(struct entrypoint *ep);
 extern void simplify_memops(struct entrypoint *ep);
 extern void pack_basic_blocks(struct entrypoint *ep);
 extern int simplify_cfg_early(struct entrypoint *ep);
-extern int insert_branch(struct instruction *insn, struct basic_block *target);
+extern int convert_to_jump(struct instruction *insn, struct basic_block *target);
 
 extern void convert_instruction_target(struct instruction *insn, pseudo_t src);
 extern void remove_dead_insns(struct entrypoint *);
diff --git a/simplify.c b/simplify.c
index 0bc201e8..7171bd56 100644
--- a/simplify.c
+++ b/simplify.c
@@ -2441,7 +2441,7 @@ static int simplify_branch(struct instruction *insn)
 
 	/* Constant conditional */
 	if (constant(cond))
-		return insert_branch(insn, cond->value ? insn->bb_true : insn->bb_false);
+		return convert_to_jump(insn, cond->value ? insn->bb_true : insn->bb_false);
 
 	/* Same target? */
 	if (insn->bb_true == insn->bb_false) {
@@ -2471,9 +2471,9 @@ static int simplify_branch(struct instruction *insn)
 				long long val1 = def->src2->value;
 				long long val2 = def->src3->value;
 				if (!val1 && !val2)
-					return insert_branch(insn, insn->bb_false);
+					return convert_to_jump(insn, insn->bb_false);
 				if (val1 && val2)
-					return insert_branch(insn, insn->bb_true);
+					return convert_to_jump(insn, insn->bb_true);
 				if (val2) {
 					struct basic_block *tmp = insn->bb_true;
 					insn->bb_true = insn->bb_false;
@@ -2509,7 +2509,7 @@ static int simplify_switch(struct instruction *insn)
 	return 0;
 
 found:
-	return insert_branch(insn, jmp->target);
+	return convert_to_jump(insn, jmp->target);
 }
 
 static struct basic_block *is_label(pseudo_t pseudo)
-- 
cgit 1.2.3-korg


From 752914c764b6d396c8e0a7c4ab207181edf7b00e Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Fri, 19 Feb 2021 07:24:35 +0100
Subject: add remove_phisources()

When a parent is removed from a BB containing one or several phi-nodes,
the corresponding phi-sources become irrelevant and need to be removed
from the phi-nodes.

Add an helper for doing this: remove_phisources().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c | 43 +++++++++++++++++++++++++++++++++++++++++++
 flow.h |  2 ++
 2 files changed, 45 insertions(+)

diff --git a/flow.c b/flow.c
index 8106cfc0..4952562a 100644
--- a/flow.c
+++ b/flow.c
@@ -22,6 +22,49 @@
 
 unsigned long bb_generation;
 
+///
+// remove phi-sources from a removed edge
+//
+// :note: It's possible to have several edges between the same BBs.
+//	  It's common with switches but it's also possible with branches.
+//	  This function will only remove a single phi-source per edge.
+int remove_phisources(struct basic_block *par, struct basic_block *old)
+{
+	struct instruction *insn;
+	int changed = 0;
+
+	FOR_EACH_PTR(old->insns, insn) {
+		pseudo_t phi;
+
+		if (!insn->bb)
+			continue;
+		if (insn->opcode != OP_PHI)
+			return changed;
+
+		// found a phi-node in the target BB,
+		// now look after its phi-sources.
+		FOR_EACH_PTR(insn->phi_list, phi) {
+			struct instruction *phisrc = phi->def;
+
+			if (phi == VOID)
+				continue;
+			assert(phisrc->phi_node == insn);
+			if (phisrc->bb != par)
+				continue;
+			// found a phi-source corresponding to this edge:
+			// remove it but avoid the recursive killing.
+			REPLACE_CURRENT_PTR(phi, VOID);
+			remove_use(&phisrc->src);
+			phisrc->bb = NULL;
+			changed |= REPEAT_CSE;
+			// Only the first one must be removed.
+			goto next;
+		} END_FOR_EACH_PTR(phi);
+next: ;
+	} END_FOR_EACH_PTR(insn);
+	return changed;
+}
+
 /*
  * Dammit, if we have a phi-node followed by a conditional
  * branch on that phi-node, we should damn well be able to
diff --git a/flow.h b/flow.h
index 2103a10f..c489ebe0 100644
--- a/flow.h
+++ b/flow.h
@@ -11,6 +11,8 @@ extern unsigned long bb_generation;
 struct entrypoint;
 struct instruction;
 
+extern int remove_phisources(struct basic_block *par, struct basic_block *old);
+
 extern int simplify_flow(struct entrypoint *ep);
 
 extern void kill_dead_stores(struct entrypoint *ep, pseudo_t addr, int local);
-- 
cgit 1.2.3-korg


From c59ba8c0b5d699256651755eed6f421667751d33 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Fri, 19 Feb 2021 07:25:33 +0100
Subject: fix phisources during CBR-BR conversion

When a parent is removed from a BB containing one or several phi-nodes,
the corresponding phi-sources must be removed from the phi-node.

However this is not done and consequentially:
* it becomes impossibly to correctly reason about the flow of values
  through these phi-nodes.
* simplifications are missed (e.g. if-conversion).

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                          | 5 +++++
 validation/optim/bad-phisrc1.c  | 1 -
 validation/optim/bad-phisrc1a.c | 1 -
 3 files changed, 5 insertions(+), 2 deletions(-)

diff --git a/flow.c b/flow.c
index 4952562a..69d95a98 100644
--- a/flow.c
+++ b/flow.c
@@ -760,6 +760,11 @@ int convert_to_jump(struct instruction *insn, struct basic_block *target)
 	struct basic_block *child;
 	int changed = REPEAT_CSE;
 
+	switch (insn->opcode) {
+	case OP_CBR:
+		changed |= remove_phisources(insn->bb, insn->bb_true == target ? insn->bb_false : insn->bb_true);
+		break;
+	}
 	kill_use(&insn->cond);
 	insn->bb_true = target;
 	insn->bb_false = NULL;
diff --git a/validation/optim/bad-phisrc1.c b/validation/optim/bad-phisrc1.c
index 59c5e4f1..aa12dd0a 100644
--- a/validation/optim/bad-phisrc1.c
+++ b/validation/optim/bad-phisrc1.c
@@ -8,7 +8,6 @@ void foo(int a, int b)
 /*
  * check-name: bad-phisrc1
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-excludes: phi\\.
diff --git a/validation/optim/bad-phisrc1a.c b/validation/optim/bad-phisrc1a.c
index cf07573b..b7519ee7 100644
--- a/validation/optim/bad-phisrc1a.c
+++ b/validation/optim/bad-phisrc1a.c
@@ -16,7 +16,6 @@ out:
 /*
  * check-name: bad-phisrc1a
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: select\\.
-- 
cgit 1.2.3-korg


From a45f9140a0c237f1b2f82e66595dba6426c5b598 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Fri, 19 Feb 2021 07:26:49 +0100
Subject: use convert_to_jump() when converting a CBR with same targets

If a conditional branch has identical targets, it should be
converted to a simple jump.

This is done but using its own code.
Change this by using the existing convert_to_jump() instead.
This also allows any redundant phi-sources to be removed.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                     | 13 ++-----------
 validation/optim/bad-phisrc2.c |  1 -
 2 files changed, 2 insertions(+), 12 deletions(-)

diff --git a/simplify.c b/simplify.c
index 7171bd56..90db041a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -2444,17 +2444,8 @@ static int simplify_branch(struct instruction *insn)
 		return convert_to_jump(insn, cond->value ? insn->bb_true : insn->bb_false);
 
 	/* Same target? */
-	if (insn->bb_true == insn->bb_false) {
-		struct basic_block *bb = insn->bb;
-		struct basic_block *target = insn->bb_false;
-		remove_bb_from_list(&target->parents, bb, 1);
-		remove_bb_from_list(&bb->children, target, 1);
-		insn->bb_false = NULL;
-		kill_use(&insn->cond);
-		insn->cond = NULL;
-		insn->opcode = OP_BR;
-		return REPEAT_CSE|REPEAT_CFG_CLEANUP;
-	}
+	if (insn->bb_true == insn->bb_false)
+		return convert_to_jump(insn, insn->bb_true);
 
 	/* Conditional on a SETNE $0 or SETEQ $0 */
 	if (cond->type == PSEUDO_REG) {
diff --git a/validation/optim/bad-phisrc2.c b/validation/optim/bad-phisrc2.c
index 3eade688..78eae288 100644
--- a/validation/optim/bad-phisrc2.c
+++ b/validation/optim/bad-phisrc2.c
@@ -10,7 +10,6 @@ int bad_phisrc2(int p, int a, int r)
 /*
  * check-name: bad-phisrc2
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: select\\.
-- 
cgit 1.2.3-korg


From 7b5cc7b6135733cbbce121cc94fdc4a5400f46b5 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Fri, 19 Feb 2021 07:25:33 +0100
Subject: fix phisources during SWITCH-BR conversion

Like for CBR-BR conversion, when a target BB containing one or several
phi-nodes is removed from an OP_SWITCH, the corresponding phi-source
must be removed from the phi-node.

However this is not done yet.

Changing this by adding some code to convert_to_jump() to remove all
phi-sources from the discarded targets if the converted instruction
is an OP_SWITCH.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                         | 20 ++++++++++++++++++++
 validation/optim/bad-phisrc3.c |  1 -
 2 files changed, 20 insertions(+), 1 deletion(-)

diff --git a/flow.c b/flow.c
index 69d95a98..cb94fcf2 100644
--- a/flow.c
+++ b/flow.c
@@ -65,6 +65,23 @@ next: ;
 	return changed;
 }
 
+///
+// remove all phisources but the one corresponding to the given target
+static int remove_other_phisources(struct basic_block *bb, struct multijmp_list *list, struct basic_block *target)
+{
+	struct multijmp *jmp;
+	int changed = 0;
+
+	FOR_EACH_PTR(list, jmp) {
+		if (jmp->target == target) {
+			target = NULL;
+			continue;
+		}
+		changed |= remove_phisources(bb, jmp->target);
+	} END_FOR_EACH_PTR(jmp);
+	return changed;
+}
+
 /*
  * Dammit, if we have a phi-node followed by a conditional
  * branch on that phi-node, we should damn well be able to
@@ -764,6 +781,9 @@ int convert_to_jump(struct instruction *insn, struct basic_block *target)
 	case OP_CBR:
 		changed |= remove_phisources(insn->bb, insn->bb_true == target ? insn->bb_false : insn->bb_true);
 		break;
+	case OP_SWITCH:
+		changed |= remove_other_phisources(insn->bb, insn->multijmp_list, target);
+		break;
 	}
 	kill_use(&insn->cond);
 	insn->bb_true = target;
diff --git a/validation/optim/bad-phisrc3.c b/validation/optim/bad-phisrc3.c
index 6e437771..41537420 100644
--- a/validation/optim/bad-phisrc3.c
+++ b/validation/optim/bad-phisrc3.c
@@ -13,7 +13,6 @@ void foo(void)
 /*
  * check-name: bad-phisrc3
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-pattern(2): phisrc\\.
-- 
cgit 1.2.3-korg


From 9794908e1ad570920c470a8c817abbc3b195b876 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sat, 20 Mar 2021 18:18:23 +0100
Subject: add insert_last_instruction()

It's relatively common to have to add an instruction at the end of a BB.
More exactly, at the end but just before the terminator instruction.
What is done for this is:
1) remove the terminator
2) add the new instruction
3) add the terminator back

This is a bit tedious, need to declare a temporary variable for the
terminator and, more generally, it's low-level details.

So, add an helper for doing this: insert_last_instruction().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.h | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/linearize.h b/linearize.h
index b6c8bf13..493f6be1 100644
--- a/linearize.h
+++ b/linearize.h
@@ -195,6 +195,14 @@ static inline void add_instruction(struct instruction_list **list, struct instru
 	add_ptr_list(list, insn);
 }
 
+static inline void insert_last_instruction(struct basic_block *bb, struct instruction *insn)
+{
+	struct instruction *last = delete_last_instruction(&bb->insns);
+	add_instruction(&bb->insns, insn);
+	add_instruction(&bb->insns, last);
+	insn->bb = bb;
+}
+
 static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp)
 {
 	add_ptr_list(list, multijmp);
-- 
cgit 1.2.3-korg


From 438393f490d6f5b773c9074880e3a8ae3b37f842 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 21 Mar 2021 15:37:53 +0100
Subject: replace add_instruction_to_end() by insert_last_instruction()

add_instruction_to_end() and insert_last_instruction() do exactly
the same thing but with the arguments in the opposite order.

So, replace add_instruction_to_end() by insert_last_instruction().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 cse.c | 10 +---------
 1 file changed, 1 insertion(+), 9 deletions(-)

diff --git a/cse.c b/cse.c
index 1e58a973..b5958181 100644
--- a/cse.c
+++ b/cse.c
@@ -298,14 +298,6 @@ static inline void remove_instruction(struct instruction_list **list, struct ins
 	delete_ptr_list_entry((struct ptr_list **)list, insn, count);
 }
 
-static void add_instruction_to_end(struct instruction *insn, struct basic_block *bb)
-{
-	struct instruction *br = delete_last_instruction(&bb->insns);
-	insn->bb = bb;
-	add_instruction(&bb->insns, insn);
-	add_instruction(&bb->insns, br);
-}
-
 static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction *i1, struct instruction *i2)
 {
 	struct basic_block *b1, *b2, *common;
@@ -343,7 +335,7 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction
 	if (common) {
 		i1 = cse_one_instruction(i2, i1);
 		remove_instruction(&b1->insns, i1, 1);
-		add_instruction_to_end(i1, common);
+		insert_last_instruction(common, i1);
 	} else {
 		i1 = i2;
 	}
-- 
cgit 1.2.3-korg


From f5d1205420aa4323aef2c93bdad973104c11df4d Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 21 Mar 2021 15:38:23 +0100
Subject: let insert_select() use insert_last_instruction()

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c | 7 +------
 1 file changed, 1 insertion(+), 6 deletions(-)

diff --git a/linearize.c b/linearize.c
index e6aa01f1..4787689b 100644
--- a/linearize.c
+++ b/linearize.c
@@ -697,11 +697,7 @@ void insert_select(struct basic_block *bb, struct instruction *br, struct instru
 	pseudo_t target;
 	struct instruction *select;
 
-	/* Remove the 'br' */
-	delete_last_instruction(&bb->insns);
-
 	select = alloc_typed_instruction(OP_SEL, phi_node->type);
-	select->bb = bb;
 
 	assert(br->cond);
 	use_pseudo(select, br->cond, &select->src1);
@@ -714,8 +710,7 @@ void insert_select(struct basic_block *bb, struct instruction *br, struct instru
 	use_pseudo(select, if_true, &select->src2);
 	use_pseudo(select, if_false, &select->src3);
 
-	add_instruction(&bb->insns, select);
-	add_instruction(&bb->insns, br);
+	insert_last_instruction(bb, select);
 }
 
 static inline int bb_empty(struct basic_block *bb)
-- 
cgit 1.2.3-korg


From d1011daff5abcf5dd90d4b01be6e977bd23c6411 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 21 Mar 2021 15:39:15 +0100
Subject: let insert_phis() use insert_last_instruction()

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/linearize.c b/linearize.c
index 4787689b..95fb3b59 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1708,10 +1708,9 @@ static void insert_phis(struct basic_block *bb, pseudo_t src, struct symbol *cty
 	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);
-		link_phi(node, phi);
+		struct instruction *phisrc = alloc_phisrc(src, ctype);
+		insert_last_instruction(parent, phisrc);
+		link_phi(node, phisrc->target);
 	} END_FOR_EACH_PTR(parent);
 }
 
-- 
cgit 1.2.3-korg


From 4c6929edf09a9d751b22531d899f6b10a7af0106 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 21 Mar 2021 15:40:40 +0100
Subject: let find_dominating_parents() use insert_last_instruction()

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 memops.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/memops.c b/memops.c
index ff54208e..f74bff2a 100644
--- a/memops.c
+++ b/memops.c
@@ -65,8 +65,8 @@ static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
 	struct basic_block *parent;
 
 	FOR_EACH_PTR(bb->parents, parent) {
+		struct instruction *phisrc;
 		struct instruction *one;
-		struct instruction *br;
 		pseudo_t phi;
 
 		FOR_EACH_PTR_REVERSE(parent->insns, one) {
@@ -95,12 +95,12 @@ no_dominance:
 		continue;
 
 found_dominator:
-		br = delete_last_instruction(&parent->insns);
-		phi = alloc_phi(parent, one->target, one->type);
+		phisrc = alloc_phisrc(one->target, one->type);
+		phisrc->phi_node = insn;
+		insert_last_instruction(parent, phisrc);
+		phi = phisrc->target;
 		phi->ident = phi->ident ? : one->target->ident;
-		add_instruction(&parent->insns, br);
 		use_pseudo(insn, phi, add_pseudo(dominators, phi));
-		phi->def->phi_node = insn;
 	} END_FOR_EACH_PTR(parent);
 	return 1;
 }		
-- 
cgit 1.2.3-korg


From 190172adee54045651babb4a9ae79d7cb4c1b1ac Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 21 Mar 2021 15:40:57 +0100
Subject: let ssa_rename_phi() use insert_last_instruction()

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ssa.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/ssa.c b/ssa.c
index b9044207..5f1a52b8 100644
--- a/ssa.c
+++ b/ssa.c
@@ -345,11 +345,11 @@ static void ssa_rename_phi(struct instruction *insn)
 	if (!var->torename)
 		return;
 	FOR_EACH_PTR(insn->bb->parents, par) {
-		struct instruction *term = delete_last_instruction(&par->insns);
 		pseudo_t val = lookup_var(par, var);
-		pseudo_t phi = alloc_phi(par, val, var);
+		struct instruction *phisrc = alloc_phisrc(val, var);
+		pseudo_t phi = phisrc->target;
 		phi->ident = var->ident;
-		add_instruction(&par->insns, term);
+		insert_last_instruction(par, phisrc);
 		link_phi(insn, phi);
 		mark_phi_used(val);
 	} END_FOR_EACH_PTR(par);
-- 
cgit 1.2.3-korg


From b204ead75fc624928e783da8b6658f3a8a06871c Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Fri, 26 Mar 2021 00:41:22 +0100
Subject: additional testcase for remove_merging_phisrc()

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/optim/multi-phisrc.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)
 create mode 100644 validation/optim/multi-phisrc.c

diff --git a/validation/optim/multi-phisrc.c b/validation/optim/multi-phisrc.c
new file mode 100644
index 00000000..c6f21f2d
--- /dev/null
+++ b/validation/optim/multi-phisrc.c
@@ -0,0 +1,24 @@
+void fun(void);
+
+void foo(int p, int a)
+{
+	if (p == p) {
+		switch (p) {
+		case 0:
+			break;
+		case 1:
+			a = 0;
+		}
+	}
+	if (a)
+		fun();
+}
+
+/*
+ * check-name: multi-phisrc
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-excludes: phi
+ */
-- 
cgit 1.2.3-korg


From dcb199646134ae0d264c72175a9ad8314f7836c8 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 28 Mar 2021 16:07:29 +0100
Subject: correctly count phi arguments

In a phi-node,pseudo_list_size() can't be used for counting its arguments
because VOIDs must be ignored.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                         | 18 +++++++++++++++++-
 validation/optim/phi-count00.c | 27 +++++++++++++++++++++++++++
 2 files changed, 44 insertions(+), 1 deletion(-)
 create mode 100644 validation/optim/phi-count00.c

diff --git a/flow.c b/flow.c
index cb94fcf2..58807432 100644
--- a/flow.c
+++ b/flow.c
@@ -189,6 +189,22 @@ out:
 	return false;
 }
 
+///
+// count the true number of argument of a phi-node
+// VOID arguments must be ignored, so pseudo_list_size() can't be used for this.
+static int phi_count(struct instruction *node)
+{
+	pseudo_t phi;
+	int n = 0;
+
+	FOR_EACH_PTR(node->phi_list, phi) {
+		if (phi == VOID)
+			continue;
+		n++;
+	} END_FOR_EACH_PTR(phi);
+	return n;
+}
+
 /*
  * When we reach here, we have:
  *  - a basic block that ends in a conditional branch and
@@ -211,7 +227,7 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 	 * simplify_symbol_usage()/conversion to SSA form.
 	 * No sane simplification can be done when we have this.
 	 */
-	bogus = bb_list_size(bb->parents) != pseudo_list_size(first->phi_list);
+	bogus = bb_list_size(bb->parents) != phi_count(first);
 
 	FOR_EACH_PTR(first->phi_list, phi) {
 		struct instruction *def = phi->def;
diff --git a/validation/optim/phi-count00.c b/validation/optim/phi-count00.c
new file mode 100644
index 00000000..38db0eda
--- /dev/null
+++ b/validation/optim/phi-count00.c
@@ -0,0 +1,27 @@
+inline int inl(int d, int e, int f)
+{
+	switch (d) {
+	case 0:
+		return e;
+	case 1:
+		return f;
+	default:
+		return 0;
+	}
+}
+
+void foo(int a, int b, int c)
+{
+	while (1) {
+		if (inl(a, b, c))
+			break;
+	}
+}
+
+/*
+ * check-name: phi-count00
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-pattern(0,2): phisrc
+ */
-- 
cgit 1.2.3-korg


From 78183a155b833ded168e9f72055a8a0f01a5ad46 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 28 Mar 2021 13:52:38 +0200
Subject: better check validity of phi-sources

Transformations made by try_to_simplify_bb() are invalid if
there isn't a one-to-one correspondence between the BB's parents
and the phi-sources of the phi-node(s) in the BB.

This correspondence is currently checked by checking if the number
of phi-sources and the number of parent are equal, but this is
only an approximation.

Change this check into an exact one, using the fact that BBs in
the parent list and phi-sources in the phi_list are in the same order.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c | 21 +++++++++++++--------
 1 file changed, 13 insertions(+), 8 deletions(-)

diff --git a/flow.c b/flow.c
index 58807432..c866dec8 100644
--- a/flow.c
+++ b/flow.c
@@ -190,19 +190,24 @@ out:
 }
 
 ///
-// count the true number of argument of a phi-node
-// VOID arguments must be ignored, so pseudo_list_size() can't be used for this.
-static int phi_count(struct instruction *node)
+// check if the sources of a phi-node match with the parent BBs
+static bool phi_check(struct instruction *node)
 {
+	struct basic_block *bb;
 	pseudo_t phi;
-	int n = 0;
 
+	PREPARE_PTR_LIST(node->bb->parents, bb);
 	FOR_EACH_PTR(node->phi_list, phi) {
-		if (phi == VOID)
+		if (phi == VOID || !phi->def)
 			continue;
-		n++;
+		if (phi->def->bb != bb)
+			return false;
+		NEXT_PTR_LIST(bb);
 	} END_FOR_EACH_PTR(phi);
-	return n;
+	if (bb)
+		return false;
+	FINISH_PTR_LIST(bb);
+	return true;
 }
 
 /*
@@ -227,7 +232,7 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 	 * simplify_symbol_usage()/conversion to SSA form.
 	 * No sane simplification can be done when we have this.
 	 */
-	bogus = bb_list_size(bb->parents) != phi_count(first);
+	bogus = !phi_check(first);
 
 	FOR_EACH_PTR(first->phi_list, phi) {
 		struct instruction *def = phi->def;
-- 
cgit 1.2.3-korg


From 8b89204e0d7e2caaaa03ff8ed79da5bf6f2e1b36 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Fri, 26 Mar 2021 00:41:22 +0100
Subject: fix remove_merging_phisrc()

The current implementation of remove_merging_phisrc() can't work correctly
when these phi-sources belong to a basic block with several children
to the same target basic block (this happens commonly with OP_SWITCH).

Fix this by directly scanning the source basic block for the presence
of any phi-source. Once identified, the processing is kept unchanged:
remove these phi-sources if a sibling phi-source will 'overwrite' them
in the target block.

Fixes: 2fdaca9e7175e62f08d259f5cb3ec7c9725bba68
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                          | 30 ++++++++++++++++++++----------
 validation/optim/multi-phisrc.c |  1 -
 2 files changed, 20 insertions(+), 11 deletions(-)

diff --git a/flow.c b/flow.c
index c866dec8..d46d0ee1 100644
--- a/flow.c
+++ b/flow.c
@@ -843,21 +843,26 @@ static int retarget_parents(struct basic_block *bb, struct basic_block *target)
 	return REPEAT_CFG_CLEANUP;
 }
 
-static void remove_merging_phisrc(struct basic_block *top, struct instruction *insn)
+static void remove_merging_phisrc(struct instruction *insn, struct basic_block *bot)
 {
-	struct instruction *user = insn->phi_node;
+	struct instruction *node = insn->phi_node;
 	pseudo_t phi;
 
-	FOR_EACH_PTR(user->phi_list, phi) {
+	if (!node) {
+		kill_instruction(insn);
+		return;
+	}
+
+	FOR_EACH_PTR(node->phi_list, phi) {
 		struct instruction *phisrc;
 
 		if (phi == VOID)
 			continue;
 		phisrc = phi->def;
-		if (phisrc->bb != top)
-			continue;
-		REPLACE_CURRENT_PTR(phi, VOID);
-		kill_instruction(phisrc);
+		if (phisrc->bb == bot) {
+			kill_instruction(insn);
+			return;
+		}
 	} END_FOR_EACH_PTR(phi);
 }
 
@@ -901,6 +906,14 @@ static int merge_bb(struct basic_block *top, struct basic_block *bot)
 		replace_bb_in_list(&bb->parents, bot, top, 1);
 	} END_FOR_EACH_PTR(bb);
 
+	FOR_EACH_PTR(top->insns, insn) {
+		if (!insn->bb)
+			continue;
+		if (insn->opcode != OP_PHISOURCE)
+			continue;
+		remove_merging_phisrc(insn, bot);
+	} END_FOR_EACH_PTR(insn);
+
 	kill_instruction(delete_last_instruction(&top->insns));
 	FOR_EACH_PTR(bot->insns, insn) {
 		if (!insn->bb)
@@ -910,9 +923,6 @@ static int merge_bb(struct basic_block *top, struct basic_block *bot)
 		case OP_PHI:
 			remove_merging_phi(top, insn);
 			continue;
-		case OP_PHISOURCE:
-			remove_merging_phisrc(top, insn);
-			break;
 		}
 		insn->bb = top;
 		add_instruction(&top->insns, insn);
diff --git a/validation/optim/multi-phisrc.c b/validation/optim/multi-phisrc.c
index c6f21f2d..ff31c083 100644
--- a/validation/optim/multi-phisrc.c
+++ b/validation/optim/multi-phisrc.c
@@ -17,7 +17,6 @@ void foo(int p, int a)
 /*
  * check-name: multi-phisrc
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-excludes: phi
-- 
cgit 1.2.3-korg