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 /// \brief A cache of @llvm.assume calls within a function.
  31 ///
  32 /// This cache provides fast lookup of assumptions within a function by caching
  33 /// them and amortizing the cost of scanning for them across all queries. The
  34 /// cache is also conservatively self-updating so that it will never return
  35 /// incorrect results about a function even as the function is being mutated.
  36 /// However, flushing the cache and rebuilding it (or explicitly updating it)
  37 /// may allow it to discover new assumptions.
  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<WeakVH, 4> AssumeHandles;
  47
  48   /// \brief Flag tracking whether we have scanned the function yet.
  49   ///
  50   /// We want to be as lazy about this as possible, and so we scan the function
  51   /// at the last moment.
  52   bool Scanned;
  53
  54   /// \brief Scan the function for assumptions and add them to the cache.
  55   void scanFunction();
  56
  57 public:
  58   /// \brief Construct an AssumptionCache from a function by scanning all of
  59   /// its instructions.
  60   AssumptionCache(Function &F) : F(F), Scanned(false) {}
  61
  62   /// \brief Add an @llvm.assume intrinsic to this function's cache.
  63   ///
  64   /// The call passed in must be an instruction within this fuction and must
  65   /// not already be in the cache.
  66   void registerAssumption(CallInst *CI);
  67
  68   /// \brief Clear the cache of @llvm.assume intrinsics for a function.
  69   ///
  70   /// It will be re-scanned the next time it is requested.
  71   void clear() {
  72     AssumeHandles.clear();
  73     Scanned = false;
  74   }
  75
  76   /// \brief Access the list of assumption handles currently tracked for this
  77   /// fuction.
  78   ///
  79   /// Note that these produce weak handles that may be null. The caller must
  80   /// handle that case.
  81   /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
  82   /// when we can write that to filter out the null values. Then caller code
  83   /// will become simpler.
  84   MutableArrayRef<WeakVH> assumptions() {
  85     if (!Scanned)
  86       scanFunction();
  87     return AssumeHandles;
  88   }
  89 };
  90
  91 /// \brief An immutable pass that tracks lazily created \c AssumptionCache
  92 /// objects.
  93 ///
  94 /// This is essentially a workaround for the legacy pass manager's weaknesses
  95 /// which associates each assumption cache with Function and clears it if the
  96 /// function is deleted. The nature of the AssumptionCache is that it is not
  97 /// invalidated by any changes to the function body and so this is sufficient
  98 /// to be conservatively correct.
  99 class AssumptionCacheTracker : public ImmutablePass {
 100   /// A callback value handle applied to function objects, which we use to
 101   /// delete our cache of intrinsics for a function when it is deleted.
 102   class FunctionCallbackVH : public CallbackVH {
 103     AssumptionCacheTracker *ACT;
 104     void deleted() override;
 105
 106   public:
 107     typedef DenseMapInfo<Value *> DMI;
 108
 109     FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
 110         : CallbackVH(V), ACT(ACT) {}
 111   };
 112
 113   friend FunctionCallbackVH;
 114
 115   typedef DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>,
 116                    FunctionCallbackVH::DMI> FunctionCallsMap;
 117   FunctionCallsMap AssumptionCaches;
 118
 119 public:
 120   /// \brief Get the cached assumptions for a function.
 121   ///
 122   /// If no assumptions are cached, this will scan the function. Otherwise, the
 123   /// existing cache will be returned.
 124   AssumptionCache &getAssumptionCache(Function &F);
 125
 126   AssumptionCacheTracker();
 127   ~AssumptionCacheTracker();
 128
 129   void releaseMemory() override { AssumptionCaches.shrink_and_clear(); }
 130
 131   void verifyAnalysis() const override;
 132   bool doFinalization(Module &) override {
 133     verifyAnalysis();
 134     return false;
 135   }
 136
 137   static char ID; // Pass identification, replacement for typeid
 138 };
 139
 140 } // end namespace llvm
 141
 142 #endif