#include <Andersen.hpp>

Inheritance diagram for jlm::llvm::aa::Andersen:

Collaboration diagram for jlm::llvm::aa::Andersen:

Classes
class	Configuration

class	Statistics

Public Member Functions
	Andersen ()

	~Andersen () noexcept override

	Andersen (const Andersen &)=delete

	Andersen (Andersen &&)=delete

Andersen &	operator= (const Andersen &)=delete

Andersen &	operator= (Andersen &&)=delete

void	SetConfiguration (Configuration config)

const Configuration &	GetConfiguration () const

std::unique_ptr< PointsToGraph >	Analyze (const rvsdg::RvsdgModule &module, util::StatisticsCollector &statisticsCollector) override

std::unique_ptr< PointsToGraph >	Analyze (const LlvmRvsdgModule &module)
	Shorthand for Analyze, ignoring collecting any statistics. More...

Public Member Functions inherited from jlm::llvm::aa::PointsToAnalysis
virtual	~PointsToAnalysis ()=default

Static Public Member Functions
static std::unique_ptr< PointsToGraph >	ConstructPointsToGraphFromPointerObjectSet (const PointerObjectSet &set, Statistics &statistics)

static std::unique_ptr< PointsToGraph >	ConstructPointsToGraphFromPointerObjectSet (const PointerObjectSet &set)

Static Public Attributes
static const char *const	ENV_TEST_ALL_CONFIGS = "JLM_ANDERSEN_TEST_ALL_CONFIGS"

static const char *const	ENV_USE_EXACT_CONFIG = "JLM_ANDERSEN_USE_EXACT_CONFIG"

static const char *const	ENV_DOUBLE_CHECK = "JLM_ANDERSEN_DOUBLE_CHECK"

static const char *const	ENV_DUMP_SUBSET_GRAPH = "JLM_ANDERSEN_DUMP_SUBSET_GRAPH"

Private Member Functions
void	AnalyzeRegion (rvsdg::Region &region)

void	AnalyzeSimpleNode (const rvsdg::SimpleNode &node)

void	AnalyzeAlloca (const rvsdg::SimpleNode &node)

void	AnalyzeMalloc (const rvsdg::SimpleNode &node)

void	AnalyzeLoad (const rvsdg::SimpleNode &node)

void	AnalyzeStore (const rvsdg::SimpleNode &node)

void	AnalyzeCall (const rvsdg::SimpleNode &callNode)

void	AnalyzeGep (const rvsdg::SimpleNode &node)

void	AnalyzeBitcast (const rvsdg::SimpleNode &node)

void	AnalyzeBits2ptr (const rvsdg::SimpleNode &node)

void	AnalyzePtrToInt (const rvsdg::SimpleNode &node)

void	AnalyzeConstantPointerNull (const rvsdg::SimpleNode &node)

void	AnalyzeUndef (const rvsdg::SimpleNode &node)

void	AnalyzeMemcpy (const rvsdg::SimpleNode &node)

void	AnalyzeConstantArray (const rvsdg::SimpleNode &node)

void	AnalyzeConstantStruct (const rvsdg::SimpleNode &node)

void	AnalyzeConstantAggregateZero (const rvsdg::SimpleNode &node)

void	AnalyzeExtractValue (const rvsdg::SimpleNode &node)

void	AnalyzeValist (const rvsdg::SimpleNode &node)

void	AnalyzePointerToFunction (const rvsdg::SimpleNode &node)

void	AnalyzeFunctionToPointer (const rvsdg::SimpleNode &node)

void	AnalyzeIOBarrier (const rvsdg::SimpleNode &node)

void	AnalyzeStructuralNode (const rvsdg::StructuralNode &node)

void	AnalyzeLambda (const rvsdg::LambdaNode &node)

void	AnalyzeDelta (const rvsdg::DeltaNode &node)

void	AnalyzePhi (const rvsdg::PhiNode &node)

void	AnalyzeGamma (const rvsdg::GammaNode &node)

void	AnalyzeTheta (const rvsdg::ThetaNode &node)

void	AnalyzeRvsdg (const rvsdg::Graph &graph)

void	AnalyzeModule (const rvsdg::RvsdgModule &module, Statistics &statistics)

Static Private Member Functions
static void	SolveConstraints (PointerObjectConstraintSet &constraints, const Configuration &config, Statistics &statistics)

Private Attributes
Configuration	Config_ = Configuration::DefaultConfiguration()

std::unique_ptr< PointerObjectSet >	Set_ = {}

std::unique_ptr< PointerObjectConstraintSet >	Constraints_ = {}

Detailed Description

class implementing Andersen's set constraint based pointer analysis, based on the Ph.D. thesis Lars Ole Andersen - Program Analysis and Specialization for the C Programming Language The analysis is inter-procedural, field-insensitive, context-insensitive, flow-insensitive, and uses a static heap model.

Definition at line 25 of file Andersen.hpp.

Constructor & Destructor Documentation

◆ Andersen() [1/3]

jlm::llvm::aa::Andersen::Andersen ( )

default

◆ ~Andersen()

jlm::llvm::aa::Andersen::~Andersen ( )

overridedefaultnoexcept

◆ Andersen() [2/3]

jlm::llvm::aa::Andersen::Andersen ( const Andersen & )

delete

◆ Andersen() [3/3]

jlm::llvm::aa::Andersen::Andersen ( Andersen && )

delete

Member Function Documentation

◆ Analyze() [1/2]

std::unique_ptr< PointsToGraph > jlm::llvm::aa::Andersen::Analyze ( const LlvmRvsdgModule & module )

Shorthand for Analyze, ignoring collecting any statistics.

See also: Analyze

Definition at line 1528 of file Andersen.cpp.

◆ Analyze() [2/2]

std::unique_ptr< PointsToGraph > jlm::llvm::aa::Andersen::Analyze	(	const rvsdg::RvsdgModule &	module,
		util::StatisticsCollector &	statisticsCollector
	)

overridevirtual

Performs Andersen's alias analysis on the rvsdg module, producing a PointsToGraph describing what memory objects exists, and which values in the rvsdg program may point to them.

Parameters

module	the module to analyze
statisticsCollector	the collector that will receive pass statistics

Returns: A PointsToGraph for the module

See also: SetConfiguration to configure settings for the analysis

Implements jlm::llvm::aa::PointsToAnalysis.

Definition at line 1426 of file Andersen.cpp.

◆ AnalyzeAlloca()

void jlm::llvm::aa::Andersen::AnalyzeAlloca ( const rvsdg::SimpleNode & node )

private

Definition at line 718 of file Andersen.cpp.

◆ AnalyzeBitcast()

void jlm::llvm::aa::Andersen::AnalyzeBitcast ( const rvsdg::SimpleNode & node )

private

Definition at line 823 of file Andersen.cpp.

◆ AnalyzeBits2ptr()

void jlm::llvm::aa::Andersen::AnalyzeBits2ptr ( const rvsdg::SimpleNode & node )

private

Definition at line 842 of file Andersen.cpp.

◆ AnalyzeCall()

void jlm::llvm::aa::Andersen::AnalyzeCall ( const rvsdg::SimpleNode & callNode )

private

Definition at line 785 of file Andersen.cpp.

◆ AnalyzeConstantAggregateZero()

void jlm::llvm::aa::Andersen::AnalyzeConstantAggregateZero ( const rvsdg::SimpleNode & node )

private

Definition at line 961 of file Andersen.cpp.

◆ AnalyzeConstantArray()

void jlm::llvm::aa::Andersen::AnalyzeConstantArray ( const rvsdg::SimpleNode & node )

private

Definition at line 916 of file Andersen.cpp.

◆ AnalyzeConstantPointerNull()

void jlm::llvm::aa::Andersen::AnalyzeConstantPointerNull ( const rvsdg::SimpleNode & node )

private

Definition at line 868 of file Andersen.cpp.

◆ AnalyzeConstantStruct()

void jlm::llvm::aa::Andersen::AnalyzeConstantStruct ( const rvsdg::SimpleNode & node )

private

Definition at line 938 of file Andersen.cpp.

◆ AnalyzeDelta()

void jlm::llvm::aa::Andersen::AnalyzeDelta ( const rvsdg::DeltaNode & node )

private

Definition at line 1116 of file Andersen.cpp.

◆ AnalyzeExtractValue()

void jlm::llvm::aa::Andersen::AnalyzeExtractValue ( const rvsdg::SimpleNode & node )

private

Definition at line 975 of file Andersen.cpp.

◆ AnalyzeFunctionToPointer()

void jlm::llvm::aa::Andersen::AnalyzeFunctionToPointer ( const rvsdg::SimpleNode & node )

private

Definition at line 1026 of file Andersen.cpp.

◆ AnalyzeGamma()

void jlm::llvm::aa::Andersen::AnalyzeGamma ( const rvsdg::GammaNode & node )

private

Definition at line 1201 of file Andersen.cpp.

◆ AnalyzeGep()

void jlm::llvm::aa::Andersen::AnalyzeGep ( const rvsdg::SimpleNode & node )

private

Definition at line 808 of file Andersen.cpp.

◆ AnalyzeIOBarrier()

void jlm::llvm::aa::Andersen::AnalyzeIOBarrier ( const rvsdg::SimpleNode & node )

private

Definition at line 1041 of file Andersen.cpp.

◆ AnalyzeLambda()

void jlm::llvm::aa::Andersen::AnalyzeLambda ( const rvsdg::LambdaNode & node )

private

Definition at line 1083 of file Andersen.cpp.

◆ AnalyzeLoad()

void jlm::llvm::aa::Andersen::AnalyzeLoad ( const rvsdg::SimpleNode & node )

private

Definition at line 744 of file Andersen.cpp.

◆ AnalyzeMalloc()

void jlm::llvm::aa::Andersen::AnalyzeMalloc ( const rvsdg::SimpleNode & node )

private

Definition at line 731 of file Andersen.cpp.

◆ AnalyzeMemcpy()

void jlm::llvm::aa::Andersen::AnalyzeMemcpy ( const rvsdg::SimpleNode & node )

private

Definition at line 894 of file Andersen.cpp.

◆ AnalyzeModule()

void jlm::llvm::aa::Andersen::AnalyzeModule	(	const rvsdg::RvsdgModule &	module,
		Statistics &	statistics
	)

private

Traverses the given module, and initializes the members Set_ and Constraints_ with PointerObjects and constraints corresponding to the module.

Parameters

module	the module to analyze
statistics	the Statistics instance used to track info about the analysis

Definition at line 1369 of file Andersen.cpp.

◆ AnalyzePhi()

void jlm::llvm::aa::Andersen::AnalyzePhi ( const rvsdg::PhiNode & node )

private

Definition at line 1155 of file Andersen.cpp.

◆ AnalyzePointerToFunction()

void jlm::llvm::aa::Andersen::AnalyzePointerToFunction ( const rvsdg::SimpleNode & node )

private

Definition at line 1011 of file Andersen.cpp.

◆ AnalyzePtrToInt()

void jlm::llvm::aa::Andersen::AnalyzePtrToInt ( const rvsdg::SimpleNode & node )

private

Definition at line 856 of file Andersen.cpp.

◆ AnalyzeRegion()

void jlm::llvm::aa::Andersen::AnalyzeRegion ( rvsdg::Region & region )

private

Definition at line 1281 of file Andersen.cpp.

◆ AnalyzeRvsdg()

void jlm::llvm::aa::Andersen::AnalyzeRvsdg ( const rvsdg::Graph & graph )

private

Definition at line 1315 of file Andersen.cpp.

◆ AnalyzeSimpleNode()

void jlm::llvm::aa::Andersen::AnalyzeSimpleNode ( const rvsdg::SimpleNode & node )

private

Definition at line 617 of file Andersen.cpp.

◆ AnalyzeStore()

void jlm::llvm::aa::Andersen::AnalyzeStore ( const rvsdg::SimpleNode & node )

private

Definition at line 765 of file Andersen.cpp.

◆ AnalyzeStructuralNode()

void jlm::llvm::aa::Andersen::AnalyzeStructuralNode ( const rvsdg::StructuralNode & node )

private

Definition at line 1056 of file Andersen.cpp.

◆ AnalyzeTheta()

void jlm::llvm::aa::Andersen::AnalyzeTheta ( const rvsdg::ThetaNode & node )

private

Definition at line 1238 of file Andersen.cpp.

◆ AnalyzeUndef()

void jlm::llvm::aa::Andersen::AnalyzeUndef ( const rvsdg::SimpleNode & node )

private

Definition at line 880 of file Andersen.cpp.

◆ AnalyzeValist()

void jlm::llvm::aa::Andersen::AnalyzeValist ( const rvsdg::SimpleNode & node )

private

Definition at line 990 of file Andersen.cpp.

◆ ConstructPointsToGraphFromPointerObjectSet() [1/2]

std::unique_ptr< PointsToGraph > jlm::llvm::aa::Andersen::ConstructPointsToGraphFromPointerObjectSet ( const PointerObjectSet & set )

static

Definition at line 1630 of file Andersen.cpp.

◆ ConstructPointsToGraphFromPointerObjectSet() [2/2]

std::unique_ptr< PointsToGraph > jlm::llvm::aa::Andersen::ConstructPointsToGraphFromPointerObjectSet	(	const PointerObjectSet &	set,
		Statistics &	statistics
	)

static

Converts a PointerObjectSet into PointsToGraph nodes, and points-to-graph set memberships into edges.

In the PointerObjectSet, the PointsToExternal flag encodes pointing to an address available outside the module. This may however be the address of a memory object within the module, that has escaped. In the final PointsToGraph, any node marked as pointing to external, will get an edge to the special "external" node, as well as to every memory object node marked as escaped.

Parameters

set	the PointerObjectSet to convert
statistics	the statistics instance used to collect statistics about the process

Returns: the newly created PointsToGraph

Definition at line 1535 of file Andersen.cpp.

◆ GetConfiguration()

const Andersen::Configuration & jlm::llvm::aa::Andersen::GetConfiguration ( ) const

Returns: the PassConfiguration used by the Andersen pass when analyzing

Definition at line 1363 of file Andersen.cpp.

◆ operator=() [1/2]

Andersen& jlm::llvm::aa::Andersen::operator= ( Andersen && )

delete

◆ operator=() [2/2]

Andersen& jlm::llvm::aa::Andersen::operator= ( const Andersen & )

delete

◆ SetConfiguration()

void jlm::llvm::aa::Andersen::SetConfiguration ( Configuration config )

Specify the PassConfiguration the Andersen pass should use when analyzing

Parameters

config

Definition at line 1357 of file Andersen.cpp.

◆ SolveConstraints()

void jlm::llvm::aa::Andersen::SolveConstraints	(	PointerObjectConstraintSet &	constraints,
		const Configuration &	config,
		Statistics &	statistics
	)

staticprivate

Solves the constraint problem using the techniques and solver specified in the given config.

Parameters

constraints	the instance of PointerObjectConstraintSet being operated on
config	settings for the solving
statistics	the Statistics instance used to track info about the analysis

Definition at line 1380 of file Andersen.cpp.

Member Data Documentation

◆ Config_

Configuration jlm::llvm::aa::Andersen::Config_ = Configuration::DefaultConfiguration()

private

Definition at line 455 of file Andersen.hpp.

◆ Constraints_

std::unique_ptr<PointerObjectConstraintSet> jlm::llvm::aa::Andersen::Constraints_ = {}

private

Definition at line 458 of file Andersen.hpp.

◆ ENV_DOUBLE_CHECK

const char* const jlm::llvm::aa::Andersen::ENV_DOUBLE_CHECK = "JLM_ANDERSEN_DOUBLE_CHECK"

inlinestatic

Environment variable that will trigger double-checking of the analysis. If ENV_TEST_ALL_CONFIGS is set, the output is double-checked against them all. Otherwise, the output is double-checked only against the default naive solver.

Definition at line 49 of file Andersen.hpp.

◆ ENV_DUMP_SUBSET_GRAPH

const char* const jlm::llvm::aa::Andersen::ENV_DUMP_SUBSET_GRAPH = "JLM_ANDERSEN_DUMP_SUBSET_GRAPH"

inlinestatic

Environment variable that will trigger dumping the subset graph before and after solving.

Definition at line 54 of file Andersen.hpp.

◆ ENV_TEST_ALL_CONFIGS

const char* const jlm::llvm::aa::Andersen::ENV_TEST_ALL_CONFIGS = "JLM_ANDERSEN_TEST_ALL_CONFIGS"

inlinestatic

Environment variable that when set, triggers analyzing the program with every single valid combination of Configuration flags. Must be set to a number, that determines how many times each config is used.

Definition at line 35 of file Andersen.hpp.

◆ ENV_USE_EXACT_CONFIG

const char* const jlm::llvm::aa::Andersen::ENV_USE_EXACT_CONFIG = "JLM_ANDERSEN_USE_EXACT_CONFIG"

inlinestatic

Alternative to testing all configs, this environment variable specifies exactly which config to use. It must be an index into the Configuration::GetAllConfigurations() vector. Should likely not be combined with ENV_TEST_ALL_CONFIGS or ENV_DOUBLE_CHECK

Definition at line 42 of file Andersen.hpp.

◆ Set_

std::unique_ptr<PointerObjectSet> jlm::llvm::aa::Andersen::Set_ = {}

private

Definition at line 457 of file Andersen.hpp.

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

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

Classes

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Andersen() [1/3]

◆ ~Andersen()

◆ Andersen() [2/3]

◆ Andersen() [3/3]

Member Function Documentation

◆ Analyze() [1/2]

◆ Analyze() [2/2]

◆ AnalyzeAlloca()

◆ AnalyzeBitcast()

◆ AnalyzeBits2ptr()

◆ AnalyzeCall()

◆ AnalyzeConstantAggregateZero()

◆ AnalyzeConstantArray()

◆ AnalyzeConstantPointerNull()

◆ AnalyzeConstantStruct()

◆ AnalyzeDelta()

◆ AnalyzeExtractValue()

◆ AnalyzeFunctionToPointer()

◆ AnalyzeGamma()

◆ AnalyzeGep()

◆ AnalyzeIOBarrier()

◆ AnalyzeLambda()

◆ AnalyzeLoad()

◆ AnalyzeMalloc()

◆ AnalyzeMemcpy()

◆ AnalyzeModule()

◆ AnalyzePhi()

◆ AnalyzePointerToFunction()

◆ AnalyzePtrToInt()

◆ AnalyzeRegion()

◆ AnalyzeRvsdg()

◆ AnalyzeSimpleNode()

◆ AnalyzeStore()

◆ AnalyzeStructuralNode()

◆ AnalyzeTheta()

◆ AnalyzeUndef()

◆ AnalyzeValist()

◆ ConstructPointsToGraphFromPointerObjectSet() [1/2]

◆ ConstructPointsToGraphFromPointerObjectSet() [2/2]

◆ GetConfiguration()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ SetConfiguration()

◆ SolveConstraints()

Member Data Documentation

◆ Config_

◆ Constraints_

◆ ENV_DOUBLE_CHECK

◆ ENV_DUMP_SUBSET_GRAPH

◆ ENV_TEST_ALL_CONFIGS

◆ ENV_USE_EXACT_CONFIG

◆ Set_