payne@zeus.unomaha.edu (Matt Payne) (03/27/91)
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]
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.larus@cs.wisc.edu (03/27/91)
Graph coloring for general graphs is NP-complete. There may be special
cases (such as interval graphs and circular-arc graphs) for which
efficient algorithms exists, but no one has shown their relevance for
register allocation (hint, hint). NB, a register allocator has an
additional constraint beyond a graph colorer. The allocator cannot throw
up its hands and quit when a graph is not 16 or 32 colorable.
And, yes both Chaitin's and Chow's algorithms are heuristics. There is no
guarantee that they achieve optimal colorings. The only promise is that
they can color all graphs (which they may modify in the process by
introducing spill code).
/Jim
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.preston@ariel.rice.edu (Preston Briggs) (03/27/91)
The interference graph for straight-line code (no branches or loops) will
be an interval graph; otherwise, it's more complex. Chow is interested in
global allocation (over an entire procedure), and must therefore worry
about such things.
Further, he must worry about spill code. Even if he has lots of registers
and achieves a minimal coloring, some programs will still require spill
code.
Preston Briggs
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.david@cs.washington.edu (David Callahan) (03/28/91)
In article <11422.27ef7017@zeus.unomaha.edu> payne@zeus.unomaha.edu (Matt Payne) writes: > >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? Conflict graphs, even coarse ones such as Chow constructs, are not interval graphs. Consider the fragment: A = B = l: ... = B ... = A C = ... ... = C B = goto l; ... A Note that the live range of B is discontiguous due to the control flow. These live ranges might be viewed as: BB CCC B AAAAAAAAAAA and so we see the conflict graph is not an interval graph. However, I don't know of a method that shows how to construct a program whose conflict graph corresponds to some arbitrary graph and so it is still possible that the restricted coloring problem associated with conflict graphs is not NP-hard. -- David Callahan (david@tera.com, david@june.cs.washington.edu,david@rice.edu) Tera Computer Co. 400 North 34th Street Seattle WA, 98103 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
preston@ariel.rice.edu (Preston Briggs) (03/29/91)
david@cs.washington.edu (David Callahan) writes: >However, I don't know of a method that shows how to construct a program >whose conflict graph corresponds to some arbitrary graph and so it is >still possible that the restricted coloring problem associated with >conflict graphs is not NP-hard. In Appendix 2 of Register Allocation via Graph Coloring Chaitin, Auslander, Chandra, Cocke, Hopkins, Markstein Computer Languages 6 (1981) they give a proof that all graphs can arise in register allocation. I won't repeat the proof, but in essence they show a systematic way to construct a program with any desired interference graph. Preston Briggs -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
spencert@cs.rpi.edu (Thomas Spencer) (03/31/91)
Organization: Rensselaer Polytechnic Institute, Troy NY References: <11422.27ef7017@zeus.unomaha.edu> <15573@june.cs.washington.edu> Date: 29 Mar 91 02:36:53 GMT In article <11422.27ef7017@zeus.unomaha.edu> payne@zeus.unomaha.edu (Matt Payne) writes: >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? Many register allocation problems have been proven to be NP-complete without reference to vertex coloring. See: Sethi, "Complete register allocation problems" SIAM J. of Computing, 1975, pp. 226-248. and Garey and Johnson "Computers and Intractibility ..." -- -Tom Spencer spencert@turing.cs.rpi.edu uunet!steinmetz!itsgw!spencert -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.