LLVM: llvm::PBQP::Graph< SolverT > Class Template Reference (original) (raw)
#include "[llvm/CodeGen/PBQP/Graph.h](CodeGen%5F2PBQP%5F2Graph%5F8h%5Fsource.html)"
| Classes | |
|---|---|
| class | AdjEdgeIdSet |
| class | EdgeIdSet |
| class | EdgeItr |
| class | NodeIdSet |
| class | NodeItr |
| Public Types | |
|---|---|
| using | RawVector = typename SolverT::RawVector |
| using | RawMatrix = typename SolverT::RawMatrix |
| using | Vector = typename SolverT::Vector |
| using | Matrix = typename SolverT::Matrix |
| using | VectorPtr = typename CostAllocator::VectorPtr |
| using | MatrixPtr = typename CostAllocator::MatrixPtr |
| using | NodeMetadata = typename SolverT::NodeMetadata |
| using | EdgeMetadata = typename SolverT::EdgeMetadata |
| using | GraphMetadata = typename SolverT::GraphMetadata |
| using | AdjEdgeItr = typename NodeEntry::AdjEdgeItr |
| Public Types inherited from llvm::PBQP::GraphBase | |
| using | NodeId = unsigned |
| using | EdgeId = unsigned |
| Public Member Functions | |
|---|---|
| Graph ()=default | |
| Construct an empty PBQP graph. | |
| Graph (GraphMetadata Metadata) | |
| Construct an empty PBQP graph with the given graph metadata. | |
| GraphMetadata & | getMetadata () |
| Get a reference to the graph metadata. | |
| const GraphMetadata & | getMetadata () const |
| Get a const-reference to the graph metadata. | |
| void | setSolver (SolverT &S) |
| Lock this graph to the given solver instance in preparation for running the solver. | |
| void | unsetSolver () |
| Release from solver instance. | |
| template | |
| NodeId | addNode (OtherVectorT Costs) |
| Add a node with the given costs. | |
| template | |
| NodeId | addNodeBypassingCostAllocator (OtherVectorPtrT Costs) |
| Add a node bypassing the cost allocator. | |
| template | |
| EdgeId | addEdge (NodeId N1Id, NodeId N2Id, OtherVectorT Costs) |
| Add an edge between the given nodes with the given costs. | |
| template | |
| NodeId | addEdgeBypassingCostAllocator (NodeId N1Id, NodeId N2Id, OtherMatrixPtrT Costs) |
| Add an edge bypassing the cost allocator. | |
| bool | empty () const |
| Returns true if the graph is empty. | |
| NodeIdSet | nodeIds () const |
| EdgeIdSet | edgeIds () const |
| AdjEdgeIdSet | adjEdgeIds (NodeId NId) |
| unsigned | getNumNodes () const |
| Get the number of nodes in the graph. | |
| unsigned | getNumEdges () const |
| Get the number of edges in the graph. | |
| template | |
| void | setNodeCosts (NodeId NId, OtherVectorT Costs) |
| Set a node's cost vector. | |
| const VectorPtr & | getNodeCostsPtr (NodeId NId) const |
| Get a VectorPtr to a node's cost vector. | |
| const Vector & | getNodeCosts (NodeId NId) const |
| Get a node's cost vector. | |
| NodeMetadata & | getNodeMetadata (NodeId NId) |
| const NodeMetadata & | getNodeMetadata (NodeId NId) const |
| NodeEntry::AdjEdgeList::size_type | getNodeDegree (NodeId NId) const |
| template | |
| void | updateEdgeCosts (EdgeId EId, OtherMatrixT Costs) |
| Update an edge's cost matrix. | |
| const MatrixPtr & | getEdgeCostsPtr (EdgeId EId) const |
| Get a MatrixPtr to a node's cost matrix. | |
| const Matrix & | getEdgeCosts (EdgeId EId) const |
| Get an edge's cost matrix. | |
| EdgeMetadata & | getEdgeMetadata (EdgeId EId) |
| const EdgeMetadata & | getEdgeMetadata (EdgeId EId) const |
| NodeId | getEdgeNode1Id (EdgeId EId) const |
| Get the first node connected to this edge. | |
| NodeId | getEdgeNode2Id (EdgeId EId) const |
| Get the second node connected to this edge. | |
| NodeId | getEdgeOtherNodeId (EdgeId EId, NodeId NId) |
| Get the "other" node connected to this edge. | |
| EdgeId | findEdge (NodeId N1Id, NodeId N2Id) |
| Get the edge connecting two nodes. | |
| void | removeNode (NodeId NId) |
| Remove a node from the graph. | |
| void | disconnectEdge (EdgeId EId, NodeId NId) |
| Disconnect an edge from the given node. | |
| void | disconnectAllNeighborsFromNode (NodeId NId) |
| Convenience method to disconnect all neighbours from the given node. | |
| void | reconnectEdge (EdgeId EId, NodeId NId) |
| Re-attach an edge to its nodes. | |
| void | removeEdge (EdgeId EId) |
| Remove an edge from the graph. | |
| void | clear () |
| Remove all nodes and edges from the graph. |
| Additional Inherited Members | |
|---|---|
| Static Public Member Functions inherited from llvm::PBQP::GraphBase | |
| static NodeId | invalidNodeId () |
| Returns a value representing an invalid (non-existent) node. | |
| static EdgeId | invalidEdgeId () |
| Returns a value representing an invalid (non-existent) edge. |
template
class llvm::PBQP::Graph< SolverT >
Instances of this class describe PBQP problems.
Definition at line 46 of file Graph.h.
◆ AdjEdgeItr
template
◆ EdgeMetadata
template
Definition at line 58 of file Graph.h.
◆ GraphMetadata
template
Definition at line 59 of file Graph.h.
◆ Matrix
template
Definition at line 54 of file Graph.h.
◆ MatrixPtr
template
Definition at line 56 of file Graph.h.
◆ NodeMetadata
template
Definition at line 57 of file Graph.h.
◆ RawMatrix
template
Definition at line 52 of file Graph.h.
◆ RawVector
template
Definition at line 51 of file Graph.h.
◆ Vector
template
Definition at line 53 of file Graph.h.
◆ VectorPtr
template
Definition at line 55 of file Graph.h.
◆ Graph() [1/2]
template
Construct an empty PBQP graph.
◆ Graph() [2/2]
template
Construct an empty PBQP graph with the given graph metadata.
Definition at line 344 of file Graph.h.
◆ addEdge()
template
template
Add an edge between the given nodes with the given costs.
Parameters
| N1Id | First node. |
|---|---|
| N2Id | Second node. |
| Costs | Cost matrix for new edge. |
Returns
Edge iterator for the added edge.
Definition at line 409 of file Graph.h.
◆ addEdgeBypassingCostAllocator()
template
template
Add an edge bypassing the cost allocator.
Parameters
| N1Id | First node. |
|---|---|
| N2Id | Second node. |
| Costs | Cost matrix for new edge. |
Returns
Edge iterator for the added edge.
This method allows for fast addition of an edge whose costs don't need to be passed through the cost allocator. The most common use case for this is when duplicating costs from an existing edge (when using a pooling allocator). These have already been uniqued, so we can avoid re-constructing and re-uniquing them by attaching them directly to the new edge.
Definition at line 434 of file Graph.h.
◆ addNode()
template
template
Add a node with the given costs.
Parameters
| Costs | Cost vector for the new node. |
|---|
Returns
Node iterator for the added node.
Definition at line 375 of file Graph.h.
◆ addNodeBypassingCostAllocator()
template
template
Add a node bypassing the cost allocator.
Parameters
| Costs | Cost vector ptr for the new node (must be convertible to VectorPtr). |
|---|
Returns
Node iterator for the added node.
This method allows for fast addition of a node whose costs don't need to be passed through the cost allocator. The most common use case for this is when duplicating costs from an existing node (when using a pooling allocator). These have already been uniqued, so we can avoid re-constructing and re-uniquing them by attaching them directly to the new node.
Definition at line 396 of file Graph.h.
◆ adjEdgeIds()
template
◆ clear()
template
Remove all nodes and edges from the graph.
Definition at line 663 of file Graph.h.
◆ disconnectAllNeighborsFromNode()
template
Convenience method to disconnect all neighbours from the given node.
Definition at line 635 of file Graph.h.
◆ disconnectEdge()
template
Disconnect an edge from the given node.
Removes the given edge from the adjacency list of the given node. This operation leaves the edge in an 'asymmetric' state: It will no longer appear in an iteration over the given node's (NId's) edges, but will appear in an iteration over the 'other', unnamed node's edges.
This does not correspond to any normal graph operation, but exists to support efficient PBQP graph-reduction based solvers. It is used to 'effectively' remove the unnamed node from the graph while the solver is performing the reduction. The solver will later call reconnectNode to restore the edge in the named node's adjacency list.
Since the degree of a node is the number of connected edges, disconnecting an edge from a node 'u' will cause the degree of 'u' to drop by 1.
A disconnected edge WILL still appear in an iteration over the graph edges.
A disconnected edge should not be removed from the graph, it should be reconnected first.
A disconnected edge can be reconnected by calling the reconnectEdge method.
Definition at line 625 of file Graph.h.
Referenced by llvm::PBQP::Graph< RegAllocSolverImpl >::disconnectAllNeighborsFromNode().
◆ edgeIds()
template
◆ empty()
template
Returns true if the graph is empty.
Definition at line 447 of file Graph.h.
◆ findEdge()
template
Get the edge connecting two nodes.
Parameters
| N1Id | First node id. |
|---|---|
| N2Id | Second node id. |
Returns
An id for edge (N1Id, N2Id) if such an edge exists, otherwise returns an invalid edge id.
Definition at line 573 of file Graph.h.
◆ getEdgeCosts()
template
Get an edge's cost matrix.
Parameters
Returns
Edge cost matrix.
Definition at line 530 of file Graph.h.
◆ getEdgeCostsPtr()
template
Get a MatrixPtr to a node's cost matrix.
Rarely useful - use getEdgeCosts where possible.
Parameters
Returns
MatrixPtr to edge cost matrix.
This method is primarily useful for duplicating costs quickly by bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer getEdgeCosts when dealing with edge cost values.
Definition at line 523 of file Graph.h.
◆ getEdgeMetadata() [1/2]
template
◆ getEdgeMetadata() [2/2]
template
◆ getEdgeNode1Id()
template
◆ getEdgeNode2Id()
template
◆ getEdgeOtherNodeId()
template
◆ getMetadata() [1/2]
template
Get a reference to the graph metadata.
Definition at line 347 of file Graph.h.
◆ getMetadata() [2/2]
template
Get a const-reference to the graph metadata.
Definition at line 350 of file Graph.h.
◆ getNodeCosts()
template
◆ getNodeCostsPtr()
template
Get a VectorPtr to a node's cost vector.
Rarely useful - use getNodeCosts where possible.
Parameters
Returns
VectorPtr to node cost vector.
This method is primarily useful for duplicating costs quickly by bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer getNodeCosts when dealing with node cost values.
Definition at line 481 of file Graph.h.
Referenced by llvm::PBQP::Graph< RegAllocSolverImpl >::getNodeCosts().
◆ getNodeDegree()
template
◆ getNodeMetadata() [1/2]
template
◆ getNodeMetadata() [2/2]
template
◆ getNumEdges()
template
Get the number of edges in the graph.
Returns
Number of edges in the graph.
Definition at line 460 of file Graph.h.
◆ getNumNodes()
template
Get the number of nodes in the graph.
Returns
Number of nodes in the graph.
Definition at line 456 of file Graph.h.
◆ nodeIds()
template
◆ reconnectEdge()
template
Re-attach an edge to its nodes.
Adds an edge that had been previously disconnected back into the adjacency set of the nodes that the edge connects.
Definition at line 644 of file Graph.h.
◆ removeEdge()
template
◆ removeNode()
template
Remove a node from the graph.
Parameters
Definition at line 585 of file Graph.h.
◆ setNodeCosts()
template
template
Set a node's cost vector.
Parameters
| NId | Node to update. |
|---|---|
| Costs | New costs to set. |
Definition at line 466 of file Graph.h.
◆ setSolver()
template
Lock this graph to the given solver instance in preparation for running the solver.
This method will call solver.handleAddNode for each node in the graph, and handleAddEdge for each edge, to give the solver an opportunity to set up any requried metadata.
Definition at line 356 of file Graph.h.
◆ unsetSolver()
template
Release from solver instance.
Definition at line 366 of file Graph.h.
◆ updateEdgeCosts()
template
template
Update an edge's cost matrix.
Parameters
| EId | Edge id. |
|---|---|
| Costs | New cost matrix. |
Definition at line 508 of file Graph.h.
The documentation for this class was generated from the following file:
- include/llvm/CodeGen/PBQP/Graph.h