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