LLVM  9.0.0svn
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 CallInst;
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  /// The function for which this cache is handling assumptions.
43  ///
44  /// We track this to lazily populate our assumptions.
45  Function &F;
46 
47  /// Vector of weak value handles to calls of the \@llvm.assume
48  /// intrinsic.
49  SmallVector<WeakTrackingVH, 4> AssumeHandles;
50 
51  class AffectedValueCallbackVH final : public CallbackVH {
52  AssumptionCache *AC;
53 
54  void deleted() override;
55  void allUsesReplacedWith(Value *) override;
56 
57  public:
58  using DMI = DenseMapInfo<Value *>;
59 
60  AffectedValueCallbackVH(Value *V, AssumptionCache *AC = nullptr)
61  : CallbackVH(V), AC(AC) {}
62  };
63 
64  friend AffectedValueCallbackVH;
65 
66  /// A map of values about which an assumption might be providing
67  /// information to the relevant set of assumptions.
68  using AffectedValuesMap =
71  AffectedValuesMap AffectedValues;
72 
73  /// Get the vector of assumptions which affect a value from the cache.
74  SmallVector<WeakTrackingVH, 1> &getOrInsertAffectedValues(Value *V);
75 
76  /// Copy affected values in the cache for OV to be affected values for NV.
77  void copyAffectedValuesInCache(Value *OV, Value *NV);
78 
79  /// Flag tracking whether we have scanned the function yet.
80  ///
81  /// We want to be as lazy about this as possible, and so we scan the function
82  /// at the last moment.
83  bool Scanned = false;
84 
85  /// Scan the function for assumptions and add them to the cache.
86  void scanFunction();
87 
88 public:
89  /// Construct an AssumptionCache from a function by scanning all of
90  /// its instructions.
91  AssumptionCache(Function &F) : F(F) {}
92 
93  /// This cache is designed to be self-updating and so it should never be
94  /// invalidated.
97  return false;
98  }
99 
100  /// Add an \@llvm.assume intrinsic to this function's cache.
101  ///
102  /// The call passed in must be an instruction within this function and must
103  /// not already be in the cache.
104  void registerAssumption(CallInst *CI);
105 
106  /// Update the cache of values being affected by this assumption (i.e.
107  /// the values about which this assumption provides information).
108  void updateAffectedValues(CallInst *CI);
109 
110  /// Clear the cache of \@llvm.assume intrinsics for a function.
111  ///
112  /// It will be re-scanned the next time it is requested.
113  void clear() {
114  AssumeHandles.clear();
115  AffectedValues.clear();
116  Scanned = false;
117  }
118 
119  /// Access the list of assumption handles currently tracked for this
120  /// function.
121  ///
122  /// Note that these produce weak handles that may be null. The caller must
123  /// handle that case.
124  /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
125  /// when we can write that to filter out the null values. Then caller code
126  /// will become simpler.
128  if (!Scanned)
129  scanFunction();
130  return AssumeHandles;
131  }
132 
133  /// Access the list of assumptions which affect this value.
135  if (!Scanned)
136  scanFunction();
137 
138  auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
139  if (AVI == AffectedValues.end())
141 
142  return AVI->second;
143  }
144 };
145 
146 /// A function analysis which provides an \c AssumptionCache.
147 ///
148 /// This analysis is intended for use with the new pass manager and will vend
149 /// assumption caches for a given function.
150 class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> {
152 
153  static AnalysisKey Key;
154 
155 public:
157 
159  return AssumptionCache(F);
160  }
161 };
162 
163 /// Printer pass for the \c AssumptionAnalysis results.
164 class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> {
165  raw_ostream &OS;
166 
167 public:
168  explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
169 
171 };
172 
173 /// An immutable pass that tracks lazily created \c AssumptionCache
174 /// objects.
175 ///
176 /// This is essentially a workaround for the legacy pass manager's weaknesses
177 /// which associates each assumption cache with Function and clears it if the
178 /// function is deleted. The nature of the AssumptionCache is that it is not
179 /// invalidated by any changes to the function body and so this is sufficient
180 /// to be conservatively correct.
182  /// A callback value handle applied to function objects, which we use to
183  /// delete our cache of intrinsics for a function when it is deleted.
184  class FunctionCallbackVH final : public CallbackVH {
186 
187  void deleted() override;
188 
189  public:
190  using DMI = DenseMapInfo<Value *>;
191 
192  FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
193  : CallbackVH(V), ACT(ACT) {}
194  };
195 
196  friend FunctionCallbackVH;
197 
198  using FunctionCallsMap =
201 
202  FunctionCallsMap AssumptionCaches;
203 
204 public:
205  /// Get the cached assumptions for a function.
206  ///
207  /// If no assumptions are cached, this will scan the function. Otherwise, the
208  /// existing cache will be returned.
209  AssumptionCache &getAssumptionCache(Function &F);
210 
212  ~AssumptionCacheTracker() override;
213 
214  void releaseMemory() override {
215  verifyAnalysis();
216  AssumptionCaches.shrink_and_clear();
217  }
218 
219  void verifyAnalysis() const override;
220 
221  bool doFinalization(Module &) override {
222  verifyAnalysis();
223  return false;
224  }
225 
226  static char ID; // Pass identification, replacement for typeid
227 };
228 
229 } // end namespace llvm
230 
231 #endif // LLVM_ANALYSIS_ASSUMPTIONCACHE_H
DiagnosticInfoOptimizationBase::Argument NV
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
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 @llvm.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 @llvm.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:290
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:255
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:839
void updateAffectedValues(CallInst *CI)
Update the cache of values being affected by this assumption (i.e.
void shrink_and_clear()
Definition: DenseMap.h:815
MutableArrayRef< WeakTrackingVH > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.
void registerAssumption(CallInst *CI)
Add an @llvm.assume intrinsic to this function&#39;s cache.
iterator end()
Definition: DenseMap.h:108
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:641
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive, key type.
Definition: DenseMap.h:195
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:72
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:379
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