path: root / website / content / slides / 11_jit / _index.md

---
title: "Just-in-time compilation"
date: 2020-12-05T17:45:53+03:00
draft: false
outputs: ["Reveal"]
---

# Just-In-Time compilation

---
## Why

- Interpreters are slow
- Flexibility
- Optimization

---
### Interpreters

Adding two numbers in an interpreter requires:

1. loading the instruction
2. decoding the intstruction
3. dispatching the opcode
4. doing the addition
5. storing the result

All is actually 2 instructions on a x86_64 CPU

    ; rax = rbx + rcx
    mov rax, rbx
    add rax, rcx

---
### Flexibility

- generate native code only for functions that will affect performance
- generate for the actual target CPU, instead of distributting prebuilt binaries

---
### Optimization

- All function arguments can be treated as contants
  - constant propagation everywhere
- unroll loops
- remove branches
- remove runtime dispatches (virtual methods)
- remove property lookups

---
## What we need

- Executable memory
- Generate code
- Execute code

---
### Executable memory

- Why
- Security concerns

---
### Create executable memory Linux

    virtualCodeAddress = mmap(
           NULL,
           codeBytes,
           PROT_READ | PROT_WRITE | PROT_EXEC,
           MAP_ANONYMOUS | MAP_PRIVATE,
           0,
           0);

---
### Create executable memory Windows

    auto const buffer = VirtualAlloc(nullptr, page_size, MEM_COMMIT, PAGE_READWRITE);
    VirtualProtect(buffer, code.size(), PAGE_EXECUTE_READ, &dummy);

---
### Create executable memory other platforms

- Consoles
- Mobile
- Pic

---
### How to create and execute code

    typedef unsigned (*asmFunc)(void);

    unsigned char * memory = (unsigned char *) (virtualCodeAddress);
    // mov %rdi, %rax
    memory[i++] = 0x48;           // REX.W prefix
    memory[i++] = 0x8b;           // MOV opcode, register/register
    memory[i++] = 0xc7;           // MOD/RM byte for %rdi -> %rax
    // ret
    memory[i++] = 0xc3;           // RET opcode
    ((asmFunc) (virtualCodeAddress))();

---
### Generate code

- Code generation takes time.
- The more optimized code, the more time it takes

---
#### JIT tiers

Most VMs have tiers that allow to trade off between latency and throughput.

- _latency_ - how soon the VM starts executing your code
- _thoughput_ - how fast the VM executes your code

---
#### JIT tiers

VMs have more than two tiers, but they are levels between the two extremes

- baseline
  - no optimizations
  - can handle everypossible type
  - profiling code to detect what needs to optimization and how to optimize it
- optimized
  - highly specialized for certain types and parameters
  - fallbacks when it can't handle the provided types or parameters

---
#### Template JIT

Every opcode can be translated to machine code snippet, possibly with changeable
registers for inputs and outputs.

- can work on the AST level as well, no explicit need for bytecode

---
#### Template JIT

The program can be translated to machine code by concatenating all the snippets
for the opcodes, possibly with other snippets that make sure that input and
output registers are matching.

---
#### Full scale compiler

- SSA
- Constant propagation
- Register allocation
- Compiler optimizations
  - branch elimination
  - loop unrolling
  - inlining
  - vectorization
  - de-virtualization
  - ...

---
#### Template JIT

    function add_answer(x) {
        return x + 42;
    }

---
##### Spasm

    func add_answer
    const 1, 42
    add 2, -1, 1
    ret 2

---
##### x86_64

    add_answer(int):
        push    rbp # save the current call frame
        mov     rbp, rsp # create a new call frame
        mov     dword ptr [rbp - 4], edi # spill first argument to stack
        mov     eax, dword ptr [rbp - 4]
        add     eax, 42
        pop     rbp # clean up our frame
        ret


---
##### JIT

    ASM prolog() {
        return ASM(["push rbp", "mov rbp, rsp"]);
    }

    ASM add(Reg a0, Reg a1, Reg a2) {
        return ASM(["mov a0, a1", "add a0, a2"]).set(a0, a1, a2);
    }

---
##### Optimized

    add_answer(int):
        lea     eax, [rdi + 42]
        ret

---
##### Floating point

    .LCPI0_0:
            .long   0x42280000
    add_answer(float):
        push    rbp
        mov     rbp, rsp
        movaps  xmm1, xmm0
        movss   xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        movss   dword ptr [rbp - 4], xmm1
        addss   xmm0, dword ptr [rbp - 4]
        pop     rbp
        ret

---
### Calling convention

- Standard
  - allows easier calling into functions compiled in the runtime or existing
    libraries
- Custom
  - allows easier mapping into the language and VM implementation

---
### FFI

Foreign Function Interface

FFI allows calls from the VM to functions in existing libraries, written in
other languages, most importantly C and OS functions.

---
#### To x86_64 and back

Translate Spasm calling convention to x86_64 and back

> For simplicity, lets assume that spasm works with integer numbers instead of
> floating point.


---
#### X86_64 calling convention

- depends on OS - MS Windows is different from the rest
- System V AMD64 APIB
    - Pass first six integer arguments into `RDI`, `RSI`, `RDX`, `RCX`, `R8`,
      `R9`
    - Result into `RAX`

---
##### Prolog

- push all arguments passed through registers onto the stack
- push the number of arguments on to the stack
- set `RDX` to point to the top of the stack

---
##### Operation

- Push new registers onto the stack as they are created
- Make all the opcode JIT code work with `RCX`, `R8` and `R9`

- Translate Spasm negative registers to positive offsets from `RDX`
  - make sure to skip `rbp`, `r15` stored on the stack
- Translate Spasm positive registeers to negative offsets from `RDX`

> The native stack grows towards lower addresses!

---
##### Operaton

For each opcode
1. Move its operands from stack to `RCX`, `R8`, `R9`
2. Insert the machine code for the opcode
3. Move the result from `RCX` to the spasm register on the stack

---
##### Epilog

- move from spasm result register to `rax`
- restore the stack frame
- `ret`

---
##### ?

How to handle vararg functions?

---

---
##### Spasm

    func add_answer
    const 1, 42
    add 2, -1, 1
    ret 2

---
#### JIT - Prolog

    push    rbp # save the current call frame
    mov     rbp, rsp # create a new call frame
    push    r15
    mov     r15, rsp # keep the stack pointer (or do lots of pop in the end)
    push    r9
    push    r8
    push    rcx
    push    rdx
    push    rsi
    push    rdi
    push    1
    mov     rdi, rsp

---
##### JIT - Body

    mov [rdi - 8], 42 # 8 -> sizeof(vm_value) # const 1, 42

    mov r8, [rdi + 8] # load operands
    mov r9, [rdi - 8]

    mov rcx, r8 # add
    add rcx, r9

    mov [rdi + 16], rcx # store result

---
##### JIT - Epilog

    mov eax, [rdi + 16]
    mov rsp, r15
    pop r15
    pop rbp
    ret


---
#### Code generators

- [LLVM](https://llvm.org/docs/ORCv2.html)
- [PeachPy](https://pypi.org/project/PeachPy/)
- [DynASM](https://corsix.github.io/dynasm-doc/index.html)
- [GNU lightning](https://www.gnu.org/software/lightning/)
  - [docs](https://www.gnu.org/software/lightning/manual/lightning.html)
- [LibJIT](https://www.gnu.org/software/libjit/)

---
# ?