diff options
| -rw-r--r-- | polly/include/polly/ScopBuilder.h | 264 | ||||
| -rw-r--r-- | polly/include/polly/ScopInfo.h | 234 | ||||
| -rw-r--r-- | polly/lib/Analysis/ScopBuilder.cpp | 2 | ||||
| -rw-r--r-- | polly/lib/Analysis/ScopInfo.cpp | 1 |
4 files changed, 267 insertions, 234 deletions
diff --git a/polly/include/polly/ScopBuilder.h b/polly/include/polly/ScopBuilder.h new file mode 100644 index 00000000000..28740d73766 --- /dev/null +++ b/polly/include/polly/ScopBuilder.h @@ -0,0 +1,264 @@ +//===- polly/ScopBuilder.h -------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Create a polyhedral description for a static control flow region. +// +// The pass creates a polyhedral description of the Scops detected by the SCoP +// detection derived from their LLVM-IR code. +// +//===----------------------------------------------------------------------===// + +#ifndef POLLY_SCOP_BUILDER_H +#define POLLY_SCOP_BUILDER_H + +#include "polly/ScopInfo.h" + +namespace polly { + +/// @brief Build the Polly IR (Scop and ScopStmt) on a Region. +class ScopBuilder { + //===-------------------------------------------------------------------===// + ScopBuilder(const ScopBuilder &) = delete; + const ScopBuilder &operator=(const ScopBuilder &) = delete; + + /// @brief The AliasAnalysis to build AliasSetTracker. + AliasAnalysis &AA; + + /// @brief Target data for element size computing. + const DataLayout &DL; + + /// @brief DominatorTree to reason about guaranteed execution. + DominatorTree &DT; + + /// @brief LoopInfo for information about loops + LoopInfo &LI; + + /// @biref Valid Regions for Scop + ScopDetection &SD; + + /// @brief The ScalarEvolution to help building Scop. + ScalarEvolution &SE; + + /// @brief Set of instructions that might read any memory location. + SmallVector<Instruction *, 16> GlobalReads; + + /// @brief Set of all accessed array base pointers. + SmallSetVector<Value *, 16> ArrayBasePointers; + + // The Scop + std::unique_ptr<Scop> scop; + + // Build the SCoP for Region @p R. + void buildScop(Region &R, AssumptionCache &AC); + + /// @brief Try to build a multi-dimensional fixed sized MemoryAccess from + /// the Load/Store instruction. + /// + /// @param Inst The Load/Store instruction that access the memory + /// @param L The parent loop of the instruction + /// + /// @returns True if the access could be built, False otherwise. + bool buildAccessMultiDimFixed(MemAccInst Inst, Loop *L); + + /// @brief Try to build a multi-dimensional parameteric sized MemoryAccess + /// from the Load/Store instruction. + /// + /// @param Inst The Load/Store instruction that access the memory + /// @param L The parent loop of the instruction + /// + /// @returns True if the access could be built, False otherwise. + bool buildAccessMultiDimParam(MemAccInst Inst, Loop *L); + + /// @brief Try to build a MemoryAccess for a memory intrinsic. + /// + /// @param Inst The instruction that access the memory + /// @param L The parent loop of the instruction + /// + /// @returns True if the access could be built, False otherwise. + bool buildAccessMemIntrinsic(MemAccInst Inst, Loop *L); + + /// @brief Try to build a MemoryAccess for a call instruction. + /// + /// @param Inst The call instruction that access the memory + /// @param L The parent loop of the instruction + /// + /// @returns True if the access could be built, False otherwise. + bool buildAccessCallInst(MemAccInst Inst, Loop *L); + + /// @brief Build a single-dimensional parameteric sized MemoryAccess + /// from the Load/Store instruction. + /// + /// @param Inst The Load/Store instruction that access the memory + /// @param L The parent loop of the instruction + void buildAccessSingleDim(MemAccInst Inst, Loop *L); + + /// @brief Build an instance of MemoryAccess from the Load/Store instruction. + /// + /// @param Inst The Load/Store instruction that access the memory + /// @param L The parent loop of the instruction + void buildMemoryAccess(MemAccInst Inst, Loop *L); + + /// @brief Analyze and extract the cross-BB scalar dependences (or, + /// dataflow dependencies) of an instruction. + /// + /// @param Inst The instruction to be analyzed. + void buildScalarDependences(Instruction *Inst); + + /// @brief Search for uses of the llvm::Value defined by @p Inst that are not + /// within the SCoP. If there is such use, add a SCALAR WRITE such that + /// it is available after the SCoP as escaping value. + /// + /// @param Inst The instruction to be analyzed. + void buildEscapingDependences(Instruction *Inst); + + /// @brief Create MemoryAccesses for the given PHI node in the given region. + /// + /// @param PHI The PHI node to be handled + /// @param NonAffineSubRegion The non affine sub-region @p PHI is in. + /// @param IsExitBlock Flag to indicate that @p PHI is in the exit BB. + void buildPHIAccesses(PHINode *PHI, Region *NonAffineSubRegion, + bool IsExitBlock = false); + + /// @brief Build the access functions for the subregion @p SR. + /// + /// @param SR A subregion of @p R. + /// @param InsnToMemAcc The Instruction to MemoryAccess mapping. + void buildAccessFunctions(Region &SR); + + /// @brief Create ScopStmt for all BBs and non-affine subregions of @p SR. + /// + /// @param SR A subregion of @p R. + /// + /// Some of the statments might be optimized away later when they do not + /// access any memory and thus have no effect. + void buildStmts(Region &SR); + + /// @brief Build the access functions for the basic block @p BB + /// + /// @param BB A basic block in @p R. + /// @param NonAffineSubRegion The non affine sub-region @p BB is in. + /// @param IsExitBlock Flag to indicate that @p BB is in the exit BB. + void buildAccessFunctions(BasicBlock &BB, + Region *NonAffineSubRegion = nullptr, + bool IsExitBlock = false); + + /// @brief Create a new MemoryAccess object and add it to #AccFuncMap. + /// + /// @param BB The block where the access takes place. + /// @param Inst The instruction doing the access. It is not necessarily + /// inside @p BB. + /// @param AccType The kind of access. + /// @param BaseAddress The accessed array's base address. + /// @param ElemType The type of the accessed array elements. + /// @param Affine Whether all subscripts are affine expressions. + /// @param AccessValue Value read or written. + /// @param Subscripts Access subscripts per dimension. + /// @param Sizes The array diminsion's sizes. + /// @param Kind The kind of memory accessed. + /// + /// @return The created MemoryAccess, or nullptr if the access is not within + /// the SCoP. + MemoryAccess *addMemoryAccess(BasicBlock *BB, Instruction *Inst, + MemoryAccess::AccessType AccType, + Value *BaseAddress, Type *ElemType, bool Affine, + Value *AccessValue, + ArrayRef<const SCEV *> Subscripts, + ArrayRef<const SCEV *> Sizes, + ScopArrayInfo::MemoryKind Kind); + + /// @brief Create a MemoryAccess that represents either a LoadInst or + /// StoreInst. + /// + /// @param MemAccInst The LoadInst or StoreInst. + /// @param AccType The kind of access. + /// @param BaseAddress The accessed array's base address. + /// @param ElemType The type of the accessed array elements. + /// @param IsAffine Whether all subscripts are affine expressions. + /// @param Subscripts Access subscripts per dimension. + /// @param Sizes The array dimension's sizes. + /// @param AccessValue Value read or written. + /// + /// @see ScopArrayInfo::MemoryKind + void addArrayAccess(MemAccInst MemAccInst, MemoryAccess::AccessType AccType, + Value *BaseAddress, Type *ElemType, bool IsAffine, + ArrayRef<const SCEV *> Subscripts, + ArrayRef<const SCEV *> Sizes, Value *AccessValue); + + /// @brief Create a MemoryAccess for writing an llvm::Instruction. + /// + /// The access will be created at the position of @p Inst. + /// + /// @param Inst The instruction to be written. + /// + /// @see ensureValueRead() + /// @see ScopArrayInfo::MemoryKind + void ensureValueWrite(Instruction *Inst); + + /// @brief Ensure an llvm::Value is available in the BB's statement, creating + /// a MemoryAccess for reloading it if necessary. + /// + /// @param V The value expected to be loaded. + /// @param UserBB Where to reload the value. + /// + /// @see ensureValueStore() + /// @see ScopArrayInfo::MemoryKind + void ensureValueRead(Value *V, BasicBlock *UserBB); + + /// @brief Create a write MemoryAccess for the incoming block of a phi node. + /// + /// Each of the incoming blocks write their incoming value to be picked in the + /// phi's block. + /// + /// @param PHI PHINode under consideration. + /// @param IncomingBlock Some predecessor block. + /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock. + /// @param IsExitBlock When true, uses the .s2a alloca instead of the + /// .phiops one. Required for values escaping through a + /// PHINode in the SCoP region's exit block. + /// @see addPHIReadAccess() + /// @see ScopArrayInfo::MemoryKind + void ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock, + Value *IncomingValue, bool IsExitBlock); + + /// @brief Create a MemoryAccess for reading the value of a phi. + /// + /// The modeling assumes that all incoming blocks write their incoming value + /// to the same location. Thus, this access will read the incoming block's + /// value as instructed by this @p PHI. + /// + /// @param PHI PHINode under consideration; the READ access will be added + /// here. + /// + /// @see ensurePHIWrite() + /// @see ScopArrayInfo::MemoryKind + void addPHIReadAccess(PHINode *PHI); + +public: + explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA, + const DataLayout &DL, DominatorTree &DT, LoopInfo &LI, + ScopDetection &SD, ScalarEvolution &SE); + ~ScopBuilder() {} + + /// @brief Try to build the Polly IR of static control part on the current + /// SESE-Region. + /// + /// @return Give up the ownership of the scop object or static control part + /// for the region + std::unique_ptr<Scop> getScop() { return std::move(scop); } +}; + +} // end namespace polly + +namespace llvm { +class PassRegistry; +void initializeScopInfoRegionPassPass(llvm::PassRegistry &); +void initializeScopInfoWrapperPassPass(llvm::PassRegistry &); +} // namespace llvm + +#endif diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h index c4082c657ef..7e3c9891656 100644 --- a/polly/include/polly/ScopInfo.h +++ b/polly/include/polly/ScopInfo.h @@ -1,4 +1,4 @@ -//===------ polly/ScopInfo.h - Create Scops from LLVM IR --------*- C++ -*-===// +//===------ polly/ScopInfo.h -----------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -2253,238 +2253,6 @@ static inline raw_ostream &operator<<(raw_ostream &O, const Scop &scop) { return O; } -/// @brief Build the Polly IR (Scop and ScopStmt) on a Region. -class ScopBuilder { - //===-------------------------------------------------------------------===// - ScopBuilder(const ScopBuilder &) = delete; - const ScopBuilder &operator=(const ScopBuilder &) = delete; - - /// @brief The AliasAnalysis to build AliasSetTracker. - AliasAnalysis &AA; - - /// @brief Target data for element size computing. - const DataLayout &DL; - - /// @brief DominatorTree to reason about guaranteed execution. - DominatorTree &DT; - - /// @brief LoopInfo for information about loops - LoopInfo &LI; - - /// @biref Valid Regions for Scop - ScopDetection &SD; - - /// @brief The ScalarEvolution to help building Scop. - ScalarEvolution &SE; - - /// @brief Set of instructions that might read any memory location. - SmallVector<Instruction *, 16> GlobalReads; - - /// @brief Set of all accessed array base pointers. - SmallSetVector<Value *, 16> ArrayBasePointers; - - // The Scop - std::unique_ptr<Scop> scop; - - // Build the SCoP for Region @p R. - void buildScop(Region &R, AssumptionCache &AC); - - /// @brief Try to build a multi-dimensional fixed sized MemoryAccess from - /// the Load/Store instruction. - /// - /// @param Inst The Load/Store instruction that access the memory - /// @param L The parent loop of the instruction - /// - /// @returns True if the access could be built, False otherwise. - bool buildAccessMultiDimFixed(MemAccInst Inst, Loop *L); - - /// @brief Try to build a multi-dimensional parameteric sized MemoryAccess - /// from the Load/Store instruction. - /// - /// @param Inst The Load/Store instruction that access the memory - /// @param L The parent loop of the instruction - /// - /// @returns True if the access could be built, False otherwise. - bool buildAccessMultiDimParam(MemAccInst Inst, Loop *L); - - /// @brief Try to build a MemoryAccess for a memory intrinsic. - /// - /// @param Inst The instruction that access the memory - /// @param L The parent loop of the instruction - /// - /// @returns True if the access could be built, False otherwise. - bool buildAccessMemIntrinsic(MemAccInst Inst, Loop *L); - - /// @brief Try to build a MemoryAccess for a call instruction. - /// - /// @param Inst The call instruction that access the memory - /// @param L The parent loop of the instruction - /// - /// @returns True if the access could be built, False otherwise. - bool buildAccessCallInst(MemAccInst Inst, Loop *L); - - /// @brief Build a single-dimensional parameteric sized MemoryAccess - /// from the Load/Store instruction. - /// - /// @param Inst The Load/Store instruction that access the memory - /// @param L The parent loop of the instruction - void buildAccessSingleDim(MemAccInst Inst, Loop *L); - - /// @brief Build an instance of MemoryAccess from the Load/Store instruction. - /// - /// @param Inst The Load/Store instruction that access the memory - /// @param L The parent loop of the instruction - void buildMemoryAccess(MemAccInst Inst, Loop *L); - - /// @brief Analyze and extract the cross-BB scalar dependences (or, - /// dataflow dependencies) of an instruction. - /// - /// @param Inst The instruction to be analyzed. - void buildScalarDependences(Instruction *Inst); - - /// @brief Search for uses of the llvm::Value defined by @p Inst that are not - /// within the SCoP. If there is such use, add a SCALAR WRITE such that - /// it is available after the SCoP as escaping value. - /// - /// @param Inst The instruction to be analyzed. - void buildEscapingDependences(Instruction *Inst); - - /// @brief Create MemoryAccesses for the given PHI node in the given region. - /// - /// @param PHI The PHI node to be handled - /// @param NonAffineSubRegion The non affine sub-region @p PHI is in. - /// @param IsExitBlock Flag to indicate that @p PHI is in the exit BB. - void buildPHIAccesses(PHINode *PHI, Region *NonAffineSubRegion, - bool IsExitBlock = false); - - /// @brief Build the access functions for the subregion @p SR. - /// - /// @param SR A subregion of @p R. - /// @param InsnToMemAcc The Instruction to MemoryAccess mapping. - void buildAccessFunctions(Region &SR); - - /// @brief Create ScopStmt for all BBs and non-affine subregions of @p SR. - /// - /// @param SR A subregion of @p R. - /// - /// Some of the statments might be optimized away later when they do not - /// access any memory and thus have no effect. - void buildStmts(Region &SR); - - /// @brief Build the access functions for the basic block @p BB - /// - /// @param BB A basic block in @p R. - /// @param NonAffineSubRegion The non affine sub-region @p BB is in. - /// @param IsExitBlock Flag to indicate that @p BB is in the exit BB. - void buildAccessFunctions(BasicBlock &BB, - Region *NonAffineSubRegion = nullptr, - bool IsExitBlock = false); - - /// @brief Create a new MemoryAccess object and add it to #AccFuncMap. - /// - /// @param BB The block where the access takes place. - /// @param Inst The instruction doing the access. It is not necessarily - /// inside @p BB. - /// @param AccType The kind of access. - /// @param BaseAddress The accessed array's base address. - /// @param ElemType The type of the accessed array elements. - /// @param Affine Whether all subscripts are affine expressions. - /// @param AccessValue Value read or written. - /// @param Subscripts Access subscripts per dimension. - /// @param Sizes The array diminsion's sizes. - /// @param Kind The kind of memory accessed. - /// - /// @return The created MemoryAccess, or nullptr if the access is not within - /// the SCoP. - MemoryAccess *addMemoryAccess(BasicBlock *BB, Instruction *Inst, - MemoryAccess::AccessType AccType, - Value *BaseAddress, Type *ElemType, bool Affine, - Value *AccessValue, - ArrayRef<const SCEV *> Subscripts, - ArrayRef<const SCEV *> Sizes, - ScopArrayInfo::MemoryKind Kind); - - /// @brief Create a MemoryAccess that represents either a LoadInst or - /// StoreInst. - /// - /// @param MemAccInst The LoadInst or StoreInst. - /// @param AccType The kind of access. - /// @param BaseAddress The accessed array's base address. - /// @param ElemType The type of the accessed array elements. - /// @param IsAffine Whether all subscripts are affine expressions. - /// @param Subscripts Access subscripts per dimension. - /// @param Sizes The array dimension's sizes. - /// @param AccessValue Value read or written. - /// - /// @see ScopArrayInfo::MemoryKind - void addArrayAccess(MemAccInst MemAccInst, MemoryAccess::AccessType AccType, - Value *BaseAddress, Type *ElemType, bool IsAffine, - ArrayRef<const SCEV *> Subscripts, - ArrayRef<const SCEV *> Sizes, Value *AccessValue); - - /// @brief Create a MemoryAccess for writing an llvm::Instruction. - /// - /// The access will be created at the position of @p Inst. - /// - /// @param Inst The instruction to be written. - /// - /// @see ensureValueRead() - /// @see ScopArrayInfo::MemoryKind - void ensureValueWrite(Instruction *Inst); - - /// @brief Ensure an llvm::Value is available in the BB's statement, creating - /// a MemoryAccess for reloading it if necessary. - /// - /// @param V The value expected to be loaded. - /// @param UserBB Where to reload the value. - /// - /// @see ensureValueStore() - /// @see ScopArrayInfo::MemoryKind - void ensureValueRead(Value *V, BasicBlock *UserBB); - - /// @brief Create a write MemoryAccess for the incoming block of a phi node. - /// - /// Each of the incoming blocks write their incoming value to be picked in the - /// phi's block. - /// - /// @param PHI PHINode under consideration. - /// @param IncomingBlock Some predecessor block. - /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock. - /// @param IsExitBlock When true, uses the .s2a alloca instead of the - /// .phiops one. Required for values escaping through a - /// PHINode in the SCoP region's exit block. - /// @see addPHIReadAccess() - /// @see ScopArrayInfo::MemoryKind - void ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock, - Value *IncomingValue, bool IsExitBlock); - - /// @brief Create a MemoryAccess for reading the value of a phi. - /// - /// The modeling assumes that all incoming blocks write their incoming value - /// to the same location. Thus, this access will read the incoming block's - /// value as instructed by this @p PHI. - /// - /// @param PHI PHINode under consideration; the READ access will be added - /// here. - /// - /// @see ensurePHIWrite() - /// @see ScopArrayInfo::MemoryKind - void addPHIReadAccess(PHINode *PHI); - -public: - explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA, - const DataLayout &DL, DominatorTree &DT, LoopInfo &LI, - ScopDetection &SD, ScalarEvolution &SE); - ~ScopBuilder() {} - - /// @brief Try to build the Polly IR of static control part on the current - /// SESE-Region. - /// - /// @return Give up the ownership of the scop object or static control part - /// for the region - std::unique_ptr<Scop> getScop() { return std::move(scop); } -}; - /// @brief The legacy pass manager's analysis pass to compute scop information /// for a region. class ScopInfoRegionPass : public RegionPass { diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp index 7875f65df14..8e6949ade5b 100644 --- a/polly/lib/Analysis/ScopBuilder.cpp +++ b/polly/lib/Analysis/ScopBuilder.cpp @@ -14,8 +14,8 @@ // //===----------------------------------------------------------------------===// +#include "polly/ScopBuilder.h" #include "polly/Options.h" -#include "polly/ScopInfo.h" #include "polly/Support/GICHelper.h" #include "polly/Support/SCEVValidator.h" #include "llvm/Analysis/RegionIterator.h" diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index 7c4dc9028c9..b67aa325e05 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -20,6 +20,7 @@ #include "polly/ScopInfo.h" #include "polly/LinkAllPasses.h" #include "polly/Options.h" +#include "polly/ScopBuilder.h" #include "polly/Support/GICHelper.h" #include "polly/Support/SCEVValidator.h" #include "polly/Support/ScopHelper.h" |
