idf: compute the iterated dominance frontier

Conversion of some IR into SSA form requires to place so called
phi-nodes where different paths for some value meet. It's important,
of course to place these correctly, but it's also important to try
to minimize the number of these phi-nodes. Several algorithms exist
for the placing of these phi-nodes but it can be shown that, for
each variable, it is suffisant to place their phi-nodes on the
dominance frontier of the nodes defining this variable and since
phi-nodes themselves give a new definition, to have the minimal
number of phi-nodes, these phi-nodes must be paced on the iterated
dominance frontier (the transitive closure of the dominance frontier
of the initial defining nodes).

This patch implement what's needed to compute the iterated dominance
frontier of a set of nodes.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>

1 files changed, 126 insertions, 0 deletions

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);
+}