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