Re: Incrementally implementing a simple ML compiler using LLVM

On Mon, 26 Nov 2007 22:53:09 +0000, Jon Harrop <usenet@jdh30.plus.com>
wrote:


>I recently tried the Low-Level Virtual Machine (LLVM) project and found that
>I can use its OCaml bindings to write native-code compilers with ease.
>
>I would like to use this technology to create a simple compiler for a
>language similar to OCaml but with no baggage (e.g. I have no desire
>to support 63-bit integers!). However, I am completely new to this (I
>am a computational physicist/dabbler) so I'd really appreciate a
>little assistance.


Tagged values are common in GC'd languages, but with some effort in
the compiler and GC runtime you can support untagged values. The idea
is simple - move the tag somewhere else. A statically typed language
actually makes it a little easier.


Basically, any data structure that the GC must examine requires a map
indicating which values within it are pointers. Obviously instances
of the same type of structure can share the same pointer map. For a
heap object you can keep a pointer to the map in the object header
(like a class pointer in an OO language).


For stack allocated objects it is a little more complicated. If you
fix the layout of a function call frame at compile time then you can
treat the call frame like any other object.


If you prefer to allow things like RAII or dynamically sized objects
(e.g., strings), you must update the call frame map at runtime so that
correctly indicates the state of the frame at any point where a GC
might occur. GC in a single threaded system can only be triggered by
allocation so the obvious point to update your current frame map is in
the preamble to a function call.


The hard part is what to do with register values. The best solution
is to partition the register set so that pointers are only to be found
in certain registers, but that isn't always possible on register
starved architectures like x86. You may find you need to store the
registers into the call frame and update the frame map before every
function call.


Another solution to the register problem is to use a memory->memory
model rather than a register model. The idea here is to keep program
values in memory and to only use machine registers for temporary
expression values. Memory->memory is less performant, but a GC for it
doesn't have to know anything about pointers in registers.




>Until now I have only been superficially aware of boxing (in the
>context of optimization). What exactly is the simplest run-time
>representation of a boxed value? Is it a pointer to a >=1 word-sized
>block?


Yes.


>Is the Cheney semi-space GC a suitable starting point?


If you want fast "bump" allocation, you're pretty much wedded to a
Cheney style system - the only other alternative is "mark-compact"
which is not very popular. Mark-compact works better in constrained
memory situations but is more complicated to implement.




>Is there an abstract interface for using a GC from generated code
>that I could adhere to?


No. GC is closely coupled to the runtime, the interface depends
crucially on the how the runtime is organized.




>Is there anything else that I should be aware of?


GC efficiency is greatly affected by how you treat allocations, and
for concurrent copying collectors, how you treat forwarded objects.
In terms of the 3-color abstraction, it makes a big difference whether
you allocate black or white and whether you forward black or grey.


If you are really interested in GC implementation, you should read the
bible:
Jones & Lins, "Garbage Collection: Algorithms for Automatic Dynamic
Memory Management", 1996, ISBN 0-471-94148-4.
http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471941484.html


Also see Richard Jones's GC pages:
http://www.cs.kent.ac.uk/people/staff/rej/gc.html
http://www.cs.kent.ac.uk/people/staff/rej/gcbib/gcbibM.html




George

Return to the comp.compilers page.
Search the comp.compilers archives again.