[NewGVN] Fix verification of MemoryPhis in verifyMemoryCongruency()

[davide]

Summary

verifyMemoryCongruency() filters out trivially dead MemoryDef, as we find them immediately dead, before moving from TOP to a new congruence class.
If you consider the testcase attached, I think we may have the same problem for PHI, and I think we may want to skip MemoryPhis if all the operands are dead.

This is the MemorySSA dump

0 = MemoryDef(liveOnEntry)
1 = MemoryDef(liveOnEntry)
2 = MemoryDef(1)
3 = MemoryPhi({entry,1},{body,2})

Looking at the operands of 3, they're both uses of trivially dead defs.

Skipping trivially dead instruction   call void @llvm.lifetime.start.p0i8(i64 4, i8* undef)
Marking   call void @llvm.lifetime.start.p0i8(i64 4, i8* undef) for deletion
Skipping trivially dead instruction   call void @llvm.lifetime.start.p0i8(i64 4, i8* undef)
Marking   call void @llvm.lifetime.start.p0i8(i64 4, i8* undef) for deletion

so we never move them out of TOP, and the phi is dead as well. Otherwise, we think this is reachable, and we hit an assertion.

[• dberlin]

It's definitely going to be the case that verifyMemoryCongruency is going to have false positives. It can't ever be 100% correct without it being an alternative value numbering method that is provably correct and as complete as our current one :)

Thus, it's limited to doing checks on "likely to be wrong" cases.

So i'm fine with improving it, but we're going to have to disable large parts of it at some point as our value numbering becomes more powerful.
(because we will always be better at finding congruences that it can't be convinced are correct :P)

lib/Transforms/Scalar/NewGVN.cpp

   auto ReachableAccessPred =
       [&](const std::pair<const MemoryAccess *, CongruenceClass *> Pair) {
         bool Result = ReachableBlocks.count(Pair.first->getBlock());
         if (!Result || MSSA->isLiveOnEntryDef(Pair.first) ||
             MemoryToDFSNum(Pair.first) == 0)
           return false;
         if (auto *MemDef = dyn_cast<MemoryDef>(Pair.first))
           return !isInstructionTriviallyDead(MemDef->getMemoryInst());
+
+        // We could have phi nodes which operands are all trivially dead,
+        // so we don't process them.
+        if (auto *MemPHI = dyn_cast<MemoryPhi>(Pair.first)) {
+          for (auto &U : MemPHI->incoming_values()) {
+            if (Instruction *I = dyn_cast<Instruction>(U.get())) {
+              if (!isInstructionTriviallyDead(I))
+                return true;
+            }
+          }
+          return false;
+        }
+
         return true;
       };
 
   auto Filtered = make_filter_range(MemoryAccessToClass, ReachableAccessPred);
   for (auto KV : Filtered) {
     assert(KV.second != TOPClass &&
            "Memory not unreachable but ended up in TOP");
     if (auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {

test/Transforms/NewGVN/verify-memoryphi.ll

+; Skip dead MemoryPhis when performing memory congruency verification
+; in NewGVN.
+; RUN: opt -S -newgvn %s | FileCheck %s
+; REQUIRES: asserts
+
+; CHECK: define void @tinkywinky() {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   br i1 false, label %body, label %end
+; CHECK:      body:
+; CHECK-NEXT:   store i8 undef, i8* null
+; CHECK-NEXT:   br label %end
+; CHECK:      end:
+; CHECK-NEXT:   ret void
+; CHECK-NEXT: }
+
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture)
+
+define void @tinkywinky() {
+entry:
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* undef)
+  br i1 false, label %body, label %end
+
+body:
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* undef)
+  br label %end
+
+end:
+  ret void
+}