A practical method for code generation based on exhaustive search

ABSTRACT

An original method for code generation has been developed in conjunction with the construction of a compiler for the C programming language on the DEC-10 computer. The method is comprehensive, determining evaluation order and doing register allocation and instruction selection simultaneously. It uses exhaustive search rather than heuristics, and is table-driven, with most machine-specific information isolated in the tables. Testing and evaluation have shown that the method is effective, that the search process is not too time consuming, and that the compiler is capable of producing code as good as that of other optimizing compilers.

REFERENCES

• 1: A. V. Aho , S. C. Johnson, Optimal Code Generation for Expression Trees, Journal of the ACM (JACM), v.23 n.3, p.488-501, July 1976 [doi>10.1145/321958.321970]
• 2: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 3: A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
• 4: A. V. Aho , S. C. Johnson , J. D. Ullman, Code-generation for machines with multiregister operations, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.21-28, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512953]
• 5: William A. Barrett , Rodney M. Bates , David A. Gustafson , John D. Couch, Compiler construction: theory and practice (2nd ed.), SRA School Group, 1986
• 6: H. J. Bloom and E. de Jong. "A critical comparison of several programming language implementations." Software Practice and Experience 10 (1980), 435-473.
• 7: John Bruno , Ravi Sethi, Code Generation for a One-Register Machine, Journal of the ACM (JACM), v.23 n.3, p.502-510, July 1976 [doi>10.1145/321958.321971]
• 8: 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]
• 9: Roderic G.G. Cattell , Joseph M. Newcomer , Bruce W. Leverett, Code generation in a machine-independent compiler, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.65-75, August 06-10, 1979, Denver, Colorado, United States
• 10: M. Ganapathi and Charles N. Fischer. "Bibliography on automated retargetable code generation." ACM SIGPLAN Notices 16, 10 (1981), 9-12.
• 11: 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]
• 12: Susan L. Graham. "Table-driven code generation." IEEE Computer 13 (1980), 25-34.
• 13: 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]
• 14: Richard Karl Johnsson, An approach to global register allocation., 1976
• 15: Nils J. Nilsson, Problem-Solving Methods in Artificial Intelligence, McGraw-Hill Pub. Co., 1971
• 16: Ravi Sethi , J. D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM (JACM), v.17 n.4, p.715-728, Oct. 1970 [doi>10.1145/321607.321620]
• 17: Thomas G. Szymanski, Assembling code for machines with span-dependent instructions, Communications of the ACM, v.21 n.4, p.300-308, April 1978 [doi>10.1145/359460.359474]
• 18: Aaron M Tenenbaum , Moshe J Augenstein, Data structures using Pascal, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 19: Stephen Gibbs Wasilew, A compiler writing system with optimization capabilities for complex object order structures, 1972
• 20: B. A. Wichmann. "Ackermann's function: a study in the efficiency of calling procedures." BIT 16 (1976), 103-110.
• 21: B. A. Wichmann. "How to call procedures, or second thoughts on Ackermann's function." Software Practice and Experience 7 (1977), 317-329.
• 22: 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
• 23: W. A. Wulf et al. "An Overview of the Production Quality Compiler-Compiler Project." IEEE Computer 13, 8 (1980), 38-49.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Languages