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