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