include/llvm/Analysis/AssumptionCache.h

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