Skip to content

Instantly share code, notes, and snippets.

@kayceesrk

kayceesrk/ocaml-native.md

Last active March 28, 2023 06:19
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kayceesrk/002822b2b7b11e928789 to your computer and use it in GitHub Desktop.
Save kayceesrk/002822b2b7b11e928789 to your computer and use it in GitHub Desktop.
Download ZIP
OCaml native code notes
Raw
ocaml-native.md

Concurrency primitives

Signature

(* raw continuation *)
type ('a,'b) stack
perform  : 'a eff -> 'a
resume   : ('a,'b) stack -> ('c -> 'a) -> 'c -> 'b
delegate : 'a eff -> ('a,'b) stack -> 'b

type ('c,'b) hval = 'c -> 'b
type 'b hexn = exn -> 'b
type ('c,'b) heff = 'c effect -> ('c,'b) stack -> 'b
caml_alloc_stack : ('c,'b) hval -> 'b hexn -> ('c,'b) heff -> ('a,'b) stack

Arity

perform : 1
resume : 3
delegate : 2

Stack layout at caml_start_program (vanilla amd64)

caml_start_program is used both to start execution of the main OCaml code as well as for callbacks from C to OCaml. The interface has the following stack layout:

       +--------------+
       |              |
       /     OCaml    /
+----->/     frames   / (* Only if Callback from C *)
|      /              /
|      |              |
|  +-->+--------------+
|  |   |              |
|  |   /       C      /
|  |   /     frames   / (* Arbitrary size *)
|  |   /              /
|  |   |              |
|  |   +--------------+ <-- top of caml_start_program
|  |   |    gc_regs   | (* Pointer to register block *)
|  |   +--------------+
|  |   | last_retaddr | (* last return address in OCaml Code. == 1 if not callback *)
|  |   +--------------+
|  +---|  bot_of_stk  | (* beginning of the OCaml stack chunk *)
|      +--------------+
|      |    exn_ip    | (* instruction pointer for the exception handler; a catch-all exception handler *)
|      +--------------+
+------|    exn_ptr   | (* exception pointer of previous handler *)
       +--------------+ <-- bottom of caml_start_program
       |  return_addr | (* amd64.S:LBL(107) *)
       +--------------+
       |              |
       /     OCaml    /
       /     frames   / 
       /              /
       |              |
       +--------------+

Bytecode stack layout

Stack grows downward from high to low. The address Stack_high(stack) > Stack_base(stack).

+------------+ <-- Stack_high(stack)
|            |
/    valid   /
/   frames   / (* Arbitrary size *)
/            /
/~~~~~~~~~~~~/ <-- sp
/            /
/   garbage  /
|            |
+------------+ <-- Stack_threshold(stack)
|            |
/  reserved  / (* 16 words *)
|            |
+------------+ <-- Stack_base(stack)
|   parent   |
+------------+
|    heff    |
+------------+
|    hexn    |
+------------+
|    hval    |
+------------+
|   dirty    |
+------------+ 
|     sp     | 
+------------+ <-- stack

sp value is valid when the stack is not active i.e, stack is a continuation. dirty is true if the stack needs to be scanned by the GC; signifies that the stack has been mutated since the last GC. hval/hexn/heff is the closure for handler returning value/exception/effect. parent is the pointer to the parent stack.

ABI: Unix on x86-64

C Calling convention

Arguments

integer arguments (in order): %rdi, %rsi, %rdx, %rcx, %r8, %r9
floating point arguments: %xmm0–%xmm7

Return

integer: %rax, %rdx
floating point: %xmm0, %xmm1

Callee-saved registers (preserved across calls)

%rbx, %rbp, %r12-r15

For more information, see [2].

OCaml Calling convention

No callee-saved registers

This is makes exception handlers really cheap. There is no need to save registers when entering a try block other than saving the stack pointer. Raising an exception just needs to restore the stack pointer. For the same reason, context switches become really cheap. There is no need to save registers when capturing a continuation. For more information, see [1].

Calling convention

The information has been gleaned from asmcomp/amd64/proc.ml.

Register map:  
    rax         0  
    rbx         1  
    rdi         2  
    rsi         3  
    rdx         4  
    rcx         5  
    r8          6  
    r9          7  
    r12         8  
    r13         9  
    rbp         12  
    r10         10  
    r11         11  
    r14         trap pointer  
    r15         allocation pointer  
    
    xmm0 - xmm15  100 - 115
  • rax - r13: OCaml function arguments (upto 10). Note that this is specifically different from what is described in [3] due to (PR#5707): r11 should not be used for parameter passing, as it can be destroyed by the dynamic loader according to SVR4 ABI. Linux's dynamic loader also destroys r10. The rest are passed on the stack, leftmost-first-in.
  • rax: OCaml function result
  • xmm0 - xmm9: OCaml floating-point function arguments
  • xmm0: OCaml floating-point function result

ABI: Unix on aarch64

OCaml calling convention

  • first integer args in r0...r15
  • first float args in d0...d15 remaining args on stack.
  • Return values in r0...r15 or d0...d15.

C calling convention

  • first integer args in r0...r7
  • first float args in d0...d7 remaining args on stack.
  • Return values in r0...r1 or d0.

Native codegen

Phases

  • Instruction selection (selection.ml)
  • Allocation combining (comballoc.ml)
  • CSE (CSE.ml)
  • Deadcode elimination / liveness analysis (deadcode.ml)
  • Register spilling (spill.ml)
  • Live range splitting (split.ml)
  • Linearization (liner.ml)
  • Instruction scheduling (scheduling.ml)
  • Emit (emit.ml)

Exceptions in native code

Exceptions in OCaml native builds upon the usual call/return semantics of the underlying machine. In particular, exception mechanism does not use setjmp()/longjmp(), becuase of OCaml's calling convention which does not use any callee saved registers. Hence, exceptional return can appear just like a return.

Setting up exception handler

  1. push exception code location. Assuming LBL(108) has the exception handler code, the first step is

    lea LBL(108)(%rip), %r13 pushq %r13

  2. push previous exception pointer. The exception pointer is maintained in %r14. Hence,

    push %r14

  3. save the new exception pointer. This is the current stack pointer. Hence,

    movq %rsp, %r14

Raising an exception

  1. unwind the stack. Since the exception pointer is maintained in %r14, simply perform

    movq %r14, %rsp

  2. restore the previous exception handler. Since the last thing that was pushed while setting up the exception handler is the previous exception pointer, just do

    popq %r14

  3. Now just return as if the function has returned.

    ret

The ret instruction pops the ip from the stack and jumps to it. Since this is now the exception pointer code, the exection continues at LBL(108).

[1] https://github.com/whitequark/ocaml-llvm-ng/blob/master/doc/abi.md
[2] www.x86-64.org/documentation/abi.pdf
[3] http://stackoverflow.com/questions/11322163/ocaml-calling-convention-is-this-an-accurate-summary

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment