stack arenas using alloca

[Michael Clark]

Hi Folks,

*sending again with Thunderbird because Apple Mail munged the message*.

I wanted to share a seed of an idea I have been ruminating on for a 
while, and that is being able to return alloca memory from a function.

I think it’s trivially possible by hacking the epilogue to unlink the 
frame  pointer but not pop the stack. Stack traces should work fine and 
it just looks like the parent function called an alloca which covers the 
fixed child frame and the alloca that it returned.

I tend to use alloca quite a lot in my programming style because I like 
to avoid the heap. I have a style where I run a loop with a size pass, 
then call alloca, then run the loop again without suppressing writes. I 
would like to be able to return, initially, one alloca to a parent 
function, but more than one should also be possible.

I haven't thought a lot about the mechanics of how one might signal to 
the compiler to suppress popping the stack, but I imagined one could 
return a pointer or structure with _Stack qualifiers to signal that 
stack memory from the child frame is being returned.

This is just a quick note as there is a deeper conversation about 
compacting stack arenas that would be possible if one had a runtime 
*and* compile time reflection API for frame metadata, where the frame is 
expressed as an anonymous C structure perhaps accessible via a function 
on a reference to a function. If you had frame metadata, you could emit 
one or many memmove calls. trivially one just needs the fixed frame 
length to recover the fixed frame stack memory and with full frame 
reflection, it would be possible to defer to a runtime routine in the 
case two or more stack pointers are returned, assuming the compiler 
tracks sizes of alloca calls. Ideally, the reflection API would also be 
constexpr-able meaning the runtime compaction could be inlined. This 
won't work for types that have pointers unless one has a full 
single-thread compacting GC that uses type metadata, but I tend to use 
indices. But unlike heap compaction, it doesn't have to worry about races.

The beauty of stack arenas, and compacting stack arenas, as a subtype, 
are many. Firstly the memory has no thread aliasing issues unlike heap 
memory, meaning analysis is much simpler and there are no pause issues 
like there are for GC. Secondly, it would be quite a neat way to 
constexpr variable-length arrays or a _List type because, unlike malloc, 
it’s much easier to reason about.

I have a relatively complete C reflection API that could be used as a 
starting point for C reflection. It currently works as an LLVM plugin. I 
am not sure how I would do this in GCC. A Python parser came to mind but 
it would be better if it somehow ran inside the compiler. It would also 
be great to have access to the frame of a function as an anonymous 
structure. It’s only runtime at present and it could benefit from a for 
comprehension because looping on variable length lists is a little 
clumsy. If I could return alloca memory in a structure that would 
largely solve this problem.

- https://github.com/michaeljclark/crefl

Regards,
Michael