1#include "all.h"
2#include <stdarg.h>
3
4static void
5adduse(Tmp *tmp, int ty, Blk *b, ...)
6{
7 Use *u;
8 int n;
9 va_list ap;
10
11 if (!tmp->use)
12 return;
13 va_start(ap, b);
14 n = tmp->nuse;
15 vgrow(&tmp->use, ++tmp->nuse);
16 u = &tmp->use[n];
17 u->type = ty;
18 u->bid = b->id;
19 switch (ty) {
20 case UPhi:
21 u->u.phi = va_arg(ap, Phi *);
22 break;
23 case UIns:
24 u->u.ins = va_arg(ap, Ins *);
25 break;
26 case UJmp:
27 break;
28 default:
29 die("unreachable");
30 }
31 va_end(ap);
32}
33
34/* fill usage, width, phi, and class information
35 * must not change .visit fields
36 */
37void
38filluse(Fn *fn)
39{
40 Blk *b;
41 Phi *p;
42 Ins *i;
43 int m, t, tp, w;
44 uint a;
45 Tmp *tmp;
46
47 /* todo, is this the correct file? */
48 tmp = fn->tmp;
49 for (t=Tmp0; t<fn->ntmp; t++) {
50 tmp[t].bid = -1u;
51 tmp[t].ndef = 0;
52 tmp[t].nuse = 0;
53 tmp[t].cls = 0;
54 tmp[t].phi = 0;
55 tmp[t].width = WFull;
56 if (tmp[t].use == 0)
57 tmp[t].use = vnew(0, sizeof(Use), Pfn);
58 }
59 for (b=fn->start; b; b=b->link) {
60 for (p=b->phi; p; p=p->link) {
61 assert(rtype(p->to) == RTmp);
62 tp = p->to.val;
63 tmp[tp].bid = b->id;
64 tmp[tp].ndef++;
65 tmp[tp].cls = p->cls;
66 tp = phicls(tp, fn->tmp);
67 for (a=0; a<p->narg; a++)
68 if (rtype(p->arg[a]) == RTmp) {
69 t = p->arg[a].val;
70 adduse(&tmp[t], UPhi, b, p);
71 t = phicls(t, fn->tmp);
72 if (t != tp)
73 tmp[t].phi = tp;
74 }
75 }
76 for (i=b->ins; i<&b->ins[b->nins]; i++) {
77 if (!req(i->to, R)) {
78 assert(rtype(i->to) == RTmp);
79 w = WFull;
80 if (isload(i->op) && i->op != Oload)
81 w = Wsb + (i->op - Oloadsb);
82 if (isext(i->op))
83 w = Wsb + (i->op - Oextsb);
84 if (w == Wsw || w == Wuw)
85 if (i->cls == Kw)
86 w = WFull;
87 t = i->to.val;
88 tmp[t].width = w;
89 tmp[t].bid = b->id;
90 tmp[t].ndef++;
91 tmp[t].cls = i->cls;
92 }
93 for (m=0; m<2; m++)
94 if (rtype(i->arg[m]) == RTmp) {
95 t = i->arg[m].val;
96 adduse(&tmp[t], UIns, b, i);
97 }
98 }
99 if (rtype(b->jmp.arg) == RTmp)
100 adduse(&tmp[b->jmp.arg.val], UJmp, b);
101 }
102}
103
104static Ref
105refindex(int t, Fn *fn)
106{
107 return newtmp(fn->tmp[t].name, fn->tmp[t].cls, fn);
108}
109
110static void
111phiins(Fn *fn)
112{
113 BSet u[1], defs[1];
114 Blk *a, *b, **blist, **be, **bp;
115 Ins *i;
116 Phi *p;
117 Use *use;
118 Ref r;
119 int t, nt, ok;
120 uint n, defb;
121 short k;
122
123 bsinit(u, fn->nblk);
124 bsinit(defs, fn->nblk);
125 blist = emalloc(fn->nblk * sizeof blist[0]);
126 be = &blist[fn->nblk];
127 nt = fn->ntmp;
128 for (t=Tmp0; t<nt; t++) {
129 fn->tmp[t].visit = 0;
130 if (fn->tmp[t].phi != 0)
131 continue;
132 if (fn->tmp[t].ndef == 1) {
133 ok = 1;
134 defb = fn->tmp[t].bid;
135 use = fn->tmp[t].use;
136 for (n=fn->tmp[t].nuse; n--; use++)
137 ok &= use->bid == defb;
138 if (ok || defb == fn->start->id)
139 continue;
140 }
141 bszero(u);
142 k = -1;
143 bp = be;
144 for (b=fn->start; b; b=b->link) {
145 b->visit = 0;
146 r = R;
147 for (i=b->ins; i<&b->ins[b->nins]; i++) {
148 if (!req(r, R)) {
149 if (req(i->arg[0], TMP(t)))
150 i->arg[0] = r;
151 if (req(i->arg[1], TMP(t)))
152 i->arg[1] = r;
153 }
154 if (req(i->to, TMP(t))) {
155 if (!bshas(b->out, t)) {
156 r = refindex(t, fn);
157 i->to = r;
158 } else {
159 if (!bshas(u, b->id)) {
160 bsset(u, b->id);
161 *--bp = b;
162 }
163 if (clsmerge(&k, i->cls))
164 die("invalid input");
165 }
166 }
167 }
168 if (!req(r, R) && req(b->jmp.arg, TMP(t)))
169 b->jmp.arg = r;
170 }
171 bscopy(defs, u);
172 while (bp != be) {
173 fn->tmp[t].visit = t;
174 b = *bp++;
175 bsclr(u, b->id);
176 for (n=0; n<b->nfron; n++) {
177 a = b->fron[n];
178 if (a->visit++ == 0)
179 if (bshas(a->in, t)) {
180 p = alloc(sizeof *p);
181 p->cls = k;
182 p->to = TMP(t);
183 p->link = a->phi;
184 p->arg = vnew(0, sizeof p->arg[0], Pfn);
185 p->blk = vnew(0, sizeof p->blk[0], Pfn);
186 a->phi = p;
187 if (!bshas(defs, a->id))
188 if (!bshas(u, a->id)) {
189 bsset(u, a->id);
190 *--bp = a;
191 }
192 }
193 }
194 }
195 }
196 free(blist);
197}
198
199typedef struct Name Name;
200struct Name {
201 Ref r;
202 Blk *b;
203 Name *up;
204};
205
206static Name *namel;
207
208static Name *
209nnew(Ref r, Blk *b, Name *up)
210{
211 Name *n;
212
213 if (namel) {
214 n = namel;
215 namel = n->up;
216 } else
217 /* could use alloc, here
218 * but namel should be reset
219 */
220 n = emalloc(sizeof *n);
221 n->r = r;
222 n->b = b;
223 n->up = up;
224 return n;
225}
226
227static void
228nfree(Name *n)
229{
230 n->up = namel;
231 namel = n;
232}
233
234static void
235rendef(Ref *r, Blk *b, Name **stk, Fn *fn)
236{
237 Ref r1;
238 int t;
239
240 t = r->val;
241 if (req(*r, R) || !fn->tmp[t].visit)
242 return;
243 r1 = refindex(t, fn);
244 fn->tmp[r1.val].visit = t;
245 stk[t] = nnew(r1, b, stk[t]);
246 *r = r1;
247}
248
249static Ref
250getstk(int t, Blk *b, Name **stk)
251{
252 Name *n, *n1;
253
254 n = stk[t];
255 while (n && !dom(n->b, b)) {
256 n1 = n;
257 n = n->up;
258 nfree(n1);
259 }
260 stk[t] = n;
261 if (!n) {
262 /* uh, oh, warn */
263 return CON_Z;
264 } else
265 return n->r;
266}
267
268static void
269renblk(Blk *b, Name **stk, Fn *fn)
270{
271 Phi *p;
272 Ins *i;
273 Blk *s, **ps, *succ[3];
274 int t, m;
275
276 for (p=b->phi; p; p=p->link)
277 rendef(&p->to, b, stk, fn);
278 for (i=b->ins; i<&b->ins[b->nins]; i++) {
279 for (m=0; m<2; m++) {
280 t = i->arg[m].val;
281 if (rtype(i->arg[m]) == RTmp)
282 if (fn->tmp[t].visit)
283 i->arg[m] = getstk(t, b, stk);
284 }
285 rendef(&i->to, b, stk, fn);
286 }
287 t = b->jmp.arg.val;
288 if (rtype(b->jmp.arg) == RTmp)
289 if (fn->tmp[t].visit)
290 b->jmp.arg = getstk(t, b, stk);
291 succ[0] = b->s1;
292 succ[1] = b->s2 == b->s1 ? 0 : b->s2;
293 succ[2] = 0;
294 for (ps=succ; (s=*ps); ps++)
295 for (p=s->phi; p; p=p->link) {
296 t = p->to.val;
297 if ((t=fn->tmp[t].visit)) {
298 m = p->narg++;
299 vgrow(&p->arg, p->narg);
300 vgrow(&p->blk, p->narg);
301 p->arg[m] = getstk(t, b, stk);
302 p->blk[m] = b;
303 }
304 }
305 for (s=b->dom; s; s=s->dlink)
306 renblk(s, stk, fn);
307}
308
309/* require rpo and use */
310void
311ssa(Fn *fn)
312{
313 Name **stk, *n;
314 int d, nt;
315 Blk *b, *b1;
316
317 nt = fn->ntmp;
318 stk = emalloc(nt * sizeof stk[0]);
319 d = debug['L'];
320 debug['L'] = 0;
321 filldom(fn);
322 if (debug['N']) {
323 fprintf(stderr, "\n> Dominators:\n");
324 for (b1=fn->start; b1; b1=b1->link) {
325 if (!b1->dom)
326 continue;
327 fprintf(stderr, "%10s:", b1->name);
328 for (b=b1->dom; b; b=b->dlink)
329 fprintf(stderr, " %s", b->name);
330 fprintf(stderr, "\n");
331 }
332 }
333 fillfron(fn);
334 filllive(fn);
335 phiins(fn);
336 renblk(fn->start, stk, fn);
337 while (nt--)
338 while ((n=stk[nt])) {
339 stk[nt] = n->up;
340 nfree(n);
341 }
342 debug['L'] = d;
343 free(stk);
344 if (debug['N']) {
345 fprintf(stderr, "\n> After SSA construction:\n");
346 printfn(fn, stderr);
347 }
348}
349
350static int
351phicheck(Phi *p, Blk *b, Ref t)
352{
353 Blk *b1;
354 uint n;
355
356 for (n=0; n<p->narg; n++)
357 if (req(p->arg[n], t)) {
358 b1 = p->blk[n];
359 if (b1 != b && !sdom(b, b1))
360 return 1;
361 }
362 return 0;
363}
364
365/* require use and ssa */
366void
367ssacheck(Fn *fn)
368{
369 Tmp *t;
370 Ins *i;
371 Phi *p;
372 Use *u;
373 Blk *b, *bu;
374 Ref r;
375
376 for (t=&fn->tmp[Tmp0]; t-fn->tmp < fn->ntmp; t++) {
377 if (t->ndef > 1)
378 err("ssa temporary %%%s defined more than once",
379 t->name);
380 if (t->nuse > 0 && t->ndef == 0) {
381 bu = fn->rpo[t->use[0].bid];
382 goto Err;
383 }
384 }
385 for (b=fn->start; b; b=b->link) {
386 for (p=b->phi; p; p=p->link) {
387 r = p->to;
388 t = &fn->tmp[r.val];
389 for (u=t->use; u<&t->use[t->nuse]; u++) {
390 bu = fn->rpo[u->bid];
391 if (u->type == UPhi) {
392 if (phicheck(u->u.phi, b, r))
393 goto Err;
394 } else
395 if (bu != b && !sdom(b, bu))
396 goto Err;
397 }
398 }
399 for (i=b->ins; i<&b->ins[b->nins]; i++) {
400 if (rtype(i->to) != RTmp)
401 continue;
402 r = i->to;
403 t = &fn->tmp[r.val];
404 for (u=t->use; u<&t->use[t->nuse]; u++) {
405 bu = fn->rpo[u->bid];
406 if (u->type == UPhi) {
407 if (phicheck(u->u.phi, b, r))
408 goto Err;
409 } else {
410 if (bu == b) {
411 if (u->type == UIns)
412 if (u->u.ins <= i)
413 goto Err;
414 } else
415 if (!sdom(b, bu))
416 goto Err;
417 }
418 }
419 }
420 }
421 return;
422Err:
423 if (t->visit)
424 die("%%%s violates ssa invariant", t->name);
425 else
426 err("ssa temporary %%%s is used undefined in @%s",
427 t->name, bu->name);
428}
429