X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocPBQP.cpp;h=fd28b05ed80a5446bb9b53e7970aa120d6098c53;hb=651ff526af3b1a2eaaef8ab1bbbd38abfb17bc78;hp=849cc6c4bc01410a72e5ea514bfa1134a046e82a;hpb=05935e2d04438f6603091235d2d9671151fac4b9;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index 849cc6c4bc0..fd28b05ed80 100644 --- a/lib/CodeGen/RegAllocPBQP.cpp +++ b/lib/CodeGen/RegAllocPBQP.cpp @@ -47,6 +47,7 @@ #include "llvm/IR/Module.h" #include "llvm/Support/Debug.h" #include "llvm/Support/FileSystem.h" +#include "llvm/Support/Printable.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetSubtargetInfo.h" @@ -126,7 +127,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. @@ -173,8 +179,40 @@ class Interference : public PBQPRAConstraint { private: typedef const PBQP::RegAlloc::AllowedRegVector* AllowedRegVecPtr; - typedef std::pair IMatrixKey; - typedef DenseMap IMatrixCache; + 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 @@ -242,6 +280,13 @@ public: // 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; @@ -285,14 +330,21 @@ public: 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 - // 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) != PBQPRAGraph::invalidEdgeId()) + 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. - createInterferenceEdge(G, NId, MId, C); + if (!createInterferenceEdge(G, NId, MId, C)) + setDisjointAllowedRegs(G, NId, MId, D); + else + EC.insert(EK); } // Finally, add Cur to the Active set. @@ -302,35 +354,48 @@ public: private: - void createInterferenceEdge(PBQPRAGraph &G, PBQPRAGraph::NodeId NId, - PBQPRAGraph::NodeId MId, IMatrixCache &C) { + // 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. - IMatrixKey K(&NRegs, &MRegs); + IKey K(&NRegs, &MRegs); IMatrixCache::iterator I = C.find(K); if (I != C.end()) { G.addEdgeBypassingCostAllocator(NId, MId, I->second); - return; + 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)) + if (TRI.regsOverlap(PRegN, PRegM)) { M[I + 1][J + 1] = std::numeric_limits::infinity(); + NodesInterfere = true; + } } } + if (!NodesInterfere) + return false; + PBQPRAGraph::EdgeId EId = G.addEdge(NId, MId, std::move(M)); C[K] = G.getEdgeCostsPtr(EId); + + return true; } }; @@ -396,7 +461,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)); } } } @@ -433,8 +498,8 @@ void PBQPRAConstraintList::anchor() {} void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { au.setPreservesCFG(); - au.addRequired(); - au.addPreserved(); + au.addRequired(); + au.addPreserved(); au.addRequired(); au.addPreserved(); au.addRequired(); @@ -486,7 +551,8 @@ static bool isACalleeSavedRegister(unsigned reg, const TargetRegisterInfo &TRI, return false; } -void RegAllocPBQP::initializeGraph(PBQPRAGraph &G) { +void RegAllocPBQP::initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, + Spiller &VRegSpiller) { MachineFunction &MF = G.getMetadata().MF; LiveIntervals &LIS = G.getMetadata().LIS; @@ -494,7 +560,12 @@ void RegAllocPBQP::initializeGraph(PBQPRAGraph &G) { const TargetRegisterInfo &TRI = *G.getMetadata().MF.getSubtarget().getRegisterInfo(); - for (auto VReg : VRegsToAlloc) { + std::vector Worklist(VRegsToAlloc.begin(), VRegsToAlloc.end()); + + while (!Worklist.empty()) { + unsigned VReg = Worklist.back(); + Worklist.pop_back(); + const TargetRegisterClass *TRC = MRI.getRegClass(VReg); LiveInterval &VRegLI = LIS.getInterval(VReg); @@ -529,6 +600,15 @@ 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 @@ -545,6 +625,33 @@ void RegAllocPBQP::initializeGraph(PBQPRAGraph &G) { } } +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, @@ -573,28 +680,11 @@ bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G, 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(); } } @@ -635,11 +725,11 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { MachineBlockFrequencyInfo &MBFI = getAnalysis(); - calculateSpillWeightsAndHints(LIS, MF, getAnalysis(), MBFI, - normalizePBQPSpillWeight); - VirtRegMap &VRM = getAnalysis(); + calculateSpillWeightsAndHints(LIS, MF, &VRM, getAnalysis(), + MBFI, normalizePBQPSpillWeight); + std::unique_ptr VRegSpiller(createInlineSpiller(*this, MF, VRM)); MF.getRegInfo().freezeReservedRegs(MF); @@ -683,7 +773,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 @@ -696,7 +786,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 @@ -716,6 +806,63 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { return true; } +/// Create Printable object for node and register info. +static Printable PrintNodeInfo(PBQP::RegAlloc::PBQPRAGraph::NodeId NId, + const PBQP::RegAlloc::PBQPRAGraph &G) { + return Printable([NId, &G](raw_ostream &OS) { + 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) << ')'; + }); +} + +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); }