X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FCaptureTracking.cpp;h=d9c02990a80125480bdd3bae75c5d6a98aec0334;hb=f4a5a613faa1a0eca6b884a6dfe83e8b1eb957b2;hp=8364d81497c2f5b9af1190cb0909f388ddedce26;hpb=837be07979723fb05ef47c828da014ce9ed1ba34;p=oota-llvm.git diff --git a/lib/Analysis/CaptureTracking.cpp b/lib/Analysis/CaptureTracking.cpp index 8364d81497c..d9c02990a80 100644 --- a/lib/Analysis/CaptureTracking.cpp +++ b/lib/Analysis/CaptureTracking.cpp @@ -16,15 +16,36 @@ // //===----------------------------------------------------------------------===// -#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" +#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 @@ -34,13 +55,40 @@ using namespace llvm; /// counts as capturing it or not. bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures) { - assert(isa(V->getType()) && "Capture is for pointers only!"); - SmallVector Worklist; - SmallSet Visited; + 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); } @@ -53,7 +101,7 @@ bool llvm::PointerMayBeCaptured(const Value *V, 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). @@ -69,28 +117,23 @@ bool llvm::PointerMayBeCaptured(const Value *V, // (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::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 - 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; + if (Tracker->captured(U)) + return; // Storing to the pointee does not cause the pointer to be captured. break; case Instruction::BitCast: @@ -102,27 +145,31 @@ bool llvm::PointerMayBeCaptured(const Value *V, 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)) + 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 (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. }