Code Generation for a One-Register Machine

John Bruno, Ravi Sethi

Research output: Contribution to journalArticlepeer-review

55 Scopus citations


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 languageEnglish (US)
Pages (from-to)502-510
Number of pages9
JournalJournal of the ACM (JACM)
Issue number3
StatePublished - Jul 1 1976


  • 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


Dive into the research topics of 'Code Generation for a One-Register Machine'. Together they form a unique fingerprint.

Cite this