#include <LoopStrengthReduction.hpp>

Inheritance diagram for jlm::llvm::LoopStrengthReduction:

Collaboration diagram for jlm::llvm::LoopStrengthReduction:

Classes
class	Context

class	Statistics

Public Member Functions
	~LoopStrengthReduction () noexcept override

	LoopStrengthReduction ()

	LoopStrengthReduction (const LoopStrengthReduction &)=delete

	LoopStrengthReduction (LoopStrengthReduction &&)=delete

LoopStrengthReduction &	operator= (const LoopStrengthReduction &)=delete

LoopStrengthReduction &	operator= (LoopStrengthReduction &&)=delete

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

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...

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

void	ReduceStrength (rvsdg::ThetaNode &thetaNode)

bool	ContainsMul (const rvsdg::Output &output)

bool	DependsOnInductionVariable (const rvsdg::Output &output)

bool	IsValidCandidateOperation (const rvsdg::Output &output, const rvsdg::SimpleOperation &operation)

void	ProcessOutput (rvsdg::Output &output, rvsdg::ThetaNode &thetaNode, util::HashSet< rvsdg::Output * > &candidateOperations, util::HashSet< rvsdg::Output * > &visited)

void	ReplaceCandidateOperation (rvsdg::Output &output, rvsdg::ThetaNode &thetaNode)

std::optional< rvsdg::Output * >	HoistChrec (const SCEVChainRecurrence &chrec, const rvsdg::ThetaNode &thetaNode, size_t numBits)

std::optional< rvsdg::Output * >	HoistSCEVExpresssion (const SCEV &scev, rvsdg::ThetaNode &thetaNode, size_t numBits)

std::optional< rvsdg::ThetaNode::LoopVar >	CreateNewGEPInductionVariable (const SCEVChainRecurrence &chrec, rvsdg::ThetaNode &thetaNode)

std::optional< rvsdg::ThetaNode::LoopVar >	CreateNewArithmeticInductionVariable (const SCEVChainRecurrence &chrec, rvsdg::ThetaNode &thetaNode, size_t numBits)

Private Attributes
std::unordered_map< const rvsdg::Output *, std::unique_ptr< SCEVChainRecurrence > >	ChrecMap_

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

std::unordered_map< const rvsdg::Output *, bool >	DependsOnIVMemo_

std::unordered_map< const rvsdg::Output *, bool >	ContainsMulMemo_

std::unique_ptr< Context >	Context_

Detailed Description

Definition at line 16 of file LoopStrengthReduction.hpp.

Constructor & Destructor Documentation

◆ ~LoopStrengthReduction()

jlm::llvm::LoopStrengthReduction::~LoopStrengthReduction ( )

overridedefaultnoexcept

◆ LoopStrengthReduction() [1/3]

jlm::llvm::LoopStrengthReduction::LoopStrengthReduction ( )

Definition at line 122 of file LoopStrengthReduction.cpp.

◆ LoopStrengthReduction() [2/3]

jlm::llvm::LoopStrengthReduction::LoopStrengthReduction ( const LoopStrengthReduction & )

delete

◆ LoopStrengthReduction() [3/3]

jlm::llvm::LoopStrengthReduction::LoopStrengthReduction ( LoopStrengthReduction && )

delete

Member Function Documentation

◆ ContainsMul()

bool jlm::llvm::LoopStrengthReduction::ContainsMul ( const rvsdg::Output & output )

private

Checks if the RVSDG subtree of the output contains an IntegerMulOperation or IntegerShlOperation (which we treat as multiplication by 2) somewhere in the tree.

Parameters

output The output to be checked

Returns: true if the subtree contains a multiplication operation, otherwise false.

Definition at line 723 of file LoopStrengthReduction.cpp.

◆ CreateNewArithmeticInductionVariable()

std::optional< rvsdg::ThetaNode::LoopVar > jlm::llvm::LoopStrengthReduction::CreateNewArithmeticInductionVariable	(	const SCEVChainRecurrence &	chrec,
		rvsdg::ThetaNode &	thetaNode,
		size_t	numBits
	)

private

Definition at line 518 of file LoopStrengthReduction.cpp.

◆ CreateNewGEPInductionVariable()

std::optional< rvsdg::ThetaNode::LoopVar > jlm::llvm::LoopStrengthReduction::CreateNewGEPInductionVariable	(	const SCEVChainRecurrence &	chrec,
		rvsdg::ThetaNode &	thetaNode
	)

private

Definition at line 586 of file LoopStrengthReduction.cpp.

◆ DependsOnInductionVariable()

bool jlm::llvm::LoopStrengthReduction::DependsOnInductionVariable ( const rvsdg::Output & output )

private

Checks if the operation depends on an induction variable. By induction variable we mean a loop variable that evolves in a predictable way, which is the same as checking if its chrec does not contain any SCEVUnknown or SCEVInit elements.

Parameters

output The output to be checked

Returns: true if the output depends on an induction variable, otherwise false.

Definition at line 689 of file LoopStrengthReduction.cpp.

◆ HoistChrec()

std::optional< rvsdg::Output * > jlm::llvm::LoopStrengthReduction::HoistChrec	(	const SCEVChainRecurrence &	chrec,
		const rvsdg::ThetaNode &	thetaNode,
		size_t	numBits
	)

private

Definition at line 310 of file LoopStrengthReduction.cpp.

◆ HoistSCEVExpresssion()

std::optional< rvsdg::Output * > jlm::llvm::LoopStrengthReduction::HoistSCEVExpresssion	(	const SCEV &	scev,
		rvsdg::ThetaNode &	thetaNode,
		size_t	numBits
	)

private

Definition at line 361 of file LoopStrengthReduction.cpp.

◆ IsValidCandidateOperation()

bool jlm::llvm::LoopStrengthReduction::IsValidCandidateOperation	(	const rvsdg::Output &	output,
		const rvsdg::SimpleOperation &	operation
	)

private

Definition at line 664 of file LoopStrengthReduction.cpp.

◆ operator=() [1/2]

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

delete

◆ operator=() [2/2]

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

delete

◆ ProcessOutput()

void jlm::llvm::LoopStrengthReduction::ProcessOutput	(	rvsdg::Output &	output,
		rvsdg::ThetaNode &	thetaNode,
		util::HashSet< rvsdg::Output * > &	candidateOperations,
		util::HashSet< rvsdg::Output * > &	visited
	)

private

Definition at line 225 of file LoopStrengthReduction.cpp.

◆ ProcessRegion()

void jlm::llvm::LoopStrengthReduction::ProcessRegion ( rvsdg::Region & region )

private

Definition at line 151 of file LoopStrengthReduction.cpp.

◆ ReduceStrength()

void jlm::llvm::LoopStrengthReduction::ReduceStrength ( rvsdg::ThetaNode & thetaNode )

private

Definition at line 171 of file LoopStrengthReduction.cpp.

◆ ReplaceCandidateOperation()

void jlm::llvm::LoopStrengthReduction::ReplaceCandidateOperation	(	rvsdg::Output &	output,
		rvsdg::ThetaNode &	thetaNode
	)

private

Definition at line 262 of file LoopStrengthReduction.cpp.

◆ Run()

void jlm::llvm::LoopStrengthReduction::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 129 of file LoopStrengthReduction.cpp.

Member Data Documentation

◆ ChrecMap_

std::unordered_map<const rvsdg::Output *, std::unique_ptr<SCEVChainRecurrence> > jlm::llvm::LoopStrengthReduction::ChrecMap_

private

Definition at line 95 of file LoopStrengthReduction.hpp.

◆ ContainsMulMemo_

std::unordered_map<const rvsdg::Output *, bool> jlm::llvm::LoopStrengthReduction::ContainsMulMemo_

private

Definition at line 98 of file LoopStrengthReduction.hpp.

◆ Context_

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

private

Definition at line 100 of file LoopStrengthReduction.hpp.

◆ DependsOnIVMemo_

std::unordered_map<const rvsdg::Output *, bool> jlm::llvm::LoopStrengthReduction::DependsOnIVMemo_

private

Definition at line 97 of file LoopStrengthReduction.hpp.

◆ SCEVMap_

std::unordered_map<const rvsdg::Output *, std::unique_ptr<SCEV> > jlm::llvm::LoopStrengthReduction::SCEVMap_

private

Definition at line 96 of file LoopStrengthReduction.hpp.

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

jlm/llvm/opt/LoopStrengthReduction.hpp
jlm/llvm/opt/LoopStrengthReduction.cpp

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ~LoopStrengthReduction()

◆ LoopStrengthReduction() [1/3]

◆ LoopStrengthReduction() [2/3]

◆ LoopStrengthReduction() [3/3]

Member Function Documentation

◆ ContainsMul()

◆ CreateNewArithmeticInductionVariable()

◆ CreateNewGEPInductionVariable()

◆ DependsOnInductionVariable()

◆ HoistChrec()

◆ HoistSCEVExpresssion()

◆ IsValidCandidateOperation()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ ProcessOutput()

◆ ProcessRegion()

◆ ReduceStrength()

◆ ReplaceCandidateOperation()

◆ Run()

Member Data Documentation

◆ ChrecMap_

◆ ContainsMulMemo_

◆ Context_

◆ DependsOnIVMemo_

◆ SCEVMap_