X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FCaptureTracking.cpp;h=d9c02990a80125480bdd3bae75c5d6a98aec0334;hb=f4a5a613faa1a0eca6b884a6dfe83e8b1eb957b2;hp=a19b8e4f94dbd3b940791a8bc5e9cd3fe5c8f973;hpb=1978426a94e3d3b53f488ffc56516e6e87906a0b;p=oota-llvm.git diff --git a/lib/Analysis/CaptureTracking.cpp b/lib/Analysis/CaptureTracking.cpp index a19b8e4f94d..d9c02990a80 100644 --- a/lib/Analysis/CaptureTracking.cpp +++ b/lib/Analysis/CaptureTracking.cpp @@ -16,27 +16,79 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/CaptureTracking.h" -#include "llvm/Instructions.h" -#include "llvm/Value.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/Support/CallSite.h" +#include "llvm/Analysis/CaptureTracking.h" using namespace llvm; +CaptureTracker::~CaptureTracker() {} + +bool CaptureTracker::shouldExplore(Use *U) { return true; } + +namespace { + struct SimpleCaptureTracker : public CaptureTracker { + explicit SimpleCaptureTracker(bool ReturnCaptures) + : ReturnCaptures(ReturnCaptures), Captured(false) {} + + void tooManyUses() { Captured = true; } + + bool captured(Use *U) { + if (isa(U->getUser()) && !ReturnCaptures) + return false; + + Captured = true; + return true; + } + + bool ReturnCaptures; + + bool Captured; + }; +} + /// 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(!isa(V) && + "It doesn't make sense to ask whether a global is 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. + (void)StoreCaptures; + + SimpleCaptureTracker SCT(ReturnCaptures); + PointerMayBeCaptured(V, &SCT); + return SCT.Captured; +} + +/// 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; + +void llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker) { + 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 Tracker->tooManyUses(); + Use *U = &UI.getUse(); + if (!Tracker->shouldExplore(U)) continue; Visited.insert(U); Worklist.push_back(U); } @@ -49,12 +101,11 @@ bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures) { switch (I->getOpcode()) { case Instruction::Call: case Instruction::Invoke: { - CallSite CS = CallSite::get(I); + 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() == Type::VoidTy) + if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy()) break; // Not captured if only passed via 'nocapture' arguments. Note that @@ -66,27 +117,23 @@ bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures) { // (think of self-referential objects). 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)) + if (A->get() == V && !CS.doesNotCapture(A - B)) // The parameter is not marked 'nocapture' - captured. - return true; - // Only passed via 'nocapture' arguments, or is the called function - not - // captured. + if (Tracker->captured(U)) + return; break; } - case Instruction::Free: - // Freeing a pointer does not cause it to be captured. - break; case Instruction::Load: // Loading from a pointer does not cause it to be captured. break; - case Instruction::Ret: - if (ReturnCaptures) - return true; + case Instruction::VAArg: + // "va-arg" from a pointer does not cause it to be captured. break; case Instruction::Store: if (V == I->getOperand(0)) - // Stored the pointer - it may be captured. - return true; + // Stored the pointer - conservatively assume it may be captured. + if (Tracker->captured(U)) + return; // Storing to the pointee does not cause the pointer to be captured. break; case Instruction::BitCast: @@ -98,15 +145,31 @@ bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures) { UI != UE; ++UI) { Use *U = &UI.getUse(); if (Visited.insert(U)) - Worklist.push_back(U); + if (Tracker->shouldExplore(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. + if (Tracker->captured(U)) + return; + break; default: // Something else - be conservative and say it is captured. - return true; + if (Tracker->captured(U)) + return; + break; } } - // All uses examined - not captured. - return false; + // All uses examined. }