Eliminating the call stack to save RAM

ABSTRACT

Most programming languages support a call stack in the programming model and also in the runtime system.We show that for applications targeting low-power embedded microcontrollers (MCUs), RAM usage can be significantly decreased by partially or completely eliminating the runtime callstack. We present flattening, a transformation that absorbs a function into its caller, replacing function invocations and returns with jumps. Unlike inlining, flattening does not duplicate the bodies of functions that have multiple callsites. Applied aggressively, flattening results in stack elimination. Flattening is most useful in conjunction with a lifting transformation that moves global variables into a local scope.

Flattening and lifting can save RAM. However, even more benefit can be obtained by adapting the compiler to cope with properties of flattened code. First, we show that flattening adds false paths that confuse a standard live variables analysis. The resulting problems can be mitigated by breaking spurious live-range conflicts between variables using information from the unflattened callgraph. Second, we show that the impact of high register pressure due to flattened and lifted code, and consequent spills out of the register allocator, can be mitigated by improving a compiler's stack layout optimizations. We have implemented both of these improvements in GCC, and have implemented flattening and lifting as source-to-source transformations. On a collection of applications for the AVR family of 8-bit MCUs, we show that total RAM usage can be reduced by 20% by compiling flattened and lifted programs with our improved GCC.

REFERENCES

• 1: Martín Abadi , Mihai Budiu , Úlfar Erlingsson , Jay Ligatti, Control-flow integrity, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102165]
• 2: C. Scott Ananian , Martin Rinard, Data size optimizations for java programs, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 3: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 4: Lan S. Bai , Lei Yang , Robert P. Dick, Automated compile-time and run-time techniques to increase usable memory in MMU-less embedded systems, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176777]
• 5: Volker Barthelmann, Inter-task register-allocation for static operating systems, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 6: Surupa Biswas , Matthew Simpson , Rajeev Barua, Memory overflow protection for embedded systems using run-time checks, reuse and compression, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023872]
• 7: Dennis Brylow , Niels Damgaard , Jens Palsberg, Static checking of interrupt-driven software, Proceedings of the 23rd International Conference on Software Engineering, p.47-56, May 12-19, 2001, Toronto, Ontario, Canada
• 8: Dominique Chanet , Bjorn De Sutter , Bruno De Bus , Ludo Van Put , Koen De Bosschere, System-wide compaction and specialization of the linux kernel, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 9: Trishul M. Chilimbi , Bob Davidson , James R. Larus, Cache-conscious structure definition, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.13-24, May 01-04, 1999, Atlanta, Georgia, United States
• 10: Keith D. Cooper , Mary W. Hall , Linda Torczon, An experiment with inline substitution, Software—Practice & Experience, v.21 n.6, p.581-601, June 1991 [doi>10.1002/spe.4380210604]
• 11: Keith D. Cooper, Mary W. Hall, and Ken Kennedy. A methodology for procedure cloning. Computer Languages, 19(2):105--118, April 1993.
• 12: Nathan Dean Cooprider , John David Regehr, Offline compression for on-chip ram, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 13: J. Engblom, Static Properties of Commercial Embedded Real-Time Programs, and Their Implication for Worst-Case Execution Time Analysis, Proceedings of the Fifth IEEE Real-Time Technology and Applications Symposium, p.46, June 02-04, 1999
• 14: Aurélien Francillon , Claude Castelluccia, Code injection attacks on harvard-architecture devices, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA [doi>10.1145/1455770.1455775]
• 15: Jack G. Ganssle, Art of Designing Embedded Systems, Butterworth-Heinemann, Newton, MA, 1999
• 16: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 17: Dirk Grunwald , Richard Neves, Whole-program optimization for time and space efficient threads, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.50-59, October 01-04, 1996, Cambridge, Massachusetts, United States
• 18: Håkon A. Hjortland. Laser video projector. http://heim.ifi.uio.no/haakoh/avr/.
• 19: Chris Lattner , Vikram S. Adve, Transparent pointer compression for linked data structures, Proceedings of the 2005 workshop on Memory system performance, June 12-12, 2005, Chicago, Illinois [doi>10.1145/1111583.1111587]
• 20: Vladimir N. Makarov. The integrated register allocator for GCC. In Proc. of the GCC Developers' Summit, pages 77--90, Ottawa, Canada, July 2007. URL http://ols.fedoraproject.org/GCC/Reprints-2007/makarov-reprint.pdf.
• 21: William P. McCartney , Nigamanth Sridhar, Abstractions for safe concurrent programming in networked embedded systems, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182825]
• 22: Bhuvan Middha , Matthew Simpson , Rajeev Barua, MTSS: multi task stack sharing for embedded systems, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086323]
• 23: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 24: Ozcan Ozturk , Mahmut Kandemir , Mary Jane Irwin, Increasing on-chip memory space utilization for embedded chip multiprocessors through data compression, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084860]
• 25: Paparazzi. The Paparazzi project, 2006. http://www.nongnu.org/paparazzi.
• 26: Rodric M. Rabbah , Krishna V. Palem, Data remapping for design space optimization of embedded memory systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.2, p.186-218, May 2003 [doi>10.1145/643470.643474]
• 27: John Regehr, Alastair Reid, and Kirk Webb. Eliminating stack overflow by abstract interpretation. In Proc. of the 3rd Intl. Conf. on Embedded Software (EMSOFT), pages 306--322, Philadelphia, PA, October 2003.
• 28: TinyOS. tinyos.net. http://www.tinyos.net.
• 29: Ben L. Titzer, Virgil: objects on the head of a pin, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 30: Ben L. Titzer , Daniel K. Lee , Jens Palsberg, Avrora: scalable sensor network simulation with precise timing, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 31: Christian Wawersich, Michael Stilkerich, and Wolfgang Schröder-Preikschat. An OSEK/VDX-based Multi-JVM for automotive appliances. In Proc. of the Intl. Embedded Systems Symposium, Irvine, CA, 2007.
• 33: Lei Yang, Robert P. Dick, Haris Lekatsas, and Srimat Chakradhar. On-line memory compression for embedded systems. ACM Trans. Embedded Computing Systems (TECS), 2006.
• 34: Youtao Zhang , Rajiv Gupta, Compressing heap data for improved memory performance: Research Articles, Software—Practice & Experience, v.36 n.10, p.1081-1111, August 2006 [doi>10.1002/spe.v36:10]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Languages, Performance

Keywords:
compiler optimization, embedded software, memory allocation, memory optimizations, sensor networks, stack liveness