Re: register allocation

[Jeff Law <law at redhat dot com>]

> > > 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.
> > That's largely what the ira-improv branch does.  Register classes at that
> > point are used primarily to drive the costing model.
> Actually, I tried on this branch disabling the improve_allocation
> function and now it is doing a great job.
> For some reason the improve_allocation function only damaged the good
> allocation that was done.
I'm sure Vlad will want to take a look at that, particularly if you've 
got a testcase for a target that's part of the mainline sources.  The 
whole point of that function is to spill a set of allocnos and using the 
hard regs for different allocnos when it seems profitable to do so.

> In order to look at that I am trying to understand the conflict table: I see
>
> ;; a3(r255,l0) conflicts: a4(r243,l0) a6(r129,l0) a8(r126,l0)
> a9(r254,l0) a10(r256,l0) a11(r257,l0) a12(r291,w0,l0) a12(r291,w1,l0)
> a13(r316,w0,l0) a13(r316,w1,l0) a14(r318,w0,l0) a14(r318,w1,l0)
> a15(r319,w0,l0) a15(r319,w1,l0) a16(r321,w0,l0) a16(r321,w1,l0)
> a5(r253,l0) a7(r252,l0) a17(r261,l0)
> ;;     total conflict hard regs: 53
> ;;     conflict hard regs: 53
>
> I see here conflicts of the pseudo with other pseudos and conflict
> with a hard reg - all are result of live range data.
Right.

> How is the constraint data which limits a pseudo in an insn to be of a
> certain class gets into this table?
Constraints are generally not used to drive conflict data, but instead 
are  to build the set of potential hard registers that can be used to 
satisfy a particular allocno and costing models.

> I have expected also all hard regs which are not allowed for this
> pseudo because of constraints in the insns to be also in the conflict
> table. I guess I miss something...
If a hard register can't be used for a particular allocno, then it's 
wasteful (in terms of memory and compilation speed) to represent 
conflicts between the unusable hard reg and the allocno.

> If it isn't there then how is it guranteed that the pseudo would be
> allocated to a hard reg which is allowed by the constraints?
The mental picture you should probably work with is build a union of all 
the registers allowed by the constraints.  Those are the set of hard 
registers that might be assigned to an allocno.  If a hard register 
isn't allowed by any constraint referenced by a particular allocno, then 
that hard register will not be part of the set of registers considered 
by IRA for that particular allocno.

Jeff