Index: lib/CodeGen/RegAllocFast.cpp
===================================================================
--- lib/CodeGen/RegAllocFast.cpp
+++ lib/CodeGen/RegAllocFast.cpp
@@ -226,6 +226,7 @@
                 MCPhysReg PhysReg);
 
     bool mayLiveOut(unsigned VirtReg);
+    bool mayLiveIn(unsigned VirtReg);
 
     void dumpState();
   };
@@ -270,8 +271,10 @@
 
   // If this block loops back to itself, it would be necessary to check whether
   // the use comes after the def.
-  if (MBB->isSuccessor(MBB))
+  if (MBB->isSuccessor(MBB)) {
+    MayLiveAcrossBlocks.set(TargetRegisterInfo::virtReg2Index(VirtReg));
     return true;
+  }
 
   // See if the first \p Limit uses of the register are all in the current
   // block.
@@ -288,6 +291,24 @@
   return false;
 }
 
+/// Returns false if \p VirtReg is known to not be live into the current block.
+bool RegAllocFast::mayLiveIn(unsigned VirtReg) {
+  if (MayLiveAcrossBlocks.test(TargetRegisterInfo::virtReg2Index(VirtReg)))
+    return true;
+
+  // See if the first \p Limit def of the register are all in the current block.
+  static const unsigned Limit = 8;
+  unsigned C = 0;
+  for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) {
+    if (DefInst.getParent() != MBB || ++C >= Limit) {
+      MayLiveAcrossBlocks.set(TargetRegisterInfo::virtReg2Index(VirtReg));
+      return true;
+    }
+  }
+
+  return false;
+}
+
 /// Insert spill instruction for \p AssignedReg before \p Before. Update
 /// DBG_VALUEs with \p VirtReg operands with the stack slot.
 void RegAllocFast::spill(MachineBasicBlock::iterator Before, unsigned VirtReg,
@@ -1083,6 +1104,11 @@
         // There is no need to allocate a register for an undef use.
         continue;
       }
+
+      // Populate MayLiveAcrossBlocks in case the use block is allocated before
+      // the def block (removing the vreg uses).
+      mayLiveIn(Reg);
+
       LiveReg &LR = reloadVirtReg(MI, I, Reg, CopyDstReg);
       MCPhysReg PhysReg = LR.PhysReg;
       CopySrcReg = (CopySrcReg == Reg || CopySrcReg == PhysReg) ? PhysReg : 0;
Index: test/CodeGen/X86/bug41973.ll
===================================================================
--- /dev/null
+++ test/CodeGen/X86/bug41973.ll
@@ -0,0 +1,45 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=x86_64-grtev4-linux-gnu -O0 -regalloc=fast < %s | FileCheck %s
+
+; A spill live out of bb5 was missing because the use instruction in
+; bb3 was allocated earlier, removing the virtual register use that
+; mayLiveOut was looking for.
+
+define i32 @main(i32 %arg, i8* %arg1) {
+; CHECK-LABEL: main:
+; CHECK:       # %bb.0: # %bb
+; CHECK-NEXT:    movq %rsi, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill
+; CHECK-NEXT:    jmp .LBB0_3
+; CHECK-NEXT:  .LBB0_1: # %bb2
+; CHECK-NEXT:  .LBB0_2: # %bb3
+; CHECK-NEXT:    # in Loop: Header=BB0_3 Depth=1
+; CHECK-NEXT:    movq {{[-0-9]+}}(%r{{[sb]}}p), %rax # 8-byte Reload
+; CHECK-NEXT:    xorl %ecx, %ecx
+; CHECK-NEXT:    movl %ecx, %edx
+; CHECK-NEXT:    movq $0, (%rax)
+; CHECK-NEXT:    movq %rdx, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill
+; CHECK-NEXT:  .LBB0_3: # %bb5
+; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    movq {{[-0-9]+}}(%r{{[sb]}}p), %rax # 8-byte Reload
+; CHECK-NEXT:    xorl %ecx, %ecx
+; CHECK-NEXT:    movl %ecx, %edx
+; CHECK-NEXT:    movq %rdx, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill
+; CHECK-NEXT:    jmpq *%rax
+bb:
+  %tmp = alloca i32, align 4
+  br label %bb5
+
+bb2:                                              ; preds = %bb5
+  unreachable
+
+bb3:                                              ; preds = %bb5
+  %tmp4 = phi i64* [ null, %bb5 ]
+  store volatile i64 0, i64* %tmp4
+  br label %bb5
+
+bb5:                                              ; preds = %bb3, %bb
+  %tmp6 = phi i64* [ null, %bb3 ], [ inttoptr (i64 123 to i64*), %bb ]
+  %tmp7 = phi i8* [ %arg1, %bb ], [ null, %bb3 ]
+  indirectbr i8* %tmp7, [label %bb3, label %bb2]
+}
+