LLVM  15.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 TargetTransformInfo;
33 class Value;
34 
35 /// 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 public:
44  /// Value of ResultElem::Index indicating that the argument to the call of the
45  /// llvm.assume.
47 
48  struct ResultElem {
50 
51  /// contains either ExprResultIdx or the index of the operand bundle
52  /// containing the knowledge.
53  unsigned Index;
54  operator Value *() const { return Assume; }
55  };
56 
57 private:
58  /// The function for which this cache is handling assumptions.
59  ///
60  /// We track this to lazily populate our assumptions.
61  Function &F;
62 
64 
65  /// Vector of weak value handles to calls of the \@llvm.assume
66  /// intrinsic.
67  SmallVector<ResultElem, 4> AssumeHandles;
68 
69  class AffectedValueCallbackVH final : public CallbackVH {
70  AssumptionCache *AC;
71 
72  void deleted() override;
73  void allUsesReplacedWith(Value *) override;
74 
75  public:
76  using DMI = DenseMapInfo<Value *>;
77 
78  AffectedValueCallbackVH(Value *V, AssumptionCache *AC = nullptr)
79  : CallbackVH(V), AC(AC) {}
80  };
81 
82  friend AffectedValueCallbackVH;
83 
84  /// A map of values about which an assumption might be providing
85  /// information to the relevant set of assumptions.
86  using AffectedValuesMap =
87  DenseMap<AffectedValueCallbackVH, SmallVector<ResultElem, 1>,
88  AffectedValueCallbackVH::DMI>;
89  AffectedValuesMap AffectedValues;
90 
91  /// Get the vector of assumptions which affect a value from the cache.
92  SmallVector<ResultElem, 1> &getOrInsertAffectedValues(Value *V);
93 
94  /// Move affected values in the cache for OV to be affected values for NV.
95  void transferAffectedValuesInCache(Value *OV, Value *NV);
96 
97  /// Flag tracking whether we have scanned the function yet.
98  ///
99  /// We want to be as lazy about this as possible, and so we scan the function
100  /// at the last moment.
101  bool Scanned = false;
102 
103  /// Scan the function for assumptions and add them to the cache.
104  void scanFunction();
105 
106 public:
107  /// Construct an AssumptionCache from a function by scanning all of
108  /// its instructions.
110  : F(F), TTI(TTI) {}
111 
112  /// This cache is designed to be self-updating and so it should never be
113  /// invalidated.
116  return false;
117  }
118 
119  /// Add an \@llvm.assume intrinsic to this function's cache.
120  ///
121  /// The call passed in must be an instruction within this function and must
122  /// not already be in the cache.
123  void registerAssumption(AssumeInst *CI);
124 
125  /// Remove an \@llvm.assume intrinsic from this function's cache if it has
126  /// been added to the cache earlier.
128 
129  /// Update the cache of values being affected by this assumption (i.e.
130  /// the values about which this assumption provides information).
132 
133  /// Clear the cache of \@llvm.assume intrinsics for a function.
134  ///
135  /// It will be re-scanned the next time it is requested.
136  void clear() {
137  AssumeHandles.clear();
138  AffectedValues.clear();
139  Scanned = false;
140  }
141 
142  /// Access the list of assumption handles currently tracked for this
143  /// function.
144  ///
145  /// Note that these produce weak handles that may be null. The caller must
146  /// handle that case.
147  /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
148  /// when we can write that to filter out the null values. Then caller code
149  /// will become simpler.
151  if (!Scanned)
152  scanFunction();
153  return AssumeHandles;
154  }
155 
156  /// Access the list of assumptions which affect this value.
158  if (!Scanned)
159  scanFunction();
160 
161  auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
162  if (AVI == AffectedValues.end())
164 
165  return AVI->second;
166  }
167 };
168 
169 /// A function analysis which provides an \c AssumptionCache.
170 ///
171 /// This analysis is intended for use with the new pass manager and will vend
172 /// assumption caches for a given function.
173 class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> {
175 
176  static AnalysisKey Key;
177 
178 public:
180 
182 };
183 
184 /// Printer pass for the \c AssumptionAnalysis results.
185 class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> {
186  raw_ostream &OS;
187 
188 public:
189  explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
190 
192 };
193 
194 /// An immutable pass that tracks lazily created \c AssumptionCache
195 /// objects.
196 ///
197 /// This is essentially a workaround for the legacy pass manager's weaknesses
198 /// which associates each assumption cache with Function and clears it if the
199 /// function is deleted. The nature of the AssumptionCache is that it is not
200 /// invalidated by any changes to the function body and so this is sufficient
201 /// to be conservatively correct.
203  /// A callback value handle applied to function objects, which we use to
204  /// delete our cache of intrinsics for a function when it is deleted.
205  class FunctionCallbackVH final : public CallbackVH {
207 
208  void deleted() override;
209 
210  public:
211  using DMI = DenseMapInfo<Value *>;
212 
213  FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
214  : CallbackVH(V), ACT(ACT) {}
215  };
216 
217  friend FunctionCallbackVH;
218 
219  using FunctionCallsMap =
222 
223  FunctionCallsMap AssumptionCaches;
224 
225 public:
226  /// Get the cached assumptions for a function.
227  ///
228  /// If no assumptions are cached, this will scan the function. Otherwise, the
229  /// existing cache will be returned.
231 
232  /// Return the cached assumptions for a function if it has already been
233  /// scanned. Otherwise return nullptr.
235 
237  ~AssumptionCacheTracker() override;
238 
239  void releaseMemory() override {
240  verifyAnalysis();
241  AssumptionCaches.shrink_and_clear();
242  }
243 
244  void verifyAnalysis() const override;
245 
246  bool doFinalization(Module &) override {
247  verifyAnalysis();
248  return false;
249  }
250 
251  static char ID; // Pass identification, replacement for typeid
252 };
253 
254 template<> struct simplify_type<AssumptionCache::ResultElem> {
255  using SimpleType = Value *;
256 
258  return Val;
259  }
260 };
261 template<> struct simplify_type<const AssumptionCache::ResultElem> {
262  using SimpleType = /*const*/ Value *;
263 
265  return Val;
266  }
267 };
268 
269 } // end namespace llvm
270 
271 #endif // LLVM_ANALYSIS_ASSUMPTIONCACHE_H
llvm::simplify_type< AssumptionCache::ResultElem >::getSimplifiedValue
static SimpleType getSimplifiedValue(AssumptionCache::ResultElem &Val)
Definition: AssumptionCache.h:257
llvm::AssumptionCache::clear
void clear()
Clear the cache of @llvm.assume intrinsics for a function.
Definition: AssumptionCache.h:136
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::AssumptionCache::registerAssumption
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
Definition: AssumptionCache.cpp:224
llvm::ImmutablePass
ImmutablePass class - This class is used to provide information that does not need to be run.
Definition: Pass.h:279
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
Pass.h
llvm::AssumptionPrinterPass
Printer pass for the AssumptionAnalysis results.
Definition: AssumptionCache.h:185
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::AssumeInst
This represents the llvm.assume intrinsic.
Definition: IntrinsicInst.h:1429
llvm::AssumptionCache::ResultElem::Index
unsigned Index
contains either ExprResultIdx or the index of the operand bundle containing the knowledge.
Definition: AssumptionCache.h:53
llvm::AssumptionPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: AssumptionCache.cpp:266
llvm::WeakVH
A nullable Value handle that is nullable.
Definition: ValueHandle.h:144
llvm::AssumptionCache::ExprResultIdx
@ ExprResultIdx
Definition: AssumptionCache.h:46
DenseMap.h
llvm::AssumptionCacheTracker::ID
static char ID
Definition: AssumptionCache.h:251
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::AssumptionPrinterPass::AssumptionPrinterPass
AssumptionPrinterPass(raw_ostream &OS)
Definition: AssumptionCache.h:189
llvm::simplify_type< const AssumptionCache::ResultElem >::getSimplifiedValue
static SimpleType getSimplifiedValue(const AssumptionCache::ResultElem &Val)
Definition: AssumptionCache.h:264
llvm::AssumptionCache::ResultElem
Definition: AssumptionCache.h:48
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::DenseMapInfo< Value * >
llvm::DenseMap::shrink_and_clear
void shrink_and_clear()
Definition: DenseMap.h:822
llvm::MutableArrayRef
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:306
llvm::simplify_type
Define a template that can be specialized by smart pointers to reflect the fact that they are automat...
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:305
llvm::AssumptionCacheTracker::AssumptionCacheTracker
AssumptionCacheTracker()
Definition: AssumptionCache.cpp:334
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:246
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:667
llvm::AssumptionCache::ResultElem::Assume
WeakVH Assume
Definition: AssumptionCache.h:49
llvm::AssumptionAnalysis::run
AssumptionCache run(Function &F, FunctionAnalysisManager &)
Definition: AssumptionCache.cpp:258
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
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:69
ArrayRef.h
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
ValueHandle.h
llvm::AssumptionCacheTracker::getAssumptionCache
AssumptionCache & getAssumptionCache(Function &F)
Get the cached assumptions for a function.
Definition: AssumptionCache.cpp:285
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
PassManager.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::CallbackVH
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
llvm::AssumptionCache::AssumptionCache
AssumptionCache(Function &F, TargetTransformInfo *TTI=nullptr)
Construct an AssumptionCache from a function by scanning all of its instructions.
Definition: AssumptionCache.h:109
SmallVector.h
llvm::AssumptionCache::assumptions
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
Definition: AssumptionCache.h:150
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:149
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:312
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
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:239
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:114
llvm::AssumptionCache::updateAffectedValues
void updateAffectedValues(AssumeInst *CI)
Update the cache of values being affected by this assumption (i.e.
Definition: AssumptionCache.cpp:136
llvm::AssumptionCacheTracker::~AssumptionCacheTracker
~AssumptionCacheTracker() override
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
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:157