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
34STATISTIC(NumCaptured, "Number of pointers maybe captured");
35STATISTIC(NumNotCaptured, "Number of pointers not captured");
36STATISTIC(NumCapturedBefore, "Number of pointers maybe captured before");
37STATISTIC(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(Val: 100));
49
50unsigned llvm::getDefaultMaxUsesToExploreForCaptureTracking() {
51 return DefaultMaxUsesToExplore;
52}
53
54CaptureTracker::~CaptureTracker() = default;
55
56bool 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>(Val: U->getUser()) && !ReturnCaptures)
71 return ContinueIgnoringReturn;
72
73 if (capturesNothing(CC: 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(A: I->getParent()))
110 return true;
111
112 // Check whether there is a path from I to BeforeHere.
113 return !isPotentiallyReachable(From: I, To: BeforeHere, ExclusionSet: nullptr, DT, LI);
114 }
115
116 Action captured(const Use *U, UseCaptureInfo CI) override {
117 Instruction *I = cast<Instruction>(Val: U->getUser());
118 if (isa<ReturnInst>(Val: 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(CC: 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>(Val: U->getUser());
169 if (isa<ReturnInst>(Val: I) && !ReturnCaptures)
170 return ContinueIgnoringReturn;
171
172 if (capturesAnything(CC: CI.UseCC & Mask)) {
173 if (!EarliestCapture)
174 EarliestCapture = I;
175 else
176 EarliestCapture = DT.findNearestCommonDominator(I1: EarliestCapture, I2: 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
194CaptureComponents llvm::PointerMayBeCaptured(
195 const Value *V, bool ReturnCaptures, CaptureComponents Mask,
196 function_ref<bool(CaptureComponents)> StopFn, unsigned MaxUsesToExplore) {
197 assert(!isa<GlobalValue>(V) &&
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, Tracker: &SCT, MaxUsesToExplore);
204 if (capturesAnything(CC: SCT.CC))
205 ++NumCaptured;
206 else {
207 ++NumNotCaptured;
208 LLVM_DEBUG(dbgs() << "not captured\n");
209 }
210 return SCT.CC;
211}
212
213bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures,
214 unsigned MaxUsesToExplore) {
215 return capturesAnything(
216 CC: PointerMayBeCaptured(V, ReturnCaptures, Mask: CaptureComponents::All,
217 StopFn: capturesAnything, MaxUsesToExplore));
218}
219
220CaptureComponents llvm::PointerMayBeCapturedBefore(
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) {
225 assert(!isa<GlobalValue>(V) &&
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, Tracker: &CB, MaxUsesToExplore);
234 if (capturesAnything(CC: CB.CC))
235 ++NumCapturedBefore;
236 else
237 ++NumNotCapturedBefore;
238 return CB.CC;
239}
240
241bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
242 const Instruction *I,
243 const DominatorTree *DT, bool IncludeI,
244 unsigned MaxUsesToExplore,
245 const LoopInfo *LI) {
246 return capturesAnything(CC: PointerMayBeCapturedBefore(
247 V, ReturnCaptures, I, DT, IncludeI, Mask: CaptureComponents::All,
248 StopFn: capturesAnything, LI, MaxUsesToExplore));
249}
250
251std::pair<Instruction *, CaptureComponents>
252llvm::FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures,
253 const DominatorTree &DT, CaptureComponents Mask,
254 unsigned MaxUsesToExplore) {
255 assert(!isa<GlobalValue>(V) &&
256 "It doesn't make sense to ask whether a global is captured.");
257
258 EarliestCaptures CB(ReturnCaptures, F, DT, Mask);
259 PointerMayBeCaptured(V, Tracker: &CB, MaxUsesToExplore);
260 if (capturesAnything(CC: CB.CC))
261 ++NumCapturedBefore;
262 else
263 ++NumNotCapturedBefore;
264 return {CB.EarliestCapture, CB.CC};
265}
266
267UseCaptureInfo llvm::DetermineUseCaptureKind(const Use &U, const Value *Base) {
268 Instruction *I = dyn_cast<Instruction>(Val: U.getUser());
269
270 // TODO: Investigate non-instruction uses.
271 if (!I)
272 return CaptureComponents::All;
273
274 switch (I->getOpcode()) {
275 case Instruction::Call:
276 case Instruction::Invoke: {
277 auto *Call = cast<CallBase>(Val: 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.
283 if (isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(Call, MustPreserveNullness: true))
284 return UseCaptureInfo::passthrough();
285
286 // Volatile operations effectively capture the memory location that they
287 // load and store to.
288 if (auto *MI = dyn_cast<MemIntrinsic>(Val: Call))
289 if (MI->isVolatile())
290 return CaptureComponents::All;
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: &U))
299 return CaptureComponents::None;
300
301 assert(Call->isDataOperand(&U) && "Non-callee must be data operand");
302 CaptureInfo CI = Call->getCaptureInfo(OpNo: Call->getDataOperandNo(U: &U));
303
304 // If the call is readonly and doesn't return a value, only the address
305 // may be captured.
306 CaptureComponents Mask = CaptureComponents::All;
307 if (Call->onlyReadsMemory() && Call->getType()->isVoidTy())
308 Mask = CaptureComponents::Address;
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>(Val: I)->isVolatile())
316 return CaptureComponents::All;
317 return CaptureComponents::None;
318 case Instruction::VAArg:
319 // "va-arg" from a pointer does not cause it to be captured.
320 return CaptureComponents::None;
321 case Instruction::Store:
322 // Stored the pointer - conservatively assume it may be captured.
323 if (U.getOperandNo() == 0)
324 return MDNode::toCaptureComponents(
325 MD: I->getMetadata(KindID: LLVMContext::MD_captures));
326
327 // Volatile stores make the address observable.
328 if (cast<StoreInst>(Val: I)->isVolatile())
329 return CaptureComponents::All;
330 return CaptureComponents::None;
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>(Val: I);
338 if (U.getOperandNo() == 1 || ARMWI->isVolatile())
339 return CaptureComponents::All;
340 return CaptureComponents::None;
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>(Val: I);
349 if (U.getOperandNo() == 1 || U.getOperandNo() == 2 || ACXI->isVolatile())
350 return CaptureComponents::All;
351 return CaptureComponents::None;
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())
357 return CaptureComponents::All;
358 return UseCaptureInfo::passthrough();
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.
364 return UseCaptureInfo::passthrough();
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.
370 return CaptureComponents::Address;
371 case Instruction::ICmp: {
372 unsigned Idx = U.getOperandNo();
373 unsigned OtherIdx = 1 - Idx;
374 if (isa<ConstantPointerNull>(Val: I->getOperand(i: OtherIdx)) &&
375 cast<ICmpInst>(Val: 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(V: U.get()->stripPointerCasts()))
384 return CaptureComponents::None;
385
386 // Check whether this is a comparison of the base pointer against
387 // null.
388 if (U.get() == Base)
389 return CaptureComponents::AddressIsNull;
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.
395 return CaptureComponents::Address;
396 }
397 default:
398 // Something else - be conservative and say it is captured.
399 return CaptureComponents::All;
400 }
401}
402
403void llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker,
404 unsigned MaxUsesToExplore) {
405 assert(V->getType()->isPointerTy() && "Capture is for pointers only!");
406 if (MaxUsesToExplore == 0)
407 MaxUsesToExplore = DefaultMaxUsesToExplore;
408
409 SmallVector<const Use *, 20> Worklist;
410 Worklist.reserve(N: getDefaultMaxUsesToExploreForCaptureTracking());
411 SmallPtrSet<const Use *, 20> Visited;
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(Ptr: &U).second)
422 continue;
423 if (!Tracker->shouldExplore(U: &U))
424 continue;
425 Worklist.push_back(Elt: &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();
434 UseCaptureInfo CI = DetermineUseCaptureKind(U: *U, Base: V);
435 if (capturesAnything(CC: CI.UseCC)) {
436 switch (Tracker->captured(U, CI)) {
437 case CaptureTracker::Stop:
438 return;
439 case CaptureTracker::ContinueIgnoringReturn:
440 continue;
441 case CaptureTracker::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(CC: 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(CC: CI.ResultCC) && !AddUses(U->getUser()))
453 return;
454 }
455
456 // All uses examined.
457}
458