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
19namespace 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.
26struct 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.
36struct 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.
47template <typename IRUnitT> class AllAnalysesOn {
48public:
49 static AnalysisSetKey *ID() { return &SetKey; }
50
51private:
52 static AnalysisSetKey SetKey;
53};
54
55template <typename IRUnitT> AnalysisSetKey AllAnalysesOn<IRUnitT>::SetKey;
56
57extern template class AllAnalysesOn<Module>;
58extern 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.
70class CFGAnalyses {
71public:
72 static AnalysisSetKey *ID() { return &SetKey; }
73
74private:
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/// ```
109class PreservedAnalyses {
110public:
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
301private:
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

source code of llvm/include/llvm/IR/Analysis.h