|Re: Register allocation using graph coloring email@example.com (Alexandre Eichenberger) (1995-02-17)|
|register allocation via graph coloring firstname.lastname@example.org (1995-02-21)|
|Re: register allocation via graph coloring email@example.com (1995-02-27)|
|Re: register allocation via graph coloring firstname.lastname@example.org (1995-02-27)|
|From:||email@example.com (Bill Mangione-Smith)|
|Date:||Mon, 27 Feb 1995 13:58:32 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
You always have to be careful with the word "optimal."
Its good to see somebody else who fights the good fight. It appears to be
a losing battle, though.
(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
Davidson and Abraham were my advisors at Michigan, and part of my research
looked at minimal register requirements for optimal performance on an etc,
etc, etc... Your right, insert the appropriate set of problem restricting
However, the goal was primarily to find the register requirements to size an
architecture, not assign registers in a compiler. In other words, I threw
gobs of cpu cycles at it.
Meleis and Davidson took what I had and removed one of the most bothersome
restrictions, i.e. read-once. They then used an IP toolkit to find the
minimal number of required registers.
I wouldn't put it in your next compiler (though I suppose I might be
underestimating the horsepower of a tera based compiler), but I'm pretty sure
the results are optimal in the real sense of the word.
Return to the
Search the comp.compilers archives again.