1// SPDX-License-Identifier: MIT
2//
3// Various utilities for flowgraphs.
4//
5// Copyright (c) 2017 Luc Van Oostenryck.
6//
7
8#include "flowgraph.h"
9#include "linearize.h"
10#include "flow.h"			// for bb_generation
11#include <assert.h>
12#include <stdio.h>
13#include <stdlib.h>
14
15
16struct cfg_info {
17	struct basic_block_list *list;
18	unsigned long gen;
19	unsigned int nr;
20};
21
22
23static void label_postorder(struct basic_block *bb, struct cfg_info *info)
24{
25	struct basic_block *child;
26
27	if (bb->generation == info->gen)
28		return;
29
30	bb->generation = info->gen;
31	FOR_EACH_PTR_REVERSE(bb->children, child) {
32		label_postorder(child, info);
33	} END_FOR_EACH_PTR_REVERSE(child);
34
35	bb->postorder_nr = info->nr++;
36	add_bb(&info->list, bb);
37}
38
39static void reverse_bbs(struct basic_block_list **dst, struct basic_block_list *src)
40{
41	struct basic_block *bb;
42	FOR_EACH_PTR_REVERSE(src, bb) {
43		add_bb(dst, bb);
44	} END_FOR_EACH_PTR_REVERSE(bb);
45}
46
47static void debug_postorder(struct entrypoint *ep)
48{
49	struct basic_block *bb;
50
51	printf("%s's reverse postorder:\n", show_ident(ep->name->ident));
52	FOR_EACH_PTR(ep->bbs, bb) {
53		printf("\t.L%u: %u\n", bb->nr, bb->postorder_nr);
54	} END_FOR_EACH_PTR(bb);
55}
56
57//
58// cfg_postorder - Set the BB's reverse postorder links
59//
60// Do a postorder DFS walk and set the links
61// (which will do the reverse part).
62//
63int cfg_postorder(struct entrypoint *ep)
64{
65	struct cfg_info info = {
66		.gen = ++bb_generation,
67	};
68
69	label_postorder(ep->entry->bb, &info);
70
71	// OK, now info.list contains the node in postorder
72	// Reuse ep->bbs for the reverse postorder.
73	free_ptr_list(&ep->bbs);
74	ep->bbs = NULL;
75	reverse_bbs(&ep->bbs, info.list);
76	free_ptr_list(&info.list);
77	if (dbg_postorder)
78		debug_postorder(ep);
79	return info.nr;
80}
81
82//
83// Calculate the dominance tree following:
84//	"A simple, fast dominance algorithm"
85//	by K. D. Cooper, T. J. Harvey, and K. Kennedy.
86//	cfr. http://www.cs.rice.edu/∼keith/EMBED/dom.pdf
87//
88static struct basic_block *intersect_dom(struct basic_block *doms[],
89		struct basic_block *b1, struct basic_block *b2)
90{
91	int f1 = b1->postorder_nr, f2 = b2->postorder_nr;
92	while (f1 != f2) {
93		while (f1 < f2) {
94			b1 = doms[f1];
95			f1 = b1->postorder_nr;
96		}
97		while (f2 < f1) {
98			b2 = doms[f2];
99			f2 = b2->postorder_nr;
100		}
101	}
102	return b1;
103}
104
105static void debug_domtree(struct entrypoint *ep)
106{
107	struct basic_block *bb = ep->entry->bb;
108
109	printf("%s's idoms:\n", show_ident(ep->name->ident));
110	FOR_EACH_PTR(ep->bbs, bb) {
111		if (bb == ep->entry->bb)
112			continue;	// entry node has no idom
113		printf("\t%s	<- %s\n", show_label(bb), show_label(bb->idom));
114	} END_FOR_EACH_PTR(bb);
115}
116
117void domtree_build(struct entrypoint *ep)
118{
119	struct basic_block *entry = ep->entry->bb;
120	struct basic_block **doms;
121	struct basic_block *bb;
122	unsigned int size;
123	int max_level = 0;
124	int changed;
125
126	// First calculate the (reverse) postorder.
127	// This will give use us:
128	//	- the links to do a reverse postorder traversal
129	//	- the order number for each block
130	size = cfg_postorder(ep);
131
132	// initialize the dominators array
133	doms = calloc(size, sizeof(*doms));
134	assert(entry->postorder_nr == size-1);
135	doms[size-1] = entry;
136
137	do {
138		struct basic_block *b;
139
140		changed = 0;
141		FOR_EACH_PTR(ep->bbs, b) {
142			struct basic_block *p;
143			int bnr = b->postorder_nr;
144			struct basic_block *new_idom = NULL;
145
146			if (b == entry)
147				continue;	// ignore entry node
148
149			FOR_EACH_PTR(b->parents, p) {
150				unsigned int pnr = p->postorder_nr;
151				if (!doms[pnr])
152					continue;
153				if (!new_idom) {
154					new_idom = p;
155					continue;
156				}
157
158				new_idom = intersect_dom(doms, p, new_idom);
159			} END_FOR_EACH_PTR(p);
160
161			assert(new_idom);
162			if (doms[bnr] != new_idom) {
163				doms[bnr] = new_idom;
164				changed = 1;
165			}
166		} END_FOR_EACH_PTR(b);
167	} while (changed);
168
169	FOR_EACH_PTR(ep->bbs, bb) {
170		free_ptr_list(&bb->doms);
171	} END_FOR_EACH_PTR(bb);
172
173	// set the idom links
174	FOR_EACH_PTR(ep->bbs, bb) {
175		struct basic_block *idom = doms[bb->postorder_nr];
176
177		if (bb == entry)
178			continue;	// ignore entry node
179
180		bb->idom = idom;
181		add_bb(&idom->doms, bb);
182	} END_FOR_EACH_PTR(bb);
183	entry->idom = NULL;
184
185	// set the dominance levels
186	FOR_EACH_PTR(ep->bbs, bb) {
187		struct basic_block *idom = bb->idom;
188		int level = idom ? idom->dom_level + 1 : 0;
189
190		bb->dom_level = level;
191		if (max_level < level)
192			max_level = level;
193	} END_FOR_EACH_PTR(bb);
194	ep->dom_levels = max_level + 1;
195
196	free(doms);
197	if (dbg_domtree)
198		debug_domtree(ep);
199}
200
201// dt_dominates - does BB a dominates BB b?
202bool domtree_dominates(struct basic_block *a, struct basic_block *b)
203{
204	if (a == b)			// dominance is reflexive
205		return true;
206	if (a == b->idom)
207		return true;
208	if (b == a->idom)
209		return false;
210
211	// can't dominate if deeper in the DT
212	if (a->dom_level >= b->dom_level)
213		return false;
214
215	// FIXME: can be faster if we have the DFS in-out numbers
216
217	// walk up the dominator tree
218	for (b = b->idom; b; b = b->idom) {
219		if (b == a)
220			return true;
221	}
222	return false;
223}
224