diff --git a/llvm/include/llvm/Analysis/CaptureTracking.h b/llvm/include/llvm/Analysis/CaptureTracking.h --- a/llvm/include/llvm/Analysis/CaptureTracking.h +++ b/llvm/include/llvm/Analysis/CaptureTracking.h @@ -25,6 +25,7 @@ class DominatorTree; class LoopInfo; class Function; + template class SmallPtrSetImpl; /// getDefaultMaxUsesToExploreForCaptureTracking - Return default value of /// the maximal number of uses to explore before giving up. It is used by @@ -41,8 +42,14 @@ /// MaxUsesToExplore specifies how many uses the analysis should explore for /// one value before giving up due too "too many uses". If MaxUsesToExplore /// is zero, a default value is assumed. + bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, + bool StoreCaptures, unsigned MaxUsesToExplore = 0); + + /// Variant of the above function which accepts a set of Values that are + /// ephemeral and cannot cause pointers to escape. bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, + const SmallPtrSetImpl &EphValues, unsigned MaxUsesToExplore = 0); /// PointerMayBeCapturedBefore - Return true if this pointer value may be diff --git a/llvm/lib/Analysis/CaptureTracking.cpp b/llvm/lib/Analysis/CaptureTracking.cpp --- a/llvm/lib/Analysis/CaptureTracking.cpp +++ b/llvm/lib/Analysis/CaptureTracking.cpp @@ -16,6 +16,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/CaptureTracking.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" @@ -74,8 +75,10 @@ namespace { struct SimpleCaptureTracker : public CaptureTracker { - explicit SimpleCaptureTracker(bool ReturnCaptures) - : ReturnCaptures(ReturnCaptures) {} + explicit SimpleCaptureTracker( + + const SmallPtrSetImpl &EphValues, bool ReturnCaptures) + : EphValues(EphValues), ReturnCaptures(ReturnCaptures) {} void tooManyUses() override { Captured = true; } @@ -83,10 +86,15 @@ if (isa(U->getUser()) && !ReturnCaptures) return false; + if (EphValues.contains(U->getUser())) + return false; + Captured = true; return true; } + const SmallPtrSetImpl &EphValues; + bool ReturnCaptures; bool Captured = false; @@ -212,8 +220,18 @@ /// 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, bool StoreCaptures, +bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures, + bool StoreCaptures, unsigned MaxUsesToExplore) { + SmallPtrSet Empty; + return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures, Empty, + MaxUsesToExplore); +} + +/// Variant of the above function which accepts a set of Values that are +/// ephemeral and cannot cause pointers to escape. +bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures, + bool StoreCaptures, + const SmallPtrSetImpl &EphValues, unsigned MaxUsesToExplore) { assert(!isa(V) && "It doesn't make sense to ask whether a global is captured."); @@ -224,7 +242,7 @@ // take advantage of this. (void)StoreCaptures; - SimpleCaptureTracker SCT(ReturnCaptures); + SimpleCaptureTracker SCT(EphValues, ReturnCaptures); PointerMayBeCaptured(V, &SCT, MaxUsesToExplore); if (SCT.Captured) ++NumCaptured; diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp --- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -38,7 +38,9 @@ #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/CaptureTracking.h" +#include "llvm/Analysis/CodeMetrics.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryBuiltins.h" @@ -762,6 +764,9 @@ // Post-order numbers for each basic block. Used to figure out if memory // accesses are executed before another access. DenseMap PostOrderNumbers; + // Values that are only used with assumes. Used to refine pointer escape + // analysis. + SmallPtrSet EphValues; /// Keep track of instructions (partly) overlapping with killing MemoryDefs per /// basic block. @@ -776,8 +781,8 @@ DSEState &operator=(const DSEState &) = delete; DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT, - PostDominatorTree &PDT, const TargetLibraryInfo &TLI, - const LoopInfo &LI) + PostDominatorTree &PDT, AssumptionCache &AC, + const TargetLibraryInfo &TLI, const LoopInfo &LI) : F(F), AA(AA), EI(DT, LI), BatchAA(AA, &EI), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI), DL(F.getParent()->getDataLayout()), LI(LI) { // Collect blocks with throwing instructions not modeled in MemorySSA and @@ -809,6 +814,8 @@ AnyUnreachableExit = any_of(PDT.roots(), [](const BasicBlock *E) { return isa(E->getTerminator()); }); + + CodeMetrics::collectEphemeralValues(&F, &AC, EphValues); } /// Return 'OW_Complete' if a store to the 'KillingLoc' location (by \p @@ -955,7 +962,7 @@ if (!isInvisibleToCallerOnUnwind(V)) { I.first->second = false; } else if (isNoAliasCall(V)) { - I.first->second = !PointerMayBeCaptured(V, true, false); + I.first->second = !PointerMayBeCaptured(V, true, false, EphValues); } } return I.first->second; @@ -974,7 +981,7 @@ // with the killing MemoryDef. But we refrain from doing so for now to // limit compile-time and this does not cause any changes to the number // of stores removed on a large test set in practice. - I.first->second = PointerMayBeCaptured(V, false, true); + I.first->second = PointerMayBeCaptured(V, false, true, EphValues); return !I.first->second; } @@ -1929,12 +1936,13 @@ static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT, PostDominatorTree &PDT, + AssumptionCache &AC, const TargetLibraryInfo &TLI, const LoopInfo &LI) { bool MadeChange = false; MSSA.ensureOptimizedUses(); - DSEState State(F, AA, MSSA, DT, PDT, TLI, LI); + DSEState State(F, AA, MSSA, DT, PDT, AC, TLI, LI); // For each store: for (unsigned I = 0; I < State.MemDefs.size(); I++) { MemoryDef *KillingDef = State.MemDefs[I]; @@ -2114,9 +2122,10 @@ DominatorTree &DT = AM.getResult(F); MemorySSA &MSSA = AM.getResult(F).getMSSA(); PostDominatorTree &PDT = AM.getResult(F); + AssumptionCache &AC = AM.getResult(F); LoopInfo &LI = AM.getResult(F); - bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI); + bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, AC, TLI, LI); #ifdef LLVM_ENABLE_STATS if (AreStatisticsEnabled()) @@ -2156,9 +2165,11 @@ MemorySSA &MSSA = getAnalysis().getMSSA(); PostDominatorTree &PDT = getAnalysis().getPostDomTree(); + AssumptionCache &AC = + getAnalysis().getAssumptionCache(F); LoopInfo &LI = getAnalysis().getLoopInfo(); - bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI); + bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, AC, TLI, LI); #ifdef LLVM_ENABLE_STATS if (AreStatisticsEnabled()) @@ -2182,6 +2193,7 @@ AU.addPreserved(); AU.addRequired(); AU.addPreserved(); + AU.addRequired(); } }; @@ -2199,6 +2211,7 @@ INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false, false) diff --git a/llvm/test/Transforms/DeadStoreElimination/assume.ll b/llvm/test/Transforms/DeadStoreElimination/assume.ll --- a/llvm/test/Transforms/DeadStoreElimination/assume.ll +++ b/llvm/test/Transforms/DeadStoreElimination/assume.ll @@ -8,7 +8,6 @@ ; CHECK-NEXT: [[TMP1:%.*]] = call noalias i8* @_Znwm(i64 32) ; CHECK-NEXT: [[TMP2:%.*]] = icmp ugt i8* [[TMP1]], @global ; CHECK-NEXT: call void @llvm.assume(i1 [[TMP2]]) -; CHECK-NEXT: store i8 0, i8* [[TMP1]], align 1 ; CHECK-NEXT: ret void ; %tmp1 = call noalias i8* @_Znwm(i64 32)