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