X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocBasic.cpp;h=77ee3148f31aae395d6bd48dda59336ae06042ee;hb=a62e235c1c539aef38b94029035b46bd82f12357;hp=88446aa505679510522533ab03e186ccccca2ddc;hpb=d0bec3e62c98b1f0ef3a41db8f95599b2014c131;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp index 88446aa5056..77ee3148f31 100644 --- a/lib/CodeGen/RegAllocBasic.cpp +++ b/lib/CodeGen/RegAllocBasic.cpp @@ -1,4 +1,4 @@ -//===-- RegAllocBasic.cpp - basic register allocator ----------------------===// +//===-- RegAllocBasic.cpp - Basic Register Allocator ----------------------===// // // The LLVM Compiler Infrastructure // @@ -13,18 +13,17 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "regalloc" -#include "LiveIntervalUnion.h" #include "RegAllocBase.h" +#include "LiveDebugVariables.h" #include "RenderMachineFunction.h" #include "Spiller.h" #include "VirtRegMap.h" -#include "VirtRegRewriter.h" -#include "llvm/ADT/OwningPtr.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/LiveRangeEdit.h" #include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" @@ -32,39 +31,29 @@ #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 +#include using namespace llvm; 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")); - namespace { + struct CompSpillWeight { + bool operator()(LiveInterval *A, LiveInterval *B) const { + return A->weight < B->weight; + } + }; +} -class PhysicalRegisterDescription : public AbstractRegisterDescription { - const TargetRegisterInfo *TRI; -public: - PhysicalRegisterDescription(const TargetRegisterInfo *T): TRI(T) {} - virtual const char *getName(unsigned Reg) const { return TRI->getName(Reg); } -}; - +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 @@ -74,10 +63,6 @@ class RABasic : public MachineFunctionPass, public RegAllocBase { // context MachineFunction *MF; - const TargetMachine *TM; - MachineRegisterInfo *MRI; - - BitVector ReservedRegs; // analyses LiveStacks *LS; @@ -85,6 +70,12 @@ class RABasic : public MachineFunctionPass, public RegAllocBase // state std::auto_ptr SpillerInstance; + std::priority_queue, + CompSpillWeight> Queue; + + // Scratch space. Allocated here to avoid repeated malloc calls in + // selectOrSplit(). + BitVector UsableRegs; public: RABasic(); @@ -103,12 +94,33 @@ 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); /// Perform register allocation. virtual bool runOnMachineFunction(MachineFunction &mf); + // Helper for spilling all live virtual registers currently unified under preg + // that interfere with the most recently queried lvr. Return true if spilling + // was successful, and append any new spilled/split intervals to splitLVRs. + bool spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, + SmallVectorImpl &SplitVRegs); + + void spillReg(LiveInterval &VirtReg, unsigned PhysReg, + SmallVectorImpl &SplitVRegs); + static char ID; }; @@ -117,10 +129,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()); + initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); initializeLiveStacksPass(*PassRegistry::getPassRegistry()); initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); @@ -135,9 +148,8 @@ void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved(); AU.addRequired(); AU.addPreserved(); - if (StrongPHIElim) - AU.addRequiredID(StrongPHIEliminationID); - AU.addRequiredTransitive(); + AU.addRequired(); + AU.addPreserved(); AU.addRequired(); AU.addRequired(); AU.addPreserved(); @@ -156,154 +168,10 @@ void RABasic::releaseMemory() { 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(PhysicalRegisterDescription PRD(TRI); - PhysReg2LiveUnion[PhysReg].dump(&PRD)); - 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::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; - PhysReg2LiveUnion.init(UnionAllocator, TRI->getNumRegs()); - // Cache an interferece query for each physical reg - Queries.reset(new LiveIntervalUnion::Query[PhysReg2LiveUnion.numRegs()]); -} - -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() { - PhysReg2LiveUnion.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) { - 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)); - } -} - -// 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); - - // 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(); - - // selectOrSplit requests the allocator to return an available physical - // register if possible and populate a list of new live intervals that - // result from splitting. - typedef SmallVector VirtRegVec; - VirtRegVec SplitVRegs; - unsigned AvailablePhysReg = selectOrSplit(VirtReg, SplitVRegs); - - if (AvailablePhysReg) { - DEBUG(dbgs() << "allocating: " << TRI->getName(AvailablePhysReg) << - " " << VirtReg << '\n'); - assert(!VRM->hasPhys(VirtReg.reg) && "duplicate vreg in union"); - VRM->assignVirt2Phys(VirtReg.reg, AvailablePhysReg); - PhysReg2LiveUnion[AvailablePhysReg].unify(VirtReg); - } - for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); - I != E; ++I) { - LiveInterval* SplitVirtReg = *I; - if (SplitVirtReg->empty()) 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)); - } - } -} - -// 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) { - if (query(VirtReg, PhysReg).checkInterference()) - return PhysReg; - for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) { - if (query(VirtReg, *AliasI).checkInterference()) - return *AliasI; - } - return 0; -} - -// Helper for spillInteferences() that spills all interfering vregs currently +// Helper for spillInterferences() that spills all interfering vregs currently // assigned to this physical register. -void RegAllocBase::spillReg(LiveInterval& VirtReg, unsigned PhysReg, - SmallVectorImpl &SplitVRegs) { +void RABasic::spillReg(LiveInterval& VirtReg, unsigned PhysReg, + SmallVectorImpl &SplitVRegs) { LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg); assert(Q.seenAllInterferences() && "need collectInterferences()"); const SmallVectorImpl &PendingSpills = Q.interferingVRegs(); @@ -316,13 +184,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, *MF, *LIS, VRM); + spiller().spill(LRE); } // After extracting segments, the query's results are invalid. But keep the // contents valid until we're done accessing pendingSpills. @@ -332,20 +198,13 @@ void RegAllocBase::spillReg(LiveInterval& VirtReg, unsigned PhysReg, // 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, +bool RABasic::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, SmallVectorImpl &SplitVRegs) { // Record each interference and determine if all are spillable before mutating // either the union or live intervals. - - // Collect interferences assigned to the requested physical register. - LiveIntervalUnion::Query &QPreg = query(VirtReg, PhysReg); - unsigned NumInterferences = QPreg.collectInterferingVRegs(); - if (QPreg.seenUnspillableVReg()) { - return false; - } + unsigned NumInterferences = 0; // Collect interferences assigned to any alias of the physical register. - for (const unsigned *asI = TRI->getAliasSet(PhysReg); *asI; ++asI) { + for (const uint16_t *asI = TRI->getOverlaps(PhysReg); *asI; ++asI) { LiveIntervalUnion::Query &QAlias = query(VirtReg, *asI); NumInterferences += QAlias.collectInterferingVRegs(); if (QAlias.seenUnspillableVReg()) { @@ -357,46 +216,11 @@ RegAllocBase::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, assert(NumInterferences > 0 && "expect interference"); // Spill each interfering vreg allocated to PhysReg or an alias. - spillReg(VirtReg, PhysReg, SplitVRegs); - for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) + for (const uint16_t *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) spillReg(VirtReg, *AliasI, SplitVRegs); return true; } -// Add newly allocated physical registers to the MBB live in sets. -void RegAllocBase::addMBBLiveIns(MachineFunction *MF) { - typedef SmallVector MBBVec; - MBBVec liveInMBBs; - MachineBasicBlock &entryMBB = *MF->begin(); - - 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); - } - } - } -} - - -//===----------------------------------------------------------------------===// -// RABasic Implementation -//===----------------------------------------------------------------------===// - // Driver for the register assignment and splitting heuristics. // Manages iteration over the LiveIntervalUnions. // @@ -411,19 +235,24 @@ void RegAllocBase::addMBBLiveIns(MachineFunction *MF) { // selectOrSplit(). unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, SmallVectorImpl &SplitVRegs) { + // Check for register mask interference. When live ranges cross calls, the + // set of usable registers is reduced to the callee-saved ones. + bool CrossRegMasks = LIS->checkRegMaskInterference(VirtReg, UsableRegs); + // Populate a list of physical register spill candidates. SmallVector PhysRegSpillCands; // Check for an available register in this class. - const TargetRegisterClass *TRC = MRI->getRegClass(VirtReg.reg); - DEBUG(dbgs() << "RegClass: " << TRC->getName() << ' '); - - 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; + + // If PhysReg is clobbered by a register mask, it isn't useful for + // allocation or spilling. + if (CrossRegMasks && !UsableRegs.test(PhysReg)) + continue; // Check interference and as a side effect, intialize queries for this // VirtReg and its aliases. @@ -432,18 +261,17 @@ unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, // Found an available register. return PhysReg; } - LiveInterval *interferingVirtReg = - Queries[interfReg].firstInterference().liveUnionPos().value(); + LiveIntervalUnion::Query &IntfQ = query(VirtReg, interfReg); + IntfQ.collectInterferingVRegs(1); + LiveInterval *interferingVirtReg = IntfQ.interferingVRegs().front(); - // The current VirtReg must either spillable, or one of its interferences + // 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); } } // Try to spill another interfering reg with less spill weight. - // - // FIXME: RAGreedy will sort this list by spill weight. for (SmallVectorImpl::iterator PhysRegI = PhysRegSpillCands.begin(), PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) { @@ -454,11 +282,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, *MF, *LIS, VRM); + spiller().spill(LRE); // The live virtual register requesting allocation was spilled, so tell // the caller not to allocate anything during this round. @@ -471,18 +301,10 @@ bool RABasic::runOnMachineFunction(MachineFunction &mf) { << ((Value*)mf.getFunction())->getName() << '\n'); MF = &mf; - TM = &mf.getTarget(); - MRI = &mf.getRegInfo(); - DEBUG(RMF = &getAnalysis()); - const TargetRegisterInfo *TRI = TM->getRegisterInfo(); - RegAllocBase::init(*TRI, getAnalysis(), - getAnalysis()); - - ReservedRegs = TRI->getReservedRegs(*MF); - - SpillerInstance.reset(createSpiller(*this, *MF, *VRM)); + RegAllocBase::init(getAnalysis(), getAnalysis()); + SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); allocatePhysRegs(); @@ -498,7 +320,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. @@ -506,7 +328,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. @@ -515,10 +337,15 @@ 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. + // All machine operands and other references to virtual registers have been + // replaced. Remove the virtual registers and release all the transient data. + VRM->clearAllVirt(); + MRI->clearVirtRegs(); releaseMemory(); return true;