[DSE] Fix a case of invalid dead store elimination

[mamai]

Summary

Fix isGuaranteedLoopInvariant() check for invariance. The checks for alloca and alloc-like instructions was not valid when the 'KillingDef' was outside of the loop, while the 'CurrentDef' was inside the loop. In that case, the 'KillingDef' only overwrites the definition from the last iteration of the loop, and not the ones of all iterations, therefor it does not make the 'CurrentDef' to be dead.

Fixing issue : https://github.com/llvm/llvm-project/issues/52774

[nikic]

From a cursory look, isn't the actual problem here that the malloc() is treated as loop invariant, even though it isn't?

[mamai]

In D115965#3200873, @nikic wrote:

From a cursory look, isn't the actual problem here that the malloc() is treated as loop invariant, even though it isn't?

Maybe. What I had been told was that this code was not really looking at invariance but at cross iteration dependencies.

[mamai]

I realized I didn't ran the tests correctly when I ran it locally, and my patch was breaking a lot of tests. I have modified the patch to not affect the code stores that are not in loops.

[fhahn]

Thanks for the patch!

In D115965#3202681, @mamai wrote:

In D115965#3200873, @nikic wrote:

From a cursory look, isn't the actual problem here that the malloc() is treated as loop invariant, even though it isn't?

Maybe. What I had been told was that this code was not really looking at invariance but at cross iteration dependencies.

I originally made the comment about cross-iteration-dependencies (in the same loop), but that was before I had a look at the full test case and the actual problem.

It looks like our handling of alloca/alloc-like instructions is not correct (as @mamai mentioned in Discord as well). Instead of the current check, we should probably just check whether the object is defined in the entry block for now:

   /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
   /// loop. In particular, this guarantees that it only references a single
   /// MemoryLocation during execution of the containing function.
   bool isGuaranteedLoopInvariant(const Value *Ptr) {
-    auto IsGuaranteedLoopInvariantBase = [this](const Value *Ptr) {
+    auto IsGuaranteedLoopInvariantBase = [](const Value *Ptr) {
       Ptr = Ptr->stripPointerCasts();
-      if (auto *I = dyn_cast<Instruction>(Ptr)) {
-        if (isa<AllocaInst>(Ptr))
-          return true;
-
-        if (isAllocLikeFn(I, &TLI))
-          return true;
-
-        return false;
-      }
+      if (auto *I = dyn_cast<Instruction>(Ptr))
+        return I->getParent() == &I->getFunction()->getEntryBlock();
       return true;
     };

llvm/test/Transforms/DeadStoreElimination/store-after-loop.ll

1

please use the new pass manager syntax (-passes=dse)

22

nit: no need for dse_local or the attributes.

26

imo it would make reading the test easier if that was between %loop1 and %loop2.

33

nit: imo it would improve readability if the values would be explicitly named with descriptive names, .e.g %iv this one and iv.next for %13 and so on.

38

This doesn't seem necessary for the test. Could we just set the field to a constant?

48

Can this loop be simplified so it doesn't need 2 pointer phis? The problem should also be exposed with an integer induction, as long as we use a pointer based on %6?

58

This function should probably return a pointer to the list, otherwise the memory is not used and the stores are practically dead?

62

nit: no need for dso_local.

65

nit: only retain the attributes needed for DSE to treat malloc as 'alloc-like'

66

not used?

[mamai]

Thanks @fhahn for your suggestions. I modified both the fix and test case as suggested. I tried to make the testcase as concise and readable as possible while still showing the issue.

[fhahn]

Thanks for the update! After addressing the final comments for the test, could you pre-commit the test (with check lines generated using llvm/utils/update_test_checks.py and then update this patch to just show the impact of your fix?

llvm/test/Transforms/DeadStoreElimination/store-after-loop.ll

7

Could you also reference the bug report as PR52774? Could also be included in the file name.

9

This is a case where auto-generating the check lines with llvm/utils/update_test_checks.py would be helpful.

43

nit: this is not a loop any more :)

Also, this probably doesn't need to be in separate BB.

[mamai]

In D115965#3206891, @fhahn wrote:

Thanks for the update! After addressing the final comments for the test, could you pre-commit the test (with check lines generated using llvm/utils/update_test_checks.py and then update this patch to just show the impact of your fix?

Do you mean making a first commit with the test case (with the store missing, so that it pass) and the this patch will contain the fix and add the missing store in the test case ?

[fhahn]

In D115965#3206906, @mamai wrote:

In D115965#3206891, @fhahn wrote:

Thanks for the update! After addressing the final comments for the test, could you pre-commit the test (with check lines generated using llvm/utils/update_test_checks.py and then update this patch to just show the impact of your fix?

Do you mean making a first commit with the test case (with the store missing, so that it pass) and the this patch will contain the fix and add the missing store in the test case ?

exactly

[mamai]

I pre-commited the test case and rebased this patch on it (https://github.com/llvm/llvm-project/commit/df590567aa435211dea1f306b55b8d4ba92ddbb1)

[fhahn]

LGTM, thanks!

It would be good to make the title/commit message a bit more descriptive

Instead of

[DSE] Fix a case of invalid dead store elimination

perhaps something like '[DSE] Fix handling of alloc-like instructions in isGuaranteedLoopInvariant`?

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1215

The code structure in this function no longer makes sense. Please rewrite the whole function to first strip offsets / GEP and then do a single entry block check.

[mamai]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1215

Sorry, I just saw your comment after comiting. I could change it, but should I open a new differential for that ?

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1215

It's probably easiest to just put up a new review with the requested changes

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

bool isGuaranteedLoopIndependent(const Instruction *Current,
     // Otherwise check the memory location is invariant to any loops.
     return isGuaranteedLoopInvariant(CurrentLoc.Ptr);
   }
 
   /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
   /// loop. In particular, this guarantees that it only references a single
   /// MemoryLocation during execution of the containing function.
   bool isGuaranteedLoopInvariant(const Value *Ptr) {
-    auto IsGuaranteedLoopInvariantBase = [this](const Value *Ptr) {
+    auto IsGuaranteedLoopInvariantBase = [](const Value *Ptr) {
       Ptr = Ptr->stripPointerCasts();
-      if (auto *I = dyn_cast<Instruction>(Ptr)) {
-        if (isa<AllocaInst>(Ptr))
-          return true;
-
-        if (isAllocLikeFn(I, &TLI))
-          return true;
-
-        return false;
-      }
+      if (auto *I = dyn_cast<Instruction>(Ptr))
+        return I->getParent()->isEntryBlock();
       return true;
     };
 
     Ptr = Ptr->stripPointerCasts();
     if (auto *I = dyn_cast<Instruction>(Ptr)) {
       if (I->getParent()->isEntryBlock())
         return true;
     }

llvm/test/Transforms/DeadStoreElimination/store-after-loop.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=dse -S | FileCheck %s
 
 target datalayout = "E-m:e-p:32:32-i64:32-f64:32:64-a:0:32-n32-S32"
 
 %struct.ilist = type { i32, %struct.ilist* }
 
 ; There is no dead store in this test. Make sure no store is deleted by DSE.
 ; Test case related to bug report PR52774.
-; NOTE: Showing actual (broken) DSE behavior.
 
 define %struct.ilist* @test() {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[TMP0:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[LIST_NEXT:%.*]] = phi %struct.ilist* [ null, [[TMP0]] ], [ [[LIST_NEW_ILIST_PTR:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[LIST_NEW_I8_PTR:%.*]] = tail call align 8 dereferenceable_or_null(8) i8* @malloc(i32 8)
 ; CHECK-NEXT:    [[LIST_NEW_ILIST_PTR]] = bitcast i8* [[LIST_NEW_I8_PTR]] to %struct.ilist*
 ; CHECK-NEXT:    [[GEP_NEW_VALUE:%.*]] = getelementptr inbounds [[STRUCT_ILIST:%.*]], %struct.ilist* [[LIST_NEW_ILIST_PTR]], i32 0, i32 0
 ; CHECK-NEXT:    store i32 42, i32* [[GEP_NEW_VALUE]], align 8
+; CHECK-NEXT:    [[GEP_NEW_NEXT:%.*]] = getelementptr inbounds [[STRUCT_ILIST]], %struct.ilist* [[LIST_NEW_ILIST_PTR]], i32 0, i32 1
+; CHECK-NEXT:    store %struct.ilist* [[LIST_NEXT]], %struct.ilist** [[GEP_NEW_NEXT]], align 4
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[IV_NEXT]], 10
 ; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[LIST_LAST_ILIST_PTR:%.*]] = bitcast i8* [[LIST_NEW_I8_PTR]] to %struct.ilist*
 ; CHECK-NEXT:    [[GEP_LIST_LAST_NEXT:%.*]] = getelementptr inbounds [[STRUCT_ILIST]], %struct.ilist* [[LIST_LAST_ILIST_PTR]], i32 0, i32 1
 ; CHECK-NEXT:    store %struct.ilist* null, %struct.ilist** [[GEP_LIST_LAST_NEXT]], align 4
 ; CHECK-NEXT:    [[GEP_LIST_NEXT_NEXT:%.*]] = getelementptr inbounds [[STRUCT_ILIST]], %struct.ilist* [[LIST_NEXT]], i32 0, i32 1
 ; CHECK-NEXT:    [[LOADED_PTR:%.*]] = load %struct.ilist*, %struct.ilist** [[GEP_LIST_NEXT_NEXT]], align 4
 ; CHECK-NEXT:    ret %struct.ilist* [[LOADED_PTR]]
 ;
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %0 ], [ %iv.next, %loop ]
   %list.next = phi %struct.ilist* [ null, %0 ], [ %list.new.ilist.ptr, %loop ]
   %list.new.i8.ptr = tail call align 8 dereferenceable_or_null(8) i8* @malloc(i32 8)
   %list.new.ilist.ptr = bitcast i8* %list.new.i8.ptr to %struct.ilist*
   %gep.new.value = getelementptr inbounds %struct.ilist, %struct.ilist* %list.new.ilist.ptr, i32 0, i32 0
   store i32 42, i32* %gep.new.value, align 8
   %gep.new.next = getelementptr inbounds %struct.ilist, %struct.ilist* %list.new.ilist.ptr, i32 0, i32 1
   store %struct.ilist* %list.next, %struct.ilist** %gep.new.next, align 4
   %iv.next = add nuw nsw i32 %iv, 1
   %cond = icmp eq i32 %iv.next, 10
   br i1 %cond, label %exit, label %loop
 
 exit:
   %list.last.ilist.ptr = bitcast i8* %list.new.i8.ptr to %struct.ilist*
   %gep.list.last.next = getelementptr inbounds %struct.ilist, %struct.ilist* %list.last.ilist.ptr, i32 0, i32 1
   store %struct.ilist* null, %struct.ilist** %gep.list.last.next, align 4
   %gep.list.next.next = getelementptr inbounds %struct.ilist, %struct.ilist* %list.next, i32 0, i32 1
   %loaded_ptr = load %struct.ilist*, %struct.ilist** %gep.list.next.next, align 4
   ret %struct.ilist* %loaded_ptr                                      ; use loaded pointer
 }
 
 ; Function Attrs: inaccessiblememonly nounwind
 declare noalias noundef align 8 i8* @malloc(i32 noundef) local_unnamed_addr #0
 
 attributes #0 = { inaccessiblememonly nounwind}