G-Machine source translation to LLVM IR

Question

I use a simple lazy functional language with LLVM as my backend in Haskell. I read two books written by Simon Peyton Jones (“Implementing Functional Programming Languages” and “Implementing Functional Languages: A Tutorial”), and based on this I managed to implement the G-Machine Compiler and Interpreter .

Now I'm stuck in the problem of generating LLVM IR code from G-Machine instructions. The main problem is that the G-Machine is a stack machine, while the LLVM IR is a recorder. Thus, in order to transfer the G-Machine to LLVM IR, I need to support some kind of runtime stack in LLVM IR (please correct me if I am wrong). I thought about distributing subsequent stack nodes in the LLVM stack using my IR instructions, but then I would have to create this stack in the form of linked lists, where each stack element has a pointer to the previous one, and the first has a null pointer. However, this approach is not very optimal, and in the case of the “Push n” operation from G-Machine it will have O (n) complexity instead of the preferred O (1). Another idea might be to allocate whole blocks of memory instead of individual cells.

My question is: do you see a better / different way to solve my problem.

Answer 1

Do not make linked list stacks that are crazy. Used blocks of fixed memory. You can use a stack of pointers and a stack not of a pointer, but by pointer I mean something that points to a bunch. Then it's pretty easy to do garbage collection, since all the roots of the GC are on the pointer stack.

Store a few things in LLVM registers: heap pointer, heap restriction pointer, two stack pointers.

If you're lucky, the LLVM will turn inefficient stack operations into efficient register operations.

Answer 2

there is a simple tutorial

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

NTN