From 4359f2bcbd685b9b142dc4b1a4bf73318d9dfc32 Mon Sep 17 00:00:00 2001 From: Cassie Jones Date: Sat, 29 Feb 2020 16:21:48 +0100 Subject: [PATCH] Add the target-independent trans module This handles translation of the AST to an SSA form. Currently not doing any control flow constructs inside a function, so functions just have a single basic block with linear SSA. This does some basic load forwarding and de-duplication optimizations since they're straightforward. The most important effect here is translating the globally resolved names into offsets into the closure record, and listing the variables that need to be copied into constructed closures. --- sixty-four.vy | 9 ++ src/ast.rs | 2 +- src/main.rs | 15 ++- src/trans.rs | 267 ++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 289 insertions(+), 4 deletions(-) create mode 100644 sixty-four.vy create mode 100644 src/trans.rs diff --git a/sixty-four.vy b/sixty-four.vy new file mode 100644 index 0000000..d17d061 --- /dev/null +++ b/sixty-four.vy @@ -0,0 +1,9 @@ +(let ( + [zero (lam (f x) x)] + [succ (lam (n f x) (f (n f x)))] + [add (lam (m n f x) (m f (n f x)))] + [mul (lam (m n f x) (m (n f) x))] + [two (succ (succ zero))] + [four (add two two)] + [_64 (mul (mul four four) four)] +) (_64 debug zero)) diff --git a/src/ast.rs b/src/ast.rs index 29c0562..61ae779 100644 --- a/src/ast.rs +++ b/src/ast.rs @@ -6,7 +6,7 @@ use std::{ sync::atomic::{AtomicU32, Ordering}, }; -#[derive(PartialEq, Eq, Clone, Copy, Debug)] +#[derive(Hash, PartialEq, Eq, Clone, Copy, Debug)] pub enum Name { Local(u32), Global(u32), diff --git a/src/main.rs b/src/main.rs index 6ab7bb1..65164d8 100644 --- a/src/main.rs +++ b/src/main.rs @@ -2,7 +2,10 @@ 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)?; @@ -13,7 +16,7 @@ fn parse(input: &str) -> Result { } static BUILTINS: &[&str] = &[ - "true", "false", "<", ">", "<=", ">=", "==", "!=", "+", "-", "*", "/", "%", + "debug", "true", "false", "<", ">", "<=", ">=", "==", "!=", "+", "-", "*", "/", "%", ]; fn main() -> io::Result<()> { @@ -34,7 +37,13 @@ fn main() -> io::Result<()> { std::process::exit(1); } }; - println!("builtins: {:?}", builtins); - println!("{}", ast.to_doc().pretty(80)); + let code = match translate(&ast) { + Ok(code) => code, + Err(err) => { + println!("{}", err); + std::process::exit(1); + } + }; + println!("{:#?}", code); Ok(()) } diff --git a/src/trans.rs b/src/trans.rs new file mode 100644 index 0000000..234229f --- /dev/null +++ b/src/trans.rs @@ -0,0 +1,267 @@ +use crate::ast::{self, Ast}; +use std::{ + collections::{HashMap, HashSet}, + fmt, +}; + +#[derive(Hash, PartialEq, Eq, Clone, Copy)] +pub struct FnName(u32); + +#[derive(Hash, PartialEq, Eq, Clone, Copy)] +pub struct SsaName(u32); + +#[derive(Hash, PartialEq, Eq, Clone, Copy)] +pub enum Var { + Global(u32), + Param(u16), + Upvar(u16), + Ssa(SsaName), +} + +#[derive(PartialEq, Eq, Clone)] +pub enum Code { + Load(Var), + StoreGlobal(u32, SsaName), + MakeLam { + name: FnName, + upvars: Vec, + params: u16, + }, + App(Vec), + Num(i64), +} + +#[derive(Debug, PartialEq, Eq, Clone)] +pub struct Program { + globals: HashSet, + functions: HashMap, + top: FnName, + fresh: u32, +} + +impl Program { + fn fresh(&mut self) -> u32 { + let res = self.fresh; + self.fresh += 1; + res + } +} + +#[derive(PartialEq, Eq, Clone)] +pub struct Func { + name: FnName, + result: SsaName, + params: u16, + block: HashMap, + order: Vec, + fresh: u32, +} + +impl Func { + fn fresh_ssa(&mut self) -> SsaName { + let fresh = SsaName(self.fresh); + self.fresh += 1; + fresh + } +} + +struct Env { + mapping: HashMap, +} + +impl Env { + fn resolve(&self, name: &ast::Name) -> Option { + self.mapping.get(&name).copied().or_else(|| match name { + ast::Name::Global(x) => Some(Var::Global(*x)), + _ => None, + }) + } +} + +pub fn translate(ast: &Ast) -> Result { + let mut prog = Program { + globals: HashSet::new(), + functions: HashMap::new(), + top: FnName(0), + fresh: 0, + }; + let mut env = Env { + mapping: HashMap::new(), + }; + let func = make_func(0, &mut prog, &mut env, ast)?; + prog.top = func.name; + prog.functions.insert(func.name, func); + Ok(prog) +} + +fn make_func(params: u16, prog: &mut Program, env: &mut Env, ast: &Ast) -> Result { + let mut func = Func { + name: FnName(prog.fresh()), + result: SsaName(0), + params, + block: HashMap::new(), + order: Vec::new(), + fresh: 0, + }; + func.result = trans_expr(prog, env, &mut func, ast)?; + Ok(func) +} + +fn trans_expr( + prog: &mut Program, + env: &mut Env, + func: &mut Func, + ast: &Ast, +) -> Result { + match ast { + Ast::Let(binds, body) => { + for (name, init) in binds { + let ssa = trans_expr(prog, env, func, init)?; + if let ast::Name::Global(g) = name { + let ssa2 = func.fresh_ssa(); + prog.globals.insert(*g); + func.block.insert(ssa2, Code::StoreGlobal(*g, ssa)); + func.order.push(ssa2); + } + // Inserting this unconditionally means that lookups within the + // local function will see the SSA name, and potentially avoid + // having to do a lookup on a global. + env.mapping.insert(*name, Var::Ssa(ssa)); + } + trans_expr(prog, env, func, body) + } + Ast::Lam { + binds, + upvars, + body, + } => { + let mut new_env = Env { + mapping: HashMap::with_capacity(binds.len() + upvars.len()), + }; + for (i, &name) in binds.iter().enumerate() { + new_env.mapping.insert(name, Var::Param(i as u16)); + } + for (i, &name) in upvars.iter().enumerate() { + new_env.mapping.insert(name, Var::Upvar(i as u16)); + } + let new_func = make_func(binds.len() as u16, prog, &mut new_env, body)?; + let ssa = func.fresh_ssa(); + let upvars = upvars + .iter() + .map(|var| { + let ssa = func.fresh_ssa(); + let load = Code::Load( + env.resolve(var) + .ok_or_else(|| format!("Unable to resolve variable {:?}", var))?, + ); + func.block.insert(ssa, load); + func.order.push(ssa); + Ok(ssa) + }) + .collect::>()?; + func.block.insert( + ssa, + Code::MakeLam { + name: new_func.name, + upvars, + params: binds.len() as u16, + }, + ); + func.order.push(ssa); + prog.functions.insert(new_func.name, new_func); + Ok(ssa) + } + Ast::App(terms) => { + let terms = terms + .iter() + .map(|term| trans_expr(prog, env, func, term)) + .collect::>()?; + let ssa = func.fresh_ssa(); + func.block.insert(ssa, Code::App(terms)); + func.order.push(ssa); + Ok(ssa) + } + Ast::Var(name) => { + match env.resolve(name) { + // Forwarding SSA variables skips unnecessary loads + Some(Var::Ssa(ssa)) => Ok(ssa), + Some(var) => { + let ssa = func.fresh_ssa(); + func.block.insert(ssa, Code::Load(var)); + // Inserting the result of the lookup into the environment deduplicates loads. + env.mapping.insert(*name, Var::Ssa(ssa)); + func.order.push(ssa); + Ok(ssa) + } + None => Err(format!("Unable to resolve variable {:?}", name)), + } + } + Ast::Num(n) => { + let ssa = func.fresh_ssa(); + func.block.insert(ssa, Code::Num(*n)); + func.order.push(ssa); + Ok(ssa) + } + } +} + +impl fmt::Debug for FnName { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + write!(fmt, "@fn{}", self.0) + } +} + +impl fmt::Debug for SsaName { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + write!(fmt, "%{}", self.0) + } +} + +impl fmt::Debug for Var { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + match *self { + Var::Global(x) => write!(fmt, "@{}", x), + Var::Param(x) => write!(fmt, "p{}", x), + Var::Upvar(x) => write!(fmt, "c{}", x), + Var::Ssa(x) => write!(fmt, "{:?}", x), + } + } +} + +impl fmt::Debug for Code { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + match self { + Code::Load(var) => write!(fmt, "load {:?}", var), + Code::StoreGlobal(g, ssa) => write!(fmt, "store [{:?}] = {:?}", Var::Global(*g), ssa), + Code::MakeLam { + name, + upvars, + params, + } => { + write!(fmt, "lam {:?} ({}) [", name, params)?; + for up in upvars { + write!(fmt, "{:?} ", up)?; + } + write!(fmt, "]") + } + Code::App(args) => { + write!(fmt, "app (")?; + for arg in args { + write!(fmt, "{:?} ", arg)?; + } + write!(fmt, ")") + } + Code::Num(n) => write!(fmt, "{}", n), + } + } +} + +impl fmt::Debug for Func { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + write!(fmt, "fn {:?} ({}) ", self.name, self.params)?; + fmt.debug_map() + .entries(self.order.iter().map(|x| (x, &self.block[x]))) + .entry(&"ret", &self.result) + .finish() + } +} -- 2.47.0