[PATCH 0/2] adjust phi-sources when merging BBs

[PATCH 0/2] adjust phi-sources when merging BBs

[Luc Van Oostenryck]

When merging BBs, phi-sources from the bottom BB should 'overwrite'
the ones from the top BB which should be ignored. This is currently
the not case and both phi-sources are present in the resulting BB.
This doesn't make much sense for the corresponding phi-node and
also causes other problems like hindering further simplifications.

This series contains a testcase and a patch for this.

Luc Van Oostenryck (2):
  add testcase for phi-adjusting during BB merge
  adjust phi-sources when merging BBs

 flow.c                                  | 28 +++++++++++++++++++++++++
 validation/optim/merge_bbe-adjust_phi.c | 23 ++++++++++++++++++++
 2 files changed, 51 insertions(+)
 create mode 100644 validation/optim/merge_bbe-adjust_phi.c

-- 
2.29.2

[PATCH 1/2] add testcase for phi-adjusting during BB merge

[Luc Van Oostenryck]

When merging BBs, phi-sources from the bottom BB should 'overwrite'
the ones from the top BB which should be ignored.

Add a testcase from the incoming fix.

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

diff --git a/validation/optim/merge_bbe-adjust_phi.c b/validation/optim/merge_bbe-adjust_phi.c
new file mode 100644
index 000000000000..de4c54cc6d49
--- /dev/null
+++ b/validation/optim/merge_bbe-adjust_phi.c
@@ -0,0 +1,24 @@
+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-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-excludes: phisrc\\.
+ * check-output-excludes: phi\\.
+ */
-- 
2.29.2

[PATCH 2/2] adjust phi-sources when merging BBs

[Luc Van Oostenryck]

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 kind 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>
---
 flow.c                                  | 28 +++++++++++++++++++++++++
 validation/optim/merge_bbe-adjust_phi.c |  1 -
 2 files changed, 28 insertions(+), 1 deletion(-)

diff --git a/flow.c b/flow.c
index ef8d04e5827f..a74769c37659 100644
--- a/flow.c
+++ b/flow.c
@@ -723,6 +723,32 @@ void vrfy_flow(struct entrypoint *ep)
 	assert(!entry);
 }
 
+static void adjust_phi(struct basic_block *top, struct instruction *insn)
+{
+	struct pseudo_user *pu;
+
+	FOR_EACH_PTR(insn->target->users, pu) {
+		struct instruction *user;
+		pseudo_t phi;
+
+		if (!pu)
+			continue;
+		user = pu->insn;
+		assert(user->opcode == OP_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);
+	} END_FOR_EACH_PTR(pu);
+}
+
 void pack_basic_blocks(struct entrypoint *ep)
 {
 	struct basic_block *bb;
@@ -804,6 +830,8 @@ out:
 			if (!insn->bb)
 				continue;
 			assert(insn->bb == bb);
+			if (insn->opcode == OP_PHISOURCE)
+				adjust_phi(parent, insn);
 			insn->bb = parent;
 			add_instruction(&parent->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 de4c54cc6d49..6a8ebb73a62d 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\\.
-- 
2.29.2