How does GCC implement variable-length arrays?

Question

How does GCC implement Variable-length arrays (VLAs)? Are such arrays essentially pointers to the dynamically allocated storage such as returned by alloca?

The other alternative I could think of, is that such an array is allocated as last variable in a function, so that the offset of the variables are known during compile-time. However, the offset of a second VLA would then again not be known during compile-time.

Lindner

VLA works by placing the array in the stack - https://mcmap.net/q/297416/-is-there-any-overhead-for-using-variable-length-arrays. That is also what I see when checking the assembly output generated by gcc when using a VLA, no call to malloc. But it might depend on the actual implementation. – Eerie

This is an open source project. You can read the code. Alternatively, you can work it out simply by inspecting the code that it omitted. Also note that it is perfectly possible that there will be different implementations on different platforms. – Meanie

@barakmanos Absolutely not. We are talking about VLAs. – Meanie

It wouldn't really make sense for an implementation to use malloc to imlement VLA because malloc can fail. Allocating a VLA is guaranteed to succeed if there is sufficient stack space available. malloc is never guaranteed to succeed. – Stallion

@EliasVanOotegem You are missing the point somewhat. – Meanie

@DavidHeffernan: :-) sorry, got a bit side-tracked by the VLA's being guaranteed to succeed bit, I completely forgot the bit about it not making sense for an implementation to use malloc to implement VLA's :) – Reliance

@Brandin: Neither allocating a variable-length array nor allocating via malloc are guaranteed to work indefinitely. In most common C implementations, using malloc for variable-length arrays would support larger variable-length arrays than using the stack, because the space available for dynamic allocation is much larger than the default stack size. – Unclear

@EricPostpischil When I said "guaranteed to succeed" what I mean is if the stack space is sufficient. It's like if you open a new block and declare 10 double's. As long as there is stack space, then the implementation must ensure that this succeeds. There is no "failure to allocate local variable" condition that you can check. It's the same for a VLA – Stallion

@Brandin: malloc also succeeds if there is space available and fails if there is not. The C standard does not make actual guarantees about behavior in either case: A C implementation could fail to allocate a variable-length array (and terminate the program) even if there is theoretically more stack space available. A claim that variable-length arrays are more reliable is not sustainable in today’s environment where most C programs have gigabytes of memory available for malloc but only a few megabytes for variable-length arrays. – Unclear

@EricPostpischil I don't recall anyone saying VLAs are more reliable. But it still stands that failure is not possible with sufficient stack space. With malloc the standard clearly defines what happens on failure. In a way this is more "reliable" but you have no guarantee that malloc will work, regardless of how many gigabytes you think you have. – Stallion

@Brandin: The C standard implicitly permits variable-length arrays to fail, as by termination of the program. There is a section in the standard that specifies certain minimums that an implementation has to meet. Implicit in this is that an implementation does not have to provide infinite resources nor to protect a program from external events (e.g., a user pressing control-C to terminate execution). So an attempt to create a variable-length array can fail; a program can abort when it is attempted. This is actually worse than a malloc failure, since there is no opportunity to handle it. – Unclear

@Brandin: There is no guarantee in the C standard that, if you have sufficient stack space, creating a variable-length array will work. If if there were such a guarantee, it is less useful in most implementations than what they provide for malloc: An attempt to create variable-length arrays will fail and will terminate the program when only a few megabytes have been used, but, if malloc were used, gigabytes of space could be used. Your hypothesized guarantee for variable-length arrays on the stack simply has little practical value. – Unclear

@Brandin: Add to that the fact that most C implementations do not provide any guarantee about how much stack space routines will use, do not provide any assistance in inspecting the result of compilation to see how much they use, and do not support run-time checking of how much stack space has been used (although obviously one could compare the value of the stack pointer to the stack limit provided one has investigated the implementation and used non-standard code). So there is no supported way to guard against a catastrophic failure to create a variable-length array. A program simply aborts. – Unclear

Answer 1

Here's the allocation code (x86 - the x64 code is similar) for the following example line taken from some GCC docs for VLA support:

char str[strlen (s1) + strlen (s2) + 1];

where the calculation for strlen (s1) + strlen (s2) + 1 is in eax (GCC MinGW 4.8.1 - no optimizations):

mov edx, eax
sub edx, 1
mov DWORD PTR [ebp-12], edx
mov edx, 16
sub edx, 1
add eax, edx
mov ecx, 16
mov edx, 0
div ecx
imul    eax, eax, 16
call    ___chkstk_ms
sub esp, eax
lea eax, [esp+8]
add eax, 0
mov DWORD PTR [ebp-16], eax

So it looks to be essentially alloca().

Disposition

I thought alloca is the "fix" to simulate VLA support, but there are some minor differences, like VLA's being GC'ed by block, alloca memory by function – Reliance

@EliasVanOotegem: I think alloca() predates VLA support. Also, alloca() is freed when the function returns, so for example, an alloca() call in a loop will grow the stack. A VLA in a loop will be deallocated and reallocated on each iteration. Also, as mentioned in the GCC doc page for VLAs, alloca() and VLAs don't necessarily play well together (deallocation of a VLA can 'free' alloca() allocations before the function returns). – Disposition

I wonder how this works when -fomit-frame-pointer is passed though – Imbue

@MichaelBurr: Sure alloca predates VLA's, and yes... I said that alloca memory is freed when the function returns (or memory allocated by alloca is valid during for the entire duration of the function, phrased it badly). What I meant to say was that your answer fails to stress that VLA memory is allocated much in alloca memory except for that the array is block scoped rather than function-scoped – Reliance

@dragonroot: if there's a VLA allocation in the function, a stack frame gets created even if -fomit-frame-pointer is used (even with -O2). – Disposition

@HansPassant: I'm guessing that the MinGW folks added a __chkskk_ms function to their libraries to support the same functionality (and to allow linking of MSVC generated object files to the MinGW runtime). – Disposition

This is un-optimized code. No sane compiler will ever use div or imul for compile-time-constant powers of 2, except sometimes with optimization disabled. This only happens because GCC's canned sequence of operations for VLAs gets substituted in after the usual transformation passes that handle compile-time constants. And apparently it's written in terms of x / 16 * 16 instead of x &= -16 to round down to the next multiple of 16. – Taught

Answer 2

Well, these are just a few wild stabs in the dark, based on the restrictions around VLA's, but anyway:

VLA's can't be:

• extern
• struct members
• static
• declared with unspecified bounds (save for function prototype)

All this points to VLA's being allocated on the stack, rather than the heap. So yes, VLA's probably are the last chunks of stack memory allocated whenever a new block is allocated (block as in block scope, these are loops, functions, branches or whatever).
That's also why VLA's increase the risk of Stack overflow, in some cases significantly (word of warning: don't even think about using VLA's in combination with recursive function calls, for example!).
This is also why out-of-bounds access is very likely to cause issues: once the block ends, anything pointing to what Was VLA memory, is pointing to invalid memory.
But on the plus side: this is also why these arrays are thread safe, though (owing to threads having their own stack), and why they're faster compared to heap memory.

The size of a VLA can't be:

• an extern value
• zero or negative

the extern restriction is pretty self evident, as is the non-zero, non-negative one... however: if the variable that specifies the size of a VLA is a signed int, for example, the compiler won't produce an error: the evaluation, and thus allocation, of a VLA is done during runtime, not compile-time. Hence The size of a VLA can't, and needn't be a given during compile-time.
As MichaelBurr rightly pointed out, VLA's are very similar to alloca memory, with one, IMHO, crucial distinction: memory allocated by alloca is valid from the point of allocation, and throughout the rest of the function. VLA's are block scoped, so the memory is freed once you exit the block in which a VLA is used:

void alloca_diff( void )
{
    char *alloca_c, *vla_c;
    for (int i=1;i<10;++i)
    {
        char *alloca_mem = alloca(i*sizeof(*alloca_mem));
        alloca_c = alloca_mem;//valid
        char vla_arr[i];
        vla_c = vla_arr;//invalid
    }//end of scope, VLA memory is freed
    printf("alloca: %c\n", *alloca_c);//fine
    printf("vla: %c\n\", *vla_c);//undefined behaviour... avoid!
}//end of function alloca memory is freed, irrespective of block scope

Reliance