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<Region *, 4> &Worklist,
 184              ScopAnalysisManager &SAM)
 185       : Worklist(Worklist), SAM(SAM), InvalidateCurrentScop(false) {}
 186
 187   bool invalidateCurrentScop() const { return InvalidateCurrentScop; }
 188
 189   void invalidateScop(Scop &S) {
 190     if (&S == CurrentScop)
 191       InvalidateCurrentScop = true;
 192
 193     Worklist.erase(&S.getRegion());
 194     SAM.clear(S);
 195   }
 196
 197 private:
 198   Scop *CurrentScop;
 199   bool InvalidateCurrentScop;
 200   SmallPriorityWorklist<Region *, 4> &Worklist;
 201   ScopAnalysisManager &SAM;
 202   template <typename ScopPassT> friend class FunctionToScopPassAdaptor;
 203 };
 204
 205 template <typename ScopPassT>
 206 class FunctionToScopPassAdaptor
 207     : public PassInfoMixin<FunctionToScopPassAdaptor<ScopPassT>> {
 208 public:
 209   explicit FunctionToScopPassAdaptor(ScopPassT Pass) : Pass(std::move(Pass)) {}
 210
 211   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
 212     PreservedAnalyses PA = PreservedAnalyses::all();
 213     auto &SD = AM.getResult<ScopAnalysis>(F);
 214     auto &SI = AM.getResult<ScopInfoAnalysis>(F);
 215     if (SI.empty())
 216       return PA;
 217
 218     SmallPriorityWorklist<Region *, 4> Worklist;
 219     for (auto &S : SI)
 220       if (S.second)
 221         Worklist.insert(S.first);
 222
 223     ScopStandardAnalysisResults AR = {AM.getResult<DominatorTreeAnalysis>(F),
 224                                       AM.getResult<ScopInfoAnalysis>(F),
 225                                       AM.getResult<ScalarEvolutionAnalysis>(F),
 226                                       AM.getResult<LoopAnalysis>(F),
 227                                       AM.getResult<RegionInfoAnalysis>(F)};
 228
 229     ScopAnalysisManager &SAM =
 230         AM.getResult<ScopAnalysisManagerFunctionProxy>(F).getManager();
 231
 232     SPMUpdater Updater{Worklist, SAM};
 233
 234     while (!Worklist.empty()) {
 235       Region *R = Worklist.pop_back_val();
 236       if (!SD.isMaxRegionInScop(*R))
 237         continue;
 238       Scop *scop = SI.getScop(R);
 239       if (!scop)
 240         continue;
 241       Updater.CurrentScop = scop;
 242       Updater.InvalidateCurrentScop = false;
 243       PreservedAnalyses PassPA = Pass.run(*scop, SAM, AR, Updater);
 244
 245       SAM.invalidate(*scop, PassPA);
 246       PA.intersect(std::move(PassPA));
 247       if (Updater.invalidateCurrentScop())
 248         SI.recompute();
 249     };
 250
 251     PA.preserveSet<AllAnalysesOn<Scop>>();
 252     PA.preserve<ScopAnalysisManagerFunctionProxy>();
 253     PA.preserve<DominatorTreeAnalysis>();
 254     PA.preserve<ScopAnalysis>();
 255     PA.preserve<ScopInfoAnalysis>();
 256     PA.preserve<ScalarEvolutionAnalysis>();
 257     PA.preserve<LoopAnalysis>();
 258     PA.preserve<RegionInfoAnalysis>();
 259     return PA;
 260   }
 261
 262 private:
 263   ScopPassT Pass;
 264 }; // namespace polly
 265
 266 template <typename ScopPassT>
 267 FunctionToScopPassAdaptor<ScopPassT>
 268 createFunctionToScopPassAdaptor(ScopPassT Pass) {
 269   return FunctionToScopPassAdaptor<ScopPassT>(std::move(Pass));
 270 }
 271
 272 } // namespace polly
 273
 274 #endif