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