Index: lib/Transforms/Utils/SimplifyCFG.cpp
===================================================================
--- lib/Transforms/Utils/SimplifyCFG.cpp
+++ lib/Transforms/Utils/SimplifyCFG.cpp
@@ -135,6 +135,8 @@
     NumLookupTablesHoles,
     "Number of switch instructions turned into lookup tables (holes checked)");
 STATISTIC(NumTableCmpReuses, "Number of reused switch table lookup compares");
+STATISTIC(NumSwitchWidened,
+          "Number of switch instructions widened to cover all possible values");
 STATISTIC(NumSinkCommons,
           "Number of common instructions sunk down to the end block");
 STATISTIC(NumSpeculations, "Number of speculative executed instructions");
@@ -4842,6 +4844,104 @@
   SI->eraseFromParent();
 }
 
+// Analyze the switch expression and compute the highest possible value of the
+// expression and if known then remap the known default values into individual
+// case statements and direct them to the default block.  Then mark the default
+// destination as unreachable.
+static bool widenSwitchRangeToCoverAllValues(SwitchInst *SI,
+                                             const DataLayout &DL,
+                                             const TargetTransformInfo &TTI) {
+  unsigned ValueWidth = DL.getTypeSizeInBits(SI->getOperand(0)->getType());
+  unsigned OrigValueWidth = ValueWidth;
+  KnownBits Known(ValueWidth);
+  llvm::computeKnownBits(SI->getOperand(0), Known, DL);
+
+  bool UnreachableDefault =
+      isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
+
+  // We only care for non-negative values.  The number of minimum leading
+  // zeros plus the number of maximum trailing ones should be equal to the
+  // width of the value.  If the default is unreachable then we skip this
+  // optimization.
+  if (Known.isNegative()  ||  UnreachableDefault  ||
+      (Known.countMinLeadingZeros() + Known.countMaxTrailingOnes()) !=
+         ValueWidth)
+    return false;
+
+  // ValueWidth should be the minimum width needed to represent
+  // MaxSwitchValue * 100.  Since 100 needs 7 bits we add 7 to ValueWidth.
+  ValueWidth += 7;
+
+  APInt NumCases(ValueWidth, SI->getNumCases());
+  APInt MaxSwitchValue = (~Known.Zero).zext(ValueWidth);
+  APInt Hundred = APInt(ValueWidth, 100);
+  APInt Seventy = APInt(ValueWidth, 70);
+
+  // At least 70% of the possible values must be defined as case statements
+  // so that there is no penalty for those which have few defined case
+  // statements.
+  if (MaxSwitchValue.ugt(NumCases)  &&
+      SI->getNumCases() > 0  &&
+      (NumCases * Hundred).udiv(MaxSwitchValue).uge(Seventy)) {
+    // Here we not only need to care for those values that are beyond the
+    // highest case value and up to the MaxSwitchValue but also for the other
+    // missing values (holes) that appear between the already defined cases.
+    BasicBlock *DefaultBlock = SI->getDefaultDest();
+    assert(SI->case_begin() != SI->case_end());
+    SmallVector<ConstantInt *, 16> Cases;
+
+    for (auto Case : SI->cases())
+      Cases.push_back(Case.getCaseValue());
+
+    // The function CasesAreContiguous sorts the vector Cases in descending
+    // order.
+    if (CasesAreContiguous(Cases)) {
+      for (APInt I = (Cases[0]->getValue().zext(ValueWidth) + 1);
+           I.ule(MaxSwitchValue);  I++) {
+        SI->addCase(ConstantInt::get(DefaultBlock->getContext(),
+                    I.trunc(OrigValueWidth)), DefaultBlock);
+        if (MaxSwitchValue.ne(I)) {
+            AddPredecessorToBlock(DefaultBlock, SI->getParent(), SI->getParent());
+        }
+      }
+    } else {
+      unsigned int i = 0;
+      bool SeenFirstDefaultCase = false;
+      for (APInt I = MaxSwitchValue, E(ValueWidth, -1);  I.ne(E);  I--) {
+        if (i >= Cases.size()  ||
+            Cases[i]->getValue().zext(ValueWidth) != I) {
+          SI->addCase(ConstantInt::get(DefaultBlock->getContext(),
+                      I.trunc(OrigValueWidth)), DefaultBlock);
+          if (SeenFirstDefaultCase)
+            AddPredecessorToBlock(DefaultBlock, SI->getParent(), SI->getParent());
+          else
+            SeenFirstDefaultCase = true;
+        } else {
+          i++;
+        }
+      }
+    }
+
+    // We have already added cases for all the possible values including those
+    // that would have mapped to the default case and redirected the newly
+    // added cases to the original default block.  Hence, the new default block 
+    // can be marked as unreachable.
+    BasicBlock *NewDefaultBlock;
+    NewDefaultBlock = BasicBlock::Create(DefaultBlock->getContext(),
+                                         "switch.unreachable.default",
+                                         DefaultBlock->getParent());
+    UnreachableInst *dummyInst LLVM_ATTRIBUTE_UNUSED;
+    dummyInst = new UnreachableInst(NewDefaultBlock->getContext(),
+                                    NewDefaultBlock);
+    SI->setDefaultDest(NewDefaultBlock);
+    SI->Widened = true;
+    ++NumSwitchWidened;
+    return true;
+  }
+
+  return false;
+}
+
 /// If the switch is only used to initialize one or more
 /// phi nodes in a common successor block with only two different
 /// constant values, replace the switch with select.
@@ -5614,6 +5714,11 @@
         return requestResimplify();
   }
 
+  // Try to convert small number of default values to individual case
+  // statements pointing to the default block.
+  if (widenSwitchRangeToCoverAllValues(SI, DL, TTI))
+    return requestResimplify();
+
   // Try to transform the switch into an icmp and a branch.
   if (TurnSwitchRangeIntoICmp(SI, Builder))
     return requestResimplify();