ssa.c

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