<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">
<div><span class="Apple-style-span" style="font-family: 'Courier New'; ">I'm hacking on an llvm backend for the ocaml language.</span></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="'Courier New'"> <a href="http://caml.inria.fr/ocaml/">http://caml.inria.fr/ocaml/</a></font></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; ">I'd like to solicit some advice regarding the constant data </span></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; ">structures that ocaml's runtime requires. Rewriting its runtime is</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; ">a non-goal.</span></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="'Courier New'">The biggest problem is a data structure called the frame table, a</font></div><div><font class="Apple-style-span" face="'Courier New'">simple structure for which LLVM seems ill-prepared. For each call </font></div><div><font class="Apple-style-span" face="'Courier New'">site in the program, ocaml emits an entry into this table:</font></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; "> key : the return address of the call site</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; "> value : the stack offset of every variable live after return</span></div><div><font class="Apple-style-span" face="Courier New"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="'Courier New'">The garbage collector uses this when walking the stack to find</font></div><div><font class="Apple-style-span" face="'Courier New'">live objects.</font></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="'Courier New'"><i> -- frame table example --</i></font></div><div><font class="Apple-style-span" face="Courier New">This program will create 3 call sites. 2 are not interesting, but </font></div><div><font class="Apple-style-span" face="Courier New">the other will have 1 live root:</font></div><div><div><font class="Apple-style-span" face="Courier New"><br class="webkit-block-placeholder"></font></div><div><div><font class="Apple-style-span" face="Courier New"> <b><i>example.ml</i>:</b></font></div><div><div><font class="Apple-style-span" face="Courier New"> let keeplive x = "";;</font></div><div><font class="Apple-style-span" face="Courier New"> </font></div><div><font class="Apple-style-span" face="Courier New"> let heapobject = "hello " ^ "world" in</font></div><div><font class="Apple-style-span" face="Courier New"> </font><font class="Apple-style-span" color="#FF0000"><font class="Apple-style-span" face="Courier New"><font class="Apple-style-span" color="#FF8000">print_endline</font> </font></font><font class="Apple-style-span" color="#0080FF"><font class="Apple-style-span" face="Courier New">heapobject</font></font><font class="Apple-style-span" face="Courier New">;</font></div><div><font class="Apple-style-span" face="Courier New"> keeplive heapobject</font></div><font class="Apple-style-span" face="Courier New"><br></font></div><div><font class="Apple-style-span" face="Courier New">The interesting call is </font><font class="Apple-style-span" color="#FF0000"><font class="Apple-style-span" face="Courier New"><font class="Apple-style-span" color="#FF8000">print_endline</font> </font></font><font class="Apple-style-span" color="#0080FF"><font class="Apple-style-span" face="Courier New">heapobject</font></font><font class="Apple-style-span" face="Courier New">. After the return </font></div><div><font class="Apple-style-span" face="Courier New">of this call, the root </font><span class="Apple-style-span" style="color: rgb(0, 128, 255); "><font class="Apple-style-span" face="Courier New">heapobject</font></span><font class="Apple-style-span" face="Courier New"> is still live, so the collector </font></div><div><font class="Apple-style-span" face="Courier New">must trace it. To instruct the runtime to do so, the ocaml </font></div><div><font class="Apple-style-span" face="Courier New">compiler emits the following assembly:</font></div><div><font class="Apple-style-span" face="Courier New"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="Courier New"> <b>from the program text in <i>example.s</i>:</b></font></div><div><div><div><span class="Apple-tab-span" style="white-space:pre"><span class="Apple-style-span" style="white-space: normal; "><font class="Apple-style-span" face="Courier New"> </font></span></span><font class="Apple-style-span" face="Courier New"> movl %eax, </font><font class="Apple-style-span" color="#0080FF"><font class="Apple-style-span" face="Courier New"><b>0</b></font></font><font class="Apple-style-span" color="#000000"><font class="Apple-style-span" face="Courier New">(%esp)</font><span class="Apple-style-span" style="color: rgb(179, 179, 179); "><font class="Apple-style-span" face="Courier New"> ; save heapobject at 0(%esp)</font></span></font></div><div><font class="Apple-style-span" face="Courier New"> call _camlPervasives__</font><font class="Apple-style-span" face="Courier New"><font class="Apple-style-span" color="#FF8000">print_endline</font></font><font class="Apple-style-span" face="Courier New">_298</font></div><div><font class="Apple-style-span" color="#008080"><span class="Apple-style-span" style="color: rgb(0, 0, 0); "><font class="Apple-style-span" face="Courier New"> </font></span><font class="Apple-style-span" face="Courier New"><b>L103</b></font></font><font class="Apple-style-span" face="Courier New">:<font class="Apple-style-span" color="#B3B3B3"> ; mark call's return address</font></font></div><font class="Apple-style-span" face="Courier New"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="Courier New"> <b>from the frame table in <i>example.s</i>:</b></font></div><div><font class="Apple-style-span" face="Courier New"> .long </font><font class="Apple-style-span" color="#008080"><font class="Apple-style-span" face="Courier New"> <b>L103</b></font><font class="Apple-style-span" color="#B3B3B3"><font class="Apple-style-span" face="Courier New"> ; "entry is for return address L103"</font></font></font></div><div><font class="Apple-style-span" face="Courier New"> .word 16</font><font class="Apple-style-span" color="#B3B3B3"><font class="Apple-style-span" face="Courier New"> ; "entry is 16 bytes in length"</font></font></div><div><font class="Apple-style-span" face="Courier New"> .word 1</font><font class="Apple-style-span" color="#B3B3B3"><font class="Apple-style-span" face="Courier New"> ; "1 gcroot follows"</font></font></div><div><font class="Apple-style-span" face="Courier New"> .word</font><font class="Apple-style-span" color="#0080FF"><span class="Apple-style-span" style="color: rgb(0, 0, 0); "><font class="Apple-style-span" face="Courier New"> </font><span class="Apple-style-span" style="color: rgb(0, 128, 255); "><font class="Apple-style-span" face="Courier New"> <b>0</b></font></span><font class="Apple-style-span" color="#B3B3B3"><font class="Apple-style-span" face="Courier New"> ; "find a gcroot at 0(%esp)"</font></font></span></font></div><font class="Apple-style-span" face="Courier New"><br class="webkit-block-placeholder"></font></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; font-style: italic; "> -- end --</span></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; ">The major challenges posed by the frame table are:</span></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; "> 1. Making a constant reference to a return address.</span></div><div><font class="Apple-style-span" face="'Courier New'"> - Labels are not global values, so ocamlopt's approach is a </font></div><div><font class="Apple-style-span" face="'Courier New'"> no-go.</font></div><div><font class="Apple-style-span" face="'Courier New'"> - Is llvm.pcmarker in any way useful? It couldn't present the </font></div><div><font class="Apple-style-span" face="'Courier New'"> correct address for a caller-save calling convention.</font></div><div><font class="Apple-style-span" face="'Courier New'"> - A constant expression like OFFSET + (intptr_t) FUNCTION can</font></div><div><font class="Apple-style-span" face="'Courier New'"> get the job done, but this requires instruction size </font></div><div><font class="Apple-style-span" face="'Courier New'"> computations which I can only find for ARM (in support of </font></div><div><font class="Apple-style-span" face="'Courier New'"> the constant island pass).</font></div><div><br></div><div><font class="Apple-style-span" face="'Courier New'"> 2. Computing the static stack offset of the GC roots.</font></div><div><font class="Apple-style-span" face="'Courier New'"> - I'm not yet sure whether this is trivial or not.</font></div><div><br></div><div><font class="Apple-style-span" face="'Courier New'">Additionally:</font></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="'Courier New'"> 3. Identifying the roots live after each call site.</font></div><div><font class="Apple-style-span" face="'Courier New'"> - Trivially correct: include all llvm.gcroot'd allocas in the</font></div><div><font class="Apple-style-span" face="'Courier New'"> function.</font></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; "> - Harder: analyze load/store dominance information vs. the </span></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; "> call site to eliminate those roots which are not live.</span></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="'Courier New'"> 4. Identifying all return addresses.</font></div><div><font class="Apple-style-span" face="'Courier New'"> - I think trivial on the MachineFunction representation, but</font></div><div><font class="Apple-style-span" face="'Courier New'"> is it possible to relate the machine instructions back to</font></div><div><font class="Apple-style-span" face="'Courier New'"> the LLVM IR, where the liveness analysis must be performed?</font></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="'Courier New'"> 5. Update the frame table constant with information only </font></div><div><font class="Apple-style-span" face="'Courier New'"> available during codegen.</font></div><div><font class="Apple-style-span" face="'Courier New'"> - I'm thinking I should populate an on-the-side data structure</font></div><div><font class="Apple-style-span" face="'Courier New'"> during compilation, and only convert it to a Constant* and </font></div><div><font class="Apple-style-span" face="'Courier New'"> emit it during an epilogue pass using</font></div><div><font class="Apple-style-span" face="'Courier New'"> AsmPrinter::<span class="Apple-style-span" style="font-family: 'Trebuchet MS'; "><font class="Apple-style-span" face="'Courier New'">EmitGlobalConstant.</font></span></font></div><div><br></div><div><font class="Apple-style-span" face="'Courier New'">That's the doozy. Unfortunately, I think the runtime requirements </font></div><div><font class="Apple-style-span" face="'Courier New'">will preclude the use of the basic LLVM toolchain<i> </i>in conjunction </font></div><div><font class="Apple-style-span" face="'Courier New'">with LLVM <i>ocamlopt</i>, which is unfortunate.</font></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="'Courier New'">The simpler problem is that each ocaml object exports symbols </font></div><div><font class="Apple-style-span" face="'Courier New'">bracketing its code and data. An ocaml object absent these symbols</font></div><div><font class="Apple-style-span" face="'Courier New'">cannot be linked into an executable.</font></div><div><br></div><div><font class="Apple-style-span" face="'Courier New'"><span class="Apple-style-span" style="font-family: 'Trebuchet MS'; "><div><font class="Apple-style-span" face="'Courier New'"> <b>prologue </b><b>from <i>example.s</i>:</b></font></div><div><font class="Apple-style-span" color="#000000" face="Courier New"> .data</font></div><div><font class="Apple-style-span" color="#000000" face="Courier New"> .globl _camlExample__data_begin</font></div><div><font class="Apple-style-span" color="#000000" face="Courier New"> _camlExample__data_begin:</font></div><div><font class="Apple-style-span" color="#000000" face="Courier New"> .text</font></div><div><font class="Apple-style-span" color="#000000" face="Courier New"> .globl _camlExample__code_begin</font></div><div><font class="Apple-style-span" color="#000000" face="Courier New"> _camlExample__code_begin:</font></div><div><font class="Apple-style-span" face="'Courier New'"> .data</font></div><div><font class="Apple-style-span" face="'Courier New'"> ; data follows</font></div><div><div><font class="Apple-style-span" face="'Courier New'"><span class="Apple-style-span" style="font-family: 'Trebuchet MS'; "><div><font class="Apple-style-span" face="'Courier New'"> .text</font></div><div><font class="Apple-style-span" face="'Courier New'"> ; code follows</font></div><div><br></div></span></font></div><div><font class="Apple-style-span" face="'Courier New'"> <b>epilogue </b><b>from <i>example.s</i>:</b></font></div><div><font class="Apple-style-span" color="#000000" face="Courier New"> .text</font></div><div><font class="Apple-style-span" color="#000000" face="Courier New"> .globl _camlExample__code_end</font></div><div><font class="Apple-style-span" color="#000000" face="Courier New"> _camlExample__code_end:</font></div><div><font class="Apple-style-span" color="#000000" face="Courier New"> .data</font></div><div><font class="Apple-style-span" color="#000000" face="Courier New"> .globl _camlExample__data_end</font></div><div><font class="Apple-style-span" color="#000000" face="Courier New"> _camlExample__data_end:</font></div><div><font class="Apple-style-span" color="#000000" face="Courier New"> .long 0</font></div><font class="Apple-style-span" color="#000000" face="Courier New"><br></font></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; ">I think I should simply write prologue- and epilogue emitter </span></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; ">passes for this boilerplate. That avoids attempting to model these</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; ">quirky symbols in the LLVM IR, but again breaks <i>llc</i> compatibility. </span></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; ">Is there a better way?</span></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="'Courier New'"><br class="webkit-block-placeholder"></font></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; ">Thanks,</span></div></span></font></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; ">Gordon</span></div></div><font class="Apple-style-span" face="Courier New"><br class="webkit-block-placeholder"></font></div><div><font class="Apple-style-span" face="'Courier New'"><span></span></font></div></body></html>