[SimplifyCFG] Also use 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

I did the full llvm test suite with this, on ppc64le and x86_64.

On top of D61237 and D61159 (which went in and then were reverted)

The idea is to put both in at the same time, so the test suite passes, but the build never breaks.

D62465 is this same commit

[shawnl]

fix tests when building tests for ALL architectures

there is one very small regression here, that a test checks for, (the three patches are together in terms of passing tests) where an unnecessary subtraction is added (and in a very few cases), but patches I have already written take care of this, so I don't think it is a big deal.

llvm/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) ||
-      (Shift > countTrailingZeros(BestIndexXor) &&
-       Values[BestIndex] >= SubThreshold)) {
+  if ((BestIndexXor >= Threshold && Shift == 0) ||
+      ((Shift > countTrailingZeros(BestIndexXor) &&
+        Values[BestIndex] >= Threshold))) {
     Base = BestIndexXor;
     MadeChanges = true;
     for (auto &V : Values)
       V = (APInt(BitWidth, V) - Base).getLimitedValue();
   }

llvm/test/Transforms/SimplifyCFG/rangereduce.ll

   ret i32 99783
 }
 
 define i32 @test9(i32 %a) {
 ; CHECK-LABEL: @test9(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[A:%.*]], 1
-; CHECK-NEXT:    [[TMP2:%.*]] = shl i32 [[A]], 31
-; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    switch i32 [[TMP3]], label [[DEF:%.*]] [
-; CHECK-NEXT:    i32 9, label [[ONE:%.*]]
-; CHECK-NEXT:    i32 10, label [[TWO:%.*]]
-; CHECK-NEXT:    i32 3, label [[THREE:%.*]]
-; CHECK-NEXT:    i32 5, label [[THREE]]
+; CHECK-NEXT:    switch i32 [[A:%.*]], label [[DEF:%.*]] [
+; CHECK-NEXT:    i32 18, label [[ONE:%.*]]
+; CHECK-NEXT:    i32 20, label [[TWO:%.*]]
+; CHECK-NEXT:    i32 6, label [[THREE:%.*]]
+; CHECK-NEXT:    i32 10, label [[THREE]]
 ; CHECK-NEXT:    ]
 ; CHECK:       def:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ]
 ; CHECK-NEXT:    ret i32 [[MERGE]]
 ; CHECK:       one:

llvm/test/Transforms/SimplifyCFG/switch-simplify-range.ll

 
 define i64 @switch_common_right_bits(i8 %a) #0  {
 ; CHECK-LABEL: @switch_common_right_bits(
 ; CHECK-NEXT:  Entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 [[A:%.*]], 123
-; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.fshr.i8(i8 [[TMP0]], i8 [[TMP0]], i8 1)
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 5
-; CHECK-NEXT:    br i1 [[TMP2]], label [[SWITCH_LOOKUP:%.*]], label [[SWITCHELSE:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = shl i8 [[TMP0]], 7
+; CHECK-NEXT:    [[TMP3:%.*]] = or i8 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ult i8 [[TMP3]], 9
+; CHECK-NEXT:    br i1 [[TMP4]], label [[SWITCH_LOOKUP:%.*]], label [[SWITCHELSE:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [5 x i64], [5 x i64]* @switch.table.switch_common_right_bits, i32 0, i8 [[TMP1]]
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [9 x i64], [9 x i64]* @switch.table.switch_common_right_bits, i32 0, i8 [[TMP3]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i64, i64* [[SWITCH_GEP]]
 ; CHECK-NEXT:    ret i64 [[SWITCH_LOAD]]
 ; CHECK:       SwitchElse:
 ; CHECK-NEXT:    ret i64 10
 ;

   i8 123, label %SwitchProng
   i8 125, label %SwitchProng1
   i8 127, label %SwitchProng2
   i8 129, label %SwitchProng3
   i8 131, label %SwitchProng4
+  i8 133, label %SwitchProng5
+  i8 135, label %SwitchProng6
+  i8 137, label %SwitchProng7
+  i8 139, label %SwitchProng8
   ]
 SwitchElse:                                       ; preds = %Entry
   ret i64 10
 SwitchProng:                                      ; preds = %Entry
   ret i64 6

   ret i64 4
 SwitchProng3:                                     ; preds = %Entry
   ret i64 2
 SwitchProng4:                                     ; preds = %Entry
   ret i64 1
+SwitchProng5:
+  ret i64 5
+SwitchProng6:
+  ret i64 849
+SwitchProng7:
+  ret i64 993
+SwitchProng8:
+  ret i64 342
 }
 
 define i64 @switch_clz1(i16 %a) optsize #0  {
 ; CHECK-LABEL: @switch_clz1(
 ; CHECK-NEXT:  Entry: