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
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
|
(** Layout of activation records; translation from Linear to Mach. *)
Require Import Coqlib.
Require Import Maps.
Require Import Errors.
Require Import AST.
Require Import Integers.
Require Import Op.
Require Import RTL.
Require Import Locations.
Require Import Linear.
Require Import Bounds.
Require Import Mach.
Require Import Conventions.
(** * Layout of activation records *)
(** The general shape of activation records is as follows,
from bottom (lowest offsets) to top:
- 24 reserved bytes. The first 4 bytes hold the back pointer to the
activation record of the caller. We use the 4 bytes at offset 12
to store the return address. (These are reserved by the PowerPC
application binary interface.) The remaining bytes are unused.
- Space for outgoing arguments to function calls.
- Local stack slots of integer type.
- Saved values of integer callee-save registers used by the function.
- One word of padding, if necessary to align the following data
on a 8-byte boundary.
- Local stack slots of float type.
- Saved values of float callee-save registers used by the function.
- Space for the stack-allocated data declared in Cminor.
To facilitate some of the proofs, the Cminor stack-allocated data
starts at offset 0; the preceding areas in the activation record
therefore have negative offsets. This part (with negative offsets)
is called the ``frame'' (see the [Machabstr] semantics for the Mach
language), by opposition with the ``Cminor stack data'' which is the part
with positive offsets.
The [frame_env] compilation environment records the positions of
the boundaries between areas in the frame part.
*)
Record frame_env : Set := mk_frame_env {
fe_size: Z;
fe_ofs_int_local: Z;
fe_ofs_int_callee_save: Z;
fe_num_int_callee_save: Z;
fe_ofs_float_local: Z;
fe_ofs_float_callee_save: Z;
fe_num_float_callee_save: Z
}.
(** Computation of the frame environment from the bounds of the current
function. *)
Definition make_env (b: bounds) :=
let oil := 4 * b.(bound_outgoing) in (* integer locals *)
let oics := oil + 4 * b.(bound_int_local) in (* integer callee-saves *)
let oendi := oics + 4 * b.(bound_int_callee_save) in
let ofl := align oendi 8 in (* float locals *)
let ofcs := ofl + 8 * b.(bound_float_local) in (* float callee-saves *)
let sz := ofcs + 8 * b.(bound_float_callee_save) in (* total frame size *)
mk_frame_env sz oil oics b.(bound_int_callee_save)
ofl ofcs b.(bound_float_callee_save).
(** Computation the frame offset for the given component of the frame.
The component is expressed by the following [frame_index] sum type. *)
Inductive frame_index: Set :=
| FI_local: Z -> typ -> frame_index
| FI_arg: Z -> typ -> frame_index
| FI_saved_int: Z -> frame_index
| FI_saved_float: Z -> frame_index.
Definition offset_of_index (fe: frame_env) (idx: frame_index) :=
match idx with
| FI_local x Tint => fe.(fe_ofs_int_local) + 4 * x
| FI_local x Tfloat => fe.(fe_ofs_float_local) + 8 * x
| FI_arg x ty => 4 * x
| FI_saved_int x => fe.(fe_ofs_int_callee_save) + 4 * x
| FI_saved_float x => fe.(fe_ofs_float_callee_save) + 8 * x
end.
(** * Saving and restoring callee-save registers *)
(** [save_callee_save fe k] adds before [k] the instructions that
store in the frame the values of callee-save registers used by the
current function. *)
Definition save_callee_save_reg
(bound: frame_env -> Z) (number: mreg -> Z) (mkindex: Z -> frame_index)
(ty: typ) (fe: frame_env) (cs: mreg) (k: Mach.code) :=
let i := number cs in
if zlt i (bound fe)
then Msetstack cs (Int.repr (offset_of_index fe (mkindex i))) ty :: k
else k.
Definition save_callee_save_regs
(bound: frame_env -> Z) (number: mreg -> Z) (mkindex: Z -> frame_index)
(ty: typ) (fe: frame_env) (csl: list mreg) (k: Mach.code) :=
List.fold_right (save_callee_save_reg bound number mkindex ty fe) k csl.
Definition save_callee_save_int (fe: frame_env) :=
save_callee_save_regs
fe_num_int_callee_save index_int_callee_save FI_saved_int
Tint fe int_callee_save_regs.
Definition save_callee_save_float (fe: frame_env) :=
save_callee_save_regs
fe_num_float_callee_save index_float_callee_save FI_saved_float
Tfloat fe float_callee_save_regs.
Definition save_callee_save (fe: frame_env) (k: Mach.code) :=
save_callee_save_int fe (save_callee_save_float fe k).
(** [restore_callee_save fe k] adds before [k] the instructions that
re-load from the frame the values of callee-save registers used by the
current function, restoring these registers to their initial values. *)
Definition restore_callee_save_reg
(bound: frame_env -> Z) (number: mreg -> Z) (mkindex: Z -> frame_index)
(ty: typ) (fe: frame_env) (cs: mreg) (k: Mach.code) :=
let i := number cs in
if zlt i (bound fe)
then Mgetstack (Int.repr (offset_of_index fe (mkindex i))) ty cs :: k
else k.
Definition restore_callee_save_regs
(bound: frame_env -> Z) (number: mreg -> Z) (mkindex: Z -> frame_index)
(ty: typ) (fe: frame_env) (csl: list mreg) (k: Mach.code) :=
List.fold_right (restore_callee_save_reg bound number mkindex ty fe) k csl.
Definition restore_callee_save_int (fe: frame_env) :=
restore_callee_save_regs
fe_num_int_callee_save index_int_callee_save FI_saved_int
Tint fe int_callee_save_regs.
Definition restore_callee_save_float (fe: frame_env) :=
restore_callee_save_regs
fe_num_float_callee_save index_float_callee_save FI_saved_float
Tfloat fe float_callee_save_regs.
Definition restore_callee_save (fe: frame_env) (k: Mach.code) :=
restore_callee_save_int fe (restore_callee_save_float fe k).
(** * Code transformation. *)
(** Translation of operations and addressing mode.
In Linear, the stack pointer has offset 0, i.e. points to the
beginning of the Cminor stack data block. In Mach, the stack
pointer points to the bottom of the activation record,
at offset [- fe.(fe_size)] where [fe] is the frame environment.
Operations and addressing mode that are relative to the stack pointer
must therefore be offset by [fe.(fe_size)] to preserve their
behaviour. *)
Definition transl_op (fe: frame_env) (op: operation) :=
match op with
| Oaddrstack ofs => Oaddrstack (Int.add (Int.repr fe.(fe_size)) ofs)
| _ => op
end.
Definition transl_addr (fe: frame_env) (addr: addressing) :=
match addr with
| Ainstack ofs => Ainstack (Int.add (Int.repr fe.(fe_size)) ofs)
| _ => addr
end.
(** Translation of a Linear instruction. Prepends the corresponding
Mach instructions to the given list of instructions.
[Lgetstack] and [Lsetstack] moves between registers and stack slots
are turned into [Mgetstack], [Mgetparent] or [Msetstack] instructions
at offsets determined by the frame environment.
Instructions and addressing modes are modified as described previously.
Code to restore the values of callee-save registers is inserted
before the function returns. *)
Definition transl_instr
(fe: frame_env) (i: Linear.instruction) (k: Mach.code) : Mach.code :=
match i with
| Lgetstack s r =>
match s with
| Local ofs ty =>
Mgetstack (Int.repr (offset_of_index fe (FI_local ofs ty))) ty r :: k
| Incoming ofs ty =>
Mgetparam (Int.repr (offset_of_index fe (FI_arg ofs ty))) ty r :: k
| Outgoing ofs ty =>
Mgetstack (Int.repr (offset_of_index fe (FI_arg ofs ty))) ty r :: k
end
| Lsetstack r s =>
match s with
| Local ofs ty =>
Msetstack r (Int.repr (offset_of_index fe (FI_local ofs ty))) ty :: k
| Incoming ofs ty =>
k (* should not happen *)
| Outgoing ofs ty =>
Msetstack r (Int.repr (offset_of_index fe (FI_arg ofs ty))) ty :: k
end
| Lop op args res =>
Mop (transl_op fe op) args res :: k
| Lload chunk addr args dst =>
Mload chunk (transl_addr fe addr) args dst :: k
| Lstore chunk addr args src =>
Mstore chunk (transl_addr fe addr) args src :: k
| Lcall sig ros =>
Mcall sig ros :: k
| Ltailcall sig ros =>
restore_callee_save fe (Mtailcall sig ros :: k)
| Lalloc =>
Malloc :: k
| Llabel lbl =>
Mlabel lbl :: k
| Lgoto lbl =>
Mgoto lbl :: k
| Lcond cond args lbl =>
Mcond cond args lbl :: k
| Lreturn =>
restore_callee_save fe (Mreturn :: k)
end.
(** Translation of a function. Code that saves the values of used
callee-save registers is inserted at function entry, followed
by the translation of the function body.
Subtle point: the compiler must check that the frame is no
larger than [- Int.min_signed] bytes, otherwise arithmetic overflows
could occur during frame accesses using signed machine integers as
offsets. *)
Definition transl_code
(fe: frame_env) (il: list Linear.instruction) : Mach.code :=
List.fold_right (transl_instr fe) nil il.
Definition transl_body (f: Linear.function) (fe: frame_env) :=
save_callee_save fe (transl_code fe f.(Linear.fn_code)).
Open Local Scope string_scope.
Definition transf_function (f: Linear.function) : res Mach.function :=
let fe := make_env (function_bounds f) in
if zlt f.(Linear.fn_stacksize) 0 then
Error (msg "Stacking.transf_function")
else if zlt (- Int.min_signed) fe.(fe_size) then
Error (msg "Too many spilled variables, stack size exceeded")
else
OK (Mach.mkfunction
f.(Linear.fn_sig)
(transl_body f fe)
f.(Linear.fn_stacksize)
fe.(fe_size)).
Definition transf_fundef (f: Linear.fundef) : res Mach.fundef :=
AST.transf_partial_fundef transf_function f.
Definition transf_program (p: Linear.program) : res Mach.program :=
transform_partial_program transf_fundef p.
|