[InstCombine] Simplify funnel shift with one zero/undef operands to simple shift

[nikic]

Summary

The following simplifications are implemented:

• fshl(X, 0, C) -> shl X, C%BW
• fshl(X, undef, C) -> shl X, C%BW (assuming undef = 0)
• fshl(0, X, C) -> lshr X, BW-C%BW
• fshl(undef, X, C) -> lshr X, BW-C%BW (assuming undef = 0)
• fshr(X, 0, C) -> shl X, (BW-C%BW)
• fshr(X, undef, C) -> shl X, BW-C%BW (assuming undef = 0)
• fshr(0, X, C) -> lshr X, C%BW
• fshr(undef, X, C) -> lshr, X, C%BW (assuming undef = 0)

The simplification is only performed if the shift amount C is constant, because we can explicitly compute C%BW and BW-C%BW in this case.

---

This change has been split off from D54666 and handling for the zero case has been added. Unfortunately that also means new tests :(

[nikic]

Rebase over baseline tests.

[spatel]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2000

This can be made an assert. We are guaranteed to call InstSimplify (line 1844) for this instruction before we reach this point in InstCombine.

2009

The convention is to use something like:

return BinaryOperator::CreateShl(Op0, ShiftAmt);

...then InstCombine handles the replacement in the calling function.

2014–2015

Similar to above:

return BinaryOperator::CreateLShr(Op1, BitWidth - ShiftAmt);

[nikic]

Convert check to assert, don't use builder.

[spatel]

LGTM - can you add at least one vector test when before committing, so we know that the constant creation is producing the correct types.

lib/Transforms/InstCombine/InstCombineCalls.cpp

2008–2009

Here and below - did that clang-format like that? Doesn't look like the normal indent.

[nikic]

I've added some vector tests before committing. Thanks for the reviews!

lib/Transforms/InstCombine/InstCombineCalls.cpp

2008–2009

You're right, I fixed this before commit. TIL about git clang-format.

lib/Transforms/InstCombine/InstCombineCalls.cpp

Instruction *InstCombiner::visitCallInst(CallInst &CI) {
 
   case Intrinsic::ctpop:
     if (auto *I = foldCtpop(*II, *this))
       return I;
     break;
 
   case Intrinsic::fshl:
   case Intrinsic::fshr: {
+    const APInt *SA;
+    if (match(II->getArgOperand(2), m_APInt(SA))) {
+      Value *Op0 = II->getArgOperand(0), *Op1 = II->getArgOperand(1);
+      unsigned BitWidth = SA->getBitWidth();
+      uint64_t ShiftAmt = SA->urem(BitWidth);
+      assert(ShiftAmt != 0 && "SimplifyCall should have handled zero shift");
+      // Normalize to funnel shift left.
+      if (II->getIntrinsicID() == Intrinsic::fshr)
+        ShiftAmt = BitWidth - ShiftAmt;
+
+      // fshl(X, 0, C) -> shl X, C
+      // fshl(X, undef, C) -> shl X, C
+      if (match(Op1, m_Zero()) || match(Op1, m_Undef()))
+        return BinaryOperator::CreateShl(Op0,
+          ConstantInt::get(II->getType(), ShiftAmt));
+
+      // fshl(0, X, C) -> lshr X, (BW-C)
+      // fshl(undef, X, C) -> lshr X, (BW-C)
+      if (match(Op0, m_Zero()) || match(Op0, m_Undef()))
+        return BinaryOperator::CreateLShr(Op1,
+          ConstantInt::get(II->getType(), BitWidth - ShiftAmt));
+    }
+
     // The shift amount (operand 2) of a funnel shift is modulo the bitwidth,
     // so only the low bits of the shift amount are demanded if the bitwidth is
     // a power-of-2.
     unsigned BitWidth = II->getType()->getScalarSizeInBits();
     if (!isPowerOf2_32(BitWidth))
       break;
     APInt Op2Demanded = APInt::getLowBitsSet(BitWidth, Log2_32_Ceil(BitWidth));
     KnownBits Op2Known(BitWidth);

test/Transforms/InstCombine/fsh.ll

;
   %r = call <2 x i31> @llvm.fshl.v2i31(<2 x i31> %x, <2 x i31> %y, <2 x i31> %bogusbits)
   ret <2 x i31> %r
 }
 
 ; Simplify one undef operand and constant shift amount.
 
 define i32 @fshl_op0_undef(i32 %x) {
 ; CHECK-LABEL: @fshl_op0_undef(
-; CHECK-NEXT:    [[R:%.*]] = call i32 @llvm.fshl.i32(i32 undef, i32 [[X:%.*]], i32 7)
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 25
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %r = call i32 @llvm.fshl.i32(i32 undef, i32 %x, i32 7)
   ret i32 %r
 }
 
 define i32 @fshl_op0_zero(i32 %x) {
 ; CHECK-LABEL: @fshl_op0_zero(
-; CHECK-NEXT:    [[R:%.*]] = call i32 @llvm.fshl.i32(i32 0, i32 [[X:%.*]], i32 7)
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 25
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %r = call i32 @llvm.fshl.i32(i32 0, i32 %x, i32 7)
   ret i32 %r
 }
 
 define i33 @fshr_op0_undef(i33 %x) {
 ; CHECK-LABEL: @fshr_op0_undef(
-; CHECK-NEXT:    [[R:%.*]] = call i33 @llvm.fshr.i33(i33 undef, i33 [[X:%.*]], i33 7)
-; CHECK-NEXT:    ret i33 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i33 [[X:%.*]], 7
+; CHECK-NEXT:    ret i33 [[TMP1]]
 ;
   %r = call i33 @llvm.fshr.i33(i33 undef, i33 %x, i33 7)
   ret i33 %r
 }
 
 define i33 @fshr_op0_zero(i33 %x) {
 ; CHECK-LABEL: @fshr_op0_zero(
-; CHECK-NEXT:    [[R:%.*]] = call i33 @llvm.fshr.i33(i33 0, i33 [[X:%.*]], i33 7)
-; CHECK-NEXT:    ret i33 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i33 [[X:%.*]], 7
+; CHECK-NEXT:    ret i33 [[TMP1]]
 ;
   %r = call i33 @llvm.fshr.i33(i33 0, i33 %x, i33 7)
   ret i33 %r
 }
 
 define i32 @fshl_op1_undef(i32 %x) {
 ; CHECK-LABEL: @fshl_op1_undef(
-; CHECK-NEXT:    [[R:%.*]] = call i32 @llvm.fshl.i32(i32 [[X:%.*]], i32 undef, i32 7)
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 7
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %r = call i32 @llvm.fshl.i32(i32 %x, i32 undef, i32 7)
   ret i32 %r
 }
 
 define i32 @fshl_op1_zero(i32 %x) {
 ; CHECK-LABEL: @fshl_op1_zero(
-; CHECK-NEXT:    [[R:%.*]] = call i32 @llvm.fshl.i32(i32 [[X:%.*]], i32 0, i32 7)
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 7
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %r = call i32 @llvm.fshl.i32(i32 %x, i32 0, i32 7)
   ret i32 %r
 }
 
 define i33 @fshr_op1_undef(i33 %x) {
 ; CHECK-LABEL: @fshr_op1_undef(
-; CHECK-NEXT:    [[R:%.*]] = call i33 @llvm.fshr.i33(i33 [[X:%.*]], i33 undef, i33 7)
-; CHECK-NEXT:    ret i33 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i33 [[X:%.*]], 26
+; CHECK-NEXT:    ret i33 [[TMP1]]
 ;
   %r = call i33 @llvm.fshr.i33(i33 %x, i33 undef, i33 7)
   ret i33 %r
 }
 
 define i33 @fshr_op1_zero(i33 %x) {
 ; CHECK-LABEL: @fshr_op1_zero(
-; CHECK-NEXT:    [[R:%.*]] = call i33 @llvm.fshr.i33(i33 [[X:%.*]], i33 0, i33 7)
-; CHECK-NEXT:    ret i33 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i33 [[X:%.*]], 26
+; CHECK-NEXT:    ret i33 [[TMP1]]
 ;
   %r = call i33 @llvm.fshr.i33(i33 %x, i33 0, i33 7)
   ret i33 %r
 }
 
 ; Only demand bits from one of the operands.
 
 define i32 @fshl_only_op0_demanded(i32 %x, i32 %y) {