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 (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 continue; 144 } 145 146 if (AvailablePhysReg) 147 Matrix->assign(*VirtReg, AvailablePhysReg); 148 149 for (Register Reg : SplitVRegs) { 150 assert(LIS->hasInterval(Reg)); 151 152 LiveInterval *SplitVirtReg = &LIS->getInterval(Reg); 153 assert(!VRM->hasPhys(SplitVirtReg->reg()) && "Register already assigned"); 154 if (MRI->reg_nodbg_empty(SplitVirtReg->reg())) { 155 assert(SplitVirtReg->empty() && "Non-empty but used interval"); 156 LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); 157 aboutToRemoveInterval(*SplitVirtReg); 158 LIS->removeInterval(SplitVirtReg->reg()); 159 continue; 160 } 161 LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 162 assert(Register::isVirtualRegister(SplitVirtReg->reg()) && 163 "expect split value in virtual register"); 164 enqueue(SplitVirtReg); 165 ++NumNewQueued; 166 } 167 } 168 } 169 170 void RegAllocBase::postOptimization() { 171 spiller().postOptimization(); 172 for (auto DeadInst : DeadRemats) { 173 LIS->RemoveMachineInstrFromMaps(*DeadInst); 174 DeadInst->eraseFromParent(); 175 } 176 DeadRemats.clear(); 177 } 178 179 void RegAllocBase::enqueue(LiveInterval *LI) { 180 const Register Reg = LI->reg(); 181 182 assert(Reg.isVirtual() && "Can only enqueue virtual registers"); 183 184 if (VRM->hasPhys(Reg)) 185 return; 186 187 const TargetRegisterClass &RC = *MRI->getRegClass(Reg); 188 if (ShouldAllocateClass(*TRI, RC)) { 189 LLVM_DEBUG(dbgs() << "Enqueuing " << printReg(Reg, TRI) << '\n'); 190 enqueueImpl(LI); 191 } else { 192 LLVM_DEBUG(dbgs() << "Not enqueueing " << printReg(Reg, TRI) 193 << " in skipped register class\n"); 194 } 195 } 196