[InstCombine] fold funnel shift amount based on demanded bits

[spatel]

Summary

The shift amount of a funnel shift is modulo the scalar bitwidth:
http://llvm.org/docs/LangRef.html#llvm-fshl-intrinsic
...so we can use demanded bits analysis on that operand to simplify it.

This is another step towards canonicalizing {shift/shift/or} to the intrinsic in IR.

[fabiang]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1998

Need to check whether BitWidth is a power of 2 here, this is incorrect for non-pow2. Take the BitWidth=33 case in the tests below.

A mod-33 funnel shift by say 65 should shift by 65-33=32 not 65 % 64 = 1.

test/Transforms/InstCombine/fsh.ll

48

Can't eliminate the AND here, the reduction mod 64 doesn't interact with the mod-33 funnel shift amount in a useful way. (That I can see.)

61

Same here.

[spatel]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1998

Oops, yes. Will fix here and the test comments.

[spatel]

Patch updated:
Fix the logic - for non-power-of-2 bitwidths, all bets are off.

[fabiang]

This one looks good!

[spatel]

In D54478#1297324, @fabiang wrote:

This one looks good!

Thank you for catching the logic bug...I think that's the 2nd time I fell on that!

lib/Transforms/InstCombine/InstCombineCalls.cpp

if (auto *I = foldCttzCtlz(*II, *this))
       return I;
     break;
 
   case Intrinsic::ctpop:
     if (auto *I = foldCtpop(*II, *this))
       return I;
     break;
 
+  case Intrinsic::fshl:
+  case Intrinsic::fshr: {
+    // 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);
+    if (SimplifyDemandedBits(II, 2, Op2Demanded, Op2Known))
+      return &CI;
+    break;
+  }
   case Intrinsic::uadd_with_overflow:
   case Intrinsic::sadd_with_overflow:
   case Intrinsic::umul_with_overflow:
   case Intrinsic::smul_with_overflow:
     if (isa<Constant>(II->getArgOperand(0)) &&
         !isa<Constant>(II->getArgOperand(1))) {
       // Canonicalize constants into the RHS.
       Value *LHS = II->getArgOperand(0);

test/Transforms/InstCombine/fsh.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 declare i32 @llvm.fshl.i32(i32, i32, i32)
 declare i33 @llvm.fshr.i33(i33, i33, i33)
 declare <2 x i32> @llvm.fshr.v2i32(<2 x i32>, <2 x i32>, <2 x i32>)
 declare <2 x i31> @llvm.fshl.v2i31(<2 x i31>, <2 x i31>, <2 x i31>)
 
 ; If the shift mask doesn't include any demanded bits, the funnel shift can be eliminated.
 
 define i32 @fshl_mask_simplify1(i32 %x, i32 %y, i32 %sh) {
 ; CHECK-LABEL: @fshl_mask_simplify1(
-; CHECK-NEXT:    [[MASKEDSH:%.*]] = and i32 [[SH:%.*]], 32
-; CHECK-NEXT:    [[R:%.*]] = call i32 @llvm.fshl.i32(i32 [[X:%.*]], i32 [[Y:%.*]], i32 [[MASKEDSH]])
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
   %maskedsh = and i32 %sh, 32
   %r = call i32 @llvm.fshl.i32(i32 %x, i32 %y, i32 %maskedsh)
   ret i32 %r
 }
 
 define <2 x i32> @fshr_mask_simplify2(<2 x i32> %x, <2 x i32> %y, <2 x i32> %sh) {
 ; CHECK-LABEL: @fshr_mask_simplify2(
-; CHECK-NEXT:    [[MASKEDSH:%.*]] = and <2 x i32> [[SH:%.*]], <i32 64, i32 64>
-; CHECK-NEXT:    [[R:%.*]] = call <2 x i32> @llvm.fshr.v2i32(<2 x i32> [[X:%.*]], <2 x i32> [[Y:%.*]], <2 x i32> [[MASKEDSH]])
-; CHECK-NEXT:    ret <2 x i32> [[R]]
+; CHECK-NEXT:    ret <2 x i32> [[Y:%.*]]
 ;
   %maskedsh = and <2 x i32> %sh, <i32 64, i32 64>
   %r = call <2 x i32> @llvm.fshr.v2i32(<2 x i32> %x, <2 x i32> %y, <2 x i32> %maskedsh)
   ret <2 x i32> %r
 }
 
 ; Negative test.
 
 define i32 @fshl_mask_simplify3(i32 %x, i32 %y, i32 %sh) {
 ; CHECK-LABEL: @fshl_mask_simplify3(
 ; CHECK-NEXT:    [[MASKEDSH:%.*]] = and i32 [[SH:%.*]], 16
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @llvm.fshl.i32(i32 [[X:%.*]], i32 [[Y:%.*]], i32 [[MASKEDSH]])
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %maskedsh = and i32 %sh, 16
   %r = call i32 @llvm.fshl.i32(i32 %x, i32 %y, i32 %maskedsh)
   ret i32 %r
 }
 
-; Check again with weird bitwidths; log2(33) means we demand the low 6 bits.
+; Check again with weird bitwidths - the analysis is invalid with non-power-of-2.
 
 define i33 @fshr_mask_simplify1(i33 %x, i33 %y, i33 %sh) {
 ; CHECK-LABEL: @fshr_mask_simplify1(
 ; CHECK-NEXT:    [[MASKEDSH:%.*]] = and i33 [[SH:%.*]], 64
 ; CHECK-NEXT:    [[R:%.*]] = call i33 @llvm.fshr.i33(i33 [[X:%.*]], i33 [[Y:%.*]], i33 [[MASKEDSH]])
 ; CHECK-NEXT:    ret i33 [[R]]
 ;
   %maskedsh = and i33 %sh, 64
   %r = call i33 @llvm.fshr.i33(i33 %x, i33 %y, i33 %maskedsh)
   ret i33 %r
 }
 
-; Check again with weird bitwidths; log2(31) means we demand the low 5 bits.
+; Check again with weird bitwidths - the analysis is invalid with non-power-of-2.
 
 define <2 x i31> @fshl_mask_simplify2(<2 x i31> %x, <2 x i31> %y, <2 x i31> %sh) {
 ; CHECK-LABEL: @fshl_mask_simplify2(
 ; CHECK-NEXT:    [[MASKEDSH:%.*]] = and <2 x i31> [[SH:%.*]], <i31 32, i31 32>
 ; CHECK-NEXT:    [[R:%.*]] = call <2 x i31> @llvm.fshl.v2i31(<2 x i31> [[X:%.*]], <2 x i31> [[Y:%.*]], <2 x i31> [[MASKEDSH]])
 ; CHECK-NEXT:    ret <2 x i31> [[R]]
 ;
   %maskedsh = and <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> %maskedsh)
   ret <2 x i31> %r
 }
 
-; Negative test.
+; Check again with weird bitwidths - the analysis is invalid with non-power-of-2.
 
 define i33 @fshr_mask_simplify3(i33 %x, i33 %y, i33 %sh) {
 ; CHECK-LABEL: @fshr_mask_simplify3(
 ; CHECK-NEXT:    [[MASKEDSH:%.*]] = and i33 [[SH:%.*]], 32
 ; CHECK-NEXT:    [[R:%.*]] = call i33 @llvm.fshr.i33(i33 [[X:%.*]], i33 [[Y:%.*]], i33 [[MASKEDSH]])
 ; CHECK-NEXT:    ret i33 [[R]]
 ;
   %maskedsh = and i33 %sh, 32
   %r = call i33 @llvm.fshr.i33(i33 %x, i33 %y, i33 %maskedsh)
   ret i33 %r
 }
 
 ; This mask op is unnecessary.
 
 define i32 @fshl_mask_not_required(i32 %x, i32 %y, i32 %sh) {
 ; CHECK-LABEL: @fshl_mask_not_required(
-; CHECK-NEXT:    [[MASKEDSH:%.*]] = and i32 [[SH:%.*]], 31
-; CHECK-NEXT:    [[R:%.*]] = call i32 @llvm.fshl.i32(i32 [[X:%.*]], i32 [[Y:%.*]], i32 [[MASKEDSH]])
+; CHECK-NEXT:    [[R:%.*]] = call i32 @llvm.fshl.i32(i32 [[X:%.*]], i32 [[Y:%.*]], i32 [[SH:%.*]])
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %maskedsh = and i32 %sh, 31
   %r = call i32 @llvm.fshl.i32(i32 %x, i32 %y, i32 %maskedsh)
   ret i32 %r
 }
 
 ; This mask op can be reduced.
 
 define i32 @fshl_mask_reduce_constant(i32 %x, i32 %y, i32 %sh) {
 ; CHECK-LABEL: @fshl_mask_reduce_constant(
-; CHECK-NEXT:    [[MASKEDSH:%.*]] = and i32 [[SH:%.*]], 33
+; CHECK-NEXT:    [[MASKEDSH:%.*]] = and i32 [[SH:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @llvm.fshl.i32(i32 [[X:%.*]], i32 [[Y:%.*]], i32 [[MASKEDSH]])
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %maskedsh = and i32 %sh, 33
   %r = call i32 @llvm.fshl.i32(i32 %x, i32 %y, i32 %maskedsh)
   ret i32 %r
 }
 
;
   %r = call i32 @llvm.fshl.i32(i32 %x, i32 %y, i32 %maskedsh)
   ret i32 %r
 }
 
 ; The transform is not limited to mask ops.
 
 define <2 x i32> @fshr_set_but_not_demanded_vec(<2 x i32> %x, <2 x i32> %y, <2 x i32> %sh) {
 ; CHECK-LABEL: @fshr_set_but_not_demanded_vec(
-; CHECK-NEXT:    [[BOGUSBITS:%.*]] = or <2 x i32> [[SH:%.*]], <i32 32, i32 32>
-; CHECK-NEXT:    [[R:%.*]] = call <2 x i32> @llvm.fshr.v2i32(<2 x i32> [[X:%.*]], <2 x i32> [[Y:%.*]], <2 x i32> [[BOGUSBITS]])
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i32> @llvm.fshr.v2i32(<2 x i32> [[X:%.*]], <2 x i32> [[Y:%.*]], <2 x i32> [[SH:%.*]])
 ; CHECK-NEXT:    ret <2 x i32> [[R]]
 ;
   %bogusbits = or <2 x i32> %sh, <i32 32, i32 32>
   %r = call <2 x i32> @llvm.fshr.v2i32(<2 x i32> %x, <2 x i32> %y, <2 x i32> %bogusbits)
   ret <2 x i32> %r
 }
 
+; Check again with weird bitwidths - the analysis is invalid with non-power-of-2.
+
 define <2 x i31> @fshl_set_but_not_demanded_vec(<2 x i31> %x, <2 x i31> %y, <2 x i31> %sh) {
 ; CHECK-LABEL: @fshl_set_but_not_demanded_vec(
 ; CHECK-NEXT:    [[BOGUSBITS:%.*]] = or <2 x i31> [[SH:%.*]], <i31 32, i31 32>
 ; 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
 }