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
|
=== Goal
A memory-safe language with a simple translator to x86 that can be feasibly
written without itself needing a translator.
Memory-safe: it should be impossible to:
a) create a pointer out of arbitrary data, or
b) to access heap memory after it's been freed.
Simple: do all the work in a 2-pass translator:
Pass 1: check each instruction's types in isolation.
Pass 2: emit code for each instruction in isolation.
=== Overview of the language
A program consists of a series of type, function and global variable declarations.
(Also constants and tests, but let's focus on these.)
Type declarations basically follow Hindley-Milner with product and (tagged) sum
types. Types are written in s-expression form. There's a `ref` type that's a
type-safe fat pointer, with an alloc id that gets incremented after each
allocation. Memory allocation and reclamation is manual. Dereferencing a ref
after its underlying memory is reclaimed (pointer alloc id no longer matches
payload alloc id) is guaranteed to immediately kill the program (like a
segfault).
# product type
type foo [
x : int
y : (ref int)
z : bar
]
# sum type
choice bar [
x : int
y : point
]
Functions have a header and a series of instructions in the body:
fn f a : int -> b : int [
...
]
Instructions have the following format:
io1, io2, ... <- operation i1, i2, ...
i1, i2 operands on the right hand side are immutable. io1, io2 are in-out
operands. They're written to, and may also be read.
User-defined functions will be called with the same syntax. They'll translate
to a sequence of push instructions (one per operand, both in and in-out), a
call instruction, and a sequence of pop instructions, either to a black hole
(in operands) or a location (in-out operands). This follows the standard Unix
calling convention. Each operand needs to be something push/pop can accept.
Primitive operations depend on the underlying processor. We'd like each primitive
operation supported by the language to map to a single instruction in the ISA.
Sometimes we have to violate that (see below), but we definitely won't be
writing to any temporary locations behind the scenes. The language affords
control over registers, and tracking unused registers gets complex, and
besides we may have no unused registers at a specific point. Instructions only
modify their operands.
In most ISAs, instructions operate on at most a word of data at a time. They
also tend to not have more than 2-3 operands, and not modify more than 2
locations in memory.
Since the number of reads from memory is limited, we break up complex high-level
operations using a special type called `address`. Addresses are strictly
short-term entities. They can't be stored in a compound type, and they can't
be passed into or returned from a user-defined function. They also can't be
used after a function call (because it could free the underlying memory) or
label (because it gets complex to check control flow, and we want to translate
each instruction simply and in isolation).
=== Compilation to 32-bit x86
Values can be stored:
in code (literals)
in registers
on the stack
on the global segment
Variables on the stack are stored at *(ESP+n)
Global variables are stored at *disp32, where disp32 is statically known
Address variables have to be in a register.
- You need them in a register to do a lookup, and
- Saving them to even the stack increases the complexity of checks needed on
function calls or labels.
Compilation proceeds by pattern matching over an instruction along with
knowledge about the types of its operands, as well as where they're stored
(register/stack/global). We now enumerate mappings for various categories of
instructions, based on the type and location of their operands.
Where types of operands aren't mentioned below, all operands of an instruction
should have the same (word-length) type.
Lots of special cases because of limitations of the x86 ISA. Beware.
A. x : int <- add y
Requires y to be scalar. Result will always be an int. No pointer arithmetic.
reg <- add literal => 81 0/subop 3/mod ...(0)
reg <- add reg => 01 3/mod ...(1)
reg <- add stack => 03 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 reg/r32 ...(2)
reg <- add global => 03 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(3)
stack <- add literal => 81 0/subop 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 literal/imm32 ...(4)
stack <- add reg => 01 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 reg/r32 ...(5)
stack <- add stack => disallowed
stack <- add global => disallowed
global <- add literal => 81 0/subop 0/mod 5/rm32/include-disp32 global/disp32 literal/imm32 ...(6)
global <- add reg => 01 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(7)
global <- add stack => disallowed
global <- add global => disallowed
Similarly for sub, and, or, xor and even copy. Replace the opcodes above with corresponding ones from this table:
add sub and or xor copy/mov
reg <- op literal 81 0/subop 81 5/subop 81 4/subop 81 1/subop 81 6/subop c7
reg <- op reg 01 or 03 29 or 2b 21 or 23 09 or 0b 31 or 33 89 or 8b
reg <- op stack 03 2b 23 0b 33 8b
reg <- op global 03 2b 23 0b 33 8b
stack <- op literal 81 0/subop 81 5/subop 81 4/subop 81 1/subop 81 6/subop c7
stack <- op reg 01 29 21 09 31 89
global <- op literal 81 0/subop 81 5/subop 81 4/subop 81 1/subop 81 6/subop c7
global <- op reg 01 29 21 09 31 89
B. x/reg : int <- mul y
Requires both y to be scalar.
x must be in a register. Multiplies can't write to memory.
reg <- mul literal => 69 ...(8)
reg <- mul reg => 0f af 3/mod ...(9)
reg <- mul stack => 0f af 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 reg/r32 ...(10)
reg <- mul global => 0f af 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(11)
C. x/EAX/quotient : int, y/EDX/remainder : int <- idiv z # divide EAX by z; store the result in EAX and EDX
Requires source x and z to both be scalar.
x must be in EAX and y must be in EDX. Divides can't write anywhere else.
First clear EDX (we don't support ints larger than 32 bits):
31/xor 3/mod 2/rm32/EDX 2/r32/EDX
then:
EAX, EDX <- idiv literal => disallowed
EAX, EDX <- idiv reg => f7 7/subop 3/mod ...(12)
EAX, EDX <- idiv stack => f7 7/subop 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 ...(13)
EAX, EDX <- idiv global => f7 7/subop 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(14)
D. x : int <- not
Requires x to be an int.
reg <- not => f7 3/mod ...(15)
stack <- not => f7 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 ...(16)
global <- not => f7 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(17)
E. x : (address t) <- get o : T, %f
(Assumes T.f has type t.)
o can't be on a register since it's a non-primitive (likely larger than a word)
f is a literal
x must be in a register (by definition for an address)
below '*' works on either address or ref types
For raw stack values we want to read *(ESP+n)
For raw global values we want to read *disp32
For address stack values we want to read *(ESP+n)+
*(ESP+n) contains an address
so we want to compute *(ESP+n) + literal
reg1 <- get reg2, literal => 8d/lea 1/mod reg2/rm32 literal/disp8 reg1/r32 ...(18)
reg <- get stack, literal => 8d/lea 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n+literal/disp8 reg/r32 ...(19)
(simplifying assumption: stack frames can't be larger than 256 bytes)
reg <- get global, literal => 8d/lea 0/mod 5/rm32/include-disp32 global+literal/disp32, reg/r32 ...(20)
F. x : (offset T) <- index i : int, %size(T)
reg1 <- index reg2, literal => 69/mul 3/mod reg2/rm32 literal/imm32 -> reg1/r32
or 68/mul 3/mod reg2/rm32 literal/imm8 -> reg1/r32 ...(21)
reg1 <- index stack, literal => 69/mul 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 literal/imm32 -> reg1/r32 ...(22)
reg1 <- index global, literal => 69/mul 0/mod 5/rm32/include-disp32 global/disp32 literal/imm32 -> reg1/r32 ...(23)
optimization: avoid multiply if literal is a power of 2
use SIB byte if literal is 2, 4 or 8
or left shift
G. x : (address T) <- advance o : (array T), idx : (offset T)
reg <- advance a/reg, idx/reg => 8d/lea 0/mod 4/rm32/SIB a/base idx/index 0/scale reg/r32 ...(24)
reg <- advance stack, literal => 8d/lea 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n+literal/disp8 reg/r32 ...(25)
reg <- advance stack, reg2 => 8d/lea 1/mod 4/rm32/SIB 4/base/ESP reg2/index 0/scale n/disp8 reg/r32 ...(26)
reg <- advance global, literal => 8d/lea 0/mod 5/rm32/include-disp32 global+literal/disp32, reg/r32 ...(27)
also instructions for runtime bounds checking
=== Example
Putting it all together: code generation for `a[i].y = 4` where a is an array
of 2-d points with x, y coordinates.
If a is allocated on the stack, say of type (array point 6) at (ESP+4):
offset/EAX : (offset point) <- index i, 8 # (22)
tmp/EBX : (address point) <- advance a : (array point 6), offset/EAX # (26)
tmp2/ECX : (address number) <- get tmp/EBX : (address point), 4/y # (18)
*tmp2/ECX <- copy 4 # (5 for copy/mov with 0 disp8)
Many instructions, particularly variants of 'get' and 'advance' -- end up encoding the exact same instructions.
But the types differ, and the type-checker checks them differently.
=== Advanced checks
Couple of items require inserting mapping to multiple instructions:
bounds checking against array length in 'advance'
dereferencing 'ref' types (see type list up top)
A. Dereferencing a ref
tmp/EDX <- advance *s, tmp0/EDI
=> compare (ESP+4), *(ESP+8) ; '*' from compiler2
jump-unless-equal panic
EDX <- add ESP, 8
EDX <- copy *EDX
EDX <- add EDX, 4
EDX <- 8d/lea EDX + result
=== More speculative ideas
Initialize data segment with special extensible syntax for literals. All
literals except numbers and strings start with %.
%size(type) => compiler replaces with size of type
%point(3, 4) => two words
and so on.
=== Credits
Forth
C
Rust
Lisp
qhasm
|