1 //===--------- ScopPass.h - Pass for Static Control Parts --------*-C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the ScopPass class. ScopPasses are just RegionPasses, 10 // except they operate on Polly IR (Scop and ScopStmt) built by ScopInfo Pass. 11 // Because they operate on Polly IR, not the LLVM IR, ScopPasses are not allowed 12 // to modify the LLVM IR. Due to this limitation, the ScopPass class takes 13 // care of declaring that no LLVM passes are invalidated. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #ifndef POLLY_SCOP_PASS_H 18 #define POLLY_SCOP_PASS_H 19 20 #include "polly/ScopInfo.h" 21 #include "llvm/ADT/PriorityWorklist.h" 22 #include "llvm/Analysis/RegionPass.h" 23 #include "llvm/IR/PassManager.h" 24 #include "llvm/IR/PassManagerImpl.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::Scop; 44 using polly::ScopAnalysisManager; 45 using polly::ScopAnalysisManagerFunctionProxy; 46 using polly::ScopInfo; 47 using polly::ScopStandardAnalysisResults; 48 using polly::SPMUpdater; 49 50 template <> 51 class InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result { 52 public: Result(ScopAnalysisManager & InnerAM,ScopInfo & SI)53 explicit Result(ScopAnalysisManager &InnerAM, ScopInfo &SI) 54 : InnerAM(&InnerAM), SI(&SI) {} Result(Result && R)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 } ~Result()64 ~Result() { 65 if (!InnerAM) 66 return; 67 InnerAM->clear(); 68 } 69 getManager()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 : InvalidateCurrentScop(false), Worklist(Worklist), SAM(SAM) {} 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, S.getName()); 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 }; 265 266 template <typename ScopPassT> 267 FunctionToScopPassAdaptor<ScopPassT> 268 createFunctionToScopPassAdaptor(ScopPassT Pass) { 269 return FunctionToScopPassAdaptor<ScopPassT>(std::move(Pass)); 270 } 271 } // namespace polly 272 273 #endif 274