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