Index: include/llvm/Analysis/CaptureTracking.h =================================================================== --- include/llvm/Analysis/CaptureTracking.h +++ include/llvm/Analysis/CaptureTracking.h @@ -14,13 +14,19 @@ #ifndef LLVM_ANALYSIS_CAPTURETRACKING_H #define LLVM_ANALYSIS_CAPTURETRACKING_H +#include "llvm/IR/PassManager.h" +#include "llvm/Pass.h" + namespace llvm { - class Value; - class Use; - class Instruction; + class AAResults; class DominatorTree; + class Function; + class Instruction; class OrderedBasicBlock; + class Use; + class Value; + class raw_ostream; /// PointerMayBeCaptured - Return true if this pointer value may be captured /// by the enclosing function (which is required to exist). This routine can @@ -33,6 +39,17 @@ bool ReturnCaptures, bool StoreCaptures); + /// 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. For the latter to have + /// effect, Alias Analysis results are required. + bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, + bool StoreCaptures, AAResults *AA); + /// PointerMayBeCapturedBefore - Return true if this pointer value may be /// captured by the enclosing function (which is required to exist). If a /// DominatorTree is provided, only captures which happen before the given @@ -72,6 +89,18 @@ virtual bool captured(const Use *U) = 0; }; + /// Printer pass for the EscapeInfo results. + class CaptureTrackingPrinterPass + : public PassInfoMixin { + + public: + explicit CaptureTrackingPrinterPass(raw_ostream &OS); + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + + private: + raw_ostream &OS; + }; + /// PointerMayBeCaptured - Visit the value and the values derived from it and /// find values which appear to be capturing the pointer value. This feeds /// results into and is controlled by the CaptureTracker object. Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -303,7 +303,7 @@ const SCEV *Expr = nullptr); /// Returns true if \p Phi is a floating point induction in the loop \p L. - /// If \p Phi is an induction, the induction descriptor \p D will contain + /// If \p Phi is an induction, the induction descriptor \p D will contain /// the data describing this induction. static bool isFPInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE, InductionDescriptor &D); @@ -432,7 +432,8 @@ SmallVectorImpl &, PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, - Loop *, AliasSetTracker *, LoopSafetyInfo *); + AliasAnalysis *AA, Loop *, AliasSetTracker *, + LoopSafetyInfo *); /// \brief Computes safety information for a loop /// checks loop body & header for the possibility of may throw Index: lib/Analysis/CaptureTracking.cpp =================================================================== --- lib/Analysis/CaptureTracking.cpp +++ lib/Analysis/CaptureTracking.cpp @@ -54,6 +54,65 @@ bool Captured; }; + struct OptimisticCaptureTracker : public CaptureTracker { + + OptimisticCaptureTracker(bool ReturnCaptures, bool StoreCaptures, + AliasAnalysis *AA) + : ReturnCaptures(ReturnCaptures), StoreCaptures(StoreCaptures), AA(AA), + Captured(false) {} + + void tooManyUses() override { Captured = true; } + + bool storeCaptures(const StoreInst *S) { + if (StoreCaptures) + return true; + + if (!AA) + return true; + + const Function *F = S->getFunction(); + const Value *Ptr = S->getPointerOperand(); + + // Check if the pointer is stored to a function argument. + for (auto &Arg : F->getArgumentList()) { + if (!isa(Arg.getType())) + continue; + + if (!AA->isNoAlias(Ptr, MemoryLocation::UnknownSize, &Arg, + MemoryLocation::UnknownSize)) + return true; + } + + // Check if the pointer is stored to a global. + for (auto &Global : F->getParent()->globals()) { + if (!AA->isNoAlias(Ptr, MemoryLocation::UnknownSize, &Global, + MemoryLocation::UnknownSize)) + return true; + } + + return false; + } + + bool captured(const Use *U) override { + if (isa(U->getUser()) && !ReturnCaptures) + return false; + + if (auto *S = dyn_cast(U->getUser())) + if (!storeCaptures(S)) + return false; + + Captured = true; + return true; + } + + bool ReturnCaptures; + bool StoreCaptures; + + AliasAnalysis *AA; + + bool Captured; + }; + /// Only find pointer captures which happen before the given instruction. Uses /// the dominator tree to determine whether one instruction is before another. /// Only support the case where the Value is defined in the same basic block @@ -149,6 +208,26 @@ }; } +CaptureTrackingPrinterPass::CaptureTrackingPrinterPass(raw_ostream &OS) + : OS(OS) {} + +PreservedAnalyses CaptureTrackingPrinterPass::run(Function &F, + FunctionAnalysisManager &AM) { + OS << "Capture tracking results for function: " << F.getName() << "\n"; + auto& AA = AM.getResult(F); + for(auto& BB : F) { + for(auto& I : BB) { + if(auto* V = dyn_cast(&I)){ + if(V->getType()->isPointerTy() && PointerMayBeCaptured(V, true, false, &AA)) { + OS << V->getName() << " may be captured\n"; + } + } + } + } + + return PreservedAnalyses::all(); +} + /// 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 @@ -165,11 +244,36 @@ // 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; + //(void)StoreCaptures; + + // TODO: We can essentially the SimpleCaptureTracker completely with the + // Optimistic one and possibly reuse the name? + + // SimpleCaptureTracker SCT(ReturnCaptures); + // PointerMayBeCaptured(V, &SCT); + // return SCT.Captured; - SimpleCaptureTracker SCT(ReturnCaptures); - PointerMayBeCaptured(V, &SCT); - return SCT.Captured; + OptimisticCaptureTracker OCT(ReturnCaptures, StoreCaptures, nullptr); + PointerMayBeCaptured(V, &OCT); + return OCT.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. For the latter to have effect, Alias Analysis +/// results are required. +bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures, + bool StoreCaptures, AliasAnalysis *AA) { + assert(!isa(V) && + "It doesn't make sense to ask whether a global is captured."); + + OptimisticCaptureTracker OCT(ReturnCaptures, StoreCaptures, AA); + PointerMayBeCaptured(V, &OCT); + return OCT.Captured; } /// PointerMayBeCapturedBefore - Return true if this pointer value may be @@ -276,11 +380,12 @@ // "va-arg" from a pointer does not cause it to be captured. break; case Instruction::Store: - // Stored the pointer - conservatively assume it may be captured. - // Volatile stores make the address observable. - if (V == I->getOperand(0) || cast(I)->isVolatile()) + // Stored the pointer - conservatively assume it may be captured. + // Volatile stores make the address observable. + if (V == I->getOperand(0) || cast(I)->isVolatile()) { if (Tracker->captured(U)) return; + } break; case Instruction::AtomicRMW: { // atomicrmw conceptually includes both a load and store from Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -24,6 +24,7 @@ #include "llvm/Analysis/BlockFrequencyInfo.h" #include "llvm/Analysis/BlockFrequencyInfoImpl.h" #include "llvm/Analysis/BranchProbabilityInfo.h" +#include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/CFGPrinter.h" #include "llvm/Analysis/CFLAndersAliasAnalysis.h" #include "llvm/Analysis/CFLSteensAliasAnalysis.h" Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -172,6 +172,7 @@ FUNCTION_PASS("print", AssumptionPrinterPass(dbgs())) FUNCTION_PASS("print", BlockFrequencyPrinterPass(dbgs())) FUNCTION_PASS("print", BranchProbabilityPrinterPass(dbgs())) +FUNCTION_PASS("print", CaptureTrackingPrinterPass(dbgs())) FUNCTION_PASS("print", DominatorTreePrinterPass(dbgs())) FUNCTION_PASS("print", PostDominatorTreePrinterPass(dbgs())) FUNCTION_PASS("print", DemandedBitsPrinterPass(dbgs())) Index: lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- lib/Transforms/Scalar/DeadStoreElimination.cpp +++ lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -1089,8 +1089,9 @@ // where the allocation doesn't escape before the last // throwing instruction; PointerMayBeCaptured // reasonably fast approximation. - IsStoreDeadOnUnwind = isAllocLikeFn(Underlying, TLI) && - !PointerMayBeCaptured(Underlying, false, true); + IsStoreDeadOnUnwind = + isAllocLikeFn(Underlying, TLI) && + !PointerMayBeCaptured(Underlying, false, false, AA); } if (!IsStoreDeadOnUnwind) break; Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -250,8 +250,9 @@ // Loop over all of the alias sets in the tracker object. for (AliasSet &AS : *CurAST) - Changed |= promoteLoopAccessesToScalars( - AS, ExitBlocks, InsertPts, PIC, LI, DT, TLI, L, CurAST, &SafetyInfo); + Changed |= + promoteLoopAccessesToScalars(AS, ExitBlocks, InsertPts, PIC, LI, DT, + TLI, AA, L, CurAST, &SafetyInfo); // Once we have promoted values across the loop body we have to recursively // reform LCSSA as any nested loop may now have values defined within the @@ -843,7 +844,8 @@ AliasSet &AS, SmallVectorImpl &ExitBlocks, SmallVectorImpl &InsertPts, PredIteratorCache &PIC, LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI, - Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo) { + AliasAnalysis *AA, Loop *CurLoop, AliasSetTracker *CurAST, + LoopSafetyInfo *SafetyInfo) { // Verify inputs. assert(LI != nullptr && DT != nullptr && CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr && @@ -1007,8 +1009,8 @@ // paths which originally didn't have them without violating the memory // model. Value *Object = GetUnderlyingObject(SomePtr, MDL); - PromotionIsLegal = - isAllocLikeFn(Object, TLI) && !PointerMayBeCaptured(Object, true, true); + PromotionIsLegal = isAllocLikeFn(Object, TLI) && + !PointerMayBeCaptured(Object, true, false, AA); } if (!PromotionIsLegal) return Changed; Index: test/Analysis/CaptureTracking/captureargstore.ll =================================================================== --- /dev/null +++ test/Analysis/CaptureTracking/captureargstore.ll @@ -0,0 +1,33 @@ +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s + +; CHECK: l may be captured +; CHECK: n may be captured +; CHECK: j may be captured + +define void @sample(i32* %i) #0 { +entry: + %i.addr = alloca i32*, align 8 + %k = alloca i32*, align 8 + store i32* %i, i32** %i.addr, align 8 + %call = call i8* @malloc(i64 4) + %l = bitcast i8* %call to i32* + store i32* %l, i32** %k, align 8 + %m = load i32*, i32** %k, align 8 + store i32 0, i32* %m, align 4 + %n = load i32*, i32** %k, align 8 + store i32* %n, i32** %i.addr, align 8 + ret void +} + +declare i8* @malloc(i64) + +define i32 @main() { +entry: + %retval = alloca i32, align 4 + %j = alloca i32, align 4 + store i32 0, i32* %retval, align 4 + store i32 1, i32* %j, align 4 + call void @sample(i32* %j) + %0 = load i32, i32* %j, align 4 + ret i32 %0 +} Index: test/Analysis/CaptureTracking/captureindirectstore.ll =================================================================== --- /dev/null +++ test/Analysis/CaptureTracking/captureindirectstore.ll @@ -0,0 +1,18 @@ +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s + +; CHECK: ptr may be captured +; CHECK-NOT: ptrtoptr may be captured +; CHECK: deref may be captured + +@global = external global i32* + +define void @sample() { +entry: + %ptr = alloca i32 + store i32 1, i32* %ptr + %ptrtoptr = alloca i32* + store i32* %ptr, i32** %ptrtoptr + %deref = load i32*, i32** %ptrtoptr + store i32* %deref , i32** @global + ret void +} Index: test/Analysis/CaptureTracking/nocapturestore.ll =================================================================== --- /dev/null +++ test/Analysis/CaptureTracking/nocapturestore.ll @@ -0,0 +1,13 @@ +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s + +; CHECK-NOT: ptr may be captured +; CHECK-NOT: ptrtoptr may be captured + +define void @sample() { +entry: + %ptr = alloca i32 + store i32 1, i32* %ptr + %ptrtoptr = alloca i32* + store i32* %ptr, i32** %ptrtoptr + ret void +}