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/Pass.h" 27 #include "llvm/Support/CommandLine.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/ErrorHandling.h" 30 #include "llvm/Support/Timer.h" 31 #include "llvm/Support/raw_ostream.h" 32 #include <cassert> 33 34 using namespace llvm; 35 36 #define DEBUG_TYPE "regalloc" 37 38 STATISTIC(NumNewQueued, "Number of new live ranges queued"); 39 40 // Temporary verification option until we can put verification inside 41 // MachineVerifier. 42 static cl::opt<bool, true> 43 VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), 44 cl::Hidden, cl::desc("Verify during register allocation")); 45 46 const char RegAllocBase::TimerGroupName[] = "regalloc"; 47 const char RegAllocBase::TimerGroupDescription[] = "Register Allocation"; 48 bool RegAllocBase::VerifyEnabled = false; 49 50 //===----------------------------------------------------------------------===// 51 // RegAllocBase Implementation 52 //===----------------------------------------------------------------------===// 53 54 // Pin the vtable to this file. 55 void RegAllocBase::anchor() {} 56 57 void RegAllocBase::init(VirtRegMap &vrm, LiveIntervals &lis, 58 LiveRegMatrix &mat) { 59 TRI = &vrm.getTargetRegInfo(); 60 MRI = &vrm.getRegInfo(); 61 VRM = &vrm; 62 LIS = &lis; 63 Matrix = &mat; 64 MRI->freezeReservedRegs(vrm.getMachineFunction()); 65 RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); 66 } 67 68 // Visit all the live registers. If they are already assigned to a physical 69 // register, unify them with the corresponding LiveIntervalUnion, otherwise push 70 // them on the priority queue for later assignment. 71 void RegAllocBase::seedLiveRegs() { 72 NamedRegionTimer T("seed", "Seed Live Regs", TimerGroupName, 73 TimerGroupDescription, TimePassesIsEnabled); 74 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 75 Register Reg = Register::index2VirtReg(i); 76 if (MRI->reg_nodbg_empty(Reg)) 77 continue; 78 enqueue(&LIS->getInterval(Reg)); 79 } 80 } 81 82 // Top-level driver to manage the queue of unassigned VirtRegs and call the 83 // selectOrSplit implementation. 84 void RegAllocBase::allocatePhysRegs() { 85 seedLiveRegs(); 86 87 // Continue assigning vregs one at a time to available physical registers. 88 while (const LiveInterval *VirtReg = dequeue()) { 89 assert(!VRM->hasPhys(VirtReg->reg()) && "Register already assigned"); 90 91 // Unused registers can appear when the spiller coalesces snippets. 92 if (MRI->reg_nodbg_empty(VirtReg->reg())) { 93 LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); 94 aboutToRemoveInterval(*VirtReg); 95 LIS->removeInterval(VirtReg->reg()); 96 continue; 97 } 98 99 // Invalidate all interference queries, live ranges could have changed. 100 Matrix->invalidateVirtRegs(); 101 102 // selectOrSplit requests the allocator to return an available physical 103 // register if possible and populate a list of new live intervals that 104 // result from splitting. 105 LLVM_DEBUG(dbgs() << "\nselectOrSplit " 106 << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg())) 107 << ':' << *VirtReg << " w=" << VirtReg->weight() << '\n'); 108 109 using VirtRegVec = SmallVector<Register, 4>; 110 111 VirtRegVec SplitVRegs; 112 MCRegister AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 113 114 if (AvailablePhysReg == ~0u) { 115 // selectOrSplit failed to find a register! 116 // Probably caused by an inline asm. 117 MachineInstr *MI = nullptr; 118 for (MachineRegisterInfo::reg_instr_iterator 119 I = MRI->reg_instr_begin(VirtReg->reg()), 120 E = MRI->reg_instr_end(); 121 I != E;) { 122 MI = &*(I++); 123 if (MI->isInlineAsm()) 124 break; 125 } 126 127 const TargetRegisterClass *RC = MRI->getRegClass(VirtReg->reg()); 128 ArrayRef<MCPhysReg> AllocOrder = RegClassInfo.getOrder(RC); 129 if (AllocOrder.empty()) 130 report_fatal_error("no registers from class available to allocate"); 131 else if (MI && MI->isInlineAsm()) { 132 MI->emitError("inline assembly requires more registers than available"); 133 } else if (MI) { 134 LLVMContext &Context = 135 MI->getParent()->getParent()->getMMI().getModule()->getContext(); 136 Context.emitError("ran out of registers during register allocation"); 137 } else { 138 report_fatal_error("ran out of registers during register allocation"); 139 } 140 141 // Keep going after reporting the error. 142 VRM->assignVirt2Phys(VirtReg->reg(), AllocOrder.front()); 143 } else if (AvailablePhysReg) 144 Matrix->assign(*VirtReg, AvailablePhysReg); 145 146 for (Register Reg : SplitVRegs) { 147 assert(LIS->hasInterval(Reg)); 148 149 LiveInterval *SplitVirtReg = &LIS->getInterval(Reg); 150 assert(!VRM->hasPhys(SplitVirtReg->reg()) && "Register already assigned"); 151 if (MRI->reg_nodbg_empty(SplitVirtReg->reg())) { 152 assert(SplitVirtReg->empty() && "Non-empty but used interval"); 153 LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); 154 aboutToRemoveInterval(*SplitVirtReg); 155 LIS->removeInterval(SplitVirtReg->reg()); 156 continue; 157 } 158 LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 159 assert(SplitVirtReg->reg().isVirtual() && 160 "expect split value in virtual register"); 161 enqueue(SplitVirtReg); 162 ++NumNewQueued; 163 } 164 } 165 } 166 167 void RegAllocBase::postOptimization() { 168 spiller().postOptimization(); 169 for (auto *DeadInst : DeadRemats) { 170 LIS->RemoveMachineInstrFromMaps(*DeadInst); 171 DeadInst->eraseFromParent(); 172 } 173 DeadRemats.clear(); 174 } 175 176 void RegAllocBase::enqueue(const LiveInterval *LI) { 177 const Register Reg = LI->reg(); 178 179 assert(Reg.isVirtual() && "Can only enqueue virtual registers"); 180 181 if (VRM->hasPhys(Reg)) 182 return; 183 184 const TargetRegisterClass &RC = *MRI->getRegClass(Reg); 185 if (ShouldAllocateClass(*TRI, RC)) { 186 LLVM_DEBUG(dbgs() << "Enqueuing " << printReg(Reg, TRI) << '\n'); 187 enqueueImpl(LI); 188 } else { 189 LLVM_DEBUG(dbgs() << "Not enqueueing " << printReg(Reg, TRI) 190 << " in skipped register class\n"); 191 } 192 } 193