Merge branch 'diamond'

* rebuild dominance tree during CFG cleanup
* simplify CBR-CBR on the same condition

2 files changed, 114 insertions, 2 deletions

diff --git a/flow.c b/flow.c
index 951241b5..162c2734 100644
--- a/flow.c
+++ b/flow.c
@@ -18,6 +18,7 @@
 #include "linearize.h"
 #include "flow.h"
 #include "target.h"
+#include "flowgraph.h"
 
 unsigned long bb_generation;
 
@@ -86,6 +87,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?
  */
@@ -147,6 +176,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
@@ -294,6 +398,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);
 }
diff --git a/optimize.c b/optimize.c
index 00595414..9b754831 100644
--- a/optimize.c
+++ b/optimize.c
@@ -47,6 +47,12 @@ static void clean_up_insns(struct entrypoint *ep)
 	} END_FOR_EACH_PTR(bb);
 }
 
+static void cleanup_cfg(struct entrypoint *ep)
+{
+	kill_unreachable_bbs(ep);
+	domtree_build(ep);
+}
+
 ///
 // optimization main loop
 void optimize(struct entrypoint *ep)
@@ -97,7 +103,7 @@ repeat:
 		} while (repeat_phase);
 		pack_basic_blocks(ep);
 		if (repeat_phase & REPEAT_CFG_CLEANUP)
-			kill_unreachable_bbs(ep);
+			cleanup_cfg(ep);
 	} while (repeat_phase);
 
 	vrfy_flow(ep);
@@ -117,7 +123,7 @@ repeat:
 	if (simplify_flow(ep)) {
 		clear_liveness(ep);
 		if (repeat_phase & REPEAT_CFG_CLEANUP)
-			kill_unreachable_bbs(ep);
+			cleanup_cfg(ep);
 		goto repeat;
 	}