llvm dev - Sep 2010 - [LLVMdev] Multi-class register allocatable only in one class

Hi people,

the LinearScan register allocator tries to use same register for both  
live intervals, if the new interval is defined by a register copy  
whose destination reg is compatible with the source register. This is  
ok. However, this "check for compatibility" is wrongly done IMHO.

Say I have regclass1 with reg A, and regclass2 with regs {A, B}, but  
regclass2 defines only "B" as allocatable by RA.

A copy instruction:
<regclass2 dst> = <regclass1 src>
where src was allocated to register A will make dst be allocated also  
to A, even when it was defined as not allocatable in .td files.

This is due to the checking in RegAllocLinearScan:1004

           if (Reg && allocatableRegs_[Reg] &&
RC->contains(Reg))
             mri_->setRegAllocationHint(cur->reg, 0, Reg);

where "allocatableRegs_" is calculated during pass init, and ignores  
register class. I think this should be changed to:

           if (Reg && (tri_->getAllocatableSet(*mf_, RC))[Reg]
&& RC-
 >contains(Reg))
             mri_->setRegAllocationHint(cur->reg, 0, Reg);

or, if compilation speed discourages calling "getAllocatableSet" so  
often, create "allocatableRegs_" array per register-class, instead of
just one.

If it is ok I can create a patch (I would go to call every time and  
optimize for speed later if needed, but I can do either version, no  
problem) and send it to the list.

BR

Carlos

On Sep 13, 2010, at 6:59 AM, Carlos Sánchez de La Lama wrote:
> Hi people,
> 
> the LinearScan register allocator tries to use same register for both  
> live intervals, if the new interval is defined by a register copy  
> whose destination reg is compatible with the source register. This is  
> ok. However, this "check for compatibility" is wrongly done IMHO.
> 
> Say I have regclass1 with reg A, and regclass2 with regs {A, B}, but  
> regclass2 defines only "B" as allocatable by RA.
The register allocator assumes in many places that a register is either
allocatable or reserved independently of the register class.

That is, if a register is allocatable in one register class, it is assumed to be
allocatable from all register classes where it is present.

What are you trying to model?

/jakob

Hi Jakob,
>> Say I have regclass1 with reg A, and regclass2 with regs {A, B}, but
>> regclass2 defines only "B" as allocatable by RA.
>
> The register allocator assumes in many places that a register is  
> either allocatable or reserved independently of the register class.
Is there any reason for this? I mean, the methods for allowing one  
physical reg be considered allocatable to one regclass and not  
allocatable to another are already there, and this would just give  
more flexibility to what can be done with regclasses AFAIU.
> What are you trying to model?
Well... it is not straightforward to explain, and has taken me quite a  
while to find a way to model it.

In my machine, certain operations can only have some regs as  
destination. I am not defining just one machine but let's say a
"kind"
of similar machines, so I have separate cases, the number of regs that  
can be destination of, for example, "add", can vary from just one to  
several. They form the "AddRegs" class. Also, they are not spillable  
to stack, but they can be copied to general purpose IntRegs.

Say I have two additions on my code, and just one reg in AddRegs. The  
RA would run out of registers, so I change the ISel in a way the adds  
are selected to my machineinstr going to AddRegs followed by a move to  
IntRegs. I want these copies to be removed by the coalescer in case I  
have low pressure on AddRegs (because there are many of them, or  
because there are few additions). If AddRegs and IntRegs are disjoint,  
this wont happen, so I create another class (say "AuxClass") which  
includes regs in IntRegs and AddRegs.

Now, my code for an addition would result (after isel):

<AddRegs r1> = ADDr <whatever> <whatever>
<AuxClass r2> = <AddRegs r1>
...
...
<something> = use <r2>

If pressure on AddRegs is low, coalescer will join r1 and r2 to  
AddRegs class (common subclass), as before the copies were added. And  
if pressure on AddRegs is high, the copy will be kept, as intended.  
But I want RA to chose an IntReg when allocating r2, and as AuxClass  
needs to be a superclass of both AddRegs and IntRegs, the only way I  
found is to constrain allocatable regs. That is, AddRegs are  
allocatable, but not when allocating a reg from AuxClass.

Hope you got the point, I am sorry for the long explanation, and  
thanks a lot for your help and interest :)

Carlos