From 06248e49099bb8fedd8eecaab2d22d9b88d29d09 Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Wed, 1 Feb 2017 21:31:34 +0000 Subject: [PATCH] [InstCombine] move folds for shift-shift pairs; NFCI Although this is 'no-functional-change-intended', I'm adding tests for shl-shl and lshr-lshr pairs because there is no existing test coverage for those folds. It seems like we should be able to remove some code from foldShiftedShift() at this point because we're handling those patterns on the general path. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@293814 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../InstCombine/InstCombineShifts.cpp | 82 ++++++++----------- test/Transforms/InstCombine/apint-shift.ll | 52 ++++++++++++ 2 files changed, 86 insertions(+), 48 deletions(-) diff --git a/lib/Transforms/InstCombine/InstCombineShifts.cpp b/lib/Transforms/InstCombine/InstCombineShifts.cpp index 4b687925563..ab8ba9e4be0 100644 --- a/lib/Transforms/InstCombine/InstCombineShifts.cpp +++ b/lib/Transforms/InstCombine/InstCombineShifts.cpp @@ -309,41 +309,6 @@ static Value *getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift, } } -/// Try to fold (X << C1) << C2, where the shifts are some combination of -/// shl/ashr/lshr. -static Instruction * -foldShiftByConstOfShiftByConst(BinaryOperator &I, const APInt *COp1, - InstCombiner::BuilderTy *Builder) { - Value *Op0 = I.getOperand(0); - unsigned TypeBits = Op0->getType()->getScalarSizeInBits(); - - // Find out if this is a shift of a shift by a constant. - BinaryOperator *ShiftOp = dyn_cast(Op0); - if (!ShiftOp || !ShiftOp->isShift()) - return nullptr; - - const APInt *ShAmt1; - if (!match(ShiftOp->getOperand(1), m_APInt(ShAmt1))) - return nullptr; - - // Check for (X << c1) << c2 and (X >> c1) >> c2 - if (I.getOpcode() == ShiftOp->getOpcode()) { - unsigned AmtSum = (*ShAmt1 + *COp1).getZExtValue(); - // If this is an oversized composite shift, then unsigned shifts become - // zero (handled in InstSimplify) and ashr saturates. - if (AmtSum >= TypeBits) { - if (I.getOpcode() != Instruction::AShr) - return nullptr; - AmtSum = TypeBits - 1; // Saturate to 31 for i32 ashr. - } - - return BinaryOperator::Create(I.getOpcode(), ShiftOp->getOperand(0), - ConstantInt::get(I.getType(), AmtSum)); - } - - return nullptr; -} - Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, Constant *Op1, BinaryOperator &I) { bool isLeftShift = I.getOpcode() == Instruction::Shl; @@ -553,9 +518,6 @@ Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, Constant *Op1, } } - if (Instruction *Folded = foldShiftByConstOfShiftByConst(I, Op1C, Builder)) - return Folded; - return nullptr; } @@ -598,10 +560,10 @@ Instruction *InstCombiner::visitShl(BinaryOperator &I) { // arithmetic expressions are still recognizable by scalar evolution. // The inexact versions are deferred to DAGCombine, so we don't hide shl // behind a bit mask. - const APInt *ShrOp1; - if (match(Op0, m_CombineOr(m_Exact(m_LShr(m_Value(X), m_APInt(ShrOp1))), - m_Exact(m_AShr(m_Value(X), m_APInt(ShrOp1)))))) { - unsigned ShrAmt = ShrOp1->getZExtValue(); + const APInt *ShOp1; + if (match(Op0, m_CombineOr(m_Exact(m_LShr(m_Value(X), m_APInt(ShOp1))), + m_Exact(m_AShr(m_Value(X), m_APInt(ShOp1)))))) { + unsigned ShrAmt = ShOp1->getZExtValue(); if (ShrAmt < ShAmt) { // If C1 < C2: (X >>?,exact C1) << C2 --> X << (C2 - C1) Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShrAmt); @@ -620,6 +582,14 @@ Instruction *InstCombiner::visitShl(BinaryOperator &I) { } } + if (match(Op0, m_Shl(m_Value(X), m_APInt(ShOp1)))) { + unsigned AmtSum = ShAmt + ShOp1->getZExtValue(); + // Oversized shifts are simplified to zero in InstSimplify. + if (AmtSum < BitWidth) + // (X << C1) << C2 --> X << (C1 + C2) + return BinaryOperator::CreateShl(X, ConstantInt::get(Ty, AmtSum)); + } + // If the shifted-out value is known-zero, then this is a NUW shift. if (!I.hasNoUnsignedWrap() && MaskedValueIsZero(Op0, APInt::getHighBitsSet(BitWidth, ShAmt), 0, &I)) { @@ -675,9 +645,9 @@ Instruction *InstCombiner::visitLShr(BinaryOperator &I) { } Value *X; - const APInt *ShlAmtAPInt; - if (match(Op0, m_Shl(m_Value(X), m_APInt(ShlAmtAPInt)))) { - unsigned ShlAmt = ShlAmtAPInt->getZExtValue(); + const APInt *ShOp1; + if (match(Op0, m_Shl(m_Value(X), m_APInt(ShOp1)))) { + unsigned ShlAmt = ShOp1->getZExtValue(); if (ShlAmt < ShAmt) { Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt); if (cast(Op0)->hasNoUnsignedWrap()) { @@ -710,6 +680,14 @@ Instruction *InstCombiner::visitLShr(BinaryOperator &I) { return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask)); } + if (match(Op0, m_LShr(m_Value(X), m_APInt(ShOp1)))) { + unsigned AmtSum = ShAmt + ShOp1->getZExtValue(); + // Oversized shifts are simplified to zero in InstSimplify. + if (AmtSum < BitWidth) + // (X >>u C1) >>u C2 --> X >>u (C1 + C2) + return BinaryOperator::CreateLShr(X, ConstantInt::get(Ty, AmtSum)); + } + // If the shifted-out value is known-zero, then this is an exact shift. if (!I.isExact() && MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmt), 0, &I)) { @@ -747,9 +725,9 @@ Instruction *InstCombiner::visitAShr(BinaryOperator &I) { // We can't handle (X << C1) >>s C2. It shifts arbitrary bits in. However, // we can handle (X <>s C2 since it only shifts in sign bits. - const APInt *ShlAmtAPInt; - if (match(Op0, m_NSWShl(m_Value(X), m_APInt(ShlAmtAPInt)))) { - unsigned ShlAmt = ShlAmtAPInt->getZExtValue(); + const APInt *ShOp1; + if (match(Op0, m_NSWShl(m_Value(X), m_APInt(ShOp1)))) { + unsigned ShlAmt = ShOp1->getZExtValue(); if (ShlAmt < ShAmt) { // (X <>s C2 --> X >>s (C2 - C1) Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt); @@ -766,6 +744,14 @@ Instruction *InstCombiner::visitAShr(BinaryOperator &I) { } } + if (match(Op0, m_AShr(m_Value(X), m_APInt(ShOp1)))) { + unsigned AmtSum = ShAmt + ShOp1->getZExtValue(); + // Oversized arithmetic shifts replicate the sign bit. + AmtSum = std::min(AmtSum, BitWidth - 1); + // (X >>s C1) >>s C2 --> X >>s (C1 + C2) + return BinaryOperator::CreateAShr(X, ConstantInt::get(Ty, AmtSum)); + } + // If the shifted-out value is known-zero, then this is an exact shift. if (!I.isExact() && MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmt), 0, &I)) { diff --git a/test/Transforms/InstCombine/apint-shift.ll b/test/Transforms/InstCombine/apint-shift.ll index fc1934b576f..f1276beec9f 100644 --- a/test/Transforms/InstCombine/apint-shift.ll +++ b/test/Transforms/InstCombine/apint-shift.ll @@ -126,6 +126,32 @@ define <2 x i19> @lshr_lshr_splat_vec(<2 x i19> %X) { ret <2 x i19> %sh2 } +define i9 @multituse_lshr_lshr(i9 %x) { +; CHECK-LABEL: @multituse_lshr_lshr( +; CHECK-NEXT: [[SH1:%.*]] = lshr i9 %x, 2 +; CHECK-NEXT: [[SH2:%.*]] = lshr i9 %x, 5 +; CHECK-NEXT: [[MUL:%.*]] = mul i9 [[SH1]], [[SH2]] +; CHECK-NEXT: ret i9 [[MUL]] +; + %sh1 = lshr i9 %x, 2 + %sh2 = lshr i9 %sh1, 3 + %mul = mul i9 %sh1, %sh2 + ret i9 %mul +} + +define <2 x i9> @multiuse_lshr_lshr_splat(<2 x i9> %x) { +; CHECK-LABEL: @multiuse_lshr_lshr_splat( +; CHECK-NEXT: [[SH1:%.*]] = lshr <2 x i9> %x, +; CHECK-NEXT: [[SH2:%.*]] = lshr <2 x i9> %x, +; CHECK-NEXT: [[MUL:%.*]] = mul <2 x i9> [[SH1]], [[SH2]] +; CHECK-NEXT: ret <2 x i9> [[MUL]] +; + %sh1 = lshr <2 x i9> %x, + %sh2 = lshr <2 x i9> %sh1, + %mul = mul <2 x i9> %sh1, %sh2 + ret <2 x i9> %mul +} + ; Two left shifts in the same direction: ; shl (shl X, C1), C2 --> shl X, C1 + C2 @@ -139,6 +165,32 @@ define <2 x i19> @shl_shl_splat_vec(<2 x i19> %X) { ret <2 x i19> %sh2 } +define i42 @multiuse_shl_shl(i42 %x) { +; CHECK-LABEL: @multiuse_shl_shl( +; CHECK-NEXT: [[SH1:%.*]] = shl i42 %x, 8 +; CHECK-NEXT: [[SH2:%.*]] = shl i42 %x, 17 +; CHECK-NEXT: [[MUL:%.*]] = mul i42 [[SH1]], [[SH2]] +; CHECK-NEXT: ret i42 [[MUL]] +; + %sh1 = shl i42 %x, 8 + %sh2 = shl i42 %sh1, 9 + %mul = mul i42 %sh1, %sh2 + ret i42 %mul +} + +define <2 x i42> @mulituse_shl_shl_splat(<2 x i42> %x) { +; CHECK-LABEL: @mulituse_shl_shl_splat( +; CHECK-NEXT: [[SH1:%.*]] = shl <2 x i42> %x, +; CHECK-NEXT: [[SH2:%.*]] = shl <2 x i42> %x, +; CHECK-NEXT: [[MUL:%.*]] = mul <2 x i42> [[SH1]], [[SH2]] +; CHECK-NEXT: ret <2 x i42> [[MUL]] +; + %sh1 = shl <2 x i42> %x, + %sh2 = shl <2 x i42> %sh1, + %mul = mul <2 x i42> %sh1, %sh2 + ret <2 x i42> %mul +} + ; Equal shift amounts in opposite directions become bitwise 'and': ; lshr (shl X, C), C --> and X, C' -- 2.50.1