[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 ↗

(On Diff #174978)

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 ↗

(On Diff #174978)

The convention is to use something like:

return BinaryOperator::CreateShl(Op0, ShiftAmt);

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

2014–2015 ↗

(On Diff #174978)

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 ↗

(On Diff #175070)

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 ↗

(On Diff #175070)

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

llvm/trunk/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);

llvm/trunk/test/Transforms/InstCombine/fsh.ll

 ; CHECK-NEXT:    [[R:%.*]] = call <2 x i31> @llvm.fshl.v2i31(<2 x i31> [[X:%.*]], <2 x i31> [[Y:%.*]], <2 x i31> [[BOGUSBITS]])
 ; CHECK-NEXT:    ret <2 x i31> [[R]]
 ;
   %bogusbits = or <2 x i31> %sh, <i31 32, i31 32>
   %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.
+; Simplify one undef or zero 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:    [[R:%.*]] = lshr i32 [[X:%.*]], 25
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %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:    [[R:%.*]] = lshr i32 [[X:%.*]], 25
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %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:    [[R:%.*]] = lshr i33 [[X:%.*]], 7
 ; CHECK-NEXT:    ret i33 [[R]]
 ;
   %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:    [[R:%.*]] = lshr i33 [[X:%.*]], 7
 ; CHECK-NEXT:    ret i33 [[R]]
 ;
   %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:    [[R:%.*]] = shl i32 [[X:%.*]], 7
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %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:    [[R:%.*]] = shl i32 [[X:%.*]], 7
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %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:    [[R:%.*]] = shl i33 [[X:%.*]], 26
 ; CHECK-NEXT:    ret i33 [[R]]
 ;
   %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:    [[R:%.*]] = shl i33 [[X:%.*]], 26
 ; CHECK-NEXT:    ret i33 [[R]]
 ;
   %r = call i33 @llvm.fshr.i33(i33 %x, i33 0, i33 7)
   ret i33 %r
 }
 
+define <2 x i31> @fshl_op0_zero_vec(<2 x i31> %x) {
+; CHECK-LABEL: @fshl_op0_zero_vec(
+; CHECK-NEXT:    [[R:%.*]] = lshr <2 x i31> [[X:%.*]], <i31 24, i31 24>
+; CHECK-NEXT:    ret <2 x i31> [[R]]
+;
+  %r = call <2 x i31> @llvm.fshl.v2i31(<2 x i31> zeroinitializer, <2 x i31> %x, <2 x i31> <i31 7, i31 7>)
+  ret <2 x i31> %r
+}
+
+define <2 x i31> @fshl_op1_undef_vec(<2 x i31> %x) {
+; CHECK-LABEL: @fshl_op1_undef_vec(
+; CHECK-NEXT:    [[R:%.*]] = shl <2 x i31> [[X:%.*]], <i31 7, i31 7>
+; CHECK-NEXT:    ret <2 x i31> [[R]]
+;
+  %r = call <2 x i31> @llvm.fshl.v2i31(<2 x i31> %x, <2 x i31> undef, <2 x i31> <i31 7, i31 7>)
+  ret <2 x i31> %r
+}
+
+define <2 x i32> @fshr_op0_undef_vec(<2 x i32> %x) {
+; CHECK-LABEL: @fshr_op0_undef_vec(
+; CHECK-NEXT:    [[R:%.*]] = lshr <2 x i32> [[X:%.*]], <i32 7, i32 7>
+; CHECK-NEXT:    ret <2 x i32> [[R]]
+;
+  %r = call <2 x i32> @llvm.fshr.v2i32(<2 x i32> undef, <2 x i32> %x, <2 x i32> <i32 7, i32 7>)
+  ret <2 x i32> %r
+}
+
+define <2 x i32> @fshr_op1_zero_vec(<2 x i32> %x) {
+; CHECK-LABEL: @fshr_op1_zero_vec(
+; CHECK-NEXT:    [[R:%.*]] = shl <2 x i32> [[X:%.*]], <i32 25, i32 25>
+; CHECK-NEXT:    ret <2 x i32> [[R]]
+;
+  %r = call <2 x i32> @llvm.fshr.v2i32(<2 x i32> %x, <2 x i32> zeroinitializer, <2 x i32> <i32 7, i32 7>)
+  ret <2 x i32> %r
+}
+
 ; Only demand bits from one of the operands.
 
 define i32 @fshl_only_op0_demanded(i32 %x, i32 %y) {
 ; CHECK-LABEL: @fshl_only_op0_demanded(
 ; CHECK-NEXT:    [[Z:%.*]] = call i32 @llvm.fshl.i32(i32 [[X:%.*]], i32 [[Y:%.*]], i32 7)
 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[Z]], 128
 ; CHECK-NEXT:    ret i32 [[R]]
 ;