Re: register allocation

[Vladimir Makarov <vmakarov at redhat dot com>]

On 01/03/2011 10:41 AM, Jeff Law wrote:
> On 12/27/10 08:43, roy rosen wrote:
> > > I'd recommend to try ira-improv branch.  I think that part of the 
> > > problem is
> > > in usage of cover classes.  The branch removes the cover classes and 
> > > permits
> > > IRA to use intersected register classes and that helps to assign 
> > > better hard
> > > registers.
Sorry for the delay with the answer.  I was on vacation last week.
> > I tried now this branch and got better results for some cases but
> > still in other cases I get lots of redundent register copies.
> > I might be missing something from the gcc history but I wonder why do
> > we need to limit the coloring stage to select a hard reg from a class
> > that was chosen by a prior stage.
In some cases, using all hard registers could improve the allocation.  
For example, usage of a pseudo for transferring value from one memory to 
another is such a case.  In this case, we could use general hard 
register or floating hard registers if there are no free general hard 
registers.

But in the most cases, usage of all hard registers is terrible idea for 
coloring because it results in wrong pseudos spilling.  For example, if 
usage of floating point hard register is less profitable than memory, 
although it will never get floating point hard register in function 
assign_hard_reg whose decision is based on costs, we will still put the 
pseudo as colorable on the stack because even if there are not enough 
general hard register, CB algorithm still count it as colorable because 
there are floating point hard registers available.  The order of pseudos 
on the stack actually defines what pseudos will be spilled.

Also original CB works on non-intersected register classes.

Those are reasons for the current IRA implementation.

> >
> It was a design decision with the introduction of IRA.  It made 
> certain problems easier to resolve at the time and in reality, most of 
> the time the set of legitimate and profitable hard registers for a 
> given pseudo maps to a register class reasonably well.
>
> > Why not simply put in the interference graph edges for all registers
> > which are not possible for a pseudo and let the coloring algorithm
> > select the best hard reg.
It is already implemented but in more efficient way through macro 
ALLOCNO_AVAILABLE_REGS_NUMS.
> >
> That's largely what the ira-improv branch does.  Register classes at 
> that point are used primarily to drive the costing model.
In other words, ira-improv permits CB works on intersected register 
classess and do better allocation for the 1st example above.