Re: Graph coloring register allocation via iterative scan

Rob Thorpe wrote:
> 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).


Actually, the current Gcc register allocator is about 10Kloc plus
15Kloc of reload pass which was shared by the mentioned Briggs
allocator implementation (whose size was ~10Kloc). So the size of the
current gcc allocator and the Briggs allocator implementation was the
same.


But you are right, it is more about execution. The current gcc
register allocator was developed and refined during 18 years and
solves all register allocator tasks in some form (like coalescing,
rematerialization, live range splitting and part of code selection
which is specific for gcc). Few years spent by Michael Matz and
others to implement Briggs allocator is not enough to achieve the same
code quality especially in such multi-target compiler as gcc with its
very complicated register model presented in GCC RTL and machine
description.


As for comparison of graph colouring and iterative scan algorithms,
they are both heuristic and might work better for one programs and
worse for others. Common opinion is that graph colouring will work
better for programs with complicated CFG (like perlbmk in
SPECInt2000), bin packing, linear scan and iterative scan will work
better for programs with small number of big basic blocks (like fpppp
from SPECFp95). But modern register allocators frequently use some
form of combination of these two approaches.

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