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