LLVM: lib/Analysis/CaptureTracking.cpp Source File

LLVM 22.0.0git
CaptureTracking.cpp
Go to the documentation of this file.
1//===--- CaptureTracking.cpp - Determine whether a pointer is captured ----===//
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 routines that help determine which pointers are captured.
10// A pointer value is captured if the function makes a copy of any part of the
11// pointer that outlives the call. Not being captured means, more or less, that
12// the pointer is only dereferenced and not stored in a global. Returning part
13// of the pointer as the function return value may or may not count as capturing
14// the pointer, depending on the context.
15//
16//===----------------------------------------------------------------------===//
17
18#include "llvm/Analysis/CaptureTracking.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/Analysis/AliasAnalysis.h"
22#include "llvm/Analysis/CFG.h"
23#include "llvm/Analysis/ValueTracking.h"
24#include "llvm/IR/Constants.h"
25#include "llvm/IR/Dominators.h"
26#include "llvm/IR/Instructions.h"
27#include "llvm/IR/IntrinsicInst.h"
28#include "llvm/Support/CommandLine.h"
29
30using namespace llvm;
31
32 #define DEBUG_TYPE "capture-tracking"
33
34 STATISTIC(NumCaptured, "Number of pointers maybe captured");
35 STATISTIC(NumNotCaptured, "Number of pointers not captured");
36 STATISTIC(NumCapturedBefore, "Number of pointers maybe captured before");
37 STATISTIC(NumNotCapturedBefore, "Number of pointers not captured before");
38
39/// The default value for MaxUsesToExplore argument. It's relatively small to
40/// keep the cost of analysis reasonable for clients like BasicAliasAnalysis,
41/// where the results can't be cached.
42/// TODO: we should probably introduce a caching CaptureTracking analysis and
43/// use it where possible. The caching version can use much higher limit or
44/// don't have this cap at all.
45static cl::opt<unsigned>
46 DefaultMaxUsesToExplore("capture-tracking-max-uses-to-explore", cl::Hidden,
47 cl::desc("Maximal number of uses to explore."),
48 cl::init(100));
49
53
54CaptureTracker::~CaptureTracker() = default;
55
56 bool CaptureTracker::shouldExplore(const Use *U) { return true; }
57
58namespace {
59struct SimpleCaptureTracker : public CaptureTracker {
60 explicit SimpleCaptureTracker(bool ReturnCaptures, CaptureComponents Mask,
61 function_ref<bool(CaptureComponents)> StopFn)
62 : ReturnCaptures(ReturnCaptures), Mask(Mask), StopFn(StopFn) {}
63
64 void tooManyUses() override {
65 LLVM_DEBUG(dbgs() << "Captured due to too many uses\n");
66 CC = Mask;
67 }
68
69 Action captured(const Use *U, UseCaptureInfo CI) override {
70 if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
71 return ContinueIgnoringReturn;
72
73 if (capturesNothing(CI.UseCC & Mask))
74 return Continue;
75
76 LLVM_DEBUG(dbgs() << "Captured by: " << *U->getUser() << "\n");
77 CC |= CI.UseCC & Mask;
78 return StopFn(CC) ? Stop : Continue;
79 }
80
81 bool ReturnCaptures;
82 CaptureComponents Mask;
83 function_ref<bool(CaptureComponents)> StopFn;
84
85 CaptureComponents CC = CaptureComponents::None;
86};
87
88/// Only find pointer captures which happen before the given instruction. Uses
89/// the dominator tree to determine whether one instruction is before another.
90/// Only support the case where the Value is defined in the same basic block
91/// as the given instruction and the use.
92struct CapturesBefore : public CaptureTracker {
93
94 CapturesBefore(bool ReturnCaptures, const Instruction *I,
95 const DominatorTree *DT, bool IncludeI, const LoopInfo *LI,
96 CaptureComponents Mask,
97 function_ref<bool(CaptureComponents)> StopFn)
98 : BeforeHere(I), DT(DT), ReturnCaptures(ReturnCaptures),
99 IncludeI(IncludeI), LI(LI), Mask(Mask), StopFn(StopFn) {}
100
101 void tooManyUses() override { CC = Mask; }
102
103 bool isSafeToPrune(Instruction *I) {
104 if (BeforeHere == I)
105 return !IncludeI;
106
107 // We explore this usage only if the usage can reach "BeforeHere".
108 // If use is not reachable from entry, there is no need to explore.
109 if (!DT->isReachableFromEntry(I->getParent()))
110 return true;
111
112 // Check whether there is a path from I to BeforeHere.
113 return !isPotentiallyReachable(I, BeforeHere, nullptr, DT, LI);
114 }
115
116 Action captured(const Use *U, UseCaptureInfo CI) override {
117 Instruction *I = cast<Instruction>(U->getUser());
118 if (isa<ReturnInst>(I) && !ReturnCaptures)
119 return ContinueIgnoringReturn;
120
121 // Check isSafeToPrune() here rather than in shouldExplore() to avoid
122 // an expensive reachability query for every instruction we look at.
123 // Instead we only do one for actual capturing candidates.
124 if (isSafeToPrune(I))
125 // If the use is not reachable, the instruction result isn't either.
126 return ContinueIgnoringReturn;
127
128 if (capturesNothing(CI.UseCC & Mask))
129 return Continue;
130
131 CC |= CI.UseCC & Mask;
132 return StopFn(CC) ? Stop : Continue;
133 }
134
135 const Instruction *BeforeHere;
136 const DominatorTree *DT;
137
138 bool ReturnCaptures;
139 bool IncludeI;
140
141 CaptureComponents CC = CaptureComponents::None;
142
143 const LoopInfo *LI;
144 CaptureComponents Mask;
145 function_ref<bool(CaptureComponents)> StopFn;
146};
147
148/// Find the 'earliest' instruction before which the pointer is known not to
149/// be captured. Here an instruction A is considered earlier than instruction
150/// B, if A dominates B. If 2 escapes do not dominate each other, the
151/// terminator of the common dominator is chosen. If not all uses cannot be
152/// analyzed, the earliest escape is set to the first instruction in the
153/// function entry block.
154// NOTE: Users have to make sure instructions compared against the earliest
155// escape are not in a cycle.
156struct EarliestCaptures : public CaptureTracker {
157
158 EarliestCaptures(bool ReturnCaptures, Function &F, const DominatorTree &DT,
159 CaptureComponents Mask)
160 : DT(DT), ReturnCaptures(ReturnCaptures), F(F), Mask(Mask) {}
161
162 void tooManyUses() override {
163 CC = Mask;
164 EarliestCapture = &*F.getEntryBlock().begin();
165 }
166
167 Action captured(const Use *U, UseCaptureInfo CI) override {
168 Instruction *I = cast<Instruction>(U->getUser());
169 if (isa<ReturnInst>(I) && !ReturnCaptures)
170 return ContinueIgnoringReturn;
171
172 if (capturesAnything(CI.UseCC & Mask)) {
173 if (!EarliestCapture)
174 EarliestCapture = I;
175 else
176 EarliestCapture = DT.findNearestCommonDominator(EarliestCapture, I);
177 CC |= CI.UseCC & Mask;
178 }
179
180 // Continue analysis, as we need to see all potential captures.
181 return Continue;
182 }
183
184 const DominatorTree &DT;
185 bool ReturnCaptures;
186 Function &F;
187 CaptureComponents Mask;
188
189 Instruction *EarliestCapture = nullptr;
190 CaptureComponents CC = CaptureComponents::None;
191};
192} // namespace
193
195 const Value *V, bool ReturnCaptures, CaptureComponents Mask,
196 function_ref<bool(CaptureComponents)> StopFn, unsigned MaxUsesToExplore) {
198 "It doesn't make sense to ask whether a global is captured.");
199
200 LLVM_DEBUG(dbgs() << "Captured?: " << *V << " = ");
201
202 SimpleCaptureTracker SCT(ReturnCaptures, Mask, StopFn);
203 PointerMayBeCaptured(V, &SCT, MaxUsesToExplore);
204 if (capturesAnything(SCT.CC))
205 ++NumCaptured;
206 else {
207 ++NumNotCaptured;
208 LLVM_DEBUG(dbgs() << "not captured\n");
209 }
210 return SCT.CC;
211}
212
213 bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures,
214 unsigned MaxUsesToExplore) {
215 return capturesAnything(
217 capturesAnything, MaxUsesToExplore));
218}
219
221 const Value *V, bool ReturnCaptures, const Instruction *I,
222 const DominatorTree *DT, bool IncludeI, CaptureComponents Mask,
223 function_ref<bool(CaptureComponents)> StopFn, const LoopInfo *LI,
224 unsigned MaxUsesToExplore) {
226 "It doesn't make sense to ask whether a global is captured.");
227
228 if (!DT)
229 return PointerMayBeCaptured(V, ReturnCaptures, Mask, StopFn,
230 MaxUsesToExplore);
231
232 CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, LI, Mask, StopFn);
233 PointerMayBeCaptured(V, &CB, MaxUsesToExplore);
234 if (capturesAnything(CB.CC))
235 ++NumCapturedBefore;
236 else
237 ++NumNotCapturedBefore;
238 return CB.CC;
239}
240
241 bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
242 const Instruction *I,
243 const DominatorTree *DT, bool IncludeI,
244 unsigned MaxUsesToExplore,
245 const LoopInfo *LI) {
247 V, ReturnCaptures, I, DT, IncludeI, CaptureComponents::All,
248 capturesAnything, LI, MaxUsesToExplore));
249}
250
251std::pair<Instruction *, CaptureComponents>
252 llvm::FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures,
253 const DominatorTree &DT, CaptureComponents Mask,
254 unsigned MaxUsesToExplore) {
256 "It doesn't make sense to ask whether a global is captured.");
257
258 EarliestCaptures CB(ReturnCaptures, F, DT, Mask);
259 PointerMayBeCaptured(V, &CB, MaxUsesToExplore);
260 if (capturesAnything(CB.CC))
261 ++NumCapturedBefore;
262 else
263 ++NumNotCapturedBefore;
264 return {CB.EarliestCapture, CB.CC};
265}
266
268 Instruction *I = dyn_cast<Instruction>(U.getUser());
269
270 // TODO: Investigate non-instruction uses.
271 if (!I)
273
274 switch (I->getOpcode()) {
275 case Instruction::Call:
276 case Instruction::Invoke: {
277 auto *Call = cast<CallBase>(I);
278 // The pointer is not captured if returned pointer is not captured.
279 // NOTE: CaptureTracking users should not assume that only functions
280 // marked with nocapture do not capture. This means that places like
281 // getUnderlyingObject in ValueTracking or DecomposeGEPExpression
282 // in BasicAA also need to know about this property.
285
286 // Volatile operations effectively capture the memory location that they
287 // load and store to.
288 if (auto *MI = dyn_cast<MemIntrinsic>(Call))
289 if (MI->isVolatile())
291
292 // Calling a function pointer does not in itself cause the pointer to
293 // be captured. This is a subtle point considering that (for example)
294 // the callee might return its own address. It is analogous to saying
295 // that loading a value from a pointer does not cause the pointer to be
296 // captured, even though the loaded value might be the pointer itself
297 // (think of self-referential objects).
298 if (Call->isCallee(&U))
300
301 assert(Call->isDataOperand(&U) && "Non-callee must be data operand");
302 CaptureInfo CI = Call->getCaptureInfo(Call->getDataOperandNo(&U));
303
304 // If the call is readonly and doesn't return a value, only the address
305 // may be captured.
307 if (Call->onlyReadsMemory() && Call->getType()->isVoidTy())
309
310 return UseCaptureInfo(CI.getOtherComponents() & Mask,
311 CI.getRetComponents());
312 }
313 case Instruction::Load:
314 // Volatile loads make the address observable.
315 if (cast<LoadInst>(I)->isVolatile())
318 case Instruction::VAArg:
319 // "va-arg" from a pointer does not cause it to be captured.
321 case Instruction::Store:
322 // Stored the pointer - conservatively assume it may be captured.
323 if (U.getOperandNo() == 0)
325 I->getMetadata(LLVMContext::MD_captures));
326
327 // Volatile stores make the address observable.
328 if (cast<StoreInst>(I)->isVolatile())
331 case Instruction::AtomicRMW: {
332 // atomicrmw conceptually includes both a load and store from
333 // the same location.
334 // As with a store, the location being accessed is not captured,
335 // but the value being stored is.
336 // Volatile stores make the address observable.
337 auto *ARMWI = cast<AtomicRMWInst>(I);
338 if (U.getOperandNo() == 1 || ARMWI->isVolatile())
341 }
342 case Instruction::AtomicCmpXchg: {
343 // cmpxchg conceptually includes both a load and store from
344 // the same location.
345 // As with a store, the location being accessed is not captured,
346 // but the value being stored is.
347 // Volatile stores make the address observable.
348 auto *ACXI = cast<AtomicCmpXchgInst>(I);
349 if (U.getOperandNo() == 1 || U.getOperandNo() == 2 || ACXI->isVolatile())
352 }
353 case Instruction::GetElementPtr:
354 // AA does not support pointers of vectors, so GEP vector splats need to
355 // be considered as captures.
356 if (I->getType()->isVectorTy())
359 case Instruction::BitCast:
360 case Instruction::PHI:
361 case Instruction::Select:
362 case Instruction::AddrSpaceCast:
363 // The original value is not captured via this if the new value isn't.
365 case Instruction::PtrToAddr:
366 // We treat ptrtoaddr as a location-independent capture of the address even
367 // if it is ultimately not used. Continuing recursive analysis after
368 // ptrtoaddr would be possible, but we'd need logic to do that correctly,
369 // which is not the same as the current pointer following logic.
371 case Instruction::ICmp: {
372 unsigned Idx = U.getOperandNo();
373 unsigned OtherIdx = 1 - Idx;
374 if (isa<ConstantPointerNull>(I->getOperand(OtherIdx)) &&
375 cast<ICmpInst>(I)->isEquality()) {
376 // TODO(captures): Remove these special cases once we make use of
377 // captures(address_is_null).
378
379 // Don't count comparisons of a no-alias return value against null as
380 // captures. This allows us to ignore comparisons of malloc results
381 // with null, for example.
382 if (U->getType()->getPointerAddressSpace() == 0)
383 if (isNoAliasCall(U.get()->stripPointerCasts()))
385
386 // Check whether this is a comparison of the base pointer against
387 // null.
388 if (U.get() == Base)
390 }
391
392 // Otherwise, be conservative. There are crazy ways to capture pointers
393 // using comparisons. However, only the address is captured, not the
394 // provenance.
396 }
397 default:
398 // Something else - be conservative and say it is captured.
400 }
401}
402
404 unsigned MaxUsesToExplore) {
405 assert(V->getType()->isPointerTy() && "Capture is for pointers only!");
406 if (MaxUsesToExplore == 0)
407 MaxUsesToExplore = DefaultMaxUsesToExplore;
408
412
413 auto AddUses = [&](const Value *V) {
414 for (const Use &U : V->uses()) {
415 // If there are lots of uses, conservatively say that the value
416 // is captured to avoid taking too much compile time.
417 if (Visited.size() >= MaxUsesToExplore) {
418 Tracker->tooManyUses();
419 return false;
420 }
421 if (!Visited.insert(&U).second)
422 continue;
423 if (!Tracker->shouldExplore(&U))
424 continue;
425 Worklist.push_back(&U);
426 }
427 return true;
428 };
429 if (!AddUses(V))
430 return;
431
432 while (!Worklist.empty()) {
433 const Use *U = Worklist.pop_back_val();
435 if (capturesAnything(CI.UseCC)) {
436 switch (Tracker->captured(U, CI)) {
438 return;
440 continue;
442 // Fall through to passthrough handling, but only if ResultCC contains
443 // additional components that UseCC does not. We assume that a
444 // capture at this point will be strictly more constraining than a
445 // later capture from following the return value.
446 if (capturesNothing(CI.ResultCC & ~CI.UseCC))
447 continue;
448 break;
449 }
450 }
451 // TODO(captures): We could keep track of ResultCC for the users.
452 if (capturesAnything(CI.ResultCC) && !AddUses(U->getUser()))
453 return;
454 }
455
456 // All uses examined.
457}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static cl::opt< unsigned > DefaultMaxUsesToExplore("capture-tracking-max-uses-to-explore", cl::Hidden, cl::desc("Maximal number of uses to explore."), cl::init(100))
The default value for MaxUsesToExplore argument.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
IRTranslator LLVM IR MI
F
#define F(x, y, z)
Definition MD5.cpp:55
I
#define I(x, y, z)
Definition MD5.cpp:58
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:114
Represents which components of the pointer may be captured in which location.
Definition ModRef.h:354
CaptureComponents getOtherComponents() const
Get components potentially captured through locations other than the return value.
Definition ModRef.h:386
CaptureComponents getRetComponents() const
Get components potentially captured by the return value.
Definition ModRef.h:382
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:165
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition Dominators.cpp:334
LLVM_ABI Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const
Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...
Definition Dominators.cpp:357
static LLVM_ABI CaptureComponents toCaptureComponents(const MDNode *MD)
Convert !captures metadata to CaptureComponents. MD may be nullptr.
Definition Metadata.cpp:1439
size_type size() const
Definition SmallPtrSet.h:99
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:389
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition SmallPtrSet.h:527
void reserve(size_type N)
Definition SmallVector.h:664
void push_back(const T &Elt)
Definition SmallVector.h:417
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition SmallVector.h:1203
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
LLVM Value Representation.
Definition Value.h:75
iterator_range< use_iterator > uses()
Definition Value.h:380
An efficient, type-erasing, non-owning reference to a callable.
CallInst * Call
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition BitmaskEnum.h:127
initializer< Ty > init(const Ty &Val)
Definition CommandLine.h:445
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
This is an optimization pass for GlobalISel generic memory operations.
Definition AddressRanges.h:18
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
LLVM_ABI std::pair< Instruction *, CaptureComponents > FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures, const DominatorTree &DT, CaptureComponents Mask, unsigned MaxUsesToExplore=0)
LLVM_ABI bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
LLVM_ABI unsigned getDefaultMaxUsesToExploreForCaptureTracking()
getDefaultMaxUsesToExploreForCaptureTracking - Return default value of the maximal number of uses to ...
LLVM_ABI bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, const Instruction *I, const DominatorTree *DT, bool IncludeI=false, unsigned MaxUsesToExplore=0, const LoopInfo *LI=nullptr)
PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...
LLVM_ABI bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(const CallBase *Call, bool MustPreserveNullness)
{launder,strip}.invariant.group returns pointer that aliases its argument, and it only captures point...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
CaptureComponents
Components of the pointer that may be captured.
Definition ModRef.h:305
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
bool capturesAnything(CaptureComponents CC)
Definition ModRef.h:319
@ Continue
Definition DWP.h:22
LLVM_ABI UseCaptureInfo DetermineUseCaptureKind(const Use &U, const Value *Base)
Determine what kind of capture behaviour U may exhibit.
bool capturesNothing(CaptureComponents CC)
Definition ModRef.h:315
LLVM_ABI bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
Definition CFG.cpp:282
This callback is used in conjunction with PointerMayBeCaptured.
virtual bool shouldExplore(const Use *U)
shouldExplore - This is the use of a value derived from the pointer.
@ ContinueIgnoringReturn
Continue traversal, but do not follow the return value of the user, even if it has additional capture...
@ Continue
Continue traversal, and also follow the return value of the user if it has additional capture compone...
@ Stop
Stop the traversal.
virtual Action captured(const Use *U, UseCaptureInfo CI)=0
Use U directly captures CI.UseCC and additionally CI.ResultCC through the return value of the user of...
virtual void tooManyUses()=0
tooManyUses - The depth of traversal has breached a limit.
virtual ~CaptureTracker()
Capture information for a specific Use.
CaptureComponents UseCC
Components captured by this use.
CaptureComponents ResultCC
Components captured by the return value of the user of this Use.
static UseCaptureInfo passthrough()
Generated on for LLVM by doxygen 1.14.0

AltStyle によって変換されたページ (->オリジナル) /