Translating G-Machine source to LLVM IR

Question

I'm implementing a simple lazy functional language with LLVM as its backend in Haskell. I've read two books written by Simon Peyton Jones ("The implementation of functional programming languages", as well as "Implementing functional languages: the tutorial") and based on that I managed to implement the G-Machine compiler and interpreter.

I'm now currently stuck on the problem of generating LLVM IR code from G-Machine instructions. The main problem is that G-Machine is a stack machine whereas LLVM IR is a register machine. Thus in order to translate G-Machine into LLVM IR I have to maintain some sort of run-time stack in LLVM IR (please correct me if I'm wrong). I was thinking of allocating subsequent stack nodes on the LLVM stack using its IR instructions, but then I'd have to create that stack in a linked-list manner, where each stack element has a pointer to the previous one and the first has a null pointer. This approach however is not very optimal and in case of "Push n" operation from G-Machine it would have a complexity of O(n) instead of preferred O(1). Other idea might be to allocate whole blocks of memory instead of single cells.

My question is whether you see a better/different way of solving my problem.

Answer 1

Don't do linked list stacks, that's crazy. Used fixed memory blocks. You can use a pointer stack and a non-pointer stack, and by pointer I mean something pointing into the heap. Then it's pretty easy to do garbage collection since all the GC roots are on the pointer stack.

Keep a few things in LLVM registers: heap pointer, heap limit pointer, the two stack pointers.

If you are lucky the LLVM optimizer will turn the inefficient stack operations into efficient register operations.

Answer 2

there is simple tutorial

http://llvm.org/releases/2.0/docs/Stacker.html

HTH