Witch of Git - ivy/blob - 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 }