From 051e78c201382cf76eb86ea914dfc1d8f31d749b Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Sun, 17 Mar 2019 19:08:00 +0000 Subject: [PATCH] [InstCombine] canonicalize rotate right by constant to rotate left This was noted as a backend problem: https://bugs.llvm.org/show_bug.cgi?id=41057 ...and subsequently fixed for x86: rL356121 But we should canonicalize these in IR for the benefit of all targets and improve IR analysis such as CSE. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@356338 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../InstCombine/InstCombineCalls.cpp | 27 ++++++++++++++----- test/Transforms/InstCombine/fsh.ll | 8 +++--- 2 files changed, 24 insertions(+), 11 deletions(-) diff --git a/lib/Transforms/InstCombine/InstCombineCalls.cpp b/lib/Transforms/InstCombine/InstCombineCalls.cpp index 1c292ea1334..bdc235f247d 100644 --- a/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ b/lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -1993,22 +1993,36 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { case Intrinsic::fshl: case Intrinsic::fshr: { - // Canonicalize a shift amount constant operand to be modulo the bit-width. - unsigned BitWidth = II->getType()->getScalarSizeInBits(); + Value *Op0 = II->getArgOperand(0), *Op1 = II->getArgOperand(1); + Type *Ty = II->getType(); + unsigned BitWidth = Ty->getScalarSizeInBits(); Constant *ShAmtC; if (match(II->getArgOperand(2), m_Constant(ShAmtC)) && !isa(ShAmtC) && !ShAmtC->containsConstantExpression()) { - Constant *WidthC = ConstantInt::get(II->getType(), BitWidth); + // Canonicalize a shift amount constant operand to modulo the bit-width. + Constant *WidthC = ConstantInt::get(Ty, BitWidth); Constant *ModuloC = ConstantExpr::getURem(ShAmtC, WidthC); if (ModuloC != ShAmtC) { II->setArgOperand(2, ModuloC); return II; } + // Canonicalize rotate right by constant to rotate left. This is not + // entirely arbitrary. For historical reasons, the backend may recognize + // rotate left patterns but miss rotate right patterns. + if (II->getIntrinsicID() == Intrinsic::fshr && Op0 == Op1) { + // fshr X, X, C --> fshl X, X, (BitWidth - C) + assert(ConstantExpr::getICmp(ICmpInst::ICMP_UGT, WidthC, ShAmtC) == + ConstantInt::getTrue(CmpInst::makeCmpResultType(Ty)) && + "Shift amount expected to be modulo bitwidth"); + Constant *LeftShiftC = ConstantExpr::getSub(WidthC, ShAmtC); + Module *Mod = II->getModule(); + Function *Fshl = Intrinsic::getDeclaration(Mod, Intrinsic::fshl, Ty); + return CallInst::Create(Fshl, { Op0, Op0, LeftShiftC }); + } } const APInt *SA; if (match(II->getArgOperand(2), m_APInt(SA))) { - Value *Op0 = II->getArgOperand(0), *Op1 = II->getArgOperand(1); uint64_t ShiftAmt = SA->urem(BitWidth); assert(ShiftAmt != 0 && "SimplifyCall should have handled zero shift"); // Normalize to funnel shift left. @@ -2018,14 +2032,13 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { // 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)); + return BinaryOperator::CreateShl(Op0, ConstantInt::get(Ty, 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)); + Op1, ConstantInt::get(Ty, BitWidth - ShiftAmt)); } // The shift amount (operand 2) of a funnel shift is modulo the bitwidth, diff --git a/test/Transforms/InstCombine/fsh.ll b/test/Transforms/InstCombine/fsh.ll index 0bef978d197..63163ac7e18 100644 --- a/test/Transforms/InstCombine/fsh.ll +++ b/test/Transforms/InstCombine/fsh.ll @@ -399,7 +399,7 @@ define <2 x i31> @rotl_constant_shift_amount_vec(<2 x i31> %x) { define i33 @rotr_constant_shift_amount(i33 %x) { ; CHECK-LABEL: @rotr_constant_shift_amount( -; CHECK-NEXT: [[R:%.*]] = call i33 @llvm.fshr.i33(i33 [[X:%.*]], i33 [[X]], i33 1) +; CHECK-NEXT: [[R:%.*]] = call i33 @llvm.fshl.i33(i33 [[X:%.*]], i33 [[X]], i33 32) ; CHECK-NEXT: ret i33 [[R]] ; %r = call i33 @llvm.fshr.i33(i33 %x, i33 %x, i33 34) @@ -408,7 +408,7 @@ define i33 @rotr_constant_shift_amount(i33 %x) { define <2 x i32> @rotr_constant_shift_amount_vec(<2 x i32> %x) { ; CHECK-LABEL: @rotr_constant_shift_amount_vec( -; CHECK-NEXT: [[R:%.*]] = call <2 x i32> @llvm.fshr.v2i32(<2 x i32> [[X:%.*]], <2 x i32> [[X]], <2 x i32> ) +; CHECK-NEXT: [[R:%.*]] = call <2 x i32> @llvm.fshl.v2i32(<2 x i32> [[X:%.*]], <2 x i32> [[X]], <2 x i32> ) ; CHECK-NEXT: ret <2 x i32> [[R]] ; %r = call <2 x i32> @llvm.fshr.v2i32(<2 x i32> %x, <2 x i32> %x, <2 x i32> ) @@ -467,7 +467,7 @@ define i33 @fshr_known_bits(i33 %x, i33 %y) { define i33 @fshr_multi_use(i33 %a) { ; CHECK-LABEL: @fshr_multi_use( -; CHECK-NEXT: [[B:%.*]] = tail call i33 @llvm.fshr.i33(i33 [[A:%.*]], i33 [[A]], i33 1) +; 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 @@ -516,7 +516,7 @@ define i16 @fshl_bswap(i16 %x) { define i16 @fshr_bswap(i16 %x) { ; CHECK-LABEL: @fshr_bswap( -; CHECK-NEXT: [[R:%.*]] = call i16 @llvm.fshr.i16(i16 [[X:%.*]], i16 [[X]], i16 8) +; 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) -- 2.40.0