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
27namespace polly {
28using llvm::AllAnalysesOn;
29using llvm::AnalysisManager;
30using llvm::DominatorTreeAnalysis;
31using llvm::InnerAnalysisManagerProxy;
32using llvm::LoopAnalysis;
33using llvm::OuterAnalysisManagerProxy;
34using llvm::PassManager;
35using llvm::RegionInfoAnalysis;
36using llvm::ScalarEvolutionAnalysis;
37using llvm::SmallPriorityWorklist;
38using llvm::TargetIRAnalysis;
39using llvm::TargetTransformInfo;
40
41class Scop;
42class SPMUpdater;
43struct ScopStandardAnalysisResults;
44
45using ScopAnalysisManager =
46 AnalysisManager<Scop, ScopStandardAnalysisResults &>;
47using ScopAnalysisManagerFunctionProxy =
48 InnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
49using FunctionAnalysisManagerScopProxy =
50 OuterAnalysisManagerProxy<FunctionAnalysisManager, Scop,
51 ScopStandardAnalysisResults &>;
52} // namespace polly
53
54namespace llvm {
55using polly::Scop;
56using polly::ScopAnalysisManager;
57using polly::ScopAnalysisManagerFunctionProxy;
58using polly::ScopInfo;
59using polly::ScopStandardAnalysisResults;
60using polly::SPMUpdater;
61
62template <>
63class InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result {
64public:
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
87private:
88 ScopAnalysisManager *InnerAM;
89 ScopInfo *SI;
90};
91
92// A partial specialization of the require analysis template pass to handle
93// extra parameters
94template <typename AnalysisT>
95struct 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
107template <>
108InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result
109InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::run(
110 Function &F, FunctionAnalysisManager &FAM);
111
112template <>
113PreservedAnalyses
114PassManager<Scop, ScopAnalysisManager, ScopStandardAnalysisResults &,
115 SPMUpdater &>::run(Scop &InitialS, ScopAnalysisManager &AM,
116 ScopStandardAnalysisResults &, SPMUpdater &);
117extern template class PassManager<Scop, ScopAnalysisManager,
118 ScopStandardAnalysisResults &, SPMUpdater &>;
119extern template class InnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
120extern template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Scop,
121 ScopStandardAnalysisResults &>;
122} // namespace llvm
123
124namespace polly {
125
126template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
127class OwningInnerAnalysisManagerProxy final
128 : public InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT> {
129public:
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
141private:
142 AnalysisManagerT InnerAM;
143};
144
145template <>
146OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result
147OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>::run(
148 Function &F, FunctionAnalysisManager &FAM);
149extern template class OwningInnerAnalysisManagerProxy<ScopAnalysisManager,
150 Function>;
151
152using OwningScopAnalysisManagerFunctionProxy =
153 OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
154using 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.
161class ScopPass : public RegionPass {
162 Scop *S;
163
164protected:
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
180private:
181 bool runOnRegion(Region *R, RGPassManager &RGM) override;
182 void print(raw_ostream &OS, const Module *) const override;
183};
184
185struct ScopStandardAnalysisResults {
186 DominatorTree &DT;
187 ScopInfo &SI;
188 ScalarEvolution &SE;
189 LoopInfo &LI;
190 RegionInfo &RI;
191 TargetTransformInfo &TTI;
192};
193
194class SPMUpdater final {
195public:
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
210private:
211 Scop *CurrentScop;
212 bool InvalidateCurrentScop;
213 SmallPriorityWorklist<Region *, 4> &Worklist;
214 ScopAnalysisManager &SAM;
215 template <typename ScopPassT> friend struct FunctionToScopPassAdaptor;
216};
217
218template <typename ScopPassT>
219struct 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
281private:
282 ScopPassT Pass;
283};
284
285template <typename ScopPassT>
286FunctionToScopPassAdaptor<ScopPassT>
287createFunctionToScopPassAdaptor(ScopPassT Pass) {
288 return FunctionToScopPassAdaptor<ScopPassT>(std::move(Pass));
289}
290} // namespace polly
291
292#endif
293

source code of polly/include/polly/ScopPass.h