X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FCaptureTracking.cpp;h=42a54d9d1eb3adba766363cf2ef38765a12055b9;hb=ff10341183adf74760e6118a55cbd1debf50f90f;hp=773f53d2cd208a7bcdc1401707003c339b1a07e5;hpb=fe095f39e7009c51d1c86769792ccbcad8cdd2ec;p=oota-llvm.git diff --git a/lib/Analysis/CaptureTracking.cpp b/lib/Analysis/CaptureTracking.cpp index 773f53d2cd2..42a54d9d1eb 100644 --- a/lib/Analysis/CaptureTracking.cpp +++ b/lib/Analysis/CaptureTracking.cpp @@ -19,23 +19,43 @@ #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Instructions.h" #include "llvm/Value.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/CallSite.h" using namespace llvm; +/// As its comment mentions, PointerMayBeCaptured can be expensive. +/// However, it's not easy for BasicAA to cache the result, because +/// it's an ImmutablePass. To work around this, bound queries at a +/// fixed number of uses. +/// +/// TODO: Write a new FunctionPass AliasAnalysis so that it can keep +/// a cache. Then we can move the code from BasicAliasAnalysis into +/// that path, and remove this threshold. +static int const Threshold = 20; + /// PointerMayBeCaptured - Return true if this pointer value may be captured /// by the enclosing function (which is required to exist). This routine can /// be expensive, so consider caching the results. The boolean ReturnCaptures /// specifies whether returning the value (or part of it) from the function +/// counts as capturing it or not. The boolean StoreCaptures specified whether +/// storing the value (or part of it) into memory anywhere automatically /// counts as capturing it or not. -bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures) { - assert(isa(V->getType()) && "Capture is for pointers only!"); - SmallVector Worklist; - SmallSet Visited; +bool llvm::PointerMayBeCaptured(const Value *V, + bool ReturnCaptures, bool StoreCaptures) { + assert(V->getType()->isPointerTy() && "Capture is for pointers only!"); + SmallVector Worklist; + SmallSet Visited; + int Count = 0; - for (Value::use_const_iterator UI = V->use_begin(), UE = V->use_end(); + for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE; ++UI) { + // If there are lots of uses, conservatively say that the value + // is captured to avoid taking too much compile time. + if (Count++ >= Threshold) + return true; + Use *U = &UI.getUse(); Visited.insert(U); Worklist.push_back(U); @@ -50,6 +70,11 @@ bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures) { case Instruction::Call: case Instruction::Invoke: { CallSite CS(I); + // Not captured if the callee is readonly, doesn't return a copy through + // its return value and doesn't unwind (a readonly function can leak bits + // by throwing an exception or not depending on the input value). + if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy()) + break; // Not captured if only passed via 'nocapture' arguments. Note that // calling a function pointer does not in itself cause the pointer to @@ -58,69 +83,62 @@ bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures) { // that loading a value from a pointer does not cause the pointer to be // captured, even though the loaded value might be the pointer itself // (think of self-referential objects). - bool MayBeCaptured = false; CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); for (CallSite::arg_iterator A = B; A != E; ++A) - if (A->get() == V && !CS.paramHasAttr(A-B+1, Attribute::NoCapture)) { - // The parameter is not marked 'nocapture' - handled by generic code - // below. - MayBeCaptured = true; - break; - } - if (!MayBeCaptured) - // Only passed via 'nocapture' arguments, or is the called function - - // not captured. - continue; - if (!CS.doesNotThrow()) - // Even a readonly function can leak bits by throwing an exception or - // not depending on the input value. - return true; - // Fall through to the generic code. + if (A->get() == V && !CS.paramHasAttr(A - B + 1, Attribute::NoCapture)) + // The parameter is not marked 'nocapture' - captured. + return true; + // Only passed via 'nocapture' arguments, or is the called function - not + // captured. break; } - case Instruction::Free: - // Freeing a pointer does not cause it to be captured. - continue; case Instruction::Load: // Loading from a pointer does not cause it to be captured. - continue; + break; + case Instruction::VAArg: + // "va-arg" from a pointer does not cause it to be captured. + break; case Instruction::Ret: if (ReturnCaptures) return true; - continue; + break; case Instruction::Store: if (V == I->getOperand(0)) - // Stored the pointer - it may be captured. + // Stored the pointer - conservatively assume it may be captured. + // TODO: If StoreCaptures is not true, we could do Fancy analysis + // to determine whether this store is not actually an escape point. + // In that case, BasicAliasAnalysis should be updated as well to + // take advantage of this. return true; // Storing to the pointee does not cause the pointer to be captured. - continue; - } - - // If it may write to memory and isn't one of the special cases above, - // be conservative and assume the pointer is captured. - if (I->mayWriteToMemory()) + break; + case Instruction::BitCast: + case Instruction::GetElementPtr: + case Instruction::PHI: + case Instruction::Select: + // The original value is not captured via this if the new value isn't. + for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); + UI != UE; ++UI) { + Use *U = &UI.getUse(); + if (Visited.insert(U)) + Worklist.push_back(U); + } + break; + case Instruction::ICmp: + // Don't count comparisons of a no-alias return value against null as + // captures. This allows us to ignore comparisons of malloc results + // with null, for example. + if (isNoAliasCall(V->stripPointerCasts())) + if (ConstantPointerNull *CPN = + dyn_cast(I->getOperand(1))) + if (CPN->getType()->getAddressSpace() == 0) + break; + // Otherwise, be conservative. There are crazy ways to capture pointers + // using comparisons. return true; - - // If the instruction doesn't write memory, it can only capture by - // having its own value depend on the input value. - const Type* Ty = I->getType(); - if (Ty == Type::VoidTy) - // The value of an instruction can't be a copy if it can't contain any - // information. - continue; - if (!isa(Ty)) - // At the moment, we don't track non-pointer values, so be conservative - // and assume the pointer is captured. - // FIXME: Track these too. This would need to be done very carefully as - // it is easy to leak bits via control flow if integer values are allowed. + default: + // Something else - be conservative and say it is captured. return true; - - // The original value is not captured via this if the new value isn't. - for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); - UI != UE; ++UI) { - Use *U = &UI.getUse(); - if (Visited.insert(U)) - Worklist.push_back(U); } }