[PATCH 0/4] fix SSA conversion of mismatched memops

[PATCH 0/4] fix SSA conversion of mismatched memops

[Luc Van Oostenryck]

The SSA conversion works under the assumption that all the memory
operations on a given symbol always refer to the same object
(same size, offset and type/kind of object) but doesn't check this
well enough. This series now does.

Luc Van Oostenryck (4):
  ssa: add some testcases for mismatched memops
  ssa: the sparse set is not needed
  ssa: avoid SSA conversion of packed bitfields
  ssa: fix conversion with mismatched size or offset

 Makefile                             |   1 -
 linearize.h                          |   2 +-
 ssa.c                                | 111 +++++++++++++++++++++------
 sset.c                               |  28 -------
 sset.h                               |  56 --------------
 validation/mem2reg/not-same-memop0.c |  48 ++++++++++++
 validation/mem2reg/packed-bitfield.c |  35 +++++++++
 7 files changed, 170 insertions(+), 111 deletions(-)
 delete mode 100644 sset.c
 delete mode 100644 sset.h
 create mode 100644 validation/mem2reg/not-same-memop0.c
 create mode 100644 validation/mem2reg/packed-bitfield.c

-- 
2.30.0

[PATCH 1/4] ssa: add some testcases for mismatched memops

[Luc Van Oostenryck]

The SSA conversion is incorrect when the size or offset of the
memory operations doesn't match. It shouldn't be done at all.

So, add a few testcases for this.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/mem2reg/not-same-memop0.c | 49 ++++++++++++++++++++++++++++
 validation/mem2reg/packed-bitfield.c | 36 ++++++++++++++++++++
 2 files changed, 85 insertions(+)
 create mode 100644 validation/mem2reg/not-same-memop0.c
 create mode 100644 validation/mem2reg/packed-bitfield.c

diff --git a/validation/mem2reg/not-same-memop0.c b/validation/mem2reg/not-same-memop0.c
new file mode 100644
index 000000000000..7a84ddce4efc
--- /dev/null
+++ b/validation/mem2reg/not-same-memop0.c
@@ -0,0 +1,49 @@
+struct s {
+	int:16;
+	short f:6;
+};
+
+static short local(struct s s)
+{
+	return s.f;
+}
+
+static void foo(struct s s)
+{
+	while (s.f) ;
+}
+
+/*
+ * check-name: not-same-memop0
+ * check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file
+ * check-known-to-fail
+ *
+ * check-output-start
+local:
+.L0:
+	<entry-point>
+	store.32    %arg1 -> 0[s]
+	load.16     %r1 <- 2[s]
+	trunc.6     %r2 <- (16) %r1
+	sext.16     %r3 <- (6) %r2
+	ret.16      %r3
+
+
+foo:
+.L2:
+	<entry-point>
+	store.32    %arg1 -> 0[s]
+	br          .L6
+
+.L6:
+	load.16     %r5 <- 2[s]
+	trunc.6     %r6 <- (16) %r5
+	setne.1     %r7 <- %r6, $0
+	cbr         %r7, .L6, .L5
+
+.L5:
+	ret
+
+
+ * check-output-end
+ */
diff --git a/validation/mem2reg/packed-bitfield.c b/validation/mem2reg/packed-bitfield.c
new file mode 100644
index 000000000000..4eaf0befeaf5
--- /dev/null
+++ b/validation/mem2reg/packed-bitfield.c
@@ -0,0 +1,36 @@
+struct s {
+	int:16;
+	int f:16;
+} __attribute__((__packed__));
+
+static void foo(struct s s)
+{
+	while (s.f)
+		;
+}
+
+/*
+ * check-name: packed-bitfield
+ * check-command: test-linearize -fmem2reg $file
+ * check-known-to-fail
+ *
+ * check-output-contains: store.32
+ * check-output-contains: load.16
+ *
+ * check-output-start
+foo:
+.L0:
+	<entry-point>
+	store.32    %arg1 -> 0[s]
+	br          .L4
+
+.L4:
+	load.16     %r1 <- 2[s]
+	cbr         %r1, .L4, .L3
+
+.L3:
+	ret
+
+
+ * check-output-end
+ */
-- 
2.30.0

[PATCH 2/4] ssa: the sparse set is not needed

[Luc Van Oostenryck]

The implementation of a 'sparse set without initialization' was
somehow needed during the initial design but it's not needed anymore.

So, remove the implementation and replace its use by the usual
bb->generation mechanism.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Makefile |  1 -
 ssa.c    | 11 ++++-------
 sset.c   | 28 ----------------------------
 sset.h   | 56 --------------------------------------------------------
 4 files changed, 4 insertions(+), 92 deletions(-)
 delete mode 100644 sset.c
 delete mode 100644 sset.h

diff --git a/Makefile b/Makefile
index f9883da101c7..6ad14375b3cd 100644
--- a/Makefile
+++ b/Makefile
@@ -63,7 +63,6 @@ LIB_OBJS += show-parse.o
 LIB_OBJS += simplify.o
 LIB_OBJS += sort.o
 LIB_OBJS += ssa.o
-LIB_OBJS += sset.o
 LIB_OBJS += stats.o
 LIB_OBJS += storage.o
 LIB_OBJS += symbol.o
diff --git a/ssa.c b/ssa.c
index b9044207db16..3f4fa1a831df 100644
--- a/ssa.c
+++ b/ssa.c
@@ -7,7 +7,6 @@
 #include <assert.h>
 #include "ssa.h"
 #include "lib.h"
-#include "sset.h"
 #include "dominate.h"
 #include "flowgraph.h"
 #include "linearize.h"
@@ -162,13 +161,12 @@ static bool rewrite_single_store(struct instruction *store)
 	return true;
 }
 
-static struct sset *processed;
-
 // we would like to know:
 // is there one or more stores?
 // are all loads & stores local/done in a single block?
 static void ssa_convert_one_var(struct entrypoint *ep, struct symbol *var)
 {
+	unsigned long generation = ++bb_generation;
 	struct basic_block_list *alpha = NULL;
 	struct basic_block_list *idf = NULL;
 	struct basic_block *samebb = NULL;
@@ -199,7 +197,6 @@ static void ssa_convert_one_var(struct entrypoint *ep, struct symbol *var)
 		return;
 
 	// 1) insert in the worklist all BBs that may modify var
-	sset_reset(processed);
 	FOR_EACH_PTR(addr->users, pu) {
 		struct instruction *insn = pu->insn;
 		struct basic_block *bb = insn->bb;
@@ -208,8 +205,10 @@ static void ssa_convert_one_var(struct entrypoint *ep, struct symbol *var)
 		case OP_STORE:
 			nbr_stores++;
 			store = insn;
-			if (!sset_testset(processed, bb->nr))
+			if (bb->generation != generation) {
+				bb->generation = generation;
 				add_bb(&alpha, bb);
+			}
 			/* fall through */
 		case OP_LOAD:
 			if (local) {
@@ -390,8 +389,6 @@ void ssa_convert(struct entrypoint *ep)
 		bb->phi_map = NULL;
 	} END_FOR_EACH_PTR(bb);
 
-	processed = sset_init(first, last);
-
 	// try to promote memory accesses to pseudos
 	FOR_EACH_PTR(ep->accesses, pseudo) {
 		ssa_convert_one_var(ep, pseudo->sym);
diff --git a/sset.c b/sset.c
deleted file mode 100644
index e9681e00ddd4..000000000000
--- a/sset.c
+++ /dev/null
@@ -1,28 +0,0 @@
-// SPDX-License-Identifier: MIT
-//
-// sset.c - an all O(1) implementation of sparse sets as presented in:
-//	"An Efficient Representation for Sparse Sets"
-//	by Preston Briggs and Linda Torczon
-//
-// Copyright (C) 2017 - Luc Van Oostenryck
-
-#include "sset.h"
-#include "lib.h"
-#include <stdlib.h>
-
-
-struct sset *sset_init(unsigned int first, unsigned int last)
-{
-	unsigned int size = last - first + 1;
-	struct sset *s = malloc(sizeof(*s) + size * 2 * sizeof(s->sets[0]));
-
-	s->size = size;
-	s->off = first;
-	s->nbr = 0;
-	return s;
-}
-
-void sset_free(struct sset *s)
-{
-	free(s);
-}
diff --git a/sset.h b/sset.h
deleted file mode 100644
index 69cee18a2768..000000000000
--- a/sset.h
+++ /dev/null
@@ -1,56 +0,0 @@
-// SPDX-License-Identifier: MIT
-
-#ifndef SSET_H
-#define SSET_H
-
-/*
- * sset.h - an all O(1) implementation of sparse sets as presented in:
- *	"An Efficient Representation for Sparse Sets"
- *	by Preston Briggs and Linda Torczon
- *
- * Copyright (C) 2017 - Luc Van Oostenryck
- */
-
-#include <stdbool.h>
-
-struct sset {
-	unsigned int nbr;
-	unsigned int off;
-	unsigned int size;
-	unsigned int sets[0];
-};
-
-extern struct sset *sset_init(unsigned int size, unsigned int off);
-extern void sset_free(struct sset *s);
-
-
-static inline void sset_reset(struct sset *s)
-{
-	s->nbr = 0;
-}
-
-static inline void sset_add(struct sset *s, unsigned int idx)
-{
-	unsigned int __idx = idx - s->off;
-	unsigned int n = s->nbr++;
-	s->sets[__idx] = n;
-	s->sets[s->size + n] = __idx;
-}
-
-static inline bool sset_test(struct sset *s, unsigned int idx)
-{
-	unsigned int __idx = idx - s->off;
-	unsigned int n = s->sets[__idx];
-
-	return (n < s->nbr) && (s->sets[s->size + n] == __idx);
-}
-
-static inline bool sset_testset(struct sset *s, unsigned int idx)
-{
-	if (sset_test(s, idx))
-		return true;
-	sset_add(s, idx);
-	return false;
-}
-
-#endif
-- 
2.30.0

[PATCH 3/4] ssa: avoid SSA conversion of packed bitfields

[Luc Van Oostenryck]

Packed bitfields are incompatible with the SSA conversion
which works on the assumption that memory operations are done
on the whole symbol.

So, directly exclude packed bitfields from the SSA conversion.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ssa.c                                | 3 +++
 validation/mem2reg/packed-bitfield.c | 1 -
 2 files changed, 3 insertions(+), 1 deletion(-)

diff --git a/ssa.c b/ssa.c
index 3f4fa1a831df..26d46baaa16c 100644
--- a/ssa.c
+++ b/ssa.c
@@ -32,6 +32,9 @@ static inline bool is_promotable(struct symbol *type)
 	case SYM_STRUCT:
 		// we allow a single scalar field
 		// but a run of bitfields count for 1
+		// (and packed bifields are excluded).
+		if (type->packed)
+			return 0;
 		nbr = 0;
 		bf_seen = 0;
 		FOR_EACH_PTR(type->symbol_list, member) {
diff --git a/validation/mem2reg/packed-bitfield.c b/validation/mem2reg/packed-bitfield.c
index 4eaf0befeaf5..f3ee259a62b8 100644
--- a/validation/mem2reg/packed-bitfield.c
+++ b/validation/mem2reg/packed-bitfield.c
@@ -12,7 +12,6 @@ static void foo(struct s s)
 /*
  * check-name: packed-bitfield
  * check-command: test-linearize -fmem2reg $file
- * check-known-to-fail
  *
  * check-output-contains: store.32
  * check-output-contains: load.16
-- 
2.30.0

[PATCH 4/4] ssa: fix conversion with mismatched size or offset

[Luc Van Oostenryck]

The SSA conversion works under the assumption that all the memory
operations on a given symbol always refer to the same object.

So, exclude the conversion of variables where:
* memory operations do not always match in size or offset
* there is an implicit integer/float conversion.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.h                          |  2 +-
 ssa.c                                | 97 ++++++++++++++++++++++------
 validation/mem2reg/not-same-memop0.c |  1 -
 3 files changed, 80 insertions(+), 20 deletions(-)

diff --git a/linearize.h b/linearize.h
index 7909b01f29c5..86ae119c82e6 100644
--- a/linearize.h
+++ b/linearize.h
@@ -18,7 +18,7 @@ struct pseudo_user {
 
 DECLARE_ALLOCATOR(pseudo_user);
 DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user);
-DECLARE_PTRMAP(phi_map, struct symbol *, pseudo_t);
+DECLARE_PTRMAP(phi_map, struct symbol *, struct instruction *);
 
 
 enum pseudo_type {
diff --git a/ssa.c b/ssa.c
index 26d46baaa16c..f61672a0b530 100644
--- a/ssa.c
+++ b/ssa.c
@@ -96,10 +96,22 @@ static void kill_store(struct instruction *insn)
 	insn->bb = NULL;
 }
 
+static bool same_memop(struct instruction *a, struct instruction *b)
+{
+	if (a->size != b->size || a->offset != b->offset)
+		return false;
+	if (is_integral_type(a->type) && is_float_type(b->type))
+		return false;
+	if (is_float_type(a->type) && is_integral_type(b->type))
+		return false;
+	return true;
+}
+
 static void rewrite_local_var(struct basic_block *bb, pseudo_t addr, int nbr_stores, int nbr_uses)
 {
+	struct instruction *store = NULL;
 	struct instruction *insn;
-	pseudo_t val = NULL;
+	bool remove = false;
 
 	if (!bb)
 		return;
@@ -110,18 +122,21 @@ static void rewrite_local_var(struct basic_block *bb, pseudo_t addr, int nbr_sto
 			continue;
 		switch (insn->opcode) {
 		case OP_LOAD:
-			if (!val)
-				val = undef_pseudo();
-			replace_with_pseudo(insn, val);
+			if (!store)
+				replace_with_pseudo(insn, undef_pseudo());
+			else if (same_memop(store, insn))
+				replace_with_pseudo(insn, store->target);
+			else
+				remove = false;
 			break;
 		case OP_STORE:
-			val = insn->target;
-			// can't use kill_instruction() unless
-			// we add a fake user to val
-			kill_store(insn);
+			store = insn;
+			remove = true;
 			break;
 		}
 	} END_FOR_EACH_PTR(insn);
+	if (remove)
+		kill_store(store);
 }
 
 static bool rewrite_single_store(struct instruction *store)
@@ -139,6 +154,8 @@ static bool rewrite_single_store(struct instruction *store)
 		// by the value from the store. This is only valid
 		// if the store dominate the load.
 
+		if (!same_memop(store, insn))
+			continue;
 		if (insn->bb == store->bb) {
 			// the load and the store are in the same BB
 			// we can convert if the load is after the store.
@@ -257,21 +274,40 @@ external_visibility:
 	kill_dead_stores(ep, addr, !mod);
 }
 
-static pseudo_t lookup_var(struct basic_block *bb, struct symbol *var)
+static struct instruction *lookup_var(struct basic_block *bb, struct symbol *var)
 {
 	do {
-		pseudo_t val = phi_map_lookup(bb->phi_map, var);
-		if (val)
-			return val;
+		struct instruction *insn = phi_map_lookup(bb->phi_map, var);
+		if (insn)
+			return insn;
 	} while ((bb = bb->idom));
-	return undef_pseudo();
+	return NULL;
 }
 
 static struct instruction_list *phis_all;
 static struct instruction_list *phis_used;
+static struct instruction_list *stores;
+
+static bool matching_load(struct instruction *def, struct instruction *insn)
+{
+	if (insn->size != def->size)
+		return false;
+	switch (def->opcode) {
+	case OP_STORE:
+	case OP_LOAD:
+		if (insn->offset != def->offset)
+			return false;
+	case OP_PHI:
+		break;
+	default:
+		return false;
+	}
+	return true;
+}
 
 static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn)
 {
+	struct instruction *def;
 	struct symbol *var;
 	pseudo_t addr;
 	pseudo_t val;
@@ -284,8 +320,8 @@ static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn)
 		var = addr->sym;
 		if (!var || !var->torename)
 			break;
-		phi_map_update(&bb->phi_map, var, insn->target);
-		kill_store(insn);
+		phi_map_update(&bb->phi_map, var, insn);
+		add_instruction(&stores, insn);
 		break;
 	case OP_LOAD:
 		addr = insn->src;
@@ -294,14 +330,22 @@ static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn)
 		var = addr->sym;
 		if (!var || !var->torename)
 			break;
-		val = lookup_var(bb, var);
+		def = lookup_var(bb, var);
+		if (!def) {
+			val = undef_pseudo();
+		} else if (!matching_load(def, insn)) {
+			var->torename = false;
+			break;
+		} else {
+			val = def->target;
+		}
 		replace_with_pseudo(insn, val);
 		break;
 	case OP_PHI:
 		var = insn->type;
 		if (!var || !var->torename)
 			break;
-		phi_map_update(&bb->phi_map, var, insn->target);
+		phi_map_update(&bb->phi_map, var, insn);
 		add_instruction(&phis_all, insn);
 		break;
 	}
@@ -348,7 +392,8 @@ static void ssa_rename_phi(struct instruction *insn)
 		return;
 	FOR_EACH_PTR(insn->bb->parents, par) {
 		struct instruction *term = delete_last_instruction(&par->insns);
-		pseudo_t val = lookup_var(par, var);
+		struct instruction *def = lookup_var(par, var);
+		pseudo_t val = def ? def->target : undef_pseudo();
 		pseudo_t phi = alloc_phi(par, val, var);
 		phi->ident = var->ident;
 		add_instruction(&par->insns, term);
@@ -376,6 +421,18 @@ static void ssa_rename_phis(struct entrypoint *ep)
 	} END_FOR_EACH_PTR(phi);
 }
 
+static void remove_dead_stores(struct instruction_list *stores)
+{
+	struct instruction *store;
+
+	FOR_EACH_PTR(stores, store) {
+		struct symbol *var = store->addr->sym;
+
+		if (var->torename)
+			kill_store(store);
+	} END_FOR_EACH_PTR(store);
+}
+
 void ssa_convert(struct entrypoint *ep)
 {
 	struct basic_block *bb;
@@ -393,6 +450,7 @@ void ssa_convert(struct entrypoint *ep)
 	} END_FOR_EACH_PTR(bb);
 
 	// try to promote memory accesses to pseudos
+	stores = NULL;
 	FOR_EACH_PTR(ep->accesses, pseudo) {
 		ssa_convert_one_var(ep, pseudo->sym);
 	} END_FOR_EACH_PTR(pseudo);
@@ -401,4 +459,7 @@ void ssa_convert(struct entrypoint *ep)
 	phis_all = phis_used = NULL;
 	ssa_rename_insns(ep);
 	ssa_rename_phis(ep);
+
+	// remove now dead stores
+	remove_dead_stores(stores);
 }
diff --git a/validation/mem2reg/not-same-memop0.c b/validation/mem2reg/not-same-memop0.c
index 7a84ddce4efc..4de981956b74 100644
--- a/validation/mem2reg/not-same-memop0.c
+++ b/validation/mem2reg/not-same-memop0.c
@@ -16,7 +16,6 @@ static void foo(struct s s)
 /*
  * check-name: not-same-memop0
  * check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file
- * check-known-to-fail
  *
  * check-output-start
 local:
-- 
2.30.0