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/Analysis/TargetTransformInfo.h" 24 #include "llvm/IR/PassManager.h" 25 #include "llvm/IR/PassManagerImpl.h" 26 27 namespace polly { 28 using llvm::AllAnalysesOn; 29 using llvm::AnalysisManager; 30 using llvm::DominatorTreeAnalysis; 31 using llvm::InnerAnalysisManagerProxy; 32 using llvm::LoopAnalysis; 33 using llvm::OuterAnalysisManagerProxy; 34 using llvm::PassManager; 35 using llvm::RegionInfoAnalysis; 36 using llvm::ScalarEvolutionAnalysis; 37 using llvm::SmallPriorityWorklist; 38 using llvm::TargetIRAnalysis; 39 using llvm::TargetTransformInfo; 40 41 class Scop; 42 class SPMUpdater; 43 struct ScopStandardAnalysisResults; 44 45 using ScopAnalysisManager = 46 AnalysisManager<Scop, ScopStandardAnalysisResults &>; 47 using ScopAnalysisManagerFunctionProxy = 48 InnerAnalysisManagerProxy<ScopAnalysisManager, Function>; 49 using FunctionAnalysisManagerScopProxy = 50 OuterAnalysisManagerProxy<FunctionAnalysisManager, Scop, 51 ScopStandardAnalysisResults &>; 52 } // namespace polly 53 54 namespace llvm { 55 using polly::Scop; 56 using polly::ScopAnalysisManager; 57 using polly::ScopAnalysisManagerFunctionProxy; 58 using polly::ScopInfo; 59 using polly::ScopStandardAnalysisResults; 60 using polly::SPMUpdater; 61 62 template <> 63 class InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result { 64 public: Result(ScopAnalysisManager & InnerAM,ScopInfo & SI)65 explicit Result(ScopAnalysisManager &InnerAM, ScopInfo &SI) 66 : InnerAM(&InnerAM), SI(&SI) {} Result(Result && R)67 Result(Result &&R) : InnerAM(std::move(R.InnerAM)), SI(R.SI) { 68 R.InnerAM = nullptr; 69 } 70 Result &operator=(Result &&RHS) { 71 InnerAM = RHS.InnerAM; 72 SI = RHS.SI; 73 RHS.InnerAM = nullptr; 74 return *this; 75 } ~Result()76 ~Result() { 77 if (!InnerAM) 78 return; 79 InnerAM->clear(); 80 } 81 getManager()82 ScopAnalysisManager &getManager() { return *InnerAM; } 83 84 bool invalidate(Function &F, const PreservedAnalyses &PA, 85 FunctionAnalysisManager::Invalidator &Inv); 86 87 private: 88 ScopAnalysisManager *InnerAM; 89 ScopInfo *SI; 90 }; 91 92 // A partial specialization of the require analysis template pass to handle 93 // extra parameters 94 template <typename AnalysisT> 95 struct RequireAnalysisPass<AnalysisT, Scop, ScopAnalysisManager, 96 ScopStandardAnalysisResults &, SPMUpdater &> 97 : PassInfoMixin< 98 RequireAnalysisPass<AnalysisT, Scop, ScopAnalysisManager, 99 ScopStandardAnalysisResults &, SPMUpdater &>> { 100 PreservedAnalyses run(Scop &L, ScopAnalysisManager &AM, 101 ScopStandardAnalysisResults &AR, SPMUpdater &) { 102 (void)AM.template getResult<AnalysisT>(L, AR); 103 return PreservedAnalyses::all(); 104 } 105 }; 106 107 template <> 108 InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result 109 InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::run( 110 Function &F, FunctionAnalysisManager &FAM); 111 112 template <> 113 PreservedAnalyses 114 PassManager<Scop, ScopAnalysisManager, ScopStandardAnalysisResults &, 115 SPMUpdater &>::run(Scop &InitialS, ScopAnalysisManager &AM, 116 ScopStandardAnalysisResults &, SPMUpdater &); 117 extern template class PassManager<Scop, ScopAnalysisManager, 118 ScopStandardAnalysisResults &, SPMUpdater &>; 119 extern template class InnerAnalysisManagerProxy<ScopAnalysisManager, Function>; 120 extern template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Scop, 121 ScopStandardAnalysisResults &>; 122 } // namespace llvm 123 124 namespace polly { 125 126 template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs> 127 class OwningInnerAnalysisManagerProxy 128 : public InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT> { 129 public: 130 OwningInnerAnalysisManagerProxy() 131 : InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>(InnerAM) {} 132 using Result = typename InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT, 133 ExtraArgTs...>::Result; 134 Result run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &AM, 135 ExtraArgTs...) { 136 return Result(InnerAM); 137 } 138 139 AnalysisManagerT &getManager() { return InnerAM; } 140 141 private: 142 AnalysisManagerT InnerAM; 143 }; 144 145 template <> 146 OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result 147 OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>::run( 148 Function &F, FunctionAnalysisManager &FAM); 149 extern template class OwningInnerAnalysisManagerProxy<ScopAnalysisManager, 150 Function>; 151 152 using OwningScopAnalysisManagerFunctionProxy = 153 OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>; 154 using ScopPassManager = 155 PassManager<Scop, ScopAnalysisManager, ScopStandardAnalysisResults &, 156 SPMUpdater &>; 157 158 /// ScopPass - This class adapts the RegionPass interface to allow convenient 159 /// creation of passes that operate on the Polly IR. Instead of overriding 160 /// runOnRegion, subclasses override runOnScop. 161 class ScopPass : public RegionPass { 162 Scop *S; 163 164 protected: 165 explicit ScopPass(char &ID) : RegionPass(ID), S(0) {} 166 167 /// runOnScop - This method must be overloaded to perform the 168 /// desired Polyhedral transformation or analysis. 169 /// 170 virtual bool runOnScop(Scop &S) = 0; 171 172 /// Print method for SCoPs. 173 virtual void printScop(raw_ostream &OS, Scop &S) const {} 174 175 /// getAnalysisUsage - Subclasses that override getAnalysisUsage 176 /// must call this. 177 /// 178 virtual void getAnalysisUsage(AnalysisUsage &AU) const override; 179 180 private: 181 bool runOnRegion(Region *R, RGPassManager &RGM) override; 182 void print(raw_ostream &OS, const Module *) const override; 183 }; 184 185 struct ScopStandardAnalysisResults { 186 DominatorTree &DT; 187 ScopInfo &SI; 188 ScalarEvolution &SE; 189 LoopInfo &LI; 190 RegionInfo &RI; 191 TargetTransformInfo &TTI; 192 }; 193 194 class SPMUpdater { 195 public: 196 SPMUpdater(SmallPriorityWorklist<Region *, 4> &Worklist, 197 ScopAnalysisManager &SAM) 198 : InvalidateCurrentScop(false), Worklist(Worklist), SAM(SAM) {} 199 200 bool invalidateCurrentScop() const { return InvalidateCurrentScop; } 201 202 void invalidateScop(Scop &S) { 203 if (&S == CurrentScop) 204 InvalidateCurrentScop = true; 205 206 Worklist.erase(&S.getRegion()); 207 SAM.clear(S, S.getName()); 208 } 209 210 private: 211 Scop *CurrentScop; 212 bool InvalidateCurrentScop; 213 SmallPriorityWorklist<Region *, 4> &Worklist; 214 ScopAnalysisManager &SAM; 215 template <typename ScopPassT> friend class FunctionToScopPassAdaptor; 216 }; 217 218 template <typename ScopPassT> 219 class FunctionToScopPassAdaptor 220 : public PassInfoMixin<FunctionToScopPassAdaptor<ScopPassT>> { 221 public: 222 explicit FunctionToScopPassAdaptor(ScopPassT Pass) : Pass(std::move(Pass)) {} 223 224 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { 225 ScopDetection &SD = AM.getResult<ScopAnalysis>(F); 226 ScopInfo &SI = AM.getResult<ScopInfoAnalysis>(F); 227 if (SI.empty()) { 228 // With no scops having been detected, no IR changes have been made and 229 // therefore all analyses are preserved. However, we must still free the 230 // Scop analysis results which may hold AssertingVH that cause an error 231 // if its value is destroyed. 232 PreservedAnalyses PA = PreservedAnalyses::all(); 233 PA.abandon<ScopInfoAnalysis>(); 234 PA.abandon<ScopAnalysis>(); 235 AM.invalidate(F, PA); 236 return PreservedAnalyses::all(); 237 } 238 239 SmallPriorityWorklist<Region *, 4> Worklist; 240 for (auto &S : SI) 241 if (S.second) 242 Worklist.insert(S.first); 243 244 ScopStandardAnalysisResults AR = {AM.getResult<DominatorTreeAnalysis>(F), 245 AM.getResult<ScopInfoAnalysis>(F), 246 AM.getResult<ScalarEvolutionAnalysis>(F), 247 AM.getResult<LoopAnalysis>(F), 248 AM.getResult<RegionInfoAnalysis>(F), 249 AM.getResult<TargetIRAnalysis>(F)}; 250 251 ScopAnalysisManager &SAM = 252 AM.getResult<ScopAnalysisManagerFunctionProxy>(F).getManager(); 253 254 SPMUpdater Updater{Worklist, SAM}; 255 256 while (!Worklist.empty()) { 257 Region *R = Worklist.pop_back_val(); 258 if (!SD.isMaxRegionInScop(*R, /*Verifying=*/false)) 259 continue; 260 Scop *scop = SI.getScop(R); 261 if (!scop) 262 continue; 263 Updater.CurrentScop = scop; 264 Updater.InvalidateCurrentScop = false; 265 PreservedAnalyses PassPA = Pass.run(*scop, SAM, AR, Updater); 266 267 SAM.invalidate(*scop, PassPA); 268 if (Updater.invalidateCurrentScop()) 269 SI.recompute(); 270 }; 271 272 // FIXME: For the same reason as we add a BarrierNoopPass in the legacy pass 273 // manager, do not preserve any analyses. While CodeGeneration may preserve 274 // IR analyses sufficiently to process another Scop in the same function (it 275 // has to, otherwise the ScopDetection result itself would need to be 276 // invalidated), it is not sufficient for other purposes. For instance, 277 // CodeGeneration does not inform LoopInfo about new loops in the 278 // Polly-generated IR. 279 return PreservedAnalyses::none(); 280 } 281 282 private: 283 ScopPassT Pass; 284 }; 285 286 template <typename ScopPassT> 287 FunctionToScopPassAdaptor<ScopPassT> 288 createFunctionToScopPassAdaptor(ScopPassT Pass) { 289 return FunctionToScopPassAdaptor<ScopPassT>(std::move(Pass)); 290 } 291 } // namespace polly 292 293 #endif 294