contrib/llvm/include/llvm/Analysis/AssumptionCache.h

   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 /// \brief 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   /// \brief The function for which this cache is handling assumptions.
  44   ///
  45   /// We track this to lazily populate our assumptions.
  46   Function &F;
  47
  48   /// \brief 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)
  62         : CallbackVH(V), AC(AC) {}
  63   };
  64
  65   friend AffectedValueCallbackVH;
  66
  67   /// \brief 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   /// \brief 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   /// \brief Scan the function for assumptions and add them to the cache.
  87   void scanFunction();
  88
  89 public:
  90   /// \brief Construct an AssumptionCache from a function by scanning all of
  91   /// its instructions.
  92   AssumptionCache(Function &F) : F(F) {}
  93
  94   /// This cache is designed to be self-updating and so it should never be
  95   /// invalidated.
  96   bool invalidate(Function &, const PreservedAnalyses &,
  97                   FunctionAnalysisManager::Invalidator &) {
  98     return false;
  99   }
 100
 101   /// \brief 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   /// \brief 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   /// \brief Clear the cache of @llvm.assume intrinsics for a function.
 112   ///
 113   /// It will be re-scanned the next time it is requested.
 114   void clear() {
 115     AssumeHandles.clear();
 116     AffectedValues.clear();
 117     Scanned = false;
 118   }
 119
 120   /// \brief 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.
 128   MutableArrayRef<WeakTrackingVH> assumptions() {
 129     if (!Scanned)
 130       scanFunction();
 131     return AssumeHandles;
 132   }
 133
 134   /// \brief Access the list of assumptions which affect this value.
 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 /// \brief 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
 159   AssumptionCache run(Function &F, FunctionAnalysisManager &) {
 160     return AssumptionCache(F);
 161   }
 162 };
 163
 164 /// \brief Printer pass for the \c AssumptionAnalysis results.
 165 class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> {
 166   raw_ostream &OS;
 167
 168 public:
 169   explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
 170
 171   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 172 };
 173
 174 /// \brief 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)
 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   /// \brief 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
 215   void releaseMemory() override {
 216     verifyAnalysis();
 217     AssumptionCaches.shrink_and_clear();
 218   }
 219
 220   void verifyAnalysis() const override;
 221
 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