jlm::llvm::InvariantValueRedirection Class Reference

Invariant Value Redirection Optimization. More...

#include <InvariantValueRedirection.hpp>

Inheritance diagram for jlm::llvm::InvariantValueRedirection:

Collaboration diagram for jlm::llvm::InvariantValueRedirection:

Classes
class	Statistics

Public Member Functions
	~InvariantValueRedirection () override
	InvariantValueRedirection ()
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 Private Member Functions
static void	RedirectInRootRegion (rvsdg::Graph &rvsdg)
static void	RedirectInRegion (rvsdg::Region &region)
static void	RedirectInSubregions (rvsdg::StructuralNode &structuralNode)
static void	RedirectGammaOutputs (rvsdg::GammaNode &gammaNode)
static void	RedirectThetaOutputs (rvsdg::ThetaNode &thetaNode)
static void	redirectThetaGammaOutputs (rvsdg::ThetaNode &thetaNode)
static void	RedirectCallOutputs (rvsdg::SimpleNode &callNode)

Detailed Description

Invariant Value Redirection Optimization.

Invariant Value Redirection (IVR) redirects invariant edges around gamma, theta, and call nodes. It does this by diverting all users of invariant gamma and theta outputs to the origin of the respective gamma and theta inputs. For call nodes, it redirects all users of invariant call outputs to the origin of the respective call input. In case of nested nodes, the optimization 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.

Theta nodes

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.

Gamma nodes

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.

Call nodes

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.

Theta nodes with a predicate that correlates with a gamma node

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:

1. 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.
2. 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:

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

Definition at line 76 of file InvariantValueRedirection.hpp.

Constructor & Destructor Documentation

~InvariantValueRedirection()

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

overridedefault

InvariantValueRedirection()

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

inline

Definition at line 83 of file InvariantValueRedirection.hpp.

Member Function Documentation

RedirectCallOutputs()

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

staticprivate

Definition at line 253 of file InvariantValueRedirection.cpp.

RedirectGammaOutputs()

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

staticprivate

Definition at line 159 of file InvariantValueRedirection.cpp.

RedirectInRegion()

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

staticprivate

Definition at line 110 of file InvariantValueRedirection.cpp.

RedirectInRootRegion()

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

staticprivate

Definition at line 67 of file InvariantValueRedirection.cpp.

RedirectInSubregions()

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

staticprivate

Definition at line 146 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 188 of file InvariantValueRedirection.cpp.

RedirectThetaOutputs()

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

staticprivate

Definition at line 171 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 53 of file InvariantValueRedirection.cpp.

---

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

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