[LLVMdev] explicit stack management

[OvermindDL1]

On Fri, Nov 28, 2008 at 9:14 PM, Jonathan Bastien-Filiatrault
<joe at x2a.org> wrote:
> I would say it means to have a "stackless" code generator. You may want
> to see http://en.wikipedia.org/wiki/Spaghetti_stack and
> http://www.nondot.org/sabre/LLVMNotes/ExplicitlyManagedStackFrames.txt .
>
> "Stackless" means that you do not use the "system" stack, but that
> rather, your language frontend manages the stack frames itself.
>
> Hope this is any help,
> Jonathan

I am actually doing something like that.  I am making a language (to
ease some certain programming styles I am needing to do) that is
C-like, but an Erlang style programming pattern, lots of little
Actors.  I have my frontend look at any point a new Actor is created
(where a function is always passed in) and it follows it down the
stack of all possible calls and sees what the largest 'stack' usage
point is (say one Actor could potentially be using a stack that is
816bytes).  When the program is run and it hits that point where the
code creates that new Actor it allocates a section of memory that is
the "sizeof(structActorInfo)+sizeof(structContinuation)*numFuncCallsAtMax+816"bytes.
 Internally all functions that are capable of suspending execution all
have two internal parameters passed around, which is the pointer to
the top of the structActorInfo area, and the current top of stack
pointer in the allocated memory.  Any function that the front-end can
prove can never suspend in any way it will not bother passing those
around, but will rather use the real CPU stack, since those functions
cannot suspend there is no worry about the machine stack being
clobbered.  Other then that I just have any function can is capable of
suspending use the passed stack pointer to store the 'stack
variables'.  Actually that is not strictly true, I do fight with LLVM
in one way in that I cannot tell it to treat my chunk of memory as a
stack, so the optimizer does not optimize most of it away as usual, so
I have my front-end do it in the normal LLVM style, but before a
suspend-capable function call (*always* a tail-call) it then copies
all 'local' vars onto the managed actor stack in specific places.  The
functions in my language are actually normal looking, just the
front-end splits them up at every possible suspend-capable function
call so those calls become tail-calls (what I do absolutely does not
work without tail-call optimization).  Either way, after a
suspend-capable function call finishes it then pops off the function
pointer off the actor stack, calling it with what this function
'returns' as a parameter (basically the function that called this
function is then continued in one of its splits.

LLVM does not make this terribly easy, but it works, and is still very
fast (a whole heck of a lot faster then Erlang, and most of it
optimizes well thanks to the fact that 'most' function calls do not
ever suspend).  There are a few rules I have of course, such as my
language does *not* support global variables.  To communicate to
another Actor they pass a message (which in the general case is
optimized to a tail-call, so still fast), but the front-end ensures
that there are no pointers passed... ever, as such I also do not allow
arbitrary integer<->pointer conversions either.  As long as the
problem I am trying to solve (which I am) is "ridiculously
parallelizable", this should scale arbitrarily.