Polly 19.0.0git
Classes | Public Types | Public Member Functions | Public Attributes | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
polly::ScopDetection Class Reference

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?
 
DetectionContextgetDetectionContext (const Region *R) const
 Return the detection context for R, nullptr if R was invalid.
 
const RejectLoglookupRejectionLog (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
ARThe non-affine subregion.
ContextThe 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
ContextThe context of scop detection.

Definition at line 1631 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

◆ 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
LThe loop to check.
ContextThe context of scop detection.
Returns
True if ISL can compute the trip count of the loop.

Definition at line 1275 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
ContextThe current detection context.
SizesThe sizes of the different array dimensions.
BasePointerThe base pointer of all the array for which to compute access functions.
ShapeThe 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 982 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
RThe region to check
SEThe scalar evolution analysis.
MinProfitableTripsThe 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 1388 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
LThe loop to check.
SEThe scalar evolution analysis.
MinProfitableTripsThe 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 1366 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
FThe function to emit remarks for.

Definition at line 1831 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

◆ 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 1485 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

◆ 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
ContextThe current detection context.
BasePointerA base pointer indicating the virtual array we are interested in.

Definition at line 868 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 1955 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 1052 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
ContextThe current detection context.
BasePointerthe base pointer we are interested in.
ScopeThe location where BasePointer is being used.
Trueif consistent (multi-dimensional) array accesses could be derived for this array.

Definition at line 1035 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
ContextThe context of scop detection.
Returns
True only if the affine loop might be amendable to distributable.

Definition at line 1696 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
ContextThe context of scop detection.
NumLoopsThe number of loops in the region.
Returns
True if region is has sufficient compute instructions, false otherwise.

Definition at line 1680 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
ContextThe current detection context.
SizesThe sizes of the different array dimensions.
BasePointerThe base pointer we are interested in.
ScopeThe 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 917 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
ContextThe context of scop detection.
AssertThrow an assert in verify mode or not.
ArgsArgument 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
S0A expression to check.
S1Another expression to check or nullptr.
ScopeThe 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 507 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
SThe expression to be checked.
ScopeThe loop nest in which S is used.
ContextThe context of scop detection.

Definition at line 541 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
BBThe block to check.
RThe analyzed region.
Returns
True if the block is a error block, false otherwise.

Definition at line 1472 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
ValValue to check for invariance.
RegThe region to consider for the invariance of Val.
CtxThe current detection context.
Returns
True if the value represented by Val is invariant in the region identified by Reg.

Definition at line 802 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
RThe Region to test if it is maximum.
VerifyRerun 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
ContextThe context of scop detection.
Returns
True if region is profitable to optimize, false otherwise.

Definition at line 1716 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
RegionThe region to check.
DbgLocParameter 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 1839 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

◆ 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
BBThe block to check.
BIThe branch to check.
ConditionThe branch condition.
IsLoopBranchFlag to indicate the branch is a loop exit/latch.
ContextThe context of scop detection.

Definition at line 577 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
CIThe call instruction to check.
ContextThe current detection context.

Definition at line 689 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
BBThe BB to check the control flow.
IsLoopBranchFlag to indicate the branch is a loop exit/latch.
AllowUnreachableAllow unreachable statements.
ContextThe context of scop detection.

Definition at line 657 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 1816 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
InstThe instruction to check.
ContextThe context of scop detection.

Definition at line 1209 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
IIThe intrinsic call instruction to check.
ContextThe current detection context.

Definition at line 756 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
LThe loop to check.
ContextThe context of scop detection.

Definition at line 1302 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
InstThe instruction accessing the memory.
ContextThe context of scop detection.

Definition at line 1197 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
ContextThe 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 1752 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
BBThe block to check.
SIThe switch to check.
ConditionThe switch condition.
IsLoopBranchFlag to indicate the branch is a loop exit/latch.
ContextThe context of scop detection.

Definition at line 553 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 1962 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
FThe function to mark as invalid.

Definition at line 1812 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
RequiredILSThe loads to check.
ContextThe 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 1820 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
RThe 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 1561 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 1552 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 1974 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
RThe Region to verify.

Definition at line 1967 of file ScopDetection.cpp.

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

Referenced by verifyAnalysis().

Member Data Documentation

◆ AA

AAResults& polly::ScopDetection::AA
private

◆ DetectionContextMap

DetectionContextMapTy polly::ScopDetection::DetectionContextMap
private

◆ DT

const DominatorTree& polly::ScopDetection::DT
private

◆ 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

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