Code Generation for a One-Register Machine

John Bruno; Ravi Sethi

doi:10.1145/321958.321971

Code Generation for a One-Register Machine

John Bruno, Ravi Sethi

Computer Science

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

55 Scopus citations

Abstract

The majority of computers that have been built have performed all computations in devices called accumulators, or registers. In this paper, it is shown that the problem of generating minimal-length code for such machines is hard in a precise sense; specifically it is shown that the problem is NP-complete. The result is true even when the programs being translated are arithmetic expressions. Admittedly, the expressions in question can become complicated.

Original language	English (US)
Pages (from-to)	502-510
Number of pages	9
Journal	Journal of the ACM (JACM)
Volume	23
Issue number	3
DOIs	https://doi.org/10.1145/321958.321971
State	Published - Jul 1 1976

Keywords

NP-complete
arithmetic expressions
basic blocks
code optimization
register allocation
straight line programs

ASJC Scopus subject areas

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Access to Document

10.1145/321958.321971

Cite this

@article{8356504c4ec246408511f82ce3209a20,

title = "Code Generation for a One-Register Machine",

abstract = "The majority of computers that have been built have performed all computations in devices called accumulators, or registers. In this paper, it is shown that the problem of generating minimal-length code for such machines is hard in a precise sense; specifically it is shown that the problem is NP-complete. The result is true even when the programs being translated are arithmetic expressions. Admittedly, the expressions in question can become complicated.",

keywords = "NP-complete, arithmetic expressions, basic blocks, code optimization, register allocation, straight line programs",

author = "John Bruno and Ravi Sethi",

year = "1976",

month = jul,

day = "1",

doi = "10.1145/321958.321971",

language = "English (US)",

volume = "23",

pages = "502--510",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

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

number = "3",

}

TY - JOUR

T1 - Code Generation for a One-Register Machine

AU - Bruno, John

AU - Sethi, Ravi

PY - 1976/7/1

Y1 - 1976/7/1

N2 - The majority of computers that have been built have performed all computations in devices called accumulators, or registers. In this paper, it is shown that the problem of generating minimal-length code for such machines is hard in a precise sense; specifically it is shown that the problem is NP-complete. The result is true even when the programs being translated are arithmetic expressions. Admittedly, the expressions in question can become complicated.

AB - The majority of computers that have been built have performed all computations in devices called accumulators, or registers. In this paper, it is shown that the problem of generating minimal-length code for such machines is hard in a precise sense; specifically it is shown that the problem is NP-complete. The result is true even when the programs being translated are arithmetic expressions. Admittedly, the expressions in question can become complicated.

KW - NP-complete

KW - arithmetic expressions

KW - basic blocks

KW - code optimization

KW - register allocation

KW - straight line programs

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

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

U2 - 10.1145/321958.321971

DO - 10.1145/321958.321971

M3 - Article

AN - SCOPUS:0016972104

SN - 0004-5411

VL - 23

SP - 502

EP - 510

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 3

ER -

Code Generation for a One-Register Machine

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this