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 } 69 70 // Visit all the live registers. If they are already assigned to a physical 71 // register, unify them with the corresponding LiveIntervalUnion, otherwise push 72 // them on the priority queue for later assignment. 73 void RegAllocBase::seedLiveRegs() { 74 NamedRegionTimer T("seed", "Seed Live Regs", TimerGroupName, 75 TimerGroupDescription, TimePassesIsEnabled); 76 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 77 Register Reg = Register::index2VirtReg(i); 78 if (MRI->reg_nodbg_empty(Reg)) 79 continue; 80 enqueue(&LIS->getInterval(Reg)); 81 } 82 } 83 84 // Top-level driver to manage the queue of unassigned VirtRegs and call the 85 // selectOrSplit implementation. 86 void RegAllocBase::allocatePhysRegs() { 87 seedLiveRegs(); 88 89 // Continue assigning vregs one at a time to available physical registers. 90 while (const LiveInterval *VirtReg = dequeue()) { 91 assert(!VRM->hasPhys(VirtReg->reg()) && "Register already assigned"); 92 93 // Unused registers can appear when the spiller coalesces snippets. 94 if (MRI->reg_nodbg_empty(VirtReg->reg())) { 95 LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); 96 aboutToRemoveInterval(*VirtReg); 97 LIS->removeInterval(VirtReg->reg()); 98 continue; 99 } 100 101 // Invalidate all interference queries, live ranges could have changed. 102 Matrix->invalidateVirtRegs(); 103 104 // selectOrSplit requests the allocator to return an available physical 105 // register if possible and populate a list of new live intervals that 106 // result from splitting. 107 LLVM_DEBUG(dbgs() << "\nselectOrSplit " 108 << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg())) 109 << ':' << *VirtReg << '\n'); 110 111 using VirtRegVec = SmallVector<Register, 4>; 112 113 VirtRegVec SplitVRegs; 114 MCRegister AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 115 116 if (AvailablePhysReg == ~0u) { 117 // selectOrSplit failed to find a register! 118 // Probably caused by an inline asm. 119 MachineInstr *MI = nullptr; 120 for (MachineInstr &MIR : MRI->reg_instructions(VirtReg->reg())) { 121 MI = &MIR; 122 if (MI->isInlineAsm()) 123 break; 124 } 125 126 const TargetRegisterClass *RC = MRI->getRegClass(VirtReg->reg()); 127 AvailablePhysReg = getErrorAssignment(*RC, MI); 128 129 // Keep going after reporting the error. 130 VRM->assignVirt2Phys(VirtReg->reg(), AvailablePhysReg); 131 } else if (AvailablePhysReg) 132 Matrix->assign(*VirtReg, AvailablePhysReg); 133 134 for (Register Reg : SplitVRegs) { 135 assert(LIS->hasInterval(Reg)); 136 137 LiveInterval *SplitVirtReg = &LIS->getInterval(Reg); 138 assert(!VRM->hasPhys(SplitVirtReg->reg()) && "Register already assigned"); 139 if (MRI->reg_nodbg_empty(SplitVirtReg->reg())) { 140 assert(SplitVirtReg->empty() && "Non-empty but used interval"); 141 LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); 142 aboutToRemoveInterval(*SplitVirtReg); 143 LIS->removeInterval(SplitVirtReg->reg()); 144 continue; 145 } 146 LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 147 assert(SplitVirtReg->reg().isVirtual() && 148 "expect split value in virtual register"); 149 enqueue(SplitVirtReg); 150 ++NumNewQueued; 151 } 152 } 153 } 154 155 void RegAllocBase::postOptimization() { 156 spiller().postOptimization(); 157 for (auto *DeadInst : DeadRemats) { 158 LIS->RemoveMachineInstrFromMaps(*DeadInst); 159 DeadInst->eraseFromParent(); 160 } 161 DeadRemats.clear(); 162 } 163 164 void RegAllocBase::enqueue(const LiveInterval *LI) { 165 const Register Reg = LI->reg(); 166 167 assert(Reg.isVirtual() && "Can only enqueue virtual registers"); 168 169 if (VRM->hasPhys(Reg)) 170 return; 171 172 if (shouldAllocateRegister(Reg)) { 173 LLVM_DEBUG(dbgs() << "Enqueuing " << printReg(Reg, TRI) << '\n'); 174 enqueueImpl(LI); 175 } else { 176 LLVM_DEBUG(dbgs() << "Not enqueueing " << printReg(Reg, TRI) 177 << " in skipped register class\n"); 178 } 179 } 180 181 MCPhysReg RegAllocBase::getErrorAssignment(const TargetRegisterClass &RC, 182 const MachineInstr *CtxMI) { 183 MachineFunction &MF = VRM->getMachineFunction(); 184 185 // Avoid printing the error for every single instance of the register. It 186 // would be better if this were per register class. 187 bool EmitError = !MF.getProperties().hasProperty( 188 MachineFunctionProperties::Property::FailedRegAlloc); 189 if (EmitError) 190 MF.getProperties().set(MachineFunctionProperties::Property::FailedRegAlloc); 191 192 const Function &Fn = MF.getFunction(); 193 LLVMContext &Context = Fn.getContext(); 194 195 ArrayRef<MCPhysReg> AllocOrder = RegClassInfo.getOrder(&RC); 196 if (AllocOrder.empty()) { 197 // If the allocation order is empty, it likely means all registers in the 198 // class are reserved. We still to need to pick something, so look at the 199 // underlying class. 200 ArrayRef<MCPhysReg> RawRegs = RC.getRegisters(); 201 202 if (EmitError) { 203 Context.diagnose(DiagnosticInfoRegAllocFailure( 204 "no registers from class available to allocate", Fn, 205 CtxMI ? CtxMI->getDebugLoc() : DiagnosticLocation())); 206 } 207 208 assert(!RawRegs.empty() && "register classes cannot have no registers"); 209 return RawRegs.front(); 210 } 211 212 if (EmitError) { 213 if (CtxMI && CtxMI->isInlineAsm()) { 214 CtxMI->emitInlineAsmError( 215 "inline assembly requires more registers than available"); 216 } else { 217 Context.diagnose(DiagnosticInfoRegAllocFailure( 218 "ran out of registers during register allocation", Fn, 219 CtxMI ? CtxMI->getDebugLoc() : DiagnosticLocation())); 220 } 221 } 222 223 return AllocOrder.front(); 224 } 225