Link-time compaction and optimization of ARM executables

ABSTRACT

The overhead in terms of code size, power consumption, and execution time caused by the use of precompiled libraries and separate compilation is often unacceptable in the embedded world, where real-time constraints, battery life-time, and production costs are of critical importance. In this paper, we present our link-time optimizer for the ARM architecture. We discuss how we can deal with the peculiarities of the ARM architecture related to its visible program counter and how the introduced overhead can to a large extent be eliminated. Our link-time optimizer is evaluated with four tool chains, two proprietary ones from ARM and two open ones based on GNU GCC. When used with proprietary tool chains from ARM Ltd., our link-time optimizer achieved average code size reductions of 16.0 and 18.5%, while the programs have become 12.8 and 12.3% faster, and 10.7 to 10.1% more energy efficient. Finally, we show how the incorporation of link-time optimization in tool chains may influence library interface design.

REFERENCES

• 1: Federico Angiolini , Francesco Menichelli , Alberto Ferrero , Luca Benini , Mauro Olivieri, A post-compiler approach to scratchpad mapping of code, 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.1023869]
• 2: ARM Ltd. 1995. An Introduction to Thumb. ARM Ltd.
• 3: ARM Ltd. 2005. ELF for the ARM Architecture. ARM Ltd.
• 4: Todd Austin , Eric Larson , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]
• 5: Árpád Beszédes , Rudolf Ferenc , Tibor Gyimóthy , André Dolenc , Konsta Karsisto, Survey of code-size reduction methods, ACM Computing Surveys (CSUR), v.35 n.3, p.223-267, September 2003 [doi>10.1145/937503.937504]
• 6: 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
• 7: Guilin Chen , Mahmut Kandemir, Optimizing Address Code Generation for Array-Intensive DSP Applications, Proceedings of the international symposium on Code generation and optimization, p.141-152, March 20-23, 2005 [doi>10.1109/CGO.2005.23]
• 8: Cohn, R., Goodwin, D., Lowney, P., and Rubin, N. 1997. Spike: An optimizer for Alpha/NT executables. In Proceedings of the USENIX Windows NT Workshop. 17--24.
• 9: Marc L. Corliss , E. Christopher Lewis , Amir Roth, A DISE implementation of dynamic code decompression, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 10: De Bus, B. 2005. Reliable, retargetable and extensible link-time program rewriting. Ph.D. thesis, Ghent University.
• 11: Bruno De Bus , Daniel Kästner , Dominique Chanet , Ludo Van Put , Bjorn De Sutter, Post-pass compaction techniques, Communications of the ACM, v.46 n.8, August 2003 [doi>10.1145/859670.859696]
• 12: Bruno De Bus , Dominique Chanet , Bjorn De Sutter , Ludo Van Put , Koen De Bosschere, The design and implementation of FIT: a flexible instrumentation toolkit, Proceedings of the 5th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08, 2004, Washington DC, USA [doi>10.1145/996821.996833]
• 13: De Sutter, B., De Bus, B., De Bosschere, K., Keyngnaert, P., and Demoen, B. 2000. On the static analysis of indirect control transfers in binaries. In Proc. of the International Conference on Parallel and Distributed Processing Techniques and Applications. 1013--1019.
• 14: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere , Saumya Debray, Combining Global Code and Data Compaction, Proceedings of the 2001 ACM SIGPLAN workshop on Optimization of middleware and distributed systems, p.29-38, August 2001, Snow Bird, Utah, United States
• 15: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere, Sifting out the mud: low level C++ code reuse, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 16: Bjorn de Sutter , Bruno de Bus , Koen de Bosschere, Bidirectional liveness analysis, or how less than half of the alpha's registers are used, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.10, p.535-548, October 2006 [doi>10.1016/j.sysarc.2006.03.001]
• 17: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere, Link-time binary rewriting techniques for program compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.5, p.882-945, September 2005 [doi>10.1145/1086642.1086645]
• 18: Bjorn De Sutter , Hans Vandierendonck , Bruno De Bus , Koen De Bosschere, On the side-effects of code abstraction, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 19: Saumya K. Debray , William Evans , Robert Muth , Bjorn De Sutter, Compiler techniques for code compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.378-415, March 2000 [doi>10.1145/349214.349233]
• 20: Jens Ernst , William Evans , Christopher W. Fraser , Todd A. Proebsting , Steven Lucco, Code compression, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.358-365, June 16-18, 1997, Las Vegas, Nevada, United States
• 21: Michael Franz, Adaptive Compression of Syntax Trees and Iterative Dynamic Code Optimization: Two Basic Technologies for Mobile Object Systems, Selected Presentations and Invited Papers Second International Workshop on Mobile Object Systems - Towards the Programmable Internet, p.263-276, July 08-09, 1996
• 22: Michael Franz , Thomas Kistler, Slim binaries, Communications of the ACM, v.40 n.12, p.87-94, Dec. 1997 [doi>10.1145/265563.265576]
• 23: Christopher W. Fraser, Automatic inference of models for statistical code compression, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.242-246, May 01-04, 1999, Atlanta, Georgia, United States
• 24: Steve B. Furber, ARM System Architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 25: Gadi Haber , Moshe Klausner , Vadim Eisenberg , Bilha Mendelson , Maxim Gurevich, Optimization opportunities created by global data reordering, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 26: Daniel Kästner, PROPAN: A Retargetable System for Postpass Optimisations and Analyses, Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, p.63-80, June 18, 2000
• 27: Daniel Kästner , Stephan Wilhelm, Generic control flow reconstruction from assembly code, 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
• 28: T. M. Kemp , R. K. Montoye , J. D. Harper , J. D. Palmer , D. J. Auerbach, A decompression core for powerPC, IBM Journal of Research and Development, v.42 n.6, p.807-812, November 1998
• 29: Darko Kirovski , Johnson Kin , William H. Mangione-Smith, Procedure based program compression, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.204-213, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 30: Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
• 31: Haris Lekatsas , Jörg Henkel , Srimat Chakradhar , Venkata Jakkula , Murugan Sankaradass, CoCo: a hardware/software platform for rapid prototyping of code compression technologies, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775912]
• 32: Levine, J. 2000. Linkers & Loaders. Morgan Kaufmann Publishers, San Mateo, CA.
• 33: Chi-Keung Luk , Robert Muth , Harish Patil , Robert Cohn , Geoff Lowney, Ispike: A Post-link Optimizer for the Intel®Itanium®Architecture, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.15, March 20-24, 2004, Palo Alto, California
• 34: Robert Michael Muth , Saumya K. Debray, Alto: a platform for object code modification, 1999
• 35: Robert Muth , Saumya K. Debray , Scott Watterson , Koen De Bosschere, Alto: a link-time optimizer for the Compaq alpha, Software—Practice & Experience, v.31 n.1, p.67-101, Jan. 2001 [doi>10.1002/1097-024X(200101)31:1<67::AID-SPE357>3.0.CO;2-A]
• 36: William Pugh, Compressing Java class files, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.247-258, May 01-04, 1999, Atlanta, Georgia, United States
• 37: Amitabh Srivastava , David W. Wall, Link-time optimization of address calculation on a 64-bit architecture, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.49-60, June 20-24, 1994, Orlando, Florida, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

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

Keywords:
Performance, compaction, linker, optimization