A new strategy for code generation: the general purpose optimizing compiler

ABSTRACT

This paper presents a systematic approach to the problem of generating good code with a compiler that is easy to construct. A compiler structure is proposed which relies on interprocedural data flow analysis, global optimization, and an intermediate language schema to simplify the task of writing the code generating portions of a compiler without sacrificing code quality. This structure is contrasted with a more conventional structure to explore the reasons why the new structure solves several problems inherent in the conventional structure. Further advantages which accrue from the new structure are also presented.

REFERENCES

• 1: Allen, F. E. Interprocedural data flow analysis. Proc. IFIP Congress 74, North Holland Publishing Co., Amsterdam, 1974, 398-402
• 2: Allen, F. E., and Cocke, J. A catalogue of optimizing transformations. Design and Optimization of Compilers, Rustin, R. (Ed.), Prentice-Hall, Englewood Cliffs, N.J., 1972, 1-30
• 3: Barth, Jeffrey M. Interprocedural data flow analysis based on transitive closure. Report UCB-CS-7644, University of California at Berkeley, September 13, 1976
• 4: J. Lawrence Carter, A case study of a new code generation technique for compilers, Communications of the ACM, v.20 n.12, p.914-920, Dec. 1977 [doi>10.1145/359897.359902]
• 5: Elson, M., and Rake, S. T. Code generation technique for large language compilers. IBM Systems Journal, Vol. 9 No. 3 (1970), 166-188
• 6: Harrison, William Compiler analysis of the value ranges of variables. IBM Research Report, RC5544, T.J. Watson Research Laboratory, Yorktown Heights, N.Y., July 1975
• 7: Harrison, William Formal semantics of a schematic intermediate language, IBM Research Report, RC6271, T.J. Watson Research Laboratory, Yorktown Heights, N.Y., November 1976
• 8: Herrick, Steven S., Donnely, David V. A survey of optimization techniques in compilers. National Technical Information Service, AD-A017-404, Rome Air Development Center, September 1975
• 9: Liskov, B. H., Zilles, S. N. Specification techniques for data abstractions. IEEE Transactions on Software Engineering, Vol. 1 No. 1, March 1975, 7-18
• 10: Lomet, David Predicting the effects of call point information on called procedure optimization. Internal Memorandum, October 1975
• 11: Lomet, D. B. Data flow analysis in the presence of procedure calls. IBM Research Report, RC5728, T.J. Watson Research Laboratory, Yorktown Heights, N.Y., November 1975
• 12: Jones, C. B. Formal definition in compiler development. Technical Report, TR25. 145, IBM Laboratory Vienna, February 1976
• 13: Rosen, Barry K. Data flow analysis for procedural languages. IBM Research Report, RC5948, T.J. Watson Research Laboratory, Yorktown Heights, N.Y., April 1976
• 14: Rosen, B. K. Data flow analysis for recursive PL/I programs. IBM Research Report, RC5211, T.J. Watson Research Laboratory, Yorktown Heights, N.Y., January 1975
• 15: Spillman, T. C. Exposing side effects in a PL/I optimizing compiler. Proc. IFIP Congress 71, North Holland Publishing Co., Amsterdam, 1971, 376-381
• 16: Ullman, J. D. Data Flow Analysis, Second USA-Japan Computer Conference, (1975)
• 17: Urschler, G. Complete redundant expression elimination in flow diagrams. IBM Research Report, RC4965, T.J. Watson Research Laboratory, Yorktown Heights, N.Y., August 1974