High-quality code generation via bottom-up tree pattern matching

ABSTRACT

High-quality local code generation is one of the most difficult tasks the compiler-writer faces. Even if register allocation decisions are postponed and common subexpressions are ignored, instruction selection on machines with complex addressing can be quite difficult. Efficient and general algorithms have been developed to do instruction selection, but these algorithms fail to always find optimal solutions. Instruction selection algorithms based on dynamic programming or complete enumeration always find optimal solutions, but seem to be too costly to be practical. This paper describes a new instruction selection algorithm, and its prototype implementation, based on bottom-up tree pattern-matching. This algorithm is both time and space efficient, and is capable of doing optimal instruction selection for the DEC VAX-11 with its rich set of addressing modes.

REFERENCES

• 1: Alfred V. Aho , Mahadevan Ganapathi, Efficient tree pattern matching (extended abstract): an aid to code generation, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.334-340, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318663]
• 2: Philippe Aigrain , Susan L. Graham , Robert R. Henry , Marshall Kirk McKusick , Eduardo Pelegri-Llopart, Experience with a Graham-Glanville style code generator, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.13-24, June 17-22, 1984, Montreal, Canada
• 3: Roderic Geoffrey Galton Cattell, Formalization and automatic derivation of code generators., 1978
• 4: R. G. Cattell, Automatic Derivation of Code Generators from Machine Descriptions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.173-190, April 1980 [doi>10.1145/357094.357097]
• 5: Thomas W. Christopher , Philip J. Hatcher , Ronald C. Kukuk, Using dynamic programming to generate optimized code in a Graham-Glanville style code generator, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.25-36, June 17-22, 1984, Montreal, Canada
• 6: Mahadevan Ganapathi, Retargetable code generation and optimization using attribute grammars, 1980
• 7: {GAN81} Ganapathi, M. and Fischer, C. A Review of Automatic Code Generation Techniques. Technical Report #407, University of Wisconsin - Madison, 1981.
• 8: 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]
• 9: Robert Steven Glanville, A machine independent algorithm for code generation and its use in retargetable compilers., 1977
• 10: Susan L. Graham , Robert R. Henry , Robert A. Schulman, An experiment in table driven code generation, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.32-43, June 23-25, 1982, Boston, Massachusetts, United States
• 11: Ralph E. Griswold , Madge T. Griswold, ICON Programmng Language, Prentice Hall Professional Technical Reference, 1983
• 12: {HAT83} Hatcher, P. and Christopher, T. Using Aho and Johnson's Linear Dynamic Programming Code Generation Algorithm in a Table-Driven Code Generator. Technical Report #49--83, Department of Computer Science, Illinois Institute of Technology, 1983.
• 13: {HAT85a} Hatcher, P. CGG User's Guide (Versions 1.1 & 2.0). Technical Report #49-85, Department of Computer Science, Illinois Institute of Technology, 1985.
• 14: Philip John Hatcher, A tool for high-quality code generation (compiling), 1985
• 15: Robert Rettig Henry, Graham/glanville code generators (compiler, parser, programming language), 1984
• 16: Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982 [doi>10.1145/322290.322295]
• 17: {HOR85} Horspool, R. and Scheunemann, A. Automating the Selection of Code Templates. <i>Software-Practice And Experience</i> 15, May 1985, pp. 503--514.
• 18: S. C. Johnson, A portable compiler: theory and practice, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-104, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512771]
• 19: David W. Krumme , David H. Ackley, A practical method for code generation based on exhaustive search, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.185-196, June 23-25, 1982, Boston, Massachusetts, United States
• 20: {LEV80} Leverett, B., Cattell, R., Hobbs, S., Newcomer, J., Reiner, A., Schatz, B. and Wulf, W. An Overview of the Production-Quality Compiler-Compiler Project. <i>Computer</i> <b>13,</b> August 1980, pp. 38--49.
• 21: Uwe Schmidt , Reinhard Völler, A multi-language compiler system with automatically generated codegenerators, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.202-212, June 17-22, 1984, Montreal, Canada
• 22: Andrew S. Tanenbaum , Hans van Staveren , E. G. Keizer , Johan W. Stevenson, A practical tool kit for making portable compilers, Communications of the ACM, v.26 n.9, p.654-660, Sept. 1983 [doi>10.1145/358172.358182]