about Register Allocation Algorithm used in GCC

[Michael Matz]

Hi,

On Tue, 5 Nov 2002, Felix Yuan wrote:

> where can I find the details of Register Allocation Algorithm used in
> GCC?

The current register allocator in GCC consists of two phases: one
allocating local pseudos (only defined and used in one basic block) to
registers, and one allocating the remaining pseudos used over basic block
borders.  It is able to handle register preferences in order to a) remove
copy insns, and b) limit the work reload later has to do.  The algorithms
itself are rather straight forward, but implemented ad hoc.  It should be
noted that both phases only allocate a hardreg to pseudos, but do not emit
spill code.  If you want to know how they work, read the extensive
comments in local-alloc.c and global.c.  regclass.c has some support
routines.  The part creating the spill insns is reload, but it also does
many other things, and you don't want to necessarily look into it if you
are new to gcc.  AFAIK there is no literature explaining the exact
algorithms used in GCC, but they really use general ideas, the local phase
uses linear scan, and the global phase a conflict graph.

Having said that, there is also work in progress to develop a new register
allocator (a preliminar version of it can be seen in CVS HEAD (-fnew-ra)),
which implements more common known algorithms (based on graph coloring,
currently it's a mixture of iterated and/or optimistic+ coalescing, using
interference region spilling, and an incremental conflict graph builder).
You can look into the ra*.[ch] files.

> Can you give me some reference books or articles about Register
> Allocation Algorithm? Thanks alot!

A good introduction into compiler backends (including register allocation)
is Muchnick: "Advanced Compiler Design & Implementation".  Morgan:
"Building an Optimizing Compiler" develops a different view on register
allocation.

For papers you want to try to search http://citeseer.nj.nec.com/cs for
register allocation.


Ciao,
Michael.