[PATCH] experimental: code sinking

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

A lot of the false 'context imbalance' warnings are caused by
a potential jump-threading being blocked between 2 conditional
branches on the same condition because the second CBR belong
to a non-empty BB. Often the offending instructions can be moved
to some other BB, sometimes even with some added advantages.

This patch help a bit with these false warnings by doing a limited
form of code sinking: blocking instructions with a single user
are moved in the BB where they're used, possibly making the
original BB empty and thus making the jump-threading possible.

Note: It's not the intention to use the patch as is.
      Ideally, it should first be checked if the original BB
      can be made empty before moving the instructions around,
      but this should be coordinated with other ways of moving
      these instructions.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Makefile    |  1 +
 code-sink.c | 92 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 optimize.c  |  2 ++
 optimize.h  |  3 ++
 4 files changed, 98 insertions(+)
 create mode 100644 code-sink.c

diff --git a/Makefile b/Makefile
index 313664467151..5ba54659f625 100644
--- a/Makefile
+++ b/Makefile
@@ -35,6 +35,7 @@ LIB_OBJS :=
 LIB_OBJS += allocate.o
 LIB_OBJS += builtin.o
 LIB_OBJS += char.o
+LIB_OBJS += code-sink.o
 LIB_OBJS += compat-$(OS).o
 LIB_OBJS += cse.o
 LIB_OBJS += dissect.o
diff --git a/code-sink.c b/code-sink.c
new file mode 100644
index 000000000000..566ddec028a0
--- /dev/null
+++ b/code-sink.c
@@ -0,0 +1,92 @@
+#include "optimize.h"
+#include "lib.h"
+#include "linearize.h"
+
+
+static inline struct instruction *get_user(pseudo_t p)
+{
+	struct pseudo_user *pu;
+
+	FOR_EACH_PTR(p->users, pu) {
+		if (!pu)
+			continue;
+		return pu->insn;
+	} END_FOR_EACH_PTR(pu);
+	return NULL;
+}
+
+static bool sink_insn(struct instruction *insn, struct basic_block *bb)
+{
+	struct instruction *curr;
+
+	FOR_EACH_PTR(bb->insns, curr) {
+		if (!curr->bb)
+			continue;
+		if (curr->opcode == OP_PHI)
+			continue;
+		INSERT_CURRENT(insn, curr);
+		insn->bb = bb;
+		return true;
+	} END_FOR_EACH_PTR(curr);
+	return false;
+}
+
+static int code_sink_bb(struct basic_block *bb)
+{
+	struct instruction *insn;
+	int changed = 0;
+
+	FOR_EACH_PTR_REVERSE(bb->insns, insn) {
+		struct instruction *user;
+		pseudo_t target;
+
+		if (!insn->bb)
+			continue;
+		switch (insn->opcode) {
+		case OP_BINARY ... OP_BINCMP_END:
+		case OP_UNOP ... OP_UNOP_END:
+		case OP_SYMADDR:
+		case OP_SLICE:
+		case OP_SEL: case OP_FMADD:
+		case OP_LABEL: case OP_SETVAL: case OP_SETFVAL:
+			break;
+		case OP_CBR:
+		case OP_INLINED_CALL:
+		case OP_NOP:
+			continue;
+		default:
+			continue;
+		}
+
+		target = insn->target;
+		if (!one_use(target))
+			continue;
+		user = get_user(target);
+		if (!user || !user->bb || user->bb == bb)
+			continue;
+		if (!sink_insn(insn, user->bb))
+			continue;
+		DELETE_CURRENT_PTR(insn);
+		changed = 1;
+	} END_FOR_EACH_PTR_REVERSE(insn);
+	return changed;
+}
+
+int code_sink(struct entrypoint *ep)
+{
+	struct basic_block *bb;
+	int changed = 0;
+
+	FOR_EACH_PTR(ep->bbs, bb) {
+		struct instruction *last;
+
+		if (!bb->ep)
+			continue;
+		last = last_instruction(bb->insns);
+		switch (last->opcode) {
+		case OP_CBR:
+			changed |= code_sink_bb(bb);
+		}
+	} END_FOR_EACH_PTR(bb);
+	return changed;
+}
diff --git a/optimize.c b/optimize.c
index 3351e67b9d5e..b652b0e76d2a 100644
--- a/optimize.c
+++ b/optimize.c
@@ -105,6 +105,8 @@ repeat:
 		pack_basic_blocks(ep);
 		if (repeat_phase & REPEAT_CFG_CLEANUP)
 			cleanup_cfg(ep);
+		if (code_sink(ep))
+			repeat_phase |= REPEAT_CSE;
 	} while (repeat_phase);
 
 	vrfy_flow(ep);
diff --git a/optimize.h b/optimize.h
index 31e2cf081704..d9ac9cd48ea2 100644
--- a/optimize.h
+++ b/optimize.h
@@ -6,4 +6,7 @@ struct entrypoint;
 /* optimize.c */
 void optimize(struct entrypoint *ep);
 
+/* sink.c */
+int code_sink(struct entrypoint *ep);
+
 #endif
-- 
2.29.2