1 //===- RegAllocBase.cpp - Register Allocator Base Class -------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the RegAllocBase class which provides common functionality 11 // for LiveIntervalUnion-based register allocators. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "RegAllocBase.h" 16 #include "Spiller.h" 17 #include "llvm/ADT/SmallVector.h" 18 #include "llvm/ADT/Statistic.h" 19 #include "llvm/CodeGen/LiveInterval.h" 20 #include "llvm/CodeGen/LiveIntervals.h" 21 #include "llvm/CodeGen/LiveRegMatrix.h" 22 #include "llvm/CodeGen/MachineInstr.h" 23 #include "llvm/CodeGen/MachineRegisterInfo.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, 58 LiveIntervals &lis, 59 LiveRegMatrix &mat) { 60 TRI = &vrm.getTargetRegInfo(); 61 MRI = &vrm.getRegInfo(); 62 VRM = &vrm; 63 LIS = &lis; 64 Matrix = &mat; 65 MRI->freezeReservedRegs(vrm.getMachineFunction()); 66 RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); 67 } 68 69 // Visit all the live registers. If they are already assigned to a physical 70 // register, unify them with the corresponding LiveIntervalUnion, otherwise push 71 // them on the priority queue for later assignment. 72 void RegAllocBase::seedLiveRegs() { 73 NamedRegionTimer T("seed", "Seed Live Regs", TimerGroupName, 74 TimerGroupDescription, TimePassesIsEnabled); 75 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 76 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 77 if (MRI->reg_nodbg_empty(Reg)) 78 continue; 79 enqueue(&LIS->getInterval(Reg)); 80 } 81 } 82 83 // Top-level driver to manage the queue of unassigned VirtRegs and call the 84 // selectOrSplit implementation. 85 void RegAllocBase::allocatePhysRegs() { 86 seedLiveRegs(); 87 88 // Continue assigning vregs one at a time to available physical registers. 89 while (LiveInterval *VirtReg = dequeue()) { 90 assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned"); 91 92 // Unused registers can appear when the spiller coalesces snippets. 93 if (MRI->reg_nodbg_empty(VirtReg->reg)) { 94 LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); 95 aboutToRemoveInterval(*VirtReg); 96 LIS->removeInterval(VirtReg->reg); 97 continue; 98 } 99 100 // Invalidate all interference queries, live ranges could have changed. 101 Matrix->invalidateVirtRegs(); 102 103 // selectOrSplit requests the allocator to return an available physical 104 // register if possible and populate a list of new live intervals that 105 // result from splitting. 106 LLVM_DEBUG(dbgs() << "\nselectOrSplit " 107 << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg)) 108 << ':' << *VirtReg << " w=" << VirtReg->weight << '\n'); 109 110 using VirtRegVec = SmallVector<unsigned, 4>; 111 112 VirtRegVec SplitVRegs; 113 unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 114 115 if (AvailablePhysReg == ~0u) { 116 // selectOrSplit failed to find a register! 117 // Probably caused by an inline asm. 118 MachineInstr *MI = nullptr; 119 for (MachineRegisterInfo::reg_instr_iterator 120 I = MRI->reg_instr_begin(VirtReg->reg), E = MRI->reg_instr_end(); 121 I != E; ) { 122 MachineInstr *TmpMI = &*(I++); 123 if (TmpMI->isInlineAsm()) { 124 MI = TmpMI; 125 break; 126 } 127 } 128 if (MI) 129 MI->emitError("inline assembly requires more registers than available"); 130 else 131 report_fatal_error("ran out of registers during register allocation"); 132 // Keep going after reporting the error. 133 VRM->assignVirt2Phys(VirtReg->reg, 134 RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front()); 135 continue; 136 } 137 138 if (AvailablePhysReg) 139 Matrix->assign(*VirtReg, AvailablePhysReg); 140 141 for (unsigned Reg : SplitVRegs) { 142 assert(LIS->hasInterval(Reg)); 143 144 LiveInterval *SplitVirtReg = &LIS->getInterval(Reg); 145 assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned"); 146 if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) { 147 assert(SplitVirtReg->empty() && "Non-empty but used interval"); 148 LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); 149 aboutToRemoveInterval(*SplitVirtReg); 150 LIS->removeInterval(SplitVirtReg->reg); 151 continue; 152 } 153 LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 154 assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && 155 "expect split value in virtual register"); 156 enqueue(SplitVirtReg); 157 ++NumNewQueued; 158 } 159 } 160 } 161 162 void RegAllocBase::postOptimization() { 163 spiller().postOptimization(); 164 for (auto DeadInst : DeadRemats) { 165 LIS->RemoveMachineInstrFromMaps(*DeadInst); 166 DeadInst->eraseFromParent(); 167 } 168 DeadRemats.clear(); 169 } 170