[SimplifyCFG] Prune code from a provably unreachable switch default

[reames]

Summary

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.

[sanjoy]

Minor drop by comments inline. I'll let someone more familiar with this bit of code do a proper review.

lib/Transforms/Utils/SimplifyCFG.cpp

3256 ↗

(On Diff #31988)

Can SI->getNumCases() ever be > pow(2, Bits)?

I don't think checking for >= is sufficient if switches allow duplicate cases, if that's how number of case can be greater than 2^Bits.

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

25 ↗

(On Diff #31988)

Interesting -- I did not know that i2 4 worked -- I presume this is the same as i2 0?

[sanjoy]

lib/Transforms/Utils/SimplifyCFG.cpp

3256 ↗

(On Diff #31988)

I don't think checking for >= is sufficient if switches allow duplicate cases, if that's how number of case can be greater than 2^Bits.

I had missed your note in the commit message -- given that duplicate values are prohibited, I think it should be sufficient to check for equality.

[reames]

lib/Transforms/Utils/SimplifyCFG.cpp

3256 ↗

(On Diff #31988)

I'll switch to the equality before submission.

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

25 ↗

(On Diff #31988)

Yep, though that really wasn't intentional. I'll adjust the tests to use the more natural 0-3 before submission.

[hans]

Nice!

lib/Transforms/Utils/SimplifyCFG.cpp

3255 ↗

(On Diff #31988)

hmm, why does DeadCases have to be empty?

3256 ↗

(On Diff #31988)

ultra nit: space between , and Bits

[majnemer]

lib/Transforms/Utils/SimplifyCFG.cpp

3256 ↗

(On Diff #31988)

pow uses doubles, was this intentional?

Could we use 1U << Bits or 1ULL << Bits?

[sanjoy]

lib/Transforms/Utils/SimplifyCFG.cpp

3256 ↗

(On Diff #31988)

Could we use 1U << Bits or 1ULL << Bits?

Won't that break if Bits is > 64?

[majnemer]

lib/Transforms/Utils/SimplifyCFG.cpp

3256 ↗

(On Diff #31988)

Right, I guess we'd need to do something like Log2_32(SI->getNumCases()) >= Bits.

[reames]

lib/Transforms/Utils/SimplifyCFG.cpp

3255 ↗

(On Diff #31988)

My original reasoning was that a dead case didn't cover the input, but thinking about it, I think that's false. By proving that it's dead, it still covered that value in the input space. So, it can be removed. :)

3256 ↗

(On Diff #31988)

I'm tempted to use the shift by Bits with an additional constraint that Bits is <= 63. I can't imagine we're every going to see a switch with more than 2^63 cases. :)

[hans]

lib/Transforms/Utils/SimplifyCFG.cpp

3256 ↗

(On Diff #31988)

We won't; a switch can not have more than 2^32 cases (actually it's probably 2^21-1 or something like that).

But I don't think there's any limit to how wide the switch expression is, so we still need to be careful here.

[reames]

Revised per review comments.

[reames]

Add a test case which exercises the Bits > 63 case for completeness.

[hans]

I was trying to remember where I'd seen something like this before, and found this in a patch that never got submitted: http://reviews.llvm.org/D6269#inline-51754

It's taking the same idea a little further by taking known bits into account. For example, if the condition is an i4 where we know the two most significant bits are always 0, having four "live" cases (0,1,2,3) means the default is unreachable.

Would you like to add that here? Could also be a follow-up if you like.

[reames]

In D11995#224516, @hans wrote:

I was trying to remember where I'd seen something like this before, and found this in a patch that never got submitted: http://reviews.llvm.org/D6269#inline-51754

It's taking the same idea a little further by taking known bits into account. For example, if the condition is an i4 where we know the two most significant bits are always 0, having four "live" cases (0,1,2,3) means the default is unreachable.

Would you like to add that here? Could also be a follow-up if you like.

This sounds like an interesting follow on, but let me land the current change first. Once that's in, I'll extend as you propose.

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

for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) {
     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.
+  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) {
     GetBranchWeights(SI, Weights);
     HasWeight = (Weights.size() == 1 + SI->getNumCases());
   }
 
   // Remove dead cases from the switch.

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: 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
+}