Note: The same question also applies for alloca.

First, alloca() is a much simpler mechanism that usually does not require storing the size of the allocated memory. Eg:

int main() {
    const int N = 1000*1000;
    const int M = 1009;
    int s = 0;
    for (int i = 0; i < N; i++) {
        int l = 1 + rand()%M;
        int *a = alloca(sizeof(int)*l);
        for (int j = 0; j < l; j++) {
            a[j] = rand();
        }
        for (int j = 0; j < l; j++) {
            s += a[j];
        }
    }
    return s == 0;
}

For large values of N, this code leads to a stack overflow. But with small values of N, all allocated memory is freed when exiting the main() function by freeing the frame on the stack. It is easy to see that when using the alloca() function in this way, the -fomit-frame-pointer key is ignored.

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?

VLA is a much more complex and precise mechanism, for example:

int main() {
    const int N = 1000*1000;
    const int M = 1009;
    int s = 0;
    for (int i = 0; i < N; i++) {
        int a[1+ rand()%M];
        for (size_t j = 0; j < sizeof(a)/sizeof(a[0]); j++) {
            a[j] = rand();
        }
        for (size_t j = 0; j < sizeof(a)/sizeof(a[0]); j++) {
            s += a[j];
        }
    }
    return s == 0;
}

At each iteration of the loop, memory on the stack is allocated and released. In this case, the size of this memory is not saved, the stack returns to the frame. But in more complex cases and/or when using other compilers, who knows? Depends on the implementation.

However, at least the debugging information contains information about VLA arrays.