copy.c

   1 #include "all.h"
   2
   3 static int
   4 iscopy(Ins *i, Ref r, Tmp *tmp)
   5 {
   6         static bits extcpy[] = {
   7                 [WFull] = 0,
   8                 [Wsb] = BIT(Wsb) | BIT(Wsh) | BIT(Wsw),
   9                 [Wub] = BIT(Wub) | BIT(Wuh) | BIT(Wuw),
  10                 [Wsh] = BIT(Wsh) | BIT(Wsw),
  11                 [Wuh] = BIT(Wuh) | BIT(Wuw),
  12                 [Wsw] = BIT(Wsw),
  13                 [Wuw] = BIT(Wuw),
  14         };
  15         bits b;
  16         Tmp *t;
  17
  18         if (i->op == Ocopy)
  19                 return 1;
  20         if (!isext(i->op) || rtype(r) != RTmp)
  21                 return 0;
  22         if (i->op == Oextsw || i->op == Oextuw)
  23         if (i->cls == Kw)
  24                 return 1;
  25
  26         t = &tmp[r.val];
  27         assert(KBASE(t->cls) == 0);
  28         if (i->cls == Kl && t->cls == Kw)
  29                 return 0;
  30         b = extcpy[t->width];
  31         return (BIT(Wsb + (i->op-Oextsb)) & b) != 0;
  32 }
  33
  34 static Ref
  35 copyof(Ref r, Ref *cpy)
  36 {
  37         if (rtype(r) == RTmp && !req(cpy[r.val], R))
  38                 return cpy[r.val];
  39         return r;
  40 }
  41
  42 /* detects a cluster of phis/copies redundant with 'r';
  43  * the algorithm is inspired by Section 3.2 of "Simple
  44  * and Efficient SSA Construction" by Braun M. et al.
  45  */
  46 static void
  47 phisimpl(Phi *p, Ref r, Ref *cpy, Use ***pstk, BSet *ts, BSet *as, Tmp *tmp)
  48 {
  49         Use **stk, *u, *u1;
  50         uint nstk, a;
  51         int t;
  52         Ref r1;
  53
  54         bszero(ts);
  55         bszero(as);
  56         stk = *pstk;
  57         nstk = 1;
  58         stk[0] = &(Use){.type = UPhi, .u.phi = p};
  59         while (nstk) {
  60                 u = stk[--nstk];
  61                 if (u->type == UIns && iscopy(u->u.ins, r, tmp)) {
  62                         p = &(Phi){.narg = 0};
  63                         t = u->u.ins->to.val;
  64                 }
  65                 else if (u->type == UPhi) {
  66                         p = u->u.phi;
  67                         t = p->to.val;
  68                 }
  69                 else
  70                         continue;
  71                 if (bshas(ts, t))
  72                         continue;
  73                 bsset(ts, t);
  74                 for (a=0; a<p->narg; a++) {
  75                         r1 = copyof(p->arg[a], cpy);
  76                         if (req(r1, r))
  77                                 continue;
  78                         if (rtype(r1) != RTmp)
  79                                 return;
  80                         bsset(as, r1.val);
  81                 }
  82                 u = tmp[t].use;
  83                 u1 = &u[tmp[t].nuse];
  84                 vgrow(pstk, nstk+(u1-u));
  85                 stk = *pstk;
  86                 for (; u<u1; u++)
  87                         stk[nstk++] = u;
  88         }
  89         bsdiff(as, ts);
  90         if (!bscount(as))
  91                 for (t=0; bsiter(ts, &t); t++)
  92                         cpy[t] = r;
  93 }
  94
  95 static void
  96 subst(Ref *pr, Ref *cpy)
  97 {
  98         assert(rtype(*pr) != RTmp || !req(cpy[pr->val], R));
  99         *pr = copyof(*pr, cpy);
 100 }
 101
 102 /* requires use and rpo, breaks use */
 103 void
 104 copy(Fn *fn)
 105 {
 106         BSet ts[1], as[1];
 107         Use **stk;
 108         Phi *p, **pp;
 109         Ins *i;
 110         Blk *b;
 111         uint n, a;
 112         Ref *cpy, r;
 113         int t;
 114
 115         bsinit(ts, fn->ntmp);
 116         bsinit(as, fn->ntmp);
 117         cpy = emalloc(fn->ntmp * sizeof cpy[0]);
 118         stk = vnew(10, sizeof stk[0], Pheap);
 119
 120         /* 1. build the copy-of map */
 121         for (n=0; n<fn->nblk; n++) {
 122                 b = fn->rpo[n];
 123                 for (p=b->phi; p; p=p->link) {
 124                         assert(rtype(p->to) == RTmp);
 125                         if (!req(cpy[p->to.val], R))
 126                                 continue;
 127                         r = R;
 128                         for (a=0; a<p->narg; a++)
 129                                 if (p->blk[a]->id < n)
 130                                         r = copyof(p->arg[a], cpy);
 131                         assert(!req(r, R));
 132                         cpy[p->to.val] = p->to;
 133                         phisimpl(p, r, cpy, &stk, ts, as, fn->tmp);
 134                 }
 135                 for (i=b->ins; i<&b->ins[b->nins]; i++) {
 136                         assert(rtype(i->to) <= RTmp);
 137                         if (!req(cpy[i->to.val], R))
 138                                 continue;
 139                         r = copyof(i->arg[0], cpy);
 140                         if (iscopy(i, r, fn->tmp))
 141                                 cpy[i->to.val] = r;
 142                         else
 143                                 cpy[i->to.val] = i->to;
 144                 }
 145         }
 146
 147         /* 2. remove redundant phis/copies
 148          * and rewrite their uses */
 149         for (b=fn->start; b; b=b->link) {
 150                 for (pp=&b->phi; (p=*pp);) {
 151                         r = cpy[p->to.val];
 152                         if (!req(r, p->to)) {
 153                                 *pp = p->link;
 154                                 continue;
 155                         }
 156                         for (a=0; a<p->narg; a++)
 157                                 subst(&p->arg[a], cpy);
 158                         pp=&p->link;
 159                 }
 160                 for (i=b->ins; i<&b->ins[b->nins]; i++) {
 161                         r = cpy[i->to.val];
 162                         if (!req(r, i->to)) {
 163                                 *i = (Ins){.op = Onop};
 164                                 continue;
 165                         }
 166                         subst(&i->arg[0], cpy);
 167                         subst(&i->arg[1], cpy);
 168                 }
 169                 subst(&b->jmp.arg, cpy);
 170         }
 171
 172         if (debug['C']) {
 173                 fprintf(stderr, "\n> Copy information:");
 174                 for (t=Tmp0; t<fn->ntmp; t++) {
 175                         if (req(cpy[t], R)) {
 176                                 fprintf(stderr, "\n%10s not seen!",
 177                                         fn->tmp[t].name);
 178                         }
 179                         else if (!req(cpy[t], TMP(t))) {
 180                                 fprintf(stderr, "\n%10s copy of ",
 181                                         fn->tmp[t].name);
 182                                 printref(cpy[t], fn, stderr);
 183                         }
 184                 }
 185                 fprintf(stderr, "\n\n> After copy elimination:\n");
 186                 printfn(fn, stderr);
 187         }
 188         vfree(stk);
 189         free(cpy);
 190 }