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