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
27namespace llvm {
28
29class AssumeInst;
30class Function;
31class raw_ostream;
32class 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.
41class AssumptionCache {
42public:
43 /// Value of ResultElem::Index indicating that the argument to the call of the
44 /// llvm.assume.
45 enum : unsigned { ExprResultIdx = std::numeric_limits<unsigned>::max() };
46
47 struct ResultElem {
48 WeakVH Assume;
49
50 /// contains either ExprResultIdx or the index of the operand bundle
51 /// containing the knowledge.
52 unsigned Index;
53 operator Value *() const { return Assume; }
54 };
55
56private:
57 /// The function for which this cache is handling assumptions.
58 ///
59 /// We track this to lazily populate our assumptions.
60 Function &F;
61
62 /// Vector of weak value handles to calls of the \@llvm.assume
63 /// intrinsic.
64 SmallVector<ResultElem, 4> AssumeHandles;
65
66 class AffectedValueCallbackVH final : public CallbackVH {
67 AssumptionCache *AC;
68
69 void deleted() override;
70 void allUsesReplacedWith(Value *) override;
71
72 public:
73 using DMI = DenseMapInfo<Value *>;
74
75 AffectedValueCallbackVH(Value *V, AssumptionCache *AC = nullptr)
76 : CallbackVH(V), AC(AC) {}
77 };
78
79 friend AffectedValueCallbackVH;
80
81 /// A map of values about which an assumption might be providing
82 /// information to the relevant set of assumptions.
83 using AffectedValuesMap =
84 DenseMap<AffectedValueCallbackVH, SmallVector<ResultElem, 1>,
85 AffectedValueCallbackVH::DMI>;
86 AffectedValuesMap AffectedValues;
87
88 /// Get the vector of assumptions which affect a value from the cache.
89 SmallVector<ResultElem, 1> &getOrInsertAffectedValues(Value *V);
90
91 /// Move affected values in the cache for OV to be affected values for NV.
92 void transferAffectedValuesInCache(Value *OV, Value *NV);
93
94 /// Flag tracking whether we have scanned the function yet.
95 ///
96 /// We want to be as lazy about this as possible, and so we scan the function
97 /// at the last moment.
98 bool Scanned = false;
99
100 /// Scan the function for assumptions and add them to the cache.
101 void scanFunction();
102
103public:
104 /// Construct an AssumptionCache from a function by scanning all of
105 /// its instructions.
106 AssumptionCache(Function &F) : F(F) {}
107
108 /// This cache is designed to be self-updating and so it should never be
109 /// invalidated.
110 bool invalidate(Function &, const PreservedAnalyses &,
111 FunctionAnalysisManager::Invalidator &) {
112 return false;
113 }
114
115 /// Add an \@llvm.assume intrinsic to this function's cache.
116 ///
117 /// The call passed in must be an instruction within this function and must
118 /// not already be in the cache.
119 void registerAssumption(AssumeInst *CI);
120
121 /// Remove an \@llvm.assume intrinsic from this function's cache if it has
122 /// been added to the cache earlier.
123 void unregisterAssumption(AssumeInst *CI);
124
125 /// Update the cache of values being affected by this assumption (i.e.
126 /// the values about which this assumption provides information).
127 void updateAffectedValues(AssumeInst *CI);
128
129 /// Clear the cache of \@llvm.assume intrinsics for a function.
130 ///
131 /// It will be re-scanned the next time it is requested.
132 void clear() {
133 AssumeHandles.clear();
134 AffectedValues.clear();
135 Scanned = false;
136 }
137
138 /// Access the list of assumption handles currently tracked for this
139 /// function.
140 ///
141 /// Note that these produce weak handles that may be null. The caller must
142 /// handle that case.
143 /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
144 /// when we can write that to filter out the null values. Then caller code
145 /// will become simpler.
146 MutableArrayRef<ResultElem> assumptions() {
147 if (!Scanned)
148 scanFunction();
149 return AssumeHandles;
150 }
151
152 /// Access the list of assumptions which affect this value.
153 MutableArrayRef<ResultElem> assumptionsFor(const Value *V) {
154 if (!Scanned)
155 scanFunction();
156
157 auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
158 if (AVI == AffectedValues.end())
159 return MutableArrayRef<ResultElem>();
160
161 return AVI->second;
162 }
163};
164
165/// A function analysis which provides an \c AssumptionCache.
166///
167/// This analysis is intended for use with the new pass manager and will vend
168/// assumption caches for a given function.
169class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> {
170 friend AnalysisInfoMixin<AssumptionAnalysis>;
171
172 static AnalysisKey Key;
173
174public:
175 using Result = AssumptionCache;
176
177 AssumptionCache run(Function &F, FunctionAnalysisManager &) {
178 return AssumptionCache(F);
179 }
180};
181
182/// Printer pass for the \c AssumptionAnalysis results.
183class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> {
184 raw_ostream &OS;
185
186public:
187 explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
188
189 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
190};
191
192/// An immutable pass that tracks lazily created \c AssumptionCache
193/// objects.
194///
195/// This is essentially a workaround for the legacy pass manager's weaknesses
196/// which associates each assumption cache with Function and clears it if the
197/// function is deleted. The nature of the AssumptionCache is that it is not
198/// invalidated by any changes to the function body and so this is sufficient
199/// to be conservatively correct.
200class AssumptionCacheTracker : public ImmutablePass {
201 /// A callback value handle applied to function objects, which we use to
202 /// delete our cache of intrinsics for a function when it is deleted.
203 class FunctionCallbackVH final : public CallbackVH {
204 AssumptionCacheTracker *ACT;
205
206 void deleted() override;
207
208 public:
209 using DMI = DenseMapInfo<Value *>;
210
211 FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
212 : CallbackVH(V), ACT(ACT) {}
213 };
214
215 friend FunctionCallbackVH;
216
217 using FunctionCallsMap =
218 DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>,
219 FunctionCallbackVH::DMI>;
220
221 FunctionCallsMap AssumptionCaches;
222
223public:
224 /// Get the cached assumptions for a function.
225 ///
226 /// If no assumptions are cached, this will scan the function. Otherwise, the
227 /// existing cache will be returned.
228 AssumptionCache &getAssumptionCache(Function &F);
229
230 /// Return the cached assumptions for a function if it has already been
231 /// scanned. Otherwise return nullptr.
232 AssumptionCache *lookupAssumptionCache(Function &F);
233
234 AssumptionCacheTracker();
235 ~AssumptionCacheTracker() override;
236
237 void releaseMemory() override {
238 verifyAnalysis();
239 AssumptionCaches.shrink_and_clear();
240 }
241
242 void verifyAnalysis() const override;
243
244 bool doFinalization(Module &) override {
245 verifyAnalysis();
246 return false;
247 }
248
249 static char ID; // Pass identification, replacement for typeid
250};
251
252template<> struct simplify_type<AssumptionCache::ResultElem> {
253 using SimpleType = Value *;
254
255 static SimpleType getSimplifiedValue(AssumptionCache::ResultElem &Val) {
256 return Val;
257 }
258};
259template<> struct simplify_type<const AssumptionCache::ResultElem> {
260 using SimpleType = /*const*/ Value *;
261
262 static SimpleType getSimplifiedValue(const AssumptionCache::ResultElem &Val) {
263 return Val;
264 }
265};
266
267} // end namespace llvm
268
269#endif // LLVM_ANALYSIS_ASSUMPTIONCACHE_H
270