LLVM 19.0.0git
Classes | Public Types | Public Member Functions | List of all members
llvm::PBQP::Graph< SolverT > Class Template Reference

PBQP Graph class. More...

#include "llvm/CodeGen/PBQP/Graph.h"

Inheritance diagram for llvm::PBQP::Graph< SolverT >:
Inheritance graph
[legend]

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.
 
GraphMetadatagetMetadata ()
 Get a reference to the graph metadata.
 
const GraphMetadatagetMetadata () 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<typename OtherVectorT >
NodeId addNode (OtherVectorT Costs)
 Add a node with the given costs.
 
template<typename OtherVectorPtrT >
NodeId addNodeBypassingCostAllocator (OtherVectorPtrT Costs)
 Add a node bypassing the cost allocator.
 
template<typename OtherVectorT >
EdgeId addEdge (NodeId N1Id, NodeId N2Id, OtherVectorT Costs)
 Add an edge between the given nodes with the given costs.
 
template<typename OtherMatrixPtrT >
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<typename OtherVectorT >
void setNodeCosts (NodeId NId, OtherVectorT Costs)
 Set a node's cost vector.
 
const VectorPtrgetNodeCostsPtr (NodeId NId) const
 Get a VectorPtr to a node's cost vector.
 
const VectorgetNodeCosts (NodeId NId) const
 Get a node's cost vector.
 
NodeMetadatagetNodeMetadata (NodeId NId)
 
const NodeMetadatagetNodeMetadata (NodeId NId) const
 
NodeEntry::AdjEdgeList::size_type getNodeDegree (NodeId NId) const
 
template<typename OtherMatrixT >
void updateEdgeCosts (EdgeId EId, OtherMatrixT Costs)
 Update an edge's cost matrix.
 
const MatrixPtrgetEdgeCostsPtr (EdgeId EId) const
 Get a MatrixPtr to a node's cost matrix.
 
const MatrixgetEdgeCosts (EdgeId EId) const
 Get an edge's cost matrix.
 
EdgeMetadatagetEdgeMetadata (EdgeId EId)
 
const EdgeMetadatagetEdgeMetadata (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.
 

Detailed Description

template<typename SolverT>
class llvm::PBQP::Graph< SolverT >

PBQP Graph class.

Instances of this class describe PBQP problems.

Definition at line 46 of file Graph.h.

Member Typedef Documentation

◆ AdjEdgeItr

template<typename SolverT >
using llvm::PBQP::Graph< SolverT >::AdjEdgeItr = typename NodeEntry::AdjEdgeItr

Definition at line 228 of file Graph.h.

◆ EdgeMetadata

template<typename SolverT >
using llvm::PBQP::Graph< SolverT >::EdgeMetadata = typename SolverT::EdgeMetadata

Definition at line 58 of file Graph.h.

◆ GraphMetadata

template<typename SolverT >
using llvm::PBQP::Graph< SolverT >::GraphMetadata = typename SolverT::GraphMetadata

Definition at line 59 of file Graph.h.

◆ Matrix

template<typename SolverT >
using llvm::PBQP::Graph< SolverT >::Matrix = typename SolverT::Matrix

Definition at line 54 of file Graph.h.

◆ MatrixPtr

template<typename SolverT >
using llvm::PBQP::Graph< SolverT >::MatrixPtr = typename CostAllocator::MatrixPtr

Definition at line 56 of file Graph.h.

◆ NodeMetadata

template<typename SolverT >
using llvm::PBQP::Graph< SolverT >::NodeMetadata = typename SolverT::NodeMetadata

Definition at line 57 of file Graph.h.

◆ RawMatrix

template<typename SolverT >
using llvm::PBQP::Graph< SolverT >::RawMatrix = typename SolverT::RawMatrix

Definition at line 52 of file Graph.h.

◆ RawVector

template<typename SolverT >
using llvm::PBQP::Graph< SolverT >::RawVector = typename SolverT::RawVector

Definition at line 51 of file Graph.h.

◆ Vector

template<typename SolverT >
using llvm::PBQP::Graph< SolverT >::Vector = typename SolverT::Vector

Definition at line 53 of file Graph.h.

◆ VectorPtr

template<typename SolverT >
using llvm::PBQP::Graph< SolverT >::VectorPtr = typename CostAllocator::VectorPtr

Definition at line 55 of file Graph.h.

Constructor & Destructor Documentation

◆ Graph() [1/2]

template<typename SolverT >
llvm::PBQP::Graph< SolverT >::Graph ( )
default

Construct an empty PBQP graph.

◆ Graph() [2/2]

template<typename SolverT >
llvm::PBQP::Graph< SolverT >::Graph ( GraphMetadata  Metadata)
inline

Construct an empty PBQP graph with the given graph metadata.

Definition at line 344 of file Graph.h.

Member Function Documentation

◆ addEdge()

template<typename SolverT >
template<typename OtherVectorT >
EdgeId llvm::PBQP::Graph< SolverT >::addEdge ( NodeId  N1Id,
NodeId  N2Id,
OtherVectorT  Costs 
)
inline

Add an edge between the given nodes with the given costs.

Parameters
N1IdFirst node.
N2IdSecond node.
CostsCost matrix for new edge.
Returns
Edge iterator for the added edge.

Definition at line 409 of file Graph.h.

References assert(), and llvm::PBQP::Graph< SolverT >::getNodeCosts().

◆ addEdgeBypassingCostAllocator()

template<typename SolverT >
template<typename OtherMatrixPtrT >
NodeId llvm::PBQP::Graph< SolverT >::addEdgeBypassingCostAllocator ( NodeId  N1Id,
NodeId  N2Id,
OtherMatrixPtrT  Costs 
)
inline

Add an edge bypassing the cost allocator.

Parameters
N1IdFirst node.
N2IdSecond node.
CostsCost 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.

References assert(), and llvm::PBQP::Graph< SolverT >::getNodeCosts().

◆ addNode()

template<typename SolverT >
template<typename OtherVectorT >
NodeId llvm::PBQP::Graph< SolverT >::addNode ( OtherVectorT  Costs)
inline

Add a node with the given costs.

Parameters
CostsCost vector for the new node.
Returns
Node iterator for the added node.

Definition at line 375 of file Graph.h.

◆ addNodeBypassingCostAllocator()

template<typename SolverT >
template<typename OtherVectorPtrT >
NodeId llvm::PBQP::Graph< SolverT >::addNodeBypassingCostAllocator ( OtherVectorPtrT  Costs)
inline

Add a node bypassing the cost allocator.

Parameters
CostsCost 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<typename SolverT >
AdjEdgeIdSet llvm::PBQP::Graph< SolverT >::adjEdgeIds ( NodeId  NId)
inline

◆ clear()

template<typename SolverT >
void llvm::PBQP::Graph< SolverT >::clear ( )
inline

Remove all nodes and edges from the graph.

Definition at line 663 of file Graph.h.

◆ disconnectAllNeighborsFromNode()

template<typename SolverT >
void llvm::PBQP::Graph< SolverT >::disconnectAllNeighborsFromNode ( NodeId  NId)
inline

Convenience method to disconnect all neighbours from the given node.

Definition at line 635 of file Graph.h.

References llvm::PBQP::Graph< SolverT >::adjEdgeIds(), llvm::PBQP::Graph< SolverT >::disconnectEdge(), and llvm::PBQP::Graph< SolverT >::getEdgeOtherNodeId().

◆ disconnectEdge()

template<typename SolverT >
void llvm::PBQP::Graph< SolverT >::disconnectEdge ( EdgeId  EId,
NodeId  NId 
)
inline

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.

References E.

Referenced by llvm::PBQP::Graph< SolverT >::disconnectAllNeighborsFromNode().

◆ edgeIds()

template<typename SolverT >
EdgeIdSet llvm::PBQP::Graph< SolverT >::edgeIds ( ) const
inline

Definition at line 450 of file Graph.h.

Referenced by llvm::PBQP::Graph< SolverT >::setSolver().

◆ empty()

template<typename SolverT >
bool llvm::PBQP::Graph< SolverT >::empty ( ) const
inline

Returns true if the graph is empty.

Definition at line 447 of file Graph.h.

References llvm::PBQP::Graph< SolverT >::NodeIdSet::empty().

◆ findEdge()

template<typename SolverT >
EdgeId llvm::PBQP::Graph< SolverT >::findEdge ( NodeId  N1Id,
NodeId  N2Id 
)
inline

Get the edge connecting two nodes.

Parameters
N1IdFirst node id.
N2IdSecond 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.

References llvm::PBQP::Graph< SolverT >::adjEdgeIds(), llvm::PBQP::Graph< SolverT >::getEdgeNode1Id(), llvm::PBQP::Graph< SolverT >::getEdgeNode2Id(), and llvm::PBQP::GraphBase::invalidEdgeId().

◆ getEdgeCosts()

template<typename SolverT >
const Matrix & llvm::PBQP::Graph< SolverT >::getEdgeCosts ( EdgeId  EId) const
inline

◆ getEdgeCostsPtr()

template<typename SolverT >
const MatrixPtr & llvm::PBQP::Graph< SolverT >::getEdgeCostsPtr ( EdgeId  EId) const
inline

Get a MatrixPtr to a node's cost matrix.

Rarely useful - use getEdgeCosts where possible.

Parameters
EIdEdge id.
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<typename SolverT >
EdgeMetadata & llvm::PBQP::Graph< SolverT >::getEdgeMetadata ( EdgeId  EId)
inline

Definition at line 534 of file Graph.h.

◆ getEdgeMetadata() [2/2]

template<typename SolverT >
const EdgeMetadata & llvm::PBQP::Graph< SolverT >::getEdgeMetadata ( EdgeId  EId) const
inline

Definition at line 538 of file Graph.h.

◆ getEdgeNode1Id()

template<typename SolverT >
NodeId llvm::PBQP::Graph< SolverT >::getEdgeNode1Id ( EdgeId  EId) const
inline

Get the first node connected to this edge.

Parameters
EIdEdge id.
Returns
The first node connected to the given edge.

Definition at line 545 of file Graph.h.

Referenced by llvm::PBQP::Graph< SolverT >::findEdge(), llvm::PBQP::RegAlloc::RegAllocSolverImpl::handleAddEdge(), and llvm::PBQP::RegAlloc::RegAllocSolverImpl::handleUpdateCosts().

◆ getEdgeNode2Id()

template<typename SolverT >
NodeId llvm::PBQP::Graph< SolverT >::getEdgeNode2Id ( EdgeId  EId) const
inline

◆ getEdgeOtherNodeId()

template<typename SolverT >
NodeId llvm::PBQP::Graph< SolverT >::getEdgeOtherNodeId ( EdgeId  EId,
NodeId  NId 
)
inline

Get the "other" node connected to this edge.

Parameters
EIdEdge id.
NIdNode id for the "given" node.
Returns
The iterator for the "other" node connected to this edge.

Definition at line 560 of file Graph.h.

References E.

Referenced by llvm::PBQP::Graph< SolverT >::disconnectAllNeighborsFromNode().

◆ getMetadata() [1/2]

template<typename SolverT >
GraphMetadata & llvm::PBQP::Graph< SolverT >::getMetadata ( )
inline

Get a reference to the graph metadata.

Definition at line 347 of file Graph.h.

◆ getMetadata() [2/2]

template<typename SolverT >
const GraphMetadata & llvm::PBQP::Graph< SolverT >::getMetadata ( ) const
inline

Get a const-reference to the graph metadata.

Definition at line 350 of file Graph.h.

◆ getNodeCosts()

template<typename SolverT >
const Vector & llvm::PBQP::Graph< SolverT >::getNodeCosts ( NodeId  NId) const
inline

◆ getNodeCostsPtr()

template<typename SolverT >
const VectorPtr & llvm::PBQP::Graph< SolverT >::getNodeCostsPtr ( NodeId  NId) const
inline

Get a VectorPtr to a node's cost vector.

Rarely useful - use getNodeCosts where possible.

Parameters
NIdNode id.
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< SolverT >::getNodeCosts().

◆ getNodeDegree()

template<typename SolverT >
NodeEntry::AdjEdgeList::size_type llvm::PBQP::Graph< SolverT >::getNodeDegree ( NodeId  NId) const
inline

Definition at line 500 of file Graph.h.

◆ getNodeMetadata() [1/2]

template<typename SolverT >
NodeMetadata & llvm::PBQP::Graph< SolverT >::getNodeMetadata ( NodeId  NId)
inline

◆ getNodeMetadata() [2/2]

template<typename SolverT >
const NodeMetadata & llvm::PBQP::Graph< SolverT >::getNodeMetadata ( NodeId  NId) const
inline

Definition at line 496 of file Graph.h.

◆ getNumEdges()

template<typename SolverT >
unsigned llvm::PBQP::Graph< SolverT >::getNumEdges ( ) const
inline

Get the number of edges in the graph.

Returns
Number of edges in the graph.

Definition at line 460 of file Graph.h.

References llvm::PBQP::Graph< SolverT >::EdgeIdSet::size().

◆ getNumNodes()

template<typename SolverT >
unsigned llvm::PBQP::Graph< SolverT >::getNumNodes ( ) const
inline

Get the number of nodes in the graph.

Returns
Number of nodes in the graph.

Definition at line 456 of file Graph.h.

References llvm::PBQP::Graph< SolverT >::NodeIdSet::size().

◆ nodeIds()

template<typename SolverT >
NodeIdSet llvm::PBQP::Graph< SolverT >::nodeIds ( ) const
inline

Definition at line 449 of file Graph.h.

Referenced by llvm::PBQP::Graph< SolverT >::setSolver().

◆ reconnectEdge()

template<typename SolverT >
void llvm::PBQP::Graph< SolverT >::reconnectEdge ( EdgeId  EId,
NodeId  NId 
)
inline

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.

References E.

◆ removeEdge()

template<typename SolverT >
void llvm::PBQP::Graph< SolverT >::removeEdge ( EdgeId  EId)
inline

Remove an edge from the graph.

Parameters
EIdEdge id.

Definition at line 653 of file Graph.h.

References E.

Referenced by llvm::PBQP::Graph< SolverT >::removeNode().

◆ removeNode()

template<typename SolverT >
void llvm::PBQP::Graph< SolverT >::removeNode ( NodeId  NId)
inline

Remove a node from the graph.

Parameters
NIdNode id.

Definition at line 585 of file Graph.h.

References N, and llvm::PBQP::Graph< SolverT >::removeEdge().

◆ setNodeCosts()

template<typename SolverT >
template<typename OtherVectorT >
void llvm::PBQP::Graph< SolverT >::setNodeCosts ( NodeId  NId,
OtherVectorT  Costs 
)
inline

Set a node's cost vector.

Parameters
NIdNode to update.
CostsNew costs to set.

Definition at line 466 of file Graph.h.

◆ setSolver()

template<typename SolverT >
void llvm::PBQP::Graph< SolverT >::setSolver ( SolverT &  S)
inline

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.

References assert(), llvm::PBQP::Graph< SolverT >::edgeIds(), and llvm::PBQP::Graph< SolverT >::nodeIds().

Referenced by llvm::PBQP::RegAlloc::RegAllocSolverImpl::solve().

◆ unsetSolver()

template<typename SolverT >
void llvm::PBQP::Graph< SolverT >::unsetSolver ( )
inline

Release from solver instance.

Definition at line 366 of file Graph.h.

References assert().

Referenced by llvm::PBQP::RegAlloc::RegAllocSolverImpl::solve().

◆ updateEdgeCosts()

template<typename SolverT >
template<typename OtherMatrixT >
void llvm::PBQP::Graph< SolverT >::updateEdgeCosts ( EdgeId  EId,
OtherMatrixT  Costs 
)
inline

Update an edge's cost matrix.

Parameters
EIdEdge id.
CostsNew cost matrix.

Definition at line 508 of file Graph.h.


The documentation for this class was generated from the following file: