dominate.c

// 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>
#include <stdio.h>


struct piggy {
	unsigned int max;
	struct basic_block_list *lists[0];
};

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

void idf_dump(struct entrypoint *ep)
{
	struct basic_block *bb;

	domtree_build(ep);

	printf("%s's IDF:\n", show_ident(ep->name->ident));
	FOR_EACH_PTR(ep->bbs, bb) {
		struct basic_block_list *alpha = NULL;
		struct basic_block_list *idf = NULL;
		struct basic_block *df;

		add_bb(&alpha, bb);
		idf_compute(ep, &idf, alpha);

		printf("\t%s\t<-", show_label(bb));
		FOR_EACH_PTR(idf, df) {
			printf(" %s", show_label(df));
		} END_FOR_EACH_PTR(df);
		printf("\n");

		free_ptr_list(&idf);
		free_ptr_list(&alpha);
	} END_FOR_EACH_PTR(bb);
}