QBE
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
108 {
109  uint n;
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  assert(rtype(p->to) == RTmp);
119  a = &fn->tmp[p->to.val].alias;
120  assert(a->type == ABot);
121  a->type = AUnk;
122  a->base = p->to;
123  a->offset = 0;
124  a->slot = 0;
125  }
126  for (i=b->ins; i<&b->ins[b->nins]; ++i) {
127  a = 0;
128  if (!req(i->to, R)) {
129  assert(rtype(i->to) == RTmp);
130  a = &fn->tmp[i->to.val].alias;
131  assert(a->type == ABot);
132  if (Oalloc <= i->op && i->op <= Oalloc1) {
133  a->type = ALoc;
134  a->slot = a;
135  } else {
136  a->type = AUnk;
137  a->slot = 0;
138  }
139  a->base = i->to;
140  a->offset = 0;
141  }
142  if (i->op == Ocopy) {
143  assert(a);
144  getalias(a, i->arg[0], fn);
145  }
146  if (i->op == Oadd) {
147  getalias(&a0, i->arg[0], fn);
148  getalias(&a1, i->arg[1], fn);
149  if (a0.type == ACon) {
150  *a = a1;
151  a->offset += a0.offset;
152  }
153  else if (a1.type == ACon) {
154  *a = a0;
155  a->offset += a1.offset;
156  }
157  }
158  if (req(i->to, R) || a->type == AUnk) {
159  if (!isload(i->op))
160  esc(i->arg[0], fn);
161  if (!isstore(i->op))
162  esc(i->arg[1], fn);
163  }
164  }
165  esc(b->jmp.arg, fn);
166  }
167 }
Ref base
Definition: all.h:316
enum Alias::@8 type
unsigned int uint
Definition: all.h:12
int escapes(Ref r, Fn *fn)
Definition: alias.c:83
Структура, хранящая информацию об инструкциях.
Definition: all.h:235
Definition: all.h:275
#define isstore(o)
Definition: all.h:204
Definition: all.h:84
Phi * link
Definition: all.h:248
Definition: all.h:196
void fillalias(Fn *fn)
Definition: alias.c:107
Con * con
Массив используемых функцией констант
Definition: all.h:387
Структура, хранящая описание переменных (более подробное описание переменной ищите в Tmp)...
Definition: all.h:77
Tmp * tmp
Массив используемых функцией переменных
Definition: all.h:386
uint32_t label
Definition: all.h:317
Definition: all.h:303
Ref arg
Definition: all.h:260
Alias * slot
Definition: all.h:319
Alias alias
Definition: all.h:340
Ref to
Definition: all.h:243
Непосредственно информация о базовом блоке.
Definition: all.h:254
enum Con::@11 type
uint nins
Definition: all.h:257
int64_t offset
Definition: all.h:318
Ref to
Definition: all.h:237
Definition: all.h:86
Definition: all.h:353
uint nblk
Количество блоков в функции
Definition: all.h:392
int64_t i
Definition: all.h:361
#define isload(o)
Definition: all.h:205
Ins * ins
Definition: all.h:256
Phi * phi
Definition: all.h:255
Blk ** rpo
Ссылка на массив блоков, пронумерованных в порядке Reverse-Post Order, заполняется функцией fillrpo...
Definition: all.h:395
Ref arg[2]
Definition: all.h:238
#define die(...)
Definition: all.h:9
uint val
Definition: all.h:80
Definition: all.h:179
Definition: all.h:301
Definition: all.h:306
Definition: all.h:85
int alias(Ref p, int sp, Ref q, int sq, int *delta, Fn *fn)
Definition: alias.c:31
#define astack(t)
Definition: all.h:314
Definition: all.h:302
#define R
Definition: all.h:92
union Con::@12 bits
struct Blk::@5 jmp
uint32_t label
Definition: all.h:359
Структура, хранящая в себе информацию о функции
Definition: all.h:384
uint op
Definition: all.h:236
Definition: all.h:242