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/CFG.h" 23 #include "llvm/Analysis/CaptureTracking.h" 24 #include "llvm/IR/CallSite.h" 25 #include "llvm/IR/Constants.h" 26 #include "llvm/IR/Dominators.h" 27 #include "llvm/IR/Instructions.h" 28 29 using namespace llvm; 30 31 CaptureTracker::~CaptureTracker() {} 32 33 bool CaptureTracker::shouldExplore(const Use *U) { return true; } 34 35 namespace { 36 struct SimpleCaptureTracker : public CaptureTracker { 37 explicit SimpleCaptureTracker(bool ReturnCaptures) 38 : ReturnCaptures(ReturnCaptures), Captured(false) {} 39 40 void tooManyUses() override { Captured = true; } 41 42 bool captured(const Use *U) override { 43 if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures) 44 return false; 45 46 Captured = true; 47 return true; 48 } 49 50 bool ReturnCaptures; 51 52 bool Captured; 53 }; 54 55 /// Only find pointer captures which happen before the given instruction. Uses 56 /// the dominator tree to determine whether one instruction is before another. 57 /// Only support the case where the Value is defined in the same basic block 58 /// as the given instruction and the use. 59 struct CapturesBefore : public CaptureTracker { 60 CapturesBefore(bool ReturnCaptures, const Instruction *I, DominatorTree *DT, 61 bool IncludeI) 62 : BeforeHere(I), DT(DT), ReturnCaptures(ReturnCaptures), 63 IncludeI(IncludeI), Captured(false) {} 64 65 void tooManyUses() override { Captured = true; } 66 67 bool shouldExplore(const Use *U) override { 68 Instruction *I = cast<Instruction>(U->getUser()); 69 if (BeforeHere == I && !IncludeI) 70 return false; 71 72 BasicBlock *BB = I->getParent(); 73 // We explore this usage only if the usage can reach "BeforeHere". 74 // If use is not reachable from entry, there is no need to explore. 75 if (BeforeHere != I && !DT->isReachableFromEntry(BB)) 76 return false; 77 // If the value is defined in the same basic block as use and BeforeHere, 78 // there is no need to explore the use if BeforeHere dominates use. 79 // Check whether there is a path from I to BeforeHere. 80 if (BeforeHere != I && DT->dominates(BeforeHere, I) && 81 !isPotentiallyReachable(I, BeforeHere, DT)) 82 return false; 83 return true; 84 } 85 86 bool captured(const Use *U) override { 87 if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures) 88 return false; 89 90 Instruction *I = cast<Instruction>(U->getUser()); 91 if (BeforeHere == I && !IncludeI) 92 return false; 93 94 BasicBlock *BB = I->getParent(); 95 // Same logic as in shouldExplore. 96 if (BeforeHere != I && !DT->isReachableFromEntry(BB)) 97 return false; 98 if (BeforeHere != I && DT->dominates(BeforeHere, I) && 99 !isPotentiallyReachable(I, BeforeHere, DT)) 100 return false; 101 Captured = true; 102 return true; 103 } 104 105 const Instruction *BeforeHere; 106 DominatorTree *DT; 107 108 bool ReturnCaptures; 109 bool IncludeI; 110 111 bool Captured; 112 }; 113 } 114 115 /// PointerMayBeCaptured - Return true if this pointer value may be captured 116 /// by the enclosing function (which is required to exist). This routine can 117 /// be expensive, so consider caching the results. The boolean ReturnCaptures 118 /// specifies whether returning the value (or part of it) from the function 119 /// counts as capturing it or not. The boolean StoreCaptures specified whether 120 /// storing the value (or part of it) into memory anywhere automatically 121 /// counts as capturing it or not. 122 bool llvm::PointerMayBeCaptured(const Value *V, 123 bool ReturnCaptures, bool StoreCaptures) { 124 assert(!isa<GlobalValue>(V) && 125 "It doesn't make sense to ask whether a global is captured."); 126 127 // TODO: If StoreCaptures is not true, we could do Fancy analysis 128 // to determine whether this store is not actually an escape point. 129 // In that case, BasicAliasAnalysis should be updated as well to 130 // take advantage of this. 131 (void)StoreCaptures; 132 133 SimpleCaptureTracker SCT(ReturnCaptures); 134 PointerMayBeCaptured(V, &SCT); 135 return SCT.Captured; 136 } 137 138 /// PointerMayBeCapturedBefore - Return true if this pointer value may be 139 /// captured by the enclosing function (which is required to exist). If a 140 /// DominatorTree is provided, only captures which happen before the given 141 /// instruction are considered. This routine can be expensive, so consider 142 /// caching the results. The boolean ReturnCaptures specifies whether 143 /// returning the value (or part of it) from the function counts as capturing 144 /// it or not. The boolean StoreCaptures specified whether storing the value 145 /// (or part of it) into memory anywhere automatically counts as capturing it 146 /// or not. 147 bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, 148 bool StoreCaptures, const Instruction *I, 149 DominatorTree *DT, bool IncludeI) { 150 assert(!isa<GlobalValue>(V) && 151 "It doesn't make sense to ask whether a global is captured."); 152 153 if (!DT) 154 return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures); 155 156 // TODO: See comment in PointerMayBeCaptured regarding what could be done 157 // with StoreCaptures. 158 159 CapturesBefore CB(ReturnCaptures, I, DT, IncludeI); 160 PointerMayBeCaptured(V, &CB); 161 return CB.Captured; 162 } 163 164 /// TODO: Write a new FunctionPass AliasAnalysis so that it can keep 165 /// a cache. Then we can move the code from BasicAliasAnalysis into 166 /// that path, and remove this threshold. 167 static int const Threshold = 20; 168 169 void llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker) { 170 assert(V->getType()->isPointerTy() && "Capture is for pointers only!"); 171 SmallVector<const Use *, Threshold> Worklist; 172 SmallSet<const Use *, Threshold> Visited; 173 int Count = 0; 174 175 for (const Use &U : V->uses()) { 176 // If there are lots of uses, conservatively say that the value 177 // is captured to avoid taking too much compile time. 178 if (Count++ >= Threshold) 179 return Tracker->tooManyUses(); 180 181 if (!Tracker->shouldExplore(&U)) continue; 182 Visited.insert(&U); 183 Worklist.push_back(&U); 184 } 185 186 while (!Worklist.empty()) { 187 const Use *U = Worklist.pop_back_val(); 188 Instruction *I = cast<Instruction>(U->getUser()); 189 V = U->get(); 190 191 switch (I->getOpcode()) { 192 case Instruction::Call: 193 case Instruction::Invoke: { 194 CallSite CS(I); 195 // Not captured if the callee is readonly, doesn't return a copy through 196 // its return value and doesn't unwind (a readonly function can leak bits 197 // by throwing an exception or not depending on the input value). 198 if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy()) 199 break; 200 201 // Not captured if only passed via 'nocapture' arguments. Note that 202 // calling a function pointer does not in itself cause the pointer to 203 // be captured. This is a subtle point considering that (for example) 204 // the callee might return its own address. It is analogous to saying 205 // that loading a value from a pointer does not cause the pointer to be 206 // captured, even though the loaded value might be the pointer itself 207 // (think of self-referential objects). 208 CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); 209 for (CallSite::arg_iterator A = B; A != E; ++A) 210 if (A->get() == V && !CS.doesNotCapture(A - B)) 211 // The parameter is not marked 'nocapture' - captured. 212 if (Tracker->captured(U)) 213 return; 214 break; 215 } 216 case Instruction::Load: 217 // Loading from a pointer does not cause it to be captured. 218 break; 219 case Instruction::VAArg: 220 // "va-arg" from a pointer does not cause it to be captured. 221 break; 222 case Instruction::Store: 223 if (V == I->getOperand(0)) 224 // Stored the pointer - conservatively assume it may be captured. 225 if (Tracker->captured(U)) 226 return; 227 // Storing to the pointee does not cause the pointer to be captured. 228 break; 229 case Instruction::BitCast: 230 case Instruction::GetElementPtr: 231 case Instruction::PHI: 232 case Instruction::Select: 233 case Instruction::AddrSpaceCast: 234 // The original value is not captured via this if the new value isn't. 235 Count = 0; 236 for (Use &UU : I->uses()) { 237 // If there are lots of uses, conservatively say that the value 238 // is captured to avoid taking too much compile time. 239 if (Count++ >= Threshold) 240 return Tracker->tooManyUses(); 241 242 if (Visited.insert(&UU).second) 243 if (Tracker->shouldExplore(&UU)) 244 Worklist.push_back(&UU); 245 } 246 break; 247 case Instruction::ICmp: 248 // Don't count comparisons of a no-alias return value against null as 249 // captures. This allows us to ignore comparisons of malloc results 250 // with null, for example. 251 if (ConstantPointerNull *CPN = 252 dyn_cast<ConstantPointerNull>(I->getOperand(1))) 253 if (CPN->getType()->getAddressSpace() == 0) 254 if (isNoAliasCall(V->stripPointerCasts())) 255 break; 256 // Otherwise, be conservative. There are crazy ways to capture pointers 257 // using comparisons. 258 if (Tracker->captured(U)) 259 return; 260 break; 261 default: 262 // Something else - be conservative and say it is captured. 263 if (Tracker->captured(U)) 264 return; 265 break; 266 } 267 } 268 269 // All uses examined. 270 } 271
