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