[LoopSimplifyCFG] Use DTU.applyUpdates instead of insert/deleteEdge

[mkazantsev]

Summary

insert/deleteEdge methods in DTU can make updates incorrectly in some cases
(see https://bugs.llvm.org/show_bug.cgi?id=40528), and it is recommended to
use applyUpdates methods instead when it is needed to make a mass update in CFG.

[mkazantsev]

I think the underlying problem is a bug of DTU, but am not 100% sure. In the given test, eager strategy does the following:

1. Removes dead edge bb4->bb18;
2. Tries to remove edge bb18->bb6, but the actual deletion does not happen because bb18 does not have a DT node;
3. As result, after these two operations the IDOM of bb6 is bb3, while it should be bb29 after we have removed edge bb18->bb6.

To me it seems that at some point we screwed up making the probper updates for bb6. I think we should've done it when removed bb4->bb18. However the comments in DTU about that are fuzzy. They say that:

/// Notify all available trees on an edge deletion. If both DT and PDT are
/// nullptrs, this function discards the update. Under either Strategy,
/// self-dominance update will be removed. The Eager Strategy applies
/// the update immediately while the Lazy Strategy queues the update.
/// It is recommended to only use this method when you have exactly one
/// deletion (and no insertions). It is recommended to use applyUpdates() in
/// all other cases. This function has to be called *after* making the update
/// on the actual CFG. An internal functions checks if the edge doesn't exist
/// in the CFG in DEBUG mode.
void deleteEdge(BasicBlock *From, BasicBlock *To);

I do not know what this recommendation is about. Does anybody know whether DTU should be able to work correctly with eager strategy?

[mkazantsev]

Maybe @kuhar knows what should be the correct behavior of eager DTU updates here? I think it's a bug in DTU, but the comments are uncertain enough to give me doubts about that. :)

[asbirlea]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

326–327

I have not looked at this in detail, but I've had a similar issue at one point in SimpleLoopUnswitch with DomTree. AFAICT, this applies for DTU as well.
Calling deleteEdge and insertEdge one after the other will not do the updates properly.
The correct way to do it is:

SmallVector<DominatorTree::UpdateType, 3> DTUpdates;
DTUpdates.push_back({DT.Insert, NewPreheader, L.getHeader()});
DTUpdates.push_back({DT.Insert, Preheader, NewPreheader});
DTUpdates.push_back({DT.Delete, Preheader, L.getHeader()});
DTU.applyUpdates(DTUpdates);

Perhaps the behavior is different with the Eager strategy, but I'm fairly confident using applyUpdates is correct for DT.

[mkazantsev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

326–327

With lazy strategy, flush() is doing exactly this thing, calling applyUpdates inside.

[mkazantsev]

It is indeed a bug in DTU, I was able to construct a unit test to reproduce it. https://bugs.llvm.org/show_bug.cgi?id=40528

[kuhar]

In D57316#1377047, @mkazantsev wrote:

It is indeed a bug in DTU, I was able to construct a unit test to reproduce it. https://bugs.llvm.org/show_bug.cgi?id=40528

You should use DTU.applyUpdates after a transformation that affects multiple CFG edges to inform DomTree about all of the things that changed since the last time it was updated. Eager strategy means that at each update point the updates are performed immediately, while the lazy update strategy is free to schedule them at any 'update' (synchronization) point between the first one and flush (possibly multiple time).
Perhaps we should improve the the documentation. @mkazantsev: do you have some suggestions?

[kuhar]

@NutshellySima What was the reason we introduced DTU.insertEdge and DTU.deleteEdge? While they are essential primitives in the incremental updater, couldn't we get rid of it entirely? My memory is blurry.

[mkazantsev]

In D57316#1377173, @kuhar wrote:

In D57316#1377047, @mkazantsev wrote:

It is indeed a bug in DTU, I was able to construct a unit test to reproduce it. https://bugs.llvm.org/show_bug.cgi?id=40528

You should use DTU.applyUpdates after a transformation that affects multiple CFG edges to inform DomTree about all of the things that changed since the last time it was updated. Eager strategy means that at each update point the updates are performed immediately, while the lazy update strategy is free to schedule them at any 'update' (synchronization) point between the first one and flush (possibly multiple time).
Perhaps we should improve the the documentation. @mkazantsev: do you have some suggestions?

When I read the documentation, I interpreted

It is recommended to only use this method when you have exactly one deletion (and no insertions). It is recommended to use applyUpdates() in all other cases.

as a profitability reasoning, not correctness reasoning. If we intentionally do not guarantee equivalence of Eager strategy and Lazy strategy (which is the same as applyUpdates), we should clearly state that "It is only legal to use this method when you have exactly one deletion...".
So if you think that the observed behavior is not a bug, I propose making this change. Otherwise, the bug should be fixed.

[mkazantsev]

I've run some extensive Fuzz testing on my side for three 72 hours, it seems this one along with other fixes on review cover all bugs we had.

[NutshellySima]

In D57316#1377177, @kuhar wrote:

@NutshellySima What was the reason we introduced DTU.insertEdge and DTU.deleteEdge? While they are essential primitives in the incremental updater, couldn't we get rid of it entirely? My memory is blurry.

Under Eager update strategy, they act as an alias of DTU.applyUpdates. And under Lazy update strategy, they'll assert when insertEdge() is inserting a nonexistent edge / deleteEdge() is deleting an edge that still exists to detect possible misuses.

Anyway, it is OK to get rid of insertEdge/deleteEdge entirely if we remove the check I mentioned. (I didn't implement a similar check in DTU.applyUpdates under Lazy strategy because it is still an open debate whether trying "inserting a nonexistent edge/deleting an edge that still exists" is a good approach.)

[mkazantsev]

So, is it OK to go with this fix here?

[kuhar]

In D57316#1384650, @mkazantsev wrote:

So, is it OK to go with this fix here?

You should replace insert/deleteEdge with applyUpdates -- I'd argue that even though it works with how the lazy strategy is implemented now, it is semantically incorrect because the DomTree updates you schedule don't match the CFG at the point of updates.
Then, it would be interesting to see whether:

1. Eager strategy works (it should)
2. How fast is eager vs lazy

[mkazantsev]

I've given up using DTU, now the updates are applied directly.

[kuhar]

In D57316#1386640, @mkazantsev wrote:

I've given up using DTU, now the updates are applied directly.

Max, why don't you use DTU with .applyUpdates? Are you facing some difficulties, or found documentation confusing somewhere else?
I don't have much time recently, but I can definitely find enough to fix some issues people have with updating dominators. If you think something is not obvious or too difficult, there are probably multiple people who faced the same problems but never bother to share their experience.

[kuhar]

In D57316#1387482, @kuhar wrote:

In D57316#1386640, @mkazantsev wrote:

I've given up using DTU, now the updates are applied directly.

Max, why don't you use DTU with .applyUpdates? Are you facing some difficulties, or found documentation confusing somewhere else?
I don't have much time recently, but I can definitely find enough to fix some issues people have with updating dominators. If you think something is not obvious or too difficult, there are probably multiple people who faced the same problems but never bother to share their experience.

The goal of DTU is take away as much low-level burden when updating dominators as possible. Ideally, nobody should have to use the raw updater in DomTree anymore, and the DTU api should enable us to cheaply update PostDominators without modifying the update logic.
That's why I'm opposed to using raw updates, unless absolutely necessary.

[mkazantsev]

Actually I am just confused by the number of different ways to do the same thing, all having different bugs inside. If using DTU.applyUpdates is the right day now, I'm ok with that.

[kuhar]

LGTM

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

 /// into unconditional branches.
 class ConstantTerminatorFoldingImpl {
 private:
   Loop &L;
   LoopInfo &LI;
   DominatorTree &DT;
   ScalarEvolution &SE;
   MemorySSAUpdater *MSSAU;
+  SmallVector<DominatorTree::UpdateType, 16> DTUpdates;
 
   // Whether or not the current loop has irreducible CFG.
   bool HasIrreducibleCFG = false;
   // Whether or not the current loop will still exist after terminator constant
   // folding will be done. In theory, there are two ways how it can happen:
   // 1. Loop's latch(es) become unreachable from loop header;
   // 2. Loop's header becomes unreachable from method entry.
   // In practice, the second situation is impossible because we only modify the
private:
   /// remove edges from the loop to these blocks.
   void handleDeadExits() {
     // If no dead exits, nothing to do.
     if (DeadExitBlocks.empty())
       return;
 
     // Construct split preheader and the dummy switch to thread edges from it to
     // dead exits.
-    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
     BasicBlock *Preheader = L.getLoopPreheader();
     BasicBlock *NewPreheader = Preheader->splitBasicBlock(
         Preheader->getTerminator(),
         Twine(Preheader->getName()).concat("-split"));
-    DTU.deleteEdge(Preheader, L.getHeader());
-    DTU.insertEdge(NewPreheader, L.getHeader());
-    DTU.insertEdge(Preheader, NewPreheader);
+    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();
 
     unsigned DummyIdx = 1;
     for (BasicBlock *BB : DeadExitBlocks) {
       SmallVector<Instruction *, 4> DeadPhis;
       for (auto &PN : BB->phis())
         DeadPhis.push_back(&PN);
 
       // Eliminate all Phis from dead exits.
       for (Instruction *PN : DeadPhis) {
         PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
         PN->eraseFromParent();
       }
       assert(DummyIdx != 0 && "Too many dead exits!");
       DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);
-      DTU.insertEdge(Preheader, BB);
+      DTUpdates.push_back({DominatorTree::Insert, Preheader, BB});
       ++NumLoopExitsDeleted;
     }
 
     assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
     if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
       OuterLoop->addBasicBlockToLoop(NewPreheader, LI);
 
       // When we break dead edges, the outer loop may become unreachable from
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!");
+        // We need all DT updates to be done before forming LCSSA.
+        DT.applyUpdates(DTUpdates);
+        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() {
-    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
     if (MSSAU) {
       SmallPtrSet<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
                                                      DeadLoopBlocks.end());
       MSSAU->removeBlocks(DeadLoopBlocksSet);
     }
     for (auto *BB : DeadLoopBlocks) {
       assert(BB != L.getHeader() &&
              "Header of the current loop cannot be dead!");
       LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
                         << "\n");
       if (LI.isLoopHeader(BB)) {
         assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
         LI.erase(LI.getLoopFor(BB));
       }
       LI.removeBlock(BB);
     }
 
-    DeleteDeadBlocks(DeadLoopBlocks, &DTU);
+    DetatchDeadBlocks(DeadLoopBlocks, &DTUpdates);
+    DT.applyUpdates(DTUpdates);
+    DTUpdates.clear();
+    for (auto *BB : DeadLoopBlocks)
+      BB->eraseFromParent();
+
     NumLoopBlocksDeleted += DeadLoopBlocks.size();
   }
 
   /// Constant-fold terminators of blocks acculumated in FoldCandidates into the
   /// unconditional branches.
   void foldTerminators() {
-    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
-
     for (BasicBlock *BB : FoldCandidates) {
       assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");
       BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
       assert(TheOnlySucc && "Should have one live successor!");
 
       LLVM_DEBUG(dbgs() << "Replacing terminator of " << BB->getName()
                         << " with an unconditional branch to the block "
                         << TheOnlySucc->getName() << "\n");
for (BasicBlock *BB : FoldCandidates) {
 
       IRBuilder<> Builder(BB->getContext());
       Instruction *Term = BB->getTerminator();
       Builder.SetInsertPoint(Term);
       Builder.CreateBr(TheOnlySucc);
       Term->eraseFromParent();
 
       for (auto *DeadSucc : DeadSuccessors)
-        DTU.deleteEdge(BB, DeadSucc);
+        DTUpdates.push_back({DominatorTree::Delete, BB, DeadSucc});
 
       ++NumTerminatorsFolded;
     }
   }
 
 public:
   ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT,
                                 ScalarEvolution &SE,
bool run() {
     handleDeadExits();
     foldTerminators();
 
     if (!DeadLoopBlocks.empty()) {
       LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
                     << " dead blocks in loop " << L.getHeader()->getName()
                     << "\n");
       deleteDeadLoopBlocks();
+    } else {
+      // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
+      DT.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(L.getHeader()));
     LI.verify(DT);
 #endif

test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; XFAIL: *
 ; REQUIRES: asserts
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -passes='require<domtree>,loop(simplify-cfg)' -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -enable-mssa-loop-dependency=true -verify-memoryssa -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
 
 ; Make sure that we can eliminate a provably dead backedge.
latch:
   %result = phi i32 [ 0, %loop ], [ %dead_phi, %subloop_latch ]
   br i1 %cond3, label %loop, label %exit
 
 exit:
   ret i32 %result
 }
 
 define void @test_crash_01() {
+; CHECK-LABEL: @test_crash_01(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br i1 undef, label [[BB17:%.*]], label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    switch i32 0, label [[BB2_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[BB19:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb2-split:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    switch i32 undef, label [[BB16:%.*]] [
+; CHECK-NEXT:    i32 0, label [[BB15:%.*]]
+; CHECK-NEXT:    i32 1, label [[BB14:%.*]]
+; CHECK-NEXT:    i32 2, label [[BB13:%.*]]
+; CHECK-NEXT:    i32 3, label [[BB12:%.*]]
+; CHECK-NEXT:    i32 4, label [[BB11:%.*]]
+; CHECK-NEXT:    i32 5, label [[BB8:%.*]]
+; CHECK-NEXT:    i32 6, label [[BB10:%.*]]
+; CHECK-NEXT:    i32 7, label [[BB9:%.*]]
+; CHECK-NEXT:    i32 8, label [[BB7:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb7:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb8:
+; CHECK-NEXT:    switch i32 undef, label [[BB28:%.*]] [
+; CHECK-NEXT:    i32 0, label [[BB27:%.*]]
+; CHECK-NEXT:    i32 1, label [[BB26:%.*]]
+; CHECK-NEXT:    i32 2, label [[BB23:%.*]]
+; CHECK-NEXT:    i32 3, label [[BB24:%.*]]
+; CHECK-NEXT:    i32 4, label [[BB25:%.*]]
+; CHECK-NEXT:    i32 5, label [[BB29:%.*]]
+; CHECK-NEXT:    i32 6, label [[BB22:%.*]]
+; CHECK-NEXT:    i32 7, label [[BB20:%.*]]
+; CHECK-NEXT:    i32 8, label [[BB21:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb9:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb10:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb11:
+; CHECK-NEXT:    br label [[BB8]]
+; CHECK:       bb12:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb13:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb14:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb15:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb16:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb17:
+; CHECK-NEXT:    ret void
+; CHECK:       bb19:
+; CHECK-NEXT:    ret void
+; CHECK:       bb20:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb21:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb22:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb23:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb24:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb25:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb26:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb27:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb28:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb29:
+; CHECK-NEXT:    br label [[BB3]]
+;
 bb:
   br label %bb1
 
 bb1:                                              ; preds = %bb
   br i1 undef, label %bb17, label %bb2
 
 bb2:                                              ; preds = %bb1
   br label %bb3
 
 bb3:                                              ; preds = %bb6, %bb2
   br label %bb4
 
 bb4:                                              ; preds = %bb3
   switch i32 0, label %bb5 [
-    i32 1, label %bb19
-    i32 2, label %bb18
   ]
 
 bb5:                                              ; preds = %bb4
   switch i32 undef, label %bb16 [
-    i32 0, label %bb15
-    i32 1, label %bb14
-    i32 2, label %bb13
-    i32 3, label %bb12
-    i32 4, label %bb11
-    i32 5, label %bb8
-    i32 6, label %bb10
-    i32 7, label %bb9
-    i32 8, label %bb7
   ]
 
 bb6:                                              ; preds = %bb29, %bb18
   br label %bb3
 
 bb7:                                              ; preds = %bb5
   unreachable
 
 bb8:                                              ; preds = %bb11, %bb5
   switch i32 undef, label %bb28 [
-    i32 0, label %bb27
-    i32 1, label %bb26
-    i32 2, label %bb23
-    i32 3, label %bb24
-    i32 4, label %bb25
-    i32 5, label %bb29
-    i32 6, label %bb22
-    i32 7, label %bb20
-    i32 8, label %bb21
   ]
 
 bb9:                                              ; preds = %bb5
   unreachable
 
 bb10:                                             ; preds = %bb5
   unreachable