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