[21/29] sssa: add basic implementation

Commit Message

Luc Van Oostenryck Aug. 16, 2017, 3:34 p.m. UTC

This a direct implementation of the pseudo-code for the
new SSA construction method a described in it's paper:

  "Simple and Efficient Construction of Static Single Assignment Form"
	by Matthias Braun, Sebastian Buchwald, Sebastian Hack,
	   Roland Leissa, Christoph Mallon and Andreas Zwinkau.

[cfr. http://www.cdl.uni-saarland.de/papers/bbhlmz13cc.pdf]

Signed-off-by: Luc Van Oostenryck <[e-mail]>
---
 Makefile |  1 +
 ssa.c    | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 99 insertions(+)
 create mode 100644 ssa.c

Patch

diff --git a/Makefile b/Makefile
index 762aee505..bcd7ab7da 100644
--- a/Makefile
+++ b/Makefile
@@ -118,6 +118,7 @@  LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \
 	  char.o sort.o allocate.o compat-$(OS).o ptrlist.o \
 	  builtin.o \
 	  ptrmap.o \
+	  ssa.o \
 	  stats.o \
 	  flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o dissect.o
 
diff --git a/ssa.c b/ssa.c
new file mode 100644
index 000000000..32e440669
--- /dev/null
+++ b/ssa.c
@@ -0,0 +1,98 @@ 
+/*
+ * This is an implementation of the SSA construction algorithm:
+ *	"Simple and Efficient Construction of Static Single Assignment Form"
+ * by Matthias Braun, Sebastian Buchwald, Sebastian Hack, Roland Leissa,
+ *    Christoph Mallon and Andreas Zwinkau.
+ * cfr. http://www.cdl.uni-saarland.de/papers/bbhlmz13cc.pdf
+ */
+
+#include "ssa.h"
+#include "linearize.h"
+#include "flow.h"
+#include "lib.h"
+#include <assert.h>
+
+
+// FIXME: -> common file
+static void append_instruction(struct basic_block *bb, struct instruction *insn)
+{
+	struct instruction *br = delete_last_instruction(&bb->insns);
+	insn->bb = bb;
+	add_instruction(&bb->insns, insn);
+	add_instruction(&bb->insns, br);
+}
+
+static pseudo_t add_phi_operand(struct symbol *var, pseudo_t phi)
+{
+	struct instruction *node = phi->def;
+	struct basic_block *parent;
+
+	FOR_EACH_PTR(node->bb->parents, parent) {
+		pseudo_t val = load_var(parent, var);
+		struct instruction *phisrc = alloc_phisrc(val, var);
+		pseudo_t src = phisrc->target;
+		append_instruction(parent, phisrc);
+		use_pseudo(node, src, add_pseudo(&node->phi_list, src));
+	} END_FOR_EACH_PTR(parent);
+	return phi;
+}
+
+static pseudo_t load_var_parents(struct basic_block *bb, struct symbol *var)
+{
+	pseudo_t val;
+
+	if (!bb->sealed) {	// incomplete CFG
+		val = insert_phi_node(bb, var);
+		val->def->var = var;
+		goto out;
+	}
+
+	switch (bb_list_size(bb->parents)) {
+	case 0:	// never defined
+		val = undef_pseudo();
+		break;
+	case 1: // no phi needed
+		val = load_var(first_basic_block(bb->parents), var);
+		break;
+	default:
+		val = insert_phi_node(bb, var);
+		store_var(bb, var, val);
+		val = add_phi_operand(var, val);
+	}
+
+out:
+	store_var(bb, var, val);
+	return val;
+}
+
+pseudo_t load_var(struct basic_block *bb, struct symbol *var)
+{
+	pseudo_t val = phi_map_lookup(var->phi_map, bb);
+	if (!val)
+		val = load_var_parents(bb, var);
+	return val;
+}
+
+void store_var(struct basic_block *bb, struct symbol *var, pseudo_t val)
+{
+	phi_map_update(&var->phi_map, bb, val);
+}
+
+void seal_bb(struct basic_block *bb)
+{
+	struct instruction *insn;
+	if (bb->sealed)
+		return;
+	FOR_EACH_PTR(bb->insns, insn) {
+		struct symbol *var;
+		if (!insn->bb)
+			continue;
+		if (insn->opcode != OP_PHI)
+			break;
+		var = insn->var;
+		assert(var);
+		insn->var = NULL;
+		add_phi_operand(var, insn->target);
+	} END_FOR_EACH_PTR(insn);
+	bb->sealed = 1;
+}