15#ifndef LLVM_CODEGEN_REGALLOCPBQP_H
16#define LLVM_CODEGEN_REGALLOCPBQP_H
40class MachineBlockFrequencyInfo;
56 : UnsafeRows(new
bool[M.getRows() - 1]()),
57 UnsafeCols(new
bool[M.getCols() - 1]()) {
58 unsigned* ColCounts =
new unsigned[M.getCols() - 1]();
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()) {
66 UnsafeRows[i - 1] =
true;
67 UnsafeCols[j - 1] =
true;
70 WorstRow = std::max(WorstRow, RowCount);
72 unsigned WorstColCountForCurRow =
73 *std::max_element(ColCounts, ColCounts + M.getCols() - 1);
74 WorstCol = std::max(WorstCol, WorstColCountForCurRow);
87 unsigned WorstRow = 0;
88 unsigned WorstCol = 0;
89 std::unique_ptr<bool[]> UnsafeRows;
90 std::unique_ptr<bool[]> UnsafeCols;
103 std::copy(OptVec.begin(), OptVec.end(), Opts.get());
106 unsigned size()
const {
return NumOpts; }
110 if (NumOpts !=
Other.NumOpts)
112 return std::equal(Opts.get(), Opts.get() + NumOpts,
Other.Opts.get());
116 return !(*
this ==
Other);
120 unsigned NumOpts = 0;
121 std::unique_ptr<MCRegister[]> Opts;
126 MCRegister *OEnd = OptRegs.Opts.get() + OptRegs.NumOpts;
149 VRegToNodeId[VReg.
id()] = NId;
153 auto VRegItr = VRegToNodeId.find(VReg);
154 if (VRegItr == VRegToNodeId.end())
156 return VRegItr->second;
160 return AllowedRegVecs.
getValue(std::move(Allowed));
165 AllowedRegVecPool AllowedRegVecs;
178 NotProvablyAllocatable,
179 ConservativelyAllocatable,
188 AllowedRegs(
Other.AllowedRegs)
189#
if LLVM_ENABLE_ABI_BREAKING_CHECKS
191 everConservativelyAllocatable(
Other.everConservativelyAllocatable)
195 std::copy(&
Other.OptUnsafeEdges[0], &
Other.OptUnsafeEdges[NumOpts],
207 this->AllowedRegs = std::move(AllowedRegs);
213 OptUnsafeEdges = std::unique_ptr<unsigned[]>(
new unsigned[NumOpts]());
218 assert(RS >= this->RS &&
"A node's reduction state can not be downgraded");
221#if LLVM_ENABLE_ABI_BREAKING_CHECKS
224 if (RS == ConservativelyAllocatable)
225 everConservativelyAllocatable =
true;
231 const bool* UnsafeOpts =
233 for (
unsigned i = 0; i < NumOpts; ++i)
234 OptUnsafeEdges[i] += UnsafeOpts[i];
239 const bool* UnsafeOpts =
241 for (
unsigned i = 0; i < NumOpts; ++i)
242 OptUnsafeEdges[i] -= UnsafeOpts[i];
246 return (DeniedOpts < NumOpts) ||
247 (std::find(&OptUnsafeEdges[0], &OptUnsafeEdges[NumOpts], 0) !=
248 &OptUnsafeEdges[NumOpts]);
251#if LLVM_ENABLE_ABI_BREAKING_CHECKS
252 bool wasConservativelyAllocatable()
const {
253 return everConservativelyAllocatable;
259 unsigned NumOpts = 0;
260 unsigned DeniedOpts = 0;
261 std::unique_ptr<unsigned[]> OptUnsafeEdges;
265#if LLVM_ENABLE_ABI_BREAKING_CHECKS
266 bool everConservativelyAllocatable =
false;
303 "PBQP Graph should not contain single or zero-option nodes");
356 moveToOptimallyReducibleNodes(NId);
358 NodeMetadata::NotProvablyAllocatable &&
361 moveToConservativelyAllocatableNodes(NId);
365 void removeFromCurrentSet(
NodeId NId) {
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);
374 case NodeMetadata::ConservativelyAllocatable:
375 assert(ConservativelyAllocatableNodes.find(NId) !=
376 ConservativelyAllocatableNodes.end() &&
377 "Node not in conservatively allocatable set.");
378 ConservativelyAllocatableNodes.erase(NId);
380 case NodeMetadata::NotProvablyAllocatable:
381 assert(NotProvablyAllocatableNodes.find(NId) !=
382 NotProvablyAllocatableNodes.end() &&
383 "Node not in not-provably-allocatable set.");
384 NotProvablyAllocatableNodes.erase(NId);
389 void moveToOptimallyReducibleNodes(
NodeId NId) {
390 removeFromCurrentSet(NId);
391 OptimallyReducibleNodes.insert(NId);
393 NodeMetadata::OptimallyReducible);
396 void moveToConservativelyAllocatableNodes(
NodeId NId) {
397 removeFromCurrentSet(NId);
398 ConservativelyAllocatableNodes.insert(NId);
400 NodeMetadata::ConservativelyAllocatable);
403 void moveToNotProvablyAllocatableNodes(
NodeId NId) {
404 removeFromCurrentSet(NId);
405 NotProvablyAllocatableNodes.insert(NId);
407 NodeMetadata::NotProvablyAllocatable);
414 moveToOptimallyReducibleNodes(NId);
416 moveToConservativelyAllocatableNodes(NId);
418 moveToNotProvablyAllocatableNodes(NId);
428 std::vector<GraphBase::NodeId> reduce() {
429 assert(!G.
empty() &&
"Cannot reduce empty graph.");
432 std::vector<NodeId> NodeStack;
436 if (!OptimallyReducibleNodes.empty()) {
439 OptimallyReducibleNodes.erase(NItr);
440 NodeStack.push_back(NId);
452 }
else if (!ConservativelyAllocatableNodes.empty()) {
461 ConservativelyAllocatableNodes.erase(NItr);
462 NodeStack.push_back(NId);
464 }
else if (!NotProvablyAllocatableNodes.empty()) {
466 SpillCostComparator(G));
468 NotProvablyAllocatableNodes.erase(NItr);
469 NodeStack.push_back(NId);
478 class SpillCostComparator {
480 SpillCostComparator(
const Graph& G) :
G(
G) {}
483 PBQPNum N1SC =
G.getNodeCosts(N1Id)[0];
484 PBQPNum N2SC =
G.getNodeCosts(N2Id)[0];
486 return G.getNodeDegree(N1Id) <
G.getNodeDegree(N2Id);
495 using NodeSet = std::set<NodeId>;
496 NodeSet OptimallyReducibleNodes;
497 NodeSet ConservativelyAllocatableNodes;
498 NodeSet NotProvablyAllocatableNodes;
524 return RegAllocSolver.
solve();
This file defines the DenseMap class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
SetVector< SUnit * >::const_iterator iterator
static NodeId invalidNodeId()
Returns a value representing an invalid (non-existent) node.
void unsetSolver()
Release from solver instance.
NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const
NodeMetadata & getNodeMetadata(NodeId NId)
typename SolverT::GraphMetadata GraphMetadata
NodeId getEdgeNode2Id(EdgeId EId) const
Get the second node connected to this edge.
NodeId getEdgeNode1Id(EdgeId EId) const
Get the first node connected to this edge.
const Matrix & getEdgeCosts(EdgeId EId) const
Get an edge's cost matrix.
NodeIdSet nodeIds() const
bool empty() const
Returns true if the graph is empty.
void setSolver(SolverT &S)
Lock this graph to the given solver instance in preparation for running the solver.
void disconnectAllNeighborsFromNode(NodeId NId)
Convenience method to disconnect all neighbours from the given node.
const Vector & getNodeCosts(NodeId NId) const
Get a node's cost vector.
const Metadata & getMetadata() const
Holds a vector of the allowed physical regs for a vreg.
bool operator!=(const AllowedRegVector &Other) const
bool operator==(const AllowedRegVector &Other) const
MCRegister operator[](size_t I) const
AllowedRegVector(const std::vector< MCRegister > &OptVec)
AllowedRegVector(AllowedRegVector &&)=default
AllowedRegVector()=default
friend hash_code hash_value(const AllowedRegVector &)
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)
void handleSetNodeCosts(NodeId NId, const Vector &newCosts)
PBQP::Graph< RegAllocSolverImpl > Graph
void handleRemoveNode(NodeId NId)
void handleUpdateCosts(EdgeId EId, const Matrix &NewCosts)
void handleDisconnectEdge(EdgeId EId, NodeId NId)
void handleAddNode(NodeId NId)
void handleAddEdge(EdgeId EId)
RegAllocSolverImpl(Graph &G)
void handleReconnectEdge(EdgeId EId, NodeId NId)
Represents a solution to a PBQP problem.
PoolRef getValue(ValueKeyT ValueKey)
std::shared_ptr< const AllowedRegVector > PoolRef
unsigned getLength() const
Return the length of the vector.
Wrapper class representing virtual and physical registers.
constexpr unsigned id() const
An opaque object representing a hash code.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
hash_code hash_value(const AllowedRegVector &OptRegs)
Solution solve(PBQPRAGraph &G)
unsigned getSpillOptionIdx()
Spill option index.
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.
auto min_element(R &&Range)
Provide wrappers to std::min_element which take ranges instead of having to pass begin/end explicitly...
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.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Implement std::hash so that hash_code can be used in STL containers.