The Design and Application of a Retargetable Peephole Optimizer

ABSTRACT

Peephole optimizers improve object code by replacing certain sequences of instructions with better sequences. This paper describes PO, a peephole optimizer that uses a symbolic machine description to simulate pairs of adjacent instructions, replacing them, where possible, with an equivalent single instruction. As a result of this organization, PO is machine independent and can be described formally and concisely: when PO is finished, no instruction, and no pair of adjacent instructions, can be replaced with a cheaper single instruction that has the same effect. This thoroughness allows PO to relieve code generators of much case analysis; for example, they might produce only load/add-register sequences and rely on PO to, where possible, discard them in favor or add-memory, add-immediate, or increment instructions. Experiments indicate that naive code generators can give good code if used with PO.

REFERENCES

• 1: ALLEN, F.E., AND COCKE, J. A catalogue of optimizing transformations. In Design and Optimization of Compilers, no. 1-30, R. Rustin (Ed)., Prentice-Hall, Englewood Cliffs, N.J., 1972.
• 2: John T. Bagwell, Jr., Local optimizations, ACM SIGPLAN Notices, v.5 n.7, p.52-66, July 1970
• 3: C. Gordon Bell , A. C. Newell, Computer structures: Readings and examples (McGraw-Hill computer science series), McGraw-Hill Pub. Co., 1971
• 4: FORTRAN-10 reference manual. Digital Equipment Corp., Maynard, Mass., 1974.
• 5: R. Steven Glanville , Susan L. Graham, A new method for compiler code generation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.231-254, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512785]
• 6: William Harrison, A new strategy for code generation: the general purpose optimizing compiler, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-37, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512954]
• 7: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 8: Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
• 9: W. M. McKeeman, Peephole optimization, Communications of the ACM, v.8 n.7, p.443-444, July 1965 [doi>10.1145/364995.365000]
• 10: PDP-11 processor handbook. Digital Equipment Corp., Maynard, Mass., 1975.
• 11: STANDISH, T.A., HARRIMAN, D.C., KIBLER, D.F., AND NEIGHBORS, J.M. The Irvine program transformation catalogue. Dep. Information and Computer Science, Univ. California, Irvine, 1976.
• 12: 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

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

General Terms:
Design, Languages, Performance, Theory