1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
#include "ir.h"
static void
porec(struct block ***rpo, struct block *b)
{
if (wasvisited(b)) return;
markvisited(b);
if (b->s2) porec(rpo, b->s2);
if (b->s1) porec(rpo, b->s1);
*--*rpo = b;
}
/* also blkid */
void
sortrpo(struct function *fn)
{
static struct block **rpobuf;
struct block **rpoend, **rpo, *blk, *next;
int i, ndead;
xbgrow(&rpobuf, fn->nblk);
rpo = rpoend = rpobuf + fn->nblk,
startbbvisit();
fn->entry->id = 0;
porec(&rpo, fn->entry);
ndead = rpo - rpobuf;
if (ndead > 0) for (blk = fn->entry->lprev; blk != fn->entry; blk = next) {
next = blk->lprev;
if (!wasvisited(blk)) {
for (int i = 0; i < blk->ins.n; ++i) {
/* if unreachable block has alloca pseudo-instrs, move them to the entry
* to be able to delete it */
if (oisalloca(instrtab[blk->ins.p[i]].op)) {
vpush(&fn->entry->ins, blk->ins.p[i]);
}
}
for (int i = 0; i < blk->npred; ++i)
assert(!wasvisited(blkpred(blk, i)));
freeblk(fn, blk);
--ndead;
}
}
for (i = 1, ++rpo; rpo < rpoend; ++rpo, ++i) {
rpo[-1]->lnext = rpo[0];
rpo[0]->lprev = rpo[-1];
rpo[0]->id = i;
}
fn->entry->lprev = rpo[-1];
rpo[-1]->lnext = fn->entry;
fn->prop |= FNBLKID | FNRPO;
}
/* also blkid */
void
filldom(struct function *fn)
{
struct block *blk = fn->entry;
int i = 0;
FREQUIRE(FNRPO);
/* Implements 'A Simple, Fast Dominance Algorithm' by K. Cooper, T. Harvey, and K. Kennedy */
do blk->id = i++, blk->idom = NULL; while ((blk = blk->lnext) != fn->entry);
fn->entry->idom = fn->entry;
for (bool changed = 1; changed;) {
changed = 0;
blk = fn->entry->lnext;
do {
struct block *new = blkpred(blk, 0);
for (int i = 1; i < blk->npred; ++i) {
struct block *p = blkpred(blk, i);
if (p->idom) { /* new = intersect(p, new) */
while (p != new) {
while (p->id > new->id) p = p->idom;
while (p->id < new->id) new = new->idom;
}
}
}
if (blk->idom != new) {
blk->idom = new;
changed = 1;
}
} while ((blk = blk->lnext) != fn->entry);
}
fn->prop |= FNBLKID | FNDOM;
}
/* vim:set ts=3 sw=3 expandtab: */
|
