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