[DSE] Improve handling of noop stores exposed after dead interfering stores are removed

[sameconrad]

Summary

This is an attempt to improve the handling of noop stores that are only exposed after the removal of interfering stores. This forces removal of noops to occur last after other deletions are complete, but should otherwise have the same semantics if the loop body exits early (ie when no def or clobbers found).

[efriedma]

Do you have any size/performance numbers for this? (Just trying to get a rough sense of how helpful this is.)

lib/Transforms/Scalar/DeadStoreElimination.cpp

1082

Can you reorganize this somehow so you don't use make_scope_exit()? Using RAII for control flow is tricky to follow. (If can't come up with anything better, even explicitly calling the lambda would be an improvement.)

[sameconrad]

Updated to call lambda manually, which seems like the simplest solution. Will work on some benchmark results, I don't have any offhand.

[efriedma]

lib/Transforms/Scalar/DeadStoreElimination.cpp

1091

Could you just eliminate this entire if statement? The condition is the same as the while loop's condition.

1097

I don't think EliminateNoop can actually do anything useful in this case; getLocForWrite never fails for store instructions.

[sameconrad]

Updated to remove unnecessary isDef/isClobber check, lambda is no longer necessary.

I did some benchmarking but unfortunately I couldn't find any noticeable differences in executable size from this patch. At least, nothing in test-suite seemed to result in any changes to the compiled binaries with this patch. It seems like the situation this is addressing is probably pretty rare.

lib/Transforms/Scalar/DeadStoreElimination.cpp

 // FIXME: This should eventually be extended to be a post-dominator tree
 // traversal.  Doing so would be pretty trivial.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/DeadStoreElimination.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
if (Inst->mayThrow()) {
       LastThrowingInstIndex = CurInstNumber;
       continue;
     }
 
     // Check to see if Inst writes to memory.  If not, continue.
     if (!hasMemoryWrite(Inst, *TLI))
       continue;
 
-    // eliminateNoopStore will update in iterator, if necessary.
-    if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, &InstrOrdering)) {
+    // Attempt to eliminate a noop store last. The store may not be a noop at
+    // this point, but could be rendered one by the removal of dead intervening
+    // stores below. We still want to attempt this anyway if there are no local
+    // memdeps, because noop elimination can work across blocks.
+    auto EliminateNoop = make_scope_exit([&]() {
+      if (Inst /* may be nulled if merged with partial store */ &&
+          eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, &InstrOrdering))
         MadeChange = true;
-      continue;
-    }
+    });
 
     // If we find something that writes memory, get its memory dependence.
     MemDepResult InstDep = MD->getDependency(Inst);
 
     // Ignore any store where we can't find a local dependence.
     // FIXME: cross-block DSE would be fun. :)
     if (!InstDep.isDef() && !InstDep.isClobber())
       continue;
 
     // Figure out what location is being stored to.
     MemoryLocation Loc = getLocForWrite(Inst, *AA);
 
     // If we didn't get a useful location, fail.
     if (!Loc.Ptr)
       continue;
 
     // Loop until we find a store we can eliminate or a load that
     // invalidates the analysis. Without an upper bound on the number of
     // instructions examined, this analysis can become very time-consuming.
     // However, the potential gain diminishes as we process more instructions
     // without eliminating any of them. Therefore, we limit the number of
     // instructions we look at.
     auto Limit = MD->getDefaultBlockScanLimit();
while (InstDep.isDef() || InstDep.isClobber()) {
 
             // Remove earlier, wider, store
             size_t Idx = InstrOrdering.lookup(DepWrite);
             InstrOrdering.erase(DepWrite);
             InstrOrdering.insert(std::make_pair(SI, Idx));
 
             // Delete the old stores and now-dead instructions that feed them.
             deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL, &InstrOrdering);
+            Inst = nullptr;
             deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
                                   &InstrOrdering);
             MadeChange = true;
 
             // We erased DepWrite and Inst (Loc); start over.
             break;
           }
         }

test/Transforms/DeadStoreElimination/late-noop.ll

+; Test to make sure noop stores exposed by removal of intervening stores can be removed,
+; even when the original load is in a different block
+; RUN: opt < %s -basicaa -dse -S | FileCheck %s
+
+define i32 @foo2(i32* %i, i1 %cond) {
+; Both stores removed, first dead, second as late noop
+B1:
+; CHECK-LABEL: B1
+; CHECK-NEXT: %val.i = load i32, i32* %i, align 4
+; CHECK-NEXT: br i1 %cond
+  %val.i = load i32, i32* %i, align 4
+  %newval.i = add i32 %val.i, 1
+  store i32 %newval.i, i32* %i, align 4
+  store i32 %val.i, i32* %i, align 4
+  br i1 %cond, label %B2, label %B3
+
+; Both stores removed, first dead, second as late noop
+B2:
+; CHECK: B2:
+; CHECK-NEXT: br label %B4
+  %val.i2 = load i32, i32* %i, align 4
+  %newval.i2 = add i32 %val.i2, 1
+  store i32 %newval.i2, i32* %i, align 4
+  store i32 %val.i, i32* %i, align 4
+  br label %B4
+
+; Store not dead, no dep in the same block
+B3:
+; CHECK: B3
+; CHECK-NEXT: %val.i3 = load i32, i32* %i, align 4
+; CHECK-NEXT: %newval.i3 = add i32 %val.i3, 1
+; CHECK-NEXT: store i32 %newval.i3, i32* %i, align 4
+; CHECK-NEXT: br label %B4
+  %val.i3 = load i32, i32* %i, align 4
+  %newval.i3 = add i32 %val.i3, 1
+  store i32 %newval.i3, i32* %i, align 4
+  br label %B4
+
+; Store not removed as noop due to presence of store in B3
+B4:
+; CHECK: B4
+; CHECK-NEXT: store i32 %val.i, i32* %i, align 4
+; CHECK-NEXT: %val.i4 = load i32, i32* %i, align 4
+; CHECK-NEXT: ret i32 %val.i4
+  store i32 %val.i, i32* %i, align 4
+  %val.i4 = load i32, i32* %i, align 4
+  ret i32 %val.i4
+}

test/Transforms/DeadStoreElimination/simple.ll

 ; CHECK-NEXT: store i32 0
 ; CHECK-NEXT: ret void
 define void @test35(i32* noalias %p) {
   call void @unknown_func()
   store i32 1, i32* %p
   store i32 0, i32* %p
   ret void
 }
+
+; Basic late noop removal
+; CHECK-LABEL: @test36(
+; CHECK-NEXT: %val.i2 = load i32, i32* %i, align 4
+; CHECK-NEXT: ret
+define i32 @test36(i32* %i) {
+  %val.i = load i32, i32* %i, align 4
+  %newval.i1 = add i32 %val.i, 1
+  store i32 %newval.i1, i32* %i, align 4
+  %newval.i2 = add i32 %newval.i1, 1
+  store i32 %newval.i2, i32* %i, align 4
+  store i32 %val.i, i32* %i, align 4
+  %val.i2 = load i32, i32* %i, align 4
+  ret i32 %val.i2
+}
+