Merge branch 'pack-early'

* cfg: remove phi-sources when merging BBs
* cfg: remove phi-nodes when merging BBs
* cfg: add missing REPEAT_CFG_CLEANUP
* cfg: call simplify_memops() unconditionally.
* cfg: early CFG simplification

18 files changed, 269 insertions, 39 deletions

diff --git a/flow.c b/flow.c
index 1c6abdca..951241b5 100644
--- a/flow.c
+++ b/flow.c
@@ -44,6 +44,25 @@ static int rewrite_branch(struct basic_block *bb,
 	return 1;
 }
 
+///
+// returns the phi-node corresponding to a phi-source
+static struct instruction *get_phinode(struct instruction *phisrc)
+{
+	struct pseudo_user *pu;
+
+	FOR_EACH_PTR(phisrc->target->users, pu) {
+		struct instruction *user;
+
+		if (!pu)
+			continue;
+		user = pu->insn;
+		assert(user->opcode == OP_PHI);
+		return user;
+	} END_FOR_EACH_PTR(pu);
+	assert(0);
+}
+
+
 /*
  * Return the known truth value of a pseudo, or -1 if
  * it's not known.
@@ -103,6 +122,31 @@ static int bb_depends_on_phi(struct basic_block *target, struct basic_block *src
 	return 0;
 }
 
+///
+// does the BB contains ignorable instructions but a final branch?
+// :note: something could be done for phi-sources but ... we'll see.
+static bool bb_is_forwarder(struct basic_block *bb)
+{
+	struct instruction *insn;
+
+	FOR_EACH_PTR(bb->insns, insn) {
+		if (!insn->bb)
+			continue;
+		switch (insn->opcode) {
+		case OP_NOP:
+		case OP_INLINED_CALL:
+			continue;
+		case OP_CBR:
+		case OP_BR:
+			return true;
+		default:
+			goto out;
+		}
+	} END_FOR_EACH_PTR(insn);
+out:
+	return false;
+}
+
 /*
  * When we reach here, we have:
  *  - a basic block that ends in a conditional branch and
@@ -724,13 +768,145 @@ void vrfy_flow(struct entrypoint *ep)
 	assert(!entry);
 }
 
+static int retarget_parents(struct basic_block *bb, struct basic_block *target)
+{
+	struct basic_block *parent;
+
+	/*
+	 * We can't do FOR_EACH_PTR() here, because the parent list
+	 * may change when we rewrite the parent.
+	 */
+	while ((parent = first_basic_block(bb->parents))) {
+		if (!rewrite_parent_branch(parent, bb, target))
+			return 0;
+	}
+	kill_bb(bb);
+	return REPEAT_CFG_CLEANUP;
+}
+
+static void remove_merging_phisrc(struct basic_block *top, struct instruction *insn)
+{
+	struct instruction *user = get_phinode(insn);
+	pseudo_t phi;
+
+	FOR_EACH_PTR(user->phi_list, phi) {
+		struct instruction *phisrc;
+
+		if (phi == VOID)
+			continue;
+		phisrc = phi->def;
+		if (phisrc->bb != top)
+			continue;
+		REPLACE_CURRENT_PTR(phi, VOID);
+		kill_instruction(phisrc);
+	} END_FOR_EACH_PTR(phi);
+}
+
+static void remove_merging_phi(struct basic_block *top, struct instruction *insn)
+{
+	pseudo_t phi;
+
+	FOR_EACH_PTR(insn->phi_list, phi) {
+		struct instruction *def;
+
+		if (phi == VOID)
+			continue;
+
+		def = phi->def;
+		if (def->bb != top)
+			continue;
+
+		convert_instruction_target(insn, def->src);
+		kill_instruction(def);
+		kill_instruction(insn);
+	} END_FOR_EACH_PTR(phi);
+}
+
+///
+// merge two BBs
+// @top: the first BB to be merged
+// @bot: the second BB to be merged
+static int merge_bb(struct basic_block *top, struct basic_block *bot)
+{
+	struct instruction *insn;
+	struct basic_block *bb;
+
+	if (top == bot)
+		return 0;
+
+	top->children = bot->children;
+	bot->children = NULL;
+	bot->parents = NULL;
+
+	FOR_EACH_PTR(top->children, bb) {
+		replace_bb_in_list(&bb->parents, bot, top, 1);
+	} END_FOR_EACH_PTR(bb);
+
+	kill_instruction(delete_last_instruction(&top->insns));
+	FOR_EACH_PTR(bot->insns, insn) {
+		if (!insn->bb)
+			continue;
+		assert(insn->bb == bot);
+		switch (insn->opcode) {
+		case OP_PHI:
+			remove_merging_phi(top, insn);
+			continue;
+		case OP_PHISOURCE:
+			remove_merging_phisrc(top, insn);
+			break;
+		}
+		insn->bb = top;
+		add_instruction(&top->insns, insn);
+	} END_FOR_EACH_PTR(insn);
+	bot->insns = NULL;
+	bot->ep = NULL;
+	return REPEAT_CFG_CLEANUP;
+}
+
+///
+// early simplification of the CFG
+// Three things are done here:
+//    # inactive BB are removed
+//    # branches to a 'forwarder' BB are redirected to the forwardee.
+//    # merge single-child/single-parent BBs.
+int simplify_cfg_early(struct entrypoint *ep)
+{
+	struct basic_block *bb;
+	int changed = 0;
+
+	FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
+		struct instruction *insn;
+		struct basic_block *tgt;
+
+		if (!bb->ep) {
+			DELETE_CURRENT_PTR(bb);
+			changed = REPEAT_CFG_CLEANUP;
+			continue;
+		}
+
+		insn = last_instruction(bb->insns);
+		if (!insn)
+			continue;
+		switch (insn->opcode) {
+		case OP_BR:
+			tgt = insn->bb_true;
+			if (bb_is_forwarder(bb))
+				changed |= retarget_parents(bb, tgt);
+			else if (bb_list_size(tgt->parents) == 1)
+				changed |= merge_bb(bb, tgt);
+			break;
+		}
+	} END_FOR_EACH_PTR_REVERSE(bb);
+	return changed;
+}
+
 void pack_basic_blocks(struct entrypoint *ep)
 {
 	struct basic_block *bb;
 
 	/* See if we can merge a bb into another one.. */
 	FOR_EACH_PTR(ep->bbs, bb) {
-		struct instruction *first, *insn;
+		struct instruction *first;
 		struct basic_block *parent, *child, *last;
 
 		if (!bb_reachable(bb))
@@ -787,28 +963,7 @@ out:
 				goto no_merge;
 		} END_FOR_EACH_PTR(child);
 
-		/*
-		 * Merge the two.
-		 */
-		repeat_phase |= REPEAT_CFG_CLEANUP;
-
-		parent->children = bb->children;
-		bb->children = NULL;
-		bb->parents = NULL;
-
-		FOR_EACH_PTR(parent->children, child) {
-			replace_bb_in_list(&child->parents, bb, parent, 0);
-		} END_FOR_EACH_PTR(child);
-
-		kill_instruction(delete_last_instruction(&parent->insns));
-		FOR_EACH_PTR(bb->insns, insn) {
-			if (!insn->bb)
-				continue;
-			assert(insn->bb == bb);
-			insn->bb = parent;
-			add_instruction(&parent->insns, insn);
-		} END_FOR_EACH_PTR(insn);
-		bb->insns = NULL;
+		repeat_phase |= merge_bb(parent, bb);
 
 	no_merge:
 		/* nothing to do */;
diff --git a/flow.h b/flow.h
index 099767d4..19a743c8 100644
--- a/flow.h
+++ b/flow.h
@@ -18,6 +18,7 @@ extern void kill_dead_stores(struct entrypoint *ep, pseudo_t addr, int local);
 extern void simplify_symbol_usage(struct entrypoint *ep);
 extern void simplify_memops(struct entrypoint *ep);
 extern void pack_basic_blocks(struct entrypoint *ep);
+extern int simplify_cfg_early(struct entrypoint *ep);
 
 extern void convert_instruction_target(struct instruction *insn, pseudo_t src);
 extern void remove_dead_insns(struct entrypoint *);
diff --git a/linearize.c b/linearize.c
index ab91113d..5d800b7f 100644
--- a/linearize.c
+++ b/linearize.c
@@ -726,6 +726,7 @@ void insert_branch(struct basic_block *bb, struct instruction *jmp, struct basic
 		remove_parent(child, bb);
 	} END_FOR_EACH_PTR(child);
 	PACK_PTR_LIST(&bb->children);
+	repeat_phase |= REPEAT_CFG_CLEANUP;
 }
 	
 
diff --git a/memops.c b/memops.c
index f071e556..badcdbbb 100644
--- a/memops.c
+++ b/memops.c
@@ -146,10 +146,12 @@ static void simplify_loads(struct basic_block *bb)
 				}
 				rewrite_load_instruction(insn, dominators);
 			} else {	// cleanup pending phi-sources
+				int repeat = repeat_phase;
 				pseudo_t phi;
 				FOR_EACH_PTR(dominators, phi) {
 					kill_instruction(phi->def);
 				} END_FOR_EACH_PTR(phi);
+				repeat_phase = repeat;
 			}
 		}
 next_load:
diff --git a/optimize.c b/optimize.c
index fd4ecb99..00595414 100644
--- a/optimize.c
+++ b/optimize.c
@@ -61,6 +61,11 @@ void optimize(struct entrypoint *ep)
 	kill_unreachable_bbs(ep);
 	ir_validate(ep);
 
+	cfg_postorder(ep);
+	if (simplify_cfg_early(ep))
+		kill_unreachable_bbs(ep);
+	ir_validate(ep);
+
 	domtree_build(ep);
 
 	/*
@@ -88,9 +93,7 @@ repeat:
 				kill_unreachable_bbs(ep);
 
 			cse_eliminate(ep);
-
-			if (repeat_phase & REPEAT_SYMBOL_CLEANUP)
-				simplify_memops(ep);
+			simplify_memops(ep);
 		} while (repeat_phase);
 		pack_basic_blocks(ep);
 		if (repeat_phase & REPEAT_CFG_CLEANUP)
diff --git a/simplify.c b/simplify.c
index e58fb6cf..a0e23d6d 100644
--- a/simplify.c
+++ b/simplify.c
@@ -2048,7 +2048,7 @@ static int simplify_branch(struct instruction *insn)
 		kill_use(&insn->cond);
 		insn->cond = NULL;
 		insn->opcode = OP_BR;
-		return REPEAT_CSE;
+		return REPEAT_CSE|REPEAT_CFG_CLEANUP;
 	}
 
 	/* Conditional on a SETNE $0 or SETEQ $0 */
diff --git a/validation/call-inlined.c b/validation/call-inlined.c
index 3612c5c4..a6cb4b5b 100644
--- a/validation/call-inlined.c
+++ b/validation/call-inlined.c
@@ -28,12 +28,14 @@ foo:
 	<entry-point>
 	add.32      %r3 <- %arg1, %arg2
 	add.32      %r5 <- %r3, $1
+	# call      %r6 <- add, %r3, $1
 	ret.32      %r5
 
 
 bar:
 .L3:
 	<entry-point>
+	# call      %r13 <- add, %r10, $1
 	ret
 
 
@@ -41,6 +43,7 @@ bas:
 .L6:
 	<entry-point>
 	add.64      %r16 <- "abc", $1
+	# call      %r17 <- lstrip, %r14
 	ret.64      %r16
 
 
@@ -48,6 +51,7 @@ qus:
 .L9:
 	<entry-point>
 	add.64      %r21 <- messg, $1
+	# call      %r22 <- lstrip, %r19
 	ret.64      %r21
 
 
diff --git a/validation/expand/builtin_constant_inline0.c b/validation/expand/builtin_constant_inline0.c
index a0057f20..d72a211f 100644
--- a/validation/expand/builtin_constant_inline0.c
+++ b/validation/expand/builtin_constant_inline0.c
@@ -16,6 +16,7 @@ int foo(void)
 foo:
 .L0:
 	<entry-point>
+	# call      %r1 <- is_const, $42
 	ret.32      $42
 
 
diff --git a/validation/inline_base0.c b/validation/inline_base0.c
index 517ee972..698c760f 100644
--- a/validation/inline_base0.c
+++ b/validation/inline_base0.c
@@ -27,6 +27,7 @@ foo0:
 .L0:
 	<entry-point>
 	add.32      %r5 <- %arg1, %arg2
+	# call      %r6 <- add, %r1, %r2
 	ret.32      %r5
 
 
@@ -34,12 +35,14 @@ foo1:
 .L3:
 	<entry-point>
 	add.32      %r10 <- %arg1, $1
+	# call      %r11 <- add, %r8, $1
 	ret.32      %r10
 
 
 foo2:
 .L6:
 	<entry-point>
+	# call      %r13 <- add, $1, $2
 	ret.32      $3
 
 
diff --git a/validation/linear/builtin_unreachable0.c b/validation/linear/builtin_unreachable0.c
index 911ed7f9..4fc56473 100644
--- a/validation/linear/builtin_unreachable0.c
+++ b/validation/linear/builtin_unreachable0.c
@@ -14,12 +14,12 @@ foo:
 .L0:
 	<entry-point>
 	seteq.32    %r2 <- %arg1, $3
-	cbr         %r2, .L1, .L3
+	cbr         %r2, .L1, .L2
 
 .L1:
 	unreachable
 
-.L3:
+.L2:
 	ret.32      %arg1
 
 
diff --git a/validation/linear/builtin_unreachable1.c b/validation/linear/builtin_unreachable1.c
index 70f6674c..2fc1d728 100644
--- a/validation/linear/builtin_unreachable1.c
+++ b/validation/linear/builtin_unreachable1.c
@@ -16,9 +16,9 @@ int foo(int c)
 foo:
 .L0:
 	<entry-point>
-	cbr         %arg1, .L3, .L2
+	cbr         %arg1, .L1, .L2
 
-.L3:
+.L1:
 	ret.32      $1
 
 .L2:
diff --git a/validation/linear/call-inline.c b/validation/linear/call-inline.c
index dfd49b62..1ad785ee 100644
--- a/validation/linear/call-inline.c
+++ b/validation/linear/call-inline.c
@@ -13,6 +13,6 @@ int i3(void) { return (***fun)(); }		// C99,C11 6.5.3.2p4
  *
  * check-output-ignore
  * check-output-excludes: load
- * check-output-excludes: call
+ * check-output-excludes: \\tcall
  * check-output-pattern(5): ret\\..* \\$42
  */
diff --git a/validation/mem2reg/cond-expr.c b/validation/mem2reg/cond-expr.c
index 8acb00ac..2474d65d 100644
--- a/validation/mem2reg/cond-expr.c
+++ b/validation/mem2reg/cond-expr.c
@@ -9,6 +9,6 @@ int foo(int a, int b, int c)
  * check-name: cond-expr
  * check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file
  * check-output-ignore
- * check-output-pattern(2): phi\\.
- * check-output-pattern(3): phisrc\\.
+ * check-output-pattern(1): phi\\.
+ * check-output-pattern(2): phisrc\\.
  */
diff --git a/validation/mem2reg/cond-expr5.c b/validation/mem2reg/cond-expr5.c
index a3ce5e3a..beef8f25 100644
--- a/validation/mem2reg/cond-expr5.c
+++ b/validation/mem2reg/cond-expr5.c
@@ -15,7 +15,6 @@ int foo(int p, int q, int a)
  * check-output-ignore
  * check-output-excludes: load\\.
  * check-output-excludes: store\\.
- * check-output-excludes: phi\\..*, .*, .*
- * check-output-pattern(3): phi\\.
- * check-output-pattern(5): phisrc\\.
+ * check-output-pattern(2): phi\\.
+ * check-output-pattern(4): phisrc\\.
  */
diff --git a/validation/optim/cse-size.c b/validation/optim/cse-size.c
index 5b31420c..0c0c2d14 100644
--- a/validation/optim/cse-size.c
+++ b/validation/optim/cse-size.c
@@ -1,7 +1,7 @@
 static void foo(void)
 {
 	unsigned short p = 0;
-	int x;
+	int x = 1;
 
 	for (;;)
 		if (p)
@@ -13,5 +13,6 @@ static void foo(void)
  * check-command: test-linearize -Wno-decl $file
  *
  * check-output-ignore
- * check-output-pattern(2): phi\\.
+ * check-output-excludes: phi\\.
+ * check-output-excludes: cbr
  */
diff --git a/validation/optim/memops-missed01.c b/validation/optim/memops-missed01.c
new file mode 100644
index 00000000..fc616f19
--- /dev/null
+++ b/validation/optim/memops-missed01.c
@@ -0,0 +1,23 @@
+void bar(int);
+
+void foo(void)
+{
+	char buf[1] = { 42 };
+	const char *p = buf;
+	const char **q = &p;
+	int ch = 0;
+	switch (**q) {
+	case 4:
+		ch = 2;
+	}
+	bar(ch);
+}
+
+/*
+ * check-name: memops-missed01
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-excludes: store\\.
+ * check-output-excludes: load\\.
+ */
diff --git a/validation/optim/memops-missed02.c b/validation/optim/memops-missed02.c
new file mode 100644
index 00000000..6f028649
--- /dev/null
+++ b/validation/optim/memops-missed02.c
@@ -0,0 +1,14 @@
+void foo(int a[])
+{
+	int i, val;
+	for (;; i++)
+		val = a[i] ? a[i] : val;
+}
+
+/*
+ * check-name: memops-missed02
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-pattern(1): load\\.
+ */
diff --git a/validation/optim/merge_bbe-adjust_phi.c b/validation/optim/merge_bbe-adjust_phi.c
new file mode 100644
index 00000000..6a8ebb73
--- /dev/null
+++ b/validation/optim/merge_bbe-adjust_phi.c
@@ -0,0 +1,23 @@
+extern int array[2];
+
+static inline int stupid_select(int idx)
+{
+	if (idx)
+		idx = 0;
+	return array[idx];
+}
+
+int select(void)
+{
+	int d = stupid_select(-1);
+	return d;
+}
+
+/*
+ * check-name: merge_bbe-adjust_phi
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-excludes: phisrc\\.
+ * check-output-excludes: phi\\.
+ */