1// SPDX-License-Identifier: MIT
2//
3// dominate.c - compute the (iterated) dominance frontier of (a set of) nodes.
4//
5// Copyright (C) 2017 - Luc Van Oostenryck
6//
7// The algorithm used is the one described in:
8//	"A Linear Time Algorithm for Placing phi-nodes"
9//	by Vugranam C. Sreedhar and Guang R. Gao
10//
11
12#include "dominate.h"
13#include "flowgraph.h"
14#include "linearize.h"
15#include "flow.h"
16#include <assert.h>
17#include <stdlib.h>
18#include <stdio.h>
19
20
21struct piggy {
22	unsigned int max;
23	struct basic_block_list *lists[0];
24};
25
26static struct piggy *bank_init(unsigned levels)
27{
28	struct piggy *bank;
29	bank = calloc(1, sizeof(*bank) + levels * sizeof(bank->lists[0]));
30	bank->max = levels - 1;
31	return bank;
32}
33
34static void bank_free(struct piggy *bank, unsigned int levels)
35{
36	for (; levels-- ;)
37		free_ptr_list(&bank->lists[levels]);
38	free(bank);
39}
40
41static void bank_put(struct piggy *bank, struct basic_block *bb)
42{
43	unsigned int level = bb->dom_level;
44	assert(level <= bank->max);
45	add_bb(&bank->lists[level], bb);
46}
47
48static inline struct basic_block *pop_bb(struct basic_block_list **list)
49{
50	return delete_ptr_list_last((struct ptr_list **)list);
51}
52
53static struct basic_block *bank_get(struct piggy *bank)
54{
55	int level = bank->max;
56	do {
57		struct basic_block *bb = pop_bb(&bank->lists[level]);
58		if (bb)
59			return bb;
60		if (!level)
61			return NULL;
62		bank->max = --level;
63	} while (1);
64}
65
66
67#define	VISITED	0x1
68#define	INPHI	0x2
69#define	ALPHA	0x4
70#define	FLAGS	0x7
71
72static void visit(struct piggy *bank, struct basic_block_list **idf, struct basic_block *x, int curr_level)
73{
74	struct basic_block *y;
75
76	x->generation |= 1;
77	FOR_EACH_PTR(x->children, y) {
78		unsigned flags = y->generation & FLAGS;
79		if (y->idom == x)	// J-edges will be processed later
80			continue;
81		if (y->dom_level > curr_level)
82			continue;
83		if (flags & INPHI)
84			continue;
85		y->generation |= INPHI;
86		add_bb(idf, y);
87		if (flags & ALPHA)
88			continue;
89		bank_put(bank, y);
90	} END_FOR_EACH_PTR(y);
91
92	FOR_EACH_PTR(x->doms, y) {
93		if (y->generation & VISITED)
94			continue;
95		visit(bank, idf, y, curr_level);
96	} END_FOR_EACH_PTR(y);
97}
98
99void idf_compute(struct entrypoint *ep, struct basic_block_list **idf, struct basic_block_list *alpha)
100{
101	int levels = ep->dom_levels;
102	struct piggy *bank = bank_init(levels);
103	struct basic_block *bb;
104	unsigned long generation = bb_generation;
105
106	generation = bb_generation;
107	generation += -generation & FLAGS;
108	bb_generation = generation + (FLAGS + 1);
109
110	// init all the nodes
111	FOR_EACH_PTR(ep->bbs, bb) {
112		// FIXME: this should be removed and the tests for
113		//	  visited/in_phi/alpha should use a sparse set
114		bb->generation = generation;
115	} END_FOR_EACH_PTR(bb);
116
117	FOR_EACH_PTR(alpha, bb) {
118		bb->generation = generation | ALPHA;
119		bank_put(bank, bb);
120	} END_FOR_EACH_PTR(bb);
121
122	while ((bb = bank_get(bank))) {
123		visit(bank, idf, bb, bb->dom_level);
124	}
125
126	bank_free(bank, levels);
127}
128
129void idf_dump(struct entrypoint *ep)
130{
131	struct basic_block *bb;
132
133	domtree_build(ep);
134
135	printf("%s's IDF:\n", show_ident(ep->name->ident));
136	FOR_EACH_PTR(ep->bbs, bb) {
137		struct basic_block_list *alpha = NULL;
138		struct basic_block_list *idf = NULL;
139		struct basic_block *df;
140
141		add_bb(&alpha, bb);
142		idf_compute(ep, &idf, alpha);
143
144		printf("\t%s\t<-", show_label(bb));
145		FOR_EACH_PTR(idf, df) {
146			printf(" %s", show_label(df));
147		} END_FOR_EACH_PTR(df);
148		printf("\n");
149
150		free_ptr_list(&idf);
151		free_ptr_list(&alpha);
152	} END_FOR_EACH_PTR(bb);
153}
154