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/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 fuction 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   /// fuction.
     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 : 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
    184