3 files changed, 136 insertions, 0 deletions
diff --git a/Makefile b/Makefile
index 256fd329..d65bd80d 100644
--- a/Makefile
+++ b/Makefile
@@ -37,6 +37,7 @@ LIB_OBJS += char.o
 LIB_OBJS += compat-$(OS).o
 LIB_OBJS += cse.o
 LIB_OBJS += dissect.o
+LIB_OBJS += dominate.o
 LIB_OBJS += evaluate.o
 LIB_OBJS += expand.o
 LIB_OBJS += expression.o
diff --git a/dominate.c b/dominate.c
new file mode 100644
index 00000000..d7808119
--- /dev/null
+++ b/dominate.c
@@ -0,0 +1,126 @@
+// SPDX-License-Identifier: MIT
+//
+// dominate.c - compute the (iterated) dominance frontier of (a set of) nodes.
+//
+// Copyright (C) 2017 - Luc Van Oostenryck
+//
+// The algorithm used is the one described in:
+//	"A Linear Time Algorithm for Placing phi-nodes"
+//	by Vugranam C. Sreedhar and Guang R. Gao
+//
+
+#include "dominate.h"
+#include "flowgraph.h"
+#include "linearize.h"
+#include "flow.h"
+#include <assert.h>
+#include <stdlib.h>
+
+
+struct piggy {
+	unsigned int max;
+	struct basic_block_list *lists[0];
+};
+
+struct piggy *bank_init(unsigned levels)
+{
+	struct piggy *bank;
+	bank = calloc(1, sizeof(*bank) + levels * sizeof(bank->lists[0]));
+	bank->max = levels - 1;
+	return bank;
+}
+
+static void bank_free(struct piggy *bank, unsigned int levels)
+{
+	for (; levels-- ;)
+		free_ptr_list(&bank->lists[levels]);
+	free(bank);
+}
+
+static void bank_put(struct piggy *bank, struct basic_block *bb)
+{
+	unsigned int level = bb->dom_level;
+	assert(level <= bank->max);
+	add_bb(&bank->lists[level], bb);
+}
+
+static inline struct basic_block *pop_bb(struct basic_block_list **list)
+{
+	return delete_ptr_list_last((struct ptr_list **)list);
+}
+
+static struct basic_block *bank_get(struct piggy *bank)
+{
+	int level = bank->max;
+	do {
+		struct basic_block *bb = pop_bb(&bank->lists[level]);
+		if (bb)
+			return bb;
+		if (!level)
+			return NULL;
+		bank->max = --level;
+	} while (1);
+}
+
+
+#define	VISITED	0x1
+#define	INPHI	0x2
+#define	ALPHA	0x4
+#define	FLAGS	0x7
+
+static void visit(struct piggy *bank, struct basic_block_list **idf, struct basic_block *x, int curr_level)
+{
+	struct basic_block *y;
+
+	x->generation |= 1;
+	FOR_EACH_PTR(x->children, y) {
+		unsigned flags = y->generation & FLAGS;
+		if (y->idom == x)	// J-edges will be processed later
+			continue;
+		if (y->dom_level > curr_level)
+			continue;
+		if (flags & INPHI)
+			continue;
+		y->generation |= INPHI;
+		add_bb(idf, y);
+		if (flags & ALPHA)
+			continue;
+		bank_put(bank, y);
+	} END_FOR_EACH_PTR(y);
+
+	FOR_EACH_PTR(x->doms, y) {
+		if (y->generation & VISITED)
+			continue;
+		visit(bank, idf, y, curr_level);
+	} END_FOR_EACH_PTR(y);
+}
+
+void idf_compute(struct entrypoint *ep, struct basic_block_list **idf, struct basic_block_list *alpha)
+{
+	int levels = ep->dom_levels;
+	struct piggy *bank = bank_init(levels);
+	struct basic_block *bb;
+	unsigned long generation = bb_generation;
+
+	generation = bb_generation;
+	generation += -generation & FLAGS;
+	bb_generation = generation + (FLAGS + 1);
+
+	// init all the nodes
+	FOR_EACH_PTR(ep->bbs, bb) {
+		// FIXME: this should be removed and the tests for
+		//	  visited/in_phi/alpha should use a sparse set
+		bb->generation = generation;
+	} END_FOR_EACH_PTR(bb);
+
+	FOR_EACH_PTR(alpha, bb) {
+		bb->generation = generation | ALPHA;
+		bank_put(bank, bb);
+	} END_FOR_EACH_PTR(bb);
+
+	while ((bb = bank_get(bank))) {
+		visit(bank, idf, bb, bb->dom_level);
+	}
+
+	bank_free(bank, levels);
+}
diff --git a/dominate.h b/dominate.h
new file mode 100644
index 00000000..6ac515d0
--- /dev/null
+++ b/dominate.h
@@ -0,0 +1,9 @@
+#ifndef DOMINATE_H
+#define DOMINATE_H
+
+struct entrypoint;
+struct basic_block_list;
+
+void idf_compute(struct entrypoint *ep, struct basic_block_list **idf, struct basic_block_list *alpha);
+
+#endif