[DSE] Extending IsGuaranteedLoopInvariant to support a GetElementPtrInst defined in the entry block

[fvrmatteo]

Summary

The IsGuaranteedLoopInvariant function is making sure to check if the incoming pointer is guaranteed to be loop invariant, therefore I think the case where the pointer is defined in the entry block of a function automatically guarantees the pointer to be loop invariant, as the entry block of a function cannot have predecessors or be part of a loop.

I implemented this small patch and tested it using ninja check-llvm-unit and ninja check-llvm. I added a contained test file that shows the problem and used opt -O3 -debug on it to make sure the case is not currently handled (in fact the debug log is showing that the DSE pass is bailing out when testing if the killer store is able to clobber the dead store).

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1920

this is not really GEP specific right? Any instruction in the entry block should be loop invariant.

[fvrmatteo]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1920

You are right, I could rewrite the lambda as IsEntryBlockInstruction to do a check on the Ptr (simply casting it to llvm::Instruction and checking if it's part of the entry block) and do that as the really first check of the IsGuaranteedLoopInvariantBase function. WDYT?

[fvrmatteo]

I tried to update the patch to execute the entry block check on the incoming pointer (if it's an instruction) as first thing in the IsGuaranteedLoopInvariant function.

[fhahn]

LGTM, thanks!

There's similar logic in MemorySSA.cpp we should unify.

llvm/test/Transforms/DeadStoreElimination/MSSA/loop-invariant-entry-block.ll

7

can you add a comment describing what is tests here?

[fvrmatteo]

Added an explanation to the test file.

[fvrmatteo]

@fhahn I verified the similar logic in MemorySSA.cpp, but I think the unification should be part of a different patch, right? Should we try to come up with a single function that we can call both from MemorySSA.cpp and DeadStoreElimination.cpp or should we keep them separated but semantically equivalent (therefore porting this addition to the MemorySSA.cpp version of the function)?

[fhahn]

In D96979#2576543, @fvrmatteo wrote:

@fhahn I verified the similar logic in MemorySSA.cpp, but I think the unification should be part of a different patch, right?

Yep, the current patch can be submitted as is.

Should we try to come up with a single function that we can call both from MemorySSA.cpp and DeadStoreElimination.cpp or should we keep them separated but semantically equivalent (therefore porting this addition to the MemorySSA.cpp version of the function)?

I think we should be able to use the same function for both. It would probably be easiest to make this accessible through MemorySSA.h. It's not directly MemorySSA related, but I'm not sure if there's a more suitable place.

[fhahn]

Please let me know if you need someone to land this change on your behalf & the name + email that should be used for attribution.

[fvrmatteo]

In D96979#2579928, @fhahn wrote:

Please let me know if you need someone to land this change on your behalf & the name + email that should be used for attribution.

Sorry for the delay, I didn't know how this worked, thought it would be committed automatically by the system.

I don't have a way to land this change, so I guess the name (Matteo Favaro) and email (fvrmatteo at gmail.com) should be fine.

Thanks a lot for following me on this, I'll try to use Arcanist next time if it makes things easier.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

auto IsGuaranteedLoopInvariantBase = [this](Value *Ptr) {
           return true;
 
         return false;
       }
       return true;
     };
 
     Ptr = Ptr->stripPointerCasts();
+    if (auto *I = dyn_cast<Instruction>(Ptr)) {
+      if (I->getParent() == &I->getFunction()->getEntryBlock()) {
+        return true;
+      }
+    }
     if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
       return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
              GEP->hasAllConstantIndices();
     }
     return IsGuaranteedLoopInvariantBase(Ptr);
   }
 
   // Find a MemoryDef writing to \p DefLoc and dominating \p StartAccess, with
   // no read access between them or on any other path to a function exit block
   // if \p DefLoc is not accessible after the function returns. If there is no

llvm/test/Transforms/DeadStoreElimination/MSSA/loop-invariant-entry-block.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -dse -S | FileCheck %s
+
+@BUFFER = external dso_local local_unnamed_addr global [0 x i8], align 1
+
+define void @MissedDSEOpportunity(i64 %idx, i1* noalias %cc) {
+;
+; The DSE pass will try to kill the store in the loop exit block using the
+; store in the function exit block. The loop invariant check on the pointer
+; used by the stores should trivially return true because a pointer defined
+; in the entry block of a function is loop invariant by definition. In fact
+; the entry block of a function cannot have predecessors or be part of a loop.
+;
+; CHECK-LABEL: @MissedDSEOpportunity(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds [0 x i8], [0 x i8]* @BUFFER, i64 0, i64 [[IDX:%.*]]
+; CHECK-NEXT:    [[BC:%.*]] = bitcast i8* [[GEP]] to i64*
+; CHECK-NEXT:    [[CC0:%.*]] = load volatile i1, i1* [[CC:%.*]], align 1
+; CHECK-NEXT:    br i1 [[CC0]], label [[HEAD:%.*]], label [[EXIT:%.*]]
+; CHECK:       head:
+; CHECK-NEXT:    [[CC1:%.*]] = load volatile i1, i1* [[CC]], align 1
+; CHECK-NEXT:    br i1 [[CC1]], label [[HEAD]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    store i64 0, i64* [[BC]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  ; The entry block cannot have predecessors or be part of a loop
+  %gep = getelementptr inbounds [0 x i8], [0 x i8]* @BUFFER, i64 0, i64 %idx
+  %bc = bitcast i8* %gep to i64*
+  %cc0 = load volatile i1, i1* %cc, align 1
+  br i1 %cc0, label %head, label %exit
+
+head:                                             ; preds = %entry, %head
+  %cc1 = load volatile i1, i1* %cc, align 1
+  br i1 %cc1, label %head, label %exit.loopexit
+
+exit.loopexit:                                    ; preds = %head
+  ; Dead store
+  store i64 2, i64* %bc, align 4
+  br label %exit
+
+exit:                                             ; preds = %exit.loopexit, %entry
+  ; Killer store
+  store i64 0, i64* %bc, align 4
+  ret void
+}
 No newline at end of file