[ARM][CodeGen] Enabling spilling of high registers in RegAllocFast for Thumb1

[pratlucas]

Summary

High registers - r8 until r12 - have no load/store instructions in
Thumb1 and, therefore, are not generally allocatable in Thumb1 mode.
When registers of this class are clobbered by inline assembly, though,
the Fast Register Allocator may be required to spill those registers.

In such conditions, the Fast Register Allocator hit an assertion failure
when trying to spill high registers to the satck through
TargetRegisterInfo's storeRegToStackSlot.

This patch enables the register allocator to use an auxiliary register
for the spill operation, introducing a new hook for the target inform
the proper register class to be used in loads/stores.

This patch is based on the discussion from D49364. The changes were written
from scratch, as there were significant changes to RegAllocFast since then.

[pratlucas]

Removing unecessary include and fixing formatting.

[efriedma]

This is intentionally not addressing greedy regalloc, I guess.

I think ConstantIslands currently assumes LR is never live in Thumb1 mode. Have you looked at that at all? (Last time I looked at this, there was also ThumbRegisterInfo::saveScavengerRegister, but that's gone now.)

llvm/lib/CodeGen/RegAllocFast.cpp

343

Is it possible to spuriously run out of registers? Say you have an inline asm that requires r0-r8. You allocate r0-r7, then try to allocate r8, then we run out of registers because r0-r7 were already reserved.

[arsenm]

llvm/lib/CodeGen/RegAllocFast.cpp

211

This needs rebasing on top of 66251f7e1de79a7c1620659b7f58352b8c8e892e

[pratlucas]

Rebasing on top of rG66251f7e1de7.

[pratlucas]

This is intentionally not addressing greedy regalloc, I guess.

Yes. Currently, RegAllocFast is the only one that finds itself in need of spilling high registers. Other register allocators detect the interference between the inline asm inputs and the clobbered registers before allocating them, avoiding the spill.
If we ever want to make the high registers generally allocatable, though, the other allocators also need to be updated.

I think ConstantIslands currently assumes LR is never live in Thumb1 mode. Have you looked at that at all? (Last time I looked at this, there was also ThumbRegisterInfo::saveScavengerRegister, but that's gone now.)

From what I've checked, ConstantIslands assumes LR was spilled in the function epilog, so it is legal for it to make use of BL instructions.
This could only have an impact on explicit uses or clobbers of LR by the inline asm itself, which were already possible prior to this patch, so I believe it won't cause any issues.

llvm/lib/CodeGen/RegAllocFast.cpp

343

Yes, it is possible but in rare circumstances as the high registers aren't generally allocatable.

For this to happen the specified high register needs a reason to be spilled, so it should either be high on the allocation order or the inline asm should have enough inputs to cause it to be previously allocated.

As we can't directly spill it, the only way I see around this is to re-allocate the clobbered registers to another available register whenever possible. If you agree, I can handle this in a separate patch as it might be out of this one's scope.

[arsenm]

llvm/lib/CodeGen/RegAllocFast.cpp

610–611

Can you split these NFC changes into a separate patch? I want to avoid yet another rebase nightmare for D52010

1038

I don't think any of these new markRegUsedInInstr calls are correct

[efriedma]

This could only have an impact on explicit uses or clobbers of LR by the inline asm itself, which were already possible prior to this patch, so I believe it won't cause any issues.

It won't cause any "new" issues, in some sense; it's probably feasible to write a testcase without this patch. But this patch probably makes it easier to trigger.

[pratlucas]

After taking a deeper look at ARMConstantIslandPass, I believe this patch won't actually cause any issues when interacting with it.

Please correct me if I'm wrong, but from what I've checked the pass's dependency on LR not being live is simply to allow it to replace unconditional branches that are out of range with BL instructions, which overrides the contents of LR.
Also, the pass doesn't seem to handle the contents of inline asm, keeping the user's assembly code as it is.

As LR is a high register, the only impact this patch has on it is allowing RegAllocFast to spill it when necessary - i.e. when its was intentionally clobbered by the user.
Clobbering it is the only way I see for LR to become live again and it was already a possibility before.

Note that LR is the last on the allocation order for high registers. Due to that, the only scenario I've found where we see a difference in behavior for the clobbering of LR would be when LR is required to handle the inline asm's inputs.
For example:

void constraint_h(int a, b, c, d, e, f) {
  asm volatile("mov lr, %5"
    :
    : "h" (a), "h" (b), "h" (c), "h" (d), "h" (e), "h" (f)
    : "lr");
}

Here, RegAllocFast previously hit the assertion failure and after the patch hits the following error:

error: inline assembly requires more registers than available

Other attempts to clobber LR are handled with no issues both before and after this patch.

[pratlucas]

Splitting NFC changes into a separate patch.

[pratlucas]

llvm/lib/CodeGen/RegAllocFast.cpp

610–611

Done! NFC is at D81942.

1038

Those aren't actually new. I've added them here to replace the one removed from definePhysReg.

[efriedma]

Please correct me if I'm wrong, but from what I've checked the pass's dependency on LR not being live is simply to allow it to replace unconditional branches that are out of range with BL instructions, which overrides the contents of LR.

Correct. The problem would be if lr were live across a branch. If an inline asm has lr as an input or output, lr has a live range which could contain a branch. Even if there aren't any such branches when regalloc runs, later transforms can introduce them. (ConstantIslands itself can introduce branches, but I'm not sure if those branches would ever need to be relaxed.)

It's definitely realistic to construct a testcase at higher optimization levels. Thinking about it a bit more, I'm having trouble coming up with a testcase that would trigger at -O0 specifically, though. It would be difficult to construct a testcase where lr is alive across a branch during isel, given the way inline asm operands are constructed, and the post-isel optimizations are very limited.

Also, the pass doesn't seem to handle the contents of inline asm, keeping the user's assembly code as it is.

Correct.

[pratlucas]

The changes from D52010 have removed the conflict that made the spilling of high register necessary.
This patch is no longer relevant. D96335 adds a test covering the high register clobbering scenario.

llvm/include/llvm/CodeGen/TargetRegisterInfo.h

public:
   /// to or from. If it is possible to copy the register directly without using
   /// a cross register class copy, return the specified RC. Returns NULL if it
   /// is not possible to copy between two registers of the specified class.
   virtual const TargetRegisterClass *
   getCrossCopyRegClass(const TargetRegisterClass *RC) const {
     return RC;
   }
 
+  /// Returns the register class that should be used to perform a spill of the
+  /// specified register class to stack.
+  ///
+  /// \note A different register class might be required for targets where not
+  /// all registers can be stored/loaded into memory
+  virtual const TargetRegisterClass *
+  getRegClassForStackSpill(const MachineFunction &MF,
+                           const TargetRegisterClass *Class) const {
+    return Class;
+  }
+
   /// Returns the largest super class of RC that is legal to use in the current
   /// sub-target and has the same spill size.
   /// The returned register class can be used to create virtual registers which
   /// means that all its registers can be copied and spilled.
   virtual const TargetRegisterClass *
   getLargestLegalSuperClass(const TargetRegisterClass *RC,
                             const MachineFunction &) const {
     /// The default implementation is very conservative and doesn't allow the

llvm/lib/CodeGen/RegAllocFast.cpp

#endif
     LiveRegMap::iterator findLiveVirtReg(Register VirtReg) {
       return LiveVirtRegs.find(Register::virtReg2Index(VirtReg));
     }
 
     LiveRegMap::const_iterator findLiveVirtReg(Register VirtReg) const {
       return LiveVirtRegs.find(Register::virtReg2Index(VirtReg));
     }
 
     MCPhysReg getBestRegForAllocation(const TargetRegisterClass &Class,
                                       Register Hint0, Register Hint1) const;
     MCPhysReg getFreeRegForAllocation(MachineInstr &MI,
                                       const TargetRegisterClass &Class,
                                       Register Hint0, Register Hint1);
     void allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint);
     void allocVirtRegUndef(MachineOperand &MO);
     MCPhysReg defineVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg,
                             Register Hint);

 /// DBG_VALUEs with \p VirtReg operands with the stack slot.
 void RegAllocFast::spill(MachineBasicBlock::iterator Before, Register VirtReg,
                          MCPhysReg AssignedReg, bool Kill) {
   LLVM_DEBUG(dbgs() << "Spilling " << printReg(VirtReg, TRI)
                     << " in " << printReg(AssignedReg, TRI));
   int FI = getStackSpaceFor(VirtReg);
   LLVM_DEBUG(dbgs() << " to stack slot #" << FI << '\n');
 
-  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
-  TII->storeRegToStackSlot(*MBB, Before, AssignedReg, Kill, FI, &RC, TRI);
+  const TargetRegisterClass *RC = MRI->getRegClass(VirtReg);
+  const TargetRegisterClass *SpillRC =
+      TRI->getRegClassForStackSpill(*MBB->getParent(), RC);
+  // If current register class cannot be directly spilled, copy to another
+  // register of the appropriate class before storing.
+  if (RC != SpillRC) {
+    MCPhysReg SpillReg =
+        getFreeRegForAllocation(*Before, *SpillRC, Register(), Register());
+    BuildMI(*MBB, Before, Before->getDebugLoc(), TII->get(TargetOpcode::COPY),
+            SpillReg)
+        .addReg(AssignedReg, llvm::RegState::Kill);
+    AssignedReg = SpillReg;
+  }
+  TII->storeRegToStackSlot(*MBB, Before, AssignedReg, Kill, FI, SpillRC, TRI);
   ++NumStores;
 
   // If this register is used by DBG_VALUE then insert new DBG_VALUE to
   // identify spilled location as the place to find corresponding variable's
   // value.
   SmallVectorImpl<MachineInstr *> &LRIDbgValues = LiveDbgValueMap[VirtReg];
   for (MachineInstr *DBG : LRIDbgValues) {
     MachineInstr *NewDV = buildDbgValueForSpill(*MBB, Before, *DBG, FI);
     assert(NewDV->getParent() == MBB && "dangling parent pointer");
     (void)NewDV;
     LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:\n" << *NewDV);
   }
   // Now this register is spilled there is should not be any DBG_VALUE
   // pointing to this register because they are all pointing to spilled value
   // now.
   LRIDbgValues.clear();
 }
 
 /// Insert reload instruction for \p PhysReg before \p Before.
 void RegAllocFast::reload(MachineBasicBlock::iterator Before, Register VirtReg,
                           MCPhysReg PhysReg) {
   LLVM_DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into "
                     << printReg(PhysReg, TRI) << '\n');
   int FI = getStackSpaceFor(VirtReg);
-  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
-  TII->loadRegFromStackSlot(*MBB, Before, PhysReg, FI, &RC, TRI);
+  const TargetRegisterClass *RC = MRI->getRegClass(VirtReg);
+  const TargetRegisterClass *SpillRC =
+      TRI->getRegClassForStackSpill(*MBB->getParent(), RC);
+  // If current register class cannot be directly loaded, get an intermediate
+  // register of the appropriate class then copy the loaded value
+  MCPhysReg SpillReg = PhysReg;
+  if (RC != SpillRC) {
+    SpillReg =
+        getFreeRegForAllocation(*Before, *SpillRC, Register(), Register());
+  }
+
+  TII->loadRegFromStackSlot(*MBB, Before, SpillReg, FI, SpillRC, TRI);
   ++NumLoads;
+
+  // Copy back to original register if necessary
+  if (SpillReg != PhysReg) {
+    BuildMI(*MBB, Before, Before->getDebugLoc(), TII->get(TargetOpcode::COPY),
+            PhysReg)
+        .addReg(SpillReg, llvm::RegState::Kill);
+  }
 }
 
 /// Return true if MO is the only remaining reference to its virtual register,
 /// and it is guaranteed to be a block-local register.
 bool RegAllocFast::isLastUseOfLocalReg(const MachineOperand &MO) const {
   // If the register has ever been spilled or reloaded, we conservatively assume
   // it is a global register used in multiple blocks.
   if (StackSlotForVirtReg[MO.getReg()] != -1)
if (isCoalescable(MI)) {
         return Reg;
     }
 
     if (++C >= DefLimit)
       break;
   }
   return Register();
 }
 
 /// Finds out which is the best register available to allocate a virtual
 /// register of the specified class, taking the hints whenever possible.
 MCPhysReg
 RegAllocFast::getBestRegForAllocation(const TargetRegisterClass &Class,
                                       Register Hint0, Register Hint1) const {
   // Try hints first
   if (Hint0.isPhysical() && MRI->isAllocatable(Hint0) &&
       Class.contains(Hint0) && (calcSpillCost(Hint0) < spillDirty))
     return Hint0;
if (Register::isVirtualRegister(Reg)) {
       continue;
     }
     if (!MRI->isAllocatable(Reg)) continue;
     if (MO.isUse()) {
       usePhysReg(MO);
     } else if (MO.isEarlyClobber()) {
       definePhysReg(MI, Reg,
                     (MO.isImplicit() || MO.isDead()) ? regFree : regReserved);
       markRegUsedInInstr(Reg);
       hasEarlyClobbers = true;
     } else
       hasPhysDefs = true;
   }
 
   // The instruction may have virtual register operands that must be allocated
   // the same register at use-time and def-time: early clobbers and tied
   // operands. If there are also physical defs, these registers must avoid

llvm/lib/Target/ARM/ARMBaseRegisterInfo.h

public:
 
   const TargetRegisterClass *
   getPointerRegClass(const MachineFunction &MF,
                      unsigned Kind = 0) const override;
   const TargetRegisterClass *
   getCrossCopyRegClass(const TargetRegisterClass *RC) const override;
 
   const TargetRegisterClass *
+  getRegClassForStackSpill(const MachineFunction &MF,
+                           const TargetRegisterClass *Class) const override;
+
+  const TargetRegisterClass *
   getLargestLegalSuperClass(const TargetRegisterClass *RC,
                             const MachineFunction &MF) const override;
 
   unsigned getRegPressureLimit(const TargetRegisterClass *RC,
                                MachineFunction &MF) const override;
 
   bool getRegAllocationHints(Register VirtReg, ArrayRef<MCPhysReg> Order,
                              SmallVectorImpl<MCPhysReg> &Hints,

llvm/lib/Target/ARM/ARMBaseRegisterInfo.cpp

 
 const TargetRegisterClass *
 ARMBaseRegisterInfo::getCrossCopyRegClass(const TargetRegisterClass *RC) const {
   if (RC == &ARM::CCRRegClass)
     return &ARM::rGPRRegClass;  // Can't copy CCR registers.
   return RC;
 }
 
+const TargetRegisterClass *ARMBaseRegisterInfo::getRegClassForStackSpill(
+    const MachineFunction &MF, const TargetRegisterClass *Class) const {
+  const ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
+  if (AFI->isThumb1OnlyFunction() && ARM::hGPRRegClass.hasSubClassEq(Class))
+    return &ARM::tGPRRegClass;
+  return Class;
+}
+
 unsigned
 ARMBaseRegisterInfo::getRegPressureLimit(const TargetRegisterClass *RC,
                                          MachineFunction &MF) const {
   const ARMSubtarget &STI = MF.getSubtarget<ARMSubtarget>();
   const ARMFrameLowering *TFI = getFrameLowering(MF);
 
   switch (RC->getID()) {
   default:

llvm/test/CodeGen/Thumb/high-reg-spill.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -run-pass regallocfast %s -o - | FileCheck %s
+
+--- |
+  ; ModuleID = 'test.c'
+  source_filename = "test.c"
+  target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
+  target triple = "thumbv6m-arm-none-eabi"
+
+  define dso_local void @constraint_h(i32 %i) {
+  entry:
+    %i.addr = alloca i32, align 4
+    store i32 %i, i32* %i.addr, align 4
+    %0 = load i32, i32* %i.addr, align 4
+    call void asm sideeffect "mov r12, $0", "h,~{r12}"(i32 %0)
+    ret void
+  }
+
+...
+---
+name:            constraint_h
+alignment:       2
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: tgpr }
+  - { id: 1, class: hgpr }
+  - { id: 2, class: tgpr }
+liveins:
+  - { reg: '$r0', virtual-reg: '%0' }
+frameInfo:
+  maxAlignment:    4
+  maxCallFrameSize: 0
+  localFrameSize:  4
+stack:
+  - { id: 0, name: i.addr, size: 4, alignment: 4, local-offset: -4 }
+machineFunctionInfo: {}
+body:             |
+  bb.0.entry:
+    liveins: $r0
+
+    ; CHECK-LABEL: name: constraint_h
+    ; CHECK: liveins: $r0
+    ; CHECK: tSTRspi killed renamable $r0, %stack.0.i.addr, 0, 14 /* CC::al */, $noreg :: (store 4 into %ir.i.addr)
+    ; CHECK: renamable $r0 = tLDRspi %stack.0.i.addr, 0, 14 /* CC::al */, $noreg :: (dereferenceable load 4 from %ir.i.addr)
+    ; CHECK: renamable $r12 = COPY killed renamable $r0
+    ; CHECK: $r0 = COPY killed $r12
+    ; CHECK: tSTRspi killed $r0, %stack.1, 0, 14 /* CC::al */, $noreg :: (store 4 into %stack.1)
+    ; CHECK: $r0 = tLDRspi %stack.1, 0, 14 /* CC::al */, $noreg :: (load 4 from %stack.1)
+    ; CHECK: $r8 = COPY killed $r0
+    ; CHECK: INLINEASM &"mov r12, $0", 1 /* sideeffect attdialect */, 1048585 /* reguse:hGPR */, renamable $r8, 12 /* clobber */, implicit-def early-clobber $r12
+    ; CHECK: tBX_RET 14 /* CC::al */, $noreg
+    %0:tgpr = COPY $r0
+    tSTRspi %0, %stack.0.i.addr, 0, 14 /* CC::al */, $noreg :: (store 4 into %ir.i.addr)
+    %2:tgpr = tLDRspi %stack.0.i.addr, 0, 14 /* CC::al */, $noreg :: (dereferenceable load 4 from %ir.i.addr)
+    %1:hgpr = COPY %2
+    INLINEASM &"mov r12, $0", 1 /* sideeffect attdialect */, 1048585 /* reguse:hGPR */, %1, 12 /* clobber */, implicit-def early-clobber $r12
+    tBX_RET 14 /* CC::al */, $noreg
+
+...

llvm/test/CodeGen/Thumb/no-regs-available.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: not llc -run-pass regallocfast %s -o - 2>&1 | FileCheck %s
+
+--- |
+  ; ModuleID = 'all-high-regs.c'
+  source_filename = "all-high-regs.c"
+  target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
+  target triple = "thumbv6m-arm-none-eabi"
+
+  define dso_local void @constraint_h(i32 %i) {
+  entry:
+    %i.addr = alloca i32, align 4
+    store i32 %i, i32* %i.addr, align 4
+    %0 = load i32, i32* %i.addr, align 4
+    call void asm sideeffect "mov r12, $0", "h,~{r12},~{r8},~{r9},~{r10},~{r11},~{lr}"(i32 %0)
+    ret void
+  }
+
+...
+---
+name:            constraint_h
+alignment:       2
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: tgpr }
+  - { id: 1, class: hgpr }
+  - { id: 2, class: tgpr }
+liveins:
+  - { reg: '$r0', virtual-reg: '%0' }
+frameInfo:
+  maxAlignment:    4
+  maxCallFrameSize: 0
+  localFrameSize:  4
+stack:
+  - { id: 0, name: i.addr, size: 4, alignment: 4, local-offset: -4 }
+machineFunctionInfo: {}
+body:             |
+  bb.0.entry:
+    liveins: $r0
+
+    %0:tgpr = COPY $r0
+    tSTRspi %0, %stack.0.i.addr, 0, 14 /* CC::al */, $noreg :: (store 4 into %ir.i.addr)
+    %2:tgpr = tLDRspi %stack.0.i.addr, 0, 14 /* CC::al */, $noreg :: (dereferenceable load 4 from %ir.i.addr)
+    %1:hgpr = COPY %2
+    INLINEASM &"mov r12, $0", 1 /* sideeffect attdialect */, 1048585 /* reguse:hGPR */, %1, 12 /* clobber */, implicit-def early-clobber $r12, 12 /* clobber */, implicit-def early-clobber $r8, 12 /* clobber */, implicit-def early-clobber $r9, 12 /* clobber */, implicit-def early-clobber $r10, 12 /* clobber */, implicit-def early-clobber $r11, 12 /* clobber */, implicit-def early-clobber $lr
+    tBX_RET 14 /* CC::al */, $noreg
+
+...
+
+# CHECK: error: inline assembly requires more registers than available
+