[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

978–979

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

1378

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.

1389

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

 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 KillingI has to
 /// overwrite \p DeadI.
struct DSEState {
   }
 
   /// Return 'OW_Complete' if a store to the 'KillingLoc' location (by \p
   /// KillingI instruction) completely overwrites a store to the 'DeadLoc'
   /// location (by \p DeadI instruction).
   /// Return OW_MaybePartial if \p KillingI does not completely overwrite
   /// \p DeadI, but they both write to the same underlying object. In that
   /// case, use isPartialOverwrite to check if \p KillingI partially overwrites
+  /// \p DeadI. Returns 'OR_None' if \p KillingI is known to not overwrite the
   /// \p DeadI. Returns 'OW_Unknown' if nothing can be determined.
   OverwriteResult isOverwrite(const Instruction *KillingI,
                               const Instruction *DeadI,
                               const MemoryLocation &KillingLoc,
                               const MemoryLocation &DeadLoc,
                               int64_t &KillingOff, int64_t &DeadOff) {
     // AliasAnalysis does not always account for loops. Limit overwrite checks
     // to dependencies for which we can guarantee they are independent of any
OverwriteResult isOverwrite(const Instruction *KillingI,
     // overwrites any other store to the same object.
     const Value *DeadPtr = DeadLoc.Ptr->stripPointerCasts();
     const Value *KillingPtr = KillingLoc.Ptr->stripPointerCasts();
     const Value *DeadUndObj = getUnderlyingObject(DeadPtr);
     const Value *KillingUndObj = getUnderlyingObject(KillingPtr);
 
     // If we can't resolve the same pointers to the same object, then we can't
     // analyze them at all.
-    if (DeadUndObj != KillingUndObj)
+    if (DeadUndObj != KillingUndObj) {
+      // Non aliasing stores to different objects don't overlap. Note that
+      // if the killing store is known to overwrite whole object (out of
+      // bounds access overwrites whole object as well) then it is assumed to
+      // completely overwrite any store to the same object even if they don't
+      // actually alias (see next check).
+      if (AAR == AliasResult::NoAlias)
+        return OW_None;
       return OW_Unknown;
+    }
 
     // If the KillingI store is to a recognizable object, get its size.
     uint64_t KillingUndObjSize = getPointerSize(KillingUndObj, DL, TLI, &F);
     if (KillingUndObjSize != MemoryLocation::UnknownSize)
       if (KillingUndObjSize == KillingSize && KillingUndObjSize >= DeadSize)
         return OW_Complete;
 
     // Okay, we have stores to two completely different pointers.  Try to
if (DeadOff >= KillingOff) {
       else if ((uint64_t)(DeadOff - KillingOff) < KillingSize)
         return OW_MaybePartial;
     }
     // If start of the killing access is "before" end of the dead access then
     // accesses overlap.
     else if ((uint64_t)(KillingOff - DeadOff) < DeadSize) {
       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()) {
         // underlying object as the terminator.
         if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI))
           continue;
       } else {
         int64_t KillingOffset = 0;
         int64_t DeadOffset = 0;
         auto OR = isOverwrite(KillingI, CurrentI, KillingLoc, *CurrentLoc,
                               KillingOffset, DeadOffset);
         // 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;
     };