Paper Info
Title
Aliased register allocation for straight-line programs is NP-complete
Abstract
Register allocation is NP-complete in general but can be solved in linear time for straight-line programs where each variable has at most one definition point if the bank of registers is homogeneous. In this paper we study registers which may alias: an aliased register can be used both independently or in combination with an adjacent register. Such registers are found in commonly-used architectures such as x86, the HP PA-RISC, the Sun SPARC processor, and MIPS floating point. In 2004, Smith, Ramsey, and Holloway presented the best algorithm for aliased register allocation so far; their algorithm is based on a heuristic for coloring of general graphs. Most architectures with register aliasing allow only aligned registers to be combined: for example, the low-address register must have an even number. Open until now has been the question of whether working with restricted classes of programs can improve the complexity of aliased register allocation with alignment restrictions. In this paper we show that aliased register allocation with alignment restrictions for straight-line programs is NP-complete. We also present a proof of a related result by Stockmeyer: the shipbuilding problem is NP-complete.
Year
DOI
Venue
2008
10.1016/j.tcs.2008.05.025
Theor. Comput. Sci.
Keywords
Field
DocType
linear time,register allocation
Alias,Status register,Register allocation,Computer science,Parallel computing,Control register,Stack register,Register renaming,Processor register,Time complexity
Journal
Volume
Issue
ISSN
407
1
Theoretical Computer Science
Citations 
PageRank 
References 
7
0.45
13
Authors
3
Name
Order
Citations
PageRank
Jonathan K. Lee1572.47
Jens Palsberg22071227.45
Fernando Magno Quintão Pereira321620.03