Witch of Git - ivy/blob - src/trans/x64.rs

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