[DSE] Queue non-memory dead instructions for later removal.

[fhahn]

Summary

This patch updates DSE's removal strategy to initially only remove the
memory instruction and queue now-dead operands for later removal.

This is required to enable PHI translation while looking for candidates
for removal, because the translated result may reference IR instructions
that would get removed before being used.

[ebrevnov]

I think, more robust approach would be not to depend on existing instructions but create the required ones during phi translation as needed. Phi translation already does this to some extent. In D90095 (which prototypes PHI translation support in DSE) pointers are simplified by GetPointerBaseWithConstantOffset during PHI translation what effectively removes dependencies on existing GEPs and BitCasts.

What is your motivating example?

[fhahn]

In D98287#2707162, @ebrevnov wrote:

I think, more robust approach would be not to depend on existing instructions but create the required ones during phi translation as needed. Phi translation already does this to some extent. In D90095 (which prototypes PHI translation support in DSE) pointers are simplified by GetPointerBaseWithConstantOffset during PHI translation what effectively removes dependencies on existing GEPs and BitCasts.

What is your motivating example?

I think even with GetPointerBaseWithConstantOffset, we could still rely on existing GEPs, e.g. if one of the indices is a non-constant value, so IIUC we could still run into problems when removing such GEPs as we go along?

An example with a crash was shared in D98288. IIUC this could be modified to use an argument value as index in the GEPs to also cause a crash with the GetPointerBaseWithConstantOffset approach.

%"struct.type" = type <{ i8 }>

; Function Attrs: noreturn
define void @f() {
entry:
  br label %while.cond

while.cond:                                       ; preds = %exit, %entry
  br i1 undef, label %if.end.i, label %if.then.i

if.then.i:                                        ; preds = %while.cond
  br label %exit

if.end.i:                                         ; preds = %while.cond
  store i8* undef, i8** inttoptr (i64 16 to i8**), align 16
  %.cast1.i = bitcast i8* undef to %"struct.type"*
  %IsMemberPointer.i.i = getelementptr inbounds %"struct.type", %"struct.type"* %.cast1.i, i64 0, i32 0
  store i8 0, i8* %IsMemberPointer.i.i, align 4
  br label %exit

exit: ; preds = %if.end.i, %if.then.i
  %retval.0.i = phi %"struct.type"* [ undef, %if.then.i ], [ %.cast1.i, %if.end.i ]
  %IsMemberPointer = getelementptr inbounds %"struct.type", %"struct.type"* %retval.0.i, i64 0, i32 0
  store i8 1, i8* %IsMemberPointer, align 4
  br label %while.cond
}

[fhahn]

rebased

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

struct DSEState {
   // Post-order numbers for each basic block. Used to figure out if memory
   // accesses are executed before another access.
   DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
 
   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
   /// basic block.
   DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;
 
+  SetVector<Instruction *> ToRemove;
+
   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
            PostDominatorTree &PDT, const TargetLibraryInfo &TLI,
            const LoopInfo &LI)
       : F(F), AA(AA), BatchAA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI),
         DL(F.getParent()->getDataLayout()), LI(LI) {}
 
   static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                       DominatorTree &DT, PostDominatorTree &PDT,
if (!isInvisibleToCallerAfterRet(DefUO)) {
       return None;
     }
 
     // No aliasing MemoryUses of EarlierAccess found, EarlierAccess is
     // potentially dead.
     return {EarlierAccess};
   }
 
-  // Delete dead memory defs
-  void deleteDeadInstruction(Instruction *SI) {
-    MemorySSAUpdater Updater(&MSSA);
-    SmallVector<Instruction *, 32> NowDeadInsts;
-    NowDeadInsts.push_back(SI);
-    --NumFastOther;
-
-    while (!NowDeadInsts.empty()) {
-      Instruction *DeadInst = NowDeadInsts.pop_back_val();
-      ++NumFastOther;
+  /// Deletes the dead instruction \p DeadInst and queue's any of it's operands
+  /// for removal, if they become dead.
+  void deleteSingleInstruction(Instruction *DeadInst,
+                               MemorySSAUpdater &Updater) {
 
-      // 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);
-        }
-        Updater.removeMemoryAccess(MA);
-      }
 
-      auto I = IOLs.find(DeadInst->getParent());
-      if (I != IOLs.end())
-        I->second.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);
-        }
+    auto Iter = IOLs.find(DeadInst->getParent());
+    if (Iter != IOLs.end())
+      Iter->second.erase(DeadInst);
+          ToRemove.insert(OpI);
 
-      DeadInst->eraseFromParent();
-    }
+
+  /// Delete all instructions in ToRemove and any of their operands, if they
+  /// become dead.
+  void deleteRemainingInsts() {
+    --NumFastOther;
+
+    MemorySSAUpdater Updater(&MSSA);
+    for (unsigned I = 0; I != ToRemove.size(); ++I)
+      deleteSingleInstruction(ToRemove[I], Updater);
+    ToRemove.clear();
+  }
+
+  // Delete dead memory defs
+  void deleteDeadInstruction(Instruction *SI) {
+    MemorySSAUpdater Updater(&MSSA);
+    --NumFastOther;
+    deleteSingleInstruction(SI, Updater);
   }
 
   // Check for any extra throws between SI and NI that block DSE.  This only
   // checks extra maythrows (those that aren't MemoryDef's). MemoryDef that may
   // throw are handled during the walk from one def to the next.
   bool mayThrowBetween(Instruction *SI, Instruction *NI,
                        const Value *SILocUnd) {
     // First see if we can ignore it by using the fact that SI is an
for (int I = MemDefs.size() - 1; I >= 0; I--) {
       if (!UO || !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);
+        // Remove the instructions that become dead after removing DefI, because
+        // it may enable further removal of unused memory instructions.
+        deleteRemainingInsts();
         ++NumFastStores;
         MadeChange = true;
       }
     }
     return MadeChange;
   }
 
   /// \returns true if \p Def is a no-op store, either because it
if (!Shortend && isRemovable(SI) &&
       continue;
     }
   }
 
   if (EnablePartialOverwriteTracking)
     for (auto &KV : State.IOLs)
       MadeChange |= removePartiallyOverlappedStores(State.DL, KV.second, TLI);
 
+  State.deleteRemainingInsts();
   MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
   return MadeChange;
 }
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 // DSE Pass
 //===----------------------------------------------------------------------===//