[MemorySSA] Update Phi insertion.

[asbirlea]

Summary

MemoryPhis may be needed following a Def insertion inthe IDF of all the
new accesses added (phis + potentially a def). Ensure this also occurs when
only the new MemoryPhis are the defining accesses.

Note: The need for computing IDF here is because of new Phis added with
edges incoming from unreachable code, Phis that had previously been
simplified. The preferred solution is to not reintroduce such Phis.
This patch is the needed fix while working on the preferred solution.

[george.burgess.iv]

LGTM, since this is a workaround to keep things rolling while we work on a more general fix.

Thanks!

lib/Analysis/MemorySSAUpdater.cpp

DefBefore->replaceUsesWithIf(MD, [MD](Use &U) {
       // Defs are automatically unoptimized when the user is set to MD below,
       // because the isOptimized() call will fail to find the same ID.
     });
   }
 
   // and that def is now our defining access.
   MD->setDefiningAccess(DefBefore);
 
-  // Remember the index where we may insert new phis below.
-  unsigned NewPhiIndex = InsertedPHIs.size();
-
   SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());
+
+  SmallPtrSet<BasicBlock *, 2> DefiningBlocks;
+
   if (!DefBeforeSameBlock) {
     // If there was a local def before us, we must have the same effect it
     // did. Because every may-def is the same, any phis/etc we would create, it
     // would also have created.  If there was no local def before us, we
     // performed a global update, and have to search all successors and make
     // sure we update the first def in each of them (following all paths until
     // we hit the first def along each path). This may also insert phi nodes.
     // TODO: There are other cases we can skip this work, such as when we have a
     // single successor, and only used a straight line of single pred blocks
     // backwards to find the def.  To make that work, we'd have to track whether
     // getDefRecursive only ever used the single predecessor case.  These types
     // of paths also only exist in between CFG simplifications.
 
     // If this is the first def in the block and this insert is in an arbitrary
     // place, compute IDF and place phis.
     auto Iter = MD->getDefsIterator();
     ++Iter;
     auto IterEnd = MSSA->getBlockDefs(MD->getBlock())->end();
-    if (Iter == IterEnd) {
-      ForwardIDFCalculator IDFs(*MSSA->DT);
-      SmallVector<BasicBlock *, 32> IDFBlocks;
-      SmallPtrSet<BasicBlock *, 2> DefiningBlocks;
-      for (const auto &VH : InsertedPHIs)
-        if (const auto *RealPHI = cast_or_null<MemoryPhi>(VH))
-          DefiningBlocks.insert(RealPHI->getBlock());
-      DefiningBlocks.insert(MD->getBlock());
-      IDFs.setDefiningBlocks(DefiningBlocks);
-      IDFs.calculate(IDFBlocks);
-      SmallVector<AssertingVH<MemoryPhi>, 4> NewInsertedPHIs;
-      for (auto *BBIDF : IDFBlocks) {
-        auto *MPhi = MSSA->getMemoryAccess(BBIDF);
-        if (!MPhi) {
-          MPhi = MSSA->createMemoryPhi(BBIDF);
-          NewInsertedPHIs.push_back(MPhi);
-        }
-        // Add the phis created into the IDF blocks to NonOptPhis, so they are
-        // not optimized out as trivial by the call to getPreviousDefFromEnd
-        // below. Once they are complete, all these Phis are added to the
-        // FixupList, and removed from NonOptPhis inside fixupDefs().
-        // Existing Phis in IDF may need fixing as well, and potentially be
-        // trivial before this insertion, hence add all IDF Phis. See PR43044.
-        NonOptPhis.insert(MPhi);
-      }
+    if (Iter == IterEnd)
+      DefiningBlocks.insert(MD->getBlock());
+
+    FixupList.push_back(MD);
+  }
+
+    // Add the phis created into the IDF blocks to NonOptPhis, so they are not
+    // optimized out as trivial by the call to getPreviousDefFromEnd below. Once
+    // they are complete, all these Phis are added to the FixupList, and removed
+    // from NonOptPhis inside fixupDefs(). Existing Phis in IDF may need fixing
+    // as well, and potentially be trivial before this insertion, hence add all
+    // IDF Phis. See PR43044.
 
-      for (auto &MPhi : NewInsertedPHIs) {
-        auto *BBIDF = MPhi->getBlock();
-        for (auto *Pred : predecessors(BBIDF)) {
-          DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
-          MPhi->addIncoming(getPreviousDefFromEnd(Pred, CachedPreviousDef),
-                            Pred);
-        }
-      }
+      MPhi->addIncoming(getPreviousDefFromEnd(Pred, CachedPreviousDef), Pred);
 
-      // Re-take the index where we're adding the new phis, because the above
-      // call to getPreviousDefFromEnd, may have inserted into InsertedPHIs.
-      NewPhiIndex = InsertedPHIs.size();
-      for (auto &MPhi : NewInsertedPHIs) {
-        InsertedPHIs.push_back(&*MPhi);
-        FixupList.push_back(&*MPhi);
-      }
-    }
-
-    FixupList.push_back(MD);
-  }
-
+  // Remember the index where we may insert new phis.
+  unsigned NewPhiIndex = InsertedPHIs.size();
   // Remember the index where we stopped inserting new phis above, since the
   // fixupDefs call in the loop below may insert more, that are already minimal.
   unsigned NewPhiIndexEnd = InsertedPHIs.size();
 
   while (!FixupList.empty()) {
     unsigned StartingPHISize = InsertedPHIs.size();
     fixupDefs(FixupList);
     FixupList.clear();

test/Analysis/MemorySSA/pr43317.ll

+; RUN: opt -S -licm -enable-mssa-loop-dependency=true < %s | FileCheck %s
+; REQUIRES: asserts
+@v_274 = external dso_local global i64, align 1
+@v_295 = external dso_local global i16, align 1
+@v_335 = external dso_local global i32, align 1
+
+; CHECK-LABEL: @main()
+define dso_local void @main() {
+entry:
+  store i32 undef, i32* @v_335, align 1
+  br i1 undef, label %gate, label %exit
+
+nopredentry1:                                     ; No predecessors!
+  br label %preinfiniteloop
+
+nopredentry2:                                     ; No predecessors!
+  br label %gate
+
+gate:                                             ; preds = %nopredentry2, %entry
+  br i1 undef, label %preinfiniteloop, label %exit
+
+preinfiniteloop:                                  ; preds = %gate, %nopredentry1
+  br label %infiniteloop
+
+infiniteloop:                                     ; preds = %infiniteloop, %preinfiniteloop
+  store i16 undef, i16* @v_295, align 1
+  br label %infiniteloop
+
+exit:                                             ; preds = %gate, %entry
+  store i64 undef, i64* @v_274, align 1
+  ret void
+}