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