[PATCH 00/13] remove phi-sources from removed branches

[PATCH 00/13] remove phi-sources from removed branches

[Luc Van Oostenryck]

This series, after some related and preparatory patches, contains
fixes for the problem of phi-sources being left in place after their
corresponding branches have been removed. This results in situations,
for example, where a phi-node has 3 arguments/inputs/sources but only
2 parent BBs and create all sort of problems, like:
* some dead code is not removed
* some optimizations involving phi-nodes are blocked (if-conversions)
* more importantly, these phi-nodes are invalid/meaningless and so
  it's impossible to reason correctly about them.

Note: This series only fixes *some* of these problems. Other probably
      still exists, especially when rewrite_branch() is used.


Luc Van Oostenryck (13):
  Revert "simplify CBR-CBR on the same condition"
  add testcases to check if phi-sources from removed targets are removed
    too
  remove insert_branch() redundant arg
  simplify remove_parent()
  fold remove_parent() into insert_branch()
  let insert_branch() reuse the terminating instruction
  move insert_branch() to flow.c
  let insert_branch() return a status
  rename insert_branch() to convert_to_jump()
  add remove_phisources()
  fix phisources during CBR-BR conversion
  use convert_to_jump() when converting a CBR with same targets
  fix phisources during SWITCH-BR conversion

 flow.c                          | 205 +++++++++++++++-----------------
 flow.h                          |   3 +
 linearize.c                     |  36 ------
 linearize.h                     |   1 -
 simplify.c                      |  34 ++----
 validation/optim/bad-phisrc1.c  |  15 +++
 validation/optim/bad-phisrc1a.c |  23 ++++
 validation/optim/bad-phisrc2.c  |  16 +++
 validation/optim/bad-phisrc3.c  |  20 ++++
 9 files changed, 184 insertions(+), 169 deletions(-)
 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

-- 
2.31.0

[PATCH 01/13] Revert "simplify CBR-CBR on the same condition"

[Luc Van Oostenryck]

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 c5319ae35ac4..6d77453a3554 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);
 }
-- 
2.31.0

[PATCH 02/13] add testcases to check if phi-sources from removed targets are removed too

[Luc Van Oostenryck]

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 000000000000..59c5e4f1e66a
--- /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 000000000000..cf07573b1fd3
--- /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 000000000000..3eade688f768
--- /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 000000000000..6e437771b4b8
--- /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\\.
+ */
-- 
2.31.0

[PATCH 03/13] remove insert_branch() redundant arg

[Luc Van Oostenryck]

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 6d77453a3554..f85c2a30c3cb 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 7248fa56b2ef..ebb03217c9d9 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 7909b01f29c5..1bb9d77eba1f 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 207af8edf28f..930c0fa7e83f 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;
 }
 
-- 
2.31.0

[PATCH 04/13] simplify remove_parent()

[Luc Van Oostenryck]

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 ebb03217c9d9..6bb1287efcb0 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 */
-- 
2.31.0

[PATCH 05/13] fold remove_parent() into insert_branch()

[Luc Van Oostenryck]

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 6bb1287efcb0..2268b0951376 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;
-- 
2.31.0

[PATCH 06/13] let insert_branch() reuse the terminating instruction

[Luc Van Oostenryck]

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 2268b0951376..1d85cf2ba208 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) {
-- 
2.31.0

[PATCH 07/13] move insert_branch() to flow.c

[Luc Van Oostenryck]

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 f85c2a30c3cb..1f4b4ff08151 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 46d76a780484..f9213306dfd6 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 1d85cf2ba208..e6aa01f1b9fe 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 1bb9d77eba1f..b6c8bf134065 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);
-- 
2.31.0

[PATCH 08/13] let insert_branch() return a status

[Luc Van Oostenryck]

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 1f4b4ff08151..38e0ccade722 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 f9213306dfd6..cad1de7723d5 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 930c0fa7e83f..0bc201e84313 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)
-- 
2.31.0

[PATCH 09/13] rename insert_branch() to convert_to_jump()

[Luc Van Oostenryck]

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 38e0ccade722..8106cfc0d10b 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 cad1de7723d5..2103a10fe428 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 0bc201e84313..7171bd564e63 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)
-- 
2.31.0

[PATCH 10/13] add remove_phisources()

[Luc Van Oostenryck]

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 8106cfc0d10b..4952562a373d 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 2103a10fe428..c489ebe03034 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);
-- 
2.31.0

[PATCH 11/13] fix phisources during CBR-BR conversion

[Luc Van Oostenryck]

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 4952562a373d..69d95a98a512 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 59c5e4f1e66a..aa12dd0ae542 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 cf07573b1fd3..b7519ee7cf5d 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\\.
-- 
2.31.0

[PATCH 12/13] use convert_to_jump() when converting a CBR with same targets

[Luc Van Oostenryck]

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 7171bd564e63..90db041af823 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 3eade688f768..78eae28856fd 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\\.
-- 
2.31.0

[PATCH 13/13] fix phisources during SWITCH-BR conversion

[Luc Van Oostenryck]

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 69d95a98a512..cb94fcf20834 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 6e437771b4b8..41537420d6fa 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\\.
-- 
2.31.0