Line data Source code
1 : //===- llvm/Analysis/AssumptionCache.h - Track @llvm.assume -----*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file contains a pass that keeps track of @llvm.assume intrinsics in
11 : // the functions of a module (allowing assumptions within any function to be
12 : // found cheaply by other parts of the optimizer).
13 : //
14 : //===----------------------------------------------------------------------===//
15 :
16 : #ifndef LLVM_ANALYSIS_ASSUMPTIONCACHE_H
17 : #define LLVM_ANALYSIS_ASSUMPTIONCACHE_H
18 :
19 : #include "llvm/ADT/ArrayRef.h"
20 : #include "llvm/ADT/DenseMap.h"
21 : #include "llvm/ADT/DenseMapInfo.h"
22 : #include "llvm/ADT/SmallVector.h"
23 : #include "llvm/IR/PassManager.h"
24 : #include "llvm/IR/ValueHandle.h"
25 : #include "llvm/Pass.h"
26 : #include <memory>
27 :
28 : namespace llvm {
29 :
30 : class CallInst;
31 : class Function;
32 : class raw_ostream;
33 : class 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.
42 : class AssumptionCache {
43 : /// The function for which this cache is handling assumptions.
44 : ///
45 : /// We track this to lazily populate our assumptions.
46 : Function &F;
47 :
48 : /// Vector of weak value handles to calls of the \@llvm.assume
49 : /// intrinsic.
50 : SmallVector<WeakTrackingVH, 4> AssumeHandles;
51 :
52 104547 : class AffectedValueCallbackVH final : public CallbackVH {
53 : AssumptionCache *AC;
54 :
55 : void deleted() override;
56 : void allUsesReplacedWith(Value *) override;
57 :
58 : public:
59 : using DMI = DenseMapInfo<Value *>;
60 :
61 : AffectedValueCallbackVH(Value *V, AssumptionCache *AC = nullptr)
62 59347 : : CallbackVH(V), AC(AC) {}
63 : };
64 :
65 : friend AffectedValueCallbackVH;
66 :
67 : /// A map of values about which an assumption might be providing
68 : /// information to the relevant set of assumptions.
69 : using AffectedValuesMap =
70 : DenseMap<AffectedValueCallbackVH, SmallVector<WeakTrackingVH, 1>,
71 : AffectedValueCallbackVH::DMI>;
72 : AffectedValuesMap AffectedValues;
73 :
74 : /// Get the vector of assumptions which affect a value from the cache.
75 : SmallVector<WeakTrackingVH, 1> &getOrInsertAffectedValues(Value *V);
76 :
77 : /// Copy affected values in the cache for OV to be affected values for NV.
78 : void copyAffectedValuesInCache(Value *OV, Value *NV);
79 :
80 : /// Flag tracking whether we have scanned the function yet.
81 : ///
82 : /// We want to be as lazy about this as possible, and so we scan the function
83 : /// at the last moment.
84 : bool Scanned = false;
85 :
86 : /// Scan the function for assumptions and add them to the cache.
87 : void scanFunction();
88 :
89 : public:
90 : /// Construct an AssumptionCache from a function by scanning all of
91 : /// its instructions.
92 2293181 : AssumptionCache(Function &F) : F(F) {}
93 :
94 : /// This cache is designed to be self-updating and so it should never be
95 : /// invalidated.
96 0 : bool invalidate(Function &, const PreservedAnalyses &,
97 : FunctionAnalysisManager::Invalidator &) {
98 0 : return false;
99 : }
100 :
101 : /// Add an \@llvm.assume intrinsic to this function's cache.
102 : ///
103 : /// The call passed in must be an instruction within this function and must
104 : /// not already be in the cache.
105 : void registerAssumption(CallInst *CI);
106 :
107 : /// Update the cache of values being affected by this assumption (i.e.
108 : /// the values about which this assumption provides information).
109 : void updateAffectedValues(CallInst *CI);
110 :
111 : /// Clear the cache of \@llvm.assume intrinsics for a function.
112 : ///
113 : /// It will be re-scanned the next time it is requested.
114 : void clear() {
115 : AssumeHandles.clear();
116 : AffectedValues.clear();
117 : Scanned = false;
118 : }
119 :
120 : /// Access the list of assumption handles currently tracked for this
121 : /// function.
122 : ///
123 : /// Note that these produce weak handles that may be null. The caller must
124 : /// handle that case.
125 : /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
126 : /// when we can write that to filter out the null values. Then caller code
127 : /// will become simpler.
128 : MutableArrayRef<WeakTrackingVH> assumptions() {
129 481574 : if (!Scanned)
130 51327 : scanFunction();
131 : return AssumeHandles;
132 : }
133 :
134 : /// Access the list of assumptions which affect this value.
135 65519039 : MutableArrayRef<WeakTrackingVH> assumptionsFor(const Value *V) {
136 65519039 : if (!Scanned)
137 59969 : scanFunction();
138 :
139 65519039 : auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
140 65519039 : if (AVI == AffectedValues.end())
141 65517355 : return MutableArrayRef<WeakTrackingVH>();
142 :
143 1684 : return AVI->second;
144 : }
145 : };
146 :
147 : /// A function analysis which provides an \c AssumptionCache.
148 : ///
149 : /// This analysis is intended for use with the new pass manager and will vend
150 : /// assumption caches for a given function.
151 : class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> {
152 : friend AnalysisInfoMixin<AssumptionAnalysis>;
153 :
154 : static AnalysisKey Key;
155 :
156 : public:
157 : using Result = AssumptionCache;
158 :
159 0 : AssumptionCache run(Function &F, FunctionAnalysisManager &) {
160 0 : return AssumptionCache(F);
161 : }
162 : };
163 :
164 : /// Printer pass for the \c AssumptionAnalysis results.
165 : class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> {
166 : raw_ostream &OS;
167 :
168 : public:
169 1 : explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
170 :
171 : PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
172 : };
173 :
174 : /// An immutable pass that tracks lazily created \c AssumptionCache
175 : /// objects.
176 : ///
177 : /// This is essentially a workaround for the legacy pass manager's weaknesses
178 : /// which associates each assumption cache with Function and clears it if the
179 : /// function is deleted. The nature of the AssumptionCache is that it is not
180 : /// invalidated by any changes to the function body and so this is sufficient
181 : /// to be conservatively correct.
182 153485 : class AssumptionCacheTracker : public ImmutablePass {
183 : /// A callback value handle applied to function objects, which we use to
184 : /// delete our cache of intrinsics for a function when it is deleted.
185 34717120 : class FunctionCallbackVH final : public CallbackVH {
186 : AssumptionCacheTracker *ACT;
187 :
188 : void deleted() override;
189 :
190 : public:
191 : using DMI = DenseMapInfo<Value *>;
192 :
193 : FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
194 23791730 : : CallbackVH(V), ACT(ACT) {}
195 : };
196 :
197 : friend FunctionCallbackVH;
198 :
199 : using FunctionCallsMap =
200 : DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>,
201 : FunctionCallbackVH::DMI>;
202 :
203 : FunctionCallsMap AssumptionCaches;
204 :
205 : public:
206 : /// Get the cached assumptions for a function.
207 : ///
208 : /// If no assumptions are cached, this will scan the function. Otherwise, the
209 : /// existing cache will be returned.
210 : AssumptionCache &getAssumptionCache(Function &F);
211 :
212 : AssumptionCacheTracker();
213 : ~AssumptionCacheTracker() override;
214 :
215 76204 : void releaseMemory() override {
216 76204 : verifyAnalysis();
217 76203 : AssumptionCaches.shrink_and_clear();
218 76204 : }
219 :
220 : void verifyAnalysis() const override;
221 :
222 51147 : bool doFinalization(Module &) override {
223 51147 : verifyAnalysis();
224 51147 : return false;
225 : }
226 :
227 : static char ID; // Pass identification, replacement for typeid
228 : };
229 :
230 : } // end namespace llvm
231 :
232 : #endif // LLVM_ANALYSIS_ASSUMPTIONCACHE_H
|
