Invariant Value Redirection. More...

#include <InvariantValueRedirection.hpp>

Inheritance diagram for jlm::llvm::InvariantValueRedirection:

Collaboration diagram for jlm::llvm::InvariantValueRedirection:

Classes
struct	Configuration

class	Statistics

Public Member Functions
	~InvariantValueRedirection () override

	InvariantValueRedirection (Configuration configuration)

void	Run (rvsdg::RvsdgModule &module, 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, Configuration configuration)

Private Member Functions
void	redirectInRootRegion (rvsdg::Graph &rvsdg)

void	redirectInRegion (rvsdg::Region &region)

void	redirectInSubregions (rvsdg::StructuralNode &structuralNode)

Static Private Member Functions
static void	redirectGammaOutputs (rvsdg::GammaNode &gammaNode)

static void	redirectThetaOutputs (rvsdg::ThetaNode &thetaNode)

static void	redirectThetaGammaOutputs (rvsdg::ThetaNode &thetaNode)

static void	redirectCallOutputs (rvsdg::SimpleNode &callNode)

static void	redirectLoadMemoryStates (rvsdg::SimpleNode &loadNode)

Private Attributes
Configuration	configuration_ {}

Detailed Description

Invariant Value Redirection.

Invariant Value Redirection (IVR) redirects invariant edges around gamma, theta, call, and load nodes. It does this by diverting all users of invariant outputs to the origin of the respective inputs. In case of nested nodes, the transformation processes the innermost nodes first to ensure that the outputs of outer nodes are correctly identified as invariant. Moreover, IVR processes a lambda node before all the lambda's call nodes to ensure that the outputs of call nodes are correctly identified as invariant. Nodes that become dead throughout the transformation are pruned from a region.

Gamma output redirection

The output of a gamma node is considered invariant if all the corresponding region results are connected to the arguments of a single gamma input. All the users of a gamma output are diverted to the origin of this gamma input.

Theta output redirection

A loop variable is considered invariant if its post value is connected to its corresponding pre value. All the users of the loop variables' output are diverted to the origin of the corresponding input. See rvsdg::ThetaLoopVarIsInvariant() for more details.

Theta/gamma correlation redirection

If the theta node has a gamma node in its subregion and for both nodes the predicates correlate, then the theta node's loop variables can be redirected under certain conditions. The correlation of predicates means that either:

The theta node's predicate origin is an exit variable of the gamma node and the respective producers of the subregion results are control constants.
The producer of the theta node's predicate origin and the gamma node's predicate origin are the same rvsdg::MatchOperation node.

These conditions are sufficient to statically determine that either one of the two gamma node's subregions is only executed on loop repetition or loop exit.

A loop variable can now be redirected in the following cases:

If the loop variable's output is dead, then only the repetition value of the loop variable is of interest. This means that we can redirect the value from the respective entry variable of the gamma node's repetition subregion to the post value.
If the loop variable's pre value is dead, then only the exit value of the loop variable is of interest. This means that we can redirect the value from the respective entry variable of the gamma node's exit subregion to the post value.

Call output redirection

The output of a call node is considered invariant if the respective result of the corresponding lambda is connected to an argument of the lambda. All the users of a call output are diverted to the origin of the call input corresponding to the lambda argument. Invariant Value Redirection for call nodes works only on non-recursive direct calls as IVR needs to inspect the lambda body in order to determine whether a value is simply routed through the lambda.

Load memory state redirection

The memory states of a load node can be diverted to their respective input's origin if the loaded value output of the load node is dead.

Definition at line 81 of file InvariantValueRedirection.hpp.

Constructor & Destructor Documentation

◆ ~InvariantValueRedirection()

jlm::llvm::InvariantValueRedirection::~InvariantValueRedirection ( )

overridedefault

◆ InvariantValueRedirection()

jlm::llvm::InvariantValueRedirection::InvariantValueRedirection ( Configuration configuration )

inlineexplicit

Definition at line 97 of file InvariantValueRedirection.hpp.

Member Function Documentation

◆ createAndRun()

void jlm::llvm::InvariantValueRedirection::createAndRun	(	rvsdg::RvsdgModule &	rvsdgModule,
		Configuration	configuration
	)

static

Creates an instance of InvariantValueRedirection and invokes its Run() method.

Parameters

rvsdgModule	The RVSDG on which invariant value redirection is invoked on.
configuration	The configuration for the instance.

Definition at line 69 of file InvariantValueRedirection.cpp.

◆ redirectCallOutputs()

void jlm::llvm::InvariantValueRedirection::redirectCallOutputs ( rvsdg::SimpleNode & callNode )

staticprivate

Definition at line 282 of file InvariantValueRedirection.cpp.

◆ redirectGammaOutputs()

void jlm::llvm::InvariantValueRedirection::redirectGammaOutputs ( rvsdg::GammaNode & gammaNode )

staticprivate

Definition at line 190 of file InvariantValueRedirection.cpp.

◆ redirectInRegion()

void jlm::llvm::InvariantValueRedirection::redirectInRegion ( rvsdg::Region & region )

private

Definition at line 122 of file InvariantValueRedirection.cpp.

◆ redirectInRootRegion()

void jlm::llvm::InvariantValueRedirection::redirectInRootRegion ( rvsdg::Graph & rvsdg )

private

Definition at line 79 of file InvariantValueRedirection.cpp.

◆ redirectInSubregions()

void jlm::llvm::InvariantValueRedirection::redirectInSubregions ( rvsdg::StructuralNode & structuralNode )

private

Definition at line 177 of file InvariantValueRedirection.cpp.

◆ redirectLoadMemoryStates()

void jlm::llvm::InvariantValueRedirection::redirectLoadMemoryStates ( rvsdg::SimpleNode & loadNode )

staticprivate

Redirects the load node's users of the memory state outputs to the origins' of the respective memory state inputs, if the value output of the load node is dead.

Parameters

loadNode The load node for which the memory states are redirected.

Definition at line 402 of file InvariantValueRedirection.cpp.

◆ redirectThetaGammaOutputs()

void jlm::llvm::InvariantValueRedirection::redirectThetaGammaOutputs ( rvsdg::ThetaNode & thetaNode )

staticprivate

Redirects invariant loop variables from theta nodes of which thet predicate statically correlates with the predicate of a gamma node.

Parameters

thetaNode The rvsdg::ThetaNode of which the loop variables are redirected.

Definition at line 217 of file InvariantValueRedirection.cpp.

◆ redirectThetaOutputs()

void jlm::llvm::InvariantValueRedirection::redirectThetaOutputs ( rvsdg::ThetaNode & thetaNode )

staticprivate

Definition at line 202 of file InvariantValueRedirection.cpp.

◆ Run()

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

Member Data Documentation

◆ configuration_

Configuration jlm::llvm::InvariantValueRedirection::configuration_ {}

private

Definition at line 151 of file InvariantValueRedirection.hpp.

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

jlm/llvm/opt/InvariantValueRedirection.hpp
jlm/llvm/opt/InvariantValueRedirection.cpp

Classes

Public Member Functions

Static Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Gamma output redirection

Theta output redirection

Theta/gamma correlation redirection

Call output redirection

Load memory state redirection

Constructor & Destructor Documentation

◆ ~InvariantValueRedirection()

◆ InvariantValueRedirection()

Member Function Documentation

◆ createAndRun()

◆ redirectCallOutputs()

◆ redirectGammaOutputs()

◆ redirectInRegion()

◆ redirectInRootRegion()

◆ redirectInSubregions()

◆ redirectLoadMemoryStates()

◆ redirectThetaGammaOutputs()

◆ redirectThetaOutputs()

◆ Run()

Member Data Documentation

◆ configuration_