X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocBasic.cpp;h=0090332a8123bb1019a7077d282c233a427f20c9;hb=415561b6e077fb4dda5d59c699829c9e7d39e08e;hp=f39a21c058a8e538ddaca4de3c28b87543ef08ea;hpb=e4fd907e72a599eddfa7a81eac4366b5b82523e3;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp index f39a21c058a..0090332a812 100644 --- a/lib/CodeGen/RegAllocBasic.cpp +++ b/lib/CodeGen/RegAllocBasic.cpp @@ -12,36 +12,35 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" -#include "RegAllocBase.h" +#include "llvm/CodeGen/Passes.h" +#include "AllocationOrder.h" #include "LiveDebugVariables.h" -#include "LiveRangeEdit.h" -#include "RenderMachineFunction.h" +#include "RegAllocBase.h" #include "Spiller.h" -#include "VirtRegMap.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/LiveRegMatrix.h" #include "llvm/CodeGen/LiveStackAnalysis.h" +#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/RegAllocRegistry.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetOptions.h" -#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/CodeGen/VirtRegMap.h" +#include "llvm/PassAnalysisSupport.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" - +#include "llvm/Target/TargetRegisterInfo.h" #include #include using namespace llvm; +#define DEBUG_TYPE "regalloc" + static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator", createBasicRegisterAllocator); @@ -64,12 +63,8 @@ class RABasic : public MachineFunctionPass, public RegAllocBase // context MachineFunction *MF; - // analyses - LiveStacks *LS; - RenderMachineFunction *RMF; - // state - std::auto_ptr SpillerInstance; + std::unique_ptr SpillerInstance; std::priority_queue, CompSpillWeight> Queue; @@ -81,45 +76,40 @@ public: RABasic(); /// Return the pass name. - virtual const char* getPassName() const { + const char* getPassName() const override { return "Basic Register Allocator"; } /// RABasic analysis usage. - virtual void getAnalysisUsage(AnalysisUsage &AU) const; + void getAnalysisUsage(AnalysisUsage &AU) const override; - virtual void releaseMemory(); + void releaseMemory() override; - virtual Spiller &spiller() { return *SpillerInstance; } + Spiller &spiller() override { return *SpillerInstance; } - virtual float getPriority(LiveInterval *LI) { return LI->weight; } - - virtual void enqueue(LiveInterval *LI) { + void enqueue(LiveInterval *LI) override { Queue.push(LI); } - virtual LiveInterval *dequeue() { + LiveInterval *dequeue() override { if (Queue.empty()) - return 0; + return nullptr; LiveInterval *LI = Queue.top(); Queue.pop(); return LI; } - virtual unsigned selectOrSplit(LiveInterval &VirtReg, - SmallVectorImpl &SplitVRegs); + unsigned selectOrSplit(LiveInterval &VirtReg, + SmallVectorImpl &SplitVRegs) override; /// Perform register allocation. - virtual bool runOnMachineFunction(MachineFunction &mf); + bool runOnMachineFunction(MachineFunction &mf) override; // 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); + SmallVectorImpl &SplitVRegs); static char ID; }; @@ -134,12 +124,11 @@ RABasic::RABasic(): MachineFunctionPass(ID) { initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); - initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); initializeLiveStacksPass(*PassRegistry::getPassRegistry()); initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); - initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry()); + initializeLiveRegMatrixPass(*PassRegistry::getPassRegistry()); } void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { @@ -147,77 +136,72 @@ void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); AU.addPreserved(); AU.addRequired(); + AU.addPreserved(); AU.addPreserved(); AU.addRequired(); AU.addPreserved(); - AU.addRequired(); AU.addRequired(); AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); AU.addRequiredID(MachineDominatorsID); AU.addPreservedID(MachineDominatorsID); AU.addRequired(); AU.addPreserved(); AU.addRequired(); AU.addPreserved(); - DEBUG(AU.addRequired()); + AU.addRequired(); + AU.addPreserved(); MachineFunctionPass::getAnalysisUsage(AU); } void RABasic::releaseMemory() { - SpillerInstance.reset(0); - RegAllocBase::releaseMemory(); + SpillerInstance.reset(); } -// Helper for spillInterferences() that spills all interfering vregs currently -// assigned to this physical register. -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(); - - 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); - 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 RABasic::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, - SmallVectorImpl &SplitVRegs) { + SmallVectorImpl &SplitVRegs) { // Record each interference and determine if all are spillable before mutating // either the union or live intervals. - unsigned NumInterferences = 0; + SmallVector Intfs; + // Collect interferences assigned to any alias of the physical register. - for (const uint16_t *asI = TRI->getOverlaps(PhysReg); *asI; ++asI) { - LiveIntervalUnion::Query &QAlias = query(VirtReg, *asI); - NumInterferences += QAlias.collectInterferingVRegs(); - if (QAlias.seenUnspillableVReg()) { + for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { + LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); + Q.collectInterferingVRegs(); + if (Q.seenUnspillableVReg()) return false; + for (unsigned i = Q.interferingVRegs().size(); i; --i) { + LiveInterval *Intf = Q.interferingVRegs()[i - 1]; + if (!Intf->isSpillable() || Intf->weight > VirtReg.weight) + return false; + Intfs.push_back(Intf); } } DEBUG(dbgs() << "spilling " << TRI->getName(PhysReg) << " interferences with " << VirtReg << "\n"); - assert(NumInterferences > 0 && "expect interference"); + assert(!Intfs.empty() && "expected interference"); // Spill each interfering vreg allocated to PhysReg or an alias. - for (const uint16_t *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) - spillReg(VirtReg, *AliasI, SplitVRegs); + for (unsigned i = 0, e = Intfs.size(); i != e; ++i) { + LiveInterval &Spill = *Intfs[i]; + + // Skip duplicates. + if (!VRM->hasPhys(Spill.reg)) + continue; + + // Deallocate the interfering vreg by removing it from the union. + // A LiveInterval instance may not be in a union during modification! + Matrix->unassign(Spill); + + // Spill the extracted interval. + LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM); + spiller().spill(LRE); + } return true; } @@ -234,50 +218,37 @@ bool RABasic::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, // minimal, there is no value in caching them outside the scope of // 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); - + 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; - - // 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. - unsigned interfReg = checkPhysRegInterference(VirtReg, PhysReg); - if (interfReg == 0) { - // Found an available register. + AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo); + while (unsigned PhysReg = Order.next()) { + // Check for interference in PhysReg + switch (Matrix->checkInterference(VirtReg, PhysReg)) { + case LiveRegMatrix::IK_Free: + // PhysReg is available, allocate it. return PhysReg; - } - LiveIntervalUnion::Query &IntfQ = query(VirtReg, interfReg); - IntfQ.collectInterferingVRegs(1); - LiveInterval *interferingVirtReg = IntfQ.interferingVRegs().front(); - // The current VirtReg must either be spillable, or one of its interferences - // must have less spill weight. - if (interferingVirtReg->weight < VirtReg.weight ) { + case LiveRegMatrix::IK_VirtReg: + // Only virtual registers in the way, we may be able to spill them. PhysRegSpillCands.push_back(PhysReg); + continue; + + default: + // RegMask or RegUnit interference. + continue; } } + // Try to spill another interfering reg with less spill weight. for (SmallVectorImpl::iterator PhysRegI = PhysRegSpillCands.begin(), - PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) { - - if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue; + PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) { + if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) + continue; - assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 && + assert(!Matrix->checkInterference(VirtReg, *PhysRegI) && "Interference after spill."); // Tell the caller to allocate to this newly freed physical register. return *PhysRegI; @@ -287,7 +258,7 @@ unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, DEBUG(dbgs() << "spilling: " << VirtReg << '\n'); if (!VirtReg.isSpillable()) return ~0u; - LiveRangeEdit LRE(VirtReg, SplitVRegs); + LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM); spiller().spill(LRE); // The live virtual register requesting allocation was spilled, so tell @@ -298,56 +269,25 @@ unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, bool RABasic::runOnMachineFunction(MachineFunction &mf) { DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n" << "********** Function: " - << ((Value*)mf.getFunction())->getName() << '\n'); + << mf.getName() << '\n'); MF = &mf; - DEBUG(RMF = &getAnalysis()); + RegAllocBase::init(getAnalysis(), + getAnalysis(), + getAnalysis()); + + calculateSpillWeightsAndHints(*LIS, *MF, + getAnalysis(), + getAnalysis()); - RegAllocBase::init(getAnalysis(), getAnalysis()); SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); allocatePhysRegs(); - addMBBLiveIns(MF); - // Diagnostic output before rewriting DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n"); - // optional HTML output - 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 - VRM->rewrite(LIS->getSlotIndexes()); - - // Write out new DBG_VALUE instructions. - getAnalysis().emitDebugValues(VRM); - - // 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; }