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/ValueHandle.h"
25 #include "llvm/Pass.h"
30 // FIXME: Replace this brittle forward declaration with the include of the new
31 // PassManager.h when doing so doesn't break the PassManagerBuilder.
32 template <typename IRUnitT> class AnalysisManager;
33 class PreservedAnalyses;
35 /// \brief A cache of @llvm.assume calls within a function.
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. The
39 /// cache is also conservatively self-updating so that it will never return
40 /// incorrect results about a function even as the function is being mutated.
41 /// However, flushing the cache and rebuilding it (or explicitly updating it)
42 /// may allow it to discover new assumptions.
43 class AssumptionCache {
44 /// \brief The function for which this cache is handling assumptions.
46 /// We track this to lazily populate our assumptions.
49 /// \brief Vector of weak value handles to calls of the @llvm.assume
51 SmallVector<WeakVH, 4> AssumeHandles;
53 /// \brief Flag tracking whether we have scanned the function yet.
55 /// We want to be as lazy about this as possible, and so we scan the function
56 /// at the last moment.
59 /// \brief Scan the function for assumptions and add them to the cache.
63 /// \brief Construct an AssumptionCache from a function by scanning all of
65 AssumptionCache(Function &F) : F(F), Scanned(false) {}
67 /// \brief Add an @llvm.assume intrinsic to this function's cache.
69 /// The call passed in must be an instruction within this function and must
70 /// not already be in the cache.
71 void registerAssumption(CallInst *CI);
73 /// \brief Clear the cache of @llvm.assume intrinsics for a function.
75 /// It will be re-scanned the next time it is requested.
77 AssumeHandles.clear();
81 /// \brief Access the list of assumption handles currently tracked for this
84 /// Note that these produce weak handles that may be null. The caller must
86 /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
87 /// when we can write that to filter out the null values. Then caller code
88 /// will become simpler.
89 MutableArrayRef<WeakVH> assumptions() {
96 /// \brief A function analysis which provides an \c AssumptionCache.
98 /// This analysis is intended for use with the new pass manager and will vend
99 /// assumption caches for a given function.
100 class AssumptionAnalysis {
104 typedef AssumptionCache Result;
106 /// \brief Opaque, unique identifier for this analysis pass.
107 static void *ID() { return (void *)&PassID; }
109 /// \brief Provide a name for the analysis for debugging and logging.
110 static StringRef name() { return "AssumptionAnalysis"; }
112 AssumptionAnalysis() {}
113 AssumptionAnalysis(const AssumptionAnalysis &Arg) {}
114 AssumptionAnalysis(AssumptionAnalysis &&Arg) {}
115 AssumptionAnalysis &operator=(const AssumptionAnalysis &RHS) { return *this; }
116 AssumptionAnalysis &operator=(AssumptionAnalysis &&RHS) { return *this; }
118 AssumptionCache run(Function &F) { return AssumptionCache(F); }
121 /// \brief Printer pass for the \c AssumptionAnalysis results.
122 class AssumptionPrinterPass {
126 explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
127 PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
129 static StringRef name() { return "AssumptionPrinterPass"; }
132 /// \brief An immutable pass that tracks lazily created \c AssumptionCache
135 /// This is essentially a workaround for the legacy pass manager's weaknesses
136 /// which associates each assumption cache with Function and clears it if the
137 /// function is deleted. The nature of the AssumptionCache is that it is not
138 /// invalidated by any changes to the function body and so this is sufficient
139 /// to be conservatively correct.
140 class AssumptionCacheTracker : public ImmutablePass {
141 /// A callback value handle applied to function objects, which we use to
142 /// delete our cache of intrinsics for a function when it is deleted.
143 class FunctionCallbackVH final : public CallbackVH {
144 AssumptionCacheTracker *ACT;
145 void deleted() override;
148 typedef DenseMapInfo<Value *> DMI;
150 FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
151 : CallbackVH(V), ACT(ACT) {}
154 friend FunctionCallbackVH;
156 typedef DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>,
157 FunctionCallbackVH::DMI> FunctionCallsMap;
158 FunctionCallsMap AssumptionCaches;
161 /// \brief Get the cached assumptions for a function.
163 /// If no assumptions are cached, this will scan the function. Otherwise, the
164 /// existing cache will be returned.
165 AssumptionCache &getAssumptionCache(Function &F);
167 AssumptionCacheTracker();
168 ~AssumptionCacheTracker() override;
170 void releaseMemory() override { AssumptionCaches.shrink_and_clear(); }
172 void verifyAnalysis() const override;
173 bool doFinalization(Module &) override {
178 static char ID; // Pass identification, replacement for typeid
181 } // end namespace llvm