RFA: patch for register migration

[Daniel Berlin]

On Apr 20, 2004, at 4:24 PM, Vladimir Makarov wrote:

>  This patch implements a register migration in reload.  Reload pass
> when it needs a hard register for a reload expells living
> pseudo-register from the hard register.  Then it tries to reassing a
> free hard register to the pseudo-register (function
> retry_global_alloc).  Usually it fails especially when the processor
> has few registers or there is a high register pressure in function. So
> finaly the pseudo-register is placed in memory.
>
>  Sometimes it is more profitable to use another hard register instead
> of memory for the pseudo-register.  It might be possible by expelling
> another rarely used pseudo-registers from their hard registers.  In
> own turn the expelled pseudo-registers can also migrate.
>
All of the above is a good idea, except for doing it in reload.
If the global/local register allocators are making unprofitable 
decisions, we shouldn't be undoing them in a *later pass* (which is 
what you are doing).  We should simply make it make the right decisions 
at allocation time (even if it requires the same type of algorithm).
This is what most compiler register allocators i've seen that work well 
do. Of course, everyone else has a global register allocator, not a 
local + global one.
Otherwise, we are wasting time doing allocations, then undoing them 
later (which is a losing proposition in general).
In the case of what you call "register migration", the global allocator 
should be deciding that what the local allocator did wasn't a good 
idea, and that it's better to spill some local register in favor of 
getting one for a "global" register.
If this isn't what is occurring that makes your "register migration" 
useful at all, then something is calculating costs wrong.
There is certainly no need to be doing this at actual spill time, and 
doing it there just makes reload larger, and makes some of the global 
allocation being done worthless. It's better to just not choose 
unprofitable situations in the first place.
In a smart, completely global allocator, what you call "register 
migration" would simply be part of choosing the colors we give to 
pseudos (we might see it was more profitable to spill these two other 
registers in order to give this one a color, etc).
If it's too hard to implement what you are doing as part of 
global-alloc, than we are in incredibly bad shape in terms of register 
allocation, since this is just another part of a good allocator.

--Dan