[prev in list] [next in list] [prev in thread] [next in thread] 

List:       gcc
Subject:    Re: Reload Pass
From:       "Vladimir N. Makarov" <vmakarov () redhat ! com>
Date:       2006-12-22 15:54:13
Message-ID: 458BFFA5.9020009 () redhat ! com
[Download RAW message or body]

Rajkishore Barik wrote:

>Hi,
>
>Thanks very much. I still have doubts on your suggestion:
>
>AFAIK, the back-end pass consists of (in order) : reg move -> insn sched 
>-> reg class -> local alloc -> global alloc -> reload -> post-reload.
>There are edges from reg move to reg class and reload back to global 
>alloc.
>
>In case I want to implement a linear scan which may split live ranges 
>(pseudos) into live intervals(smaller pseudos) and allocate different 
>registers
>for each of them. This process would break the whole loop. 
>
>So, what did you mean by --- "run this pass in between the register 
>allocator and
>reload, that would probably be doable."?
>
>
>  
>
Sorry, you were not specific.  When  I read your first message, I also 
thought that you were going to rewrite the reload pass in other words to 
use another algorithm make strict RTL when there are only hard registers 
and all insn constraints are satisfied.

As I understood correctly now, you are going to implement linear scan 
register allocator which also does what reload in gcc does.

The first of all you did not stated what are your project goals.  Is it 
better understanding how gcc register allocator and reload work (that is 
a good project then) or you want to write a better register allocator 
which will be used in gcc.  The second goal is hard to achieve because 
linear scan register allocator generates worse code than Chaitin-Briggs 
and the current gcc register allocator (Chow's priority based 
coloring).  Another problem is that the linear scan register allocation 
is patented.  Do you have permission to use it in gcc?  Currently we 
have permission to Chaitin's (IBM) and Brigg's (Rice university) 
patents.  We can not ignore patents as LLVM does not worry about patents 
which uses petented linear scan and Callahan-Koblentz register allocators.

IMHO, Ian wrote correctly that you can write a decent register allocator 
which does also reload stuff for one target (although even in this case 
number of details to keep in mind will be overwhelming) but it is a hard 
to write a decent code which works for all gcc targets.  So many efforts 
were used to improve reload for all gcc processors (even weird ones like 
SH with many registers but very small displacements or mcore with few 
registers and small displacements), you should do the same to be successful.

Reload does a lot of things not mentioned in Zack's document like 
register rematerialziation, virtual register elimination, address 
inheritance (which is important for processor with small address 
displacements) and few others.  There is opinion that doing some reload 
things before the register allocation will permit to generate a better 
code because register allocation will not worry about the constraints 
and reload will be more predictable (more accurately will work in less 
cases).  Such project already exists (see svn branches).

In any case your work on register allocation and reload will be 
appreciated by the community only please be prepared that it will be not 
an easy way.

Vlad
[prev in list] [next in list] [prev in thread] [next in thread]