1//===- AnalysisManager.h - Analysis Management Infrastructure ---*- 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#ifndef MLIR_PASS_ANALYSISMANAGER_H
10#define MLIR_PASS_ANALYSISMANAGER_H
11
12#include "mlir/IR/Operation.h"
13#include "mlir/Pass/PassInstrumentation.h"
14#include "mlir/Support/LLVM.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/MapVector.h"
17#include "llvm/ADT/SmallPtrSet.h"
18#include "llvm/Support/TypeName.h"
19#include <optional>
20
21namespace mlir {
22class AnalysisManager;
23
24//===----------------------------------------------------------------------===//
25// Analysis Preservation and Concept Modeling
26//===----------------------------------------------------------------------===//
27
28namespace detail {
29/// A utility class to represent the analyses that are known to be preserved.
30class PreservedAnalyses {
31 /// A type used to represent all potential analyses.
32 struct AllAnalysesType {};
33
34public:
35 /// Mark all analyses as preserved.
36 void preserveAll() { preservedIDs.insert(Ptr: TypeID::get<AllAnalysesType>()); }
37
38 /// Returns true if all analyses were marked preserved.
39 bool isAll() const {
40 return preservedIDs.count(Ptr: TypeID::get<AllAnalysesType>());
41 }
42
43 /// Returns true if no analyses were marked preserved.
44 bool isNone() const { return preservedIDs.empty(); }
45
46 /// Preserve the given analyses.
47 template <typename AnalysisT>
48 void preserve() {
49 preserve(TypeID::get<AnalysisT>());
50 }
51 template <typename AnalysisT, typename AnalysisT2, typename... OtherAnalysesT>
52 void preserve() {
53 preserve<AnalysisT>();
54 preserve<AnalysisT2, OtherAnalysesT...>();
55 }
56 void preserve(TypeID id) { preservedIDs.insert(Ptr: id); }
57
58 /// Returns true if the given analysis has been marked as preserved. Note that
59 /// this simply checks for the presence of a given analysis ID and should not
60 /// be used as a general preservation checker.
61 template <typename AnalysisT>
62 bool isPreserved() const {
63 return isPreserved(TypeID::get<AnalysisT>());
64 }
65 bool isPreserved(TypeID id) const { return preservedIDs.count(Ptr: id); }
66
67private:
68 /// Remove the analysis from preserved set.
69 template <typename AnalysisT>
70 void unpreserve() {
71 preservedIDs.erase(Ptr: TypeID::get<AnalysisT>());
72 }
73
74 /// AnalysisModel need access to unpreserve().
75 template <typename>
76 friend struct AnalysisModel;
77
78 /// The set of analyses that are known to be preserved.
79 SmallPtrSet<TypeID, 2> preservedIDs;
80};
81
82namespace analysis_impl {
83/// Trait to check if T provides a static 'isInvalidated' method.
84template <typename T, typename... Args>
85using has_is_invalidated = decltype(std::declval<T &>().isInvalidated(
86 std::declval<const PreservedAnalyses &>()));
87
88/// Implementation of 'isInvalidated' if the analysis provides a definition.
89template <typename AnalysisT>
90std::enable_if_t<llvm::is_detected<has_is_invalidated, AnalysisT>::value, bool>
91isInvalidated(AnalysisT &analysis, const PreservedAnalyses &pa) {
92 return analysis.isInvalidated(pa);
93}
94/// Default implementation of 'isInvalidated'.
95template <typename AnalysisT>
96std::enable_if_t<!llvm::is_detected<has_is_invalidated, AnalysisT>::value, bool>
97isInvalidated(AnalysisT &analysis, const PreservedAnalyses &pa) {
98 return !pa.isPreserved<AnalysisT>();
99}
100} // namespace analysis_impl
101
102/// The abstract polymorphic base class representing an analysis.
103struct AnalysisConcept {
104 virtual ~AnalysisConcept() = default;
105
106 /// A hook used to query analyses for invalidation. Given a preserved analysis
107 /// set, returns true if it should truly be invalidated. This allows for more
108 /// fine-tuned invalidation in cases where an analysis wasn't explicitly
109 /// marked preserved, but may be preserved(or invalidated) based upon other
110 /// properties such as analyses sets. Invalidated analyses must also be
111 /// removed from pa.
112 virtual bool invalidate(PreservedAnalyses &pa) = 0;
113};
114
115/// A derived analysis model used to hold a specific analysis object.
116template <typename AnalysisT>
117struct AnalysisModel : public AnalysisConcept {
118 template <typename... Args>
119 explicit AnalysisModel(Args &&...args)
120 : analysis(std::forward<Args>(args)...) {}
121
122 /// A hook used to query analyses for invalidation. Removes invalidated
123 /// analyses from pa.
124 bool invalidate(PreservedAnalyses &pa) final {
125 bool result = analysis_impl::isInvalidated(analysis, pa);
126 if (result)
127 pa.unpreserve<AnalysisT>();
128 return result;
129 }
130
131 /// The actual analysis object.
132 AnalysisT analysis;
133};
134
135/// This class represents a cache of analyses for a single operation. All
136/// computation, caching, and invalidation of analyses takes place here.
137class AnalysisMap {
138 /// A mapping between an analysis id and an existing analysis instance.
139 using ConceptMap = llvm::MapVector<TypeID, std::unique_ptr<AnalysisConcept>>;
140
141 /// Utility to return the name of the given analysis class.
142 template <typename AnalysisT>
143 static StringRef getAnalysisName() {
144 StringRef name = llvm::getTypeName<AnalysisT>();
145 if (!name.consume_front(Prefix: "mlir::"))
146 name.consume_front(Prefix: "(anonymous namespace)::");
147 return name;
148 }
149
150public:
151 explicit AnalysisMap(Operation *ir) : ir(ir) {}
152
153 /// Get an analysis for the current IR unit, computing it if necessary.
154 template <typename AnalysisT>
155 AnalysisT &getAnalysis(PassInstrumentor *pi, AnalysisManager &am) {
156 return getAnalysisImpl<AnalysisT, Operation *>(pi, ir, am);
157 }
158
159 /// Get an analysis for the current IR unit assuming it's of specific derived
160 /// operation type.
161 template <typename AnalysisT, typename OpT>
162 std::enable_if_t<
163 std::is_constructible<AnalysisT, OpT>::value ||
164 std::is_constructible<AnalysisT, OpT, AnalysisManager &>::value,
165 AnalysisT &>
166 getAnalysis(PassInstrumentor *pi, AnalysisManager &am) {
167 return getAnalysisImpl<AnalysisT, OpT>(pi, cast<OpT>(ir), am);
168 }
169
170 /// Get a cached analysis instance if one exists, otherwise return null.
171 template <typename AnalysisT>
172 std::optional<std::reference_wrapper<AnalysisT>> getCachedAnalysis() const {
173 auto res = analyses.find(TypeID::get<AnalysisT>());
174 if (res == analyses.end())
175 return std::nullopt;
176 return {static_cast<AnalysisModel<AnalysisT> &>(*res->second).analysis};
177 }
178
179 /// Returns the operation that this analysis map represents.
180 Operation *getOperation() const { return ir; }
181
182 /// Clear any held analyses.
183 void clear() { analyses.clear(); }
184
185 /// Invalidate any cached analyses based upon the given set of preserved
186 /// analyses.
187 void invalidate(const PreservedAnalyses &pa) {
188 PreservedAnalyses paCopy(pa);
189 // Remove any analyses that were invalidated.
190 // As we are using MapVector, order of insertion is preserved and
191 // dependencies always go before users, so we need only one iteration.
192 analyses.remove_if(
193 Pred: [&](auto &val) { return val.second->invalidate(paCopy); });
194 }
195
196private:
197 template <typename AnalysisT, typename OpT>
198 AnalysisT &getAnalysisImpl(PassInstrumentor *pi, OpT op,
199 AnalysisManager &am) {
200 TypeID id = TypeID::get<AnalysisT>();
201
202 auto it = analyses.find(Key: id);
203 // If we don't have a cached analysis for this operation, compute it
204 // directly and add it to the cache.
205 if (analyses.end() == it) {
206 if (pi)
207 pi->runBeforeAnalysis(name: getAnalysisName<AnalysisT>(), id, op: ir);
208
209 bool wasInserted;
210 std::tie(args&: it, args&: wasInserted) =
211 analyses.insert({id, constructAnalysis<AnalysisT>(am, op)});
212 assert(wasInserted);
213
214 if (pi)
215 pi->runAfterAnalysis(name: getAnalysisName<AnalysisT>(), id, op: ir);
216 }
217 return static_cast<AnalysisModel<AnalysisT> &>(*it->second).analysis;
218 }
219
220 /// Construct analysis using two arguments constructor (OpT, AnalysisManager)
221 template <typename AnalysisT, typename OpT,
222 std::enable_if_t<std::is_constructible<
223 AnalysisT, OpT, AnalysisManager &>::value> * = nullptr>
224 static auto constructAnalysis(AnalysisManager &am, OpT op) {
225 return std::make_unique<AnalysisModel<AnalysisT>>(op, am);
226 }
227
228 /// Construct analysis using single argument constructor (OpT)
229 template <typename AnalysisT, typename OpT,
230 std::enable_if_t<!std::is_constructible<
231 AnalysisT, OpT, AnalysisManager &>::value> * = nullptr>
232 static auto constructAnalysis(AnalysisManager &, OpT op) {
233 return std::make_unique<AnalysisModel<AnalysisT>>(op);
234 }
235
236 Operation *ir;
237 ConceptMap analyses;
238};
239
240/// An analysis map that contains a map for the current operation, and a set of
241/// maps for any child operations.
242struct NestedAnalysisMap {
243 NestedAnalysisMap(Operation *op, PassInstrumentor *instrumentor)
244 : analyses(op), parentOrInstrumentor(instrumentor) {}
245 NestedAnalysisMap(Operation *op, NestedAnalysisMap *parent)
246 : analyses(op), parentOrInstrumentor(parent) {}
247
248 /// Get the operation for this analysis map.
249 Operation *getOperation() const { return analyses.getOperation(); }
250
251 /// Invalidate any non preserved analyses.
252 void invalidate(const PreservedAnalyses &pa);
253
254 /// Returns the parent analysis map for this analysis map, or null if this is
255 /// the top-level map.
256 const NestedAnalysisMap *getParent() const {
257 return llvm::dyn_cast_if_present<NestedAnalysisMap *>(Val: parentOrInstrumentor);
258 }
259
260 /// Returns a pass instrumentation object for the current operation. This
261 /// value may be null.
262 PassInstrumentor *getPassInstrumentor() const {
263 if (auto *parent = getParent())
264 return parent->getPassInstrumentor();
265 return parentOrInstrumentor.get<PassInstrumentor *>();
266 }
267
268 /// The cached analyses for nested operations.
269 DenseMap<Operation *, std::unique_ptr<NestedAnalysisMap>> childAnalyses;
270
271 /// The analyses for the owning operation.
272 detail::AnalysisMap analyses;
273
274 /// This value has three possible states:
275 /// NestedAnalysisMap*: A pointer to the parent analysis map.
276 /// PassInstrumentor*: This analysis map is the top-level map, and this
277 /// pointer is the optional pass instrumentor for the
278 /// current compilation.
279 /// nullptr: This analysis map is the top-level map, and there is nop pass
280 /// instrumentor.
281 PointerUnion<NestedAnalysisMap *, PassInstrumentor *> parentOrInstrumentor;
282};
283} // namespace detail
284
285//===----------------------------------------------------------------------===//
286// Analysis Management
287//===----------------------------------------------------------------------===//
288class ModuleAnalysisManager;
289
290/// This class represents an analysis manager for a particular operation
291/// instance. It is used to manage and cache analyses on the operation as well
292/// as those for child operations, via nested AnalysisManager instances
293/// accessible via 'slice'. This class is intended to be passed around by value,
294/// and cannot be constructed directly.
295class AnalysisManager {
296 using ParentPointerT =
297 PointerUnion<const ModuleAnalysisManager *, const AnalysisManager *>;
298
299public:
300 using PreservedAnalyses = detail::PreservedAnalyses;
301
302 /// Query for a cached analysis on the given parent operation. The analysis
303 /// may not exist and if it does it may be out-of-date.
304 template <typename AnalysisT>
305 std::optional<std::reference_wrapper<AnalysisT>>
306 getCachedParentAnalysis(Operation *parentOp) const {
307 const detail::NestedAnalysisMap *curParent = impl;
308 while (auto *parentAM = curParent->getParent()) {
309 if (parentAM->getOperation() == parentOp)
310 return parentAM->analyses.getCachedAnalysis<AnalysisT>();
311 curParent = parentAM;
312 }
313 return std::nullopt;
314 }
315
316 /// Query for the given analysis for the current operation.
317 template <typename AnalysisT>
318 AnalysisT &getAnalysis() {
319 return impl->analyses.getAnalysis<AnalysisT>(getPassInstrumentor(), *this);
320 }
321
322 /// Query for the given analysis for the current operation of a specific
323 /// derived operation type.
324 template <typename AnalysisT, typename OpT>
325 AnalysisT &getAnalysis() {
326 return impl->analyses.getAnalysis<AnalysisT, OpT>(getPassInstrumentor(),
327 *this);
328 }
329
330 /// Query for a cached entry of the given analysis on the current operation.
331 template <typename AnalysisT>
332 std::optional<std::reference_wrapper<AnalysisT>> getCachedAnalysis() const {
333 return impl->analyses.getCachedAnalysis<AnalysisT>();
334 }
335
336 /// Query for an analysis of a child operation, constructing it if necessary.
337 template <typename AnalysisT>
338 AnalysisT &getChildAnalysis(Operation *op) {
339 return nest(op).template getAnalysis<AnalysisT>();
340 }
341
342 /// Query for an analysis of a child operation of a specific derived operation
343 /// type, constructing it if necessary.
344 template <typename AnalysisT, typename OpT>
345 AnalysisT &getChildAnalysis(OpT child) {
346 return nest(op: child).template getAnalysis<AnalysisT, OpT>();
347 }
348
349 /// Query for a cached analysis of a child operation, or return null.
350 template <typename AnalysisT>
351 std::optional<std::reference_wrapper<AnalysisT>>
352 getCachedChildAnalysis(Operation *op) const {
353 assert(op->getParentOp() == impl->getOperation());
354 auto it = impl->childAnalyses.find(Val: op);
355 if (it == impl->childAnalyses.end())
356 return std::nullopt;
357 return it->second->analyses.getCachedAnalysis<AnalysisT>();
358 }
359
360 /// Get an analysis manager for the given operation, which must be a proper
361 /// descendant of the current operation represented by this analysis manager.
362 AnalysisManager nest(Operation *op);
363
364 /// Invalidate any non preserved analyses,
365 void invalidate(const PreservedAnalyses &pa) { impl->invalidate(pa); }
366
367 /// Clear any held analyses.
368 void clear() {
369 impl->analyses.clear();
370 impl->childAnalyses.clear();
371 }
372
373 /// Returns a pass instrumentation object for the current operation. This
374 /// value may be null.
375 PassInstrumentor *getPassInstrumentor() const {
376 return impl->getPassInstrumentor();
377 }
378
379private:
380 AnalysisManager(detail::NestedAnalysisMap *impl) : impl(impl) {}
381
382 /// Get an analysis manager for the given immediately nested child operation.
383 AnalysisManager nestImmediate(Operation *op);
384
385 /// A reference to the impl analysis map within the parent analysis manager.
386 detail::NestedAnalysisMap *impl;
387
388 /// Allow access to the constructor.
389 friend class ModuleAnalysisManager;
390};
391
392/// An analysis manager class specifically for the top-level operation. This
393/// class contains the memory allocations for all nested analysis managers, and
394/// provides an anchor point. This is necessary because AnalysisManager is
395/// designed to be a thin wrapper around an existing analysis map instance.
396class ModuleAnalysisManager {
397public:
398 ModuleAnalysisManager(Operation *op, PassInstrumentor *passInstrumentor)
399 : analyses(op, passInstrumentor) {}
400 ModuleAnalysisManager(const ModuleAnalysisManager &) = delete;
401 ModuleAnalysisManager &operator=(const ModuleAnalysisManager &) = delete;
402
403 /// Returns an analysis manager for the current top-level module.
404 operator AnalysisManager() { return AnalysisManager(&analyses); }
405
406private:
407 /// The analyses for the owning module.
408 detail::NestedAnalysisMap analyses;
409};
410
411} // namespace mlir
412
413#endif // MLIR_PASS_ANALYSISMANAGER_H
414

source code of mlir/include/mlir/Pass/AnalysisManager.h