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