[LLVMdev] [PATCH] RegScavenger::scavengeRegister

[Jakob Stoklund Olesen]

On Apr 7, 2013, at 12:35 PM, Hal Finkel <hfinkel at anl.gov> wrote:

>> The types on register classes are only used by isel, and this
>> register class wouldn't be used before register allocation. Just
>> make it [i32], or even [untyped]. (The type is used to pick a
>> default spill size, so you may need to 'let Size = 4' if you go with
>> untyped).
>> 
>> Your implementation in copyPhysReg is the final word on what it means
>> to copy between registers in this class.
>> 
>> The register class will not be used automatically without permission
>> from your implementation of getLargestLegalSuperClass. This function
>> should not allow normal GPR registers to be inflated to the GPR+CR
>> super-class because not all registers in that class have enough
>> bits.
>> 
>> X86RegisterInfo::getLargestLegalSuperClass() does something similar
>> with the GR8_NOREX register class to work around some awkward x86
>> encoding issues with the 20 8-bit registers.
> 
> Okay, thanks! So when the RA decides to use this register inflation mechanism, it decides on both the inflation point and the deflation point at the same time? I'd like to understand this better, can you please provide a pointer to the logic for this?

When the register allocator runs out of registers, it tries splitting the live range it is currently looking at (RAGreedy::selectOrSplit). If splitting was successful, there may be an opportunity to choose a larger register class for some of the parts. The original register class was selected as the intersection of the constraints imposed by all the users of the virtual register. The new live ranges each have fewer users, so they may be less constrained.

The splitter calls LiveRangeEdit::calculateRegClassAndHint() which calls MachineRegisterInfo::recomputeRegClass() for each of the new virtual registers created by splitting an old one.

The new register class is computed by starting from getLargestLegalSuperClass(OldRC) and then applying the constraints from each use in turn.

The register allocator is more aggressive about splitting live ranges when it sees a register class that is inflatable. See the checks for isProperSubClass() here and there. In particular, it may split around a single instruction, and that is how the cross-class spilling works.

Suppose:

  %vreg0 = CMP ...; %vreg0:CRRC
...
  BRANCH %vreg0; %vreg0:CRRC

Live range splitting can split around the individual instructions to produce:

  %vreg1 = CMP ...; %vreg1:CRRC
  %vreg2 = COPY %vreg1
...
  %vreg3 = COPY %vreg2; %vreg3:CRRC
  BRANCH %vreg3; %vreg3:CRRC
  
The tiny live ranges %vreg1 and %vreg3 are constrained to CRRC by their users, but %vreg2 is only used by COPY instructions which don't impose any constraints.

This means the %vreg2 gets whatever register class is returned by getLargestLegalSuperClass(CRRC). If that class contains the GPRs there is a good chance we will be able to find a register.

Now, the same thing can happen when splitting a GPRC register, and so it is important that getLargestLegalSuperClass(GPRC) only returns register classes with all 32/64 bits.

/jakob