[MemorySSA] Cleanup trivial phis.

[asbirlea]

Summary

This is unfortunately needed for correctness, if we are to extend the tolerance of the update API to the way simple loop unswitch is doing cloning.

In simple loop unswitch (as opposed to loop unswitch), not all blocks are cloned. This can create unreachable cloned blocks (no predecessor), which are later cleaned up.

In MemorySSA, the APIs for supporting these kind of updates (clone + update exit blocks), make certain assumption on the integrity of the CFG. When cloning, if something was not cloned, it's values in MemorySSA default to LiveOnEntry. When updating exit blocks, it is safe to assume that we can first insert phis in the blocks merging two clones, then add additional phis in the IDF of the blocks that received phis. This no longer holds true if one of the clones being merged comes from an unreachable block. We'd conservatively need to add all phis before filling in their incoming definitions. In practice this restriction can be relaxed if we clean up trivial phis after the first round of insertion.

[george.burgess.iv]

Thanks!

lib/Analysis/MemorySSAUpdater.cpp

if (PrevBlockSet.empty()) {
       // iterator here.
       NewBlocks.insert(BB);
     }
   }
   // Nothing to process for new/cloned blocks.
   for (auto *BB : NewBlocks)
     PredMap.erase(BB);
 
-  SmallVector<BasicBlock *, 8> BlocksToProcess;
   SmallVector<BasicBlock *, 16> BlocksWithDefsToReplace;
   SmallVector<WeakVH, 8> InsertedPhis;
 
   // First create MemoryPhis in all blocks that don't have one. Create in the
   // order found in Updates, not in PredMap, to get deterministic numbering.
   for (auto &Edge : Updates) {
     BasicBlock *BB = Edge.getTo();
     if (PredMap.count(BB) && !MSSA->getMemoryAccess(BB))
if (NewPhi->getNumOperands()) {
       for (auto *Pred : AddedBlockSet) {
         auto *LastDefForPred = LastDefAddedPred[Pred];
         for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
           NewPhi->addIncoming(LastDefForPred, Pred);
       }
       for (auto *Pred : PrevBlockSet)
         for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
           NewPhi->addIncoming(DefP1, Pred);
-
-      // Insert BB in the set of blocks that now have definition. We'll use this
-      // to compute IDF and add Phis there next.
-      BlocksToProcess.push_back(BB);
     }
 
     // Get all blocks that used to dominate BB and no longer do after adding
     // AddedBlockSet, where PrevBlockSet are the previously known predecessors.
     assert(DT.getNode(BB)->getIDom() && "BB does not have valid idom");
     BasicBlock *PrevIDom = FindNearestCommonDominator(PrevBlockSet);
     assert(PrevIDom && "Previous IDom should exists");
     BasicBlock *NewIDom = DT.getNode(BB)->getIDom()->getBlock();
     assert(NewIDom && "BB should have a new valid idom");
     assert(DT.dominates(NewIDom, PrevIDom) &&
            "New idom should dominate old idom");
     GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);
   }
 
+  tryRemoveTrivialPhis(InsertedPhis);
+  // Create the set of blocks that now have a definition. We'll use this to
+  // compute IDF and add Phis there next.
+  SmallVector<BasicBlock *, 8> BlocksToProcess;
+  for (auto &VH : InsertedPhis)
+    if (auto *MPhi = cast_or_null<MemoryPhi>(VH))
+      BlocksToProcess.push_back(MPhi->getBlock());
+
   // Compute IDF and add Phis in all IDF blocks that do not have one.
   SmallVector<BasicBlock *, 32> IDFBlocks;
   if (!BlocksToProcess.empty()) {
     ForwardIDFCalculator IDFs(DT);
     SmallPtrSet<BasicBlock *, 16> DefiningBlocks(BlocksToProcess.begin(),
                                                  BlocksToProcess.end());
     IDFs.setDefiningBlocks(DefiningBlocks);
     IDFs.calculate(IDFBlocks);

test/Analysis/MemorySSA/simple_loop_unswitch_nontrivial.ll

+; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -verify-memoryssa -S %s | FileCheck %s
+; REQUIRES: asserts
+
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @foo()
+
+; In Test1, there are no definitions. MemorySSA updates insert trivial phis and remove them.
+; Verify all are removed, considering the SLU pass leaves unreachable blocks hanging when the MSSA updates are done.
+; CHECK-LABEL: @Test1
+define void @Test1(i32) {
+header:
+  br label %outer
+
+outer.loopexit.split:                             ; preds = %continue
+  br label %outer.loopexit
+
+outer.loopexit:                                   ; preds = %outer.loopexit.split.us, %outer.loopexit.split
+  br label %outer
+
+outer:                                            ; preds = %outer.loopexit, %header
+  br i1 false, label %outer.split.us, label %outer.split
+
+outer.split.us:                                   ; preds = %outer
+  br label %inner.us
+
+inner.us:                                         ; preds = %continue.us, %outer.split.us
+  br label %overflow.us
+
+overflow.us:                                      ; preds = %inner.us
+  br label %continue.us
+
+continue.us:                                      ; preds = %overflow.us
+  br i1 true, label %outer.loopexit.split.us, label %inner.us
+
+outer.loopexit.split.us:                          ; preds = %continue.us
+  br label %outer.loopexit
+
+outer.split:                                      ; preds = %outer
+  br label %inner
+
+inner:                                            ; preds = %continue, %outer.split
+  br label %switchme
+
+switchme:                                         ; preds = %inner
+  switch i32 %0, label %continue [
+    i32 88, label %go_out
+    i32 99, label %case2
+  ]
+
+case2:                                            ; preds = %switchme
+  br label %continue
+
+continue:                                         ; preds = %case2, %switchme
+  br i1 true, label %outer.loopexit.split, label %inner
+
+go_out:                                           ; preds = %switchme
+  unreachable
+}
+
+; In Test2 there is a single def (call to foo). There are already Phis in place that are cloned when unswitching.
+; Ensure MemorySSA remains correct. Due to SLU's pruned cloning, continue.us2 becomes unreachable, with an empty Phi that is later cleaned.
+; CHECK-LABEL: @Test2
+define void @Test2(i32) {
+header:
+  br label %outer
+
+outer.loopexit.split:                             ; preds = %continue
+  br label %outer.loopexit
+
+outer.loopexit:                                   ; preds = %outer.loopexit.split.us, %outer.loopexit.split
+  br label %outer
+
+outer:                                            ; preds = %outer.loopexit, %header
+  br i1 false, label %outer.split.us, label %outer.split
+
+outer.split.us:                                   ; preds = %outer
+  br label %inner.us
+
+inner.us:                                         ; preds = %continue.us, %outer.split.us
+  br label %overflow.us
+
+overflow.us:                                      ; preds = %inner.us
+  br label %continue.us
+
+continue.us:                                      ; preds = %overflow.us
+  br i1 true, label %outer.loopexit.split.us, label %inner.us
+
+outer.loopexit.split.us:                          ; preds = %continue.us
+  br label %outer.loopexit
+
+outer.split:                                      ; preds = %outer
+  br label %inner
+
+inner:                                            ; preds = %continue, %outer.split
+  br label %switchme
+
+switchme:                                         ; preds = %inner
+  switch i32 %0, label %continue [
+    i32 88, label %go_out
+    i32 99, label %case2
+  ]
+
+case2:                                            ; preds = %switchme
+  call void @foo()
+  br label %continue
+
+continue:                                         ; preds = %case2, %switchme
+  br i1 true, label %outer.loopexit.split, label %inner
+
+go_out:                                           ; preds = %switchme
+  unreachable
+}