X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FCaptureTracking.cpp;h=3708e6080f32ce1a557eeb60e5e48fee302aa02c;hb=2413bf30046836a27a060a1ede4671d0c6e0759a;hp=649b760b706912704962821acbb64caebb579c71;hpb=046e78ce55a7c3d82b7b6758d2d77f2d99f970bf;p=oota-llvm.git diff --git a/lib/Analysis/CaptureTracking.cpp b/lib/Analysis/CaptureTracking.cpp index 649b760b706..3708e6080f3 100644 --- a/lib/Analysis/CaptureTracking.cpp +++ b/lib/Analysis/CaptureTracking.cpp @@ -16,49 +16,99 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/CaptureTracking.h" -#include "llvm/Analysis/MallocHelper.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/AliasAnalysis.h" +#include "llvm/Analysis/CaptureTracking.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Instructions.h" + using namespace llvm; +CaptureTracker::~CaptureTracker() {} + +bool CaptureTracker::shouldExplore(const Use *U) { return true; } + +namespace { + struct SimpleCaptureTracker : public CaptureTracker { + explicit SimpleCaptureTracker(bool ReturnCaptures) + : ReturnCaptures(ReturnCaptures), Captured(false) {} + + void tooManyUses() override { Captured = true; } + + bool captured(const Use *U) override { + 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; - - for (Value::use_const_iterator UI = V->use_begin(), UE = V->use_end(); - UI != UE; ++UI) { - Use *U = &UI.getUse(); - Visited.insert(U); - Worklist.push_back(U); +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 (const Use &U : V->uses()) { + // 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(); + + if (!Tracker->shouldExplore(&U)) continue; + Visited.insert(&U); + Worklist.push_back(&U); } while (!Worklist.empty()) { - Use *U = Worklist.pop_back_val(); + const Use *U = Worklist.pop_back_val(); Instruction *I = cast(U->getUser()); V = U->get(); switch (I->getOpcode()) { case Instruction::Call: - if (isFreeCall(I)) - // Freeing a pointer does not cause it to be captured. - break; 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::getVoidTy(V->getContext())) + if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy()) break; // Not captured if only passed via 'nocapture' arguments. Note that @@ -70,44 +120,64 @@ 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::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: case Instruction::GetElementPtr: case Instruction::PHI: case Instruction::Select: + case Instruction::AddrSpaceCast: // 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); + Count = 0; + for (Use &UU : I->uses()) { + // 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(); + + if (Visited.insert(&UU)) + if (Tracker->shouldExplore(&UU)) + Worklist.push_back(&UU); } 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 (ConstantPointerNull *CPN = + dyn_cast(I->getOperand(1))) + if (CPN->getType()->getAddressSpace() == 0) + if (isNoAliasCall(V->stripPointerCasts())) + 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. }