#include <OnlineCycleDetection.hpp>

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

[legend]

Public Member Functions
	OnlineCycleDetector (PointerObjectSet &set, const GetSuccessorsFunctor &GetSuccessors, const UnifyPointerObjectsFunctor &UnifyPointerObjects)

void	InitializeTopologicalOrdering ()

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

size_t	NumOnlineCyclesDetected () const noexcept

size_t	NumOnlineCycleUnifications () const noexcept

Private Member Functions
bool	HasValidTopologicalOrder () const

bool	ObjectIsInTopologicalOrder (PointerObjectIndex object) const

bool	IsTopologicalOrderIndexFilled (PointerObjectIndex topologicalIndex) const

bool	ComesAfter (PointerObjectIndex after, PointerObjectIndex before) const

void	ClearDfsState ()

Private Attributes
PointerObjectSet &	Set_

const GetSuccessorsFunctor &	GetSuccessors_

const UnifyPointerObjectsFunctor &	UnifyPointerObjects_

std::vector< PointerObjectIndex >	ObjectToTopoOrder_

std::vector< PointerObjectIndex >	TopoOrderToObject_

std::stack< std::pair< PointerObjectIndex, bool > >	DfsStack_

util::HashSet< PointerObjectIndex >	DfsNodesVisited_

util::HashSet< PointerObjectIndex >	DfsCycleNodes_

std::vector< PointerObjectIndex >	DfsSupersetAndBeyond_

size_t	NumOnlineCyclesDetected_ = 0

size_t	NumOnlineCycleUnifications_ = 0

Static Private Attributes
static constexpr PointerObjectIndex	EmptyTopologicalSlot

Detailed Description

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

Online Cycle Detection maintains a topological ordering of all unification roots, with respect to superset edges. If this is not possible, there must be a cycle, which gets eliminated. Online Cycle Detection can not be combined with other cycle detection schemes, but that is OK, since OCD finds every cycle.

Template Parameters

GetSuccessorsFunctor	is a function returning the superset edge successors of a given node
UnifyPointerObjectsFunctor	is a function that unifies other unification roots.

Definition at line 27 of file OnlineCycleDetection.hpp.

Constructor & Destructor Documentation

◆ OnlineCycleDetector()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

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

inline

Definition at line 31 of file OnlineCycleDetection.hpp.

Member Function Documentation

◆ ClearDfsState()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

void jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::ClearDfsState ( )

inlineprivate

Prepares all internal state for a new DFS

Definition at line 375 of file OnlineCycleDetection.hpp.

◆ ComesAfter()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

bool jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::ComesAfter	(	PointerObjectIndex	after,
		PointerObjectIndex	before
	)		const

inlineprivate

Returns: true if the nodes after and before both have positions in the topological index, and after comes strictly after before. Otherwise false.

Definition at line 364 of file OnlineCycleDetection.hpp.

◆ HasValidTopologicalOrder()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

bool jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::HasValidTopologicalOrder ( ) const

inlineprivate

Function for validating that all invariants of the topological ordering are maintained. Nodes should have a position in the topological order iff they are unification roots. All successor roots should come later in the topological order. The bi-directional lookup, node <-> topological index, is maintained.

Returns: true if all invariants are satisfied, false otherwise

Definition at line 295 of file OnlineCycleDetection.hpp.

◆ InitializeTopologicalOrdering()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

void jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::InitializeTopologicalOrdering ( )

inline

Assigns each unification root a position in a topological ordering. If any cycles are detected, they are unified. This function assumes that GetSuccessors returns only unification roots.

Definition at line 46 of file OnlineCycleDetection.hpp.

◆ IsTopologicalOrderIndexFilled()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

bool jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::IsTopologicalOrderIndexFilled ( PointerObjectIndex topologicalIndex ) const

inlineprivate

The topological order contains all unification roots, and only unification roots.

Returns: true if the given index in the topological order is occupied, false otherwise.

Definition at line 354 of file OnlineCycleDetection.hpp.

◆ MaintainTopologicalOrder()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

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

inline

Call this function after adding a superset edge subset -> superset. Both must be unification roots. If subset has a higher topological index than superset, the topological order is re-arranged. If a cycle is detected, then it will be unified away, and the unification root is returned.

Parameters

subset	the tail of the just added superset edge
superset	the head of the just added superset edge

Returns: the root of the new unification, if any, otherwise nullopt.

Definition at line 107 of file OnlineCycleDetection.hpp.

◆ NumOnlineCyclesDetected()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

size_t jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NumOnlineCyclesDetected ( ) const

inlinenoexcept

Returns: how many cycles have been detected and eliminated by OCD

Definition at line 272 of file OnlineCycleDetection.hpp.

◆ NumOnlineCycleUnifications()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

size_t jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NumOnlineCycleUnifications ( ) const

inlinenoexcept

Returns: how many pairwise unifications have been made while eliminating cycles

Definition at line 281 of file OnlineCycleDetection.hpp.

◆ ObjectIsInTopologicalOrder()

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

bool jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::ObjectIsInTopologicalOrder ( PointerObjectIndex object ) const

inlineprivate

The topological order contains all unification roots, and only unification roots.

Returns: true if object has a position in the topological order, false otherwise.

Definition at line 344 of file OnlineCycleDetection.hpp.

Member Data Documentation

◆ DfsCycleNodes_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

util::HashSet<PointerObjectIndex> jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::DfsCycleNodes_

private

Definition at line 418 of file OnlineCycleDetection.hpp.

◆ DfsNodesVisited_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

util::HashSet<PointerObjectIndex> jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::DfsNodesVisited_

private

Definition at line 414 of file OnlineCycleDetection.hpp.

◆ DfsStack_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

std::stack<std::pair<PointerObjectIndex, bool> > jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::DfsStack_

private

Definition at line 411 of file OnlineCycleDetection.hpp.

◆ DfsSupersetAndBeyond_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

std::vector<PointerObjectIndex> jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::DfsSupersetAndBeyond_

private

Definition at line 421 of file OnlineCycleDetection.hpp.

◆ EmptyTopologicalSlot

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

constexpr PointerObjectIndex jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::EmptyTopologicalSlot

staticconstexprprivate

Initial value:

=

std::numeric_limits<PointerObjectIndex>::max()

Definition at line 394 of file OnlineCycleDetection.hpp.

◆ GetSuccessors_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

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

private

Definition at line 388 of file OnlineCycleDetection.hpp.

◆ NumOnlineCyclesDetected_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

size_t jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NumOnlineCyclesDetected_ = 0

private

Definition at line 424 of file OnlineCycleDetection.hpp.

◆ NumOnlineCycleUnifications_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

size_t jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::NumOnlineCycleUnifications_ = 0

private

Definition at line 425 of file OnlineCycleDetection.hpp.

◆ ObjectToTopoOrder_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

std::vector<PointerObjectIndex> jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::ObjectToTopoOrder_

private

Definition at line 400 of file OnlineCycleDetection.hpp.

◆ Set_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

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

private

Definition at line 385 of file OnlineCycleDetection.hpp.

◆ TopoOrderToObject_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

std::vector<PointerObjectIndex> jlm::llvm::aa::OnlineCycleDetector< GetSuccessorsFunctor, UnifyPointerObjectsFunctor >::TopoOrderToObject_

private

Definition at line 404 of file OnlineCycleDetection.hpp.

◆ UnifyPointerObjects_

template<typename GetSuccessorsFunctor , typename UnifyPointerObjectsFunctor >

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

private

Definition at line 389 of file OnlineCycleDetection.hpp.

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

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

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

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

Constructor & Destructor Documentation

◆ OnlineCycleDetector()

Member Function Documentation

◆ ClearDfsState()

◆ ComesAfter()

◆ HasValidTopologicalOrder()

◆ InitializeTopologicalOrdering()

◆ IsTopologicalOrderIndexFilled()

◆ MaintainTopologicalOrder()

◆ NumOnlineCyclesDetected()

◆ NumOnlineCycleUnifications()

◆ ObjectIsInTopologicalOrder()

Member Data Documentation

◆ DfsCycleNodes_

◆ DfsNodesVisited_

◆ DfsStack_

◆ DfsSupersetAndBeyond_

◆ EmptyTopologicalSlot

◆ GetSuccessors_

◆ NumOnlineCyclesDetected_

◆ NumOnlineCycleUnifications_

◆ ObjectToTopoOrder_

◆ Set_

◆ TopoOrderToObject_

◆ UnifyPointerObjects_

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