#include <LoopUnswitching.hpp>

Inheritance diagram for jlm::llvm::LoopUnswitching:

Collaboration diagram for jlm::llvm::LoopUnswitching:

Classes
class	Statistics

Public Member Functions
	~LoopUnswitching () noexcept override

	LoopUnswitching (std::shared_ptr< const LoopUnswitchingHeuristic > heuristic)

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

Static Public Member Functions
static void	CreateAndRun (rvsdg::RvsdgModule &rvsdgModule, util::StatisticsCollector &statisticsCollector, std::shared_ptr< const LoopUnswitchingHeuristic > heuristic)

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

bool	UnswitchLoop (rvsdg::ThetaNode &thetaNode)

Static Private Member Functions
static rvsdg::GammaNode *	IsUnswitchable (const rvsdg::ThetaNode &thetaNode)

static void	SinkNodesIntoGamma (rvsdg::GammaNode &gammaNode, const rvsdg::ThetaNode &thetaNode)

static std::vector< std::vector< rvsdg::Node * > >	CollectPredicateNodes (const rvsdg::ThetaNode &thetaNode, const rvsdg::GammaNode &gammaNode)

static void	CopyPredicateNodes (rvsdg::Region &target, rvsdg::SubstitutionMap &substitutionMap, const std::vector< std::vector< rvsdg::Node * >> &nodes)

static bool	allLoopVarsAreRoutedThroughGamma (const rvsdg::ThetaNode &thetaNode, const rvsdg::GammaNode &gammaNode)

Private Attributes
std::shared_ptr< const LoopUnswitchingHeuristic >	heuristic_

Detailed Description

LoopUnswitching.

Loop unswitching transforms a theta node with a gamma node in its subregion to a gamma node that contains a theta node in one of its subregions, avoiding the conditional in every loop iteration.

The pass transforms the following graph:

theta
P

| -—|— | | | | | | | —|-----------------------------------------------— |

		gamma
		X	R
		_________________________	__________________________

| | | |__|____________________________________________________________|

to the following graph: P | -—|---------------------------------------------------------— | gamma | | | | ----------------------------------— |

		theta
		R


		P

| | | | | | | | |_____|_____________________________| | | | | |______________________|________________________________________|

*X*

where

P is the predicate subgraph, i.e., all nodes that are responsible for computing the predicate of the theta and gamma node. The theta and gamma node must have the same predicate for the transformation to occur.
X is the exit subregion. It denotes the region that is executed once the predicate evaluates to false and the loop is exited.
R is the repetition subregion. It denotes the region that is executed if the predicate evaluates to true the loop is repeated.

The predicate subgraph P is duplicated as part of the transformation.

Definition at line 107 of file LoopUnswitching.hpp.

Constructor & Destructor Documentation

◆ ~LoopUnswitching()

jlm::llvm::LoopUnswitching::~LoopUnswitching ( )

overridedefaultnoexcept

◆ LoopUnswitching()

jlm::llvm::LoopUnswitching::LoopUnswitching ( std::shared_ptr< const LoopUnswitchingHeuristic > heuristic )

inlineexplicit

Definition at line 114 of file LoopUnswitching.hpp.

Member Function Documentation

◆ allLoopVarsAreRoutedThroughGamma()

bool jlm::llvm::LoopUnswitching::allLoopVarsAreRoutedThroughGamma	(	const rvsdg::ThetaNode &	thetaNode,
		const rvsdg::GammaNode &	gammaNode
	)

staticprivate

Checks that the post-values from all loop variables are originating from gammaNode.

Parameters

thetaNode	The theta node for which to perform the check.
gammaNode	The gamma node through which all loop variables need to be routed.

Returns: True, if all post-values originate from gammaNode, otherwise false.

Definition at line 187 of file LoopUnswitching.cpp.

◆ CollectPredicateNodes()

std::vector< std::vector< rvsdg::Node * > > jlm::llvm::LoopUnswitching::CollectPredicateNodes	(	const rvsdg::ThetaNode &	thetaNode,
		const rvsdg::GammaNode &	gammaNode
	)

staticprivate

Definition at line 150 of file LoopUnswitching.cpp.

◆ CopyPredicateNodes()

void jlm::llvm::LoopUnswitching::CopyPredicateNodes	(	rvsdg::Region &	target,
		rvsdg::SubstitutionMap &	substitutionMap,
		const std::vector< std::vector< rvsdg::Node * >> &	nodes
	)

staticprivate

Definition at line 174 of file LoopUnswitching.cpp.

◆ CreateAndRun()

void jlm::llvm::LoopUnswitching::CreateAndRun	(	rvsdg::RvsdgModule &	rvsdgModule,
		util::StatisticsCollector &	statisticsCollector,
		std::shared_ptr< const LoopUnswitchingHeuristic >	heuristic
	)

static

Definition at line 400 of file LoopUnswitching.cpp.

◆ HandleRegion()

void jlm::llvm::LoopUnswitching::HandleRegion ( rvsdg::Region & region )

private

Definition at line 358 of file LoopUnswitching.cpp.

◆ IsUnswitchable()

rvsdg::GammaNode * jlm::llvm::LoopUnswitching::IsUnswitchable ( const rvsdg::ThetaNode & thetaNode )

staticprivate

Definition at line 84 of file LoopUnswitching.cpp.

◆ Run()

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

◆ SinkNodesIntoGamma()

void jlm::llvm::LoopUnswitching::SinkNodesIntoGamma	(	rvsdg::GammaNode &	gammaNode,
		const rvsdg::ThetaNode &	thetaNode
	)

staticprivate

Definition at line 130 of file LoopUnswitching.cpp.

◆ UnswitchLoop()

bool jlm::llvm::LoopUnswitching::UnswitchLoop ( rvsdg::ThetaNode & thetaNode )

private

Definition at line 202 of file LoopUnswitching.cpp.

Member Data Documentation

◆ heuristic_

std::shared_ptr<const LoopUnswitchingHeuristic> jlm::llvm::LoopUnswitching::heuristic_

private

Definition at line 162 of file LoopUnswitching.hpp.

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

jlm/llvm/opt/LoopUnswitching.hpp
jlm/llvm/opt/LoopUnswitching.cpp

Classes

Public Member Functions

Static Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

The pass transforms the following graph:

Constructor & Destructor Documentation

◆ ~LoopUnswitching()

◆ LoopUnswitching()

Member Function Documentation

◆ allLoopVarsAreRoutedThroughGamma()

◆ CollectPredicateNodes()

◆ CopyPredicateNodes()

◆ CreateAndRun()

◆ HandleRegion()

◆ IsUnswitchable()

◆ Run()

◆ SinkNodesIntoGamma()

◆ UnswitchLoop()

Member Data Documentation

◆ heuristic_