Polly 20.0.0git
Macros | Functions | Variables
ScopInfo.cpp File Reference
#include "polly/ScopInfo.h"
#include "polly/LinkAllPasses.h"
#include "polly/Options.h"
#include "polly/ScopBuilder.h"
#include "polly/ScopDetection.h"
#include "polly/Support/GICHelper.h"
#include "polly/Support/ISLOStream.h"
#include "polly/Support/ISLTools.h"
#include "polly/Support/SCEVAffinator.h"
#include "polly/Support/SCEVValidator.h"
#include "polly/Support/ScopHelper.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/RegionIterator.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "isl/aff.h"
#include "isl/local_space.h"
#include "isl/map.h"
#include "isl/options.h"
#include "isl/set.h"
#include <cassert>
#include <numeric>
#include "polly/Support/PollyDebug.h"

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "polly-scops"
 

Functions

 STATISTIC (AssumptionsAliasing, "Number of aliasing assumptions taken.")
 
 STATISTIC (AssumptionsInbounds, "Number of inbounds assumptions taken.")
 
 STATISTIC (AssumptionsWrapping, "Number of wrapping assumptions taken.")
 
 STATISTIC (AssumptionsUnsigned, "Number of unsigned assumptions taken.")
 
 STATISTIC (AssumptionsComplexity, "Number of too complex SCoPs.")
 
 STATISTIC (AssumptionsUnprofitable, "Number of unprofitable SCoPs.")
 
 STATISTIC (AssumptionsErrorBlock, "Number of error block assumptions taken.")
 
 STATISTIC (AssumptionsInfiniteLoop, "Number of bounded loop assumptions taken.")
 
 STATISTIC (AssumptionsInvariantLoad, "Number of invariant loads assumptions taken.")
 
 STATISTIC (AssumptionsDelinearization, "Number of delinearization assumptions taken.")
 
 STATISTIC (NumScops, "Number of feasible SCoPs after ScopInfo")
 
 STATISTIC (NumLoopsInScop, "Number of loops in scops")
 
 STATISTIC (NumBoxedLoops, "Number of boxed loops in SCoPs after ScopInfo")
 
 STATISTIC (NumAffineLoops, "Number of affine loops in SCoPs after ScopInfo")
 
 STATISTIC (NumScopsDepthZero, "Number of scops with maximal loop depth 0")
 
 STATISTIC (NumScopsDepthOne, "Number of scops with maximal loop depth 1")
 
 STATISTIC (NumScopsDepthTwo, "Number of scops with maximal loop depth 2")
 
 STATISTIC (NumScopsDepthThree, "Number of scops with maximal loop depth 3")
 
 STATISTIC (NumScopsDepthFour, "Number of scops with maximal loop depth 4")
 
 STATISTIC (NumScopsDepthFive, "Number of scops with maximal loop depth 5")
 
 STATISTIC (NumScopsDepthLarger, "Number of scops with maximal loop depth 6 and larger")
 
 STATISTIC (MaxNumLoopsInScop, "Maximal number of loops in scops")
 
 STATISTIC (NumValueWrites, "Number of scalar value writes after ScopInfo")
 
 STATISTIC (NumValueWritesInLoops, "Number of scalar value writes nested in affine loops after ScopInfo")
 
 STATISTIC (NumPHIWrites, "Number of scalar phi writes after ScopInfo")
 
 STATISTIC (NumPHIWritesInLoops, "Number of scalar phi writes nested in affine loops after ScopInfo")
 
 STATISTIC (NumSingletonWrites, "Number of singleton writes after ScopInfo")
 
 STATISTIC (NumSingletonWritesInLoops, "Number of singleton writes nested in affine loops after ScopInfo")
 
static cl::opt< bool > PollyRemarksMinimal ("polly-remarks-minimal", cl::desc("Do not emit remarks about assumptions that are known"), cl::Hidden, cl::cat(PollyCategory))
 
static cl::opt< bool > IslOnErrorAbort ("polly-on-isl-error-abort", cl::desc("Abort if an isl error is encountered"), cl::init(true), cl::cat(PollyCategory))
 
static cl::opt< bool > PollyPreciseInbounds ("polly-precise-inbounds", cl::desc("Take more precise inbounds assumptions (do not scale well)"), cl::Hidden, cl::init(false), cl::cat(PollyCategory))
 
static cl::opt< bool > PollyIgnoreParamBounds ("polly-ignore-parameter-bounds", cl::desc("Do not add parameter bounds and do no gist simplify sets accordingly"), cl::Hidden, cl::init(false), cl::cat(PollyCategory))
 
static cl::opt< bool > PollyPreciseFoldAccesses ("polly-precise-fold-accesses", cl::desc("Fold memory accesses to model more possible delinearizations " "(does not scale well)"), cl::Hidden, cl::init(false), cl::cat(PollyCategory))
 
static cl::opt< bool, true > XUseInstructionNames ("polly-use-llvm-names", cl::desc("Use LLVM-IR names when deriving statement names"), cl::location(UseInstructionNames), cl::Hidden, cl::cat(PollyCategory))
 
static cl::opt< bool > PollyPrintInstructions ("polly-print-instructions", cl::desc("Output instructions per ScopStmt"), cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory))
 
static cl::list< std::string > IslArgs ("polly-isl-arg", cl::value_desc("argument"), cl::desc("Option passed to ISL"), cl::cat(PollyCategory))
 
static isl::set addRangeBoundsToSet (isl::set S, const ConstantRange &Range, int dim, isl::dim type)
 
static const ScopArrayInfoidentifyBasePtrOriginSAI (Scop *S, Value *BasePtr)
 
static isl::map getEqualAndLarger (isl::space SetDomain)
 
static isl::set simplifyAssumptionContext (isl::set AssumptionContext, const Scop &S)
 
static std::string toString (AssumptionKind Kind)
 
void updateLoopCountStatistic (ScopDetection::LoopStats Stats, Scop::ScopStatistics ScopStats)
 
 INITIALIZE_PASS_BEGIN (ScopInfoRegionPass, "polly-scops", "Polly - Create polyhedral description of Scops", false, false)
 
 INITIALIZE_PASS_DEPENDENCY (AAResultsWrapperPass)
 
 INITIALIZE_PASS_DEPENDENCY (AssumptionCacheTracker)
 
 INITIALIZE_PASS_DEPENDENCY (LoopInfoWrapperPass)
 
 INITIALIZE_PASS_DEPENDENCY (RegionInfoPass)
 
 INITIALIZE_PASS_DEPENDENCY (ScalarEvolutionWrapperPass)
 
 INITIALIZE_PASS_DEPENDENCY (ScopDetectionWrapperPass)
 
 INITIALIZE_PASS_DEPENDENCY (DominatorTreeWrapperPass)
 
 INITIALIZE_PASS_END (ScopInfoRegionPass, "polly-scops", "Polly - Create polyhedral description of Scops", false, false) namespace
 
 INITIALIZE_PASS_BEGIN (ScopInfoPrinterLegacyRegionPass, "polly-print-scops", "Polly - Print polyhedral description of Scops", false, false)
 
 INITIALIZE_PASS_DEPENDENCY (ScopInfoRegionPass)
 
 INITIALIZE_PASS_END (ScopInfoPrinterLegacyRegionPass, "polly-print-scops", "Polly - Print polyhedral description of Scops", false, false) ScopInfo
 
 INITIALIZE_PASS_BEGIN (ScopInfoWrapperPass, "polly-function-scops", "Polly - Create polyhedral description of all Scops of a function", false, false)
 
 INITIALIZE_PASS_END (ScopInfoWrapperPass, "polly-function-scops", "Polly - Create polyhedral description of all Scops of a function", false, false) namespace
 
 INITIALIZE_PASS_BEGIN (ScopInfoPrinterLegacyFunctionPass, "polly-print-function-scops", "Polly - Print polyhedral description of all Scops of a function", false, false)
 
 INITIALIZE_PASS_DEPENDENCY (ScopInfoWrapperPass)
 

Variables

static int const MaxDisjunctsInContext = 4
 
static int const MaxDisjunktsInDefinedBehaviourContext = 8
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "polly-scops"

Definition at line 77 of file ScopInfo.cpp.

Function Documentation

◆ addRangeBoundsToSet()

static isl::set addRangeBoundsToSet ( isl::set  S,
const ConstantRange &  Range,
int  dim,
isl::dim  type 
)
static

◆ getEqualAndLarger()

static isl::map getEqualAndLarger ( isl::space  SetDomain)
static

◆ identifyBasePtrOriginSAI()

static const ScopArrayInfo * identifyBasePtrOriginSAI ( Scop S,
Value *  BasePtr 
)
static

Definition at line 208 of file ScopInfo.cpp.

Referenced by polly::ScopArrayInfo::ScopArrayInfo().

◆ INITIALIZE_PASS_BEGIN() [1/4]

INITIALIZE_PASS_BEGIN ( ScopInfoPrinterLegacyFunctionPass  ,
"polly-print-function-scops"  ,
"Polly - Print polyhedral description of all Scops of a function"  ,
false  ,
false   
)

◆ INITIALIZE_PASS_BEGIN() [2/4]

INITIALIZE_PASS_BEGIN ( ScopInfoPrinterLegacyRegionPass  ,
"polly-print-scops"  ,
"Polly - Print polyhedral description of Scops"  ,
false  ,
false   
)

◆ INITIALIZE_PASS_BEGIN() [3/4]

INITIALIZE_PASS_BEGIN ( ScopInfoRegionPass  ,
"polly-scops"  ,
"Polly - Create polyhedral description of Scops"  ,
false  ,
false   
)

◆ INITIALIZE_PASS_BEGIN() [4/4]

INITIALIZE_PASS_BEGIN ( ScopInfoWrapperPass  ,
"polly-function-scops"  ,
"Polly - Create polyhedral description of all Scops of a function"  ,
false  ,
false   
)

◆ INITIALIZE_PASS_DEPENDENCY() [1/9]

INITIALIZE_PASS_DEPENDENCY ( AAResultsWrapperPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [2/9]

INITIALIZE_PASS_DEPENDENCY ( AssumptionCacheTracker  )

◆ INITIALIZE_PASS_DEPENDENCY() [3/9]

INITIALIZE_PASS_DEPENDENCY ( DominatorTreeWrapperPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [4/9]

INITIALIZE_PASS_DEPENDENCY ( LoopInfoWrapperPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [5/9]

INITIALIZE_PASS_DEPENDENCY ( RegionInfoPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [6/9]

INITIALIZE_PASS_DEPENDENCY ( ScalarEvolutionWrapperPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [7/9]

INITIALIZE_PASS_DEPENDENCY ( ScopDetectionWrapperPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [8/9]

INITIALIZE_PASS_DEPENDENCY ( ScopInfoRegionPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [9/9]

INITIALIZE_PASS_DEPENDENCY ( ScopInfoWrapperPass  )

◆ INITIALIZE_PASS_END() [1/3]

INITIALIZE_PASS_END ( ScopInfoPrinterLegacyRegionPass  ,
"polly-print-scops"  ,
"Polly - Print polyhedral description of Scops"  ,
false  ,
false   
)

Definition at line 2697 of file ScopInfo.cpp.

◆ INITIALIZE_PASS_END() [2/3]

INITIALIZE_PASS_END ( ScopInfoRegionPass  ,
"polly-scops"  ,
"Polly - Create polyhedral description of Scops"  ,
false  ,
false   
)

Print result from ScopInfoRegionPass.

Definition at line 2647 of file ScopInfo.cpp.

References polly::ScopInfoRegionPass::print().

◆ INITIALIZE_PASS_END() [3/3]

INITIALIZE_PASS_END ( ScopInfoWrapperPass  ,
"polly-function-scops"  ,
"Polly - Create polyhedral description of all Scops of a function"  ,
false  ,
false   
)

Print result from ScopInfoWrapperPass.

Definition at line 2829 of file ScopInfo.cpp.

References Function, and polly::ScopInfoWrapperPass::print().

◆ IslArgs()

static cl::list< std::string > IslArgs ( "polly-isl-arg"  ,
cl::value_desc("argument")  ,
cl::desc("Option passed to ISL")  ,
cl::cat(PollyCategory  
)
static

Referenced by polly::Scop::Scop().

◆ IslOnErrorAbort()

static cl::opt< bool > IslOnErrorAbort ( "polly-on-isl-error-abort"  ,
cl::desc("Abort if an isl error is encountered")  ,
cl::init(true)  ,
cl::cat(PollyCategory  
)
static

Referenced by polly::Scop::Scop().

◆ PollyIgnoreParamBounds()

static cl::opt< bool > PollyIgnoreParamBounds ( "polly-ignore-parameter-bounds"  ,
cl::desc("Do not add parameter bounds and do no gist simplify sets accordingly")  ,
cl::Hidden  ,
cl::init(false)  ,
cl::cat(PollyCategory  
)
static

◆ PollyPreciseFoldAccesses()

static cl::opt< bool > PollyPreciseFoldAccesses ( "polly-precise-fold-accesses"  ,
cl::desc("Fold memory accesses to model more possible delinearizations " "(does not scale well)")  ,
cl::Hidden  ,
cl::init(false)  ,
cl::cat(PollyCategory  
)
static

◆ PollyPreciseInbounds()

static cl::opt< bool > PollyPreciseInbounds ( "polly-precise-inbounds"  ,
cl::desc("Take more precise inbounds assumptions (do not scale well)")  ,
cl::Hidden  ,
cl::init(false)  ,
cl::cat(PollyCategory  
)
static

◆ PollyPrintInstructions()

static cl::opt< bool > PollyPrintInstructions ( "polly-print-instructions"  ,
cl::desc("Output instructions per ScopStmt")  ,
cl::Hidden  ,
cl::Optional  ,
cl::init(false)  ,
cl::cat(PollyCategory  
)
static

◆ PollyRemarksMinimal()

static cl::opt< bool > PollyRemarksMinimal ( "polly-remarks-minimal"  ,
cl::desc("Do not emit remarks about assumptions that are known")  ,
cl::Hidden  ,
cl::cat(PollyCategory  
)
static

◆ simplifyAssumptionContext()

static isl::set simplifyAssumptionContext ( isl::set  AssumptionContext,
const Scop S 
)
static

Definition at line 1540 of file ScopInfo.cpp.

References isl::set::gist_params().

Referenced by polly::Scop::simplifyContexts().

◆ STATISTIC() [1/28]

STATISTIC ( AssumptionsAliasing  ,
"Number of aliasing assumptions taken."   
)

◆ STATISTIC() [2/28]

STATISTIC ( AssumptionsComplexity  ,
"Number of too complex SCoPs."   
)

◆ STATISTIC() [3/28]

STATISTIC ( AssumptionsDelinearization  ,
"Number of delinearization assumptions taken."   
)

◆ STATISTIC() [4/28]

STATISTIC ( AssumptionsErrorBlock  ,
"Number of error block assumptions taken."   
)

◆ STATISTIC() [5/28]

STATISTIC ( AssumptionsInbounds  ,
"Number of inbounds assumptions taken."   
)

◆ STATISTIC() [6/28]

STATISTIC ( AssumptionsInfiniteLoop  ,
"Number of bounded loop assumptions taken."   
)

◆ STATISTIC() [7/28]

STATISTIC ( AssumptionsInvariantLoad  ,
"Number of invariant loads assumptions taken."   
)

◆ STATISTIC() [8/28]

STATISTIC ( AssumptionsUnprofitable  ,
"Number of unprofitable SCoPs."   
)

◆ STATISTIC() [9/28]

STATISTIC ( AssumptionsUnsigned  ,
"Number of unsigned assumptions taken."   
)

◆ STATISTIC() [10/28]

STATISTIC ( AssumptionsWrapping  ,
"Number of wrapping assumptions taken."   
)

◆ STATISTIC() [11/28]

STATISTIC ( MaxNumLoopsInScop  ,
"Maximal number of loops in scops"   
)

◆ STATISTIC() [12/28]

STATISTIC ( NumAffineLoops  ,
"Number of affine loops in SCoPs after ScopInfo"   
)

◆ STATISTIC() [13/28]

STATISTIC ( NumBoxedLoops  ,
"Number of boxed loops in SCoPs after ScopInfo"   
)

◆ STATISTIC() [14/28]

STATISTIC ( NumLoopsInScop  ,
"Number of loops in scops"   
)

◆ STATISTIC() [15/28]

STATISTIC ( NumPHIWrites  ,
"Number of scalar phi writes after ScopInfo"   
)

◆ STATISTIC() [16/28]

STATISTIC ( NumPHIWritesInLoops  ,
"Number of scalar phi writes nested in affine loops after ScopInfo"   
)

◆ STATISTIC() [17/28]

STATISTIC ( NumScops  ,
"Number of feasible SCoPs after ScopInfo"   
)

◆ STATISTIC() [18/28]

STATISTIC ( NumScopsDepthFive  ,
"Number of scops with maximal loop depth 5"   
)

◆ STATISTIC() [19/28]

STATISTIC ( NumScopsDepthFour  ,
"Number of scops with maximal loop depth 4"   
)

◆ STATISTIC() [20/28]

STATISTIC ( NumScopsDepthLarger  ,
"Number of scops with maximal loop depth 6 and larger"   
)

◆ STATISTIC() [21/28]

STATISTIC ( NumScopsDepthOne  ,
"Number of scops with maximal loop depth 1"   
)

◆ STATISTIC() [22/28]

STATISTIC ( NumScopsDepthThree  ,
"Number of scops with maximal loop depth 3"   
)

◆ STATISTIC() [23/28]

STATISTIC ( NumScopsDepthTwo  ,
"Number of scops with maximal loop depth 2"   
)

◆ STATISTIC() [24/28]

STATISTIC ( NumScopsDepthZero  ,
"Number of scops with maximal loop depth 0"   
)

◆ STATISTIC() [25/28]

STATISTIC ( NumSingletonWrites  ,
"Number of singleton writes after ScopInfo"   
)

◆ STATISTIC() [26/28]

STATISTIC ( NumSingletonWritesInLoops  ,
"Number of singleton writes nested in affine loops after ScopInfo"   
)

◆ STATISTIC() [27/28]

STATISTIC ( NumValueWrites  ,
"Number of scalar value writes after ScopInfo"   
)

◆ STATISTIC() [28/28]

STATISTIC ( NumValueWritesInLoops  ,
"Number of scalar value writes nested in affine loops after ScopInfo"   
)

◆ toString()

static std::string toString ( AssumptionKind  Kind)
static

◆ updateLoopCountStatistic()

void updateLoopCountStatistic ( ScopDetection::LoopStats  Stats,
Scop::ScopStatistics  ScopStats 
)

◆ XUseInstructionNames()

static cl::opt< bool, true > XUseInstructionNames ( "polly-use-llvm-names"  ,
cl::desc("Use LLVM-IR names when deriving statement names")  ,
cl::location(UseInstructionNames)  ,
cl::Hidden  ,
cl::cat(PollyCategory  
)
static

Variable Documentation

◆ MaxDisjunctsInContext

int const MaxDisjunctsInContext = 4
static

Definition at line 123 of file ScopInfo.cpp.

Referenced by addRangeBoundsToSet().

◆ MaxDisjunktsInDefinedBehaviourContext

int const MaxDisjunktsInDefinedBehaviourContext = 8
static

Definition at line 127 of file ScopInfo.cpp.

Referenced by polly::Scop::intersectDefinedBehavior().