Link-time binary rewriting techniques for program compaction

ABSTRACT

Small program size is an important requirement for embedded systems with limited amounts of memory. We describe how link-time compaction through binary rewriting can achieve code size reductions of up to 62&percent; for statically bound languages such as C, C++, and Fortran, without compromising on performance. We demonstrate how the limited amount of information about a program at link time can be exploited to overcome overhead resulting from separate compilation. This is done with scalable, cost-effective, whole-program analyses, optimizations, and duplicate code and data elimination techniques. The discussed techniques are evaluated and their cost-effectiveness is quantified with Squeeze++, a prototype link-time compactor.

REFERENCES

• 1: Ole Agesen , David Ungar, Sifting out the gold: delivering compact applications from an exploratory object-oriented programming environment, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.355-370, October 23-28, 1994, Portland, Oregon, United States
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: 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
• 4: Anckaert, B., Vandeputte, F., De Bus, B., De Sutter, B., and De Bosschere, K. 2004. Link-time optimization of IA64 binaries. In Proceedings of the Euro-Par 2004 Conference. 284--291.
• 5: Baker, B. and Manber, U. 1998. Deducing similarities in Java sources from bytecodes. In Proceedings of the USENIX Annual Technical Conference. Usenix, Berkeley, CA, 179--190.
• 6: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 7: Á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]
• 8: Gary Bray, Sharing code among instances of Ada generics, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.276-284, June 17-22, 1984, Montreal, Canada
• 9: Burger, D. and Austin, T. 1997. The simplescalar toolset, version 2.0. Tech. Rep. TR-97-1342, University of Wisconsin-Madison, Madison, WI.
• 10: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Wen-mei W. Hwu, Profile-guided automatic inline expansion for C programs, Software—Practice & Experience, v.22 n.5, p.349-369, May 1992 [doi>10.1002/spe.4380220502]
• 11: Cheung, W., Evans, W., and Moses, J. 2003. Predicated instructions for code compaction. In Proceedings of the 7th International Workshop on Software and Compilers for Embedded Systems (SCOPES). Lecture Notes in Computer Science, vol. 2826. Springer, Berlin, Germany, 17--32.
• 12: Lars Ræder Clausen , Ulrik Pagh Schultz , Charles Consel , Gilles Muller, Java bytecode compression for low-end embedded systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.471-489, May 2000 [doi>10.1145/353926.353933]
• 13: 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.
• 14: Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.139-149, May 01-04, 1999, Atlanta, Georgia, United States
• 15: 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
• 16: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 17: Bruno De Bus , Bjorn De Sutter , Ludo Van Put , Dominique Chanet , Koen De Bosschere, Link-time optimization of ARM binaries, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 18: 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
• 19: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere , Saumya Debray, Combining Global Code and Data Compaction, Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems, p.29-38, August 2001, Snow Bird, Utah, United States
• 20: 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 Proceedings of the 2000 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA). 1013--1019.
• 21: 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
• 22: Saumya Debray , William Evans, Profile-guided code compression, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 23: 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]
• 24: Saumya Debray , Robert Muth , Matthew Weippert, Alias analysis of executable code, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-24, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268948]
• 25: 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
• 26: William S. Evans , Christopher W. Fraser, Bytecode compression via profiled grammar rewriting, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.148-155, June 2001, Snowbird, Utah, United States
• 27: Ferdinand, C. 2001. Post pass code compaction at the assembly level for c16x. CONTACT, Infineon Technologies Development Tool Partners 3, 9, 35--36.
• 28: Flower, R., Luk, C.-K., Muth, R., Patil, H., Shakshober, J., Cohn, R., and P. G., L. 2001. Kernel optimizations and prefetch with the spike executable optimizer. In Proceedings of the 4th Workshop on Feedback-Directed and Dynamic Optimization (“FDDO-4”).
• 29: 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
• 30: Michael Franz, Dynamic Linking of Software Components, Computer, v.30 n.3, p.74-81, March 1997 [doi>10.1109/2.573670]
• 31: Michael Franz , Thomas Kistler, Slim binaries, Communications of the ACM, v.40 n.12, p.87-94, Dec. 1997 [doi>10.1145/265563.265576]
• 32: 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
• 33: Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.117-121, June 17-22, 1984, Montreal, Canada
• 34: Raymond J. Hookway , Mark A. Herdeg, DIGITAL FX!32: combining emulation and binary translation, Digital Technical Journal, v.9 n.1, p.3-12, 1997
• 35: 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
• 36: 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
• 37: 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
• 38: Kissell, K. D. 1997. Mips16: High-density mips for the embedded market. In Proceedings of Real Time Systems (RTS'97).
• 39: Raghavan Komondoor , Susan Horwitz, Using Slicing to Identify Duplication in Source Code, Proceedings of the 8th International Symposium on Static Analysis, p.40-56, July 16-18, 2001
• 40: Jens Krinke, Identifying Similar Code with Program Dependence Graphs, Proceedings of the Eighth Working Conference on Reverse Engineering (WCRE'01), p.301, October 02-05, 2001
• 41: Arvind Krishnaswamy , Rajiv Gupta, Profile guided selection of ARM and thumb instructions, 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
• 42: Arvind Krishnaswamy , Rajiv Gupta, Dynamic coalescing for 16-bit instructions, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.1, p.3-37, February 2005 [doi>10.1145/1053271.1053273]
• 43: Jeremy Lau , Stefan Schoenmackers , Timothy Sherwood , Brad Calder, Reducing code size with echo instructions, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951724]
• 44: 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]
• 45: Levine, J. 2000. Linkers & Loaders. Morgan Kaufmann, San Francisco, CA.
• 46: Madou, M., De Sutter, B., De Bus, B., Van Put, L., and De Bosschere, K. 2004. Link-time optimization of MIPS programs. In Proceedings of the 2004 International Conference on Embedded Systems and Applications (ESA'04). 70--75.
• 47: Robert Michael Muth , Saumya K. Debray, Alto: a platform for object code modification, 1999
• 48: 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]
• 49: Krishna V. Palem , Rodric M. Rabbah , Vincent J. Mooney, III , Pinar Korkmaz , Kiran Puttaswamy, Design space optimization of embedded memory systems via data remapping, 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
• 50: Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
• 51: Todd A. Proebsting, Optimizing an ANSI C interpreter with superoperators, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.322-332, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199526]
• 52: 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
• 53: Montserrat Ros , Peter Sutton, Compiler optimization and ordering effects on VLIW code compression, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951725]
• 54: Jonathan Rosenberg, Generating compact code for generic subprograms, 1983
• 55: B. Schwarz , S. Debray , G. Andrews, Disassembly of Executable Code Revisited, Proceedings of the Ninth Working Conference on Reverse Engineering (WCRE'02), p.45, October 29-November 01, 2002
• 56: Noah Snavely , Saumya Debray , Gregory Andrews, Unscheduling, Unpredication, Unspeculation: Reverse Engineering Itanium Executables, Proceedings of the 10th Working Conference on Reverse Engineering, p.4, November 13-17, 2003
• 57: Amitabh Srivastava, Unreachable procedures in object-oriented programming, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.355-364, Dec. 1992 [doi>10.1145/161494.161517]
• 58: 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
• 59: Peter F. Sweeney , Frank Tip, A study of dead data members in C++ applications, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.324-332, June 17-19, 1998, Montreal, Quebec, Canada
• 60: Thomas G. Szymanski, Assembling code for machines with span-dependent instructions, Communications of the ACM, v.21 n.4, p.300-308, April 1978 [doi>10.1145/359460.359474]
• 61: Frank Tip , Jens Palsberg, Scalable propagation-based call graph construction algorithms, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.281-293, October 2000, Minneapolis, Minnesota, United States
• 62: Frank Tip , Peter F. Sweeney , Chris Laffra , Aldo Eisma , David Streeter, Practical extraction techniques for Java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.6, p.625-666, November 2002 [doi>10.1145/586088.586090]
• 63: TriMedia Technologies Inc. 2000. TriMedia32 Architecture. TriMedia Technologies Inc, Sunnyvale, CA.
• 64: Turley, J. 1995. Thumb squeezes ARM code size. Microproc. Rep. 9, 4 (Mar.), 1--5.
• 65: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]

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

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Keywords:
Program representation, binary rewriting, code abstraction, compaction, interprocedural analysis, linker, whole-program optimization