RegAlloc: Do not fatal error if there are no registers in the alloc order (#119640)

Try to use DiagnosticInfo if every register in the class is reserved
by forcing assignment to a reserved register. Also reduces the number
of redundant errors emitted, particularly with fast.

This is still broken in the case of undef uses. There are additional
complications in greedy and fast, so leave it for a separate fix.

10 files changed, 139 insertions, 68 deletions

diff --git a/llvm/include/llvm/CodeGen/MachineFunction.h b/llvm/include/llvm/CodeGen/MachineFunction.h
index 547cc26..d696add 100644
--- a/llvm/include/llvm/CodeGen/MachineFunction.h
+++ b/llvm/include/llvm/CodeGen/MachineFunction.h
@@ -186,6 +186,7 @@ public:
     Selected,
     TiedOpsRewritten,
     FailsVerification,
+    FailedRegAlloc,
     TracksDebugUserValues,
     LastProperty = TracksDebugUserValues,
   };
diff --git a/llvm/lib/CodeGen/MachineFunction.cpp b/llvm/lib/CodeGen/MachineFunction.cpp
index a293a77..e6b9538f 100644
--- a/llvm/lib/CodeGen/MachineFunction.cpp
+++ b/llvm/lib/CodeGen/MachineFunction.cpp
@@ -102,6 +102,7 @@ static const char *getPropertyName(MachineFunctionProperties::Property Prop) {
   case P::TracksLiveness: return "TracksLiveness";
   case P::TiedOpsRewritten: return "TiedOpsRewritten";
   case P::FailsVerification: return "FailsVerification";
+  case P::FailedRegAlloc: return "FailedRegAlloc";
   case P::TracksDebugUserValues: return "TracksDebugUserValues";
   }
   // clang-format on
diff --git a/llvm/lib/CodeGen/RegAllocBase.cpp b/llvm/lib/CodeGen/RegAllocBase.cpp
index 6300f6b..980a675 100644
--- a/llvm/lib/CodeGen/RegAllocBase.cpp
+++ b/llvm/lib/CodeGen/RegAllocBase.cpp
@@ -124,25 +124,10 @@ void RegAllocBase::allocatePhysRegs() {
       }
 
       const TargetRegisterClass *RC = MRI->getRegClass(VirtReg->reg());
-      ArrayRef<MCPhysReg> AllocOrder = RegClassInfo.getOrder(RC);
-      if (AllocOrder.empty()) {
-        report_fatal_error("no registers from class available to allocate");
-      } else {
-        if (MI && MI->isInlineAsm()) {
-          MI->emitInlineAsmError(
-              "inline assembly requires more registers than available");
-        } else {
-          const Function &Fn = VRM->getMachineFunction().getFunction();
-          LLVMContext &Context = Fn.getContext();
-          DiagnosticInfoRegAllocFailure DI(
-              "ran out of registers during register allocation", Fn,
-              MI ? MI->getDebugLoc() : DiagnosticLocation());
-          Context.diagnose(DI);
-        }
-      }
+      AvailablePhysReg = getErrorAssignment(*RC, MI);
 
       // Keep going after reporting the error.
-      VRM->assignVirt2Phys(VirtReg->reg(), AllocOrder.front());
+      VRM->assignVirt2Phys(VirtReg->reg(), AvailablePhysReg);
     } else if (AvailablePhysReg)
       Matrix->assign(*VirtReg, AvailablePhysReg);
 
@@ -192,3 +177,50 @@ void RegAllocBase::enqueue(const LiveInterval *LI) {
                       << " in skipped register class\n");
   }
 }
+
+MCPhysReg RegAllocBase::getErrorAssignment(const TargetRegisterClass &RC,
+                                           const MachineInstr *CtxMI) {
+  MachineFunction &MF = VRM->getMachineFunction();
+
+  // Avoid printing the error for every single instance of the register. It
+  // would be better if this were per register class.
+  bool EmitError = !MF.getProperties().hasProperty(
+      MachineFunctionProperties::Property::FailedRegAlloc);
+  if (EmitError)
+    MF.getProperties().set(MachineFunctionProperties::Property::FailedRegAlloc);
+
+  const Function &Fn = MF.getFunction();
+  LLVMContext &Context = Fn.getContext();
+
+  ArrayRef<MCPhysReg> AllocOrder = RegClassInfo.getOrder(&RC);
+  if (AllocOrder.empty()) {
+    // If the allocation order is empty, it likely means all registers in the
+    // class are reserved. We still to need to pick something, so look at the
+    // underlying class.
+    ArrayRef<MCPhysReg> RawRegs = RC.getRegisters();
+
+    if (EmitError) {
+      DiagnosticInfoRegAllocFailure DI(
+          "no registers from class available to allocate", Fn,
+          CtxMI ? CtxMI->getDebugLoc() : DiagnosticLocation());
+      Context.diagnose(DI);
+    }
+
+    assert(!RawRegs.empty() && "register classes cannot have no registers");
+    return RawRegs.front();
+  }
+
+  if (EmitError) {
+    if (CtxMI && CtxMI->isInlineAsm()) {
+      CtxMI->emitInlineAsmError(
+          "inline assembly requires more registers than available");
+    } else {
+      DiagnosticInfoRegAllocFailure DI(
+          "ran out of registers during register allocation", Fn,
+          CtxMI ? CtxMI->getDebugLoc() : DiagnosticLocation());
+      Context.diagnose(DI);
+    }
+  }
+
+  return AllocOrder.front();
+}
diff --git a/llvm/lib/CodeGen/RegAllocBase.h b/llvm/lib/CodeGen/RegAllocBase.h
index a1ede08..5bd52da 100644
--- a/llvm/lib/CodeGen/RegAllocBase.h
+++ b/llvm/lib/CodeGen/RegAllocBase.h
@@ -123,6 +123,12 @@ protected:
   virtual MCRegister selectOrSplit(const LiveInterval &VirtReg,
                                    SmallVectorImpl<Register> &splitLVRs) = 0;
 
+  /// Query a physical register to use as a filler in contexts where the
+  /// allocation has failed. This will raise an error, but not abort the
+  /// compilation.
+  MCPhysReg getErrorAssignment(const TargetRegisterClass &RC,
+                               const MachineInstr *CtxMI = nullptr);
+
   // Use this group name for NamedRegionTimer.
   static const char TimerGroupName[];
   static const char TimerGroupDescription[];
diff --git a/llvm/lib/CodeGen/RegAllocFast.cpp b/llvm/lib/CodeGen/RegAllocFast.cpp
index 65a27d5..8323a05 100644
--- a/llvm/lib/CodeGen/RegAllocFast.cpp
+++ b/llvm/lib/CodeGen/RegAllocFast.cpp
@@ -368,6 +368,9 @@ private:
                      bool LookAtPhysRegUses = false);
   bool useVirtReg(MachineInstr &MI, MachineOperand &MO, Register VirtReg);
 
+  MCPhysReg getErrorAssignment(const LiveReg &LR, MachineInstr &MI,
+                               const TargetRegisterClass &RC);
+
   MachineBasicBlock::iterator
   getMBBBeginInsertionPoint(MachineBasicBlock &MBB,
                             SmallSet<Register, 2> &PrologLiveIns) const;
@@ -963,22 +966,8 @@ void RegAllocFastImpl::allocVirtReg(MachineInstr &MI, LiveReg &LR,
   if (!BestReg) {
     // Nothing we can do: Report an error and keep going with an invalid
     // allocation.
-    if (MI.isInlineAsm()) {
-      MI.emitInlineAsmError(
-          "inline assembly requires more registers than available");
-    } else {
-      const Function &Fn = MBB->getParent()->getFunction();
-      DiagnosticInfoRegAllocFailure DI(
-          "ran out of registers during register allocation", Fn,
-          MI.getDebugLoc());
-      Fn.getContext().diagnose(DI);
-    }
-
+    LR.PhysReg = getErrorAssignment(LR, MI, RC);
     LR.Error = true;
-    if (!AllocationOrder.empty())
-      LR.PhysReg = AllocationOrder.front();
-    else
-      LR.PhysReg = 0;
     return;
   }
 
@@ -1000,6 +989,7 @@ void RegAllocFastImpl::allocVirtRegUndef(MachineOperand &MO) {
   } else {
     const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
     ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
+    // FIXME: This can happen, and should fall back to a reserved entry in RC.
     assert(!AllocationOrder.empty() && "Allocation order must not be empty");
     PhysReg = AllocationOrder[0];
   }
@@ -1074,15 +1064,6 @@ bool RegAllocFastImpl::defineVirtReg(MachineInstr &MI, unsigned OpNum,
   }
   if (LRI->PhysReg == 0) {
     allocVirtReg(MI, *LRI, 0, LookAtPhysRegUses);
-    // If no physical register is available for LRI, we assign one at random
-    // and bail out of this function immediately.
-    if (LRI->Error) {
-      const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
-      ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
-      if (AllocationOrder.empty())
-        return setPhysReg(MI, MO, MCRegister::NoRegister);
-      return setPhysReg(MI, MO, *AllocationOrder.begin());
-    }
   } else {
     assert((!isRegUsedInInstr(LRI->PhysReg, LookAtPhysRegUses) || LRI->Error) &&
            "TODO: preassign mismatch");
@@ -1167,13 +1148,6 @@ bool RegAllocFastImpl::useVirtReg(MachineInstr &MI, MachineOperand &MO,
       }
     }
     allocVirtReg(MI, *LRI, Hint, false);
-    if (LRI->Error) {
-      const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
-      ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
-      if (AllocationOrder.empty())
-        return setPhysReg(MI, MO, MCRegister::NoRegister);
-      return setPhysReg(MI, MO, *AllocationOrder.begin());
-    }
   }
 
   LRI->LastUse = &MI;
@@ -1185,6 +1159,56 @@ bool RegAllocFastImpl::useVirtReg(MachineInstr &MI, MachineOperand &MO,
   return setPhysReg(MI, MO, LRI->PhysReg);
 }
 
+/// Query a physical register to use as a filler in contexts where the
+/// allocation has failed. This will raise an error, but not abort the
+/// compilation.
+MCPhysReg RegAllocFastImpl::getErrorAssignment(const LiveReg &LR,
+                                               MachineInstr &MI,
+                                               const TargetRegisterClass &RC) {
+  MachineFunction &MF = *MI.getMF();
+
+  // Avoid repeating the error every time a register is used.
+  bool EmitError = !MF.getProperties().hasProperty(
+      MachineFunctionProperties::Property::FailedRegAlloc);
+  if (EmitError)
+    MF.getProperties().set(MachineFunctionProperties::Property::FailedRegAlloc);
+
+  // If the allocation order was empty, all registers in the class were
+  // probably reserved. Fall back to taking the first register in the class,
+  // even if it's reserved.
+  ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
+  if (AllocationOrder.empty()) {
+    const Function &Fn = MF.getFunction();
+    if (EmitError) {
+      DiagnosticInfoRegAllocFailure DI(
+          "no registers from class available to allocate", Fn,
+          MI.getDebugLoc());
+      Fn.getContext().diagnose(DI);
+    }
+
+    ArrayRef<MCPhysReg> RawRegs = RC.getRegisters();
+    assert(!RawRegs.empty() && "register classes cannot have no registers");
+    return RawRegs.front();
+  }
+
+  if (!LR.Error && EmitError) {
+    // Nothing we can do: Report an error and keep going with an invalid
+    // allocation.
+    if (MI.isInlineAsm()) {
+      MI.emitInlineAsmError(
+          "inline assembly requires more registers than available");
+    } else {
+      const Function &Fn = MBB->getParent()->getFunction();
+      DiagnosticInfoRegAllocFailure DI(
+          "ran out of registers during register allocation", Fn,
+          MI.getDebugLoc());
+      Fn.getContext().diagnose(DI);
+    }
+  }
+
+  return AllocationOrder.front();
+}
+
 /// Changes operand OpNum in MI the refer the PhysReg, considering subregs.
 /// \return true if MI's MachineOperands were re-arranged/invalidated.
 bool RegAllocFastImpl::setPhysReg(MachineInstr &MI, MachineOperand &MO,
diff --git a/llvm/lib/CodeGen/VirtRegMap.cpp b/llvm/lib/CodeGen/VirtRegMap.cpp
index b28c746..d3f87f0 100644
--- a/llvm/lib/CodeGen/VirtRegMap.cpp
+++ b/llvm/lib/CodeGen/VirtRegMap.cpp
@@ -88,7 +88,9 @@ void VirtRegMap::assignVirt2Phys(Register virtReg, MCPhysReg physReg) {
   assert(!Virt2PhysMap[virtReg] &&
          "attempt to assign physical register to already mapped "
          "virtual register");
-  assert(!getRegInfo().isReserved(physReg) &&
+  assert((!getRegInfo().isReserved(physReg) ||
+          MF->getProperties().hasProperty(
+              MachineFunctionProperties::Property::FailedRegAlloc)) &&
          "Attempt to map virtReg to a reserved physReg");
   Virt2PhysMap[virtReg] = physReg;
 }
@@ -615,7 +617,10 @@ void VirtRegRewriter::rewrite() {
         assert(Register(PhysReg).isPhysical());
 
         RewriteRegs.insert(PhysReg);
-        assert(!MRI->isReserved(PhysReg) && "Reserved register assignment");
+        assert((!MRI->isReserved(PhysReg) ||
+                MF->getProperties().hasProperty(
+                    MachineFunctionProperties::Property::FailedRegAlloc)) &&
+               "Reserved register assignment");
 
         // Preserve semantics of sub-register operands.
         unsigned SubReg = MO.getSubReg();
diff --git a/llvm/test/CodeGen/AMDGPU/alloc-all-regs-reserved-in-class.mir b/llvm/test/CodeGen/AMDGPU/alloc-all-regs-reserved-in-class.mir
index f1308a1..d40fb7b 100644
--- a/llvm/test/CodeGen/AMDGPU/alloc-all-regs-reserved-in-class.mir
+++ b/llvm/test/CodeGen/AMDGPU/alloc-all-regs-reserved-in-class.mir
@@ -1,12 +1,10 @@
-# RUN: not --crash llc -mtriple=amdgcn-amd-amdhsa -mcpu=gfx900 -run-pass=greedy -verify-machineinstrs -o /dev/null %s 2>&1 | FileCheck %s
+# RUN: not llc -mtriple=amdgcn-amd-amdhsa -mcpu=gfx900 -run-pass=greedy -verify-machineinstrs -filetype=null %s 2>&1 | FileCheck --implicit-check-not=error %s
 
 # Check that there isn't an assert if we try to allocate a virtual register from
 # a class where all registers are reserved. All AGPRs are reserved on subtargets
 # that do not have them.
 
-# CHECK-NOT: ran out of registers during register allocation
-# CHECK: LLVM ERROR: no registers from class available to allocate
-# CHECK-NOT: ran out of registers during register allocation
+# CHECK: error: <unknown>:0:0: no registers from class available to allocate in function 'use_agpr'
 
 ---
 name: use_agpr
diff --git a/llvm/test/CodeGen/AMDGPU/ran-out-of-registers-error-all-regs-reserved.ll b/llvm/test/CodeGen/AMDGPU/ran-out-of-registers-error-all-regs-reserved.ll
index 3e3e201..0597592 100644
--- a/llvm/test/CodeGen/AMDGPU/ran-out-of-registers-error-all-regs-reserved.ll
+++ b/llvm/test/CodeGen/AMDGPU/ran-out-of-registers-error-all-regs-reserved.ll
@@ -1,17 +1,29 @@
-; RUN: not --crash llc -mtriple=amdgcn-amd-amdhsa -mcpu=gfx908 -vgpr-regalloc=greedy -filetype=null %s 2>&1 | FileCheck %s
-; RUN: not --crash llc -mtriple=amdgcn-amd-amdhsa -mcpu=gfx908 -vgpr-regalloc=basic -filetype=null %s 2>&1 | FileCheck %s
+; RUN: not llc -mtriple=amdgcn-amd-amdhsa -mcpu=gfx908 -vgpr-regalloc=greedy -verify-machineinstrs=0 -filetype=null %s 2>&1 | FileCheck -implicit-check-not=error %s
+; RUN: not llc -mtriple=amdgcn-amd-amdhsa -mcpu=gfx908 -vgpr-regalloc=basic -verify-machineinstrs=0 -filetype=null %s 2>&1 | FileCheck -implicit-check-not=error %s
+; RUN: not llc -mtriple=amdgcn-amd-amdhsa -mcpu=gfx908 -vgpr-regalloc=fast -verify-machineinstrs=0 -filetype=null %s 2>&1 | FileCheck -implicit-check-not=error %s
 
-; TODO: Check regalloc fast when it doesn't assert after failing.
-
-; CHECK: LLVM ERROR: no registers from class available to allocate
+; FIXME: Should pass verifier after failure.
 
 declare <32 x i32> @llvm.amdgcn.mfma.i32.32x32x4i8(i32, i32, <32 x i32>, i32 immarg, i32 immarg, i32 immarg)
 
+; CHECK: error: <unknown>:0:0: no registers from class available to allocate in function 'no_registers_from_class_available_to_allocate'
 define <32 x i32> @no_registers_from_class_available_to_allocate(<32 x i32> %arg) #0 {
   %ret = call <32 x i32> @llvm.amdgcn.mfma.i32.32x32x4i8(i32 1, i32 2, <32 x i32> %arg, i32 1, i32 2, i32 3)
   ret <32 x i32> %ret
 }
 
+; CHECK: error: <unknown>:0:0: no registers from class available to allocate in function 'no_registers_from_class_available_to_allocate_asm_use'
+define void @no_registers_from_class_available_to_allocate_asm_use(<32 x i32> %arg) #0 {
+  call void asm sideeffect "; use $0", "v"(<32 x i32> %arg)
+  ret void
+}
+
+; CHECK: error: <unknown>:0:0: no registers from class available to allocate in function 'no_registers_from_class_available_to_allocate_asm_def'
+define <32 x i32> @no_registers_from_class_available_to_allocate_asm_def() #0 {
+  %ret = call <32 x i32> asm sideeffect "; def $0", "=v"()
+  ret <32 x i32> %ret
+}
+
 ; FIXME: Special case in fast RA, asserts. Also asserts in greedy
 ; define void @no_registers_from_class_available_to_allocate_undef_asm() #0 {
 ;   call void asm sideeffect "; use $0", "v"(<32 x i32> poison)
diff --git a/llvm/test/CodeGen/AMDGPU/ran-out-of-registers-errors.ll b/llvm/test/CodeGen/AMDGPU/ran-out-of-registers-errors.ll
index 3d150fe..bd1752d 100644
--- a/llvm/test/CodeGen/AMDGPU/ran-out-of-registers-errors.ll
+++ b/llvm/test/CodeGen/AMDGPU/ran-out-of-registers-errors.ll
@@ -12,16 +12,12 @@
 
 
 ; CHECK: error: <unknown>:0:0: ran out of registers during register allocation in function 'ran_out_of_registers_general'
-; BASIC: error: <unknown>:0:0: ran out of registers during register allocation in function 'ran_out_of_registers_general'
-; FAST: error: <unknown>:0:0: ran out of registers during register allocation in function 'ran_out_of_registers_general'
 
 ; DBGINFO-GREEDY: error: {{.*}}:3:1: ran out of registers during register allocation in function 'ran_out_of_registers_general'
 
 ; DBGINFO-BASIC: error: {{.*}}:1:1: ran out of registers during register allocation in function 'ran_out_of_registers_general'
-; DBGINFO-BASIC: error: {{.*}}:3:1: ran out of registers during register allocation in function 'ran_out_of_registers_general'
 
 ; DBGINFO-FAST: error: {{.*}}:3:1: ran out of registers during register allocation in function 'ran_out_of_registers_general'
-; DBGINFO-FAST: error: {{.*}}:1:0: ran out of registers during register allocation in function 'ran_out_of_registers_general'
 define i32 @ran_out_of_registers_general(ptr addrspace(1) %ptr) #0 {
   %ld0 = load volatile i32, ptr addrspace(1) %ptr
   %ld1 = load volatile i32, ptr addrspace(1) %ptr
@@ -49,14 +45,11 @@ define void @ran_out_of_registers_asm_use() #0 {
 ; BASIC: error: inline assembly requires more registers than available at line 23
 
 ; FAST: error: <unknown>:0:0: ran out of registers during register allocation in function '@0'
-; FAST: error: <unknown>:0:0: ran out of registers during register allocation in function '@0'
-
 
 ; DBGINFO-GREEDY: error: inline assembly requires more registers than available at line 23
 ; DBGINFO-BASIC: error: inline assembly requires more registers than available at line 23
 
 ; DBGINFO-FAST: error: {{.*}}:12:1: ran out of registers during register allocation in function '@0'
-; DBGINFO-FAST: error: {{.*}}:9:0: ran out of registers during register allocation in function '@0'
 define i32 @0(ptr addrspace(1) %ptr) #0 {
   %asm = call { i32, i32 } asm sideeffect "; def $0 $1 use $2", "=v,=v,v"(ptr addrspace(1) %ptr), !srcloc !0
   %elt0 = extractvalue { i32, i32 } %asm, 0
diff --git a/llvm/test/CodeGen/AMDGPU/regalloc-illegal-eviction-assert.ll b/llvm/test/CodeGen/AMDGPU/regalloc-illegal-eviction-assert.ll
index 1b6e885..45ca0d4 100644
--- a/llvm/test/CodeGen/AMDGPU/regalloc-illegal-eviction-assert.ll
+++ b/llvm/test/CodeGen/AMDGPU/regalloc-illegal-eviction-assert.ll
@@ -1,11 +1,10 @@
-; RUN: not llc -mtriple=amdgcn -mcpu=gfx908 -verify-machineinstrs -o - %s 2>%t.err | FileCheck %s
+; RUN: not llc -mtriple=amdgcn -mcpu=gfx908 -verify-machineinstrs -o - %s 2>%t.err | FileCheck -implicit-check-not=error %s
 ; RUN: FileCheck -check-prefix=ERR %s < %t.err
 
 ; This testcase would fail on an "illegal eviction". If the assert was
 ; relaxed to allow equivalent cascade numbers, it would infinite loop.
 
 ; ERR: error: inline assembly requires more registers than available
-; ERR: error: inline assembly requires more registers than available
 
 %asm.output = type { <16 x i32>, <8 x i32>, <5 x i32>, <4 x i32>, <16 x i32> }