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" 23ec3bb4b660fc2f8353c510ebfc15277bcf28df8bJakub Staszak#include "llvm/IR/Constants.h" 24ec3bb4b660fc2f8353c510ebfc15277bcf28df8bJakub Staszak#include "llvm/IR/Instructions.h" 25ec3bb4b660fc2f8353c510ebfc15277bcf28df8bJakub Staszak#include "llvm/Support/CallSite.h" 26ec3bb4b660fc2f8353c510ebfc15277bcf28df8bJakub Staszak 278556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sandsusing namespace llvm; 288556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands 296935b78e6f3b7dca7786041c56c9a795d2247659Nick LewyckyCaptureTracker::~CaptureTracker() {} 306935b78e6f3b7dca7786041c56c9a795d2247659Nick Lewycky 31c92b8aa79f4a2cd16f7b674189e425c2c367e886Nick Lewyckybool CaptureTracker::shouldExplore(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 3888990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky void tooManyUses() { Captured = true; } 3988990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky 40b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky bool captured(Use *U) { 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!"); 847912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky SmallVector<Use*, Threshold> Worklist; 857912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky SmallSet<Use*, Threshold> Visited; 867912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky int Count = 0; 877912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 887912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); 897912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky UI != UE; ++UI) { 907912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // If there are lots of uses, conservatively say that the value 917912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // is captured to avoid taking too much compile time. 927912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (Count++ >= Threshold) 937912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky return Tracker->tooManyUses(); 947912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 957912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky Use *U = &UI.getUse(); 967912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (!Tracker->shouldExplore(U)) continue; 977912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky Visited.insert(U); 987912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky Worklist.push_back(U); 997912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky } 1007912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 1017912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky while (!Worklist.empty()) { 1027912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky Use *U = Worklist.pop_back_val(); 1037912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky Instruction *I = cast<Instruction>(U->getUser()); 1047912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky V = U->get(); 1057912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 1067912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky switch (I->getOpcode()) { 1077912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::Call: 1087912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::Invoke: { 1097912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky CallSite CS(I); 1107912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Not captured if the callee is readonly, doesn't return a copy through 1117912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // its return value and doesn't unwind (a readonly function can leak bits 1127912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // by throwing an exception or not depending on the input value). 1137912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy()) 1147912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1157912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 1167912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Not captured if only passed via 'nocapture' arguments. Note that 1177912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // calling a function pointer does not in itself cause the pointer to 1187912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // be captured. This is a subtle point considering that (for example) 1197912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // the callee might return its own address. It is analogous to saying 1207912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // that loading a value from a pointer does not cause the pointer to be 1217912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // captured, even though the loaded value might be the pointer itself 1227912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // (think of self-referential objects). 1237912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); 1247912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky for (CallSite::arg_iterator A = B; A != E; ++A) 1257912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (A->get() == V && !CS.doesNotCapture(A - B)) 1267912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // The parameter is not marked 'nocapture' - captured. 127b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (Tracker->captured(U)) 1287912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky return; 1297912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1307912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky } 1317912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::Load: 1327912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Loading from a pointer does not cause it to be captured. 1337912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1347912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::VAArg: 1357912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // "va-arg" from a pointer does not cause it to be captured. 1367912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1377912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::Store: 1387912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (V == I->getOperand(0)) 1397912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Stored the pointer - conservatively assume it may be captured. 140b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (Tracker->captured(U)) 1417912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky return; 1427912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Storing to the pointee does not cause the pointer to be captured. 1437912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1447912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::BitCast: 1457912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::GetElementPtr: 1467912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::PHI: 1477912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::Select: 1487912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // The original value is not captured via this if the new value isn't. 1497912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); 1507912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky UI != UE; ++UI) { 1517912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky Use *U = &UI.getUse(); 1527912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (Visited.insert(U)) 1537912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (Tracker->shouldExplore(U)) 1547912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky Worklist.push_back(U); 1557912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky } 1567912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1577912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky case Instruction::ICmp: 1587912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Don't count comparisons of a no-alias return value against null as 1597912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // captures. This allows us to ignore comparisons of malloc results 1607912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // with null, for example. 1617912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (isNoAliasCall(V->stripPointerCasts())) 1627912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (ConstantPointerNull *CPN = 1637912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky dyn_cast<ConstantPointerNull>(I->getOperand(1))) 1647912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky if (CPN->getType()->getAddressSpace() == 0) 1657912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1667912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Otherwise, be conservative. There are crazy ways to capture pointers 1677912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // using comparisons. 168b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (Tracker->captured(U)) 1697912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky return; 1707912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1717912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky default: 1727912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // Something else - be conservative and say it is captured. 173b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (Tracker->captured(U)) 1747912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky return; 1757912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky break; 1767912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky } 1777912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky } 1787912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky 1797912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky // All uses examined. 1807912ef97ffde3ab3334143ddfb4cafdf04e2ebfcNick Lewycky} 181