Complete register allocation problems

Ravi Sethi

Research output: Contribution to journalConference articlepeer-review

3 Scopus citations


The search for efficient algorithms for register allocation dates back to the time of the first Fortran compiler for the IBM 704. Since then, many variants of the problem have been considered; depending on two factors: (1) the particular model for registers, and (2) the definition of the term "computation of a program" e.g. Whether values may be computed more than once. We will show that several variants of the register allocation problem for straight line programs are polynomial complete. In particular we consider, (1) the case when each value is computed exactly once, and (2) the case when values may be recomputed as necessary. The completeness of the third problem considered is surprising. A straight line program starts with a set of initial values, and computes intermediate and final values. Suppose, for each value, the register that value must be computed into is preassigned. Then, (3) the problem of determining if there is a computation of the straight line program, that computes values into the assigned registers, is polynomial complete.

Original languageEnglish (US)
Pages (from-to)182-195
Number of pages14
JournalProceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Apr 30 1973
Event5th Annual ACM Symposium on Theory of Computing, STOC 1973 - Austin, United States
Duration: Apr 30 1973May 2 1973


  • Dag
  • Polynomial complete
  • Program optimization
  • Register allocation
  • Straight line program

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Complete register allocation problems'. Together they form a unique fingerprint.

Cite this