[LoopSimplifyCFG] Change logic of dead loops removal to avoid hitting asserts

[mkazantsev]

Summary

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. Our current logic of deletion of dead blocks may erase the
information about preheader before we handle the loop, and therefore we may hit this
assertion.

This patch changes the logic of loop deletion: we make them top-level loops before
we actually erase them. This allows us to trigger the simple branch of erase logic which
just detatches blocks from the loop and does not try to do some complex stuff that need
this invariant.

Thanks to @uabelho for reporting this!

[uabelho]

It solves the problem I saw, thanks!

The change looks fine to me but I don't know this code so let someone else ok it.

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

408–409 ↗

(On Diff #183494)

Perhaps replace

if (DL->getParentLoop()) {
  for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())

with

while (auto *PL = DL->getParentLoop()) {

?

[mkazantsev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

408–409 ↗

(On Diff #183494)

And loop infinitely? :) We need to change DL somehow, otherwise PL is always the same loop.

[uabelho]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

408–409 ↗

(On Diff #183494)

Doesn't
DL->getParentLoop()->removeChildLoop(DL);
disconnect DL from PL, so in the next loop round DL doesn't have the old PL as parent anymore?

[mkazantsev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

408–409 ↗

(On Diff #183494)

The line DL->getParentLoop()->removeChildLoop(DL); is executed once *after* this loop. You seem to be misreading the code. :)

[uabelho]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

408–409 ↗

(On Diff #183494)

Right. When I tried what I suggested I did

while (auto *PL = DL->getParentLoop()) {
  for (auto *BB : DL->getBlocks())
    PL->removeBlockFromLoop(BB);
  DL->getParentLoop()->removeChildLoop(DL);
  LI.addTopLevelLoop(DL);
}

with that all the testcases (including the reproducer in this patch) passes but perhaps it's stupid to call LI.addTopLevelLoop(DL) several times.
But nvm, I just thought the

if (DL->getParentLoop()) {
  for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())

was cumbersome and could be simplified, I didn't mean to make a mess :)

[mkazantsev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

408–409 ↗

(On Diff #183494)

I've seen that pattern across the code and think it's fine. Feel free to refactor it if you like. :)

[mkazantsev]

Aside from refactoring that we can make as follow-up if needed (yet I don't really think it does), does it look OK? :)

[uabelho]

In D57221#1384651, @mkazantsev wrote:

Aside from refactoring that we can make as follow-up if needed (yet I don't really think it does), does it look OK? :)

It does to me but as I said I don't know this code so I think someone else should ok it.

[fedor.sergeev]

LGTM.

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

404 ↗

(On Diff #183494)

Please, put a short comment here describing the idea of this first loop through dead blocks.

[sammccall]

llvm/trunk/test/Transforms/LoopSimplifyCFG/update_parents.ll

2

this REQUIRES was still needed because of the use of -debug-only.
Fixed in r353842

llvm/trunk/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

private:
   /// 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)) {
+        assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
+        Loop *DL = LI.getLoopFor(BB);
+        if (DL->getParentLoop()) {
+          for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())
+            for (auto *BB : DL->getBlocks())
+              PL->removeBlockFromLoop(BB);
+          DL->getParentLoop()->removeChildLoop(DL);
+          LI.addTopLevelLoop(DL);
+        }
+        LI.erase(DL);
+      }
+
     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);
     }
 
     DetatchDeadBlocks(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true);
     DTU.applyUpdates(DTUpdates);
     DTUpdates.clear();
     for (auto *BB : DeadLoopBlocks)
       DTU.deleteBB(BB);

llvm/trunk/test/Transforms/LoopSimplifyCFG/update_parents.ll

-; XFAIL: *
-; REQUIRES: asserts
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; 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 triple = "x86_64-unknown-linux-gnu"
 
 define void @test() {
-
 ; CHECK-LABEL: @test(
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1.loopexit:
+; CHECK-NEXT:    br label [[BB1]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb2.loopexit:
+; CHECK-NEXT:    br label [[BB2]]
+; CHECK:       bb2:
+; CHECK-NEXT:    switch i32 0, label [[BB2_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[BB1_LOOPEXIT:%.*]]
+; CHECK-NEXT:    i32 2, label [[BB2_LOOPEXIT:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb2-split:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br label [[BB3]]
+;
 
   br label %bb1
 
 bb1:                                              ; preds = %bb4, %0
   br label %bb2
 
 bb2:                                              ; preds = %bb6, %bb1
   br label %bb3
 
 bb3:                                              ; preds = %bb8, %bb3, %bb2
   br i1 false, label %bb4, label %bb3
 
 bb4:                                              ; preds = %bb8, %bb3
   br i1 undef, label %bb1, label %bb6
 
 bb6:                                              ; preds = %bb4
   br i1 undef, label %bb2, label %bb8
 
 bb8:                                              ; preds = %bb6
   br i1 true, label %bb4, label %bb3
 }
 
 define void @test_many_subloops(i1 %c) {
-
 ; CHECK-LABEL: @test_many_subloops(
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1.loopexit:
+; CHECK-NEXT:    br label [[BB1]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb2.loopexit:
+; CHECK-NEXT:    br label [[BB2]]
+; CHECK:       bb2:
+; CHECK-NEXT:    switch i32 0, label [[BB2_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[BB1_LOOPEXIT:%.*]]
+; CHECK-NEXT:    i32 2, label [[BB2_LOOPEXIT:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb2-split:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br label [[BB3]]
+;
 
   br label %bb1
 
 bb1:
   br label %bb2
 
 bb2:
   br label %bb3