[Clang] Mixed use of VLAs and alloca leads to miscompilation (early pop of alloca memory)

[kkofler]

In this (minimized, not linkable, use clang -O2 -S allocatest.c and look at the output to test) testcase:

#include <alloca.h>

struct nlopt;

extern int n;
struct nlopt *create(void);
void f(struct nlopt *opt, double *x, void *userdata);
void solve(struct nlopt *opt);

int main(void)
{
  struct nlopt *opt = create();
  int i;
  {
    double x[n];
    for (i = 0; i < n; i++) {
      void *p = alloca(8);
      f(opt, x, p);
    }
  }
  solve(opt);
  return 0;
}

the alloca needs to live until the end of the function, but (as evidenced by the assembly output), Clang actually emits code to restore rsp to its value before the VLA creation at the point where the VLA goes out of scope, and that also ends up destroying the arrays from alloca.

In the real (much longer) code, the solve function (actually called nlopt_optimize) ends up using the pointers that were recorded in the opt structure by the function f (actually called nlopt_add_inequality_constraint), but due to the early pop, they will have been overwritten, leading to a crash.

I can reproduce this with all 3 of clang version 20.1.7, clang version 18.1.8, and with the ancient clang version 13.0.1, so this is a longstanding bug.

GCC gets this right: gcc -O2 -S allocatest.c shows that rsp is not restored until after solve is called (so the lifetime of the VLA also has to be extended, but there is not really a way around that in this case), and in fact, the real program also does not crash when compiled with GCC as it does when compiled with Clang.

[kkofler]

Hmmmph, why does releases.llvm.org show me version 18.1.8 as the latest when the actual latest version here is 20.1.7?

[kkofler]

Bug still present with clang version 20.1.7 (https://github.com/llvm/llvm-project 6146a88f60492b520a36f8f8f3231e15f3cc6082).

[kkofler]

GCC actually had a similar bug in the past, but it was fixed in 2015: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14236

[AaronBallman]

CC @efriedma-quic @rjmccall

My codegen-fu is not as strong as yours: is this happening because we call llvm.stackrestore in the for.end block? Is that basically restoring the saved stack for the VLA and the explicit alloca at the same time?

[kkofler]

The question is probably not directed to me, but I would guess so, yes. Though I am not familiar with the internals of LLVM. (I do have some experience with compiler internals though, having worked on a GCC port, see http://tigcc.ticalc.org/ .) So let us wait for the LLVM codegen experts to confirm.

[nikic]

Hm, is there anything we can do about this short of just never freeing VLAs if alloca() is used in the same function?

[AaronBallman]

Hm, is there anything we can do about this short of just never freeing VLAs if alloca() is used in the same function?

I think we may run into similar problems when we get to the defer proposal because that will have similar stack allocation behavior to VLAs (block-scoped lifetime, not function-scoped like alloca). So maybe we need different LLVM IR for alloca vs block scoped stack allocations?

[nikic]

I don't think that different IR is going to help. We can't free allocations on the stack out of order, so as soon as an alloca occurs, we lose the ability to free anything that was allocated below it.

I kind of feel like using alloca in a function with VLAs should be considered ill-formed, as both of their requirements cannot be satisfied at the same time.

[AaronBallman]

I don't think that different IR is going to help. We can't free allocations on the stack out of order, so as soon as an alloca occurs, we lose the ability to free anything that was allocated below it.

I was thinking we could play games with the stack to make that possible (e.g., allocas and VLAs grow different parts of the stack so there's not as strong of a relationship between the two). But I suppose a better question is: what did GCC do to address this?

I kind of feel like using alloca in a function with VLAs should be considered ill-formed, as both of their requirements cannot be satisfied at the same time.

That would be tricky for the FE to diagnose reliably. Consider code where the alloca is conditionally controlled; if the alloca isn't called on a particular path, we'd be wrong to reject that code.

[kkofler]

What GCC does appears to be "just never freeing VLAs if alloca() is used in the same function", at least in any parts that can be reached from the alloca. That is sufficient to comply to the specs of alloca, and I am not convinced that it actually violates the constraints of VLAs. (Is it said anywhere that those must be popped at any specific point?)

Stack partitioning is a possibility, but is it worth it, when other compilers do not do it (so program(mer)s cannot rely on it being done anyway)?

[AaronBallman]

What GCC does appears to be "just never freeing VLAs if alloca() is used in the same function", at least in any parts that can be reached from the alloca. That is sufficient to comply to the specs of alloca, and I am not convinced that it actually violates the constraints of VLAs. (Is it said anywhere that those must be popped at any specific point?)

Stack partitioning is a possibility, but is it worth it, when other compilers do not do it (so program(mer)s cannot rely on it being done anyway)?

The C standard has this to say about the lifetime of a VLA:

For such an object that does have a variable length array type, its lifetime extends from the declaration of the object until execution of the program leaves the scope of the declaration. If the scope is entered recursively, a new instance of the object is created each time. The initial representation of the object is indeterminate.

So I think we're fine to extend the lifetime of the VLA to the function scope; it's UB to access it once the block containing the VLA is exited, but extending the lifetime in the presence of alloca doesn't change that. CC @uecker just in case I'm missing something subtle about VLAs.

[efriedma-quic]

The C standard technically doesn't require VLAs to be freed at any particular time... but if we don't use llvm.stacksave/llvm.stackrestore, we leak resources.

That would be tricky for the FE to diagnose reliably. Consider code where the alloca is conditionally controlled; if the alloca isn't called on a particular path, we'd be wrong to reject that code.

I think if you have VLAs and alloca in the same function, you've basically already messed up, even if we can't prove the alloca is dynamically executed.

I don't mind copying gcc behavior here, but we should warn whenever we erase llvm.stackrestores.