[InstCombine] Prune fshl/fshr with masked operands

[shawnl]

Summary

Example:

fshl((A & 255), (B), BW - 8) -> shr(B, 8)

[shawnl]

There is a bug there.

[shawnl]

OK, ready for review

[nikic]

The idea here looks reasonable to me, but this doesn't seem like the right place to make the transform. This is ultimately a demanded bits problem and as such should be handled in either BDCE or InstCombineSimplifyDemanded.

lib/Transforms/InstCombine/InstCombineCalls.cpp

2090 ↗

(On Diff #195047)

You cannot assume that the ShAmtC is a ConstantInt here. It could also be a vector (something that should be covered in tests).

[nikic]

Actually all the necessary support is already in place here, all you need to do is call SimplifyDemandedInstructionBits():

if (SimplifyDemandedInstructionBits(*II))
    return &CI;

[shawnl]

use SimplifyDemandedInstructionBits

[lebedev.ri]

Please upload all patches with full context (-U99999)

lib/Transforms/InstCombine/InstCombineCalls.cpp

2087 ↗

(On Diff #195078)

This should probably be at the top level of whatever function this is.
Not sure where in the function though.

[nikic]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2087 ↗

(On Diff #195078)

It should probably be right below this block. We already have the demanded bits simplification for the shift amount there (which we should probably move into the fshl handling in InstCombineSimplifyDemanded as a followup).

[shawnl]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2087 ↗

(On Diff #195078)

I think it should go at the top of the match block here. This text is for the shift being a constant, and it can't be simplified unless the shift is a constant.

[shawnl]

move up

[shawnl]

keep tests

[lebedev.ri]

Please can you place the original tests in a *new* differential,
with check lines for llvm trunk, and then rebase this patch ontop of that patch,
so that test diff shows diff and not whole new tests being added.

lib/Transforms/InstCombine/InstCombineCalls.cpp

2100–2101 ↗

(On Diff #195083)

I think that new code should be here.

[shawnl]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2100–2101 ↗

(On Diff #195083)

but it has to be above this:

if (!isPowerOf2_32(BitWidth))

[shawnl]

base on top of D60688

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2100–2101 ↗

(On Diff #195083)

Good point, then place it just before that check :)

[shawnl]

move lower

[shawnl]

kill newline

[nikic]

LGTM

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2090–2091 ↗

(On Diff #195147)

Separate with newline

llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp

if (match(II->getArgOperand(2), m_Constant(ShAmtC)) &&
 
       // fshl(0, X, C) --> lshr X, (BW-C)
       // fshl(undef, X, C) --> lshr X, (BW-C)
       if (match(Op0, m_ZeroInt()) || match(Op0, m_Undef()))
         return BinaryOperator::CreateLShr(Op1,
                                           ConstantExpr::getSub(WidthC, ShAmtC));
     }
 
+    // Left or right might be masked.
+    if (SimplifyDemandedInstructionBits(*II))
+      return &CI;
+
     // 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.
     if (!isPowerOf2_32(BitWidth))
       break;
     APInt Op2Demanded = APInt::getLowBitsSet(BitWidth, Log2_32_Ceil(BitWidth));
     KnownBits Op2Known(BitWidth);
     if (SimplifyDemandedBits(II, 2, Op2Demanded, Op2Known))

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

 ; CHECK-NEXT:    ret i16 [[R]]
 ;
   %r = call i16 @llvm.fshr.i16(i16 %x, i16 %x, i16 8)
   ret i16 %r
 }
 
 define i32 @fshl_mask_args_same1(i32 %a) {
 ; CHECK-LABEL: @fshl_mask_args_same1(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -65536
-; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.fshl.i32(i32 [[TMP1]], i32 [[TMP1]], i32 16)
+; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[A:%.*]], 16
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %tmp1 = and i32 %a, 4294901760 ; 0xffff0000
   %tmp2 = call i32 @llvm.fshl.i32(i32 %tmp1, i32 %tmp1, i32 16)
   ret i32 %tmp2
 }
 
 define i32 @fshl_mask_args_same2(i32 %a) {
 ; CHECK-LABEL: @fshl_mask_args_same2(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], 255
-; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.fshl.i32(i32 [[TMP1]], i32 [[TMP1]], i32 8)
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[A:%.*]], 8
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 65280
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %tmp1 = and i32 %a, 255
   %tmp2 = call i32 @llvm.fshl.i32(i32 %tmp1, i32 %tmp1, i32 8)
   ret i32 %tmp2
 }
 
 define i32 @fshl_mask_args_same3(i32 %a) {
 ; CHECK-LABEL: @fshl_mask_args_same3(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], 255
-; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.fshl.i32(i32 [[TMP1]], i32 [[TMP1]], i32 24)
+; CHECK-NEXT:    [[TMP2:%.*]] = shl i32 [[A:%.*]], 24
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %tmp1 = and i32 %a, 255
   %tmp2 = call i32 @llvm.fshl.i32(i32 %tmp1, i32 %tmp1, i32 24)
   ret i32 %tmp2
 }
 
 define i32 @fshl_mask_args_different(i32 %a) {
 ; CHECK-LABEL: @fshl_mask_args_different(
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[A:%.*]], -65536
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A]], -16777216
-; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @llvm.fshl.i32(i32 [[TMP2]], i32 [[TMP1]], i32 17)
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[A:%.*]], 15
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP1]], 130560
 ; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
   %tmp2 = and i32 %a, 4294901760 ; 0xfffff00f
   %tmp1 = and i32 %a, 4278190080 ; 0xff00f00f
   %tmp3 = call i32 @llvm.fshl.i32(i32 %tmp2, i32 %tmp1, i32 17)
   ret i32 %tmp3
 }
 
 define <2 x i31> @fshr_mask_args_same_vector(<2 x i31> %a) {
 ; CHECK-LABEL: @fshr_mask_args_same_vector(
-; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i31> [[A:%.*]], <i31 1000, i31 1000>
-; CHECK-NEXT:    [[TMP3:%.*]] = call <2 x i31> @llvm.fshl.v2i31(<2 x i31> [[A]], <2 x i31> [[TMP1]], <2 x i31> <i31 10, i31 10>)
+; CHECK-NEXT:    [[TMP3:%.*]] = shl <2 x i31> [[A:%.*]], <i31 10, i31 10>
 ; CHECK-NEXT:    ret <2 x i31> [[TMP3]]
 ;
   %tmp1 = and <2 x i31> %a, <i31 1000, i31 1000>
   %tmp2 = and <2 x i31> %a, <i31 6442450943, i31 6442450943>
   %tmp3 = call <2 x i31> @llvm.fshl.v2i31(<2 x i31> %tmp2, <2 x i31> %tmp1, <2 x i31> <i31 10, i31 10>)
   ret <2 x i31> %tmp3
 }
 
 define <2 x i32> @fshr_mask_args_same_vector2(<2 x i32> %a, <2 x i32> %b) {
 ; CHECK-LABEL: @fshr_mask_args_same_vector2(
 ; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[A:%.*]], <i32 1000000, i32 100000>
-; CHECK-NEXT:    [[TMP3:%.*]] = call <2 x i32> @llvm.fshl.v2i32(<2 x i32> [[TMP1]], <2 x i32> [[TMP1]], <2 x i32> <i32 29, i32 29>)
+; CHECK-NEXT:    [[TMP3:%.*]] = lshr exact <2 x i32> [[TMP1]], <i32 3, i32 3>
 ; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
 ;
   %tmp1 = and <2 x i32> %a, <i32 1000000, i32 100000>
   %tmp2 = and <2 x i32> %a, <i32 6442450943, i32 6442450943>
   %tmp3 = call <2 x i32> @llvm.fshr.v2i32(<2 x i32> %tmp1, <2 x i32> %tmp1, <2 x i32> <i32 3, i32 3>)
   ret <2 x i32> %tmp3
 }