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   /// 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>
applyR1(GraphT & G,typename GraphT::NodeId NId)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>
applyR2(GraphT & G,typename GraphT::NodeId NId)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>
hasRegisterOptions(const VectorT & V)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   // 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>
backpropagate(GraphT & G,StackT stack)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