X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FRegAllocPBQP.h;h=4122811a9e5cebe1dbc084cd0dda5aef655f05f8;hb=f7fc15ed79ddcb8cb26f00b61d32b757c62a24b3;hp=540af08408816ba9d2a6903cb79ce25698253eb8;hpb=0059dd4dd1b567c79c05d781363e28da17088f0a;p=oota-llvm.git diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h index 540af084088..4122811a9e5 100644 --- a/include/llvm/CodeGen/RegAllocPBQP.h +++ b/include/llvm/CodeGen/RegAllocPBQP.h @@ -17,12 +17,15 @@ #define LLVM_CODEGEN_REGALLOCPBQP_H #include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/PBQPRAConstraint.h" #include "llvm/CodeGen/PBQP/CostAllocator.h" #include "llvm/CodeGen/PBQP/ReductionRules.h" +#include "llvm/CodeGen/PBQPRAConstraint.h" #include "llvm/Support/ErrorHandling.h" namespace llvm { + +class raw_ostream; + namespace PBQP { namespace RegAlloc { @@ -131,7 +134,7 @@ inline hash_code hash_value(const AllowedRegVector &OptRegs) { hash_combine_range(OStart, OEnd)); } -/// \brief Holds graph-level metadata relevent to PBQP RA problems. +/// \brief Holds graph-level metadata relevant to PBQP RA problems. class GraphMetadata { private: typedef ValuePool AllowedRegVecPool; @@ -177,23 +180,38 @@ 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), - VReg(0) {} + VReg(0) +#ifndef NDEBUG + , everConservativelyAllocatable(false) +#endif + {} // FIXME: Re-implementing default behavior to work around MSVC. Remove once // MSVC synthesizes move constructors properly. NodeMetadata(const NodeMetadata &Other) : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts), OptUnsafeEdges(new unsigned[NumOpts]), VReg(Other.VReg), - AllowedRegs(Other.AllowedRegs) { - std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts], - &OptUnsafeEdges[0]); + AllowedRegs(Other.AllowedRegs) +#ifndef NDEBUG + , everConservativelyAllocatable(Other.everConservativelyAllocatable) +#endif + { + if (NumOpts > 0) { + std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts], + &OptUnsafeEdges[0]); + } } // FIXME: Re-implementing default behavior to work around MSVC. Remove once @@ -201,7 +219,11 @@ public: NodeMetadata(NodeMetadata &&Other) : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts), OptUnsafeEdges(std::move(Other.OptUnsafeEdges)), VReg(Other.VReg), - AllowedRegs(std::move(Other.AllowedRegs)) {} + AllowedRegs(std::move(Other.AllowedRegs)) +#ifndef NDEBUG + , everConservativelyAllocatable(Other.everConservativelyAllocatable) +#endif + {} // FIXME: Re-implementing default behavior to work around MSVC. Remove once // MSVC synthesizes move constructors properly. @@ -214,6 +236,9 @@ public: OptUnsafeEdges.get()); VReg = Other.VReg; AllowedRegs = Other.AllowedRegs; +#ifndef NDEBUG + everConservativelyAllocatable = Other.everConservativelyAllocatable; +#endif return *this; } @@ -226,6 +251,9 @@ public: OptUnsafeEdges = std::move(Other.OptUnsafeEdges); VReg = Other.VReg; AllowedRegs = std::move(Other.AllowedRegs); +#ifndef NDEBUG + everConservativelyAllocatable = Other.everConservativelyAllocatable; +#endif return *this; } @@ -243,10 +271,21 @@ 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; + +#ifndef NDEBUG + // Remember this state to assert later that a non-infinite register + // option was available. + if (RS == ConservativelyAllocatable) + everConservativelyAllocatable = true; +#endif + } + void handleAddEdge(const MatrixMetadata& MD, bool Transpose) { - DeniedOpts += Transpose ? MD.getWorstCol() : MD.getWorstRow(); + DeniedOpts += Transpose ? MD.getWorstRow() : MD.getWorstCol(); const bool* UnsafeOpts = Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows(); for (unsigned i = 0; i < NumOpts; ++i) @@ -254,7 +293,7 @@ public: } void handleRemoveEdge(const MatrixMetadata& MD, bool Transpose) { - DeniedOpts -= Transpose ? MD.getWorstCol() : MD.getWorstRow(); + DeniedOpts -= Transpose ? MD.getWorstRow() : MD.getWorstCol(); const bool* UnsafeOpts = Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows(); for (unsigned i = 0; i < NumOpts; ++i) @@ -267,6 +306,12 @@ public: &OptUnsafeEdges[NumOpts]); } +#ifndef NDEBUG + bool wasConservativelyAllocatable() const { + return everConservativelyAllocatable; + } +#endif + private: ReductionState RS; unsigned NumOpts; @@ -274,6 +319,10 @@ private: std::unique_ptr OptUnsafeEdges; unsigned VReg; GraphMetadata::AllowedRegVecRef AllowedRegs; + +#ifndef NDEBUG + bool everConservativelyAllocatable; +#endif }; class RegAllocSolverImpl { @@ -307,6 +356,8 @@ public: } void handleAddNode(NodeId NId) { + assert(G.getNodeCosts(NId).getLength() > 1 && + "PBQP Graph should not contain single or zero-option nodes"); G.getNodeMetadata(NId).setup(G.getNodeCosts(NId)); } void handleRemoveNode(NodeId NId) {} @@ -326,15 +377,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) { @@ -343,20 +386,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; @@ -477,8 +544,10 @@ private: public: SpillCostComparator(const Graph& G) : G(G) {} bool operator()(NodeId N1Id, NodeId N2Id) { - PBQPNum N1SC = G.getNodeCosts(N1Id)[0] / G.getNodeDegree(N1Id); - PBQPNum N2SC = G.getNodeCosts(N2Id)[0] / G.getNodeDegree(N2Id); + PBQPNum N1SC = G.getNodeCosts(N1Id)[0]; + PBQPNum N2SC = G.getNodeCosts(N2Id)[0]; + if (N1SC == N2SC) + return G.getNodeDegree(N1Id) < G.getNodeDegree(N2Id); return N1SC < N2SC; } private: @@ -497,6 +566,17 @@ private: typedef PBQP::Graph BaseT; public: PBQPRAGraph(GraphMetadata Metadata) : BaseT(Metadata) {} + + /// @brief Dump this graph to dbgs(). + void dump() const; + + /// @brief Dump this graph to an output stream. + /// @param OS Output stream to print on. + void dump(raw_ostream &OS) const; + + /// @brief Print a representation of this graph in DOT format. + /// @param OS Output stream to print on. + void printDot(raw_ostream &OS) const; }; inline Solution solve(PBQPRAGraph& G) {