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/DenseMapInfo.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/IR/PassManager.h" 24 #include "llvm/IR/ValueHandle.h" 25 #include "llvm/Pass.h" 26 #include <memory> 27 28 namespace llvm { 29 30 class CallInst; 31 class Function; 32 class raw_ostream; 33 class Value; 34 35 /// A cache of \@llvm.assume calls within a function. 36 /// 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. Passes 39 /// that create new assumptions are required to call registerAssumption() to 40 /// register any new \@llvm.assume calls that they create. Deletions of 41 /// \@llvm.assume calls do not require special handling. 42 class AssumptionCache { 43 /// The function for which this cache is handling assumptions. 44 /// 45 /// We track this to lazily populate our assumptions. 46 Function &F; 47 48 /// Vector of weak value handles to calls of the \@llvm.assume 49 /// intrinsic. 50 SmallVector<WeakTrackingVH, 4> AssumeHandles; 51 52 class AffectedValueCallbackVH final : public CallbackVH { 53 AssumptionCache *AC; 54 55 void deleted() override; 56 void allUsesReplacedWith(Value *) override; 57 58 public: 59 using DMI = DenseMapInfo<Value *>; 60 61 AffectedValueCallbackVH(Value *V, AssumptionCache *AC = nullptr) CallbackVH(V)62 : CallbackVH(V), AC(AC) {} 63 }; 64 65 friend AffectedValueCallbackVH; 66 67 /// A map of values about which an assumption might be providing 68 /// information to the relevant set of assumptions. 69 using AffectedValuesMap = 70 DenseMap<AffectedValueCallbackVH, SmallVector<WeakTrackingVH, 1>, 71 AffectedValueCallbackVH::DMI>; 72 AffectedValuesMap AffectedValues; 73 74 /// Get the vector of assumptions which affect a value from the cache. 75 SmallVector<WeakTrackingVH, 1> &getOrInsertAffectedValues(Value *V); 76 77 /// Copy affected values in the cache for OV to be affected values for NV. 78 void copyAffectedValuesInCache(Value *OV, Value *NV); 79 80 /// Flag tracking whether we have scanned the function yet. 81 /// 82 /// We want to be as lazy about this as possible, and so we scan the function 83 /// at the last moment. 84 bool Scanned = false; 85 86 /// Scan the function for assumptions and add them to the cache. 87 void scanFunction(); 88 89 public: 90 /// Construct an AssumptionCache from a function by scanning all of 91 /// its instructions. AssumptionCache(Function & F)92 AssumptionCache(Function &F) : F(F) {} 93 94 /// This cache is designed to be self-updating and so it should never be 95 /// invalidated. invalidate(Function &,const PreservedAnalyses &,FunctionAnalysisManager::Invalidator &)96 bool invalidate(Function &, const PreservedAnalyses &, 97 FunctionAnalysisManager::Invalidator &) { 98 return false; 99 } 100 101 /// Add an \@llvm.assume intrinsic to this function's cache. 102 /// 103 /// The call passed in must be an instruction within this function and must 104 /// not already be in the cache. 105 void registerAssumption(CallInst *CI); 106 107 /// Update the cache of values being affected by this assumption (i.e. 108 /// the values about which this assumption provides information). 109 void updateAffectedValues(CallInst *CI); 110 111 /// Clear the cache of \@llvm.assume intrinsics for a function. 112 /// 113 /// It will be re-scanned the next time it is requested. clear()114 void clear() { 115 AssumeHandles.clear(); 116 AffectedValues.clear(); 117 Scanned = false; 118 } 119 120 /// Access the list of assumption handles currently tracked for this 121 /// function. 122 /// 123 /// Note that these produce weak handles that may be null. The caller must 124 /// handle that case. 125 /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>> 126 /// when we can write that to filter out the null values. Then caller code 127 /// will become simpler. assumptions()128 MutableArrayRef<WeakTrackingVH> assumptions() { 129 if (!Scanned) 130 scanFunction(); 131 return AssumeHandles; 132 } 133 134 /// Access the list of assumptions which affect this value. assumptionsFor(const Value * V)135 MutableArrayRef<WeakTrackingVH> assumptionsFor(const Value *V) { 136 if (!Scanned) 137 scanFunction(); 138 139 auto AVI = AffectedValues.find_as(const_cast<Value *>(V)); 140 if (AVI == AffectedValues.end()) 141 return MutableArrayRef<WeakTrackingVH>(); 142 143 return AVI->second; 144 } 145 }; 146 147 /// A function analysis which provides an \c AssumptionCache. 148 /// 149 /// This analysis is intended for use with the new pass manager and will vend 150 /// assumption caches for a given function. 151 class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> { 152 friend AnalysisInfoMixin<AssumptionAnalysis>; 153 154 static AnalysisKey Key; 155 156 public: 157 using Result = AssumptionCache; 158 run(Function & F,FunctionAnalysisManager &)159 AssumptionCache run(Function &F, FunctionAnalysisManager &) { 160 return AssumptionCache(F); 161 } 162 }; 163 164 /// Printer pass for the \c AssumptionAnalysis results. 165 class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> { 166 raw_ostream &OS; 167 168 public: AssumptionPrinterPass(raw_ostream & OS)169 explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {} 170 171 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 172 }; 173 174 /// An immutable pass that tracks lazily created \c AssumptionCache 175 /// objects. 176 /// 177 /// This is essentially a workaround for the legacy pass manager's weaknesses 178 /// which associates each assumption cache with Function and clears it if the 179 /// function is deleted. The nature of the AssumptionCache is that it is not 180 /// invalidated by any changes to the function body and so this is sufficient 181 /// to be conservatively correct. 182 class AssumptionCacheTracker : public ImmutablePass { 183 /// A callback value handle applied to function objects, which we use to 184 /// delete our cache of intrinsics for a function when it is deleted. 185 class FunctionCallbackVH final : public CallbackVH { 186 AssumptionCacheTracker *ACT; 187 188 void deleted() override; 189 190 public: 191 using DMI = DenseMapInfo<Value *>; 192 193 FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr) CallbackVH(V)194 : CallbackVH(V), ACT(ACT) {} 195 }; 196 197 friend FunctionCallbackVH; 198 199 using FunctionCallsMap = 200 DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>, 201 FunctionCallbackVH::DMI>; 202 203 FunctionCallsMap AssumptionCaches; 204 205 public: 206 /// Get the cached assumptions for a function. 207 /// 208 /// If no assumptions are cached, this will scan the function. Otherwise, the 209 /// existing cache will be returned. 210 AssumptionCache &getAssumptionCache(Function &F); 211 212 AssumptionCacheTracker(); 213 ~AssumptionCacheTracker() override; 214 releaseMemory()215 void releaseMemory() override { 216 verifyAnalysis(); 217 AssumptionCaches.shrink_and_clear(); 218 } 219 220 void verifyAnalysis() const override; 221 doFinalization(Module &)222 bool doFinalization(Module &) override { 223 verifyAnalysis(); 224 return false; 225 } 226 227 static char ID; // Pass identification, replacement for typeid 228 }; 229 230 } // end namespace llvm 231 232 #endif // LLVM_ANALYSIS_ASSUMPTIONCACHE_H 233