LLVM 22.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 return AffectedValues[AffectedValueCallbackVH(V, this)];
54}
55
56static void
59 // Note: This code must be kept in-sync with the code in
60 // computeKnownBitsFromAssume in ValueTracking.
61
62 auto InsertAffected = [&Affected](Value *V) {
64 };
65
66 auto AddAffectedVal = [&Affected](Value *V, unsigned Idx) {
67 if (isa<Argument>(V) || isa<GlobalValue>(V) || isa<Instruction>(V)) {
68 Affected.push_back({V, Idx});
69 }
70 };
71
72 for (unsigned Idx = 0; Idx != CI->getNumOperandBundles(); Idx++) {
74 if (Bundle.getTagName() == "separate_storage") {
75 assert(Bundle.Inputs.size() == 2 &&
76 "separate_storage must have two args");
77 AddAffectedVal(getUnderlyingObject(Bundle.Inputs[0]), Idx);
78 AddAffectedVal(getUnderlyingObject(Bundle.Inputs[1]), Idx);
79 } else if (Bundle.Inputs.size() > ABA_WasOn &&
80 Bundle.getTagName() != IgnoreBundleTag)
81 AddAffectedVal(Bundle.Inputs[ABA_WasOn], Idx);
82 }
83
84 Value *Cond = CI->getArgOperand(0);
85 findValuesAffectedByCondition(Cond, /*IsAssume=*/true, InsertAffected);
86
87 if (TTI) {
88 const Value *Ptr;
89 unsigned AS;
90 std::tie(Ptr, AS) = TTI->getPredicatedAddrSpace(Cond);
91 if (Ptr)
92 AddAffectedVal(const_cast<Value *>(Ptr->stripInBoundsOffsets()),
94 }
95}
96
99 findAffectedValues(CI, TTI, Affected);
100
101 for (auto &AV : Affected) {
102 auto &AVV = getOrInsertAffectedValues(AV.Assume);
103 if (llvm::none_of(AVV, [&](ResultElem &Elem) {
104 return Elem.Assume == CI && Elem.Index == AV.Index;
105 }))
106 AVV.push_back({CI, AV.Index});
107 }
108}
109
112 findAffectedValues(CI, TTI, Affected);
113
114 for (auto &AV : Affected) {
115 auto AVI = AffectedValues.find_as(AV.Assume);
116 if (AVI == AffectedValues.end())
117 continue;
118 bool Found = false;
119 bool HasNonnull = false;
120 for (ResultElem &Elem : AVI->second) {
121 if (Elem.Assume == CI) {
122 Found = true;
123 Elem.Assume = nullptr;
124 }
125 HasNonnull |= !!Elem.Assume;
126 if (HasNonnull && Found)
127 break;
128 }
129 assert(Found && "already unregistered or incorrect cache state");
130 if (!HasNonnull)
131 AffectedValues.erase(AVI);
132 }
133
134 llvm::erase(AssumeHandles, CI);
135}
136
137void AssumptionCache::AffectedValueCallbackVH::deleted() {
138 AC->AffectedValues.erase(getValPtr());
139 // 'this' now dangles!
140}
141
142void AssumptionCache::transferAffectedValuesInCache(Value *OV, Value *NV) {
143 auto &NAVV = getOrInsertAffectedValues(NV);
144 auto AVI = AffectedValues.find(OV);
145 if (AVI == AffectedValues.end())
146 return;
147
148 for (auto &A : AVI->second)
149 if (!llvm::is_contained(NAVV, A))
150 NAVV.push_back(A);
151 AffectedValues.erase(OV);
152}
153
154void AssumptionCache::AffectedValueCallbackVH::allUsesReplacedWith(Value *NV) {
155 if (!isa<Instruction>(NV) && !isa<Argument>(NV))
156 return;
157
158 // Any assumptions that affected this value now affect the new value.
159
160 AC->transferAffectedValuesInCache(getValPtr(), NV);
161 // 'this' now might dangle! If the AffectedValues map was resized to add an
162 // entry for NV then this object might have been destroyed in favor of some
163 // copy in the grown map.
164}
165
166void AssumptionCache::scanFunction() {
167 assert(!Scanned && "Tried to scan the function twice!");
168 assert(AssumeHandles.empty() && "Already have assumes when scanning!");
169
170 // Go through all instructions in all blocks, add all calls to @llvm.assume
171 // to this cache.
172 for (BasicBlock &B : F)
173 for (Instruction &I : B)
174 if (isa<AssumeInst>(&I))
175 AssumeHandles.push_back({&I, ExprResultIdx});
176
177 // Mark the scan as complete.
178 Scanned = true;
179
180 // Update affected values.
181 for (auto &A : AssumeHandles)
182 updateAffectedValues(cast<AssumeInst>(A));
183}
184
186 // If we haven't scanned the function yet, just drop this assumption. It will
187 // be found when we scan later.
188 if (!Scanned)
189 return;
190
191 AssumeHandles.push_back({CI, ExprResultIdx});
192
193#ifndef NDEBUG
194 assert(CI->getParent() &&
195 "Cannot register @llvm.assume call not in a basic block");
196 assert(&F == CI->getParent()->getParent() &&
197 "Cannot register @llvm.assume call not in this function");
198
199 // We expect the number of assumptions to be small, so in an asserts build
200 // check that we don't accumulate duplicates and that all assumptions point
201 // to the same function.
202 SmallPtrSet<Value *, 16> AssumptionSet;
203 for (auto &VH : AssumeHandles) {
204 if (!VH)
205 continue;
206
207 assert(&F == cast<Instruction>(VH)->getParent()->getParent() &&
208 "Cached assumption not inside this function!");
209 assert(match(cast<CallInst>(VH), m_Intrinsic<Intrinsic::assume>()) &&
210 "Cached something other than a call to @llvm.assume!");
211 assert(AssumptionSet.insert(VH).second &&
212 "Cache contains multiple copies of a call!");
213 }
214#endif
215
217}
218
222 return AssumptionCache(F, &TTI);
223}
224
225AnalysisKey AssumptionAnalysis::Key;
226
230
231 OS << "Cached assumptions for function: " << F.getName() << "\n";
232 for (auto &VH : AC.assumptions())
233 if (VH)
234 OS << " " << *cast<CallInst>(VH)->getArgOperand(0) << "\n";
235
236 return PreservedAnalyses::all();
237}
238
239void AssumptionCacheTracker::FunctionCallbackVH::deleted() {
240 auto I = ACT->AssumptionCaches.find_as(cast<Function>(getValPtr()));
241 if (I != ACT->AssumptionCaches.end())
242 ACT->AssumptionCaches.erase(I);
243 // 'this' now dangles!
244}
245
247 // We probe the function map twice to try and avoid creating a value handle
248 // around the function in common cases. This makes insertion a bit slower,
249 // but if we have to insert we're going to scan the whole function so that
250 // shouldn't matter.
251 auto I = AssumptionCaches.find_as(&F);
252 if (I != AssumptionCaches.end())
253 return *I->second;
254
255 auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
256 auto *TTI = TTIWP ? &TTIWP->getTTI(F) : nullptr;
257
258 // Ok, build a new cache by scanning the function, insert it and the value
259 // handle into our map, and return the newly populated cache.
260 auto IP = AssumptionCaches.insert(std::make_pair(
261 FunctionCallbackVH(&F, this), std::make_unique<AssumptionCache>(F, TTI)));
262 assert(IP.second && "Scanning function already in the map?");
263 return *IP.first->second;
264}
265
267 auto I = AssumptionCaches.find_as(&F);
268 if (I != AssumptionCaches.end())
269 return I->second.get();
270 return nullptr;
271}
272
274 // FIXME: In the long term the verifier should not be controllable with a
275 // flag. We should either fix all passes to correctly update the assumption
276 // cache and enable the verifier unconditionally or somehow arrange for the
277 // assumption list to be updated automatically by passes.
279 return;
280
282 for (const auto &I : AssumptionCaches) {
283 for (auto &VH : I.second->assumptions())
284 if (VH)
285 AssumptionSet.insert(cast<CallInst>(VH));
286
287 for (const BasicBlock &B : cast<Function>(*I.first))
288 for (const Instruction &II : B)
289 if (match(&II, m_Intrinsic<Intrinsic::assume>()) &&
290 !AssumptionSet.count(cast<CallInst>(&II)))
291 report_fatal_error("Assumption in scanned function not in cache");
292 }
293}
294
296
298
300
301INITIALIZE_PASS(AssumptionCacheTracker, "assumption-cache-tracker",
302 "Assumption Cache Tracker", false, true)
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
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
This header defines various interfaces for pass management in LLVM.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
uint64_t IntrinsicInst * II
FunctionAnalysisManager FAM
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:56
const SmallVectorImpl< MachineOperand > & Cond
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:255
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:412
This represents the llvm.assume intrinsic.
A function analysis which provides an AssumptionCache.
LLVM_ABI 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.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM_ABI 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.
LLVM_ABI void unregisterAssumption(AssumeInst *CI)
Remove an @llvm.assume intrinsic from this function's cache if it has been added to the cache earlier...
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM Basic Block Representation.
Definition: BasicBlock.h:62
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1116
OperandBundleUse getOperandBundleAt(unsigned Index) const
Return the operand bundle at a specific index.
Definition: InstrTypes.h:2052
unsigned getNumOperandBundles() const
Return the number of operand bundles associated with this User.
Definition: InstrTypes.h:1996
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1292
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:165
bool erase(const KeyT &Val)
Definition: DenseMap.h:303
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
Definition: DenseMap.h:173
iterator end()
Definition: DenseMap.h:81
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:214
ImmutablePass class - This class is used to provide information that does not need to be run.
Definition: Pass.h:285
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:118
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:470
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:401
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:541
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:574
void push_back(const T &Elt)
Definition: SmallVector.h:414
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1197
Analysis pass providing the TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
LLVM_ABI std::pair< const Value *, unsigned > getPredicatedAddrSpace(const Value *V) const
LLVM Value Representation.
Definition: Value.h:75
const ParentTy * getParent() const
Definition: ilist_node.h:34
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:444
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.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:2147
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:1758
LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)
Definition: Error.cpp:167
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1916
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
LLVM_ABI 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:29
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:1011
StringRef getTagName() const
Return the tag of this operand bundle as a string.
Definition: InstrTypes.h:1030
ArrayRef< Use > Inputs
Definition: InstrTypes.h:1012