[MemorySSA] bug in MemorySSA construction

There appears to be a bug in MemorySSA that sometimes results in memory defs that don't dominate their uses. If you apply the below patch and run the following command you should be able to reproduce the issue. I haven't been able to investigate it yet, but may do so tomorrow if no one gets to it first.

$ opt -print-memoryssa llvm/test/Transforms/GlobalDCE/complex-constantexpr.ll

diff --git a/lib/Transforms/Utils/MemorySSA.cpp b/lib/Transforms/Utils/MemorySSA.cpp
index 4a604c9..ed2574b 100644
--- a/lib/Transforms/Utils/MemorySSA.cpp
+++ b/lib/Transforms/Utils/MemorySSA.cpp
@@ -1900,7 +1900,9 @@ void MemorySSA::verifyDomination(Function &F) const {
              }
            }
          } else {
- UseBlock = cast<MemoryAccess>(U)->getBlock();
+ auto *MA = cast<MemoryAccess>(U);
+ UseBlock = MA->getBlock();
+ assert(MD->getBlock() != UseBlock || locallyDominates(MD, MA));
          }
          assert(DT->dominates(MD->getBlock(), UseBlock) &&
                 "Memory Def does not dominate it's uses");

The problem is that we somehow end up trying to optimize the same block 3 times …

Inorder Dominator Tree:
[1] %bb {0,9}
[2] %bb2 {1,8}
[3] %bb11 {2,7}
[4] %bb1 {3,4}
[4] %bb15 {5,6}

Use Optimizer visiting block bb
Use Optimizer visiting block bb2
Use Optimizer visiting block bb11
Use Optimizer visiting block bb1
Use Optimizer visiting block bb11
Use Optimizer visiting block bb15
Use Optimizer visiting block bb11
Use Optimizer visiting block bb2
Use Optimizer visiting block bb

I see what is wrong with the iterator, but i’m just going to replace it with depth_first anyway.