Avoiding alloca elision

Hello

I’m implementing stack copying coroutines. It’s an interesting challenge. When we use setjmp/longjmp to move between stacks, we must make sure that restoring the stack doesn’t blow away the current stack frame before calling longjmp.

To do that, we check how big the stack we are restoring is, and use alloca to push the current stack frame beyond that. It works but when I add “-O3” the alloca is elided and it fails again.

I managed to avoid this by using the resulting buffer in an operation the compiler can’t elide. But I was wondering, is there an attribute or other mechanism by which I can tell the compiler: Don’t elide this statement even if the result is unused.

Here is the code: https://github.com/ioquatix/ruby/blob/3fd9102cb885858038d6a29071acecef78e6d6a5/coroutine/copy/Context.c#L36-L80

You can see on line 57, I forced compiler to use the result of the alloca. If I remove this, it fails because alloca is not invoked.

Any help/suggestions appreciated.

Kind regards,
Samuel

Hi Samuel,

You can't expect alloca's to reliably lower to stack pointer
adjustments. The semantics of alloca is more high level -- it give
you an abstract memory location that lives and dies with the function
frame, but there is no guarantee that it will actually "allocate"
memory from the stack frame. The compiler may promote the memory to
registers or (theoretically speaking, we don't do this today) even
demote it to a heap allocation.

You'll have to phrase your stack copy coroutines implementation in
terms of the abstract alloca semantics without assuming that LLVM will
lower allocas in some specific manner (i.e. without relying on
"implementation details").

-- Sanjoy

What?!?

  1. If it gets demoted to a heap allocation, when does the memory ever get freed? There is no “freea” call, after all.
  2. What alloca documentation are you looking at, that allows for heap allocation?

As far as I know, if the memory can’t be stack-allocated, alloca() is just supposed to return NULL… though frankly, as far as I can tell alloca is a nonstandard extension that is implemented differently from one platform to the next. For that matter, even variable-length arrays in C aren’t guaranteed to work. (C11 made them optional?) And interestingly, Linux went to the trouble of removing them all ( https://www.phoronix.com/scan.php?page=news_item&px=Linux-Kills-The-VLA )

– Jorg

Hi Samuel,

You can’t expect alloca’s to reliably lower to stack pointer
adjustments. The semantics of alloca is more high level – it give
you an abstract memory location that lives and dies with the function
frame, but there is no guarantee that it will actually “allocate”
memory from the stack frame. The compiler may promote the memory to
registers or (theoretically speaking, we don’t do this today) even
demote it to a heap allocation.

What?!?

  1. If it gets demoted to a heap allocation, when does the memory ever get freed? There is no “freea” call, after all.
  2. What alloca documentation are you looking at, that allows for heap allocation?

As far as I know, if the memory can’t be stack-allocated, alloca() is just supposed to return NULL… though frankly, as far as I can tell alloca is a nonstandard extension that is implemented differently from one platform to the next. For that matter, even variable-length arrays in C aren’t guaranteed to work. (C11 made them optional?) And interestingly, Linux went to the trouble of removing them all ( https://www.phoronix.com/scan.php?page=news_item&px=Linux-Kills-The-VLA )

I think Sanjoy was maybe talking in terms of LLVM’s alloca intrinsic, rather than the C API. But in any case, the C API seems quite implementable with dynamic memory allocation - the basic API being "The alloca() function allocates size bytes of space in the stack frame of the caller. This temporary space is automatically freed when the function that called alloca() returns to its caller. - yeah, an implementation could implement that in terms of dynamic memory allocation automatically freed at the end of the function call.

The fact that it says “in the stack frame of the caller” is perhaps fuzzy enough - we already have things like split stacks - seems plausible we could have dynamically allocated stack frames, or partially dynamically allocated ones - at which point alloca using such a thing would fit the definition.

I think Sanjoy was maybe talking in terms of LLVM's alloca intrinsic, rather than the C API. But in any case, the C API seems quite implementable with dynamic memory allocation

Definitely. Historically armcc used malloc for alloca; while I was
there we got around to implementing "stack-based alloca" as a
bona-fide feature.

For Jorg:

1) If it gets demoted to a heap allocation, when does the memory ever get freed? There is no "freea" call, after all.

The implementation would ensure free got called on every exit path
from the function. It's not a fundamentally different problem compared
to calling destructors in C++.

Cheers.

Tim.