#include <LazyCycleDetection.hpp>

Collaboration diagram for jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >:

[legend]

Public Member Functions
	LazyCycleDetector (PointerObjectSet &set, const GetSuccessorsFunctor &GetSuccessors, const UnifyPointerObjectsFunctor &unifyPointerObjects)

void	Initialize ()

bool	IsInitialized () const noexcept

std::optional< PointerObjectIndex >	OnPropagatedNothing (PointerObjectIndex subset, PointerObjectIndex superset)

size_t	NumCycleDetectionAttempts () const noexcept

size_t	NumCyclesDetected () const noexcept

size_t	NumCycleUnifications () const noexcept

Private Attributes
PointerObjectSet &	Set_

const GetSuccessorsFunctor &	GetSuccessors_

const UnifyPointerObjectsFunctor &	UnifyPointerObjects_

util::HashSet< std::pair< PointerObjectIndex, PointerObjectIndex > >	CheckedEdges_

std::stack< PointerObjectIndex >	DfsStack_

std::vector< uint8_t >	NodeStates_

size_t	NumCycleDetectAttempts_ = 0

size_t	NumCyclesDetected_ = 0

size_t	NumCycleUnifications_ = 0

Static Private Attributes
static constexpr uint8_t	NodeStateNotVisited = 0

static constexpr uint8_t	NodeStateVisited = 1

static constexpr uint8_t	NodeStatePopped = 2

Detailed Description

template<typename GetSuccessorsFunctor, typename UnifyPointerObjectsFunctor>
class jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >

Implements Lazy Cycle Detection, as described by Hardekopf and Lin, 2007: "The And and the Grasshopper"

Template Parameters

GetSuccessorsFunctor	is a function returning the superset edge successors of a given node
UnifyPointerObjectsFunctor	the functor to be called to unify a cycle, when found

Definition at line 27 of file LazyCycleDetection.hpp.

Constructor & Destructor Documentation

◆ LazyCycleDetector()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::LazyCycleDetector	(	PointerObjectSet &	set,
		const GetSuccessorsFunctor &	GetSuccessors,
		const UnifyPointerObjectsFunctor &	unifyPointerObjects
	)

inline

Definition at line 31 of file LazyCycleDetection.hpp.

Member Function Documentation

◆ Initialize()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

void jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::Initialize ( )

inline

Call before calling any other method

Definition at line 44 of file LazyCycleDetection.hpp.

◆ IsInitialized()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

bool jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::IsInitialized ( ) const

inlinenoexcept

Definition at line 50 of file LazyCycleDetection.hpp.

◆ NumCycleDetectionAttempts()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

size_t jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NumCycleDetectionAttempts ( ) const

inlinenoexcept

Returns: the number of DFSs performed to look for cycles

Definition at line 141 of file LazyCycleDetection.hpp.

◆ NumCyclesDetected()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

size_t jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NumCyclesDetected ( ) const

inlinenoexcept

Returns: the number of cycles detected by Lazy cycle detection

Definition at line 150 of file LazyCycleDetection.hpp.

◆ NumCycleUnifications()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

size_t jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NumCycleUnifications ( ) const

inlinenoexcept

Returns: the number of unifications made while eliminating found cycles

Definition at line 159 of file LazyCycleDetection.hpp.

◆ OnPropagatedNothing()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

std::optional<PointerObjectIndex> jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::OnPropagatedNothing	(	PointerObjectIndex	subset,
		PointerObjectIndex	superset
	)

inline

Call when an edge subset -> superset was visited, and zero pointees had to be propagated. Only call if subset has at least one new pointee. If a path from superset to subset is found, there is a cycle, that gets unified.

Parameters

subset	the tail of the added edge, must be unification root
superset	the head of the added edge, must be unification root

Returns: the root of the unification if unification happened, otherwise nullopt

Definition at line 64 of file LazyCycleDetection.hpp.

Member Data Documentation

◆ CheckedEdges_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

util::HashSet<std::pair<PointerObjectIndex, PointerObjectIndex> > jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::CheckedEdges_

private

Definition at line 170 of file LazyCycleDetection.hpp.

◆ DfsStack_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

std::stack<PointerObjectIndex> jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::DfsStack_

private

Definition at line 173 of file LazyCycleDetection.hpp.

◆ GetSuccessors_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

const GetSuccessorsFunctor& jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::GetSuccessors_

private

Definition at line 166 of file LazyCycleDetection.hpp.

◆ NodeStateNotVisited

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

constexpr uint8_t jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NodeStateNotVisited = 0

staticconstexprprivate

Definition at line 175 of file LazyCycleDetection.hpp.

◆ NodeStatePopped

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

constexpr uint8_t jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NodeStatePopped = 2

staticconstexprprivate

Definition at line 177 of file LazyCycleDetection.hpp.

◆ NodeStates_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

std::vector<uint8_t> jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NodeStates_

private

Definition at line 178 of file LazyCycleDetection.hpp.

◆ NodeStateVisited

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

constexpr uint8_t jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NodeStateVisited = 1

staticconstexprprivate

Definition at line 176 of file LazyCycleDetection.hpp.

◆ NumCycleDetectAttempts_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

size_t jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NumCycleDetectAttempts_ = 0

private

Definition at line 180 of file LazyCycleDetection.hpp.

◆ NumCyclesDetected_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

size_t jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NumCyclesDetected_ = 0

private

Definition at line 181 of file LazyCycleDetection.hpp.

◆ NumCycleUnifications_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

size_t jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NumCycleUnifications_ = 0

private

Definition at line 182 of file LazyCycleDetection.hpp.

◆ Set_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

PointerObjectSet& jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::Set_

private

Definition at line 165 of file LazyCycleDetection.hpp.

◆ UnifyPointerObjects_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

const UnifyPointerObjectsFunctor& jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::UnifyPointerObjects_

private

Definition at line 167 of file LazyCycleDetection.hpp.

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

jlm/llvm/opt/alias-analyses/LazyCycleDetection.hpp

Public Member Functions

Private Attributes

Static Private Attributes

Detailed Description

template<typename GetSuccessorsFunctor, typename UnifyPointerObjectsFunctor> class jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >

Constructor & Destructor Documentation

◆ LazyCycleDetector()

Member Function Documentation

◆ Initialize()

◆ IsInitialized()

◆ NumCycleDetectionAttempts()

◆ NumCyclesDetected()

◆ NumCycleUnifications()

◆ OnPropagatedNothing()

Member Data Documentation

◆ CheckedEdges_

◆ DfsStack_

◆ GetSuccessors_

◆ NodeStateNotVisited

◆ NodeStatePopped

◆ NodeStates_

◆ NodeStateVisited

◆ NumCycleDetectAttempts_

◆ NumCyclesDetected_

◆ NumCycleUnifications_

◆ Set_

◆ UnifyPointerObjects_

template<typename GetSuccessorsFunctor, typename UnifyPointerObjectsFunctor>
class jlm::llvm::aa::LazyCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >