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/Constants.h" 21 #include "llvm/Instructions.h" 22 #include "llvm/Value.h" 23 #include "llvm/Analysis/AliasAnalysis.h" 24 #include "llvm/ADT/SmallSet.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/Support/CallSite.h" 27 using namespace llvm; 28 29 /// As its comment mentions, PointerMayBeCaptured can be expensive. 30 /// However, it's not easy for BasicAA to cache the result, because 31 /// it's an ImmutablePass. To work around this, bound queries at a 32 /// fixed number of uses. 33 /// 34 /// TODO: Write a new FunctionPass AliasAnalysis so that it can keep 35 /// a cache. Then we can move the code from BasicAliasAnalysis into 36 /// that path, and remove this threshold. 37 static int const Threshold = 20; 38 39 /// PointerMayBeCaptured - Return true if this pointer value may be captured 40 /// by the enclosing function (which is required to exist). This routine can 41 /// be expensive, so consider caching the results. The boolean ReturnCaptures 42 /// specifies whether returning the value (or part of it) from the function 43 /// counts as capturing it or not. The boolean StoreCaptures specified whether 44 /// storing the value (or part of it) into memory anywhere automatically 45 /// counts as capturing it or not. 46 bool llvm::PointerMayBeCaptured(const Value *V, 47 bool ReturnCaptures, bool StoreCaptures) { 48 assert(V->getType()->isPointerTy() && "Capture is for pointers only!"); 49 SmallVector<Use*, Threshold> Worklist; 50 SmallSet<Use*, Threshold> Visited; 51 int Count = 0; 52 53 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); 54 UI != UE; ++UI) { 55 // If there are lots of uses, conservatively say that the value 56 // is captured to avoid taking too much compile time. 57 if (Count++ >= Threshold) 58 return true; 59 60 Use *U = &UI.getUse(); 61 Visited.insert(U); 62 Worklist.push_back(U); 63 } 64 65 while (!Worklist.empty()) { 66 Use *U = Worklist.pop_back_val(); 67 Instruction *I = cast<Instruction>(U->getUser()); 68 V = U->get(); 69 70 switch (I->getOpcode()) { 71 case Instruction::Call: 72 case Instruction::Invoke: { 73 CallSite CS(I); 74 // Not captured if the callee is readonly, doesn't return a copy through 75 // its return value and doesn't unwind (a readonly function can leak bits 76 // by throwing an exception or not depending on the input value). 77 if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy()) 78 break; 79 80 // Not captured if only passed via 'nocapture' arguments. Note that 81 // calling a function pointer does not in itself cause the pointer to 82 // be captured. This is a subtle point considering that (for example) 83 // the callee might return its own address. It is analogous to saying 84 // that loading a value from a pointer does not cause the pointer to be 85 // captured, even though the loaded value might be the pointer itself 86 // (think of self-referential objects). 87 CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); 88 for (CallSite::arg_iterator A = B; A != E; ++A) 89 if (A->get() == V && !CS.paramHasAttr(A - B + 1, Attribute::NoCapture)) 90 // The parameter is not marked 'nocapture' - captured. 91 return true; 92 // Only passed via 'nocapture' arguments, or is the called function - not 93 // captured. 94 break; 95 } 96 case Instruction::Load: 97 // Loading from a pointer does not cause it to be captured. 98 break; 99 case Instruction::VAArg: 100 // "va-arg" from a pointer does not cause it to be captured. 101 break; 102 case Instruction::Ret: 103 if (ReturnCaptures) 104 return true; 105 break; 106 case Instruction::Store: 107 if (V == I->getOperand(0)) 108 // Stored the pointer - conservatively assume it may be captured. 109 // TODO: If StoreCaptures is not true, we could do Fancy analysis 110 // to determine whether this store is not actually an escape point. 111 // In that case, BasicAliasAnalysis should be updated as well to 112 // take advantage of this. 113 return true; 114 // Storing to the pointee does not cause the pointer to be captured. 115 break; 116 case Instruction::BitCast: 117 case Instruction::GetElementPtr: 118 case Instruction::PHI: 119 case Instruction::Select: 120 // The original value is not captured via this if the new value isn't. 121 for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); 122 UI != UE; ++UI) { 123 Use *U = &UI.getUse(); 124 if (Visited.insert(U)) 125 Worklist.push_back(U); 126 } 127 break; 128 case Instruction::ICmp: 129 // Don't count comparisons of a no-alias return value against null as 130 // captures. This allows us to ignore comparisons of malloc results 131 // with null, for example. 132 if (isNoAliasCall(V->stripPointerCasts())) 133 if (ConstantPointerNull *CPN = 134 dyn_cast<ConstantPointerNull>(I->getOperand(1))) 135 if (CPN->getType()->getAddressSpace() == 0) 136 break; 137 // Otherwise, be conservative. There are crazy ways to capture pointers 138 // using comparisons. 139 return true; 140 default: 141 // Something else - be conservative and say it is captured. 142 return true; 143 } 144 } 145 146 // All uses examined - not captured. 147 return false; 148 } 149
