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 @@ -1075,16 +1075,22 @@ } MemoryAccess *UseAccess = WorkList[I]; - // Simply adding the users of MemoryPhi to the worklist is not enough, - // because we might miss read clobbers in different iterations of a loop, - // for example. - // TODO: Add support for phi translation to handle the loop case. - if (isa(UseAccess)) + if (isa(UseAccess)) { + PushMemUses(cast(UseAccess)); + continue; + } + Instruction *UseInst = cast(UseAccess)->getMemoryInst(); + // AliasAnalysis does not account for loops. Limit elimination to + // candidates for which we can guarantee they always store to the same + // memory location and not located in different loops. + if (!isGuaranteedLoopIndependent(UseInst, Def->getMemoryInst(), + *MaybeLoc)) { + LLVM_DEBUG(dbgs() << " ... not guaranteed loop independent\n"); return false; + } // TODO: Checking for aliasing is expensive. Consider reducing the amount // of times this is called and/or caching it. - Instruction *UseInst = cast(UseAccess)->getMemoryInst(); if (isReadClobber(*MaybeLoc, UseInst)) { LLVM_DEBUG(dbgs() << " ... hit read clobber " << *UseInst << ".\n"); return false; diff --git a/llvm/test/Transforms/DeadStoreElimination/multiblock-loop-carried-dependence.ll b/llvm/test/Transforms/DeadStoreElimination/multiblock-loop-carried-dependence.ll --- a/llvm/test/Transforms/DeadStoreElimination/multiblock-loop-carried-dependence.ll +++ b/llvm/test/Transforms/DeadStoreElimination/multiblock-loop-carried-dependence.ll @@ -29,9 +29,6 @@ ; CHECK-NEXT: [[PTR_IV_2:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[IV_2]] ; CHECK-NEXT: [[L_0:%.*]] = load i32, i32* [[PTR_IV_2]], align 4 ; CHECK-NEXT: call void @use(i32 [[L_0]]) -; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[IV_2]], 1 -; CHECK-NEXT: [[PTR_IV_2_ADD_1:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[ADD]] -; CHECK-NEXT: store i32 10, i32* [[PTR_IV_2_ADD_1]], align 4 ; CHECK-NEXT: [[L_1:%.*]] = load i32, i32* [[PTR_IV_2]], align 4 ; CHECK-NEXT: call void @use(i32 [[L_1]]) ; CHECK-NEXT: [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 1 diff --git a/llvm/test/Transforms/DeadStoreElimination/multiblock-malloc-free.ll b/llvm/test/Transforms/DeadStoreElimination/multiblock-malloc-free.ll --- a/llvm/test/Transforms/DeadStoreElimination/multiblock-malloc-free.ll +++ b/llvm/test/Transforms/DeadStoreElimination/multiblock-malloc-free.ll @@ -180,7 +180,6 @@ ; CHECK-NEXT: br i1 true, label [[BB2:%.*]], label [[BB3:%.*]] ; CHECK: bb2: ; CHECK-NEXT: [[M:%.*]] = call noalias i8* @malloc(i64 10) -; CHECK-NEXT: store i8 1, i8* [[M]], align 1 ; CHECK-NEXT: br label [[BB3]] ; CHECK: bb3: ; CHECK-NEXT: [[R:%.*]] = phi i8* [ null, [[BB1:%.*]] ], [ [[M]], [[BB2]] ] diff --git a/llvm/test/Transforms/DeadStoreElimination/multiblock-memintrinsics.ll b/llvm/test/Transforms/DeadStoreElimination/multiblock-memintrinsics.ll --- a/llvm/test/Transforms/DeadStoreElimination/multiblock-memintrinsics.ll +++ b/llvm/test/Transforms/DeadStoreElimination/multiblock-memintrinsics.ll @@ -138,8 +138,6 @@ ; CHECK: bb1: ; CHECK-NEXT: br label [[BB3:%.*]] ; CHECK: bb2: -; CHECK-NEXT: [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1 -; CHECK-NEXT: store i32 1, i32* [[ARRAYIDX1]], align 4 ; CHECK-NEXT: br label [[BB3]] ; CHECK: bb3: ; CHECK-NEXT: ret void @@ -177,12 +175,8 @@ ; CHECK-NEXT: call void @readonly_use(i32* [[P]]) ; CHECK-NEXT: br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]] ; CHECK: bb1: -; CHECK-NEXT: [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1 -; CHECK-NEXT: store i32 1, i32* [[ARRAYIDX1]], align 4 ; CHECK-NEXT: br label [[BB3:%.*]] ; CHECK: bb2: -; CHECK-NEXT: [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1 -; CHECK-NEXT: store i32 1, i32* [[ARRAYIDX2]], align 4 ; CHECK-NEXT: br label [[BB3]] ; CHECK: bb3: ; CHECK-NEXT: ret void diff --git a/llvm/test/Transforms/DeadStoreElimination/phi-translation.ll b/llvm/test/Transforms/DeadStoreElimination/phi-translation.ll --- a/llvm/test/Transforms/DeadStoreElimination/phi-translation.ll +++ b/llvm/test/Transforms/DeadStoreElimination/phi-translation.ll @@ -1,7 +1,7 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -dse -S %s | FileCheck %s -; TODO: Both the stores in %then and %else can be eliminated by translating %p +; Both the stores in %then and %else can be eliminated by translating %p ; through the phi. define void @memoryphi_translate_1(i1 %c) { ; CHECK-LABEL: @memoryphi_translate_1( @@ -10,10 +10,8 @@ ; CHECK-NEXT: [[A_2:%.*]] = alloca i8, align 1 ; CHECK-NEXT: br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: -; CHECK-NEXT: store i8 0, i8* [[A_1]], align 1 ; CHECK-NEXT: br label [[END:%.*]] ; CHECK: else: -; CHECK-NEXT: store i8 9, i8* [[A_2]], align 1 ; CHECK-NEXT: br label [[END]] ; CHECK: end: ; CHECK-NEXT: [[P:%.*]] = phi i8* [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ] @@ -39,7 +37,7 @@ ret void } -; TODO: The store in %else can be eliminated by translating %p through the phi. +; The store in %else can be eliminated by translating %p through the phi. ; The store in %then cannot be eliminated, because %a.1 is read before the final ; store. define i8 @memoryphi_translate_2(i1 %c) { @@ -52,7 +50,6 @@ ; CHECK-NEXT: store i8 0, i8* [[A_1]], align 1 ; CHECK-NEXT: br label [[END:%.*]] ; CHECK: else: -; CHECK-NEXT: store i8 9, i8* [[A_2]], align 1 ; CHECK-NEXT: br label [[END]] ; CHECK: end: ; CHECK-NEXT: [[P:%.*]] = phi i8* [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ] @@ -80,7 +77,7 @@ ret i8 %l } -; TODO: The store in %then can be eliminated by translating %p through the phi. +; The store in %then can be eliminated by translating %p through the phi. ; The store in %else cannot be eliminated, because %a.2 is read before the final ; store. define i8 @memoryphi_translate_3(i1 %c) { @@ -90,7 +87,6 @@ ; CHECK-NEXT: [[A_2:%.*]] = alloca i8, align 1 ; CHECK-NEXT: br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: -; CHECK-NEXT: store i8 0, i8* [[A_1]], align 1 ; CHECK-NEXT: br label [[END:%.*]] ; CHECK: else: ; CHECK-NEXT: store i8 9, i8* [[A_2]], align 1 @@ -166,11 +162,9 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: [[A:%.*]] = alloca i8, align 1 ; CHECK-NEXT: [[B:%.*]] = alloca i8, align 1 -; CHECK-NEXT: [[C:%.*]] = alloca i8, align 1 ; CHECK-NEXT: store i8 0, i8* [[A]], align 1 ; CHECK-NEXT: br i1 [[COND:%.*]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]] ; CHECK: cond.true: -; CHECK-NEXT: store i8 0, i8* [[C]], align 1 ; CHECK-NEXT: br label [[COND_END]] ; CHECK: cond.end: ; CHECK-NEXT: [[P:%.*]] = phi i8* [ [[B]], [[COND_TRUE]] ], [ [[A]], [[ENTRY:%.*]] ]