Paper Info
Title
Register allocation after classical SSA elimination is NP-Complete
Abstract
Chaitin proved that register allocation is equivalent to graph coloring and hence NP-complete. Recently, Bouchez, Brisk, and Hack have proved independently that the interference graph of a program in static single assignment (SSA) form is chordal and therefore colorable in linear time. Can we use the result of Bouchez et al. to do register allocation in polynomial time by first transforming the program to SSA form, then performing register allocation, and finally doing the classical SSA elimination that replaces φ-functions with copy instructions? In this paper we show that the answer is no, unless P = NP: register allocation after classical SSA elimination is NP-complete. Chaitin's proof technique does not work for programs after classical SSA elimination; instead we use a reduction from the graph coloring problem for circular arc graphs.
Year
DOI
Venue
2006
10.1007/11690634_6
FoSSaCS
Keywords
Field
DocType
register allocation,interference graph,proof technique,circular arc graph,copy instruction,classical ssa elimination,polynomial time,linear time,ssa form,graph coloring,graph coloring problem,static single assignment
Graph theory,Discrete mathematics,Combinatorics,Register allocation,Interval graph,Computer science,Chordal graph,Register file,Time complexity,Static single assignment form,Graph coloring
Conference
Volume
ISSN
ISBN
3921
0302-9743
3-540-33045-3
Citations 
PageRank 
References 
12
0.66
17
Authors
2
Name
Order
Citations
PageRank
Fernando Magno Quintão Pereira121620.03
Jens Palsberg22071227.45