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