[PATCH 0/9] fix usage when killing loads & stores

[PATCH 0/9] fix usage when killing loads & stores

[Luc Van Oostenryck]

This series contains 4 fixes for missing removal of
value or address usage when unneeded loads or stores
are killed during symbol simplification.

This series is available in the Git repository at:
  https://github.com/lucvoo/sparse-dev/tree/fix-missing-kills
  git://github.com/lucvoo/sparse-dev.git fix-missing-kills

----------------------------------------------------------------
Luc Van Oostenryck (9):
      add helpers for pseudo's user-list's size
      add testcase for bad killing of dominated stores
      add testcases for converted loads
      fix killing of converted loads
      kill dead stores when simplifying symbols
      use has_users() in dead_insn() too
      let kill_instruction() report if changes were made
      kill dead loads
      fix usage of deadborn loads

 flow.c                                | 23 ++++++-----------------
 flow.h                                | 10 +++++-----
 linearize.h                           | 10 ++++++++++
 memops.c                              | 11 +----------
 simplify.c                            | 34 +++++++++++++++++-----------------
 validation/mem2reg/load-deadborn.c    |  9 +++++++++
 validation/optim/load-converted.c     | 14 ++++++++++++++
 validation/optim/load-dead.c          | 11 +++++++++++
 validation/optim/load-semi-volatile.c | 25 +++++++++++++++++++++++++
 validation/optim/store-dominated.c    | 15 +++++++++++++++
 10 files changed, 113 insertions(+), 49 deletions(-)
 create mode 100644 validation/mem2reg/load-deadborn.c
 create mode 100644 validation/optim/load-converted.c
 create mode 100644 validation/optim/load-dead.c
 create mode 100644 validation/optim/load-semi-volatile.c
 create mode 100644 validation/optim/store-dominated.c

[PATCH 1/9] add testcases for converted loads

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/optim/load-converted.c     | 15 +++++++++++++++
 validation/optim/load-semi-volatile.c | 25 +++++++++++++++++++++++++
 2 files changed, 40 insertions(+)
 create mode 100644 validation/optim/load-converted.c
 create mode 100644 validation/optim/load-semi-volatile.c

diff --git a/validation/optim/load-converted.c b/validation/optim/load-converted.c
new file mode 100644
index 000000000..010c6bc7b
--- /dev/null
+++ b/validation/optim/load-converted.c
@@ -0,0 +1,15 @@
+static int foo(int *p, int i)
+{
+	int a = p[i];
+	int b = p[i];
+	return (a - b);
+}
+
+/*
+ * check-name: load-converted
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-excludes: add\.
+ */
diff --git a/validation/optim/load-semi-volatile.c b/validation/optim/load-semi-volatile.c
new file mode 100644
index 000000000..0e266e171
--- /dev/null
+++ b/validation/optim/load-semi-volatile.c
@@ -0,0 +1,25 @@
+struct s {
+	volatile int a;
+};
+
+struct s s;
+
+void foo(void)
+{
+	s;
+	s.a;
+}
+
+/*
+ * check-name: load-semi-volatile
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-pattern(1): load
+ *
+ * check-description:
+ *	The load at line 9 must be removed.
+ *	The load at line 10 is volatile and thus
+ *	must not be removed.
+ */
-- 
2.16.0

[PATCH 2/9] fix killing of converted loads

[Luc Van Oostenryck]

Converted loads are dead and can be removed but that
also means that the address usage need to be adjusted
which wasn't done.

Fix this by directly using kill_instruction().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                            | 4 +---
 validation/optim/load-converted.c | 1 -
 2 files changed, 1 insertion(+), 4 deletions(-)

diff --git a/flow.c b/flow.c
index 62658b920..c614a11d9 100644
--- a/flow.c
+++ b/flow.c
@@ -305,9 +305,7 @@ void convert_instruction_target(struct instruction *insn, pseudo_t src)
 void convert_load_instruction(struct instruction *insn, pseudo_t src)
 {
 	convert_instruction_target(insn, src);
-	/* Turn the load into a no-op */
-	insn->opcode = OP_LNOP;
-	insn->bb = NULL;
+	kill_instruction(insn);
 }
 
 static int overlapping_memop(struct instruction *a, struct instruction *b)
diff --git a/validation/optim/load-converted.c b/validation/optim/load-converted.c
index 010c6bc7b..7cbb53cf4 100644
--- a/validation/optim/load-converted.c
+++ b/validation/optim/load-converted.c
@@ -8,7 +8,6 @@ static int foo(int *p, int i)
 /*
  * check-name: load-converted
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-excludes: add\.
-- 
2.16.0

[PATCH 3/9] fix usage of deadborn loads

[Luc Van Oostenryck]

In some situations, loads and others instructions can be
unreachable already when linearized, for example in code like:
	void foo(int *ptr)
	{
		return;
		*ptr;
	}
Such loads are detected in find_dominating_stores() and must
be discarded. This is done and the load have its opcode set
to OP_LNOP (wich is only useful for debugging) but it's
address is left as being used by the load.

Fix this by removing the address usage.

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

diff --git a/flow.c b/flow.c
index c614a11d9..528c8f32d 100644
--- a/flow.c
+++ b/flow.c
@@ -479,7 +479,7 @@ static int find_dominating_stores(pseudo_t pseudo, struct instruction *insn,
 
 	/* Unreachable load? Undo it */
 	if (!bb) {
-		insn->opcode = OP_LNOP;
+		kill_use(&insn->src);
 		return 1;
 	}
 
diff --git a/validation/mem2reg/load-deadborn.c b/validation/mem2reg/load-deadborn.c
new file mode 100644
index 000000000..fa0baeae8
--- /dev/null
+++ b/validation/mem2reg/load-deadborn.c
@@ -0,0 +1,9 @@
+static void foo(int a)
+{
+	return;
+	a;
+}
+
+/*
+ * check-name: load-deadborn
+ */
-- 
2.16.0

[PATCH 4/9] add helpers for pseudo's user-list's size

[Luc Van Oostenryck]

Add pseudo_user_list_size() instead of having to use
ptr_list_size() with an ugly cast.
Also add has_user(), a wrapper around the above that
can directly be used on a pseudo.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.h | 10 ++++++++++
 simplify.c  |  4 ++--
 2 files changed, 12 insertions(+), 2 deletions(-)

diff --git a/linearize.h b/linearize.h
index c0c49bdf0..15a6be9c9 100644
--- a/linearize.h
+++ b/linearize.h
@@ -325,6 +325,16 @@ static inline int has_use_list(pseudo_t p)
 	return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_VAL);
 }
 
+static inline int pseudo_user_list_size(struct pseudo_user_list *list)
+{
+	return ptr_list_size((struct ptr_list *)list);
+}
+
+static inline int has_users(pseudo_t p)
+{
+	return pseudo_user_list_size(p->users) != 0;
+}
+
 static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp)
 {
 	struct pseudo_user *user = __alloc_pseudo_user(0);
diff --git a/simplify.c b/simplify.c
index 8aac852b4..971f8ca91 100644
--- a/simplify.c
+++ b/simplify.c
@@ -179,7 +179,7 @@ static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_
 	} END_FOR_EACH_PTR(pu);
 	assert(count <= 0);
 out:
-	if (ptr_list_size((struct ptr_list *) *list) == 0)
+	if (pseudo_user_list_size(*list) == 0)
 		*list = NULL;
 	return count;
 }
@@ -797,7 +797,7 @@ static int simplify_associative_binop(struct instruction *insn)
 		return 0;
 	if (!simple_pseudo(def->src2))
 		return 0;
-	if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
+	if (pseudo_user_list_size(def->target->users) != 1)
 		return 0;
 	switch_pseudo(def, &def->src1, insn, &insn->src2);
 	return REPEAT_CSE;
-- 
2.16.0

[PATCH 5/9] use has_users() in dead_insn() too

[Luc Van Oostenryck]

The same functionality was open-coded here.
Change this by calling the new helper: has_users().

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

diff --git a/simplify.c b/simplify.c
index 971f8ca91..5a90b9c6a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -308,11 +308,8 @@ void kill_insn(struct instruction *insn, int force)
  */
 static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
 {
-	struct pseudo_user *pu;
-	FOR_EACH_PTR(insn->target->users, pu) {
-		if (*pu->userp != VOID)
-			return 0;
-	} END_FOR_EACH_PTR(pu);
+	if (has_users(insn->target))
+		return 0;
 
 	insn->bb = NULL;
 	kill_use(src1);
-- 
2.16.0

[PATCH 6/9] let kill_instruction() report if changes were made

[Luc Van Oostenryck]

This let us take others actions if no changes have been made
and allow simpler call to this function since its effect on
'repeat_phase' can be directly returned.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.h     | 10 +++++-----
 simplify.c | 17 ++++++++---------
 2 files changed, 13 insertions(+), 14 deletions(-)

diff --git a/flow.h b/flow.h
index 6743db1ee..8e96f62fb 100644
--- a/flow.h
+++ b/flow.h
@@ -26,14 +26,14 @@ extern void kill_bb(struct basic_block *);
 extern void kill_use(pseudo_t *);
 extern void kill_unreachable_bbs(struct entrypoint *ep);
 
-extern void kill_insn(struct instruction *, int force);
-static inline void kill_instruction(struct instruction *insn)
+extern int kill_insn(struct instruction *, int force);
+static inline int kill_instruction(struct instruction *insn)
 {
-	kill_insn(insn, 0);
+	return kill_insn(insn, 0);
 }
-static inline void kill_instruction_force(struct instruction *insn)
+static inline int kill_instruction_force(struct instruction *insn)
 {
-	kill_insn(insn, 1);
+	return kill_insn(insn, 1);
 }
 
 void check_access(struct instruction *insn);
diff --git a/simplify.c b/simplify.c
index 5a90b9c6a..f0dc69ff9 100644
--- a/simplify.c
+++ b/simplify.c
@@ -221,10 +221,10 @@ static void kill_use_list(struct pseudo_list *list)
  * the function does that unconditionally (must only be used
  * for unreachable instructions.
  */
-void kill_insn(struct instruction *insn, int force)
+int kill_insn(struct instruction *insn, int force)
 {
 	if (!insn || !insn->bb)
-		return;
+		return 0;
 
 	switch (insn->opcode) {
 	case OP_SEL:
@@ -266,9 +266,9 @@ void kill_insn(struct instruction *insn, int force)
 		if (!force) {
 			/* a "pure" function can be killed too */
 			if (!(insn->func->type == PSEUDO_SYM))
-				return;
+				return 0;
 			if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
-				return;
+				return 0;
 		}
 		kill_use_list(insn->arguments);
 		if (insn->func->type == PSEUDO_REG)
@@ -277,20 +277,20 @@ void kill_insn(struct instruction *insn, int force)
 
 	case OP_LOAD:
 		if (!force && insn->type->ctype.modifiers & MOD_VOLATILE)
-			return;
+			return 0;
 		kill_use(&insn->src);
 		break;
 
 	case OP_STORE:
 		if (!force)
-			return;
+			return 0;
 		kill_use(&insn->src);
 		kill_use(&insn->target);
 		break;
 
 	case OP_ENTRY:
 		/* ignore */
-		return;
+		return 0;
 
 	case OP_BR:
 	case OP_SETFVAL:
@@ -299,8 +299,7 @@ void kill_insn(struct instruction *insn, int force)
 	}
 
 	insn->bb = NULL;
-	repeat_phase |= REPEAT_CSE;
-	return;
+	return repeat_phase |= REPEAT_CSE;
 }
 
 /*
-- 
2.16.0

[PATCH 7/9] kill dead loads

[Luc Van Oostenryck]

Like others instructions producing a value, OP_LOADs can be dead.

But currently, dead OP_LOAD are not removed as dead_insn() do
for others instructions.

Fix this by checking at simplification time if OP_LOADs are
dead and call kill_instruction() if it is the case.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                   |  6 +++++-
 validation/optim/load-dead.c | 11 +++++++++++
 2 files changed, 16 insertions(+), 1 deletion(-)
 create mode 100644 validation/optim/load-dead.c

diff --git a/simplify.c b/simplify.c
index f0dc69ff9..dbea438e7 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1195,7 +1195,11 @@ int simplify_instruction(struct instruction *insn)
 
 	case OP_NOT: case OP_NEG:
 		return simplify_unop(insn);
-	case OP_LOAD: case OP_STORE:
+	case OP_LOAD:
+		if (!has_users(insn->target))
+			return kill_instruction(insn);
+		/* fall-through */
+	case OP_STORE:
 		return simplify_memop(insn);
 	case OP_SYMADDR:
 		if (dead_insn(insn, NULL, NULL, NULL))
diff --git a/validation/optim/load-dead.c b/validation/optim/load-dead.c
new file mode 100644
index 000000000..52538cc2d
--- /dev/null
+++ b/validation/optim/load-dead.c
@@ -0,0 +1,11 @@
+void foo(int *p) { *p; }
+
+int *p;
+void bar(void) { *p; }
+
+/*
+ * check-name: load-dead
+ * check-command: test-linearize -Wno-decl $file
+ * check-output-ignore
+ * check-output-excludes: load\\.
+ */
-- 
2.16.0

[PATCH 8/9] add testcase for bad killing of dominated stores

[Luc Van Oostenryck]

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

diff --git a/validation/optim/store-dominated.c b/validation/optim/store-dominated.c
new file mode 100644
index 000000000..f1e2e6f29
--- /dev/null
+++ b/validation/optim/store-dominated.c
@@ -0,0 +1,16 @@
+static int a[];
+
+static void foo(void)
+{
+	int *c = &a[1];
+	*c = *c = 0;
+}
+
+/*
+ * check-name: store-dominated
+ * check-command: test-linearize $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-excludes: add\.
+ */
-- 
2.16.0

[PATCH 9/9] kill dead stores when simplifying symbols

[Luc Van Oostenryck]

In the initial simplify_symbols() and in simplify_memops()
when a store is simplified away, it's killed via kill_store()
where its ->bb is set to NULL and the usage is removed from
the value. However the usage is not removed from the address.
As consequence, code related to the address calculation
is not optimized away as it should be since the value is
wrongly considered as needed.

Fix this by using kill_instruction_force() to remove these
stores.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                             | 17 ++++-------------
 memops.c                           | 11 +----------
 validation/optim/store-dominated.c |  1 -
 3 files changed, 5 insertions(+), 24 deletions(-)

diff --git a/flow.c b/flow.c
index 528c8f32d..495b118d2 100644
--- a/flow.c
+++ b/flow.c
@@ -542,15 +542,6 @@ found:
 	return 1;
 }
 
-static void kill_store(struct instruction *insn)
-{
-	if (insn) {
-		insn->bb = NULL;
-		insn->opcode = OP_SNOP;
-		kill_use(&insn->target);
-	}
-}
-
 /* Kill a pseudo that is dead on exit from the bb */
 static void kill_dead_stores(pseudo_t pseudo, unsigned long generation, struct basic_block *bb, int local)
 {
@@ -575,7 +566,7 @@ static void kill_dead_stores(pseudo_t pseudo, unsigned long generation, struct b
 		if (insn->src == pseudo) {
 			if (opcode == OP_LOAD)
 				return;
-			kill_store(insn);
+			kill_instruction_force(insn);
 			continue;
 		}
 		if (local)
@@ -606,7 +597,7 @@ static void kill_dominated_stores(pseudo_t pseudo, struct instruction *insn,
 
 	/* Unreachable store? Undo it */
 	if (!bb) {
-		kill_store(insn);
+		kill_instruction_force(insn);
 		return;
 	}
 	if (bb->generation == generation)
@@ -629,7 +620,7 @@ static void kill_dominated_stores(pseudo_t pseudo, struct instruction *insn,
 			return;
 		if (one->opcode == OP_LOAD)
 			return;
-		kill_store(one);
+		kill_instruction_force(one);
 	} END_FOR_EACH_PTR_REVERSE(one);
 
 	if (!found) {
@@ -721,7 +712,7 @@ external_visibility:
 		FOR_EACH_PTR(pseudo->users, pu) {
 			struct instruction *insn = pu->insn;
 			if (insn->opcode == OP_STORE)
-				kill_store(insn);
+				kill_instruction_force(insn);
 		} END_FOR_EACH_PTR(pu);
 	} else {
 		/*
diff --git a/memops.c b/memops.c
index 788ed2f2f..5762f4f2c 100644
--- a/memops.c
+++ b/memops.c
@@ -139,15 +139,6 @@ next_load:
 	} END_FOR_EACH_PTR_REVERSE(insn);
 }
 
-static void kill_store(struct instruction *insn)
-{
-	if (insn) {
-		insn->bb = NULL;
-		insn->opcode = OP_SNOP;
-		kill_use(&insn->target);
-	}
-}
-
 static void kill_dominated_stores(struct basic_block *bb)
 {
 	struct instruction *insn;
@@ -178,7 +169,7 @@ static void kill_dominated_stores(struct basic_block *bb)
 					if (dom->opcode == OP_LOAD)
 						goto next_store;
 					/* Yeehaa! Found one! */
-					kill_store(dom);
+					kill_instruction_force(dom);
 				}
 			} END_FOR_EACH_PTR_REVERSE(dom);
 
diff --git a/validation/optim/store-dominated.c b/validation/optim/store-dominated.c
index f1e2e6f29..d74db7790 100644
--- a/validation/optim/store-dominated.c
+++ b/validation/optim/store-dominated.c
@@ -9,7 +9,6 @@ static void foo(void)
 /*
  * check-name: store-dominated
  * check-command: test-linearize $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-excludes: add\.
-- 
2.16.0

Re: [PATCH 4/9] add helpers for pseudo's user-list's size

[Linus Torvalds]

On Mon, Feb 12, 2018 at 2:02 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Also add has_user(), a wrapper around the above that
> can directly be used on a pseudo.

You add that wrapper, but then:

> -       if (ptr_list_size((struct ptr_list *) *list) == 0)
> +       if (pseudo_user_list_size(*list) == 0)

you don't actually *use* it. That seems pointless.

                Linus

Re: [PATCH 4/9] add helpers for pseudo's user-list's size

[Luc Van Oostenryck]

On Mon, Feb 12, 2018 at 02:11:34PM -0800, Linus Torvalds wrote:
> On Mon, Feb 12, 2018 at 2:02 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > Also add has_user(), a wrapper around the above that
> > can directly be used on a pseudo.
> 
> You add that wrapper, but then:
> 
> > -       if (ptr_list_size((struct ptr_list *) *list) == 0)
> > +       if (pseudo_user_list_size(*list) == 0)
> 
> you don't actually *use* it. That seems pointless.

Yes, I know it's not ideal.
My intention when I made has_users() was to use it too,
but I also made it to directly take a pseudo as argument
(which is the common case). And then when wanting to use
it I saw that there is pseudo here, only the pseudo_user_list.
So, I had to use the intermediate pseudo_user_list_size()
here instead of has_users().

I may change has_users() to take the user list instead
of the pseudo but my mental model was pseudos. 

-- Luc

Re: [PATCH 4/9] add helpers for pseudo's user-list's size

[Luc Van Oostenryck]

On Mon, Feb 12, 2018 at 11:28:04PM +0100, Luc Van Oostenryck wrote:
> On Mon, Feb 12, 2018 at 02:11:34PM -0800, Linus Torvalds wrote:
> > On Mon, Feb 12, 2018 at 2:02 PM, Luc Van Oostenryck
> > <luc.vanoostenryck@gmail.com> wrote:
> > > Also add has_user(), a wrapper around the above that
> > > can directly be used on a pseudo.
> > 
> > You add that wrapper, but then:
> > 
> > > -       if (ptr_list_size((struct ptr_list *) *list) == 0)
> > > +       if (pseudo_user_list_size(*list) == 0)
> > 
> > you don't actually *use* it. That seems pointless.
> 
> Yes, I know it's not ideal.
> My intention when I made has_users() was to use it too,
> but I also made it to directly take a pseudo as argument
> (which is the common case). And then when wanting to use
> it I saw that there is pseudo here, only the pseudo_user_list.
> So, I had to use the intermediate pseudo_user_list_size()
> here instead of has_users().
> 
> I may change has_users() to take the user list instead
> of the pseudo but my mental model was pseudos. 

I've splitted the patch in two, one with leaving
the changes with pseudo_user_list_size() and another
one introduncing has_users(). I think that it makes
things easier to follow.

Thanks for noticing.
-- Luc