[DSE] Improve mayThrowBetween for 2 instructions in the same BB.

[fhahn]

Summary

This patch adds a way to quickly check if there are throwing instructions
between two instructions in the same basic block.

To do so, we first number all instructions in a BB starting from 0 and
incrementing the counter every time we hit a throwing instruction. If
2 instructions have the same number, there is no throwing instruction
between them.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

[efriedma]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1644

What happens if NI is the first instruction in the block? Or is that impossible in this context?

1706

This map seems sort of expensive, but maybe not a big deal relative to other stuff we have here already.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1644

I think that should be impossible, as SI must come before NI (they cannot be equal either) and SI and NI must be in the same BB.

1706

Yep, we probably should populate it lazily. And I think at least for C/C++ programs, it should not really be needed at all. There's no difference in the MultiSource/SPEC2000/SPEC2006 binaries with and without this patch, now that I updated D72146 to skip throwing instructions modeled in MemorySSA.

[efriedma]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1706

That's not surprising. It's theoretically possible to have a function that's readnone and not nothrow, but it doesn't happen in practice for C/C++ code.

[fhahn]

This is not really required for C/C++. I'll re-visit the patch once we have the more important pieces of MemorySSA based machinery in.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1706

Yep, I think wit would probably make sense to re-visit this patch later and focus on getting the other parts in first :)

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

while (!NowDeadInsts.empty()) {
 
     DeadInst->eraseFromParent();
   }
 }
 
 // Check for any extra throws between SI and NI that block DSE.  This only
 // checks extra maythrows (those that arn'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,
-                     SmallSetVector<const Value *, 16> &InvisibleToCaller,
-                     SmallPtrSetImpl<BasicBlock *> &ThrowingBlocks) {
+bool mayThrowBetween(
+    Instruction *SI, Instruction *NI, const Value *SILocUnd,
+    DenseMap<BasicBlock *, DenseMap<Instruction *, unsigned>> &ThrowingBlocks) {
   // 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 && InvisibleToCaller.count(SILocUnd))
     return false;
 
-  if (SI->getParent() == NI->getParent())
-    return ThrowingBlocks.find(SI->getParent()) != ThrowingBlocks.end();
+  if (SI->getParent() == NI->getParent()) {
+    auto BlockMap = ThrowingBlocks.find(SI->getParent());
+    if (BlockMap == ThrowingBlocks.end())
+      return false;
+    return BlockMap->second[SI] !=
+           BlockMap->second[&*std::prev(NI->getIterator())];
+  }
   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 instructions stronger that monotonic.
 bool isDSEBarrier(Instruction *SI, MemoryLocation &SILoc, const Value *SILocUnd,
bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
   SmallVector<MemoryDef *, 4> Stores;
   // Any that should be skipped as they are already deleted
   SmallPtrSet<MemoryDef *, 4> SkipStores;
   // A map of interval maps representing partially-overwritten value parts
   InstOverlapIntervalsTy IOL;
   // Keep track of all of the objects that are invisible to the caller until the
   // function returns.
   SmallSetVector<const Value *, 16> InvisibleToCaller;
-  // Keep track of blocks with throwing instructions.
-  SmallPtrSet<BasicBlock *, 16> ThrowingBlocks;
+  // Keep track of blocks with throwing instructions. For each block with
+  // throwing instructions, we number all instructions in the block, starting
+  // with 0 and incrementing the counter for throwing instructions. If 2
+  // instructions have the same number there are no throwing instructions
+  // between them.
+  DenseMap<BasicBlock *, DenseMap<Instruction *, unsigned>> ThrowingBlocks;
 
   // Post-order numbers for basic blocks in the function.
   DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
   unsigned PO = 0;
   // Collect blocks with throwing instructions, alloc-like objects and
   // post-order numbers for basic blocks.
   for (BasicBlock *BB : post_order(&F)) {
     PostOrderNumbers[BB] = PO++;
+
+    unsigned ThrowingCnt = 0;
+    DenseMap<Instruction *, unsigned> BlockMap;
     for (Instruction &I : *BB) {
       if (I.mayThrow())
-        ThrowingBlocks.insert(I.getParent());
+        ThrowingCnt++;
+      BlockMap[&I] = ThrowingCnt;
 
       auto *MD = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(&I));
       if (MD && hasAnalyzableMemoryWrite(&I, TLI) && isRemovable(&I))
         Stores.push_back(MD);
 
     // Track alloca and alloca-like objects. Here we care about objects not
     // visible to the caller during function execution. Alloca objects are
     // invalid in the caller, for alloca-like objects we ensure that they are
     // not captured throughout the function.
     if (isa<AllocaInst>(&I) ||
         (isAllocLikeFn(&I, &TLI) && !PointerMayBeCaptured(&I, false, true)))
       InvisibleToCaller.insert(&I);
     }
+
+    // Only add the mapping for blocks with any throwing instructions.
+    if (ThrowingCnt != 0)
+      ThrowingBlocks[BB] = BlockMap;
   }
   // Treat byval or inalloca arguments the same as Allocas, stores to them are
   // dead at the end of the function.
   for (Argument &AI : F.args())
     if (AI.hasByValOrInAllocaAttr())
       InvisibleToCaller.insert(&AI);
 
   // For each store:

llvm/test/Transforms/DeadStoreElimination/MSSA/combined-partial-overwrites.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -dse -enable-dse-partial-store-merging=false < %s | FileCheck %s
+; RUN: opt -S -dse -enable-dse-memoryssa -enable-dse-partial-store-merging=false < %s | FileCheck %s
 target datalayout = "E-m:e-i64:64-n32:64"
 target triple = "powerpc64-bgq-linux"
 
 %"struct.std::complex" = type { { float, float } }
 
 define void @_Z4testSt7complexIfE(%"struct.std::complex"* noalias nocapture sret %agg.result, i64 %c.coerce) {
 ; CHECK-LABEL: @_Z4testSt7complexIfE(
 ; CHECK-NEXT:  entry:

 }
 
 define signext i8 @test5(i32 *%ptr) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[BPTR:%.*]] = bitcast i32* [[PTR:%.*]] to i8*
 ; CHECK-NEXT:    [[BPTR1:%.*]] = getelementptr inbounds i8, i8* [[BPTR]], i64 1
 ; CHECK-NEXT:    [[BPTR2:%.*]] = getelementptr inbounds i8, i8* [[BPTR]], i64 2
+; CHECK-NEXT:    [[BPTR3:%.*]] = getelementptr inbounds i8, i8* [[BPTR]], i64 3
 ; CHECK-NEXT:    [[WPTR:%.*]] = bitcast i8* [[BPTR]] to i16*
 ; CHECK-NEXT:    [[WPTR1:%.*]] = bitcast i8* [[BPTR1]] to i16*
 ; CHECK-NEXT:    [[WPTR2:%.*]] = bitcast i8* [[BPTR2]] to i16*
 ; CHECK-NEXT:    store i16 -1, i16* [[WPTR2]], align 1
 ; CHECK-NEXT:    store i16 1456, i16* [[WPTR1]], align 1
 ; CHECK-NEXT:    store i16 1346, i16* [[WPTR]], align 1
 ; CHECK-NEXT:    ret i8 0
 ;

llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll

 }
 
 ; TODO
 ; We can remove redundant store, as noalias %p guarantees that the function does
 ; only access it via %p. This also holds for the call to unknown_func even though
 ; it could unwind
 define void @test34(i32* noalias %p) {
 ; CHECK-LABEL: @test34(
-; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
 ; CHECK-NEXT:    call void @unknown_func()
 ; CHECK-NEXT:    store i32 0, i32* [[P]]
 ; CHECK-NEXT:    ret void
 ;
   store i32 1, i32* %p
   call void @unknown_func()
   store i32 0, i32* %p
   ret void
 }
 
-; TODO
 ; 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 1, i32* [[P:%.*]]
 ; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
 ; CHECK-NEXT:    ret void
 ;
   call void @unknown_func()
   store i32 1, i32* %p
   store i32 0, i32* %p
   ret void
 }

 define void @test41(i32* noalias %P) {
 ; NOCHECK-LABEL: @test41(
 ; NOCHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
 ; NOCHECK-NEXT:    store i32 1, i32* [[P]]
 ; NOCHECK-NEXT:    call void @unknown_func()
 ; NOCHECK-NEXT:    call void @free(i8* [[P2]])
 ; NOCHECK-NEXT:    ret void
 ;
+; CHECK-LABEL: @test41(
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    store i32 2, i32* [[P]]
+; 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) {
 ; NOCHECK-LABEL: @test42(
 ; NOCHECK-NEXT:    store i32 1, i32* [[P:%.*]]
 ; NOCHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P]] to i8*
 ; NOCHECK-NEXT:    store i32 2, i32* [[Q:%.*]]
 ; NOCHECK-NEXT:    store i8 3, i8* [[P2]]
 ; NOCHECK-NEXT:    ret void
 ;
+; CHECK-LABEL: @test42(
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P]] to i8*
+; CHECK-NEXT:    store i32 2, i32* [[Q:%.*]]
+; CHECK-NEXT:    store i8 3, i8* [[P2]]
+; CHECK-NEXT:    ret void
+;
   store i32 1, i32* %P
   %P2 = bitcast i32* %P to i8*
   store i32 2, i32* %Q
   store i8 3, i8* %P2
   ret void
 }
 
 define void @test42a(i32* %P, i32* %Q) {
 ; NOCHECK-LABEL: @test42a(
 ; NOCHECK-NEXT:    store atomic i32 1, i32* [[P:%.*]] unordered, align 4
 ; NOCHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P]] to i8*
 ; NOCHECK-NEXT:    store atomic i32 2, i32* [[Q:%.*]] unordered, align 4
 ; NOCHECK-NEXT:    store atomic i8 3, i8* [[P2]] unordered, align 4
 ; NOCHECK-NEXT:    ret void
 ;
+; CHECK-LABEL: @test42a(
+; CHECK-NEXT:    store atomic i32 1, i32* [[P:%.*]] unordered, align 4
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P]] to i8*
+; CHECK-NEXT:    store atomic i32 2, i32* [[Q:%.*]] unordered, align 4
+; CHECK-NEXT:    store atomic i8 3, i8* [[P2]] unordered, align 4
+; CHECK-NEXT:    ret void
+;
   store atomic i32 1, i32* %P unordered, align 4
   %P2 = bitcast i32* %P to i8*
   store atomic i32 2, i32* %Q unordered, align 4
   store atomic i8 3, i8* %P2 unordered, align 4
   ret void
 }