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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
|
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdarg.h>
#include "simple-reg.h"
#define TRUE 1
#define FALSE 0
static int
find_reg (op_t reg, int n_registers, const op_t *registers)
{
int i;
for (i = 0; i < n_registers; ++i)
{
if (registers[i] == reg)
return i;
}
return -1;
}
/* Calling this function conceptually spills every register
* allocated by @parent so far, except those listed as preserved,
* to memory, freeing them up for reuse.
*
* In practice, registers aren't actually written to memory
* until necessary.
*/
void
reg_alloc_init (reg_alloc_t *reg_alloc,
asm_t *as,
int n_registers, const op_t *registers, int register_size,
reg_alloc_t *parent,
int n_preserved, ...)
{
int preserved[MAX_REGISTERS] = { 0 };
va_list list;
int i;
reg_alloc->as = as;
reg_alloc->register_size = register_size;
reg_alloc->n_spills = 0;
reg_alloc->n_registers = n_registers;
va_start (list, n_preserved);
for (i = 0; i < n_preserved; ++i)
{
op_t reg = va_arg (list, op_t);
preserved[find_reg (reg, n_registers, registers)] = TRUE;
}
va_end (list);
for (i = 0; i < n_registers; ++i)
{
reg_alloc->info[i].reg = registers[i];
switch (parent->info[i].state)
{
case SPILLABLE:
if (preserved[i])
{
fprintf (stderr,
"Asking to preserve a register that "
"was previously spilled");
abort();
}
reg_alloc->info[i].state = SPILLABLE;
break;
case SPILLED:
case IN_USE:
if (preserved[i])
reg_alloc->info[i].state = IN_USE;
else
reg_alloc->info[i].state = SPILLABLE;
break;
case UNUSED:
reg_alloc->info[i].state = UNUSED;
break;
}
}
}
op_t
reg_alloc_alloc (reg_alloc_t *reg_alloc)
{
int i;
/* First try to allocate an unused register */
for (i = 0; i < reg_alloc->n_registers; ++i)
{
if (reg_alloc->info[i].state == UNUSED)
{
reg_alloc->info[i].state = IN_USE;
return reg_alloc->info[i].reg;
}
}
/* If that failed, find a spillable one */
for (i = 0; i < reg_alloc->n_registers; ++i)
{
reg_info_t *info = ®_alloc->info[i];
if (info->state == SPILLABLE)
{
op_t spill_loc;
/* Allocate space on the stack if this is the first time
* we spill something.
*
* FIXME: this will interact badly if there is more than one
* register allocator in play. Maybe register allocators should
* have support for register classes, or maybe we need the
* concept of a stack manager.
*/
if (reg_alloc->n_spills == 0)
{
int n_stack_bytes =
reg_alloc->n_registers * reg_alloc->register_size;
x86_asm (
reg_alloc->as,
"sub", rsp, IMM (n_stack_bytes),
NULL);
}
spill_loc = BASE (
rsp, reg_alloc->n_spills * reg_alloc->register_size);
reg_alloc->info[i].state = SPILLED;
reg_alloc->info[i].spill_loc = spill_loc;
reg_alloc->n_spills++;
x86_asm (
reg_alloc->as,
"mov", spill_loc, reg_alloc->info[i].reg,
NULL);
return reg_alloc->info[i].reg;
}
}
/* No register could be allocated */
return (op_t)-1;
}
void
reg_alloc_free (reg_alloc_t *reg_alloc, op_t op)
{
}
/* Frees all registers allocated, except those listed, which
* become allocated in the parent allocator.
*
* If it is not possible to allocate all preserved registers,
* FALSE is returned and the JIT compilation should be aborted.
*/
int
reg_alloc_fini (reg_alloc_t *reg_alloc,
int n_preserved, ...)
{
int i;
va_list list;
/* If we have a parent allocator, this function must
* accomplish two things:
*
* (1) All the registers that we spilled must be moved back
* into their original location.
*
* (2) All the preserved registers must be allocated in
* the parent allocator.
*
* (3) Finally, the stack pointer must be returned to its original
* state.
*
* For (2), if the register in question is simply IN_USE, that
* means the parent doesn't deal with it. If it is SPILLED, then
* we have a conflict between (1) and (2). In this case, if we
* can find a register in the parent that is UNUSED, we can
* simply move the preserved register there. If we can't, we
* have to find a register that is SPILLABLE in the parent and
* then depending on *our* opinion of that register:
*
* if it is SPILLABLE for us, then after restoring all spilled
* registers, we can simply allocate a register afterwards.
*/
/* The preserved registers must be turned into allocated
* registers in the parent.
*
* If the register is UNUSED in the parent, all is well;
* we can just mark it as IN_USE.
*
* If the register is IN_USE or SPILLABLE in the parent,
* then we
* if the register is IN_USE or SPILLABLE in the parent,
* we have to find an unused register and move it there.
*
* If no such register can be found, we have to find
* a spillable register in the parent and move it there.
* In this case, a tricky dance must be performed if the
* register in question is also SPILLED
*/
va_start (list, n_preserved);
for (i = 0; i < n_preserved; ++i)
{
op_t reg = va_arg (list, op_t);
}
va_end (list);
return 0;
}
|
