llvm dev - Aug 2004 - [LLVMdev] Stack branching for non-preemptive threading

Hi,

	Is there any way to support either stack branching or heap-allocated
stack frames in llvm?

	What I am after is non-preemptive threading support (as in Modsim,
but I have also written a small library in asm to allow this in C),
where a function can "suspend" itself and resume execution later.

	I was excited to find llvm as I thought it would be an excellent
back end for a language I am developing (I had once thought I could use
JVM similarly but found it much too high level and java-specific), but
due to the automatic stack frame management, I find I still cannot do
what I am after.

	Perhaps a backup approach would be:  Can I create a pointer to a
label, and then branch to that later?  If so, perhaps I could bypass
llvm's intrinsic call/ret altogether and just implement my own calling
convention?

	-Brandyn

p.s., please cc me directly in any replies as I am only polling the
list on the web site for the moment until I decide to jump in
headlong.

-- 
---------- brandyn at sifter.org ------- http://www.sifter.org/~brandyn
----------

  	  A word saved by one clever writer is a word saved a million readers.

On Wed, 25 Aug 2004, Brandyn Webb wrote:
> 	Is there any way to support either stack branching or heap-allocated
> stack frames in llvm?
No, we do not currently support this, though we do have long term plans to
(which could become short-term plans if you help implement it :)

The basic idea for our implementation is that, given proper tail calls,
you can implement the entire system using continuations and implement the
stack frame yourself.  Unfortunately, LLVM does not currently support
proper tail calls yet (i.e. arbitrary tail calls are not guaranteed to
execute in zero space, e.g. calls through function pointers).

If you are interested in this functionality, the first step is to
implement the ideas described in this document:

http://nondot.org/sabre/LLVMNotes/CustomCallingConventions.txt

Given an implementation of this, CC#0 would naturally provide "proper"
tail call support.
> 	What I am after is non-preemptive threading support (as in Modsim,
> but I have also written a small library in asm to allow this in C),
> where a function can "suspend" itself and resume execution later.
Yes, this makes sense.  Depending on how you are implementing this, you
could implement stacks yourself using the
getcontext/setcontext/swapcontext system calls.  However, these will only
work if you have multiple threads with disjoint stacks: shared stacks
won't work.
> 	I was excited to find llvm as I thought it would be an excellent
> back end for a language I am developing (I had once thought I could use
> JVM similarly but found it much too high level and java-specific), but
> due to the automatic stack frame management, I find I still cannot do
> what I am after.
LLVM does make a great back-end, but we are currently missing this one
feature.  I think it would be relatively straight-forward to implement it
if you desire though.
> 	Perhaps a backup approach would be:  Can I create a pointer to a
> label, and then branch to that later?  If so, perhaps I could bypass
> llvm's intrinsic call/ret altogether and just implement my own calling
> convention?
See the document above.  It's not possible to take the address of a label
in LLVM, but you shouldn't need to.  The other option is to use some of
the well known ways of implementing languages like yours in C, but these
tend to be extremely inefficient.  I think that adding the initial chunk
or alternate calling convention support (describe in the link above) would
a straight-forward way to get great performance out of your language.

-Chris

-- 
http://llvm.org/
http://nondot.org/sabre/