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	AnnotateCall (const rvsdg::SimpleNode &callNode, const rvsdg::LambdaNode &lambda)

void	SolveModRefSetConstraintGraph ()

bool	VerifyBlocklists () const

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

See also: ModRefSummarizer; MemoryStateEncoder

Definition at line 55 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 924 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 916 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 1049 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateAlloca()

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

private

Definition at line 1120 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateCall()

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

private

Definition at line 1170 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateFree()

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

private

Definition at line 1138 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 933 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateLoad()

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

private

Definition at line 1092 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateMalloc()

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

private

Definition at line 1129 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateMemcpy()

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

private

Definition at line 1153 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 951 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 1001 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateStore()

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

private

Definition at line 1106 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateStructuralNode()

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

private

Definition at line 985 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 1277 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 1364 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 1354 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 562 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 890 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 832 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 748 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 704 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 788 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 825 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 1218 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 467 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 1299 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 1261 of file RegionAwareModRefSummarizer.cpp.

Member Data Documentation

◆ Context_

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

private

Definition at line 285 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 283 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()

◆ AnnotateRegion()

◆ AnnotateSimpleNode()

◆ AnnotateStore()

◆ AnnotateStructuralNode()

◆ CallGraphSCCsToString()

◆ Create() [1/2]

◆ Create() [2/2]

◆ createCallGraph()

◆ CreateExternalModRefSet()

◆ CreateNonReentrantAllocaSets()

◆ CreateSimpleAllocaSet()

◆ FindAllocasDeadInSccs()

◆ GetSimpleAllocasReachableFromRegionArguments()

◆ IsRecursionPossible()

◆ operator=()

◆ SolveModRefSetConstraintGraph()

◆ SummarizeModRefs()

◆ ToRegionTree()

◆ VerifyBlocklists()

Member Data Documentation

◆ Context_

◆ ModRefSummary_