How does the gcc determine stack size the function

Question

I write program in C programming language, and I use objdump to translate the executable file to asm file. I have no idea how gcc determine the stack size the function will use?

    int a()
    {
         int temp[1024 * 1024];
         temp[0] = 1;
         return temp[0];
    }

It's just for problem explanation, ignore that it's naïve. Will the gcc allocate really 1024 * 1024 bytes space for function a?

If the function is a little complicated, sometimes a lot of local variables, how does the compiler determine the stack size?

Answer 1

How does the gcc determine stack size the function based on C will use?

It does so by looking at the size of the variables used and adding them. (As a first approximation, anyway. For performance and correctness reasons, alignment and padding and whatever else might be added to the allocated amount as well.)

Will the gcc allocate really 1024 * 1024 bytes space for function a?

If you tell it to do so (you disable optimizations), it most probably will. (Not 1024 * 1024 bytes, though -- rather 1024 * 1024 * sizeof(int) bytes. At least.) But you can just go ahead and compile it and look at the generated assembly.

But your function is quite a simple one, and its behavior is trivial to reason about, so I'd expect any decent compiler to optimize away the array declaration. (But again, look at what actual assembly it outputs. It might vary from version to version, with flags, with platforms, etc.)

If the function is a little complicate, sometimes a lot of local variables, how does the compiler determine the stack size?

The complexity of your function does not matter. If it's too complicated, then maybe the compiler can do less optimizations. But it definitely can compute the upper bound of the necessary memory by - naively - adding all the sizes of the variables used.

Answer 2

First, at least without optimizations, GCC will emit code that allocates 1024*1024 int-s (not bytes; often an int is 4 bytes because sizeof(int)==4) on the call stack (i.e. 4Mbytes!). This might be too much, and you might get a segmentation fault because of the stack overflow. See also the setrlimit(2) and execve(2) syscalls.

Some versions of GCC are able to optimize your code. On Linux/Debian/Sid/x86-64 the gcc-4.8 -O3 -fverbose-asm -S stonestrong.c command (actually using GCC 4.8.2) is able to optimize your code to:

    .globl  a
    .type   a, @function
a:
.LFB0:
    .cfi_startproc
    movl    $1, %eax    #,
    ret
    .cfi_endproc
.LFE0:
.size   a, .-a

So in your particular case, no stack frame at all is needed when optimizing with -O3.

The compiler determines the stack size and layout using quite complex optimization algorithms. Each function usually has its own stack frame. When the compiler is optimizing, a given slot of the call frame might be used for several source code variables, and a given source variable might not need any stack slot (because it could be kept in a register), or maybe use several of them (one slot for a block, another for another, etc...).

You may want to explore the various internal representations (notably Gimple) used by GCC by passing -fdump-tree-all (which will dump hundreds of files!) to your gcc command. You may want to use MELT to extend GCC (by adding your new passes) or inspect the internal representations.

Some variables or some intermediate values are not even kept on the stack, but only in register. The compiler works hard (when optimizing) on register allocation (which is a difficult question having its own experts). See also this.

A general rule of thumb when coding in C (or in C++) is to avoid too large call frames; often, you want your local variables to consume no more than a few kilobytes at most.

Program optimization can be very hard; however current compilers are quite good at optimization like the one above. With GCC you need to enable optimizations (e.g. with -O2 or -O3 and many other flags) explicitly. GCC has more than ten millions lines of source code, and half of them are middle-end optimizations (not depending on the source language or the target processor).