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 | 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> |
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> |
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 | 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 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS |
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(nodeId: mId)); |
207 | } else { |
208 | NodeId mId = G.getEdgeNode1Id(EId); |
209 | v += edgeCosts.getRowAsVector(s.getSelection(nodeId: mId)); |
210 | } |
211 | } |
212 | |
213 | s.setSelection(nodeId: NId, selection: 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 | |