[SimplifyCFG] Prune code from a provably unreachable switch default

As Sanjoy pointed out over in http://reviews.llvm.org/D11819, a switch on an icmp should always be able to become a branch instruction. This patch generalizes that notion slightly to prove that the default case of a switch is unreachable if the cases completely cover all possible bit patterns in the condition. Once that's done, the switch to branch conversion kicks in just fine.

Note: Duplicate case values are disallowed by the LangRef and verifier.

Differential Revision: http://reviews.llvm.org/D11995

llvm-svn: 246125

2 files changed, 104 insertions, 0 deletions

diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index db260b66db6..c6312a3a4e8 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -3248,6 +3248,23 @@ static bool EliminateDeadSwitchCases(SwitchInst *SI, AssumptionCache *AC,
     }
   }
 
+  // If we can prove that the cases must cover all possible values, the 
+  // default destination becomes dead and we can remove it.
+  bool HasDefault =
+    !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
+  if (HasDefault && Bits < 64 /* avoid overflow */ &&  
+      SI->getNumCases() == (1ULL << Bits)) {
+    DEBUG(dbgs() << "SimplifyCFG: switch default is dead.\n");
+    BasicBlock *NewDefault = SplitBlockPredecessors(SI->getDefaultDest(),
+                                                    SI->getParent(), "");
+    SI->setDefaultDest(NewDefault);
+    SplitBlock(NewDefault, NewDefault->begin());
+    auto *OldTI = NewDefault->getTerminator();
+    new UnreachableInst(SI->getContext(), OldTI);
+    EraseTerminatorInstAndDCECond(OldTI);
+    return true;
+  }
+
   SmallVector<uint64_t, 8> Weights;
   bool HasWeight = HasBranchWeights(SI);
   if (HasWeight) {
diff --git a/llvm/test/Transforms/SimplifyCFG/switch-dead-default.ll b/llvm/test/Transforms/SimplifyCFG/switch-dead-default.ll
new file mode 100644
index 00000000000..b54ea881d8b
--- /dev/null
+++ b/llvm/test/Transforms/SimplifyCFG/switch-dead-default.ll
@@ -0,0 +1,87 @@
+; RUN: opt %s -S -simplifycfg | FileCheck %s
+declare void @foo(i32)
+
+define void @test(i1 %a) {
+; CHECK-LABEL @test
+; CHECK: br i1 [[IGNORE:%.*]], label %true, label %false
+  switch i1 %a, label %default [i1 1, label %true
+                                i1 0, label %false]
+true:
+  call void @foo(i32 1)
+  ret void
+false:
+  call void @foo(i32 3)
+  ret void
+default:
+  call void @foo(i32 2)
+  ret void
+}  
+
+define void @test2(i2 %a) {
+; CHECK-LABEL @test2
+  switch i2 %a, label %default [i2 0, label %case0
+                                i2 1, label %case1
+                                i2 2, label %case2
+                                i2 3, label %case3]
+case0:
+  call void @foo(i32 0)
+  ret void
+case1:
+  call void @foo(i32 1)
+  ret void
+case2:
+  call void @foo(i32 2)
+  ret void
+case3:
+  call void @foo(i32 3)
+  ret void
+default:
+; CHECK-LABEL: default1:
+; CHECK-NEXT: unreachable
+  call void @foo(i32 4)
+  ret void
+}  
+
+; This one is a negative test - we know the value of the default,
+; but that's about it
+define void @test3(i2 %a) {
+; CHECK-LABEL @test3
+  switch i2 %a, label %default [i2 0, label %case0
+                                i2 1, label %case1
+                                i2 2, label %case2]
+
+case0:
+  call void @foo(i32 0)
+  ret void
+case1:
+  call void @foo(i32 1)
+  ret void
+case2:
+  call void @foo(i32 2)
+  ret void
+default:
+; CHECK-LABEL: default:
+; CHECK-NEXT: call void @foo
+  call void @foo(i32 0)
+  ret void
+}  
+
+; Negative test - check for possible overflow when computing
+; number of possible cases.
+define void @test4(i128 %a) {
+; CHECK-LABEL @test4
+  switch i128 %a, label %default [i128 0, label %case0
+                                  i128 1, label %case1]
+
+case0:
+  call void @foo(i32 0)
+  ret void
+case1:
+  call void @foo(i32 1)
+  ret void
+default:
+; CHECK-LABEL: default:
+; CHECK-NEXT: call void @foo
+  call void @foo(i32 0)
+  ret void
+}