LCOV - code coverage report
Current view: top level - include/llvm/Analysis - AssumptionCache.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 26 26 100.0 %
Date: 2017-09-14 15:23:50 Functions: 7 7 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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      880790 : 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      265024 :   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      106992 :         : 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      861954 :   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      614744 :     if (!Scanned)
     130        7801 :       scanFunction();
     131     1229488 :     return AssumeHandles;
     132             :   }
     133             : 
     134             :   /// \brief Access the list of assumptions which affect this value.
     135    40433079 :   MutableArrayRef<WeakTrackingVH> assumptionsFor(const Value *V) {
     136    40433079 :     if (!Scanned)
     137       77231 :       scanFunction();
     138             : 
     139    40433079 :     auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
     140   121299237 :     if (AVI == AffectedValues.end())
     141    40431741 :       return MutableArrayRef<WeakTrackingVH>();
     142             : 
     143        2676 :     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        1665 :     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           1 :   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       89426 : 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    39196991 :   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    16242132 :         : 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       46903 :   void releaseMemory() override {
     216       46903 :     verifyAnalysis();
     217       46903 :     AssumptionCaches.shrink_and_clear();
     218       46903 :   }
     219             : 
     220             :   void verifyAnalysis() const override;
     221             : 
     222       29793 :   bool doFinalization(Module &) override {
     223       29793 :     verifyAnalysis();
     224       29793 :     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

Generated by: LCOV version 1.13