[DSE] Eliminates redundant store of an exisiting value (PR16520)

[yurai007]

Summary

That's https://reviews.llvm.org/D90328 follow-up.

This change eliminates writes to variables where the value that is being written is already stored in the variable. This achieves the goal by looping through all memory definitions in the current state and getting defining access from each of them. When there is defining access where the write instruction is identical to the original instruction it will remove this redundant write.

For example:

void f() {

x = 1;
if foo() {
   x = 1;
   g();
} else {
  h();
}

}
void g();
void h();

The second x=1 will be eliminated since it is rewriting 1 to x. This pass will produce this:

void f() {

x = 1;
if foo() {
   g();
} else {
  h();
}

}
void g();
void h();

[xbolva00]

llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll

314–341

Is this top of trunk?

[nikic]

This looks reasonable to me.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1947

Exisiting -> Existing

1948

This is a bool.

1950

Also exisiting -> existing

1955

auto *

[lebedev.ri]

All comments from the original review still apply.

[yurai007]

In D111727#3061936, @lebedev.ri wrote:

All comments from the original review still apply.

Do you have something specific in mind? It looks like all comments from old review are done (even if not marked as "fixed" which is quite confusing) except one from Nikita addressed in this change.

llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll

314–341

Oops, sorry. Now should be fine.

[yurai007]

Worth to mention that patch cannot help in resolving pr49927 because stores aren't identical. In theory pr50339 test could be fixed. However for now memcpyies are treated as clobbering ones and this is the reason why elimination is rejected.

[lebedev.ri]

https://reviews.llvm.org/D90328#2428525

In D111727#3069380, @yurai007 wrote:

In D111727#3061936, @lebedev.ri wrote:

All comments from the original review still apply.

Do you have something specific in mind? It looks like all comments from old review are done (even if not marked as "fixed" which is quite confusing) except one from Nikita addressed in this change.

In D90328#2428525, @lebedev.ri wrote:

Terminology check: the store being eliminated isn't so much dead,
it's that the stored value is identical to the currently-stored value,
i.e. the store is effectively a no-op.

In D90328#2432235, @fhahn wrote:

In D90328#2428525, @lebedev.ri wrote:

Terminology check: the store being eliminated isn't so much dead,
it's that the stored value is identical to the currently-stored value,
i.e. the store is effectively a no-op.

Yep, it would be better to refer to redundant or no-op stores.

[yurai007]

All comments addressed.

[fhahn]

This achieves the goal by looping through all memory definitions in the current state & each definitions uses.

Does the patch description need updating? Looks like it refers to looping over all uses, but the patch here looks at the defining access of each memdef?

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1955

can the defining access ever be null?

[nikic]

LGTM with @fhahn's comment addressed.

[fhahn]

Results in terms of additionally removed stores look good, thanks for picking up the patch!

LGTM as well with the commit addressed.

[fhahn]

Thanks for the updates. I left 2 more additional suggestions, please feel free to address them directly in the commit version.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1965

for debugging purposes it would be helpful if we had a debug message for removed stores here, like we have in other places.

2131

It might be better to eliminate the redundant stores after removePartiallyOverlappedStores, as this might shorten memsets based on state collected earlier. This will become an issue once we support eliminating stores made redundant by a memset, as in D112321

[yurai007]

@fhahn: Finally there is green light from CI for this change (that's why I hesitated with closing it even if CI failures were irrelevant to patch). Ok, before I push it I can address those 2 remaining comments here.

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1962

Actually, why do we need this isReadClobber() check? I don't think we care whether the instruction also reads the value, removing the redundant store is still fine. This would allow us to catch the @pr50339 case as well.

[yurai007]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1962

It's redundant and can be removed. I thought it was needed to ensure correctness for cases with intermediate clobbering (like tests3/test4). I will get rid of check and adjust tests.

[yurai007]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1962

Ok. Actually we cannot simply get rid of it. Now I see why it is needed. It's for self-reads like:

call void @llvm.memmove.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
call void @llvm.memmove.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)

Without check memmove is eliminated which is wrong when P and Q alias.

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1962

Oh right. It's okay to ignore the clobber for memcpy, but not for memmove. Let's leave it as-is for now.

This probably also prevents removing strcat(x, y); strcat(x, y);(with x, y noalias) as the second one will read x as well to find the insertion point. Might be worth adding a test for that case as well.

[yurai007]

Addressed comments.

[yurai007]

Rebased.

[yurai007]

Since all comments are addressed and it has already double LGTM I'm going to close it today.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
             return false;
         }
         return true;
       }
     }
 
     return false;
   }
+
+  /// Eliminates writes to locations where the value that is being written
+  /// is already stored at the same location.
+  bool eliminateRedundantStoresOfExistingValues() {
+    bool MadeChange = false;
+    LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs that write the "
+                         "already existing value\n");
+    for (auto *Def : MemDefs) {
+      if (SkipStores.contains(Def) || MSSA.isLiveOnEntryDef(Def) ||
+          !isRemovable(Def->getMemoryInst()))
+        continue;
+      auto *UpperDef = dyn_cast<MemoryDef>(Def->getDefiningAccess());
+      if (!UpperDef || MSSA.isLiveOnEntryDef(UpperDef))
+        continue;
+      auto *DefInst = Def->getMemoryInst();
+      auto *UpperInst = UpperDef->getMemoryInst();
+      auto MaybeUpperLoc = getLocForWriteEx(UpperInst);
+      if (!MaybeUpperLoc || !DefInst->isIdenticalTo(UpperInst) ||
+          isReadClobber(*MaybeUpperLoc, DefInst))
+        continue;
+      deleteDeadInstruction(DefInst);
+      NumRedundantStores++;
+      MadeChange = true;
+    }
+    return MadeChange;
+  }
 };
 
 static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                                 DominatorTree &DT, PostDominatorTree &PDT,
                                 const TargetLibraryInfo &TLI,
                                 const LoopInfo &LI) {
   bool MadeChange = false;
 
if (!Shortend && isRemovable(KillingI) &&
                         << '\n');
       State.deleteDeadInstruction(KillingI);
       NumRedundantStores++;
       MadeChange = true;
       continue;
     }
   }
 
+  MadeChange |= State.eliminateRedundantStoresOfExistingValues();
   if (EnablePartialOverwriteTracking)
     for (auto &KV : State.IOLs)
       MadeChange |= removePartiallyOverlappedStores(State.DL, KV.second, TLI);
 
   MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
   return MadeChange;
 }
 } // end anonymous namespace

llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -basic-aa -dse -S %s | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 @a = external global [32 x i8], align 16
 
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture writeonly, i8* noalias nocapture readonly, i64, i1 immarg)
 
-; Test case for PR16520. The store in %if.then is dead, because the same value
+; Test case for PR16520. The store in %if.then is redundant, because the same value
 ; has been stored earlier to the same location.
 define void @test1_pr16520(i1 %b, i8* nocapture %r) {
 ; CHECK-LABEL: @test1_pr16520(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    store i8 1, i8* [[R:%.*]], align 1
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    store i8 1, i8* [[R]], align 1
 ; CHECK-NEXT:    tail call void @fn_mayread_or_clobber()
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
 ; CHECK-NEXT:    tail call void @fn_mayread_or_clobber()
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    ret void
 ;
if.else:                                          ; preds = %entry
   tail call void @fn_mayread_or_clobber()
   br label %if.end
 
 if.end:                                           ; preds = %if.else, %if.then
   ret void
 }
 
 declare void @fn_mayread_or_clobber()
-
-
 declare void @fn_readonly() readonly
 
 define void @test2(i1 %b, i8* nocapture %r) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    store i8 1, i8* [[R:%.*]], align 1
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    tail call void @fn_readonly()
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
 ; CHECK-NEXT:    tail call void @fn_readonly()
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    store i8 1, i8* [[R]], align 1
 ; CHECK-NEXT:    ret void
 ;
 entry:
   store i8 1, i8* %r, align 1
   br i1 %b, label %if.then, label %if.else
 
 if.then:                                          ; preds = %entry
   tail call void @fn_readonly()
   br label %if.end
 
 if.else:                                          ; preds = %entry
   tail call void @fn_readonly()
   br label %if.end
 
 if.end:                                           ; preds = %if.else, %if.then
   store i8 1, i8* %r, align 1
   ret void
 }
 
+; Make sure volatile stores are not removed.
+define void @test2_volatile(i1 %b, i8* nocapture %r) {
+; CHECK-LABEL: @test2_volatile(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store volatile i8 1, i8* [[R:%.*]], align 1
+; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    tail call void @fn_readonly()
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    tail call void @fn_readonly()
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store volatile i8 1, i8* [[R]], align 1
+; CHECK-NEXT:    ret void
+;
+entry:
+  store volatile i8 1, i8* %r, align 1
+  br i1 %b, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  tail call void @fn_readonly()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  tail call void @fn_readonly()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  store volatile i8 1, i8* %r, align 1
+  ret void
+}
+
 define void @test3(i1 %b, i8* nocapture %r) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    store i8 1, i8* [[R:%.*]], align 1
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    tail call void @fn_mayread_or_clobber()
 ; CHECK-NEXT:    br label [[IF_END:%.*]]

 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_HEADER:%.*]]
 ; CHECK:       for.header:
 ; CHECK-NEXT:    store i32 1, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[C1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[C1]], label [[FOR_BODY:%.*]], label [[END:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
 ; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[P]], align 4
 ; CHECK-NEXT:    br label [[FOR_HEADER]]
 ; CHECK:       end:
 ; CHECK-NEXT:    store i32 3, i32* [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.header

 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb3:
-; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
   store i32 0, i32* %P
   br i1 true, label %bb1, label %bb2
 bb1:
   br label %bb3
 bb2:
   ret void

 ; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    call void @fn_mayread_or_clobber()
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb3:
-; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
   store i32 0, i32* %P
   br i1 true, label %bb1, label %bb2
 bb1:
   br label %bb3
 bb2:
   call void @fn_mayread_or_clobber()
   ret void
 bb3:
   store i32 0, i32* %P
   ret void
 }
 
 define void @pr49927(i32* %q, i32* %p) {
 ; CHECK-LABEL: @pr49927(
 ; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    store i32 [[V]], i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    store i32 [[V]], i32* [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
   %v = load i32, i32* %p, align 4
   store i32 %v, i32* %q, align 4
   ; FIXME: this store can be eliminated
   store i32 %v, i32* %p, align 4
   ret void
 }
 
 
 define void @pr50339(i8* nocapture readonly %0) {
 ; CHECK-LABEL: @pr50339(
 ; CHECK-NEXT:    tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* noundef nonnull align 16 dereferenceable(16) getelementptr inbounds ([32 x i8], [32 x i8]* @a, i64 0, i64 0), i8* noundef nonnull align 1 dereferenceable(16) [[TMP0:%.*]], i64 16, i1 false)
 ; CHECK-NEXT:    tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* noundef nonnull align 16 dereferenceable(16) getelementptr inbounds ([32 x i8], [32 x i8]* @a, i64 0, i64 0), i8* noundef nonnull align 1 dereferenceable(16) [[TMP0]], i64 16, i1 false)
 ; CHECK-NEXT:    ret void
 ;
   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* noundef nonnull align 16 dereferenceable(16) getelementptr inbounds ([32 x i8], [32 x i8]* @a, i64 0, i64 0), i8* noundef nonnull align 1 dereferenceable(16) %0, i64 16, i1 false)
   ; FIXME: Eliminate the second memcpy as a "store of existing value" for this particular case, where both memcpy's are identical (same source, not just same dest).
   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* noundef nonnull align 16 dereferenceable(16) getelementptr inbounds ([32 x i8], [32 x i8]* @a, i64 0, i64 0), i8* noundef nonnull align 1 dereferenceable(16) %0, i64 16, i1 false)
   ret void
 }