[IPSCCP] Support unfeasible default dests for switch.

[fhahn]

Summary

At the moment, unfeasible default destinations are not handled properly
in removeNonFeasibleEdges. So far, only unfeasible cases are removed,
but later code expects unreachable blocks to have no predecessors.

This is causing the crash reported in PR49573.

If the default destination is unfeasible it won't be executed. Create
a new unreachable block on demand and use that as default
destination.

Note that at the moment this only is relevant for cases where
resolvedUndefsIn marks the first case as executable. Regular switch
handling has a FIXME/TODO to support determining whether the default
case is feasible or not.

[fhahn]

ping :)

[fhahn]

ping :)

[lebedev.ri]

Not really familiar with this pass, but the transform sounds legal, although i would have guessed you'd want to instead point it to an new block with unreachable?

[nikic]

Agree with @lebedev.ri, this should point to an unreachable block. It doesn't matter much for the resolvedUndefsIn case, but with proper support merging into an unrelated case would be a pretty bad choice.

[fhahn]

In D113497#3154248, @lebedev.ri wrote:

Not really familiar with this pass, but the transform sounds legal, although i would have guessed you'd want to instead point it to an new block with unreachable?

! In D113497#3154265, @nikic wrote:

Agree with @lebedev.ri, this should point to an unreachable block. It doesn't matter much for the resolvedUndefsIn case, but with proper support merging into an unrelated case would be a pretty bad choice.

Thanks, I updated the code to create a new unreachable block on demand (and cache it for the function) and use that as default successor.

[lebedev.ri]

LG.

If SCCP runs again, will it then again create a new unreachable block
for the default that is already pointing at the unreachable block?
Should it not do such redundant work?

[fhahn]

In D113497#3155755, @lebedev.ri wrote:

LG.

If SCCP runs again, will it then again create a new unreachable block
for the default that is already pointing at the unreachable block?
Should it not do such redundant work?

Good point. In practice I think IPSCCP is only run twice when doing LTO, so it's probably not a big deal. But let me check if the default dst is already unreachable.

[fhahn]

In D113497#3157893, @fhahn wrote:

In D113497#3155755, @lebedev.ri wrote:

LG.

If SCCP runs again, will it then again create a new unreachable block
for the default that is already pointing at the unreachable block?
Should it not do such redundant work?

Good point. In practice I think IPSCCP is only run twice when doing LTO, so it's probably not a big deal. But let me check if the default dst is already unreachable.

If the default destination is already only an unreachable block and unfeasible, it the original block will be removed as part of the clean-up. re-using the block would be difficult, because it's been already marked for deletion and I think making changes to that is probably not worth the trouble.

llvm/lib/Transforms/Scalar/SCCP.cpp

for (BasicBlock &BB : F) {
 
     if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
       if (!isa<UndefValue>(RI->getOperand(0)))
         ReturnsToZap.push_back(RI);
   }
 }
 
 static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB,
-                                   DomTreeUpdater &DTU) {
+                                   DomTreeUpdater &DTU,
+                                   BasicBlock *&NewUnreachableBB) {
   SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors;
   bool HasNonFeasibleEdges = false;
   for (BasicBlock *Succ : successors(BB)) {
     if (Solver.isEdgeFeasible(BB, Succ))
       FeasibleSuccessors.insert(Succ);
     else
       HasNonFeasibleEdges = true;
   }
if (FeasibleSuccessors.size() == 1) {
     }
 
     BranchInst::Create(OnlyFeasibleSuccessor, BB);
     TI->eraseFromParent();
     DTU.applyUpdatesPermissive(Updates);
   } else if (FeasibleSuccessors.size() > 1) {
     SwitchInstProfUpdateWrapper SI(*cast<SwitchInst>(TI));
     SmallVector<DominatorTree::UpdateType, 8> Updates;
+
+    // If the default destination is unfeasible it will never be taken. Replace
+    // it with a new block with a single Unreachable instruction.
+    BasicBlock *DefaultDest = SI->getDefaultDest();
+    if (!FeasibleSuccessors.contains(DefaultDest)) {
+      if (!NewUnreachableBB) {
+        NewUnreachableBB =
+            BasicBlock::Create(DefaultDest->getContext(), "default.unreachable",
+                               DefaultDest->getParent(), DefaultDest);
+        new UnreachableInst(DefaultDest->getContext(), NewUnreachableBB);
+      }
+
+      SI->setDefaultDest(NewUnreachableBB);
+      Updates.push_back({DominatorTree::Delete, BB, DefaultDest});
+      Updates.push_back({DominatorTree::Insert, BB, NewUnreachableBB});
+    }
+
     for (auto CI = SI->case_begin(); CI != SI->case_end();) {
       if (FeasibleSuccessors.contains(CI->getCaseSuccessor())) {
         ++CI;
         continue;
       }
 
       BasicBlock *Succ = CI->getCaseSuccessor();
       Succ->removePredecessor(BB);
for (Function &F : M) {
     for (BasicBlock *BB : BlocksToErase) {
       NumInstRemoved += changeToUnreachable(BB->getFirstNonPHI(),
                                             /*PreserveLCSSA=*/false, &DTU);
     }
     if (!Solver.isBlockExecutable(&F.front()))
       NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(),
                                             /*PreserveLCSSA=*/false, &DTU);
 
+    BasicBlock *NewUnreachableBB = nullptr;
     for (BasicBlock &BB : F)
-      MadeChanges |= removeNonFeasibleEdges(Solver, &BB, DTU);
+      MadeChanges |= removeNonFeasibleEdges(Solver, &BB, DTU, NewUnreachableBB);
 
     for (BasicBlock *DeadBB : BlocksToErase)
       DTU.deleteBB(DeadBB);
 
     for (BasicBlock &BB : F) {
       for (Instruction &Inst : llvm::make_early_inc_range(BB)) {
         if (Solver.getPredicateInfoFor(&Inst)) {
           if (auto *II = dyn_cast<IntrinsicInst>(&Inst)) {

llvm/test/Transforms/SCCP/switch-constantfold-crash.ll

bb2:                                              ; preds = %bb, %bb
   ]
 
 bb3:                                              ; preds = %bb2
   unreachable
 
 bb4:                                              ; preds = %bb2, %bb2, %bb2
   unreachable
 }
+
+; Test case from PR49573. %default.bb is unfeasible. Make sure it gets replaced
+; by an unreachable block.
+define void @pr49573_main() {
+; CHECK-LABEL: @pr49573_main(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TGT:%.*]] = call i16 @pr49573_fn()
+; CHECK-NEXT:    switch i16 2, label %default.unreachable [
+; CHECK-NEXT:    i16 0, label %case.0
+; CHECK-NEXT:    i16 2, label %case.2
+; CHECK-NEXT:    ]
+; CHECK:       case.0:
+; CHECK-NEXT:    unreachable
+; CHECK:       default.unreachable:
+; CHECK-NEXT:    unreachable
+; CHECK:       case.2:
+; CHECK-NEXT:    br label [[NEXT:%.*]]
+; CHECK:       next:
+; CHECK-NEXT:    [[TGT_2:%.*]] = call i16 @pr49573_fn_2()
+; CHECK-NEXT:    switch i16 2, label %default.unreachable [
+; CHECK-NEXT:    i16 0, label %case.0
+; CHECK-NEXT:    i16 2, label %case.2
+; CHECK-NEXT:    ]
+;
+entry:
+  %tgt = call i16 @pr49573_fn()
+  switch i16 %tgt, label %default.bb [
+  i16 0, label %case.0
+  i16 1, label %case.1
+  i16 2, label %case.2
+  ]
+
+case.0:
+  unreachable
+
+default.bb:
+  ret void
+
+case.1:
+  ret void
+
+case.2:
+  br label %next
+
+next:
+  %tgt.2 = call i16 @pr49573_fn_2()
+  switch i16 %tgt.2, label %default.bb [
+  i16 0, label %case.0
+  i16 2, label %case.2
+  ]
+}
+
+; Make sure a new unreachable BB is created.
+define void @pr49573_main_2() {
+; CHECK-LABEL: @pr49573_main_2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TGT:%.*]] = call i16 @pr49573_fn()
+; CHECK-NEXT:    switch i16 2, label %default.unreachable [
+; CHECK-NEXT:    i16 0, label %case.0
+; CHECK-NEXT:    i16 2, label %case.2
+; CHECK-NEXT:    ]
+; CHECK:       case.0:
+; CHECK-NEXT:    unreachable
+; CHECK:       default.unreachable:
+; CHECK-NEXT:    unreachable
+; CHECK:       case.2:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %tgt = call i16 @pr49573_fn()
+  switch i16 %tgt, label %default.bb [
+  i16 0, label %case.0
+  i16 1, label %case.1
+  i16 2, label %case.2
+  ]
+
+case.0:
+  unreachable
+
+default.bb:
+  ret void
+
+case.1:
+  ret void
+
+case.2:
+  ret void
+}
+
+define internal i16 @pr49573_fn() {
+; CHECK-LABEL: define internal i16 @pr49573_fn(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[ELSE:%.*]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i16 undef
+;
+entry:
+  br i1 undef, label %then, label %else
+
+then:
+  ret i16 0
+
+else:
+  ret i16 2
+}
+
+define internal i16 @pr49573_fn_2() {
+; CHECK-LABEL: define internal i16 @pr49573_fn_2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[ELSE:%.*]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i16 undef
+;
+entry:
+  br i1 undef, label %then, label %else
+
+then:
+  ret i16 0
+
+else:
+  ret i16 2
+}