X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocBasic.cpp;h=5496d69fd3df1aa381faee2de9cdb4a3b9911100;hb=1b3f9198ab3880be34b6252423b9e388b5cd6a5e;hp=83999d9eb1371e88993afe6b81a9eac87a938654;hpb=e16eecc323879744dcff4f359ba9ccdb25bd6909;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp index 83999d9eb13..5496d69fd3d 100644 --- a/lib/CodeGen/RegAllocBasic.cpp +++ b/lib/CodeGen/RegAllocBasic.cpp @@ -13,14 +13,20 @@ //===----------------------------------------------------------------------===// #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 "VirtRegRewriter.h" +#include "VirtRegMap.h" +#include "llvm/ADT/OwningPtr.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Function.h" #include "llvm/PassAnalysisSupport.h" #include "llvm/CodeGen/CalcSpillWeights.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" @@ -28,27 +34,47 @@ #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" +#ifndef NDEBUG +#include "llvm/ADT/SparseBitVector.h" +#endif #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Support/Timer.h" -#include "VirtRegMap.h" -#include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "llvm/Target/TargetRegisterInfo.h" - - -#include +#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::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 /// algorithm. It prioritizes live virtual registers by spill weight and spills /// whenever a register is unavailable. This is not practical in production but @@ -57,17 +83,16 @@ namespace { class RABasic : public MachineFunctionPass, public RegAllocBase { // context - MachineFunction *mf_; - const TargetMachine *tm_; - MachineRegisterInfo *mri_; + MachineFunction *MF; // analyses - LiveStacks *ls_; - RenderMachineFunction *rmf_; + LiveStacks *LS; + RenderMachineFunction *RMF; // state - std::auto_ptr spiller_; - + std::auto_ptr SpillerInstance; + std::priority_queue, + CompSpillWeight> Queue; public: RABasic(); @@ -77,12 +102,28 @@ public: } /// RABasic analysis usage. - virtual void getAnalysisUsage(AnalysisUsage &au) const; + virtual void getAnalysisUsage(AnalysisUsage &AU) const; virtual void releaseMemory(); - virtual unsigned selectOrSplit(LiveInterval &lvr, - SmallVectorImpl &splitLVRs); + virtual Spiller &spiller() { return *SpillerInstance; } + + 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); /// Perform register allocation. virtual bool runOnMachineFunction(MachineFunction &mf); @@ -94,215 +135,400 @@ char RABasic::ID = 0; } // end anonymous namespace -// We should not need to publish the initializer as long as no other passes -// require RABasic. -#if 0 // disable INITIALIZE_PASS -INITIALIZE_PASS_BEGIN(RABasic, "basic-regalloc", - "Basic Register Allocator", false, false) -INITIALIZE_PASS_DEPENDENCY(LiveIntervals) -INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination) -INITIALIZE_AG_DEPENDENCY(RegisterCoalescer) -INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights) -INITIALIZE_PASS_DEPENDENCY(LiveStacks) -INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) -INITIALIZE_PASS_DEPENDENCY(VirtRegMap) -#ifndef NDEBUG -INITIALIZE_PASS_DEPENDENCY(RenderMachineFunction) -#endif -INITIALIZE_PASS_END(RABasic, "basic-regalloc", - "Basic Register Allocator", false, false) -#endif // disable INITIALIZE_PASS - 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()); initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry()); } -void RABasic::getAnalysisUsage(AnalysisUsage &au) const { - au.setPreservesCFG(); - au.addRequired(); - au.addPreserved(); +void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); if (StrongPHIElim) - au.addRequiredID(StrongPHIEliminationID); - au.addRequiredTransitive(); - au.addRequired(); - au.addRequired(); - au.addPreserved(); - au.addRequired(); - au.addPreserved(); - au.addRequired(); - au.addPreserved(); - DEBUG(au.addRequired()); - MachineFunctionPass::getAnalysisUsage(au); + AU.addRequiredID(StrongPHIEliminationID); + AU.addRequiredTransitiveID(RegisterCoalescerPassID); + AU.addRequired(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequiredID(MachineDominatorsID); + AU.addPreservedID(MachineDominatorsID); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + DEBUG(AU.addRequired()); + MachineFunctionPass::getAnalysisUsage(AU); } void RABasic::releaseMemory() { - spiller_.reset(0); + SpillerInstance.reset(0); RegAllocBase::releaseMemory(); } +#ifndef NDEBUG +// Verify each LiveIntervalUnion. +void RegAllocBase::verify() { + LiveVirtRegBitSet VisitedVRegs; + OwningArrayPtr + unionVRegs(new LiveVirtRegBitSet[PhysReg2LiveUnion.numRegs()]); + + // Verify disjoint unions. + for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) { + DEBUG(PhysReg2LiveUnion[PhysReg].print(dbgs(), TRI)); + LiveVirtRegBitSet &VRegs = unionVRegs[PhysReg]; + PhysReg2LiveUnion[PhysReg].verify(VRegs); + // Union + intersection test could be done efficiently in one pass, but + // don't add a method to SparseBitVector unless we really need it. + assert(!VisitedVRegs.intersects(VRegs) && "vreg in multiple unions"); + VisitedVRegs |= VRegs; + } + + // Verify vreg coverage. + for (LiveIntervals::iterator liItr = LIS->begin(), liEnd = LIS->end(); + liItr != liEnd; ++liItr) { + unsigned reg = liItr->first; + if (TargetRegisterInfo::isPhysicalRegister(reg)) continue; + if (!VRM->hasPhys(reg)) continue; // spilled? + unsigned PhysReg = VRM->getPhys(reg); + if (!unionVRegs[PhysReg].test(reg)) { + dbgs() << "LiveVirtReg " << reg << " not in union " << + TRI->getName(PhysReg) << "\n"; + llvm_unreachable("unallocated live vreg"); + } + } + // FIXME: I'm not sure how to verify spilled intervals. +} +#endif //!NDEBUG + //===----------------------------------------------------------------------===// // RegAllocBase Implementation //===----------------------------------------------------------------------===// // Instantiate a LiveIntervalUnion for each physical register. -void RegAllocBase::LIUArray::init(unsigned nRegs) { - array_.reset(new LiveIntervalUnion[nRegs]); - nRegs_ = nRegs; - for (unsigned pr = 0; pr < nRegs; ++pr) { - array_[pr].init(pr); - } +void RegAllocBase::LiveUnionArray::init(LiveIntervalUnion::Allocator &allocator, + unsigned NRegs) { + NumRegs = NRegs; + Array = + static_cast(malloc(sizeof(LiveIntervalUnion)*NRegs)); + for (unsigned r = 0; r != NRegs; ++r) + new(Array + r) LiveIntervalUnion(r, allocator); } -void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm, - LiveIntervals &lis) { - tri_ = &tri; - vrm_ = &vrm; - lis_ = &lis; - physReg2liu_.init(tri_->getNumRegs()); +void RegAllocBase::init(VirtRegMap &vrm, LiveIntervals &lis) { + NamedRegionTimer T("Initialize", TimerGroupName, TimePassesIsEnabled); + TRI = &vrm.getTargetRegInfo(); + MRI = &vrm.getRegInfo(); + VRM = &vrm; + LIS = &lis; + 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::LIUArray::clear() { - nRegs_ = 0; - array_.reset(0); +void RegAllocBase::LiveUnionArray::clear() { + if (!Array) + return; + for (unsigned r = 0; r != NumRegs; ++r) + Array[r].~LiveIntervalUnion(); + free(Array); + NumRegs = 0; + Array = 0; } void RegAllocBase::releaseMemory() { - physReg2liu_.clear(); + for (unsigned r = 0, e = PhysReg2LiveUnion.numRegs(); r != e; ++r) + PhysReg2LiveUnion[r].clear(); } -namespace llvm { -/// This class defines a queue of live virtual registers prioritized by spill -/// weight. The heaviest vreg is popped first. -/// -/// Currently, this is trivial wrapper that gives us an opaque type in the -/// header, but we may later give it a virtual interface for register allocators -/// to override the priority queue comparator. -class LiveVirtRegQueue { - typedef std::priority_queue - , LessSpillWeightPriority> PQ; - PQ pq_; - -public: - // Is the queue empty? - bool empty() { return pq_.empty(); } - - // Get the highest priority lvr (top + pop) - LiveInterval *get() { - LiveInterval *lvr = pq_.top(); - pq_.pop(); - return lvr; - } - // Add this lvr to the queue - void push(LiveInterval *lvr) { - pq_.push(lvr); +// 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 + enqueue(&VirtReg); } -}; -} // end namespace llvm +} -// 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(LiveVirtRegQueue &lvrQ) { - for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end(); - liItr != liEnd; ++liItr) { - unsigned reg = liItr->first; - LiveInterval &li = *liItr->second; - if (TargetRegisterInfo::isPhysicalRegister(reg)) { - physReg2liu_[reg].unify(li); - } - else { - lvrQ.push(&li); - } - } +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; } -// Top-level driver to manage the queue of unassigned LiveVirtRegs and call the +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() { - LiveVirtRegQueue lvrQ; - seedLiveVirtRegs(lvrQ); - while (!lvrQ.empty()) { - LiveInterval *lvr = lvrQ.get(); - typedef SmallVector LVRVec; - LVRVec splitLVRs; - unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs); - if (availablePhysReg) { - assert(splitLVRs.empty() && "inconsistent splitting"); - assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions"); - vrm_->assignVirt2Phys(lvr->reg, availablePhysReg); - physReg2liu_[availablePhysReg].unify(*lvr); + seedLiveRegs(); + + // Continue assigning vregs one at a time to available physical registers. + 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'); + typedef SmallVector VirtRegVec; + VirtRegVec SplitVRegs; + 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; } - else { - for (LVRVec::iterator lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end(); - lvrI != lvrEnd; ++lvrI) { - assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) && - "expect split value in virtual register"); - lvrQ.push(*lvrI); + + if (AvailablePhysReg) + assign(*VirtReg, AvailablePhysReg); + + for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); + I != E; ++I) { + 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"); + enqueue(SplitVirtReg); + ++NumNewQueued; + } + } +} + +// Check if this live virtual register interferes with a physical register. If +// not, then check for interference on each register that aliases with the +// physical register. Return the interfering register. +unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &VirtReg, + unsigned PhysReg) { + for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) + if (query(VirtReg, *AliasI).checkInterference()) + return *AliasI; + return 0; +} + +// Helper for spillInteferences() that spills all interfering vregs currently +// assigned to this physical register. +void RegAllocBase::spillReg(LiveInterval& VirtReg, unsigned PhysReg, + SmallVectorImpl &SplitVRegs) { + LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg); + assert(Q.seenAllInterferences() && "need collectInterferences()"); + const SmallVectorImpl &PendingSpills = Q.interferingVRegs(); + + for (SmallVectorImpl::const_iterator I = PendingSpills.begin(), + E = PendingSpills.end(); I != E; ++I) { + LiveInterval &SpilledVReg = **I; + DEBUG(dbgs() << "extracting from " << + TRI->getName(PhysReg) << " " << SpilledVReg << '\n'); + + // Deallocate the interfering vreg by removing it from the union. + // A LiveInterval instance may not be in a union during modification! + unassign(SpilledVReg, PhysReg); + + // Spill the extracted interval. + 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. + Q.clear(); +} + +// Spill or split all live virtual registers currently unified under PhysReg +// that interfere with VirtReg. The newly spilled or split live intervals are +// returned by appending them to SplitVRegs. +bool +RegAllocBase::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, + SmallVectorImpl &SplitVRegs) { + // Record each interference and determine if all are spillable before mutating + // either the union or live intervals. + unsigned NumInterferences = 0; + // Collect interferences assigned to any alias of the physical register. + for (const unsigned *asI = TRI->getOverlaps(PhysReg); *asI; ++asI) { + LiveIntervalUnion::Query &QAlias = query(VirtReg, *asI); + NumInterferences += QAlias.collectInterferingVRegs(); + if (QAlias.seenUnspillableVReg()) { + return false; } } + DEBUG(dbgs() << "spilling " << TRI->getName(PhysReg) << + " interferences with " << VirtReg << "\n"); + assert(NumInterferences > 0 && "expect interference"); + + // Spill each interfering vreg allocated to PhysReg or an alias. + for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) + spillReg(VirtReg, *AliasI, SplitVRegs); + return true; } -// Check if this live virtual reg interferes with a physical register. If not, -// then check for interference on each register that aliases with the physical -// register. -bool RegAllocBase::checkPhysRegInterference(LiveIntervalUnion::Query &query, - unsigned preg) { - if (query.checkInterference()) - return true; - for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) { - // We assume it's very unlikely for a register in the alias set to also be - // in the original register class. So we don't bother caching the - // interference. - LiveIntervalUnion::Query subQuery(query.lvr(), physReg2liu_[*asI] ); - if (subQuery.checkInterference()) - return true; +// Add newly allocated physical registers to the MBB live in sets. +void RegAllocBase::addMBBLiveIns(MachineFunction *MF) { + NamedRegionTimer T("MBB Live Ins", TimerGroupName, TimePassesIsEnabled); + 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; + 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'); } - return false; } + //===----------------------------------------------------------------------===// // RABasic Implementation //===----------------------------------------------------------------------===// // Driver for the register assignment and splitting heuristics. // Manages iteration over the LiveIntervalUnions. -// -// Minimal implementation of register assignment and splitting--spills whenever -// we run out of registers. +// +// This is a minimal implementation of register assignment and splitting that +// spills whenever we run out of registers. // // selectOrSplit can only be called once per live virtual register. We then do a // single interference test for each register the correct class until we find an // available register. So, the number of interference tests in the worst case is // |vregs| * |machineregs|. And since the number of interference tests is -// minimal, there is no value in caching them. -unsigned RABasic::selectOrSplit(LiveInterval &lvr, - SmallVectorImpl &splitLVRs) { - // Check for an available reg in this class. - const TargetRegisterClass *trc = mri_->getRegClass(lvr.reg); - for (TargetRegisterClass::iterator trcI = trc->allocation_order_begin(*mf_), - trcEnd = trc->allocation_order_end(*mf_); - trcI != trcEnd; ++trcI) { - unsigned preg = *trcI; - LiveIntervalUnion::Query query(lvr, physReg2liu_[preg]); - if (!checkPhysRegInterference(query, preg)) { - DEBUG(dbgs() << "\tallocating: " << tri_->getName(preg) << lvr << '\n'); - return preg; +// minimal, there is no value in caching them outside the scope of +// selectOrSplit(). +unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, + SmallVectorImpl &SplitVRegs) { + // Populate a list of physical register spill candidates. + SmallVector PhysRegSpillCands; + + // Check for an available register in this class. + ArrayRef Order = + RegClassInfo.getOrder(MRI->getRegClass(VirtReg.reg)); + for (ArrayRef::iterator I = Order.begin(), E = Order.end(); I != E; + ++I) { + unsigned PhysReg = *I; + + // Check interference and as a side effect, intialize queries for this + // VirtReg and its aliases. + unsigned interfReg = checkPhysRegInterference(VirtReg, PhysReg); + if (interfReg == 0) { + // Found an available register. + return PhysReg; + } + Queries[interfReg].collectInterferingVRegs(1); + LiveInterval *interferingVirtReg = + Queries[interfReg].interferingVRegs().front(); + + // The current VirtReg must either be spillable, or one of its interferences + // must have less spill weight. + if (interferingVirtReg->weight < VirtReg.weight ) { + PhysRegSpillCands.push_back(PhysReg); } } - DEBUG(dbgs() << "\tspilling: " << lvr << '\n'); - SmallVector spillIs; // ignored - spiller_->spill(&lvr, splitLVRs, spillIs); + // Try to spill another interfering reg with less spill weight. + for (SmallVectorImpl::iterator PhysRegI = PhysRegSpillCands.begin(), + PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) { - // FIXME: update LiveStacks + if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue; + + assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 && + "Interference after spill."); + // 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'); + 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. return 0; } @@ -311,36 +537,55 @@ bool RABasic::runOnMachineFunction(MachineFunction &mf) { << "********** Function: " << ((Value*)mf.getFunction())->getName() << '\n'); - mf_ = &mf; - tm_ = &mf.getTarget(); - mri_ = &mf.getRegInfo(); + MF = &mf; + DEBUG(RMF = &getAnalysis()); - DEBUG(rmf_ = &getAnalysis()); - - RegAllocBase::init(*tm_->getRegisterInfo(), getAnalysis(), - getAnalysis()); + RegAllocBase::init(getAnalysis(), getAnalysis()); + SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); - spiller_.reset(createSpiller(*this, *mf_, *vrm_)); - allocatePhysRegs(); + addMBBLiveIns(MF); + // Diagnostic output before rewriting - DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n"); + DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n"); // optional HTML output - DEBUG(rmf_->renderMachineFunction("After basic register allocation.", vrm_)); + DEBUG(RMF->renderMachineFunction("After basic register allocation.", VRM)); + + // FIXME: Verification currently must run before VirtRegRewriter. We should + // make the rewriter a separate pass and override verifyAnalysis instead. When + // that happens, verification naturally falls under VerifyMachineCode. +#ifndef NDEBUG + if (VerifyEnabled) { + // Verify accuracy of LiveIntervals. The standard machine code verifier + // ensures that each LiveIntervals covers all uses of the virtual reg. + + // FIXME: MachineVerifier is badly broken when using the standard + // 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, "In RABasic::verify"); + + // Verify that LiveIntervals are partitioned into unions and disjoint within + // the unions. + verify(); + } +#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(); - + return true; } -FunctionPass* llvm::createBasicRegisterAllocator() +FunctionPass* llvm::createBasicRegisterAllocator() { return new RABasic(); }