Polly 19.0.0git
Classes | Typedefs | Enumerations | Functions | Variables
polly Namespace Reference

Classes

struct  ArrayShape
 
struct  Assumption
 Helper struct to remember assumptions. More...
 
struct  AstBuildUserInfo
 Temporary information used when building the ast. More...
 
struct  BandAttr
 Represent the attributes of a loop. More...
 
class  BlockGenerator
 Generate a new basic block for a polyhedral statement. More...
 
struct  CodeGenerationPass
 
struct  CodePreparationPass
 
struct  DeadCodeElimPass
 
struct  DeLICMPass
 
struct  DeLICMPrinterPass
 
struct  DependenceAnalysis
 
class  DependenceInfo
 
struct  DependenceInfoPrinterPass
 
class  DependenceInfoWrapperPass
 Construct a new DependenceInfoWrapper pass. More...
 
class  Dependences
 The accumulated dependence information for a SCoP. More...
 
struct  DumpFunctionPass
 A pass that isolates a function into a new Module and writes it into a file. More...
 
struct  DumpModulePass
 A pass that prints the module into a file. More...
 
struct  ForwardOpTreePass
 
struct  ForwardOpTreePrinterPass
 
struct  FunctionToScopPassAdaptor
 
struct  InvariantAccess
 Helper structure for invariant memory accesses. More...
 
struct  InvariantEquivClassTy
 Type for equivalent invariant accesses and their domain context. More...
 
class  IRInserter
 Add Polly specifics when running IRBuilder. More...
 
class  IslAst
 
struct  IslAstAnalysis
 
class  IslAstInfo
 
class  IslAstInfoWrapperPass
 
struct  IslAstPrinterPass
 
class  IslExprBuilder
 LLVM-IR generator for isl_ast_expr[essions]. More...
 
class  IslMaxOperationsGuard
 Scoped limit of ISL operations. More...
 
class  IslNodeBuilder
 
class  IslQuotaScope
 Scope guard for code that allows arbitrary isl function to return an error if the max-operations quota exceeds. More...
 
struct  IslScheduleOptimizerPass
 
struct  IslScheduleOptimizerPrinterPass
 
struct  JSONExportPass
 This pass exports a scop to a jscop file. More...
 
struct  JSONImportPass
 This pass imports a scop from a jscop file. More...
 
class  MaximalStaticExpansionPass
 
struct  MaximalStaticExpansionPrinterPass
 
struct  MemAcc
 
class  MemAccInst
 Utility proxy to wrap the common members of LoadInst and StoreInst. More...
 
class  MemoryAccess
 Represent memory accesses in statements. More...
 
class  OwningInnerAnalysisManagerProxy
 
class  ParallelLoopGenerator
 The ParallelLoopGenerator allows to create parallelized loops. More...
 
class  ParallelLoopGeneratorGOMP
 This ParallelLoopGenerator subclass handles the generation of parallelized code, utilizing the GNU OpenMP library. More...
 
class  ParallelLoopGeneratorKMP
 This ParallelLoopGenerator subclass handles the generation of parallelized code, utilizing the LLVM OpenMP library. More...
 
class  PerfMonitor
 
class  PolyhedralInfo
 
struct  PruneUnprofitablePass
 
struct  RecursiveScheduleTreeVisitor
 Recursively visit all nodes of a schedule tree. More...
 
class  RegionGenerator
 Generator for new versions of polyhedral region statements. More...
 
class  RejectLog
 Stores all errors that occurred during the detection. More...
 
class  RejectReason
 Base class of all reject reasons found during Scop detection. More...
 
class  ReportAffFunc
 Base class for non-affine reject reasons. More...
 
class  ReportAlias
 Captures errors with aliasing. More...
 
class  ReportAlloca
 Captures errors with alloca instructions. More...
 
class  ReportCFG
 Base class for CFG related reject reasons. More...
 
class  ReportDifferentArrayElementSize
 Report array accesses with differing element size. More...
 
class  ReportEntry
 Captures errors with regions containing the function entry block. More...
 
class  ReportFuncCall
 Captures errors with non-side-effect-known function calls. More...
 
class  ReportIndirectPredecessor
 Captures regions with an IndirectBr predecessor. More...
 
class  ReportIntToPtr
 Captures errors with bad IntToPtr instructions. More...
 
class  ReportInvalidCond
 Captures an invalid condition. More...
 
class  ReportInvalidTerminator
 Captures bad terminator within a Scop candidate. More...
 
class  ReportIrreducibleRegion
 Captures irreducible regions in CFG. More...
 
class  ReportLoopBound
 Captures errors with non affine loop bounds. More...
 
class  ReportLoopHasMultipleExits
 Captures errors when a loop has multiple exists. More...
 
class  ReportLoopHasNoExit
 Captures errors when loop has no exit. More...
 
class  ReportLoopOnlySomeLatches
 Captures errors when not all loop latches are part of the scop. More...
 
class  ReportNoBasePtr
 Captures a missing base pointer. More...
 
class  ReportNonAffBranch
 Captures a non-affine branch. More...
 
class  ReportNonAffineAccess
 Captures a non-affine access function. More...
 
class  ReportNonSimpleMemoryAccess
 Captures errors with non-simple memory accesses. More...
 
class  ReportOther
 Base class for otherwise ungrouped reject reasons. More...
 
class  ReportUndefBasePtr
 Captures an undefined base pointer. More...
 
class  ReportUndefCond
 Captures a condition that is based on an 'undef' value. More...
 
class  ReportUndefOperand
 Captures an undefined operand. More...
 
class  ReportUnknownInst
 Captures errors with unknown instructions. More...
 
class  ReportUnprofitable
 Report regions that seem not profitable to be optimized. More...
 
class  ReportUnreachableInExit
 Captures regions with an unreachable in the exit block. More...
 
class  ReportVariantBasePtr
 Captures a base pointer that is not invariant in the region. More...
 
struct  RuntimeDebugBuilder
 Insert function calls that print certain LLVM values at run time. More...
 
class  SCEVAffinator
 Translate a SCEV to an isl::pw_aff and the domain on which it is invalid. More...
 
struct  ScheduleNodeRewriter
 Recursively visit all nodes of a schedule tree while allowing changes. More...
 
struct  ScheduleTreeVisitor
 This class defines a simple visitor class that may be used for various schedule tree analysis purposes. More...
 
class  Scop
 Static Control Part. More...
 
struct  ScopAnalysis
 
struct  ScopAnalysisPrinterPass
 
class  ScopAnnotator
 Helper class to annotate newly generated SCoPs with metadata. More...
 
class  ScopArrayInfo
 A class to store information about arrays in the SCoP. More...
 
class  ScopBuilder
 Build the Polly IR (Scop and ScopStmt) on a Region. More...
 
class  ScopDetection
 Pass to detect the maximal static control parts (Scops) of a function. More...
 
class  ScopDetectionWrapperPass
 
class  ScopInfo
 
struct  ScopInfoAnalysis
 
struct  ScopInfoPrinterPass
 
class  ScopInfoRegionPass
 The legacy pass manager's analysis pass to compute scop information for a region. More...
 
class  ScopInfoWrapperPass
 The legacy pass manager's analysis pass to compute scop information for the whole function. More...
 
struct  ScopOnlyPrinter
 
struct  ScopOnlyViewer
 
class  ScopPass
 ScopPass - This class adapts the RegionPass interface to allow convenient creation of passes that operate on the Polly IR. More...
 
struct  ScopPrinter
 
struct  ScopStandardAnalysisResults
 
class  ScopStmt
 Statement of the Scop. More...
 
struct  ScopViewer
 
struct  SimplifyPass
 
struct  SimplifyPrinterPass
 
class  SPMUpdater
 
struct  SubtreeReferences
 
class  VirtualInstruction
 This class represents a "virtual instruction", an instruction in a ScopStmt, effectively a ScopStmt/Instruction-pair. More...
 
class  VirtualOperandIterator
 An iterator for virtual operands. More...
 
class  VirtualUse
 Determine the nature of a value's use within a statement. More...
 
class  ZoneAlgorithm
 Base class for algorithms based on zones, like DeLICM. More...
 

Typedefs

typedef llvm::IRBuilder< llvm::ConstantFolder, IRInserterPollyIRBuilder
 
using BBPair = std::pair< llvm::BasicBlock *, llvm::BasicBlock * >
 Type to hold region delimiters (entry & exit block).
 
using ParamSetType = std::set< const SCEV * >
 
using MapInsnToMemAcc = std::map< const Instruction *, MemAcc >
 
using PairInstSCEV = std::pair< const Instruction *, const SCEV * >
 
using AFs = std::vector< PairInstSCEV >
 
using BaseToAFs = std::map< const SCEVUnknown *, AFs >
 
using BaseToElSize = std::map< const SCEVUnknown *, const SCEV * >
 
using RejectReasonPtr = std::shared_ptr< RejectReason >
 
using LoopBoundMapType = std::map< const Loop *, const SCEV * >
 Maps from a loop to the affine function expressing its backedge taken count.
 
using AccFuncVector = std::vector< std::unique_ptr< MemoryAccess > >
 
using MemoryAccessList = std::forward_list< MemoryAccess * >
 Ordered list type to hold accesses.
 
using InvariantAccessesTy = SmallVector< InvariantAccess, 8 >
 Ordered container type to hold invariant accesses.
 
using InvariantEquivClassesTy = SmallVector< InvariantEquivClassTy, 8 >
 Type for invariant accesses equivalence classes.
 
using ScopAnalysisManager = AnalysisManager< Scop, ScopStandardAnalysisResults & >
 
using ScopAnalysisManagerFunctionProxy = InnerAnalysisManagerProxy< ScopAnalysisManager, Function >
 
using FunctionAnalysisManagerScopProxy = OuterAnalysisManagerProxy< FunctionAnalysisManager, Scop, ScopStandardAnalysisResults & >
 
using OwningScopAnalysisManagerFunctionProxy = OwningInnerAnalysisManagerProxy< ScopAnalysisManager, Function >
 
using ScopPassManager = PassManager< Scop, ScopAnalysisManager, ScopStandardAnalysisResults &, SPMUpdater & >
 
typedef std::pair< isl::pw_aff, isl::setPWACtx
 The result type of the SCEVAffinator.
 
using RecordedAssumptionsTy = llvm::SmallVector< Assumption, 8 >
 
using ValueMapT = llvm::DenseMap< llvm::AssertingVH< llvm::Value >, llvm::AssertingVH< llvm::Value > >
 Type to remap values.
 
using InvariantLoadsSetTy = llvm::SetVector< llvm::AssertingVH< llvm::LoadInst > >
 Type for a set of invariant loads.
 
using ParameterSetTy = llvm::SetVector< const llvm::SCEV * >
 Set type for parameters.
 
using BoxedLoopsSetTy = llvm::SetVector< const llvm::Loop * >
 Set of loops (used to remember loops in non-affine subregions).
 

Enumerations

enum  VectorizerChoice { VECTORIZER_NONE , VECTORIZER_STRIPMINE }
 
enum class  OMPGeneralSchedulingType {
  StaticChunked = 33 , StaticNonChunked = 34 , Dynamic = 35 , Guided = 36 ,
  Runtime = 37
}
 General scheduling types of parallel OpenMP for loops. More...
 
enum class  RejectReasonKind {
  CFG , InvalidTerminator , IrreducibleRegion , UnreachableInExit ,
  IndirectPredecessor , LastCFG , AffFunc , UndefCond ,
  InvalidCond , UndefOperand , NonAffBranch , NoBasePtr ,
  UndefBasePtr , VariantBasePtr , NonAffineAccess , DifferentElementSize ,
  LastAffFunc , LoopBound , LoopHasNoExit , LoopHasMultipleExits ,
  LoopOnlySomeLatches , FuncCall , NonSimpleMemoryAccess , Alias ,
  Other , IntToPtr , Alloca , UnknownInst ,
  Entry , Unprofitable , LastOther
}
 
enum class  MemoryKind { Array , Value , PHI , ExitPHI }
 The different memory kinds used in Polly. More...
 
enum  AssumptionKind {
  ALIASING , INBOUNDS , WRAPPING , UNSIGNED ,
  PROFITABLE , ERRORBLOCK , COMPLEXITY , INFINITELOOP ,
  INVARIANTLOAD , DELINEARIZATION
}
 Enumeration of assumptions Polly can take. More...
 
enum  AssumptionSign { AS_ASSUMPTION , AS_RESTRICTION }
 Enum to distinguish between assumptions and restrictions. More...
 
enum  PassPositionChoice { POSITION_EARLY , POSITION_BEFORE_VECTORIZER }
 
enum  OptimizerChoice { OPTIMIZER_NONE , OPTIMIZER_ISL }
 
enum  CodeGenChoice { CODEGEN_FULL , CODEGEN_AST , CODEGEN_NONE }
 

Functions

void registerCanonicalicationPasses (llvm::legacy::PassManagerBase &PM)
 Schedule a set of canonicalization passes to prepare for Polly.
 
llvm::FunctionPassManager buildCanonicalicationPassesForNPM (llvm::ModulePassManager &MPM, llvm::OptimizationLevel Level)
 
void markBlockUnreachable (BasicBlock &Block, PollyIRBuilder &Builder)
 Mark a basic block unreachable.
 
llvm::Pass * createIslAstInfoWrapperPassPass ()
 
llvm::Pass * createIslAstInfoPrinterLegacyPass (llvm::raw_ostream &OS)
 
void addReferencesFromStmt (ScopStmt *Stmt, void *UserPtr, bool CreateScalarRefs=true)
 Extract the out-of-scop values and SCEVs referenced from a ScopStmt.
 
Value * createLoop (Value *LowerBound, Value *UpperBound, Value *Stride, PollyIRBuilder &Builder, LoopInfo &LI, DominatorTree &DT, BasicBlock *&ExitBlock, ICmpInst::Predicate Predicate, ScopAnnotator *Annotator=nullptr, bool Parallel=false, bool UseGuard=true, bool LoopVectDisabled=false)
 Create a scalar do/for-style loop.
 
llvm::DebugLoc createDebugLocForGeneratedCode (Function *F)
 Create a DebugLoc representing generated instructions.
 
std::pair< BBPair, llvm::BranchInst * > executeScopConditionally (Scop &S, llvm::Value *RTC, llvm::DominatorTree &DT, llvm::RegionInfo &RI, llvm::LoopInfo &LI)
 Execute a Scop conditionally wrt RTC.
 
llvm::Pass * createDeadCodeElimWrapperPass ()
 
llvm::Pass * createDeLICMWrapperPass ()
 Create a new DeLICM pass instance.
 
llvm::Pass * createDeLICMPrinterLegacyPass (llvm::raw_ostream &OS)
 
bool isConflicting (isl::union_set ExistingOccupied, isl::union_set ExistingUnused, isl::union_map ExistingKnown, isl::union_map ExistingWrites, isl::union_set ProposedOccupied, isl::union_set ProposedUnused, isl::union_map ProposedKnown, isl::union_map ProposedWrites, llvm::raw_ostream *OS=nullptr, unsigned Indent=0)
 Determine whether two lifetimes are conflicting.
 
llvm::Pass * createDependenceInfoPass ()
 
llvm::Pass * createDependenceInfoPrinterLegacyPass (llvm::raw_ostream &OS)
 
llvm::Pass * createDependenceInfoWrapperPassPass ()
 
llvm::Pass * createDependenceInfoPrinterLegacyFunctionPass (llvm::raw_ostream &OS)
 
isl::union_map flattenSchedule (isl::union_map Schedule)
 Recursively flatten a schedule.
 
llvm::Pass * createFlattenSchedulePass ()
 
llvm::Pass * createFlattenSchedulePrinterLegacyPass (llvm::raw_ostream &OS)
 
llvm::Pass * createForwardOpTreeWrapperPass ()
 
llvm::Pass * createForwardOpTreePrinterLegacyPass (llvm::raw_ostream &OS)
 
llvm::Pass * createJSONExporterPass ()
 
llvm::Pass * createJSONImporterPass ()
 
llvm::Pass * createJSONImporterPrinterLegacyPass (llvm::raw_ostream &OS)
 
llvm::Pass * createCodePreparationPass ()
 
llvm::Pass * createScopInlinerPass ()
 
llvm::Pass * createDOTOnlyPrinterWrapperPass ()
 
llvm::Pass * createDOTOnlyViewerWrapperPass ()
 
llvm::Pass * createDOTPrinterWrapperPass ()
 
llvm::Pass * createDOTViewerWrapperPass ()
 
llvm::Pass * createPollyCanonicalizePass ()
 
llvm::Pass * createPolyhedralInfoPass ()
 
llvm::Pass * createPolyhedralInfoPrinterLegacyPass (llvm::raw_ostream &OS)
 
llvm::Pass * createScopDetectionWrapperPassPass ()
 
llvm::Pass * createScopDetectionPrinterLegacyPass (llvm::raw_ostream &OS)
 
llvm::Pass * createScopInfoRegionPassPass ()
 
llvm::Pass * createScopInfoPrinterLegacyRegionPass (llvm::raw_ostream &OS)
 
llvm::Pass * createScopInfoWrapperPassPass ()
 
llvm::Pass * createScopInfoPrinterLegacyFunctionPass (llvm::raw_ostream &OS)
 
llvm::Pass * createCodeGenerationPass ()
 
llvm::Pass * createIslScheduleOptimizerWrapperPass ()
 
llvm::Pass * createIslScheduleOptimizerPrinterLegacyPass (llvm::raw_ostream &OS)
 
llvm::Pass * createMaximalStaticExpansionPass ()
 
llvm::Pass * createSimplifyWrapperPass (int CallNo=0)
 Create a Simplify pass.
 
llvm::Pass * createSimplifyPrinterLegacyPass (llvm::raw_ostream &OS)
 
llvm::Pass * createPruneUnprofitableWrapperPass ()
 
isl::schedule applyManualTransformations (Scop *S, isl::schedule Sched, const Dependences &D, llvm::OptimizationRemarkEmitter *ORE)
 Apply loop-transformation metadata.
 
isl::schedule_node tryOptimizeMatMulPattern (isl::schedule_node Node, const llvm::TargetTransformInfo *TTI, const Dependences *D)
 Apply the BLIS matmul optimization pattern if possible.
 
void initializePollyPasses (llvm::PassRegistry &Registry)
 
void registerPollyPasses (llvm::PassBuilder &PB)
 
bool isBandMark (const isl::schedule_node &Node)
 Is this node the marker for its parent band?
 
BandAttrgetBandAttr (isl::schedule_node MarkOrBand)
 Extract the BandAttr from a band's wrapping marker.
 
isl::schedule hoistExtensionNodes (isl::schedule Sched)
 Hoist all domains from extension into the root domain node, such that there are no more extension nodes (which isl does not support for some operations).
 
isl::schedule applyFullUnroll (isl::schedule_node BandToUnroll)
 Replace the AST band BandToUnroll by a sequence of all its iterations.
 
isl::schedule applyPartialUnroll (isl::schedule_node BandToUnroll, int Factor)
 Replace the AST band BandToUnroll by a partially unrolled equivalent.
 
isl::schedule applyMaxFission (isl::schedule_node BandToFission)
 Loop-distribute the band BandToFission as much as possible.
 
isl::set getPartialTilePrefixes (isl::set ScheduleRange, int VectorWidth)
 Build the desired set of partial tile prefixes.
 
isl::union_set getIsolateOptions (isl::set IsolateDomain, unsigned OutDimsNum)
 Create an isl::union_set, which describes the isolate option based on IsolateDomain.
 
isl::union_set getDimOptions (isl::ctx Ctx, const char *Option)
 Create an isl::union_set, which describes the specified option for the dimension of the current node.
 
isl::schedule_node tileNode (isl::schedule_node Node, const char *Identifier, llvm::ArrayRef< int > TileSizes, int DefaultTileSize)
 Tile a schedule node.
 
isl::schedule_node applyRegisterTiling (isl::schedule_node Node, llvm::ArrayRef< int > TileSizes, int DefaultTileSize)
 Tile a schedule node and unroll point loops.
 
isl::schedule applyGreedyFusion (isl::schedule Sched, const isl::union_map &Deps)
 Apply greedy fusion.
 
BBPair getBBPairForRegion (const Region *R)
 Return the region delimiters (entry & exit block) of R.
 
void getDebugLocations (const BBPair &P, DebugLoc &Begin, DebugLoc &End)
 Set the begin and end source location for the region limited by P.
 
void emitRejectionRemarks (const BBPair &P, const RejectLog &Log, OptimizationRemarkEmitter &ORE)
 Emit optimization remarks about the rejected regions to the user.
 
raw_ostream & operator<< (raw_ostream &OS, MemoryAccess::ReductionType RT)
 
raw_ostream & operator<< (raw_ostream &OS, const ScopStmt &S)
 Print ScopStmt S to raw_ostream OS.
 
raw_ostream & operator<< (raw_ostream &OS, const Scop &scop)
 Print Scop scop to raw_ostream OS.
 
llvm::Pass * createScopInfoPrinterLegacyRegionPass (raw_ostream &OS)
 
template<typename ScopPassT >
FunctionToScopPassAdaptor< ScopPassT > createFunctionToScopPassAdaptor (ScopPassT Pass)
 
llvm::SmallVector< MemoryAccess *, 32 > getAccessesInOrder (ScopStmt &Stmt)
 Return a vector that contains MemoryAccesses in the order in which they are executed.
 
llvm::FunctionPass * createDumpFunctionWrapperPass (std::string Suffix)
 
llvm::ModulePass * createDumpModuleWrapperPass (std::string Filename, bool IsSuffix)
 Create a pass that prints the module into a file.
 
__isl_give isl_valisl_valFromAPInt (isl_ctx *Ctx, const llvm::APInt Int, bool IsSigned)
 Translate an llvm::APInt to an isl_val.
 
isl::val valFromAPInt (isl_ctx *Ctx, const llvm::APInt Int, bool IsSigned)
 Translate an llvm::APInt to an isl::val.
 
llvm::APInt APIntFromVal (__isl_take isl_val *Val)
 Translate isl_val to llvm::APInt.
 
llvm::APInt APIntFromVal (isl::val V)
 Translate isl::val to llvm::APInt.
 
llvm::raw_ostream & operator<< (llvm::raw_ostream &OS, __isl_keep isl_union_map *Map)
 
llvm::raw_ostream & operator<< (llvm::raw_ostream &OS, __isl_keep isl_map *Map)
 
llvm::raw_ostream & operator<< (llvm::raw_ostream &OS, __isl_keep isl_set *Set)
 
llvm::raw_ostream & operator<< (llvm::raw_ostream &OS, __isl_keep isl_pw_aff *Map)
 
llvm::raw_ostream & operator<< (llvm::raw_ostream &OS, __isl_keep isl_pw_multi_aff *PMA)
 
llvm::raw_ostream & operator<< (llvm::raw_ostream &OS, __isl_keep isl_multi_aff *MA)
 
llvm::raw_ostream & operator<< (llvm::raw_ostream &OS, __isl_keep isl_union_pw_multi_aff *UPMA)
 
llvm::raw_ostream & operator<< (llvm::raw_ostream &OS, __isl_keep isl_schedule *Schedule)
 
llvm::raw_ostream & operator<< (llvm::raw_ostream &OS, __isl_keep isl_space *Space)
 
std::string getIslCompatibleName (const std::string &Prefix, const llvm::Value *Val, long Number, const std::string &Suffix, bool UseInstructionNames)
 Combine Prefix, Val (or Number) and Suffix to an isl-compatible name.
 
std::string getIslCompatibleName (const std::string &Prefix, const std::string &Middle, long Number, const std::string &Suffix, bool UseInstructionNames)
 Combine Prefix, Name (or Number) and Suffix to an isl-compatible name.
 
std::string getIslCompatibleName (const std::string &Prefix, const std::string &Middle, const std::string &Suffix)
 
llvm::DiagnosticInfoOptimizationBase & operator<< (llvm::DiagnosticInfoOptimizationBase &OS, const isl::union_map &Obj)
 
isl::map beforeScatter (isl::map Map, bool Strict)
 Return the range elements that are lexicographically smaller.
 
isl::union_map beforeScatter (isl::union_map UMap, bool Strict)
 Piecewise beforeScatter(isl::map,bool).
 
isl::map afterScatter (isl::map Map, bool Strict)
 Return the range elements that are lexicographically larger.
 
isl::union_map afterScatter (const isl::union_map &UMap, bool Strict)
 Piecewise afterScatter(isl::map,bool).
 
isl::map betweenScatter (isl::map From, isl::map To, bool InclFrom, bool InclTo)
 Construct a range of timepoints between two timepoints.
 
isl::union_map betweenScatter (isl::union_map From, isl::union_map To, bool InclFrom, bool InclTo)
 Piecewise betweenScatter(isl::map,isl::map,bool,bool).
 
isl::map singleton (isl::union_map UMap, isl::space ExpectedSpace)
 If by construction a union map is known to contain only a single map, return it.
 
isl::set singleton (isl::union_set USet, isl::space ExpectedSpace)
 If by construction an isl_union_set is known to contain only a single isl_set, return it.
 
unsigned getNumScatterDims (const isl::union_map &Schedule)
 Determine how many dimensions the scatter space of Schedule has.
 
isl::space getScatterSpace (const isl::union_map &Schedule)
 Return the scatter space of a Schedule.
 
isl::map makeIdentityMap (const isl::set &Set, bool RestrictDomain)
 Construct an identity map for the given domain values.
 
isl::union_map makeIdentityMap (const isl::union_set &USet, bool RestrictDomain)
 Construct an identity map for the given domain values.
 
isl::map reverseDomain (isl::map Map)
 Reverse the nested map tuple in Map's domain.
 
isl::union_map reverseDomain (const isl::union_map &UMap)
 Piecewise reverseDomain(isl::map).
 
isl::set shiftDim (isl::set Set, int Pos, int Amount)
 Add a constant to one dimension of a set.
 
isl::union_set shiftDim (isl::union_set USet, int Pos, int Amount)
 Piecewise shiftDim(isl::set,int,int).
 
isl::map shiftDim (isl::map Map, isl::dim Dim, int Pos, int Amount)
 Add a constant to one dimension of a map.
 
isl::union_map shiftDim (isl::union_map UMap, isl::dim Dim, int Pos, int Amount)
 Add a constant to one dimension of a each map in a union map.
 
void simplify (isl::set &Set)
 Simplify a set inplace.
 
void simplify (isl::union_set &USet)
 Simplify a union set inplace.
 
void simplify (isl::map &Map)
 Simplify a map inplace.
 
void simplify (isl::union_map &UMap)
 Simplify a union map inplace.
 
isl::union_map computeReachingWrite (isl::union_map Schedule, isl::union_map Writes, bool Reverse, bool InclPrevDef, bool InclNextDef)
 Compute the reaching definition statement or the next overwrite for each definition of an array element.
 
isl::union_map computeArrayUnused (isl::union_map Schedule, isl::union_map Writes, isl::union_map Reads, bool ReadEltInSameInst, bool InclLastRead, bool InclWrite)
 Compute the timepoints where the contents of an array element are not used.
 
isl::union_set convertZoneToTimepoints (isl::union_set Zone, bool InclStart, bool InclEnd)
 Convert a zone (range between timepoints) to timepoints.
 
isl::union_map convertZoneToTimepoints (isl::union_map Zone, isl::dim Dim, bool InclStart, bool InclEnd)
 Like convertZoneToTimepoints(isl::union_set,InclStart,InclEnd), but convert either the domain or the range of a map.
 
isl::map convertZoneToTimepoints (isl::map Zone, isl::dim Dim, bool InclStart, bool InclEnd)
 Overload of convertZoneToTimepoints(isl::map,InclStart,InclEnd) to process only a single map.
 
isl::map distributeDomain (isl::map Map)
 Distribute the domain to the tuples of a wrapped range map.
 
isl::union_map distributeDomain (isl::union_map UMap)
 Apply distributeDomain(isl::map) to each map in the union.
 
isl::union_map liftDomains (isl::union_map UMap, isl::union_set Factor)
 Prepend a space to the tuples of a map.
 
isl::union_map applyDomainRange (isl::union_map UMap, isl::union_map Func)
 Apply a map to the 'middle' of another relation.
 
isl::map intersectRange (isl::map Map, isl::union_set Range)
 Intersect the range of Map with Range.
 
isl::map subtractParams (isl::map Map, isl::set Params)
 Subtract the parameter space Params from Map.
 
isl::set subtractParams (isl::set Set, isl::set Params)
 Subtract the parameter space Params from Set.
 
isl::val getConstant (isl::pw_aff PwAff, bool Max, bool Min)
 If PwAff maps to a constant, return said constant.
 
isl::val getConstant (isl::map Map, isl::dim Dim, int Pos)
 If the relation PwAff lies on a hyperplane where the given dimension Pos with the type Dim has a fixed value, then return that value.
 
llvm::iota_range< unsigned > rangeIslSize (unsigned Begin, isl::size End)
 Check that End is valid and return an iterator from Begin to End.
 
bool getPollyDebugFlag ()
 
void findLoops (const llvm::SCEV *Expr, llvm::SetVector< const llvm::Loop * > &Loops)
 Find the loops referenced from a SCEV expression.
 
void findValues (const llvm::SCEV *Expr, llvm::ScalarEvolution &SE, llvm::SetVector< llvm::Value * > &Values)
 Find the values referenced by SCEVUnknowns in a given SCEV expression.
 
bool hasScalarDepsInsideRegion (const llvm::SCEV *Expr, const llvm::Region *R, llvm::Loop *Scope, bool AllowLoops, const InvariantLoadsSetTy &ILS)
 Returns true when the SCEV contains references to instructions within the region.
 
bool isAffineExpr (const llvm::Region *R, llvm::Loop *Scope, const llvm::SCEV *Expression, llvm::ScalarEvolution &SE, InvariantLoadsSetTy *ILS=nullptr)
 
bool isAffineConstraint (llvm::Value *V, const llvm::Region *R, llvm::Loop *Scope, llvm::ScalarEvolution &SE, ParameterSetTy &Params, bool OrExpr=false)
 Check if V describes an affine constraint in R.
 
ParameterSetTy getParamsInAffineExpr (const llvm::Region *R, llvm::Loop *Scope, const llvm::SCEV *Expression, llvm::ScalarEvolution &SE)
 
std::pair< const llvm::SCEVConstant *, const llvm::SCEV * > extractConstantFactor (const llvm::SCEV *M, llvm::ScalarEvolution &SE)
 Extract the constant factors from the multiplication M.
 
const llvm::SCEV * tryForwardThroughPHI (const llvm::SCEV *Expr, llvm::Region &R, llvm::ScalarEvolution &SE, ScopDetection *SD)
 Try to look through PHI nodes, where some incoming edges come from error blocks.
 
llvm::Value * getUniqueNonErrorValue (llvm::PHINode *PHI, llvm::Region *R, ScopDetection *SD)
 Return a unique non-error block incoming value for PHI if available.
 
void recordAssumption (RecordedAssumptionsTy *RecordedAssumptions, AssumptionKind Kind, isl::set Set, llvm::DebugLoc Loc, AssumptionSign Sign, llvm::BasicBlock *BB=nullptr, bool RTC=true)
 Record an assumption for later addition to the assumed context.
 
void simplifyRegion (llvm::Region *R, llvm::DominatorTree *DT, llvm::LoopInfo *LI, llvm::RegionInfo *RI)
 Simplify the region to have a single unconditional entry edge and a single exit edge.
 
void splitEntryBlockForAlloca (llvm::BasicBlock *EntryBlock, llvm::Pass *P)
 Split the entry block of a function to store the newly inserted allocations outside of all Scops.
 
void splitEntryBlockForAlloca (llvm::BasicBlock *EntryBlock, llvm::DominatorTree *DT, llvm::LoopInfo *LI, llvm::RegionInfo *RI)
 Split the entry block of a function to store the newly inserted allocations outside of all Scops.
 
llvm::Value * expandCodeFor (Scop &S, llvm::ScalarEvolution &SE, const llvm::DataLayout &DL, const char *Name, const llvm::SCEV *E, llvm::Type *Ty, llvm::Instruction *IP, ValueMapT *VMap, llvm::BasicBlock *RTCBB)
 Wrapper for SCEVExpander extended to all Polly features.
 
llvm::Value * getConditionFromTerminator (llvm::Instruction *TI)
 Return the condition for the terminator TI.
 
llvm::Loop * getLoopSurroundingScop (Scop &S, llvm::LoopInfo &LI)
 Get the smallest loop that contains S but is not in S.
 
unsigned getNumBlocksInLoop (llvm::Loop *L)
 Get the number of blocks in L.
 
unsigned getNumBlocksInRegionNode (llvm::RegionNode *RN)
 Get the number of blocks in RN.
 
llvm::Loop * getRegionNodeLoop (llvm::RegionNode *RN, llvm::LoopInfo &LI)
 Return the smallest loop surrounding RN.
 
bool isHoistableLoad (llvm::LoadInst *LInst, llvm::Region &R, llvm::LoopInfo &LI, llvm::ScalarEvolution &SE, const llvm::DominatorTree &DT, const InvariantLoadsSetTy &KnownInvariantLoads)
 Check if LInst can be hoisted in R.
 
bool isIgnoredIntrinsic (const llvm::Value *V)
 Return true iff V is an intrinsic that we ignore during code generation.
 
bool canSynthesize (const llvm::Value *V, const Scop &S, llvm::ScalarEvolution *SE, llvm::Loop *Scope)
 Check whether a value an be synthesized by the code generator.
 
llvm::BasicBlock * getUseBlock (const llvm::Use &U)
 Return the block in which a value is used.
 
llvm::Loop * getFirstNonBoxedLoopFor (llvm::Loop *L, llvm::LoopInfo &LI, const BoxedLoopsSetTy &BoxedLoops)
 
llvm::Loop * getFirstNonBoxedLoopFor (llvm::BasicBlock *BB, llvm::LoopInfo &LI, const BoxedLoopsSetTy &BoxedLoops)
 
bool isDebugCall (llvm::Instruction *Inst)
 Is the given instruction a call to a debug function?
 
bool hasDebugCall (ScopStmt *Stmt)
 Does the statement contain a call to a debug function?
 
std::optional< llvm::Metadata * > findMetadataOperand (llvm::MDNode *LoopMD, llvm::StringRef Name)
 Find a property value in a LoopID.
 
bool getBooleanLoopAttribute (llvm::MDNode *LoopID, llvm::StringRef Name)
 Find a boolean property value in a LoopID.
 
std::optional< int > getOptionalIntLoopAttribute (llvm::MDNode *LoopID, llvm::StringRef Name)
 Find an integers property value in a LoopID.
 
bool hasDisableAllTransformsHint (llvm::Loop *L)
 Does the loop's LoopID contain a 'llvm.loop.disable_heuristics' property?
 
bool hasDisableAllTransformsHint (llvm::MDNode *LoopID)
 
isl::id getIslLoopAttr (isl::ctx Ctx, BandAttr *Attr)
 Get an isl::id representing a loop.
 
isl::id createIslLoopAttr (isl::ctx Ctx, llvm::Loop *L)
 Create an isl::id that identifies an original loop.
 
bool isLoopAttr (const isl::id &Id)
 Is Id representing a loop?
 
BandAttrgetLoopAttr (const isl::id &Id)
 Return the BandAttr of a loop's isl::id.
 
void getDebugLocation (const llvm::Region *R, unsigned &LineBegin, unsigned &LineEnd, std::string &FileName)
 Get the location of a region from the debug info.
 
static bool operator== (VirtualInstruction LHS, VirtualInstruction RHS)
 
void markReachable (Scop *S, LoopInfo *LI, DenseSet< VirtualInstruction > &UsedInsts, DenseSet< MemoryAccess * > &UsedAccs, ScopStmt *OnlyLocal=nullptr)
 Find all reachable instructions and accesses.
 
isl::union_map filterKnownValInst (const isl::union_map &UMap)
 Return only the mappings that map to known values.
 
isl::union_map makeUnknownForDomain (isl::union_set Domain)
 Create a domain-to-unknown value mapping.
 
template<typename T >
std::string operator+ (Twine LHS, const T &RHS)
 Small string conversion via raw_string_stream.
 
static cl::opt< bool > PollyEnabled ("polly", cl::desc("Enable the polly optimizer (with -O1, -O2 or -O3)"), cl::cat(PollyCategory))
 
static cl::opt< bool > PollyDetectOnly ("polly-only-scop-detection", cl::desc("Only run scop detection, but no other optimizations"), cl::cat(PollyCategory))
 
static cl::opt< PassPositionChoicePassPosition ("polly-position", cl::desc("Where to run polly in the pass pipeline"), cl::values(clEnumValN(POSITION_EARLY, "early", "Before everything"), clEnumValN(POSITION_BEFORE_VECTORIZER, "before-vectorizer", "Right before the vectorizer")), cl::Hidden, cl::init(POSITION_BEFORE_VECTORIZER), cl::cat(PollyCategory))
 
static cl::opt< OptimizerChoiceOptimizer ("polly-optimizer", cl::desc("Select the scheduling optimizer"), cl::values(clEnumValN(OPTIMIZER_NONE, "none", "No optimizer"), clEnumValN(OPTIMIZER_ISL, "isl", "The isl scheduling optimizer")), cl::Hidden, cl::init(OPTIMIZER_ISL), cl::cat(PollyCategory))
 
static cl::opt< CodeGenChoiceCodeGeneration ("polly-code-generation", cl::desc("How much code-generation to perform"), cl::values(clEnumValN(CODEGEN_FULL, "full", "AST and IR generation"), clEnumValN(CODEGEN_AST, "ast", "Only AST generation"), clEnumValN(CODEGEN_NONE, "none", "No code generation")), cl::Hidden, cl::init(CODEGEN_FULL), cl::cat(PollyCategory))
 
static cl::opt< VectorizerChoice, true > Vectorizer ("polly-vectorizer", cl::desc("Select the vectorization strategy"), cl::values(clEnumValN(VECTORIZER_NONE, "none", "No Vectorization"), clEnumValN(VECTORIZER_STRIPMINE, "stripmine", "Strip-mine outer loops for the loop-vectorizer to trigger")), cl::location(PollyVectorizerChoice), cl::init(VECTORIZER_NONE), cl::cat(PollyCategory))
 
static cl::opt< bool > ImportJScop ("polly-import", cl::desc("Import the polyhedral description of the detected Scops"), cl::Hidden, cl::cat(PollyCategory))
 
static cl::opt< bool > FullyIndexedStaticExpansion ("polly-enable-mse", cl::desc("Fully expand the memory accesses of the detected Scops"), cl::Hidden, cl::cat(PollyCategory))
 
static cl::opt< bool > ExportJScop ("polly-export", cl::desc("Export the polyhedral description of the detected Scops"), cl::Hidden, cl::cat(PollyCategory))
 
static cl::opt< bool > DeadCodeElim ("polly-run-dce", cl::desc("Run the dead code elimination"), cl::Hidden, cl::cat(PollyCategory))
 
static cl::opt< bool > PollyViewer ("polly-show", cl::desc("Highlight the code regions that will be optimized in a " "(CFG BBs and LLVM-IR instructions)"), cl::cat(PollyCategory))
 
static cl::opt< bool > PollyOnlyViewer ("polly-show-only", cl::desc("Highlight the code regions that will be optimized in " "a (CFG only BBs)"), cl::init(false), cl::cat(PollyCategory))
 
static cl::opt< bool > PollyPrinter ("polly-dot", cl::desc("Enable the Polly DOT printer in -O3"), cl::Hidden, cl::value_desc("Run the Polly DOT printer at -O3"), cl::init(false), cl::cat(PollyCategory))
 
static cl::opt< bool > PollyOnlyPrinter ("polly-dot-only", cl::desc("Enable the Polly DOT printer in -O3 (no BB content)"), cl::Hidden, cl::value_desc("Run the Polly DOT printer at -O3 (no BB content"), cl::init(false), cl::cat(PollyCategory))
 
static cl::opt< bool > CFGPrinter ("polly-view-cfg", cl::desc("Show the Polly CFG right after code generation"), cl::Hidden, cl::init(false), cl::cat(PollyCategory))
 
static cl::opt< bool > EnableForwardOpTree ("polly-enable-optree", cl::desc("Enable operand tree forwarding"), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
 
static cl::opt< bool > DumpBefore ("polly-dump-before", cl::desc("Dump module before Polly transformations into a file " "suffixed with \"-before\""), cl::init(false), cl::cat(PollyCategory))
 
static cl::list< std::string > DumpBeforeFile ("polly-dump-before-file", cl::desc("Dump module before Polly transformations to the given file"), cl::cat(PollyCategory))
 
static cl::opt< bool > DumpAfter ("polly-dump-after", cl::desc("Dump module after Polly transformations into a file " "suffixed with \"-after\""), cl::init(false), cl::cat(PollyCategory))
 
static cl::list< std::string > DumpAfterFile ("polly-dump-after-file", cl::desc("Dump module after Polly transformations to the given file"), cl::cat(PollyCategory))
 
static cl::opt< bool > EnableDeLICM ("polly-enable-delicm", cl::desc("Eliminate scalar loop carried dependences"), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
 
static cl::opt< bool > EnableSimplify ("polly-enable-simplify", cl::desc("Simplify SCoP after optimizations"), cl::init(true), cl::cat(PollyCategory))
 
static cl::opt< bool > EnablePruneUnprofitable ("polly-enable-prune-unprofitable", cl::desc("Bail out on unprofitable SCoPs before rescheduling"), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
 
static bool shouldEnablePollyForOptimization ()
 
static bool shouldEnablePollyForDiagnostic ()
 
static void buildCommonPollyPipeline (FunctionPassManager &PM, OptimizationLevel Level, bool EnableForOpt)
 Register Polly passes such that they form a polyhedral optimizer.
 
static void buildEarlyPollyPipeline (llvm::ModulePassManager &MPM, llvm::OptimizationLevel Level)
 
static void buildLatePollyPipeline (FunctionPassManager &PM, llvm::OptimizationLevel Level)
 
static OwningScopAnalysisManagerFunctionProxy createScopAnalyses (FunctionAnalysisManager &FAM, PassInstrumentationCallbacks *PIC)
 
static void registerFunctionAnalyses (FunctionAnalysisManager &FAM, PassInstrumentationCallbacks *PIC)
 
static bool parseFunctionPipeline (StringRef Name, FunctionPassManager &FPM, ArrayRef< PassBuilder::PipelineElement > Pipeline)
 
static bool parseScopPass (StringRef Name, ScopPassManager &SPM, PassInstrumentationCallbacks *PIC)
 
static bool parseScopPipeline (StringRef Name, FunctionPassManager &FPM, PassInstrumentationCallbacks *PIC, ArrayRef< PassBuilder::PipelineElement > Pipeline)
 
static bool isScopPassName (StringRef Name)
 
static bool parseTopLevelPipeline (llvm::ModulePassManager &MPM, PassInstrumentationCallbacks *PIC, ArrayRef< PassBuilder::PipelineElement > Pipeline)
 
void registerPollyPasses (PassBuilder &PB)
 Register Polly to be available as an optimizer.
 
void getDebugLocation (const Region *R, unsigned &LineBegin, unsigned &LineEnd, std::string &FileName)
 
void dumpIslObj (const isl::schedule_node &Node, llvm::raw_ostream &OS)
 Emit the equivaltent of the isl_*_dump output into a raw_ostream.
 
void dumpIslObj (__isl_keep isl_schedule_node *node, llvm::raw_ostream &OS)
 
isl::pw_aff operator+ (isl::pw_aff Left, isl::pw_aff Right)
 Addition.
 
isl::pw_aff operator+ (isl::val ValLeft, isl::pw_aff Right)
 
isl::pw_aff operator+ (isl::pw_aff Left, isl::val ValRight)
 
isl::pw_aff operator+ (long IntLeft, isl::pw_aff Right)
 
isl::pw_aff operator+ (isl::pw_aff Left, long IntRight)
 
isl::pw_aff operator* (isl::pw_aff Left, isl::pw_aff Right)
 Multiplication.
 
isl::pw_aff operator* (isl::val ValLeft, isl::pw_aff Right)
 
isl::pw_aff operator* (isl::pw_aff Left, isl::val ValRight)
 
isl::pw_aff operator* (long IntLeft, isl::pw_aff Right)
 
isl::pw_aff operator* (isl::pw_aff Left, long IntRight)
 
isl::pw_aff operator- (isl::pw_aff Left, isl::pw_aff Right)
 Subtraction.
 
isl::pw_aff operator- (isl::val ValLeft, isl::pw_aff Right)
 
isl::pw_aff operator- (isl::pw_aff Left, isl::val ValRight)
 
isl::pw_aff operator- (long IntLeft, isl::pw_aff Right)
 
isl::pw_aff operator- (isl::pw_aff Left, long IntRight)
 
isl::pw_aff operator/ (isl::pw_aff Left, isl::pw_aff Right)
 Division.
 
isl::pw_aff operator/ (isl::val ValLeft, isl::pw_aff Right)
 
isl::pw_aff operator/ (isl::pw_aff Left, isl::val ValRight)
 
isl::pw_aff operator/ (long IntLeft, isl::pw_aff Right)
 
isl::pw_aff operator/ (isl::pw_aff Left, long IntRight)
 
isl::pw_aff operator% (isl::pw_aff Left, isl::pw_aff Right)
 Remainder.
 
isl::pw_aff operator% (isl::val ValLeft, isl::pw_aff Right)
 
isl::pw_aff operator% (isl::pw_aff Left, isl::val ValRight)
 
isl::pw_aff operator% (long IntLeft, isl::pw_aff Right)
 
isl::pw_aff operator% (isl::pw_aff Left, long IntRight)
 
void dumpPw (const isl::set &Set)
 Dump a description of the argument to llvm::errs().
 
void dumpPw (const isl::map &Map)
 
void dumpPw (const isl::union_set &USet)
 
void dumpPw (const isl::union_map &UMap)
 
void dumpPw (__isl_keep isl_set *Set)
 
void dumpPw (__isl_keep isl_map *Map)
 
void dumpPw (__isl_keep isl_union_set *USet)
 
void dumpPw (__isl_keep isl_union_map *UMap)
 
void dumpExpanded (const isl::set &Set)
 Dump all points of the argument to llvm::errs().
 
void dumpExpanded (const isl::map &Map)
 
void dumpExpanded (const isl::union_set &USet)
 
void dumpExpanded (const isl::union_map &UMap)
 
void dumpExpanded (__isl_keep isl_set *Set)
 
void dumpExpanded (__isl_keep isl_map *Map)
 
void dumpExpanded (__isl_keep isl_union_set *USet)
 
void dumpExpanded (__isl_keep isl_union_map *UMap)
 

Variables

VectorizerChoice PollyVectorizerChoice
 
bool PerfMonitoring
 
int PollyNumThreads
 
OMPGeneralSchedulingType PollyScheduling
 
int PollyChunkSize
 
char & CodePreparationID = CodePreparation::ID
 
bool ModelReadOnlyScalars
 Command line switch whether to model read-only accesses.
 
bool PollyTrackFailures = false
 
bool PollyDelinearize = false
 
bool PollyUseRuntimeAliasChecks
 
bool PollyProcessUnprofitable
 
bool PollyInvariantLoadHoisting
 
bool PollyAllowUnsignedOperations
 
bool PollyAllowFullFunction
 
StringRef PollySkipFnAttr = "polly.skip.fn"
 A function attribute which will cause Polly to skip the function.
 
bool UseInstructionNames
 
unsigned const MaxDisjunctsInDomain = 20
 

Typedef Documentation

◆ AccFuncVector

using polly::AccFuncVector = typedef std::vector<std::unique_ptr<MemoryAccess> >

Definition at line 212 of file ScopInfo.h.

◆ AFs

using polly::AFs = typedef std::vector<PairInstSCEV>

Definition at line 115 of file ScopDetection.h.

◆ BaseToAFs

using polly::BaseToAFs = typedef std::map<const SCEVUnknown *, AFs>

Definition at line 116 of file ScopDetection.h.

◆ BaseToElSize

using polly::BaseToElSize = typedef std::map<const SCEVUnknown *, const SCEV *>

Definition at line 117 of file ScopDetection.h.

◆ BBPair

typedef std::pair< BasicBlock *, BasicBlock * > polly::BBPair

Type to hold region delimiters (entry & exit block).

Definition at line 31 of file Utils.h.

◆ BoxedLoopsSetTy

using polly::BoxedLoopsSetTy = typedef llvm::SetVector<const llvm::Loop *>

Set of loops (used to remember loops in non-affine subregions).

Definition at line 112 of file ScopHelper.h.

◆ FunctionAnalysisManagerScopProxy

using polly::FunctionAnalysisManagerScopProxy = typedef OuterAnalysisManagerProxy<FunctionAnalysisManager, Scop, ScopStandardAnalysisResults &>

Definition at line 49 of file ScopPass.h.

◆ InvariantAccessesTy

using polly::InvariantAccessesTy = typedef SmallVector<InvariantAccess, 8>

Ordered container type to hold invariant accesses.

Definition at line 1101 of file ScopInfo.h.

◆ InvariantEquivClassesTy

using polly::InvariantEquivClassesTy = typedef SmallVector<InvariantEquivClassTy, 8>

Type for invariant accesses equivalence classes.

Definition at line 1129 of file ScopInfo.h.

◆ InvariantLoadsSetTy

using polly::InvariantLoadsSetTy = typedef llvm::SetVector<llvm::AssertingVH<llvm::LoadInst> >

Type for a set of invariant loads.

Definition at line 106 of file ScopHelper.h.

◆ LoopBoundMapType

using polly::LoopBoundMapType = typedef std::map<const Loop *, const SCEV *>

Maps from a loop to the affine function expressing its backedge taken count.

The backedge taken count already enough to express iteration domain as we only allow loops with canonical induction variable. A canonical induction variable is: an integer recurrence that starts at 0 and increments by one each time through the loop.

Definition at line 210 of file ScopInfo.h.

◆ MapInsnToMemAcc

using polly::MapInsnToMemAcc = typedef std::map<const Instruction *, MemAcc>

Definition at line 113 of file ScopDetection.h.

◆ MemoryAccessList

using polly::MemoryAccessList = typedef std::forward_list<MemoryAccess *>

Ordered list type to hold accesses.

Definition at line 1089 of file ScopInfo.h.

◆ OwningScopAnalysisManagerFunctionProxy

Definition at line 152 of file ScopPass.h.

◆ PairInstSCEV

using polly::PairInstSCEV = typedef std::pair<const Instruction *, const SCEV *>

Definition at line 114 of file ScopDetection.h.

◆ ParameterSetTy

using polly::ParameterSetTy = typedef llvm::SetVector<const llvm::SCEV *>

Set type for parameters.

Definition at line 109 of file ScopHelper.h.

◆ ParamSetType

using polly::ParamSetType = typedef std::set<const SCEV *>

Definition at line 87 of file ScopDetection.h.

◆ PollyIRBuilder

typedef llvm::IRBuilder<llvm::ConstantFolder, IRInserter> polly::PollyIRBuilder

Definition at line 141 of file IRBuilder.h.

◆ PWACtx

typedef std::pair<isl::pw_aff, isl::set> polly::PWACtx

The result type of the SCEVAffinator.

The first element of the pair is the isl representation of the SCEV, the second is the domain under which it is invalid.

Definition at line 27 of file SCEVAffinator.h.

◆ RecordedAssumptionsTy

using polly::RecordedAssumptionsTy = typedef llvm::SmallVector<Assumption, 8>

Definition at line 77 of file ScopHelper.h.

◆ RejectReasonPtr

using polly::RejectReasonPtr = typedef std::shared_ptr<RejectReason>

Definition at line 163 of file ScopDetectionDiagnostic.h.

◆ ScopAnalysisManager

using polly::ScopAnalysisManager = typedef AnalysisManager<Scop, ScopStandardAnalysisResults &>

Definition at line 45 of file ScopPass.h.

◆ ScopAnalysisManagerFunctionProxy

using polly::ScopAnalysisManagerFunctionProxy = typedef InnerAnalysisManagerProxy<ScopAnalysisManager, Function>

Definition at line 47 of file ScopPass.h.

◆ ScopPassManager

Definition at line 154 of file ScopPass.h.

◆ ValueMapT

using polly::ValueMapT = typedef llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::AssertingVH<llvm::Value> >

Type to remap values.

Definition at line 102 of file ScopHelper.h.

Enumeration Type Documentation

◆ AssumptionKind

Enumeration of assumptions Polly can take.

Enumerator
ALIASING 
INBOUNDS 
WRAPPING 
UNSIGNED 
PROFITABLE 
ERRORBLOCK 
COMPLEXITY 
INFINITELOOP 
INVARIANTLOAD 
DELINEARIZATION 

Definition at line 40 of file ScopHelper.h.

◆ AssumptionSign

Enum to distinguish between assumptions and restrictions.

Enumerator
AS_ASSUMPTION 
AS_RESTRICTION 

Definition at line 54 of file ScopHelper.h.

◆ CodeGenChoice

Enumerator
CODEGEN_FULL 
CODEGEN_AST 
CODEGEN_NONE 

Definition at line 91 of file RegisterPasses.cpp.

◆ MemoryKind

enum class polly::MemoryKind
strong

The different memory kinds used in Polly.

We distinguish between arrays and various scalar memory objects. We use the term `‘array’' to describe memory objects that consist of a set of individual data elements arranged in a multi-dimensional grid. A scalar memory object describes an individual data element and is used to model the definition and uses of llvm::Values.

The polyhedral model does traditionally not reason about SSA values. To reason about llvm::Values we model them "as if" they were zero-dimensional memory objects, even though they were not actually allocated in (main) memory. Memory for such objects is only alloca[ed] at CodeGeneration time. To relate the memory slots used during code generation with the llvm::Values they belong to the new names for these corresponding stack slots are derived by appending suffixes (currently ".s2a" and ".phiops") to the name of the original llvm::Value. To describe how def/uses are modeled exactly we use these suffixes here as well.

There are currently four different kinds of memory objects:

Enumerator
Array 

MemoryKind::Array: Models a one or multi-dimensional array.

A memory object that can be described by a multi-dimensional array. Memory objects of this type are used to model actual multi-dimensional arrays as they exist in LLVM-IR, but they are also used to describe other objects:

  • A single data element allocated on the stack using 'alloca' is modeled as a one-dimensional, single-element array.
  • A single data element allocated as a global variable is modeled as one-dimensional, single-element array.
  • Certain multi-dimensional arrays with variable size, which in LLVM-IR are commonly expressed as a single-dimensional access with a complicated access function, are modeled as multi-dimensional memory objects (grep for "delinearization").
Value 

MemoryKind::Value: Models an llvm::Value.

Memory objects of type MemoryKind::Value are used to model the data flow induced by llvm::Values. For each llvm::Value that is used across BasicBlocks, one ScopArrayInfo object is created. A single memory WRITE stores the llvm::Value at its definition into the memory object and at each use of the llvm::Value (ignoring trivial intra-block uses) a corresponding READ is added. For instance, the use/def chain of a llvm::Value V depicted below


|DefBB: |

| %V = float op ... |

| |


|UseBB1: | |UseBB2: | | use float V | | use float V |


is modeled as if the following memory accesses occurred:

                   __________________________
                   |entry:                  |
                   |  %V.s2a = alloca float |
                   --------------------------
                                |
               ___________________________________
               |DefBB:                           |
               |  store %float %V, float* %V.s2a |
               -----------------------------------
                      |                   |

|UseBB1: | |UseBB2: | | V.reload1 = load float* V.s2a | | V.reload2 = load float* V.s2a| | use float V.reload1 | | use float V.reload2 |


PHI 

MemoryKind::PHI: Models PHI nodes within the SCoP.

Besides the MemoryKind::Value memory object used to model the normal llvm::Value dependences described above, PHI nodes require an additional memory object of type MemoryKind::PHI to describe the forwarding of values to the PHI node.

As an example, a PHIInst instructions

PHI = phi float [ Val1, IncomingBlock1 ], [ Val2, IncomingBlock2 ]

is modeled as if the accesses occurred this way:

               _______________________________
               |entry:                       |
               |  %PHI.phiops = alloca float |
               -------------------------------
                      |              |

|IncomingBlock1: | |IncomingBlock2: | | ... | | ... | | store float Val1 PHI.phiops | | store float Val2 PHI.phiops | | br label % JoinBlock | | br label JoinBlock |


\ / \ /


|JoinBlock: |

| %PHI = load float, float* PHI.phiops |

Note that there can also be a scalar write access for PHI if used in a different BasicBlock, i.e. there can be a memory object PHI.phiops as well as a memory object PHI.s2a.

ExitPHI 

MemoryKind::ExitPHI: Models PHI nodes in the SCoP's exit block.

For PHI nodes in the Scop's exit block a special memory object kind is used. The modeling used is identical to MemoryKind::PHI, with the exception that there are no READs from these memory objects. The PHINode's llvm::Value is treated as a value escaping the SCoP. WRITE accesses write directly to the escaping value's ".s2a" alloca.

Definition at line 100 of file ScopInfo.h.

◆ OMPGeneralSchedulingType

General scheduling types of parallel OpenMP for loops.

Initialization values taken from OpenMP's enum in kmp.h: sched_type. Currently, only 'static' scheduling may change from chunked to non-chunked.

Enumerator
StaticChunked 
StaticNonChunked 
Dynamic 
Guided 
Runtime 

Definition at line 36 of file LoopGenerators.h.

◆ OptimizerChoice

Enumerator
OPTIMIZER_NONE 
OPTIMIZER_ISL 

Definition at line 75 of file RegisterPasses.cpp.

◆ PassPositionChoice

Enumerator
POSITION_EARLY 
POSITION_BEFORE_VECTORIZER 

Definition at line 73 of file RegisterPasses.cpp.

◆ RejectReasonKind

enum class polly::RejectReasonKind
strong
Enumerator
CFG 
InvalidTerminator 
IrreducibleRegion 
UnreachableInExit 
IndirectPredecessor 
LastCFG 
AffFunc 
UndefCond 
InvalidCond 
UndefOperand 
NonAffBranch 
NoBasePtr 
UndefBasePtr 
VariantBasePtr 
NonAffineAccess 
DifferentElementSize 
LastAffFunc 
LoopBound 
LoopHasNoExit 
LoopHasMultipleExits 
LoopOnlySomeLatches 
FuncCall 
NonSimpleMemoryAccess 
Alias 
Other 
IntToPtr 
Alloca 
UnknownInst 
Entry 
Unprofitable 
LastOther 

Definition at line 70 of file ScopDetectionDiagnostic.h.

◆ VectorizerChoice

Enumerator
VECTORIZER_NONE 
VECTORIZER_STRIPMINE 

Definition at line 18 of file CodeGeneration.h.

Function Documentation

◆ addReferencesFromStmt()

void polly::addReferencesFromStmt ( ScopStmt Stmt,
void *  UserPtr,
bool  CreateScalarRefs = true 
)

Extract the out-of-scop values and SCEVs referenced from a ScopStmt.

This includes the SCEVUnknowns referenced by the SCEVs used in the statement and the base pointers of the memory accesses. For scalar statements we force the generation of alloca memory locations and list these locations in the set of out-of-scop values as well.

We also collect an isl::space that includes all parameter dimensions used in the statement's memory accesses, in case the ParamSpace pointer is non-null.

Parameters
StmtThe statement for which to extract the information.
UserPtrA void pointer that can be casted to a SubtreeReferences structure.
CreateScalarRefsShould the result include allocas of scalar references?

Definition at line 246 of file IslNodeBuilder.cpp.

References isl::space::align_params(), polly::Scop::contains(), findReferencesInStmt(), and polly::ScopStmt::getParent().

Referenced by addReferencesFromStmtSet().

◆ afterScatter() [1/2]

isl::union_map polly::afterScatter ( const isl::union_map UMap,
bool  Strict 
)

◆ afterScatter() [2/2]

isl::map polly::afterScatter ( isl::map  Map,
bool  Strict 
)

Return the range elements that are lexicographically larger.

Parameters
Map{ Space[] -> Scatter[] }
StrictTrue for strictly lexicographically larger elements (exclude same timepoints from the result).
Returns
{ Space[] -> Scatter[] } A map to all timepoints that happen after the timepoints the input map originally mapped to.

Definition at line 103 of file ISLTools.cpp.

References isl::map::apply_range(), isl::map::get_space(), isl::map::lex_le(), isl::map::lex_lt(), and isl::space::range().

Referenced by afterScatter(), and betweenScatter().

◆ APIntFromVal() [1/2]

APInt polly::APIntFromVal ( __isl_take isl_val Val)

Translate isl_val to llvm::APInt.

This function can only be called on isl_val values which are integers. Calling this function with a non-integral rational, NaN or infinity value is not allowed.

As the input isl_val may be negative, the APInt that this function returns must always be interpreted as signed two's complement value. The bitwidth of the generated APInt is always the minimal bitwidth necessary to model the provided integer when interpreting the bit pattern as signed value.

Some example conversions are:

Input Bits Signed Bitwidth 0 -> 0 0 1 -1 -> 1 -1 1 1 -> 01 1 2 -2 -> 10 -2 2 2 -> 010 2 3 -3 -> 101 -3 3 3 -> 011 3 3 -4 -> 100 -4 3 4 -> 0100 4 4

Parameters
ValThe isl val to translate.
Returns
The APInt value corresponding to Val.

Definition at line 51 of file GICHelper.cpp.

References A(), assert, isl_val_free(), isl_val_get_abs_num_chunks(), isl_val_is_int(), isl_val_is_neg(), and isl_val_n_abs_num_chunks().

Referenced by APIntFromVal(), polly::IslExprBuilder::createInt(), polly::ScopBuilder::foldSizeConstantsToRight(), and polly::IslExprBuilder::hasLargeInts().

◆ APIntFromVal() [2/2]

llvm::APInt polly::APIntFromVal ( isl::val  V)
inline

Translate isl::val to llvm::APInt.

This function can only be called on isl::val values which are integers. Calling this function with a non-integral rational, NaN or infinity value is not allowed.

As the input isl::val may be negative, the APInt that this function returns must always be interpreted as signed two's complement value. The bitwidth of the generated APInt is always the minimal bitwidth necessary to model the provided integer when interpreting the bit pattern as signed value.

Some example conversions are:

Input Bits Signed Bitwidth 0 -> 0 0 1 -1 -> 1 -1 1 1 -> 01 1 2 -2 -> 10 -2 2 2 -> 010 2 3 -3 -> 101 -3 3 3 -> 011 3 3 -4 -> 100 -4 3 4 -> 0100 4 4

Parameters
ValThe isl val to translate.
Returns
The APInt value corresponding to Val.

Definition at line 147 of file GICHelper.h.

References APIntFromVal(), and isl::val::release().

◆ applyDomainRange()

isl::union_map polly::applyDomainRange ( isl::union_map  UMap,
isl::union_map  Func 
)

Apply a map to the 'middle' of another relation.

Parameters
UMap{ [DomainDomain[] -> DomainRange[]] -> Range[] }
Func{ DomainRange[] -> NewDomainRange[] }
Returns
{ [DomainDomain[] -> NewDomainRange[]] -> Range[] }

Definition at line 517 of file ISLTools.cpp.

References isl::union_map::apply_domain(), isl::union_map::domain(), liftDomains(), and isl::union_set::unwrap().

◆ applyFullUnroll()

isl::schedule polly::applyFullUnroll ( isl::schedule_node  BandToUnroll)

◆ applyGreedyFusion()

isl::schedule polly::applyGreedyFusion ( isl::schedule  Sched,
const isl::union_map Deps 
)

Apply greedy fusion.

That is, fuse any loop that is possible to be fused top-down.

Parameters
SchedSched tree to fuse all the loops in.
DepsValidity constraints that must be preserved.

Definition at line 1230 of file ScheduleTreeTransform.cpp.

References POLLY_DEBUG.

◆ applyManualTransformations()

isl::schedule polly::applyManualTransformations ( Scop S,
isl::schedule  Sched,
const Dependences D,
llvm::OptimizationRemarkEmitter *  ORE 
)

Apply loop-transformation metadata.

The loop metadata are taken from mark-nodes in @sched. These nodes have been added by ScopBuilder when creating a schedule for a loop with an attach LoopID.

Parameters
SThe SCoP for Sched.
SchedThe input schedule to apply the directives on.
Returns
The transformed schedule with all mark-nodes with loop transformations applied. Returns NULL in case of an error or Sched itself if no transformation has been applied.

◆ applyMaxFission()

isl::schedule polly::applyMaxFission ( isl::schedule_node  BandToFission)

◆ applyPartialUnroll()

isl::schedule polly::applyPartialUnroll ( isl::schedule_node  BandToUnroll,
int  Factor 
)

◆ applyRegisterTiling()

isl::schedule_node polly::applyRegisterTiling ( isl::schedule_node  Node,
llvm::ArrayRef< int >  TileSizes,
int  DefaultTileSize 
)

Tile a schedule node and unroll point loops.

Parameters
NodeThe node to register tile.
TileSizesA vector of tile sizes that should be used for tiling.
DefaultTileSizeA default tile size that is used for dimensions

◆ beforeScatter() [1/2]

isl::map polly::beforeScatter ( isl::map  Map,
bool  Strict 
)

Return the range elements that are lexicographically smaller.

Parameters
Map{ Space[] -> Scatter[] }
StrictTrue for strictly lexicographically smaller elements (exclude same timepoints from the result).
Returns
{ Space[] -> Scatter[] } A map to all timepoints that happen before the timepoints the input mapped to.

Definition at line 85 of file ISLTools.cpp.

References isl::map::apply_range(), isl::map::get_space(), isl::map::lex_ge(), isl::map::lex_gt(), and isl::space::range().

Referenced by beforeScatter(), betweenScatter(), and polly::ZoneAlgorithm::computePerPHI().

◆ beforeScatter() [2/2]

isl::union_map polly::beforeScatter ( isl::union_map  UMap,
bool  Strict 
)

◆ betweenScatter() [1/2]

isl::map polly::betweenScatter ( isl::map  From,
isl::map  To,
bool  InclFrom,
bool  InclTo 
)

Construct a range of timepoints between two timepoints.

Example: From := { A[] -> [0]; B[] -> [0] } To := { B[] -> [10]; C[] -> [20] }

Result: { B[] -> [i] : 0 < i < 10 }

Note that A[] and C[] are not in the result because they do not have a start or end timepoint. If a start (or end) timepoint is not unique, the first (respectively last) is chosen.

Parameters
From{ Space[] -> Scatter[] } Map to start timepoints.
To{ Space[] -> Scatter[] } Map to end timepoints.
InclFromWhether to include the start timepoints in the result. In the example, this would add { B[] -> [0] }
InclToWhether to include the end timepoints in the result. In this example, this would add { B[] -> [10] }
Returns
{ Space[] -> Scatter[] } A map for each domain element of timepoints between two extreme points, or nullptr if From or To is nullptr, or the isl max operations is exceeded.

Definition at line 119 of file ISLTools.cpp.

References afterScatter(), beforeScatter(), and isl::map::intersect().

Referenced by computeArrayUnused().

◆ betweenScatter() [2/2]

isl::union_map polly::betweenScatter ( isl::union_map  From,
isl::union_map  To,
bool  InclFrom,
bool  InclTo 
)

◆ buildCanonicalicationPassesForNPM()

FunctionPassManager polly::buildCanonicalicationPassesForNPM ( llvm::ModulePassManager &  MPM,
llvm::OptimizationLevel  Level 
)

Definition at line 91 of file Canonicalization.cpp.

References buildInlinePasses(), and PollyInliner().

Referenced by buildEarlyPollyPipeline().

◆ buildCommonPollyPipeline()

static void polly::buildCommonPollyPipeline ( FunctionPassManager &  PM,
OptimizationLevel  Level,
bool  EnableForOpt 
)
static

Register Polly passes such that they form a polyhedral optimizer.

The individual Polly passes are registered in the pass manager such that they form a full polyhedral optimizer. The flow of the optimizer starts with a set of preparing transformations that canonicalize the LLVM-IR such that the LLVM-IR is easier for us to understand and to optimizes. On the canonicalized LLVM-IR we first run the ScopDetection pass, which detects static control flow regions. Those regions are then translated by the ScopInfo pass into a polyhedral representation. As a next step, a scheduling optimizer is run on the polyhedral representation and finally the optimized polyhedral representation is code generated back to LLVM-IR.

Besides this core functionality, we optionally schedule passes that provide a graphical view of the scops (Polly[Only]Viewer, Polly[Only]Printer), that allow the export/import of the polyhedral representation (JSCON[Exporter|Importer]) or that show the cfg after code generation.

For certain parts of the Polly optimizer, several alternatives are provided:

As scheduling optimizer we support the isl scheduling optimizer (http://freecode.com/projects/isl). It is also possible to run Polly with no optimizer. This mode is mainly provided to analyze the run and compile time changes caused by the scheduling optimizer.

Polly supports the isl internal code generator. Add the pass sequence required for Polly to the New Pass Manager.

Parameters
PMThe pass manager itself.
LevelThe optimization level. Used for the cleanup of Polly's output.
EnableForOptWhether to add Polly IR transformations. If False, only the analysis passes are added, skipping Polly itself. The IR may still be modified.

Definition at line 302 of file RegisterPasses.cpp.

References CFGPrinter(), CODEGEN_AST, CODEGEN_FULL, CODEGEN_NONE, CodeGeneration(), createFunctionToScopPassAdaptor(), DeadCodeElim(), EnableDeLICM(), EnableForwardOpTree(), EnablePruneUnprofitable(), EnableSimplify(), ExportJScop(), FullyIndexedStaticExpansion(), ImportJScop(), Optimizer(), OPTIMIZER_ISL, OPTIMIZER_NONE, PollyDetectOnly(), PollyOnlyPrinter(), PollyOnlyViewer(), PollyPrinter(), and PollyViewer().

Referenced by buildEarlyPollyPipeline(), and buildLatePollyPipeline().

◆ buildEarlyPollyPipeline()

static void polly::buildEarlyPollyPipeline ( llvm::ModulePassManager &  MPM,
llvm::OptimizationLevel  Level 
)
static

◆ buildLatePollyPipeline()

static void polly::buildLatePollyPipeline ( FunctionPassManager &  PM,
llvm::OptimizationLevel  Level 
)
static

◆ canSynthesize()

bool polly::canSynthesize ( const llvm::Value *  V,
const Scop S,
llvm::ScalarEvolution *  SE,
llvm::Loop *  Scope 
)

Check whether a value an be synthesized by the code generator.

Some value will be recalculated only from information that is code generated from the polyhedral representation. For such instructions we do not need to ensure that their operands are available during code generation.

Parameters
VThe value to check.
SThe current SCoP.
SEThe scalar evolution database.
ScopeLocation where the value would by synthesized.
Returns
If the instruction I can be regenerated from its scalar evolution representation, return true, otherwise return false.

Referenced by polly::ScopBuilder::buildPHIAccesses(), polly::BlockGenerator::canSyntheziseInStmt(), polly::VirtualUse::create(), and polly::ScopBuilder::shouldModelInst().

◆ CFGPrinter()

static cl::opt< bool > polly::CFGPrinter ( "polly-view-cfg"  ,
cl::desc("Show the Polly CFG right after code generation")  ,
cl::Hidden  ,
cl::init(false)  ,
cl::cat(PollyCategory  
)
static

◆ CodeGeneration()

static cl::opt< CodeGenChoice > polly::CodeGeneration ( "polly-code-generation"  ,
cl::desc("How much code-generation to perform")  ,
cl::values(clEnumValN(CODEGEN_FULL, "full", "AST and IR generation"), clEnumValN(CODEGEN_AST, "ast", "Only AST generation"), clEnumValN(CODEGEN_NONE, "none", "No code generation"))  ,
cl::Hidden  ,
cl::init(CODEGEN_FULL ,
cl::cat(PollyCategory  
)
static

◆ computeArrayUnused()

isl::union_map polly::computeArrayUnused ( isl::union_map  Schedule,
isl::union_map  Writes,
isl::union_map  Reads,
bool  ReadEltInSameInst,
bool  InclLastRead,
bool  InclWrite 
)

Compute the timepoints where the contents of an array element are not used.

An element is unused at a timepoint when the element is overwritten in the future, but it is not read in between. Another way to express this: the time from when the element is written, to the most recent read before it, or infinitely into the past if there is no read before. Such unused elements can be overwritten by any value without changing the scop's semantics. An example:

Schedule := { Read[] -> [0]; Write[] -> [10]; Def[] -> [20] } Writes := { Write[] -> A[5]; Def[] -> A[6] } Reads := { Read[] -> A[5] }

The result is:

{ A[5] -> [i] : 0 < i < 10; A[6] -> [i] : i < 20 }

That is, A[5] is unused between timepoint 0 (the read) and timepoint 10 (the write). A[6] is unused before timepoint 20, but might be used after the scop's execution (A[5] and any other A[i] as well). Use InclLastRead=false and InclWrite=true to interpret the result as zone.

Parameters
Schedule{ Domain[] -> Scatter[] } The schedule of (at least) all statement instances occurring in Writes or Reads. All other instances are ignored.
Writes{ DomainWrite[] -> Element[] } Elements written to by the statement instances.
Reads{ DomainRead[] -> Element[] } Elements read from by the statement instances.
ReadEltInSameInstWhether a load reads the value from a write that is scheduled at the same timepoint (Writes happen before reads). Otherwise, loads use the value of an element that it had before the timepoint (Reads before writes). For example: { Read[] -> [0]; Write[] -> [0] } With ReadEltInSameInst=false it is assumed that the read happens before the write, such that the element is never unused, or just at timepoint 0, depending on InclLastRead/InclWrite. With ReadEltInSameInst=false it assumes that the value just written is used. Anything before timepoint 0 is considered unused.
InclLastReadWhether a timepoint where an element is last read counts as unused (the read happens at the beginning of its timepoint, and nothing (else) can use it during the timepoint). In the example, this option adds { A[5] -> [0] } to the result.
InclWriteWhether the timepoint where an element is written itself counts as unused (the write happens at the end of its timepoint; no (other) operations uses the element during the timepoint). In this example, this adds { A[5] -> [10]; A[6] -> [20] } to the result.
Returns
{ Element[] -> Scatter[] } The unused timepoints as defined above, or nullptr if either Schedule, Writes are Reads is nullptr, or the ISL max operations count is exceeded.

Definition at line 366 of file ISLTools.cpp.

References isl::union_map::apply_domain(), isl::union_map::apply_range(), betweenScatter(), computeReachingWrite(), isl::map::curry(), isl::union_map::domain(), isl::union_map::domain_factor_domain(), isl::union_map::intersect_domain(), isl::union_map::lexmax(), isl::union_map::range_map(), isl::map::reverse(), isl::union_map::reverse(), reverseDomain(), isl::union_map::subtract_domain(), isl::union_map::unite(), and isl::union_map::wrap().

◆ computeReachingWrite()

isl::union_map polly::computeReachingWrite ( isl::union_map  Schedule,
isl::union_map  Writes,
bool  Reverse,
bool  InclPrevDef,
bool  InclNextDef 
)

Compute the reaching definition statement or the next overwrite for each definition of an array element.

The reaching definition of an array element at a specific timepoint is the statement instance that has written the current element's content. Alternatively, this function determines for each timepoint and element which write is going to overwrite an element at a future timepoint. This can be seen as "reaching definition in reverse" where definitions are found in the past.

For example:

Schedule := { Write[] -> [0]; Overwrite[] -> [10] } Defs := { Write[] -> A[5]; Overwrite[] -> A[5] }

If index 5 of array A is written at timepoint 0 and 10, the resulting reaching definitions are:

{ [A[5] -> [i]] -> Write[] : 0 < i < 10; [A[5] -> [i]] -> Overwrite[] : 10 < i }

Between timepoint 0 (Write[]) and timepoint 10 (Overwrite[]), the content of A[5] is written by statement instance Write[] and after timepoint 10 by Overwrite[]. Values not defined in the map have no known definition. This includes the statement instance timepoints themselves, because reads at those timepoints could either read the old or the new value, defined only by the statement itself. But this can be changed by InclPrevDef and InclNextDef. InclPrevDef=false and InclNextDef=true returns a zone. Unless InclPrevDef and InclNextDef are both true, there is only one unique definition per element and timepoint.

Parameters
Schedule{ DomainWrite[] -> Scatter[] } Schedule of (at least) all array writes. Instances not in Writes are ignored.
Writes{ DomainWrite[] -> Element[] } Elements written to by the statement instances.
ReverseIf true, look for definitions in the future. That is, find the write that is overwrites the current value.
InclPrevDefInclude the definition's timepoint to the set of well-defined elements (any load at that timepoint happen at the writes). In the example, enabling this option adds {[A[5] -> [0]] -> Write[]; [A[5] -> [10]] -> Overwrite[]} to the result.
InclNextDefWhether to assume that at the timepoint where an element is overwritten, it still contains the old value (any load at that timepoint would happen before the overwrite). In this example, enabling this adds { [A[] -> [10]] -> Write[] } to the result.
Returns
{ [Element[] -> Scatter[]] -> DomainWrite[] } The reaching definitions or future overwrite as described above, or nullptr if either Schedule or Writes is nullptr, or the isl max operations count has exceeded.

Definition at line 313 of file ISLTools.cpp.

References isl::union_map::apply_domain(), isl::union_map::apply_range(), isl::union_map::coalesce(), getScatterSpace(), isl::map::lex_ge(), isl::map::lex_gt(), isl::map::lex_le(), isl::map::lex_lt(), isl::union_map::lexmax(), isl::union_map::lexmin(), isl::map::range_map(), isl::union_map::range_map(), isl::map::reverse(), isl::union_map::reverse(), isl::union_map::subtract(), isl::union_map::uncurry(), and isl::union_map::unite().

Referenced by computeArrayUnused(), and computeReachingDefinition().

◆ convertZoneToTimepoints() [1/3]

isl::map polly::convertZoneToTimepoints ( isl::map  Zone,
isl::dim  Dim,
bool  InclStart,
bool  InclEnd 
)

Overload of convertZoneToTimepoints(isl::map,InclStart,InclEnd) to process only a single map.

Definition at line 440 of file ISLTools.cpp.

References assert, isl::map::intersect(), shiftDim(), and isl::map::unite().

◆ convertZoneToTimepoints() [2/3]

isl::union_map polly::convertZoneToTimepoints ( isl::union_map  Zone,
isl::dim  Dim,
bool  InclStart,
bool  InclEnd 
)

Like convertZoneToTimepoints(isl::union_set,InclStart,InclEnd), but convert either the domain or the range of a map.

Definition at line 425 of file ISLTools.cpp.

References assert, isl::union_map::intersect(), shiftDim(), and isl::union_map::unite().

◆ convertZoneToTimepoints() [3/3]

isl::union_set polly::convertZoneToTimepoints ( isl::union_set  Zone,
bool  InclStart,
bool  InclEnd 
)

Convert a zone (range between timepoints) to timepoints.

A zone represents the time between (integer) timepoints, but not the timepoints themselves. This function can be used to determine whether a timepoint lies within a zone.

For instance, the range (1,3), representing the time between 1 and 3, is represented by the zone

{ [i] : 1 < i <= 3 }

The set of timepoints that lie completely within this range is

{ [i] : 1 < i < 3 }

A typical use-case is the range in which a value written by a store is available until it is overwritten by another value. If the write is at timepoint 1 and its value is overwritten by another value at timepoint 3, the value is available between those timepoints: timepoint 2 in this example.

When InclStart is true, the range is interpreted left-inclusive, i.e. adds the timepoint 1 to the result:

{ [i] : 1 <= i < 3 }

In the use-case mentioned above that means that the value written at timepoint 1 is already available in timepoint 1 (write takes place before any read of it even if executed at the same timepoint)

When InclEnd is true, the range is interpreted right-inclusive, i.e. adds the timepoint 3 to the result:

{ [i] : 1 < i <= 3 }

In the use-case mentioned above that means that although the value is overwritten in timepoint 3, the old value is still available at timepoint 3 (write takes place after any read even if executed at the same timepoint)

Parameters
Zone{ Zone[] }
InclStartInclude timepoints adjacent to the beginning of a zone.
InclEndInclude timepoints adjacent to the ending of a zone.
Returns
{ Scatter[] }

Definition at line 410 of file ISLTools.cpp.

References assert, isl::union_set::intersect(), shiftDim(), and isl::union_set::unite().

Referenced by polly::ZoneAlgorithm::computeUseToDefFlowDependency().

◆ createCodeGenerationPass()

Pass * polly::createCodeGenerationPass ( )

Definition at line 371 of file CodeGeneration.cpp.

◆ createCodePreparationPass()

Pass * polly::createCodePreparationPass ( )

Definition at line 114 of file CodePreparation.cpp.

◆ createDeadCodeElimWrapperPass()

Pass * polly::createDeadCodeElimWrapperPass ( )

Definition at line 168 of file DeadCodeElimination.cpp.

◆ createDebugLocForGeneratedCode()

DebugLoc polly::createDebugLocForGeneratedCode ( Function *  F)

Create a DebugLoc representing generated instructions.

The IR verifier requires !dbg metadata to be set in some situations. For instance, if an (inlinable) function has debug info, all its call site must have debug info as well.

Definition at line 253 of file LoopGenerators.cpp.

References Ctx.

◆ createDeLICMPrinterLegacyPass()

llvm::Pass * polly::createDeLICMPrinterLegacyPass ( llvm::raw_ostream &  OS)

Definition at line 1497 of file DeLICM.cpp.

◆ createDeLICMWrapperPass()

Pass * polly::createDeLICMWrapperPass ( )

Create a new DeLICM pass instance.

Definition at line 1495 of file DeLICM.cpp.

◆ createDependenceInfoPass()

Pass * polly::createDependenceInfoPass ( )

Definition at line 930 of file DependenceInfo.cpp.

◆ createDependenceInfoPrinterLegacyFunctionPass()

llvm::Pass * polly::createDependenceInfoPrinterLegacyFunctionPass ( llvm::raw_ostream &  OS)

◆ createDependenceInfoPrinterLegacyPass()

llvm::Pass * polly::createDependenceInfoPrinterLegacyPass ( llvm::raw_ostream &  OS)

◆ createDependenceInfoWrapperPassPass()

Pass * polly::createDependenceInfoWrapperPassPass ( )

Definition at line 1031 of file DependenceInfo.cpp.

◆ createDOTOnlyPrinterWrapperPass()

Pass * polly::createDOTOnlyPrinterWrapperPass ( )

Definition at line 231 of file ScopGraphPrinter.cpp.

◆ createDOTOnlyViewerWrapperPass()

Pass * polly::createDOTOnlyViewerWrapperPass ( )

Definition at line 223 of file ScopGraphPrinter.cpp.

◆ createDOTPrinterWrapperPass()

Pass * polly::createDOTPrinterWrapperPass ( )

Definition at line 227 of file ScopGraphPrinter.cpp.

◆ createDOTViewerWrapperPass()

Pass * polly::createDOTViewerWrapperPass ( )

Definition at line 219 of file ScopGraphPrinter.cpp.

◆ createDumpFunctionWrapperPass()

FunctionPass * polly::createDumpFunctionWrapperPass ( std::string  Suffix)

Definition at line 117 of file DumpFunctionPass.cpp.

◆ createDumpModuleWrapperPass()

ModulePass * polly::createDumpModuleWrapperPass ( std::string  Filename,
bool  IsSuffix 
)

Create a pass that prints the module into a file.

The meaning of Filename depends on IsSuffix. If IsSuffix==false, then the module is written to the Filename. If it is true, the filename is generated from the module's name, Filename with an '.ll' extension.

The intent of IsSuffix is to avoid the file being overwritten when processing multiple modules and/or with multiple dump passes in the pipeline.

Definition at line 88 of file DumpModulePass.cpp.

◆ createFlattenSchedulePass()

Pass * polly::createFlattenSchedulePass ( )

Definition at line 135 of file FlattenSchedule.cpp.

◆ createFlattenSchedulePrinterLegacyPass()

Pass * polly::createFlattenSchedulePrinterLegacyPass ( llvm::raw_ostream &  OS)

Definition at line 137 of file FlattenSchedule.cpp.

◆ createForwardOpTreePrinterLegacyPass()

Pass * polly::createForwardOpTreePrinterLegacyPass ( llvm::raw_ostream &  OS)

Definition at line 1186 of file ForwardOpTree.cpp.

◆ createForwardOpTreeWrapperPass()

Pass * polly::createForwardOpTreeWrapperPass ( )

Definition at line 1182 of file ForwardOpTree.cpp.

◆ createFunctionToScopPassAdaptor()

template<typename ScopPassT >
FunctionToScopPassAdaptor< ScopPassT > polly::createFunctionToScopPassAdaptor ( ScopPassT  Pass)

Definition at line 287 of file ScopPass.h.

Referenced by buildCommonPollyPipeline(), parseScopPipeline(), and parseTopLevelPipeline().

◆ createIslAstInfoPrinterLegacyPass()

llvm::Pass * polly::createIslAstInfoPrinterLegacyPass ( llvm::raw_ostream &  OS)

◆ createIslAstInfoWrapperPassPass()

Pass * polly::createIslAstInfoWrapperPassPass ( )

Definition at line 809 of file IslAst.cpp.

◆ createIslLoopAttr()

isl::id polly::createIslLoopAttr ( isl::ctx  Ctx,
llvm::Loop *  L 
)

Create an isl::id that identifies an original loop.

Return nullptr if the loop does not need a BandAttr (i.e. has no properties);

This creates a BandAttr which must be unique per loop and therefore this must not be called multiple times on the same loop as their id would be different.

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

◆ createIslScheduleOptimizerPrinterLegacyPass()

llvm::Pass * polly::createIslScheduleOptimizerPrinterLegacyPass ( llvm::raw_ostream &  OS)

◆ createIslScheduleOptimizerWrapperPass()

Pass * polly::createIslScheduleOptimizerWrapperPass ( )

Definition at line 998 of file ScheduleOptimizer.cpp.

◆ createJSONExporterPass()

Pass * polly::createJSONExporterPass ( )

Definition at line 758 of file JSONExporter.cpp.

◆ createJSONImporterPass()

Pass * polly::createJSONImporterPass ( )

Definition at line 796 of file JSONExporter.cpp.

◆ createJSONImporterPrinterLegacyPass()

Pass * polly::createJSONImporterPrinterLegacyPass ( llvm::raw_ostream &  OS)

Definition at line 873 of file JSONExporter.cpp.

◆ createLoop()

Value * polly::createLoop ( Value *  LowerBound,
Value *  UpperBound,
Value *  Stride,
PollyIRBuilder Builder,
LoopInfo &  LI,
DominatorTree &  DT,
BasicBlock *&  ExitBlock,
ICmpInst::Predicate  Predicate,
ScopAnnotator Annotator = nullptr,
bool  Parallel = false,
bool  UseGuard = true,
bool  LoopVectDisabled = false 
)

Create a scalar do/for-style loop.

Parameters
LowerBoundThe starting value of the induction variable.
UpperBoundThe upper bound of the induction variable.
StrideThe value by which the induction variable is incremented.
BuilderThe builder used to create the loop.
PA pointer to the pass that uses this function. It is used to update analysis information.
LIThe loop info for the current function
DTThe dominator tree we need to update
ExitBlockThe block the loop will exit to.
PredicateThe predicate used to generate the upper loop bound.
AnnotatorThis function can (optionally) take a ScopAnnotator which annotates loops and alias information in the SCoP.
ParallelIf this loop should be marked parallel in the Annotator.
UseGuardCreate a guard in front of the header to check if the loop is executed at least once, otherwise just assume it.
LoopVectDisabledIf the Loop vectorizer should be disabled for this loop.
Returns
Value* The newly created induction variable for this loop.

Definition at line 83 of file LoopGenerators.cpp.

References polly::ScopAnnotator::annotateLoopLatch(), assert, B(), Function, polly::ScopAnnotator::pushLoop(), and Value.

Referenced by polly::IslNodeBuilder::createForSequential(), polly::ParallelLoopGeneratorGOMP::createSubFn(), and polly::ParallelLoopGeneratorKMP::createSubFn().

◆ createMaximalStaticExpansionPass()

Pass * polly::createMaximalStaticExpansionPass ( )

Definition at line 545 of file MaximalStaticExpansion.cpp.

◆ createPollyCanonicalizePass()

Pass * polly::createPollyCanonicalizePass ( )

Definition at line 170 of file Canonicalization.cpp.

◆ createPolyhedralInfoPass()

Pass * polly::createPolyhedralInfoPass ( )

Definition at line 156 of file PolyhedralInfo.cpp.

◆ createPolyhedralInfoPrinterLegacyPass()

llvm::Pass * polly::createPolyhedralInfoPrinterLegacyPass ( llvm::raw_ostream &  OS)

◆ createPruneUnprofitableWrapperPass()

Pass * polly::createPruneUnprofitableWrapperPass ( )

Definition at line 102 of file PruneUnprofitable.cpp.

◆ createScopAnalyses()

static OwningScopAnalysisManagerFunctionProxy polly::createScopAnalyses ( FunctionAnalysisManager &  FAM,
PassInstrumentationCallbacks *  PIC 
)
static

◆ createScopDetectionPrinterLegacyPass()

llvm::Pass * polly::createScopDetectionPrinterLegacyPass ( llvm::raw_ostream &  OS)

◆ createScopDetectionWrapperPassPass()

Pass * polly::createScopDetectionWrapperPassPass ( )

Definition at line 2055 of file ScopDetection.cpp.

◆ createScopInfoPrinterLegacyFunctionPass()

llvm::Pass * polly::createScopInfoPrinterLegacyFunctionPass ( llvm::raw_ostream &  OS)

◆ createScopInfoPrinterLegacyRegionPass() [1/2]

llvm::Pass * polly::createScopInfoPrinterLegacyRegionPass ( llvm::raw_ostream &  OS)

◆ createScopInfoPrinterLegacyRegionPass() [2/2]

Pass * polly::createScopInfoPrinterLegacyRegionPass ( raw_ostream &  OS)

Definition at line 2681 of file ScopInfo.cpp.

◆ createScopInfoRegionPassPass()

Pass * polly::createScopInfoRegionPassPass ( )

Definition at line 2627 of file ScopInfo.cpp.

◆ createScopInfoWrapperPassPass()

Pass * polly::createScopInfoWrapperPassPass ( )

Definition at line 2806 of file ScopInfo.cpp.

◆ createScopInlinerPass()

Pass * polly::createScopInlinerPass ( )

Definition at line 116 of file ScopInliner.cpp.

◆ createSimplifyPrinterLegacyPass()

llvm::Pass * polly::createSimplifyPrinterLegacyPass ( llvm::raw_ostream &  OS)

◆ createSimplifyWrapperPass()

Pass * polly::createSimplifyWrapperPass ( int  CallNo = 0)

Create a Simplify pass.

Parameters
CallNoDisambiguates this instance for when there are multiple instances of this pass in the pass manager. It is used only to keep the statistics apart and has no influence on the simplification itself.
Returns
The Simplify pass.

Definition at line 846 of file Simplify.cpp.

◆ DeadCodeElim()

static cl::opt< bool > polly::DeadCodeElim ( "polly-run-dce"  ,
cl::desc("Run the dead code elimination")  ,
cl::Hidden  ,
cl::cat(PollyCategory  
)
static

◆ distributeDomain() [1/2]

isl::map polly::distributeDomain ( isl::map  Map)

◆ distributeDomain() [2/2]

isl::union_map polly::distributeDomain ( isl::union_map  UMap)

◆ DumpAfter()

static cl::opt< bool > polly::DumpAfter ( "polly-dump-after"  ,
cl::desc("Dump module after Polly transformations into a file " "suffixed with \"-after\"")  ,
cl::init(false)  ,
cl::cat(PollyCategory  
)
static

◆ DumpAfterFile()

static cl::list< std::string > polly::DumpAfterFile ( "polly-dump-after-file"  ,
cl::desc("Dump module after Polly transformations to the given file")  ,
cl::cat(PollyCategory  
)
static

◆ DumpBefore()

static cl::opt< bool > polly::DumpBefore ( "polly-dump-before"  ,
cl::desc("Dump module before Polly transformations into a file " "suffixed with \"-before\"")  ,
cl::init(false)  ,
cl::cat(PollyCategory  
)
static

◆ DumpBeforeFile()

static cl::list< std::string > polly::DumpBeforeFile ( "polly-dump-before-file"  ,
cl::desc("Dump module before Polly transformations to the given file")  ,
cl::cat(PollyCategory  
)
static

◆ dumpExpanded() [1/8]

LLVM_DUMP_METHOD void polly::dumpExpanded ( __isl_keep isl_map Map)

Definition at line 909 of file ISLTools.cpp.

References dumpExpanded(), and isl::manage_copy().

◆ dumpExpanded() [2/8]

LLVM_DUMP_METHOD void polly::dumpExpanded ( __isl_keep isl_set Set)

Definition at line 905 of file ISLTools.cpp.

References dumpExpanded(), and isl::manage_copy().

◆ dumpExpanded() [3/8]

LLVM_DUMP_METHOD void polly::dumpExpanded ( __isl_keep isl_union_map UMap)

Definition at line 917 of file ISLTools.cpp.

References dumpExpanded(), and isl::manage_copy().

◆ dumpExpanded() [4/8]

LLVM_DUMP_METHOD void polly::dumpExpanded ( __isl_keep isl_union_set USet)

Definition at line 913 of file ISLTools.cpp.

References dumpExpanded(), and isl::manage_copy().

◆ dumpExpanded() [5/8]

LLVM_DUMP_METHOD void polly::dumpExpanded ( const isl::map Map)

Definition at line 893 of file ISLTools.cpp.

References expand(), printSortedPolyhedra(), and isl::map::wrap().

◆ dumpExpanded() [6/8]

LLVM_DUMP_METHOD void polly::dumpExpanded ( const isl::set Set)

Dump all points of the argument to llvm::errs().

Before being printed by dumpPw(), the argument's pieces are expanded to contain only single points. If a dimension is unbounded, it keeps its representation.

This is useful for debugging reduced cases where parameters are set to constants to keep the example simple. Such sets can still contain existential dimensions which makes the polyhedral hard to compare.

Example: { [MemRef_A[i0] -> [i1]] : (exists (e0 = floor((1 + i1)/3): i0 = 1 and 3e0 <= i1 and 3e0 >= -1 + i1 and i1 >= 15 and i1 <= 25)) or (exists (e0 = floor((i1)/3): i0 = 0 and 3e0 < i1 and 3e0 >= -2 + i1 and i1 > 0 and i1 <= 11)) }

dumpExpanded: { [MemRef_A[0] ->[1]]; [MemRef_A[0] ->[2]]; [MemRef_A[0] ->[4]]; [MemRef_A[0] ->[5]]; [MemRef_A[0] ->[7]]; [MemRef_A[0] ->[8]]; [MemRef_A[0] ->[10]]; [MemRef_A[0] ->[11]]; [MemRef_A[1] ->[15]]; [MemRef_A[1] ->[16]]; [MemRef_A[1] ->[18]]; [MemRef_A[1] ->[19]]; [MemRef_A[1] ->[21]]; [MemRef_A[1] ->[22]]; [MemRef_A[1] ->[24]]; [MemRef_A[1] ->[25]] }

Definition at line 889 of file ISLTools.cpp.

References expand(), and printSortedPolyhedra().

Referenced by dumpExpanded().

◆ dumpExpanded() [7/8]

LLVM_DUMP_METHOD void polly::dumpExpanded ( const isl::union_map UMap)

Definition at line 901 of file ISLTools.cpp.

References expand(), printSortedPolyhedra(), and isl::union_map::wrap().

◆ dumpExpanded() [8/8]

LLVM_DUMP_METHOD void polly::dumpExpanded ( const isl::union_set USet)

Definition at line 897 of file ISLTools.cpp.

References expand(), and printSortedPolyhedra().

◆ dumpIslObj() [1/2]

void polly::dumpIslObj ( __isl_keep isl_schedule_node node,
llvm::raw_ostream &  OS 
)

◆ dumpIslObj() [2/2]

void polly::dumpIslObj ( const isl::schedule_node Node,
llvm::raw_ostream &  OS 
)

Emit the equivaltent of the isl_*_dump output into a raw_ostream.

◆ dumpPw() [1/8]

LLVM_DUMP_METHOD void polly::dumpPw ( __isl_keep isl_map Map)

Definition at line 877 of file ISLTools.cpp.

References dumpPw(), and isl::manage_copy().

◆ dumpPw() [2/8]

LLVM_DUMP_METHOD void polly::dumpPw ( __isl_keep isl_set Set)

Definition at line 873 of file ISLTools.cpp.

References dumpPw(), and isl::manage_copy().

◆ dumpPw() [3/8]

LLVM_DUMP_METHOD void polly::dumpPw ( __isl_keep isl_union_map UMap)

Definition at line 885 of file ISLTools.cpp.

References dumpPw(), and isl::manage_copy().

◆ dumpPw() [4/8]

LLVM_DUMP_METHOD void polly::dumpPw ( __isl_keep isl_union_set USet)

Definition at line 881 of file ISLTools.cpp.

References dumpPw(), and isl::manage_copy().

◆ dumpPw() [5/8]

LLVM_DUMP_METHOD void polly::dumpPw ( const isl::map Map)

Definition at line 861 of file ISLTools.cpp.

References printSortedPolyhedra(), and isl::map::wrap().

◆ dumpPw() [6/8]

LLVM_DUMP_METHOD void polly::dumpPw ( const isl::set Set)

Dump a description of the argument to llvm::errs().

In contrast to isl's dump function, there are a few differences:

  • Each polyhedron (pieces) is written on its own line.
  • Spaces are sorted by structure. E.g. maps with same domain space are grouped. Isl sorts them according to the space's hash function.
  • Pieces of the same space are sorted using their lower bound.
  • A more compact to_str representation is used instead of Isl's dump functions that try to show the internal representation.

The goal is to get a better understandable representation that is also useful to compare two sets. As all dump() functions, its intended use is to be called in a debugger only.

isl_map_dump example: [p_0, p_1, p_2] -> { Stmt0[i0] -> [o0, o1] : (o0 = i0 and o1 = 0 and i0 > 0 and i0 <= 5 - p_2) or (i0 = 0 and o0 = 0 and o1 = 0); Stmt3[i0] -> [o0, o1] : (o0 = i0 and o1 = 3 and i0 > 0 and i0 <= 5 - p_2) or (i0 = 0 and o0 = 0 and o1 = 3); Stmt2[i0] -> [o0, o1] : (o0 = i0 and o1 = 1 and i0 >= 3 + p_0 - p_1 and i0 > 0 and i0 <= 5 - p_2) or (o0 = i0 and o1 = 1 and i0 > 0 and i0 <= 5 - p_2 and i0 < p_0 - p_1) or (i0 = 0 and o0 = 0 and o1 = 1 and p_1 >= 3

  • p_0) or (i0 = 0 and o0 = 0 and o1 = 1 and p_1 < p_0) or (p_0 = 0 and i0 = 2 - p_1 and o0 = 2 - p_1 and o1 = 1 and p_2 <= 3 + p_1 and p_1 <= 1) or (p_1 = 1 + p_0 and i0 = 0 and o0 = 0 and o1 = 1) or (p_0 = 0 and p_1 = 2 and i0 = 0 and o0 = 0 and o1 = 1) or (p_0 = -1 and p_1 = -1 and i0 = 0 and o0 = 0 and o1 = 1); Stmt1[i0] -> [o0, o1] : (p_0 = -1 and i0 = 1 - p_1 and o0 = 1 - p_1 and o1 = 2 and p_2 <= 4 + p_1 and p_1 <= 0) or (p_0 = 0 and i0 = -p_1 and o0 = -p_1 and o1 = 2 and p_2 <= 5 + p_1 and p_1 < 0) or (p_0 = -1 and p_1 = 1 and i0 = 0 and o0 = 0 and o1 = 2) or (p_0 = 0 and p_1 = 0 and i0 = 0 and o0 = 0 and o1 = 2) }

dumpPw example (same set): [p_0, p_1, p_2] -> { Stmt0[0] -> [0, 0]; Stmt0[i0] -> [i0, 0] : 0 < i0 <= 5 - p_2; Stmt1[0] -> [0, 2] : p_1 = 1 and p_0 = -1; Stmt1[0] -> [0, 2] : p_1 = 0 and p_0 = 0; Stmt1[1 - p_1] -> [1 - p_1, 2] : p_0 = -1 and p_1 <= 0 and p_2 <= 4 + p_1; Stmt1[-p_1] -> [-p_1, 2] : p_0 = 0 and p_1 < 0 and p_2 <= 5 + p_1; Stmt2[0] -> [0, 1] : p_1 >= 3 + p_0; Stmt2[0] -> [0, 1] : p_1 < p_0; Stmt2[0] -> [0, 1] : p_1 = 1 + p_0; Stmt2[0] -> [0, 1] : p_1 = 2 and p_0 = 0; Stmt2[0] -> [0, 1] : p_1 = -1 and p_0 = -1; Stmt2[i0] -> [i0, 1] : i0 >= 3 + p_0 - p_1 and 0 < i0 <= 5 - p_2; Stmt2[i0] -> [i0, 1] : 0 < i0 <= 5 - p_2 and i0 < p_0 - p_1; Stmt2[2 - p_1] -> [2 - p_1, 1] : p_0 = 0 and p_1 <= 1 and p_2 <= 3 + p_1; Stmt3[0] -> [0, 3]; Stmt3[i0] -> [i0, 3] : 0 < i0 <= 5 - p_2 }

Definition at line 857 of file ISLTools.cpp.

References printSortedPolyhedra().

Referenced by dumpPw().

◆ dumpPw() [7/8]

LLVM_DUMP_METHOD void polly::dumpPw ( const isl::union_map UMap)

Definition at line 869 of file ISLTools.cpp.

References printSortedPolyhedra(), and isl::union_map::wrap().

◆ dumpPw() [8/8]

LLVM_DUMP_METHOD void polly::dumpPw ( const isl::union_set USet)

Definition at line 865 of file ISLTools.cpp.

References printSortedPolyhedra().

◆ emitRejectionRemarks()

void polly::emitRejectionRemarks ( const BBPair P,
const RejectLog Log,
OptimizationRemarkEmitter &  ORE 
)

Emit optimization remarks about the rejected regions to the user.

This emits the content of the reject log as optimization remarks. Remember to at least track failures (-polly-detect-track-failures).

Parameters
PThe region delimiters (entry & exit) we emit remarks for.
LogThe error log containing all messages being emitted as remark.

Definition at line 135 of file ScopDetectionDiagnostic.cpp.

References DEBUG_TYPE, and getDebugLocations().

Referenced by polly::ScopDetection::emitMissedRemarks().

◆ EnableDeLICM()

static cl::opt< bool > polly::EnableDeLICM ( "polly-enable-delicm"  ,
cl::desc("Eliminate scalar loop carried dependences")  ,
cl::Hidden  ,
cl::init(true)  ,
cl::cat(PollyCategory  
)
static

◆ EnableForwardOpTree()

static cl::opt< bool > polly::EnableForwardOpTree ( "polly-enable-optree"  ,
cl::desc("Enable operand tree forwarding")  ,
cl::Hidden  ,
cl::init(true)  ,
cl::cat(PollyCategory  
)
static

◆ EnablePruneUnprofitable()

static cl::opt< bool > polly::EnablePruneUnprofitable ( "polly-enable-prune-unprofitable"  ,
cl::desc("Bail out on unprofitable SCoPs before rescheduling")  ,
cl::Hidden  ,
cl::init(true)  ,
cl::cat(PollyCategory  
)
static

◆ EnableSimplify()

static cl::opt< bool > polly::EnableSimplify ( "polly-enable-simplify"  ,
cl::desc("Simplify SCoP after optimizations")  ,
cl::init(true)  ,
cl::cat(PollyCategory  
)
static

◆ executeScopConditionally()

std::pair< BBPair, llvm::BranchInst * > polly::executeScopConditionally ( Scop S,
llvm::Value *  RTC,
llvm::DominatorTree &  DT,
llvm::RegionInfo &  RI,
llvm::LoopInfo &  LI 
)

Execute a Scop conditionally wrt RTC.

In the CFG the optimized code of the Scop is generated next to the original code. Both the new and the original version of the code remain in the CFG. A branch statement decides which version is executed based on the runtime value of RTC.

Before transformation:

                   bb0
                    |
                orig_scop
                    |
                   bb1

After transformation: bb0 | polly.splitBlock / . | startBlock | | orig_scop new_scop \ / \ / bb1 (joinBlock)

Parameters
SThe Scop to execute conditionally.
PA reference to the pass calling this function.
RTCThe runtime condition checked before executing the new SCoP.
Returns
An std::pair:
  • The first element is a BBPair of (StartBlock, EndBlock).
  • The second element is the BranchInst which conditionally branches to the SCoP based on the RTC.

Referenced by generateCode().

◆ expandCodeFor()

llvm::Value * polly::expandCodeFor ( Scop S,
llvm::ScalarEvolution &  SE,
const llvm::DataLayout &  DL,
const char *  Name,
const llvm::SCEV *  E,
llvm::Type *  Ty,
llvm::Instruction *  IP,
ValueMapT VMap,
llvm::BasicBlock *  RTCBB 
)

Wrapper for SCEVExpander extended to all Polly features.

This wrapper will internally call the SCEVExpander but also makes sure that all additional features not represented in SCEV (e.g., SDiv/SRem are not black boxes but can be part of the function) will be expanded correctly.

The parameters are the same as for the creation of a SCEVExpander as well as the call to SCEVExpander::expandCodeFor:

Parameters
SThe current Scop.
SEThe Scalar Evolution pass.
DLThe module data layout.
NameThe suffix added to the new instruction names.
EThe expression for which code is actually generated.
TyThe type of the resulting code.
IPThe insertion point for the new code.
VMapA remapping of values used in E.
RTCBBThe last block of the RTC. Used to insert loop-invariant instructions in rare cases.

Referenced by polly::IslExprBuilder::createAccessAddress(), polly::IslNodeBuilder::generateSCEV(), and polly::BlockGenerator::trySynthesizeNewValue().

◆ ExportJScop()

static cl::opt< bool > polly::ExportJScop ( "polly-export"  ,
cl::desc("Export the polyhedral description of the detected Scops")  ,
cl::Hidden  ,
cl::cat(PollyCategory  
)
static

◆ extractConstantFactor()

std::pair< const llvm::SCEVConstant *, const llvm::SCEV * > polly::extractConstantFactor ( const llvm::SCEV *  M,
llvm::ScalarEvolution &  SE 
)

Extract the constant factors from the multiplication M.

Parameters
MA potential SCEV multiplication.
SEThe ScalarEvolution analysis to create new SCEVs.
Returns
The constant factor in M and the rest of M.

Referenced by polly::Scop::addParams(), polly::ScopBuilder::addUserAssumptions(), and polly::SCEVAffinator::visit().

◆ filterKnownValInst()

isl::union_map polly::filterKnownValInst ( const isl::union_map UMap)

Return only the mappings that map to known values.

Parameters
UMap{ [] -> ValInst[] }
Returns
{ [] -> ValInst[] }

Definition at line 254 of file ZoneAlgo.cpp.

References isl::union_map::ctx(), isl::union_map::empty(), isl::union_map::get_map_list(), isMapToUnknown(), and isl::union_map::unite().

Referenced by polly::ZoneAlgorithm::computeKnownFromMustWrites().

◆ findLoops()

void polly::findLoops ( const llvm::SCEV *  Expr,
llvm::SetVector< const llvm::Loop * > &  Loops 
)

Find the loops referenced from a SCEV expression.

Parameters
ExprThe SCEV expression to scan for loops.
LoopsA vector into which the found loops are inserted.

Referenced by polly::ScopBuilder::buildAccessSingleDim(), polly::IslNodeBuilder::getReferencesInSubtree(), and polly::ScopDetection::isValidAccess().

◆ findMetadataOperand()

std::optional< llvm::Metadata * > polly::findMetadataOperand ( llvm::MDNode *  LoopMD,
llvm::StringRef  Name 
)

Find a property value in a LoopID.

Generally, a property MDNode has the format

!{ !"Name", value }

In which case the value is returned.

If the property is just

!{ !"Name" }

Then nullptr is set to mark the property is existing, but does not carry any value. If the property does not exist, std::nullopt is returned.

◆ findValues()

void polly::findValues ( const llvm::SCEV *  Expr,
llvm::ScalarEvolution &  SE,
llvm::SetVector< llvm::Value * > &  Values 
)

Find the values referenced by SCEVUnknowns in a given SCEV expression.

Parameters
ExprThe SCEV expression to scan for SCEVUnknowns.
SEThe ScalarEvolution analysis for this function.
ValuesA vector into which the found values are inserted.

Referenced by polly::ScopBuilder::addInvariantLoads(), polly::IslNodeBuilder::getReferencesInSubtree(), polly::ScopDetection::involvesMultiplePtrs(), polly::IslNodeBuilder::materializeValue(), and polly::IslNodeBuilder::preloadInvariantEquivClass().

◆ flattenSchedule()

isl::union_map polly::flattenSchedule ( isl::union_map  Schedule)

Recursively flatten a schedule.

Reduce the number of scatter dimensions as much as possible without changing the relative order of instances in a schedule. Ideally, this results in a single scatter dimension, but it may not always be possible to combine dimensions, eg. if a dimension is unbounded. In worst case, the original schedule is returned.

Schedules with fewer dimensions may be easier to understand for humans, but it should make no difference to the computer.

Parameters
ScheduleThe input schedule.
Returns
The flattened schedule.

Definition at line 306 of file FlattenAlgo.cpp.

References getNumScatterDims(), and POLLY_DEBUG.

◆ FullyIndexedStaticExpansion()

static cl::opt< bool > polly::FullyIndexedStaticExpansion ( "polly-enable-mse"  ,
cl::desc("Fully expand the memory accesses of the detected Scops")  ,
cl::Hidden  ,
cl::cat(PollyCategory  
)
static

◆ getAccessesInOrder()

SmallVector< MemoryAccess *, 32 > polly::getAccessesInOrder ( ScopStmt Stmt)

Return a vector that contains MemoryAccesses in the order in which they are executed.

The order is:

Definition at line 828 of file Simplify.cpp.

◆ getBandAttr()

BandAttr * polly::getBandAttr ( isl::schedule_node  MarkOrBand)

Extract the BandAttr from a band's wrapping marker.

Can also pass the band itself and this methods will try to find its wrapping mark. Returns nullptr if the band has not BandAttr.

Definition at line 966 of file ScheduleTreeTransform.cpp.

References isl::schedule_node::as(), isl::schedule_node_mark::get_id(), and getLoopAttr().

◆ getBBPairForRegion()

BBPair polly::getBBPairForRegion ( const Region *  R)

◆ getBooleanLoopAttribute()

bool polly::getBooleanLoopAttribute ( llvm::MDNode *  LoopID,
llvm::StringRef  Name 
)

Find a boolean property value in a LoopID.

The value not being defined is interpreted as a false value.

Referenced by hasDisableAllTransformsHint().

◆ getConditionFromTerminator()

llvm::Value * polly::getConditionFromTerminator ( llvm::Instruction *  TI)

Return the condition for the terminator TI.

For unconditional branches the "i1 true" condition will be returned.

Parameters
TIThe terminator to get the condition from.
Returns
The condition of TI and nullptr if none could be extracted.

Referenced by polly::ScopBuilder::buildConditionSets(), and polly::ScopDetection::isValidCFG().

◆ getConstant() [1/2]

isl::val polly::getConstant ( isl::map  Map,
isl::dim  Dim,
int  Pos 
)

If the relation PwAff lies on a hyperplane where the given dimension Pos with the type Dim has a fixed value, then return that value.

Otherwise return NaN.

Definition at line 266 of file ISLTools.cpp.

References assert, isl::map::dim(), isl::map::get(), isl_map_plain_get_val_if_fixed(), isl::manage(), and unsignedFromIslSize().

◆ getConstant() [2/2]

isl::val polly::getConstant ( isl::pw_aff  PwAff,
bool  Max,
bool  Min 
)

If PwAff maps to a constant, return said constant.

If Max/Min, it can also be a piecewise constant and it would return the minimum/maximum value. Otherwise, return NaN.

Definition at line 552 of file ISLTools.cpp.

References assert, isl::aff::ctx(), isl::val::eq(), isl::stat::error(), isl::pw_aff::foreach_piece(), isl::aff::get_constant_val(), if(), isl::aff::is_cst(), isl::stat::is_error(), isl::val::is_nan(), isl::val::is_null(), isl::val::nan(), and isl::stat::ok().

Referenced by polly::Scop::createScopArrayInfo(), and flatCompare().

◆ getDebugLocation() [1/2]

void polly::getDebugLocation ( const llvm::Region *  R,
unsigned &  LineBegin,
unsigned &  LineEnd,
std::string &  FileName 
)

Get the location of a region from the debug info.

Parameters
RThe region to get debug info for.
LineBeginThe first line in the region.
LineEndThe last line in the region.
FileNameThe filename where the region was defined.

Referenced by getJSON(), and polly::ScopDetection::printLocations().

◆ getDebugLocation() [2/2]

void polly::getDebugLocation ( const Region *  R,
unsigned &  LineBegin,
unsigned &  LineEnd,
std::string &  FileName 
)

Definition at line 21 of file ScopLocation.cpp.

◆ getDebugLocations()

void polly::getDebugLocations ( const BBPair P,
DebugLoc &  Begin,
DebugLoc &  End 
)

Set the begin and end source location for the region limited by P.

Definition at line 113 of file ScopDetectionDiagnostic.cpp.

Referenced by emitRejectionRemarks(), and polly::ScopBuilder::ScopBuilder().

◆ getDimOptions()

isl::union_set polly::getDimOptions ( isl::ctx  Ctx,
const char *  Option 
)

Create an isl::union_set, which describes the specified option for the dimension of the current node.

Parameters
CtxAn isl::ctx, which is used to create the isl::union_set.
OptionThe name of the option.

Definition at line 1144 of file ScheduleTreeTransform.cpp.

References isl::id::alloc(), Ctx, and isl::set::universe().

◆ getFirstNonBoxedLoopFor() [1/2]

llvm::Loop * polly::getFirstNonBoxedLoopFor ( llvm::BasicBlock *  BB,
llvm::LoopInfo &  LI,
const BoxedLoopsSetTy BoxedLoops 
)

Definition at line 638 of file ScopHelper.cpp.

References getFirstNonBoxedLoopFor().

◆ getFirstNonBoxedLoopFor() [2/2]

llvm::Loop * polly::getFirstNonBoxedLoopFor ( llvm::Loop *  L,
llvm::LoopInfo &  LI,
const BoxedLoopsSetTy BoxedLoops 
)

◆ getIslCompatibleName() [1/3]

std::string polly::getIslCompatibleName ( const std::string &  Prefix,
const llvm::Value *  Val,
long  Number,
const std::string &  Suffix,
bool  UseInstructionNames 
)

Combine Prefix, Val (or Number) and Suffix to an isl-compatible name.

In case UseInstructionNames is set, this function returns:

Prefix + "_" + Val->getName() + Suffix

otherwise

Prefix + to_string(Number) + Suffix

We ignore the value names by default, as they may change between release and debug mode and can consequently not be used when aiming for reproducible builds. However, for debugging named statements are often helpful, hence we allow their optional use.

Referenced by polly::Scop::createParameterId(), makeStmtName(), polly::ZoneAlgorithm::makeValueId(), polly::ScopArrayInfo::ScopArrayInfo(), and polly::ScopStmt::ScopStmt().

◆ getIslCompatibleName() [2/3]

std::string polly::getIslCompatibleName ( const std::string &  Prefix,
const std::string &  Middle,
const std::string &  Suffix 
)

Definition at line 154 of file GICHelper.cpp.

References makeIslCompatible().

◆ getIslCompatibleName() [3/3]

std::string polly::getIslCompatibleName ( const std::string &  Prefix,
const std::string &  Middle,
long  Number,
const std::string &  Suffix,
bool  UseInstructionNames 
)

Combine Prefix, Name (or Number) and Suffix to an isl-compatible name.

In case UseInstructionNames is set, this function returns:

Prefix + "_" + Name + Suffix

otherwise

Prefix + to_string(Number) + Suffix

We ignore Name by default, as they may change between release and debug mode and can consequently not be used when aiming for reproducible builds. However, for debugging named statements are often helpful, hence we allow their optional use.

Definition at line 162 of file GICHelper.cpp.

References makeIslCompatible(), and UseInstructionNames.

◆ getIslLoopAttr()

isl::id polly::getIslLoopAttr ( isl::ctx  Ctx,
BandAttr Attr 
)

Get an isl::id representing a loop.

This takes the ownership of the BandAttr and will be free'd when the returned isl::Id is free'd.

Definition at line 778 of file ScopHelper.cpp.

References isl::id::alloc(), assert, Ctx, isl_id_set_free_user(), isl::manage(), and isl::id::release().

◆ getIsolateOptions()

isl::union_set polly::getIsolateOptions ( isl::set  IsolateDomain,
unsigned  OutDimsNum 
)

Create an isl::union_set, which describes the isolate option based on IsolateDomain.

Parameters
IsolateDomainAn isl::set whose OutDimsNum last dimensions should belong to the current band node.
OutDimsNumA number of dimensions that should belong to the current band node.

Definition at line 1127 of file ScheduleTreeTransform.cpp.

References isl::id::alloc(), assert, isl::set::ctx(), isl::map::from_domain(), isl::in, isl::map::move_dims(), isl::out, isl::set::set_tuple_id(), isl::set::tuple_dim(), unsignedFromIslSize(), and isl::map::wrap().

◆ getLoopAttr()

BandAttr * polly::getLoopAttr ( const isl::id Id)

Return the BandAttr of a loop's isl::id.

Definition at line 815 of file ScopHelper.cpp.

Referenced by polly::IslNodeBuilder::createMark(), and getBandAttr().

◆ getLoopSurroundingScop()

llvm::Loop * polly::getLoopSurroundingScop ( Scop S,
llvm::LoopInfo &  LI 
)

Get the smallest loop that contains S but is not in S.

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

◆ getNumBlocksInLoop()

unsigned polly::getNumBlocksInLoop ( llvm::Loop *  L)

Get the number of blocks in L.

The number of blocks in a loop are the number of basic blocks actually belonging to the loop, as well as all single basic blocks that the loop exits to and which terminate in an unreachable instruction. We do not allow such basic blocks in the exit of a scop, hence they belong to the scop and represent run-time conditions which we want to model and subsequently speculate away.

See also
getRegionNodeLoop for additional details.

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

◆ getNumBlocksInRegionNode()

unsigned polly::getNumBlocksInRegionNode ( llvm::RegionNode *  RN)

Get the number of blocks in RN.

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

◆ getNumScatterDims()

unsigned polly::getNumScatterDims ( const isl::union_map Schedule)

Determine how many dimensions the scatter space of Schedule has.

The schedule must not be empty and have equal number of dimensions of any subspace it contains.

The implementation currently returns the maximum number of dimensions it encounters, if different, and 0 if none is encountered. However, most other code will most likely fail if one of these happen.

Definition at line 163 of file ISLTools.cpp.

References isl::union_map::get_map_list(), and unsignedFromIslSize().

Referenced by flattenSchedule(), and getScatterSpace().

◆ getOptionalIntLoopAttribute()

std::optional< int > polly::getOptionalIntLoopAttribute ( llvm::MDNode *  LoopID,
llvm::StringRef  Name 
)

Find an integers property value in a LoopID.

◆ getParamsInAffineExpr()

ParameterSetTy polly::getParamsInAffineExpr ( const llvm::Region *  R,
llvm::Loop *  Scope,
const llvm::SCEV *  Expression,
llvm::ScalarEvolution &  SE 
)

◆ getPartialTilePrefixes()

isl::set polly::getPartialTilePrefixes ( isl::set  ScheduleRange,
int  VectorWidth 
)

Build the desired set of partial tile prefixes.

We build a set of partial tile prefixes, which are prefixes of the vector loop that have exactly VectorWidth iterations.

  1. Drop all constraints involving the dimension that represents the vector loop.
  2. Constrain the last dimension to get a set, which has exactly VectorWidth iterations.
  3. Subtract loop domain from it, project out the vector loop dimension and get a set that contains prefixes, which do not have exactly VectorWidth iterations.
  4. Project out the vector loop dimension of the set that was build on the first step and subtract the set built on the previous step to get the desired set of prefixes.
Parameters
ScheduleRangeA range of a map, which describes a prefix schedule relation.

Definition at line 1114 of file ScheduleTreeTransform.cpp.

References assert, isl::set::drop_constraints_involving_dims(), isl::set::project_out(), isl::set, isl::set::subtract(), isl::set::tuple_dim(), and unsignedFromIslSize().

◆ getPollyDebugFlag()

bool polly::getPollyDebugFlag ( )

Definition at line 20 of file PollyDebug.cpp.

References PollyDebugFlag.

◆ getRegionNodeLoop()

llvm::Loop * polly::getRegionNodeLoop ( llvm::RegionNode *  RN,
llvm::LoopInfo &  LI 
)

◆ getScatterSpace()

isl::space polly::getScatterSpace ( const isl::union_map Schedule)

Return the scatter space of a Schedule.

This is basically the range space of the schedule map, but harder to determine because it is an isl_union_map.

Definition at line 174 of file ISLTools.cpp.

References isl::space::add_dims(), isl::union_map::get_space(), getNumScatterDims(), isl::union_map::is_null(), isl::set, and isl::space::set_from_params().

Referenced by computeReachingWrite(), computeScalarReachingDefinition(), and polly::ZoneAlgorithm::ZoneAlgorithm().

◆ getUniqueNonErrorValue()

llvm::Value * polly::getUniqueNonErrorValue ( llvm::PHINode *  PHI,
llvm::Region *  R,
ScopDetection SD 
)

Return a unique non-error block incoming value for PHI if available.

Parameters
RThe region to run our code on.
SDThe ScopDetection

Referenced by polly::ScopBuilder::buildConditionSets(), and polly::ScopDetection::isValidBranch().

◆ getUseBlock()

llvm::BasicBlock * polly::getUseBlock ( const llvm::Use &  U)

Return the block in which a value is used.

For normal instructions, this is the instruction's parent block. For PHI nodes, this is the incoming block of that use, because this is where the operand must be defined (i.e. its definition dominates this block). Non-instructions do not use operands at a specific point such that in this case this function returns nullptr.

Definition at line 620 of file ScopHelper.cpp.

References PHI.

Referenced by polly::VirtualUse::create(), and polly::Scop::isEscaping().

◆ hasDebugCall()

bool polly::hasDebugCall ( ScopStmt Stmt)

Does the statement contain a call to a debug function?

Such a statement must not be removed, even if has no side-effects.

Definition at line 666 of file ScopHelper.cpp.

References DebugFunctions(), polly::ScopStmt::getEntryBlock(), polly::ScopStmt::getInstructions(), polly::ScopStmt::getRegion(), hasDebugCall(), isDebugCall(), and polly::ScopStmt::isRegionStmt().

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

◆ hasDisableAllTransformsHint() [1/2]

bool polly::hasDisableAllTransformsHint ( llvm::Loop *  L)

Does the loop's LoopID contain a 'llvm.loop.disable_heuristics' property?

This is equivalent to llvm::hasDisableAllTransformsHint(Loop*), but including the LoopUtils.h header indirectly also declares llvm::MemoryAccess which clashes with polly::MemoryAccess. Declaring this alias here avoid having to include LoopUtils.h in other files.

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

◆ hasDisableAllTransformsHint() [2/2]

bool polly::hasDisableAllTransformsHint ( llvm::MDNode *  LoopID)

Definition at line 774 of file ScopHelper.cpp.

References getBooleanLoopAttribute().

◆ hasScalarDepsInsideRegion()

bool polly::hasScalarDepsInsideRegion ( const llvm::SCEV *  Expr,
const llvm::Region *  R,
llvm::Loop *  Scope,
bool  AllowLoops,
const InvariantLoadsSetTy ILS 
)

Returns true when the SCEV contains references to instructions within the region.

Parameters
ExprThe SCEV to analyze.
RThe region in which we look for dependences.
ScopeLocation where the value is needed.
AllowLoopsWhether loop recurrences outside the loop that are in the region count as dependence.

Referenced by polly::ScopDetection::hasValidArraySizes().

◆ hoistExtensionNodes()

isl::schedule polly::hoistExtensionNodes ( isl::schedule  Sched)

Hoist all domains from extension into the root domain node, such that there are no more extension nodes (which isl does not support for some operations).

This assumes that domains added by to extension nodes do not overlap.

Definition at line 974 of file ScheduleTreeTransform.cpp.

◆ ImportJScop()

static cl::opt< bool > polly::ImportJScop ( "polly-import"  ,
cl::desc("Import the polyhedral description of the detected Scops")  ,
cl::Hidden  ,
cl::cat(PollyCategory  
)
static

◆ initializePollyPasses()

void polly::initializePollyPasses ( llvm::PassRegistry &  Registry)

Definition at line 216 of file RegisterPasses.cpp.

References llvm::initializeCodeGenerationPass(), llvm::initializeCodePreparationPass(), llvm::initializeDeadCodeElimWrapperPassPass(), llvm::initializeDeLICMPrinterLegacyPassPass(), llvm::initializeDeLICMWrapperPassPass(), llvm::initializeDependenceInfoPass(), llvm::initializeDependenceInfoPrinterLegacyFunctionPassPass(), llvm::initializeDependenceInfoPrinterLegacyPassPass(), llvm::initializeDependenceInfoWrapperPassPass(), llvm::initializeDumpModuleWrapperPassPass(), llvm::initializeFlattenSchedulePass(), llvm::initializeFlattenSchedulePrinterLegacyPassPass(), llvm::initializeForwardOpTreePrinterLegacyPassPass(), llvm::initializeForwardOpTreeWrapperPassPass(), llvm::initializeIslAstInfoPrinterLegacyPassPass(), llvm::initializeIslAstInfoWrapperPassPass(), llvm::initializeIslScheduleOptimizerPrinterLegacyPassPass(), llvm::initializeIslScheduleOptimizerWrapperPassPass(), llvm::initializeJSONExporterPass(), llvm::initializeJSONImporterPass(), llvm::initializeJSONImporterPrinterLegacyPassPass(), llvm::initializeMaximalStaticExpanderWrapperPassPass(), llvm::initializePollyCanonicalizePass(), llvm::initializePolyhedralInfoPass(), llvm::initializePolyhedralInfoPrinterLegacyPassPass(), llvm::initializePruneUnprofitableWrapperPassPass(), llvm::initializeScopDetectionPrinterLegacyPassPass(), llvm::initializeScopDetectionWrapperPassPass(), llvm::initializeScopInfoPrinterLegacyFunctionPassPass(), llvm::initializeScopInfoPrinterLegacyRegionPassPass(), llvm::initializeScopInfoRegionPassPass(), llvm::initializeScopInfoWrapperPassPass(), llvm::initializeScopInlinerPass(), llvm::initializeSimplifyPrinterLegacyPassPass(), and llvm::initializeSimplifyWrapperPassPass().

◆ intersectRange()

isl::map polly::intersectRange ( isl::map  Map,
isl::union_set  Range 
)

Intersect the range of Map with Range.

Since Map is an isl::map, the result will be a single space, even though Range is an isl::union_set. This is the only difference to isl::map::intersect_range and isl::union_map::interset_range.

Parameters
Map{ Domain[] -> Range[] }
Range{ Range[] }
Returns
{ Domain[] -> Range[] }

Definition at line 535 of file ISLTools.cpp.

References isl::map::get_space(), isl::map::intersect_range(), Range, and isl::space::range().

Referenced by polly::ZoneAlgorithm::addArrayReadAccess(), and polly::ZoneAlgorithm::addArrayWriteAccess().

◆ isAffineConstraint()

bool polly::isAffineConstraint ( llvm::Value *  V,
const llvm::Region *  R,
llvm::Loop *  Scope,
llvm::ScalarEvolution &  SE,
ParameterSetTy Params,
bool  OrExpr = false 
)

Check if V describes an affine constraint in R.

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

◆ isAffineExpr()

bool polly::isAffineExpr ( const llvm::Region *  R,
llvm::Loop *  Scope,
const llvm::SCEV *  Expression,
llvm::ScalarEvolution &  SE,
InvariantLoadsSetTy ILS = nullptr 
)

◆ isBandMark()

bool polly::isBandMark ( const isl::schedule_node Node)

Is this node the marker for its parent band?

Definition at line 961 of file ScheduleTreeTransform.cpp.

References isl::schedule_node::as(), isl::schedule_node_mark::get_id(), and isLoopAttr().

◆ isConflicting()

bool polly::isConflicting ( isl::union_set  ExistingOccupied,
isl::union_set  ExistingUnused,
isl::union_map  ExistingKnown,
isl::union_map  ExistingWrites,
isl::union_set  ProposedOccupied,
isl::union_set  ProposedUnused,
isl::union_map  ProposedKnown,
isl::union_map  ProposedWrites,
llvm::raw_ostream *  OS = nullptr,
unsigned  Indent = 0 
)

Determine whether two lifetimes are conflicting.

Used by unittesting.

Definition at line 1515 of file DeLICM.cpp.

◆ isDebugCall()

bool polly::isDebugCall ( llvm::Instruction *  Inst)

Is the given instruction a call to a debug function?

A debug function can be used to insert output in Polly-optimized code which normally does not allow function calls with side-effects. For instance, a printf can be inserted to check whether a value still has the expected value after Polly generated code:

int sum = 0;
for (int i = 0; i < 16; i+=1) {
  sum += i;
  printf("The value of sum at i=%d is %d\n", sum, i);
} 

Referenced by polly::ScopBuilder::buildAccessCallInst(), hasDebugCall(), hasDebugCall(), isErrorBlockImpl(), and polly::ScopDetection::isValidCallInst().

◆ isHoistableLoad()

bool polly::isHoistableLoad ( llvm::LoadInst *  LInst,
llvm::Region &  R,
llvm::LoopInfo &  LI,
llvm::ScalarEvolution &  SE,
const llvm::DominatorTree &  DT,
const InvariantLoadsSetTy KnownInvariantLoads 
)

Check if LInst can be hoisted in R.

Parameters
LInstThe load to check.
RThe analyzed region.
LIThe loop info.
SEThe scalar evolution analysis.
DTThe dominator tree of the function.
KnownInvariantLoadsThe invariant load set.
Returns
True if LInst can be hoisted in R.

Referenced by polly::ScopDetection::hasValidArraySizes(), polly::ScopDetection::isValidAccess(), and polly::ScopDetection::onlyValidRequiredInvariantLoads().

◆ isIgnoredIntrinsic()

bool polly::isIgnoredIntrinsic ( const llvm::Value *  V)

◆ isl_valFromAPInt()

__isl_give isl_val * polly::isl_valFromAPInt ( isl_ctx Ctx,
const llvm::APInt  Int,
bool  IsSigned 
)

Translate an llvm::APInt to an isl_val.

Translate the bitsequence without sign information as provided by APInt into a signed isl_val type. Depending on the value of IsSigned Int is interpreted as unsigned value or as signed value in two's complement representation.

Input IsSigned Output

0        0           ->    0
1        0           ->    1

00 0 -> 0 01 0 -> 1 10 0 -> 2 11 0 -> 3

0 1 -> 0 1 1 -> -1 00 1 -> 0 01 1 -> 1 10 1 -> -2 11 1 -> -1

Parameters
CtxThe isl_ctx to create the isl_val in.
IntThe integer value to translate.
IsSignedIf the APInt should be interpreted as signed or unsigned value.
Returns
The isl_val corresponding to Int.

Referenced by valFromAPInt(), and polly::SCEVAffinator::visitConstant().

◆ isLoopAttr()

bool polly::isLoopAttr ( const isl::id Id)

Is Id representing a loop?

Such ids contain a polly::BandAttr as its user pointer.

Definition at line 808 of file ScopHelper.cpp.

References isl::id::get_name(), and isl::id::is_null().

Referenced by isBandMark().

◆ isScopPassName()

static bool polly::isScopPassName ( StringRef  Name)
static

Definition at line 523 of file RegisterPasses.cpp.

Referenced by parseTopLevelPipeline().

◆ liftDomains()

isl::union_map polly::liftDomains ( isl::union_map  UMap,
isl::union_set  Factor 
)

Prepend a space to the tuples of a map.

Parameters
UMap{ Domain[] -> Range[] }
Factor{ Factor[] }
Returns
{ [Factor[] -> Domain[]] -> [Factor[] -> Range[]] }

Definition at line 509 of file ISLTools.cpp.

References makeIdentityMap(), and isl::union_map::product().

Referenced by applyDomainRange().

◆ makeIdentityMap() [1/2]

isl::map polly::makeIdentityMap ( const isl::set Set,
bool  RestrictDomain 
)

Construct an identity map for the given domain values.

Parameters
USet{ Space[] } The returned map's domain and range.
RestrictDomainIf true, the returned map only maps elements contained in Set and no other. If false, it returns an overapproximation with the identity maps of any space in Set, not just the elements in it.
Returns
{ Space[] -> Space[] } A map that maps each value of Set to itself.

Definition at line 182 of file ISLTools.cpp.

References isl::set::get_space(), isl::map::identity(), isl::map::intersect_domain(), and isl::space::map_from_set().

Referenced by liftDomains(), and makeIdentityMap().

◆ makeIdentityMap() [2/2]

isl::union_map polly::makeIdentityMap ( const isl::union_set USet,
bool  RestrictDomain 
)

Construct an identity map for the given domain values.

There is no type resembling isl_union_space, hence we have to pass an isl_union_set as the map's domain and range space.

Parameters
USet{ Space[] } The returned map's domain and range.
RestrictDomainIf true, the returned map only maps elements contained in USet and no other. If false, it returns an overapproximation with the identity maps of any space in USet, not just the elements in it.
Returns
{ Space[] -> Space[] } A map that maps each value of USet to itself.

Definition at line 189 of file ISLTools.cpp.

References isl::union_set::ctx(), isl::union_map::empty(), isl::union_set::get_set_list(), makeIdentityMap(), and isl::union_map::unite().

◆ makeUnknownForDomain()

isl::union_map polly::makeUnknownForDomain ( isl::union_set  Domain)

Create a domain-to-unknown value mapping.

Value instances that do not represent a specific value are represented by an unnamed tuple of 0 dimensions. Its meaning depends on the context. It can either mean a specific but unknown value which cannot be represented by other means. It conflicts with itself because those two unknown ValInsts may have different concrete values at runtime.

The other meaning is an arbitrary or wildcard value that can be chosen freely, like LLVM's undef. If matched with an unknown ValInst, there is no conflict.

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

Definition at line 229 of file ZoneAlgo.cpp.

References Domain, and isl::union_map::from_domain().

◆ markBlockUnreachable()

void polly::markBlockUnreachable ( BasicBlock &  Block,
PollyIRBuilder Builder 
)

Mark a basic block unreachable.

Marks the basic block Block unreachable by equipping it with an UnreachableInst.

Definition at line 78 of file CodeGeneration.cpp.

Referenced by generateCode().

◆ markReachable()

void polly::markReachable ( Scop S,
LoopInfo *  LI,
DenseSet< VirtualInstruction > &  UsedInsts,
DenseSet< MemoryAccess * > &  UsedAccs,
ScopStmt OnlyLocal = nullptr 
)

Find all reachable instructions and accesses.

Parameters
SThe SCoP to find everything reachable in.
LILoopInfo required for analysis.
UsedInsts[out]Receives all reachable instructions.
UsedAccs[out]Receives all reachable accesses.
OnlyLocalIf non-nullptr, activates local mode: The SCoP is assumed to consist only of this statement and is conservatively correct. Does not require walking the whole SCoP.

Definition at line 405 of file VirtualInstruction.cpp.

References addRoots(), and walkReachable().

◆ operator%() [1/5]

isl::pw_aff polly::operator% ( isl::pw_aff  Left,
isl::pw_aff  Right 
)
inline

Remainder.

This is the remainder of a division which rounds towards zero. This follows the semantics of C/C++.

Definition at line 153 of file ISLOperators.h.

References isl::pw_aff::tdiv_r().

◆ operator%() [2/5]

isl::pw_aff polly::operator% ( isl::pw_aff  Left,
isl::val  ValRight 
)
inline

Definition at line 162 of file ISLOperators.h.

References isl::pw_aff::domain(), and isl::pw_aff::tdiv_r().

◆ operator%() [3/5]

isl::pw_aff polly::operator% ( isl::pw_aff  Left,
long  IntRight 
)
inline

Definition at line 174 of file ISLOperators.h.

References isl::pw_aff::ctx(), Ctx, isl::pw_aff::domain(), and isl::pw_aff::tdiv_r().

◆ operator%() [4/5]

isl::pw_aff polly::operator% ( isl::val  ValLeft,
isl::pw_aff  Right 
)
inline

Definition at line 157 of file ISLOperators.h.

References isl::pw_aff::domain(), and isl::pw_aff::tdiv_r().

◆ operator%() [5/5]

isl::pw_aff polly::operator% ( long  IntLeft,
isl::pw_aff  Right 
)
inline

Definition at line 167 of file ISLOperators.h.

References isl::pw_aff::ctx(), Ctx, isl::pw_aff::domain(), and isl::pw_aff::tdiv_r().

◆ operator*() [1/5]

isl::pw_aff polly::operator* ( isl::pw_aff  Left,
isl::pw_aff  Right 
)
inline

Multiplication.

Definition at line 53 of file ISLOperators.h.

References isl::pw_aff::mul().

◆ operator*() [2/5]

isl::pw_aff polly::operator* ( isl::pw_aff  Left,
isl::val  ValRight 
)
inline

Definition at line 62 of file ISLOperators.h.

References isl::pw_aff::domain(), and isl::pw_aff::mul().

◆ operator*() [3/5]

isl::pw_aff polly::operator* ( isl::pw_aff  Left,
long  IntRight 
)
inline

Definition at line 74 of file ISLOperators.h.

References isl::pw_aff::ctx(), Ctx, isl::pw_aff::domain(), and isl::pw_aff::mul().

◆ operator*() [4/5]

isl::pw_aff polly::operator* ( isl::val  ValLeft,
isl::pw_aff  Right 
)
inline

Definition at line 57 of file ISLOperators.h.

References isl::pw_aff::domain(), and isl::pw_aff::mul().

◆ operator*() [5/5]

isl::pw_aff polly::operator* ( long  IntLeft,
isl::pw_aff  Right 
)
inline

Definition at line 67 of file ISLOperators.h.

References isl::pw_aff::ctx(), Ctx, isl::pw_aff::domain(), and isl::pw_aff::mul().

◆ operator+() [1/6]

isl::pw_aff polly::operator+ ( isl::pw_aff  Left,
isl::pw_aff  Right 
)
inline

Addition.

Definition at line 22 of file ISLOperators.h.

References isl::pw_aff::add().

◆ operator+() [2/6]

isl::pw_aff polly::operator+ ( isl::pw_aff  Left,
isl::val  ValRight 
)
inline

Definition at line 31 of file ISLOperators.h.

References isl::pw_aff::add(), and isl::pw_aff::domain().

◆ operator+() [3/6]

isl::pw_aff polly::operator+ ( isl::pw_aff  Left,
long  IntRight 
)
inline

Definition at line 43 of file ISLOperators.h.

References isl::pw_aff::add(), isl::pw_aff::ctx(), Ctx, and isl::pw_aff::domain().

◆ operator+() [4/6]

isl::pw_aff polly::operator+ ( isl::val  ValLeft,
isl::pw_aff  Right 
)
inline

Definition at line 26 of file ISLOperators.h.

References isl::pw_aff::add(), and isl::pw_aff::domain().

◆ operator+() [5/6]

isl::pw_aff polly::operator+ ( long  IntLeft,
isl::pw_aff  Right 
)
inline

Definition at line 36 of file ISLOperators.h.

References isl::pw_aff::add(), isl::pw_aff::ctx(), Ctx, and isl::pw_aff::domain().

◆ operator+() [6/6]

template<typename T >
std::string polly::operator+ ( Twine  LHS,
const T &  RHS 
)

Small string conversion via raw_string_stream.

Definition at line 88 of file ScopDetectionDiagnostic.cpp.

◆ operator-() [1/5]

isl::pw_aff polly::operator- ( isl::pw_aff  Left,
isl::pw_aff  Right 
)
inline

Subtraction.

Definition at line 84 of file ISLOperators.h.

References isl::pw_aff::sub().

◆ operator-() [2/5]

isl::pw_aff polly::operator- ( isl::pw_aff  Left,
isl::val  ValRight 
)
inline

Definition at line 93 of file ISLOperators.h.

References isl::pw_aff::domain(), and isl::pw_aff::sub().

◆ operator-() [3/5]

isl::pw_aff polly::operator- ( isl::pw_aff  Left,
long  IntRight 
)
inline

Definition at line 105 of file ISLOperators.h.

References isl::pw_aff::ctx(), Ctx, isl::pw_aff::domain(), and isl::pw_aff::sub().

◆ operator-() [4/5]

isl::pw_aff polly::operator- ( isl::val  ValLeft,
isl::pw_aff  Right 
)
inline

Definition at line 88 of file ISLOperators.h.

References isl::pw_aff::domain(), and isl::pw_aff::sub().

◆ operator-() [5/5]

isl::pw_aff polly::operator- ( long  IntLeft,
isl::pw_aff  Right 
)
inline

Definition at line 98 of file ISLOperators.h.

References isl::pw_aff::ctx(), Ctx, isl::pw_aff::domain(), and isl::pw_aff::sub().

◆ operator/() [1/5]

isl::pw_aff polly::operator/ ( isl::pw_aff  Left,
isl::pw_aff  Right 
)
inline

Division.

This division rounds towards zero. This follows the semantics of C/C++.

Definition at line 118 of file ISLOperators.h.

References isl::pw_aff::tdiv_q().

◆ operator/() [2/5]

isl::pw_aff polly::operator/ ( isl::pw_aff  Left,
isl::val  ValRight 
)
inline

Definition at line 127 of file ISLOperators.h.

References isl::pw_aff::domain(), and isl::pw_aff::tdiv_q().

◆ operator/() [3/5]

isl::pw_aff polly::operator/ ( isl::pw_aff  Left,
long  IntRight 
)
inline

Definition at line 139 of file ISLOperators.h.

References isl::pw_aff::ctx(), Ctx, isl::pw_aff::domain(), and isl::pw_aff::tdiv_q().

◆ operator/() [4/5]

isl::pw_aff polly::operator/ ( isl::val  ValLeft,
isl::pw_aff  Right 
)
inline

Definition at line 122 of file ISLOperators.h.

References isl::pw_aff::domain(), and isl::pw_aff::tdiv_q().

◆ operator/() [5/5]

isl::pw_aff polly::operator/ ( long  IntLeft,
isl::pw_aff  Right 
)
inline

Definition at line 132 of file ISLOperators.h.

References isl::pw_aff::ctx(), Ctx, isl::pw_aff::domain(), and isl::pw_aff::tdiv_q().

◆ operator<<() [1/13]

llvm::DiagnosticInfoOptimizationBase & polly::operator<< ( llvm::DiagnosticInfoOptimizationBase &  OS,
const isl::union_map Obj 
)
inline

Definition at line 340 of file GICHelper.h.

◆ operator<<() [2/13]

llvm::raw_ostream & polly::operator<< ( llvm::raw_ostream &  OS,
__isl_keep isl_map Map 
)
inline

Definition at line 250 of file GICHelper.h.

◆ operator<<() [3/13]

llvm::raw_ostream & polly::operator<< ( llvm::raw_ostream &  OS,
__isl_keep isl_multi_aff MA 
)
inline

Definition at line 274 of file GICHelper.h.

◆ operator<<() [4/13]

llvm::raw_ostream & polly::operator<< ( llvm::raw_ostream &  OS,
__isl_keep isl_pw_aff Map 
)
inline

Definition at line 262 of file GICHelper.h.

◆ operator<<() [5/13]

llvm::raw_ostream & polly::operator<< ( llvm::raw_ostream &  OS,
__isl_keep isl_pw_multi_aff PMA 
)
inline

Definition at line 268 of file GICHelper.h.

◆ operator<<() [6/13]

llvm::raw_ostream & polly::operator<< ( llvm::raw_ostream &  OS,
__isl_keep isl_schedule Schedule 
)
inline

Definition at line 286 of file GICHelper.h.

◆ operator<<() [7/13]

llvm::raw_ostream & polly::operator<< ( llvm::raw_ostream &  OS,
__isl_keep isl_set Set 
)
inline

Definition at line 256 of file GICHelper.h.

◆ operator<<() [8/13]

llvm::raw_ostream & polly::operator<< ( llvm::raw_ostream &  OS,
__isl_keep isl_space Space 
)
inline

Definition at line 292 of file GICHelper.h.

◆ operator<<() [9/13]

llvm::raw_ostream & polly::operator<< ( llvm::raw_ostream &  OS,
__isl_keep isl_union_map Map 
)
inline

Definition at line 244 of file GICHelper.h.

◆ operator<<() [10/13]

llvm::raw_ostream & polly::operator<< ( llvm::raw_ostream &  OS,
__isl_keep isl_union_pw_multi_aff UPMA 
)
inline

Definition at line 280 of file GICHelper.h.

◆ operator<<() [11/13]

raw_ostream & polly::operator<< ( raw_ostream &  OS,
const Scop scop 
)

Print Scop scop to raw_ostream OS.

Definition at line 2536 of file ScopInfo.cpp.

References PollyPrintInstructions(), and scop.

◆ operator<<() [12/13]

raw_ostream & polly::operator<< ( raw_ostream &  OS,
const ScopStmt S 
)

Print ScopStmt S to raw_ostream OS.

Definition at line 1348 of file ScopInfo.cpp.

References PollyPrintInstructions().

◆ operator<<() [13/13]

raw_ostream & polly::operator<< ( raw_ostream &  OS,
MemoryAccess::ReductionType  RT 
)

◆ operator==()

static bool polly::operator== ( VirtualInstruction  LHS,
VirtualInstruction  RHS 
)
inlinestatic

◆ Optimizer()

static cl::opt< OptimizerChoice > polly::Optimizer ( "polly-optimizer"  ,
cl::desc("Select the scheduling optimizer")  ,
cl::values(clEnumValN(OPTIMIZER_NONE, "none", "No optimizer"), clEnumValN(OPTIMIZER_ISL, "isl", "The isl scheduling optimizer"))  ,
cl::Hidden  ,
cl::init(OPTIMIZER_ISL ,
cl::cat(PollyCategory  
)
static

◆ parseFunctionPipeline()

static bool polly::parseFunctionPipeline ( StringRef  Name,
FunctionPassManager &  FPM,
ArrayRef< PassBuilder::PipelineElement >  Pipeline 
)
static

Definition at line 467 of file RegisterPasses.cpp.

Referenced by registerPollyPasses().

◆ parseScopPass()

static bool polly::parseScopPass ( StringRef  Name,
ScopPassManager SPM,
PassInstrumentationCallbacks *  PIC 
)
static

Definition at line 489 of file RegisterPasses.cpp.

Referenced by parseScopPipeline(), and parseTopLevelPipeline().

◆ parseScopPipeline()

static bool polly::parseScopPipeline ( StringRef  Name,
FunctionPassManager &  FPM,
PassInstrumentationCallbacks *  PIC,
ArrayRef< PassBuilder::PipelineElement >  Pipeline 
)
static

Definition at line 508 of file RegisterPasses.cpp.

References createFunctionToScopPassAdaptor(), and parseScopPass().

Referenced by registerPollyPasses().

◆ parseTopLevelPipeline()

static bool polly::parseTopLevelPipeline ( llvm::ModulePassManager &  MPM,
PassInstrumentationCallbacks *  PIC,
ArrayRef< PassBuilder::PipelineElement >  Pipeline 
)
static

◆ PassPosition()

static cl::opt< PassPositionChoice > polly::PassPosition ( "polly-position"  ,
cl::desc("Where to run polly in the pass pipeline")  ,
cl::values(clEnumValN(POSITION_EARLY, "early", "Before everything"), clEnumValN(POSITION_BEFORE_VECTORIZER, "before-vectorizer", "Right before the vectorizer"))  ,
cl::Hidden  ,
cl::init(POSITION_BEFORE_VECTORIZER ,
cl::cat(PollyCategory  
)
static

Referenced by registerPollyPasses().

◆ PollyDetectOnly()

static cl::opt< bool > polly::PollyDetectOnly ( "polly-only-scop-detection"  ,
cl::desc("Only run scop detection, but no other optimizations")  ,
cl::cat(PollyCategory  
)
static

◆ PollyEnabled()

static cl::opt< bool > polly::PollyEnabled ( "polly"  ,
cl::desc("Enable the polly optimizer (with -O1, -O2 or -O3)")  ,
cl::cat(PollyCategory  
)
static

◆ PollyOnlyPrinter()

static cl::opt< bool > polly::PollyOnlyPrinter ( "polly-dot-only"  ,
cl::desc("Enable the Polly DOT printer in -O3 (no BB content)")  ,
cl::Hidden   
)
static

◆ PollyOnlyViewer()

static cl::opt< bool > polly::PollyOnlyViewer ( "polly-show-only"  ,
cl::desc("Highlight the code regions that will be optimized in " "a (CFG only BBs)")  ,
cl::init(false)  ,
cl::cat(PollyCategory  
)
static

◆ PollyPrinter()

static cl::opt< bool > polly::PollyPrinter ( "polly-dot"  ,
cl::desc("Enable the Polly DOT printer in -O3")  ,
cl::Hidden  ,
cl::value_desc("Run the Polly DOT printer at -O3")  ,
cl::init(false)  ,
cl::cat(PollyCategory  
)
static

◆ PollyViewer()

static cl::opt< bool > polly::PollyViewer ( "polly-show"  ,
cl::desc("Highlight the code regions that will be optimized in a " "(CFG BBs and LLVM-IR instructions)")  ,
cl::cat(PollyCategory  
)
static

◆ rangeIslSize()

llvm::iota_range< unsigned > polly::rangeIslSize ( unsigned  Begin,
isl::size  End 
)

Check that End is valid and return an iterator from Begin to End.

Use case example: for (unsigned i : rangeIslSize(0, Map.domain_tuple_dim())) // do stuff

Definition at line 597 of file ISLTools.cpp.

References unsignedFromIslSize().

Referenced by polly::ScopBuilder::addUserContext(), createNextIterationMap(), fixSetToZero(), polly::BlockGenerator::generateBeginStmtTrace(), polly::ZoneAlgorithm::getDefToTarget(), polly::Dependences::isValidSchedule(), partitionSetParts(), and polly::RecursiveScheduleTreeVisitor< Derived, RetTy, Args >::visitNode().

◆ recordAssumption()

void polly::recordAssumption ( RecordedAssumptionsTy RecordedAssumptions,
AssumptionKind  Kind,
isl::set  Set,
llvm::DebugLoc  Loc,
AssumptionSign  Sign,
llvm::BasicBlock *  BB = nullptr,
bool  RTC = true 
)

Record an assumption for later addition to the assumed context.

This function will add the assumption to the RecordedAssumptions. This collection will be added (

See also
addAssumption) to the assumed context once all paramaters are known and the context is fully built.
Parameters
RecordedAssumptioncontainer which keeps all recorded assumptions.
KindThe assumption kind describing the underlying cause.
SetThe relations between parameters that are assumed to hold.
LocThe location in the source that caused this assumption.
SignEnum to indicate if the assumptions in Set are positive (needed/assumptions) or negative (invalid/restrictions).
BBThe block in which this assumption was taken. If it is set, the domain of that block will be used to simplify the actual assumption in Set once it is added. This is useful if the assumption was created prior to the domain.
RTCDoes the assumption require a runtime check?

Referenced by polly::ScopBuilder::addLoopBoundsToHeaderDomain(), polly::ScopBuilder::assumeNoOutOfBounds(), polly::SCEVAffinator::checkForWrapping(), polly::ScopBuilder::propagateInvalidStmtDomains(), polly::SCEVAffinator::takeNonNegativeAssumption(), and polly::SCEVAffinator::visitTruncateExpr().

◆ registerCanonicalicationPasses()

void polly::registerCanonicalicationPasses ( llvm::legacy::PassManagerBase &  PM)

Schedule a set of canonicalization passes to prepare for Polly.

The set of optimization passes was partially taken/copied from the set of default optimization passes in LLVM. It is used to bring the code into a canonical form that simplifies the analysis and optimization passes of Polly. The set of optimization passes scheduled here is probably not yet optimal. TODO: Optimize the set of canonicalization passes.

Definition at line 42 of file Canonicalization.cpp.

References PollyInliner().

◆ registerFunctionAnalyses()

static void polly::registerFunctionAnalyses ( FunctionAnalysisManager &  FAM,
PassInstrumentationCallbacks *  PIC 
)
static

Definition at line 455 of file RegisterPasses.cpp.

References createScopAnalyses().

Referenced by registerPollyPasses().

◆ registerPollyPasses() [1/2]

void polly::registerPollyPasses ( llvm::PassBuilder &  PB)

Referenced by getPollyPluginInfo().

◆ registerPollyPasses() [2/2]

void polly::registerPollyPasses ( PassBuilder &  PB)

Register Polly to be available as an optimizer.

We can currently run Polly at two different points int the pass manager. a) very early, b) right before the vectorizer.

The default is currently a), to register Polly such that it runs as early as possible. This has several implications:

1) We need to schedule more canonicalization passes

As nothing is run before Polly, it is necessary to run a set of preparing transformations before Polly to canonicalize the LLVM-IR and to allow Polly to detect and understand the code.

2) We get the full -O3 optimization sequence after Polly

The LLVM-IR that is generated by Polly has been optimized on a high level, but it may be rather inefficient on the lower/scalar level. By scheduling Polly before all other passes, we have the full sequence of -O3 optimizations behind us, such that inefficiencies on the low level can be optimized away.

We are currently evaluating the benefit or running Polly at b). b) is nice as everything is fully inlined and canonicalized, but we need to be able to handle LICMed code to make it useful.

Definition at line 593 of file RegisterPasses.cpp.

References buildEarlyPollyPipeline(), buildLatePollyPipeline(), parseFunctionPipeline(), parseScopPipeline(), parseTopLevelPipeline(), PassPosition(), POSITION_BEFORE_VECTORIZER, POSITION_EARLY, and registerFunctionAnalyses().

◆ reverseDomain() [1/2]

isl::union_map polly::reverseDomain ( const isl::union_map UMap)

◆ reverseDomain() [2/2]

isl::map polly::reverseDomain ( isl::map  Map)

Reverse the nested map tuple in Map's domain.

Parameters
Map{ [Space1[] -> Space2[]] -> Space3[] }
Returns
{ [Space2[] -> Space1[]] -> Space3[] }

Definition at line 199 of file ISLTools.cpp.

References isl::map::apply_domain(), isl::space::domain(), isl::map::get_space(), isl::space::range(), and isl::space::unwrap().

Referenced by computeArrayUnused(), and reverseDomain().

◆ shiftDim() [1/4]

isl::map polly::shiftDim ( isl::map  Map,
isl::dim  Dim,
int  Pos,
int  Amount 
)

Add a constant to one dimension of a map.

Parameters
MapThe map to shift a dimension in.
TypeA tuple of Map which contains the dimension to shift.
PosThe dimension to shift. If negative, the dimensions are counted from the end instead from the beginning. Eg. -1 is the last dimension in the tuple.
AmountThe offset to add to the specified dimension.
Returns
The modified map.

Definition at line 237 of file ISLTools.cpp.

References isl::map::apply_domain(), isl::map::apply_range(), assert, isl::map::dim(), isl::space::domain(), isl::map::from_multi_aff(), isl::map::get_space(), isl::in, isl::space::map_from_domain_and_range(), isl::out, isl::space::range(), and unsignedFromIslSize().

◆ shiftDim() [2/4]

isl::set polly::shiftDim ( isl::set  Set,
int  Pos,
int  Amount 
)

Add a constant to one dimension of a set.

Parameters
MapThe set to shift a dimension in.
PosThe dimension to shift. If negative, the dimensions are counted from the end instead from the beginning. E.g. -1 is the last dimension in the tuple.
AmountThe offset to add to the specified dimension.
Returns
The modified set.

Definition at line 216 of file ISLTools.cpp.

References isl::set::apply(), assert, isl::map::from_multi_aff(), isl::set::get_space(), isl::space::map_from_domain_and_range(), isl::set::tuple_dim(), and unsignedFromIslSize().

Referenced by convertZoneToTimepoints(), and shiftDim().

◆ shiftDim() [3/4]

isl::union_map polly::shiftDim ( isl::union_map  UMap,
isl::dim  Dim,
int  Pos,
int  Amount 
)

Add a constant to one dimension of a each map in a union map.

Parameters
UMapThe maps to shift a dimension in.
TypeThe tuple which contains the dimension to shift.
PosThe dimension to shift. If negative, the dimensions are counted from the ends of each map of union instead from their beginning. E.g. -1 is the last dimension of any map.
AmountThe offset to add to the specified dimension.
Returns
The union of all modified maps.

Definition at line 278 of file ISLTools.cpp.

References isl::union_map::ctx(), isl::union_map::empty(), isl::union_map::get_map_list(), shiftDim(), and isl::union_map::unite().

◆ shiftDim() [4/4]

isl::union_set polly::shiftDim ( isl::union_set  USet,
int  Pos,
int  Amount 
)

◆ shouldEnablePollyForDiagnostic()

static bool polly::shouldEnablePollyForDiagnostic ( )
static

◆ shouldEnablePollyForOptimization()

static bool polly::shouldEnablePollyForOptimization ( )
static

Definition at line 255 of file RegisterPasses.cpp.

References PollyEnabled().

Referenced by buildEarlyPollyPipeline(), and buildLatePollyPipeline().

◆ simplify() [1/4]

void polly::simplify ( isl::map Map)

Simplify a map inplace.

Definition at line 301 of file ISLTools.cpp.

References isl::map::coalesce(), isl::map::copy(), isl::map::detect_equalities(), isl_map_compute_divs(), and isl::manage().

◆ simplify() [2/4]

void polly::simplify ( isl::set Set)

Simplify a set inplace.

Definition at line 289 of file ISLTools.cpp.

References isl::set::coalesce(), isl::set::copy(), isl::set::detect_equalities(), isl_set_compute_divs(), and isl::manage().

Referenced by buildMinMaxAccess().

◆ simplify() [3/4]

void polly::simplify ( isl::union_map UMap)

◆ simplify() [4/4]

void polly::simplify ( isl::union_set USet)

◆ simplifyRegion()

void polly::simplifyRegion ( llvm::Region *  R,
llvm::DominatorTree *  DT,
llvm::LoopInfo *  LI,
llvm::RegionInfo *  RI 
)

Simplify the region to have a single unconditional entry edge and a single exit edge.

Although this function allows DT and RI to be null, regions only work properly if the DominatorTree (for Region::contains) and RegionInfo are kept up-to-date.

Parameters
RThe region to be simplified
DTDominatorTree to be updated.
LILoopInfo to be updated.
RIRegionInfo to be updated.

Referenced by generateCode().

◆ singleton() [1/2]

isl::map polly::singleton ( isl::union_map  UMap,
isl::space  ExpectedSpace 
)

If by construction a union map is known to contain only a single map, return it.

This function combines isl_map_from_union_map() and isl_union_map_extract_map(). isl_map_from_union_map() fails if the map is empty because it does not know which space it would be in. isl_union_map_extract_map() on the other hand does not check whether there is (at most) one isl_map in the union, i.e. how it has been constructed is probably wrong.

Definition at line 135 of file ISLTools.cpp.

References assert, isl::map::empty(), isl::map::from_union_map(), isl::union_map::get(), isl::map::get_space(), isl::space::has_equal_tuples(), isl::map::is_null(), isl::union_map::is_null(), and isl_union_map_n_map().

Referenced by polly::ZoneAlgorithm::computePerPHI(), computeScalarReachingDefinition(), polly::ZoneAlgorithm::getScatterFor(), and polly::Dependences::isValidSchedule().

◆ singleton() [2/2]

isl::set polly::singleton ( isl::union_set  USet,
isl::space  ExpectedSpace 
)

If by construction an isl_union_set is known to contain only a single isl_set, return it.

This function combines isl_set_from_union_set() and isl_union_set_extract_set(). isl_map_from_union_set() fails if the set is empty because it does not know which space it would be in. isl_union_set_extract_set() on the other hand does not check whether there is (at most) one isl_set in the union, i.e. how it has been constructed is probably wrong.

Definition at line 149 of file ISLTools.cpp.

References assert, isl::set::empty(), isl::union_set::get(), isl::set::get_space(), isl::space::has_equal_tuples(), isl::set::is_null(), isl::union_set::is_null(), and isl_union_set_n_set().

◆ splitEntryBlockForAlloca() [1/2]

void polly::splitEntryBlockForAlloca ( llvm::BasicBlock *  EntryBlock,
llvm::DominatorTree *  DT,
llvm::LoopInfo *  LI,
llvm::RegionInfo *  RI 
)

Split the entry block of a function to store the newly inserted allocations outside of all Scops.

Parameters
DTDominatorTree to be updated.
LILoopInfo to be updated.
RIRegionInfo to be updated.

◆ splitEntryBlockForAlloca() [2/2]

void polly::splitEntryBlockForAlloca ( llvm::BasicBlock *  EntryBlock,
llvm::Pass *  P 
)

Split the entry block of a function to store the newly inserted allocations outside of all Scops.

Parameters
EntryBlockThe entry block of the current function.
PThe pass that currently running.

Referenced by polly::CodePreparationPass::run().

◆ subtractParams() [1/2]

isl::map polly::subtractParams ( isl::map  Map,
isl::set  Params 
)

Subtract the parameter space Params from Map.

This is akin to isl::map::intersect_params.

Example: subtractParams( { [i] -> [i] }, [x] -> { : x < 0 } ) = [x] -> { [i] -> [i] : x >= 0 }

Parameters
MapRemove the conditions of Params from this map.
ParamsParameter set to subtract.
Themap with the parameter conditions removed.

Definition at line 540 of file ISLTools.cpp.

References isl::map::get_space(), isl::map::intersect_params(), isl::map::subtract(), and isl::map::universe().

◆ subtractParams() [2/2]

isl::set polly::subtractParams ( isl::set  Set,
isl::set  Params 
)

Subtract the parameter space Params from Set.

Definition at line 546 of file ISLTools.cpp.

References isl::set::get_space(), isl::set::intersect_params(), isl::set::subtract(), and isl::set::universe().

◆ tileNode()

isl::schedule_node polly::tileNode ( isl::schedule_node  Node,
const char *  Identifier,
llvm::ArrayRef< int >  TileSizes,
int  DefaultTileSize 
)

Tile a schedule node.

Parameters
NodeThe node to tile.
IdentifierAn name that identifies this kind of tiling and that is used to mark the tiled loops in the generated AST.
TileSizesA vector of tile sizes that should be used for tiling.
DefaultTileSizeA default tile size that is used for dimensions that are not covered by the TileSizes vector.

◆ tryForwardThroughPHI()

const llvm::SCEV * polly::tryForwardThroughPHI ( const llvm::SCEV *  Expr,
llvm::Region &  R,
llvm::ScalarEvolution &  SE,
ScopDetection SD 
)

Try to look through PHI nodes, where some incoming edges come from error blocks.

In case a PHI node follows an error block we can assume that the incoming value can only come from the node that is not an error block. As a result, conditions that seemed non-affine before are now in fact affine.

Referenced by polly::ScopBuilder::buildConditionSets(), and polly::ScopDetection::isValidBranch().

◆ tryOptimizeMatMulPattern()

isl::schedule_node polly::tryOptimizeMatMulPattern ( isl::schedule_node  Node,
const llvm::TargetTransformInfo *  TTI,
const Dependences D 
)

Apply the BLIS matmul optimization pattern if possible.

Make the loops containing the matrix multiplication be the innermost loops and apply the BLIS matmul optimization pattern. BLIS implements gemm as three nested loops around a macro-kernel, plus two packing routines. The macro-kernel is implemented in terms of two additional loops around a micro-kernel. The micro-kernel is a loop around a rank-1 (i.e., outer product) update.

For a detailed description please see [1].

The order of the loops defines the data reused in the BLIS implementation of gemm ([1]). In particular, elements of the matrix B, the second operand of matrix multiplication, are reused between iterations of the innermost loop. To keep the reused data in cache, only elements of matrix A, the first operand of matrix multiplication, should be evicted during an iteration of the innermost loop. To provide such a cache replacement policy, elements of the matrix A can, in particular, be loaded first and, consequently, be least-recently-used.

In our case matrices are stored in row-major order instead of column-major order used in the BLIS implementation ([1]). It affects only on the form of the BLIS micro kernel and the computation of its parameters. In particular, reused elements of the matrix B are successively multiplied by specific elements of the matrix A.

Refs.: [1] - Analytical Modeling is Enough for High Performance BLIS Tze Meng Low, Francisco D Igual, Tyler M Smith, Enrique S Quintana-Orti Technical Report, 2014 http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf

See also
ScheduleTreeOptimizer::createMicroKernel
ScheduleTreeOptimizer::createMacroKernel
getMicroKernelParams
getMacroKernelParams

TODO: Implement the packing transformation.

Parameters
NodeThe node that contains a band to be optimized. The node is required to successfully pass ScheduleTreeOptimizer::isMatrMultPattern.
TTITarget Transform Info.
DThe dependencies.
Returns
The transformed schedule or nullptr if the optimization cannot be applied.

Definition at line 1824 of file MatmulOptimizer.cpp.

References PMBasedMMMOpts(), PMBasedTCOpts(), and POLLY_DEBUG.

◆ valFromAPInt()

isl::val polly::valFromAPInt ( isl_ctx Ctx,
const llvm::APInt  Int,
bool  IsSigned 
)
inline

Translate an llvm::APInt to an isl::val.

Translate the bitsequence without sign information as provided by APInt into a signed isl::val type. Depending on the value of IsSigned Int is interpreted as unsigned value or as signed value in two's complement representation.

Input IsSigned Output

0        0           ->    0
1        0           ->    1

00 0 -> 0 01 0 -> 1 10 0 -> 2 11 0 -> 3

0 1 -> 0 1 1 -> -1 00 1 -> 0 01 1 -> 1 10 1 -> -2 11 1 -> -1

Parameters
CtxThe isl_ctx to create the isl::val in.
IntThe integer value to translate.
IsSignedIf the APInt should be interpreted as signed or unsigned value.
Returns
The isl::val corresponding to Int.

Definition at line 86 of file GICHelper.h.

References Ctx, isl_valFromAPInt(), and isl::manage().

Referenced by addRangeBoundsToSet(), and polly::MemoryAccess::wrapConstantDimensions().

◆ Vectorizer()

static cl::opt< VectorizerChoice, true > polly::Vectorizer ( "polly-vectorizer"  ,
cl::desc("Select the vectorization strategy")  ,
cl::values(clEnumValN(VECTORIZER_NONE, "none", "No Vectorization"), clEnumValN(VECTORIZER_STRIPMINE, "stripmine", "Strip-mine outer loops for the loop-vectorizer to trigger"))  ,
cl::location(PollyVectorizerChoice ,
cl::init(VECTORIZER_NONE ,
cl::cat(PollyCategory  
)
static

Variable Documentation

◆ CodePreparationID

char & polly::CodePreparationID = CodePreparation::ID
extern

Definition at line 112 of file CodePreparation.cpp.

◆ MaxDisjunctsInDomain

unsigned const polly::MaxDisjunctsInDomain = 20
extern

◆ ModelReadOnlyScalars

bool polly::ModelReadOnlyScalars
extern

Command line switch whether to model read-only accesses.

Definition at line 71 of file ScopBuilder.cpp.

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

◆ PerfMonitoring

bool polly::PerfMonitoring
extern

Definition at line 57 of file CodeGeneration.cpp.

Referenced by generateCode().

◆ PollyAllowFullFunction

bool polly::PollyAllowFullFunction
extern

Definition at line 131 of file ScopDetection.cpp.

Referenced by polly::ScopDetection::isValidRegion().

◆ PollyAllowUnsignedOperations

bool polly::PollyAllowUnsignedOperations
extern

◆ PollyChunkSize

int polly::PollyChunkSize
extern

◆ PollyDelinearize

bool polly::PollyDelinearize = false
extern

◆ PollyInvariantLoadHoisting

bool polly::PollyInvariantLoadHoisting
extern

◆ PollyNumThreads

int polly::PollyNumThreads
extern

◆ PollyProcessUnprofitable

bool polly::PollyProcessUnprofitable
extern

◆ PollyScheduling

OMPGeneralSchedulingType polly::PollyScheduling
extern

◆ PollySkipFnAttr

StringRef polly::PollySkipFnAttr = "polly.skip.fn"
extern

A function attribute which will cause Polly to skip the function.

Definition at line 236 of file ScopDetection.cpp.

Referenced by polly::ParallelLoopGenerator::createSubFnDefinition(), polly::ScopDetection::isValidFunction(), and polly::ScopDetection::markFunctionAsInvalid().

◆ PollyTrackFailures

bool polly::PollyTrackFailures = false
extern

◆ PollyUseRuntimeAliasChecks

bool polly::PollyUseRuntimeAliasChecks
extern

◆ PollyVectorizerChoice

VectorizerChoice polly::PollyVectorizerChoice

Definition at line 99 of file RegisterPasses.cpp.

Referenced by polly::IslAst::init().

◆ UseInstructionNames

bool polly::UseInstructionNames
extern