Is register allocation really NP-Complete?

payne@zeus.unomaha.edu (Matt Payne)
26 Mar 91 16:00:23 CST

          From comp.compilers

Related articles
Is register allocation really NP-Complete? payne@zeus.unomaha.edu (1991-03-26)
Re: Is register allocation really NP-Complete? larus@cs.wisc.edu (1991-03-27)
Re: Is register allocation really NP-Complete? preston@ariel.rice.edu (1991-03-27)
Re: Is register allocation really NP-Complete? david@cs.washington.edu (1991-03-27)
Re: Is register allocation really NP-Complete? preston@ariel.rice.edu (1991-03-28)
Re: Is register allocation really NP-Complete? spencert@cs.rpi.edu (1991-03-31)
| List of all articles for this month |

Newsgroups: comp.compilers
From: payne@zeus.unomaha.edu (Matt Payne)
Keywords: optimization, theory, design
Organization: Compilers Central
Date: 26 Mar 91 16:00:23 CST

In the paper "The Priority-Based Coloring Approach to Register
Allocation" by F.C. Chow and J.L. Hennessy in ACM TOPLAS October 1990
[Chow 90]


States that "Earlier descriptions of the algorithm have not addressed some
other practical issues that arise. We see three key issues." "Third, the
running time of the algorithm must be reasonable. The determination of
whether a graph is r-colorable is NP-complete."


In general this is true, but [Chow 90] describes the interference (or
conflict) graph that is colored to allocate the registers. [Chow 90]'s
describtion of interference graphs sounds a lot like interval graphs as
described in _Algorithmic Graph Theory and Perfect Graphs_ by M.C.
Golumbic [Golumbic 80]. U.I. Gupta, D.T. Lee, and J.Y.T. Leung "Efficient
algorithms for interval graphs and circular-arc graphs" in Networks 12
(1982), pp.459-467 is supposed to contain a POLYNOMIAL algorithm for
finding the Chromatic Number of an interval graph.


So, I'm confused. [Chow 90] implies that this is a NP-complete problem,
but how can it be if [Chow 90]'s interference graphs are interval
graphs?


Please help! Thanks!! -- matt
payne@zeus.unomaha.edu
[Perhaps Chow's algorithm isn't optimal. There are often fast approximate
solutions to NP complete problems -John]
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.