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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
#include "ir.h"
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;
assert(cls);
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 || op == Ointrin) {
struct call *call = &calltab.p[ref->idx];
for (int i = 0; i < call->narg; ++i)
use(blk, 0, op == Ocall ? call->abiargregs[i] : -1, &call->args[i]);
} else if (op == Ophi) {
struct phi *phi = &phitab.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 = &instrtab[ref->idx];
if (oisalloca(ins->op)) return;
if (!ins->cls) return;
if (!ins->reg) {
if (op == -1) /* cond branch */
if (oiscmp(ins->op) && 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;
/* TODO implement actual constraints and stuff */
if (ins->op == Ocall) {
struct call *call = &calltab.p[ins->r.idx];
hint = call->abiret[0].reg;
} else if (ins->op == Ocall2r) {
struct instr *ins2 = &instrtab[ins->l.idx];
struct call *call = &calltab.p[ins2->r.idx];
assert(ins->l.t == RTMP && ins2->op == Ocall);
hint = call->abiret[0].reg;
}
if (hint != -1 && !bstest(taken, hint)) {
bsset(taken, hint);
ins->reg = hint + 1;
} else {
ins->reg = nextreg(ins->cls) + 1;
}
}
}
void
regalloc(struct function *fn)
{
struct instr *ins;
struct block *last = fn->entry->lprev, *blk;
/* 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
*/
blk = last;
do {
for (int i = 0; i < 2; ++i) {
if (!blk->jmp.arg[i].t) break;
use(blk, (blk->jmp.t == Jb) - 1,
blk->jmp.t == Jret ? fn->abiret[i].reg : -1,
&blk->jmp.arg[i]);
}
for (int i = blk->phi.n - 1; i >= 0; --i) {
ins = &instrtab[blk->phi.p[i]];
def(ins);
assert(ins->op == Ophi);
use(blk, Ophi, ins->reg - 1, &ins->l);
}
for (int i = blk->ins.n - 1; i >= 0; --i) {
int hint0 = -1, hint1 = -1;
ins = &instrtab[blk->ins.p[i]];
def(ins);
if (ins->op == Ocopy) hint0 = ins->reg - 1;
if (ins->l.t) use(blk, ins->op, hint0, &ins->l);
if (ins->r.t) use(blk, ins->op, hint1, &ins->r);
}
} while ((blk = blk->lprev) != last);
}
/* vim:set ts=3 sw=3 expandtab: */
|
