[WIP][DSE] Enable MSSA DSE to optimize across PHIs

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

 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/MustExecute.h"
bool canSkipDef(MemoryDef *D, bool DefVisibleToCaller) {
 
   // Skip intrinsics that do not really read or modify memory.
   if (isNoopIntrinsic(D->getMemoryInst()))
     return true;
 
   return false;
 }
 
+using PhiTransPtr = std::pair<WeakTrackingVH, int64_t>;
+using ExMemoryAccess = std::pair<MemoryAccess *, PhiTransPtr>;
+
+static PhiTransPtr phiTranslatePtr(const PhiTransPtr &Ptr, BasicBlock *FromBB,
+                                   BasicBlock *ToBB, const DataLayout &DL,
+                                   DominatorTree &DT, AssumptionCache *AC) {
+  PhiTransPtr ResPtr;
+  DenseMap<BasicBlock *, PhiTransPtr> Visited;
+  SmallVector<std::pair<BasicBlock *, const PhiTransPtr>, 16> WorkList;
+
+  if (FromBB == ToBB) {
+    return Ptr;
+  }
+
+  WorkList.push_back({FromBB, Ptr});
+
+  while (!WorkList.empty()) {
+    auto CurrNode = WorkList.pop_back_val();
+    BasicBlock *CurrBB = CurrNode.first;
+    const PhiTransPtr &CurrPtr = CurrNode.second;
+    int64_t Offset = 0;
+    Value *const BasePtr =
+        GetPointerBaseWithConstantOffset(CurrPtr.first, Offset, DL);
+    const int64_t BaseOffset = CurrPtr.second + Offset;
+
+    for (pred_iterator PI = pred_begin(CurrBB), E = pred_end(CurrBB); PI != E;
+         ++PI) {
+      BasicBlock *PredBB = *PI;
+      PHITransAddr TransAddr{BasePtr, DL, AC};
+
+      // TODO:
+      if (!DT.dominates(ToBB, PredBB))
+        continue;
+
+      if (TransAddr.NeedsPHITranslationFromBlock(CurrBB) &&
+              (!TransAddr.IsPotentiallyPHITranslatable() ||
+          TransAddr.PHITranslateValue(CurrBB, PredBB, &DT, false)))
+        return PhiTransPtr{};
+
+      auto Inserted =
+          Visited.try_emplace(PredBB, TransAddr.getAddr(), BaseOffset);
+      auto &TransPtr = Inserted.first->second;
+      if (!Inserted.second) {
+        if (TransAddr.getAddr() != TransPtr.first ||
+            BaseOffset != TransPtr.second)
+          // We already visited this block before. If it was with a different
+          // address - bail out!
+          return PhiTransPtr{};
+        continue;
+      }
+
+      if (PredBB == ToBB) {
+        ResPtr = TransPtr;
+        continue;
+      }
+
+      WorkList.push_back({PredBB, TransPtr});
+    }
+  }
+
+  assert(ResPtr.first.pointsToAliveValue() &&
+         "PHI translation is expected to complete successfully");
+  return ResPtr;
+}
+
+static ExMemoryAccess
+phiTransFromMemoryAccessTo(const ExMemoryAccess &FromAccess,
+                           MemoryAccess *ToAccess, const DataLayout &DL,
+                           DominatorTree &DT, AssumptionCache *AC) {
+  PhiTransPtr ResAddr;
+
+  if (FromAccess.second.first.pointsToAliveValue()) {
+
+    ResAddr = phiTranslatePtr(FromAccess.second, FromAccess.first->getBlock(),
+                               ToAccess->getBlock(), DL, DT, AC);
+  }
+
+  return std::make_pair(ToAccess, ResAddr);
+}
+
+static ExMemoryAccess getExDefiningAccess(const ExMemoryAccess &CurrAccess,
+                                          const DataLayout &DL, DominatorTree &DT,
+                                          AssumptionCache *AC) {
+  assert(isa<MemoryUseOrDef>(CurrAccess.first) && "TODO");
+  MemoryAccess *Next =
+      cast<MemoryUseOrDef>(CurrAccess.first)->getDefiningAccess();
+  return phiTransFromMemoryAccessTo(CurrAccess, Next, DL, DT, AC);
+}
+
 struct DSEState {
   Function &F;
   AliasAnalysis &AA;
 
   /// The single BatchAA instance that is used to cache AA queries. It will
   /// not be invalidated over the whole run. This is safe, because:
   /// 1. Only memory writes are removed, so the alias cache for memory
   ///    locations remains valid.
   /// 2. No new instructions are added (only instructions removed), so cached
   ///    information for a deleted value cannot be accessed by a re-used new
   ///    value pointer.
   BatchAAResults BatchAA;
 
   MemorySSA &MSSA;
   DominatorTree &DT;
   PostDominatorTree &PDT;
   const TargetLibraryInfo &TLI;
   const DataLayout &DL;
   const LoopInfo &LI;
+  AssumptionCache *AC;
 
   // Whether the function contains any irreducible control flow, useful for
   // being accurately able to detect loops.
   bool ContainsIrreducibleLoops;
 
   // All MemoryDefs that potentially could kill other MemDefs.
   SmallVector<MemoryDef *, 64> MemDefs;
   // Any that should be skipped as they are already deleted
struct DSEState {
   DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
 
   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
   /// basic block.
   DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;
 
   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
            PostDominatorTree &PDT, const TargetLibraryInfo &TLI,
-           const LoopInfo &LI)
+           const LoopInfo &LI, AssumptionCache *AC)
       : F(F), AA(AA), BatchAA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI),
-        DL(F.getParent()->getDataLayout()), LI(LI) {}
+        DL(F.getParent()->getDataLayout()), LI(LI), AC(AC),
+        ContainsIrreducibleLoops(false) {}
 
   static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                       DominatorTree &DT, PostDominatorTree &PDT,
-                      const TargetLibraryInfo &TLI, const LoopInfo &LI) {
-    DSEState State(F, AA, MSSA, DT, PDT, TLI, LI);
+                      const TargetLibraryInfo &TLI, const LoopInfo &LI,
+                      AssumptionCache *AC) {
+    DSEState State(F, AA, MSSA, DT, PDT, TLI, LI, AC);
     // Collect blocks with throwing instructions not modeled in MemorySSA and
     // alloc-like objects.
     unsigned PO = 0;
     for (BasicBlock *BB : post_order(&F)) {
       State.PostOrderNumbers[BB] = PO++;
       for (Instruction &I : *BB) {
         MemoryAccess *MA = MSSA.getMemoryAccess(&I);
         if (I.mayThrow() && !MA)
struct DSEState {
   }
 
   // Find a MemoryDef writing to \p DefLoc and dominating \p StartAccess, with
   // no read access between them or on any other path to a function exit block
   // if \p DefLoc is not accessible after the function returns. If there is no
   // such MemoryDef, return None. The returned value may not (completely)
   // overwrite \p DefLoc. Currently we bail out when we encounter an aliasing
   // MemoryUse (read).
-  Optional<MemoryAccess *>
-  getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *StartAccess,
+  Optional<ExMemoryAccess>
+  getDomMemoryDef(MemoryDef *KillingDef, const ExMemoryAccess &ExStartAccess,
                   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;
     }
 
-    MemoryAccess *Current = StartAccess;
+    MemoryAccess * const StartAccess = ExStartAccess.first;
     Instruction *KillingI = KillingDef->getMemoryInst();
     LLVM_DEBUG(dbgs() << "  trying to get dominating access\n");
 
-    // Find the next clobbering Mod access for DefLoc, starting at StartAccess.
+    ExMemoryAccess ExCurrentAccess = ExStartAccess;
     Optional<MemoryLocation> CurrentLoc;
-    for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
+    MemoryLocation PhiTransKillingLoc(KillingLoc.Ptr, KillingLoc.Size,
+                                      KillingLoc.AATags);
+    int64_t PhiTransKillingPtrOffset = 0;
+
+    // Find the next clobbering Mod access for KillingLoc, starting at
+    // StartAccess.
+    for (;;
+         ExCurrentAccess = getExDefiningAccess(ExCurrentAccess, DL, DT, AC)) {
+      MemoryAccess *CurrentAccess = ExCurrentAccess.first;
+
+      if (ExCurrentAccess.second.first.pointsToAliveValue()) {
+        PhiTransKillingLoc.Ptr = ExCurrentAccess.second.first;
+        PhiTransKillingPtrOffset = ExCurrentAccess.second.second;
+      } else {
+        PhiTransKillingLoc.Ptr = KillingLoc.Ptr;
+        PhiTransKillingPtrOffset = 0;
+      }
+
       LLVM_DEBUG({
-        dbgs() << "   visiting " << *Current;
-        if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef>(Current))
-          dbgs() << " (" << *cast<MemoryUseOrDef>(Current)->getMemoryInst()
+        dbgs() << "   visiting " << *CurrentAccess;
+        if (!MSSA.isLiveOnEntryDef(CurrentAccess) &&
+            isa<MemoryUseOrDef>(CurrentAccess))
+          dbgs() << " ("
+                 << *cast<MemoryUseOrDef>(CurrentAccess)->getMemoryInst()
                  << ")";
         dbgs() << "\n";
       });
 
       // Reached TOP.
-      if (MSSA.isLiveOnEntryDef(Current)) {
+      if (MSSA.isLiveOnEntryDef(CurrentAccess)) {
         LLVM_DEBUG(dbgs() << "   ...  found LiveOnEntryDef\n");
         return None;
       }
 
       // Cost of a step. Accesses in the same block are more likely to be valid
       // candidates for elimination, hence consider them cheaper.
-      unsigned StepCost = KillingDef->getBlock() == Current->getBlock()
+      unsigned StepCost = KillingDef->getBlock() == CurrentAccess->getBlock()
                               ? MemorySSASameBBStepCost
                               : MemorySSAOtherBBStepCost;
       if (WalkerStepLimit <= StepCost) {
         LLVM_DEBUG(dbgs() << "   ...  hit walker step limit\n");
         return None;
       }
       WalkerStepLimit -= StepCost;
 
       // Return for MemoryPhis. They cannot be eliminated directly and the
       // caller is responsible for traversing them.
-      if (isa<MemoryPhi>(Current)) {
+      if (isa<MemoryPhi>(CurrentAccess)) {
         LLVM_DEBUG(dbgs() << "   ...  found MemoryPhi\n");
-        return Current;
+        return ExCurrentAccess;
       }
 
       // 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);
+      MemoryDef *CurrentDef = cast<MemoryDef>(CurrentAccess);
       Instruction *CurrentI = CurrentDef->getMemoryInst();
 
       if (canSkipDef(CurrentDef, !isInvisibleToCallerBeforeRet(KillingUndObj)))
         continue;
 
       // Before we try to remove anything, check for any extra throwing
       // instructions that block us from DSEing
       if (mayThrowBetween(KillingI, CurrentI, KillingUndObj)) {
         LLVM_DEBUG(dbgs() << "  ... skip, may throw!\n");
         return None;
       }
 
       // Check for anything that looks like it will be a barrier to further
       // removal
       if (isDSEBarrier(KillingUndObj, CurrentI)) {
         LLVM_DEBUG(dbgs() << "  ... skip, barrier\n");
         return None;
       }
 
       // If Current does not have an analyzable write location, skip it
+      int64_t CurrOffset = 0;
       CurrentLoc = getLocForWriteEx(CurrentI);
       if (!CurrentLoc)
         continue;
 
-      // If Current is known to be on path that reads DefLoc or is a read
+      // If Current is known to be on path that reads KillingLoc 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(KillingI, KillingLoc, 0, CurrentI, CurrentLoc, 0))
+          isReadClobber(KillingI, PhiTransKillingLoc, PhiTransKillingPtrOffset,
+                        CurrentI, CurrentLoc, CurrOffset))
         return None;
 
       // Quick check if there are direct uses that are read-clobbers.
-      if (any_of(Current->uses(), [this, KillingI, &KillingLoc,
+      if (any_of(CurrentAccess->uses(), [this, KillingI, &KillingLoc,
                                    StartAccess](Use &U) {
             if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser())) {
               auto *UseInst = UseOrDef->getMemoryInst();
               return !MSSA.dominates(StartAccess, UseOrDef) &&
                      isReadClobber(KillingI, KillingLoc, 0, UseInst);
             }
             return false;
           })) {
for (;;
 
       if (IsMemTerm) {
         // If the killing def is a memory terminator (e.g. lifetime.end), check
         // the next candidate if the current Current does not write the same
         // underlying object as the terminator.
         if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI))
           continue;
       } else {
-        int64_t KillingOffset = 0;
-        int64_t KilledOffset = 0;
-        auto OR = isOverwrite(KillingI, CurrentI, KillingLoc, *CurrentLoc,
-                              KillingOffset, KilledOffset);
+        auto OR =
+            isOverwrite(KillingI, CurrentI, PhiTransKillingLoc, *CurrentLoc,
+                        PhiTransKillingPtrOffset, CurrOffset);
         // If Current does not write to the same object as KillingDef, check
         // the next candidate.
         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,
getDomMemoryDef(MemoryDef *KillingDef, const ExMemoryAccess &ExStartAccess,
     };
 
     // Accesses to objects accessible after the function returns can only be
     // eliminated if the access is killed along all paths to the exit. Collect
     // the blocks with killing (=completely overwriting MemoryDefs) and check if
     // they cover all paths from KilledAccess to any function exit.
     SmallPtrSet<Instruction *, 16> KillingDefs;
     KillingDefs.insert(KillingDef->getMemoryInst());
-    MemoryAccess *KilledAccess = Current;
+    MemoryAccess *KilledAccess = ExCurrentAccess.first;
     MemoryLocation KilledLoc = *CurrentLoc;
-    Instruction *KilledI =
-        cast<MemoryDef>(KilledAccess)->getMemoryInst();
+    Instruction *KilledI = cast<MemoryDef>(KilledAccess)->getMemoryInst();
     LLVM_DEBUG(dbgs() << "  Checking for reads of " << *KilledAccess << " ("
                       << *KilledI << ")\n");
 
     SmallSetVector<MemoryAccess *, 32> WorkList;
     auto PushMemUses = [&WorkList](MemoryAccess *Acc) {
       for (Use &U : Acc->uses())
         WorkList.insert(cast<MemoryAccess>(U.getUser()));
     };
if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
           break;
         CommonPred = PDT.findNearestCommonDominator(CommonPred, *I);
       }
 
       // If CommonPred is in the set of killing blocks, just check if it
       // post-dominates KilledAccess.
       if (KillingBlocks.count(CommonPred)) {
         if (PDT.dominates(CommonPred, KilledAccess->getBlock()))
-          return {KilledAccess};
+          return {ExCurrentAccess};
         return None;
       }
 
       // If the common post-dominator does not post-dominate KilledAccess,
       // there is a path from KilledAccess to an exit not going through a
       // killing block.
       if (PDT.dominates(CommonPred, KilledAccess->getBlock())) {
         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())
             WorkList.insert(R);
 
         NumCFGTries++;
         // Check if all paths starting from an exit node go through one of the
         // killing blocks before reaching KilledAccess.
         for (unsigned I = 0; I < WorkList.size(); I++) {
           NumCFGChecks++;
-          BasicBlock *Current = WorkList[I];
-          if (KillingBlocks.count(Current))
+          BasicBlock *CurrentBB = WorkList[I];
+          if (KillingBlocks.count(CurrentBB))
             continue;
-          if (Current == KilledAccess->getBlock())
+          if (CurrentBB == KilledAccess->getBlock())
             return None;
 
           // KilledAccess is reachable from the entry, so we don't have to
           // explore unreachable blocks further.
-          if (!DT.isReachableFromEntry(Current))
+          if (!DT.isReachableFromEntry(CurrentBB))
             continue;
 
-          for (BasicBlock *Pred : predecessors(Current))
+          for (BasicBlock *Pred : predecessors(CurrentBB))
             WorkList.insert(Pred);
 
           if (WorkList.size() >= MemorySSAPathCheckLimit)
             return None;
         }
         NumCFGSuccess++;
-        return {KilledAccess};
+        return {ExCurrentAccess};
       }
       return None;
     }
 
     // No aliasing MemoryUses of KilledAccess found, KilledAccess is
     // potentially dead.
-    return {KilledAccess};
+    return {ExCurrentAccess};
   }
 
   // Delete dead memory defs
   void deleteDeadInstruction(Instruction *SI) {
     MemorySSAUpdater Updater(&MSSA);
     SmallVector<Instruction *, 32> NowDeadInsts;
     NowDeadInsts.push_back(SI);
     --NumFastOther;
bool storeIsNoop(MemoryDef *Def, const MemoryLocation &DefLoc,
 
     return false;
   }
 };
 
 static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                                 DominatorTree &DT, PostDominatorTree &PDT,
                                 const TargetLibraryInfo &TLI,
-                                const LoopInfo &LI) {
+                                const LoopInfo &LI, AssumptionCache *AC) {
   bool MadeChange = false;
 
-  DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI, LI);
+  const DataLayout &DL = F.getParent()->getDataLayout();
+  DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI, LI, AC);
   // For each store:
   for (unsigned I = 0; I < State.MemDefs.size(); I++) {
     MemoryDef *KillingDef = State.MemDefs[I];
     if (State.SkipStores.count(KillingDef))
       continue;
     Instruction *KillingI = KillingDef->getMemoryInst();
 
     Optional<MemoryLocation> MaybeKillingLoc;
     if (State.isMemTerminatorInst(KillingI))
       MaybeKillingLoc = State.getLocForTerminator(KillingI).map(
           [](const std::pair<MemoryLocation, bool> &P) { return P.first; });
     else
       MaybeKillingLoc = State.getLocForWriteEx(KillingI);
 
     if (!MaybeKillingLoc) {
       LLVM_DEBUG(dbgs() << "Failed to find analyzable write location for "
                         << *KillingI << "\n");
       continue;
     }
     MemoryLocation KillingLoc = *MaybeKillingLoc;
     assert(KillingLoc.Ptr && "KillingLoc should not be null");
     const Value *KillingUndObj = getUnderlyingObject(KillingLoc.Ptr);
 
-    MemoryAccess *Current = KillingDef;
     LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by "
                       << *KillingDef << " (" << *KillingI << ")\n");
 
     unsigned ScanLimit = MemorySSAScanLimit;
     unsigned WalkerStepLimit = MemorySSAUpwardsStepLimit;
     unsigned PartialLimit = MemorySSAPartialStoreLimit;
     // Worklist of MemoryAccesses that may be killed by KillingDef.
-    SetVector<MemoryAccess *> ToCheck;
+    SmallVector<ExMemoryAccess> ToCheck;
 
-    if (KillingUndObj)
-      ToCheck.insert(KillingDef->getDefiningAccess());
+    if (KillingUndObj) {
+      ExMemoryAccess ExKillingDef{KillingDef,
+                                  {const_cast<Value *>(KillingLoc.Ptr), 0}};
+      ToCheck.push_back(getExDefiningAccess(ExKillingDef, DL, DT, AC));
+    }
 
     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++) {
-      Current = ToCheck[I];
+    while (!ToCheck.empty()) {
+      const ExMemoryAccess CurrentAccess = ToCheck.pop_back_val();
+      MemoryAccess *Current = CurrentAccess.first;
       if (State.SkipStores.count(Current))
         continue;
 
-      Optional<MemoryAccess *> MaybeKilledAccess = State.getDomMemoryDef(
-          KillingDef, Current, KillingLoc, KillingUndObj, ScanLimit, WalkerStepLimit,
-          IsMemTerm, PartialLimit);
+      Optional<ExMemoryAccess> MaybeKilledAccess = State.getDomMemoryDef(
+          KillingDef, CurrentAccess, KillingLoc, KillingUndObj, ScanLimit,
+          WalkerStepLimit, IsMemTerm, PartialLimit);
 
       if (!MaybeKilledAccess) {
         LLVM_DEBUG(dbgs() << "  finished walk\n");
         continue;
       }
 
-      MemoryAccess *KilledAccess = *MaybeKilledAccess;
+      ExMemoryAccess &ExKilledAccess = *MaybeKilledAccess;
+      MemoryAccess *KilledAccess = ExKilledAccess.first;
       LLVM_DEBUG(dbgs() << " Checking if we can kill " << *KilledAccess);
       if (isa<MemoryPhi>(KilledAccess)) {
         LLVM_DEBUG(dbgs() << "\n  ... adding incoming values to worklist\n");
         for (Value *V : cast<MemoryPhi>(KilledAccess)->incoming_values()) {
           MemoryAccess *IncomingAccess = cast<MemoryAccess>(V);
           BasicBlock *IncomingBlock = IncomingAccess->getBlock();
           BasicBlock *PhiBlock = KilledAccess->getBlock();
 
           // We only consider incoming MemoryAccesses that come before the
           // MemoryPhi. Otherwise we could discover candidates that do not
           // strictly dominate our starting def.
           if (State.PostOrderNumbers[IncomingBlock] >
               State.PostOrderNumbers[PhiBlock])
-            ToCheck.insert(IncomingAccess);
+            ToCheck.push_back(phiTransFromMemoryAccessTo(
+                ExKilledAccess, IncomingAccess, DL, DT, AC));
         }
         continue;
       }
       auto *KilledDefAccess = cast<MemoryDef>(KilledAccess);
       Instruction *KilledI = KilledDefAccess->getMemoryInst();
       LLVM_DEBUG(dbgs() << " (" << *KilledI << ")\n");
-      ToCheck.insert(KilledDefAccess->getDefiningAccess());
+      ToCheck.push_back(getExDefiningAccess(ExKilledAccess, DL, DT, AC));
       NumGetDomMemoryDefPassed++;
 
       if (!DebugCounter::shouldExecute(MemorySSACounter))
         continue;
 
       MemoryLocation KilledLoc = *State.getLocForWriteEx(KilledI);
 
       if (IsMemTerm) {
         const Value *KilledUndObj = getUnderlyingObject(KilledLoc.Ptr);
         if (KillingUndObj != KilledUndObj)
           continue;
         LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *KilledI
                           << "\n  KILLER: " << *KillingI << '\n');
         State.deleteDeadInstruction(KilledI);
         ++NumFastStores;
         MadeChange = true;
       } else {
         // Check if KilledI overwrites KillingI.
         int64_t KillingOffset = 0;
         int64_t KilledOffset = 0;
+
+        if (ExKilledAccess.second.first.pointsToAliveValue()) {
+          KillingLoc.Ptr = ExKilledAccess.second.first;
+          KillingOffset = ExKilledAccess.second.second;
+        }
+
         OverwriteResult OR =
             State.isOverwrite(KillingI, KilledI, KillingLoc, KilledLoc,
                               KillingOffset, KilledOffset);
         if (OR == OW_MaybePartial) {
           auto Iter = State.IOLs.insert(
               std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
                   KilledI->getParent(), InstOverlapIntervalsTy()));
           auto &IOL = Iter.first->second;

 //===----------------------------------------------------------------------===//
 PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
   AliasAnalysis &AA = AM.getResult<AAManager>(F);
   const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
   MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
   PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
   LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
+  AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
 
-  bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI);
+  bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI, &AC);
 
 #ifdef LLVM_ENABLE_STATS
   if (AreStatisticsEnabled())
     for (auto &I : instructions(F))
       NumRemainingStores += isa<StoreInst>(&I);
 #endif
 
   if (!Changed)
bool runOnFunction(Function &F) override {
     AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     const TargetLibraryInfo &TLI =
         getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
     MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
     PostDominatorTree &PDT =
         getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
     LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+    AssumptionCache &AC =
+        getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
 
-    bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI);
+    bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI, &AC);
 
 #ifdef LLVM_ENABLE_STATS
     if (AreStatisticsEnabled())
       for (auto &I : instructions(F))
         NumRemainingStores += isa<StoreInst>(&I);
 #endif
 
     return Changed;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addRequired<PostDominatorTreeWrapperPass>();
     AU.addRequired<MemorySSAWrapperPass>();
     AU.addPreserved<PostDominatorTreeWrapperPass>();
     AU.addPreserved<MemorySSAWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addPreserved<LoopInfoWrapperPass>();
+    AU.addRequired<AssumptionCacheTracker>();
+    AU.addPreserved<AssumptionCacheTracker>();
   }
 };
 
 } // end anonymous namespace
 
 char DSELegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,

llvm/test/Transforms/DeadStoreElimination/phi-translation.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -dse -S %s | FileCheck %s
 
-; TODO: Both the stores in %then and %else can be eliminated by translating %p
+; Both the stores in %then and %else can be eliminated by translating %p
 ; through the phi.
 define void @memoryphi_translate_1(i1 %c) {
 ; CHECK-LABEL: @memoryphi_translate_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_1:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    [[A_2:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
-; CHECK-NEXT:    store i8 0, i8* [[A_1]], align 1
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       else:
-; CHECK-NEXT:    store i8 9, i8* [[A_2]], align 1
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ]
 ; CHECK-NEXT:    store i8 10, i8* [[P]], align 1
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a.1 = alloca i8
else:
   br label %end
 
 end:
   %p = phi i8* [ %a.1, %then ], [ %a.2, %else ]
   store i8 10, i8* %p
   ret void
 }
 
-; TODO: The store in %else can be eliminated by translating %p through the phi.
+; The store in %else can be eliminated by translating %p through the phi.
 ; The store in %then cannot be eliminated, because %a.1 is read before the final
 ; store.
 define i8 @memoryphi_translate_2(i1 %c) {
 ; CHECK-LABEL: @memoryphi_translate_2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_1:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    [[A_2:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    store i8 0, i8* [[A_1]], align 1
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       else:
-; CHECK-NEXT:    store i8 9, i8* [[A_2]], align 1
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ]
 ; CHECK-NEXT:    [[L:%.*]] = load i8, i8* [[A_1]], align 1
 ; CHECK-NEXT:    store i8 10, i8* [[P]], align 1
 ; CHECK-NEXT:    ret i8 [[L]]
 ;
 entry:

 
 end:
   %p = phi i8* [ %a.1, %then ], [ %a.2, %else ]
   %l = load i8, i8* %a.1
   store i8 10, i8* %p
   ret i8 %l
 }
 
-; TODO: The store in %then can be eliminated by translating %p through the phi.
+; The store in %then can be eliminated by translating %p through the phi.
 ; The store in %else cannot be eliminated, because %a.2 is read before the final
 ; store.
 define i8 @memoryphi_translate_3(i1 %c) {
 ; CHECK-LABEL: @memoryphi_translate_3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_1:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    [[A_2:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
-; CHECK-NEXT:    store i8 0, i8* [[A_1]], align 1
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       else:
 ; CHECK-NEXT:    store i8 9, i8* [[A_2]], align 1
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ]
 ; CHECK-NEXT:    [[L:%.*]] = load i8, i8* [[A_2]], align 1
 ; CHECK-NEXT:    store i8 10, i8* [[P]], align 1

 ; CHECK-LABEL: @test_trans_null(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       else:
 ; CHECK-NEXT:    call void @fn()
 ; CHECK-NEXT:    [[BC:%.*]] = bitcast i8* undef to i16*
-; CHECK-NEXT:    [[GEP_1:%.*]] = getelementptr inbounds i16, i16* [[BC]], i64 2
-; CHECK-NEXT:    store i16 8, i16* [[GEP_1]], align 2
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[P:%.*]] = phi i16* [ [[PTR:%.*]], [[THEN]] ], [ [[BC]], [[ELSE]] ]
 ; CHECK-NEXT:    [[GEP_2:%.*]] = getelementptr inbounds i16, i16* [[P]], i64 2
 ; CHECK-NEXT:    store i16 8, i16* [[GEP_2]], align 2
 ; CHECK-NEXT:    ret void
 ;
 entry: