diff options
author | Lang Hames <lhames@gmail.com> | 2008-11-16 12:12:54 +0000 |
---|---|---|
committer | Lang Hames <lhames@gmail.com> | 2008-11-16 12:12:54 +0000 |
commit | 27601ef8325f85b9677b55e3e2ca1a1368d8eee5 (patch) | |
tree | bc69c0bbbfbe6ef9cddbace90f8d6f63c70b40de /lib/CodeGen/RegAllocPBQP.cpp | |
parent | 1a6111f32dcc1f4b0bc5993a09af4adb65a23b3f (diff) | |
download | external_llvm-27601ef8325f85b9677b55e3e2ca1a1368d8eee5.zip external_llvm-27601ef8325f85b9677b55e3e2ca1a1368d8eee5.tar.gz external_llvm-27601ef8325f85b9677b55e3e2ca1a1368d8eee5.tar.bz2 |
Big PBQP allocator update. Adds coalescing support, stack slot coloring, several bug-fixes.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59414 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/CodeGen/RegAllocPBQP.cpp')
-rw-r--r-- | lib/CodeGen/RegAllocPBQP.cpp | 617 |
1 files changed, 478 insertions, 139 deletions
diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index 8f3284d..e9271ef 100644 --- a/lib/CodeGen/RegAllocPBQP.cpp +++ b/lib/CodeGen/RegAllocPBQP.cpp @@ -32,20 +32,15 @@ // //===----------------------------------------------------------------------===// -// 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 "VirtRegMap.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/RegAllocRegistry.h" +#include "llvm/CodeGen/RegisterCoalescer.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/Target/TargetMachine.h" @@ -63,7 +58,6 @@ static RegisterRegAlloc registerPBQPRepAlloc("pbqp", "PBQP register allocator", createPBQPRegisterAllocator); - namespace { //! @@ -86,7 +80,11 @@ namespace { //! PBQP analysis usage. virtual void getAnalysisUsage(AnalysisUsage &au) const { au.addRequired<LiveIntervals>(); + au.addRequiredTransitive<RegisterCoalescer>(); + au.addRequired<LiveStacks>(); + au.addPreserved<LiveStacks>(); au.addRequired<MachineLoopInfo>(); + au.addPreserved<MachineLoopInfo>(); MachineFunctionPass::getAnalysisUsage(au); } @@ -98,7 +96,11 @@ namespace { typedef std::vector<const LiveInterval*> Node2LIMap; typedef std::vector<unsigned> AllowedSet; typedef std::vector<AllowedSet> AllowedSetMap; - typedef std::set<unsigned> IgnoreSet; + typedef std::set<unsigned> RegSet; + typedef std::pair<unsigned, unsigned> RegPair; + typedef std::map<RegPair, PBQPNum> CoalesceMap; + + typedef std::set<LiveInterval*> LiveIntervalSet; MachineFunction *mf; const TargetMachine *tm; @@ -107,17 +109,22 @@ namespace { const MachineLoopInfo *loopInfo; MachineRegisterInfo *mri; - LiveIntervals *li; + LiveIntervals *lis; + LiveStacks *lss; VirtRegMap *vrm; LI2NodeMap li2Node; Node2LIMap node2LI; AllowedSetMap allowedSets; - IgnoreSet ignoreSet; + LiveIntervalSet vregIntervalsToAlloc, + emptyVRegIntervals; + //! Builds a PBQP cost vector. - template <typename Container> - PBQPVector* buildCostVector(const Container &allowed, + template <typename RegContainer> + PBQPVector* buildCostVector(unsigned vReg, + const RegContainer &allowed, + const CoalesceMap &cealesces, PBQPNum spillCost) const; //! \brief Builds a PBQP interference matrix. @@ -128,29 +135,28 @@ namespace { //! 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 <typename Container> - PBQPMatrix* buildInterferenceMatrix(const Container &allowed1, - const Container &allowed2) const; + template <typename RegContainer> + PBQPMatrix* 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 <typename Container> - PBQPMatrix* buildCoalescingMatrix(const Container &allowed1, - const Container &allowed2, + template <typename RegContainer> + PBQPMatrix* buildCoalescingMatrix(const RegContainer &allowed1, + const RegContainer &allowed2, PBQPNum cBenefit) const; - //! \brief Helper function for constructInitialPBQPProblem(). + //! \brief Finds coalescing opportunities and returns them as a map. //! - //! This function iterates over the Function we are about to allocate for - //! and computes spill costs. - void calcSpillCosts(); + //! Any entries in the map are guaranteed coalescable, even if their + //! corresponding live intervals overlap. + CoalesceMap findCoalesces(); - //! \brief Scans the MachineFunction being allocated to find coalescing - // opportunities. - void findCoalescingOpportunities(); + //! \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. @@ -158,33 +164,64 @@ namespace { //! @return a PBQP solver object for the register allocation problem. pbqp* 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, float &weight); + //! \brief Given a solved PBQP problem maps this solution back to a register //! assignment. bool mapPBQPToRegAlloc(pbqp *problem); + //! \brief Postprocessing before final spilling. Sets basic block "live in" + //! variables. + void finalizeAlloc() const; + }; char PBQPRegAlloc::ID = 0; } -template <typename Container> -PBQPVector* PBQPRegAlloc::buildCostVector(const Container &allowed, +template <typename RegContainer> +PBQPVector* PBQPRegAlloc::buildCostVector(unsigned vReg, + const RegContainer &allowed, + const CoalesceMap &coalesces, 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); (*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; + + // We have a coalesce - insert the benefit. + (*v)[ai + 1] = -cmItr->second; + } + return v; } -template <typename Container> +template <typename RegContainer> PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( - const Container &allowed1, const Container &allowed2) const { + 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 @@ -210,14 +247,14 @@ PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( unsigned ri = 1; // Iterate over allowed sets, insert infinities where required. - for (ContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); + 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; @@ -245,100 +282,262 @@ PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( return m; } -void PBQPRegAlloc::calcSpillCosts() { +template <typename RegContainer> +PBQPMatrix* PBQPRegAlloc::buildCoalescingMatrix( + const RegContainer &allowed1, const RegContainer &allowed2, + 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. + PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1); + + // 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; + } + + ++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; - // 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(); + // 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; - for (unsigned opNo = 0; opNo < instr->getNumOperands(); ++opNo) { + // If this isn't a copy then continue to the next instruction. + if (!tii->isMoveInstr(*instr, srcReg, dstReg)) + continue; - const MachineOperand &mo = instr->getOperand(opNo); + // If the registers are already the same our job is nice and easy. + if (dstReg == srcReg) + continue; - // We're not interested in non-registers... - if (!mo.isReg()) - continue; - - unsigned moReg = mo.getReg(); + bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg), + dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg); - // ...Or invalid registers... - if (moReg == 0) + // 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); + + 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(srcRegClass->allocation_order_begin(*mf), + srcRegClass->allocation_order_end(*mf), srcReg) == + srcRegClass->allocation_order_end(*mf)) continue; + } - // ...Or physical registers... - if (TargetRegisterInfo::isPhysicalRegister(moReg)) + if (dstRegIsPhysical) { + if (std::find(dstRegClass->allocation_order_begin(*mf), + dstRegClass->allocation_order_end(*mf), dstReg) == + dstRegClass->allocation_order_end(*mf)) continue; + } - assert ((mo.isUse() || mo.isDef()) && - "Not a use, not a def, what is it?"); + // 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 def that kills the coalescing opportunity then + // record it and break from the loop. + if (dstLI->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); + // If we have a bad def give up, continue to the next instruction. + if (badDef) + continue; + + // 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)->copy == instr) + continue; + + if (srcLI->liveAt((*vniItr)->def)) { + badDef = true; + break; + } + } + + // 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() { typedef std::vector<const LiveInterval*> LIVector; - typedef std::set<unsigned> RegSet; + typedef std::vector<unsigned> 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(findCoalesces()); // Construct a PBQP solver for this problem - pbqp *solver = alloc_pbqp(virtIntervals.size()); + pbqp *solver = alloc_pbqp(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) { @@ -348,36 +547,46 @@ pbqp* PBQPRegAlloc::constructPBQPProblem() { 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)); - - // 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) { + RegVector liAllowed(liRC->allocation_order_begin(*mf), + liRC->allocation_order_end(*mf)); - if (li->overlaps(**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) { - unsigned pReg = (*pItr)->reg; + if (!li->overlaps(**pItr)) + continue; - // Remove the overlapping reg... - liAllowed.erase(pReg); + unsigned pReg = (*pItr)->reg; - const unsigned *aliasItr = tri->getAliasSet(pReg); + // 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; - if (aliasItr != 0) { - // ...and its aliases. - for (; *aliasItr != 0; ++aliasItr) { - liAllowed.erase(*aliasItr); - } + // If we get here then we have a genuine exclusion. + // Remove the overlapping reg... + RegVector::iterator eraseItr = + std::find(liAllowed.begin(), liAllowed.end(), pReg); + + 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 @@ -391,33 +600,36 @@ pbqp* PBQPRegAlloc::constructPBQPProblem() { // Build a cost vector for this interval. add_pbqp_nodecosts(solver, node, - buildCostVector(allowedSets[node], spillCost)); + 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]); + PBQPMatrix *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) { + add_pbqp_edgecosts(solver, node1, node2, m); + delete m; } } } @@ -426,6 +638,25 @@ pbqp* PBQPRegAlloc::constructPBQPProblem() { return solver; } +void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, float &weight) { + int stackSlot = vrm->getStackSlot(spilled->reg); + + if (stackSlot == VirtRegMap::NO_STACK_SLOT) + return; + + LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot); + stackInterval.weight += weight; + + VNInfo *vni; + if (stackInterval.getNumValNums() != 0) + vni = stackInterval.getValNumInfo(0); + else + vni = stackInterval.getNextValue(-0U, 0, lss->getVNInfoAllocator()); + + LiveInterval &rhsInterval = lis->getInterval(spilled->reg); + stackInterval.MergeRangesInAsValue(rhsInterval, vni); +} + bool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) { // Set to true if we have any spills @@ -436,7 +667,7 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) { // 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, + unsigned virtReg = node2LI[node]->reg, allocSelection = get_pbqp_solution(problem, node); // If the PBQP solution is non-zero it's a physical register... @@ -444,24 +675,48 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) { // Get the physical reg, subtracting 1 to account for the spill option. unsigned physReg = allowedSets[node][allocSelection - 1]; + DOUT << "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); + vregIntervalsToAlloc.erase(&lis->getInterval(virtReg)); - float SSWeight; + float ssWeight; // Insert spill ranges for this live range + const LiveInterval *spillInterval = node2LI[node]; + double oldSpillWeight = spillInterval->weight; SmallVector<LiveInterval*, 8> spillIs; std::vector<LiveInterval*> newSpills = - li->addIntervalsForSpills(*node2LI[node], spillIs, loopInfo, *vrm, - SSWeight); + lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm, + ssWeight); + addStackInterval(spillInterval, ssWeight); + + DOUT << "VREG " << virtReg << " -> SPILLED (Cost: " + << oldSpillWeight << ", New vregs: "; + + // Copy any newly inserted live intervals into the list of regs to + // allocate. + for (std::vector<LiveInterval*>::const_iterator + itr = newSpills.begin(), end = newSpills.end(); + itr != end; ++itr) { + + assert(!(*itr)->empty() && "Empty spill range."); + + DOUT << (*itr)->reg << " "; + + vregIntervalsToAlloc.insert(*itr); + } + + DOUT << ")\n"; // We need another round if spill intervals were added. anotherRoundNeeded |= !newSpills.empty(); @@ -471,19 +726,86 @@ 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::iterator + itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end(); + itr != end; ++itr) { + LiveInterval *li = *itr; + + unsigned physReg = li->preference; + + 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<MachineBasicBlock*, 8> 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; + } + + // 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(); + tii = tm->getInstrInfo(); mri = &mf->getRegInfo(); - li = &getAnalysis<LiveIntervals>(); + lis = &getAnalysis<LiveIntervals>(); + lss = &getAnalysis<LiveStacks>(); loopInfo = &getAnalysis<MachineLoopInfo>(); std::auto_ptr<VirtRegMap> vrmAutoPtr(new VirtRegMap(*mf)); vrm = vrmAutoPtr.get(); + DOUT << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n"; + // Allocator main loop: // // * Map current regalloc problem to a PBQP problem @@ -493,31 +815,49 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { // // This process is continued till no more spills are generated. - bool regallocComplete = false; + // Find the vreg intervals in need of allocation. + findVRegIntervalsToAlloc(); - // Calculate spill costs for intervals - calcSpillCosts(); + // If there aren't any then we're done here. + if (vregIntervalsToAlloc.empty() && emptyVRegIntervals.empty()) + return true; - while (!regallocComplete) { - pbqp *problem = constructPBQPProblem(); + // If there are non-empty intervals allocate them using pbqp. + if (!vregIntervalsToAlloc.empty()) { + + bool pbqpAllocComplete = false; + unsigned round = 0; + + while (!pbqpAllocComplete) { + DOUT << " PBQP Regalloc round " << round << ":\n"; + + pbqp *problem = constructPBQPProblem(); - // Fast out if there's no problem to solve. - if (problem == 0) - return true; - - solve_pbqp(problem); + solve_pbqp(problem); - regallocComplete = mapPBQPToRegAlloc(problem); + pbqpAllocComplete = mapPBQPToRegAlloc(problem); + + free_pbqp(problem); - free_pbqp(problem); + ++round; + } } - ignoreSet.clear(); + // Finalise allocation, allocate empty ranges. + finalizeAlloc(); - std::auto_ptr<Spiller> spiller(createSpiller()); + vregIntervalsToAlloc.clear(); + emptyVRegIntervals.clear(); + li2Node.clear(); + node2LI.clear(); + allowedSets.clear(); + DOUT << "Post alloc VirtRegMap:\n" << *vrm << "\n"; + + // Run spiller + std::auto_ptr<Spiller> spiller(createSpiller()); spiller->runOnMachineFunction(*mf, *vrm); - + return true; } @@ -527,4 +867,3 @@ FunctionPass* llvm::createPBQPRegisterAllocator() { #undef DEBUG_TYPE - |