Polly  6.0.0svn
Classes | Public Types | Public Member Functions | Static 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>

Collaboration diagram for polly::ScopDetection:
Collaboration graph
[legend]

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

 ScopDetection (Function &F, const DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, RegionInfo &RI, AliasAnalysis &AA, OptimizationRemarkEmitter &ORE)
 
RegionInfo * getRI () const
 Get the RegionInfo stored in this pass. More...
 
LoopInfo * getLI () const
 Get the LoopInfo stored in this pass. More...
 
bool isMaxRegionInScop (const Region &R, bool Verify=true) const
 Is the region is the maximum region of a Scop? More...
 
DetectionContextgetDetectionContext (const Region *R) const
 Return the detection context for R, nullptr if R was invalid. More...
 
const RejectLoglookupRejectionLog (const Region *R) const
 Return the set of rejection causes for R. More...
 
bool isNonAffineSubRegion (const Region *SubR, const Region *ScopR) const
 Return true if SubR is a non-affine subregion in ScopR. More...
 
std::string regionIsInvalidBecause (const Region *R) const
 Get a message why a region is invalid. More...
 
void emitMissedRemarks (const Function &F)
 Emit rejection remarks for all rejected regions. More...
 
void verifyAnalysis () const
 Verify if all valid Regions in this Function are still valid after some transformations. More...
 
void verifyRegion (const Region &R) const
 Verify if R is still a valid part of Scop after some transformations. More...
 

Static Public Member Functions

static void markFunctionAsInvalid (Function *F)
 Mark the function as invalid so we will not extract any scop from the function. More...
 
static ScopDetection::LoopStats countBeneficialLoops (Region *R, ScalarEvolution &SE, LoopInfo &LI, unsigned MinProfitableTrips)
 Count the number of loops and the maximal loop depth in R. More...
 

Public Attributes

RegionSet ValidRegions
 

Private Types

using DetectionContextMapTy = DenseMap< BBPair, DetectionContext >
 Map to remember detection contexts for all regions. More...
 

Private Member Functions

void removeCachedResults (const Region &R)
 Remove cached results for R. More...
 
void removeCachedResultsRecursively (const Region &R)
 Remove cached results for the children of R recursively. More...
 
bool involvesMultiplePtrs (const SCEV *S0, const SCEV *S1, Loop *Scope) const
 Check if S0 and S1 do contain multiple possibly aliasing pointers. More...
 
bool addOverApproximatedRegion (Region *AR, DetectionContext &Context) const
 Add the region AR as over approximated sub-region in Context. More...
 
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. More...
 
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. More...
 
bool computeAccessFunctions (DetectionContext &Context, const SCEVUnknown *BasePointer, std::shared_ptr< ArrayShape > Shape) const
 Derive access functions for a given base pointer. More...
 
bool hasBaseAffineAccesses (DetectionContext &Context, const SCEVUnknown *BasePointer, Loop *Scope) const
 Check if all accesses to a given BasePointer are affine. More...
 
bool hasAffineMemoryAccesses (DetectionContext &Context) const
 
Region * expandRegion (Region &R)
 
void findScops (Region &R)
 Find the Scops in this region tree. More...
 
bool allBlocksValid (DetectionContext &Context) const
 Check if all basic block in the region are valid. More...
 
bool hasSufficientCompute (DetectionContext &Context, int NumAffineLoops) const
 Check if a region has sufficient compute instructions. More...
 
bool hasPossiblyDistributableLoop (DetectionContext &Context) const
 Check if the unique affine loop might be amendable to distribution. More...
 
bool isProfitableRegion (DetectionContext &Context) const
 Check if a region is profitable to optimize. More...
 
bool isValidRegion (DetectionContext &Context) const
 Check if a region is a Scop. More...
 
bool isValidIntrinsicInst (IntrinsicInst &II, DetectionContext &Context) const
 Check if an intrinsic call can be part of a Scop. More...
 
bool isValidCallInst (CallInst &CI, DetectionContext &Context) const
 Check if a call instruction can be part of a Scop. More...
 
bool onlyValidRequiredInvariantLoads (InvariantLoadsSetTy &RequiredILS, DetectionContext &Context) const
 Check if the given loads could be invariant and can be hoisted. More...
 
bool isInvariant (Value &Val, const Region &Reg, DetectionContext &Ctx) const
 Check if a value is invariant in the region Reg. More...
 
bool isValidAccess (Instruction *Inst, const SCEV *AF, const SCEVUnknown *BP, DetectionContext &Context) const
 Check if the memory access caused by Inst is valid. More...
 
bool isValidMemoryAccess (MemAccInst Inst, DetectionContext &Context) const
 Check if a memory access can be part of a Scop. More...
 
bool hasScalarDependency (Instruction &Inst, Region &RefRegion) const
 Check if an instruction has any non trivial scalar dependencies as part of a Scop. More...
 
bool isValidInstruction (Instruction &Inst, DetectionContext &Context) const
 Check if an instruction can be part of a Scop. More...
 
bool isValidSwitch (BasicBlock &BB, SwitchInst *SI, Value *Condition, bool IsLoopBranch, DetectionContext &Context) const
 Check if the switch SI with condition Condition is valid. More...
 
bool isValidBranch (BasicBlock &BB, BranchInst *BI, Value *Condition, bool IsLoopBranch, DetectionContext &Context) const
 Check if the branch BI with condition Condition is valid. More...
 
bool isAffine (const SCEV *S, Loop *Scope, DetectionContext &Context) const
 Check if the SCEV S is affine in the current Context. More...
 
bool isValidCFG (BasicBlock &BB, bool IsLoopBranch, bool AllowUnreachable, DetectionContext &Context) const
 Check if the control flow in a basic block is valid. More...
 
bool isValidLoop (Loop *L, DetectionContext &Context) const
 Is a loop valid with respect to a given region. More...
 
bool isValidFunction (Function &F)
 Check if the function F is marked as invalid. More...
 
bool canUseISLTripCount (Loop *L, DetectionContext &Context) const
 Can ISL compute the trip count of a loop. More...
 
void printLocations (Function &F)
 Print the locations of all detected scops. More...
 
bool isReducibleRegion (Region &R, DebugLoc &DbgLoc) const
 Check if a region is reducible or not. More...
 
template<class RR , typename... Args>
bool invalid (DetectionContext &Context, bool Assert, Args &&... Arguments) const
 Track diagnostics for invalid scops. More...
 

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. More...
 

Private Attributes

DetectionContextMapTy DetectionContextMap
 
OptimizationRemarkEmitter & ORE
 OptimizationRemarkEmitter object used to emit diagnostic remarks. More...
 
const DominatorTree & DT
 Analyses used. More...
 
ScalarEvolution & SE
 
LoopInfo & LI
 
RegionInfo & RI
 
AliasAnalysis & AA
 

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
 
iterator begin ()
 
iterator end ()
 
const_iterator begin () const
 
const_iterator end () const
 

Detailed Description

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

Definition at line 144 of file ScopDetection.h.

Member Typedef Documentation

◆ const_iterator

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

Definition at line 592 of file ScopDetection.h.

◆ DetectionContextMapTy

Map to remember detection contexts for all regions.

Definition at line 233 of file ScopDetection.h.

◆ iterator

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

Definition at line 591 of file ScopDetection.h.

◆ RegionSet

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

Definition at line 146 of file ScopDetection.h.

Constructor & Destructor Documentation

◆ ScopDetection()

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

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 450 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) const
private

Check if all basic block in the region are valid.

Parameters
ContextThe context of scop detection.
Returns
True if all blocks in R are valid, false otherwise.

Definition at line 1496 of file ScopDetection.cpp.

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

Referenced by expandRegion(), and isValidRegion().

◆ begin() [1/2]

iterator polly::ScopDetection::begin ( )
inline

Definition at line 594 of file ScopDetection.h.

Referenced by ScopViewer::processFunction().

◆ begin() [2/2]

const_iterator polly::ScopDetection::begin ( ) const
inline

Definition at line 597 of file ScopDetection.h.

◆ canUseISLTripCount()

bool ScopDetection::canUseISLTripCount ( Loop *  L,
DetectionContext Context 
) const
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 1244 of file ScopDetection.cpp.

References isValidCFG().

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 973 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::Accesses, AllowNonAffine(), polly::MemAcc::DelinearizedSubscripts, polly::ScopDetection::DetectionContext::InsnToMemAcc, isAffine(), KeepGoing(), LI, S, 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 1334 of file ScopDetection.cpp.

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

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

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

Definition at line 1312 of file ScopDetection.cpp.

References polly::ScopDetection::LoopStats::MaxDepth, and polly::ScopDetection::LoopStats::NumLoops.

Referenced by countBeneficialLoops().

◆ emitMissedRemarks()

void ScopDetection::emitMissedRemarks ( const Function &  F)

Emit rejection remarks for all rejected regions.

Parameters
FThe function to emit remarks for.

Definition at line 1674 of file ScopDetection.cpp.

References DetectionContextMap, polly::emitRejectionRemarks(), and ORE.

Referenced by ScopDetection().

◆ end() [1/2]

iterator polly::ScopDetection::end ( )
inline

Definition at line 595 of file ScopDetection.h.

Referenced by ScopViewer::processFunction().

◆ end() [2/2]

const_iterator polly::ScopDetection::end ( ) const
inline

Definition at line 598 of file ScopDetection.h.

◆ expandRegion()

Region * ScopDetection::expandRegion ( Region &  R)
private

◆ 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 861 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 1794 of file ScopDetection.cpp.

References DetectionContextMap, and polly::getBBPairForRegion().

Referenced by lookupRejectionLog().

◆ getLI()

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

Get the LoopInfo stored in this pass.

Definition at line 559 of file ScopDetection.h.

References Verify().

◆ getRI()

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

◆ hasAffineMemoryAccesses()

bool ScopDetection::hasAffineMemoryAccesses ( DetectionContext Context) const
private

◆ 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 1025 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 1555 of file ScopDetection.cpp.

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

Referenced by isProfitableRegion().

◆ hasScalarDependency()

bool polly::ScopDetection::hasScalarDependency ( Instruction &  Inst,
Region &  RefRegion 
) const
private

Check if an instruction has any non trivial scalar dependencies as part of a Scop.

Parameters
InstThe instruction to check.
RefRegionThe region in respect to which we check the access function.
Returns
True if the instruction has scalar dependences, false otherwise.

◆ 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 1539 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 910 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 402 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::Log, polly::PollyTrackFailures, 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 504 of file ScopDetection.cpp.

References AA, polly::findValues(), 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 538 of file ScopDetection.cpp.

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

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

◆ 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 794 of file ScopDetection.cpp.

References LI, polly::ScopDetection::DetectionContext::RequiredILS, and SE.

Referenced by isValidAccess().

◆ isMaxRegionInScop()

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

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.
Returns
Return true if R is the maximum Region in a Scop, false otherwise.

Definition at line 420 of file ScopDetection.cpp.

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

Referenced by llvm::DOTGraphTraits< ScopDetectionWrapperPass * >::printRegionCluster(), and verifyRegion().

◆ isNonAffineSubRegion()

bool polly::ScopDetection::isNonAffineSubRegion ( const Region *  SubR,
const Region *  ScopR 
) const

Return true if SubR is a non-affine subregion in ScopR.

◆ 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 1575 of file ScopDetection.cpp.

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

Referenced by ScopDetection().

◆ 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 1682 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
InstThe access instruction.
AFThe access function.
BPThe access base pointer.
ContextThe current detection context.

Definition at line 1061 of file ScopDetection.cpp.

References AllowDifferentTypes(), AllowNonAffine(), DT, polly::findLoops(), polly::hasIVParams(), IgnoreAliasing(), isAffine(), polly::isHoistableLoad(), isInvariant(), LI, polly::PollyDelinearize, polly::PollyUseRuntimeAliasChecks, and SE.

Referenced by isValidIntrinsicInst(), and isValidMemoryAccess().

◆ isValidBranch()

bool ScopDetection::isValidBranch ( BasicBlock &  BB,
BranchInst *  BI,
Value Condition,
bool  IsLoopBranch,
DetectionContext Context 
) const
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.
Returns
True if the branch BI is valid.

Definition at line 574 of file ScopDetection.cpp.

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

Referenced by 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.
Returns
True if the call instruction is valid, false otherwise.

Definition at line 686 of file ScopDetection.cpp.

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

Referenced by isValidInstruction().

◆ isValidCFG()

bool ScopDetection::isValidCFG ( BasicBlock &  BB,
bool  IsLoopBranch,
bool  AllowUnreachable,
DetectionContext Context 
) const
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.
ContextThe context of scop detection.
Returns
True if the BB contains only valid control flow.

Definition at line 654 of file ScopDetection.cpp.

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

Referenced by allBlocksValid(), and canUseISLTripCount().

◆ isValidFunction()

bool ScopDetection::isValidFunction ( Function &  F)
private

Check if the function F is marked as invalid.

Note
An OpenMP subfunction will be marked as invalid.

Definition at line 1659 of file ScopDetection.cpp.

References polly::PollySkipFnAttr.

Referenced by ScopDetection().

◆ isValidInstruction()

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

Check if an instruction can be part of a Scop.

Parameters
InstThe instruction to check.
ContextThe context of scop detection.
Returns
True if the instruction is valid, false otherwise.

Definition at line 1179 of file ScopDetection.cpp.

References polly::ScopDetection::DetectionContext::CurRegion, DT, polly::MemAccInst::dyn_cast(), polly::ScopDetection::DetectionContext::hasLoads, polly::ScopDetection::DetectionContext::hasStores, polly::isErrorBlock(), isValidCallInst(), isValidMemoryAccess(), LI, 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.
Returns
True if the call instruction is valid, false otherwise.

Definition at line 748 of file ScopDetection.cpp.

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

Referenced by isValidCallInst().

◆ isValidLoop()

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

Is a loop valid with respect to a given region.

Parameters
LThe loop to check.
ContextThe context of scop detection.
Returns
True if the loop is valid in the region.

Definition at line 1260 of file ScopDetection.cpp.

References addOverApproximatedRegion(), AllowNonAffineSubLoops(), AllowNonAffineSubRegions(), canUseISLTripCount(), 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.
Returns
True if the memory access is valid, false otherwise.

Definition at line 1167 of file ScopDetection.cpp.

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

Referenced by isValidInstruction().

◆ isValidRegion()

bool ScopDetection::isValidRegion ( DetectionContext Context) const
private

Check if a region is a Scop.

Parameters
ContextThe context of scop detection.
Returns
True if R is a Scop, false otherwise.

Definition at line 1611 of file ScopDetection.cpp.

References allBlocksValid(), polly::ScopDetection::DetectionContext::CurRegion, isReducibleRegion(), OnlyRegion(), 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.
Returns
True if the branch BI is valid.

Definition at line 550 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 1801 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 1655 of file ScopDetection.cpp.

References polly::PollySkipFnAttr.

Referenced by GPUNodeBuilder::createKernelFunction().

◆ 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 468 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 1663 of file ScopDetection.cpp.

References polly::getDebugLocation().

Referenced by ScopDetection().

◆ 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 436 of file ScopDetection.cpp.

References lookupRejectionLog().

Referenced by llvm::DOTGraphTraits< ScopDetectionWrapperPass * >::printRegionCluster().

◆ removeCachedResults()

void ScopDetection::removeCachedResults ( const Region &  R)
private

Remove cached results for R.

Definition at line 1435 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 1426 of file ScopDetection.cpp.

References removeCachedResults(), and ValidRegions.

Referenced by findScops().

◆ verifyAnalysis()

void ScopDetection::verifyAnalysis ( ) const

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

Definition at line 1813 of file ScopDetection.cpp.

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

◆ verifyRegion()

void ScopDetection::verifyRegion ( const Region &  R) const

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

Parameters
RThe Region to verify.

Definition at line 1806 of file ScopDetection.cpp.

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

Referenced by verifyAnalysis().

Member Data Documentation

◆ AA

AliasAnalysis& polly::ScopDetection::AA
private

◆ DetectionContextMap

DetectionContextMapTy polly::ScopDetection::DetectionContextMap
mutableprivate

◆ DT

const DominatorTree& polly::ScopDetection::DT
private

◆ LI

LoopInfo& polly::ScopDetection::LI
private

◆ ORE

OptimizationRemarkEmitter& polly::ScopDetection::ORE
private

OptimizationRemarkEmitter object used to emit diagnostic remarks.

Definition at line 635 of file ScopDetection.h.

Referenced by emitMissedRemarks(), and polly::ScopDetectionWrapperPass::runOnFunction().

◆ RI

RegionInfo& polly::ScopDetection::RI
private

◆ SE

ScalarEvolution& polly::ScopDetection::SE
private

◆ ValidRegions

RegionSet polly::ScopDetection::ValidRegions

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