How is the size of a variable length array computed at runtime in C99?

Question

In C89, the length of an array is known at compile time. But in C99, with variable length arrays, the length of an array may be unknown before runtime.

So how does it get computed?

And why couldn't the length of a dynamically allocated array be computed in the same way?

Answer 1

From ISO/IEC 9899:TC3 Section 6.7.5.2: Array declarators

An ordinary identifier (as defined in 6.2.3) that has a variably modified type shall have either block scope and no linkage or function prototype scope. If an identifier is declared to be an object with static storage duration, it shall not have a variable length array type.

The sizeof a VLA is simply sizeof(vla_element_type) * vla_length. Since a VLA can only be defined within a block, its length must be either a local variable or a function parameter, which can be accessed by the compiler when the vla is accessed. (Since the length of vla and the vla itself belongs to the same stack frame).

Here is an example:

int main(int argc, char* argv[])
{
  int m;
  scanf("%d\n", &m);
  int a[m];

  printf("%d\n", sizeof(a));

  return 0;
}

Compiled with clang -o test.ll -O2 -emit-llvm -S test.c, the generated IR is shown as follows:

define i32 @main(i32 %argc, i8** nocapture %argv) nounwind {
entry:
  // Allocate space on stack for m
  %m = alloca i32, align 4  

  // call scanf
  %call = call i32 (i8*, ...)* @__isoc99_scanf(i8* getelementptr inbounds ([4 x i8]* @.str, i32 0, i32 0), i32* %m) nounwind  

  // %0 now contains the value of m
  %0 = load i32* %m, align 4, !tbaa !0

  // %1 is m << 2, which is m * sizeof(int)
  %1 = shl nuw i32 %0, 2  

  // call printf, output m * sizeof(int) to screen.
  %call1 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i32 0, i32 0), i32 %1) nounwind  

  // DONE.
  ret i32 0
}

Answer 2

The difference between a VLA and a malloced array that you hold through a pointer variable (besides living in different parts of the memory) is that the compiler knows at compile time that the first is an array. It can hold the size information(s) in some place along with the VLA, so basically this is some sort of hidden variable(s). Depending on the usage that you do with that variable, if e.g you use sizeof with it or if you index a 2D VLA through something like A[i][j] the compiler can then decide if that hidden variable is really needed, and, if not, optimize it out.