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