#include <ScalarEvolution.hpp>

Inheritance diagram for jlm::llvm::ScalarEvolution:

Collaboration diagram for jlm::llvm::ScalarEvolution:

Classes
class	Context

struct	DependencyInfo

class	Statistics

Public Types
enum class	DependencyOp { Add , Mul , None }

typedef std::unordered_map< rvsdg::Output *, DependencyInfo >	DependencyMap

typedef std::unordered_map< rvsdg::Output *, DependencyMap >	DependencyGraph

Public Member Functions
	~ScalarEvolution () noexcept override

	ScalarEvolution ()

	ScalarEvolution (const ScalarEvolution &)=delete

	ScalarEvolution (ScalarEvolution &&)=delete

ScalarEvolution &	operator= (const ScalarEvolution &)=delete

ScalarEvolution &	operator= (ScalarEvolution &&)=delete

std::unordered_map< const rvsdg::Output *, std::unique_ptr< SCEVChainRecurrence > >	GetChrecMap () const

std::unordered_map< const rvsdg::Output *, std::unique_ptr< SCEV > >	GetSCEVMap () const

std::unordered_map< const rvsdg::ThetaNode *, size_t >	GetTripCountMap () const noexcept

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

std::optional< size_t >	GetPredictedTripCount (rvsdg::ThetaNode &thetaNode)

void	AnalyzeRegion (rvsdg::Region &region)

void	CombineChrecsAcrossLoops ()

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.

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

static bool	IsUnknown (const SCEV &scev)

Private Member Functions
std::unique_ptr< SCEV >	GetOrCreateSCEVForOutput (rvsdg::Output &output)

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

void	PerformSCEVAnalysis (rvsdg::ThetaNode &thetaNode)

std::unique_ptr< SCEV >	ComputeSCEVForGepInnerOffset (const rvsdg::SimpleNode &gepNode, size_t inputIndex, const rvsdg::Type &type)

std::optional< std::unique_ptr< SCEV > >	TryReplaceInitForSCEV (const SCEV &scev, rvsdg::Output &output)

std::unique_ptr< SCEVChainRecurrence >	GetOrCreateChainRecurrence (rvsdg::Output &output, const SCEV &scev, rvsdg::ThetaNode &thetaNode)

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

Static Private Member Functions
static std::optional< size_t >	ComputeBackedgeTakenCountForChrec (const SCEVChainRecurrence &chrec, int64_t bound, const rvsdg::SimpleOperation *comparisonOperation)

static std::optional< size_t >	SolveQuadraticEquation (int64_t a, int64_t b, int64_t c)
	Tries to find a solution to the quadratic equation a^2 x + b x + c = 0 using integer arithmetic.

static bool	IsStepNegative (const SCEV &stepSCEV)

static bool	IsStepPositive (const SCEV &stepSCEV)

static bool	IsStepZero (const SCEV &stepSCEV)

static std::unique_ptr< SCEV >	GetNegativeSCEV (const SCEV &scev)

static void	FindDependenciesForSCEV (const SCEV &scev, DependencyMap &dependencies, DependencyOp op)

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

static std::unique_ptr< SCEV >	ApplyAddFolding (SCEV lhsOperand, SCEV rhsOperand, rvsdg::Output &output)
	Apply folding rules for addition to combine two SCEV operands into one.

static std::unique_ptr< SCEVChainRecurrence >	ComputeProductOfChrecs (SCEVChainRecurrence lhsChrec, SCEVChainRecurrence rhsChrec, rvsdg::Output &output)

static std::unique_ptr< SCEV >	ApplyMulFolding (SCEV lhsOperand, SCEV rhsOperand, rvsdg::Output &output)
	Apply folding rules for multiplication to combine two SCEV operands into one.

static std::unique_ptr< SCEV >	FoldNAryExpression (SCEVNAryExpr &expression, rvsdg::Output &output)
	Try to combine the constants in an n-ary expression (Add or Mul) into themselves.

static bool	CanCreateChainRecurrence (rvsdg::Output &output, DependencyGraph &dependencyGraph)

static bool	HasCycleThroughOthers (rvsdg::Output &currentOutput, const rvsdg::Output &originalOutput, DependencyGraph &dependencyGraph, std::unordered_set< const rvsdg::Output * > &visited, std::unordered_set< const rvsdg::Output * > &recursionStack)

Private Attributes
std::unique_ptr< Context >	Context_

Detailed Description

Definition at line 575 of file ScalarEvolution.hpp.

Member Typedef Documentation

◆ DependencyGraph

typedef std::unordered_map<rvsdg::Output *, DependencyMap> jlm::llvm::ScalarEvolution::DependencyGraph

Definition at line 604 of file ScalarEvolution.hpp.

◆ DependencyMap

typedef std::unordered_map<rvsdg::Output *, DependencyInfo> jlm::llvm::ScalarEvolution::DependencyMap

Definition at line 602 of file ScalarEvolution.hpp.

Member Enumeration Documentation

◆ DependencyOp

enum class jlm::llvm::ScalarEvolution::DependencyOp

strong

Enumerator
Add
Mul
None

Definition at line 581 of file ScalarEvolution.hpp.

Constructor & Destructor Documentation

◆ ~ScalarEvolution()

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

overridedefaultnoexcept

◆ ScalarEvolution() [1/3]

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

Definition at line 236 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 ( rvsdg::Region & region )

Definition at line 288 of file ScalarEvolution.cpp.

◆ ApplyAddFolding()

std::unique_ptr< SCEV > jlm::llvm::ScalarEvolution::ApplyAddFolding	(	SCEV *	lhsOperand,
		SCEV *	rhsOperand,
		rvsdg::Output &	output
	)

staticprivate

Apply folding rules for addition to combine two SCEV operands into one.

Parameters

lhsOperand	The left-hand side operand of the add operation
rhsOperand	The right-hand side operand of the add operation
output	The output of the addition operation we are folding.

Returns: A unique ptr to the new operand

Definition at line 1343 of file ScalarEvolution.cpp.

◆ ApplyMulFolding()

std::unique_ptr< SCEV > jlm::llvm::ScalarEvolution::ApplyMulFolding	(	SCEV *	lhsOperand,
		SCEV *	rhsOperand,
		rvsdg::Output &	output
	)

staticprivate

Apply folding rules for multiplication to combine two SCEV operands into one.

Parameters

lhsOperand	The left-hand side operand of the mul operation
rhsOperand	The right-hand side operand of the mul operation
output	The output of the multiplication operation we are folding

Returns: A unique ptr to the new operand

Definition at line 1700 of file ScalarEvolution.cpp.

◆ CanCreateChainRecurrence()

bool jlm::llvm::ScalarEvolution::CanCreateChainRecurrence	(	rvsdg::Output &	output,
		DependencyGraph &	dependencyGraph
	)

staticprivate

Checks the dependencies of the input variable to determine if we can create a chain recurrence using it's SCEV.

The requirements are:

No more than one self-dependency (indicates a self-dependent variable)
No cyclic dependencies (A depends on B and B depends on A)
No dependencies via multiplication (results in a geometric update sequence, which we treat as an invalid induction variable)

Parameters

output	The output to check.
dependencyGraph	The dependency graph which stores the dependencies of all outputs in the loop.

Returns: True if the requirements are fulfilled, false otherwise.

Definition at line 1918 of file ScalarEvolution.cpp.

◆ CombineChrecsAcrossLoops()

void jlm::llvm::ScalarEvolution::CombineChrecsAcrossLoops ( )

Goes through all chain recurrences stored in the context (across different loops), and stitches them together wherever possible.

Definition at line 768 of file ScalarEvolution.cpp.

◆ ComputeBackedgeTakenCountForChrec()

std::optional< size_t > jlm::llvm::ScalarEvolution::ComputeBackedgeTakenCountForChrec	(	const SCEVChainRecurrence &	chrec,
		int64_t	bound,
		const rvsdg::SimpleOperation *	comparisonOperation
	)

staticprivate

Tries to compute the number of times the backedge is taken in a loop where the condition for the predicate checks whether the variable described by chrec satisfies the comparison operation when compared to the bound.

Figuring out the number of times the backedge is taken can be equivalently expressed as: "At which iteration does the loop condition become false?" That’s naturally expressed as: f(i) - k changes sign, where f(i) is the value of the recurrence at iteration i and k is the bound value

Parameters

chrec	The chain recurrence to compare with the bound.
bound	The compare value for the operation.
comparisonOperation	The comparison operation that is used in the predicate of the loop.

Returns: The backedge taken count, or std::nullopt if the count cannot be computed or the loop does not terminate.

Definition at line 607 of file ScalarEvolution.cpp.

◆ ComputeProductOfChrecs()

std::unique_ptr< SCEVChainRecurrence > jlm::llvm::ScalarEvolution::ComputeProductOfChrecs	(	SCEVChainRecurrence *	lhsChrec,
		SCEVChainRecurrence *	rhsChrec,
		rvsdg::Output &	output
	)

staticprivate

Definition at line 1586 of file ScalarEvolution.cpp.

◆ ComputeSCEVForGepInnerOffset()

std::unique_ptr< SCEV > jlm::llvm::ScalarEvolution::ComputeSCEVForGepInnerOffset	(	const rvsdg::SimpleNode &	gepNode,
		size_t	inputIndex,
		const rvsdg::Type &	type
	)

private

Definition at line 1052 of file ScalarEvolution.cpp.

◆ CreateDependencyGraph()

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

private

Definition at line 1131 of file ScalarEvolution.cpp.

◆ FindDependenciesForSCEV()

void jlm::llvm::ScalarEvolution::FindDependenciesForSCEV	(	const SCEV &	scev,
		DependencyMap &	dependencies,
		DependencyOp	op = `DependencyOp::None`
	)

staticprivate

Definition at line 1101 of file ScalarEvolution.cpp.

◆ FoldNAryExpression()

std::unique_ptr< SCEV > jlm::llvm::ScalarEvolution::FoldNAryExpression	(	SCEVNAryExpr &	expression,
		rvsdg::Output &	output
	)

staticprivate

Try to combine the constants in an n-ary expression (Add or Mul) into themselves.

Parameters

expression	The expression to be folded
output	The output of the operation the n-ary expression represents

Returns: The unique ptr to the expression

Definition at line 1291 of file ScalarEvolution.cpp.

◆ GetChrecMap()

std::unordered_map< const rvsdg::Output *, std::unique_ptr< SCEVChainRecurrence > > jlm::llvm::ScalarEvolution::GetChrecMap ( ) const

Returns a copy of the chrec map containing the computed chain recurrences after running the analysis.

Definition at line 243 of file ScalarEvolution.cpp.

◆ GetNegativeSCEV()

std::unique_ptr< SCEV > jlm::llvm::ScalarEvolution::GetNegativeSCEV ( const SCEV & scev )

staticprivate

Definition at line 1885 of file ScalarEvolution.cpp.

◆ GetOrCreateChainRecurrence()

std::unique_ptr< SCEVChainRecurrence > jlm::llvm::ScalarEvolution::GetOrCreateChainRecurrence	(	rvsdg::Output &	output,
		const SCEV &	scev,
		rvsdg::ThetaNode &	thetaNode
	)

private

Definition at line 1211 of file ScalarEvolution.cpp.

◆ GetOrCreateSCEVForOutput()

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

private

Definition at line 944 of file ScalarEvolution.cpp.

◆ GetOrCreateStepForSCEV()

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

private

Definition at line 1244 of file ScalarEvolution.cpp.

◆ GetPredictedTripCount()

std::optional< size_t > jlm::llvm::ScalarEvolution::GetPredictedTripCount ( rvsdg::ThetaNode & thetaNode )

Definition at line 401 of file ScalarEvolution.cpp.

◆ GetSCEVMap()

std::unordered_map< const rvsdg::Output *, std::unique_ptr< SCEV > > jlm::llvm::ScalarEvolution::GetSCEVMap ( ) const

Returns a copy of the scev map containing the computed scev trees after running the analysis.

Definition at line 254 of file ScalarEvolution.cpp.

◆ GetTripCountMap()

std::unordered_map< const rvsdg::ThetaNode *, size_t > jlm::llvm::ScalarEvolution::GetTripCountMap ( ) const

noexcept

Definition at line 265 of file ScalarEvolution.cpp.

◆ HasCycleThroughOthers()

bool jlm::llvm::ScalarEvolution::HasCycleThroughOthers	(	rvsdg::Output &	currentOutput,
		const rvsdg::Output &	originalOutput,
		DependencyGraph &	dependencyGraph,
		std::unordered_set< const rvsdg::Output * > &	visited,
		std::unordered_set< const rvsdg::Output * > &	recursionStack
	)

staticprivate

Definition at line 1943 of file ScalarEvolution.cpp.

◆ IsStepNegative()

bool jlm::llvm::ScalarEvolution::IsStepNegative ( const SCEV & stepSCEV )

staticprivate

Definition at line 323 of file ScalarEvolution.cpp.

◆ IsStepPositive()

bool jlm::llvm::ScalarEvolution::IsStepPositive ( const SCEV & stepSCEV )

staticprivate

Definition at line 349 of file ScalarEvolution.cpp.

◆ IsStepZero()

bool jlm::llvm::ScalarEvolution::IsStepZero ( const SCEV & stepSCEV )

staticprivate

Definition at line 375 of file ScalarEvolution.cpp.

◆ IsUnknown()

bool jlm::llvm::ScalarEvolution::IsUnknown ( const SCEV & scev )

static

Checks if the given scev is or contains a SCEVUnknown.

Parameters

scev	the SCEV expression to be checked

Returns: true if the SCEV contains or is unknown, false otherwise

Definition at line 1978 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()

void jlm::llvm::ScalarEvolution::PerformSCEVAnalysis ( rvsdg::ThetaNode & thetaNode )

private

Definition at line 867 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 271 of file ScalarEvolution.cpp.

◆ SolveQuadraticEquation()

std::optional< size_t > jlm::llvm::ScalarEvolution::SolveQuadraticEquation	(	int64_t	a,
		int64_t	b,
		int64_t	c
	)

staticprivate

Tries to find a solution to the quadratic equation a^2 x + b x + c = 0 using integer arithmetic.

Credit to the SolveQuadraticEquationWrap() method in the LLVM APInt.cpp file (https://llvm.org/doxygen/APInt_8cpp_source.html#l02823) for the general approach.

Returns: A solution to the equation which is greater than zero, or std::nullopt if none can be found

Definition at line 696 of file ScalarEvolution.cpp.

◆ StructurallyEqual()

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

static

Definition at line 2008 of file ScalarEvolution.cpp.

◆ TopologicalSort()

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

staticprivate

Definition at line 1158 of file ScalarEvolution.cpp.

◆ TryReplaceInitForSCEV()

std::optional< std::unique_ptr< SCEV > > jlm::llvm::ScalarEvolution::TryReplaceInitForSCEV	(	const SCEV &	scev,
		rvsdg::Output &	output
	)

private

Recursively traverses chain recurrences to find Init nodes that can be replaced with their (now computed) corresponding chain recurrences and replaces them

Parameters

scev	The SCEV expression to be traversed
output	The output of the operation the SCEV represents

Returns: The resulting recurrence, or std::nullopt if no change was made

Definition at line 803 of file ScalarEvolution.cpp.

Member Data Documentation

◆ Context_

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

private

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

◆ DependencyGraph

◆ DependencyMap

Member Enumeration Documentation

◆ DependencyOp

Constructor & Destructor Documentation

◆ ~ScalarEvolution()

◆ ScalarEvolution() [1/3]

◆ ScalarEvolution() [2/3]

◆ ScalarEvolution() [3/3]

Member Function Documentation

◆ AnalyzeRegion()

◆ ApplyAddFolding()

◆ ApplyMulFolding()

◆ CanCreateChainRecurrence()

◆ CombineChrecsAcrossLoops()

◆ ComputeBackedgeTakenCountForChrec()

◆ ComputeProductOfChrecs()

◆ ComputeSCEVForGepInnerOffset()

◆ CreateDependencyGraph()

◆ FindDependenciesForSCEV()

◆ FoldNAryExpression()

◆ GetChrecMap()

◆ GetNegativeSCEV()

◆ GetOrCreateChainRecurrence()

◆ GetOrCreateSCEVForOutput()

◆ GetOrCreateStepForSCEV()

◆ GetPredictedTripCount()

◆ GetSCEVMap()

◆ GetTripCountMap()

◆ HasCycleThroughOthers()

◆ IsStepNegative()

◆ IsStepPositive()

◆ IsStepZero()

◆ IsUnknown()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ PerformSCEVAnalysis()

◆ Run()

◆ SolveQuadraticEquation()

◆ StructurallyEqual()

◆ TopologicalSort()

◆ TryReplaceInitForSCEV()

Member Data Documentation

◆ Context_