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/PassManager.h" 25 #include "llvm/IR/ValueHandle.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. 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. 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<WeakTrackingVH, 4> AssumeHandles; 47 48 class AffectedValueCallbackVH final : public CallbackVH { 49 AssumptionCache *AC; 50 void deleted() override; 51 void allUsesReplacedWith(Value *) override; 52 53 public: 54 using DMI = DenseMapInfo<Value *>; 55 56 AffectedValueCallbackVH(Value *V, AssumptionCache *AC = nullptr) 57 : CallbackVH(V), AC(AC) {} 58 }; 59 60 friend AffectedValueCallbackVH; 61 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; 68 69 /// Get the vector of assumptions which affect a value from the cache. 70 SmallVector<WeakTrackingVH, 1> &getOrInsertAffectedValues(Value *V); 71 72 /// Copy affected values in the cache for OV to be affected values for NV. 73 void copyAffectedValuesInCache(Value *OV, Value *NV); 74 75 /// \brief Flag tracking whether we have scanned the function yet. 76 /// 77 /// We want to be as lazy about this as possible, and so we scan the function 78 /// at the last moment. 79 bool Scanned; 80 81 /// \brief Scan the function for assumptions and add them to the cache. 82 void scanFunction(); 83 84 public: 85 /// \brief Construct an AssumptionCache from a function by scanning all of 86 /// its instructions. 87 AssumptionCache(Function &F) : F(F), Scanned(false) {} 88 89 /// This cache is designed to be self-updating and so it should never be 90 /// invalidated. 91 bool invalidate(Function &, const PreservedAnalyses &, 92 FunctionAnalysisManager::Invalidator &) { 93 return false; 94 } 95 96 /// \brief Add an @llvm.assume intrinsic to this function's cache. 97 /// 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); 101 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); 105 106 /// \brief Clear the cache of @llvm.assume intrinsics for a function. 107 /// 108 /// It will be re-scanned the next time it is requested. 109 void clear() { 110 AssumeHandles.clear(); 111 AffectedValues.clear(); 112 Scanned = false; 113 } 114 115 /// \brief Access the list of assumption handles currently tracked for this 116 /// function. 117 /// 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() { 124 if (!Scanned) 125 scanFunction(); 126 return AssumeHandles; 127 } 128 129 /// \brief Access the list of assumptions which affect this value. 130 MutableArrayRef<WeakTrackingVH> assumptionsFor(const Value *V) { 131 if (!Scanned) 132 scanFunction(); 133 134 auto AVI = AffectedValues.find_as(const_cast<Value *>(V)); 135 if (AVI == AffectedValues.end()) 136 return MutableArrayRef<WeakTrackingVH>(); 137 138 return AVI->second; 139 } 140 }; 141 142 /// \brief A function analysis which provides an \c AssumptionCache. 143 /// 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; 149 150 public: 151 typedef AssumptionCache Result; 152 153 AssumptionCache run(Function &F, FunctionAnalysisManager &) { 154 return AssumptionCache(F); 155 } 156 }; 157 158 /// \brief Printer pass for the \c AssumptionAnalysis results. 159 class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> { 160 raw_ostream &OS; 161 162 public: 163 explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {} 164 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 165 }; 166 167 /// \brief An immutable pass that tracks lazily created \c AssumptionCache 168 /// objects. 169 /// 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; 181 182 public: 183 typedef DenseMapInfo<Value *> DMI; 184 185 FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr) 186 : CallbackVH(V), ACT(ACT) {} 187 }; 188 189 friend FunctionCallbackVH; 190 191 typedef DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>, 192 FunctionCallbackVH::DMI> FunctionCallsMap; 193 FunctionCallsMap AssumptionCaches; 194 195 public: 196 /// \brief Get the cached assumptions for a function. 197 /// 198 /// If no assumptions are cached, this will scan the function. Otherwise, the 199 /// existing cache will be returned. 200 AssumptionCache &getAssumptionCache(Function &F); 201 202 AssumptionCacheTracker(); 203 ~AssumptionCacheTracker() override; 204 205 void releaseMemory() override { 206 verifyAnalysis(); 207 AssumptionCaches.shrink_and_clear(); 208 } 209 210 void verifyAnalysis() const override; 211 bool doFinalization(Module &) override { 212 verifyAnalysis(); 213 return false; 214 } 215 216 static char ID; // Pass identification, replacement for typeid 217 }; 218 219 } // end namespace llvm 220 221 #endif 222
