[SimplifyCFG] eliminate switch cases based on known range of switch condition

[spatel]

Summary

This was noted in PR24766:
https://llvm.org/bugs/show_bug.cgi?id=24766#c2

We may not know whether the sign bit(s) are zero or one, but we can still optimize based on knowing that the sign bit is repeated.

[davidxl]

lib/Transforms/Utils/SimplifyCFG.cpp

3870

MinCondWidth --> MaxCondWidth?

[spatel]

lib/Transforms/Utils/SimplifyCFG.cpp

3870

Yes, that's vague. How about "MaxSignificantBitsInCond"?

[spatel]

Patch updated:
Changed variable name to be less ambiguous.

[davidxl]

lgtm

lib/Transforms/Utils/SimplifyCFG.cpp

 /// and use it to remove dead cases.
 static bool EliminateDeadSwitchCases(SwitchInst *SI, AssumptionCache *AC,
                                      const DataLayout &DL) {
   Value *Cond = SI->getCondition();
   unsigned Bits = Cond->getType()->getIntegerBitWidth();
   APInt KnownZero(Bits, 0), KnownOne(Bits, 0);
   computeKnownBits(Cond, KnownZero, KnownOne, DL, 0, AC, SI);
 
+  // In addition to known bits, we can trim dead cases by determining that their
+  // values are outside of the limited range of the condition based on how many
+  // significant (non-sign) bits are in that value.
+  unsigned ExtraSignBits = ComputeNumSignBits(Cond, DL, 0, AC, SI) - 1;
+  unsigned MinCondWidth = Bits - ExtraSignBits;
+
   // Gather dead cases.
   SmallVector<ConstantInt*, 8> DeadCases;
   for (auto &Case : SI->cases()) {
-    if ((Case.getCaseValue()->getValue() & KnownZero) != 0 ||
-        (Case.getCaseValue()->getValue() & KnownOne) != KnownOne) {
+    APInt CaseVal = Case.getCaseValue()->getValue();
+    if ((CaseVal & KnownZero) != 0 || (CaseVal & KnownOne) != KnownOne ||
+        (CaseVal.getMinSignedBits() > MinCondWidth)) {
       DeadCases.push_back(Case.getCaseValue());
-      DEBUG(dbgs() << "SimplifyCFG: switch case '"
-                   << Case.getCaseValue() << "' is dead.\n");
+      DEBUG(dbgs() << "SimplifyCFG: switch case " << CaseVal << " 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.  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 =

test/Transforms/SimplifyCFG/switch-masked-bits.ll

 }
 
 ; We're sign extending an 8-bit value.
 ; The switch condition must be in the range [-128, 127], so any cases outside of that range must be dead.
 
 define i1 @repeated_signbits(i8 %condition) {
 ; CHECK-LABEL: @repeated_signbits(
 ; CHECK:         switch i32
-; CHECK-DAG:     i32 -2147483648, label %a
-; CHECK-DAG:     i32 -129, label %a
 ; CHECK-DAG:     i32 -128, label %a
 ; CHECK-DAG:     i32 -1, label %a
 ; CHECK-DAG:     i32  0, label %a
 ; CHECK-DAG:     i32  127, label %a
-; CHECK-DAG:     i32  128, label %a
-; CHECK-DAG:     i32  2147483647, label %a
 ; CHECK-NEXT:    ]
 ;
 entry:
   %sext = sext i8 %condition to i32
   switch i32 %sext, label %default [
   i32 -2147483648, label %a
   i32 -129, label %a
   i32 -128, label %a