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 comon functionality 11 // for LiveIntervalUnion-based register allocators. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #define DEBUG_TYPE "regalloc" 16 #include "RegAllocBase.h" 17 #include "Spiller.h" 18 #include "llvm/ADT/Statistic.h" 19 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 20 #include "llvm/CodeGen/LiveRangeEdit.h" 21 #include "llvm/CodeGen/LiveRegMatrix.h" 22 #include "llvm/CodeGen/MachineInstr.h" 23 #include "llvm/CodeGen/MachineRegisterInfo.h" 24 #include "llvm/CodeGen/VirtRegMap.h" 25 #include "llvm/Target/TargetMachine.h" 26 #include "llvm/Target/TargetRegisterInfo.h" 27 #ifndef NDEBUG 28 #include "llvm/ADT/SparseBitVector.h" 29 #endif 30 #include "llvm/Support/CommandLine.h" 31 #include "llvm/Support/Debug.h" 32 #include "llvm/Support/ErrorHandling.h" 33 #include "llvm/Support/raw_ostream.h" 34 #include "llvm/Support/Timer.h" 35 36 using namespace llvm; 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::desc("Verify during register allocation")); 45 46 const char *RegAllocBase::TimerGroupName = "Register Allocation"; 47 bool RegAllocBase::VerifyEnabled = false; 48 49 //===----------------------------------------------------------------------===// 50 // RegAllocBase Implementation 51 //===----------------------------------------------------------------------===// 52 53 void RegAllocBase::init(VirtRegMap &vrm, 54 LiveIntervals &lis, 55 LiveRegMatrix &mat) { 56 TRI = &vrm.getTargetRegInfo(); 57 MRI = &vrm.getRegInfo(); 58 VRM = &vrm; 59 LIS = &lis; 60 Matrix = &mat; 61 MRI->freezeReservedRegs(vrm.getMachineFunction()); 62 RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); 63 } 64 65 // Visit all the live registers. If they are already assigned to a physical 66 // register, unify them with the corresponding LiveIntervalUnion, otherwise push 67 // them on the priority queue for later assignment. 68 void RegAllocBase::seedLiveRegs() { 69 NamedRegionTimer T("Seed Live Regs", TimerGroupName, TimePassesIsEnabled); 70 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 71 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 72 if (MRI->reg_nodbg_empty(Reg)) 73 continue; 74 enqueue(&LIS->getInterval(Reg)); 75 } 76 } 77 78 // Top-level driver to manage the queue of unassigned VirtRegs and call the 79 // selectOrSplit implementation. 80 void RegAllocBase::allocatePhysRegs() { 81 seedLiveRegs(); 82 83 // Continue assigning vregs one at a time to available physical registers. 84 while (LiveInterval *VirtReg = dequeue()) { 85 assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned"); 86 87 // Unused registers can appear when the spiller coalesces snippets. 88 if (MRI->reg_nodbg_empty(VirtReg->reg)) { 89 DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); 90 LIS->removeInterval(VirtReg->reg); 91 continue; 92 } 93 94 // Invalidate all interference queries, live ranges could have changed. 95 Matrix->invalidateVirtRegs(); 96 97 // selectOrSplit requests the allocator to return an available physical 98 // register if possible and populate a list of new live intervals that 99 // result from splitting. 100 DEBUG(dbgs() << "\nselectOrSplit " 101 << MRI->getRegClass(VirtReg->reg)->getName() 102 << ':' << PrintReg(VirtReg->reg) << ' ' << *VirtReg << '\n'); 103 typedef SmallVector<LiveInterval*, 4> VirtRegVec; 104 VirtRegVec SplitVRegs; 105 unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 106 107 if (AvailablePhysReg == ~0u) { 108 // selectOrSplit failed to find a register! 109 const char *Msg = "ran out of registers during register allocation"; 110 // Probably caused by an inline asm. 111 MachineInstr *MI; 112 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(VirtReg->reg); 113 (MI = I.skipInstruction());) 114 if (MI->isInlineAsm()) 115 break; 116 if (MI) 117 MI->emitError(Msg); 118 else 119 report_fatal_error(Msg); 120 // Keep going after reporting the error. 121 VRM->assignVirt2Phys(VirtReg->reg, 122 RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front()); 123 continue; 124 } 125 126 if (AvailablePhysReg) 127 Matrix->assign(*VirtReg, AvailablePhysReg); 128 129 for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); 130 I != E; ++I) { 131 LiveInterval *SplitVirtReg = *I; 132 assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned"); 133 if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) { 134 DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); 135 LIS->removeInterval(SplitVirtReg->reg); 136 continue; 137 } 138 DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 139 assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && 140 "expect split value in virtual register"); 141 enqueue(SplitVirtReg); 142 ++NumNewQueued; 143 } 144 } 145 } 146