X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocPBQP.cpp;h=d0db26b2089f6df1304d408d99fa04e6f71f159d;hb=5fa2d458af8522a0fc3c6c93227d8cb3c0dc2862;hp=107d277f4de703fa0460f65106b1af3d9fbefd3d;hpb=17a82eaeb6339b184acb2f8bf0f314d69ad2e1d3;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index 107d277f4de..d0db26b2089 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,504 +26,614 @@ // 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 "Spiller.h" #include "VirtRegMap.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/RegAllocRegistry.h" +#include "RegisterCoalescer.h" +#include "llvm/Module.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/LiveRangeEdit.h" +#include "llvm/CodeGen/LiveStackAnalysis.h" +#include "llvm/CodeGen/RegAllocPBQP.h" +#include "llvm/CodeGen/MachineDominators.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/PBQP/HeuristicSolver.h" +#include "llvm/CodeGen/PBQP/Graph.h" +#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h" +#include "llvm/CodeGen/RegAllocRegistry.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include #include -#include #include +#include #include -#include using namespace llvm; static RegisterRegAlloc -registerPBQPRepAlloc("pbqp", " PBQP register allocator", - createPBQPRegisterAllocator); +registerPBQPRepAlloc("pbqp", "PBQP register allocator", + createDefaultPBQPRegisterAllocator); + +static cl::opt +pbqpCoalescing("pbqp-coalescing", + cl::desc("Attempt coalescing during PBQP register allocation."), + cl::init(false), cl::Hidden); +#ifndef NDEBUG +static cl::opt +pbqpDumpGraphs("pbqp-dump-graphs", + cl::desc("Dump graphs for each function/round in the compilation unit."), + cl::init(false), cl::Hidden); +#endif 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 { - public: - - static char ID; - - //! Construct a PBQP register allocator. - PBQPRegAlloc() : MachineFunctionPass((intptr_t)&ID) {} - - //! Return the pass name. - virtual const char* getPassName() const throw() { - return "PBQP Register Allocator"; - } +/// +/// PBQP based allocators solve the register allocation problem by mapping +/// register allocation problems to Partitioned Boolean Quadratic +/// Programming problems. +class RegAllocPBQP : public MachineFunctionPass { +public: + + static char ID; + + /// Construct a PBQP register allocator. + RegAllocPBQP(std::auto_ptr b, char *cPassID=0) + : MachineFunctionPass(ID), builder(b), customPassID(cPassID) { + initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); + initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); + initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); + initializeLiveStacksPass(*PassRegistry::getPassRegistry()); + initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); + initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); + } - //! PBQP analysis usage. - virtual void getAnalysisUsage(AnalysisUsage &au) const { - au.addRequired(); - au.addRequired(); - MachineFunctionPass::getAnalysisUsage(au); - } + /// Return the pass name. + virtual const char* getPassName() const { + return "PBQP Register Allocator"; + } - //! Perform register allocation - virtual bool runOnMachineFunction(MachineFunction &MF); - - private: - typedef std::map LI2NodeMap; - typedef std::vector Node2LIMap; - typedef std::vector AllowedSet; - typedef std::vector AllowedSetMap; - typedef std::set IgnoreSet; - - MachineFunction *mf; - const TargetMachine *tm; - const TargetRegisterInfo *tri; - const TargetInstrInfo *tii; - const MachineLoopInfo *loopInfo; - MachineRegisterInfo *mri; - - LiveIntervals *li; - 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 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 - 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 function 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); - - }; - - char PBQPRegAlloc::ID = 0; -} + /// PBQP analysis usage. + virtual void getAnalysisUsage(AnalysisUsage &au) const; + /// Perform register allocation + virtual bool runOnMachineFunction(MachineFunction &MF); -template -PBQPVector* PBQPRegAlloc::buildCostVector(const Container &allowed, - PBQPNum spillCost) const { +private: - // Allocate vector. Additional element (0th) used for spill option - PBQPVector *v = new PBQPVector(allowed.size() + 1); + typedef std::map LI2NodeMap; + typedef std::vector Node2LIMap; + typedef std::vector AllowedSet; + typedef std::vector AllowedSetMap; + typedef std::pair RegPair; + typedef std::map CoalesceMap; + typedef std::vector NodeVector; + typedef std::set RegSet; - (*v)[0] = spillCost; - return v; -} + std::auto_ptr builder; -template -PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( - const Container &allowed1, const Container &allowed2) const { - - typedef typename Container::const_iterator ContainerIterator; - - // Construct a PBQP matrix representing the cost of allocation options. The - // rows and columns correspond to the allocation options for the two live - // intervals. Elements will be infinite where corresponding registers alias, - // since we cannot allocate aliasing registers to interfering live intervals. - // All other elements (non-aliasing combinations) will have zero cost. Note - // 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); - - // 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 - // same class). The term "overlapping" is used advisedly: sets which do not - // intersect, but contain registers which alias, will have non-zero matrices. - // We optimize zero matrices away to improve solver speed. - 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 allowed sets, insert infinities where required. - for (ContainerIterator 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(); - 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(); - isZeroMatrix = false; - } + char *customPassID; - ++ci; - } + MachineFunction *mf; + const TargetMachine *tm; + const TargetRegisterInfo *tri; + const TargetInstrInfo *tii; + const MachineLoopInfo *loopInfo; + MachineRegisterInfo *mri; - ++ri; - } + std::auto_ptr spiller; + LiveIntervals *lis; + LiveStacks *lss; + VirtRegMap *vrm; - // If this turns out to be a zero matrix... - if (isZeroMatrix) { - // free it and return null. - delete m; - return 0; - } + RegSet vregsToAlloc, emptyIntervalVRegs; - // ...otherwise return the cost matrix. - return m; + /// \brief Finds the initial set of vreg intervals to allocate. + void findVRegIntervalsToAlloc(); + + /// \brief Given a solved PBQP problem maps this solution back to a register + /// assignment. + bool mapPBQPToRegAlloc(const PBQPRAProblem &problem, + const PBQP::Solution &solution); + + /// \brief Postprocessing before final spilling. Sets basic block "live in" + /// variables. + void finalizeAlloc() const; + +}; + +char RegAllocPBQP::ID = 0; + +} // End anonymous namespace. + +unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node) const { + Node2VReg::const_iterator vregItr = node2VReg.find(node); + assert(vregItr != node2VReg.end() && "No vreg for node."); + return vregItr->second; } -void PBQPRegAlloc::calcSpillCosts() { +PBQP::Graph::NodeItr PBQPRAProblem::getNodeForVReg(unsigned vreg) const { + VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg); + assert(nodeItr != vreg2Node.end() && "No node for vreg."); + return nodeItr->second; - // 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(); - bbItr != bbEnd; ++bbItr) { +} - const MachineBasicBlock *mbb = &*bbItr; - float loopDepth = loopInfo->getLoopDepth(mbb); +const PBQPRAProblem::AllowedSet& + PBQPRAProblem::getAllowedSet(unsigned vreg) const { + AllowedSetMap::const_iterator allowedSetItr = allowedSets.find(vreg); + assert(allowedSetItr != allowedSets.end() && "No pregs for vreg."); + const AllowedSet &allowedSet = allowedSetItr->second; + return allowedSet; +} - for (MachineBasicBlock::const_iterator - iItr = mbb->begin(), iEnd = mbb->end(); iItr != iEnd; ++iItr) { +unsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const { + assert(isPRegOption(vreg, option) && "Not a preg option."); - const MachineInstr *instr = &*iItr; + const AllowedSet& allowedSet = getAllowedSet(vreg); + assert(option <= allowedSet.size() && "Option outside allowed set."); + return allowedSet[option - 1]; +} - for (unsigned opNo = 0; opNo < instr->getNumOperands(); ++opNo) { +std::auto_ptr PBQPBuilder::build(MachineFunction *mf, + const LiveIntervals *lis, + const MachineLoopInfo *loopInfo, + const RegSet &vregs) { - const MachineOperand &mo = instr->getOperand(opNo); + typedef std::vector LIVector; + LiveIntervals *LIS = const_cast(lis); + MachineRegisterInfo *mri = &mf->getRegInfo(); + const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo(); - // We're not interested in non-registers... - if (!mo.isReg()) - continue; - - unsigned moReg = mo.getReg(); + std::auto_ptr p(new PBQPRAProblem()); + PBQP::Graph &g = p->getGraph(); + RegSet pregs; - // ...Or invalid registers... - if (moReg == 0) - continue; + // Collect the set of preg intervals, record that they're used in the MF. + for (unsigned Reg = 1, e = tri->getNumRegs(); Reg != e; ++Reg) { + if (mri->def_empty(Reg)) + continue; + pregs.insert(Reg); + mri->setPhysRegUsed(Reg); + } - // ...Or physical registers... - if (TargetRegisterInfo::isPhysicalRegister(moReg)) - continue; + BitVector reservedRegs = tri->getReservedRegs(*mf); + + // Iterate over vregs. + for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end(); + vregItr != vregEnd; ++vregItr) { + unsigned vreg = *vregItr; + const TargetRegisterClass *trc = mri->getRegClass(vreg); + LiveInterval *vregLI = &LIS->getInterval(vreg); + + // Record any overlaps with regmask operands. + BitVector regMaskOverlaps(tri->getNumRegs()); + LIS->checkRegMaskInterference(*vregLI, regMaskOverlaps); + + // Compute an initial allowed set for the current vreg. + typedef std::vector VRAllowed; + VRAllowed vrAllowed; + ArrayRef rawOrder = trc->getRawAllocationOrder(*mf); + for (unsigned i = 0; i != rawOrder.size(); ++i) { + unsigned preg = rawOrder[i]; + if (reservedRegs.test(preg)) + continue; - assert ((mo.isUse() || mo.isDef()) && - "Not a use, not a def, what is it?"); + // vregLI crosses a regmask operand that clobbers preg. + if (!regMaskOverlaps.empty() && !regMaskOverlaps.test(preg)) + continue; - //... Just the virtual registers. We treat loads and stores as equal. - li->getInterval(moReg).weight += powf(10.0f, loopDepth); + // vregLI overlaps fixed regunit interference. + bool Interference = false; + for (MCRegUnitIterator Units(preg, tri); Units.isValid(); ++Units) { + if (vregLI->overlaps(LIS->getRegUnit(*Units))) { + Interference = true; + break; + } } + if (Interference) + continue; + // preg is usable for this virtual register. + vrAllowed.push_back(preg); } - } + // Construct the node. + PBQP::Graph::NodeItr node = + g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0)); -} + // Record the mapping and allowed set in the problem. + p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end()); -pbqp* PBQPRegAlloc::constructPBQPProblem() { + PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ? + vregLI->weight : std::numeric_limits::min(); - typedef std::vector LIVector; - typedef std::set RegSet; + addSpillCosts(g.getNodeCosts(node), spillCost); + } - // These will store the physical & virtual intervals, respectively. - LIVector physIntervals, virtIntervals; + for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end(); + vr1Itr != vrEnd; ++vr1Itr) { + unsigned vr1 = *vr1Itr; + const LiveInterval &l1 = lis->getInterval(vr1); + const PBQPRAProblem::AllowedSet &vr1Allowed = p->getAllowedSet(vr1); + + for (RegSet::const_iterator vr2Itr = llvm::next(vr1Itr); + vr2Itr != vrEnd; ++vr2Itr) { + unsigned vr2 = *vr2Itr; + const LiveInterval &l2 = lis->getInterval(vr2); + const PBQPRAProblem::AllowedSet &vr2Allowed = p->getAllowedSet(vr2); + + assert(!l2.empty() && "Empty interval in vreg set?"); + if (l1.overlaps(l2)) { + PBQP::Graph::EdgeItr edge = + g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2), + PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0)); + + addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri); + } + } + } - // Start by clearing the old node <-> live interval mappings & allowed sets - li2Node.clear(); - node2LI.clear(); - allowedSets.clear(); + return p; +} - // 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(); - itr != end; ++itr) { +void PBQPBuilder::addSpillCosts(PBQP::Vector &costVec, + PBQP::PBQPNum spillCost) { + costVec[0] = spillCost; +} - if (itr->second->getNumValNums() != 0) { - DOUT << "Live range has " << itr->second->getNumValNums() << ": " << itr->second << "\n"; - } +void PBQPBuilder::addInterferenceCosts( + PBQP::Matrix &costMat, + const PBQPRAProblem::AllowedSet &vr1Allowed, + const PBQPRAProblem::AllowedSet &vr2Allowed, + const TargetRegisterInfo *tri) { + assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch."); + assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch."); - if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { - physIntervals.push_back(itr->second); - mri->setPhysRegUsed(itr->second->reg); - } - else { + for (unsigned i = 0; i != vr1Allowed.size(); ++i) { + unsigned preg1 = vr1Allowed[i]; - // 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; + for (unsigned j = 0; j != vr2Allowed.size(); ++j) { + unsigned preg2 = vr2Allowed[j]; - li2Node[itr->second] = node2LI.size(); - node2LI.push_back(itr->second); - virtIntervals.push_back(itr->second); + if (tri->regsOverlap(preg1, preg2)) { + costMat[i + 1][j + 1] = std::numeric_limits::infinity(); + } } } +} - // Early out if there's no regs to allocate for. - if (virtIntervals.empty()) - return 0; +std::auto_ptr PBQPBuilderWithCoalescing::build( + MachineFunction *mf, + const LiveIntervals *lis, + const MachineLoopInfo *loopInfo, + const RegSet &vregs) { - // Construct a PBQP solver for this problem - pbqp *solver = alloc_pbqp(virtIntervals.size()); + std::auto_ptr p = PBQPBuilder::build(mf, lis, loopInfo, vregs); + PBQP::Graph &g = p->getGraph(); - // Resize allowedSets container appropriately. - allowedSets.resize(virtIntervals.size()); + const TargetMachine &tm = mf->getTarget(); + CoalescerPair cp(*tm.getRegisterInfo()); - // Iterate over virtual register intervals to compute allowed sets... - for (unsigned node = 0; node < node2LI.size(); ++node) { + // Scan the machine function and add a coalescing cost whenever CoalescerPair + // gives the Ok. + for (MachineFunction::const_iterator mbbItr = mf->begin(), + mbbEnd = mf->end(); + mbbItr != mbbEnd; ++mbbItr) { + const MachineBasicBlock *mbb = &*mbbItr; - // 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)); + for (MachineBasicBlock::const_iterator miItr = mbb->begin(), + miEnd = mbb->end(); + miItr != miEnd; ++miItr) { + const MachineInstr *mi = &*miItr; - // 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) { + if (!cp.setRegisters(mi)) { + continue; // Not coalescable. + } - if (li->overlaps(**pItr)) { + if (cp.getSrcReg() == cp.getDstReg()) { + continue; // Already coalesced. + } - unsigned pReg = (*pItr)->reg; + unsigned dst = cp.getDstReg(), + src = cp.getSrcReg(); - // Remove the overlapping reg... - liAllowed.erase(pReg); + const float copyFactor = 0.5; // Cost of copy relative to load. Current + // value plucked randomly out of the air. - const unsigned *aliasItr = tri->getAliasSet(pReg); + PBQP::PBQPNum cBenefit = + copyFactor * LiveIntervals::getSpillWeight(false, true, + loopInfo->getLoopDepth(mbb)); - if (aliasItr != 0) { - // ...and its aliases. - for (; *aliasItr != 0; ++aliasItr) { - liAllowed.erase(*aliasItr); - } + if (cp.isPhys()) { + if (!lis->isAllocatable(dst)) { + continue; + } + const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src); + unsigned pregOpt = 0; + while (pregOpt < allowed.size() && allowed[pregOpt] != dst) { + ++pregOpt; + } + if (pregOpt < allowed.size()) { + ++pregOpt; // +1 to account for spill option. + PBQP::Graph::NodeItr node = p->getNodeForVReg(src); + addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit); + } + } else { + const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst); + const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src); + PBQP::Graph::NodeItr node1 = p->getNodeForVReg(dst); + PBQP::Graph::NodeItr node2 = p->getNodeForVReg(src); + PBQP::Graph::EdgeItr edge = g.findEdge(node1, node2); + if (edge == g.edgesEnd()) { + edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1, + allowed2->size() + 1, + 0)); + } else { + if (g.getEdgeNode1(edge) == node2) { + std::swap(node1, node2); + std::swap(allowed1, allowed2); } - } + addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2, + cBenefit); } - } + } - // Copy the allowed set into a member vector for use when constructing cost - // vectors & matrices, and mapping PBQP solutions back to assignments. - allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end()); + return p; +} + +void PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec, + unsigned pregOption, + PBQP::PBQPNum benefit) { + costVec[pregOption] += -benefit; +} - // 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(); +void PBQPBuilderWithCoalescing::addVirtRegCoalesce( + PBQP::Matrix &costMat, + const PBQPRAProblem::AllowedSet &vr1Allowed, + const PBQPRAProblem::AllowedSet &vr2Allowed, + PBQP::PBQPNum benefit) { - // Build a cost vector for this interval. - add_pbqp_nodecosts(solver, node, - buildCostVector(allowedSets[node], spillCost)); + assert(costMat.getRows() == vr1Allowed.size() + 1 && "Size mismatch."); + assert(costMat.getCols() == vr2Allowed.size() + 1 && "Size mismatch."); + for (unsigned i = 0; i != vr1Allowed.size(); ++i) { + unsigned preg1 = vr1Allowed[i]; + for (unsigned j = 0; j != vr2Allowed.size(); ++j) { + unsigned preg2 = vr2Allowed[j]; + + if (preg1 == preg2) { + costMat[i + 1][j + 1] += -benefit; + } + } } +} - // 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]; +void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { + au.setPreservesCFG(); + au.addRequired(); + au.addPreserved(); + au.addRequired(); + au.addPreserved(); + au.addRequired(); + //au.addRequiredID(SplitCriticalEdgesID); + if (customPassID) + au.addRequiredID(*customPassID); + au.addRequired(); + au.addRequired(); + au.addPreserved(); + au.addRequired(); + au.addPreserved(); + au.addRequired(); + au.addPreserved(); + au.addRequired(); + MachineFunctionPass::getAnalysisUsage(au); +} - if (li2->empty()) - continue; +void RegAllocPBQP::findVRegIntervalsToAlloc() { - if (li->overlaps(*li2)) { - PBQPMatrix *m = - buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]); + // Iterate over all live ranges. + for (unsigned i = 0, e = mri->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (mri->reg_nodbg_empty(Reg)) + continue; + LiveInterval *li = &lis->getInterval(Reg); - if (m != 0) { - add_pbqp_edgecosts(solver, node1, node2, m); - delete m; - } - } + // 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()) { + vregsToAlloc.insert(li->reg); + } else { + emptyIntervalVRegs.insert(li->reg); } } - - // We're done, PBQP problem constructed - return it. - return solver; } -bool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) { - +bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem &problem, + 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); - - // 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]; - - // Add to the virt reg map and update the used phys regs. - vrm->assignVirt2Phys(symReg, physReg); - mri->setPhysRegUsed(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; + const PBQP::Graph &g = problem.getGraph(); + // Iterate over the nodes mapping the PBQP solution to a register + // assignment. + for (PBQP::Graph::ConstNodeItr node = g.nodesBegin(), + nodeEnd = g.nodesEnd(); + node != nodeEnd; ++node) { + unsigned vreg = problem.getVRegForNode(node); + unsigned alloc = solution.getSelection(node); + + if (problem.isPRegOption(vreg, alloc)) { + unsigned preg = problem.getPRegForOption(vreg, alloc); + DEBUG(dbgs() << "VREG " << PrintReg(vreg, tri) << " -> " + << tri->getName(preg) << "\n"); + assert(preg != 0 && "Invalid preg selected."); + vrm->assignVirt2Phys(vreg, preg); + } else if (problem.isSpillOption(vreg, alloc)) { + vregsToAlloc.erase(vreg); + SmallVector newSpills; + LiveRangeEdit LRE(&lis->getInterval(vreg), newSpills, *mf, *lis, vrm); + spiller->spill(LRE); + + DEBUG(dbgs() << "VREG " << PrintReg(vreg, tri) << " -> SPILLED (Cost: " + << LRE.getParent().weight << ", New vregs: "); + + // Copy any newly inserted live intervals into the list of regs to + // allocate. + for (LiveRangeEdit::iterator itr = LRE.begin(), end = LRE.end(); + itr != end; ++itr) { + assert(!(*itr)->empty() && "Empty spill range."); + DEBUG(dbgs() << PrintReg((*itr)->reg, tri) << " "); + vregsToAlloc.insert((*itr)->reg); + } - // Insert spill ranges for this live range - SmallVector spillIs; - std::vector newSpills = - li->addIntervalsForSpills(*node2LI[node], spillIs, loopInfo, *vrm, - SSWeight); + DEBUG(dbgs() << ")\n"); // We need another round if spill intervals were added. - anotherRoundNeeded |= !newSpills.empty(); + anotherRoundNeeded |= !LRE.empty(); + } else { + llvm_unreachable("Unknown allocation option."); } } return !anotherRoundNeeded; } -bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { - + +void RegAllocPBQP::finalizeAlloc() const { + // First allocate registers for the empty intervals. + for (RegSet::const_iterator + itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end(); + itr != end; ++itr) { + LiveInterval *li = &lis->getInterval(*itr); + + unsigned physReg = vrm->getRegAllocPref(li->reg); + + if (physReg == 0) { + const TargetRegisterClass *liRC = mri->getRegClass(li->reg); + physReg = liRC->getRawAllocationOrder(*mf).front(); + } + + vrm->assignVirt2Phys(li->reg, physReg); + } +} + +bool RegAllocPBQP::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(); + spiller.reset(createInlineSpiller(*this, MF, *vrm)); + + mri->freezeReservedRegs(MF); + + 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(); + + const Function* func = mf->getFunction(); + std::string fqn = + func->getParent()->getModuleIdentifier() + "." + + func->getName().str(); + (void)fqn; + + // If there are non-empty intervals allocate them using pbqp. + if (!vregsToAlloc.empty()) { + + bool pbqpAllocComplete = false; + unsigned round = 0; + + while (!pbqpAllocComplete) { + DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); + + std::auto_ptr problem = + builder->build(mf, lis, loopInfo, vregsToAlloc); + +#ifndef NDEBUG + if (pbqpDumpGraphs) { + std::ostringstream rs; + rs << round; + std::string graphFileName(fqn + "." + rs.str() + ".pbqpgraph"); + std::string tmp; + raw_fd_ostream os(graphFileName.c_str(), tmp); + DEBUG(dbgs() << "Dumping graph for round " << round << " to \"" + << graphFileName << "\"\n"); + problem->getGraph().dump(os); + } +#endif + + PBQP::Solution solution = + PBQP::HeuristicSolver::solve( + problem->getGraph()); + + pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution); + + ++round; + } } - ignoreSet.clear(); + // Finalise allocation, allocate empty ranges. + finalizeAlloc(); + vregsToAlloc.clear(); + emptyIntervalVRegs.clear(); - std::auto_ptr spiller(createSpiller()); + DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); - spiller->runOnMachineFunction(*mf, *vrm); - - return true; + return true; } -FunctionPass* llvm::createPBQPRegisterAllocator() { - return new PBQPRegAlloc(); +FunctionPass* llvm::createPBQPRegisterAllocator( + std::auto_ptr builder, + char *customPassID) { + return new RegAllocPBQP(builder, customPassID); } +FunctionPass* llvm::createDefaultPBQPRegisterAllocator() { + if (pbqpCoalescing) { + return createPBQPRegisterAllocator( + std::auto_ptr(new PBQPBuilderWithCoalescing())); + } // else + return createPBQPRegisterAllocator( + std::auto_ptr(new PBQPBuilder())); +} #undef DEBUG_TYPE