#include <PointsToGraph.hpp>

Classes
struct	NodeData

Public Types
enum class	NodeKind : uint8_t { RegisterNode = 0 , AllocaNode , DeltaNode , ImportNode , LambdaNode , MallocNode , ExternalNode , COUNT }

using	NodeIndex = uint32_t

Public Member Functions
	PointsToGraph (const PointsToGraph &)=delete

	PointsToGraph (PointsToGraph &&)=delete

PointsToGraph &	operator= (const PointsToGraph &)=delete

PointsToGraph &	operator= (PointsToGraph &&)=delete

AllocaNodeRange	allocaNodes () const noexcept

DeltaNodeRange	deltaNodes () const noexcept

ImportNodeRange	importNodes () const noexcept

LambdaNodeRange	lambdaNodes () const noexcept

MallocNodeRange	mallocNodes () const noexcept

NodeIndex	getExternalMemoryNode () const noexcept

RegisterNodeRange	registerNodes () const noexcept

size_t	numAllocaNodes () const noexcept

size_t	numDeltaNodes () const noexcept

size_t	numImportNodes () const noexcept

size_t	numLambdaNodes () const noexcept

size_t	numMallocNodes () const noexcept

size_t	numRegisterNodes () const noexcept

size_t	numMappedRegisters () const noexcept

size_t	numMemoryNodes () const noexcept

size_t	numNodes () const noexcept

bool	hasNodeForAlloca (const rvsdg::SimpleNode &node) const

bool	hasNodeForDelta (const rvsdg::DeltaNode &node) const

bool	hasNodeForImport (const rvsdg::GraphImport &argument) const

bool	hasNodeForLambda (const rvsdg::LambdaNode &node) const

bool	hasNodeForMalloc (const rvsdg::SimpleNode &node) const

bool	hasNodeForRegister (const rvsdg::Output &output) const

NodeIndex	getNodeForAlloca (const rvsdg::SimpleNode &node) const

NodeIndex	getNodeForDelta (const rvsdg::DeltaNode &node) const

NodeIndex	getNodeForImport (const rvsdg::GraphImport &argument) const

NodeIndex	getNodeForLambda (const rvsdg::LambdaNode &node) const

NodeIndex	getNodeForMalloc (const rvsdg::SimpleNode &node) const

NodeIndex	getNodeForRegister (const rvsdg::Output &output) const

std::optional< NodeIndex >	tryGetNodeForRegister (const rvsdg::Output &output) const noexcept

NodeKind	getNodeKind (NodeIndex index) const

bool	isRegisterNode (NodeIndex index) const

bool	isMemoryNode (NodeIndex index) const

bool	isExternallyAvailable (NodeIndex index) const

bool	isTargetingAllExternallyAvailable (NodeIndex index) const

bool	isNodeConstant (NodeIndex index) const noexcept

std::optional< size_t >	tryGetNodeSize (NodeIndex index) const noexcept

const util::HashSet< NodeIndex > &	getExplicitTargets (NodeIndex index) const

bool	isTargeting (NodeIndex source, NodeIndex target) const

const std::vector< NodeIndex > &	getExternallyAvailableNodes () const noexcept

size_t	numExternallyAvailableNodes () const noexcept

size_t	numNodesTargetingAllExternallyAvailable () const noexcept

const rvsdg::SimpleNode &	getAllocaForNode (NodeIndex index) const

const rvsdg::DeltaNode &	getDeltaForNode (NodeIndex index) const

const rvsdg::GraphImport &	getImportForNode (NodeIndex index) const

const rvsdg::LambdaNode &	getLambdaForNode (NodeIndex index) const

const rvsdg::SimpleNode &	getMallocForNode (NodeIndex index) const

NodeIndex	addNodeForAlloca (const rvsdg::SimpleNode &allocaNode, bool externallyAvailable)

NodeIndex	addNodeForDelta (const rvsdg::DeltaNode &deltaNode, bool externallyAvailable)

NodeIndex	addNodeForImport (const rvsdg::GraphImport &argument, bool externallyAvailable)

NodeIndex	addNodeForLambda (const rvsdg::LambdaNode &lambdaNode, bool externallyAvailable)

NodeIndex	addNodeForMalloc (const rvsdg::SimpleNode &mallocNode, bool externallyAvailable)

NodeIndex	addNodeForRegisters ()

void	mapRegisterToNode (const rvsdg::Output &output, NodeIndex nodeIndex)

void	markAsTargetsAllExternallyAvailable (NodeIndex index)

bool	addTarget (NodeIndex source, NodeIndex target)

std::pair< size_t, size_t >	numEdges () const noexcept

std::string	getNodeDebugString (NodeIndex index, char separator=' ') const

bool	isSupergraphOf (const PointsToGraph &subgraph) const

Static Public Member Functions
static void	dumpGraph (util::graph::Writer &graphWriter, const PointsToGraph &pointsToGraph)

static std::string	dumpDot (const PointsToGraph &pointsToGraph)

static std::unique_ptr< PointsToGraph >	create ()

Static Public Attributes
static constexpr NodeIndex	externalMemoryNode = 0

Private Types
using	AllocaNodeMap = std::unordered_map< const rvsdg::SimpleNode *, NodeIndex >

using	DeltaNodeMap = std::unordered_map< const rvsdg::DeltaNode *, NodeIndex >

using	ImportNodeMap = std::unordered_map< const rvsdg::GraphImport *, NodeIndex >

using	LambdaNodeMap = std::unordered_map< const rvsdg::LambdaNode *, NodeIndex >

using	MallocNodeMap = std::unordered_map< const rvsdg::SimpleNode *, NodeIndex >

using	RegisterNodeMap = std::unordered_map< const rvsdg::Output *, NodeIndex >

using	AllocaNodeIterator = util::MapValueIterator< const NodeIndex, AllocaNodeMap::const_iterator >

using	AllocaNodeRange = util::IteratorRange< AllocaNodeIterator >

using	DeltaNodeIterator = util::MapValueIterator< const NodeIndex, DeltaNodeMap::const_iterator >

using	DeltaNodeRange = util::IteratorRange< DeltaNodeIterator >

using	ImportNodeIterator = util::MapValueIterator< const NodeIndex, ImportNodeMap::const_iterator >

using	ImportNodeRange = util::IteratorRange< ImportNodeIterator >

using	LambdaNodeIterator = util::MapValueIterator< const NodeIndex, LambdaNodeMap::const_iterator >

using	LambdaNodeRange = util::IteratorRange< LambdaNodeIterator >

using	MallocNodeIterator = util::MapValueIterator< const NodeIndex, MallocNodeMap::const_iterator >

using	MallocNodeRange = util::IteratorRange< MallocNodeIterator >

using	RegisterNodeIterator = std::vector< NodeIndex >::const_iterator

using	RegisterNodeRange = util::IteratorRange< RegisterNodeIterator >

using	ExternallyAvailableIterator = std::vector< NodeIndex >::const_iterator

using	ExternallyAvailableRange = util::IteratorRange< ExternallyAvailableIterator >

Private Member Functions
	PointsToGraph ()

NodeIndex	addNode (NodeKind kind, bool externallyAvailable, bool isConstant, std::optional< size_t > memorySize, const void *object)

Private Attributes
std::vector< NodeData >	nodeData_

std::vector< util::HashSet< NodeIndex > >	nodeExplicitTargets_

std::vector< const void * >	nodeObjects_

AllocaNodeMap	allocaMap_

DeltaNodeMap	deltaMap_

ImportNodeMap	importMap_

LambdaNodeMap	lambdaMap_

MallocNodeMap	mallocMap_

RegisterNodeMap	registerMap_

std::vector< NodeIndex >	registerNodes_

std::vector< NodeIndex >	externallyAvailableNodes_

size_t	numNodesTargetingAllExternallyAvailable_ = 0

Detailed Description

The PointsToGraph is a graph where nodes represent virtual registers or locations in memory. An edge, e.g., X -> Y, represents the possibility of node X containing a pointer to memory represented by node Y.

An edge X -> Y can be represented in two ways:

explicitly: node Y is a member of node X's set of explicit targets.
implicitly: node X is flagged as targeting all externally available memory, and node Y is flagged as being externally available.

Definition at line 46 of file PointsToGraph.hpp.

Member Typedef Documentation

◆ AllocaNodeIterator

using jlm::llvm::aa::PointsToGraph::AllocaNodeIterator = util::MapValueIterator<const NodeIndex, AllocaNodeMap::const_iterator>

private

Definition at line 114 of file PointsToGraph.hpp.

◆ AllocaNodeMap

using jlm::llvm::aa::PointsToGraph::AllocaNodeMap = std::unordered_map<const rvsdg::SimpleNode *, NodeIndex>

private

Definition at line 107 of file PointsToGraph.hpp.

◆ AllocaNodeRange

using jlm::llvm::aa::PointsToGraph::AllocaNodeRange = util::IteratorRange<AllocaNodeIterator>

private

Definition at line 115 of file PointsToGraph.hpp.

◆ DeltaNodeIterator

using jlm::llvm::aa::PointsToGraph::DeltaNodeIterator = util::MapValueIterator<const NodeIndex, DeltaNodeMap::const_iterator>

private

Definition at line 117 of file PointsToGraph.hpp.

◆ DeltaNodeMap

using jlm::llvm::aa::PointsToGraph::DeltaNodeMap = std::unordered_map<const rvsdg::DeltaNode *, NodeIndex>

private

Definition at line 108 of file PointsToGraph.hpp.

◆ DeltaNodeRange

using jlm::llvm::aa::PointsToGraph::DeltaNodeRange = util::IteratorRange<DeltaNodeIterator>

private

Definition at line 118 of file PointsToGraph.hpp.

◆ ExternallyAvailableIterator

using jlm::llvm::aa::PointsToGraph::ExternallyAvailableIterator = std::vector<NodeIndex>::const_iterator

private

Definition at line 132 of file PointsToGraph.hpp.

◆ ExternallyAvailableRange

using jlm::llvm::aa::PointsToGraph::ExternallyAvailableRange = util::IteratorRange<ExternallyAvailableIterator>

private

Definition at line 133 of file PointsToGraph.hpp.

◆ ImportNodeIterator

using jlm::llvm::aa::PointsToGraph::ImportNodeIterator = util::MapValueIterator<const NodeIndex, ImportNodeMap::const_iterator>

private

Definition at line 120 of file PointsToGraph.hpp.

◆ ImportNodeMap

using jlm::llvm::aa::PointsToGraph::ImportNodeMap = std::unordered_map<const rvsdg::GraphImport *, NodeIndex>

private

Definition at line 109 of file PointsToGraph.hpp.

◆ ImportNodeRange

using jlm::llvm::aa::PointsToGraph::ImportNodeRange = util::IteratorRange<ImportNodeIterator>

private

Definition at line 121 of file PointsToGraph.hpp.

◆ LambdaNodeIterator

using jlm::llvm::aa::PointsToGraph::LambdaNodeIterator = util::MapValueIterator<const NodeIndex, LambdaNodeMap::const_iterator>

private

Definition at line 123 of file PointsToGraph.hpp.

◆ LambdaNodeMap

using jlm::llvm::aa::PointsToGraph::LambdaNodeMap = std::unordered_map<const rvsdg::LambdaNode *, NodeIndex>

private

Definition at line 110 of file PointsToGraph.hpp.

◆ LambdaNodeRange

using jlm::llvm::aa::PointsToGraph::LambdaNodeRange = util::IteratorRange<LambdaNodeIterator>

private

Definition at line 124 of file PointsToGraph.hpp.

◆ MallocNodeIterator

using jlm::llvm::aa::PointsToGraph::MallocNodeIterator = util::MapValueIterator<const NodeIndex, MallocNodeMap::const_iterator>

private

Definition at line 126 of file PointsToGraph.hpp.

◆ MallocNodeMap

using jlm::llvm::aa::PointsToGraph::MallocNodeMap = std::unordered_map<const rvsdg::SimpleNode *, NodeIndex>

private

Definition at line 111 of file PointsToGraph.hpp.

◆ MallocNodeRange

using jlm::llvm::aa::PointsToGraph::MallocNodeRange = util::IteratorRange<MallocNodeIterator>

private

Definition at line 127 of file PointsToGraph.hpp.

◆ NodeIndex

using jlm::llvm::aa::PointsToGraph::NodeIndex = uint32_t

Definition at line 49 of file PointsToGraph.hpp.

◆ RegisterNodeIterator

using jlm::llvm::aa::PointsToGraph::RegisterNodeIterator = std::vector<NodeIndex>::const_iterator

private

Definition at line 129 of file PointsToGraph.hpp.

◆ RegisterNodeMap

using jlm::llvm::aa::PointsToGraph::RegisterNodeMap = std::unordered_map<const rvsdg::Output *, NodeIndex>

private

Definition at line 112 of file PointsToGraph.hpp.

◆ RegisterNodeRange

using jlm::llvm::aa::PointsToGraph::RegisterNodeRange = util::IteratorRange<RegisterNodeIterator>

private

Definition at line 130 of file PointsToGraph.hpp.

Member Enumeration Documentation

◆ NodeKind

enum jlm::llvm::aa::PointsToGraph::NodeKind : uint8_t

strong

Enumerator
RegisterNode
AllocaNode
DeltaNode
ImportNode
LambdaNode
MallocNode
ExternalNode
COUNT

Definition at line 54 of file PointsToGraph.hpp.

Constructor & Destructor Documentation

◆ PointsToGraph() [1/3]

jlm::llvm::aa::PointsToGraph::PointsToGraph ( )

private

Definition at line 17 of file PointsToGraph.cpp.

◆ PointsToGraph() [2/3]

jlm::llvm::aa::PointsToGraph::PointsToGraph ( const PointsToGraph & )

delete

◆ PointsToGraph() [3/3]

jlm::llvm::aa::PointsToGraph::PointsToGraph ( PointsToGraph && )

delete

Member Function Documentation

◆ addNode()

PointsToGraph::NodeIndex jlm::llvm::aa::PointsToGraph::addNode	(	NodeKind	kind,
		bool	externallyAvailable,
		bool	isConstant,
		std::optional< size_t >	memorySize,
		const void *	object
	)

private

Definition at line 474 of file PointsToGraph.cpp.

◆ addNodeForAlloca()

PointsToGraph::NodeIndex jlm::llvm::aa::PointsToGraph::addNodeForAlloca	(	const rvsdg::SimpleNode &	allocaNode,
		bool	externallyAvailable
	)

Creates a new PointsToGraph node mapped to the given allocaNode, which must have the llvm::AllocaOperation.

Parameters

allocaNode	the alloca node. Must not already be mapped to any other node.
externallyAvailable	if the created node should be flagged as externally available.

Returns: the index of the created PointsToGraph node.

Definition at line 70 of file PointsToGraph.cpp.

◆ addNodeForDelta()

PointsToGraph::NodeIndex jlm::llvm::aa::PointsToGraph::addNodeForDelta	(	const rvsdg::DeltaNode &	deltaNode,
		bool	externallyAvailable
	)

Creates a new PointsToGraph node of DeltaNode kind, mapped to the given deltaNode.

Parameters

deltaNode	the node.
externallyAvailable	if the created node should be flagged as externally available.

Returns: the index of the created PointsToGraph node.

Definition at line 101 of file PointsToGraph.cpp.

◆ addNodeForImport()

PointsToGraph::NodeIndex jlm::llvm::aa::PointsToGraph::addNodeForImport	(	const rvsdg::GraphImport &	argument,
		bool	externallyAvailable
	)

Creates a new PointsToGraph node of ImportNode kind, mapped to the given argument.

Parameters

argument	the graph import argument. Must not already be mapped to any other node.
externallyAvailable	if the created node should be flagged as externally available.

Returns: the index of the created PointsToGraph node.

Definition at line 115 of file PointsToGraph.cpp.

◆ addNodeForLambda()

PointsToGraph::NodeIndex jlm::llvm::aa::PointsToGraph::addNodeForLambda	(	const rvsdg::LambdaNode &	lambdaNode,
		bool	externallyAvailable
	)

Creates a new PointsToGraph node of LambdaNode kind, mapped to the given lambdaNode.

Parameters

lambdaNode	the lambda node. Must not already be mapped to any other node.
externallyAvailable	if the created node should be flagged as externally available.

Returns: the index of the created PointsToGraph node.

Definition at line 153 of file PointsToGraph.cpp.

◆ addNodeForMalloc()

PointsToGraph::NodeIndex jlm::llvm::aa::PointsToGraph::addNodeForMalloc	(	const rvsdg::SimpleNode &	mallocNode,
		bool	externallyAvailable
	)

Creates a new PointsToGraph node mapped to the given mallocNode, which must have the llvm::MallocOperation.

Parameters

mallocNode	the malloc node. Must not already be mapped to any other node.
externallyAvailable	if the created node should be flagged as externally available.

Returns: the index of the created PointsToGraph node.

Definition at line 165 of file PointsToGraph.cpp.

◆ addNodeForRegisters()

PointsToGraph::NodeIndex jlm::llvm::aa::PointsToGraph::addNodeForRegisters ( )

Creates a new PointsToGraph node of kind RegisterNode.

See also: mapRegisterToNode to map RVSDG outputs to the PointsToGraph node.

Returns: the index of the new PointsToGraph node.

Definition at line 195 of file PointsToGraph.cpp.

◆ addTarget()

bool jlm::llvm::aa::PointsToGraph::addTarget	(	NodeIndex	source,
		NodeIndex	target
	)

Adds the given target to source's set of targets. If source is marked as targeting all externally available nodes, and the target is marked as externally available, this is a no-op.

Neither the target nor the source can be the external node. That node can only be a target / targeted via flags.

Parameters

source	the source node. Can not be the external node.
target	the target node. Must be a memory node, and not the external node.

Returns: true if the target was added, or any flags were changed

Definition at line 227 of file PointsToGraph.cpp.

◆ allocaNodes()

PointsToGraph::AllocaNodeRange jlm::llvm::aa::PointsToGraph::allocaNodes ( ) const

noexcept

Returns: iterator range of all nodes in the PointsToGraph that are of the AllocaNode kind.

Definition at line 28 of file PointsToGraph.cpp.

◆ create()

static std::unique_ptr<PointsToGraph> jlm::llvm::aa::PointsToGraph::create ( )

inlinestatic

Definition at line 802 of file PointsToGraph.hpp.

◆ deltaNodes()

PointsToGraph::DeltaNodeRange jlm::llvm::aa::PointsToGraph::deltaNodes ( ) const

noexcept

Returns: iterator range of all nodes in the PointsToGraph that are of the DeltaNode kind.

Definition at line 34 of file PointsToGraph.cpp.

◆ dumpDot()

std::string jlm::llvm::aa::PointsToGraph::dumpDot ( const PointsToGraph & pointsToGraph )

static

Shorthand for dumping the given pointsToGraph as a string in the GraphViz dot format.

Returns: the points to graph in dot format.

Definition at line 547 of file PointsToGraph.cpp.

◆ dumpGraph()

void jlm::llvm::aa::PointsToGraph::dumpGraph	(	util::graph::Writer &	graphWriter,
		const PointsToGraph &	pointsToGraph
	)

static

Writes the given pointsToGraph to the given graphWriter. Each node is associated with the rvsdg object(s) it represents through attribute(s).

Definition at line 494 of file PointsToGraph.cpp.

◆ getAllocaForNode()

const rvsdg::SimpleNode& jlm::llvm::aa::PointsToGraph::getAllocaForNode ( NodeIndex index ) const

inline

Gets the rvsdg::SimpleNode mapped to the PointsToGraph node with the given index.

Parameters

index the PointsToGraph node.

Returns: the associated node, which contains a llvm::AllocaOperation.

Exceptions

std::logic_error if the given node is not of the AllocaNode kind.

Definition at line 595 of file PointsToGraph.hpp.

◆ getDeltaForNode()

const rvsdg::DeltaNode& jlm::llvm::aa::PointsToGraph::getDeltaForNode ( NodeIndex index ) const

inline

Gets the rvsdg::DeltaNode mapped to the PointsToGraph node with the given index.

Parameters

index the PointsToGraph node.

Returns: the associated delta node.

Exceptions

std::logic_error if the given node is not of the DeltaNode kind.

Definition at line 610 of file PointsToGraph.hpp.

◆ getExplicitTargets()

const util::HashSet<NodeIndex>& jlm::llvm::aa::PointsToGraph::getExplicitTargets ( NodeIndex index ) const

inline

Gets the set of memory nodes that are targeted explicitly by the node with the given index. When a node X explicitly targets a node Y, it means that the value(s) represented by X may contain a pointer to memory represented by Y. Node Y must be a memory node. Explicit targets is one way of representing pointer-pointee relations, the other being implicit targets using flags.

See also: isExternallyAvailable; isTargetingAllExternallyAvailable

Parameters

index the index of the PointsToGraph node X.

Returns: the set of indices of PointsToGraph nodes targeted by X.

Definition at line 537 of file PointsToGraph.hpp.

◆ getExternallyAvailableNodes()

const std::vector<NodeIndex>& jlm::llvm::aa::PointsToGraph::getExternallyAvailableNodes ( ) const

inlinenoexcept

Returns: the indices of all PointsToGraph nodes that are marked as being externally available. Only memory nodes can have this flag.

Definition at line 563 of file PointsToGraph.hpp.

◆ getExternalMemoryNode()

PointsToGraph::NodeIndex jlm::llvm::aa::PointsToGraph::getExternalMemoryNode ( ) const

noexcept

Returns: the index of the node that represents all memory that is not represented by any other memory node. It is impossible to target this node directly, so it must be targeted through the flag for targeting all external memory. It is also impossible to add explicit targets to this node, so all targets must be added using the flag for marking memory as externally available.

Definition at line 58 of file PointsToGraph.cpp.

◆ getImportForNode()

const rvsdg::GraphImport& jlm::llvm::aa::PointsToGraph::getImportForNode ( NodeIndex index ) const

inline

Gets the rvsdg::GraphImport mapped to the PointsToGraph node with the given index.

Parameters

index the PointsToGraph node.

Returns: the associated graph import argument.

Exceptions

std::logic_error if the given node is not of the ImportNode kind.

Definition at line 625 of file PointsToGraph.hpp.

◆ getLambdaForNode()

const rvsdg::LambdaNode& jlm::llvm::aa::PointsToGraph::getLambdaForNode ( NodeIndex index ) const

inline

Gets the rvsdg::LambdaNode mapped to the PointsToGraph node with the given index.

Parameters

index the PointsToGraph node.

Returns: the associated lambda node.

Exceptions

std::logic_error if the given node is not of the LambdaNode kind.

Definition at line 640 of file PointsToGraph.hpp.

◆ getMallocForNode()

const rvsdg::SimpleNode& jlm::llvm::aa::PointsToGraph::getMallocForNode ( NodeIndex index ) const

inline

Gets the rvsdg::SimpleNode mapped to the PointsToGraph node with the given index.

Parameters

index the PointsToGraph node.

Returns: the associated node, which contains a llvm::MallocOperation.

Exceptions

std::logic_error if the given node is not of the MallocNode kind.

Definition at line 655 of file PointsToGraph.hpp.

◆ getNodeDebugString()

std::string jlm::llvm::aa::PointsToGraph::getNodeDebugString	(	NodeIndex	index,
		char	separator = `' '`
	)		const

Produces a debug string for the given node, containing the index, flags, size, constness and info about the underlying object. Does not include explicit targets.

Parameters

index	the index of the node to create a debug string for
separator	the char to put between parts of the debug string

Returns: the debug string

Definition at line 269 of file PointsToGraph.cpp.

◆ getNodeForAlloca()

NodeIndex jlm::llvm::aa::PointsToGraph::getNodeForAlloca ( const rvsdg::SimpleNode & node ) const

inline

Retrieves the index of the PointsToGraph node mapped to the given rvsdg::SimpleNode.

Parameters

node	the node being looked up, which must contain an AllocaOperation.

Returns: the PointsToGraph node mapped to node, always of AllocaNode kind.

Exceptions

std::out_of_range if the alloca node is not mapped to a PointsToGraph node.

Definition at line 354 of file PointsToGraph.hpp.

◆ getNodeForDelta()

NodeIndex jlm::llvm::aa::PointsToGraph::getNodeForDelta ( const rvsdg::DeltaNode & node ) const

inline

Retrieves the index of the PointsToGraph node mapped to the given rvsdg::DeltaNode.

Parameters

node	the delta node being looked up.

Returns: the PointsToGraph node mapped to node, always of DeltaNode kind.

Exceptions

std::out_of_range if the delta node is not mapped to a PointsToGraph node.

Definition at line 366 of file PointsToGraph.hpp.

◆ getNodeForImport()

NodeIndex jlm::llvm::aa::PointsToGraph::getNodeForImport ( const rvsdg::GraphImport & argument ) const

inline

Retrieves the index of the PointsToGraph node mapped to the given rvsdg::GraphImport.

Parameters

argument the import being looked up.

Returns: the PointsToGraph node mapped to argument, always of ImportNode kind.

Exceptions

std::out_of_range if the argument is not mapped to a PointsToGraph node.

Definition at line 378 of file PointsToGraph.hpp.

◆ getNodeForLambda()

NodeIndex jlm::llvm::aa::PointsToGraph::getNodeForLambda ( const rvsdg::LambdaNode & node ) const

inline

Retrieves the index of the PointsToGraph node mapped to the given rvsdg::LambdaNode.

Parameters

node	the lambda node being looked up.

Returns: the PointsToGraph node mapped to node, always of LambdaNode kind.

Exceptions

std::out_of_range if the lambda node is not mapped to a PointsToGraph node.

Definition at line 390 of file PointsToGraph.hpp.

◆ getNodeForMalloc()

NodeIndex jlm::llvm::aa::PointsToGraph::getNodeForMalloc ( const rvsdg::SimpleNode & node ) const

inline

Retrieves the index of the PointsToGraph node mapped to the given rvsdg::SimpleNode.

Parameters

node	the node being looked up, which must contain a MallocOperation.

Returns: the PointsToGraph node mapped to node, always of MallocNode kind.

Exceptions

std::out_of_range if the malloc node is not mapped to a PointsToGraph node.

Definition at line 402 of file PointsToGraph.hpp.

◆ getNodeForRegister()

NodeIndex jlm::llvm::aa::PointsToGraph::getNodeForRegister ( const rvsdg::Output & output ) const

inline

Retrieves the index of the PointsToGraph node mapped to the given output.

Parameters

output the RVSDG output being looked up.

Returns: the PointsToGraph node mapped to output, always of RegisterNode kind.

Exceptions

std::out_of_range if the output is not mapped to a PointsToGraph node.

Definition at line 414 of file PointsToGraph.hpp.

◆ getNodeKind()

NodeKind jlm::llvm::aa::PointsToGraph::getNodeKind ( NodeIndex index ) const

inline

Gets the NodeKind of the node with the given index.

Parameters

index the index of the node in question.

Returns: the NodeKind of the given node.

Definition at line 439 of file PointsToGraph.hpp.

◆ hasNodeForAlloca()

bool jlm::llvm::aa::PointsToGraph::hasNodeForAlloca ( const rvsdg::SimpleNode & node ) const

inline

Checks whether a PointsToGraph AllocaNode has been created for the given RVSDG SimpleNode. The SimpleNode must correspond to an AllocaOperation.

Parameters

node	the RVSDG node to look up.

Returns: true if an AllocaNode is mapped to this RVSDG node, false otherwise.

Definition at line 286 of file PointsToGraph.hpp.

◆ hasNodeForDelta()

bool jlm::llvm::aa::PointsToGraph::hasNodeForDelta ( const rvsdg::DeltaNode & node ) const

inline

Checks whether a PointsToGraph DeltaNode is mapped to the given rvsdg::DeltaNode.

Parameters

node	the RVSDG delta node to look up.

Returns: true if a DeltaNode is mapped to this node, false otherwise.

Definition at line 297 of file PointsToGraph.hpp.

◆ hasNodeForImport()

bool jlm::llvm::aa::PointsToGraph::hasNodeForImport ( const rvsdg::GraphImport & argument ) const

inline

Checks whether a PointsToGraph ImportNode is mapped to the given rvsdg::GraphImport.

Parameters

argument the RVSDG import to look up.

Returns: true if an ImportNode is mapped to this import, false otherwise.

Definition at line 308 of file PointsToGraph.hpp.

◆ hasNodeForLambda()

bool jlm::llvm::aa::PointsToGraph::hasNodeForLambda ( const rvsdg::LambdaNode & node ) const

inline

Checks whether a PointsToGraph LambdaNode is mapped to the given rvsdg::LambdaNode.

Parameters

node	the RVSDG lambda node to look up.

Returns: true if a LambdaNode is mapped to this node, false otherwise.

Definition at line 319 of file PointsToGraph.hpp.

◆ hasNodeForMalloc()

bool jlm::llvm::aa::PointsToGraph::hasNodeForMalloc ( const rvsdg::SimpleNode & node ) const

inline

Checks whether a PointsToGraph MallocNode is mapped to the given rvsdg::SimpleNode. The simple node must correspond to a MallocOperation.

Parameters

node	the RVSDG node to look up.

Returns: true if a MallocNode is mapped to this node, false otherwise.

Definition at line 331 of file PointsToGraph.hpp.

◆ hasNodeForRegister()

bool jlm::llvm::aa::PointsToGraph::hasNodeForRegister ( const rvsdg::Output & output ) const

inline

Checks whether a PointsToGraph RegisterNode has been created for the given rvsdg::Output.

Parameters

output the RVSDG output to look up.

Returns: true if a RegisterNode is mapped to this output, false otherwise.

Definition at line 342 of file PointsToGraph.hpp.

◆ importNodes()

PointsToGraph::ImportNodeRange jlm::llvm::aa::PointsToGraph::importNodes ( ) const

noexcept

Returns: iterator range of all nodes in the PointsToGraph that are of the ImportNode kind.

Definition at line 40 of file PointsToGraph.cpp.

◆ isExternallyAvailable()

bool jlm::llvm::aa::PointsToGraph::isExternallyAvailable ( NodeIndex index ) const

inline

Checks the the PointsToGraph node with the given index is flagged as externally available. Only memory nodes can have this flag.

Parameters

index the index of the PointsToGraph node.

Returns: true if the node is flagged, false otherwise.

Definition at line 475 of file PointsToGraph.hpp.

◆ isMemoryNode()

bool jlm::llvm::aa::PointsToGraph::isMemoryNode ( NodeIndex index ) const

inline

Checks if the PointsToGraph node with the given index is a memory node. This means all nodes that are not of the RegisterNode kind.

Parameters

index the index of the node in question.

Returns: true if node is a memory node, otherwise false.

Definition at line 463 of file PointsToGraph.hpp.

◆ isNodeConstant()

bool jlm::llvm::aa::PointsToGraph::isNodeConstant ( NodeIndex index ) const

inlinenoexcept

Checks if the memory represented by the given node is representing constant memory. Constant memory means the value stored in the memory never changes during execution.

Parameters

index the index of the PointsToGraph node

Returns: true if the memory represented by the node is constant

Definition at line 502 of file PointsToGraph.hpp.

◆ isRegisterNode()

bool jlm::llvm::aa::PointsToGraph::isRegisterNode ( NodeIndex index ) const

inline

Checks if the PointsToGraph node with the given index is of the RegisterNode kind.

Parameters

index the index of the node in question.

Returns: true if node is a register node, otherwise false.

Definition at line 451 of file PointsToGraph.hpp.

◆ isSupergraphOf()

bool jlm::llvm::aa::PointsToGraph::isSupergraphOf ( const PointsToGraph & subgraph ) const

Checks if this PointsToGraph is a supergraph of subgraph. Every node in the subgraph needs to have corresponding nodes in the supergraph. Any flags present in the subgraph must also be present in the supergraph. All pointer-pointee relations in the subgraph must be represented in the supergraph, either as explicit or implicit targets.

Parameters

subgraph the graph to compare against

Returns: true if this graph is a supergraph of the given subgraph, false otherwise

Definition at line 324 of file PointsToGraph.cpp.

◆ isTargeting()

bool jlm::llvm::aa::PointsToGraph::isTargeting	(	NodeIndex	source,
		NodeIndex	target
	)		const

inline

Checks if the node with index source targets the node with index target, either explicitly or implicitly.

Parameters

source	the pointing node.
target	the node that is possibly a pointee.

Returns: true if source targets target, otherwise false.

Definition at line 551 of file PointsToGraph.hpp.

◆ isTargetingAllExternallyAvailable()

bool jlm::llvm::aa::PointsToGraph::isTargetingAllExternallyAvailable ( NodeIndex index ) const

inline

Checks if the PointsToGraph node with the given index is flagged as targeting all externally available memory. If it is, it implicitly targets every PointsToGraph node flagged as externally available.

Parameters

index the index of the PointsToGraph node.

Returns: true if the node is flagged, false otherwise.

Definition at line 489 of file PointsToGraph.hpp.

◆ lambdaNodes()

PointsToGraph::LambdaNodeRange jlm::llvm::aa::PointsToGraph::lambdaNodes ( ) const

noexcept

Returns: iterator range of all nodes in the PointsToGraph that are of the LambdaNode kind.

Definition at line 46 of file PointsToGraph.cpp.

◆ mallocNodes()

PointsToGraph::MallocNodeRange jlm::llvm::aa::PointsToGraph::mallocNodes ( ) const

noexcept

Returns: iterator range of all nodes in the PointsToGraph that are of the MallocNode kind.

Definition at line 52 of file PointsToGraph.cpp.

◆ mapRegisterToNode()

void jlm::llvm::aa::PointsToGraph::mapRegisterToNode	(	const rvsdg::Output &	output,
		NodeIndex	nodeIndex
	)

Maps the given output to the PointsToGraph node with the given nodeIndex. The PointsToGraph node must be of the RegisterNode kind.

Parameters

output	the RVSDG output that is mapped
nodeIndex	the index of the PointsToGraph node it is mapped to

Definition at line 205 of file PointsToGraph.cpp.

◆ markAsTargetsAllExternallyAvailable()

void jlm::llvm::aa::PointsToGraph::markAsTargetsAllExternallyAvailable ( NodeIndex index )

Marks the given node as targeting every node that is externally available. Note that this method will not go over other targets and remove doubled up pointees.

Parameters

index the index of the PointsToGraph node that should be marked

Definition at line 216 of file PointsToGraph.cpp.

◆ numAllocaNodes()

size_t jlm::llvm::aa::PointsToGraph::numAllocaNodes ( ) const

inlinenoexcept

Returns: the number of nodes in the PointsToGraph that are of the AllocaNode kind.

Definition at line 198 of file PointsToGraph.hpp.

◆ numDeltaNodes()

size_t jlm::llvm::aa::PointsToGraph::numDeltaNodes ( ) const

inlinenoexcept

Returns: the number of nodes in the PointsToGraph that are of the DeltaNode kind.

Definition at line 207 of file PointsToGraph.hpp.

◆ numEdges()

std::pair< size_t, size_t > jlm::llvm::aa::PointsToGraph::numEdges ( ) const

noexcept

Gets the total number of edges in the PointsToGraph.

This can be counted in two different ways:

Only explicit edges
Both explicit and implicit edges (only counting doubled up pointees once)

In both cases, register nodes are only counted once, even if multiple registers map to them.

Returns: a pair (number of explicit edges, total number of edges)

Definition at line 246 of file PointsToGraph.cpp.

◆ numExternallyAvailableNodes()

size_t jlm::llvm::aa::PointsToGraph::numExternallyAvailableNodes ( ) const

inlinenoexcept

Returns: the number of nodes in the PointsToGraph that are flagged as being externally available. Only memory nodes can have this flag.

Definition at line 573 of file PointsToGraph.hpp.

◆ numImportNodes()

size_t jlm::llvm::aa::PointsToGraph::numImportNodes ( ) const

inlinenoexcept

Returns: the number of nodes in the PointsToGraph that are of the ImportNode kind.

Definition at line 216 of file PointsToGraph.hpp.

◆ numLambdaNodes()

size_t jlm::llvm::aa::PointsToGraph::numLambdaNodes ( ) const

inlinenoexcept

Returns: the number of nodes in the PointsToGraph that are of the LambdaNode kind.

Definition at line 225 of file PointsToGraph.hpp.

◆ numMallocNodes()

size_t jlm::llvm::aa::PointsToGraph::numMallocNodes ( ) const

inlinenoexcept

Returns: the number of nodes in the PointsToGraph that are of the MallocNode kind.

Definition at line 234 of file PointsToGraph.hpp.

◆ numMappedRegisters()

size_t jlm::llvm::aa::PointsToGraph::numMappedRegisters ( ) const

inlinenoexcept

Returns: the total number of rvsdg::Output's mapped to nodes in the PointsToGraph.

Definition at line 252 of file PointsToGraph.hpp.

◆ numMemoryNodes()

size_t jlm::llvm::aa::PointsToGraph::numMemoryNodes ( ) const

inlinenoexcept

Returns: the number of nodes in the PointsToGraph that are classified as memory nodes, i.e., all nodes that are not register nodes.

Definition at line 262 of file PointsToGraph.hpp.

◆ numNodes()

size_t jlm::llvm::aa::PointsToGraph::numNodes ( ) const

inlinenoexcept

Returns: the total number of nodes in the PointsToGraph.

Definition at line 272 of file PointsToGraph.hpp.

◆ numNodesTargetingAllExternallyAvailable()

size_t jlm::llvm::aa::PointsToGraph::numNodesTargetingAllExternallyAvailable ( ) const

inlinenoexcept

Returns: the number of nodes in the PointsToGraph that are flagged as possibly pointing to all memory nodes that are externally available.

Definition at line 583 of file PointsToGraph.hpp.

◆ numRegisterNodes()

size_t jlm::llvm::aa::PointsToGraph::numRegisterNodes ( ) const

inlinenoexcept

Returns: the number of nodes in the PointsToGraph that are of the RegisterNode kind.

Definition at line 243 of file PointsToGraph.hpp.

◆ operator=() [1/2]

PointsToGraph& jlm::llvm::aa::PointsToGraph::operator= ( const PointsToGraph & )

delete

◆ operator=() [2/2]

PointsToGraph& jlm::llvm::aa::PointsToGraph::operator= ( PointsToGraph && )

delete

◆ registerNodes()

PointsToGraph::RegisterNodeRange jlm::llvm::aa::PointsToGraph::registerNodes ( ) const

noexcept

Returns: iterator range of all nodes in the PointsToGraph that are of the RegisterNode kind.

Definition at line 64 of file PointsToGraph.cpp.

◆ tryGetNodeForRegister()

std::optional<NodeIndex> jlm::llvm::aa::PointsToGraph::tryGetNodeForRegister ( const rvsdg::Output & output ) const

inlinenoexcept

Retrieves the index of the PointsToGraph node mapped to the given output, if such a node exists. Otherwise nullopt is returned.

See also: getNodeForRegister()

Definition at line 425 of file PointsToGraph.hpp.

◆ tryGetNodeSize()

std::optional<size_t> jlm::llvm::aa::PointsToGraph::tryGetNodeSize ( NodeIndex index ) const

inlinenoexcept

Gets the size of the memory location represented by the node with the given index. The node can also represent many locations, as long as they all have the same size. If the memory locations have varying or unknown size, nullopt is returned.

Parameters

index the index of the PointsToGraph node

Returns: the size of the memory location(s) in bytes, or nullopt if unknown.

Definition at line 516 of file PointsToGraph.hpp.

Member Data Documentation

◆ allocaMap_

AllocaNodeMap jlm::llvm::aa::PointsToGraph::allocaMap_

private

Definition at line 824 of file PointsToGraph.hpp.

◆ deltaMap_

DeltaNodeMap jlm::llvm::aa::PointsToGraph::deltaMap_

private

Definition at line 825 of file PointsToGraph.hpp.

◆ externallyAvailableNodes_

std::vector<NodeIndex> jlm::llvm::aa::PointsToGraph::externallyAvailableNodes_

private

Definition at line 837 of file PointsToGraph.hpp.

◆ externalMemoryNode

constexpr NodeIndex jlm::llvm::aa::PointsToGraph::externalMemoryNode = 0

staticconstexpr

Definition at line 52 of file PointsToGraph.hpp.

◆ importMap_

ImportNodeMap jlm::llvm::aa::PointsToGraph::importMap_

private

Definition at line 826 of file PointsToGraph.hpp.

◆ lambdaMap_

LambdaNodeMap jlm::llvm::aa::PointsToGraph::lambdaMap_

private

Definition at line 827 of file PointsToGraph.hpp.

◆ mallocMap_

MallocNodeMap jlm::llvm::aa::PointsToGraph::mallocMap_

private

Definition at line 828 of file PointsToGraph.hpp.

◆ nodeData_

std::vector<NodeData> jlm::llvm::aa::PointsToGraph::nodeData_

private

Definition at line 817 of file PointsToGraph.hpp.

◆ nodeExplicitTargets_

std::vector<util::HashSet<NodeIndex> > jlm::llvm::aa::PointsToGraph::nodeExplicitTargets_

private

Definition at line 819 of file PointsToGraph.hpp.

◆ nodeObjects_

std::vector<const void *> jlm::llvm::aa::PointsToGraph::nodeObjects_

private

Definition at line 821 of file PointsToGraph.hpp.

◆ numNodesTargetingAllExternallyAvailable_

size_t jlm::llvm::aa::PointsToGraph::numNodesTargetingAllExternallyAvailable_ = 0

private

Definition at line 839 of file PointsToGraph.hpp.

◆ registerMap_

RegisterNodeMap jlm::llvm::aa::PointsToGraph::registerMap_

private

Definition at line 832 of file PointsToGraph.hpp.

◆ registerNodes_

std::vector<NodeIndex> jlm::llvm::aa::PointsToGraph::registerNodes_

private

Definition at line 835 of file PointsToGraph.hpp.

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

jlm/llvm/opt/alias-analyses/PointsToGraph.hpp
jlm/llvm/opt/alias-analyses/PointsToGraph.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ AllocaNodeIterator

◆ AllocaNodeMap

◆ AllocaNodeRange

◆ DeltaNodeIterator

◆ DeltaNodeMap

◆ DeltaNodeRange

◆ ExternallyAvailableIterator

◆ ExternallyAvailableRange

◆ ImportNodeIterator

◆ ImportNodeMap

◆ ImportNodeRange

◆ LambdaNodeIterator

◆ LambdaNodeMap

◆ LambdaNodeRange

◆ MallocNodeIterator

◆ MallocNodeMap

◆ MallocNodeRange

◆ NodeIndex

◆ RegisterNodeIterator

◆ RegisterNodeMap

◆ RegisterNodeRange

Member Enumeration Documentation

◆ NodeKind

Constructor & Destructor Documentation

◆ PointsToGraph() [1/3]

◆ PointsToGraph() [2/3]

◆ PointsToGraph() [3/3]

Member Function Documentation

◆ addNode()

◆ addNodeForAlloca()

◆ addNodeForDelta()

◆ addNodeForImport()

◆ addNodeForLambda()

◆ addNodeForMalloc()

◆ addNodeForRegisters()

◆ addTarget()

◆ allocaNodes()

◆ create()

◆ deltaNodes()

◆ dumpDot()

◆ dumpGraph()

◆ getAllocaForNode()

◆ getDeltaForNode()

◆ getExplicitTargets()

◆ getExternallyAvailableNodes()

◆ getExternalMemoryNode()

◆ getImportForNode()

◆ getLambdaForNode()

◆ getMallocForNode()

◆ getNodeDebugString()

◆ getNodeForAlloca()

◆ getNodeForDelta()

◆ getNodeForImport()

◆ getNodeForLambda()

◆ getNodeForMalloc()

◆ getNodeForRegister()

◆ getNodeKind()

◆ hasNodeForAlloca()

◆ hasNodeForDelta()

◆ hasNodeForImport()

◆ hasNodeForLambda()

◆ hasNodeForMalloc()

◆ hasNodeForRegister()

◆ importNodes()

◆ isExternallyAvailable()

◆ isMemoryNode()

◆ isNodeConstant()

◆ isRegisterNode()

◆ isSupergraphOf()

◆ isTargeting()