#include <LocalAliasAnalysis.hpp>

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

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

Classes
struct	TraceCollection

struct	TracedPointerOrigin

Public Member Functions
	LocalAliasAnalysis ()

	~LocalAliasAnalysis () noexcept override

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 std::optional< int64_t >	CalculateGepOffset (const rvsdg::SimpleNode &gepNode)

static TracedPointerOrigin	TracePointerOriginPrecise (const rvsdg::Output &p)

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

static bool	TraceAllPointerOrigins (TracedPointerOrigin p, TraceCollection &traceCollection)

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 (TracedPointerOrigin trace)

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)

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

Static Private Attributes
static constexpr size_t	MaxTraceCollectionSize = 1000

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

◆ CalculateGepOffset()

std::optional< int64_t > jlm::llvm::aa::LocalAliasAnalysis::CalculateGepOffset ( const rvsdg::SimpleNode & gepNode )

staticprivate

Calculates the byte offset applied by the GEP, if the offset is static. The offset is the number of bytes needed to satisfy output ptr = input ptr + offset in bytes

Parameters

gepNode the node representing the GetElementPtrOperation

Returns: the offset applied by the GEP, if it is possible to determine at compile time

Definition at line 242 of file LocalAliasAnalysis.cpp.

◆ 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 601 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 540 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 466 of file LocalAliasAnalysis.cpp.

◆ GetRemainingSize()

std::optional< size_t > jlm::llvm::aa::LocalAliasAnalysis::GetRemainingSize ( TracedPointerOrigin trace )

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

trace the traced pointer

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

Definition at line 499 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 752 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 455 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 DeltaOperation, 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 429 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 622 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 72 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 299 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 567 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 581 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 516 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 30 of file LocalAliasAnalysis.cpp.

◆ TraceAllPointerOrigins()

bool jlm::llvm::aa::LocalAliasAnalysis::TraceAllPointerOrigins	(	TracedPointerOrigin	p,
		TraceCollection &	traceCollection
	)

staticprivate

Traces to find all possible origins of the given pointer. Traces through GetElementPtrOperation, including those with offsets that are not known at compile time. Also traces through gamma and theta nodes, building a set of multiple possibilities. Tracing stops at "top origins", for example an AllocaOperation, a LoadNonVolatileOperation, the return value of a CallOperation etc.

Parameters

p	the pointer to trace from
traceCollection	the collection of trace points being created

Returns: false if the trace collection reached its maximum allowed size, and tracing aborted

Definition at line 326 of file LocalAliasAnalysis.cpp.

◆ TracePointerOriginPrecise()

LocalAliasAnalysis::TracedPointerOrigin jlm::llvm::aa::LocalAliasAnalysis::TracePointerOriginPrecise ( const rvsdg::Output & p )

staticprivate

Returns the result of tracing the origin of p as far as possible, without tracing through operations that add an unknown offsets, or add multiple possible origins. Since the pointer has exactly one possible origin with a statically known offset, it may be possible to give MustAlias responses. If not, more extensive tracing can be performed using TraceAllPointerOrigins.

Parameters

p	the pointer value to trace

Returns: the TracedPointer for p, which is guaranteed to have a defined offset

Definition at line 266 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 250 of file LocalAliasAnalysis.hpp.

◆ MaxTraceCollectionSize

constexpr size_t jlm::llvm::aa::LocalAliasAnalysis::MaxTraceCollectionSize = 1000

staticconstexprprivate

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

Classes

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ LocalAliasAnalysis()

◆ ~LocalAliasAnalysis()

Member Function Documentation

◆ CalculateGepOffset()

◆ DoTraceCollectionsOverlap()

◆ GetMinimumOffsetFromStart()

◆ GetOriginalOriginSize()

◆ GetRemainingSize()

◆ HasOnlyFullyTraceableTopOrigins()

◆ HasOnlyOriginalTopOrigins()

◆ IsOriginalOrigin()

◆ IsOriginalOriginFullyTraceable()

◆ Query()

◆ QueryOffsets()

◆ RemoveTopOriginsSmallerThanSize()

◆ RemoveTopOriginsWithinTheFirstNBytes()

◆ RemoveTopOriginsWithRemainingSizeBelow()

◆ ToString()

◆ TraceAllPointerOrigins()

◆ TracePointerOriginPrecise()

Member Data Documentation

◆ IsFullyTraceable_

◆ MaxTraceCollectionSize