1 //===- ReductionRules.h - Reduction Rules -----------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Reduction Rules. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_CODEGEN_PBQP_REDUCTIONRULES_H 14 #define LLVM_CODEGEN_PBQP_REDUCTIONRULES_H 15 16 #include "Graph.h" 17 #include "Math.h" 18 #include "Solution.h" 19 #include <cassert> 20 #include <limits> 21 22 namespace llvm { 23 namespace PBQP { 24 25 /// Reduce a node of degree one. 26 /// 27 /// Propagate costs from the given node, which must be of degree one, to its 28 /// neighbor. Notify the problem domain. 29 template <typename GraphT> applyR1(GraphT & G,typename GraphT::NodeId NId)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; 36 37 assert(G.getNodeDegree(NId) == 1 && 38 "R1 applied to node with degree != 1."); 39 40 EdgeId EId = *G.adjEdgeIds(NId).begin(); 41 NodeId MId = G.getEdgeOtherNodeId(EId, NId); 42 43 const Matrix &ECosts = G.getEdgeCosts(EId); 44 const Vector &XCosts = G.getNodeCosts(NId); 45 RawVector YCosts = G.getNodeCosts(MId); 46 47 // Duplicate a little to avoid transposing matrices. 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]; 53 if (C < Min) 54 Min = C; 55 } 56 YCosts[j] += Min; 57 } 58 } else { 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]; 63 if (C < Min) 64 Min = C; 65 } 66 YCosts[i] += Min; 67 } 68 } 69 G.setNodeCosts(MId, YCosts); 70 G.disconnectEdge(EId, MId); 71 } 72 73 template <typename GraphT> applyR2(GraphT & G,typename GraphT::NodeId NId)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; 80 81 assert(G.getNodeDegree(NId) == 2 && 82 "R2 applied to node with degree != 2."); 83 84 const Vector &XCosts = G.getNodeCosts(NId); 85 86 typename GraphT::AdjEdgeItr AEItr = G.adjEdgeIds(NId).begin(); 87 EdgeId YXEId = *AEItr, 88 ZXEId = *(++AEItr); 89 90 NodeId YNId = G.getEdgeOtherNodeId(YXEId, NId), 91 ZNId = G.getEdgeOtherNodeId(ZXEId, NId); 92 93 bool FlipEdge1 = (G.getEdgeNode1Id(YXEId) == NId), 94 FlipEdge2 = (G.getEdgeNode1Id(ZXEId) == NId); 95 96 const Matrix *YXECosts = FlipEdge1 ? 97 new Matrix(G.getEdgeCosts(YXEId).transpose()) : 98 &G.getEdgeCosts(YXEId); 99 100 const Matrix *ZXECosts = FlipEdge2 ? 101 new Matrix(G.getEdgeCosts(ZXEId).transpose()) : 102 &G.getEdgeCosts(ZXEId); 103 104 unsigned XLen = XCosts.getLength(), 105 YLen = YXECosts->getRows(), 106 ZLen = ZXECosts->getRows(); 107 108 RawMatrix Delta(YLen, ZLen); 109 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]; 115 if (C < Min) { 116 Min = C; 117 } 118 } 119 Delta[i][j] = Min; 120 } 121 } 122 123 if (FlipEdge1) 124 delete YXECosts; 125 126 if (FlipEdge2) 127 delete ZXECosts; 128 129 EdgeId YZEId = G.findEdge(YNId, ZNId); 130 131 if (YZEId == G.invalidEdgeId()) { 132 YZEId = G.addEdge(YNId, ZNId, Delta); 133 } else { 134 const Matrix &YZECosts = G.getEdgeCosts(YZEId); 135 if (YNId == G.getEdgeNode1Id(YZEId)) { 136 G.updateEdgeCosts(YZEId, Delta + YZECosts); 137 } else { 138 G.updateEdgeCosts(YZEId, Delta.transpose() + YZECosts); 139 } 140 } 141 142 G.disconnectEdge(YXEId, YNId); 143 G.disconnectEdge(ZXEId, ZNId); 144 145 // TODO: Try to normalize newly added/modified edge. 146 } 147 148 #ifndef NDEBUG 149 // Does this Cost vector have any register options ? 150 template <typename VectorT> hasRegisterOptions(const VectorT & V)151 bool hasRegisterOptions(const VectorT &V) { 152 unsigned VL = V.getLength(); 153 154 // An empty or spill only cost vector does not provide any register option. 155 if (VL <= 1) 156 return false; 157 158 // If there are registers in the cost vector, but all of them have infinite 159 // costs, then ... there is no available register. 160 for (unsigned i = 1; i < VL; ++i) 161 if (V[i] != std::numeric_limits<PBQP::PBQPNum>::infinity()) 162 return true; 163 164 return false; 165 } 166 #endif 167 168 // Find a solution to a fully reduced graph by backpropagation. 169 // 170 // Given a graph and a reduction order, pop each node from the reduction 171 // order and greedily compute a minimum solution based on the node costs, and 172 // the dependent costs due to previously solved nodes. 173 // 174 // Note - This does not return the graph to its original (pre-reduction) 175 // state: the existing solvers destructively alter the node and edge 176 // costs. Given that, the backpropagate function doesn't attempt to 177 // replace the edges either, but leaves the graph in its reduced 178 // state. 179 template <typename GraphT, typename StackT> backpropagate(GraphT & G,StackT stack)180 Solution backpropagate(GraphT& G, StackT stack) { 181 using NodeId = GraphBase::NodeId; 182 using Matrix = typename GraphT::Matrix; 183 using RawVector = typename GraphT::RawVector; 184 185 Solution s; 186 187 while (!stack.empty()) { 188 NodeId NId = stack.back(); 189 stack.pop_back(); 190 191 RawVector v = G.getNodeCosts(NId); 192 193 #ifndef NDEBUG 194 // Although a conservatively allocatable node can be allocated to a register, 195 // spilling it may provide a lower cost solution. Assert here that spilling 196 // is done by choice, not because there were no register available. 197 if (G.getNodeMetadata(NId).wasConservativelyAllocatable()) 198 assert(hasRegisterOptions(v) && "A conservatively allocatable node " 199 "must have available register options"); 200 #endif 201 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); 206 v += edgeCosts.getColAsVector(s.getSelection(mId)); 207 } else { 208 NodeId mId = G.getEdgeNode1Id(EId); 209 v += edgeCosts.getRowAsVector(s.getSelection(mId)); 210 } 211 } 212 213 s.setSelection(NId, v.minIndex()); 214 } 215 216 return s; 217 } 218 219 } // end namespace PBQP 220 } // end namespace llvm 221 222 #endif // LLVM_CODEGEN_PBQP_REDUCTIONRULES_H 223