[SimplifyCFG] use fshr instead of shl/lshr/or

[shawnl]

Summary

We already try (but fail due to lack of sub op)
to convert this to fshr in AggressiveInstCombine.cpp:92.

If a target cannot lower fshr/fshl then it needs to be fixed.
Performance on targets that have such an instruction should
not be penalized.

[shawnl]

somehow ended up with two of these

lib/Transforms/Utils/SimplifyCFG.cpp

   // 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);
   auto *ShiftC = ConstantInt::get(Ty, Shift);
   auto *Sub = Builder.CreateSub(SI->getCondition(), ConstantInt::get(Ty, Base));
-  auto *LShr = Builder.CreateLShr(Sub, ShiftC);
-  auto *Shl = Builder.CreateShl(Sub, Ty->getBitWidth() - Shift);
-  auto *Rot = Builder.CreateOr(LShr, Shl);
+  Function *Fshr = Intrinsic::getDeclaration(SI->getModule(), Intrinsic::fshr, Ty);
+  auto *Rot = Builder.CreateCall(Fshr, {Sub, Sub, ShiftC});
   SI->replaceUsesOfWith(SI->getCondition(), Rot);
 
   for (auto Case : SI->cases()) {
     auto *Orig = Case.getCaseValue();
     auto Sub = Orig->getValue() - APInt(Ty->getBitWidth(), Base);
     Case.setValue(
         cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(ShiftC->getValue()))));
   }

test/Transforms/SimplifyCFG/rangereduce.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -switch-to-lookup -S | FileCheck %s
 ; RUN: opt < %s -passes='simplify-cfg<switch-to-lookup>' -S | FileCheck %s
 
 target datalayout = "e-n32"
 
 define i32 @test1(i32 %a) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
-; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[DEF:%.*]] [
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.fshr.i32(i32 [[TMP1]], i32 [[TMP1]], i32 2)
+; CHECK-NEXT:    switch i32 [[TMP2]], label [[DEF:%.*]] [
 ; CHECK-NEXT:    i32 0, label [[ONE:%.*]]
 ; CHECK-NEXT:    i32 1, label [[TWO:%.*]]
 ; CHECK-NEXT:    i32 2, label [[THREE:%.*]]
 ; CHECK-NEXT:    i32 3, label [[THREE]]
 ; CHECK-NEXT:    ]
 ; CHECK:       def:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ]
 ; CHECK-NEXT:    ret i32 [[MERGE]]
two:
   ret i32 1143
 three:
   ret i32 99783
 }
 
 define i32 @test6(i32 %a) optsize {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], -109
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
-; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[DEF:%.*]] [
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.fshr.i32(i32 [[TMP1]], i32 [[TMP1]], i32 2)
+; CHECK-NEXT:    switch i32 [[TMP2]], label [[DEF:%.*]] [
 ; CHECK-NEXT:    i32 3, label [[ONE:%.*]]
 ; CHECK-NEXT:    i32 2, label [[TWO:%.*]]
 ; CHECK-NEXT:    i32 1, label [[THREE:%.*]]
 ; CHECK-NEXT:    i32 0, label [[THREE]]
 ; CHECK-NEXT:    ]
 ; CHECK:       def:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ]
 ; CHECK-NEXT:    ret i32 [[MERGE]]
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:    [[TMP5:%.*]] = icmp ult i8 [[TMP4]], 4
-; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[DEF:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.fshr.i8(i8 [[TMP1]], i8 [[TMP1]], i8 2)
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i8 [[TMP2]], 4
+; CHECK-NEXT:    br i1 [[TMP3]], label [[SWITCH_LOOKUP:%.*]], label [[DEF:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = zext i8 [[TMP4]] to i32
+; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = zext i8 [[TMP2]] 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]]
 ; CHECK:       def:
 ; CHECK-NEXT:    ret i8 -93
 ;
   switch i8 %a, label %def [
two:
   ret i8 1143
 three:
   ret i8 99783
 }
 
 define i32 @test8(i32 %a) optsize {
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
-; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[DEF:%.*]] [
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.fshr.i32(i32 [[TMP1]], i32 [[TMP1]], i32 2)
+; CHECK-NEXT:    switch i32 [[TMP2]], label [[DEF:%.*]] [
 ; CHECK-NEXT:    i32 0, label [[ONE:%.*]]
 ; CHECK-NEXT:    i32 1, label [[TWO:%.*]]
 ; CHECK-NEXT:    i32 2, label [[THREE:%.*]]
 ; CHECK-NEXT:    i32 4, label [[THREE]]
 ; CHECK-NEXT:    ]
 ; CHECK:       def:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ]
 ; CHECK-NEXT:    ret i32 [[MERGE]]
two:
   ret i32 1143
 three:
   ret i32 99783
 }
 
 define i32 @test9(i32 %a) {
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 6
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 1
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 31
-; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[DEF:%.*]] [
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.fshr.i32(i32 [[TMP1]], i32 [[TMP1]], i32 1)
+; CHECK-NEXT:    switch i32 [[TMP2]], label [[DEF:%.*]] [
 ; CHECK-NEXT:    i32 6, label [[ONE:%.*]]
 ; CHECK-NEXT:    i32 7, label [[TWO:%.*]]
 ; CHECK-NEXT:    i32 0, label [[THREE:%.*]]
 ; CHECK-NEXT:    i32 2, label [[THREE]]
 ; CHECK-NEXT:    ]
 ; CHECK:       def:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ]
 ; CHECK-NEXT:    ret i32 [[MERGE]]