From 05e4f7bde95a83192b84f8bb1e6bcd416343154c Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Fri, 30 Oct 2020 09:32:43 +0000 Subject: [PATCH] [DSE] Remove noop stores after killing stores for a MemoryDef. Currently we fail to eliminate some noop stores if there is a kill-able store between the starting def and the load. This is because we eliminate noop stores first. In practice it seems like eliminating noop stores after the main elimination for a def covers slightly more cases. This patch improves the number of stores slightly in 2 cases for X86 -O3 -flto Same hash: 235 (filtered out) Remaining: 2 Metric: dse.NumRedundantStores Program base patch diff test-suite...ce/Benchmarks/PAQ8p/paq8p.test 2.00 3.00 50.0% test-suite...006/453.povray/453.povray.test 18.00 21.00 16.7% There might be other phase ordering issues, but it appears that they do not show up in the test-suite/SPEC2000/SPEC2006. We can always tune the ordering later. Partly fixes PR47887. Reviewed By: asbirlea, zoecarver Differential Revision: https://reviews.llvm.org/D89650 --- .../lib/Transforms/Scalar/DeadStoreElimination.cpp | 27 ++++++++++++---------- .../DeadStoreElimination/MSSA/calloc-store.ll | 4 ---- .../DeadStoreElimination/MSSA/noop-stores.ll | 7 ------ 3 files changed, 15 insertions(+), 23 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp index 2738050..acdb1c4 100644 --- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -2504,15 +2504,6 @@ bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA, assert(SILoc.Ptr && "SILoc should not be null"); const Value *SILocUnd = getUnderlyingObject(SILoc.Ptr); - // Check if the store is a no-op. - if (isRemovable(SI) && State.storeIsNoop(KillingDef, SILoc, SILocUnd)) { - LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n DEAD: " << *SI << '\n'); - State.deleteDeadInstruction(SI); - NumRedundantStores++; - MadeChange = true; - continue; - } - MemoryAccess *Current = KillingDef; LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by " << *KillingDef << " (" << *SI << ")\n"); @@ -2522,10 +2513,11 @@ bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA, unsigned PartialLimit = MemorySSAPartialStoreLimit; // Worklist of MemoryAccesses that may be killed by KillingDef. SetVector ToCheck; - ToCheck.insert(KillingDef->getDefiningAccess()); - if (!SILocUnd) - continue; + if (SILocUnd) + ToCheck.insert(KillingDef->getDefiningAccess()); + + bool Shortend = false; bool IsMemTerm = State.isMemTerminatorInst(SI); DSEState::CheckCache Cache; // Check if MemoryAccesses in the worklist are killed by KillingDef. @@ -2612,6 +2604,7 @@ bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA, ++NumModifiedStores; MadeChange = true; + Shortend = true; // Remove later store and remove any outstanding overlap intervals // for the updated store. State.deleteDeadInstruction(Later); @@ -2632,6 +2625,16 @@ bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA, } } } + + // Check if the store is a no-op. + if (!Shortend && isRemovable(SI) && + State.storeIsNoop(KillingDef, SILoc, SILocUnd)) { + LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n DEAD: " << *SI << '\n'); + State.deleteDeadInstruction(SI); + NumRedundantStores++; + MadeChange = true; + continue; + } } if (EnablePartialOverwriteTracking) diff --git a/llvm/test/Transforms/DeadStoreElimination/MSSA/calloc-store.ll b/llvm/test/Transforms/DeadStoreElimination/MSSA/calloc-store.ll index ddb10d7..830d20f 100644 --- a/llvm/test/Transforms/DeadStoreElimination/MSSA/calloc-store.ll +++ b/llvm/test/Transforms/DeadStoreElimination/MSSA/calloc-store.ll @@ -114,13 +114,9 @@ define i8* @test10() { ret i8* %p } -; TODO: we could also eliminate the last store i8 0, i8* %p.3.2, but currently -; don't because those are eliminated before eliminating killed stores. define i8* @test11() { ; CHECK-LABEL: @test11( ; CHECK-NEXT: [[P:%.*]] = tail call noalias i8* @calloc(i64 1, i64 4) -; CHECK-NEXT: [[P_3_2:%.*]] = getelementptr i8, i8* [[P]], i32 3 -; CHECK-NEXT: store i8 0, i8* [[P_3_2]], align 1 ; CHECK-NEXT: ret i8* [[P]] ; diff --git a/llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll b/llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll index 97fa988..ec407a9 100644 --- a/llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll +++ b/llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll @@ -208,8 +208,6 @@ define void @test44(i32* %Q) { define void @test45(i32* %Q) { ; CHECK-LABEL: @test45( -; CHECK-NEXT: [[A:%.*]] = load i32, i32* [[Q:%.*]], align 4 -; CHECK-NEXT: store i32 [[A]], i32* [[Q]], align 4 ; CHECK-NEXT: ret void ; %a = load i32, i32* %Q @@ -252,16 +250,13 @@ bb2: ret i32 0 } -; TODO: Remove both redundant stores if loaded value is in another block inside a loop. define i32 @test47(i1 %c, i32* %p, i32 %i) { ; CHECK-LABEL: @test47( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[V:%.*]] = load i32, i32* [[P:%.*]], align 4 ; CHECK-NEXT: br label [[BB1:%.*]] ; CHECK: bb1: ; CHECK-NEXT: br i1 [[C:%.*]], label [[BB1]], label [[BB2:%.*]] ; CHECK: bb2: -; CHECK-NEXT: store i32 [[V]], i32* [[P]], align 4 ; CHECK-NEXT: br i1 [[C]], label [[BB3:%.*]], label [[BB1]] ; CHECK: bb3: ; CHECK-NEXT: ret i32 0 @@ -299,9 +294,7 @@ entry: define void @test_noalias_store_between_load_and_store_elimin_order(i32* noalias %x, i32* noalias %y) { ; CHECK-LABEL: @test_noalias_store_between_load_and_store_elimin_order( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[LV:%.*]] = load i32, i32* [[X:%.*]], align 4 ; CHECK-NEXT: store i32 0, i32* [[Y:%.*]], align 4 -; CHECK-NEXT: store i32 [[LV]], i32* [[X]], align 4 ; CHECK-NEXT: ret void ; entry: -- 2.7.4