[SimplifyCFG] Also using the SwitchReduceRange Threshold for shift operations.

[shawnl]

Summary

There is a test that happens to want it this way

CodeGen/Thumb2/constant-islands-jump-table.ll

[shawnl]

this should use saturating multiplication

[shawnl]

use saturating multiply

[nikic]

Before we go any further here, I'd suggest to revert all the switch related changes that have landed for now. They've had a lot of test fallout, and it looks like they broke the ubsan (and msan and asan) builders (see e.g. http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap-ubsan/builds/13084) in a way that looks like a miscompile of the clang bootstrap to me. Hard to tell which change exactly is at fault as multiple were pushed at the same time. As such I'd suggest to revert back to a green build and then reapply changes more carefully, such that tests pass for each individual commit.

[shawnl]

Yes, can you revert them. I really am not very skilled with svn.

lib/Transforms/Utils/SimplifyCFG.cpp

 /// This converts a sparse switch into a dense switch which allows better
 /// lowering and could also allow transforming into a lookup table.
 static bool ReduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder,
                               const DataLayout &DL,
                               const TargetTransformInfo &TTI) {
-  // The number of cases that need to be removed by a subtraction operation
-  // to make it worth using.
-  const unsigned SubThreshold = (SI->getFunction()->hasOptSize() ? 2 : 8);
+  // The number of cases that need to be removed by a subtraction or
+  // shift right operation to make it worth using.
+  const unsigned Threshold = (SI->getFunction()->hasOptSize() ? 2 : 8);
   auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
   unsigned BitWidth = CondTy->getIntegerBitWidth();
   if (BitWidth > 64 || !DL.fitsInLegalInteger(BitWidth))
     return false;
   // Only bother with this optimization if there are more than 3 switch cases;

   uint64_t BestIndexXor = Values[BestIndex];
   for (auto &V : Values)
     Shift = std::min(Shift, countTrailingZeros(V ^ BestIndexXor));
   assert(Shift < 64);
   if (Shift > 0) {
-    MadeChanges = true;
-    for (auto &V : Values)
-      V >>= Shift;
+    if (SaturatingMultiply<uint64_t>((1ULL << Shift) - 1, Values.size()) >= Threshold) {
+      MadeChanges = true;
+      for (auto &V : Values)
+        V >>= Shift;
+    } else
+      // Not worth it.
+      Shift = 0;
   }
 
   // We Xor against Values[] (any element will do) because the if we do not
-  // start at zero, but also don't meet the SubThreshold, then we still might
+  // start at zero, but also don't meet the Threshold, then we still might
   // share common rights bits, and if this transform succeeds
   // then we should insert the subtraction anyways, because the rotate trick
   // below to avoid a branch needs the shifted away bits to be zero.
 
   // Now transform the values such that they start at zero and ascend. Do not
-  // do this if the shift reduces the lowest value to less than SubThreshold,
-  // or if the subtraction is less than SubThreshold and it does not enable a
+  // do this if the shift reduces the lowest value to less than Threshold,
+  // or if the subtraction is less than Threshold and it does not enable a
   // rotate.
   uint64_t Base = 0;
-  if ((BestIndexXor >= SubThreshold && Shift == 0) ||
+  if ((BestIndexXor >= Threshold && Shift == 0) ||
       (Shift > countTrailingZeros(BestIndexXor) &&
-       Values[BestIndex] >= SubThreshold)) {
+       Values[BestIndex] >= Threshold)) {
     Base = BestIndexXor;
     MadeChanges = true;
     for (auto &V : Values)
       V = (APInt(BitWidth, V) - Base).getLimitedValue();
   }