[DSE][WIP] Take advantage of isOverwrite in isReadClobber

[ebrevnov]

Update.

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
struct DSEState {
   }
 
   /// Returns true if \p Def is not read before returning from the function.
   bool isWriteAtEndOfFunction(MemoryDef *Def) {
     LLVM_DEBUG(dbgs() << "  Check if def " << *Def << " ("
                       << *Def->getMemoryInst()
                       << ") is at the end the function \n");
 
-    auto MaybeLoc = getLocForWriteEx(Def->getMemoryInst());
+    Instruction *DefInst = Def->getMemoryInst();
+    auto MaybeLoc = getLocForWriteEx(DefInst);
     if (!MaybeLoc) {
       LLVM_DEBUG(dbgs() << "  ... could not get location for write.\n");
       return false;
     }
 
     SmallVector<MemoryAccess *, 4> WorkList;
     SmallPtrSet<MemoryAccess *, 8> Visited;
     auto PushMemUses = [&WorkList, &Visited](MemoryAccess *Acc) {
for (unsigned I = 0; I < WorkList.size(); I++) {
       // for example.
       // TODO: Add support for phi translation to handle the loop case.
       if (isa<MemoryPhi>(UseAccess))
         return false;
 
       // TODO: Checking for aliasing is expensive. Consider reducing the amount
       // of times this is called and/or caching it.
       Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
-      if (isReadClobber(*MaybeLoc, UseInst)) {
+      if (isReadClobber(DefInst, *MaybeLoc, 0, UseInst)) {
         LLVM_DEBUG(dbgs() << "  ... hit read clobber " << *UseInst << ".\n");
         return false;
       }
 
       if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
         PushMemUses(UseDef);
     }
     return true;
bool isMemTerminator(const MemoryLocation &Loc, Instruction *AccessI,
     }
     int64_t InstWriteOffset = 0;
     int64_t DepWriteOffset = 0;
     return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, DepWriteOffset,
                        InstWriteOffset) == OW_Complete;
   }
 
   // Returns true if \p Use may read from \p DefLoc.
-  bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {
+  bool isReadClobber(Instruction *DefInst, const MemoryLocation &DefLoc,
+                     const int64_t DefOffset, Instruction *UseInst,
+                     Optional<MemoryLocation> UseLoc = None,
+                     const int64_t UseOffset = 0) {
     if (isNoopIntrinsic(UseInst))
       return false;
 
     // Monotonic or weaker atomic stores can be re-ordered and do not need to be
     // treated as read clobber.
     if (auto SI = dyn_cast<StoreInst>(UseInst))
       return isStrongerThan(SI->getOrdering(), AtomicOrdering::Monotonic);
 
     if (!UseInst->mayReadFromMemory())
       return false;
 
     if (auto *CB = dyn_cast<CallBase>(UseInst))
       if (CB->onlyAccessesInaccessibleMemory())
         return false;
 
+    if (!UseLoc) {
+      UseLoc = getLocForWriteEx(UseInst);
+      if (!UseLoc)
+        UseLoc = MemoryLocation::getOrNone(UseInst);
+    }
+
+    int64_t DummyDefOffset = DefOffset;
+    int64_t DummyUseOffset = UseOffset;
+    if (UseLoc &&
+        isOverwrite(DefInst, UseInst, DefLoc, *UseLoc, DummyUseOffset,
+                    DummyDefOffset) == OW_None)
+      return false;
+
     // NOTE: For calls, the number of stores removed could be slightly improved
     // by using AA.callCapturesBefore(UseInst, DefLoc, &DT), but that showed to
     // be expensive compared to the benefits in practice. For now, avoid more
     // expensive analysis to limit compile-time.
+    if (DefOffset == 0 && UseOffset == 0)
       return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc));
+
+    return true;
   }
 
   /// Returns true if a dependency between \p Current and \p KillingDef is
   /// guaranteed to be loop invariant for the loops that they are in. Either
   /// because they are known to be in the same block, in the same loop level or
   /// by guaranteeing that \p CurrentLoc only references a single MemoryLocation
   /// during execution of the containing function.
   bool isGuaranteedLoopIndependent(const Instruction *Current,
for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
 
       // Check for anything that looks like it will be a barrier to further
       // removal
       if (isDSEBarrier(DefUO, CurrentI)) {
         LLVM_DEBUG(dbgs() << "  ... skip, barrier\n");
         return None;
       }
 
+      // If Current does not have an analyzable write location, skip it
+      CurrentLoc = getLocForWriteEx(CurrentI);
+      if (!CurrentLoc)
+        continue;
+
       // If Current is known to be on path that reads DefLoc or is a read
       // clobber, bail out, as the path is not profitable. We skip this check
       // for intrinsic calls, because the code knows how to handle memcpy
       // intrinsics.
-      if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(DefLoc, CurrentI))
+      if (!isa<IntrinsicInst>(CurrentI) &&
+          isReadClobber(KillingI, DefLoc, 0, CurrentI, CurrentLoc, 0))
         return None;
 
       // Quick check if there are direct uses that are read-clobbers.
-      if (any_of(Current->uses(), [this, &DefLoc, StartAccess](Use &U) {
-            if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
+      if (any_of(Current->uses(), [this, KillingI, &DefLoc,
+                                   StartAccess](Use &U) {
+            if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser())) {
+              auto *UseInst = UseOrDef->getMemoryInst();
               return !MSSA.dominates(StartAccess, UseOrDef) &&
-                     isReadClobber(DefLoc, UseOrDef->getMemoryInst());
+                     isReadClobber(KillingI, DefLoc, 0, UseInst);
+            }
             return false;
           })) {
         LLVM_DEBUG(dbgs() << "   ...  found a read clobber\n");
         return None;
       }
 
       // If Current cannot be analyzed or is not removable, check the next
       // candidate.
       if (!hasAnalyzableMemoryWrite(CurrentI, TLI) || !isRemovable(CurrentI))
         continue;
 
-      // If Current does not have an analyzable write location, skip it
-      CurrentLoc = getLocForWriteEx(CurrentI);
-      if (!CurrentLoc)
-        continue;
-
       // AliasAnalysis does not account for loops. Limit elimination to
       // candidates for which we can guarantee they always store to the same
       // memory location and not located in different loops.
       if (!isGuaranteedLoopIndependent(CurrentI, KillingI, *CurrentLoc)) {
         LLVM_DEBUG(dbgs() << "  ... not guaranteed loop independent\n");
         WalkerStepLimit -= 1;
         continue;
       }
for (unsigned I = 0; I < WorkList.size(); I++) {
 
       if (UseInst->mayThrow() && !isInvisibleToCallerBeforeRet(DefUO)) {
         LLVM_DEBUG(dbgs() << "  ... found throwing instruction\n");
         return None;
       }
 
       // Uses which may read the original MemoryDef mean we cannot eliminate the
       // original MD. Stop walk.
-      if (isReadClobber(*CurrentLoc, UseInst)) {
+      if (isReadClobber(EarlierMemInst, *CurrentLoc, 0, UseInst)) {
         LLVM_DEBUG(dbgs() << "    ... found read clobber\n");
         return None;
       }
 
       // If this worklist walks back to the original memory access (and the
       // pointer is not guarenteed loop invariant) then we cannot assume that a
       // store kills itself.
       if (EarlierAccess == UseAccess &&