[DSE] Add OR_None (not for commit)

[fhahn]

Summary

Slight variant of D105098 which also returns OW_None on NoAlias.

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1012

Maybe move this check to the start?

1069

Comment is outdated.

[fhahn]

This is not really intended for commit, just to make it easy to apply/test the follow-up changes.

Let's work on getting the original D105098 in.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1012

I originally had the check just after getting AAR, but isOverwrite considers out-of-bounds writes killing other writes to the same underlying object, which would be missed by the early exit.

[ebrevnov]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1012

Could you clarify which particular piece of code handles "out-of-bounds" case?

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1012

It is not handled explicitly and is a consequence of the code just below (lines 1017-1020). If the underlying object size matches the size of the out-of-bounds store, the out of bounds store is considered killing other stores to the same object. Note that this logic does not kick in, if the out-of-bounds store is smaller than the underlying object. I added such a test case in 9c00afe926e9

[ebrevnov]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1012

Got it, thanks. Will update D105098 and add related comment.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1012

That sounds great, thanks!

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1012

@ebrevnov do you already have an idea on when you'll be able to update D105098?

otherwise I could also fold the changes from D105098 into this one and commit it on your behalf.

[ebrevnov]

I'm totally fine if you commit changes by yourself. I will be able to get to it early next week only.

PS: I had a very busy week and didn't have chance to work on that. Sorry...

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 namespace {
 
 enum OverwriteResult {
   OW_Begin,
   OW_Complete,
   OW_End,
   OW_PartialEarlierWithFullLater,
   OW_MaybePartial,
-  OW_Unknown
+  OW_Unknown,
+  OW_None
 };
 
 } // end anonymous namespace
 
 /// Check if two instruction are masked stores that completely
 /// overwrite one another. More specifically, \p KillingI has to
 /// overwrite \p DeadI.
 static OverwriteResult isMaskedStoreOverwrite(const Instruction *KillingI,
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) {
+      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
OverwriteResult isOverwrite(const Instruction *KillingI,
     }
     // 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;
+    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()) {
           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;