Re: Register allocation using graph coloring

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


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


--

Return to the comp.compilers page.
Search the comp.compilers archives again.