X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocBasic.cpp;h=5496d69fd3df1aa381faee2de9cdb4a3b9911100;hb=cccfd194ecf8e1c6fb203ec3f96aca8cfe9e0484;hp=f01ebf5030e07f8971df5eb5560a01fc32976bfe;hpb=16999da951677a94a2f30d98c8126ff175f457e1;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp index f01ebf5030e..5496d69fd3d 100644 --- a/lib/CodeGen/RegAllocBasic.cpp +++ b/lib/CodeGen/RegAllocBasic.cpp @@ -13,13 +13,15 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "regalloc" -#include "LiveIntervalUnion.h" #include "RegAllocBase.h" +#include "LiveDebugVariables.h" +#include "LiveIntervalUnion.h" +#include "LiveRangeEdit.h" #include "RenderMachineFunction.h" #include "Spiller.h" #include "VirtRegMap.h" -#include "VirtRegRewriter.h" #include "llvm/ADT/OwningPtr.h" +#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Function.h" #include "llvm/PassAnalysisSupport.h" @@ -32,7 +34,6 @@ #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/RegAllocRegistry.h" -#include "llvm/CodeGen/RegisterCoalescer.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetOptions.h" #include "llvm/Target/TargetRegisterInfo.h" @@ -45,19 +46,33 @@ #include "llvm/Support/Timer.h" #include +#include using namespace llvm; +STATISTIC(NumAssigned , "Number of registers assigned"); +STATISTIC(NumUnassigned , "Number of registers unassigned"); +STATISTIC(NumNewQueued , "Number of new live ranges queued"); + static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator", createBasicRegisterAllocator); // Temporary verification option until we can put verification inside // MachineVerifier. -static cl::opt -VerifyRegAlloc("verify-regalloc", - cl::desc("Verify live intervals before renaming")); +static cl::opt +VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), + cl::desc("Verify during register allocation")); const char *RegAllocBase::TimerGroupName = "Register Allocation"; +bool RegAllocBase::VerifyEnabled = false; + +namespace { + struct CompSpillWeight { + bool operator()(LiveInterval *A, LiveInterval *B) const { + return A->weight < B->weight; + } + }; +} namespace { /// RABasic provides a minimal implementation of the basic register allocation @@ -69,7 +84,6 @@ class RABasic : public MachineFunctionPass, public RegAllocBase { // context MachineFunction *MF; - BitVector ReservedRegs; // analyses LiveStacks *LS; @@ -77,7 +91,8 @@ class RABasic : public MachineFunctionPass, public RegAllocBase // state std::auto_ptr SpillerInstance; - + std::priority_queue, + CompSpillWeight> Queue; public: RABasic(); @@ -95,6 +110,18 @@ public: virtual float getPriority(LiveInterval *LI) { return LI->weight; } + virtual void enqueue(LiveInterval *LI) { + Queue.push(LI); + } + + virtual LiveInterval *dequeue() { + if (Queue.empty()) + return 0; + LiveInterval *LI = Queue.top(); + Queue.pop(); + return LI; + } + virtual unsigned selectOrSplit(LiveInterval &VirtReg, SmallVectorImpl &SplitVRegs); @@ -109,10 +136,11 @@ char RABasic::ID = 0; } // end anonymous namespace RABasic::RABasic(): MachineFunctionPass(ID) { + initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); - initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry()); + initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); initializeLiveStacksPass(*PassRegistry::getPassRegistry()); initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); @@ -127,9 +155,11 @@ void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved(); AU.addRequired(); AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); if (StrongPHIElim) AU.addRequiredID(StrongPHIEliminationID); - AU.addRequiredTransitive(); + AU.addRequiredTransitiveID(RegisterCoalescerPassID); AU.addRequired(); AU.addRequired(); AU.addPreserved(); @@ -203,9 +233,14 @@ void RegAllocBase::init(VirtRegMap &vrm, LiveIntervals &lis) { MRI = &vrm.getRegInfo(); VRM = &vrm; LIS = &lis; - PhysReg2LiveUnion.init(UnionAllocator, TRI->getNumRegs()); - // Cache an interferece query for each physical reg - Queries.reset(new LiveIntervalUnion::Query[PhysReg2LiveUnion.numRegs()]); + RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); + + const unsigned NumRegs = TRI->getNumRegs(); + if (NumRegs != PhysReg2LiveUnion.numRegs()) { + PhysReg2LiveUnion.init(UnionAllocator, NumRegs); + // Cache an interferece query for each physical reg + Queries.reset(new LiveIntervalUnion::Query[PhysReg2LiveUnion.numRegs()]); + } } void RegAllocBase::LiveUnionArray::clear() { @@ -219,63 +254,109 @@ void RegAllocBase::LiveUnionArray::clear() { } void RegAllocBase::releaseMemory() { - PhysReg2LiveUnion.clear(); + for (unsigned r = 0, e = PhysReg2LiveUnion.numRegs(); r != e; ++r) + PhysReg2LiveUnion[r].clear(); } -// Visit all the live virtual registers. If they are already assigned to a -// physical register, unify them with the corresponding LiveIntervalUnion, -// otherwise push them on the priority queue for later assignment. -void RegAllocBase:: -seedLiveVirtRegs(std::priority_queue > &VirtRegQ) { +// Visit all the live registers. If they are already assigned to a physical +// register, unify them with the corresponding LiveIntervalUnion, otherwise push +// them on the priority queue for later assignment. +void RegAllocBase::seedLiveRegs() { + NamedRegionTimer T("Seed Live Regs", TimerGroupName, TimePassesIsEnabled); for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); I != E; ++I) { unsigned RegNum = I->first; LiveInterval &VirtReg = *I->second; if (TargetRegisterInfo::isPhysicalRegister(RegNum)) PhysReg2LiveUnion[RegNum].unify(VirtReg); else - VirtRegQ.push(std::make_pair(getPriority(&VirtReg), RegNum)); + enqueue(&VirtReg); } } +void RegAllocBase::assign(LiveInterval &VirtReg, unsigned PhysReg) { + DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) + << " to " << PrintReg(PhysReg, TRI) << '\n'); + assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); + VRM->assignVirt2Phys(VirtReg.reg, PhysReg); + MRI->setPhysRegUsed(PhysReg); + PhysReg2LiveUnion[PhysReg].unify(VirtReg); + ++NumAssigned; +} + +void RegAllocBase::unassign(LiveInterval &VirtReg, unsigned PhysReg) { + DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) + << " from " << PrintReg(PhysReg, TRI) << '\n'); + assert(VRM->getPhys(VirtReg.reg) == PhysReg && "Inconsistent unassign"); + PhysReg2LiveUnion[PhysReg].extract(VirtReg); + VRM->clearVirt(VirtReg.reg); + ++NumUnassigned; +} + // Top-level driver to manage the queue of unassigned VirtRegs and call the // selectOrSplit implementation. void RegAllocBase::allocatePhysRegs() { - - // Push each vreg onto a queue or "precolor" by adding it to a physreg union. - std::priority_queue > VirtRegQ; - seedLiveVirtRegs(VirtRegQ); + seedLiveRegs(); // Continue assigning vregs one at a time to available physical registers. - while (!VirtRegQ.empty()) { - // Pop the highest priority vreg. - LiveInterval &VirtReg = LIS->getInterval(VirtRegQ.top().second); - VirtRegQ.pop(); + while (LiveInterval *VirtReg = dequeue()) { + assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned"); + + // Unused registers can appear when the spiller coalesces snippets. + if (MRI->reg_nodbg_empty(VirtReg->reg)) { + DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); + LIS->removeInterval(VirtReg->reg); + continue; + } + + // Invalidate all interference queries, live ranges could have changed. + invalidateVirtRegs(); // selectOrSplit requests the allocator to return an available physical // register if possible and populate a list of new live intervals that // result from splitting. - DEBUG(dbgs() << "\nselectOrSplit " << MRI->getRegClass(VirtReg.reg)->getName() - << ':' << VirtReg << '\n'); + DEBUG(dbgs() << "\nselectOrSplit " + << MRI->getRegClass(VirtReg->reg)->getName() + << ':' << *VirtReg << '\n'); typedef SmallVector VirtRegVec; VirtRegVec SplitVRegs; - unsigned AvailablePhysReg = selectOrSplit(VirtReg, SplitVRegs); - - if (AvailablePhysReg) { - DEBUG(dbgs() << "allocating: " << TRI->getName(AvailablePhysReg) - << " for " << VirtReg << '\n'); - assert(!VRM->hasPhys(VirtReg.reg) && "duplicate vreg in union"); - VRM->assignVirt2Phys(VirtReg.reg, AvailablePhysReg); - PhysReg2LiveUnion[AvailablePhysReg].unify(VirtReg); + unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); + + if (AvailablePhysReg == ~0u) { + // selectOrSplit failed to find a register! + const char *Msg = "ran out of registers during register allocation"; + // Probably caused by an inline asm. + MachineInstr *MI; + for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(VirtReg->reg); + (MI = I.skipInstruction());) + if (MI->isInlineAsm()) + break; + if (MI) + MI->emitError(Msg); + else + report_fatal_error(Msg); + // Keep going after reporting the error. + VRM->assignVirt2Phys(VirtReg->reg, + RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front()); + continue; } + + if (AvailablePhysReg) + assign(*VirtReg, AvailablePhysReg); + for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); I != E; ++I) { - LiveInterval* SplitVirtReg = *I; - if (SplitVirtReg->empty()) continue; + LiveInterval *SplitVirtReg = *I; + assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned"); + if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) { + DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); + LIS->removeInterval(SplitVirtReg->reg); + continue; + } DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && "expect split value in virtual register"); - VirtRegQ.push(std::make_pair(getPriority(SplitVirtReg), - SplitVirtReg->reg)); + enqueue(SplitVirtReg); + ++NumNewQueued; } } } @@ -307,13 +388,11 @@ void RegAllocBase::spillReg(LiveInterval& VirtReg, unsigned PhysReg, // Deallocate the interfering vreg by removing it from the union. // A LiveInterval instance may not be in a union during modification! - PhysReg2LiveUnion[PhysReg].extract(SpilledVReg); - - // Clear the vreg assignment. - VRM->clearVirt(SpilledVReg.reg); + unassign(SpilledVReg, PhysReg); // Spill the extracted interval. - spiller().spill(&SpilledVReg, SplitVRegs, PendingSpills); + LiveRangeEdit LRE(SpilledVReg, SplitVRegs, 0, &PendingSpills); + spiller().spill(LRE); } // After extracting segments, the query's results are invalid. But keep the // contents valid until we're done accessing pendingSpills. @@ -350,30 +429,36 @@ RegAllocBase::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, // Add newly allocated physical registers to the MBB live in sets. void RegAllocBase::addMBBLiveIns(MachineFunction *MF) { NamedRegionTimer T("MBB Live Ins", TimerGroupName, TimePassesIsEnabled); - typedef SmallVector MBBVec; - MBBVec liveInMBBs; - MachineBasicBlock &entryMBB = *MF->begin(); + SlotIndexes *Indexes = LIS->getSlotIndexes(); + if (MF->size() <= 1) + return; + LiveIntervalUnion::SegmentIter SI; for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) { LiveIntervalUnion &LiveUnion = PhysReg2LiveUnion[PhysReg]; if (LiveUnion.empty()) continue; - for (LiveIntervalUnion::SegmentIter SI = LiveUnion.begin(); SI.valid(); - ++SI) { - - // Find the set of basic blocks which this range is live into... - liveInMBBs.clear(); - if (!LIS->findLiveInMBBs(SI.start(), SI.stop(), liveInMBBs)) continue; - - // And add the physreg for this interval to their live-in sets. - for (MBBVec::iterator I = liveInMBBs.begin(), E = liveInMBBs.end(); - I != E; ++I) { - MachineBasicBlock *MBB = *I; - if (MBB == &entryMBB) continue; - if (MBB->isLiveIn(PhysReg)) continue; - MBB->addLiveIn(PhysReg); - } + DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " live-in:"); + MachineFunction::iterator MBB = llvm::next(MF->begin()); + MachineFunction::iterator MFE = MF->end(); + SlotIndex Start, Stop; + tie(Start, Stop) = Indexes->getMBBRange(MBB); + SI.setMap(LiveUnion.getMap()); + SI.find(Start); + while (SI.valid()) { + if (SI.start() <= Start) { + if (!MBB->isLiveIn(PhysReg)) + MBB->addLiveIn(PhysReg); + DEBUG(dbgs() << "\tBB#" << MBB->getNumber() << ':' + << PrintReg(SI.value()->reg, TRI)); + } else if (SI.start() > Stop) + MBB = Indexes->getMBBFromIndex(SI.start().getPrevIndex()); + if (++MBB == MFE) + break; + tie(Start, Stop) = Indexes->getMBBRange(MBB); + SI.advanceTo(Start); } + DEBUG(dbgs() << '\n'); } } @@ -400,14 +485,11 @@ unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, SmallVector PhysRegSpillCands; // Check for an available register in this class. - const TargetRegisterClass *TRC = MRI->getRegClass(VirtReg.reg); - - for (TargetRegisterClass::iterator I = TRC->allocation_order_begin(*MF), - E = TRC->allocation_order_end(*MF); - I != E; ++I) { - + ArrayRef Order = + RegClassInfo.getOrder(MRI->getRegClass(VirtReg.reg)); + for (ArrayRef::iterator I = Order.begin(), E = Order.end(); I != E; + ++I) { unsigned PhysReg = *I; - if (ReservedRegs.test(PhysReg)) continue; // Check interference and as a side effect, intialize queries for this // VirtReg and its aliases. @@ -416,8 +498,9 @@ unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, // Found an available register. return PhysReg; } + Queries[interfReg].collectInterferingVRegs(1); LiveInterval *interferingVirtReg = - Queries[interfReg].firstInterference().liveUnionPos().value(); + Queries[interfReg].interferingVRegs().front(); // The current VirtReg must either be spillable, or one of its interferences // must have less spill weight. @@ -436,11 +519,13 @@ unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, // Tell the caller to allocate to this newly freed physical register. return *PhysRegI; } + // No other spill candidates were found, so spill the current VirtReg. DEBUG(dbgs() << "spilling: " << VirtReg << '\n'); - SmallVector pendingSpills; - - spiller().spill(&VirtReg, SplitVRegs, pendingSpills); + if (!VirtReg.isSpillable()) + return ~0u; + LiveRangeEdit LRE(VirtReg, SplitVRegs); + spiller().spill(LRE); // The live virtual register requesting allocation was spilled, so tell // the caller not to allocate anything during this round. @@ -456,10 +541,7 @@ bool RABasic::runOnMachineFunction(MachineFunction &mf) { DEBUG(RMF = &getAnalysis()); RegAllocBase::init(getAnalysis(), getAnalysis()); - - ReservedRegs = TRI->getReservedRegs(*MF); - - SpillerInstance.reset(createSpiller(*this, *MF, *VRM)); + SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); allocatePhysRegs(); @@ -475,7 +557,7 @@ bool RABasic::runOnMachineFunction(MachineFunction &mf) { // make the rewriter a separate pass and override verifyAnalysis instead. When // that happens, verification naturally falls under VerifyMachineCode. #ifndef NDEBUG - if (VerifyRegAlloc) { + if (VerifyEnabled) { // Verify accuracy of LiveIntervals. The standard machine code verifier // ensures that each LiveIntervals covers all uses of the virtual reg. @@ -483,7 +565,7 @@ bool RABasic::runOnMachineFunction(MachineFunction &mf) { // spiller. Always use -spiller=inline with -verify-regalloc. Even with the // inline spiller, some tests fail to verify because the coalescer does not // always generate verifiable code. - MF->verify(this); + MF->verify(this, "In RABasic::verify"); // Verify that LiveIntervals are partitioned into unions and disjoint within // the unions. @@ -492,8 +574,10 @@ bool RABasic::runOnMachineFunction(MachineFunction &mf) { #endif // !NDEBUG // Run rewriter - std::auto_ptr rewriter(createVirtRegRewriter()); - rewriter->runOnMachineFunction(*MF, *VRM, LIS); + VRM->rewrite(LIS->getSlotIndexes()); + + // Write out new DBG_VALUE instructions. + getAnalysis().emitDebugValues(VRM); // The pass output is in VirtRegMap. Release all the transient data. releaseMemory();