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.
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().
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
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).
-fomit-frame-pointer is passed though__chkskk_ms function to their libraries to support the same functionality (and to allow linking of MSVC generated object files to the MinGW runtime).
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.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:
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:
extern valuethe 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
VLA works by placing the array in the stack- stackoverflow.com/questions/2034712/variable-length-arrays. That is also what I see when checking the assembly output generated by gcc when using a VLA, no call tomalloc. But it might depend on the actual implementation.mallocto 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.mallocare guaranteed to work indefinitely. In most common C implementations, usingmallocfor 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.