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