LLVM 20.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
16
17namespace llvm {
18
19class Function;
20class Module;
21
22/// A special type used by analysis passes to provide an address that
23/// identifies that particular analysis pass type.
24///
25/// Analysis passes should have a static data member of this type and derive
26/// from the \c AnalysisInfoMixin to get a static ID method used to identify
27/// the analysis in the pass management infrastructure.
28struct alignas(8) AnalysisKey {};
29
30/// A special type used to provide an address that identifies a set of related
31/// analyses. These sets are primarily used below to mark sets of analyses as
32/// preserved.
33///
34/// For example, a transformation can indicate that it preserves the CFG of a
35/// function by preserving the appropriate AnalysisSetKey. An analysis that
36/// depends only on the CFG can then check if that AnalysisSetKey is preserved;
37/// if it is, the analysis knows that it itself is preserved.
38struct alignas(8) AnalysisSetKey {};
39
40/// This templated class represents "all analyses that operate over <a
41/// particular IR unit>" (e.g. a Function or a Module) in instances of
42/// PreservedAnalysis.
43///
44/// This lets a transformation say e.g. "I preserved all function analyses".
45///
46/// Note that you must provide an explicit instantiation declaration and
47/// definition for this template in order to get the correct behavior on
48/// Windows. Otherwise, the address of SetKey will not be stable.
49template <typename IRUnitT> class AllAnalysesOn {
50public:
51 static AnalysisSetKey *ID() { return &SetKey; }
52
53private:
54 static AnalysisSetKey SetKey;
55};
56
57template <typename IRUnitT> AnalysisSetKey AllAnalysesOn<IRUnitT>::SetKey;
58
59extern template class AllAnalysesOn<Module>;
60extern template class AllAnalysesOn<Function>;
61
62/// Represents analyses that only rely on functions' control flow.
63///
64/// This can be used with \c PreservedAnalyses to mark the CFG as preserved and
65/// to query whether it has been preserved.
66///
67/// The CFG of a function is defined as the set of basic blocks and the edges
68/// between them. Changing the set of basic blocks in a function is enough to
69/// mutate the CFG. Mutating the condition of a branch or argument of an
70/// invoked function does not mutate the CFG, but changing the successor labels
71/// of those instructions does.
73public:
74 static AnalysisSetKey *ID() { return &SetKey; }
75
76private:
77 static AnalysisSetKey SetKey;
78};
79
80/// A set of analyses that are preserved following a run of a transformation
81/// pass.
82///
83/// Transformation passes build and return these objects to communicate which
84/// analyses are still valid after the transformation. For most passes this is
85/// fairly simple: if they don't change anything all analyses are preserved,
86/// otherwise only a short list of analyses that have been explicitly updated
87/// are preserved.
88///
89/// This class also lets transformation passes mark abstract *sets* of analyses
90/// as preserved. A transformation that (say) does not alter the CFG can
91/// indicate such by marking a particular AnalysisSetKey as preserved, and
92/// then analyses can query whether that AnalysisSetKey is preserved.
93///
94/// Finally, this class can represent an "abandoned" analysis, which is
95/// not preserved even if it would be covered by some abstract set of analyses.
96///
97/// Given a `PreservedAnalyses` object, an analysis will typically want to
98/// figure out whether it is preserved. In the example below, MyAnalysisType is
99/// preserved if it's not abandoned, and (a) it's explicitly marked as
100/// preserved, (b), the set AllAnalysesOn<MyIRUnit> is preserved, or (c) both
101/// AnalysisSetA and AnalysisSetB are preserved.
102///
103/// ```
104/// auto PAC = PA.getChecker<MyAnalysisType>();
105/// if (PAC.preserved() || PAC.preservedSet<AllAnalysesOn<MyIRUnit>>() ||
106/// (PAC.preservedSet<AnalysisSetA>() &&
107/// PAC.preservedSet<AnalysisSetB>())) {
108/// // The analysis has been successfully preserved ...
109/// }
110/// ```
112public:
113 /// Convenience factory function for the empty preserved set.
115
116 /// Construct a special preserved set that preserves all passes.
119 PA.PreservedIDs.insert(&AllAnalysesKey);
120 return PA;
121 }
122
123 /// Construct a preserved analyses object with a single preserved set.
124 template <typename AnalysisSetT> static PreservedAnalyses allInSet() {
126 PA.preserveSet<AnalysisSetT>();
127 return PA;
128 }
129
130 /// Mark an analysis as preserved.
131 template <typename AnalysisT> void preserve() { preserve(AnalysisT::ID()); }
132
133 /// Given an analysis's ID, mark the analysis as preserved, adding it
134 /// to the set.
136 // Clear this ID from the explicit not-preserved set if present.
137 NotPreservedAnalysisIDs.erase(ID);
138
139 // If we're not already preserving all analyses (other than those in
140 // NotPreservedAnalysisIDs).
141 if (!areAllPreserved())
142 PreservedIDs.insert(ID);
143 }
144
145 /// Mark an analysis set as preserved.
146 template <typename AnalysisSetT> void preserveSet() {
147 preserveSet(AnalysisSetT::ID());
148 }
149
150 /// Mark an analysis set as preserved using its ID.
152 // If we're not already in the saturated 'all' state, add this set.
153 if (!areAllPreserved())
154 PreservedIDs.insert(ID);
155 }
156
157 /// Mark an analysis as abandoned.
158 ///
159 /// An abandoned analysis is not preserved, even if it is nominally covered
160 /// by some other set or was previously explicitly marked as preserved.
161 ///
162 /// Note that you can only abandon a specific analysis, not a *set* of
163 /// analyses.
164 template <typename AnalysisT> void abandon() { abandon(AnalysisT::ID()); }
165
166 /// Mark an analysis as abandoned using its ID.
167 ///
168 /// An abandoned analysis is not preserved, even if it is nominally covered
169 /// by some other set or was previously explicitly marked as preserved.
170 ///
171 /// Note that you can only abandon a specific analysis, not a *set* of
172 /// analyses.
174 PreservedIDs.erase(ID);
175 NotPreservedAnalysisIDs.insert(ID);
176 }
177
178 /// Intersect this set with another in place.
179 ///
180 /// This is a mutating operation on this preserved set, removing all
181 /// preserved passes which are not also preserved in the argument.
182 void intersect(const PreservedAnalyses &Arg) {
183 if (Arg.areAllPreserved())
184 return;
185 if (areAllPreserved()) {
186 *this = Arg;
187 return;
188 }
189 // The intersection requires the *union* of the explicitly not-preserved
190 // IDs and the *intersection* of the preserved IDs.
191 for (auto *ID : Arg.NotPreservedAnalysisIDs) {
192 PreservedIDs.erase(ID);
193 NotPreservedAnalysisIDs.insert(ID);
194 }
195 PreservedIDs.remove_if(
196 [&](void *ID) { return !Arg.PreservedIDs.contains(ID); });
197 }
198
199 /// Intersect this set with a temporary other set in place.
200 ///
201 /// This is a mutating operation on this preserved set, removing all
202 /// preserved passes which are not also preserved in the argument.
204 if (Arg.areAllPreserved())
205 return;
206 if (areAllPreserved()) {
207 *this = std::move(Arg);
208 return;
209 }
210 // The intersection requires the *union* of the explicitly not-preserved
211 // IDs and the *intersection* of the preserved IDs.
212 for (auto *ID : Arg.NotPreservedAnalysisIDs) {
213 PreservedIDs.erase(ID);
214 NotPreservedAnalysisIDs.insert(ID);
215 }
216 PreservedIDs.remove_if(
217 [&](void *ID) { return !Arg.PreservedIDs.contains(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.
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.
233 : PA(PA), ID(ID), IsAbandoned(PA.NotPreservedAnalysisIDs.count(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(&AllAnalysesKey) ||
241 PA.PreservedIDs.count(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(&AllAnalysesKey) ||
255 PA.PreservedIDs.count(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`.
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(&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.
297 return NotPreservedAnalysisIDs.empty() &&
298 (PreservedIDs.count(&AllAnalysesKey) || PreservedIDs.count(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
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:49
static AnalysisSetKey * ID()
Definition: Analysis.h:51
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:72
static AnalysisSetKey * ID()
Definition: Analysis.h:74
A checker object that makes it easy to query for whether an analysis or some set covering it is prese...
Definition: Analysis.h:222
bool preserved()
Returns true if the checker's analysis was not abandoned and either.
Definition: Analysis.h:239
bool preservedWhenStateless()
Return true if the checker's analysis was not abandoned, i.e.
Definition: Analysis.h:247
bool preservedSet()
Returns true if the checker's analysis was not abandoned and either.
Definition: Analysis.h:252
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: Analysis.h:114
void preserveSet(AnalysisSetKey *ID)
Mark an analysis set as preserved using its ID.
Definition: Analysis.h:151
bool areAllPreserved() const
Test whether all analyses are preserved (and none are abandoned).
Definition: Analysis.h:281
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
bool allAnalysesInSetPreserved() const
Directly test whether a set of analyses is preserved.
Definition: Analysis.h:289
PreservedAnalysisChecker getChecker(AnalysisKey *ID) const
Build a checker for this PreservedAnalyses and the specified analysis ID.
Definition: Analysis.h:273
void intersect(const PreservedAnalyses &Arg)
Intersect this set with another in place.
Definition: Analysis.h:182
void intersect(PreservedAnalyses &&Arg)
Intersect this set with a temporary other set in place.
Definition: Analysis.h:203
void abandon(AnalysisKey *ID)
Mark an analysis as abandoned using its ID.
Definition: Analysis.h:173
bool allAnalysesInSetPreserved(AnalysisSetKey *SetID) const
Directly test whether a set of analyses is preserved.
Definition: Analysis.h:296
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:146
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: Analysis.h:264
void preserve(AnalysisKey *ID)
Given an analysis's ID, mark the analysis as preserved, adding it to the set.
Definition: Analysis.h:135
void abandon()
Mark an analysis as abandoned.
Definition: Analysis.h:164
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:131
static PreservedAnalyses allInSet()
Construct a preserved analyses object with a single preserved set.
Definition: Analysis.h:124
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:436
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:368
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:442
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:503
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:1914
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:28
A special type used to provide an address that identifies a set of related analyses.
Definition: Analysis.h:38