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 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         *delta = ap.offset - aq.offset;
  39         ovlap = ap.offset < aq.offset + sq && aq.offset < ap.offset + sp;
  40
  41         if (astack(ap.type) && astack(aq.type)) {
  42                 /* if both are offsets of the same
  43                  * stack slot, they alias iif they
  44                  * overlap */
  45                 if (ap.base == aq.base && ovlap)
  46                         return MustAlias;
  47                 return NoAlias;
  48         }
  49
  50         if (ap.type == ASym && aq.type == ASym) {
  51                 /* they conservatively alias if the
  52                  * symbols are different, or they
  53                  * alias for sure if they overlap */
  54                 if (!symeq(ap.u.sym, aq.u.sym))
  55                         return MayAlias;
  56                 if (ovlap)
  57                         return MustAlias;
  58                 return NoAlias;
  59         }
  60
  61         if ((ap.type == ACon && aq.type == ACon)
  62         || (ap.type == aq.type && ap.base == aq.base)) {
  63                 assert(ap.type == ACon || ap.type == AUnk);
  64                 /* if they have the same base, we
  65                  * can rely on the offsets only */
  66                 if (ovlap)
  67                         return MustAlias;
  68                 return NoAlias;
  69         }
  70
  71         /* if one of the two is unknown
  72          * there may be aliasing unless
  73          * the other is provably local */
  74         if (ap.type == AUnk && aq.type != ALoc)
  75                 return MayAlias;
  76         if (aq.type == AUnk && ap.type != ALoc)
  77                 return MayAlias;
  78
  79         return NoAlias;
  80 }
  81
  82 int
  83 escapes(Ref r, Fn *fn)
  84 {
  85         Alias *a;
  86
  87         if (rtype(r) != RTmp)
  88                 return 1;
  89         a = &fn->tmp[r.val].alias;
  90         return !astack(a->type) || a->slot->type == AEsc;
  91 }
  92
  93 static void
  94 esc(Ref r, Fn *fn)
  95 {
  96         Alias *a;
  97
  98         assert(rtype(r) <= RType);
  99         if (rtype(r) == RTmp) {
 100                 a = &fn->tmp[r.val].alias;
 101                 if (astack(a->type))
 102                         a->slot->type = AEsc;
 103         }
 104 }
 105
 106 void
 107 fillalias(Fn *fn)
 108 {
 109         uint n, m;
 110         int t;
 111         int64_t x;
 112         bits w;
 113         Blk *b;
 114         Phi *p;
 115         Ins *i;
 116         Con *c;
 117         Alias *a, a0, a1;
 118
 119         for (t=0; t<fn->ntmp; t++)
 120                 fn->tmp[t].alias.type = ABot;
 121         for (n=0; n<fn->nblk; ++n) {
 122                 b = fn->rpo[n];
 123                 for (p=b->phi; p; p=p->link) {
 124                         for (m=0; m<p->narg; m++)
 125                                 esc(p->arg[m], fn);
 126                         assert(rtype(p->to) == RTmp);
 127                         a = &fn->tmp[p->to.val].alias;
 128                         assert(a->type == ABot);
 129                         a->type = AUnk;
 130                         a->base = p->to.val;
 131                         a->offset = 0;
 132                         a->slot = 0;
 133                 }
 134                 for (i=b->ins; i<&b->ins[b->nins]; ++i) {
 135                         a = 0;
 136                         if (!req(i->to, R)) {
 137                                 assert(rtype(i->to) == RTmp);
 138                                 a = &fn->tmp[i->to.val].alias;
 139                                 assert(a->type == ABot);
 140                                 if (Oalloc <= i->op && i->op <= Oalloc1) {
 141                                         a->type = ALoc;
 142                                         a->slot = a;
 143                                         a->u.loc.sz = -1;
 144                                         if (rtype(i->arg[0]) == RCon) {
 145                                                 c = &fn->con[i->arg[0].val];
 146                                                 x = c->bits.i;
 147                                                 if (c->type == CBits)
 148                                                 if (0 <= x && x <= NBit)
 149                                                         a->u.loc.sz = x;
 150                                         }
 151                                 } else {
 152                                         a->type = AUnk;
 153                                         a->slot = 0;
 154                                 }
 155                                 a->base = i->to.val;
 156                                 a->offset = 0;
 157                         }
 158                         if (i->op == Ocopy) {
 159                                 assert(a);
 160                                 getalias(a, i->arg[0], fn);
 161                         }
 162                         if (i->op == Oadd) {
 163                                 getalias(&a0, i->arg[0], fn);
 164                                 getalias(&a1, i->arg[1], fn);
 165                                 if (a0.type == ACon) {
 166                                         *a = a1;
 167                                         a->offset += a0.offset;
 168                                 }
 169                                 else if (a1.type == ACon) {
 170                                         *a = a0;
 171                                         a->offset += a1.offset;
 172                                 }
 173                         }
 174                         if (req(i->to, R) || a->type == AUnk) {
 175                                 if (!isload(i->op))
 176                                         esc(i->arg[0], fn);
 177                                 if (!isstore(i->op))
 178                                 if (i->op != Oargc)
 179                                         esc(i->arg[1], fn);
 180                         }
 181                         if (isstore(i->op))
 182                         if (rtype(i->arg[1]) == RTmp) {
 183                                 a = &fn->tmp[i->arg[1].val].alias;
 184                                 if (a->slot) {
 185                                         assert(astack(a->type));
 186                                         x = a->offset;
 187                                         if (0 <= x && x < NBit) {
 188                                                 w = BIT(storesz(i)) - 1;
 189                                                 a->slot->u.loc.m |= w << x;
 190                                         } else
 191                                                 a->slot->u.loc.sz = -1;
 192                                 }
 193                         }
 194                 }
 195                 esc(b->jmp.arg, fn);
 196         }
 197 }