RegAllocBase.cpp revision 234285
1284677Sdim//===-- RegAllocBase.cpp - Register Allocator Base Class ------------------===// 2284677Sdim// 3284677Sdim// The LLVM Compiler Infrastructure 4284677Sdim// 5284677Sdim// This file is distributed under the University of Illinois Open Source 6284677Sdim// License. See LICENSE.TXT for details. 7284677Sdim// 8284677Sdim//===----------------------------------------------------------------------===// 9284677Sdim// 10284677Sdim// This file defines the RegAllocBase class which provides comon functionality 11284677Sdim// for LiveIntervalUnion-based register allocators. 12284677Sdim// 13284677Sdim//===----------------------------------------------------------------------===// 14284677Sdim 15284677Sdim#define DEBUG_TYPE "regalloc" 16284677Sdim#include "RegAllocBase.h" 17284677Sdim#include "Spiller.h" 18284677Sdim#include "VirtRegMap.h" 19284677Sdim#include "llvm/ADT/Statistic.h" 20284677Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 21284677Sdim#include "llvm/CodeGen/LiveRangeEdit.h" 22284677Sdim#include "llvm/CodeGen/MachineInstr.h" 23284677Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 24284677Sdim#include "llvm/Target/TargetMachine.h" 25284677Sdim#include "llvm/Target/TargetRegisterInfo.h" 26284677Sdim#ifndef NDEBUG 27284677Sdim#include "llvm/ADT/SparseBitVector.h" 28284677Sdim#endif 29284677Sdim#include "llvm/Support/CommandLine.h" 30284677Sdim#include "llvm/Support/Debug.h" 31284677Sdim#include "llvm/Support/ErrorHandling.h" 32284677Sdim#include "llvm/Support/raw_ostream.h" 33284677Sdim#include "llvm/Support/Timer.h" 34284677Sdim 35284677Sdimusing namespace llvm; 36284677Sdim 37284677SdimSTATISTIC(NumAssigned , "Number of registers assigned"); 38284677SdimSTATISTIC(NumUnassigned , "Number of registers unassigned"); 39284677SdimSTATISTIC(NumNewQueued , "Number of new live ranges queued"); 40284677Sdim 41284677Sdim// Temporary verification option until we can put verification inside 42284677Sdim// MachineVerifier. 43284677Sdimstatic cl::opt<bool, true> 44284677SdimVerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), 45284677Sdim cl::desc("Verify during register allocation")); 46284677Sdim 47284677Sdimconst char *RegAllocBase::TimerGroupName = "Register Allocation"; 48284677Sdimbool RegAllocBase::VerifyEnabled = false; 49284677Sdim 50284677Sdim#ifndef NDEBUG 51284677Sdim// Verify each LiveIntervalUnion. 52284677Sdimvoid RegAllocBase::verify() { 53284677Sdim LiveVirtRegBitSet VisitedVRegs; 54284677Sdim OwningArrayPtr<LiveVirtRegBitSet> 55284677Sdim unionVRegs(new LiveVirtRegBitSet[PhysReg2LiveUnion.numRegs()]); 56284677Sdim 57284677Sdim // Verify disjoint unions. 58284677Sdim for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) { 59284677Sdim DEBUG(PhysReg2LiveUnion[PhysReg].print(dbgs(), TRI)); 60284677Sdim LiveVirtRegBitSet &VRegs = unionVRegs[PhysReg]; 61284677Sdim PhysReg2LiveUnion[PhysReg].verify(VRegs); 62284677Sdim // Union + intersection test could be done efficiently in one pass, but 63284677Sdim // don't add a method to SparseBitVector unless we really need it. 64284677Sdim assert(!VisitedVRegs.intersects(VRegs) && "vreg in multiple unions"); 65284677Sdim VisitedVRegs |= VRegs; 66284677Sdim } 67284677Sdim 68284677Sdim // Verify vreg coverage. 69284677Sdim for (LiveIntervals::iterator liItr = LIS->begin(), liEnd = LIS->end(); 70284677Sdim liItr != liEnd; ++liItr) { 71284677Sdim unsigned reg = liItr->first; 72284677Sdim if (TargetRegisterInfo::isPhysicalRegister(reg)) continue; 73284677Sdim if (!VRM->hasPhys(reg)) continue; // spilled? 74284677Sdim unsigned PhysReg = VRM->getPhys(reg); 75284677Sdim if (!unionVRegs[PhysReg].test(reg)) { 76284677Sdim dbgs() << "LiveVirtReg " << reg << " not in union " << 77284677Sdim TRI->getName(PhysReg) << "\n"; 78284677Sdim llvm_unreachable("unallocated live vreg"); 79284677Sdim } 80284677Sdim } 81284677Sdim // FIXME: I'm not sure how to verify spilled intervals. 82284677Sdim} 83284677Sdim#endif //!NDEBUG 84284677Sdim 85284677Sdim//===----------------------------------------------------------------------===// 86284677Sdim// RegAllocBase Implementation 87284677Sdim//===----------------------------------------------------------------------===// 88284677Sdim 89284677Sdim// Instantiate a LiveIntervalUnion for each physical register. 90284677Sdimvoid RegAllocBase::LiveUnionArray::init(LiveIntervalUnion::Allocator &allocator, 91284677Sdim unsigned NRegs) { 92284677Sdim NumRegs = NRegs; 93284677Sdim Array = 94284677Sdim static_cast<LiveIntervalUnion*>(malloc(sizeof(LiveIntervalUnion)*NRegs)); 95284677Sdim for (unsigned r = 0; r != NRegs; ++r) 96284677Sdim new(Array + r) LiveIntervalUnion(r, allocator); 97284677Sdim} 98284677Sdim 99284677Sdimvoid RegAllocBase::init(VirtRegMap &vrm, LiveIntervals &lis) { 100284677Sdim NamedRegionTimer T("Initialize", TimerGroupName, TimePassesIsEnabled); 101284677Sdim TRI = &vrm.getTargetRegInfo(); 102284677Sdim MRI = &vrm.getRegInfo(); 103284677Sdim VRM = &vrm; 104284677Sdim LIS = &lis; 105284677Sdim MRI->freezeReservedRegs(vrm.getMachineFunction()); 106284677Sdim RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); 107284677Sdim 108284677Sdim const unsigned NumRegs = TRI->getNumRegs(); 109284677Sdim if (NumRegs != PhysReg2LiveUnion.numRegs()) { 110284677Sdim PhysReg2LiveUnion.init(UnionAllocator, NumRegs); 111284677Sdim // Cache an interferece query for each physical reg 112284677Sdim Queries.reset(new LiveIntervalUnion::Query[PhysReg2LiveUnion.numRegs()]); 113284677Sdim } 114284677Sdim} 115284677Sdim 116284677Sdimvoid RegAllocBase::LiveUnionArray::clear() { 117284677Sdim if (!Array) 118284677Sdim return; 119284677Sdim for (unsigned r = 0; r != NumRegs; ++r) 120284677Sdim Array[r].~LiveIntervalUnion(); 121284677Sdim free(Array); 122284677Sdim NumRegs = 0; 123284677Sdim Array = 0; 124284677Sdim} 125284677Sdim 126284677Sdimvoid RegAllocBase::releaseMemory() { 127284677Sdim for (unsigned r = 0, e = PhysReg2LiveUnion.numRegs(); r != e; ++r) 128284677Sdim PhysReg2LiveUnion[r].clear(); 129284677Sdim} 130284677Sdim 131284677Sdim// Visit all the live registers. If they are already assigned to a physical 132284677Sdim// register, unify them with the corresponding LiveIntervalUnion, otherwise push 133284677Sdim// them on the priority queue for later assignment. 134284677Sdimvoid RegAllocBase::seedLiveRegs() { 135284677Sdim NamedRegionTimer T("Seed Live Regs", TimerGroupName, TimePassesIsEnabled); 136284677Sdim for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); I != E; ++I) { 137284677Sdim unsigned RegNum = I->first; 138284677Sdim LiveInterval &VirtReg = *I->second; 139284677Sdim if (TargetRegisterInfo::isPhysicalRegister(RegNum)) 140284677Sdim PhysReg2LiveUnion[RegNum].unify(VirtReg); 141284677Sdim else 142284677Sdim enqueue(&VirtReg); 143284677Sdim } 144284677Sdim} 145284677Sdim 146284677Sdimvoid RegAllocBase::assign(LiveInterval &VirtReg, unsigned PhysReg) { 147284677Sdim DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) 148284677Sdim << " to " << PrintReg(PhysReg, TRI) << '\n'); 149284677Sdim assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); 150284677Sdim VRM->assignVirt2Phys(VirtReg.reg, PhysReg); 151284677Sdim MRI->setPhysRegUsed(PhysReg); 152284677Sdim PhysReg2LiveUnion[PhysReg].unify(VirtReg); 153284677Sdim ++NumAssigned; 154284677Sdim} 155284677Sdim 156284677Sdimvoid RegAllocBase::unassign(LiveInterval &VirtReg, unsigned PhysReg) { 157284677Sdim DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) 158284677Sdim << " from " << PrintReg(PhysReg, TRI) << '\n'); 159284677Sdim assert(VRM->getPhys(VirtReg.reg) == PhysReg && "Inconsistent unassign"); 160284677Sdim PhysReg2LiveUnion[PhysReg].extract(VirtReg); 161284677Sdim VRM->clearVirt(VirtReg.reg); 162284677Sdim ++NumUnassigned; 163284677Sdim} 164284677Sdim 165284677Sdim// Top-level driver to manage the queue of unassigned VirtRegs and call the 166284677Sdim// selectOrSplit implementation. 167284677Sdimvoid RegAllocBase::allocatePhysRegs() { 168284677Sdim seedLiveRegs(); 169284677Sdim 170284677Sdim // Continue assigning vregs one at a time to available physical registers. 171284677Sdim while (LiveInterval *VirtReg = dequeue()) { 172284677Sdim assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned"); 173284677Sdim 174284677Sdim // Unused registers can appear when the spiller coalesces snippets. 175284677Sdim if (MRI->reg_nodbg_empty(VirtReg->reg)) { 176284677Sdim DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); 177284677Sdim LIS->removeInterval(VirtReg->reg); 178284677Sdim continue; 179284677Sdim } 180284677Sdim 181284677Sdim // Invalidate all interference queries, live ranges could have changed. 182284677Sdim invalidateVirtRegs(); 183284677Sdim 184284677Sdim // selectOrSplit requests the allocator to return an available physical 185284677Sdim // register if possible and populate a list of new live intervals that 186284677Sdim // result from splitting. 187284677Sdim DEBUG(dbgs() << "\nselectOrSplit " 188284677Sdim << MRI->getRegClass(VirtReg->reg)->getName() 189284677Sdim << ':' << *VirtReg << '\n'); 190284677Sdim typedef SmallVector<LiveInterval*, 4> VirtRegVec; 191284677Sdim VirtRegVec SplitVRegs; 192284677Sdim unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 193284677Sdim 194284677Sdim if (AvailablePhysReg == ~0u) { 195284677Sdim // selectOrSplit failed to find a register! 196284677Sdim const char *Msg = "ran out of registers during register allocation"; 197284677Sdim // Probably caused by an inline asm. 198284677Sdim MachineInstr *MI; 199284677Sdim for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(VirtReg->reg); 200284677Sdim (MI = I.skipInstruction());) 201284677Sdim if (MI->isInlineAsm()) 202284677Sdim break; 203284677Sdim if (MI) 204284677Sdim MI->emitError(Msg); 205284677Sdim else 206284677Sdim report_fatal_error(Msg); 207284677Sdim // Keep going after reporting the error. 208284677Sdim VRM->assignVirt2Phys(VirtReg->reg, 209284677Sdim RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front()); 210284677Sdim continue; 211284677Sdim } 212284677Sdim 213284677Sdim if (AvailablePhysReg) 214284677Sdim assign(*VirtReg, AvailablePhysReg); 215284677Sdim 216284677Sdim for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); 217284677Sdim I != E; ++I) { 218284677Sdim LiveInterval *SplitVirtReg = *I; 219284677Sdim assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned"); 220284677Sdim if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) { 221284677Sdim DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); 222284677Sdim LIS->removeInterval(SplitVirtReg->reg); 223284677Sdim continue; 224284677Sdim } 225284677Sdim DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 226284677Sdim assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && 227284677Sdim "expect split value in virtual register"); 228284677Sdim enqueue(SplitVirtReg); 229284677Sdim ++NumNewQueued; 230284677Sdim } 231284677Sdim } 232284677Sdim} 233284677Sdim 234284677Sdim// Check if this live virtual register interferes with a physical register. If 235284677Sdim// not, then check for interference on each register that aliases with the 236284677Sdim// physical register. Return the interfering register. 237284677Sdimunsigned RegAllocBase::checkPhysRegInterference(LiveInterval &VirtReg, 238284677Sdim unsigned PhysReg) { 239284677Sdim for (const uint16_t *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) 240284677Sdim if (query(VirtReg, *AliasI).checkInterference()) 241284677Sdim return *AliasI; 242284677Sdim return 0; 243284677Sdim} 244284677Sdim 245284677Sdim// Add newly allocated physical registers to the MBB live in sets. 246284677Sdimvoid RegAllocBase::addMBBLiveIns(MachineFunction *MF) { 247284677Sdim NamedRegionTimer T("MBB Live Ins", TimerGroupName, TimePassesIsEnabled); 248284677Sdim SlotIndexes *Indexes = LIS->getSlotIndexes(); 249284677Sdim if (MF->size() <= 1) 250284677Sdim return; 251284677Sdim 252284677Sdim LiveIntervalUnion::SegmentIter SI; 253284677Sdim for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) { 254284677Sdim LiveIntervalUnion &LiveUnion = PhysReg2LiveUnion[PhysReg]; 255284677Sdim if (LiveUnion.empty()) 256284677Sdim continue; 257284677Sdim DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " live-in:"); 258284677Sdim MachineFunction::iterator MBB = llvm::next(MF->begin()); 259284677Sdim MachineFunction::iterator MFE = MF->end(); 260284677Sdim SlotIndex Start, Stop; 261284677Sdim tie(Start, Stop) = Indexes->getMBBRange(MBB); 262284677Sdim SI.setMap(LiveUnion.getMap()); 263284677Sdim SI.find(Start); 264284677Sdim while (SI.valid()) { 265284677Sdim if (SI.start() <= Start) { 266284677Sdim if (!MBB->isLiveIn(PhysReg)) 267284677Sdim MBB->addLiveIn(PhysReg); 268284677Sdim DEBUG(dbgs() << "\tBB#" << MBB->getNumber() << ':' 269284677Sdim << PrintReg(SI.value()->reg, TRI)); 270284677Sdim } else if (SI.start() > Stop) 271284677Sdim MBB = Indexes->getMBBFromIndex(SI.start().getPrevIndex()); 272284677Sdim if (++MBB == MFE) 273284677Sdim break; 274284677Sdim tie(Start, Stop) = Indexes->getMBBRange(MBB); 275284677Sdim SI.advanceTo(Start); 276284677Sdim } 277284677Sdim DEBUG(dbgs() << '\n'); 278284677Sdim } 279284677Sdim} 280284677Sdim 281284677Sdim