Reland "[CVP] Check whether the default case is reachable (#79993)" (#96089)

This patch reverts https://github.com/llvm/llvm-project/pull/81585 as
https://github.com/llvm/llvm-project/pull/78582 has been landed.
Now clang works well with reproducer
https://github.com/llvm/llvm-project/pull/79993#issuecomment-1936822679.

3 files changed, 339 insertions, 5 deletions

diff --git a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
index 50b5fdb..88adeb5 100644
--- a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -366,6 +366,7 @@ static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI,
   { // Scope for SwitchInstProfUpdateWrapper. It must not live during
     // ConstantFoldTerminator() as the underlying SwitchInst can be changed.
     SwitchInstProfUpdateWrapper SI(*I);
+    unsigned ReachableCaseCount = 0;
 
     for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
       ConstantInt *Case = CI->getCaseValue();
@@ -402,6 +403,31 @@ static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI,
 
       // Increment the case iterator since we didn't delete it.
       ++CI;
+      ++ReachableCaseCount;
+    }
+
+    BasicBlock *DefaultDest = SI->getDefaultDest();
+    if (ReachableCaseCount > 1 &&
+        !isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg())) {
+      ConstantRange CR = LVI->getConstantRangeAtUse(I->getOperandUse(0),
+                                                    /*UndefAllowed*/ false);
+      // The default dest is unreachable if all cases are covered.
+      if (!CR.isSizeLargerThan(ReachableCaseCount)) {
+        BasicBlock *NewUnreachableBB =
+            BasicBlock::Create(BB->getContext(), "default.unreachable",
+                               BB->getParent(), DefaultDest);
+        new UnreachableInst(BB->getContext(), NewUnreachableBB);
+
+        DefaultDest->removePredecessor(BB);
+        SI->setDefaultDest(NewUnreachableBB);
+
+        if (SuccessorsCount[DefaultDest] == 1)
+          DTU.applyUpdates({{DominatorTree::Delete, BB, DefaultDest}});
+        DTU.applyUpdates({{DominatorTree::Insert, BB, NewUnreachableBB}});
+
+        ++NumDeadCases;
+        Changed = true;
+      }
     }
   }
 
@@ -1283,6 +1309,12 @@ CorrelatedValuePropagationPass::run(Function &F, FunctionAnalysisManager &AM) {
   if (!Changed) {
     PA = PreservedAnalyses::all();
   } else {
+#if defined(EXPENSIVE_CHECKS)
+    assert(DT->verify(DominatorTree::VerificationLevel::Full));
+#else
+    assert(DT->verify(DominatorTree::VerificationLevel::Fast));
+#endif // EXPENSIVE_CHECKS
+
     PA.preserve<DominatorTreeAnalysis>();
     PA.preserve<LazyValueAnalysis>();
   }
diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll b/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll
index 701d867..a3b1c89 100644
--- a/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll
@@ -442,7 +442,7 @@ define i32 @switch_range(i32 %cond) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[S:%.*]] = urem i32 [[COND:%.*]], 3
 ; CHECK-NEXT:    [[S1:%.*]] = add nuw nsw i32 [[S]], 1
-; CHECK-NEXT:    switch i32 [[S1]], label [[UNREACHABLE:%.*]] [
+; CHECK-NEXT:    switch i32 [[S1]], label [[DEFAULT_UNREACHABLE:%.*]] [
 ; CHECK-NEXT:      i32 1, label [[EXIT1:%.*]]
 ; CHECK-NEXT:      i32 2, label [[EXIT2:%.*]]
 ; CHECK-NEXT:      i32 3, label [[EXIT1]]
@@ -451,6 +451,8 @@ define i32 @switch_range(i32 %cond) {
 ; CHECK-NEXT:    ret i32 1
 ; CHECK:       exit2:
 ; CHECK-NEXT:    ret i32 2
+; CHECK:       default.unreachable:
+; CHECK-NEXT:    unreachable
 ; CHECK:       unreachable:
 ; CHECK-NEXT:    ret i32 0
 ;
@@ -513,10 +515,9 @@ define i8 @switch_defaultdest_multipleuse(i8 %t0) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[O:%.*]] = or i8 [[T0:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = srem i8 1, [[O]]
-; CHECK-NEXT:    switch i8 [[R]], label [[EXIT:%.*]] [
-; CHECK-NEXT:      i8 0, label [[EXIT]]
-; CHECK-NEXT:      i8 1, label [[EXIT]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       default.unreachable:
+; CHECK-NEXT:    unreachable
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i8 0
 ;
diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/switch.ll b/llvm/test/Transforms/CorrelatedValuePropagation/switch.ll
new file mode 100644
index 0000000..a0794d5
--- /dev/null
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/switch.ll
@@ -0,0 +1,301 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 4
+; RUN: opt < %s -passes=correlated-propagation -S | FileCheck %s
+
+define i32 @test_unreachable_default(i32 noundef %num) {
+; CHECK-LABEL: define i32 @test_unreachable_default(
+; CHECK-SAME: i32 noundef [[NUM:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SUB:%.*]] = add i32 [[NUM]], -120
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[SUB]], 3
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 2
+; CHECK-NEXT:    switch i32 [[COND]], label [[DEFAULT_UNREACHABLE:%.*]] [
+; CHECK-NEXT:      i32 0, label [[SW_BB:%.*]]
+; CHECK-NEXT:      i32 1, label [[SW_BB2:%.*]]
+; CHECK-NEXT:      i32 2, label [[SW_BB4:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       sw.bb:
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @call0()
+; CHECK-NEXT:    br label [[CLEANUP:%.*]]
+; CHECK:       sw.bb2:
+; CHECK-NEXT:    [[CALL3:%.*]] = call i32 @call1()
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       sw.bb4:
+; CHECK-NEXT:    [[CALL5:%.*]] = call i32 @call2()
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       default.unreachable:
+; CHECK-NEXT:    unreachable
+; CHECK:       sw.default:
+; CHECK-NEXT:    [[CALL6:%.*]] = call i32 @call3()
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL6]], [[SW_DEFAULT:%.*]] ], [ [[CALL5]], [[SW_BB4]] ], [ [[CALL3]], [[SW_BB2]] ], [ [[CALL]], [[SW_BB]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %sub = add i32 %num, -120
+  %cmp = icmp ult i32 %sub, 3
+  %cond = select i1 %cmp, i32 %sub, i32 2
+  switch i32 %cond, label %sw.default [
+  i32 0, label %sw.bb
+  i32 1, label %sw.bb2
+  i32 2, label %sw.bb4
+  ]
+
+sw.bb:
+  %call = call i32 @call0()
+  br label %cleanup
+
+sw.bb2:
+  %call3 = call i32 @call1()
+  br label %cleanup
+
+sw.bb4:
+  %call5 = call i32 @call2()
+  br label %cleanup
+
+sw.default:
+  %call6 = call i32 @call3()
+  br label %cleanup
+
+cleanup:
+  %retval.0 = phi i32 [ %call6, %sw.default ], [ %call5, %sw.bb4 ], [ %call3, %sw.bb2 ], [ %call, %sw.bb ]
+  ret i32 %retval.0
+}
+
+define i32 @test_unreachable_default_shared_edge(i32 noundef %num) {
+; CHECK-LABEL: define i32 @test_unreachable_default_shared_edge(
+; CHECK-SAME: i32 noundef [[NUM:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SUB:%.*]] = add i32 [[NUM]], -120
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[SUB]], 3
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 2
+; CHECK-NEXT:    switch i32 [[COND]], label [[DEFAULT_UNREACHABLE:%.*]] [
+; CHECK-NEXT:      i32 0, label [[SW_BB:%.*]]
+; CHECK-NEXT:      i32 1, label [[SW_BB2:%.*]]
+; CHECK-NEXT:      i32 2, label [[SW_BB4:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       sw.bb:
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @call0()
+; CHECK-NEXT:    br label [[CLEANUP:%.*]]
+; CHECK:       sw.bb2:
+; CHECK-NEXT:    [[CALL3:%.*]] = call i32 @call1()
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       default.unreachable:
+; CHECK-NEXT:    unreachable
+; CHECK:       sw.bb4:
+; CHECK-NEXT:    [[CALL5:%.*]] = call i32 @call4(i32 [[SUB]])
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL5]], [[SW_BB4]] ], [ [[CALL3]], [[SW_BB2]] ], [ [[CALL]], [[SW_BB]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %sub = add i32 %num, -120
+  %cmp = icmp ult i32 %sub, 3
+  %cond = select i1 %cmp, i32 %sub, i32 2
+  switch i32 %cond, label %sw.bb4 [
+  i32 0, label %sw.bb
+  i32 1, label %sw.bb2
+  i32 2, label %sw.bb4
+  ]
+
+sw.bb:
+  %call = call i32 @call0()
+  br label %cleanup
+
+sw.bb2:
+  %call3 = call i32 @call1()
+  br label %cleanup
+
+sw.bb4:
+  %val = phi i32 [ %sub, %entry ], [ %sub, %entry ]
+  %call5 = call i32 @call4(i32 %val)
+  br label %cleanup
+
+cleanup:
+  %retval.0 = phi i32 [ %call5, %sw.bb4 ], [ %call3, %sw.bb2 ], [ %call, %sw.bb ]
+  ret i32 %retval.0
+}
+
+; Negative tests
+
+define i32 @test_reachable_default(i32 noundef %num) {
+; CHECK-LABEL: define i32 @test_reachable_default(
+; CHECK-SAME: i32 noundef [[NUM:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SUB:%.*]] = add i32 [[NUM]], -120
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[SUB]], 3
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 4
+; CHECK-NEXT:    switch i32 [[COND]], label [[SW_DEFAULT:%.*]] [
+; CHECK-NEXT:      i32 0, label [[SW_BB:%.*]]
+; CHECK-NEXT:      i32 1, label [[SW_BB2:%.*]]
+; CHECK-NEXT:      i32 2, label [[SW_BB4:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       sw.bb:
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @call0()
+; CHECK-NEXT:    br label [[CLEANUP:%.*]]
+; CHECK:       sw.bb2:
+; CHECK-NEXT:    [[CALL3:%.*]] = call i32 @call1()
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       sw.bb4:
+; CHECK-NEXT:    [[CALL5:%.*]] = call i32 @call2()
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       sw.default:
+; CHECK-NEXT:    [[CALL6:%.*]] = call i32 @call3()
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL6]], [[SW_DEFAULT]] ], [ [[CALL5]], [[SW_BB4]] ], [ [[CALL3]], [[SW_BB2]] ], [ [[CALL]], [[SW_BB]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %sub = add i32 %num, -120
+  %cmp = icmp ult i32 %sub, 3
+  %cond = select i1 %cmp, i32 %sub, i32 4
+  switch i32 %cond, label %sw.default [
+  i32 0, label %sw.bb
+  i32 1, label %sw.bb2
+  i32 2, label %sw.bb4
+  ]
+
+sw.bb:
+  %call = call i32 @call0()
+  br label %cleanup
+
+sw.bb2:
+  %call3 = call i32 @call1()
+  br label %cleanup
+
+sw.bb4:
+  %call5 = call i32 @call2()
+  br label %cleanup
+
+sw.default:
+  %call6 = call i32 @call3()
+  br label %cleanup
+
+cleanup:
+  %retval.0 = phi i32 [ %call6, %sw.default ], [ %call5, %sw.bb4 ], [ %call3, %sw.bb2 ], [ %call, %sw.bb ]
+  ret i32 %retval.0
+}
+
+define i32 @test_unreachable_default_cond_may_be_undef(i32 %num) {
+; CHECK-LABEL: define i32 @test_unreachable_default_cond_may_be_undef(
+; CHECK-SAME: i32 [[NUM:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SUB:%.*]] = add i32 [[NUM]], -120
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[SUB]], 3
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 2
+; CHECK-NEXT:    switch i32 [[COND]], label [[SW_DEFAULT:%.*]] [
+; CHECK-NEXT:      i32 0, label [[SW_BB:%.*]]
+; CHECK-NEXT:      i32 1, label [[SW_BB2:%.*]]
+; CHECK-NEXT:      i32 2, label [[SW_BB4:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       sw.bb:
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @call0()
+; CHECK-NEXT:    br label [[CLEANUP:%.*]]
+; CHECK:       sw.bb2:
+; CHECK-NEXT:    [[CALL3:%.*]] = call i32 @call1()
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       sw.bb4:
+; CHECK-NEXT:    [[CALL5:%.*]] = call i32 @call2()
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       sw.default:
+; CHECK-NEXT:    [[CALL6:%.*]] = call i32 @call3()
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL6]], [[SW_DEFAULT]] ], [ [[CALL5]], [[SW_BB4]] ], [ [[CALL3]], [[SW_BB2]] ], [ [[CALL]], [[SW_BB]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %sub = add i32 %num, -120
+  %cmp = icmp ult i32 %sub, 3
+  %cond = select i1 %cmp, i32 %sub, i32 2
+  switch i32 %cond, label %sw.default [
+  i32 0, label %sw.bb
+  i32 1, label %sw.bb2
+  i32 2, label %sw.bb4
+  ]
+
+sw.bb:
+  %call = call i32 @call0()
+  br label %cleanup
+
+sw.bb2:
+  %call3 = call i32 @call1()
+  br label %cleanup
+
+sw.bb4:
+  %call5 = call i32 @call2()
+  br label %cleanup
+
+sw.default:
+  %call6 = call i32 @call3()
+  br label %cleanup
+
+cleanup:
+  %retval.0 = phi i32 [ %call6, %sw.default ], [ %call5, %sw.bb4 ], [ %call3, %sw.bb2 ], [ %call, %sw.bb ]
+  ret i32 %retval.0
+}
+
+define i32 @test_default_is_already_unreachable(i32 %num) {
+; CHECK-LABEL: define i32 @test_default_is_already_unreachable(
+; CHECK-SAME: i32 [[NUM:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SUB:%.*]] = add i32 [[NUM]], -120
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[SUB]], 3
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 2
+; CHECK-NEXT:    switch i32 [[COND]], label [[SW_DEFAULT:%.*]] [
+; CHECK-NEXT:      i32 0, label [[SW_BB:%.*]]
+; CHECK-NEXT:      i32 1, label [[SW_BB2:%.*]]
+; CHECK-NEXT:      i32 2, label [[SW_BB4:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       sw.bb:
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @call0()
+; CHECK-NEXT:    br label [[CLEANUP:%.*]]
+; CHECK:       sw.bb2:
+; CHECK-NEXT:    [[CALL3:%.*]] = call i32 @call1()
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       sw.bb4:
+; CHECK-NEXT:    [[CALL5:%.*]] = call i32 @call2()
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       sw.default:
+; CHECK-NEXT:    unreachable
+; CHECK:       cleanup:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL5]], [[SW_BB4]] ], [ [[CALL3]], [[SW_BB2]] ], [ [[CALL]], [[SW_BB]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %sub = add i32 %num, -120
+  %cmp = icmp ult i32 %sub, 3
+  %cond = select i1 %cmp, i32 %sub, i32 2
+  switch i32 %cond, label %sw.default [
+  i32 0, label %sw.bb
+  i32 1, label %sw.bb2
+  i32 2, label %sw.bb4
+  ]
+
+sw.bb:
+  %call = call i32 @call0()
+  br label %cleanup
+
+sw.bb2:
+  %call3 = call i32 @call1()
+  br label %cleanup
+
+sw.bb4:
+  %call5 = call i32 @call2()
+  br label %cleanup
+
+sw.default:
+  unreachable
+
+cleanup:
+  %retval.0 = phi i32 [ %call5, %sw.bb4 ], [ %call3, %sw.bb2 ], [ %call, %sw.bb ]
+  ret i32 %retval.0
+}
+
+declare i32 @call0()
+declare i32 @call1()
+declare i32 @call2()
+declare i32 @call3()
+declare i32 @call4(i32)