[SimpleLoopUnswitch] Add non-empty unreachable block check to exit cases removed.

[asbirlea]

Summary

Update check to include the check for unreachable.

Basic blocks ending in unreachable are special cased, as these blocks may be already unswitched. Before this patch this check is only done for the default destination.
The condition for the exit cases and the default case must be the same, because we should never leave edges from the switch instruction to a basic block that we are unswitching. In PR45355 we still have a remaining edge (that we're attempting to remove from the DT) because its the default edge to an unreachable-terminated block where we unswitch a case edge to that block.

Resolves PR45355.

[asbirlea]

Gentle ping.

[chandlerc]

Might also be good to explain a bit of *how* this fixes the PR to the commit log (or bug) for posterity. It seemed to surprise both of us that this was the fix when talking through the code, I suspect a future reader may benefit from having a log of what went on here.

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

624–626

Comment about the fact that the default and case conditions *must* be the exact same? Otherwise I fear we'll add back this bug some day soon...

[asbirlea]

Address comment and updated description.

[chandlerc]

LGTM!! Thanks for tracking down this surprising fix to the PR!

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
   Value *LoopCond = SI.getCondition();
 
   // If this isn't switching on an invariant condition, we can't unswitch it.
   if (!L.isLoopInvariant(LoopCond))
     return false;
 
   auto *ParentBB = SI.getParent();
 
+  // The same check must be used both for the default and the exit cases. We
+  // should never leave edges from the switch instruction to a basic block that
+  // we are unswitching, hence the condition used to determine the default case
+  // needs to also be used to populate ExitCaseIndices, which is then used to
+  // remove cases from the switch.
   auto IsTriviallyUnswitchableExitBlock = [&](BasicBlock &BBToCheck) {
     // BBToCheck is not an exit block if it is inside loop L.
     if (L.contains(&BBToCheck))
       return false;
     // BBToCheck is not trivial to unswitch if its phis aren't loop invariant.
     if (!areLoopExitPHIsLoopInvariant(L, *ParentBB, BBToCheck))
       return false;
     // We do not unswitch a block that only has an unreachable statement, as
     // it's possible this is a previously unswitched block. Only unswitch if
     // either the terminator is not unreachable, or, if it is, it's not the only
     // instruction in the block.
     auto *TI = BBToCheck.getTerminator();
     bool isUnreachable = isa<UnreachableInst>(TI);
     return !isUnreachable ||
            (isUnreachable && (BBToCheck.getFirstNonPHIOrDbg() != TI));
   };
 
   SmallVector<int, 4> ExitCaseIndices;
-  for (auto Case : SI.cases()) {
-    auto *SuccBB = Case.getCaseSuccessor();
-    if (!L.contains(SuccBB) &&
-        areLoopExitPHIsLoopInvariant(L, *ParentBB, *SuccBB))
+  for (auto Case : SI.cases())
+    if (IsTriviallyUnswitchableExitBlock(*Case.getCaseSuccessor()))
       ExitCaseIndices.push_back(Case.getCaseIndex());
-  }
   BasicBlock *DefaultExitBB = nullptr;
   SwitchInstProfUpdateWrapper::CaseWeightOpt DefaultCaseWeight =
       SwitchInstProfUpdateWrapper::getSuccessorWeight(SI, 0);
   if (IsTriviallyUnswitchableExitBlock(*SI.getDefaultDest())) {
     DefaultExitBB = SI.getDefaultDest();
   } else if (ExitCaseIndices.empty())
     return false;
 

llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll

NonEmptyUnreachableBlock:
   call void @f()
   call void @g()
   unreachable
 
 ; CHECK:loop:
 ; CHECK-NEXT:  %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
 ; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %NonEmptyUnreachableBlock [
 ; CHECK-NEXT:    i32 1, label %NonEmptyUnreachableBlock
-; CHECK-NEXT:    i32 2, label %loop.loopexit
 ; CHECK-NEXT:    i32 0, label %loop.split
+; CHECK-NEXT:    i32 2, label %loop.split
+; CHECK-NEXT:  ]
+
+; CHECK:loop.split:
+; CHECK-NEXT:  br label %for.cond
+
+; CHECK:for.cond:
+; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %loop.loopexit [
+; CHECK-NEXT:    i32 0, label %for.cond
+; CHECK-NEXT:  ]
+
+; CHECK:loop.loopexit:
+; CHECK-NEXT:  unreachable
+
+; CHECK:NonEmptyUnreachableBlock:
+; CHECK-NEXT:  call void @f()
+; CHECK-NEXT:  call void @g()
+; CHECK-NEXT:  unreachable
+}
+
+define void @test_unswitch_switch_with_nonempty_unreachable2() {
+; CHECK-LABEL: @test_unswitch_switch_with_nonempty_unreachable2()
+entry:
+  br label %loop
+
+loop:
+  %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
+  br label %for.cond
+
+for.cond:
+  switch i32 %cleanup.dest.slot.0, label %for.cond [
+    i32 0, label %for.cond
+    i32 1, label %NonEmptyUnreachableBlock
+    i32 2, label %loop.loopexit
+  ]
+
+loop.loopexit:
+  unreachable
+
+NonEmptyUnreachableBlock:
+  call void @f()
+  call void @g()
+  unreachable
+
+; CHECK:loop:
+; CHECK-NEXT:  %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
+; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %loop.split [
+; CHECK-NEXT:    i32 1, label %NonEmptyUnreachableBlock
 ; CHECK-NEXT:  ]
 
 ; CHECK:loop.split:
 ; CHECK-NEXT:  br label %for.cond
 
 ; CHECK:for.cond:
+; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %for.cond.backedge [
+; CHECK-NEXT:    i32 0, label %for.cond.backedge
+; CHECK-NEXT:    i32 2, label %loop.loopexit
+; CHECK-NEXT:  ]
+
+; CHECK:for.cond.backedge:
 ; CHECK-NEXT:  br label %for.cond
 
 ; CHECK:loop.loopexit:
 ; CHECK-NEXT:  unreachable
 
 ; CHECK:NonEmptyUnreachableBlock:
 ; CHECK-NEXT:  call void @f()
 ; CHECK-NEXT:  call void @g()
 ; CHECK-NEXT:  unreachable
 }
+
+; PR45355
+define void @test_unswitch_switch_with_duplicate_edge() {
+; CHECK-LABEL: @test_unswitch_switch_with_duplicate_edge()
+entry:
+  br label %lbl1
+
+lbl1:                                             ; preds = %entry
+  %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.cond1, %lbl1
+  switch i32 %cleanup.dest.slot.0, label %UnifiedUnreachableBlock [
+    i32 0, label %for.cond1
+    i32 5, label %UnifiedUnreachableBlock
+    i32 2, label %lbl1.loopexit
+  ]
+
+UnifiedUnreachableBlock:                          ; preds = %for.cond1, %for.cond1
+  unreachable
+
+lbl1.loopexit:                                    ; preds = %for.cond1
+  unreachable
+
+; CHECK: for.cond1:
+; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %UnifiedUnreachableBlock [
+; CHECK-NEXT:    i32 0, label %for.cond1
+; CHECK-NEXT:    i32 5, label %UnifiedUnreachableBlock
+; CHECK-NEXT:    i32 2, label %lbl1.loopexit
+; CHECK-NEXT:  ]
+}