X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocPBQP.cpp;h=5bd33743db0dc618bdec0cb5d39809f7e2b053b2;hb=ab08da75d70c76fd946483e29366264c92cc092b;hp=0dd921482696271d7a9589fece30c9baf5cb0db0;hpb=90c579de5a383cee278acc3f7e7b9d0a656e6a35;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index 0dd92148269..5bd33743db0 100644 --- a/lib/CodeGen/RegAllocPBQP.cpp +++ b/lib/CodeGen/RegAllocPBQP.cpp @@ -29,848 +29,577 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" - -#include "PBQP/HeuristicSolver.h" -#include "PBQP/Graph.h" -#include "PBQP/Heuristics/Briggs.h" -#include "RenderMachineFunction.h" -#include "Splitter.h" -#include "VirtRegMap.h" -#include "VirtRegRewriter.h" +#include "llvm/CodeGen/RegAllocPBQP.h" +#include "RegisterCoalescer.h" +#include "Spiller.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/LiveRangeEdit.h" #include "llvm/CodeGen/LiveStackAnalysis.h" +#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" +#include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/RegAllocRegistry.h" -#include "llvm/CodeGen/RegisterCoalescer.h" +#include "llvm/CodeGen/VirtRegMap.h" +#include "llvm/IR/Module.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/FileSystem.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetSubtargetInfo.h" #include -#include #include +#include #include +#include #include using namespace llvm; +#define DEBUG_TYPE "regalloc" + static RegisterRegAlloc -registerPBQPRepAlloc("pbqp", "PBQP register allocator", - llvm::createPBQPRegisterAllocator); +RegisterPBQPRepAlloc("pbqp", "PBQP register allocator", + createDefaultPBQPRegisterAllocator); static cl::opt -pbqpCoalescing("pbqp-coalescing", +PBQPCoalescing("pbqp-coalescing", cl::desc("Attempt coalescing during PBQP register allocation."), cl::init(false), cl::Hidden); +#ifndef NDEBUG static cl::opt -pbqpPreSplitting("pbqp-pre-splitting", - cl::desc("Pre-splite before PBQP register allocation."), - cl::init(false), cl::Hidden); +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 PBQPRegAlloc : public MachineFunctionPass { - public: - - static char ID; - - /// Construct a PBQP register allocator. - PBQPRegAlloc() : MachineFunctionPass(ID) {} +/// +/// 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(char *cPassID = nullptr) + : MachineFunctionPass(ID), customPassID(cPassID) { + initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); + initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); + initializeLiveStacksPass(*PassRegistry::getPassRegistry()); + initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); + } - /// Return the pass name. - virtual const char* getPassName() const { - return "PBQP Register Allocator"; - } + /// Return the pass name. + const char* getPassName() const override { + return "PBQP Register Allocator"; + } - /// 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(); - if (pbqpPreSplitting) - au.addRequired(); - au.addRequired(); - au.addRequired(); - MachineFunctionPass::getAnalysisUsage(au); - } + /// PBQP analysis usage. + void getAnalysisUsage(AnalysisUsage &au) const override; - /// Perform register allocation - virtual bool runOnMachineFunction(MachineFunction &MF); + /// Perform register allocation + bool runOnMachineFunction(MachineFunction &MF) override; - private: +private: - class LIOrdering { - public: - bool operator()(const LiveInterval *li1, const LiveInterval *li2) const { - return li1->reg < li2->reg; - } - }; - - typedef std::map LI2NodeMap; - typedef std::vector Node2LIMap; - typedef std::vector AllowedSet; - typedef std::vector AllowedSetMap; - 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; - const TargetRegisterInfo *tri; - const TargetInstrInfo *tii; - const MachineLoopInfo *loopInfo; - MachineRegisterInfo *mri; - - LiveIntervals *lis; - LiveStacks *lss; - VirtRegMap *vrm; - - LI2NodeMap li2Node; - Node2LIMap node2LI; - AllowedSetMap allowedSets; - 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; - - }; - - char PBQPRegAlloc::ID = 0; -} + 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::set RegSet; + char *customPassID; -template -PBQP::Vector PBQPRegAlloc::buildCostVector(unsigned vReg, - const RegContainer &allowed, - const CoalesceMap &coalesces, - PBQP::PBQPNum spillCost) const { + RegSet VRegsToAlloc, EmptyIntervalVRegs; - typedef typename RegContainer::const_iterator AllowedItr; + /// \brief Finds the initial set of vreg intervals to allocate. + void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS); - // Allocate vector. Additional element (0th) used for spill option - PBQP::Vector v(allowed.size() + 1, 0); + /// \brief Constructs an initial graph. + void initializeGraph(PBQPRAGraph &G); - v[0] = spillCost; + /// \brief Given a solved PBQP problem maps this solution back to a register + /// assignment. + bool mapPBQPToRegAlloc(const PBQPRAGraph &G, + const PBQP::Solution &Solution, + VirtRegMap &VRM, + Spiller &VRegSpiller); - // 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) { + /// \brief Postprocessing before final spilling. Sets basic block "live in" + /// variables. + void finalizeAlloc(MachineFunction &MF, LiveIntervals &LIS, + VirtRegMap &VRM) const; - unsigned pReg = *itr; +}; - CoalesceMap::const_iterator cmItr = - coalesces.find(RegPair(vReg, pReg)); +char RegAllocPBQP::ID = 0; - // No coalesce - on to the next preg. - if (cmItr == coalesces.end()) - continue; +/// @brief Set spill costs for each node in the PBQP reg-alloc graph. +class SpillCosts : public PBQPRAConstraint { +public: + void apply(PBQPRAGraph &G) override { + LiveIntervals &LIS = G.getMetadata().LIS; - // We have a coalesce - insert the benefit. - v[ai + 1] = -cmItr->second; + for (auto NId : G.nodeIds()) { + PBQP::PBQPNum SpillCost = + LIS.getInterval(G.getNodeMetadata(NId).getVReg()).weight; + if (SpillCost == 0.0) + SpillCost = std::numeric_limits::min(); + PBQPRAGraph::RawVector NodeCosts(G.getNodeCosts(NId)); + NodeCosts[PBQP::RegAlloc::getSpillOptionIdx()] = SpillCost; + G.setNodeCosts(NId, std::move(NodeCosts)); + } } +}; - return v; -} - -template -PBQP::Matrix* PBQPRegAlloc::buildInterferenceMatrix( - const RegContainer &allowed1, const RegContainer &allowed2) const { - - 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 - // 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). - 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 - // 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 (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) { - - unsigned reg2 = *a2Itr; - - // If the row/column regs are identical or alias insert an infinity. - if (tri->regsOverlap(reg1, reg2)) { - (*m)[ri][ci] = std::numeric_limits::infinity(); - isZeroMatrix = false; - } +/// @brief Add interference edges between overlapping vregs. +class Interference : public PBQPRAConstraint { +private: - ++ci; - } + // Holds (Interval, CurrentSegmentID, and NodeId). The first two are required + // for the fast interference graph construction algorithm. The last is there + // to save us from looking up node ids via the VRegToNode map in the graph + // metadata. + typedef std::tuple + IntervalInfo; - ++ri; + static SlotIndex getStartPoint(const IntervalInfo &I) { + return std::get<0>(I)->segments[std::get<1>(I)].start; } - // If this turns out to be a zero matrix... - if (isZeroMatrix) { - // free it and return null. - delete m; - return 0; + static SlotIndex getEndPoint(const IntervalInfo &I) { + return std::get<0>(I)->segments[std::get<1>(I)].end; } - // ...otherwise return the cost matrix. - return m; -} - -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; - } - - ++ri; + static PBQP::GraphBase::NodeId getNodeId(const IntervalInfo &I) { + return std::get<2>(I); } - // If this turns out to be a zero matrix... - if (isZeroMatrix) { - // ...free it and return null. - delete m; - return 0; + static bool lowestStartPoint(const IntervalInfo &I1, + const IntervalInfo &I2) { + // Condition reversed because priority queue has the *highest* element at + // the front, rather than the lowest. + return getStartPoint(I1) > getStartPoint(I2); } - return m; -} - -PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() { + static bool lowestEndPoint(const IntervalInfo &I1, + const IntervalInfo &I2) { + SlotIndex E1 = getEndPoint(I1); + SlotIndex E2 = getEndPoint(I2); - typedef MachineFunction::const_iterator MFIterator; - typedef MachineBasicBlock::const_iterator MBBIterator; - typedef LiveInterval::const_vni_iterator VNIIterator; + if (E1 < E2) + return true; - CoalesceMap coalescesFound; + if (E1 > E2) + return false; - // 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) { + // If two intervals end at the same point, we need a way to break the tie or + // the set will assume they're actually equal and refuse to insert a + // "duplicate". Just compare the vregs - fast and guaranteed unique. + return std::get<0>(I1)->reg < std::get<0>(I2)->reg; + } - const MachineBasicBlock *mbb = &*bbItr; + static bool isAtLastSegment(const IntervalInfo &I) { + return std::get<1>(I) == std::get<0>(I)->size() - 1; + } - for (MBBIterator iItr = mbb->begin(), iEnd = mbb->end(); - iItr != iEnd; ++iItr) { + static IntervalInfo nextSegment(const IntervalInfo &I) { + return std::make_tuple(std::get<0>(I), std::get<1>(I) + 1, std::get<2>(I)); + } - const MachineInstr *instr = &*iItr; +public: + + void apply(PBQPRAGraph &G) override { + // The following is loosely based on the linear scan algorithm introduced in + // "Linear Scan Register Allocation" by Poletto and Sarkar. This version + // isn't linear, because the size of the active set isn't bound by the + // number of registers, but rather the size of the largest clique in the + // graph. Still, we expect this to be better than N^2. + LiveIntervals &LIS = G.getMetadata().LIS; + const TargetRegisterInfo &TRI = + *G.getMetadata().MF.getTarget().getSubtargetImpl()->getRegisterInfo(); + + typedef std::set IntervalSet; + typedef std::priority_queue, + decltype(&lowestStartPoint)> IntervalQueue; + IntervalSet Active(lowestEndPoint); + IntervalQueue Inactive(lowestStartPoint); + + // Start by building the inactive set. + for (auto NId : G.nodeIds()) { + unsigned VReg = G.getNodeMetadata(NId).getVReg(); + LiveInterval &LI = LIS.getInterval(VReg); + assert(!LI.empty() && "PBQP graph contains node for empty interval"); + Inactive.push(std::make_tuple(&LI, 0, NId)); + } - // If this isn't a copy then continue to the next instruction. - if (!instr->isCopy()) - continue; + while (!Inactive.empty()) { + // Tentatively grab the "next" interval - this choice may be overriden + // below. + IntervalInfo Cur = Inactive.top(); + + // Retire any active intervals that end before Cur starts. + IntervalSet::iterator RetireItr = Active.begin(); + while (RetireItr != Active.end() && + (getEndPoint(*RetireItr) <= getStartPoint(Cur))) { + // If this interval has subsequent segments, add the next one to the + // inactive list. + if (!isAtLastSegment(*RetireItr)) + Inactive.push(nextSegment(*RetireItr)); + + ++RetireItr; + } + Active.erase(Active.begin(), RetireItr); + + // One of the newly retired segments may actually start before the + // Cur segment, so re-grab the front of the inactive list. + Cur = Inactive.top(); + Inactive.pop(); + + // At this point we know that Cur overlaps all active intervals. Add the + // interference edges. + PBQP::GraphBase::NodeId NId = getNodeId(Cur); + for (const auto &A : Active) { + PBQP::GraphBase::NodeId MId = getNodeId(A); + + // Check that we haven't already added this edge + // FIXME: findEdge is expensive in the worst case (O(max_clique(G))). + // It might be better to replace this with a local bit-matrix. + if (G.findEdge(NId, MId) != PBQP::GraphBase::invalidEdgeId()) + continue; - unsigned srcReg = instr->getOperand(1).getReg(); - unsigned dstReg = instr->getOperand(0).getReg(); + // This is a new edge - add it to the graph. + const auto &NOpts = G.getNodeMetadata(NId).getOptionRegs(); + const auto &MOpts = G.getNodeMetadata(MId).getOptionRegs(); + G.addEdge(NId, MId, createInterferenceMatrix(TRI, NOpts, MOpts)); + } - // If the registers are already the same our job is nice and easy. - if (dstReg == srcReg) - continue; + // Finally, add Cur to the Active set. + Active.insert(Cur); + } + } - bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg), - dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg); +private: + + PBQPRAGraph::RawMatrix createInterferenceMatrix( + const TargetRegisterInfo &TRI, + const PBQPRAGraph::NodeMetadata::OptionToRegMap &NOpts, + const PBQPRAGraph::NodeMetadata::OptionToRegMap &MOpts) { + PBQPRAGraph::RawMatrix M(NOpts.size() + 1, MOpts.size() + 1, 0); + for (unsigned I = 0; I != NOpts.size(); ++I) { + unsigned PRegN = NOpts[I]; + for (unsigned J = 0; J != MOpts.size(); ++J) { + unsigned PRegM = MOpts[J]; + if (TRI.regsOverlap(PRegN, PRegM)) + M[I + 1][J + 1] = std::numeric_limits::infinity(); + } + } - // If both registers are physical then we can't coalesce. - if (srcRegIsPhysical && dstRegIsPhysical) - continue; + return M; + } +}; - // If it's a copy that includes two virtual register but the source and - // destination classes differ then we can't coalesce. - if (!srcRegIsPhysical && !dstRegIsPhysical && - mri->getRegClass(srcReg) != mri->getRegClass(dstReg)) - continue; - // If one is physical and one is virtual, check that the physical is - // allocatable in the class of the virtual. - if (srcRegIsPhysical && !dstRegIsPhysical) { - const TargetRegisterClass *dstRegClass = mri->getRegClass(dstReg); - if (std::find(dstRegClass->allocation_order_begin(*mf), - dstRegClass->allocation_order_end(*mf), srcReg) == - dstRegClass->allocation_order_end(*mf)) - continue; - } - if (!srcRegIsPhysical && dstRegIsPhysical) { - const TargetRegisterClass *srcRegClass = mri->getRegClass(srcReg); - if (std::find(srcRegClass->allocation_order_begin(*mf), - srcRegClass->allocation_order_end(*mf), dstReg) == - srcRegClass->allocation_order_end(*mf)) - continue; - } +class Coalescing : public PBQPRAConstraint { +public: + void apply(PBQPRAGraph &G) override { + MachineFunction &MF = G.getMetadata().MF; + MachineBlockFrequencyInfo &MBFI = G.getMetadata().MBFI; + CoalescerPair CP(*MF.getTarget().getSubtargetImpl()->getRegisterInfo()); - // 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); + // Scan the machine function and add a coalescing cost whenever CoalescerPair + // gives the Ok. + for (const auto &MBB : MF) { + for (const auto &MI : MBB) { - 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. + // Skip not-coalescable or already coalesced copies. + if (!CP.setRegisters(&MI) || CP.getSrcReg() == CP.getDstReg()) + continue; - // Otherwise start by assuming we're ok. - bool badDef = false; + unsigned DstReg = CP.getDstReg(); + unsigned SrcReg = CP.getSrcReg(); - // Test all defs of the source range. - for (VNIIterator - vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end(); - vniItr != vniEnd; ++vniItr) { + const float CopyFactor = 0.5; // Cost of copy relative to load. Current + // value plucked randomly out of the air. - // If we find a poorly defined def we err on the side of caution. - if (!(*vniItr)->def.isValid()) { - badDef = true; - break; - } + PBQP::PBQPNum CBenefit = + CopyFactor * LiveIntervals::getSpillWeight(false, true, &MBFI, &MI); - // 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; - } - } + if (CP.isPhys()) { + if (!MF.getRegInfo().isAllocatable(DstReg)) + continue; - // If we have a bad def give up, continue to the next instruction. - if (badDef) - continue; + PBQPRAGraph::NodeId NId = G.getMetadata().getNodeIdForVReg(SrcReg); - // Otherwise test definitions of the destination range. - for (VNIIterator - vniItr = dstLI->vni_begin(), vniEnd = dstLI->vni_end(); - vniItr != vniEnd; ++vniItr) { + const PBQPRAGraph::NodeMetadata::OptionToRegMap &Allowed = + G.getNodeMetadata(NId).getOptionRegs(); - // We want to make sure we skip the copy instruction itself. - if ((*vniItr)->getCopy() == instr) - continue; + unsigned PRegOpt = 0; + while (PRegOpt < Allowed.size() && Allowed[PRegOpt] != DstReg) + ++PRegOpt; - if (!(*vniItr)->def.isValid()) { - badDef = true; - break; + if (PRegOpt < Allowed.size()) { + PBQPRAGraph::RawVector NewCosts(G.getNodeCosts(NId)); + NewCosts[PRegOpt + 1] -= CBenefit; + G.setNodeCosts(NId, std::move(NewCosts)); } - - if (srcLI->liveAt((*vniItr)->def)) { - badDef = true; - break; + } else { + PBQPRAGraph::NodeId N1Id = G.getMetadata().getNodeIdForVReg(DstReg); + PBQPRAGraph::NodeId N2Id = G.getMetadata().getNodeIdForVReg(SrcReg); + const PBQPRAGraph::NodeMetadata::OptionToRegMap *Allowed1 = + &G.getNodeMetadata(N1Id).getOptionRegs(); + const PBQPRAGraph::NodeMetadata::OptionToRegMap *Allowed2 = + &G.getNodeMetadata(N2Id).getOptionRegs(); + + PBQPRAGraph::EdgeId EId = G.findEdge(N1Id, N2Id); + if (EId == G.invalidEdgeId()) { + PBQPRAGraph::RawMatrix Costs(Allowed1->size() + 1, + Allowed2->size() + 1, 0); + addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit); + G.addEdge(N1Id, N2Id, std::move(Costs)); + } else { + if (G.getEdgeNode1Id(EId) == N2Id) { + std::swap(N1Id, N2Id); + std::swap(Allowed1, Allowed2); + } + PBQPRAGraph::RawMatrix Costs(G.getEdgeCosts(EId)); + addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit); + G.setEdgeCosts(EId, std::move(Costs)); } } - - // 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 = std::pow(10.0f, (float)loopInfo->getLoopDepth(mbb)) / 5.0; - - coalescesFound[RegPair(srcReg, dstReg)] = cBenefit; - coalescesFound[RegPair(dstReg, srcReg)] = cBenefit; } + } +private: + + void addVirtRegCoalesce( + PBQPRAGraph::RawMatrix &CostMat, + const PBQPRAGraph::NodeMetadata::OptionToRegMap &Allowed1, + const PBQPRAGraph::NodeMetadata::OptionToRegMap &Allowed2, + PBQP::PBQPNum Benefit) { + assert(CostMat.getRows() == Allowed1.size() + 1 && "Size mismatch."); + assert(CostMat.getCols() == Allowed2.size() + 1 && "Size mismatch."); + for (unsigned I = 0; I != Allowed1.size(); ++I) { + unsigned PReg1 = Allowed1[I]; + for (unsigned J = 0; J != Allowed2.size(); ++J) { + unsigned PReg2 = Allowed2[J]; + if (PReg1 == PReg2) + CostMat[I + 1][J + 1] -= Benefit; + } + } } - return coalescesFound; +}; + +} // End anonymous namespace. + +// Out-of-line destructor/anchor for PBQPRAConstraint. +PBQPRAConstraint::~PBQPRAConstraint() {} +void PBQPRAConstraint::anchor() {} +void PBQPRAConstraintList::anchor() {} + +void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { + au.setPreservesCFG(); + au.addRequired(); + au.addPreserved(); + au.addRequired(); + au.addPreserved(); + au.addRequired(); + au.addPreserved(); + //au.addRequiredID(SplitCriticalEdgesID); + if (customPassID) + au.addRequiredID(*customPassID); + au.addRequired(); + au.addPreserved(); + au.addRequired(); + au.addPreserved(); + au.addRequired(); + au.addPreserved(); + au.addRequired(); + au.addPreserved(); + au.addRequired(); + au.addPreserved(); + MachineFunctionPass::getAnalysisUsage(au); } -void PBQPRegAlloc::findVRegIntervalsToAlloc() { +void RegAllocPBQP::findVRegIntervalsToAlloc(const MachineFunction &MF, + LiveIntervals &LIS) { + const MachineRegisterInfo &MRI = MF.getRegInfo(); // 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)) + for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(I); + if (MRI.reg_nodbg_empty(Reg)) continue; - - LiveInterval *li = itr->second; + LiveInterval &LI = LIS.getInterval(Reg); // 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); + if (!LI.empty()) { + VRegsToAlloc.insert(LI.reg); + } else { + EmptyIntervalVRegs.insert(LI.reg); } } } -PBQP::Graph PBQPRegAlloc::constructPBQPProblem() { - - typedef std::vector LIVector; - typedef std::vector RegVector; - - // 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(); - - // Populate physIntervals, update preg use: - for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); - itr != end; ++itr) { - - if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { - physIntervals.push_back(itr->second); - mri->setPhysRegUsed(itr->second->reg); - } - } - - // 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[li] = node2LI.size(); - node2LI.push_back(li); - } - - // Get the set of potential coalesces. - CoalesceMap coalesces; - - if (pbqpCoalescing) { - coalesces = findCoalesces(); - } - - // Construct a PBQP solver for this problem - PBQP::Graph problem; - problemNodes.resize(vregIntervalsToAlloc.size()); +void RegAllocPBQP::initializeGraph(PBQPRAGraph &G) { + MachineFunction &MF = G.getMetadata().MF; - // Resize allowedSets container appropriately. - allowedSets.resize(vregIntervalsToAlloc.size()); + LiveIntervals &LIS = G.getMetadata().LIS; + const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo(); + const TargetRegisterInfo &TRI = + *G.getMetadata().MF.getTarget().getSubtargetImpl()->getRegisterInfo(); - // Iterate over virtual register intervals to compute allowed sets... - for (unsigned node = 0; node < node2LI.size(); ++node) { + for (auto VReg : VRegsToAlloc) { + const TargetRegisterClass *TRC = MRI.getRegClass(VReg); + LiveInterval &VRegLI = LIS.getInterval(VReg); - // Grab pointers to the interval and its register class. - const LiveInterval *li = node2LI[node]; - const TargetRegisterClass *liRC = mri->getRegClass(li->reg); + // Record any overlaps with regmask operands. + BitVector RegMaskOverlaps; + LIS.checkRegMaskInterference(VRegLI, RegMaskOverlaps); - // Start by assuming all allocable registers in the class are allowed... - RegVector liAllowed(liRC->allocation_order_begin(*mf), - liRC->allocation_order_end(*mf)); - - // 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)) + // Compute an initial allowed set for the current vreg. + std::vector VRegAllowed; + ArrayRef RawPRegOrder = TRC->getRawAllocationOrder(MF); + for (unsigned I = 0; I != RawPRegOrder.size(); ++I) { + unsigned PReg = RawPRegOrder[I]; + if (MRI.isReserved(PReg)) continue; - 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()) + // vregLI crosses a regmask operand that clobbers preg. + if (!RegMaskOverlaps.empty() && !RegMaskOverlaps.test(PReg)) continue; - // 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); - } + // 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; } } - } - - // 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()); - - // Set the spill cost to the interval weight, or epsilon if the - // interval weight is zero - PBQP::PBQPNum spillCost = (li->weight != 0.0) ? - li->weight : std::numeric_limits::min(); - - // Build a cost vector for this interval. - 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]; - - // Test for live range overlaps and insert interference matrices. - for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) { - const LiveInterval *li2 = node2LI[node2]; - - CoalesceMap::const_iterator cmItr = - coalesces.find(RegPair(li->reg, li2->reg)); - - PBQP::Matrix *m = 0; - - 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); + if (Interference) + continue; - delete m; - } + // preg is usable for this virtual register. + VRegAllowed.push_back(PReg); } - } - - 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 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); + PBQPRAGraph::RawVector NodeCosts(VRegAllowed.size() + 1, 0); + PBQPRAGraph::NodeId NId = G.addNode(std::move(NodeCosts)); + G.getNodeMetadata(NId).setVReg(VReg); + G.getNodeMetadata(NId).setOptionRegs(std::move(VRegAllowed)); + G.getMetadata().setNodeIdForVReg(VReg, NId); + } } -bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { +bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G, + const PBQP::Solution &Solution, + VirtRegMap &VRM, + Spiller &VRegSpiller) { + MachineFunction &MF = G.getMetadata().MF; + LiveIntervals &LIS = G.getMetadata().LIS; + const TargetRegisterInfo &TRI = + *MF.getTarget().getSubtargetImpl()->getRegisterInfo(); + (void)TRI; // Set to true if we have any spills - bool anotherRoundNeeded = false; + 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 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(virtReg, physReg); - } - // ...Otherwise it's a spill. - else { - - // Make sure we ignore this virtual reg on the next round - // of allocation - 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 = - lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm); - addStackInterval(spillInterval, mri); - - (void) oldSpillWeight; - DEBUG(dbgs() << "VREG " << virtReg << " -> SPILLED (Cost: " - << oldSpillWeight << ", New vregs: "); + VRM.clearAllVirt(); + + // Iterate over the nodes mapping the PBQP solution to a register + // assignment. + for (auto NId : G.nodeIds()) { + unsigned VReg = G.getNodeMetadata(NId).getVReg(); + unsigned AllocOption = Solution.getSelection(NId); + + if (AllocOption != PBQP::RegAlloc::getSpillOptionIdx()) { + unsigned PReg = G.getNodeMetadata(NId).getOptionRegs()[AllocOption - 1]; + DEBUG(dbgs() << "VREG " << PrintReg(VReg, &TRI) << " -> " + << TRI.getName(PReg) << "\n"); + assert(PReg != 0 && "Invalid preg selected."); + VRM.assignVirt2Phys(VReg, PReg); + } else { + VRegsToAlloc.erase(VReg); + SmallVector NewSpills; + LiveRangeEdit LRE(&LIS.getInterval(VReg), NewSpills, MF, LIS, &VRM); + VRegSpiller.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 (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); + for (LiveRangeEdit::iterator I = LRE.begin(), E = LRE.end(); + I != E; ++I) { + LiveInterval &LI = LIS.getInterval(*I); + assert(!LI.empty() && "Empty spill range."); + DEBUG(dbgs() << PrintReg(LI.reg, &TRI) << " "); + VRegsToAlloc.insert(LI.reg); } DEBUG(dbgs() << ")\n"); // We need another round if spill intervals were added. - anotherRoundNeeded |= !newSpills.empty(); + AnotherRoundNeeded |= !LRE.empty(); } } - return !anotherRoundNeeded; + return !AnotherRoundNeeded; } -void PBQPRegAlloc::finalizeAlloc() const { - typedef LiveIntervals::iterator LIIterator; - typedef LiveInterval::Ranges::const_iterator LRIterator; + +void RegAllocPBQP::finalizeAlloc(MachineFunction &MF, + LiveIntervals &LIS, + VirtRegMap &VRM) const { + MachineRegisterInfo &MRI = MF.getRegInfo(); // First allocate registers for the empty intervals. - for (LiveIntervalSet::const_iterator - itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end(); - itr != end; ++itr) { - LiveInterval *li = *itr; + for (RegSet::const_iterator + I = EmptyIntervalVRegs.begin(), E = EmptyIntervalVRegs.end(); + I != E; ++I) { + LiveInterval &LI = LIS.getInterval(*I); - unsigned physReg = vrm->getRegAllocPref(li->reg); + unsigned PReg = MRI.getSimpleHint(LI.reg); - if (physReg == 0) { - const TargetRegisterClass *liRC = mri->getRegClass(li->reg); - physReg = *liRC->allocation_order_begin(*mf); + if (PReg == 0) { + const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg); + PReg = RC.getRawAllocationOrder(MF).front(); } - vrm->assignVirt2Phys(li->reg, physReg); + VRM.assignVirt2Phys(LI.reg, PReg); } - - // 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) { +bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { + LiveIntervals &LIS = getAnalysis(); + MachineBlockFrequencyInfo &MBFI = + getAnalysis(); - mf = &MF; - tm = &mf->getTarget(); - tri = tm->getRegisterInfo(); - tii = tm->getInstrInfo(); - mri = &mf->getRegInfo(); + calculateSpillWeightsAndHints(LIS, MF, getAnalysis(), MBFI); - lis = &getAnalysis(); - lss = &getAnalysis(); - loopInfo = &getAnalysis(); - RenderMachineFunction *rmf = &getAnalysis(); + VirtRegMap &VRM = getAnalysis(); - vrm = &getAnalysis(); + std::unique_ptr VRegSpiller(createInlineSpiller(*this, MF, VRM)); + MF.getRegInfo().freezeReservedRegs(MF); - DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n"); + DEBUG(dbgs() << "PBQP Register Allocating for " << MF.getName() << "\n"); // Allocator main loop: // @@ -882,52 +611,72 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { // This process is continued till no more spills are generated. // Find the vreg intervals in need of allocation. - findVRegIntervalsToAlloc(); - - // If there are non-empty intervals allocate them using pbqp. - if (!vregIntervalsToAlloc.empty()) { + findVRegIntervalsToAlloc(MF, LIS); - bool pbqpAllocComplete = false; - unsigned round = 0; +#ifndef NDEBUG + const Function &F = *MF.getFunction(); + std::string FullyQualifiedName = + F.getParent()->getModuleIdentifier() + "." + F.getName().str(); +#endif - while (!pbqpAllocComplete) { - DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); - - PBQP::Graph problem = constructPBQPProblem(); - PBQP::Solution solution = - PBQP::HeuristicSolver::solve(problem); - - pbqpAllocComplete = mapPBQPToRegAlloc(solution); + // If there are non-empty intervals allocate them using pbqp. + if (!VRegsToAlloc.empty()) { + + const TargetSubtargetInfo &Subtarget = *MF.getTarget().getSubtargetImpl(); + std::unique_ptr ConstraintsRoot = + llvm::make_unique(); + ConstraintsRoot->addConstraint(llvm::make_unique()); + ConstraintsRoot->addConstraint(llvm::make_unique()); + if (PBQPCoalescing) + ConstraintsRoot->addConstraint(llvm::make_unique()); + ConstraintsRoot->addConstraint(Subtarget.getCustomPBQPConstraints()); + + bool PBQPAllocComplete = false; + unsigned Round = 0; + + while (!PBQPAllocComplete) { + DEBUG(dbgs() << " PBQP Regalloc round " << Round << ":\n"); + + PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI)); + initializeGraph(G); + ConstraintsRoot->apply(G); + +#ifndef NDEBUG + if (PBQPDumpGraphs) { + std::ostringstream RS; + RS << Round; + std::string GraphFileName = FullyQualifiedName + "." + RS.str() + + ".pbqpgraph"; + std::error_code EC; + raw_fd_ostream OS(GraphFileName, EC, sys::fs::F_Text); + DEBUG(dbgs() << "Dumping graph for round " << Round << " to \"" + << GraphFileName << "\"\n"); + G.dumpToStream(OS); + } +#endif - ++round; + PBQP::Solution Solution = PBQP::RegAlloc::solve(G); + PBQPAllocComplete = mapPBQPToRegAlloc(G, Solution, VRM, *VRegSpiller); + ++Round; } } // Finalise allocation, allocate empty ranges. - finalizeAlloc(); - - rmf->renderMachineFunction("After PBQP register allocation.", vrm); + finalizeAlloc(MF, LIS, VRM); + VRegsToAlloc.clear(); + EmptyIntervalVRegs.clear(); - 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()); - - rewriter->runOnMachineFunction(*mf, *vrm, lis); + DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << VRM << "\n"); return true; } -FunctionPass* llvm::createPBQPRegisterAllocator() { - return new PBQPRegAlloc(); +FunctionPass *llvm::createPBQPRegisterAllocator(char *customPassID) { + return new RegAllocPBQP(customPassID); } +FunctionPass* llvm::createDefaultPBQPRegisterAllocator() { + return createPBQPRegisterAllocator(); +} #undef DEBUG_TYPE