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