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(CaptureComponents Mask,
61 function_ref<bool(CaptureComponents)> StopFn)
62 : Mask(Mask), StopFn(StopFn) {}
63
64 void tooManyUses() override {
65 LLVM_DEBUG(dbgs() << "Captured due to too many uses\n");
66 CC = Mask;
67 CCWithRet = Mask;
68 }
69
70 Action captured(const Use *U, UseCaptureInfo CI) override {
71 if (capturesNothing(CC: CI.UseCC & Mask))
72 return Continue;
73
74 LLVM_DEBUG(dbgs() << "Captured by: " << *U->getUser() << "\n");
75 CCWithRet |= CI.UseCC & Mask;
76 if (!isa<ReturnInst>(Val: U->getUser()))
77 CC |= CI.UseCC & Mask;
78 return StopFn(CC) ? Stop : Continue;
79 }
80
81 CaptureComponents Mask;
82 function_ref<bool(CaptureComponents)> StopFn;
83
84 CaptureComponents CC = CaptureComponents::None;
85 CaptureComponents CCWithRet = 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(Function &F, const DominatorTree &DT, CaptureComponents Mask)
159 : DT(DT), F(F), Mask(Mask) {}
160
161 void tooManyUses() override {
162 CC = Mask;
163 CCWithRet = 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 (capturesAnything(CC: CI.UseCC & Mask)) {
170 CCWithRet |= CI.UseCC & Mask;
171 if (!isa<ReturnInst>(Val: I)) {
172 if (!EarliestCapture)
173 EarliestCapture = I;
174 else
175 EarliestCapture = DT.findNearestCommonDominator(I1: EarliestCapture, I2: I);
176 CC |= CI.UseCC & Mask;
177 }
178 }
179
180 // Continue analysis, as we need to see all potential captures.
181 return Continue;
182 }
183
184 const DominatorTree &DT;
185 Function &F;
186 CaptureComponents Mask;
187
188 Instruction *EarliestCapture = nullptr;
189 CaptureComponents CC = CaptureComponents::None;
190 CaptureComponents CCWithRet = CaptureComponents::None;
191};
192} // namespace
193
194CaptureResult
195llvm::PointerMayBeCaptured(const Value *V, CaptureComponents Mask,
196 function_ref<bool(CaptureComponents)> StopFn,
197 unsigned MaxUsesToExplore) {
198 assert(!isa<GlobalValue>(V) &&
199 "It doesn't make sense to ask whether a global is captured.");
200
201 LLVM_DEBUG(dbgs() << "Captured?: " << *V << " = ");
202
203 SimpleCaptureTracker SCT(Mask, StopFn);
204 PointerMayBeCaptured(V, Tracker: &SCT, MaxUsesToExplore);
205 if (capturesAnything(CC: SCT.CC))
206 ++NumCaptured;
207 else {
208 ++NumNotCaptured;
209 LLVM_DEBUG(dbgs() << "not captured\n");
210 }
211 return {.WithoutRet: SCT.CC, .WithRet: SCT.CCWithRet};
212}
213
214bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures,
215 unsigned MaxUsesToExplore) {
216 CaptureResult Res = PointerMayBeCaptured(V, Mask: CaptureComponents::All,
217 StopFn: capturesAnything, MaxUsesToExplore);
218 return capturesAnything(CC: ReturnCaptures ? Res.WithRet : Res.WithoutRet);
219}
220
221CaptureComponents llvm::PointerMayBeCapturedBefore(
222 const Value *V, bool ReturnCaptures, const Instruction *I,
223 const DominatorTree *DT, bool IncludeI, CaptureComponents Mask,
224 function_ref<bool(CaptureComponents)> StopFn, const LoopInfo *LI,
225 unsigned MaxUsesToExplore) {
226 assert(!isa<GlobalValue>(V) &&
227 "It doesn't make sense to ask whether a global is captured.");
228
229 if (!DT) {
230 CaptureResult Res = PointerMayBeCaptured(V, Mask, StopFn, MaxUsesToExplore);
231 return ReturnCaptures ? Res.WithRet : Res.WithoutRet;
232 }
233
234 CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, LI, Mask, StopFn);
235 PointerMayBeCaptured(V, Tracker: &CB, MaxUsesToExplore);
236 if (capturesAnything(CC: CB.CC))
237 ++NumCapturedBefore;
238 else
239 ++NumNotCapturedBefore;
240 return CB.CC;
241}
242
243bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
244 const Instruction *I,
245 const DominatorTree *DT, bool IncludeI,
246 unsigned MaxUsesToExplore,
247 const LoopInfo *LI) {
248 return capturesAnything(CC: PointerMayBeCapturedBefore(
249 V, ReturnCaptures, I, DT, IncludeI, Mask: CaptureComponents::All,
250 StopFn: capturesAnything, LI, MaxUsesToExplore));
251}
252
253std::pair<Instruction *, CaptureResult>
254llvm::FindEarliestCapture(const Value *V, Function &F, const DominatorTree &DT,
255 CaptureComponents Mask, unsigned MaxUsesToExplore) {
256 assert(!isa<GlobalValue>(V) &&
257 "It doesn't make sense to ask whether a global is captured.");
258
259 EarliestCaptures CB(F, DT, Mask);
260 PointerMayBeCaptured(V, Tracker: &CB, MaxUsesToExplore);
261 if (capturesAnything(CC: CB.CC))
262 ++NumCapturedBefore;
263 else
264 ++NumNotCapturedBefore;
265 return {CB.EarliestCapture, {.WithoutRet: CB.CC, .WithRet: CB.CCWithRet}};
266}
267
268UseCaptureInfo llvm::DetermineUseCaptureKind(const Use &U, const Value *Base) {
269 Instruction *I = dyn_cast<Instruction>(Val: U.getUser());
270
271 // TODO: Investigate non-instruction uses.
272 if (!I)
273 return CaptureComponents::All;
274
275 switch (I->getOpcode()) {
276 case Instruction::Call:
277 case Instruction::Invoke: {
278 auto *Call = cast<CallBase>(Val: I);
279 // The pointer is not captured if returned pointer is not captured.
280 // NOTE: CaptureTracking users should not assume that only functions
281 // marked with nocapture do not capture. This logic needs to stay in
282 // sync with isEscapeSource().
283 if (isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(
284 Call, /*MustPreserveOffset=*/false))
285 return UseCaptureInfo::passthrough();
286
287 // Calling a function pointer does not in itself cause the pointer to
288 // be captured. This is a subtle point considering that (for example)
289 // the callee might return its own address. It is analogous to saying
290 // that loading a value from a pointer does not cause the pointer to be
291 // captured, even though the loaded value might be the pointer itself
292 // (think of self-referential objects).
293 if (Call->isCallee(U: &U))
294 return CaptureComponents::None;
295
296 // Volatile operations make the address observable.
297 // TODO: This should probably get sunk into CallBase::getCaptureInfo().
298 CaptureComponents VolatileCC = CaptureComponents::None;
299 if (auto *MI = dyn_cast<MemIntrinsic>(Val: Call))
300 if (MI->isVolatile())
301 VolatileCC |= CaptureComponents::Address;
302
303 assert(Call->isDataOperand(&U) && "Non-callee must be data operand");
304 CaptureInfo CI = Call->getCaptureInfo(OpNo: Call->getDataOperandNo(U: &U));
305
306 // If the call is readonly and doesn't return a value, only the address
307 // may be captured.
308 CaptureComponents Mask = CaptureComponents::All;
309 if (Call->onlyReadsMemory() && Call->getType()->isVoidTy())
310 Mask = CaptureComponents::Address;
311
312 return UseCaptureInfo((CI.getOtherComponents() & Mask) | VolatileCC,
313 CI.getRetComponents());
314 }
315 case Instruction::Load:
316 // Volatile loads make the address observable.
317 if (cast<LoadInst>(Val: I)->isVolatile())
318 return CaptureComponents::Address;
319 return CaptureComponents::None;
320 case Instruction::VAArg:
321 // "va-arg" from a pointer does not cause it to be captured.
322 return CaptureComponents::None;
323 case Instruction::Store:
324 // Stored the pointer - conservatively assume it may be captured.
325 if (U.getOperandNo() == 0)
326 return MDNode::toCaptureComponents(
327 MD: I->getMetadata(KindID: LLVMContext::MD_captures));
328
329 // Volatile stores make the address observable.
330 if (cast<StoreInst>(Val: I)->isVolatile())
331 return CaptureComponents::Address;
332 return CaptureComponents::None;
333 case Instruction::AtomicRMW: {
334 // atomicrmw conceptually includes both a load and store from
335 // the same location.
336 // As with a store, the location being accessed is not captured,
337 // but the value being stored is.
338 auto *ARMWI = cast<AtomicRMWInst>(Val: I);
339 if (U.getOperandNo() == 1)
340 return CaptureComponents::All;
341 // Volatile stores make the address observable.
342 if (ARMWI->isVolatile())
343 return CaptureComponents::Address;
344 return CaptureComponents::None;
345 }
346 case Instruction::AtomicCmpXchg: {
347 // cmpxchg conceptually includes both a load and store from
348 // the same location.
349 // As with a store, the location being accessed is not captured,
350 // but the value being stored is.
351 auto *ACXI = cast<AtomicCmpXchgInst>(Val: I);
352 if (U.getOperandNo() == 1 || U.getOperandNo() == 2)
353 return CaptureComponents::All;
354 // Volatile stores make the address observable.
355 if (ACXI->isVolatile())
356 return CaptureComponents::Address;
357 return CaptureComponents::None;
358 }
359 case Instruction::GetElementPtr:
360 // AA does not support pointers of vectors, so GEP vector splats need to
361 // be considered as captures.
362 if (I->getType()->isVectorTy())
363 return CaptureComponents::All;
364 return UseCaptureInfo::passthrough();
365 case Instruction::BitCast:
366 case Instruction::PHI:
367 case Instruction::Select:
368 case Instruction::AddrSpaceCast:
369 // The original value is not captured via this if the new value isn't.
370 return UseCaptureInfo::passthrough();
371 case Instruction::PtrToAddr:
372 // We treat ptrtoaddr as a location-independent capture of the address even
373 // if it is ultimately not used. Continuing recursive analysis after
374 // ptrtoaddr would be possible, but we'd need logic to do that correctly,
375 // which is not the same as the current pointer following logic.
376 return CaptureComponents::Address;
377 case Instruction::ICmp: {
378 unsigned Idx = U.getOperandNo();
379 unsigned OtherIdx = 1 - Idx;
380 // Check whether this is a comparison of the base pointer against
381 // null.
382 if (isa<ConstantPointerNull>(Val: I->getOperand(i: OtherIdx)) &&
383 cast<ICmpInst>(Val: I)->isEquality() && U.get() == Base)
384 return CaptureComponents::AddressIsNull;
385
386 // Otherwise, be conservative. There are crazy ways to capture pointers
387 // using comparisons. However, only the address is captured, not the
388 // provenance.
389 return CaptureComponents::Address;
390 }
391 default:
392 // Something else - be conservative and say it is captured.
393 return CaptureComponents::All;
394 }
395}
396
397void llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker,
398 unsigned MaxUsesToExplore) {
399 assert(V->getType()->isPointerTy() && "Capture is for pointers only!");
400 if (MaxUsesToExplore == 0)
401 MaxUsesToExplore = DefaultMaxUsesToExplore;
402
403 SmallVector<const Use *, 20> Worklist;
404 Worklist.reserve(N: getDefaultMaxUsesToExploreForCaptureTracking());
405 SmallPtrSet<const Use *, 20> Visited;
406
407 auto AddUses = [&](const Value *V) {
408 for (const Use &U : V->uses()) {
409 // If there are lots of uses, conservatively say that the value
410 // is captured to avoid taking too much compile time.
411 if (Visited.size() >= MaxUsesToExplore) {
412 Tracker->tooManyUses();
413 return false;
414 }
415 if (!Visited.insert(Ptr: &U).second)
416 continue;
417 if (!Tracker->shouldExplore(U: &U))
418 continue;
419 Worklist.push_back(Elt: &U);
420 }
421 return true;
422 };
423 if (!AddUses(V))
424 return;
425
426 while (!Worklist.empty()) {
427 const Use *U = Worklist.pop_back_val();
428 UseCaptureInfo CI = DetermineUseCaptureKind(U: *U, Base: V);
429 if (capturesAnything(CC: CI.UseCC)) {
430 switch (Tracker->captured(U, CI)) {
431 case CaptureTracker::Stop:
432 return;
433 case CaptureTracker::ContinueIgnoringReturn:
434 continue;
435 case CaptureTracker::Continue:
436 // Fall through to passthrough handling, but only if ResultCC contains
437 // additional components that UseCC does not. We assume that a
438 // capture at this point will be strictly more constraining than a
439 // later capture from following the return value.
440 if (capturesNothing(CC: CI.ResultCC & ~CI.UseCC))
441 continue;
442 break;
443 }
444 }
445 // TODO(captures): We could keep track of ResultCC for the users.
446 if (capturesAnything(CC: CI.ResultCC) && !AddUses(U->getUser()))
447 return;
448 }
449
450 // All uses examined.
451}
452