From a4e0f19757a4d01f847dc2128ac28705f20c8f0f Mon Sep 17 00:00:00 2001 From: Cassie Jones Date: Sun, 1 Mar 2020 01:48:44 +0100 Subject: [PATCH] Add an extensible framework for adding built-ins Now builtins can be written in assembly at the bottom, and they'll be included and registered in the entry point on-demand by the program. Only functions that are referenced will be included in the output. This will need to be extended to handle functions which reference other functions (like the handling of "true" and "false" if any of the comparisons are included), but that's a matter of front-end changes. --- src/ast.rs | 9 ++++-- src/lib.rs | 16 ++++++++++ src/main.rs | 25 +++------------ src/trans.rs | 13 +++++--- src/trans/x64.rs | 80 +++++++++++++++++++++++++++++++++++++++--------- 5 files changed, 100 insertions(+), 43 deletions(-) create mode 100644 src/lib.rs diff --git a/src/ast.rs b/src/ast.rs index 61ae779..60d3b97 100644 --- a/src/ast.rs +++ b/src/ast.rs @@ -19,9 +19,14 @@ impl Name { Name::Global(_) => false, } } -} -impl Name { + pub fn global_number(&self) -> Option { + match self { + Name::Local(_) => None, + Name::Global(g) => Some(*g), + } + } + fn to_doc(&self) -> RcDoc { match self { Name::Local(n) => RcDoc::text(format!("x{}", n)), diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..955e63d --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,16 @@ +use ess::{self, parser::ParseError, Sexp}; + +pub mod ast; +pub mod trans; + +pub fn parse(input: &str) -> Result { + let (sexp, rest) = ess::parse_one(input)?; + if !rest.trim().is_empty() { + return Err(ParseError::Unexpected('\0', sexp.get_loc().1)); + } + Ok(sexp) +} + +pub static BUILTINS: &[&str] = &[ + "debug", "true", "false", "<", ">", "<=", ">=", "==", "!=", "+", "-", "*", "/", "%", +]; diff --git a/src/main.rs b/src/main.rs index 19d9392..1e6374a 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,23 +1,5 @@ -use ess::{self, parser::ParseError, Sexp}; use std::io::{self, Read}; - -mod ast; -mod trans; - -use ast::Ast; -use trans::translate; - -fn parse(input: &str) -> Result { - let (sexp, rest) = ess::parse_one(input)?; - if !rest.trim().is_empty() { - return Err(ParseError::Unexpected('\0', sexp.get_loc().1)); - } - Ok(sexp) -} - -static BUILTINS: &[&str] = &[ - "debug", "true", "false", "<", ">", "<=", ">=", "==", "!=", "+", "-", "*", "/", "%", -]; +use ivy::{parse, BUILTINS, ast::Ast, trans::{self, translate}}; fn main() -> io::Result<()> { let stdin = std::io::stdin(); @@ -30,7 +12,7 @@ fn main() -> io::Result<()> { std::process::exit(1); } }; - let (ast, builtins) = match Ast::parse(BUILTINS, &sexp) { + let (ast, mut builtins) = match Ast::parse(BUILTINS, &sexp) { Ok(ast) => ast, Err(err) => { println!("{}", err); @@ -44,7 +26,8 @@ fn main() -> io::Result<()> { std::process::exit(1); } }; + builtins.retain(|_, v| code.globals.contains(&v.global_number().unwrap())); let stdout = std::io::stdout(); - trans::x64::write_compile(&mut stdout.lock(), &code)?; + trans::x64::write_compile(&builtins, &mut stdout.lock(), &code)?; Ok(()) } diff --git a/src/trans.rs b/src/trans.rs index 5ded82e..c518197 100644 --- a/src/trans.rs +++ b/src/trans.rs @@ -35,7 +35,7 @@ pub enum Code { #[derive(Debug, PartialEq, Eq, Clone)] pub struct Program { - globals: HashSet, + pub globals: HashSet, functions: HashMap, top: FnName, fresh: u32, @@ -152,10 +152,10 @@ fn trans_expr( .iter() .map(|var| { let ssa = func.fresh_ssa(); - let load = Code::Load( - env.resolve(var) - .ok_or_else(|| format!("Unable to resolve variable {:?}", var))?, - ); + let resolved = env + .resolve(var) + .ok_or_else(|| format!("Unable to resolve variable {:?}", var))?; + let load = Code::Load(resolved); func.block.insert(ssa, load); func.order.push(ssa); Ok(ssa) @@ -188,6 +188,9 @@ fn trans_expr( // Forwarding SSA variables skips unnecessary loads Some(Var::Ssa(ssa)) => Ok(ssa), Some(var) => { + if let Var::Global(g) = var { + prog.globals.insert(g); + } let ssa = func.fresh_ssa(); func.block.insert(ssa, Code::Load(var)); // Inserting the result of the lookup into the environment deduplicates loads. diff --git a/src/trans/x64.rs b/src/trans/x64.rs index b1bdaf3..f2dd634 100644 --- a/src/trans/x64.rs +++ b/src/trans/x64.rs @@ -1,6 +1,9 @@ use crate::trans::{Code, FnName, Func, Program, SsaName, Var}; +use crate::ast; use std::{ + borrow::Cow, fmt, + collections::HashMap, io::{self, Write}, }; @@ -48,6 +51,7 @@ pub enum Inst { Imm(Reg, i64), Lea(Reg, Addr), Call(Label), + Jmp(Label), Add(Reg, u32), Sub(Reg, u32), Pop(Reg), @@ -57,7 +61,7 @@ pub enum Inst { #[derive(Debug, Clone, PartialEq, Eq, Hash)] pub struct Definition { name: Label, - body: Vec, + body: Cow<'static, [Inst]>, } pub struct Global { @@ -65,8 +69,32 @@ pub struct Global { value: i64, } -pub fn write_compile(out: &mut impl Write, prog: &Program) -> io::Result<()> { +pub fn write_compile( + builtins: &HashMap, + out: &mut impl Write, + prog: &Program, +) -> io::Result<()> { let (entry, globals, defns) = compile(&prog); + struct Entry { + number: u32, + defn: Definition, + params: u16, + } + let builtins = builtins + .iter() + .map(|(name, id)| { + let number = id.global_number().unwrap(); + let (params, name, code) = builtin(&name); + Entry { + number, + defn: Definition { + name: Label::Builtin(name), + body: Cow::Borrowed(code), + }, + params, + } + }) + .collect::>(); writeln!(out, ".data")?; for global in globals { writeln!(out, "{}", global)?; @@ -78,24 +106,37 @@ pub fn write_compile(out: &mut impl Write, prog: &Program) -> io::Result<()> { .global _start _start: sub rsp, 15 - and spl, 0xF0 + and spl, 0xF0"# + )?; - lea rdi, [rip + ivy_builtin$0] - mov rsi, 1 + for builtin in &builtins { + writeln!( + out, + r#" + lea rdi, [rip + {}] + mov rsi, {} mov rdx, 0 call _ivy_make_lam - mov [rip + IVY_GLOBAL$0], rax + mov [rip + {}], rax"#, + builtin.defn.name, + builtin.params, + Label::Global(builtin.number), + )?; + } + writeln!( + out, + r#" call {} mov rdi, 0 call _ivy_exit - -ivy_builtin$0: - mov rdi, [rdi + 24] - jmp _ivy_debug "#, entry )?; + for builtin in &builtins { + writeln!(out, "{}", builtin.defn)?; + writeln!(out)?; + } for defn in defns { writeln!(out, "{}", defn)?; writeln!(out)?; @@ -111,12 +152,11 @@ 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 .values() - .map(|func| compile_func(prog, func)) + .map(|func| compile_func(func)) .collect(); (Label::Function(prog.top), globals, defns) } @@ -125,7 +165,7 @@ fn even_up(x: usize) -> usize { x + (x & 1) } -fn compile_func(prog: &Program, func: &Func) -> Definition { +fn compile_func(func: &Func) -> Definition { fn stack(x: &SsaName) -> Addr { Addr::Off(Reg::Rsp, x.0 as i32 * 8) } @@ -210,7 +250,7 @@ fn compile_func(prog: &Program, func: &Func) -> Definition { body.push(Inst::Ret); Definition { name: Label::Function(func.name), - body, + body: Cow::Owned(body), } } @@ -290,10 +330,20 @@ impl fmt::Display for Inst { 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::Jmp(l) => write!(fmt, "jmp {}", 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), } } } + +fn builtin(name: &str) -> (u16, &'static str, &'static [Inst]) { + match name { + "debug" => (1, "debug", &[ + Inst::Load(Reg::Rdi, Addr::Off(Reg::Rdi, 0x18)), + Inst::Jmp(Label::Extern("_ivy_debug")), + ]), + name => panic!("Unsupported builtin '{}' for x64", name), + } +} -- 2.47.0