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