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