From f87e0c68d78652aa9973e742e6c8df86fd7eee17 Mon Sep 17 00:00:00 2001 From: Dawid Jurczak Date: Fri, 22 Oct 2021 14:11:12 +0200 Subject: [PATCH] [DSE] Eliminates redundant store of an exisiting value (PR16520) 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(); Differential Revision: https://reviews.llvm.org/D111727 --- .../lib/Transforms/Scalar/DeadStoreElimination.cpp | 29 +++++++++++ .../stores-of-existing-values.ll | 56 ++++++++++++++++++---- 2 files changed, 77 insertions(+), 8 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp index 8cee53f..26ae587 100644 --- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -1941,6 +1941,34 @@ struct DSEState { 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(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; + LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n DEAD: " << *DefInst + << '\n'); + deleteDeadInstruction(DefInst); + NumRedundantStores++; + MadeChange = true; + } + return MadeChange; + } }; static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, @@ -2106,6 +2134,7 @@ static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, for (auto &KV : State.IOLs) MadeChange |= removePartiallyOverlappedStores(State.DL, KV.second, TLI); + MadeChange |= State.eliminateRedundantStoresOfExistingValues(); MadeChange |= State.eliminateDeadWritesAtEndOfFunction(); return MadeChange; } diff --git a/llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll b/llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll index 0380e80a..7888a39 100644 --- a/llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll +++ b/llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll @@ -7,7 +7,7 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f3 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( @@ -15,7 +15,6 @@ define void @test1_pr16520(i1 %b, i8* nocapture %r) { ; 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: @@ -42,8 +41,6 @@ if.end: ; preds = %if.else, %if.then } declare void @fn_mayread_or_clobber() - - declare void @fn_readonly() readonly define void @test2(i1 %b, i8* nocapture %r) { @@ -58,7 +55,6 @@ define void @test2(i1 %b, i8* nocapture %r) { ; 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: @@ -78,6 +74,39 @@ if.end: ; preds = %if.else, %if.then 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: @@ -185,7 +214,6 @@ define void @test6(i32* noalias %P) { ; 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: @@ -220,7 +248,6 @@ define void @test7(i32* noalias %P) { ; 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 @@ -272,7 +299,6 @@ define void @test9(i32* noalias %P) { ; 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 @@ -478,6 +504,20 @@ define void @test13_memset_shortened(i64* %ptr) { ret void } +declare i8* @strcat(i8*, i8*) nounwind argmemonly + +define void @test14_strcat(i8* noalias %P, i8* noalias %Q) { +; CHECK-LABEL: @test14_strcat( +; CHECK-NEXT: call i8* @strcat(i8* [[P:%.*]], i8* [[Q:%.*]]) +; CHECK-NEXT: call i8* @strcat(i8* [[P]], i8* [[Q]]) +; CHECK-NEXT: ret void +; + %call1 = call i8* @strcat(i8* %P, i8* %Q) + ; FIXME: Eliminate the second strcat as a "store of existing value" for this particular case, where both strcat's are identical (same source, not just same dest). + %call2 = call i8* @strcat(i8* %P, i8* %Q) + ret void +} + define void @pr49927(i32* %q, i32* %p) { ; CHECK-LABEL: @pr49927( ; CHECK-NEXT: [[V:%.*]] = load i32, i32* [[P:%.*]], align 4 -- 2.7.4