[PATCH 0/8] fix uses of killed instructions

[PATCH 0/8] fix uses of killed instructions

[Luc Van Oostenryck]

The series fixes some issues regarding the operands of killed
instructions not having their usage adjusted.
The main apparent consequence of this situation is that
some instructions which should be considered as unneeded are
not removed from the code as expected. This can sometimes have
a cascading effect that can be "quite interesting".

There is some closely related issues that remains,
for example the situation of the exotic instructions.
It's also possible that something is missing with OP_SYMADDR.

OP_LOAD, OP_STORE & OP_CALL are completly ignored and their
correct handling need another approach, so they're also
ignored by this series.


*ATTENTION*
The test cases in this series depends on some
features I added to the test-suite that I posted the
10th November with the "fix discarded label statement" serie.


Luc Van Oostenryck (8):
  kill uses of replaced instructions
  fix killing OP_SETVAL instructions
  fix killing OP_PHI instructions
  fix killing OP_CAST & friends
  fix killing OP_SELECT
  fix killing OP_COMPUTEDGOTO
  explicitely ignore killing OP_ENTRY
  cleanup kill_instruction()

 simplify.c                      | 74 ++++++++++++++++++++++++++++-------------
 validation/kill-casts.c         | 22 ++++++++++++
 validation/kill-computedgoto.c  | 17 ++++++++++
 validation/kill-phi-node.c      | 18 ++++++++++
 validation/kill-replaced-insn.c | 61 +++++++++++++++++++++++++++++++++
 validation/kill-select.c        | 16 +++++++++
 6 files changed, 184 insertions(+), 24 deletions(-)
 create mode 100644 validation/kill-casts.c
 create mode 100644 validation/kill-computedgoto.c
 create mode 100644 validation/kill-phi-node.c
 create mode 100644 validation/kill-replaced-insn.c
 create mode 100644 validation/kill-select.c

-- 

[PATCH 1/8] kill uses of replaced instructions

[Luc Van Oostenryck]

When an instruction is replaced by a pseudo, the 'usage' of its
operands should be removed too but it's not the case.

The fix consists in calling kill_use() for each operands after
the pseudo is replaced.
Not all types of instruction are considered, only those which
can be replaced by a pseudo.

The following example illustrate the situation. When looking at
the output of test-linearize, the following function:

	static int kill_add(int a, int b)
	{
		return (a + b) && 0;
	}

without the patch, gives this output:

	kill_add:
		add.32      %r3 <- %arg1, %arg2
		ret.32      $0

The 'add' instruction is obviously unneeded but nevertheless present.

Before any optimization the code was something like:

	kill_add:
		add.32      %r3 <- %arg1, %arg2
		and_bool.32 %r4 <- %r3, $0
		ret.32      %r4

During the simplification phase, the result of the 'and' instruction (%r4)
have been replaced by '0' and the instruction itself is discarded.
But '%r3' usage has not been adjusted and the further phases are not
aware that '%r3' is not needed anymore and so the 'add' instruction is kept
while not needed by anything.

With the patch the 'add' instruction is correctly discarded, giving the
expected output:

	kill_add:
		ret.32      $0

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                      | 20 +++++++++++++++
 validation/kill-replaced-insn.c | 54 +++++++++++++++++++++++++++++++++++++++++
 2 files changed, 74 insertions(+)
 create mode 100644 validation/kill-replaced-insn.c

diff --git a/simplify.c b/simplify.c
index b5cd0ea7..85da5bec 100644
--- a/simplify.c
+++ b/simplify.c
@@ -253,6 +253,26 @@ static inline int constant(pseudo_t pseudo)
 static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 {
 	convert_instruction_target(insn, pseudo);
+
+	switch (insn->opcode) {
+	case OP_SEL:
+	case OP_RANGE:
+		kill_use(&insn->src3);
+	case OP_BINARY ... OP_BINCMP_END:
+		kill_use(&insn->src2);
+	case OP_NOT:
+	case OP_NEG:
+	case OP_SYMADDR:
+	case OP_CAST:
+	case OP_SCAST:
+	case OP_FPCAST:
+	case OP_PTRCAST:
+		kill_use(&insn->src1);
+		break;
+
+	default:
+		assert(0);
+	}
 	insn->bb = NULL;
 	return REPEAT_CSE;
 }
diff --git a/validation/kill-replaced-insn.c b/validation/kill-replaced-insn.c
new file mode 100644
index 00000000..be031b6c
--- /dev/null
+++ b/validation/kill-replaced-insn.c
@@ -0,0 +1,54 @@
+// See if the replaced operation is effectively killed or not
+
+static int kill_add(int a, int b)
+{
+	return (a + b) && 0;
+}
+
+static int kill_scast(short a)
+{
+	return ((int) a) && 0;
+}
+
+static int kill_ucast(unsigned char a)
+{
+	return ((int) a) && 0;
+}
+
+static int kill_pcast(int *a)
+{
+	return ((void*) a) && 0;
+}
+
+static int kill_fcast(double a)
+{
+	return ((int) a) && 0;
+}
+
+static int kill_select(int a)
+{
+	return (a ? 1 : 0) && 0;
+}
+
+static int kill_load(int *a)
+{
+	return *a && 0;
+}
+
+static int kill_store(int *a)
+{
+	return (*a = 1) && 0;
+}
+
+/*
+ * check-name: kill-replaced-insn
+ * check-command: test-linearize $file
+ *
+ * check-output-ignore
+ * check-output-excludes: add\\.
+ * check-output-excludes: scast\\.
+ * check-output-excludes: \\<cast\\.
+ * check-output-excludes: ptrcast\\.
+ * check-output-excludes: fpcast\\.
+ * check-output-excludes: sel\\.
+ */
-- 
2.10.2

[PATCH 2/8] fix killing OP_SETVAL instructions

[Luc Van Oostenryck]

Currently, kill_instruction() ignore OP_SETVAL instructions
with the result that some instructions are not optimized away
as expected.

For example, when looking at the output of test-linearize,
the following function:

	static int kill_setval(void)
	{
	l:
		return &&l && 0;
	}

gives the following output:

	kill_setval:
		set.64      %r6 <- .L1
		ret.32      $0

The 'set' instruction is obviously unneeded but nevertheless present.

With the patch, the output is the expected:

	kill_set:
		ret.32      $0

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                      | 1 +
 validation/kill-replaced-insn.c | 7 +++++++
 2 files changed, 8 insertions(+)

diff --git a/simplify.c b/simplify.c
index 85da5bec..d07ca1b1 100644
--- a/simplify.c
+++ b/simplify.c
@@ -195,6 +195,7 @@ void kill_instruction(struct instruction *insn)
 		repeat_phase |= REPEAT_CSE;
 		return;
 
+	case OP_SETVAL:
 	case OP_NOT: case OP_NEG:
 		insn->bb = NULL;
 		kill_use(&insn->src1);
diff --git a/validation/kill-replaced-insn.c b/validation/kill-replaced-insn.c
index be031b6c..92021877 100644
--- a/validation/kill-replaced-insn.c
+++ b/validation/kill-replaced-insn.c
@@ -30,6 +30,12 @@ static int kill_select(int a)
 	return (a ? 1 : 0) && 0;
 }
 
+static int kill_setval(int a)
+{
+l:
+	return &&l && 0;
+}
+
 static int kill_load(int *a)
 {
 	return *a && 0;
@@ -51,4 +57,5 @@ static int kill_store(int *a)
  * check-output-excludes: ptrcast\\.
  * check-output-excludes: fpcast\\.
  * check-output-excludes: sel\\.
+ * check-output-excludes: set\\.
  */
-- 
2.10.2

[PATCH 3/8] fix killing OP_PHI instructions

[Luc Van Oostenryck]

Currently kill_instruction() doesn't do anything with the
sources of OP_PHI instructions. But when these instructions
are removed the 'usage' of the associated sources must also
be removed. This is not done and as result the instructions
producing the phi-sources are not optimized away as expected.

This patch fixes that by calling clear_phi() when killing a
phi-instruction.

For example, when looking at the output of test-linearize,
the following function:
	void foo(int a, int *b, unsigned int g);
	void foo(int a, int *b, unsigned int g)
	{
		int d = 0;

		if ((!a || *b) && g)
			d = 16;
		else
			d = 8;
	}

gives this output without the patch:
	foo:
		br          %arg1, .L1, .L2
	.L1:
		phisrc.32   %phi1 <- $1
		br          .L3
	.L2:
		load.32     %r3 <- 0[%arg2]
		phisrc.32   %phi2 <- %r3
		br          .L3
	.L3:
		ret

The 'phisrc' instructions are obviously unneeded but nevertheless present.

With the patch, the output is much closer to what's expected:
	foo:
		br          %arg1, .L3, .L2
	.L2:
		load.32     %r3 <- 0[%arg2]
		br          .L3
	.L3:
		ret

Note 1) The 'load' instruction is also dead and should have been removed
but it's separate problem.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                 |  1 +
 validation/kill-phi-node.c | 18 ++++++++++++++++++
 2 files changed, 19 insertions(+)
 create mode 100644 validation/kill-phi-node.c

diff --git a/simplify.c b/simplify.c
index d07ca1b1..421b28f2 100644
--- a/simplify.c
+++ b/simplify.c
@@ -203,6 +203,7 @@ void kill_instruction(struct instruction *insn)
 		return;
 
 	case OP_PHI:
+		clear_phi(insn);
 		insn->bb = NULL;
 		repeat_phase |= REPEAT_CSE;
 		return;
diff --git a/validation/kill-phi-node.c b/validation/kill-phi-node.c
new file mode 100644
index 00000000..88de9f96
--- /dev/null
+++ b/validation/kill-phi-node.c
@@ -0,0 +1,18 @@
+void foo(int a, int *b, unsigned int g);
+void foo(int a, int *b, unsigned int g)
+{
+	int d = 0;
+
+	if ((!a || *b) && g)
+		d = 16;
+	else
+		d = 8;
+}
+
+/*
+ * check-name: kill-phi-node
+ * check-command: test-linearize $file
+ *
+ * check-output-ignore
+ * check-output-excludes: phisrc\\.
+ */
-- 
2.10.2

[PATCH 4/8] fix killing OP_CAST & friends

[Luc Van Oostenryck]

Currently  kill_instruction() doesn't do anything with the
operands of casts instructions. But when theses instructions
are removed the operands 'usage' must be adjusted and this is
not done and as result the instructions producing the operands
of these casts are not optimized away as expected.

This patch fixes that by killing these casts the same way as others
unary instructions (OP_NOT & OP_NEG).

To illustrate the situation, the output of test-linearize
on the following code:
	extern void __abort(void);
	struct s {
		int elem:3;
	};
	void foo(struct s *x);
	void foo(struct s *x)
	{
		if (x->elem == 0) {
			if (x->elem != 0 && x->elem != 1)
				__abort();
		}
	}

gives this output without the patch:
	foo:
		load.32     %r2 <- 0[%arg1]
		cast.32     %r3 <- (3) %r2
		br          .L1
	.L1:
		ret

Since x->elem can't be at the same time == 0 & != 0, the inner if is never
true and the whole code should have been optimized away.
The 'cast' instruction is obviously not needed but nevertheless present.

With the patch, the output is much closer to what's expected:
	foo:
		load.32     %r2 <- 0[%arg1]
		br          .L1
	.L1:
		ret

Note 1) The 'load' instruction is also dead but it's a separate problem.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c              |  4 ++++
 validation/kill-casts.c | 22 ++++++++++++++++++++++
 2 files changed, 26 insertions(+)
 create mode 100644 validation/kill-casts.c

diff --git a/simplify.c b/simplify.c
index 421b28f2..939ba6af 100644
--- a/simplify.c
+++ b/simplify.c
@@ -195,6 +195,10 @@ void kill_instruction(struct instruction *insn)
 		repeat_phase |= REPEAT_CSE;
 		return;
 
+	case OP_CAST:
+	case OP_SCAST:
+	case OP_FPCAST:
+	case OP_PTRCAST:
 	case OP_SETVAL:
 	case OP_NOT: case OP_NEG:
 		insn->bb = NULL;
diff --git a/validation/kill-casts.c b/validation/kill-casts.c
new file mode 100644
index 00000000..cf52f246
--- /dev/null
+++ b/validation/kill-casts.c
@@ -0,0 +1,22 @@
+extern void __abort(void);
+
+struct s {
+	int elem:3;
+};
+
+void foo(struct s *x);
+void foo(struct s *x)
+{
+	if (x->elem == 0) {
+		if (x->elem != 0 && x->elem != 1)
+			__abort();
+	}
+}
+
+/*
+ * check-name: kill-casts
+ * check-command: test-linearize $file
+ *
+ * check-output-ignore
+ * check-output-excludes: cast\\.
+ */
-- 
2.10.2

[PATCH 5/8] fix killing OP_SELECT

[Luc Van Oostenryck]

Currently kill_instruction() doesn't do anything with the
operands of select instructions (OP_SELECT). But when these
instructions are removed we must also remove the operands 'usage'.
Without this the instructions which provides the select's
operands are not optimized away as expected.

This patch fixes this by doing for OP_SELECTs the basic
kill_instruction() for ternary instruction, like OP_RANGE.

As an example, when looking at the output of test-linearize,
the following code:

	void foo(int x)
	{
		unsigned int ui;

		ui = x + 1;
		ui = ui ? 0 : 1;
	}

gives this output:

	foo:
		add.32      %r2 <- %arg1, $1
		ret

Since the result of the ?: is never used, the whole code should be
optimized away. The 'select' instruction itself is indeed discarded
but the 'add' is not.

With the patch, the output is much closer to what's expected:

	foo:
		ret

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c               |  1 +
 validation/kill-select.c | 16 ++++++++++++++++
 2 files changed, 17 insertions(+)
 create mode 100644 validation/kill-select.c

diff --git a/simplify.c b/simplify.c
index 939ba6af..1dd1bda6 100644
--- a/simplify.c
+++ b/simplify.c
@@ -217,6 +217,7 @@ void kill_instruction(struct instruction *insn)
 		repeat_phase |= REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 		return;
 
+	case OP_SEL:
 	case OP_RANGE:
 		insn->bb = NULL;
 		repeat_phase |= REPEAT_CSE;
diff --git a/validation/kill-select.c b/validation/kill-select.c
new file mode 100644
index 00000000..445472be
--- /dev/null
+++ b/validation/kill-select.c
@@ -0,0 +1,16 @@
+void foo(int x);
+void foo(int x)
+{
+	unsigned int ui;
+
+	ui = x + 1;
+	ui = ui ? 0 : 1;
+}
+
+/*
+ * check-name: kill-select
+ * check-command: test-linearize $file
+ *
+ * check-output-ignore
+ * check-output-excludes: add\\.
+ */
-- 
2.10.2

[PATCH 6/8] fix killing OP_COMPUTEDGOTO

[Luc Van Oostenryck]

Currently kill_instruction() doesn't do anything with the
operands of computed gotos (OP_COMPUTEDGOTO). But when these
instructions are removed we must also remove the operands 'usage'.
Without this some instructions, which provides the select's
operands, are not optimized away as expected.

The fix consists by killing it's operand much like what is done for
conditional branches.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                     |  1 +
 validation/kill-computedgoto.c | 17 +++++++++++++++++
 2 files changed, 18 insertions(+)
 create mode 100644 validation/kill-computedgoto.c

diff --git a/simplify.c b/simplify.c
index 1dd1bda6..1be9b3d0 100644
--- a/simplify.c
+++ b/simplify.c
@@ -226,6 +226,7 @@ void kill_instruction(struct instruction *insn)
 		kill_use(&insn->src3);
 		return;
 	case OP_BR:
+	case OP_COMPUTEDGOTO:
 		insn->bb = NULL;
 		repeat_phase |= REPEAT_CSE;
 		if (insn->cond)
diff --git a/validation/kill-computedgoto.c b/validation/kill-computedgoto.c
new file mode 100644
index 00000000..3b3ed8ff
--- /dev/null
+++ b/validation/kill-computedgoto.c
@@ -0,0 +1,17 @@
+void foo(int a);
+void foo(int a)
+{
+	void *l = &&end + 3;
+
+end:
+	if (a * 0)
+		goto *l;
+}
+
+/*
+ * check-name: kill-computedgoto
+ * check-command: test-linearize $file
+ *
+ * check-output-ignore
+ * check-output-excludes: add\\.
+ */
-- 
2.10.2

[PATCH 7/8] explicitely ignore killing OP_ENTRY

[Luc Van Oostenryck]

It doesn't change anything, it's more for documentation
purpose.

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

diff --git a/simplify.c b/simplify.c
index 1be9b3d0..afbbb7b6 100644
--- a/simplify.c
+++ b/simplify.c
@@ -232,6 +232,10 @@ void kill_instruction(struct instruction *insn)
 		if (insn->cond)
 			kill_use(&insn->cond);
 		return;
+
+	case OP_ENTRY:
+		/* ignore */
+		return;
 	}
 }
 
-- 
2.10.2

[PATCH 8/8] cleanup kill_instruction()

[Luc Van Oostenryck]

No functional changes:
- factorize out the '->bb = NULL' and '|= REPEAT_CSE'.
- fall through the switch cases for ternary/bunary/unary ops.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c | 46 ++++++++++++++++++++--------------------------
 1 file changed, 20 insertions(+), 26 deletions(-)

diff --git a/simplify.c b/simplify.c
index afbbb7b6..fc69def1 100644
--- a/simplify.c
+++ b/simplify.c
@@ -188,12 +188,14 @@ void kill_instruction(struct instruction *insn)
 		return;
 
 	switch (insn->opcode) {
+	case OP_SEL:
+	case OP_RANGE:
+		kill_use(&insn->src3);
+		/* fall through */
+
 	case OP_BINARY ... OP_BINCMP_END:
-		insn->bb = NULL;
-		kill_use(&insn->src1);
 		kill_use(&insn->src2);
-		repeat_phase |= REPEAT_CSE;
-		return;
+		/* fall through */
 
 	case OP_CAST:
 	case OP_SCAST:
@@ -201,42 +203,34 @@ void kill_instruction(struct instruction *insn)
 	case OP_PTRCAST:
 	case OP_SETVAL:
 	case OP_NOT: case OP_NEG:
-		insn->bb = NULL;
 		kill_use(&insn->src1);
-		repeat_phase |= REPEAT_CSE;
-		return;
+		break;
 
 	case OP_PHI:
 		clear_phi(insn);
-		insn->bb = NULL;
-		repeat_phase |= REPEAT_CSE;
-		return;
+		break;
 
 	case OP_SYMADDR:
-		insn->bb = NULL;
-		repeat_phase |= REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
-		return;
+		repeat_phase |= REPEAT_SYMBOL_CLEANUP;
+		break;
 
-	case OP_SEL:
-	case OP_RANGE:
-		insn->bb = NULL;
-		repeat_phase |= REPEAT_CSE;
-		kill_use(&insn->src1);
-		kill_use(&insn->src2);
-		kill_use(&insn->src3);
-		return;
 	case OP_BR:
+		if (!insn->cond)
+			break;
+		/* fall through */
+
 	case OP_COMPUTEDGOTO:
-		insn->bb = NULL;
-		repeat_phase |= REPEAT_CSE;
-		if (insn->cond)
-			kill_use(&insn->cond);
-		return;
+		kill_use(&insn->cond);
+		break;
 
 	case OP_ENTRY:
 		/* ignore */
 		return;
 	}
+
+	insn->bb = NULL;
+	repeat_phase |= REPEAT_CSE;
+	return;
 }
 
 /*
-- 
2.10.2