include/polly/ScopPass.h

   1 //===--------- ScopPass.h - Pass for Static Control Parts --------*-C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the ScopPass class.  ScopPasses are just RegionPasses,
  11 // except they operate on Polly IR (Scop and ScopStmt) built by ScopInfo Pass.
  12 // Because they operate on Polly IR, not the LLVM IR, ScopPasses are not allowed
  13 // to modify the LLVM IR. Due to this limitation, the ScopPass class takes
  14 // care of declaring that no LLVM passes are invalidated.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #ifndef POLLY_SCOP_PASS_H
  19 #define POLLY_SCOP_PASS_H
  20
  21 #include "polly/ScopInfo.h"
  22 #include "llvm/ADT/PriorityWorklist.h"
  23 #include "llvm/Analysis/RegionPass.h"
  24 #include "llvm/IR/PassManager.h"
  25
  26 using namespace llvm;
  27
  28 namespace polly {
  29 class Scop;
  30 class SPMUpdater;
  31 struct ScopStandardAnalysisResults;
  32
  33 using ScopAnalysisManager =
  34     AnalysisManager<Scop, ScopStandardAnalysisResults &>;
  35 using ScopAnalysisManagerFunctionProxy =
  36     InnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
  37 using FunctionAnalysisManagerScopProxy =
  38     OuterAnalysisManagerProxy<FunctionAnalysisManager, Scop,
  39                               ScopStandardAnalysisResults &>;
  40 } // namespace polly
  41
  42 namespace llvm {
  43 using polly::SPMUpdater;
  44 using polly::Scop;
  45 using polly::ScopAnalysisManager;
  46 using polly::ScopAnalysisManagerFunctionProxy;
  47 using polly::ScopInfo;
  48 using polly::ScopStandardAnalysisResults;
  49
  50 template <>
  51 class InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result {
  52 public:
  53   explicit Result(ScopAnalysisManager &InnerAM, ScopInfo &SI)
  54       : InnerAM(&InnerAM), SI(&SI) {}
  55   Result(Result &&R) : InnerAM(std::move(R.InnerAM)), SI(R.SI) {
  56     R.InnerAM = nullptr;
  57   }
  58   Result &operator=(Result &&RHS) {
  59     InnerAM = RHS.InnerAM;
  60     SI = RHS.SI;
  61     RHS.InnerAM = nullptr;
  62     return *this;
  63   }
  64   ~Result() {
  65     if (!InnerAM)
  66       return;
  67     InnerAM->clear();
  68   }
  69
  70   ScopAnalysisManager &getManager() { return *InnerAM; }
  71
  72   bool invalidate(Function &F, const PreservedAnalyses &PA,
  73                   FunctionAnalysisManager::Invalidator &Inv);
  74
  75 private:
  76   ScopAnalysisManager *InnerAM;
  77   ScopInfo *SI;
  78 };
  79
  80 // A partial specialization of the require analysis template pass to handle
  81 // extra parameters
  82 template <typename AnalysisT>
  83 struct RequireAnalysisPass<AnalysisT, Scop, ScopAnalysisManager,
  84                            ScopStandardAnalysisResults &, SPMUpdater &>
  85     : PassInfoMixin<
  86           RequireAnalysisPass<AnalysisT, Scop, ScopAnalysisManager,
  87                               ScopStandardAnalysisResults &, SPMUpdater &>> {
  88   PreservedAnalyses run(Scop &L, ScopAnalysisManager &AM,
  89                         ScopStandardAnalysisResults &AR, SPMUpdater &) {
  90     (void)AM.template getResult<AnalysisT>(L, AR);
  91     return PreservedAnalyses::all();
  92   }
  93 };
  94
  95 template <>
  96 InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result
  97 InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::run(
  98     Function &F, FunctionAnalysisManager &FAM);
  99
 100 template <>
 101 PreservedAnalyses
 102 PassManager<Scop, ScopAnalysisManager, ScopStandardAnalysisResults &,
 103             SPMUpdater &>::run(Scop &InitialS, ScopAnalysisManager &AM,
 104                                ScopStandardAnalysisResults &, SPMUpdater &);
 105 extern template class PassManager<Scop, ScopAnalysisManager,
 106                                   ScopStandardAnalysisResults &, SPMUpdater &>;
 107 extern template class InnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
 108 extern template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Scop,
 109                                                 ScopStandardAnalysisResults &>;
 110 } // namespace llvm
 111
 112 namespace polly {
 113
 114 template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
 115 class OwningInnerAnalysisManagerProxy
 116     : public InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT> {
 117 public:
 118   OwningInnerAnalysisManagerProxy()
 119       : InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>(InnerAM) {}
 120   using Result = typename InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT,
 121                                                     ExtraArgTs...>::Result;
 122   Result run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &AM,
 123              ExtraArgTs...) {
 124     return Result(InnerAM);
 125   }
 126
 127   AnalysisManagerT &getManager() { return InnerAM; }
 128
 129 private:
 130   AnalysisManagerT InnerAM;
 131 };
 132
 133 template <>
 134 OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result
 135 OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>::run(
 136     Function &F, FunctionAnalysisManager &FAM);
 137 extern template class OwningInnerAnalysisManagerProxy<ScopAnalysisManager,
 138                                                       Function>;
 139
 140 using OwningScopAnalysisManagerFunctionProxy =
 141     OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
 142 using ScopPassManager =
 143     PassManager<Scop, ScopAnalysisManager, ScopStandardAnalysisResults &,
 144                 SPMUpdater &>;
 145
 146 /// ScopPass - This class adapts the RegionPass interface to allow convenient
 147 /// creation of passes that operate on the Polly IR. Instead of overriding
 148 /// runOnRegion, subclasses override runOnScop.
 149 class ScopPass : public RegionPass {
 150   Scop *S;
 151
 152 protected:
 153   explicit ScopPass(char &ID) : RegionPass(ID), S(0) {}
 154
 155   /// runOnScop - This method must be overloaded to perform the
 156   /// desired Polyhedral transformation or analysis.
 157   ///
 158   virtual bool runOnScop(Scop &S) = 0;
 159
 160   /// Print method for SCoPs.
 161   virtual void printScop(raw_ostream &OS, Scop &S) const {}
 162
 163   /// getAnalysisUsage - Subclasses that override getAnalysisUsage
 164   /// must call this.
 165   ///
 166   virtual void getAnalysisUsage(AnalysisUsage &AU) const override;
 167
 168 private:
 169   bool runOnRegion(Region *R, RGPassManager &RGM) override;
 170   void print(raw_ostream &OS, const Module *) const override;
 171 };
 172
 173 struct ScopStandardAnalysisResults {
 174   DominatorTree &DT;
 175   ScopInfo &SI;
 176   ScalarEvolution &SE;
 177   LoopInfo &LI;
 178   RegionInfo &RI;
 179 };
 180
 181 class SPMUpdater {
 182 public:
 183   SPMUpdater(SmallPriorityWorklist<Scop *, 4> &Worklist,
 184              ScopAnalysisManager &SAM)
 185       : Worklist(Worklist), SAM(SAM) {}
 186
 187   void SkipScop(Scop &S) {
 188     if (Worklist.erase(&S))
 189       SAM.clear(S);
 190   }
 191
 192 private:
 193   SmallPriorityWorklist<Scop *, 4> &Worklist;
 194   ScopAnalysisManager &SAM;
 195 };
 196
 197 template <typename ScopPassT>
 198 class FunctionToScopPassAdaptor
 199     : public PassInfoMixin<FunctionToScopPassAdaptor<ScopPassT>> {
 200 public:
 201   explicit FunctionToScopPassAdaptor(ScopPassT Pass) : Pass(std::move(Pass)) {}
 202
 203   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
 204     PreservedAnalyses PA = PreservedAnalyses::all();
 205     auto &Scops = AM.getResult<ScopInfoAnalysis>(F);
 206     if (Scops.empty())
 207       return PA;
 208
 209     ScopStandardAnalysisResults AR = {AM.getResult<DominatorTreeAnalysis>(F),
 210                                       AM.getResult<ScopInfoAnalysis>(F),
 211                                       AM.getResult<ScalarEvolutionAnalysis>(F),
 212                                       AM.getResult<LoopAnalysis>(F),
 213                                       AM.getResult<RegionInfoAnalysis>(F)};
 214
 215     ScopAnalysisManager &SAM =
 216         AM.getResult<ScopAnalysisManagerFunctionProxy>(F).getManager();
 217
 218     SmallPriorityWorklist<Scop *, 4> Worklist;
 219     SPMUpdater Updater{Worklist, SAM};
 220
 221     for (auto &S : Scops)
 222       if (auto *scop = S.second.get())
 223         Worklist.insert(scop);
 224
 225     while (!Worklist.empty()) {
 226       Scop *scop = Worklist.pop_back_val();
 227       PreservedAnalyses PassPA = Pass.run(*scop, SAM, AR, Updater);
 228
 229       SAM.invalidate(*scop, PassPA);
 230       PA.intersect(std::move(PassPA));
 231     };
 232
 233     PA.preserveSet<AllAnalysesOn<Scop>>();
 234     PA.preserve<ScopAnalysisManagerFunctionProxy>();
 235     PA.preserve<DominatorTreeAnalysis>();
 236     PA.preserve<ScopAnalysis>();
 237     PA.preserve<ScopInfoAnalysis>();
 238     PA.preserve<ScalarEvolutionAnalysis>();
 239     PA.preserve<LoopAnalysis>();
 240     PA.preserve<RegionInfoAnalysis>();
 241     return PA;
 242   }
 243
 244 private:
 245   ScopPassT Pass;
 246 }; // namespace polly
 247
 248 template <typename ScopPassT>
 249 FunctionToScopPassAdaptor<ScopPassT>
 250 createFunctionToScopPassAdaptor(ScopPassT Pass) {
 251   return FunctionToScopPassAdaptor<ScopPassT>(std::move(Pass));
 252 }
 253
 254 } // namespace polly
 255
 256 #endif