Abstract
Echo Instructions have recently been introduced to allow embedded processors to provide runtime decompression of LZ77-compressed programs at a minimal hardware cost compared to other recent decompression schemes. As embedded architectures begin to adopt echo instructions, new compiler techniques will be required to perform the compression step. This paper describes a novel instruction selection algorithm that can be integrated into a retargetable compiler that targets such architectures. The algorithm uses pattern matching to identify repeated fragments of the compiler’s intermediate representation of a program. Identical program fragments are replaced with echo instructions, thereby compressing the program. The techniques presented here can easily be adapted to perform procedural abstraction, which replaces repeated program fragments with procedure calls rather than echo instructions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Fraser, C.W.: An Instruction for Direct Interpretation of LZ77-compressed Programs. In: Microsoft Technical Report TR-2002-90 (2002)
Lau, J., Schoemackers, S., Sherwood, T., Calder, B.: Reducing Code Size With Echo Instructions. In: CASES (2003)
Ziv, J., Lempel, A.: A Universal Algorithm for Sequential Data Compression. IEEE Trans. on Information Theory 23(3), 337–343 (1977)
Fraser, C.W., Myers, E.W., Wendt, A.: Analyzing and Compressing Assembly Code. In: ACM Symposium on Compiler Construction (1984)
Debray, S., Evans, W., Muth, R., De Sutter, B.: Compiler Techniques for Code Compaction. ACM Trans. Programming Languages and Systems 22(2), 378–415 (2000)
Cooper, K.D., McIntosh, N.: Enhanced Code Compression for Embedded RISC Processors. In: International Conference on Programming Language Design and Implementation (1999)
Runeson, J.: Code Compression Through Procedural Abstraction before Register Allocation. Masters Thesis, University of Uppsala (1992)
Lefurgy, C., Bird, P., Chen, I., Mudge, T.: Improving Code Density Using Compression Techniques. In: 30th International Symposium on Microarchitecture (1997)
Liao, S., Devadas, S., Keutzer, K.: A Text-compression-based Method for Code Size Minimization in Embedded Systems. ACM Trans. Design Automation of Embedded Systems 4(1), 12–38 (1999)
Wolfe, A., Chanin, A.: Executing Compressed Programs on an Embedded RISC Architecture. In: 25th International Symposium on Microarchitecture (1992)
Kozuch, M., Wolfe, A.: Compression of Embedded System Programs. In: IEEE Int. Conf. Computer Design (1994)
Kemp, T.M., Montoye, R.K., Harper, J.D., Palmer, J.D., Auerbach, D.J.: A Decompression Core for PowerPC. IBM Journal of Research and Development 42(6), 807–812 (1998)
Game, M., Booker, A.: CodePack: Code Compression for PowerPC Processors, Version 1.0. In: Technical Report, IBM Microelectronics Division
Lefurgy, C., Piccininni, E., Mudge, T.: Evaluation of a High Performance Data Compression Method. In: 32nd International Symposium on Microarchitecture (1999)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co, New York (1979)
Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: An Improved Algorithm for Matching Large Graphs. In: The 3rd IAPR-TC15 Workshop on Graph-based Representations (2001)
Kastner, R., Kaplan, A., Memik, S.O., Bozorgzadeh, E.: Instruction Generation for Hybrid Reconfigurable Systems. ACM Trans. Design Automation of Embedded Systems 7(4), 605–627 (2002)
Kirovski, D., Potkonjak, M.: Efficient Coloring of a Large Spectrum of Graphs. In: Design Automation Conference (1997)
Kunchithapadam, K., Larus, J.R.: Using Lightweight Procedures to Improve Instruc- tion Cache Performance. In: University of Wisconsin-Madison Technical Report CS-TR-99-1390 (1999)
Briggs, P., Cooper, K.D., Torczon, L.: Improvements to Graph Coloring Register Allocation. ACM Trans. Programming Languages and Systems 16(3), 428–455 (1994)
George, L., Appel, A.W.: Iterated Register Coalescing. ACM Trans. Programming Languages and Systems 18(3), 300–324 (1996)
Park, J., Moon, S.M.: Optimistic Register Coalescing. In: International Conference on Parallel Architectures and Compilation Techniques (1998)
Lee, C., Potkonjak, M., Mangione-Smith, W.: MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communications Applications. In: 30th International Sympo- sium on Microarchitecture (1997)
Guthaus, M.R., Ringenberg, J.S., Ernst, D., Austin, T.M., Mudge, T., Brown, R.B.: MiBench: A free, commercially representative embedded benchmark suite. In: IEEE 4th Annual Workshop on Workload Characterization (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brisk, P., Nahapetian, A., Sarrafzadeh, M. (2004). Instruction Selection for Compilers That Target Architectures with Echo Instructions. In: Schepers, H. (eds) Software and Compilers for Embedded Systems. SCOPES 2004. Lecture Notes in Computer Science, vol 3199. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30113-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-30113-4_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23035-9
Online ISBN: 978-3-540-30113-4
eBook Packages: Springer Book Archive