simplify CBR-CBR on the same condition

In situations like:
		...
		cbr	<cond>, L1, L2

	L1:		L2:
	...		...

		L3:
		cbr	<cond>, L4, L5

since the conditions are the same and L3 is empty but the CBR,
all branches to L3 in L1 can be changed to branches to L4
(idem with L5 in L2). The same can be done in all BB 'in the
path between L1 and L3', more exactly in all BB dominated by L1,
this guarantee that the changes is only done on the BB where
the conditions match.

Note: This simplification kinda generalizes the current
      simplify_branch_branch() but should itself generalized
      to handle the presence of phi-sources in L3.

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

1 files changed, 106 insertions, 0 deletions

diff --git a/flow.c b/flow.c
index 2e20ab75..2615bbed 100644
--- a/flow.c
+++ b/flow.c
@@ -17,6 +17,7 @@
 #include "linearize.h"
 #include "flow.h"
 #include "target.h"
+#include "flowgraph.h"
 
 unsigned long bb_generation;
 
@@ -85,6 +86,34 @@ 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?
  */
@@ -146,6 +175,81 @@ 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
@@ -293,6 +397,8 @@ 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);
 }