Tue, 21 Feb 1995 21:37:51 GMT

Related articles |
---|

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: | preston@tera.com (Preston Briggs) |

Keywords: | registers, optimize, bibliography |

Organization: | Compilers Central |

References: | 95-02-136 |

Date: | Tue, 21 Feb 1995 21:37:51 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.