From 8ee1b65836500a588b6086aef720fae916958e16 Mon Sep 17 00:00:00 2001 From: "Arnaud A. de Grandmaison" Date: Wed, 11 Feb 2015 08:25:36 +0000 Subject: [PATCH] [PBQP] Cautiously update edge costs in the solver The NodeMetadata are maintained in an incremental way. When an edge between 2 nodes has its cost updated, in the course of graph reduction for example, the NodeMetadata need first to have the old edge cost removed, then the new edge cost added. Only once the NodeMetadata have been fully updated, it becomes safe to consider promoting the nodes to the ConservativelyAllocatable or OptimallyReducible sets. Previously, this promotion was occuring right after the removing the old cost, and this was breaking the assumption that a ConservativelyAllocatable should not be spilled. This patch also adds asserts to: - enforces the invariant that a node's reduction can not be downgraded, - only not provably allocatable or optimally reducible nodes can be spilled. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@228816 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/PBQP/Graph.h | 6 +- include/llvm/CodeGen/PBQP/ReductionRules.h | 4 +- include/llvm/CodeGen/RegAllocPBQP.h | 65 +++++++++++++++------- lib/CodeGen/RegAllocPBQP.cpp | 4 +- lib/Target/AArch64/AArch64PBQPRegAlloc.cpp | 4 +- 5 files changed, 56 insertions(+), 27 deletions(-) diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h index a56583f06d2..efb723cab39 100644 --- a/include/llvm/CodeGen/PBQP/Graph.h +++ b/include/llvm/CodeGen/PBQP/Graph.h @@ -507,14 +507,14 @@ namespace PBQP { return getNode(NId).getAdjEdgeIds().size(); } - /// @brief Set an edge's cost matrix. + /// @brief Update an edge's cost matrix. /// @param EId Edge id. /// @param Costs New cost matrix. template - void setEdgeCosts(EdgeId EId, OtherMatrixT Costs) { + void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs) { MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs)); if (Solver) - Solver->handleSetEdgeCosts(EId, *AllocatedCosts); + Solver->handleUpdateCosts(EId, *AllocatedCosts); getEdge(EId).Costs = AllocatedCosts; } diff --git a/include/llvm/CodeGen/PBQP/ReductionRules.h b/include/llvm/CodeGen/PBQP/ReductionRules.h index 21fde4d8a5c..cc495042195 100644 --- a/include/llvm/CodeGen/PBQP/ReductionRules.h +++ b/include/llvm/CodeGen/PBQP/ReductionRules.h @@ -132,9 +132,9 @@ namespace PBQP { } else { const Matrix &YZECosts = G.getEdgeCosts(YZEId); if (YNId == G.getEdgeNode1Id(YZEId)) { - G.setEdgeCosts(YZEId, Delta + YZECosts); + G.updateEdgeCosts(YZEId, Delta + YZECosts); } else { - G.setEdgeCosts(YZEId, Delta.transpose() + YZECosts); + G.updateEdgeCosts(YZEId, Delta.transpose() + YZECosts); } } diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h index cfa616006b5..80d232a215a 100644 --- a/include/llvm/CodeGen/RegAllocPBQP.h +++ b/include/llvm/CodeGen/RegAllocPBQP.h @@ -180,10 +180,15 @@ class NodeMetadata { public: typedef RegAlloc::AllowedRegVector AllowedRegVector; - typedef enum { Unprocessed, - OptimallyReducible, - ConservativelyAllocatable, - NotProvablyAllocatable } ReductionState; + // The node's reduction state. The order in this enum is important, + // as it is assumed nodes can only progress up (i.e. towards being + // optimally reducible) when reducing the graph. + typedef enum { + Unprocessed, + NotProvablyAllocatable, + ConservativelyAllocatable, + OptimallyReducible + } ReductionState; NodeMetadata() : RS(Unprocessed), NumOpts(0), DeniedOpts(0), OptUnsafeEdges(nullptr), @@ -248,7 +253,13 @@ public: } ReductionState getReductionState() const { return RS; } - void setReductionState(ReductionState RS) { this->RS = RS; } + void setReductionState(ReductionState RS) { + assert(RS >= this->RS && "A node's reduction state can not be downgraded"); + this->RS = RS; + } + bool isSpillable() const { + return RS == NotProvablyAllocatable || RS == OptimallyReducible; + } void handleAddEdge(const MatrixMetadata& MD, bool Transpose) { DeniedOpts += Transpose ? MD.getWorstRow() : MD.getWorstCol(); @@ -333,15 +344,7 @@ public: NodeMetadata& NMd = G.getNodeMetadata(NId); const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata(); NMd.handleRemoveEdge(MMd, NId == G.getEdgeNode2Id(EId)); - if (G.getNodeDegree(NId) == 3) { - // This node is becoming optimally reducible. - moveToOptimallyReducibleNodes(NId); - } else if (NMd.getReductionState() == - NodeMetadata::NotProvablyAllocatable && - NMd.isConservativelyAllocatable()) { - // This node just became conservatively allocatable. - moveToConservativelyAllocatableNodes(NId); - } + promote(NId, NMd); } void handleReconnectEdge(EdgeId EId, NodeId NId) { @@ -350,20 +353,44 @@ public: NMd.handleAddEdge(MMd, NId == G.getEdgeNode2Id(EId)); } - void handleSetEdgeCosts(EdgeId EId, const Matrix& NewCosts) { - handleRemoveEdge(EId); - + void handleUpdateCosts(EdgeId EId, const Matrix& NewCosts) { NodeId N1Id = G.getEdgeNode1Id(EId); NodeId N2Id = G.getEdgeNode2Id(EId); NodeMetadata& N1Md = G.getNodeMetadata(N1Id); NodeMetadata& N2Md = G.getNodeMetadata(N2Id); + bool Transpose = N1Id != G.getEdgeNode1Id(EId); + + // Metadata are computed incrementally. First, update them + // by removing the old cost. + const MatrixMetadata& OldMMd = G.getEdgeCosts(EId).getMetadata(); + N1Md.handleRemoveEdge(OldMMd, Transpose); + N2Md.handleRemoveEdge(OldMMd, !Transpose); + + // And update now the metadata with the new cost. const MatrixMetadata& MMd = NewCosts.getMetadata(); - N1Md.handleAddEdge(MMd, N1Id != G.getEdgeNode1Id(EId)); - N2Md.handleAddEdge(MMd, N2Id != G.getEdgeNode1Id(EId)); + N1Md.handleAddEdge(MMd, Transpose); + N2Md.handleAddEdge(MMd, !Transpose); + + // As the metadata may have changed with the update, the nodes may have + // become ConservativelyAllocatable or OptimallyReducible. + promote(N1Id, N1Md); + promote(N2Id, N2Md); } private: + void promote(NodeId NId, NodeMetadata& NMd) { + if (G.getNodeDegree(NId) == 3) { + // This node is becoming optimally reducible. + moveToOptimallyReducibleNodes(NId); + } else if (NMd.getReductionState() == + NodeMetadata::NotProvablyAllocatable && + NMd.isConservativelyAllocatable()) { + // This node just became conservatively allocatable. + moveToConservativelyAllocatableNodes(NId); + } + } + void removeFromCurrentSet(NodeId NId) { switch (G.getNodeMetadata(NId).getReductionState()) { case NodeMetadata::Unprocessed: break; diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index af6d16eefd7..0fb4ef62eff 100644 --- a/lib/CodeGen/RegAllocPBQP.cpp +++ b/lib/CodeGen/RegAllocPBQP.cpp @@ -401,7 +401,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)); } } } @@ -621,6 +621,8 @@ bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G, assert(PReg != 0 && "Invalid preg selected."); VRM.assignVirt2Phys(VReg, PReg); } else { + assert(G.getNodeMetadata(NId).isSpillable() && + "Spilling a node which can not be spilled."); // Spill VReg. If this introduces new intervals we'll need another round // of allocation. SmallVector NewVRegs; diff --git a/lib/Target/AArch64/AArch64PBQPRegAlloc.cpp b/lib/Target/AArch64/AArch64PBQPRegAlloc.cpp index 1f072ebfd00..4690177d029 100644 --- a/lib/Target/AArch64/AArch64PBQPRegAlloc.cpp +++ b/lib/Target/AArch64/AArch64PBQPRegAlloc.cpp @@ -235,7 +235,7 @@ bool A57ChainingConstraint::addIntraChainConstraint(PBQPRAGraph &G, unsigned Rd, costs[i + 1][j + 1] = sameParityMax + 1.0; } } - G.setEdgeCosts(edge, std::move(costs)); + G.updateEdgeCosts(edge, std::move(costs)); return true; } @@ -312,7 +312,7 @@ void A57ChainingConstraint::addInterChainConstraint(PBQPRAGraph &G, unsigned Rd, costs[i + 1][j + 1] = sameParityMax + 1.0; } } - G.setEdgeCosts(edge, std::move(costs)); + G.updateEdgeCosts(edge, std::move(costs)); } } } -- 2.34.1