[PATCH 7/7] move up instructions blocking if-conversion

[Luc Van Oostenryck <luc.vanoostenryck@gmail.com>]

---
 linearize.h |  6 +++++
 simplify.c  | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 68 insertions(+), 2 deletions(-)

diff --git a/linearize.h b/linearize.h
index 2c548d43526f..71a693960c9e 100644
--- a/linearize.h
+++ b/linearize.h
@@ -300,6 +300,12 @@ static inline void replace_bb_in_list(struct basic_block_list **list,
 	replace_ptr_list_entry((struct ptr_list **)list, old, new, count);
 }
 
+static inline void replace_insn(struct instruction *old, struct instruction *new)
+{
+	replace_ptr_list_entry((struct ptr_list **)&old->bb->insns, old, new, 1);
+}
+
+
 struct entrypoint {
 	struct symbol *name;
 	struct symbol_list *syms;
diff --git a/simplify.c b/simplify.c
index fc64e5b77adf..14a5562c84a4 100644
--- a/simplify.c
+++ b/simplify.c
@@ -61,6 +61,63 @@ static inline bool is_pow2(pseudo_t src)
 	return is_power_of_2(src->value);
 }
 
+///
+// check if a pseudo is defined in a BB
+//
+// :note: this could also use the liveness information if available.
+//
+static inline bool is_defined_at(pseudo_t src, struct basic_block *bb)
+{
+	if (src->type != PSEUDO_REG)
+		return true;
+	return domtree_dominates(src->def->bb, bb);
+}
+
+///
+// move an instruction at the end of the given BB
+static void move_insn(struct instruction *insn, struct basic_block *bb)
+{
+	struct instruction *last = delete_last_instruction(&bb->insns);
+	insn->bb = bb;
+	add_instruction(&bb->insns, insn);
+	add_instruction(&bb->insns, last);
+}
+
+///
+// try to move an instruction into a BB if all its arguments are defined there
+static bool try_to_move_insn(struct instruction *insn, struct basic_block *bb)
+{
+	static struct instruction NOP;	// will later be ignore because !ep
+
+	if (!bb || bb == insn->bb)
+		return 0;
+
+	switch (insn->opcode) {
+	case OP_SEL:
+		if (!is_defined_at(insn->src3, bb))
+			return 0;
+	case OP_ADD: case OP_SUB:
+	case OP_ASR: case OP_LSR: case OP_SHL:
+	case OP_AND: case OP_XOR: case OP_OR:
+	case OP_BINCMP ... OP_BINCMP_END:
+	case OP_FPCMP ... OP_FPCMP_END:
+	case OP_FADD: case OP_FSUB:
+		// basically, all the binops but multiply and divide, just because
+		if (!is_defined_at(insn->src2, bb))
+			return 0;
+	case OP_UNOP ... OP_UNOP_END:
+		if (!is_defined_at(insn->src1, bb))
+			return 0;
+		break;
+	default:
+		return 0;
+	}
+	replace_insn(insn, &NOP);
+	move_insn(insn, bb);
+	repeat_phase |= REPEAT_CSE;
+	return 1;
+}
+
 ///
 // find the trivial parent for a phi-source
 static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
@@ -68,8 +125,11 @@ static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseud
 	/* Can't go upwards if the pseudo is defined in the bb it came from.. */
 	if (pseudo->type == PSEUDO_REG) {
 		struct instruction *def = pseudo->def;
-		if (def->bb == source)
-			return source;
+		if (def->bb == source) {
+			// unless we can move the defining instruction up
+			if (!try_to_move_insn(def, source->idom))
+				return source;
+		}
 	}
 	if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
 		return source;
-- 
2.29.2