Sifting out the mud: low level C++ code reuse

ABSTRACT

More and more computers are being incorporated in devices where the available amount of memory is limited. This contrasts with the increasing need for additional functionality and the need for rapid application development. While object-oriented programming languages, providing mechanisms such as inheritance and templates, allow fast development of complex applications, they have a detrimental effect on program size. This paper introduces new techniques to reuse the code of whole procedures at the binary level and a supporting technique for data reuse. These techniques benefit specifically from program properties originating from the use of templates and inheritance. Together with our previous work on code abstraction at lower levels of granularity, they achieve additional code size reductions of up to 38% on already highly optimized and compacted binaries, without sacrificing execution speed. We have incorporated these techniques in Squeeze++, a prototype link-time binary rewriter for the Alpha architecture, and extensively evaluate them on a suite of 8 real-life C++ applications. The total code size reductions achieved post link-time (i.e. without requiring any change to the compiler) range from 27 to 70%, averaging at around 43%.

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: B. S. Baker and U. Manber. Deducing similarities in Java sources from bytecodes. In USENIX Annual Technical Conference, pages 179--190, June 1998.
• 3: 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
• 4: 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]
• 5: R. Cohn, D. Goodwin, P. Lowney, and N. Rubin. Spike: An optimizer for alpha/nt executables. In USENIX Windows NT Workshop, Aug. 1997.
• 6: 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
• 7: 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
• 8: Jeffrey Dean , Greg DeFouw , David Grove , Vassily Litvinov , Craig Chambers, Vortex: an optimizing compiler for object-oriented languages, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.83-100, October 06-10, 1996, San Jose, California, United States
• 9: 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
• 10: 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]
• 11: Embedded C++ Technical Committee. The Embedded C++ Specification, Oct. 1999.
• 12: 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
• 13: Maria Francesca Fernandez, A retargetable, optimizing linker, Princeton University, Princeton, NJ, 1996
• 14: 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
• 15: Michael Franz , Thomas Kistler, Slim binaries, Communications of the ACM, v.40 n.12, p.87-94, Dec. 1997 [doi>10.1145/265563.265576]
• 16: 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
• 17: 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
• 18: C. Fraser and T. Proebsting. Custom instruction sets for code compression. http://research.microsoft.com/ toddpro, 1995.
• 19: Jan Hoogerbrugge , Lex Augusteijn , Jeroen Trum , Rik Van De Wiel, A code compression system based on pipelined interpreters, Software—Practice & Experience, v.29 n.11, p.1005-2023, Sept. 1999 [doi>10.1002/(SICI)1097-024X(199909)29:11<1005::AID-SPE270>3.0.CO;2-F]
• 20: 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
• 21: 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
• 22: 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
• 23: K. D. Kissell. MIPS16: High-density MIPS for the embedded market. In Proc. of Real Time Systems '97 (RTS97), 1997.
• 24: Charles Robert Lefurgy , Trevor Mudge, Efficient execution of compressed programs, 2000
• 25: J. Levine. Linkers & Loaders. Morgan Kaufmann Publishers, 2000.
• 26: 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]
• 27: 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
• 28: Jonathan Rosenberg, Generating compact code for generic subprograms, 1983
• 29: B. Schwarz, G. Andrews, M. Legendre, and S. Debray. PLTO: A link-time optimizer for the intel ia-32 architecture. In Proc. Workshop on Binary Translation (WBT), Sept. 2001.
• 30: 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]
• 31: 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
• 32: 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
• 33: Frank Tip , Chris Laffra , Peter F. Sweeney , David Streeter, Practical experience with an application extractor for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.292-305, November 01-05, 1999, Denver, Colorado, United States
• 34: 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
• 35: TriMedia Technologies Inc. TriMedia32 Architecture, Oct. 2000.
• 36: J. Turley. Thumb squeezes ARM code size. Microprocessor Report, 9(4):1--5, Mar. 1995.
• 37: 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
• 38: http://www.absint.com/aipop/.
• 39: http://www.raisonance.com.
• 40: http://www.transitives.com.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

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

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

General Terms:
Experimentation, Performance

Keywords:
code compaction, code size reduction