[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article

Combining Global Code and Data Compaction

Published: 01 August 2001 Publication History

Abstract

Computers are increasingly being incorporated in devices with a limited amount of available memory. As a result research is increasingly focusing on the automated reduction of program size. Existing literature focuses on either data or code compaction or on highly language dependent techniques. This paper shows how combined code and data compaction can be achieved using a link-time code compaction system that reasons about the use of both code and data addresses. The analyses proposed rely only on fundamental properties of linked code and are therefore generally applicable. The combined code and data compaction is implemented in SQUEEZE, a link-time program compaction system, and evaluated on SPEC2000, MediaBench and C++ programs, resulting in total binary program size reductions of 23.6%-46.6%. This compaction involves no speed trade-off, as the compacted programs are on average about 8% faster.

References

[1]
O. Agesen and D. Ungar. Sifting out the gold: Delivering compact applications from an exploratory object-oriented environment. In Proc. OOPSLA, pages 355-370, Oct. 1994.
[2]
A. Aho, R. Sethi, and J. Ullman. Compilers, Principles, Techniques and Tools. Addison-Wesley, 1986.
[3]
B. S. Baker and U. Manber. Deducing similarities in Java sources from bytecodes. In Proc. USENIX Annual Technical Conference, pages 179-190, Berkeley, CA, June 1998. Usenix.
[4]
L. Clausen, U. Schultz, C. Consel, and G. Muller. Java bytecode compression for low-end embedded systems. ACM TOPLAS, 22(3):471-489, May 2000.
[5]
C. Click and K. Cooper. Combining analyses, combining optimizations. ACM TOPLAS, 17(2):181-196, March 1995.
[6]
K. Cooper and N. McIntosh. Enhanced code compression for embedded RISC processors. In Proc. PLDI, pages 139-149, May 1999.
[7]
B. De Sutter, B. De Bus, S. Debray, and K. De Bosschere. Combining global code and data compaction. Technical Report PARIS 01-02, Ghent University, 2001.
[8]
S. Debray, W.Evans, R. Muth, and B. De Sutter. Compiler techniques for code compaction. ACM TOPLAS, 22(2):378-415, March 2000.
[9]
S. Debray, R. Muth, and M. Weippert. Alias analysis of executable code. In Proc. 1998 ACM Symposium on Principles of Programming Languages (POPL-98), pages 12-24, January 1998.
[10]
J. Ernst, W. Evans, C. Fraser, S. Lucco, and T. Proebsting. Code compression. In Proc. PLDI, pages 358-365, June 1997.
[11]
M. Franz. Adaptive compression of syntax trees and iterative dynamic code optimization: Two basic technologies for mobile-object systems. In J. Vitek and C. Tschudin, editors, Mobile Object Systems: Towards the Programmable Internet, number 1222 in LNCS, pages 263-276. Springer, Feb. 1997.
[12]
M. Franz and T. Kistler. Slim binaries. Commun. ACM, 40(12):87-94, Dec. 1997.
[13]
C. Fraser. Automatic inference of models for statistical code compression. In Proc. PLDI, pages 242-246, May 1999.
[14]
C. Fraser, E. Myers, and A. Wendt. Analyzing and compressing assembly code. In Proc. ACM SIGPLAN Symposium on Compiler Construction, volume 19, pages 117-121, June 1984.
[15]
N. Jones, C. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall International, 1993.
[16]
T. M. Kemp, R. M. Montoye, J. D. Harper, J. D. Palmer, and D. J. Auerbach. A decompression core for PowerPC. IBM J. Research and Development, 42(6), November 1998.
[17]
K. D. Kissell. MIPS16: High-density MIPS for the embedded market. In Proc. Real Time Systems '97 (RTS97), 1997.
[18]
R. Muth, S. Debray, S.Watterson, and K. De Bosschere. alto : A link-time optimizer for the Compaq Alpha. Software Practice andExperience, 31(1):67-101, January 2001.
[19]
W. Pugh. Compressing Java class files. In Proc. PLDI, pages 247-258, May 1999.
[20]
A. Srivastava. Unreachable procedures in object-oriented programming. ACM Letters on Programming Languages and Systems, 1(4):355-364, December 1992.
[21]
A. Srivastava and W. Wall. Link-time optimization of address calculation on a 64-bit architecture. In Proc. PLDI, pages 49-60, June 1994.
[22]
P. Sweeney. and F. Tip. A study of dead data members in C++ applications. In Proc. PLDI, pages 324-323, June 1998.
[23]
F. Tip, C. Laffra, and P. Sweeney. Practical experience with an application extractor for Java. In Proc. OOPSLA, pages 292-305, Nov. 1999.
[24]
M. Wegman and F. Zadeck. Constant propagation with conditional branches. ACM TOPLAS, 13(2):181-210, April 1991.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices
ACM SIGPLAN Notices  Volume 36, Issue 8
Aug. 2001
245 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/384196
Issue’s Table of Contents
  • cover image ACM Conferences
    OM '01: Proceedings of the 2001 ACM SIGPLAN workshop on Optimization of middleware and distributed systems
    August 2001
    250 pages
    ISBN:1581134266
    DOI:10.1145/384198
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2001
Published in SIGPLAN Volume 36, Issue 8

Check for updates

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2005)Post-compilation optimization for multiple gains with pattern matchingACM SIGPLAN Notices10.1145/1117303.111730640:12(14-23)Online publication date: 1-Dec-2005
  • (2021)CinnamonProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370313(103-114)Online publication date: 27-Feb-2021
  • (2014)Exploiting function similarity for code size reductionACM SIGPLAN Notices10.1145/2666357.259781149:5(85-94)Online publication date: 12-Jun-2014
  • (2014)Exploiting function similarity for code size reductionProceedings of the 2014 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems10.1145/2597809.2597811(85-94)Online publication date: 12-Jun-2014
  • (2008)Documenting and automating collateral evolutions in linux device driversACM SIGOPS Operating Systems Review10.1145/1357010.135261842:4(247-260)Online publication date: 1-Apr-2008
  • (2008)ParallaxACM SIGOPS Operating Systems Review10.1145/1357010.135259842:4(41-54)Online publication date: 1-Apr-2008
  • (2008)Efficient guaranteed disk request scheduling with fahrradACM SIGOPS Operating Systems Review10.1145/1357010.135259542:4(13-25)Online publication date: 1-Apr-2008
  • (2007)Robust implicit EDFACM Transactions on Embedded Computing Systems10.1145/1274858.12748666:4(28-es)Online publication date: 1-Sep-2007
  • (2007)Automated reduction of the memory footprint of the Linux kernelACM Transactions on Embedded Computing Systems10.1145/1274858.12748616:4(23-es)Online publication date: 1-Sep-2007
  • (2006)A computing perspective on the Bologna processACM SIGCSE Bulletin10.1145/1189136.118918138:4(115-131)Online publication date: 26-Jun-2006
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media