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

Inheritance diagram for llvm::PBQP::Graph< SolverT >:

Collaboration diagram for llvm::PBQP::Graph< SolverT >:

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. More...

	Graph (GraphMetadata Metadata)
	Construct an empty PBQP graph with the given graph metadata. More...

GraphMetadata &	getMetadata ()
	Get a reference to the graph metadata. More...

const GraphMetadata &	getMetadata () const
	Get a const-reference to the graph metadata. More...

void	setSolver (SolverT &S)
	Lock this graph to the given solver instance in preparation for running the solver. More...

void	unsetSolver ()
	Release from solver instance. More...

template<typename OtherVectorT >
NodeId	addNode (OtherVectorT Costs)
	Add a node with the given costs. More...

template<typename OtherVectorPtrT >
NodeId	addNodeBypassingCostAllocator (OtherVectorPtrT Costs)
	Add a node bypassing the cost allocator. More...

template<typename OtherVectorT >
EdgeId	addEdge (NodeId N1Id, NodeId N2Id, OtherVectorT Costs)
	Add an edge between the given nodes with the given costs. More...

template<typename OtherMatrixPtrT >
NodeId	addEdgeBypassingCostAllocator (NodeId N1Id, NodeId N2Id, OtherMatrixPtrT Costs)
	Add an edge bypassing the cost allocator. More...

bool	empty () const
	Returns true if the graph is empty. More...

NodeIdSet	nodeIds () const

EdgeIdSet	edgeIds () const

AdjEdgeIdSet	adjEdgeIds (NodeId NId)

unsigned	getNumNodes () const
	Get the number of nodes in the graph. More...

unsigned	getNumEdges () const
	Get the number of edges in the graph. More...

template<typename OtherVectorT >
void	setNodeCosts (NodeId NId, OtherVectorT Costs)
	Set a node's cost vector. More...

const VectorPtr &	getNodeCostsPtr (NodeId NId) const
	Get a VectorPtr to a node's cost vector. More...

const Vector &	getNodeCosts (NodeId NId) const
	Get a node's cost vector. More...

NodeMetadata &	getNodeMetadata (NodeId NId)

const NodeMetadata &	getNodeMetadata (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. More...

const MatrixPtr &	getEdgeCostsPtr (EdgeId EId) const
	Get a MatrixPtr to a node's cost matrix. More...

const Matrix &	getEdgeCosts (EdgeId EId) const
	Get an edge's cost matrix. More...

EdgeMetadata &	getEdgeMetadata (EdgeId EId)

const EdgeMetadata &	getEdgeMetadata (EdgeId EId) const

NodeId	getEdgeNode1Id (EdgeId EId) const
	Get the first node connected to this edge. More...

NodeId	getEdgeNode2Id (EdgeId EId) const
	Get the second node connected to this edge. More...

NodeId	getEdgeOtherNodeId (EdgeId EId, NodeId NId)
	Get the "other" node connected to this edge. More...

EdgeId	findEdge (NodeId N1Id, NodeId N2Id)
	Get the edge connecting two nodes. More...

void	removeNode (NodeId NId)
	Remove a node from the graph. More...

void	disconnectEdge (EdgeId EId, NodeId NId)
	Disconnect an edge from the given node. More...

void	disconnectAllNeighborsFromNode (NodeId NId)
	Convenience method to disconnect all neighbours from the given node. More...

void	reconnectEdge (EdgeId EId, NodeId NId)
	Re-attach an edge to its nodes. More...

void	removeEdge (EdgeId EId)
	Remove an edge from the graph. More...

void	clear ()
	Remove all nodes and edges from the graph. More...

Additional Inherited Members
Static Public Member Functions inherited from llvm::PBQP::GraphBase
static NodeId	invalidNodeId ()
	Returns a value representing an invalid (non-existent) node. More...

static EdgeId	invalidEdgeId ()
	Returns a value representing an invalid (non-existent) edge. More...

Detailed Description

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

PBQP Graph class.

Instances of this class describe PBQP problems.

Definition at line 47 of file Graph.h.

Member Typedef Documentation

◆ AdjEdgeItr

template<typename SolverT>

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

Definition at line 229 of file Graph.h.

◆ EdgeMetadata

template<typename SolverT>

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

Definition at line 59 of file Graph.h.

◆ GraphMetadata

template<typename SolverT>

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

Definition at line 60 of file Graph.h.

◆ Matrix

template<typename SolverT>

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

Definition at line 55 of file Graph.h.

◆ MatrixPtr

template<typename SolverT>

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

Definition at line 57 of file Graph.h.

◆ NodeMetadata

template<typename SolverT>

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

Definition at line 58 of file Graph.h.

◆ RawMatrix

template<typename SolverT>

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

Definition at line 53 of file Graph.h.

◆ RawVector

template<typename SolverT>

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

Definition at line 52 of file Graph.h.

◆ Vector

template<typename SolverT>

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

Definition at line 54 of file Graph.h.

◆ VectorPtr

template<typename SolverT>

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

Definition at line 56 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 345 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

N1Id	First node.
N2Id	Second node.
Costs	Cost matrix for new edge.

Returns: Edge iterator for the added edge.

Definition at line 410 of file Graph.h.

◆ 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

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 435 of file Graph.h.

◆ addNode()

template<typename SolverT>

template<typename OtherVectorT >

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

inline

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 376 of file Graph.h.

Referenced by isACalleeSavedRegister().

◆ addNodeBypassingCostAllocator()

template<typename SolverT>

template<typename OtherVectorPtrT >

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

inline

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 397 of file Graph.h.

◆ adjEdgeIds()

template<typename SolverT>

AdjEdgeIdSet llvm::PBQP::Graph< SolverT >::adjEdgeIds ( NodeId NId )

inline

Definition at line 453 of file Graph.h.

◆ clear()

template<typename SolverT>

void llvm::PBQP::Graph< SolverT >::clear ( )

inline

Remove all nodes and edges from the graph.

Definition at line 664 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 636 of file Graph.h.

◆ 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 626 of file Graph.h.

◆ edgeIds()

template<typename SolverT>

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

inline

Definition at line 451 of file Graph.h.

◆ empty()

template<typename SolverT>

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

inline

Returns true if the graph is empty.

Definition at line 448 of file Graph.h.

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

◆ findEdge()

template<typename SolverT>

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

inline

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 574 of file Graph.h.

◆ getEdgeCosts()

template<typename SolverT>

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

inline

Get an edge's cost matrix.

Parameters

EId Edge id.

Returns: Edge cost matrix.

Definition at line 531 of file Graph.h.

◆ 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

EId Edge 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 524 of file Graph.h.

◆ getEdgeMetadata() [1/2]

template<typename SolverT>

EdgeMetadata& llvm::PBQP::Graph< SolverT >::getEdgeMetadata ( EdgeId EId )

inline

Definition at line 535 of file Graph.h.

◆ getEdgeMetadata() [2/2]

template<typename SolverT>

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

inline

Definition at line 539 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

EId Edge id.

Returns: The first node connected to the given edge.

Definition at line 546 of file Graph.h.

◆ getEdgeNode2Id()

template<typename SolverT>

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

inline

Get the second node connected to this edge.

Parameters

EId Edge id.

Returns: The second node connected to the given edge.

Definition at line 553 of file Graph.h.

◆ getEdgeOtherNodeId()

template<typename SolverT>

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

inline

Get the "other" node connected to this edge.

Parameters

EId	Edge id.
NId	Node id for the "given" node.

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

Definition at line 561 of file Graph.h.

◆ getMetadata() [1/2]

template<typename SolverT>

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

inline

Get a reference to the graph metadata.

Definition at line 348 of file Graph.h.

Referenced by llvm::A57ChainingConstraint::apply(), isACalleeSavedRegister(), and PrintNodeInfo().

◆ 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 351 of file Graph.h.

◆ getNodeCosts()

template<typename SolverT>

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

inline

Get a node's cost vector.

Parameters

NId Node id.

Returns: Node cost vector.

Definition at line 489 of file Graph.h.

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

◆ 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

NId Node 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 482 of file Graph.h.

◆ getNodeDegree()

template<typename SolverT>

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

inline

Definition at line 501 of file Graph.h.

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

◆ getNodeMetadata() [1/2]

template<typename SolverT>

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

inline

Definition at line 493 of file Graph.h.

Referenced by isACalleeSavedRegister(), and PrintNodeInfo().

◆ getNodeMetadata() [2/2]

template<typename SolverT>

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

inline

Definition at line 497 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 461 of file Graph.h.

◆ 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 457 of file Graph.h.

◆ nodeIds()

template<typename SolverT>

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

inline

Definition at line 450 of file Graph.h.

Referenced by isACalleeSavedRegister().

◆ 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 645 of file Graph.h.

◆ removeEdge()

template<typename SolverT>

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

inline

Remove an edge from the graph.

Parameters

EId Edge id.

Definition at line 654 of file Graph.h.

◆ removeNode()

template<typename SolverT>

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

inline

Remove a node from the graph.

Parameters

NId Node id.

Definition at line 586 of file Graph.h.

◆ 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

NId	Node to update.
Costs	New costs to set.

Definition at line 467 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 357 of file Graph.h.

◆ unsetSolver()

template<typename SolverT>

void llvm::PBQP::Graph< SolverT >::unsetSolver ( )

inline

Release from solver instance.

Definition at line 367 of file Graph.h.

◆ 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

EId	Edge id.
Costs	New cost matrix.

Definition at line 509 of file Graph.h.

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

include/llvm/CodeGen/PBQP/Graph.h

Classes

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

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

Member Typedef Documentation

◆ AdjEdgeItr

◆ EdgeMetadata

◆ GraphMetadata

◆ Matrix

◆ MatrixPtr

◆ NodeMetadata

◆ RawMatrix

◆ RawVector

◆ Vector

◆ VectorPtr

Constructor & Destructor Documentation

◆ Graph() [1/2]

◆ Graph() [2/2]

Member Function Documentation

◆ addEdge()

◆ addEdgeBypassingCostAllocator()

◆ addNode()

◆ addNodeBypassingCostAllocator()

◆ adjEdgeIds()

◆ clear()

◆ disconnectAllNeighborsFromNode()

◆ disconnectEdge()

◆ edgeIds()

◆ empty()

◆ findEdge()

◆ getEdgeCosts()

◆ getEdgeCostsPtr()

◆ getEdgeMetadata() [1/2]

◆ getEdgeMetadata() [2/2]

◆ getEdgeNode1Id()

◆ getEdgeNode2Id()

◆ getEdgeOtherNodeId()

◆ getMetadata() [1/2]

◆ getMetadata() [2/2]

◆ getNodeCosts()

◆ getNodeCostsPtr()

◆ getNodeDegree()

◆ getNodeMetadata() [1/2]

◆ getNodeMetadata() [2/2]

◆ getNumEdges()

◆ getNumNodes()

◆ nodeIds()

◆ reconnectEdge()

◆ removeEdge()

◆ removeNode()

◆ setNodeCosts()

◆ setSolver()

◆ unsetSolver()

◆ updateEdgeCosts()

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