#include <ScalarEvolution.hpp>

Inheritance diagram for jlm::llvm::ScalarEvolution:

Collaboration diagram for jlm::llvm::ScalarEvolution:

Classes
class	Context

class	Statistics

Public Types
typedef util::HashSet< const rvsdg::Output * >	InductionVariableSet

typedef std::unordered_map< const rvsdg::Output , std::unordered_map< const rvsdg::Output , int > >	IVDependencyGraph

Public Member Functions
	~ScalarEvolution () noexcept override

	ScalarEvolution ()

	ScalarEvolution (const ScalarEvolution &)=delete

	ScalarEvolution (ScalarEvolution &&)=delete

ScalarEvolution &	operator= (const ScalarEvolution &)=delete

ScalarEvolution &	operator= (ScalarEvolution &&)=delete

void	Run (rvsdg::RvsdgModule &rvsdgModule, util::StatisticsCollector &statisticsCollector) override
	Perform RVSDG transformation. More...

std::unordered_map< const rvsdg::Output *, std::unique_ptr< SCEVChainRecurrence > >	PerformSCEVAnalysis (const rvsdg::ThetaNode &thetaNode)

Public Member Functions inherited from jlm::rvsdg::Transformation
virtual	~Transformation () noexcept

	Transformation (std::string_view Name)

const std::string_view &	GetName () const noexcept

void	Run (RvsdgModule &module)
	Perform RVSDG transformation. More...

Static Public Member Functions
static bool	StructurallyEqual (const SCEV &a, const SCEV &b)

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

std::unique_ptr< SCEV >	GetOrCreateSCEVForOutput (const rvsdg::Output &output)

std::optional< const SCEV * >	TryGetSCEVForOutput (const rvsdg::Output &output)

IVDependencyGraph	CreateDependencyGraph (const rvsdg::ThetaNode &thetaNode) const

std::unique_ptr< SCEVChainRecurrence >	CreateChainRecurrence (const rvsdg::Output &IV, const SCEV &scevTree, const rvsdg::ThetaNode &thetaNode)

Static Private Member Functions
static std::unordered_map< const rvsdg::Output *, int >	FindDependenciesForSCEV (const SCEV &currentSCEV, const rvsdg::Output &currentIV)

static std::vector< const rvsdg::Output * >	TopologicalSort (const IVDependencyGraph &dependencyGraph)

static std::unique_ptr< SCEV >	ApplyFolding (SCEV lhsOperand, SCEV rhsOperand)

static bool	IsValidInductionVariable (const rvsdg::Output &variable, IVDependencyGraph &dependencyGraph)

static bool	IsUnknown (const SCEVChainRecurrence &chrec)

static bool	HasCycleThroughOthers (const rvsdg::Output &currentIV, const rvsdg::Output &originalIV, IVDependencyGraph &dependencyGraph, std::unordered_set< const rvsdg::Output * > &visited, std::unordered_set< const rvsdg::Output * > &recursionStack)

Private Attributes
std::unordered_map< const rvsdg::ThetaNode *, InductionVariableSet >	InductionVariableMap_

std::unordered_map< const rvsdg::Output *, std::unique_ptr< SCEV > >	UniqueSCEVs_

std::unordered_map< const rvsdg::Output *, std::unique_ptr< SCEVChainRecurrence > >	ChainRecurrenceMap_

std::unique_ptr< Context >	Context_

Detailed Description

Definition at line 358 of file ScalarEvolution.hpp.

Member Typedef Documentation

◆ InductionVariableSet

typedef util::HashSet<const rvsdg::Output *> jlm::llvm::ScalarEvolution::InductionVariableSet

Definition at line 365 of file ScalarEvolution.hpp.

◆ IVDependencyGraph

typedef std::unordered_map<const rvsdg::Output *, std::unordered_map<const rvsdg::Output *, int> > jlm::llvm::ScalarEvolution::IVDependencyGraph

Definition at line 369 of file ScalarEvolution.hpp.

Constructor & Destructor Documentation

◆ ~ScalarEvolution()

jlm::llvm::ScalarEvolution::~ScalarEvolution ( )

overridedefaultnoexcept

◆ ScalarEvolution() [1/3]

jlm::llvm::ScalarEvolution::ScalarEvolution ( )

Definition at line 129 of file ScalarEvolution.cpp.

◆ ScalarEvolution() [2/3]

jlm::llvm::ScalarEvolution::ScalarEvolution ( const ScalarEvolution & )

delete

◆ ScalarEvolution() [3/3]

jlm::llvm::ScalarEvolution::ScalarEvolution ( ScalarEvolution && )

delete

Member Function Documentation

◆ AnalyzeRegion()

void jlm::llvm::ScalarEvolution::AnalyzeRegion ( const rvsdg::Region & region )

private

Definition at line 166 of file ScalarEvolution.cpp.

◆ ApplyFolding()

std::unique_ptr< SCEV > jlm::llvm::ScalarEvolution::ApplyFolding	(	SCEV *	lhsOperand,
		SCEV *	rhsOperand
	)

staticprivate

Definition at line 535 of file ScalarEvolution.cpp.

◆ CreateChainRecurrence()

std::unique_ptr< SCEVChainRecurrence > jlm::llvm::ScalarEvolution::CreateChainRecurrence	(	const rvsdg::Output &	IV,
		const SCEV &	scevTree,
		const rvsdg::ThetaNode &	thetaNode
	)

private

Definition at line 471 of file ScalarEvolution.cpp.

◆ CreateDependencyGraph()

ScalarEvolution::IVDependencyGraph jlm::llvm::ScalarEvolution::CreateDependencyGraph ( const rvsdg::ThetaNode & thetaNode ) const

private

Definition at line 284 of file ScalarEvolution.cpp.

◆ FindDependenciesForSCEV()

std::unordered_map< const rvsdg::Output *, int > jlm::llvm::ScalarEvolution::FindDependenciesForSCEV	(	const SCEV &	currentSCEV,
		const rvsdg::Output &	currentIV
	)

staticprivate

Definition at line 250 of file ScalarEvolution.cpp.

◆ GetOrCreateSCEVForOutput()

std::unique_ptr< SCEV > jlm::llvm::ScalarEvolution::GetOrCreateSCEVForOutput ( const rvsdg::Output & output )

private

Definition at line 204 of file ScalarEvolution.cpp.

◆ HasCycleThroughOthers()

bool jlm::llvm::ScalarEvolution::HasCycleThroughOthers	(	const rvsdg::Output &	currentIV,
		const rvsdg::Output &	originalIV,
		IVDependencyGraph &	dependencyGraph,
		std::unordered_set< const rvsdg::Output * > &	visited,
		std::unordered_set< const rvsdg::Output * > &	recursionStack
	)

staticprivate

Definition at line 655 of file ScalarEvolution.cpp.

◆ IsUnknown()

bool jlm::llvm::ScalarEvolution::IsUnknown ( const SCEVChainRecurrence & chrec )

staticprivate

Checks the operands of the given chrec to see if any of them are unknown.

Parameters

chrec the chain recurrence to be checked

Returns: true if the recurrence contains an unknown, false otherwise

Definition at line 153 of file ScalarEvolution.cpp.

◆ IsValidInductionVariable()

bool jlm::llvm::ScalarEvolution::IsValidInductionVariable	(	const rvsdg::Output &	variable,
		IVDependencyGraph &	dependencyGraph
	)

staticprivate

Definition at line 640 of file ScalarEvolution.cpp.

◆ operator=() [1/2]

ScalarEvolution& jlm::llvm::ScalarEvolution::operator= ( const ScalarEvolution & )

delete

◆ operator=() [2/2]

ScalarEvolution& jlm::llvm::ScalarEvolution::operator= ( ScalarEvolution && )

delete

◆ PerformSCEVAnalysis()

std::unordered_map< const rvsdg::Output *, std::unique_ptr< SCEVChainRecurrence > > jlm::llvm::ScalarEvolution::PerformSCEVAnalysis ( const rvsdg::ThetaNode & thetaNode )

Definition at line 366 of file ScalarEvolution.cpp.

◆ Run()

void jlm::llvm::ScalarEvolution::Run	(	rvsdg::RvsdgModule &	module,
		util::StatisticsCollector &	statisticsCollector
	)

overridevirtual

Perform RVSDG transformation.

Note: This method is expected to be called multiple times. An implementation is required to reset the objects' internal state to ensure correct behavior after every invocation.

Parameters

module	RVSDG module the transformation is performed on.
statisticsCollector	Statistics collector for collecting transformation statistics.

Implements jlm::rvsdg::Transformation.

Definition at line 136 of file ScalarEvolution.cpp.

◆ StructurallyEqual()

bool jlm::llvm::ScalarEvolution::StructurallyEqual	(	const SCEV &	a,
		const SCEV &	b
	)

static

Definition at line 690 of file ScalarEvolution.cpp.

◆ TopologicalSort()

std::vector< const rvsdg::Output * > jlm::llvm::ScalarEvolution::TopologicalSort ( const IVDependencyGraph & dependencyGraph )

staticprivate

Definition at line 303 of file ScalarEvolution.cpp.

◆ TryGetSCEVForOutput()

std::optional< const SCEV * > jlm::llvm::ScalarEvolution::TryGetSCEVForOutput ( const rvsdg::Output & output )

private

Definition at line 196 of file ScalarEvolution.cpp.

Member Data Documentation

◆ ChainRecurrenceMap_

std::unordered_map<const rvsdg::Output *, std::unique_ptr<SCEVChainRecurrence> > jlm::llvm::ScalarEvolution::ChainRecurrenceMap_

private

Definition at line 398 of file ScalarEvolution.hpp.

◆ Context_

std::unique_ptr<Context> jlm::llvm::ScalarEvolution::Context_

private

Definition at line 447 of file ScalarEvolution.hpp.

◆ InductionVariableMap_

std::unordered_map<const rvsdg::ThetaNode *, InductionVariableSet> jlm::llvm::ScalarEvolution::InductionVariableMap_

private

Definition at line 395 of file ScalarEvolution.hpp.

◆ UniqueSCEVs_

std::unordered_map<const rvsdg::Output *, std::unique_ptr<SCEV> > jlm::llvm::ScalarEvolution::UniqueSCEVs_

private

Definition at line 396 of file ScalarEvolution.hpp.

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

jlm/llvm/opt/ScalarEvolution.hpp
jlm/llvm/opt/ScalarEvolution.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ InductionVariableSet

◆ IVDependencyGraph

Constructor & Destructor Documentation

◆ ~ScalarEvolution()

◆ ScalarEvolution() [1/3]

◆ ScalarEvolution() [2/3]

◆ ScalarEvolution() [3/3]

Member Function Documentation

◆ AnalyzeRegion()

◆ ApplyFolding()

◆ CreateChainRecurrence()

◆ CreateDependencyGraph()

◆ FindDependenciesForSCEV()

◆ GetOrCreateSCEVForOutput()

◆ HasCycleThroughOthers()

◆ IsUnknown()

◆ IsValidInductionVariable()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ PerformSCEVAnalysis()

◆ Run()

◆ StructurallyEqual()

◆ TopologicalSort()

◆ TryGetSCEVForOutput()

Member Data Documentation

◆ ChainRecurrenceMap_

◆ Context_

◆ InductionVariableMap_

◆ UniqueSCEVs_