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?

Are you asking how this is implemented, or why does it compile given that it isn't legal C++? — juanchopanza, Mar 13 '14 at 18:01

Kerrek SB · Accepted Answer · 2014-03-13T18:16:20.563

7

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).

edited Mar 13 '14 at 18:16

answered Mar 13 '14 at 18:02

Kerrek SB

464,522
92
875
1,084

It did get added to C++ and the problems were solved (see [N3639](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3639.html)), but was pulled out and moved to a TS covering array extensions – Jonathan Wakely Mar 13 '14 at 18:37
@JonathanWakely As I understand it, the proposal was split off into a seperate TS because after it was approved enough updates kept getting made to indicate that it wasn't really finished or stable enough to be confident that everything had really been solved the right ways. – bames53 Mar 13 '14 at 18:43
If arrays behaved sanely in the first place (e.g., no pointer decay) then dynamic arrays in C++ would probably be much easier because the type system would actually help, rather than actively obstruct. – bames53 Mar 13 '14 at 18:44
@bames53: You still have the problem that you need to introduce a notion of "types that are only defined dynamically". Yes, array-new has the same problem, but with array-new you never see the actual object, only its first element. In C you can see how `sizeof` suddenly becomes a whole lot more complex because of VLAs... – Kerrek SB Mar 13 '14 at 18:58
@bames53, The array of runtime bound (ARB) proposal didn't have problems. There were updates to `std::dynarray`, not ARBs, but some people felt strongly that the two features were coupled and if `dynarray` was moved to a TS then ARBs must be too. So now we have a TS on array extensions. – Jonathan Wakely Mar 13 '14 at 19:13
@KerrekSB Dynamic arrays can have a statically determined type. They don't need to share types with static arrays. – bames53 Mar 13 '14 at 20:39

Hristo Iliev · Answer 2 · 2014-03-13T20:09:25.233

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).

`alloca` is not part of the C standard library. – Kerrek SB Mar 13 '14 at 19:00 — Kerrek SB, Mar 13 '14 at 19:00
@KerrekSB, true - fixed. – Hristo Iliev Mar 13 '14 at 20:11 — Hristo Iliev, Mar 13 '14 at 20:11

How does gcc allocate statically run time known length of array

2 Answers2