LLVM  13.0.0git
AssumptionCache.h
Go to the documentation of this file.
1 //===- llvm/Analysis/AssumptionCache.h - Track @llvm.assume -----*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains a pass that keeps track of @llvm.assume intrinsics in
10 // the functions of a module (allowing assumptions within any function to be
11 // found cheaply by other parts of the optimizer).
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_ANALYSIS_ASSUMPTIONCACHE_H
16 #define LLVM_ANALYSIS_ASSUMPTIONCACHE_H
17 
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/DenseMapInfo.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/IR/PassManager.h"
23 #include "llvm/IR/ValueHandle.h"
24 #include "llvm/Pass.h"
25 #include <memory>
26 
27 namespace llvm {
28 
29 class AssumeInst;
30 class Function;
31 class raw_ostream;
32 class Value;
33 
34 /// A cache of \@llvm.assume calls within a function.
35 ///
36 /// This cache provides fast lookup of assumptions within a function by caching
37 /// them and amortizing the cost of scanning for them across all queries. Passes
38 /// that create new assumptions are required to call registerAssumption() to
39 /// register any new \@llvm.assume calls that they create. Deletions of
40 /// \@llvm.assume calls do not require special handling.
42 public:
43  /// Value of ResultElem::Index indicating that the argument to the call of the
44  /// llvm.assume.
46 
47  struct ResultElem {
49 
50  /// contains either ExprResultIdx or the index of the operand bundle
51  /// containing the knowledge.
52  unsigned Index;
53  operator Value *() const { return Assume; }
54  };
55 
56 private:
57  /// The function for which this cache is handling assumptions.
58  ///
59  /// We track this to lazily populate our assumptions.
60  Function &F;
61 
62  /// Vector of weak value handles to calls of the \@llvm.assume
63  /// intrinsic.
64  SmallVector<ResultElem, 4> AssumeHandles;
65 
66  class AffectedValueCallbackVH final : public CallbackVH {
67  AssumptionCache *AC;
68 
69  void deleted() override;
70  void allUsesReplacedWith(Value *) override;
71 
72  public:
73  using DMI = DenseMapInfo<Value *>;
74 
75  AffectedValueCallbackVH(Value *V, AssumptionCache *AC = nullptr)
76  : CallbackVH(V), AC(AC) {}
77  };
78 
79  friend AffectedValueCallbackVH;
80 
81  /// A map of values about which an assumption might be providing
82  /// information to the relevant set of assumptions.
83  using AffectedValuesMap =
84  DenseMap<AffectedValueCallbackVH, SmallVector<ResultElem, 1>,
85  AffectedValueCallbackVH::DMI>;
86  AffectedValuesMap AffectedValues;
87 
88  /// Get the vector of assumptions which affect a value from the cache.
89  SmallVector<ResultElem, 1> &getOrInsertAffectedValues(Value *V);
90 
91  /// Move affected values in the cache for OV to be affected values for NV.
92  void transferAffectedValuesInCache(Value *OV, Value *NV);
93 
94  /// Flag tracking whether we have scanned the function yet.
95  ///
96  /// We want to be as lazy about this as possible, and so we scan the function
97  /// at the last moment.
98  bool Scanned = false;
99 
100  /// Scan the function for assumptions and add them to the cache.
101  void scanFunction();
102 
103 public:
104  /// Construct an AssumptionCache from a function by scanning all of
105  /// its instructions.
107 
108  /// This cache is designed to be self-updating and so it should never be
109  /// invalidated.
112  return false;
113  }
114 
115  /// Add an \@llvm.assume intrinsic to this function's cache.
116  ///
117  /// The call passed in must be an instruction within this function and must
118  /// not already be in the cache.
119  void registerAssumption(AssumeInst *CI);
120 
121  /// Remove an \@llvm.assume intrinsic from this function's cache if it has
122  /// been added to the cache earlier.
124 
125  /// Update the cache of values being affected by this assumption (i.e.
126  /// the values about which this assumption provides information).
128 
129  /// Clear the cache of \@llvm.assume intrinsics for a function.
130  ///
131  /// It will be re-scanned the next time it is requested.
132  void clear() {
133  AssumeHandles.clear();
134  AffectedValues.clear();
135  Scanned = false;
136  }
137 
138  /// Access the list of assumption handles currently tracked for this
139  /// function.
140  ///
141  /// Note that these produce weak handles that may be null. The caller must
142  /// handle that case.
143  /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
144  /// when we can write that to filter out the null values. Then caller code
145  /// will become simpler.
147  if (!Scanned)
148  scanFunction();
149  return AssumeHandles;
150  }
151 
152  /// Access the list of assumptions which affect this value.
154  if (!Scanned)
155  scanFunction();
156 
157  auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
158  if (AVI == AffectedValues.end())
160 
161  return AVI->second;
162  }
163 };
164 
165 /// A function analysis which provides an \c AssumptionCache.
166 ///
167 /// This analysis is intended for use with the new pass manager and will vend
168 /// assumption caches for a given function.
169 class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> {
171 
172  static AnalysisKey Key;
173 
174 public:
176 
178  return AssumptionCache(F);
179  }
180 };
181 
182 /// Printer pass for the \c AssumptionAnalysis results.
183 class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> {
184  raw_ostream &OS;
185 
186 public:
187  explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
188 
190 };
191 
192 /// An immutable pass that tracks lazily created \c AssumptionCache
193 /// objects.
194 ///
195 /// This is essentially a workaround for the legacy pass manager's weaknesses
196 /// which associates each assumption cache with Function and clears it if the
197 /// function is deleted. The nature of the AssumptionCache is that it is not
198 /// invalidated by any changes to the function body and so this is sufficient
199 /// to be conservatively correct.
201  /// A callback value handle applied to function objects, which we use to
202  /// delete our cache of intrinsics for a function when it is deleted.
203  class FunctionCallbackVH final : public CallbackVH {
205 
206  void deleted() override;
207 
208  public:
209  using DMI = DenseMapInfo<Value *>;
210 
211  FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
212  : CallbackVH(V), ACT(ACT) {}
213  };
214 
215  friend FunctionCallbackVH;
216 
217  using FunctionCallsMap =
220 
221  FunctionCallsMap AssumptionCaches;
222 
223 public:
224  /// Get the cached assumptions for a function.
225  ///
226  /// If no assumptions are cached, this will scan the function. Otherwise, the
227  /// existing cache will be returned.
229 
230  /// Return the cached assumptions for a function if it has already been
231  /// scanned. Otherwise return nullptr.
233 
235  ~AssumptionCacheTracker() override;
236 
237  void releaseMemory() override {
238  verifyAnalysis();
239  AssumptionCaches.shrink_and_clear();
240  }
241 
242  void verifyAnalysis() const override;
243 
244  bool doFinalization(Module &) override {
245  verifyAnalysis();
246  return false;
247  }
248 
249  static char ID; // Pass identification, replacement for typeid
250 };
251 
252 template<> struct simplify_type<AssumptionCache::ResultElem> {
253  using SimpleType = Value *;
254 
256  return Val;
257  }
258 };
259 template<> struct simplify_type<const AssumptionCache::ResultElem> {
260  using SimpleType = /*const*/ Value *;
261 
263  return Val;
264  }
265 };
266 
267 } // end namespace llvm
268 
269 #endif // LLVM_ANALYSIS_ASSUMPTIONCACHE_H
llvm::simplify_type< AssumptionCache::ResultElem >::getSimplifiedValue
static SimpleType getSimplifiedValue(AssumptionCache::ResultElem &Val)
Definition: AssumptionCache.h:255
llvm::AssumptionCache::clear
void clear()
Clear the cache of @llvm.assume intrinsics for a function.
Definition: AssumptionCache.h:132
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
Definition: AllocatorList.h:23
llvm::AssumptionCache::registerAssumption
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
Definition: AssumptionCache.cpp:217
llvm::ImmutablePass
ImmutablePass class - This class is used to provide information that does not need to be run.
Definition: Pass.h:269
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:61
Pass.h
llvm::AssumptionPrinterPass
Printer pass for the AssumptionAnalysis results.
Definition: AssumptionCache.h:183
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::AssumeInst
This represents the llvm.assume intrinsic.
Definition: IntrinsicInst.h:1272
llvm::AssumptionCache::ResultElem::Index
unsigned Index
contains either ExprResultIdx or the index of the operand bundle containing the knowledge.
Definition: AssumptionCache.h:52
llvm::AssumptionPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: AssumptionCache.cpp:253
llvm::WeakVH
A nullable Value handle that is nullable.
Definition: ValueHandle.h:144
DenseMap.h
llvm::AssumptionCacheTracker::ID
static char ID
Definition: AssumptionCache.h:249
llvm::AssumptionCache::ExprResultIdx
@ ExprResultIdx
Definition: AssumptionCache.h:45
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:128
llvm::AssumptionPrinterPass::AssumptionPrinterPass
AssumptionPrinterPass(raw_ostream &OS)
Definition: AssumptionCache.h:187
llvm::simplify_type< const AssumptionCache::ResultElem >::getSimplifiedValue
static SimpleType getSimplifiedValue(const AssumptionCache::ResultElem &Val)
Definition: AssumptionCache.h:262
llvm::AssumptionCache::ResultElem
Definition: AssumptionCache.h:47
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::DenseMapInfo< Value * >
llvm::DenseMap::shrink_and_clear
void shrink_and_clear()
Definition: DenseMap.h:820
llvm::MutableArrayRef
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:305
llvm::simplify_type
Definition: ilist_iterator.h:178
llvm::AssumptionCacheTracker::lookupAssumptionCache
AssumptionCache * lookupAssumptionCache(Function &F)
Return the cached assumptions for a function if it has already been scanned.
Definition: AssumptionCache.cpp:289
llvm::AssumptionCacheTracker::AssumptionCacheTracker
AssumptionCacheTracker()
Definition: AssumptionCache.cpp:318
llvm::AssumptionCacheTracker::doFinalization
bool doFinalization(Module &) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
Definition: AssumptionCache.h:244
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::AssumptionAnalysis::run
AssumptionCache run(Function &F, FunctionAnalysisManager &)
Definition: AssumptionCache.h:177
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:670
llvm::AssumptionCache::ResultElem::Assume
WeakVH Assume
Definition: AssumptionCache.h:48
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
llvm::DenseMap< FunctionCallbackVH, std::unique_ptr< AssumptionCache >, FunctionCallbackVH::DMI >
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::AssumptionCache::AssumptionCache
AssumptionCache(Function &F)
Construct an AssumptionCache from a function by scanning all of its instructions.
Definition: AssumptionCache.h:106
ArrayRef.h
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:391
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:200
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
ValueHandle.h
llvm::AssumptionCacheTracker::getAssumptionCache
AssumptionCache & getAssumptionCache(Function &F)
Get the cached assumptions for a function.
Definition: AssumptionCache.cpp:272
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
PassManager.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::CallbackVH
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
SmallVector.h
llvm::AssumptionCache::assumptions
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
Definition: AssumptionCache.h:146
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::AssumptionCache::unregisterAssumption
void unregisterAssumption(AssumeInst *CI)
Remove an @llvm.assume intrinsic from this function's cache if it has been added to the cache earlier...
Definition: AssumptionCache.cpp:142
DenseMapInfo.h
llvm::AssumptionCacheTracker::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: AssumptionCache.cpp:296
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::AssumptionCacheTracker::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: AssumptionCache.h:237
llvm::AssumptionCache::invalidate
bool invalidate(Function &, const PreservedAnalyses &, FunctionAnalysisManager::Invalidator &)
This cache is designed to be self-updating and so it should never be invalidated.
Definition: AssumptionCache.h:110
llvm::AssumptionCache::updateAffectedValues
void updateAffectedValues(AssumeInst *CI)
Update the cache of values being affected by this assumption (i.e.
Definition: AssumptionCache.cpp:129
llvm::AssumptionCacheTracker::~AssumptionCacheTracker
~AssumptionCacheTracker() override
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::AssumptionCache::assumptionsFor
MutableArrayRef< ResultElem > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.
Definition: AssumptionCache.h:153