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