aboutsummaryrefslogtreecommitdiffstats
path: root/include/llvm/CodeGen/RegAllocPBQP.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/CodeGen/RegAllocPBQP.h')
-rw-r--r--include/llvm/CodeGen/RegAllocPBQP.h132
1 files changed, 105 insertions, 27 deletions
diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h
index 540af08..c7bb07b 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 {
@@ -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<unsigned[]> 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;
@@ -497,6 +564,17 @@ private:
typedef PBQP::Graph<RegAllocSolverImpl> 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) {
generated by cgit v1.1 at 2024-12-22 11:48:47 +0000