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/SmallSet.h" 22 #include "llvm/IR/Function.h" 23 #include "llvm/IR/Instructions.h" 24 #include "llvm/IR/ValueHandle.h" 25 #include "llvm/IR/PassManager.h" 26 #include "llvm/Pass.h" 27 #include <memory> 28 29 namespace llvm { 30 31 /// \brief A cache of @llvm.assume calls within a function. 32 /// 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. The 35 /// cache is also conservatively self-updating so that it will never return 36 /// incorrect results about a function even as the function is being mutated. 37 /// However, flushing the cache and rebuilding it (or explicitly updating it) 38 /// may allow it to discover new assumptions. 39 class AssumptionCache { 40 /// \brief The function for which this cache is handling assumptions. 41 /// 42 /// We track this to lazily populate our assumptions. 43 Function &F; 44 45 /// \brief Vector of weak value handles to calls of the @llvm.assume 46 /// intrinsic. 47 SmallVector<WeakVH, 4> AssumeHandles; 48 49 /// \brief Flag tracking whether we have scanned the function yet. 50 /// 51 /// We want to be as lazy about this as possible, and so we scan the function 52 /// at the last moment. 53 bool Scanned; 54 55 /// \brief Scan the function for assumptions and add them to the cache. 56 void scanFunction(); 57 58 public: 59 /// \brief Construct an AssumptionCache from a function by scanning all of 60 /// its instructions. AssumptionCache(Function & F)61 AssumptionCache(Function &F) : F(F), Scanned(false) {} 62 63 /// \brief Add an @llvm.assume intrinsic to this function's cache. 64 /// 65 /// The call passed in must be an instruction within this function and must 66 /// not already be in the cache. 67 void registerAssumption(CallInst *CI); 68 69 /// \brief Clear the cache of @llvm.assume intrinsics for a function. 70 /// 71 /// It will be re-scanned the next time it is requested. clear()72 void clear() { 73 AssumeHandles.clear(); 74 Scanned = false; 75 } 76 77 /// \brief Access the list of assumption handles currently tracked for this 78 /// function. 79 /// 80 /// Note that these produce weak handles that may be null. The caller must 81 /// handle that case. 82 /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>> 83 /// when we can write that to filter out the null values. Then caller code 84 /// will become simpler. assumptions()85 MutableArrayRef<WeakVH> assumptions() { 86 if (!Scanned) 87 scanFunction(); 88 return AssumeHandles; 89 } 90 }; 91 92 /// \brief A function analysis which provides an \c AssumptionCache. 93 /// 94 /// This analysis is intended for use with the new pass manager and will vend 95 /// assumption caches for a given function. 96 class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> { 97 friend AnalysisInfoMixin<AssumptionAnalysis>; 98 static char PassID; 99 100 public: 101 typedef AssumptionCache Result; 102 AssumptionAnalysis()103 AssumptionAnalysis() {} AssumptionAnalysis(const AssumptionAnalysis & Arg)104 AssumptionAnalysis(const AssumptionAnalysis &Arg) {} AssumptionAnalysis(AssumptionAnalysis && Arg)105 AssumptionAnalysis(AssumptionAnalysis &&Arg) {} 106 AssumptionAnalysis &operator=(const AssumptionAnalysis &RHS) { return *this; } 107 AssumptionAnalysis &operator=(AssumptionAnalysis &&RHS) { return *this; } 108 run(Function & F,FunctionAnalysisManager &)109 AssumptionCache run(Function &F, FunctionAnalysisManager &) { 110 return AssumptionCache(F); 111 } 112 }; 113 114 /// \brief Printer pass for the \c AssumptionAnalysis results. 115 class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> { 116 raw_ostream &OS; 117 118 public: AssumptionPrinterPass(raw_ostream & OS)119 explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {} 120 PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); 121 }; 122 123 /// \brief An immutable pass that tracks lazily created \c AssumptionCache 124 /// objects. 125 /// 126 /// This is essentially a workaround for the legacy pass manager's weaknesses 127 /// which associates each assumption cache with Function and clears it if the 128 /// function is deleted. The nature of the AssumptionCache is that it is not 129 /// invalidated by any changes to the function body and so this is sufficient 130 /// to be conservatively correct. 131 class AssumptionCacheTracker : public ImmutablePass { 132 /// A callback value handle applied to function objects, which we use to 133 /// delete our cache of intrinsics for a function when it is deleted. 134 class FunctionCallbackVH final : public CallbackVH { 135 AssumptionCacheTracker *ACT; 136 void deleted() override; 137 138 public: 139 typedef DenseMapInfo<Value *> DMI; 140 141 FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr) CallbackVH(V)142 : CallbackVH(V), ACT(ACT) {} 143 }; 144 145 friend FunctionCallbackVH; 146 147 typedef DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>, 148 FunctionCallbackVH::DMI> FunctionCallsMap; 149 FunctionCallsMap AssumptionCaches; 150 151 public: 152 /// \brief Get the cached assumptions for a function. 153 /// 154 /// If no assumptions are cached, this will scan the function. Otherwise, the 155 /// existing cache will be returned. 156 AssumptionCache &getAssumptionCache(Function &F); 157 158 AssumptionCacheTracker(); 159 ~AssumptionCacheTracker() override; 160 releaseMemory()161 void releaseMemory() override { AssumptionCaches.shrink_and_clear(); } 162 163 void verifyAnalysis() const override; doFinalization(Module &)164 bool doFinalization(Module &) override { 165 verifyAnalysis(); 166 return false; 167 } 168 169 static char ID; // Pass identification, replacement for typeid 170 }; 171 172 } // end namespace llvm 173 174 #endif 175