Index: SimplifyCFG.cpp
===================================================================
--- SimplifyCFG.cpp	(revision 200617)
+++ SimplifyCFG.cpp	(working copy)
@@ -66,6 +66,10 @@
     "simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true),
     cl::desc("Hoist conditional stores if an unconditional store precedes"));
 
+static cl::opt<bool> CheckHoles(
+    "simplifycfg-check-holes", cl::Hidden, cl::init(true),
+    cl::desc("Allow holes in a value table by testing a mask"));
+
 STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
 STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables");
 STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block");
@@ -3745,12 +3749,33 @@
   uint64_t TableSize = RangeSpread.getLimitedValue() + 1;
   bool TableHasHoles = (NumResults < TableSize);
 
-  // If the table has holes, we need a constant result for the default case.
+  unsigned NeededMaskSize = 0;
+  if (CheckHoles) {
+    if (TableSize <= 32 && TD->fitsInLegalInteger(32))
+      NeededMaskSize = 32;
+    else if (TableSize <= 64 && TD->fitsInLegalInteger(64))
+      NeededMaskSize = 64;
+  }
+
+  // If the table has holes, we need a constant result for the default case...
   SmallVector<std::pair<PHINode*, Constant*>, 4> DefaultResultsList;
-  if (TableHasHoles && !GetCaseResults(SI, 0, SI->getDefaultDest(), &CommonDest,
-                                       DefaultResultsList, TD))
+  bool NeedMask = (TableHasHoles &&
+                  !GetCaseResults(SI, 0, SI->getDefaultDest(), &CommonDest,
+                                  DefaultResultsList, TD));
+  // ...or need to check for valid values with a sufficiently small bit set.
+  if (NeedMask && NeededMaskSize == 0)
     return false;
 
+  if (NeedMask) {
+    // As an extra penalty for the validity test we require more cases.
+    if (SI->getNumCases() < 4)  // TODO: Make threshold configurable.
+      return false;
+    // We need any value to fill the table; the first one suffices.
+    SwitchInst::CaseIt CI = SI->case_begin();
+    GetCaseResults(SI, CI.getCaseValue(), CI.getCaseSuccessor(),
+                   &CommonDest, DefaultResultsList, TD);
+  }
+
   for (size_t I = 0, E = DefaultResultsList.size(); I != E; ++I) {
     PHINode *PHI = DefaultResultsList[I].first;
     Constant *Result = DefaultResultsList[I].second;
@@ -3796,6 +3821,43 @@
 
   // Populate the BB that does the lookups.
   Builder.SetInsertPoint(LookupBB);
+
+  if (NeedMask) {
+    uint64_t UseMask = 0;
+    for (SwitchInst::CaseIt CI = SI->case_begin(), E = SI->case_end();
+         CI != E; ++CI) {
+      ConstantInt *CaseVal = CI.getCaseValue();
+      UseMask |= 1ULL <<
+        (CaseVal->getValue() - MinCaseVal->getValue()).getLimitedValue();
+    }
+
+    BasicBlock *MaskBB = BasicBlock::Create(Mod.getContext(),
+                                            "switch.lookup2",
+                                            CommonDest->getParent(),
+                                            CommonDest);
+    ConstantInt *Zero;
+    ConstantInt *One;
+    ConstantInt *Mask;
+    Value *CmpVal;
+    if (NeededMaskSize == 32) {
+      Zero = Builder.getInt32(0);
+      One = Builder.getInt32(1);
+      Mask = Builder.getInt32(UseMask);
+      CmpVal = Builder.CreateZExtOrTrunc(TableIndex, Builder.getInt32Ty());
+    } else {
+      Zero = Builder.getInt64(0);
+      One = Builder.getInt64(1);
+      Mask = Builder.getInt64(UseMask);
+      CmpVal = Builder.CreateZExtOrTrunc(TableIndex, Builder.getInt64Ty());
+    }
+    Value *Shr = Builder.CreateLShr(Mask, CmpVal);
+    Value *And = Builder.CreateAnd(Shr, One);
+    Value *CmpZ = Builder.CreateICmpNE(And, Zero);
+    Builder.CreateCondBr(CmpZ, MaskBB, SI->getDefaultDest());
+    Builder.SetInsertPoint(MaskBB);
+    LookupBB = MaskBB;
+  }
+
   bool ReturnedEarly = false;
   for (size_t I = 0, E = PHIs.size(); I != E; ++I) {
     PHINode *PHI = PHIs[I];