diff options
| -rw-r--r-- | polly/include/polly/ScopInfo.h | 268 | ||||
| -rw-r--r-- | polly/include/polly/TempScopInfo.h | 305 | ||||
| -rw-r--r-- | polly/lib/Analysis/ScopInfo.cpp | 395 | ||||
| -rw-r--r-- | polly/lib/Analysis/TempScopInfo.cpp | 431 | ||||
| -rw-r--r-- | polly/lib/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | polly/lib/CodeGen/CodeGeneration.cpp | 1 | ||||
| -rw-r--r-- | polly/lib/CodeGen/IslNodeBuilder.cpp | 1 | ||||
| -rw-r--r-- | polly/lib/Support/RegisterPasses.cpp | 1 |
8 files changed, 662 insertions, 741 deletions
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h index 4106ea620e5..a122d98c9db 100644 --- a/polly/include/polly/ScopInfo.h +++ b/polly/include/polly/ScopInfo.h @@ -67,6 +67,36 @@ class TempScop; class Comparison; class SCEVAffFunc; +class Comparison { + const SCEV *LHS; + const SCEV *RHS; + + ICmpInst::Predicate Pred; + +public: + Comparison(const SCEV *LHS, const SCEV *RHS, ICmpInst::Predicate Pred) + : LHS(LHS), RHS(RHS), Pred(Pred) {} + + const SCEV *getLHS() const { return LHS; } + const SCEV *getRHS() const { return RHS; } + + ICmpInst::Predicate getPred() const { return Pred; } + void print(raw_ostream &OS) const; +}; + +//===---------------------------------------------------------------------===// + +/// 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. +typedef std::map<const Loop *, const SCEV *> LoopBoundMapType; + +typedef std::vector<std::pair<IRAccess, Instruction *>> AccFuncSetType; +typedef std::map<const BasicBlock *, AccFuncSetType> AccFuncMapType; + /// @brief A class to store information about arrays in the SCoP. /// /// Objects are accessible via the ScoP, MemoryAccess or the id associated with @@ -184,6 +214,78 @@ private: bool IsPHI; }; +//===---------------------------------------------------------------------===// +/// @brief A memory access described by a SCEV expression and the access type. +class IRAccess { +public: + Value *BaseAddress; + Value *AccessValue; + + const SCEV *Offset; + + // The type of the scev affine function + enum TypeKind { + READ = 0x1, + MUST_WRITE = 0x2, + MAY_WRITE = 0x3, + }; + +private: + unsigned ElemBytes; + TypeKind Type; + bool IsAffine; + + /// @brief Is this IRAccess modeling special PHI node accesses? + bool IsPHI; + +public: + SmallVector<const SCEV *, 4> Subscripts, Sizes; + + /// @brief Create a new IRAccess + /// + /// @param IsPHI Are we modeling special PHI node accesses? + explicit IRAccess(TypeKind Type, Value *BaseAddress, const SCEV *Offset, + unsigned elemBytes, bool Affine, Value *AccessValue, + bool IsPHI = false) + : BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset), + ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(IsPHI) {} + + explicit IRAccess(TypeKind Type, Value *BaseAddress, const SCEV *Offset, + unsigned elemBytes, bool Affine, + SmallVector<const SCEV *, 4> Subscripts, + SmallVector<const SCEV *, 4> Sizes, Value *AccessValue) + : BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset), + ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(false), + Subscripts(Subscripts), Sizes(Sizes) {} + + enum TypeKind getType() const { return Type; } + + Value *getBase() const { return BaseAddress; } + + Value *getAccessValue() const { return AccessValue; } + + const SCEV *getOffset() const { return Offset; } + + unsigned getElemSizeInBytes() const { return ElemBytes; } + + bool isAffine() const { return IsAffine; } + + bool isRead() const { return Type == READ; } + + bool isWrite() const { return Type == MUST_WRITE; } + + void setMayWrite() { Type = MAY_WRITE; } + + bool isMayWrite() const { return Type == MAY_WRITE; } + + bool isScalar() const { return Subscripts.size() == 0; } + + // @brief Is this IRAccess modeling special PHI node accesses? + bool isPHI() const { return IsPHI; } + + void print(raw_ostream &OS) const; +}; + /// @brief Represent memory accesses in statements. class MemoryAccess { public: @@ -1275,6 +1377,171 @@ static inline raw_ostream &operator<<(raw_ostream &O, const Scop &scop) { return O; } +//===---------------------------------------------------------------------===// +/// @brief Scop represent with llvm objects. +/// +/// A helper class for remembering the parameter number and the max depth in +/// this Scop, and others context. +class TempScop { + // The Region. + Region &R; + + // Access function of bbs. + AccFuncMapType &AccFuncMap; + + friend class TempScopInfo; + + explicit TempScop(Region &r, AccFuncMapType &accFuncMap) + : R(r), AccFuncMap(accFuncMap) {} + +public: + ~TempScop(); + + /// @brief Get the maximum Region contained by this Scop. + /// + /// @return The maximum Region contained by this Scop. + Region &getMaxRegion() const { return R; } + + /// @brief Get all access functions in a BasicBlock + /// + /// @param BB The BasicBlock that containing the access functions. + /// + /// @return All access functions in BB + /// + AccFuncSetType *getAccessFunctions(const BasicBlock *BB) { + AccFuncMapType::iterator at = AccFuncMap.find(BB); + return at != AccFuncMap.end() ? &(at->second) : 0; + } + //@} + + /// @brief Print the Temporary Scop information. + /// + /// @param OS The output stream the access functions is printed to. + /// @param SE The ScalarEvolution that help printing Temporary Scop + /// information. + /// @param LI The LoopInfo that help printing the access functions. + void print(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI) const; + + /// @brief Print the access functions and loop bounds in this Scop. + /// + /// @param OS The output stream the access functions is printed to. + /// @param SE The ScalarEvolution that help printing the access functions. + /// @param LI The LoopInfo that help printing the access functions. + void printDetail(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI, + const Region *Reg, unsigned ind) const; +}; + +typedef std::map<const Region *, TempScop *> TempScopMapType; +//===----------------------------------------------------------------------===// +/// @brief The Function Pass to extract temporary information for Static control +/// part in llvm function. +/// +class TempScopInfo : public RegionPass { + //===-------------------------------------------------------------------===// + TempScopInfo(const TempScopInfo &) = delete; + const TempScopInfo &operator=(const TempScopInfo &) = delete; + + // The ScalarEvolution to help building Scop. + ScalarEvolution *SE; + + // LoopInfo for information about loops + LoopInfo *LI; + + // The AliasAnalysis to build AliasSetTracker. + AliasAnalysis *AA; + + // Valid Regions for Scop + ScopDetection *SD; + + // Target data for element size computing. + const DataLayout *TD; + + // Access function of statements (currently BasicBlocks) . + AccFuncMapType AccFuncMap; + + // Pre-created zero for the scalar accesses, with it we do not need create a + // zero scev every time when we need it. + const SCEV *ZeroOffset; + + // The TempScop for this region. + TempScop *TempScopOfRegion; + + // Clear the context. + void clear(); + + // Build the temprory information of Region R, where R must be a valid part + // of Scop. + TempScop *buildTempScop(Region &R); + + /// @brief Build an instance of IRAccess from the Load/Store instruction. + /// + /// @param Inst The Load/Store instruction that access the memory + /// @param L The parent loop of the instruction + /// @param R The region on which we are going to build a TempScop + /// @param BoxedLoops The set of loops that are overapproximated in @p R. + /// + /// @return The IRAccess to describe the access function of the + /// instruction. + IRAccess buildIRAccess(Instruction *Inst, Loop *L, Region *R, + const ScopDetection::BoxedLoopsSetTy *BoxedLoops); + + /// @brief Analyze and extract the cross-BB scalar dependences (or, + /// dataflow dependencies) of an instruction. + /// + /// @param Inst The instruction to be analyzed + /// @param R The SCoP region + /// @param NonAffineSubRegion The non affine sub-region @p Inst is in. + /// + /// @return True if the Instruction is used in other BB and a scalar write + /// Access is required. + bool buildScalarDependences(Instruction *Inst, Region *R, + Region *NonAffineSubRegio); + + /// @brief Create IRAccesses for the given PHI node in the given region. + /// + /// @param PHI The PHI node to be handled + /// @param R The SCoP region + /// @param Functions The access functions of the current BB + /// @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 &R, AccFuncSetType &Functions, + Region *NonAffineSubRegion, bool IsExitBlock = false); + + /// @brief Build the access functions for the subregion @p SR. + /// + /// @param R The SCoP region. + /// @param SR A subregion of @p R. + void buildAccessFunctions(Region &R, Region &SR); + + /// @brief Build the access functions for the basic block @p BB + /// + /// @param R The SCoP region. + /// @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(Region &R, BasicBlock &BB, + Region *NonAffineSubRegion = nullptr, + bool IsExitBlock = false); + +public: + static char ID; + explicit TempScopInfo() : RegionPass(ID), TempScopOfRegion(nullptr) {} + ~TempScopInfo(); + + /// @brief Get the temporay Scop information in LLVM IR for this region. + /// + /// @return The Scop information in LLVM IR represent. + TempScop *getTempScop() const; + + /// @name RegionPass interface + //@{ + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual void releaseMemory() { clear(); } + virtual bool runOnRegion(Region *R, RGPassManager &RGM); + virtual void print(raw_ostream &OS, const Module *) const; + //@} +}; + ///===---------------------------------------------------------------------===// /// @brief Build the Polly IR (Scop and ScopStmt) on a Region. /// @@ -1326,6 +1593,7 @@ public: namespace llvm { class PassRegistry; +void initializeTempScopInfoPass(llvm::PassRegistry &); void initializeScopInfoPass(llvm::PassRegistry &); } diff --git a/polly/include/polly/TempScopInfo.h b/polly/include/polly/TempScopInfo.h deleted file mode 100644 index 3eddc8dafe7..00000000000 --- a/polly/include/polly/TempScopInfo.h +++ /dev/null @@ -1,305 +0,0 @@ -//===-------- polly/TempScopInfo.h - Extract TempScops ----------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Collect information about the control flow regions detected by the Scop -// detection, such that this information can be translated info its polyhedral -// representation. -// -//===----------------------------------------------------------------------===// - -#ifndef POLLY_TEMP_SCOP_EXTRACTION_H -#define POLLY_TEMP_SCOP_EXTRACTION_H - -#include "polly/ScopDetection.h" -#include "llvm/Analysis/RegionPass.h" -#include "llvm/IR/Instructions.h" - -namespace llvm { -class DataLayout; -} - -using namespace llvm; - -namespace polly { - -//===---------------------------------------------------------------------===// -/// @brief A memory access described by a SCEV expression and the access type. -class IRAccess { -public: - Value *BaseAddress; - Value *AccessValue; - - const SCEV *Offset; - - // The type of the scev affine function - enum TypeKind { - READ = 0x1, - MUST_WRITE = 0x2, - MAY_WRITE = 0x3, - }; - -private: - unsigned ElemBytes; - TypeKind Type; - bool IsAffine; - - /// @brief Is this IRAccess modeling special PHI node accesses? - bool IsPHI; - -public: - SmallVector<const SCEV *, 4> Subscripts, Sizes; - - /// @brief Create a new IRAccess - /// - /// @param IsPHI Are we modeling special PHI node accesses? - explicit IRAccess(TypeKind Type, Value *BaseAddress, const SCEV *Offset, - unsigned elemBytes, bool Affine, Value *AccessValue, - bool IsPHI = false) - : BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset), - ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(IsPHI) {} - - explicit IRAccess(TypeKind Type, Value *BaseAddress, const SCEV *Offset, - unsigned elemBytes, bool Affine, - SmallVector<const SCEV *, 4> Subscripts, - SmallVector<const SCEV *, 4> Sizes, Value *AccessValue) - : BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset), - ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(false), - Subscripts(Subscripts), Sizes(Sizes) {} - - enum TypeKind getType() const { return Type; } - - Value *getBase() const { return BaseAddress; } - - Value *getAccessValue() const { return AccessValue; } - - const SCEV *getOffset() const { return Offset; } - - unsigned getElemSizeInBytes() const { return ElemBytes; } - - bool isAffine() const { return IsAffine; } - - bool isRead() const { return Type == READ; } - - bool isWrite() const { return Type == MUST_WRITE; } - - void setMayWrite() { Type = MAY_WRITE; } - - bool isMayWrite() const { return Type == MAY_WRITE; } - - bool isScalar() const { return Subscripts.size() == 0; } - - // @brief Is this IRAccess modeling special PHI node accesses? - bool isPHI() const { return IsPHI; } - - void print(raw_ostream &OS) const; -}; - -class Comparison { - const SCEV *LHS; - const SCEV *RHS; - - ICmpInst::Predicate Pred; - -public: - Comparison(const SCEV *LHS, const SCEV *RHS, ICmpInst::Predicate Pred) - : LHS(LHS), RHS(RHS), Pred(Pred) {} - - const SCEV *getLHS() const { return LHS; } - const SCEV *getRHS() const { return RHS; } - - ICmpInst::Predicate getPred() const { return Pred; } - void print(raw_ostream &OS) const; -}; - -//===---------------------------------------------------------------------===// - -/// 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. -typedef std::map<const Loop *, const SCEV *> LoopBoundMapType; - -typedef std::vector<std::pair<IRAccess, Instruction *>> AccFuncSetType; -typedef std::map<const BasicBlock *, AccFuncSetType> AccFuncMapType; - -//===---------------------------------------------------------------------===// -/// @brief Scop represent with llvm objects. -/// -/// A helper class for remembering the parameter number and the max depth in -/// this Scop, and others context. -class TempScop { - // The Region. - Region &R; - - // Access function of bbs. - AccFuncMapType &AccFuncMap; - - friend class TempScopInfo; - - explicit TempScop(Region &r, AccFuncMapType &accFuncMap) - : R(r), AccFuncMap(accFuncMap) {} - -public: - ~TempScop(); - - /// @brief Get the maximum Region contained by this Scop. - /// - /// @return The maximum Region contained by this Scop. - Region &getMaxRegion() const { return R; } - - /// @brief Get all access functions in a BasicBlock - /// - /// @param BB The BasicBlock that containing the access functions. - /// - /// @return All access functions in BB - /// - AccFuncSetType *getAccessFunctions(const BasicBlock *BB) { - AccFuncMapType::iterator at = AccFuncMap.find(BB); - return at != AccFuncMap.end() ? &(at->second) : 0; - } - //@} - - /// @brief Print the Temporary Scop information. - /// - /// @param OS The output stream the access functions is printed to. - /// @param SE The ScalarEvolution that help printing Temporary Scop - /// information. - /// @param LI The LoopInfo that help printing the access functions. - void print(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI) const; - - /// @brief Print the access functions and loop bounds in this Scop. - /// - /// @param OS The output stream the access functions is printed to. - /// @param SE The ScalarEvolution that help printing the access functions. - /// @param LI The LoopInfo that help printing the access functions. - void printDetail(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI, - const Region *Reg, unsigned ind) const; -}; - -typedef std::map<const Region *, TempScop *> TempScopMapType; -//===----------------------------------------------------------------------===// -/// @brief The Function Pass to extract temporary information for Static control -/// part in llvm function. -/// -class TempScopInfo : public RegionPass { - //===-------------------------------------------------------------------===// - TempScopInfo(const TempScopInfo &) = delete; - const TempScopInfo &operator=(const TempScopInfo &) = delete; - - // The ScalarEvolution to help building Scop. - ScalarEvolution *SE; - - // LoopInfo for information about loops - LoopInfo *LI; - - // The AliasAnalysis to build AliasSetTracker. - AliasAnalysis *AA; - - // Valid Regions for Scop - ScopDetection *SD; - - // Target data for element size computing. - const DataLayout *TD; - - // Access function of statements (currently BasicBlocks) . - AccFuncMapType AccFuncMap; - - // Pre-created zero for the scalar accesses, with it we do not need create a - // zero scev every time when we need it. - const SCEV *ZeroOffset; - - // The TempScop for this region. - TempScop *TempScopOfRegion; - - // Clear the context. - void clear(); - - // Build the temprory information of Region R, where R must be a valid part - // of Scop. - TempScop *buildTempScop(Region &R); - - /// @brief Build an instance of IRAccess from the Load/Store instruction. - /// - /// @param Inst The Load/Store instruction that access the memory - /// @param L The parent loop of the instruction - /// @param R The region on which we are going to build a TempScop - /// @param BoxedLoops The set of loops that are overapproximated in @p R. - /// - /// @return The IRAccess to describe the access function of the - /// instruction. - IRAccess buildIRAccess(Instruction *Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops); - - /// @brief Analyze and extract the cross-BB scalar dependences (or, - /// dataflow dependencies) of an instruction. - /// - /// @param Inst The instruction to be analyzed - /// @param R The SCoP region - /// @param NonAffineSubRegion The non affine sub-region @p Inst is in. - /// - /// @return True if the Instruction is used in other BB and a scalar write - /// Access is required. - bool buildScalarDependences(Instruction *Inst, Region *R, - Region *NonAffineSubRegio); - - /// @brief Create IRAccesses for the given PHI node in the given region. - /// - /// @param PHI The PHI node to be handled - /// @param R The SCoP region - /// @param Functions The access functions of the current BB - /// @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 &R, AccFuncSetType &Functions, - Region *NonAffineSubRegion, bool IsExitBlock = false); - - /// @brief Build the access functions for the subregion @p SR. - /// - /// @param R The SCoP region. - /// @param SR A subregion of @p R. - void buildAccessFunctions(Region &R, Region &SR); - - /// @brief Build the access functions for the basic block @p BB - /// - /// @param R The SCoP region. - /// @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(Region &R, BasicBlock &BB, - Region *NonAffineSubRegion = nullptr, - bool IsExitBlock = false); - -public: - static char ID; - explicit TempScopInfo() : RegionPass(ID), TempScopOfRegion(nullptr) {} - ~TempScopInfo(); - - /// @brief Get the temporay Scop information in LLVM IR for this region. - /// - /// @return The Scop information in LLVM IR represent. - TempScop *getTempScop() const; - - /// @name RegionPass interface - //@{ - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory() { clear(); } - virtual bool runOnRegion(Region *R, RGPassManager &RGM); - virtual void print(raw_ostream &OS, const Module *) const; - //@} -}; - -} // end namespace polly - -namespace llvm { -class PassRegistry; -void initializeTempScopInfoPass(llvm::PassRegistry &); -} - -#endif diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index be2e2977e22..f3104a992ed 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -23,7 +23,7 @@ #include "polly/Support/GICHelper.h" #include "polly/Support/SCEVValidator.h" #include "polly/Support/ScopHelper.h" -#include "polly/TempScopInfo.h" +#include "polly/CodeGen/BlockGenerators.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" @@ -59,6 +59,11 @@ using namespace polly; STATISTIC(ScopFound, "Number of valid Scops"); STATISTIC(RichScopFound, "Number of Scops containing a loop"); +static cl::opt<bool> ModelReadOnlyScalars( + "polly-analyze-read-only-scalars", + cl::desc("Model read-only scalar values in the scop description"), + cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory)); + // Multiplicative reductions can be disabled separately as these kind of // operations can overflow easily. Additive reductions and bit operations // are in contrast pretty stable. @@ -86,6 +91,13 @@ static cl::opt<bool> DetectReductions("polly-detect-reductions", cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory)); +//===----------------------------------------------------------------------===// +/// Helper Classes + +void Comparison::print(raw_ostream &OS) const { + // Not yet implemented. +} + // Create a sequence of two schedules. Either argument may be null and is // interpreted as the empty schedule. Can also return null if both schedules are // empty. @@ -213,6 +225,17 @@ const ScopArrayInfo *ScopArrayInfo::getFromId(isl_id *Id) { return SAI; } +void IRAccess::print(raw_ostream &OS) const { + if (isRead()) + OS << "Read "; + else { + if (isMayWrite()) + OS << "May"; + OS << "Write "; + } + OS << BaseAddress->getName() << '[' << *Offset << "]\n"; +} + const std::string MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) { switch (RT) { @@ -2328,6 +2351,36 @@ ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const { return StmtMapIt->second; } +//===----------------------------------------------------------------------===// +// TempScop implementation +TempScop::~TempScop() {} + +void TempScop::print(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI) const { + OS << "Scop: " << R.getNameStr() << "\n"; + + printDetail(OS, SE, LI, &R, 0); +} + +void TempScop::printDetail(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI, + const Region *CurR, unsigned ind) const { + // FIXME: Print other details rather than memory accesses. + for (const auto &CurBlock : CurR->blocks()) { + AccFuncMapType::const_iterator AccSetIt = AccFuncMap.find(CurBlock); + + // Ignore trivial blocks that do not contain any memory access. + if (AccSetIt == AccFuncMap.end()) + continue; + + OS.indent(ind) << "BB: " << CurBlock->getName() << '\n'; + typedef AccFuncSetType::const_iterator access_iterator; + const AccFuncSetType &AccFuncs = AccSetIt->second; + + for (access_iterator AI = AccFuncs.begin(), AE = AccFuncs.end(); AI != AE; + ++AI) + AI->first.print(OS.indent(ind + 2)); + } +} + int Scop::getRelativeLoopDepth(const Loop *L) const { Loop *OuterLoop = L ? R.outermostLoopInRegion(const_cast<Loop *>(L)) : nullptr; @@ -2336,6 +2389,346 @@ int Scop::getRelativeLoopDepth(const Loop *L) const { return L->getLoopDepth() - OuterLoop->getLoopDepth(); } +void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R, + AccFuncSetType &Functions, + Region *NonAffineSubRegion, + bool IsExitBlock) { + + // PHI nodes that are in the exit block of the region, hence if IsExitBlock is + // true, are not modeled as ordinary PHI nodes as they are not part of the + // region. However, we model the operands in the predecessor blocks that are + // part of the region as regular scalar accesses. + + // If we can synthesize a PHI we can skip it, however only if it is in + // the region. If it is not it can only be in the exit block of the region. + // In this case we model the operands but not the PHI itself. + if (!IsExitBlock && canSynthesize(PHI, LI, SE, &R)) + return; + + // PHI nodes are modeled as if they had been demoted prior to the SCoP + // detection. Hence, the PHI is a load of a new memory location in which the + // incoming value was written at the end of the incoming basic block. + bool OnlyNonAffineSubRegionOperands = true; + for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) { + Value *Op = PHI->getIncomingValue(u); + BasicBlock *OpBB = PHI->getIncomingBlock(u); + + // Do not build scalar dependences inside a non-affine subregion. + if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB)) + continue; + + OnlyNonAffineSubRegionOperands = false; + + if (!R.contains(OpBB)) + continue; + + Instruction *OpI = dyn_cast<Instruction>(Op); + if (OpI) { + BasicBlock *OpIBB = OpI->getParent(); + // As we pretend there is a use (or more precise a write) of OpI in OpBB + // we have to insert a scalar dependence from the definition of OpI to + // OpBB if the definition is not in OpBB. + if (OpIBB != OpBB) { + IRAccess ScalarRead(IRAccess::READ, OpI, ZeroOffset, 1, true, OpI); + AccFuncMap[OpBB].push_back(std::make_pair(ScalarRead, PHI)); + IRAccess ScalarWrite(IRAccess::MUST_WRITE, OpI, ZeroOffset, 1, true, + OpI); + AccFuncMap[OpIBB].push_back(std::make_pair(ScalarWrite, OpI)); + } + } + + // Always use the terminator of the incoming basic block as the access + // instruction. + OpI = OpBB->getTerminator(); + + IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true, Op, + /* IsPHI */ !IsExitBlock); + AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI)); + } + + if (!OnlyNonAffineSubRegionOperands) { + IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true, PHI, + /* IsPHI */ !IsExitBlock); + Functions.push_back(std::make_pair(ScalarAccess, PHI)); + } +} + +bool TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R, + Region *NonAffineSubRegion) { + bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R); + if (isIgnoredIntrinsic(Inst)) + return false; + + bool AnyCrossStmtUse = false; + BasicBlock *ParentBB = Inst->getParent(); + + for (User *U : Inst->users()) { + Instruction *UI = dyn_cast<Instruction>(U); + + // Ignore the strange user + if (UI == 0) + continue; + + BasicBlock *UseParent = UI->getParent(); + + // Ignore the users in the same BB (statement) + if (UseParent == ParentBB) + continue; + + // Do not build scalar dependences inside a non-affine subregion. + if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent)) + continue; + + // Check whether or not the use is in the SCoP. + if (!R->contains(UseParent)) { + AnyCrossStmtUse = true; + continue; + } + + // If the instruction can be synthesized and the user is in the region + // we do not need to add scalar dependences. + if (canSynthesizeInst) + continue; + + // No need to translate these scalar dependences into polyhedral form, + // because synthesizable scalars can be generated by the code generator. + if (canSynthesize(UI, LI, SE, R)) + continue; + + // Skip PHI nodes in the region as they handle their operands on their own. + if (isa<PHINode>(UI)) + continue; + + // Now U is used in another statement. + AnyCrossStmtUse = true; + + // Do not build a read access that is not in the current SCoP + // Use the def instruction as base address of the IRAccess, so that it will + // become the name of the scalar access in the polyhedral form. + IRAccess ScalarAccess(IRAccess::READ, Inst, ZeroOffset, 1, true, Inst); + AccFuncMap[UseParent].push_back(std::make_pair(ScalarAccess, UI)); + } + + if (ModelReadOnlyScalars) { + for (Value *Op : Inst->operands()) { + if (canSynthesize(Op, LI, SE, R)) + continue; + + if (Instruction *OpInst = dyn_cast<Instruction>(Op)) + if (R->contains(OpInst)) + continue; + + if (isa<Constant>(Op)) + continue; + + IRAccess ScalarAccess(IRAccess::READ, Op, ZeroOffset, 1, true, Op); + AccFuncMap[Inst->getParent()].push_back( + std::make_pair(ScalarAccess, Inst)); + } + } + + return AnyCrossStmtUse; +} + +extern MapInsnToMemAcc InsnToMemAcc; + +IRAccess +TempScopInfo::buildIRAccess(Instruction *Inst, Loop *L, Region *R, + const ScopDetection::BoxedLoopsSetTy *BoxedLoops) { + unsigned Size; + Type *SizeType; + Value *Val; + enum IRAccess::TypeKind Type; + + if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) { + SizeType = Load->getType(); + Size = TD->getTypeStoreSize(SizeType); + Type = IRAccess::READ; + Val = Load; + } else { + StoreInst *Store = cast<StoreInst>(Inst); + SizeType = Store->getValueOperand()->getType(); + Size = TD->getTypeStoreSize(SizeType); + Type = IRAccess::MUST_WRITE; + Val = Store->getValueOperand(); + } + + const SCEV *AccessFunction = SE->getSCEVAtScope(getPointerOperand(*Inst), L); + const SCEVUnknown *BasePointer = + dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction)); + + assert(BasePointer && "Could not find base pointer"); + AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer); + + auto AccItr = InsnToMemAcc.find(Inst); + if (PollyDelinearize && AccItr != InsnToMemAcc.end()) + return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, true, + AccItr->second.DelinearizedSubscripts, + AccItr->second.Shape->DelinearizedSizes, Val); + + // Check if the access depends on a loop contained in a non-affine subregion. + bool isVariantInNonAffineLoop = false; + if (BoxedLoops) { + SetVector<const Loop *> Loops; + findLoops(AccessFunction, Loops); + for (const Loop *L : Loops) + if (BoxedLoops->count(L)) + isVariantInNonAffineLoop = true; + } + + bool IsAffine = !isVariantInNonAffineLoop && + isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue()); + + SmallVector<const SCEV *, 4> Subscripts, Sizes; + Subscripts.push_back(AccessFunction); + Sizes.push_back(SE->getConstant(ZeroOffset->getType(), Size)); + + if (!IsAffine && Type == IRAccess::MUST_WRITE) + Type = IRAccess::MAY_WRITE; + + return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, IsAffine, + Subscripts, Sizes, Val); +} + +void TempScopInfo::buildAccessFunctions(Region &R, Region &SR) { + + if (SD->isNonAffineSubRegion(&SR, &R)) { + for (BasicBlock *BB : SR.blocks()) + buildAccessFunctions(R, *BB, &SR); + return; + } + + for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I) + if (I->isSubRegion()) + buildAccessFunctions(R, *I->getNodeAs<Region>()); + else + buildAccessFunctions(R, *I->getNodeAs<BasicBlock>()); +} + +void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB, + Region *NonAffineSubRegion, + bool IsExitBlock) { + AccFuncSetType Functions; + Loop *L = LI->getLoopFor(&BB); + + // The set of loops contained in non-affine subregions that are part of R. + const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R); + + for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) { + Instruction *Inst = I; + + PHINode *PHI = dyn_cast<PHINode>(Inst); + if (PHI) + buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion, IsExitBlock); + + // For the exit block we stop modeling after the last PHI node. + if (!PHI && IsExitBlock) + break; + + if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst)) + Functions.push_back( + std::make_pair(buildIRAccess(Inst, L, &R, BoxedLoops), Inst)); + + if (isIgnoredIntrinsic(Inst)) + continue; + + if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) { + // If the Instruction is used outside the statement, we need to build the + // write access. + if (!isa<StoreInst>(Inst)) { + IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true, + Inst); + Functions.push_back(std::make_pair(ScalarAccess, Inst)); + } + } + } + + if (Functions.empty()) + return; + + AccFuncSetType &Accs = AccFuncMap[&BB]; + Accs.insert(Accs.end(), Functions.begin(), Functions.end()); +} + +TempScop *TempScopInfo::buildTempScop(Region &R) { + TempScop *TScop = new TempScop(R, AccFuncMap); + + buildAccessFunctions(R, R); + + // In case the region does not have an exiting block we will later (during + // code generation) split the exit block. This will move potential PHI nodes + // from the current exit block into the new region exiting block. Hence, PHI + // nodes that are at this point not part of the region will be. + // To handle these PHI nodes later we will now model their operands as scalar + // accesses. Note that we do not model anything in the exit block if we have + // an exiting block in the region, as there will not be any splitting later. + if (!R.getExitingBlock()) + buildAccessFunctions(R, *R.getExit(), nullptr, /* IsExitBlock */ true); + + return TScop; +} + +TempScop *TempScopInfo::getTempScop() const { return TempScopOfRegion; } + +void TempScopInfo::print(raw_ostream &OS, const Module *) const { + if (TempScopOfRegion) + TempScopOfRegion->print(OS, SE, LI); +} + +bool TempScopInfo::runOnRegion(Region *R, RGPassManager &RGM) { + SD = &getAnalysis<ScopDetection>(); + + if (!SD->isMaxRegionInScop(*R)) + return false; + + Function *F = R->getEntry()->getParent(); + SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); + LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); + AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); + TD = &F->getParent()->getDataLayout(); + ZeroOffset = SE->getConstant(TD->getIntPtrType(F->getContext()), 0); + + assert(!TempScopOfRegion && "Build the TempScop only once"); + TempScopOfRegion = buildTempScop(*R); + + return false; +} + +void TempScopInfo::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequiredTransitive<LoopInfoWrapperPass>(); + AU.addRequiredTransitive<ScalarEvolutionWrapperPass>(); + AU.addRequiredTransitive<ScopDetection>(); + AU.addRequiredID(IndependentBlocksID); + AU.addRequired<AAResultsWrapperPass>(); + AU.setPreservesAll(); +} + +TempScopInfo::~TempScopInfo() { clear(); } + +void TempScopInfo::clear() { + AccFuncMap.clear(); + if (TempScopOfRegion) + delete TempScopOfRegion; + TempScopOfRegion = nullptr; +} + +//===----------------------------------------------------------------------===// +// TempScop information extraction pass implement +char TempScopInfo::ID = 0; + +Pass *polly::createTempScopInfoPass() { return new TempScopInfo(); } + +INITIALIZE_PASS_BEGIN(TempScopInfo, "polly-analyze-ir", + "Polly - Analyse the LLVM-IR in the detected regions", + false, false); +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass); +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); +INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); +INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); +INITIALIZE_PASS_END(TempScopInfo, "polly-analyze-ir", + "Polly - Analyse the LLVM-IR in the detected regions", + false, false) + //===----------------------------------------------------------------------===// ScopInfo::ScopInfo() : RegionPass(ID), scop(0) { ctx = isl_ctx_alloc(); diff --git a/polly/lib/Analysis/TempScopInfo.cpp b/polly/lib/Analysis/TempScopInfo.cpp deleted file mode 100644 index c3afa017723..00000000000 --- a/polly/lib/Analysis/TempScopInfo.cpp +++ /dev/null @@ -1,431 +0,0 @@ -//===---------- TempScopInfo.cpp - Extract TempScops ---------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Collect information about the control flow regions detected by the Scop -// detection, such that this information can be translated info its polyhedral -// representation. -// -//===----------------------------------------------------------------------===// - -#include "polly/TempScopInfo.h" -#include "polly/Options.h" -#include "polly/CodeGen/BlockGenerators.h" -#include "polly/LinkAllPasses.h" -#include "polly/ScopDetection.h" -#include "polly/Support/GICHelper.h" -#include "polly/Support/SCEVValidator.h" -#include "polly/Support/ScopHelper.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/Analysis/PostDominators.h" -#include "llvm/Analysis/RegionIterator.h" -#include "llvm/Analysis/ScalarEvolution.h" -#include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/IR/DataLayout.h" -#include "llvm/IR/Module.h" -#include "llvm/Support/Debug.h" - -using namespace llvm; -using namespace polly; - -static cl::opt<bool> ModelReadOnlyScalars( - "polly-analyze-read-only-scalars", - cl::desc("Model read-only scalar values in the scop description"), - cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory)); - -#define DEBUG_TYPE "polly-analyze-ir" - -//===----------------------------------------------------------------------===// -/// Helper Classes - -void IRAccess::print(raw_ostream &OS) const { - if (isRead()) - OS << "Read "; - else { - if (isMayWrite()) - OS << "May"; - OS << "Write "; - } - OS << BaseAddress->getName() << '[' << *Offset << "]\n"; -} - -void Comparison::print(raw_ostream &OS) const { - // Not yet implemented. -} - -//===----------------------------------------------------------------------===// -// TempScop implementation -TempScop::~TempScop() {} - -void TempScop::print(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI) const { - OS << "Scop: " << R.getNameStr() << "\n"; - - printDetail(OS, SE, LI, &R, 0); -} - -void TempScop::printDetail(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI, - const Region *CurR, unsigned ind) const { - // FIXME: Print other details rather than memory accesses. - for (const auto &CurBlock : CurR->blocks()) { - AccFuncMapType::const_iterator AccSetIt = AccFuncMap.find(CurBlock); - - // Ignore trivial blocks that do not contain any memory access. - if (AccSetIt == AccFuncMap.end()) - continue; - - OS.indent(ind) << "BB: " << CurBlock->getName() << '\n'; - typedef AccFuncSetType::const_iterator access_iterator; - const AccFuncSetType &AccFuncs = AccSetIt->second; - - for (access_iterator AI = AccFuncs.begin(), AE = AccFuncs.end(); AI != AE; - ++AI) - AI->first.print(OS.indent(ind + 2)); - } -} - -void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R, - AccFuncSetType &Functions, - Region *NonAffineSubRegion, - bool IsExitBlock) { - - // PHI nodes that are in the exit block of the region, hence if IsExitBlock is - // true, are not modeled as ordinary PHI nodes as they are not part of the - // region. However, we model the operands in the predecessor blocks that are - // part of the region as regular scalar accesses. - - // If we can synthesize a PHI we can skip it, however only if it is in - // the region. If it is not it can only be in the exit block of the region. - // In this case we model the operands but not the PHI itself. - if (!IsExitBlock && canSynthesize(PHI, LI, SE, &R)) - return; - - // PHI nodes are modeled as if they had been demoted prior to the SCoP - // detection. Hence, the PHI is a load of a new memory location in which the - // incoming value was written at the end of the incoming basic block. - bool OnlyNonAffineSubRegionOperands = true; - for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) { - Value *Op = PHI->getIncomingValue(u); - BasicBlock *OpBB = PHI->getIncomingBlock(u); - - // Do not build scalar dependences inside a non-affine subregion. - if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB)) - continue; - - OnlyNonAffineSubRegionOperands = false; - - if (!R.contains(OpBB)) - continue; - - Instruction *OpI = dyn_cast<Instruction>(Op); - if (OpI) { - BasicBlock *OpIBB = OpI->getParent(); - // As we pretend there is a use (or more precise a write) of OpI in OpBB - // we have to insert a scalar dependence from the definition of OpI to - // OpBB if the definition is not in OpBB. - if (OpIBB != OpBB) { - IRAccess ScalarRead(IRAccess::READ, OpI, ZeroOffset, 1, true, OpI); - AccFuncMap[OpBB].push_back(std::make_pair(ScalarRead, PHI)); - IRAccess ScalarWrite(IRAccess::MUST_WRITE, OpI, ZeroOffset, 1, true, - OpI); - AccFuncMap[OpIBB].push_back(std::make_pair(ScalarWrite, OpI)); - } - } - - // Always use the terminator of the incoming basic block as the access - // instruction. - OpI = OpBB->getTerminator(); - - IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true, Op, - /* IsPHI */ !IsExitBlock); - AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI)); - } - - if (!OnlyNonAffineSubRegionOperands) { - IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true, PHI, - /* IsPHI */ !IsExitBlock); - Functions.push_back(std::make_pair(ScalarAccess, PHI)); - } -} - -bool TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R, - Region *NonAffineSubRegion) { - bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R); - if (isIgnoredIntrinsic(Inst)) - return false; - - bool AnyCrossStmtUse = false; - BasicBlock *ParentBB = Inst->getParent(); - - for (User *U : Inst->users()) { - Instruction *UI = dyn_cast<Instruction>(U); - - // Ignore the strange user - if (UI == 0) - continue; - - BasicBlock *UseParent = UI->getParent(); - - // Ignore the users in the same BB (statement) - if (UseParent == ParentBB) - continue; - - // Do not build scalar dependences inside a non-affine subregion. - if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent)) - continue; - - // Check whether or not the use is in the SCoP. - if (!R->contains(UseParent)) { - AnyCrossStmtUse = true; - continue; - } - - // If the instruction can be synthesized and the user is in the region - // we do not need to add scalar dependences. - if (canSynthesizeInst) - continue; - - // No need to translate these scalar dependences into polyhedral form, - // because synthesizable scalars can be generated by the code generator. - if (canSynthesize(UI, LI, SE, R)) - continue; - - // Skip PHI nodes in the region as they handle their operands on their own. - if (isa<PHINode>(UI)) - continue; - - // Now U is used in another statement. - AnyCrossStmtUse = true; - - // Do not build a read access that is not in the current SCoP - // Use the def instruction as base address of the IRAccess, so that it will - // become the name of the scalar access in the polyhedral form. - IRAccess ScalarAccess(IRAccess::READ, Inst, ZeroOffset, 1, true, Inst); - AccFuncMap[UseParent].push_back(std::make_pair(ScalarAccess, UI)); - } - - if (ModelReadOnlyScalars) { - for (Value *Op : Inst->operands()) { - if (canSynthesize(Op, LI, SE, R)) - continue; - - if (Instruction *OpInst = dyn_cast<Instruction>(Op)) - if (R->contains(OpInst)) - continue; - - if (isa<Constant>(Op)) - continue; - - IRAccess ScalarAccess(IRAccess::READ, Op, ZeroOffset, 1, true, Op); - AccFuncMap[Inst->getParent()].push_back( - std::make_pair(ScalarAccess, Inst)); - } - } - - return AnyCrossStmtUse; -} - -extern MapInsnToMemAcc InsnToMemAcc; - -IRAccess -TempScopInfo::buildIRAccess(Instruction *Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops) { - unsigned Size; - Type *SizeType; - Value *Val; - enum IRAccess::TypeKind Type; - - if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) { - SizeType = Load->getType(); - Size = TD->getTypeStoreSize(SizeType); - Type = IRAccess::READ; - Val = Load; - } else { - StoreInst *Store = cast<StoreInst>(Inst); - SizeType = Store->getValueOperand()->getType(); - Size = TD->getTypeStoreSize(SizeType); - Type = IRAccess::MUST_WRITE; - Val = Store->getValueOperand(); - } - - const SCEV *AccessFunction = SE->getSCEVAtScope(getPointerOperand(*Inst), L); - const SCEVUnknown *BasePointer = - dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction)); - - assert(BasePointer && "Could not find base pointer"); - AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer); - - auto AccItr = InsnToMemAcc.find(Inst); - if (PollyDelinearize && AccItr != InsnToMemAcc.end()) - return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, true, - AccItr->second.DelinearizedSubscripts, - AccItr->second.Shape->DelinearizedSizes, Val); - - // Check if the access depends on a loop contained in a non-affine subregion. - bool isVariantInNonAffineLoop = false; - if (BoxedLoops) { - SetVector<const Loop *> Loops; - findLoops(AccessFunction, Loops); - for (const Loop *L : Loops) - if (BoxedLoops->count(L)) - isVariantInNonAffineLoop = true; - } - - bool IsAffine = !isVariantInNonAffineLoop && - isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue()); - - SmallVector<const SCEV *, 4> Subscripts, Sizes; - Subscripts.push_back(AccessFunction); - Sizes.push_back(SE->getConstant(ZeroOffset->getType(), Size)); - - if (!IsAffine && Type == IRAccess::MUST_WRITE) - Type = IRAccess::MAY_WRITE; - - return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, IsAffine, - Subscripts, Sizes, Val); -} - -void TempScopInfo::buildAccessFunctions(Region &R, Region &SR) { - - if (SD->isNonAffineSubRegion(&SR, &R)) { - for (BasicBlock *BB : SR.blocks()) - buildAccessFunctions(R, *BB, &SR); - return; - } - - for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I) - if (I->isSubRegion()) - buildAccessFunctions(R, *I->getNodeAs<Region>()); - else - buildAccessFunctions(R, *I->getNodeAs<BasicBlock>()); -} - -void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB, - Region *NonAffineSubRegion, - bool IsExitBlock) { - AccFuncSetType Functions; - Loop *L = LI->getLoopFor(&BB); - - // The set of loops contained in non-affine subregions that are part of R. - const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R); - - for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) { - Instruction *Inst = I; - - PHINode *PHI = dyn_cast<PHINode>(Inst); - if (PHI) - buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion, IsExitBlock); - - // For the exit block we stop modeling after the last PHI node. - if (!PHI && IsExitBlock) - break; - - if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst)) - Functions.push_back( - std::make_pair(buildIRAccess(Inst, L, &R, BoxedLoops), Inst)); - - if (isIgnoredIntrinsic(Inst)) - continue; - - if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) { - // If the Instruction is used outside the statement, we need to build the - // write access. - if (!isa<StoreInst>(Inst)) { - IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true, - Inst); - Functions.push_back(std::make_pair(ScalarAccess, Inst)); - } - } - } - - if (Functions.empty()) - return; - - AccFuncSetType &Accs = AccFuncMap[&BB]; - Accs.insert(Accs.end(), Functions.begin(), Functions.end()); -} - -TempScop *TempScopInfo::buildTempScop(Region &R) { - TempScop *TScop = new TempScop(R, AccFuncMap); - - buildAccessFunctions(R, R); - - // In case the region does not have an exiting block we will later (during - // code generation) split the exit block. This will move potential PHI nodes - // from the current exit block into the new region exiting block. Hence, PHI - // nodes that are at this point not part of the region will be. - // To handle these PHI nodes later we will now model their operands as scalar - // accesses. Note that we do not model anything in the exit block if we have - // an exiting block in the region, as there will not be any splitting later. - if (!R.getExitingBlock()) - buildAccessFunctions(R, *R.getExit(), nullptr, /* IsExitBlock */ true); - - return TScop; -} - -TempScop *TempScopInfo::getTempScop() const { return TempScopOfRegion; } - -void TempScopInfo::print(raw_ostream &OS, const Module *) const { - if (TempScopOfRegion) - TempScopOfRegion->print(OS, SE, LI); -} - -bool TempScopInfo::runOnRegion(Region *R, RGPassManager &RGM) { - SD = &getAnalysis<ScopDetection>(); - - if (!SD->isMaxRegionInScop(*R)) - return false; - - Function *F = R->getEntry()->getParent(); - SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); - LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); - AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); - TD = &F->getParent()->getDataLayout(); - ZeroOffset = SE->getConstant(TD->getIntPtrType(F->getContext()), 0); - - assert(!TempScopOfRegion && "Build the TempScop only once"); - TempScopOfRegion = buildTempScop(*R); - - return false; -} - -void TempScopInfo::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequiredTransitive<LoopInfoWrapperPass>(); - AU.addRequiredTransitive<ScalarEvolutionWrapperPass>(); - AU.addRequiredTransitive<ScopDetection>(); - AU.addRequiredID(IndependentBlocksID); - AU.addRequired<AAResultsWrapperPass>(); - AU.setPreservesAll(); -} - -TempScopInfo::~TempScopInfo() { clear(); } - -void TempScopInfo::clear() { - AccFuncMap.clear(); - if (TempScopOfRegion) - delete TempScopOfRegion; - TempScopOfRegion = nullptr; -} - -//===----------------------------------------------------------------------===// -// TempScop information extraction pass implement -char TempScopInfo::ID = 0; - -Pass *polly::createTempScopInfoPass() { return new TempScopInfo(); } - -INITIALIZE_PASS_BEGIN(TempScopInfo, "polly-analyze-ir", - "Polly - Analyse the LLVM-IR in the detected regions", - false, false); -INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass); -INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); -INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); -INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); -INITIALIZE_PASS_END(TempScopInfo, "polly-analyze-ir", - "Polly - Analyse the LLVM-IR in the detected regions", - false, false) diff --git a/polly/lib/CMakeLists.txt b/polly/lib/CMakeLists.txt index daa7cd0f1ce..6e63ec7505d 100644 --- a/polly/lib/CMakeLists.txt +++ b/polly/lib/CMakeLists.txt @@ -275,7 +275,6 @@ add_polly_library(Polly Analysis/ScopInfo.cpp Analysis/ScopGraphPrinter.cpp Analysis/ScopPass.cpp - Analysis/TempScopInfo.cpp CodeGen/BlockGenerators.cpp ${ISL_CODEGEN_FILES} CodeGen/LoopGenerators.cpp diff --git a/polly/lib/CodeGen/CodeGeneration.cpp b/polly/lib/CodeGen/CodeGeneration.cpp index b8e40087226..17e23b78296 100644 --- a/polly/lib/CodeGen/CodeGeneration.cpp +++ b/polly/lib/CodeGen/CodeGeneration.cpp @@ -26,7 +26,6 @@ #include "polly/LinkAllPasses.h" #include "polly/ScopInfo.h" #include "polly/Support/ScopHelper.h" -#include "polly/TempScopInfo.h" #include "llvm/IR/Module.h" #include "llvm/IR/Verifier.h" #include "llvm/Support/Debug.h" diff --git a/polly/lib/CodeGen/IslNodeBuilder.cpp b/polly/lib/CodeGen/IslNodeBuilder.cpp index 44569e52793..427f6bc3e49 100644 --- a/polly/lib/CodeGen/IslNodeBuilder.cpp +++ b/polly/lib/CodeGen/IslNodeBuilder.cpp @@ -26,7 +26,6 @@ #include "polly/Support/GICHelper.h" #include "polly/Support/SCEVValidator.h" #include "polly/Support/ScopHelper.h" -#include "polly/TempScopInfo.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/LoopInfo.h" diff --git a/polly/lib/Support/RegisterPasses.cpp b/polly/lib/Support/RegisterPasses.cpp index e249d0f99d5..a27943c7aec 100644 --- a/polly/lib/Support/RegisterPasses.cpp +++ b/polly/lib/Support/RegisterPasses.cpp @@ -27,7 +27,6 @@ #include "polly/Options.h" #include "polly/ScopDetection.h" #include "polly/ScopInfo.h" -#include "polly/TempScopInfo.h" #include "llvm/Analysis/CFGPrinter.h" #include "llvm/IR/LegacyPassManager.h" #include "llvm/Transforms/IPO/PassManagerBuilder.h" |
