QBE
cfg.c
См. документацию.
1 #include "all.h"
2 
3 Blk *
5 {
6  static Blk z;
7  Blk *b;
8 
9  b = alloc(sizeof *b);
10  *b = z;
11  return b;
12 }
13 
14 void
15 edgedel(Blk *bs, Blk **pbd)
16 {
17  Blk *bd;
18  Phi *p;
19  uint a;
20  int mult;
21 
22  bd = *pbd;
23  mult = 1 + (bs->s1 == bs->s2);
24  *pbd = 0;
25  if (!bd || mult > 1)
26  return;
27  for (p=bd->phi; p; p=p->link) {
28  for (a=0; p->blk[a]!=bs; a++)
29  assert(a+1<p->narg);
30  p->narg--;
31  memmove(&p->blk[a], &p->blk[a+1],
32  sizeof p->blk[0] * (p->narg-a));
33  memmove(&p->arg[a], &p->arg[a+1],
34  sizeof p->arg[0] * (p->narg-a));
35  }
36  if (bd->npred != 0) {
37  for (a=0; bd->pred[a]!=bs; a++)
38  assert(a+1<bd->npred);
39  bd->npred--;
40  memmove(&bd->pred[a], &bd->pred[a+1],
41  sizeof bd->pred[0] * (bd->npred-a));
42  }
43 }
44 
45 static void
46 addpred(Blk *bp, Blk *bc)
47 {
48  if (!bc->pred) {
49  bc->pred = alloc(bc->npred * sizeof bc->pred[0]);
50  bc->visit = 0;
51  }
52  bc->pred[bc->visit++] = bp;
53 }
54 
55 /* fill predecessors information in blocks */
56 void
58 {
59  Blk *b;
60 
61  for (b=f->start; b; b=b->link) {
62  b->npred = 0;
63  b->pred = 0;
64  }
65  for (b=f->start; b; b=b->link) {
66  if (b->s1)
67  b->s1->npred++;
68  if (b->s2 && b->s2 != b->s1)
69  b->s2->npred++;
70  }
71  for (b=f->start; b; b=b->link) {
72  if (b->s1)
73  addpred(b, b->s1);
74  if (b->s2 && b->s2 != b->s1)
75  addpred(b, b->s2);
76  }
77 }
78 
79 static int
80 rporec(Blk *b, uint x)
81 {
82  Blk *s1, *s2;
83 
84  if (!b || b->id != -1u)
85  return x;
86  b->id = 1;
87  s1 = b->s1;
88  s2 = b->s2;
89  if (s1 && s2 && s1->loop > s2->loop) {
90  s1 = b->s2;
91  s2 = b->s1;
92  }
93  x = rporec(s1, x);
94  x = rporec(s2, x);
95  b->id = x;
96  assert(x != -1u);
97  return x - 1;
98 }
99 
100 /* fill the rpo information */
101 void
103 {
104  uint n;
105  Blk *b, **p;
106 
107  for (b=f->start; b; b=b->link)
108  b->id = -1u;
109  n = 1 + rporec(f->start, f->nblk-1);
110  f->nblk -= n;
111  f->rpo = alloc(f->nblk * sizeof f->rpo[0]);
112  for (p=&f->start; (b=*p);) {
113  if (b->id == -1u) {
114  edgedel(b, &b->s1);
115  edgedel(b, &b->s2);
116  *p = b->link;
117  } else {
118  b->id -= n;
119  f->rpo[b->id] = b;
120  p = &b->link;
121  }
122  }
123 }
124 
125 /* for dominators computation, read
126  * "A Simple, Fast Dominance Algorithm"
127  * by K. Cooper, T. Harvey, and K. Kennedy.
128  */
129 
130 static Blk *
131 inter(Blk *b1, Blk *b2)
132 {
133  Blk *bt;
134 
135  if (b1 == 0)
136  return b2;
137  while (b1 != b2) {
138  if (b1->id < b2->id) {
139  bt = b1;
140  b1 = b2;
141  b2 = bt;
142  }
143  while (b1->id > b2->id) {
144  b1 = b1->idom;
145  assert(b1);
146  }
147  }
148  return b1;
149 }
150 
151 void
153 {
154  Blk *b, *d;
155  int ch;
156  uint n, p;
157 
158  for (b=fn->start; b; b=b->link) {
159  b->idom = 0;
160  b->dom = 0;
161  b->dlink = 0;
162  }
163  do {
164  ch = 0;
165  for (n=1; n<fn->nblk; n++) {
166  b = fn->rpo[n];
167  d = 0;
168  for (p=0; p<b->npred; p++)
169  if (b->pred[p]->idom
170  || b->pred[p] == fn->start)
171  d = inter(d, b->pred[p]);
172  if (d != b->idom) {
173  ch++;
174  b->idom = d;
175  }
176  }
177  } while (ch);
178  for (b=fn->start; b; b=b->link)
179  if ((d=b->idom)) {
180  assert(d != b);
181  b->dlink = d->dom;
182  d->dom = b;
183  }
184 }
185 
186 int
187 sdom(Blk *b1, Blk *b2)
188 {
189  assert(b1 && b2);
190  if (b1 == b2)
191  return 0;
192  while (b2->id > b1->id)
193  b2 = b2->idom;
194  return b1 == b2;
195 }
196 
197 int
198 dom(Blk *b1, Blk *b2)
199 {
200  return b1 == b2 || sdom(b1, b2);
201 }
202 
203 static void
204 addfron(Blk *a, Blk *b)
205 {
206  uint n;
207 
208  for (n=0; n<a->nfron; n++)
209  if (a->fron[n] == b)
210  return;
211  if (!a->nfron)
212  a->fron = vnew(++a->nfron, sizeof a->fron[0], Pfn);
213  else
214  vgrow(&a->fron, ++a->nfron);
215  a->fron[a->nfron-1] = b;
216 }
217 
218 /* fill the dominance frontier */
219 void
221 {
222  Blk *a, *b;
223 
224  for (b=fn->start; b; b=b->link)
225  b->nfron = 0;
226  for (b=fn->start; b; b=b->link) {
227  if (b->s1)
228  for (a=b; !sdom(a, b->s1); a=a->idom)
229  addfron(a, b->s1);
230  if (b->s2)
231  for (a=b; !sdom(a, b->s2); a=a->idom)
232  addfron(a, b->s2);
233  }
234 }
235 
236 static void
237 loopmark(Blk *hd, Blk *b, void f(Blk *, Blk *))
238 {
239  uint p;
240 
241  if (b->id < hd->id || b->visit == hd->id)
242  return;
243  b->visit = hd->id;
244  f(hd, b);
245  for (p=0; p<b->npred; ++p)
246  loopmark(hd, b->pred[p], f);
247 }
248 
249 void
250 loopiter(Fn *fn, void f(Blk *, Blk *))
251 {
252  uint n, p;
253  Blk *b;
254 
255  for (b=fn->start; b; b=b->link)
256  b->visit = -1u;
257  for (n=0; n<fn->nblk; ++n) {
258  b = fn->rpo[n];
259  for (p=0; p<b->npred; ++p)
260  if (b->pred[p]->id >= n)
261  loopmark(b, b->pred[p], f);
262  }
263 }
264 
265 void
266 multloop(Blk *hd, Blk *b)
267 {
268  (void)hd;
269  b->loop *= 10;
270 }
271 
272 void
274 {
275  Blk *b;
276 
277  for (b=fn->start; b; b=b->link)
278  b->loop = 1;
279  loopiter(fn, multloop);
280 }
281 
282 static void
283 uffind(Blk **pb, Blk **uf)
284 {
285  Blk **pb1;
286 
287  pb1 = &uf[(*pb)->id];
288  if (*pb1) {
289  uffind(pb1, uf);
290  *pb = *pb1;
291  }
292 }
293 
294 /* requires rpo and no phis, breaks cfg */
295 void
297 {
298 
299  Blk **uf; /* union-find */
300  Blk *b;
301  int c;
302 
303  uf = emalloc(fn->nblk * sizeof uf[0]);
304  for (b=fn->start; b; b=b->link) {
305  assert(!b->phi);
306  if (b->nins == 0)
307  if (b->jmp.type == Jjmp) {
308  uffind(&b->s1, uf);
309  if (b->s1 != b)
310  uf[b->id] = b->s1;
311  }
312  }
313  for (b=fn->start; b; b=b->link) {
314  if (b->s1)
315  uffind(&b->s1, uf);
316  if (b->s2)
317  uffind(&b->s2, uf);
318  c = b->jmp.type - Jjf;
319  if (0 <= c && c <= NCmp)
320  if (b->s1 == b->s2) {
321  b->jmp.type = Jjmp;
322  b->s2 = 0;
323  }
324  }
325  free(uf);
326 }
unsigned int uint
Definition: all.h:12
Blk * start
Указатель на блок функции, являющийся её входной точкой
Definition: all.h:385
Blk ** pred
Definition: all.h:274
void * emalloc(size_t)
Definition: util.c:66
uint narg
Definition: all.h:246
void multloop(Blk *hd, Blk *b)
Definition: cfg.c:266
void fillpreds(Fn *f)
Definition: cfg.c:57
Blk * dlink
Definition: all.h:270
void loopiter(Fn *fn, void f(Blk *, Blk *))
Definition: cfg.c:250
void fillrpo(Fn *f)
Definition: cfg.c:102
void * vnew(ulong, size_t, Pool)
Definition: util.c:111
Blk * blknew()
Definition: cfg.c:4
Phi * link
Definition: all.h:248
Blk * s1
Definition: all.h:262
Definition: all.h:154
Ref arg[NPred]
Definition: all.h:244
void fillfron(Fn *fn)
Definition: cfg.c:220
int dom(Blk *b1, Blk *b2)
Definition: cfg.c:198
Definition: all.h:181
Blk * s2
Definition: all.h:263
Непосредственно информация о базовом блоке.
Definition: all.h:254
void * alloc(size_t)
Definition: util.c:77
Blk * idom
Definition: all.h:269
Blk * link
Definition: all.h:264
uint nins
Definition: all.h:257
Definition: all.h:460
uint visit
Definition: all.h:267
int loop
Definition: all.h:278
void vgrow(void *, ulong)
Definition: util.c:142
uint nblk
Количество блоков в функции
Definition: all.h:392
void fillloop(Fn *fn)
Definition: cfg.c:273
uint npred
Definition: all.h:275
short type
Definition: all.h:259
Phi * phi
Definition: all.h:255
Blk ** rpo
Ссылка на массив блоков, пронумерованных в порядке Reverse-Post Order, заполняется функцией fillrpo...
Definition: all.h:395
void edgedel(Blk *bs, Blk **pbd)
Definition: cfg.c:15
Blk * dom
Definition: all.h:270
int sdom(Blk *b1, Blk *b2)
Definition: cfg.c:187
Definition: all.h:200
uint id
Definition: all.h:266
uint nfron
Definition: all.h:272
void simpljmp(Fn *fn)
Definition: cfg.c:296
Blk * blk[NPred]
Definition: all.h:245
struct Blk::@5 jmp
Структура, хранящая в себе информацию о функции
Definition: all.h:384
void filldom(Fn *fn)
Definition: cfg.c:152
Definition: all.h:242
Blk ** fron
Definition: all.h:271