include/polly/ScopPass.h

0001 //===--------- ScopPass.h - Pass for Static Control Parts --------*-C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file defines the ScopPass class.  ScopPasses are just RegionPasses,
0010 // except they operate on Polly IR (Scop and ScopStmt) built by ScopInfo Pass.
0011 // Because they operate on Polly IR, not the LLVM IR, ScopPasses are not allowed
0012 // to modify the LLVM IR. Due to this limitation, the ScopPass class takes
0013 // care of declaring that no LLVM passes are invalidated.
0014 //
0015 //===----------------------------------------------------------------------===//
0016
0017 #ifndef POLLY_SCOP_PASS_H
0018 #define POLLY_SCOP_PASS_H
0019
0020 #include "polly/ScopInfo.h"
0021 #include "llvm/ADT/PriorityWorklist.h"
0022 #include "llvm/Analysis/RegionPass.h"
0023 #include "llvm/Analysis/TargetTransformInfo.h"
0024 #include "llvm/IR/PassManager.h"
0025 #include "llvm/IR/PassManagerImpl.h"
0026
0027 namespace polly {
0028 using llvm::AllAnalysesOn;
0029 using llvm::AnalysisManager;
0030 using llvm::DominatorTreeAnalysis;
0031 using llvm::InnerAnalysisManagerProxy;
0032 using llvm::LoopAnalysis;
0033 using llvm::OuterAnalysisManagerProxy;
0034 using llvm::PassManager;
0035 using llvm::RegionInfoAnalysis;
0036 using llvm::ScalarEvolutionAnalysis;
0037 using llvm::SmallPriorityWorklist;
0038 using llvm::TargetIRAnalysis;
0039 using llvm::TargetTransformInfo;
0040
0041 class Scop;
0042 class SPMUpdater;
0043 struct ScopStandardAnalysisResults;
0044
0045 using ScopAnalysisManager =
0046     AnalysisManager<Scop, ScopStandardAnalysisResults &>;
0047 using ScopAnalysisManagerFunctionProxy =
0048     InnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
0049 using FunctionAnalysisManagerScopProxy =
0050     OuterAnalysisManagerProxy<FunctionAnalysisManager, Scop,
0051                               ScopStandardAnalysisResults &>;
0052 } // namespace polly
0053
0054 namespace llvm {
0055 using polly::Scop;
0056 using polly::ScopAnalysisManager;
0057 using polly::ScopAnalysisManagerFunctionProxy;
0058 using polly::ScopInfo;
0059 using polly::ScopStandardAnalysisResults;
0060 using polly::SPMUpdater;
0061
0062 template <>
0063 class InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result {
0064 public:
0065   explicit Result(ScopAnalysisManager &InnerAM, ScopInfo &SI)
0066       : InnerAM(&InnerAM), SI(&SI) {}
0067   Result(Result &&R) : InnerAM(std::move(R.InnerAM)), SI(R.SI) {
0068     R.InnerAM = nullptr;
0069   }
0070   Result &operator=(Result &&RHS) {
0071     InnerAM = RHS.InnerAM;
0072     SI = RHS.SI;
0073     RHS.InnerAM = nullptr;
0074     return *this;
0075   }
0076   ~Result() {
0077     if (!InnerAM)
0078       return;
0079     InnerAM->clear();
0080   }
0081
0082   ScopAnalysisManager &getManager() { return *InnerAM; }
0083
0084   bool invalidate(Function &F, const PreservedAnalyses &PA,
0085                   FunctionAnalysisManager::Invalidator &Inv);
0086
0087 private:
0088   ScopAnalysisManager *InnerAM;
0089   ScopInfo *SI;
0090 };
0091
0092 // A partial specialization of the require analysis template pass to handle
0093 // extra parameters
0094 template <typename AnalysisT>
0095 struct RequireAnalysisPass<AnalysisT, Scop, ScopAnalysisManager,
0096                            ScopStandardAnalysisResults &, SPMUpdater &>
0097     : PassInfoMixin<
0098           RequireAnalysisPass<AnalysisT, Scop, ScopAnalysisManager,
0099                               ScopStandardAnalysisResults &, SPMUpdater &>> {
0100   PreservedAnalyses run(Scop &L, ScopAnalysisManager &AM,
0101                         ScopStandardAnalysisResults &AR, SPMUpdater &) {
0102     (void)AM.template getResult<AnalysisT>(L, AR);
0103     return PreservedAnalyses::all();
0104   }
0105 };
0106
0107 template <>
0108 InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result
0109 InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::run(
0110     Function &F, FunctionAnalysisManager &FAM);
0111
0112 template <>
0113 PreservedAnalyses
0114 PassManager<Scop, ScopAnalysisManager, ScopStandardAnalysisResults &,
0115             SPMUpdater &>::run(Scop &InitialS, ScopAnalysisManager &AM,
0116                                ScopStandardAnalysisResults &, SPMUpdater &);
0117 extern template class PassManager<Scop, ScopAnalysisManager,
0118                                   ScopStandardAnalysisResults &, SPMUpdater &>;
0119 extern template class InnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
0120 extern template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Scop,
0121                                                 ScopStandardAnalysisResults &>;
0122 } // namespace llvm
0123
0124 namespace polly {
0125
0126 template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
0127 class OwningInnerAnalysisManagerProxy final
0128     : public InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT> {
0129 public:
0130   OwningInnerAnalysisManagerProxy()
0131       : InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>(InnerAM) {}
0132   using Result = typename InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT,
0133                                                     ExtraArgTs...>::Result;
0134   Result run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &AM,
0135              ExtraArgTs...) {
0136     return Result(InnerAM);
0137   }
0138
0139   AnalysisManagerT &getManager() { return InnerAM; }
0140
0141 private:
0142   AnalysisManagerT InnerAM;
0143 };
0144
0145 template <>
0146 OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result
0147 OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>::run(
0148     Function &F, FunctionAnalysisManager &FAM);
0149 extern template class OwningInnerAnalysisManagerProxy<ScopAnalysisManager,
0150                                                       Function>;
0151
0152 using OwningScopAnalysisManagerFunctionProxy =
0153     OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
0154 using ScopPassManager =
0155     PassManager<Scop, ScopAnalysisManager, ScopStandardAnalysisResults &,
0156                 SPMUpdater &>;
0157
0158 /// ScopPass - This class adapts the RegionPass interface to allow convenient
0159 /// creation of passes that operate on the Polly IR. Instead of overriding
0160 /// runOnRegion, subclasses override runOnScop.
0161 class ScopPass : public RegionPass {
0162   Scop *S;
0163
0164 protected:
0165   explicit ScopPass(char &ID) : RegionPass(ID), S(nullptr) {}
0166
0167   /// runOnScop - This method must be overloaded to perform the
0168   /// desired Polyhedral transformation or analysis.
0169   ///
0170   virtual bool runOnScop(Scop &S) = 0;
0171
0172   /// Print method for SCoPs.
0173   virtual void printScop(raw_ostream &OS, Scop &S) const {}
0174
0175   /// getAnalysisUsage - Subclasses that override getAnalysisUsage
0176   /// must call this.
0177   ///
0178   void getAnalysisUsage(AnalysisUsage &AU) const override;
0179
0180 private:
0181   bool runOnRegion(Region *R, RGPassManager &RGM) override;
0182   void print(raw_ostream &OS, const Module *) const override;
0183 };
0184
0185 struct ScopStandardAnalysisResults {
0186   DominatorTree &DT;
0187   ScopInfo &SI;
0188   ScalarEvolution &SE;
0189   LoopInfo &LI;
0190   RegionInfo &RI;
0191   TargetTransformInfo &TTI;
0192 };
0193
0194 class SPMUpdater final {
0195 public:
0196   SPMUpdater(SmallPriorityWorklist<Region *, 4> &Worklist,
0197              ScopAnalysisManager &SAM)
0198       : InvalidateCurrentScop(false), Worklist(Worklist), SAM(SAM) {}
0199
0200   bool invalidateCurrentScop() const { return InvalidateCurrentScop; }
0201
0202   void invalidateScop(Scop &S) {
0203     if (&S == CurrentScop)
0204       InvalidateCurrentScop = true;
0205
0206     Worklist.erase(&S.getRegion());
0207     SAM.clear(S, S.getName());
0208   }
0209
0210 private:
0211   Scop *CurrentScop;
0212   bool InvalidateCurrentScop;
0213   SmallPriorityWorklist<Region *, 4> &Worklist;
0214   ScopAnalysisManager &SAM;
0215   template <typename ScopPassT> friend struct FunctionToScopPassAdaptor;
0216 };
0217
0218 template <typename ScopPassT>
0219 struct FunctionToScopPassAdaptor final
0220     : PassInfoMixin<FunctionToScopPassAdaptor<ScopPassT>> {
0221   explicit FunctionToScopPassAdaptor(ScopPassT Pass) : Pass(std::move(Pass)) {}
0222
0223   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
0224     ScopDetection &SD = AM.getResult<ScopAnalysis>(F);
0225     ScopInfo &SI = AM.getResult<ScopInfoAnalysis>(F);
0226     if (SI.empty()) {
0227       // With no scops having been detected, no IR changes have been made and
0228       // therefore all analyses are preserved. However, we must still free the
0229       // Scop analysis results which may hold AssertingVH that cause an error
0230       // if its value is destroyed.
0231       PreservedAnalyses PA = PreservedAnalyses::all();
0232       PA.abandon<ScopInfoAnalysis>();
0233       PA.abandon<ScopAnalysis>();
0234       AM.invalidate(F, PA);
0235       return PreservedAnalyses::all();
0236     }
0237
0238     SmallPriorityWorklist<Region *, 4> Worklist;
0239     for (auto &S : SI)
0240       if (S.second)
0241         Worklist.insert(S.first);
0242
0243     ScopStandardAnalysisResults AR = {AM.getResult<DominatorTreeAnalysis>(F),
0244                                       AM.getResult<ScopInfoAnalysis>(F),
0245                                       AM.getResult<ScalarEvolutionAnalysis>(F),
0246                                       AM.getResult<LoopAnalysis>(F),
0247                                       AM.getResult<RegionInfoAnalysis>(F),
0248                                       AM.getResult<TargetIRAnalysis>(F)};
0249
0250     ScopAnalysisManager &SAM =
0251         AM.getResult<ScopAnalysisManagerFunctionProxy>(F).getManager();
0252
0253     SPMUpdater Updater{Worklist, SAM};
0254
0255     while (!Worklist.empty()) {
0256       Region *R = Worklist.pop_back_val();
0257       if (!SD.isMaxRegionInScop(*R, /*Verify=*/false))
0258         continue;
0259       Scop *scop = SI.getScop(R);
0260       if (!scop)
0261         continue;
0262       Updater.CurrentScop = scop;
0263       Updater.InvalidateCurrentScop = false;
0264       PreservedAnalyses PassPA = Pass.run(*scop, SAM, AR, Updater);
0265
0266       SAM.invalidate(*scop, PassPA);
0267       if (Updater.invalidateCurrentScop())
0268         SI.recompute();
0269     };
0270
0271     // FIXME: For the same reason as we add a BarrierNoopPass in the legacy pass
0272     // manager, do not preserve any analyses. While CodeGeneration may preserve
0273     // IR analyses sufficiently to process another Scop in the same function (it
0274     // has to, otherwise the ScopDetection result itself would need to be
0275     // invalidated), it is not sufficient for other purposes. For instance,
0276     // CodeGeneration does not inform LoopInfo about new loops in the
0277     // Polly-generated IR.
0278     return PreservedAnalyses::none();
0279   }
0280
0281 private:
0282   ScopPassT Pass;
0283 };
0284
0285 template <typename ScopPassT>
0286 FunctionToScopPassAdaptor<ScopPassT>
0287 createFunctionToScopPassAdaptor(ScopPassT Pass) {
0288   return FunctionToScopPassAdaptor<ScopPassT>(std::move(Pass));
0289 }
0290 } // namespace polly
0291
0292 #endif