jlm::llvm::aa::Andersen Class Reference

#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.
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	AnalyzePtrMask (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	AnalyzePoison (const rvsdg::SimpleNode &node)
void	AnalyzeFreeze (const rvsdg::SimpleNode &node)
void	AnalyzeMemcpy (const rvsdg::SimpleNode &node)
void	AnalyzeMemset (const rvsdg::SimpleNode &node)
void	AnalyzeMemmove (const rvsdg::SimpleNode &node)
void	AnalyzeConstantArray (const rvsdg::SimpleNode &node)
void	AnalyzeConstantStruct (const rvsdg::SimpleNode &node)
void	AnalyzeConstantAggregateZero (const rvsdg::SimpleNode &node)
void	AnalyzeInsertValue (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 24 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 1677 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 1575 of file Andersen.cpp.

AnalyzeAlloca()

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

private

Definition at line 750 of file Andersen.cpp.

AnalyzeBitcast()

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

private

Definition at line 869 of file Andersen.cpp.

AnalyzeBits2ptr()

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

private

Definition at line 888 of file Andersen.cpp.

AnalyzeCall()

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

private

Definition at line 817 of file Andersen.cpp.

AnalyzeConstantAggregateZero()

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

private

Definition at line 1073 of file Andersen.cpp.

AnalyzeConstantArray()

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

private

Definition at line 1028 of file Andersen.cpp.

AnalyzeConstantPointerNull()

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

private

Definition at line 914 of file Andersen.cpp.

AnalyzeConstantStruct()

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

private

Definition at line 1050 of file Andersen.cpp.

AnalyzeDelta()

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

private

Definition at line 1265 of file Andersen.cpp.

AnalyzeExtractValue()

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

private

Definition at line 1124 of file Andersen.cpp.

AnalyzeFreeze()

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

private

Definition at line 954 of file Andersen.cpp.

AnalyzeFunctionToPointer()

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

private

Definition at line 1175 of file Andersen.cpp.

AnalyzeGamma()

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

private

Definition at line 1350 of file Andersen.cpp.

AnalyzeGep()

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

private

Definition at line 840 of file Andersen.cpp.

AnalyzeInsertValue()

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

private

Definition at line 1087 of file Andersen.cpp.

AnalyzeIOBarrier()

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

private

Definition at line 1190 of file Andersen.cpp.

AnalyzeLambda()

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

private

Definition at line 1232 of file Andersen.cpp.

AnalyzeLoad()

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

private

Definition at line 776 of file Andersen.cpp.

AnalyzeMalloc()

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

private

Definition at line 763 of file Andersen.cpp.

AnalyzeMemcpy()

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

private

Definition at line 971 of file Andersen.cpp.

AnalyzeMemmove()

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

private

Definition at line 993 of file Andersen.cpp.

AnalyzeMemset()

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

private

Definition at line 1015 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 1518 of file Andersen.cpp.

AnalyzePhi()

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

private

Definition at line 1304 of file Andersen.cpp.

AnalyzePointerToFunction()

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

private

Definition at line 1160 of file Andersen.cpp.

AnalyzePoison()

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

private

Definition at line 940 of file Andersen.cpp.

AnalyzePtrMask()

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

private

Definition at line 855 of file Andersen.cpp.

AnalyzePtrToInt()

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

private

Definition at line 902 of file Andersen.cpp.

AnalyzeRegion()

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

private

Definition at line 1430 of file Andersen.cpp.

AnalyzeRvsdg()

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

private

Definition at line 1464 of file Andersen.cpp.

AnalyzeSimpleNode()

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

private

Definition at line 625 of file Andersen.cpp.

AnalyzeStore()

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

private

Definition at line 797 of file Andersen.cpp.

AnalyzeStructuralNode()

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

private

Definition at line 1205 of file Andersen.cpp.

AnalyzeTheta()

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

private

Definition at line 1387 of file Andersen.cpp.

AnalyzeUndef()

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

private

Definition at line 926 of file Andersen.cpp.

AnalyzeValist()

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

private

Definition at line 1139 of file Andersen.cpp.

ConstructPointsToGraphFromPointerObjectSet() [1/2]

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

static

Definition at line 1779 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 1684 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 1512 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 1506 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 1529 of file Andersen.cpp.

Member Data Documentation

Config_

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

private

Definition at line 472 of file Andersen.hpp.

Constraints_

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

private

Definition at line 475 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 48 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 53 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 34 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 41 of file Andersen.hpp.

Set_

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

private

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