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
91
92
93
|
#include "ir.h"
#include "u_hash.h"
static inline bool
pure(const Instr *ins)
{
return oisarith(ins->op) || (oisload(ins->op) && !ins->keep);
}
static inline bool
insequ(const Instr *a, const Instr *b)
{
if (a->op != b->op) return 0;
enum op op = a->op;
switch (opnoper[op]) {
default: assert(0);
case 2: if (a->r.bits != b->r.bits) return 0;
case 1: if (a->l.bits != b->l.bits) return 0;
}
return 1;
}
static struct Ht {
uint t;
ushort memno, cutoff;
Block *b;
} *insht;
static uint ninsht;
static inline size_t
hashins(const Instr *ins)
{
return hashb(0, ins, sizeof *ins);
}
static bool
doms(Block *blk, Block *b)
{
for (;; b = b->idom) {
if (blk == b) return 1;
if (blk == b->idom) return 1;
if (blk->id > b->id) return 0;
}
}
static int
uniq(int t, Block *blk, int cutoff, int memno)
{
assert((uint)t < MAXINSTR);
Instr *ins = &instrtab[t];
if (!pure(ins)) return t;
for (size_t h = hashins(&instrtab[t]), i = h;; ++i) {
struct Ht *p = &insht[i &= (ninsht-1)];
if (!p->b) Put: {
p->b = blk;
p->memno = memno;
p->cutoff = cutoff;
return p->t = t;
} else if (insequ(&instrtab[p->t], ins)) {
if (p->cutoff == cutoff && (!oisload(ins->op) || p->memno == memno) && doms(p->b, blk))
return p->t;
goto Put;
}
}
}
void
cselim(Function *fn)
{
FREQUIRE(FNUSE | FNRPO | FNDOM | FNBLKID);
extern int ninstrtab;
for (ninsht = 32; ninsht <= ninstrtab; ninsht *= 2) ;
insht = allocz(fn->passarena, ninsht * sizeof *insht, 0);
int memno = 0, cutoff = 0;
Block *blk = fn->entry;
do {
++memno;
for (int i = 0; i < blk->ins.n; ++i) {
int t = blk->ins.p[i], q;
if ((q = uniq(t, blk, cutoff, memno)) != t) {
replcuses(mkref(RTMP, t), mkref(RTMP, q));
delinstr(blk, i--);
} else if (oisstore(instrtab[t].op)) {
/* assume everything alias everything */
++memno;
} else if (instrtab[t].op == Ocall) {
++cutoff;
}
}
} while ((blk = blk->lnext) != fn->entry);
}
/* vim:set ts=3 sw=3 expandtab: */
|
