cfg: remove phi-sources when merging BBs

When merging two basic blocks, it may happen that both of theses
blocks contain a phi-source for the same phi-node. In this case,
only the phi-source from the bottom BB must be taken in account,
it kinda overwrites the value from the top BB and the phi-source
from the top BB must be ignored, in fact it must be removed.

However, it is not the case and this extra phi-source creates
different kinds of problems. Among other things, it hinders
further simplifications. For example, the following code:

	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;
	}

should boil down to a simple dereference of the array with
an index of zero, like:
	select:
		load.32     %r8 <- 0[array]
		ret.32      %r8

but currently gives:
	select:
		phisrc.32   %phi3(idx) <- $0xffffffff
		phisrc.32   %phi4(idx) <- $0
		phi.32      %r12(idx) <- %phi3(idx), %phi4(idx)
		sext.64     %r5 <- (32) %r12(idx)
		mul.64      %r6 <- %r5, $4
		add.64      %r7 <- %r6, array
		load.32     %r8 <- 0[%r7]
		ret.32      %r8

This patch takes care of the problem by:
* when merging 2 BBs, check when reaching a phi-source in the bottom BB
* if one is found, look after sibling phi-sources
* remove such sibling if belonging to the top BB.
With this change, the code above gives:
	select:
		phisrc.32   %phi4(idx) <- $0
		phi.32      %r12(idx) <- %phi4(idx)
		sext.64     %r5 <- (32) %r12(idx)
		mul.64      %r6 <- %r5, $4
		add.64      %r7 <- %r6, array
		load.32     %r8 <- 0[%r7]
		ret.32      %r8

which can the be simplified into the expected result.

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

2 files changed, 42 insertions, 1 deletions

diff --git a/flow.c b/flow.c
index 9ae8612a..566f4637 100644
--- a/flow.c
+++ b/flow.c
@@ -43,6 +43,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.
@@ -723,6 +742,24 @@ void vrfy_flow(struct entrypoint *ep)
 	assert(!entry);
 }
 
+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);
+}
+
 ///
 // merge two BBs
 // @top: the first BB to be merged
@@ -748,6 +785,11 @@ static int merge_bb(struct basic_block *top, struct basic_block *bot)
 		if (!insn->bb)
 			continue;
 		assert(insn->bb == bot);
+		switch (insn->opcode) {
+		case OP_PHISOURCE:
+			remove_merging_phisrc(top, insn);
+			break;
+		}
 		insn->bb = top;
 		add_instruction(&top->insns, insn);
 	} END_FOR_EACH_PTR(insn);
diff --git a/validation/optim/merge_bbe-adjust_phi.c b/validation/optim/merge_bbe-adjust_phi.c
index de4c54cc..6a8ebb73 100644
--- a/validation/optim/merge_bbe-adjust_phi.c
+++ b/validation/optim/merge_bbe-adjust_phi.c
@@ -16,7 +16,6 @@ int select(void)
 /*
  * check-name: merge_bbe-adjust_phi
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-excludes: phisrc\\.