Index: include/polly/CodeGen/BlockGenerators.h =================================================================== --- include/polly/CodeGen/BlockGenerators.h +++ include/polly/CodeGen/BlockGenerators.h @@ -147,8 +147,8 @@ /// the code generation. /// /// @see createScalarInitialization(Scop &) - /// @see createScalarFinalization(Region &) - void finalizeSCoP(Scop &S); + /// @see createScalarFinalization(Region &, ValueMapT &) + void finalizeSCoP(Scop &S, ValueMapT &InterScopMap); /// @brief An empty destructor virtual ~BlockGenerator(){}; @@ -417,7 +417,7 @@ /// If a scalar value was used outside the SCoP we need to promote the value /// stored in the memory cell allocated for that scalar and combine it with /// the original value in the non-optimized SCoP. - void createScalarFinalization(Region &R); + void createScalarFinalization(Region &R, ValueMapT &InterScopMap); /// @brief Try to synthesize a new value /// Index: include/polly/CodeGen/IslAst.h =================================================================== --- include/polly/CodeGen/IslAst.h +++ include/polly/CodeGen/IslAst.h @@ -41,6 +41,7 @@ class Scop; class IslAst; class MemoryAccess; +class DependenceInfo; class IslAstInfo : public ScopPass { public: @@ -80,12 +81,15 @@ }; private: - Scop *S; - IslAst *Ast; + /// @brief Mapping from SCoP to AST representation. + DenseMap AstMap; + + /// @brief The dependence info pass. + DependenceInfo *DI; public: static char ID; - IslAstInfo() : ScopPass(ID), S(nullptr), Ast(nullptr) {} + IslAstInfo() : ScopPass(ID) {} /// @brief Build the AST for the given SCoP @p S. bool runOnScop(Scop &S) override; @@ -96,11 +100,14 @@ /// @brief Release the internal memory. void releaseMemory() override; + /// @brief Initializer called once per function. + void initializeScopPass() override; + /// @brief Print a source code representation of the program. void printScop(llvm::raw_ostream &OS, Scop &S) const override; - /// @brief Return a copy of the AST root node. - __isl_give isl_ast_node *getAst() const; + /// @brief Return a copy of the AST root node for the SCoP @p S. + __isl_give isl_ast_node *getAst(Scop &S) const; /// @brief Get the run condition. /// @@ -108,7 +115,7 @@ /// assumptions that have been taken hold. If the run condition evaluates to /// zero/false some assumptions do not hold and the original code needs to /// be executed. - __isl_give isl_ast_expr *getRunCondition() const; + __isl_give isl_ast_expr *getRunCondition(Scop &S) const; /// @name Extract information attached to an isl ast (for) node. /// Index: include/polly/CodeGen/IslNodeBuilder.h =================================================================== --- include/polly/CodeGen/IslNodeBuilder.h +++ include/polly/CodeGen/IslNodeBuilder.h @@ -31,9 +31,10 @@ public: IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, Pass *P, const DataLayout &DL, LoopInfo &LI, ScalarEvolution &SE, - DominatorTree &DT, Scop &S) + DominatorTree &DT, Scop &S, ValueMapT &InterScopMap) : S(S), Builder(Builder), Annotator(Annotator), ExprBuilder(S, Builder, IDToValue, ValueMap, DL, SE, DT, LI), + ValueMap(InterScopMap), InterScopMap(InterScopMap), BlockGen(Builder, LI, SE, DT, ScalarMap, PHIOpMap, EscapeMap, ValueMap, &ExprBuilder), RegionGen(BlockGen), P(P), DL(DL), LI(LI), SE(SE), DT(DT) {} @@ -49,7 +50,7 @@ /// @brief Finalize code generation for the SCoP @p S. /// /// @see BlockGenerator::finalizeSCoP(Scop &S) - void finalizeSCoP(Scop &S) { BlockGen.finalizeSCoP(S); } + void finalizeSCoP(Scop &S) { BlockGen.finalizeSCoP(S, InterScopMap); } IslExprBuilder &getExprBuilder() { return ExprBuilder; } @@ -65,6 +66,12 @@ IslExprBuilder ExprBuilder; + /// A set of Value -> Value remappings to apply when generating new code. + /// + /// When generating new code for a ScopStmt this map is used to map certain + /// llvm::Values to new llvm::Values. + ValueMapT ValueMap; + /// @brief Maps used by the block and region generator to demote scalars. /// ///@{ @@ -78,6 +85,9 @@ /// @brief See BlockGenerator::EscapeMap. BlockGenerator::EscapeUsersAllocaMapTy EscapeMap; + /// @brief Map to resolve changes to cached SCEVs in other SCoPs. + ValueMapT &InterScopMap; + ///@} /// @brief The generator used to copy a basic block. @@ -112,12 +122,6 @@ /// @param Expr The expression to code generate. llvm::Value *generateSCEV(const SCEV *Expr); - /// A set of Value -> Value remappings to apply when generating new code. - /// - /// When generating new code for a ScopStmt this map is used to map certain - /// llvm::Values to new llvm::Values. - ValueMapT ValueMap; - /// @brief Materialize code for @p Id if it was not done before. void materializeValue(__isl_take isl_id *Id); Index: include/polly/DependenceInfo.h =================================================================== --- include/polly/DependenceInfo.h +++ include/polly/DependenceInfo.h @@ -82,6 +82,14 @@ TYPE_TC_RED = 1 << 4, }; + /// @brief Create an empty dependences struct. + Dependences() + : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr), + TC_RED(nullptr) {} + + /// @brief Destructor that will free internal objects. + ~Dependences() { releaseMemory(); } + /// @brief Get the dependences of type @p Kinds. /// /// @param Kinds This integer defines the different kinds of dependences @@ -138,14 +146,6 @@ friend class DependenceInfo; private: - /// @brief Create an empty dependences struct. - Dependences() - : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr), - TC_RED(nullptr) {} - - /// @brief Destructor that will free internal objects. - ~Dependences() { releaseMemory(); } - /// @brief Calculate and add at the privatization dependences. void addPrivatizationDependences(); @@ -182,29 +182,34 @@ /// @brief Construct a new DependenceInfo pass. DependenceInfo() : ScopPass(ID) {} - /// @brief Return the dependence information for the current SCoP. - const Dependences &getDependences() { return D; } + /// @brief Return the dependence information for the given SCoP @p S + const Dependences &getDependences(Scop &S) const { + assert(DependenceMap.count(&S) && "Dependences for given SCoP not found"); + return DependenceMap.find(&S)->getSecond(); + } - /// @brief Recompute dependences from schedule and memory accesses. - void recomputeDependences(); + /// @brief Return the dependence information for the given SCoP @p S + Dependences &getDependences(Scop &S) { + assert(DependenceMap.count(&S) && "Dependences for given SCoP not found"); + return DependenceMap.find(&S)->getSecond(); + } - /// @brief Compute the dependence information for the SCoP @p S. - bool runOnScop(Scop &S) override; + /// @brief Recompute dependences from schedule and memory accesses. + void recomputeDependences(Scop &S); - /// @brief Print the dependences for the given SCoP to @p OS. - void printScop(raw_ostream &OS, Scop &) const override { D.print(OS); } + /// @brief Initializer called once per function. + void initializeScopPass() override {} - /// @brief Release the internal memory. - void releaseMemory() override { D.releaseMemory(); } + /// @brief Print the dependences for the given SCoP @p S to @p OS. + void printScop(raw_ostream &OS, Scop &S) const override; - /// @brief Register all analyses and transformation required. + bool runOnScop(Scop &S) override; + void releaseMemory() override; void getAnalysisUsage(AnalysisUsage &AU) const override; private: - Scop *S; - - /// @brief Dependences struct for the current SCoP. - Dependences D; + /// @brief Mapping from SCoPs to their dependence structs. + DenseMap DependenceMap; }; } // End polly namespace. Index: include/polly/ScopDetection.h =================================================================== --- include/polly/ScopDetection.h +++ include/polly/ScopDetection.h @@ -430,13 +430,9 @@ /// function. //@{ typedef RegionSet::iterator iterator; - typedef RegionSet::const_iterator const_iterator; iterator begin() { return ValidRegions.begin(); } iterator end() { return ValidRegions.end(); } - - const_iterator begin() const { return ValidRegions.begin(); } - const_iterator end() const { return ValidRegions.end(); } //@} /// @name Reject log iterators Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -24,8 +24,11 @@ #include "polly/Support/SCEVAffinator.h" #include "llvm/ADT/MapVector.h" -#include "llvm/Analysis/RegionPass.h" #include "isl/aff.h" + +#include "llvm/Analysis/RegionPass.h" +#include "llvm/Pass.h" + #include "isl/ctx.h" #include @@ -1605,8 +1608,16 @@ ///===---------------------------------------------------------------------===// /// @brief Build the Polly IR (Scop and ScopStmt) on a Region. /// -class ScopInfo : public RegionPass { - //===-------------------------------------------------------------------===// +class ScopInfo : public FunctionPass { +public: + /// @brief Type for a vector of SCoPs. + using ScopVectorTy = SmallVector; + + /// @brief Iterator type for a SCoP vector. + using iterator = ScopVectorTy::iterator; + using const_iterator = ScopVectorTy::const_iterator; + +private: ScopInfo(const ScopInfo &) = delete; const ScopInfo &operator=(const ScopInfo &) = delete; @@ -1631,79 +1642,72 @@ // must live until #scop is deleted. AccFuncMapType AccFuncMap; - // The Scop - Scop *scop; - isl_ctx *ctx; - - /// @brief Return the SCoP region that is currently processed. - Region *getRegion() const { - if (!scop) - return nullptr; - return &scop->getRegion(); - } + /// @brief The SCoPs build in this function. + ScopVectorTy Scops; - // Clear the context. - void clear(); + /// @brief The isl contexts for each SCoP created. + SmallVector IslCtxs; - // Build the SCoP for Region @p R. - void buildScop(Region &R, DominatorTree &DT); + /// @brief Build the SCoP for Region @p R. + Scop *buildScop(Region &R, DominatorTree &DT); /// @brief Build an instance of MemoryAccess from the Load/Store instruction. /// + /// @param S The SCoP currently build. /// @param Inst The Load/Store instruction that access the memory /// @param L The parent loop of the instruction - /// @param R The region on which to build the data access dictionary. /// @param BoxedLoops The set of loops that are overapproximated in @p R. /// @param ScopRIL The required invariant loads equivalence classes. - void buildMemoryAccess(Instruction *Inst, Loop *L, Region *R, + void buildMemoryAccess(Scop &S, Instruction *Inst, Loop *L, const ScopDetection::BoxedLoopsSetTy *BoxedLoops, const InvariantLoadsSetTy &ScopRIL); /// @brief Analyze and extract the cross-BB scalar dependences (or, /// dataflow dependencies) of an instruction. /// + /// @param S The SCoP currently build. /// @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, + bool buildScalarDependences(Scop &S, Instruction *Inst, Region *NonAffineSubRegio); /// @brief Create MemoryAccesses for the given PHI node in the given region. /// + /// @param S The SCoP currently build. /// @param PHI The PHI node to be handled - /// @param R The SCoP region /// @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, Region *NonAffineSubRegion, + void buildPHIAccesses(Scop &S, PHINode *PHI, Region *NonAffineSubRegion, bool IsExitBlock = false); /// @brief Build the access functions for the subregion @p SR. /// - /// @param R The SCoP region. + /// @param S The SCoP currently build. /// @param SR A subregion of @p R. - void buildAccessFunctions(Region &R, Region &SR); + void buildAccessFunctions(Scop &S, Region &SR); /// @brief Create ScopStmt for all BBs and non-affine subregions of @p SR. /// /// 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); + void buildStmts(Scop &S, Region &SR); /// @brief Build the access functions for the basic block @p BB /// - /// @param R The SCoP region. + /// @param S The SCoP currently build. /// @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, + void buildAccessFunctions(Scop &S, BasicBlock &BB, Region *NonAffineSubRegion = nullptr, bool IsExitBlock = false); /// @brief Create a new MemoryAccess object and add it to #AccFuncMap. /// + /// @param S The SCoP currently build. /// @param BB The block where the access takes place. /// @param Inst The instruction doing the access. It is not necessarily /// inside @p BB. @@ -1715,7 +1719,7 @@ /// @param Subscripts Access subscripts per dimension. /// @param Sizes The array diminsion's sizes. /// @param Origin Purpose of this access. - void addMemoryAccess(BasicBlock *BB, Instruction *Inst, + void addMemoryAccess(Scop &S, BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType Type, Value *BaseAddress, unsigned ElemBytes, bool Affine, Value *AccessValue, ArrayRef Subscripts, @@ -1725,6 +1729,7 @@ /// @brief Create a MemoryAccess that represents either a LoadInst or /// StoreInst. /// + /// @param S The SCoP currently build. /// @param MemAccInst The LoadInst or StoreInst. /// @param Type The kind of access. /// @param BaseAddress The accessed array's base address. @@ -1734,8 +1739,9 @@ /// @param Sizes The array dimension's sizes. /// @param AccessValue Value read or written. /// @see AccessOrigin - void addExplicitAccess(Instruction *MemAccInst, MemoryAccess::AccessType Type, - Value *BaseAddress, unsigned ElemBytes, bool IsAffine, + void addExplicitAccess(Scop &S, Instruction *MemAccInst, + MemoryAccess::AccessType Type, Value *BaseAddress, + unsigned ElemBytes, bool IsAffine, ArrayRef Subscripts, ArrayRef Sizes, Value *AccessValue); @@ -1743,20 +1749,22 @@ /// /// The access will be created at the @p Value's definition. /// + /// @param S The SCoP currently build. /// @param Value The value to be written. /// @see addScalarReadAccess() /// @see AccessOrigin - void addScalarWriteAccess(Instruction *Value); + void addScalarWriteAccess(Scop &S, Instruction *Value); /// @brief Create a MemoryAccess for reloading an llvm::Value. /// /// Use this overload only for non-PHI instructions. /// + /// @param S The SCoP currently build. /// @param Value The scalar expected to be loaded. /// @param User User of the scalar; this is where the access is added. /// @see addScalarWriteAccess() /// @see AccessOrigin - void addScalarReadAccess(Value *Value, Instruction *User); + void addScalarReadAccess(Scop &S, Value *Value, Instruction *User); /// @brief Create a MemoryAccess for reloading an llvm::Value. /// @@ -1764,19 +1772,22 @@ /// be available at the incoming block instead of when hitting the /// instruction. /// + /// @param S The SCoP currently build. /// @param Value The scalar expected to be loaded. /// @param User The PHI node referencing @p Value. /// @param UserBB Incoming block for the incoming @p Value. /// @see addPHIWriteAccess() /// @see addScalarWriteAccess() /// @see AccessOrigin - void addScalarReadAccess(Value *Value, PHINode *User, BasicBlock *UserBB); + void addScalarReadAccess(Scop &S, Value *Value, PHINode *User, + 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 S The SCoP currently build. /// @param PHI PHINode under consideration. /// @param IncomingBlock Some predecessor block. /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock. @@ -1785,7 +1796,7 @@ /// PHINode in the SCoP region's exit block. /// @see addPHIReadAccess() /// @see AccessOrigin - void addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock, + void addPHIWriteAccess(Scop &S, PHINode *PHI, BasicBlock *IncomingBlock, Value *IncomingValue, bool IsExitBlock); /// @brief Create a MemoryAccess for reading the value of a phi. @@ -1794,32 +1805,33 @@ /// to the same location. Thus, this access will read the incoming block's /// value as instructed by this @p PHI. /// + /// @param S The SCoP currently build. /// @param PHI PHINode under consideration; the READ access will be added /// here. /// @see addPHIWriteAccess() /// @see AccessOrigin - void addPHIReadAccess(PHINode *PHI); + void addPHIReadAccess(Scop &S, PHINode *PHI); public: static char ID; - explicit ScopInfo(); + ScopInfo() : FunctionPass(ID) {} ~ScopInfo(); - /// @brief Try to build the Polly IR of static control part on the current - /// SESE-Region. + /// @brief Iterator interface to access all SCoPs in this function. /// - /// @return If the current region is a valid for a static control part, - /// return the Polly IR representing this static control part, - /// return null otherwise. - Scop *getScop() { return scop; } - const Scop *getScop() const { return scop; } + ///{ + iterator begin() { return Scops.begin(); } + iterator end() { return Scops.end(); } + const_iterator begin() const { return Scops.begin(); } + const_iterator end() const { return Scops.end(); } + ///} - /// @name RegionPass interface + /// @name FunctionPass interface //@{ - virtual bool runOnRegion(Region *R, RGPassManager &RGM); - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory() { clear(); } - virtual void print(raw_ostream &OS, const Module *) const; + virtual bool runOnFunction(Function &F) override; + virtual void getAnalysisUsage(AnalysisUsage &AU) const override; + virtual void releaseMemory() override; + virtual void print(raw_ostream &OS, const Module *) const override; //@} }; Index: include/polly/ScopPass.h =================================================================== --- include/polly/ScopPass.h +++ include/polly/ScopPass.h @@ -7,7 +7,7 @@ // //===----------------------------------------------------------------------===// // -// This file defines the ScopPass class. ScopPasses are just RegionPasses, +// This file defines the ScopPass class. ScopPasses are just FunctionPasses, // except they operate on Polly IR (Scop and ScopStmt) built by ScopInfo Pass. // Because they operate on Polly IR, not the LLVM IR, ScopPasses are not allowed // to modify the LLVM IR. Due to this limitation, the ScopPass class takes @@ -18,7 +18,7 @@ #ifndef POLLY_SCOP_PASS_H #define POLLY_SCOP_PASS_H -#include "llvm/Analysis/RegionPass.h" +#include "llvm/Pass.h" using namespace llvm; @@ -26,31 +26,36 @@ namespace polly { class Scop; +class ScopInfo; -/// ScopPass - This class adapts the RegionPass interface to allow convenient +/// ScopPass - This class adapts the FunctionPass interface to allow convenient /// creation of passes that operate on the Polly IR. Instead of overriding -/// runOnRegion, subclasses override runOnScop. -class ScopPass : public RegionPass { - Scop *S; +/// runOnFunction, subclasses override runOnScop. +class ScopPass : public FunctionPass { + + /// @brief The ScopInfo class that builds the SCoPs. + ScopInfo *SI; protected: - explicit ScopPass(char &ID) : RegionPass(ID), S(0) {} + explicit ScopPass(char &ID) : FunctionPass(ID) {} - /// runOnScop - This method must be overloaded to perform the - /// desired Polyhedral transformation or analysis. - /// + /// @brief Run method for all ScopPass subclasses. Called for each SCoP once. virtual bool runOnScop(Scop &S) = 0; + /// @brief Initialization method run once per function. + /// + /// This allows ScopPass subclasses to initialize members like analysis passes + /// once per function instead of once per SCoP. + virtual void initializeScopPass() = 0; + /// @brief Print method for SCoPs. virtual void printScop(raw_ostream &OS, Scop &S) const {}; - /// getAnalysisUsage - Subclasses that override getAnalysisUsage - /// must call this. - /// + /// @brief Subclasses that override getAnalysisUsage must call this. virtual void getAnalysisUsage(AnalysisUsage &AU) const override; private: - bool runOnRegion(Region *R, RGPassManager &RGM) override; + bool runOnFunction(Function &F) override; void print(raw_ostream &OS, const Module *) const override; }; Index: lib/Analysis/DependenceInfo.cpp =================================================================== --- lib/Analysis/DependenceInfo.cpp +++ lib/Analysis/DependenceInfo.cpp @@ -25,6 +25,8 @@ #include "polly/Options.h" #include "polly/ScopInfo.h" #include "polly/Support/GICHelper.h" + +#include "llvm/Analysis/RegionInfo.h" #include "llvm/Support/Debug.h" #include #include @@ -688,17 +690,25 @@ ReductionDependences[MA] = D; } -void DependenceInfo::recomputeDependences() { - releaseMemory(); - D.calculateDependences(*S); +void DependenceInfo::releaseMemory() { DependenceMap.clear(); } + +void DependenceInfo::recomputeDependences(Scop &S) { + Dependences &D = getDependences(S); + D.releaseMemory(); + D.calculateDependences(S); } -bool DependenceInfo::runOnScop(Scop &ScopVar) { - S = &ScopVar; - recomputeDependences(); +bool DependenceInfo::runOnScop(Scop &S) { + Dependences &D = DependenceMap[&S]; + D.calculateDependences(S); return false; } +void DependenceInfo::printScop(raw_ostream &OS, Scop &S) const { + OS << "Dependences for region: " << S.getRegion() << "\n"; + getDependences(S).print(OS); +} + void DependenceInfo::getAnalysisUsage(AnalysisUsage &AU) const { ScopPass::getAnalysisUsage(AU); } Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -3263,7 +3263,7 @@ return L->getLoopDepth() - OuterLoop->getLoopDepth(); } -void ScopInfo::buildPHIAccesses(PHINode *PHI, Region &R, +void ScopInfo::buildPHIAccesses(Scop &S, PHINode *PHI, Region *NonAffineSubRegion, bool IsExitBlock) { // PHI nodes that are in the exit block of the region, hence if IsExitBlock is @@ -3274,7 +3274,7 @@ // 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)) + if (!IsExitBlock && canSynthesize(PHI, LI, SE, &S.getRegion())) return; // PHI nodes are modeled as if they had been demoted prior to the SCoP @@ -3291,7 +3291,7 @@ OnlyNonAffineSubRegionOperands = false; - if (!R.contains(OpBB)) + if (!S.getRegion().contains(OpBB)) continue; Instruction *OpI = dyn_cast(Op); @@ -3300,25 +3300,25 @@ // 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 (scop->getStmtForBasicBlock(OpIBB) != - scop->getStmtForBasicBlock(OpBB)) { - addScalarReadAccess(OpI, PHI, OpBB); - addScalarWriteAccess(OpI); + if (S.getStmtForBasicBlock(OpIBB) != S.getStmtForBasicBlock(OpBB)) { + addScalarReadAccess(S, OpI, PHI, OpBB); + addScalarWriteAccess(S, OpI); } } else if (ModelReadOnlyScalars && !isa(Op)) { - addScalarReadAccess(Op, PHI, OpBB); + addScalarReadAccess(S, Op, PHI, OpBB); } - addPHIWriteAccess(PHI, OpBB, Op, IsExitBlock); + addPHIWriteAccess(S, PHI, OpBB, Op, IsExitBlock); } if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) { - addPHIReadAccess(PHI); + addPHIReadAccess(S, PHI); } } -bool ScopInfo::buildScalarDependences(Instruction *Inst, Region *R, +bool ScopInfo::buildScalarDependences(Scop &S, Instruction *Inst, Region *NonAffineSubRegion) { + Region *R = &S.getRegion(); bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R); if (isIgnoredIntrinsic(Inst)) return false; @@ -3406,7 +3406,7 @@ // Do not build a read access that is not in the current SCoP // Use the def instruction as base address of the MemoryAccess, so that it // will become the name of the scalar access in the polyhedral form. - addScalarReadAccess(Inst, UI); + addScalarReadAccess(S, Inst, UI); } if (ModelReadOnlyScalars && !isa(Inst)) { @@ -3421,7 +3421,7 @@ if (isa(Op)) continue; - addScalarReadAccess(Op, Inst); + addScalarReadAccess(S, Op, Inst); } } @@ -3431,13 +3431,15 @@ extern MapInsnToMemAcc InsnToMemAcc; void ScopInfo::buildMemoryAccess( - Instruction *Inst, Loop *L, Region *R, + Scop &S, Instruction *Inst, Loop *L, const ScopDetection::BoxedLoopsSetTy *BoxedLoops, const InvariantLoadsSetTy &ScopRIL) { + unsigned Size; Type *SizeType; Value *Val; enum MemoryAccess::AccessType Type; + Region *R = &S.getRegion(); if (LoadInst *Load = dyn_cast(Inst)) { SizeType = Load->getType(); @@ -3500,7 +3502,7 @@ SizesSCEV.push_back(SE->getSCEV(ConstantInt::get( IntegerType::getInt64Ty(BasePtr->getContext()), Size))); - addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, true, + addExplicitAccess(S, Inst, Type, BasePointer->getValue(), Size, true, Subscripts, SizesSCEV, Val); return; } @@ -3509,7 +3511,7 @@ auto AccItr = InsnToMemAcc.find(Inst); if (PollyDelinearize && AccItr != InsnToMemAcc.end()) { - addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, true, + addExplicitAccess(S, Inst, Type, BasePointer->getValue(), Size, true, AccItr->second.DelinearizedSubscripts, AccItr->second.Shape->DelinearizedSizes, Val); return; @@ -3542,58 +3544,59 @@ if (!IsAffine && Type == MemoryAccess::MUST_WRITE) Type = MemoryAccess::MAY_WRITE; - addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, IsAffine, + addExplicitAccess(S, Inst, Type, BasePointer->getValue(), Size, IsAffine, ArrayRef(AccessFunction), ArrayRef(SizeSCEV), Val); } -void ScopInfo::buildAccessFunctions(Region &R, Region &SR) { +void ScopInfo::buildAccessFunctions(Scop &S, Region &SR) { - if (SD->isNonAffineSubRegion(&SR, &R)) { + if (SD->isNonAffineSubRegion(&SR, &S.getRegion())) { for (BasicBlock *BB : SR.blocks()) - buildAccessFunctions(R, *BB, &SR); + buildAccessFunctions(S, *BB, &SR); return; } for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I) if (I->isSubRegion()) - buildAccessFunctions(R, *I->getNodeAs()); + buildAccessFunctions(S, *I->getNodeAs()); else - buildAccessFunctions(R, *I->getNodeAs()); + buildAccessFunctions(S, *I->getNodeAs()); } -void ScopInfo::buildStmts(Region &SR) { - Region *R = getRegion(); +void ScopInfo::buildStmts(Scop &S, Region &SR) { + Region *R = &S.getRegion(); if (SD->isNonAffineSubRegion(&SR, R)) { - scop->addScopStmt(nullptr, &SR); + S.addScopStmt(nullptr, &SR); return; } for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I) if (I->isSubRegion()) - buildStmts(*I->getNodeAs()); + buildStmts(S, *I->getNodeAs()); else - scop->addScopStmt(I->getNodeAs(), nullptr); + S.addScopStmt(I->getNodeAs(), nullptr); } -void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB, +void ScopInfo::buildAccessFunctions(Scop &S, BasicBlock &BB, Region *NonAffineSubRegion, bool IsExitBlock) { + Region *R = &S.getRegion(); 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); + const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(R); // The set of loads that are required to be invariant. - auto &ScopRIL = *SD->getRequiredInvariantLoads(&R); + auto &ScopRIL = *SD->getRequiredInvariantLoads(R); for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) { Instruction *Inst = I; PHINode *PHI = dyn_cast(Inst); if (PHI) - buildPHIAccesses(PHI, R, NonAffineSubRegion, IsExitBlock); + buildPHIAccesses(S, PHI, NonAffineSubRegion, IsExitBlock); // For the exit block we stop modeling after the last PHI node. if (!PHI && IsExitBlock) @@ -3604,7 +3607,7 @@ // there might be other invariant accesses that will be hoisted and // that would allow to make a non-affine access affine. if (isa(Inst) || isa(Inst)) - buildMemoryAccess(Inst, L, &R, BoxedLoops, ScopRIL); + buildMemoryAccess(S, Inst, L, BoxedLoops, ScopRIL); if (isIgnoredIntrinsic(Inst)) continue; @@ -3614,21 +3617,21 @@ if (ScopRIL.count(dyn_cast(Inst))) continue; - if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) { + if (buildScalarDependences(S, Inst, NonAffineSubRegion)) { if (!isa(Inst)) - addScalarWriteAccess(Inst); + addScalarWriteAccess(S, Inst); } } } -void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst, +void ScopInfo::addMemoryAccess(Scop &S, BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType Type, Value *BaseAddress, unsigned ElemBytes, bool Affine, Value *AccessValue, ArrayRef Subscripts, ArrayRef Sizes, MemoryAccess::AccessOrigin Origin) { - ScopStmt *Stmt = scop->getStmtForBasicBlock(BB); + ScopStmt *Stmt = S.getStmtForBasicBlock(BB); // Do not create a memory access for anything not in the SCoP. It would be // ignored anyway. @@ -3642,7 +3645,7 @@ std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, ""); std::string IdName = "__polly_array_ref_" + std::to_string(Identifier); - isl_id *Id = isl_id_alloc(ctx, IdName.c_str(), nullptr); + isl_id *Id = isl_id_alloc(IslCtxs.back(), IdName.c_str(), nullptr); bool isApproximated = Stmt->isRegionStmt() && (Stmt->getRegion()->getEntry() != BB); @@ -3654,52 +3657,61 @@ Stmt->addAccess(&AccList.back()); } -void ScopInfo::addExplicitAccess( - Instruction *MemAccInst, MemoryAccess::AccessType Type, Value *BaseAddress, - unsigned ElemBytes, bool IsAffine, ArrayRef Subscripts, - ArrayRef Sizes, Value *AccessValue) { +void ScopInfo::addExplicitAccess(Scop &S, Instruction *MemAccInst, + MemoryAccess::AccessType Type, + Value *BaseAddress, unsigned ElemBytes, + bool IsAffine, + ArrayRef Subscripts, + ArrayRef Sizes, + Value *AccessValue) { assert(isa(MemAccInst) || isa(MemAccInst)); assert(isa(MemAccInst) == (Type == MemoryAccess::READ)); - addMemoryAccess(MemAccInst->getParent(), MemAccInst, Type, BaseAddress, + addMemoryAccess(S, MemAccInst->getParent(), MemAccInst, Type, BaseAddress, ElemBytes, IsAffine, AccessValue, Subscripts, Sizes, MemoryAccess::EXPLICIT); } -void ScopInfo::addScalarWriteAccess(Instruction *Value) { - addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, 1, - true, Value, ArrayRef(), +void ScopInfo::addScalarWriteAccess(Scop &S, Instruction *Value) { + addMemoryAccess(S, Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, + 1, true, Value, ArrayRef(), ArrayRef(), MemoryAccess::SCALAR); } -void ScopInfo::addScalarReadAccess(Value *Value, Instruction *User) { +void ScopInfo::addScalarReadAccess(Scop &S, Value *Value, Instruction *User) { assert(!isa(User)); - addMemoryAccess(User->getParent(), User, MemoryAccess::READ, Value, 1, true, - Value, ArrayRef(), ArrayRef(), - MemoryAccess::SCALAR); + addMemoryAccess(S, User->getParent(), User, MemoryAccess::READ, Value, 1, + true, Value, ArrayRef(), + ArrayRef(), MemoryAccess::SCALAR); } -void ScopInfo::addScalarReadAccess(Value *Value, PHINode *User, +void ScopInfo::addScalarReadAccess(Scop &S, Value *Value, PHINode *User, BasicBlock *UserBB) { - addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, 1, true, Value, + addMemoryAccess(S, UserBB, User, MemoryAccess::READ, Value, 1, true, Value, ArrayRef(), ArrayRef(), MemoryAccess::SCALAR); } -void ScopInfo::addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock, +void ScopInfo::addPHIWriteAccess(Scop &S, PHINode *PHI, + BasicBlock *IncomingBlock, Value *IncomingValue, bool IsExitBlock) { - addMemoryAccess(IncomingBlock, IncomingBlock->getTerminator(), + addMemoryAccess(S, IncomingBlock, IncomingBlock->getTerminator(), MemoryAccess::MUST_WRITE, PHI, 1, true, IncomingValue, ArrayRef(), ArrayRef(), IsExitBlock ? MemoryAccess::SCALAR : MemoryAccess::PHI); } -void ScopInfo::addPHIReadAccess(PHINode *PHI) { - addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI, - ArrayRef(), ArrayRef(), +void ScopInfo::addPHIReadAccess(Scop &S, PHINode *PHI) { + addMemoryAccess(S, PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, + PHI, ArrayRef(), ArrayRef(), MemoryAccess::PHI); } -void ScopInfo::buildScop(Region &R, DominatorTree &DT) { +Scop *ScopInfo::buildScop(Region &R, DominatorTree &DT) { + + isl_ctx *Ctx = isl_ctx_alloc(); + isl_options_set_on_error(Ctx, ISL_ON_ERROR_ABORT); + IslCtxs.push_back(Ctx); + unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD); - scop = new Scop(R, AccFuncMap, *SD, *SE, DT, *LI, ctx, MaxLoopDepth); + Scop *S = new Scop(R, AccFuncMap, *SD, *SE, DT, *LI, Ctx, MaxLoopDepth); - buildStmts(R); - buildAccessFunctions(R, R); + buildStmts(*S, R); + buildAccessFunctions(*S, 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 @@ -3709,42 +3721,68 @@ // 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); + buildAccessFunctions(*S, *R.getExit(), nullptr, /* IsExitBlock */ true); - scop->init(*AA); + S->init(*AA); + return S; } -void ScopInfo::print(raw_ostream &OS, const Module *) const { - if (!scop) { - OS << "Invalid Scop!\n"; - return; +bool ScopInfo::runOnFunction(Function &F) { + SD = &getAnalysis(); + + SE = &getAnalysis().getSE(); + LI = &getAnalysis().getLoopInfo(); + AA = &getAnalysis().getAAResults(); + TD = &F.getParent()->getDataLayout(); + DominatorTree &DT = getAnalysis().getDomTree(); + + for (ScopDetection::iterator I = SD->begin(), E = SD->end(); I != E; ++I) { + const Region *R = *I; + if (!SD->isMaxRegionInScop(*R)) + continue; + + Scop *S = buildScop(const_cast(*R), DT); + DEBUG(S->print(dbgs())); + + if (!S->hasFeasibleRuntimeContext()) { + delete S; + continue; + } + + Scops.push_back(S); + + // Statistics. + ++ScopFound; + if (S->getMaxLoopDepth() > 0) + ++RichScopFound; } + return false; +} - scop->print(OS); +void ScopInfo::print(raw_ostream &OS, const Module *) const { + for (const Scop *S : *this) + S->print(OS); } -void ScopInfo::clear() { +void ScopInfo::releaseMemory() { AccFuncMap.clear(); - if (scop) { - delete scop; - scop = 0; - } -} -//===----------------------------------------------------------------------===// -ScopInfo::ScopInfo() : RegionPass(ID), scop(0) { - ctx = isl_ctx_alloc(); - isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT); + for (const Scop *S : *this) + delete S; + Scops.clear(); } ScopInfo::~ScopInfo() { - clear(); - isl_ctx_free(ctx); + releaseMemory(); + + for (isl_ctx *Ctx : IslCtxs) + isl_ctx_free(Ctx); + IslCtxs.clear(); } void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequiredTransitive(); AU.addRequired(); - AU.addRequired(); AU.addRequired(); AU.addRequiredTransitive(); AU.addRequiredTransitive(); @@ -3752,36 +3790,6 @@ AU.setPreservesAll(); } -bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) { - SD = &getAnalysis(); - - if (!SD->isMaxRegionInScop(*R)) - return false; - - Function *F = R->getEntry()->getParent(); - SE = &getAnalysis().getSE(); - LI = &getAnalysis().getLoopInfo(); - AA = &getAnalysis().getAAResults(); - TD = &F->getParent()->getDataLayout(); - DominatorTree &DT = getAnalysis().getDomTree(); - - buildScop(*R, DT); - - DEBUG(scop->print(dbgs())); - - if (scop->isEmpty() || !scop->hasFeasibleRuntimeContext()) { - delete scop; - scop = nullptr; - return false; - } - - // Statistics. - ++ScopFound; - if (scop->getMaxLoopDepth() > 0) - ++RichScopFound; - return false; -} - char ScopInfo::ID = 0; Pass *polly::createScopInfoPass() { return new ScopInfo(); } Index: lib/Analysis/ScopPass.cpp =================================================================== --- lib/Analysis/ScopPass.cpp +++ lib/Analysis/ScopPass.cpp @@ -17,21 +17,23 @@ using namespace llvm; using namespace polly; -bool ScopPass::runOnRegion(Region *R, RGPassManager &RGM) { - S = nullptr; +bool ScopPass::runOnFunction(Function &F) { + SI = &getAnalysis(); - if ((S = getAnalysis().getScop())) - return runOnScop(*S); + initializeScopPass(); + + for (Scop *S : *SI) + runOnScop(*S); return false; } void ScopPass::print(raw_ostream &OS, const Module *M) const { - if (S) + for (Scop *S : *SI) printScop(OS, *S); } void ScopPass::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); + AU.addRequiredTransitive(); AU.setPreservesAll(); } Index: lib/CodeGen/BlockGenerators.cpp =================================================================== --- lib/CodeGen/BlockGenerators.cpp +++ lib/CodeGen/BlockGenerators.cpp @@ -520,7 +520,8 @@ } } -void BlockGenerator::createScalarFinalization(Region &R) { +void BlockGenerator::createScalarFinalization(Region &R, + ValueMapT &InterScopMap) { // The exit block of the __unoptimized__ region. BasicBlock *ExitBB = R.getExitingBlock(); // The merge block __just after__ the region and the optimized region. @@ -556,9 +557,11 @@ MergePHI->addIncoming(EscapeInst, ExitBB); // The information of scalar evolution about the escaping instruction needs - // to be revoked so the new merged instruction will be used. - if (SE.isSCEVable(EscapeInst->getType())) + // to be updated so the new merged instruction will be used in other SCoPs. + if (SE.isSCEVable(EscapeInst->getType())) { SE.forgetValue(EscapeInst); + InterScopMap[EscapeInst] = MergePHI; + } // Replace all uses of the demoted instruction with the merge PHI. for (Instruction *EUser : EscapeUsers) @@ -632,11 +635,11 @@ } } -void BlockGenerator::finalizeSCoP(Scop &S) { +void BlockGenerator::finalizeSCoP(Scop &S, ValueMapT &VMap) { findOutsideUsers(S); createScalarInitialization(S); createExitPHINodeMerges(S); - createScalarFinalization(S.getRegion()); + createScalarFinalization(S.getRegion(), VMap); } VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen, Index: lib/CodeGen/CodeGeneration.cpp =================================================================== --- lib/CodeGen/CodeGeneration.cpp +++ lib/CodeGen/CodeGeneration.cpp @@ -30,6 +30,7 @@ #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/PostDominators.h" +#include "llvm/Analysis/RegionInfo.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" #include "llvm/IR/Module.h" #include "llvm/IR/Verifier.h" @@ -60,15 +61,26 @@ RegionInfo *RI; ///} + /// @brief Mapping from escaping scevable values to the new merged ones. + /// + /// We build code for the SCoPs in a function one after another, thus there + /// can be a use in a later SCoP of a value defined in a former one. In such + /// cases we map the used value to the merged value at the end of the + /// optimized former region. This is necessary because we cache SCEVs in the + /// later SCoPs that would otherwise reference value that do not dominate the + /// later SCoP any more. + ValueMapT InterScopMap; + /// @brief Build the runtime condition. /// /// Build the condition that evaluates at run-time to true iff all /// assumptions taken for the SCoP hold, and to false otherwise. /// /// @return A value evaluating to true/false if execution is save/unsafe. - Value *buildRTC(PollyIRBuilder &Builder, IslExprBuilder &ExprBuilder) { + Value *buildRTC(Scop &S, PollyIRBuilder &Builder, + IslExprBuilder &ExprBuilder) { Builder.SetInsertPoint(Builder.GetInsertBlock()->getTerminator()); - Value *RTC = ExprBuilder.create(AI->getRunCondition()); + Value *RTC = ExprBuilder.create(AI->getRunCondition(S)); if (!RTC->getType()->isIntegerTy(1)) RTC = Builder.CreateIsNotNull(RTC); return RTC; @@ -107,18 +119,12 @@ /// @brief Generate LLVM-IR for the SCoP @p S. bool runOnScop(Scop &S) override { - AI = &getAnalysis(); // Check if we created an isl_ast root node, otherwise exit. - isl_ast_node *AstRoot = AI->getAst(); + isl_ast_node *AstRoot = AI->getAst(S); if (!AstRoot) return false; - LI = &getAnalysis().getLoopInfo(); - DT = &getAnalysis().getDomTree(); - SE = &getAnalysis().getSE(); - DL = &S.getRegion().getEntry()->getParent()->getParent()->getDataLayout(); - RI = &getAnalysis().getRegionInfo(); Region *R = &S.getRegion(); assert(!R->isTopLevelRegion() && "Top level regions are not supported"); @@ -131,7 +137,9 @@ assert(EnteringBB); PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator); - IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S); + DL = &S.getRegion().getEntry()->getParent()->getParent()->getDataLayout(); + IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S, + InterScopMap); // Only build the run-time condition and parameters _after_ having // introduced the conditional branch. This is important as the conditional @@ -151,7 +159,7 @@ NodeBuilder.preloadInvariantLoads(); NodeBuilder.addParameters(S.getContext()); - Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder()); + Value *RTC = buildRTC(S, Builder, NodeBuilder.getExprBuilder()); Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC); Builder.SetInsertPoint(StartBlock->begin()); @@ -165,6 +173,15 @@ return true; } + /// @brief Initializer called once per function. + void initializeScopPass() override { + AI = &getAnalysis(); + LI = &getAnalysis().getLoopInfo(); + DT = &getAnalysis().getDomTree(); + SE = &getAnalysis().getSE(); + RI = &getAnalysis().getRegionInfo(); + } + /// @brief Register all analyses and transformation required. void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); @@ -172,8 +189,8 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); - AU.addRequired(); AU.addRequired(); + AU.addRequiredTransitive(); AU.addPreserved(); Index: lib/CodeGen/IslAst.cpp =================================================================== --- lib/CodeGen/IslAst.cpp +++ lib/CodeGen/IslAst.cpp @@ -433,29 +433,31 @@ } void IslAstInfo::releaseMemory() { - if (Ast) { - delete Ast; - Ast = nullptr; - } + DeleteContainerSeconds(AstMap); + AstMap.clear(); } -bool IslAstInfo::runOnScop(Scop &Scop) { - if (Ast) - delete Ast; - - S = &Scop; +void IslAstInfo::initializeScopPass() { DI = &getAnalysis(); } - const Dependences &D = getAnalysis().getDependences(); +bool IslAstInfo::runOnScop(Scop &S) { - Ast = IslAst::create(&Scop, D); + const Dependences &D = DI->getDependences(S); + AstMap[&S] = IslAst::create(&S, D); - DEBUG(printScop(dbgs(), Scop)); + DEBUG(printScop(dbgs(), S)); return false; } -__isl_give isl_ast_node *IslAstInfo::getAst() const { return Ast->getAst(); } -__isl_give isl_ast_expr *IslAstInfo::getRunCondition() const { - return Ast->getRunCondition(); +__isl_give isl_ast_node *IslAstInfo::getAst(Scop &S) const { + IslAst *AST = AstMap.lookup(&S); + assert(AST && "AST for given SCoP not found!"); + return AST->getAst(); +} + +__isl_give isl_ast_expr *IslAstInfo::getRunCondition(Scop &S) const { + IslAst *AST = AstMap.lookup(&S); + assert(AST && "AST for given SCoP not found!"); + return AST->getRunCondition(); } IslAstUserPayload *IslAstInfo::getNodePayload(__isl_keep isl_ast_node *Node) { @@ -537,7 +539,7 @@ void IslAstInfo::printScop(raw_ostream &OS, Scop &S) const { isl_ast_print_options *Options; - isl_ast_node *RootNode = getAst(); + isl_ast_node *RootNode = getAst(S); Function *F = S.getRegion().getEntry()->getParent(); OS << ":: isl ast :: " << F->getName() << " :: " << S.getRegion().getNameStr() @@ -553,7 +555,7 @@ return; } - isl_ast_expr *RunCondition = getRunCondition(); + isl_ast_expr *RunCondition = getRunCondition(S); char *RtCStr, *AstStr; Options = isl_ast_print_options_alloc(S.getIslCtx()); @@ -592,7 +594,6 @@ void IslAstInfo::getAnalysisUsage(AnalysisUsage &AU) const { // Get the Common analysis usage of ScopPasses. ScopPass::getAnalysisUsage(AU); - AU.addRequired(); AU.addRequired(); } Index: lib/CodeGen/IslExprBuilder.cpp =================================================================== --- lib/CodeGen/IslExprBuilder.cpp +++ lib/CodeGen/IslExprBuilder.cpp @@ -13,6 +13,9 @@ #include "polly/ScopInfo.h" #include "polly/Support/GICHelper.h" #include "polly/Support/ScopHelper.h" + +#include "llvm/Analysis/ScalarEvolutionExpander.h" +#include "llvm/IR/Dominators.h" #include "llvm/Support/Debug.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" Index: lib/CodeGen/IslNodeBuilder.cpp =================================================================== --- lib/CodeGen/IslNodeBuilder.cpp +++ lib/CodeGen/IslNodeBuilder.cpp @@ -30,6 +30,7 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/PostDominators.h" +#include "llvm/Analysis/RegionInfo.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Module.h" #include "llvm/IR/Verifier.h" Index: lib/Exchange/JSONExporter.cpp =================================================================== --- lib/Exchange/JSONExporter.cpp +++ lib/Exchange/JSONExporter.cpp @@ -69,6 +69,9 @@ /// @brief Register all analyses and transformation required. void getAnalysisUsage(AnalysisUsage &AU) const override; + + /// @brief Initializer called once per function. + void initializeScopPass() override {} }; struct JSONImporter : public ScopPass { @@ -86,6 +89,9 @@ /// @brief Register all analyses and transformation required. void getAnalysisUsage(AnalysisUsage &AU) const override; + + /// @brief Initializer called once per function. + void initializeScopPass() override {} }; } @@ -173,7 +179,7 @@ void JSONExporter::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - AU.addRequired(); + AU.addRequiredTransitive(); } Pass *polly::createJSONExporterPass() { return new JSONExporter(); } @@ -201,7 +207,7 @@ bool JSONImporter::runOnScop(Scop &S) { Region &R = S.getRegion(); - const Dependences &D = getAnalysis().getDependences(); + const Dependences &D = getAnalysis().getDependences(S); const DataLayout &DL = S.getRegion().getEntry()->getParent()->getParent()->getDataLayout(); Index: lib/Support/SCEVAffinator.cpp =================================================================== --- lib/Support/SCEVAffinator.cpp +++ lib/Support/SCEVAffinator.cpp @@ -16,6 +16,7 @@ #include "polly/Support/GICHelper.h" #include "polly/Support/SCEVValidator.h" #include "polly/Support/ScopHelper.h" +#include "llvm/Analysis/RegionInfo.h" #include "isl/aff.h" #include "isl/local_space.h" #include "isl/set.h" Index: lib/Transform/DeadCodeElimination.cpp =================================================================== --- lib/Transform/DeadCodeElimination.cpp +++ lib/Transform/DeadCodeElimination.cpp @@ -62,10 +62,16 @@ /// @brief Remove dead iterations from the schedule of @p S. bool runOnScop(Scop &S) override; + /// @brief Initializer called once per function. + void initializeScopPass() override; + /// @brief Register all analyses and transformation required. void getAnalysisUsage(AnalysisUsage &AU) const override; private: + /// @brief The dependence info pass. + DependenceInfo *DI; + /// @brief Return the set of live iterations. /// /// The set of live iterations are all iterations that write to memory and for @@ -115,7 +121,7 @@ /// simplifies the life set with an affine hull. bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) { DependenceInfo &DI = getAnalysis(); - const Dependences &D = DI.getDependences(); + const Dependences &D = DI.getDependences(S); if (!D.hasValidDependences()) return false; @@ -156,13 +162,15 @@ bool Changed = S.restrictDomains(isl_union_set_coalesce(Live)); - // FIXME: We can probably avoid the recomputation of all dependences by + // FIXME: We can probably avoid the recomputation of all DependenceInfo by // updating them explicitly. if (Changed) - DI.recomputeDependences(); + DI.recomputeDependences(S); return Changed; } +void DeadCodeElim::initializeScopPass() { DI = &getAnalysis(); } + bool DeadCodeElim::runOnScop(Scop &S) { return eliminateDeadCode(S, DCEPreciseSteps); } Index: lib/Transform/ScheduleOptimizer.cpp =================================================================== --- lib/Transform/ScheduleOptimizer.cpp +++ lib/Transform/ScheduleOptimizer.cpp @@ -430,6 +430,9 @@ /// @brief Optimize the schedule of the SCoP @p S. bool runOnScop(Scop &S) override; + /// @brief Initializer called once per function. + void initializeScopPass() override; + /// @brief Print the new schedule for the SCoP @p S. void printScop(raw_ostream &OS, Scop &S) const override; @@ -444,11 +447,18 @@ private: isl_schedule *LastSchedule; + + /// @brief The dependence info pass. + DependenceInfo *DI; }; } char IslScheduleOptimizer::ID = 0; +void IslScheduleOptimizer::initializeScopPass() { + DI = &getAnalysis(); +} + bool IslScheduleOptimizer::runOnScop(Scop &S) { // Skip empty SCoPs but still allow code generation as it will delete the @@ -458,8 +468,7 @@ return false; } - const Dependences &D = getAnalysis().getDependences(); - + const Dependences &D = DI->getDependences(S); if (!D.hasValidDependences()) return false; Index: test/DependenceInfo/computeout.ll =================================================================== --- test/DependenceInfo/computeout.ll +++ test/DependenceInfo/computeout.ll @@ -50,7 +50,8 @@ ret void } -; VALUE: region: 'S1 => exit.3' in function 'sequential_writes': +; VALUE: function 'sequential_writes' +; VALUE: for region: S1 => exit.3 ; VALUE: RAW dependences: ; VALUE: { } ; VALUE: WAR dependences: @@ -62,7 +63,8 @@ ; VALUE: Stmt_S1[i0] -> Stmt_S3[i0] : i0 <= 99 and i0 >= 10 ; VALUE: } -; TIMEOUT: region: 'S1 => exit.3' in function 'sequential_writes': +; TIMEOUT: function 'sequential_writes' +; TIMEOUT: for region: S1 => exit.3 ; TIMEOUT: RAW dependences: ; TIMEOUT: n/a ; TIMEOUT: WAR dependences: Index: test/DependenceInfo/sequential_loops.ll =================================================================== --- test/DependenceInfo/sequential_loops.ll +++ test/DependenceInfo/sequential_loops.ll @@ -50,7 +50,8 @@ ret void } -; VALUE-LABEL: region: 'S1 => exit.3' in function 'sequential_writes': +; VALUE: for function 'sequential_writes' +; VALUE: region: S1 => exit.3 ; VALUE: RAW dependences: ; VALUE: { } ; VALUE: WAR dependences: @@ -62,7 +63,8 @@ ; VALUE: Stmt_S1[i0] -> Stmt_S3[i0] : i0 <= 99 and i0 >= 10 ; VALUE: } -; MEMORY-LABEL: region: 'S1 => exit.3' in function 'sequential_writes': +; MEMORY: for function 'sequential_writes' +; MEMORY: region: S1 => exit.3 ; MEMORY: RAW dependences: ; MEMORY: { } ; MEMORY: WAR dependences: @@ -125,7 +127,8 @@ ret void } -; VALUE-LABEL: region: 'S1 => exit.3' in function 'read_after_writes': +; VALUE: for function 'read_after_writes' +; VALUE: region: S1 => exit.3 ; VALUE: RAW dependences: ; VALUE: { ; VALUE: Stmt_S2[i0] -> Stmt_S3[i0] : i0 <= 9 and i0 >= 0; @@ -138,7 +141,8 @@ ; VALUE: Stmt_S1[i0] -> Stmt_S2[i0] : i0 <= 9 and i0 >= 0 ; VALUE: } -; MEMORY-LABEL: region: 'S1 => exit.3' in function 'read_after_writes': +; MEMORY: for function 'read_after_writes' +; MEMORY: region: S1 => exit.3 ; MEMORY: RAW dependences: ; MEMORY: { ; MEMORY: Stmt_S2[i0] -> Stmt_S3[i0] : i0 <= 9 and i0 >= 0; @@ -202,7 +206,8 @@ ret void } -; VALUE-LABEL: region: 'S1 => exit.3' in function 'write_after_read': +; VALUE: for function 'write_after_read' +; VALUE: region: S1 => exit.3 ; VALUE: RAW dependences: ; VALUE: { ; VALUE: } @@ -216,7 +221,8 @@ ; VALUE: Stmt_S2[i0] -> Stmt_S3[i0] : i0 <= 9 and i0 >= 0 ; VALUE: } -; MEMORY-LABEL: region: 'S1 => exit.3' in function 'write_after_read': +; MEMORY: for function 'write_after_read' +; MEMORY: region: S1 => exit.3 ; MEMORY: RAW dependences: ; MEMORY: { ; MEMORY: } @@ -268,7 +274,8 @@ ret void } -; VALUE: region: 'S1 => exit.2' in function 'parametric_offset': +; VALUE: for function 'parametric_offset' +; VALUE: region: S1 => exit.2 ; VALUE: RAW dependences: ; VALUE: [p] -> { ; VALUE: Stmt_S1[i0] -> Stmt_S2[-p + i0] : @@ -284,7 +291,8 @@ ; VALUE: [p] -> { ; VALUE: } -; MEMORY: region: 'S1 => exit.2' in function 'parametric_offset': +; MEMORY: for function 'parametric_offset' +; MEMORY: region: S1 => exit.2 ; MEMORY: RAW dependences: ; MEMORY: [p] -> { ; MEMORY: Stmt_S1[i0] -> Stmt_S2[-p + i0] : Index: test/Isl/CodeGen/MemAccess/simple_analyze.ll =================================================================== --- test/Isl/CodeGen/MemAccess/simple_analyze.ll +++ test/Isl/CodeGen/MemAccess/simple_analyze.ll @@ -49,6 +49,19 @@ ; Verify that the new access function (see above) is actually used during vector code generation. +; JSCOPVEC: store i32 0, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) +; JSCOPVEC: store i32 1, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) +; JSCOPVEC: store i32 2, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) +; JSCOPVEC: store i32 3, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) +; JSCOPVEC: store i32 4, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) +; JSCOPVEC: store i32 5, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) +; JSCOPVEC: store i32 6, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) +; JSCOPVEC: store i32 7, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) +; JSCOPVEC: store i32 8, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) +; JSCOPVEC: store i32 9, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) +; JSCOPVEC: store i32 10, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) +; JSCOPVEC: store i32 11, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) + ; JSCOPVEC: store i32 0, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0) ; JSCOPVEC: store i32 1, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0) ; JSCOPVEC: store i32 2, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0) @@ -62,15 +75,3 @@ ; JSCOPVEC: store i32 10, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0) ; JSCOPVEC: store i32 11, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @B, i32 0, i32 0) -; JSCOPVEC: store i32 0, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) -; JSCOPVEC: store i32 1, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) -; JSCOPVEC: store i32 2, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) -; JSCOPVEC: store i32 3, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) -; JSCOPVEC: store i32 4, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) -; JSCOPVEC: store i32 5, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) -; JSCOPVEC: store i32 6, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) -; JSCOPVEC: store i32 7, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) -; JSCOPVEC: store i32 8, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) -; JSCOPVEC: store i32 9, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) -; JSCOPVEC: store i32 10, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) -; JSCOPVEC: store i32 11, i32* getelementptr inbounds ([100 x i32], [100 x i32]* @A, i32 0, i32 0) Index: test/Isl/CodeGen/invariant_load_escaping_second_scop.ll =================================================================== --- test/Isl/CodeGen/invariant_load_escaping_second_scop.ll +++ test/Isl/CodeGen/invariant_load_escaping_second_scop.ll @@ -18,7 +18,7 @@ ; } while (i++ < x / 2); ; } ; -; CHECK: polly.start: +; CHECK: polly.start6: ; CHECK-NEXT: sext i32 %tmp.merge to i64 ; target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" Index: test/Isl/CodeGen/simple_loop_non_single_exit.ll =================================================================== --- test/Isl/CodeGen/simple_loop_non_single_exit.ll +++ test/Isl/CodeGen/simple_loop_non_single_exit.ll @@ -1,4 +1,4 @@ -; RUN: opt %loadPolly -polly-codegen -analyze < %s | FileCheck %s +; RUN: opt %loadPolly -polly-ast -analyze < %s | FileCheck %s ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s -check-prefix=CHECK-CODE ; void f(long A[], long N) { @@ -31,6 +31,6 @@ ret void } -; CHECK: Create LLVM-IR from SCoPs' for region: 'next => polly.merge_new_and_old' +; CHECK: :: isl ast :: f :: next => return ; CHECK-CODE: polly.split_new_and_old ; CHECK-CODE: polly.merge_new_and_old Index: test/Isl/CodeGen/simple_loop_non_single_exit_2.ll =================================================================== --- test/Isl/CodeGen/simple_loop_non_single_exit_2.ll +++ test/Isl/CodeGen/simple_loop_non_single_exit_2.ll @@ -1,4 +1,4 @@ -; RUN: opt %loadPolly -polly-codegen -analyze < %s | FileCheck %s +; RUN: opt %loadPolly -polly-ast -analyze < %s | FileCheck %s ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s -check-prefix=CHECK-CODE ; void f(long A[], long N) { @@ -32,6 +32,6 @@ ret void } -; CHECK: Create LLVM-IR from SCoPs' for region: 'for.i => return' +; CHECK: :: isl ast :: f :: next => return ; CHECK-CODE: polly.split_new_and_old ; CHECK-CODE: polly.merge_new_and_old Index: test/Isl/CodeGen/simple_non_single_entry.ll =================================================================== --- test/Isl/CodeGen/simple_non_single_entry.ll +++ test/Isl/CodeGen/simple_non_single_entry.ll @@ -1,4 +1,4 @@ -; RUN: opt %loadPolly -polly-codegen -analyze < %s | FileCheck %s +; RUN: opt %loadPolly -polly-ast -analyze < %s | FileCheck %s ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s -check-prefix=CHECK-CODE ; void f(long A[], long N) { @@ -67,6 +67,6 @@ ret void } -; CHECK: Create LLVM-IR from SCoPs' for region: 'next => polly.merge_new_and_old' +; CHECK: :: isl ast :: f :: next => for.i ; CHECK-CODE: polly.split_new_and_old ; CHECK-CODE: polly.merge_new_and_old Index: test/Isl/CodeGen/single_loop_zero_iterations.ll =================================================================== --- test/Isl/CodeGen/single_loop_zero_iterations.ll +++ test/Isl/CodeGen/single_loop_zero_iterations.ll @@ -64,5 +64,4 @@ ret i32 %retval.0 } -; SCALAR: for region: 'for.cond => for.end' in function 'main': ; SCALAR-NOT: Stmt_for_body(0); Index: test/Isl/CodeGen/two-scops-in-row.ll =================================================================== --- test/Isl/CodeGen/two-scops-in-row.ll +++ test/Isl/CodeGen/two-scops-in-row.ll @@ -3,6 +3,9 @@ ; RUN: opt %loadPolly -polly-codegen -polly-ignore-aliasing -disable-output < %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +; SCALAR: if (1) +; SCALAR: Stmt_for_0(0); + ; SCALAR: if ( ; SCALAR: { ; SCALAR: Stmt_for_1(0); @@ -10,10 +13,6 @@ ; SCALAR: Stmt_for_1(c0); ; SCALAR: } -; SCALAR: if (1) -; SCALAR: Stmt_for_0(0); - - define void @foo(i32* %A) { entry: %Scalar0 = alloca i32 Index: test/ScopInfo/aliasing_many_parameters_not_all_involved.ll =================================================================== --- test/ScopInfo/aliasing_many_parameters_not_all_involved.ll +++ test/ScopInfo/aliasing_many_parameters_not_all_involved.ll @@ -4,11 +4,9 @@ ; Check that we allow this SCoP even though it has 10 parameters involved in posisbly aliasing accesses. ; However, only 7 are involved in accesses through B, 8 through C and none in accesses through A. ; -; MAX8-LABEL: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond => for.end' in function 'jd': -; MAX8: Function: jd - -; MAX7-LABEL: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond => for.end' in function 'jd': -; MAX7: Invalid Scop! +; MAX8: Function: jd +; +; MAX7-NOT: Function: jd ; ; void jd(int *A, int *B, int *C, long p1, long p2, long p3, long p4, long p5, ; long p6, long p7, long p8, long p9, long p10) { Index: test/ScopInfo/cond_in_loop.ll =================================================================== --- test/ScopInfo/cond_in_loop.ll +++ test/ScopInfo/cond_in_loop.ll @@ -44,6 +44,5 @@ ret void } -; CHECK-LABEL: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'bb => return' in function 'f': -; CHECK-NEXT: Function: f +; CHECK: Function: f ; CHECK-NEXT: Region: %bb---%return Index: test/ScopInfo/integers.ll =================================================================== --- test/ScopInfo/integers.ll +++ test/ScopInfo/integers.ll @@ -14,7 +14,8 @@ store i1024 %indvar, i1024* %a, align 8 %indvar.next = add nsw i1024 %indvar, 1 %exitcond = icmp eq i1024 %indvar, 123456000000000000000000000 -; CHECK: 'bb => return' in function 'f' +; CHECK: Function: f +; CHECK: Region: %bb---%return ; CHECK: i0 <= 123456000000000000000000000 br i1 %exitcond, label %return, label %bb @@ -33,7 +34,8 @@ store i32 %indvar, i32* %scevgep, align 8 %indvar.next = add nsw i32 %indvar, 1 %exitcond = icmp eq i32 %indvar, 123456 -; CHECK: 'bb => return' in function 'f2' +; CHECK: Function: f2 +; CHECK: Region: %bb---%return ; CHECK: i0 <= 123456 br i1 %exitcond, label %return, label %bb @@ -53,7 +55,8 @@ %indvar.next = add nsw i32 %indvar, 1 %sub = sub i32 %n, 123456 %exitcond = icmp eq i32 %indvar, %sub -; CHECK: 'bb => return' in function 'f3' +; CHECK: Function: f3 +; CHECK: Region: %bb---%return ; CHECK: -123456 br i1 %exitcond, label %return, label %bb @@ -72,7 +75,8 @@ store i1024 %indvar, i1024* %scevgep, align 8 %indvar.next = add nsw i1024 %indvar, 1 %sub = sub i1024 %n, 123456000000000000000000000000000000 -; CHECK: 'bb => return' in function 'f4' +; CHECK: Function: f4 +; CHECK: Region: %bb---%return ; CHECK: -123456000000000000000000000000000000 %exitcond = icmp eq i1024 %indvar, %sub br i1 %exitcond, label %return, label %bb @@ -91,7 +95,8 @@ store i1023 %indvar, i1023* %scevgep, align 8 %indvar.next = add nsw i1023 %indvar, 1 %sub = sub i1023 %n, 123456000000000000000000000000000000 -; CHECK: 'bb => return' in function 'f5' +; CHECK: Function: f5 +; CHECK: Region: %bb---%return ; CHECK: -123456000000000000000000000000000000 %exitcond = icmp eq i1023 %indvar, %sub br i1 %exitcond, label %return, label %bb @@ -111,7 +116,8 @@ store i3 %indvar, i3* %scevgep, align 8 %indvar.next = add nsw i3 %indvar, 1 %sub = sub i3 %n, 3 -; CHECK: 'bb => return' in function 'f6' +; CHECK: Function: f6 +; CHECK: Region: %bb---%return ; CHECK: -3 %exitcond = icmp eq i3 %indvar, %sub br i1 %exitcond, label %return, label %bb Index: test/ScopInfo/undef_in_cond.ll =================================================================== --- test/ScopInfo/undef_in_cond.ll +++ test/ScopInfo/undef_in_cond.ll @@ -19,4 +19,4 @@ ret void } -; CHECK: Invalid Scop! +; CHECK-NOT: Statements