On Apr 10, 2011, at 2:45 PM, Talin wrote:> I wonder - would something like this allow for multiple stacks for a single thread? I'm thinking of something like continuations / fibers / green threads, which would be very handy.I haven't looked at the proposal, but yes, this would be very useful functionality for LLVM to provide. -Chris> > On Wed, Mar 23, 2011 at 3:07 AM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote: > Hi All! > > I will be applying to the LLVM project for this GSoC, and I wanted some > preliminary sanity check on my project idea. > > I intend to implement split (segmented) stacks for LLVM (like we have in > Go, and as being implemented for GCC [1]). A lot of what follows is > lifted from [1]; I will progressively add more details as I get more > familiar with the LLVM codebase. > > I intend to start with the simplest possible approach - representing the > stack as a doubly linked list of _block_s, the size of each _block_ > being a power of two. This can later be modified to improve performance > and accommodate other factors. Blocks will be chained together into a > doubly linked list structure (using the first two words in the block as > the next and previous pointers). > > In the prologue, a function will check whether the current block has > enough stack space. This is easily done for function which don't have > variable sized allocas, and for ones which do, we can assume some > worst-case upper bound. The prologue can then call an intrinsic (let's > call it llvm.adjust_stack) which allocates a new block (possibly by > delegating this to a user-provided callback), copies the arguments, > saves the previous stack pointer (in the new block), and adjusts the > next and previous pointers. It will also have to adjust the stack > pointer, and the frame pointer, if it is being maintained. Cleanup can > be done by hijacking the return value, as also mentioned in [1]. It > might make sense to leave the allocated blocks around, to prevent > re-allocating the next time the program needs more stack space. > > DWARF info can be generated as follows: since we know the offset of base > of the stack frame from the stack pointer (or we are maintaining a frame > pointer), we can always say whether the concerned call frame is the > first call frame or not. In the second case, all the previous register > values can be computed as usual, and in the first case, we will add an > extra indirection, involving looking up the stack pointer saved in this > block's header. > > One thing I'd really like some input on is whether implementing split > stacks would be useful enough to warrant the effort (especially keeping > in mind that this is pretty useless on 64 bit architectures). > > [1] http://gcc.gnu.org/wiki/SplitStacks > -- > Sanjoy Das > http://playingwithpointers.com > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > > -- > -- Talin > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110410/1265f704/attachment.html>
On Sun, Apr 10, 2011 at 4:16 PM, Chris Lattner <clattner at apple.com> wrote:> > On Apr 10, 2011, at 2:45 PM, Talin wrote: > > I wonder - would something like this allow for multiple stacks for a single > thread? I'm thinking of something like continuations / fibers / green > threads, which would be very handy. > > > I haven't looked at the proposal, but yes, this would be very useful > functionality for LLVM to provide. >Another thing I'd like is for any proposed segmented stack mechanism to be garbage-collector friendly - which essentially means an API that can reliably iterate through all of the stack frames, starting from the current function, and calculate the correct return address for each stack frame. I'm envisioning something like this: frame = llvm.currentframe(); while frame != NULL { retaddr = llvm.returnaddr(frame); // do stack tracing using frame and retaddr to identify stack roots. frame = llvm.nextframe(frame); } This is essentially what I do now with the EBP register - but it would be better if it were encapsulated behind an API, so that frontends wouldn't have to know about specific registers.> > -Chris > > > On Wed, Mar 23, 2011 at 3:07 AM, Sanjoy Das < > sanjoy at playingwithpointers.com> wrote: > >> Hi All! >> >> I will be applying to the LLVM project for this GSoC, and I wanted some >> preliminary sanity check on my project idea. >> >> I intend to implement split (segmented) stacks for LLVM (like we have in >> Go, and as being implemented for GCC [1]). A lot of what follows is >> lifted from [1]; I will progressively add more details as I get more >> familiar with the LLVM codebase. >> >> I intend to start with the simplest possible approach - representing the >> stack as a doubly linked list of _block_s, the size of each _block_ >> being a power of two. This can later be modified to improve performance >> and accommodate other factors. Blocks will be chained together into a >> doubly linked list structure (using the first two words in the block as >> the next and previous pointers). >> >> In the prologue, a function will check whether the current block has >> enough stack space. This is easily done for function which don't have >> variable sized allocas, and for ones which do, we can assume some >> worst-case upper bound. The prologue can then call an intrinsic (let's >> call it llvm.adjust_stack) which allocates a new block (possibly by >> delegating this to a user-provided callback), copies the arguments, >> saves the previous stack pointer (in the new block), and adjusts the >> next and previous pointers. It will also have to adjust the stack >> pointer, and the frame pointer, if it is being maintained. Cleanup can >> be done by hijacking the return value, as also mentioned in [1]. It >> might make sense to leave the allocated blocks around, to prevent >> re-allocating the next time the program needs more stack space. >> >> DWARF info can be generated as follows: since we know the offset of base >> of the stack frame from the stack pointer (or we are maintaining a frame >> pointer), we can always say whether the concerned call frame is the >> first call frame or not. In the second case, all the previous register >> values can be computed as usual, and in the first case, we will add an >> extra indirection, involving looking up the stack pointer saved in this >> block's header. >> >> One thing I'd really like some input on is whether implementing split >> stacks would be useful enough to warrant the effort (especially keeping >> in mind that this is pretty useless on 64 bit architectures). >> >> [1] http://gcc.gnu.org/wiki/SplitStacks >> -- >> Sanjoy Das >> http://playingwithpointers.com >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> > > > > -- > -- Talin > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > >-- -- Talin -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110410/cf272b78/attachment.html>
Hi! Thanks for the feedback. For context, my implementation plan is here: http://pastebin.com/e9JMZNCE First, about unwinding: In architectures like x86-64, where unwinding based on DWARF info, there shouldn't be any problems; since the DWARF info will be emitted correctly. Otherwise, if the unwinding is done by following BP, it should still be possible to have BP de-reference correctly (ref. "Frame Pointers" section in the implementation plan). SP will not always have a correct value - I don't know if this is problem. About co-routines: Here is a sketch of how I think co-routines can be implemented (I'll merge this with the main implementation plan after I get some feedback): Have a new instruction, called "yield" to return a value from a co-routine, preserving the state. Thus, we immediately know which functions are co-routines. Each co-routine will have a new stack. Associate each co-routine with a thread-local global variable (called saved_stack here, will have to be mangled with the name of the co-routine) which points to the start stack block for that co-routine. This will be the first block in the chain of blocks to follow. The structure of the block will be similar to the structure of a regular stack block, except that it will also have space to store two registers - this_ip and this_sp. The prologue of a co-routine will jump to a function similar to setup_new_block (setup_new_block_coroutine) which will work like setup_new_block, except: 1. It will first check if saved_stack is NULL. If it is NULL, it will allocate a new block and save it to saved_stack. It if isn't, it'll simply restore saved_sp, saved_ip. 2. In case a new block was allocated, it will pretty much do what setup_block does, after which it will adjust the SP to make space for the saved registers. The destroy_block procedure will also have to be a little different (mentioned below). There are four things (relevant to this discussion) a co-routine can do: Yield This returns control to the calling function, without forgetting the current state of the function. To do this, we save saved_ip and saved_sp. Every yield be padded with instructions pushing and popping the registers live at that point. Then we set the return value (register or memory), and restore saved_sp and saved_ip from the current block. We can't simply return because the actual return value has been hijacked to provide for block cleanup. Call to regular function Just a simple call - the caller's prologue will handle setting up a it's own stack space etc. Call to Co-routine This too should "just work", since all the heavy-lifting is done in the co-routine's prologue. However, the above approach will not work for nested co-routines (i.e. calling the same co-routine body with one call is still active, recursively). I'm not sure if having support for nested co-routines will add any value. Return This will be a regular return. Since the return value has been hijacked to point to a another block of code (destroy_block_coroutine), control will jump there instead. destroy_block_coroutine will free the linked-list of stack blocks (we have to free this, since we will won't have a reference to this list anymore), set saved_stack for this co-routine to NULL, and restore saved_sp and saved_ip. -- Sanjoy Das http://playingwithpointers.com