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 "VirtRegMap.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 21 #include "llvm/CodeGen/LiveRangeEdit.h" 22 #include "llvm/CodeGen/MachineInstr.h" 23 #include "llvm/CodeGen/MachineRegisterInfo.h" 24 #include "llvm/Target/TargetMachine.h" 25 #include "llvm/Target/TargetRegisterInfo.h" 26 #ifndef NDEBUG 27 #include "llvm/ADT/SparseBitVector.h" 28 #endif 29 #include "llvm/Support/CommandLine.h" 30 #include "llvm/Support/Debug.h" 31 #include "llvm/Support/ErrorHandling.h" 32 #include "llvm/Support/raw_ostream.h" 33 #include "llvm/Support/Timer.h" 34 35 using namespace llvm; 36 37 STATISTIC(NumAssigned , "Number of registers assigned"); 38 STATISTIC(NumUnassigned , "Number of registers unassigned"); 39 STATISTIC(NumNewQueued , "Number of new live ranges queued"); 40 41 // Temporary verification option until we can put verification inside 42 // MachineVerifier. 43 static cl::opt<bool, true> 44 VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), 45 cl::desc("Verify during register allocation")); 46 47 const char *RegAllocBase::TimerGroupName = "Register Allocation"; 48 bool RegAllocBase::VerifyEnabled = false; 49 50 #ifndef NDEBUG 51 // Verify each LiveIntervalUnion. 52 void RegAllocBase::verify() { 53 LiveVirtRegBitSet VisitedVRegs; 54 OwningArrayPtr<LiveVirtRegBitSet> 55 unionVRegs(new LiveVirtRegBitSet[PhysReg2LiveUnion.numRegs()]); 56 57 // Verify disjoint unions. 58 for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) { 59 DEBUG(PhysReg2LiveUnion[PhysReg].print(dbgs(), TRI)); 60 LiveVirtRegBitSet &VRegs = unionVRegs[PhysReg]; 61 PhysReg2LiveUnion[PhysReg].verify(VRegs); 62 // Union + intersection test could be done efficiently in one pass, but 63 // don't add a method to SparseBitVector unless we really need it. 64 assert(!VisitedVRegs.intersects(VRegs) && "vreg in multiple unions"); 65 VisitedVRegs |= VRegs; 66 } 67 68 // Verify vreg coverage. 69 for (LiveIntervals::iterator liItr = LIS->begin(), liEnd = LIS->end(); 70 liItr != liEnd; ++liItr) { 71 unsigned reg = liItr->first; 72 if (TargetRegisterInfo::isPhysicalRegister(reg)) continue; 73 if (!VRM->hasPhys(reg)) continue; // spilled? 74 unsigned PhysReg = VRM->getPhys(reg); 75 if (!unionVRegs[PhysReg].test(reg)) { 76 dbgs() << "LiveVirtReg " << reg << " not in union " << 77 TRI->getName(PhysReg) << "\n"; 78 llvm_unreachable("unallocated live vreg"); 79 } 80 } 81 // FIXME: I'm not sure how to verify spilled intervals. 82 } 83 #endif //!NDEBUG 84 85 //===----------------------------------------------------------------------===// 86 // RegAllocBase Implementation 87 //===----------------------------------------------------------------------===// 88 89 // Instantiate a LiveIntervalUnion for each physical register. 90 void RegAllocBase::LiveUnionArray::init(LiveIntervalUnion::Allocator &allocator, 91 unsigned NRegs) { 92 NumRegs = NRegs; 93 Array = 94 static_cast<LiveIntervalUnion*>(malloc(sizeof(LiveIntervalUnion)*NRegs)); 95 for (unsigned r = 0; r != NRegs; ++r) 96 new(Array + r) LiveIntervalUnion(r, allocator); 97 } 98 99 void RegAllocBase::init(VirtRegMap &vrm, LiveIntervals &lis) { 100 NamedRegionTimer T("Initialize", TimerGroupName, TimePassesIsEnabled); 101 TRI = &vrm.getTargetRegInfo(); 102 MRI = &vrm.getRegInfo(); 103 VRM = &vrm; 104 LIS = &lis; 105 MRI->freezeReservedRegs(vrm.getMachineFunction()); 106 RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); 107 108 const unsigned NumRegs = TRI->getNumRegs(); 109 if (NumRegs != PhysReg2LiveUnion.numRegs()) { 110 PhysReg2LiveUnion.init(UnionAllocator, NumRegs); 111 // Cache an interferece query for each physical reg 112 Queries.reset(new LiveIntervalUnion::Query[PhysReg2LiveUnion.numRegs()]); 113 } 114 } 115 116 void RegAllocBase::LiveUnionArray::clear() { 117 if (!Array) 118 return; 119 for (unsigned r = 0; r != NumRegs; ++r) 120 Array[r].~LiveIntervalUnion(); 121 free(Array); 122 NumRegs = 0; 123 Array = 0; 124 } 125 126 void RegAllocBase::releaseMemory() { 127 for (unsigned r = 0, e = PhysReg2LiveUnion.numRegs(); r != e; ++r) 128 PhysReg2LiveUnion[r].clear(); 129 } 130 131 // Visit all the live registers. If they are already assigned to a physical 132 // register, unify them with the corresponding LiveIntervalUnion, otherwise push 133 // them on the priority queue for later assignment. 134 void RegAllocBase::seedLiveRegs() { 135 NamedRegionTimer T("Seed Live Regs", TimerGroupName, TimePassesIsEnabled); 136 for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); I != E; ++I) { 137 unsigned RegNum = I->first; 138 LiveInterval &VirtReg = *I->second; 139 if (TargetRegisterInfo::isPhysicalRegister(RegNum)) 140 PhysReg2LiveUnion[RegNum].unify(VirtReg); 141 else 142 enqueue(&VirtReg); 143 } 144 } 145 146 void RegAllocBase::assign(LiveInterval &VirtReg, unsigned PhysReg) { 147 DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) 148 << " to " << PrintReg(PhysReg, TRI) << '\n'); 149 assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); 150 VRM->assignVirt2Phys(VirtReg.reg, PhysReg); 151 MRI->setPhysRegUsed(PhysReg); 152 PhysReg2LiveUnion[PhysReg].unify(VirtReg); 153 ++NumAssigned; 154 } 155 156 void RegAllocBase::unassign(LiveInterval &VirtReg, unsigned PhysReg) { 157 DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) 158 << " from " << PrintReg(PhysReg, TRI) << '\n'); 159 assert(VRM->getPhys(VirtReg.reg) == PhysReg && "Inconsistent unassign"); 160 PhysReg2LiveUnion[PhysReg].extract(VirtReg); 161 VRM->clearVirt(VirtReg.reg); 162 ++NumUnassigned; 163 } 164 165 // Top-level driver to manage the queue of unassigned VirtRegs and call the 166 // selectOrSplit implementation. 167 void RegAllocBase::allocatePhysRegs() { 168 seedLiveRegs(); 169 170 // Continue assigning vregs one at a time to available physical registers. 171 while (LiveInterval *VirtReg = dequeue()) { 172 assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned"); 173 174 // Unused registers can appear when the spiller coalesces snippets. 175 if (MRI->reg_nodbg_empty(VirtReg->reg)) { 176 DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); 177 LIS->removeInterval(VirtReg->reg); 178 continue; 179 } 180 181 // Invalidate all interference queries, live ranges could have changed. 182 invalidateVirtRegs(); 183 184 // selectOrSplit requests the allocator to return an available physical 185 // register if possible and populate a list of new live intervals that 186 // result from splitting. 187 DEBUG(dbgs() << "\nselectOrSplit " 188 << MRI->getRegClass(VirtReg->reg)->getName() 189 << ':' << *VirtReg << '\n'); 190 typedef SmallVector<LiveInterval*, 4> VirtRegVec; 191 VirtRegVec SplitVRegs; 192 unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 193 194 if (AvailablePhysReg == ~0u) { 195 // selectOrSplit failed to find a register! 196 const char *Msg = "ran out of registers during register allocation"; 197 // Probably caused by an inline asm. 198 MachineInstr *MI; 199 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(VirtReg->reg); 200 (MI = I.skipInstruction());) 201 if (MI->isInlineAsm()) 202 break; 203 if (MI) 204 MI->emitError(Msg); 205 else 206 report_fatal_error(Msg); 207 // Keep going after reporting the error. 208 VRM->assignVirt2Phys(VirtReg->reg, 209 RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front()); 210 continue; 211 } 212 213 if (AvailablePhysReg) 214 assign(*VirtReg, AvailablePhysReg); 215 216 for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); 217 I != E; ++I) { 218 LiveInterval *SplitVirtReg = *I; 219 assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned"); 220 if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) { 221 DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); 222 LIS->removeInterval(SplitVirtReg->reg); 223 continue; 224 } 225 DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 226 assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && 227 "expect split value in virtual register"); 228 enqueue(SplitVirtReg); 229 ++NumNewQueued; 230 } 231 } 232 } 233 234 // Check if this live virtual register interferes with a physical register. If 235 // not, then check for interference on each register that aliases with the 236 // physical register. Return the interfering register. 237 unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &VirtReg, 238 unsigned PhysReg) { 239 for (const uint16_t *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) 240 if (query(VirtReg, *AliasI).checkInterference()) 241 return *AliasI; 242 return 0; 243 } 244 245 // Add newly allocated physical registers to the MBB live in sets. 246 void RegAllocBase::addMBBLiveIns(MachineFunction *MF) { 247 NamedRegionTimer T("MBB Live Ins", TimerGroupName, TimePassesIsEnabled); 248 SlotIndexes *Indexes = LIS->getSlotIndexes(); 249 if (MF->size() <= 1) 250 return; 251 252 LiveIntervalUnion::SegmentIter SI; 253 for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) { 254 LiveIntervalUnion &LiveUnion = PhysReg2LiveUnion[PhysReg]; 255 if (LiveUnion.empty()) 256 continue; 257 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " live-in:"); 258 MachineFunction::iterator MBB = llvm::next(MF->begin()); 259 MachineFunction::iterator MFE = MF->end(); 260 SlotIndex Start, Stop; 261 tie(Start, Stop) = Indexes->getMBBRange(MBB); 262 SI.setMap(LiveUnion.getMap()); 263 SI.find(Start); 264 while (SI.valid()) { 265 if (SI.start() <= Start) { 266 if (!MBB->isLiveIn(PhysReg)) 267 MBB->addLiveIn(PhysReg); 268 DEBUG(dbgs() << "\tBB#" << MBB->getNumber() << ':' 269 << PrintReg(SI.value()->reg, TRI)); 270 } else if (SI.start() > Stop) 271 MBB = Indexes->getMBBFromIndex(SI.start().getPrevIndex()); 272 if (++MBB == MFE) 273 break; 274 tie(Start, Stop) = Indexes->getMBBRange(MBB); 275 SI.advanceTo(Start); 276 } 277 DEBUG(dbgs() << '\n'); 278 } 279 } 280 281