1#include "all.h"
2
3Blk *
4blknew()
5{
6 static Blk z;
7 Blk *b;
8
9 b = alloc(sizeof *b);
10 *b = z;
11 return b;
12}
13
14void
15edgedel(Blk *bs, Blk **pbd)
16{
17 Blk *bd;
18 Phi *p;
19 uint a;
20 int mult;
21
22 bd = *pbd;
23 mult = 1 + (bs->s1 == bs->s2);
24 *pbd = 0;
25 if (!bd || mult > 1)
26 return;
27 for (p=bd->phi; p; p=p->link) {
28 for (a=0; p->blk[a]!=bs; a++)
29 assert(a+1<p->narg);
30 p->narg--;
31 memmove(&p->blk[a], &p->blk[a+1],
32 sizeof p->blk[0] * (p->narg-a));
33 memmove(&p->arg[a], &p->arg[a+1],
34 sizeof p->arg[0] * (p->narg-a));
35 }
36 if (bd->npred != 0) {
37 for (a=0; bd->pred[a]!=bs; a++)
38 assert(a+1<bd->npred);
39 bd->npred--;
40 memmove(&bd->pred[a], &bd->pred[a+1],
41 sizeof bd->pred[0] * (bd->npred-a));
42 }
43}
44
45static void
46addpred(Blk *bp, Blk *bc)
47{
48 if (!bc->pred) {
49 bc->pred = alloc(bc->npred * sizeof bc->pred[0]);
50 bc->visit = 0;
51 }
52 bc->pred[bc->visit++] = bp;
53}
54
55/* fill predecessors information in blocks */
56void
57fillpreds(Fn *f)
58{
59 Blk *b;
60
61 for (b=f->start; b; b=b->link) {
62 b->npred = 0;
63 b->pred = 0;
64 }
65 for (b=f->start; b; b=b->link) {
66 if (b->s1)
67 b->s1->npred++;
68 if (b->s2 && b->s2 != b->s1)
69 b->s2->npred++;
70 }
71 for (b=f->start; b; b=b->link) {
72 if (b->s1)
73 addpred(b, b->s1);
74 if (b->s2 && b->s2 != b->s1)
75 addpred(b, b->s2);
76 }
77}
78
79static int
80rporec(Blk *b, uint x)
81{
82 Blk *s1, *s2;
83
84 if (!b || b->id != -1u)
85 return x;
86 b->id = 1;
87 s1 = b->s1;
88 s2 = b->s2;
89 if (s1 && s2 && s1->loop > s2->loop) {
90 s1 = b->s2;
91 s2 = b->s1;
92 }
93 x = rporec(s1, x);
94 x = rporec(s2, x);
95 b->id = x;
96 assert(x != -1u);
97 return x - 1;
98}
99
100/* fill the rpo information */
101void
102fillrpo(Fn *f)
103{
104 uint n;
105 Blk *b, **p;
106
107 for (b=f->start; b; b=b->link)
108 b->id = -1u;
109 n = 1 + rporec(f->start, f->nblk-1);
110 f->nblk -= n;
111 f->rpo = alloc(f->nblk * sizeof f->rpo[0]);
112 for (p=&f->start; (b=*p);) {
113 if (b->id == -1u) {
114 edgedel(b, &b->s1);
115 edgedel(b, &b->s2);
116 *p = b->link;
117 } else {
118 b->id -= n;
119 f->rpo[b->id] = b;
120 p = &b->link;
121 }
122 }
123}
124
125/* for dominators computation, read
126 * "A Simple, Fast Dominance Algorithm"
127 * by K. Cooper, T. Harvey, and K. Kennedy.
128 */
129
130static Blk *
131inter(Blk *b1, Blk *b2)
132{
133 Blk *bt;
134
135 if (b1 == 0)
136 return b2;
137 while (b1 != b2) {
138 if (b1->id < b2->id) {
139 bt = b1;
140 b1 = b2;
141 b2 = bt;
142 }
143 while (b1->id > b2->id) {
144 b1 = b1->idom;
145 assert(b1);
146 }
147 }
148 return b1;
149}
150
151void
152filldom(Fn *fn)
153{
154 Blk *b, *d;
155 int ch;
156 uint n, p;
157
158 for (b=fn->start; b; b=b->link) {
159 b->idom = 0;
160 b->dom = 0;
161 b->dlink = 0;
162 }
163 do {
164 ch = 0;
165 for (n=1; n<fn->nblk; n++) {
166 b = fn->rpo[n];
167 d = 0;
168 for (p=0; p<b->npred; p++)
169 if (b->pred[p]->idom
170 || b->pred[p] == fn->start)
171 d = inter(d, b->pred[p]);
172 if (d != b->idom) {
173 ch++;
174 b->idom = d;
175 }
176 }
177 } while (ch);
178 for (b=fn->start; b; b=b->link)
179 if ((d=b->idom)) {
180 assert(d != b);
181 b->dlink = d->dom;
182 d->dom = b;
183 }
184}
185
186int
187sdom(Blk *b1, Blk *b2)
188{
189 assert(b1 && b2);
190 if (b1 == b2)
191 return 0;
192 while (b2->id > b1->id)
193 b2 = b2->idom;
194 return b1 == b2;
195}
196
197int
198dom(Blk *b1, Blk *b2)
199{
200 return b1 == b2 || sdom(b1, b2);
201}
202
203static void
204addfron(Blk *a, Blk *b)
205{
206 uint n;
207
208 for (n=0; n<a->nfron; n++)
209 if (a->fron[n] == b)
210 return;
211 if (!a->nfron)
212 a->fron = vnew(++a->nfron, sizeof a->fron[0], Pfn);
213 else
214 vgrow(&a->fron, ++a->nfron);
215 a->fron[a->nfron-1] = b;
216}
217
218/* fill the dominance frontier */
219void
220fillfron(Fn *fn)
221{
222 Blk *a, *b;
223
224 for (b=fn->start; b; b=b->link)
225 b->nfron = 0;
226 for (b=fn->start; b; b=b->link) {
227 if (b->s1)
228 for (a=b; !sdom(a, b->s1); a=a->idom)
229 addfron(a, b->s1);
230 if (b->s2)
231 for (a=b; !sdom(a, b->s2); a=a->idom)
232 addfron(a, b->s2);
233 }
234}
235
236static void
237loopmark(Blk *hd, Blk *b, void f(Blk *, Blk *))
238{
239 uint p;
240
241 if (b->id < hd->id || b->visit == hd->id)
242 return;
243 b->visit = hd->id;
244 f(hd, b);
245 for (p=0; p<b->npred; ++p)
246 loopmark(hd, b->pred[p], f);
247}
248
249void
250loopiter(Fn *fn, void f(Blk *, Blk *))
251{
252 uint n, p;
253 Blk *b;
254
255 for (b=fn->start; b; b=b->link)
256 b->visit = -1u;
257 for (n=0; n<fn->nblk; ++n) {
258 b = fn->rpo[n];
259 for (p=0; p<b->npred; ++p)
260 if (b->pred[p]->id >= n)
261 loopmark(b, b->pred[p], f);
262 }
263}
264
265void
266multloop(Blk *hd, Blk *b)
267{
268 (void)hd;
269 b->loop *= 10;
270}
271
272void
273fillloop(Fn *fn)
274{
275 Blk *b;
276
277 for (b=fn->start; b; b=b->link)
278 b->loop = 1;
279 loopiter(fn, multloop);
280}
281
282static void
283uffind(Blk **pb, Blk **uf)
284{
285 Blk **pb1;
286
287 pb1 = &uf[(*pb)->id];
288 if (*pb1) {
289 uffind(pb1, uf);
290 *pb = *pb1;
291 }
292}
293
294/* requires rpo and no phis, breaks cfg */
295void
296simpljmp(Fn *fn)
297{
298
299 Blk **uf; /* union-find */
300 Blk **p, *b, *ret;
301
302 ret = blknew();
303 ret->id = fn->nblk++;
304 ret->jmp.type = Jret0;
305 uf = emalloc(fn->nblk * sizeof uf[0]);
306 for (b=fn->start; b; b=b->link) {
307 assert(!b->phi);
308 if (b->jmp.type == Jret0) {
309 b->jmp.type = Jjmp;
310 b->s1 = ret;
311 }
312 if (b->nins == 0)
313 if (b->jmp.type == Jjmp) {
314 uffind(&b->s1, uf);
315 if (b->s1 != b)
316 uf[b->id] = b->s1;
317 }
318 }
319 for (p=&fn->start; (b=*p); p=&b->link) {
320 if (b->s1)
321 uffind(&b->s1, uf);
322 if (b->s2)
323 uffind(&b->s2, uf);
324 if (b->s1 && b->s1 == b->s2) {
325 b->jmp.type = Jjmp;
326 b->s2 = 0;
327 }
328 }
329 *p = ret;
330 free(uf);
331}
332