Affix grammar driven code generation

ABSTRACT

Affix grammars are used to describe the instruction set of a target architecture for purposes of compiler code generation. A code generator is obtained automatically for a compiler using attributed parsing techniques. A compiler built on this model can automatically perform most popular machine-dependent optimizations, including peephole optimizations. Code generators based on this model demonstrate retargetability for the VAX1-11, iAPX2-86, Z-80003, PDP4-11, MC-68000, NS32032, FOM, and IBM-370 architectures.

REFERENCES

• 1: AHO, A.V. Translator writing systems: Where do they now stand? IEEE Comput. 13, 8 (1980), 9-14.
• 2: 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]
• 3: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 4: 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
• 5: A. V. Aho , S. C. Johnson , J. D. Ullman, Deterministic parsing of ambiguous grammars, Communications of the ACM, v.18 n.8, p.441-452, Aug. 1975 [doi>10.1145/360933.360969]
• 6: ANDERSON, T., EVE, J., AND HORNING, J.J. Efficient LR(1) parsers. Acta Inf. 2, 1 (1973), 12-39.
• 7: BRANTLEY, W. C., AND WEISS, J. FOM: A Fortran optimized machine--A high performance, high-level language machine. IBM Res. Rep. RC 9640 (no. 40815), 1982. Also in Proceedings of the International Workshop on High-Level Language Computer Architecture (Fort Lauderdale, Fla., Nov. 30-Dec. 3, 1982).
• 8: BRANTLE~, W. C., AND WEISS, J. Organization and architecture trade-offs in FOM. IBM Res. Rep. RC9700 (no. 42748), 1982. Also in Proceedings of the International Workshop on Computer Systems Organization (New Orleans, La., Mar. 29-31, 1983).
• 9: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 10: 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]
• 11: Frederick Chi-Tak Chow, A portable machine-independent global optimizer--design and measurements, 1984
• 12: CHOW, F. C., AND GANAPATHI, M. Intermediate languages in compiler construction--a bibliography. ACM SIGPLAN Not. 18, 11 (Nov. 1983).
• 13: CROWLE~, T.R. Combining table-driven effect selection and description-driven peephole optimization for automatic code generation. M.S. thesis, MIT. Also Tech. Rep., Bell Laboratories, Dept. 45412, Sept. 1982.
• 14: 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]
• 15: FISCHER, C. $., GANAPATHI, M., AND LEBLANC, R.J. A simple and practical implementation of predicates in context-free parsers. Computer Sciences Tech. Rep. 493, Univ. of Wisconsin- Madison, Apr. 1983.
• 16: Christopher Warwick Fraser, Automatic generation of code generators., 1977
• 17: Mahadevan Ganapathi, Retargetable code generation and optimization using attribute grammars, 1980
• 18: Mahadevan Ganapathi , Charles N. Fischer, Description-driven code generation using attribute grammars, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.108-119, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582165]
• 19: 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]
• 20: M. Ganapathi , J. L. Hennessy , C. N. Fischer, Surveyor's Forum: Retargetable Code Generators, ACM Computing Surveys (CSUR), v.15 n.3, p.280-281, Sept. 1983 [doi>10.1145/356914.356921]
• 21: GANAPATHI, M., AND FISCHER, C. $. Automatic compiler code generation and reusable machine-dependent optimization--a revised bibliography. ACM SIGPLAN Not. 18, 4 (Apr. 1983), 27-34.
• 22: Mahadevan Ganapathi , Charles N. Fischer, Attributed linear intermediate representations for retargetable code generators, Software—Practice & Experience, v.14 n.4, p.347-364, April 1984 [doi>10.1002/spe.4380140406]
• 23: Mahadevan Ganapathi , Charles N. Fischer, Instruction selection by attributed parsing, Stanford University, Stanford, CA, 1984
• 24: Mahadevan Ganapathi , John Hennessy , Vivek Sarkar, Reverse synthesis compilation for architectural research, Stanford University, Stanford, CA, 1984
• 25: GIEGERICH, R. Automatic generation of machine-specific code optimizers. ACM Trans. Program. Lang. Syst. (July 1983).
• 26: Robert Steven Glanville, A machine independent algorithm for code generation and its use in retargetable compilers., 1977
• 27: 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]
• 28: 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
• 29: 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
• 30: John L. Hennessy , Thomas Gross, Postpass Code Optimization of Pipeline Constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.422-448, July 1983 [doi>10.1145/2166.357217]
• 31: Robert Rettig Henry, Graham/glanville code generators (compiler, parser, programming language), 1984
• 32: JOHNSON, S.C. YACC--y~t another compiler compiler. Computer Sciences Tech. Rep. 32, Bell Telephone Laboratories, Murray Hill, N. J., 1975.
• 33: 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]
• 34: KOSTER, C. H.A. Affix grammars. In ALGOL 68 Implementation, J. E. L. Peck, Ed., North- Holland, Amsterdam, 1971.
• 35: Rudolf Landwehr , Hans-Stephan Jansohn , Gerhard Goos, Experience with an automatic code generator generator, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.56-66, June 23-25, 1982, Boston, Massachusetts, United States
• 36: Bruce Wallace Leverett, Register allocation in optimizing compilers, 1981
• 37: LEVERETT, B.W. Topics in code generation and register allocation. Tech. Rep. CMU CS-82- 130, July 1982.
• 38: LUNELL, $. Code generator writing systems. Software Systems Research Center, S-58183, Linkoping, Sweden, 1983.
• 39: MAUNEY, J., AND FISCHER, C.N. ECP--an error correcting parser generator: User guide. Tech. Rep. 450, Computer Sciences Dept., Univ. of Wisconsin-Madison, Oct. 1981.
• 40: W. M. McKeeman, Peephole optimization, Communications of the ACM, v.8 n.7, p.443-444, July 1965 [doi>10.1145/364995.365000]
• 41: D. R. Milton , L. W. Kirchhoff , B. R. Rowland, An all(1) compiler generator, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.152-157, August 06-10, 1979, Denver, Colorado, United States
• 42: PURDOM, P. AND BROWN, C.A. Semantic routines and LR(k) parsers. Acta Inf. 14, 4 (1980), 299-316.
• 43: A. Rudmik , E. S. Lee, Compiler design for efficient code generation and program optimization, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.127-138, August 06-10, 1979, Denver, Colorado, United States
• 44: Andrew S. Tanenbaum , Hans van Staveren , Johan W. Stevenson, Using Peephole Optimization on Intermediate Code, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.21-36, Jan. 1982 [doi>10.1145/357153.357155]
• 45: WAll', D.A. The parsing problem for affix grammars. Acta In{. 8 (1977).
• 46: 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
• 47: WULF, W., LEVERETT, B. W., CATTELL, R. G. G., HOBES, S. O., NEWCOMER, J. M., REINER, A. H., AND SCHATZ, B. R. An overview of the production-quality compiler-compiler project. IEEE Comput. 13, 8 (Aug. 1980), 38-49.
• 48: WULg, W., ANO GOOS, G. EDS. DIANA Re{erence Manual. Tech. Rep. CMU-CS-81-101, Computer Sciences Dept., Carnegie Mellon Univ., Mar. 1981.

INDEX TERMS

Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Translator writing systems and compiler generators; Optimization; Compilers

General Terms:
Algorithms, Design, Languages