[DSE,MemorySSA] Split off partial tracking from isOverwite.

[fhahn]

Summary

When traversing memory uses to look for aliasing reads/writes, we only
care about complete overwrites. This patch splits off the partial
overwrite tracking from isOverwrite This avoids some unnecessary work
when checking for read/write clobbers with MemorySSA-DSE.
isOverwrite, which skips the partial overwrite tracking.

This gives a relatively small improvement
http://llvm-compile-time-tracker.com/compare.php?from=ef2a2f77f87553a0a4a39f518eb9ac86b756bda6&to=658f3905dd96d3415f3782adc712c79fa59a4665&stat=instructions

This is part of the patches to bring down compile-time to the level
referenced in
http://lists.llvm.org/pipermail/llvm-dev/2020-August/144417.html

[fhahn]

Rebased so it can be applied on trunk ahead of D86275.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 
 namespace {
 
 enum OverwriteResult {
   OW_Begin,
   OW_Complete,
   OW_End,
   OW_PartialEarlierWithFullLater,
+  OW_MaybePartial,
   OW_Unknown
 };
 
 } // end anonymous namespace
 
 /// Return 'OW_Complete' if a store to the 'Later' location completely
-/// overwrites a store to the 'Earlier' location, 'OW_End' if the end of the
-/// 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the
-/// beginning of the 'Earlier' location is overwritten by 'Later'.
-/// 'OW_PartialEarlierWithFullLater' means that an earlier (big) store was
-/// overwritten by a latter (smaller) store which doesn't write outside the big
-/// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.
+/// overwrites a store to the 'Earlier' location. 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.
 static OverwriteResult isOverwrite(const MemoryLocation &Later,
                                    const MemoryLocation &Earlier,
                                    const DataLayout &DL,
                                    const TargetLibraryInfo &TLI,
                                    int64_t &EarlierOff, int64_t &LaterOff,
-                                   Instruction *DepWrite,
-                                   InstOverlapIntervalsTy &IOL,
-                                   AliasAnalysis &AA,
-                                   const Function *F) {
+                                   AliasAnalysis &AA, const Function *F) {
   // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
   // get imprecise values here, though (except for unknown sizes).
   if (!Later.Size.isPrecise() || !Earlier.Size.isPrecise())
     return OW_Unknown;
 
   const uint64_t LaterSize = Later.Size.getValue();
   const uint64_t EarlierSize = Earlier.Size.getValue();
 
static OverwriteResult isOverwrite(const MemoryLocation &Later,
   //    |-----  later  ------|
   //
   // We have to be careful here as *Off is signed while *.Size is unsigned.
   if (EarlierOff >= LaterOff &&
       LaterSize >= EarlierSize &&
       uint64_t(EarlierOff - LaterOff) + EarlierSize <= LaterSize)
     return OW_Complete;
 
+  // Later may overwrite earlier completely with other partial writes.
+  return OW_MaybePartial;
+}
+
+/// Return 'OW_Complete' if a store to the 'Later' location completely
+/// overwrites a store to the 'Earlier' location, 'OW_End' if the end of the
+/// 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the
+/// beginning of the 'Earlier' location is overwritten by 'Later'.
+/// 'OW_PartialEarlierWithFullLater' means that an earlier (big) store was
+/// overwritten by a latter (smaller) store which doesn't write outside the big
+/// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.
+/// NOTE: This function must only be called if both \p Later and \p Earlier
+/// write to the same underlying object with valid \p EarlierOff and \p
+/// LaterOff.
+static OverwriteResult isPartialOverwrite(const MemoryLocation &Later,
+                                          const MemoryLocation &Earlier,
+                                          int64_t EarlierOff, int64_t LaterOff,
+                                          Instruction *DepWrite,
+                                          InstOverlapIntervalsTy &IOL) {
+  const uint64_t LaterSize = Later.Size.getValue();
+  const uint64_t EarlierSize = Earlier.Size.getValue();
   // We may now overlap, although the overlap is not complete. There might also
   // be other incomplete overlaps, and together, they might cover the complete
   // earlier write.
   // Note: The correctness of this logic depends on the fact that this function
   // is not even called providing DepWrite when there are any intervening reads.
   if (EnablePartialOverwriteTracking &&
       LaterOff < int64_t(EarlierOff + EarlierSize) &&
       int64_t(LaterOff + LaterSize) >= EarlierOff) {
while (InstDep.isDef() || InstDep.isClobber()) {
       // completely obliterated by the store to 'Loc', and c) which we know that
       // 'Inst' doesn't load from, then we can remove it.
       // Also try to merge two stores if a later one only touches memory written
       // to by the earlier one.
       if (isRemovable(DepWrite) &&
           !isPossibleSelfRead(Inst, Loc, DepWrite, *TLI, *AA)) {
         int64_t InstWriteOffset, DepWriteOffset;
         OverwriteResult OR = isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset,
-                                         InstWriteOffset, DepWrite, IOL, *AA,
-                                         BB.getParent());
+                                         InstWriteOffset, *AA, BB.getParent());
+        if (OR == OW_MaybePartial)
+          OR = isPartialOverwrite(Loc, DepLoc, DepWriteOffset, InstWriteOffset,
+                                  DepWrite, IOL);
+
         if (OR == OW_Complete) {
           LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *DepWrite
                             << "\n  KILLER: " << *Inst << '\n');
 
           // Delete the store and now-dead instructions that feed it.
           deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
                                 ThrowableInst);
           ++NumFastStores;
if (!UseInst->mayWriteToMemory())
       return false;
 
     if (auto *CB = dyn_cast<CallBase>(UseInst))
       if (CB->onlyAccessesInaccessibleMemory())
         return false;
 
     int64_t InstWriteOffset, DepWriteOffset;
     auto CC = getLocForWriteEx(UseInst);
-    InstOverlapIntervalsTy IOL;
-
     const DataLayout &DL = F.getParent()->getDataLayout();
-
-    return CC &&
-           isOverwrite(*CC, DefLoc, DL, TLI, DepWriteOffset, InstWriteOffset,
-                       UseInst, IOL, AA, &F) == OW_Complete;
+    return CC && isOverwrite(*CC, DefLoc, DL, TLI, DepWriteOffset,
+                             InstWriteOffset, AA, &F) == OW_Complete;
   }
 
   /// 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");
 
for (unsigned I = 0; I < ToCheck.size(); I++) {
         LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *NI
                           << "\n  KILLER: " << *SI << '\n');
         State.deleteDeadInstruction(NI);
         ++NumFastStores;
         MadeChange = true;
       } else {
         // Check if NI overwrites SI.
         int64_t InstWriteOffset, DepWriteOffset;
+        OverwriteResult OR = isOverwrite(SILoc, NILoc, DL, TLI, DepWriteOffset,
+                                         InstWriteOffset, State.AA, &F);
+        if (OR == OW_MaybePartial) {
           auto Iter = State.IOLs.insert(
               std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
                   NI->getParent(), InstOverlapIntervalsTy()));
           auto &IOL = Iter.first->second;
-        OverwriteResult OR = isOverwrite(SILoc, NILoc, DL, TLI, DepWriteOffset,
-                                         InstWriteOffset, NI, IOL, AA, &F);
+          OR = isPartialOverwrite(SILoc, NILoc, DepWriteOffset, InstWriteOffset,
+                                  NI, IOL);
+        }
 
         if (EnablePartialStoreMerging && OR == OW_PartialEarlierWithFullLater) {
           auto *Earlier = dyn_cast<StoreInst>(NI);
           auto *Later = dyn_cast<StoreInst>(SI);
           // We are re-using tryToMergePartialOverlappingStores, which requires
           // Earlier to domiante Later.
           // TODO: implement tryToMergeParialOverlappingStores using MemorySSA.
           if (Earlier && Later && DT.dominates(Earlier, Later)) {