LLVM  6.0.0svn
AssumptionCache.h
Go to the documentation of this file.
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.
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  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  : 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 =
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  AssumptionCache(Function &F) : F(F) {}
93 
94  /// This cache is designed to be self-updating and so it should never be
95  /// invalidated.
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.
129  if (!Scanned)
130  scanFunction();
131  return AssumeHandles;
132  }
133 
134  /// \brief Access the list of assumptions which affect this value.
136  if (!Scanned)
137  scanFunction();
138 
139  auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
140  if (AVI == AffectedValues.end())
142 
143  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> {
153 
154  static AnalysisKey Key;
155 
156 public:
158 
160  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  explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
170 
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.
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  class FunctionCallbackVH final : public CallbackVH {
187 
188  void deleted() override;
189 
190  public:
191  using DMI = DenseMapInfo<Value *>;
192 
193  FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
194  : CallbackVH(V), ACT(ACT) {}
195  };
196 
197  friend FunctionCallbackVH;
198 
199  using FunctionCallsMap =
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 
213  ~AssumptionCacheTracker() override;
214 
215  void releaseMemory() override {
216  verifyAnalysis();
217  AssumptionCaches.shrink_and_clear();
218  }
219 
220  void verifyAnalysis() const override;
221 
222  bool doFinalization(Module &) override {
223  verifyAnalysis();
224  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
DiagnosticInfoOptimizationBase::Argument NV
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
Printer pass for the AssumptionAnalysis results.
This class represents a function call, abstracting a target machine&#39;s calling convention.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of .assume calls within a function.
MutableArrayRef< WeakTrackingVH > assumptions()
Access the list of assumption handles currently tracked for this function.
bool doFinalization(Module &) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
Key
PAL metadata keys.
#define F(x, y, z)
Definition: MD5.cpp:55
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:365
void clear()
Clear the cache of .assume intrinsics for a function.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:291
AssumptionCache(Function &F)
Construct an AssumptionCache from a function by scanning all of its instructions. ...
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:382
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
A function analysis which provides an AssumptionCache.
AssumptionCache run(Function &F, FunctionAnalysisManager &)
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:256
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
void updateAffectedValues(CallInst *CI)
Update the cache of values being affected by this assumption (i.e.
void shrink_and_clear()
Definition: DenseMap.h:745
MutableArrayRef< WeakTrackingVH > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.
void registerAssumption(CallInst *CI)
Add an .assume intrinsic to this function&#39;s cache.
iterator end()
Definition: DenseMap.h:79
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive, key type.
Definition: DenseMap.h:165
bool invalidate(Function &, const PreservedAnalyses &, FunctionAnalysisManager::Invalidator &)
This cache is designed to be self-updating and so it should never be invalidated. ...
LLVM Value Representation.
Definition: Value.h:73
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:389
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
AssumptionPrinterPass(raw_ostream &OS)
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70