Fix MemorySSAUpdater::insertDef for dead code

[apilipenko]

Summary

Currently, the attached test case fails with an assert in MemorySSAUpdater::fixupDefs:

// We are now this def's defining access, make sure we actually dominate
// it
assert(MSSA->dominates(NewDef, FirstDef) &&
       "Should have dominated the new access");

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

This happens because we are trying to insert a def in dead code. In this test case GVN attempts to merge baz.invoke block into dead.block (both blocks are dead, i.e. unreachable from entry). This triggers an update to MemorySSA with the following call chain:

MergeBlockIntoPredecessor
  MemorySSAUpdater::moveToPlace
    MemorySSAUpdater::moveTo
      MemorySSAUpdater::insertDef
        MemorySSAUpdater::fixupDefs

fixupDefs asserts that the new defining access dominates the memory access being updated. This assert fails for dead code because DomTree doesn't provide dominance information for blocks not reachable from entry (it simply returns false).

When constructing a fresh MSSA we mark all memory accesses in dead code as live-on-entry. In this patch, I do the same for incremental updates via insertDef.

[fhahn]

LGTM, thanks! Please wait a day or so with committing, in case others have additional comments. In terms of test location, it might be good to place it under Transforms/GVN as this is causing by an update through a transformation. But we are not really strict with avoiding running transforms in Analysis tests, so whatever should be fine.

[asbirlea]

Looks good to me as well.

llvm/lib/Analysis/MemorySSAUpdater.cpp

 
 // A brief description of the algorithm:
 // First, we compute what should define the new def, using the SSA
 // construction algorithm.
 // Then, we update the defs below us (and any new phi nodes) in the graph to
 // point to the correct new defs, to ensure we only have one variable, and no
 // disconnected stores.
 void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
+  // Don't bother updating dead code.
+  if (!MSSA->DT->isReachableFromEntry(MD->getBlock())) {
+    MD->setDefiningAccess(MSSA->getLiveOnEntryDef());
+    return;
+  }
+
   VisitedBlocks.clear();
   InsertedPHIs.clear();
 
   // See if we had a local def, and if not, go hunting.
   MemoryAccess *DefBefore = getPreviousDef(MD);
   bool DefBeforeSameBlock = false;
   if (DefBefore->getBlock() == MD->getBlock() &&
       !(isa<MemoryPhi>(DefBefore) &&
while (!FixupList.empty()) {
     FixupList.append(InsertedPHIs.begin() + StartingPHISize, InsertedPHIs.end());
   }
 
   // Optimize potentially non-minimal phis added in this method.
   unsigned NewPhiSize = NewPhiIndexEnd - NewPhiIndex;
   if (NewPhiSize)
     tryRemoveTrivialPhis(ArrayRef<WeakVH>(&InsertedPHIs[NewPhiIndex], NewPhiSize));
 
-  // Now that all fixups are done, rename all uses if we are asked. Skip
-  // renaming for defs in unreachable blocks.
+  // Now that all fixups are done, rename all uses if we are asked. The defs are
+  // guaranteed to be in reachable code due to the check at the method entry.
   BasicBlock *StartBlock = MD->getBlock();
-  if (RenameUses && MSSA->getDomTree().getNode(StartBlock)) {
+  if (RenameUses) {
     SmallPtrSet<BasicBlock *, 16> Visited;
     // We are guaranteed there is a def in the block, because we just got it
     // handed to us in this function.
     MemoryAccess *FirstDef = &*MSSA->getWritableBlockDefs(StartBlock)->begin();
     // Convert to incoming value if it's a memorydef. A phi *is* already an
     // incoming value.
     if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
       FirstDef = MD->getDefiningAccess();

llvm/test/Transforms/GVN/mssa-update-dead-def.ll

+; RUN: opt -passes='require<memoryssa>,gvn' -verify-memoryssa -S %s | FileCheck %s
+
+; This is a regression test for a bug in MemorySSA updater.
+; Make sure that we don't crash and end up with a valid MemorySSA.
+
+; CHECK: @test()
+define void @test() personality i32* ()* null {
+  invoke void @bar()
+          to label %bar.normal unwind label %exceptional
+
+bar.normal:
+  ret void
+
+dead.block:
+  br label %baz.invoke
+
+baz.invoke:
+  invoke void @baz()
+          to label %baz.normal unwind label %exceptional
+
+baz.normal:
+  ret void
+
+exceptional:
+  %tmp9 = landingpad { i8*, i32 }
+          cleanup
+  call void @foo()
+  ret void
+}
+
+declare void @foo()
+declare void @bar()
+declare void @baz()