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