17 Feb 2006 00:09:10 -0500

Related articles |
---|

Graph coloring register allocation via iterative scan avayvod@gmail.com (2006-02-03) |

Re: Graph coloring register allocation via iterative scan robert.thorpe@antenova.com (Rob Thorpe) (2006-02-06) |

Re: Graph coloring register allocation via iterative scan vmakarov@redhat.com (Vladimir Makarov) (2006-02-07) |

Re: Graph coloring register allocation via iterative scan avayvod@gmail.com (Whywhat) (2006-02-11) |

Re: Graph coloring register allocation via iterative scan vmakarov@redhat.com (Vladimir Makarov) (2006-02-14) |

Re: Graph coloring register allocation via iterative scan sylerugby@yahoo.com (2006-02-17) |

Re: Graph coloring register allocation via iterative scan Sid.Touati@inria.fr (Sid Touati) (2006-02-20) |

Re: Graph coloring register allocation via iterative scan u.hobelmann@web.de (Ulrich Hobelmann) (2006-02-24) |

Re: Graph coloring register allocation via iterative scan koes@cmu.edu (dkoes) (2006-03-11) |

From: | sylerugby@yahoo.com |

Newsgroups: | comp.theory,comp.compilers,comp.programming |

Date: | 17 Feb 2006 00:09:10 -0500 |

Organization: | http://groups.google.com |

References: | 06-02-018 |

Keywords: | registers |

Posted-Date: | 17 Feb 2006 00:09:10 EST |

Hi,

I just want ot make a small comment on graphs and register allocation.

I read the paper on Linear Scan Register Allocation, and what

immediately astonished me ist that it is in fact a graph coloring

algorithm ! More precisely it is interval graph coloring. All what is

said about the algorithm and its complexity is well known in graph

theory since at least 1970 (the book of Claude Berge: Graphs and

Hypergraphs).

Of course the use of this algorithm in the context of global register

allocation is interesting, as interval graphs model only live ranges in

code without control structures like conditionals and loops (i.e basic

blocks). In fact when the results are good vs Chaitin-Briggs

algorithm, then I would bet that is because few conditionals are

present in the code. Chaitin-Briggs algorithm is a general graph

coloring algorithm. The heuristic in the paper with the SCCs is aimed

at that goal I think.

As a note, interference graphs built in the case of loops (single loop

without conditionals) are circular-arc graphs whose coloring is also

well known in the art (Tucker 1975 and1978 for the coloring, and the

paper on spill code mimisation in PLDI 89 by Bernstein et al. (Golumbic

is one of the authors)for mentioning this, and of course the paper of

Laurie Hendren at CC'92 for register allocation in loops.

I would also like to mention the PhD thesis of Angelika Zobel (1992),

which, if I remember well, tries to modify the code to make the

interference graphs similar to graphs whose coloring is easier and

well-known (like interval or circular-arc graphs). But it is a bit in

the fog of my memory.

For intersection graphs (interval graphs, circle graphs, circular-arc

graphs) it is common place to work on the interval families underlying

the graph structure and not on the graph structure itself. It is

easier.

It would be nice if compiler writers open other books than compiler

books sometimes, espacially when dealing with problems or solutions not

directlly in the field.

Sylvain Lelait

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.