jlm::llvm::aa Namespace Reference

Classes
class	AgnosticModRefSummary
	Mod/Ref summary of agnostic mod/ref summarizer. More...
class	AgnosticModRefSummarizer
	Agnostic mod/ref summarizer. More...
class	AliasAnalysis
class	ChainedAliasAnalysis
class	AliasAnalysisPrecisionEvaluator
class	Andersen
class	DifferencePropagation
class	EliminatedModRefSummarizer
	Combines a ModeRefSummarizer and a ModRefEliminator. More...
class	LazyCycleDetector
class	LocalAliasAnalysis
struct	MemoryStateTypeCounter
	Helper struct for counting up MemoryNodes, among some set of entities that use them. More...
class	EncodingStatistics
	Statistics class for memory state encoder encoding. More...
class	StateMap
	Hash map for mapping points-to graph memory nodes to RVSDG memory states. More...
class	RegionalizedStateMap
	Hash map for mapping Rvsdg regions to StateMap class instances. More...
class	MemoryStateEncoder
	Memory State Encoder. More...
class	ModRefEliminator
class	ModRefSummarizer
class	ModRefSummary
	Mod/Ref Summary. More...
class	OnlineCycleDetector
class	PointerObjectSet
class	SupersetConstraint
class	StoreConstraint
class	LoadConstraint
class	FunctionCallConstraint
class	EscapeFlagConstraint
class	EscapedFunctionConstraint
class	PointerObjectConstraintSet
class	PointsToAnalysis
	Points-to Analysis Interface. More...
class	PointsToAnalysisStateEncoder
class	PointsToGraph
class	PointsToGraphAliasAnalysis
class	ModRefSet
class	RegionAwareModRefSummary
	Mod/Ref summary of region-aware mod/ref summarizer. More...
class	RegionAwareModRefSummarizer
	Region-aware mod/ref summarizer. More...

Typedefs
using	PointerObjectIndex = uint32_t
using	ModRefSetIndex = uint32_t

Enumerations
enum class	PointerObjectKind : uint8_t {   Register = 0 , AllocaMemoryObject , MallocMemoryObject , GlobalMemoryObject ,   FunctionMemoryObject , ImportMemoryObject , COUNT }

Functions
static bool	AreAliasResponsesCompatible (AliasAnalysis::AliasQueryResponse a, AliasAnalysis::AliasQueryResponse b)
bool	IsPointerCompatible (const rvsdg::Output &value)
bool	IsOrContainsPointerType (const rvsdg::Type &type)
static std::optional< int64_t >	CalculateIntraTypeGepOffset (const rvsdg::SimpleNode &gepNode, size_t inputIndex, const rvsdg::Type &type)
static std::vector< MemoryNodeId >	GetMemoryNodeIds (const util::HashSet< PointsToGraph::NodeIndex > &memoryNodes)
template<typename MarkAsPointeesEscaping , typename MarkAsPointsToExternal >
void	HandleCallingExternalFunction (PointerObjectSet &set, const rvsdg::SimpleNode &callNode, MarkAsPointeesEscaping &markAsPointeesEscaping, MarkAsPointsToExternal &markAsPointsToExternal)
template<typename MarkAsPointeesEscaping , typename MarkAsPointsToExternal >
static void	HandleCallingImportedFunction (PointerObjectSet &set, const rvsdg::SimpleNode &callNode, [[maybe_unused]] PointerObjectIndex imported, MarkAsPointeesEscaping &markAsPointeesEscaping, MarkAsPointsToExternal &markAsPointsToExternal)
template<typename MakeSupersetFunctor >
static void	HandleLambdaCallParameters (PointerObjectSet &set, const rvsdg::SimpleNode &callNode, const rvsdg::LambdaNode &lambdaNode, MakeSupersetFunctor &makeSuperset)
template<typename MakeSupersetFunctor >
static void	HandleLambdaCallReturnValues (PointerObjectSet &set, const rvsdg::SimpleNode &callNode, const rvsdg::LambdaNode &lambdaNode, MakeSupersetFunctor &makeSuperset)
template<typename MakeSupersetFunctor >
static void	HandleCallingLambdaFunction (PointerObjectSet &set, const rvsdg::SimpleNode &callNode, PointerObjectIndex lambda, MakeSupersetFunctor &makeSuperset)
template<typename MarkAsPointeesEscapingFunctor , typename MarkAsPointsToExternalFunctor >
static void	HandleEscapedFunction (PointerObjectSet &set, PointerObjectIndex lambda, MarkAsPointeesEscapingFunctor &markAsPointeesEscaping, MarkAsPointsToExternalFunctor &markAsPointsToExternal)
static std::string	CreateSubsetGraphNodeLabel (PointerObjectSet &set, PointerObjectIndex index)
static void	CreateSubsetGraphNodes (PointerObjectSet &set, util::graph::Graph &graph)
static void	CreateSubsetGraphEdges (const PointerObjectSet &set, const std::vector< PointerObjectConstraintSet::ConstraintVariant > &constraints, util::graph::Graph &graph)
static void	LabelFunctionsArgumentsAndReturnValues (PointerObjectSet &set, util::graph::Graph &graph)
static std::vector< int64_t >	AssignOvsEquivalenceSetLabels (std::vector< util::HashSet< PointerObjectIndex >> &successors, size_t numSccs, std::vector< size_t > &sccIndex, std::vector< size_t > &reverseTopologicalOrder, std::vector< bool > &sccHasDirectNodesOnly)
static std::vector< const rvsdg::LambdaNode * >	CollectLambdaNodes (const rvsdg::RvsdgModule &rvsdgModule)

Variables
static constexpr bool	ENABLE_UNIFICATION = true
static const bool	ENABLE_DEAD_ALLOCA_BLOCKLIST = !std::getenv("JLM_DISABLE_DEAD_ALLOCA_BLOCKLIST")
static const bool	ENABLE_NON_REENTRANT_ALLOCA_BLOCKLIST
static const bool	ENABLE_OPERATION_SIZE_BLOCKING
static const bool	ENABLE_CONSTANT_MEMORY_BLOCKING

Typedef Documentation

ModRefSetIndex

using jlm::llvm::aa::ModRefSetIndex = typedef uint32_t

Definition at line 17 of file RegionAwareModRefSummarizer.hpp.

PointerObjectIndex

using jlm::llvm::aa::PointerObjectIndex = typedef uint32_t

Definition at line 44 of file PointerObjectSet.hpp.

Enumeration Type Documentation

PointerObjectKind

enum jlm::llvm::aa::PointerObjectKind : uint8_t

strong

Enumerator
Register
AllocaMemoryObject
MallocMemoryObject
GlobalMemoryObject
FunctionMemoryObject
ImportMemoryObject
COUNT

Definition at line 28 of file PointerObjectSet.hpp.

Function Documentation

AreAliasResponsesCompatible()

static bool jlm::llvm::aa::AreAliasResponsesCompatible ( AliasAnalysis::AliasQueryResponse  a, AliasAnalysis::AliasQueryResponse  b  )

static

Checks if two alias query responses are compatible with each other. NoAlias is incompatible with MustAlias, and vice versa. MayAlias is compatible with all responses.

Parameters

a	first alias query response to check
b	second alias query response to check

Returns

true if the responses are compatible, false otherwise

Definition at line 31 of file AliasAnalysis.cpp.

AssignOvsEquivalenceSetLabels()

static std::vector<int64_t> jlm::llvm::aa::AssignOvsEquivalenceSetLabels ( std::vector< util::HashSet< PointerObjectIndex >> &  successors, size_t  numSccs, std::vector< size_t > &  sccIndex, std::vector< size_t > &  reverseTopologicalOrder, std::vector< bool > &  sccHasDirectNodesOnly  )

static

Part of Offline Variable Substitution, works on the OVS subset graph. Takes the set of SCCs in the graph, and assigns equivalence set labels to each SCC. If all predecessors of a direct SCC have the same equivalence set label, that label is used.

Returns

a vector of equivalence set labels assigned to each SCC

See also

PointerObjectConstraintSet::IsOfflineVariableSubstitutionEnabled()

Definition at line 1330 of file PointerObjectSet.cpp.

CalculateIntraTypeGepOffset()

static std::optional<int64_t> jlm::llvm::aa::CalculateIntraTypeGepOffset ( const rvsdg::SimpleNode &  gepNode, size_t  inputIndex, const rvsdg::Type &  type  )

static

Calculates the byte offset inside the given type, starting at the given offset of GEP inputs. Uses recursion to handle nested types. If any indexing input is not a compile time constant, nullopt is returned.

Parameters

gepNode	the GEP node
inputIndex	the index of the input that applies inside the given type
type	the type the offset is inside

Returns

the byte offset within the given type, or nullopt if not possible.

Definition at line 190 of file LocalAliasAnalysis.cpp.

CollectLambdaNodes()

static std::vector<const rvsdg::LambdaNode *> jlm::llvm::aa::CollectLambdaNodes ( const rvsdg::RvsdgModule &  rvsdgModule )

static

Collects all lambda nodes defined in the given module, in an unspecified order.

Parameters

rvsdgModule

the module

Returns

a list of all lambda nodes in the module

Definition at line 532 of file RegionAwareModRefSummarizer.cpp.

CreateSubsetGraphEdges()

static void jlm::llvm::aa::CreateSubsetGraphEdges ( const PointerObjectSet &  set, const std::vector< PointerObjectConstraintSet::ConstraintVariant > &  constraints, util::graph::Graph &  graph  )

static

Creates edges representing the different constraints in the subset graph. Subset constraints become normal edges. Load and store constraints become dashed edges with a circle on the end being dereferenced. Function call constraints append to the labels to the nodes involved in the function call. Helper function used by DrawSubsetGraph.

Definition at line 1135 of file PointerObjectSet.cpp.

CreateSubsetGraphNodeLabel()

static std::string jlm::llvm::aa::CreateSubsetGraphNodeLabel ( PointerObjectSet &  set, PointerObjectIndex  index  )

static

Creates a label describing the PointerObject with the given index in the given set. The label includes the index and the PointerObjectKind. The PointerObject's pointees are included, or a reference to the unification root. Helper function used by DrawSubsetGraph.

Definition at line 1025 of file PointerObjectSet.cpp.

CreateSubsetGraphNodes()

static void jlm::llvm::aa::CreateSubsetGraphNodes ( PointerObjectSet &  set, util::graph::Graph &  graph  )

static

Creates GraphWriter nodes for each PointerObject in the set, with appropriate shape and label. Memory objects are rectangular, registers are oval. Escaped nodes have a yellow fill. Helper function used by DrawSubsetGraph.

Definition at line 1082 of file PointerObjectSet.cpp.

GetMemoryNodeIds()

static std::vector<MemoryNodeId> jlm::llvm::aa::GetMemoryNodeIds ( const util::HashSet< PointsToGraph::NodeIndex > &  memoryNodes )

static

Definition at line 608 of file MemoryStateEncoder.cpp.

HandleCallingExternalFunction()

template<typename MarkAsPointeesEscaping , typename MarkAsPointsToExternal >

void jlm::llvm::aa::HandleCallingExternalFunction	(	PointerObjectSet &	set,
		const rvsdg::SimpleNode &	callNode,
		MarkAsPointeesEscaping &	markAsPointeesEscaping,
		MarkAsPointsToExternal &	markAsPointsToExternal
	)

Handles informing the arguments and return values of the CallNode about possibly being sent to and retrieved from unknown code.

Parameters

set	the PointerObjectSet representing this module.
callNode	the RVSDG CallNode that represents the function call itself
markAsPointeesEscaping	the function to call when marking a register as pointees escaping
markAsPointsToExternal	called to flag a PointerObject as pointing to external

Definition at line 606 of file PointerObjectSet.cpp.

HandleCallingImportedFunction()

template<typename MarkAsPointeesEscaping , typename MarkAsPointsToExternal >

static void jlm::llvm::aa::HandleCallingImportedFunction ( PointerObjectSet &  set, const rvsdg::SimpleNode &  callNode, [[maybe_unused] ] PointerObjectIndex  imported, MarkAsPointeesEscaping &  markAsPointeesEscaping, MarkAsPointsToExternal &  markAsPointsToExternal  )

static

Handles informing the arguments and return values of the CallNode about possibly being sent to and received from a given PointerObject of ImportMemoryObject.

Parameters

set	the PointerObjectSet representing this module.
callNode	the RVSDG CallNode that represents the function call itself
imported	the PointerObject of ImportMemoryObject kind that might be called.
markAsPointeesEscaping	the function to call when marking a register as pointees escaping
markAsPointsToExternal	called to flag a PointerObject as pointing to external

Definition at line 644 of file PointerObjectSet.cpp.

HandleCallingLambdaFunction()

template<typename MakeSupersetFunctor >

static void jlm::llvm::aa::HandleCallingLambdaFunction ( PointerObjectSet &  set, const rvsdg::SimpleNode &  callNode, PointerObjectIndex  lambda, MakeSupersetFunctor &  makeSuperset  )

static

Handles informing the CallNode about possibly calling the function represented by lambda. Passes the points-to-sets of the arguments into the function subregion, and passes the points-to-sets of the function's return values back to the CallNode's outputs. Passing pointees is performed by calling the provided makeSuperset functor, with signature void(PointerObjectIndex superset, PointerObjectIndex subset)

Parameters

set	the PointerObjectSet representing this module.
callNode	the RVSDG CallNode that represents the function call itself
lambda	the PointerObject of FunctionMemoryObject kind that might be called.
makeSuperset	the function to call to make one points-to set a superset of another

Definition at line 733 of file PointerObjectSet.cpp.

HandleEscapedFunction()

template<typename MarkAsPointeesEscapingFunctor , typename MarkAsPointsToExternalFunctor >

static void jlm::llvm::aa::HandleEscapedFunction ( PointerObjectSet &  set, PointerObjectIndex  lambda, MarkAsPointeesEscapingFunctor &  markAsPointeesEscaping, MarkAsPointsToExternalFunctor &  markAsPointsToExternal  )

static

Given an escaped function, the results registers should be marked as escaping pointees, and all arguments as pointing to external, provided they are of types we track the pointees of. The modifications are made using the provided functors, which are called only if any flags are missing. Each functor takes a single parameter: The index of a PointerObject of Register kind that is missing the specified flag.

Parameters

set	the PointerObjectSet representing this module
lambda	the escaped PointerObject of function kind
markAsPointeesEscaping	the function to call when marking a register as pointees escaping
markAsPointsToExternal	called to flag a PointerObject as pointing to external

Definition at line 869 of file PointerObjectSet.cpp.

HandleLambdaCallParameters()

template<typename MakeSupersetFunctor >

static void jlm::llvm::aa::HandleLambdaCallParameters ( PointerObjectSet &  set, const rvsdg::SimpleNode &  callNode, const rvsdg::LambdaNode &  lambdaNode, MakeSupersetFunctor &  makeSuperset  )

static

Pairs up call node inputs and function body argument, and calls the provided makeSuperset to make the function body arguments include all pointees the call node may pass in.

Definition at line 668 of file PointerObjectSet.cpp.

HandleLambdaCallReturnValues()

template<typename MakeSupersetFunctor >

static void jlm::llvm::aa::HandleLambdaCallReturnValues ( PointerObjectSet &  set, const rvsdg::SimpleNode &  callNode, const rvsdg::LambdaNode &  lambdaNode, MakeSupersetFunctor &  makeSuperset  )

static

Pairs up function body results and call node outputs, and calls the provided makeSuperset to make the call node output include all possible returned pointees.

Definition at line 697 of file PointerObjectSet.cpp.

IsOrContainsPointerType()

bool jlm::llvm::aa::IsOrContainsPointerType

(

const rvsdg::Type &

type

)

If values are pointers, or contain pointers to things, its set of pointees must be tracked.

Parameters

type	the rvsdg type to be checked

Returns

true if pointees should be tracked for all values of the given type, otherwise false

Definition at line 22 of file Andersen.cpp.

IsPointerCompatible()

bool jlm::llvm::aa::IsPointerCompatible

(

const rvsdg::Output &

value

)

Determines if the given value is regarded as representing a pointer

Parameters

value

the value in question

Returns

true if value is or contains a pointer, false otherwise

Definition at line 74 of file AliasAnalysis.cpp.

LabelFunctionsArgumentsAndReturnValues()

static void jlm::llvm::aa::LabelFunctionsArgumentsAndReturnValues ( PointerObjectSet &  set, util::graph::Graph &  graph  )

static

Appends to the labels of all nodes that represent parts of functions. This includes nodes representing the function itself, e.g. "function4", nodes representing the functions arguments, e.g. "function4 arg2", and nodes representing values returned from the function, e.g. "function4 res0". Helper function used by DrawSubsetGraph.

Definition at line 1207 of file PointerObjectSet.cpp.

Variable Documentation

ENABLE_CONSTANT_MEMORY_BLOCKING

const bool jlm::llvm::aa::ENABLE_CONSTANT_MEMORY_BLOCKING

static

Initial value:

=
    !std::getenv("JLM_DISABLE_CONSTANT_MEMORY_BLOCKING")

Constant memory, such as functions, constant globals and constant import, can never change. We therefore never need to route their memory states through anything.

Definition at line 54 of file RegionAwareModRefSummarizer.cpp.

ENABLE_DEAD_ALLOCA_BLOCKLIST

const bool jlm::llvm::aa::ENABLE_DEAD_ALLOCA_BLOCKLIST = !std::getenv("JLM_DISABLE_DEAD_ALLOCA_BLOCKLIST")

static

allocas that are not defined in f(), and not defined in a predecessor of f() in the call graph, cannot be live inside f(). They are added to the DeadAllocaBlocklist.

Definition at line 32 of file RegionAwareModRefSummarizer.cpp.

ENABLE_NON_REENTRANT_ALLOCA_BLOCKLIST

const bool jlm::llvm::aa::ENABLE_NON_REENTRANT_ALLOCA_BLOCKLIST

static

Initial value:

=
    !std::getenv("JLM_DISABLE_NON_REENTRANT_ALLOCA_BLOCKLIST")

In a region with an alloca definition, the memory node representing the alloca does not need to be routed into the region if the alloca is shown to be non-reentrant. Such allocas are added to the NonReentrantBlocklist.

Definition at line 39 of file RegionAwareModRefSummarizer.cpp.

ENABLE_OPERATION_SIZE_BLOCKING

const bool jlm::llvm::aa::ENABLE_OPERATION_SIZE_BLOCKING

static

Initial value:

=
    !std::getenv("JLM_DISABLE_OPERATION_SIZE_BLOCKING")

Operations like loads and stores have a size. If the size is larger than the size of a memory represented by a memory node X, X can be excluded from the Mod/Ref summary of the operation.

Definition at line 47 of file RegionAwareModRefSummarizer.cpp.

ENABLE_UNIFICATION

constexpr bool jlm::llvm::aa::ENABLE_UNIFICATION = true

staticconstexpr

Flag that enables unification logic. When enabled, each points-to set lookup needs to perform a find operation. When disabled, attempting to call UnifyPointerObjects panics.

Definition at line 25 of file PointerObjectSet.cpp.