1//===- InstCombineMulDivRem.cpp -------------------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the visit functions for mul, fmul, sdiv, udiv, fdiv, 11// srem, urem, frem. 12// 13//===----------------------------------------------------------------------===// 14 15#include "InstCombineInternal.h" 16#include "llvm/Analysis/InstructionSimplify.h" 17#include "llvm/IR/IntrinsicInst.h" 18#include "llvm/IR/PatternMatch.h" 19using namespace llvm; 20using namespace PatternMatch; 21 22#define DEBUG_TYPE "instcombine" 23 24 25/// simplifyValueKnownNonZero - The specific integer value is used in a context 26/// where it is known to be non-zero. If this allows us to simplify the 27/// computation, do so and return the new operand, otherwise return null. 28static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC, 29 Instruction &CxtI) { 30 // If V has multiple uses, then we would have to do more analysis to determine 31 // if this is safe. For example, the use could be in dynamically unreached 32 // code. 33 if (!V->hasOneUse()) return nullptr; 34 35 bool MadeChange = false; 36 37 // ((1 << A) >>u B) --> (1 << (A-B)) 38 // Because V cannot be zero, we know that B is less than A. 39 Value *A = nullptr, *B = nullptr, *One = nullptr; 40 if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(One), m_Value(A))), m_Value(B))) && 41 match(One, m_One())) { 42 A = IC.Builder->CreateSub(A, B); 43 return IC.Builder->CreateShl(One, A); 44 } 45 46 // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it 47 // inexact. Similarly for <<. 48 if (BinaryOperator *I = dyn_cast<BinaryOperator>(V)) 49 if (I->isLogicalShift() && 50 isKnownToBeAPowerOfTwo(I->getOperand(0), IC.getDataLayout(), false, 0, 51 IC.getAssumptionCache(), &CxtI, 52 IC.getDominatorTree())) { 53 // We know that this is an exact/nuw shift and that the input is a 54 // non-zero context as well. 55 if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) { 56 I->setOperand(0, V2); 57 MadeChange = true; 58 } 59 60 if (I->getOpcode() == Instruction::LShr && !I->isExact()) { 61 I->setIsExact(); 62 MadeChange = true; 63 } 64 65 if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) { 66 I->setHasNoUnsignedWrap(); 67 MadeChange = true; 68 } 69 } 70 71 // TODO: Lots more we could do here: 72 // If V is a phi node, we can call this on each of its operands. 73 // "select cond, X, 0" can simplify to "X". 74 75 return MadeChange ? V : nullptr; 76} 77 78 79/// MultiplyOverflows - True if the multiply can not be expressed in an int 80/// this size. 81static bool MultiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product, 82 bool IsSigned) { 83 bool Overflow; 84 if (IsSigned) 85 Product = C1.smul_ov(C2, Overflow); 86 else 87 Product = C1.umul_ov(C2, Overflow); 88 89 return Overflow; 90} 91 92/// \brief True if C2 is a multiple of C1. Quotient contains C2/C1. 93static bool IsMultiple(const APInt &C1, const APInt &C2, APInt &Quotient, 94 bool IsSigned) { 95 assert(C1.getBitWidth() == C2.getBitWidth() && 96 "Inconsistent width of constants!"); 97 98 APInt Remainder(C1.getBitWidth(), /*Val=*/0ULL, IsSigned); 99 if (IsSigned) 100 APInt::sdivrem(C1, C2, Quotient, Remainder); 101 else 102 APInt::udivrem(C1, C2, Quotient, Remainder); 103 104 return Remainder.isMinValue(); 105} 106 107/// \brief A helper routine of InstCombiner::visitMul(). 108/// 109/// If C is a vector of known powers of 2, then this function returns 110/// a new vector obtained from C replacing each element with its logBase2. 111/// Return a null pointer otherwise. 112static Constant *getLogBase2Vector(ConstantDataVector *CV) { 113 const APInt *IVal; 114 SmallVector<Constant *, 4> Elts; 115 116 for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) { 117 Constant *Elt = CV->getElementAsConstant(I); 118 if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2()) 119 return nullptr; 120 Elts.push_back(ConstantInt::get(Elt->getType(), IVal->logBase2())); 121 } 122 123 return ConstantVector::get(Elts); 124} 125 126/// \brief Return true if we can prove that: 127/// (mul LHS, RHS) === (mul nsw LHS, RHS) 128bool InstCombiner::WillNotOverflowSignedMul(Value *LHS, Value *RHS, 129 Instruction &CxtI) { 130 // Multiplying n * m significant bits yields a result of n + m significant 131 // bits. If the total number of significant bits does not exceed the 132 // result bit width (minus 1), there is no overflow. 133 // This means if we have enough leading sign bits in the operands 134 // we can guarantee that the result does not overflow. 135 // Ref: "Hacker's Delight" by Henry Warren 136 unsigned BitWidth = LHS->getType()->getScalarSizeInBits(); 137 138 // Note that underestimating the number of sign bits gives a more 139 // conservative answer. 140 unsigned SignBits = 141 ComputeNumSignBits(LHS, 0, &CxtI) + ComputeNumSignBits(RHS, 0, &CxtI); 142 143 // First handle the easy case: if we have enough sign bits there's 144 // definitely no overflow. 145 if (SignBits > BitWidth + 1) 146 return true; 147 148 // There are two ambiguous cases where there can be no overflow: 149 // SignBits == BitWidth + 1 and 150 // SignBits == BitWidth 151 // The second case is difficult to check, therefore we only handle the 152 // first case. 153 if (SignBits == BitWidth + 1) { 154 // It overflows only when both arguments are negative and the true 155 // product is exactly the minimum negative number. 156 // E.g. mul i16 with 17 sign bits: 0xff00 * 0xff80 = 0x8000 157 // For simplicity we just check if at least one side is not negative. 158 bool LHSNonNegative, LHSNegative; 159 bool RHSNonNegative, RHSNegative; 160 ComputeSignBit(LHS, LHSNonNegative, LHSNegative, /*Depth=*/0, &CxtI); 161 ComputeSignBit(RHS, RHSNonNegative, RHSNegative, /*Depth=*/0, &CxtI); 162 if (LHSNonNegative || RHSNonNegative) 163 return true; 164 } 165 return false; 166} 167 168Instruction *InstCombiner::visitMul(BinaryOperator &I) { 169 bool Changed = SimplifyAssociativeOrCommutative(I); 170 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 171 172 if (Value *V = SimplifyVectorOp(I)) 173 return ReplaceInstUsesWith(I, V); 174 175 if (Value *V = SimplifyMulInst(Op0, Op1, DL, TLI, DT, AC)) 176 return ReplaceInstUsesWith(I, V); 177 178 if (Value *V = SimplifyUsingDistributiveLaws(I)) 179 return ReplaceInstUsesWith(I, V); 180 181 // X * -1 == 0 - X 182 if (match(Op1, m_AllOnes())) { 183 BinaryOperator *BO = BinaryOperator::CreateNeg(Op0, I.getName()); 184 if (I.hasNoSignedWrap()) 185 BO->setHasNoSignedWrap(); 186 return BO; 187 } 188 189 // Also allow combining multiply instructions on vectors. 190 { 191 Value *NewOp; 192 Constant *C1, *C2; 193 const APInt *IVal; 194 if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)), 195 m_Constant(C1))) && 196 match(C1, m_APInt(IVal))) { 197 // ((X << C2)*C1) == (X * (C1 << C2)) 198 Constant *Shl = ConstantExpr::getShl(C1, C2); 199 BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0)); 200 BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl); 201 if (I.hasNoUnsignedWrap() && Mul->hasNoUnsignedWrap()) 202 BO->setHasNoUnsignedWrap(); 203 if (I.hasNoSignedWrap() && Mul->hasNoSignedWrap() && 204 Shl->isNotMinSignedValue()) 205 BO->setHasNoSignedWrap(); 206 return BO; 207 } 208 209 if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) { 210 Constant *NewCst = nullptr; 211 if (match(C1, m_APInt(IVal)) && IVal->isPowerOf2()) 212 // Replace X*(2^C) with X << C, where C is either a scalar or a splat. 213 NewCst = ConstantInt::get(NewOp->getType(), IVal->logBase2()); 214 else if (ConstantDataVector *CV = dyn_cast<ConstantDataVector>(C1)) 215 // Replace X*(2^C) with X << C, where C is a vector of known 216 // constant powers of 2. 217 NewCst = getLogBase2Vector(CV); 218 219 if (NewCst) { 220 BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst); 221 222 if (I.hasNoUnsignedWrap()) 223 Shl->setHasNoUnsignedWrap(); 224 if (I.hasNoSignedWrap() && NewCst->isNotMinSignedValue()) 225 Shl->setHasNoSignedWrap(); 226 227 return Shl; 228 } 229 } 230 } 231 232 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 233 // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n 234 // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n 235 // The "* (2**n)" thus becomes a potential shifting opportunity. 236 { 237 const APInt & Val = CI->getValue(); 238 const APInt &PosVal = Val.abs(); 239 if (Val.isNegative() && PosVal.isPowerOf2()) { 240 Value *X = nullptr, *Y = nullptr; 241 if (Op0->hasOneUse()) { 242 ConstantInt *C1; 243 Value *Sub = nullptr; 244 if (match(Op0, m_Sub(m_Value(Y), m_Value(X)))) 245 Sub = Builder->CreateSub(X, Y, "suba"); 246 else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1)))) 247 Sub = Builder->CreateSub(Builder->CreateNeg(C1), Y, "subc"); 248 if (Sub) 249 return 250 BinaryOperator::CreateMul(Sub, 251 ConstantInt::get(Y->getType(), PosVal)); 252 } 253 } 254 } 255 } 256 257 // Simplify mul instructions with a constant RHS. 258 if (isa<Constant>(Op1)) { 259 // Try to fold constant mul into select arguments. 260 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 261 if (Instruction *R = FoldOpIntoSelect(I, SI)) 262 return R; 263 264 if (isa<PHINode>(Op0)) 265 if (Instruction *NV = FoldOpIntoPhi(I)) 266 return NV; 267 268 // Canonicalize (X+C1)*CI -> X*CI+C1*CI. 269 { 270 Value *X; 271 Constant *C1; 272 if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) { 273 Value *Mul = Builder->CreateMul(C1, Op1); 274 // Only go forward with the transform if C1*CI simplifies to a tidier 275 // constant. 276 if (!match(Mul, m_Mul(m_Value(), m_Value()))) 277 return BinaryOperator::CreateAdd(Builder->CreateMul(X, Op1), Mul); 278 } 279 } 280 } 281 282 if (Value *Op0v = dyn_castNegVal(Op0)) { // -X * -Y = X*Y 283 if (Value *Op1v = dyn_castNegVal(Op1)) { 284 BinaryOperator *BO = BinaryOperator::CreateMul(Op0v, Op1v); 285 if (I.hasNoSignedWrap() && 286 match(Op0, m_NSWSub(m_Value(), m_Value())) && 287 match(Op1, m_NSWSub(m_Value(), m_Value()))) 288 BO->setHasNoSignedWrap(); 289 return BO; 290 } 291 } 292 293 // (X / Y) * Y = X - (X % Y) 294 // (X / Y) * -Y = (X % Y) - X 295 { 296 Value *Op1C = Op1; 297 BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0); 298 if (!BO || 299 (BO->getOpcode() != Instruction::UDiv && 300 BO->getOpcode() != Instruction::SDiv)) { 301 Op1C = Op0; 302 BO = dyn_cast<BinaryOperator>(Op1); 303 } 304 Value *Neg = dyn_castNegVal(Op1C); 305 if (BO && BO->hasOneUse() && 306 (BO->getOperand(1) == Op1C || BO->getOperand(1) == Neg) && 307 (BO->getOpcode() == Instruction::UDiv || 308 BO->getOpcode() == Instruction::SDiv)) { 309 Value *Op0BO = BO->getOperand(0), *Op1BO = BO->getOperand(1); 310 311 // If the division is exact, X % Y is zero, so we end up with X or -X. 312 if (PossiblyExactOperator *SDiv = dyn_cast<PossiblyExactOperator>(BO)) 313 if (SDiv->isExact()) { 314 if (Op1BO == Op1C) 315 return ReplaceInstUsesWith(I, Op0BO); 316 return BinaryOperator::CreateNeg(Op0BO); 317 } 318 319 Value *Rem; 320 if (BO->getOpcode() == Instruction::UDiv) 321 Rem = Builder->CreateURem(Op0BO, Op1BO); 322 else 323 Rem = Builder->CreateSRem(Op0BO, Op1BO); 324 Rem->takeName(BO); 325 326 if (Op1BO == Op1C) 327 return BinaryOperator::CreateSub(Op0BO, Rem); 328 return BinaryOperator::CreateSub(Rem, Op0BO); 329 } 330 } 331 332 /// i1 mul -> i1 and. 333 if (I.getType()->getScalarType()->isIntegerTy(1)) 334 return BinaryOperator::CreateAnd(Op0, Op1); 335 336 // X*(1 << Y) --> X << Y 337 // (1 << Y)*X --> X << Y 338 { 339 Value *Y; 340 BinaryOperator *BO = nullptr; 341 bool ShlNSW = false; 342 if (match(Op0, m_Shl(m_One(), m_Value(Y)))) { 343 BO = BinaryOperator::CreateShl(Op1, Y); 344 ShlNSW = cast<ShlOperator>(Op0)->hasNoSignedWrap(); 345 } else if (match(Op1, m_Shl(m_One(), m_Value(Y)))) { 346 BO = BinaryOperator::CreateShl(Op0, Y); 347 ShlNSW = cast<ShlOperator>(Op1)->hasNoSignedWrap(); 348 } 349 if (BO) { 350 if (I.hasNoUnsignedWrap()) 351 BO->setHasNoUnsignedWrap(); 352 if (I.hasNoSignedWrap() && ShlNSW) 353 BO->setHasNoSignedWrap(); 354 return BO; 355 } 356 } 357 358 // If one of the operands of the multiply is a cast from a boolean value, then 359 // we know the bool is either zero or one, so this is a 'masking' multiply. 360 // X * Y (where Y is 0 or 1) -> X & (0-Y) 361 if (!I.getType()->isVectorTy()) { 362 // -2 is "-1 << 1" so it is all bits set except the low one. 363 APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true); 364 365 Value *BoolCast = nullptr, *OtherOp = nullptr; 366 if (MaskedValueIsZero(Op0, Negative2, 0, &I)) 367 BoolCast = Op0, OtherOp = Op1; 368 else if (MaskedValueIsZero(Op1, Negative2, 0, &I)) 369 BoolCast = Op1, OtherOp = Op0; 370 371 if (BoolCast) { 372 Value *V = Builder->CreateSub(Constant::getNullValue(I.getType()), 373 BoolCast); 374 return BinaryOperator::CreateAnd(V, OtherOp); 375 } 376 } 377 378 if (!I.hasNoSignedWrap() && WillNotOverflowSignedMul(Op0, Op1, I)) { 379 Changed = true; 380 I.setHasNoSignedWrap(true); 381 } 382 383 if (!I.hasNoUnsignedWrap() && 384 computeOverflowForUnsignedMul(Op0, Op1, &I) == 385 OverflowResult::NeverOverflows) { 386 Changed = true; 387 I.setHasNoUnsignedWrap(true); 388 } 389 390 return Changed ? &I : nullptr; 391} 392 393/// Detect pattern log2(Y * 0.5) with corresponding fast math flags. 394static void detectLog2OfHalf(Value *&Op, Value *&Y, IntrinsicInst *&Log2) { 395 if (!Op->hasOneUse()) 396 return; 397 398 IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op); 399 if (!II) 400 return; 401 if (II->getIntrinsicID() != Intrinsic::log2 || !II->hasUnsafeAlgebra()) 402 return; 403 Log2 = II; 404 405 Value *OpLog2Of = II->getArgOperand(0); 406 if (!OpLog2Of->hasOneUse()) 407 return; 408 409 Instruction *I = dyn_cast<Instruction>(OpLog2Of); 410 if (!I) 411 return; 412 if (I->getOpcode() != Instruction::FMul || !I->hasUnsafeAlgebra()) 413 return; 414 415 if (match(I->getOperand(0), m_SpecificFP(0.5))) 416 Y = I->getOperand(1); 417 else if (match(I->getOperand(1), m_SpecificFP(0.5))) 418 Y = I->getOperand(0); 419} 420 421static bool isFiniteNonZeroFp(Constant *C) { 422 if (C->getType()->isVectorTy()) { 423 for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; 424 ++I) { 425 ConstantFP *CFP = dyn_cast_or_null<ConstantFP>(C->getAggregateElement(I)); 426 if (!CFP || !CFP->getValueAPF().isFiniteNonZero()) 427 return false; 428 } 429 return true; 430 } 431 432 return isa<ConstantFP>(C) && 433 cast<ConstantFP>(C)->getValueAPF().isFiniteNonZero(); 434} 435 436static bool isNormalFp(Constant *C) { 437 if (C->getType()->isVectorTy()) { 438 for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; 439 ++I) { 440 ConstantFP *CFP = dyn_cast_or_null<ConstantFP>(C->getAggregateElement(I)); 441 if (!CFP || !CFP->getValueAPF().isNormal()) 442 return false; 443 } 444 return true; 445 } 446 447 return isa<ConstantFP>(C) && cast<ConstantFP>(C)->getValueAPF().isNormal(); 448} 449 450/// Helper function of InstCombiner::visitFMul(BinaryOperator(). It returns 451/// true iff the given value is FMul or FDiv with one and only one operand 452/// being a normal constant (i.e. not Zero/NaN/Infinity). 453static bool isFMulOrFDivWithConstant(Value *V) { 454 Instruction *I = dyn_cast<Instruction>(V); 455 if (!I || (I->getOpcode() != Instruction::FMul && 456 I->getOpcode() != Instruction::FDiv)) 457 return false; 458 459 Constant *C0 = dyn_cast<Constant>(I->getOperand(0)); 460 Constant *C1 = dyn_cast<Constant>(I->getOperand(1)); 461 462 if (C0 && C1) 463 return false; 464 465 return (C0 && isFiniteNonZeroFp(C0)) || (C1 && isFiniteNonZeroFp(C1)); 466} 467 468/// foldFMulConst() is a helper routine of InstCombiner::visitFMul(). 469/// The input \p FMulOrDiv is a FMul/FDiv with one and only one operand 470/// being a constant (i.e. isFMulOrFDivWithConstant(FMulOrDiv) == true). 471/// This function is to simplify "FMulOrDiv * C" and returns the 472/// resulting expression. Note that this function could return NULL in 473/// case the constants cannot be folded into a normal floating-point. 474/// 475Value *InstCombiner::foldFMulConst(Instruction *FMulOrDiv, Constant *C, 476 Instruction *InsertBefore) { 477 assert(isFMulOrFDivWithConstant(FMulOrDiv) && "V is invalid"); 478 479 Value *Opnd0 = FMulOrDiv->getOperand(0); 480 Value *Opnd1 = FMulOrDiv->getOperand(1); 481 482 Constant *C0 = dyn_cast<Constant>(Opnd0); 483 Constant *C1 = dyn_cast<Constant>(Opnd1); 484 485 BinaryOperator *R = nullptr; 486 487 // (X * C0) * C => X * (C0*C) 488 if (FMulOrDiv->getOpcode() == Instruction::FMul) { 489 Constant *F = ConstantExpr::getFMul(C1 ? C1 : C0, C); 490 if (isNormalFp(F)) 491 R = BinaryOperator::CreateFMul(C1 ? Opnd0 : Opnd1, F); 492 } else { 493 if (C0) { 494 // (C0 / X) * C => (C0 * C) / X 495 if (FMulOrDiv->hasOneUse()) { 496 // It would otherwise introduce another div. 497 Constant *F = ConstantExpr::getFMul(C0, C); 498 if (isNormalFp(F)) 499 R = BinaryOperator::CreateFDiv(F, Opnd1); 500 } 501 } else { 502 // (X / C1) * C => X * (C/C1) if C/C1 is not a denormal 503 Constant *F = ConstantExpr::getFDiv(C, C1); 504 if (isNormalFp(F)) { 505 R = BinaryOperator::CreateFMul(Opnd0, F); 506 } else { 507 // (X / C1) * C => X / (C1/C) 508 Constant *F = ConstantExpr::getFDiv(C1, C); 509 if (isNormalFp(F)) 510 R = BinaryOperator::CreateFDiv(Opnd0, F); 511 } 512 } 513 } 514 515 if (R) { 516 R->setHasUnsafeAlgebra(true); 517 InsertNewInstWith(R, *InsertBefore); 518 } 519 520 return R; 521} 522 523Instruction *InstCombiner::visitFMul(BinaryOperator &I) { 524 bool Changed = SimplifyAssociativeOrCommutative(I); 525 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 526 527 if (Value *V = SimplifyVectorOp(I)) 528 return ReplaceInstUsesWith(I, V); 529 530 if (isa<Constant>(Op0)) 531 std::swap(Op0, Op1); 532 533 if (Value *V = 534 SimplifyFMulInst(Op0, Op1, I.getFastMathFlags(), DL, TLI, DT, AC)) 535 return ReplaceInstUsesWith(I, V); 536 537 bool AllowReassociate = I.hasUnsafeAlgebra(); 538 539 // Simplify mul instructions with a constant RHS. 540 if (isa<Constant>(Op1)) { 541 // Try to fold constant mul into select arguments. 542 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 543 if (Instruction *R = FoldOpIntoSelect(I, SI)) 544 return R; 545 546 if (isa<PHINode>(Op0)) 547 if (Instruction *NV = FoldOpIntoPhi(I)) 548 return NV; 549 550 // (fmul X, -1.0) --> (fsub -0.0, X) 551 if (match(Op1, m_SpecificFP(-1.0))) { 552 Constant *NegZero = ConstantFP::getNegativeZero(Op1->getType()); 553 Instruction *RI = BinaryOperator::CreateFSub(NegZero, Op0); 554 RI->copyFastMathFlags(&I); 555 return RI; 556 } 557 558 Constant *C = cast<Constant>(Op1); 559 if (AllowReassociate && isFiniteNonZeroFp(C)) { 560 // Let MDC denote an expression in one of these forms: 561 // X * C, C/X, X/C, where C is a constant. 562 // 563 // Try to simplify "MDC * Constant" 564 if (isFMulOrFDivWithConstant(Op0)) 565 if (Value *V = foldFMulConst(cast<Instruction>(Op0), C, &I)) 566 return ReplaceInstUsesWith(I, V); 567 568 // (MDC +/- C1) * C => (MDC * C) +/- (C1 * C) 569 Instruction *FAddSub = dyn_cast<Instruction>(Op0); 570 if (FAddSub && 571 (FAddSub->getOpcode() == Instruction::FAdd || 572 FAddSub->getOpcode() == Instruction::FSub)) { 573 Value *Opnd0 = FAddSub->getOperand(0); 574 Value *Opnd1 = FAddSub->getOperand(1); 575 Constant *C0 = dyn_cast<Constant>(Opnd0); 576 Constant *C1 = dyn_cast<Constant>(Opnd1); 577 bool Swap = false; 578 if (C0) { 579 std::swap(C0, C1); 580 std::swap(Opnd0, Opnd1); 581 Swap = true; 582 } 583 584 if (C1 && isFiniteNonZeroFp(C1) && isFMulOrFDivWithConstant(Opnd0)) { 585 Value *M1 = ConstantExpr::getFMul(C1, C); 586 Value *M0 = isNormalFp(cast<Constant>(M1)) ? 587 foldFMulConst(cast<Instruction>(Opnd0), C, &I) : 588 nullptr; 589 if (M0 && M1) { 590 if (Swap && FAddSub->getOpcode() == Instruction::FSub) 591 std::swap(M0, M1); 592 593 Instruction *RI = (FAddSub->getOpcode() == Instruction::FAdd) 594 ? BinaryOperator::CreateFAdd(M0, M1) 595 : BinaryOperator::CreateFSub(M0, M1); 596 RI->copyFastMathFlags(&I); 597 return RI; 598 } 599 } 600 } 601 } 602 } 603 604 // sqrt(X) * sqrt(X) -> X 605 if (AllowReassociate && (Op0 == Op1)) 606 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op0)) 607 if (II->getIntrinsicID() == Intrinsic::sqrt) 608 return ReplaceInstUsesWith(I, II->getOperand(0)); 609 610 // Under unsafe algebra do: 611 // X * log2(0.5*Y) = X*log2(Y) - X 612 if (AllowReassociate) { 613 Value *OpX = nullptr; 614 Value *OpY = nullptr; 615 IntrinsicInst *Log2; 616 detectLog2OfHalf(Op0, OpY, Log2); 617 if (OpY) { 618 OpX = Op1; 619 } else { 620 detectLog2OfHalf(Op1, OpY, Log2); 621 if (OpY) { 622 OpX = Op0; 623 } 624 } 625 // if pattern detected emit alternate sequence 626 if (OpX && OpY) { 627 BuilderTy::FastMathFlagGuard Guard(*Builder); 628 Builder->SetFastMathFlags(Log2->getFastMathFlags()); 629 Log2->setArgOperand(0, OpY); 630 Value *FMulVal = Builder->CreateFMul(OpX, Log2); 631 Value *FSub = Builder->CreateFSub(FMulVal, OpX); 632 FSub->takeName(&I); 633 return ReplaceInstUsesWith(I, FSub); 634 } 635 } 636 637 // Handle symmetric situation in a 2-iteration loop 638 Value *Opnd0 = Op0; 639 Value *Opnd1 = Op1; 640 for (int i = 0; i < 2; i++) { 641 bool IgnoreZeroSign = I.hasNoSignedZeros(); 642 if (BinaryOperator::isFNeg(Opnd0, IgnoreZeroSign)) { 643 BuilderTy::FastMathFlagGuard Guard(*Builder); 644 Builder->SetFastMathFlags(I.getFastMathFlags()); 645 646 Value *N0 = dyn_castFNegVal(Opnd0, IgnoreZeroSign); 647 Value *N1 = dyn_castFNegVal(Opnd1, IgnoreZeroSign); 648 649 // -X * -Y => X*Y 650 if (N1) { 651 Value *FMul = Builder->CreateFMul(N0, N1); 652 FMul->takeName(&I); 653 return ReplaceInstUsesWith(I, FMul); 654 } 655 656 if (Opnd0->hasOneUse()) { 657 // -X * Y => -(X*Y) (Promote negation as high as possible) 658 Value *T = Builder->CreateFMul(N0, Opnd1); 659 Value *Neg = Builder->CreateFNeg(T); 660 Neg->takeName(&I); 661 return ReplaceInstUsesWith(I, Neg); 662 } 663 } 664 665 // (X*Y) * X => (X*X) * Y where Y != X 666 // The purpose is two-fold: 667 // 1) to form a power expression (of X). 668 // 2) potentially shorten the critical path: After transformation, the 669 // latency of the instruction Y is amortized by the expression of X*X, 670 // and therefore Y is in a "less critical" position compared to what it 671 // was before the transformation. 672 // 673 if (AllowReassociate) { 674 Value *Opnd0_0, *Opnd0_1; 675 if (Opnd0->hasOneUse() && 676 match(Opnd0, m_FMul(m_Value(Opnd0_0), m_Value(Opnd0_1)))) { 677 Value *Y = nullptr; 678 if (Opnd0_0 == Opnd1 && Opnd0_1 != Opnd1) 679 Y = Opnd0_1; 680 else if (Opnd0_1 == Opnd1 && Opnd0_0 != Opnd1) 681 Y = Opnd0_0; 682 683 if (Y) { 684 BuilderTy::FastMathFlagGuard Guard(*Builder); 685 Builder->SetFastMathFlags(I.getFastMathFlags()); 686 Value *T = Builder->CreateFMul(Opnd1, Opnd1); 687 688 Value *R = Builder->CreateFMul(T, Y); 689 R->takeName(&I); 690 return ReplaceInstUsesWith(I, R); 691 } 692 } 693 } 694 695 if (!isa<Constant>(Op1)) 696 std::swap(Opnd0, Opnd1); 697 else 698 break; 699 } 700 701 return Changed ? &I : nullptr; 702} 703 704/// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select 705/// instruction. 706bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) { 707 SelectInst *SI = cast<SelectInst>(I.getOperand(1)); 708 709 // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y 710 int NonNullOperand = -1; 711 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1))) 712 if (ST->isNullValue()) 713 NonNullOperand = 2; 714 // div/rem X, (Cond ? Y : 0) -> div/rem X, Y 715 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2))) 716 if (ST->isNullValue()) 717 NonNullOperand = 1; 718 719 if (NonNullOperand == -1) 720 return false; 721 722 Value *SelectCond = SI->getOperand(0); 723 724 // Change the div/rem to use 'Y' instead of the select. 725 I.setOperand(1, SI->getOperand(NonNullOperand)); 726 727 // Okay, we know we replace the operand of the div/rem with 'Y' with no 728 // problem. However, the select, or the condition of the select may have 729 // multiple uses. Based on our knowledge that the operand must be non-zero, 730 // propagate the known value for the select into other uses of it, and 731 // propagate a known value of the condition into its other users. 732 733 // If the select and condition only have a single use, don't bother with this, 734 // early exit. 735 if (SI->use_empty() && SelectCond->hasOneUse()) 736 return true; 737 738 // Scan the current block backward, looking for other uses of SI. 739 BasicBlock::iterator BBI = &I, BBFront = I.getParent()->begin(); 740 741 while (BBI != BBFront) { 742 --BBI; 743 // If we found a call to a function, we can't assume it will return, so 744 // information from below it cannot be propagated above it. 745 if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI)) 746 break; 747 748 // Replace uses of the select or its condition with the known values. 749 for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end(); 750 I != E; ++I) { 751 if (*I == SI) { 752 *I = SI->getOperand(NonNullOperand); 753 Worklist.Add(BBI); 754 } else if (*I == SelectCond) { 755 *I = Builder->getInt1(NonNullOperand == 1); 756 Worklist.Add(BBI); 757 } 758 } 759 760 // If we past the instruction, quit looking for it. 761 if (&*BBI == SI) 762 SI = nullptr; 763 if (&*BBI == SelectCond) 764 SelectCond = nullptr; 765 766 // If we ran out of things to eliminate, break out of the loop. 767 if (!SelectCond && !SI) 768 break; 769 770 } 771 return true; 772} 773 774 775/// This function implements the transforms common to both integer division 776/// instructions (udiv and sdiv). It is called by the visitors to those integer 777/// division instructions. 778/// @brief Common integer divide transforms 779Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { 780 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 781 782 // The RHS is known non-zero. 783 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) { 784 I.setOperand(1, V); 785 return &I; 786 } 787 788 // Handle cases involving: [su]div X, (select Cond, Y, Z) 789 // This does not apply for fdiv. 790 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 791 return &I; 792 793 if (Instruction *LHS = dyn_cast<Instruction>(Op0)) { 794 const APInt *C2; 795 if (match(Op1, m_APInt(C2))) { 796 Value *X; 797 const APInt *C1; 798 bool IsSigned = I.getOpcode() == Instruction::SDiv; 799 800 // (X / C1) / C2 -> X / (C1*C2) 801 if ((IsSigned && match(LHS, m_SDiv(m_Value(X), m_APInt(C1)))) || 802 (!IsSigned && match(LHS, m_UDiv(m_Value(X), m_APInt(C1))))) { 803 APInt Product(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); 804 if (!MultiplyOverflows(*C1, *C2, Product, IsSigned)) 805 return BinaryOperator::Create(I.getOpcode(), X, 806 ConstantInt::get(I.getType(), Product)); 807 } 808 809 if ((IsSigned && match(LHS, m_NSWMul(m_Value(X), m_APInt(C1)))) || 810 (!IsSigned && match(LHS, m_NUWMul(m_Value(X), m_APInt(C1))))) { 811 APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); 812 813 // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1. 814 if (IsMultiple(*C2, *C1, Quotient, IsSigned)) { 815 BinaryOperator *BO = BinaryOperator::Create( 816 I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient)); 817 BO->setIsExact(I.isExact()); 818 return BO; 819 } 820 821 // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2. 822 if (IsMultiple(*C1, *C2, Quotient, IsSigned)) { 823 BinaryOperator *BO = BinaryOperator::Create( 824 Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient)); 825 BO->setHasNoUnsignedWrap( 826 !IsSigned && 827 cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap()); 828 BO->setHasNoSignedWrap( 829 cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap()); 830 return BO; 831 } 832 } 833 834 if ((IsSigned && match(LHS, m_NSWShl(m_Value(X), m_APInt(C1))) && 835 *C1 != C1->getBitWidth() - 1) || 836 (!IsSigned && match(LHS, m_NUWShl(m_Value(X), m_APInt(C1))))) { 837 APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); 838 APInt C1Shifted = APInt::getOneBitSet( 839 C1->getBitWidth(), static_cast<unsigned>(C1->getLimitedValue())); 840 841 // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of C1. 842 if (IsMultiple(*C2, C1Shifted, Quotient, IsSigned)) { 843 BinaryOperator *BO = BinaryOperator::Create( 844 I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient)); 845 BO->setIsExact(I.isExact()); 846 return BO; 847 } 848 849 // (X << C1) / C2 -> X * (C2 >> C1) if C1 is a multiple of C2. 850 if (IsMultiple(C1Shifted, *C2, Quotient, IsSigned)) { 851 BinaryOperator *BO = BinaryOperator::Create( 852 Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient)); 853 BO->setHasNoUnsignedWrap( 854 !IsSigned && 855 cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap()); 856 BO->setHasNoSignedWrap( 857 cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap()); 858 return BO; 859 } 860 } 861 862 if (*C2 != 0) { // avoid X udiv 0 863 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 864 if (Instruction *R = FoldOpIntoSelect(I, SI)) 865 return R; 866 if (isa<PHINode>(Op0)) 867 if (Instruction *NV = FoldOpIntoPhi(I)) 868 return NV; 869 } 870 } 871 } 872 873 if (ConstantInt *One = dyn_cast<ConstantInt>(Op0)) { 874 if (One->isOne() && !I.getType()->isIntegerTy(1)) { 875 bool isSigned = I.getOpcode() == Instruction::SDiv; 876 if (isSigned) { 877 // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the 878 // result is one, if Op1 is -1 then the result is minus one, otherwise 879 // it's zero. 880 Value *Inc = Builder->CreateAdd(Op1, One); 881 Value *Cmp = Builder->CreateICmpULT( 882 Inc, ConstantInt::get(I.getType(), 3)); 883 return SelectInst::Create(Cmp, Op1, ConstantInt::get(I.getType(), 0)); 884 } else { 885 // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the 886 // result is one, otherwise it's zero. 887 return new ZExtInst(Builder->CreateICmpEQ(Op1, One), I.getType()); 888 } 889 } 890 } 891 892 // See if we can fold away this div instruction. 893 if (SimplifyDemandedInstructionBits(I)) 894 return &I; 895 896 // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y 897 Value *X = nullptr, *Z = nullptr; 898 if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1 899 bool isSigned = I.getOpcode() == Instruction::SDiv; 900 if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) || 901 (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1))))) 902 return BinaryOperator::Create(I.getOpcode(), X, Op1); 903 } 904 905 return nullptr; 906} 907 908/// dyn_castZExtVal - Checks if V is a zext or constant that can 909/// be truncated to Ty without losing bits. 910static Value *dyn_castZExtVal(Value *V, Type *Ty) { 911 if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) { 912 if (Z->getSrcTy() == Ty) 913 return Z->getOperand(0); 914 } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) { 915 if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth()) 916 return ConstantExpr::getTrunc(C, Ty); 917 } 918 return nullptr; 919} 920 921namespace { 922const unsigned MaxDepth = 6; 923typedef Instruction *(*FoldUDivOperandCb)(Value *Op0, Value *Op1, 924 const BinaryOperator &I, 925 InstCombiner &IC); 926 927/// \brief Used to maintain state for visitUDivOperand(). 928struct UDivFoldAction { 929 FoldUDivOperandCb FoldAction; ///< Informs visitUDiv() how to fold this 930 ///< operand. This can be zero if this action 931 ///< joins two actions together. 932 933 Value *OperandToFold; ///< Which operand to fold. 934 union { 935 Instruction *FoldResult; ///< The instruction returned when FoldAction is 936 ///< invoked. 937 938 size_t SelectLHSIdx; ///< Stores the LHS action index if this action 939 ///< joins two actions together. 940 }; 941 942 UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand) 943 : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {} 944 UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS) 945 : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {} 946}; 947} 948 949// X udiv 2^C -> X >> C 950static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1, 951 const BinaryOperator &I, InstCombiner &IC) { 952 const APInt &C = cast<Constant>(Op1)->getUniqueInteger(); 953 BinaryOperator *LShr = BinaryOperator::CreateLShr( 954 Op0, ConstantInt::get(Op0->getType(), C.logBase2())); 955 if (I.isExact()) 956 LShr->setIsExact(); 957 return LShr; 958} 959 960// X udiv C, where C >= signbit 961static Instruction *foldUDivNegCst(Value *Op0, Value *Op1, 962 const BinaryOperator &I, InstCombiner &IC) { 963 Value *ICI = IC.Builder->CreateICmpULT(Op0, cast<ConstantInt>(Op1)); 964 965 return SelectInst::Create(ICI, Constant::getNullValue(I.getType()), 966 ConstantInt::get(I.getType(), 1)); 967} 968 969// X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 970static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I, 971 InstCombiner &IC) { 972 Instruction *ShiftLeft = cast<Instruction>(Op1); 973 if (isa<ZExtInst>(ShiftLeft)) 974 ShiftLeft = cast<Instruction>(ShiftLeft->getOperand(0)); 975 976 const APInt &CI = 977 cast<Constant>(ShiftLeft->getOperand(0))->getUniqueInteger(); 978 Value *N = ShiftLeft->getOperand(1); 979 if (CI != 1) 980 N = IC.Builder->CreateAdd(N, ConstantInt::get(N->getType(), CI.logBase2())); 981 if (ZExtInst *Z = dyn_cast<ZExtInst>(Op1)) 982 N = IC.Builder->CreateZExt(N, Z->getDestTy()); 983 BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N); 984 if (I.isExact()) 985 LShr->setIsExact(); 986 return LShr; 987} 988 989// \brief Recursively visits the possible right hand operands of a udiv 990// instruction, seeing through select instructions, to determine if we can 991// replace the udiv with something simpler. If we find that an operand is not 992// able to simplify the udiv, we abort the entire transformation. 993static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I, 994 SmallVectorImpl<UDivFoldAction> &Actions, 995 unsigned Depth = 0) { 996 // Check to see if this is an unsigned division with an exact power of 2, 997 // if so, convert to a right shift. 998 if (match(Op1, m_Power2())) { 999 Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1)); 1000 return Actions.size(); 1001 } 1002 1003 if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) 1004 // X udiv C, where C >= signbit 1005 if (C->getValue().isNegative()) { 1006 Actions.push_back(UDivFoldAction(foldUDivNegCst, C)); 1007 return Actions.size(); 1008 } 1009 1010 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 1011 if (match(Op1, m_Shl(m_Power2(), m_Value())) || 1012 match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) { 1013 Actions.push_back(UDivFoldAction(foldUDivShl, Op1)); 1014 return Actions.size(); 1015 } 1016 1017 // The remaining tests are all recursive, so bail out if we hit the limit. 1018 if (Depth++ == MaxDepth) 1019 return 0; 1020 1021 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 1022 if (size_t LHSIdx = 1023 visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth)) 1024 if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) { 1025 Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1)); 1026 return Actions.size(); 1027 } 1028 1029 return 0; 1030} 1031 1032Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { 1033 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1034 1035 if (Value *V = SimplifyVectorOp(I)) 1036 return ReplaceInstUsesWith(I, V); 1037 1038 if (Value *V = SimplifyUDivInst(Op0, Op1, DL, TLI, DT, AC)) 1039 return ReplaceInstUsesWith(I, V); 1040 1041 // Handle the integer div common cases 1042 if (Instruction *Common = commonIDivTransforms(I)) 1043 return Common; 1044 1045 // (x lshr C1) udiv C2 --> x udiv (C2 << C1) 1046 { 1047 Value *X; 1048 const APInt *C1, *C2; 1049 if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && 1050 match(Op1, m_APInt(C2))) { 1051 bool Overflow; 1052 APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow); 1053 if (!Overflow) { 1054 bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value())); 1055 BinaryOperator *BO = BinaryOperator::CreateUDiv( 1056 X, ConstantInt::get(X->getType(), C2ShlC1)); 1057 if (IsExact) 1058 BO->setIsExact(); 1059 return BO; 1060 } 1061 } 1062 } 1063 1064 // (zext A) udiv (zext B) --> zext (A udiv B) 1065 if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 1066 if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 1067 return new ZExtInst( 1068 Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div", I.isExact()), 1069 I.getType()); 1070 1071 // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...)))) 1072 SmallVector<UDivFoldAction, 6> UDivActions; 1073 if (visitUDivOperand(Op0, Op1, I, UDivActions)) 1074 for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) { 1075 FoldUDivOperandCb Action = UDivActions[i].FoldAction; 1076 Value *ActionOp1 = UDivActions[i].OperandToFold; 1077 Instruction *Inst; 1078 if (Action) 1079 Inst = Action(Op0, ActionOp1, I, *this); 1080 else { 1081 // This action joins two actions together. The RHS of this action is 1082 // simply the last action we processed, we saved the LHS action index in 1083 // the joining action. 1084 size_t SelectRHSIdx = i - 1; 1085 Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult; 1086 size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx; 1087 Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult; 1088 Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(), 1089 SelectLHS, SelectRHS); 1090 } 1091 1092 // If this is the last action to process, return it to the InstCombiner. 1093 // Otherwise, we insert it before the UDiv and record it so that we may 1094 // use it as part of a joining action (i.e., a SelectInst). 1095 if (e - i != 1) { 1096 Inst->insertBefore(&I); 1097 UDivActions[i].FoldResult = Inst; 1098 } else 1099 return Inst; 1100 } 1101 1102 return nullptr; 1103} 1104 1105Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { 1106 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1107 1108 if (Value *V = SimplifyVectorOp(I)) 1109 return ReplaceInstUsesWith(I, V); 1110 1111 if (Value *V = SimplifySDivInst(Op0, Op1, DL, TLI, DT, AC)) 1112 return ReplaceInstUsesWith(I, V); 1113 1114 // Handle the integer div common cases 1115 if (Instruction *Common = commonIDivTransforms(I)) 1116 return Common; 1117 1118 // sdiv X, -1 == -X 1119 if (match(Op1, m_AllOnes())) 1120 return BinaryOperator::CreateNeg(Op0); 1121 1122 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 1123 // sdiv X, C --> ashr exact X, log2(C) 1124 if (I.isExact() && RHS->getValue().isNonNegative() && 1125 RHS->getValue().isPowerOf2()) { 1126 Value *ShAmt = llvm::ConstantInt::get(RHS->getType(), 1127 RHS->getValue().exactLogBase2()); 1128 return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName()); 1129 } 1130 } 1131 1132 if (Constant *RHS = dyn_cast<Constant>(Op1)) { 1133 // X/INT_MIN -> X == INT_MIN 1134 if (RHS->isMinSignedValue()) 1135 return new ZExtInst(Builder->CreateICmpEQ(Op0, Op1), I.getType()); 1136 1137 // -X/C --> X/-C provided the negation doesn't overflow. 1138 Value *X; 1139 if (match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) { 1140 auto *BO = BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(RHS)); 1141 BO->setIsExact(I.isExact()); 1142 return BO; 1143 } 1144 } 1145 1146 // If the sign bits of both operands are zero (i.e. we can prove they are 1147 // unsigned inputs), turn this into a udiv. 1148 if (I.getType()->isIntegerTy()) { 1149 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 1150 if (MaskedValueIsZero(Op0, Mask, 0, &I)) { 1151 if (MaskedValueIsZero(Op1, Mask, 0, &I)) { 1152 // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set 1153 auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 1154 BO->setIsExact(I.isExact()); 1155 return BO; 1156 } 1157 1158 if (isKnownToBeAPowerOfTwo(Op1, DL, /*OrZero*/ true, 0, AC, &I, DT)) { 1159 // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y) 1160 // Safe because the only negative value (1 << Y) can take on is 1161 // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have 1162 // the sign bit set. 1163 auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 1164 BO->setIsExact(I.isExact()); 1165 return BO; 1166 } 1167 } 1168 } 1169 1170 return nullptr; 1171} 1172 1173/// CvtFDivConstToReciprocal tries to convert X/C into X*1/C if C not a special 1174/// FP value and: 1175/// 1) 1/C is exact, or 1176/// 2) reciprocal is allowed. 1177/// If the conversion was successful, the simplified expression "X * 1/C" is 1178/// returned; otherwise, NULL is returned. 1179/// 1180static Instruction *CvtFDivConstToReciprocal(Value *Dividend, Constant *Divisor, 1181 bool AllowReciprocal) { 1182 if (!isa<ConstantFP>(Divisor)) // TODO: handle vectors. 1183 return nullptr; 1184 1185 const APFloat &FpVal = cast<ConstantFP>(Divisor)->getValueAPF(); 1186 APFloat Reciprocal(FpVal.getSemantics()); 1187 bool Cvt = FpVal.getExactInverse(&Reciprocal); 1188 1189 if (!Cvt && AllowReciprocal && FpVal.isFiniteNonZero()) { 1190 Reciprocal = APFloat(FpVal.getSemantics(), 1.0f); 1191 (void)Reciprocal.divide(FpVal, APFloat::rmNearestTiesToEven); 1192 Cvt = !Reciprocal.isDenormal(); 1193 } 1194 1195 if (!Cvt) 1196 return nullptr; 1197 1198 ConstantFP *R; 1199 R = ConstantFP::get(Dividend->getType()->getContext(), Reciprocal); 1200 return BinaryOperator::CreateFMul(Dividend, R); 1201} 1202 1203Instruction *InstCombiner::visitFDiv(BinaryOperator &I) { 1204 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1205 1206 if (Value *V = SimplifyVectorOp(I)) 1207 return ReplaceInstUsesWith(I, V); 1208 1209 if (Value *V = SimplifyFDivInst(Op0, Op1, I.getFastMathFlags(), 1210 DL, TLI, DT, AC)) 1211 return ReplaceInstUsesWith(I, V); 1212 1213 if (isa<Constant>(Op0)) 1214 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 1215 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1216 return R; 1217 1218 bool AllowReassociate = I.hasUnsafeAlgebra(); 1219 bool AllowReciprocal = I.hasAllowReciprocal(); 1220 1221 if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 1222 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 1223 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1224 return R; 1225 1226 if (AllowReassociate) { 1227 Constant *C1 = nullptr; 1228 Constant *C2 = Op1C; 1229 Value *X; 1230 Instruction *Res = nullptr; 1231 1232 if (match(Op0, m_FMul(m_Value(X), m_Constant(C1)))) { 1233 // (X*C1)/C2 => X * (C1/C2) 1234 // 1235 Constant *C = ConstantExpr::getFDiv(C1, C2); 1236 if (isNormalFp(C)) 1237 Res = BinaryOperator::CreateFMul(X, C); 1238 } else if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) { 1239 // (X/C1)/C2 => X /(C2*C1) [=> X * 1/(C2*C1) if reciprocal is allowed] 1240 // 1241 Constant *C = ConstantExpr::getFMul(C1, C2); 1242 if (isNormalFp(C)) { 1243 Res = CvtFDivConstToReciprocal(X, C, AllowReciprocal); 1244 if (!Res) 1245 Res = BinaryOperator::CreateFDiv(X, C); 1246 } 1247 } 1248 1249 if (Res) { 1250 Res->setFastMathFlags(I.getFastMathFlags()); 1251 return Res; 1252 } 1253 } 1254 1255 // X / C => X * 1/C 1256 if (Instruction *T = CvtFDivConstToReciprocal(Op0, Op1C, AllowReciprocal)) { 1257 T->copyFastMathFlags(&I); 1258 return T; 1259 } 1260 1261 return nullptr; 1262 } 1263 1264 if (AllowReassociate && isa<Constant>(Op0)) { 1265 Constant *C1 = cast<Constant>(Op0), *C2; 1266 Constant *Fold = nullptr; 1267 Value *X; 1268 bool CreateDiv = true; 1269 1270 // C1 / (X*C2) => (C1/C2) / X 1271 if (match(Op1, m_FMul(m_Value(X), m_Constant(C2)))) 1272 Fold = ConstantExpr::getFDiv(C1, C2); 1273 else if (match(Op1, m_FDiv(m_Value(X), m_Constant(C2)))) { 1274 // C1 / (X/C2) => (C1*C2) / X 1275 Fold = ConstantExpr::getFMul(C1, C2); 1276 } else if (match(Op1, m_FDiv(m_Constant(C2), m_Value(X)))) { 1277 // C1 / (C2/X) => (C1/C2) * X 1278 Fold = ConstantExpr::getFDiv(C1, C2); 1279 CreateDiv = false; 1280 } 1281 1282 if (Fold && isNormalFp(Fold)) { 1283 Instruction *R = CreateDiv ? BinaryOperator::CreateFDiv(Fold, X) 1284 : BinaryOperator::CreateFMul(X, Fold); 1285 R->setFastMathFlags(I.getFastMathFlags()); 1286 return R; 1287 } 1288 return nullptr; 1289 } 1290 1291 if (AllowReassociate) { 1292 Value *X, *Y; 1293 Value *NewInst = nullptr; 1294 Instruction *SimpR = nullptr; 1295 1296 if (Op0->hasOneUse() && match(Op0, m_FDiv(m_Value(X), m_Value(Y)))) { 1297 // (X/Y) / Z => X / (Y*Z) 1298 // 1299 if (!isa<Constant>(Y) || !isa<Constant>(Op1)) { 1300 NewInst = Builder->CreateFMul(Y, Op1); 1301 if (Instruction *RI = dyn_cast<Instruction>(NewInst)) { 1302 FastMathFlags Flags = I.getFastMathFlags(); 1303 Flags &= cast<Instruction>(Op0)->getFastMathFlags(); 1304 RI->setFastMathFlags(Flags); 1305 } 1306 SimpR = BinaryOperator::CreateFDiv(X, NewInst); 1307 } 1308 } else if (Op1->hasOneUse() && match(Op1, m_FDiv(m_Value(X), m_Value(Y)))) { 1309 // Z / (X/Y) => Z*Y / X 1310 // 1311 if (!isa<Constant>(Y) || !isa<Constant>(Op0)) { 1312 NewInst = Builder->CreateFMul(Op0, Y); 1313 if (Instruction *RI = dyn_cast<Instruction>(NewInst)) { 1314 FastMathFlags Flags = I.getFastMathFlags(); 1315 Flags &= cast<Instruction>(Op1)->getFastMathFlags(); 1316 RI->setFastMathFlags(Flags); 1317 } 1318 SimpR = BinaryOperator::CreateFDiv(NewInst, X); 1319 } 1320 } 1321 1322 if (NewInst) { 1323 if (Instruction *T = dyn_cast<Instruction>(NewInst)) 1324 T->setDebugLoc(I.getDebugLoc()); 1325 SimpR->setFastMathFlags(I.getFastMathFlags()); 1326 return SimpR; 1327 } 1328 } 1329 1330 return nullptr; 1331} 1332 1333/// This function implements the transforms common to both integer remainder 1334/// instructions (urem and srem). It is called by the visitors to those integer 1335/// remainder instructions. 1336/// @brief Common integer remainder transforms 1337Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) { 1338 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1339 1340 // The RHS is known non-zero. 1341 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) { 1342 I.setOperand(1, V); 1343 return &I; 1344 } 1345 1346 // Handle cases involving: rem X, (select Cond, Y, Z) 1347 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 1348 return &I; 1349 1350 if (isa<Constant>(Op1)) { 1351 if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) { 1352 if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) { 1353 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1354 return R; 1355 } else if (isa<PHINode>(Op0I)) { 1356 if (Instruction *NV = FoldOpIntoPhi(I)) 1357 return NV; 1358 } 1359 1360 // See if we can fold away this rem instruction. 1361 if (SimplifyDemandedInstructionBits(I)) 1362 return &I; 1363 } 1364 } 1365 1366 return nullptr; 1367} 1368 1369Instruction *InstCombiner::visitURem(BinaryOperator &I) { 1370 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1371 1372 if (Value *V = SimplifyVectorOp(I)) 1373 return ReplaceInstUsesWith(I, V); 1374 1375 if (Value *V = SimplifyURemInst(Op0, Op1, DL, TLI, DT, AC)) 1376 return ReplaceInstUsesWith(I, V); 1377 1378 if (Instruction *common = commonIRemTransforms(I)) 1379 return common; 1380 1381 // (zext A) urem (zext B) --> zext (A urem B) 1382 if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 1383 if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 1384 return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1), 1385 I.getType()); 1386 1387 // X urem Y -> X and Y-1, where Y is a power of 2, 1388 if (isKnownToBeAPowerOfTwo(Op1, DL, /*OrZero*/ true, 0, AC, &I, DT)) { 1389 Constant *N1 = Constant::getAllOnesValue(I.getType()); 1390 Value *Add = Builder->CreateAdd(Op1, N1); 1391 return BinaryOperator::CreateAnd(Op0, Add); 1392 } 1393 1394 // 1 urem X -> zext(X != 1) 1395 if (match(Op0, m_One())) { 1396 Value *Cmp = Builder->CreateICmpNE(Op1, Op0); 1397 Value *Ext = Builder->CreateZExt(Cmp, I.getType()); 1398 return ReplaceInstUsesWith(I, Ext); 1399 } 1400 1401 return nullptr; 1402} 1403 1404Instruction *InstCombiner::visitSRem(BinaryOperator &I) { 1405 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1406 1407 if (Value *V = SimplifyVectorOp(I)) 1408 return ReplaceInstUsesWith(I, V); 1409 1410 if (Value *V = SimplifySRemInst(Op0, Op1, DL, TLI, DT, AC)) 1411 return ReplaceInstUsesWith(I, V); 1412 1413 // Handle the integer rem common cases 1414 if (Instruction *Common = commonIRemTransforms(I)) 1415 return Common; 1416 1417 { 1418 const APInt *Y; 1419 // X % -Y -> X % Y 1420 if (match(Op1, m_APInt(Y)) && Y->isNegative() && !Y->isMinSignedValue()) { 1421 Worklist.AddValue(I.getOperand(1)); 1422 I.setOperand(1, ConstantInt::get(I.getType(), -*Y)); 1423 return &I; 1424 } 1425 } 1426 1427 // If the sign bits of both operands are zero (i.e. we can prove they are 1428 // unsigned inputs), turn this into a urem. 1429 if (I.getType()->isIntegerTy()) { 1430 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 1431 if (MaskedValueIsZero(Op1, Mask, 0, &I) && 1432 MaskedValueIsZero(Op0, Mask, 0, &I)) { 1433 // X srem Y -> X urem Y, iff X and Y don't have sign bit set 1434 return BinaryOperator::CreateURem(Op0, Op1, I.getName()); 1435 } 1436 } 1437 1438 // If it's a constant vector, flip any negative values positive. 1439 if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) { 1440 Constant *C = cast<Constant>(Op1); 1441 unsigned VWidth = C->getType()->getVectorNumElements(); 1442 1443 bool hasNegative = false; 1444 bool hasMissing = false; 1445 for (unsigned i = 0; i != VWidth; ++i) { 1446 Constant *Elt = C->getAggregateElement(i); 1447 if (!Elt) { 1448 hasMissing = true; 1449 break; 1450 } 1451 1452 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt)) 1453 if (RHS->isNegative()) 1454 hasNegative = true; 1455 } 1456 1457 if (hasNegative && !hasMissing) { 1458 SmallVector<Constant *, 16> Elts(VWidth); 1459 for (unsigned i = 0; i != VWidth; ++i) { 1460 Elts[i] = C->getAggregateElement(i); // Handle undef, etc. 1461 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) { 1462 if (RHS->isNegative()) 1463 Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS)); 1464 } 1465 } 1466 1467 Constant *NewRHSV = ConstantVector::get(Elts); 1468 if (NewRHSV != C) { // Don't loop on -MININT 1469 Worklist.AddValue(I.getOperand(1)); 1470 I.setOperand(1, NewRHSV); 1471 return &I; 1472 } 1473 } 1474 } 1475 1476 return nullptr; 1477} 1478 1479Instruction *InstCombiner::visitFRem(BinaryOperator &I) { 1480 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1481 1482 if (Value *V = SimplifyVectorOp(I)) 1483 return ReplaceInstUsesWith(I, V); 1484 1485 if (Value *V = SimplifyFRemInst(Op0, Op1, I.getFastMathFlags(), 1486 DL, TLI, DT, AC)) 1487 return ReplaceInstUsesWith(I, V); 1488 1489 // Handle cases involving: rem X, (select Cond, Y, Z) 1490 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 1491 return &I; 1492 1493 return nullptr; 1494} 1495