#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

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 ()

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_

NodeIndex	externalMemoryNode_

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 44 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 109 of file PointsToGraph.hpp.

◆ AllocaNodeMap

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

private

Definition at line 102 of file PointsToGraph.hpp.

◆ AllocaNodeRange

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

private

Definition at line 110 of file PointsToGraph.hpp.

◆ DeltaNodeIterator

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

private

Definition at line 112 of file PointsToGraph.hpp.

◆ DeltaNodeMap

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

private

Definition at line 103 of file PointsToGraph.hpp.

◆ DeltaNodeRange

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

private

Definition at line 113 of file PointsToGraph.hpp.

◆ ExternallyAvailableIterator

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

private

Definition at line 127 of file PointsToGraph.hpp.

◆ ExternallyAvailableRange

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

private

Definition at line 128 of file PointsToGraph.hpp.

◆ ImportNodeIterator

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

private

Definition at line 115 of file PointsToGraph.hpp.

◆ ImportNodeMap

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

private

Definition at line 104 of file PointsToGraph.hpp.

◆ ImportNodeRange

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

private

Definition at line 116 of file PointsToGraph.hpp.

◆ LambdaNodeIterator

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

private

Definition at line 118 of file PointsToGraph.hpp.

◆ LambdaNodeMap

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

private

Definition at line 105 of file PointsToGraph.hpp.

◆ LambdaNodeRange

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

private

Definition at line 119 of file PointsToGraph.hpp.

◆ MallocNodeIterator

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

private

Definition at line 121 of file PointsToGraph.hpp.

◆ MallocNodeMap

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

private

Definition at line 106 of file PointsToGraph.hpp.

◆ MallocNodeRange

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

private

Definition at line 122 of file PointsToGraph.hpp.

◆ NodeIndex

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

Definition at line 47 of file PointsToGraph.hpp.

◆ RegisterNodeIterator

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

private

Definition at line 124 of file PointsToGraph.hpp.

◆ RegisterNodeMap

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

private

Definition at line 107 of file PointsToGraph.hpp.

◆ RegisterNodeRange

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

private

Definition at line 125 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 49 of file PointsToGraph.hpp.

Constructor & Destructor Documentation

◆ PointsToGraph() [1/3]

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

private

Definition at line 16 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 471 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 67 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 98 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 112 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 150 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 162 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 192 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 224 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 25 of file PointsToGraph.cpp.

◆ create()

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

inlinestatic

Definition at line 783 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 31 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 544 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 491 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 576 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 591 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 518 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 544 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 55 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 606 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 621 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 636 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 266 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 349 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 361 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 373 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 385 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 397 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 409 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 420 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 281 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 292 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 303 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 314 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 326 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 337 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 37 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 456 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 444 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 483 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 432 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 321 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 532 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 470 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 43 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 49 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 202 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 213 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 193 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 202 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 243 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 554 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 211 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 220 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 229 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 247 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 257 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 267 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 564 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 238 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 61 of file PointsToGraph.cpp.

◆ 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 497 of file PointsToGraph.hpp.

Member Data Documentation

◆ allocaMap_

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

private

Definition at line 805 of file PointsToGraph.hpp.

◆ deltaMap_

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

private

Definition at line 806 of file PointsToGraph.hpp.

◆ externallyAvailableNodes_

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

private

Definition at line 821 of file PointsToGraph.hpp.

◆ externalMemoryNode_

NodeIndex jlm::llvm::aa::PointsToGraph::externalMemoryNode_

private

Definition at line 812 of file PointsToGraph.hpp.

◆ importMap_

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

private

Definition at line 807 of file PointsToGraph.hpp.

◆ lambdaMap_

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

private

Definition at line 808 of file PointsToGraph.hpp.

◆ mallocMap_

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

private

Definition at line 809 of file PointsToGraph.hpp.

◆ nodeData_

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

private

Definition at line 798 of file PointsToGraph.hpp.

◆ nodeExplicitTargets_

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

private

Definition at line 800 of file PointsToGraph.hpp.

◆ nodeObjects_

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

private

Definition at line 802 of file PointsToGraph.hpp.

◆ numNodesTargetingAllExternallyAvailable_

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

private

Definition at line 823 of file PointsToGraph.hpp.

◆ registerMap_

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

private

Definition at line 816 of file PointsToGraph.hpp.

◆ registerNodes_

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

private

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

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()

◆ isTargetingAllExternallyAvailable()