[PATCH 8/8] trivial-phi: remove more complex trivial phi-nodes

[Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx>]

In a set of related phi-nodes and phi-sources if all phi-sources
but one correspond to the target of one of the phi-sources, then
no phi-nodes is needed and all %phis can be replaced by the unique
source.
For example, code like:
	int test(void);
	int foo(int a)
	{
		while (test())
			a ^= 0;
		return a;
	}

used to produce an IR with a phi-node for 'a', like:
	foo:
		phisrc.32   %phi2(a) <- %arg1
		br          .L4
	.L4:
		phi.32      %r7(a) <- %phi2(a), %phi3(a)
		call.32     %r1 <- test
		cbr         %r1, .L2, .L5
	.L2:
		phisrc.32   %phi3(a) <- %r7(a)
		br          .L4
	.L5:
		ret.32      %r7(a)

but since 'a ^= 0' is a no-op, the value of 'a' is in fact
never mofified. This can be seen in the phi-node where its
second operand (%phi3) is the same as its target (%r7). So
the only possible value for 'a' is the one from the first
operand, its initial value (%arg1).

Once this trivial phi-nodes is removed, the IR is the expected:
	foo:
		br          .L4
	.L4:
		call.32     %r1 <- test
		cbr         %r1, .L4, .L5
	.L5:
		ret.32      %arg1

Removing these trivial phi-nodes will usually trigger other
simplifications, especially those concerning the CFG.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx>
---
 simplify.c                      | 19 +++++++++++++++++--
 validation/optim/trivial-phis.c |  1 -
 2 files changed, 17 insertions(+), 3 deletions(-)

diff --git a/simplify.c b/simplify.c
index 1fa46548a..696d9d587 100644
--- a/simplify.c
+++ b/simplify.c
@@ -180,11 +180,17 @@ static int if_convert_phi(struct instruction *insn)
 //
 // A phi-node is trivial if it has a single possible result:
 //	# all operands are the same
+//	# the operands are themselves defined by a chain or cycle of phi-nodes
+//		and the set of all operands involved contains a single value
+//		not defined by these phi-nodes
 // Since the result is unique, these phi-nodes can be removed.
-static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn)
+static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn, struct pseudo_list **list)
 {
+	pseudo_t target = insn->target;
 	pseudo_t phi;
 
+	add_pseudo(list, target);
+
 	FOR_EACH_PTR(insn->phi_list, phi) {
 		struct instruction *def;
 		pseudo_t src;
@@ -203,6 +209,14 @@ static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn)
 		}
 		if (src == pseudo)
 			continue;
+		if (src == target)
+			continue;
+		if (DEF_OPCODE(def, src) == OP_PHI) {
+			if (pseudo_in_list(*list, src))
+				continue;
+			if ((pseudo = trivial_phi(pseudo, def, list)))
+				continue;
+		}
 		return NULL;
 	} END_FOR_EACH_PTR(phi);
 
@@ -211,9 +225,10 @@ static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn)
 
 static int clean_up_phi(struct instruction *insn)
 {
+	struct pseudo_list *list = NULL;
 	pseudo_t pseudo;
 
-	if ((pseudo = trivial_phi(NULL, insn))) {
+	if ((pseudo = trivial_phi(NULL, insn, &list))) {
 		convert_instruction_target(insn, pseudo);
 		kill_instruction(insn);
 		return REPEAT_CSE;
diff --git a/validation/optim/trivial-phis.c b/validation/optim/trivial-phis.c
index 754affb73..8af093c1a 100644
--- a/validation/optim/trivial-phis.c
+++ b/validation/optim/trivial-phis.c
@@ -7,7 +7,6 @@ void foo(int a)
 /*
  * check-name: trivial phis
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-excludes: phi\\.
-- 
2.18.0