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: |
65 | explicit Result(ScopAnalysisManager &InnerAM, ScopInfo &SI) |
66 | : InnerAM(&InnerAM), SI(&SI) {} |
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 | } |
76 | ~Result() { |
77 | if (!InnerAM) |
78 | return; |
79 | InnerAM->clear(); |
80 | } |
81 | |
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(X: &S.getRegion()); |
207 | SAM.clear(IR&: S, Name: 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>(IR&: F); |
225 | ScopInfo &SI = AM.getResult<ScopInfoAnalysis>(IR&: 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(IR&: 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(X: S.first); |
242 | |
243 | ScopStandardAnalysisResults AR = {.DT: AM.getResult<DominatorTreeAnalysis>(IR&: F), |
244 | .SI: AM.getResult<ScopInfoAnalysis>(IR&: F), |
245 | .SE: AM.getResult<ScalarEvolutionAnalysis>(IR&: F), |
246 | .LI: AM.getResult<LoopAnalysis>(IR&: F), |
247 | .RI: AM.getResult<RegionInfoAnalysis>(IR&: F), |
248 | .TTI: AM.getResult<TargetIRAnalysis>(IR&: F)}; |
249 | |
250 | ScopAnalysisManager &SAM = |
251 | AM.getResult<ScopAnalysisManagerFunctionProxy>(IR&: 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: *R, /*Verify=*/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(IR&: *scop, PA: 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 | |