LLVM  8.0.0svn
ReductionRules.h
Go to the documentation of this file.
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>
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  // 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
uint64_t CallInst * C
Represents a solution to a PBQP problem.
Definition: Solution.h:27
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
uint32_t NodeId
Definition: RDFGraph.h:261
Vector getRowAsVector(unsigned R) const
Returns the given row as a vector.
Definition: Math.h:188
Live Register Matrix
float PBQPNum
Definition: Math.h:23
Vector getColAsVector(unsigned C) const
Returns the given column as a vector.
Definition: Math.h:197
unsigned getRows() const
Return the number of rows in this matrix.
Definition: Math.h:162
void applyR1(GraphT &G, typename GraphT::NodeId NId)
Reduce a node of degree one.
unsigned NodeId
Definition: Graph.h:29
PBQP Matrix class.
Definition: Math.h:122
PBQP Vector class.
Definition: Math.h:26
bool hasRegisterOptions(const VectorT &V)
Solution backpropagate(GraphT &G, StackT stack)
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
void setSelection(GraphBase::NodeId nodeId, unsigned selection)
Set the selection for a given node.
Definition: Solution.h:39
unsigned getSelection(GraphBase::NodeId nodeId) const
Get a node&#39;s selection.
Definition: Solution.h:46
void applyR2(GraphT &G, typename GraphT::NodeId NId)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())