alias.c

   1 #include "all.h"
   2
   3 static 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->label = c->label;
  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 (req(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 (ap.label != aq.label)
  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 && req(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         Blk *b;
 111         Phi *p;
 112         Ins *i;
 113         Alias *a, a0, a1;
 114
 115         for (n=0; n<fn->nblk; ++n) {
 116                 b = fn->rpo[n];
 117                 for (p=b->phi; p; p=p->link) {
 118                         for (m=0; m<p->narg; m++)
 119                                 esc(p->arg[m], fn);
 120                         assert(rtype(p->to) == RTmp);
 121                         a = &fn->tmp[p->to.val].alias;
 122                         assert(a->type == ABot);
 123                         a->type = AUnk;
 124                         a->base = p->to;
 125                         a->offset = 0;
 126                         a->slot = 0;
 127                 }
 128                 for (i=b->ins; i<&b->ins[b->nins]; ++i) {
 129                         a = 0;
 130                         if (!req(i->to, R)) {
 131                                 assert(rtype(i->to) == RTmp);
 132                                 a = &fn->tmp[i->to.val].alias;
 133                                 assert(a->type == ABot);
 134                                 if (Oalloc <= i->op && i->op <= Oalloc1) {
 135                                         a->type = ALoc;
 136                                         a->slot = a;
 137                                 } else {
 138                                         a->type = AUnk;
 139                                         a->slot = 0;
 140                                 }
 141                                 a->base = i->to;
 142                                 a->offset = 0;
 143                         }
 144                         if (i->op == Ocopy) {
 145                                 assert(a);
 146                                 getalias(a, i->arg[0], fn);
 147                         }
 148                         if (i->op == Oadd) {
 149                                 getalias(&a0, i->arg[0], fn);
 150                                 getalias(&a1, i->arg[1], fn);
 151                                 if (a0.type == ACon) {
 152                                         *a = a1;
 153                                         a->offset += a0.offset;
 154                                 }
 155                                 else if (a1.type == ACon) {
 156                                         *a = a0;
 157                                         a->offset += a1.offset;
 158                                 }
 159                         }
 160                         if (req(i->to, R) || a->type == AUnk) {
 161                                 if (!isload(i->op))
 162                                         esc(i->arg[0], fn);
 163                                 if (!isstore(i->op))
 164                                         esc(i->arg[1], fn);
 165                         }
 166                 }
 167                 esc(b->jmp.arg, fn);
 168         }
 169 }