Peephole optimization as a targeting and coupling tool

ABSTRACT

The term peephole optimization is used to mean the pattern matching and conditional replacement performed on small sections of the intermediate form. The circular dependence between the code generation phases implies that local optimals are rarely global optimals. There are several reactions: (1) accept the local optimal, (2) develop intermediate goals whose achievement suggest global optimality, (3) retain the choices so that the decisions can be made later, (4) optimize the object code by replacing awkward or overly constrained segments of code with improved ones. Optimizing the object code has several advantages. First, code generation is greatly simplified. The code generator is allowed to forgo case analysis and utilize only a subset of the machine's instructions and addressing modes [BD88,DF84a,DF84b,DF87]. Second, a phase ordering problem often encountered in optimizations is reduced.

REFERENCES

• All86: Vicki Hurst Allan, A critical analysis of the global optimization problem for horizontal microcode (phase-coupled, compaction, code motion, compilation), 1986
• AM87: Vicki H. Allan , Robert A. Mueller, Phase coupling for horizontal microcode generation, Proceedings of the 20th annual workshop on Microprogramming, p.115-125, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255328]
• AM88: V. H. Allen , R. A. Mueller, Compaction with General Synchronous Timing, IEEE Transactions on Software Engineering, v.14 n.5, p.595-599, May 1988 [doi>10.1109/32.6137 ]
• AN88: A. Aiken , A. Nicolau, Optimal loop parallelization, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.308-317, June 20-24, 1988, Atlanta, Georgia, United States
• BD88: M.E. Benitez and J.W. Davidson. A portable global optimizer and linker. SIG- PLAN '88 Conference on Programming Language Design and Implementation, 23(7):329-338, July,1988.
• Cat82: R.G.G. Cattell. Formalization and Automatic Derivation of Code Generators. UMI Research Press, Ann Arbor, Michigan, 1982.
• Das80: Subrata Dasgupta, Some Aspects of High-Level Microprogramming, ACM Computing Surveys (CSUR), v.12 n.3, p.295-323, Sept. 1980 [doi>10.1145/356819.356823]
• Dav86: Jack W. Davidson, A retargetable instruction reorganizer, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.234-241, June 25-27, 1986, Palo Alto, California, United States
• Dav88: S. Davidson. High-Level Microprogramming Languages. In S. Habib, editor, Microprogramming and Firmware Engineering Methods, Van Nostrand Reinhold, New York, NY, 1988.
• DB86: G Davies , S Bowsher, Algorithms for pattern matching, Software—Practice & Experience, v.16 n.6, p.575-601, June. 1986 [doi>10.1002/spe.4380160608]
• DeW76: David Johns Dewitt, A machine independent approach to the production of optimized horizontal microcode., 1976
• DF84a: Jack W. Davidson , Christopher W. Fraser, Automatic generation of peephole optimizations, ACM SIGPLAN Notices, v.19 n.6, p.111-116, June 1984
• DF84b: 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]
• DF87: Jack W. Davidson , Christopher W. Fraser, Automatic inference and fast interpretation of peephole optimization rules, Software—Practice & Experience, v.17 n.11, p.801-812, November 1, 1987 [doi>10.1002/spe.4380171104]
• GF85: Mahadevan Ganapathi , Charles N. Fischer, Affix grammar driven code generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.560-599, Oct. 1985 [doi>10.1145/4472.4486]
• GFH82: Mahadevan Ganapathi , Charles N. Fischer , John L. Hennessy, Retargetable Compiler Code Generation, ACM Computing Surveys (CSUR), v.14 n.4, p.573-592, Dec. 1982 [doi>10.1145/356893.356897]
• Gur89: P. Gurd, Bit slice software: user retargetable microcode tools, ACM SIGMICRO Newsletter, v.20 n.2, p.26-31, June 1989 [doi>10.1145/71539.71543]
• JRS89: JRS: integrated design automation system (IDAS), ACM SIGMICRO Newsletter, v.19-20 n.4-1, p.11-17, Mar. 1989 [doi>10.1145/378818.378833]
• KT79: J. Kim and C.J. Tan. Register Assignment Algorithms for Optimizing Microcode Compilers - Part I. Technical Report RC 7639, IBM, Computer Sciences Department, IBM T.J. Watson Research Center, Yorktown Heights, NY, May 1979.
• Lev81: Bruce Wallace Leverett, Register allocation in optimizing compilers, 1981
• SDWX87: Bogong Su , Shiyuan Ding , Jian Wang , Jinshi Xia, Microcode compaction with timing constraints, Proceedings of the 20th annual workshop on Microprogramming, p.59-68, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255314]
• Veg82: Steven Roger Vegdahl, Local code generation and compaction in optimizing microcode compilers, 1982
• Wil89: D. Wilburn, Step engineering: step development system, ACM SIGMICRO Newsletter, v.20 n.2, p.19-25, June 1989 [doi>10.1145/71539.71542]
• You88: J.L. Young. The Software Foundry: Almost too Good to Be True. Electronics, 47-48, January 21, 1988.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers
      B.1.5 Microcode Applications
          Subjects: Firmware support of operating systems/instruction sets**

General Terms:
Algorithms, Design, Languages