Fri, 17 Feb 1995 16:01:11 GMT

Related articles |
---|

Register allocation with graph coloring alexe@eecs.umich.edu (Alexandre Eichenberger) (1995-02-01) |

Re: Register allocation using graph coloring alexe@eecs.umich.edu (Alexandre Eichenberger) (1995-02-17) |

register allocation via graph coloring preston@tera.com (1995-02-21) |

Re: register allocation via graph coloring billms@corp.mot.com (1995-02-27) |

Re: register allocation via graph coloring anton@mips.complang.tuwien.ac.at (1995-02-27) |

Newsgroups: | comp.compilers |

From: | Alexandre Eichenberger <alexe@eecs.umich.edu> |

Keywords: | optimize, summary, registers |

Organization: | Compilers Central |

References: | 95-02-032 |

Date: | Fri, 17 Feb 1995 16:01:11 GMT |

Here are the answers I got about register allocation using graph

coloring. Besides the articles mentioned in the following emails, I

found an article that presents an algorithm for register allocation

and spilling for a given schedule in an optimal fashion:

W. M. Meleis and E. S. Davidson, "Optimal Register Allocation for a

Multiple-Issue Machine, in the Proceedings of the 1994 International

Conference on Supercomputing (ICS), Manchester, UK, pp 107-116

Thanks,

Alexandre Eichenberger

============================================================================

>Which graph coloring algorithms for register allocation are considered

>"state-of-the-art" ? Are any of these algorithms available on the net?

>Also, is there an optimal graph coloring algorithm available on the net?

>

>Any pointers to articles and codes are appreciated.

>

>{And are they patented? -John]

============================================================================

From: Marc Brandis <brandis@inf.ethz.ch>

Date: Mon, 6 Feb 95 21:20:59 +0100

Newsgroups: comp.compilers

Organization: Dept. Informatik, Swiss Federal Institute of

Technology (ETH), Zurich, CH

[cut]

There have not really been too many improvements in graph-coloring register

allocation over the last couple of years. Here are some pointers:

P. Briggs. Register Allocation via Graph Coloring. Ph.D. thesis,

Rice University, Houston, Texas. Available as Technical Report Rice

COMP TR92-183. 1992. (also available through ftp, but I do not

have the address)

Excellent work in improving the original Yorktown allocator by Chaitin, and

a very good overview of the field. Includes a lot of hints on how to

actually implement such an allocator.

D. Callahan and B. Koblenz. Register Allocation via Hierarchical Graph

Coloring. In Proceedings of the ACM SIGPLAN '91 Conference on

Programming Language Design and Implementation. Toronto, Canada.

June 1991.

In my opinion, simply the best way to do register allocation known today. It

is very simple to make it work with all kinds of calling conventions or other

physical register requirements. Due to its hierarchical nature, the graphs

to color are rather small, which speeds up the process dramatically. Finally,

the method allows to place spill code intelligently. Highly recommended!

We use it in our optimizing Oberon compiler, and we are very happy with it.

L. Hendren, G. Gao, E. Altman, and C. Mukerji. A Register Allocation

Framework Based on Hierarchical Cyclic Interval Graphs. In Proceedings

of the 4th International Conference on Compiler Construction. Lecture

Notes in Computer Science 641, Springer. 1992.

L. Hendren, G. Gao, E. Altman, and C. Mukerji. Register Allocation

using Cyclic Interval Graphs: A New Approach to an Old Problem. ACAPS

Memo No. 33. Available from FTP_server ftp.cs.mcgill.ca. 1993.

Not exactly a graph coloring method, but a very interesting approach. Instead

of interference graphs, interval graphs are used. It allows to carefully select

values which should be located in the same register in order to maximize usage

of the register (which closely corresponds to minimizing the amount of spilling

required). This work is still under research, and I see a couple of problems

making it work for general flow graphs, but if you want to do research in the

field, this is at least very interesting reading.

Hope this helps.

Marc

Marc-Michael Brandis

Institute for Computer Systems

ETH-Zentrum (Swiss Federal Institute of Technology)

CH-8092 Zurich, Switzerland

email: brandis@inf.ethz.ch

============================================================================

Date: Fri, 3 Feb 1995 10:11:01 -0500

From: Cliff Click <cliffc@crocus.hpl.hp.com>

[cut]

You might try asking Preston Briggs for a copy of his work done at

Rice. He's now with Tera, preston@tera.com. Reading Preston's thesis

will probably get you real close to the state-of-the-art in graph

coloring allocators. Graph-coloring is NP-complete, so an optimal

algorithm will have to be exponential. Don't know if one exists, but

it's much less likely to be interesting than a better spill metric, or

live-range-splitting algorithm. In other words, most interference

graphs are NOT colorable, so a "perfect" coloring algorithm will fail

anyways. The more important issue is how you mangle the live-ranges

to get a colorable graph.

Cliff

============================================================================

Date: Thu, 2 Feb 1995 22:40:28 -0800

From: "John D. Mitchell" <johnm@CSUA.Berkeley.EDU>

Newsgroups: comp.compilers

Organization: Computer Science Undergraduate Association, UC Berkeley

[cut]

I don't know about availability of code but all of the major players have

published their work. Check the last few years of the proceedings of the

PLDI conference.

>Also, is there an optimal graph coloring algorithm available on the net?

There's no such thing as 'optimal' graph coloring. Coloring is one form of

heuristic to tractably deal with an untractable problem (in general).

Take care,

John

============================================================================

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.