[LLVMdev] Multi-class register allocatable only in one class

[Jakob Stoklund Olesen]

On Sep 13, 2010, at 12:13 PM, Carlos Sánchez de La Lama wrote:

>>> 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.

The goal is to keep the register constraints as simple as possible while keeping them useful for real world targets.

The constraints are already way more complicated that what most academics assume when researching register allocation algorithms. We don't want to widen the gap.

We currently have a fairly well-defined concept of reserved registers. Ideally, the allocatable registers should be just the complement.


>> 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.

For weird stuff like this, it is usually better to present a more abstract model to the register allocator. Look at how it is done for the X87 floating point stack registers.

> 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.

The coalescer is really doing the same thing as the register allocator when coalescing. It will only join allocatable registers.

/jakob