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