I'm writing my own F#-esque language and I'm using LLVM for code generation. I want my language to support continuation passing style and I think I've got TCO figured out but I cannot figure out how to make continuations use heap memory instead of stack memory. As far as I can tell there is no direct mechanism for making a function's alloca call a custom allocation function. Do I have to implement a custom backend for this?
Asked
Active
Viewed 162 times
1 Answers
0
LLVM does not have a built in mechanism for such an abstraction, because it does not really implement a language level stack. It implements an activation record allocation stack. In C, these map 1:1, but once you explore more complex abstractions, these do not necessarily map 1:1.
Unless you are only talking about initial captures, you are likely to run into the issue that LLVM has no way to resume a function.
Typically, you would implement closures by using multiple activation records by splitting up your closure up into a state machine. One for the initial capture and then one for each entry point that you could need to resume to. The LLVM stack can be used to store values that are local to a specific state, but when values need to be stored between states, you will need to create some sort of struct datastructure, to store them in, and then store that struct in an appropriate place, for your languages concept of what a closure value is.
Depending on the implementation, you may choose to have a single struct which you mutate, or treat it as an immutable datastructure, where each state is a function from the initial values to values at the pause point.
It may also be useful to record what state you are in in this datastructure, in order to facilitate dispatch.
To take the concrete example of F#, an F# closure is just a class, containing a field for each captured value, and a virtual Invoke method. All captured values are rewritten to field accesses against the this parameter in the Invoke method, whilst the creation of the closure is rewritten to assign the values of the variables at the point of capture to the newly allocated closure object's fields.
user1937198
- 437
- 3
- 7
-
How would you deal with ensuring the function doesn't use stack space? You can (I guess) avoid allocating local variables by using the right calling convention and passing things through registers as much as possible, but you have to store the return address somewhere. Can you store the return address "somewhere else" other than on the stack using LLVM? – Gabriel May 14 '23 at 01:17
-
@Gabriel By separating the language level concept of 'stack space' or in C++ terminology which I prefer: Variables with automatic storage duration, from the implementation/LLVM concept of stack space. Just because something is a language stack variable, does not mean you have to put it on the implementation stack. And this is exactly what F# does with closures. The closure is an object, with state, and that state is used for the storage of captures. – user1937198 May 14 '23 at 12:17
-
@Gabriel You must have some in language value of a 'closure' that you use to resume it. Thats your handle to heap memory, and you tie your state off that. – user1937198 May 14 '23 at 12:20
-
@Gabriel As for return addresses, thats what I mean't by LLVM doesn't support resuming. _You can't return to arbitary addresses_. What you have to do is abstract to a tail call to a function. Which means the resume to arbitarty places. There are two standard approaches to this: 1) create an LLVM function for every place you could want to return to, pass that as a function pointer, and tail call that. 2) create a single LLVM function with an extra int argument indicating the resume point, with a giant switch at the start based on that in argument, and call with that argument. – user1937198 May 14 '23 at 12:23
-
I see, so all your local variables / possibly captures are in an object, and you pass a function that tail calls itself and you use TCO to turn it into a loop. If you need to allocate more memory you can use a linked list-like data structure or something. – Gabriel May 14 '23 at 19:38
-
@Gabriel Pretty much – user1937198 May 14 '23 at 19:50