cfg.c

   1 #include "all.h"
   2
   3 Blk *
   4 blknew()
   5 {
   6         static Blk z;
   7         Blk *b;
   8
   9         b = alloc(sizeof *b);
  10         *b = z;
  11         return b;
  12 }
  13
  14 void
  15 edgedel(Blk *bs, Blk **pbd)
  16 {
  17         Blk *bd;
  18         Phi *p;
  19         uint a;
  20         int mult;
  21
  22         bd = *pbd;
  23         mult = 1 + (bs->s1 == bs->s2);
  24         *pbd = 0;
  25         if (!bd || mult > 1)
  26                 return;
  27         for (p=bd->phi; p; p=p->link) {
  28                 for (a=0; p->blk[a]!=bs; a++)
  29                         assert(a+1<p->narg);
  30                 p->narg--;
  31                 memmove(&p->blk[a], &p->blk[a+1],
  32                         sizeof p->blk[0] * (p->narg-a));
  33                 memmove(&p->arg[a], &p->arg[a+1],
  34                         sizeof p->arg[0] * (p->narg-a));
  35         }
  36         if (bd->npred != 0) {
  37                 for (a=0; bd->pred[a]!=bs; a++)
  38                         assert(a+1<bd->npred);
  39                 bd->npred--;
  40                 memmove(&bd->pred[a], &bd->pred[a+1],
  41                         sizeof bd->pred[0] * (bd->npred-a));
  42         }
  43 }
  44
  45 static void
  46 addpred(Blk *bp, Blk *bc)
  47 {
  48         if (!bc->pred) {
  49                 bc->pred = alloc(bc->npred * sizeof bc->pred[0]);
  50                 bc->visit = 0;
  51         }
  52         bc->pred[bc->visit++] = bp;
  53 }
  54
  55 /* fill predecessors information in blocks */
  56 void
  57 fillpreds(Fn *f)
  58 {
  59         Blk *b;
  60
  61         for (b=f->start; b; b=b->link) {
  62                 b->npred = 0;
  63                 b->pred = 0;
  64         }
  65         for (b=f->start; b; b=b->link) {
  66                 if (b->s1)
  67                         b->s1->npred++;
  68                 if (b->s2 && b->s2 != b->s1)
  69                         b->s2->npred++;
  70         }
  71         for (b=f->start; b; b=b->link) {
  72                 if (b->s1)
  73                         addpred(b, b->s1);
  74                 if (b->s2 && b->s2 != b->s1)
  75                         addpred(b, b->s2);
  76         }
  77 }
  78
  79 static int
  80 rporec(Blk *b, uint x)
  81 {
  82         Blk *s1, *s2;
  83
  84         if (!b || b->id != -1u)
  85                 return x;
  86         b->id = 1;
  87         s1 = b->s1;
  88         s2 = b->s2;
  89         if (s1 && s2 && s1->loop > s2->loop) {
  90                 s1 = b->s2;
  91                 s2 = b->s1;
  92         }
  93         x = rporec(s1, x);
  94         x = rporec(s2, x);
  95         b->id = x;
  96         assert(x != -1u);
  97         return x - 1;
  98 }
  99
 100 /* fill the rpo information */
 101 void
 102 fillrpo(Fn *f)
 103 {
 104         uint n;
 105         Blk *b, **p;
 106
 107         for (b=f->start; b; b=b->link)
 108                 b->id = -1u;
 109         n = 1 + rporec(f->start, f->nblk-1);
 110         f->nblk -= n;
 111         f->rpo = alloc(f->nblk * sizeof f->rpo[0]);
 112         for (p=&f->start; (b=*p);) {
 113                 if (b->id == -1u) {
 114                         edgedel(b, &b->s1);
 115                         edgedel(b, &b->s2);
 116                         *p = b->link;
 117                 } else {
 118                         b->id -= n;
 119                         f->rpo[b->id] = b;
 120                         p = &b->link;
 121                 }
 122         }
 123 }
 124
 125 /* for dominators computation, read
 126  * "A Simple, Fast Dominance Algorithm"
 127  * by K. Cooper, T. Harvey, and K. Kennedy.
 128  */
 129
 130 static Blk *
 131 inter(Blk *b1, Blk *b2)
 132 {
 133         Blk *bt;
 134
 135         if (b1 == 0)
 136                 return b2;
 137         while (b1 != b2) {
 138                 if (b1->id < b2->id) {
 139                         bt = b1;
 140                         b1 = b2;
 141                         b2 = bt;
 142                 }
 143                 while (b1->id > b2->id) {
 144                         b1 = b1->idom;
 145                         assert(b1);
 146                 }
 147         }
 148         return b1;
 149 }
 150
 151 void
 152 filldom(Fn *fn)
 153 {
 154         Blk *b, *d;
 155         int ch;
 156         uint n, p;
 157
 158         for (b=fn->start; b; b=b->link) {
 159                 b->idom = 0;
 160                 b->dom = 0;
 161                 b->dlink = 0;
 162         }
 163         do {
 164                 ch = 0;
 165                 for (n=1; n<fn->nblk; n++) {
 166                         b = fn->rpo[n];
 167                         d = 0;
 168                         for (p=0; p<b->npred; p++)
 169                                 if (b->pred[p]->idom
 170                                 ||  b->pred[p] == fn->start)
 171                                         d = inter(d, b->pred[p]);
 172                         if (d != b->idom) {
 173                                 ch++;
 174                                 b->idom = d;
 175                         }
 176                 }
 177         } while (ch);
 178         for (b=fn->start; b; b=b->link)
 179                 if ((d=b->idom)) {
 180                         assert(d != b);
 181                         b->dlink = d->dom;
 182                         d->dom = b;
 183                 }
 184 }
 185
 186 int
 187 sdom(Blk *b1, Blk *b2)
 188 {
 189         assert(b1 && b2);
 190         if (b1 == b2)
 191                 return 0;
 192         while (b2->id > b1->id)
 193                 b2 = b2->idom;
 194         return b1 == b2;
 195 }
 196
 197 int
 198 dom(Blk *b1, Blk *b2)
 199 {
 200         return b1 == b2 || sdom(b1, b2);
 201 }
 202
 203 static void
 204 addfron(Blk *a, Blk *b)
 205 {
 206         uint n;
 207
 208         for (n=0; n<a->nfron; n++)
 209                 if (a->fron[n] == b)
 210                         return;
 211         if (!a->nfron)
 212                 a->fron = vnew(++a->nfron, sizeof a->fron[0], PFn);
 213         else
 214                 vgrow(&a->fron, ++a->nfron);
 215         a->fron[a->nfron-1] = b;
 216 }
 217
 218 /* fill the dominance frontier */
 219 void
 220 fillfron(Fn *fn)
 221 {
 222         Blk *a, *b;
 223
 224         for (b=fn->start; b; b=b->link)
 225                 b->nfron = 0;
 226         for (b=fn->start; b; b=b->link) {
 227                 if (b->s1)
 228                         for (a=b; !sdom(a, b->s1); a=a->idom)
 229                                 addfron(a, b->s1);
 230                 if (b->s2)
 231                         for (a=b; !sdom(a, b->s2); a=a->idom)
 232                                 addfron(a, b->s2);
 233         }
 234 }
 235
 236 static void
 237 loopmark(Blk *hd, Blk *b, void f(Blk *, Blk *))
 238 {
 239         uint p;
 240
 241         if (b->id < hd->id || b->visit == hd->id)
 242                 return;
 243         b->visit = hd->id;
 244         f(hd, b);
 245         for (p=0; p<b->npred; ++p)
 246                 loopmark(hd, b->pred[p], f);
 247 }
 248
 249 void
 250 loopiter(Fn *fn, void f(Blk *, Blk *))
 251 {
 252         uint n, p;
 253         Blk *b;
 254
 255         for (b=fn->start; b; b=b->link)
 256                 b->visit = -1u;
 257         for (n=0; n<fn->nblk; ++n) {
 258                 b = fn->rpo[n];
 259                 for (p=0; p<b->npred; ++p)
 260                         if (b->pred[p]->id >= n)
 261                                 loopmark(b, b->pred[p], f);
 262         }
 263 }
 264
 265 void
 266 multloop(Blk *hd, Blk *b)
 267 {
 268         (void)hd;
 269         b->loop *= 10;
 270 }
 271
 272 void
 273 fillloop(Fn *fn)
 274 {
 275         Blk *b;
 276
 277         for (b=fn->start; b; b=b->link)
 278                 b->loop = 1;
 279         loopiter(fn, multloop);
 280 }
 281
 282 static void
 283 uffind(Blk **pb, Blk **uf)
 284 {
 285         Blk **pb1;
 286
 287         pb1 = &uf[(*pb)->id];
 288         if (*pb1) {
 289                 uffind(pb1, uf);
 290                 *pb = *pb1;
 291         }
 292 }
 293
 294 /* requires rpo and no phis, breaks cfg */
 295 void
 296 simpljmp(Fn *fn)
 297 {
 298
 299         Blk **uf; /* union-find */
 300         Blk **p, *b, *ret;
 301
 302         ret = blknew();
 303         ret->id = fn->nblk++;
 304         ret->jmp.type = Jret0;
 305         uf = emalloc(fn->nblk * sizeof uf[0]);
 306         for (b=fn->start; b; b=b->link) {
 307                 assert(!b->phi);
 308                 if (b->jmp.type == Jret0) {
 309                         b->jmp.type = Jjmp;
 310                         b->s1 = ret;
 311                 }
 312                 if (b->nins == 0)
 313                 if (b->jmp.type == Jjmp) {
 314                         uffind(&b->s1, uf);
 315                         if (b->s1 != b)
 316                                 uf[b->id] = b->s1;
 317                 }
 318         }
 319         for (p=&fn->start; (b=*p); p=&b->link) {
 320                 if (b->s1)
 321                         uffind(&b->s1, uf);
 322                 if (b->s2)
 323                         uffind(&b->s2, uf);
 324                 if (b->s1 && b->s1 == b->s2) {
 325                         b->jmp.type = Jjmp;
 326                         b->s2 = 0;
 327                 }
 328         }
 329         *p = ret;
 330         free(uf);
 331 }