[DSE] Use notCapturedBeforeOrAt for isInvisibleToCallerBeforeRet (WIP).

[fhahn]

Summary

Not for commit!

PoC for using the caching introduced in D109844 for
isInvisibleToCallerBeforeRet.

This has a noticeable compile-time impact at the moment.

http://llvm-compile-time-tracker.com/compare.php?from=c12ba45d25e0bdde24b639b2638e8e735069f192&to=1ac1575395e6d51e512dce563375bae1784c2b04&stat=instructions

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

if (I.second) {
         auto *Inst = dyn_cast<Instruction>(V);
         if (Inst && isAllocLikeFn(Inst, &TLI))
           I.first->second = !PointerMayBeCaptured(V, true, false);
       }
     }
     return I.first->second;
   }
 
-  bool isInvisibleToCallerBeforeRet(const Value *V) {
+  bool isInvisibleToCallerBeforeRet(const Value *V,
+                                    Instruction *CtxI = nullptr) {
     if (isa<AllocaInst>(V))
       return true;
     auto I = InvisibleToCallerBeforeRet.insert({V, false});
     if (I.second) {
       auto *Inst = dyn_cast<Instruction>(V);
       if (Inst && isAllocLikeFn(Inst, &TLI))
         // NOTE: This could be made more precise by PointerMayBeCapturedBefore
         // 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);
     }
+    if (!I.first->second && CtxI)
+      return notCapturedBeforeOrAt(V, CtxI);
     return I.first->second;
   }
 
   Optional<MemoryLocation> getLocForWriteEx(Instruction *I) const {
     if (!I->mayWriteToMemory())
       return None;
 
     if (auto *MTI = dyn_cast<AnyMemIntrinsic>(I))
for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
         return Current;
       }
 
       // Below, check if CurrentDef is a valid candidate to be eliminated by
       // KillingDef. If it is not, check the next candidate.
       MemoryDef *CurrentDef = cast<MemoryDef>(Current);
       Instruction *CurrentI = CurrentDef->getMemoryInst();
 
-      if (canSkipDef(CurrentDef, !isInvisibleToCallerBeforeRet(DefUO), TLI))
+      if (canSkipDef(CurrentDef, !isInvisibleToCallerBeforeRet(DefUO, CurrentI),
+                     TLI))
         continue;
 
       // Before we try to remove anything, check for any extra throwing
       // instructions that block us from DSEing
       if (mayThrowBetween(KillingI, CurrentI, DefUO)) {
         LLVM_DEBUG(dbgs() << "  ... skip, may throw!\n");
         return None;
       }
for (unsigned I = 0; I < WorkList.size(); I++) {
       }
 
       if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {
         LLVM_DEBUG(dbgs() << "    ... adding uses of intrinsic\n");
         PushMemUses(UseAccess);
         continue;
       }
 
-      if (UseInst->mayThrow() && !isInvisibleToCallerBeforeRet(DefUO)) {
+      if (UseInst->mayThrow() &&
+          !isInvisibleToCallerBeforeRet(DefUO, UseInst)) {
         LLVM_DEBUG(dbgs() << "  ... found throwing instruction\n");
         return None;
       }
 
       // Uses which may read the original MemoryDef mean we cannot eliminate the
       // original MD. Stop walk.
       if (isReadClobber(*CurrentLoc, UseInst)) {
         LLVM_DEBUG(dbgs() << "    ... found read clobber\n");
struct DSEState {
   // Check for any extra throws between SI and NI that block DSE.  This only
   // checks extra maythrows (those that aren't MemoryDef's). MemoryDef that may
   // throw are handled during the walk from one def to the next.
   bool mayThrowBetween(Instruction *SI, Instruction *NI,
                        const Value *SILocUnd) {
     // First see if we can ignore it by using the fact that SI is an
     // alloca/alloca like object that is not visible to the caller during
     // execution of the function.
-    if (SILocUnd && isInvisibleToCallerBeforeRet(SILocUnd))
+    if (SILocUnd && isInvisibleToCallerBeforeRet(SILocUnd, NI))
       return false;
 
     if (SI->getParent() == NI->getParent())
       return ThrowingBlocks.count(SI->getParent());
     return !ThrowingBlocks.empty();
   }
 
   // Check if \p NI acts as a DSE barrier for \p SI. The following instructions
   // act as barriers:
   //  * A memory instruction that may throw and \p SI accesses a non-stack
   //  object.
   //  * Atomic stores stronger that monotonic.
   bool isDSEBarrier(const Value *SILocUnd, Instruction *NI) {
     // If NI may throw it acts as a barrier, unless we are to an alloca/alloca
     // like object that does not escape.
-    if (NI->mayThrow() && !isInvisibleToCallerBeforeRet(SILocUnd))
+    if (NI->mayThrow() && !isInvisibleToCallerBeforeRet(SILocUnd, NI))
       return true;
 
     // If NI is an atomic load/store stronger than monotonic, do not try to
     // eliminate/reorder it.
     if (NI->isAtomic()) {
       if (auto *LI = dyn_cast<LoadInst>(NI))
         return isStrongerThanMonotonic(LI->getOrdering());
       if (auto *SI = dyn_cast<StoreInst>(NI))

llvm/test/Transforms/DeadStoreElimination/multiblock-captures.ll

exit:
   ret i8* %m
 }
 
 ; TODO: We could remove the first store store i8 0, i8* %m because %m escapes
 ; after the killing store.
 define i8* @test_malloc_capture_4() {
 ; CHECK-LABEL: @test_malloc_capture_4(
 ; CHECK-NEXT:    [[M:%.*]] = call i8* @malloc(i64 24)
-; CHECK-NEXT:    store i8 0, i8* [[M]], align 1
 ; CHECK-NEXT:    call void @may_throw_readnone()
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    store i8 1, i8* [[M]], align 1
 ; CHECK-NEXT:    call void @capture(i8* [[M]])
 ; CHECK-NEXT:    ret i8* [[M]]
 ;
 

 
 
 ; TODO: We could remove the first store 'store i8 0, i8* %m' even though there
 ; is a throwing instruction between them, because %m escapes after the killing
 ; store.
 define i8* @test_malloc_capture_6() {
 ; CHECK-LABEL: @test_malloc_capture_6(
 ; CHECK-NEXT:    [[M:%.*]] = call i8* @malloc(i64 24)
-; CHECK-NEXT:    store i8 0, i8* [[M]], align 1
 ; CHECK-NEXT:    call void @may_throw_readnone()
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    store i8 1, i8* [[M]], align 1
 ; CHECK-NEXT:    call void @capture(i8* [[M]])
 ; CHECK-NEXT:    ret i8* [[M]]
 ;
 

 ; throwing instruction between them, because %m escapes after the killing store.
 ; But this would require using PointerMayBeCapturedBefore in
 ; isInvisibleToCallerBeforeRet, which we currently do not do to limit
 ; compile-time, as this appears to hardly ever lead to more stores eliminated
 ; in practice.
 define i8* @test_malloc_capture_7() {
 ; CHECK-LABEL: @test_malloc_capture_7(
 ; CHECK-NEXT:    [[M:%.*]] = call i8* @malloc(i64 24)
-; CHECK-NEXT:    store i8 0, i8* [[M]], align 1
 ; CHECK-NEXT:    call void @may_throw()
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    store i8 1, i8* [[M]], align 1
 ; CHECK-NEXT:    call void @capture(i8* [[M]])
 ; CHECK-NEXT:    ret i8* [[M]]
 ;
 

llvm/test/Transforms/DeadStoreElimination/multiblock-malloc-free.ll

 bb3:
   call void @free(i8* %P2)
   store i32 1, i32* %P
   ret void
 }
 
 ; We cannot remove the store in the entry block, because @unknown_func could
 ; unwind and the stored value could be read by the caller.
-define void @test17(i32* noalias %P) {
+define void @test17(i32* %P) {
 ; CHECK-LABEL: @test17(
 ; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
 ; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    call void @unknown_func()
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    call void @free(i8* [[P2]])
 ; CHECK-NEXT:    ret void
 ;
   %P2 = bitcast i32* %P to i8*
   store i32 1, i32* %P
   br i1 true, label %bb1, label %bb3
 bb1:
   call void @unknown_func()
   store i32 1, i32* %P
   br label %bb3
 bb3:
   call void @free(i8* %P2)
   ret void
 }
 
+; Same as @test17, but with the argument %P being noalias. This guarantees that
+; @unknown_func cannot access it and the store can be removed.
+define void @test17_2(i32* noalias %P) {
+; CHECK-LABEL: @test17_2(
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    call void @free(i8* [[P2]])
+; CHECK-NEXT:    ret void
+;
+  %P2 = bitcast i32* %P to i8*
+  store i32 1, i32* %P
+  br i1 true, label %bb1, label %bb3
+bb1:
+  call void @unknown_func()
+  store i32 1, i32* %P
+  br label %bb3
+bb3:
+  call void @free(i8* %P2)
+  ret void
+}
+
 define void @test17_read_after_free(i32* noalias %P) {
 ; CHECK-LABEL: @test17_read_after_free(
 ; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    call void @free(i8* [[P2]])

llvm/test/Transforms/DeadStoreElimination/simple.ll

bb1:
   call void @unknown_func()
   br i1 undef, label %bb1, label %bb2
 bb2:
   ret i32 0
 }
 
 ; We cannot remove any stores, because @unknown_func may unwind and the caller
 ; may read %p while unwinding.
-define void @test34(i32* noalias %p) {
+define void @test34(i32* %p) {
 ; CHECK-LABEL: @test34(
 ; CHECK-NEXT:    store i32 1, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    call void @unknown_func()
 ; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
   store i32 1, i32* %p
   call void @unknown_func()
   store i32 0, i32* %p
   ret void
 }
 
+; Like @test34 but with the argument %p being noalias. @unknown_func cannot
+; access the object and the first store can be removed.
+define void @test34_2(i32* noalias %p) {
+; CHECK-LABEL: @test34_2(
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %p
+  call void @unknown_func()
+  store i32 0, i32* %p
+  ret void
+}
+
 ; Remove redundant store even with an unwinding function in the same block
 define void @test35(i32* noalias %p) {
 ; CHECK-LABEL: @test35(
 ; CHECK-NEXT:    call void @unknown_func()
 ; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    ret void
 ;
   call void @unknown_func()
entry:
   call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %Ac)
   ret void
 }
 
 declare void @free(i8* nocapture)
 
 ; We cannot remove `store i32 1, i32* %p`, because @unknown_func may unwind
 ; and the caller may read %p while unwinding.
-define void @test41(i32* noalias %P) {
+define void @test41(i32* %P) {
 ; CHECK-LABEL: @test41(
 ; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
 ; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
 ; CHECK-NEXT:    call void @unknown_func()
 ; CHECK-NEXT:    call void @free(i8* [[P2]])
 ; CHECK-NEXT:    ret void
 ;
   %P2 = bitcast i32* %P to i8*
   store i32 1, i32* %P
   call void @unknown_func()
   store i32 2, i32* %P
   call void @free(i8* %P2)
   ret void
 }
 
+; Like @test41 but with the argument %p being noalias. @unknown_func cannot
+; access the object and the first store can be removed.
+define void @test41_2(i32* noalias %P) {
+; CHECK-LABEL: @test41_2(
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    call void @free(i8* [[P2]])
+; CHECK-NEXT:    ret void
+;
+  %P2 = bitcast i32* %P to i8*
+  store i32 1, i32* %P
+  call void @unknown_func()
+  store i32 2, i32* %P
+  call void @free(i8* %P2)
+  ret void
+}
+
 define void @test42(i32* %P, i32* %Q) {
 ; CHECK-LABEL: @test42(
 ; CHECK-NEXT:    store i32 1, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P]] to i8*
 ; CHECK-NEXT:    store i32 2, i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    store i8 3, i8* [[P2]], align 1
 ; CHECK-NEXT:    ret void
 ;