Register allocation in structured programs

Sampath Kannan, Todd Proebsting

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations


In this paper we look at the register allocation problem. In the literature this problem is frequently reduced to the general graph coloring problem and the solutions to the problem are obtained from graph coloring heuristics. Hence, no algorithm with a good performance guarantee is known. Here we show that when attention is restricted to structured programs which we define to be programs whose control-flow graphs are series-parallel, there is an efficient algorithm that produces a solution which is within a factor of 2 of the optimal solution. We note that even with the above restriction the resulting coloring problem is NP-complete. We also consider how to delete a minimum number of edges from arbitrary control-flow graphs to make them series-parallel and apply our algorithm. We show that this problem is Max SNP hard. However, we define the notion of an approximate articulation point and give efficient algorithms to find approximate articulation points. We present a heuristic for the edge deletion problem based on this notion which seems to work well when the given graph is close to series-parallel.

Original languageEnglish (US)
Title of host publicationProceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
PublisherAssociation for Computing Machinery
Number of pages9
ISBN (Electronic)0898713498
StatePublished - Jan 22 1995
Event6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 - San Francisco, United States
Duration: Jan 22 1995Jan 24 1995

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
Country/TerritoryUnited States
CitySan Francisco

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Register allocation in structured programs'. Together they form a unique fingerprint.

Cite this