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.
AssumptionCache(Function & F)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 function 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.
clear()76   void clear() {
77     AssumeHandles.clear();
78     Scanned = false;
79   }
80 
81   /// \brief Access the list of assumption handles currently tracked for this
82   /// function.
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.
assumptions()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.
ID()107   static void *ID() { return (void *)&PassID; }
108 
109   /// \brief Provide a name for the analysis for debugging and logging.
name()110   static StringRef name() { return "AssumptionAnalysis"; }
111 
AssumptionAnalysis()112   AssumptionAnalysis() {}
AssumptionAnalysis(const AssumptionAnalysis & Arg)113   AssumptionAnalysis(const AssumptionAnalysis &Arg) {}
AssumptionAnalysis(AssumptionAnalysis && Arg)114   AssumptionAnalysis(AssumptionAnalysis &&Arg) {}
115   AssumptionAnalysis &operator=(const AssumptionAnalysis &RHS) { return *this; }
116   AssumptionAnalysis &operator=(AssumptionAnalysis &&RHS) { return *this; }
117 
run(Function & F)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:
AssumptionPrinterPass(raw_ostream & OS)126   explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
127   PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
128 
name()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 final : 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)
CallbackVH(V)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 
releaseMemory()170   void releaseMemory() override { AssumptionCaches.shrink_and_clear(); }
171 
172   void verifyAnalysis() const override;
doFinalization(Module &)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