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
23namespace llvm {
24namespace 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  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>
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>
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  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