LLVM 17.0.0git
AssumptionCache.h
Go to the documentation of this file.
1//===- llvm/Analysis/AssumptionCache.h - Track @llvm.assume -----*- 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//
9// This file contains a pass that keeps track of @llvm.assume intrinsics in
10// the functions of a module (allowing assumptions within any function to be
11// found cheaply by other parts of the optimizer).
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ANALYSIS_ASSUMPTIONCACHE_H
16#define LLVM_ANALYSIS_ASSUMPTIONCACHE_H
17
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/DenseMap.h"
22#include "llvm/IR/PassManager.h"
23#include "llvm/IR/ValueHandle.h"
24#include "llvm/Pass.h"
25#include <memory>
26
27namespace llvm {
28
29class CondGuardInst;
30class Function;
31class raw_ostream;
32class TargetTransformInfo;
33class Value;
34
35/// A cache of \@llvm.assume calls within a function.
36///
37/// This cache provides fast lookup of assumptions within a function by caching
38/// them and amortizing the cost of scanning for them across all queries. Passes
39/// that create new assumptions are required to call registerAssumption() to
40/// register any new \@llvm.assume calls that they create. Deletions of
41/// \@llvm.assume calls do not require special handling.
43public:
44 /// Value of ResultElem::Index indicating that the argument to the call of the
45 /// llvm.assume.
46 enum : unsigned { ExprResultIdx = std::numeric_limits<unsigned>::max() };
47
48 struct ResultElem {
50
51 /// contains either ExprResultIdx or the index of the operand bundle
52 /// containing the knowledge.
53 unsigned Index;
54 operator Value *() const { return Assume; }
55 };
56
57private:
58 /// The function for which this cache is handling assumptions.
59 ///
60 /// We track this to lazily populate our assumptions.
61 Function &F;
62
64
65 /// Vector of weak value handles to calls of the \@llvm.assume
66 /// intrinsic.
67 SmallVector<ResultElem, 4> AssumeHandles;
68
69 class AffectedValueCallbackVH final : public CallbackVH {
71
72 void deleted() override;
73 void allUsesReplacedWith(Value *) override;
74
75 public:
76 using DMI = DenseMapInfo<Value *>;
77
78 AffectedValueCallbackVH(Value *V, AssumptionCache *AC = nullptr)
79 : CallbackVH(V), AC(AC) {}
80 };
81
82 friend AffectedValueCallbackVH;
83
84 /// A map of values about which an assumption might be providing
85 /// information to the relevant set of assumptions.
86 using AffectedValuesMap =
87 DenseMap<AffectedValueCallbackVH, SmallVector<ResultElem, 1>,
88 AffectedValueCallbackVH::DMI>;
89 AffectedValuesMap AffectedValues;
90
91 /// Get the vector of assumptions which affect a value from the cache.
92 SmallVector<ResultElem, 1> &getOrInsertAffectedValues(Value *V);
93
94 /// Move affected values in the cache for OV to be affected values for NV.
95 void transferAffectedValuesInCache(Value *OV, Value *NV);
96
97 /// Flag tracking whether we have scanned the function yet.
98 ///
99 /// We want to be as lazy about this as possible, and so we scan the function
100 /// at the last moment.
101 bool Scanned = false;
102
103 /// Scan the function for assumptions and add them to the cache.
104 void scanFunction();
105
106public:
107 /// Construct an AssumptionCache from a function by scanning all of
108 /// its instructions.
110 : F(F), TTI(TTI) {}
111
112 /// This cache is designed to be self-updating and so it should never be
113 /// invalidated.
116 return false;
117 }
118
119 /// Add an \@llvm.assume intrinsic to this function's cache.
120 ///
121 /// The call passed in must be an instruction within this function and must
122 /// not already be in the cache.
124
125 /// Remove an \@llvm.assume intrinsic from this function's cache if it has
126 /// been added to the cache earlier.
128
129 /// Update the cache of values being affected by this assumption (i.e.
130 /// the values about which this assumption provides information).
132
133 /// Clear the cache of \@llvm.assume intrinsics for a function.
134 ///
135 /// It will be re-scanned the next time it is requested.
136 void clear() {
137 AssumeHandles.clear();
138 AffectedValues.clear();
139 Scanned = false;
140 }
141
142 /// Access the list of assumption handles currently tracked for this
143 /// function.
144 ///
145 /// Note that these produce weak handles that may be null. The caller must
146 /// handle that case.
147 /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
148 /// when we can write that to filter out the null values. Then caller code
149 /// will become simpler.
151 if (!Scanned)
152 scanFunction();
153 return AssumeHandles;
154 }
155
156 /// Access the list of assumptions which affect this value.
158 if (!Scanned)
159 scanFunction();
160
161 auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
162 if (AVI == AffectedValues.end())
164
165 return AVI->second;
166 }
167};
168
169/// A function analysis which provides an \c AssumptionCache.
170///
171/// This analysis is intended for use with the new pass manager and will vend
172/// assumption caches for a given function.
173class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> {
175
176 static AnalysisKey Key;
177
178public:
180
182};
183
184/// Printer pass for the \c AssumptionAnalysis results.
185class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> {
186 raw_ostream &OS;
187
188public:
189 explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
190
192};
193
194/// An immutable pass that tracks lazily created \c AssumptionCache
195/// objects.
196///
197/// This is essentially a workaround for the legacy pass manager's weaknesses
198/// which associates each assumption cache with Function and clears it if the
199/// function is deleted. The nature of the AssumptionCache is that it is not
200/// invalidated by any changes to the function body and so this is sufficient
201/// to be conservatively correct.
203 /// A callback value handle applied to function objects, which we use to
204 /// delete our cache of intrinsics for a function when it is deleted.
205 class FunctionCallbackVH final : public CallbackVH {
207
208 void deleted() override;
209
210 public:
211 using DMI = DenseMapInfo<Value *>;
212
213 FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
214 : CallbackVH(V), ACT(ACT) {}
215 };
216
217 friend FunctionCallbackVH;
218
219 using FunctionCallsMap =
222
223 FunctionCallsMap AssumptionCaches;
224
225public:
226 /// Get the cached assumptions for a function.
227 ///
228 /// If no assumptions are cached, this will scan the function. Otherwise, the
229 /// existing cache will be returned.
231
232 /// Return the cached assumptions for a function if it has already been
233 /// scanned. Otherwise return nullptr.
235
238
239 void releaseMemory() override {
241 AssumptionCaches.shrink_and_clear();
242 }
243
244 void verifyAnalysis() const override;
245
246 bool doFinalization(Module &) override {
248 return false;
249 }
250
251 static char ID; // Pass identification, replacement for typeid
252};
253
254template<> struct simplify_type<AssumptionCache::ResultElem> {
255 using SimpleType = Value *;
256
258 return Val;
259 }
260};
261template<> struct simplify_type<const AssumptionCache::ResultElem> {
262 using SimpleType = /*const*/ Value *;
263
265 return Val;
266 }
267};
268
269} // end namespace llvm
270
271#endif // LLVM_ANALYSIS_ASSUMPTIONCACHE_H
aarch64 promote const
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
#define F(x, y, z)
Definition: MD5.cpp:55
This header defines various interfaces for pass management in LLVM.
This file defines the SmallVector class.
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
A function analysis which provides an AssumptionCache.
AssumptionCache run(Function &F, FunctionAnalysisManager &)
An immutable pass that tracks lazily created AssumptionCache objects.
bool doFinalization(Module &) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
AssumptionCache * lookupAssumptionCache(Function &F)
Return the cached assumptions for a function if it has already been scanned.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
AssumptionCache & getAssumptionCache(Function &F)
Get the cached assumptions for a function.
A cache of @llvm.assume calls within a function.
void updateAffectedValues(CondGuardInst *CI)
Update the cache of values being affected by this assumption (i.e.
void clear()
Clear the cache of @llvm.assume intrinsics for a function.
bool invalidate(Function &, const PreservedAnalyses &, FunctionAnalysisManager::Invalidator &)
This cache is designed to be self-updating and so it should never be invalidated.
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
void registerAssumption(CondGuardInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
AssumptionCache(Function &F, TargetTransformInfo *TTI=nullptr)
Construct an AssumptionCache from a function by scanning all of its instructions.
MutableArrayRef< ResultElem > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.
void unregisterAssumption(CondGuardInst *CI)
Remove an @llvm.assume intrinsic from this function's cache if it has been added to the cache earlier...
Printer pass for the AssumptionAnalysis results.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
AssumptionPrinterPass(raw_ostream &OS)
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
This represents intrinsics that guard a condition.
void shrink_and_clear()
Definition: DenseMap.h:820
ImmutablePass class - This class is used to provide information that does not need to be run.
Definition: Pass.h:279
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:305
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
LLVM Value Representation.
Definition: Value.h:74
A nullable Value handle that is nullable.
Definition: ValueHandle.h:144
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
unsigned Index
contains either ExprResultIdx or the index of the operand bundle containing the knowledge.
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:51
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
static SimpleType getSimplifiedValue(AssumptionCache::ResultElem &Val)
static SimpleType getSimplifiedValue(const AssumptionCache::ResultElem &Val)
Define a template that can be specialized by smart pointers to reflect the fact that they are automat...
Definition: Casting.h:34