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