A formal approach to code optimization

Alfred V. Aho; Ravi Sethi; J. D. Ullman

doi:10.1145/800028.808486

A formal approach to code optimization

Alfred V. Aho, Ravi Sethi, J. D. Ullman

Computer Science

Research output: Contribution to conference › Paper › peer-review

1 Scopus citations

Abstract

We examine from a formal point of view some problems which arise in code optimization and present some of the results which can come from such an approach. Specifically, a set of transformations which characterize optimization algorithms for straight line code is presented. Then we present an algorithm which produces machine code for evaluating arithmetic expressions on machines with N > 1 general purpose registers. We can prove that this algorithm produces optimal code when the cost criterion is the length of machine code generated.

Original language	English (US)
Pages	86-100
Number of pages	15
DOIs	https://doi.org/10.1145/800028.808486
State	Published - Jul 27 1970
Event	1970 Symposium on Compiler Optimization - Urbana-Champaign, United States Duration: Jul 27 1970 → Jul 28 1970

Other

Other	1970 Symposium on Compiler Optimization
Country/Territory	United States
City	Urbana-Champaign
Period	7/27/70 → 7/28/70

ASJC Scopus subject areas

Hardware and Architecture

Access to Document

10.1145/800028.808486

Cite this

@conference{6d6aba0e1e73453cb52f1a1899a3fc80,

title = "A formal approach to code optimization",

abstract = "We examine from a formal point of view some problems which arise in code optimization and present some of the results which can come from such an approach. Specifically, a set of transformations which characterize optimization algorithms for straight line code is presented. Then we present an algorithm which produces machine code for evaluating arithmetic expressions on machines with N > 1 general purpose registers. We can prove that this algorithm produces optimal code when the cost criterion is the length of machine code generated.",

author = "Aho, {Alfred V.} and Ravi Sethi and Ullman, {J. D.}",

note = "Publisher Copyright: {\textcopyright} 1970 Proceedings of a Symposium on Compiler Optimization. All Rights Reserved.; 1970 Symposium on Compiler Optimization ; Conference date: 27-07-1970 Through 28-07-1970",

year = "1970",

month = jul,

day = "27",

doi = "10.1145/800028.808486",

language = "English (US)",

pages = "86--100",

}

TY - CONF

T1 - A formal approach to code optimization

AU - Aho, Alfred V.

AU - Sethi, Ravi

AU - Ullman, J. D.

PY - 1970/7/27

Y1 - 1970/7/27

N2 - We examine from a formal point of view some problems which arise in code optimization and present some of the results which can come from such an approach. Specifically, a set of transformations which characterize optimization algorithms for straight line code is presented. Then we present an algorithm which produces machine code for evaluating arithmetic expressions on machines with N > 1 general purpose registers. We can prove that this algorithm produces optimal code when the cost criterion is the length of machine code generated.

AB - We examine from a formal point of view some problems which arise in code optimization and present some of the results which can come from such an approach. Specifically, a set of transformations which characterize optimization algorithms for straight line code is presented. Then we present an algorithm which produces machine code for evaluating arithmetic expressions on machines with N > 1 general purpose registers. We can prove that this algorithm produces optimal code when the cost criterion is the length of machine code generated.

UR - http://www.scopus.com/inward/record.url?scp=85059739058&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059739058&partnerID=8YFLogxK

U2 - 10.1145/800028.808486

DO - 10.1145/800028.808486

M3 - Paper

AN - SCOPUS:85059739058

SP - 86

EP - 100

T2 - 1970 Symposium on Compiler Optimization

Y2 - 27 July 1970 through 28 July 1970

ER -

A formal approach to code optimization

Abstract

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this