Post-compilation optimization for multiple gains with pattern matching

ABSTRACT

Many existing retargetable compilers for ASIPs and domain-specific processors generate low quality code since the compiler is not able to fully utilize the intricacies of ISA of these processors. Hence, there is a need to further optimize the code produced by these compilers. In this paper, we introduce a new post-compilation optimization technique which is based on finding repeating instruction patterns in generated code and replacing them with their optimized equivalents. The instruction patterns to be found are represented by finite state machines which allow encapsulation of multiple patterns in just one representation, and instructions in a pattern to be not necessarily lexically adjacent. We also present a conflict resolution algorithm to select an optimization whenever a set of instructions fall under two or more different patterns of which only one can be applied on the basis of code size, cycle count or switching activity improvement. We tested this technique on the compiled binaries of ARM and Intel processors for code size improvement. We discuss the possible applications of this strategy in design space exploration (DSE) of embedded processors.

REFERENCES

• 1: 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]
• 2: Bruno De Bus , Bjorn De Sutter , Ludo Van Put , Dominique Chanet , Koen De Bosschere, Link-time optimization of ARM binaries, ACM SIGPLAN Notices, v.39 n.7, July 2004
• 3: Jack W. Davidson , Christopher W. Fraser, Automatic generation of peephole optimizations, ACM SIGPLAN Notices, v.39 n.4, April 2004 [doi>10.1145/989393.989407]
• 4: Jack W. Davidson , Christopher W. Fraser, The Design and Application of a Retargetable Peephole Optimizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.191-202, April 1980 [doi>10.1145/357094.357098]
• 5: Jack W. Davidson , Christopher W. Fraser, Code selection through object code optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.505-526, Oct. 1984 [doi>10.1145/1780.1783]
• 6: Saumya Debray , William Evans, Profile-guided code compression, ACM SIGPLAN Notices, v.37 n.5, May 2002
• 7: 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]
• 8: 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
• 9: 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
• 10: Michael Franz , Thomas Kistler, Slim binaries, Communications of the ACM, v.40 n.12, p.87-94, Dec. 1997 [doi>10.1145/265563.265576]
• 11: 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
• 12: Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, ACM SIGPLAN Notices, v.19 n.6, p.117-121, June 1984
• 13: M. Ghosh. Compiler Backend Generation and a Post-Compilation Optimization Technique for Extensible Architecture. MS Thesis. Computer Sc. & Engineering Department, IIT Kharagpur, 2004.
• 14: 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
• 15: Peter B. Kessler, Discovering machine-specific code improvements, ACM SIGPLAN Notices, v.21 n.7, p.249-254, July 1986
• 16: Robert R. Kessler, Peep: an architectural description driven peephole optimizer, ACM SIGPLAN Notices, v.19 n.6, p.106-110, June 1984
• 17: K. D. Kissell. MIPS16: High-density MIPS for the embedded market. In Proc. Real Time Systems (RTS97), 1997.
• 18: D. A. Lamb. Construction of a peephole optimizer. Software - Practice and Experience, 11(6): 638--647, June 1981.
• 19: Sheayun Lee , Andreas Ermedahl , Sang Lyul Min, An Accurate Instruction-Level Energy Consumption Model for Embedded RISC Processors, ACM SIGPLAN Notices, v.36 n.8, p.1-10, Aug. 2001
• 20: Haris Lekatsas , Jorg Henkel , Venkata Jakkula , Srimat Chakradhar, A Unified Architecture for Adaptive Compression of Data and Code on Embedded Systems, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design (VLSID'05), p.117-123, January 03-07, 2005 [doi>10.1109/ICVD.2005.36]
• 21: Rainer Leupers, Compiler Design Issues for Embedded Processors, IEEE Design & Test, v.19 n.4, p.51-58, July 2002 [doi>10.1109/MDT.2002.1018133]
• 22: W. M. McKeeman, Peephole optimization, Communications of the ACM, v.8 n.7, p.443-444, July 1965 [doi>10.1145/364995.365000]
• 23: B. J. McKenzie, Fast peephole optimization techniques, Software—Practice & Experience, v.19 n.12, p.1151-1162, Dec. 1989
• 24: S. Nystrom, J. Runeson, and J. Sjodin. Code compression techniques for embedded systems, 2000.
• 25: B. S. Pankaj and A. Gupta. Porting NET and a Post Compilation Optimization Technique. B. Tech. Project Report. Computer Sc. & Engineering Dept., IIT Kharagpur, May 2004.
• 26: 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
• 27: Diomidis Spinellis, Declarative peephole optimization using string pattern matching, ACM SIGPLAN Notices, v.34 n.2, p.47-50, Feb. 1999 [doi>10.1145/307903.307921]
• 28: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere , Saumya Debray, Combining Global Code and Data Compaction, ACM SIGPLAN Notices, v.36 n.8, p.29-38, Aug. 2001
• 29: Andrew S. Tanenbaum , Hans van Staveren , Johan W. Stevenson, Using Peephole Optimization on Intermediate Code, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.21-36, Jan. 1982 [doi>10.1145/357153.357155]
• 30: M. Zastre. Compacting object code via parameterized procedural abstraction. Master's thesis, University Victoria, 1995.
• 31: Min Zhao , Bruce Childers , Mary Lou Soffa, Predicting the impact of optimizations for embedded systems, ACM SIGPLAN Notices, v.38 n.7, July 2003

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments; Compilers

General Terms:
Algorithms, Design

Keywords:
instruction set FSM, pattern matching, peephole optimization, post-compilation optimization