copy.c

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