DeadStoreElimination: remove a redundant store even if the load is in a different block.

[eeckstein]

Summary

DeadStoreElimination does eliminate a store if it stores a value which was loaded from the same memory location.
So far this worked only if the store is in the same block as the load. This patch allows that the load is in another block than the store.
Example:

define i32 @test26(i1, i32*) {
entry:

%l2 = load i32, i32* %1, align 4
br i1 %0, label %bb1, label %bb2

bb1:

br label %bb3

bb2:

; This store is redundant
store i32 %l2, i32* %1, align 4
br label %bb3

bb3:

ret i32 0

}

[qcolombet]

Hi Erik,

Couple of comments:
Please upload your patch with the full context.
Please use -instnamer on your test cases to get rid of the %[0-9]+ variables.

Thanks,
-Quentin

[majnemer]

Could you please provide more context in the diff for DeadStoreElimination.cpp?

[eeckstein]

renamed variables in test
diff with full context

[reames]

lib/Transforms/Scalar/DeadStoreElimination.cpp

496 ↗

(On Diff #31562)

I think you'd be better to phrase the non-local query here so that it benefits both sub-optimizations.

504 ↗

(On Diff #31562)

Phasing this is isNonLocal wouldbe much clearer.

[• dberlin]

So, Karthik posted and got http://reviews.llvm.org/D11143 reviewed

Does this not cover your case?

Additionally, " MD->getNonLocalPointerDependency(SI, Deps);"

This is very compile time expensive to call a lot. I'd really like to know how often yours actually triggers, and what performance different it actually makes relative to Karthik's

[eeckstein]

Thanks for looking at this patch.

So, Karthik posted and got http://reviews.llvm.org/D11143 reviewed
Does this not cover your case?

I checked this and no, it does not cover my case.

Nevertheless thanks for pointing me to Karthik's patch. I think I will invest a little bit more work and use a similar work-list algorithm as Kathik. It will cover more cases: my current approach (with getNonLocalPointerDependency) has the drawback that it does not work if there is a (harmless) other load between the first load and the store.

Also I assume (but I'm not sure) it will be faster than getNonLocalPointerDependency.

I will upload an updated patch soon. But anyway I don't want to commit anything until Kathik's patch has landed so that there are no conflicts.

Thanks,
Erik

[eeckstein]

This updated version uses a work-list algorithm to do the safety checking. This has 2 advantages compared to MD->getNonLocalPointerDependency:

1. It ignores load instructions which should not prevent the optimization
2. It's faster because it bails out at the first memory alias it finds.

I still have to do some measurements. I will post some data in the next time.

[eeckstein]

Philip, thanks for your comments on the first version. Please let me know if your questions are still relevant with this updated patch.

[eeckstein]

Some data from the lnt test suite:

Compile time: I did not see any changes which are not noise.
Execution time: There are a few benchmarks with improvements, but I think most (if not all) is noise.

Static statistics data:
This optimization effects redundant stores of the form:

%x = load %p
store %x, %p

With this patch the compiler can eliminate 131 more redundant stores of this kind.

[eeckstein]

Correction to the static data:

In the original version, the compiler did eliminate 46 redundant stores of this kind.
With this patch, the compiler eliminates 131 redundant stores of this kind.
So the difference is 85 or 2.8x.

[• dberlin]

LGTM
LNT doesn't have particularly large programs, so not seeing compile
time effects there is not surprising. Your walk may in fact, walk the
entire CFG *for each store* (if load is in entry block, store is near
exit block).

This is, in general, a really expensive way to perform this optimization.

It's sad this can't take advantage of GVN, and instead just directly
compares pointer operands. This means things like bitcasts/etc, will
cause it to not eliminate dead stores it could. Another thing on the
pile of usefulness for separating GVN's analysis and elimination.

However, all that said, i'm fine with this patch, we'll fix any
compile time issues when they pop up by doing it right.

--Dan

[eeckstein]

Thanks for reviewing!

PS to compile time: while you are right that it goes over the whole CFG for each store, this is only the worst case scenario.
The MemoryIsNotModifiedBetween() is only called if the value and pointer operands match, which is the case for 0.2% of all stores.
And even then it bails out early if it finds a potentially aliased store. On average MemoryIsNotModifiedBetween() traverses only about 3 blocks or 10 instructions per invocation. On average it calls 2 times getModRefInfo per invocation.

[eeckstein]

Here is an updated version with a bug fix in MemoryIsNotModifiedBetween.
I also added a few tests.

I plan to commit it tomorrow unless anyone has additional comments on the update.

Thanks,
Erik

[eeckstein]

committed in r244901

llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp

 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/Local.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "dse"
 
+STATISTIC(NumRedundantStores, "Number of redundant stores deleted");
 STATISTIC(NumFastStores, "Number of stores deleted");
 STATISTIC(NumFastOther , "Number of other instrs removed");
 
 namespace {
   struct DSE : public FunctionPass {
     AliasAnalysis *AA;
     MemoryDependenceAnalysis *MD;
     DominatorTree *DT;
bool runOnFunction(Function &F) override {
         if (DT->isReachableFromEntry(I))
           Changed |= runOnBasicBlock(*I);
 
       AA = nullptr; MD = nullptr; DT = nullptr;
       return Changed;
     }
 
     bool runOnBasicBlock(BasicBlock &BB);
+    bool MemoryIsNotModifiedBetween(LoadInst *LI, StoreInst *SI);
     bool HandleFree(CallInst *F);
     bool handleEndBlock(BasicBlock &BB);
     void RemoveAccessedObjects(const MemoryLocation &LoadedLoc,
                                SmallSetVector<Value *, 16> &DeadStackObjects,
                                const DataLayout &DL);
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
if (CallInst *F = isFreeCall(Inst, TLI)) {
       MadeChange |= HandleFree(F);
       continue;
     }
 
     // If we find something that writes memory, get its memory dependence.
     if (!hasMemoryWrite(Inst, *TLI))
       continue;
 
-    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;
-
     // If we're storing the same value back to a pointer that we just
     // loaded from, then the store can be removed.
     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
-      if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) {
+      if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
         if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
-            SI->getOperand(0) == DepLoad && isRemovable(SI)) {
+            isRemovable(SI) &&
+            MemoryIsNotModifiedBetween(DepLoad, SI)) {
+
           DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n  "
                        << "LOAD: " << *DepLoad << "\n  STORE: " << *SI << '\n');
 
           // DeleteDeadInstruction can delete the current instruction.  Save BBI
           // in case we need it.
           WeakVH NextInst(BBI);
 
           DeleteDeadInstruction(SI, *MD, *TLI);
 
           if (!NextInst)  // Next instruction deleted.
             BBI = BB.begin();
           else if (BBI != BB.begin())  // Revisit this instruction if possible.
             --BBI;
-          ++NumFastStores;
+          ++NumRedundantStores;
           MadeChange = true;
           continue;
         }
       }
     }
 
+    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;
 
     while (InstDep.isDef() || InstDep.isClobber()) {
bool DSE::runOnBasicBlock(BasicBlock &BB) {
   // If this block ends in a return, unwind, or unreachable, all allocas are
   // dead at its end, which means stores to them are also dead.
   if (BB.getTerminator()->getNumSuccessors() == 0)
     MadeChange |= handleEndBlock(BB);
 
   return MadeChange;
 }
 
+/// Returns true if the memory which is accessed by the store instruction is not
+/// modified between the load and the store instruction.
+/// Precondition: The store instruction must be dominated by the load
+/// instruction.
+bool DSE::MemoryIsNotModifiedBetween(LoadInst *LI, StoreInst *SI) {
+  SmallVector<BasicBlock *, 16> WorkList;
+  SmallPtrSet<BasicBlock *, 8> Visited;
+  BasicBlock::iterator LoadBBI(LI);
+  ++LoadBBI;
+  BasicBlock::iterator StoreBBI(SI);
+  BasicBlock *LoadBB = LI->getParent();
+  BasicBlock *StoreBB = SI->getParent();
+  MemoryLocation StoreLoc = MemoryLocation::get(SI);
+
+  // Start checking the store-block.
+  WorkList.push_back(StoreBB);
+  bool isFirstBlock = true;
+
+  // Check all blocks going backward until we reach the load-block.
+  while (!WorkList.empty()) {
+    BasicBlock *B = WorkList.pop_back_val();
+
+    // Ignore instructions before LI if this is the LoadBB.
+    BasicBlock::iterator BI = (B == LoadBB ? LoadBBI : B->begin());
+
+    BasicBlock::iterator EI;
+    if (isFirstBlock) {
+      // Ignore instructions after SI if this is the first visit of StoreBB.
+      assert(B == StoreBB && "first block is not the store block");
+      EI = StoreBBI;
+      isFirstBlock = false;
+    } else {
+      // It's not StoreBB or (in case of a loop) the second visit of StoreBB.
+      // In this case we also have to look at instructions after SI.
+      EI = B->end();
+    }
+    for (; BI != EI; ++BI) {
+      Instruction *I = BI;
+      if (I->mayWriteToMemory() && I != SI) {
+        auto Res = AA->getModRefInfo(I, StoreLoc);
+        if (Res != MRI_NoModRef)
+          return false;
+      }
+    }
+    if (B != LoadBB) {
+      assert(B != &LoadBB->getParent()->getEntryBlock() &&
+          "Should not hit the entry block because SI must be dominated by LI");
+      for (auto PredI = pred_begin(B), PE = pred_end(B); PredI != PE; ++PredI) {
+        if (!Visited.insert(*PredI).second)
+          continue;
+        WorkList.push_back(*PredI);
+      }
+    }
+  }
+  return true;
+}
+
 /// Find all blocks that will unconditionally lead to the block BB and append
 /// them to F.
 static void FindUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks,
                                    BasicBlock *BB, DominatorTree *DT) {
   for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
     BasicBlock *Pred = *I;
     if (Pred == BB) continue;
     TerminatorInst *PredTI = Pred->getTerminator();

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

 define i8* @test25(i8* %p) nounwind {
   %p.4 = getelementptr i8, i8* %p, i64 4
   %tmp = load i8, i8* %p.4, align 1
   store i8 0, i8* %p.4, align 1
   %q = call i8* @strdup(i8* %p) nounwind optsize
   store i8 %tmp, i8* %p.4, align 1
   ret i8* %q
 }
+
+; Remove redundant store if loaded value is in another block.
+; CHECK-LABEL: @test26(
+; CHECK-NOT: store
+; CHECK: ret
+define i32 @test26(i1 %c, i32* %p) {
+entry:
+  %v = load i32, i32* %p, align 4
+  br i1 %c, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 %v, i32* %p, align 4
+  br label %bb3
+bb3:
+  ret i32 0
+}
+
+; Remove redundant store if loaded value is in another block.
+; CHECK-LABEL: @test27(
+; CHECK-NOT: store
+; CHECK: ret
+define i32 @test27(i1 %c, i32* %p) {
+entry:
+  %v = load i32, i32* %p, align 4
+  br i1 %c, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  br label %bb3
+bb3:
+  store i32 %v, i32* %p, align 4
+  ret i32 0
+}
+
+; Don't remove redundant store because of may-aliased store.
+; CHECK-LABEL: @test28(
+; CHECK: bb3:
+; CHECK-NEXT: store i32 %v
+define i32 @test28(i1 %c, i32* %p, i32* %p2, i32 %i) {
+entry:
+  %v = load i32, i32* %p, align 4
+
+  ; Might overwrite value at %p
+  store i32 %i, i32* %p2, align 4
+  br i1 %c, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  br label %bb3
+bb3:
+  store i32 %v, i32* %p, align 4
+  ret i32 0
+}
+
+; Don't remove redundant store because of may-aliased store.
+; CHECK-LABEL: @test29(
+; CHECK: bb3:
+; CHECK-NEXT: store i32 %v
+define i32 @test29(i1 %c, i32* %p, i32* %p2, i32 %i) {
+entry:
+  %v = load i32, i32* %p, align 4
+  br i1 %c, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  ; Might overwrite value at %p
+  store i32 %i, i32* %p2, align 4
+  br label %bb3
+bb3:
+  store i32 %v, i32* %p, align 4
+  ret i32 0
+}
+
+declare void @unknown_func()
+
+; Don't remove redundant store because of unknown call.
+; CHECK-LABEL: @test30(
+; CHECK: bb3:
+; CHECK-NEXT: store i32 %v
+define i32 @test30(i1 %c, i32* %p, i32 %i) {
+entry:
+  %v = load i32, i32* %p, align 4
+  br i1 %c, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  ; Might overwrite value at %p
+  call void @unknown_func()
+  br label %bb3
+bb3:
+  store i32 %v, i32* %p, align 4
+  ret i32 0
+}
+
+; Remove redundant store if loaded value is in another block inside a loop.
+; CHECK-LABEL: @test31(
+; CHECK-NOT: store
+; CHECK: ret
+define i32 @test31(i1 %c, i32* %p, i32 %i) {
+entry:
+  %v = load i32, i32* %p, align 4
+  br label %bb1
+bb1:
+  store i32 %v, i32* %p, align 4
+  br i1 undef, label %bb1, label %bb2
+bb2:
+  ret i32 0
+}
+
+; Don't remove redundant store in a loop with a may-alias store.
+; CHECK-LABEL: @test32(
+; CHECK: bb1:
+; CHECK-NEXT: store i32 %v
+; CHECK-NEXT: call void @unknown_func
+define i32 @test32(i1 %c, i32* %p, i32 %i) {
+entry:
+  %v = load i32, i32* %p, align 4
+  br label %bb1
+bb1:
+  store i32 %v, i32* %p, align 4
+  ; Might read and overwrite value at %p
+  call void @unknown_func()
+  br i1 undef, label %bb1, label %bb2
+bb2:
+  ret i32 0
+}
+
+; Remove redundant store, which is in the lame loop as the load.
+; CHECK-LABEL: @test33(
+; CHECK-NOT: store
+; CHECK: ret
+define i32 @test33(i1 %c, i32* %p, i32 %i) {
+entry:
+  br label %bb1
+bb1:
+  %v = load i32, i32* %p, align 4
+  br label %bb2
+bb2:
+  store i32 %v, i32* %p, align 4
+  ; Might read and overwrite value at %p, but doesn't matter.
+  call void @unknown_func()
+  br i1 undef, label %bb1, label %bb3
+bb3:
+  ret i32 0
+}
+