[DO NOT MERGE] Explore MSSA behavior in LoopSimplifyCFG

[mkazantsev]

Summary

With this patch, test test/Transforms/LoopSimplifyCFG/lcssa.ll hits the assertion

opt: /home/mkazantsev/work/llvm/llvm/lib/Analysis/MemorySSAUpdater.cpp:848: void llvm::MemorySSAUpdater::applyInsertUpdates(llvm::ArrayRef<llvm::cfg::Update<llvm::BasicBlock*> >, llvm::DominatorTree&, const llvm::GraphDiff<llvm::BasicBlock*, false>*): Assertion `DT.dominates(NewIDom, PrevIDom) && "New idom should dominate old idom"' failed.

when we try to apply updates to MSSA. The very same updates have updated DT correctly (it passes verification).
It must be something fishy around how MSSA updater works which I don't understand.

[rtereshin]

Shall we close this?

llvm/lib/Analysis/MemorySSAUpdater.cpp

for (auto &BBPredPair : PredMap) {
 
     // 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");
+    dbgs() << "ZZZ BB = " << BB->getName() << ", PrevIDom = " << PrevIDom->getName() << ", NewIDom = " << NewIDom->getName() << "\n";
     assert(DT.dominates(NewIDom, PrevIDom) &&
            "New idom should dominate old idom");
     GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);
   }
 
   // Compute IDF and add Phis in all IDF blocks that do not have one.
   SmallVector<BasicBlock *, 32> IDFBlocks;
   if (!BlocksToProcess.empty()) {

llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

private:
   ///
   /// Doing so, we preserve static reachibility of all dead exits and can later
   /// remove edges from the loop to these blocks.
   void handleDeadExits() {
     // If no dead exits, nothing to do.
     if (DeadExitBlocks.empty())
       return;
 
+    dbgs() << "ZZZ Entered " << __FUNCTION__ << "\n";
     // Construct split preheader and the dummy switch to thread edges from it to
     // dead exits.
     BasicBlock *Preheader = L.getLoopPreheader();
     BasicBlock *NewPreheader = Preheader->splitBasicBlock(
         Preheader->getTerminator(),
         Twine(Preheader->getName()).concat("-split"));
-    if (MSSAU)
-      MSSAU->removeEdge(Preheader, L.getHeader());
     DTUpdates.push_back({DominatorTree::Delete, Preheader, L.getHeader()});
     DTUpdates.push_back({DominatorTree::Insert, NewPreheader, L.getHeader()});
     DTUpdates.push_back({DominatorTree::Insert, Preheader, NewPreheader});
     IRBuilder<> Builder(Preheader->getTerminator());
     SwitchInst *DummySwitch =
         Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);
     Preheader->getTerminator()->eraseFromParent();
 
if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
 
         // Some values from loops in [OuterLoop, StillReachable) could be used
         // in the current loop. Now it is not their child anymore, so such uses
         // require LCSSA Phis.
         Loop *FixLCSSALoop = OuterLoop;
         while (FixLCSSALoop->getParentLoop() != StillReachable)
           FixLCSSALoop = FixLCSSALoop->getParentLoop();
         assert(FixLCSSALoop && "Should be a loop!");
+        L.getHeader()->getParent()->dump();
         // We need all DT updates to be done before forming LCSSA.
         DTU.applyUpdates(DTUpdates);
+        assert(DT.verify());
+        if (MSSAU)
+          MSSAU->applyUpdates(DTUpdates, DT);
         DTUpdates.clear();
         formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);
       }
     }
   }
 
   /// Delete loop blocks that have become unreachable after folding. Make all
   /// relevant updates to DT and LI.
   void deleteDeadLoopBlocks() {
-    if (MSSAU) {
-      SmallPtrSet<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
-                                                     DeadLoopBlocks.end());
-      MSSAU->removeBlocks(DeadLoopBlocksSet);
-    }
-
     // The function LI.erase has some invariants that need to be preserved when
     // it tries to remove a loop which is not the top-level loop. In particular,
     // it requires loop's preheader to be strictly in loop's parent. We cannot
     // just remove blocks one by one, because after removal of preheader we may
     // break this invariant for the dead loop. So we detatch and erase all dead
     // loops beforehand.
     for (auto *BB : DeadLoopBlocks)
       if (LI.isLoopHeader(BB)) {
for (auto *BB : DeadLoopBlocks) {
              "Header of the current loop cannot be dead!");
       LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
                         << "\n");
       LI.removeBlock(BB);
     }
 
     DetatchDeadBlocks(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true);
     DTU.applyUpdates(DTUpdates);
+    if (MSSAU) {
+      MSSAU->applyUpdates(DTUpdates, DT);
+      SmallPtrSet<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
+                                                     DeadLoopBlocks.end());
+      MSSAU->removeBlocks(DeadLoopBlocksSet);
+    }
     DTUpdates.clear();
     for (auto *BB : DeadLoopBlocks)
       DTU.deleteBB(BB);
 
     NumLoopBlocksDeleted += DeadLoopBlocks.size();
   }
 
   /// Constant-fold terminators of blocks acculumated in FoldCandidates into the
for (BasicBlock *BB : FoldCandidates) {
       unsigned TheOnlySuccDuplicates = 0;
       for (auto *Succ : successors(BB))
         if (Succ != TheOnlySucc) {
           DeadSuccessors.insert(Succ);
           // If our successor lies in a different loop, we don't want to remove
           // the one-input Phi because it is a LCSSA Phi.
           bool PreserveLCSSAPhi = !L.contains(Succ);
           Succ->removePredecessor(BB, PreserveLCSSAPhi);
-          if (MSSAU)
-            MSSAU->removeEdge(BB, Succ);
         } else
           ++TheOnlySuccDuplicates;
 
       assert(TheOnlySuccDuplicates > 0 && "Should be!");
       // If TheOnlySucc was BB's successor more than once, after transform it
       // will be its successor only once. Remove redundant inputs from
       // TheOnlySucc's Phis.
       bool PreserveLCSSAPhi = !L.contains(TheOnlySucc);
bool run() {
     foldTerminators();
 
     if (!DeadLoopBlocks.empty()) {
       LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
                     << " dead blocks in loop " << Header->getName() << "\n");
       deleteDeadLoopBlocks();
     } else {
       // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
+      if (MSSAU)
+        MSSAU->applyUpdates(DTUpdates, DT);
       DTU.applyUpdates(DTUpdates);
       DTUpdates.clear();
     }
 
 #ifndef NDEBUG
     // Make sure that we have preserved all data structures after the transform.
     assert(DT.verify() && "DT broken after transform!");
     assert(DT.isReachableFromEntry(Header));

llvm/test/Transforms/LoopSimplifyCFG/lcssa.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -passes='require<domtree>,loop(simplify-cfg)' -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -enable-mssa-loop-dependency=true -verify-memoryssa -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 
-define void @c() {
-; CHECK-LABEL: @c(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[D:%.*]]
-; CHECK:       d.loopexit:
-; CHECK-NEXT:    [[DOTLCSSA:%.*]] = phi i32 [ [[TMP1:%.*]], [[FOR_COND:%.*]] ]
-; CHECK-NEXT:    br label [[D]]
-; CHECK:       d:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ undef, [[ENTRY:%.*]] ], [ [[DOTLCSSA]], [[D_LOOPEXIT:%.*]] ]
-; CHECK-NEXT:    br label [[FOR_COND]]
-; CHECK:       for.cond:
-; CHECK-NEXT:    [[TMP1]] = phi i32 [ [[TMP0]], [[D]] ], [ 0, [[IF_END:%.*]] ]
-; CHECK-NEXT:    [[TOBOOL2:%.*]] = icmp eq i32 [[TMP1]], 0
-; CHECK-NEXT:    br i1 [[TOBOOL2]], label [[IF_END]], label [[D_LOOPEXIT]]
-; CHECK:       if.end:
-; CHECK-NEXT:    br label [[FOR_COND]]
-;
-entry:
-  br label %d
-
-d.loopexit:                                       ; preds = %if.end.7, %for.body
-  %.lcssa = phi i32 [ %1, %for.body ], [ 0, %if.end.7 ]
-  br label %d
-
-d:                                                ; preds = %d.loopexit, %entry
-  %0 = phi i32 [ undef, %entry ], [ %.lcssa, %d.loopexit ]
-  br label %for.cond
-
-for.cond:                                         ; preds = %if.end.8, %d
-  %1 = phi i32 [ %0, %d ], [ 0, %if.end.8 ]
-  br label %for.body
-
-for.body:                                         ; preds = %for.cond
-  %tobool2 = icmp eq i32 %1, 0
-  br i1 %tobool2, label %if.end, label %d.loopexit
-
-if.end:                                           ; preds = %for.body
-  br label %if.end.7
-
-if.end.7:                                         ; preds = %if.end
-  br i1 true, label %if.end.8, label %d.loopexit
-
-if.end.8:                                         ; preds = %if.end.7
-  br label %for.cond
-}
-
 define void @test_01() {
 ; CHECK-LABEL: @test_01(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
 ; CHECK:       for.cond.loopexit:
 ; CHECK-NEXT:    br label [[FOR_COND]]
 ; CHECK:       for.cond:
 ; CHECK-NEXT:    [[INC41_LCSSA3:%.*]] = phi i16 [ undef, [[FOR_COND_LOOPEXIT:%.*]] ], [ undef, [[ENTRY:%.*]] ]

 while.cond:                                       ; preds = %while.body, %for.cond
   %inc41 = phi i16 [ %inc4, %while.body ], [ %inc41.lcssa3, %for.cond ]
   br i1 true, label %while.body, label %for.cond.loopexit
 
 while.body:                                       ; preds = %while.cond
   %inc4 = add nsw i16 %inc41, 1
   br label %while.cond
 }
-
-define void @bar() {
-; CHECK-LABEL: @bar(
-; CHECK-NEXT:  bb:
-; CHECK-NEXT:    switch i32 0, label [[BB_SPLIT:%.*]] [
-; CHECK-NEXT:    i32 1, label [[BB10:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       bb-split:
-; CHECK-NEXT:    br label [[BB1:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ [[TMP7:%.*]], [[BB6:%.*]] ], [ undef, [[BB_SPLIT]] ]
-; CHECK-NEXT:    switch i32 undef, label [[BB5:%.*]] [
-; CHECK-NEXT:    i32 0, label [[BB6]]
-; CHECK-NEXT:    i32 1, label [[BB8:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       bb5:
-; CHECK-NEXT:    ret void
-; CHECK:       bb6:
-; CHECK-NEXT:    [[TMP7]] = add i32 undef, 123
-; CHECK-NEXT:    br label [[BB1]]
-; CHECK:       bb8:
-; CHECK-NEXT:    [[TMP9:%.*]] = phi i32 [ [[TMP]], [[BB1]] ]
-; CHECK-NEXT:    [[USE:%.*]] = add i32 [[TMP9]], 1
-; CHECK-NEXT:    ret void
-; CHECK:       bb10:
-; CHECK-NEXT:    ret void
-;
-
-bb:
-  br label %bb1
-
-bb1:                                              ; preds = %bb6, %bb
-  %tmp = phi i32 [ %tmp7, %bb6 ], [ undef, %bb ]
-  br i1 false, label %bb2, label %bb4
-
-bb2:                                              ; preds = %bb1
-  switch i32 undef, label %bb10 [
-  i32 0, label %bb3
-  i32 1, label %bb8
-  ]
-
-bb3:                                              ; preds = %bb2
-  br label %bb6
-
-bb4:                                              ; preds = %bb1
-  switch i32 undef, label %bb5 [
-  i32 0, label %bb6
-  i32 1, label %bb8
-  ]
-
-bb5:                                              ; preds = %bb4
-  ret void
-
-bb6:                                              ; preds = %bb4, %bb3
-  %tmp7 = add i32 undef, 123
-  br label %bb1
-
-bb8:                                              ; preds = %bb4, %bb2
-  %tmp9 = phi i32 [ %tmp, %bb2 ], [ %tmp, %bb4 ]
-  %use = add i32 %tmp9, 1
-  ret void
-
-bb10:                                             ; preds = %bb2
-  ret void
-}
-
-define void @memlcssa() {
-; CHECK-LABEL: @memlcssa(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    switch i32 0, label [[ENTRY_SPLIT:%.*]] [
-; CHECK-NEXT:    i32 1, label [[DEFAULT_BB:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       entry-split:
-; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
-; CHECK:       for.body:
-; CHECK-NEXT:    call void @foo()
-; CHECK-NEXT:    br label [[FOR_BODY]]
-; CHECK:       default.bb:
-; CHECK-NEXT:    unreachable
-;
-entry:
-  br label %for.body
-
-for.body:                                         ; preds = %exit, %entry
-  br label %switch.bb
-
-switch.bb:                                        ; preds = %for.body
-  switch i2 1, label %default.bb [
-  i2 1, label %case.bb
-  ]
-
-case.bb:                                          ; preds = %switch
-  br label %exit
-
-default.bb:                                       ; preds = %switch
-  unreachable
-
-exit:                                             ; preds = %case.bb
-  call void @foo()
-  br label %for.body
-}
-
-declare void @foo()