[SimplifyCFG] Use known bits to eliminate dead switch defaults

[reames]

Summary

This is a follow up to http://reviews.llvm.org/D11995 implementing the suggestion by Hans.

If we know some of the bits of the value being switched on, we know that the maximum number of unique cases covers the unknown bits. This allows to eliminate switch defaults for large integers (i32) when most bits in the value are known.

Note that I had to make the transform contingent on not having any dead cases. This is conservatively correct with the old code, but required for the new code since we might have a dead case which varies one of the known bits. Counting that towards our number of covering cases would be bad.

[hans]

Thanks for the patch!

lib/Transforms/Utils/SimplifyCFG.cpp

3262 ↗

(On Diff #33601)

Instead of making this contingent on DeadCases.empty(), can't we use "SI->getNumCases() - DeadCases.size()" to get the number of live cases?

The situation I have in mind:

x &= 0x3; // NumUnknownBits is now 2
switch (x) {
case 0, 1, 2, 3: stuff
case 5: dead
default: dead
}

[reames]

lib/Transforms/Utils/SimplifyCFG.cpp

3262 ↗

(On Diff #33601)

This example will work today, just as two rounds. We'll first delete the dead case, then come back around (within the same run of the pass) and delete the dead default. Your requested change would basically just change the order of the two steps. We could try to do everything at once, but doing each step individually seems less error prone.

[hans]

lgtm

lib/Transforms/Utils/SimplifyCFG.cpp

3262 ↗

(On Diff #33601)

Even if the next round will take care of it, it seems simple enough that we might as well handle it while we're here the first time.

It's no big deal though, and if you prefer to not do it that's fine too; as long as the example works, I'm happy.

[hans]

Did this land?

llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp

if ((I.getCaseValue()->getValue() & KnownZero) != 0 ||
         (I.getCaseValue()->getValue() & KnownOne) != KnownOne) {
       DeadCases.push_back(I.getCaseValue());
       DEBUG(dbgs() << "SimplifyCFG: switch case '"
                    << I.getCaseValue() << "' is dead.\n");
     }
   }
 
   // If we can prove that the cases must cover all possible values, the 
-  // default destination becomes dead and we can remove it.
+  // default destination becomes dead and we can remove it.  If we know some 
+  // of the bits in the value, we can use that to more precisely compute the
+  // number of possible unique case values.
   bool HasDefault =
     !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
-  if (HasDefault && Bits < 64 /* avoid overflow */ &&  
-      SI->getNumCases() == (1ULL << Bits)) {
+  const unsigned NumUnknownBits = Bits - 
+    (KnownZero.Or(KnownOne)).countPopulation();
+  assert(0 <= NumUnknownBits && NumUnknownBits <= Bits);
+  if (HasDefault && DeadCases.empty() &&
+      NumUnknownBits < 64 /* avoid overflow */ &&  
+      SI->getNumCases() == (1ULL << NumUnknownBits)) {
     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);

llvm/trunk/test/Transforms/SimplifyCFG/switch-dead-default.ll

 ; RUN: opt %s -S -simplifycfg | FileCheck %s
 declare void @foo(i32)
 
 define void @test(i1 %a) {
-; CHECK-LABEL @test
+; 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
+; 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:

 ; 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
+; 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
+; 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
 }  
+
+; All but one bit known zero
+define void @test5(i8 %a) {
+; CHECK-LABEL: @test5
+; CHECK: br i1 [[IGNORE:%.*]], label %true, label %false
+  %cmp = icmp ult i8 %a, 2 
+  call void @llvm.assume(i1 %cmp)
+  switch i8 %a, label %default [i8 1, label %true
+                                i8 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
+} 
+
+;; All but one bit known one
+define void @test6(i8 %a) {
+; CHECK-LABEL: @test6
+; CHECK: @llvm.assume
+; CHECK: br i1 [[IGNORE:%.*]], label %true, label %false
+  %and = and i8 %a, 254
+  %cmp = icmp eq i8 %and, 254 
+  call void @llvm.assume(i1 %cmp)
+  switch i8 %a, label %default [i8 255, label %true
+                                i8 254, 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
+}
+
+; Check that we can eliminate both dead cases and dead defaults
+; within a single run of simplify-cfg
+define void @test7(i8 %a) {
+; CHECK-LABEL: @test7
+; CHECK: @llvm.assume
+; CHECK: br i1 [[IGNORE:%.*]], label %true, label %false
+  %and = and i8 %a, 254
+  %cmp = icmp eq i8 %and, 254 
+  call void @llvm.assume(i1 %cmp)
+  switch i8 %a, label %default [i8 255, label %true
+                                i8 254, label %false
+                                i8 0, label %also_dead]
+true:
+  call void @foo(i32 1)
+  ret void
+false:
+  call void @foo(i32 3)
+  ret void
+also_dead:
+  call void @foo(i32 5)
+  ret void
+default:
+  call void @foo(i32 2)
+  ret void
+}
+
+;; All but one bit known undef
+;; Note: This is currently testing an optimization which doesn't trigger. The
+;; case this is protecting against is that a bit could be assumed both zero 
+;; *or* one given we know it's undef.  ValueTracking doesn't do this today,
+;; but it doesn't hurt to confirm.
+define void @test8(i8 %a) {
+; CHECK-LABEL: @test8(
+; CHECK: switch i8
+  %and = and i8 %a, 254
+  %cmp = icmp eq i8 %and, undef
+  call void @llvm.assume(i1 %cmp)
+  switch i8 %a, label %default [i8 255, label %true
+                                i8 254, 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
+}
+
+declare void @llvm.assume(i1)