copy.c

   1 #include "all.h"
   2
   3 typedef struct RList RList;
   4 struct RList {
   5         int t;
   6         RList *l;
   7 };
   8
   9 static Ref
  10 copyof(Ref r, Ref *cp)
  11 {
  12         if (rtype(r) == RTmp)
  13                 return cp[r.val];
  14         else
  15                 return r;
  16 }
  17
  18 static void
  19 update(Ref r, Ref rcp, Ref *cp, RList ***pw)
  20 {
  21         RList *l;
  22
  23         if (!req(cp[r.val], rcp)) {
  24                 cp[r.val] = rcp;
  25                 l = emalloc(sizeof *l);
  26                 l->t = r.val;
  27                 l->l = 0;
  28                 **pw = l;
  29                 *pw = &l->l;
  30         }
  31 }
  32
  33 static void
  34 visitphi(Phi *p, Ref *cp, RList ***pw)
  35 {
  36         uint a;
  37         Ref r, r1;
  38
  39         r = R;
  40         for (a=0; a<p->narg; a++) {
  41                 r1 = copyof(p->arg[a], cp);
  42                 if (req(r1, R) || req(r1, p->to))
  43                         continue;
  44                 if (req(r, R) || req(r, r1))
  45                         r = r1;
  46                 else {
  47                         r = p->to;
  48                         break;
  49                 }
  50         }
  51         update(p->to, r, cp, pw);
  52 }
  53
  54 static int
  55 iscopy(Ins *i, Ref r, Fn *fn)
  56 {
  57         static bits extcpy[] = {
  58                 [WFull] = 0,
  59                 [Wsb] = BIT(Wsb) | BIT(Wsh) | BIT(Wsw),
  60                 [Wub] = BIT(Wub) | BIT(Wuh) | BIT(Wuw),
  61                 [Wsh] = BIT(Wsh) | BIT(Wsw),
  62                 [Wuh] = BIT(Wuh) | BIT(Wuw),
  63                 [Wsw] = BIT(Wsw),
  64                 [Wuw] = BIT(Wuw),
  65         };
  66         bits b;
  67         Tmp *t;
  68
  69         if (i->op == Ocopy)
  70                 return 1;
  71         if (!isext(i->op) || rtype(r) != RTmp)
  72                 return 0;
  73         if (i->op == Oextsw || i->op == Oextuw)
  74         if (i->cls == Kw)
  75                 return 1;
  76
  77         t = &fn->tmp[r.val];
  78         assert(KBASE(t->cls) == 0);
  79         if (i->cls == Kl && t->cls == Kw)
  80                 return 0;
  81         b = extcpy[t->width];
  82         return (BIT(Wsb + (i->op-Oextsb)) & b) != 0;
  83 }
  84
  85 static void
  86 visitins(Ins *i, Ref *cp, RList ***pw, Fn *fn)
  87 {
  88         Ref r;
  89
  90         r = copyof(i->arg[0], cp);
  91         if (iscopy(i, r, fn)) {
  92                 update(i->to, r, cp, pw);
  93         } else if (!req(i->to, R)) {
  94                 assert(rtype(i->to) == RTmp);
  95                 update(i->to, i->to, cp, pw);
  96         }
  97 }
  98
  99 static void
 100 subst(Ref *r, Ref *cp)
 101 {
 102         assert((rtype(*r) != RTmp || !req(copyof(*r, cp), R)) && "ssa invariant broken");
 103         *r = copyof(*r, cp);
 104 }
 105
 106 void
 107 copy(Fn *fn)
 108 {
 109         Blk *b;
 110         Ref *cp, r;
 111         RList *w, *w1, **pw;
 112         Use *u, *u1;
 113         Ins *i;
 114         Phi *p, **pp;
 115         uint a;
 116         int t;
 117
 118         w = 0;
 119         pw = &w;
 120         cp = emalloc(fn->ntmp * sizeof cp[0]);
 121         for (b=fn->start; b; b=b->link) {
 122                 for (p=b->phi; p; p=p->link)
 123                         visitphi(p, cp, &pw);
 124                 for (i=b->ins; i-b->ins < b->nins; i++)
 125                         visitins(i, cp, &pw, fn);
 126         }
 127         while ((w1=w)) {
 128                 t = w->t;
 129                 u = fn->tmp[t].use;
 130                 u1 = u + fn->tmp[t].nuse;
 131                 for (; u<u1; u++)
 132                         switch (u->type) {
 133                         case UPhi:
 134                                 visitphi(u->u.phi, cp, &pw);
 135                                 break;
 136                         case UIns:
 137                                 visitins(u->u.ins, cp, &pw, fn);
 138                                 break;
 139                         case UJmp:
 140                                 break;
 141                         default:
 142                                 die("invalid use %d", u->type);
 143                         }
 144                 w = w->l;
 145                 free(w1);
 146         }
 147         for (b=fn->start; b; b=b->link) {
 148                 for (pp=&b->phi; (p=*pp);) {
 149                         r = cp[p->to.val];
 150                         if (!req(r, p->to)) {
 151                                 *pp = p->link;
 152                                 continue;
 153                         }
 154                         for (a=0; a<p->narg; a++)
 155                                 subst(&p->arg[a], cp);
 156                         pp=&p->link;
 157                 }
 158                 for (i=b->ins; i-b->ins < b->nins; i++) {
 159                         r = copyof(i->to, cp);
 160                         if (!req(r, i->to)) {
 161                                 *i = (Ins){.op = Onop};
 162                                 continue;
 163                         }
 164                         for (a=0; a<2; a++)
 165                                 subst(&i->arg[a], cp);
 166                 }
 167                 subst(&b->jmp.arg, cp);
 168         }
 169         if (debug['C']) {
 170                 fprintf(stderr, "\n> Copy information:");
 171                 for (t=Tmp0; t<fn->ntmp; t++) {
 172                         if (req(cp[t], R)) {
 173                                 fprintf(stderr, "\n%10s not seen!",
 174                                         fn->tmp[t].name);
 175                         }
 176                         else if (!req(cp[t], TMP(t))) {
 177                                 fprintf(stderr, "\n%10s copy of ",
 178                                         fn->tmp[t].name);
 179                                 printref(cp[t], fn, stderr);
 180                         }
 181                 }
 182                 fprintf(stderr, "\n\n> After copy elimination:\n");
 183                 printfn(fn, stderr);
 184         }
 185         free(cp);
 186 }