Pass to detect the maximal static control parts (Scops) of a function. More...

#include <ScopDetection.h>

Classes
struct	DetectionContext
	Context variables for SCoP detection. More...

struct	LoopStats
	Helper data structure to collect statistics about loop counts. More...

Public Types
using	RegionSet = SetVector< const Region * >

Public Member Functions
int	getNextID ()

	ScopDetection (const DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, RegionInfo &RI, AAResults &AA, OptimizationRemarkEmitter &ORE)

void	detect (Function &F)

RegionInfo *	getRI () const
	Get the RegionInfo stored in this pass.

LoopInfo *	getLI () const
	Get the LoopInfo stored in this pass.

bool	isMaxRegionInScop (const Region &R, bool Verify=true)
	Is the region is the maximum region of a Scop?

DetectionContext *	getDetectionContext (const Region *R) const
	Return the detection context for `R`, nullptr if `R` was invalid.

const RejectLog *	lookupRejectionLog (const Region *R) const
	Return the set of rejection causes for `R`.

std::string	regionIsInvalidBecause (const Region *R) const
	Get a message why a region is invalid.

Public Attributes
RegionSet	ValidRegions

int	NextScopID = 0

Private Types
using	DetectionContextMapTy = DenseMap< BBPair, std::unique_ptr< DetectionContext > >
	Map to remember detection contexts for all regions.

Private Member Functions
void	removeCachedResults (const Region &R)
	Remove cached results for `R`.

void	removeCachedResultsRecursively (const Region &R)
	Remove cached results for the children of `R` recursively.

bool	involvesMultiplePtrs (const SCEV S0, const SCEV S1, Loop *Scope) const
	Check if `S0` and `S1` do contain multiple possibly aliasing pointers.

bool	addOverApproximatedRegion (Region *AR, DetectionContext &Context) const
	Add the region `AR` as over approximated sub-region in `Context`.

SmallVector< const SCEV *, 4 >	getDelinearizationTerms (DetectionContext &Context, const SCEVUnknown *BasePointer) const
	Find for a given base pointer terms that hint towards dimension sizes of a multi-dimensional array.

bool	hasValidArraySizes (DetectionContext &Context, SmallVectorImpl< const SCEV * > &Sizes, const SCEVUnknown BasePointer, Loop Scope) const
	Check if the dimension size of a delinearized array is valid.

bool	computeAccessFunctions (DetectionContext &Context, const SCEVUnknown *BasePointer, std::shared_ptr< ArrayShape > Shape) const
	Derive access functions for a given base pointer.

bool	hasBaseAffineAccesses (DetectionContext &Context, const SCEVUnknown BasePointer, Loop Scope) const
	Check if all accesses to a given BasePointer are affine.

bool	hasAffineMemoryAccesses (DetectionContext &Context) const
	Delinearize all non affine memory accesses and return false when there exists a non affine memory access that cannot be delinearized.

Region *	expandRegion (Region &R)
	Try to expand the region R.

void	findScops (Region &R)
	Find the Scops in this region tree.

bool	allBlocksValid (DetectionContext &Context)
	Check if all basic block in the region are valid.

bool	hasSufficientCompute (DetectionContext &Context, int NumAffineLoops) const
	Check if a region has sufficient compute instructions.

bool	hasPossiblyDistributableLoop (DetectionContext &Context) const
	Check if the unique affine loop might be amendable to distribution.

bool	isProfitableRegion (DetectionContext &Context) const
	Check if a region is profitable to optimize.

bool	isValidRegion (DetectionContext &Context)
	Check if a region is a Scop.

bool	isValidIntrinsicInst (IntrinsicInst &II, DetectionContext &Context) const
	Check if an intrinsic call can be part of a Scop.

bool	isValidCallInst (CallInst &CI, DetectionContext &Context) const
	Check if a call instruction can be part of a Scop.

bool	onlyValidRequiredInvariantLoads (InvariantLoadsSetTy &RequiredILS, DetectionContext &Context) const
	Check if the given loads could be invariant and can be hoisted.

bool	isInvariant (Value &Val, const Region &Reg, DetectionContext &Ctx) const
	Check if a value is invariant in the region Reg.

bool	isValidAccess (Instruction Inst, const SCEV AF, const SCEVUnknown *BP, DetectionContext &Context) const
	Check if the memory access caused by `Inst` is valid.

bool	isValidMemoryAccess (MemAccInst Inst, DetectionContext &Context) const
	Check if a memory access can be part of a Scop.

bool	isValidInstruction (Instruction &Inst, DetectionContext &Context)
	Check if an instruction can be part of a Scop.

bool	isValidSwitch (BasicBlock &BB, SwitchInst SI, Value Condition, bool IsLoopBranch, DetectionContext &Context) const
	Check if the switch `SI` with condition `Condition` is valid.

bool	isValidBranch (BasicBlock &BB, BranchInst BI, Value Condition, bool IsLoopBranch, DetectionContext &Context)
	Check if the branch `BI` with condition `Condition` is valid.

bool	isAffine (const SCEV S, Loop Scope, DetectionContext &Context) const
	Check if the SCEV `S` is affine in the current `Context`.

bool	isValidCFG (BasicBlock &BB, bool IsLoopBranch, bool AllowUnreachable, DetectionContext &Context)
	Check if the control flow in a basic block is valid.

bool	isValidLoop (Loop *L, DetectionContext &Context)
	Is a loop valid with respect to a given region.

bool	canUseISLTripCount (Loop *L, DetectionContext &Context)
	Can ISL compute the trip count of a loop.

void	printLocations (Function &F)
	Print the locations of all detected scops.

bool	isReducibleRegion (Region &R, DebugLoc &DbgLoc) const
	Check if a region is reducible or not.

template<class RR , typename... Args>
bool	invalid (DetectionContext &Context, bool Assert, Args &&...Arguments) const
	Track diagnostics for invalid scops.

Static Private Member Functions
static ScopDetection::LoopStats	countBeneficialSubLoops (Loop *L, ScalarEvolution &SE, unsigned MinProfitableTrips)
	Count the number of loops and the maximal loop depth in `L`.

static bool	isValidFunction (Function &F)
	Check if the function `F` is marked as invalid.

Private Attributes
const DominatorTree &	DT
	Analyses used.

ScalarEvolution &	SE

LoopInfo &	LI

RegionInfo &	RI

AAResults &	AA

DetectionContextMapTy	DetectionContextMap

DenseMap< std::tuple< const BasicBlock , const Region >, bool >	ErrorBlockCache
	Cache for the isErrorBlock function.

Maximum Region In Scops Iterators
These iterators iterator over all maximum region in Scops of this function.
using	iterator = RegionSet::iterator

using	const_iterator = RegionSet::const_iterator

OptimizationRemarkEmitter &	ORE
	OptimizationRemarkEmitter object used to emit diagnostic remarks.

iterator	begin ()

iterator	end ()

const_iterator	begin () const

const_iterator	end () const

void	emitMissedRemarks (const Function &F)
	Emit rejection remarks for all rejected regions.

void	verifyAnalysis ()
	Verify if all valid Regions in this Function are still valid after some transformations.

void	verifyRegion (const Region &R)
	Verify if R is still a valid part of Scop after some transformations.

bool	isErrorBlock (llvm::BasicBlock &BB, const llvm::Region &R)
	Check if the block is a error block.

static void	markFunctionAsInvalid (Function *F)
	Mark the function as invalid so we will not extract any scop from the function.

static ScopDetection::LoopStats	countBeneficialLoops (Region *R, ScalarEvolution &SE, LoopInfo &LI, unsigned MinProfitableTrips)
	Count the number of loops and the maximal loop depth in `R`.

Detailed Description

Pass to detect the maximal static control parts (Scops) of a function.

Definition at line 133 of file ScopDetection.h.

Member Typedef Documentation

◆ const_iterator

using polly::ScopDetection::const_iterator = RegionSet::const_iterator

Definition at line 553 of file ScopDetection.h.

◆ DetectionContextMapTy

using polly::ScopDetection::DetectionContextMapTy = DenseMap<BBPair, std::unique_ptr<DetectionContext> >

private

Map to remember detection contexts for all regions.

Definition at line 216 of file ScopDetection.h.

◆ iterator

using polly::ScopDetection::iterator = RegionSet::iterator

Definition at line 552 of file ScopDetection.h.

◆ RegionSet

using polly::ScopDetection::RegionSet = SetVector<const Region *>

Definition at line 135 of file ScopDetection.h.

Constructor & Destructor Documentation

◆ ScopDetection()

ScopDetection::ScopDetection	(	const DominatorTree &	DT,
		ScalarEvolution &	SE,
		LoopInfo &	LI,
		RegionInfo &	RI,
		AAResults &	AA,
		OptimizationRemarkEmitter &	ORE
	)

Definition at line 340 of file ScopDetection.cpp.

Member Function Documentation

◆ addOverApproximatedRegion()

bool ScopDetection::addOverApproximatedRegion	(	Region *	AR,
		DetectionContext &	Context
	)		const

private

Add the region AR as over approximated sub-region in Context.

Parameters

AR	The non-affine subregion.
Context	The current detection context.

Returns: True if the subregion can be over approximated, false otherwise.

Definition at line 454 of file ScopDetection.cpp.

References AllowNonAffineSubLoops(), polly::ScopDetection::DetectionContext::BoxedLoopsSet, LI, and polly::ScopDetection::DetectionContext::NonAffineSubRegionSet.

Referenced by isValidBranch(), isValidLoop(), and isValidSwitch().

◆ allBlocksValid()

bool ScopDetection::allBlocksValid ( DetectionContext & Context )

private

Check if all basic block in the region are valid.

Parameters

Context The context of scop detection.

Definition at line 1632 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::CurRegion, hasAffineMemoryAccesses(), isErrorBlock(), polly::ScopDetection::DetectionContext::IsInvalid, isValidCFG(), isValidInstruction(), isValidLoop(), KeepGoing(), and LI.

Referenced by expandRegion(), and isValidRegion().

◆ begin() [1/2]

iterator polly::ScopDetection::begin ( )

inline

Definition at line 555 of file ScopDetection.h.

References ValidRegions.

Referenced by polly::ScopViewer::processFunction(), and ScopViewerWrapperPass::processFunction().

◆ begin() [2/2]

const_iterator polly::ScopDetection::begin ( ) const

inline

Definition at line 558 of file ScopDetection.h.

References ValidRegions.

◆ canUseISLTripCount()

bool ScopDetection::canUseISLTripCount	(	Loop *	L,
		DetectionContext &	Context
	)

private

Can ISL compute the trip count of a loop.

Parameters

L	The loop to check.
Context	The context of scop detection.

Returns: True if ISL can compute the trip count of the loop.

Definition at line 1276 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::IsInvalid, isValidCFG(), polly::ScopDetection::DetectionContext::Log, and polly::RejectLog::size().

Referenced by isValidLoop().

◆ computeAccessFunctions()

bool ScopDetection::computeAccessFunctions	(	DetectionContext &	Context,
		const SCEVUnknown *	BasePointer,
		std::shared_ptr< ArrayShape >	Shape
	)		const

private

Derive access functions for a given base pointer.

Parameters

Context	The current detection context.
Sizes	The sizes of the different array dimensions.
BasePointer	The base pointer of all the array for which to compute access functions.
Shape	The shape that describes the derived array sizes and which should be filled with newly computed access functions.

Returns: True if a set of affine access functions could be derived.

Definition at line 983 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::Accesses, AllowNonAffine(), polly::MemAcc::DelinearizedSubscripts, polly::ScopDetection::DetectionContext::InsnToMemAcc, isAffine(), KeepGoing(), LI, SE, and polly::Value.

Referenced by hasBaseAffineAccesses().

◆ countBeneficialLoops()

ScopDetection::LoopStats ScopDetection::countBeneficialLoops	(	Region *	R,
		ScalarEvolution &	SE,
		LoopInfo &	LI,
		unsigned	MinProfitableTrips
	)

static

Count the number of loops and the maximal loop depth in R.

Parameters

R	The region to check
SE	The scalar evolution analysis.
MinProfitableTrips	The minimum number of trip counts from which a loop is assumed to be profitable and consequently is counted. returns A tuple of number of loops and their maximal depth.

Definition at line 1389 of file ScopDetection.cpp.

References countBeneficialSubLoops(), LI, polly::ScopDetection::LoopStats::MaxDepth, polly::ScopDetection::LoopStats::NumLoops, and SE.

Referenced by detect(), polly::Scop::getStatistics(), isProfitableRegion(), polly::ScopInfo::recompute(), and polly::ScopInfoRegionPass::runOnRegion().

◆ countBeneficialSubLoops()

ScopDetection::LoopStats ScopDetection::countBeneficialSubLoops	(	Loop *	L,
		ScalarEvolution &	SE,
		unsigned	MinProfitableTrips
	)

staticprivate

Count the number of loops and the maximal loop depth in L.

Return the number of loops in L (incl.

Parameters

L	The loop to check.
SE	The scalar evolution analysis.
MinProfitableTrips	The minimum number of trip counts from which a loop is assumed to be profitable and consequently is counted. returns A tuple of number of loops and their maximal depth.

L) that have a trip count that is not known to be less than @MinProfitableTrips.

Definition at line 1367 of file ScopDetection.cpp.

References countBeneficialSubLoops(), polly::ScopDetection::LoopStats::MaxDepth, polly::ScopDetection::LoopStats::NumLoops, and SE.

Referenced by countBeneficialLoops(), and countBeneficialSubLoops().

◆ detect()

void ScopDetection::detect ( Function & F )

◆ emitMissedRemarks()

void ScopDetection::emitMissedRemarks ( const Function & F )

Emit rejection remarks for all rejected regions.

Parameters

F	The function to emit remarks for.

Definition at line 1832 of file ScopDetection.cpp.

References DetectionContextMap, polly::emitRejectionRemarks(), polly::RejectLog::hasErrors(), polly::ScopDetection::DetectionContext::Log, and ORE.

Referenced by detect().

◆ end() [1/2]

iterator polly::ScopDetection::end ( )

inline

Definition at line 556 of file ScopDetection.h.

References ValidRegions.

Referenced by polly::ScopViewer::processFunction(), and ScopViewerWrapperPass::processFunction().

◆ end() [2/2]

const_iterator polly::ScopDetection::end ( ) const

inline

Definition at line 559 of file ScopDetection.h.

References ValidRegions.

◆ expandRegion()

Region * ScopDetection::expandRegion ( Region & R )

private

Try to expand the region R.

If R can be expanded return the expanded region, NULL otherwise.

Definition at line 1486 of file ScopDetection.cpp.

References AA, allBlocksValid(), DetectionContextMap, polly::Entry, polly::getBBPairForRegion(), polly::RejectLog::hasErrors(), polly::ScopDetection::DetectionContext::Log, POLLY_DEBUG, and removeCachedResults().

Referenced by findScops().

◆ findScops()

void ScopDetection::findScops ( Region & R )

private

Find the Scops in this region tree.

Parameters

The	region tree to scan for scops.

Definition at line 1566 of file ScopDetection.cpp.

References AA, assert, DetectionContextMap, polly::Entry, expandRegion(), findScops(), polly::getBBPairForRegion(), polly::RejectLog::hasErrors(), polly::ScopDetection::DetectionContext::IsInvalid, isValidRegion(), KeepGoing(), LI, lookupRejectionLog(), polly::PollyProcessUnprofitable, regionWithoutLoops(), removeCachedResults(), removeCachedResultsRecursively(), and ValidRegions.

Referenced by detect(), and findScops().

◆ getDelinearizationTerms()

SmallVector< const SCEV *, 4 > ScopDetection::getDelinearizationTerms	(	DetectionContext &	Context,
		const SCEVUnknown *	BasePointer
	)		const

private

Find for a given base pointer terms that hint towards dimension sizes of a multi-dimensional array.

Parameters

Context	The current detection context.
BasePointer	A base pointer indicating the virtual array we are interested in.

Definition at line 869 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::Accesses, polly::ScopDetection::DetectionContext::CurRegion, and SE.

Referenced by hasBaseAffineAccesses().

◆ getDetectionContext()

ScopDetection::DetectionContext * ScopDetection::getDetectionContext ( const Region * R ) const

Return the detection context for R, nullptr if R was invalid.

Definition at line 1956 of file ScopDetection.cpp.

References DetectionContextMap, and polly::getBBPairForRegion().

Referenced by polly::ScopBuilder::buildScop(), and lookupRejectionLog().

◆ getLI()

LoopInfo * polly::ScopDetection::getLI ( ) const

inline

Get the LoopInfo stored in this pass.

Definition at line 522 of file ScopDetection.h.

References LI.

◆ getNextID()

int polly::ScopDetection::getNextID ( )

inline

Definition at line 201 of file ScopDetection.h.

References NextScopID.

Referenced by polly::ScopBuilder::buildScop().

◆ getRI()

RegionInfo * polly::ScopDetection::getRI ( ) const

inline

Get the RegionInfo stored in this pass.

This was added to give the DOT printer easy access to this information.

Definition at line 519 of file ScopDetection.h.

References RI.

Referenced by llvm::GraphTraits< polly::ScopDetection * >::getEntryNode(), and llvm::DOTGraphTraits< polly::ScopDetection * >::getNodeLabel().

◆ hasAffineMemoryAccesses()

bool ScopDetection::hasAffineMemoryAccesses ( DetectionContext & Context ) const

private

Delinearize all non affine memory accesses and return false when there exists a non affine memory access that cannot be delinearized.

Return true when all array accesses are affine after delinearization.

Definition at line 1053 of file ScopDetection.cpp.

References AllowNonAffine(), hasBaseAffineAccesses(), polly::ScopDetection::DetectionContext::HasUnknownAccess, polly::ScopDetection::DetectionContext::IsInvalid, KeepGoing(), and polly::ScopDetection::DetectionContext::NonAffineAccesses.

Referenced by allBlocksValid().

◆ hasBaseAffineAccesses()

bool ScopDetection::hasBaseAffineAccesses	(	DetectionContext &	Context,
		const SCEVUnknown *	BasePointer,
		Loop *	Scope
	)		const

private

Check if all accesses to a given BasePointer are affine.

Parameters

Context	The current detection context.
BasePointer	the base pointer we are interested in.
Scope	The location where `BasePointer` is being used.
True	if consistent (multi-dimensional) array accesses could be derived for this array.

Definition at line 1036 of file ScopDetection.cpp.

References computeAccessFunctions(), polly::ScopDetection::DetectionContext::ElementSize, getDelinearizationTerms(), hasValidArraySizes(), and SE.

Referenced by hasAffineMemoryAccesses().

◆ hasPossiblyDistributableLoop()

bool ScopDetection::hasPossiblyDistributableLoop ( DetectionContext & Context ) const

private

Check if the unique affine loop might be amendable to distribution.

This function checks if the number of non-trivial blocks in the unique affine loop in Context.CurRegion is at least two, thus if the loop might be amendable to distribution.

Parameters

Context The context of scop detection.

Returns: True only if the affine loop might be amendable to distributable.

Definition at line 1697 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::BoxedLoopsSet, polly::ScopDetection::DetectionContext::CurRegion, and LI.

Referenced by isProfitableRegion().

◆ hasSufficientCompute()

bool ScopDetection::hasSufficientCompute	(	DetectionContext &	Context,
		int	NumAffineLoops
	)		const

private

Check if a region has sufficient compute instructions.

This function checks if a region has a non-trivial number of instructions in each loop. This can be used as an indicator whether a loop is worth optimizing.

Parameters

Context	The context of scop detection.
NumLoops	The number of loops in the region.

Returns: True if region is has sufficient compute instructions, false otherwise.

Definition at line 1681 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::CurRegion, LI, and ProfitabilityMinPerLoopInstructions().

Referenced by isProfitableRegion().

◆ hasValidArraySizes()

bool ScopDetection::hasValidArraySizes	(	DetectionContext &	Context,
		SmallVectorImpl< const SCEV * > &	Sizes,
		const SCEVUnknown *	BasePointer,
		Loop *	Scope
	)		const

private

Check if the dimension size of a delinearized array is valid.

Parameters

Context	The current detection context.
Sizes	The sizes of the different array dimensions.
BasePointer	The base pointer we are interested in.
Scope	The location where `BasePointer` is being used.

Returns: True if one or more array sizes could be derived - meaning: we see this array as multi-dimensional.

Definition at line 918 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::Accesses, AllowNonAffine(), polly::ScopDetection::DetectionContext::CurRegion, DT, polly::hasScalarDepsInsideRegion(), isAffine(), polly::isHoistableLoad(), KeepGoing(), LI, polly::ScopDetection::DetectionContext::RequiredILS, SE, and polly::Value.

Referenced by hasBaseAffineAccesses().

◆ invalid()

template<class RR , typename... Args>

bool ScopDetection::invalid	(	DetectionContext &	Context,
		bool	Assert,
		Args &&...	Arguments
	)		const

inlineprivate

Track diagnostics for invalid scops.

Parameters

Context	The context of scop detection.
Assert	Throw an assert in verify mode or not.
Args	Argument list that gets passed to the constructor of RR.

Definition at line 399 of file ScopDetection.cpp.

References assert, polly::RejectReason::getMessage(), polly::ScopDetection::DetectionContext::IsInvalid, polly::ScopDetection::DetectionContext::Log, POLLY_DEBUG, polly::RejectLog::report(), and polly::ScopDetection::DetectionContext::Verifying.

◆ involvesMultiplePtrs()

bool ScopDetection::involvesMultiplePtrs	(	const SCEV *	S0,
		const SCEV *	S1,
		Loop *	Scope
	)		const

private

Check if S0 and S1 do contain multiple possibly aliasing pointers.

Parameters

S0	A expression to check.
S1	Another expression to check or nullptr.
Scope	The loop/scope the expressions are checked in.

Returns: True, if multiple possibly aliasing pointers are used in S0 (and S1 if given).

Definition at line 508 of file ScopDetection.cpp.

References AA, polly::findValues(), S1(), and SE.

Referenced by isValidBranch(), and isValidSwitch().

◆ isAffine()

bool ScopDetection::isAffine	(	const SCEV *	S,
		Loop *	Scope,
		DetectionContext &	Context
	)		const

private

Check if the SCEV S is affine in the current Context.

This will also use a heuristic to decide if we want to require loads to be invariant to make the expression affine or if we want to treat is as non-affine.

Parameters

S	The expression to be checked.
Scope	The loop nest in which `S` is used.
Context	The context of scop detection.

Definition at line 542 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::CurRegion, polly::isAffineExpr(), onlyValidRequiredInvariantLoads(), and SE.

Referenced by computeAccessFunctions(), hasValidArraySizes(), isValidAccess(), isValidBranch(), isValidIntrinsicInst(), and isValidSwitch().

◆ isErrorBlock()

bool ScopDetection::isErrorBlock	(	llvm::BasicBlock &	BB,
		const llvm::Region &	R
	)

Check if the block is a error block.

A error block is currently any block that fulfills at least one of the following conditions:

It is terminated by an unreachable instruction
It contains a call to a non-pure function that is not immediately dominated by a loop header and that does not dominate the region exit. This is a heuristic to pick only error blocks that are conditionally executed and can be assumed to be not executed at all without the domains being available.

Parameters

BB	The block to check.
R	The analyzed region.

Returns: True if the block is a error block, false otherwise.

Definition at line 1473 of file ScopDetection.cpp.

References DT, ErrorBlockCache, isErrorBlockImpl(), LI, and PollyAllowErrorBlocks().

Referenced by allBlocksValid(), polly::ScopBuilder::buildAccessFunctions(), polly::ScopBuilder::buildScop(), containsErrorBlock(), and isValidInstruction().

◆ isInvariant()

bool ScopDetection::isInvariant	(	Value &	Val,
		const Region &	Reg,
		DetectionContext &	Ctx
	)		const

private

Check if a value is invariant in the region Reg.

Parameters

Val	Value to check for invariance.
Reg	The region to consider for the invariance of Val.
Ctx	The current detection context.

Returns: True if the value represented by Val is invariant in the region identified by Reg.

Definition at line 803 of file ScopDetection.cpp.

References Ctx, and LI.

Referenced by isValidAccess().

◆ isMaxRegionInScop()

bool ScopDetection::isMaxRegionInScop	(	const Region &	R,
		bool	Verify = `true`
	)

Is the region is the maximum region of a Scop?

Parameters

R	The Region to test if it is maximum.
Verify	Rerun the scop detection to verify SCoP was not invalidated meanwhile. Do not use if the region's DetectionContect is referenced by a Scop that is still to be processed.

Returns: Return true if R is the maximum Region in a Scop, false otherwise.

Definition at line 419 of file ScopDetection.cpp.

References AA, DetectionContextMap, polly::Entry, polly::getBBPairForRegion(), isValidRegion(), ValidRegions, and Verify().

Referenced by polly::ScopInfo::recompute(), polly::FunctionToScopPassAdaptor< ScopPassT >::run(), and verifyRegion().

◆ isProfitableRegion()

bool ScopDetection::isProfitableRegion ( DetectionContext & Context ) const

private

Check if a region is profitable to optimize.

Regions that are unlikely to expose interesting optimization opportunities are called 'unprofitable' and may be skipped during scop detection.

Parameters

Context The context of scop detection.

Returns: True if region is profitable to optimize, false otherwise.

Definition at line 1717 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::BoxedLoopsSet, countBeneficialLoops(), polly::ScopDetection::DetectionContext::CurRegion, polly::ScopDetection::DetectionContext::hasLoads, hasPossiblyDistributableLoop(), polly::ScopDetection::DetectionContext::hasStores, hasSufficientCompute(), LI, MIN_LOOP_TRIP_COUNT, polly::ScopDetection::LoopStats::NumLoops, polly::PollyProcessUnprofitable, and SE.

Referenced by detect().

◆ isReducibleRegion()

bool ScopDetection::isReducibleRegion	(	Region &	R,
		DebugLoc &	DbgLoc
	)		const

private

Check if a region is reducible or not.

Parameters

Region	The region to check.
DbgLoc	Parameter to save the location of instruction that causes irregular control flow if the region is irreducible.

Returns: True if R is reducible, false otherwise.

Enum for coloring BBs in Region.

WHITE - Unvisited BB in DFS walk. GREY - BBs which are currently on the DFS stack for processing. BLACK - Visited and completely processed BB.

Definition at line 1840 of file ScopDetection.cpp.

References DT.

Referenced by isValidRegion().

◆ isValidAccess()

bool ScopDetection::isValidAccess	(	Instruction *	Inst,
		const SCEV *	AF,
		const SCEVUnknown *	BP,
		DetectionContext &	Context
	)		const

private

Check if the memory access caused by Inst is valid.

Parameters

Inst	The access instruction.
AF	The access function.
BP	The access base pointer.
Context	The current detection context.

Definition at line 1071 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::Accesses, AllowDifferentTypes(), AllowNonAffine(), polly::ScopDetection::DetectionContext::AST, polly::ScopDetection::DetectionContext::BoxedLoopsSet, polly::ScopDetection::DetectionContext::CurRegion, DT, polly::ScopDetection::DetectionContext::ElementSize, polly::findLoops(), IgnoreAliasing(), isAffine(), polly::isHoistableLoad(), isInvariant(), LI, polly::ScopDetection::DetectionContext::NonAffineAccesses, polly::PollyDelinearize, polly::PollyUseRuntimeAliasChecks, polly::ScopDetection::DetectionContext::RequiredILS, SE, and polly::Value.

Referenced by isValidIntrinsicInst(), and isValidMemoryAccess().

◆ isValidBranch()

bool ScopDetection::isValidBranch	(	BasicBlock &	BB,
		BranchInst *	BI,
		Value *	Condition,
		bool	IsLoopBranch,
		DetectionContext &	Context
	)

private

Check if the branch BI with condition Condition is valid.

Parameters

BB	The block to check.
BI	The branch to check.
Condition	The branch condition.
IsLoopBranch	Flag to indicate the branch is a loop exit/latch.
Context	The context of scop detection.

Definition at line 578 of file ScopDetection.cpp.

References addOverApproximatedRegion(), AllowNonAffineSubRegions(), polly::ScopDetection::DetectionContext::CurRegion, polly::getUniqueNonErrorValue(), involvesMultiplePtrs(), isAffine(), isValidBranch(), LI, polly::PHI, polly::PollyAllowUnsignedOperations, polly::ScopDetection::DetectionContext::RequiredILS, RI, SE, polly::tryForwardThroughPHI(), and polly::Value.

Referenced by isValidBranch(), and isValidCFG().

◆ isValidCallInst()

bool ScopDetection::isValidCallInst	(	CallInst &	CI,
		DetectionContext &	Context
	)		const

private

Check if a call instruction can be part of a Scop.

Parameters

CI	The call instruction to check.
Context	The current detection context.

Definition at line 690 of file ScopDetection.cpp.

References AA, AllowModrefCall(), polly::ScopDetection::DetectionContext::AST, Function, polly::ScopDetection::DetectionContext::HasUnknownAccess, polly::isDebugCall(), isValidIntrinsicInst(), LI, POLLY_DEBUG, and SE.

Referenced by isValidInstruction().

◆ isValidCFG()

bool ScopDetection::isValidCFG	(	BasicBlock &	BB,
		bool	IsLoopBranch,
		bool	AllowUnreachable,
		DetectionContext &	Context
	)

private

Check if the control flow in a basic block is valid.

This function checks if a certain basic block is terminated by a Terminator instruction we can handle or, if this is not the case, registers this basic block as the start of a non-affine region.

This function optionally allows unreachable statements.

Parameters

BB	The BB to check the control flow.
IsLoopBranch	Flag to indicate the branch is a loop exit/latch.
AllowUnreachable	Allow unreachable statements.
Context	The context of scop detection.

Definition at line 658 of file ScopDetection.cpp.

References assert, polly::ScopDetection::DetectionContext::CurRegion, polly::getConditionFromTerminator(), isValidBranch(), isValidSwitch(), and polly::Value.

Referenced by allBlocksValid(), and canUseISLTripCount().

◆ isValidFunction()

bool ScopDetection::isValidFunction ( Function & F )

staticprivate

Check if the function F is marked as invalid.

Note: An OpenMP subfunction will be marked as invalid.

Definition at line 1817 of file ScopDetection.cpp.

References polly::PollySkipFnAttr.

Referenced by detect().

◆ isValidInstruction()

bool ScopDetection::isValidInstruction	(	Instruction &	Inst,
		DetectionContext &	Context
	)

private

Check if an instruction can be part of a Scop.

Parameters

Inst	The instruction to check.
Context	The context of scop detection.

Definition at line 1210 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::CurRegion, polly::MemAccInst::dyn_cast(), polly::ScopDetection::DetectionContext::hasLoads, polly::ScopDetection::DetectionContext::hasStores, isErrorBlock(), isValidCallInst(), isValidMemoryAccess(), and polly::PHI.

Referenced by allBlocksValid().

◆ isValidIntrinsicInst()

bool ScopDetection::isValidIntrinsicInst	(	IntrinsicInst &	II,
		DetectionContext &	Context
	)		const

private

Check if an intrinsic call can be part of a Scop.

Parameters

II	The intrinsic call instruction to check.
Context	The current detection context.

Definition at line 757 of file ScopDetection.cpp.

References isAffine(), polly::isIgnoredIntrinsic(), isValidAccess(), LI, and SE.

Referenced by isValidCallInst().

◆ isValidLoop()

bool ScopDetection::isValidLoop	(	Loop *	L,
		DetectionContext &	Context
	)

private

Is a loop valid with respect to a given region.

Parameters

L	The loop to check.
Context	The context of scop detection.

Definition at line 1303 of file ScopDetection.cpp.

References addOverApproximatedRegion(), AllowNonAffineSubLoops(), AllowNonAffineSubRegions(), canUseISLTripCount(), polly::ScopDetection::DetectionContext::CurRegion, hasExitingBlocks(), RI, and SE.

Referenced by allBlocksValid().

◆ isValidMemoryAccess()

bool ScopDetection::isValidMemoryAccess	(	MemAccInst	Inst,
		DetectionContext &	Context
	)		const

private

Check if a memory access can be part of a Scop.

Parameters

Inst	The instruction accessing the memory.
Context	The context of scop detection.

Definition at line 1198 of file ScopDetection.cpp.

References polly::MemAccInst::getPointerOperand(), isValidAccess(), LI, SE, and polly::Value.

Referenced by isValidInstruction().

◆ isValidRegion()

bool ScopDetection::isValidRegion ( DetectionContext & Context )

private

Check if a region is a Scop.

Parameters

Context The context of scop detection.

Returns: If we short-circuited early to not waste time on known-invalid SCoPs. Use Context.IsInvalid to determine whether the region is a valid SCoP.

Definition at line 1753 of file ScopDetection.cpp.

References allBlocksValid(), polly::ScopDetection::DetectionContext::CurRegion, polly::ScopDetection::DetectionContext::IsInvalid, isReducibleRegion(), OnlyRegion(), POLLY_DEBUG, and polly::PollyAllowFullFunction.

Referenced by findScops(), isMaxRegionInScop(), and verifyRegion().

◆ isValidSwitch()

bool ScopDetection::isValidSwitch	(	BasicBlock &	BB,
		SwitchInst *	SI,
		Value *	Condition,
		bool	IsLoopBranch,
		DetectionContext &	Context
	)		const

private

Check if the switch SI with condition Condition is valid.

Parameters

BB	The block to check.
SI	The switch to check.
Condition	The switch condition.
IsLoopBranch	Flag to indicate the branch is a loop exit/latch.
Context	The context of scop detection.

Definition at line 554 of file ScopDetection.cpp.

References addOverApproximatedRegion(), AllowNonAffineSubRegions(), involvesMultiplePtrs(), isAffine(), LI, RI, and SE.

Referenced by isValidCFG().

◆ lookupRejectionLog()

const RejectLog * ScopDetection::lookupRejectionLog ( const Region * R ) const

Return the set of rejection causes for R.

Definition at line 1963 of file ScopDetection.cpp.

References getDetectionContext(), and polly::ScopDetection::DetectionContext::Log.

Referenced by findScops(), and regionIsInvalidBecause().

◆ markFunctionAsInvalid()

void ScopDetection::markFunctionAsInvalid ( Function * F )

static

Mark the function as invalid so we will not extract any scop from the function.

Parameters

F	The function to mark as invalid.

Definition at line 1813 of file ScopDetection.cpp.

References polly::PollySkipFnAttr.

◆ onlyValidRequiredInvariantLoads()

bool ScopDetection::onlyValidRequiredInvariantLoads	(	InvariantLoadsSetTy &	RequiredILS,
		DetectionContext &	Context
	)		const

private

Check if the given loads could be invariant and can be hoisted.

If true is returned the loads are added to the required invariant loads contained in the Context.

Parameters

RequiredILS	The loads to check.
Context	The current detection context.

Returns: True if all loads can be assumed invariant.

Definition at line 472 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::CurRegion, DT, polly::isHoistableLoad(), LI, polly::ScopDetection::DetectionContext::NonAffineSubRegionSet, polly::PollyInvariantLoadHoisting, polly::ScopDetection::DetectionContext::RequiredILS, and SE.

Referenced by isAffine().

◆ printLocations()

void ScopDetection::printLocations ( Function & F )

private

Print the locations of all detected scops.

Definition at line 1821 of file ScopDetection.cpp.

References polly::getDebugLocation().

Referenced by detect().

◆ regionIsInvalidBecause()

std::string ScopDetection::regionIsInvalidBecause ( const Region * R ) const

Get a message why a region is invalid.

Parameters

R	The region for which we get the error message

Returns: The error or "" if no error appeared.

Definition at line 440 of file ScopDetection.cpp.

References lookupRejectionLog().

◆ removeCachedResults()

void ScopDetection::removeCachedResults ( const Region & R )

private

Remove cached results for R.

Definition at line 1562 of file ScopDetection.cpp.

References ValidRegions.

Referenced by expandRegion(), findScops(), and removeCachedResultsRecursively().

◆ removeCachedResultsRecursively()

void ScopDetection::removeCachedResultsRecursively ( const Region & R )

private

Remove cached results for the children of R recursively.

Definition at line 1553 of file ScopDetection.cpp.

References removeCachedResults(), removeCachedResultsRecursively(), and ValidRegions.

Referenced by findScops(), and removeCachedResultsRecursively().

◆ verifyAnalysis()

void ScopDetection::verifyAnalysis ( )

Verify if all valid Regions in this Function are still valid after some transformations.

Definition at line 1975 of file ScopDetection.cpp.

References ValidRegions, verifyRegion(), and VerifyScops().

◆ verifyRegion()

void ScopDetection::verifyRegion ( const Region & R )

Verify if R is still a valid part of Scop after some transformations.

Parameters

R	The Region to verify.

Definition at line 1968 of file ScopDetection.cpp.

References AA, assert, isMaxRegionInScop(), and isValidRegion().

Referenced by verifyAnalysis().

Member Data Documentation

◆ AA

AAResults& polly::ScopDetection::AA

private

Definition at line 212 of file ScopDetection.h.

Referenced by expandRegion(), findScops(), involvesMultiplePtrs(), isMaxRegionInScop(), isValidCallInst(), and verifyRegion().

◆ DetectionContextMap

DetectionContextMapTy polly::ScopDetection::DetectionContextMap

private

Definition at line 218 of file ScopDetection.h.

Referenced by detect(), emitMissedRemarks(), expandRegion(), findScops(), getDetectionContext(), and isMaxRegionInScop().

◆ DT

const DominatorTree& polly::ScopDetection::DT

private

Analyses used.

Definition at line 208 of file ScopDetection.h.

Referenced by hasValidArraySizes(), isErrorBlock(), isReducibleRegion(), isValidAccess(), and onlyValidRequiredInvariantLoads().

◆ ErrorBlockCache

DenseMap<std::tuple<const BasicBlock *, const Region *>, bool> polly::ScopDetection::ErrorBlockCache

private

Cache for the isErrorBlock function.

Definition at line 222 of file ScopDetection.h.

Referenced by isErrorBlock().

◆ LI

LoopInfo& polly::ScopDetection::LI

private

◆ NextScopID

int polly::ScopDetection::NextScopID = 0

Definition at line 200 of file ScopDetection.h.

Referenced by getNextID().

◆ ORE

OptimizationRemarkEmitter& polly::ScopDetection::ORE

private

OptimizationRemarkEmitter object used to emit diagnostic remarks.

Definition at line 614 of file ScopDetection.h.

Referenced by emitMissedRemarks().

◆ RI

RegionInfo& polly::ScopDetection::RI

private

Definition at line 211 of file ScopDetection.h.

Referenced by detect(), getRI(), isValidBranch(), isValidLoop(), and isValidSwitch().

◆ SE

ScalarEvolution& polly::ScopDetection::SE

private

◆ ValidRegions

RegionSet polly::ScopDetection::ValidRegions

Definition at line 138 of file ScopDetection.h.

Referenced by begin(), detect(), end(), findScops(), isMaxRegionInScop(), removeCachedResults(), removeCachedResultsRecursively(), and verifyAnalysis().

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

Classes

Public Types

Public Member Functions

Public Attributes

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Maximum Region In Scops Iterators

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ DetectionContextMapTy

◆ iterator

◆ RegionSet

Constructor & Destructor Documentation

◆ ScopDetection()

Member Function Documentation

◆ addOverApproximatedRegion()

◆ allBlocksValid()

◆ begin() [1/2]

◆ begin() [2/2]

◆ canUseISLTripCount()

◆ computeAccessFunctions()

◆ countBeneficialLoops()

◆ countBeneficialSubLoops()

◆ detect()

◆ emitMissedRemarks()

◆ end() [1/2]

◆ end() [2/2]

◆ expandRegion()

◆ findScops()

◆ getDelinearizationTerms()

◆ getDetectionContext()

◆ getLI()

◆ getNextID()

◆ getRI()

◆ hasAffineMemoryAccesses()

◆ hasBaseAffineAccesses()

◆ hasPossiblyDistributableLoop()

◆ hasSufficientCompute()

◆ hasValidArraySizes()

◆ invalid()

◆ involvesMultiplePtrs()

◆ isAffine()

◆ isErrorBlock()

◆ isInvariant()

◆ isMaxRegionInScop()

◆ isProfitableRegion()

◆ isReducibleRegion()

◆ isValidAccess()

◆ isValidBranch()

◆ isValidCallInst()

◆ isValidCFG()

◆ isValidFunction()

◆ isValidInstruction()

◆ isValidIntrinsicInst()

◆ isValidLoop()

◆ isValidMemoryAccess()

◆ isValidRegion()

◆ isValidSwitch()

◆ lookupRejectionLog()

◆ markFunctionAsInvalid()

◆ onlyValidRequiredInvariantLoads()

◆ printLocations()

◆ regionIsInvalidBecause()

◆ removeCachedResults()

◆ removeCachedResultsRecursively()

◆ verifyAnalysis()

◆ verifyRegion()

Member Data Documentation

◆ AA

◆ DetectionContextMap

◆ DT

◆ ErrorBlockCache

◆ LI

◆ NextScopID

◆ ORE

◆ RI

◆ SE