10b57cec5SDimitry Andric //===- InstCombineShifts.cpp ----------------------------------------------===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // This file implements the visitShl, visitLShr, and visitAShr functions. 100b57cec5SDimitry Andric // 110b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 120b57cec5SDimitry Andric 130b57cec5SDimitry Andric #include "InstCombineInternal.h" 140b57cec5SDimitry Andric #include "llvm/Analysis/InstructionSimplify.h" 150b57cec5SDimitry Andric #include "llvm/IR/IntrinsicInst.h" 160b57cec5SDimitry Andric #include "llvm/IR/PatternMatch.h" 17e8d8bef9SDimitry Andric #include "llvm/Transforms/InstCombine/InstCombiner.h" 180b57cec5SDimitry Andric using namespace llvm; 190b57cec5SDimitry Andric using namespace PatternMatch; 200b57cec5SDimitry Andric 210b57cec5SDimitry Andric #define DEBUG_TYPE "instcombine" 220b57cec5SDimitry Andric 2323408297SDimitry Andric bool canTryToConstantAddTwoShiftAmounts(Value *Sh0, Value *ShAmt0, Value *Sh1, 2423408297SDimitry Andric Value *ShAmt1) { 2523408297SDimitry Andric // We have two shift amounts from two different shifts. The types of those 2623408297SDimitry Andric // shift amounts may not match. If that's the case let's bailout now.. 2723408297SDimitry Andric if (ShAmt0->getType() != ShAmt1->getType()) 2823408297SDimitry Andric return false; 2923408297SDimitry Andric 3023408297SDimitry Andric // As input, we have the following pattern: 3123408297SDimitry Andric // Sh0 (Sh1 X, Q), K 3223408297SDimitry Andric // We want to rewrite that as: 3323408297SDimitry Andric // Sh x, (Q+K) iff (Q+K) u< bitwidth(x) 3423408297SDimitry Andric // While we know that originally (Q+K) would not overflow 3523408297SDimitry Andric // (because 2 * (N-1) u<= iN -1), we have looked past extensions of 3623408297SDimitry Andric // shift amounts. so it may now overflow in smaller bitwidth. 3723408297SDimitry Andric // To ensure that does not happen, we need to ensure that the total maximal 3823408297SDimitry Andric // shift amount is still representable in that smaller bit width. 3923408297SDimitry Andric unsigned MaximalPossibleTotalShiftAmount = 4023408297SDimitry Andric (Sh0->getType()->getScalarSizeInBits() - 1) + 4123408297SDimitry Andric (Sh1->getType()->getScalarSizeInBits() - 1); 4223408297SDimitry Andric APInt MaximalRepresentableShiftAmount = 43349cc55cSDimitry Andric APInt::getAllOnes(ShAmt0->getType()->getScalarSizeInBits()); 4423408297SDimitry Andric return MaximalRepresentableShiftAmount.uge(MaximalPossibleTotalShiftAmount); 4523408297SDimitry Andric } 4623408297SDimitry Andric 470b57cec5SDimitry Andric // Given pattern: 480b57cec5SDimitry Andric // (x shiftopcode Q) shiftopcode K 490b57cec5SDimitry Andric // we should rewrite it as 5047395794SDimitry Andric // x shiftopcode (Q+K) iff (Q+K) u< bitwidth(x) and 5147395794SDimitry Andric // 5247395794SDimitry Andric // This is valid for any shift, but they must be identical, and we must be 5347395794SDimitry Andric // careful in case we have (zext(Q)+zext(K)) and look past extensions, 5447395794SDimitry Andric // (Q+K) must not overflow or else (Q+K) u< bitwidth(x) is bogus. 558bcb0991SDimitry Andric // 568bcb0991SDimitry Andric // AnalyzeForSignBitExtraction indicates that we will only analyze whether this 578bcb0991SDimitry Andric // pattern has any 2 right-shifts that sum to 1 less than original bit width. 58e8d8bef9SDimitry Andric Value *InstCombinerImpl::reassociateShiftAmtsOfTwoSameDirectionShifts( 598bcb0991SDimitry Andric BinaryOperator *Sh0, const SimplifyQuery &SQ, 608bcb0991SDimitry Andric bool AnalyzeForSignBitExtraction) { 618bcb0991SDimitry Andric // Look for a shift of some instruction, ignore zext of shift amount if any. 628bcb0991SDimitry Andric Instruction *Sh0Op0; 638bcb0991SDimitry Andric Value *ShAmt0; 648bcb0991SDimitry Andric if (!match(Sh0, 658bcb0991SDimitry Andric m_Shift(m_Instruction(Sh0Op0), m_ZExtOrSelf(m_Value(ShAmt0))))) 660b57cec5SDimitry Andric return nullptr; 670b57cec5SDimitry Andric 688bcb0991SDimitry Andric // If there is a truncation between the two shifts, we must make note of it 698bcb0991SDimitry Andric // and look through it. The truncation imposes additional constraints on the 708bcb0991SDimitry Andric // transform. 718bcb0991SDimitry Andric Instruction *Sh1; 728bcb0991SDimitry Andric Value *Trunc = nullptr; 738bcb0991SDimitry Andric match(Sh0Op0, 748bcb0991SDimitry Andric m_CombineOr(m_CombineAnd(m_Trunc(m_Instruction(Sh1)), m_Value(Trunc)), 758bcb0991SDimitry Andric m_Instruction(Sh1))); 768bcb0991SDimitry Andric 778bcb0991SDimitry Andric // Inner shift: (x shiftopcode ShAmt1) 788bcb0991SDimitry Andric // Like with other shift, ignore zext of shift amount if any. 798bcb0991SDimitry Andric Value *X, *ShAmt1; 808bcb0991SDimitry Andric if (!match(Sh1, m_Shift(m_Value(X), m_ZExtOrSelf(m_Value(ShAmt1))))) 810b57cec5SDimitry Andric return nullptr; 828bcb0991SDimitry Andric 8323408297SDimitry Andric // Verify that it would be safe to try to add those two shift amounts. 8423408297SDimitry Andric if (!canTryToConstantAddTwoShiftAmounts(Sh0, ShAmt0, Sh1, ShAmt1)) 8547395794SDimitry Andric return nullptr; 8647395794SDimitry Andric 878bcb0991SDimitry Andric // We are only looking for signbit extraction if we have two right shifts. 888bcb0991SDimitry Andric bool HadTwoRightShifts = match(Sh0, m_Shr(m_Value(), m_Value())) && 898bcb0991SDimitry Andric match(Sh1, m_Shr(m_Value(), m_Value())); 908bcb0991SDimitry Andric // ... and if it's not two right-shifts, we know the answer already. 918bcb0991SDimitry Andric if (AnalyzeForSignBitExtraction && !HadTwoRightShifts) 928bcb0991SDimitry Andric return nullptr; 938bcb0991SDimitry Andric 948bcb0991SDimitry Andric // The shift opcodes must be identical, unless we are just checking whether 958bcb0991SDimitry Andric // this pattern can be interpreted as a sign-bit-extraction. 968bcb0991SDimitry Andric Instruction::BinaryOps ShiftOpcode = Sh0->getOpcode(); 978bcb0991SDimitry Andric bool IdenticalShOpcodes = Sh0->getOpcode() == Sh1->getOpcode(); 988bcb0991SDimitry Andric if (!IdenticalShOpcodes && !AnalyzeForSignBitExtraction) 998bcb0991SDimitry Andric return nullptr; 1008bcb0991SDimitry Andric 1018bcb0991SDimitry Andric // If we saw truncation, we'll need to produce extra instruction, 1028bcb0991SDimitry Andric // and for that one of the operands of the shift must be one-use, 1038bcb0991SDimitry Andric // unless of course we don't actually plan to produce any instructions here. 1048bcb0991SDimitry Andric if (Trunc && !AnalyzeForSignBitExtraction && 1058bcb0991SDimitry Andric !match(Sh0, m_c_BinOp(m_OneUse(m_Value()), m_Value()))) 1068bcb0991SDimitry Andric return nullptr; 1078bcb0991SDimitry Andric 1080b57cec5SDimitry Andric // Can we fold (ShAmt0+ShAmt1) ? 1098bcb0991SDimitry Andric auto *NewShAmt = dyn_cast_or_null<Constant>( 11081ad6265SDimitry Andric simplifyAddInst(ShAmt0, ShAmt1, /*isNSW=*/false, /*isNUW=*/false, 1118bcb0991SDimitry Andric SQ.getWithInstruction(Sh0))); 1120b57cec5SDimitry Andric if (!NewShAmt) 1130b57cec5SDimitry Andric return nullptr; // Did not simplify. 1148bcb0991SDimitry Andric unsigned NewShAmtBitWidth = NewShAmt->getType()->getScalarSizeInBits(); 1158bcb0991SDimitry Andric unsigned XBitWidth = X->getType()->getScalarSizeInBits(); 1168bcb0991SDimitry Andric // Is the new shift amount smaller than the bit width of inner/new shift? 1170b57cec5SDimitry Andric if (!match(NewShAmt, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT, 1188bcb0991SDimitry Andric APInt(NewShAmtBitWidth, XBitWidth)))) 1198bcb0991SDimitry Andric return nullptr; // FIXME: could perform constant-folding. 1208bcb0991SDimitry Andric 1218bcb0991SDimitry Andric // If there was a truncation, and we have a right-shift, we can only fold if 1228bcb0991SDimitry Andric // we are left with the original sign bit. Likewise, if we were just checking 1238bcb0991SDimitry Andric // that this is a sighbit extraction, this is the place to check it. 1248bcb0991SDimitry Andric // FIXME: zero shift amount is also legal here, but we can't *easily* check 1258bcb0991SDimitry Andric // more than one predicate so it's not really worth it. 1268bcb0991SDimitry Andric if (HadTwoRightShifts && (Trunc || AnalyzeForSignBitExtraction)) { 1278bcb0991SDimitry Andric // If it's not a sign bit extraction, then we're done. 1288bcb0991SDimitry Andric if (!match(NewShAmt, 1298bcb0991SDimitry Andric m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ, 1308bcb0991SDimitry Andric APInt(NewShAmtBitWidth, XBitWidth - 1)))) 1310b57cec5SDimitry Andric return nullptr; 1328bcb0991SDimitry Andric // If it is, and that was the question, return the base value. 1338bcb0991SDimitry Andric if (AnalyzeForSignBitExtraction) 1348bcb0991SDimitry Andric return X; 1358bcb0991SDimitry Andric } 1368bcb0991SDimitry Andric 1378bcb0991SDimitry Andric assert(IdenticalShOpcodes && "Should not get here with different shifts."); 1388bcb0991SDimitry Andric 1395f757f3fSDimitry Andric if (NewShAmt->getType() != X->getType()) { 1405f757f3fSDimitry Andric NewShAmt = ConstantFoldCastOperand(Instruction::ZExt, NewShAmt, 1415f757f3fSDimitry Andric X->getType(), SQ.DL); 1425f757f3fSDimitry Andric if (!NewShAmt) 1435f757f3fSDimitry Andric return nullptr; 1445f757f3fSDimitry Andric } 1458bcb0991SDimitry Andric 1465f757f3fSDimitry Andric // All good, we can do this fold. 1470b57cec5SDimitry Andric BinaryOperator *NewShift = BinaryOperator::Create(ShiftOpcode, X, NewShAmt); 1488bcb0991SDimitry Andric 1498bcb0991SDimitry Andric // The flags can only be propagated if there wasn't a trunc. 1508bcb0991SDimitry Andric if (!Trunc) { 1518bcb0991SDimitry Andric // If the pattern did not involve trunc, and both of the original shifts 1528bcb0991SDimitry Andric // had the same flag set, preserve the flag. 1530b57cec5SDimitry Andric if (ShiftOpcode == Instruction::BinaryOps::Shl) { 1540b57cec5SDimitry Andric NewShift->setHasNoUnsignedWrap(Sh0->hasNoUnsignedWrap() && 1550b57cec5SDimitry Andric Sh1->hasNoUnsignedWrap()); 1560b57cec5SDimitry Andric NewShift->setHasNoSignedWrap(Sh0->hasNoSignedWrap() && 1570b57cec5SDimitry Andric Sh1->hasNoSignedWrap()); 1580b57cec5SDimitry Andric } else { 1590b57cec5SDimitry Andric NewShift->setIsExact(Sh0->isExact() && Sh1->isExact()); 1600b57cec5SDimitry Andric } 1618bcb0991SDimitry Andric } 1628bcb0991SDimitry Andric 1638bcb0991SDimitry Andric Instruction *Ret = NewShift; 1648bcb0991SDimitry Andric if (Trunc) { 1658bcb0991SDimitry Andric Builder.Insert(NewShift); 1668bcb0991SDimitry Andric Ret = CastInst::Create(Instruction::Trunc, NewShift, Sh0->getType()); 1678bcb0991SDimitry Andric } 1688bcb0991SDimitry Andric 1698bcb0991SDimitry Andric return Ret; 1708bcb0991SDimitry Andric } 1718bcb0991SDimitry Andric 1728bcb0991SDimitry Andric // If we have some pattern that leaves only some low bits set, and then performs 1738bcb0991SDimitry Andric // left-shift of those bits, if none of the bits that are left after the final 1748bcb0991SDimitry Andric // shift are modified by the mask, we can omit the mask. 1758bcb0991SDimitry Andric // 1768bcb0991SDimitry Andric // There are many variants to this pattern: 1778bcb0991SDimitry Andric // a) (x & ((1 << MaskShAmt) - 1)) << ShiftShAmt 1788bcb0991SDimitry Andric // b) (x & (~(-1 << MaskShAmt))) << ShiftShAmt 179349cc55cSDimitry Andric // c) (x & (-1 l>> MaskShAmt)) << ShiftShAmt 180349cc55cSDimitry Andric // d) (x & ((-1 << MaskShAmt) l>> MaskShAmt)) << ShiftShAmt 1818bcb0991SDimitry Andric // e) ((x << MaskShAmt) l>> MaskShAmt) << ShiftShAmt 1828bcb0991SDimitry Andric // f) ((x << MaskShAmt) a>> MaskShAmt) << ShiftShAmt 1838bcb0991SDimitry Andric // All these patterns can be simplified to just: 1848bcb0991SDimitry Andric // x << ShiftShAmt 1858bcb0991SDimitry Andric // iff: 1868bcb0991SDimitry Andric // a,b) (MaskShAmt+ShiftShAmt) u>= bitwidth(x) 1878bcb0991SDimitry Andric // c,d,e,f) (ShiftShAmt-MaskShAmt) s>= 0 (i.e. ShiftShAmt u>= MaskShAmt) 1888bcb0991SDimitry Andric static Instruction * 1898bcb0991SDimitry Andric dropRedundantMaskingOfLeftShiftInput(BinaryOperator *OuterShift, 1908bcb0991SDimitry Andric const SimplifyQuery &Q, 1918bcb0991SDimitry Andric InstCombiner::BuilderTy &Builder) { 1928bcb0991SDimitry Andric assert(OuterShift->getOpcode() == Instruction::BinaryOps::Shl && 1938bcb0991SDimitry Andric "The input must be 'shl'!"); 1948bcb0991SDimitry Andric 1958bcb0991SDimitry Andric Value *Masked, *ShiftShAmt; 196480093f4SDimitry Andric match(OuterShift, 197480093f4SDimitry Andric m_Shift(m_Value(Masked), m_ZExtOrSelf(m_Value(ShiftShAmt)))); 198480093f4SDimitry Andric 199480093f4SDimitry Andric // *If* there is a truncation between an outer shift and a possibly-mask, 200480093f4SDimitry Andric // then said truncation *must* be one-use, else we can't perform the fold. 201480093f4SDimitry Andric Value *Trunc; 202480093f4SDimitry Andric if (match(Masked, m_CombineAnd(m_Trunc(m_Value(Masked)), m_Value(Trunc))) && 203480093f4SDimitry Andric !Trunc->hasOneUse()) 204480093f4SDimitry Andric return nullptr; 2058bcb0991SDimitry Andric 2068bcb0991SDimitry Andric Type *NarrowestTy = OuterShift->getType(); 2078bcb0991SDimitry Andric Type *WidestTy = Masked->getType(); 208480093f4SDimitry Andric bool HadTrunc = WidestTy != NarrowestTy; 209480093f4SDimitry Andric 2108bcb0991SDimitry Andric // The mask must be computed in a type twice as wide to ensure 2118bcb0991SDimitry Andric // that no bits are lost if the sum-of-shifts is wider than the base type. 2128bcb0991SDimitry Andric Type *ExtendedTy = WidestTy->getExtendedType(); 2138bcb0991SDimitry Andric 2148bcb0991SDimitry Andric Value *MaskShAmt; 2158bcb0991SDimitry Andric 2168bcb0991SDimitry Andric // ((1 << MaskShAmt) - 1) 2178bcb0991SDimitry Andric auto MaskA = m_Add(m_Shl(m_One(), m_Value(MaskShAmt)), m_AllOnes()); 2188bcb0991SDimitry Andric // (~(-1 << maskNbits)) 219*0fca6ea1SDimitry Andric auto MaskB = m_Not(m_Shl(m_AllOnes(), m_Value(MaskShAmt))); 220349cc55cSDimitry Andric // (-1 l>> MaskShAmt) 221349cc55cSDimitry Andric auto MaskC = m_LShr(m_AllOnes(), m_Value(MaskShAmt)); 222349cc55cSDimitry Andric // ((-1 << MaskShAmt) l>> MaskShAmt) 2238bcb0991SDimitry Andric auto MaskD = 224349cc55cSDimitry Andric m_LShr(m_Shl(m_AllOnes(), m_Value(MaskShAmt)), m_Deferred(MaskShAmt)); 2258bcb0991SDimitry Andric 2268bcb0991SDimitry Andric Value *X; 2278bcb0991SDimitry Andric Constant *NewMask; 2288bcb0991SDimitry Andric 2298bcb0991SDimitry Andric if (match(Masked, m_c_And(m_CombineOr(MaskA, MaskB), m_Value(X)))) { 230480093f4SDimitry Andric // Peek through an optional zext of the shift amount. 231480093f4SDimitry Andric match(MaskShAmt, m_ZExtOrSelf(m_Value(MaskShAmt))); 232480093f4SDimitry Andric 23323408297SDimitry Andric // Verify that it would be safe to try to add those two shift amounts. 23423408297SDimitry Andric if (!canTryToConstantAddTwoShiftAmounts(OuterShift, ShiftShAmt, Masked, 23523408297SDimitry Andric MaskShAmt)) 236480093f4SDimitry Andric return nullptr; 237480093f4SDimitry Andric 2388bcb0991SDimitry Andric // Can we simplify (MaskShAmt+ShiftShAmt) ? 23981ad6265SDimitry Andric auto *SumOfShAmts = dyn_cast_or_null<Constant>(simplifyAddInst( 2408bcb0991SDimitry Andric MaskShAmt, ShiftShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q)); 2418bcb0991SDimitry Andric if (!SumOfShAmts) 2428bcb0991SDimitry Andric return nullptr; // Did not simplify. 2438bcb0991SDimitry Andric // In this pattern SumOfShAmts correlates with the number of low bits 2448bcb0991SDimitry Andric // that shall remain in the root value (OuterShift). 2458bcb0991SDimitry Andric 2468bcb0991SDimitry Andric // An extend of an undef value becomes zero because the high bits are never 247349cc55cSDimitry Andric // completely unknown. Replace the `undef` shift amounts with final 2488bcb0991SDimitry Andric // shift bitwidth to ensure that the value remains undef when creating the 2498bcb0991SDimitry Andric // subsequent shift op. 250480093f4SDimitry Andric SumOfShAmts = Constant::replaceUndefsWith( 2518bcb0991SDimitry Andric SumOfShAmts, ConstantInt::get(SumOfShAmts->getType()->getScalarType(), 2528bcb0991SDimitry Andric ExtendedTy->getScalarSizeInBits())); 2535f757f3fSDimitry Andric auto *ExtendedSumOfShAmts = ConstantFoldCastOperand( 2545f757f3fSDimitry Andric Instruction::ZExt, SumOfShAmts, ExtendedTy, Q.DL); 2555f757f3fSDimitry Andric if (!ExtendedSumOfShAmts) 2565f757f3fSDimitry Andric return nullptr; 2575f757f3fSDimitry Andric 2588bcb0991SDimitry Andric // And compute the mask as usual: ~(-1 << (SumOfShAmts)) 2598bcb0991SDimitry Andric auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(ExtendedTy); 260*0fca6ea1SDimitry Andric Constant *ExtendedInvertedMask = ConstantFoldBinaryOpOperands( 261*0fca6ea1SDimitry Andric Instruction::Shl, ExtendedAllOnes, ExtendedSumOfShAmts, Q.DL); 262*0fca6ea1SDimitry Andric if (!ExtendedInvertedMask) 263*0fca6ea1SDimitry Andric return nullptr; 264*0fca6ea1SDimitry Andric 2658bcb0991SDimitry Andric NewMask = ConstantExpr::getNot(ExtendedInvertedMask); 2668bcb0991SDimitry Andric } else if (match(Masked, m_c_And(m_CombineOr(MaskC, MaskD), m_Value(X))) || 2678bcb0991SDimitry Andric match(Masked, m_Shr(m_Shl(m_Value(X), m_Value(MaskShAmt)), 2688bcb0991SDimitry Andric m_Deferred(MaskShAmt)))) { 269480093f4SDimitry Andric // Peek through an optional zext of the shift amount. 270480093f4SDimitry Andric match(MaskShAmt, m_ZExtOrSelf(m_Value(MaskShAmt))); 271480093f4SDimitry Andric 27223408297SDimitry Andric // Verify that it would be safe to try to add those two shift amounts. 27323408297SDimitry Andric if (!canTryToConstantAddTwoShiftAmounts(OuterShift, ShiftShAmt, Masked, 27423408297SDimitry Andric MaskShAmt)) 275480093f4SDimitry Andric return nullptr; 276480093f4SDimitry Andric 2778bcb0991SDimitry Andric // Can we simplify (ShiftShAmt-MaskShAmt) ? 27881ad6265SDimitry Andric auto *ShAmtsDiff = dyn_cast_or_null<Constant>(simplifySubInst( 2798bcb0991SDimitry Andric ShiftShAmt, MaskShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q)); 2808bcb0991SDimitry Andric if (!ShAmtsDiff) 2818bcb0991SDimitry Andric return nullptr; // Did not simplify. 2828bcb0991SDimitry Andric // In this pattern ShAmtsDiff correlates with the number of high bits that 2838bcb0991SDimitry Andric // shall be unset in the root value (OuterShift). 2848bcb0991SDimitry Andric 2858bcb0991SDimitry Andric // An extend of an undef value becomes zero because the high bits are never 286349cc55cSDimitry Andric // completely unknown. Replace the `undef` shift amounts with negated 2878bcb0991SDimitry Andric // bitwidth of innermost shift to ensure that the value remains undef when 2888bcb0991SDimitry Andric // creating the subsequent shift op. 2898bcb0991SDimitry Andric unsigned WidestTyBitWidth = WidestTy->getScalarSizeInBits(); 290480093f4SDimitry Andric ShAmtsDiff = Constant::replaceUndefsWith( 2918bcb0991SDimitry Andric ShAmtsDiff, ConstantInt::get(ShAmtsDiff->getType()->getScalarType(), 2928bcb0991SDimitry Andric -WidestTyBitWidth)); 2935f757f3fSDimitry Andric auto *ExtendedNumHighBitsToClear = ConstantFoldCastOperand( 2945f757f3fSDimitry Andric Instruction::ZExt, 2958bcb0991SDimitry Andric ConstantExpr::getSub(ConstantInt::get(ShAmtsDiff->getType(), 2968bcb0991SDimitry Andric WidestTyBitWidth, 2978bcb0991SDimitry Andric /*isSigned=*/false), 2988bcb0991SDimitry Andric ShAmtsDiff), 2995f757f3fSDimitry Andric ExtendedTy, Q.DL); 3005f757f3fSDimitry Andric if (!ExtendedNumHighBitsToClear) 3015f757f3fSDimitry Andric return nullptr; 3025f757f3fSDimitry Andric 3038bcb0991SDimitry Andric // And compute the mask as usual: (-1 l>> (NumHighBitsToClear)) 3048bcb0991SDimitry Andric auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(ExtendedTy); 3055f757f3fSDimitry Andric NewMask = ConstantFoldBinaryOpOperands(Instruction::LShr, ExtendedAllOnes, 3065f757f3fSDimitry Andric ExtendedNumHighBitsToClear, Q.DL); 3075f757f3fSDimitry Andric if (!NewMask) 3085f757f3fSDimitry Andric return nullptr; 3098bcb0991SDimitry Andric } else 3108bcb0991SDimitry Andric return nullptr; // Don't know anything about this pattern. 3118bcb0991SDimitry Andric 3128bcb0991SDimitry Andric NewMask = ConstantExpr::getTrunc(NewMask, NarrowestTy); 3138bcb0991SDimitry Andric 3148bcb0991SDimitry Andric // Does this mask has any unset bits? If not then we can just not apply it. 3158bcb0991SDimitry Andric bool NeedMask = !match(NewMask, m_AllOnes()); 3168bcb0991SDimitry Andric 3178bcb0991SDimitry Andric // If we need to apply a mask, there are several more restrictions we have. 3188bcb0991SDimitry Andric if (NeedMask) { 3198bcb0991SDimitry Andric // The old masking instruction must go away. 3208bcb0991SDimitry Andric if (!Masked->hasOneUse()) 3218bcb0991SDimitry Andric return nullptr; 3228bcb0991SDimitry Andric // The original "masking" instruction must not have been`ashr`. 3238bcb0991SDimitry Andric if (match(Masked, m_AShr(m_Value(), m_Value()))) 3248bcb0991SDimitry Andric return nullptr; 3258bcb0991SDimitry Andric } 3268bcb0991SDimitry Andric 327480093f4SDimitry Andric // If we need to apply truncation, let's do it first, since we can. 328480093f4SDimitry Andric // We have already ensured that the old truncation will go away. 329480093f4SDimitry Andric if (HadTrunc) 330480093f4SDimitry Andric X = Builder.CreateTrunc(X, NarrowestTy); 331480093f4SDimitry Andric 3328bcb0991SDimitry Andric // No 'NUW'/'NSW'! We no longer know that we won't shift-out non-0 bits. 333480093f4SDimitry Andric // We didn't change the Type of this outermost shift, so we can just do it. 3348bcb0991SDimitry Andric auto *NewShift = BinaryOperator::Create(OuterShift->getOpcode(), X, 3358bcb0991SDimitry Andric OuterShift->getOperand(1)); 3368bcb0991SDimitry Andric if (!NeedMask) 3370b57cec5SDimitry Andric return NewShift; 3388bcb0991SDimitry Andric 3398bcb0991SDimitry Andric Builder.Insert(NewShift); 3408bcb0991SDimitry Andric return BinaryOperator::Create(Instruction::And, NewShift, NewMask); 3410b57cec5SDimitry Andric } 3420b57cec5SDimitry Andric 34306c3fb27SDimitry Andric /// If we have a shift-by-constant of a bin op (bitwise logic op or add/sub w/ 34406c3fb27SDimitry Andric /// shl) that itself has a shift-by-constant operand with identical opcode, we 34506c3fb27SDimitry Andric /// may be able to convert that into 2 independent shifts followed by the logic 34606c3fb27SDimitry Andric /// op. This eliminates a use of an intermediate value (reduces dependency 34706c3fb27SDimitry Andric /// chain). 34806c3fb27SDimitry Andric static Instruction *foldShiftOfShiftedBinOp(BinaryOperator &I, 349480093f4SDimitry Andric InstCombiner::BuilderTy &Builder) { 350480093f4SDimitry Andric assert(I.isShift() && "Expected a shift as input"); 35106c3fb27SDimitry Andric auto *BinInst = dyn_cast<BinaryOperator>(I.getOperand(0)); 35206c3fb27SDimitry Andric if (!BinInst || 35306c3fb27SDimitry Andric (!BinInst->isBitwiseLogicOp() && 35406c3fb27SDimitry Andric BinInst->getOpcode() != Instruction::Add && 35506c3fb27SDimitry Andric BinInst->getOpcode() != Instruction::Sub) || 35606c3fb27SDimitry Andric !BinInst->hasOneUse()) 357480093f4SDimitry Andric return nullptr; 358480093f4SDimitry Andric 359e8d8bef9SDimitry Andric Constant *C0, *C1; 360e8d8bef9SDimitry Andric if (!match(I.getOperand(1), m_Constant(C1))) 361480093f4SDimitry Andric return nullptr; 362480093f4SDimitry Andric 363480093f4SDimitry Andric Instruction::BinaryOps ShiftOpcode = I.getOpcode(); 36406c3fb27SDimitry Andric // Transform for add/sub only works with shl. 36506c3fb27SDimitry Andric if ((BinInst->getOpcode() == Instruction::Add || 36606c3fb27SDimitry Andric BinInst->getOpcode() == Instruction::Sub) && 36706c3fb27SDimitry Andric ShiftOpcode != Instruction::Shl) 36806c3fb27SDimitry Andric return nullptr; 36906c3fb27SDimitry Andric 370480093f4SDimitry Andric Type *Ty = I.getType(); 371480093f4SDimitry Andric 3727a6dacacSDimitry Andric // Find a matching shift by constant. The fold is not valid if the sum 373480093f4SDimitry Andric // of the shift values equals or exceeds bitwidth. 374480093f4SDimitry Andric Value *X, *Y; 3757a6dacacSDimitry Andric auto matchFirstShift = [&](Value *V, Value *W) { 3767a6dacacSDimitry Andric unsigned Size = Ty->getScalarSizeInBits(); 3777a6dacacSDimitry Andric APInt Threshold(Size, Size); 3787a6dacacSDimitry Andric return match(V, m_BinOp(ShiftOpcode, m_Value(X), m_Constant(C0))) && 3797a6dacacSDimitry Andric (V->hasOneUse() || match(W, m_ImmConstant())) && 380e8d8bef9SDimitry Andric match(ConstantExpr::getAdd(C0, C1), 381e8d8bef9SDimitry Andric m_SpecificInt_ICMP(ICmpInst::ICMP_ULT, Threshold)); 382480093f4SDimitry Andric }; 383480093f4SDimitry Andric 38406c3fb27SDimitry Andric // Logic ops and Add are commutative, so check each operand for a match. Sub 38506c3fb27SDimitry Andric // is not so we cannot reoder if we match operand(1) and need to keep the 38606c3fb27SDimitry Andric // operands in their original positions. 38706c3fb27SDimitry Andric bool FirstShiftIsOp1 = false; 3887a6dacacSDimitry Andric if (matchFirstShift(BinInst->getOperand(0), BinInst->getOperand(1))) 38906c3fb27SDimitry Andric Y = BinInst->getOperand(1); 3907a6dacacSDimitry Andric else if (matchFirstShift(BinInst->getOperand(1), BinInst->getOperand(0))) { 39106c3fb27SDimitry Andric Y = BinInst->getOperand(0); 39206c3fb27SDimitry Andric FirstShiftIsOp1 = BinInst->getOpcode() == Instruction::Sub; 39306c3fb27SDimitry Andric } else 394480093f4SDimitry Andric return nullptr; 395480093f4SDimitry Andric 39606c3fb27SDimitry Andric // shift (binop (shift X, C0), Y), C1 -> binop (shift X, C0+C1), (shift Y, C1) 397e8d8bef9SDimitry Andric Constant *ShiftSumC = ConstantExpr::getAdd(C0, C1); 398480093f4SDimitry Andric Value *NewShift1 = Builder.CreateBinOp(ShiftOpcode, X, ShiftSumC); 399bdd1243dSDimitry Andric Value *NewShift2 = Builder.CreateBinOp(ShiftOpcode, Y, C1); 40006c3fb27SDimitry Andric Value *Op1 = FirstShiftIsOp1 ? NewShift2 : NewShift1; 40106c3fb27SDimitry Andric Value *Op2 = FirstShiftIsOp1 ? NewShift1 : NewShift2; 40206c3fb27SDimitry Andric return BinaryOperator::Create(BinInst->getOpcode(), Op1, Op2); 403480093f4SDimitry Andric } 404480093f4SDimitry Andric 405e8d8bef9SDimitry Andric Instruction *InstCombinerImpl::commonShiftTransforms(BinaryOperator &I) { 40604eeddc0SDimitry Andric if (Instruction *Phi = foldBinopWithPhiOperands(I)) 40704eeddc0SDimitry Andric return Phi; 40804eeddc0SDimitry Andric 4090b57cec5SDimitry Andric Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 4100b57cec5SDimitry Andric assert(Op0->getType() == Op1->getType()); 41181ad6265SDimitry Andric Type *Ty = I.getType(); 4120b57cec5SDimitry Andric 4138bcb0991SDimitry Andric // If the shift amount is a one-use `sext`, we can demote it to `zext`. 4148bcb0991SDimitry Andric Value *Y; 4158bcb0991SDimitry Andric if (match(Op1, m_OneUse(m_SExt(m_Value(Y))))) { 41681ad6265SDimitry Andric Value *NewExt = Builder.CreateZExt(Y, Ty, Op1->getName()); 4178bcb0991SDimitry Andric return BinaryOperator::Create(I.getOpcode(), Op0, NewExt); 4188bcb0991SDimitry Andric } 4198bcb0991SDimitry Andric 4200b57cec5SDimitry Andric // See if we can fold away this shift. 4210b57cec5SDimitry Andric if (SimplifyDemandedInstructionBits(I)) 4220b57cec5SDimitry Andric return &I; 4230b57cec5SDimitry Andric 4240b57cec5SDimitry Andric // Try to fold constant and into select arguments. 4250b57cec5SDimitry Andric if (isa<Constant>(Op0)) 4260b57cec5SDimitry Andric if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 4270b57cec5SDimitry Andric if (Instruction *R = FoldOpIntoSelect(I, SI)) 4280b57cec5SDimitry Andric return R; 4290b57cec5SDimitry Andric 4300b57cec5SDimitry Andric if (Constant *CUI = dyn_cast<Constant>(Op1)) 4310b57cec5SDimitry Andric if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I)) 4320b57cec5SDimitry Andric return Res; 4330b57cec5SDimitry Andric 4348bcb0991SDimitry Andric if (auto *NewShift = cast_or_null<Instruction>( 4358bcb0991SDimitry Andric reassociateShiftAmtsOfTwoSameDirectionShifts(&I, SQ))) 4360b57cec5SDimitry Andric return NewShift; 4370b57cec5SDimitry Andric 43881ad6265SDimitry Andric // Pre-shift a constant shifted by a variable amount with constant offset: 43981ad6265SDimitry Andric // C shift (A add nuw C1) --> (C shift C1) shift A 4400b57cec5SDimitry Andric Value *A; 44181ad6265SDimitry Andric Constant *C, *C1; 44281ad6265SDimitry Andric if (match(Op0, m_Constant(C)) && 443*0fca6ea1SDimitry Andric match(Op1, m_NUWAddLike(m_Value(A), m_Constant(C1)))) { 44481ad6265SDimitry Andric Value *NewC = Builder.CreateBinOp(I.getOpcode(), C, C1); 445*0fca6ea1SDimitry Andric BinaryOperator *NewShiftOp = BinaryOperator::Create(I.getOpcode(), NewC, A); 446*0fca6ea1SDimitry Andric if (I.getOpcode() == Instruction::Shl) { 447*0fca6ea1SDimitry Andric NewShiftOp->setHasNoSignedWrap(I.hasNoSignedWrap()); 448*0fca6ea1SDimitry Andric NewShiftOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 449*0fca6ea1SDimitry Andric } else { 450*0fca6ea1SDimitry Andric NewShiftOp->setIsExact(I.isExact()); 451*0fca6ea1SDimitry Andric } 452*0fca6ea1SDimitry Andric return NewShiftOp; 45381ad6265SDimitry Andric } 45481ad6265SDimitry Andric 45581ad6265SDimitry Andric unsigned BitWidth = Ty->getScalarSizeInBits(); 45681ad6265SDimitry Andric 45781ad6265SDimitry Andric const APInt *AC, *AddC; 45881ad6265SDimitry Andric // Try to pre-shift a constant shifted by a variable amount added with a 45981ad6265SDimitry Andric // negative number: 46081ad6265SDimitry Andric // C << (X - AddC) --> (C >> AddC) << X 46181ad6265SDimitry Andric // and 46281ad6265SDimitry Andric // C >> (X - AddC) --> (C << AddC) >> X 46381ad6265SDimitry Andric if (match(Op0, m_APInt(AC)) && match(Op1, m_Add(m_Value(A), m_APInt(AddC))) && 46481ad6265SDimitry Andric AddC->isNegative() && (-*AddC).ult(BitWidth)) { 46581ad6265SDimitry Andric assert(!AC->isZero() && "Expected simplify of shifted zero"); 46681ad6265SDimitry Andric unsigned PosOffset = (-*AddC).getZExtValue(); 46781ad6265SDimitry Andric 46881ad6265SDimitry Andric auto isSuitableForPreShift = [PosOffset, &I, AC]() { 46981ad6265SDimitry Andric switch (I.getOpcode()) { 47081ad6265SDimitry Andric default: 47181ad6265SDimitry Andric return false; 47281ad6265SDimitry Andric case Instruction::Shl: 47381ad6265SDimitry Andric return (I.hasNoSignedWrap() || I.hasNoUnsignedWrap()) && 47481ad6265SDimitry Andric AC->eq(AC->lshr(PosOffset).shl(PosOffset)); 47581ad6265SDimitry Andric case Instruction::LShr: 47681ad6265SDimitry Andric return I.isExact() && AC->eq(AC->shl(PosOffset).lshr(PosOffset)); 47781ad6265SDimitry Andric case Instruction::AShr: 47881ad6265SDimitry Andric return I.isExact() && AC->eq(AC->shl(PosOffset).ashr(PosOffset)); 47981ad6265SDimitry Andric } 48081ad6265SDimitry Andric }; 48181ad6265SDimitry Andric if (isSuitableForPreShift()) { 48281ad6265SDimitry Andric Constant *NewC = ConstantInt::get(Ty, I.getOpcode() == Instruction::Shl 48381ad6265SDimitry Andric ? AC->lshr(PosOffset) 48481ad6265SDimitry Andric : AC->shl(PosOffset)); 48581ad6265SDimitry Andric BinaryOperator *NewShiftOp = 48681ad6265SDimitry Andric BinaryOperator::Create(I.getOpcode(), NewC, A); 48781ad6265SDimitry Andric if (I.getOpcode() == Instruction::Shl) { 48881ad6265SDimitry Andric NewShiftOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 48981ad6265SDimitry Andric } else { 49081ad6265SDimitry Andric NewShiftOp->setIsExact(); 49181ad6265SDimitry Andric } 49281ad6265SDimitry Andric return NewShiftOp; 49381ad6265SDimitry Andric } 49481ad6265SDimitry Andric } 4950b57cec5SDimitry Andric 496e8d8bef9SDimitry Andric // X shift (A srem C) -> X shift (A and (C - 1)) iff C is a power of 2. 4970b57cec5SDimitry Andric // Because shifts by negative values (which could occur if A were negative) 4980b57cec5SDimitry Andric // are undefined. 499e8d8bef9SDimitry Andric if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Constant(C))) && 500e8d8bef9SDimitry Andric match(C, m_Power2())) { 5010b57cec5SDimitry Andric // FIXME: Should this get moved into SimplifyDemandedBits by saying we don't 5020b57cec5SDimitry Andric // demand the sign bit (and many others) here?? 50381ad6265SDimitry Andric Constant *Mask = ConstantExpr::getSub(C, ConstantInt::get(Ty, 1)); 504e8d8bef9SDimitry Andric Value *Rem = Builder.CreateAnd(A, Mask, Op1->getName()); 5055ffd83dbSDimitry Andric return replaceOperand(I, 1, Rem); 5060b57cec5SDimitry Andric } 5070b57cec5SDimitry Andric 50806c3fb27SDimitry Andric if (Instruction *Logic = foldShiftOfShiftedBinOp(I, Builder)) 509480093f4SDimitry Andric return Logic; 510480093f4SDimitry Andric 51106c3fb27SDimitry Andric if (match(Op1, m_Or(m_Value(), m_SpecificInt(BitWidth - 1)))) 51206c3fb27SDimitry Andric return replaceOperand(I, 1, ConstantInt::get(Ty, BitWidth - 1)); 51306c3fb27SDimitry Andric 5140b57cec5SDimitry Andric return nullptr; 5150b57cec5SDimitry Andric } 5160b57cec5SDimitry Andric 5170b57cec5SDimitry Andric /// Return true if we can simplify two logical (either left or right) shifts 5180b57cec5SDimitry Andric /// that have constant shift amounts: OuterShift (InnerShift X, C1), C2. 5190b57cec5SDimitry Andric static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl, 520e8d8bef9SDimitry Andric Instruction *InnerShift, 521e8d8bef9SDimitry Andric InstCombinerImpl &IC, Instruction *CxtI) { 5220b57cec5SDimitry Andric assert(InnerShift->isLogicalShift() && "Unexpected instruction type"); 5230b57cec5SDimitry Andric 5240b57cec5SDimitry Andric // We need constant scalar or constant splat shifts. 5250b57cec5SDimitry Andric const APInt *InnerShiftConst; 5260b57cec5SDimitry Andric if (!match(InnerShift->getOperand(1), m_APInt(InnerShiftConst))) 5270b57cec5SDimitry Andric return false; 5280b57cec5SDimitry Andric 5290b57cec5SDimitry Andric // Two logical shifts in the same direction: 5300b57cec5SDimitry Andric // shl (shl X, C1), C2 --> shl X, C1 + C2 5310b57cec5SDimitry Andric // lshr (lshr X, C1), C2 --> lshr X, C1 + C2 5320b57cec5SDimitry Andric bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl; 5330b57cec5SDimitry Andric if (IsInnerShl == IsOuterShl) 5340b57cec5SDimitry Andric return true; 5350b57cec5SDimitry Andric 5360b57cec5SDimitry Andric // Equal shift amounts in opposite directions become bitwise 'and': 5370b57cec5SDimitry Andric // lshr (shl X, C), C --> and X, C' 5380b57cec5SDimitry Andric // shl (lshr X, C), C --> and X, C' 5390b57cec5SDimitry Andric if (*InnerShiftConst == OuterShAmt) 5400b57cec5SDimitry Andric return true; 5410b57cec5SDimitry Andric 5420b57cec5SDimitry Andric // If the 2nd shift is bigger than the 1st, we can fold: 5430b57cec5SDimitry Andric // lshr (shl X, C1), C2 --> and (shl X, C1 - C2), C3 5440b57cec5SDimitry Andric // shl (lshr X, C1), C2 --> and (lshr X, C1 - C2), C3 5450b57cec5SDimitry Andric // but it isn't profitable unless we know the and'd out bits are already zero. 5460b57cec5SDimitry Andric // Also, check that the inner shift is valid (less than the type width) or 5470b57cec5SDimitry Andric // we'll crash trying to produce the bit mask for the 'and'. 5480b57cec5SDimitry Andric unsigned TypeWidth = InnerShift->getType()->getScalarSizeInBits(); 5490b57cec5SDimitry Andric if (InnerShiftConst->ugt(OuterShAmt) && InnerShiftConst->ult(TypeWidth)) { 5500b57cec5SDimitry Andric unsigned InnerShAmt = InnerShiftConst->getZExtValue(); 5510b57cec5SDimitry Andric unsigned MaskShift = 5520b57cec5SDimitry Andric IsInnerShl ? TypeWidth - InnerShAmt : InnerShAmt - OuterShAmt; 5530b57cec5SDimitry Andric APInt Mask = APInt::getLowBitsSet(TypeWidth, OuterShAmt) << MaskShift; 5540b57cec5SDimitry Andric if (IC.MaskedValueIsZero(InnerShift->getOperand(0), Mask, 0, CxtI)) 5550b57cec5SDimitry Andric return true; 5560b57cec5SDimitry Andric } 5570b57cec5SDimitry Andric 5580b57cec5SDimitry Andric return false; 5590b57cec5SDimitry Andric } 5600b57cec5SDimitry Andric 5610b57cec5SDimitry Andric /// See if we can compute the specified value, but shifted logically to the left 5620b57cec5SDimitry Andric /// or right by some number of bits. This should return true if the expression 5630b57cec5SDimitry Andric /// can be computed for the same cost as the current expression tree. This is 5640b57cec5SDimitry Andric /// used to eliminate extraneous shifting from things like: 5650b57cec5SDimitry Andric /// %C = shl i128 %A, 64 5660b57cec5SDimitry Andric /// %D = shl i128 %B, 96 5670b57cec5SDimitry Andric /// %E = or i128 %C, %D 5680b57cec5SDimitry Andric /// %F = lshr i128 %E, 64 5690b57cec5SDimitry Andric /// where the client will ask if E can be computed shifted right by 64-bits. If 5700b57cec5SDimitry Andric /// this succeeds, getShiftedValue() will be called to produce the value. 5710b57cec5SDimitry Andric static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift, 572e8d8bef9SDimitry Andric InstCombinerImpl &IC, Instruction *CxtI) { 5735f757f3fSDimitry Andric // We can always evaluate immediate constants. 5745f757f3fSDimitry Andric if (match(V, m_ImmConstant())) 5750b57cec5SDimitry Andric return true; 5760b57cec5SDimitry Andric 5770b57cec5SDimitry Andric Instruction *I = dyn_cast<Instruction>(V); 5780b57cec5SDimitry Andric if (!I) return false; 5790b57cec5SDimitry Andric 5800b57cec5SDimitry Andric // We can't mutate something that has multiple uses: doing so would 5810b57cec5SDimitry Andric // require duplicating the instruction in general, which isn't profitable. 5820b57cec5SDimitry Andric if (!I->hasOneUse()) return false; 5830b57cec5SDimitry Andric 5840b57cec5SDimitry Andric switch (I->getOpcode()) { 5850b57cec5SDimitry Andric default: return false; 5860b57cec5SDimitry Andric case Instruction::And: 5870b57cec5SDimitry Andric case Instruction::Or: 5880b57cec5SDimitry Andric case Instruction::Xor: 5890b57cec5SDimitry Andric // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted. 5900b57cec5SDimitry Andric return canEvaluateShifted(I->getOperand(0), NumBits, IsLeftShift, IC, I) && 5910b57cec5SDimitry Andric canEvaluateShifted(I->getOperand(1), NumBits, IsLeftShift, IC, I); 5920b57cec5SDimitry Andric 5930b57cec5SDimitry Andric case Instruction::Shl: 5940b57cec5SDimitry Andric case Instruction::LShr: 5950b57cec5SDimitry Andric return canEvaluateShiftedShift(NumBits, IsLeftShift, I, IC, CxtI); 5960b57cec5SDimitry Andric 5970b57cec5SDimitry Andric case Instruction::Select: { 5980b57cec5SDimitry Andric SelectInst *SI = cast<SelectInst>(I); 5990b57cec5SDimitry Andric Value *TrueVal = SI->getTrueValue(); 6000b57cec5SDimitry Andric Value *FalseVal = SI->getFalseValue(); 6010b57cec5SDimitry Andric return canEvaluateShifted(TrueVal, NumBits, IsLeftShift, IC, SI) && 6020b57cec5SDimitry Andric canEvaluateShifted(FalseVal, NumBits, IsLeftShift, IC, SI); 6030b57cec5SDimitry Andric } 6040b57cec5SDimitry Andric case Instruction::PHI: { 6050b57cec5SDimitry Andric // We can change a phi if we can change all operands. Note that we never 6060b57cec5SDimitry Andric // get into trouble with cyclic PHIs here because we only consider 6070b57cec5SDimitry Andric // instructions with a single use. 6080b57cec5SDimitry Andric PHINode *PN = cast<PHINode>(I); 6090b57cec5SDimitry Andric for (Value *IncValue : PN->incoming_values()) 6100b57cec5SDimitry Andric if (!canEvaluateShifted(IncValue, NumBits, IsLeftShift, IC, PN)) 6110b57cec5SDimitry Andric return false; 6120b57cec5SDimitry Andric return true; 6130b57cec5SDimitry Andric } 614fcaf7f86SDimitry Andric case Instruction::Mul: { 615fcaf7f86SDimitry Andric const APInt *MulConst; 616fcaf7f86SDimitry Andric // We can fold (shr (mul X, -(1 << C)), C) -> (and (neg X), C`) 617fcaf7f86SDimitry Andric return !IsLeftShift && match(I->getOperand(1), m_APInt(MulConst)) && 61806c3fb27SDimitry Andric MulConst->isNegatedPowerOf2() && MulConst->countr_zero() == NumBits; 619fcaf7f86SDimitry Andric } 6200b57cec5SDimitry Andric } 6210b57cec5SDimitry Andric } 6220b57cec5SDimitry Andric 6230b57cec5SDimitry Andric /// Fold OuterShift (InnerShift X, C1), C2. 6240b57cec5SDimitry Andric /// See canEvaluateShiftedShift() for the constraints on these instructions. 6250b57cec5SDimitry Andric static Value *foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt, 6260b57cec5SDimitry Andric bool IsOuterShl, 6270b57cec5SDimitry Andric InstCombiner::BuilderTy &Builder) { 6280b57cec5SDimitry Andric bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl; 6290b57cec5SDimitry Andric Type *ShType = InnerShift->getType(); 6300b57cec5SDimitry Andric unsigned TypeWidth = ShType->getScalarSizeInBits(); 6310b57cec5SDimitry Andric 6320b57cec5SDimitry Andric // We only accept shifts-by-a-constant in canEvaluateShifted(). 6330b57cec5SDimitry Andric const APInt *C1; 6340b57cec5SDimitry Andric match(InnerShift->getOperand(1), m_APInt(C1)); 6350b57cec5SDimitry Andric unsigned InnerShAmt = C1->getZExtValue(); 6360b57cec5SDimitry Andric 6370b57cec5SDimitry Andric // Change the shift amount and clear the appropriate IR flags. 6380b57cec5SDimitry Andric auto NewInnerShift = [&](unsigned ShAmt) { 6390b57cec5SDimitry Andric InnerShift->setOperand(1, ConstantInt::get(ShType, ShAmt)); 6400b57cec5SDimitry Andric if (IsInnerShl) { 6410b57cec5SDimitry Andric InnerShift->setHasNoUnsignedWrap(false); 6420b57cec5SDimitry Andric InnerShift->setHasNoSignedWrap(false); 6430b57cec5SDimitry Andric } else { 6440b57cec5SDimitry Andric InnerShift->setIsExact(false); 6450b57cec5SDimitry Andric } 6460b57cec5SDimitry Andric return InnerShift; 6470b57cec5SDimitry Andric }; 6480b57cec5SDimitry Andric 6490b57cec5SDimitry Andric // Two logical shifts in the same direction: 6500b57cec5SDimitry Andric // shl (shl X, C1), C2 --> shl X, C1 + C2 6510b57cec5SDimitry Andric // lshr (lshr X, C1), C2 --> lshr X, C1 + C2 6520b57cec5SDimitry Andric if (IsInnerShl == IsOuterShl) { 6530b57cec5SDimitry Andric // If this is an oversized composite shift, then unsigned shifts get 0. 6540b57cec5SDimitry Andric if (InnerShAmt + OuterShAmt >= TypeWidth) 6550b57cec5SDimitry Andric return Constant::getNullValue(ShType); 6560b57cec5SDimitry Andric 6570b57cec5SDimitry Andric return NewInnerShift(InnerShAmt + OuterShAmt); 6580b57cec5SDimitry Andric } 6590b57cec5SDimitry Andric 6600b57cec5SDimitry Andric // Equal shift amounts in opposite directions become bitwise 'and': 6610b57cec5SDimitry Andric // lshr (shl X, C), C --> and X, C' 6620b57cec5SDimitry Andric // shl (lshr X, C), C --> and X, C' 6630b57cec5SDimitry Andric if (InnerShAmt == OuterShAmt) { 6640b57cec5SDimitry Andric APInt Mask = IsInnerShl 6650b57cec5SDimitry Andric ? APInt::getLowBitsSet(TypeWidth, TypeWidth - OuterShAmt) 6660b57cec5SDimitry Andric : APInt::getHighBitsSet(TypeWidth, TypeWidth - OuterShAmt); 6670b57cec5SDimitry Andric Value *And = Builder.CreateAnd(InnerShift->getOperand(0), 6680b57cec5SDimitry Andric ConstantInt::get(ShType, Mask)); 6690b57cec5SDimitry Andric if (auto *AndI = dyn_cast<Instruction>(And)) { 6700b57cec5SDimitry Andric AndI->moveBefore(InnerShift); 6710b57cec5SDimitry Andric AndI->takeName(InnerShift); 6720b57cec5SDimitry Andric } 6730b57cec5SDimitry Andric return And; 6740b57cec5SDimitry Andric } 6750b57cec5SDimitry Andric 6760b57cec5SDimitry Andric assert(InnerShAmt > OuterShAmt && 6770b57cec5SDimitry Andric "Unexpected opposite direction logical shift pair"); 6780b57cec5SDimitry Andric 6790b57cec5SDimitry Andric // In general, we would need an 'and' for this transform, but 6800b57cec5SDimitry Andric // canEvaluateShiftedShift() guarantees that the masked-off bits are not used. 6810b57cec5SDimitry Andric // lshr (shl X, C1), C2 --> shl X, C1 - C2 6820b57cec5SDimitry Andric // shl (lshr X, C1), C2 --> lshr X, C1 - C2 6830b57cec5SDimitry Andric return NewInnerShift(InnerShAmt - OuterShAmt); 6840b57cec5SDimitry Andric } 6850b57cec5SDimitry Andric 6860b57cec5SDimitry Andric /// When canEvaluateShifted() returns true for an expression, this function 6870b57cec5SDimitry Andric /// inserts the new computation that produces the shifted value. 6880b57cec5SDimitry Andric static Value *getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift, 689e8d8bef9SDimitry Andric InstCombinerImpl &IC, const DataLayout &DL) { 6900b57cec5SDimitry Andric // We can always evaluate constants shifted. 6910b57cec5SDimitry Andric if (Constant *C = dyn_cast<Constant>(V)) { 6920b57cec5SDimitry Andric if (isLeftShift) 6935ffd83dbSDimitry Andric return IC.Builder.CreateShl(C, NumBits); 6940b57cec5SDimitry Andric else 6955ffd83dbSDimitry Andric return IC.Builder.CreateLShr(C, NumBits); 6960b57cec5SDimitry Andric } 6970b57cec5SDimitry Andric 6980b57cec5SDimitry Andric Instruction *I = cast<Instruction>(V); 699e8d8bef9SDimitry Andric IC.addToWorklist(I); 7000b57cec5SDimitry Andric 7010b57cec5SDimitry Andric switch (I->getOpcode()) { 7020b57cec5SDimitry Andric default: llvm_unreachable("Inconsistency with CanEvaluateShifted"); 7030b57cec5SDimitry Andric case Instruction::And: 7040b57cec5SDimitry Andric case Instruction::Or: 7050b57cec5SDimitry Andric case Instruction::Xor: 7060b57cec5SDimitry Andric // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted. 7070b57cec5SDimitry Andric I->setOperand( 7080b57cec5SDimitry Andric 0, getShiftedValue(I->getOperand(0), NumBits, isLeftShift, IC, DL)); 7090b57cec5SDimitry Andric I->setOperand( 7100b57cec5SDimitry Andric 1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL)); 7110b57cec5SDimitry Andric return I; 7120b57cec5SDimitry Andric 7130b57cec5SDimitry Andric case Instruction::Shl: 7140b57cec5SDimitry Andric case Instruction::LShr: 7150b57cec5SDimitry Andric return foldShiftedShift(cast<BinaryOperator>(I), NumBits, isLeftShift, 7160b57cec5SDimitry Andric IC.Builder); 7170b57cec5SDimitry Andric 7180b57cec5SDimitry Andric case Instruction::Select: 7190b57cec5SDimitry Andric I->setOperand( 7200b57cec5SDimitry Andric 1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL)); 7210b57cec5SDimitry Andric I->setOperand( 7220b57cec5SDimitry Andric 2, getShiftedValue(I->getOperand(2), NumBits, isLeftShift, IC, DL)); 7230b57cec5SDimitry Andric return I; 7240b57cec5SDimitry Andric case Instruction::PHI: { 7250b57cec5SDimitry Andric // We can change a phi if we can change all operands. Note that we never 7260b57cec5SDimitry Andric // get into trouble with cyclic PHIs here because we only consider 7270b57cec5SDimitry Andric // instructions with a single use. 7280b57cec5SDimitry Andric PHINode *PN = cast<PHINode>(I); 7290b57cec5SDimitry Andric for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 7300b57cec5SDimitry Andric PN->setIncomingValue(i, getShiftedValue(PN->getIncomingValue(i), NumBits, 7310b57cec5SDimitry Andric isLeftShift, IC, DL)); 7320b57cec5SDimitry Andric return PN; 7330b57cec5SDimitry Andric } 734fcaf7f86SDimitry Andric case Instruction::Mul: { 735fcaf7f86SDimitry Andric assert(!isLeftShift && "Unexpected shift direction!"); 736fcaf7f86SDimitry Andric auto *Neg = BinaryOperator::CreateNeg(I->getOperand(0)); 7375f757f3fSDimitry Andric IC.InsertNewInstWith(Neg, I->getIterator()); 738fcaf7f86SDimitry Andric unsigned TypeWidth = I->getType()->getScalarSizeInBits(); 739fcaf7f86SDimitry Andric APInt Mask = APInt::getLowBitsSet(TypeWidth, TypeWidth - NumBits); 740fcaf7f86SDimitry Andric auto *And = BinaryOperator::CreateAnd(Neg, 741fcaf7f86SDimitry Andric ConstantInt::get(I->getType(), Mask)); 742fcaf7f86SDimitry Andric And->takeName(I); 7435f757f3fSDimitry Andric return IC.InsertNewInstWith(And, I->getIterator()); 744fcaf7f86SDimitry Andric } 7450b57cec5SDimitry Andric } 7460b57cec5SDimitry Andric } 7470b57cec5SDimitry Andric 7480b57cec5SDimitry Andric // If this is a bitwise operator or add with a constant RHS we might be able 7490b57cec5SDimitry Andric // to pull it through a shift. 7500b57cec5SDimitry Andric static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift, 7510b57cec5SDimitry Andric BinaryOperator *BO) { 7520b57cec5SDimitry Andric switch (BO->getOpcode()) { 7530b57cec5SDimitry Andric default: 7540b57cec5SDimitry Andric return false; // Do not perform transform! 7550b57cec5SDimitry Andric case Instruction::Add: 7560b57cec5SDimitry Andric return Shift.getOpcode() == Instruction::Shl; 7570b57cec5SDimitry Andric case Instruction::Or: 7580b57cec5SDimitry Andric case Instruction::And: 7590b57cec5SDimitry Andric return true; 760e8d8bef9SDimitry Andric case Instruction::Xor: 761e8d8bef9SDimitry Andric // Do not change a 'not' of logical shift because that would create a normal 762e8d8bef9SDimitry Andric // 'xor'. The 'not' is likely better for analysis, SCEV, and codegen. 763e8d8bef9SDimitry Andric return !(Shift.isLogicalShift() && match(BO, m_Not(m_Value()))); 7640b57cec5SDimitry Andric } 7650b57cec5SDimitry Andric } 7660b57cec5SDimitry Andric 76781ad6265SDimitry Andric Instruction *InstCombinerImpl::FoldShiftByConstant(Value *Op0, Constant *C1, 7680b57cec5SDimitry Andric BinaryOperator &I) { 76981ad6265SDimitry Andric // (C2 << X) << C1 --> (C2 << C1) << X 77081ad6265SDimitry Andric // (C2 >> X) >> C1 --> (C2 >> C1) >> X 77181ad6265SDimitry Andric Constant *C2; 77281ad6265SDimitry Andric Value *X; 773bdd1243dSDimitry Andric bool IsLeftShift = I.getOpcode() == Instruction::Shl; 774*0fca6ea1SDimitry Andric if (match(Op0, m_BinOp(I.getOpcode(), m_ImmConstant(C2), m_Value(X)))) { 775*0fca6ea1SDimitry Andric Instruction *R = BinaryOperator::Create( 776*0fca6ea1SDimitry Andric I.getOpcode(), Builder.CreateBinOp(I.getOpcode(), C2, C1), X); 777*0fca6ea1SDimitry Andric BinaryOperator *BO0 = cast<BinaryOperator>(Op0); 778*0fca6ea1SDimitry Andric if (IsLeftShift) { 779*0fca6ea1SDimitry Andric R->setHasNoUnsignedWrap(I.hasNoUnsignedWrap() && 780*0fca6ea1SDimitry Andric BO0->hasNoUnsignedWrap()); 781*0fca6ea1SDimitry Andric R->setHasNoSignedWrap(I.hasNoSignedWrap() && BO0->hasNoSignedWrap()); 782*0fca6ea1SDimitry Andric } else 783*0fca6ea1SDimitry Andric R->setIsExact(I.isExact() && BO0->isExact()); 784*0fca6ea1SDimitry Andric return R; 785*0fca6ea1SDimitry Andric } 786*0fca6ea1SDimitry Andric 787bdd1243dSDimitry Andric Type *Ty = I.getType(); 788bdd1243dSDimitry Andric unsigned TypeBits = Ty->getScalarSizeInBits(); 789bdd1243dSDimitry Andric 790bdd1243dSDimitry Andric // (X / +DivC) >> (Width - 1) --> ext (X <= -DivC) 791bdd1243dSDimitry Andric // (X / -DivC) >> (Width - 1) --> ext (X >= +DivC) 792bdd1243dSDimitry Andric const APInt *DivC; 793*0fca6ea1SDimitry Andric if (!IsLeftShift && match(C1, m_SpecificIntAllowPoison(TypeBits - 1)) && 794bdd1243dSDimitry Andric match(Op0, m_SDiv(m_Value(X), m_APInt(DivC))) && !DivC->isZero() && 795bdd1243dSDimitry Andric !DivC->isMinSignedValue()) { 796bdd1243dSDimitry Andric Constant *NegDivC = ConstantInt::get(Ty, -(*DivC)); 797bdd1243dSDimitry Andric ICmpInst::Predicate Pred = 798bdd1243dSDimitry Andric DivC->isNegative() ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_SLE; 799bdd1243dSDimitry Andric Value *Cmp = Builder.CreateICmp(Pred, X, NegDivC); 800bdd1243dSDimitry Andric auto ExtOpcode = (I.getOpcode() == Instruction::AShr) ? Instruction::SExt 801bdd1243dSDimitry Andric : Instruction::ZExt; 802bdd1243dSDimitry Andric return CastInst::Create(ExtOpcode, Cmp, Ty); 803bdd1243dSDimitry Andric } 804bdd1243dSDimitry Andric 8050b57cec5SDimitry Andric const APInt *Op1C; 80681ad6265SDimitry Andric if (!match(C1, m_APInt(Op1C))) 8070b57cec5SDimitry Andric return nullptr; 8080b57cec5SDimitry Andric 809bdd1243dSDimitry Andric assert(!Op1C->uge(TypeBits) && 810bdd1243dSDimitry Andric "Shift over the type width should have been removed already"); 811bdd1243dSDimitry Andric 8120b57cec5SDimitry Andric // See if we can propagate this shift into the input, this covers the trivial 8130b57cec5SDimitry Andric // cast of lshr(shl(x,c1),c2) as well as other more complex cases. 8140b57cec5SDimitry Andric if (I.getOpcode() != Instruction::AShr && 815349cc55cSDimitry Andric canEvaluateShifted(Op0, Op1C->getZExtValue(), IsLeftShift, *this, &I)) { 8160b57cec5SDimitry Andric LLVM_DEBUG( 8170b57cec5SDimitry Andric dbgs() << "ICE: GetShiftedValue propagating shift through expression" 8180b57cec5SDimitry Andric " to eliminate shift:\n IN: " 8190b57cec5SDimitry Andric << *Op0 << "\n SH: " << I << "\n"); 8200b57cec5SDimitry Andric 8210b57cec5SDimitry Andric return replaceInstUsesWith( 822349cc55cSDimitry Andric I, getShiftedValue(Op0, Op1C->getZExtValue(), IsLeftShift, *this, DL)); 8230b57cec5SDimitry Andric } 8240b57cec5SDimitry Andric 8250b57cec5SDimitry Andric if (Instruction *FoldedShift = foldBinOpIntoSelectOrPhi(I)) 8260b57cec5SDimitry Andric return FoldedShift; 8270b57cec5SDimitry Andric 828349cc55cSDimitry Andric if (!Op0->hasOneUse()) 829349cc55cSDimitry Andric return nullptr; 830e8d8bef9SDimitry Andric 831349cc55cSDimitry Andric if (auto *Op0BO = dyn_cast<BinaryOperator>(Op0)) { 8320b57cec5SDimitry Andric // If the operand is a bitwise operator with a constant RHS, and the 8330b57cec5SDimitry Andric // shift is the only use, we can pull it out of the shift. 8340b57cec5SDimitry Andric const APInt *Op0C; 8350b57cec5SDimitry Andric if (match(Op0BO->getOperand(1), m_APInt(Op0C))) { 8360b57cec5SDimitry Andric if (canShiftBinOpWithConstantRHS(I, Op0BO)) { 83781ad6265SDimitry Andric Value *NewRHS = 83881ad6265SDimitry Andric Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(1), C1); 8390b57cec5SDimitry Andric 8400b57cec5SDimitry Andric Value *NewShift = 84181ad6265SDimitry Andric Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), C1); 8420b57cec5SDimitry Andric NewShift->takeName(Op0BO); 8430b57cec5SDimitry Andric 844349cc55cSDimitry Andric return BinaryOperator::Create(Op0BO->getOpcode(), NewShift, NewRHS); 8450b57cec5SDimitry Andric } 8460b57cec5SDimitry Andric } 8470b57cec5SDimitry Andric } 8480b57cec5SDimitry Andric 8490b57cec5SDimitry Andric // If we have a select that conditionally executes some binary operator, 8500b57cec5SDimitry Andric // see if we can pull it the select and operator through the shift. 8510b57cec5SDimitry Andric // 8520b57cec5SDimitry Andric // For example, turning: 8530b57cec5SDimitry Andric // shl (select C, (add X, C1), X), C2 8540b57cec5SDimitry Andric // Into: 8550b57cec5SDimitry Andric // Y = shl X, C2 8560b57cec5SDimitry Andric // select C, (add Y, C1 << C2), Y 8570b57cec5SDimitry Andric Value *Cond; 8580b57cec5SDimitry Andric BinaryOperator *TBO; 8590b57cec5SDimitry Andric Value *FalseVal; 8600b57cec5SDimitry Andric if (match(Op0, m_Select(m_Value(Cond), m_OneUse(m_BinOp(TBO)), 8610b57cec5SDimitry Andric m_Value(FalseVal)))) { 8620b57cec5SDimitry Andric const APInt *C; 8630b57cec5SDimitry Andric if (!isa<Constant>(FalseVal) && TBO->getOperand(0) == FalseVal && 8640b57cec5SDimitry Andric match(TBO->getOperand(1), m_APInt(C)) && 8650b57cec5SDimitry Andric canShiftBinOpWithConstantRHS(I, TBO)) { 86681ad6265SDimitry Andric Value *NewRHS = 86781ad6265SDimitry Andric Builder.CreateBinOp(I.getOpcode(), TBO->getOperand(1), C1); 8680b57cec5SDimitry Andric 86981ad6265SDimitry Andric Value *NewShift = Builder.CreateBinOp(I.getOpcode(), FalseVal, C1); 870349cc55cSDimitry Andric Value *NewOp = Builder.CreateBinOp(TBO->getOpcode(), NewShift, NewRHS); 8710b57cec5SDimitry Andric return SelectInst::Create(Cond, NewOp, NewShift); 8720b57cec5SDimitry Andric } 8730b57cec5SDimitry Andric } 8740b57cec5SDimitry Andric 8750b57cec5SDimitry Andric BinaryOperator *FBO; 8760b57cec5SDimitry Andric Value *TrueVal; 8770b57cec5SDimitry Andric if (match(Op0, m_Select(m_Value(Cond), m_Value(TrueVal), 8780b57cec5SDimitry Andric m_OneUse(m_BinOp(FBO))))) { 8790b57cec5SDimitry Andric const APInt *C; 8800b57cec5SDimitry Andric if (!isa<Constant>(TrueVal) && FBO->getOperand(0) == TrueVal && 8810b57cec5SDimitry Andric match(FBO->getOperand(1), m_APInt(C)) && 8820b57cec5SDimitry Andric canShiftBinOpWithConstantRHS(I, FBO)) { 88381ad6265SDimitry Andric Value *NewRHS = 88481ad6265SDimitry Andric Builder.CreateBinOp(I.getOpcode(), FBO->getOperand(1), C1); 8850b57cec5SDimitry Andric 88681ad6265SDimitry Andric Value *NewShift = Builder.CreateBinOp(I.getOpcode(), TrueVal, C1); 887349cc55cSDimitry Andric Value *NewOp = Builder.CreateBinOp(FBO->getOpcode(), NewShift, NewRHS); 8880b57cec5SDimitry Andric return SelectInst::Create(Cond, NewShift, NewOp); 8890b57cec5SDimitry Andric } 8900b57cec5SDimitry Andric } 8910b57cec5SDimitry Andric 8920b57cec5SDimitry Andric return nullptr; 8930b57cec5SDimitry Andric } 8940b57cec5SDimitry Andric 895bdd1243dSDimitry Andric // Tries to perform 896bdd1243dSDimitry Andric // (lshr (add (zext X), (zext Y)), K) 897bdd1243dSDimitry Andric // -> (icmp ult (add X, Y), X) 898bdd1243dSDimitry Andric // where 899bdd1243dSDimitry Andric // - The add's operands are zexts from a K-bits integer to a bigger type. 900bdd1243dSDimitry Andric // - The add is only used by the shr, or by iK (or narrower) truncates. 901bdd1243dSDimitry Andric // - The lshr type has more than 2 bits (other types are boolean math). 902bdd1243dSDimitry Andric // - K > 1 903bdd1243dSDimitry Andric // note that 904bdd1243dSDimitry Andric // - The resulting add cannot have nuw/nsw, else on overflow we get a 905bdd1243dSDimitry Andric // poison value and the transform isn't legal anymore. 906bdd1243dSDimitry Andric Instruction *InstCombinerImpl::foldLShrOverflowBit(BinaryOperator &I) { 907bdd1243dSDimitry Andric assert(I.getOpcode() == Instruction::LShr); 908bdd1243dSDimitry Andric 909bdd1243dSDimitry Andric Value *Add = I.getOperand(0); 910bdd1243dSDimitry Andric Value *ShiftAmt = I.getOperand(1); 911bdd1243dSDimitry Andric Type *Ty = I.getType(); 912bdd1243dSDimitry Andric 913bdd1243dSDimitry Andric if (Ty->getScalarSizeInBits() < 3) 914bdd1243dSDimitry Andric return nullptr; 915bdd1243dSDimitry Andric 916bdd1243dSDimitry Andric const APInt *ShAmtAPInt = nullptr; 917bdd1243dSDimitry Andric Value *X = nullptr, *Y = nullptr; 918bdd1243dSDimitry Andric if (!match(ShiftAmt, m_APInt(ShAmtAPInt)) || 919bdd1243dSDimitry Andric !match(Add, 920bdd1243dSDimitry Andric m_Add(m_OneUse(m_ZExt(m_Value(X))), m_OneUse(m_ZExt(m_Value(Y)))))) 921bdd1243dSDimitry Andric return nullptr; 922bdd1243dSDimitry Andric 923bdd1243dSDimitry Andric const unsigned ShAmt = ShAmtAPInt->getZExtValue(); 924bdd1243dSDimitry Andric if (ShAmt == 1) 925bdd1243dSDimitry Andric return nullptr; 926bdd1243dSDimitry Andric 927bdd1243dSDimitry Andric // X/Y are zexts from `ShAmt`-sized ints. 928bdd1243dSDimitry Andric if (X->getType()->getScalarSizeInBits() != ShAmt || 929bdd1243dSDimitry Andric Y->getType()->getScalarSizeInBits() != ShAmt) 930bdd1243dSDimitry Andric return nullptr; 931bdd1243dSDimitry Andric 932bdd1243dSDimitry Andric // Make sure that `Add` is only used by `I` and `ShAmt`-truncates. 933bdd1243dSDimitry Andric if (!Add->hasOneUse()) { 934bdd1243dSDimitry Andric for (User *U : Add->users()) { 935bdd1243dSDimitry Andric if (U == &I) 936bdd1243dSDimitry Andric continue; 937bdd1243dSDimitry Andric 938bdd1243dSDimitry Andric TruncInst *Trunc = dyn_cast<TruncInst>(U); 939bdd1243dSDimitry Andric if (!Trunc || Trunc->getType()->getScalarSizeInBits() > ShAmt) 940bdd1243dSDimitry Andric return nullptr; 941bdd1243dSDimitry Andric } 942bdd1243dSDimitry Andric } 943bdd1243dSDimitry Andric 944bdd1243dSDimitry Andric // Insert at Add so that the newly created `NarrowAdd` will dominate it's 945bdd1243dSDimitry Andric // users (i.e. `Add`'s users). 946bdd1243dSDimitry Andric Instruction *AddInst = cast<Instruction>(Add); 947bdd1243dSDimitry Andric Builder.SetInsertPoint(AddInst); 948bdd1243dSDimitry Andric 949bdd1243dSDimitry Andric Value *NarrowAdd = Builder.CreateAdd(X, Y, "add.narrowed"); 950bdd1243dSDimitry Andric Value *Overflow = 951bdd1243dSDimitry Andric Builder.CreateICmpULT(NarrowAdd, X, "add.narrowed.overflow"); 952bdd1243dSDimitry Andric 953bdd1243dSDimitry Andric // Replace the uses of the original add with a zext of the 954bdd1243dSDimitry Andric // NarrowAdd's result. Note that all users at this stage are known to 955bdd1243dSDimitry Andric // be ShAmt-sized truncs, or the lshr itself. 95606c3fb27SDimitry Andric if (!Add->hasOneUse()) { 957bdd1243dSDimitry Andric replaceInstUsesWith(*AddInst, Builder.CreateZExt(NarrowAdd, Ty)); 95806c3fb27SDimitry Andric eraseInstFromFunction(*AddInst); 95906c3fb27SDimitry Andric } 960bdd1243dSDimitry Andric 961bdd1243dSDimitry Andric // Replace the LShr with a zext of the overflow check. 962bdd1243dSDimitry Andric return new ZExtInst(Overflow, Ty); 963bdd1243dSDimitry Andric } 964bdd1243dSDimitry Andric 9655f757f3fSDimitry Andric // Try to set nuw/nsw flags on shl or exact flag on lshr/ashr using knownbits. 9665f757f3fSDimitry Andric static bool setShiftFlags(BinaryOperator &I, const SimplifyQuery &Q) { 9675f757f3fSDimitry Andric assert(I.isShift() && "Expected a shift as input"); 9685f757f3fSDimitry Andric // We already have all the flags. 9695f757f3fSDimitry Andric if (I.getOpcode() == Instruction::Shl) { 9705f757f3fSDimitry Andric if (I.hasNoUnsignedWrap() && I.hasNoSignedWrap()) 9715f757f3fSDimitry Andric return false; 9725f757f3fSDimitry Andric } else { 9735f757f3fSDimitry Andric if (I.isExact()) 9745f757f3fSDimitry Andric return false; 9755f757f3fSDimitry Andric 9765f757f3fSDimitry Andric // shr (shl X, Y), Y 9775f757f3fSDimitry Andric if (match(I.getOperand(0), m_Shl(m_Value(), m_Specific(I.getOperand(1))))) { 9785f757f3fSDimitry Andric I.setIsExact(); 9795f757f3fSDimitry Andric return true; 9805f757f3fSDimitry Andric } 9815f757f3fSDimitry Andric } 9825f757f3fSDimitry Andric 9835f757f3fSDimitry Andric // Compute what we know about shift count. 9845f757f3fSDimitry Andric KnownBits KnownCnt = computeKnownBits(I.getOperand(1), /* Depth */ 0, Q); 9855f757f3fSDimitry Andric unsigned BitWidth = KnownCnt.getBitWidth(); 9865f757f3fSDimitry Andric // Since shift produces a poison value if RHS is equal to or larger than the 9875f757f3fSDimitry Andric // bit width, we can safely assume that RHS is less than the bit width. 9885f757f3fSDimitry Andric uint64_t MaxCnt = KnownCnt.getMaxValue().getLimitedValue(BitWidth - 1); 9895f757f3fSDimitry Andric 9905f757f3fSDimitry Andric KnownBits KnownAmt = computeKnownBits(I.getOperand(0), /* Depth */ 0, Q); 9915f757f3fSDimitry Andric bool Changed = false; 9925f757f3fSDimitry Andric 9935f757f3fSDimitry Andric if (I.getOpcode() == Instruction::Shl) { 9945f757f3fSDimitry Andric // If we have as many leading zeros than maximum shift cnt we have nuw. 9955f757f3fSDimitry Andric if (!I.hasNoUnsignedWrap() && MaxCnt <= KnownAmt.countMinLeadingZeros()) { 9965f757f3fSDimitry Andric I.setHasNoUnsignedWrap(); 9975f757f3fSDimitry Andric Changed = true; 9985f757f3fSDimitry Andric } 9995f757f3fSDimitry Andric // If we have more sign bits than maximum shift cnt we have nsw. 10005f757f3fSDimitry Andric if (!I.hasNoSignedWrap()) { 10015f757f3fSDimitry Andric if (MaxCnt < KnownAmt.countMinSignBits() || 10025f757f3fSDimitry Andric MaxCnt < ComputeNumSignBits(I.getOperand(0), Q.DL, /*Depth*/ 0, Q.AC, 10035f757f3fSDimitry Andric Q.CxtI, Q.DT)) { 10045f757f3fSDimitry Andric I.setHasNoSignedWrap(); 10055f757f3fSDimitry Andric Changed = true; 10065f757f3fSDimitry Andric } 10075f757f3fSDimitry Andric } 10085f757f3fSDimitry Andric return Changed; 10095f757f3fSDimitry Andric } 10105f757f3fSDimitry Andric 10115f757f3fSDimitry Andric // If we have at least as many trailing zeros as maximum count then we have 10125f757f3fSDimitry Andric // exact. 10135f757f3fSDimitry Andric Changed = MaxCnt <= KnownAmt.countMinTrailingZeros(); 10145f757f3fSDimitry Andric I.setIsExact(Changed); 10155f757f3fSDimitry Andric 10165f757f3fSDimitry Andric return Changed; 10175f757f3fSDimitry Andric } 10185f757f3fSDimitry Andric 1019e8d8bef9SDimitry Andric Instruction *InstCombinerImpl::visitShl(BinaryOperator &I) { 10208bcb0991SDimitry Andric const SimplifyQuery Q = SQ.getWithInstruction(&I); 10218bcb0991SDimitry Andric 102281ad6265SDimitry Andric if (Value *V = simplifyShlInst(I.getOperand(0), I.getOperand(1), 10238bcb0991SDimitry Andric I.hasNoSignedWrap(), I.hasNoUnsignedWrap(), Q)) 10240b57cec5SDimitry Andric return replaceInstUsesWith(I, V); 10250b57cec5SDimitry Andric 10260b57cec5SDimitry Andric if (Instruction *X = foldVectorBinop(I)) 10270b57cec5SDimitry Andric return X; 10280b57cec5SDimitry Andric 10290b57cec5SDimitry Andric if (Instruction *V = commonShiftTransforms(I)) 10300b57cec5SDimitry Andric return V; 10310b57cec5SDimitry Andric 10328bcb0991SDimitry Andric if (Instruction *V = dropRedundantMaskingOfLeftShiftInput(&I, Q, Builder)) 10338bcb0991SDimitry Andric return V; 10348bcb0991SDimitry Andric 10350b57cec5SDimitry Andric Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 10360b57cec5SDimitry Andric Type *Ty = I.getType(); 10370b57cec5SDimitry Andric unsigned BitWidth = Ty->getScalarSizeInBits(); 10380b57cec5SDimitry Andric 1039349cc55cSDimitry Andric const APInt *C; 1040349cc55cSDimitry Andric if (match(Op1, m_APInt(C))) { 1041349cc55cSDimitry Andric unsigned ShAmtC = C->getZExtValue(); 10420b57cec5SDimitry Andric 1043349cc55cSDimitry Andric // shl (zext X), C --> zext (shl X, C) 10440b57cec5SDimitry Andric // This is only valid if X would have zeros shifted out. 10450b57cec5SDimitry Andric Value *X; 10468bcb0991SDimitry Andric if (match(Op0, m_OneUse(m_ZExt(m_Value(X))))) { 10470b57cec5SDimitry Andric unsigned SrcWidth = X->getType()->getScalarSizeInBits(); 1048349cc55cSDimitry Andric if (ShAmtC < SrcWidth && 1049349cc55cSDimitry Andric MaskedValueIsZero(X, APInt::getHighBitsSet(SrcWidth, ShAmtC), 0, &I)) 1050349cc55cSDimitry Andric return new ZExtInst(Builder.CreateShl(X, ShAmtC), Ty); 10510b57cec5SDimitry Andric } 10520b57cec5SDimitry Andric 10530b57cec5SDimitry Andric // (X >> C) << C --> X & (-1 << C) 10540b57cec5SDimitry Andric if (match(Op0, m_Shr(m_Value(X), m_Specific(Op1)))) { 1055349cc55cSDimitry Andric APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC)); 10560b57cec5SDimitry Andric return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask)); 10570b57cec5SDimitry Andric } 10580b57cec5SDimitry Andric 1059349cc55cSDimitry Andric const APInt *C1; 1060349cc55cSDimitry Andric if (match(Op0, m_Exact(m_Shr(m_Value(X), m_APInt(C1)))) && 1061349cc55cSDimitry Andric C1->ult(BitWidth)) { 1062349cc55cSDimitry Andric unsigned ShrAmt = C1->getZExtValue(); 1063349cc55cSDimitry Andric if (ShrAmt < ShAmtC) { 1064349cc55cSDimitry Andric // If C1 < C: (X >>?,exact C1) << C --> X << (C - C1) 1065349cc55cSDimitry Andric Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShrAmt); 10660b57cec5SDimitry Andric auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff); 10675f757f3fSDimitry Andric NewShl->setHasNoUnsignedWrap( 10685f757f3fSDimitry Andric I.hasNoUnsignedWrap() || 10695f757f3fSDimitry Andric (ShrAmt && 10705f757f3fSDimitry Andric cast<Instruction>(Op0)->getOpcode() == Instruction::LShr && 10715f757f3fSDimitry Andric I.hasNoSignedWrap())); 10720b57cec5SDimitry Andric NewShl->setHasNoSignedWrap(I.hasNoSignedWrap()); 10730b57cec5SDimitry Andric return NewShl; 10740b57cec5SDimitry Andric } 1075349cc55cSDimitry Andric if (ShrAmt > ShAmtC) { 1076349cc55cSDimitry Andric // If C1 > C: (X >>?exact C1) << C --> X >>?exact (C1 - C) 1077349cc55cSDimitry Andric Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmtC); 10780b57cec5SDimitry Andric auto *NewShr = BinaryOperator::Create( 10790b57cec5SDimitry Andric cast<BinaryOperator>(Op0)->getOpcode(), X, ShiftDiff); 10800b57cec5SDimitry Andric NewShr->setIsExact(true); 10810b57cec5SDimitry Andric return NewShr; 10820b57cec5SDimitry Andric } 10830b57cec5SDimitry Andric } 10840b57cec5SDimitry Andric 1085349cc55cSDimitry Andric if (match(Op0, m_OneUse(m_Shr(m_Value(X), m_APInt(C1)))) && 1086349cc55cSDimitry Andric C1->ult(BitWidth)) { 1087349cc55cSDimitry Andric unsigned ShrAmt = C1->getZExtValue(); 1088349cc55cSDimitry Andric if (ShrAmt < ShAmtC) { 1089349cc55cSDimitry Andric // If C1 < C: (X >>? C1) << C --> (X << (C - C1)) & (-1 << C) 1090349cc55cSDimitry Andric Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShrAmt); 1091e8d8bef9SDimitry Andric auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff); 10925f757f3fSDimitry Andric NewShl->setHasNoUnsignedWrap( 10935f757f3fSDimitry Andric I.hasNoUnsignedWrap() || 10945f757f3fSDimitry Andric (ShrAmt && 10955f757f3fSDimitry Andric cast<Instruction>(Op0)->getOpcode() == Instruction::LShr && 10965f757f3fSDimitry Andric I.hasNoSignedWrap())); 1097e8d8bef9SDimitry Andric NewShl->setHasNoSignedWrap(I.hasNoSignedWrap()); 1098e8d8bef9SDimitry Andric Builder.Insert(NewShl); 1099349cc55cSDimitry Andric APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC)); 1100e8d8bef9SDimitry Andric return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask)); 1101e8d8bef9SDimitry Andric } 1102349cc55cSDimitry Andric if (ShrAmt > ShAmtC) { 1103349cc55cSDimitry Andric // If C1 > C: (X >>? C1) << C --> (X >>? (C1 - C)) & (-1 << C) 1104349cc55cSDimitry Andric Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmtC); 1105e8d8bef9SDimitry Andric auto *OldShr = cast<BinaryOperator>(Op0); 1106e8d8bef9SDimitry Andric auto *NewShr = 1107e8d8bef9SDimitry Andric BinaryOperator::Create(OldShr->getOpcode(), X, ShiftDiff); 1108e8d8bef9SDimitry Andric NewShr->setIsExact(OldShr->isExact()); 1109e8d8bef9SDimitry Andric Builder.Insert(NewShr); 1110349cc55cSDimitry Andric APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC)); 1111e8d8bef9SDimitry Andric return BinaryOperator::CreateAnd(NewShr, ConstantInt::get(Ty, Mask)); 1112e8d8bef9SDimitry Andric } 1113e8d8bef9SDimitry Andric } 1114e8d8bef9SDimitry Andric 1115349cc55cSDimitry Andric // Similar to above, but look through an intermediate trunc instruction. 1116349cc55cSDimitry Andric BinaryOperator *Shr; 1117349cc55cSDimitry Andric if (match(Op0, m_OneUse(m_Trunc(m_OneUse(m_BinOp(Shr))))) && 1118349cc55cSDimitry Andric match(Shr, m_Shr(m_Value(X), m_APInt(C1)))) { 1119349cc55cSDimitry Andric // The larger shift direction survives through the transform. 1120349cc55cSDimitry Andric unsigned ShrAmtC = C1->getZExtValue(); 1121349cc55cSDimitry Andric unsigned ShDiff = ShrAmtC > ShAmtC ? ShrAmtC - ShAmtC : ShAmtC - ShrAmtC; 1122349cc55cSDimitry Andric Constant *ShiftDiffC = ConstantInt::get(X->getType(), ShDiff); 1123349cc55cSDimitry Andric auto ShiftOpc = ShrAmtC > ShAmtC ? Shr->getOpcode() : Instruction::Shl; 1124349cc55cSDimitry Andric 1125349cc55cSDimitry Andric // If C1 > C: 1126349cc55cSDimitry Andric // (trunc (X >> C1)) << C --> (trunc (X >> (C1 - C))) && (-1 << C) 1127349cc55cSDimitry Andric // If C > C1: 1128349cc55cSDimitry Andric // (trunc (X >> C1)) << C --> (trunc (X << (C - C1))) && (-1 << C) 1129349cc55cSDimitry Andric Value *NewShift = Builder.CreateBinOp(ShiftOpc, X, ShiftDiffC, "sh.diff"); 1130349cc55cSDimitry Andric Value *Trunc = Builder.CreateTrunc(NewShift, Ty, "tr.sh.diff"); 1131349cc55cSDimitry Andric APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC)); 1132349cc55cSDimitry Andric return BinaryOperator::CreateAnd(Trunc, ConstantInt::get(Ty, Mask)); 1133349cc55cSDimitry Andric } 1134349cc55cSDimitry Andric 1135349cc55cSDimitry Andric // If we have an opposite shift by the same amount, we may be able to 1136349cc55cSDimitry Andric // reorder binops and shifts to eliminate math/logic. 1137349cc55cSDimitry Andric auto isSuitableBinOpcode = [](Instruction::BinaryOps BinOpcode) { 1138349cc55cSDimitry Andric switch (BinOpcode) { 1139349cc55cSDimitry Andric default: 1140349cc55cSDimitry Andric return false; 1141349cc55cSDimitry Andric case Instruction::Add: 1142349cc55cSDimitry Andric case Instruction::And: 1143349cc55cSDimitry Andric case Instruction::Or: 1144349cc55cSDimitry Andric case Instruction::Xor: 1145349cc55cSDimitry Andric case Instruction::Sub: 1146349cc55cSDimitry Andric // NOTE: Sub is not commutable and the tranforms below may not be valid 1147349cc55cSDimitry Andric // when the shift-right is operand 1 (RHS) of the sub. 1148349cc55cSDimitry Andric return true; 1149349cc55cSDimitry Andric } 1150349cc55cSDimitry Andric }; 1151349cc55cSDimitry Andric BinaryOperator *Op0BO; 1152349cc55cSDimitry Andric if (match(Op0, m_OneUse(m_BinOp(Op0BO))) && 1153349cc55cSDimitry Andric isSuitableBinOpcode(Op0BO->getOpcode())) { 1154349cc55cSDimitry Andric // Commute so shift-right is on LHS of the binop. 1155349cc55cSDimitry Andric // (Y bop (X >> C)) << C -> ((X >> C) bop Y) << C 1156349cc55cSDimitry Andric // (Y bop ((X >> C) & CC)) << C -> (((X >> C) & CC) bop Y) << C 1157349cc55cSDimitry Andric Value *Shr = Op0BO->getOperand(0); 1158349cc55cSDimitry Andric Value *Y = Op0BO->getOperand(1); 1159349cc55cSDimitry Andric Value *X; 1160349cc55cSDimitry Andric const APInt *CC; 1161349cc55cSDimitry Andric if (Op0BO->isCommutative() && Y->hasOneUse() && 1162349cc55cSDimitry Andric (match(Y, m_Shr(m_Value(), m_Specific(Op1))) || 1163349cc55cSDimitry Andric match(Y, m_And(m_OneUse(m_Shr(m_Value(), m_Specific(Op1))), 1164349cc55cSDimitry Andric m_APInt(CC))))) 1165349cc55cSDimitry Andric std::swap(Shr, Y); 1166349cc55cSDimitry Andric 1167349cc55cSDimitry Andric // ((X >> C) bop Y) << C -> (X bop (Y << C)) & (~0 << C) 1168349cc55cSDimitry Andric if (match(Shr, m_OneUse(m_Shr(m_Value(X), m_Specific(Op1))))) { 1169349cc55cSDimitry Andric // Y << C 1170349cc55cSDimitry Andric Value *YS = Builder.CreateShl(Y, Op1, Op0BO->getName()); 1171349cc55cSDimitry Andric // (X bop (Y << C)) 1172349cc55cSDimitry Andric Value *B = 1173349cc55cSDimitry Andric Builder.CreateBinOp(Op0BO->getOpcode(), X, YS, Shr->getName()); 1174349cc55cSDimitry Andric unsigned Op1Val = C->getLimitedValue(BitWidth); 1175349cc55cSDimitry Andric APInt Bits = APInt::getHighBitsSet(BitWidth, BitWidth - Op1Val); 1176349cc55cSDimitry Andric Constant *Mask = ConstantInt::get(Ty, Bits); 1177349cc55cSDimitry Andric return BinaryOperator::CreateAnd(B, Mask); 1178349cc55cSDimitry Andric } 1179349cc55cSDimitry Andric 1180349cc55cSDimitry Andric // (((X >> C) & CC) bop Y) << C -> (X & (CC << C)) bop (Y << C) 1181349cc55cSDimitry Andric if (match(Shr, 1182349cc55cSDimitry Andric m_OneUse(m_And(m_OneUse(m_Shr(m_Value(X), m_Specific(Op1))), 1183349cc55cSDimitry Andric m_APInt(CC))))) { 1184349cc55cSDimitry Andric // Y << C 1185349cc55cSDimitry Andric Value *YS = Builder.CreateShl(Y, Op1, Op0BO->getName()); 1186349cc55cSDimitry Andric // X & (CC << C) 1187349cc55cSDimitry Andric Value *M = Builder.CreateAnd(X, ConstantInt::get(Ty, CC->shl(*C)), 1188349cc55cSDimitry Andric X->getName() + ".mask"); 1189*0fca6ea1SDimitry Andric auto *NewOp = BinaryOperator::Create(Op0BO->getOpcode(), M, YS); 1190*0fca6ea1SDimitry Andric if (auto *Disjoint = dyn_cast<PossiblyDisjointInst>(Op0BO); 1191*0fca6ea1SDimitry Andric Disjoint && Disjoint->isDisjoint()) 1192*0fca6ea1SDimitry Andric cast<PossiblyDisjointInst>(NewOp)->setIsDisjoint(true); 1193*0fca6ea1SDimitry Andric return NewOp; 1194349cc55cSDimitry Andric } 1195349cc55cSDimitry Andric } 1196349cc55cSDimitry Andric 1197349cc55cSDimitry Andric // (C1 - X) << C --> (C1 << C) - (X << C) 1198349cc55cSDimitry Andric if (match(Op0, m_OneUse(m_Sub(m_APInt(C1), m_Value(X))))) { 1199349cc55cSDimitry Andric Constant *NewLHS = ConstantInt::get(Ty, C1->shl(*C)); 1200349cc55cSDimitry Andric Value *NewShift = Builder.CreateShl(X, Op1); 1201349cc55cSDimitry Andric return BinaryOperator::CreateSub(NewLHS, NewShift); 1202349cc55cSDimitry Andric } 12030b57cec5SDimitry Andric } 12040b57cec5SDimitry Andric 12055f757f3fSDimitry Andric if (setShiftFlags(I, Q)) 12060b57cec5SDimitry Andric return &I; 12070b57cec5SDimitry Andric 12080b57cec5SDimitry Andric // Transform (x >> y) << y to x & (-1 << y) 12090b57cec5SDimitry Andric // Valid for any type of right-shift. 12100b57cec5SDimitry Andric Value *X; 12110b57cec5SDimitry Andric if (match(Op0, m_OneUse(m_Shr(m_Value(X), m_Specific(Op1))))) { 12120b57cec5SDimitry Andric Constant *AllOnes = ConstantInt::getAllOnesValue(Ty); 12130b57cec5SDimitry Andric Value *Mask = Builder.CreateShl(AllOnes, Op1); 12140b57cec5SDimitry Andric return BinaryOperator::CreateAnd(Mask, X); 12150b57cec5SDimitry Andric } 12160b57cec5SDimitry Andric 1217*0fca6ea1SDimitry Andric // Transform (-1 >> y) << y to -1 << y 1218*0fca6ea1SDimitry Andric if (match(Op0, m_LShr(m_AllOnes(), m_Specific(Op1)))) { 1219*0fca6ea1SDimitry Andric Constant *AllOnes = ConstantInt::getAllOnesValue(Ty); 1220*0fca6ea1SDimitry Andric return BinaryOperator::CreateShl(AllOnes, Op1); 1221*0fca6ea1SDimitry Andric } 1222*0fca6ea1SDimitry Andric 12230b57cec5SDimitry Andric Constant *C1; 1224*0fca6ea1SDimitry Andric if (match(Op1, m_ImmConstant(C1))) { 12250b57cec5SDimitry Andric Constant *C2; 12260b57cec5SDimitry Andric Value *X; 12270b57cec5SDimitry Andric // (X * C2) << C1 --> X * (C2 << C1) 1228*0fca6ea1SDimitry Andric if (match(Op0, m_Mul(m_Value(X), m_ImmConstant(C2)))) 1229*0fca6ea1SDimitry Andric return BinaryOperator::CreateMul(X, Builder.CreateShl(C2, C1)); 12308bcb0991SDimitry Andric 12318bcb0991SDimitry Andric // shl (zext i1 X), C1 --> select (X, 1 << C1, 0) 12328bcb0991SDimitry Andric if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) { 1233*0fca6ea1SDimitry Andric auto *NewC = Builder.CreateShl(ConstantInt::get(Ty, 1), C1); 12348bcb0991SDimitry Andric return SelectInst::Create(X, NewC, ConstantInt::getNullValue(Ty)); 12358bcb0991SDimitry Andric } 12360b57cec5SDimitry Andric } 12370b57cec5SDimitry Andric 1238bdd1243dSDimitry Andric if (match(Op0, m_One())) { 12390b57cec5SDimitry Andric // (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1 1240bdd1243dSDimitry Andric if (match(Op1, m_Sub(m_SpecificInt(BitWidth - 1), m_Value(X)))) 12410b57cec5SDimitry Andric return BinaryOperator::CreateLShr( 12420b57cec5SDimitry Andric ConstantInt::get(Ty, APInt::getSignMask(BitWidth)), X); 12430b57cec5SDimitry Andric 124406c3fb27SDimitry Andric // Canonicalize "extract lowest set bit" using cttz to and-with-negate: 124506c3fb27SDimitry Andric // 1 << (cttz X) --> -X & X 124606c3fb27SDimitry Andric if (match(Op1, 124706c3fb27SDimitry Andric m_OneUse(m_Intrinsic<Intrinsic::cttz>(m_Value(X), m_Value())))) { 124806c3fb27SDimitry Andric Value *NegX = Builder.CreateNeg(X, "neg"); 124906c3fb27SDimitry Andric return BinaryOperator::CreateAnd(NegX, X); 125006c3fb27SDimitry Andric } 1251bdd1243dSDimitry Andric } 1252bdd1243dSDimitry Andric 12530b57cec5SDimitry Andric return nullptr; 12540b57cec5SDimitry Andric } 12550b57cec5SDimitry Andric 1256e8d8bef9SDimitry Andric Instruction *InstCombinerImpl::visitLShr(BinaryOperator &I) { 125781ad6265SDimitry Andric if (Value *V = simplifyLShrInst(I.getOperand(0), I.getOperand(1), I.isExact(), 12580b57cec5SDimitry Andric SQ.getWithInstruction(&I))) 12590b57cec5SDimitry Andric return replaceInstUsesWith(I, V); 12600b57cec5SDimitry Andric 12610b57cec5SDimitry Andric if (Instruction *X = foldVectorBinop(I)) 12620b57cec5SDimitry Andric return X; 12630b57cec5SDimitry Andric 12640b57cec5SDimitry Andric if (Instruction *R = commonShiftTransforms(I)) 12650b57cec5SDimitry Andric return R; 12660b57cec5SDimitry Andric 12670b57cec5SDimitry Andric Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 12680b57cec5SDimitry Andric Type *Ty = I.getType(); 1269bdd1243dSDimitry Andric Value *X; 1270349cc55cSDimitry Andric const APInt *C; 1271bdd1243dSDimitry Andric unsigned BitWidth = Ty->getScalarSizeInBits(); 1272bdd1243dSDimitry Andric 1273bdd1243dSDimitry Andric // (iN (~X) u>> (N - 1)) --> zext (X > -1) 1274bdd1243dSDimitry Andric if (match(Op0, m_OneUse(m_Not(m_Value(X)))) && 1275*0fca6ea1SDimitry Andric match(Op1, m_SpecificIntAllowPoison(BitWidth - 1))) 1276bdd1243dSDimitry Andric return new ZExtInst(Builder.CreateIsNotNeg(X, "isnotneg"), Ty); 1277bdd1243dSDimitry Andric 1278*0fca6ea1SDimitry Andric // ((X << nuw Z) sub nuw Y) >>u exact Z --> X sub nuw (Y >>u exact Z) 1279*0fca6ea1SDimitry Andric Value *Y; 1280*0fca6ea1SDimitry Andric if (I.isExact() && 1281*0fca6ea1SDimitry Andric match(Op0, m_OneUse(m_NUWSub(m_NUWShl(m_Value(X), m_Specific(Op1)), 1282*0fca6ea1SDimitry Andric m_Value(Y))))) { 1283*0fca6ea1SDimitry Andric Value *NewLshr = Builder.CreateLShr(Y, Op1, "", /*isExact=*/true); 1284*0fca6ea1SDimitry Andric auto *NewSub = BinaryOperator::CreateNUWSub(X, NewLshr); 1285*0fca6ea1SDimitry Andric NewSub->setHasNoSignedWrap( 1286*0fca6ea1SDimitry Andric cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap()); 1287*0fca6ea1SDimitry Andric return NewSub; 1288*0fca6ea1SDimitry Andric } 1289*0fca6ea1SDimitry Andric 1290*0fca6ea1SDimitry Andric // Fold (X + Y) / 2 --> (X & Y) iff (X u<= 1) && (Y u<= 1) 1291*0fca6ea1SDimitry Andric if (match(Op0, m_Add(m_Value(X), m_Value(Y))) && match(Op1, m_One()) && 1292*0fca6ea1SDimitry Andric computeKnownBits(X, /*Depth=*/0, &I).countMaxActiveBits() <= 1 && 1293*0fca6ea1SDimitry Andric computeKnownBits(Y, /*Depth=*/0, &I).countMaxActiveBits() <= 1) 1294*0fca6ea1SDimitry Andric return BinaryOperator::CreateAnd(X, Y); 1295*0fca6ea1SDimitry Andric 1296*0fca6ea1SDimitry Andric // (sub nuw X, (Y << nuw Z)) >>u exact Z --> (X >>u exact Z) sub nuw Y 1297*0fca6ea1SDimitry Andric if (I.isExact() && 1298*0fca6ea1SDimitry Andric match(Op0, m_OneUse(m_NUWSub(m_Value(X), 1299*0fca6ea1SDimitry Andric m_NUWShl(m_Value(Y), m_Specific(Op1)))))) { 1300*0fca6ea1SDimitry Andric Value *NewLshr = Builder.CreateLShr(X, Op1, "", /*isExact=*/true); 1301*0fca6ea1SDimitry Andric auto *NewSub = BinaryOperator::CreateNUWSub(NewLshr, Y); 1302*0fca6ea1SDimitry Andric NewSub->setHasNoSignedWrap( 1303*0fca6ea1SDimitry Andric cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap()); 1304*0fca6ea1SDimitry Andric return NewSub; 1305*0fca6ea1SDimitry Andric } 1306*0fca6ea1SDimitry Andric 1307*0fca6ea1SDimitry Andric auto isSuitableBinOpcode = [](Instruction::BinaryOps BinOpcode) { 1308*0fca6ea1SDimitry Andric switch (BinOpcode) { 1309*0fca6ea1SDimitry Andric default: 1310*0fca6ea1SDimitry Andric return false; 1311*0fca6ea1SDimitry Andric case Instruction::Add: 1312*0fca6ea1SDimitry Andric case Instruction::And: 1313*0fca6ea1SDimitry Andric case Instruction::Or: 1314*0fca6ea1SDimitry Andric case Instruction::Xor: 1315*0fca6ea1SDimitry Andric // Sub is handled separately. 1316*0fca6ea1SDimitry Andric return true; 1317*0fca6ea1SDimitry Andric } 1318*0fca6ea1SDimitry Andric }; 1319*0fca6ea1SDimitry Andric 1320*0fca6ea1SDimitry Andric // If both the binop and the shift are nuw, then: 1321*0fca6ea1SDimitry Andric // ((X << nuw Z) binop nuw Y) >>u Z --> X binop nuw (Y >>u Z) 1322*0fca6ea1SDimitry Andric if (match(Op0, m_OneUse(m_c_BinOp(m_NUWShl(m_Value(X), m_Specific(Op1)), 1323*0fca6ea1SDimitry Andric m_Value(Y))))) { 1324*0fca6ea1SDimitry Andric BinaryOperator *Op0OB = cast<BinaryOperator>(Op0); 1325*0fca6ea1SDimitry Andric if (isSuitableBinOpcode(Op0OB->getOpcode())) { 1326*0fca6ea1SDimitry Andric if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(Op0); 1327*0fca6ea1SDimitry Andric !OBO || OBO->hasNoUnsignedWrap()) { 1328*0fca6ea1SDimitry Andric Value *NewLshr = Builder.CreateLShr( 1329*0fca6ea1SDimitry Andric Y, Op1, "", I.isExact() && Op0OB->getOpcode() != Instruction::And); 1330*0fca6ea1SDimitry Andric auto *NewBinOp = BinaryOperator::Create(Op0OB->getOpcode(), NewLshr, X); 1331*0fca6ea1SDimitry Andric if (OBO) { 1332*0fca6ea1SDimitry Andric NewBinOp->setHasNoUnsignedWrap(true); 1333*0fca6ea1SDimitry Andric NewBinOp->setHasNoSignedWrap(OBO->hasNoSignedWrap()); 1334*0fca6ea1SDimitry Andric } else if (auto *Disjoint = dyn_cast<PossiblyDisjointInst>(Op0)) { 1335*0fca6ea1SDimitry Andric cast<PossiblyDisjointInst>(NewBinOp)->setIsDisjoint( 1336*0fca6ea1SDimitry Andric Disjoint->isDisjoint()); 1337*0fca6ea1SDimitry Andric } 1338*0fca6ea1SDimitry Andric return NewBinOp; 1339*0fca6ea1SDimitry Andric } 1340*0fca6ea1SDimitry Andric } 1341*0fca6ea1SDimitry Andric } 1342*0fca6ea1SDimitry Andric 1343349cc55cSDimitry Andric if (match(Op1, m_APInt(C))) { 1344349cc55cSDimitry Andric unsigned ShAmtC = C->getZExtValue(); 13450b57cec5SDimitry Andric auto *II = dyn_cast<IntrinsicInst>(Op0); 1346349cc55cSDimitry Andric if (II && isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == ShAmtC && 13470b57cec5SDimitry Andric (II->getIntrinsicID() == Intrinsic::ctlz || 13480b57cec5SDimitry Andric II->getIntrinsicID() == Intrinsic::cttz || 13490b57cec5SDimitry Andric II->getIntrinsicID() == Intrinsic::ctpop)) { 13500b57cec5SDimitry Andric // ctlz.i32(x)>>5 --> zext(x == 0) 13510b57cec5SDimitry Andric // cttz.i32(x)>>5 --> zext(x == 0) 13520b57cec5SDimitry Andric // ctpop.i32(x)>>5 --> zext(x == -1) 13530b57cec5SDimitry Andric bool IsPop = II->getIntrinsicID() == Intrinsic::ctpop; 13540b57cec5SDimitry Andric Constant *RHS = ConstantInt::getSigned(Ty, IsPop ? -1 : 0); 13550b57cec5SDimitry Andric Value *Cmp = Builder.CreateICmpEQ(II->getArgOperand(0), RHS); 13560b57cec5SDimitry Andric return new ZExtInst(Cmp, Ty); 13570b57cec5SDimitry Andric } 13580b57cec5SDimitry Andric 1359349cc55cSDimitry Andric const APInt *C1; 1360349cc55cSDimitry Andric if (match(Op0, m_Shl(m_Value(X), m_APInt(C1))) && C1->ult(BitWidth)) { 1361349cc55cSDimitry Andric if (C1->ult(ShAmtC)) { 1362349cc55cSDimitry Andric unsigned ShlAmtC = C1->getZExtValue(); 1363349cc55cSDimitry Andric Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShlAmtC); 13640b57cec5SDimitry Andric if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) { 1365349cc55cSDimitry Andric // (X <<nuw C1) >>u C --> X >>u (C - C1) 13660b57cec5SDimitry Andric auto *NewLShr = BinaryOperator::CreateLShr(X, ShiftDiff); 13670b57cec5SDimitry Andric NewLShr->setIsExact(I.isExact()); 13680b57cec5SDimitry Andric return NewLShr; 13690b57cec5SDimitry Andric } 137004eeddc0SDimitry Andric if (Op0->hasOneUse()) { 1371349cc55cSDimitry Andric // (X << C1) >>u C --> (X >>u (C - C1)) & (-1 >> C) 13720b57cec5SDimitry Andric Value *NewLShr = Builder.CreateLShr(X, ShiftDiff, "", I.isExact()); 1373349cc55cSDimitry Andric APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC)); 13740b57cec5SDimitry Andric return BinaryOperator::CreateAnd(NewLShr, ConstantInt::get(Ty, Mask)); 13750b57cec5SDimitry Andric } 137604eeddc0SDimitry Andric } else if (C1->ugt(ShAmtC)) { 1377349cc55cSDimitry Andric unsigned ShlAmtC = C1->getZExtValue(); 1378349cc55cSDimitry Andric Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmtC - ShAmtC); 13790b57cec5SDimitry Andric if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) { 13805f757f3fSDimitry Andric // (X <<nuw C1) >>u C --> X <<nuw/nsw (C1 - C) 13810b57cec5SDimitry Andric auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff); 13820b57cec5SDimitry Andric NewShl->setHasNoUnsignedWrap(true); 13835f757f3fSDimitry Andric NewShl->setHasNoSignedWrap(ShAmtC > 0); 13840b57cec5SDimitry Andric return NewShl; 13850b57cec5SDimitry Andric } 138604eeddc0SDimitry Andric if (Op0->hasOneUse()) { 1387349cc55cSDimitry Andric // (X << C1) >>u C --> X << (C1 - C) & (-1 >> C) 13880b57cec5SDimitry Andric Value *NewShl = Builder.CreateShl(X, ShiftDiff); 1389349cc55cSDimitry Andric APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC)); 13900b57cec5SDimitry Andric return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask)); 13910b57cec5SDimitry Andric } 139204eeddc0SDimitry Andric } else { 1393349cc55cSDimitry Andric assert(*C1 == ShAmtC); 13940b57cec5SDimitry Andric // (X << C) >>u C --> X & (-1 >>u C) 1395349cc55cSDimitry Andric APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC)); 13960b57cec5SDimitry Andric return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask)); 13970b57cec5SDimitry Andric } 139804eeddc0SDimitry Andric } 139904eeddc0SDimitry Andric 140004eeddc0SDimitry Andric // ((X << C) + Y) >>u C --> (X + (Y >>u C)) & (-1 >>u C) 140104eeddc0SDimitry Andric // TODO: Consolidate with the more general transform that starts from shl 140204eeddc0SDimitry Andric // (the shifts are in the opposite order). 140304eeddc0SDimitry Andric if (match(Op0, 140404eeddc0SDimitry Andric m_OneUse(m_c_Add(m_OneUse(m_Shl(m_Value(X), m_Specific(Op1))), 140504eeddc0SDimitry Andric m_Value(Y))))) { 140604eeddc0SDimitry Andric Value *NewLshr = Builder.CreateLShr(Y, Op1); 140704eeddc0SDimitry Andric Value *NewAdd = Builder.CreateAdd(NewLshr, X); 140804eeddc0SDimitry Andric unsigned Op1Val = C->getLimitedValue(BitWidth); 140904eeddc0SDimitry Andric APInt Bits = APInt::getLowBitsSet(BitWidth, BitWidth - Op1Val); 141004eeddc0SDimitry Andric Constant *Mask = ConstantInt::get(Ty, Bits); 141104eeddc0SDimitry Andric return BinaryOperator::CreateAnd(NewAdd, Mask); 141204eeddc0SDimitry Andric } 14130b57cec5SDimitry Andric 14140b57cec5SDimitry Andric if (match(Op0, m_OneUse(m_ZExt(m_Value(X)))) && 14150b57cec5SDimitry Andric (!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType()))) { 1416349cc55cSDimitry Andric assert(ShAmtC < X->getType()->getScalarSizeInBits() && 14170b57cec5SDimitry Andric "Big shift not simplified to zero?"); 14180b57cec5SDimitry Andric // lshr (zext iM X to iN), C --> zext (lshr X, C) to iN 1419349cc55cSDimitry Andric Value *NewLShr = Builder.CreateLShr(X, ShAmtC); 14200b57cec5SDimitry Andric return new ZExtInst(NewLShr, Ty); 14210b57cec5SDimitry Andric } 14220b57cec5SDimitry Andric 1423349cc55cSDimitry Andric if (match(Op0, m_SExt(m_Value(X)))) { 14240b57cec5SDimitry Andric unsigned SrcTyBitWidth = X->getType()->getScalarSizeInBits(); 1425349cc55cSDimitry Andric // lshr (sext i1 X to iN), C --> select (X, -1 >> C, 0) 1426349cc55cSDimitry Andric if (SrcTyBitWidth == 1) { 1427349cc55cSDimitry Andric auto *NewC = ConstantInt::get( 1428349cc55cSDimitry Andric Ty, APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC)); 1429349cc55cSDimitry Andric return SelectInst::Create(X, NewC, ConstantInt::getNullValue(Ty)); 1430349cc55cSDimitry Andric } 14310b57cec5SDimitry Andric 1432349cc55cSDimitry Andric if ((!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType())) && 1433349cc55cSDimitry Andric Op0->hasOneUse()) { 1434349cc55cSDimitry Andric // Are we moving the sign bit to the low bit and widening with high 1435349cc55cSDimitry Andric // zeros? lshr (sext iM X to iN), N-1 --> zext (lshr X, M-1) to iN 1436349cc55cSDimitry Andric if (ShAmtC == BitWidth - 1) { 14370b57cec5SDimitry Andric Value *NewLShr = Builder.CreateLShr(X, SrcTyBitWidth - 1); 14380b57cec5SDimitry Andric return new ZExtInst(NewLShr, Ty); 14390b57cec5SDimitry Andric } 14400b57cec5SDimitry Andric 14410b57cec5SDimitry Andric // lshr (sext iM X to iN), N-M --> zext (ashr X, min(N-M, M-1)) to iN 1442349cc55cSDimitry Andric if (ShAmtC == BitWidth - SrcTyBitWidth) { 14430b57cec5SDimitry Andric // The new shift amount can't be more than the narrow source type. 1444349cc55cSDimitry Andric unsigned NewShAmt = std::min(ShAmtC, SrcTyBitWidth - 1); 14450b57cec5SDimitry Andric Value *AShr = Builder.CreateAShr(X, NewShAmt); 14460b57cec5SDimitry Andric return new ZExtInst(AShr, Ty); 14470b57cec5SDimitry Andric } 14480b57cec5SDimitry Andric } 1449349cc55cSDimitry Andric } 14500b57cec5SDimitry Andric 1451349cc55cSDimitry Andric if (ShAmtC == BitWidth - 1) { 1452fe6060f1SDimitry Andric // lshr i32 or(X,-X), 31 --> zext (X != 0) 1453fe6060f1SDimitry Andric if (match(Op0, m_OneUse(m_c_Or(m_Neg(m_Value(X)), m_Deferred(X))))) 1454fe6060f1SDimitry Andric return new ZExtInst(Builder.CreateIsNotNull(X), Ty); 1455fe6060f1SDimitry Andric 1456fe6060f1SDimitry Andric // lshr i32 (X -nsw Y), 31 --> zext (X < Y) 1457fe6060f1SDimitry Andric if (match(Op0, m_OneUse(m_NSWSub(m_Value(X), m_Value(Y))))) 1458e8d8bef9SDimitry Andric return new ZExtInst(Builder.CreateICmpSLT(X, Y), Ty); 1459e8d8bef9SDimitry Andric 1460fe6060f1SDimitry Andric // Check if a number is negative and odd: 1461fe6060f1SDimitry Andric // lshr i32 (srem X, 2), 31 --> and (X >> 31), X 1462fe6060f1SDimitry Andric if (match(Op0, m_OneUse(m_SRem(m_Value(X), m_SpecificInt(2))))) { 1463349cc55cSDimitry Andric Value *Signbit = Builder.CreateLShr(X, ShAmtC); 1464fe6060f1SDimitry Andric return BinaryOperator::CreateAnd(Signbit, X); 1465fe6060f1SDimitry Andric } 1466fe6060f1SDimitry Andric } 1467fe6060f1SDimitry Andric 1468349cc55cSDimitry Andric Instruction *TruncSrc; 1469349cc55cSDimitry Andric if (match(Op0, m_OneUse(m_Trunc(m_Instruction(TruncSrc)))) && 1470349cc55cSDimitry Andric match(TruncSrc, m_LShr(m_Value(X), m_APInt(C1)))) { 1471349cc55cSDimitry Andric unsigned SrcWidth = X->getType()->getScalarSizeInBits(); 1472349cc55cSDimitry Andric unsigned AmtSum = ShAmtC + C1->getZExtValue(); 1473349cc55cSDimitry Andric 1474349cc55cSDimitry Andric // If the combined shift fits in the source width: 1475349cc55cSDimitry Andric // (trunc (X >>u C1)) >>u C --> and (trunc (X >>u (C1 + C)), MaskC 1476349cc55cSDimitry Andric // 1477349cc55cSDimitry Andric // If the first shift covers the number of bits truncated, then the 1478349cc55cSDimitry Andric // mask instruction is eliminated (and so the use check is relaxed). 1479349cc55cSDimitry Andric if (AmtSum < SrcWidth && 1480349cc55cSDimitry Andric (TruncSrc->hasOneUse() || C1->uge(SrcWidth - BitWidth))) { 1481349cc55cSDimitry Andric Value *SumShift = Builder.CreateLShr(X, AmtSum, "sum.shift"); 1482349cc55cSDimitry Andric Value *Trunc = Builder.CreateTrunc(SumShift, Ty, I.getName()); 1483349cc55cSDimitry Andric 1484349cc55cSDimitry Andric // If the first shift does not cover the number of bits truncated, then 1485349cc55cSDimitry Andric // we require a mask to get rid of high bits in the result. 1486349cc55cSDimitry Andric APInt MaskC = APInt::getAllOnes(BitWidth).lshr(ShAmtC); 1487349cc55cSDimitry Andric return BinaryOperator::CreateAnd(Trunc, ConstantInt::get(Ty, MaskC)); 1488349cc55cSDimitry Andric } 1489349cc55cSDimitry Andric } 1490349cc55cSDimitry Andric 149181ad6265SDimitry Andric const APInt *MulC; 149281ad6265SDimitry Andric if (match(Op0, m_NUWMul(m_Value(X), m_APInt(MulC)))) { 1493*0fca6ea1SDimitry Andric if (BitWidth > 2 && (*MulC - 1).isPowerOf2() && 1494*0fca6ea1SDimitry Andric MulC->logBase2() == ShAmtC) { 1495*0fca6ea1SDimitry Andric // Look for a "splat" mul pattern - it replicates bits across each half 1496*0fca6ea1SDimitry Andric // of a value, so a right shift simplifies back to just X: 1497*0fca6ea1SDimitry Andric // lshr i[2N] (mul nuw X, (2^N)+1), N --> X 1498*0fca6ea1SDimitry Andric if (ShAmtC * 2 == BitWidth) 1499*0fca6ea1SDimitry Andric return replaceInstUsesWith(I, X); 1500*0fca6ea1SDimitry Andric 1501*0fca6ea1SDimitry Andric // lshr (mul nuw (X, 2^N + 1)), N -> add nuw (X, lshr(X, N)) 1502*0fca6ea1SDimitry Andric if (Op0->hasOneUse()) { 1503*0fca6ea1SDimitry Andric auto *NewAdd = BinaryOperator::CreateNUWAdd( 1504*0fca6ea1SDimitry Andric X, Builder.CreateLShr(X, ConstantInt::get(Ty, ShAmtC), "", 1505*0fca6ea1SDimitry Andric I.isExact())); 1506*0fca6ea1SDimitry Andric NewAdd->setHasNoSignedWrap( 1507*0fca6ea1SDimitry Andric cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap()); 1508*0fca6ea1SDimitry Andric return NewAdd; 1509*0fca6ea1SDimitry Andric } 1510*0fca6ea1SDimitry Andric } 1511fe6060f1SDimitry Andric 151281ad6265SDimitry Andric // The one-use check is not strictly necessary, but codegen may not be 151381ad6265SDimitry Andric // able to invert the transform and perf may suffer with an extra mul 151481ad6265SDimitry Andric // instruction. 151581ad6265SDimitry Andric if (Op0->hasOneUse()) { 151681ad6265SDimitry Andric APInt NewMulC = MulC->lshr(ShAmtC); 151781ad6265SDimitry Andric // if c is divisible by (1 << ShAmtC): 15185f757f3fSDimitry Andric // lshr (mul nuw x, MulC), ShAmtC -> mul nuw nsw x, (MulC >> ShAmtC) 151981ad6265SDimitry Andric if (MulC->eq(NewMulC.shl(ShAmtC))) { 152081ad6265SDimitry Andric auto *NewMul = 152181ad6265SDimitry Andric BinaryOperator::CreateNUWMul(X, ConstantInt::get(Ty, NewMulC)); 15225f757f3fSDimitry Andric assert(ShAmtC != 0 && 15235f757f3fSDimitry Andric "lshr X, 0 should be handled by simplifyLShrInst."); 15245f757f3fSDimitry Andric NewMul->setHasNoSignedWrap(true); 152581ad6265SDimitry Andric return NewMul; 152681ad6265SDimitry Andric } 152781ad6265SDimitry Andric } 152881ad6265SDimitry Andric } 152981ad6265SDimitry Andric 1530*0fca6ea1SDimitry Andric // lshr (mul nsw (X, 2^N + 1)), N -> add nsw (X, lshr(X, N)) 1531*0fca6ea1SDimitry Andric if (match(Op0, m_OneUse(m_NSWMul(m_Value(X), m_APInt(MulC))))) { 1532*0fca6ea1SDimitry Andric if (BitWidth > 2 && (*MulC - 1).isPowerOf2() && 1533*0fca6ea1SDimitry Andric MulC->logBase2() == ShAmtC) { 1534*0fca6ea1SDimitry Andric return BinaryOperator::CreateNSWAdd( 1535*0fca6ea1SDimitry Andric X, Builder.CreateLShr(X, ConstantInt::get(Ty, ShAmtC), "", 1536*0fca6ea1SDimitry Andric I.isExact())); 1537*0fca6ea1SDimitry Andric } 1538*0fca6ea1SDimitry Andric } 1539*0fca6ea1SDimitry Andric 154081ad6265SDimitry Andric // Try to narrow bswap. 154181ad6265SDimitry Andric // In the case where the shift amount equals the bitwidth difference, the 154281ad6265SDimitry Andric // shift is eliminated. 154381ad6265SDimitry Andric if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::bswap>( 154481ad6265SDimitry Andric m_OneUse(m_ZExt(m_Value(X))))))) { 154581ad6265SDimitry Andric unsigned SrcWidth = X->getType()->getScalarSizeInBits(); 154681ad6265SDimitry Andric unsigned WidthDiff = BitWidth - SrcWidth; 154781ad6265SDimitry Andric if (SrcWidth % 16 == 0) { 154881ad6265SDimitry Andric Value *NarrowSwap = Builder.CreateUnaryIntrinsic(Intrinsic::bswap, X); 154981ad6265SDimitry Andric if (ShAmtC >= WidthDiff) { 155081ad6265SDimitry Andric // (bswap (zext X)) >> C --> zext (bswap X >> C') 155181ad6265SDimitry Andric Value *NewShift = Builder.CreateLShr(NarrowSwap, ShAmtC - WidthDiff); 155281ad6265SDimitry Andric return new ZExtInst(NewShift, Ty); 155381ad6265SDimitry Andric } else { 155481ad6265SDimitry Andric // (bswap (zext X)) >> C --> (zext (bswap X)) << C' 155581ad6265SDimitry Andric Value *NewZExt = Builder.CreateZExt(NarrowSwap, Ty); 155681ad6265SDimitry Andric Constant *ShiftDiff = ConstantInt::get(Ty, WidthDiff - ShAmtC); 155781ad6265SDimitry Andric return BinaryOperator::CreateShl(NewZExt, ShiftDiff); 155881ad6265SDimitry Andric } 155981ad6265SDimitry Andric } 156081ad6265SDimitry Andric } 156181ad6265SDimitry Andric 1562bdd1243dSDimitry Andric // Reduce add-carry of bools to logic: 1563bdd1243dSDimitry Andric // ((zext BoolX) + (zext BoolY)) >> 1 --> zext (BoolX && BoolY) 1564bdd1243dSDimitry Andric Value *BoolX, *BoolY; 1565bdd1243dSDimitry Andric if (ShAmtC == 1 && match(Op0, m_Add(m_Value(X), m_Value(Y))) && 1566bdd1243dSDimitry Andric match(X, m_ZExt(m_Value(BoolX))) && match(Y, m_ZExt(m_Value(BoolY))) && 1567bdd1243dSDimitry Andric BoolX->getType()->isIntOrIntVectorTy(1) && 1568bdd1243dSDimitry Andric BoolY->getType()->isIntOrIntVectorTy(1) && 1569bdd1243dSDimitry Andric (X->hasOneUse() || Y->hasOneUse() || Op0->hasOneUse())) { 1570bdd1243dSDimitry Andric Value *And = Builder.CreateAnd(BoolX, BoolY); 1571bdd1243dSDimitry Andric return new ZExtInst(And, Ty); 1572bdd1243dSDimitry Andric } 15735f757f3fSDimitry Andric } 1574bdd1243dSDimitry Andric 15755f757f3fSDimitry Andric const SimplifyQuery Q = SQ.getWithInstruction(&I); 15765f757f3fSDimitry Andric if (setShiftFlags(I, Q)) 15770b57cec5SDimitry Andric return &I; 15780b57cec5SDimitry Andric 15790b57cec5SDimitry Andric // Transform (x << y) >> y to x & (-1 >> y) 15800b57cec5SDimitry Andric if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_Specific(Op1))))) { 15810b57cec5SDimitry Andric Constant *AllOnes = ConstantInt::getAllOnesValue(Ty); 15820b57cec5SDimitry Andric Value *Mask = Builder.CreateLShr(AllOnes, Op1); 15830b57cec5SDimitry Andric return BinaryOperator::CreateAnd(Mask, X); 15840b57cec5SDimitry Andric } 15850b57cec5SDimitry Andric 1586*0fca6ea1SDimitry Andric // Transform (-1 << y) >> y to -1 >> y 1587*0fca6ea1SDimitry Andric if (match(Op0, m_Shl(m_AllOnes(), m_Specific(Op1)))) { 1588*0fca6ea1SDimitry Andric Constant *AllOnes = ConstantInt::getAllOnesValue(Ty); 1589*0fca6ea1SDimitry Andric return BinaryOperator::CreateLShr(AllOnes, Op1); 1590*0fca6ea1SDimitry Andric } 1591*0fca6ea1SDimitry Andric 1592bdd1243dSDimitry Andric if (Instruction *Overflow = foldLShrOverflowBit(I)) 1593bdd1243dSDimitry Andric return Overflow; 1594bdd1243dSDimitry Andric 15950b57cec5SDimitry Andric return nullptr; 15960b57cec5SDimitry Andric } 15970b57cec5SDimitry Andric 15988bcb0991SDimitry Andric Instruction * 1599e8d8bef9SDimitry Andric InstCombinerImpl::foldVariableSignZeroExtensionOfVariableHighBitExtract( 16008bcb0991SDimitry Andric BinaryOperator &OldAShr) { 16018bcb0991SDimitry Andric assert(OldAShr.getOpcode() == Instruction::AShr && 16028bcb0991SDimitry Andric "Must be called with arithmetic right-shift instruction only."); 16038bcb0991SDimitry Andric 16048bcb0991SDimitry Andric // Check that constant C is a splat of the element-wise bitwidth of V. 16058bcb0991SDimitry Andric auto BitWidthSplat = [](Constant *C, Value *V) { 16068bcb0991SDimitry Andric return match( 16078bcb0991SDimitry Andric C, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ, 16088bcb0991SDimitry Andric APInt(C->getType()->getScalarSizeInBits(), 16098bcb0991SDimitry Andric V->getType()->getScalarSizeInBits()))); 16108bcb0991SDimitry Andric }; 16118bcb0991SDimitry Andric 16128bcb0991SDimitry Andric // It should look like variable-length sign-extension on the outside: 16138bcb0991SDimitry Andric // (Val << (bitwidth(Val)-Nbits)) a>> (bitwidth(Val)-Nbits) 16148bcb0991SDimitry Andric Value *NBits; 16158bcb0991SDimitry Andric Instruction *MaybeTrunc; 16168bcb0991SDimitry Andric Constant *C1, *C2; 16178bcb0991SDimitry Andric if (!match(&OldAShr, 16188bcb0991SDimitry Andric m_AShr(m_Shl(m_Instruction(MaybeTrunc), 16198bcb0991SDimitry Andric m_ZExtOrSelf(m_Sub(m_Constant(C1), 16208bcb0991SDimitry Andric m_ZExtOrSelf(m_Value(NBits))))), 16218bcb0991SDimitry Andric m_ZExtOrSelf(m_Sub(m_Constant(C2), 16228bcb0991SDimitry Andric m_ZExtOrSelf(m_Deferred(NBits)))))) || 16238bcb0991SDimitry Andric !BitWidthSplat(C1, &OldAShr) || !BitWidthSplat(C2, &OldAShr)) 16248bcb0991SDimitry Andric return nullptr; 16258bcb0991SDimitry Andric 16268bcb0991SDimitry Andric // There may or may not be a truncation after outer two shifts. 16278bcb0991SDimitry Andric Instruction *HighBitExtract; 16288bcb0991SDimitry Andric match(MaybeTrunc, m_TruncOrSelf(m_Instruction(HighBitExtract))); 16298bcb0991SDimitry Andric bool HadTrunc = MaybeTrunc != HighBitExtract; 16308bcb0991SDimitry Andric 16318bcb0991SDimitry Andric // And finally, the innermost part of the pattern must be a right-shift. 16328bcb0991SDimitry Andric Value *X, *NumLowBitsToSkip; 16338bcb0991SDimitry Andric if (!match(HighBitExtract, m_Shr(m_Value(X), m_Value(NumLowBitsToSkip)))) 16348bcb0991SDimitry Andric return nullptr; 16358bcb0991SDimitry Andric 16368bcb0991SDimitry Andric // Said right-shift must extract high NBits bits - C0 must be it's bitwidth. 16378bcb0991SDimitry Andric Constant *C0; 16388bcb0991SDimitry Andric if (!match(NumLowBitsToSkip, 16398bcb0991SDimitry Andric m_ZExtOrSelf( 16408bcb0991SDimitry Andric m_Sub(m_Constant(C0), m_ZExtOrSelf(m_Specific(NBits))))) || 16418bcb0991SDimitry Andric !BitWidthSplat(C0, HighBitExtract)) 16428bcb0991SDimitry Andric return nullptr; 16438bcb0991SDimitry Andric 16448bcb0991SDimitry Andric // Since the NBits is identical for all shifts, if the outermost and 16458bcb0991SDimitry Andric // innermost shifts are identical, then outermost shifts are redundant. 16468bcb0991SDimitry Andric // If we had truncation, do keep it though. 16478bcb0991SDimitry Andric if (HighBitExtract->getOpcode() == OldAShr.getOpcode()) 16488bcb0991SDimitry Andric return replaceInstUsesWith(OldAShr, MaybeTrunc); 16498bcb0991SDimitry Andric 16508bcb0991SDimitry Andric // Else, if there was a truncation, then we need to ensure that one 16518bcb0991SDimitry Andric // instruction will go away. 16528bcb0991SDimitry Andric if (HadTrunc && !match(&OldAShr, m_c_BinOp(m_OneUse(m_Value()), m_Value()))) 16538bcb0991SDimitry Andric return nullptr; 16548bcb0991SDimitry Andric 16558bcb0991SDimitry Andric // Finally, bypass two innermost shifts, and perform the outermost shift on 16568bcb0991SDimitry Andric // the operands of the innermost shift. 16578bcb0991SDimitry Andric Instruction *NewAShr = 16588bcb0991SDimitry Andric BinaryOperator::Create(OldAShr.getOpcode(), X, NumLowBitsToSkip); 16598bcb0991SDimitry Andric NewAShr->copyIRFlags(HighBitExtract); // We can preserve 'exact'-ness. 16608bcb0991SDimitry Andric if (!HadTrunc) 16618bcb0991SDimitry Andric return NewAShr; 16628bcb0991SDimitry Andric 16638bcb0991SDimitry Andric Builder.Insert(NewAShr); 16648bcb0991SDimitry Andric return TruncInst::CreateTruncOrBitCast(NewAShr, OldAShr.getType()); 16658bcb0991SDimitry Andric } 16668bcb0991SDimitry Andric 1667e8d8bef9SDimitry Andric Instruction *InstCombinerImpl::visitAShr(BinaryOperator &I) { 166881ad6265SDimitry Andric if (Value *V = simplifyAShrInst(I.getOperand(0), I.getOperand(1), I.isExact(), 16690b57cec5SDimitry Andric SQ.getWithInstruction(&I))) 16700b57cec5SDimitry Andric return replaceInstUsesWith(I, V); 16710b57cec5SDimitry Andric 16720b57cec5SDimitry Andric if (Instruction *X = foldVectorBinop(I)) 16730b57cec5SDimitry Andric return X; 16740b57cec5SDimitry Andric 16750b57cec5SDimitry Andric if (Instruction *R = commonShiftTransforms(I)) 16760b57cec5SDimitry Andric return R; 16770b57cec5SDimitry Andric 16780b57cec5SDimitry Andric Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 16790b57cec5SDimitry Andric Type *Ty = I.getType(); 16800b57cec5SDimitry Andric unsigned BitWidth = Ty->getScalarSizeInBits(); 16810b57cec5SDimitry Andric const APInt *ShAmtAPInt; 16820b57cec5SDimitry Andric if (match(Op1, m_APInt(ShAmtAPInt)) && ShAmtAPInt->ult(BitWidth)) { 16830b57cec5SDimitry Andric unsigned ShAmt = ShAmtAPInt->getZExtValue(); 16840b57cec5SDimitry Andric 16850b57cec5SDimitry Andric // If the shift amount equals the difference in width of the destination 16860b57cec5SDimitry Andric // and source scalar types: 16870b57cec5SDimitry Andric // ashr (shl (zext X), C), C --> sext X 16880b57cec5SDimitry Andric Value *X; 16890b57cec5SDimitry Andric if (match(Op0, m_Shl(m_ZExt(m_Value(X)), m_Specific(Op1))) && 16900b57cec5SDimitry Andric ShAmt == BitWidth - X->getType()->getScalarSizeInBits()) 16910b57cec5SDimitry Andric return new SExtInst(X, Ty); 16920b57cec5SDimitry Andric 16930b57cec5SDimitry Andric // We can't handle (X << C1) >>s C2. It shifts arbitrary bits in. However, 16940b57cec5SDimitry Andric // we can handle (X <<nsw C1) >>s C2 since it only shifts in sign bits. 16950b57cec5SDimitry Andric const APInt *ShOp1; 16960b57cec5SDimitry Andric if (match(Op0, m_NSWShl(m_Value(X), m_APInt(ShOp1))) && 16970b57cec5SDimitry Andric ShOp1->ult(BitWidth)) { 16980b57cec5SDimitry Andric unsigned ShlAmt = ShOp1->getZExtValue(); 16990b57cec5SDimitry Andric if (ShlAmt < ShAmt) { 17000b57cec5SDimitry Andric // (X <<nsw C1) >>s C2 --> X >>s (C2 - C1) 17010b57cec5SDimitry Andric Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt); 17020b57cec5SDimitry Andric auto *NewAShr = BinaryOperator::CreateAShr(X, ShiftDiff); 17030b57cec5SDimitry Andric NewAShr->setIsExact(I.isExact()); 17040b57cec5SDimitry Andric return NewAShr; 17050b57cec5SDimitry Andric } 17060b57cec5SDimitry Andric if (ShlAmt > ShAmt) { 17070b57cec5SDimitry Andric // (X <<nsw C1) >>s C2 --> X <<nsw (C1 - C2) 17080b57cec5SDimitry Andric Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt); 17090b57cec5SDimitry Andric auto *NewShl = BinaryOperator::Create(Instruction::Shl, X, ShiftDiff); 17100b57cec5SDimitry Andric NewShl->setHasNoSignedWrap(true); 17110b57cec5SDimitry Andric return NewShl; 17120b57cec5SDimitry Andric } 17130b57cec5SDimitry Andric } 17140b57cec5SDimitry Andric 17150b57cec5SDimitry Andric if (match(Op0, m_AShr(m_Value(X), m_APInt(ShOp1))) && 17160b57cec5SDimitry Andric ShOp1->ult(BitWidth)) { 17170b57cec5SDimitry Andric unsigned AmtSum = ShAmt + ShOp1->getZExtValue(); 17180b57cec5SDimitry Andric // Oversized arithmetic shifts replicate the sign bit. 17190b57cec5SDimitry Andric AmtSum = std::min(AmtSum, BitWidth - 1); 17200b57cec5SDimitry Andric // (X >>s C1) >>s C2 --> X >>s (C1 + C2) 17210b57cec5SDimitry Andric return BinaryOperator::CreateAShr(X, ConstantInt::get(Ty, AmtSum)); 17220b57cec5SDimitry Andric } 17230b57cec5SDimitry Andric 17240b57cec5SDimitry Andric if (match(Op0, m_OneUse(m_SExt(m_Value(X)))) && 17250b57cec5SDimitry Andric (Ty->isVectorTy() || shouldChangeType(Ty, X->getType()))) { 17260b57cec5SDimitry Andric // ashr (sext X), C --> sext (ashr X, C') 17270b57cec5SDimitry Andric Type *SrcTy = X->getType(); 17280b57cec5SDimitry Andric ShAmt = std::min(ShAmt, SrcTy->getScalarSizeInBits() - 1); 17290b57cec5SDimitry Andric Value *NewSh = Builder.CreateAShr(X, ConstantInt::get(SrcTy, ShAmt)); 17300b57cec5SDimitry Andric return new SExtInst(NewSh, Ty); 17310b57cec5SDimitry Andric } 17320b57cec5SDimitry Andric 1733fe6060f1SDimitry Andric if (ShAmt == BitWidth - 1) { 1734fe6060f1SDimitry Andric // ashr i32 or(X,-X), 31 --> sext (X != 0) 1735fe6060f1SDimitry Andric if (match(Op0, m_OneUse(m_c_Or(m_Neg(m_Value(X)), m_Deferred(X))))) 1736fe6060f1SDimitry Andric return new SExtInst(Builder.CreateIsNotNull(X), Ty); 1737fe6060f1SDimitry Andric 1738e8d8bef9SDimitry Andric // ashr i32 (X -nsw Y), 31 --> sext (X < Y) 1739e8d8bef9SDimitry Andric Value *Y; 1740fe6060f1SDimitry Andric if (match(Op0, m_OneUse(m_NSWSub(m_Value(X), m_Value(Y))))) 1741e8d8bef9SDimitry Andric return new SExtInst(Builder.CreateICmpSLT(X, Y), Ty); 1742fe6060f1SDimitry Andric } 1743*0fca6ea1SDimitry Andric 1744*0fca6ea1SDimitry Andric const APInt *MulC; 1745*0fca6ea1SDimitry Andric if (match(Op0, m_OneUse(m_NSWMul(m_Value(X), m_APInt(MulC)))) && 1746*0fca6ea1SDimitry Andric (BitWidth > 2 && (*MulC - 1).isPowerOf2() && 1747*0fca6ea1SDimitry Andric MulC->logBase2() == ShAmt && 1748*0fca6ea1SDimitry Andric (ShAmt < BitWidth - 1))) /* Minus 1 for the sign bit */ { 1749*0fca6ea1SDimitry Andric 1750*0fca6ea1SDimitry Andric // ashr (mul nsw (X, 2^N + 1)), N -> add nsw (X, ashr(X, N)) 1751*0fca6ea1SDimitry Andric auto *NewAdd = BinaryOperator::CreateNSWAdd( 1752*0fca6ea1SDimitry Andric X, 1753*0fca6ea1SDimitry Andric Builder.CreateAShr(X, ConstantInt::get(Ty, ShAmt), "", I.isExact())); 1754*0fca6ea1SDimitry Andric NewAdd->setHasNoUnsignedWrap( 1755*0fca6ea1SDimitry Andric cast<OverflowingBinaryOperator>(Op0)->hasNoUnsignedWrap()); 1756*0fca6ea1SDimitry Andric return NewAdd; 1757*0fca6ea1SDimitry Andric } 17585f757f3fSDimitry Andric } 1759e8d8bef9SDimitry Andric 17605f757f3fSDimitry Andric const SimplifyQuery Q = SQ.getWithInstruction(&I); 17615f757f3fSDimitry Andric if (setShiftFlags(I, Q)) 17620b57cec5SDimitry Andric return &I; 17630b57cec5SDimitry Andric 1764349cc55cSDimitry Andric // Prefer `-(x & 1)` over `(x << (bitwidth(x)-1)) a>> (bitwidth(x)-1)` 1765349cc55cSDimitry Andric // as the pattern to splat the lowest bit. 1766349cc55cSDimitry Andric // FIXME: iff X is already masked, we don't need the one-use check. 1767349cc55cSDimitry Andric Value *X; 1768*0fca6ea1SDimitry Andric if (match(Op1, m_SpecificIntAllowPoison(BitWidth - 1)) && 1769349cc55cSDimitry Andric match(Op0, m_OneUse(m_Shl(m_Value(X), 1770*0fca6ea1SDimitry Andric m_SpecificIntAllowPoison(BitWidth - 1))))) { 1771349cc55cSDimitry Andric Constant *Mask = ConstantInt::get(Ty, 1); 1772349cc55cSDimitry Andric // Retain the knowledge about the ignored lanes. 1773349cc55cSDimitry Andric Mask = Constant::mergeUndefsWith( 1774349cc55cSDimitry Andric Constant::mergeUndefsWith(Mask, cast<Constant>(Op1)), 1775349cc55cSDimitry Andric cast<Constant>(cast<Instruction>(Op0)->getOperand(1))); 1776349cc55cSDimitry Andric X = Builder.CreateAnd(X, Mask); 1777349cc55cSDimitry Andric return BinaryOperator::CreateNeg(X); 1778349cc55cSDimitry Andric } 1779349cc55cSDimitry Andric 17808bcb0991SDimitry Andric if (Instruction *R = foldVariableSignZeroExtensionOfVariableHighBitExtract(I)) 17818bcb0991SDimitry Andric return R; 17828bcb0991SDimitry Andric 17830b57cec5SDimitry Andric // See if we can turn a signed shr into an unsigned shr. 1784bdd1243dSDimitry Andric if (MaskedValueIsZero(Op0, APInt::getSignMask(BitWidth), 0, &I)) { 1785bdd1243dSDimitry Andric Instruction *Lshr = BinaryOperator::CreateLShr(Op0, Op1); 1786bdd1243dSDimitry Andric Lshr->setIsExact(I.isExact()); 1787bdd1243dSDimitry Andric return Lshr; 1788bdd1243dSDimitry Andric } 17890b57cec5SDimitry Andric 1790fe6060f1SDimitry Andric // ashr (xor %x, -1), %y --> xor (ashr %x, %y), -1 1791fe6060f1SDimitry Andric if (match(Op0, m_OneUse(m_Not(m_Value(X))))) { 1792fe6060f1SDimitry Andric // Note that we must drop 'exact'-ness of the shift! 1793fe6060f1SDimitry Andric // Note that we can't keep undef's in -1 vector constant! 1794fe6060f1SDimitry Andric auto *NewAShr = Builder.CreateAShr(X, Op1, Op0->getName() + ".not"); 1795fe6060f1SDimitry Andric return BinaryOperator::CreateNot(NewAShr); 1796fe6060f1SDimitry Andric } 1797fe6060f1SDimitry Andric 17980b57cec5SDimitry Andric return nullptr; 17990b57cec5SDimitry Andric } 1800