[SimplifyCFG] ReduceSwitchRange: Improve on the case where the SubThreshold doesn't trigger

[shawnl]

Summary

This is patch 5 is a series beginning with D61150

[shawnl]

remove some dead code

[shawnl]

bugs

[shawnl]

bugs, tests

[shawnl]

type

[jmolloy]

LGTM with a couple of nits. Thanks!

lib/Transforms/Utils/SimplifyCFG.cpp

5578

Values[any] -> Values[BestIndex]?

5592

I don't think this comment serves any purpose split. Just cat it onto the end of the ... above, I think.

[shawnl]

no longer depends on cttz transform

[shawnl]

applied 361728

lib/Transforms/Utils/SimplifyCFG.cpp

uint64_t BestDistance =
       Values.back() + Values.front() + 1;
   unsigned BestIndex = 0;
   for (unsigned I = 1, E = Values.size(); I != E; I++) {
     if (Values[I] - Values[I - 1] > BestDistance) {
       BestIndex = I;
       BestDistance = Values[I] - Values[I - 1];
     }
   }
-  uint64_t Base = 0;
-  // Now transform the values such that they start at zero and ascend.
-  if (Values[BestIndex] >= SubThreshold) {
-    Base = Values[BestIndex];
-    MadeChanges = true;
-    for (auto &V : Values)
-      V = (APInt(BitWidth, V) - Base).getLimitedValue();
-  }
-
-  // Now we have signed numbers that have been shifted so that, given enough
-  // precision, there are no negative values. Since the rest of the transform
-  // is bitwise only, we switch now to an unsigned representation.
 
   // This transform can be done speculatively because it is so cheap - it
   // results in a single rotate operation being inserted.
   // FIXME: It's possible that optimizing a switch on powers of two might also
   // be beneficial - flag values are often powers of two and we could use a CLZ
   // as the key function.
 
   // countTrailingZeros(0) returns 64. As Values is guaranteed to have more than
   // one element and LLVM disallows duplicate cases, Shift is guaranteed to be
   // less than 64.
   unsigned Shift = 64;
+  // We need to store this from _before_ the transform
+  uint64_t BestIndexXor = Values[BestIndex];
   for (auto &V : Values)
-    Shift = std::min(Shift, countTrailingZeros(V));
+    Shift = std::min(Shift, countTrailingZeros(V ^ BestIndexXor));
   assert(Shift < 64);
   if (Shift > 0) {
     MadeChanges = true;
     for (auto &V : Values)
       V >>= Shift;
   }
 
+  // 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
+  // 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
+  // rotate.
+  uint64_t Base = 0;
+  if ((BestIndexXor >= SubThreshold && Shift == 0) ||
+      (Shift > countTrailingZeros(BestIndexXor) &&
+       Values[BestIndex] >= SubThreshold)) {
+    Base = BestIndexXor;
+    MadeChanges = true;
+    for (auto &V : Values)
+      V = (APInt(BitWidth, V) - Base).getLimitedValue();
+  }
+
   if (!MadeChanges)
     // We didn't do anything.
     return false;
 
   // The obvious transform is to shift the switch condition right and emit a
   // check that the condition actually cleanly divided by GCD, i.e.
   //   C & (1 << Shift - 1) == 0
   // inserting a new CFG edge to handle the case where it didn't divide cleanly.
   //
   // A cheaper way of doing this is a simple ROTR(C, Shift). This performs the
   // shift and puts the shifted-off bits in the uppermost bits. If any of these
   // are nonzero then the switch condition will be very large and will hit the
   // default case.
 
   auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
   Builder.SetInsertPoint(SI);
   Value *Key = SI->getCondition();
   if (Base > 0)
     Key = Builder.CreateSub(Key, ConstantInt::get(Ty, Base));
   if (Shift > 0) {
     // FIXME replace with fshr?
     auto *ShiftC = ConstantInt::get(Ty, Shift);
     auto *LShr = Builder.CreateLShr(Key, ShiftC);
     auto *Shl = Builder.CreateShl(Key, Ty->getBitWidth() - Shift);
     Key = Builder.CreateOr(LShr, Shl);
   }
   SI->replaceUsesOfWith(SI->getCondition(), Key);
 
   for (auto Case : SI->cases()) {
     auto *Orig = Case.getCaseValue();
-    auto Sub = Orig->getValue() - APInt(Ty->getBitWidth(), Base);
+    auto Sub = Orig->getValue() - Base;
     Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
   }
   return true;
 }
 
 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
   BasicBlock *BB = SI->getParent();
 

test/Transforms/SimplifyCFG/rangereduce.ll

 two:
   ret i32 1143
 three:
   ret i32 99783
 }
 
 define i8 @test7(i8 %a) optsize {
 ; CHECK-LABEL: @test7(
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i8 [[A:%.*]], -36
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i8 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i8 [[TMP1]], 6
-; CHECK-NEXT:    [[TMP4:%.*]] = or i8 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 [[A:%.*]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = shl i8 [[A]], 6
+; CHECK-NEXT:    [[TMP3:%.*]] = or i8 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = sub i8 [[TMP3]], 55
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i8 [[TMP4]], 4
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[DEF:%.*]]
 ; CHECK:       switch.lookup:
 ; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = zext i8 [[TMP4]] to i32
 ; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i32 [[SWITCH_CAST]], 8
 ; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i32 -943228976, [[SWITCH_SHIFTAMT]]
 ; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i32 [[SWITCH_DOWNSHIFT]] to i8
 ; CHECK-NEXT:    ret i8 [[SWITCH_MASKED]]