LLVM API Documentation
00001 //===--- CaptureTracking.cpp - Determine whether a pointer is captured ----===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file contains routines that help determine which pointers are captured. 00011 // A pointer value is captured if the function makes a copy of any part of the 00012 // pointer that outlives the call. Not being captured means, more or less, that 00013 // the pointer is only dereferenced and not stored in a global. Returning part 00014 // of the pointer as the function return value may or may not count as capturing 00015 // the pointer, depending on the context. 00016 // 00017 //===----------------------------------------------------------------------===// 00018 00019 #include "llvm/Analysis/CaptureTracking.h" 00020 #include "llvm/Instructions.h" 00021 #include "llvm/Value.h" 00022 #include "llvm/ADT/SmallSet.h" 00023 #include "llvm/ADT/SmallVector.h" 00024 #include "llvm/Support/CallSite.h" 00025 using namespace llvm; 00026 00027 /// PointerMayBeCaptured - Return true if this pointer value may be captured 00028 /// by the enclosing function (which is required to exist). This routine can 00029 /// be expensive, so consider caching the results. The boolean ReturnCaptures 00030 /// specifies whether returning the value (or part of it) from the function 00031 /// counts as capturing it or not. 00032 bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures) { 00033 assert(isa<PointerType>(V->getType()) && "Capture is for pointers only!"); 00034 SmallVector<Use*, 16> Worklist; 00035 SmallSet<Use*, 16> Visited; 00036 00037 for (Value::use_const_iterator UI = V->use_begin(), UE = V->use_end(); 00038 UI != UE; ++UI) { 00039 Use *U = &UI.getUse(); 00040 Visited.insert(U); 00041 Worklist.push_back(U); 00042 } 00043 00044 while (!Worklist.empty()) { 00045 Use *U = Worklist.pop_back_val(); 00046 Instruction *I = cast<Instruction>(U->getUser()); 00047 V = U->get(); 00048 00049 switch (I->getOpcode()) { 00050 case Instruction::Call: 00051 case Instruction::Invoke: { 00052 CallSite CS = CallSite::get(I); 00053 // Not captured if the callee is readonly, doesn't return a copy through 00054 // its return value and doesn't unwind (a readonly function can leak bits 00055 // by throwing an exception or not depending on the input value). 00056 if (CS.onlyReadsMemory() && CS.doesNotThrow() && 00057 I->getType() == Type::getVoidTy(V->getContext())) 00058 break; 00059 00060 // Not captured if only passed via 'nocapture' arguments. Note that 00061 // calling a function pointer does not in itself cause the pointer to 00062 // be captured. This is a subtle point considering that (for example) 00063 // the callee might return its own address. It is analogous to saying 00064 // that loading a value from a pointer does not cause the pointer to be 00065 // captured, even though the loaded value might be the pointer itself 00066 // (think of self-referential objects). 00067 CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); 00068 for (CallSite::arg_iterator A = B; A != E; ++A) 00069 if (A->get() == V && !CS.paramHasAttr(A - B + 1, Attribute::NoCapture)) 00070 // The parameter is not marked 'nocapture' - captured. 00071 return true; 00072 // Only passed via 'nocapture' arguments, or is the called function - not 00073 // captured. 00074 break; 00075 } 00076 case Instruction::Free: 00077 // Freeing a pointer does not cause it to be captured. 00078 break; 00079 case Instruction::Load: 00080 // Loading from a pointer does not cause it to be captured. 00081 break; 00082 case Instruction::Ret: 00083 if (ReturnCaptures) 00084 return true; 00085 break; 00086 case Instruction::Store: 00087 if (V == I->getOperand(0)) 00088 // Stored the pointer - it may be captured. 00089 return true; 00090 // Storing to the pointee does not cause the pointer to be captured. 00091 break; 00092 case Instruction::BitCast: 00093 case Instruction::GetElementPtr: 00094 case Instruction::PHI: 00095 case Instruction::Select: 00096 // The original value is not captured via this if the new value isn't. 00097 for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); 00098 UI != UE; ++UI) { 00099 Use *U = &UI.getUse(); 00100 if (Visited.insert(U)) 00101 Worklist.push_back(U); 00102 } 00103 break; 00104 default: 00105 // Something else - be conservative and say it is captured. 00106 return true; 00107 } 00108 } 00109 00110 // All uses examined - not captured. 00111 return false; 00112 }