alias.c (4355B)
1 #include "all.h" 2 3 void 4 getalias(Alias *a, Ref r, Fn *fn) 5 { 6 Con *c; 7 8 switch (rtype(r)) { 9 default: 10 die("unreachable"); 11 case RTmp: 12 *a = fn->tmp[r.val].alias; 13 if (astack(a->type)) 14 a->type = a->slot->type; 15 assert(a->type != ABot); 16 break; 17 case RCon: 18 c = &fn->con[r.val]; 19 if (c->type == CAddr) { 20 a->type = ASym; 21 a->u.sym = c->sym; 22 } else 23 a->type = ACon; 24 a->offset = c->bits.i; 25 a->slot = 0; 26 break; 27 } 28 } 29 30 int 31 alias(Ref p, int op, int sp, Ref q, int sq, int *delta, Fn *fn) 32 { 33 Alias ap, aq; 34 int ovlap; 35 36 getalias(&ap, p, fn); 37 getalias(&aq, q, fn); 38 ap.offset += op; 39 /* when delta is meaningful (ovlap == 1), 40 * we do not overflow int because sp and 41 * sq are bounded by 2^28 */ 42 *delta = ap.offset - aq.offset; 43 ovlap = ap.offset < aq.offset + sq && aq.offset < ap.offset + sp; 44 45 if (astack(ap.type) && astack(aq.type)) { 46 /* if both are offsets of the same 47 * stack slot, they alias iif they 48 * overlap */ 49 if (ap.base == aq.base && ovlap) 50 return MustAlias; 51 return NoAlias; 52 } 53 54 if (ap.type == ASym && aq.type == ASym) { 55 /* they conservatively alias if the 56 * symbols are different, or they 57 * alias for sure if they overlap */ 58 if (!symeq(ap.u.sym, aq.u.sym)) 59 return MayAlias; 60 if (ovlap) 61 return MustAlias; 62 return NoAlias; 63 } 64 65 if ((ap.type == ACon && aq.type == ACon) 66 || (ap.type == aq.type && ap.base == aq.base)) { 67 assert(ap.type == ACon || ap.type == AUnk); 68 /* if they have the same base, we 69 * can rely on the offsets only */ 70 if (ovlap) 71 return MustAlias; 72 return NoAlias; 73 } 74 75 /* if one of the two is unknown 76 * there may be aliasing unless 77 * the other is provably local */ 78 if (ap.type == AUnk && aq.type != ALoc) 79 return MayAlias; 80 if (aq.type == AUnk && ap.type != ALoc) 81 return MayAlias; 82 83 return NoAlias; 84 } 85 86 int 87 escapes(Ref r, Fn *fn) 88 { 89 Alias *a; 90 91 if (rtype(r) != RTmp) 92 return 1; 93 a = &fn->tmp[r.val].alias; 94 return !astack(a->type) || a->slot->type == AEsc; 95 } 96 97 static void 98 esc(Ref r, Fn *fn) 99 { 100 Alias *a; 101 102 assert(rtype(r) <= RType); 103 if (rtype(r) == RTmp) { 104 a = &fn->tmp[r.val].alias; 105 if (astack(a->type)) 106 a->slot->type = AEsc; 107 } 108 } 109 110 static void 111 store(Ref r, int sz, Fn *fn) 112 { 113 Alias *a; 114 int64_t off; 115 bits m; 116 117 if (rtype(r) == RTmp) { 118 a = &fn->tmp[r.val].alias; 119 if (a->slot) { 120 assert(astack(a->type)); 121 off = a->offset; 122 if (sz >= NBit 123 || (off < 0 || off >= NBit)) 124 m = -1; 125 else 126 m = (BIT(sz) - 1) << off; 127 a->slot->u.loc.m |= m; 128 } 129 } 130 } 131 132 void 133 fillalias(Fn *fn) 134 { 135 uint n, m; 136 int t, sz; 137 int64_t x; 138 Blk *b; 139 Phi *p; 140 Ins *i; 141 Con *c; 142 Alias *a, a0, a1; 143 144 for (t=0; t<fn->ntmp; t++) 145 fn->tmp[t].alias.type = ABot; 146 for (n=0; n<fn->nblk; ++n) { 147 b = fn->rpo[n]; 148 for (p=b->phi; p; p=p->link) { 149 for (m=0; m<p->narg; m++) 150 esc(p->arg[m], fn); 151 assert(rtype(p->to) == RTmp); 152 a = &fn->tmp[p->to.val].alias; 153 assert(a->type == ABot); 154 a->type = AUnk; 155 a->base = p->to.val; 156 a->offset = 0; 157 a->slot = 0; 158 } 159 for (i=b->ins; i<&b->ins[b->nins]; ++i) { 160 a = 0; 161 if (!req(i->to, R)) { 162 assert(rtype(i->to) == RTmp); 163 a = &fn->tmp[i->to.val].alias; 164 assert(a->type == ABot); 165 if (Oalloc <= i->op && i->op <= Oalloc1) { 166 a->type = ALoc; 167 a->slot = a; 168 a->u.loc.sz = -1; 169 if (rtype(i->arg[0]) == RCon) { 170 c = &fn->con[i->arg[0].val]; 171 x = c->bits.i; 172 if (c->type == CBits) 173 if (0 <= x && x <= NBit) 174 a->u.loc.sz = x; 175 } 176 } else { 177 a->type = AUnk; 178 a->slot = 0; 179 } 180 a->base = i->to.val; 181 a->offset = 0; 182 } 183 if (i->op == Ocopy) { 184 assert(a); 185 getalias(a, i->arg[0], fn); 186 } 187 if (i->op == Oadd) { 188 getalias(&a0, i->arg[0], fn); 189 getalias(&a1, i->arg[1], fn); 190 if (a0.type == ACon) { 191 *a = a1; 192 a->offset += a0.offset; 193 } 194 else if (a1.type == ACon) { 195 *a = a0; 196 a->offset += a1.offset; 197 } 198 } 199 if (req(i->to, R) || a->type == AUnk) 200 if (i->op != Oblit0) { 201 if (!isload(i->op)) 202 esc(i->arg[0], fn); 203 if (!isstore(i->op)) 204 if (i->op != Oargc) 205 esc(i->arg[1], fn); 206 } 207 if (i->op == Oblit0) { 208 ++i; 209 assert(i->op == Oblit1); 210 assert(rtype(i->arg[0]) == RInt); 211 sz = abs(rsval(i->arg[0])); 212 store((i-1)->arg[1], sz, fn); 213 } 214 if (isstore(i->op)) 215 store(i->arg[1], storesz(i), fn); 216 } 217 if (b->jmp.type != Jretc) 218 esc(b->jmp.arg, fn); 219 } 220 }