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 final
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(nullptr) {}
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   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 final {
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 struct FunctionToScopPassAdaptor;
216 };
217 
218 template <typename ScopPassT>
219 struct FunctionToScopPassAdaptor final
220     : PassInfoMixin<FunctionToScopPassAdaptor<ScopPassT>> {
221   explicit FunctionToScopPassAdaptor(ScopPassT Pass) : Pass(std::move(Pass)) {}
222 
223   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
224     ScopDetection &SD = AM.getResult<ScopAnalysis>(F);
225     ScopInfo &SI = AM.getResult<ScopInfoAnalysis>(F);
226     if (SI.empty()) {
227       // With no scops having been detected, no IR changes have been made and
228       // therefore all analyses are preserved. However, we must still free the
229       // Scop analysis results which may hold AssertingVH that cause an error
230       // if its value is destroyed.
231       PreservedAnalyses PA = PreservedAnalyses::all();
232       PA.abandon<ScopInfoAnalysis>();
233       PA.abandon<ScopAnalysis>();
234       AM.invalidate(F, PA);
235       return PreservedAnalyses::all();
236     }
237 
238     SmallPriorityWorklist<Region *, 4> Worklist;
239     for (auto &S : SI)
240       if (S.second)
241         Worklist.insert(S.first);
242 
243     ScopStandardAnalysisResults AR = {AM.getResult<DominatorTreeAnalysis>(F),
244                                       AM.getResult<ScopInfoAnalysis>(F),
245                                       AM.getResult<ScalarEvolutionAnalysis>(F),
246                                       AM.getResult<LoopAnalysis>(F),
247                                       AM.getResult<RegionInfoAnalysis>(F),
248                                       AM.getResult<TargetIRAnalysis>(F)};
249 
250     ScopAnalysisManager &SAM =
251         AM.getResult<ScopAnalysisManagerFunctionProxy>(F).getManager();
252 
253     SPMUpdater Updater{Worklist, SAM};
254 
255     while (!Worklist.empty()) {
256       Region *R = Worklist.pop_back_val();
257       if (!SD.isMaxRegionInScop(*R, /*Verify=*/false))
258         continue;
259       Scop *scop = SI.getScop(R);
260       if (!scop)
261         continue;
262       Updater.CurrentScop = scop;
263       Updater.InvalidateCurrentScop = false;
264       PreservedAnalyses PassPA = Pass.run(*scop, SAM, AR, Updater);
265 
266       SAM.invalidate(*scop, PassPA);
267       if (Updater.invalidateCurrentScop())
268         SI.recompute();
269     };
270 
271     // FIXME: For the same reason as we add a BarrierNoopPass in the legacy pass
272     // manager, do not preserve any analyses. While CodeGeneration may preserve
273     // IR analyses sufficiently to process another Scop in the same function (it
274     // has to, otherwise the ScopDetection result itself would need to be
275     // invalidated), it is not sufficient for other purposes. For instance,
276     // CodeGeneration does not inform LoopInfo about new loops in the
277     // Polly-generated IR.
278     return PreservedAnalyses::none();
279   }
280 
281 private:
282   ScopPassT Pass;
283 };
284 
285 template <typename ScopPassT>
286 FunctionToScopPassAdaptor<ScopPassT>
287 createFunctionToScopPassAdaptor(ScopPassT Pass) {
288   return FunctionToScopPassAdaptor<ScopPassT>(std::move(Pass));
289 }
290 } // namespace polly
291 
292 #endif
293