5 files changed, 289 insertions, 0 deletions
diff --git a/Makefile b/Makefile
index 3cffd000..f031fadb 100644
--- a/Makefile
+++ b/Makefile
@@ -59,6 +59,7 @@ LIB_OBJS += scope.o
 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
diff --git a/linearize.h b/linearize.h
index 3cce3656..0e980578 100644
--- a/linearize.h
+++ b/linearize.h
@@ -7,6 +7,7 @@
 #include "opcode.h"
 #include "parse.h"
 #include "symbol.h"
+#include "ptrmap.h"
 
 struct instruction;
 
@@ -17,6 +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);
 
 
 enum pseudo_type {
@@ -100,6 +102,7 @@ struct instruction {
 			struct multijmp_list *multijmp_list;
 		};
 		struct /* phi_node */ {
+			pseudo_t phi_var;		// used for SSA conversion
 			struct pseudo_list *phi_list;
 		};
 		struct /* phi source */ {
@@ -277,6 +280,7 @@ struct basic_block {
 	struct instruction_list *insns;	/* Linear list of instructions */
 	struct basic_block *idom;	/* link to the immediate dominator */
 	struct basic_block_list *doms;	/* list of BB idominated by this one */
+	struct phi_map *phi_map;
 	struct pseudo_list *needs, *defines;
 	union {
 		unsigned int nr;	/* unique id for label's names */
diff --git a/ssa.c b/ssa.c
new file mode 100644
index 00000000..29e6e40b
--- /dev/null
+++ b/ssa.c
@@ -0,0 +1,277 @@
+// SPDX-License-Identifier: MIT
+//
+// SSA conversion
+// Copyright (C) 2005 Luc Van Oostenryck
+//
+
+#include <assert.h>
+#include "lib.h"
+#include "sset.h"
+#include "dominate.h"
+#include "flowgraph.h"
+#include "linearize.h"
+#include "flow.h"			// for convert_load_instruction()
+
+
+// Is it possible and desirable for this to be promoted to a pseudo?
+static inline bool is_promotable(struct symbol *type)
+{
+	struct symbol *member;
+	int bf_seen;
+	int nbr;
+
+	if (type->type == SYM_NODE)
+		type = type->ctype.base_type;
+	switch (type->type) {
+	case SYM_ENUM:
+	case SYM_BITFIELD:
+	case SYM_PTR:
+	case SYM_RESTRICT:	// OK, always integer types
+		return 1;
+	case SYM_STRUCT:
+		if (type->bit_size > long_ctype.bit_size)
+			return 0;
+		// we allow a single scalar field
+		// but a run of bitfields count for 1
+		nbr = 0;
+		bf_seen = 0;
+		FOR_EACH_PTR(type->symbol_list, member) {
+			if (is_bitfield_type(member)) {
+				if (bf_seen)
+					continue;
+				bf_seen = 1;
+			} else {
+				bf_seen = 0;
+			}
+			if (!is_scalar_type(member))
+				return 0;
+			if (nbr++)
+				return 0;
+		} END_FOR_EACH_PTR(member);
+		return 1;
+	case SYM_UNION:
+		// FIXME: should be like struct but has problem
+		//        when used with/for type cohercion
+		// -----> OK if only same sized integral types
+		FOR_EACH_PTR(type->symbol_list, member) {
+			if (member->bit_size != type->bit_size)
+				return 0;
+			if (!is_integral_type(member))
+				return 0;
+		} END_FOR_EACH_PTR(member);
+		return 1;
+	default:
+		break;
+	}
+	if (type->ctype.base_type == &int_type)
+		return 1;
+	if (type->ctype.base_type == &fp_type)
+		return 1;
+	return 0;
+}
+
+static bool insn_before(struct instruction *a, struct instruction *b)
+{
+	struct basic_block *bb = a->bb;
+	struct instruction *insn;
+
+	assert(b->bb == bb);
+	FOR_EACH_PTR(bb->insns, insn) {
+		if (insn == a)
+			return true;
+		if (insn == b)
+			return false;
+	} END_FOR_EACH_PTR(insn);
+	assert(0);
+}
+
+static void kill_store(struct instruction *insn)
+{
+	remove_use(&insn->src);
+	remove_use(&insn->target);
+	insn->bb = NULL;
+}
+
+static void rewrite_local_var(struct basic_block *bb, pseudo_t addr, int nbr_stores, int nbr_uses)
+{
+	struct instruction *insn;
+	pseudo_t val = NULL;
+
+	if (!bb)
+		return;
+
+	FOR_EACH_PTR(bb->insns, insn) {
+
+		if (!insn->bb || insn->src != addr)
+			continue;
+		switch (insn->opcode) {
+		case OP_LOAD:
+			if (!val)
+				val = undef_pseudo();
+			convert_load_instruction(insn, val);
+			break;
+		case OP_STORE:
+			val = insn->target;
+			// can't use kill_instruction() unless
+			// we add a fake user to val
+			kill_store(insn);
+			break;
+		}
+	} END_FOR_EACH_PTR(insn);
+}
+
+static bool rewrite_single_store(struct instruction *store)
+{
+	pseudo_t addr = store->src;
+	struct pseudo_user *pu;
+
+	FOR_EACH_PTR(addr->users, pu) {
+		struct instruction *insn = pu->insn;
+
+		if (insn->opcode != OP_LOAD)
+			continue;
+
+		// Let's try to replace the value of the load
+		// by the value from the store. This is only valid
+		// if the store dominate the load.
+
+		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.
+			if (!insn_before(store, insn))
+				continue;
+		} else if (!domtree_dominates(store->bb, insn->bb)) {
+			// we can't convert this load
+			continue;
+		}
+
+		// OK, we can rewrite this load
+
+		// undefs ?
+
+		convert_load_instruction(insn, store->target);
+	} END_FOR_EACH_PTR(pu);
+
+	// is there some unconverted loads?
+	if (pseudo_user_list_size(addr->users) > 1)
+		return false;
+
+	kill_store(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)
+{
+	struct basic_block_list *alpha = NULL;
+	struct basic_block_list *idf = NULL;
+	struct basic_block *samebb = NULL;
+	struct instruction *store = NULL;
+	struct basic_block *bb;
+	struct pseudo_user *pu;
+	unsigned long mod = var->ctype.modifiers;
+	bool local = true;
+	int nbr_stores = 0;
+	int nbr_uses   = 0;
+	pseudo_t addr;
+
+	/* Never used as a symbol? */
+	addr = var->pseudo;
+	if (!addr)
+		return;
+
+	/* We don't do coverage analysis of volatiles.. */
+	if (mod & MOD_VOLATILE)
+		return;
+
+	/* ..and symbols with external visibility need more care */
+	mod &= (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE);
+	if (mod)
+		goto external_visibility;
+
+	if (!is_promotable(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;
+
+		switch (insn->opcode) {
+		case OP_STORE:
+			nbr_stores++;
+			store = insn;
+			if (!sset_testset(processed, bb->nr))
+				add_bb(&alpha, bb);
+			/* fall through */
+		case OP_LOAD:
+			if (local) {
+				if (!samebb)
+					samebb = bb;
+				else if (samebb != bb)
+					local = false;
+			}
+			nbr_uses++;
+			break;
+		case OP_SYMADDR:
+			mod |= MOD_ADDRESSABLE;
+			goto external_visibility;
+		default:
+			warning(var->pos, "symbol '%s' pseudo used in unexpected way",
+				show_ident(var->ident));
+		}
+	} END_FOR_EACH_PTR(pu);
+
+	if (nbr_stores == 1) {
+		if (rewrite_single_store(store))
+			return;
+	}
+
+	// if all uses are local to a single block
+	// they can easily be rewritten and doesn't need phi-nodes
+	// FIXME: could be done for extended BB too
+	if (local) {
+		rewrite_local_var(samebb, addr, nbr_stores, nbr_uses);
+		return;
+	}
+
+	idf_compute(ep, &idf, alpha);
+	FOR_EACH_PTR(idf, bb) {
+		struct instruction *node = insert_phi_node(bb, var);
+		node->phi_var = var->pseudo;
+	} END_FOR_EACH_PTR(bb);
+	var->torename = 1;
+
+external_visibility:
+	if (mod & (MOD_NONLOCAL | MOD_STATIC))
+		return;
+	kill_dead_stores(ep, addr, !mod);
+}
+
+void ssa_convert(struct entrypoint *ep)
+{
+	struct basic_block *bb;
+	pseudo_t pseudo;
+	int first, last;
+
+	// calculate the number of BBs
+	first = ep->entry->bb->nr;
+	last = first;
+	FOR_EACH_PTR(ep->bbs, bb) {
+		int nr = bb->nr;
+		if (nr > last)
+			last = nr;
+	} 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);
+	} END_FOR_EACH_PTR(pseudo);
+}
diff --git a/ssa.h b/ssa.h
new file mode 100644
index 00000000..cbcbc3a4
--- /dev/null
+++ b/ssa.h
@@ -0,0 +1,6 @@
+#ifndef SSA_H
+#define SSA_H
+
+void ssa_convert(struct entrypoint *ep);
+
+#endif
diff --git a/symbol.h b/symbol.h
index 27b5bfb2..27e67256 100644
--- a/symbol.h
+++ b/symbol.h
@@ -175,6 +175,7 @@ struct symbol {
 					forced_arg:1,
 					accessed:1,
 					builtin:1,
+					torename:1,
 					transparent_union:1;
 			struct expression *array_size;
 			struct ctype ctype;