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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the visitShl, visitLShr, and visitAShr functions. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "InstCombineInternal.h" 14 #include "llvm/Analysis/ConstantFolding.h" 15 #include "llvm/Analysis/InstructionSimplify.h" 16 #include "llvm/IR/IntrinsicInst.h" 17 #include "llvm/IR/PatternMatch.h" 18 #include "llvm/Transforms/InstCombine/InstCombiner.h" 19 using namespace llvm; 20 using namespace PatternMatch; 21 22 #define DEBUG_TYPE "instcombine" 23 24 bool canTryToConstantAddTwoShiftAmounts(Value *Sh0, Value *ShAmt0, Value *Sh1, 25 Value *ShAmt1) { 26 // We have two shift amounts from two different shifts. The types of those 27 // shift amounts may not match. If that's the case let's bailout now.. 28 if (ShAmt0->getType() != ShAmt1->getType()) 29 return false; 30 31 // As input, we have the following pattern: 32 // Sh0 (Sh1 X, Q), K 33 // We want to rewrite that as: 34 // Sh x, (Q+K) iff (Q+K) u< bitwidth(x) 35 // While we know that originally (Q+K) would not overflow 36 // (because 2 * (N-1) u<= iN -1), we have looked past extensions of 37 // shift amounts. so it may now overflow in smaller bitwidth. 38 // To ensure that does not happen, we need to ensure that the total maximal 39 // shift amount is still representable in that smaller bit width. 40 unsigned MaximalPossibleTotalShiftAmount = 41 (Sh0->getType()->getScalarSizeInBits() - 1) + 42 (Sh1->getType()->getScalarSizeInBits() - 1); 43 APInt MaximalRepresentableShiftAmount = 44 APInt::getAllOnesValue(ShAmt0->getType()->getScalarSizeInBits()); 45 return MaximalRepresentableShiftAmount.uge(MaximalPossibleTotalShiftAmount); 46 } 47 48 // Given pattern: 49 // (x shiftopcode Q) shiftopcode K 50 // we should rewrite it as 51 // x shiftopcode (Q+K) iff (Q+K) u< bitwidth(x) and 52 // 53 // This is valid for any shift, but they must be identical, and we must be 54 // careful in case we have (zext(Q)+zext(K)) and look past extensions, 55 // (Q+K) must not overflow or else (Q+K) u< bitwidth(x) is bogus. 56 // 57 // AnalyzeForSignBitExtraction indicates that we will only analyze whether this 58 // pattern has any 2 right-shifts that sum to 1 less than original bit width. 59 Value *InstCombinerImpl::reassociateShiftAmtsOfTwoSameDirectionShifts( 60 BinaryOperator *Sh0, const SimplifyQuery &SQ, 61 bool AnalyzeForSignBitExtraction) { 62 // Look for a shift of some instruction, ignore zext of shift amount if any. 63 Instruction *Sh0Op0; 64 Value *ShAmt0; 65 if (!match(Sh0, 66 m_Shift(m_Instruction(Sh0Op0), m_ZExtOrSelf(m_Value(ShAmt0))))) 67 return nullptr; 68 69 // If there is a truncation between the two shifts, we must make note of it 70 // and look through it. The truncation imposes additional constraints on the 71 // transform. 72 Instruction *Sh1; 73 Value *Trunc = nullptr; 74 match(Sh0Op0, 75 m_CombineOr(m_CombineAnd(m_Trunc(m_Instruction(Sh1)), m_Value(Trunc)), 76 m_Instruction(Sh1))); 77 78 // Inner shift: (x shiftopcode ShAmt1) 79 // Like with other shift, ignore zext of shift amount if any. 80 Value *X, *ShAmt1; 81 if (!match(Sh1, m_Shift(m_Value(X), m_ZExtOrSelf(m_Value(ShAmt1))))) 82 return nullptr; 83 84 // Verify that it would be safe to try to add those two shift amounts. 85 if (!canTryToConstantAddTwoShiftAmounts(Sh0, ShAmt0, Sh1, ShAmt1)) 86 return nullptr; 87 88 // We are only looking for signbit extraction if we have two right shifts. 89 bool HadTwoRightShifts = match(Sh0, m_Shr(m_Value(), m_Value())) && 90 match(Sh1, m_Shr(m_Value(), m_Value())); 91 // ... and if it's not two right-shifts, we know the answer already. 92 if (AnalyzeForSignBitExtraction && !HadTwoRightShifts) 93 return nullptr; 94 95 // The shift opcodes must be identical, unless we are just checking whether 96 // this pattern can be interpreted as a sign-bit-extraction. 97 Instruction::BinaryOps ShiftOpcode = Sh0->getOpcode(); 98 bool IdenticalShOpcodes = Sh0->getOpcode() == Sh1->getOpcode(); 99 if (!IdenticalShOpcodes && !AnalyzeForSignBitExtraction) 100 return nullptr; 101 102 // If we saw truncation, we'll need to produce extra instruction, 103 // and for that one of the operands of the shift must be one-use, 104 // unless of course we don't actually plan to produce any instructions here. 105 if (Trunc && !AnalyzeForSignBitExtraction && 106 !match(Sh0, m_c_BinOp(m_OneUse(m_Value()), m_Value()))) 107 return nullptr; 108 109 // Can we fold (ShAmt0+ShAmt1) ? 110 auto *NewShAmt = dyn_cast_or_null<Constant>( 111 SimplifyAddInst(ShAmt0, ShAmt1, /*isNSW=*/false, /*isNUW=*/false, 112 SQ.getWithInstruction(Sh0))); 113 if (!NewShAmt) 114 return nullptr; // Did not simplify. 115 unsigned NewShAmtBitWidth = NewShAmt->getType()->getScalarSizeInBits(); 116 unsigned XBitWidth = X->getType()->getScalarSizeInBits(); 117 // Is the new shift amount smaller than the bit width of inner/new shift? 118 if (!match(NewShAmt, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT, 119 APInt(NewShAmtBitWidth, XBitWidth)))) 120 return nullptr; // FIXME: could perform constant-folding. 121 122 // If there was a truncation, and we have a right-shift, we can only fold if 123 // we are left with the original sign bit. Likewise, if we were just checking 124 // that this is a sighbit extraction, this is the place to check it. 125 // FIXME: zero shift amount is also legal here, but we can't *easily* check 126 // more than one predicate so it's not really worth it. 127 if (HadTwoRightShifts && (Trunc || AnalyzeForSignBitExtraction)) { 128 // If it's not a sign bit extraction, then we're done. 129 if (!match(NewShAmt, 130 m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ, 131 APInt(NewShAmtBitWidth, XBitWidth - 1)))) 132 return nullptr; 133 // If it is, and that was the question, return the base value. 134 if (AnalyzeForSignBitExtraction) 135 return X; 136 } 137 138 assert(IdenticalShOpcodes && "Should not get here with different shifts."); 139 140 // All good, we can do this fold. 141 NewShAmt = ConstantExpr::getZExtOrBitCast(NewShAmt, X->getType()); 142 143 BinaryOperator *NewShift = BinaryOperator::Create(ShiftOpcode, X, NewShAmt); 144 145 // The flags can only be propagated if there wasn't a trunc. 146 if (!Trunc) { 147 // If the pattern did not involve trunc, and both of the original shifts 148 // had the same flag set, preserve the flag. 149 if (ShiftOpcode == Instruction::BinaryOps::Shl) { 150 NewShift->setHasNoUnsignedWrap(Sh0->hasNoUnsignedWrap() && 151 Sh1->hasNoUnsignedWrap()); 152 NewShift->setHasNoSignedWrap(Sh0->hasNoSignedWrap() && 153 Sh1->hasNoSignedWrap()); 154 } else { 155 NewShift->setIsExact(Sh0->isExact() && Sh1->isExact()); 156 } 157 } 158 159 Instruction *Ret = NewShift; 160 if (Trunc) { 161 Builder.Insert(NewShift); 162 Ret = CastInst::Create(Instruction::Trunc, NewShift, Sh0->getType()); 163 } 164 165 return Ret; 166 } 167 168 // If we have some pattern that leaves only some low bits set, and then performs 169 // left-shift of those bits, if none of the bits that are left after the final 170 // shift are modified by the mask, we can omit the mask. 171 // 172 // There are many variants to this pattern: 173 // a) (x & ((1 << MaskShAmt) - 1)) << ShiftShAmt 174 // b) (x & (~(-1 << MaskShAmt))) << ShiftShAmt 175 // c) (x & (-1 >> MaskShAmt)) << ShiftShAmt 176 // d) (x & ((-1 << MaskShAmt) >> MaskShAmt)) << ShiftShAmt 177 // e) ((x << MaskShAmt) l>> MaskShAmt) << ShiftShAmt 178 // f) ((x << MaskShAmt) a>> MaskShAmt) << ShiftShAmt 179 // All these patterns can be simplified to just: 180 // x << ShiftShAmt 181 // iff: 182 // a,b) (MaskShAmt+ShiftShAmt) u>= bitwidth(x) 183 // c,d,e,f) (ShiftShAmt-MaskShAmt) s>= 0 (i.e. ShiftShAmt u>= MaskShAmt) 184 static Instruction * 185 dropRedundantMaskingOfLeftShiftInput(BinaryOperator *OuterShift, 186 const SimplifyQuery &Q, 187 InstCombiner::BuilderTy &Builder) { 188 assert(OuterShift->getOpcode() == Instruction::BinaryOps::Shl && 189 "The input must be 'shl'!"); 190 191 Value *Masked, *ShiftShAmt; 192 match(OuterShift, 193 m_Shift(m_Value(Masked), m_ZExtOrSelf(m_Value(ShiftShAmt)))); 194 195 // *If* there is a truncation between an outer shift and a possibly-mask, 196 // then said truncation *must* be one-use, else we can't perform the fold. 197 Value *Trunc; 198 if (match(Masked, m_CombineAnd(m_Trunc(m_Value(Masked)), m_Value(Trunc))) && 199 !Trunc->hasOneUse()) 200 return nullptr; 201 202 Type *NarrowestTy = OuterShift->getType(); 203 Type *WidestTy = Masked->getType(); 204 bool HadTrunc = WidestTy != NarrowestTy; 205 206 // The mask must be computed in a type twice as wide to ensure 207 // that no bits are lost if the sum-of-shifts is wider than the base type. 208 Type *ExtendedTy = WidestTy->getExtendedType(); 209 210 Value *MaskShAmt; 211 212 // ((1 << MaskShAmt) - 1) 213 auto MaskA = m_Add(m_Shl(m_One(), m_Value(MaskShAmt)), m_AllOnes()); 214 // (~(-1 << maskNbits)) 215 auto MaskB = m_Xor(m_Shl(m_AllOnes(), m_Value(MaskShAmt)), m_AllOnes()); 216 // (-1 >> MaskShAmt) 217 auto MaskC = m_Shr(m_AllOnes(), m_Value(MaskShAmt)); 218 // ((-1 << MaskShAmt) >> MaskShAmt) 219 auto MaskD = 220 m_Shr(m_Shl(m_AllOnes(), m_Value(MaskShAmt)), m_Deferred(MaskShAmt)); 221 222 Value *X; 223 Constant *NewMask; 224 225 if (match(Masked, m_c_And(m_CombineOr(MaskA, MaskB), m_Value(X)))) { 226 // Peek through an optional zext of the shift amount. 227 match(MaskShAmt, m_ZExtOrSelf(m_Value(MaskShAmt))); 228 229 // Verify that it would be safe to try to add those two shift amounts. 230 if (!canTryToConstantAddTwoShiftAmounts(OuterShift, ShiftShAmt, Masked, 231 MaskShAmt)) 232 return nullptr; 233 234 // Can we simplify (MaskShAmt+ShiftShAmt) ? 235 auto *SumOfShAmts = dyn_cast_or_null<Constant>(SimplifyAddInst( 236 MaskShAmt, ShiftShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q)); 237 if (!SumOfShAmts) 238 return nullptr; // Did not simplify. 239 // In this pattern SumOfShAmts correlates with the number of low bits 240 // that shall remain in the root value (OuterShift). 241 242 // An extend of an undef value becomes zero because the high bits are never 243 // completely unknown. Replace the the `undef` shift amounts with final 244 // shift bitwidth to ensure that the value remains undef when creating the 245 // subsequent shift op. 246 SumOfShAmts = Constant::replaceUndefsWith( 247 SumOfShAmts, ConstantInt::get(SumOfShAmts->getType()->getScalarType(), 248 ExtendedTy->getScalarSizeInBits())); 249 auto *ExtendedSumOfShAmts = ConstantExpr::getZExt(SumOfShAmts, ExtendedTy); 250 // And compute the mask as usual: ~(-1 << (SumOfShAmts)) 251 auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(ExtendedTy); 252 auto *ExtendedInvertedMask = 253 ConstantExpr::getShl(ExtendedAllOnes, ExtendedSumOfShAmts); 254 NewMask = ConstantExpr::getNot(ExtendedInvertedMask); 255 } else if (match(Masked, m_c_And(m_CombineOr(MaskC, MaskD), m_Value(X))) || 256 match(Masked, m_Shr(m_Shl(m_Value(X), m_Value(MaskShAmt)), 257 m_Deferred(MaskShAmt)))) { 258 // Peek through an optional zext of the shift amount. 259 match(MaskShAmt, m_ZExtOrSelf(m_Value(MaskShAmt))); 260 261 // Verify that it would be safe to try to add those two shift amounts. 262 if (!canTryToConstantAddTwoShiftAmounts(OuterShift, ShiftShAmt, Masked, 263 MaskShAmt)) 264 return nullptr; 265 266 // Can we simplify (ShiftShAmt-MaskShAmt) ? 267 auto *ShAmtsDiff = dyn_cast_or_null<Constant>(SimplifySubInst( 268 ShiftShAmt, MaskShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q)); 269 if (!ShAmtsDiff) 270 return nullptr; // Did not simplify. 271 // In this pattern ShAmtsDiff correlates with the number of high bits that 272 // shall be unset in the root value (OuterShift). 273 274 // An extend of an undef value becomes zero because the high bits are never 275 // completely unknown. Replace the the `undef` shift amounts with negated 276 // bitwidth of innermost shift to ensure that the value remains undef when 277 // creating the subsequent shift op. 278 unsigned WidestTyBitWidth = WidestTy->getScalarSizeInBits(); 279 ShAmtsDiff = Constant::replaceUndefsWith( 280 ShAmtsDiff, ConstantInt::get(ShAmtsDiff->getType()->getScalarType(), 281 -WidestTyBitWidth)); 282 auto *ExtendedNumHighBitsToClear = ConstantExpr::getZExt( 283 ConstantExpr::getSub(ConstantInt::get(ShAmtsDiff->getType(), 284 WidestTyBitWidth, 285 /*isSigned=*/false), 286 ShAmtsDiff), 287 ExtendedTy); 288 // And compute the mask as usual: (-1 l>> (NumHighBitsToClear)) 289 auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(ExtendedTy); 290 NewMask = 291 ConstantExpr::getLShr(ExtendedAllOnes, ExtendedNumHighBitsToClear); 292 } else 293 return nullptr; // Don't know anything about this pattern. 294 295 NewMask = ConstantExpr::getTrunc(NewMask, NarrowestTy); 296 297 // Does this mask has any unset bits? If not then we can just not apply it. 298 bool NeedMask = !match(NewMask, m_AllOnes()); 299 300 // If we need to apply a mask, there are several more restrictions we have. 301 if (NeedMask) { 302 // The old masking instruction must go away. 303 if (!Masked->hasOneUse()) 304 return nullptr; 305 // The original "masking" instruction must not have been`ashr`. 306 if (match(Masked, m_AShr(m_Value(), m_Value()))) 307 return nullptr; 308 } 309 310 // If we need to apply truncation, let's do it first, since we can. 311 // We have already ensured that the old truncation will go away. 312 if (HadTrunc) 313 X = Builder.CreateTrunc(X, NarrowestTy); 314 315 // No 'NUW'/'NSW'! We no longer know that we won't shift-out non-0 bits. 316 // We didn't change the Type of this outermost shift, so we can just do it. 317 auto *NewShift = BinaryOperator::Create(OuterShift->getOpcode(), X, 318 OuterShift->getOperand(1)); 319 if (!NeedMask) 320 return NewShift; 321 322 Builder.Insert(NewShift); 323 return BinaryOperator::Create(Instruction::And, NewShift, NewMask); 324 } 325 326 /// If we have a shift-by-constant of a bitwise logic op that itself has a 327 /// shift-by-constant operand with identical opcode, we may be able to convert 328 /// that into 2 independent shifts followed by the logic op. This eliminates a 329 /// a use of an intermediate value (reduces dependency chain). 330 static Instruction *foldShiftOfShiftedLogic(BinaryOperator &I, 331 InstCombiner::BuilderTy &Builder) { 332 assert(I.isShift() && "Expected a shift as input"); 333 auto *LogicInst = dyn_cast<BinaryOperator>(I.getOperand(0)); 334 if (!LogicInst || !LogicInst->isBitwiseLogicOp() || !LogicInst->hasOneUse()) 335 return nullptr; 336 337 Constant *C0, *C1; 338 if (!match(I.getOperand(1), m_Constant(C1))) 339 return nullptr; 340 341 Instruction::BinaryOps ShiftOpcode = I.getOpcode(); 342 Type *Ty = I.getType(); 343 344 // Find a matching one-use shift by constant. The fold is not valid if the sum 345 // of the shift values equals or exceeds bitwidth. 346 // TODO: Remove the one-use check if the other logic operand (Y) is constant. 347 Value *X, *Y; 348 auto matchFirstShift = [&](Value *V) { 349 BinaryOperator *BO; 350 APInt Threshold(Ty->getScalarSizeInBits(), Ty->getScalarSizeInBits()); 351 return match(V, m_BinOp(BO)) && BO->getOpcode() == ShiftOpcode && 352 match(V, m_OneUse(m_Shift(m_Value(X), m_Constant(C0)))) && 353 match(ConstantExpr::getAdd(C0, C1), 354 m_SpecificInt_ICMP(ICmpInst::ICMP_ULT, Threshold)); 355 }; 356 357 // Logic ops are commutative, so check each operand for a match. 358 if (matchFirstShift(LogicInst->getOperand(0))) 359 Y = LogicInst->getOperand(1); 360 else if (matchFirstShift(LogicInst->getOperand(1))) 361 Y = LogicInst->getOperand(0); 362 else 363 return nullptr; 364 365 // shift (logic (shift X, C0), Y), C1 -> logic (shift X, C0+C1), (shift Y, C1) 366 Constant *ShiftSumC = ConstantExpr::getAdd(C0, C1); 367 Value *NewShift1 = Builder.CreateBinOp(ShiftOpcode, X, ShiftSumC); 368 Value *NewShift2 = Builder.CreateBinOp(ShiftOpcode, Y, I.getOperand(1)); 369 return BinaryOperator::Create(LogicInst->getOpcode(), NewShift1, NewShift2); 370 } 371 372 Instruction *InstCombinerImpl::commonShiftTransforms(BinaryOperator &I) { 373 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 374 assert(Op0->getType() == Op1->getType()); 375 376 // If the shift amount is a one-use `sext`, we can demote it to `zext`. 377 Value *Y; 378 if (match(Op1, m_OneUse(m_SExt(m_Value(Y))))) { 379 Value *NewExt = Builder.CreateZExt(Y, I.getType(), Op1->getName()); 380 return BinaryOperator::Create(I.getOpcode(), Op0, NewExt); 381 } 382 383 // See if we can fold away this shift. 384 if (SimplifyDemandedInstructionBits(I)) 385 return &I; 386 387 // Try to fold constant and into select arguments. 388 if (isa<Constant>(Op0)) 389 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 390 if (Instruction *R = FoldOpIntoSelect(I, SI)) 391 return R; 392 393 if (Constant *CUI = dyn_cast<Constant>(Op1)) 394 if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I)) 395 return Res; 396 397 if (auto *NewShift = cast_or_null<Instruction>( 398 reassociateShiftAmtsOfTwoSameDirectionShifts(&I, SQ))) 399 return NewShift; 400 401 // (C1 shift (A add C2)) -> (C1 shift C2) shift A) 402 // iff A and C2 are both positive. 403 Value *A; 404 Constant *C; 405 if (match(Op0, m_Constant()) && match(Op1, m_Add(m_Value(A), m_Constant(C)))) 406 if (isKnownNonNegative(A, DL, 0, &AC, &I, &DT) && 407 isKnownNonNegative(C, DL, 0, &AC, &I, &DT)) 408 return BinaryOperator::Create( 409 I.getOpcode(), Builder.CreateBinOp(I.getOpcode(), Op0, C), A); 410 411 // X shift (A srem C) -> X shift (A and (C - 1)) iff C is a power of 2. 412 // Because shifts by negative values (which could occur if A were negative) 413 // are undefined. 414 if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Constant(C))) && 415 match(C, m_Power2())) { 416 // FIXME: Should this get moved into SimplifyDemandedBits by saying we don't 417 // demand the sign bit (and many others) here?? 418 Constant *Mask = ConstantExpr::getSub(C, ConstantInt::get(I.getType(), 1)); 419 Value *Rem = Builder.CreateAnd(A, Mask, Op1->getName()); 420 return replaceOperand(I, 1, Rem); 421 } 422 423 if (Instruction *Logic = foldShiftOfShiftedLogic(I, Builder)) 424 return Logic; 425 426 return nullptr; 427 } 428 429 /// Return true if we can simplify two logical (either left or right) shifts 430 /// that have constant shift amounts: OuterShift (InnerShift X, C1), C2. 431 static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl, 432 Instruction *InnerShift, 433 InstCombinerImpl &IC, Instruction *CxtI) { 434 assert(InnerShift->isLogicalShift() && "Unexpected instruction type"); 435 436 // We need constant scalar or constant splat shifts. 437 const APInt *InnerShiftConst; 438 if (!match(InnerShift->getOperand(1), m_APInt(InnerShiftConst))) 439 return false; 440 441 // Two logical shifts in the same direction: 442 // shl (shl X, C1), C2 --> shl X, C1 + C2 443 // lshr (lshr X, C1), C2 --> lshr X, C1 + C2 444 bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl; 445 if (IsInnerShl == IsOuterShl) 446 return true; 447 448 // Equal shift amounts in opposite directions become bitwise 'and': 449 // lshr (shl X, C), C --> and X, C' 450 // shl (lshr X, C), C --> and X, C' 451 if (*InnerShiftConst == OuterShAmt) 452 return true; 453 454 // If the 2nd shift is bigger than the 1st, we can fold: 455 // lshr (shl X, C1), C2 --> and (shl X, C1 - C2), C3 456 // shl (lshr X, C1), C2 --> and (lshr X, C1 - C2), C3 457 // but it isn't profitable unless we know the and'd out bits are already zero. 458 // Also, check that the inner shift is valid (less than the type width) or 459 // we'll crash trying to produce the bit mask for the 'and'. 460 unsigned TypeWidth = InnerShift->getType()->getScalarSizeInBits(); 461 if (InnerShiftConst->ugt(OuterShAmt) && InnerShiftConst->ult(TypeWidth)) { 462 unsigned InnerShAmt = InnerShiftConst->getZExtValue(); 463 unsigned MaskShift = 464 IsInnerShl ? TypeWidth - InnerShAmt : InnerShAmt - OuterShAmt; 465 APInt Mask = APInt::getLowBitsSet(TypeWidth, OuterShAmt) << MaskShift; 466 if (IC.MaskedValueIsZero(InnerShift->getOperand(0), Mask, 0, CxtI)) 467 return true; 468 } 469 470 return false; 471 } 472 473 /// See if we can compute the specified value, but shifted logically to the left 474 /// or right by some number of bits. This should return true if the expression 475 /// can be computed for the same cost as the current expression tree. This is 476 /// used to eliminate extraneous shifting from things like: 477 /// %C = shl i128 %A, 64 478 /// %D = shl i128 %B, 96 479 /// %E = or i128 %C, %D 480 /// %F = lshr i128 %E, 64 481 /// where the client will ask if E can be computed shifted right by 64-bits. If 482 /// this succeeds, getShiftedValue() will be called to produce the value. 483 static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift, 484 InstCombinerImpl &IC, Instruction *CxtI) { 485 // We can always evaluate constants shifted. 486 if (isa<Constant>(V)) 487 return true; 488 489 Instruction *I = dyn_cast<Instruction>(V); 490 if (!I) return false; 491 492 // We can't mutate something that has multiple uses: doing so would 493 // require duplicating the instruction in general, which isn't profitable. 494 if (!I->hasOneUse()) return false; 495 496 switch (I->getOpcode()) { 497 default: return false; 498 case Instruction::And: 499 case Instruction::Or: 500 case Instruction::Xor: 501 // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted. 502 return canEvaluateShifted(I->getOperand(0), NumBits, IsLeftShift, IC, I) && 503 canEvaluateShifted(I->getOperand(1), NumBits, IsLeftShift, IC, I); 504 505 case Instruction::Shl: 506 case Instruction::LShr: 507 return canEvaluateShiftedShift(NumBits, IsLeftShift, I, IC, CxtI); 508 509 case Instruction::Select: { 510 SelectInst *SI = cast<SelectInst>(I); 511 Value *TrueVal = SI->getTrueValue(); 512 Value *FalseVal = SI->getFalseValue(); 513 return canEvaluateShifted(TrueVal, NumBits, IsLeftShift, IC, SI) && 514 canEvaluateShifted(FalseVal, NumBits, IsLeftShift, IC, SI); 515 } 516 case Instruction::PHI: { 517 // We can change a phi if we can change all operands. Note that we never 518 // get into trouble with cyclic PHIs here because we only consider 519 // instructions with a single use. 520 PHINode *PN = cast<PHINode>(I); 521 for (Value *IncValue : PN->incoming_values()) 522 if (!canEvaluateShifted(IncValue, NumBits, IsLeftShift, IC, PN)) 523 return false; 524 return true; 525 } 526 } 527 } 528 529 /// Fold OuterShift (InnerShift X, C1), C2. 530 /// See canEvaluateShiftedShift() for the constraints on these instructions. 531 static Value *foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt, 532 bool IsOuterShl, 533 InstCombiner::BuilderTy &Builder) { 534 bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl; 535 Type *ShType = InnerShift->getType(); 536 unsigned TypeWidth = ShType->getScalarSizeInBits(); 537 538 // We only accept shifts-by-a-constant in canEvaluateShifted(). 539 const APInt *C1; 540 match(InnerShift->getOperand(1), m_APInt(C1)); 541 unsigned InnerShAmt = C1->getZExtValue(); 542 543 // Change the shift amount and clear the appropriate IR flags. 544 auto NewInnerShift = [&](unsigned ShAmt) { 545 InnerShift->setOperand(1, ConstantInt::get(ShType, ShAmt)); 546 if (IsInnerShl) { 547 InnerShift->setHasNoUnsignedWrap(false); 548 InnerShift->setHasNoSignedWrap(false); 549 } else { 550 InnerShift->setIsExact(false); 551 } 552 return InnerShift; 553 }; 554 555 // Two logical shifts in the same direction: 556 // shl (shl X, C1), C2 --> shl X, C1 + C2 557 // lshr (lshr X, C1), C2 --> lshr X, C1 + C2 558 if (IsInnerShl == IsOuterShl) { 559 // If this is an oversized composite shift, then unsigned shifts get 0. 560 if (InnerShAmt + OuterShAmt >= TypeWidth) 561 return Constant::getNullValue(ShType); 562 563 return NewInnerShift(InnerShAmt + OuterShAmt); 564 } 565 566 // Equal shift amounts in opposite directions become bitwise 'and': 567 // lshr (shl X, C), C --> and X, C' 568 // shl (lshr X, C), C --> and X, C' 569 if (InnerShAmt == OuterShAmt) { 570 APInt Mask = IsInnerShl 571 ? APInt::getLowBitsSet(TypeWidth, TypeWidth - OuterShAmt) 572 : APInt::getHighBitsSet(TypeWidth, TypeWidth - OuterShAmt); 573 Value *And = Builder.CreateAnd(InnerShift->getOperand(0), 574 ConstantInt::get(ShType, Mask)); 575 if (auto *AndI = dyn_cast<Instruction>(And)) { 576 AndI->moveBefore(InnerShift); 577 AndI->takeName(InnerShift); 578 } 579 return And; 580 } 581 582 assert(InnerShAmt > OuterShAmt && 583 "Unexpected opposite direction logical shift pair"); 584 585 // In general, we would need an 'and' for this transform, but 586 // canEvaluateShiftedShift() guarantees that the masked-off bits are not used. 587 // lshr (shl X, C1), C2 --> shl X, C1 - C2 588 // shl (lshr X, C1), C2 --> lshr X, C1 - C2 589 return NewInnerShift(InnerShAmt - OuterShAmt); 590 } 591 592 /// When canEvaluateShifted() returns true for an expression, this function 593 /// inserts the new computation that produces the shifted value. 594 static Value *getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift, 595 InstCombinerImpl &IC, const DataLayout &DL) { 596 // We can always evaluate constants shifted. 597 if (Constant *C = dyn_cast<Constant>(V)) { 598 if (isLeftShift) 599 return IC.Builder.CreateShl(C, NumBits); 600 else 601 return IC.Builder.CreateLShr(C, NumBits); 602 } 603 604 Instruction *I = cast<Instruction>(V); 605 IC.addToWorklist(I); 606 607 switch (I->getOpcode()) { 608 default: llvm_unreachable("Inconsistency with CanEvaluateShifted"); 609 case Instruction::And: 610 case Instruction::Or: 611 case Instruction::Xor: 612 // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted. 613 I->setOperand( 614 0, getShiftedValue(I->getOperand(0), NumBits, isLeftShift, IC, DL)); 615 I->setOperand( 616 1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL)); 617 return I; 618 619 case Instruction::Shl: 620 case Instruction::LShr: 621 return foldShiftedShift(cast<BinaryOperator>(I), NumBits, isLeftShift, 622 IC.Builder); 623 624 case Instruction::Select: 625 I->setOperand( 626 1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL)); 627 I->setOperand( 628 2, getShiftedValue(I->getOperand(2), NumBits, isLeftShift, IC, DL)); 629 return I; 630 case Instruction::PHI: { 631 // We can change a phi if we can change all operands. Note that we never 632 // get into trouble with cyclic PHIs here because we only consider 633 // instructions with a single use. 634 PHINode *PN = cast<PHINode>(I); 635 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 636 PN->setIncomingValue(i, getShiftedValue(PN->getIncomingValue(i), NumBits, 637 isLeftShift, IC, DL)); 638 return PN; 639 } 640 } 641 } 642 643 // If this is a bitwise operator or add with a constant RHS we might be able 644 // to pull it through a shift. 645 static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift, 646 BinaryOperator *BO) { 647 switch (BO->getOpcode()) { 648 default: 649 return false; // Do not perform transform! 650 case Instruction::Add: 651 return Shift.getOpcode() == Instruction::Shl; 652 case Instruction::Or: 653 case Instruction::And: 654 return true; 655 case Instruction::Xor: 656 // Do not change a 'not' of logical shift because that would create a normal 657 // 'xor'. The 'not' is likely better for analysis, SCEV, and codegen. 658 return !(Shift.isLogicalShift() && match(BO, m_Not(m_Value()))); 659 } 660 } 661 662 Instruction *InstCombinerImpl::FoldShiftByConstant(Value *Op0, Constant *Op1, 663 BinaryOperator &I) { 664 bool isLeftShift = I.getOpcode() == Instruction::Shl; 665 666 const APInt *Op1C; 667 if (!match(Op1, m_APInt(Op1C))) 668 return nullptr; 669 670 // See if we can propagate this shift into the input, this covers the trivial 671 // cast of lshr(shl(x,c1),c2) as well as other more complex cases. 672 if (I.getOpcode() != Instruction::AShr && 673 canEvaluateShifted(Op0, Op1C->getZExtValue(), isLeftShift, *this, &I)) { 674 LLVM_DEBUG( 675 dbgs() << "ICE: GetShiftedValue propagating shift through expression" 676 " to eliminate shift:\n IN: " 677 << *Op0 << "\n SH: " << I << "\n"); 678 679 return replaceInstUsesWith( 680 I, getShiftedValue(Op0, Op1C->getZExtValue(), isLeftShift, *this, DL)); 681 } 682 683 // See if we can simplify any instructions used by the instruction whose sole 684 // purpose is to compute bits we don't care about. 685 Type *Ty = I.getType(); 686 unsigned TypeBits = Ty->getScalarSizeInBits(); 687 assert(!Op1C->uge(TypeBits) && 688 "Shift over the type width should have been removed already"); 689 690 if (Instruction *FoldedShift = foldBinOpIntoSelectOrPhi(I)) 691 return FoldedShift; 692 693 // Fold shift2(trunc(shift1(x,c1)), c2) -> trunc(shift2(shift1(x,c1),c2)) 694 if (auto *TI = dyn_cast<TruncInst>(Op0)) { 695 // If 'shift2' is an ashr, we would have to get the sign bit into a funny 696 // place. Don't try to do this transformation in this case. Also, we 697 // require that the input operand is a shift-by-constant so that we have 698 // confidence that the shifts will get folded together. We could do this 699 // xform in more cases, but it is unlikely to be profitable. 700 const APInt *TrShiftAmt; 701 if (I.isLogicalShift() && 702 match(TI->getOperand(0), m_Shift(m_Value(), m_APInt(TrShiftAmt)))) { 703 auto *TrOp = cast<Instruction>(TI->getOperand(0)); 704 Type *SrcTy = TrOp->getType(); 705 706 // Okay, we'll do this xform. Make the shift of shift. 707 Constant *ShAmt = ConstantExpr::getZExt(Op1, SrcTy); 708 // (shift2 (shift1 & 0x00FF), c2) 709 Value *NSh = Builder.CreateBinOp(I.getOpcode(), TrOp, ShAmt, I.getName()); 710 711 // For logical shifts, the truncation has the effect of making the high 712 // part of the register be zeros. Emulate this by inserting an AND to 713 // clear the top bits as needed. This 'and' will usually be zapped by 714 // other xforms later if dead. 715 unsigned SrcSize = SrcTy->getScalarSizeInBits(); 716 Constant *MaskV = 717 ConstantInt::get(SrcTy, APInt::getLowBitsSet(SrcSize, TypeBits)); 718 719 // The mask we constructed says what the trunc would do if occurring 720 // between the shifts. We want to know the effect *after* the second 721 // shift. We know that it is a logical shift by a constant, so adjust the 722 // mask as appropriate. 723 MaskV = ConstantExpr::get(I.getOpcode(), MaskV, ShAmt); 724 // shift1 & 0x00FF 725 Value *And = Builder.CreateAnd(NSh, MaskV, TI->getName()); 726 // Return the value truncated to the interesting size. 727 return new TruncInst(And, Ty); 728 } 729 } 730 731 if (Op0->hasOneUse()) { 732 if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) { 733 // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C) 734 Value *V1; 735 const APInt *CC; 736 switch (Op0BO->getOpcode()) { 737 default: break; 738 case Instruction::Add: 739 case Instruction::And: 740 case Instruction::Or: 741 case Instruction::Xor: { 742 // These operators commute. 743 // Turn (Y + (X >> C)) << C -> (X + (Y << C)) & (~0 << C) 744 if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() && 745 match(Op0BO->getOperand(1), m_Shr(m_Value(V1), 746 m_Specific(Op1)))) { 747 Value *YS = // (Y << C) 748 Builder.CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName()); 749 // (X + (Y << C)) 750 Value *X = Builder.CreateBinOp(Op0BO->getOpcode(), YS, V1, 751 Op0BO->getOperand(1)->getName()); 752 unsigned Op1Val = Op1C->getLimitedValue(TypeBits); 753 APInt Bits = APInt::getHighBitsSet(TypeBits, TypeBits - Op1Val); 754 Constant *Mask = ConstantInt::get(Ty, Bits); 755 return BinaryOperator::CreateAnd(X, Mask); 756 } 757 758 // Turn (Y + ((X >> C) & CC)) << C -> ((X & (CC << C)) + (Y << C)) 759 Value *Op0BOOp1 = Op0BO->getOperand(1); 760 if (isLeftShift && Op0BOOp1->hasOneUse() && 761 match(Op0BOOp1, m_And(m_OneUse(m_Shr(m_Value(V1), m_Specific(Op1))), 762 m_APInt(CC)))) { 763 Value *YS = // (Y << C) 764 Builder.CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName()); 765 // X & (CC << C) 766 Value *XM = Builder.CreateAnd( 767 V1, ConstantExpr::getShl(ConstantInt::get(Ty, *CC), Op1), 768 V1->getName() + ".mask"); 769 return BinaryOperator::Create(Op0BO->getOpcode(), YS, XM); 770 } 771 LLVM_FALLTHROUGH; 772 } 773 774 case Instruction::Sub: { 775 // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C) 776 if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() && 777 match(Op0BO->getOperand(0), m_Shr(m_Value(V1), 778 m_Specific(Op1)))) { 779 Value *YS = // (Y << C) 780 Builder.CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName()); 781 // (X + (Y << C)) 782 Value *X = Builder.CreateBinOp(Op0BO->getOpcode(), V1, YS, 783 Op0BO->getOperand(0)->getName()); 784 unsigned Op1Val = Op1C->getLimitedValue(TypeBits); 785 APInt Bits = APInt::getHighBitsSet(TypeBits, TypeBits - Op1Val); 786 Constant *Mask = ConstantInt::get(Ty, Bits); 787 return BinaryOperator::CreateAnd(X, Mask); 788 } 789 790 // Turn (((X >> C)&CC) + Y) << C -> (X + (Y << C)) & (CC << C) 791 if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() && 792 match(Op0BO->getOperand(0), 793 m_And(m_OneUse(m_Shr(m_Value(V1), m_Specific(Op1))), 794 m_APInt(CC)))) { 795 Value *YS = // (Y << C) 796 Builder.CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName()); 797 // X & (CC << C) 798 Value *XM = Builder.CreateAnd( 799 V1, ConstantExpr::getShl(ConstantInt::get(Ty, *CC), Op1), 800 V1->getName() + ".mask"); 801 return BinaryOperator::Create(Op0BO->getOpcode(), XM, YS); 802 } 803 804 break; 805 } 806 } 807 808 // If the operand is a bitwise operator with a constant RHS, and the 809 // shift is the only use, we can pull it out of the shift. 810 const APInt *Op0C; 811 if (match(Op0BO->getOperand(1), m_APInt(Op0C))) { 812 if (canShiftBinOpWithConstantRHS(I, Op0BO)) { 813 Constant *NewRHS = ConstantExpr::get(I.getOpcode(), 814 cast<Constant>(Op0BO->getOperand(1)), Op1); 815 816 Value *NewShift = 817 Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1); 818 NewShift->takeName(Op0BO); 819 820 return BinaryOperator::Create(Op0BO->getOpcode(), NewShift, 821 NewRHS); 822 } 823 } 824 825 // If the operand is a subtract with a constant LHS, and the shift 826 // is the only use, we can pull it out of the shift. 827 // This folds (shl (sub C1, X), C2) -> (sub (C1 << C2), (shl X, C2)) 828 if (isLeftShift && Op0BO->getOpcode() == Instruction::Sub && 829 match(Op0BO->getOperand(0), m_APInt(Op0C))) { 830 Constant *NewRHS = ConstantExpr::get(I.getOpcode(), 831 cast<Constant>(Op0BO->getOperand(0)), Op1); 832 833 Value *NewShift = Builder.CreateShl(Op0BO->getOperand(1), Op1); 834 NewShift->takeName(Op0BO); 835 836 return BinaryOperator::CreateSub(NewRHS, NewShift); 837 } 838 } 839 840 // If we have a select that conditionally executes some binary operator, 841 // see if we can pull it the select and operator through the shift. 842 // 843 // For example, turning: 844 // shl (select C, (add X, C1), X), C2 845 // Into: 846 // Y = shl X, C2 847 // select C, (add Y, C1 << C2), Y 848 Value *Cond; 849 BinaryOperator *TBO; 850 Value *FalseVal; 851 if (match(Op0, m_Select(m_Value(Cond), m_OneUse(m_BinOp(TBO)), 852 m_Value(FalseVal)))) { 853 const APInt *C; 854 if (!isa<Constant>(FalseVal) && TBO->getOperand(0) == FalseVal && 855 match(TBO->getOperand(1), m_APInt(C)) && 856 canShiftBinOpWithConstantRHS(I, TBO)) { 857 Constant *NewRHS = ConstantExpr::get(I.getOpcode(), 858 cast<Constant>(TBO->getOperand(1)), Op1); 859 860 Value *NewShift = 861 Builder.CreateBinOp(I.getOpcode(), FalseVal, Op1); 862 Value *NewOp = Builder.CreateBinOp(TBO->getOpcode(), NewShift, 863 NewRHS); 864 return SelectInst::Create(Cond, NewOp, NewShift); 865 } 866 } 867 868 BinaryOperator *FBO; 869 Value *TrueVal; 870 if (match(Op0, m_Select(m_Value(Cond), m_Value(TrueVal), 871 m_OneUse(m_BinOp(FBO))))) { 872 const APInt *C; 873 if (!isa<Constant>(TrueVal) && FBO->getOperand(0) == TrueVal && 874 match(FBO->getOperand(1), m_APInt(C)) && 875 canShiftBinOpWithConstantRHS(I, FBO)) { 876 Constant *NewRHS = ConstantExpr::get(I.getOpcode(), 877 cast<Constant>(FBO->getOperand(1)), Op1); 878 879 Value *NewShift = 880 Builder.CreateBinOp(I.getOpcode(), TrueVal, Op1); 881 Value *NewOp = Builder.CreateBinOp(FBO->getOpcode(), NewShift, 882 NewRHS); 883 return SelectInst::Create(Cond, NewShift, NewOp); 884 } 885 } 886 } 887 888 return nullptr; 889 } 890 891 Instruction *InstCombinerImpl::visitShl(BinaryOperator &I) { 892 const SimplifyQuery Q = SQ.getWithInstruction(&I); 893 894 if (Value *V = SimplifyShlInst(I.getOperand(0), I.getOperand(1), 895 I.hasNoSignedWrap(), I.hasNoUnsignedWrap(), Q)) 896 return replaceInstUsesWith(I, V); 897 898 if (Instruction *X = foldVectorBinop(I)) 899 return X; 900 901 if (Instruction *V = commonShiftTransforms(I)) 902 return V; 903 904 if (Instruction *V = dropRedundantMaskingOfLeftShiftInput(&I, Q, Builder)) 905 return V; 906 907 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 908 Type *Ty = I.getType(); 909 unsigned BitWidth = Ty->getScalarSizeInBits(); 910 911 const APInt *ShAmtAPInt; 912 if (match(Op1, m_APInt(ShAmtAPInt))) { 913 unsigned ShAmt = ShAmtAPInt->getZExtValue(); 914 915 // shl (zext X), ShAmt --> zext (shl X, ShAmt) 916 // This is only valid if X would have zeros shifted out. 917 Value *X; 918 if (match(Op0, m_OneUse(m_ZExt(m_Value(X))))) { 919 unsigned SrcWidth = X->getType()->getScalarSizeInBits(); 920 if (ShAmt < SrcWidth && 921 MaskedValueIsZero(X, APInt::getHighBitsSet(SrcWidth, ShAmt), 0, &I)) 922 return new ZExtInst(Builder.CreateShl(X, ShAmt), Ty); 923 } 924 925 // (X >> C) << C --> X & (-1 << C) 926 if (match(Op0, m_Shr(m_Value(X), m_Specific(Op1)))) { 927 APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmt)); 928 return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask)); 929 } 930 931 const APInt *ShOp1; 932 if (match(Op0, m_Exact(m_Shr(m_Value(X), m_APInt(ShOp1)))) && 933 ShOp1->ult(BitWidth)) { 934 unsigned ShrAmt = ShOp1->getZExtValue(); 935 if (ShrAmt < ShAmt) { 936 // If C1 < C2: (X >>?,exact C1) << C2 --> X << (C2 - C1) 937 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShrAmt); 938 auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff); 939 NewShl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 940 NewShl->setHasNoSignedWrap(I.hasNoSignedWrap()); 941 return NewShl; 942 } 943 if (ShrAmt > ShAmt) { 944 // If C1 > C2: (X >>?exact C1) << C2 --> X >>?exact (C1 - C2) 945 Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmt); 946 auto *NewShr = BinaryOperator::Create( 947 cast<BinaryOperator>(Op0)->getOpcode(), X, ShiftDiff); 948 NewShr->setIsExact(true); 949 return NewShr; 950 } 951 } 952 953 if (match(Op0, m_OneUse(m_Shr(m_Value(X), m_APInt(ShOp1)))) && 954 ShOp1->ult(BitWidth)) { 955 unsigned ShrAmt = ShOp1->getZExtValue(); 956 if (ShrAmt < ShAmt) { 957 // If C1 < C2: (X >>? C1) << C2 --> X << (C2 - C1) & (-1 << C2) 958 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShrAmt); 959 auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff); 960 NewShl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 961 NewShl->setHasNoSignedWrap(I.hasNoSignedWrap()); 962 Builder.Insert(NewShl); 963 APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmt)); 964 return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask)); 965 } 966 if (ShrAmt > ShAmt) { 967 // If C1 > C2: (X >>? C1) << C2 --> X >>? (C1 - C2) & (-1 << C2) 968 Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmt); 969 auto *OldShr = cast<BinaryOperator>(Op0); 970 auto *NewShr = 971 BinaryOperator::Create(OldShr->getOpcode(), X, ShiftDiff); 972 NewShr->setIsExact(OldShr->isExact()); 973 Builder.Insert(NewShr); 974 APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmt)); 975 return BinaryOperator::CreateAnd(NewShr, ConstantInt::get(Ty, Mask)); 976 } 977 } 978 979 if (match(Op0, m_Shl(m_Value(X), m_APInt(ShOp1))) && ShOp1->ult(BitWidth)) { 980 unsigned AmtSum = ShAmt + ShOp1->getZExtValue(); 981 // Oversized shifts are simplified to zero in InstSimplify. 982 if (AmtSum < BitWidth) 983 // (X << C1) << C2 --> X << (C1 + C2) 984 return BinaryOperator::CreateShl(X, ConstantInt::get(Ty, AmtSum)); 985 } 986 987 // If the shifted-out value is known-zero, then this is a NUW shift. 988 if (!I.hasNoUnsignedWrap() && 989 MaskedValueIsZero(Op0, APInt::getHighBitsSet(BitWidth, ShAmt), 0, &I)) { 990 I.setHasNoUnsignedWrap(); 991 return &I; 992 } 993 994 // If the shifted-out value is all signbits, then this is a NSW shift. 995 if (!I.hasNoSignedWrap() && ComputeNumSignBits(Op0, 0, &I) > ShAmt) { 996 I.setHasNoSignedWrap(); 997 return &I; 998 } 999 } 1000 1001 // Transform (x >> y) << y to x & (-1 << y) 1002 // Valid for any type of right-shift. 1003 Value *X; 1004 if (match(Op0, m_OneUse(m_Shr(m_Value(X), m_Specific(Op1))))) { 1005 Constant *AllOnes = ConstantInt::getAllOnesValue(Ty); 1006 Value *Mask = Builder.CreateShl(AllOnes, Op1); 1007 return BinaryOperator::CreateAnd(Mask, X); 1008 } 1009 1010 Constant *C1; 1011 if (match(Op1, m_Constant(C1))) { 1012 Constant *C2; 1013 Value *X; 1014 // (C2 << X) << C1 --> (C2 << C1) << X 1015 if (match(Op0, m_OneUse(m_Shl(m_Constant(C2), m_Value(X))))) 1016 return BinaryOperator::CreateShl(ConstantExpr::getShl(C2, C1), X); 1017 1018 // (X * C2) << C1 --> X * (C2 << C1) 1019 if (match(Op0, m_Mul(m_Value(X), m_Constant(C2)))) 1020 return BinaryOperator::CreateMul(X, ConstantExpr::getShl(C2, C1)); 1021 1022 // shl (zext i1 X), C1 --> select (X, 1 << C1, 0) 1023 if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) { 1024 auto *NewC = ConstantExpr::getShl(ConstantInt::get(Ty, 1), C1); 1025 return SelectInst::Create(X, NewC, ConstantInt::getNullValue(Ty)); 1026 } 1027 } 1028 1029 // (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1 1030 if (match(Op0, m_One()) && 1031 match(Op1, m_Sub(m_SpecificInt(BitWidth - 1), m_Value(X)))) 1032 return BinaryOperator::CreateLShr( 1033 ConstantInt::get(Ty, APInt::getSignMask(BitWidth)), X); 1034 1035 return nullptr; 1036 } 1037 1038 Instruction *InstCombinerImpl::visitLShr(BinaryOperator &I) { 1039 if (Value *V = SimplifyLShrInst(I.getOperand(0), I.getOperand(1), I.isExact(), 1040 SQ.getWithInstruction(&I))) 1041 return replaceInstUsesWith(I, V); 1042 1043 if (Instruction *X = foldVectorBinop(I)) 1044 return X; 1045 1046 if (Instruction *R = commonShiftTransforms(I)) 1047 return R; 1048 1049 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1050 Type *Ty = I.getType(); 1051 const APInt *ShAmtAPInt; 1052 if (match(Op1, m_APInt(ShAmtAPInt))) { 1053 unsigned ShAmt = ShAmtAPInt->getZExtValue(); 1054 unsigned BitWidth = Ty->getScalarSizeInBits(); 1055 auto *II = dyn_cast<IntrinsicInst>(Op0); 1056 if (II && isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == ShAmt && 1057 (II->getIntrinsicID() == Intrinsic::ctlz || 1058 II->getIntrinsicID() == Intrinsic::cttz || 1059 II->getIntrinsicID() == Intrinsic::ctpop)) { 1060 // ctlz.i32(x)>>5 --> zext(x == 0) 1061 // cttz.i32(x)>>5 --> zext(x == 0) 1062 // ctpop.i32(x)>>5 --> zext(x == -1) 1063 bool IsPop = II->getIntrinsicID() == Intrinsic::ctpop; 1064 Constant *RHS = ConstantInt::getSigned(Ty, IsPop ? -1 : 0); 1065 Value *Cmp = Builder.CreateICmpEQ(II->getArgOperand(0), RHS); 1066 return new ZExtInst(Cmp, Ty); 1067 } 1068 1069 Value *X; 1070 const APInt *ShOp1; 1071 if (match(Op0, m_Shl(m_Value(X), m_APInt(ShOp1))) && ShOp1->ult(BitWidth)) { 1072 if (ShOp1->ult(ShAmt)) { 1073 unsigned ShlAmt = ShOp1->getZExtValue(); 1074 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt); 1075 if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) { 1076 // (X <<nuw C1) >>u C2 --> X >>u (C2 - C1) 1077 auto *NewLShr = BinaryOperator::CreateLShr(X, ShiftDiff); 1078 NewLShr->setIsExact(I.isExact()); 1079 return NewLShr; 1080 } 1081 // (X << C1) >>u C2 --> (X >>u (C2 - C1)) & (-1 >> C2) 1082 Value *NewLShr = Builder.CreateLShr(X, ShiftDiff, "", I.isExact()); 1083 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt)); 1084 return BinaryOperator::CreateAnd(NewLShr, ConstantInt::get(Ty, Mask)); 1085 } 1086 if (ShOp1->ugt(ShAmt)) { 1087 unsigned ShlAmt = ShOp1->getZExtValue(); 1088 Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt); 1089 if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) { 1090 // (X <<nuw C1) >>u C2 --> X <<nuw (C1 - C2) 1091 auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff); 1092 NewShl->setHasNoUnsignedWrap(true); 1093 return NewShl; 1094 } 1095 // (X << C1) >>u C2 --> X << (C1 - C2) & (-1 >> C2) 1096 Value *NewShl = Builder.CreateShl(X, ShiftDiff); 1097 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt)); 1098 return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask)); 1099 } 1100 assert(*ShOp1 == ShAmt); 1101 // (X << C) >>u C --> X & (-1 >>u C) 1102 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt)); 1103 return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask)); 1104 } 1105 1106 if (match(Op0, m_OneUse(m_ZExt(m_Value(X)))) && 1107 (!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType()))) { 1108 assert(ShAmt < X->getType()->getScalarSizeInBits() && 1109 "Big shift not simplified to zero?"); 1110 // lshr (zext iM X to iN), C --> zext (lshr X, C) to iN 1111 Value *NewLShr = Builder.CreateLShr(X, ShAmt); 1112 return new ZExtInst(NewLShr, Ty); 1113 } 1114 1115 if (match(Op0, m_SExt(m_Value(X))) && 1116 (!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType()))) { 1117 // Are we moving the sign bit to the low bit and widening with high zeros? 1118 unsigned SrcTyBitWidth = X->getType()->getScalarSizeInBits(); 1119 if (ShAmt == BitWidth - 1) { 1120 // lshr (sext i1 X to iN), N-1 --> zext X to iN 1121 if (SrcTyBitWidth == 1) 1122 return new ZExtInst(X, Ty); 1123 1124 // lshr (sext iM X to iN), N-1 --> zext (lshr X, M-1) to iN 1125 if (Op0->hasOneUse()) { 1126 Value *NewLShr = Builder.CreateLShr(X, SrcTyBitWidth - 1); 1127 return new ZExtInst(NewLShr, Ty); 1128 } 1129 } 1130 1131 // lshr (sext iM X to iN), N-M --> zext (ashr X, min(N-M, M-1)) to iN 1132 if (ShAmt == BitWidth - SrcTyBitWidth && Op0->hasOneUse()) { 1133 // The new shift amount can't be more than the narrow source type. 1134 unsigned NewShAmt = std::min(ShAmt, SrcTyBitWidth - 1); 1135 Value *AShr = Builder.CreateAShr(X, NewShAmt); 1136 return new ZExtInst(AShr, Ty); 1137 } 1138 } 1139 1140 Value *Y; 1141 if (ShAmt == BitWidth - 1) { 1142 // lshr i32 or(X,-X), 31 --> zext (X != 0) 1143 if (match(Op0, m_OneUse(m_c_Or(m_Neg(m_Value(X)), m_Deferred(X))))) 1144 return new ZExtInst(Builder.CreateIsNotNull(X), Ty); 1145 1146 // lshr i32 (X -nsw Y), 31 --> zext (X < Y) 1147 if (match(Op0, m_OneUse(m_NSWSub(m_Value(X), m_Value(Y))))) 1148 return new ZExtInst(Builder.CreateICmpSLT(X, Y), Ty); 1149 1150 // Check if a number is negative and odd: 1151 // lshr i32 (srem X, 2), 31 --> and (X >> 31), X 1152 if (match(Op0, m_OneUse(m_SRem(m_Value(X), m_SpecificInt(2))))) { 1153 Value *Signbit = Builder.CreateLShr(X, ShAmt); 1154 return BinaryOperator::CreateAnd(Signbit, X); 1155 } 1156 } 1157 1158 if (match(Op0, m_LShr(m_Value(X), m_APInt(ShOp1)))) { 1159 unsigned AmtSum = ShAmt + ShOp1->getZExtValue(); 1160 // Oversized shifts are simplified to zero in InstSimplify. 1161 if (AmtSum < BitWidth) 1162 // (X >>u C1) >>u C2 --> X >>u (C1 + C2) 1163 return BinaryOperator::CreateLShr(X, ConstantInt::get(Ty, AmtSum)); 1164 } 1165 1166 // Look for a "splat" mul pattern - it replicates bits across each half of 1167 // a value, so a right shift is just a mask of the low bits: 1168 // lshr i32 (mul nuw X, Pow2+1), 16 --> and X, Pow2-1 1169 // TODO: Generalize to allow more than just half-width shifts? 1170 const APInt *MulC; 1171 if (match(Op0, m_NUWMul(m_Value(X), m_APInt(MulC))) && 1172 ShAmt * 2 == BitWidth && (*MulC - 1).isPowerOf2() && 1173 MulC->logBase2() == ShAmt) 1174 return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, *MulC - 2)); 1175 1176 // If the shifted-out value is known-zero, then this is an exact shift. 1177 if (!I.isExact() && 1178 MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmt), 0, &I)) { 1179 I.setIsExact(); 1180 return &I; 1181 } 1182 } 1183 1184 // Transform (x << y) >> y to x & (-1 >> y) 1185 Value *X; 1186 if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_Specific(Op1))))) { 1187 Constant *AllOnes = ConstantInt::getAllOnesValue(Ty); 1188 Value *Mask = Builder.CreateLShr(AllOnes, Op1); 1189 return BinaryOperator::CreateAnd(Mask, X); 1190 } 1191 1192 return nullptr; 1193 } 1194 1195 Instruction * 1196 InstCombinerImpl::foldVariableSignZeroExtensionOfVariableHighBitExtract( 1197 BinaryOperator &OldAShr) { 1198 assert(OldAShr.getOpcode() == Instruction::AShr && 1199 "Must be called with arithmetic right-shift instruction only."); 1200 1201 // Check that constant C is a splat of the element-wise bitwidth of V. 1202 auto BitWidthSplat = [](Constant *C, Value *V) { 1203 return match( 1204 C, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ, 1205 APInt(C->getType()->getScalarSizeInBits(), 1206 V->getType()->getScalarSizeInBits()))); 1207 }; 1208 1209 // It should look like variable-length sign-extension on the outside: 1210 // (Val << (bitwidth(Val)-Nbits)) a>> (bitwidth(Val)-Nbits) 1211 Value *NBits; 1212 Instruction *MaybeTrunc; 1213 Constant *C1, *C2; 1214 if (!match(&OldAShr, 1215 m_AShr(m_Shl(m_Instruction(MaybeTrunc), 1216 m_ZExtOrSelf(m_Sub(m_Constant(C1), 1217 m_ZExtOrSelf(m_Value(NBits))))), 1218 m_ZExtOrSelf(m_Sub(m_Constant(C2), 1219 m_ZExtOrSelf(m_Deferred(NBits)))))) || 1220 !BitWidthSplat(C1, &OldAShr) || !BitWidthSplat(C2, &OldAShr)) 1221 return nullptr; 1222 1223 // There may or may not be a truncation after outer two shifts. 1224 Instruction *HighBitExtract; 1225 match(MaybeTrunc, m_TruncOrSelf(m_Instruction(HighBitExtract))); 1226 bool HadTrunc = MaybeTrunc != HighBitExtract; 1227 1228 // And finally, the innermost part of the pattern must be a right-shift. 1229 Value *X, *NumLowBitsToSkip; 1230 if (!match(HighBitExtract, m_Shr(m_Value(X), m_Value(NumLowBitsToSkip)))) 1231 return nullptr; 1232 1233 // Said right-shift must extract high NBits bits - C0 must be it's bitwidth. 1234 Constant *C0; 1235 if (!match(NumLowBitsToSkip, 1236 m_ZExtOrSelf( 1237 m_Sub(m_Constant(C0), m_ZExtOrSelf(m_Specific(NBits))))) || 1238 !BitWidthSplat(C0, HighBitExtract)) 1239 return nullptr; 1240 1241 // Since the NBits is identical for all shifts, if the outermost and 1242 // innermost shifts are identical, then outermost shifts are redundant. 1243 // If we had truncation, do keep it though. 1244 if (HighBitExtract->getOpcode() == OldAShr.getOpcode()) 1245 return replaceInstUsesWith(OldAShr, MaybeTrunc); 1246 1247 // Else, if there was a truncation, then we need to ensure that one 1248 // instruction will go away. 1249 if (HadTrunc && !match(&OldAShr, m_c_BinOp(m_OneUse(m_Value()), m_Value()))) 1250 return nullptr; 1251 1252 // Finally, bypass two innermost shifts, and perform the outermost shift on 1253 // the operands of the innermost shift. 1254 Instruction *NewAShr = 1255 BinaryOperator::Create(OldAShr.getOpcode(), X, NumLowBitsToSkip); 1256 NewAShr->copyIRFlags(HighBitExtract); // We can preserve 'exact'-ness. 1257 if (!HadTrunc) 1258 return NewAShr; 1259 1260 Builder.Insert(NewAShr); 1261 return TruncInst::CreateTruncOrBitCast(NewAShr, OldAShr.getType()); 1262 } 1263 1264 Instruction *InstCombinerImpl::visitAShr(BinaryOperator &I) { 1265 if (Value *V = SimplifyAShrInst(I.getOperand(0), I.getOperand(1), I.isExact(), 1266 SQ.getWithInstruction(&I))) 1267 return replaceInstUsesWith(I, V); 1268 1269 if (Instruction *X = foldVectorBinop(I)) 1270 return X; 1271 1272 if (Instruction *R = commonShiftTransforms(I)) 1273 return R; 1274 1275 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1276 Type *Ty = I.getType(); 1277 unsigned BitWidth = Ty->getScalarSizeInBits(); 1278 const APInt *ShAmtAPInt; 1279 if (match(Op1, m_APInt(ShAmtAPInt)) && ShAmtAPInt->ult(BitWidth)) { 1280 unsigned ShAmt = ShAmtAPInt->getZExtValue(); 1281 1282 // If the shift amount equals the difference in width of the destination 1283 // and source scalar types: 1284 // ashr (shl (zext X), C), C --> sext X 1285 Value *X; 1286 if (match(Op0, m_Shl(m_ZExt(m_Value(X)), m_Specific(Op1))) && 1287 ShAmt == BitWidth - X->getType()->getScalarSizeInBits()) 1288 return new SExtInst(X, Ty); 1289 1290 // We can't handle (X << C1) >>s C2. It shifts arbitrary bits in. However, 1291 // we can handle (X <<nsw C1) >>s C2 since it only shifts in sign bits. 1292 const APInt *ShOp1; 1293 if (match(Op0, m_NSWShl(m_Value(X), m_APInt(ShOp1))) && 1294 ShOp1->ult(BitWidth)) { 1295 unsigned ShlAmt = ShOp1->getZExtValue(); 1296 if (ShlAmt < ShAmt) { 1297 // (X <<nsw C1) >>s C2 --> X >>s (C2 - C1) 1298 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt); 1299 auto *NewAShr = BinaryOperator::CreateAShr(X, ShiftDiff); 1300 NewAShr->setIsExact(I.isExact()); 1301 return NewAShr; 1302 } 1303 if (ShlAmt > ShAmt) { 1304 // (X <<nsw C1) >>s C2 --> X <<nsw (C1 - C2) 1305 Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt); 1306 auto *NewShl = BinaryOperator::Create(Instruction::Shl, X, ShiftDiff); 1307 NewShl->setHasNoSignedWrap(true); 1308 return NewShl; 1309 } 1310 } 1311 1312 if (match(Op0, m_AShr(m_Value(X), m_APInt(ShOp1))) && 1313 ShOp1->ult(BitWidth)) { 1314 unsigned AmtSum = ShAmt + ShOp1->getZExtValue(); 1315 // Oversized arithmetic shifts replicate the sign bit. 1316 AmtSum = std::min(AmtSum, BitWidth - 1); 1317 // (X >>s C1) >>s C2 --> X >>s (C1 + C2) 1318 return BinaryOperator::CreateAShr(X, ConstantInt::get(Ty, AmtSum)); 1319 } 1320 1321 if (match(Op0, m_OneUse(m_SExt(m_Value(X)))) && 1322 (Ty->isVectorTy() || shouldChangeType(Ty, X->getType()))) { 1323 // ashr (sext X), C --> sext (ashr X, C') 1324 Type *SrcTy = X->getType(); 1325 ShAmt = std::min(ShAmt, SrcTy->getScalarSizeInBits() - 1); 1326 Value *NewSh = Builder.CreateAShr(X, ConstantInt::get(SrcTy, ShAmt)); 1327 return new SExtInst(NewSh, Ty); 1328 } 1329 1330 if (ShAmt == BitWidth - 1) { 1331 // ashr i32 or(X,-X), 31 --> sext (X != 0) 1332 if (match(Op0, m_OneUse(m_c_Or(m_Neg(m_Value(X)), m_Deferred(X))))) 1333 return new SExtInst(Builder.CreateIsNotNull(X), Ty); 1334 1335 // ashr i32 (X -nsw Y), 31 --> sext (X < Y) 1336 Value *Y; 1337 if (match(Op0, m_OneUse(m_NSWSub(m_Value(X), m_Value(Y))))) 1338 return new SExtInst(Builder.CreateICmpSLT(X, Y), Ty); 1339 } 1340 1341 // If the shifted-out value is known-zero, then this is an exact shift. 1342 if (!I.isExact() && 1343 MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmt), 0, &I)) { 1344 I.setIsExact(); 1345 return &I; 1346 } 1347 } 1348 1349 if (Instruction *R = foldVariableSignZeroExtensionOfVariableHighBitExtract(I)) 1350 return R; 1351 1352 // See if we can turn a signed shr into an unsigned shr. 1353 if (MaskedValueIsZero(Op0, APInt::getSignMask(BitWidth), 0, &I)) 1354 return BinaryOperator::CreateLShr(Op0, Op1); 1355 1356 // ashr (xor %x, -1), %y --> xor (ashr %x, %y), -1 1357 Value *X; 1358 if (match(Op0, m_OneUse(m_Not(m_Value(X))))) { 1359 // Note that we must drop 'exact'-ness of the shift! 1360 // Note that we can't keep undef's in -1 vector constant! 1361 auto *NewAShr = Builder.CreateAShr(X, Op1, Op0->getName() + ".not"); 1362 return BinaryOperator::CreateNot(NewAShr); 1363 } 1364 1365 return nullptr; 1366 } 1367