1 //===- llvm/Analysis/AssumptionCache.h - Track @llvm.assume -----*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file contains a pass that keeps track of @llvm.assume intrinsics in 10 // the functions of a module (allowing assumptions within any function to be 11 // found cheaply by other parts of the optimizer). 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_ANALYSIS_ASSUMPTIONCACHE_H 16 #define LLVM_ANALYSIS_ASSUMPTIONCACHE_H 17 18 #include "llvm/ADT/ArrayRef.h" 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/ADT/DenseMapInfo.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include "llvm/IR/PassManager.h" 23 #include "llvm/IR/ValueHandle.h" 24 #include "llvm/Pass.h" 25 #include "llvm/Support/Compiler.h" 26 #include <memory> 27 28 namespace llvm { 29 30 class AssumeInst; 31 class Function; 32 class raw_ostream; 33 class TargetTransformInfo; 34 class Value; 35 36 /// A cache of \@llvm.assume calls within a function. 37 /// 38 /// This cache provides fast lookup of assumptions within a function by caching 39 /// them and amortizing the cost of scanning for them across all queries. Passes 40 /// that create new assumptions are required to call registerAssumption() to 41 /// register any new \@llvm.assume calls that they create. Deletions of 42 /// \@llvm.assume calls do not require special handling. 43 class AssumptionCache { 44 public: 45 /// Value of ResultElem::Index indicating that the argument to the call of the 46 /// llvm.assume. 47 enum : unsigned { ExprResultIdx = std::numeric_limits<unsigned>::max() }; 48 49 struct ResultElem { 50 WeakVH Assume; 51 52 /// contains either ExprResultIdx or the index of the operand bundle 53 /// containing the knowledge. 54 unsigned Index; 55 operator Value *() const { return Assume; } 56 }; 57 58 private: 59 /// The function for which this cache is handling assumptions. 60 /// 61 /// We track this to lazily populate our assumptions. 62 Function &F; 63 64 TargetTransformInfo *TTI; 65 66 /// Vector of weak value handles to calls of the \@llvm.assume 67 /// intrinsic. 68 SmallVector<ResultElem, 4> AssumeHandles; 69 70 class LLVM_ABI AffectedValueCallbackVH final : public CallbackVH { 71 AssumptionCache *AC; 72 73 void deleted() override; 74 void allUsesReplacedWith(Value *) override; 75 76 public: 77 using DMI = DenseMapInfo<Value *>; 78 79 AffectedValueCallbackVH(Value *V, AssumptionCache *AC = nullptr) CallbackVH(V)80 : CallbackVH(V), AC(AC) {} 81 }; 82 83 friend AffectedValueCallbackVH; 84 85 /// A map of values about which an assumption might be providing 86 /// information to the relevant set of assumptions. 87 using AffectedValuesMap = 88 DenseMap<AffectedValueCallbackVH, SmallVector<ResultElem, 1>, 89 AffectedValueCallbackVH::DMI>; 90 AffectedValuesMap AffectedValues; 91 92 /// Get the vector of assumptions which affect a value from the cache. 93 SmallVector<ResultElem, 1> &getOrInsertAffectedValues(Value *V); 94 95 /// Move affected values in the cache for OV to be affected values for NV. 96 void transferAffectedValuesInCache(Value *OV, Value *NV); 97 98 /// Flag tracking whether we have scanned the function yet. 99 /// 100 /// We want to be as lazy about this as possible, and so we scan the function 101 /// at the last moment. 102 bool Scanned = false; 103 104 /// Scan the function for assumptions and add them to the cache. 105 LLVM_ABI void scanFunction(); 106 107 public: 108 /// Construct an AssumptionCache from a function by scanning all of 109 /// its instructions. 110 AssumptionCache(Function &F, TargetTransformInfo *TTI = nullptr) F(F)111 : F(F), TTI(TTI) {} 112 113 /// This cache is designed to be self-updating and so it should never be 114 /// invalidated. invalidate(Function &,const PreservedAnalyses &,FunctionAnalysisManager::Invalidator &)115 bool invalidate(Function &, const PreservedAnalyses &, 116 FunctionAnalysisManager::Invalidator &) { 117 return false; 118 } 119 120 /// Add an \@llvm.assume intrinsic to this function's cache. 121 /// 122 /// The call passed in must be an instruction within this function and must 123 /// not already be in the cache. 124 LLVM_ABI void registerAssumption(AssumeInst *CI); 125 126 /// Remove an \@llvm.assume intrinsic from this function's cache if it has 127 /// been added to the cache earlier. 128 LLVM_ABI void unregisterAssumption(AssumeInst *CI); 129 130 /// Update the cache of values being affected by this assumption (i.e. 131 /// the values about which this assumption provides information). 132 LLVM_ABI void updateAffectedValues(AssumeInst *CI); 133 134 /// Clear the cache of \@llvm.assume intrinsics for a function. 135 /// 136 /// It will be re-scanned the next time it is requested. clear()137 void clear() { 138 AssumeHandles.clear(); 139 AffectedValues.clear(); 140 Scanned = false; 141 } 142 143 /// Access the list of assumption handles currently tracked for this 144 /// function. 145 /// 146 /// Note that these produce weak handles that may be null. The caller must 147 /// handle that case. 148 /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>> 149 /// when we can write that to filter out the null values. Then caller code 150 /// will become simpler. assumptions()151 MutableArrayRef<ResultElem> assumptions() { 152 if (!Scanned) 153 scanFunction(); 154 return AssumeHandles; 155 } 156 157 /// Access the list of assumptions which affect this value. assumptionsFor(const Value * V)158 MutableArrayRef<ResultElem> assumptionsFor(const Value *V) { 159 if (!Scanned) 160 scanFunction(); 161 162 auto AVI = AffectedValues.find_as(const_cast<Value *>(V)); 163 if (AVI == AffectedValues.end()) 164 return MutableArrayRef<ResultElem>(); 165 166 return AVI->second; 167 } 168 }; 169 170 /// A function analysis which provides an \c AssumptionCache. 171 /// 172 /// This analysis is intended for use with the new pass manager and will vend 173 /// assumption caches for a given function. 174 class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> { 175 friend AnalysisInfoMixin<AssumptionAnalysis>; 176 177 LLVM_ABI static AnalysisKey Key; 178 179 public: 180 using Result = AssumptionCache; 181 182 LLVM_ABI AssumptionCache run(Function &F, FunctionAnalysisManager &); 183 }; 184 185 /// Printer pass for the \c AssumptionAnalysis results. 186 class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> { 187 raw_ostream &OS; 188 189 public: AssumptionPrinterPass(raw_ostream & OS)190 explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {} 191 192 LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 193 isRequired()194 static bool isRequired() { return true; } 195 }; 196 197 /// An immutable pass that tracks lazily created \c AssumptionCache 198 /// objects. 199 /// 200 /// This is essentially a workaround for the legacy pass manager's weaknesses 201 /// which associates each assumption cache with Function and clears it if the 202 /// function is deleted. The nature of the AssumptionCache is that it is not 203 /// invalidated by any changes to the function body and so this is sufficient 204 /// to be conservatively correct. 205 class LLVM_ABI AssumptionCacheTracker : public ImmutablePass { 206 /// A callback value handle applied to function objects, which we use to 207 /// delete our cache of intrinsics for a function when it is deleted. 208 class LLVM_ABI FunctionCallbackVH final : public CallbackVH { 209 AssumptionCacheTracker *ACT; 210 211 void deleted() override; 212 213 public: 214 using DMI = DenseMapInfo<Value *>; 215 216 FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr) CallbackVH(V)217 : CallbackVH(V), ACT(ACT) {} 218 }; 219 220 friend FunctionCallbackVH; 221 222 using FunctionCallsMap = 223 DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>, 224 FunctionCallbackVH::DMI>; 225 226 FunctionCallsMap AssumptionCaches; 227 228 public: 229 /// Get the cached assumptions for a function. 230 /// 231 /// If no assumptions are cached, this will scan the function. Otherwise, the 232 /// existing cache will be returned. 233 AssumptionCache &getAssumptionCache(Function &F); 234 235 /// Return the cached assumptions for a function if it has already been 236 /// scanned. Otherwise return nullptr. 237 AssumptionCache *lookupAssumptionCache(Function &F); 238 239 AssumptionCacheTracker(); 240 ~AssumptionCacheTracker() override; 241 releaseMemory()242 void releaseMemory() override { 243 verifyAnalysis(); 244 AssumptionCaches.shrink_and_clear(); 245 } 246 247 void verifyAnalysis() const override; 248 doFinalization(Module &)249 bool doFinalization(Module &) override { 250 verifyAnalysis(); 251 return false; 252 } 253 254 static char ID; // Pass identification, replacement for typeid 255 }; 256 257 template<> struct simplify_type<AssumptionCache::ResultElem> { 258 using SimpleType = Value *; 259 260 static SimpleType getSimplifiedValue(AssumptionCache::ResultElem &Val) { 261 return Val; 262 } 263 }; 264 template<> struct simplify_type<const AssumptionCache::ResultElem> { 265 using SimpleType = /*const*/ Value *; 266 267 static SimpleType getSimplifiedValue(const AssumptionCache::ResultElem &Val) { 268 return Val; 269 } 270 }; 271 272 } // end namespace llvm 273 274 #endif // LLVM_ANALYSIS_ASSUMPTIONCACHE_H 275