Re: Graph coloring register allocation via iterative scan

avayvod@gmail.com wrote:
> I wonder whether register allocation via graph coloring (improved by
> Preston Briggs) is commonly better than iterative scan algortihm
> (introduced by Alkis Evlogimenos). In what cases one is better than
> the other? Are there some theoretical proofs of dominance of one of
> the methods?
>
> By being better I mean producing more efficient code with less register
> spills.


Register allocation algorithms can be complicated. As important as
good code is producing something that allocates fast enough not to
hurt compile times too much, this was the intention of linear scan.


It also can be very difficult to bolt a particular algorithm into a
particular compiler. A while ago an attempt was made to put a Briggs
like allocator into GCC, but GCC's backend had a completely different
point of view of the machine making it very complex. The authors
ended up writing something like 16Kloc to do something that in so
compilers only takes ~1Kloc, and in the end gave up. So GCC still
uses something else (an odd variation of the Chow/Hennessey algorithm
I think).

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