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 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?
domtree_dominates(struct basic_block * a,struct basic_block * b)202 bool 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