CaptureTracking.cpp revision 8556d2a7f155c7edfaf454a3acda8ce28863c5e4
1//===--- CaptureTracking.cpp - Determine whether a pointer is captured ----===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file contains routines that help determine which pointers are captured. 11// A pointer value is captured if the function makes a copy of any part of the 12// pointer that outlives the call. Not being captured means, more or less, that 13// the pointer is only dereferenced and not stored in a global. Returning part 14// of the pointer as the function return value may or may not count as capturing 15// the pointer, depending on the context. 16// 17//===----------------------------------------------------------------------===// 18 19#include "llvm/Analysis/CaptureTracking.h" 20#include "llvm/Instructions.h" 21#include "llvm/Value.h" 22#include "llvm/ADT/SmallSet.h" 23#include "llvm/ADT/SmallVector.h" 24#include "llvm/Support/CallSite.h" 25using namespace llvm; 26 27/// PointerMayBeCaptured - Return true if this pointer value may be captured 28/// by the enclosing function (which is required to exist). This routine can 29/// be expensive, so consider caching the results. The boolean ReturnCaptures 30/// specifies whether returning the value (or part of it) from the function 31/// counts as capturing it or not. 32bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures) { 33 assert(isa<PointerType>(V->getType()) && "Capture is for pointers only!"); 34 SmallVector<Use*, 16> Worklist; 35 SmallSet<Use*, 16> Visited; 36 37 for (Value::use_const_iterator UI = V->use_begin(), UE = V->use_end(); 38 UI != UE; ++UI) { 39 Use *U = &UI.getUse(); 40 Visited.insert(U); 41 Worklist.push_back(U); 42 } 43 44 while (!Worklist.empty()) { 45 Use *U = Worklist.pop_back_val(); 46 Instruction *I = cast<Instruction>(U->getUser()); 47 V = U->get(); 48 49 switch (I->getOpcode()) { 50 case Instruction::Call: 51 case Instruction::Invoke: { 52 CallSite CS = CallSite::get(I); 53 // Not captured if the callee is readonly and doesn't return a copy 54 // through its return value. 55 if (CS.onlyReadsMemory() && I->getType() == Type::VoidTy) 56 break; 57 58 // Not captured if only passed via 'nocapture' arguments. Note that 59 // calling a function pointer does not in itself cause the pointer to 60 // be captured. This is a subtle point considering that (for example) 61 // the callee might return its own address. It is analogous to saying 62 // that loading a value from a pointer does not cause the pointer to be 63 // captured, even though the loaded value might be the pointer itself 64 // (think of self-referential objects). 65 CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); 66 for (CallSite::arg_iterator A = B; A != E; ++A) 67 if (A->get() == V && !CS.paramHasAttr(A - B + 1, Attribute::NoCapture)) 68 // The parameter is not marked 'nocapture' - captured. 69 return true; 70 // Only passed via 'nocapture' arguments, or is the called function - not 71 // captured. 72 break; 73 } 74 case Instruction::Free: 75 // Freeing a pointer does not cause it to be captured. 76 break; 77 case Instruction::Load: 78 // Loading from a pointer does not cause it to be captured. 79 break; 80 case Instruction::Ret: 81 if (ReturnCaptures) 82 return true; 83 break; 84 case Instruction::Store: 85 if (V == I->getOperand(0)) 86 // Stored the pointer - it may be captured. 87 return true; 88 // Storing to the pointee does not cause the pointer to be captured. 89 break; 90 case Instruction::BitCast: 91 case Instruction::GetElementPtr: 92 case Instruction::PHI: 93 case Instruction::Select: 94 // The original value is not captured via this if the new value isn't. 95 for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); 96 UI != UE; ++UI) { 97 Use *U = &UI.getUse(); 98 if (Visited.insert(U)) 99 Worklist.push_back(U); 100 } 101 break; 102 default: 103 // Something else - be conservative and say it is captured. 104 return true; 105 } 106 } 107 108 // All uses examined - not captured. 109 return false; 110} 111