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