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/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