[PATCH 0/4] fix 2 problems with phi-sources

[PATCH 0/4] fix 2 problems with phi-sources

[Luc Van Oostenryck]

This series fixes two problems relatd to phi-sources:
1) fix and improve the check that protects try_to_simplify_bb()
2) fix remove_merging_phisrc() which couldn't handle the case
   where there is several CFG edges between two basic blocks.

Luc Van Oostenryck (4):
  additional testcase for remove_merging_phisrc()
  correctly count phi arguments
  better check validity of phi-sources
  fix remove_merging_phisrc()

 flow.c                          | 53 ++++++++++++++++++++++++++-------
 validation/optim/multi-phisrc.c | 23 ++++++++++++++
 validation/optim/phi-count00.c  | 27 +++++++++++++++++
 3 files changed, 92 insertions(+), 11 deletions(-)
 create mode 100644 validation/optim/multi-phisrc.c
 create mode 100644 validation/optim/phi-count00.c

-- 
2.31.1

[PATCH 1/4] additional testcase for remove_merging_phisrc()

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/optim/multi-phisrc.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)
 create mode 100644 validation/optim/multi-phisrc.c

diff --git a/validation/optim/multi-phisrc.c b/validation/optim/multi-phisrc.c
new file mode 100644
index 000000000000..c6f21f2db15a
--- /dev/null
+++ b/validation/optim/multi-phisrc.c
@@ -0,0 +1,24 @@
+void fun(void);
+
+void foo(int p, int a)
+{
+	if (p == p) {
+		switch (p) {
+		case 0:
+			break;
+		case 1:
+			a = 0;
+		}
+	}
+	if (a)
+		fun();
+}
+
+/*
+ * check-name: multi-phisrc
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-excludes: phi
+ */
-- 
2.31.1

[PATCH 2/4] correctly count phi arguments

[Luc Van Oostenryck]

In a phi-node,pseudo_list_size() can't be used for counting its arguments
because VOIDs must be ignored.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                         | 18 +++++++++++++++++-
 validation/optim/phi-count00.c | 27 +++++++++++++++++++++++++++
 2 files changed, 44 insertions(+), 1 deletion(-)
 create mode 100644 validation/optim/phi-count00.c

diff --git a/flow.c b/flow.c
index cb94fcf20834..58807432b3aa 100644
--- a/flow.c
+++ b/flow.c
@@ -189,6 +189,22 @@ out:
 	return false;
 }
 
+///
+// count the true number of argument of a phi-node
+// VOID arguments must be ignored, so pseudo_list_size() can't be used for this.
+static int phi_count(struct instruction *node)
+{
+	pseudo_t phi;
+	int n = 0;
+
+	FOR_EACH_PTR(node->phi_list, phi) {
+		if (phi == VOID)
+			continue;
+		n++;
+	} END_FOR_EACH_PTR(phi);
+	return n;
+}
+
 /*
  * When we reach here, we have:
  *  - a basic block that ends in a conditional branch and
@@ -211,7 +227,7 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 	 * simplify_symbol_usage()/conversion to SSA form.
 	 * No sane simplification can be done when we have this.
 	 */
-	bogus = bb_list_size(bb->parents) != pseudo_list_size(first->phi_list);
+	bogus = bb_list_size(bb->parents) != phi_count(first);
 
 	FOR_EACH_PTR(first->phi_list, phi) {
 		struct instruction *def = phi->def;
diff --git a/validation/optim/phi-count00.c b/validation/optim/phi-count00.c
new file mode 100644
index 000000000000..38db0edaea0e
--- /dev/null
+++ b/validation/optim/phi-count00.c
@@ -0,0 +1,27 @@
+inline int inl(int d, int e, int f)
+{
+	switch (d) {
+	case 0:
+		return e;
+	case 1:
+		return f;
+	default:
+		return 0;
+	}
+}
+
+void foo(int a, int b, int c)
+{
+	while (1) {
+		if (inl(a, b, c))
+			break;
+	}
+}
+
+/*
+ * check-name: phi-count00
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-pattern(0,2): phisrc
+ */
-- 
2.31.1

[PATCH 3/4] better check validity of phi-sources

[Luc Van Oostenryck]

Transformations made by try_to_simplify_bb() are invalid if
there isn't a one-to-one correspondence between the BB's parents
and the phi-sources of the phi-node(s) in the BB.

This correspondence is currently checked by checking if the number
of phi-sources and the number of parent are equal, but this is
only an approximation.

Change this check into an exact one, using the fact that BBs in
the parent list and phi-sources in the phi_list are in the same order.

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

diff --git a/flow.c b/flow.c
index 58807432b3aa..c866dec80480 100644
--- a/flow.c
+++ b/flow.c
@@ -190,19 +190,24 @@ out:
 }
 
 ///
-// count the true number of argument of a phi-node
-// VOID arguments must be ignored, so pseudo_list_size() can't be used for this.
-static int phi_count(struct instruction *node)
+// check if the sources of a phi-node match with the parent BBs
+static bool phi_check(struct instruction *node)
 {
+	struct basic_block *bb;
 	pseudo_t phi;
-	int n = 0;
 
+	PREPARE_PTR_LIST(node->bb->parents, bb);
 	FOR_EACH_PTR(node->phi_list, phi) {
-		if (phi == VOID)
+		if (phi == VOID || !phi->def)
 			continue;
-		n++;
+		if (phi->def->bb != bb)
+			return false;
+		NEXT_PTR_LIST(bb);
 	} END_FOR_EACH_PTR(phi);
-	return n;
+	if (bb)
+		return false;
+	FINISH_PTR_LIST(bb);
+	return true;
 }
 
 /*
@@ -227,7 +232,7 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 	 * simplify_symbol_usage()/conversion to SSA form.
 	 * No sane simplification can be done when we have this.
 	 */
-	bogus = bb_list_size(bb->parents) != phi_count(first);
+	bogus = !phi_check(first);
 
 	FOR_EACH_PTR(first->phi_list, phi) {
 		struct instruction *def = phi->def;
-- 
2.31.1

[PATCH 4/4] fix remove_merging_phisrc()

[Luc Van Oostenryck]

The current implementation of remove_merging_phisrc() can't work correctly
when these phi-sources belong to a basic block with several children
to the same target basic block (this happens commonly with OP_SWITCH).

Fix this by directly scanning the source basic block for the presence
of any phi-source. Once identified, the processing is kept unchanged:
remove these phi-sources if a sibling phi-source will 'overwrite' them
in the target block.

Fixes: 2fdaca9e7175e62f08d259f5cb3ec7c9725bba68
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                          | 30 ++++++++++++++++++++----------
 validation/optim/multi-phisrc.c |  1 -
 2 files changed, 20 insertions(+), 11 deletions(-)

diff --git a/flow.c b/flow.c
index c866dec80480..d46d0ee1bb7e 100644
--- a/flow.c
+++ b/flow.c
@@ -843,21 +843,26 @@ static int retarget_parents(struct basic_block *bb, struct basic_block *target)
 	return REPEAT_CFG_CLEANUP;
 }
 
-static void remove_merging_phisrc(struct basic_block *top, struct instruction *insn)
+static void remove_merging_phisrc(struct instruction *insn, struct basic_block *bot)
 {
-	struct instruction *user = insn->phi_node;
+	struct instruction *node = insn->phi_node;
 	pseudo_t phi;
 
-	FOR_EACH_PTR(user->phi_list, phi) {
+	if (!node) {
+		kill_instruction(insn);
+		return;
+	}
+
+	FOR_EACH_PTR(node->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);
+		if (phisrc->bb == bot) {
+			kill_instruction(insn);
+			return;
+		}
 	} END_FOR_EACH_PTR(phi);
 }
 
@@ -901,6 +906,14 @@ static int merge_bb(struct basic_block *top, struct basic_block *bot)
 		replace_bb_in_list(&bb->parents, bot, top, 1);
 	} END_FOR_EACH_PTR(bb);
 
+	FOR_EACH_PTR(top->insns, insn) {
+		if (!insn->bb)
+			continue;
+		if (insn->opcode != OP_PHISOURCE)
+			continue;
+		remove_merging_phisrc(insn, bot);
+	} END_FOR_EACH_PTR(insn);
+
 	kill_instruction(delete_last_instruction(&top->insns));
 	FOR_EACH_PTR(bot->insns, insn) {
 		if (!insn->bb)
@@ -910,9 +923,6 @@ static int merge_bb(struct basic_block *top, struct basic_block *bot)
 		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);
diff --git a/validation/optim/multi-phisrc.c b/validation/optim/multi-phisrc.c
index c6f21f2db15a..ff31c0834e58 100644
--- a/validation/optim/multi-phisrc.c
+++ b/validation/optim/multi-phisrc.c
@@ -17,7 +17,6 @@ void foo(int p, int a)
 /*
  * check-name: multi-phisrc
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-excludes: phi
-- 
2.31.1