FastRegAlloc: Fix implicit operands not rewritten

[gbossu]

Summary

This patch fixes a potential crash due to RegAllocFast not rewriting virtual registers. This essentially happens because of a call to MachineInstr::addRegisterKilled() in the process of allocating a "killed" vreg. The former can eventually delete implicit operands without RegAllocFast noticing, leading to some operands being "skipped" and not rewritten to use physical registers.

Note that I noticed this crash when working on a solution for tying a register with one/multiple of its sub-registers within an instruction. (See problem description here: https://discourse.llvm.org/t/pass-to-tie-an-output-operand-to-a-subregister-of-an-input-operand/67184).

Aside from this fix, I believe there could be further improvements to the RegAllocFast when it comes to instructions with multiple uses of a same virtual register. You can see it in the added test where the implicit uses have been re-written in a somewhat surprising way because of phase ordering. Ultimately, when allocating vregs for an instruction, I believe we should iterate on the vregs it uses (and then process all the operands that use this vregs), instead of directly iterating on operands and somewhat assuming each operand uses a different vreg. This would in the end be quite close to what greedy+virtregrewriter does. If that makes sense, I would probably spin off another patch (after I get more familiar with RegAllocFast).

[arsenm]

Processing all uses of a register at once makes sense to me

llvm/lib/CodeGen/RegAllocFast.cpp

1444

Don't you only need to maybe repeat if you saw a kill use?

[gbossu]

llvm/lib/CodeGen/RegAllocFast.cpp

1444

At the moment, that is right. I just preferred to play it safe because some of the callees inside RegAllocFast::setPhysReg() could potentially mess around with implicit operands further. Although, to this date, I haven't found any other case :) Tbh, it's also not easy to find out whether useVirtReg() has changed any implicit operands, so I preferred to be conservative.

[gbossu]

Any additional feedback?

[qcolombet]

llvm/lib/CodeGen/RegAllocFast.cpp

1444

TL;DR only redo the loop when something changes.

Could we modify useVirtReg to surface whether or not something changed?
It should be possible to surface addRegisterKilled and whatnot that setPhysReg uses.

Bonus point would be to differentiate when we add an operand (actually removing is the issue here) vs. when we just update one, but we can cross that bridge later if compile time is problematic.

I guess we also could be clever and instead of redoing all the iterations of the loop only tweak how the iterator moves (i.e., don't advance if there is a change), but that's probably not worth and may be being too clever for our own good.

[gbossu]

Re-process MachineOperands when kill/dead flags are added. Adding those on implicit operands might re-arrange the whole list of MOs in a MachineInstr.

[gbossu]

llvm/lib/CodeGen/RegAllocFast.cpp

1444

Sorry it took me some time to get back to this patch. I changed a couple of functions to propagate whether kill/dead flags were added, in which case I assume the list of MOs might have been re-arranged.

I cannot say I'm 100% happy about the change, there are lots of nesting levels in RegAllocFast, and I'm essentially adding a new one. I could move some more logic in separate functions (like I did for findAndSortDefOperandIndexes) to help readability if needed. So far I tried to strike a balance between keeping the code readable and also not refactor too much. Suggestions are welcome for further improvements.

[qcolombet]

llvm/lib/CodeGen/RegAllocFast.cpp

1444

Let's go with that for now

[gbossu]

llvm/lib/CodeGen/RegAllocFast.cpp

1444

Great, thanks for the review. I believe I still do not have "write" permission. Could you maybe commit on my behalf? Here are my details: Gaëtan Bossu <[e-mail]>.

[qcolombet]

Sure!
I'll probably do that beginning of next week.

llvm/lib/CodeGen/RegAllocFast.cpp

namespace {
   private:
     bool runOnMachineFunction(MachineFunction &MF) override;
 
     void allocateBasicBlock(MachineBasicBlock &MBB);
 
     void addRegClassDefCounts(std::vector<unsigned> &RegClassDefCounts,
                               Register Reg) const;
 
+    void findAndSortDefOperandIndexes(const MachineInstr &MI);
+
     void allocateInstruction(MachineInstr &MI);
     void handleDebugValue(MachineInstr &MI);
     void handleBundle(MachineInstr &MI);
 
     bool usePhysReg(MachineInstr &MI, MCPhysReg PhysReg);
     bool definePhysReg(MachineInstr &MI, MCPhysReg PhysReg);
     bool displacePhysReg(MachineInstr &MI, MCPhysReg PhysReg);
     void freePhysReg(MCPhysReg PhysReg);
private:
     }
 
     void assignVirtToPhysReg(MachineInstr &MI, LiveReg &, MCPhysReg PhysReg);
     void allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint,
                       bool LookAtPhysRegUses = false);
     void allocVirtRegUndef(MachineOperand &MO);
     void assignDanglingDebugValues(MachineInstr &Def, Register VirtReg,
                                    MCPhysReg Reg);
-    void defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,
+    bool defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,
                                   Register VirtReg);
-    void defineVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg,
+    bool defineVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg,
                        bool LookAtPhysRegUses = false);
-    void useVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg);
+    bool useVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg);
 
     MachineBasicBlock::iterator
     getMBBBeginInsertionPoint(MachineBasicBlock &MBB,
                               SmallSet<Register, 2> &PrologLiveIns) const;
 
     void reloadAtBegin(MachineBasicBlock &MBB);
-    void setPhysReg(MachineInstr &MI, MachineOperand &MO, MCPhysReg PhysReg);
+    bool setPhysReg(MachineInstr &MI, MachineOperand &MO, MCPhysReg PhysReg);
 
     Register traceCopies(Register VirtReg) const;
     Register traceCopyChain(Register Reg) const;
 
     bool shouldAllocateRegister(const Register Reg) const;
     int getStackSpaceFor(Register VirtReg);
     void spill(MachineBasicBlock::iterator Before, Register VirtReg,
                MCPhysReg AssignedReg, bool Kill, bool LiveOut);
if (SubRegIdx != 0) {
     MO.setSubReg(0);
   }
   MO.setReg(PhysReg);
   MO.setIsRenamable(true);
 }
 
 /// Variation of defineVirtReg() with special handling for livethrough regs
 /// (tied or earlyclobber) that may interfere with preassigned uses.
-void RegAllocFast::defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,
+/// \return true if MI's MachineOperands were re-arranged/invalidated.
+bool RegAllocFast::defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,
                                             Register VirtReg) {
   if (!shouldAllocateRegister(VirtReg))
-    return;
+    return false;
   LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
   if (LRI != LiveVirtRegs.end()) {
     MCPhysReg PrevReg = LRI->PhysReg;
     if (PrevReg != 0 && isRegUsedInInstr(PrevReg, true)) {
       LLVM_DEBUG(dbgs() << "Need new assignment for " << printReg(PrevReg, TRI)
                         << " (tied/earlyclobber resolution)\n");
       freePhysReg(PrevReg);
       LRI->PhysReg = 0;
bool RegAllocFast::defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,
   return defineVirtReg(MI, OpNum, VirtReg, true);
 }
 
 /// Allocates a register for VirtReg definition. Typically the register is
 /// already assigned from a use of the virtreg, however we still need to
 /// perform an allocation if:
 /// - It is a dead definition without any uses.
 /// - The value is live out and all uses are in different basic blocks.
-void RegAllocFast::defineVirtReg(MachineInstr &MI, unsigned OpNum,
+///
+/// \return true if MI's MachineOperands were re-arranged/invalidated.
+bool RegAllocFast::defineVirtReg(MachineInstr &MI, unsigned OpNum,
                                  Register VirtReg, bool LookAtPhysRegUses) {
   assert(VirtReg.isVirtual() && "Not a virtual register");
   if (!shouldAllocateRegister(VirtReg))
-    return;
+    return false;
   MachineOperand &MO = MI.getOperand(OpNum);
   LiveRegMap::iterator LRI;
   bool New;
   std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
   if (New) {
     if (!MO.isDead()) {
       if (mayLiveOut(VirtReg)) {
         LRI->LiveOut = true;
if (LRI->Reloaded || LRI->LiveOut) {
     }
     LRI->LiveOut = false;
     LRI->Reloaded = false;
   }
   if (MI.getOpcode() == TargetOpcode::BUNDLE) {
     BundleVirtRegsMap[VirtReg] = PhysReg;
   }
   markRegUsedInInstr(PhysReg);
-  setPhysReg(MI, MO, PhysReg);
+  return setPhysReg(MI, MO, PhysReg);
 }
 
 /// Allocates a register for a VirtReg use.
-void RegAllocFast::useVirtReg(MachineInstr &MI, unsigned OpNum,
+/// \return true if MI's MachineOperands were re-arranged/invalidated.
+bool RegAllocFast::useVirtReg(MachineInstr &MI, unsigned OpNum,
                               Register VirtReg) {
   assert(VirtReg.isVirtual() && "Not a virtual register");
   if (!shouldAllocateRegister(VirtReg))
-    return;
+    return false;
   MachineOperand &MO = MI.getOperand(OpNum);
   LiveRegMap::iterator LRI;
   bool New;
   std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
   if (New) {
     MachineOperand &MO = MI.getOperand(OpNum);
     if (!MO.isKill()) {
       if (mayLiveOut(VirtReg)) {
if (MI.isCopy() && MI.getOperand(1).getSubReg() == 0) {
         assert(Hint.isPhysical() &&
                "Copy destination should already be assigned");
       }
     }
     allocVirtReg(MI, *LRI, Hint, false);
     if (LRI->Error) {
       const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
       ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
-      setPhysReg(MI, MO, *AllocationOrder.begin());
-      return;
+      return setPhysReg(MI, MO, *AllocationOrder.begin());
     }
   }
 
   LRI->LastUse = &MI;
 
   if (MI.getOpcode() == TargetOpcode::BUNDLE) {
     BundleVirtRegsMap[VirtReg] = LRI->PhysReg;
   }
   markRegUsedInInstr(LRI->PhysReg);
-  setPhysReg(MI, MO, LRI->PhysReg);
+  return setPhysReg(MI, MO, LRI->PhysReg);
 }
 
-/// Changes operand OpNum in MI the refer the PhysReg, considering subregs. This
-/// may invalidate any operand pointers.  Return true if the operand kills its
-/// register.
-void RegAllocFast::setPhysReg(MachineInstr &MI, MachineOperand &MO,
+/// Changes operand OpNum in MI the refer the PhysReg, considering subregs.
+/// \return true if MI's MachineOperands were re-arranged/invalidated.
+bool RegAllocFast::setPhysReg(MachineInstr &MI, MachineOperand &MO,
                               MCPhysReg PhysReg) {
   if (!MO.getSubReg()) {
     MO.setReg(PhysReg);
     MO.setIsRenamable(true);
-    return;
+    return false;
   }
 
   // Handle subregister index.
   MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : MCRegister());
   MO.setIsRenamable(true);
   // Note: We leave the subreg number around a little longer in case of defs.
   // This is so that the register freeing logic in allocateInstruction can still
   // recognize this as subregister defs. The code there will clear the number.
   if (!MO.isDef())
     MO.setSubReg(0);
 
   // A kill flag implies killing the full register. Add corresponding super
   // register kill.
   if (MO.isKill()) {
     MI.addRegisterKilled(PhysReg, TRI, true);
-    return;
+    // Conservatively assume implicit MOs were re-arranged
+    return true;
   }
 
   // A <def,read-undef> of a sub-register requires an implicit def of the full
   // register.
   if (MO.isDef() && MO.isUndef()) {
     if (MO.isDead())
       MI.addRegisterDead(PhysReg, TRI, true);
     else
       MI.addRegisterDefined(PhysReg, TRI);
+    // Conservatively assume implicit MOs were re-arranged
+    return true;
   }
+  return false;
 }
 
 #ifndef NDEBUG
 
 void RegAllocFast::dumpState() const {
   for (unsigned Unit = 1, UnitE = TRI->getNumRegUnits(); Unit != UnitE;
        ++Unit) {
     switch (unsigned VirtReg = RegUnitStates[Unit]) {
for (MCRegAliasIterator Alias(Reg, TRI, true); Alias.isValid(); ++Alias) {
       if (IdxRC->contains(*Alias)) {
         ++RegClassDefCounts[RCIdx];
         break;
       }
     }
   }
 }
 
+/// Compute \ref DefOperandIndexes so it contains the indices of "def" operands
+/// that are to be allocated. Those are ordered in a way that small classes,
+/// early clobbers and livethroughs are allocated first.
+void RegAllocFast::findAndSortDefOperandIndexes(const MachineInstr &MI) {
+  DefOperandIndexes.clear();
+
+  // Track number of defs which may consume a register from the class.
+  std::vector<unsigned> RegClassDefCounts(TRI->getNumRegClasses(), 0);
+  assert(RegClassDefCounts[0] == 0);
+
+  LLVM_DEBUG(dbgs() << "Need to assign livethroughs\n");
+  for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) {
+    const MachineOperand &MO = MI.getOperand(I);
+    if (!MO.isReg())
+      continue;
+    Register Reg = MO.getReg();
+    if (MO.readsReg()) {
+      if (Reg.isPhysical()) {
+        LLVM_DEBUG(dbgs() << "mark extra used: " << printReg(Reg, TRI) << '\n');
+        markPhysRegUsedInInstr(Reg);
+      }
+    }
+
+    if (MO.isDef()) {
+      if (Reg.isVirtual() && shouldAllocateRegister(Reg))
+        DefOperandIndexes.push_back(I);
+
+      addRegClassDefCounts(RegClassDefCounts, Reg);
+    }
+  }
+
+  llvm::sort(DefOperandIndexes, [&](uint16_t I0, uint16_t I1) {
+    const MachineOperand &MO0 = MI.getOperand(I0);
+    const MachineOperand &MO1 = MI.getOperand(I1);
+    Register Reg0 = MO0.getReg();
+    Register Reg1 = MO1.getReg();
+    const TargetRegisterClass &RC0 = *MRI->getRegClass(Reg0);
+    const TargetRegisterClass &RC1 = *MRI->getRegClass(Reg1);
+
+    // Identify regclass that are easy to use up completely just in this
+    // instruction.
+    unsigned ClassSize0 = RegClassInfo.getOrder(&RC0).size();
+    unsigned ClassSize1 = RegClassInfo.getOrder(&RC1).size();
+
+    bool SmallClass0 = ClassSize0 < RegClassDefCounts[RC0.getID()];
+    bool SmallClass1 = ClassSize1 < RegClassDefCounts[RC1.getID()];
+    if (SmallClass0 > SmallClass1)
+      return true;
+    if (SmallClass0 < SmallClass1)
+      return false;
+
+    // Allocate early clobbers and livethrough operands first.
+    bool Livethrough0 = MO0.isEarlyClobber() || MO0.isTied() ||
+                        (MO0.getSubReg() == 0 && !MO0.isUndef());
+    bool Livethrough1 = MO1.isEarlyClobber() || MO1.isTied() ||
+                        (MO1.getSubReg() == 0 && !MO1.isUndef());
+    if (Livethrough0 > Livethrough1)
+      return true;
+    if (Livethrough0 < Livethrough1)
+      return false;
+
+    // Tie-break rule: operand index.
+    return I0 < I1;
+  });
+}
+
 void RegAllocFast::allocateInstruction(MachineInstr &MI) {
   // The basic algorithm here is:
   // 1. Mark registers of def operands as free
   // 2. Allocate registers to use operands and place reload instructions for
   //    registers displaced by the allocation.
   //
   // However we need to handle some corner cases:
   // - pre-assigned defs and uses need to be handled before the other def/use
if (MO.isReg()) {
       HasRegMask = true;
       RegMasks.push_back(MO.getRegMask());
     }
   }
 
   // Allocate virtreg defs.
   if (HasDef) {
     if (HasVRegDef) {
+      // Note that Implicit MOs can get re-arranged by defineVirtReg(), so loop
+      // multiple times to ensure no operand is missed.
+      bool ReArrangedImplicitOps = true;
+
       // Special handling for early clobbers, tied operands or subregister defs:
       // Compared to "normal" defs these:
       // - Must not use a register that is pre-assigned for a use operand.
       // - In order to solve tricky inline assembly constraints we change the
       //   heuristic to figure out a good operand order before doing
       //   assignments.
       if (NeedToAssignLiveThroughs) {
-        DefOperandIndexes.clear();
         PhysRegUses.clear();
 
-        // Track number of defs which may consume a register from the class.
-        std::vector<unsigned> RegClassDefCounts(TRI->getNumRegClasses(), 0);
-        assert(RegClassDefCounts[0] == 0);
-
-        LLVM_DEBUG(dbgs() << "Need to assign livethroughs\n");
-        for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) {
-          const MachineOperand &MO = MI.getOperand(I);
-          if (!MO.isReg())
-            continue;
-          Register Reg = MO.getReg();
-          if (MO.readsReg()) {
-            if (Reg.isPhysical()) {
-              LLVM_DEBUG(dbgs() << "mark extra used: " << printReg(Reg, TRI)
-                                << '\n');
-              markPhysRegUsedInInstr(Reg);
-            }
-          }
-
-          if (MO.isDef()) {
-            if (Reg.isVirtual() && shouldAllocateRegister(Reg))
-              DefOperandIndexes.push_back(I);
-
-            addRegClassDefCounts(RegClassDefCounts, Reg);
-          }
-        }
-
-        llvm::sort(DefOperandIndexes, [&](uint16_t I0, uint16_t I1) {
-          const MachineOperand &MO0 = MI.getOperand(I0);
-          const MachineOperand &MO1 = MI.getOperand(I1);
-          Register Reg0 = MO0.getReg();
-          Register Reg1 = MO1.getReg();
-          const TargetRegisterClass &RC0 = *MRI->getRegClass(Reg0);
-          const TargetRegisterClass &RC1 = *MRI->getRegClass(Reg1);
-
-          // Identify regclass that are easy to use up completely just in this
-          // instruction.
-          unsigned ClassSize0 = RegClassInfo.getOrder(&RC0).size();
-          unsigned ClassSize1 = RegClassInfo.getOrder(&RC1).size();
-
-          bool SmallClass0 = ClassSize0 < RegClassDefCounts[RC0.getID()];
-          bool SmallClass1 = ClassSize1 < RegClassDefCounts[RC1.getID()];
-          if (SmallClass0 > SmallClass1)
-            return true;
-          if (SmallClass0 < SmallClass1)
-            return false;
-
-          // Allocate early clobbers and livethrough operands first.
-          bool Livethrough0 = MO0.isEarlyClobber() || MO0.isTied() ||
-                              (MO0.getSubReg() == 0 && !MO0.isUndef());
-          bool Livethrough1 = MO1.isEarlyClobber() || MO1.isTied() ||
-                              (MO1.getSubReg() == 0 && !MO1.isUndef());
-          if (Livethrough0 > Livethrough1)
-            return true;
-          if (Livethrough0 < Livethrough1)
-            return false;
-
-          // Tie-break rule: operand index.
-          return I0 < I1;
-        });
-
+        while (ReArrangedImplicitOps) {
+          ReArrangedImplicitOps = false;
+          findAndSortDefOperandIndexes(MI);
           for (uint16_t OpIdx : DefOperandIndexes) {
             MachineOperand &MO = MI.getOperand(OpIdx);
             LLVM_DEBUG(dbgs() << "Allocating " << MO << '\n');
             unsigned Reg = MO.getReg();
             if (MO.isEarlyClobber() ||
                 (MO.isTied() && !TiedOpIsUndef(MO, OpIdx)) ||
                 (MO.getSubReg() && !MO.isUndef())) {
-            defineLiveThroughVirtReg(MI, OpIdx, Reg);
+              ReArrangedImplicitOps = defineLiveThroughVirtReg(MI, OpIdx, Reg);
             } else {
-            defineVirtReg(MI, OpIdx, Reg);
+              ReArrangedImplicitOps = defineVirtReg(MI, OpIdx, Reg);
+            }
+            if (ReArrangedImplicitOps) {
+              // Implicit operands of MI were re-arranged,
+              // re-compute DefOperandIndexes.
+              break;
+            }
           }
         }
       } else {
         // Assign virtual register defs.
+        while (ReArrangedImplicitOps) {
+          ReArrangedImplicitOps = false;
           for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) {
             MachineOperand &MO = MI.getOperand(I);
             if (!MO.isReg() || !MO.isDef())
               continue;
             Register Reg = MO.getReg();
-          if (Reg.isVirtual())
-            defineVirtReg(MI, I, Reg);
+            if (Reg.isVirtual()) {
+              ReArrangedImplicitOps = defineVirtReg(MI, I, Reg);
+              if (ReArrangedImplicitOps) {
+                break;
+              }
+            }
+          }
         }
       }
     }
 
     // Free registers occupied by defs.
     // Iterate operands in reverse order, so we see the implicit super register
     // defs first (we added them earlier in case of <def,read-undef>).
     for (signed I = MI.getNumOperands() - 1; I >= 0; --I) {
for (MachineOperand &MO : MI.operands()) {
         continue;
       bool displacedAny = usePhysReg(MI, Reg);
       if (!displacedAny)
         MO.setIsKill(true);
     }
   }
 
   // Allocate virtreg uses and insert reloads as necessary.
+  // Implicit MOs can get moved/removed by useVirtReg(), so loop multiple
+  // times to ensure no operand is missed.
   bool HasUndefUse = false;
+  bool ReArrangedImplicitMOs = true;
+  while (ReArrangedImplicitMOs) {
+    ReArrangedImplicitMOs = false;
     for (unsigned I = 0; I < MI.getNumOperands(); ++I) {
       MachineOperand &MO = MI.getOperand(I);
       if (!MO.isReg() || !MO.isUse())
         continue;
       Register Reg = MO.getReg();
       if (!Reg.isVirtual() || !shouldAllocateRegister(Reg))
         continue;
 
       if (MO.isUndef()) {
         HasUndefUse = true;
         continue;
       }
 
-
       // Populate MayLiveAcrossBlocks in case the use block is allocated before
       // the def block (removing the vreg uses).
       mayLiveIn(Reg);
 
-
       assert(!MO.isInternalRead() && "Bundles not supported");
       assert(MO.readsReg() && "reading use");
-    useVirtReg(MI, I, Reg);
+      ReArrangedImplicitMOs = useVirtReg(MI, I, Reg);
+      if (ReArrangedImplicitMOs)
+        break;
+    }
   }
 
   // Allocate undef operands. This is a separate step because in a situation
   // like  ` = OP undef %X, %X`    both operands need the same register assign
   // so we should perform the normal assignment first.
   if (HasUndefUse) {
     for (MachineOperand &MO : MI.uses()) {
       if (!MO.isReg() || !MO.isUse())

llvm/test/CodeGen/ARM/regalloc-fast-rewrite-implicits.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=armv7-apple-ios -run-pass=regallocfast -o - %s | FileCheck %s
+
+
+# tBX_RET uses an implicit vreg with a sub-register. That implicit use will
+# typically be rewritten as a use of the relevant super-register. Make sure
+# regallocfast is able to process the remaining operands (here, %2) and rewrite
+# them to use physical registers.
+---
+name:            different_vreg
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $d2, $d4, $d7
+
+    ; CHECK-LABEL: name: different_vreg
+    ; CHECK: liveins: $d2, $d4, $d7
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: renamable $d5 = COPY killed $d4
+    ; CHECK-NEXT: renamable $d4 = COPY killed $d2
+    ; CHECK-NEXT: undef renamable $d0 = COPY renamable $d5, implicit-def $q0_q1
+    ; CHECK-NEXT: renamable $d1 = COPY renamable $d4
+    ; CHECK-NEXT: renamable $d2 = COPY killed renamable $d5
+    ; CHECK-NEXT: renamable $d3 = COPY killed renamable $d4
+    ; CHECK-NEXT: tBX_RET 14 /* CC::al */, $noreg, implicit killed renamable $d7, implicit killed $q0_q1
+    %0:dpr_vfp2 = COPY $d4
+    %1:dpr_vfp2 = COPY $d2
+    %2:dpr_vfp2 = COPY $d7
+    undef %4.dsub_0:dquad = COPY %0
+    %4.dsub_1:dquad = COPY %1
+    %4.dsub_2:dquad = COPY %0
+    %4.dsub_3:dquad = COPY %1
+    tBX_RET 14, $noreg, implicit %4.dsub_3, implicit %2
+...
+
+
+# tBX_RET uses the same vreg twice, make sure regallocfast is able to allocate a
+# physical register for it and replace both references.
+---
+name:            same_vreg_twice
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $d2, $d4
+
+    ; CHECK-LABEL: name: same_vreg_twice
+    ; CHECK: liveins: $d2, $d4
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: renamable $d5 = COPY killed $d4
+    ; CHECK-NEXT: renamable $d4 = COPY killed $d2
+    ; CHECK-NEXT: undef renamable $d0 = COPY renamable $d5, implicit-def $q0_q1
+    ; CHECK-NEXT: renamable $d1 = COPY renamable $d4
+    ; CHECK-NEXT: renamable $d2 = COPY killed renamable $d5
+    ; CHECK-NEXT: renamable $d3 = COPY killed renamable $d4
+    ; CHECK-NEXT: tBX_RET 14 /* CC::al */, $noreg, implicit renamable $d3, implicit killed $q0_q1
+    %0:dpr_vfp2 = COPY $d4
+    %1:dpr_vfp2 = COPY $d2
+    undef %4.dsub_0:dquad = COPY %0
+    %4.dsub_1:dquad = COPY %1
+    %4.dsub_2:dquad = COPY %0
+    %4.dsub_3:dquad = COPY %1
+    tBX_RET 14, $noreg, implicit %4.dsub_1, implicit %4.dsub_3
+...
+
+# tBL partially defines two vregs, which turn out to be dead. Make sure
+# regallocfast allocates a phys reg for both %0 and %1.
+---
+name:            partial_dead
+tracksRegLiveness: true
+body:             |
+  bb.0:
+
+    ; CHECK-LABEL: name: partial_dead
+    ; CHECK: tBL 14 /* CC::al */, $noreg, 0, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit-def $sp, implicit-def dead $q0_q1, implicit-def dead $q2_q3
+    ; CHECK-NEXT: tBX_RET 14 /* CC::al */, $noreg
+    tBL 14, $noreg, 0, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit-def $sp, implicit-def undef %0.dsub_0:dquad, implicit-def undef %1.dsub_2:dquad
+    tBX_RET 14, $noreg
+...