|old register allocators by coloring Sid-Ahmed-Ali.TOUATI@inria.fr (Sid Ahmed Ali TOUATI) (2001-11-25)|
|Re: old register allocators by coloring firstname.lastname@example.org (2001-12-15)|
|From:||Sid Ahmed Ali TOUATI <Sid-Ahmed-Ali.TOUATI@inria.fr>|
|Date:||25 Nov 2001 22:39:52 -0500|
|Posted-Date:||25 Nov 2001 22:39:52 EST|
I have an understanding (possible naive) problem about old register
allocation process by graph coloring. I suppose straight-line code, no
parallelism between instructions.
First, we know that the problem of searching an execution order of a
basic block statements such that the interference graph is k-colorable
is NP-complete. Dually, fixing this order and minimizing the spill
code is also NP-complete.
My question is about the coloring methods (Chaitin, Chow, etc...) for
register allocation. They generally make at first a live range
analysis step to build an interference graph. After, they try to color
it with some heuristics. I don't understand why they use heuristics
here : if we assume some live range schemes, so we have live
intervals. We can buid an interval graph : looking for a maximal
clique is not NP-complete in such a graph (and hence the dual coloring
problem is also easy). Why do they use heuristics here ?
Return to the
Search the comp.compilers archives again.