Re: 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."


Its good to see somebody else who fights the good fight. It appears to be
a losing battle, though.


      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.


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


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.




Bill
--

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