3 ms·

A good compiler would focus optimization efforts on removing variables from the stack. It would probably just reject programs that get silly with deep recursion

by burfog 7y ago

A good compiler would focus optimization efforts on removing variables from the stack. It would probably just reject programs that get silly with deep recursion. For example, if the compiler can prove that a function never gets more than one active stack frame (no recursion) then the local variables don't need to be on a stack. They can be in the data section. If the compiler can prove this for two functions together, such that they will never both have active stack frames, then the variables can reside in the same memory. Going beyond this, partial sharing is possible. If function X calls function Y, the variables of function Y can reside in the locations of many of the variables of function X. It is only the variables of function X that must survive the call to Y that would need distinct memory locations. Inlining can help too. That gets rid of the need to push a return address and so on.

duskwuff 7y ago
I'm not sure that's a valid set of optimizations. It's certainly incompatible with a compile-then-link workflow involving multiple object files, as there's no way to safely allocate local variables across modules. Nor is this approach compatible with function pointers!
- burfog 7y ago
  I know that moving stack variables to the data section is in fact an optimization that is in use by commercial compilers. It works fine with function pointers. There are two possible answers to the problem of a compile-then-link workflow involving multiple object files. The first is that the optimization can be limited to within one file. Calls going between source files can sometimes limit the optimization opportunity because it may become impossible to prove that there is no mutual recursion. Functions that may be involved in recursion can not be optimized in this way. One might add a #pragma to override the compiler's determination of safety. The second possible answer is to have the link phase do the real compiling. The supposed compile phase just preprocesses and verifies syntax. Function pointers certainly liven things up. Suppose the function pointer of type *X is used to call a function of type X, which then exclusively calls functions of type Y. If we know that none of those type Y functions end up calling any type X functions, then that first-mentioned function of type X will not get more than one stack frame. It is thus safe to optimize with that assumption.

by burfog 7y ago

duskwuff 7y ago

I'm not sure that's a valid set of optimizations. It's certainly incompatible with a compile-then-link workflow involving multiple object files, as there's no way to safely allocate local variables across modules. Nor is this approach compatible with function pointers!

burfog 7y ago
I know that moving stack variables to the data section is in fact an optimization that is in use by commercial compilers. It works fine with function pointers. There are two possible answers to the problem of a compile-then-link workflow involving multiple object files. The first is that the optimization can be limited to within one file. Calls going between source files can sometimes limit the optimization opportunity because it may become impossible to prove that there is no mutual recursion. Functions that may be involved in recursion can not be optimized in this way. One might add a #pragma to override the compiler's determination of safety. The second possible answer is to have the link phase do the real compiling. The supposed compile phase just preprocesses and verifies syntax. Function pointers certainly liven things up. Suppose the function pointer of type *X is used to call a function of type X, which then exclusively calls functions of type Y. If we know that none of those type Y functions end up calling any type X functions, then that first-mentioned function of type X will not get more than one stack frame. It is thus safe to optimize with that assumption.