X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocPBQP.cpp;h=862ce00e1c8b2f108b56f701983ecbf566b7322a;hb=6248fa45299a9e54aac84b3296c02c44ddec84e8;hp=8f3284d22068fb8ef67b3ea38c32516c5d0eb792;hpb=56c523c63b2b5d95ed61c79e1efe9de5465a7d25;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index 8f3284d2206..862ce00e1c8 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,36 +26,30 @@ // 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 "VirtRegMap.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/RegAllocRegistry.h" +#include "VirtRegRewriter.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; @@ -63,7 +57,6 @@ static RegisterRegAlloc registerPBQPRepAlloc("pbqp", "PBQP register allocator", createPBQPRegisterAllocator); - namespace { //! @@ -74,7 +67,7 @@ namespace { public: static char ID; - + //! Construct a PBQP register allocator. PBQPRegAlloc() : MachineFunctionPass((intptr_t)&ID) {} @@ -84,10 +77,16 @@ namespace { } //! PBQP analysis usage. - virtual void getAnalysisUsage(AnalysisUsage &au) const { - au.addRequired(); - au.addRequired(); - MachineFunctionPass::getAnalysisUsage(au); + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addRequiredTransitive(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + MachineFunctionPass::getAnalysisUsage(AU); } //! Perform register allocation @@ -98,7 +97,11 @@ 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; MachineFunction *mf; const TargetMachine *tm; @@ -107,17 +110,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 - PBQPVector* buildCostVector(const Container &allowed, + template + PBQPVector* buildCostVector(unsigned vReg, + const RegContainer &allowed, + const CoalesceMap &cealesces, PBQPNum spillCost) const; //! \brief Builds a PBQP interference matrix. @@ -128,29 +136,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 - PBQPMatrix* buildInterferenceMatrix(const Container &allowed1, - const Container &allowed2) const; + template + 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 - PBQPMatrix* buildCoalescingMatrix(const Container &allowed1, - const Container &allowed2, + template + 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,9 +165,17 @@ 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,MachineRegisterInfo* mri); + //! \brief Given a solved PBQP problem maps this solution back to a register //! assignment. - bool mapPBQPToRegAlloc(pbqp *problem); + bool mapPBQPToRegAlloc(pbqp *problem); + + //! \brief Postprocessing before final spilling. Sets basic block "live in" + //! variables. + void finalizeAlloc() const; }; @@ -168,23 +183,46 @@ namespace { } -template -PBQPVector* PBQPRegAlloc::buildCostVector(const Container &allowed, +template +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 +template 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 @@ -195,7 +233,7 @@ PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( // 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); - + // 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,17 +245,17 @@ 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; @@ -245,100 +283,262 @@ PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( return m; } -void PBQPRegAlloc::calcSpillCosts() { +template +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, 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; + + bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg), + dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg); + + // 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); - for (unsigned opNo = 0; opNo < instr->getNumOperands(); ++opNo) { + const TargetRegisterClass *dstRegClass = dstRegIsPhysical ? + tri->getPhysicalRegisterRegClass(dstReg) : mri->getRegClass(dstReg); - const MachineOperand &mo = instr->getOperand(opNo); + if (srcRegClass != dstRegClass) + continue; - // We're not interested in non-registers... - if (!mo.isReg()) + // 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; - - unsigned moReg = mo.getReg(); + } - // ...Or invalid registers... - if (moReg == 0) + if (dstRegIsPhysical) { + if (std::find(dstRegClass->allocation_order_begin(*mf), + dstRegClass->allocation_order_end(*mf), dstReg) == + dstRegClass->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 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)->copy == instr) + continue; - //... Just the virtual registers. We treat loads and stores as equal. - li->getInterval(moReg).weight += powf(10.0f, loopDepth); + 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 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(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) { @@ -346,38 +546,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,57 +596,80 @@ 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) ? + 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)); + 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; } } } // We're done, PBQP problem constructed - return it. - return solver; + return solver; +} + +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(0, 0, false, 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 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, + 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 +677,45 @@ 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); - - 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); + + DOUT << "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."); + + DOUT << (*itr)->reg << " "; + + vregIntervalsToAlloc.insert(*itr); + } + + DOUT << ")\n"; // We need another round if spill intervals were added. anotherRoundNeeded |= !newSpills.empty(); @@ -471,54 +725,144 @@ 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; + } + + // Ignore unallocated vregs: + if (reg == 0) { + 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(); + lis = &getAnalysis(); + lss = &getAnalysis(); loopInfo = &getAnalysis(); - std::auto_ptr vrmAutoPtr(new VirtRegMap(*mf)); - vrm = vrmAutoPtr.get(); + vrm = &getAnalysis(); + + DEBUG(errs() << "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 aren't any then we're done here. + if (vregIntervalsToAlloc.empty() && emptyVRegIntervals.empty()) + return true; + + // 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(); + + solve_pbqp(problem); + + pbqpAllocComplete = mapPBQPToRegAlloc(problem); + + free_pbqp(problem); + + ++round; + } } - ignoreSet.clear(); + // Finalise allocation, allocate empty ranges. + finalizeAlloc(); + + vregIntervalsToAlloc.clear(); + emptyVRegIntervals.clear(); + li2Node.clear(); + node2LI.clear(); + allowedSets.clear(); - std::auto_ptr spiller(createSpiller()); + DOUT << "Post alloc VirtRegMap:\n" << *vrm << "\n"; - spiller->runOnMachineFunction(*mf, *vrm); - - return true; + // Run rewriter + std::auto_ptr rewriter(createVirtRegRewriter()); + + rewriter->runOnMachineFunction(*mf, *vrm, lis); + + return true; } FunctionPass* llvm::createPBQPRegisterAllocator() { @@ -527,4 +871,3 @@ FunctionPass* llvm::createPBQPRegisterAllocator() { #undef DEBUG_TYPE -