Home > Archive > Compilers > November 2007 > Incrementally implementing a simple ML compiler using LLVM
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Incrementally implementing a simple ML compiler using LLVM
|
|
| Jon Harrop 2007-11-26, 7:22 pm |
| 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.
I already have a really bare-bones compiler for a first-order language
with a single type (int) that can compile a Fibonacci program to
x86-64 native code.
I'm not even sure what my milestones should be but I assume I should
add more types (e.g. function pointers), boxed values and a garbage
collector next.
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?
Is the Cheney semi-space GC a suitable starting point? Is there an
abstract interface for using a GC from generated code that I could
adhere to?
Is there anything else that I should be aware of?
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
| |
| George Neuner 2007-11-29, 4:35 am |
| 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/Wiley...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/sta...bib/gcbibM.html
George
| |
| Joachim Durchholz 2007-11-30, 4:28 am |
| Jon Harrop schrieb:
> Is the Cheney semi-space GC a suitable starting point? Is there an
> abstract interface for using a GC from generated code that I could
> adhere to?
>
> Is there anything else that I should be aware of?
Let me comlement the already-given advice by remarking that
implementing an efficient, robust GC is D**n Bl**dy Hard (TM). Entire
lifetimes have been devoted to writing and tuning a GC.
That's the reason why most people stick with the Boehm/Demers/Weiser
collector. This will give you a reasonable GC, allow you to
concentrate on other issues, and come back to the GC side of your
system when you have the time.
The risk with that strategy is that the Boehm collector will warp the
design of your run-time. OTOH unless you're already a GC guru, your
run-time design will likely warp the GC design into something less
efficient than it could be, so there's no risk-free strategy anyway...
Regards,
Jo
| |
|
|
|
|
|