Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

No stack allocation whole program compilation?

If you write an app that is:

  • Single threaded
  • Has no cycles in call graph
  • Doesn't use alloca or VLAs

Can modern whole program optimizing compilers optimize away all stack allocation (e.g. GCC, MSVC, ICC)? It seems like in those circumstances it should be able to allocate all possible stack space statically. By 'whole program' I mean the compiler has access to /all/ source code (no possiblity of dlopen'ing things at runtime, etc.).

like image 867
Joseph Garvin Avatar asked Apr 09 '12 13:04

Joseph Garvin


1 Answers

If you can guarantee the conditions you stated, then yes: it would be possible to effectively have the stack be completely statically allocated. Each function would have a block of stack memory.

However, will actual compilers do it? No.

It gains absolutely nothing to do so. Indeed, it may gain less than nothing. Often times, much of the working stack is in the cache, so modifications to it are pretty cheap. If the stack were in static memory, then the only time any particular function's "stack" memory would be cached would be if you had recently called that function. Using a real stack, you're more likely to be working in the cache.

Furthermore, giving each function a block of stack memory can easily make your program's static memory usage much larger than it needs to be. The stack is a fixed-size construct; no matter how many functions you have, the stack takes up a certain size. If you have 100,000 functions, and each function takes up 64 bytes of space, then your static "stack" must take up ~6.4MB of space.

Why? You're never going to be using most of that memory at any one time. The program would run just fine in a 1MB or even 512KB stack; why take up 6x that memory for nothing?

So it is both not a performance optimization and can bloats your program's memory.

like image 196
Nicol Bolas Avatar answered Sep 29 '22 03:09

Nicol Bolas