S. Schaeckeler and W. Shang, "Stack Size Reduction of Recursive Programs". In CASES '07: Proceedings of the 2007 International Conference on Compilers, Architecture and Synthesis for Embedded Systems, pages 48-52, New York, NY, USA, 2007. ACM Press.

Abstract - For memory constrained environments like embedded systems, optimization for size is often as important, if not more important than optimization for execution speed. Commonly, compilers try to reduce the code segment size and neglect the stack segment, although the stack can significantly grow during the execution of recursive functions as a separate activation record is required for each recursive call. An activation record holds administrative data like the return address and the stack pointer but also the function's formal parameter list and local variables.

If a formal parameter or local variable is dead at all recursive call points, then it can be declared globally so that only one instance exists independent of the call depth. We found that in 70% of popular recursive algorithms and in all our real world benchmarks, it is possible to reduce the stack size by declaring formal parameters and local variables globally.

Architectures might impose a penalty in code size for accessing global data. On IA32 this stack size reduction starts to materialize for our benchmarks no later than in the fifth recursion.

Categories and Subject Descriptors: D.3.4 [Programming Languages]: Processors---Memory Management (garbage collection), Code Generation, Compilers, Optimization; E.4 [Coding And Information Theory]: Data Compaction and Compression

General Terms: Languages, Performance, Experimentation

Keywords: Embedded systems, stack size reduction, recursion