[InstCombine] matchRotate - support (uniform) constant rotation amounts (PR46895)

[RKSimon]

Summary

This patch adds handling of rotation patterns with constant shift amounts - the next bit will be how we want to support non-uniform constant vectors.

[RKSimon]

any comments on this?

[RKSimon]

fix clang-tidy warnings

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2115

Probably need to either guard or assert against invalid shift amounts here. Don't want to combine -33 and +1.

llvm/lib/Transforms/Utils/Local.cpp

2910 ↗

(On Diff #291597)

mount -> amount

2922 ↗

(On Diff #291597)

Don't we need to check that the fsh operands are the same, or at least LHS->Provider and RHS->Provider are?

2924 ↗

(On Diff #291597)

I suspect this is inverted, but maybe I misunderstand the direction of the mapping. It would be good to at least add some tests where the fsh amount is not exactly half the bitwidth.

Result = fshl(LHS, RHS, 1)
Result[0] = RHS[31]
Result[1] = LHS[0]
...
Result[31] = LHS[30]

[RKSimon]

Fix the -ve shift amount issue - still looking at better testing of fshl/fshr inside collectBitParts

[RKSimon]

@nikic I've pulled (and fixed) the Local.cpp changes out to D88292 for review first.

[RKSimon]

rebase now that D88292 has landed

[nikic]

LGTM

[nikic]

There's a 40% code size increase on CMakeFiles/7zip-benchmark.dir/CPP/7zip/Crypto/Sha1.cpp.o, might be worth double checking that we're not missing some optimizations on funnel shifts.

[RKSimon]

In D87452#2295999, @nikic wrote:

There's a 40% code size increase on CMakeFiles/7zip-benchmark.dir/CPP/7zip/Crypto/Sha1.cpp.o, might be worth double checking that we're not missing some optimizations on funnel shifts.

Looking at this now: https://wide.godbolt.org/z/h9GoTo

[RKSimon]

In D87452#2296369, @RKSimon wrote:

In D87452#2295999, @nikic wrote:

There's a 40% code size increase on CMakeFiles/7zip-benchmark.dir/CPP/7zip/Crypto/Sha1.cpp.o, might be worth double checking that we're not missing some optimizations on funnel shifts.

Looking at this now: https://wide.godbolt.org/z/h9GoTo

I think I've worked out whats happened - we've replaced a 3 x instruction pattern (which was later matched to a single rotate instruction in the DAG) with 1 intrinsic (which matched to the same single rotate instruction) - which seems to have allowed a couple of core loops to be unrolled further/completely - leading to the code size increase.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombinerImpl::matchBSwap(BinaryOperator &Or) {
   return LastInst;
 }
 
 /// Transform UB-safe variants of bitwise rotate to the funnel shift intrinsic.
 static Instruction *matchRotate(Instruction &Or) {
   // TODO: Can we reduce the code duplication between this and the related
   // rotate matching code under visitSelect and visitTrunc?
   unsigned Width = Or.getType()->getScalarSizeInBits();
-  if (!isPowerOf2_32(Width))
-    return nullptr;
 
   // First, find an or'd pair of opposite shifts with the same shifted operand:
   // or (lshr ShVal, ShAmt0), (shl ShVal, ShAmt1)
   BinaryOperator *Or0, *Or1;
   if (!match(Or.getOperand(0), m_BinOp(Or0)) ||
       !match(Or.getOperand(1), m_BinOp(Or1)))
     return nullptr;
 
   Value *ShVal, *ShAmt0, *ShAmt1;
   if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal), m_Value(ShAmt0)))) ||
       !match(Or1, m_OneUse(m_LogicalShift(m_Specific(ShVal), m_Value(ShAmt1)))))
     return nullptr;
 
   BinaryOperator::BinaryOps ShiftOpcode0 = Or0->getOpcode();
   BinaryOperator::BinaryOps ShiftOpcode1 = Or1->getOpcode();
   if (ShiftOpcode0 == ShiftOpcode1)
     return nullptr;
 
   // Match the shift amount operands for a rotate pattern. This always matches
   // a subtraction on the R operand.
   auto matchShiftAmount = [](Value *L, Value *R, unsigned Width) -> Value * {
+    // Check for constant shift amounts that sum to the bitwidth.
+    // TODO: Support non-uniform shift amounts.
+    const APInt *LC, *RC;
+    if (match(L, m_APInt(LC)) && match(R, m_APInt(RC)))
+      if (LC->ult(Width) && RC->ult(Width) && (*LC + *RC) == Width)
+        return L;
+
+    // For non-constant cases we don't support non-pow2 shift masks.
+    // TODO: Is it worth matching urem as well?
+    if (!isPowerOf2_32(Width))
+      return nullptr;
+
     // The shift amount may be masked with negation:
     // (shl ShVal, (X & (Width - 1))) | (lshr ShVal, ((-X) & (Width - 1)))
     Value *X;
     unsigned Mask = Width - 1;
     if (match(L, m_And(m_Value(X), m_SpecificInt(Mask))) &&
         match(R, m_And(m_Neg(m_Specific(X)), m_SpecificInt(Mask))))
       return X;
 

llvm/test/Transforms/InstCombine/bswap.ll

 }
 
 ; Extra use should not prevent matching to bswap.
 ; swaphalf = (x << 16 | x >> 16)
 ; ((swaphalf & 0x00ff00ff) << 8) | ((swaphalf >> 8) & 0x00ff00ff)
 
 define i32 @bswap32_and_first_extra_use(i32 %x) {
 ; CHECK-LABEL: @bswap32_and_first_extra_use(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], 16
-; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 [[X]], 16
-; CHECK-NEXT:    [[SWAPHALF:%.*]] = or i32 [[SHL]], [[SHR]]
+; CHECK-NEXT:    [[SWAPHALF:%.*]] = call i32 @llvm.fshl.i32(i32 [[X:%.*]], i32 [[X]], i32 16)
 ; CHECK-NEXT:    [[T:%.*]] = and i32 [[SWAPHALF]], 16711935
 ; CHECK-NEXT:    [[BSWAP:%.*]] = call i32 @llvm.bswap.i32(i32 [[X]])
 ; CHECK-NEXT:    call void @extra_use(i32 [[T]])
 ; CHECK-NEXT:    ret i32 [[BSWAP]]
 ;
   %shl = shl i32 %x, 16
   %shr = lshr i32 %x, 16
   %swaphalf = or i32 %shl, %shr

 }
 
 ; Extra use should not prevent matching to bswap.
 ; swaphalf = (x << 16 | x >> 16)
 ; ((swaphalf << 8) & 0xff00ff00) | ((swaphalf >> 8) & 0x00ff00ff)
 
 define i32 @bswap32_shl_first_extra_use(i32 %x) {
 ; CHECK-LABEL: @bswap32_shl_first_extra_use(
-; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 [[X:%.*]], 16
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X]], 24
-; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[SHR]], 8
-; CHECK-NEXT:    [[T:%.*]] = or i32 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[SWAPHALF:%.*]] = call i32 @llvm.fshl.i32(i32 [[X:%.*]], i32 [[X]], i32 16)
+; CHECK-NEXT:    [[T:%.*]] = shl i32 [[SWAPHALF]], 8
 ; CHECK-NEXT:    [[BSWAP:%.*]] = call i32 @llvm.bswap.i32(i32 [[X]])
 ; CHECK-NEXT:    call void @extra_use(i32 [[T]])
 ; CHECK-NEXT:    ret i32 [[BSWAP]]
 ;
   %shl = shl i32 %x, 16
   %shr = lshr i32 %x, 16
   %swaphalf = or i32 %shl, %shr
   %t = shl i32 %swaphalf, 8

llvm/test/Transforms/InstCombine/fsh.ll

;
   ret i33 %e
 }
 
 ; This demonstrates the same simplification working if the fshr intrinsic
 ; is expanded into shifts and or.
 
 define i33 @expanded_fshr_multi_use(i33 %a) {
 ; CHECK-LABEL: @expanded_fshr_multi_use(
-; CHECK-NEXT:    [[TMP:%.*]] = lshr i33 [[A:%.*]], 1
-; CHECK-NEXT:    [[C:%.*]] = lshr i33 [[A]], 24
-; CHECK-NEXT:    [[D:%.*]] = xor i33 [[C]], [[TMP]]
+; CHECK-NEXT:    [[B:%.*]] = call i33 @llvm.fshl.i33(i33 [[A:%.*]], i33 [[A]], i33 32)
+; CHECK-NEXT:    [[C:%.*]] = lshr i33 [[B]], 23
+; CHECK-NEXT:    [[D:%.*]] = xor i33 [[C]], [[B]]
 ; CHECK-NEXT:    [[E:%.*]] = and i33 [[D]], 31
 ; CHECK-NEXT:    ret i33 [[E]]
 ;
   %tmp = lshr i33 %a, 1
   %tmp2 = shl i33 %a, 32
   %b = or i33 %tmp, %tmp2
   %c = lshr i33 %b, 23
   %d = xor i33 %c, %b

llvm/test/Transforms/InstCombine/or-concat.ll

;
   %7 = zext <2 x i32> %5 to <2 x i64>
   %8 = shl nuw <2 x i64> %7, <i64 32, i64 32>
   %9 = or <2 x i64> %6, %8
   ret <2 x i64> %9
 }
 
 define i64 @concat_bswap32_unary_flip(i64 %a0) {
 ; CHECK-LABEL: @concat_bswap32_unary_flip(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[A0:%.*]], 32
-; CHECK-NEXT:    [[TMP2:%.*]] = shl i64 [[A0]], 32
-; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    [[TMP4:%.*]] = call i64 @llvm.bswap.i64(i64 [[TMP3]])
-; CHECK-NEXT:    ret i64 [[TMP4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @llvm.fshl.i64(i64 [[A0:%.*]], i64 [[A0]], i64 32)
+; CHECK-NEXT:    [[TMP2:%.*]] = call i64 @llvm.bswap.i64(i64 [[TMP1]])
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
   %1 = lshr i64 %a0, 32
   %2 = trunc i64 %1 to i32
   %3 = trunc i64 %a0 to i32
   %4 = tail call i32 @llvm.bswap.i32(i32 %2)
   %5 = tail call i32 @llvm.bswap.i32(i32 %3)
   %6 = zext i32 %4 to i64
   %7 = zext i32 %5 to i64
   %8 = shl nuw i64 %6, 32
   %9 = or i64 %7, %8
   ret i64 %9
 }
 
 define <2 x i64> @concat_bswap32_unary_flip_vector(<2 x i64> %a0) {
 ; CHECK-LABEL: @concat_bswap32_unary_flip_vector(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i64> [[A0:%.*]], <i64 32, i64 32>
-; CHECK-NEXT:    [[TMP2:%.*]] = shl <2 x i64> [[A0]], <i64 32, i64 32>
-; CHECK-NEXT:    [[TMP3:%.*]] = or <2 x i64> [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    [[TMP4:%.*]] = call <2 x i64> @llvm.bswap.v2i64(<2 x i64> [[TMP3]])
-; CHECK-NEXT:    ret <2 x i64> [[TMP4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i64> @llvm.fshl.v2i64(<2 x i64> [[A0:%.*]], <2 x i64> [[A0]], <2 x i64> <i64 32, i64 32>)
+; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i64> @llvm.bswap.v2i64(<2 x i64> [[TMP1]])
+; CHECK-NEXT:    ret <2 x i64> [[TMP2]]
 ;
   %1 = lshr <2 x i64> %a0, <i64 32, i64 32>
   %2 = trunc <2 x i64> %1 to <2 x i32>
   %3 = trunc <2 x i64> %a0 to <2 x i32>
   %4 = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> %2)
   %5 = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> %3)
   %6 = zext <2 x i32> %4 to <2 x i64>
   %7 = zext <2 x i32> %5 to <2 x i64>
;
   %7 = zext <2 x i32> %5 to <2 x i64>
   %8 = shl nuw <2 x i64> %7, <i64 32, i64 32>
   %9 = or <2 x i64> %6, %8
   ret <2 x i64> %9
 }
 
 define i64 @concat_bitreverse32_unary_flip(i64 %a0) {
 ; CHECK-LABEL: @concat_bitreverse32_unary_flip(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[A0:%.*]], 32
-; CHECK-NEXT:    [[TMP2:%.*]] = shl i64 [[A0]], 32
-; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    [[TMP4:%.*]] = call i64 @llvm.bitreverse.i64(i64 [[TMP3]])
-; CHECK-NEXT:    ret i64 [[TMP4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @llvm.fshl.i64(i64 [[A0:%.*]], i64 [[A0]], i64 32)
+; CHECK-NEXT:    [[TMP2:%.*]] = call i64 @llvm.bitreverse.i64(i64 [[TMP1]])
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
   %1 = lshr i64 %a0, 32
   %2 = trunc i64 %1 to i32
   %3 = trunc i64 %a0 to i32
   %4 = tail call i32 @llvm.bitreverse.i32(i32 %2)
   %5 = tail call i32 @llvm.bitreverse.i32(i32 %3)
   %6 = zext i32 %4 to i64
   %7 = zext i32 %5 to i64
   %8 = shl nuw i64 %6, 32
   %9 = or i64 %7, %8
   ret i64 %9
 }
 
 define <2 x i64> @concat_bitreverse32_unary_flip_vector(<2 x i64> %a0) {
 ; CHECK-LABEL: @concat_bitreverse32_unary_flip_vector(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i64> [[A0:%.*]], <i64 32, i64 32>
-; CHECK-NEXT:    [[TMP2:%.*]] = shl <2 x i64> [[A0]], <i64 32, i64 32>
-; CHECK-NEXT:    [[TMP3:%.*]] = or <2 x i64> [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    [[TMP4:%.*]] = call <2 x i64> @llvm.bitreverse.v2i64(<2 x i64> [[TMP3]])
-; CHECK-NEXT:    ret <2 x i64> [[TMP4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i64> @llvm.fshl.v2i64(<2 x i64> [[A0:%.*]], <2 x i64> [[A0]], <2 x i64> <i64 32, i64 32>)
+; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i64> @llvm.bitreverse.v2i64(<2 x i64> [[TMP1]])
+; CHECK-NEXT:    ret <2 x i64> [[TMP2]]
 ;
   %1 = lshr <2 x i64> %a0, <i64 32, i64 32>
   %2 = trunc <2 x i64> %1 to <2 x i32>
   %3 = trunc <2 x i64> %a0 to <2 x i32>
   %4 = tail call <2 x i32> @llvm.bitreverse.v2i32(<2 x i32> %2)
   %5 = tail call <2 x i32> @llvm.bitreverse.v2i32(<2 x i32> %3)
   %6 = zext <2 x i32> %4 to <2 x i64>
   %7 = zext <2 x i32> %5 to <2 x i64>

llvm/test/Transforms/InstCombine/rotate.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
 
-; TODO: Canonicalize rotate by constant to funnel shift intrinsics.
+; Canonicalize rotate by constant to funnel shift intrinsics.
 ; This should help cost modeling for vectorization, inlining, etc.
 ; If a target does not have a rotate instruction, the expansion will
 ; be exactly these same 3 basic ops (shl/lshr/or).
 
 define i32 @rotl_i32_constant(i32 %x) {
 ; CHECK-LABEL: @rotl_i32_constant(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], 11
-; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 [[X]], 21
-; CHECK-NEXT:    [[R:%.*]] = or i32 [[SHR]], [[SHL]]
+; CHECK-NEXT:    [[R:%.*]] = call i32 @llvm.fshl.i32(i32 [[X:%.*]], i32 [[X]], i32 11)
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %shl = shl i32 %x, 11
   %shr = lshr i32 %x, 21
   %r = or i32 %shr, %shl
   ret i32 %r
 }
 
 define i42 @rotr_i42_constant(i42 %x) {
 ; CHECK-LABEL: @rotr_i42_constant(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i42 [[X:%.*]], 31
-; CHECK-NEXT:    [[SHR:%.*]] = lshr i42 [[X]], 11
-; CHECK-NEXT:    [[R:%.*]] = or i42 [[SHR]], [[SHL]]
+; CHECK-NEXT:    [[R:%.*]] = call i42 @llvm.fshl.i42(i42 [[X:%.*]], i42 [[X]], i42 31)
 ; CHECK-NEXT:    ret i42 [[R]]
 ;
   %shl = shl i42 %x, 31
   %shr = lshr i42 %x, 11
   %r = or i42 %shr, %shl
   ret i42 %r
 }
 
 define i8 @rotr_i8_constant_commute(i8 %x) {
 ; CHECK-LABEL: @rotr_i8_constant_commute(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[SHR:%.*]] = lshr i8 [[X]], 3
-; CHECK-NEXT:    [[R:%.*]] = or i8 [[SHL]], [[SHR]]
+; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.fshl.i8(i8 [[X:%.*]], i8 [[X]], i8 5)
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %shl = shl i8 %x, 5
   %shr = lshr i8 %x, 3
   %r = or i8 %shl, %shr
   ret i8 %r
 }
 
 define i88 @rotl_i88_constant_commute(i88 %x) {
 ; CHECK-LABEL: @rotl_i88_constant_commute(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i88 [[X:%.*]], 44
-; CHECK-NEXT:    [[SHR:%.*]] = lshr i88 [[X]], 44
-; CHECK-NEXT:    [[R:%.*]] = or i88 [[SHL]], [[SHR]]
+; CHECK-NEXT:    [[R:%.*]] = call i88 @llvm.fshl.i88(i88 [[X:%.*]], i88 [[X]], i88 44)
 ; CHECK-NEXT:    ret i88 [[R]]
 ;
   %shl = shl i88 %x, 44
   %shr = lshr i88 %x, 44
   %r = or i88 %shl, %shr
   ret i88 %r
 }
 
 ; Vector types are allowed.
 
 define <2 x i16> @rotl_v2i16_constant_splat(<2 x i16> %x) {
 ; CHECK-LABEL: @rotl_v2i16_constant_splat(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i16> [[X:%.*]], <i16 1, i16 1>
-; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i16> [[X]], <i16 15, i16 15>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i16> [[SHL]], [[SHR]]
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i16> @llvm.fshl.v2i16(<2 x i16> [[X:%.*]], <2 x i16> [[X]], <2 x i16> <i16 1, i16 1>)
 ; CHECK-NEXT:    ret <2 x i16> [[R]]
 ;
   %shl = shl <2 x i16> %x, <i16 1, i16 1>
   %shr = lshr <2 x i16> %x, <i16 15, i16 15>
   %r = or <2 x i16> %shl, %shr
   ret <2 x i16> %r
 }
 
 ; Non-power-of-2 vector types are allowed.
 
 define <2 x i17> @rotr_v2i17_constant_splat(<2 x i17> %x) {
 ; CHECK-LABEL: @rotr_v2i17_constant_splat(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i17> [[X:%.*]], <i17 12, i17 12>
-; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i17> [[X]], <i17 5, i17 5>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i17> [[SHR]], [[SHL]]
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i17> @llvm.fshl.v2i17(<2 x i17> [[X:%.*]], <2 x i17> [[X]], <2 x i17> <i17 12, i17 12>)
 ; CHECK-NEXT:    ret <2 x i17> [[R]]
 ;
   %shl = shl <2 x i17> %x, <i17 12, i17 12>
   %shr = lshr <2 x i17> %x, <i17 5, i17 5>
   %r = or <2 x i17> %shr, %shl
   ret <2 x i17> %r
 }
 
-; Allow arbitrary shift constants.
+; TODO: Allow arbitrary shift constants.
 
 define <2 x i32> @rotr_v2i32_constant_nonsplat(<2 x i32> %x) {
 ; CHECK-LABEL: @rotr_v2i32_constant_nonsplat(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i32> [[X:%.*]], <i32 17, i32 19>
 ; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i32> [[X]], <i32 15, i32 13>
 ; CHECK-NEXT:    [[R:%.*]] = or <2 x i32> [[SHL]], [[SHR]]
 ; CHECK-NEXT:    ret <2 x i32> [[R]]
 ;