#include <LocalAliasAnalysis.hpp>

Inheritance diagram for jlm::llvm::aa::LocalAliasAnalysis:

Collaboration diagram for jlm::llvm::aa::LocalAliasAnalysis:

Public Member Functions
	LocalAliasAnalysis ()

	~LocalAliasAnalysis () noexcept override

size_t	getMaxTraceCollectionSize ()

void	setMaxTraceCollectionSize (size_t maxTraceCollectionSize)

std::string	ToString () const override

AliasQueryResponse	Query (const rvsdg::Output &p1, size_t s1, const rvsdg::Output &p2, size_t s2) override

Public Member Functions inherited from jlm::llvm::aa::AliasAnalysis
	AliasAnalysis ()

virtual	~AliasAnalysis () noexcept

Private Member Functions
bool	IsOriginalOriginFullyTraceable (const rvsdg::Output &pointer)

bool	HasOnlyFullyTraceableTopOrigins (TraceCollection &traces)

Static Private Member Functions
static AliasQueryResponse	QueryOffsets (std::optional< int64_t > offset1, size_t s1, std::optional< int64_t > offset2, size_t s2)

static bool	IsOriginalOrigin (const rvsdg::Output &pointer)

static bool	HasOnlyOriginalTopOrigins (TraceCollection &traces)

static std::optional< size_t >	GetOriginalOriginSize (const rvsdg::Output &pointer)

static std::optional< size_t >	GetRemainingSize (const rvsdg::Output &basePointer, const std::optional< int64_t > &offsetInBytes)

static void	RemoveTopOriginsWithRemainingSizeBelow (TraceCollection &traces, size_t s)

static size_t	GetMinimumOffsetFromStart (TraceCollection &traces)

static void	RemoveTopOriginsSmallerThanSize (TraceCollection &traces, size_t s)

static void	RemoveTopOriginsWithinTheFirstNBytes (TraceCollection &traces, size_t s, size_t N)

static bool	DoTraceCollectionsOverlap (TraceCollection &tc1, size_t s1, TraceCollection &tc2, size_t s2)

static bool	hasOnlyAllocaTopOrigins (const TraceCollection &traceCollection)

static void	removeArgumentTopOrigins (TraceCollection &traceCollection)

Private Attributes
size_t	maxTraceCollectionSize_ = 1000

std::unordered_map< const rvsdg::Output *, bool >	IsFullyTraceable_

Additional Inherited Members
Public Types inherited from jlm::llvm::aa::AliasAnalysis
enum	AliasQueryResponse { NoAlias , MayAlias , MustAlias }

Detailed Description

Class for making alias analysis queries using stateless ad hoc IR traversal. It roughly corresponds to BasicAA from LLVM. It is unable to trace via memory or across function calls. It tries to keep track of pointer offsets when possible, and can respond NoAlias when the queried pointers are based on distinct offsets into the same base pointer. If the offsets are identical, MustAlias is returned.

Definition at line 25 of file LocalAliasAnalysis.hpp.

Constructor & Destructor Documentation

◆ LocalAliasAnalysis()

jlm::llvm::aa::LocalAliasAnalysis::LocalAliasAnalysis ( )

default

◆ ~LocalAliasAnalysis()

jlm::llvm::aa::LocalAliasAnalysis::~LocalAliasAnalysis ( )

overridedefaultnoexcept

Member Function Documentation

◆ DoTraceCollectionsOverlap()

bool jlm::llvm::aa::LocalAliasAnalysis::DoTraceCollectionsOverlap	(	TraceCollection &	tc1,
		size_t	s1,
		TraceCollection &	tc2,
		size_t	s2
	)

staticprivate

Checks if any of the top origins in the two trace collections are the same, and have overlapping offsets. Only identical top origins are considered, so if two distinct top origins point to the same memory, that aliasing will not be detected by this method.

Parameters

tc1	the collection of traces of p1
s1	the size of the operation performed at p1
tc2	the collection of traces of p2
s2	the size of the operation performed at p2

Returns: true if any top origins are shared, and possibly overlap

Definition at line 387 of file LocalAliasAnalysis.cpp.

◆ getMaxTraceCollectionSize()

size_t jlm::llvm::aa::LocalAliasAnalysis::getMaxTraceCollectionSize ( )

Gets the maximum trace collection size before the analysis gives up with "MayAlias". If set <= 1, tracing stops as soon as a value has multiple origins, or unknown offset.

Returns: the maximum number of outputs to trace before giving up on a pointer.

Definition at line 39 of file LocalAliasAnalysis.cpp.

◆ GetMinimumOffsetFromStart()

size_t jlm::llvm::aa::LocalAliasAnalysis::GetMinimumOffsetFromStart ( TraceCollection & traces )

staticprivate

Finds the minimum distance into some memory region the traced pointer is pointing. For example, if the trace collection only contains the trace p = b + 12 we know that any operation on p will not touch the first 12 bytes of whatever region b is in. The region must also be at least 12 + s bytes large.

Parameters

traces

Returns: the minimum offset among all traces in the collection, or 0 if some are unknown

Definition at line 326 of file LocalAliasAnalysis.cpp.

◆ GetOriginalOriginSize()

std::optional< size_t > jlm::llvm::aa::LocalAliasAnalysis::GetOriginalOriginSize ( const rvsdg::Output & pointer )

staticprivate

Gets the size of the memory location(s) defined at the given output's operation. If the output is not an original origin, or the size is unknown, nullopt is returned.

Parameters

pointer a pointer output, should be from a memory location defining operation

Returns: the size of the defined memory location, or nullopt if it is unknown

Definition at line 250 of file LocalAliasAnalysis.cpp.

◆ GetRemainingSize()

std::optional< size_t > jlm::llvm::aa::LocalAliasAnalysis::GetRemainingSize	(	const rvsdg::Output &	basePointer,
		const std::optional< int64_t > &	offsetInBytes
	)

staticprivate

Given a traced pointer origin like p, where b = alloca[3 x i32] p = b + 8

we know that an operation starting at p can have a maximum size of 4 bytes. This function attempts to calculate this size, known as the pointer's remaining size.

If the offset is larger than the size of the target, the size 0 is returned. If the offset is unknown, the size of the target is returned.

Parameters

basePointer	The base pointer of the traced pointer.
offsetInBytes	The offset in bytes of the traced pointer.

Returns: the number of bytes left after the given traced pointer, or nullopt if unknown.

Definition at line 283 of file LocalAliasAnalysis.cpp.

◆ hasOnlyAllocaTopOrigins()

bool jlm::llvm::aa::LocalAliasAnalysis::hasOnlyAllocaTopOrigins ( const TraceCollection & traceCollection )

staticprivate

Checks if the given traceCollection only contains top origins that are allocas in the current function.

Parameters

traceCollection the TraceCollection to check

Returns: true iff all top origins in tc are alloca outputs

Definition at line 408 of file LocalAliasAnalysis.cpp.

◆ HasOnlyFullyTraceableTopOrigins()

bool jlm::llvm::aa::LocalAliasAnalysis::HasOnlyFullyTraceableTopOrigins ( TraceCollection & traces )

private

Checks if the given trace collection only contains top origins that are fully traced.

Parameters

traces the trace collection

Returns: true if all top origins are fully traceable

Definition at line 572 of file LocalAliasAnalysis.cpp.

◆ HasOnlyOriginalTopOrigins()

bool jlm::llvm::aa::LocalAliasAnalysis::HasOnlyOriginalTopOrigins ( TraceCollection & traces )

staticprivate

Checks if all top origins in the trace collection are original.

Parameters

traces the trace collection

Returns: true if all top origins are original, false otherwise

Definition at line 239 of file LocalAliasAnalysis.cpp.

◆ IsOriginalOrigin()

bool jlm::llvm::aa::LocalAliasAnalysis::IsOriginalOrigin ( const rvsdg::Output & pointer )

staticprivate

Checks if the given pointer is the direct result of a memory location defining operation. These operations are guaranteed to output pointers that do not alias any pointer, except for those that are based on the original pointer itself. The pointer is also guaranteed to be at the very beginning of the memory region.

For example, the output of an AllocaOperation, a LlvmDeltaOperation, or a rvsdg::GraphImport, are such original origins.

Parameters

pointer the pointer value to check

Returns: true if the pointer is the original pointer to a memory location

Definition at line 213 of file LocalAliasAnalysis.cpp.

◆ IsOriginalOriginFullyTraceable()

bool jlm::llvm::aa::LocalAliasAnalysis::IsOriginalOriginFullyTraceable ( const rvsdg::Output & pointer )

private

Checks if the given pointer is the output of an original memory location, AND that the address of the memory location is never passed anywhere that is not traceable back to the original operation.

Only AllocaOperation is fully traceable, and only when the address can be traced to all uses, and all uses are loads and stores. If the address is passed to a function, or stored in a variable, the AllocaOperation is not fully traceable. For a fully traceable AllocaOperation, any use of its address can therefore be traced back to the AllocaOperation using the TraceAllPointerOrigins function

In summary: this function performs a simple, local, escape analysis for ALLOCAs. Its result is cached for performance.

Parameters

pointer the pointer output to be analyzed

Returns: true if the output is an original pointer, and it can be fully traced

Definition at line 442 of file LocalAliasAnalysis.cpp.

◆ Query()

AliasAnalysis::AliasQueryResponse jlm::llvm::aa::LocalAliasAnalysis::Query	(	const rvsdg::Output &	p1,
		size_t	s1,
		const rvsdg::Output &	p2,
		size_t	s2
	)

overridevirtual

Queries the alias analysis about two memory regions represented as pointer + size pairs.

Parameters

p1	the first pointer value
s1	the byte size of the first pointer access
p2	the second pointer value
s2	the byte size of the second pointer access

Returns: the result of the alias query

Implements jlm::llvm::aa::AliasAnalysis.

Definition at line 51 of file LocalAliasAnalysis.cpp.

◆ QueryOffsets()

AliasAnalysis::AliasQueryResponse jlm::llvm::aa::LocalAliasAnalysis::QueryOffsets	(	std::optional< int64_t >	offset1,
		size_t	s1,
		std::optional< int64_t >	offset2,
		size_t	s2
	)

staticprivate

Given two pointers with the same base pointer p1 = base + offset1 p2 = base + offset2 Answers if the regions [p1, p1 + s1) and [p2, p2 + s2) may alias. If p1 == p2, MustAlias is returned.

Parameters

offset1	the offset of the first pointer. If it is nullopt, the offset is unknown.
s1	the size of the first memory region
offset2	the offset of the second pointer. If it is nullopt, the offset is unknown.
s2	the size of the second memory region

Definition at line 186 of file LocalAliasAnalysis.cpp.

◆ removeArgumentTopOrigins()

void jlm::llvm::aa::LocalAliasAnalysis::removeArgumentTopOrigins ( TraceCollection & traceCollection )

staticprivate

Removes all top origins from the given traceCollection that are arguments to the function.

Parameters

traceCollection the TraceCollection to modify

Definition at line 419 of file LocalAliasAnalysis.cpp.

◆ RemoveTopOriginsSmallerThanSize()

void jlm::llvm::aa::LocalAliasAnalysis::RemoveTopOriginsSmallerThanSize	(	TraceCollection &	traces,
		size_t	s
	)

staticprivate

For each top origin in the given trace collection, it is removed if it is too small. This function considers the total size of the target, and ignores the offset.

Parameters

traces	the trace collection
s	the minimum size of remaining top origins

Definition at line 353 of file LocalAliasAnalysis.cpp.

◆ RemoveTopOriginsWithinTheFirstNBytes()

void jlm::llvm::aa::LocalAliasAnalysis::RemoveTopOriginsWithinTheFirstNBytes	(	TraceCollection &	traces,
		size_t	s,
		size_t	N
	)

staticprivate

When a top origin represents an original memory location, its offset indicates how far into the memory region the operation is accessing memory. If this access only touches memory within the first N bytes, remove the top origin.

Parameters

traces	the traces of some pointer p being accessed
s	the size of the memory access performed at the traced pointer
N	the number of bytes into its memory region an access must be to be kept.

Definition at line 367 of file LocalAliasAnalysis.cpp.

◆ RemoveTopOriginsWithRemainingSizeBelow()

void jlm::llvm::aa::LocalAliasAnalysis::RemoveTopOriginsWithRemainingSizeBelow	(	TraceCollection &	traces,
		size_t	s
	)

staticprivate

For each top origin in the given trace collection, it is removed if it is deemed too small. Let p be the traced pointer, and let the TraceCollection contain p = b + o, where b is an original origin with a statically known size of S bytes.

We know that the operation being performed at p has a length of s bytes. If o + s > S, the operation would exceed the bounds of b. The traced origin p = b + o can therefore be removed as an impossibility.

Further, if we have a trace p = c + unknown offset, where c is an original origin whose size is exactly equal to s, then we replace the unknown offset with a 0, as that is the only possible offset that leaves s bytes remaining in the trace.

Parameters

traces	the trace collection
s	the size of the operation being performed at the traced pointer

Definition at line 302 of file LocalAliasAnalysis.cpp.

◆ setMaxTraceCollectionSize()

void jlm::llvm::aa::LocalAliasAnalysis::setMaxTraceCollectionSize ( size_t maxTraceCollectionSize )

Sets the maximum number of outputs a pointer can be traced to before giving up with "MayAlias" If set <= 1, tracing stops as soon as a value has multiple origins, or unknown offset.

Parameters

maxTraceCollectionSize the number of outputs

Definition at line 45 of file LocalAliasAnalysis.cpp.

◆ ToString()

std::string jlm::llvm::aa::LocalAliasAnalysis::ToString ( ) const

overridevirtual

Returns: a string description of the alias analysis

Implements jlm::llvm::aa::AliasAnalysis.

Definition at line 33 of file LocalAliasAnalysis.cpp.

Member Data Documentation

◆ IsFullyTraceable_

std::unordered_map<const rvsdg::Output *, bool> jlm::llvm::aa::LocalAliasAnalysis::IsFullyTraceable_

private

Memoization of "fully traceable" (escape analysis) queries. It assumes that no changes are made to the underlying RVSDG between queries.

Definition at line 247 of file LocalAliasAnalysis.hpp.

◆ maxTraceCollectionSize_

size_t jlm::llvm::aa::LocalAliasAnalysis::maxTraceCollectionSize_ = 1000

private

The number of outputs a pointer can be traced to before giving up

See also: setMaxTraceCollectionSize

Definition at line 241 of file LocalAliasAnalysis.hpp.

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

jlm/llvm/opt/alias-analyses/LocalAliasAnalysis.hpp
jlm/llvm/opt/alias-analyses/LocalAliasAnalysis.cpp

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ LocalAliasAnalysis()

◆ ~LocalAliasAnalysis()

Member Function Documentation

◆ DoTraceCollectionsOverlap()

◆ getMaxTraceCollectionSize()

◆ GetMinimumOffsetFromStart()

◆ GetOriginalOriginSize()

◆ GetRemainingSize()

◆ hasOnlyAllocaTopOrigins()

◆ HasOnlyFullyTraceableTopOrigins()

◆ HasOnlyOriginalTopOrigins()

◆ IsOriginalOrigin()

◆ IsOriginalOriginFullyTraceable()

◆ Query()

◆ QueryOffsets()

◆ removeArgumentTopOrigins()

◆ RemoveTopOriginsSmallerThanSize()

◆ RemoveTopOriginsWithinTheFirstNBytes()

◆ RemoveTopOriginsWithRemainingSizeBelow()

◆ setMaxTraceCollectionSize()

◆ ToString()

Member Data Documentation

◆ IsFullyTraceable_

◆ maxTraceCollectionSize_