/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/PBQP/ReductionRules.h
Line | Count | Source (jump to first uncovered line) |
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> |
30 | 20 | void applyR1(GraphT &G, typename GraphT::NodeId NId) { |
31 | 20 | using NodeId = typename GraphT::NodeId; |
32 | 20 | using EdgeId = typename GraphT::EdgeId; |
33 | 20 | using Vector = typename GraphT::Vector; |
34 | 20 | using Matrix = typename GraphT::Matrix; |
35 | 20 | using RawVector = typename GraphT::RawVector; |
36 | 20 | |
37 | 20 | assert(G.getNodeDegree(NId) == 1 && |
38 | 20 | "R1 applied to node with degree != 1."); |
39 | 20 | |
40 | 20 | EdgeId EId = *G.adjEdgeIds(NId).begin(); |
41 | 20 | NodeId MId = G.getEdgeOtherNodeId(EId, NId); |
42 | 20 | |
43 | 20 | const Matrix &ECosts = G.getEdgeCosts(EId); |
44 | 20 | const Vector &XCosts = G.getNodeCosts(NId); |
45 | 20 | RawVector YCosts = G.getNodeCosts(MId); |
46 | 20 | |
47 | 20 | // Duplicate a little to avoid transposing matrices. |
48 | 20 | if (NId == G.getEdgeNode1Id(EId)) { |
49 | 293 | for (unsigned j = 0; j < YCosts.getLength(); ++j284 ) { |
50 | 284 | PBQPNum Min = ECosts[0][j] + XCosts[0]; |
51 | 9.05k | for (unsigned i = 1; i < XCosts.getLength(); ++i8.76k ) { |
52 | 8.76k | PBQPNum C = ECosts[i][j] + XCosts[i]; |
53 | 8.76k | if (C < Min) |
54 | 372 | Min = C; |
55 | 8.76k | } |
56 | 284 | YCosts[j] += Min; |
57 | 284 | } |
58 | 11 | } else { |
59 | 316 | for (unsigned i = 0; i < YCosts.getLength(); ++i305 ) { |
60 | 305 | PBQPNum Min = ECosts[i][0] + XCosts[0]; |
61 | 9.52k | for (unsigned j = 1; j < XCosts.getLength(); ++j9.22k ) { |
62 | 9.22k | PBQPNum C = ECosts[i][j] + XCosts[j]; |
63 | 9.22k | if (C < Min) |
64 | 305 | Min = C; |
65 | 9.22k | } |
66 | 305 | YCosts[i] += Min; |
67 | 305 | } |
68 | 11 | } |
69 | 20 | G.setNodeCosts(MId, YCosts); |
70 | 20 | G.disconnectEdge(EId, MId); |
71 | 20 | } |
72 | | |
73 | | template <typename GraphT> |
74 | 33 | void applyR2(GraphT &G, typename GraphT::NodeId NId) { |
75 | 33 | using NodeId = typename GraphT::NodeId; |
76 | 33 | using EdgeId = typename GraphT::EdgeId; |
77 | 33 | using Vector = typename GraphT::Vector; |
78 | 33 | using Matrix = typename GraphT::Matrix; |
79 | 33 | using RawMatrix = typename GraphT::RawMatrix; |
80 | 33 | |
81 | 33 | assert(G.getNodeDegree(NId) == 2 && |
82 | 33 | "R2 applied to node with degree != 2."); |
83 | 33 | |
84 | 33 | const Vector &XCosts = G.getNodeCosts(NId); |
85 | 33 | |
86 | 33 | typename GraphT::AdjEdgeItr AEItr = G.adjEdgeIds(NId).begin(); |
87 | 33 | EdgeId YXEId = *AEItr, |
88 | 33 | ZXEId = *(++AEItr); |
89 | 33 | |
90 | 33 | NodeId YNId = G.getEdgeOtherNodeId(YXEId, NId), |
91 | 33 | ZNId = G.getEdgeOtherNodeId(ZXEId, NId); |
92 | 33 | |
93 | 33 | bool FlipEdge1 = (G.getEdgeNode1Id(YXEId) == NId), |
94 | 33 | FlipEdge2 = (G.getEdgeNode1Id(ZXEId) == NId); |
95 | 33 | |
96 | 33 | const Matrix *YXECosts = FlipEdge1 ? |
97 | 4 | new Matrix(G.getEdgeCosts(YXEId).transpose()) : |
98 | 33 | &G.getEdgeCosts(YXEId)29 ; |
99 | 33 | |
100 | 33 | const Matrix *ZXECosts = FlipEdge2 ? |
101 | 19 | new Matrix(G.getEdgeCosts(ZXEId).transpose()) : |
102 | 33 | &G.getEdgeCosts(ZXEId)14 ; |
103 | 33 | |
104 | 33 | unsigned XLen = XCosts.getLength(), |
105 | 33 | YLen = YXECosts->getRows(), |
106 | 33 | ZLen = ZXECosts->getRows(); |
107 | 33 | |
108 | 33 | RawMatrix Delta(YLen, ZLen); |
109 | 33 | |
110 | 1.05k | for (unsigned i = 0; i < YLen; ++i1.02k ) { |
111 | 34.0k | for (unsigned j = 0; j < ZLen; ++j33.0k ) { |
112 | 33.0k | PBQPNum Min = (*YXECosts)[i][0] + (*ZXECosts)[j][0] + XCosts[0]; |
113 | 1.07M | for (unsigned k = 1; k < XLen; ++k1.04M ) { |
114 | 1.04M | PBQPNum C = (*YXECosts)[i][k] + (*ZXECosts)[j][k] + XCosts[k]; |
115 | 1.04M | if (C < Min) { |
116 | 36.5k | Min = C; |
117 | 36.5k | } |
118 | 1.04M | } |
119 | 33.0k | Delta[i][j] = Min; |
120 | 33.0k | } |
121 | 1.02k | } |
122 | 33 | |
123 | 33 | if (FlipEdge1) |
124 | 4 | delete YXECosts; |
125 | 33 | |
126 | 33 | if (FlipEdge2) |
127 | 19 | delete ZXECosts; |
128 | 33 | |
129 | 33 | EdgeId YZEId = G.findEdge(YNId, ZNId); |
130 | 33 | |
131 | 33 | if (YZEId == G.invalidEdgeId()) { |
132 | 0 | YZEId = G.addEdge(YNId, ZNId, Delta); |
133 | 33 | } else { |
134 | 33 | const Matrix &YZECosts = G.getEdgeCosts(YZEId); |
135 | 33 | if (YNId == G.getEdgeNode1Id(YZEId)) { |
136 | 30 | G.updateEdgeCosts(YZEId, Delta + YZECosts); |
137 | 30 | } else { |
138 | 3 | G.updateEdgeCosts(YZEId, Delta.transpose() + YZECosts); |
139 | 3 | } |
140 | 33 | } |
141 | 33 | |
142 | 33 | G.disconnectEdge(YXEId, YNId); |
143 | 33 | G.disconnectEdge(ZXEId, ZNId); |
144 | 33 | |
145 | 33 | // TODO: Try to normalize newly added/modified edge. |
146 | 33 | } |
147 | | |
148 | | #ifndef NDEBUG |
149 | | // Does this Cost vector have any register options ? |
150 | | template <typename VectorT> |
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> |
180 | 8 | Solution backpropagate(GraphT& G, StackT stack) { |
181 | 8 | using NodeId = GraphBase::NodeId; |
182 | 8 | using Matrix = typename GraphT::Matrix; |
183 | 8 | using RawVector = typename GraphT::RawVector; |
184 | 8 | |
185 | 8 | Solution s; |
186 | 8 | |
187 | 161 | while (!stack.empty()) { |
188 | 153 | NodeId NId = stack.back(); |
189 | 153 | stack.pop_back(); |
190 | 153 | |
191 | 153 | RawVector v = G.getNodeCosts(NId); |
192 | 153 | |
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 | 559 | for (auto EId : G.adjEdgeIds(NId)) { |
203 | 559 | const Matrix& edgeCosts = G.getEdgeCosts(EId); |
204 | 559 | if (NId == G.getEdgeNode1Id(EId)) { |
205 | 168 | NodeId mId = G.getEdgeNode2Id(EId); |
206 | 168 | v += edgeCosts.getColAsVector(s.getSelection(mId)); |
207 | 391 | } else { |
208 | 391 | NodeId mId = G.getEdgeNode1Id(EId); |
209 | 391 | v += edgeCosts.getRowAsVector(s.getSelection(mId)); |
210 | 391 | } |
211 | 559 | } |
212 | 153 | |
213 | 153 | s.setSelection(NId, v.minIndex()); |
214 | 153 | } |
215 | 8 | |
216 | 8 | return s; |
217 | 8 | } |
218 | | |
219 | | } // end namespace PBQP |
220 | | } // end namespace llvm |
221 | | |
222 | | #endif // LLVM_CODEGEN_PBQP_REDUCTIONRULES_H |