Index: include/polly/LinkAllPasses.h =================================================================== --- include/polly/LinkAllPasses.h +++ include/polly/LinkAllPasses.h @@ -43,7 +43,7 @@ llvm::Pass *createJSONImporterPass(); llvm::Pass *createPollyCanonicalizePass(); llvm::Pass *createPolyhedralInfoPass(); -llvm::Pass *createScopDetectionPass(); +llvm::Pass *createScopDetectionWrapperPassPass(); llvm::Pass *createScopInfoRegionPassPass(); llvm::Pass *createScopInfoWrapperPassPass(); llvm::Pass *createIslAstInfoPass(); @@ -78,7 +78,7 @@ polly::createDOTViewerPass(); polly::createJSONExporterPass(); polly::createJSONImporterPass(); - polly::createScopDetectionPass(); + polly::createScopDetectionWrapperPassPass(); polly::createScopInfoRegionPassPass(); polly::createPollyCanonicalizePass(); polly::createPolyhedralInfoPass(); Index: include/polly/PolyhedralInfo.h =================================================================== --- include/polly/PolyhedralInfo.h +++ include/polly/PolyhedralInfo.h @@ -27,7 +27,7 @@ namespace polly { class Scop; -class ScopInfoWrapperPass; +class ScopInfo; class DependenceInfoWrapperPass; class PolyhedralInfo : public llvm::FunctionPass { @@ -87,7 +87,7 @@ bool checkParallel(llvm::Loop *L, __isl_give isl_pw_aff **MinDepDistPtr = nullptr) const; - ScopInfoWrapperPass *SI; + ScopInfo *SI; DependenceInfoWrapperPass *DI; }; Index: include/polly/ScopDetection.h =================================================================== --- include/polly/ScopDetection.h +++ include/polly/ScopDetection.h @@ -119,7 +119,7 @@ //===----------------------------------------------------------------------===// /// Pass to detect the maximal static control parts (Scops) of a /// function. -class ScopDetection : public FunctionPass { +class ScopDetection { public: typedef SetVector RegionSet; @@ -198,16 +198,14 @@ private: //===--------------------------------------------------------------------===// - ScopDetection(const ScopDetection &) = delete; - const ScopDetection &operator=(const ScopDetection &) = delete; - /// Analysis passes used. + /// Analyses used //@{ - const DominatorTree *DT; - ScalarEvolution *SE; - LoopInfo *LI; - RegionInfo *RI; - AliasAnalysis *AA; + const DominatorTree &DT; + ScalarEvolution &SE; + LoopInfo &LI; + RegionInfo &RI; + AliasAnalysis &AA; //@} /// Map to remember detection contexts for all regions. @@ -527,16 +525,16 @@ Args &&... Arguments) const; public: - static char ID; - explicit ScopDetection(); + ScopDetection(Function &F, const DominatorTree &DT, ScalarEvolution &SE, + LoopInfo &LI, RegionInfo &RI, AliasAnalysis &AA); /// Get the RegionInfo stored in this pass. /// /// This was added to give the DOT printer easy access to this information. - RegionInfo *getRI() const { return RI; } + RegionInfo *getRI() const { return &RI; } /// Get the LoopInfo stored in this pass. - LoopInfo *getLI() const { return LI; } + LoopInfo *getLI() const { return &LI; } /// Is the region is the maximum region of a Scop? /// @@ -598,14 +596,6 @@ /// @param R The Region to verify. void verifyRegion(const Region &R) const; - /// @name FunctionPass interface - //@{ - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory(); - virtual bool runOnFunction(Function &F); - virtual void print(raw_ostream &OS, const Module *) const; - //@} - /// Count the number of loops and the maximal loop depth in @p R. /// /// @param R The region to check @@ -619,11 +609,40 @@ unsigned MinProfitableTrips); }; +struct ScopAnalysis : public AnalysisInfoMixin { + static AnalysisKey Key; + using Result = ScopDetection; + Result run(Function &F, FunctionAnalysisManager &FAM); +}; + +struct ScopAnalysisPrinterPass : public PassInfoMixin { + ScopAnalysisPrinterPass(raw_ostream &O) : Stream(O) {} + PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); + raw_ostream &Stream; +}; + +struct ScopDetectionWrapperPass : public FunctionPass { + static char ID; + std::unique_ptr Result; + + ScopDetectionWrapperPass(); + /// @name FunctionPass interface + //@{ + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual void releaseMemory(); + virtual bool runOnFunction(Function &F); + virtual void print(raw_ostream &OS, const Module *) const; + //@} + + ScopDetection &getSD() { return *Result; } + const ScopDetection &getSD() const { return *Result; } +}; + } // end namespace polly namespace llvm { class PassRegistry; -void initializeScopDetectionPass(llvm::PassRegistry &); +void initializeScopDetectionWrapperPassPass(llvm::PassRegistry &); } // namespace llvm #endif Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -23,6 +23,7 @@ #include "llvm/ADT/MapVector.h" #include "llvm/Analysis/RegionPass.h" +#include "llvm/IR/PassManager.h" #include "isl/aff.h" #include "isl/ctx.h" #include "isl/set.h" @@ -1542,6 +1543,9 @@ /// The underlying Region. Region &R; + /// The name of the SCoP (identical to the regions name) + std::string name; + // Access functions of the SCoP. // // This owns all the MemoryAccess objects of the Scop created in this pass. @@ -2171,6 +2175,8 @@ /// could be executed. bool isEmpty() const { return Stmts.empty(); } + const StringRef getName() const { return name; } + typedef ArrayInfoSetTy::iterator array_iterator; typedef ArrayInfoSetTy::const_iterator const_array_iterator; typedef iterator_range array_range; @@ -2732,16 +2738,7 @@ void getAnalysisUsage(AnalysisUsage &AU) const override; }; -//===----------------------------------------------------------------------===// -/// The legacy pass manager's analysis pass to compute scop information -/// for the whole function. -/// -/// This pass will maintain a map of the maximal region within a scop to its -/// scop object for all the feasible scops present in a function. -/// This pass is an alternative to the ScopInfoRegionPass in order to avoid a -/// region pass manager. -class ScopInfoWrapperPass : public FunctionPass { - +class ScopInfo { public: using RegionToScopMapTy = DenseMap>; using iterator = RegionToScopMapTy::iterator; @@ -2753,10 +2750,9 @@ RegionToScopMapTy RegionToScopMap; public: - static char ID; // Pass identification, replacement for typeid - - ScopInfoWrapperPass() : FunctionPass(ID) {} - ~ScopInfoWrapperPass() {} + ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE, + LoopInfo &LI, AliasAnalysis &AA, DominatorTree &DT, + AssumptionCache &AC); /// Get the Scop object for the given Region /// @@ -2775,11 +2771,45 @@ iterator end() { return RegionToScopMap.end(); } const_iterator begin() const { return RegionToScopMap.begin(); } const_iterator end() const { return RegionToScopMap.end(); } + bool empty() const { return RegionToScopMap.empty(); } +}; + +struct ScopInfoAnalysis : public AnalysisInfoMixin { + static AnalysisKey Key; + using Result = ScopInfo; + Result run(Function &, FunctionAnalysisManager &); +}; + +struct ScopInfoPrinterPass : public PassInfoMixin { + ScopInfoPrinterPass(raw_ostream &O) : Stream(O) {} + PreservedAnalyses run(Function &, FunctionAnalysisManager &); + raw_ostream &Stream; +}; + +//===----------------------------------------------------------------------===// +/// The legacy pass manager's analysis pass to compute scop information +/// for the whole function. +/// +/// This pass will maintain a map of the maximal region within a scop to its +/// scop object for all the feasible scops present in a function. +/// This pass is an alternative to the ScopInfoRegionPass in order to avoid a +/// region pass manager. +class ScopInfoWrapperPass : public FunctionPass { + std::unique_ptr Result; + +public: + ScopInfoWrapperPass() : FunctionPass(ID) {} + ~ScopInfoWrapperPass() = default; + + static char ID; // Pass identification, replacement for typeid + + ScopInfo *getSI() { return Result.get(); } + const ScopInfo *getSI() const { return Result.get(); } /// Calculate all the polyhedral scops for a given function. bool runOnFunction(Function &F) override; - void releaseMemory() override { RegionToScopMap.clear(); } + void releaseMemory() override { Result.reset(); } void print(raw_ostream &O, const Module *M = nullptr) const override; Index: include/polly/ScopPass.h =================================================================== --- include/polly/ScopPass.h +++ include/polly/ScopPass.h @@ -18,12 +18,82 @@ #ifndef POLLY_SCOP_PASS_H #define POLLY_SCOP_PASS_H +#include "polly/ScopInfo.h" +#include "llvm/ADT/PriorityWorklist.h" #include "llvm/Analysis/RegionPass.h" +#include "llvm/IR/PassManager.h" using namespace llvm; namespace polly { class Scop; +struct ScopStandardAnalysisResults; + +using ScopAnalysisManager = + AnalysisManager; +using ScopAnalysisManagerFunctionProxy = + InnerAnalysisManagerProxy; +using FunctionAnalysisManagerScopProxy = + OuterAnalysisManagerProxy; +} // namespace polly + +namespace llvm { +using polly::Scop; +using polly::ScopInfo; +using polly::ScopAnalysisManager; +using polly::ScopStandardAnalysisResults; +using polly::ScopAnalysisManagerFunctionProxy; + +template <> +class InnerAnalysisManagerProxy::Result { +public: + explicit Result(ScopAnalysisManager &InnerAM, ScopInfo &SI) + : InnerAM(&InnerAM), SI(&SI) {} + Result(Result &&R) : InnerAM(std::move(R.InnerAM)), SI(R.SI) { + R.InnerAM = nullptr; + } + Result &operator=(Result &&RHS) { + InnerAM = RHS.InnerAM; + SI = RHS.SI; + RHS.InnerAM = nullptr; + return *this; + } + ~Result() { + if (!InnerAM) + return; + InnerAM->clear(); + } + + ScopAnalysisManager &getManager() { return *InnerAM; } + + bool invalidate(Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv); + +private: + ScopAnalysisManager *InnerAM; + ScopInfo *SI; +}; + +template <> +InnerAnalysisManagerProxy::Result +InnerAnalysisManagerProxy::run( + Function &F, FunctionAnalysisManager &FAM); + +template <> +PreservedAnalyses +PassManager::run( + Scop &InitialS, ScopAnalysisManager &AM, ScopStandardAnalysisResults &); +extern template class PassManager; +extern template class InnerAnalysisManagerProxy; +extern template class OuterAnalysisManagerProxy; +} // namespace llvm + +namespace polly { +using ScopPassManager = + PassManager; /// ScopPass - This class adapts the RegionPass interface to allow convenient /// creation of passes that operate on the Polly IR. Instead of overriding @@ -52,6 +122,57 @@ void print(raw_ostream &OS, const Module *) const override; }; +struct ScopStandardAnalysisResults { + DominatorTree &DT; + ScalarEvolution &SE; + LoopInfo &LI; + RegionInfo &RI; +}; + +template +class FunctionToScopPassAdaptor + : public PassInfoMixin> { +public: + explicit FunctionToScopPassAdaptor(ScopPassT Pass) : Pass(std::move(Pass)) {} + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { + PreservedAnalyses PA = PreservedAnalyses::all(); + auto &Scops = AM.getResult(F); + if (Scops.empty()) + return PA; + + ScopAnalysisManager &SAM = + AM.getResult(F).getManager(); + + ScopStandardAnalysisResults AR = {AM.getResult(F), + AM.getResult(F), + AM.getResult(F), + AM.getResult(F)}; + + for (auto &S : Scops) { + if (auto *scop = S.second.get()) { + PreservedAnalyses PassPA = Pass.run(*scop, SAM, AR); + + SAM.invalidate(*scop, PassPA); + PA.intersect(std::move(PassPA)); + } + } + + PA.preserveSet>(); + PA.preserve(); + return PA; + } + +private: + ScopPassT Pass; +}; // namespace polly + +template +FunctionToScopPassAdaptor +createFunctionToScopPassAdaptor(ScopPassT Pass) { + return FunctionToScopPassAdaptor(std::move(Pass)); +} + } // namespace polly #endif Index: lib/Analysis/DependenceInfo.cpp =================================================================== --- lib/Analysis/DependenceInfo.cpp +++ lib/Analysis/DependenceInfo.cpp @@ -982,7 +982,7 @@ } bool DependenceInfoWrapperPass::runOnFunction(Function &F) { - auto &SI = getAnalysis(); + auto &SI = *getAnalysis().getSI(); for (auto &It : SI) { assert(It.second && "Invalid SCoP object!"); recomputeDependences(It.second.get(), Dependences::AL_Access); Index: lib/Analysis/PolyhedralInfo.cpp =================================================================== --- lib/Analysis/PolyhedralInfo.cpp +++ lib/Analysis/PolyhedralInfo.cpp @@ -53,7 +53,7 @@ bool PolyhedralInfo::runOnFunction(Function &F) { DI = &getAnalysis(); - SI = &getAnalysis(); + SI = getAnalysis().getSI(); return false; } Index: lib/Analysis/ScopDetection.cpp =================================================================== --- lib/Analysis/ScopDetection.cpp +++ lib/Analysis/ScopDetection.cpp @@ -44,10 +44,10 @@ // //===----------------------------------------------------------------------===// -#include "polly/ScopDetection.h" #include "polly/CodeGen/CodeGeneration.h" #include "polly/LinkAllPasses.h" #include "polly/Options.h" +#include "polly/ScopDetection.h" #include "polly/ScopDetectionDiagnostic.h" #include "polly/Support/SCEVValidator.h" #include "polly/Support/ScopLocation.h" @@ -225,6 +225,9 @@ STATISTIC(MaxNumLoopsInProfScop, "Maximal number of loops in scops (profitable scops only)"); +static void updateLoopCountStatistic(ScopDetection::LoopStats Stats, + bool OnlyProfitable); + class DiagnosticScopFound : public DiagnosticInfo { private: static int PluginDiagnosticKind; @@ -266,10 +269,55 @@ //===----------------------------------------------------------------------===// // ScopDetection. -ScopDetection::ScopDetection() : FunctionPass(ID) { - // Disable runtime alias checks if we ignore aliasing all together. - if (IgnoreAliasing) - PollyUseRuntimeAliasChecks = false; +ScopDetection::ScopDetection(Function &F, const DominatorTree &DT, + ScalarEvolution &SE, LoopInfo &LI, RegionInfo &RI, + AliasAnalysis &AA) + : DT(DT), SE(SE), LI(LI), RI(RI), AA(AA) { + + if (!PollyProcessUnprofitable && LI.empty()) + return; + + Region *TopRegion = RI.getTopLevelRegion(); + + if (OnlyFunction != "" && !F.getName().count(OnlyFunction)) + return; + + if (!isValidFunction(F)) + return; + + findScops(*TopRegion); + + NumScopRegions += ValidRegions.size(); + + // Prune non-profitable regions. + for (auto &DIt : DetectionContextMap) { + auto &DC = DIt.getSecond(); + if (DC.Log.hasErrors()) + continue; + if (!ValidRegions.count(&DC.CurRegion)) + continue; + LoopStats Stats = countBeneficialLoops(&DC.CurRegion, SE, LI, 0); + updateLoopCountStatistic(Stats, false /* OnlyProfitable */); + if (isProfitableRegion(DC)) { + updateLoopCountStatistic(Stats, true /* OnlyProfitable */); + continue; + } + + ValidRegions.remove(&DC.CurRegion); + } + + NumProfScopRegions += ValidRegions.size(); + NumLoopsOverall += countBeneficialLoops(TopRegion, SE, LI, 0).NumLoops; + + // Only makes sense when we tracked errors. + if (PollyTrackFailures) + emitMissedRemarks(F); + + if (ReportLevel) + printLocations(F); + + assert(ValidRegions.size() <= DetectionContextMap.size() && + "Cached more results than valid regions"); } template @@ -300,7 +348,7 @@ DetectionContextMap.erase(getBBPairForRegion(&R)); const auto &It = DetectionContextMap.insert(std::make_pair( getBBPairForRegion(&R), - DetectionContext(const_cast(R), *AA, false /*verifying*/))); + DetectionContext(const_cast(R), AA, false /*verifying*/))); DetectionContext &Context = It.first->second; return isValidRegion(Context); } @@ -333,7 +381,7 @@ // are accesses that depend on the iteration count. for (BasicBlock *BB : AR->blocks()) { - Loop *L = LI->getLoopFor(BB); + Loop *L = LI.getLoopFor(BB); if (AR->contains(L)) Context.BoxedLoopsSet.insert(L); } @@ -358,7 +406,7 @@ if (Context.RequiredILS.count(Load)) continue; - if (!isHoistableLoad(Load, CurRegion, *LI, *SE, *DT)) + if (!isHoistableLoad(Load, CurRegion, LI, SE, DT)) return false; for (auto NonAffineRegion : Context.NonAffineSubRegionSet) { @@ -381,9 +429,9 @@ bool ScopDetection::involvesMultiplePtrs(const SCEV *S0, const SCEV *S1, Loop *Scope) const { SetVector Values; - findValues(S0, *SE, Values); + findValues(S0, SE, Values); if (S1) - findValues(S1, *SE, Values); + findValues(S1, SE, Values); SmallPtrSet PtrVals; for (auto *V : Values) { @@ -393,18 +441,18 @@ if (!V->getType()->isPointerTy()) continue; - auto *PtrSCEV = SE->getSCEVAtScope(V, Scope); + auto *PtrSCEV = SE.getSCEVAtScope(V, Scope); if (isa(PtrSCEV)) continue; - auto *BasePtr = dyn_cast(SE->getPointerBase(PtrSCEV)); + auto *BasePtr = dyn_cast(SE.getPointerBase(PtrSCEV)); if (!BasePtr) return true; auto *BasePtrVal = BasePtr->getValue(); if (PtrVals.insert(BasePtrVal).second) { for (auto *PtrVal : PtrVals) - if (PtrVal != BasePtrVal && !AA->isNoAlias(PtrVal, BasePtrVal)) + if (PtrVal != BasePtrVal && !AA.isNoAlias(PtrVal, BasePtrVal)) return true; } } @@ -416,7 +464,7 @@ DetectionContext &Context) const { InvariantLoadsSetTy AccessILS; - if (!isAffineExpr(&Context.CurRegion, Scope, S, *SE, &AccessILS)) + if (!isAffineExpr(&Context.CurRegion, Scope, S, SE, &AccessILS)) return false; if (!onlyValidRequiredInvariantLoads(AccessILS, Context)) @@ -428,8 +476,8 @@ bool ScopDetection::isValidSwitch(BasicBlock &BB, SwitchInst *SI, Value *Condition, bool IsLoopBranch, DetectionContext &Context) const { - Loop *L = LI->getLoopFor(&BB); - const SCEV *ConditionSCEV = SE->getSCEVAtScope(Condition, L); + Loop *L = LI.getLoopFor(&BB); + const SCEV *ConditionSCEV = SE.getSCEVAtScope(Condition, L); if (IsLoopBranch && L->isLoopLatch(&BB)) return false; @@ -442,7 +490,7 @@ return true; if (AllowNonAffineSubRegions && - addOverApproximatedRegion(RI->getRegionFor(&BB), Context)) + addOverApproximatedRegion(RI.getRegionFor(&BB), Context)) return true; return invalid(Context, /*Assert=*/true, &BB, @@ -470,7 +518,7 @@ // Non constant conditions of branches need to be ICmpInst. if (!isa(Condition)) { if (!IsLoopBranch && AllowNonAffineSubRegions && - addOverApproximatedRegion(RI->getRegionFor(&BB), Context)) + addOverApproximatedRegion(RI.getRegionFor(&BB), Context)) return true; return invalid(Context, /*Assert=*/true, BI, &BB); } @@ -482,14 +530,14 @@ isa(ICmp->getOperand(1))) return invalid(Context, /*Assert=*/true, &BB, ICmp); - Loop *L = LI->getLoopFor(&BB); - const SCEV *LHS = SE->getSCEVAtScope(ICmp->getOperand(0), L); - const SCEV *RHS = SE->getSCEVAtScope(ICmp->getOperand(1), L); + Loop *L = LI.getLoopFor(&BB); + const SCEV *LHS = SE.getSCEVAtScope(ICmp->getOperand(0), L); + const SCEV *RHS = SE.getSCEVAtScope(ICmp->getOperand(1), L); // If unsigned operations are not allowed try to approximate the region. if (ICmp->isUnsigned() && !PollyAllowUnsignedOperations) return !IsLoopBranch && AllowNonAffineSubRegions && - addOverApproximatedRegion(RI->getRegionFor(&BB), Context); + addOverApproximatedRegion(RI.getRegionFor(&BB), Context); // Check for invalid usage of different pointers in one expression. if (ICmp->isEquality() && involvesMultiplePtrs(LHS, nullptr, L) && @@ -504,7 +552,7 @@ return true; if (!IsLoopBranch && AllowNonAffineSubRegions && - addOverApproximatedRegion(RI->getRegionFor(&BB), Context)) + addOverApproximatedRegion(RI.getRegionFor(&BB), Context)) return true; if (IsLoopBranch) @@ -565,7 +613,7 @@ return false; if (AllowModrefCall) { - switch (AA->getModRefBehavior(CalledFunction)) { + switch (AA.getModRefBehavior(CalledFunction)) { case FMRB_UnknownModRefBehavior: return false; case FMRB_DoesNotAccessMemory: @@ -583,11 +631,11 @@ // Bail if a pointer argument has a base address not known to // ScalarEvolution. Note that a zero pointer is acceptable. - auto *ArgSCEV = SE->getSCEVAtScope(Arg, LI->getLoopFor(CI.getParent())); + auto *ArgSCEV = SE.getSCEVAtScope(Arg, LI.getLoopFor(CI.getParent())); if (ArgSCEV->isZero()) continue; - auto *BP = dyn_cast(SE->getPointerBase(ArgSCEV)); + auto *BP = dyn_cast(SE.getPointerBase(ArgSCEV)); if (!BP) return false; @@ -614,7 +662,7 @@ return true; // The closest loop surrounding the call instruction. - Loop *L = LI->getLoopFor(II.getParent()); + Loop *L = LI.getLoopFor(II.getParent()); // The access function and base pointer for memory intrinsics. const SCEV *AF; @@ -624,25 +672,25 @@ // Memory intrinsics that can be represented are supported. case llvm::Intrinsic::memmove: case llvm::Intrinsic::memcpy: - AF = SE->getSCEVAtScope(cast(II).getSource(), L); + AF = SE.getSCEVAtScope(cast(II).getSource(), L); if (!AF->isZero()) { - BP = dyn_cast(SE->getPointerBase(AF)); + BP = dyn_cast(SE.getPointerBase(AF)); // Bail if the source pointer is not valid. if (!isValidAccess(&II, AF, BP, Context)) return false; } // Fall through case llvm::Intrinsic::memset: - AF = SE->getSCEVAtScope(cast(II).getDest(), L); + AF = SE.getSCEVAtScope(cast(II).getDest(), L); if (!AF->isZero()) { - BP = dyn_cast(SE->getPointerBase(AF)); + BP = dyn_cast(SE.getPointerBase(AF)); // Bail if the destination pointer is not valid. if (!isValidAccess(&II, AF, BP, Context)) return false; } // Bail if the length is not affine. - if (!isAffine(SE->getSCEVAtScope(cast(II).getLength(), L), L, + if (!isAffine(SE.getSCEVAtScope(cast(II).getLength(), L), L, Context)) return false; @@ -722,7 +770,7 @@ SmallVector Terms; for (const auto &Pair : Context.Accesses[BasePointer]) { std::vector MaxTerms; - SCEVRemoveMax::rewrite(Pair.second, *SE, &MaxTerms); + SCEVRemoveMax::rewrite(Pair.second, SE, &MaxTerms); if (MaxTerms.size() > 0) { Terms.insert(Terms.begin(), MaxTerms.begin(), MaxTerms.end()); continue; @@ -738,7 +786,7 @@ if (auto *AF = dyn_cast(Pair.second)) { for (auto Op : AF->operands()) { if (auto *AF2 = dyn_cast(Op)) - SE->collectParametricTerms(AF2, Terms); + SE.collectParametricTerms(AF2, Terms); if (auto *AF2 = dyn_cast(Op)) { SmallVector Operands; @@ -756,12 +804,12 @@ } } if (Operands.size()) - Terms.push_back(SE->getMulExpr(Operands)); + Terms.push_back(SE.getMulExpr(Operands)); } } } if (Terms.empty()) - SE->collectParametricTerms(Pair.second, Terms); + SE.collectParametricTerms(Pair.second, Terms); } return Terms; } @@ -781,7 +829,7 @@ auto *V = dyn_cast(Unknown->getValue()); if (auto *Load = dyn_cast(V)) { if (Context.CurRegion.contains(Load) && - isHoistableLoad(Load, CurRegion, *LI, *SE, *DT)) + isHoistableLoad(Load, CurRegion, LI, SE, DT)) Context.RequiredILS.insert(Load); continue; } @@ -828,11 +876,11 @@ for (const auto &Pair : Context.Accesses[BasePointer]) { const Instruction *Insn = Pair.first; auto *AF = Pair.second; - AF = SCEVRemoveMax::rewrite(AF, *SE); + AF = SCEVRemoveMax::rewrite(AF, SE); bool IsNonAffine = false; TempMemoryAccesses.insert(std::make_pair(Insn, MemAcc(Insn, Shape))); MemAcc *Acc = &TempMemoryAccesses.find(Insn)->second; - auto *Scope = LI->getLoopFor(Insn->getParent()); + auto *Scope = LI.getLoopFor(Insn->getParent()); if (!AF) { if (isAffine(Pair.second, Scope, Context)) @@ -840,8 +888,8 @@ else IsNonAffine = true; } else { - SE->computeAccessFunctions(AF, Acc->DelinearizedSubscripts, - Shape->DelinearizedSizes); + SE.computeAccessFunctions(AF, Acc->DelinearizedSubscripts, + Shape->DelinearizedSizes); if (Acc->DelinearizedSubscripts.size() == 0) IsNonAffine = true; for (const SCEV *S : Acc->DelinearizedSubscripts) @@ -874,8 +922,8 @@ auto Terms = getDelinearizationTerms(Context, BasePointer); - SE->findArrayDimensions(Terms, Shape->DelinearizedSizes, - Context.ElementSize[BasePointer]); + SE.findArrayDimensions(Terms, Shape->DelinearizedSizes, + Context.ElementSize[BasePointer]); if (!hasValidArraySizes(Context, Shape->DelinearizedSizes, BasePointer, Scope)) @@ -923,15 +971,15 @@ if (!isInvariant(*BV, Context.CurRegion, Context)) return invalid(Context, /*Assert=*/true, BV, Inst); - AF = SE->getMinusSCEV(AF, BP); + AF = SE.getMinusSCEV(AF, BP); const SCEV *Size; if (!isa(Inst)) { - Size = SE->getElementSize(Inst); + Size = SE.getElementSize(Inst); } else { auto *SizeTy = - SE->getEffectiveSCEVType(PointerType::getInt8PtrTy(SE->getContext())); - Size = SE->getConstant(SizeTy, 8); + SE.getEffectiveSCEVType(PointerType::getInt8PtrTy(SE.getContext())); + Size = SE.getConstant(SizeTy, 8); } if (Context.ElementSize[BP]) { @@ -939,7 +987,7 @@ return invalid(Context, /*Assert=*/true, Inst, BV); - Context.ElementSize[BP] = SE->getSMinExpr(Size, Context.ElementSize[BP]); + Context.ElementSize[BP] = SE.getSMinExpr(Size, Context.ElementSize[BP]); } else { Context.ElementSize[BP] = Size; } @@ -951,7 +999,7 @@ if (Context.BoxedLoopsSet.count(L)) IsVariantInNonAffineLoop = true; - auto *Scope = LI->getLoopFor(Inst->getParent()); + auto *Scope = LI.getLoopFor(Inst->getParent()); bool IsAffine = !IsVariantInNonAffineLoop && isAffine(AF, Scope, Context); // Do not try to delinearize memory intrinsics and force them to be affine. if (isa(Inst) && !IsAffine) { @@ -962,7 +1010,7 @@ if (!IsAffine) Context.NonAffineAccesses.insert( - std::make_pair(BP, LI->getLoopFor(Inst->getParent()))); + std::make_pair(BP, LI.getLoopFor(Inst->getParent()))); } else if (!AllowNonAffine && !IsAffine) { return invalid(Context, /*Assert=*/true, AF, Inst, BV); @@ -990,7 +1038,7 @@ Instruction *Inst = dyn_cast(Ptr.getValue()); if (Inst && Context.CurRegion.contains(Inst)) { auto *Load = dyn_cast(Inst); - if (Load && isHoistableLoad(Load, Context.CurRegion, *LI, *SE, *DT)) { + if (Load && isHoistableLoad(Load, Context.CurRegion, LI, SE, DT)) { Context.RequiredILS.insert(Load); continue; } @@ -1012,11 +1060,11 @@ bool ScopDetection::isValidMemoryAccess(MemAccInst Inst, DetectionContext &Context) const { Value *Ptr = Inst.getPointerOperand(); - Loop *L = LI->getLoopFor(Inst->getParent()); - const SCEV *AccessFunction = SE->getSCEVAtScope(Ptr, L); + Loop *L = LI.getLoopFor(Inst->getParent()); + const SCEV *AccessFunction = SE.getSCEVAtScope(Ptr, L); const SCEVUnknown *BasePointer; - BasePointer = dyn_cast(SE->getPointerBase(AccessFunction)); + BasePointer = dyn_cast(SE.getPointerBase(AccessFunction)); return isValidAccess(Inst, AccessFunction, BasePointer, Context); } @@ -1029,7 +1077,7 @@ if (!OpInst) continue; - if (isErrorBlock(*OpInst->getParent(), Context.CurRegion, *LI, *DT)) + if (isErrorBlock(*OpInst->getParent(), Context.CurRegion, LI, DT)) return false; } @@ -1130,7 +1178,7 @@ return true; if (AllowNonAffineSubLoops && AllowNonAffineSubRegions) { - Region *R = RI->getRegionFor(L->getHeader()); + Region *R = RI.getRegionFor(L->getHeader()); while (R != &Context.CurRegion && !R->contains(L)) R = R->getParent(); @@ -1138,7 +1186,7 @@ return true; } - const SCEV *LoopCount = SE->getBackedgeTakenCount(L); + const SCEV *LoopCount = SE.getBackedgeTakenCount(L); return invalid(Context, /*Assert=*/true, L, LoopCount); } @@ -1199,7 +1247,7 @@ while (ExpandedRegion) { const auto &It = DetectionContextMap.insert(std::make_pair( getBBPairForRegion(ExpandedRegion.get()), - DetectionContext(*ExpandedRegion, *AA, false /*verifying*/))); + DetectionContext(*ExpandedRegion, AA, false /*verifying*/))); DetectionContext &Context = It.first->second; DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n"); // Only expand when we did not collect errors. @@ -1244,9 +1292,9 @@ return LastValidRegion.release(); } -static bool regionWithoutLoops(Region &R, LoopInfo *LI) { +static bool regionWithoutLoops(Region &R, LoopInfo &LI) { for (const BasicBlock *BB : R.blocks()) - if (R.contains(LI->getLoopFor(BB))) + if (R.contains(LI.getLoopFor(BB))) return false; return true; @@ -1267,7 +1315,7 @@ void ScopDetection::findScops(Region &R) { const auto &It = DetectionContextMap.insert(std::make_pair( - getBBPairForRegion(&R), DetectionContext(R, *AA, false /*verifying*/))); + getBBPairForRegion(&R), DetectionContext(R, AA, false /*verifying*/))); DetectionContext &Context = It.first->second; bool RegionIsValid = false; @@ -1326,14 +1374,14 @@ Region &CurRegion = Context.CurRegion; for (const BasicBlock *BB : CurRegion.blocks()) { - Loop *L = LI->getLoopFor(BB); + Loop *L = LI.getLoopFor(BB); if (L && L->getHeader() == BB && CurRegion.contains(L) && (!isValidLoop(L, Context) && !KeepGoing)) return false; } for (BasicBlock *BB : CurRegion.blocks()) { - bool IsErrorBlock = isErrorBlock(*BB, CurRegion, *LI, *DT); + bool IsErrorBlock = isErrorBlock(*BB, CurRegion, LI, DT); // Also check exception blocks (and possibly register them as non-affine // regions). Even though exception blocks are not modeled, we use them @@ -1363,7 +1411,7 @@ return false; for (auto *BB : Context.CurRegion.blocks()) - if (Context.CurRegion.contains(LI->getLoopFor(BB))) + if (Context.CurRegion.contains(LI.getLoopFor(BB))) InstCount += BB->size(); InstCount = InstCount / NumLoops; @@ -1374,7 +1422,7 @@ bool ScopDetection::hasPossiblyDistributableLoop( DetectionContext &Context) const { for (auto *BB : Context.CurRegion.blocks()) { - auto *L = LI->getLoopFor(BB); + auto *L = LI.getLoopFor(BB); if (!Context.CurRegion.contains(L)) continue; if (Context.BoxedLoopsSet.count(L)) @@ -1403,7 +1451,7 @@ return invalid(Context, /*Assert=*/true, &CurRegion); int NumLoops = - countBeneficialLoops(&CurRegion, *SE, *LI, MIN_LOOP_TRIP_COUNT).NumLoops; + countBeneficialLoops(&CurRegion, SE, LI, MIN_LOOP_TRIP_COUNT).NumLoops; int NumAffineLoops = NumLoops - Context.BoxedLoopsSet.size(); // Scops with at least two loops may allow either loop fusion or tiling and @@ -1553,7 +1601,7 @@ // GREY indicates a loop in the control flow. // If the destination dominates the source, it is a natural loop // else, an irreducible control flow in the region is detected. - if (!DT->dominates(SuccBB, CurrBB)) { + if (!DT.dominates(SuccBB, CurrBB)) { // Get debug info of instruction which causes irregular control flow. DbgLoc = TInst->getDebugLoc(); return false; @@ -1570,8 +1618,8 @@ return true; } -void updateLoopCountStatistic(ScopDetection::LoopStats Stats, - bool OnlyProfitable) { +static void updateLoopCountStatistic(ScopDetection::LoopStats Stats, + bool OnlyProfitable) { if (!OnlyProfitable) { NumLoopsInScop += Stats.NumLoops; MaxNumLoopsInScop = @@ -1607,61 +1655,6 @@ } } -bool ScopDetection::runOnFunction(llvm::Function &F) { - LI = &getAnalysis().getLoopInfo(); - RI = &getAnalysis().getRegionInfo(); - if (!PollyProcessUnprofitable && LI->empty()) - return false; - - AA = &getAnalysis().getAAResults(); - SE = &getAnalysis().getSE(); - DT = &getAnalysis().getDomTree(); - Region *TopRegion = RI->getTopLevelRegion(); - - releaseMemory(); - - if (OnlyFunction != "" && !F.getName().count(OnlyFunction)) - return false; - - if (!isValidFunction(F)) - return false; - - findScops(*TopRegion); - - NumScopRegions += ValidRegions.size(); - - // Prune non-profitable regions. - for (auto &DIt : DetectionContextMap) { - auto &DC = DIt.getSecond(); - if (DC.Log.hasErrors()) - continue; - if (!ValidRegions.count(&DC.CurRegion)) - continue; - LoopStats Stats = countBeneficialLoops(&DC.CurRegion, *SE, *LI, 0); - updateLoopCountStatistic(Stats, false /* OnlyProfitable */); - if (isProfitableRegion(DC)) { - updateLoopCountStatistic(Stats, true /* OnlyProfitable */); - continue; - } - - ValidRegions.remove(&DC.CurRegion); - } - - NumProfScopRegions += ValidRegions.size(); - NumLoopsOverall += countBeneficialLoops(TopRegion, *SE, *LI, 0).NumLoops; - - // Only makes sense when we tracked errors. - if (PollyTrackFailures) - emitMissedRemarks(F); - - if (ReportLevel) - printLocations(F); - - assert(ValidRegions.size() <= DetectionContextMap.size() && - "Cached more results than valid regions"); - return false; -} - ScopDetection::DetectionContext * ScopDetection::getDetectionContext(const Region *R) const { auto DCMIt = DetectionContextMap.find(getBBPairForRegion(R)); @@ -1678,7 +1671,7 @@ void polly::ScopDetection::verifyRegion(const Region &R) const { assert(isMaxRegionInScop(R) && "Expect R is a valid region."); - DetectionContext Context(const_cast(R), *AA, true /*verifying*/); + DetectionContext Context(const_cast(R), AA, true /*verifying*/); isValidRegion(Context); } @@ -1690,7 +1683,17 @@ verifyRegion(*R); } -void ScopDetection::getAnalysisUsage(AnalysisUsage &AU) const { +bool ScopDetectionWrapperPass::runOnFunction(llvm::Function &F) { + auto &LI = getAnalysis().getLoopInfo(); + auto &RI = getAnalysis().getRegionInfo(); + auto &AA = getAnalysis().getAAResults(); + auto &SE = getAnalysis().getSE(); + auto &DT = getAnalysis().getDomTree(); + Result.reset(new ScopDetection(F, DT, SE, LI, RI, AA)); + return false; +} + +void ScopDetectionWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); AU.addRequiredTransitive(); AU.addRequired(); @@ -1700,25 +1703,49 @@ AU.setPreservesAll(); } -void ScopDetection::print(raw_ostream &OS, const Module *) const { - for (const Region *R : ValidRegions) +void ScopDetectionWrapperPass::print(raw_ostream &OS, const Module *) const { + for (const Region *R : Result->ValidRegions) OS << "Valid Region for Scop: " << R->getNameStr() << '\n'; OS << "\n"; } -void ScopDetection::releaseMemory() { - ValidRegions.clear(); - DetectionContextMap.clear(); +ScopDetectionWrapperPass::ScopDetectionWrapperPass() : FunctionPass(ID) { + // Disable runtime alias checks if we ignore aliasing all together. + if (IgnoreAliasing) + PollyUseRuntimeAliasChecks = false; +} - // Do not clear the invalid function set. +void ScopDetectionWrapperPass::releaseMemory() { Result.reset(); } + +char ScopDetectionWrapperPass::ID; + +AnalysisKey ScopAnalysis::Key; + +ScopDetection ScopAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { + auto &LI = FAM.getResult(F); + auto &RI = FAM.getResult(F); + auto &AA = FAM.getResult(F); + auto &SE = FAM.getResult(F); + auto &DT = FAM.getResult(F); + return {F, DT, SE, LI, RI, AA}; } -char ScopDetection::ID = 0; +PreservedAnalyses ScopAnalysisPrinterPass::run(Function &F, + FunctionAnalysisManager &FAM) { + auto &SD = FAM.getResult(F); + for (const Region *R : SD.ValidRegions) + Stream << "Valid Region for Scop: " << R->getNameStr() << '\n'; -Pass *polly::createScopDetectionPass() { return new ScopDetection(); } + Stream << "\n"; + return PreservedAnalyses::all(); +} + +Pass *polly::createScopDetectionWrapperPassPass() { + return new ScopDetectionWrapperPass(); +} -INITIALIZE_PASS_BEGIN(ScopDetection, "polly-detect", +INITIALIZE_PASS_BEGIN(ScopDetectionWrapperPass, "polly-detect", "Polly - Detect static control parts (SCoPs)", false, false); INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass); @@ -1726,5 +1753,5 @@ INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass); INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); -INITIALIZE_PASS_END(ScopDetection, "polly-detect", +INITIALIZE_PASS_END(ScopDetectionWrapperPass, "polly-detect", "Polly - Detect static control parts (SCoPs)", false, false) Index: lib/Analysis/ScopGraphPrinter.cpp =================================================================== --- lib/Analysis/ScopGraphPrinter.cpp +++ lib/Analysis/ScopGraphPrinter.cpp @@ -47,6 +47,20 @@ } }; +template <> +struct GraphTraits + : public GraphTraits { + static NodeRef getEntryNode(ScopDetectionWrapperPass *P) { + return GraphTraits::getEntryNode(&P->getSD()); + } + static nodes_iterator nodes_begin(ScopDetectionWrapperPass *P) { + return nodes_iterator::begin(getEntryNode(P)); + } + static nodes_iterator nodes_end(ScopDetectionWrapperPass *P) { + return nodes_iterator::end(getEntryNode(P)); + } +}; + template <> struct DOTGraphTraits : public DefaultDOTGraphTraits { DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} @@ -67,15 +81,19 @@ }; template <> -struct DOTGraphTraits : public DOTGraphTraits { +struct DOTGraphTraits + : public DOTGraphTraits { DOTGraphTraits(bool isSimple = false) : DOTGraphTraits(isSimple) {} - static std::string getGraphName(ScopDetection *SD) { return "Scop Graph"; } + static std::string getGraphName(ScopDetectionWrapperPass *SD) { + return "Scop Graph"; + } std::string getEdgeAttributes(RegionNode *srcNode, GraphTraits::ChildIteratorType CI, - ScopDetection *SD) { + ScopDetectionWrapperPass *P) { RegionNode *destNode = *CI; + auto *SD = &P->getSD(); if (srcNode->isSubRegion() || destNode->isSubRegion()) return ""; @@ -99,9 +117,10 @@ return ""; } - std::string getNodeLabel(RegionNode *Node, ScopDetection *SD) { + std::string getNodeLabel(RegionNode *Node, ScopDetectionWrapperPass *P) { return DOTGraphTraits::getNodeLabel( - Node, reinterpret_cast(SD->getRI()->getTopLevelRegion())); + Node, reinterpret_cast( + P->getSD().getRI()->getTopLevelRegion())); } static std::string escapeString(std::string String) { @@ -169,20 +188,24 @@ O.indent(2 * depth) << "}\n"; } - static void addCustomGraphFeatures(const ScopDetection *SD, - GraphWriter &GW) { + static void + addCustomGraphFeatures(const ScopDetectionWrapperPass *SD, + GraphWriter &GW) { raw_ostream &O = GW.getOStream(); O << "\tcolorscheme = \"paired12\"\n"; - printRegionCluster(SD, SD->getRI()->getTopLevelRegion(), O, 4); + printRegionCluster(&SD->getSD(), SD->getSD().getRI()->getTopLevelRegion(), + O, 4); } }; } // end namespace llvm -struct ScopViewer : public DOTGraphTraitsViewer { +struct ScopViewer + : public DOTGraphTraitsViewer { static char ID; - ScopViewer() : DOTGraphTraitsViewer("scops", ID) {} - bool processFunction(Function &F, ScopDetection &SD) override { + ScopViewer() + : DOTGraphTraitsViewer("scops", ID) {} + bool processFunction(Function &F, ScopDetectionWrapperPass &SD) override { if (ViewFilter != "" && !F.getName().count(ViewFilter)) return false; @@ -190,28 +213,33 @@ return true; // Check that at least one scop was detected. - return std::distance(SD.begin(), SD.end()) > 0; + return std::distance(SD.getSD().begin(), SD.getSD().end()) > 0; } }; char ScopViewer::ID = 0; -struct ScopOnlyViewer : public DOTGraphTraitsViewer { +struct ScopOnlyViewer + : public DOTGraphTraitsViewer { static char ID; ScopOnlyViewer() - : DOTGraphTraitsViewer("scopsonly", ID) {} + : DOTGraphTraitsViewer("scopsonly", ID) {} }; char ScopOnlyViewer::ID = 0; -struct ScopPrinter : public DOTGraphTraitsPrinter { +struct ScopPrinter + : public DOTGraphTraitsPrinter { static char ID; - ScopPrinter() : DOTGraphTraitsPrinter("scops", ID) {} + ScopPrinter() + : DOTGraphTraitsPrinter("scops", ID) {} }; char ScopPrinter::ID = 0; -struct ScopOnlyPrinter : public DOTGraphTraitsPrinter { +struct ScopOnlyPrinter + : public DOTGraphTraitsPrinter { static char ID; ScopOnlyPrinter() - : DOTGraphTraitsPrinter("scopsonly", ID) {} + : DOTGraphTraitsPrinter("scopsonly", ID) { + } }; char ScopOnlyPrinter::ID = 0; Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -17,10 +17,10 @@ // //===----------------------------------------------------------------------===// -#include "polly/ScopInfo.h" #include "polly/LinkAllPasses.h" #include "polly/Options.h" #include "polly/ScopBuilder.h" +#include "polly/ScopInfo.h" #include "polly/Support/GICHelper.h" #include "polly/Support/SCEVValidator.h" #include "polly/Support/ScopHelper.h" @@ -3256,9 +3256,9 @@ Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI, ScopDetection::DetectionContext &DC) - : SE(&ScalarEvolution), R(R), IsOptimized(false), - HasSingleExitEdge(R.getExitingBlock()), HasErrorBlock(false), - MaxLoopDepth(0), CopyStmtsNum(0), DC(DC), + : SE(&ScalarEvolution), R(R), name("Scop for region " + R.getNameStr()), + IsOptimized(false), HasSingleExitEdge(R.getExitingBlock()), + HasErrorBlock(false), MaxLoopDepth(0), CopyStmtsNum(0), DC(DC), IslCtx(isl_ctx_alloc(), isl_ctx_free), Context(nullptr), Affinator(this, LI), AssumedContext(nullptr), InvalidContext(nullptr), Schedule(nullptr) { @@ -4710,7 +4710,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequiredTransitive(); - AU.addRequiredTransitive(); + AU.addRequiredTransitive(); AU.addRequired(); AU.addRequired(); AU.setPreservesAll(); @@ -4736,7 +4736,7 @@ } bool ScopInfoRegionPass::runOnRegion(Region *R, RGPassManager &RGM) { - auto &SD = getAnalysis(); + auto &SD = getAnalysis().getSD(); if (!SD.isMaxRegionInScop(*R)) return false; @@ -4780,27 +4780,72 @@ INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); -INITIALIZE_PASS_DEPENDENCY(ScopDetection); +INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass); INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass); INITIALIZE_PASS_END(ScopInfoRegionPass, "polly-scops", "Polly - Create polyhedral description of Scops", false, false) //===----------------------------------------------------------------------===// +ScopInfo::ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE, + LoopInfo &LI, AliasAnalysis &AA, DominatorTree &DT, + AssumptionCache &AC) { + /// Create polyhedral descripton of scops for all the valid regions of a + /// function. + for (auto &It : SD) { + Region *R = const_cast(It); + if (!SD.isMaxRegionInScop(*R)) + continue; + + ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE); + std::unique_ptr S = SB.getScop(); + if (!S) + continue; + bool Inserted = RegionToScopMap.insert({R, std::move(S)}).second; + assert(Inserted && "Building Scop for the same region twice!"); + (void)Inserted; + } +} + +AnalysisKey ScopInfoAnalysis::Key; + +ScopInfoAnalysis::Result ScopInfoAnalysis::run(Function &F, + FunctionAnalysisManager &FAM) { + auto &SD = FAM.getResult(F); + auto &SE = FAM.getResult(F); + auto &LI = FAM.getResult(F); + auto &AA = FAM.getResult(F); + auto &DT = FAM.getResult(F); + auto &AC = FAM.getResult(F); + auto &DL = F.getParent()->getDataLayout(); + return {DL, SD, SE, LI, AA, DT, AC}; +} + +PreservedAnalyses ScopInfoPrinterPass::run(Function &F, + FunctionAnalysisManager &FAM) { + auto &SI = FAM.getResult(F); + for (auto &It : SI) { + if (It.second) + It.second->print(Stream); + else + Stream << "Invalid Scop!\n"; + } + return PreservedAnalyses::all(); +} + void ScopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); AU.addRequired(); AU.addRequired(); AU.addRequiredTransitive(); - AU.addRequiredTransitive(); + AU.addRequiredTransitive(); AU.addRequired(); AU.addRequired(); AU.setPreservesAll(); } bool ScopInfoWrapperPass::runOnFunction(Function &F) { - auto &SD = getAnalysis(); - + auto &SD = getAnalysis().getSD(); auto &SE = getAnalysis().getSE(); auto &LI = getAnalysis().getLoopInfo(); auto &AA = getAnalysis().getAAResults(); @@ -4808,27 +4853,12 @@ auto &DT = getAnalysis().getDomTree(); auto &AC = getAnalysis().getAssumptionCache(F); - /// Create polyhedral descripton of scops for all the valid regions of a - /// function. - for (auto &It : SD) { - Region *R = const_cast(It); - if (!SD.isMaxRegionInScop(*R)) - continue; - - ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE); - std::unique_ptr S = SB.getScop(); - if (!S) - continue; - bool Inserted = - RegionToScopMap.insert(std::make_pair(R, std::move(S))).second; - assert(Inserted && "Building Scop for the same region twice!"); - (void)Inserted; - } + Result.reset(new ScopInfo{DL, SD, SE, LI, AA, DT, AC}); return false; } void ScopInfoWrapperPass::print(raw_ostream &OS, const Module *) const { - for (auto &It : RegionToScopMap) { + for (auto &It : *Result) { if (It.second) It.second->print(OS); else @@ -4851,7 +4881,7 @@ INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); -INITIALIZE_PASS_DEPENDENCY(ScopDetection); +INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass); INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass); INITIALIZE_PASS_END( ScopInfoWrapperPass, "polly-function-scops", Index: lib/Analysis/ScopPass.cpp =================================================================== --- lib/Analysis/ScopPass.cpp +++ lib/Analysis/ScopPass.cpp @@ -14,6 +14,8 @@ #include "polly/ScopPass.h" #include "polly/ScopInfo.h" +#include "llvm/Analysis/AssumptionCache.h" + using namespace llvm; using namespace polly; @@ -35,3 +37,100 @@ AU.addRequired(); AU.setPreservesAll(); } + +namespace llvm { + +template class PassManager; +template class InnerAnalysisManagerProxy; +template class OuterAnalysisManagerProxy; + +template <> +PreservedAnalyses +PassManager::run( + Scop &S, ScopAnalysisManager &AM, ScopStandardAnalysisResults &AR) { + auto PA = PreservedAnalyses::all(); + for (auto &Pass : Passes) { + auto PassPA = Pass->run(S, AM, AR); + + AM.invalidate(S, PassPA); + PA.intersect(std::move(PassPA)); + } + + // All analyses for 'this' Scop have been invalidated above. Different Scops + // aren't affected + // FIXME is this correct wrt. the current pass behaviours? + PA.preserveSet>(); + return PA; +} + +bool ScopAnalysisManagerFunctionProxy::Result::invalidate( + Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv) { + + // First, check whether our ScopInfo is about to be invalidated + auto PAC = PA.getChecker(); + if (!(PAC.preserved() || PAC.preservedSet>() || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA))) { + + // As everything depends on ScopInfo, we must drop all existing results + for (auto &S : *SI) + if (auto *scop = S.second.get()) + if (InnerAM) + InnerAM->clear(*scop); + + InnerAM = nullptr; + return true; // Invalidate the proxy result as well. + } + + bool allPreserved = PA.allAnalysesInSetPreserved>(); + + // Invalidate all non-preserved analyses + // Even if all analyses were preserved, we still need to run deferred + // invalidation + for (auto &S : *SI) { + Optional InnerPA; + auto *scop = S.second.get(); + if (!scop) + continue; + + if (auto *OuterProxy = + InnerAM->getCachedResult(*scop)) { + for (const auto &InvPair : OuterProxy->getOuterInvalidations()) { + auto *OuterAnalysisID = InvPair.first; + const auto &InnerAnalysisIDs = InvPair.second; + + if (Inv.invalidate(OuterAnalysisID, F, PA)) { + if (!InnerPA) + InnerPA = PA; + for (auto *InnerAnalysisID : InnerAnalysisIDs) + InnerPA->abandon(InnerAnalysisID); + } + } + + if (InnerPA) { + InnerAM->invalidate(*scop, *InnerPA); + continue; + } + } + + if (!allPreserverd) + InnerAM->invalidate(*scop, PA); + } + + return false; // This proxy is still valid +} + +template <> +ScopAnalysisManagerFunctionProxy::Result +ScopAnalysisManagerFunctionProxy::run(Function &F, + FunctionAnalysisManager &FAM) { + return Result(*InnerAM, FAM.getResult(F)); +} +} // namespace llvm Index: lib/CodeGen/CodeGeneration.cpp =================================================================== --- lib/CodeGen/CodeGeneration.cpp +++ lib/CodeGen/CodeGeneration.cpp @@ -276,7 +276,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); - AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addRequired(); @@ -288,7 +288,7 @@ AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); - AU.addPreserved(); + AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -311,6 +311,6 @@ INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); -INITIALIZE_PASS_DEPENDENCY(ScopDetection); +INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass); INITIALIZE_PASS_END(CodeGeneration, "polly-codegen", "Polly - Create LLVM-IR from SCoPs", false, false) Index: lib/CodeGen/PPCGCodeGeneration.cpp =================================================================== --- lib/CodeGen/PPCGCodeGeneration.cpp +++ lib/CodeGen/PPCGCodeGeneration.cpp @@ -2694,7 +2694,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); - AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addRequired(); @@ -2703,7 +2703,7 @@ AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); - AU.addPreserved(); + AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -2731,6 +2731,6 @@ INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); -INITIALIZE_PASS_DEPENDENCY(ScopDetection); +INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass); INITIALIZE_PASS_END(PPCGCodeGeneration, "polly-codegen-ppcg", "Polly - Apply PPCG translation to SCOP", false, false) Index: lib/Support/RegisterPasses.cpp =================================================================== --- lib/Support/RegisterPasses.cpp +++ lib/Support/RegisterPasses.cpp @@ -234,7 +234,7 @@ initializeIslScheduleOptimizerPass(Registry); initializePollyCanonicalizePass(Registry); initializePolyhedralInfoPass(Registry); - initializeScopDetectionPass(Registry); + initializeScopDetectionWrapperPassPass(Registry); initializeScopInfoRegionPassPass(Registry); initializeScopInfoWrapperPassPass(Registry); initializeCodegenCleanupPass(Registry); @@ -277,7 +277,7 @@ for (auto &Filename : DumpBeforeFile) PM.add(polly::createDumpModulePass(Filename, false)); - PM.add(polly::createScopDetectionPass()); + PM.add(polly::createScopDetectionWrapperPassPass()); if (PollyDetectOnly) return; Index: unittests/CMakeLists.txt =================================================================== --- unittests/CMakeLists.txt +++ unittests/CMakeLists.txt @@ -22,3 +22,4 @@ add_subdirectory(Isl) add_subdirectory(Flatten) add_subdirectory(DeLICM) +add_subdirectory(ScopPassManager) Index: unittests/ScopPassManager/CMakeLists.txt =================================================================== --- /dev/null +++ unittests/ScopPassManager/CMakeLists.txt @@ -0,0 +1,3 @@ +add_polly_unittest(ScopPassManagerTests + PassManagerTest.cpp + ) Index: unittests/ScopPassManager/PassManagerTest.cpp =================================================================== --- /dev/null +++ unittests/ScopPassManager/PassManagerTest.cpp @@ -0,0 +1,66 @@ +#include "polly/CodeGen/IslAst.h" +#include "polly/DependenceInfo.h" +#include "polly/ScopPass.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Passes/PassBuilder.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" +#include "gtest/gtest.h" + +using namespace polly; +using namespace llvm; + +namespace { +class ScopPassRegistry : public ::testing::Test { +protected: + ModuleAnalysisManager MAM; + FunctionAnalysisManager FAM; + LoopAnalysisManager LAM; + CGSCCAnalysisManager CGAM; + ScopAnalysisManager SAM; + AAManager AM; + +public: + ScopPassRegistry(ScopPassRegistry &&) = delete; + ScopPassRegistry(const ScopPassRegistry &) = delete; + ScopPassRegistry &operator=(ScopPassRegistry &&) = delete; + ScopPassRegistry &operator=(const ScopPassRegistry &) = delete; + ScopPassRegistry() { + PassBuilder PB; + + AM = PB.buildDefaultAAPipeline(); + PB.registerModuleAnalyses(MAM); + PB.registerFunctionAnalyses(FAM); + PB.registerLoopAnalyses(LAM); + PB.registerCGSCCAnalyses(CGAM); + + FAM.registerPass([] { return ScopAnalysis(); }); + FAM.registerPass([] { return ScopInfoAnalysis(); }); + FAM.registerPass([this] { return ScopAnalysisManagerFunctionProxy(SAM); }); + + SAM.registerPass([] { return IslAstAnalysis(); }); + SAM.registerPass([] { return DependenceAnalysis(); }); + SAM.registerPass([this] { return FunctionAnalysisManagerScopProxy(FAM); }); + + PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + } +}; + +TEST_F(ScopPassRegistry, PrintScops) { + FunctionPassManager FPM; + FPM.addPass(ScopAnalysisPrinterPass(errs())); +} + +TEST_F(ScopPassRegistry, PrintScopInfo) { + FunctionPassManager FPM; + FPM.addPass(ScopInfoPrinterPass(errs())); +} + +TEST_F(ScopPassRegistry, PrinIslAstInfo) { + FunctionPassManager FPM; + ScopPassManager SPM; + SPM.addPass(IslAstPrinterPass(errs())); + FPM.addPass(createFunctionToScopPassAdaptor(std::move(SPM))); +} +} // namespace