[PATCH 00/16] instructions killing & operands usage

[PATCH 00/16] instructions killing & operands usage

[Luc Van Oostenryck]

This serie aims at solving a number of problems caused by
imcomplete, missing or wrong handling of operands usage when
killing an instruction

Luc Van Oostenryck (16):
  add killing of OP_SLICEs
  add killing of OP_PHISOURCEs
  add helper kill_use_list()
  fix killing of OP_PHIs
  fix clear_phi(), replace it by kill_instruction()
  remove unused clear_phi()
  fix killing of otherwise not-handled instructions
  kill_instruction() may need to be forced or not
  add killing of pure calls
  fix killing OP_CALL via pointers
  add killing of non-volatile loads
  add killing of stores
  fix killing of rewritten loads
  use kill_instruction() when killing an OP_PHI during CSE
  use kill_instruction() when killing any instructions during CSE
  fix OP_PHI usage in try_to_simplify_bb()

 cse.c                            | 15 +--------
 flow.c                           |  7 ++--
 flow.h                           | 11 +++++-
 simplify.c                       | 73 +++++++++++++++++++++++++++++++---------
 validation/kill-cse.c            | 21 ++++++++++++
 validation/kill-load.c           | 17 ++++++++++
 validation/kill-phi-node.c       |  9 +++++
 validation/kill-phi-ttsbb.c      | 28 +++++++++++++++
 validation/kill-phisrc.c         | 21 ++++++++++++
 validation/kill-pure-call.c      | 17 ++++++++++
 validation/kill-rewritten-load.c | 16 +++++++++
 validation/kill-slice.c          | 19 +++++++++++
 validation/kill-store.c          | 16 +++++++++
 13 files changed, 236 insertions(+), 34 deletions(-)
 create mode 100644 validation/kill-cse.c
 create mode 100644 validation/kill-load.c
 create mode 100644 validation/kill-phi-ttsbb.c
 create mode 100644 validation/kill-phisrc.c
 create mode 100644 validation/kill-pure-call.c
 create mode 100644 validation/kill-rewritten-load.c
 create mode 100644 validation/kill-slice.c
 create mode 100644 validation/kill-store.c

-- 
2.11.0

[PATCH 01/16] add killing of OP_SLICEs

[Luc Van Oostenryck]

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

diff --git a/simplify.c b/simplify.c
index 2a1f0b200..90e45bf1a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -203,6 +203,7 @@ void kill_instruction(struct instruction *insn)
 	case OP_PTRCAST:
 	case OP_SETVAL:
 	case OP_NOT: case OP_NEG:
+	case OP_SLICE:
 		kill_use(&insn->src1);
 		break;
 
diff --git a/validation/kill-slice.c b/validation/kill-slice.c
new file mode 100644
index 000000000..00db0e0f7
--- /dev/null
+++ b/validation/kill-slice.c
@@ -0,0 +1,19 @@
+struct bar {
+	int x;
+	int y[2];
+};
+struct bar bar(void);
+
+int foo(void)
+{
+	int x = bar().x;
+	return x & 0;
+}
+
+/*
+ * check-name: kill-slice
+ * check-command: test-linearize -Wno-decl $file
+ * check-output-ignore
+ *
+ * check-output-excludes: slice\\.
+ */
-- 
2.11.0

[PATCH 02/16] add killing of OP_PHISOURCEs

[Luc Van Oostenryck]

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

diff --git a/simplify.c b/simplify.c
index 90e45bf1a..ced63bfa3 100644
--- a/simplify.c
+++ b/simplify.c
@@ -210,6 +210,9 @@ void kill_instruction(struct instruction *insn)
 	case OP_PHI:
 		clear_phi(insn);
 		break;
+	case OP_PHISOURCE:
+		kill_use(&insn->phi_src);
+		break;
 
 	case OP_SYMADDR:
 		repeat_phase |= REPEAT_SYMBOL_CLEANUP;
diff --git a/validation/kill-phisrc.c b/validation/kill-phisrc.c
new file mode 100644
index 000000000..f00dbed24
--- /dev/null
+++ b/validation/kill-phisrc.c
@@ -0,0 +1,21 @@
+int foo(int a, int b)
+{
+	int r = a + b;
+
+	if (a && 0) {
+		int s = r;
+		if (b)
+			s = 0;
+		(void) s;
+	}
+
+	return 0;
+}
+
+/*
+ * check-name: kill-phisrc
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-excludes: add\\.
+ */
-- 
2.11.0

[PATCH 03/16] add helper kill_use_list()

[Luc Van Oostenryck]

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

diff --git a/simplify.c b/simplify.c
index ced63bfa3..d4e730894 100644
--- a/simplify.c
+++ b/simplify.c
@@ -182,6 +182,16 @@ void kill_use(pseudo_t *usep)
 	}
 }
 
+static void kill_use_list(struct pseudo_list *list)
+{
+	pseudo_t p;
+	FOR_EACH_PTR(list, p) {
+		if (p == VOID)
+			continue;
+		kill_use(THIS_ADDRESS(p));
+	} END_FOR_EACH_PTR(p);
+}
+
 void kill_instruction(struct instruction *insn)
 {
 	if (!insn || !insn->bb)
-- 
2.11.0

[PATCH 04/16] fix killing of OP_PHIs

[Luc Van Oostenryck]

OP_PHIs were killed by calling clear_phi() but this function
only replaces the phi node's sources by VOID without adjusting
the usage of these sources.

Fix this by instead calling kill_use() on each of the sources
via the newly created helper kill_use_list().

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

diff --git a/simplify.c b/simplify.c
index d4e730894..17f1e2b61 100644
--- a/simplify.c
+++ b/simplify.c
@@ -218,7 +218,7 @@ void kill_instruction(struct instruction *insn)
 		break;
 
 	case OP_PHI:
-		clear_phi(insn);
+		kill_use_list(insn->phi_list);
 		break;
 	case OP_PHISOURCE:
 		kill_use(&insn->phi_src);
diff --git a/validation/kill-phi-node.c b/validation/kill-phi-node.c
index 88de9f962..cff62b649 100644
--- a/validation/kill-phi-node.c
+++ b/validation/kill-phi-node.c
@@ -9,6 +9,15 @@ void foo(int a, int *b, unsigned int g)
 		d = 8;
 }
 
+int bar(void);
+int bar(void)
+{
+	int i;
+	for (i = 0; i; i--)
+		;
+	return 0;
+}
+
 /*
  * check-name: kill-phi-node
  * check-command: test-linearize $file
-- 
2.11.0

[PATCH 05/16] fix clear_phi(), replace it by kill_instruction()

[Luc Van Oostenryck]

clear_phi() only replaces a phi-node's sources by VOID
without adjusting the usage of these sources.
As such it can't be used for cleaning things before
removing an OP_PHI.

Fix this by replacing calls to clear_phi() by calls
to kill_instruction().

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

diff --git a/simplify.c b/simplify.c
index 17f1e2b61..ddd0aa9c5 100644
--- a/simplify.c
+++ b/simplify.c
@@ -110,7 +110,7 @@ static int if_convert_phi(struct instruction *insn)
 	 * the conditional branch too.
 	 */
 	insert_select(source, br, insn, p1, p2);
-	clear_phi(insn);
+	kill_instruction(insn);
 	return REPEAT_CSE;
 }
 
@@ -140,7 +140,7 @@ static int clean_up_phi(struct instruction *insn)
 	if (same) {
 		pseudo_t pseudo = last ? last->src1 : VOID;
 		convert_instruction_target(insn, pseudo);
-		clear_phi(insn);
+		kill_instruction(insn);
 		return REPEAT_CSE;
 	}
 
@@ -1142,7 +1142,7 @@ int simplify_instruction(struct instruction *insn)
 		return simplify_cast(insn);
 	case OP_PHI:
 		if (dead_insn(insn, NULL, NULL, NULL)) {
-			clear_phi(insn);
+			kill_use_list(insn->phi_list);
 			return REPEAT_CSE;
 		}
 		return clean_up_phi(insn);
-- 
2.11.0

[PATCH 06/16] remove unused clear_phi()

[Luc Van Oostenryck]

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

diff --git a/simplify.c b/simplify.c
index ddd0aa9c5..82ae97ae9 100644
--- a/simplify.c
+++ b/simplify.c
@@ -26,16 +26,6 @@ static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseud
 	return first_basic_block(source->parents);
 }
 
-static void clear_phi(struct instruction *insn)
-{
-	pseudo_t phi;
-
-	insn->bb = NULL;
-	FOR_EACH_PTR(insn->phi_list, phi) {
-		*THIS_ADDRESS(phi) = VOID;
-	} END_FOR_EACH_PTR(phi);
-}

[PATCH 07/16] fix killing of otherwise not-handled instructions

[Luc Van Oostenryck]

The instructions which are otherwise not handled in
kill_instruction() were simply ignored  but they must
still have their ->bb set to NULL.

Fix this by separating the default case from OP_ENTRY,
the only kind that must be ignored in all circonstances.

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

diff --git a/simplify.c b/simplify.c
index 82ae97ae9..1fbad1060 100644
--- a/simplify.c
+++ b/simplify.c
@@ -228,9 +228,11 @@ void kill_instruction(struct instruction *insn)
 		break;
 
 	case OP_ENTRY:
-	default:
 		/* ignore */
 		return;
+
+	default:
+		break;
 	}
 
 	insn->bb = NULL;
-- 
2.11.0

[PATCH 08/16] kill_instruction() may need to be forced or not

[Luc Van Oostenryck]

There is essentially three cases where kill_instruction() is
called:
1) when implicitely removing an instruction via
   kill_use()/remove_usage() once all users of (the target of)
   this instruction have been removed and so this instruction
   become unneeded.
2) when explicitely removing a specific instruction.
3) when explicitely removing all instructions in a basic block
   because it became unreachable.

For 'pure' instructions, like the arithmetic operators, these
three cases can be handled exactly the same but for instructions
having side-effects, special care is needed.
For them case 1) should do nothing while cases 2) & 3) should
remove the instruction and adjust the usage of its operands like
for normal instructions.

To handle this gracefully:
- rename kill_instruction() into kill_insn()
- add a new argument ('force') to kill_insn()
- create kill_instruction() & kill_instruction_force() as inline
  functions calling kill_insn() with 'force' set respectively to 0 & 1.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c     |  3 +--
 flow.h     | 11 ++++++++++-
 simplify.c | 11 ++++++++++-
 3 files changed, 21 insertions(+), 4 deletions(-)

diff --git a/flow.c b/flow.c
index ef07b6db9..8409fac60 100644
--- a/flow.c
+++ b/flow.c
@@ -759,13 +759,12 @@ void kill_bb(struct basic_block *bb)
 	struct basic_block *child, *parent;
 
 	FOR_EACH_PTR(bb->insns, insn) {
-		kill_instruction(insn);
+		kill_instruction_force(insn);
 		kill_defs(insn);
 		/*
 		 * We kill unreachable instructions even if they
 		 * otherwise aren't "killable" (e.g. volatile loads)
 		 */
-		insn->bb = NULL;
 	} END_FOR_EACH_PTR(insn);
 	bb->insns = NULL;
 
diff --git a/flow.h b/flow.h
index 370aaddf1..31ed80d40 100644
--- a/flow.h
+++ b/flow.h
@@ -23,9 +23,18 @@ extern int simplify_instruction(struct instruction *);
 
 extern void kill_bb(struct basic_block *);
 extern void kill_use(pseudo_t *);
-extern void kill_instruction(struct instruction *);
 extern void kill_unreachable_bbs(struct entrypoint *ep);
 
+extern void kill_insn(struct instruction *, int force);
+static inline void kill_instruction(struct instruction *insn)
+{
+	kill_insn(insn, 0);
+}
+static inline void kill_instruction_force(struct instruction *insn)
+{
+	kill_insn(insn, 1);
+}
+
 void check_access(struct instruction *insn);
 void convert_load_instruction(struct instruction *, pseudo_t);
 void rewrite_load_instruction(struct instruction *, struct pseudo_list *);
diff --git a/simplify.c b/simplify.c
index 1fbad1060..b8944f0f7 100644
--- a/simplify.c
+++ b/simplify.c
@@ -182,7 +182,16 @@ static void kill_use_list(struct pseudo_list *list)
 	} END_FOR_EACH_PTR(p);
 }
 
-void kill_instruction(struct instruction *insn)
+/*
+ * kill an instruction:
+ * - remove it from its bb
+ * - remove the usage of all its operands
+ * If forse is zero, the normal case, the function only for
+ * instructions free of (possible) side-effects. Otherwise
+ * the function does that unconditionally (must only be used
+ * for unreachable instructions.
+ */
+void kill_insn(struct instruction *insn, int force)
 {
 	if (!insn || !insn->bb)
 		return;
-- 
2.11.0

[PATCH 09/16] add killing of pure calls

[Luc Van Oostenryck]

OP_CALL were ignored by kill_instruction() but there are two cases
were something can or must be done:
1) if the function is pure, it is free of side-effects and can thus
   be optimized away like others instructions.
2) if force-killed then we need to adjust the usage of all the arguments.

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

diff --git a/simplify.c b/simplify.c
index b8944f0f7..cacf81f9f 100644
--- a/simplify.c
+++ b/simplify.c
@@ -236,6 +236,17 @@ void kill_insn(struct instruction *insn, int force)
 		kill_use(&insn->cond);
 		break;
 
+	case OP_CALL:
+		if (!force) {
+			/* a "pure" function can be killed too */
+			if (!(insn->func->type == PSEUDO_SYM))
+				return;
+			if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
+				return;
+		}
+		kill_use_list(insn->arguments);
+		break;
+
 	case OP_ENTRY:
 		/* ignore */
 		return;
diff --git a/validation/kill-pure-call.c b/validation/kill-pure-call.c
new file mode 100644
index 000000000..d3f78c026
--- /dev/null
+++ b/validation/kill-pure-call.c
@@ -0,0 +1,17 @@
+int side(int a);
+int pure(int a) __attribute__((pure));
+
+int keep(int a) { return side(a) && 0; }
+int kill(int a) { return pure(a) && 0; }
+
+/*
+ * check-name: kill-pure-call
+ * check-command: test-linearize -Wno-decl $file
+ * check-description:
+ *	See that the call is optimized away but only
+ *	when the function is "pure".
+ *
+ * check-output-ignore
+ * check-output-contains: call\\..* side
+ * check-output-excludes: call\\..* pure
+ */
-- 
2.11.0

[PATCH 10/16] fix killing OP_CALL via pointers

[Luc Van Oostenryck]

When killing an OP_CALL corresponding to a function pointer
the ->func field needs also to have its usage adjusted.

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

diff --git a/simplify.c b/simplify.c
index cacf81f9f..b80d05b87 100644
--- a/simplify.c
+++ b/simplify.c
@@ -245,6 +245,8 @@ void kill_insn(struct instruction *insn, int force)
 				return;
 		}
 		kill_use_list(insn->arguments);
+		if (insn->func->type == PSEUDO_REG)
+			kill_use(&insn->func);
 		break;
 
 	case OP_ENTRY:
-- 
2.11.0

[PATCH 11/16] add killing of non-volatile loads

[Luc Van Oostenryck]

OP_LOADs were ignored by kill_instruction() but there are two cases
were something can or must be done:
1) if the is not a volatile one, it is free of side-effects and can thus
   be optimized away like others instructions.
2) if force-killed then we need to adjust the usage of its operand.

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

diff --git a/simplify.c b/simplify.c
index b80d05b87..a27f6a33a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -249,6 +249,12 @@ void kill_insn(struct instruction *insn, int force)
 			kill_use(&insn->func);
 		break;
 
+	case OP_LOAD:
+		if (!force && insn->type->ctype.modifiers & MOD_VOLATILE)
+			return;
+		kill_use(&insn->src);
+		break;
+
 	case OP_ENTRY:
 		/* ignore */
 		return;
diff --git a/validation/kill-load.c b/validation/kill-load.c
new file mode 100644
index 000000000..45fb83e4b
--- /dev/null
+++ b/validation/kill-load.c
@@ -0,0 +1,17 @@
+int keep(volatile int *p)	{ return *p && 0; }
+int kill(int *p, int i)		{ return *p && 0; }
+void ind(volatile int *p,int i)	{ int v = i++; if (i && 0) p[v]; }
+
+
+/*
+ * check-name: kill-load
+ * check-command: test-linearize -Wno-decl $file
+ * check-description:
+ *	Check that loads are optimized away but only
+ *	when needed:
+ *	- non-volatile
+ *	- bb unreachable.
+ *
+ * check-output-ignore
+ * check-output-pattern-1-times: load\\.
+ */
-- 
2.11.0

[PATCH 12/16] add killing of stores

[Luc Van Oostenryck]

OP_STOREs were ignored by kill_instruction() but if it is force-killed
because the basic block it belong became unreachable then we need to
adjust the usage of its operands.

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

diff --git a/simplify.c b/simplify.c
index a27f6a33a..804467f0d 100644
--- a/simplify.c
+++ b/simplify.c
@@ -255,6 +255,13 @@ void kill_insn(struct instruction *insn, int force)
 		kill_use(&insn->src);
 		break;
 
+	case OP_STORE:
+		if (!force)
+			return;
+		kill_use(&insn->src);
+		kill_use(&insn->target);
+		break;
+
 	case OP_ENTRY:
 		/* ignore */
 		return;
diff --git a/validation/kill-store.c b/validation/kill-store.c
new file mode 100644
index 000000000..8f7253226
--- /dev/null
+++ b/validation/kill-store.c
@@ -0,0 +1,16 @@
+void keep(int *p)	 { *p = 0; }
+void kill(int *p, int i) { if (i && 0) *p = 0; }
+void dead(int *p, int i) { int v = i++; if (i && 0) p[v] = 0; }
+
+
+/*
+ * check-name: kill-store
+ * check-command: test-linearize -Wno-decl $file
+ * check-description:
+ *	Check that stores are optimized away but only
+ *	when needed:
+ *	- bb unreachable.
+ *
+ * check-output-ignore
+ * check-output-pattern-1-times: store\\.
+ */
-- 
2.11.0

[PATCH 13/16] fix killing of rewritten loads

[Luc Van Oostenryck]

OP_LOADs removed by rewrite_load_instruction() had their ->bb simply
set to NULL the usage of its operand was not adjusted.

Fix that by calling kill_instruction().

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

diff --git a/flow.c b/flow.c
index 8409fac60..fbac9336c 100644
--- a/flow.c
+++ b/flow.c
@@ -401,7 +401,7 @@ void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *domi
 	 * pseudo.
 	 */
 	FOR_EACH_PTR(dominators, phi) {
-		phi->def->bb = NULL;
+		kill_instruction(phi->def);
 	} END_FOR_EACH_PTR(phi);
 	convert_load_instruction(insn, new);
 	return;
diff --git a/validation/kill-rewritten-load.c b/validation/kill-rewritten-load.c
new file mode 100644
index 000000000..31b895e53
--- /dev/null
+++ b/validation/kill-rewritten-load.c
@@ -0,0 +1,16 @@
+int foo(int i)
+{
+	i++;
+	if (i && 0)
+		i;
+	return 0;
+}
+
+
+/*
+ * check-name: kill-rewritten-load
+ * check-command: test-linearize -Wno-decl $file
+ * check-output-ignore
+ *
+ * check-output-excludes: add\\.
+ */
-- 
2.11.0

[PATCH 14/16] use kill_instruction() when killing an OP_PHI during CSE

[Luc Van Oostenryck]

cse_one_instruction() contains some code to be executed when
an OP_PHI is eliminated. This code is roughly equivalent to
what is done in kill_instruction() for OP_PHI but not complete
since it doesn't recursively try to kill others instructions
which are used only by this OP_PHI.

Fix this and avoid duplicated code by replacing this code by
a call to kill_instruction().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 cse.c | 10 +---------
 1 file changed, 1 insertion(+), 9 deletions(-)

diff --git a/cse.c b/cse.c
index e8fbe344f..165b862af 100644
--- a/cse.c
+++ b/cse.c
@@ -252,15 +252,7 @@ static struct instruction * cse_one_instruction(struct instruction *insn, struct
 	convert_instruction_target(insn, def->target);
 
 	if (insn->opcode == OP_PHI) {
-		/* Remove the instruction from PHI users */
-		pseudo_t phi;
-		FOR_EACH_PTR(insn->phi_list, phi) {
-			struct pseudo_user *pu;
-			FOR_EACH_PTR(phi->users, pu) {
-				if (pu->insn == insn)
-					DELETE_CURRENT_PTR(pu);
-			} END_FOR_EACH_PTR(pu);
-		} END_FOR_EACH_PTR(phi);
+		kill_instruction(insn);
 	}
 
 	insn->opcode = OP_NOP;
-- 
2.11.0

[PATCH 15/16] use kill_instruction() when killing any instructions during CSE

[Luc Van Oostenryck]

Instructions removed during CSE had their ->bb simply set to NULL
and the usage of their operand was not adjusted.

Fix that by calling kill_instruction().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 cse.c                 |  7 +------
 validation/kill-cse.c | 21 +++++++++++++++++++++
 2 files changed, 22 insertions(+), 6 deletions(-)
 create mode 100644 validation/kill-cse.c

diff --git a/cse.c b/cse.c
index 165b862af..048a3eb79 100644
--- a/cse.c
+++ b/cse.c
@@ -251,12 +251,7 @@ static struct instruction * cse_one_instruction(struct instruction *insn, struct
 {
 	convert_instruction_target(insn, def->target);
 
-	if (insn->opcode == OP_PHI) {
-		kill_instruction(insn);
-	}
-
-	insn->opcode = OP_NOP;
-	insn->bb = NULL;
+	kill_instruction(insn);
 	repeat_phase |= REPEAT_CSE;
 	return def;
 }
diff --git a/validation/kill-cse.c b/validation/kill-cse.c
new file mode 100644
index 000000000..2e2b10246
--- /dev/null
+++ b/validation/kill-cse.c
@@ -0,0 +1,21 @@
+int foo(int a)
+{
+	return ((a == 0) + 1) != ((a == 0) + 1);
+}
+
+/*
+ * check-name: kill-cse
+ * check-description:
+ *	Verify that instructions removed at CSE are
+ *	properly adjust the usage of their operands.
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+foo:
+.L0:
+	<entry-point>
+	ret.32      $0
+
+
+ * check-output-end
+ */
-- 
2.11.0

[PATCH 16/16] fix OP_PHI usage in try_to_simplify_bb()

[Luc Van Oostenryck]

In try_to_simplify_bb(), simplification is attempted when a constant
phisrc whose corresponding phi-node control a conditional branch.
In this case, for the path between the phisrc and the conditional
branch, the following OP_PHI is sort of unneeded since the constant
determine which branch will be taken.

If this simplification can be made, it means that the OP_PHI
doesn't depend anymore on the constant phisrc. In fact the OP_PHI's bb
won't be anymore reachable from the constant phisrc's bb.
But currently, the OP_PHI usage is not adjusted and this leads to all
sort of oddities and causes to miss further simplifications.

The situation can be more concretly seen on test-linearize's output,
here an extract of Linux's kernel/futex.c:get_futex_key().
	.L594:
		...
		br          %r1294, .L651, .L656
	.L651:
		phisrc.32   %phi85 <- $1
		br          .L649
	.L656:
		...
		and.64      %r1340 <- %r1339, $1
		phisrc.32   %phi87 <- %r1340
		phi.32      %r1343 <- %phi85, %phi87
		br          %r1343, .L649, .L648

The constant phisrc is %phi85 in .L651, the OP_PHI and the conditional
branch are .L656's last instructions (which have been packed with its
now unique parent which is sign of a problem). One can see that the
OP_PHi seems to depend on %phi85 (it's in its phi_list) but in fact
depends only on %phi87 (.L656 can't be reached from .L651 where %phi85
is defined since after the simplification .L651 directly branches to
one of the .L656's children, here .L649).

The fix consists in adjusting the OP_PHI's usage when the
simplification is made.

On the same code extract we can now see that the situation is more
"normal". In fact the OP_PHI have now been able to be optimized away
together, as well as .L651:
	.L594:
		...
		br          %r1294, .L649, .L656
	.L656:
		...
		and.64      %r1340 <- %r1339, $1
		br          %r1340, .L649, .L648

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                      |  2 ++
 validation/kill-phi-ttsbb.c | 28 ++++++++++++++++++++++++++++
 2 files changed, 30 insertions(+)
 create mode 100644 validation/kill-phi-ttsbb.c

diff --git a/flow.c b/flow.c
index fbac9336c..088c21785 100644
--- a/flow.c
+++ b/flow.c
@@ -121,6 +121,8 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 			continue;
 		changed |= rewrite_branch(source, &br->bb_true, bb, target);
 		changed |= rewrite_branch(source, &br->bb_false, bb, target);
+		if (changed)
+			kill_use(THIS_ADDRESS(phi));
 	} END_FOR_EACH_PTR(phi);
 	return changed;
 }
diff --git a/validation/kill-phi-ttsbb.c b/validation/kill-phi-ttsbb.c
new file mode 100644
index 000000000..178a65d19
--- /dev/null
+++ b/validation/kill-phi-ttsbb.c
@@ -0,0 +1,28 @@
+int def(void);
+void use(int);
+
+static int foo(int a, int b)
+{
+	int c;
+
+	if (a)
+		c = 1;
+	else
+		c = def();
+
+	if (c)
+		use(1);
+	else
+		use(0);
+}
+
+/*
+ * check-name: kill-phi-ttsbb
+ * check-description:
+ *	Verify if OP_PHI usage is adjusted after successful try_to_simplify_bb()
+ * check-command: test-linearize $file
+ * check-output-ignore
+ *
+ * check-output-excludes: phi\\.
+ * check-output-excludes: phisrc\\.
+ */
-- 
2.11.0