Re: Re: about Register Allocation Algorithm used in GCC

["Felix Yuan" <bigbrain at sohu dot com>]

Dear Mr.Michael Matz,

I am very grateful for your help.
We are developing a C compiler for a specific DSP.The DSP has its own instruction set and the architecture of its registers is also peculiar.
Can you give us some advices on the developing,especially the register allocator? 

Thanks!

	

on Tue,5 Nov 2002,Michael Matz wrote:

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

= = = = = = = = = = = = = = = = = = = 
				 
yours sincerely,

Felix Yuan
bigbrain@sohu.com
2002-11-08