1 //===- llvm/Analysis/AssumptionCache.h - Track @llvm.assume ---*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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).
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_ANALYSIS_ASSUMPTIONCACHE_H
17 #define LLVM_ANALYSIS_ASSUMPTIONCACHE_H
19 #include "llvm/ADT/ArrayRef.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/SmallSet.h"
22 #include "llvm/IR/Function.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/PassManager.h"
25 #include "llvm/IR/ValueHandle.h"
26 #include "llvm/Pass.h"
31 /// \brief A cache of @llvm.assume calls within a function.
33 /// This cache provides fast lookup of assumptions within a function by caching
34 /// them and amortizing the cost of scanning for them across all queries. Passes
35 /// that create new assumptions are required to call registerAssumption() to
36 /// register any new @llvm.assume calls that they create. Deletions of
37 /// @llvm.assume calls do not require special handling.
38 class AssumptionCache {
39 /// \brief The function for which this cache is handling assumptions.
41 /// We track this to lazily populate our assumptions.
44 /// \brief Vector of weak value handles to calls of the @llvm.assume
46 SmallVector<WeakTrackingVH, 4> AssumeHandles;
48 class AffectedValueCallbackVH final : public CallbackVH {
50 void deleted() override;
51 void allUsesReplacedWith(Value *) override;
54 using DMI = DenseMapInfo<Value *>;
56 AffectedValueCallbackVH(Value *V, AssumptionCache *AC = nullptr)
57 : CallbackVH(V), AC(AC) {}
60 friend AffectedValueCallbackVH;
62 /// \brief A map of values about which an assumption might be providing
63 /// information to the relevant set of assumptions.
64 using AffectedValuesMap =
65 DenseMap<AffectedValueCallbackVH, SmallVector<WeakTrackingVH, 1>,
66 AffectedValueCallbackVH::DMI>;
67 AffectedValuesMap AffectedValues;
69 /// Get the vector of assumptions which affect a value from the cache.
70 SmallVector<WeakTrackingVH, 1> &getOrInsertAffectedValues(Value *V);
72 /// Copy affected values in the cache for OV to be affected values for NV.
73 void copyAffectedValuesInCache(Value *OV, Value *NV);
75 /// \brief Flag tracking whether we have scanned the function yet.
77 /// We want to be as lazy about this as possible, and so we scan the function
78 /// at the last moment.
81 /// \brief Scan the function for assumptions and add them to the cache.
85 /// \brief Construct an AssumptionCache from a function by scanning all of
87 AssumptionCache(Function &F) : F(F), Scanned(false) {}
89 /// This cache is designed to be self-updating and so it should never be
91 bool invalidate(Function &, const PreservedAnalyses &,
92 FunctionAnalysisManager::Invalidator &) {
96 /// \brief Add an @llvm.assume intrinsic to this function's cache.
98 /// The call passed in must be an instruction within this function and must
99 /// not already be in the cache.
100 void registerAssumption(CallInst *CI);
102 /// \brief Update the cache of values being affected by this assumption (i.e.
103 /// the values about which this assumption provides information).
104 void updateAffectedValues(CallInst *CI);
106 /// \brief Clear the cache of @llvm.assume intrinsics for a function.
108 /// It will be re-scanned the next time it is requested.
110 AssumeHandles.clear();
111 AffectedValues.clear();
115 /// \brief Access the list of assumption handles currently tracked for this
118 /// Note that these produce weak handles that may be null. The caller must
119 /// handle that case.
120 /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
121 /// when we can write that to filter out the null values. Then caller code
122 /// will become simpler.
123 MutableArrayRef<WeakTrackingVH> assumptions() {
126 return AssumeHandles;
129 /// \brief Access the list of assumptions which affect this value.
130 MutableArrayRef<WeakTrackingVH> assumptionsFor(const Value *V) {
134 auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
135 if (AVI == AffectedValues.end())
136 return MutableArrayRef<WeakTrackingVH>();
142 /// \brief A function analysis which provides an \c AssumptionCache.
144 /// This analysis is intended for use with the new pass manager and will vend
145 /// assumption caches for a given function.
146 class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> {
147 friend AnalysisInfoMixin<AssumptionAnalysis>;
148 static AnalysisKey Key;
151 typedef AssumptionCache Result;
153 AssumptionCache run(Function &F, FunctionAnalysisManager &) {
154 return AssumptionCache(F);
158 /// \brief Printer pass for the \c AssumptionAnalysis results.
159 class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> {
163 explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
164 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
167 /// \brief An immutable pass that tracks lazily created \c AssumptionCache
170 /// This is essentially a workaround for the legacy pass manager's weaknesses
171 /// which associates each assumption cache with Function and clears it if the
172 /// function is deleted. The nature of the AssumptionCache is that it is not
173 /// invalidated by any changes to the function body and so this is sufficient
174 /// to be conservatively correct.
175 class AssumptionCacheTracker : public ImmutablePass {
176 /// A callback value handle applied to function objects, which we use to
177 /// delete our cache of intrinsics for a function when it is deleted.
178 class FunctionCallbackVH final : public CallbackVH {
179 AssumptionCacheTracker *ACT;
180 void deleted() override;
183 typedef DenseMapInfo<Value *> DMI;
185 FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
186 : CallbackVH(V), ACT(ACT) {}
189 friend FunctionCallbackVH;
191 typedef DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>,
192 FunctionCallbackVH::DMI> FunctionCallsMap;
193 FunctionCallsMap AssumptionCaches;
196 /// \brief Get the cached assumptions for a function.
198 /// If no assumptions are cached, this will scan the function. Otherwise, the
199 /// existing cache will be returned.
200 AssumptionCache &getAssumptionCache(Function &F);
202 AssumptionCacheTracker();
203 ~AssumptionCacheTracker() override;
205 void releaseMemory() override {
207 AssumptionCaches.shrink_and_clear();
210 void verifyAnalysis() const override;
211 bool doFinalization(Module &) override {
216 static char ID; // Pass identification, replacement for typeid
219 } // end namespace llvm