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