13#ifndef LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
14#define LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
29 template <
typename GraphT>
30 void applyR1(GraphT &
G,
typename GraphT::NodeId NId) {
31 using NodeId =
typename GraphT::NodeId;
32 using EdgeId =
typename GraphT::EdgeId;
33 using Vector =
typename GraphT::Vector;
34 using Matrix =
typename GraphT::Matrix;
35 using RawVector =
typename GraphT::RawVector;
37 assert(
G.getNodeDegree(NId) == 1 &&
38 "R1 applied to node with degree != 1.");
40 EdgeId EId = *
G.adjEdgeIds(NId).begin();
41 NodeId MId =
G.getEdgeOtherNodeId(EId, NId);
43 const Matrix &ECosts =
G.getEdgeCosts(EId);
44 const Vector &XCosts =
G.getNodeCosts(NId);
45 RawVector YCosts =
G.getNodeCosts(MId);
48 if (NId ==
G.getEdgeNode1Id(EId)) {
49 for (
unsigned j = 0; j < YCosts.getLength(); ++j) {
50 PBQPNum Min = ECosts[0][j] + XCosts[0];
51 for (
unsigned i = 1; i < XCosts.getLength(); ++i) {
52 PBQPNum C = ECosts[i][j] + XCosts[i];
59 for (
unsigned i = 0; i < YCosts.getLength(); ++i) {
60 PBQPNum Min = ECosts[i][0] + XCosts[0];
61 for (
unsigned j = 1; j < XCosts.getLength(); ++j) {
62 PBQPNum C = ECosts[i][j] + XCosts[j];
69 G.setNodeCosts(MId, YCosts);
70 G.disconnectEdge(EId, MId);
73 template <
typename GraphT>
74 void applyR2(GraphT &
G,
typename GraphT::NodeId NId) {
75 using NodeId =
typename GraphT::NodeId;
76 using EdgeId =
typename GraphT::EdgeId;
77 using Vector =
typename GraphT::Vector;
78 using Matrix =
typename GraphT::Matrix;
79 using RawMatrix =
typename GraphT::RawMatrix;
81 assert(
G.getNodeDegree(NId) == 2 &&
82 "R2 applied to node with degree != 2.");
84 const Vector &XCosts =
G.getNodeCosts(NId);
86 typename GraphT::AdjEdgeItr AEItr =
G.adjEdgeIds(NId).begin();
87 EdgeId YXEId = *AEItr,
90 NodeId YNId =
G.getEdgeOtherNodeId(YXEId, NId),
91 ZNId =
G.getEdgeOtherNodeId(ZXEId, NId);
93 bool FlipEdge1 = (
G.getEdgeNode1Id(YXEId) == NId),
94 FlipEdge2 = (
G.getEdgeNode1Id(ZXEId) == NId);
96 const Matrix *YXECosts = FlipEdge1 ?
97 new Matrix(
G.getEdgeCosts(YXEId).transpose()) :
98 &
G.getEdgeCosts(YXEId);
100 const Matrix *ZXECosts = FlipEdge2 ?
101 new Matrix(
G.getEdgeCosts(ZXEId).transpose()) :
102 &
G.getEdgeCosts(ZXEId);
108 RawMatrix Delta(YLen, ZLen);
110 for (
unsigned i = 0; i < YLen; ++i) {
111 for (
unsigned j = 0; j < ZLen; ++j) {
112 PBQPNum Min = (*YXECosts)[i][0] + (*ZXECosts)[j][0] + XCosts[0];
113 for (
unsigned k = 1; k < XLen; ++k) {
114 PBQPNum C = (*YXECosts)[i][k] + (*ZXECosts)[j][k] + XCosts[k];
129 EdgeId YZEId =
G.findEdge(YNId, ZNId);
131 if (YZEId ==
G.invalidEdgeId()) {
132 YZEId =
G.addEdge(YNId, ZNId, Delta);
134 const Matrix &YZECosts =
G.getEdgeCosts(YZEId);
135 if (YNId ==
G.getEdgeNode1Id(YZEId)) {
136 G.updateEdgeCosts(YZEId, Delta + YZECosts);
138 G.updateEdgeCosts(YZEId, Delta.transpose() + YZECosts);
142 G.disconnectEdge(YXEId, YNId);
143 G.disconnectEdge(ZXEId, ZNId);
150 template <
typename VectorT>
152 unsigned VL = V.getLength();
160 for (
unsigned i = 1; i < VL; ++i)
161 if (V[i] != std::numeric_limits<PBQP::PBQPNum>::infinity())
179 template <
typename GraphT,
typename StackT>
182 using Matrix =
typename GraphT::Matrix;
183 using RawVector =
typename GraphT::RawVector;
187 while (!stack.empty()) {
188 NodeId NId = stack.back();
191 RawVector v =
G.getNodeCosts(NId);
193#if LLVM_ENABLE_ABI_BREAKING_CHECKS
197 if (
G.getNodeMetadata(NId).wasConservativelyAllocatable())
199 "must have available register options");
202 for (
auto EId :
G.adjEdgeIds(NId)) {
203 const Matrix& edgeCosts =
G.getEdgeCosts(EId);
204 if (NId ==
G.getEdgeNode1Id(EId)) {
205 NodeId mId =
G.getEdgeNode2Id(EId);
208 NodeId mId =
G.getEdgeNode1Id(EId);
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getRows() const
Return the number of rows in this matrix.
Vector getColAsVector(unsigned C) const
Returns the given column as a vector.
Vector getRowAsVector(unsigned R) const
Returns the given row as a vector.
Represents a solution to a PBQP problem.
void setSelection(GraphBase::NodeId nodeId, unsigned selection)
Set the selection for a given node.
unsigned getSelection(GraphBase::NodeId nodeId) const
Get a node's selection.
unsigned getLength() const
Return the length of the vector.
@ C
The default llvm calling convention, compatible with C.
void applyR2(GraphT &G, typename GraphT::NodeId NId)
void applyR1(GraphT &G, typename GraphT::NodeId NId)
Reduce a node of degree one.
Solution backpropagate(GraphT &G, StackT stack)
bool hasRegisterOptions(const VectorT &V)
This is an optimization pass for GlobalISel generic memory operations.