X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocPBQP.cpp;h=81cfd8f0bbdc8531ff1438bad486fe428756f338;hb=188a87da79f51b00522b9487ee352a50a01e5ea4;hp=ee82f6333fdba8a9ce18c582bfd25d3460026d58;hpb=b1290a6cc40f7caa0351450ce7021a0d48b5f2c0;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index ee82f6333fd..81cfd8f0bbd 100644 --- a/lib/CodeGen/RegAllocPBQP.cpp +++ b/lib/CodeGen/RegAllocPBQP.cpp @@ -6,17 +6,17 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -// +// // This file contains a Partitioned Boolean Quadratic Programming (PBQP) based // register allocator for LLVM. This allocator works by constructing a PBQP // problem representing the register allocation problem under consideration, // solving this using a PBQP solver, and mapping the solution back to a // register assignment. If any variables are selected for spilling then spill -// code is inserted and the process repeated. +// code is inserted and the process repeated. // // The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned // for register allocation. For more information on PBQP for register -// allocation see the following papers: +// allocation, see the following papers: // // (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with // PBQP. In Proceedings of the 7th Joint Modular Languages Conference @@ -26,71 +26,81 @@ // architectures. In Proceedings of the Joint Conference on Languages, // Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York, // NY, USA, 139-148. -// -// Author: Lang Hames -// Email: lhames@gmail.com // //===----------------------------------------------------------------------===// -// TODO: -// -// * Use of std::set in constructPBQPProblem destroys allocation order preference. -// Switch to an order preserving container. -// -// * Coalescing support. - #define DEBUG_TYPE "regalloc" -#include "PBQP.h" +#include "PBQP/HeuristicSolver.h" +#include "PBQP/Graph.h" +#include "PBQP/Heuristics/Briggs.h" #include "VirtRegMap.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/RegAllocRegistry.h" +#include "VirtRegRewriter.h" +#include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/LiveStackAnalysis.h" +#include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineLoopInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/RegAllocRegistry.h" +#include "llvm/CodeGen/RegisterCoalescer.h" #include "llvm/Support/Debug.h" -#include +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include #include +#include #include #include -#include using namespace llvm; static RegisterRegAlloc -registerPBQPRepAlloc("pbqp", " PBQP register allocator", - createPBQPRegisterAllocator); +registerPBQPRepAlloc("pbqp", "PBQP register allocator", + llvm::createPBQPRegisterAllocator); +static cl::opt +pbqpCoalescing("pbqp-coalescing", + cl::desc("Attempt coalescing during PBQP register allocation."), + cl::init(false), cl::Hidden); namespace { - //! - //! PBQP based allocators solve the register allocation problem by mapping - //! register allocation problems to Partitioned Boolean Quadratic - //! Programming problems. - class VISIBILITY_HIDDEN PBQPRegAlloc : public MachineFunctionPass { + /// + /// PBQP based allocators solve the register allocation problem by mapping + /// register allocation problems to Partitioned Boolean Quadratic + /// Programming problems. + class PBQPRegAlloc : public MachineFunctionPass { public: static char ID; - - //! Construct a PBQP register allocator. - PBQPRegAlloc() : MachineFunctionPass((intptr_t)&ID) {} - //! Return the pass name. - virtual const char* getPassName() const throw() { + /// Construct a PBQP register allocator. + PBQPRegAlloc() : MachineFunctionPass(&ID) {} + + /// Return the pass name. + virtual const char* getPassName() const { return "PBQP Register Allocator"; } - //! PBQP analysis usage. + /// PBQP analysis usage. virtual void getAnalysisUsage(AnalysisUsage &au) const { + au.addRequired(); + au.addPreserved(); au.addRequired(); + //au.addRequiredID(SplitCriticalEdgesID); + au.addRequired(); + au.addRequired(); + au.addRequired(); + au.addPreserved(); au.addRequired(); + au.addPreserved(); + au.addRequired(); MachineFunctionPass::getAnalysisUsage(au); } - //! Perform register allocation + /// Perform register allocation virtual bool runOnMachineFunction(MachineFunction &MF); private: @@ -98,7 +108,13 @@ namespace { typedef std::vector Node2LIMap; typedef std::vector AllowedSet; typedef std::vector AllowedSetMap; - typedef std::set IgnoreSet; + typedef std::set RegSet; + typedef std::pair RegPair; + typedef std::map CoalesceMap; + + typedef std::set LiveIntervalSet; + + typedef std::vector NodeVector; MachineFunction *mf; const TargetMachine *tm; @@ -107,60 +123,73 @@ namespace { const MachineLoopInfo *loopInfo; MachineRegisterInfo *mri; - LiveIntervals *li; + LiveIntervals *lis; + LiveStacks *lss; VirtRegMap *vrm; LI2NodeMap li2Node; Node2LIMap node2LI; AllowedSetMap allowedSets; - IgnoreSet ignoreSet; - - //! Builds a PBQP cost vector. - template - PBQPVector* buildCostVector(const Container &allowed, - PBQPNum spillCost) const; - - //! \brief Builds a PBQP interfernce matrix. - //! - //! @return Either a pointer to a non-zero PBQP matrix representing the - //! allocation option costs, or a null pointer for a zero matrix. - //! - //! Expects allowed sets for two interfering LiveIntervals. These allowed - //! sets should contain only allocable registers from the LiveInterval's - //! register class, with any interfering pre-colored registers removed. - template - PBQPMatrix* buildInterferenceMatrix(const Container &allowed1, - const Container &allowed2) const; - - //! - //! Expects allowed sets for two potentially coalescable LiveIntervals, - //! and an estimated benefit due to coalescing. The allowed sets should - //! contain only allocable registers from the LiveInterval's register - //! classes, with any interfering pre-colored registers removed. - template - PBQPMatrix* buildCoalescingMatrix(const Container &allowed1, - const Container &allowed2, - PBQPNum cBenefit) const; - - //! \brief Helper functior for constructInitialPBQPProblem(). - //! - //! This function iterates over the Function we are about to allocate for - //! and computes spill costs. - void calcSpillCosts(); - - //! \brief Scans the MachineFunction being allocated to find coalescing - // opportunities. - void findCoalescingOpportunities(); - - //! \brief Constructs a PBQP problem representation of the register - //! allocation problem for this function. - //! - //! @return a PBQP solver object for the register allocation problem. - pbqp* constructPBQPProblem(); - - //! \brief Given a solved PBQP problem maps this solution back to a register - //! assignment. - bool mapPBQPToRegAlloc(pbqp *problem); + LiveIntervalSet vregIntervalsToAlloc, + emptyVRegIntervals; + NodeVector problemNodes; + + + /// Builds a PBQP cost vector. + template + PBQP::Vector buildCostVector(unsigned vReg, + const RegContainer &allowed, + const CoalesceMap &cealesces, + PBQP::PBQPNum spillCost) const; + + /// \brief Builds a PBQP interference matrix. + /// + /// @return Either a pointer to a non-zero PBQP matrix representing the + /// allocation option costs, or a null pointer for a zero matrix. + /// + /// Expects allowed sets for two interfering LiveIntervals. These allowed + /// sets should contain only allocable registers from the LiveInterval's + /// register class, with any interfering pre-colored registers removed. + template + PBQP::Matrix* buildInterferenceMatrix(const RegContainer &allowed1, + const RegContainer &allowed2) const; + + /// + /// Expects allowed sets for two potentially coalescable LiveIntervals, + /// and an estimated benefit due to coalescing. The allowed sets should + /// contain only allocable registers from the LiveInterval's register + /// classes, with any interfering pre-colored registers removed. + template + PBQP::Matrix* buildCoalescingMatrix(const RegContainer &allowed1, + const RegContainer &allowed2, + PBQP::PBQPNum cBenefit) const; + + /// \brief Finds coalescing opportunities and returns them as a map. + /// + /// Any entries in the map are guaranteed coalescable, even if their + /// corresponding live intervals overlap. + CoalesceMap findCoalesces(); + + /// \brief Finds the initial set of vreg intervals to allocate. + void findVRegIntervalsToAlloc(); + + /// \brief Constructs a PBQP problem representation of the register + /// allocation problem for this function. + /// + /// @return a PBQP solver object for the register allocation problem. + PBQP::Graph constructPBQPProblem(); + + /// \brief Adds a stack interval if the given live interval has been + /// spilled. Used to support stack slot coloring. + void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri); + + /// \brief Given a solved PBQP problem maps this solution back to a register + /// assignment. + bool mapPBQPToRegAlloc(const PBQP::Solution &solution); + + /// \brief Postprocessing before final spilling. Sets basic block "live in" + /// variables. + void finalizeAlloc() const; }; @@ -168,23 +197,46 @@ namespace { } -template -PBQPVector* PBQPRegAlloc::buildCostVector(const Container &allowed, - PBQPNum spillCost) const { +template +PBQP::Vector PBQPRegAlloc::buildCostVector(unsigned vReg, + const RegContainer &allowed, + const CoalesceMap &coalesces, + PBQP::PBQPNum spillCost) const { + + typedef typename RegContainer::const_iterator AllowedItr; // Allocate vector. Additional element (0th) used for spill option - PBQPVector *v = new PBQPVector(allowed.size() + 1); + PBQP::Vector v(allowed.size() + 1, 0); + + v[0] = spillCost; + + // Iterate over the allowed registers inserting coalesce benefits if there + // are any. + unsigned ai = 0; + for (AllowedItr itr = allowed.begin(), end = allowed.end(); + itr != end; ++itr, ++ai) { + + unsigned pReg = *itr; + + CoalesceMap::const_iterator cmItr = + coalesces.find(RegPair(vReg, pReg)); + + // No coalesce - on to the next preg. + if (cmItr == coalesces.end()) + continue; - (*v)[0] = spillCost; + // We have a coalesce - insert the benefit. + v[ai + 1] = -cmItr->second; + } return v; } -template -PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( - const Container &allowed1, const Container &allowed2) const { +template +PBQP::Matrix* PBQPRegAlloc::buildInterferenceMatrix( + const RegContainer &allowed1, const RegContainer &allowed2) const { - typedef typename Container::const_iterator ContainerIterator; + typedef typename RegContainer::const_iterator RegContainerIterator; // Construct a PBQP matrix representing the cost of allocation options. The // rows and columns correspond to the allocation options for the two live @@ -194,8 +246,9 @@ PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( // that the spill option (element 0,0) has zero cost, since we can allocate // both intervals to memory safely (the cost for each individual allocation // to memory is accounted for by the cost vectors for each live interval). - PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1); - + PBQP::Matrix *m = + new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0); + // Assume this is a zero matrix until proven otherwise. Zero matrices occur // between interfering live ranges with non-overlapping register sets (e.g. // non-overlapping reg classes, or disjoint sets of allowed regs within the @@ -207,24 +260,24 @@ PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( // Row index. Starts at 1, since the 0th row is for the spill option, which // is always zero. - unsigned ri = 1; + unsigned ri = 1; - // Iterate over allowed sets, insert infinities where required. - for (ContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); + // Iterate over allowed sets, insert infinities where required. + for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); a1Itr != a1End; ++a1Itr) { // Column index, starts at 1 as for row index. unsigned ci = 1; unsigned reg1 = *a1Itr; - for (ContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); + for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); a2Itr != a2End; ++a2Itr) { unsigned reg2 = *a2Itr; // If the row/column regs are identical or alias insert an infinity. - if ((reg1 == reg2) || tri->areAliases(reg1, reg2)) { - (*m)[ri][ci] = std::numeric_limits::infinity(); + if (tri->regsOverlap(reg1, reg2)) { + (*m)[ri][ci] = std::numeric_limits::infinity(); isZeroMatrix = false; } @@ -245,100 +298,279 @@ PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( return m; } -void PBQPRegAlloc::calcSpillCosts() { +template +PBQP::Matrix* PBQPRegAlloc::buildCoalescingMatrix( + const RegContainer &allowed1, const RegContainer &allowed2, + PBQP::PBQPNum cBenefit) const { + + typedef typename RegContainer::const_iterator RegContainerIterator; + + // Construct a PBQP Matrix representing the benefits of coalescing. As with + // interference matrices the rows and columns represent allowed registers + // for the LiveIntervals which are (potentially) to be coalesced. The amount + // -cBenefit will be placed in any element representing the same register + // for both intervals. + PBQP::Matrix *m = + new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0); + + // Reset costs to zero. + m->reset(0); + + // Assume the matrix is zero till proven otherwise. Zero matrices will be + // optimized away as in the interference case. + bool isZeroMatrix = true; + + // Row index. Starts at 1, since the 0th row is for the spill option, which + // is always zero. + unsigned ri = 1; + + // Iterate over the allowed sets, insert coalescing benefits where + // appropriate. + for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); + a1Itr != a1End; ++a1Itr) { + + // Column index, starts at 1 as for row index. + unsigned ci = 1; + unsigned reg1 = *a1Itr; + + for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); + a2Itr != a2End; ++a2Itr) { + + // If the row and column represent the same register insert a beneficial + // cost to preference this allocation - it would allow us to eliminate a + // move instruction. + if (reg1 == *a2Itr) { + (*m)[ri][ci] = -cBenefit; + isZeroMatrix = false; + } + + ++ci; + } - // Calculate the spill cost for each live interval by iterating over the - // function counting loads and stores, with loop depth taken into account. - for (MachineFunction::const_iterator bbItr = mf->begin(), bbEnd = mf->end(); + ++ri; + } + + // If this turns out to be a zero matrix... + if (isZeroMatrix) { + // ...free it and return null. + delete m; + return 0; + } + + return m; +} + +PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() { + + typedef MachineFunction::const_iterator MFIterator; + typedef MachineBasicBlock::const_iterator MBBIterator; + typedef LiveInterval::const_vni_iterator VNIIterator; + + CoalesceMap coalescesFound; + + // To find coalesces we need to iterate over the function looking for + // copy instructions. + for (MFIterator bbItr = mf->begin(), bbEnd = mf->end(); bbItr != bbEnd; ++bbItr) { const MachineBasicBlock *mbb = &*bbItr; - float loopDepth = loopInfo->getLoopDepth(mbb); - for (MachineBasicBlock::const_iterator - iItr = mbb->begin(), iEnd = mbb->end(); iItr != iEnd; ++iItr) { + for (MBBIterator iItr = mbb->begin(), iEnd = mbb->end(); + iItr != iEnd; ++iItr) { const MachineInstr *instr = &*iItr; + unsigned srcReg, dstReg, srcSubReg, dstSubReg; + + // If this isn't a copy then continue to the next instruction. + if (!tii->isMoveInstr(*instr, srcReg, dstReg, srcSubReg, dstSubReg)) + continue; + + // If the registers are already the same our job is nice and easy. + if (dstReg == srcReg) + continue; - for (unsigned opNo = 0; opNo < instr->getNumOperands(); ++opNo) { + bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg), + dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg); - const MachineOperand &mo = instr->getOperand(opNo); + // If both registers are physical then we can't coalesce. + if (srcRegIsPhysical && dstRegIsPhysical) + continue; + + // If it's a copy that includes a virtual register but the source and + // destination classes differ then we can't coalesce, so continue with + // the next instruction. + const TargetRegisterClass *srcRegClass = srcRegIsPhysical ? + tri->getPhysicalRegisterRegClass(srcReg) : mri->getRegClass(srcReg); + + const TargetRegisterClass *dstRegClass = dstRegIsPhysical ? + tri->getPhysicalRegisterRegClass(dstReg) : mri->getRegClass(dstReg); - // We're not interested in non-registers... - if (!mo.isRegister()) + if (srcRegClass != dstRegClass) + continue; + + // We also need any physical regs to be allocable, coalescing with + // a non-allocable register is invalid. + if (srcRegIsPhysical) { + if (std::find(dstRegClass->allocation_order_begin(*mf), + dstRegClass->allocation_order_end(*mf), srcReg) == + dstRegClass->allocation_order_end(*mf)) continue; - - unsigned moReg = mo.getReg(); + } - // ...Or invalid registers... - if (moReg == 0) + if (dstRegIsPhysical) { + if (std::find(srcRegClass->allocation_order_begin(*mf), + srcRegClass->allocation_order_end(*mf), dstReg) == + srcRegClass->allocation_order_end(*mf)) continue; + } + + // If we've made it here we have a copy with compatible register classes. + // We can probably coalesce, but we need to consider overlap. + const LiveInterval *srcLI = &lis->getInterval(srcReg), + *dstLI = &lis->getInterval(dstReg); + + if (srcLI->overlaps(*dstLI)) { + // Even in the case of an overlap we might still be able to coalesce, + // but we need to make sure that no definition of either range occurs + // while the other range is live. + + // Otherwise start by assuming we're ok. + bool badDef = false; + + // Test all defs of the source range. + for (VNIIterator + vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end(); + vniItr != vniEnd; ++vniItr) { + + // If we find a poorly defined def we err on the side of caution. + if (!(*vniItr)->def.isValid()) { + badDef = true; + break; + } + + // If we find a def that kills the coalescing opportunity then + // record it and break from the loop. + if (dstLI->liveAt((*vniItr)->def)) { + badDef = true; + break; + } + } - // ...Or physical registers... - if (TargetRegisterInfo::isPhysicalRegister(moReg)) + // If we have a bad def give up, continue to the next instruction. + if (badDef) continue; - assert ((mo.isUse() || mo.isDef()) && - "Not a use, not a def, what is it?"); + // Otherwise test definitions of the destination range. + for (VNIIterator + vniItr = dstLI->vni_begin(), vniEnd = dstLI->vni_end(); + vniItr != vniEnd; ++vniItr) { + + // We want to make sure we skip the copy instruction itself. + if ((*vniItr)->getCopy() == instr) + continue; + + if (!(*vniItr)->def.isValid()) { + badDef = true; + break; + } + + if (srcLI->liveAt((*vniItr)->def)) { + badDef = true; + break; + } + } - //... Just the virtual registers. We treat loads and stores as equal. - li->getInterval(moReg).weight += powf(10.0f, loopDepth); + // As before a bad def we give up and continue to the next instr. + if (badDef) + continue; } + // If we make it to here then either the ranges didn't overlap, or they + // did, but none of their definitions would prevent us from coalescing. + // We're good to go with the coalesce. + + float cBenefit = powf(10.0f, loopInfo->getLoopDepth(mbb)) / 5.0; + + coalescesFound[RegPair(srcReg, dstReg)] = cBenefit; + coalescesFound[RegPair(dstReg, srcReg)] = cBenefit; } } + return coalescesFound; +} + +void PBQPRegAlloc::findVRegIntervalsToAlloc() { + + // Iterate over all live ranges. + for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); + itr != end; ++itr) { + + // Ignore physical ones. + if (TargetRegisterInfo::isPhysicalRegister(itr->first)) + continue; + + LiveInterval *li = itr->second; + + // If this live interval is non-empty we will use pbqp to allocate it. + // Empty intervals we allocate in a simple post-processing stage in + // finalizeAlloc. + if (!li->empty()) { + vregIntervalsToAlloc.insert(li); + } + else { + emptyVRegIntervals.insert(li); + } + } } -pbqp* PBQPRegAlloc::constructPBQPProblem() { +PBQP::Graph PBQPRegAlloc::constructPBQPProblem() { typedef std::vector LIVector; - typedef std::set RegSet; + typedef std::vector RegVector; - // These will store the physical & virtual intervals, respectively. - LIVector physIntervals, virtIntervals; + // This will store the physical intervals for easy reference. + LIVector physIntervals; // Start by clearing the old node <-> live interval mappings & allowed sets li2Node.clear(); node2LI.clear(); allowedSets.clear(); - // Iterate over intervals classifying them as physical or virtual, and - // constructing live interval <-> node number mappings. - for (LiveIntervals::iterator itr = li->begin(), end = li->end(); + // Populate physIntervals, update preg use: + for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); itr != end; ++itr) { - if (itr->second->getNumValNums() != 0) { - DOUT << "Live range has " << itr->second->getNumValNums() << ": " << itr->second << "\n"; - } - if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { physIntervals.push_back(itr->second); mri->setPhysRegUsed(itr->second->reg); } - else { + } - // If we've allocated this virtual register interval a stack slot on a - // previous round then it's not an allocation candidate - if (ignoreSet.find(itr->first) != ignoreSet.end()) - continue; + // Iterate over vreg intervals, construct live interval <-> node number + // mappings. + for (LiveIntervalSet::const_iterator + itr = vregIntervalsToAlloc.begin(), end = vregIntervalsToAlloc.end(); + itr != end; ++itr) { + const LiveInterval *li = *itr; - li2Node[itr->second] = node2LI.size(); - node2LI.push_back(itr->second); - virtIntervals.push_back(itr->second); - } + li2Node[li] = node2LI.size(); + node2LI.push_back(li); } - // Early out if there's no regs to allocate for. - if (virtIntervals.empty()) - return 0; + // Get the set of potential coalesces. + CoalesceMap coalesces; + + if (pbqpCoalescing) { + coalesces = findCoalesces(); + } // Construct a PBQP solver for this problem - pbqp *solver = alloc_pbqp(virtIntervals.size()); + PBQP::Graph problem; + problemNodes.resize(vregIntervalsToAlloc.size()); // Resize allowedSets container appropriately. - allowedSets.resize(virtIntervals.size()); + allowedSets.resize(vregIntervalsToAlloc.size()); // Iterate over virtual register intervals to compute allowed sets... for (unsigned node = 0; node < node2LI.size(); ++node) { @@ -346,38 +578,48 @@ pbqp* PBQPRegAlloc::constructPBQPProblem() { // Grab pointers to the interval and its register class. const LiveInterval *li = node2LI[node]; const TargetRegisterClass *liRC = mri->getRegClass(li->reg); - + // Start by assuming all allocable registers in the class are allowed... - RegSet liAllowed(liRC->allocation_order_begin(*mf), - liRC->allocation_order_end(*mf)); + RegVector liAllowed(liRC->allocation_order_begin(*mf), + liRC->allocation_order_end(*mf)); - // If this range is non-empty then eliminate the physical registers which - // overlap with this range, along with all their aliases. - if (!li->empty()) { - for (LIVector::iterator pItr = physIntervals.begin(), - pEnd = physIntervals.end(); pItr != pEnd; ++pItr) { + // Eliminate the physical registers which overlap with this range, along + // with all their aliases. + for (LIVector::iterator pItr = physIntervals.begin(), + pEnd = physIntervals.end(); pItr != pEnd; ++pItr) { + + if (!li->overlaps(**pItr)) + continue; - if (li->overlaps(**pItr)) { + unsigned pReg = (*pItr)->reg; - unsigned pReg = (*pItr)->reg; + // If we get here then the live intervals overlap, but we're still ok + // if they're coalescable. + if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end()) + continue; - // Remove the overlapping reg... - liAllowed.erase(pReg); + // If we get here then we have a genuine exclusion. - const unsigned *aliasItr = tri->getAliasSet(pReg); + // Remove the overlapping reg... + RegVector::iterator eraseItr = + std::find(liAllowed.begin(), liAllowed.end(), pReg); - if (aliasItr != 0) { - // ...and its aliases. - for (; *aliasItr != 0; ++aliasItr) { - liAllowed.erase(*aliasItr); - } + if (eraseItr != liAllowed.end()) + liAllowed.erase(eraseItr); + + const unsigned *aliasItr = tri->getAliasSet(pReg); + if (aliasItr != 0) { + // ...and its aliases. + for (; *aliasItr != 0; ++aliasItr) { + RegVector::iterator eraseItr = + std::find(liAllowed.begin(), liAllowed.end(), *aliasItr); + + if (eraseItr != liAllowed.end()) { + liAllowed.erase(eraseItr); } - } - } - } // Copy the allowed set into a member vector for use when constructing cost @@ -386,82 +628,140 @@ pbqp* PBQPRegAlloc::constructPBQPProblem() { // Set the spill cost to the interval weight, or epsilon if the // interval weight is zero - PBQPNum spillCost = (li->weight != 0.0) ? - li->weight : std::numeric_limits::min(); + PBQP::PBQPNum spillCost = (li->weight != 0.0) ? + li->weight : std::numeric_limits::min(); // Build a cost vector for this interval. - add_pbqp_nodecosts(solver, node, - buildCostVector(allowedSets[node], spillCost)); + problemNodes[node] = + problem.addNode( + buildCostVector(li->reg, allowedSets[node], coalesces, spillCost)); } + // Now add the cost matrices... for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) { - const LiveInterval *li = node2LI[node1]; - if (li->empty()) - continue; - // Test for live range overlaps and insert interference matrices. for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) { const LiveInterval *li2 = node2LI[node2]; - if (li2->empty()) - continue; + CoalesceMap::const_iterator cmItr = + coalesces.find(RegPair(li->reg, li2->reg)); - if (li->overlaps(*li2)) { - PBQPMatrix *m = - buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]); + PBQP::Matrix *m = 0; - if (m != 0) { - add_pbqp_edgecosts(solver, node1, node2, m); - delete m; - } + if (cmItr != coalesces.end()) { + m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2], + cmItr->second); + } + else if (li->overlaps(*li2)) { + m = buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]); + } + + if (m != 0) { + problem.addEdge(problemNodes[node1], + problemNodes[node2], + *m); + + delete m; } } } + assert(problem.getNumNodes() == allowedSets.size()); +/* + std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, " + << problem.getNumEdges() << " edges.\n"; + + problem.printDot(std::cerr); +*/ // We're done, PBQP problem constructed - return it. - return solver; + return problem; } -bool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) { - +void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, + MachineRegisterInfo* mri) { + int stackSlot = vrm->getStackSlot(spilled->reg); + + if (stackSlot == VirtRegMap::NO_STACK_SLOT) + return; + + const TargetRegisterClass *RC = mri->getRegClass(spilled->reg); + LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC); + + VNInfo *vni; + if (stackInterval.getNumValNums() != 0) + vni = stackInterval.getValNumInfo(0); + else + vni = stackInterval.getNextValue( + SlotIndex(), 0, false, lss->getVNInfoAllocator()); + + LiveInterval &rhsInterval = lis->getInterval(spilled->reg); + stackInterval.MergeRangesInAsValue(rhsInterval, vni); +} + +bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { + // Set to true if we have any spills bool anotherRoundNeeded = false; // Clear the existing allocation. vrm->clearAllVirt(); - + // Iterate over the nodes mapping the PBQP solution to a register assignment. for (unsigned node = 0; node < node2LI.size(); ++node) { - unsigned symReg = node2LI[node]->reg, - allocSelection = get_pbqp_solution(problem, node); + unsigned virtReg = node2LI[node]->reg, + allocSelection = solution.getSelection(problemNodes[node]); + // If the PBQP solution is non-zero it's a physical register... if (allocSelection != 0) { // Get the physical reg, subtracting 1 to account for the spill option. unsigned physReg = allowedSets[node][allocSelection - 1]; + DEBUG(dbgs() << "VREG " << virtReg << " -> " + << tri->getName(physReg) << "\n"); + + assert(physReg != 0); + // Add to the virt reg map and update the used phys regs. - vrm->assignVirt2Phys(symReg, physReg); - mri->setPhysRegUsed(physReg); + vrm->assignVirt2Phys(virtReg, physReg); } // ...Otherwise it's a spill. else { // Make sure we ignore this virtual reg on the next round // of allocation - ignoreSet.insert(node2LI[node]->reg); - - float SSWeight; + vregIntervalsToAlloc.erase(&lis->getInterval(virtReg)); // Insert spill ranges for this live range + const LiveInterval *spillInterval = node2LI[node]; + double oldSpillWeight = spillInterval->weight; SmallVector spillIs; std::vector newSpills = - li->addIntervalsForSpills(*node2LI[node], spillIs, loopInfo, *vrm, - SSWeight); + lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm); + addStackInterval(spillInterval, mri); + + (void) oldSpillWeight; + DEBUG(dbgs() << "VREG " << virtReg << " -> SPILLED (Cost: " + << oldSpillWeight << ", New vregs: "); + + // Copy any newly inserted live intervals into the list of regs to + // allocate. + for (std::vector::const_iterator + itr = newSpills.begin(), end = newSpills.end(); + itr != end; ++itr) { + + assert(!(*itr)->empty() && "Empty spill range."); + + DEBUG(dbgs() << (*itr)->reg << " "); + + vregIntervalsToAlloc.insert(*itr); + } + + DEBUG(dbgs() << ")\n"); // We need another round if spill intervals were added. anotherRoundNeeded |= !newSpills.empty(); @@ -471,54 +771,139 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) { return !anotherRoundNeeded; } +void PBQPRegAlloc::finalizeAlloc() const { + typedef LiveIntervals::iterator LIIterator; + typedef LiveInterval::Ranges::const_iterator LRIterator; + + // First allocate registers for the empty intervals. + for (LiveIntervalSet::const_iterator + itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end(); + itr != end; ++itr) { + LiveInterval *li = *itr; + + unsigned physReg = vrm->getRegAllocPref(li->reg); + + if (physReg == 0) { + const TargetRegisterClass *liRC = mri->getRegClass(li->reg); + physReg = *liRC->allocation_order_begin(*mf); + } + + vrm->assignVirt2Phys(li->reg, physReg); + } + + // Finally iterate over the basic blocks to compute and set the live-in sets. + SmallVector liveInMBBs; + MachineBasicBlock *entryMBB = &*mf->begin(); + + for (LIIterator liItr = lis->begin(), liEnd = lis->end(); + liItr != liEnd; ++liItr) { + + const LiveInterval *li = liItr->second; + unsigned reg = 0; + + // Get the physical register for this interval + if (TargetRegisterInfo::isPhysicalRegister(li->reg)) { + reg = li->reg; + } + else if (vrm->isAssignedReg(li->reg)) { + reg = vrm->getPhys(li->reg); + } + else { + // Ranges which are assigned a stack slot only are ignored. + continue; + } + + if (reg == 0) { + // Filter out zero regs - they're for intervals that were spilled. + continue; + } + + // Iterate over the ranges of the current interval... + for (LRIterator lrItr = li->begin(), lrEnd = li->end(); + lrItr != lrEnd; ++lrItr) { + + // Find the set of basic blocks which this range is live into... + if (lis->findLiveInMBBs(lrItr->start, lrItr->end, liveInMBBs)) { + // And add the physreg for this interval to their live-in sets. + for (unsigned i = 0; i < liveInMBBs.size(); ++i) { + if (liveInMBBs[i] != entryMBB) { + if (!liveInMBBs[i]->isLiveIn(reg)) { + liveInMBBs[i]->addLiveIn(reg); + } + } + } + liveInMBBs.clear(); + } + } + } + +} + bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { - + mf = &MF; tm = &mf->getTarget(); tri = tm->getRegisterInfo(); - mri = &mf->getRegInfo(); + tii = tm->getInstrInfo(); + mri = &mf->getRegInfo(); - li = &getAnalysis(); + lis = &getAnalysis(); + lss = &getAnalysis(); loopInfo = &getAnalysis(); - std::auto_ptr vrmAutoPtr(new VirtRegMap(*mf)); - vrm = vrmAutoPtr.get(); + vrm = &getAnalysis(); + + DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n"); // Allocator main loop: - // + // // * Map current regalloc problem to a PBQP problem // * Solve the PBQP problem // * Map the solution back to a register allocation // * Spill if necessary - // + // // This process is continued till no more spills are generated. - bool regallocComplete = false; - - // Calculate spill costs for intervals - calcSpillCosts(); - - while (!regallocComplete) { - pbqp *problem = constructPBQPProblem(); - - // Fast out if there's no problem to solve. - if (problem == 0) - return true; - - solve_pbqp(problem); - - regallocComplete = mapPBQPToRegAlloc(problem); - - free_pbqp(problem); + // Find the vreg intervals in need of allocation. + findVRegIntervalsToAlloc(); + + // If there are non-empty intervals allocate them using pbqp. + if (!vregIntervalsToAlloc.empty()) { + + bool pbqpAllocComplete = false; + unsigned round = 0; + + while (!pbqpAllocComplete) { + DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); + + PBQP::Graph problem = constructPBQPProblem(); + PBQP::Solution solution = + PBQP::HeuristicSolver::solve(problem); + + pbqpAllocComplete = mapPBQPToRegAlloc(solution); + + ++round; + } } - ignoreSet.clear(); + // Finalise allocation, allocate empty ranges. + finalizeAlloc(); + + vregIntervalsToAlloc.clear(); + emptyVRegIntervals.clear(); + li2Node.clear(); + node2LI.clear(); + allowedSets.clear(); + problemNodes.clear(); + + DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); + + // Run rewriter + std::auto_ptr rewriter(createVirtRegRewriter()); - std::auto_ptr spiller(createSpiller()); + rewriter->runOnMachineFunction(*mf, *vrm, lis); - spiller->runOnMachineFunction(*mf, *vrm); - - return true; + return true; } FunctionPass* llvm::createPBQPRegisterAllocator() {