1 //===-- RegAllocPBQP.h ------------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the PBQPBuilder interface, for classes which build PBQP
11 // instances to represent register allocation problems, and the RegAllocPBQP
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_CODEGEN_REGALLOCPBQP_H
17 #define LLVM_CODEGEN_REGALLOCPBQP_H
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"
33 /// @brief Spill option index.
34 inline unsigned getSpillOptionIdx() { return 0; }
36 /// \brief Metadata to speed allocatability test.
38 /// Keeps track of the number of infinities in each row and column.
39 class MatrixMetadata {
41 MatrixMetadata(const MatrixMetadata&);
42 void operator=(const MatrixMetadata&);
44 MatrixMetadata(const Matrix& M)
45 : WorstRow(0), WorstCol(0),
46 UnsafeRows(new bool[M.getRows() - 1]()),
47 UnsafeCols(new bool[M.getCols() - 1]()) {
49 unsigned* ColCounts = new unsigned[M.getCols() - 1]();
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()) {
57 UnsafeRows[i - 1] = true;
58 UnsafeCols[j - 1] = true;
61 WorstRow = std::max(WorstRow, RowCount);
63 unsigned WorstColCountForCurRow =
64 *std::max_element(ColCounts, ColCounts + M.getCols() - 1);
65 WorstCol = std::max(WorstCol, WorstColCountForCurRow);
69 unsigned getWorstRow() const { return WorstRow; }
70 unsigned getWorstCol() const { return WorstCol; }
71 const bool* getUnsafeRows() const { return UnsafeRows.get(); }
72 const bool* getUnsafeCols() const { return UnsafeCols.get(); }
75 unsigned WorstRow, WorstCol;
76 std::unique_ptr<bool[]> UnsafeRows;
77 std::unique_ptr<bool[]> UnsafeCols;
80 /// \brief Holds a vector of the allowed physical regs for a vreg.
81 class AllowedRegVector {
82 friend hash_code hash_value(const AllowedRegVector &);
85 AllowedRegVector() : NumOpts(0), Opts(nullptr) {}
87 AllowedRegVector(const std::vector<unsigned> &OptVec)
88 : NumOpts(OptVec.size()), Opts(new unsigned[NumOpts]) {
89 std::copy(OptVec.begin(), OptVec.end(), Opts.get());
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());
97 AllowedRegVector(AllowedRegVector &&Other)
98 : NumOpts(std::move(Other.NumOpts)), Opts(std::move(Other.Opts)) {}
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());
107 AllowedRegVector& operator=(AllowedRegVector &&Other) {
108 NumOpts = std::move(Other.NumOpts);
109 Opts = std::move(Other.Opts);
113 unsigned size() const { return NumOpts; }
114 unsigned operator[](size_t I) const { return Opts[I]; }
116 bool operator==(const AllowedRegVector &Other) const {
117 if (NumOpts != Other.NumOpts)
119 return std::equal(Opts.get(), Opts.get() + NumOpts, Other.Opts.get());
122 bool operator!=(const AllowedRegVector &Other) const {
123 return !(*this == Other);
128 std::unique_ptr<unsigned[]> Opts;
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));
138 /// \brief Holds graph-level metadata relevant to PBQP RA problems.
139 class GraphMetadata {
141 typedef ValuePool<AllowedRegVector> AllowedRegVecPool;
144 typedef AllowedRegVecPool::PoolRef AllowedRegVecRef;
146 GraphMetadata(MachineFunction &MF,
148 MachineBlockFrequencyInfo &MBFI)
149 : MF(MF), LIS(LIS), MBFI(MBFI) {}
153 MachineBlockFrequencyInfo &MBFI;
155 void setNodeIdForVReg(unsigned VReg, GraphBase::NodeId NId) {
156 VRegToNodeId[VReg] = NId;
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;
166 void eraseNodeIdForVReg(unsigned VReg) {
167 VRegToNodeId.erase(VReg);
170 AllowedRegVecRef getAllowedRegs(AllowedRegVector Allowed) {
171 return AllowedRegVecs.getValue(std::move(Allowed));
175 DenseMap<unsigned, GraphBase::NodeId> VRegToNodeId;
176 AllowedRegVecPool AllowedRegVecs;
179 /// \brief Holds solver state and other metadata relevant to each PBQP RA node.
182 typedef RegAlloc::AllowedRegVector AllowedRegVector;
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.
189 NotProvablyAllocatable,
190 ConservativelyAllocatable,
195 : RS(Unprocessed), NumOpts(0), DeniedOpts(0), OptUnsafeEdges(nullptr),
198 , everConservativelyAllocatable(false)
202 // FIXME: Re-implementing default behavior to work around MSVC. Remove once
203 // MSVC synthesizes move constructors properly.
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)
209 , everConservativelyAllocatable(Other.everConservativelyAllocatable)
213 std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts],
218 // FIXME: Re-implementing default behavior to work around MSVC. Remove once
219 // MSVC synthesizes move constructors properly.
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))
225 , everConservativelyAllocatable(Other.everConservativelyAllocatable)
229 // FIXME: Re-implementing default behavior to work around MSVC. Remove once
230 // MSVC synthesizes move constructors properly.
231 NodeMetadata& operator=(const NodeMetadata &Other) {
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());
239 AllowedRegs = Other.AllowedRegs;
241 everConservativelyAllocatable = Other.everConservativelyAllocatable;
246 // FIXME: Re-implementing default behavior to work around MSVC. Remove once
247 // MSVC synthesizes move constructors properly.
248 NodeMetadata& operator=(NodeMetadata &&Other) {
250 NumOpts = Other.NumOpts;
251 DeniedOpts = Other.DeniedOpts;
252 OptUnsafeEdges = std::move(Other.OptUnsafeEdges);
254 AllowedRegs = std::move(Other.AllowedRegs);
256 everConservativelyAllocatable = Other.everConservativelyAllocatable;
261 void setVReg(unsigned VReg) { this->VReg = VReg; }
262 unsigned getVReg() const { return VReg; }
264 void setAllowedRegs(GraphMetadata::AllowedRegVecRef AllowedRegs) {
265 this->AllowedRegs = std::move(AllowedRegs);
267 const AllowedRegVector& getAllowedRegs() const { return *AllowedRegs; }
269 void setup(const Vector& Costs) {
270 NumOpts = Costs.getLength() - 1;
271 OptUnsafeEdges = std::unique_ptr<unsigned[]>(new unsigned[NumOpts]());
274 ReductionState getReductionState() const { return RS; }
275 void setReductionState(ReductionState RS) {
276 assert(RS >= this->RS && "A node's reduction state can not be downgraded");
280 // Remember this state to assert later that a non-infinite register
281 // option was available.
282 if (RS == ConservativelyAllocatable)
283 everConservativelyAllocatable = true;
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];
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];
304 bool isConservativelyAllocatable() const {
305 return (DeniedOpts < NumOpts) ||
306 (std::find(&OptUnsafeEdges[0], &OptUnsafeEdges[NumOpts], 0) !=
307 &OptUnsafeEdges[NumOpts]);
311 bool wasConservativelyAllocatable() const {
312 return everConservativelyAllocatable;
320 std::unique_ptr<unsigned[]> OptUnsafeEdges;
322 GraphMetadata::AllowedRegVecRef AllowedRegs;
325 bool everConservativelyAllocatable;
329 class RegAllocSolverImpl {
331 typedef MDMatrix<MatrixMetadata> RAMatrix;
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;
339 typedef GraphBase::NodeId NodeId;
340 typedef GraphBase::EdgeId EdgeId;
342 typedef RegAlloc::NodeMetadata NodeMetadata;
343 struct EdgeMetadata { };
344 typedef RegAlloc::GraphMetadata GraphMetadata;
346 typedef PBQP::Graph<RegAllocSolverImpl> Graph;
348 RegAllocSolverImpl(Graph &G) : G(G) {}
354 S = backpropagate(G, reduce());
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));
364 void handleRemoveNode(NodeId NId) {}
365 void handleSetNodeCosts(NodeId NId, const Vector& newCosts) {}
367 void handleAddEdge(EdgeId EId) {
368 handleReconnectEdge(EId, G.getEdgeNode1Id(EId));
369 handleReconnectEdge(EId, G.getEdgeNode2Id(EId));
372 void handleRemoveEdge(EdgeId EId) {
373 handleDisconnectEdge(EId, G.getEdgeNode1Id(EId));
374 handleDisconnectEdge(EId, G.getEdgeNode2Id(EId));
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));
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));
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);
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);
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);
408 // As the metadata may have changed with the update, the nodes may have
409 // become ConservativelyAllocatable or OptimallyReducible.
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);
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);
437 case NodeMetadata::ConservativelyAllocatable:
438 assert(ConservativelyAllocatableNodes.find(NId) !=
439 ConservativelyAllocatableNodes.end() &&
440 "Node not in conservatively allocatable set.");
441 ConservativelyAllocatableNodes.erase(NId);
443 case NodeMetadata::NotProvablyAllocatable:
444 assert(NotProvablyAllocatableNodes.find(NId) !=
445 NotProvablyAllocatableNodes.end() &&
446 "Node not in not-provably-allocatable set.");
447 NotProvablyAllocatableNodes.erase(NId);
452 void moveToOptimallyReducibleNodes(NodeId NId) {
453 removeFromCurrentSet(NId);
454 OptimallyReducibleNodes.insert(NId);
455 G.getNodeMetadata(NId).setReductionState(
456 NodeMetadata::OptimallyReducible);
459 void moveToConservativelyAllocatableNodes(NodeId NId) {
460 removeFromCurrentSet(NId);
461 ConservativelyAllocatableNodes.insert(NId);
462 G.getNodeMetadata(NId).setReductionState(
463 NodeMetadata::ConservativelyAllocatable);
466 void moveToNotProvablyAllocatableNodes(NodeId NId) {
467 removeFromCurrentSet(NId);
468 NotProvablyAllocatableNodes.insert(NId);
469 G.getNodeMetadata(NId).setReductionState(
470 NodeMetadata::NotProvablyAllocatable);
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);
481 moveToNotProvablyAllocatableNodes(NId);
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
491 std::vector<GraphBase::NodeId> reduce() {
492 assert(!G.empty() && "Cannot reduce empty graph.");
494 typedef GraphBase::NodeId NodeId;
495 std::vector<NodeId> NodeStack;
497 // Consume worklists.
499 if (!OptimallyReducibleNodes.empty()) {
500 NodeSet::iterator NItr = OptimallyReducibleNodes.begin();
502 OptimallyReducibleNodes.erase(NItr);
503 NodeStack.push_back(NId);
504 switch (G.getNodeDegree(NId)) {
513 default: llvm_unreachable("Not an optimally reducible node.");
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
522 NodeSet::iterator NItr = ConservativelyAllocatableNodes.begin();
524 ConservativelyAllocatableNodes.erase(NItr);
525 NodeStack.push_back(NId);
526 G.disconnectAllNeighborsFromNode(NId);
528 } else if (!NotProvablyAllocatableNodes.empty()) {
529 NodeSet::iterator NItr =
530 std::min_element(NotProvablyAllocatableNodes.begin(),
531 NotProvablyAllocatableNodes.end(),
532 SpillCostComparator(G));
534 NotProvablyAllocatableNodes.erase(NItr);
535 NodeStack.push_back(NId);
536 G.disconnectAllNeighborsFromNode(NId);
544 class SpillCostComparator {
546 SpillCostComparator(const Graph& G) : G(G) {}
547 bool operator()(NodeId N1Id, NodeId N2Id) {
548 PBQPNum N1SC = G.getNodeCosts(N1Id)[0];
549 PBQPNum N2SC = G.getNodeCosts(N2Id)[0];
551 return G.getNodeDegree(N1Id) < G.getNodeDegree(N2Id);
559 typedef std::set<NodeId> NodeSet;
560 NodeSet OptimallyReducibleNodes;
561 NodeSet ConservativelyAllocatableNodes;
562 NodeSet NotProvablyAllocatableNodes;
565 class PBQPRAGraph : public PBQP::Graph<RegAllocSolverImpl> {
567 typedef PBQP::Graph<RegAllocSolverImpl> BaseT;
569 PBQPRAGraph(GraphMetadata Metadata) : BaseT(Metadata) {}
571 /// @brief Dump this graph to dbgs().
574 /// @brief Dump this graph to an output stream.
575 /// @param OS Output stream to print on.
576 void dump(raw_ostream &OS) const;
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;
583 inline Solution solve(PBQPRAGraph& G) {
586 RegAllocSolverImpl RegAllocSolver(G);
587 return RegAllocSolver.solve();
590 } // namespace RegAlloc
593 /// @brief Create a PBQP register allocator instance.
595 createPBQPRegisterAllocator(char *customPassID = nullptr);
599 #endif /* LLVM_CODEGEN_REGALLOCPBQP_H */