#include <PointerObjectSet.hpp>

Collaboration diagram for jlm::llvm::aa::PointerObjectConstraintSet:

Classes
struct	WorklistStatistics

Public Types
enum class	WorklistSolverPolicy { LeastRecentlyFired , TwoPhaseLeastRecentlyFired , TopologicalSort , FirstInFirstOut , LastInFirstOut }

using	ConstraintVariant = std::variant< SupersetConstraint, StoreConstraint, LoadConstraint, FunctionCallConstraint >

Public Member Functions
	PointerObjectConstraintSet (PointerObjectSet &set)

	PointerObjectConstraintSet (const PointerObjectConstraintSet &other)=delete

	PointerObjectConstraintSet (PointerObjectConstraintSet &&other)=delete

PointerObjectConstraintSet &	operator= (const PointerObjectConstraintSet &other)=delete

PointerObjectConstraintSet &	operator= (PointerObjectConstraintSet &&other)=delete

bool	IsFrozen () const noexcept

void	AddPointerPointeeConstraint (PointerObjectIndex pointer, PointerObjectIndex pointee)

void	AddPointsToExternalConstraint (PointerObjectIndex pointer)

void	AddRegisterContentEscapedConstraint (PointerObjectIndex registerIndex)

void	AddConstraint (ConstraintVariant c)

const std::vector< ConstraintVariant > &	GetConstraints () const noexcept

size_t	NumBaseConstraints () const noexcept

std::pair< size_t, size_t >	NumFlagConstraints () const noexcept

util::graph::Graph &	DrawSubsetGraph (util::graph::Writer &writer) const

size_t	PerformOfflineVariableSubstitution (bool storeRefCycleUnificationRoot)

size_t	NormalizeConstraints ()

WorklistStatistics	SolveUsingWorklist (WorklistSolverPolicy policy, bool enableOnlineCycleDetection, bool enableHybridCycleDetection, bool enableLazyCycleDetection, bool enableDifferencePropagation, bool enablePreferImplicitPropation)

size_t	SolveNaively ()

std::pair< std::unique_ptr< PointerObjectSet >, std::unique_ptr< PointerObjectConstraintSet > >	Clone () const

Static Public Member Functions
static const char *	WorklistSolverPolicyToString (WorklistSolverPolicy policy)

Private Member Functions
std::tuple< size_t, std::vector< util::HashSet< PointerObjectIndex > >, std::vector< bool > >	CreateOvsSubsetGraph ()

template<typename Worklist , bool EnableOnlineCycleDetection, bool EnableHybridCycleDetection, bool EnableLazyCycleDetection, bool EnableDifferencePropagation, bool EnablePreferImplicitPointees>
void	RunWorklistSolver (WorklistStatistics &statistics)

Private Attributes
PointerObjectSet &	Set_

std::vector< ConstraintVariant >	Constraints_

bool	ConstraintSetFrozen_

std::unordered_map< PointerObjectIndex, PointerObjectIndex >	RefNodeUnificationRoot_

Detailed Description

A class for adding and applying constraints to the points-to-sets of the PointerObjectSet. Unlike the set modification methods on PointerObjectSet, constraints can be added in any order, with the same result. Multiple solvers can be used to solve for the final points-to sets.

Some additional constraints on the PointerObject flags are built in.

Definition at line 843 of file PointerObjectSet.hpp.

Member Typedef Documentation

◆ ConstraintVariant

using jlm::llvm::aa::PointerObjectConstraintSet::ConstraintVariant = std::variant<SupersetConstraint, StoreConstraint, LoadConstraint, FunctionCallConstraint>

Definition at line 846 of file PointerObjectSet.hpp.

Member Enumeration Documentation

◆ WorklistSolverPolicy

enum jlm::llvm::aa::PointerObjectConstraintSet::WorklistSolverPolicy

strong

Enumerator
LeastRecentlyFired	A worklist policy based on selecting the work item that was least recently selected. From: A. Kanamori and D. Weise "Worklist management strategies for Dataflow Analysis" (1994) See also jlm::util::LrfWorklist
TwoPhaseLeastRecentlyFired	A worklist policy like LeastRecentlyFired, but using two lists instead of a priority queue. Described by: B. Hardekopf and C. Lin "The And and the Grasshopper: Fast and Accurate Pointer Analysis for Millions of Lines of Code" (2007) See also jlm::util::TwoPhaseLrfWorklist
TopologicalSort	Not a real worklist policy. For each "sweep", all nodes are visited in topological order. Any cycles found during topological sorting are eliminated. This continues until a full sweep has been done with no attempts at pushing to the worklist. Described by: Pearce 2007: "Efficient field-sensitive pointer analysis of C"
FirstInFirstOut	A worklist policy based on a queue. See also jlm::util::FifoWorklist
LastInFirstOut	A worklist policy based on a stack. See also jlm::util::LifoWorklist

Definition at line 849 of file PointerObjectSet.hpp.

Constructor & Destructor Documentation

◆ PointerObjectConstraintSet() [1/3]

jlm::llvm::aa::PointerObjectConstraintSet::PointerObjectConstraintSet ( PointerObjectSet & set )

inlineexplicit

Definition at line 958 of file PointerObjectSet.hpp.

◆ PointerObjectConstraintSet() [2/3]

jlm::llvm::aa::PointerObjectConstraintSet::PointerObjectConstraintSet ( const PointerObjectConstraintSet & other )

delete

◆ PointerObjectConstraintSet() [3/3]

jlm::llvm::aa::PointerObjectConstraintSet::PointerObjectConstraintSet ( PointerObjectConstraintSet && other )

delete

Member Function Documentation

◆ AddConstraint()

void jlm::llvm::aa::PointerObjectConstraintSet::AddConstraint ( ConstraintVariant c )

Generic add function for all struct based constraints

Parameters

c	an instance of a constraint struct, passed as a ConstraintVariant

Definition at line 969 of file PointerObjectSet.cpp.

◆ AddPointerPointeeConstraint()

void jlm::llvm::aa::PointerObjectConstraintSet::AddPointerPointeeConstraint	(	PointerObjectIndex	pointer,
		PointerObjectIndex	pointee
	)

The simplest constraint, on the form: pointee in P(pointer)

Parameters

pointer	the PointerObject that should have the pointee in its points-to set
pointee	the PointerObject that should be in the points-to-set

Definition at line 943 of file PointerObjectSet.cpp.

◆ AddPointsToExternalConstraint()

void jlm::llvm::aa::PointerObjectConstraintSet::AddPointsToExternalConstraint ( PointerObjectIndex pointer )

Adds a constraint making pointer flagged as pointing to external

Parameters

pointer the PointerObject that should be marked as pointing to external

Definition at line 953 of file PointerObjectSet.cpp.

◆ AddRegisterContentEscapedConstraint()

void jlm::llvm::aa::PointerObjectConstraintSet::AddRegisterContentEscapedConstraint ( PointerObjectIndex registerIndex )

Ensures that any PointerObject in P(registerIndex) will be marked as escaped.

Parameters

registerIndex the register whose content leaves the module, thus exposing any memory it may point to

Definition at line 961 of file PointerObjectSet.cpp.

◆ Clone()

std::pair< std::unique_ptr< PointerObjectSet >, std::unique_ptr< PointerObjectConstraintSet > > jlm::llvm::aa::PointerObjectConstraintSet::Clone ( ) const

Creates a clone of this constraint set, and the underlying PointerObjectSet. The result is an identical copy, containing no references to the original.

Returns: the cloned PointerObjectSet and PointerObjectConstraintSet

Definition at line 2349 of file PointerObjectSet.cpp.

◆ CreateOvsSubsetGraph()

std::tuple< size_t, std::vector< util::HashSet< PointerObjectIndex > >, std::vector< bool > > jlm::llvm::aa::PointerObjectConstraintSet::CreateOvsSubsetGraph ( )

private

Creates a special subset graph containing both regular nodes n(v) and dereference nodes n(*v). The graph is used by PointerObjectConstraintSet::PerformOfflineVariableSubstitution().

Some nodes are marked as direct, when all subset predecessors are known offline. They can:

only be n(v) nodes, where v is a register
not be the return value of a function call
not be an argument of a function body

Returns

a tuple containing:

the total number of nodes N
a vector of length N containing the successors of each node
a boolean vector of length N, containing true on direct nodes, and false otherwise

Definition at line 1253 of file PointerObjectSet.cpp.

◆ DrawSubsetGraph()

util::graph::Graph & jlm::llvm::aa::PointerObjectConstraintSet::DrawSubsetGraph ( util::graph::Writer & writer ) const

Creates a subset graph containing all PointerObjects, their current points-to sets, and edges representing the current set of constraints.

Definition at line 1239 of file PointerObjectSet.cpp.

◆ GetConstraints()

const std::vector< PointerObjectConstraintSet::ConstraintVariant > & jlm::llvm::aa::PointerObjectConstraintSet::GetConstraints ( ) const

noexcept

Returns: all added constraints that were not simple one-off pointee inclusions or flag changes

Definition at line 976 of file PointerObjectSet.cpp.

◆ IsFrozen()

bool jlm::llvm::aa::PointerObjectConstraintSet::IsFrozen ( ) const

noexcept

Some offline processing relies on knowing about all constraints that will ever be added. After doing such processing, the constraint set is frozen, which prevents any new constraints from being added. Offline processing and solving can still be performed while frozen.

Returns: true if the constraint set has been frozen, false otherwise

Definition at line 937 of file PointerObjectSet.cpp.

◆ NormalizeConstraints()

size_t jlm::llvm::aa::PointerObjectConstraintSet::NormalizeConstraints ( )

Traverses the list of constraints, and does the following:

Redirects constraints to reference the root of unifications
Removes no-op constraints (e.g. X is a superset of X)
Removes duplicate constraints

Returns: the number of constraints that were removed

Definition at line 1488 of file PointerObjectSet.cpp.

◆ NumBaseConstraints()

size_t jlm::llvm::aa::PointerObjectConstraintSet::NumBaseConstraints ( ) const

noexcept

Returns: the number of base constraints

Definition at line 982 of file PointerObjectSet.cpp.

◆ NumFlagConstraints()

std::pair< size_t, size_t > jlm::llvm::aa::PointerObjectConstraintSet::NumFlagConstraints ( ) const

noexcept

Gets the number of flag constraints, among all PointerObjetcs. Flags that are unified are only counted once (on the unification root). The count is divided into two: flags for loads/stores of scalars, and the other flags

Returns: a pair (num flags on scalar operations, num other flags)

Definition at line 994 of file PointerObjectSet.cpp.

◆ operator=() [1/2]

PointerObjectConstraintSet& jlm::llvm::aa::PointerObjectConstraintSet::operator= ( const PointerObjectConstraintSet & other )

delete

◆ operator=() [2/2]

PointerObjectConstraintSet& jlm::llvm::aa::PointerObjectConstraintSet::operator= ( PointerObjectConstraintSet && other )

delete

◆ PerformOfflineVariableSubstitution()

size_t jlm::llvm::aa::PointerObjectConstraintSet::PerformOfflineVariableSubstitution ( bool storeRefCycleUnificationRoot )

Performs off-line detection of PointerObjects that can be shown to always contain the same pointees, and unifies them. It is a version of Rountev and Chandra, 2000: "Off-line variable substitution", modified to support SSA based constraint graphs.

The algorithm uses an offline constraint graph, consisting of two nodes per PointerObject v: n(v) represents the points-to set of v n(*v) represents the union of points-to sets of all pointees of v Edges in the graph represent points-to set inclusion.

In this graph, strongly connected components (SCCs) are collapsed into single equivalence sets.

If an SCC consists of only "direct" nodes, and all predecessors share equivalence set label, the SCC gets the same label. See PointerObjectConstraintSet::CreateOvsSubsetGraph() for a description of direct nodes.

All PointerObjects v1, ... vN where n(v1), ... n(vN) share equivalence set label, get unified. The run time is linear in the amount of PointerObjects and constraints.

Parameters

storeRefCycleUnificationRoot if true, ref nodes in cycles with regular nodes are stored, to be used by hybrid cycle detection during solving.

Returns: the number PointerObject unifications made

See also: NormalizeConstraints() call it afterwards to remove constraints made unnecessary.

Definition at line 1392 of file PointerObjectSet.cpp.

◆ RunWorklistSolver()

template<typename Worklist , bool EnableOnlineCycleDetection, bool EnableHybridCycleDetection, bool EnableLazyCycleDetection, bool EnableDifferencePropagation, bool EnablePreferImplicitPointees>

void jlm::llvm::aa::PointerObjectConstraintSet::RunWorklistSolver ( WorklistStatistics & statistics )

private

The worklist solver, with configuration passed at compile time as templates.

Parameters

statistics the WorklistStatistics instance that will get information about this run.

Template Parameters

Worklist	a type supporting the worklist interface with PointerObjectIndex as work items
EnableOnlineCycleDetection	if true, online cycle detection is enabled.
EnableHybridCycleDetection	if true, hybrid cycle detection is enabled.
EnableLazyCycleDetection	if true, lazy cycle detection is enabled.
EnableDifferencePropagation	if true, difference propagation is enabled.
EnablePreferImplicitPointees	if true, prefer implicit pointees is enabled

See also: SolveUsingWorklist() for the public interface.

Definition at line 1555 of file PointerObjectSet.cpp.

◆ SolveNaively()

size_t jlm::llvm::aa::PointerObjectConstraintSet::SolveNaively ( )

Iterates over and applies constraints until all points-to-sets satisfy them. Also applies inference rules on the escaped and pointing to external flags. This operation potentially has a long runtime, with an upper bound of O(n^5).

Returns: the number of iterations until a fixed solution was established. At least 1.

Definition at line 2319 of file PointerObjectSet.cpp.

◆ SolveUsingWorklist()

PointerObjectConstraintSet::WorklistStatistics jlm::llvm::aa::PointerObjectConstraintSet::SolveUsingWorklist	(	WorklistSolverPolicy	policy,
		bool	enableOnlineCycleDetection,
		bool	enableHybridCycleDetection,
		bool	enableLazyCycleDetection,
		bool	enableDifferencePropagation,
		bool	enablePreferImplicitPropation
	)

Finds a least solution satisfying all constraints, using the Worklist algorithm. Descriptions of the algorithm can be found in

Pearce et al. 2003: "Online cycle detection and difference propagation for pointer analysis"
Hardekopf and Lin, 2007: "The Ant and the Grasshopper". These papers also describe a set of techniques that potentially improve solving performance:
Online Cycle Detection (Pearce, 2003)
Hybrid Cycle Detection (Hardekopf 2007)
Lazy Cycle Detection (Hardekopf 2007)

Difference Propagation (Pearce, 2003)

Parameters

policy	the worklist iteration order policy to use
enableOnlineCycleDetection	if true, online cycle detection will be performed.
enableHybridCycleDetection	if true, hybrid cycle detection will be performed.
enableLazyCycleDetection	if true, lazy cycle detection will be performed.
enableDifferencePropagation	if true, difference propagation will be enabled.
enablePreferImplicitPropation	if true, enables PIP, which is novel to this codebase

Returns: an instance of WorklistStatistics describing solver statistics

Definition at line 2187 of file PointerObjectSet.cpp.

◆ WorklistSolverPolicyToString()

const char * jlm::llvm::aa::PointerObjectConstraintSet::WorklistSolverPolicyToString ( WorklistSolverPolicy policy )

static

Definition at line 2299 of file PointerObjectSet.cpp.

Member Data Documentation

◆ Constraints_

std::vector<ConstraintVariant> jlm::llvm::aa::PointerObjectConstraintSet::Constraints_

private

Definition at line 1168 of file PointerObjectSet.hpp.

◆ ConstraintSetFrozen_

bool jlm::llvm::aa::PointerObjectConstraintSet::ConstraintSetFrozen_

private

Definition at line 1172 of file PointerObjectSet.hpp.

◆ RefNodeUnificationRoot_

std::unordered_map<PointerObjectIndex, PointerObjectIndex> jlm::llvm::aa::PointerObjectConstraintSet::RefNodeUnificationRoot_

private

Definition at line 1177 of file PointerObjectSet.hpp.

◆ Set_

PointerObjectSet& jlm::llvm::aa::PointerObjectConstraintSet::Set_

private

Definition at line 1165 of file PointerObjectSet.hpp.

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

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

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ ConstraintVariant

Member Enumeration Documentation

◆ WorklistSolverPolicy

Constructor & Destructor Documentation

◆ PointerObjectConstraintSet() [1/3]

◆ PointerObjectConstraintSet() [2/3]

◆ PointerObjectConstraintSet() [3/3]

Member Function Documentation

◆ AddConstraint()

◆ AddPointerPointeeConstraint()

◆ AddPointsToExternalConstraint()

◆ AddRegisterContentEscapedConstraint()

◆ Clone()

◆ CreateOvsSubsetGraph()

◆ DrawSubsetGraph()

◆ GetConstraints()

◆ IsFrozen()

◆ NormalizeConstraints()

◆ NumBaseConstraints()

◆ NumFlagConstraints()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ PerformOfflineVariableSubstitution()

◆ RunWorklistSolver()

◆ SolveNaively()

◆ SolveUsingWorklist()

◆ WorklistSolverPolicyToString()

Member Data Documentation

◆ Constraints_

◆ ConstraintSetFrozen_

◆ RefNodeUnificationRoot_

◆ Set_