[DSE] Revisit pointers that may no longer escape after removing another store

[aeubanks]

Summary

In dependent-capture, previously we'd see that %tmp4 is captured due to
the first store. We'd cache this info in CapturedBeforeReturn and
InvisibleToCallerAfterRet. Then the first store is then removed, causing
the cached values to be wrong.

We also need to revisit everything because normally we work backwards
when removing stores at the end of the function, but in this case
removing an earlier store causes a later store to be removable.

No compile time impact:
https://llvm-compile-time-tracker.com/compare.php?from=32f3633171aa9d7352e9507c12d219efb48899a0&to=f1dc620e55635a69250d011c1a9950c45a364264&stat=instructions

[asbirlea]

LGTM.

[fhahn]

I am surprised that this doesn't have a noticeable compile-time impact on CTMark, but then it also doesn't cause any binary changes, so the test binaries there probably won't cause too many additional iterations. IIUC we should be able to at least safe 1 unnecessary extra iteration if we would check if an underlying object got removed from CapturedBeforeReturn?

[aeubanks]

only rerun if we remove something from CapturedBeforeReturn

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

while (!NowDeadInsts.empty()) {
       // Try to preserve debug information attached to the dead instruction.
       salvageDebugInfo(*DeadInst);
       salvageKnowledge(DeadInst);
 
       // Remove the Instruction from MSSA.
       if (MemoryAccess *MA = MSSA.getMemoryAccess(DeadInst)) {
         if (MemoryDef *MD = dyn_cast<MemoryDef>(MA)) {
           SkipStores.insert(MD);
+          if (auto *SI = dyn_cast<StoreInst>(MD->getMemoryInst())) {
+            if (SI->getValueOperand()->getType()->isPointerTy()) {
+              const Value *UO = getUnderlyingObject(SI->getValueOperand());
+              CapturedBeforeReturn.erase(UO);
+              InvisibleToCallerAfterRet.erase(UO);
+            }
+          }
         }
 
         Updater.removeMemoryAccess(MA);
       }
 
       auto I = IOLs.find(DeadInst->getParent());
       if (I != IOLs.end())
         I->second.erase(DeadInst);
bool isDSEBarrier(const Value *KillingUndObj, Instruction *DeadI) {
     }
     return false;
   }
 
   /// Eliminate writes to objects that are not visible in the caller and are not
   /// accessed before returning from the function.
   bool eliminateDeadWritesAtEndOfFunction() {
     bool MadeChange = false;
+    bool MadeChangeThisIteration;
     LLVM_DEBUG(
         dbgs()
         << "Trying to eliminate MemoryDefs at the end of the function\n");
+    do {
+      MadeChangeThisIteration = false;
       for (MemoryDef *Def : llvm::reverse(MemDefs)) {
         if (SkipStores.contains(Def))
           continue;
 
         Instruction *DefI = Def->getMemoryInst();
         auto DefLoc = getLocForWrite(DefI);
         if (!DefLoc || !isRemovable(DefI))
           continue;
 
-      // NOTE: Currently eliminating writes at the end of a function is limited
-      // to MemoryDefs with a single underlying object, to save compile-time. In
-      // practice it appears the case with multiple underlying objects is very
-      // uncommon. If it turns out to be important, we can use
-      // getUnderlyingObjects here instead.
+        // NOTE: Currently eliminating writes at the end of a function is
+        // limited to MemoryDefs with a single underlying object, to save
+        // compile-time. In practice it appears the case with multiple
+        // underlying objects is very uncommon. If it turns out to be important,
+        // we can use getUnderlyingObjects here instead.
         const Value *UO = getUnderlyingObject(DefLoc->Ptr);
         if (!isInvisibleToCallerAfterRet(UO))
           continue;
 
         if (isWriteAtEndOfFunction(Def)) {
           // See through pointer-to-pointer bitcasts
           LLVM_DEBUG(dbgs() << "   ... MemoryDef is not accessed until the end "
                                "of the function\n");
           deleteDeadInstruction(DefI);
           ++NumFastStores;
           MadeChange = true;
+          MadeChangeThisIteration = true;
         }
       }
+    } while (MadeChangeThisIteration);
     return MadeChange;
   }
 
   /// If we have a zero initializing memset following a call to malloc,
   /// try folding it into a call to calloc.
   bool tryFoldIntoCalloc(MemoryDef *Def, const Value *DefUO) {
     Instruction *DefI = Def->getMemoryInst();
     MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);

llvm/test/Transforms/DeadStoreElimination/dependent-capture.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=dse -S < %s | FileCheck %s
 
 define void @f() {
 ; CHECK-LABEL: @f(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call noalias ptr @_Znwm()
 ; CHECK-NEXT:    [[TMP4:%.*]] = call noalias ptr @_Znwm()
-; CHECK-NEXT:    store i8 0, ptr [[TMP4]], align 1
 ; CHECK-NEXT:    ret void
 ;
   %tmp1 = call noalias ptr @_Znwm()
   %tmp4 = call noalias ptr @_Znwm()
   store ptr %tmp4, ptr %tmp1
   store i8 0, ptr %tmp4, align 1
   ret void
 }
 
 declare ptr @_Znwm()