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 
16 struct cfg_info {
17 	struct basic_block_list *list;
18 	unsigned long gen;
19 	unsigned int nr;
20 };
21 
22 
label_postorder(struct basic_block * bb,struct cfg_info * info)23 static 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 
reverse_bbs(struct basic_block_list ** dst,struct basic_block_list * src)39 static 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 
debug_postorder(struct entrypoint * ep)47 static 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 //
cfg_postorder(struct entrypoint * ep)63 int 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 //
intersect_dom(struct basic_block * doms[],struct basic_block * b1,struct basic_block * b2)88 static 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 
debug_domtree(struct entrypoint * ep)105 static 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 
domtree_build(struct entrypoint * ep)117 void 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 	// set the idom links
170 	FOR_EACH_PTR(ep->bbs, bb) {
171 		struct basic_block *idom = doms[bb->postorder_nr];
172 
173 		if (bb == entry)
174 			continue;	// ignore entry node
175 
176 		bb->idom = idom;
177 		add_bb(&idom->doms, bb);
178 	} END_FOR_EACH_PTR(bb);
179 	entry->idom = NULL;
180 
181 	// set the dominance levels
182 	FOR_EACH_PTR(ep->bbs, bb) {
183 		struct basic_block *idom = bb->idom;
184 		int level = idom ? idom->dom_level + 1 : 0;
185 
186 		bb->dom_level = level;
187 		if (max_level < level)
188 			max_level = level;
189 	} END_FOR_EACH_PTR(bb);
190 	ep->dom_levels = max_level + 1;
191 
192 	free(doms);
193 	if (dbg_domtree)
194 		debug_domtree(ep);
195 }
196 
197 // dt_dominates - does BB a dominates BB b?
domtree_dominates(struct basic_block * a,struct basic_block * b)198 bool domtree_dominates(struct basic_block *a, struct basic_block *b)
199 {
200 	if (a == b)			// dominance is reflexive
201 		return true;
202 	if (a == b->idom)
203 		return true;
204 	if (b == a->idom)
205 		return false;
206 
207 	// can't dominate if deeper in the DT
208 	if (a->dom_level >= b->dom_level)
209 		return false;
210 
211 	// FIXME: can be faster if we have the DFS in-out numbers
212 
213 	// walk up the dominator tree
214 	for (b = b->idom; b; b = b->idom) {
215 		if (b == a)
216 			return true;
217 	}
218 	return false;
219 }
220