25 Nov 2001 22:39:52 -0500

Related articles |
---|

old register allocators by coloring Sid-Ahmed-Ali.TOUATI@inria.fr (Sid Ahmed Ali TOUATI) (2001-11-25) |

Re: old register allocators by coloring thp@cs.ucr.edu (2001-12-15) |

From: | Sid Ahmed Ali TOUATI <Sid-Ahmed-Ali.TOUATI@inria.fr> |

Newsgroups: | comp.compilers |

Date: | 25 Nov 2001 22:39:52 -0500 |

Organization: | INRIA |

Keywords: | registers |

Posted-Date: | 25 Nov 2001 22:39:52 EST |

Dear all,

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 ?

Thank you

SAAT

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.