LLVM  7.0.0svn
RegAllocPBQP.h
Go to the documentation of this file.
1 //===- RegAllocPBQP.h -------------------------------------------*- 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 // This file defines the PBQPBuilder interface, for classes which build PBQP
11 // instances to represent register allocation problems, and the RegAllocPBQP
12 // interface.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_CODEGEN_REGALLOCPBQP_H
17 #define LLVM_CODEGEN_REGALLOCPBQP_H
18 
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/Hashing.h"
23 #include "llvm/CodeGen/PBQP/Math.h"
27 #include <algorithm>
28 #include <cassert>
29 #include <cstddef>
30 #include <limits>
31 #include <memory>
32 #include <set>
33 #include <vector>
34 
35 namespace llvm {
36 
37 class FunctionPass;
38 class LiveIntervals;
39 class MachineBlockFrequencyInfo;
40 class MachineFunction;
41 class raw_ostream;
42 
43 namespace PBQP {
44 namespace RegAlloc {
45 
46 /// @brief Spill option index.
47 inline unsigned getSpillOptionIdx() { return 0; }
48 
49 /// \brief Metadata to speed allocatability test.
50 ///
51 /// Keeps track of the number of infinities in each row and column.
53 public:
55  : UnsafeRows(new bool[M.getRows() - 1]()),
56  UnsafeCols(new bool[M.getCols() - 1]()) {
57  unsigned* ColCounts = new unsigned[M.getCols() - 1]();
58 
59  for (unsigned i = 1; i < M.getRows(); ++i) {
60  unsigned RowCount = 0;
61  for (unsigned j = 1; j < M.getCols(); ++j) {
62  if (M[i][j] == std::numeric_limits<PBQPNum>::infinity()) {
63  ++RowCount;
64  ++ColCounts[j - 1];
65  UnsafeRows[i - 1] = true;
66  UnsafeCols[j - 1] = true;
67  }
68  }
69  WorstRow = std::max(WorstRow, RowCount);
70  }
71  unsigned WorstColCountForCurRow =
72  *std::max_element(ColCounts, ColCounts + M.getCols() - 1);
73  WorstCol = std::max(WorstCol, WorstColCountForCurRow);
74  delete[] ColCounts;
75  }
76 
77  MatrixMetadata(const MatrixMetadata &) = delete;
78  MatrixMetadata &operator=(const MatrixMetadata &) = delete;
79 
80  unsigned getWorstRow() const { return WorstRow; }
81  unsigned getWorstCol() const { return WorstCol; }
82  const bool* getUnsafeRows() const { return UnsafeRows.get(); }
83  const bool* getUnsafeCols() const { return UnsafeCols.get(); }
84 
85 private:
86  unsigned WorstRow = 0;
87  unsigned WorstCol = 0;
88  std::unique_ptr<bool[]> UnsafeRows;
89  std::unique_ptr<bool[]> UnsafeCols;
90 };
91 
92 /// \brief Holds a vector of the allowed physical regs for a vreg.
94  friend hash_code hash_value(const AllowedRegVector &);
95 
96 public:
97  AllowedRegVector() = default;
98  AllowedRegVector(AllowedRegVector &&) = default;
99 
100  AllowedRegVector(const std::vector<unsigned> &OptVec)
101  : NumOpts(OptVec.size()), Opts(new unsigned[NumOpts]) {
102  std::copy(OptVec.begin(), OptVec.end(), Opts.get());
103  }
104 
105  unsigned size() const { return NumOpts; }
106  unsigned operator[](size_t I) const { return Opts[I]; }
107 
108  bool operator==(const AllowedRegVector &Other) const {
109  if (NumOpts != Other.NumOpts)
110  return false;
111  return std::equal(Opts.get(), Opts.get() + NumOpts, Other.Opts.get());
112  }
113 
114  bool operator!=(const AllowedRegVector &Other) const {
115  return !(*this == Other);
116  }
117 
118 private:
119  unsigned NumOpts = 0;
120  std::unique_ptr<unsigned[]> Opts;
121 };
122 
123 inline hash_code hash_value(const AllowedRegVector &OptRegs) {
124  unsigned *OStart = OptRegs.Opts.get();
125  unsigned *OEnd = OptRegs.Opts.get() + OptRegs.NumOpts;
126  return hash_combine(OptRegs.NumOpts,
127  hash_combine_range(OStart, OEnd));
128 }
129 
130 /// \brief Holds graph-level metadata relevant to PBQP RA problems.
132 private:
134 
135 public:
137 
139  LiveIntervals &LIS,
141  : MF(MF), LIS(LIS), MBFI(MBFI) {}
142 
146 
147  void setNodeIdForVReg(unsigned VReg, GraphBase::NodeId NId) {
148  VRegToNodeId[VReg] = NId;
149  }
150 
151  GraphBase::NodeId getNodeIdForVReg(unsigned VReg) const {
152  auto VRegItr = VRegToNodeId.find(VReg);
153  if (VRegItr == VRegToNodeId.end())
154  return GraphBase::invalidNodeId();
155  return VRegItr->second;
156  }
157 
159  return AllowedRegVecs.getValue(std::move(Allowed));
160  }
161 
162 private:
164  AllowedRegVecPool AllowedRegVecs;
165 };
166 
167 /// \brief Holds solver state and other metadata relevant to each PBQP RA node.
169 public:
171 
172  // The node's reduction state. The order in this enum is important,
173  // as it is assumed nodes can only progress up (i.e. towards being
174  // optimally reducible) when reducing the graph.
175  using ReductionState = enum {
176  Unprocessed,
177  NotProvablyAllocatable,
178  ConservativelyAllocatable,
179  OptimallyReducible
180  };
181 
182  NodeMetadata() = default;
183 
185  : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts),
186  OptUnsafeEdges(new unsigned[NumOpts]), VReg(Other.VReg),
187  AllowedRegs(Other.AllowedRegs)
188 #ifndef NDEBUG
189  , everConservativelyAllocatable(Other.everConservativelyAllocatable)
190 #endif
191  {
192  if (NumOpts > 0) {
193  std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts],
194  &OptUnsafeEdges[0]);
195  }
196  }
197 
198  NodeMetadata(NodeMetadata &&) = default;
199  NodeMetadata& operator=(NodeMetadata &&) = default;
200 
201  void setVReg(unsigned VReg) { this->VReg = VReg; }
202  unsigned getVReg() const { return VReg; }
203 
205  this->AllowedRegs = std::move(AllowedRegs);
206  }
207  const AllowedRegVector& getAllowedRegs() const { return *AllowedRegs; }
208 
209  void setup(const Vector& Costs) {
210  NumOpts = Costs.getLength() - 1;
211  OptUnsafeEdges = std::unique_ptr<unsigned[]>(new unsigned[NumOpts]());
212  }
213 
214  ReductionState getReductionState() const { return RS; }
216  assert(RS >= this->RS && "A node's reduction state can not be downgraded");
217  this->RS = RS;
218 
219 #ifndef NDEBUG
220  // Remember this state to assert later that a non-infinite register
221  // option was available.
222  if (RS == ConservativelyAllocatable)
223  everConservativelyAllocatable = true;
224 #endif
225  }
226 
227  void handleAddEdge(const MatrixMetadata& MD, bool Transpose) {
228  DeniedOpts += Transpose ? MD.getWorstRow() : MD.getWorstCol();
229  const bool* UnsafeOpts =
230  Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
231  for (unsigned i = 0; i < NumOpts; ++i)
232  OptUnsafeEdges[i] += UnsafeOpts[i];
233  }
234 
235  void handleRemoveEdge(const MatrixMetadata& MD, bool Transpose) {
236  DeniedOpts -= Transpose ? MD.getWorstRow() : MD.getWorstCol();
237  const bool* UnsafeOpts =
238  Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
239  for (unsigned i = 0; i < NumOpts; ++i)
240  OptUnsafeEdges[i] -= UnsafeOpts[i];
241  }
242 
244  return (DeniedOpts < NumOpts) ||
245  (std::find(&OptUnsafeEdges[0], &OptUnsafeEdges[NumOpts], 0) !=
246  &OptUnsafeEdges[NumOpts]);
247  }
248 
249 #ifndef NDEBUG
251  return everConservativelyAllocatable;
252  }
253 #endif
254 
255 private:
256  ReductionState RS = Unprocessed;
257  unsigned NumOpts = 0;
258  unsigned DeniedOpts = 0;
259  std::unique_ptr<unsigned[]> OptUnsafeEdges;
260  unsigned VReg = 0;
262 
263 #ifndef NDEBUG
264  bool everConservativelyAllocatable = false;
265 #endif
266 };
267 
269 private:
271 
272 public:
276  using Matrix = RAMatrix;
278 
281 
283  struct EdgeMetadata {};
285 
287 
289 
291  G.setSolver(*this);
292  Solution S;
293  setup();
294  S = backpropagate(G, reduce());
295  G.unsetSolver();
296  return S;
297  }
298 
299  void handleAddNode(NodeId NId) {
300  assert(G.getNodeCosts(NId).getLength() > 1 &&
301  "PBQP Graph should not contain single or zero-option nodes");
302  G.getNodeMetadata(NId).setup(G.getNodeCosts(NId));
303  }
304 
306  void handleSetNodeCosts(NodeId NId, const Vector& newCosts) {}
307 
308  void handleAddEdge(EdgeId EId) {
309  handleReconnectEdge(EId, G.getEdgeNode1Id(EId));
310  handleReconnectEdge(EId, G.getEdgeNode2Id(EId));
311  }
312 
314  NodeMetadata& NMd = G.getNodeMetadata(NId);
315  const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
316  NMd.handleRemoveEdge(MMd, NId == G.getEdgeNode2Id(EId));
317  promote(NId, NMd);
318  }
319 
321  NodeMetadata& NMd = G.getNodeMetadata(NId);
322  const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
323  NMd.handleAddEdge(MMd, NId == G.getEdgeNode2Id(EId));
324  }
325 
326  void handleUpdateCosts(EdgeId EId, const Matrix& NewCosts) {
327  NodeId N1Id = G.getEdgeNode1Id(EId);
328  NodeId N2Id = G.getEdgeNode2Id(EId);
329  NodeMetadata& N1Md = G.getNodeMetadata(N1Id);
330  NodeMetadata& N2Md = G.getNodeMetadata(N2Id);
331  bool Transpose = N1Id != G.getEdgeNode1Id(EId);
332 
333  // Metadata are computed incrementally. First, update them
334  // by removing the old cost.
335  const MatrixMetadata& OldMMd = G.getEdgeCosts(EId).getMetadata();
336  N1Md.handleRemoveEdge(OldMMd, Transpose);
337  N2Md.handleRemoveEdge(OldMMd, !Transpose);
338 
339  // And update now the metadata with the new cost.
340  const MatrixMetadata& MMd = NewCosts.getMetadata();
341  N1Md.handleAddEdge(MMd, Transpose);
342  N2Md.handleAddEdge(MMd, !Transpose);
343 
344  // As the metadata may have changed with the update, the nodes may have
345  // become ConservativelyAllocatable or OptimallyReducible.
346  promote(N1Id, N1Md);
347  promote(N2Id, N2Md);
348  }
349 
350 private:
351  void promote(NodeId NId, NodeMetadata& NMd) {
352  if (G.getNodeDegree(NId) == 3) {
353  // This node is becoming optimally reducible.
354  moveToOptimallyReducibleNodes(NId);
355  } else if (NMd.getReductionState() ==
356  NodeMetadata::NotProvablyAllocatable &&
358  // This node just became conservatively allocatable.
359  moveToConservativelyAllocatableNodes(NId);
360  }
361  }
362 
363  void removeFromCurrentSet(NodeId NId) {
364  switch (G.getNodeMetadata(NId).getReductionState()) {
365  case NodeMetadata::Unprocessed: break;
366  case NodeMetadata::OptimallyReducible:
367  assert(OptimallyReducibleNodes.find(NId) !=
368  OptimallyReducibleNodes.end() &&
369  "Node not in optimally reducible set.");
370  OptimallyReducibleNodes.erase(NId);
371  break;
372  case NodeMetadata::ConservativelyAllocatable:
373  assert(ConservativelyAllocatableNodes.find(NId) !=
374  ConservativelyAllocatableNodes.end() &&
375  "Node not in conservatively allocatable set.");
376  ConservativelyAllocatableNodes.erase(NId);
377  break;
378  case NodeMetadata::NotProvablyAllocatable:
379  assert(NotProvablyAllocatableNodes.find(NId) !=
380  NotProvablyAllocatableNodes.end() &&
381  "Node not in not-provably-allocatable set.");
382  NotProvablyAllocatableNodes.erase(NId);
383  break;
384  }
385  }
386 
387  void moveToOptimallyReducibleNodes(NodeId NId) {
388  removeFromCurrentSet(NId);
389  OptimallyReducibleNodes.insert(NId);
390  G.getNodeMetadata(NId).setReductionState(
391  NodeMetadata::OptimallyReducible);
392  }
393 
394  void moveToConservativelyAllocatableNodes(NodeId NId) {
395  removeFromCurrentSet(NId);
396  ConservativelyAllocatableNodes.insert(NId);
397  G.getNodeMetadata(NId).setReductionState(
398  NodeMetadata::ConservativelyAllocatable);
399  }
400 
401  void moveToNotProvablyAllocatableNodes(NodeId NId) {
402  removeFromCurrentSet(NId);
403  NotProvablyAllocatableNodes.insert(NId);
404  G.getNodeMetadata(NId).setReductionState(
405  NodeMetadata::NotProvablyAllocatable);
406  }
407 
408  void setup() {
409  // Set up worklists.
410  for (auto NId : G.nodeIds()) {
411  if (G.getNodeDegree(NId) < 3)
412  moveToOptimallyReducibleNodes(NId);
413  else if (G.getNodeMetadata(NId).isConservativelyAllocatable())
414  moveToConservativelyAllocatableNodes(NId);
415  else
416  moveToNotProvablyAllocatableNodes(NId);
417  }
418  }
419 
420  // Compute a reduction order for the graph by iteratively applying PBQP
421  // reduction rules. Locally optimal rules are applied whenever possible (R0,
422  // R1, R2). If no locally-optimal rules apply then any conservatively
423  // allocatable node is reduced. Finally, if no conservatively allocatable
424  // node exists then the node with the lowest spill-cost:degree ratio is
425  // selected.
426  std::vector<GraphBase::NodeId> reduce() {
427  assert(!G.empty() && "Cannot reduce empty graph.");
428 
429  using NodeId = GraphBase::NodeId;
430  std::vector<NodeId> NodeStack;
431 
432  // Consume worklists.
433  while (true) {
434  if (!OptimallyReducibleNodes.empty()) {
435  NodeSet::iterator NItr = OptimallyReducibleNodes.begin();
436  NodeId NId = *NItr;
437  OptimallyReducibleNodes.erase(NItr);
438  NodeStack.push_back(NId);
439  switch (G.getNodeDegree(NId)) {
440  case 0:
441  break;
442  case 1:
443  applyR1(G, NId);
444  break;
445  case 2:
446  applyR2(G, NId);
447  break;
448  default: llvm_unreachable("Not an optimally reducible node.");
449  }
450  } else if (!ConservativelyAllocatableNodes.empty()) {
451  // Conservatively allocatable nodes will never spill. For now just
452  // take the first node in the set and push it on the stack. When we
453  // start optimizing more heavily for register preferencing, it may
454  // would be better to push nodes with lower 'expected' or worst-case
455  // register costs first (since early nodes are the most
456  // constrained).
457  NodeSet::iterator NItr = ConservativelyAllocatableNodes.begin();
458  NodeId NId = *NItr;
459  ConservativelyAllocatableNodes.erase(NItr);
460  NodeStack.push_back(NId);
461  G.disconnectAllNeighborsFromNode(NId);
462  } else if (!NotProvablyAllocatableNodes.empty()) {
463  NodeSet::iterator NItr =
464  std::min_element(NotProvablyAllocatableNodes.begin(),
465  NotProvablyAllocatableNodes.end(),
466  SpillCostComparator(G));
467  NodeId NId = *NItr;
468  NotProvablyAllocatableNodes.erase(NItr);
469  NodeStack.push_back(NId);
470  G.disconnectAllNeighborsFromNode(NId);
471  } else
472  break;
473  }
474 
475  return NodeStack;
476  }
477 
478  class SpillCostComparator {
479  public:
480  SpillCostComparator(const Graph& G) : G(G) {}
481 
482  bool operator()(NodeId N1Id, NodeId N2Id) {
483  PBQPNum N1SC = G.getNodeCosts(N1Id)[0];
484  PBQPNum N2SC = G.getNodeCosts(N2Id)[0];
485  if (N1SC == N2SC)
486  return G.getNodeDegree(N1Id) < G.getNodeDegree(N2Id);
487  return N1SC < N2SC;
488  }
489 
490  private:
491  const Graph& G;
492  };
493 
494  Graph& G;
495  using NodeSet = std::set<NodeId>;
496  NodeSet OptimallyReducibleNodes;
497  NodeSet ConservativelyAllocatableNodes;
498  NodeSet NotProvablyAllocatableNodes;
499 };
500 
501 class PBQPRAGraph : public PBQP::Graph<RegAllocSolverImpl> {
502 private:
504 
505 public:
506  PBQPRAGraph(GraphMetadata Metadata) : BaseT(std::move(Metadata)) {}
507 
508  /// @brief Dump this graph to dbgs().
509  void dump() const;
510 
511  /// @brief Dump this graph to an output stream.
512  /// @param OS Output stream to print on.
513  void dump(raw_ostream &OS) const;
514 
515  /// @brief Print a representation of this graph in DOT format.
516  /// @param OS Output stream to print on.
517  void printDot(raw_ostream &OS) const;
518 };
519 
521  if (G.empty())
522  return Solution();
523  RegAllocSolverImpl RegAllocSolver(G);
524  return RegAllocSolver.solve();
525 }
526 
527 } // end namespace RegAlloc
528 } // end namespace PBQP
529 
530 /// @brief Create a PBQP register allocator instance.
531 FunctionPass *
532 createPBQPRegisterAllocator(char *customPassID = nullptr);
533 
534 } // end namespace llvm
535 
536 #endif // LLVM_CODEGEN_REGALLOCPBQP_H
Represents a solution to a PBQP problem.
Definition: Solution.h:27
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void setAllowedRegs(GraphMetadata::AllowedRegVecRef AllowedRegs)
Definition: RegAllocPBQP.h:204
Holds a vector of the allowed physical regs for a vreg.
Definition: RegAllocPBQP.h:93
bool empty() const
Returns true if the graph is empty.
Definition: Graph.h:448
void handleSetNodeCosts(NodeId NId, const Vector &newCosts)
Definition: RegAllocPBQP.h:306
unsigned getLength() const
Return the length of the vector.
Definition: Math.h:61
static NodeId invalidNodeId()
Returns a value representing an invalid (non-existent) node.
Definition: Graph.h:33
enum { Unprocessed, NotProvablyAllocatable, ConservativelyAllocatable, OptimallyReducible } ReductionState
Definition: RegAllocPBQP.h:180
AllowedRegVecPool::PoolRef AllowedRegVecRef
Definition: RegAllocPBQP.h:136
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
NodeMetadata(const NodeMetadata &Other)
Definition: RegAllocPBQP.h:184
MachineBlockFrequencyInfo & MBFI
Definition: RegAllocPBQP.h:145
void setup(const Vector &Costs)
Definition: RegAllocPBQP.h:209
void setReductionState(ReductionState RS)
Definition: RegAllocPBQP.h:215
Live Register Matrix
FunctionPass * createPBQPRegisterAllocator(char *customPassID=nullptr)
Create a PBQP register allocator instance.
Definition: BitVector.h:920
typename RegAllocSolverImpl ::GraphMetadata GraphMetadata
Definition: Graph.h:60
const bool * getUnsafeRows() const
Definition: RegAllocPBQP.h:82
float PBQPNum
Definition: Math.h:23
const bool * getUnsafeCols() const
Definition: RegAllocPBQP.h:83
unsigned getRows() const
Return the number of rows in this matrix.
Definition: Math.h:162
void setNodeIdForVReg(unsigned VReg, GraphBase::NodeId NId)
Definition: RegAllocPBQP.h:147
void applyR1(GraphT &G, typename GraphT::NodeId NId)
Reduce a node of degree one.
void handleDisconnectEdge(EdgeId EId, NodeId NId)
Definition: RegAllocPBQP.h:313
AllowedRegVecRef getAllowedRegs(AllowedRegVector Allowed)
Definition: RegAllocPBQP.h:158
const AllowedRegVector & getAllowedRegs() const
Definition: RegAllocPBQP.h:207
unsigned getCols() const
Return the number of cols in this matrix.
Definition: Math.h:168
unsigned NodeId
Definition: Graph.h:29
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
const Vector & getNodeCosts(NodeId NId) const
Get a node&#39;s cost vector.
Definition: Graph.h:489
PBQP Matrix class.
Definition: Math.h:122
PBQPRAGraph(GraphMetadata Metadata)
Definition: RegAllocPBQP.h:506
void handleAddEdge(const MatrixMetadata &MD, bool Transpose)
Definition: RegAllocPBQP.h:227
AllowedRegVector(const std::vector< unsigned > &OptVec)
Definition: RegAllocPBQP.h:100
PBQP Vector class.
Definition: Math.h:26
bool operator==(const AllowedRegVector &Other) const
Definition: RegAllocPBQP.h:108
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
GraphMetadata(MachineFunction &MF, LiveIntervals &LIS, MachineBlockFrequencyInfo &MBFI)
Definition: RegAllocPBQP.h:138
void handleRemoveEdge(const MatrixMetadata &MD, bool Transpose)
Definition: RegAllocPBQP.h:235
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:835
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Holds solver state and other metadata relevant to each PBQP RA node.
Definition: RegAllocPBQP.h:168
GraphBase::NodeId getNodeIdForVReg(unsigned VReg) const
Definition: RegAllocPBQP.h:151
ReductionState getReductionState() const
Definition: RegAllocPBQP.h:214
Metadata to speed allocatability test.
Definition: RegAllocPBQP.h:52
static cl::opt< RegisterRegAlloc::FunctionPassCtor, false, RegisterPassParser< RegisterRegAlloc > > RegAlloc("regalloc", cl::Hidden, cl::init(&useDefaultRegisterAllocator), cl::desc("Register allocator to use"))
Solution backpropagate(GraphT &G, StackT stack)
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const
Definition: Graph.h:501
void handleUpdateCosts(EdgeId EId, const Matrix &NewCosts)
Definition: RegAllocPBQP.h:326
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:602
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:480
#define NDEBUG
Definition: regutils.h:48
An opaque object representing a hash code.
Definition: Hashing.h:72
unsigned operator[](size_t I) const
Definition: RegAllocPBQP.h:106
bool operator!=(const AllowedRegVector &Other) const
Definition: RegAllocPBQP.h:114
const Metadata & getMetadata() const
Definition: Math.h:278
std::shared_ptr< const AllowedRegVector > PoolRef
Definition: CostAllocator.h:31
void handleReconnectEdge(EdgeId EId, NodeId NId)
Definition: RegAllocPBQP.h:320
#define I(x, y, z)
Definition: MD5.cpp:58
hash_code hash_value(const AllowedRegVector &OptRegs)
Definition: RegAllocPBQP.h:123
Solution solve(PBQPRAGraph &G)
Definition: RegAllocPBQP.h:520
unsigned getSpillOptionIdx()
Spill option index.
Definition: RegAllocPBQP.h:47
loop reduce
void applyR2(GraphT &G, typename GraphT::NodeId NId)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned EdgeId
Definition: Graph.h:30
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
Holds graph-level metadata relevant to PBQP RA problems.
Definition: RegAllocPBQP.h:131
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:866
Root of the metadata hierarchy.
Definition: Metadata.h:58
MatrixMetadata & operator=(const MatrixMetadata &)=delete