X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocBasic.cpp;h=6bc678e8521190bed76f37429a18c5215abdbe42;hb=8308f0e30fb647576a9a9de775e45fb4b1c0a08f;hp=6c592c8e25ed66e8d94d821eb9ca63f2d24d5cd0;hpb=964bc25e5a03be208427ce2ebadb22a42681ef9c;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp index 6c592c8e25e..6bc678e8521 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 // @@ -12,43 +12,48 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" -#include "LiveIntervalUnion.h" +#include "llvm/CodeGen/Passes.h" +#include "AllocationOrder.h" +#include "LiveDebugVariables.h" #include "RegAllocBase.h" -#include "RenderMachineFunction.h" #include "Spiller.h" -#include "VirtRegRewriter.h" -#include "llvm/Function.h" -#include "llvm/PassAnalysisSupport.h" +#include "llvm/Analysis/AliasAnalysis.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/CodeGen/RegisterCoalescer.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetOptions.h" +#include "llvm/CodeGen/VirtRegMap.h" +#include "llvm/PassAnalysisSupport.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" - -#include "VirtRegMap.h" -#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" - - -#include +#include #include using namespace llvm; +#define DEBUG_TYPE "regalloc" + static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator", createBasicRegisterAllocator); 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,35 +62,55 @@ namespace { class RABasic : public MachineFunctionPass, public RegAllocBase { // context - MachineFunction *mf_; - const TargetMachine *tm_; - MachineRegisterInfo *mri_; - - // analyses - LiveStacks *ls_; - RenderMachineFunction *rmf_; + MachineFunction *MF; // state - std::auto_ptr spiller_; + std::unique_ptr SpillerInstance; + std::priority_queue, + CompSpillWeight> Queue; + + // Scratch space. Allocated here to avoid repeated malloc calls in + // selectOrSplit(). + BitVector UsableRegs; 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 unsigned selectOrSplit(LiveInterval &lvr, - SmallVectorImpl &splitLVRs); + Spiller &spiller() override { return *SpillerInstance; } + + void enqueue(LiveInterval *LI) override { + Queue.push(LI); + } + + LiveInterval *dequeue() override { + if (Queue.empty()) + return nullptr; + LiveInterval *LI = Queue.top(); + Queue.pop(); + return LI; + } + + 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); static char ID; }; @@ -94,256 +119,180 @@ 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()); - initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); + initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); + initializeMachineSchedulerPass(*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 { - au.setPreservesCFG(); - au.addRequired(); - au.addPreserved(); - if (StrongPHIElim) - au.addRequiredID(StrongPHIEliminationID); - au.addRequiredTransitive(); - 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::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequiredID(MachineDominatorsID); + AU.addPreservedID(MachineDominatorsID); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + MachineFunctionPass::getAnalysisUsage(AU); } void RABasic::releaseMemory() { - spiller_.reset(0); - RegAllocBase::releaseMemory(); + SpillerInstance.reset(); } -//===----------------------------------------------------------------------===// -// 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); +// 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) { + // Record each interference and determine if all are spillable before mutating + // either the union or live intervals. + SmallVector Intfs; + + // Collect interferences assigned to any alias of the physical register. + 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(!Intfs.empty() && "expected interference"); -void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm, - LiveIntervals &lis) { - tri_ = &tri; - vrm_ = &vrm; - lis_ = &lis; - physReg2liu_.init(tri_->getNumRegs()); -} + // Spill each interfering vreg allocated to PhysReg or an alias. + for (unsigned i = 0, e = Intfs.size(); i != e; ++i) { + LiveInterval &Spill = *Intfs[i]; -void RegAllocBase::LIUArray::clear() { - nRegs_ = 0; - array_.reset(0); -} + // Skip duplicates. + if (!VRM->hasPhys(Spill.reg)) + continue; -void RegAllocBase::releaseMemory() { - physReg2liu_.clear(); -} + // Deallocate the interfering vreg by removing it from the union. + // A LiveInterval instance may not be in a union during modification! + Matrix->unassign(Spill); -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; + // Spill the extracted interval. + LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM); + spiller().spill(LRE); } - // Add this lvr to the queue - void push(LiveInterval *lvr) { - pq_.push(lvr); - } -}; -} // 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); - } - } -} - -// Top-level driver to manage the queue of unassigned LiveVirtRegs 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); - } - 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); - } - } - } -} - -// 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; - } - return false; + return true; } -//===----------------------------------------------------------------------===// -// 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. + 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; + + 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; } } - DEBUG(dbgs() << "\tspilling: " << lvr << '\n'); - SmallVector spillIs; // ignored - spiller_->spill(&lvr, splitLVRs, spillIs); - // FIXME: update LiveStacks + // 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; + + assert(!Matrix->checkInterference(VirtReg, *PhysRegI) && + "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, *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. return 0; } bool RABasic::runOnMachineFunction(MachineFunction &mf) { DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n" << "********** Function: " - << ((Value*)mf.getFunction())->getName() << '\n'); + << mf.getName() << '\n'); - mf_ = &mf; - tm_ = &mf.getTarget(); - mri_ = &mf.getRegInfo(); + MF = &mf; + RegAllocBase::init(getAnalysis(), + getAnalysis(), + getAnalysis()); - DEBUG(rmf_ = &getAnalysis()); - - RegAllocBase::init(*tm_->getRegisterInfo(), getAnalysis(), - getAnalysis()); + calculateSpillWeightsAndHints(*LIS, *MF, + getAnalysis(), + getAnalysis()); + + SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); - spiller_.reset(createSpiller(*this, *mf_, *vrm_)); - allocatePhysRegs(); // Diagnostic output before rewriting - DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n"); - - // optional HTML output - DEBUG(rmf_->renderMachineFunction("After basic register allocation.", vrm_)); - - // Run rewriter - std::auto_ptr rewriter(createVirtRegRewriter()); - rewriter->runOnMachineFunction(*mf_, *vrm_, lis_); + DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n"); - // The pass output is in VirtRegMap. Release all the transient data. releaseMemory(); - return true; } -FunctionPass* llvm::createBasicRegisterAllocator() +FunctionPass* llvm::createBasicRegisterAllocator() { return new RABasic(); }