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, 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 }