Base class for algorithms based on zones, like DeLICM. More...

#include <ZoneAlgo.h>

Public Member Functions
Scop *	getScop () const
	Return the SCoP this object is analyzing.

isl::union_map	computeKnownFromMustWrites () const
	A reaching definition zone is known to have the definition's written value if the definition is a MUST_WRITE.

isl::union_map	computeKnownFromLoad () const
	A reaching definition zone is known to be the same value as any load that reads from that array element in that period.

isl::union_map	computeKnown (bool FromWrite, bool FromRead) const
	Compute which value an array element stores at every instant.

Protected Member Functions
	ZoneAlgorithm (const char PassName, Scop S, llvm::LoopInfo *LI)
	Prepare the object before computing the zones of `S`.

isl::union_set	makeEmptyUnionSet () const

isl::union_map	makeEmptyUnionMap () const

isl::union_map	computePerPHI (const polly::ScopArrayInfo *SAI)
	For each 'execution' of a PHINode, get the incoming block that was executed before.

void	collectCompatibleElts ()
	Find the array elements that can be used for zone analysis.

isl::map	getScatterFor (ScopStmt *Stmt) const
	Get the schedule for `Stmt`.

isl::map	getScatterFor (MemoryAccess *MA) const
	Get the schedule of `MA's` parent statement.

isl::union_map	getScatterFor (isl::union_set Domain) const
	Get the schedule for the statement instances of `Domain`.

isl::map	getScatterFor (isl::set Domain) const
	Get the schedule for the statement instances of `Domain`.

isl::set	getDomainFor (ScopStmt *Stmt) const
	Get the domain of `Stmt`.

isl::set	getDomainFor (MemoryAccess *MA) const
	Get the domain `MA's` parent statement.

isl::map	getAccessRelationFor (MemoryAccess *MA) const
	Get the access relation of `MA`.

isl::map	getDefToTarget (ScopStmt DefStmt, ScopStmt TargetStmt)
	Get a domain translation map from a (scalar) definition to the statement where the definition is being moved to.

isl::map	getScalarReachingDefinition (ScopStmt *Stmt)
	Get the reaching definition of a scalar defined in `Stmt`.

isl::map	getScalarReachingDefinition (isl::set DomainDef)
	Get the reaching definition of a scalar defined in `DefDomain`.

isl::map	makeUnknownForDomain (ScopStmt *Stmt) const
	Create a statement-to-unknown value mapping.

isl::id	makeValueId (llvm::Value *V)
	Create an isl_id that represents `V`.

isl::space	makeValueSpace (llvm::Value *V)
	Create the space for an llvm::Value that is available everywhere.

isl::set	makeValueSet (llvm::Value *V)
	Create a set with the llvm::Value `V` which is available everywhere.

isl::map	makeValInst (llvm::Value Val, ScopStmt UserStmt, llvm::Loop *Scope, bool IsCertain=true)
	Create a mapping from a statement instance to the instance of an llvm::Value that can be used in there.

isl::union_map	makeNormalizedValInst (llvm::Value Val, ScopStmt UserStmt, llvm::Loop *Scope, bool IsCertain=true)
	Create and normalize a ValInst.

bool	isCompatibleAccess (MemoryAccess *MA)
	Return whether `MA` can be used for transformations (e.g.

void	computeCommon ()
	Compute the different zones.

void	computeNormalizedPHIs ()
	Compute the normalization map that replaces PHIs by their incoming values.

void	printAccesses (llvm::raw_ostream &OS, int Indent=0) const
	Print the current state of all MemoryAccesses to .

bool	isNormalizable (MemoryAccess *MA)
	Is `MA` a PHI READ access that can be normalized?


isl::boolean	isNormalized (isl::map Map)

isl::boolean	isNormalized (isl::union_map Map)

Protected Attributes
const char *	PassName
	The name of the pass this is used from. Used for optimization remarks.

std::shared_ptr< isl_ctx >	IslCtx
	Hold a reference to the isl_ctx to avoid it being freed before we released all of the isl objects.

llvm::DenseMap< ScopStmt *, isl::map >	ScalarReachDefZone
	Cached reaching definitions for each ScopStmt.

Scop *	S
	The analyzed Scop.

llvm::LoopInfo *	LI
	LoopInfo analysis used to determine whether values are synthesizable.

isl::space	ParamSpace
	Parameter space that does not need realignment.

isl::space	ScatterSpace
	Space the schedule maps to.

isl::union_map	Schedule
	Cached version of the schedule and domains.

isl::union_map	AllReads
	Combined access relations of all MemoryKind::Array READ accesses.

isl::union_map	AllReadValInst
	The loaded values (llvm::LoadInst) of all reads.

isl::union_map	AllMayWrites
	Combined access relations of all MemoryKind::Array, MAY_WRITE accesses.

isl::union_map	AllMustWrites
	Combined access relations of all MemoryKind::Array, MUST_WRITE accesses.

isl::union_map	AllWrites
	Combined access relations of all MK_Array write accesses (union of AllMayWrites and AllMustWrites).

isl::union_map	AllWriteValInst
	The value instances written to array elements of all write accesses.

isl::union_map	WriteReachDefZone
	All reaching definitions for MemoryKind::Array writes.

llvm::DenseMap< llvm::Value *, isl::id >	ValueIds
	Map llvm::Values to an isl identifier.

isl::union_set	CompatibleElts
	Set of array elements that can be reliably used for zone analysis.

llvm::SmallPtrSet< llvm::PHINode *, 4 >	RecursivePHIs
	List of PHIs that may transitively refer to themselves.

llvm::DenseSet< llvm::PHINode * >	ComputedPHIs
	PHIs that have been computed.

isl::union_map	NormalizeMap
	For computed PHIs, contains the ValInst they stand for.

llvm::SmallDenseMap< llvm::PHINode *, isl::union_map >	PerPHIMaps
	Cache for computePerPHI(const ScopArrayInfo *)

llvm::DenseMap< std::pair< ScopStmt , ScopStmt >, isl::map >	DefToTargetCache
	A cache for getDefToTarget().

Private Member Functions
void	collectIncompatibleElts (ScopStmt *Stmt, isl::union_set &IncompatibleElts, isl::union_set &AllElts)
	Find the array elements that violate the zone analysis assumptions.

void	addArrayReadAccess (MemoryAccess *MA)

isl::union_map	getWrittenValue (MemoryAccess *MA, isl::map AccRel)
	Return the ValInst write by a (must-)write access.

void	addArrayWriteAccess (MemoryAccess *MA)

isl::map	computeUseToDefFlowDependency (ScopStmt UseStmt, ScopStmt DefStmt)
	For an llvm::Value defined in `DefStmt`, compute the RAW dependency for a use in every instance of `UseStmt`.

Detailed Description

Base class for algorithms based on zones, like DeLICM.

Definition at line 44 of file ZoneAlgo.h.

Constructor & Destructor Documentation

◆ ZoneAlgorithm()

ZoneAlgorithm::ZoneAlgorithm	(	const char *	PassName,
		Scop *	S,
		llvm::LoopInfo *	LI
	)

protected

Prepare the object before computing the zones of S.

Parameters

PassName	Name of the pass using this analysis.
S	The SCoP to process.
LI	LoopInfo analysis used to determine synthesizable values.

Definition at line 263 of file ZoneAlgo.cpp.

References isl::union_map::get_space(), polly::getScatterSpace(), isl::union_map::intersect_domain(), ParamSpace, ScatterSpace, and Schedule.

Member Function Documentation

◆ addArrayReadAccess()

void ZoneAlgorithm::addArrayReadAccess ( MemoryAccess * MA )

private

◆ addArrayWriteAccess()

void ZoneAlgorithm::addArrayWriteAccess ( MemoryAccess * MA )

private

◆ collectCompatibleElts()

void ZoneAlgorithm::collectCompatibleElts ( )

protected

Find the array elements that can be used for zone analysis.

Definition at line 599 of file ZoneAlgo.cpp.

References collectIncompatibleElts(), CompatibleElts, isl::union_set::get(), isl_union_set_n_set(), makeEmptyUnionSet(), and isl::union_set::subtract().

◆ collectIncompatibleElts()

void ZoneAlgorithm::collectIncompatibleElts	(	ScopStmt *	Stmt,
		isl::union_set &	IncompatibleElts,
		isl::union_set &	AllElts
	)

private

Find the array elements that violate the zone analysis assumptions.

What violates our assumptions:

A load after a write of the same location; we assume that all reads occur before the writes.
Two writes to the same location; we cannot model the order in which these occur.

Scalar reads implicitly always occur before other accesses therefore never violate the first condition. There is also at most one write to a scalar, satisfying the second condition.

Parameters

	Stmt	The statement to be analyzed.
[out]	IncompatibleElts	Receives the elements that are not zone-analysis compatible.
[out]	AllElts	receives all encountered elements.

Definition at line 323 of file ZoneAlgo.cpp.

References isl::map::get_space(), getAccessRelationFor(), polly::ScopStmt::isRegionStmt(), makeEmptyUnionMap(), onlySameValueWrites(), PassName, POLLY_DEBUG, isl::space::range(), Stores, isl::union_set::unite(), and isl::set::universe().

Referenced by collectCompatibleElts().

◆ computeCommon()

void ZoneAlgorithm::computeCommon ( )

protected

Compute the different zones.

Definition at line 965 of file ZoneAlgo.cpp.

References addArrayReadAccess(), addArrayWriteAccess(), AllMayWrites, AllMustWrites, AllReads, AllReadValInst, AllWrites, AllWriteValInst, ComputedPHIs, computeReachingDefinition(), makeEmptyUnionMap(), NormalizeMap, Schedule, simplify, isl::union_map::unite(), and WriteReachDefZone.

◆ computeKnown()

isl::union_map ZoneAlgorithm::computeKnown	(	bool	FromWrite,
		bool	FromRead
	)		const

Compute which value an array element stores at every instant.

Parameters

FromWrite	Use stores as source of information.
FromRead	Use loads as source of information.

Returns: { [Element[] -> Zone[]] -> ValInst[] }

Definition at line 1161 of file ZoneAlgo.cpp.

References computeKnownFromLoad(), computeKnownFromMustWrites(), makeEmptyUnionMap(), simplify, and isl::union_map::unite().

◆ computeKnownFromLoad()

isl::union_map ZoneAlgorithm::computeKnownFromLoad ( ) const

A reaching definition zone is known to be the same value as any load that reads from that array element in that period.

Returns: { [Element[] -> Zone[]] -> ValInst[] }

Definition at line 1113 of file ZoneAlgo.cpp.

Referenced by computeKnown().

◆ computeKnownFromMustWrites()

isl::union_map ZoneAlgorithm::computeKnownFromMustWrites ( ) const

A reaching definition zone is known to have the definition's written value if the definition is a MUST_WRITE.

Returns: { [Element[] -> Zone[]] -> ValInst[] }

Definition at line 1102 of file ZoneAlgo.cpp.

References AllWriteValInst, isl::union_map::apply_range(), isl::union_map::curry(), polly::distributeDomain(), polly::filterKnownValInst(), and WriteReachDefZone.

Referenced by computeKnown().

◆ computeNormalizedPHIs()

void ZoneAlgorithm::computeNormalizedPHIs ( )

protected

Compute the normalization map that replaces PHIs by their incoming values.

See also: NormalizeMap

Definition at line 999 of file ZoneAlgo.cpp.

References isl::union_map::apply_domain(), isl::union_map::apply_range(), assert, ComputedPHIs, computePerPHI(), polly::ScopStmt::getSurroundingLoop(), isl::boolean::is_false(), isl::union_map::is_null(), isl::union_map::is_single_valued(), isNormalizable(), isNormalized(), isRecursivePHI(), makeEmptyUnionMap(), makeValInst(), NormalizeMap, normalizeValInst(), polly::PHI, RecursivePHIs, simplify, isl::union_map::unite(), and polly::Value.

◆ computePerPHI()

isl::union_map ZoneAlgorithm::computePerPHI ( const polly::ScopArrayInfo * SAI )

protected

For each 'execution' of a PHINode, get the incoming block that was executed before.

For each PHI instance we can directly determine which was the incoming block, and hence derive which value the PHI has.

Parameters

SAI	The ScopArrayInfo representing the PHI's storage.

Returns: { DomainPHIRead[] -> DomainPHIWrite[] }

Definition at line 537 of file ZoneAlgo.cpp.

References isl::union_map::apply_range(), assert, polly::beforeScatter(), polly::ScopArrayInfo::getBasePtr(), getScatterFor(), isl::map::intersect_params(), isl::map::intersect_range(), isl::boolean::is_false(), isl::union_map::is_injective(), isl::set::is_null(), isl::union_map::is_single_valued(), polly::ScopArrayInfo::isPHIKind(), isl::map::lexmax(), makeEmptyUnionMap(), PerPHIMaps, polly::PHI, isl::union_map::range(), isl::union_map::reverse(), ScatterSpace, polly::singleton(), and isl::union_map::unite().

Referenced by computeNormalizedPHIs().

◆ computeUseToDefFlowDependency()

isl::map ZoneAlgorithm::computeUseToDefFlowDependency	(	ScopStmt *	UseStmt,
		ScopStmt *	DefStmt
	)

private

For an llvm::Value defined in DefStmt, compute the RAW dependency for a use in every instance of UseStmt.

Parameters

UseStmt	Statement a scalar is used in.
DefStmt	Statement a scalar is defined in.

Returns: { DomainUse[] -> DomainDef[] }

Definition at line 484 of file ZoneAlgo.cpp.

References isl::map::apply_range(), polly::convertZoneToTimepoints(), getScalarReachingDefinition(), getScatterFor(), and isl::in.

Referenced by getDefToTarget().

◆ getAccessRelationFor()

isl::map ZoneAlgorithm::getAccessRelationFor ( MemoryAccess * MA ) const

protected

Get the access relation of MA.

The domain of the result is as narrow as possible.

Definition at line 647 of file ZoneAlgo.cpp.

References Domain, getDomainFor(), polly::MemoryAccess::getLatestAccessRelation(), and isl::map::intersect_domain().

Referenced by addArrayReadAccess(), addArrayWriteAccess(), and collectIncompatibleElts().

◆ getDefToTarget()

isl::map ZoneAlgorithm::getDefToTarget	(	ScopStmt *	DefStmt,
		ScopStmt *	TargetStmt
	)

protected

Get a domain translation map from a (scalar) definition to the statement where the definition is being moved to.

TargetStmt can also be seen at an llvm::Use of an llvm::Value in DefStmt. In addition, we allow transitive uses:

DefStmt -> MiddleStmt -> TargetStmt

where an operand tree of instructions in DefStmt and MiddleStmt are to be moved to TargetStmt. To be generally correct, we also need to know all the intermediate statements. However, we make use of the fact that ForwardOpTree currently does not support a move from a loop body across its header such that only the first definition and the target statement are relevant.

Parameters

DefStmt	Statement from where a definition might be moved from.
TargetStmt	Statement where the definition is potentially being moved to (should contain a use of that definition).

Returns: { DomainDef[] -> DomainTarget[] }

Definition at line 653 of file ZoneAlgo.cpp.

References assert, computeUseToDefFlowDependency(), DefToTargetCache, isl::map::equate(), isl::map::from_domain_and_range(), getDomainFor(), polly::ScopStmt::getSurroundingLoop(), isl::map::identity(), isl::in, isl::map::is_null(), isInsideLoop(), isl::out, polly::rangeIslSize(), isl::map::reverse(), simplify, isl::set::tuple_dim(), and unsignedFromIslSize().

Referenced by makeValInst().

◆ getDomainFor() [1/2]

isl::set ZoneAlgorithm::getDomainFor ( MemoryAccess * MA ) const

protected

Get the domain MA's parent statement.

Definition at line 643 of file ZoneAlgo.cpp.

References getDomainFor(), and polly::MemoryAccess::getStatement().

◆ getDomainFor() [2/2]

isl::set ZoneAlgorithm::getDomainFor ( ScopStmt * Stmt ) const

protected

Get the domain of Stmt.

Definition at line 639 of file ZoneAlgo.cpp.

References polly::ScopStmt::getDomain(), and isl::set::remove_redundancies().

Referenced by getAccessRelationFor(), getDefToTarget(), getDomainFor(), getScalarReachingDefinition(), makeUnknownForDomain(), and makeValInst().

◆ getScalarReachingDefinition() [1/2]

isl::map ZoneAlgorithm::getScalarReachingDefinition ( isl::set DomainDef )

protected

Get the reaching definition of a scalar defined in DefDomain.

Parameters

DomainDef { DomainDef[] } The write statements to get the reaching definition for.

Returns: { Scatter[] -> DomainDef[] }

Definition at line 719 of file ZoneAlgo.cpp.

References isl::set::get_tuple_id(), getScalarReachingDefinition(), and isl_id_get_user().

◆ getScalarReachingDefinition() [2/2]

isl::map ZoneAlgorithm::getScalarReachingDefinition ( ScopStmt * Stmt )

protected

Get the reaching definition of a scalar defined in Stmt.

Note that this does not depend on the llvm::Instruction, only on the statement it is defined in. Therefore the same computation can be reused.

Parameters

Stmt	The statement in which a scalar is defined.

Returns: { Scatter[] -> DomainDef[] }

Definition at line 707 of file ZoneAlgo.cpp.

References computeScalarReachingDefinition(), Domain, getDomainFor(), ScalarReachDefZone, Schedule, and simplify.

Referenced by computeUseToDefFlowDependency(), and getScalarReachingDefinition().

◆ getScatterFor() [1/4]

isl::map ZoneAlgorithm::getScatterFor ( isl::set Domain ) const

protected

Get the schedule for the statement instances of Domain.

Definition at line 630 of file ZoneAlgo.cpp.

References assert, Domain, getScatterFor(), isl_bool_true, ScatterSpace, and polly::singleton().

◆ getScatterFor() [2/4]

isl::union_map ZoneAlgorithm::getScatterFor ( isl::union_set Domain ) const

protected

Get the schedule for the statement instances of Domain.

Definition at line 626 of file ZoneAlgo.cpp.

References Domain, isl::union_map::intersect_domain(), and Schedule.

◆ getScatterFor() [3/4]

isl::map ZoneAlgorithm::getScatterFor ( MemoryAccess * MA ) const

protected

Get the schedule of MA's parent statement.

Definition at line 622 of file ZoneAlgo.cpp.

References getScatterFor(), and polly::MemoryAccess::getStatement().

◆ getScatterFor() [4/4]

isl::map ZoneAlgorithm::getScatterFor ( ScopStmt * Stmt ) const

protected

Get the schedule for Stmt.

The domain of the result is as narrow as possible.

Definition at line 616 of file ZoneAlgo.cpp.

References isl::union_map::extract_map(), polly::ScopStmt::getDomainSpace(), isl::space::map_from_domain_and_range(), ScatterSpace, and Schedule.

Referenced by computePerPHI(), computeUseToDefFlowDependency(), and getScatterFor().

◆ getScop()

Scop * polly::ZoneAlgorithm::getScop ( ) const

inline

Return the SCoP this object is analyzing.

Definition at line 378 of file ZoneAlgo.h.

References S.

◆ getWrittenValue()

isl::union_map ZoneAlgorithm::getWrittenValue	(	MemoryAccess *	MA,
		isl::map	AccRel
	)

private

Return the ValInst write by a (must-)write access.

Returns the 'unknown' ValInst if there is no single ValInst[] the array element written to will have.

Returns: { ValInst[] }

Definition at line 416 of file ZoneAlgo.cpp.

References polly::MemoryAccess::getAccessInstruction(), polly::MemoryAccess::getAccessValue(), polly::ScopArrayInfo::getElementType(), polly::MemoryAccess::getLatestScopArrayInfo(), polly::MemoryAccess::getStatement(), polly::ScopStmt::getSurroundingLoop(), isl::map::is_single_valued(), isl::boolean::is_true(), polly::MemoryAccess::isMustWrite(), polly::MemoryAccess::isOriginalArrayKind(), LI, makeNormalizedValInst(), and polly::Value.

Referenced by addArrayWriteAccess().

◆ isCompatibleAccess()

bool ZoneAlgorithm::isCompatibleAccess ( MemoryAccess * MA )

protected

Return whether MA can be used for transformations (e.g.

OpTree load forwarding, DeLICM mapping).

Definition at line 890 of file ZoneAlgo.cpp.

References polly::MemoryAccess::getAccessInstruction(), and polly::MemoryAccess::isLatestArrayKind().

◆ isNormalizable()

bool ZoneAlgorithm::isNormalizable ( MemoryAccess * MA )

protected

Is MA a PHI READ access that can be normalized?

See also: NormalizeMap

Definition at line 899 of file ZoneAlgo.cpp.

References assert, polly::MemoryAccess::getAccessInstruction(), polly::MemoryAccess::getOriginalScopArrayInfo(), polly::MemoryAccess::isOriginalPHIKind(), polly::MemoryAccess::isRead(), polly::PHI, and RecursivePHIs.

Referenced by computeNormalizedPHIs(), and isNormalized().

◆ isNormalized() [1/2]

isl::boolean ZoneAlgorithm::isNormalized ( isl::map Map )

protected

Determine whether the argument does not map to any computed PHI. Those should have been replaced by their incoming values.

See also: #NormalizedPHI

Definition at line 927 of file ZoneAlgo.cpp.

References isl::map::get_space(), isl::space::get_tuple_id(), isl::id::get_user(), isl::in, isl::id::is_null(), isl::boolean::is_true(), isl::space::is_wrapping(), isNormalizable(), isl::out, polly::PHI, isl::space::range(), isl::space::unwrap(), and polly::Value.

Referenced by computeNormalizedPHIs(), and isNormalized().

◆ isNormalized() [2/2]

isl::boolean ZoneAlgorithm::isNormalized ( isl::union_map Map )

protected

Definition at line 954 of file ZoneAlgo.cpp.

References isl::union_map::get_map_list(), isl::boolean::is_true(), and isNormalized().

◆ makeEmptyUnionMap()

isl::union_map ZoneAlgorithm::makeEmptyUnionMap ( ) const

protected

Definition at line 595 of file ZoneAlgo.cpp.

References isl::space::ctx(), isl::union_map::empty(), and ParamSpace.

Referenced by collectIncompatibleElts(), computeCommon(), computeKnown(), computeNormalizedPHIs(), and computePerPHI().

◆ makeEmptyUnionSet()

isl::union_set ZoneAlgorithm::makeEmptyUnionSet ( ) const

protected

Definition at line 591 of file ZoneAlgo.cpp.

References isl::space::ctx(), isl::union_set::empty(), and ParamSpace.

Referenced by collectCompatibleElts().

◆ makeNormalizedValInst()

isl::union_map ZoneAlgorithm::makeNormalizedValInst	(	llvm::Value *	Val,
		ScopStmt *	UserStmt,
		llvm::Loop *	Scope,
		bool	IsCertain = `true`
	)

protected

Create and normalize a ValInst.

See also: makeValInst; normalizeValInst; #NormalizedPHI

Definition at line 880 of file ZoneAlgo.cpp.

References ComputedPHIs, makeValInst(), NormalizeMap, and normalizeValInst().

Referenced by getWrittenValue().

◆ makeUnknownForDomain()

isl::map ZoneAlgorithm::makeUnknownForDomain ( ScopStmt * Stmt ) const

protected

Create a statement-to-unknown value mapping.

Parameters

Stmt	The statement whose instances are mapped to unknown.

Returns: { Domain[] -> ValInst[] }

Definition at line 728 of file ZoneAlgo.cpp.

References getDomainFor().

Referenced by addArrayWriteAccess(), and makeValInst().

◆ makeValInst()

isl::map ZoneAlgorithm::makeValInst	(	llvm::Value *	Val,
		ScopStmt *	UserStmt,
		llvm::Loop *	Scope,
		bool	IsCertain = `true`
	)

protected

Create a mapping from a statement instance to the instance of an llvm::Value that can be used in there.

Although LLVM IR uses single static assignment, llvm::Values can have different contents in loops, when they get redefined in the last iteration. This function tries to get the statement instance of the previous definition, relative to a user.

Example: for (int i = 0; i < N; i += 1) { DEF: int v = A[i]; USE: use(v); }

The value instance used by statement instance USE[i] is DEF[i]. Hence, makeValInst returns:

{ USE[i] -> [DEF[i] -> v[]] : 0 <= i < N }

Parameters

Val	The value to get the instance of.
UserStmt	The statement that uses `Val`. Can be nullptr.
Scope	Loop the using instruction resides in.
IsCertain	Pass true if the definition of `Val` is a MUST_WRITE or false if the write is conditional.

Returns: { DomainUse[] -> ValInst[] }

Definition at line 755 of file ZoneAlgo.cpp.

References polly::VirtualUse::Block, polly::VirtualUse::Constant, polly::VirtualUse::create(), isl::map::from_domain_and_range(), getDefToTarget(), getDomainFor(), polly::VirtualUse::Hoisted, isl::map::identity(), polly::VirtualUse::Inter, polly::VirtualUse::Intra, isl_id_alloc(), makeUnknownForDomain(), makeValueSet(), isl::manage(), polly::VirtualUse::ReadOnly, isl::map::reverse(), isl::set, simplify, and polly::VirtualUse::Synthesizable.

Referenced by addArrayReadAccess(), computeNormalizedPHIs(), and makeNormalizedValInst().

◆ makeValueId()

isl::id ZoneAlgorithm::makeValueId ( llvm::Value * V )

protected

Create an isl_id that represents V.

Definition at line 732 of file ZoneAlgo.cpp.

References isl::id::alloc(), polly::getIslCompatibleName(), IslCtx, polly::UseInstructionNames, and ValueIds.

Referenced by makeValueSpace().

◆ makeValueSet()

isl::set ZoneAlgorithm::makeValueSet ( llvm::Value * V )

protected

Create a set with the llvm::Value V which is available everywhere.

Definition at line 750 of file ZoneAlgo.cpp.

References makeValueSpace(), and isl::set::universe().

Referenced by makeValInst().

◆ makeValueSpace()

isl::space ZoneAlgorithm::makeValueSpace ( llvm::Value * V )

protected

Create the space for an llvm::Value that is available everywhere.

Definition at line 745 of file ZoneAlgo.cpp.

References makeValueId(), ParamSpace, isl::set, isl::space::set_from_params(), and isl::space::set_tuple_id().

Referenced by makeValueSet().

◆ printAccesses()

void ZoneAlgorithm::printAccesses	(	llvm::raw_ostream &	OS,
		int	Indent = `0`
	)		const

protected

Print the current state of all MemoryAccesses to .

Definition at line 1092 of file ZoneAlgo.cpp.

Member Data Documentation

◆ AllMayWrites

isl::union_map polly::ZoneAlgorithm::AllMayWrites

protected

Combined access relations of all MemoryKind::Array, MAY_WRITE accesses.

{ DomainMayWrite[] -> Element[] }

Definition at line 87 of file ZoneAlgo.h.

Referenced by addArrayWriteAccess(), and computeCommon().

◆ AllMustWrites

isl::union_map polly::ZoneAlgorithm::AllMustWrites

protected

Combined access relations of all MemoryKind::Array, MUST_WRITE accesses.

{ DomainMustWrite[] -> Element[] }

Definition at line 91 of file ZoneAlgo.h.

Referenced by addArrayWriteAccess(), and computeCommon().

◆ AllReads

isl::union_map polly::ZoneAlgorithm::AllReads

protected

Combined access relations of all MemoryKind::Array READ accesses.

{ DomainRead[] -> Element[] }

Definition at line 79 of file ZoneAlgo.h.

Referenced by addArrayReadAccess(), computeCommon(), and computeKnownFromLoad().

◆ AllReadValInst

isl::union_map polly::ZoneAlgorithm::AllReadValInst

protected

The loaded values (llvm::LoadInst) of all reads.

{ [Element[] -> DomainRead[]] -> ValInst[] }

Definition at line 83 of file ZoneAlgo.h.

Referenced by addArrayReadAccess(), computeCommon(), and computeKnownFromLoad().

◆ AllWrites

isl::union_map polly::ZoneAlgorithm::AllWrites

protected

Combined access relations of all MK_Array write accesses (union of AllMayWrites and AllMustWrites).

{ DomainWrite[] -> Element[] }

Definition at line 96 of file ZoneAlgo.h.

Referenced by computeCommon(), and computeKnownFromLoad().

◆ AllWriteValInst

isl::union_map polly::ZoneAlgorithm::AllWriteValInst

protected

The value instances written to array elements of all write accesses.

{ [Element[] -> DomainWrite[]] -> ValInst[] }

Definition at line 100 of file ZoneAlgo.h.

Referenced by addArrayWriteAccess(), computeCommon(), and computeKnownFromMustWrites().

◆ CompatibleElts

isl::union_set polly::ZoneAlgorithm::CompatibleElts

protected

Set of array elements that can be reliably used for zone analysis.

{ Element[] }

Definition at line 113 of file ZoneAlgo.h.

Referenced by addArrayReadAccess(), addArrayWriteAccess(), and collectCompatibleElts().

◆ ComputedPHIs

llvm::DenseSet<llvm::PHINode *> polly::ZoneAlgorithm::ComputedPHIs

protected

PHIs that have been computed.

Computed PHIs are replaced by their incoming values using NormalizeMap.

Definition at line 125 of file ZoneAlgo.h.

Referenced by computeCommon(), computeNormalizedPHIs(), and makeNormalizedValInst().

◆ DefToTargetCache

llvm::DenseMap<std::pair<ScopStmt *, ScopStmt *>, isl::map> polly::ZoneAlgorithm::DefToTargetCache

protected

A cache for getDefToTarget().

Definition at line 157 of file ZoneAlgo.h.

Referenced by getDefToTarget().

◆ IslCtx

std::shared_ptr<isl_ctx> polly::ZoneAlgorithm::IslCtx

protected

Hold a reference to the isl_ctx to avoid it being freed before we released all of the isl objects.

This must be declared before any other member that holds an isl object. This guarantees that the shared_ptr and its isl_ctx is destructed last, after all other members free'd the isl objects they were holding.

Definition at line 55 of file ZoneAlgo.h.

Referenced by makeValueId().

◆ LI

llvm::LoopInfo* polly::ZoneAlgorithm::LI

protected

LoopInfo analysis used to determine whether values are synthesizable.

Definition at line 66 of file ZoneAlgo.h.

Referenced by addArrayReadAccess(), and getWrittenValue().

◆ NormalizeMap

isl::union_map polly::ZoneAlgorithm::NormalizeMap

protected

For computed PHIs, contains the ValInst they stand for.

To show an example, assume the following PHINode:

Stmt: phi = phi double [val1, bb1], [val2, bb2]

It's ValInst is:

{ [Stmt[i] -> phi[]] }

The value phi will be either val1 or val2, depending on whether in iteration i bb1 or bb2 has been executed before. In SCoPs, this can be determined at compile-time, and the result stored in NormalizeMap. For the previous example, it could be:

{ [Stmt[i] -> phi[]] -> [Stmt[0] -> val1[]]; [Stmt[i] -> phi[]] -> [Stmt[i] -> val2[]] : i > 0 }

Only ValInsts in ComputedPHIs are present in this map. Other values are assumed to represent themselves. This is to avoid adding lots of identity entries to this map.

{ PHIValInst[] -> IncomingValInst[] }

Definition at line 151 of file ZoneAlgo.h.

Referenced by computeCommon(), computeNormalizedPHIs(), and makeNormalizedValInst().

◆ ParamSpace

isl::space polly::ZoneAlgorithm::ParamSpace

protected

Parameter space that does not need realignment.

Definition at line 69 of file ZoneAlgo.h.

Referenced by makeEmptyUnionMap(), makeEmptyUnionSet(), makeValueSpace(), and ZoneAlgorithm().

◆ PassName

const char* polly::ZoneAlgorithm::PassName

protected

The name of the pass this is used from. Used for optimization remarks.

Definition at line 47 of file ZoneAlgo.h.

Referenced by collectIncompatibleElts().

◆ PerPHIMaps

llvm::SmallDenseMap<llvm::PHINode *, isl::union_map> polly::ZoneAlgorithm::PerPHIMaps

protected

Cache for computePerPHI(const ScopArrayInfo *)

Definition at line 154 of file ZoneAlgo.h.

Referenced by computePerPHI().

◆ RecursivePHIs

llvm::SmallPtrSet<llvm::PHINode *, 4> polly::ZoneAlgorithm::RecursivePHIs

protected

List of PHIs that may transitively refer to themselves.

Computing them would require a polyhedral transitive closure operation, for which isl may only return an approximation. For correctness, we always require an exact result. Hence, we exclude such PHIs.

Definition at line 120 of file ZoneAlgo.h.

Referenced by computeNormalizedPHIs(), and isNormalizable().

◆ S

Scop* polly::ZoneAlgorithm::S

protected

The analyzed Scop.

Definition at line 63 of file ZoneAlgo.h.

Referenced by getScop().

◆ ScalarReachDefZone

llvm::DenseMap<ScopStmt *, isl::map> polly::ZoneAlgorithm::ScalarReachDefZone

protected

Cached reaching definitions for each ScopStmt.

Use getScalarReachingDefinition() to get its contents.

Definition at line 60 of file ZoneAlgo.h.

Referenced by getScalarReachingDefinition().

◆ ScatterSpace

isl::space polly::ZoneAlgorithm::ScatterSpace

protected

Space the schedule maps to.

Definition at line 72 of file ZoneAlgo.h.

Referenced by computeKnownFromLoad(), computePerPHI(), getScatterFor(), and ZoneAlgorithm().

◆ Schedule

isl::union_map polly::ZoneAlgorithm::Schedule

protected

Cached version of the schedule and domains.

Definition at line 75 of file ZoneAlgo.h.

Referenced by computeCommon(), computeKnownFromLoad(), getScalarReachingDefinition(), getScatterFor(), and ZoneAlgorithm().

◆ ValueIds

llvm::DenseMap<llvm::Value *, isl::id> polly::ZoneAlgorithm::ValueIds

protected

Map llvm::Values to an isl identifier.

Used with -polly-use-llvm-names=false as an alternative method to get unique ids that do not depend on pointer values.

Definition at line 109 of file ZoneAlgo.h.

Referenced by makeValueId().

◆ WriteReachDefZone

isl::union_map polly::ZoneAlgorithm::WriteReachDefZone

protected

All reaching definitions for MemoryKind::Array writes.

{ [Element[] -> Zone[]] -> DomainWrite[] }

Definition at line 104 of file ZoneAlgo.h.

Referenced by computeCommon(), computeKnownFromLoad(), and computeKnownFromMustWrites().

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

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ ZoneAlgorithm()

Member Function Documentation

◆ addArrayReadAccess()

◆ addArrayWriteAccess()

◆ collectCompatibleElts()

◆ collectIncompatibleElts()

◆ computeCommon()

◆ computeKnown()

◆ computeKnownFromLoad()

◆ computeKnownFromMustWrites()

◆ computeNormalizedPHIs()

◆ computePerPHI()

◆ computeUseToDefFlowDependency()

◆ getAccessRelationFor()

◆ getDefToTarget()

◆ getDomainFor() [1/2]

◆ getDomainFor() [2/2]

◆ getScalarReachingDefinition() [1/2]

◆ getScalarReachingDefinition() [2/2]

◆ getScatterFor() [1/4]

◆ getScatterFor() [2/4]

◆ getScatterFor() [3/4]

◆ getScatterFor() [4/4]

◆ getScop()

◆ getWrittenValue()

◆ isCompatibleAccess()

◆ isNormalizable()

◆ isNormalized() [1/2]

◆ isNormalized() [2/2]

◆ makeEmptyUnionMap()

◆ makeEmptyUnionSet()

◆ makeNormalizedValInst()

◆ makeUnknownForDomain()

◆ makeValInst()

◆ makeValueId()

◆ makeValueSet()

◆ makeValueSpace()

◆ printAccesses()

Member Data Documentation

◆ AllMayWrites

◆ AllMustWrites

◆ AllReads

◆ AllReadValInst

◆ AllWrites

◆ AllWriteValInst

◆ CompatibleElts

◆ ComputedPHIs

◆ DefToTargetCache

◆ IslCtx

◆ LI

◆ NormalizeMap

◆ ParamSpace

◆ PassName

◆ PerPHIMaps

◆ RecursivePHIs

◆ S

◆ ScalarReachDefZone

◆ ScatterSpace

◆ Schedule

◆ ValueIds

◆ WriteReachDefZone