How does gcc allocate statically run time known length of array

Question

I wrote the following code:

int tester(int n)
{
    int arr[n];
    // ...
}

This code compiled, no warnings, using g++.

My question is - how? The parameter n is known just in runtime, in the array is statically allocated. How does gcc compile this?

Answer 1

This is an extension that GCC offers for C++, though variable-length arrays ("VLAs") are properly supported by C since C99.

The implementation isn't terribly hard; on a typical call-stack implementation, the function only needs to save the base of the stack frame and then advance the stack pointer by the dynamically specified amount. VLAs always come with the caveat that if the number is too large, you get undefined behaviour (manifesting in Stack Overflow), which makes them much tricker to use right than, say, std::vector.

There had at some point been an effort to add a similar feature to C++, but this turns out surprisingly difficult in terms of the type system (e.g. what is the type of arr? How does it get deduced in function templates?). The problems are less visible in C which has a much simpler type system and object model (but that said, you can still argue that C is worse off for having VLAs, a considerable part of the standard is spent on them, and the language would have been quite a bit simpler without them, and not necessarily poorer for it).

Answer 2

The GNU C library provides a function to allocate memory on the stack - alloca(3). It simply decrements the stack pointer thus creating some scratch space on it. GCC uses alloca(3) to implement C99 variable-length arrays - it first decrements the stack pointer in the function prologue to create space for all automatic variables, whose size is known at compile time, and then uses alloca(3) to further decrement it and make space for arr with size as determined at run-time. The optimiser might actually fuse both decrements.

int tester(int n)
{
   int arr[n];
   return 0;
}

compiles into

;; Function tester (tester)

tester (int n)
{
  int arr[0:D.1602D.1602] [value-expr: *arr.1];
  int[0:D.1602D.1602] * arr.1;
  long unsigned int D.1610D.1610;
  int n.0;
  ...

<bb 2>:
  n.0 = n;
  ...
  D.1609D.1609 = (long unsigned int) n.0;
  D.1610D.1610 = D.1609D.1609 * 4;
  D.1612D.1612 = __builtin_alloca (D.1610D.1610); <----- arr is allocated here
  arr.1 = (int[0:D.1602D.1602] *) D.1612D.1612;
  ...

That's equivalent to the following C code:

int tester(int n)
{
   int *arr = __builtin_alloca(n * sizeof(int));
   return 0;
}

__builtin_alloca() is GCC's internal implementation of alloca(3).