copy.c (4509B)
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 }