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/ValueHandle.h"
  25 #include "llvm/Pass.h"
  26 #include <memory>
  27
  28 namespace llvm {
  29
  30 // FIXME: Replace this brittle forward declaration with the include of the new
  31 // PassManager.h when doing so doesn't break the PassManagerBuilder.
  32 template <typename IRUnitT> class AnalysisManager;
  33 class PreservedAnalyses;
  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. The
  39 /// cache is also conservatively self-updating so that it will never return
  40 /// incorrect results about a function even as the function is being mutated.
  41 /// However, flushing the cache and rebuilding it (or explicitly updating it)
  42 /// may allow it to discover new assumptions.
  43 class AssumptionCache {
  44   /// \brief The function for which this cache is handling assumptions.
  45   ///
  46   /// We track this to lazily populate our assumptions.
  47   Function &F;
  48
  49   /// \brief Vector of weak value handles to calls of the @llvm.assume
  50   /// intrinsic.
  51   SmallVector<WeakVH, 4> AssumeHandles;
  52
  53   /// \brief Flag tracking whether we have scanned the function yet.
  54   ///
  55   /// We want to be as lazy about this as possible, and so we scan the function
  56   /// at the last moment.
  57   bool Scanned;
  58
  59   /// \brief Scan the function for assumptions and add them to the cache.
  60   void scanFunction();
  61
  62 public:
  63   /// \brief Construct an AssumptionCache from a function by scanning all of
  64   /// its instructions.
  65   AssumptionCache(Function &F) : F(F), Scanned(false) {}
  66
  67   /// \brief Add an @llvm.assume intrinsic to this function's cache.
  68   ///
  69   /// The call passed in must be an instruction within this function and must
  70   /// not already be in the cache.
  71   void registerAssumption(CallInst *CI);
  72
  73   /// \brief Clear the cache of @llvm.assume intrinsics for a function.
  74   ///
  75   /// It will be re-scanned the next time it is requested.
  76   void clear() {
  77     AssumeHandles.clear();
  78     Scanned = false;
  79   }
  80
  81   /// \brief Access the list of assumption handles currently tracked for this
  82   /// function.
  83   ///
  84   /// Note that these produce weak handles that may be null. The caller must
  85   /// handle that case.
  86   /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
  87   /// when we can write that to filter out the null values. Then caller code
  88   /// will become simpler.
  89   MutableArrayRef<WeakVH> assumptions() {
  90     if (!Scanned)
  91       scanFunction();
  92     return AssumeHandles;
  93   }
  94 };
  95
  96 /// \brief A function analysis which provides an \c AssumptionCache.
  97 ///
  98 /// This analysis is intended for use with the new pass manager and will vend
  99 /// assumption caches for a given function.
 100 class AssumptionAnalysis {
 101   static char PassID;
 102
 103 public:
 104   typedef AssumptionCache Result;
 105
 106   /// \brief Opaque, unique identifier for this analysis pass.
 107   static void *ID() { return (void *)&PassID; }
 108
 109   /// \brief Provide a name for the analysis for debugging and logging.
 110   static StringRef name() { return "AssumptionAnalysis"; }
 111
 112   AssumptionAnalysis() {}
 113   AssumptionAnalysis(const AssumptionAnalysis &Arg) {}
 114   AssumptionAnalysis(AssumptionAnalysis &&Arg) {}
 115   AssumptionAnalysis &operator=(const AssumptionAnalysis &RHS) { return *this; }
 116   AssumptionAnalysis &operator=(AssumptionAnalysis &&RHS) { return *this; }
 117
 118   AssumptionCache run(Function &F) { return AssumptionCache(F); }
 119 };
 120
 121 /// \brief Printer pass for the \c AssumptionAnalysis results.
 122 class AssumptionPrinterPass {
 123   raw_ostream &OS;
 124
 125 public:
 126   explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
 127   PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
 128
 129   static StringRef name() { return "AssumptionPrinterPass"; }
 130 };
 131
 132 /// \brief An immutable pass that tracks lazily created \c AssumptionCache
 133 /// objects.
 134 ///
 135 /// This is essentially a workaround for the legacy pass manager's weaknesses
 136 /// which associates each assumption cache with Function and clears it if the
 137 /// function is deleted. The nature of the AssumptionCache is that it is not
 138 /// invalidated by any changes to the function body and so this is sufficient
 139 /// to be conservatively correct.
 140 class AssumptionCacheTracker : public ImmutablePass {
 141   /// A callback value handle applied to function objects, which we use to
 142   /// delete our cache of intrinsics for a function when it is deleted.
 143   class FunctionCallbackVH final : public CallbackVH {
 144     AssumptionCacheTracker *ACT;
 145     void deleted() override;
 146
 147   public:
 148     typedef DenseMapInfo<Value *> DMI;
 149
 150     FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
 151         : CallbackVH(V), ACT(ACT) {}
 152   };
 153
 154   friend FunctionCallbackVH;
 155
 156   typedef DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>,
 157                    FunctionCallbackVH::DMI> FunctionCallsMap;
 158   FunctionCallsMap AssumptionCaches;
 159
 160 public:
 161   /// \brief Get the cached assumptions for a function.
 162   ///
 163   /// If no assumptions are cached, this will scan the function. Otherwise, the
 164   /// existing cache will be returned.
 165   AssumptionCache &getAssumptionCache(Function &F);
 166
 167   AssumptionCacheTracker();
 168   ~AssumptionCacheTracker() override;
 169
 170   void releaseMemory() override { AssumptionCaches.shrink_and_clear(); }
 171
 172   void verifyAnalysis() const override;
 173   bool doFinalization(Module &) override {
 174     verifyAnalysis();
 175     return false;
 176   }
 177
 178   static char ID; // Pass identification, replacement for typeid
 179 };
 180
 181 } // end namespace llvm
 182
 183 #endif