458 lines · cpp
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-exception6//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 the11// pointer that outlives the call. Not being captured means, more or less, that12// the pointer is only dereferenced and not stored in a global. Returning part13// of the pointer as the function return value may or may not count as capturing14// 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 to40/// 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 and43/// use it where possible. The caching version can use much higher limit or44/// 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 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>(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. Uses89/// 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 block91/// 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 avoid122 // 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 to149/// be captured. Here an instruction A is considered earlier than instruction150/// B, if A dominates B. If 2 escapes do not dominate each other, the151/// terminator of the common dominator is chosen. If not all uses cannot be152/// analyzed, the earliest escape is set to the first instruction in the153/// function entry block.154// NOTE: Users have to make sure instructions compared against the earliest155// 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 else176 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} // namespace193 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, &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 213bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures,214 unsigned MaxUsesToExplore) {215 return capturesAnything(216 PointerMayBeCaptured(V, ReturnCaptures, CaptureComponents::All,217 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, &CB, MaxUsesToExplore);234 if (capturesAnything(CB.CC))235 ++NumCapturedBefore;236 else237 ++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(PointerMayBeCapturedBefore(247 V, ReturnCaptures, I, DT, IncludeI, CaptureComponents::All,248 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, &CB, MaxUsesToExplore);260 if (capturesAnything(CB.CC))261 ++NumCapturedBefore;262 else263 ++NumNotCapturedBefore;264 return {CB.EarliestCapture, CB.CC};265}266 267UseCaptureInfo llvm::DetermineUseCaptureKind(const Use &U, const Value *Base) {268 Instruction *I = dyn_cast<Instruction>(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>(I);278 // The pointer is not captured if returned pointer is not captured.279 // NOTE: CaptureTracking users should not assume that only functions280 // marked with nocapture do not capture. This means that places like281 // getUnderlyingObject in ValueTracking or DecomposeGEPExpression282 // in BasicAA also need to know about this property.283 if (isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(Call, true))284 return UseCaptureInfo::passthrough();285 286 // Volatile operations effectively capture the memory location that they287 // load and store to.288 if (auto *MI = dyn_cast<MemIntrinsic>(Call))289 if (MI->isVolatile())290 return CaptureComponents::All;291 292 // Calling a function pointer does not in itself cause the pointer to293 // be captured. This is a subtle point considering that (for example)294 // the callee might return its own address. It is analogous to saying295 // that loading a value from a pointer does not cause the pointer to be296 // captured, even though the loaded value might be the pointer itself297 // (think of self-referential objects).298 if (Call->isCallee(&U))299 return CaptureComponents::None;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 address305 // 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>(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 I->getMetadata(LLVMContext::MD_captures));326 327 // Volatile stores make the address observable.328 if (cast<StoreInst>(I)->isVolatile())329 return CaptureComponents::All;330 return CaptureComponents::None;331 case Instruction::AtomicRMW: {332 // atomicrmw conceptually includes both a load and store from333 // 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())339 return CaptureComponents::All;340 return CaptureComponents::None;341 }342 case Instruction::AtomicCmpXchg: {343 // cmpxchg conceptually includes both a load and store from344 // 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())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 to355 // 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 even367 // if it is ultimately not used. Continuing recursive analysis after368 // 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>(I->getOperand(OtherIdx)) &&375 cast<ICmpInst>(I)->isEquality()) {376 // TODO(captures): Remove these special cases once we make use of377 // captures(address_is_null).378 379 // Don't count comparisons of a no-alias return value against null as380 // captures. This allows us to ignore comparisons of malloc results381 // with null, for example.382 if (U->getType()->getPointerAddressSpace() == 0)383 if (isNoAliasCall(U.get()->stripPointerCasts()))384 return CaptureComponents::None;385 386 // Check whether this is a comparison of the base pointer against387 // null.388 if (U.get() == Base)389 return CaptureComponents::AddressIsNull;390 }391 392 // Otherwise, be conservative. There are crazy ways to capture pointers393 // using comparisons. However, only the address is captured, not the394 // 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(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 value416 // 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();434 UseCaptureInfo CI = DetermineUseCaptureKind(*U, V);435 if (capturesAnything(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 contains443 // additional components that UseCC does not. We assume that a444 // capture at this point will be strictly more constraining than a445 // 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}458