/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/CodeGen/PBQP/ReductionRules.h
Line | Count | Source (jump to first uncovered line) |
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 | 12 | void applyR1(GraphT &G, typename GraphT::NodeId NId) { |
32 | 12 | using NodeId = typename GraphT::NodeId; |
33 | 12 | using EdgeId = typename GraphT::EdgeId; |
34 | 12 | using Vector = typename GraphT::Vector; |
35 | 12 | using Matrix = typename GraphT::Matrix; |
36 | 12 | using RawVector = typename GraphT::RawVector; |
37 | 12 | |
38 | 12 | assert(G.getNodeDegree(NId) == 1 && |
39 | 12 | "R1 applied to node with degree != 1."); |
40 | 12 | |
41 | 12 | EdgeId EId = *G.adjEdgeIds(NId).begin(); |
42 | 12 | NodeId MId = G.getEdgeOtherNodeId(EId, NId); |
43 | 12 | |
44 | 12 | const Matrix &ECosts = G.getEdgeCosts(EId); |
45 | 12 | const Vector &XCosts = G.getNodeCosts(NId); |
46 | 12 | RawVector YCosts = G.getNodeCosts(MId); |
47 | 12 | |
48 | 12 | // Duplicate a little to avoid transposing matrices. |
49 | 12 | if (NId == G.getEdgeNode1Id(EId)12 ) { |
50 | 206 | for (unsigned j = 0; j < YCosts.getLength()206 ; ++j197 ) { |
51 | 197 | PBQPNum Min = ECosts[0][j] + XCosts[0]; |
52 | 5.94k | for (unsigned i = 1; i < XCosts.getLength()5.94k ; ++i5.74k ) { |
53 | 5.74k | PBQPNum C = ECosts[i][j] + XCosts[i]; |
54 | 5.74k | if (C < Min) |
55 | 209 | Min = C; |
56 | 5.74k | } |
57 | 197 | YCosts[j] += Min; |
58 | 197 | } |
59 | 12 | } else { |
60 | 99 | for (unsigned i = 0; i < YCosts.getLength()99 ; ++i96 ) { |
61 | 96 | PBQPNum Min = ECosts[i][0] + XCosts[0]; |
62 | 2.97k | for (unsigned j = 1; j < XCosts.getLength()2.97k ; ++j2.88k ) { |
63 | 2.88k | PBQPNum C = ECosts[i][j] + XCosts[j]; |
64 | 2.88k | if (C < Min) |
65 | 189 | Min = C; |
66 | 2.88k | } |
67 | 96 | YCosts[i] += Min; |
68 | 96 | } |
69 | 3 | } |
70 | 12 | G.setNodeCosts(MId, YCosts); |
71 | 12 | G.disconnectEdge(EId, MId); |
72 | 12 | } |
73 | | |
74 | | template <typename GraphT> |
75 | 39 | void applyR2(GraphT &G, typename GraphT::NodeId NId) { |
76 | 39 | using NodeId = typename GraphT::NodeId; |
77 | 39 | using EdgeId = typename GraphT::EdgeId; |
78 | 39 | using Vector = typename GraphT::Vector; |
79 | 39 | using Matrix = typename GraphT::Matrix; |
80 | 39 | using RawMatrix = typename GraphT::RawMatrix; |
81 | 39 | |
82 | 39 | assert(G.getNodeDegree(NId) == 2 && |
83 | 39 | "R2 applied to node with degree != 2."); |
84 | 39 | |
85 | 39 | const Vector &XCosts = G.getNodeCosts(NId); |
86 | 39 | |
87 | 39 | typename GraphT::AdjEdgeItr AEItr = G.adjEdgeIds(NId).begin(); |
88 | 39 | EdgeId YXEId = *AEItr, |
89 | 39 | ZXEId = *(++AEItr); |
90 | 39 | |
91 | 39 | NodeId YNId = G.getEdgeOtherNodeId(YXEId, NId), |
92 | 39 | ZNId = G.getEdgeOtherNodeId(ZXEId, NId); |
93 | 39 | |
94 | 39 | bool FlipEdge1 = (G.getEdgeNode1Id(YXEId) == NId), |
95 | 39 | FlipEdge2 = (G.getEdgeNode1Id(ZXEId) == NId); |
96 | 39 | |
97 | 39 | const Matrix *YXECosts = FlipEdge1 ? |
98 | 37 | new Matrix(G.getEdgeCosts(YXEId).transpose()) : |
99 | 2 | &G.getEdgeCosts(YXEId); |
100 | 39 | |
101 | 39 | const Matrix *ZXECosts = FlipEdge2 ? |
102 | 37 | new Matrix(G.getEdgeCosts(ZXEId).transpose()) : |
103 | 2 | &G.getEdgeCosts(ZXEId); |
104 | 39 | |
105 | 39 | unsigned XLen = XCosts.getLength(), |
106 | 39 | YLen = YXECosts->getRows(), |
107 | 39 | ZLen = ZXECosts->getRows(); |
108 | 39 | |
109 | 39 | RawMatrix Delta(YLen, ZLen); |
110 | 39 | |
111 | 1.26k | for (unsigned i = 0; i < YLen1.26k ; ++i1.22k ) { |
112 | 39.1k | for (unsigned j = 0; j < ZLen39.1k ; ++j37.9k ) { |
113 | 37.9k | PBQPNum Min = (*YXECosts)[i][0] + (*ZXECosts)[j][0] + XCosts[0]; |
114 | 1.23M | for (unsigned k = 1; k < XLen1.23M ; ++k1.20M ) { |
115 | 1.20M | PBQPNum C = (*YXECosts)[i][k] + (*ZXECosts)[j][k] + XCosts[k]; |
116 | 1.20M | if (C < Min1.20M ) { |
117 | 43.9k | Min = C; |
118 | 43.9k | } |
119 | 1.20M | } |
120 | 37.9k | Delta[i][j] = Min; |
121 | 37.9k | } |
122 | 1.22k | } |
123 | 39 | |
124 | 39 | if (FlipEdge1) |
125 | 37 | delete YXECosts; |
126 | 39 | |
127 | 39 | if (FlipEdge2) |
128 | 37 | delete ZXECosts; |
129 | 39 | |
130 | 39 | EdgeId YZEId = G.findEdge(YNId, ZNId); |
131 | 39 | |
132 | 39 | if (YZEId == G.invalidEdgeId()39 ) { |
133 | 0 | YZEId = G.addEdge(YNId, ZNId, Delta); |
134 | 39 | } else { |
135 | 39 | const Matrix &YZECosts = G.getEdgeCosts(YZEId); |
136 | 39 | if (YNId == G.getEdgeNode1Id(YZEId)39 ) { |
137 | 21 | G.updateEdgeCosts(YZEId, Delta + YZECosts); |
138 | 39 | } else { |
139 | 18 | G.updateEdgeCosts(YZEId, Delta.transpose() + YZECosts); |
140 | 18 | } |
141 | 39 | } |
142 | 39 | |
143 | 39 | G.disconnectEdge(YXEId, YNId); |
144 | 39 | G.disconnectEdge(ZXEId, ZNId); |
145 | 39 | |
146 | 39 | // TODO: Try to normalize newly added/modified edge. |
147 | 39 | } |
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 | 8 | Solution backpropagate(GraphT& G, StackT stack) { |
182 | 8 | using NodeId = GraphBase::NodeId; |
183 | 8 | using Matrix = typename GraphT::Matrix; |
184 | 8 | using RawVector = typename GraphT::RawVector; |
185 | 8 | |
186 | 8 | Solution s; |
187 | 8 | |
188 | 163 | while (!stack.empty()163 ) { |
189 | 155 | NodeId NId = stack.back(); |
190 | 155 | stack.pop_back(); |
191 | 155 | |
192 | 155 | RawVector v = G.getNodeCosts(NId); |
193 | 155 | |
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 | 564 | for (auto EId : G.adjEdgeIds(NId)) { |
204 | 564 | const Matrix& edgeCosts = G.getEdgeCosts(EId); |
205 | 564 | if (NId == G.getEdgeNode1Id(EId)564 ) { |
206 | 327 | NodeId mId = G.getEdgeNode2Id(EId); |
207 | 327 | v += edgeCosts.getColAsVector(s.getSelection(mId)); |
208 | 564 | } else { |
209 | 237 | NodeId mId = G.getEdgeNode1Id(EId); |
210 | 237 | v += edgeCosts.getRowAsVector(s.getSelection(mId)); |
211 | 237 | } |
212 | 564 | } |
213 | 155 | |
214 | 155 | s.setSelection(NId, v.minIndex()); |
215 | 155 | } |
216 | 8 | |
217 | 8 | return s; |
218 | 8 | } |
219 | | |
220 | | } // end namespace PBQP |
221 | | } // end namespace llvm |
222 | | |
223 | | #endif // LLVM_CODEGEN_PBQP_REDUCTIONRULES_H |