In C, you can do this:
int arr[i];
From what I understand, this is called a VLA—variable length array—which is an array whose size is not known at compile time, which in most implementations is stored on the stack.
In the implementations of VLAs that store the array on the stack, do they store the size of the array somewhere at runtime? If yes, where? If not, how do you know at runtime how much to decrement the stack pointer once the array goes out of scope?
Note: The same question also applies for alloca.
In C, you can do this:
int arr[i];
From what I understand, this is called a VLA—variable length array—which is an array whose size is not known at compile time, which in most implementations is stored on the stack.
In the implementations of VLAs that store the array on the stack, do they store the size of the array somewhere at runtime? If yes, where? If not, how do you know at runtime how much to decrement the stack pointer once the array goes out of scope?
Note: The same question also applies for alloca.
The compiler can store the size anywhere it sees fit, it is usually going to be in the stack or in some register just like a variable. Here is an example:
#include <stddef.h>
size_t g();
void f()
{
volatile char arr1[g()];
for (size_t i = 0; i < sizeof(arr1); ++i)
arr1[i] = 0;
}
GCC compiles the code above to this x64 code:
f:
push rbp
xor eax, eax
mov rbp, rsp
call g
lea rdx, [rax+15]
and rdx, -16
sub rsp, rdx
test rax, rax
je .L1
mov rcx, rsp
xor edx, edx
test al, 1
je .L3
mov BYTE PTR [rsp], 0
mov edx, 1
cmp rax, 1
je .L1
.L3:
mov BYTE PTR [rcx+rdx], 0
mov BYTE PTR [rcx+1+rdx], 0
add rdx, 2
cmp rax, rdx
jne .L3
.L1:
leave
ret
This C code creates a VLA using the result of calling a function g defined elsewhere. Since in x64 Linux functions return integers in rax, the compiler uses the value in rax to calculate a new size for the stack frame. Then it uses rax in the loop condition because the array’s size was already there anyway:
add rdx, 2
cmp rax, rdx
jne .L3
So in this case the array’s size stays always in rax.
In general, if the array size is calculated at runtime the compiler can simply reuse the same register where the final calculation is. It might also move it to the stack if it decides to use the register for something else. So in the generated machine code the size of a VLA behaves just like a variable.
That being said, the above Assembly code shows how you don’t need the size of the array to undo the new stack frame. The stack frame is created by pushing the base pointer rbp onto the stack, moving the value in the stack pointer rsp to rbp and then decrementing rsp. When returning we simply move the value in rbp back to rsp, making rsp point to the top of the stack where the previous value of rbp was, then we pop the value from the top of the stack back into rbp. This is what the leave instruction does.
in the implementations of VLAs that store the array on the stack, do they store the size of the array somewhere at runtime?
sizeof reports the sizes of VLAs, which are known only at runtime, so it must be possible to evaluate VLA sizes at runtime. Regardless of where a VLA is stored, then, if and as long as there is a potential for an lvalue designating that array to be the operand of a sizeof operator, either the VLA's size or an equivalent must be preserved somewhere in the program's state.
Moreover, during the lifetime of a VLA, the program must ensure that it does not use its storage for anything else. That does not necessarily require tracking a direct equivalent of its size, but certainly something related must be stored, if only as, say, the value of the stack pointer.
If yes, where?
It's unlikely that different implementations are wholly consistent about the details, but VLAs can be declared only at block scope, so with automatic storage duration. Given that, and the fact that there is no defined way to access an object containing their size, it is plausible that an implementation would satisfy a need to preserve VLA sizes with the same kind of storage that they would an automatic variable with register storage class. That does not necessarily mean a CPU register as the storage, but that's one possibility. The stack is another possibility. An indirect representation such as in the value of the stack pointer is another. On the other hand, where there is no chance that the size could be required by a sizeof expression, it might not be preserved in a recoverable manner at all.
If not, how do you know at runtime how much to decrement the stack pointer once the array goes out of scope?
In a typical stack-based machine, a called function does not rely on tracking the number of bytes of stack it is using so as to be able release that memory. Rather, it has the address of the start of its stack frame (the stack base), and on termination, it adjusts the stack pointer to equal its base pointer. The caller's own stack base will be restored as well, in a manner specific to machine architecture and calling convention.
Note: The same question also applies for alloca.
alloca() is a GNU extension, not part of standard C. It is distinguished from the VLA case by not engaging any special sizeof behavior that would require the size of the allocated object to be recoverable at runtime. However, it places the same requirement that the implementation needs to retain enough information to avoid using the allocated object's storage for anything else during that object's lifetime. That might be stored in any of the ways discussed for VLAs, but it is more likely to take a form that does not afford recovering the exact size.
The run-time size of the array can be obtained using sizeof arr. This will result in the same value as i * sizeof *arr (assuming i hasn't been changed), and it could very well result in the same code. Or not. How it obtains the size is not important.
If not, how do you know at runtime how much to decrement the stack pointer once the array goes out of scope?
The size of the array is not needed for this. A stack frame can be removed by simply restoring the stack pointer to its previous value.
This is what happens with gcc on an x86_64. Note the leave instruction achieving this in this example.
My question is, in the implementations of VLAs that store the array on the stack, do they store the size of the array somewhere at runtime?
Yes, if it is needed. Effectively, the compiler creates a variable whose name you do not know and stores the size of the array in it. (This is not specified by the C standard, but we can see the effects are equivalent: A user-declared automatic variable retains a run-time value, and that is just what is needed for the size of a variable length array.)
There are embellishments on this. If you define int A[2*n+3]; and then use A without applying sizeof to it, then, once the compiler has allocated stack space for it, it no longer needs to know the size of the array except to release the stack space. It is as if you wrote this code:
size_t SizeOfA = 2*n+3;
int A[SizeOfA];
… Some loop that uses a[i]…
foo(SizeOfA, A);
In that code, the compiler needs to keep SizeOfA at least until the call to foo, since it is passed as an argument. Similarly, if you wrote foo(sizeof A, A);, the compiler would need to keep its hidden hypothetical variable until the call to foo. But if you did not have the call to foo in that code, then optimization could discard the SizeOfA variable since it is never used. Similarly, the compiler can discard its hypothetical variable since it is never used (because it may have another way to release the stack space, per below).
If yes, where?
Likely the size of an array is treated as just one more thing the compiler has to keep track of in a routine, along with user variable, and it is subject to optimization just like anything else.
Also note that, if you have int A[2*n+3];, the compiler does not need to keep the size if it can recalculate it from n, which it can do if n does not change (or it keeps a copy). This would all be up to optimization and other software inside the compiler.
If not, how do you know at runtime how much to decrement the stack pointer once the array goes out of scope?
It is common to have a frame pointer that is a copy of the stack pointer made at the time the routine was started (or some fixed point relative to the start of the routine, such as just after doing some stack housekeeping). If we have a saved frame pointer, everything that the routine pushed onto the stack can be popped simply by copying the frame pointer to the stack pointer.
If we do not have a frame pointer, then the amount to adjust the stack pointer can be calculated from the hypothetical variable described above.
Things get more complicated if you have variable length arrays inside nested blocks that may or may not get executed, due to if statements or other control statements. You can still pop everything with a frame point, but are you going to keep everything that was allocated inside a nested block between the time the block is exited and the time the function returns? Or are you going to pop the variable length arrays when the block is exited? Do you do that by calculating space or by making copies of the stack pointer when such blocks are entered?
You said:
In C you can do this:
int arr[i];
You wrote it!!!! (in i you have the number of elements
sizeof arr. – chux Commented Jan 30 at 17:15sizeofis called). – Eugene Sh. Commented Jan 30 at 17:23sizeofoperator to get its size. Look at the assembly code generated by the compiler to see how it calculates the size for the `sizeof`` operation. Check with both unoptimized and optimized builds to see what the compiler is doing. Remember to actually do something with both the array and the size, so the compiler won't optimize it to an empty program. – Some programmer dude Commented Jan 30 at 17:24