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