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
util::HashSet< PointsToGraph::NodeIndex >	getReachableSimpleAllocas (std::queue< PointsToGraph::NodeIndex > &nodes)

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

util::HashSet< PointsToGraph::NodeIndex >	getSimpleAllocasReachableFromCallArguments (const rvsdg::SimpleNode &call)

void	removeSimpleAllocasAroundSetjmp ()

void	AddModRefSimpleConstraint (ModRefSetIndex from, ModRefSetIndex to)

void	addModRefSetSimpleAllocaAllowlist (ModRefSetIndex index, util::HashSet< PointsToGraph::NodeIndex > allowlist)

void	annotateInterproceduralRegion (const rvsdg::Region &region)

void	AnnotateFunction (const rvsdg::LambdaNode &lambda)

void	AnnotateRegion (const rvsdg::Region &region, ModRefSetIndex modRefSet, 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, ModRefEffect modRefEffect)

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

ModRefSetIndex	AnnotateMalloc (const rvsdg::SimpleNode &mallocNode, const rvsdg::LambdaNode &lambda)

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

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

void	SolveModRefSetConstraintGraph ()

bool	verifySimpleAllocaAllowlists () const

void	determineReadOnlyMemory ()

void	materializeSets ()

void	materializeSetsInFunction (const rvsdg::LambdaNode &lambda)

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

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.
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.
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 and flags are propagated along edges in the graph
Mod/Ref set materialization, converting implicit memory nodes into explicit memory nodes. During this materialization, memory nodes are also compressed into the external memory node if possible. Compression is done on a per-function basis, and is possible when a memory node's effects is always a subset of the effects on the external node, across all sets in the function.

In a previous version of this class, alloca blocking was done based on SCCs in the call graph. Given a function call where the caller is in a different SCC than the callee, any alloca defined in the callee's SCC can be blocked from being propagated to the call. In practise, this blocking only helped to remove loads from a single file in the benchmarks.

See also: ModRefSummarizer; MemoryStateEncoder

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

◆ addModRefSetSimpleAllocaAllowlist()

void jlm::llvm::aa::RegionAwareModRefSummarizer::addModRefSetSimpleAllocaAllowlist	(	ModRefSetIndex	index,
		util::HashSet< PointsToGraph::NodeIndex >	allowlist
	)

private

Defines a set of simple alloca memory nodes that are allowed to be added to the ModRefSet with the given index. When an allowlist is specified, all other simple allocas are blocked from being added.

Note: The allowlist only prevents propagation during solving, so the user must avoid adding simple alloca memory nodes manually.

See also: verifyAllowlists()

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

◆ addPointerOriginTargets()

void jlm::llvm::aa::RegionAwareModRefSummarizer::addPointerOriginTargets	(	ModRefSetIndex	modRefSetIndex,
		const rvsdg::Output &	origin,
		std::optional< size_t >	minTargetSize,
		ModRefEffect	modRefEffect
	)

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
modRefEffect	the effect the operation may have on the memory targeted by origin

Definition at line 1197 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateAlloca()

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

private

Definition at line 1272 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateCall()

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

private

Definition at line 1363 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateFree()

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

private

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

◆ annotateInterproceduralRegion()

void jlm::llvm::aa::RegionAwareModRefSummarizer::annotateInterproceduralRegion ( const rvsdg::Region & region )

private

Recursively traverses the given region to find and annotate all contained lambda nodes.

Parameters

region the interprocedural region to annotate

Definition at line 1060 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateLoad()

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

private

Definition at line 1244 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateMalloc()

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

private

Definition at line 1285 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateMemcpy()

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

private

Definition at line 1313 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateMemmove()

ModRefSetIndex jlm::llvm::aa::RegionAwareModRefSummarizer::AnnotateMemmove	(	const rvsdg::SimpleNode &	memmoveNode,
		const rvsdg::LambdaNode &	lambda
	)

private

Definition at line 1330 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateMemset()

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

private

Definition at line 1347 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateRegion()

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

private

Recursive call used to make the given region, its nodes and its subregions all be represented by the given ModRefSet.

Parameters

region	the region whose operations should be represented by the ModRefSet
modRefSet	the index of the ModRefSet used to represent the region
lambda	the function this region belongs to

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

◆ AnnotateStore()

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

private

Definition at line 1258 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateStructuralNode()

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

private

Definition at line 1125 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 1711 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 1701 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 922 of file RegionAwareModRefSummarizer.cpp.

◆ determineReadOnlyMemory()

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

private

After solving, the ModRefSet representing all external functions is used to determine if any non-escaped variables in the module are only referenced, and never written to. These memory nodes can be considered constant, and should be omitted from all ModRefSets.

Definition at line 1490 of file RegionAwareModRefSummarizer.cpp.

◆ getReachableSimpleAllocas()

util::HashSet< PointsToGraph::NodeIndex > jlm::llvm::aa::RegionAwareModRefSummarizer::getReachableSimpleAllocas ( std::queue< PointsToGraph::NodeIndex > & nodes )

private

Gets the set of simple allocas that can be reached in the PointsToGraph, from the given set of nodes, by following points-to relations. The starting nodes must all be of register kind.

Parameters

nodes the register nodes used as starting points for the reachability checks.

Returns: the set of simple alloca nodes reachable from the nodes

Definition at line 962 of file RegionAwareModRefSummarizer.cpp.

◆ getSimpleAllocasReachableFromCallArguments()

util::HashSet< PointsToGraph::NodeIndex > jlm::llvm::aa::RegionAwareModRefSummarizer::getSimpleAllocasReachableFromCallArguments ( const rvsdg::SimpleNode & call )

private

Gets the set of simple alloca nodes that are reachable from the call's arguments. Reachability is defined in terms of the PointsToGraph.

Parameters

call	the call whose arguments are checked

Returns: the set of simple allocas reachable from the call's arguments

Definition at line 1007 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 are reachable from region's arguments. Reachability is defined in terms of the PointsToGraph.

Parameters

region the region whose arguments are checked

Returns: the set of simple allocas reachable from region arguments

Definition at line 988 of file RegionAwareModRefSummarizer.cpp.

◆ materializeSets()

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

private

Goes through the solved ModRefSet instances and materializes them. Also performs compression into the external memory node.

See also: materializeSetsInFunction()

Definition at line 1518 of file RegionAwareModRefSummarizer.cpp.

◆ materializeSetsInFunction()

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

private

Materializes the ModRefSet instances in the given function, by explicitly adding memory nodes that are implicitly included in the set due to flags.

Also determines which memory nodes can be compressed into the external node in the function: memory nodes whose effects are always a subset of the effects on the external memory node, for every ModRefSet in the function.

Parameters

lambda the function whose sets should be materialized.

Definition at line 1527 of file RegionAwareModRefSummarizer.cpp.

◆ operator=()

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

delete

◆ removeSimpleAllocasAroundSetjmp()

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

private

Disqualifies allocas from being regarded as simple if they are reachable from the arguments of functions that call setjmp.

Definition at line 1029 of file RegionAwareModRefSummarizer.cpp.

◆ 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 1418 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 859 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 1651 of file RegionAwareModRefSummarizer.cpp.

◆ verifySimpleAllocaAllowlists()

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

private

For all ModRefSets where a simple alloca allowlist is defined, checks that no other simple allocas outside of the list are included.

Returns: true if all allowlists are satisfied.

Definition at line 1474 of file RegionAwareModRefSummarizer.cpp.

Member Data Documentation

◆ Context_

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

private

Definition at line 307 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 305 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

◆ addModRefSetSimpleAllocaAllowlist()

◆ AddModRefSimpleConstraint()

◆ addPointerOriginTargets()

◆ AnnotateAlloca()

◆ AnnotateCall()

◆ AnnotateFree()

◆ AnnotateFunction()

◆ annotateInterproceduralRegion()

◆ AnnotateLoad()

◆ AnnotateMalloc()

◆ AnnotateMemcpy()

◆ AnnotateMemmove()

◆ AnnotateMemset()

◆ AnnotateRegion()

◆ AnnotateSimpleNode()

◆ AnnotateStore()

◆ AnnotateStructuralNode()

◆ Create() [1/2]

◆ Create() [2/2]

◆ CreateSimpleAllocaSet()

◆ determineReadOnlyMemory()

◆ getReachableSimpleAllocas()

◆ getSimpleAllocasReachableFromCallArguments()

◆ getSimpleAllocasReachableFromRegionArguments()

◆ materializeSets()

◆ materializeSetsInFunction()

◆ operator=()

◆ removeSimpleAllocasAroundSetjmp()

◆ SolveModRefSetConstraintGraph()

◆ SummarizeModRefs()

◆ ToRegionTree()

◆ verifySimpleAllocaAllowlists()

Member Data Documentation

◆ Context_

◆ ModRefSummary_