1 //===----------- ReductionRules.h - Reduction Rules -------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
15 #define LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
23 /// \brief Reduce a node of degree one.
25 /// Propagate costs from the given node, which must be of degree one, to its
26 /// neighbor. Notify the problem domain.
27 template <typename GraphT>
28 void applyR1(GraphT &G, typename GraphT::NodeId NId) {
29 typedef typename GraphT::NodeId NodeId;
30 typedef typename GraphT::EdgeId EdgeId;
31 typedef typename GraphT::Vector Vector;
32 typedef typename GraphT::Matrix Matrix;
33 typedef typename GraphT::RawVector RawVector;
35 assert(G.getNodeDegree(NId) == 1 &&
36 "R1 applied to node with degree != 1.");
38 EdgeId EId = *G.adjEdgeIds(NId).begin();
39 NodeId MId = G.getEdgeOtherNodeId(EId, NId);
41 const Matrix &ECosts = G.getEdgeCosts(EId);
42 const Vector &XCosts = G.getNodeCosts(NId);
43 RawVector YCosts = G.getNodeCosts(MId);
45 // Duplicate a little to avoid transposing matrices.
46 if (NId == G.getEdgeNode1Id(EId)) {
47 for (unsigned j = 0; j < YCosts.getLength(); ++j) {
48 PBQPNum Min = ECosts[0][j] + XCosts[0];
49 for (unsigned i = 1; i < XCosts.getLength(); ++i) {
50 PBQPNum C = ECosts[i][j] + XCosts[i];
57 for (unsigned i = 0; i < YCosts.getLength(); ++i) {
58 PBQPNum Min = ECosts[i][0] + XCosts[0];
59 for (unsigned j = 1; j < XCosts.getLength(); ++j) {
60 PBQPNum C = ECosts[i][j] + XCosts[j];
67 G.setNodeCosts(MId, YCosts);
68 G.disconnectEdge(EId, MId);
71 template <typename GraphT>
72 void applyR2(GraphT &G, typename GraphT::NodeId NId) {
73 typedef typename GraphT::NodeId NodeId;
74 typedef typename GraphT::EdgeId EdgeId;
75 typedef typename GraphT::Vector Vector;
76 typedef typename GraphT::Matrix Matrix;
77 typedef typename GraphT::RawMatrix RawMatrix;
79 assert(G.getNodeDegree(NId) == 2 &&
80 "R2 applied to node with degree != 2.");
82 const Vector &XCosts = G.getNodeCosts(NId);
84 typename GraphT::AdjEdgeItr AEItr = G.adjEdgeIds(NId).begin();
85 EdgeId YXEId = *AEItr,
88 NodeId YNId = G.getEdgeOtherNodeId(YXEId, NId),
89 ZNId = G.getEdgeOtherNodeId(ZXEId, NId);
91 bool FlipEdge1 = (G.getEdgeNode1Id(YXEId) == NId),
92 FlipEdge2 = (G.getEdgeNode1Id(ZXEId) == NId);
94 const Matrix *YXECosts = FlipEdge1 ?
95 new Matrix(G.getEdgeCosts(YXEId).transpose()) :
96 &G.getEdgeCosts(YXEId);
98 const Matrix *ZXECosts = FlipEdge2 ?
99 new Matrix(G.getEdgeCosts(ZXEId).transpose()) :
100 &G.getEdgeCosts(ZXEId);
102 unsigned XLen = XCosts.getLength(),
103 YLen = YXECosts->getRows(),
104 ZLen = ZXECosts->getRows();
106 RawMatrix Delta(YLen, ZLen);
108 for (unsigned i = 0; i < YLen; ++i) {
109 for (unsigned j = 0; j < ZLen; ++j) {
110 PBQPNum Min = (*YXECosts)[i][0] + (*ZXECosts)[j][0] + XCosts[0];
111 for (unsigned k = 1; k < XLen; ++k) {
112 PBQPNum C = (*YXECosts)[i][k] + (*ZXECosts)[j][k] + XCosts[k];
127 EdgeId YZEId = G.findEdge(YNId, ZNId);
129 if (YZEId == G.invalidEdgeId()) {
130 YZEId = G.addEdge(YNId, ZNId, Delta);
132 const Matrix &YZECosts = G.getEdgeCosts(YZEId);
133 if (YNId == G.getEdgeNode1Id(YZEId)) {
134 G.setEdgeCosts(YZEId, Delta + YZECosts);
136 G.setEdgeCosts(YZEId, Delta.transpose() + YZECosts);
140 G.disconnectEdge(YXEId, YNId);
141 G.disconnectEdge(ZXEId, ZNId);
143 // TODO: Try to normalize newly added/modified edge.
147 // \brief Find a solution to a fully reduced graph by backpropagation.
149 // Given a graph and a reduction order, pop each node from the reduction
150 // order and greedily compute a minimum solution based on the node costs, and
151 // the dependent costs due to previously solved nodes.
153 // Note - This does not return the graph to its original (pre-reduction)
154 // state: the existing solvers destructively alter the node and edge
155 // costs. Given that, the backpropagate function doesn't attempt to
156 // replace the edges either, but leaves the graph in its reduced
158 template <typename GraphT, typename StackT>
159 Solution backpropagate(GraphT& G, StackT stack) {
160 typedef GraphBase::NodeId NodeId;
161 typedef typename GraphT::Matrix Matrix;
162 typedef typename GraphT::RawVector RawVector;
166 while (!stack.empty()) {
167 NodeId NId = stack.back();
170 RawVector v = G.getNodeCosts(NId);
172 for (auto EId : G.adjEdgeIds(NId)) {
173 const Matrix& edgeCosts = G.getEdgeCosts(EId);
174 if (NId == G.getEdgeNode1Id(EId)) {
175 NodeId mId = G.getEdgeNode2Id(EId);
176 v += edgeCosts.getColAsVector(s.getSelection(mId));
178 NodeId mId = G.getEdgeNode1Id(EId);
179 v += edgeCosts.getRowAsVector(s.getSelection(mId));
183 s.setSelection(NId, v.minIndex());