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(AllowedRegVector &&) = default;
94 unsigned size() const { return NumOpts; }
95 unsigned operator[](size_t I) const { return Opts[I]; }
97 bool operator==(const AllowedRegVector &Other) const {
98 if (NumOpts != Other.NumOpts)
100 return std::equal(Opts.get(), Opts.get() + NumOpts, Other.Opts.get());
103 bool operator!=(const AllowedRegVector &Other) const {
104 return !(*this == Other);
109 std::unique_ptr<unsigned[]> Opts;
112 inline hash_code hash_value(const AllowedRegVector &OptRegs) {
113 unsigned *OStart = OptRegs.Opts.get();
114 unsigned *OEnd = OptRegs.Opts.get() + OptRegs.NumOpts;
115 return hash_combine(OptRegs.NumOpts,
116 hash_combine_range(OStart, OEnd));
119 /// \brief Holds graph-level metadata relevant to PBQP RA problems.
120 class GraphMetadata {
122 typedef ValuePool<AllowedRegVector> AllowedRegVecPool;
125 typedef AllowedRegVecPool::PoolRef AllowedRegVecRef;
127 GraphMetadata(MachineFunction &MF,
129 MachineBlockFrequencyInfo &MBFI)
130 : MF(MF), LIS(LIS), MBFI(MBFI) {}
134 MachineBlockFrequencyInfo &MBFI;
136 void setNodeIdForVReg(unsigned VReg, GraphBase::NodeId NId) {
137 VRegToNodeId[VReg] = NId;
140 GraphBase::NodeId getNodeIdForVReg(unsigned VReg) const {
141 auto VRegItr = VRegToNodeId.find(VReg);
142 if (VRegItr == VRegToNodeId.end())
143 return GraphBase::invalidNodeId();
144 return VRegItr->second;
147 AllowedRegVecRef getAllowedRegs(AllowedRegVector Allowed) {
148 return AllowedRegVecs.getValue(std::move(Allowed));
152 DenseMap<unsigned, GraphBase::NodeId> VRegToNodeId;
153 AllowedRegVecPool AllowedRegVecs;
156 /// \brief Holds solver state and other metadata relevant to each PBQP RA node.
159 typedef RegAlloc::AllowedRegVector AllowedRegVector;
161 // The node's reduction state. The order in this enum is important,
162 // as it is assumed nodes can only progress up (i.e. towards being
163 // optimally reducible) when reducing the graph.
166 NotProvablyAllocatable,
167 ConservativelyAllocatable,
172 : RS(Unprocessed), NumOpts(0), DeniedOpts(0), OptUnsafeEdges(nullptr),
175 , everConservativelyAllocatable(false)
179 NodeMetadata(const NodeMetadata &Other)
180 : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts),
181 OptUnsafeEdges(new unsigned[NumOpts]), VReg(Other.VReg),
182 AllowedRegs(Other.AllowedRegs)
184 , everConservativelyAllocatable(Other.everConservativelyAllocatable)
188 std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts],
193 NodeMetadata(NodeMetadata &&Other) = default;
195 NodeMetadata& operator=(NodeMetadata &&Other) = default;
197 void setVReg(unsigned VReg) { this->VReg = VReg; }
198 unsigned getVReg() const { return VReg; }
200 void setAllowedRegs(GraphMetadata::AllowedRegVecRef AllowedRegs) {
201 this->AllowedRegs = std::move(AllowedRegs);
203 const AllowedRegVector& getAllowedRegs() const { return *AllowedRegs; }
205 void setup(const Vector& Costs) {
206 NumOpts = Costs.getLength() - 1;
207 OptUnsafeEdges = std::unique_ptr<unsigned[]>(new unsigned[NumOpts]());
210 ReductionState getReductionState() const { return RS; }
211 void setReductionState(ReductionState RS) {
212 assert(RS >= this->RS && "A node's reduction state can not be downgraded");
216 // Remember this state to assert later that a non-infinite register
217 // option was available.
218 if (RS == ConservativelyAllocatable)
219 everConservativelyAllocatable = true;
223 void handleAddEdge(const MatrixMetadata& MD, bool Transpose) {
224 DeniedOpts += Transpose ? MD.getWorstRow() : MD.getWorstCol();
225 const bool* UnsafeOpts =
226 Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
227 for (unsigned i = 0; i < NumOpts; ++i)
228 OptUnsafeEdges[i] += UnsafeOpts[i];
231 void handleRemoveEdge(const MatrixMetadata& MD, bool Transpose) {
232 DeniedOpts -= Transpose ? MD.getWorstRow() : MD.getWorstCol();
233 const bool* UnsafeOpts =
234 Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
235 for (unsigned i = 0; i < NumOpts; ++i)
236 OptUnsafeEdges[i] -= UnsafeOpts[i];
239 bool isConservativelyAllocatable() const {
240 return (DeniedOpts < NumOpts) ||
241 (std::find(&OptUnsafeEdges[0], &OptUnsafeEdges[NumOpts], 0) !=
242 &OptUnsafeEdges[NumOpts]);
246 bool wasConservativelyAllocatable() const {
247 return everConservativelyAllocatable;
255 std::unique_ptr<unsigned[]> OptUnsafeEdges;
257 GraphMetadata::AllowedRegVecRef AllowedRegs;
260 bool everConservativelyAllocatable;
264 class RegAllocSolverImpl {
266 typedef MDMatrix<MatrixMetadata> RAMatrix;
268 typedef PBQP::Vector RawVector;
269 typedef PBQP::Matrix RawMatrix;
270 typedef PBQP::Vector Vector;
271 typedef RAMatrix Matrix;
272 typedef PBQP::PoolCostAllocator<Vector, Matrix> CostAllocator;
274 typedef GraphBase::NodeId NodeId;
275 typedef GraphBase::EdgeId EdgeId;
277 typedef RegAlloc::NodeMetadata NodeMetadata;
278 struct EdgeMetadata { };
279 typedef RegAlloc::GraphMetadata GraphMetadata;
281 typedef PBQP::Graph<RegAllocSolverImpl> Graph;
283 RegAllocSolverImpl(Graph &G) : G(G) {}
289 S = backpropagate(G, reduce());
294 void handleAddNode(NodeId NId) {
295 assert(G.getNodeCosts(NId).getLength() > 1 &&
296 "PBQP Graph should not contain single or zero-option nodes");
297 G.getNodeMetadata(NId).setup(G.getNodeCosts(NId));
299 void handleRemoveNode(NodeId NId) {}
300 void handleSetNodeCosts(NodeId NId, const Vector& newCosts) {}
302 void handleAddEdge(EdgeId EId) {
303 handleReconnectEdge(EId, G.getEdgeNode1Id(EId));
304 handleReconnectEdge(EId, G.getEdgeNode2Id(EId));
307 void handleDisconnectEdge(EdgeId EId, NodeId NId) {
308 NodeMetadata& NMd = G.getNodeMetadata(NId);
309 const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
310 NMd.handleRemoveEdge(MMd, NId == G.getEdgeNode2Id(EId));
314 void handleReconnectEdge(EdgeId EId, NodeId NId) {
315 NodeMetadata& NMd = G.getNodeMetadata(NId);
316 const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
317 NMd.handleAddEdge(MMd, NId == G.getEdgeNode2Id(EId));
320 void handleUpdateCosts(EdgeId EId, const Matrix& NewCosts) {
321 NodeId N1Id = G.getEdgeNode1Id(EId);
322 NodeId N2Id = G.getEdgeNode2Id(EId);
323 NodeMetadata& N1Md = G.getNodeMetadata(N1Id);
324 NodeMetadata& N2Md = G.getNodeMetadata(N2Id);
325 bool Transpose = N1Id != G.getEdgeNode1Id(EId);
327 // Metadata are computed incrementally. First, update them
328 // by removing the old cost.
329 const MatrixMetadata& OldMMd = G.getEdgeCosts(EId).getMetadata();
330 N1Md.handleRemoveEdge(OldMMd, Transpose);
331 N2Md.handleRemoveEdge(OldMMd, !Transpose);
333 // And update now the metadata with the new cost.
334 const MatrixMetadata& MMd = NewCosts.getMetadata();
335 N1Md.handleAddEdge(MMd, Transpose);
336 N2Md.handleAddEdge(MMd, !Transpose);
338 // As the metadata may have changed with the update, the nodes may have
339 // become ConservativelyAllocatable or OptimallyReducible.
346 void promote(NodeId NId, NodeMetadata& NMd) {
347 if (G.getNodeDegree(NId) == 3) {
348 // This node is becoming optimally reducible.
349 moveToOptimallyReducibleNodes(NId);
350 } else if (NMd.getReductionState() ==
351 NodeMetadata::NotProvablyAllocatable &&
352 NMd.isConservativelyAllocatable()) {
353 // This node just became conservatively allocatable.
354 moveToConservativelyAllocatableNodes(NId);
358 void removeFromCurrentSet(NodeId NId) {
359 switch (G.getNodeMetadata(NId).getReductionState()) {
360 case NodeMetadata::Unprocessed: break;
361 case NodeMetadata::OptimallyReducible:
362 assert(OptimallyReducibleNodes.find(NId) !=
363 OptimallyReducibleNodes.end() &&
364 "Node not in optimally reducible set.");
365 OptimallyReducibleNodes.erase(NId);
367 case NodeMetadata::ConservativelyAllocatable:
368 assert(ConservativelyAllocatableNodes.find(NId) !=
369 ConservativelyAllocatableNodes.end() &&
370 "Node not in conservatively allocatable set.");
371 ConservativelyAllocatableNodes.erase(NId);
373 case NodeMetadata::NotProvablyAllocatable:
374 assert(NotProvablyAllocatableNodes.find(NId) !=
375 NotProvablyAllocatableNodes.end() &&
376 "Node not in not-provably-allocatable set.");
377 NotProvablyAllocatableNodes.erase(NId);
382 void moveToOptimallyReducibleNodes(NodeId NId) {
383 removeFromCurrentSet(NId);
384 OptimallyReducibleNodes.insert(NId);
385 G.getNodeMetadata(NId).setReductionState(
386 NodeMetadata::OptimallyReducible);
389 void moveToConservativelyAllocatableNodes(NodeId NId) {
390 removeFromCurrentSet(NId);
391 ConservativelyAllocatableNodes.insert(NId);
392 G.getNodeMetadata(NId).setReductionState(
393 NodeMetadata::ConservativelyAllocatable);
396 void moveToNotProvablyAllocatableNodes(NodeId NId) {
397 removeFromCurrentSet(NId);
398 NotProvablyAllocatableNodes.insert(NId);
399 G.getNodeMetadata(NId).setReductionState(
400 NodeMetadata::NotProvablyAllocatable);
405 for (auto NId : G.nodeIds()) {
406 if (G.getNodeDegree(NId) < 3)
407 moveToOptimallyReducibleNodes(NId);
408 else if (G.getNodeMetadata(NId).isConservativelyAllocatable())
409 moveToConservativelyAllocatableNodes(NId);
411 moveToNotProvablyAllocatableNodes(NId);
415 // Compute a reduction order for the graph by iteratively applying PBQP
416 // reduction rules. Locally optimal rules are applied whenever possible (R0,
417 // R1, R2). If no locally-optimal rules apply then any conservatively
418 // allocatable node is reduced. Finally, if no conservatively allocatable
419 // node exists then the node with the lowest spill-cost:degree ratio is
421 std::vector<GraphBase::NodeId> reduce() {
422 assert(!G.empty() && "Cannot reduce empty graph.");
424 typedef GraphBase::NodeId NodeId;
425 std::vector<NodeId> NodeStack;
427 // Consume worklists.
429 if (!OptimallyReducibleNodes.empty()) {
430 NodeSet::iterator NItr = OptimallyReducibleNodes.begin();
432 OptimallyReducibleNodes.erase(NItr);
433 NodeStack.push_back(NId);
434 switch (G.getNodeDegree(NId)) {
443 default: llvm_unreachable("Not an optimally reducible node.");
445 } else if (!ConservativelyAllocatableNodes.empty()) {
446 // Conservatively allocatable nodes will never spill. For now just
447 // take the first node in the set and push it on the stack. When we
448 // start optimizing more heavily for register preferencing, it may
449 // would be better to push nodes with lower 'expected' or worst-case
450 // register costs first (since early nodes are the most
452 NodeSet::iterator NItr = ConservativelyAllocatableNodes.begin();
454 ConservativelyAllocatableNodes.erase(NItr);
455 NodeStack.push_back(NId);
456 G.disconnectAllNeighborsFromNode(NId);
458 } else if (!NotProvablyAllocatableNodes.empty()) {
459 NodeSet::iterator NItr =
460 std::min_element(NotProvablyAllocatableNodes.begin(),
461 NotProvablyAllocatableNodes.end(),
462 SpillCostComparator(G));
464 NotProvablyAllocatableNodes.erase(NItr);
465 NodeStack.push_back(NId);
466 G.disconnectAllNeighborsFromNode(NId);
474 class SpillCostComparator {
476 SpillCostComparator(const Graph& G) : G(G) {}
477 bool operator()(NodeId N1Id, NodeId N2Id) {
478 PBQPNum N1SC = G.getNodeCosts(N1Id)[0];
479 PBQPNum N2SC = G.getNodeCosts(N2Id)[0];
481 return G.getNodeDegree(N1Id) < G.getNodeDegree(N2Id);
489 typedef std::set<NodeId> NodeSet;
490 NodeSet OptimallyReducibleNodes;
491 NodeSet ConservativelyAllocatableNodes;
492 NodeSet NotProvablyAllocatableNodes;
495 class PBQPRAGraph : public PBQP::Graph<RegAllocSolverImpl> {
497 typedef PBQP::Graph<RegAllocSolverImpl> BaseT;
499 PBQPRAGraph(GraphMetadata Metadata) : BaseT(Metadata) {}
501 /// @brief Dump this graph to dbgs().
504 /// @brief Dump this graph to an output stream.
505 /// @param OS Output stream to print on.
506 void dump(raw_ostream &OS) const;
508 /// @brief Print a representation of this graph in DOT format.
509 /// @param OS Output stream to print on.
510 void printDot(raw_ostream &OS) const;
513 inline Solution solve(PBQPRAGraph& G) {
516 RegAllocSolverImpl RegAllocSolver(G);
517 return RegAllocSolver.solve();
520 } // namespace RegAlloc
523 /// @brief Create a PBQP register allocator instance.
525 createPBQPRegisterAllocator(char *customPassID = nullptr);
529 #endif /* LLVM_CODEGEN_REGALLOCPBQP_H */