1849 lines · cpp
1//===- InstCombineShifts.cpp ----------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the visitShl, visitLShr, and visitAShr functions.10//11//===----------------------------------------------------------------------===//12 13#include "InstCombineInternal.h"14#include "llvm/Analysis/InstructionSimplify.h"15#include "llvm/IR/IntrinsicInst.h"16#include "llvm/IR/PatternMatch.h"17#include "llvm/Transforms/InstCombine/InstCombiner.h"18using namespace llvm;19using namespace PatternMatch;20 21#define DEBUG_TYPE "instcombine"22 23bool canTryToConstantAddTwoShiftAmounts(Value *Sh0, Value *ShAmt0, Value *Sh1,24 Value *ShAmt1) {25 // We have two shift amounts from two different shifts. The types of those26 // shift amounts may not match. If that's the case let's bailout now..27 if (ShAmt0->getType() != ShAmt1->getType())28 return false;29 30 // As input, we have the following pattern:31 // Sh0 (Sh1 X, Q), K32 // We want to rewrite that as:33 // Sh x, (Q+K) iff (Q+K) u< bitwidth(x)34 // While we know that originally (Q+K) would not overflow35 // (because 2 * (N-1) u<= iN -1), we have looked past extensions of36 // shift amounts. so it may now overflow in smaller bitwidth.37 // To ensure that does not happen, we need to ensure that the total maximal38 // shift amount is still representable in that smaller bit width.39 unsigned MaximalPossibleTotalShiftAmount =40 (Sh0->getType()->getScalarSizeInBits() - 1) +41 (Sh1->getType()->getScalarSizeInBits() - 1);42 APInt MaximalRepresentableShiftAmount =43 APInt::getAllOnes(ShAmt0->getType()->getScalarSizeInBits());44 return MaximalRepresentableShiftAmount.uge(MaximalPossibleTotalShiftAmount);45}46 47// Given pattern:48// (x shiftopcode Q) shiftopcode K49// we should rewrite it as50// x shiftopcode (Q+K) iff (Q+K) u< bitwidth(x) and51//52// This is valid for any shift, but they must be identical, and we must be53// careful in case we have (zext(Q)+zext(K)) and look past extensions,54// (Q+K) must not overflow or else (Q+K) u< bitwidth(x) is bogus.55//56// AnalyzeForSignBitExtraction indicates that we will only analyze whether this57// pattern has any 2 right-shifts that sum to 1 less than original bit width.58Value *InstCombinerImpl::reassociateShiftAmtsOfTwoSameDirectionShifts(59 BinaryOperator *Sh0, const SimplifyQuery &SQ,60 bool AnalyzeForSignBitExtraction) {61 // Look for a shift of some instruction, ignore zext of shift amount if any.62 Instruction *Sh0Op0;63 Value *ShAmt0;64 if (!match(Sh0,65 m_Shift(m_Instruction(Sh0Op0), m_ZExtOrSelf(m_Value(ShAmt0)))))66 return nullptr;67 68 // If there is a truncation between the two shifts, we must make note of it69 // and look through it. The truncation imposes additional constraints on the70 // transform.71 Instruction *Sh1;72 Value *Trunc = nullptr;73 match(Sh0Op0,74 m_CombineOr(m_CombineAnd(m_Trunc(m_Instruction(Sh1)), m_Value(Trunc)),75 m_Instruction(Sh1)));76 77 // Inner shift: (x shiftopcode ShAmt1)78 // Like with other shift, ignore zext of shift amount if any.79 Value *X, *ShAmt1;80 if (!match(Sh1, m_Shift(m_Value(X), m_ZExtOrSelf(m_Value(ShAmt1)))))81 return nullptr;82 83 // Verify that it would be safe to try to add those two shift amounts.84 if (!canTryToConstantAddTwoShiftAmounts(Sh0, ShAmt0, Sh1, ShAmt1))85 return nullptr;86 87 // We are only looking for signbit extraction if we have two right shifts.88 bool HadTwoRightShifts = match(Sh0, m_Shr(m_Value(), m_Value())) &&89 match(Sh1, m_Shr(m_Value(), m_Value()));90 // ... and if it's not two right-shifts, we know the answer already.91 if (AnalyzeForSignBitExtraction && !HadTwoRightShifts)92 return nullptr;93 94 // The shift opcodes must be identical, unless we are just checking whether95 // this pattern can be interpreted as a sign-bit-extraction.96 Instruction::BinaryOps ShiftOpcode = Sh0->getOpcode();97 bool IdenticalShOpcodes = Sh0->getOpcode() == Sh1->getOpcode();98 if (!IdenticalShOpcodes && !AnalyzeForSignBitExtraction)99 return nullptr;100 101 // If we saw truncation, we'll need to produce extra instruction,102 // and for that one of the operands of the shift must be one-use,103 // unless of course we don't actually plan to produce any instructions here.104 if (Trunc && !AnalyzeForSignBitExtraction &&105 !match(Sh0, m_c_BinOp(m_OneUse(m_Value()), m_Value())))106 return nullptr;107 108 // Can we fold (ShAmt0+ShAmt1) ?109 auto *NewShAmt = dyn_cast_or_null<Constant>(110 simplifyAddInst(ShAmt0, ShAmt1, /*isNSW=*/false, /*isNUW=*/false,111 SQ.getWithInstruction(Sh0)));112 if (!NewShAmt)113 return nullptr; // Did not simplify.114 unsigned NewShAmtBitWidth = NewShAmt->getType()->getScalarSizeInBits();115 unsigned XBitWidth = X->getType()->getScalarSizeInBits();116 // Is the new shift amount smaller than the bit width of inner/new shift?117 if (!match(NewShAmt, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT,118 APInt(NewShAmtBitWidth, XBitWidth))))119 return nullptr; // FIXME: could perform constant-folding.120 121 // If there was a truncation, and we have a right-shift, we can only fold if122 // we are left with the original sign bit. Likewise, if we were just checking123 // that this is a sighbit extraction, this is the place to check it.124 // FIXME: zero shift amount is also legal here, but we can't *easily* check125 // more than one predicate so it's not really worth it.126 if (HadTwoRightShifts && (Trunc || AnalyzeForSignBitExtraction)) {127 // If it's not a sign bit extraction, then we're done.128 if (!match(NewShAmt,129 m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ,130 APInt(NewShAmtBitWidth, XBitWidth - 1))))131 return nullptr;132 // If it is, and that was the question, return the base value.133 if (AnalyzeForSignBitExtraction)134 return X;135 }136 137 assert(IdenticalShOpcodes && "Should not get here with different shifts.");138 139 if (NewShAmt->getType() != X->getType()) {140 NewShAmt = ConstantFoldCastOperand(Instruction::ZExt, NewShAmt,141 X->getType(), SQ.DL);142 if (!NewShAmt)143 return nullptr;144 }145 146 // All good, we can do this fold.147 BinaryOperator *NewShift = BinaryOperator::Create(ShiftOpcode, X, NewShAmt);148 149 // The flags can only be propagated if there wasn't a trunc.150 if (!Trunc) {151 // If the pattern did not involve trunc, and both of the original shifts152 // had the same flag set, preserve the flag.153 if (ShiftOpcode == Instruction::BinaryOps::Shl) {154 NewShift->setHasNoUnsignedWrap(Sh0->hasNoUnsignedWrap() &&155 Sh1->hasNoUnsignedWrap());156 NewShift->setHasNoSignedWrap(Sh0->hasNoSignedWrap() &&157 Sh1->hasNoSignedWrap());158 } else {159 NewShift->setIsExact(Sh0->isExact() && Sh1->isExact());160 }161 }162 163 Instruction *Ret = NewShift;164 if (Trunc) {165 Builder.Insert(NewShift);166 Ret = CastInst::Create(Instruction::Trunc, NewShift, Sh0->getType());167 }168 169 return Ret;170}171 172// If we have some pattern that leaves only some low bits set, and then performs173// left-shift of those bits, if none of the bits that are left after the final174// shift are modified by the mask, we can omit the mask.175//176// There are many variants to this pattern:177// a) (x & ((1 << MaskShAmt) - 1)) << ShiftShAmt178// b) (x & (~(-1 << MaskShAmt))) << ShiftShAmt179// c) (x & (-1 l>> MaskShAmt)) << ShiftShAmt180// d) (x & ((-1 << MaskShAmt) l>> MaskShAmt)) << ShiftShAmt181// e) ((x << MaskShAmt) l>> MaskShAmt) << ShiftShAmt182// f) ((x << MaskShAmt) a>> MaskShAmt) << ShiftShAmt183// All these patterns can be simplified to just:184// x << ShiftShAmt185// iff:186// a,b) (MaskShAmt+ShiftShAmt) u>= bitwidth(x)187// c,d,e,f) (ShiftShAmt-MaskShAmt) s>= 0 (i.e. ShiftShAmt u>= MaskShAmt)188static Instruction *189dropRedundantMaskingOfLeftShiftInput(BinaryOperator *OuterShift,190 const SimplifyQuery &Q,191 InstCombiner::BuilderTy &Builder) {192 assert(OuterShift->getOpcode() == Instruction::BinaryOps::Shl &&193 "The input must be 'shl'!");194 195 Value *Masked, *ShiftShAmt;196 match(OuterShift,197 m_Shift(m_Value(Masked), m_ZExtOrSelf(m_Value(ShiftShAmt))));198 199 // *If* there is a truncation between an outer shift and a possibly-mask,200 // then said truncation *must* be one-use, else we can't perform the fold.201 Value *Trunc;202 if (match(Masked, m_CombineAnd(m_Trunc(m_Value(Masked)), m_Value(Trunc))) &&203 !Trunc->hasOneUse())204 return nullptr;205 206 Type *NarrowestTy = OuterShift->getType();207 Type *WidestTy = Masked->getType();208 bool HadTrunc = WidestTy != NarrowestTy;209 210 // The mask must be computed in a type twice as wide to ensure211 // that no bits are lost if the sum-of-shifts is wider than the base type.212 Type *ExtendedTy = WidestTy->getExtendedType();213 214 Value *MaskShAmt;215 216 // ((1 << MaskShAmt) - 1)217 auto MaskA = m_Add(m_Shl(m_One(), m_Value(MaskShAmt)), m_AllOnes());218 // (~(-1 << maskNbits))219 auto MaskB = m_Not(m_Shl(m_AllOnes(), m_Value(MaskShAmt)));220 // (-1 l>> MaskShAmt)221 auto MaskC = m_LShr(m_AllOnes(), m_Value(MaskShAmt));222 // ((-1 << MaskShAmt) l>> MaskShAmt)223 auto MaskD =224 m_LShr(m_Shl(m_AllOnes(), m_Value(MaskShAmt)), m_Deferred(MaskShAmt));225 226 Value *X;227 Constant *NewMask;228 229 if (match(Masked, m_c_And(m_CombineOr(MaskA, MaskB), m_Value(X)))) {230 // Peek through an optional zext of the shift amount.231 match(MaskShAmt, m_ZExtOrSelf(m_Value(MaskShAmt)));232 233 // Verify that it would be safe to try to add those two shift amounts.234 if (!canTryToConstantAddTwoShiftAmounts(OuterShift, ShiftShAmt, Masked,235 MaskShAmt))236 return nullptr;237 238 // Can we simplify (MaskShAmt+ShiftShAmt) ?239 auto *SumOfShAmts = dyn_cast_or_null<Constant>(simplifyAddInst(240 MaskShAmt, ShiftShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q));241 if (!SumOfShAmts)242 return nullptr; // Did not simplify.243 // In this pattern SumOfShAmts correlates with the number of low bits244 // that shall remain in the root value (OuterShift).245 246 // An extend of an undef value becomes zero because the high bits are never247 // completely unknown. Replace the `undef` shift amounts with final248 // shift bitwidth to ensure that the value remains undef when creating the249 // subsequent shift op.250 SumOfShAmts = Constant::replaceUndefsWith(251 SumOfShAmts, ConstantInt::get(SumOfShAmts->getType()->getScalarType(),252 ExtendedTy->getScalarSizeInBits()));253 auto *ExtendedSumOfShAmts = ConstantFoldCastOperand(254 Instruction::ZExt, SumOfShAmts, ExtendedTy, Q.DL);255 if (!ExtendedSumOfShAmts)256 return nullptr;257 258 // And compute the mask as usual: ~(-1 << (SumOfShAmts))259 auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(ExtendedTy);260 Constant *ExtendedInvertedMask = ConstantFoldBinaryOpOperands(261 Instruction::Shl, ExtendedAllOnes, ExtendedSumOfShAmts, Q.DL);262 if (!ExtendedInvertedMask)263 return nullptr;264 265 NewMask = ConstantExpr::getNot(ExtendedInvertedMask);266 } else if (match(Masked, m_c_And(m_CombineOr(MaskC, MaskD), m_Value(X))) ||267 match(Masked, m_Shr(m_Shl(m_Value(X), m_Value(MaskShAmt)),268 m_Deferred(MaskShAmt)))) {269 // Peek through an optional zext of the shift amount.270 match(MaskShAmt, m_ZExtOrSelf(m_Value(MaskShAmt)));271 272 // Verify that it would be safe to try to add those two shift amounts.273 if (!canTryToConstantAddTwoShiftAmounts(OuterShift, ShiftShAmt, Masked,274 MaskShAmt))275 return nullptr;276 277 // Can we simplify (ShiftShAmt-MaskShAmt) ?278 auto *ShAmtsDiff = dyn_cast_or_null<Constant>(simplifySubInst(279 ShiftShAmt, MaskShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q));280 if (!ShAmtsDiff)281 return nullptr; // Did not simplify.282 // In this pattern ShAmtsDiff correlates with the number of high bits that283 // shall be unset in the root value (OuterShift).284 285 // An extend of an undef value becomes zero because the high bits are never286 // completely unknown. Replace the `undef` shift amounts with negated287 // bitwidth of innermost shift to ensure that the value remains undef when288 // creating the subsequent shift op.289 unsigned WidestTyBitWidth = WidestTy->getScalarSizeInBits();290 ShAmtsDiff = Constant::replaceUndefsWith(291 ShAmtsDiff, ConstantInt::get(ShAmtsDiff->getType()->getScalarType(),292 -WidestTyBitWidth));293 auto *ExtendedNumHighBitsToClear = ConstantFoldCastOperand(294 Instruction::ZExt,295 ConstantExpr::getSub(ConstantInt::get(ShAmtsDiff->getType(),296 WidestTyBitWidth,297 /*isSigned=*/false),298 ShAmtsDiff),299 ExtendedTy, Q.DL);300 if (!ExtendedNumHighBitsToClear)301 return nullptr;302 303 // And compute the mask as usual: (-1 l>> (NumHighBitsToClear))304 auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(ExtendedTy);305 NewMask = ConstantFoldBinaryOpOperands(Instruction::LShr, ExtendedAllOnes,306 ExtendedNumHighBitsToClear, Q.DL);307 if (!NewMask)308 return nullptr;309 } else310 return nullptr; // Don't know anything about this pattern.311 312 NewMask = ConstantExpr::getTrunc(NewMask, NarrowestTy);313 314 // Does this mask has any unset bits? If not then we can just not apply it.315 bool NeedMask = !match(NewMask, m_AllOnes());316 317 // If we need to apply a mask, there are several more restrictions we have.318 if (NeedMask) {319 // The old masking instruction must go away.320 if (!Masked->hasOneUse())321 return nullptr;322 // The original "masking" instruction must not have been`ashr`.323 if (match(Masked, m_AShr(m_Value(), m_Value())))324 return nullptr;325 }326 327 // If we need to apply truncation, let's do it first, since we can.328 // We have already ensured that the old truncation will go away.329 if (HadTrunc)330 X = Builder.CreateTrunc(X, NarrowestTy);331 332 // No 'NUW'/'NSW'! We no longer know that we won't shift-out non-0 bits.333 // We didn't change the Type of this outermost shift, so we can just do it.334 auto *NewShift = BinaryOperator::Create(OuterShift->getOpcode(), X,335 OuterShift->getOperand(1));336 if (!NeedMask)337 return NewShift;338 339 Builder.Insert(NewShift);340 return BinaryOperator::Create(Instruction::And, NewShift, NewMask);341}342 343/// If we have a shift-by-constant of a bin op (bitwise logic op or add/sub w/344/// shl) that itself has a shift-by-constant operand with identical opcode, we345/// may be able to convert that into 2 independent shifts followed by the logic346/// op. This eliminates a use of an intermediate value (reduces dependency347/// chain).348static Instruction *foldShiftOfShiftedBinOp(BinaryOperator &I,349 InstCombiner::BuilderTy &Builder) {350 assert(I.isShift() && "Expected a shift as input");351 auto *BinInst = dyn_cast<BinaryOperator>(I.getOperand(0));352 if (!BinInst ||353 (!BinInst->isBitwiseLogicOp() &&354 BinInst->getOpcode() != Instruction::Add &&355 BinInst->getOpcode() != Instruction::Sub) ||356 !BinInst->hasOneUse())357 return nullptr;358 359 Constant *C0, *C1;360 if (!match(I.getOperand(1), m_Constant(C1)))361 return nullptr;362 363 Instruction::BinaryOps ShiftOpcode = I.getOpcode();364 // Transform for add/sub only works with shl.365 if ((BinInst->getOpcode() == Instruction::Add ||366 BinInst->getOpcode() == Instruction::Sub) &&367 ShiftOpcode != Instruction::Shl)368 return nullptr;369 370 Type *Ty = I.getType();371 372 // Find a matching shift by constant. The fold is not valid if the sum373 // of the shift values equals or exceeds bitwidth.374 Value *X, *Y;375 auto matchFirstShift = [&](Value *V, Value *W) {376 unsigned Size = Ty->getScalarSizeInBits();377 APInt Threshold(Size, Size);378 return match(V, m_BinOp(ShiftOpcode, m_Value(X), m_Constant(C0))) &&379 (V->hasOneUse() || match(W, m_ImmConstant())) &&380 match(ConstantExpr::getAdd(C0, C1),381 m_SpecificInt_ICMP(ICmpInst::ICMP_ULT, Threshold));382 };383 384 // Logic ops and Add are commutative, so check each operand for a match. Sub385 // is not so we cannot reoder if we match operand(1) and need to keep the386 // operands in their original positions.387 bool FirstShiftIsOp1 = false;388 if (matchFirstShift(BinInst->getOperand(0), BinInst->getOperand(1)))389 Y = BinInst->getOperand(1);390 else if (matchFirstShift(BinInst->getOperand(1), BinInst->getOperand(0))) {391 Y = BinInst->getOperand(0);392 FirstShiftIsOp1 = BinInst->getOpcode() == Instruction::Sub;393 } else394 return nullptr;395 396 // shift (binop (shift X, C0), Y), C1 -> binop (shift X, C0+C1), (shift Y, C1)397 Constant *ShiftSumC = ConstantExpr::getAdd(C0, C1);398 Value *NewShift1 = Builder.CreateBinOp(ShiftOpcode, X, ShiftSumC);399 Value *NewShift2 = Builder.CreateBinOp(ShiftOpcode, Y, C1);400 Value *Op1 = FirstShiftIsOp1 ? NewShift2 : NewShift1;401 Value *Op2 = FirstShiftIsOp1 ? NewShift1 : NewShift2;402 return BinaryOperator::Create(BinInst->getOpcode(), Op1, Op2);403}404 405Instruction *InstCombinerImpl::commonShiftTransforms(BinaryOperator &I) {406 if (Instruction *Phi = foldBinopWithPhiOperands(I))407 return Phi;408 409 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);410 assert(Op0->getType() == Op1->getType());411 Type *Ty = I.getType();412 413 // If the shift amount is a one-use `sext`, we can demote it to `zext`.414 Value *Y;415 if (match(Op1, m_OneUse(m_SExt(m_Value(Y))))) {416 Value *NewExt = Builder.CreateZExt(Y, Ty, Op1->getName());417 return BinaryOperator::Create(I.getOpcode(), Op0, NewExt);418 }419 420 // See if we can fold away this shift.421 if (SimplifyDemandedInstructionBits(I))422 return &I;423 424 // Try to fold constant and into select arguments.425 if (isa<Constant>(Op0))426 if (SelectInst *SI = dyn_cast<SelectInst>(Op1))427 if (Instruction *R = FoldOpIntoSelect(I, SI))428 return R;429 430 Constant *CUI;431 if (match(Op1, m_ImmConstant(CUI)))432 if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I))433 return Res;434 435 if (auto *NewShift = cast_or_null<Instruction>(436 reassociateShiftAmtsOfTwoSameDirectionShifts(&I, SQ)))437 return NewShift;438 439 // Pre-shift a constant shifted by a variable amount with constant offset:440 // C shift (A add nuw C1) --> (C shift C1) shift A441 Value *A;442 Constant *C, *C1;443 if (match(Op0, m_Constant(C)) &&444 match(Op1, m_NUWAddLike(m_Value(A), m_Constant(C1)))) {445 Value *NewC = Builder.CreateBinOp(I.getOpcode(), C, C1);446 BinaryOperator *NewShiftOp = BinaryOperator::Create(I.getOpcode(), NewC, A);447 if (I.getOpcode() == Instruction::Shl) {448 NewShiftOp->setHasNoSignedWrap(I.hasNoSignedWrap());449 NewShiftOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());450 } else {451 NewShiftOp->setIsExact(I.isExact());452 }453 return NewShiftOp;454 }455 456 unsigned BitWidth = Ty->getScalarSizeInBits();457 458 const APInt *AC, *AddC;459 // Try to pre-shift a constant shifted by a variable amount added with a460 // negative number:461 // C << (X - AddC) --> (C >> AddC) << X462 // and463 // C >> (X - AddC) --> (C << AddC) >> X464 if (match(Op0, m_APInt(AC)) && match(Op1, m_Add(m_Value(A), m_APInt(AddC))) &&465 AddC->isNegative() && (-*AddC).ult(BitWidth)) {466 assert(!AC->isZero() && "Expected simplify of shifted zero");467 unsigned PosOffset = (-*AddC).getZExtValue();468 469 auto isSuitableForPreShift = [PosOffset, &I, AC]() {470 switch (I.getOpcode()) {471 default:472 return false;473 case Instruction::Shl:474 return (I.hasNoSignedWrap() || I.hasNoUnsignedWrap()) &&475 AC->eq(AC->lshr(PosOffset).shl(PosOffset));476 case Instruction::LShr:477 return I.isExact() && AC->eq(AC->shl(PosOffset).lshr(PosOffset));478 case Instruction::AShr:479 return I.isExact() && AC->eq(AC->shl(PosOffset).ashr(PosOffset));480 }481 };482 if (isSuitableForPreShift()) {483 Constant *NewC = ConstantInt::get(Ty, I.getOpcode() == Instruction::Shl484 ? AC->lshr(PosOffset)485 : AC->shl(PosOffset));486 BinaryOperator *NewShiftOp =487 BinaryOperator::Create(I.getOpcode(), NewC, A);488 if (I.getOpcode() == Instruction::Shl) {489 NewShiftOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());490 } else {491 NewShiftOp->setIsExact();492 }493 return NewShiftOp;494 }495 }496 497 // X shift (A srem C) -> X shift (A and (C - 1)) iff C is a power of 2.498 // Because shifts by negative values (which could occur if A were negative)499 // are undefined.500 if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Constant(C))) &&501 match(C, m_Power2())) {502 // FIXME: Should this get moved into SimplifyDemandedBits by saying we don't503 // demand the sign bit (and many others) here??504 Constant *Mask = ConstantExpr::getSub(C, ConstantInt::get(Ty, 1));505 Value *Rem = Builder.CreateAnd(A, Mask, Op1->getName());506 return replaceOperand(I, 1, Rem);507 }508 509 if (Instruction *Logic = foldShiftOfShiftedBinOp(I, Builder))510 return Logic;511 512 if (match(Op1, m_Or(m_Value(), m_SpecificInt(BitWidth - 1))))513 return replaceOperand(I, 1, ConstantInt::get(Ty, BitWidth - 1));514 515 Instruction *CmpIntr;516 if ((I.getOpcode() == Instruction::LShr ||517 I.getOpcode() == Instruction::AShr) &&518 match(Op0, m_OneUse(m_Instruction(CmpIntr))) &&519 isa<CmpIntrinsic>(CmpIntr) &&520 match(Op1, m_SpecificInt(Ty->getScalarSizeInBits() - 1))) {521 Value *Cmp =522 Builder.CreateICmp(cast<CmpIntrinsic>(CmpIntr)->getLTPredicate(),523 CmpIntr->getOperand(0), CmpIntr->getOperand(1));524 return CastInst::Create(I.getOpcode() == Instruction::LShr525 ? Instruction::ZExt526 : Instruction::SExt,527 Cmp, Ty);528 }529 530 return nullptr;531}532 533/// Return true if we can simplify two logical (either left or right) shifts534/// that have constant shift amounts: OuterShift (InnerShift X, C1), C2.535static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl,536 Instruction *InnerShift,537 InstCombinerImpl &IC, Instruction *CxtI) {538 assert(InnerShift->isLogicalShift() && "Unexpected instruction type");539 540 // We need constant scalar or constant splat shifts.541 const APInt *InnerShiftConst;542 if (!match(InnerShift->getOperand(1), m_APInt(InnerShiftConst)))543 return false;544 545 // Two logical shifts in the same direction:546 // shl (shl X, C1), C2 --> shl X, C1 + C2547 // lshr (lshr X, C1), C2 --> lshr X, C1 + C2548 bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;549 if (IsInnerShl == IsOuterShl)550 return true;551 552 // Equal shift amounts in opposite directions become bitwise 'and':553 // lshr (shl X, C), C --> and X, C'554 // shl (lshr X, C), C --> and X, C'555 if (*InnerShiftConst == OuterShAmt)556 return true;557 558 // If the 2nd shift is bigger than the 1st, we can fold:559 // lshr (shl X, C1), C2 --> and (shl X, C1 - C2), C3560 // shl (lshr X, C1), C2 --> and (lshr X, C1 - C2), C3561 // but it isn't profitable unless we know the and'd out bits are already zero.562 // Also, check that the inner shift is valid (less than the type width) or563 // we'll crash trying to produce the bit mask for the 'and'.564 unsigned TypeWidth = InnerShift->getType()->getScalarSizeInBits();565 if (InnerShiftConst->ugt(OuterShAmt) && InnerShiftConst->ult(TypeWidth)) {566 unsigned InnerShAmt = InnerShiftConst->getZExtValue();567 unsigned MaskShift =568 IsInnerShl ? TypeWidth - InnerShAmt : InnerShAmt - OuterShAmt;569 APInt Mask = APInt::getLowBitsSet(TypeWidth, OuterShAmt) << MaskShift;570 if (IC.MaskedValueIsZero(InnerShift->getOperand(0), Mask, CxtI))571 return true;572 }573 574 return false;575}576 577/// See if we can compute the specified value, but shifted logically to the left578/// or right by some number of bits. This should return true if the expression579/// can be computed for the same cost as the current expression tree. This is580/// used to eliminate extraneous shifting from things like:581/// %C = shl i128 %A, 64582/// %D = shl i128 %B, 96583/// %E = or i128 %C, %D584/// %F = lshr i128 %E, 64585/// where the client will ask if E can be computed shifted right by 64-bits. If586/// this succeeds, getShiftedValue() will be called to produce the value.587static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift,588 InstCombinerImpl &IC, Instruction *CxtI) {589 // We can always evaluate immediate constants.590 if (match(V, m_ImmConstant()))591 return true;592 593 Instruction *I = dyn_cast<Instruction>(V);594 if (!I) return false;595 596 // We can't mutate something that has multiple uses: doing so would597 // require duplicating the instruction in general, which isn't profitable.598 if (!I->hasOneUse()) return false;599 600 switch (I->getOpcode()) {601 default: return false;602 case Instruction::And:603 case Instruction::Or:604 case Instruction::Xor:605 // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.606 return canEvaluateShifted(I->getOperand(0), NumBits, IsLeftShift, IC, I) &&607 canEvaluateShifted(I->getOperand(1), NumBits, IsLeftShift, IC, I);608 609 case Instruction::Shl:610 case Instruction::LShr:611 return canEvaluateShiftedShift(NumBits, IsLeftShift, I, IC, CxtI);612 613 case Instruction::Select: {614 SelectInst *SI = cast<SelectInst>(I);615 Value *TrueVal = SI->getTrueValue();616 Value *FalseVal = SI->getFalseValue();617 return canEvaluateShifted(TrueVal, NumBits, IsLeftShift, IC, SI) &&618 canEvaluateShifted(FalseVal, NumBits, IsLeftShift, IC, SI);619 }620 case Instruction::PHI: {621 // We can change a phi if we can change all operands. Note that we never622 // get into trouble with cyclic PHIs here because we only consider623 // instructions with a single use.624 PHINode *PN = cast<PHINode>(I);625 for (Value *IncValue : PN->incoming_values())626 if (!canEvaluateShifted(IncValue, NumBits, IsLeftShift, IC, PN))627 return false;628 return true;629 }630 case Instruction::Mul: {631 const APInt *MulConst;632 // We can fold (shr (mul X, -(1 << C)), C) -> (and (neg X), C`)633 return !IsLeftShift && match(I->getOperand(1), m_APInt(MulConst)) &&634 MulConst->isNegatedPowerOf2() && MulConst->countr_zero() == NumBits;635 }636 }637}638 639/// Fold OuterShift (InnerShift X, C1), C2.640/// See canEvaluateShiftedShift() for the constraints on these instructions.641static Value *foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt,642 bool IsOuterShl,643 InstCombiner::BuilderTy &Builder) {644 bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;645 Type *ShType = InnerShift->getType();646 unsigned TypeWidth = ShType->getScalarSizeInBits();647 648 // We only accept shifts-by-a-constant in canEvaluateShifted().649 const APInt *C1;650 match(InnerShift->getOperand(1), m_APInt(C1));651 unsigned InnerShAmt = C1->getZExtValue();652 653 // Change the shift amount and clear the appropriate IR flags.654 auto NewInnerShift = [&](unsigned ShAmt) {655 InnerShift->setOperand(1, ConstantInt::get(ShType, ShAmt));656 if (IsInnerShl) {657 InnerShift->setHasNoUnsignedWrap(false);658 InnerShift->setHasNoSignedWrap(false);659 } else {660 InnerShift->setIsExact(false);661 }662 return InnerShift;663 };664 665 // Two logical shifts in the same direction:666 // shl (shl X, C1), C2 --> shl X, C1 + C2667 // lshr (lshr X, C1), C2 --> lshr X, C1 + C2668 if (IsInnerShl == IsOuterShl) {669 // If this is an oversized composite shift, then unsigned shifts get 0.670 if (InnerShAmt + OuterShAmt >= TypeWidth)671 return Constant::getNullValue(ShType);672 673 return NewInnerShift(InnerShAmt + OuterShAmt);674 }675 676 // Equal shift amounts in opposite directions become bitwise 'and':677 // lshr (shl X, C), C --> and X, C'678 // shl (lshr X, C), C --> and X, C'679 if (InnerShAmt == OuterShAmt) {680 APInt Mask = IsInnerShl681 ? APInt::getLowBitsSet(TypeWidth, TypeWidth - OuterShAmt)682 : APInt::getHighBitsSet(TypeWidth, TypeWidth - OuterShAmt);683 Value *And = Builder.CreateAnd(InnerShift->getOperand(0),684 ConstantInt::get(ShType, Mask));685 if (auto *AndI = dyn_cast<Instruction>(And)) {686 AndI->moveBefore(InnerShift->getIterator());687 AndI->takeName(InnerShift);688 }689 return And;690 }691 692 assert(InnerShAmt > OuterShAmt &&693 "Unexpected opposite direction logical shift pair");694 695 // In general, we would need an 'and' for this transform, but696 // canEvaluateShiftedShift() guarantees that the masked-off bits are not used.697 // lshr (shl X, C1), C2 --> shl X, C1 - C2698 // shl (lshr X, C1), C2 --> lshr X, C1 - C2699 return NewInnerShift(InnerShAmt - OuterShAmt);700}701 702/// When canEvaluateShifted() returns true for an expression, this function703/// inserts the new computation that produces the shifted value.704static Value *getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift,705 InstCombinerImpl &IC, const DataLayout &DL) {706 // We can always evaluate constants shifted.707 if (Constant *C = dyn_cast<Constant>(V)) {708 if (isLeftShift)709 return IC.Builder.CreateShl(C, NumBits);710 else711 return IC.Builder.CreateLShr(C, NumBits);712 }713 714 Instruction *I = cast<Instruction>(V);715 IC.addToWorklist(I);716 717 switch (I->getOpcode()) {718 default: llvm_unreachable("Inconsistency with CanEvaluateShifted");719 case Instruction::And:720 case Instruction::Or:721 case Instruction::Xor:722 // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.723 I->setOperand(724 0, getShiftedValue(I->getOperand(0), NumBits, isLeftShift, IC, DL));725 I->setOperand(726 1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));727 return I;728 729 case Instruction::Shl:730 case Instruction::LShr:731 return foldShiftedShift(cast<BinaryOperator>(I), NumBits, isLeftShift,732 IC.Builder);733 734 case Instruction::Select:735 I->setOperand(736 1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));737 I->setOperand(738 2, getShiftedValue(I->getOperand(2), NumBits, isLeftShift, IC, DL));739 return I;740 case Instruction::PHI: {741 // We can change a phi if we can change all operands. Note that we never742 // get into trouble with cyclic PHIs here because we only consider743 // instructions with a single use.744 PHINode *PN = cast<PHINode>(I);745 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)746 PN->setIncomingValue(i, getShiftedValue(PN->getIncomingValue(i), NumBits,747 isLeftShift, IC, DL));748 return PN;749 }750 case Instruction::Mul: {751 assert(!isLeftShift && "Unexpected shift direction!");752 auto *Neg = BinaryOperator::CreateNeg(I->getOperand(0));753 IC.InsertNewInstWith(Neg, I->getIterator());754 unsigned TypeWidth = I->getType()->getScalarSizeInBits();755 APInt Mask = APInt::getLowBitsSet(TypeWidth, TypeWidth - NumBits);756 auto *And = BinaryOperator::CreateAnd(Neg,757 ConstantInt::get(I->getType(), Mask));758 And->takeName(I);759 return IC.InsertNewInstWith(And, I->getIterator());760 }761 }762}763 764// If this is a bitwise operator or add with a constant RHS we might be able765// to pull it through a shift.766static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift,767 BinaryOperator *BO) {768 switch (BO->getOpcode()) {769 default:770 return false; // Do not perform transform!771 case Instruction::Add:772 return Shift.getOpcode() == Instruction::Shl;773 case Instruction::Or:774 case Instruction::And:775 return true;776 case Instruction::Xor:777 // Do not change a 'not' of logical shift because that would create a normal778 // 'xor'. The 'not' is likely better for analysis, SCEV, and codegen.779 return !(Shift.isLogicalShift() && match(BO, m_Not(m_Value())));780 }781}782 783Instruction *InstCombinerImpl::FoldShiftByConstant(Value *Op0, Constant *C1,784 BinaryOperator &I) {785 // (C2 << X) << C1 --> (C2 << C1) << X786 // (C2 >> X) >> C1 --> (C2 >> C1) >> X787 Constant *C2;788 Value *X;789 bool IsLeftShift = I.getOpcode() == Instruction::Shl;790 if (match(Op0, m_BinOp(I.getOpcode(), m_ImmConstant(C2), m_Value(X)))) {791 Instruction *R = BinaryOperator::Create(792 I.getOpcode(), Builder.CreateBinOp(I.getOpcode(), C2, C1), X);793 BinaryOperator *BO0 = cast<BinaryOperator>(Op0);794 if (IsLeftShift) {795 R->setHasNoUnsignedWrap(I.hasNoUnsignedWrap() &&796 BO0->hasNoUnsignedWrap());797 R->setHasNoSignedWrap(I.hasNoSignedWrap() && BO0->hasNoSignedWrap());798 } else799 R->setIsExact(I.isExact() && BO0->isExact());800 return R;801 }802 803 Type *Ty = I.getType();804 unsigned TypeBits = Ty->getScalarSizeInBits();805 806 // (X / +DivC) >> (Width - 1) --> ext (X <= -DivC)807 // (X / -DivC) >> (Width - 1) --> ext (X >= +DivC)808 const APInt *DivC;809 if (!IsLeftShift && match(C1, m_SpecificIntAllowPoison(TypeBits - 1)) &&810 match(Op0, m_SDiv(m_Value(X), m_APInt(DivC))) && !DivC->isZero() &&811 !DivC->isMinSignedValue()) {812 Constant *NegDivC = ConstantInt::get(Ty, -(*DivC));813 ICmpInst::Predicate Pred =814 DivC->isNegative() ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_SLE;815 Value *Cmp = Builder.CreateICmp(Pred, X, NegDivC);816 auto ExtOpcode = (I.getOpcode() == Instruction::AShr) ? Instruction::SExt817 : Instruction::ZExt;818 return CastInst::Create(ExtOpcode, Cmp, Ty);819 }820 821 const APInt *Op1C;822 if (!match(C1, m_APInt(Op1C)))823 return nullptr;824 825 assert(!Op1C->uge(TypeBits) &&826 "Shift over the type width should have been removed already");827 828 // See if we can propagate this shift into the input, this covers the trivial829 // cast of lshr(shl(x,c1),c2) as well as other more complex cases.830 if (I.getOpcode() != Instruction::AShr &&831 canEvaluateShifted(Op0, Op1C->getZExtValue(), IsLeftShift, *this, &I)) {832 LLVM_DEBUG(833 dbgs() << "ICE: GetShiftedValue propagating shift through expression"834 " to eliminate shift:\n IN: "835 << *Op0 << "\n SH: " << I << "\n");836 837 return replaceInstUsesWith(838 I, getShiftedValue(Op0, Op1C->getZExtValue(), IsLeftShift, *this, DL));839 }840 841 if (Instruction *FoldedShift = foldBinOpIntoSelectOrPhi(I))842 return FoldedShift;843 844 if (!Op0->hasOneUse())845 return nullptr;846 847 if (auto *Op0BO = dyn_cast<BinaryOperator>(Op0)) {848 // If the operand is a bitwise operator with a constant RHS, and the849 // shift is the only use, we can pull it out of the shift.850 const APInt *Op0C;851 if (match(Op0BO->getOperand(1), m_APInt(Op0C))) {852 if (canShiftBinOpWithConstantRHS(I, Op0BO)) {853 Value *NewRHS =854 Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(1), C1);855 856 Value *NewShift =857 Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), C1);858 NewShift->takeName(Op0BO);859 860 return BinaryOperator::Create(Op0BO->getOpcode(), NewShift, NewRHS);861 }862 }863 }864 865 // If we have a select that conditionally executes some binary operator,866 // see if we can pull it the select and operator through the shift.867 //868 // For example, turning:869 // shl (select C, (add X, C1), X), C2870 // Into:871 // Y = shl X, C2872 // select C, (add Y, C1 << C2), Y873 Value *Cond;874 BinaryOperator *TBO;875 Value *FalseVal;876 if (match(Op0, m_Select(m_Value(Cond), m_OneUse(m_BinOp(TBO)),877 m_Value(FalseVal)))) {878 const APInt *C;879 if (!isa<Constant>(FalseVal) && TBO->getOperand(0) == FalseVal &&880 match(TBO->getOperand(1), m_APInt(C)) &&881 canShiftBinOpWithConstantRHS(I, TBO)) {882 Value *NewRHS =883 Builder.CreateBinOp(I.getOpcode(), TBO->getOperand(1), C1);884 885 Value *NewShift = Builder.CreateBinOp(I.getOpcode(), FalseVal, C1);886 Value *NewOp = Builder.CreateBinOp(TBO->getOpcode(), NewShift, NewRHS);887 return SelectInst::Create(Cond, NewOp, NewShift);888 }889 }890 891 BinaryOperator *FBO;892 Value *TrueVal;893 if (match(Op0, m_Select(m_Value(Cond), m_Value(TrueVal),894 m_OneUse(m_BinOp(FBO))))) {895 const APInt *C;896 if (!isa<Constant>(TrueVal) && FBO->getOperand(0) == TrueVal &&897 match(FBO->getOperand(1), m_APInt(C)) &&898 canShiftBinOpWithConstantRHS(I, FBO)) {899 Value *NewRHS =900 Builder.CreateBinOp(I.getOpcode(), FBO->getOperand(1), C1);901 902 Value *NewShift = Builder.CreateBinOp(I.getOpcode(), TrueVal, C1);903 Value *NewOp = Builder.CreateBinOp(FBO->getOpcode(), NewShift, NewRHS);904 return SelectInst::Create(Cond, NewShift, NewOp);905 }906 }907 908 return nullptr;909}910 911// Tries to perform912// (lshr (add (zext X), (zext Y)), K)913// -> (icmp ult (add X, Y), X)914// where915// - The add's operands are zexts from a K-bits integer to a bigger type.916// - The add is only used by the shr, or by iK (or narrower) truncates.917// - The lshr type has more than 2 bits (other types are boolean math).918// - K > 1919// note that920// - The resulting add cannot have nuw/nsw, else on overflow we get a921// poison value and the transform isn't legal anymore.922Instruction *InstCombinerImpl::foldLShrOverflowBit(BinaryOperator &I) {923 assert(I.getOpcode() == Instruction::LShr);924 925 Value *Add = I.getOperand(0);926 Value *ShiftAmt = I.getOperand(1);927 Type *Ty = I.getType();928 929 if (Ty->getScalarSizeInBits() < 3)930 return nullptr;931 932 const APInt *ShAmtAPInt = nullptr;933 Value *X = nullptr, *Y = nullptr;934 if (!match(ShiftAmt, m_APInt(ShAmtAPInt)) ||935 !match(Add,936 m_Add(m_OneUse(m_ZExt(m_Value(X))), m_OneUse(m_ZExt(m_Value(Y))))))937 return nullptr;938 939 const unsigned ShAmt = ShAmtAPInt->getZExtValue();940 if (ShAmt == 1)941 return nullptr;942 943 // X/Y are zexts from `ShAmt`-sized ints.944 if (X->getType()->getScalarSizeInBits() != ShAmt ||945 Y->getType()->getScalarSizeInBits() != ShAmt)946 return nullptr;947 948 // Make sure that `Add` is only used by `I` and `ShAmt`-truncates.949 if (!Add->hasOneUse()) {950 for (User *U : Add->users()) {951 if (U == &I)952 continue;953 954 TruncInst *Trunc = dyn_cast<TruncInst>(U);955 if (!Trunc || Trunc->getType()->getScalarSizeInBits() > ShAmt)956 return nullptr;957 }958 }959 960 // Insert at Add so that the newly created `NarrowAdd` will dominate it's961 // users (i.e. `Add`'s users).962 Instruction *AddInst = cast<Instruction>(Add);963 Builder.SetInsertPoint(AddInst);964 965 Value *NarrowAdd = Builder.CreateAdd(X, Y, "add.narrowed");966 Value *Overflow =967 Builder.CreateICmpULT(NarrowAdd, X, "add.narrowed.overflow");968 969 // Replace the uses of the original add with a zext of the970 // NarrowAdd's result. Note that all users at this stage are known to971 // be ShAmt-sized truncs, or the lshr itself.972 if (!Add->hasOneUse()) {973 replaceInstUsesWith(*AddInst, Builder.CreateZExt(NarrowAdd, Ty));974 eraseInstFromFunction(*AddInst);975 }976 977 // Replace the LShr with a zext of the overflow check.978 return new ZExtInst(Overflow, Ty);979}980 981// Try to set nuw/nsw flags on shl or exact flag on lshr/ashr using knownbits.982static bool setShiftFlags(BinaryOperator &I, const SimplifyQuery &Q) {983 assert(I.isShift() && "Expected a shift as input");984 // We already have all the flags.985 if (I.getOpcode() == Instruction::Shl) {986 if (I.hasNoUnsignedWrap() && I.hasNoSignedWrap())987 return false;988 } else {989 if (I.isExact())990 return false;991 992 // shr (shl X, Y), Y993 if (match(I.getOperand(0), m_Shl(m_Value(), m_Specific(I.getOperand(1))))) {994 I.setIsExact();995 return true;996 }997 // Infer 'exact' flag if shift amount is cttz(x) on the same operand.998 if (match(I.getOperand(1), m_Intrinsic<Intrinsic::cttz>(999 m_Specific(I.getOperand(0)), m_Value()))) {1000 I.setIsExact();1001 return true;1002 }1003 }1004 1005 // Compute what we know about shift count.1006 KnownBits KnownCnt = computeKnownBits(I.getOperand(1), Q);1007 unsigned BitWidth = KnownCnt.getBitWidth();1008 // Since shift produces a poison value if RHS is equal to or larger than the1009 // bit width, we can safely assume that RHS is less than the bit width.1010 uint64_t MaxCnt = KnownCnt.getMaxValue().getLimitedValue(BitWidth - 1);1011 1012 KnownBits KnownAmt = computeKnownBits(I.getOperand(0), Q);1013 bool Changed = false;1014 1015 if (I.getOpcode() == Instruction::Shl) {1016 // If we have as many leading zeros than maximum shift cnt we have nuw.1017 if (!I.hasNoUnsignedWrap() && MaxCnt <= KnownAmt.countMinLeadingZeros()) {1018 I.setHasNoUnsignedWrap();1019 Changed = true;1020 }1021 // If we have more sign bits than maximum shift cnt we have nsw.1022 if (!I.hasNoSignedWrap()) {1023 if (MaxCnt < KnownAmt.countMinSignBits() ||1024 MaxCnt <1025 ComputeNumSignBits(I.getOperand(0), Q.DL, Q.AC, Q.CxtI, Q.DT)) {1026 I.setHasNoSignedWrap();1027 Changed = true;1028 }1029 }1030 return Changed;1031 }1032 1033 // If we have at least as many trailing zeros as maximum count then we have1034 // exact.1035 Changed = MaxCnt <= KnownAmt.countMinTrailingZeros();1036 I.setIsExact(Changed);1037 1038 return Changed;1039}1040 1041Instruction *InstCombinerImpl::visitShl(BinaryOperator &I) {1042 const SimplifyQuery Q = SQ.getWithInstruction(&I);1043 1044 if (Value *V = simplifyShlInst(I.getOperand(0), I.getOperand(1),1045 I.hasNoSignedWrap(), I.hasNoUnsignedWrap(), Q))1046 return replaceInstUsesWith(I, V);1047 1048 if (Instruction *X = foldVectorBinop(I))1049 return X;1050 1051 if (Instruction *V = commonShiftTransforms(I))1052 return V;1053 1054 if (Instruction *V = dropRedundantMaskingOfLeftShiftInput(&I, Q, Builder))1055 return V;1056 1057 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);1058 Type *Ty = I.getType();1059 unsigned BitWidth = Ty->getScalarSizeInBits();1060 1061 const APInt *C;1062 if (match(Op1, m_APInt(C))) {1063 unsigned ShAmtC = C->getZExtValue();1064 1065 // shl (zext X), C --> zext (shl X, C)1066 // This is only valid if X would have zeros shifted out.1067 Value *X;1068 if (match(Op0, m_OneUse(m_ZExt(m_Value(X))))) {1069 unsigned SrcWidth = X->getType()->getScalarSizeInBits();1070 if (ShAmtC < SrcWidth &&1071 MaskedValueIsZero(X, APInt::getHighBitsSet(SrcWidth, ShAmtC), &I))1072 return new ZExtInst(Builder.CreateShl(X, ShAmtC), Ty);1073 }1074 1075 // (X >> C) << C --> X & (-1 << C)1076 if (match(Op0, m_Shr(m_Value(X), m_Specific(Op1)))) {1077 APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC));1078 return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask));1079 }1080 1081 const APInt *C1;1082 if (match(Op0, m_Exact(m_Shr(m_Value(X), m_APInt(C1)))) &&1083 C1->ult(BitWidth)) {1084 unsigned ShrAmt = C1->getZExtValue();1085 if (ShrAmt < ShAmtC) {1086 // If C1 < C: (X >>?,exact C1) << C --> X << (C - C1)1087 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShrAmt);1088 auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);1089 NewShl->setHasNoUnsignedWrap(1090 I.hasNoUnsignedWrap() ||1091 (ShrAmt &&1092 cast<Instruction>(Op0)->getOpcode() == Instruction::LShr &&1093 I.hasNoSignedWrap()));1094 NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());1095 return NewShl;1096 }1097 if (ShrAmt > ShAmtC) {1098 // If C1 > C: (X >>?exact C1) << C --> X >>?exact (C1 - C)1099 Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmtC);1100 auto *NewShr = BinaryOperator::Create(1101 cast<BinaryOperator>(Op0)->getOpcode(), X, ShiftDiff);1102 NewShr->setIsExact(true);1103 return NewShr;1104 }1105 }1106 1107 if (match(Op0, m_OneUse(m_Shr(m_Value(X), m_APInt(C1)))) &&1108 C1->ult(BitWidth)) {1109 unsigned ShrAmt = C1->getZExtValue();1110 if (ShrAmt < ShAmtC) {1111 // If C1 < C: (X >>? C1) << C --> (X << (C - C1)) & (-1 << C)1112 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShrAmt);1113 auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);1114 NewShl->setHasNoUnsignedWrap(1115 I.hasNoUnsignedWrap() ||1116 (ShrAmt &&1117 cast<Instruction>(Op0)->getOpcode() == Instruction::LShr &&1118 I.hasNoSignedWrap()));1119 NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());1120 Builder.Insert(NewShl);1121 APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC));1122 return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask));1123 }1124 if (ShrAmt > ShAmtC) {1125 // If C1 > C: (X >>? C1) << C --> (X >>? (C1 - C)) & (-1 << C)1126 Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmtC);1127 auto *OldShr = cast<BinaryOperator>(Op0);1128 auto *NewShr =1129 BinaryOperator::Create(OldShr->getOpcode(), X, ShiftDiff);1130 NewShr->setIsExact(OldShr->isExact());1131 Builder.Insert(NewShr);1132 APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC));1133 return BinaryOperator::CreateAnd(NewShr, ConstantInt::get(Ty, Mask));1134 }1135 }1136 1137 // Similar to above, but look through an intermediate trunc instruction.1138 BinaryOperator *Shr;1139 if (match(Op0, m_OneUse(m_Trunc(m_OneUse(m_BinOp(Shr))))) &&1140 match(Shr, m_Shr(m_Value(X), m_APInt(C1)))) {1141 // The larger shift direction survives through the transform.1142 unsigned ShrAmtC = C1->getZExtValue();1143 unsigned ShDiff = ShrAmtC > ShAmtC ? ShrAmtC - ShAmtC : ShAmtC - ShrAmtC;1144 Constant *ShiftDiffC = ConstantInt::get(X->getType(), ShDiff);1145 auto ShiftOpc = ShrAmtC > ShAmtC ? Shr->getOpcode() : Instruction::Shl;1146 1147 // If C1 > C:1148 // (trunc (X >> C1)) << C --> (trunc (X >> (C1 - C))) && (-1 << C)1149 // If C > C1:1150 // (trunc (X >> C1)) << C --> (trunc (X << (C - C1))) && (-1 << C)1151 Value *NewShift = Builder.CreateBinOp(ShiftOpc, X, ShiftDiffC, "sh.diff");1152 Value *Trunc = Builder.CreateTrunc(NewShift, Ty, "tr.sh.diff");1153 APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC));1154 return BinaryOperator::CreateAnd(Trunc, ConstantInt::get(Ty, Mask));1155 }1156 1157 // If we have an opposite shift by the same amount, we may be able to1158 // reorder binops and shifts to eliminate math/logic.1159 auto isSuitableBinOpcode = [](Instruction::BinaryOps BinOpcode) {1160 switch (BinOpcode) {1161 default:1162 return false;1163 case Instruction::Add:1164 case Instruction::And:1165 case Instruction::Or:1166 case Instruction::Xor:1167 case Instruction::Sub:1168 // NOTE: Sub is not commutable and the tranforms below may not be valid1169 // when the shift-right is operand 1 (RHS) of the sub.1170 return true;1171 }1172 };1173 BinaryOperator *Op0BO;1174 if (match(Op0, m_OneUse(m_BinOp(Op0BO))) &&1175 isSuitableBinOpcode(Op0BO->getOpcode())) {1176 // Commute so shift-right is on LHS of the binop.1177 // (Y bop (X >> C)) << C -> ((X >> C) bop Y) << C1178 // (Y bop ((X >> C) & CC)) << C -> (((X >> C) & CC) bop Y) << C1179 Value *Shr = Op0BO->getOperand(0);1180 Value *Y = Op0BO->getOperand(1);1181 Value *X;1182 const APInt *CC;1183 if (Op0BO->isCommutative() && Y->hasOneUse() &&1184 (match(Y, m_Shr(m_Value(), m_Specific(Op1))) ||1185 match(Y, m_And(m_OneUse(m_Shr(m_Value(), m_Specific(Op1))),1186 m_APInt(CC)))))1187 std::swap(Shr, Y);1188 1189 // ((X >> C) bop Y) << C -> (X bop (Y << C)) & (~0 << C)1190 if (match(Shr, m_OneUse(m_Shr(m_Value(X), m_Specific(Op1))))) {1191 // Y << C1192 Value *YS = Builder.CreateShl(Y, Op1, Op0BO->getName());1193 // (X bop (Y << C))1194 Value *B =1195 Builder.CreateBinOp(Op0BO->getOpcode(), X, YS, Shr->getName());1196 unsigned Op1Val = C->getLimitedValue(BitWidth);1197 APInt Bits = APInt::getHighBitsSet(BitWidth, BitWidth - Op1Val);1198 Constant *Mask = ConstantInt::get(Ty, Bits);1199 return BinaryOperator::CreateAnd(B, Mask);1200 }1201 1202 // (((X >> C) & CC) bop Y) << C -> (X & (CC << C)) bop (Y << C)1203 if (match(Shr,1204 m_OneUse(m_And(m_OneUse(m_Shr(m_Value(X), m_Specific(Op1))),1205 m_APInt(CC))))) {1206 // Y << C1207 Value *YS = Builder.CreateShl(Y, Op1, Op0BO->getName());1208 // X & (CC << C)1209 Value *M = Builder.CreateAnd(X, ConstantInt::get(Ty, CC->shl(*C)),1210 X->getName() + ".mask");1211 auto *NewOp = BinaryOperator::Create(Op0BO->getOpcode(), M, YS);1212 if (auto *Disjoint = dyn_cast<PossiblyDisjointInst>(Op0BO);1213 Disjoint && Disjoint->isDisjoint())1214 cast<PossiblyDisjointInst>(NewOp)->setIsDisjoint(true);1215 return NewOp;1216 }1217 }1218 1219 // (C1 - X) << C --> (C1 << C) - (X << C)1220 if (match(Op0, m_OneUse(m_Sub(m_APInt(C1), m_Value(X))))) {1221 Constant *NewLHS = ConstantInt::get(Ty, C1->shl(*C));1222 Value *NewShift = Builder.CreateShl(X, Op1);1223 return BinaryOperator::CreateSub(NewLHS, NewShift);1224 }1225 }1226 1227 if (setShiftFlags(I, Q))1228 return &I;1229 1230 // Transform (x >> y) << y to x & (-1 << y)1231 // Valid for any type of right-shift.1232 Value *X;1233 if (match(Op0, m_OneUse(m_Shr(m_Value(X), m_Specific(Op1))))) {1234 Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);1235 Value *Mask = Builder.CreateShl(AllOnes, Op1);1236 return BinaryOperator::CreateAnd(Mask, X);1237 }1238 1239 // Transform (-1 >> y) << y to -1 << y1240 if (match(Op0, m_LShr(m_AllOnes(), m_Specific(Op1)))) {1241 Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);1242 return BinaryOperator::CreateShl(AllOnes, Op1);1243 }1244 1245 Constant *C1;1246 if (match(Op1, m_ImmConstant(C1))) {1247 Constant *C2;1248 Value *X;1249 // (X * C2) << C1 --> X * (C2 << C1)1250 if (match(Op0, m_Mul(m_Value(X), m_ImmConstant(C2))))1251 return BinaryOperator::CreateMul(X, Builder.CreateShl(C2, C1));1252 1253 // shl (zext i1 X), C1 --> select (X, 1 << C1, 0)1254 if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {1255 auto *NewC = Builder.CreateShl(ConstantInt::get(Ty, 1), C1);1256 return createSelectInstWithUnknownProfile(X, NewC,1257 ConstantInt::getNullValue(Ty));1258 }1259 }1260 1261 if (match(Op0, m_One())) {1262 // (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 11263 if (match(Op1, m_Sub(m_SpecificInt(BitWidth - 1), m_Value(X))))1264 return BinaryOperator::CreateLShr(1265 ConstantInt::get(Ty, APInt::getSignMask(BitWidth)), X);1266 1267 // Canonicalize "extract lowest set bit" using cttz to and-with-negate:1268 // 1 << (cttz X) --> -X & X1269 if (match(Op1,1270 m_OneUse(m_Intrinsic<Intrinsic::cttz>(m_Value(X), m_Value())))) {1271 Value *NegX = Builder.CreateNeg(X, "neg");1272 return BinaryOperator::CreateAnd(NegX, X);1273 }1274 }1275 1276 return nullptr;1277}1278 1279Instruction *InstCombinerImpl::visitLShr(BinaryOperator &I) {1280 if (Value *V = simplifyLShrInst(I.getOperand(0), I.getOperand(1), I.isExact(),1281 SQ.getWithInstruction(&I)))1282 return replaceInstUsesWith(I, V);1283 1284 if (Instruction *X = foldVectorBinop(I))1285 return X;1286 1287 if (Instruction *R = commonShiftTransforms(I))1288 return R;1289 1290 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);1291 Type *Ty = I.getType();1292 Value *X;1293 const APInt *C;1294 unsigned BitWidth = Ty->getScalarSizeInBits();1295 1296 // (iN (~X) u>> (N - 1)) --> zext (X > -1)1297 if (match(Op0, m_OneUse(m_Not(m_Value(X)))) &&1298 match(Op1, m_SpecificIntAllowPoison(BitWidth - 1)))1299 return new ZExtInst(Builder.CreateIsNotNeg(X, "isnotneg"), Ty);1300 1301 // ((X << nuw Z) sub nuw Y) >>u exact Z --> X sub nuw (Y >>u exact Z)1302 Value *Y;1303 if (I.isExact() &&1304 match(Op0, m_OneUse(m_NUWSub(m_NUWShl(m_Value(X), m_Specific(Op1)),1305 m_Value(Y))))) {1306 Value *NewLshr = Builder.CreateLShr(Y, Op1, "", /*isExact=*/true);1307 auto *NewSub = BinaryOperator::CreateNUWSub(X, NewLshr);1308 NewSub->setHasNoSignedWrap(1309 cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap());1310 return NewSub;1311 }1312 1313 // Fold (X + Y) / 2 --> (X & Y) iff (X u<= 1) && (Y u<= 1)1314 if (match(Op0, m_Add(m_Value(X), m_Value(Y))) && match(Op1, m_One()) &&1315 computeKnownBits(X, &I).countMaxActiveBits() <= 1 &&1316 computeKnownBits(Y, &I).countMaxActiveBits() <= 1)1317 return BinaryOperator::CreateAnd(X, Y);1318 1319 // (sub nuw X, (Y << nuw Z)) >>u exact Z --> (X >>u exact Z) sub nuw Y1320 if (I.isExact() &&1321 match(Op0, m_OneUse(m_NUWSub(m_Value(X),1322 m_NUWShl(m_Value(Y), m_Specific(Op1)))))) {1323 Value *NewLshr = Builder.CreateLShr(X, Op1, "", /*isExact=*/true);1324 auto *NewSub = BinaryOperator::CreateNUWSub(NewLshr, Y);1325 NewSub->setHasNoSignedWrap(1326 cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap());1327 return NewSub;1328 }1329 1330 auto isSuitableBinOpcode = [](Instruction::BinaryOps BinOpcode) {1331 switch (BinOpcode) {1332 default:1333 return false;1334 case Instruction::Add:1335 case Instruction::And:1336 case Instruction::Or:1337 case Instruction::Xor:1338 // Sub is handled separately.1339 return true;1340 }1341 };1342 1343 // If both the binop and the shift are nuw, then:1344 // ((X << nuw Z) binop nuw Y) >>u Z --> X binop nuw (Y >>u Z)1345 if (match(Op0, m_OneUse(m_c_BinOp(m_NUWShl(m_Value(X), m_Specific(Op1)),1346 m_Value(Y))))) {1347 BinaryOperator *Op0OB = cast<BinaryOperator>(Op0);1348 if (isSuitableBinOpcode(Op0OB->getOpcode())) {1349 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(Op0);1350 !OBO || OBO->hasNoUnsignedWrap()) {1351 Value *NewLshr = Builder.CreateLShr(1352 Y, Op1, "", I.isExact() && Op0OB->getOpcode() != Instruction::And);1353 auto *NewBinOp = BinaryOperator::Create(Op0OB->getOpcode(), NewLshr, X);1354 if (OBO) {1355 NewBinOp->setHasNoUnsignedWrap(true);1356 NewBinOp->setHasNoSignedWrap(OBO->hasNoSignedWrap());1357 } else if (auto *Disjoint = dyn_cast<PossiblyDisjointInst>(Op0)) {1358 cast<PossiblyDisjointInst>(NewBinOp)->setIsDisjoint(1359 Disjoint->isDisjoint());1360 }1361 return NewBinOp;1362 }1363 }1364 }1365 1366 if (match(Op1, m_APInt(C))) {1367 unsigned ShAmtC = C->getZExtValue();1368 auto *II = dyn_cast<IntrinsicInst>(Op0);1369 if (II && isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == ShAmtC &&1370 (II->getIntrinsicID() == Intrinsic::ctlz ||1371 II->getIntrinsicID() == Intrinsic::cttz ||1372 II->getIntrinsicID() == Intrinsic::ctpop)) {1373 // ctlz.i32(x)>>5 --> zext(x == 0)1374 // cttz.i32(x)>>5 --> zext(x == 0)1375 // ctpop.i32(x)>>5 --> zext(x == -1)1376 bool IsPop = II->getIntrinsicID() == Intrinsic::ctpop;1377 Constant *RHS = ConstantInt::getSigned(Ty, IsPop ? -1 : 0);1378 Value *Cmp = Builder.CreateICmpEQ(II->getArgOperand(0), RHS);1379 return new ZExtInst(Cmp, Ty);1380 }1381 1382 const APInt *C1;1383 if (match(Op0, m_Shl(m_Value(X), m_APInt(C1))) && C1->ult(BitWidth)) {1384 if (C1->ult(ShAmtC)) {1385 unsigned ShlAmtC = C1->getZExtValue();1386 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShlAmtC);1387 if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {1388 // (X <<nuw C1) >>u C --> X >>u (C - C1)1389 auto *NewLShr = BinaryOperator::CreateLShr(X, ShiftDiff);1390 NewLShr->setIsExact(I.isExact());1391 return NewLShr;1392 }1393 if (Op0->hasOneUse()) {1394 // (X << C1) >>u C --> (X >>u (C - C1)) & (-1 >> C)1395 Value *NewLShr = Builder.CreateLShr(X, ShiftDiff, "", I.isExact());1396 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC));1397 return BinaryOperator::CreateAnd(NewLShr, ConstantInt::get(Ty, Mask));1398 }1399 } else if (C1->ugt(ShAmtC)) {1400 unsigned ShlAmtC = C1->getZExtValue();1401 Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmtC - ShAmtC);1402 if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {1403 // (X <<nuw C1) >>u C --> X <<nuw/nsw (C1 - C)1404 auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);1405 NewShl->setHasNoUnsignedWrap(true);1406 NewShl->setHasNoSignedWrap(ShAmtC > 0);1407 return NewShl;1408 }1409 if (Op0->hasOneUse()) {1410 // (X << C1) >>u C --> X << (C1 - C) & (-1 >> C)1411 Value *NewShl = Builder.CreateShl(X, ShiftDiff);1412 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC));1413 return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask));1414 }1415 } else {1416 assert(*C1 == ShAmtC);1417 // (X << C) >>u C --> X & (-1 >>u C)1418 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC));1419 return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask));1420 }1421 }1422 1423 // ((X << C) + Y) >>u C --> (X + (Y >>u C)) & (-1 >>u C)1424 // TODO: Consolidate with the more general transform that starts from shl1425 // (the shifts are in the opposite order).1426 if (match(Op0,1427 m_OneUse(m_c_Add(m_OneUse(m_Shl(m_Value(X), m_Specific(Op1))),1428 m_Value(Y))))) {1429 Value *NewLshr = Builder.CreateLShr(Y, Op1);1430 Value *NewAdd = Builder.CreateAdd(NewLshr, X);1431 unsigned Op1Val = C->getLimitedValue(BitWidth);1432 APInt Bits = APInt::getLowBitsSet(BitWidth, BitWidth - Op1Val);1433 Constant *Mask = ConstantInt::get(Ty, Bits);1434 return BinaryOperator::CreateAnd(NewAdd, Mask);1435 }1436 1437 if (match(Op0, m_OneUse(m_ZExt(m_Value(X)))) &&1438 (!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType()))) {1439 assert(ShAmtC < X->getType()->getScalarSizeInBits() &&1440 "Big shift not simplified to zero?");1441 // lshr (zext iM X to iN), C --> zext (lshr X, C) to iN1442 Value *NewLShr = Builder.CreateLShr(X, ShAmtC);1443 return new ZExtInst(NewLShr, Ty);1444 }1445 1446 if (match(Op0, m_SExt(m_Value(X)))) {1447 unsigned SrcTyBitWidth = X->getType()->getScalarSizeInBits();1448 // lshr (sext i1 X to iN), C --> select (X, -1 >> C, 0)1449 if (SrcTyBitWidth == 1) {1450 auto *NewC = ConstantInt::get(1451 Ty, APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC));1452 return SelectInst::Create(X, NewC, ConstantInt::getNullValue(Ty));1453 }1454 1455 if ((!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType())) &&1456 Op0->hasOneUse()) {1457 // Are we moving the sign bit to the low bit and widening with high1458 // zeros? lshr (sext iM X to iN), N-1 --> zext (lshr X, M-1) to iN1459 if (ShAmtC == BitWidth - 1) {1460 Value *NewLShr = Builder.CreateLShr(X, SrcTyBitWidth - 1);1461 return new ZExtInst(NewLShr, Ty);1462 }1463 1464 // lshr (sext iM X to iN), N-M --> zext (ashr X, min(N-M, M-1)) to iN1465 if (ShAmtC == BitWidth - SrcTyBitWidth) {1466 // The new shift amount can't be more than the narrow source type.1467 unsigned NewShAmt = std::min(ShAmtC, SrcTyBitWidth - 1);1468 Value *AShr = Builder.CreateAShr(X, NewShAmt);1469 return new ZExtInst(AShr, Ty);1470 }1471 }1472 }1473 1474 if (ShAmtC == BitWidth - 1) {1475 // lshr i32 or(X,-X), 31 --> zext (X != 0)1476 if (match(Op0, m_OneUse(m_c_Or(m_Neg(m_Value(X)), m_Deferred(X)))))1477 return new ZExtInst(Builder.CreateIsNotNull(X), Ty);1478 1479 // lshr i32 (X -nsw Y), 31 --> zext (X < Y)1480 if (match(Op0, m_OneUse(m_NSWSub(m_Value(X), m_Value(Y)))))1481 return new ZExtInst(Builder.CreateICmpSLT(X, Y), Ty);1482 1483 // Check if a number is negative and odd:1484 // lshr i32 (srem X, 2), 31 --> and (X >> 31), X1485 if (match(Op0, m_OneUse(m_SRem(m_Value(X), m_SpecificInt(2))))) {1486 Value *Signbit = Builder.CreateLShr(X, ShAmtC);1487 return BinaryOperator::CreateAnd(Signbit, X);1488 }1489 1490 // lshr iN (X - 1) & ~X, N-1 --> zext (X == 0)1491 if (match(Op0, m_OneUse(m_c_And(m_Add(m_Value(X), m_AllOnes()),1492 m_Not(m_Deferred(X))))))1493 return new ZExtInst(Builder.CreateIsNull(X), Ty);1494 }1495 1496 Instruction *TruncSrc;1497 if (match(Op0, m_OneUse(m_Trunc(m_Instruction(TruncSrc)))) &&1498 match(TruncSrc, m_LShr(m_Value(X), m_APInt(C1)))) {1499 unsigned SrcWidth = X->getType()->getScalarSizeInBits();1500 unsigned AmtSum = ShAmtC + C1->getZExtValue();1501 1502 // If the combined shift fits in the source width:1503 // (trunc (X >>u C1)) >>u C --> and (trunc (X >>u (C1 + C)), MaskC1504 //1505 // If the first shift covers the number of bits truncated, then the1506 // mask instruction is eliminated (and so the use check is relaxed).1507 if (AmtSum < SrcWidth &&1508 (TruncSrc->hasOneUse() || C1->uge(SrcWidth - BitWidth))) {1509 Value *SumShift = Builder.CreateLShr(X, AmtSum, "sum.shift");1510 Value *Trunc = Builder.CreateTrunc(SumShift, Ty, I.getName());1511 1512 // If the first shift does not cover the number of bits truncated, then1513 // we require a mask to get rid of high bits in the result.1514 APInt MaskC = APInt::getAllOnes(BitWidth).lshr(ShAmtC);1515 return BinaryOperator::CreateAnd(Trunc, ConstantInt::get(Ty, MaskC));1516 }1517 }1518 1519 const APInt *MulC;1520 if (match(Op0, m_NUWMul(m_Value(X), m_APInt(MulC)))) {1521 if (BitWidth > 2 && (*MulC - 1).isPowerOf2() &&1522 MulC->logBase2() == ShAmtC) {1523 // Look for a "splat" mul pattern - it replicates bits across each half1524 // of a value, so a right shift simplifies back to just X:1525 // lshr i[2N] (mul nuw X, (2^N)+1), N --> X1526 if (ShAmtC * 2 == BitWidth)1527 return replaceInstUsesWith(I, X);1528 1529 // lshr (mul nuw (X, 2^N + 1)), N -> add nuw (X, lshr(X, N))1530 if (Op0->hasOneUse()) {1531 auto *NewAdd = BinaryOperator::CreateNUWAdd(1532 X, Builder.CreateLShr(X, ConstantInt::get(Ty, ShAmtC), "",1533 I.isExact()));1534 NewAdd->setHasNoSignedWrap(1535 cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap());1536 return NewAdd;1537 }1538 }1539 1540 // The one-use check is not strictly necessary, but codegen may not be1541 // able to invert the transform and perf may suffer with an extra mul1542 // instruction.1543 if (Op0->hasOneUse()) {1544 APInt NewMulC = MulC->lshr(ShAmtC);1545 // if c is divisible by (1 << ShAmtC):1546 // lshr (mul nuw x, MulC), ShAmtC -> mul nuw nsw x, (MulC >> ShAmtC)1547 if (MulC->eq(NewMulC.shl(ShAmtC))) {1548 auto *NewMul =1549 BinaryOperator::CreateNUWMul(X, ConstantInt::get(Ty, NewMulC));1550 assert(ShAmtC != 0 &&1551 "lshr X, 0 should be handled by simplifyLShrInst.");1552 NewMul->setHasNoSignedWrap(true);1553 return NewMul;1554 }1555 }1556 }1557 1558 // lshr (mul nsw (X, 2^N + 1)), N -> add nsw (X, lshr(X, N))1559 if (match(Op0, m_OneUse(m_NSWMul(m_Value(X), m_APInt(MulC))))) {1560 if (BitWidth > 2 && (*MulC - 1).isPowerOf2() &&1561 MulC->logBase2() == ShAmtC) {1562 return BinaryOperator::CreateNSWAdd(1563 X, Builder.CreateLShr(X, ConstantInt::get(Ty, ShAmtC), "",1564 I.isExact()));1565 }1566 }1567 1568 // Try to narrow bswap.1569 // In the case where the shift amount equals the bitwidth difference, the1570 // shift is eliminated.1571 if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::bswap>(1572 m_OneUse(m_ZExt(m_Value(X))))))) {1573 unsigned SrcWidth = X->getType()->getScalarSizeInBits();1574 unsigned WidthDiff = BitWidth - SrcWidth;1575 if (SrcWidth % 16 == 0) {1576 Value *NarrowSwap = Builder.CreateUnaryIntrinsic(Intrinsic::bswap, X);1577 if (ShAmtC >= WidthDiff) {1578 // (bswap (zext X)) >> C --> zext (bswap X >> C')1579 Value *NewShift = Builder.CreateLShr(NarrowSwap, ShAmtC - WidthDiff);1580 return new ZExtInst(NewShift, Ty);1581 } else {1582 // (bswap (zext X)) >> C --> (zext (bswap X)) << C'1583 Value *NewZExt = Builder.CreateZExt(NarrowSwap, Ty);1584 Constant *ShiftDiff = ConstantInt::get(Ty, WidthDiff - ShAmtC);1585 return BinaryOperator::CreateShl(NewZExt, ShiftDiff);1586 }1587 }1588 }1589 1590 // Reduce add-carry of bools to logic:1591 // ((zext BoolX) + (zext BoolY)) >> 1 --> zext (BoolX && BoolY)1592 Value *BoolX, *BoolY;1593 if (ShAmtC == 1 && match(Op0, m_Add(m_Value(X), m_Value(Y))) &&1594 match(X, m_ZExt(m_Value(BoolX))) && match(Y, m_ZExt(m_Value(BoolY))) &&1595 BoolX->getType()->isIntOrIntVectorTy(1) &&1596 BoolY->getType()->isIntOrIntVectorTy(1) &&1597 (X->hasOneUse() || Y->hasOneUse() || Op0->hasOneUse())) {1598 Value *And = Builder.CreateAnd(BoolX, BoolY);1599 return new ZExtInst(And, Ty);1600 }1601 }1602 1603 const SimplifyQuery Q = SQ.getWithInstruction(&I);1604 if (setShiftFlags(I, Q))1605 return &I;1606 1607 // Transform (x << y) >> y to x & (-1 >> y)1608 if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_Specific(Op1))))) {1609 Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);1610 Value *Mask = Builder.CreateLShr(AllOnes, Op1);1611 return BinaryOperator::CreateAnd(Mask, X);1612 }1613 1614 // Transform (-1 << y) >> y to -1 >> y1615 if (match(Op0, m_Shl(m_AllOnes(), m_Specific(Op1)))) {1616 Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);1617 return BinaryOperator::CreateLShr(AllOnes, Op1);1618 }1619 1620 if (Instruction *Overflow = foldLShrOverflowBit(I))1621 return Overflow;1622 1623 // Transform ((pow2 << x) >> cttz(pow2 << y)) -> ((1 << x) >> y)1624 Value *Shl0_Op0, *Shl0_Op1, *Shl1_Op1;1625 BinaryOperator *Shl1;1626 if (match(Op0, m_Shl(m_Value(Shl0_Op0), m_Value(Shl0_Op1))) &&1627 match(Op1, m_Intrinsic<Intrinsic::cttz>(m_BinOp(Shl1))) &&1628 match(Shl1, m_Shl(m_Specific(Shl0_Op0), m_Value(Shl1_Op1))) &&1629 isKnownToBeAPowerOfTwo(Shl0_Op0, /*OrZero=*/true, &I)) {1630 auto *Shl0 = cast<BinaryOperator>(Op0);1631 bool HasNUW = Shl0->hasNoUnsignedWrap() && Shl1->hasNoUnsignedWrap();1632 bool HasNSW = Shl0->hasNoSignedWrap() && Shl1->hasNoSignedWrap();1633 if (HasNUW || HasNSW) {1634 Value *NewShl = Builder.CreateShl(ConstantInt::get(Shl1->getType(), 1),1635 Shl0_Op1, "", HasNUW, HasNSW);1636 return BinaryOperator::CreateLShr(NewShl, Shl1_Op1);1637 }1638 }1639 return nullptr;1640}1641 1642Instruction *1643InstCombinerImpl::foldVariableSignZeroExtensionOfVariableHighBitExtract(1644 BinaryOperator &OldAShr) {1645 assert(OldAShr.getOpcode() == Instruction::AShr &&1646 "Must be called with arithmetic right-shift instruction only.");1647 1648 // Check that constant C is a splat of the element-wise bitwidth of V.1649 auto BitWidthSplat = [](Constant *C, Value *V) {1650 return match(1651 C, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ,1652 APInt(C->getType()->getScalarSizeInBits(),1653 V->getType()->getScalarSizeInBits())));1654 };1655 1656 // It should look like variable-length sign-extension on the outside:1657 // (Val << (bitwidth(Val)-Nbits)) a>> (bitwidth(Val)-Nbits)1658 Value *NBits;1659 Instruction *MaybeTrunc;1660 Constant *C1, *C2;1661 if (!match(&OldAShr,1662 m_AShr(m_Shl(m_Instruction(MaybeTrunc),1663 m_ZExtOrSelf(m_Sub(m_Constant(C1),1664 m_ZExtOrSelf(m_Value(NBits))))),1665 m_ZExtOrSelf(m_Sub(m_Constant(C2),1666 m_ZExtOrSelf(m_Deferred(NBits)))))) ||1667 !BitWidthSplat(C1, &OldAShr) || !BitWidthSplat(C2, &OldAShr))1668 return nullptr;1669 1670 // There may or may not be a truncation after outer two shifts.1671 Instruction *HighBitExtract;1672 match(MaybeTrunc, m_TruncOrSelf(m_Instruction(HighBitExtract)));1673 bool HadTrunc = MaybeTrunc != HighBitExtract;1674 1675 // And finally, the innermost part of the pattern must be a right-shift.1676 Value *X, *NumLowBitsToSkip;1677 if (!match(HighBitExtract, m_Shr(m_Value(X), m_Value(NumLowBitsToSkip))))1678 return nullptr;1679 1680 // Said right-shift must extract high NBits bits - C0 must be it's bitwidth.1681 Constant *C0;1682 if (!match(NumLowBitsToSkip,1683 m_ZExtOrSelf(1684 m_Sub(m_Constant(C0), m_ZExtOrSelf(m_Specific(NBits))))) ||1685 !BitWidthSplat(C0, HighBitExtract))1686 return nullptr;1687 1688 // Since the NBits is identical for all shifts, if the outermost and1689 // innermost shifts are identical, then outermost shifts are redundant.1690 // If we had truncation, do keep it though.1691 if (HighBitExtract->getOpcode() == OldAShr.getOpcode())1692 return replaceInstUsesWith(OldAShr, MaybeTrunc);1693 1694 // Else, if there was a truncation, then we need to ensure that one1695 // instruction will go away.1696 if (HadTrunc && !match(&OldAShr, m_c_BinOp(m_OneUse(m_Value()), m_Value())))1697 return nullptr;1698 1699 // Finally, bypass two innermost shifts, and perform the outermost shift on1700 // the operands of the innermost shift.1701 Instruction *NewAShr =1702 BinaryOperator::Create(OldAShr.getOpcode(), X, NumLowBitsToSkip);1703 NewAShr->copyIRFlags(HighBitExtract); // We can preserve 'exact'-ness.1704 if (!HadTrunc)1705 return NewAShr;1706 1707 Builder.Insert(NewAShr);1708 return TruncInst::CreateTruncOrBitCast(NewAShr, OldAShr.getType());1709}1710 1711Instruction *InstCombinerImpl::visitAShr(BinaryOperator &I) {1712 if (Value *V = simplifyAShrInst(I.getOperand(0), I.getOperand(1), I.isExact(),1713 SQ.getWithInstruction(&I)))1714 return replaceInstUsesWith(I, V);1715 1716 if (Instruction *X = foldVectorBinop(I))1717 return X;1718 1719 if (Instruction *R = commonShiftTransforms(I))1720 return R;1721 1722 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);1723 Type *Ty = I.getType();1724 unsigned BitWidth = Ty->getScalarSizeInBits();1725 const APInt *ShAmtAPInt;1726 if (match(Op1, m_APInt(ShAmtAPInt)) && ShAmtAPInt->ult(BitWidth)) {1727 unsigned ShAmt = ShAmtAPInt->getZExtValue();1728 1729 // If the shift amount equals the difference in width of the destination1730 // and source scalar types:1731 // ashr (shl (zext X), C), C --> sext X1732 Value *X;1733 if (match(Op0, m_Shl(m_ZExt(m_Value(X)), m_Specific(Op1))) &&1734 ShAmt == BitWidth - X->getType()->getScalarSizeInBits())1735 return new SExtInst(X, Ty);1736 1737 // We can't handle (X << C1) >>s C2. It shifts arbitrary bits in. However,1738 // we can handle (X <<nsw C1) >>s C2 since it only shifts in sign bits.1739 const APInt *ShOp1;1740 if (match(Op0, m_NSWShl(m_Value(X), m_APInt(ShOp1))) &&1741 ShOp1->ult(BitWidth)) {1742 unsigned ShlAmt = ShOp1->getZExtValue();1743 if (ShlAmt < ShAmt) {1744 // (X <<nsw C1) >>s C2 --> X >>s (C2 - C1)1745 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt);1746 auto *NewAShr = BinaryOperator::CreateAShr(X, ShiftDiff);1747 NewAShr->setIsExact(I.isExact());1748 return NewAShr;1749 }1750 if (ShlAmt > ShAmt) {1751 // (X <<nsw C1) >>s C2 --> X <<nsw (C1 - C2)1752 Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt);1753 auto *NewShl = BinaryOperator::Create(Instruction::Shl, X, ShiftDiff);1754 NewShl->setHasNoSignedWrap(true);1755 return NewShl;1756 }1757 }1758 1759 if (match(Op0, m_AShr(m_Value(X), m_APInt(ShOp1))) &&1760 ShOp1->ult(BitWidth)) {1761 unsigned AmtSum = ShAmt + ShOp1->getZExtValue();1762 // Oversized arithmetic shifts replicate the sign bit.1763 AmtSum = std::min(AmtSum, BitWidth - 1);1764 // (X >>s C1) >>s C2 --> X >>s (C1 + C2)1765 return BinaryOperator::CreateAShr(X, ConstantInt::get(Ty, AmtSum));1766 }1767 1768 if (match(Op0, m_OneUse(m_SExt(m_Value(X)))) &&1769 (Ty->isVectorTy() || shouldChangeType(Ty, X->getType()))) {1770 // ashr (sext X), C --> sext (ashr X, C')1771 Type *SrcTy = X->getType();1772 ShAmt = std::min(ShAmt, SrcTy->getScalarSizeInBits() - 1);1773 Value *NewSh = Builder.CreateAShr(X, ConstantInt::get(SrcTy, ShAmt));1774 return new SExtInst(NewSh, Ty);1775 }1776 1777 if (ShAmt == BitWidth - 1) {1778 // ashr i32 or(X,-X), 31 --> sext (X != 0)1779 if (match(Op0, m_OneUse(m_c_Or(m_Neg(m_Value(X)), m_Deferred(X)))))1780 return new SExtInst(Builder.CreateIsNotNull(X), Ty);1781 1782 // ashr i32 (X -nsw Y), 31 --> sext (X < Y)1783 Value *Y;1784 if (match(Op0, m_OneUse(m_NSWSub(m_Value(X), m_Value(Y)))))1785 return new SExtInst(Builder.CreateICmpSLT(X, Y), Ty);1786 1787 // ashr iN (X - 1) & ~X, N-1 --> sext (X == 0)1788 if (match(Op0, m_OneUse(m_c_And(m_Add(m_Value(X), m_AllOnes()),1789 m_Not(m_Deferred(X))))))1790 return new SExtInst(Builder.CreateIsNull(X), Ty);1791 }1792 1793 const APInt *MulC;1794 if (match(Op0, m_OneUse(m_NSWMul(m_Value(X), m_APInt(MulC)))) &&1795 (BitWidth > 2 && (*MulC - 1).isPowerOf2() &&1796 MulC->logBase2() == ShAmt &&1797 (ShAmt < BitWidth - 1))) /* Minus 1 for the sign bit */ {1798 1799 // ashr (mul nsw (X, 2^N + 1)), N -> add nsw (X, ashr(X, N))1800 auto *NewAdd = BinaryOperator::CreateNSWAdd(1801 X,1802 Builder.CreateAShr(X, ConstantInt::get(Ty, ShAmt), "", I.isExact()));1803 NewAdd->setHasNoUnsignedWrap(1804 cast<OverflowingBinaryOperator>(Op0)->hasNoUnsignedWrap());1805 return NewAdd;1806 }1807 }1808 1809 const SimplifyQuery Q = SQ.getWithInstruction(&I);1810 if (setShiftFlags(I, Q))1811 return &I;1812 1813 // Prefer `-(x & 1)` over `(x << (bitwidth(x)-1)) a>> (bitwidth(x)-1)`1814 // as the pattern to splat the lowest bit.1815 // FIXME: iff X is already masked, we don't need the one-use check.1816 Value *X;1817 if (match(Op1, m_SpecificIntAllowPoison(BitWidth - 1)) &&1818 match(Op0, m_OneUse(m_Shl(m_Value(X),1819 m_SpecificIntAllowPoison(BitWidth - 1))))) {1820 Constant *Mask = ConstantInt::get(Ty, 1);1821 // Retain the knowledge about the ignored lanes.1822 Mask = Constant::mergeUndefsWith(1823 Constant::mergeUndefsWith(Mask, cast<Constant>(Op1)),1824 cast<Constant>(cast<Instruction>(Op0)->getOperand(1)));1825 X = Builder.CreateAnd(X, Mask);1826 return BinaryOperator::CreateNeg(X);1827 }1828 1829 if (Instruction *R = foldVariableSignZeroExtensionOfVariableHighBitExtract(I))1830 return R;1831 1832 // See if we can turn a signed shr into an unsigned shr.1833 if (MaskedValueIsZero(Op0, APInt::getSignMask(BitWidth), &I)) {1834 Instruction *Lshr = BinaryOperator::CreateLShr(Op0, Op1);1835 Lshr->setIsExact(I.isExact());1836 return Lshr;1837 }1838 1839 // ashr (xor %x, -1), %y --> xor (ashr %x, %y), -11840 if (match(Op0, m_OneUse(m_Not(m_Value(X))))) {1841 // Note that we must drop 'exact'-ness of the shift!1842 // Note that we can't keep undef's in -1 vector constant!1843 auto *NewAShr = Builder.CreateAShr(X, Op1, Op0->getName() + ".not");1844 return BinaryOperator::CreateNot(NewAShr);1845 }1846 1847 return nullptr;1848}1849