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