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/CodeGen/MachineFunctionPass.h"
20 #include "llvm/CodeGen/PBQP/CostAllocator.h"
21 #include "llvm/CodeGen/PBQP/ReductionRules.h"
22 #include "llvm/CodeGen/PBQPRAConstraint.h"
23 #include "llvm/Support/ErrorHandling.h"
24 #include <set>
25
26 namespace llvm {
27
28 class raw_ostream;
29
30 namespace PBQP {
31 namespace RegAlloc {
32
33 /// @brief Spill option index.
getSpillOptionIdx()34 inline unsigned getSpillOptionIdx() { return 0; }
35
36 /// \brief Metadata to speed allocatability test.
37 ///
38 /// Keeps track of the number of infinities in each row and column.
39 class MatrixMetadata {
40 private:
41 MatrixMetadata(const MatrixMetadata&);
42 void operator=(const MatrixMetadata&);
43 public:
MatrixMetadata(const Matrix & M)44 MatrixMetadata(const Matrix& M)
45 : WorstRow(0), WorstCol(0),
46 UnsafeRows(new bool[M.getRows() - 1]()),
47 UnsafeCols(new bool[M.getCols() - 1]()) {
48
49 unsigned* ColCounts = new unsigned[M.getCols() - 1]();
50
51 for (unsigned i = 1; i < M.getRows(); ++i) {
52 unsigned RowCount = 0;
53 for (unsigned j = 1; j < M.getCols(); ++j) {
54 if (M[i][j] == std::numeric_limits<PBQPNum>::infinity()) {
55 ++RowCount;
56 ++ColCounts[j - 1];
57 UnsafeRows[i - 1] = true;
58 UnsafeCols[j - 1] = true;
59 }
60 }
61 WorstRow = std::max(WorstRow, RowCount);
62 }
63 unsigned WorstColCountForCurRow =
64 *std::max_element(ColCounts, ColCounts + M.getCols() - 1);
65 WorstCol = std::max(WorstCol, WorstColCountForCurRow);
66 delete[] ColCounts;
67 }
68
getWorstRow()69 unsigned getWorstRow() const { return WorstRow; }
getWorstCol()70 unsigned getWorstCol() const { return WorstCol; }
getUnsafeRows()71 const bool* getUnsafeRows() const { return UnsafeRows.get(); }
getUnsafeCols()72 const bool* getUnsafeCols() const { return UnsafeCols.get(); }
73
74 private:
75 unsigned WorstRow, WorstCol;
76 std::unique_ptr<bool[]> UnsafeRows;
77 std::unique_ptr<bool[]> UnsafeCols;
78 };
79
80 /// \brief Holds a vector of the allowed physical regs for a vreg.
81 class AllowedRegVector {
82 friend hash_code hash_value(const AllowedRegVector &);
83 public:
84
AllowedRegVector()85 AllowedRegVector() : NumOpts(0), Opts(nullptr) {}
86
AllowedRegVector(const std::vector<unsigned> & OptVec)87 AllowedRegVector(const std::vector<unsigned> &OptVec)
88 : NumOpts(OptVec.size()), Opts(new unsigned[NumOpts]) {
89 std::copy(OptVec.begin(), OptVec.end(), Opts.get());
90 }
91
AllowedRegVector(const AllowedRegVector & Other)92 AllowedRegVector(const AllowedRegVector &Other)
93 : NumOpts(Other.NumOpts), Opts(new unsigned[NumOpts]) {
94 std::copy(Other.Opts.get(), Other.Opts.get() + NumOpts, Opts.get());
95 }
96
AllowedRegVector(AllowedRegVector && Other)97 AllowedRegVector(AllowedRegVector &&Other)
98 : NumOpts(std::move(Other.NumOpts)), Opts(std::move(Other.Opts)) {}
99
100 AllowedRegVector& operator=(const AllowedRegVector &Other) {
101 NumOpts = Other.NumOpts;
102 Opts.reset(new unsigned[NumOpts]);
103 std::copy(Other.Opts.get(), Other.Opts.get() + NumOpts, Opts.get());
104 return *this;
105 }
106
107 AllowedRegVector& operator=(AllowedRegVector &&Other) {
108 NumOpts = std::move(Other.NumOpts);
109 Opts = std::move(Other.Opts);
110 return *this;
111 }
112
size()113 unsigned size() const { return NumOpts; }
114 unsigned operator[](size_t I) const { return Opts[I]; }
115
116 bool operator==(const AllowedRegVector &Other) const {
117 if (NumOpts != Other.NumOpts)
118 return false;
119 return std::equal(Opts.get(), Opts.get() + NumOpts, Other.Opts.get());
120 }
121
122 bool operator!=(const AllowedRegVector &Other) const {
123 return !(*this == Other);
124 }
125
126 private:
127 unsigned NumOpts;
128 std::unique_ptr<unsigned[]> Opts;
129 };
130
hash_value(const AllowedRegVector & OptRegs)131 inline hash_code hash_value(const AllowedRegVector &OptRegs) {
132 unsigned *OStart = OptRegs.Opts.get();
133 unsigned *OEnd = OptRegs.Opts.get() + OptRegs.NumOpts;
134 return hash_combine(OptRegs.NumOpts,
135 hash_combine_range(OStart, OEnd));
136 }
137
138 /// \brief Holds graph-level metadata relevant to PBQP RA problems.
139 class GraphMetadata {
140 private:
141 typedef ValuePool<AllowedRegVector> AllowedRegVecPool;
142 public:
143
144 typedef AllowedRegVecPool::PoolRef AllowedRegVecRef;
145
GraphMetadata(MachineFunction & MF,LiveIntervals & LIS,MachineBlockFrequencyInfo & MBFI)146 GraphMetadata(MachineFunction &MF,
147 LiveIntervals &LIS,
148 MachineBlockFrequencyInfo &MBFI)
149 : MF(MF), LIS(LIS), MBFI(MBFI) {}
150
151 MachineFunction &MF;
152 LiveIntervals &LIS;
153 MachineBlockFrequencyInfo &MBFI;
154
setNodeIdForVReg(unsigned VReg,GraphBase::NodeId NId)155 void setNodeIdForVReg(unsigned VReg, GraphBase::NodeId NId) {
156 VRegToNodeId[VReg] = NId;
157 }
158
getNodeIdForVReg(unsigned VReg)159 GraphBase::NodeId getNodeIdForVReg(unsigned VReg) const {
160 auto VRegItr = VRegToNodeId.find(VReg);
161 if (VRegItr == VRegToNodeId.end())
162 return GraphBase::invalidNodeId();
163 return VRegItr->second;
164 }
165
eraseNodeIdForVReg(unsigned VReg)166 void eraseNodeIdForVReg(unsigned VReg) {
167 VRegToNodeId.erase(VReg);
168 }
169
getAllowedRegs(AllowedRegVector Allowed)170 AllowedRegVecRef getAllowedRegs(AllowedRegVector Allowed) {
171 return AllowedRegVecs.getValue(std::move(Allowed));
172 }
173
174 private:
175 DenseMap<unsigned, GraphBase::NodeId> VRegToNodeId;
176 AllowedRegVecPool AllowedRegVecs;
177 };
178
179 /// \brief Holds solver state and other metadata relevant to each PBQP RA node.
180 class NodeMetadata {
181 public:
182 typedef RegAlloc::AllowedRegVector AllowedRegVector;
183
184 // The node's reduction state. The order in this enum is important,
185 // as it is assumed nodes can only progress up (i.e. towards being
186 // optimally reducible) when reducing the graph.
187 typedef enum {
188 Unprocessed,
189 NotProvablyAllocatable,
190 ConservativelyAllocatable,
191 OptimallyReducible
192 } ReductionState;
193
NodeMetadata()194 NodeMetadata()
195 : RS(Unprocessed), NumOpts(0), DeniedOpts(0), OptUnsafeEdges(nullptr),
196 VReg(0)
197 #ifndef NDEBUG
198 , everConservativelyAllocatable(false)
199 #endif
200 {}
201
202 // FIXME: Re-implementing default behavior to work around MSVC. Remove once
203 // MSVC synthesizes move constructors properly.
NodeMetadata(const NodeMetadata & Other)204 NodeMetadata(const NodeMetadata &Other)
205 : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts),
206 OptUnsafeEdges(new unsigned[NumOpts]), VReg(Other.VReg),
207 AllowedRegs(Other.AllowedRegs)
208 #ifndef NDEBUG
209 , everConservativelyAllocatable(Other.everConservativelyAllocatable)
210 #endif
211 {
212 if (NumOpts > 0) {
213 std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts],
214 &OptUnsafeEdges[0]);
215 }
216 }
217
218 // FIXME: Re-implementing default behavior to work around MSVC. Remove once
219 // MSVC synthesizes move constructors properly.
NodeMetadata(NodeMetadata && Other)220 NodeMetadata(NodeMetadata &&Other)
221 : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts),
222 OptUnsafeEdges(std::move(Other.OptUnsafeEdges)), VReg(Other.VReg),
223 AllowedRegs(std::move(Other.AllowedRegs))
224 #ifndef NDEBUG
225 , everConservativelyAllocatable(Other.everConservativelyAllocatable)
226 #endif
227 {}
228
229 // FIXME: Re-implementing default behavior to work around MSVC. Remove once
230 // MSVC synthesizes move constructors properly.
231 NodeMetadata& operator=(const NodeMetadata &Other) {
232 RS = Other.RS;
233 NumOpts = Other.NumOpts;
234 DeniedOpts = Other.DeniedOpts;
235 OptUnsafeEdges.reset(new unsigned[NumOpts]);
236 std::copy(Other.OptUnsafeEdges.get(), Other.OptUnsafeEdges.get() + NumOpts,
237 OptUnsafeEdges.get());
238 VReg = Other.VReg;
239 AllowedRegs = Other.AllowedRegs;
240 #ifndef NDEBUG
241 everConservativelyAllocatable = Other.everConservativelyAllocatable;
242 #endif
243 return *this;
244 }
245
246 // FIXME: Re-implementing default behavior to work around MSVC. Remove once
247 // MSVC synthesizes move constructors properly.
248 NodeMetadata& operator=(NodeMetadata &&Other) {
249 RS = Other.RS;
250 NumOpts = Other.NumOpts;
251 DeniedOpts = Other.DeniedOpts;
252 OptUnsafeEdges = std::move(Other.OptUnsafeEdges);
253 VReg = Other.VReg;
254 AllowedRegs = std::move(Other.AllowedRegs);
255 #ifndef NDEBUG
256 everConservativelyAllocatable = Other.everConservativelyAllocatable;
257 #endif
258 return *this;
259 }
260
setVReg(unsigned VReg)261 void setVReg(unsigned VReg) { this->VReg = VReg; }
getVReg()262 unsigned getVReg() const { return VReg; }
263
setAllowedRegs(GraphMetadata::AllowedRegVecRef AllowedRegs)264 void setAllowedRegs(GraphMetadata::AllowedRegVecRef AllowedRegs) {
265 this->AllowedRegs = std::move(AllowedRegs);
266 }
getAllowedRegs()267 const AllowedRegVector& getAllowedRegs() const { return *AllowedRegs; }
268
setup(const Vector & Costs)269 void setup(const Vector& Costs) {
270 NumOpts = Costs.getLength() - 1;
271 OptUnsafeEdges = std::unique_ptr<unsigned[]>(new unsigned[NumOpts]());
272 }
273
getReductionState()274 ReductionState getReductionState() const { return RS; }
setReductionState(ReductionState RS)275 void setReductionState(ReductionState RS) {
276 assert(RS >= this->RS && "A node's reduction state can not be downgraded");
277 this->RS = RS;
278
279 #ifndef NDEBUG
280 // Remember this state to assert later that a non-infinite register
281 // option was available.
282 if (RS == ConservativelyAllocatable)
283 everConservativelyAllocatable = true;
284 #endif
285 }
286
287
handleAddEdge(const MatrixMetadata & MD,bool Transpose)288 void handleAddEdge(const MatrixMetadata& MD, bool Transpose) {
289 DeniedOpts += Transpose ? MD.getWorstRow() : MD.getWorstCol();
290 const bool* UnsafeOpts =
291 Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
292 for (unsigned i = 0; i < NumOpts; ++i)
293 OptUnsafeEdges[i] += UnsafeOpts[i];
294 }
295
handleRemoveEdge(const MatrixMetadata & MD,bool Transpose)296 void handleRemoveEdge(const MatrixMetadata& MD, bool Transpose) {
297 DeniedOpts -= Transpose ? MD.getWorstRow() : MD.getWorstCol();
298 const bool* UnsafeOpts =
299 Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
300 for (unsigned i = 0; i < NumOpts; ++i)
301 OptUnsafeEdges[i] -= UnsafeOpts[i];
302 }
303
isConservativelyAllocatable()304 bool isConservativelyAllocatable() const {
305 return (DeniedOpts < NumOpts) ||
306 (std::find(&OptUnsafeEdges[0], &OptUnsafeEdges[NumOpts], 0) !=
307 &OptUnsafeEdges[NumOpts]);
308 }
309
310 #ifndef NDEBUG
wasConservativelyAllocatable()311 bool wasConservativelyAllocatable() const {
312 return everConservativelyAllocatable;
313 }
314 #endif
315
316 private:
317 ReductionState RS;
318 unsigned NumOpts;
319 unsigned DeniedOpts;
320 std::unique_ptr<unsigned[]> OptUnsafeEdges;
321 unsigned VReg;
322 GraphMetadata::AllowedRegVecRef AllowedRegs;
323
324 #ifndef NDEBUG
325 bool everConservativelyAllocatable;
326 #endif
327 };
328
329 class RegAllocSolverImpl {
330 private:
331 typedef MDMatrix<MatrixMetadata> RAMatrix;
332 public:
333 typedef PBQP::Vector RawVector;
334 typedef PBQP::Matrix RawMatrix;
335 typedef PBQP::Vector Vector;
336 typedef RAMatrix Matrix;
337 typedef PBQP::PoolCostAllocator<Vector, Matrix> CostAllocator;
338
339 typedef GraphBase::NodeId NodeId;
340 typedef GraphBase::EdgeId EdgeId;
341
342 typedef RegAlloc::NodeMetadata NodeMetadata;
343 struct EdgeMetadata { };
344 typedef RegAlloc::GraphMetadata GraphMetadata;
345
346 typedef PBQP::Graph<RegAllocSolverImpl> Graph;
347
RegAllocSolverImpl(Graph & G)348 RegAllocSolverImpl(Graph &G) : G(G) {}
349
solve()350 Solution solve() {
351 G.setSolver(*this);
352 Solution S;
353 setup();
354 S = backpropagate(G, reduce());
355 G.unsetSolver();
356 return S;
357 }
358
handleAddNode(NodeId NId)359 void handleAddNode(NodeId NId) {
360 assert(G.getNodeCosts(NId).getLength() > 1 &&
361 "PBQP Graph should not contain single or zero-option nodes");
362 G.getNodeMetadata(NId).setup(G.getNodeCosts(NId));
363 }
handleRemoveNode(NodeId NId)364 void handleRemoveNode(NodeId NId) {}
handleSetNodeCosts(NodeId NId,const Vector & newCosts)365 void handleSetNodeCosts(NodeId NId, const Vector& newCosts) {}
366
handleAddEdge(EdgeId EId)367 void handleAddEdge(EdgeId EId) {
368 handleReconnectEdge(EId, G.getEdgeNode1Id(EId));
369 handleReconnectEdge(EId, G.getEdgeNode2Id(EId));
370 }
371
handleRemoveEdge(EdgeId EId)372 void handleRemoveEdge(EdgeId EId) {
373 handleDisconnectEdge(EId, G.getEdgeNode1Id(EId));
374 handleDisconnectEdge(EId, G.getEdgeNode2Id(EId));
375 }
376
handleDisconnectEdge(EdgeId EId,NodeId NId)377 void handleDisconnectEdge(EdgeId EId, NodeId NId) {
378 NodeMetadata& NMd = G.getNodeMetadata(NId);
379 const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
380 NMd.handleRemoveEdge(MMd, NId == G.getEdgeNode2Id(EId));
381 promote(NId, NMd);
382 }
383
handleReconnectEdge(EdgeId EId,NodeId NId)384 void handleReconnectEdge(EdgeId EId, NodeId NId) {
385 NodeMetadata& NMd = G.getNodeMetadata(NId);
386 const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
387 NMd.handleAddEdge(MMd, NId == G.getEdgeNode2Id(EId));
388 }
389
handleUpdateCosts(EdgeId EId,const Matrix & NewCosts)390 void handleUpdateCosts(EdgeId EId, const Matrix& NewCosts) {
391 NodeId N1Id = G.getEdgeNode1Id(EId);
392 NodeId N2Id = G.getEdgeNode2Id(EId);
393 NodeMetadata& N1Md = G.getNodeMetadata(N1Id);
394 NodeMetadata& N2Md = G.getNodeMetadata(N2Id);
395 bool Transpose = N1Id != G.getEdgeNode1Id(EId);
396
397 // Metadata are computed incrementally. First, update them
398 // by removing the old cost.
399 const MatrixMetadata& OldMMd = G.getEdgeCosts(EId).getMetadata();
400 N1Md.handleRemoveEdge(OldMMd, Transpose);
401 N2Md.handleRemoveEdge(OldMMd, !Transpose);
402
403 // And update now the metadata with the new cost.
404 const MatrixMetadata& MMd = NewCosts.getMetadata();
405 N1Md.handleAddEdge(MMd, Transpose);
406 N2Md.handleAddEdge(MMd, !Transpose);
407
408 // As the metadata may have changed with the update, the nodes may have
409 // become ConservativelyAllocatable or OptimallyReducible.
410 promote(N1Id, N1Md);
411 promote(N2Id, N2Md);
412 }
413
414 private:
415
promote(NodeId NId,NodeMetadata & NMd)416 void promote(NodeId NId, NodeMetadata& NMd) {
417 if (G.getNodeDegree(NId) == 3) {
418 // This node is becoming optimally reducible.
419 moveToOptimallyReducibleNodes(NId);
420 } else if (NMd.getReductionState() ==
421 NodeMetadata::NotProvablyAllocatable &&
422 NMd.isConservativelyAllocatable()) {
423 // This node just became conservatively allocatable.
424 moveToConservativelyAllocatableNodes(NId);
425 }
426 }
427
removeFromCurrentSet(NodeId NId)428 void removeFromCurrentSet(NodeId NId) {
429 switch (G.getNodeMetadata(NId).getReductionState()) {
430 case NodeMetadata::Unprocessed: break;
431 case NodeMetadata::OptimallyReducible:
432 assert(OptimallyReducibleNodes.find(NId) !=
433 OptimallyReducibleNodes.end() &&
434 "Node not in optimally reducible set.");
435 OptimallyReducibleNodes.erase(NId);
436 break;
437 case NodeMetadata::ConservativelyAllocatable:
438 assert(ConservativelyAllocatableNodes.find(NId) !=
439 ConservativelyAllocatableNodes.end() &&
440 "Node not in conservatively allocatable set.");
441 ConservativelyAllocatableNodes.erase(NId);
442 break;
443 case NodeMetadata::NotProvablyAllocatable:
444 assert(NotProvablyAllocatableNodes.find(NId) !=
445 NotProvablyAllocatableNodes.end() &&
446 "Node not in not-provably-allocatable set.");
447 NotProvablyAllocatableNodes.erase(NId);
448 break;
449 }
450 }
451
moveToOptimallyReducibleNodes(NodeId NId)452 void moveToOptimallyReducibleNodes(NodeId NId) {
453 removeFromCurrentSet(NId);
454 OptimallyReducibleNodes.insert(NId);
455 G.getNodeMetadata(NId).setReductionState(
456 NodeMetadata::OptimallyReducible);
457 }
458
moveToConservativelyAllocatableNodes(NodeId NId)459 void moveToConservativelyAllocatableNodes(NodeId NId) {
460 removeFromCurrentSet(NId);
461 ConservativelyAllocatableNodes.insert(NId);
462 G.getNodeMetadata(NId).setReductionState(
463 NodeMetadata::ConservativelyAllocatable);
464 }
465
moveToNotProvablyAllocatableNodes(NodeId NId)466 void moveToNotProvablyAllocatableNodes(NodeId NId) {
467 removeFromCurrentSet(NId);
468 NotProvablyAllocatableNodes.insert(NId);
469 G.getNodeMetadata(NId).setReductionState(
470 NodeMetadata::NotProvablyAllocatable);
471 }
472
setup()473 void setup() {
474 // Set up worklists.
475 for (auto NId : G.nodeIds()) {
476 if (G.getNodeDegree(NId) < 3)
477 moveToOptimallyReducibleNodes(NId);
478 else if (G.getNodeMetadata(NId).isConservativelyAllocatable())
479 moveToConservativelyAllocatableNodes(NId);
480 else
481 moveToNotProvablyAllocatableNodes(NId);
482 }
483 }
484
485 // Compute a reduction order for the graph by iteratively applying PBQP
486 // reduction rules. Locally optimal rules are applied whenever possible (R0,
487 // R1, R2). If no locally-optimal rules apply then any conservatively
488 // allocatable node is reduced. Finally, if no conservatively allocatable
489 // node exists then the node with the lowest spill-cost:degree ratio is
490 // selected.
reduce()491 std::vector<GraphBase::NodeId> reduce() {
492 assert(!G.empty() && "Cannot reduce empty graph.");
493
494 typedef GraphBase::NodeId NodeId;
495 std::vector<NodeId> NodeStack;
496
497 // Consume worklists.
498 while (true) {
499 if (!OptimallyReducibleNodes.empty()) {
500 NodeSet::iterator NItr = OptimallyReducibleNodes.begin();
501 NodeId NId = *NItr;
502 OptimallyReducibleNodes.erase(NItr);
503 NodeStack.push_back(NId);
504 switch (G.getNodeDegree(NId)) {
505 case 0:
506 break;
507 case 1:
508 applyR1(G, NId);
509 break;
510 case 2:
511 applyR2(G, NId);
512 break;
513 default: llvm_unreachable("Not an optimally reducible node.");
514 }
515 } else if (!ConservativelyAllocatableNodes.empty()) {
516 // Conservatively allocatable nodes will never spill. For now just
517 // take the first node in the set and push it on the stack. When we
518 // start optimizing more heavily for register preferencing, it may
519 // would be better to push nodes with lower 'expected' or worst-case
520 // register costs first (since early nodes are the most
521 // constrained).
522 NodeSet::iterator NItr = ConservativelyAllocatableNodes.begin();
523 NodeId NId = *NItr;
524 ConservativelyAllocatableNodes.erase(NItr);
525 NodeStack.push_back(NId);
526 G.disconnectAllNeighborsFromNode(NId);
527
528 } else if (!NotProvablyAllocatableNodes.empty()) {
529 NodeSet::iterator NItr =
530 std::min_element(NotProvablyAllocatableNodes.begin(),
531 NotProvablyAllocatableNodes.end(),
532 SpillCostComparator(G));
533 NodeId NId = *NItr;
534 NotProvablyAllocatableNodes.erase(NItr);
535 NodeStack.push_back(NId);
536 G.disconnectAllNeighborsFromNode(NId);
537 } else
538 break;
539 }
540
541 return NodeStack;
542 }
543
544 class SpillCostComparator {
545 public:
SpillCostComparator(const Graph & G)546 SpillCostComparator(const Graph& G) : G(G) {}
operator()547 bool operator()(NodeId N1Id, NodeId N2Id) {
548 PBQPNum N1SC = G.getNodeCosts(N1Id)[0];
549 PBQPNum N2SC = G.getNodeCosts(N2Id)[0];
550 if (N1SC == N2SC)
551 return G.getNodeDegree(N1Id) < G.getNodeDegree(N2Id);
552 return N1SC < N2SC;
553 }
554 private:
555 const Graph& G;
556 };
557
558 Graph& G;
559 typedef std::set<NodeId> NodeSet;
560 NodeSet OptimallyReducibleNodes;
561 NodeSet ConservativelyAllocatableNodes;
562 NodeSet NotProvablyAllocatableNodes;
563 };
564
565 class PBQPRAGraph : public PBQP::Graph<RegAllocSolverImpl> {
566 private:
567 typedef PBQP::Graph<RegAllocSolverImpl> BaseT;
568 public:
PBQPRAGraph(GraphMetadata Metadata)569 PBQPRAGraph(GraphMetadata Metadata) : BaseT(Metadata) {}
570
571 /// @brief Dump this graph to dbgs().
572 void dump() const;
573
574 /// @brief Dump this graph to an output stream.
575 /// @param OS Output stream to print on.
576 void dump(raw_ostream &OS) const;
577
578 /// @brief Print a representation of this graph in DOT format.
579 /// @param OS Output stream to print on.
580 void printDot(raw_ostream &OS) const;
581 };
582
solve(PBQPRAGraph & G)583 inline Solution solve(PBQPRAGraph& G) {
584 if (G.empty())
585 return Solution();
586 RegAllocSolverImpl RegAllocSolver(G);
587 return RegAllocSolver.solve();
588 }
589
590 } // namespace RegAlloc
591 } // namespace PBQP
592
593 /// @brief Create a PBQP register allocator instance.
594 FunctionPass *
595 createPBQPRegisterAllocator(char *customPassID = nullptr);
596
597 } // namespace llvm
598
599 #endif /* LLVM_CODEGEN_REGALLOCPBQP_H */
600