[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

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

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

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

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

2110–2111

I think that new code should be here.

[shawnl]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2110–2111

but it has to be above this:

if (!isPowerOf2_32(BitWidth))

[shawnl]

base on top of D60688

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2110–2111

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

Separate with newline

lib/Transforms/InstCombine/InstCombineCalls.cpp

if (match(II->getArgOperand(2), m_Constant(ShAmtC)) &&
       if (match(Op1, m_ZeroInt()) || match(Op1, m_Undef()))
         return BinaryOperator::CreateShl(Op0, 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));
+
+      // try fshl((A & B), (C & D), E) -> lshr/shl
+      Value *A, *C;
+      const APInt *B, *D;
+      if (match(II->getArgOperand(0), m_c_And(m_Value(A), m_APInt(B))) &&
+          match(II->getArgOperand(1), m_c_And(m_Value(C), m_APInt(D))) &&
+          A == C) {
+        APInt BAndD = (*B & *D), E = dyn_cast<ConstantInt>(ShAmtC)->getValue();
+        if (BAndD.countLeadingZeros() >= E.getLimitedValue())
+          return BinaryOperator::CreateShl(Op0, ShAmtC);
+        if (BAndD.countTrailingZeros() >= BitWidth - E.getLimitedValue())
+          return BinaryOperator::CreateLShr(
+            Op1, ConstantInt::get(II->getContext(), APInt(BitWidth, BitWidth) - E));
+      }
     }
 
     // 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))
       return &CI;
     break;
   }
   case Intrinsic::uadd_with_overflow:
   case Intrinsic::sadd_with_overflow: {
     if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))
       return I;
     if (Instruction *I = foldIntrinsicWithOverflowCommon(II))
       return I;
 

test/Transforms/InstCombine/fsh.ll

 define i16 @fshr_bswap(i16 %x) {
 ; CHECK-LABEL: @fshr_bswap(
 ; CHECK-NEXT:    [[R:%.*]] = call i16 @llvm.fshl.i16(i16 [[X:%.*]], i16 [[X]], i16 8)
 ; 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:    [[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:%.*]] = 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_same_3(i32 %a) {
+; CHECK-LABEL: @fshl_mask_args_same_3(
+; 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_same4(i32 %a) {
+; CHECK-LABEL: @fshl_mask_args_same4(
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[A:%.*]], 8
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 16711680
+; CHECK-NEXT:    ret i32 [[TMP2]]
+;
+  %tmp1 = and i32 %a, 4278190080 ; 0xff000000
+  %tmp2 = call i32 @llvm.fshl.i32(i32 %tmp1, i32 %tmp1, i32 24)
+  ret i32 %tmp2
+}