[MemorySSA] Add additional verification for phis.

[asbirlea]

Summary

Verify that the incoming defs into phis are the last defs from the
respective incoming blocks.
When moving blocks, insertDef must RenameUses. Adding this verification
makes GVNHoist tests fail that uncovered this issue.

[asbirlea]

Add NDEBUG.

[george.burgess.iv]

Thanks for adding this!

just a code clarity nit. LGTM otherwise

lib/Analysis/MemorySSA.cpp

1873 ↗

(On Diff #204128)

nit: IMO, the control-flow of this loop is a bit difficult to follow, and the verification it's doing about forwards-unreachable code are pretty understated. do you think something like the following is clearer (and functionally equivalent)?

if (DT->getNode(Pred))) {
  auto *CurBB = Pred;
  while (CurBB) {
    if (/* getblockdefs(CurBB) */) {
      assert(LastAcc == IncAcc);
      break;
    }
    CurBB = IDom;
  }
  assert(CurBB || IncAcc == LOE && ...);
} else if (/* getblockdefs(Pred) */) {
  assert(IncAcc == LastAcc);
} else {
  assert(IncAcc == LOE);
}

[asbirlea]

lib/Analysis/MemorySSA.cpp

1873 ↗

(On Diff #204128)

To me it seemed cleaner before, because I didn't need to duplicate the if (getblockdefs) and each of the two asserts. But perhaps it's clearer to duplicate, I have no strong preference TBH.
I'll update shortly.

[asbirlea]

Update per the comment suggestion.

[george.burgess.iv]

Thanks!

llvm/trunk/include/llvm/Analysis/MemorySSA.h

public:
   enum InsertionPlace { Beginning, End };
 
 protected:
   // Used by Memory SSA annotater, dumpers, and wrapper pass
   friend class MemorySSAAnnotatedWriter;
   friend class MemorySSAPrinterLegacyPass;
   friend class MemorySSAUpdater;
 
+  void verifyPrevDefInPhis(Function &F) const;
   void verifyDefUses(Function &F) const;
   void verifyDomination(Function &F) const;
   void verifyOrdering(Function &F) const;
   void verifyDominationNumbers(const Function &F) const;
 
   // This is used by the use optimizer and updater.
   AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
     auto It = PerBlockAccesses.find(BB);

llvm/trunk/lib/Analysis/MemorySSA.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FormattedStream.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
+#include <cstdlib>
 #include <iterator>
 #include <memory>
 #include <utility>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "memoryssa"
 

 LLVM_DUMP_METHOD void MemorySSA::dump() const { print(dbgs()); }
 #endif
 
 void MemorySSA::verifyMemorySSA() const {
   verifyDefUses(F);
   verifyDomination(F);
   verifyOrdering(F);
   verifyDominationNumbers(F);
+  verifyPrevDefInPhis(F);
   // Previously, the verification used to also verify that the clobberingAccess
   // cached by MemorySSA is the same as the clobberingAccess found at a later
   // query to AA. This does not hold true in general due to the current fragility
   // of BasicAA which has arbitrary caps on the things it analyzes before giving
   // up. As a result, transformations that are correct, will lead to BasicAA
   // returning different Alias answers before and after that transformation.
   // Invalidating MemorySSA is not an option, as the results in BasicAA can be so
   // random, in the worst case we'd need to rebuild MemorySSA from scratch after
   // every transformation, which defeats the purpose of using it. For such an
   // example, see test4 added in D51960.
 }
 
+void MemorySSA::verifyPrevDefInPhis(Function &F) const {
+#ifndef NDEBUG
+  for (const BasicBlock &BB : F) {
+    if (MemoryPhi *Phi = getMemoryAccess(&BB)) {
+      for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) {
+        auto *Pred = Phi->getIncomingBlock(I);
+        auto *IncAcc = Phi->getIncomingValue(I);
+        // If Pred has no unreachable predecessors, get last def looking at
+        // IDoms. If, while walkings IDoms, any of these has an unreachable
+        // predecessor, then the expected incoming def is LoE.
+        if (auto *DTNode = DT->getNode(Pred)) {
+          while (DTNode) {
+            if (auto *DefList = getBlockDefs(DTNode->getBlock())) {
+              auto *LastAcc = &*(--DefList->end());
+              assert(LastAcc == IncAcc &&
+                     "Incorrect incoming access into phi.");
+              break;
+            }
+            DTNode = DTNode->getIDom();
+          }
+          assert((DTNode || IncAcc == getLiveOnEntryDef()) &&
+                 "Expected LoE inc");
+        } else if (auto *DefList = getBlockDefs(Pred)) {
+          // If Pred has unreachable predecessors, but has at least a Def, the
+          // incoming access can be the last Def in Pred, or it could have been
+          // optimized to LoE.
+          auto *LastAcc = &*(--DefList->end());
+          assert((LastAcc == IncAcc || IncAcc == getLiveOnEntryDef()) &&
+                 "Incorrect incoming access into phi.");
+        } else {
+          // If Pred has unreachable predecessors and no Defs, incoming access
+          // should be LoE.
+          assert(IncAcc == getLiveOnEntryDef() && "Expected LoE inc");
+        }
+      }
+    }
+  }
+#endif
+}
+
 /// Verify that all of the blocks we believe to have valid domination numbers
 /// actually have valid domination numbers.
 void MemorySSA::verifyDominationNumbers(const Function &F) const {
 #ifndef NDEBUG
   if (BlockNumberingValid.empty())
     return;
 
   SmallPtrSet<const BasicBlock *, 16> ValidBlocks = BlockNumberingValid;

llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp

void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
   // Replace all our users with our defining access.
   What->replaceAllUsesWith(What->getDefiningAccess());
 
   // Let MemorySSA take care of moving it around in the lists.
   MSSA->moveTo(What, BB, Where);
 
   // Now reinsert it into the IR and do whatever fixups needed.
   if (auto *MD = dyn_cast<MemoryDef>(What))
-    insertDef(MD);
+    insertDef(MD, true);
   else
     insertUse(cast<MemoryUse>(What));
 
   // Clear dangling pointers. We added all MemoryPhi users, but not all
   // of them are removed by fixupDefs().
   NonOptPhis.clear();
 }
 

llvm/trunk/test/Analysis/MemorySSA/unreachable.ll

+; RUN: opt -licm -enable-mssa-loop-dependency -verify-memoryssa %s -S | FileCheck %s
+; REQUIRES: asserts
+; Ensure verification doesn't fail with unreachable blocks.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-grtev4-linux-gnu"
+
+declare dso_local void @f()
+
+; CHECK-LABEL: @foo
+define dso_local void @foo() {
+entry:
+  br i1 undef, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  br label %try.cont
+
+if.end:                                           ; preds = %entry
+; 1 = MemoryDef(liveOnEntry)
+  call void @f()
+  br label %try.cont
+
+catch:                                            ; No predecessors!
+; 2 = MemoryDef(liveOnEntry)
+  call void @f()
+  br label %try.cont
+
+try.cont:                                         ; preds = %if.end, %catch, %if.then
+; 3 = MemoryPhi({if.then,liveOnEntry},{if.end,1},{catch,liveOnEntry})
+  ret void
+}