LLVM  10.0.0svn
ReductionRules.h
Go to the documentation of this file.
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 #ifndef NDEBUG
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(mId));
207  } else {
208  NodeId mId = G.getEdgeNode1Id(EId);
209  v += edgeCosts.getRowAsVector(s.getSelection(mId));
210  }
211  }
212 
213  s.setSelection(NId, 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
uint64_t CallInst * C
Represents a solution to a PBQP problem.
Definition: Solution.h:26
This class represents lattice values for constants.
Definition: AllocatorList.h:23
uint32_t NodeId
Definition: RDFGraph.h:260
Vector getRowAsVector(unsigned R) const
Returns the given row as a vector.
Definition: Math.h:187
Live Register Matrix
float PBQPNum
Definition: Math.h:22
Vector getColAsVector(unsigned C) const
Returns the given column as a vector.
Definition: Math.h:196
unsigned getRows() const
Return the number of rows in this matrix.
Definition: Math.h:161
void applyR1(GraphT &G, typename GraphT::NodeId NId)
Reduce a node of degree one.
unsigned NodeId
Definition: Graph.h:28
PBQP Matrix class.
Definition: Math.h:121
PBQP Vector class.
Definition: Math.h:25
bool hasRegisterOptions(const VectorT &V)
Solution backpropagate(GraphT &G, StackT stack)
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
void setSelection(GraphBase::NodeId nodeId, unsigned selection)
Set the selection for a given node.
Definition: Solution.h:38
unsigned getSelection(GraphBase::NodeId nodeId) const
Get a node&#39;s selection.
Definition: Solution.h:45
void applyR2(GraphT &G, typename GraphT::NodeId NId)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())