LLVM 18.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
20#include "llvm/ADT/SmallSet.h"
22#include "llvm/ADT/Statistic.h"
24#include "llvm/Analysis/CFG.h"
26#include "llvm/IR/Constants.h"
27#include "llvm/IR/Dominators.h"
31
32using namespace llvm;
33
34#define DEBUG_TYPE "capture-tracking"
35
36STATISTIC(NumCaptured, "Number of pointers maybe captured");
37STATISTIC(NumNotCaptured, "Number of pointers not captured");
38STATISTIC(NumCapturedBefore, "Number of pointers maybe captured before");
39STATISTIC(NumNotCapturedBefore, "Number of pointers not captured before");
40
41/// The default value for MaxUsesToExplore argument. It's relatively small to
42/// keep the cost of analysis reasonable for clients like BasicAliasAnalysis,
43/// where the results can't be cached.
44/// TODO: we should probably introduce a caching CaptureTracking analysis and
45/// use it where possible. The caching version can use much higher limit or
46/// don't have this cap at all.
48 DefaultMaxUsesToExplore("capture-tracking-max-uses-to-explore", cl::Hidden,
49 cl::desc("Maximal number of uses to explore."),
50 cl::init(100));
51
54}
55
57
58bool CaptureTracker::shouldExplore(const Use *U) { return true; }
59
61 // We want comparisons to null pointers to not be considered capturing,
62 // but need to guard against cases like gep(p, -ptrtoint(p2)) == null,
63 // which are equivalent to p == p2 and would capture the pointer.
64 //
65 // A dereferenceable pointer is a case where this is known to be safe,
66 // because the pointer resulting from such a construction would not be
67 // dereferenceable.
68 //
69 // It is not sufficient to check for inbounds GEP here, because GEP with
70 // zero offset is always inbounds.
71 bool CanBeNull, CanBeFreed;
72 return O->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
73}
74
75namespace {
76 struct SimpleCaptureTracker : public CaptureTracker {
77 explicit SimpleCaptureTracker(
78
79 const SmallPtrSetImpl<const Value *> &EphValues, bool ReturnCaptures)
80 : EphValues(EphValues), ReturnCaptures(ReturnCaptures) {}
81
82 void tooManyUses() override {
83 LLVM_DEBUG(dbgs() << "Captured due to too many uses\n");
84 Captured = true;
85 }
86
87 bool captured(const Use *U) override {
88 if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
89 return false;
90
91 if (EphValues.contains(U->getUser()))
92 return false;
93
94 LLVM_DEBUG(dbgs() << "Captured by: " << *U->getUser() << "\n");
95
96 Captured = true;
97 return true;
98 }
99
100 const SmallPtrSetImpl<const Value *> &EphValues;
101
102 bool ReturnCaptures;
103
104 bool Captured = false;
105 };
106
107 /// Only find pointer captures which happen before the given instruction. Uses
108 /// the dominator tree to determine whether one instruction is before another.
109 /// Only support the case where the Value is defined in the same basic block
110 /// as the given instruction and the use.
111 struct CapturesBefore : public CaptureTracker {
112
113 CapturesBefore(bool ReturnCaptures, const Instruction *I,
114 const DominatorTree *DT, bool IncludeI, const LoopInfo *LI)
115 : BeforeHere(I), DT(DT), ReturnCaptures(ReturnCaptures),
116 IncludeI(IncludeI), LI(LI) {}
117
118 void tooManyUses() override { Captured = true; }
119
120 bool isSafeToPrune(Instruction *I) {
121 if (BeforeHere == I)
122 return !IncludeI;
123
124 // We explore this usage only if the usage can reach "BeforeHere".
125 // If use is not reachable from entry, there is no need to explore.
126 if (!DT->isReachableFromEntry(I->getParent()))
127 return true;
128
129 // Check whether there is a path from I to BeforeHere.
130 return !isPotentiallyReachable(I, BeforeHere, nullptr, DT, LI);
131 }
132
133 bool captured(const Use *U) override {
134 Instruction *I = cast<Instruction>(U->getUser());
135 if (isa<ReturnInst>(I) && !ReturnCaptures)
136 return false;
137
138 // Check isSafeToPrune() here rather than in shouldExplore() to avoid
139 // an expensive reachability query for every instruction we look at.
140 // Instead we only do one for actual capturing candidates.
141 if (isSafeToPrune(I))
142 return false;
143
144 Captured = true;
145 return true;
146 }
147
148 const Instruction *BeforeHere;
149 const DominatorTree *DT;
150
151 bool ReturnCaptures;
152 bool IncludeI;
153
154 bool Captured = false;
155
156 const LoopInfo *LI;
157 };
158
159 /// Find the 'earliest' instruction before which the pointer is known not to
160 /// be captured. Here an instruction A is considered earlier than instruction
161 /// B, if A dominates B. If 2 escapes do not dominate each other, the
162 /// terminator of the common dominator is chosen. If not all uses cannot be
163 /// analyzed, the earliest escape is set to the first instruction in the
164 /// function entry block.
165 // NOTE: Users have to make sure instructions compared against the earliest
166 // escape are not in a cycle.
167 struct EarliestCaptures : public CaptureTracker {
168
169 EarliestCaptures(bool ReturnCaptures, Function &F, const DominatorTree &DT,
170 const SmallPtrSetImpl<const Value *> &EphValues)
171 : EphValues(EphValues), DT(DT), ReturnCaptures(ReturnCaptures), F(F) {}
172
173 void tooManyUses() override {
174 Captured = true;
175 EarliestCapture = &*F.getEntryBlock().begin();
176 }
177
178 bool captured(const Use *U) override {
179 Instruction *I = cast<Instruction>(U->getUser());
180 if (isa<ReturnInst>(I) && !ReturnCaptures)
181 return false;
182
183 if (EphValues.contains(I))
184 return false;
185
186 if (!EarliestCapture)
187 EarliestCapture = I;
188 else
189 EarliestCapture = DT.findNearestCommonDominator(EarliestCapture, I);
190 Captured = true;
191
192 // Return false to continue analysis; we need to see all potential
193 // captures.
194 return false;
195 }
196
197 const SmallPtrSetImpl<const Value *> &EphValues;
198
199 Instruction *EarliestCapture = nullptr;
200
201 const DominatorTree &DT;
202
203 bool ReturnCaptures;
204
205 bool Captured = false;
206
207 Function &F;
208 };
209}
210
211/// PointerMayBeCaptured - Return true if this pointer value may be captured
212/// by the enclosing function (which is required to exist). This routine can
213/// be expensive, so consider caching the results. The boolean ReturnCaptures
214/// specifies whether returning the value (or part of it) from the function
215/// counts as capturing it or not. The boolean StoreCaptures specified whether
216/// storing the value (or part of it) into memory anywhere automatically
217/// counts as capturing it or not.
218bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures,
219 bool StoreCaptures, unsigned MaxUsesToExplore) {
221 return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures, Empty,
222 MaxUsesToExplore);
223}
224
225/// Variant of the above function which accepts a set of Values that are
226/// ephemeral and cannot cause pointers to escape.
227bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures,
228 bool StoreCaptures,
229 const SmallPtrSetImpl<const Value *> &EphValues,
230 unsigned MaxUsesToExplore) {
231 assert(!isa<GlobalValue>(V) &&
232 "It doesn't make sense to ask whether a global is captured.");
233
234 // TODO: If StoreCaptures is not true, we could do Fancy analysis
235 // to determine whether this store is not actually an escape point.
236 // In that case, BasicAliasAnalysis should be updated as well to
237 // take advantage of this.
238 (void)StoreCaptures;
239
240 LLVM_DEBUG(dbgs() << "Captured?: " << *V << " = ");
241
242 SimpleCaptureTracker SCT(EphValues, ReturnCaptures);
243 PointerMayBeCaptured(V, &SCT, MaxUsesToExplore);
244 if (SCT.Captured)
245 ++NumCaptured;
246 else {
247 ++NumNotCaptured;
248 LLVM_DEBUG(dbgs() << "not captured\n");
249 }
250 return SCT.Captured;
251}
252
253/// PointerMayBeCapturedBefore - Return true if this pointer value may be
254/// captured by the enclosing function (which is required to exist). If a
255/// DominatorTree is provided, only captures which happen before the given
256/// instruction are considered. This routine can be expensive, so consider
257/// caching the results. The boolean ReturnCaptures specifies whether
258/// returning the value (or part of it) from the function counts as capturing
259/// it or not. The boolean StoreCaptures specified whether storing the value
260/// (or part of it) into memory anywhere automatically counts as capturing it
261/// or not.
262bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
263 bool StoreCaptures, const Instruction *I,
264 const DominatorTree *DT, bool IncludeI,
265 unsigned MaxUsesToExplore,
266 const LoopInfo *LI) {
267 assert(!isa<GlobalValue>(V) &&
268 "It doesn't make sense to ask whether a global is captured.");
269
270 if (!DT)
271 return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures,
272 MaxUsesToExplore);
273
274 // TODO: See comment in PointerMayBeCaptured regarding what could be done
275 // with StoreCaptures.
276
277 CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, LI);
278 PointerMayBeCaptured(V, &CB, MaxUsesToExplore);
279 if (CB.Captured)
280 ++NumCapturedBefore;
281 else
282 ++NumNotCapturedBefore;
283 return CB.Captured;
284}
285
287llvm::FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures,
288 bool StoreCaptures, const DominatorTree &DT,
289
290 const SmallPtrSetImpl<const Value *> &EphValues,
291 unsigned MaxUsesToExplore) {
292 assert(!isa<GlobalValue>(V) &&
293 "It doesn't make sense to ask whether a global is captured.");
294
295 EarliestCaptures CB(ReturnCaptures, F, DT, EphValues);
296 PointerMayBeCaptured(V, &CB, MaxUsesToExplore);
297 if (CB.Captured)
298 ++NumCapturedBefore;
299 else
300 ++NumNotCapturedBefore;
301 return CB.EarliestCapture;
302}
303
305 const Use &U,
306 function_ref<bool(Value *, const DataLayout &)> IsDereferenceableOrNull) {
307 Instruction *I = dyn_cast<Instruction>(U.getUser());
308
309 // TODO: Investigate non-instruction uses.
310 if (!I)
312
313 switch (I->getOpcode()) {
314 case Instruction::Call:
315 case Instruction::Invoke: {
316 auto *Call = cast<CallBase>(I);
317 // Not captured if the callee is readonly, doesn't return a copy through
318 // its return value and doesn't unwind (a readonly function can leak bits
319 // by throwing an exception or not depending on the input value).
320 if (Call->onlyReadsMemory() && Call->doesNotThrow() &&
321 Call->getType()->isVoidTy())
323
324 // The pointer is not captured if returned pointer is not captured.
325 // NOTE: CaptureTracking users should not assume that only functions
326 // marked with nocapture do not capture. This means that places like
327 // getUnderlyingObject in ValueTracking or DecomposeGEPExpression
328 // in BasicAA also need to know about this property.
331
332 // Volatile operations effectively capture the memory location that they
333 // load and store to.
334 if (auto *MI = dyn_cast<MemIntrinsic>(Call))
335 if (MI->isVolatile())
337
338 // Calling a function pointer does not in itself cause the pointer to
339 // be captured. This is a subtle point considering that (for example)
340 // the callee might return its own address. It is analogous to saying
341 // that loading a value from a pointer does not cause the pointer to be
342 // captured, even though the loaded value might be the pointer itself
343 // (think of self-referential objects).
344 if (Call->isCallee(&U))
346
347 // Not captured if only passed via 'nocapture' arguments.
348 if (Call->isDataOperand(&U) &&
349 !Call->doesNotCapture(Call->getDataOperandNo(&U))) {
350 // The parameter is not marked 'nocapture' - captured.
352 }
354 }
355 case Instruction::Load:
356 // Volatile loads make the address observable.
357 if (cast<LoadInst>(I)->isVolatile())
360 case Instruction::VAArg:
361 // "va-arg" from a pointer does not cause it to be captured.
363 case Instruction::Store:
364 // Stored the pointer - conservatively assume it may be captured.
365 // Volatile stores make the address observable.
366 if (U.getOperandNo() == 0 || cast<StoreInst>(I)->isVolatile())
369 case Instruction::AtomicRMW: {
370 // atomicrmw conceptually includes both a load and store from
371 // the same location.
372 // As with a store, the location being accessed is not captured,
373 // but the value being stored is.
374 // Volatile stores make the address observable.
375 auto *ARMWI = cast<AtomicRMWInst>(I);
376 if (U.getOperandNo() == 1 || ARMWI->isVolatile())
379 }
380 case Instruction::AtomicCmpXchg: {
381 // cmpxchg conceptually includes both a load and store from
382 // the same location.
383 // As with a store, the location being accessed is not captured,
384 // but the value being stored is.
385 // Volatile stores make the address observable.
386 auto *ACXI = cast<AtomicCmpXchgInst>(I);
387 if (U.getOperandNo() == 1 || U.getOperandNo() == 2 || ACXI->isVolatile())
390 }
391 case Instruction::BitCast:
392 case Instruction::GetElementPtr:
393 case Instruction::PHI:
394 case Instruction::Select:
395 case Instruction::AddrSpaceCast:
396 // The original value is not captured via this if the new value isn't.
398 case Instruction::ICmp: {
399 unsigned Idx = U.getOperandNo();
400 unsigned OtherIdx = 1 - Idx;
401 if (auto *CPN = dyn_cast<ConstantPointerNull>(I->getOperand(OtherIdx))) {
402 // Don't count comparisons of a no-alias return value against null as
403 // captures. This allows us to ignore comparisons of malloc results
404 // with null, for example.
405 if (CPN->getType()->getAddressSpace() == 0)
406 if (isNoAliasCall(U.get()->stripPointerCasts()))
408 if (!I->getFunction()->nullPointerIsDefined()) {
409 auto *O = I->getOperand(Idx)->stripPointerCastsSameRepresentation();
410 // Comparing a dereferenceable_or_null pointer against null cannot
411 // lead to pointer escapes, because if it is not null it must be a
412 // valid (in-bounds) pointer.
413 const DataLayout &DL = I->getModule()->getDataLayout();
414 if (IsDereferenceableOrNull && IsDereferenceableOrNull(O, DL))
416 }
417 }
418
419 // Otherwise, be conservative. There are crazy ways to capture pointers
420 // using comparisons.
422 }
423 default:
424 // Something else - be conservative and say it is captured.
426 }
427}
428
430 unsigned MaxUsesToExplore) {
431 assert(V->getType()->isPointerTy() && "Capture is for pointers only!");
432 if (MaxUsesToExplore == 0)
433 MaxUsesToExplore = DefaultMaxUsesToExplore;
434
438
439 auto AddUses = [&](const Value *V) {
440 for (const Use &U : V->uses()) {
441 // If there are lots of uses, conservatively say that the value
442 // is captured to avoid taking too much compile time.
443 if (Visited.size() >= MaxUsesToExplore) {
444 Tracker->tooManyUses();
445 return false;
446 }
447 if (!Visited.insert(&U).second)
448 continue;
449 if (!Tracker->shouldExplore(&U))
450 continue;
451 Worklist.push_back(&U);
452 }
453 return true;
454 };
455 if (!AddUses(V))
456 return;
457
458 auto IsDereferenceableOrNull = [Tracker](Value *V, const DataLayout &DL) {
459 return Tracker->isDereferenceableOrNull(V, DL);
460 };
461 while (!Worklist.empty()) {
462 const Use *U = Worklist.pop_back_val();
463 switch (DetermineUseCaptureKind(*U, IsDereferenceableOrNull)) {
465 continue;
467 if (Tracker->captured(U))
468 return;
469 continue;
471 if (!AddUses(U->getUser()))
472 return;
473 continue;
474 }
475 }
476
477 // All uses examined.
478}
479
481 const Value *V, SmallDenseMap<const Value *, bool, 8> *IsCapturedCache) {
483 if (IsCapturedCache) {
484 bool Inserted;
485 std::tie(CacheIt, Inserted) = IsCapturedCache->insert({V, false});
486 if (!Inserted)
487 // Found cached result, return it!
488 return CacheIt->second;
489 }
490
491 // If this is an identified function-local object, check to see if it escapes.
493 // Set StoreCaptures to True so that we can assume in our callers that the
494 // pointer is not the result of a load instruction. Currently
495 // PointerMayBeCaptured doesn't have any special analysis for the
496 // StoreCaptures=false case; if it did, our callers could be refined to be
497 // more precise.
498 auto Ret = !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
499 if (IsCapturedCache)
500 CacheIt->second = Ret;
501 return Ret;
502 }
503
504 return false;
505}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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...
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 LLVM_DEBUG(X)
Definition: Debug.h:101
IRTranslator LLVM IR MI
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
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:167
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
size_type size() const
Definition: SmallSet.h:161
bool empty() const
Definition: SmallVector.h:94
void reserve(size_type N)
Definition: SmallVector.h:667
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
An efficient, type-erasing, non-owning reference to a callable.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
UseCaptureKind DetermineUseCaptureKind(const Use &U, llvm::function_ref< bool(Value *, const DataLayout &)> IsDereferenceableOrNull)
Determine what kind of capture behaviour U may exhibit.
bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, 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...
Instruction * FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures, bool StoreCaptures, const DominatorTree &DT, const SmallPtrSetImpl< const Value * > &EphValues, unsigned MaxUsesToExplore=0)
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
bool isNonEscapingLocalObject(const Value *V, SmallDenseMap< const Value *, bool, 8 > *IsCapturedCache=nullptr)
Returns true if the pointer is to a function-local object that never escapes from the function.
unsigned getDefaultMaxUsesToExploreForCaptureTracking()
getDefaultMaxUsesToExploreForCaptureTracking - Return default value of the maximal number of uses to ...
bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(const CallBase *Call, bool MustPreserveNullness)
{launder,strip}.invariant.group returns pointer that aliases its argument, and it only captures point...
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
UseCaptureKind
Types of use capture kinds, see DetermineUseCaptureKind.
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:231
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.
virtual bool isDereferenceableOrNull(Value *O, const DataLayout &DL)
isDereferenceableOrNull - Overload to allow clients with additional knowledge about pointer dereferen...
virtual void tooManyUses()=0
tooManyUses - The depth of traversal has breached a limit.
virtual ~CaptureTracker()
virtual bool captured(const Use *U)=0
captured - Information about the pointer was captured by the user of use U.