class Graph

Declaration

template <typename SolverT>
class Graph : public GraphBase { /* full declaration omitted */ };

Description

PBQP Graph class. Instances of this class describe PBQP problems.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:46

Inherits from: GraphBase

Templates

SolverT

Member Variables

private llvm::PBQP::Graph::GraphMetadata Metadata

private llvm::PBQP::Graph::CostAllocator CostAlloc

private SolverT* Solver = nullptr

private llvm::PBQP::Graph::NodeVector Nodes

private llvm::PBQP::Graph::FreeNodeVector FreeNodeIds

private llvm::PBQP::Graph::EdgeVector Edges

private llvm::PBQP::Graph::FreeEdgeVector FreeEdgeIds

Method Overview

• private Graph<SolverT>(const Graph<SolverT> & Other)
• public Graph<SolverT>()
• public Graph<SolverT>(llvm::PBQP::Graph::GraphMetadata Metadata)
• private llvm::PBQP::GraphBase::EdgeId addConstructedEdge(llvm::PBQP::Graph::EdgeEntry E)
• private llvm::PBQP::GraphBase::NodeId addConstructedNode(llvm::PBQP::Graph::NodeEntry N)
• public template <typename OtherVectorT>llvm::PBQP::GraphBase::EdgeId addEdge(llvm::PBQP::GraphBase::NodeId N1Id, llvm::PBQP::GraphBase::NodeId N2Id, OtherVectorT Costs)
• public template <typename OtherMatrixPtrT>llvm::PBQP::GraphBase::NodeId addEdgeBypassingCostAllocator(llvm::PBQP::GraphBase::NodeId N1Id, llvm::PBQP::GraphBase::NodeId N2Id, OtherMatrixPtrT Costs)
• public template <typename OtherVectorT>llvm::PBQP::GraphBase::NodeId addNode(OtherVectorT Costs)
• public template <typename OtherVectorPtrT>llvm::PBQP::GraphBase::NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs)
• public llvm::PBQP::Graph::AdjEdgeIdSet adjEdgeIds(llvm::PBQP::GraphBase::NodeId NId)
• public void clear()
• public void disconnectAllNeighborsFromNode(llvm::PBQP::GraphBase::NodeId NId)
• public void disconnectEdge(llvm::PBQP::GraphBase::EdgeId EId, llvm::PBQP::GraphBase::NodeId NId)
• public llvm::PBQP::Graph::EdgeIdSet edgeIds() const
• public bool empty() const
• public llvm::PBQP::GraphBase::EdgeId findEdge(llvm::PBQP::GraphBase::NodeId N1Id, llvm::PBQP::GraphBase::NodeId N2Id)
• private const llvm::PBQP::Graph::EdgeEntry & getEdge(llvm::PBQP::GraphBase::EdgeId EId) const
• private llvm::PBQP::Graph::EdgeEntry & getEdge(llvm::PBQP::GraphBase::EdgeId EId)
• public const llvm::PBQP::Graph::Matrix & getEdgeCosts(llvm::PBQP::GraphBase::EdgeId EId) const
• public const llvm::PBQP::Graph::MatrixPtr & getEdgeCostsPtr(llvm::PBQP::GraphBase::EdgeId EId) const
• public const llvm::PBQP::Graph::EdgeMetadata & getEdgeMetadata(llvm::PBQP::GraphBase::EdgeId EId) const
• public llvm::PBQP::Graph::EdgeMetadata & getEdgeMetadata(llvm::PBQP::GraphBase::EdgeId EId)
• public llvm::PBQP::GraphBase::NodeId getEdgeNode1Id(llvm::PBQP::GraphBase::EdgeId EId) const
• public llvm::PBQP::GraphBase::NodeId getEdgeNode2Id(llvm::PBQP::GraphBase::EdgeId EId) const
• public llvm::PBQP::GraphBase::NodeId getEdgeOtherNodeId(llvm::PBQP::GraphBase::EdgeId EId, llvm::PBQP::GraphBase::NodeId NId)
• public const llvm::PBQP::Graph::GraphMetadata & getMetadata() const
• public llvm::PBQP::Graph::GraphMetadata & getMetadata()
• private llvm::PBQP::Graph::NodeEntry & getNode(llvm::PBQP::GraphBase::NodeId NId)
• private const llvm::PBQP::Graph::NodeEntry & getNode(llvm::PBQP::GraphBase::NodeId NId) const
• public const llvm::PBQP::Graph::Vector & getNodeCosts(llvm::PBQP::GraphBase::NodeId NId) const
• public const llvm::PBQP::Graph::VectorPtr & getNodeCostsPtr(llvm::PBQP::GraphBase::NodeId NId) const
• public typename NodeEntry::AdjEdgeList::size_type getNodeDegree(llvm::PBQP::GraphBase::NodeId NId) const
• public const llvm::PBQP::Graph::NodeMetadata & getNodeMetadata(llvm::PBQP::GraphBase::NodeId NId) const
• public llvm::PBQP::Graph::NodeMetadata & getNodeMetadata(llvm::PBQP::GraphBase::NodeId NId)
• public unsigned int getNumEdges() const
• public unsigned int getNumNodes() const
• public llvm::PBQP::Graph::NodeIdSet nodeIds() const
• public void reconnectEdge(llvm::PBQP::GraphBase::EdgeId EId, llvm::PBQP::GraphBase::NodeId NId)
• public void removeEdge(llvm::PBQP::GraphBase::EdgeId EId)
• public void removeNode(llvm::PBQP::GraphBase::NodeId NId)
• public template <typename OtherVectorT>void setNodeCosts(llvm::PBQP::GraphBase::NodeId NId, OtherVectorT Costs)
• public void setSolver(SolverT & S)
• public void unsetSolver()
• public template <typename OtherMatrixT>void updateEdgeCosts(llvm::PBQP::GraphBase::EdgeId EId, OtherMatrixT Costs)

Inherited from GraphBase:

• public invalidEdgeId
• public invalidNodeId

Methods

¶Graph<SolverT>(const Graph<SolverT>& Other)

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:176

Parameters

const Graph<SolverT>& Other

¶Graph<SolverT>()

Description

Construct an empty PBQP graph.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:341

¶Graph<SolverT>(
    llvm::PBQP::Graph::GraphMetadata Metadata)

Description

Construct an empty PBQP graph with the given graph metadata.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:344

Parameters

llvm::PBQP::Graph::GraphMetadata Metadata

¶llvm::PBQP::GraphBase::EdgeId addConstructedEdge(
    llvm::PBQP::Graph::EdgeEntry E)

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:205

Parameters

llvm::PBQP::Graph::EdgeEntry E

¶llvm::PBQP::GraphBase::NodeId addConstructedNode(
    llvm::PBQP::Graph::NodeEntry N)

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:192

Parameters

llvm::PBQP::Graph::NodeEntry N

¶template <typename OtherVectorT>
llvm::PBQP::GraphBase::EdgeId addEdge(
    llvm::PBQP::GraphBase::NodeId N1Id,
    llvm::PBQP::GraphBase::NodeId N2Id,
    OtherVectorT Costs)

Description

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

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:409

Templates

OtherVectorT

Parameters

llvm::PBQP::GraphBase::NodeId N1Id

First node.

llvm::PBQP::GraphBase::NodeId N2Id

Second node.

OtherVectorT Costs

Cost matrix for new edge.

Returns

Edge iterator for the added edge.

¶template <typename OtherMatrixPtrT>
llvm::PBQP::GraphBase::NodeId
addEdgeBypassingCostAllocator(
    llvm::PBQP::GraphBase::NodeId N1Id,
    llvm::PBQP::GraphBase::NodeId N2Id,
    OtherMatrixPtrT Costs)

Description

Add an edge bypassing the cost allocator. 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.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:434

Templates

OtherMatrixPtrT

Parameters

llvm::PBQP::GraphBase::NodeId N1Id

First node.

llvm::PBQP::GraphBase::NodeId N2Id

Second node.

OtherMatrixPtrT Costs

Cost matrix for new edge.

Returns

Edge iterator for the added edge.

¶template <typename OtherVectorT>
llvm::PBQP::GraphBase::NodeId addNode(
    OtherVectorT Costs)

Description

Add a node with the given costs.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:375

Templates

OtherVectorT

Parameters

OtherVectorT Costs

Cost vector for the new node.

Returns

Node iterator for the added node.

¶template <typename OtherVectorPtrT>
llvm::PBQP::GraphBase::NodeId
addNodeBypassingCostAllocator(
    OtherVectorPtrT Costs)

Description

Add a node bypassing the cost allocator. 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.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:396

Templates

OtherVectorPtrT

Parameters

OtherVectorPtrT Costs

Cost vector ptr for the new node (must be convertible to VectorPtr).

Returns

Node iterator for the added node.

¶llvm::PBQP::Graph::AdjEdgeIdSet adjEdgeIds(
    llvm::PBQP::GraphBase::NodeId NId)

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:452

Parameters

llvm::PBQP::GraphBase::NodeId NId

¶void clear()

Description

Remove all nodes and edges from the graph.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:663

¶void disconnectAllNeighborsFromNode(
    llvm::PBQP::GraphBase::NodeId NId)

Description

Convenience method to disconnect all neighbours from the given node.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:635

Parameters

llvm::PBQP::GraphBase::NodeId NId

¶void disconnectEdge(
    llvm::PBQP::GraphBase::EdgeId EId,
    llvm::PBQP::GraphBase::NodeId NId)

Description

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.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:625

Parameters

llvm::PBQP::GraphBase::EdgeId EId

llvm::PBQP::GraphBase::NodeId NId

¶llvm::PBQP::Graph::EdgeIdSet edgeIds() const

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:450

¶bool empty() const

Description

Returns true if the graph is empty.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:447

¶llvm::PBQP::GraphBase::EdgeId findEdge(
    llvm::PBQP::GraphBase::NodeId N1Id,
    llvm::PBQP::GraphBase::NodeId N2Id)

Description

Get the edge connecting two nodes.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:573

Parameters

llvm::PBQP::GraphBase::NodeId N1Id

First node id.

llvm::PBQP::GraphBase::NodeId N2Id

Second node id.

Returns

An id for edge (N1Id, N2Id) if such an edge exists, otherwise returns an invalid edge id.

¶const llvm::PBQP::Graph::EdgeEntry& getEdge(
    llvm::PBQP::GraphBase::EdgeId EId) const

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:190

Parameters

llvm::PBQP::GraphBase::EdgeId EId

¶llvm::PBQP::Graph::EdgeEntry& getEdge(
    llvm::PBQP::GraphBase::EdgeId EId)

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:189

Parameters

llvm::PBQP::GraphBase::EdgeId EId

¶const llvm::PBQP::Graph::Matrix& getEdgeCosts(
    llvm::PBQP::GraphBase::EdgeId EId) const

Description

Get an edge's cost matrix.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:530

Parameters

llvm::PBQP::GraphBase::EdgeId EId

Edge id.

Returns

Edge cost matrix.

¶const llvm::PBQP::Graph::MatrixPtr&
getEdgeCostsPtr(
    llvm::PBQP::GraphBase::EdgeId EId) const

Description

Get a MatrixPtr to a node's cost matrix. Rarely useful - use getEdgeCosts where possible. This method is primarily useful for duplicating costs quickly by bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer getEdgeCosts when dealing with edge cost values.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:523

Parameters

llvm::PBQP::GraphBase::EdgeId EId

Edge id.

Returns

MatrixPtr to edge cost matrix.

¶const llvm::PBQP::Graph::EdgeMetadata&
getEdgeMetadata(
    llvm::PBQP::GraphBase::EdgeId EId) const

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:538

Parameters

llvm::PBQP::GraphBase::EdgeId EId

¶llvm::PBQP::Graph::EdgeMetadata& getEdgeMetadata(
    llvm::PBQP::GraphBase::EdgeId EId)

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:534

Parameters

llvm::PBQP::GraphBase::EdgeId EId

¶llvm::PBQP::GraphBase::NodeId getEdgeNode1Id(
    llvm::PBQP::GraphBase::EdgeId EId) const

Description

Get the first node connected to this edge.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:545

Parameters

llvm::PBQP::GraphBase::EdgeId EId

Edge id.

Returns

The first node connected to the given edge.

¶llvm::PBQP::GraphBase::NodeId getEdgeNode2Id(
    llvm::PBQP::GraphBase::EdgeId EId) const

Description

Get the second node connected to this edge.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:552

Parameters

llvm::PBQP::GraphBase::EdgeId EId

Edge id.

Returns

The second node connected to the given edge.

¶llvm::PBQP::GraphBase::NodeId getEdgeOtherNodeId(
    llvm::PBQP::GraphBase::EdgeId EId,
    llvm::PBQP::GraphBase::NodeId NId)

Description

Get the "other" node connected to this edge.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:560

Parameters

llvm::PBQP::GraphBase::EdgeId EId

Edge id.

llvm::PBQP::GraphBase::NodeId NId

Node id for the "given" node.

Returns

The iterator for the "other" node connected to this edge.

¶const llvm::PBQP::Graph::GraphMetadata&
getMetadata() const

Description

Get a const-reference to the graph metadata.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:350

¶llvm::PBQP::Graph::GraphMetadata& getMetadata()

Description

Get a reference to the graph metadata.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:347

¶llvm::PBQP::Graph::NodeEntry& getNode(
    llvm::PBQP::GraphBase::NodeId NId)

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:180

Parameters

llvm::PBQP::GraphBase::NodeId NId

¶const llvm::PBQP::Graph::NodeEntry& getNode(
    llvm::PBQP::GraphBase::NodeId NId) const

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:184

Parameters

llvm::PBQP::GraphBase::NodeId NId

¶const llvm::PBQP::Graph::Vector& getNodeCosts(
    llvm::PBQP::GraphBase::NodeId NId) const

Description

Get a node's cost vector.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:488

Parameters

llvm::PBQP::GraphBase::NodeId NId

Node id.

Returns

Node cost vector.

¶const llvm::PBQP::Graph::VectorPtr&
getNodeCostsPtr(
    llvm::PBQP::GraphBase::NodeId NId) const

Description

Get a VectorPtr to a node's cost vector. Rarely useful - use getNodeCosts where possible. This method is primarily useful for duplicating costs quickly by bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer getNodeCosts when dealing with node cost values.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:481

Parameters

llvm::PBQP::GraphBase::NodeId NId

Node id.

Returns

VectorPtr to node cost vector.

¶typename NodeEntry::AdjEdgeList::size_type
getNodeDegree(
    llvm::PBQP::GraphBase::NodeId NId) const

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:500

Parameters

llvm::PBQP::GraphBase::NodeId NId

¶const llvm::PBQP::Graph::NodeMetadata&
getNodeMetadata(
    llvm::PBQP::GraphBase::NodeId NId) const

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:496

Parameters

llvm::PBQP::GraphBase::NodeId NId

¶llvm::PBQP::Graph::NodeMetadata& getNodeMetadata(
    llvm::PBQP::GraphBase::NodeId NId)

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:492

Parameters

llvm::PBQP::GraphBase::NodeId NId

¶unsigned int getNumEdges() const

Description

Get the number of edges in the graph.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:460

Returns

Number of edges in the graph.

¶unsigned int getNumNodes() const

Description

Get the number of nodes in the graph.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:456

Returns

Number of nodes in the graph.

¶llvm::PBQP::Graph::NodeIdSet nodeIds() const

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:449

¶void reconnectEdge(
    llvm::PBQP::GraphBase::EdgeId EId,
    llvm::PBQP::GraphBase::NodeId NId)

Description

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.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:644

Parameters

llvm::PBQP::GraphBase::EdgeId EId

llvm::PBQP::GraphBase::NodeId NId

¶void removeEdge(llvm::PBQP::GraphBase::EdgeId EId)

Description

Remove an edge from the graph.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:653

Parameters

llvm::PBQP::GraphBase::EdgeId EId

Edge id.

¶void removeNode(llvm::PBQP::GraphBase::NodeId NId)

Description

Remove a node from the graph.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:585

Parameters

llvm::PBQP::GraphBase::NodeId NId

Node id.

¶template <typename OtherVectorT>
void setNodeCosts(
    llvm::PBQP::GraphBase::NodeId NId,
    OtherVectorT Costs)

Description

Set a node's cost vector.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:466

Templates

OtherVectorT

Parameters

llvm::PBQP::GraphBase::NodeId NId

Node to update.

OtherVectorT Costs

New costs to set.

¶void setSolver(SolverT& S)

Description

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.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:356

Parameters

SolverT& S

¶void unsetSolver()

Description

Release from solver instance.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:366

¶template <typename OtherMatrixT>
void updateEdgeCosts(
    llvm::PBQP::GraphBase::EdgeId EId,
    OtherMatrixT Costs)

Description

Update an edge's cost matrix.

Declared at: llvm/include/llvm/CodeGen/PBQP/Graph.h:508

Templates

OtherMatrixT

Parameters

llvm::PBQP::GraphBase::EdgeId EId

Edge id.

OtherMatrixT Costs

New cost matrix.