A formal approach to code optimization

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

doi:10.1145/390013.808486

A formal approach to code optimization

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

Computer Science

Research output: Contribution to journal › Article › peer-review

10 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 (from-to)	86-100
Number of pages	15
Journal	SIGPLAN Notices (ACM Special Interest Group on Programming Languages)
Volume	5
Issue number	7
DOIs	https://doi.org/10.1145/390013.808486
State	Published - Jul 1 1970

ASJC Scopus subject areas

Software
Computer Graphics and Computer-Aided Design

Access to Document

10.1145/390013.808486

Cite this

@article{ae0071d7c33e41d1a5a5024631bbd746,

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.}",

year = "1970",

month = jul,

day = "1",

doi = "10.1145/390013.808486",

language = "English (US)",

volume = "5",

pages = "86--100",

journal = "SIGPLAN Notices (ACM Special Interest Group on Programming Languages)",

issn = "0362-1340",

publisher = "Association for Computing Machinery (ACM)",

number = "7",

}

TY - JOUR

T1 - A formal approach to code optimization

AU - Aho, Alfred V.

AU - Sethi, Ravi

AU - Ullman, J. D.

PY - 1970/7/1

Y1 - 1970/7/1

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=38049108008&partnerID=8YFLogxK

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

U2 - 10.1145/390013.808486

DO - 10.1145/390013.808486

M3 - Article

AN - SCOPUS:38049108008

SN - 0362-1340

VL - 5

SP - 86

EP - 100

JO - SIGPLAN Notices (ACM Special Interest Group on Programming Languages)

JF - SIGPLAN Notices (ACM Special Interest Group on Programming Languages)

IS - 7

ER -

A formal approach to code optimization

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this