Discovering machine-specific code improvements

ABSTRACT

I have designed and built a compiler construction tool that automates much of the case analysis necessary to exploit special purpose instructions on a target machine. Given a suitable description of the target machine, my analysis identifies instruction sequences that are equivalent to single instructions. During code generation, these equivalences can be used to avoid inefficient instruction sequences in favor of more efficient instructions.I present a working prototype of the instruction set analyzer needed in the framework outlined by [Giegerich 83]. In contrast to the work presented in [Davidson and Fraser 80, 84], I analyze machine descriptions during compiler construction, rather than analyzing instruction sequences that occur during code generation. [R Kessler 84] describes a system which analyzes machine descriptions during compiler construction, but which which is limited to discovering instructions that are equivalent to instruction sequences of length 2. The techniques presented here can identify instruction sequences of arbitrary length that are equivalent to single instructions.I have applied this analysis to the descriptions of two machines, and used the results to replace hand-written case analysis routines in an otherwise table-driven code generator [Henry 84].

REFERENCES

• Backus et al. 57: I.W. Backus, R, .I. Beeber, S. Best, R. Goldberg, L. M. ttaibt, H. L. Herrick, R. A. Nelson. D. Sayre, P. B. Sheridan, !-!. Stern. I. Ziiler, R, A. Hughes and R. Nutt, '"l'he FORTRAN Coding System", Proceedings of the Weslern Joinl Computer Conference, Los Angeles, CA, February 1957, 188-198.
• Cocke and Schwartz 70: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• Davidson and Fraser 80: 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]
• Davidson and Fraser 84: Jack W. Davidson , Christopher W. Fraser, Automatic generation of peephole optimizations, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.111-116, June 17-22, 1984, Montreal, Canada
• Ganapathi 80: Mahadevan Ganapathi, Retargetable code generation and optimization using attribute grammars, 1980
• Giegerich 83: Robert Giegerich, A Formal Framework for the Derivation of Machine-Specific Optimizers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.478-498, July 1983 [doi>10.1145/2166.357219]
• Henry 84: Robert Rettig Henry, Graham/glanville code generators (compiler, parser, programming language), 1984
• Johnson 78: S, C. Johnson, "'YACC: Yet Another Compiler-Compiler", Bell Laboratories Murray Hilt, N J, July 1978.
• RKessler 84: Robert R. Kessler, Peep: an architectural description driven peephole optimizer, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.106-110, June 17-22, 1984, Montreal, Canada
• Lesk and Schmidt 75: M. E. Lesk and E. Schmidt, "'EEX - A Lexical Analyzer Generator", Computer Science Technical Report TR-39, Bell Laboratories Murray mliil. N.I. October, 1975.
• Morgan and Rowe 82: Thomas M. Morgan , Lawrence A. Rowe, Analyzing exotic instructions for a retargetable code generator, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.197-204, June 23-25, 1982, Boston, Massachusetts, United States
• Wulf et al. 75: William Allan Wulf , Richard K. Johnsson , Charles B. Weinstock , Steven O. Hobbs , Charles M. Geschke, The Design of an Optimizing Compiler, Elsevier Science Inc., New York, NY, 1975

INDEX TERMS

Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Design, Theory