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