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
94
|
#include "ir.h"
extern struct instr instr[];
extern vec_of(struct call) calls;
extern vec_of(struct phi) phis;
static struct bitset taken[1];
static void
def(struct instr *ins)
{
if (ins->reg)
bsclr(taken, ins->reg - 1);
}
static int
nextreg(enum irclass cls)
{
int r0, rend, i;
if (kisint(cls)) {
r0 = mctarg->gpr0;
rend = mctarg->gpr0 + mctarg->ngpr;
} else if (kisflt(cls)) {
r0 = mctarg->fpr0;
rend = mctarg->fpr0 + mctarg->nfpr;
} else assert(0);
for (i = r0; i < rend; ++i) {
if (!bstest(taken, i)) {
bsset(taken, i);
return i;
}
}
assert(!"no more reg");
}
static void
use(struct block *blk, enum op op, int hint, union ref *ref)
{
struct instr *ins;
if (ref->t == RMORE) {
if (op == Ocall) {
struct call *call = &calls.p[ref->idx];
for (int i = 0; i < call->narg; ++i)
use(blk, 0, 0, &call->args[i]);
} else if (op == Ophi) {
struct phi *phi = &phis.p[ref->idx];
for (int i = 0; i < phi->n; ++i)
use(blk, 0, hint, &phi->ref[i]);
} else assert("ext?");
return;
} else if (ref->t != RTMP) return;
ins = &instr[ref->idx];
if (in_range(ins->op, Oalloca1, Oalloca16)) return;
if (!ins->reg) {
if (op == -1) /* cond branch */
if (in_range(ins->op, Oequ, Oulte) && ref->idx == blk->ins.p[blk->ins.n-1])
/* result of comparison instr is only used to conditionally branch,
* doesn't usually need a reg (handled by isel) */
return;
ins->reg = (hint ? hint : nextreg(ins->cls)) + 1;
}
}
void
regalloc(struct function *fn)
{
struct instr *ins;
struct block *last = fn->entry->lprev, *blk = last;
/* a dumb linear register allocator that visits instructions physically backwards
* starting at the end of the function, when encountering a use of a new
* temporary, it allocates a register for it. when encountering the definition
* of a temporary, it frees up its register
*/
do {
if (blk->jmp.arg.t) use(blk, blk->jmp.t == Jbcnd ? -1 : 0, 0, &blk->jmp.arg);
for (int i = blk->phi.n - 1; i >= 0; --i) {
ins = &instr[blk->phi.p[i]];
def(ins);
assert(ins->op == Ophi);
use(blk, Ophi, ins->reg, &ins->l);
}
for (int i = blk->ins.n - 1; i >= 0; --i) {
ins = &instr[blk->ins.p[i]];
def(ins);
if (ins->l.t) use(blk, ins->op, 0, &ins->l);
if (ins->r.t) use(blk, ins->op, 0, &ins->r);
}
} while ((blk = blk->lprev) != last);
}
/* vim:set ts=3 sw=3 expandtab: */
|
