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/Support/Compiler.h"
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.
73class CFGAnalyses {
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/// ```
112class PreservedAnalyses {
113public:
114 /// Convenience factory function for the empty preserved set.
115 static PreservedAnalyses none() { return PreservedAnalyses(); }
116
117 /// Construct a special preserved set that preserves all passes.
118 static PreservedAnalyses all() {
119 PreservedAnalyses PA;
120 PA.PreservedIDs.insert(Ptr: &AllAnalysesKey);
121 return PA;
122 }
123
124 /// Construct a preserved analyses object with a single preserved set.
125 template <typename AnalysisSetT> static PreservedAnalyses allInSet() {
126 PreservedAnalyses PA;
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.
139 PreservedAnalyses &preserve(AnalysisKey *ID) {
140 // Clear this ID from the explicit not-preserved set if present.
141 NotPreservedAnalysisIDs.erase(Ptr: ID);
142
143 // If we're not already preserving all analyses (other than those in
144 // NotPreservedAnalysisIDs).
145 if (!areAllPreserved())
146 PreservedIDs.insert(Ptr: 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.
157 PreservedAnalyses &preserveSet(AnalysisSetKey *ID) {
158 // If we're not already in the saturated 'all' state, add this set.
159 if (!areAllPreserved())
160 PreservedIDs.insert(Ptr: 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.
183 PreservedAnalyses &abandon(AnalysisKey *ID) {
184 PreservedIDs.erase(Ptr: ID);
185 NotPreservedAnalysisIDs.insert(Ptr: 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(Ptr: ID);
204 NotPreservedAnalysisIDs.insert(Ptr: ID);
205 }
206 PreservedIDs.remove_if(
207 P: [&](void *ID) { return !Arg.PreservedIDs.contains(Ptr: 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.
214 void intersect(PreservedAnalyses &&Arg) {
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(Ptr: ID);
225 NotPreservedAnalysisIDs.insert(Ptr: ID);
226 }
227 PreservedIDs.remove_if(
228 P: [&](void *ID) { return !Arg.PreservedIDs.contains(Ptr: 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.
233 class PreservedAnalysisChecker {
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.
243 PreservedAnalysisChecker(const PreservedAnalyses &PA, AnalysisKey *ID)
244 : PA(PA), ID(ID), IsAbandoned(PA.NotPreservedAnalysisIDs.count(Ptr: 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(Ptr: &AllAnalysesKey) ||
252 PA.PreservedIDs.count(Ptr: 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(Ptr: &AllAnalysesKey) ||
266 PA.PreservedIDs.count(Ptr: 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`.
284 PreservedAnalysisChecker getChecker(AnalysisKey *ID) const {
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(Ptr: &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.
307 bool allAnalysesInSetPreserved(AnalysisSetKey *SetID) const {
308 return NotPreservedAnalysisIDs.empty() &&
309 (PreservedIDs.count(Ptr: &AllAnalysesKey) || PreservedIDs.count(Ptr: 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
331

Provided by KDAB

Privacy Policy
Update your C++ knowledge – Modern C++11/14/17 Training
Find out more

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