[DSE][NFC] Introduce "doesn't overwrite" return code for isOverwrite

[ebrevnov]

Summary

Add OR_None code to indicate that there is no overwrite. This has no any effect for current uses but will be used in one of the next patches building support for PHI translation.

[xbolva00]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1057–1058

Adjust comment

[ebrevnov]

Fixed comments + formatting

[ebrevnov]

Minor update

[ebrevnov]

Ping...

[ebrevnov]

Rebase

[ebrevnov]

Ping

[fhahn]

Looks good in general, but I couldn't find a use in the linked patches. Could you update the description with more details about the motivation, when/how this will be used.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1457

The comment here seems slightly inaccurate and I think it is more obvious after this change; we skip if we can't prove that there is a (partial) overwrite. Might be good to adjust the comment.

1468

This seems unrelated to the patch?

[ebrevnov]

In D105098#2984988, @fhahn wrote:

Looks good in general, but I couldn't find a use in the linked patches. Could you update the description with more details about the motivation, when/how this will be used.

The thing is that I had to remove depending changes from the list since I didn't manage to come up with a regression test. Looks like it is not that critical and we can return to it once main functionality settles down. So let's skip this one for now as well if you don't mind :-)

[fhahn]

In D105098#2986088, @ebrevnov wrote:

In D105098#2984988, @fhahn wrote:

Looks good in general, but I couldn't find a use in the linked patches. Could you update the description with more details about the motivation, when/how this will be used.

The thing is that I had to remove depending changes from the list since I didn't manage to come up with a regression test. Looks like it is not that critical and we can return to it once main functionality settles down. So let's skip this one for now as well if you don't mind :-)

Sounds good to me. Marking as changes requested so it is gone from the review queue for now.

[fhahn]

In D105098#3005755, @fhahn wrote:

In D105098#2986088, @ebrevnov wrote:

In D105098#2984988, @fhahn wrote:

Looks good in general, but I couldn't find a use in the linked patches. Could you update the description with more details about the motivation, when/how this will be used.

The thing is that I had to remove depending changes from the list since I didn't manage to come up with a regression test. Looks like it is not that critical and we can return to it once main functionality settles down. So let's skip this one for now as well if you don't mind :-)

Sounds good to me. Marking as changes requested so it is gone from the review queue for now.

I've encountered another case where OW_None would be helpful: D112313.

@ebrevnov I think it would be very useful to get this patch in soonish to unblock D112313 & following. I put up a variation of this patch as D112312 with a small addition: returning OW_None if both accesses do not alias. It would be good to include those here as well.

[fhahn]

reverse ping :)

[ebrevnov]

Merge with D112312

[fhahn]

LGTM, thanks!

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 //===- DeadStoreElimination.cpp - MemorySSA Backed Dead Store Elimination -===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // The code below implements dead store elimination using MemorySSA. It uses

 namespace {
 
 enum OverwriteResult {
   OW_Begin,
   OW_Complete,
   OW_End,
   OW_PartialEarlierWithFullLater,
   OW_MaybePartial,
+  OW_None,
   OW_Unknown
 };
 
 } // end anonymous namespace
 
 /// Check if two instruction are masked stores that completely
 /// overwrite one another. More specifically, \p Later has to
 /// overwrite \p Earlier.
struct DSEState {
   }
 
   /// Return 'OW_Complete' if a store to the 'Later' location (by \p LaterI
   /// instruction) completely overwrites a store to the 'Earlier' location.
   /// (by \p EarlierI instruction).
   /// Return OW_MaybePartial if \p Later does not completely overwrite
   /// \p Earlier, but they both write to the same underlying object. In that
   /// case, use isPartialOverwrite to check if \p Later partially overwrites
-  /// \p Earlier. Returns 'OW_Unknown' if nothing can be determined.
+  /// \p Earlier. Returns 'OR_None' if later is known to not overwrite the
+  /// earlier. 'OW_Unknown' if nothing can be determined.
   OverwriteResult
   isOverwrite(const Instruction *LaterI, const Instruction *EarlierI,
               const MemoryLocation &Later, const MemoryLocation &Earlier,
               int64_t &EarlierOff, int64_t &LaterOff) {
     // AliasAnalysis does not always account for loops. Limit overwrite checks
     // to dependencies for which we can guarantee they are independant of any
     // loops they are in.
     if (!isGuaranteedLoopIndependent(EarlierI, LaterI, Earlier))
if (EarlierOff >= LaterOff) {
       else if ((uint64_t)(EarlierOff - LaterOff) < LaterSize)
         return OW_MaybePartial;
     }
     // If start of the later access is "before" end of the earlier access then
     // accesses overlap.
     else if ((uint64_t)(LaterOff - EarlierOff) < EarlierSize) {
       return OW_MaybePartial;
     }
 
-    // Can reach here only if accesses are known not to overlap. There is no
-    // dedicated code to indicate no overlap so signal "unknown".
-    return OW_Unknown;
+    // Can reach here only if accesses are known not to overlap.
+    return OW_None;
   }
 
   bool isInvisibleToCallerAfterRet(const Value *V) {
     if (isa<AllocaInst>(V))
       return true;
     auto I = InvisibleToCallerAfterRet.insert({V, false});
     if (I.second) {
       if (!isInvisibleToCallerBeforeRet(V)) {
for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
         // the next candidate if the current Current does not write the same
         // underlying object as the terminator.
         if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI))
           continue;
       } else {
         int64_t InstWriteOffset, DepWriteOffset;
         auto OR = isOverwrite(KillingI, CurrentI, DefLoc, *CurrentLoc,
                               DepWriteOffset, InstWriteOffset);
         // If Current does not write to the same object as KillingDef, check
         // the next candidate.
-        if (OR == OW_Unknown)
+        if (OR == OW_Unknown || OR == OW_None)
           continue;
         else if (OR == OW_MaybePartial) {
           // If KillingDef only partially overwrites Current, check the next
           // candidate if the partial step limit is exceeded. This aggressively
           // limits the number of candidates for partial store elimination,
           // which are less likely to be removable in the end.
           if (PartialLimit <= 1) {
             WalkerStepLimit -= 1;
+            LLVM_DEBUG(dbgs() << "   ... reached partial limit ... continue with next access\n");
             continue;
           }
           PartialLimit -= 1;
         }
       }
       break;
     };