jlm::rvsdg::RegionPredicateTrace Class Reference

Traces region reachability by predicate assertions. More...

#include <RegionPredicateTrace.hpp>

Classes
class	Observer

Public Member Functions
	~RegionPredicateTrace ()
	RegionPredicateTrace ()
PredicateValueRange	GetRegionPredicateAssignConstraints (Region &region, Input &predUse)
	Computes value range for a predicate when exiting a region.
PredicateSatRequired	GetRegionSatRequired (Region &region)
	Computes required predicate assignments for region.
bool	CheckPredicatesSatisfiable (Region &originRegion, Region &targetRegion)
	Checks for dynamic reachability between two regions.

Private Types
using	RegionPredRange = std::unordered_map< Region *, PredicateValueRange >

Private Member Functions
void	Clear ()
void	ObserveRegion (Region &region)
const PredicateValueRange &	ComputeAndRecord (RegionPredRange &regionPredRange, Input &input, std::unordered_map< Input *, PredicateValueRange > &visitedInputs, const ControlType &type)
PredicateValueRange	Compute (RegionPredRange &regionPredRange, Input &input, std::unordered_map< Input *, PredicateValueRange > &visitedInputs, const ControlType &type)

Private Attributes
std::unordered_map< Input *, RegionPredRange >	predAssignment_
std::unordered_map< Region *, PredicateSatRequired >	predSat_
std::unordered_map< Region *, std::unique_ptr< Observer > >	observers_

Detailed Description

Traces region reachability by predicate assertions.

Traces predicate def/use patterns in the graph and determines assignments of values to predicates in different regions, as well as the predicate assignments necessary to reach a given region.

Definition at line 104 of file RegionPredicateTrace.hpp.

Member Typedef Documentation

RegionPredRange

using jlm::rvsdg::RegionPredicateTrace::RegionPredRange = std::unordered_map<Region *, PredicateValueRange>

private

Definition at line 194 of file RegionPredicateTrace.hpp.

Constructor & Destructor Documentation

~RegionPredicateTrace()

jlm::rvsdg::RegionPredicateTrace::~RegionPredicateTrace

(

)

Definition at line 73 of file RegionPredicateTrace.cpp.

RegionPredicateTrace()

jlm::rvsdg::RegionPredicateTrace::RegionPredicateTrace

(

)

Definition at line 76 of file RegionPredicateTrace.cpp.

Member Function Documentation

CheckPredicatesSatisfiable()

bool jlm::rvsdg::RegionPredicateTrace::CheckPredicatesSatisfiable	(	Region &	originRegion,
		Region &	targetRegion
	)

Checks for dynamic reachability between two regions.

Parameters

originRegion	The "upper" region, from which we want to check whether another regino can be reached.
targetRegion	The "lower" region which we want to check whether it can be reached.

Returns

True iff targetRegion is dynamically reachable assuming that originRegion has been reached before.

Computes predicates value ranges that are necessarily assigned assuming that originRegion has been entered, and checks whether these predicates allow targetRegion to be entered.

This allows to dynamically discriminate whether a value generated in originRegion can affect a use site in targetRegion:

• if this returns true, then a value generated in originRegion may dynamically be forwarded and used in targetRegion
• if this returns false, then any value generated in originRegion cannot be the value ultimately used in targetRegion – the effective value at the use site within targetRegion must originate from somewhere else (effectively a gamma branch that is parallel to originRegion).

Definition at line 315 of file RegionPredicateTrace.cpp.

Clear()

void jlm::rvsdg::RegionPredicateTrace::Clear ( )

private

Definition at line 80 of file RegionPredicateTrace.cpp.

Compute()

PredicateValueRange jlm::rvsdg::RegionPredicateTrace::Compute ( RegionPredRange &  regionPredRange, Input &  input, std::unordered_map< Input *, PredicateValueRange > &  visitedInputs, const ControlType &  type  )

private

Helper function for the above ComputeAndRecord

Definition at line 145 of file RegionPredicateTrace.cpp.

ComputeAndRecord()

const PredicateValueRange & jlm::rvsdg::RegionPredicateTrace::ComputeAndRecord ( RegionPredRange &  regionPredRange, Input &  input, std::unordered_map< Input *, PredicateValueRange > &  visitedInputs, const ControlType &  type  )

private

Traces from the given input to find the regions that may provide its value.

Parameters

regionPredRange	the resulting map of possible values provided in each region.
input	the input being traced from
visitedInputs	set of seen inputs, to avoid re-visiting
type	the type of the input

Definition at line 108 of file RegionPredicateTrace.cpp.

GetRegionPredicateAssignConstraints()

PredicateValueRange jlm::rvsdg::RegionPredicateTrace::GetRegionPredicateAssignConstraints	(	Region &	region,
		Input &	predUse
	)

Computes value range for a predicate when exiting a region.

Parameters

region	Region to check at exit
predUse	Use site of the predicate of interest

Returns

The value range that can be reached coming out of this region, and that might be effective at the use site

Traces the definitions of the predicate used at preUse back to its definition sites. Computes the possible values that the predicate can obtain from its definition sites at the end of the region queried.

For example, if a constant value is assigned to a predicate within this region, then this will determine its value range. If OTOH there are multiple alternative paths within or leading into this region with multiple possible predicate assignments, then this will report the union of all possible values.

Definition at line 255 of file RegionPredicateTrace.cpp.

GetRegionSatRequired()

PredicateSatRequired jlm::rvsdg::RegionPredicateTrace::GetRegionSatRequired

(

Region &

region

)

Computes required predicate assignments for region.

Parameters

region

The region that we want to check for reachability

Returns

Necessary predicate / value pairs that need to be satisfied in order to reach this region.

Computes which predicate needs to be assigned which value in order to reach a specific region. E.g. for a region nested inside three gamma nodes, this gives the required assignments to the three control predicates in question that are needed in order to reach the inner region.

Definition at line 283 of file RegionPredicateTrace.cpp.

ObserveRegion()

void jlm::rvsdg::RegionPredicateTrace::ObserveRegion ( Region &  region )

private

Definition at line 97 of file RegionPredicateTrace.cpp.

Member Data Documentation

observers_

std::unordered_map<Region *, std::unique_ptr<Observer> > jlm::rvsdg::RegionPredicateTrace::observers_

private

Definition at line 235 of file RegionPredicateTrace.hpp.

predAssignment_

std::unordered_map<Input *, RegionPredRange> jlm::rvsdg::RegionPredicateTrace::predAssignment_

private

Definition at line 229 of file RegionPredicateTrace.hpp.

predSat_

std::unordered_map<Region *, PredicateSatRequired> jlm::rvsdg::RegionPredicateTrace::predSat_

private

Definition at line 232 of file RegionPredicateTrace.hpp.

---

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

• jlm/rvsdg/RegionPredicateTrace.hpp
• jlm/rvsdg/RegionPredicateTrace.cpp