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