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 29namespace 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. 39class 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 58public: 59 /// \brief Construct an AssumptionCache from a function by scanning all of 60 /// its instructions. 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. 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. 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. 96class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> { 97 friend AnalysisInfoMixin<AssumptionAnalysis>; 98 static char PassID; 99 100public: 101 typedef AssumptionCache Result; 102 103 AssumptionAnalysis() {} 104 AssumptionAnalysis(const AssumptionAnalysis &Arg) {} 105 AssumptionAnalysis(AssumptionAnalysis &&Arg) {} 106 AssumptionAnalysis &operator=(const AssumptionAnalysis &RHS) { return *this; } 107 AssumptionAnalysis &operator=(AssumptionAnalysis &&RHS) { return *this; } 108 109 AssumptionCache run(Function &F, FunctionAnalysisManager &) { 110 return AssumptionCache(F); 111 } 112}; 113 114/// \brief Printer pass for the \c AssumptionAnalysis results. 115class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> { 116 raw_ostream &OS; 117 118public: 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. 131class 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) 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 151public: 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 161 void releaseMemory() override { AssumptionCaches.shrink_and_clear(); } 162 163 void verifyAnalysis() const override; 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