]> Witch of Git - ivy/blob - src/trans/x64.rs
Add an extensible framework for adding built-ins
[ivy] / src / trans / x64.rs
1 use crate::trans::{Code, FnName, Func, Program, SsaName, Var};
2 use crate::ast;
3 use std::{
4 borrow::Cow,
5 fmt,
6 collections::HashMap,
7 io::{self, Write},
8 };
9
10 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
11 pub enum Label {
12 Global(u32),
13 Function(FnName),
14 Extern(&'static str),
15 Builtin(&'static str),
16 }
17
18 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
19 pub enum Addr {
20 Rip(Label),
21 Off(Reg, i32),
22 }
23
24 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
25 #[allow(unused)]
26 pub enum Reg {
27 Rax,
28 Rbx,
29 Rcx,
30 Rdx,
31 Rsi,
32 Rdi,
33 Rbp,
34 Rsp,
35 R8,
36 R9,
37 R10,
38 R11,
39 R12,
40 R13,
41 R14,
42 R15,
43 }
44
45 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
46 pub enum Inst {
47 Push(Reg),
48 Load(Reg, Addr),
49 Store(Addr, Reg),
50 Mov(Reg, Reg),
51 Imm(Reg, i64),
52 Lea(Reg, Addr),
53 Call(Label),
54 Jmp(Label),
55 Add(Reg, u32),
56 Sub(Reg, u32),
57 Pop(Reg),
58 Ret,
59 }
60
61 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
62 pub struct Definition {
63 name: Label,
64 body: Cow<'static, [Inst]>,
65 }
66
67 pub struct Global {
68 name: Label,
69 value: i64,
70 }
71
72 pub fn write_compile(
73 builtins: &HashMap<String, ast::Name>,
74 out: &mut impl Write,
75 prog: &Program,
76 ) -> io::Result<()> {
77 let (entry, globals, defns) = compile(&prog);
78 struct Entry {
79 number: u32,
80 defn: Definition,
81 params: u16,
82 }
83 let builtins = builtins
84 .iter()
85 .map(|(name, id)| {
86 let number = id.global_number().unwrap();
87 let (params, name, code) = builtin(&name);
88 Entry {
89 number,
90 defn: Definition {
91 name: Label::Builtin(name),
92 body: Cow::Borrowed(code),
93 },
94 params,
95 }
96 })
97 .collect::<Vec<_>>();
98 writeln!(out, ".data")?;
99 for global in globals {
100 writeln!(out, "{}", global)?;
101 }
102 writeln!(out)?;
103 writeln!(
104 out,
105 r#".text
106 .global _start
107 _start:
108 sub rsp, 15
109 and spl, 0xF0"#
110 )?;
111
112 for builtin in &builtins {
113 writeln!(
114 out,
115 r#"
116 lea rdi, [rip + {}]
117 mov rsi, {}
118 mov rdx, 0
119 call _ivy_make_lam
120 mov [rip + {}], rax"#,
121 builtin.defn.name,
122 builtin.params,
123 Label::Global(builtin.number),
124 )?;
125 }
126
127 writeln!(
128 out,
129 r#"
130 call {}
131 mov rdi, 0
132 call _ivy_exit
133 "#,
134 entry
135 )?;
136 for builtin in &builtins {
137 writeln!(out, "{}", builtin.defn)?;
138 writeln!(out)?;
139 }
140 for defn in defns {
141 writeln!(out, "{}", defn)?;
142 writeln!(out)?;
143 }
144 Ok(())
145 }
146
147 pub fn compile(prog: &Program) -> (Label, Vec<Global>, Vec<Definition>) {
148 let globals = prog
149 .globals
150 .iter()
151 .map(|&global| Global {
152 name: Label::Global(global),
153 value: 0,
154 })
155 .collect();
156 let defns = prog
157 .functions
158 .values()
159 .map(|func| compile_func(func))
160 .collect();
161 (Label::Function(prog.top), globals, defns)
162 }
163
164 fn even_up(x: usize) -> usize {
165 x + (x & 1)
166 }
167
168 fn compile_func(func: &Func) -> Definition {
169 fn stack(x: &SsaName) -> Addr {
170 Addr::Off(Reg::Rsp, x.0 as i32 * 8)
171 }
172
173 const HEADER_SIZE: i32 = 0x18;
174
175 fn param(x: u16) -> Addr {
176 Addr::Off(Reg::Rbx, HEADER_SIZE + x as i32 * 8)
177 }
178
179 let upvar = move |x: u16| {
180 let params = func.params as i32 * 8;
181 Addr::Off(Reg::Rbx, HEADER_SIZE + params + x as i32 * 8)
182 };
183
184 let mut body = Vec::new();
185 let stack_slots = even_up(func.order.len());
186 body.push(Inst::Push(Reg::Rbx));
187 body.push(Inst::Mov(Reg::Rbx, Reg::Rdi));
188 body.push(Inst::Sub(Reg::Rsp, stack_slots as u32 * 8));
189 for ssa in &func.order {
190 match &func.block[ssa] {
191 Code::Load(Var::Global(x)) => {
192 body.push(Inst::Load(Reg::Rax, Addr::Rip(Label::Global(*x))));
193 body.push(Inst::Store(stack(ssa), Reg::Rax));
194 }
195 Code::Load(Var::Param(x)) => {
196 body.push(Inst::Load(Reg::Rax, param(*x)));
197 body.push(Inst::Store(stack(ssa), Reg::Rax));
198 }
199 Code::Load(Var::Upvar(x)) => {
200 body.push(Inst::Load(Reg::Rax, upvar(*x)));
201 body.push(Inst::Store(stack(ssa), Reg::Rax));
202 }
203 Code::Load(Var::Ssa(ssa2)) => {
204 body.push(Inst::Load(Reg::Rax, stack(ssa2)));
205 body.push(Inst::Store(stack(ssa), Reg::Rax));
206 }
207 Code::StoreGlobal(x, s) => {
208 body.push(Inst::Load(Reg::Rax, stack(s)));
209 body.push(Inst::Store(Addr::Rip(Label::Global(*x)), Reg::Rax));
210 }
211 Code::MakeLam {
212 name,
213 upvars,
214 params,
215 } => {
216 body.push(Inst::Lea(Reg::Rdi, Addr::Rip(Label::Function(*name))));
217 body.push(Inst::Imm(Reg::Rsi, *params as i64));
218 body.push(Inst::Imm(Reg::Rdx, upvars.len() as i64));
219 body.push(Inst::Call(Label::Extern("_ivy_make_lam")));
220 // @TODO: Implement copying in closure captures
221 assert!(upvars.is_empty());
222 body.push(Inst::Store(stack(ssa), Reg::Rax));
223 }
224 Code::App(terms) => {
225 let mut terms = terms.iter();
226 body.push(Inst::Load(
227 Reg::Rdi,
228 stack(terms.next().expect("a function to apply")),
229 ));
230 match terms.next() {
231 Some(s) => body.push(Inst::Load(Reg::Rsi, stack(s))),
232 None => body.push(Inst::Imm(Reg::Rsi, 0)),
233 }
234 body.push(Inst::Call(Label::Extern("_ivy_app")));
235 while let Some(term) = terms.next() {
236 body.push(Inst::Mov(Reg::Rdi, Reg::Rax));
237 body.push(Inst::Load(Reg::Rsi, stack(term)));
238 body.push(Inst::Call(Label::Extern("_ivy_app_mut")));
239 }
240 body.push(Inst::Store(stack(ssa), Reg::Rax));
241 }
242 Code::Num(n) => {
243 body.push(Inst::Imm(Reg::Rax, (n << 1) | 1i64));
244 body.push(Inst::Store(stack(ssa), Reg::Rax));
245 }
246 }
247 }
248 body.push(Inst::Add(Reg::Rsp, stack_slots as u32 * 8));
249 body.push(Inst::Pop(Reg::Rbx));
250 body.push(Inst::Ret);
251 Definition {
252 name: Label::Function(func.name),
253 body: Cow::Owned(body),
254 }
255 }
256
257 impl fmt::Display for Definition {
258 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
259 match self.body.len() {
260 0 => write!(fmt, "{}:", self.name),
261 1 => write!(fmt, "{}: {}", self.name, self.body[0]),
262 len => {
263 writeln!(fmt, "{}:", self.name)?;
264 for inst in &self.body[..len - 1] {
265 writeln!(fmt, " {}", inst)?;
266 }
267 write!(fmt, " {}", self.body.last().unwrap())
268 }
269 }
270 }
271 }
272
273 impl fmt::Display for Global {
274 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
275 write!(fmt, "{}: .quad {}", self.name, self.value)
276 }
277 }
278
279 impl fmt::Display for Label {
280 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
281 match self {
282 Label::Global(g) => write!(fmt, "IVY_GLOBAL${}", g),
283 Label::Function(f) => write!(fmt, "ivy_fn${}", f.0),
284 Label::Extern(l) => write!(fmt, "{}", l),
285 Label::Builtin(l) => write!(fmt, "ivy_builtin${}", l),
286 }
287 }
288 }
289
290 impl fmt::Display for Reg {
291 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
292 match self {
293 Reg::Rax => write!(fmt, "rax"),
294 Reg::Rbx => write!(fmt, "rbx"),
295 Reg::Rcx => write!(fmt, "rcx"),
296 Reg::Rdx => write!(fmt, "rdx"),
297 Reg::Rsi => write!(fmt, "rsi"),
298 Reg::Rdi => write!(fmt, "rdi"),
299 Reg::Rbp => write!(fmt, "rbp"),
300 Reg::Rsp => write!(fmt, "rsp"),
301 Reg::R8 => write!(fmt, "r8"),
302 Reg::R9 => write!(fmt, "r9"),
303 Reg::R10 => write!(fmt, "r10"),
304 Reg::R11 => write!(fmt, "r11"),
305 Reg::R12 => write!(fmt, "r12"),
306 Reg::R13 => write!(fmt, "r13"),
307 Reg::R14 => write!(fmt, "r14"),
308 Reg::R15 => write!(fmt, "r15"),
309 }
310 }
311 }
312
313 impl fmt::Display for Addr {
314 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
315 match self {
316 Addr::Rip(l) => write!(fmt, "[rip + {}]", l),
317 Addr::Off(r, o) => write!(fmt, "[{} + {}]", r, o),
318 }
319 }
320 }
321
322 impl fmt::Display for Inst {
323 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
324 match self {
325 Inst::Push(r) => write!(fmt, "push {}", r),
326 Inst::Pop(r) => write!(fmt, "pop {}", r),
327 Inst::Mov(d, s) => write!(fmt, "mov {}, {}", d, s),
328 Inst::Load(r, a) => write!(fmt, "mov {}, {}", r, a),
329 Inst::Store(a, r) => write!(fmt, "mov {}, {}", a, r),
330 Inst::Imm(r, i) => write!(fmt, "mov {}, {}", r, i),
331 Inst::Lea(r, a) => write!(fmt, "lea {}, {}", r, a),
332 Inst::Call(l) => write!(fmt, "call {}", l),
333 Inst::Jmp(l) => write!(fmt, "jmp {}", l),
334 Inst::Add(r, x) => write!(fmt, "add {}, {}", r, x),
335 Inst::Sub(r, x) => write!(fmt, "sub {}, {}", r, x),
336 Inst::Ret => write!(fmt, "ret"),
337 }
338 }
339 }
340
341 fn builtin(name: &str) -> (u16, &'static str, &'static [Inst]) {
342 match name {
343 "debug" => (1, "debug", &[
344 Inst::Load(Reg::Rdi, Addr::Off(Reg::Rdi, 0x18)),
345 Inst::Jmp(Label::Extern("_ivy_debug")),
346 ]),
347 name => panic!("Unsupported builtin '{}' for x64", name),
348 }
349 }