18556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands//===--- CaptureTracking.cpp - Determine whether a pointer is captured ----===// 28556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// 38556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// The LLVM Compiler Infrastructure 48556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// 58556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// This file is distributed under the University of Illinois Open Source 68556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// License. See LICENSE.TXT for details. 78556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// 88556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands//===----------------------------------------------------------------------===// 98556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// 108556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// This file contains routines that help determine which pointers are captured. 118556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// A pointer value is captured if the function makes a copy of any part of the 128556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// pointer that outlives the call. Not being captured means, more or less, that 138556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// the pointer is only dereferenced and not stored in a global. Returning part 148556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// of the pointer as the function return value may or may not count as capturing 158556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// the pointer, depending on the context. 168556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands// 178556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands//===----------------------------------------------------------------------===// 188556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands 19bda43e95a03c19868106e8111d7a5bf1c924ec63Jakub Staszak#include "llvm/ADT/SmallSet.h" 20bda43e95a03c19868106e8111d7a5bf1c924ec63Jakub Staszak#include "llvm/ADT/SmallVector.h" 21ec3bb4b660fc2f8353c510ebfc15277bcf28df8bJakub Staszak#include "llvm/Analysis/AliasAnalysis.h" 228556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands#include "llvm/Analysis/CaptureTracking.h" 2336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CallSite.h" 24ec3bb4b660fc2f8353c510ebfc15277bcf28df8bJakub Staszak#include "llvm/IR/Constants.h" 25ec3bb4b660fc2f8353c510ebfc15277bcf28df8bJakub Staszak#include "llvm/IR/Instructions.h" 26ec3bb4b660fc2f8353c510ebfc15277bcf28df8bJakub Staszak 278556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sandsusing namespace llvm; 288556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands 296935b78e6f3b7dca7786041c56c9a795d2247659Nick LewyckyCaptureTracker::~CaptureTracker() {} 306935b78e6f3b7dca7786041c56c9a795d2247659Nick Lewycky 3136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool CaptureTracker::shouldExplore(const Use *U) { return true; } 32c92b8aa79f4a2cd16f7b674189e425c2c367e886Nick Lewycky 3388990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewyckynamespace { 347912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky struct SimpleCaptureTracker : public CaptureTracker { 3588990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky explicit SimpleCaptureTracker(bool ReturnCaptures) 3688990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky : ReturnCaptures(ReturnCaptures), Captured(false) {} 3788990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void tooManyUses() override { Captured = true; } 3988990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool captured(const Use *U) override { 41b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures) 42620ee81fa0bef312d711688c86b73aa16f088509Chad Rosier return false; 4388990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky 4488990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky Captured = true; 4588990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky return true; 4688990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky } 4788990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky 4888990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky bool ReturnCaptures; 4988990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky 5088990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky bool Captured; 5188990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky }; 5288990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky} 538456d60becd2b502e3d6ebf124ea324ec5d1c108Dan Gohman 548556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands/// PointerMayBeCaptured - Return true if this pointer value may be captured 558556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands/// by the enclosing function (which is required to exist). This routine can 568556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands/// be expensive, so consider caching the results. The boolean ReturnCaptures 578556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands/// specifies whether returning the value (or part of it) from the function 58f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman/// counts as capturing it or not. The boolean StoreCaptures specified whether 59f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman/// storing the value (or part of it) into memory anywhere automatically 608556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands/// counts as capturing it or not. 61f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohmanbool llvm::PointerMayBeCaptured(const Value *V, 62f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman bool ReturnCaptures, bool StoreCaptures) { 639f47fb66370e5513bb9f737923e8cb476088acecNick Lewycky assert(!isa<GlobalValue>(V) && 649f47fb66370e5513bb9f737923e8cb476088acecNick Lewycky "It doesn't make sense to ask whether a global is captured."); 659f47fb66370e5513bb9f737923e8cb476088acecNick Lewycky 6688990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky // TODO: If StoreCaptures is not true, we could do Fancy analysis 6788990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky // to determine whether this store is not actually an escape point. 6888990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky // In that case, BasicAliasAnalysis should be updated as well to 6988990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky // take advantage of this. 7088990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky (void)StoreCaptures; 7188990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky 7288990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky SimpleCaptureTracker SCT(ReturnCaptures); 737912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky PointerMayBeCaptured(V, &SCT); 7488990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky return SCT.Captured; 758556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands} 767912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 777912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky/// TODO: Write a new FunctionPass AliasAnalysis so that it can keep 787912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky/// a cache. Then we can move the code from BasicAliasAnalysis into 797912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky/// that path, and remove this threshold. 807912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewyckystatic int const Threshold = 20; 817912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 827912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewyckyvoid llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker) { 837912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky assert(V->getType()->isPointerTy() && "Capture is for pointers only!"); 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<const Use *, Threshold> Worklist; 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallSet<const Use *, Threshold> Visited; 867912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky int Count = 0; 877912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (const Use &U : V->uses()) { 897912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // If there are lots of uses, conservatively say that the value 907912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // is captured to avoid taking too much compile time. 917912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (Count++ >= Threshold) 927912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky return Tracker->tooManyUses(); 937912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!Tracker->shouldExplore(&U)) continue; 9536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Visited.insert(&U); 9636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Worklist.push_back(&U); 977912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky } 987912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 997912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky while (!Worklist.empty()) { 10036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const Use *U = Worklist.pop_back_val(); 1017912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky Instruction *I = cast<Instruction>(U->getUser()); 1027912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky V = U->get(); 1037912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 1047912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky switch (I->getOpcode()) { 1057912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::Call: 1067912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::Invoke: { 1077912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky CallSite CS(I); 1087912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Not captured if the callee is readonly, doesn't return a copy through 1097912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // its return value and doesn't unwind (a readonly function can leak bits 1107912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // by throwing an exception or not depending on the input value). 1117912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy()) 1127912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1137912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 1147912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Not captured if only passed via 'nocapture' arguments. Note that 1157912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // calling a function pointer does not in itself cause the pointer to 1167912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // be captured. This is a subtle point considering that (for example) 1177912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // the callee might return its own address. It is analogous to saying 1187912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // that loading a value from a pointer does not cause the pointer to be 1197912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // captured, even though the loaded value might be the pointer itself 1207912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // (think of self-referential objects). 1217912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); 1227912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky for (CallSite::arg_iterator A = B; A != E; ++A) 1237912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (A->get() == V && !CS.doesNotCapture(A - B)) 1247912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // The parameter is not marked 'nocapture' - captured. 125b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (Tracker->captured(U)) 1267912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky return; 1277912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1287912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky } 1297912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::Load: 1307912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Loading from a pointer does not cause it to be captured. 1317912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1327912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::VAArg: 1337912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // "va-arg" from a pointer does not cause it to be captured. 1347912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1357912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::Store: 1367912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (V == I->getOperand(0)) 1377912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Stored the pointer - conservatively assume it may be captured. 138b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (Tracker->captured(U)) 1397912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky return; 1407912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Storing to the pointee does not cause the pointer to be captured. 1417912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1427912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::BitCast: 1437912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::GetElementPtr: 1447912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::PHI: 1457912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::Select: 14636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case Instruction::AddrSpaceCast: 1477912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // The original value is not captured via this if the new value isn't. 1484d63c8daec1759e60f85a49b7a91f88edf0c0a4dBenjamin Kramer Count = 0; 14936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Use &UU : I->uses()) { 1504d63c8daec1759e60f85a49b7a91f88edf0c0a4dBenjamin Kramer // If there are lots of uses, conservatively say that the value 1514d63c8daec1759e60f85a49b7a91f88edf0c0a4dBenjamin Kramer // is captured to avoid taking too much compile time. 1524d63c8daec1759e60f85a49b7a91f88edf0c0a4dBenjamin Kramer if (Count++ >= Threshold) 1534d63c8daec1759e60f85a49b7a91f88edf0c0a4dBenjamin Kramer return Tracker->tooManyUses(); 1544d63c8daec1759e60f85a49b7a91f88edf0c0a4dBenjamin Kramer 15536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Visited.insert(&UU)) 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Tracker->shouldExplore(&UU)) 15736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Worklist.push_back(&UU); 1587912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky } 1597912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1607912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::ICmp: 1617912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Don't count comparisons of a no-alias return value against null as 1627912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // captures. This allows us to ignore comparisons of malloc results 1637912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // with null, for example. 164dc89737bcdbb8f69d8ae7578bdfa904cabcfc5edNick Lewycky if (ConstantPointerNull *CPN = 165dc89737bcdbb8f69d8ae7578bdfa904cabcfc5edNick Lewycky dyn_cast<ConstantPointerNull>(I->getOperand(1))) 166dc89737bcdbb8f69d8ae7578bdfa904cabcfc5edNick Lewycky if (CPN->getType()->getAddressSpace() == 0) 167dc89737bcdbb8f69d8ae7578bdfa904cabcfc5edNick Lewycky if (isNoAliasCall(V->stripPointerCasts())) 1687912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1697912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Otherwise, be conservative. There are crazy ways to capture pointers 1707912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // using comparisons. 171b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (Tracker->captured(U)) 1727912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky return; 1737912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1747912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky default: 1757912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Something else - be conservative and say it is captured. 176b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (Tracker->captured(U)) 1777912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky return; 1787912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1797912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky } 1807912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky } 1817912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 1827912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // All uses examined. 1837912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky} 184