diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp --- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -2398,10 +2398,42 @@ if (auto *LoadI = dyn_cast(Store->getOperand(0))) { if (LoadI->getPointerOperand() == Store->getOperand(1)) { + // Get the defining access for the load. auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess(); - // If both accesses share the same defining access, no instructions - // between them can modify the memory location. - return LoadAccess == Def->getDefiningAccess(); + // Fast path: the defining accesses are the same. + if (LoadAccess == Def->getDefiningAccess()) + return true; + + // Look through phi accesses. Recursively scan all phi accesses by adding them + // to a worklist. Bail when we run into a memory def. + SetVector ToCheck; + MemoryAccess *Current = Def->getDefiningAccess(); + // We don't want to bail when we run into the store memory def. But, the phi + // access may point to it. So, pretend like we've already checked it. + ToCheck.insert(Def); + ToCheck.insert(Current); + // Start at current (1) to simulate already having checked Def. + for (unsigned I = 1; I < ToCheck.size(); ++I) { + Current = ToCheck[I]; + if (auto PhiAccess = dyn_cast(Current)) { + // Check all the operands. + for (auto &Use : PhiAccess->incoming_values()) + ToCheck.insert(cast(&Use)); + continue; + } + + // If we found a memory def, bail. This happens when we have an unrelated + // write in between an otherwise noop store. + if (isa(Current)) { + // TODO: Skip no alias MemoryDefs that have no aliasing reads. + // We are searching for the definition of the store's destination. + // So, if that is the same definition as the load, then this is a + // noop. Otherwise, fail. + if (LoadAccess != Current) + return false; + } + } + return true; } } diff --git a/llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll b/llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll --- a/llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll +++ b/llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll @@ -101,6 +101,47 @@ ret i32 0 } +; Remove redundant store if loaded value is in another block inside a loop. +define i32 @test31(i1 %c, i32* %p, i32 %i) { +; CHECK-LABEL: @test31( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[BB1:%.*]] +; CHECK: bb1: +; CHECK-NEXT: br i1 [[C:%.*]], label [[BB1]], label [[BB2:%.*]] +; CHECK: bb2: +; CHECK-NEXT: ret i32 0 +; +entry: + %v = load i32, i32* %p, align 4 + br label %bb1 +bb1: + store i32 %v, i32* %p, align 4 + br i1 %c, label %bb1, label %bb2 +bb2: + ret i32 0 +} + +; Don't remove "redundant" store if %p is possibly stored to. +define i32 @test46(i1 %c, i32* %p, i32* %p2, i32 %i) { +; CHECK-LABEL: @test46( +; CHECK: load +; CHECK: store +; CHECK: store +; CHECK: ret i32 0 +; +entry: + %v = load i32, i32* %p, align 4 + br label %bb1 +bb1: + store i32 %v, i32* %p, align 4 + br i1 %c, label %bb1, label %bb2 +bb2: + store i32 0, i32* %p2, align 4 + br i1 %c, label %bb3, label %bb1 +bb3: + ret i32 0 +} + declare void @unknown_func() ; Remove redundant store, which is in the lame loop as the load. @@ -112,7 +153,7 @@ ; CHECK-NEXT: br label [[BB2:%.*]] ; CHECK: bb2: ; CHECK-NEXT: call void @unknown_func() -; CHECK-NEXT: br i1 undef, label [[BB1]], label [[BB3:%.*]] +; CHECK-NEXT: br i1 [[C:%.*]], label [[BB1]], label [[BB3:%.*]] ; CHECK: bb3: ; CHECK-NEXT: ret i32 0 ; @@ -125,7 +166,7 @@ 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 + br i1 %c, label %bb1, label %bb3 bb3: ret i32 0 } @@ -168,4 +209,52 @@ ret void } +define i32 @test48(i1 %c, i32* %p) { +; CHECK-LABEL: @test48( +; CHECK: entry: +; CHECK-NEXT: [[V:%.*]] = load +; CHECK: store i32 0 +; CHECK: store i32 [[V]] +; CHECK: ret i32 0 +entry: + %v = load i32, i32* %p, align 4 + br i1 %c, label %bb0, label %bb0.0 + +bb0: + store i32 0, i32* %p + br i1 %c, label %bb1, label %bb2 + +bb0.0: + br label %bb1 + +bb1: + store i32 %v, i32* %p, align 4 + br i1 %c, label %bb2, label %bb0 +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) { +; X-CHECK-LABEL: @test47( +; X-CHECK-NEXT: entry: +; X-CHECK-NEXT: br label [[BB1:%.*]] +; X-CHECK: bb1: +; X-CHECK-NEXT: br i1 [[C:%.*]], label [[BB1]], label [[BB2:%.*]] +; X-CHECK: bb2: +; X-CHECK-NEXT: br i1 [[C]], label [[BB2]], label [[BB3:%.*]] +; X-CHECK: bb3: +; X-CHECK-NEXT: ret i32 0 +entry: + %v = load i32, i32* %p, align 4 + br label %bb1 +bb1: + store i32 %v, i32* %p, align 4 + br i1 %c, label %bb1, label %bb2 +bb2: + store i32 %v, i32* %p, align 4 + br i1 %c, label %bb3, label %bb1 +bb3: + ret i32 0 +} diff --git a/llvm/test/Transforms/DeadStoreElimination/MSSA/simple-todo.ll b/llvm/test/Transforms/DeadStoreElimination/MSSA/simple-todo.ll deleted file mode 100644 --- a/llvm/test/Transforms/DeadStoreElimination/MSSA/simple-todo.ll +++ /dev/null @@ -1,25 +0,0 @@ -; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; XFAIL: * -; RUN: opt < %s -basic-aa -dse -S | FileCheck %s -; RUN: opt < %s -aa-pipeline=basic-aa -passes=dse -S | FileCheck %s -target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128" - -; Remove redundant store if loaded value is in another block inside a loop. -define i32 @test31(i1 %c, i32* %p, i32 %i) { -; CHECK-LABEL: @test31( -; CHECK-NEXT: entry: -; CHECK-NEXT: br label [[BB1:%.*]] -; CHECK: bb1: -; CHECK-NEXT: br i1 undef, label [[BB1]], label [[BB2:%.*]] -; CHECK: bb2: -; CHECK-NEXT: ret i32 0 -; -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 -}