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  /// Remove an \@llvm.assume intrinsic from this function's cache if it has
107  /// been added to the cache earlier.
108  void unregisterAssumption(CallInst *CI);
109 
110  /// Update the cache of values being affected by this assumption (i.e.
111  /// the values about which this assumption provides information).
112  void updateAffectedValues(CallInst *CI);
113 
114  /// Clear the cache of \@llvm.assume intrinsics for a function.
115  ///
116  /// It will be re-scanned the next time it is requested.
117  void clear() {
118  AssumeHandles.clear();
119  AffectedValues.clear();
120  Scanned = false;
121  }
122 
123  /// Access the list of assumption handles currently tracked for this
124  /// function.
125  ///
126  /// Note that these produce weak handles that may be null. The caller must
127  /// handle that case.
128  /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
129  /// when we can write that to filter out the null values. Then caller code
130  /// will become simpler.
132  if (!Scanned)
133  scanFunction();
134  return AssumeHandles;
135  }
136 
137  /// Access the list of assumptions which affect this value.
139  if (!Scanned)
140  scanFunction();
141 
142  auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
143  if (AVI == AffectedValues.end())
145 
146  return AVI->second;
147  }
148 };
149 
150 /// A function analysis which provides an \c AssumptionCache.
151 ///
152 /// This analysis is intended for use with the new pass manager and will vend
153 /// assumption caches for a given function.
154 class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> {
156 
157  static AnalysisKey Key;
158 
159 public:
161 
163  return AssumptionCache(F);
164  }
165 };
166 
167 /// Printer pass for the \c AssumptionAnalysis results.
168 class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> {
169  raw_ostream &OS;
170 
171 public:
172  explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
173 
175 };
176 
177 /// An immutable pass that tracks lazily created \c AssumptionCache
178 /// objects.
179 ///
180 /// This is essentially a workaround for the legacy pass manager's weaknesses
181 /// which associates each assumption cache with Function and clears it if the
182 /// function is deleted. The nature of the AssumptionCache is that it is not
183 /// invalidated by any changes to the function body and so this is sufficient
184 /// to be conservatively correct.
186  /// A callback value handle applied to function objects, which we use to
187  /// delete our cache of intrinsics for a function when it is deleted.
188  class FunctionCallbackVH final : public CallbackVH {
190 
191  void deleted() override;
192 
193  public:
194  using DMI = DenseMapInfo<Value *>;
195 
196  FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
197  : CallbackVH(V), ACT(ACT) {}
198  };
199 
200  friend FunctionCallbackVH;
201 
202  using FunctionCallsMap =
205 
206  FunctionCallsMap AssumptionCaches;
207 
208 public:
209  /// Get the cached assumptions for a function.
210  ///
211  /// If no assumptions are cached, this will scan the function. Otherwise, the
212  /// existing cache will be returned.
213  AssumptionCache &getAssumptionCache(Function &F);
214 
215  /// Return the cached assumptions for a function if it has already been
216  /// scanned. Otherwise return nullptr.
217  AssumptionCache *lookupAssumptionCache(Function &F);
218 
220  ~AssumptionCacheTracker() override;
221 
222  void releaseMemory() override {
223  verifyAnalysis();
224  AssumptionCaches.shrink_and_clear();
225  }
226 
227  void verifyAnalysis() const override;
228 
229  bool doFinalization(Module &) override {
230  verifyAnalysis();
231  return false;
232  }
233 
234  static char ID; // Pass identification, replacement for typeid
235 };
236 
237 } // end namespace llvm
238 
239 #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:65
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...
void unregisterAssumption(CallInst *CI)
Remove an @llvm.assume intrinsic from this function&#39;s cache if it has been added to the cache earlier...
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:841
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