[PATCH 0/4] phisrc fixes

[PATCH 0/4] phisrc fixes

[Luc Van Oostenryck]

This series fixes problems with the creation and placement of phisrcs.

Patch 1 is a preparatory step for patch 4 but fixes a very problem
of its own.
Patch 2 & 3 are the main fixes.
Patch 4 is a small improvement but also avoid divergence in the code
regarding the changes made in patch 3.

Note: I'm very sure there is still others bugs in the same corner but
      at least these patch improve the situation a bit.
Note: Only one patch has a regression test. For the other 3, it's
      to have some examples but this doesn't fit very well into the current
      testsuite.
      
This serie can also be found on the 'sent/broken-phisrc' of
	git://github.com/lucvoo/sparse.git

Luc Van Oostenryck (4):
  volatile loads must not be simplified
  fix superfluous phisrc
  fix phisrc mixup
  missing load simplification

 flow.c                       | 23 ++++++++++++++++-------
 memops.c                     | 13 ++++++-------
 validation/memops-volatile.c | 21 +++++++++++++++++++++
 3 files changed, 43 insertions(+), 14 deletions(-)
 create mode 100644 validation/memops-volatile.c

[PATCH 1/4] volatile loads must not be simplified

[Luc Van Oostenryck]

memops.c:simplify_loads() tries to simplify all loads,
even volatile ones.
For example, on the following code:
	static int foo(volatile int *a, int v)
	{
		*a = v;
		return *a;
	}

test-linearize returns something like:
	foo:
		store.32    %arg2 -> 0[%arg1]
		ret.32      %arg2

while the correct output is more like:
	foo:
		store.32    %arg2 -> 0[%arg1]
		load.32     %r5 <- 0[%arg1]
		ret.32      %r5

The fix is to simply ignore loads with the 'volatile' modifier.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 memops.c                     |  3 +++
 validation/memops-volatile.c | 21 +++++++++++++++++++++
 2 files changed, 24 insertions(+)
 create mode 100644 validation/memops-volatile.c

diff --git a/memops.c b/memops.c
index 45bd3401..6dac1f57 100644
--- a/memops.c
+++ b/memops.c
@@ -99,6 +99,9 @@ static void simplify_loads(struct basic_block *bb)
 			/* Check for illegal offsets.. */
 			check_access(insn);
 
+			if (insn->type->ctype.modifiers & MOD_VOLATILE)
+				continue;
+
 			RECURSE_PTR_REVERSE(insn, dom) {
 				int dominance;
 				if (!dom->bb)
diff --git a/validation/memops-volatile.c b/validation/memops-volatile.c
new file mode 100644
index 00000000..0f3e12ad
--- /dev/null
+++ b/validation/memops-volatile.c
@@ -0,0 +1,21 @@
+static int foo(volatile int *a, int v)
+{
+	*a = v;
+	return *a;
+}
+
+/*
+ * check-name: memops-volatile
+ * check-command: test-linearize $file
+ *
+ * check-output-start
+foo:
+.L0:
+	<entry-point>
+	store.32    %arg2 -> 0[%arg1]
+	load.32     %r5 <- 0[%arg1]
+	ret.32      %r5
+
+
+ * check-output-end
+ */
-- 
2.11.0

[PATCH 2/4] fix superfluous phisrc

[Luc Van Oostenryck]

In some case more phisrc are created than expected.
For example, on the following code:
	static int foo(int a, int b)
	{
		int i, x = 0;
		switch (a) {
		case  0: i = 0; break;
		case  1: i = 1; break;
		default: i = -1; break;
		}
		if (b)
			x = i;
		return x;
	}

test-linearize returns something like:
	foo:
	.L0:
		<entry-point>
		phisrc.32   %phi2(x) <- $0
		phisrc.32   %phi3(x) <- $0
		phisrc.32   %phi4(x) <- $0
		switch      %arg1, 0 -> .L2, 1 -> .L3, default -> .L4
	.L2:
		phisrc.32   %phi6(i) <- $0
		br          .L1
	.L3:
		phisrc.32   %phi7(i) <- $1
		br          .L1
	.L4:
		phisrc.32   %phi8(i) <- $0xffffffff
		br          .L1
	.L1:
		br          %arg2, .L5, .L6
	.L5:
		phi.32      %r3 <- %phi6(i), %phi7(i), %phi8(i)
		phisrc.32   %phi5(x) <- %r3
		br          .L6
	.L6:
		phi.32      %r4 <- %phi2(x), %phi3(x), %phi4(x), %phi5(x)
		ret.32      %r4

where we can notice that %phi2, %phi3 and %phi4 in .L0 and .L6
are completly redundant, only one of them is needed. This also
violates the usual semantic of phi-nodes: one phi for each parent bb.

There is as much %phi such created as there is cases in the switch
statement and the same problem also occurs with an if-else and 2 %phis.

Whats' happening is the following:
- find_dominating_parents() search dominators for .L6
- try first parent: .L1, find nothing, thus recurses
- .L1 has 3 parents (the three cases): .L2, .L3, .L4
- each of them has .L0 as dominator, it's recorded as such but three times

The problem is fixed by checking the dominators list and refusing to create
more than one phisrc in the same basic block.

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

diff --git a/flow.c b/flow.c
index 7db9548f..d8e253b1 100644
--- a/flow.c
+++ b/flow.c
@@ -316,6 +316,17 @@ int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom
 	return 1;
 }
 
+static int phisrc_in_bb(struct pseudo_list *list, struct basic_block *bb)
+{
+	pseudo_t p;
+	FOR_EACH_PTR(list, p) {
+		if (p->def->bb == bb)
+			return 1;
+	} END_FOR_EACH_PTR(p);
+
+	return 0;
+}
+
 static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
 	struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
 	int local, int loads)
@@ -358,6 +369,8 @@ no_dominance:
 		continue;
 
 found_dominator:
+		if (dominators && phisrc_in_bb(*dominators, parent))
+			continue;
 		br = delete_last_instruction(&parent->insns);
 		phi = alloc_phi(parent, one->target, one->size);
 		phi->ident = phi->ident ? : pseudo->ident;
-- 
2.11.0

[PATCH 3/4] fix phisrc mixup

[Luc Van Oostenryck]

In some cases phi sources are all mixed-up.
For example, on the following case:
	static int foo(void)
	{
		int i = 6;
		int j = 1;
		do {
			if (i != 6)
				i++;
			i++;
		} while (i != j);
		return j;
	}

test-linearize returns something like:
	.L0:
		phisrc.32   %phi3(i) <- $6
		phisrc.32   %phi7(i) <- $6
		br          .L1
	.L1:
		phi.32      %r1(i) <- %phi7(i), %phi8(i)
		setne.32    %r2 <- %r1(i), $6
		br          %r2, .L4, .L5
	.L4:
		add.32      %r4 <- %r1(i), $1
		phisrc.32   %phi5(i) <- %r4
		br          .L5
	.L5:
		phi.32      %r5 <- %phi3(i), %phi4(i), %phi5(i)
		add.32      %r6(i) <- %r5, $1
		phisrc.32   %phi4(i) <- %r6(i)
		phisrc.32   %phi8(i) <- %r6(i)
		setne.32    %r8 <- %r6(i), $1
		br          %r8, .L1, .L6
	.L6:
		ret.32      $1

The phi-node in .L5 is odd: .L5 has 2 parents (.L1 & .L4), we thus
expect to have 2 phisrc, one in .L1 and another one in .L4. There is
other oddities with phisrc: the redundant ones in .L0 and .L5.
In fact there is some sort of mixup with the phi & phisrc of .L1
and the ones in .L5 (and investigation showed it doesn't come from
further simplification phase but are already there since the creation
of these phi & phisrc).

The fix essentially consists in a revert of
  (commit cf07903a "Don't bother finding dominating loads if we have to search multiple paths")
which was already partially reverted in
  (commit c040f2e0 "Remove incorrect left-over from (not useful) old load-load dominance trials.")

We then get the more expected:
	.L0:
		phisrc.32   %phi6(i) <- $6
		br          .L1
	.L1:
		phi.32      %r1(i) <- %phi6(i), %phi7(i)
		setne.32    %r2 <- %r1(i), $6
		phisrc.32   %phi3(i) <- %r1(i)
		br          %r2, .L4, .L5
	.L4:
		add.32      %r4 <- %r1(i), $1
		phisrc.32   %phi4(i) <- %r4
		br          .L5
	.L5:
		phi.32      %r5 <- %phi3(i), %phi4(i)
		add.32      %r6(i) <- %r5, $1
		phisrc.32   %phi7(i) <- %r6(i)
		setne.32    %r8 <- %r6(i), $1
		br          %r8, .L1, .L6
	.L6:
		ret.32      $1

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

diff --git a/flow.c b/flow.c
index d8e253b1..ef07b6db 100644
--- a/flow.c
+++ b/flow.c
@@ -329,15 +329,13 @@ static int phisrc_in_bb(struct pseudo_list *list, struct basic_block *bb)
 
 static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
 	struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
-	int local, int loads)
+	int local)
 {
 	struct basic_block *parent;
 
 	if (!bb->parents)
 		return !!local;
 
-	if (bb_list_size(bb->parents) > 1)
-		loads = 0;
 	FOR_EACH_PTR(bb->parents, parent) {
 		struct instruction *one;
 		struct instruction *br;
@@ -355,8 +353,6 @@ static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
 			}
 			if (!dominance)
 				continue;
-			if (one->opcode == OP_LOAD && !loads)
-				continue;
 			goto found_dominator;
 		} END_FOR_EACH_PTR_REVERSE(one);
 no_dominance:
@@ -364,7 +360,7 @@ no_dominance:
 			continue;
 		parent->generation = generation;
 
-		if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local, loads))
+		if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local))
 			return 0;
 		continue;
 
@@ -467,7 +463,7 @@ found:
 	bb->generation = generation;
 
 	dominators = NULL;
-	if (!find_dominating_parents(pseudo, insn, bb, generation, &dominators, local, 1))
+	if (!find_dominating_parents(pseudo, insn, bb, generation, &dominators, local))
 		return 0;
 
 	/* This happens with initial assignments to structures etc.. */
-- 
2.11.0

[PATCH 4/4] missing load simplification

[Luc Van Oostenryck]

In memops:find_dominating_parents(), the 'load-load optimization'
(see commit cf07903a "Don't bother finding dominating loads if ...")
cause some loads simplification to be missed.
For example, with the following code:
	int foo(int *i, int *j)
	{
		*i = 6;
		*j = 1;

		do {
			if (*i != 6)
				(*i)++;
			(*i)++;
		} while (*i != *j);

		return *j;
	}

test-linearize returns something like:
	foo:
	.L0:
		<entry-point>
		store.32    $6 -> 0[%arg1]
		store.32    $1 -> 0[%arg2]
		br          .L1

	.L1:
		load.32     %r4 <- 0[%arg1]
		setne.32    %r5 <- %r4, $6
		br          %r5, .L4, .L5

	.L4:
		add.32      %r8 <- %r4, $1
		store.32    %r8 -> 0[%arg1]
		br          .L5

	.L5:
		load.32     %r10 <- 0[%arg1]
		add.32      %r11 <- %r10, $1
		store.32    %r11 -> 0[%arg1]
		load.32     %r15 <- 0[%arg2]
		setne.32    %r16 <- %r11, %r15
		br          %r16, .L1, .L6

	.L6:
		ret.32      %r15

where we can notice that the first load in .L5 is not needed,
the value could be retrieved from %r4 and %r8, like:
	@@ -8,15 +8,17 @@
	 .L1:
	 	load.32     %r4 <- 0[%arg1]
	 	setne.32    %r5 <- %r4, $6
	+	phisrc.32   %phi4 <- %r4
	 	br          %r5, .L4, .L5

	 .L4:
	 	add.32      %r8 <- %r4, $1
	 	store.32    %r8 -> 0[%arg1]
	+	phisrc.32   %phi5 <- %r8
	 	br          .L5

	 .L5:
	-	load.32     %r10 <- 0[%arg1]
	+	phi.32      %r10 <- %phi4, %phi5
	 	add.32      %r11 <- %r10, $1
	 	store.32    %r11 -> 0[%arg1]
	 	load.32     %r15 <- 0[%arg2]

The fix essentially consists in reverting commit cf07903a but on
memops.c's version of find_dominating_parents().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 memops.c | 10 +++-------
 1 file changed, 3 insertions(+), 7 deletions(-)

diff --git a/memops.c b/memops.c
index 6dac1f57..5efdd6f2 100644
--- a/memops.c
+++ b/memops.c
@@ -18,12 +18,10 @@
 
 static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
 	struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
-	int local, int loads)
+	int local)
 {
 	struct basic_block *parent;
 
-	if (bb_list_size(bb->parents) > 1)
-		loads = 0;
 	FOR_EACH_PTR(bb->parents, parent) {
 		struct instruction *one;
 		struct instruction *br;
@@ -41,8 +39,6 @@ static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
 			}
 			if (!dominance)
 				continue;
-			if (one->opcode == OP_LOAD && !loads)
-				continue;
 			goto found_dominator;
 		} END_FOR_EACH_PTR_REVERSE(one);
 no_dominance:
@@ -50,7 +46,7 @@ no_dominance:
 			continue;
 		parent->generation = generation;
 
-		if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local, loads))
+		if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local))
 			return 0;
 		continue;
 
@@ -124,7 +120,7 @@ static void simplify_loads(struct basic_block *bb)
 			generation = ++bb_generation;
 			bb->generation = generation;
 			dominators = NULL;
-			if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local, 1)) {
+			if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local)) {
 				/* This happens with initial assignments to structures etc.. */
 				if (!dominators) {
 					if (local) {
-- 
2.11.0