[DSE] Sink a memory access if it is only alive in one successor.

[StephenFan]

Summary

If a memory access is only alive in one successor, sinking the instruction
of this memory access to the alive successor will make the program execute one
less instruction if it goes to dead successors(successors except the
alive successor).

Since deleting instruction is more beneficial than sinking, sinking will
be doing until we have deleted all dead instructions.

It seems to have no effect on on compile time: https://llvm-compile-time-tracker.com/compare.php?from=6eb40bf51b768672218539935f60ce55ae6ad750&to=e8bccfd7a3c58f3287f7da7ab3e2582ec270b0f4&stat=instructions

[StephenFan]

Update.

[StephenFan]

Fix CI error.

[pcwalton]

This is great! A couple of things I noticed on my test case:

1. This doesn't handle the case in which you might sink a store into a basic block that reads it (in my test case, it's a throwing instruction), because the check for readers will kick in and return None from getDomMemoryDef() before ever getting to check whether it can sink the store. I guess to fix this we could track reading instructions, instead of bailing out immediately, and see if they are all inside or dominated by SuccToSinkTo. If so, we should be able to safely sink the store, I think?

2. This doesn't handle the slow CFG search that kicks in if there are unreachable instructions. We could presumably detect sink targets there too.

Both of these things could be followups of course. :)

[StephenFan]

In D136218#3881225, @pcwalton wrote:

This is great! A couple of things I noticed on my test case:

1. This doesn't handle the case in which you might sink a store into a basic block that reads it (in my test case, it's a throwing instruction), because the check for readers will kick in and return None from getDomMemoryDef() before ever getting to check whether it can sink the store. I guess to fix this we could track reading instructions, instead of bailing out immediately, and see if they are all inside or dominated by SuccToSinkTo. If so, we should be able to safely sink the store, I think?

2. This doesn't handle the slow CFG search that kicks in if there are unreachable instructions. We could presumably detect sink targets there too.

Both of these things could be followups of course. :)

Thanks a lot for testing it and making suggestions. I will try to solve these cases these days.

[StephenFan]

In D136218#3881225, @pcwalton wrote:

This is great! A couple of things I noticed on my test case:

1. This doesn't handle the case in which you might sink a store into a basic block that reads it (in my test case, it's a throwing instruction), because the check for readers will kick in and return None from getDomMemoryDef() before ever getting to check whether it can sink the store. I guess to fix this we could track reading instructions, instead of bailing out immediately, and see if they are all inside or dominated by SuccToSinkTo. If so, we should be able to safely sink the store, I think?

2. This doesn't handle the slow CFG search that kicks in if there are unreachable instructions. We could presumably detect sink targets there too.

Both of these things could be followups of course. :)

I don't get the point of your second suggestion, do you mind giving a test case? :)

[StephenFan]

1. Don't bail out immediatly if has read clobber.
2. Handle the slow CFG search.

[StephenFan]

Ping:)

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "dse"
 
 STATISTIC(NumRemainingStores, "Number of stores remaining after DSE");
 STATISTIC(NumRedundantStores, "Number of redundant stores deleted");
 STATISTIC(NumFastStores, "Number of stores deleted");
+STATISTIC(NumSunkStores, "Number of sunk stores");
 STATISTIC(NumFastOther, "Number of other instrs removed");
 STATISTIC(NumCompletePartials, "Number of stores dead by later partials");
 STATISTIC(NumModifiedStores, "Number of stores modified");
 STATISTIC(NumCFGChecks, "Number of stores modified");
 STATISTIC(NumCFGTries, "Number of stores modified");
 STATISTIC(NumCFGSuccess, "Number of stores modified");
 STATISTIC(NumGetDomMemoryDefPassed,
           "Number of times a valid candidate is returned from getDomMemoryDef");
enum OverwriteResult {
   OW_Complete,
   OW_End,
   OW_PartialEarlierWithFullLater,
   OW_MaybePartial,
   OW_None,
   OW_Unknown
 };
 
-} // end anonymous namespace
+// Represent a dead access candidate that we can delete or sink it.
+struct DeadAccessCandidate {
+  MemoryAccess *MaybeDeadAccess;
+
+  // Only successor that MaybeDeadAccess live in. nullptr if
+  // MaybeDeadAccess is post-dominated by its KillingDefs.
+  BasicBlock *AliveSucc;
+
+  bool hasAliveSucc() { return AliveSucc != nullptr; }
+};
+
+} // 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,
                                               const Instruction *DeadI,
                                               BatchAAResults &AA) {
   const auto *KillingII = dyn_cast<IntrinsicInst>(KillingI);
struct DSEState {
   DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
   // Values that are only used with assumes. Used to refine pointer escape
   // analysis.
   SmallPtrSet<const Value *, 32> EphValues;
 
   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
   /// basic block.
   MapVector<BasicBlock *, InstOverlapIntervalsTy> IOLs;
+
+  /// Keep track of instructions that is only alive in one successor.
+  MapVector<Instruction *, BasicBlock *> SinkCandidates;
+
   // Check if there are root nodes that are terminated by UnreachableInst.
   // Those roots pessimize post-dominance queries. If there are such roots,
   // fall back to CFG scan starting from all non-unreachable roots.
   bool AnyUnreachableExit;
 
   // Whether or not we should iterate on removing dead stores at the end of the
   // function due to removing a store causing a previously captured pointer to
   // no longer be captured.
struct DSEState {
   }
 
   // Find a MemoryDef writing to \p KillingLoc and dominating \p StartAccess,
   // with no read access between them or on any other path to a function exit
   // block if \p KillingLoc is not accessible after the function returns. If
   // there is no such MemoryDef, return None. The returned value may not
   // (completely) overwrite \p KillingLoc. Currently we bail out when we
   // encounter an aliasing MemoryUse (read).
-  Optional<MemoryAccess *>
+  Optional<DeadAccessCandidate>
   getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *StartAccess,
                   const MemoryLocation &KillingLoc, const Value *KillingUndObj,
                   unsigned &ScanLimit, unsigned &WalkerStepLimit,
                   bool IsMemTerm, unsigned &PartialLimit) {
     if (ScanLimit == 0 || WalkerStepLimit == 0) {
       LLVM_DEBUG(dbgs() << "\n    ...  hit scan limit\n");
       return None;
     }
for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
         return None;
       }
       WalkerStepLimit -= StepCost;
 
       // Return for MemoryPhis. They cannot be eliminated directly and the
       // caller is responsible for traversing them.
       if (isa<MemoryPhi>(Current)) {
         LLVM_DEBUG(dbgs() << "   ...  found MemoryPhi\n");
-        return Current;
+        return {{Current, nullptr}};
       }
 
       // Below, check if CurrentDef is a valid candidate to be eliminated by
       // KillingDef. If it is not, check the next candidate.
       MemoryDef *CurrentDef = cast<MemoryDef>(Current);
       Instruction *CurrentI = CurrentDef->getMemoryInst();
 
       if (canSkipDef(CurrentDef, !isInvisibleToCallerOnUnwind(KillingUndObj))) {
getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *StartAccess,
     // eliminated if the access is dead along all paths to the exit. Collect
     // the blocks with killing (=completely overwriting MemoryDefs) and check if
     // they cover all paths from MaybeDeadAccess to any function exit.
     SmallPtrSet<Instruction *, 16> KillingDefs;
     KillingDefs.insert(KillingDef->getMemoryInst());
     MemoryAccess *MaybeDeadAccess = Current;
     MemoryLocation MaybeDeadLoc = *CurrentLoc;
     Instruction *MaybeDeadI = cast<MemoryDef>(MaybeDeadAccess)->getMemoryInst();
+    // This indicates there is throw instruction or read clobber that doesn't
+    // dominated by any of KillingDefs. We use this flag instead of bailing out immediately
+    // since we might be able to sink stores.
+    SmallPtrSet<Instruction *, 2> ThrowOrReadClobbers;
     LLVM_DEBUG(dbgs() << "  Checking for reads of " << *MaybeDeadAccess << " ("
                       << *MaybeDeadI << ")\n");
 
     SmallSetVector<MemoryAccess *, 32> WorkList;
     auto PushMemUses = [&WorkList](MemoryAccess *Acc) {
       for (Use &U : Acc->uses())
         WorkList.insert(cast<MemoryAccess>(U.getUser()));
     };
for (unsigned I = 0; I < WorkList.size(); I++) {
       if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {
         LLVM_DEBUG(dbgs() << "    ... adding uses of intrinsic\n");
         PushMemUses(UseAccess);
         continue;
       }
 
       if (UseInst->mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj)) {
         LLVM_DEBUG(dbgs() << "  ... found throwing instruction\n");
-        return None;
+        ThrowOrReadClobbers.insert(UseInst);
+        continue;
       }
 
       // Uses which may read the original MemoryDef mean we cannot eliminate the
       // original MD. Stop walk.
       if (isReadClobber(MaybeDeadLoc, UseInst)) {
         LLVM_DEBUG(dbgs() << "    ... found read clobber\n");
-        return None;
+        ThrowOrReadClobbers.insert(UseInst);
+        continue;
       }
 
       // 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 (MaybeDeadAccess == UseAccess &&
           !isGuaranteedLoopInvariant(MaybeDeadLoc.Ptr)) {
         LLVM_DEBUG(dbgs() << "    ... found not loop invariant self access\n");
for (unsigned I = 0; I < WorkList.size(); I++) {
                        << "    ... found preceeding def " << *UseInst << "\n");
             return None;
           }
         } else
           PushMemUses(UseDef);
       }
     }
 
+    auto findSuccToSinkTo = [&](BasicBlock *BB) -> BasicBlock * {
+      // It does not make sense to sink if has only one successor.
+      if (succ_size(BB) == 1 || IsMemTerm)
+        return nullptr;
+      BasicBlock *SuccToSinkTo = nullptr;
+      for (auto *Succ : successors(BB)) {
+        if (all_of(KillingDefs, [Succ](Instruction *KillingDef) {
+          return KillingDef->getParent() != Succ;
+        })) {
+          if (SuccToSinkTo)
+            return nullptr;
+
+          // If the successor to sink has other predecessors, then sink
+          // to it will cause mis-compilation.
+          if (pred_size(Succ) > 1)
+            return nullptr;
+
+          SuccToSinkTo = Succ;
+        }
+      }
+      if (all_of(ThrowOrReadClobbers, [&](Instruction *I) {
+        return I->getParent() != MaybeDeadAccess->getBlock();
+      }))
+        return SuccToSinkTo;
+      return nullptr;
+    };
+
+    BasicBlock *SuccToSinkTo = findSuccToSinkTo(MaybeDeadAccess->getBlock());
+
     // For accesses to locations visible after the function returns, make sure
     // that the location is dead (=overwritten) along all paths from
     // MaybeDeadAccess to the exit.
     if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
       SmallPtrSet<BasicBlock *, 16> KillingBlocks;
       for (Instruction *KD : KillingDefs)
         KillingBlocks.insert(KD->getParent());
       assert(!KillingBlocks.empty() &&
              "Expected at least a single killing block");
 
       // Find the common post-dominator of all killing blocks.
       BasicBlock *CommonPred = *KillingBlocks.begin();
       for (BasicBlock *BB : llvm::drop_begin(KillingBlocks)) {
         if (!CommonPred)
           break;
         CommonPred = PDT.findNearestCommonDominator(CommonPred, BB);
       }
 
       // If the common post-dominator does not post-dominate MaybeDeadAccess,
       // there is a path from MaybeDeadAccess to an exit not going through a
       // killing block.
       if (!PDT.dominates(CommonPred, MaybeDeadAccess->getBlock())) {
-        if (!AnyUnreachableExit)
+        if (!AnyUnreachableExit) {
+          if (SuccToSinkTo)
+            return {{MaybeDeadAccess, SuccToSinkTo}};
           return None;
-
+        }
         // Fall back to CFG scan starting at all non-unreachable roots if not
         // all paths to the exit go through CommonPred.
         CommonPred = nullptr;
       }
 
+      // At this point, we will not do sink. Return None if has throw or read clobber.
+      if (ThrowOrReadClobbers.size())
+        return None;
+
       // If CommonPred itself is in the set of killing blocks, we're done.
       if (KillingBlocks.count(CommonPred))
-        return {MaybeDeadAccess};
+        return {{MaybeDeadAccess, nullptr}};
 
       SetVector<BasicBlock *> WorkList;
       // If CommonPred is null, there are multiple exits from the function.
       // They all have to be added to the worklist.
       if (CommonPred)
         WorkList.insert(CommonPred);
       else
         for (BasicBlock *R : PDT.roots()) {
           if (!isa<UnreachableInst>(R->getTerminator()))
             WorkList.insert(R);
         }
 
       NumCFGTries++;
       // Check if all paths starting from an exit node go through one of the
       // killing blocks before reaching MaybeDeadAccess.
       for (unsigned I = 0; I < WorkList.size(); I++) {
         NumCFGChecks++;
         BasicBlock *Current = WorkList[I];
         if (KillingBlocks.count(Current))
           continue;
-        if (Current == MaybeDeadAccess->getBlock())
+        if (Current == MaybeDeadAccess->getBlock()) {
+          if (SuccToSinkTo)
+            return {{MaybeDeadAccess, SuccToSinkTo}};
           return None;
+        }
 
         // MaybeDeadAccess is reachable from the entry, so we don't have to
         // explore unreachable blocks further.
         if (!DT.isReachableFromEntry(Current))
           continue;
 
         for (BasicBlock *Pred : predecessors(Current))
           WorkList.insert(Pred);
 
         if (WorkList.size() >= MemorySSAPathCheckLimit)
           return None;
       }
       NumCFGSuccess++;
     }
 
     // No aliasing MemoryUses of MaybeDeadAccess found, MaybeDeadAccess is
     // potentially dead.
-    return {MaybeDeadAccess};
+    if (!ThrowOrReadClobbers.size())
+      return {{MaybeDeadAccess, nullptr}};
+    return None;
+  }
+
+  bool sinkInstructions() {
+    bool MadeChange = false;
+    MemorySSAUpdater Updater(&MSSA);
+    for (auto Candidate : SinkCandidates) {
+      Instruction *ToSink = Candidate.first;
+      BasicBlock *SuccToSinkTo = Candidate.second;
+      MemoryAccess *DeadAccess = MSSA.getMemoryAccess(ToSink);
+      assert(!isa<MemoryPhi>(DeadAccess) && "Can't sink MemoryPhi");
+      MemoryAccess *DeadAccessDefining =
+          cast<MemoryUseOrDef>(DeadAccess)->getDefiningAccess();
+
+      if (auto *Def = dyn_cast<MemoryDef>(DeadAccess))
+        SkipStores.insert(Def);
+      Updater.removeMemoryAccess(DeadAccess);
+      ToSink->moveBefore(SuccToSinkTo->getFirstNonPHI());
+      Updater.createMemoryAccessInBB(ToSink, DeadAccessDefining,
+                                     ToSink->getParent(), MemorySSA::Beginning);
+      ++NumSunkStores;
+      MadeChange = true;
+    }
+    return MadeChange;
   }
 
   // Delete dead memory defs
   void deleteDeadInstruction(Instruction *SI) {
     MemorySSAUpdater Updater(&MSSA);
     SmallVector<Instruction *, 32> NowDeadInsts;
     NowDeadInsts.push_back(SI);
     --NumFastOther;
while (!NowDeadInsts.empty()) {
         }
 
         Updater.removeMemoryAccess(MA);
       }
 
       auto I = IOLs.find(DeadInst->getParent());
       if (I != IOLs.end())
         I->second.erase(DeadInst);
+
+      // Deleting is more beneficial than sinking.
+      if (SinkCandidates.count(DeadInst))
+        SinkCandidates.erase(DeadInst);
+
       // Remove its operands
       for (Use &O : DeadInst->operands())
         if (Instruction *OpI = dyn_cast<Instruction>(O)) {
           O = nullptr;
           if (isInstructionTriviallyDead(OpI, &TLI))
             NowDeadInsts.push_back(OpI);
         }
 
for (unsigned I = 0; I < State.MemDefs.size(); I++) {
     bool Shortend = false;
     bool IsMemTerm = State.isMemTerminatorInst(KillingI);
     // Check if MemoryAccesses in the worklist are killed by KillingDef.
     for (unsigned I = 0; I < ToCheck.size(); I++) {
       MemoryAccess *Current = ToCheck[I];
       if (State.SkipStores.count(Current))
         continue;
 
-      Optional<MemoryAccess *> MaybeDeadAccess = State.getDomMemoryDef(
+      Optional<DeadAccessCandidate> DeadCandidate = State.getDomMemoryDef(
           KillingDef, Current, KillingLoc, KillingUndObj, ScanLimit,
           WalkerStepLimit, IsMemTerm, PartialLimit);
 
-      if (!MaybeDeadAccess) {
+      if (!DeadCandidate) {
         LLVM_DEBUG(dbgs() << "  finished walk\n");
         continue;
       }
 
-      MemoryAccess *DeadAccess = *MaybeDeadAccess;
+      MemoryAccess *DeadAccess = DeadCandidate->MaybeDeadAccess;
       LLVM_DEBUG(dbgs() << " Checking if we can kill " << *DeadAccess);
       if (isa<MemoryPhi>(DeadAccess)) {
         LLVM_DEBUG(dbgs() << "\n  ... adding incoming values to worklist\n");
         for (Value *V : cast<MemoryPhi>(DeadAccess)->incoming_values()) {
           MemoryAccess *IncomingAccess = cast<MemoryAccess>(V);
           BasicBlock *IncomingBlock = IncomingAccess->getBlock();
           BasicBlock *PhiBlock = DeadAccess->getBlock();
 
for (unsigned I = 0; I < ToCheck.size(); I++) {
         ++NumFastStores;
         MadeChange = true;
       } else {
         // Check if DeadI overwrites KillingI.
         int64_t KillingOffset = 0;
         int64_t DeadOffset = 0;
         OverwriteResult OR = State.isOverwrite(
             KillingI, DeadI, KillingLoc, DeadLoc, KillingOffset, DeadOffset);
+        if (!DeadCandidate->hasAliveSucc()) {
           if (OR == OW_MaybePartial) {
             auto Iter = State.IOLs.insert(
                 std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
                     DeadI->getParent(), InstOverlapIntervalsTy()));
             auto &IOL = Iter.first->second;
             OR = isPartialOverwrite(KillingLoc, DeadLoc, KillingOffset,
                                     DeadOffset, DeadI, IOL);
           }
 
-        if (EnablePartialStoreMerging && OR == OW_PartialEarlierWithFullLater) {
+          if (EnablePartialStoreMerging &&
+              OR == OW_PartialEarlierWithFullLater) {
             auto *DeadSI = dyn_cast<StoreInst>(DeadI);
             auto *KillingSI = dyn_cast<StoreInst>(KillingI);
-          // We are re-using tryToMergePartialOverlappingStores, which requires
-          // DeadSI to dominate DeadSI.
-          // TODO: implement tryToMergeParialOverlappingStores using MemorySSA.
+            // We are re-using tryToMergePartialOverlappingStores, which
+            // requires DeadSI to dominate DeadSI.
+            // TODO: implement tryToMergeParialOverlappingStores using
+            // MemorySSA.
             if (DeadSI && KillingSI && DT.dominates(DeadSI, KillingSI)) {
               if (Constant *Merged = tryToMergePartialOverlappingStores(
                       KillingSI, DeadSI, KillingOffset, DeadOffset, State.DL,
                       State.BatchAA, &DT)) {
 
                 // Update stored value of earlier store to merged constant.
                 DeadSI->setOperand(0, Merged);
                 ++NumModifiedStores;
                 MadeChange = true;
 
                 Shortend = true;
                 // Remove killing store and remove any outstanding overlap
                 // intervals for the updated store.
                 State.deleteDeadInstruction(KillingSI);
                 auto I = State.IOLs.find(DeadSI->getParent());
                 if (I != State.IOLs.end())
                   I->second.erase(DeadSI);
                 break;
               }
             }
           }
 
           if (OR == OW_Complete) {
             LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *DeadI
                               << "\n  KILLER: " << *KillingI << '\n');
             State.deleteDeadInstruction(DeadI);
             ++NumFastStores;
             MadeChange = true;
           }
+        } else if (OR == OW_Complete) {
+          // The MaybeDeadAccess is live in only one successor, in which case,
+          // we can sink the instruction of MaybeDeadAccess to this successor.
+          State.SinkCandidates.insert({DeadI, DeadCandidate->AliveSucc});
+          MadeChange = true;
+        }
       }
     }
 
     // Check if the store is a no-op.
     if (!Shortend && State.storeIsNoop(KillingDef, KillingUndObj)) {
       LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n  DEAD: " << *KillingI
                         << '\n');
       State.deleteDeadInstruction(KillingI);
static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
   }
 
   if (EnablePartialOverwriteTracking)
     for (auto &KV : State.IOLs)
       MadeChange |= State.removePartiallyOverlappedStores(KV.second);
 
   MadeChange |= State.eliminateRedundantStoresOfExistingValues();
   MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
+  MadeChange |= State.sinkInstructions();
   return MadeChange;
 }
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 // DSE Pass
 //===----------------------------------------------------------------------===//
 PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {

llvm/test/Transforms/DeadStoreElimination/multiblock-multipath.ll

bb5:
   call void @use(ptr %P)
   ret void
 }
 
 ; Cannot remove store in entry block because it is not overwritten on path
 ; entry->bb2->bb5.
 define void @accessible_after_return_3(ptr noalias %P, i1 %c1) {
 ; CHECK-LABEL: @accessible_after_return_3(
-; CHECK-NEXT:    store i32 1, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    store i32 0, ptr [[P]], align 4
+; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[BB5:%.*]]
 ; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, ptr [[P]], align 4
 ; CHECK-NEXT:    br label [[BB5]]
 ; CHECK:       bb5:
 ; CHECK-NEXT:    call void @use(ptr [[P]])
 ; CHECK-NEXT:    ret void
 ;
   store i32 1, ptr %P
   br i1 %c1, label %bb1, label %bb2
 
 bb1:
   store i32 0, ptr %P
   br label %bb5
 
 bb2:
   br label %bb5
 
 bb5:
   call void @use(ptr %P)
   ret void
 }
 
 ; Cannot remove store in entry block because it is not overwritten on path
 ; entry->bb2->bb5.
 define void @accessible_after_return_4(ptr noalias %P, i1 %c1) {
 ; CHECK-LABEL: @accessible_after_return_4(
-; CHECK-NEXT:    store i32 1, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    store i32 0, ptr [[P]], align 4
+; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    call void @use(ptr [[P]])
 ; CHECK-NEXT:    br label [[BB5:%.*]]
 ; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, ptr [[P]], align 4
 ; CHECK-NEXT:    br label [[BB5]]
 ; CHECK:       bb5:
 ; CHECK-NEXT:    ret void
 ;
   store i32 1, ptr %P
   br i1 %c1, label %bb1, label %bb2
 
 bb1:
   store i32 0, ptr %P
   call void @use(ptr %P)
   br label %bb5
 
 bb2:
   br label %bb5
 
 bb5:
   ret void
 }
 
 ; Cannot remove the store in entry, as it is not overwritten on all paths to an
 ; exit (patch including bb4).
 define void @accessible_after_return5(ptr %P, i1 %c.1, i1 %c.2) {
 ; CHECK-LABEL: @accessible_after_return5(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    store i32 1, ptr [[P]], align 4
 ; CHECK-NEXT:    br label [[BB5:%.*]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    store i32 2, ptr [[P]], align 4
 ; CHECK-NEXT:    br label [[BB5]]
 ; CHECK:       bb4:

 }
 
 
 ; Cannot remove store in entry block, because it is overwritten along each path to
 ; the exit (entry->bb1->bb4->bb5).
 define void @accessible_after_return8(ptr %P, i1 %c.1, i1 %c.2) {
 ; CHECK-LABEL: @accessible_after_return8(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    store i32 1, ptr [[P]], align 4
 ; CHECK-NEXT:    br label [[BB5:%.*]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    store i32 2, ptr [[P]], align 4
 ; CHECK-NEXT:    br label [[BB5]]
 ; CHECK:       bb4:

 }
 
 ; Cannot remove store in entry block because it is not overwritten on path
 ; entry->bb2->bb4. Also make sure we deal with dead exit blocks without
 ; crashing.
 define void @accessible_after_return10_dead_block(ptr %P, i1 %c.1, i1 %c.2) {
 ; CHECK-LABEL: @accessible_after_return10_dead_block(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    store i32 1, ptr [[P]], align 4
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb3:
 ; CHECK-NEXT:    store i32 2, ptr [[P]], align 4
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb4:

llvm/test/Transforms/DeadStoreElimination/multiblock-simple.ll

bb2:
   br label %bb3
 bb3:
   store i32 0, ptr %P
   ret void
 }
 
 define void @test3(ptr noalias %P) {
 ; CHECK-LABEL: @test3(
-; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    store i32 1, ptr [[P]], align 4
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret void
 ;
   store i32 0, ptr %P
bb2:
   br label %bb3
 bb3:
   store i32 2, ptr %P
   ret void
 }
 
 define void @test10(ptr %P) {
 ; CHECK-LABEL: @test10(
-; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    store i32 1, ptr [[P]], align 4
+; CHECK-NEXT:    store i32 1, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, ptr [[P]], align 4
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret void
 ;
   store i32 0, ptr %P
   br i1 true, label %bb1, label %bb2
 bb1:
   store i32 1, ptr %P

llvm/test/Transforms/DeadStoreElimination/multiblock-sink.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -dse -S | FileCheck %s
+;
+declare void @foo() readonly
+
+define void @sink_if_has_read_clobber(ptr %P) {
+; CHECK-LABEL: @sink_if_has_read_clobber(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 1, ptr [[P:%.*]], align 4
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, ptr [[P]], align 4
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i32 0, ptr %P
+  br i1 true, label %bb1, label %bb2
+
+bb1:
+  store i32 1, ptr %P
+  br label %bb3
+
+bb2:
+  call void @foo()
+  br label %bb3
+
+bb3:
+  ret void
+}
+
+define void @dont_sink_if_has_read_clobber(ptr %P) {
+; CHECK-LABEL: @dont_sink_if_has_read_clobber(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 1, ptr [[P]], align 4
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i32 0, ptr %P
+  call void @foo()
+  br i1 true, label %bb1, label %bb2
+
+bb1:
+  store i32 1, ptr %P
+  br label %bb3
+
+bb2:
+  call void @foo()
+  br label %bb3
+
+bb3:
+  ret void
+}
+
+define void @dont_sink_if_has_only_one_succ(ptr noalias %P) {
+; CHECK-LABEL: @dont_sink_if_has_only_one_succ(
+; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
+; CHECK-NEXT:    br label [[BB0:%.*]]
+; CHECK:       bb0:
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 1, ptr [[P]], align 4
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+  store i32 0, ptr %P
+  br label %bb0
+bb0:
+  br i1 true, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  store i32 1, ptr %P
+  br label %bb3
+
+bb3:
+  ret void
+}
+
+define void @shouldnt_sink_since_theres_a_full_overlap(ptr %ptr, i1 %c) {
+; CHECK-LABEL: @shouldnt_sink_since_theres_a_full_overlap(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[BPTRM1:%.*]] = getelementptr inbounds i8, ptr [[PTR:%.*]], i64 -1
+; CHECK-NEXT:    [[BPTR3:%.*]] = getelementptr inbounds i8, ptr [[PTR]], i64 3
+; CHECK-NEXT:    store i32 1234, ptr [[BPTRM1]], align 1
+; CHECK-NEXT:    store i64 5678, ptr [[BPTR3]], align 1
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i64 1, ptr [[PTR]], align 4
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i64 0, ptr %ptr
+  %bptrm1 = getelementptr inbounds i8, ptr %ptr, i64 -1
+  %bptr3 = getelementptr inbounds i8, ptr %ptr, i64 3
+  store i32 1234, ptr %bptrm1, align 1
+  store i64 5678, ptr %bptr3, align 1
+  br i1 %c, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  store i64 1, ptr %ptr
+  br label %bb3
+
+bb3:
+  ret void
+}
+
+define void @dont_sink_if_succ_to_sink_will_reach_other_succs(ptr noalias %P) {
+; CHECK-LABEL: @dont_sink_if_succ_to_sink_will_reach_other_succs(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 1, ptr [[P]], align 4
+; CHECK-NEXT:    br label [[BB2]]
+; CHECK:       bb2:
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i32 0, ptr %P
+  br i1 true, label %bb1, label %bb2
+
+bb1:
+  store i32 1, ptr %P
+  br label %bb2
+
+bb2:
+  ret void
+}
+
+define i32 @successor_of_each_other(i1 %c, ptr %p) {
+; CHECK-LABEL: @successor_of_each_other(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[V:%.*]] = load i32, ptr [[P:%.*]], align 4
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB0:%.*]], label [[BB0_0:%.*]]
+; CHECK:       bb0:
+; CHECK-NEXT:    br i1 [[C]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb0.0:
+; CHECK-NEXT:    br label [[BB1]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 [[V]], ptr [[P]], align 4
+; CHECK-NEXT:    br i1 [[C]], label [[BB3:%.*]], label [[BB0]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 0, ptr [[P]], align 4
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %v = load i32, ptr %p, align 4
+  br i1 %c, label %bb0, label %bb0.0
+
+bb0:
+  store i32 0, ptr %p
+  br i1 %c, label %bb1, label %bb2
+
+bb0.0:
+  br label %bb1
+
+bb1:
+  store i32 %v, ptr %p, align 4
+  br i1 %c, label %bb3, label %bb0
+
+bb2:
+  br label %bb3
+
+bb3:
+  ret i32 0
+}

llvm/test/Transforms/DeadStoreElimination/multiblock-unreachable.ll

if.end:
   store i64 0, ptr %ptr, align 8
   ret void
 }
 
 ; Cannot remove the store in entry, because it is not dead on the path to e.1
 define void @unreachable_exit_but_another_exit(ptr noalias %ptr, i1 %c.1, i32 %s, i1 %c.2) {
 ; CHECK-LABEL: @unreachable_exit_but_another_exit(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store i64 1, ptr [[PTR:%.*]], align 8
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
+; CHECK-NEXT:    store i64 1, ptr [[PTR:%.*]], align 8
 ; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[E_0:%.*]], label [[E_1:%.*]]
 ; CHECK:       e.0:
 ; CHECK-NEXT:    tail call void @exit() #[[ATTR0]]
 ; CHECK-NEXT:    unreachable
 ; CHECK:       e.1:
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.end:
 ; CHECK-NEXT:    store i64 0, ptr [[PTR]], align 8

llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=dse -dse-optimize-memoryssa=false -S %s | FileCheck --check-prefixes=CHECK,UNOPT %s
 ; RUN: opt -passes=dse -dse-optimize-memoryssa -S %s | FileCheck --check-prefixes=CHECK,OPT %s
 ; RUN: opt -passes=dse -S %s | FileCheck --check-prefixes=CHECK,OPT %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 @a = external global [32 x i8], align 16
 
 declare void @llvm.memcpy.p0.p0.i64(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i64, i1 immarg)
 
 ; Test case for PR16520. The store in %if.then is redundant, because the same value
 ; has been stored earlier to the same location.
 define void @test1_pr16520(i1 %b, ptr nocapture %r) {
 ; CHECK-LABEL: @test1_pr16520(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store i8 1, ptr [[R:%.*]], align 1
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    tail call void @fn_mayread_or_clobber()
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
+; CHECK-NEXT:    store i8 1, ptr [[R:%.*]], align 1
 ; CHECK-NEXT:    tail call void @fn_mayread_or_clobber()
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   store i8 1, ptr %r, align 1
   br i1 %b, label %if.then, label %if.else

llvm/test/Transforms/PhaseOrdering/AArch64/mul-ov.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes="default<O3>" -S < %s  | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64-unknown-linux-unknown"
 
 define i128 @__muloti4(i128 %0, i128 %1, i32* nonnull align 4 %2) {
 ; CHECK-LABEL: @__muloti4(
 ; CHECK-NEXT:  Entry:
 ; CHECK-NEXT:    [[DOTFR:%.*]] = freeze i128 [[TMP1:%.*]]
-; CHECK-NEXT:    store i32 0, i32* [[TMP2:%.*]], align 4
 ; CHECK-NEXT:    [[MUL:%.*]] = tail call { i128, i1 } @llvm.smul.with.overflow.i128(i128 [[TMP0:%.*]], i128 [[DOTFR]])
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i128 [[TMP0]], 0
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i128 [[DOTFR]], -170141183460469231731687303715884105728
 ; CHECK-NEXT:    [[TMP5:%.*]] = and i1 [[TMP3]], [[TMP4]]
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[THEN7:%.*]], label [[ELSE2:%.*]]
 ; CHECK:       Else2:
 ; CHECK-NEXT:    [[MUL_OV:%.*]] = extractvalue { i128, i1 } [[MUL]], 1
 ; CHECK-NEXT:    br i1 [[MUL_OV]], label [[THEN7]], label [[BLOCK9:%.*]]
 ; CHECK:       Then7:
-; CHECK-NEXT:    store i32 1, i32* [[TMP2]], align 4
 ; CHECK-NEXT:    br label [[BLOCK9]]
 ; CHECK:       Block9:
+; CHECK-NEXT:    [[STOREMERGE:%.*]] = phi i32 [ 1, [[THEN7]] ], [ 0, [[ELSE2]] ]
+; CHECK-NEXT:    store i32 [[STOREMERGE]], i32* [[TMP2:%.*]], align 4
 ; CHECK-NEXT:    [[MUL_VAL:%.*]] = extractvalue { i128, i1 } [[MUL]], 0
 ; CHECK-NEXT:    ret i128 [[MUL_VAL]]
 ;
 Entry:
   %3 = alloca i128, align 16
   %4 = alloca i128, align 16
   store i32 0, i32* %2, align 4
   %5 = mul i128 %0, %1