[LegacyPM] Fix PR37888 by teaching the legacy loop pass manager how to clear out deleted loops from the current queue beyond just the current loop.

[chandlerc]

Summary

This is important because SimpleLoopUnswitch will now enqueue the same
loop to be re-processed. When it does this with the legacy PM, we don't
have a way of canceling the rest of the pipeline and so we can end up
deleting the loop before we reprocess it. =/

This change also makes it easy to support deleting other loops in the
queue to process, although I don't have any use cases for that.

[sanjoy]

llvm/lib/Analysis/LoopPass.cpp

149 ↗

(On Diff #152421)

Can we have the same loop multiple times in the loop queue? If not would be nice to assert that and use the single iterator version of erase.

[chandlerc]

llvm/lib/Analysis/LoopPass.cpp

149 ↗

(On Diff #152421)

Yeah, technically... You could have two SimpleLoopUnswitch passes in the same pipeline, and because of how this works, both could run, find something to transform, transform it, and re-enqueue the loop to be processed. Then we'll end up re-visiting it twice too.

We could prevent this, but it'd take a bunch of code and doesn't seem worth it when we can just handle it here.

llvm/trunk/lib/Analysis/LoopPass.cpp

void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
   Info.addRequired<LoopInfoWrapperPass>();
   Info.addRequired<DominatorTreeWrapperPass>();
   Info.setPreservesAll();
 }
 
 void LPPassManager::markLoopAsDeleted(Loop &L) {
   assert((&L == CurrentLoop || CurrentLoop->contains(&L)) &&
          "Must not delete loop outside the current loop tree!");
-  if (&L == CurrentLoop)
+  // If this loop appears elsewhere within the queue, we also need to remove it
+  // there. However, we have to be careful to not remove the back of the queue
+  // as that is assumed to match the current loop.
+  assert(LQ.back() == CurrentLoop && "Loop queue back isn't the current loop!");
+  LQ.erase(std::remove(LQ.begin(), LQ.end(), &L), LQ.end());
+
+  if (&L == CurrentLoop) {
     CurrentLoopDeleted = true;
+    // Add this loop back onto the back of the queue to preserve our invariants.
+    LQ.push_back(&L);
+  }
 }
 
 /// run - Execute all of the passes scheduled for execution.  Keep track of
 /// whether any of the passes modifies the function, and if so, return true.
 bool LPPassManager::runOnFunction(Function &F) {
   auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
   LI = &LIWP.getLoopInfo();
   Module &M = *F.getParent();

llvm/trunk/test/Transforms/SimpleLoopUnswitch/pr37888.ll

+; RUN: opt -simple-loop-unswitch -loop-deletion -S < %s | FileCheck %s
+;
+; Check that when we do unswitching where we re-enqueue the loop to be processed
+; again, but manage to delete the loop before ever getting to iterate on it, it
+; doesn't crash the legacy pass manager.
+
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @pr37888() {
+; CHECK-LABEL: define void @pr37888()
+entry:
+  %tobool = icmp ne i16 undef, 0
+  br label %for.body
+; CHECK:         %[[TOBOOL:.*]] = icmp ne
+; CHECK-NEXT:    br i1 %[[TOBOOL]], label %if.then, label %[[ENTRY_SPLIT:.*]]
+;
+; CHECK:       [[ENTRY_SPLIT]]:
+; CHECK-NEXT:    br label %for.end
+
+for.body:
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:
+  unreachable
+; CHECK:       if.then:
+; CHECK-NEXT:    unreachable
+
+if.end:
+  br label %for.inc
+
+for.inc:
+  br i1 undef, label %for.body, label %for.end
+
+for.end:
+  ret void
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+}