[PATCH 0/2] simplify CBR-CBR on the same condition

[PATCH 0/2] simplify CBR-CBR on the same condition

[Luc Van Oostenryck]

These two patches do the the CBR-CBR 'diamond' simplification.
Together with the previous series, it shaves a few more 
'context imbalance' warnings but I think it will need to handle
phi-sources to show its full potential.


Luc Van Oostenryck (2):
  rebuild dominance tree during CFG cleanup
  simplify CBR-CBR on the same condition

 flow.c     | 106 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 optimize.c |  10 ++++-
 2 files changed, 114 insertions(+), 2 deletions(-)

-- 
2.29.2

[PATCH 1/2] rebuild dominance tree during CFG cleanup

[Luc Van Oostenryck]

Currently, the dominance tree is build once, just before the
SSA conversion.

However, changes in the CFG potentially changes the dominance
relationships.

So, rebuild the dominance tree after changes to the CFG.

Note: This doesn't seems to significantly affect the performance
      (at least when used on the kernel):
	before			after
	real	 4m15.854s	real	 4m16.95&s
	user	71m11.390s	user	71m29.180s
	sys	28m45.222s	sys	28m46.145s

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 optimize.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/optimize.c b/optimize.c
index 338714c78e68..c047495f26cf 100644
--- a/optimize.c
+++ b/optimize.c
@@ -45,6 +45,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);
+}
+
 void optimize(struct entrypoint *ep)
 {
 	if (fdump_ir & PASS_LINEARIZE)
@@ -93,7 +99,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);
@@ -113,7 +119,7 @@ repeat:
 	if (simplify_flow(ep)) {
 		clear_liveness(ep);
 		if (repeat_phase & REPEAT_CFG_CLEANUP)
-			kill_unreachable_bbs(ep);
+			cleanup_cfg(ep);
 		goto repeat;
 	}
 
-- 
2.29.2

[PATCH 2/2] simplify CBR-CBR on the same condition

[Luc Van Oostenryck]

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>
---
 flow.c | 106 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 106 insertions(+)

diff --git a/flow.c b/flow.c
index f56e72db470c..88e0014c75ac 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);
 }
-- 
2.29.2