1 //===- RegAllocBase.cpp - Register Allocator Base Class -------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the RegAllocBase class which provides common functionality 10 // for LiveIntervalUnion-based register allocators. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "RegAllocBase.h" 15 #include "llvm/ADT/SmallVector.h" 16 #include "llvm/ADT/Statistic.h" 17 #include "llvm/CodeGen/LiveInterval.h" 18 #include "llvm/CodeGen/LiveIntervals.h" 19 #include "llvm/CodeGen/LiveRegMatrix.h" 20 #include "llvm/CodeGen/MachineInstr.h" 21 #include "llvm/CodeGen/MachineModuleInfo.h" 22 #include "llvm/CodeGen/MachineRegisterInfo.h" 23 #include "llvm/CodeGen/Spiller.h" 24 #include "llvm/CodeGen/TargetRegisterInfo.h" 25 #include "llvm/CodeGen/VirtRegMap.h" 26 #include "llvm/IR/DiagnosticInfo.h" 27 #include "llvm/IR/Module.h" 28 #include "llvm/Pass.h" 29 #include "llvm/Support/CommandLine.h" 30 #include "llvm/Support/Debug.h" 31 #include "llvm/Support/ErrorHandling.h" 32 #include "llvm/Support/Timer.h" 33 #include "llvm/Support/raw_ostream.h" 34 #include <cassert> 35 36 using namespace llvm; 37 38 #define DEBUG_TYPE "regalloc" 39 40 STATISTIC(NumNewQueued, "Number of new live ranges queued"); 41 42 // Temporary verification option until we can put verification inside 43 // MachineVerifier. 44 static cl::opt<bool, true> 45 VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), 46 cl::Hidden, cl::desc("Verify during register allocation")); 47 48 const char RegAllocBase::TimerGroupName[] = "regalloc"; 49 const char RegAllocBase::TimerGroupDescription[] = "Register Allocation"; 50 bool RegAllocBase::VerifyEnabled = false; 51 52 //===----------------------------------------------------------------------===// 53 // RegAllocBase Implementation 54 //===----------------------------------------------------------------------===// 55 56 // Pin the vtable to this file. 57 void RegAllocBase::anchor() {} 58 59 void RegAllocBase::init(VirtRegMap &vrm, LiveIntervals &lis, 60 LiveRegMatrix &mat) { 61 TRI = &vrm.getTargetRegInfo(); 62 MRI = &vrm.getRegInfo(); 63 VRM = &vrm; 64 LIS = &lis; 65 Matrix = &mat; 66 MRI->freezeReservedRegs(); 67 RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); 68 FailedVRegs.clear(); 69 } 70 71 // Visit all the live registers. If they are already assigned to a physical 72 // register, unify them with the corresponding LiveIntervalUnion, otherwise push 73 // them on the priority queue for later assignment. 74 void RegAllocBase::seedLiveRegs() { 75 NamedRegionTimer T("seed", "Seed Live Regs", TimerGroupName, 76 TimerGroupDescription, TimePassesIsEnabled); 77 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 78 Register Reg = Register::index2VirtReg(i); 79 if (MRI->reg_nodbg_empty(Reg)) 80 continue; 81 enqueue(&LIS->getInterval(Reg)); 82 } 83 } 84 85 // Top-level driver to manage the queue of unassigned VirtRegs and call the 86 // selectOrSplit implementation. 87 void RegAllocBase::allocatePhysRegs() { 88 seedLiveRegs(); 89 90 // Continue assigning vregs one at a time to available physical registers. 91 while (const LiveInterval *VirtReg = dequeue()) { 92 assert(!VRM->hasPhys(VirtReg->reg()) && "Register already assigned"); 93 94 // Unused registers can appear when the spiller coalesces snippets. 95 if (MRI->reg_nodbg_empty(VirtReg->reg())) { 96 LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); 97 aboutToRemoveInterval(*VirtReg); 98 LIS->removeInterval(VirtReg->reg()); 99 continue; 100 } 101 102 // Invalidate all interference queries, live ranges could have changed. 103 Matrix->invalidateVirtRegs(); 104 105 // selectOrSplit requests the allocator to return an available physical 106 // register if possible and populate a list of new live intervals that 107 // result from splitting. 108 LLVM_DEBUG(dbgs() << "\nselectOrSplit " 109 << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg())) 110 << ':' << *VirtReg << '\n'); 111 112 using VirtRegVec = SmallVector<Register, 4>; 113 114 VirtRegVec SplitVRegs; 115 MCRegister AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 116 117 if (AvailablePhysReg == ~0u) { 118 // selectOrSplit failed to find a register! 119 // Probably caused by an inline asm. 120 MachineInstr *MI = nullptr; 121 for (MachineInstr &MIR : MRI->reg_instructions(VirtReg->reg())) { 122 MI = &MIR; 123 if (MI->isInlineAsm()) 124 break; 125 } 126 127 const TargetRegisterClass *RC = MRI->getRegClass(VirtReg->reg()); 128 AvailablePhysReg = getErrorAssignment(*RC, MI); 129 130 // Keep going after reporting the error. 131 cleanupFailedVReg(VirtReg->reg(), AvailablePhysReg, SplitVRegs); 132 } else if (AvailablePhysReg) 133 Matrix->assign(*VirtReg, AvailablePhysReg); 134 135 for (Register Reg : SplitVRegs) { 136 assert(LIS->hasInterval(Reg)); 137 138 LiveInterval *SplitVirtReg = &LIS->getInterval(Reg); 139 assert(!VRM->hasPhys(SplitVirtReg->reg()) && "Register already assigned"); 140 if (MRI->reg_nodbg_empty(SplitVirtReg->reg())) { 141 assert(SplitVirtReg->empty() && "Non-empty but used interval"); 142 LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); 143 aboutToRemoveInterval(*SplitVirtReg); 144 LIS->removeInterval(SplitVirtReg->reg()); 145 continue; 146 } 147 LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 148 assert(SplitVirtReg->reg().isVirtual() && 149 "expect split value in virtual register"); 150 enqueue(SplitVirtReg); 151 ++NumNewQueued; 152 } 153 } 154 } 155 156 void RegAllocBase::postOptimization() { 157 spiller().postOptimization(); 158 for (auto *DeadInst : DeadRemats) { 159 LIS->RemoveMachineInstrFromMaps(*DeadInst); 160 DeadInst->eraseFromParent(); 161 } 162 DeadRemats.clear(); 163 } 164 165 void RegAllocBase::cleanupFailedVReg(Register FailedReg, MCRegister PhysReg, 166 SmallVectorImpl<Register> &SplitRegs) { 167 // We still should produce valid IR. Kill all the uses and reduce the live 168 // ranges so that we don't think it's possible to introduce kill flags later 169 // which will fail the verifier. 170 for (MachineOperand &MO : MRI->reg_operands(FailedReg)) { 171 if (MO.readsReg()) 172 MO.setIsUndef(true); 173 } 174 175 if (!MRI->isReserved(PhysReg)) { 176 // Physical liveness for any aliasing registers is now unreliable, so delete 177 // the uses. 178 for (MCRegAliasIterator Aliases(PhysReg, TRI, true); Aliases.isValid(); 179 ++Aliases) { 180 for (MachineOperand &MO : MRI->reg_operands(*Aliases)) { 181 if (MO.readsReg()) { 182 MO.setIsUndef(true); 183 LIS->removeAllRegUnitsForPhysReg(MO.getReg()); 184 } 185 } 186 } 187 } 188 189 // Directly perform the rewrite, and do not leave it to VirtRegRewriter as 190 // usual. This avoids trying to manage illegal overlapping assignments in 191 // LiveRegMatrix. 192 MRI->replaceRegWith(FailedReg, PhysReg); 193 LIS->removeInterval(FailedReg); 194 } 195 196 void RegAllocBase::enqueue(const LiveInterval *LI) { 197 const Register Reg = LI->reg(); 198 199 assert(Reg.isVirtual() && "Can only enqueue virtual registers"); 200 201 if (VRM->hasPhys(Reg)) 202 return; 203 204 if (shouldAllocateRegister(Reg)) { 205 LLVM_DEBUG(dbgs() << "Enqueuing " << printReg(Reg, TRI) << '\n'); 206 enqueueImpl(LI); 207 } else { 208 LLVM_DEBUG(dbgs() << "Not enqueueing " << printReg(Reg, TRI) 209 << " in skipped register class\n"); 210 } 211 } 212 213 MCPhysReg RegAllocBase::getErrorAssignment(const TargetRegisterClass &RC, 214 const MachineInstr *CtxMI) { 215 MachineFunction &MF = VRM->getMachineFunction(); 216 217 // Avoid printing the error for every single instance of the register. It 218 // would be better if this were per register class. 219 bool EmitError = !MF.getProperties().hasFailedRegAlloc(); 220 if (EmitError) 221 MF.getProperties().setFailedRegAlloc(); 222 223 const Function &Fn = MF.getFunction(); 224 LLVMContext &Context = Fn.getContext(); 225 226 ArrayRef<MCPhysReg> AllocOrder = RegClassInfo.getOrder(&RC); 227 if (AllocOrder.empty()) { 228 // If the allocation order is empty, it likely means all registers in the 229 // class are reserved. We still to need to pick something, so look at the 230 // underlying class. 231 ArrayRef<MCPhysReg> RawRegs = RC.getRegisters(); 232 233 if (EmitError) { 234 Context.diagnose(DiagnosticInfoRegAllocFailure( 235 "no registers from class available to allocate", Fn, 236 CtxMI ? CtxMI->getDebugLoc() : DiagnosticLocation())); 237 } 238 239 assert(!RawRegs.empty() && "register classes cannot have no registers"); 240 return RawRegs.front(); 241 } 242 243 if (EmitError) { 244 if (CtxMI && CtxMI->isInlineAsm()) { 245 CtxMI->emitInlineAsmError( 246 "inline assembly requires more registers than available"); 247 } else { 248 Context.diagnose(DiagnosticInfoRegAllocFailure( 249 "ran out of registers during register allocation", Fn, 250 CtxMI ? CtxMI->getDebugLoc() : DiagnosticLocation())); 251 } 252 } 253 254 return AllocOrder.front(); 255 } 256