register allocation via graph coloring

alexe@eecs.umich.edu writes
>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


You always have to be careful with the word "optimal." Technically
(the way papapers always use it), it does _not_ mean "none better",
which is too bad. I'm sure the paper will spell out the exact
conditions for optimality, but they aren't always what you might
expect.


I haven't read the paper (oops), but you mention one restriction,
namely "for a given schedule". This is the same sort of
simplification that Chaitin makes, I make, Chow&Hennessy make,
Callahan&Koblenz, make, etc. Interesting work that explores the
alternative (i.e., letting the schedule flex) includes


    author="Schlomit S. Pinter",
    title="Register Allocation with Instruction Scheduling: A New Approach",
    pages="248--257",
    journal=sigplan,
    year=1993,
    month=jun,
    volume=28,
    number=6,
    note=pldi93


and


A scheduler-sensitive global register allocator
Norris and Pollack
Supercomputing '93


Other possible simplifications include restricting the problem to a
single routine (most people do this, but there are exceptions), to a
single block, or even to a single expression. If you're looking at
more than a single expression (with no reuse, that is, a tree), the
problem of "optimal" allocation, for most definitions of optimal, is
at least NP complete (in the really general cases, it's just plain
undecidable).


About the NP-completeness thing, yet again. If somebody proves that
some particular formulation of a problem is NP complete, it means that
it's unlikely that an algorithm exists that can find an optimal
solution quickly. Note well the use of the special hedge words
"unlikely", "optimal", and "quickly".


So, for the paper referenced above, I expect they're solving some
limited problem well. However, the use of the word "optimal" suggests
that the problem they solve is so limited that their approach is
probably not that interesting (not meaning to be harsh or keep my head
too deeply in the sand, but there are a lot of NP-complete problems
for them to work around).


The moderator writes:


[And are they patented? -John]


Chaitin's work is patented by IBM. The work I published with Cooper,
Kennedy, and Torczon is patented by Rice (our PLDI '89 paper, or chapter 3
of my thesis). The rest of my stuff has not been patented. Callahan &
Koblenz is not patented. I don't know about other approaches.


Does a patent matter? Depends, doesn't it? In terms of research or home
projects, it doesn't matter at all. In terms of a product, it surely
matters, though it isn't necessarily prohibitive. You just have to pursue
liscensing issues (or, to keep the patent, the owners must actively pursue
users).


Marc-Michael Brandis wrote


      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)


Available via anonymous ftp from cs.rice.edu, in the directory public/preston


Cliff Click wrote


      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.


I have some problems with some of this. An optimal algorithm does not
_need_ to be exponential; however, everyone will be very interested in a
polynomial-time algorithm. Also, it's easy to write an optimal algorithm
for graph coloring that requires exponential time.


Otherwise, Cliff makes good points. For most interesting routines, a
k-coloring won't exist, so _something_ must be done, typically spilling,
splitting, or rescheduling. In terms of research, this is where all the
action is.


John D. Mitchell wrote


      >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).


Eh? The problem of coloring a given graph using a minimal number of
colors certainly has an optimal solution. And it's easy to write an
(expensive) algorithm for finding the optimal solution. It's also easy to
dream up faster, but non-optimal heuristics for coloring. Here's one:


give every node a different color


Not very minimal! How about this:


start with all nodes being uncolored


foreach node n, (in any order)
choose a color for n that differs from its neighbors


Better. And so forth.


But none of these have much to do with register allocation, wherein you've
got to find a k-coloring (not just a minimal coloring), or if you can't,
modify the code until you can, all in some reasonable amount of time.


Preston Briggs
--

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