LLVM 19.0.0git
AssumptionCache.cpp
Go to the documentation of this file.
1//===- AssumptionCache.cpp - Cache finding @llvm.assume calls -------------===//
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.
11//
12//===----------------------------------------------------------------------===//
13
15#include "llvm/ADT/STLExtras.h"
21#include "llvm/IR/BasicBlock.h"
22#include "llvm/IR/Function.h"
23#include "llvm/IR/InstrTypes.h"
24#include "llvm/IR/Instruction.h"
26#include "llvm/IR/PassManager.h"
29#include "llvm/Pass.h"
34#include <cassert>
35#include <utility>
36
37using namespace llvm;
38using namespace llvm::PatternMatch;
39
40static cl::opt<bool>
41 VerifyAssumptionCache("verify-assumption-cache", cl::Hidden,
42 cl::desc("Enable verification of assumption cache"),
43 cl::init(false));
44
46AssumptionCache::getOrInsertAffectedValues(Value *V) {
47 // Try using find_as first to avoid creating extra value handles just for the
48 // purpose of doing the lookup.
49 auto AVI = AffectedValues.find_as(V);
50 if (AVI != AffectedValues.end())
51 return AVI->second;
52
53 auto AVIP = AffectedValues.insert(
54 {AffectedValueCallbackVH(V, this), SmallVector<ResultElem, 1>()});
55 return AVIP.first->second;
56}
57
58static void
61 // Note: This code must be kept in-sync with the code in
62 // computeKnownBitsFromAssume in ValueTracking.
63
64 auto InsertAffected = [&Affected](Value *V) {
66 };
67
68 auto AddAffectedVal = [&Affected](Value *V, unsigned Idx) {
69 if (isa<Argument>(V) || isa<GlobalValue>(V) || isa<Instruction>(V)) {
70 Affected.push_back({V, Idx});
71 }
72 };
73
74 for (unsigned Idx = 0; Idx != CI->getNumOperandBundles(); Idx++) {
76 if (Bundle.getTagName() == "separate_storage") {
77 assert(Bundle.Inputs.size() == 2 &&
78 "separate_storage must have two args");
79 AddAffectedVal(getUnderlyingObject(Bundle.Inputs[0]), Idx);
80 AddAffectedVal(getUnderlyingObject(Bundle.Inputs[1]), Idx);
81 } else if (Bundle.Inputs.size() > ABA_WasOn &&
82 Bundle.getTagName() != IgnoreBundleTag)
83 AddAffectedVal(Bundle.Inputs[ABA_WasOn], Idx);
84 }
85
86 Value *Cond = CI->getArgOperand(0);
87 findValuesAffectedByCondition(Cond, /*IsAssume=*/true, InsertAffected);
88
89 if (TTI) {
90 const Value *Ptr;
91 unsigned AS;
92 std::tie(Ptr, AS) = TTI->getPredicatedAddrSpace(Cond);
93 if (Ptr)
94 AddAffectedVal(const_cast<Value *>(Ptr->stripInBoundsOffsets()),
96 }
97}
98
101 findAffectedValues(CI, TTI, Affected);
102
103 for (auto &AV : Affected) {
104 auto &AVV = getOrInsertAffectedValues(AV.Assume);
105 if (llvm::none_of(AVV, [&](ResultElem &Elem) {
106 return Elem.Assume == CI && Elem.Index == AV.Index;
107 }))
108 AVV.push_back({CI, AV.Index});
109 }
110}
111
114 findAffectedValues(CI, TTI, Affected);
115
116 for (auto &AV : Affected) {
117 auto AVI = AffectedValues.find_as(AV.Assume);
118 if (AVI == AffectedValues.end())
119 continue;
120 bool Found = false;
121 bool HasNonnull = false;
122 for (ResultElem &Elem : AVI->second) {
123 if (Elem.Assume == CI) {
124 Found = true;
125 Elem.Assume = nullptr;
126 }
127 HasNonnull |= !!Elem.Assume;
128 if (HasNonnull && Found)
129 break;
130 }
131 assert(Found && "already unregistered or incorrect cache state");
132 if (!HasNonnull)
133 AffectedValues.erase(AVI);
134 }
135
136 llvm::erase(AssumeHandles, CI);
137}
138
139void AssumptionCache::AffectedValueCallbackVH::deleted() {
140 AC->AffectedValues.erase(getValPtr());
141 // 'this' now dangles!
142}
143
144void AssumptionCache::transferAffectedValuesInCache(Value *OV, Value *NV) {
145 auto &NAVV = getOrInsertAffectedValues(NV);
146 auto AVI = AffectedValues.find(OV);
147 if (AVI == AffectedValues.end())
148 return;
149
150 for (auto &A : AVI->second)
151 if (!llvm::is_contained(NAVV, A))
152 NAVV.push_back(A);
153 AffectedValues.erase(OV);
154}
155
156void AssumptionCache::AffectedValueCallbackVH::allUsesReplacedWith(Value *NV) {
157 if (!isa<Instruction>(NV) && !isa<Argument>(NV))
158 return;
159
160 // Any assumptions that affected this value now affect the new value.
161
162 AC->transferAffectedValuesInCache(getValPtr(), NV);
163 // 'this' now might dangle! If the AffectedValues map was resized to add an
164 // entry for NV then this object might have been destroyed in favor of some
165 // copy in the grown map.
166}
167
168void AssumptionCache::scanFunction() {
169 assert(!Scanned && "Tried to scan the function twice!");
170 assert(AssumeHandles.empty() && "Already have assumes when scanning!");
171
172 // Go through all instructions in all blocks, add all calls to @llvm.assume
173 // to this cache.
174 for (BasicBlock &B : F)
175 for (Instruction &I : B)
176 if (isa<AssumeInst>(&I))
177 AssumeHandles.push_back({&I, ExprResultIdx});
178
179 // Mark the scan as complete.
180 Scanned = true;
181
182 // Update affected values.
183 for (auto &A : AssumeHandles)
184 updateAffectedValues(cast<AssumeInst>(A));
185}
186
188 // If we haven't scanned the function yet, just drop this assumption. It will
189 // be found when we scan later.
190 if (!Scanned)
191 return;
192
193 AssumeHandles.push_back({CI, ExprResultIdx});
194
195#ifndef NDEBUG
196 assert(CI->getParent() &&
197 "Cannot register @llvm.assume call not in a basic block");
198 assert(&F == CI->getParent()->getParent() &&
199 "Cannot register @llvm.assume call not in this function");
200
201 // We expect the number of assumptions to be small, so in an asserts build
202 // check that we don't accumulate duplicates and that all assumptions point
203 // to the same function.
204 SmallPtrSet<Value *, 16> AssumptionSet;
205 for (auto &VH : AssumeHandles) {
206 if (!VH)
207 continue;
208
209 assert(&F == cast<Instruction>(VH)->getParent()->getParent() &&
210 "Cached assumption not inside this function!");
211 assert(match(cast<CallInst>(VH), m_Intrinsic<Intrinsic::assume>()) &&
212 "Cached something other than a call to @llvm.assume!");
213 assert(AssumptionSet.insert(VH).second &&
214 "Cache contains multiple copies of a call!");
215 }
216#endif
217
219}
220
224 return AssumptionCache(F, &TTI);
225}
226
227AnalysisKey AssumptionAnalysis::Key;
228
232
233 OS << "Cached assumptions for function: " << F.getName() << "\n";
234 for (auto &VH : AC.assumptions())
235 if (VH)
236 OS << " " << *cast<CallInst>(VH)->getArgOperand(0) << "\n";
237
238 return PreservedAnalyses::all();
239}
240
241void AssumptionCacheTracker::FunctionCallbackVH::deleted() {
242 auto I = ACT->AssumptionCaches.find_as(cast<Function>(getValPtr()));
243 if (I != ACT->AssumptionCaches.end())
244 ACT->AssumptionCaches.erase(I);
245 // 'this' now dangles!
246}
247
249 // We probe the function map twice to try and avoid creating a value handle
250 // around the function in common cases. This makes insertion a bit slower,
251 // but if we have to insert we're going to scan the whole function so that
252 // shouldn't matter.
253 auto I = AssumptionCaches.find_as(&F);
254 if (I != AssumptionCaches.end())
255 return *I->second;
256
257 auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
258 auto *TTI = TTIWP ? &TTIWP->getTTI(F) : nullptr;
259
260 // Ok, build a new cache by scanning the function, insert it and the value
261 // handle into our map, and return the newly populated cache.
262 auto IP = AssumptionCaches.insert(std::make_pair(
263 FunctionCallbackVH(&F, this), std::make_unique<AssumptionCache>(F, TTI)));
264 assert(IP.second && "Scanning function already in the map?");
265 return *IP.first->second;
266}
267
269 auto I = AssumptionCaches.find_as(&F);
270 if (I != AssumptionCaches.end())
271 return I->second.get();
272 return nullptr;
273}
274
276 // FIXME: In the long term the verifier should not be controllable with a
277 // flag. We should either fix all passes to correctly update the assumption
278 // cache and enable the verifier unconditionally or somehow arrange for the
279 // assumption list to be updated automatically by passes.
281 return;
282
284 for (const auto &I : AssumptionCaches) {
285 for (auto &VH : I.second->assumptions())
286 if (VH)
287 AssumptionSet.insert(cast<CallInst>(VH));
288
289 for (const BasicBlock &B : cast<Function>(*I.first))
290 for (const Instruction &II : B)
291 if (match(&II, m_Intrinsic<Intrinsic::assume>()) &&
292 !AssumptionSet.count(cast<CallInst>(&II)))
293 report_fatal_error("Assumption in scanned function not in cache");
294 }
295}
296
299}
300
302
304
305INITIALIZE_PASS(AssumptionCacheTracker, "assumption-cache-tracker",
306 "Assumption Cache Tracker", false, true)
static void findAffectedValues(CallBase *CI, TargetTransformInfo *TTI, SmallVectorImpl< AssumptionCache::ResultElem > &Affected)
static cl::opt< bool > VerifyAssumptionCache("verify-assumption-cache", cl::Hidden, cl::desc("Enable verification of assumption cache"), cl::init(false))
static const Function * getParent(const Value *V)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This pass exposes codegen information to IR-level passes.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:473
This represents the llvm.assume intrinsic.
A function analysis which provides an AssumptionCache.
AssumptionCache run(Function &F, FunctionAnalysisManager &)
An immutable pass that tracks lazily created AssumptionCache objects.
AssumptionCache * lookupAssumptionCache(Function &F)
Return the cached assumptions for a function if it has already been scanned.
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
AssumptionCache & getAssumptionCache(Function &F)
Get the cached assumptions for a function.
A cache of @llvm.assume calls within a function.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
void updateAffectedValues(AssumeInst *CI)
Update the cache of values being affected by this assumption (i.e.
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
void unregisterAssumption(AssumeInst *CI)
Remove an @llvm.assume intrinsic from this function's cache if it has been added to the cache earlier...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:206
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1467
OperandBundleUse getOperandBundleAt(unsigned Index) const
Return the operand bundle at a specific index.
Definition: InstrTypes.h:2342
unsigned getNumOperandBundles() const
Return the number of operand bundles associated with this User.
Definition: InstrTypes.h:2286
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1660
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
bool erase(const KeyT &Val)
Definition: DenseMap.h:329
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
Definition: DenseMap.h:180
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
ImmutablePass class - This class is used to provide information that does not need to be run.
Definition: Pass.h:282
const BasicBlock * getParent() const
Definition: Instruction.h:152
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Analysis pass providing the TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
std::pair< const Value *, unsigned > getPredicatedAddrSpace(const Value *V) const
LLVM Value Representation.
Definition: Value.h:74
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
constexpr StringRef IgnoreBundleTag
Tag in operand bundle indicating that this bundle should be ignored.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
void initializeAssumptionCacheTrackerPass(PassRegistry &)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:2059
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1736
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:156
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879
void findValuesAffectedByCondition(Value *Cond, bool IsAssume, function_ref< void(Value *)> InsertAffected)
Call InsertAffected on all Values whose known bits / value may be affected by the condition Cond.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
unsigned Index
contains either ExprResultIdx or the index of the operand bundle containing the knowledge.
A lightweight accessor for an operand bundle meant to be passed around by value.
Definition: InstrTypes.h:1362
StringRef getTagName() const
Return the tag of this operand bundle as a string.
Definition: InstrTypes.h:1381
ArrayRef< Use > Inputs
Definition: InstrTypes.h:1363