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. 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	AnalyzePoison (const rvsdg::SimpleNode &node)
void	AnalyzeFreeze (const rvsdg::SimpleNode &node)
void	AnalyzeMemcpy (const rvsdg::SimpleNode &node)
void	AnalyzeMemset (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 1633 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 1531 of file Andersen.cpp.

AnalyzeAlloca()

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

private

Definition at line 742 of file Andersen.cpp.

AnalyzeBitcast()

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

private

Definition at line 847 of file Andersen.cpp.

AnalyzeBits2ptr()

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

private

Definition at line 866 of file Andersen.cpp.

AnalyzeCall()

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

private

Definition at line 809 of file Andersen.cpp.

AnalyzeConstantAggregateZero()

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

private

Definition at line 1029 of file Andersen.cpp.

AnalyzeConstantArray()

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

private

Definition at line 984 of file Andersen.cpp.

AnalyzeConstantPointerNull()

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

private

Definition at line 892 of file Andersen.cpp.

AnalyzeConstantStruct()

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

private

Definition at line 1006 of file Andersen.cpp.

AnalyzeDelta()

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

private

Definition at line 1221 of file Andersen.cpp.

AnalyzeExtractValue()

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

private

Definition at line 1080 of file Andersen.cpp.

AnalyzeFreeze()

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

private

Definition at line 932 of file Andersen.cpp.

AnalyzeFunctionToPointer()

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

private

Definition at line 1131 of file Andersen.cpp.

AnalyzeGamma()

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

private

Definition at line 1306 of file Andersen.cpp.

AnalyzeGep()

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

private

Definition at line 832 of file Andersen.cpp.

AnalyzeInsertValue()

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

private

Definition at line 1043 of file Andersen.cpp.

AnalyzeIOBarrier()

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

private

Definition at line 1146 of file Andersen.cpp.

AnalyzeLambda()

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

private

Definition at line 1188 of file Andersen.cpp.

AnalyzeLoad()

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

private

Definition at line 768 of file Andersen.cpp.

AnalyzeMalloc()

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

private

Definition at line 755 of file Andersen.cpp.

AnalyzeMemcpy()

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

private

Definition at line 949 of file Andersen.cpp.

AnalyzeMemset()

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

private

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

AnalyzePhi()

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

private

Definition at line 1260 of file Andersen.cpp.

AnalyzePointerToFunction()

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

private

Definition at line 1116 of file Andersen.cpp.

AnalyzePoison()

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

private

Definition at line 918 of file Andersen.cpp.

AnalyzePtrToInt()

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

private

Definition at line 880 of file Andersen.cpp.

AnalyzeRegion()

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

private

Definition at line 1386 of file Andersen.cpp.

AnalyzeRvsdg()

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

private

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

AnalyzeStructuralNode()

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

private

Definition at line 1161 of file Andersen.cpp.

AnalyzeTheta()

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

private

Definition at line 1343 of file Andersen.cpp.

AnalyzeUndef()

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

private

Definition at line 904 of file Andersen.cpp.

AnalyzeValist()

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

private

Definition at line 1095 of file Andersen.cpp.

ConstructPointsToGraphFromPointerObjectSet() [1/2]

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

static

Definition at line 1735 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 1640 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 1468 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 1462 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 1485 of file Andersen.cpp.

Member Data Documentation

Config_

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

private

Definition at line 466 of file Andersen.hpp.

Constraints_

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

private

Definition at line 469 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 468 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