CaptureTracking.h revision 173862e5468fbcf4b022b9088d2c81b25c2d60c5
1//===----- llvm/Analysis/CaptureTracking.h - Pointer capture ----*- C++ -*-===// 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// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_ANALYSIS_CAPTURETRACKING_H 15#define LLVM_ANALYSIS_CAPTURETRACKING_H 16 17#include "llvm/Constants.h" 18#include "llvm/Instructions.h" 19#include "llvm/Analysis/AliasAnalysis.h" 20#include "llvm/ADT/SmallSet.h" 21#include "llvm/ADT/SmallVector.h" 22#include "llvm/Support/CallSite.h" 23 24namespace llvm { 25 /// PointerMayBeCaptured - Return true if this pointer value may be captured 26 /// by the enclosing function (which is required to exist). This routine can 27 /// be expensive, so consider caching the results. The boolean ReturnCaptures 28 /// specifies whether returning the value (or part of it) from the function 29 /// counts as capturing it or not. The boolean StoreCaptures specified 30 /// whether storing the value (or part of it) into memory anywhere 31 /// automatically counts as capturing it or not. 32 bool PointerMayBeCaptured(const Value *V, 33 bool ReturnCaptures, 34 bool StoreCaptures); 35 36 /// PointerMayBeCaptured - Visit the value and the values derived from it and 37 /// find values which appear to be capturing the pointer value. This feeds 38 /// results into and is controlled by the templated CaptureTracker object: 39 /// 40 /// struct YourCaptureTracker { 41 /// /// tooManyUses - The depth of traversal has breached a limit. 42 /// /// The tracker should conservatively assume that the value is captured. 43 /// void tooManyUses(); 44 /// 45 /// /// shouldExplore - This is the use of a value derived from the pointer. 46 /// /// Return false to prune the search (ie., assume that none of its users 47 /// /// could possibly capture) return false. To search it, return true. 48 /// /// 49 /// /// Also, U->getUser() is guaranteed to be an Instruction. 50 /// bool shouldExplore(Use *U); 51 /// 52 /// /// captured - The instruction I captured the pointer. Return true to 53 /// /// stop the traversal or false to continue looking for more capturing 54 /// /// instructions. 55 /// bool captured(Instruction *I); 56 /// 57 /// /// Provide your own getters for the state. 58 /// }; 59 template<typename CaptureTracker> 60 void PointerMayBeCaptured(const Value *V, CaptureTracker &Tracker); 61} // end namespace llvm 62 63template<typename CaptureTracker> 64void llvm::PointerMayBeCaptured(const llvm::Value *V, CaptureTracker &Tracker) { 65 assert(V->getType()->isPointerTy() && "Capture is for pointers only!"); 66 SmallVector<Use*, 20> Worklist; 67 SmallSet<Use*, 20> Visited; 68 int Count = 0; 69 70 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); 71 UI != UE; ++UI) { 72 // If there are lots of uses, conservatively say that the value 73 // is captured to avoid taking too much compile time. 74 if (Count++ >= 20) 75 return Tracker.tooManyUses(); 76 77 Use *U = &UI.getUse(); 78 if (!Tracker.shouldExplore(U)) continue; 79 Visited.insert(U); 80 Worklist.push_back(U); 81 } 82 83 while (!Worklist.empty()) { 84 Use *U = Worklist.pop_back_val(); 85 Instruction *I = cast<Instruction>(U->getUser()); 86 V = U->get(); 87 88 switch (I->getOpcode()) { 89 case Instruction::Call: 90 case Instruction::Invoke: { 91 CallSite CS(I); 92 // Not captured if the callee is readonly, doesn't return a copy through 93 // its return value and doesn't unwind (a readonly function can leak bits 94 // by throwing an exception or not depending on the input value). 95 if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy()) 96 break; 97 98 // Not captured if only passed via 'nocapture' arguments. Note that 99 // calling a function pointer does not in itself cause the pointer to 100 // be captured. This is a subtle point considering that (for example) 101 // the callee might return its own address. It is analogous to saying 102 // that loading a value from a pointer does not cause the pointer to be 103 // captured, even though the loaded value might be the pointer itself 104 // (think of self-referential objects). 105 CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); 106 for (CallSite::arg_iterator A = B; A != E; ++A) 107 if (A->get() == V && !CS.doesNotCapture(A - B)) 108 // The parameter is not marked 'nocapture' - captured. 109 if (Tracker.captured(I)) 110 return; 111 break; 112 } 113 case Instruction::Load: 114 // Loading from a pointer does not cause it to be captured. 115 break; 116 case Instruction::VAArg: 117 // "va-arg" from a pointer does not cause it to be captured. 118 break; 119 case Instruction::Store: 120 if (V == I->getOperand(0)) 121 // Stored the pointer - conservatively assume it may be captured. 122 if (Tracker.captured(I)) 123 return; 124 // Storing to the pointee does not cause the pointer to be captured. 125 break; 126 case Instruction::BitCast: 127 case Instruction::GetElementPtr: 128 case Instruction::PHI: 129 case Instruction::Select: 130 // The original value is not captured via this if the new value isn't. 131 for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); 132 UI != UE; ++UI) { 133 Use *U = &UI.getUse(); 134 if (Visited.insert(U)) 135 if (Tracker.shouldExplore(U)) 136 Worklist.push_back(U); 137 } 138 break; 139 case Instruction::ICmp: 140 // Don't count comparisons of a no-alias return value against null as 141 // captures. This allows us to ignore comparisons of malloc results 142 // with null, for example. 143 if (isNoAliasCall(V->stripPointerCasts())) 144 if (ConstantPointerNull *CPN = 145 dyn_cast<ConstantPointerNull>(I->getOperand(1))) 146 if (CPN->getType()->getAddressSpace() == 0) 147 break; 148 // Otherwise, be conservative. There are crazy ways to capture pointers 149 // using comparisons. 150 if (Tracker.captured(I)) 151 return; 152 break; 153 default: 154 // Something else - be conservative and say it is captured. 155 if (Tracker.captured(I)) 156 return; 157 break; 158 } 159 } 160 161 // All uses examined. 162} 163 164#endif 165