1 | //===- Analysis.h --------------------------------------------*- 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 | /// \file |
9 | /// Pass manager infrastructure for declaring and invalidating analyses. |
10 | //===----------------------------------------------------------------------===// |
11 | |
12 | #ifndef LLVM_IR_ANALYSIS_H |
13 | #define LLVM_IR_ANALYSIS_H |
14 | |
15 | #include "llvm/ADT/SmallPtrSet.h" |
16 | #include "llvm/IR/Function.h" |
17 | #include "llvm/IR/Module.h" |
18 | |
19 | namespace llvm { |
20 | /// A special type used by analysis passes to provide an address that |
21 | /// identifies that particular analysis pass type. |
22 | /// |
23 | /// Analysis passes should have a static data member of this type and derive |
24 | /// from the \c AnalysisInfoMixin to get a static ID method used to identify |
25 | /// the analysis in the pass management infrastructure. |
26 | struct alignas(8) AnalysisKey {}; |
27 | |
28 | /// A special type used to provide an address that identifies a set of related |
29 | /// analyses. These sets are primarily used below to mark sets of analyses as |
30 | /// preserved. |
31 | /// |
32 | /// For example, a transformation can indicate that it preserves the CFG of a |
33 | /// function by preserving the appropriate AnalysisSetKey. An analysis that |
34 | /// depends only on the CFG can then check if that AnalysisSetKey is preserved; |
35 | /// if it is, the analysis knows that it itself is preserved. |
36 | struct alignas(8) AnalysisSetKey {}; |
37 | |
38 | /// This templated class represents "all analyses that operate over \<a |
39 | /// particular IR unit\>" (e.g. a Function or a Module) in instances of |
40 | /// PreservedAnalysis. |
41 | /// |
42 | /// This lets a transformation say e.g. "I preserved all function analyses". |
43 | /// |
44 | /// Note that you must provide an explicit instantiation declaration and |
45 | /// definition for this template in order to get the correct behavior on |
46 | /// Windows. Otherwise, the address of SetKey will not be stable. |
47 | template <typename IRUnitT> class AllAnalysesOn { |
48 | public: |
49 | static AnalysisSetKey *ID() { return &SetKey; } |
50 | |
51 | private: |
52 | static AnalysisSetKey SetKey; |
53 | }; |
54 | |
55 | template <typename IRUnitT> AnalysisSetKey AllAnalysesOn<IRUnitT>::SetKey; |
56 | |
57 | extern template class AllAnalysesOn<Module>; |
58 | extern template class AllAnalysesOn<Function>; |
59 | |
60 | /// Represents analyses that only rely on functions' control flow. |
61 | /// |
62 | /// This can be used with \c PreservedAnalyses to mark the CFG as preserved and |
63 | /// to query whether it has been preserved. |
64 | /// |
65 | /// The CFG of a function is defined as the set of basic blocks and the edges |
66 | /// between them. Changing the set of basic blocks in a function is enough to |
67 | /// mutate the CFG. Mutating the condition of a branch or argument of an |
68 | /// invoked function does not mutate the CFG, but changing the successor labels |
69 | /// of those instructions does. |
70 | class CFGAnalyses { |
71 | public: |
72 | static AnalysisSetKey *ID() { return &SetKey; } |
73 | |
74 | private: |
75 | static AnalysisSetKey SetKey; |
76 | }; |
77 | |
78 | /// A set of analyses that are preserved following a run of a transformation |
79 | /// pass. |
80 | /// |
81 | /// Transformation passes build and return these objects to communicate which |
82 | /// analyses are still valid after the transformation. For most passes this is |
83 | /// fairly simple: if they don't change anything all analyses are preserved, |
84 | /// otherwise only a short list of analyses that have been explicitly updated |
85 | /// are preserved. |
86 | /// |
87 | /// This class also lets transformation passes mark abstract *sets* of analyses |
88 | /// as preserved. A transformation that (say) does not alter the CFG can |
89 | /// indicate such by marking a particular AnalysisSetKey as preserved, and |
90 | /// then analyses can query whether that AnalysisSetKey is preserved. |
91 | /// |
92 | /// Finally, this class can represent an "abandoned" analysis, which is |
93 | /// not preserved even if it would be covered by some abstract set of analyses. |
94 | /// |
95 | /// Given a `PreservedAnalyses` object, an analysis will typically want to |
96 | /// figure out whether it is preserved. In the example below, MyAnalysisType is |
97 | /// preserved if it's not abandoned, and (a) it's explicitly marked as |
98 | /// preserved, (b), the set AllAnalysesOn<MyIRUnit> is preserved, or (c) both |
99 | /// AnalysisSetA and AnalysisSetB are preserved. |
100 | /// |
101 | /// ``` |
102 | /// auto PAC = PA.getChecker<MyAnalysisType>(); |
103 | /// if (PAC.preserved() || PAC.preservedSet<AllAnalysesOn<MyIRUnit>>() || |
104 | /// (PAC.preservedSet<AnalysisSetA>() && |
105 | /// PAC.preservedSet<AnalysisSetB>())) { |
106 | /// // The analysis has been successfully preserved ... |
107 | /// } |
108 | /// ``` |
109 | class PreservedAnalyses { |
110 | public: |
111 | /// Convenience factory function for the empty preserved set. |
112 | static PreservedAnalyses none() { return PreservedAnalyses(); } |
113 | |
114 | /// Construct a special preserved set that preserves all passes. |
115 | static PreservedAnalyses all() { |
116 | PreservedAnalyses PA; |
117 | PA.PreservedIDs.insert(Ptr: &AllAnalysesKey); |
118 | return PA; |
119 | } |
120 | |
121 | /// Construct a preserved analyses object with a single preserved set. |
122 | template <typename AnalysisSetT> static PreservedAnalyses allInSet() { |
123 | PreservedAnalyses PA; |
124 | PA.preserveSet<AnalysisSetT>(); |
125 | return PA; |
126 | } |
127 | |
128 | /// Mark an analysis as preserved. |
129 | template <typename AnalysisT> void preserve() { preserve(AnalysisT::ID()); } |
130 | |
131 | /// Given an analysis's ID, mark the analysis as preserved, adding it |
132 | /// to the set. |
133 | void preserve(AnalysisKey *ID) { |
134 | // Clear this ID from the explicit not-preserved set if present. |
135 | NotPreservedAnalysisIDs.erase(Ptr: ID); |
136 | |
137 | // If we're not already preserving all analyses (other than those in |
138 | // NotPreservedAnalysisIDs). |
139 | if (!areAllPreserved()) |
140 | PreservedIDs.insert(Ptr: ID); |
141 | } |
142 | |
143 | /// Mark an analysis set as preserved. |
144 | template <typename AnalysisSetT> void preserveSet() { |
145 | preserveSet(AnalysisSetT::ID()); |
146 | } |
147 | |
148 | /// Mark an analysis set as preserved using its ID. |
149 | void preserveSet(AnalysisSetKey *ID) { |
150 | // If we're not already in the saturated 'all' state, add this set. |
151 | if (!areAllPreserved()) |
152 | PreservedIDs.insert(Ptr: ID); |
153 | } |
154 | |
155 | /// Mark an analysis as abandoned. |
156 | /// |
157 | /// An abandoned analysis is not preserved, even if it is nominally covered |
158 | /// by some other set or was previously explicitly marked as preserved. |
159 | /// |
160 | /// Note that you can only abandon a specific analysis, not a *set* of |
161 | /// analyses. |
162 | template <typename AnalysisT> void abandon() { abandon(AnalysisT::ID()); } |
163 | |
164 | /// Mark an analysis as abandoned using its ID. |
165 | /// |
166 | /// An abandoned analysis is not preserved, even if it is nominally covered |
167 | /// by some other set or was previously explicitly marked as preserved. |
168 | /// |
169 | /// Note that you can only abandon a specific analysis, not a *set* of |
170 | /// analyses. |
171 | void abandon(AnalysisKey *ID) { |
172 | PreservedIDs.erase(Ptr: ID); |
173 | NotPreservedAnalysisIDs.insert(Ptr: ID); |
174 | } |
175 | |
176 | /// Intersect this set with another in place. |
177 | /// |
178 | /// This is a mutating operation on this preserved set, removing all |
179 | /// preserved passes which are not also preserved in the argument. |
180 | void intersect(const PreservedAnalyses &Arg) { |
181 | if (Arg.areAllPreserved()) |
182 | return; |
183 | if (areAllPreserved()) { |
184 | *this = Arg; |
185 | return; |
186 | } |
187 | // The intersection requires the *union* of the explicitly not-preserved |
188 | // IDs and the *intersection* of the preserved IDs. |
189 | for (auto *ID : Arg.NotPreservedAnalysisIDs) { |
190 | PreservedIDs.erase(Ptr: ID); |
191 | NotPreservedAnalysisIDs.insert(Ptr: ID); |
192 | } |
193 | for (auto *ID : PreservedIDs) |
194 | if (!Arg.PreservedIDs.count(Ptr: ID)) |
195 | PreservedIDs.erase(Ptr: ID); |
196 | } |
197 | |
198 | /// Intersect this set with a temporary other set in place. |
199 | /// |
200 | /// This is a mutating operation on this preserved set, removing all |
201 | /// preserved passes which are not also preserved in the argument. |
202 | void intersect(PreservedAnalyses &&Arg) { |
203 | if (Arg.areAllPreserved()) |
204 | return; |
205 | if (areAllPreserved()) { |
206 | *this = std::move(Arg); |
207 | return; |
208 | } |
209 | // The intersection requires the *union* of the explicitly not-preserved |
210 | // IDs and the *intersection* of the preserved IDs. |
211 | for (auto *ID : Arg.NotPreservedAnalysisIDs) { |
212 | PreservedIDs.erase(Ptr: ID); |
213 | NotPreservedAnalysisIDs.insert(Ptr: ID); |
214 | } |
215 | for (auto *ID : PreservedIDs) |
216 | if (!Arg.PreservedIDs.count(Ptr: ID)) |
217 | PreservedIDs.erase(Ptr: ID); |
218 | } |
219 | |
220 | /// A checker object that makes it easy to query for whether an analysis or |
221 | /// some set covering it is preserved. |
222 | class PreservedAnalysisChecker { |
223 | friend class PreservedAnalyses; |
224 | |
225 | const PreservedAnalyses &PA; |
226 | AnalysisKey *const ID; |
227 | const bool IsAbandoned; |
228 | |
229 | /// A PreservedAnalysisChecker is tied to a particular Analysis because |
230 | /// `preserved()` and `preservedSet()` both return false if the Analysis |
231 | /// was abandoned. |
232 | PreservedAnalysisChecker(const PreservedAnalyses &PA, AnalysisKey *ID) |
233 | : PA(PA), ID(ID), IsAbandoned(PA.NotPreservedAnalysisIDs.count(Ptr: ID)) {} |
234 | |
235 | public: |
236 | /// Returns true if the checker's analysis was not abandoned and either |
237 | /// - the analysis is explicitly preserved or |
238 | /// - all analyses are preserved. |
239 | bool preserved() { |
240 | return !IsAbandoned && (PA.PreservedIDs.count(Ptr: &AllAnalysesKey) || |
241 | PA.PreservedIDs.count(Ptr: ID)); |
242 | } |
243 | |
244 | /// Return true if the checker's analysis was not abandoned, i.e. it was not |
245 | /// explicitly invalidated. Even if the analysis is not explicitly |
246 | /// preserved, if the analysis is known stateless, then it is preserved. |
247 | bool preservedWhenStateless() { return !IsAbandoned; } |
248 | |
249 | /// Returns true if the checker's analysis was not abandoned and either |
250 | /// - \p AnalysisSetT is explicitly preserved or |
251 | /// - all analyses are preserved. |
252 | template <typename AnalysisSetT> bool preservedSet() { |
253 | AnalysisSetKey *SetID = AnalysisSetT::ID(); |
254 | return !IsAbandoned && (PA.PreservedIDs.count(Ptr: &AllAnalysesKey) || |
255 | PA.PreservedIDs.count(Ptr: SetID)); |
256 | } |
257 | }; |
258 | |
259 | /// Build a checker for this `PreservedAnalyses` and the specified analysis |
260 | /// type. |
261 | /// |
262 | /// You can use the returned object to query whether an analysis was |
263 | /// preserved. See the example in the comment on `PreservedAnalysis`. |
264 | template <typename AnalysisT> PreservedAnalysisChecker getChecker() const { |
265 | return PreservedAnalysisChecker(*this, AnalysisT::ID()); |
266 | } |
267 | |
268 | /// Build a checker for this `PreservedAnalyses` and the specified analysis |
269 | /// ID. |
270 | /// |
271 | /// You can use the returned object to query whether an analysis was |
272 | /// preserved. See the example in the comment on `PreservedAnalysis`. |
273 | PreservedAnalysisChecker getChecker(AnalysisKey *ID) const { |
274 | return PreservedAnalysisChecker(*this, ID); |
275 | } |
276 | |
277 | /// Test whether all analyses are preserved (and none are abandoned). |
278 | /// |
279 | /// This is used primarily to optimize for the common case of a transformation |
280 | /// which makes no changes to the IR. |
281 | bool areAllPreserved() const { |
282 | return NotPreservedAnalysisIDs.empty() && |
283 | PreservedIDs.count(Ptr: &AllAnalysesKey); |
284 | } |
285 | |
286 | /// Directly test whether a set of analyses is preserved. |
287 | /// |
288 | /// This is only true when no analyses have been explicitly abandoned. |
289 | template <typename AnalysisSetT> bool allAnalysesInSetPreserved() const { |
290 | return allAnalysesInSetPreserved(AnalysisSetT::ID()); |
291 | } |
292 | |
293 | /// Directly test whether a set of analyses is preserved. |
294 | /// |
295 | /// This is only true when no analyses have been explicitly abandoned. |
296 | bool allAnalysesInSetPreserved(AnalysisSetKey *SetID) const { |
297 | return NotPreservedAnalysisIDs.empty() && |
298 | (PreservedIDs.count(Ptr: &AllAnalysesKey) || PreservedIDs.count(Ptr: SetID)); |
299 | } |
300 | |
301 | private: |
302 | /// A special key used to indicate all analyses. |
303 | static AnalysisSetKey AllAnalysesKey; |
304 | |
305 | /// The IDs of analyses and analysis sets that are preserved. |
306 | SmallPtrSet<void *, 2> PreservedIDs; |
307 | |
308 | /// The IDs of explicitly not-preserved analyses. |
309 | /// |
310 | /// If an analysis in this set is covered by a set in `PreservedIDs`, we |
311 | /// consider it not-preserved. That is, `NotPreservedAnalysisIDs` always |
312 | /// "wins" over analysis sets in `PreservedIDs`. |
313 | /// |
314 | /// Also, a given ID should never occur both here and in `PreservedIDs`. |
315 | SmallPtrSet<AnalysisKey *, 2> NotPreservedAnalysisIDs; |
316 | }; |
317 | } // namespace llvm |
318 | |
319 | #endif |