The design of a global optimizer

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The design of a global optimizer

Full text

Pdf (791 KB)

Source

Symposium on Compiler Construction archive
Proceedings of the 1979 SIGPLAN symposium on Compiler construction table of contents

Denver, Colorado, United States

Pages: 226 - 234

Year of Publication: 1979

ISBN:0-89791-002-8

Also published in ...

Authors

Ronald J. Mintz	Incoterm Corporation, Wellesley Hills, Massachusetts
Gerald A. Fisher, Jr.	Incoterm Corporation, Wellesley Hills, Massachusetts
Micha Sharir	Courant Institute of Mathematical Sciences, New York University, New York, N.Y.

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 15, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800229.806974 What is a DOI?

ABSTRACT

We are constructing a compiler for a high level systems and applications programming language. Because the compiler is required to generate efficient object code, a global optimization phase and register allocation phase are an integral part of the design. It was determined that the familiar optimizations of code motion, redundant expression elimination, and dead code removal would be sufficient. The optimizer design was to be based on the most recent applicable theoretical results, yet simple and straightforward to implement. Traditional approaches were considered inadequate because they assume a primitive intermediate code representation (quadruples), elaborate flow graph constructions, and numerous special cases. High level data flow analysis as proposed by Rosen [1,2] provided the framework we sought. Using his approach, the parse tree of the program, with its high level control structures intact, becomes a suitable intermediate representation. Complex statement structures are analyzed quickly in two tree traversals to determine the solutions to data flow problems.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Barry K. Rosen, High-level data flow analysis, Communications of the ACM, v.20 n.10, p.712-724, Oct. 1977 [doi>10.1145/359842.359849]
	2	Rosen, Barry K., "monoids for Rapid Data Flow Analysis," IBM Res. Rep. RC 7032, 3/78. IBM T. J. Watson Res. Cr., Yorktown Heights, New York.
	3	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
	4	E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
	5	Schwartz, J. T., "On Programming: an Interim Report on the SETL Project," Second Edition, Courant Institute of Mathematical Sciences, New York University, New York, New York, 1975.
	6	Schwartz, J. T., and Sharir, M., "Design of Optimizations of the Bit-Vectoring Class," Courant Institute of Mathematical Sciences, New York University, New York, New York, Technical Report to appear.

CITED BY 2

	Manfred Weber , Susan L. Bernstein, Global register allocation for non-equivalent register sets, ACM SIGPLAN Notices, v.15 n.2, p.74-81, February 1980
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, ACM SIGPLAN Notices, v.29 n.6, p.147-158, June 1994