alias.c

   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;
 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                         assert(rtype(p->to) == RTmp);
 150                         a = &fn->tmp[p->to.val].alias;
 151                         assert(a->type == ABot);
 152                         a->type = AUnk;
 153                         a->base = p->to.val;
 154                         a->offset = 0;
 155                         a->slot = 0;
 156                 }
 157                 for (i=b->ins; i<&b->ins[b->nins]; ++i) {
 158                         a = 0;
 159                         if (!req(i->to, R)) {
 160                                 assert(rtype(i->to) == RTmp);
 161                                 a = &fn->tmp[i->to.val].alias;
 162                                 assert(a->type == ABot);
 163                                 if (Oalloc <= i->op && i->op <= Oalloc1) {
 164                                         a->type = ALoc;
 165                                         a->slot = a;
 166                                         a->u.loc.sz = -1;
 167                                         if (rtype(i->arg[0]) == RCon) {
 168                                                 c = &fn->con[i->arg[0].val];
 169                                                 x = c->bits.i;
 170                                                 if (c->type == CBits)
 171                                                 if (0 <= x && x <= NBit)
 172                                                         a->u.loc.sz = x;
 173                                         }
 174                                 } else {
 175                                         a->type = AUnk;
 176                                         a->slot = 0;
 177                                 }
 178                                 a->base = i->to.val;
 179                                 a->offset = 0;
 180                         }
 181                         if (i->op == Ocopy) {
 182                                 assert(a);
 183                                 getalias(a, i->arg[0], fn);
 184                         }
 185                         if (i->op == Oadd) {
 186                                 getalias(&a0, i->arg[0], fn);
 187                                 getalias(&a1, i->arg[1], fn);
 188                                 if (a0.type == ACon) {
 189                                         *a = a1;
 190                                         a->offset += a0.offset;
 191                                 }
 192                                 else if (a1.type == ACon) {
 193                                         *a = a0;
 194                                         a->offset += a1.offset;
 195                                 }
 196                         }
 197                         if (req(i->to, R) || a->type == AUnk)
 198                         if (i->op != Oblit0) {
 199                                 if (!isload(i->op))
 200                                         esc(i->arg[0], fn);
 201                                 if (!isstore(i->op))
 202                                 if (i->op != Oargc)
 203                                         esc(i->arg[1], fn);
 204                         }
 205                         if (i->op == Oblit0) {
 206                                 ++i;
 207                                 assert(i->op == Oblit1);
 208                                 assert(rtype(i->arg[0]) == RInt);
 209                                 sz = abs(rsval(i->arg[0]));
 210                                 store((i-1)->arg[1], sz, fn);
 211                         }
 212                         if (isstore(i->op))
 213                                 store(i->arg[1], storesz(i), fn);
 214                 }
 215                 if (b->jmp.type != Jretc)
 216                         esc(b->jmp.arg, fn);
 217         }
 218         for (b=fn->start; b; b=b->link)
 219                 for (p=b->phi; p; p=p->link)
 220                         for (n=0; n<p->narg; n++)
 221                                 esc(p->arg[n], fn);
 222 }