#include <Trace.hpp>

Inheritance diagram for jlm::rvsdg::OutputTracer:

Collaboration diagram for jlm::rvsdg::OutputTracer:

[legend]

Classes
class	TraceStepResult

Public Types
enum class	StructuralNodePolicy { traceThroughTriviallyInvariant = 0 , traceThroughIfDetectedInvariant = 1 , traceIntoSubregions = 2 }

Public Member Functions
virtual	~OutputTracer ()

	OutputTracer () noexcept

StructuralNodePolicy	getStructuralNodePolicy () const noexcept

bool	isDeepInvarianceCheckingEnabled () const noexcept

bool	isTracingIntoSubregionsEnabled () const noexcept

void	setStructuralNodePolicy (StructuralNodePolicy value) noexcept

bool	isInterprocedural () const noexcept

void	setInterprocedural (bool value) noexcept

bool	isEnteringPhiNodes () const noexcept

void	setEnterPhiNodes (bool value) noexcept

bool	isRegionPredicateCheckingEnabled () const noexcept

void	setRegionPredicateCheckingEnabled (bool value) noexcept

bool	isInvarianceCachingEnabled () const noexcept

void	setInvarianceCaching (bool value) noexcept

void	clearInvarianceCache ()

Output &	trace (Output &output)

Output &	trace (Output &output, const Region *withinRegion)

Protected Types
enum class	BackEdgeState { NoBackEdgeTaken , PossiblyBackEdgeTaken }

Protected Member Functions
TraceStepResult	traceInternal (Output &output, BackEdgeState backEdgeState, const Region *withinRegion)

TraceStepResult	traceGammaOutput (GammaNode &gammaNode, Output &output, BackEdgeState backEdgeState)

TraceStepResult	traceThetaOutput (ThetaNode &thetaNode, Output &output, BackEdgeState backEdgeState)

TraceStepResult	traceThetaArgument (ThetaNode &thetaNode, Output &output)

virtual TraceStepResult	traceStep (Output &output, BackEdgeState backEdgeState, const Region *withinRegion)

Output &	insertInInvarianceCache (const Output &structuralOutput, Input &structuralInput)

Input *	lookupInInvarianceCache (const Output &structuralOutput)

Protected Attributes
StructuralNodePolicy	structuralNodePolicy_

bool	isInterprocedural_ = true

bool	enterPhiNodes_ = true

bool	enableRegionPredicateChecking_ = false

AlternativeRegionPredicateTracer	regionPredicateTracer_

const Output *	startingOutput_ = nullptr

bool	enableInvarianceCaching_ = false

std::unordered_map< const Output , Input >	invariantOutputCache_ {}

Detailed Description

Helper class for tracing through RVSDG graphs to find the origins of outputs. Traces through simple nodes that do not affect the value, through structural nodes when the value is invariant, and out of structural nodes when the value is passed in.

It supports caching of traced values at gamma and theta outputs to avoid the retracing of a value through these structural nodes.

Definition at line 26 of file Trace.hpp.

Member Enumeration Documentation

◆ BackEdgeState

enum class jlm::rvsdg::OutputTracer::BackEdgeState

strongprotected

Enumerator
NoBackEdgeTaken
PossiblyBackEdgeTaken

Definition at line 238 of file Trace.hpp.

◆ StructuralNodePolicy

enum class jlm::rvsdg::OutputTracer::StructuralNodePolicy

strong

Different policies for how to handle outputs of structural nodes during tracing. The policies are numbered such that a greater number means more effort is spent.

These policies only apply to gamma and theta nodes. For phi nodes, see isEnteringPhiNodes()

Enumerator
traceThroughTriviallyInvariant
traceThroughIfDetectedInvariant
traceIntoSubregions

Definition at line 36 of file Trace.hpp.

Constructor & Destructor Documentation

◆ ~OutputTracer()

jlm::rvsdg::OutputTracer::~OutputTracer ( )

virtualdefault

◆ OutputTracer()

jlm::rvsdg::OutputTracer::OutputTracer ( )

noexcept

Creates an OutputTracer with the default configuration

Definition at line 17 of file Trace.cpp.

Member Function Documentation

◆ clearInvarianceCache()

void jlm::rvsdg::OutputTracer::clearInvarianceCache ( )

inline

Clears the invariance cache.

This only needs to done if invariance caching is enabled.

See also: isInvarianceCachingEnabled()

It only needs to be done if either of the following happens:

structural outputs that were once invariant have their origin changed inside the structural node to make them no longer be invariant, or be invariant copies of a different structural input.
structural input and outputs are removed from the graph.

Definition at line 212 of file Trace.hpp.

◆ getStructuralNodePolicy()

StructuralNodePolicy jlm::rvsdg::OutputTracer::getStructuralNodePolicy ( ) const

inlinenoexcept

When tracing reaches the output of a structural node, how should the tracer continue.

See also: StructuralNodePolicy

Returns: the current structural node policy

Definition at line 71 of file Trace.hpp.

◆ insertInInvarianceCache()

Output & jlm::rvsdg::OutputTracer::insertInInvarianceCache	(	const Output &	structuralOutput,
		Input &	structuralInput
	)

protected

Inserts the given structuralOutput in the invariance cache. Invariance means that the structural output gets its value from one of the inputs of the structural node, so tracing can pass through the structural node without looking inside its subregions.

When determining invariance, it is important to not makse assumptions about tracing never having followed back-edges.

Parameters

structuralOutput	The structural output that was traced.
structuralInput	The corresponding structural input.

Returns: The origin of structuralInput for convenience.

Definition at line 416 of file Trace.cpp.

◆ isDeepInvarianceCheckingEnabled()

bool jlm::rvsdg::OutputTracer::isDeepInvarianceCheckingEnabled ( ) const

inlinenoexcept

Checks if the current StructuralNodePolicy allows checking for invariant outputs of structural nodes by performing tracing inside the subregion(s) of the node.

Returns: true if the policy allows deep invariance checking, false otherwise

Definition at line 83 of file Trace.hpp.

◆ isEnteringPhiNodes()

bool jlm::rvsdg::OutputTracer::isEnteringPhiNodes ( ) const

inlinenoexcept

Controls if tracing is allowed to enter the subregion of a phi node from its outputs. If true, tracing can go further and reach lambda or delta nodes inside of phi nodes. It does, however, mean that the result of tracing can end up inside a region that is not an ancestor of the starting region in the region tree.

Returns: true if tracing may enter phi nodes.

Definition at line 142 of file Trace.hpp.

◆ isInterprocedural()

bool jlm::rvsdg::OutputTracer::isInterprocedural ( ) const

inlinenoexcept

Controls if tracing is allowed to leave functions. If true, outputs can be traced out of functions via context arguments. If false, tracing stops if it reaches lambda context arguments.

Returns: true if interprocedural tracing is enabled.

Definition at line 118 of file Trace.hpp.

◆ isInvarianceCachingEnabled()

bool jlm::rvsdg::OutputTracer::isInvarianceCachingEnabled ( ) const

inlinenoexcept

Controls whether caching of structural output invariance is enabled, which can speed up tracing through deeply nested graphs.

It only caches outputs that are confirmed to be invariant, so outputs that change from variant to invariant will still be picked up. Outputs that change from invariant to variant need to trigger a manual cache invalidation.

See also: clearInvarianceCache().

Returns: true if structutal output invariance is cached, false otherwise.

Definition at line 182 of file Trace.hpp.

◆ isRegionPredicateCheckingEnabled()

bool jlm::rvsdg::OutputTracer::isRegionPredicateCheckingEnabled ( ) const

inlinenoexcept

Definition at line 159 of file Trace.hpp.

◆ isTracingIntoSubregionsEnabled()

bool jlm::rvsdg::OutputTracer::isTracingIntoSubregionsEnabled ( ) const

inlinenoexcept

Checks if the current StructuralNodePolicy allows tracing to enter subregions, and returning value origins that are inside subregions or sibling regions of the region where tracing started.

Returns: true if the policy allows tracing to enter subregions, false otherwise.

Definition at line 96 of file Trace.hpp.

◆ lookupInInvarianceCache()

Input * jlm::rvsdg::OutputTracer::lookupInInvarianceCache ( const Output & structuralOutput )

protected

Performs a lookup in the invariance cache.

Parameters

structuralOutput the output to look up in the cache.

Returns: the corresponding structural input the invariant output gets its value from.

Definition at line 428 of file Trace.cpp.

◆ setEnterPhiNodes()

void jlm::rvsdg::OutputTracer::setEnterPhiNodes ( bool value )

inlinenoexcept

Enables or disables tracing into phi nodes from the outside.

See also: isEnteringPhiNodes()

Parameters

value the new value

Definition at line 153 of file Trace.hpp.

◆ setInterprocedural()

void jlm::rvsdg::OutputTracer::setInterprocedural ( bool value )

inlinenoexcept

Enables or disables interprocedural tracing.

See also: isInterprocedural()

Parameters

value the new value

Definition at line 129 of file Trace.hpp.

◆ setInvarianceCaching()

void jlm::rvsdg::OutputTracer::setInvarianceCaching ( bool value )

inlinenoexcept

Enables or disables invariant structural output caching.

See also: isInvarianceCachingEnabled()

Parameters

value the new value

Definition at line 194 of file Trace.hpp.

◆ setRegionPredicateCheckingEnabled()

void jlm::rvsdg::OutputTracer::setRegionPredicateCheckingEnabled ( bool value )

inlinenoexcept

Definition at line 165 of file Trace.hpp.

◆ setStructuralNodePolicy()

void jlm::rvsdg::OutputTracer::setStructuralNodePolicy ( StructuralNodePolicy value )

inlinenoexcept

Sets the policy for how to trace when reaching outputs of structural nodes.

Parameters

value the new value

Definition at line 106 of file Trace.hpp.

◆ trace() [1/2]

Output & jlm::rvsdg::OutputTracer::trace ( Output & output )

Traces from the given output to find the source of the output's value.

Parameters

output the output to trace from.

Definition at line 21 of file Trace.cpp.

◆ trace() [2/2]

Output & jlm::rvsdg::OutputTracer::trace	(	Output &	output,
		const Region *	withinRegion
	)

Traces from the given output to find the source of the output's value. The optional parameter withinRegion prevents values from being traced out of the region. If withinRegion is a nullptr, the tracing will continue until the output no longer changes.

Parameters

output	the output to trace from.
withinRegion	the region where we stop tracing.

Definition at line 27 of file Trace.cpp.

◆ traceGammaOutput()

OutputTracer::TraceStepResult jlm::rvsdg::OutputTracer::traceGammaOutput	(	GammaNode &	gammaNode,
		Output &	output,
		BackEdgeState	backEdgeState
	)

protected

Trace from the given gamma output. If the gamma output can be traced to the same gamma input in all subregions, the origin of the gamma input is returned. Otherwise, if the tracer is allowed to trace into subregions, and only one of the subregions can be the origin of the value being traced, the origin within that subregion is returned. Otherwise, the gamma output itself is returned.

Precondition: the output is an output of the given gammaNode

Parameters

gammaNode	the gamma node to trace through
output	an output of the given gamma node
backEdgeState	enum describing the path taken from the starting output to `output`.

Returns: the result of tracing from the gamma output

Definition at line 94 of file Trace.cpp.

◆ traceInternal()

OutputTracer::TraceStepResult jlm::rvsdg::OutputTracer::traceInternal	(	Output &	output,
		BackEdgeState	backEdgeState,
		const Region *	withinRegion
	)

protected

Performs tracing from the given output, without updating the current starting output. Keeps tracing until the tracer is unable to find a more canonical output, or until an argument of the optional withinRegion limit is reached.

Parameters

output	the output to trace from.
backEdgeState	enum describing the path taken from the starting output to `output`.
withinRegion	the region tracing has to stay within, or nullptr

Returns: the end result of tracing, either a final output, or an impossible origin.

Definition at line 55 of file Trace.cpp.

◆ traceStep()

OutputTracer::TraceStepResult jlm::rvsdg::OutputTracer::traceStep	(	Output &	output,
		BackEdgeState	backEdgeState,
		const Region *	withinRegion
	)

protectedvirtual

The innermost body of the tracing loop. Should trace at least one step, if possible. If it is not possible to trace further, the same output is returned.

Parameters

output	the output to trace from.
backEdgeState	enum describing the path taken from the starting output to `output`.
withinRegion	if not nullptr, tracing stops if it reaches an argument of the region.

Returns: the result of tracing from the given output

Reimplemented in jlm::llvm::OutputTracer.

Definition at line 330 of file Trace.cpp.

◆ traceThetaArgument()

OutputTracer::TraceStepResult jlm::rvsdg::OutputTracer::traceThetaArgument	(	ThetaNode &	thetaNode,
		Output &	output
	)

protected

Trace from the given loop variable pre argument. This function is only used when the tracing starting point is inside the theta.

Precondition: the output is an argument of the given thetaNode's subregion.

Parameters

thetaNode	the theta node to attempt to trace out of
output	the theta subregion argument

Returns: the result of tracing from the theta argument

Definition at line 309 of file Trace.cpp.

◆ traceThetaOutput()

OutputTracer::TraceStepResult jlm::rvsdg::OutputTracer::traceThetaOutput	(	ThetaNode &	thetaNode,
		Output &	output,
		BackEdgeState	backEdgeState
	)

protected

Trace from the the given loop output. If the loop output is found to be loop invariant, the origin of the theta input is returned. Otherwise, if the tracer is allowed to trace into the subregion of structural nodes, the traced origin of the loop variable post inside the theta is returned. Otherwise, the theta output itself is returned.

Precondition: the output is an output of the given thetaNode

Parameters

thetaNode	the theta node to trace through
output	an output of the given theta node
backEdgeState	enum describing the path taken from the starting output to `output`.

Returns: the result of tracing from the theta output

Definition at line 223 of file Trace.cpp.

Member Data Documentation

◆ enableInvarianceCaching_

bool jlm::rvsdg::OutputTracer::enableInvarianceCaching_ = false

protected

Definition at line 487 of file Trace.hpp.

◆ enableRegionPredicateChecking_

bool jlm::rvsdg::OutputTracer::enableRegionPredicateChecking_ = false

protected

Definition at line 476 of file Trace.hpp.

◆ enterPhiNodes_

bool jlm::rvsdg::OutputTracer::enterPhiNodes_ = true

protected

Definition at line 472 of file Trace.hpp.

◆ invariantOutputCache_

std::unordered_map<const Output *, Input *> jlm::rvsdg::OutputTracer::invariantOutputCache_ {}

protected

Definition at line 490 of file Trace.hpp.

◆ isInterprocedural_

bool jlm::rvsdg::OutputTracer::isInterprocedural_ = true

protected

Definition at line 468 of file Trace.hpp.

◆ regionPredicateTracer_

AlternativeRegionPredicateTracer jlm::rvsdg::OutputTracer::regionPredicateTracer_

protected

Definition at line 478 of file Trace.hpp.

◆ startingOutput_

const Output* jlm::rvsdg::OutputTracer::startingOutput_ = nullptr

protected

Definition at line 482 of file Trace.hpp.

◆ structuralNodePolicy_

StructuralNodePolicy jlm::rvsdg::OutputTracer::structuralNodePolicy_

protected

Initial value:

=

StructuralNodePolicy::traceThroughIfDetectedInvariant

jlm::rvsdg::OutputTracer::StructuralNodePolicy::traceThroughIfDetectedInvariant

@ traceThroughIfDetectedInvariant

Definition at line 463 of file Trace.hpp.

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

jlm/rvsdg/Trace.hpp
jlm/rvsdg/Trace.cpp

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Enumeration Documentation

◆ BackEdgeState

◆ StructuralNodePolicy

Constructor & Destructor Documentation

◆ ~OutputTracer()

◆ OutputTracer()

Member Function Documentation

◆ clearInvarianceCache()

◆ getStructuralNodePolicy()

◆ insertInInvarianceCache()

◆ isDeepInvarianceCheckingEnabled()

◆ isEnteringPhiNodes()

◆ isInterprocedural()

◆ isInvarianceCachingEnabled()

◆ isRegionPredicateCheckingEnabled()

◆ isTracingIntoSubregionsEnabled()

◆ lookupInInvarianceCache()

◆ setEnterPhiNodes()

◆ setInterprocedural()

◆ setInvarianceCaching()

◆ setRegionPredicateCheckingEnabled()

◆ setStructuralNodePolicy()

◆ trace() [1/2]

◆ trace() [2/2]

◆ traceGammaOutput()

◆ traceInternal()

◆ traceStep()

◆ traceThetaArgument()

◆ traceThetaOutput()

Member Data Documentation

◆ enableInvarianceCaching_

◆ enableRegionPredicateChecking_

◆ enterPhiNodes_

◆ invariantOutputCache_

◆ isInterprocedural_

◆ regionPredicateTracer_

◆ startingOutput_

◆ structuralNodePolicy_