[LLVMdev] ocaml+llvm

[Gordon Henriksen]

I'm hacking on an llvm backend for the ocaml language.

    http://caml.inria.fr/ocaml/

I'd like to solicit some advice regarding the constant data
structures that ocaml's runtime requires. Rewriting its runtime is
a non-goal.


The biggest problem is a data structure called the frame table, a
simple structure for which LLVM seems ill-prepared. For each call
site in the program, ocaml emits an entry into this table:

     key   : the return address of the call site
     value : the stack offset of every variable live after return

The garbage collector uses this when walking the stack to find
live objects.

                      -- frame table example --
This program will create 3 call sites. 2 are not interesting, but
the other will have 1 live root:

     example.ml:
     let keeplive x = "";;

     let heapobject = "hello " ^ "world" in
       print_endline heapobject;
       keeplive heapobject

The interesting call is print_endline heapobject. After the return
of this call, the root heapobject is still live, so the collector
must trace it. To instruct the runtime to do so, the ocaml
compiler emits the following assembly:

     from the program text in example.s:
         movl    %eax, 0(%esp)  ; save heapobject at 0(%esp)
         call    _camlPervasives__print_endline_298
     L103:                      ; mark call's return address

     from the frame table in example.s:
         .long    L103  ; "entry is for return address L103"
         .word    16    ; "entry is 16 bytes in length"
         .word    1     ; "1 gcroot follows"
         .word    0     ; "find a gcroot at 0(%esp)"

                              -- end --

The major challenges posed by the frame table are:

  1. Making a constant reference to a return address.
     - Labels are not global values, so ocamlopt's approach is a
       no-go.
     - Is llvm.pcmarker in any way useful? It couldn't present the
       correct address for a caller-save calling convention.
     - A constant expression like OFFSET + (intptr_t) FUNCTION can
       get the job done, but this requires instruction size
       computations which I can only find for ARM (in support of
       the constant island pass).

  2. Computing the static stack offset of the GC roots.
     - I'm not yet sure whether this is trivial or not.

Additionally:

  3. Identifying the roots live after each call site.
     - Trivially correct: include all llvm.gcroot'd allocas in the
       function.
     - Harder: analyze load/store dominance information vs. the
       call site to eliminate those roots which are not live.

  4. Identifying all return addresses.
     - I think trivial on the MachineFunction representation, but
       is it possible to relate the machine instructions back to
       the LLVM IR, where the liveness analysis must be performed?

  5. Update the frame table constant with information only
     available during codegen.
     - I'm thinking I should populate an on-the-side data structure
       during compilation, and only convert it to a Constant* and
       emit it during an epilogue pass using
       AsmPrinter::EmitGlobalConstant.

That's the doozy. Unfortunately, I think the runtime requirements
will preclude the use of the basic LLVM toolchain in conjunction
with LLVM ocamlopt, which is unfortunate.


The simpler problem is that each ocaml object exports symbols
bracketing its code and data. An ocaml object absent these symbols
cannot be linked into an executable.

     prologue from example.s:
         .data
         .globl  _camlExample__data_begin
     _camlExample__data_begin:
         .text
         .globl  _camlExample__code_begin
     _camlExample__code_begin:
         .data
         ; data follows
         .text
         ; code follows

     epilogue from example.s:
         .text
         .globl  _camlExample__code_end
     _camlExample__code_end:
         .data
         .globl  _camlExample__data_end
     _camlExample__data_end:
         .long 0

I think I should simply write prologue- and epilogue emitter
passes for this boilerplate. That avoids attempting to model these
quirky symbols in the LLVM IR, but again breaks llc compatibility.
Is there a better way?


Thanks,
Gordon


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070812/b763945c/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: example.ml
Type: application/octet-stream
Size: 112 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070812/b763945c/attachment.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070812/b763945c/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: example.s
Type: application/octet-stream
Size: 1493 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070812/b763945c/attachment-0001.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070812/b763945c/attachment-0002.html>