jlm::llvm::aa Namespace Reference

Classes
class	AgnosticModRefSet
	class returned by the Agnostic ModRefSummarizer More...
class	AgnosticModRefSummarizer
	Agnostic mod/ref summarizer. More...
class	AgnosticModRefSummary
	Mod/Ref summary of agnostic mod/ref summarizer. More...
class	AliasAnalysis
class	AliasAnalysisPrecisionEvaluator
class	Andersen
class	ChainedAliasAnalysis
class	DifferencePropagation
class	EliminatedModRefSummarizer
	Combines a ModeRefSummarizer and a ModRefEliminator. More...
class	EscapedFunctionConstraint
class	EscapeFlagConstraint
class	FunctionCallConstraint
class	LazyCycleDetector
class	LoadConstraint
class	LocalAliasAnalysis
class	MemoryStateEncoder
	Memory State Encoder. More...
struct	MemoryStateSummary
class	ModRefEliminator
class	ModRefSet
class	ModRefSummarizer
class	ModRefSummary
	Mod/Ref Summary. More...
class	OnlineCycleDetector
class	PointerObjectConstraintSet
class	PointerObjectSet
class	PointsToAnalysis
	Points-to Analysis Interface. More...
class	PointsToAnalysisStateEncoder
class	PointsToGraph
class	PointsToGraphAliasAnalysis
class	RegionAwareModRefSet
class	RegionAwareModRefSummarizer
	Region-aware mod/ref summarizer. More...
class	RegionAwareModRefSummary
	Mod/Ref summary of region-aware mod/ref summarizer. More...
class	StoreConstraint
class	SupersetConstraint

Typedefs
using	PointerObjectIndex = uint32_t
using	ModRefSetIndex = uint32_t

Enumerations
enum	ModRefEffect : uint8_t { NoEffect = 0 , RefOnly = 0b1 , ModOnly = 0b10 , ModRef = 0b11 }
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::vector< MemoryNodeId >	getModRefSetNodes (const ModRefSet &modRefSet)
std::vector< MemoryStateSummary >	collectMemoryStateDistribution (const rvsdg::Graph &rvsdg, const ModRefSummary &modRefSummary)
std::string	toString (const std::vector< MemoryStateSummary > &memoryStateDistribution)
bool	mayEffectReference (ModRefEffect effect)
bool	mayEffectModify (ModRefEffect effect)
ModRefEffect	operator| (ModRefEffect a, ModRefEffect b)
ModRefEffect &	operator|= (ModRefEffect &a, ModRefEffect b)
bool	isEffectSubset (ModRefEffect subset, ModRefEffect superset)
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, 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)

Variables
static constexpr bool	ENABLE_UNIFICATION = true
static const bool	ENABLE_OPERATION_SIZE_BLOCKING
static const bool	ENABLE_CONSTANT_MEMORY_BLOCKING
static const bool	ENABLE_READ_ONLY_DETECTION = !std::getenv("JLM_DISABLE_READ_ONLY_DETECTION")
static const bool	ENABLE_FUNCTION_SIMPLE_ALLOCA_ALLOWLIST
static const bool	ENABLE_CALL_SIMPLE_ALLOCA_ALLOWLIST
static const bool	ENABLE_EXTERN_SIMPLE_ALLOCA_ALLOWLIST

Typedef Documentation

ModRefSetIndex

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

Definition at line 20 of file RegionAwareModRefSummarizer.hpp.

PointerObjectIndex

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

Definition at line 44 of file PointerObjectSet.hpp.

Enumeration Type Documentation

ModRefEffect

enum jlm::llvm::aa::ModRefEffect : uint8_t

This enum represents the ways in which a ModRefSet may affect a memory node.

The enum values are chosen such that bitwise OR results in the union of effects.

Enumerator
NoEffect
RefOnly
ModOnly
ModRef

Definition at line 26 of file ModRefSummary.hpp.

PointerObjectKind

enum class 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.

collectMemoryStateDistribution()

std::vector< MemoryStateSummary > jlm::llvm::aa::collectMemoryStateDistribution	(	const rvsdg::Graph &	rvsdg,
		const ModRefSummary &	modRefSummary
	)

Definition at line 20 of file ModRefSummary.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.

getModRefSetNodes()

static std::vector< MemoryNodeId > jlm::llvm::aa::getModRefSetNodes ( const ModRefSet &  modRefSet )

static

Definition at line 444 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, 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.

isEffectSubset()

bool jlm::llvm::aa::isEffectSubset ( ModRefEffect  subset, ModRefEffect  superset  )

inline

Checks if the effects represented by subset are all contained within the effects represented by superset.

Parameters

subset	the subset effects to check
superset	the superset effects to check against

Returns

true if subset is a subset of superset, false otherwise

Definition at line 92 of file ModRefSummary.hpp.

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 30 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 76 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.

mayEffectModify()

bool jlm::llvm::aa::mayEffectModify ( ModRefEffect  effect )

inline

Returns

true if the given effect includes possibly modifying memory, false otherwise

Definition at line 55 of file ModRefSummary.hpp.

mayEffectReference()

bool jlm::llvm::aa::mayEffectReference ( ModRefEffect  effect )

inline

Returns

true if the given effect includes possibly referencing memory, false otherwise

Definition at line 45 of file ModRefSummary.hpp.

operator|()

ModRefEffect jlm::llvm::aa::operator| ( ModRefEffect  a, ModRefEffect  b  )

inline

Union operator between two ModRefEffect values.

Parameters

a	the first effect
b	the second effect

Returns

a ModRefEffect representing both a and b

Definition at line 68 of file ModRefSummary.hpp.

operator|=()

ModRefEffect & jlm::llvm::aa::operator|= ( ModRefEffect &  a, ModRefEffect  b  )

inline

Assignment operator version of union of two ModRefEffect values.

Definition at line 79 of file ModRefSummary.hpp.

toString()

std::string jlm::llvm::aa::toString

(

const std::vector< MemoryStateSummary > &

memoryStateDistribution

)

Definition at line 147 of file ModRefSummary.cpp.

Variable Documentation

ENABLE_CALL_SIMPLE_ALLOCA_ALLOWLIST

const bool jlm::llvm::aa::ENABLE_CALL_SIMPLE_ALLOCA_ALLOWLIST

static

Initial value:

=
    !std::getenv("JLM_DISABLE_CALL_SIMPLE_ALLOCA_ALLOWLIST")

When doing a call, only simple allocas that are reachable from the arguments to the call need to be propagated from the callee to the call. Other simple allocas can be blocked.

Definition at line 73 of file RegionAwareModRefSummarizer.cpp.

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 53 of file RegionAwareModRefSummarizer.cpp.

ENABLE_EXTERN_SIMPLE_ALLOCA_ALLOWLIST

const bool jlm::llvm::aa::ENABLE_EXTERN_SIMPLE_ALLOCA_ALLOWLIST

static

Initial value:

=
    !std::getenv("JLM_DISABLE_EXTERN_SIMPLE_ALLOCA_ALLOWLIST")

When creating a ModRefSet representing memory effects in external functions, simple allocas can always be excluded, since they by definition cannot be passed via external functions or otherwise be accessible from external modules.

Definition at line 81 of file RegionAwareModRefSummarizer.cpp.

ENABLE_FUNCTION_SIMPLE_ALLOCA_ALLOWLIST

const bool jlm::llvm::aa::ENABLE_FUNCTION_SIMPLE_ALLOCA_ALLOWLIST

static

Initial value:

=
    !std::getenv("JLM_DISABLE_FUNCTION_SIMPLE_ALLOCA_ALLOWLIST")

For functions, only simple allocas that are reachable from the function arguments need to be included in the ModRefSet of the function. Other simple allocas can be blocked.

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

ENABLE_READ_ONLY_DETECTION

const bool jlm::llvm::aa::ENABLE_READ_ONLY_DETECTION = !std::getenv("JLM_DISABLE_READ_ONLY_DETECTION")

static

Some global memory is not marked as constant, but can be proven to never be written to. Detecting this lets us treat them as constants, omitting them from memory state routing.

Definition at line 60 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.