Jlm
Loading...
Searching...
No Matches
Classes | Public Member Functions | Static Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
jlm::llvm::aa::RegionAwareModRefSummarizer Class Referencefinal

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

#include <RegionAwareModRefSummarizer.hpp>

Inheritance diagram for jlm::llvm::aa::RegionAwareModRefSummarizer:
Inheritance graph
[legend]
Collaboration diagram for jlm::llvm::aa::RegionAwareModRefSummarizer:
Collaboration graph
[legend]

Classes

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

Public Member Functions

 ~RegionAwareModRefSummarizer () noexcept override
 
 RegionAwareModRefSummarizer ()
 
 RegionAwareModRefSummarizer (const RegionAwareModRefSummarizer &)=delete
 
RegionAwareModRefSummarizeroperator= (const RegionAwareModRefSummarizer &)=delete
 
std::unique_ptr< ModRefSummarySummarizeModRefs (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< ModRefSummaryCreate (const rvsdg::RvsdgModule &rvsdgModule, const PointsToGraph &pointsToGraph, util::StatisticsCollector &statisticsCollector)
 
static std::unique_ptr< ModRefSummaryCreate (const rvsdg::RvsdgModule &rvsdgModule, const PointsToGraph &pointsToGraph)
 

Private Member Functions

void createCallGraph (const rvsdg::RvsdgModule &rvsdgModule)
 
util::HashSet< PointsToGraph::NodeIndexgetReachableSimpleAllocas (std::queue< PointsToGraph::NodeIndex > &nodes)
 
util::HashSet< PointsToGraph::NodeIndexgetSimpleAllocasReachableFromRegionArguments (const rvsdg::Region &region)
 
util::HashSet< PointsToGraph::NodeIndexgetSimpleAllocasReachableFromCallArguments (const rvsdg::SimpleNode &call)
 
bool IsRecursionPossible (const rvsdg::LambdaNode &lambda) const
 
size_t CreateNonReentrantAllocaSets ()
 
void AddModRefSimpleConstraint (ModRefSetIndex from, ModRefSetIndex to)
 
void AddModRefSetBlocklist (ModRefSetIndex index, const util::HashSet< PointsToGraph::NodeIndex > &blocklist)
 
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< ModRefSetIndexAnnotateSimpleNode (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 VerifyBlocklists () const
 
void determineReadOnlyMemory ()
 
void materializeSets ()
 
void materializeSetsInFunction (const rvsdg::LambdaNode &lambda)
 

Static Private Member Functions

static util::HashSet< PointsToGraph::NodeIndexCreateSimpleAllocaSet (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< RegionAwareModRefSummaryModRefSummary_
 
std::unique_ptr< ContextContext_
 

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. Mod/Ref Graph Solving: Mod/Ref sets and flags are propagated along edges in the graph
  6. 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 63 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 1350 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 1340 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
modRefSetIndexthe index of the ModRefSet representing some memory operation
originthe output producing the pointer value being operated on
minTargetSizean optional size requirement for targeted memory locations
modRefEffectthe effect the operation may have on the memory targeted by origin

Definition at line 1484 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateAlloca()

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

Definition at line 1559 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateCall()

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

Definition at line 1650 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateFree()

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

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

◆ AnnotateLoad()

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

Definition at line 1531 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateMalloc()

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

Definition at line 1572 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateMemcpy()

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

Definition at line 1600 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateMemmove()

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

Definition at line 1617 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateMemset()

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

Definition at line 1634 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
regionthe region whose operations should be represented by the ModRefSet
modRefSetthe index of the ModRefSet used to represent the region
lambdathe function this region belongs to

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

◆ AnnotateStore()

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

Definition at line 1545 of file RegionAwareModRefSummarizer.cpp.

◆ AnnotateStructuralNode()

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

Definition at line 1405 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 1933 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
rvsdgModuleThe RVSDG module for which the ModRefSummary should be computed.
pointsToGraphThe PointsToGraph corresponding to the RVSDG module.
Returns
A new instance of ModRefSummary.

Definition at line 2015 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
rvsdgModuleThe RVSDG module for which the ModRefSummary should be computed.
pointsToGraphThe PointsToGraph corresponding to the RVSDG module.
statisticsCollectorThe statistics collector for collecting pass statistics.
Returns
A new instance of ModRefSummary.

Definition at line 2005 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
rvsdgModulethe module for which a mod/ref summary is computed.

Definition at line 1025 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 1281 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 1167 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 1769 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
nodesthe register nodes used as starting points for the reachability checks.
Returns
the set of simple alloca nodes reachable from the nodes

Definition at line 1207 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
callthe call whose arguments are checked
Returns
the set of simple allocas reachable from the call's arguments

Definition at line 1252 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
regionthe region whose arguments are checked
Returns
the set of simple allocas reachable from region arguments

Definition at line 1233 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
lambdathe function in question.
Returns
true if it is possible for lambda to be involved in recursion, false otherwise

Definition at line 1274 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 1797 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
lambdathe function whose sets should be materialized.

Definition at line 1809 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 1700 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
rvsdgModuleThe RVSDG module for which a ModRefSummary should be computed.
pointsToGraphThe points-to graph corresponding to rvsdgModule.
statisticsCollectorThe statistics collector for collecting pass statistics.
Returns
An instance of ModRefSummary.

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

Definition at line 914 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
rvsdgThe RVSDG that is converted to a region tree.
modRefSummaryThe Mod/Ref summary used for annotating the region tree.
Returns
A string that contains the region tree.

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

Member Data Documentation

◆ Context_

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

Definition at line 337 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 335 of file RegionAwareModRefSummarizer.hpp.


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