[DSE] Rewrite function memoryIsNotModified using MemorySSA

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

386

Do I understand correctly that another precondition of this code is now that FirstI must mod SecondI? Otherwise the walk may go past FirstI and an incorrect modification would be reported?

I think it would be better to do a domination check, as in https://github.com/llvm/llvm-project/blob/419580c699481de40f1e819c396fe07a63885b43/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp#L369.

We should also assert that SecondI is a MemoryDef, for MemoryUses different logic is required.

I'm also slightly concerned that this may produce incorrect results for the loop varying case if SecondI is a call, as MSSA has a known issue in this area.

[StephenFan]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

386

Thanks for reviewing! Would you mind posting a test case that can reflect the known issue?

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

386

See https://github.com/llvm/llvm-project/issues/54682.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

static OverwriteResult isPartialOverwrite(const MemoryLocation &KillingLoc,
   }
   // Otherwise, they don't completely overlap.
   return OW_Unknown;
 }
 
 /// Returns true if the memory which is accessed by the second instruction is not
 /// modified between the first and the second instruction.
 /// Precondition: Second instruction must be dominated by the first
 /// instruction.
-static bool
-memoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI,
-                           BatchAAResults &AA, const DataLayout &DL,
-                           DominatorTree *DT) {
-  // Do a backwards scan through the CFG from SecondI to FirstI. Look for
-  // instructions which can modify the memory location accessed by SecondI.
-  //
-  // While doing the walk keep track of the address to check. It might be
-  // different in different basic blocks due to PHI translation.
-  using BlockAddressPair = std::pair<BasicBlock *, PHITransAddr>;
-  SmallVector<BlockAddressPair, 16> WorkList;
-  // Keep track of the address we visited each block with. Bail out if we
-  // visit a block with different addresses.
-  DenseMap<BasicBlock *, Value *> Visited;
-
-  BasicBlock::iterator FirstBBI(FirstI);
-  ++FirstBBI;
-  BasicBlock::iterator SecondBBI(SecondI);
-  BasicBlock *FirstBB = FirstI->getParent();
-  BasicBlock *SecondBB = SecondI->getParent();
-  MemoryLocation MemLoc;
-  if (auto *MemSet = dyn_cast<MemSetInst>(SecondI))
-    MemLoc = MemoryLocation::getForDest(MemSet);
-  else
-    MemLoc = MemoryLocation::get(SecondI);
-
-  auto *MemLocPtr = const_cast<Value *>(MemLoc.Ptr);
-
-  // Start checking the SecondBB.
-  WorkList.push_back(
-      std::make_pair(SecondBB, PHITransAddr(MemLocPtr, DL, nullptr)));
-  bool isFirstBlock = true;
-
-  // Check all blocks going backward until we reach the FirstBB.
-  while (!WorkList.empty()) {
-    BlockAddressPair Current = WorkList.pop_back_val();
-    BasicBlock *B = Current.first;
-    PHITransAddr &Addr = Current.second;
-    Value *Ptr = Addr.getAddr();
-
-    // Ignore instructions before FirstI if this is the FirstBB.
-    BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());
-
-    BasicBlock::iterator EI;
-    if (isFirstBlock) {
-      // Ignore instructions after SecondI if this is the first visit of SecondBB.
-      assert(B == SecondBB && "first block is not the store block");
-      EI = SecondBBI;
-      isFirstBlock = false;
-    } else {
-      // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
-      // In this case we also have to look at instructions after SecondI.
-      EI = B->end();
-    }
-    for (; BI != EI; ++BI) {
-      Instruction *I = &*BI;
-      if (I->mayWriteToMemory() && I != SecondI)
-        if (isModSet(AA.getModRefInfo(I, MemLoc.getWithNewPtr(Ptr))))
-          return false;
-    }
-    if (B != FirstBB) {
-      assert(B != &FirstBB->getParent()->getEntryBlock() &&
-          "Should not hit the entry block because SI must be dominated by LI");
-      for (BasicBlock *Pred : predecessors(B)) {
-        PHITransAddr PredAddr = Addr;
-        if (PredAddr.NeedsPHITranslationFromBlock(B)) {
-          if (!PredAddr.IsPotentiallyPHITranslatable())
-            return false;
-          if (PredAddr.PHITranslateValue(B, Pred, DT, false))
-            return false;
-        }
-        Value *TranslatedPtr = PredAddr.getAddr();
-        auto Inserted = Visited.insert(std::make_pair(Pred, TranslatedPtr));
-        if (!Inserted.second) {
-          // We already visited this block before. If it was with a different
-          // address - bail out!
-          if (TranslatedPtr != Inserted.first->second)
-            return false;
-          // ... otherwise just skip it.
-          continue;
-        }
-        WorkList.push_back(std::make_pair(Pred, PredAddr));
-      }
-    }
-  }
+static bool memoryIsNotModifiedBetween(MemorySSA &MSSA, Instruction *FirstI,
+                                       Instruction *SecondI) {
+  MemoryAccess *Def = MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(
+      MSSA.getMemoryAccess(SecondI));
+  if (!MSSA.isLiveOnEntryDef(Def) && Def != MSSA.getMemoryAccess(FirstI))
   return true;
 }
 
 static bool tryToShorten(Instruction *DeadI, int64_t &DeadStart,
                          uint64_t &DeadSize, int64_t KillingStart,
                          uint64_t KillingSize, bool IsOverwriteEnd) {
   auto *DeadIntrinsic = cast<AnyMemIntrinsic>(DeadI);
   Align PrefAlign = DeadIntrinsic->getDestAlign().valueOrOne();
if (KillingStart <= DeadStart &&
     }
   }
   return false;
 }
 
 static Constant *
 tryToMergePartialOverlappingStores(StoreInst *KillingI, StoreInst *DeadI,
                                    int64_t KillingOffset, int64_t DeadOffset,
-                                   const DataLayout &DL, BatchAAResults &AA,
-                                   DominatorTree *DT) {
+                                   const DataLayout &DL, MemorySSA &MSSA) {
 
   if (DeadI && isa<ConstantInt>(DeadI->getValueOperand()) &&
       DL.typeSizeEqualsStoreSize(DeadI->getValueOperand()->getType()) &&
       KillingI && isa<ConstantInt>(KillingI->getValueOperand()) &&
       DL.typeSizeEqualsStoreSize(KillingI->getValueOperand()->getType()) &&
-      memoryIsNotModifiedBetween(DeadI, KillingI, AA, DL, DT)) {
+      memoryIsNotModifiedBetween(MSSA, DeadI, KillingI)) {
     // If the store we find is:
     //   a) partially overwritten by the store to 'Loc'
     //   b) the killing store is fully contained in the dead one and
     //   c) they both have a constant value
     //   d) none of the two stores need padding
     // Merge the two stores, replacing the dead store's value with a
     // merge of both values.
     // TODO: Deal with other constant types (vectors, etc), and probably
auto shouldCreateCalloc = [](CallInst *Malloc, CallInst *Memset) {
         return false;
       if (Pred != ICmpInst::ICMP_EQ || MemsetBB != FalseBB)
         return false;
       return true;
     };
 
     if (Malloc->getOperand(0) != MemSet->getLength())
       return false;
-    if (!shouldCreateCalloc(Malloc, MemSet) ||
-        !DT.dominates(Malloc, MemSet) ||
-        !memoryIsNotModifiedBetween(Malloc, MemSet, BatchAA, DL, &DT))
+    if (!shouldCreateCalloc(Malloc, MemSet) || !DT.dominates(Malloc, MemSet) ||
+        !memoryIsNotModifiedBetween(MSSA, Malloc, MemSet))
       return false;
     IRBuilder<> IRB(Malloc);
     const auto &DL = Malloc->getModule()->getDataLayout();
     auto *Calloc =
       emitCalloc(ConstantInt::get(IRB.getIntPtrTy(DL), 1),
                  Malloc->getArgOperand(0), IRB, TLI);
     if (!Calloc)
       return false;
for (unsigned I = 0; I < ToCheck.size(); I++) {
           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.
           if (DeadSI && KillingSI && DT.dominates(DeadSI, KillingSI)) {
             if (Constant *Merged = tryToMergePartialOverlappingStores(
                     KillingSI, DeadSI, KillingOffset, DeadOffset, State.DL,
-                    State.BatchAA, &DT)) {
+                    MSSA)) {
 
               // 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