Region-aware mod/ref summarizer. More...

#include <RegionAwareModRefSummarizer.hpp>

Inheritance diagram for jlm::llvm::aa::RegionAwareModRefSummarizer:

Collaboration diagram for jlm::llvm::aa::RegionAwareModRefSummarizer:

Classes
struct	Context

class	Statistics
	Region-aware mod/ref summarizer statistics. More...

Public Member Functions
	~RegionAwareModRefSummarizer () noexcept override

	RegionAwareModRefSummarizer ()

	RegionAwareModRefSummarizer (const RegionAwareModRefSummarizer &)=delete

RegionAwareModRefSummarizer &	operator= (const RegionAwareModRefSummarizer &)=delete

std::unique_ptr< ModRefSummary >	SummarizeModRefs (const rvsdg::RvsdgModule &rvsdgModule, const PointsToGraph &pointsToGraph, util::StatisticsCollector &statisticsCollector) override

Public Member Functions inherited from jlm::llvm::aa::ModRefSummarizer
virtual	~ModRefSummarizer () noexcept=default

Static Public Member Functions
static std::unique_ptr< ModRefSummary >	Create (const rvsdg::RvsdgModule &rvsdgModule, const PointsToGraph &pointsToGraph, util::StatisticsCollector &statisticsCollector)

static std::unique_ptr< ModRefSummary >	Create (const rvsdg::RvsdgModule &rvsdgModule, const PointsToGraph &pointsToGraph)

Private Member Functions
void	createCallGraph (const rvsdg::RvsdgModule &rvsdgModule)

void	FindAllocasDeadInSccs ()

util::HashSet< PointsToGraph::NodeIndex >	GetSimpleAllocasReachableFromRegionArguments (const rvsdg::Region &region)

bool	IsRecursionPossible (const rvsdg::LambdaNode &lambda) const

size_t	CreateNonReentrantAllocaSets ()

void	CreateExternalModRefSet ()

void	AddModRefSimpleConstraint (ModRefSetIndex from, ModRefSetIndex to)

void	AddModRefSetBlocklist (ModRefSetIndex index, const util::HashSet< PointsToGraph::NodeIndex > &blocklist)

void	AnnotateFunction (const rvsdg::LambdaNode &lambda)

ModRefSetIndex	AnnotateRegion (const rvsdg::Region &region, const rvsdg::LambdaNode &lambda)

ModRefSetIndex	AnnotateStructuralNode (const rvsdg::StructuralNode &structuralNode, const rvsdg::LambdaNode &lambda)

std::optional< ModRefSetIndex >	AnnotateSimpleNode (const rvsdg::SimpleNode &simpleNode, const rvsdg::LambdaNode &lambda)

void	AddPointerOriginTargets (ModRefSetIndex modRefSetIndex, const rvsdg::Output &origin, std::optional< size_t > minTargetSize, const rvsdg::LambdaNode &lambda)

ModRefSetIndex	AnnotateLoad (const rvsdg::SimpleNode &loadNode, const rvsdg::LambdaNode &lambda)

ModRefSetIndex	AnnotateStore (const rvsdg::SimpleNode &storeNode, const rvsdg::LambdaNode &lambda)

ModRefSetIndex	AnnotateAlloca (const rvsdg::SimpleNode &allocaNode)

ModRefSetIndex	AnnotateMalloc (const rvsdg::SimpleNode &mallocNode)

ModRefSetIndex	AnnotateFree (const rvsdg::SimpleNode &freeNode, const rvsdg::LambdaNode &lambda)

ModRefSetIndex	AnnotateMemcpy (const rvsdg::SimpleNode &memcpyNode, const rvsdg::LambdaNode &lambda)

ModRefSetIndex	AnnotateMemset (const rvsdg::SimpleNode &memsetNode, const rvsdg::LambdaNode &lambda)

ModRefSetIndex	AnnotateCall (const rvsdg::SimpleNode &callNode, const rvsdg::LambdaNode &lambda)

void	SolveModRefSetConstraintGraph ()

bool	VerifyBlocklists () const

void	doExternalCompression ()

void	compressExternalInFunction (const rvsdg::LambdaNode &lambda)

void	findAllModRefSets (const rvsdg::Node &node, util::HashSet< ModRefSetIndex > &modRefSets)

Static Private Member Functions
static util::HashSet< PointsToGraph::NodeIndex >	CreateSimpleAllocaSet (const PointsToGraph &pointsToGraph)

static std::string	CallGraphSCCsToString (const RegionAwareModRefSummarizer &summarizer)

static std::string	ToRegionTree (const rvsdg::Graph &rvsdg, const RegionAwareModRefSummary &modRefSummary)

Private Attributes
std::unique_ptr< RegionAwareModRefSummary >	ModRefSummary_

std::unique_ptr< Context >	Context_

Detailed Description

Region-aware mod/ref summarizer.

The key idea of the region-aware memory mod/ref summarizer is to only route memory locations into structural nodes if the memory is actually used within its regions. This ensures that no superfluous states will be routed through structural nodes and renders them independent if they do not reference the same memory location. The region-aware analysis proceeds as follows:

Call Graph Creation: creates a call graph by looking at all call operations. This graph includes calls to external functions, and calls from external functions. Each function is assigned to a strongly connected component.
Find allocas that are dead in each SCC: For each SCC in the call graph, only allocas defined within the SCC, or within one of its predecessors, can be live. All other allocas are placed in the DeadAllocasInScc lists.
Simple Alloca Set Creation: An alloca is "simple" if its address is never stored to any memory location, except for other simple allocas. The PointsToGraph is used to determine which allocas are simple.
Create sets of non-reentrant allocas for each region. The requirements are:
- the alloca must be simple
- the alloca must not be reachable from any of the region's arguments, when following points-to edges in the PointsToGraph.
Mod/Ref Graph Building: Creates a graph containing nodes for loads, stores, calls, regions and functions. Each node has a Mod/Ref set, and edges propagate info. Special edges are used between function body region -> function, which filter away all simple allocas defined in the function that are not recursive.
Mod/Ref Graph Solving: Mod/Ref sets are propagated along edges in the graph
Mod/Ref set compaction: Within each function, memory nodes that always appear along with the external node are removed. External can represent it instead.

See also: ModRefSummarizer; MemoryStateEncoder

Definition at line 58 of file RegionAwareModRefSummarizer.hpp.

Constructor & Destructor Documentation

◆ ~RegionAwareModRefSummarizer()

jlm::llvm::aa::RegionAwareModRefSummarizer::~RegionAwareModRefSummarizer ( )

overridedefaultnoexcept

◆ RegionAwareModRefSummarizer() [1/2]

jlm::llvm::aa::RegionAwareModRefSummarizer::RegionAwareModRefSummarizer ( )

default

◆ RegionAwareModRefSummarizer() [2/2]

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

delete

Member Function Documentation

◆ AddModRefSetBlocklist()

void jlm::llvm::aa::RegionAwareModRefSummarizer::AddModRefSetBlocklist	(	ModRefSetIndex	index,
		const util::HashSet< PointsToGraph::NodeIndex > &	blocklist
	)

private

Defines a set of memory nodes to be blocked from the ModRefSet with the given index. A ModRefSet can have at most one such blocklist. The reference to the blocklist must stay valid until solving is finished.

Note: The blocklist only prevents propagation during solving, so the user must avoid adding blocked memory nodes manually.

See also: VerifyBlocklists to check that no blocked memory nodes have been added

Definition at line 994 of file RegionAwareModRefSummarizer.cpp.

◆ AddModRefSimpleConstraint()

void jlm::llvm::aa::RegionAwareModRefSummarizer::AddModRefSimpleConstraint	(	ModRefSetIndex	from,
		ModRefSetIndex	to
	)

private

Adds the fact that everything in the ModRefSet from should also be included in the ModRefSet to.

Definition at line 986 of file RegionAwareModRefSummarizer.cpp.

◆ AddPointerOriginTargets()

void jlm::llvm::aa::RegionAwareModRefSummarizer::AddPointerOriginTargets	(	ModRefSetIndex	modRefSetIndex,
		const rvsdg::Output &	origin,
		std::optional< size_t >	minTargetSize,
		const rvsdg::LambdaNode &	lambda
	)

private

Helper function for filling ModRefSets based on the pointer being operated on

Parameters

modRefSetIndex	the index of the ModRefSet representing some memory operation
origin	the output producing the pointer value being operated on
minTargetSize	an optional size requirement for targeted memory locations
lambda	the function the operation is happening in

Definition at line 1131 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateAlloca()

ModRefSetIndex jlm::llvm::aa::RegionAwareModRefSummarizer::AnnotateAlloca ( const rvsdg::SimpleNode & allocaNode )

private

Definition at line 1202 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateCall()

ModRefSetIndex jlm::llvm::aa::RegionAwareModRefSummarizer::AnnotateCall	(	const rvsdg::SimpleNode &	callNode,
		const rvsdg::LambdaNode &	lambda
	)

private

Definition at line 1268 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateFree()

ModRefSetIndex jlm::llvm::aa::RegionAwareModRefSummarizer::AnnotateFree	(	const rvsdg::SimpleNode &	freeNode,
		const rvsdg::LambdaNode &	lambda
	)

private

Definition at line 1220 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateFunction()

void jlm::llvm::aa::RegionAwareModRefSummarizer::AnnotateFunction ( const rvsdg::LambdaNode & lambda )

private

Creates ModRefSets for regions and nodes within the function. The flow of MemoryNodes between sets is modeled by adding edges to the constraint graph.

Definition at line 1003 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateLoad()

ModRefSetIndex jlm::llvm::aa::RegionAwareModRefSummarizer::AnnotateLoad	(	const rvsdg::SimpleNode &	loadNode,
		const rvsdg::LambdaNode &	lambda
	)

private

Definition at line 1174 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateMalloc()

ModRefSetIndex jlm::llvm::aa::RegionAwareModRefSummarizer::AnnotateMalloc ( const rvsdg::SimpleNode & mallocNode )

private

Definition at line 1211 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateMemcpy()

ModRefSetIndex jlm::llvm::aa::RegionAwareModRefSummarizer::AnnotateMemcpy	(	const rvsdg::SimpleNode &	memcpyNode,
		const rvsdg::LambdaNode &	lambda
	)

private

Definition at line 1235 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateMemset()

ModRefSetIndex jlm::llvm::aa::RegionAwareModRefSummarizer::AnnotateMemset	(	const rvsdg::SimpleNode &	memsetNode,
		const rvsdg::LambdaNode &	lambda
	)

private

Definition at line 1252 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateRegion()

ModRefSetIndex jlm::llvm::aa::RegionAwareModRefSummarizer::AnnotateRegion	(	const rvsdg::Region &	region,
		const rvsdg::LambdaNode &	lambda
	)

private

Recursive call used to create ModRefSets for the given region, its nodes and its sub-regions.

Parameters

region	the region to create ModRefSets for.
lambda	the function this region belongs to

Definition at line 1029 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateSimpleNode()

std::optional< ModRefSetIndex > jlm::llvm::aa::RegionAwareModRefSummarizer::AnnotateSimpleNode	(	const rvsdg::SimpleNode &	simpleNode,
		const rvsdg::LambdaNode &	lambda
	)

private

Definition at line 1079 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateStore()

ModRefSetIndex jlm::llvm::aa::RegionAwareModRefSummarizer::AnnotateStore	(	const rvsdg::SimpleNode &	storeNode,
		const rvsdg::LambdaNode &	lambda
	)

private

Definition at line 1188 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateStructuralNode()

ModRefSetIndex jlm::llvm::aa::RegionAwareModRefSummarizer::AnnotateStructuralNode	(	const rvsdg::StructuralNode &	structuralNode,
		const rvsdg::LambdaNode &	lambda
	)

private

Definition at line 1063 of file RegionAwareModRefSummarizer.cpp.

◆ CallGraphSCCsToString()

std::string jlm::llvm::aa::RegionAwareModRefSummarizer::CallGraphSCCsToString ( const RegionAwareModRefSummarizer & summarizer )

staticprivate

Helper function for debugging, listing out all functions, grouped by call graph SCC.

Definition at line 1460 of file RegionAwareModRefSummarizer.cpp.

◆ compressExternalInFunction()

void jlm::llvm::aa::RegionAwareModRefSummarizer::compressExternalInFunction ( const rvsdg::LambdaNode & lambda )

private

Performs external compaction in the given function.

Definition at line 1387 of file RegionAwareModRefSummarizer.cpp.

◆ Create() [1/2]

std::unique_ptr< ModRefSummary > jlm::llvm::aa::RegionAwareModRefSummarizer::Create	(	const rvsdg::RvsdgModule &	rvsdgModule,
		const PointsToGraph &	pointsToGraph
	)

static

Creates a RegionAwareModRefSummarizer and calls the SummarizeModRefs() method.

Parameters

rvsdgModule	The RVSDG module for which the ModRefSummary should be computed.
pointsToGraph	The PointsToGraph corresponding to the RVSDG module.

Returns: A new instance of ModRefSummary.

Definition at line 1547 of file RegionAwareModRefSummarizer.cpp.

◆ Create() [2/2]

std::unique_ptr< ModRefSummary > jlm::llvm::aa::RegionAwareModRefSummarizer::Create	(	const rvsdg::RvsdgModule &	rvsdgModule,
		const PointsToGraph &	pointsToGraph,
		util::StatisticsCollector &	statisticsCollector
	)

static

Creates a RegionAwareModRefSummarizer and calls the SummarizeModRefs() method.

Parameters

rvsdgModule	The RVSDG module for which the ModRefSummary should be computed.
pointsToGraph	The PointsToGraph corresponding to the RVSDG module.
statisticsCollector	The statistics collector for collecting pass statistics.

Returns: A new instance of ModRefSummary.

Definition at line 1537 of file RegionAwareModRefSummarizer.cpp.

◆ createCallGraph()

void jlm::llvm::aa::RegionAwareModRefSummarizer::createCallGraph ( const rvsdg::RvsdgModule & rvsdgModule )

private

Creates a call graph including all functions in the module, and groups all functions into SCCs. The resulting SCCs and topological order will be stored in the Context_ field.

Parameters

rvsdgModule the module for which a mod/ref summary is computed.

Definition at line 632 of file RegionAwareModRefSummarizer.cpp.

◆ CreateExternalModRefSet()

void jlm::llvm::aa::RegionAwareModRefSummarizer::CreateExternalModRefSet ( )

private

Creates one ModRefSet which is responsible for representing all reads and writes that may happen in external functions.

Definition at line 960 of file RegionAwareModRefSummarizer.cpp.

◆ CreateNonReentrantAllocaSets()

size_t jlm::llvm::aa::RegionAwareModRefSummarizer::CreateNonReentrantAllocaSets ( )

private

Creates subsets of the allocas defined in each region in the program, containing only the allocas that are determined to be non-reentrant. The requirements are:

The alloca is simple, i.e., not reachable from memory nodes in the PointsToGraph.
It is not possible to reach the alloca from any of the region's arguments, by following edges in the PointsToGraph.
Returns
the total number of non-reentrant allocas in the program

Definition at line 902 of file RegionAwareModRefSummarizer.cpp.

◆ CreateSimpleAllocaSet()

util::HashSet< PointsToGraph::NodeIndex > jlm::llvm::aa::RegionAwareModRefSummarizer::CreateSimpleAllocaSet ( const PointsToGraph & pointsToGraph )

staticprivate

Creates a set containing all simple Allocas is the PointsToGraph. An Alloca is simple if it is only reachable from other simple Allocas, or from RegisterNodes, in the PointsToGraph.

Definition at line 818 of file RegionAwareModRefSummarizer.cpp.

◆ doExternalCompression()

void jlm::llvm::aa::RegionAwareModRefSummarizer::doExternalCompression ( )

private

Goes through all ModRefSets in all functions, and keeps track of memory nodes that always appear alongside the external memory node. These memory nodes are compressible, and can be removed from all ModRefSets in the function.

Definition at line 1375 of file RegionAwareModRefSummarizer.cpp.

◆ findAllModRefSets()

void jlm::llvm::aa::RegionAwareModRefSummarizer::findAllModRefSets	(	const rvsdg::Node &	node,
		util::HashSet< ModRefSetIndex > &	modRefSets
	)

private

Helper function for recursively finding all ModRefSets in the given node.

Parameters

node	the node to traverse, including any subregions.
modRefSets	the hash set in which all found ModRefSets are placed.

Definition at line 1435 of file RegionAwareModRefSummarizer.cpp.

◆ FindAllocasDeadInSccs()

void jlm::llvm::aa::RegionAwareModRefSummarizer::FindAllocasDeadInSccs ( )

private

For each SCC in the call graph, determines which allocas can be known to not be live when a function from the SCC is at the top of the call stack.

Definition at line 774 of file RegionAwareModRefSummarizer.cpp.

◆ GetSimpleAllocasReachableFromRegionArguments()

util::HashSet< PointsToGraph::NodeIndex > jlm::llvm::aa::RegionAwareModRefSummarizer::GetSimpleAllocasReachableFromRegionArguments ( const rvsdg::Region & region )

private

Gets the set of simple alloca nodes that it is possible to reach from region's arguments. Reachability is defined in terms of the PointsToGraph. A simple alloca is by definition only reachable from register nodes and other simple alloca nodes, so other types of memory nodes in the points-to graph can be ignored.

Parameters

region the region whose arguments are checked

Returns: the set of simple allocas reachable from region arguments

Definition at line 858 of file RegionAwareModRefSummarizer.cpp.

◆ IsRecursionPossible()

bool jlm::llvm::aa::RegionAwareModRefSummarizer::IsRecursionPossible ( const rvsdg::LambdaNode & lambda ) const

private

Uses the call graph to determine if the given function can ever be involved in a recursive chain of function calls.

Parameters

lambda the function in question.

Returns: true if it is possible for lambda to be involved in recursion, false otherwise

Definition at line 895 of file RegionAwareModRefSummarizer.cpp.

◆ operator=()

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

delete

◆ SolveModRefSetConstraintGraph()

void jlm::llvm::aa::RegionAwareModRefSummarizer::SolveModRefSetConstraintGraph ( )

private

Uses the simple and complex constraints to propagate MemoryNodes between ModRefSets until all constraints are satisfied.

Definition at line 1316 of file RegionAwareModRefSummarizer.cpp.

◆ SummarizeModRefs()

std::unique_ptr< ModRefSummary > jlm::llvm::aa::RegionAwareModRefSummarizer::SummarizeModRefs	(	const rvsdg::RvsdgModule &	rvsdgModule,
		const PointsToGraph &	pointsToGraph,
		util::StatisticsCollector &	statisticsCollector
	)

overridevirtual

Computes the memory nodes that are required at the entry and exit of a region, or at the entry/exit of a call node.

Parameters

rvsdgModule	The RVSDG module for which a ModRefSummary should be computed.
pointsToGraph	The points-to graph corresponding to `rvsdgModule`.
statisticsCollector	The statistics collector for collecting pass statistics.

Returns: An instance of ModRefSummary.

Implements jlm::llvm::aa::ModRefSummarizer.

Definition at line 525 of file RegionAwareModRefSummarizer.cpp.

◆ ToRegionTree()

std::string jlm::llvm::aa::RegionAwareModRefSummarizer::ToRegionTree	(	const rvsdg::Graph &	rvsdg,
		const RegionAwareModRefSummary &	modRefSummary
	)

staticprivate

Converts rvsdg to an annotated region tree. This method is very useful for debugging the RegionAwareMemoryNodeProvider.

Parameters

rvsdg	The RVSDG that is converted to a region tree.
modRefSummary	The Mod/Ref summary used for annotating the region tree.

Returns: A string that contains the region tree.

Definition at line 1482 of file RegionAwareModRefSummarizer.cpp.

◆ VerifyBlocklists()

bool jlm::llvm::aa::RegionAwareModRefSummarizer::VerifyBlocklists ( ) const

private

For all ModRefSets where a blocklist is defined, checks that none of the MemoryNodes from the blocklist have been added to the ModRefSet.

Returns: true if all blocklists are satisfied.

Definition at line 1359 of file RegionAwareModRefSummarizer.cpp.

Member Data Documentation

◆ Context_

std::unique_ptr<Context> jlm::llvm::aa::RegionAwareModRefSummarizer::Context_

private

Definition at line 313 of file RegionAwareModRefSummarizer.hpp.

◆ ModRefSummary_

std::unique_ptr<RegionAwareModRefSummary> jlm::llvm::aa::RegionAwareModRefSummarizer::ModRefSummary_

private

The Mod/Ref summary produced by this summarizer

Definition at line 311 of file RegionAwareModRefSummarizer.hpp.

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

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

Classes

Public Member Functions

Static Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ~RegionAwareModRefSummarizer()

◆ RegionAwareModRefSummarizer() [1/2]

◆ RegionAwareModRefSummarizer() [2/2]

Member Function Documentation

◆ AddModRefSetBlocklist()

◆ AddModRefSimpleConstraint()

◆ AddPointerOriginTargets()

◆ AnnotateAlloca()

◆ AnnotateCall()

◆ AnnotateFree()

◆ AnnotateFunction()

◆ AnnotateLoad()

◆ AnnotateMalloc()

◆ AnnotateMemcpy()

◆ AnnotateMemset()

◆ AnnotateRegion()

◆ AnnotateSimpleNode()

◆ AnnotateStore()

◆ AnnotateStructuralNode()

◆ CallGraphSCCsToString()

◆ compressExternalInFunction()

◆ Create() [1/2]

◆ Create() [2/2]

◆ createCallGraph()

◆ CreateExternalModRefSet()

◆ CreateNonReentrantAllocaSets()

◆ CreateSimpleAllocaSet()

◆ doExternalCompression()

◆ findAllModRefSets()

◆ FindAllocasDeadInSccs()

◆ GetSimpleAllocasReachableFromRegionArguments()

◆ IsRecursionPossible()

◆ operator=()

◆ SolveModRefSetConstraintGraph()

◆ SummarizeModRefs()

◆ ToRegionTree()

◆ VerifyBlocklists()

Member Data Documentation

◆ Context_

◆ ModRefSummary_