X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocPBQP.cpp;h=eeff73d0f2a02c2bbaff1f9e9295d9b32f8bc954;hb=f3d745cdc916df5a5db78ac0a5c0efbd8925c097;hp=16c4934fcfe9a93e88ac23bbc75acc3be7d782a7;hpb=54d63b4fd5ebaeccc19775c51725b5daf43c469f;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index 16c4934fcfe..eeff73d0f2a 100644 --- a/lib/CodeGen/RegAllocPBQP.cpp +++ b/lib/CodeGen/RegAllocPBQP.cpp @@ -49,10 +49,10 @@ #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 @@ -126,7 +126,12 @@ private: void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS); /// \brief Constructs an initial graph. - void initializeGraph(PBQPRAGraph &G); + void initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, Spiller &VRegSpiller); + + /// \brief Spill the given VReg. + void spillVReg(unsigned VReg, SmallVectorImpl &NewIntervals, + MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM, + Spiller &VRegSpiller); /// \brief Given a solved PBQP problem maps this solution back to a register /// assignment. @@ -150,11 +155,17 @@ public: void apply(PBQPRAGraph &G) override { LiveIntervals &LIS = G.getMetadata().LIS; + // A minimum spill costs, so that register constraints can can be set + // without normalization in the [0.0:MinSpillCost( interval. + const PBQP::PBQPNum MinSpillCost = 10.0; + for (auto NId : G.nodeIds()) { PBQP::PBQPNum SpillCost = LIS.getInterval(G.getNodeMetadata(NId).getVReg()).weight; if (SpillCost == 0.0) SpillCost = std::numeric_limits::min(); + else + SpillCost += MinSpillCost; PBQPRAGraph::RawVector NodeCosts(G.getNodeCosts(NId)); NodeCosts[PBQP::RegAlloc::getSpillOptionIdx()] = SpillCost; G.setNodeCosts(NId, std::move(NodeCosts)); @@ -164,50 +175,226 @@ public: /// @brief Add interference edges between overlapping vregs. class Interference : public PBQPRAConstraint { +private: + + typedef const PBQP::RegAlloc::AllowedRegVector* AllowedRegVecPtr; + typedef std::pair IKey; + typedef DenseMap IMatrixCache; + typedef DenseSet DisjointAllowedRegsCache; + typedef std::pair IEdgeKey; + typedef DenseSet IEdgeCache; + + bool haveDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId, + PBQPRAGraph::NodeId MId, + const DisjointAllowedRegsCache &D) const { + const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs(); + const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs(); + + if (NRegs == MRegs) + return false; + + if (NRegs < MRegs) + return D.count(IKey(NRegs, MRegs)) > 0; + + return D.count(IKey(MRegs, NRegs)) > 0; + } + + void setDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId, + PBQPRAGraph::NodeId MId, + DisjointAllowedRegsCache &D) { + const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs(); + const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs(); + + assert(NRegs != MRegs && "AllowedRegs can not be disjoint with itself"); + + if (NRegs < MRegs) + D.insert(IKey(NRegs, MRegs)); + else + D.insert(IKey(MRegs, NRegs)); + } + + // 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; + + static SlotIndex getStartPoint(const IntervalInfo &I) { + return std::get<0>(I)->segments[std::get<1>(I)].start; + } + + static SlotIndex getEndPoint(const IntervalInfo &I) { + return std::get<0>(I)->segments[std::get<1>(I)].end; + } + + static PBQP::GraphBase::NodeId getNodeId(const IntervalInfo &I) { + return std::get<2>(I); + } + + 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); + } + + static bool lowestEndPoint(const IntervalInfo &I1, + const IntervalInfo &I2) { + SlotIndex E1 = getEndPoint(I1); + SlotIndex E2 = getEndPoint(I2); + + if (E1 < E2) + return true; + + if (E1 > E2) + return false; + + // 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; + } + + static bool isAtLastSegment(const IntervalInfo &I) { + return std::get<1>(I) == std::get<0>(I)->size() - 1; + } + + static IntervalInfo nextSegment(const IntervalInfo &I) { + return std::make_tuple(std::get<0>(I), std::get<1>(I) + 1, std::get<2>(I)); + } + 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(); - - for (auto NItr = G.nodeIds().begin(), NEnd = G.nodeIds().end(); - NItr != NEnd; ++NItr) { - auto NId = *NItr; - unsigned NVReg = G.getNodeMetadata(NId).getVReg(); - LiveInterval &NLI = LIS.getInterval(NVReg); - - for (auto MItr = std::next(NItr); MItr != NEnd; ++MItr) { - auto MId = *MItr; - unsigned MVReg = G.getNodeMetadata(MId).getVReg(); - LiveInterval &MLI = LIS.getInterval(MVReg); - - if (NLI.overlaps(MLI)) { - const auto &NOpts = G.getNodeMetadata(NId).getOptionRegs(); - const auto &MOpts = G.getNodeMetadata(MId).getOptionRegs(); - G.addEdge(NId, MId, createInterferenceMatrix(TRI, NOpts, MOpts)); - } + + // Interferenc matrices are incredibly regular - they're only a function of + // the allowed sets, so we cache them to avoid the overhead of constructing + // and uniquing them. + IMatrixCache C; + + // Finding an edge is expensive in the worst case (O(max_clique(G))). So + // cache locally edges we have already seen. + IEdgeCache EC; + + // Cache known disjoint allowed registers pairs + DisjointAllowedRegsCache D; + + 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)); + } + + 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); + + // Do not add an edge when the nodes' allowed registers do not + // intersect: there is obviously no interference. + if (haveDisjointAllowedRegs(G, NId, MId, D)) + continue; + + // Check that we haven't already added this edge + IEdgeKey EK(std::min(NId, MId), std::max(NId, MId)); + if (EC.count(EK)) + continue; + + // This is a new edge - add it to the graph. + if (!createInterferenceEdge(G, NId, MId, C)) + setDisjointAllowedRegs(G, NId, MId, D); + else + EC.insert(EK); } + + // Finally, add Cur to the Active set. + Active.insert(Cur); } } 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)) + // Create an Interference edge and add it to the graph, unless it is + // a null matrix, meaning the nodes' allowed registers do not have any + // interference. This case occurs frequently between integer and floating + // point registers for example. + // return true iff both nodes interferes. + bool createInterferenceEdge(PBQPRAGraph &G, + PBQPRAGraph::NodeId NId, PBQPRAGraph::NodeId MId, + IMatrixCache &C) { + + const TargetRegisterInfo &TRI = + *G.getMetadata().MF.getSubtarget().getRegisterInfo(); + const auto &NRegs = G.getNodeMetadata(NId).getAllowedRegs(); + const auto &MRegs = G.getNodeMetadata(MId).getAllowedRegs(); + + // Try looking the edge costs up in the IMatrixCache first. + IKey K(&NRegs, &MRegs); + IMatrixCache::iterator I = C.find(K); + if (I != C.end()) { + G.addEdgeBypassingCostAllocator(NId, MId, I->second); + return true; + } + + PBQPRAGraph::RawMatrix M(NRegs.size() + 1, MRegs.size() + 1, 0); + bool NodesInterfere = false; + for (unsigned I = 0; I != NRegs.size(); ++I) { + unsigned PRegN = NRegs[I]; + for (unsigned J = 0; J != MRegs.size(); ++J) { + unsigned PRegM = MRegs[J]; + if (TRI.regsOverlap(PRegN, PRegM)) { M[I + 1][J + 1] = std::numeric_limits::infinity(); + NodesInterfere = true; + } } } - return M; + if (!NodesInterfere) + return false; + + PBQPRAGraph::EdgeId EId = G.addEdge(NId, MId, std::move(M)); + C[K] = G.getEdgeCostsPtr(EId); + + return true; } }; @@ -217,7 +404,7 @@ public: void apply(PBQPRAGraph &G) override { MachineFunction &MF = G.getMetadata().MF; MachineBlockFrequencyInfo &MBFI = G.getMetadata().MBFI; - CoalescerPair CP(*MF.getTarget().getSubtargetImpl()->getRegisterInfo()); + CoalescerPair CP(*MF.getSubtarget().getRegisterInfo()); // Scan the machine function and add a coalescing cost whenever CoalescerPair // gives the Ok. @@ -231,11 +418,8 @@ public: unsigned DstReg = CP.getDstReg(); unsigned SrcReg = CP.getSrcReg(); - const float CopyFactor = 0.5; // Cost of copy relative to load. Current - // value plucked randomly out of the air. - - PBQP::PBQPNum CBenefit = - CopyFactor * LiveIntervals::getSpillWeight(false, true, &MBFI, &MI); + const float Scale = 1.0f / MBFI.getEntryFreq(); + PBQP::PBQPNum CBenefit = MBFI.getBlockFreq(&MBB).getFrequency() * Scale; if (CP.isPhys()) { if (!MF.getRegInfo().isAllocatable(DstReg)) @@ -243,8 +427,8 @@ public: PBQPRAGraph::NodeId NId = G.getMetadata().getNodeIdForVReg(SrcReg); - const PBQPRAGraph::NodeMetadata::OptionToRegMap &Allowed = - G.getNodeMetadata(NId).getOptionRegs(); + const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed = + G.getNodeMetadata(NId).getAllowedRegs(); unsigned PRegOpt = 0; while (PRegOpt < Allowed.size() && Allowed[PRegOpt] != DstReg) @@ -252,16 +436,16 @@ public: if (PRegOpt < Allowed.size()) { PBQPRAGraph::RawVector NewCosts(G.getNodeCosts(NId)); - NewCosts[PRegOpt + 1] += CBenefit; + NewCosts[PRegOpt + 1] -= CBenefit; G.setNodeCosts(NId, std::move(NewCosts)); } } 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(); + const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed1 = + &G.getNodeMetadata(N1Id).getAllowedRegs(); + const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed2 = + &G.getNodeMetadata(N2Id).getAllowedRegs(); PBQPRAGraph::EdgeId EId = G.findEdge(N1Id, N2Id); if (EId == G.invalidEdgeId()) { @@ -276,7 +460,7 @@ public: } PBQPRAGraph::RawMatrix Costs(G.getEdgeCosts(EId)); addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit); - G.setEdgeCosts(EId, std::move(Costs)); + G.updateEdgeCosts(EId, std::move(Costs)); } } } @@ -286,10 +470,10 @@ public: private: void addVirtRegCoalesce( - PBQPRAGraph::RawMatrix &CostMat, - const PBQPRAGraph::NodeMetadata::OptionToRegMap &Allowed1, - const PBQPRAGraph::NodeMetadata::OptionToRegMap &Allowed2, - PBQP::PBQPNum Benefit) { + PBQPRAGraph::RawMatrix &CostMat, + const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed1, + const PBQPRAGraph::NodeMetadata::AllowedRegVector &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) { @@ -297,7 +481,7 @@ private: for (unsigned J = 0; J != Allowed2.size(); ++J) { unsigned PReg2 = Allowed2[J]; if (PReg1 == PReg2) - CostMat[I + 1][J + 1] += -Benefit; + CostMat[I + 1][J + 1] -= Benefit; } } } @@ -357,15 +541,30 @@ void RegAllocPBQP::findVRegIntervalsToAlloc(const MachineFunction &MF, } } -void RegAllocPBQP::initializeGraph(PBQPRAGraph &G) { +static bool isACalleeSavedRegister(unsigned reg, const TargetRegisterInfo &TRI, + const MachineFunction &MF) { + const MCPhysReg *CSR = TRI.getCalleeSavedRegs(&MF); + for (unsigned i = 0; CSR[i] != 0; ++i) + if (TRI.regsOverlap(reg, CSR[i])) + return true; + return false; +} + +void RegAllocPBQP::initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, + Spiller &VRegSpiller) { MachineFunction &MF = G.getMetadata().MF; LiveIntervals &LIS = G.getMetadata().LIS; const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo(); const TargetRegisterInfo &TRI = - *G.getMetadata().MF.getTarget().getSubtargetImpl()->getRegisterInfo(); + *G.getMetadata().MF.getSubtarget().getRegisterInfo(); + + std::vector Worklist(VRegsToAlloc.begin(), VRegsToAlloc.end()); + + while (!Worklist.empty()) { + unsigned VReg = Worklist.back(); + Worklist.pop_back(); - for (auto VReg : VRegsToAlloc) { const TargetRegisterClass *TRC = MRI.getRegClass(VReg); LiveInterval &VRegLI = LIS.getInterval(VReg); @@ -400,22 +599,65 @@ void RegAllocPBQP::initializeGraph(PBQPRAGraph &G) { VRegAllowed.push_back(PReg); } + // Check for vregs that have no allowed registers. These should be + // pre-spilled and the new vregs added to the worklist. + if (VRegAllowed.empty()) { + SmallVector NewVRegs; + spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller); + Worklist.insert(Worklist.end(), NewVRegs.begin(), NewVRegs.end()); + continue; + } + PBQPRAGraph::RawVector NodeCosts(VRegAllowed.size() + 1, 0); + + // Tweak cost of callee saved registers, as using then force spilling and + // restoring them. This would only happen in the prologue / epilogue though. + for (unsigned i = 0; i != VRegAllowed.size(); ++i) + if (isACalleeSavedRegister(VRegAllowed[i], TRI, MF)) + NodeCosts[1 + i] += 1.0; + PBQPRAGraph::NodeId NId = G.addNode(std::move(NodeCosts)); G.getNodeMetadata(NId).setVReg(VReg); - G.getNodeMetadata(NId).setOptionRegs(std::move(VRegAllowed)); + G.getNodeMetadata(NId).setAllowedRegs( + G.getMetadata().getAllowedRegs(std::move(VRegAllowed))); G.getMetadata().setNodeIdForVReg(VReg, NId); } } +void RegAllocPBQP::spillVReg(unsigned VReg, + SmallVectorImpl &NewIntervals, + MachineFunction &MF, LiveIntervals &LIS, + VirtRegMap &VRM, Spiller &VRegSpiller) { + + VRegsToAlloc.erase(VReg); + LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, MF, LIS, &VRM); + VRegSpiller.spill(LRE); + + const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); + (void)TRI; + 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 I = LRE.begin(), E = LRE.end(); + I != E; ++I) { + const LiveInterval &LI = LIS.getInterval(*I); + assert(!LI.empty() && "Empty spill range."); + DEBUG(dbgs() << PrintReg(LI.reg, &TRI) << " "); + VRegsToAlloc.insert(LI.reg); + } + + DEBUG(dbgs() << ")\n"); +} + 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(); + const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); (void)TRI; // Set to true if we have any spills @@ -431,41 +673,23 @@ bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G, unsigned AllocOption = Solution.getSelection(NId); if (AllocOption != PBQP::RegAlloc::getSpillOptionIdx()) { - unsigned PReg = G.getNodeMetadata(NId).getOptionRegs()[AllocOption - 1]; + unsigned PReg = G.getNodeMetadata(NId).getAllowedRegs()[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 (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 |= !LRE.empty(); + // Spill VReg. If this introduces new intervals we'll need another round + // of allocation. + SmallVector NewVRegs; + spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller); + AnotherRoundNeeded |= !NewVRegs.empty(); } } return !AnotherRoundNeeded; } - void RegAllocPBQP::finalizeAlloc(MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM) const { @@ -488,12 +712,20 @@ void RegAllocPBQP::finalizeAlloc(MachineFunction &MF, } } +static inline float normalizePBQPSpillWeight(float UseDefFreq, unsigned Size, + unsigned NumInstr) { + // All intervals have a spill weight that is mostly proportional to the number + // of uses, with uses in loops having a bigger weight. + return NumInstr * normalizeSpillWeight(UseDefFreq, Size, 1); +} + bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { LiveIntervals &LIS = getAnalysis(); MachineBlockFrequencyInfo &MBFI = getAnalysis(); - calculateSpillWeightsAndHints(LIS, MF, getAnalysis(), MBFI); + calculateSpillWeightsAndHints(LIS, MF, getAnalysis(), MBFI, + normalizePBQPSpillWeight); VirtRegMap &VRM = getAnalysis(); @@ -524,7 +756,7 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { // If there are non-empty intervals allocate them using pbqp. if (!VRegsToAlloc.empty()) { - const TargetSubtargetInfo &Subtarget = *MF.getTarget().getSubtargetImpl(); + const TargetSubtargetInfo &Subtarget = MF.getSubtarget(); std::unique_ptr ConstraintsRoot = llvm::make_unique(); ConstraintsRoot->addConstraint(llvm::make_unique()); @@ -540,7 +772,7 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { DEBUG(dbgs() << " PBQP Regalloc round " << Round << ":\n"); PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI)); - initializeGraph(G); + initializeGraph(G, VRM, *VRegSpiller); ConstraintsRoot->apply(G); #ifndef NDEBUG @@ -553,7 +785,7 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { raw_fd_ostream OS(GraphFileName, EC, sys::fs::F_Text); DEBUG(dbgs() << "Dumping graph for round " << Round << " to \"" << GraphFileName << "\"\n"); - G.dumpToStream(OS); + G.dump(OS); } #endif @@ -573,6 +805,79 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { return true; } +namespace { +// A helper class for printing node and register info in a consistent way +class PrintNodeInfo { +public: + typedef PBQP::RegAlloc::PBQPRAGraph Graph; + typedef PBQP::RegAlloc::PBQPRAGraph::NodeId NodeId; + + PrintNodeInfo(NodeId NId, const Graph &G) : G(G), NId(NId) {} + + void print(raw_ostream &OS) const { + const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo(); + const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo(); + unsigned VReg = G.getNodeMetadata(NId).getVReg(); + const char *RegClassName = TRI->getRegClassName(MRI.getRegClass(VReg)); + OS << NId << " (" << RegClassName << ':' << PrintReg(VReg, TRI) << ')'; + } + +private: + const Graph &G; + NodeId NId; +}; + +inline raw_ostream &operator<<(raw_ostream &OS, const PrintNodeInfo &PR) { + PR.print(OS); + return OS; +} +} // anonymous namespace + +void PBQP::RegAlloc::PBQPRAGraph::dump(raw_ostream &OS) const { + for (auto NId : nodeIds()) { + const Vector &Costs = getNodeCosts(NId); + assert(Costs.getLength() != 0 && "Empty vector in graph."); + OS << PrintNodeInfo(NId, *this) << ": " << Costs << '\n'; + } + OS << '\n'; + + for (auto EId : edgeIds()) { + NodeId N1Id = getEdgeNode1Id(EId); + NodeId N2Id = getEdgeNode2Id(EId); + assert(N1Id != N2Id && "PBQP graphs should not have self-edges."); + const Matrix &M = getEdgeCosts(EId); + assert(M.getRows() != 0 && "No rows in matrix."); + assert(M.getCols() != 0 && "No cols in matrix."); + OS << PrintNodeInfo(N1Id, *this) << ' ' << M.getRows() << " rows / "; + OS << PrintNodeInfo(N2Id, *this) << ' ' << M.getCols() << " cols:\n"; + OS << M << '\n'; + } +} + +void PBQP::RegAlloc::PBQPRAGraph::dump() const { dump(dbgs()); } + +void PBQP::RegAlloc::PBQPRAGraph::printDot(raw_ostream &OS) const { + OS << "graph {\n"; + for (auto NId : nodeIds()) { + OS << " node" << NId << " [ label=\"" + << PrintNodeInfo(NId, *this) << "\\n" + << getNodeCosts(NId) << "\" ]\n"; + } + + OS << " edge [ len=" << nodeIds().size() << " ]\n"; + for (auto EId : edgeIds()) { + OS << " node" << getEdgeNode1Id(EId) + << " -- node" << getEdgeNode2Id(EId) + << " [ label=\""; + const Matrix &EdgeCosts = getEdgeCosts(EId); + for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) { + OS << EdgeCosts.getRowAsVector(i) << "\\n"; + } + OS << "\" ]\n"; + } + OS << "}\n"; +} + FunctionPass *llvm::createPBQPRegisterAllocator(char *customPassID) { return new RegAllocPBQP(customPassID); }