From 55bd00592439e5ff1485503b6b831868655a0a13 Mon Sep 17 00:00:00 2001 From: Cassie Jones Date: Sat, 29 Feb 2020 19:28:23 +0100 Subject: [PATCH] Implement basic code generation This commit makes it possible to compile and assemble sixty-four.vy, and compute the correct result!!!!!!! In order to avoid having to do any detailed analysis on variable usage, this currently accesses everything via the stack. This means allocating stack space for every instruction, and then saving and loading everything from the stack frame. The translation of individual functions is pretty direct. Due to going via the stack for everything, we can translate each individual instruction on its own, in order, without looking at other instructions. This currently doesn't implement copying data into the closures, because the current test case doesn't do that at all. This also hard-codes the one builtin (debug) that's referred to by the test program. --- src/trans/x64.rs | 128 ++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 126 insertions(+), 2 deletions(-) diff --git a/src/trans/x64.rs b/src/trans/x64.rs index 6cfa161..b1bdaf3 100644 --- a/src/trans/x64.rs +++ b/src/trans/x64.rs @@ -1,4 +1,4 @@ -use crate::trans::{FnName, Func, Program}; +use crate::trans::{Code, FnName, Func, Program, SsaName, Var}; use std::{ fmt, io::{self, Write}, @@ -8,15 +8,18 @@ use std::{ pub enum Label { Global(u32), Function(FnName), + Extern(&'static str), + Builtin(&'static str), } #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] pub enum Addr { Rip(Label), - Off(Reg, u32), + Off(Reg, i32), } #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +#[allow(unused)] pub enum Reg { Rax, Rbx, @@ -42,6 +45,11 @@ pub enum Inst { Load(Reg, Addr), Store(Addr, Reg), Mov(Reg, Reg), + Imm(Reg, i64), + Lea(Reg, Addr), + Call(Label), + Add(Reg, u32), + Sub(Reg, u32), Pop(Reg), Ret, } @@ -71,14 +79,26 @@ pub fn write_compile(out: &mut impl Write, prog: &Program) -> io::Result<()> { _start: sub rsp, 15 and spl, 0xF0 + + lea rdi, [rip + ivy_builtin$0] + mov rsi, 1 + mov rdx, 0 + call _ivy_make_lam + mov [rip + IVY_GLOBAL$0], rax + call {} mov rdi, 0 call _ivy_exit + +ivy_builtin$0: + mov rdi, [rdi + 24] + jmp _ivy_debug "#, entry )?; for defn in defns { writeln!(out, "{}", defn)?; + writeln!(out)?; } Ok(()) } @@ -91,6 +111,7 @@ pub fn compile(prog: &Program) -> (Label, Vec, Vec) { name: Label::Global(global), value: 0, }) + .chain(Some(Global { name: Label::Global(0), value: 0 })) .collect(); let defns = prog .functions @@ -100,8 +121,92 @@ pub fn compile(prog: &Program) -> (Label, Vec, Vec) { (Label::Function(prog.top), globals, defns) } +fn even_up(x: usize) -> usize { + x + (x & 1) +} + fn compile_func(prog: &Program, func: &Func) -> Definition { + fn stack(x: &SsaName) -> Addr { + Addr::Off(Reg::Rsp, x.0 as i32 * 8) + } + + const HEADER_SIZE: i32 = 0x18; + + fn param(x: u16) -> Addr { + Addr::Off(Reg::Rbx, HEADER_SIZE + x as i32 * 8) + } + + let upvar = move |x: u16| { + let params = func.params as i32 * 8; + Addr::Off(Reg::Rbx, HEADER_SIZE + params + x as i32 * 8) + }; + let mut body = Vec::new(); + let stack_slots = even_up(func.order.len()); + body.push(Inst::Push(Reg::Rbx)); + body.push(Inst::Mov(Reg::Rbx, Reg::Rdi)); + body.push(Inst::Sub(Reg::Rsp, stack_slots as u32 * 8)); + for ssa in &func.order { + match &func.block[ssa] { + Code::Load(Var::Global(x)) => { + body.push(Inst::Load(Reg::Rax, Addr::Rip(Label::Global(*x)))); + body.push(Inst::Store(stack(ssa), Reg::Rax)); + } + Code::Load(Var::Param(x)) => { + body.push(Inst::Load(Reg::Rax, param(*x))); + body.push(Inst::Store(stack(ssa), Reg::Rax)); + } + Code::Load(Var::Upvar(x)) => { + body.push(Inst::Load(Reg::Rax, upvar(*x))); + body.push(Inst::Store(stack(ssa), Reg::Rax)); + } + Code::Load(Var::Ssa(ssa2)) => { + body.push(Inst::Load(Reg::Rax, stack(ssa2))); + body.push(Inst::Store(stack(ssa), Reg::Rax)); + } + Code::StoreGlobal(x, s) => { + body.push(Inst::Load(Reg::Rax, stack(s))); + body.push(Inst::Store(Addr::Rip(Label::Global(*x)), Reg::Rax)); + } + Code::MakeLam { + name, + upvars, + params, + } => { + body.push(Inst::Lea(Reg::Rdi, Addr::Rip(Label::Function(*name)))); + body.push(Inst::Imm(Reg::Rsi, *params as i64)); + body.push(Inst::Imm(Reg::Rdx, upvars.len() as i64)); + body.push(Inst::Call(Label::Extern("_ivy_make_lam"))); + // @TODO: Implement copying in closure captures + assert!(upvars.is_empty()); + body.push(Inst::Store(stack(ssa), Reg::Rax)); + } + Code::App(terms) => { + let mut terms = terms.iter(); + body.push(Inst::Load( + Reg::Rdi, + stack(terms.next().expect("a function to apply")), + )); + match terms.next() { + Some(s) => body.push(Inst::Load(Reg::Rsi, stack(s))), + None => body.push(Inst::Imm(Reg::Rsi, 0)), + } + body.push(Inst::Call(Label::Extern("_ivy_app"))); + while let Some(term) = terms.next() { + body.push(Inst::Mov(Reg::Rdi, Reg::Rax)); + body.push(Inst::Load(Reg::Rsi, stack(term))); + body.push(Inst::Call(Label::Extern("_ivy_app_mut"))); + } + body.push(Inst::Store(stack(ssa), Reg::Rax)); + } + Code::Num(n) => { + body.push(Inst::Imm(Reg::Rax, (n << 1) | 1i64)); + body.push(Inst::Store(stack(ssa), Reg::Rax)); + } + } + } + body.push(Inst::Add(Reg::Rsp, stack_slots as u32 * 8)); + body.push(Inst::Pop(Reg::Rbx)); body.push(Inst::Ret); Definition { name: Label::Function(func.name), @@ -136,6 +241,8 @@ impl fmt::Display for Label { match self { Label::Global(g) => write!(fmt, "IVY_GLOBAL${}", g), Label::Function(f) => write!(fmt, "ivy_fn${}", f.0), + Label::Extern(l) => write!(fmt, "{}", l), + Label::Builtin(l) => write!(fmt, "ivy_builtin${}", l), } } } @@ -163,11 +270,28 @@ impl fmt::Display for Reg { } } +impl fmt::Display for Addr { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + match self { + Addr::Rip(l) => write!(fmt, "[rip + {}]", l), + Addr::Off(r, o) => write!(fmt, "[{} + {}]", r, o), + } + } +} + impl fmt::Display for Inst { fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { match self { Inst::Push(r) => write!(fmt, "push {}", r), Inst::Pop(r) => write!(fmt, "pop {}", r), + Inst::Mov(d, s) => write!(fmt, "mov {}, {}", d, s), + Inst::Load(r, a) => write!(fmt, "mov {}, {}", r, a), + Inst::Store(a, r) => write!(fmt, "mov {}, {}", a, r), + Inst::Imm(r, i) => write!(fmt, "mov {}, {}", r, i), + Inst::Lea(r, a) => write!(fmt, "lea {}, {}", r, a), + Inst::Call(l) => write!(fmt, "call {}", l), + Inst::Add(r, x) => write!(fmt, "add {}, {}", r, x), + Inst::Sub(r, x) => write!(fmt, "sub {}, {}", r, x), Inst::Ret => write!(fmt, "ret"), inst => write!(fmt, "{:?}", inst), } -- 2.43.2