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