1 //===- InstCombineMulDivRem.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 visit functions for mul, fmul, sdiv, udiv, fdiv, 10 // srem, urem, frem. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "InstCombineInternal.h" 15 #include "llvm/ADT/APInt.h" 16 #include "llvm/ADT/SmallVector.h" 17 #include "llvm/Analysis/InstructionSimplify.h" 18 #include "llvm/Analysis/ValueTracking.h" 19 #include "llvm/IR/BasicBlock.h" 20 #include "llvm/IR/Constant.h" 21 #include "llvm/IR/Constants.h" 22 #include "llvm/IR/InstrTypes.h" 23 #include "llvm/IR/Instruction.h" 24 #include "llvm/IR/Instructions.h" 25 #include "llvm/IR/IntrinsicInst.h" 26 #include "llvm/IR/Intrinsics.h" 27 #include "llvm/IR/Operator.h" 28 #include "llvm/IR/PatternMatch.h" 29 #include "llvm/IR/Type.h" 30 #include "llvm/IR/Value.h" 31 #include "llvm/Support/Casting.h" 32 #include "llvm/Support/ErrorHandling.h" 33 #include "llvm/Transforms/InstCombine/InstCombiner.h" 34 #include "llvm/Transforms/Utils/BuildLibCalls.h" 35 #include <cassert> 36 37 #define DEBUG_TYPE "instcombine" 38 #include "llvm/Transforms/Utils/InstructionWorklist.h" 39 40 using namespace llvm; 41 using namespace PatternMatch; 42 43 /// The specific integer value is used in a context where it is known to be 44 /// non-zero. If this allows us to simplify the computation, do so and return 45 /// the new operand, otherwise return null. 46 static Value *simplifyValueKnownNonZero(Value *V, InstCombinerImpl &IC, 47 Instruction &CxtI) { 48 // If V has multiple uses, then we would have to do more analysis to determine 49 // if this is safe. For example, the use could be in dynamically unreached 50 // code. 51 if (!V->hasOneUse()) return nullptr; 52 53 bool MadeChange = false; 54 55 // ((1 << A) >>u B) --> (1 << (A-B)) 56 // Because V cannot be zero, we know that B is less than A. 57 Value *A = nullptr, *B = nullptr, *One = nullptr; 58 if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(One), m_Value(A))), m_Value(B))) && 59 match(One, m_One())) { 60 A = IC.Builder.CreateSub(A, B); 61 return IC.Builder.CreateShl(One, A); 62 } 63 64 // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it 65 // inexact. Similarly for <<. 66 BinaryOperator *I = dyn_cast<BinaryOperator>(V); 67 if (I && I->isLogicalShift() && 68 IC.isKnownToBeAPowerOfTwo(I->getOperand(0), false, 0, &CxtI)) { 69 // We know that this is an exact/nuw shift and that the input is a 70 // non-zero context as well. 71 if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) { 72 IC.replaceOperand(*I, 0, V2); 73 MadeChange = true; 74 } 75 76 if (I->getOpcode() == Instruction::LShr && !I->isExact()) { 77 I->setIsExact(); 78 MadeChange = true; 79 } 80 81 if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) { 82 I->setHasNoUnsignedWrap(); 83 MadeChange = true; 84 } 85 } 86 87 // TODO: Lots more we could do here: 88 // If V is a phi node, we can call this on each of its operands. 89 // "select cond, X, 0" can simplify to "X". 90 91 return MadeChange ? V : nullptr; 92 } 93 94 // TODO: This is a specific form of a much more general pattern. 95 // We could detect a select with any binop identity constant, or we 96 // could use SimplifyBinOp to see if either arm of the select reduces. 97 // But that needs to be done carefully and/or while removing potential 98 // reverse canonicalizations as in InstCombiner::foldSelectIntoOp(). 99 static Value *foldMulSelectToNegate(BinaryOperator &I, 100 InstCombiner::BuilderTy &Builder) { 101 Value *Cond, *OtherOp; 102 103 // mul (select Cond, 1, -1), OtherOp --> select Cond, OtherOp, -OtherOp 104 // mul OtherOp, (select Cond, 1, -1) --> select Cond, OtherOp, -OtherOp 105 if (match(&I, m_c_Mul(m_OneUse(m_Select(m_Value(Cond), m_One(), m_AllOnes())), 106 m_Value(OtherOp)))) { 107 bool HasAnyNoWrap = I.hasNoSignedWrap() || I.hasNoUnsignedWrap(); 108 Value *Neg = Builder.CreateNeg(OtherOp, "", false, HasAnyNoWrap); 109 return Builder.CreateSelect(Cond, OtherOp, Neg); 110 } 111 // mul (select Cond, -1, 1), OtherOp --> select Cond, -OtherOp, OtherOp 112 // mul OtherOp, (select Cond, -1, 1) --> select Cond, -OtherOp, OtherOp 113 if (match(&I, m_c_Mul(m_OneUse(m_Select(m_Value(Cond), m_AllOnes(), m_One())), 114 m_Value(OtherOp)))) { 115 bool HasAnyNoWrap = I.hasNoSignedWrap() || I.hasNoUnsignedWrap(); 116 Value *Neg = Builder.CreateNeg(OtherOp, "", false, HasAnyNoWrap); 117 return Builder.CreateSelect(Cond, Neg, OtherOp); 118 } 119 120 // fmul (select Cond, 1.0, -1.0), OtherOp --> select Cond, OtherOp, -OtherOp 121 // fmul OtherOp, (select Cond, 1.0, -1.0) --> select Cond, OtherOp, -OtherOp 122 if (match(&I, m_c_FMul(m_OneUse(m_Select(m_Value(Cond), m_SpecificFP(1.0), 123 m_SpecificFP(-1.0))), 124 m_Value(OtherOp)))) { 125 IRBuilder<>::FastMathFlagGuard FMFGuard(Builder); 126 Builder.setFastMathFlags(I.getFastMathFlags()); 127 return Builder.CreateSelect(Cond, OtherOp, Builder.CreateFNeg(OtherOp)); 128 } 129 130 // fmul (select Cond, -1.0, 1.0), OtherOp --> select Cond, -OtherOp, OtherOp 131 // fmul OtherOp, (select Cond, -1.0, 1.0) --> select Cond, -OtherOp, OtherOp 132 if (match(&I, m_c_FMul(m_OneUse(m_Select(m_Value(Cond), m_SpecificFP(-1.0), 133 m_SpecificFP(1.0))), 134 m_Value(OtherOp)))) { 135 IRBuilder<>::FastMathFlagGuard FMFGuard(Builder); 136 Builder.setFastMathFlags(I.getFastMathFlags()); 137 return Builder.CreateSelect(Cond, Builder.CreateFNeg(OtherOp), OtherOp); 138 } 139 140 return nullptr; 141 } 142 143 /// Reduce integer multiplication patterns that contain a (+/-1 << Z) factor. 144 /// Callers are expected to call this twice to handle commuted patterns. 145 static Value *foldMulShl1(BinaryOperator &Mul, bool CommuteOperands, 146 InstCombiner::BuilderTy &Builder) { 147 Value *X = Mul.getOperand(0), *Y = Mul.getOperand(1); 148 if (CommuteOperands) 149 std::swap(X, Y); 150 151 const bool HasNSW = Mul.hasNoSignedWrap(); 152 const bool HasNUW = Mul.hasNoUnsignedWrap(); 153 154 // X * (1 << Z) --> X << Z 155 Value *Z; 156 if (match(Y, m_Shl(m_One(), m_Value(Z)))) { 157 bool PropagateNSW = HasNSW && cast<ShlOperator>(Y)->hasNoSignedWrap(); 158 return Builder.CreateShl(X, Z, Mul.getName(), HasNUW, PropagateNSW); 159 } 160 161 // Similar to above, but an increment of the shifted value becomes an add: 162 // X * ((1 << Z) + 1) --> (X * (1 << Z)) + X --> (X << Z) + X 163 // This increases uses of X, so it may require a freeze, but that is still 164 // expected to be an improvement because it removes the multiply. 165 BinaryOperator *Shift; 166 if (match(Y, m_OneUse(m_Add(m_BinOp(Shift), m_One()))) && 167 match(Shift, m_OneUse(m_Shl(m_One(), m_Value(Z))))) { 168 bool PropagateNSW = HasNSW && Shift->hasNoSignedWrap(); 169 Value *FrX = Builder.CreateFreeze(X, X->getName() + ".fr"); 170 Value *Shl = Builder.CreateShl(FrX, Z, "mulshl", HasNUW, PropagateNSW); 171 return Builder.CreateAdd(Shl, FrX, Mul.getName(), HasNUW, PropagateNSW); 172 } 173 174 // Similar to above, but a decrement of the shifted value is disguised as 175 // 'not' and becomes a sub: 176 // X * (~(-1 << Z)) --> X * ((1 << Z) - 1) --> (X << Z) - X 177 // This increases uses of X, so it may require a freeze, but that is still 178 // expected to be an improvement because it removes the multiply. 179 if (match(Y, m_OneUse(m_Not(m_OneUse(m_Shl(m_AllOnes(), m_Value(Z))))))) { 180 Value *FrX = Builder.CreateFreeze(X, X->getName() + ".fr"); 181 Value *Shl = Builder.CreateShl(FrX, Z, "mulshl"); 182 return Builder.CreateSub(Shl, FrX, Mul.getName()); 183 } 184 185 return nullptr; 186 } 187 188 Instruction *InstCombinerImpl::visitMul(BinaryOperator &I) { 189 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 190 if (Value *V = 191 simplifyMulInst(Op0, Op1, I.hasNoSignedWrap(), I.hasNoUnsignedWrap(), 192 SQ.getWithInstruction(&I))) 193 return replaceInstUsesWith(I, V); 194 195 if (SimplifyAssociativeOrCommutative(I)) 196 return &I; 197 198 if (Instruction *X = foldVectorBinop(I)) 199 return X; 200 201 if (Instruction *Phi = foldBinopWithPhiOperands(I)) 202 return Phi; 203 204 if (Value *V = foldUsingDistributiveLaws(I)) 205 return replaceInstUsesWith(I, V); 206 207 Type *Ty = I.getType(); 208 const unsigned BitWidth = Ty->getScalarSizeInBits(); 209 const bool HasNSW = I.hasNoSignedWrap(); 210 const bool HasNUW = I.hasNoUnsignedWrap(); 211 212 // X * -1 --> 0 - X 213 if (match(Op1, m_AllOnes())) { 214 return HasNSW ? BinaryOperator::CreateNSWNeg(Op0) 215 : BinaryOperator::CreateNeg(Op0); 216 } 217 218 // Also allow combining multiply instructions on vectors. 219 { 220 Value *NewOp; 221 Constant *C1, *C2; 222 const APInt *IVal; 223 if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)), 224 m_Constant(C1))) && 225 match(C1, m_APInt(IVal))) { 226 // ((X << C2)*C1) == (X * (C1 << C2)) 227 Constant *Shl = ConstantExpr::getShl(C1, C2); 228 BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0)); 229 BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl); 230 if (HasNUW && Mul->hasNoUnsignedWrap()) 231 BO->setHasNoUnsignedWrap(); 232 if (HasNSW && Mul->hasNoSignedWrap() && Shl->isNotMinSignedValue()) 233 BO->setHasNoSignedWrap(); 234 return BO; 235 } 236 237 if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) { 238 // Replace X*(2^C) with X << C, where C is either a scalar or a vector. 239 if (Constant *NewCst = ConstantExpr::getExactLogBase2(C1)) { 240 BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst); 241 242 if (HasNUW) 243 Shl->setHasNoUnsignedWrap(); 244 if (HasNSW) { 245 const APInt *V; 246 if (match(NewCst, m_APInt(V)) && *V != V->getBitWidth() - 1) 247 Shl->setHasNoSignedWrap(); 248 } 249 250 return Shl; 251 } 252 } 253 } 254 255 if (Op0->hasOneUse() && match(Op1, m_NegatedPower2())) { 256 // Interpret X * (-1<<C) as (-X) * (1<<C) and try to sink the negation. 257 // The "* (1<<C)" thus becomes a potential shifting opportunity. 258 if (Value *NegOp0 = Negator::Negate(/*IsNegation*/ true, Op0, *this)) 259 return BinaryOperator::CreateMul( 260 NegOp0, ConstantExpr::getNeg(cast<Constant>(Op1)), I.getName()); 261 262 // Try to convert multiply of extended operand to narrow negate and shift 263 // for better analysis. 264 // This is valid if the shift amount (trailing zeros in the multiplier 265 // constant) clears more high bits than the bitwidth difference between 266 // source and destination types: 267 // ({z/s}ext X) * (-1<<C) --> (zext (-X)) << C 268 const APInt *NegPow2C; 269 Value *X; 270 if (match(Op0, m_ZExtOrSExt(m_Value(X))) && 271 match(Op1, m_APIntAllowUndef(NegPow2C))) { 272 unsigned SrcWidth = X->getType()->getScalarSizeInBits(); 273 unsigned ShiftAmt = NegPow2C->countTrailingZeros(); 274 if (ShiftAmt >= BitWidth - SrcWidth) { 275 Value *N = Builder.CreateNeg(X, X->getName() + ".neg"); 276 Value *Z = Builder.CreateZExt(N, Ty, N->getName() + ".z"); 277 return BinaryOperator::CreateShl(Z, ConstantInt::get(Ty, ShiftAmt)); 278 } 279 } 280 } 281 282 if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I)) 283 return FoldedMul; 284 285 if (Value *FoldedMul = foldMulSelectToNegate(I, Builder)) 286 return replaceInstUsesWith(I, FoldedMul); 287 288 // Simplify mul instructions with a constant RHS. 289 Constant *MulC; 290 if (match(Op1, m_ImmConstant(MulC))) { 291 // Canonicalize (X+C1)*MulC -> X*MulC+C1*MulC. 292 // Canonicalize (X|C1)*MulC -> X*MulC+C1*MulC. 293 Value *X; 294 Constant *C1; 295 if ((match(Op0, m_OneUse(m_Add(m_Value(X), m_ImmConstant(C1))))) || 296 (match(Op0, m_OneUse(m_Or(m_Value(X), m_ImmConstant(C1)))) && 297 haveNoCommonBitsSet(X, C1, DL, &AC, &I, &DT))) { 298 // C1*MulC simplifies to a tidier constant. 299 Value *NewC = Builder.CreateMul(C1, MulC); 300 auto *BOp0 = cast<BinaryOperator>(Op0); 301 bool Op0NUW = 302 (BOp0->getOpcode() == Instruction::Or || BOp0->hasNoUnsignedWrap()); 303 Value *NewMul = Builder.CreateMul(X, MulC); 304 auto *BO = BinaryOperator::CreateAdd(NewMul, NewC); 305 if (HasNUW && Op0NUW) { 306 // If NewMulBO is constant we also can set BO to nuw. 307 if (auto *NewMulBO = dyn_cast<BinaryOperator>(NewMul)) 308 NewMulBO->setHasNoUnsignedWrap(); 309 BO->setHasNoUnsignedWrap(); 310 } 311 return BO; 312 } 313 } 314 315 // abs(X) * abs(X) -> X * X 316 // nabs(X) * nabs(X) -> X * X 317 if (Op0 == Op1) { 318 Value *X, *Y; 319 SelectPatternFlavor SPF = matchSelectPattern(Op0, X, Y).Flavor; 320 if (SPF == SPF_ABS || SPF == SPF_NABS) 321 return BinaryOperator::CreateMul(X, X); 322 323 if (match(Op0, m_Intrinsic<Intrinsic::abs>(m_Value(X)))) 324 return BinaryOperator::CreateMul(X, X); 325 } 326 327 // -X * C --> X * -C 328 Value *X, *Y; 329 Constant *Op1C; 330 if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Constant(Op1C))) 331 return BinaryOperator::CreateMul(X, ConstantExpr::getNeg(Op1C)); 332 333 // -X * -Y --> X * Y 334 if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Neg(m_Value(Y)))) { 335 auto *NewMul = BinaryOperator::CreateMul(X, Y); 336 if (HasNSW && cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap() && 337 cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap()) 338 NewMul->setHasNoSignedWrap(); 339 return NewMul; 340 } 341 342 // -X * Y --> -(X * Y) 343 // X * -Y --> -(X * Y) 344 if (match(&I, m_c_Mul(m_OneUse(m_Neg(m_Value(X))), m_Value(Y)))) 345 return BinaryOperator::CreateNeg(Builder.CreateMul(X, Y)); 346 347 // (X / Y) * Y = X - (X % Y) 348 // (X / Y) * -Y = (X % Y) - X 349 { 350 Value *Y = Op1; 351 BinaryOperator *Div = dyn_cast<BinaryOperator>(Op0); 352 if (!Div || (Div->getOpcode() != Instruction::UDiv && 353 Div->getOpcode() != Instruction::SDiv)) { 354 Y = Op0; 355 Div = dyn_cast<BinaryOperator>(Op1); 356 } 357 Value *Neg = dyn_castNegVal(Y); 358 if (Div && Div->hasOneUse() && 359 (Div->getOperand(1) == Y || Div->getOperand(1) == Neg) && 360 (Div->getOpcode() == Instruction::UDiv || 361 Div->getOpcode() == Instruction::SDiv)) { 362 Value *X = Div->getOperand(0), *DivOp1 = Div->getOperand(1); 363 364 // If the division is exact, X % Y is zero, so we end up with X or -X. 365 if (Div->isExact()) { 366 if (DivOp1 == Y) 367 return replaceInstUsesWith(I, X); 368 return BinaryOperator::CreateNeg(X); 369 } 370 371 auto RemOpc = Div->getOpcode() == Instruction::UDiv ? Instruction::URem 372 : Instruction::SRem; 373 // X must be frozen because we are increasing its number of uses. 374 Value *XFreeze = Builder.CreateFreeze(X, X->getName() + ".fr"); 375 Value *Rem = Builder.CreateBinOp(RemOpc, XFreeze, DivOp1); 376 if (DivOp1 == Y) 377 return BinaryOperator::CreateSub(XFreeze, Rem); 378 return BinaryOperator::CreateSub(Rem, XFreeze); 379 } 380 } 381 382 // Fold the following two scenarios: 383 // 1) i1 mul -> i1 and. 384 // 2) X * Y --> X & Y, iff X, Y can be only {0,1}. 385 // Note: We could use known bits to generalize this and related patterns with 386 // shifts/truncs 387 if (Ty->isIntOrIntVectorTy(1) || 388 (match(Op0, m_And(m_Value(), m_One())) && 389 match(Op1, m_And(m_Value(), m_One())))) 390 return BinaryOperator::CreateAnd(Op0, Op1); 391 392 if (Value *R = foldMulShl1(I, /* CommuteOperands */ false, Builder)) 393 return replaceInstUsesWith(I, R); 394 if (Value *R = foldMulShl1(I, /* CommuteOperands */ true, Builder)) 395 return replaceInstUsesWith(I, R); 396 397 // (zext bool X) * (zext bool Y) --> zext (and X, Y) 398 // (sext bool X) * (sext bool Y) --> zext (and X, Y) 399 // Note: -1 * -1 == 1 * 1 == 1 (if the extends match, the result is the same) 400 if (((match(Op0, m_ZExt(m_Value(X))) && match(Op1, m_ZExt(m_Value(Y)))) || 401 (match(Op0, m_SExt(m_Value(X))) && match(Op1, m_SExt(m_Value(Y))))) && 402 X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType() && 403 (Op0->hasOneUse() || Op1->hasOneUse() || X == Y)) { 404 Value *And = Builder.CreateAnd(X, Y, "mulbool"); 405 return CastInst::Create(Instruction::ZExt, And, Ty); 406 } 407 // (sext bool X) * (zext bool Y) --> sext (and X, Y) 408 // (zext bool X) * (sext bool Y) --> sext (and X, Y) 409 // Note: -1 * 1 == 1 * -1 == -1 410 if (((match(Op0, m_SExt(m_Value(X))) && match(Op1, m_ZExt(m_Value(Y)))) || 411 (match(Op0, m_ZExt(m_Value(X))) && match(Op1, m_SExt(m_Value(Y))))) && 412 X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType() && 413 (Op0->hasOneUse() || Op1->hasOneUse())) { 414 Value *And = Builder.CreateAnd(X, Y, "mulbool"); 415 return CastInst::Create(Instruction::SExt, And, Ty); 416 } 417 418 // (zext bool X) * Y --> X ? Y : 0 419 // Y * (zext bool X) --> X ? Y : 0 420 if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) 421 return SelectInst::Create(X, Op1, ConstantInt::getNullValue(Ty)); 422 if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) 423 return SelectInst::Create(X, Op0, ConstantInt::getNullValue(Ty)); 424 425 Constant *ImmC; 426 if (match(Op1, m_ImmConstant(ImmC))) { 427 // (sext bool X) * C --> X ? -C : 0 428 if (match(Op0, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) { 429 Constant *NegC = ConstantExpr::getNeg(ImmC); 430 return SelectInst::Create(X, NegC, ConstantInt::getNullValue(Ty)); 431 } 432 433 // (ashr i32 X, 31) * C --> (X < 0) ? -C : 0 434 const APInt *C; 435 if (match(Op0, m_OneUse(m_AShr(m_Value(X), m_APInt(C)))) && 436 *C == C->getBitWidth() - 1) { 437 Constant *NegC = ConstantExpr::getNeg(ImmC); 438 Value *IsNeg = Builder.CreateIsNeg(X, "isneg"); 439 return SelectInst::Create(IsNeg, NegC, ConstantInt::getNullValue(Ty)); 440 } 441 } 442 443 // (lshr X, 31) * Y --> (X < 0) ? Y : 0 444 // TODO: We are not checking one-use because the elimination of the multiply 445 // is better for analysis? 446 const APInt *C; 447 if (match(&I, m_c_BinOp(m_LShr(m_Value(X), m_APInt(C)), m_Value(Y))) && 448 *C == C->getBitWidth() - 1) { 449 Value *IsNeg = Builder.CreateIsNeg(X, "isneg"); 450 return SelectInst::Create(IsNeg, Y, ConstantInt::getNullValue(Ty)); 451 } 452 453 // (and X, 1) * Y --> (trunc X) ? Y : 0 454 if (match(&I, m_c_BinOp(m_OneUse(m_And(m_Value(X), m_One())), m_Value(Y)))) { 455 Value *Tr = Builder.CreateTrunc(X, CmpInst::makeCmpResultType(Ty)); 456 return SelectInst::Create(Tr, Y, ConstantInt::getNullValue(Ty)); 457 } 458 459 // ((ashr X, 31) | 1) * X --> abs(X) 460 // X * ((ashr X, 31) | 1) --> abs(X) 461 if (match(&I, m_c_BinOp(m_Or(m_AShr(m_Value(X), 462 m_SpecificIntAllowUndef(BitWidth - 1)), 463 m_One()), 464 m_Deferred(X)))) { 465 Value *Abs = Builder.CreateBinaryIntrinsic( 466 Intrinsic::abs, X, ConstantInt::getBool(I.getContext(), HasNSW)); 467 Abs->takeName(&I); 468 return replaceInstUsesWith(I, Abs); 469 } 470 471 if (Instruction *Ext = narrowMathIfNoOverflow(I)) 472 return Ext; 473 474 bool Changed = false; 475 if (!HasNSW && willNotOverflowSignedMul(Op0, Op1, I)) { 476 Changed = true; 477 I.setHasNoSignedWrap(true); 478 } 479 480 if (!HasNUW && willNotOverflowUnsignedMul(Op0, Op1, I)) { 481 Changed = true; 482 I.setHasNoUnsignedWrap(true); 483 } 484 485 return Changed ? &I : nullptr; 486 } 487 488 Instruction *InstCombinerImpl::foldFPSignBitOps(BinaryOperator &I) { 489 BinaryOperator::BinaryOps Opcode = I.getOpcode(); 490 assert((Opcode == Instruction::FMul || Opcode == Instruction::FDiv) && 491 "Expected fmul or fdiv"); 492 493 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 494 Value *X, *Y; 495 496 // -X * -Y --> X * Y 497 // -X / -Y --> X / Y 498 if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y)))) 499 return BinaryOperator::CreateWithCopiedFlags(Opcode, X, Y, &I); 500 501 // fabs(X) * fabs(X) -> X * X 502 // fabs(X) / fabs(X) -> X / X 503 if (Op0 == Op1 && match(Op0, m_FAbs(m_Value(X)))) 504 return BinaryOperator::CreateWithCopiedFlags(Opcode, X, X, &I); 505 506 // fabs(X) * fabs(Y) --> fabs(X * Y) 507 // fabs(X) / fabs(Y) --> fabs(X / Y) 508 if (match(Op0, m_FAbs(m_Value(X))) && match(Op1, m_FAbs(m_Value(Y))) && 509 (Op0->hasOneUse() || Op1->hasOneUse())) { 510 IRBuilder<>::FastMathFlagGuard FMFGuard(Builder); 511 Builder.setFastMathFlags(I.getFastMathFlags()); 512 Value *XY = Builder.CreateBinOp(Opcode, X, Y); 513 Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, XY); 514 Fabs->takeName(&I); 515 return replaceInstUsesWith(I, Fabs); 516 } 517 518 return nullptr; 519 } 520 521 Instruction *InstCombinerImpl::visitFMul(BinaryOperator &I) { 522 if (Value *V = simplifyFMulInst(I.getOperand(0), I.getOperand(1), 523 I.getFastMathFlags(), 524 SQ.getWithInstruction(&I))) 525 return replaceInstUsesWith(I, V); 526 527 if (SimplifyAssociativeOrCommutative(I)) 528 return &I; 529 530 if (Instruction *X = foldVectorBinop(I)) 531 return X; 532 533 if (Instruction *Phi = foldBinopWithPhiOperands(I)) 534 return Phi; 535 536 if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I)) 537 return FoldedMul; 538 539 if (Value *FoldedMul = foldMulSelectToNegate(I, Builder)) 540 return replaceInstUsesWith(I, FoldedMul); 541 542 if (Instruction *R = foldFPSignBitOps(I)) 543 return R; 544 545 // X * -1.0 --> -X 546 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 547 if (match(Op1, m_SpecificFP(-1.0))) 548 return UnaryOperator::CreateFNegFMF(Op0, &I); 549 550 // With no-nans: X * 0.0 --> copysign(0.0, X) 551 if (I.hasNoNaNs() && match(Op1, m_PosZeroFP())) { 552 CallInst *CopySign = Builder.CreateIntrinsic(Intrinsic::copysign, 553 {I.getType()}, {Op1, Op0}, &I); 554 return replaceInstUsesWith(I, CopySign); 555 } 556 557 // -X * C --> X * -C 558 Value *X, *Y; 559 Constant *C; 560 if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_Constant(C))) 561 if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL)) 562 return BinaryOperator::CreateFMulFMF(X, NegC, &I); 563 564 // (select A, B, C) * (select A, D, E) --> select A, (B*D), (C*E) 565 if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1)) 566 return replaceInstUsesWith(I, V); 567 568 if (I.hasAllowReassoc()) { 569 // Reassociate constant RHS with another constant to form constant 570 // expression. 571 if (match(Op1, m_Constant(C)) && C->isFiniteNonZeroFP()) { 572 Constant *C1; 573 if (match(Op0, m_OneUse(m_FDiv(m_Constant(C1), m_Value(X))))) { 574 // (C1 / X) * C --> (C * C1) / X 575 Constant *CC1 = 576 ConstantFoldBinaryOpOperands(Instruction::FMul, C, C1, DL); 577 if (CC1 && CC1->isNormalFP()) 578 return BinaryOperator::CreateFDivFMF(CC1, X, &I); 579 } 580 if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) { 581 // (X / C1) * C --> X * (C / C1) 582 Constant *CDivC1 = 583 ConstantFoldBinaryOpOperands(Instruction::FDiv, C, C1, DL); 584 if (CDivC1 && CDivC1->isNormalFP()) 585 return BinaryOperator::CreateFMulFMF(X, CDivC1, &I); 586 587 // If the constant was a denormal, try reassociating differently. 588 // (X / C1) * C --> X / (C1 / C) 589 Constant *C1DivC = 590 ConstantFoldBinaryOpOperands(Instruction::FDiv, C1, C, DL); 591 if (C1DivC && Op0->hasOneUse() && C1DivC->isNormalFP()) 592 return BinaryOperator::CreateFDivFMF(X, C1DivC, &I); 593 } 594 595 // We do not need to match 'fadd C, X' and 'fsub X, C' because they are 596 // canonicalized to 'fadd X, C'. Distributing the multiply may allow 597 // further folds and (X * C) + C2 is 'fma'. 598 if (match(Op0, m_OneUse(m_FAdd(m_Value(X), m_Constant(C1))))) { 599 // (X + C1) * C --> (X * C) + (C * C1) 600 if (Constant *CC1 = ConstantFoldBinaryOpOperands( 601 Instruction::FMul, C, C1, DL)) { 602 Value *XC = Builder.CreateFMulFMF(X, C, &I); 603 return BinaryOperator::CreateFAddFMF(XC, CC1, &I); 604 } 605 } 606 if (match(Op0, m_OneUse(m_FSub(m_Constant(C1), m_Value(X))))) { 607 // (C1 - X) * C --> (C * C1) - (X * C) 608 if (Constant *CC1 = ConstantFoldBinaryOpOperands( 609 Instruction::FMul, C, C1, DL)) { 610 Value *XC = Builder.CreateFMulFMF(X, C, &I); 611 return BinaryOperator::CreateFSubFMF(CC1, XC, &I); 612 } 613 } 614 } 615 616 Value *Z; 617 if (match(&I, m_c_FMul(m_OneUse(m_FDiv(m_Value(X), m_Value(Y))), 618 m_Value(Z)))) { 619 // Sink division: (X / Y) * Z --> (X * Z) / Y 620 Value *NewFMul = Builder.CreateFMulFMF(X, Z, &I); 621 return BinaryOperator::CreateFDivFMF(NewFMul, Y, &I); 622 } 623 624 // sqrt(X) * sqrt(Y) -> sqrt(X * Y) 625 // nnan disallows the possibility of returning a number if both operands are 626 // negative (in that case, we should return NaN). 627 if (I.hasNoNaNs() && match(Op0, m_OneUse(m_Sqrt(m_Value(X)))) && 628 match(Op1, m_OneUse(m_Sqrt(m_Value(Y))))) { 629 Value *XY = Builder.CreateFMulFMF(X, Y, &I); 630 Value *Sqrt = Builder.CreateUnaryIntrinsic(Intrinsic::sqrt, XY, &I); 631 return replaceInstUsesWith(I, Sqrt); 632 } 633 634 // The following transforms are done irrespective of the number of uses 635 // for the expression "1.0/sqrt(X)". 636 // 1) 1.0/sqrt(X) * X -> X/sqrt(X) 637 // 2) X * 1.0/sqrt(X) -> X/sqrt(X) 638 // We always expect the backend to reduce X/sqrt(X) to sqrt(X), if it 639 // has the necessary (reassoc) fast-math-flags. 640 if (I.hasNoSignedZeros() && 641 match(Op0, (m_FDiv(m_SpecificFP(1.0), m_Value(Y)))) && 642 match(Y, m_Sqrt(m_Value(X))) && Op1 == X) 643 return BinaryOperator::CreateFDivFMF(X, Y, &I); 644 if (I.hasNoSignedZeros() && 645 match(Op1, (m_FDiv(m_SpecificFP(1.0), m_Value(Y)))) && 646 match(Y, m_Sqrt(m_Value(X))) && Op0 == X) 647 return BinaryOperator::CreateFDivFMF(X, Y, &I); 648 649 // Like the similar transform in instsimplify, this requires 'nsz' because 650 // sqrt(-0.0) = -0.0, and -0.0 * -0.0 does not simplify to -0.0. 651 if (I.hasNoNaNs() && I.hasNoSignedZeros() && Op0 == Op1 && 652 Op0->hasNUses(2)) { 653 // Peek through fdiv to find squaring of square root: 654 // (X / sqrt(Y)) * (X / sqrt(Y)) --> (X * X) / Y 655 if (match(Op0, m_FDiv(m_Value(X), m_Sqrt(m_Value(Y))))) { 656 Value *XX = Builder.CreateFMulFMF(X, X, &I); 657 return BinaryOperator::CreateFDivFMF(XX, Y, &I); 658 } 659 // (sqrt(Y) / X) * (sqrt(Y) / X) --> Y / (X * X) 660 if (match(Op0, m_FDiv(m_Sqrt(m_Value(Y)), m_Value(X)))) { 661 Value *XX = Builder.CreateFMulFMF(X, X, &I); 662 return BinaryOperator::CreateFDivFMF(Y, XX, &I); 663 } 664 } 665 666 // pow(X, Y) * X --> pow(X, Y+1) 667 // X * pow(X, Y) --> pow(X, Y+1) 668 if (match(&I, m_c_FMul(m_OneUse(m_Intrinsic<Intrinsic::pow>(m_Value(X), 669 m_Value(Y))), 670 m_Deferred(X)))) { 671 Value *Y1 = 672 Builder.CreateFAddFMF(Y, ConstantFP::get(I.getType(), 1.0), &I); 673 Value *Pow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, X, Y1, &I); 674 return replaceInstUsesWith(I, Pow); 675 } 676 677 if (I.isOnlyUserOfAnyOperand()) { 678 // pow(X, Y) * pow(X, Z) -> pow(X, Y + Z) 679 if (match(Op0, m_Intrinsic<Intrinsic::pow>(m_Value(X), m_Value(Y))) && 680 match(Op1, m_Intrinsic<Intrinsic::pow>(m_Specific(X), m_Value(Z)))) { 681 auto *YZ = Builder.CreateFAddFMF(Y, Z, &I); 682 auto *NewPow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, X, YZ, &I); 683 return replaceInstUsesWith(I, NewPow); 684 } 685 // pow(X, Y) * pow(Z, Y) -> pow(X * Z, Y) 686 if (match(Op0, m_Intrinsic<Intrinsic::pow>(m_Value(X), m_Value(Y))) && 687 match(Op1, m_Intrinsic<Intrinsic::pow>(m_Value(Z), m_Specific(Y)))) { 688 auto *XZ = Builder.CreateFMulFMF(X, Z, &I); 689 auto *NewPow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, XZ, Y, &I); 690 return replaceInstUsesWith(I, NewPow); 691 } 692 693 // powi(x, y) * powi(x, z) -> powi(x, y + z) 694 if (match(Op0, m_Intrinsic<Intrinsic::powi>(m_Value(X), m_Value(Y))) && 695 match(Op1, m_Intrinsic<Intrinsic::powi>(m_Specific(X), m_Value(Z))) && 696 Y->getType() == Z->getType()) { 697 auto *YZ = Builder.CreateAdd(Y, Z); 698 auto *NewPow = Builder.CreateIntrinsic( 699 Intrinsic::powi, {X->getType(), YZ->getType()}, {X, YZ}, &I); 700 return replaceInstUsesWith(I, NewPow); 701 } 702 703 // exp(X) * exp(Y) -> exp(X + Y) 704 if (match(Op0, m_Intrinsic<Intrinsic::exp>(m_Value(X))) && 705 match(Op1, m_Intrinsic<Intrinsic::exp>(m_Value(Y)))) { 706 Value *XY = Builder.CreateFAddFMF(X, Y, &I); 707 Value *Exp = Builder.CreateUnaryIntrinsic(Intrinsic::exp, XY, &I); 708 return replaceInstUsesWith(I, Exp); 709 } 710 711 // exp2(X) * exp2(Y) -> exp2(X + Y) 712 if (match(Op0, m_Intrinsic<Intrinsic::exp2>(m_Value(X))) && 713 match(Op1, m_Intrinsic<Intrinsic::exp2>(m_Value(Y)))) { 714 Value *XY = Builder.CreateFAddFMF(X, Y, &I); 715 Value *Exp2 = Builder.CreateUnaryIntrinsic(Intrinsic::exp2, XY, &I); 716 return replaceInstUsesWith(I, Exp2); 717 } 718 } 719 720 // (X*Y) * X => (X*X) * Y where Y != X 721 // The purpose is two-fold: 722 // 1) to form a power expression (of X). 723 // 2) potentially shorten the critical path: After transformation, the 724 // latency of the instruction Y is amortized by the expression of X*X, 725 // and therefore Y is in a "less critical" position compared to what it 726 // was before the transformation. 727 if (match(Op0, m_OneUse(m_c_FMul(m_Specific(Op1), m_Value(Y)))) && 728 Op1 != Y) { 729 Value *XX = Builder.CreateFMulFMF(Op1, Op1, &I); 730 return BinaryOperator::CreateFMulFMF(XX, Y, &I); 731 } 732 if (match(Op1, m_OneUse(m_c_FMul(m_Specific(Op0), m_Value(Y)))) && 733 Op0 != Y) { 734 Value *XX = Builder.CreateFMulFMF(Op0, Op0, &I); 735 return BinaryOperator::CreateFMulFMF(XX, Y, &I); 736 } 737 } 738 739 // log2(X * 0.5) * Y = log2(X) * Y - Y 740 if (I.isFast()) { 741 IntrinsicInst *Log2 = nullptr; 742 if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::log2>( 743 m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) { 744 Log2 = cast<IntrinsicInst>(Op0); 745 Y = Op1; 746 } 747 if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::log2>( 748 m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) { 749 Log2 = cast<IntrinsicInst>(Op1); 750 Y = Op0; 751 } 752 if (Log2) { 753 Value *Log2 = Builder.CreateUnaryIntrinsic(Intrinsic::log2, X, &I); 754 Value *LogXTimesY = Builder.CreateFMulFMF(Log2, Y, &I); 755 return BinaryOperator::CreateFSubFMF(LogXTimesY, Y, &I); 756 } 757 } 758 759 // Simplify FMUL recurrences starting with 0.0 to 0.0 if nnan and nsz are set. 760 // Given a phi node with entry value as 0 and it used in fmul operation, 761 // we can replace fmul with 0 safely and eleminate loop operation. 762 PHINode *PN = nullptr; 763 Value *Start = nullptr, *Step = nullptr; 764 if (matchSimpleRecurrence(&I, PN, Start, Step) && I.hasNoNaNs() && 765 I.hasNoSignedZeros() && match(Start, m_Zero())) 766 return replaceInstUsesWith(I, Start); 767 768 return nullptr; 769 } 770 771 /// Fold a divide or remainder with a select instruction divisor when one of the 772 /// select operands is zero. In that case, we can use the other select operand 773 /// because div/rem by zero is undefined. 774 bool InstCombinerImpl::simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I) { 775 SelectInst *SI = dyn_cast<SelectInst>(I.getOperand(1)); 776 if (!SI) 777 return false; 778 779 int NonNullOperand; 780 if (match(SI->getTrueValue(), m_Zero())) 781 // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y 782 NonNullOperand = 2; 783 else if (match(SI->getFalseValue(), m_Zero())) 784 // div/rem X, (Cond ? Y : 0) -> div/rem X, Y 785 NonNullOperand = 1; 786 else 787 return false; 788 789 // Change the div/rem to use 'Y' instead of the select. 790 replaceOperand(I, 1, SI->getOperand(NonNullOperand)); 791 792 // Okay, we know we replace the operand of the div/rem with 'Y' with no 793 // problem. However, the select, or the condition of the select may have 794 // multiple uses. Based on our knowledge that the operand must be non-zero, 795 // propagate the known value for the select into other uses of it, and 796 // propagate a known value of the condition into its other users. 797 798 // If the select and condition only have a single use, don't bother with this, 799 // early exit. 800 Value *SelectCond = SI->getCondition(); 801 if (SI->use_empty() && SelectCond->hasOneUse()) 802 return true; 803 804 // Scan the current block backward, looking for other uses of SI. 805 BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin(); 806 Type *CondTy = SelectCond->getType(); 807 while (BBI != BBFront) { 808 --BBI; 809 // If we found an instruction that we can't assume will return, so 810 // information from below it cannot be propagated above it. 811 if (!isGuaranteedToTransferExecutionToSuccessor(&*BBI)) 812 break; 813 814 // Replace uses of the select or its condition with the known values. 815 for (Use &Op : BBI->operands()) { 816 if (Op == SI) { 817 replaceUse(Op, SI->getOperand(NonNullOperand)); 818 Worklist.push(&*BBI); 819 } else if (Op == SelectCond) { 820 replaceUse(Op, NonNullOperand == 1 ? ConstantInt::getTrue(CondTy) 821 : ConstantInt::getFalse(CondTy)); 822 Worklist.push(&*BBI); 823 } 824 } 825 826 // If we past the instruction, quit looking for it. 827 if (&*BBI == SI) 828 SI = nullptr; 829 if (&*BBI == SelectCond) 830 SelectCond = nullptr; 831 832 // If we ran out of things to eliminate, break out of the loop. 833 if (!SelectCond && !SI) 834 break; 835 836 } 837 return true; 838 } 839 840 /// True if the multiply can not be expressed in an int this size. 841 static bool multiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product, 842 bool IsSigned) { 843 bool Overflow; 844 Product = IsSigned ? C1.smul_ov(C2, Overflow) : C1.umul_ov(C2, Overflow); 845 return Overflow; 846 } 847 848 /// True if C1 is a multiple of C2. Quotient contains C1/C2. 849 static bool isMultiple(const APInt &C1, const APInt &C2, APInt &Quotient, 850 bool IsSigned) { 851 assert(C1.getBitWidth() == C2.getBitWidth() && "Constant widths not equal"); 852 853 // Bail if we will divide by zero. 854 if (C2.isZero()) 855 return false; 856 857 // Bail if we would divide INT_MIN by -1. 858 if (IsSigned && C1.isMinSignedValue() && C2.isAllOnes()) 859 return false; 860 861 APInt Remainder(C1.getBitWidth(), /*val=*/0ULL, IsSigned); 862 if (IsSigned) 863 APInt::sdivrem(C1, C2, Quotient, Remainder); 864 else 865 APInt::udivrem(C1, C2, Quotient, Remainder); 866 867 return Remainder.isMinValue(); 868 } 869 870 static Instruction *foldIDivShl(BinaryOperator &I, 871 InstCombiner::BuilderTy &Builder) { 872 assert((I.getOpcode() == Instruction::SDiv || 873 I.getOpcode() == Instruction::UDiv) && 874 "Expected integer divide"); 875 876 bool IsSigned = I.getOpcode() == Instruction::SDiv; 877 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 878 Type *Ty = I.getType(); 879 880 Instruction *Ret = nullptr; 881 Value *X, *Y, *Z; 882 883 // With appropriate no-wrap constraints, remove a common factor in the 884 // dividend and divisor that is disguised as a left-shifted value. 885 if (match(Op1, m_Shl(m_Value(X), m_Value(Z))) && 886 match(Op0, m_c_Mul(m_Specific(X), m_Value(Y)))) { 887 // Both operands must have the matching no-wrap for this kind of division. 888 auto *Mul = cast<OverflowingBinaryOperator>(Op0); 889 auto *Shl = cast<OverflowingBinaryOperator>(Op1); 890 bool HasNUW = Mul->hasNoUnsignedWrap() && Shl->hasNoUnsignedWrap(); 891 bool HasNSW = Mul->hasNoSignedWrap() && Shl->hasNoSignedWrap(); 892 893 // (X * Y) u/ (X << Z) --> Y u>> Z 894 if (!IsSigned && HasNUW) 895 Ret = BinaryOperator::CreateLShr(Y, Z); 896 897 // (X * Y) s/ (X << Z) --> Y s/ (1 << Z) 898 if (IsSigned && HasNSW && (Op0->hasOneUse() || Op1->hasOneUse())) { 899 Value *Shl = Builder.CreateShl(ConstantInt::get(Ty, 1), Z); 900 Ret = BinaryOperator::CreateSDiv(Y, Shl); 901 } 902 } 903 904 // With appropriate no-wrap constraints, remove a common factor in the 905 // dividend and divisor that is disguised as a left-shift amount. 906 if (match(Op0, m_Shl(m_Value(X), m_Value(Z))) && 907 match(Op1, m_Shl(m_Value(Y), m_Specific(Z)))) { 908 auto *Shl0 = cast<OverflowingBinaryOperator>(Op0); 909 auto *Shl1 = cast<OverflowingBinaryOperator>(Op1); 910 911 // For unsigned div, we need 'nuw' on both shifts or 912 // 'nsw' on both shifts + 'nuw' on the dividend. 913 // (X << Z) / (Y << Z) --> X / Y 914 if (!IsSigned && 915 ((Shl0->hasNoUnsignedWrap() && Shl1->hasNoUnsignedWrap()) || 916 (Shl0->hasNoUnsignedWrap() && Shl0->hasNoSignedWrap() && 917 Shl1->hasNoSignedWrap()))) 918 Ret = BinaryOperator::CreateUDiv(X, Y); 919 920 // For signed div, we need 'nsw' on both shifts + 'nuw' on the divisor. 921 // (X << Z) / (Y << Z) --> X / Y 922 if (IsSigned && Shl0->hasNoSignedWrap() && Shl1->hasNoSignedWrap() && 923 Shl1->hasNoUnsignedWrap()) 924 Ret = BinaryOperator::CreateSDiv(X, Y); 925 } 926 927 if (!Ret) 928 return nullptr; 929 930 Ret->setIsExact(I.isExact()); 931 return Ret; 932 } 933 934 /// This function implements the transforms common to both integer division 935 /// instructions (udiv and sdiv). It is called by the visitors to those integer 936 /// division instructions. 937 /// Common integer divide transforms 938 Instruction *InstCombinerImpl::commonIDivTransforms(BinaryOperator &I) { 939 if (Instruction *Phi = foldBinopWithPhiOperands(I)) 940 return Phi; 941 942 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 943 bool IsSigned = I.getOpcode() == Instruction::SDiv; 944 Type *Ty = I.getType(); 945 946 // The RHS is known non-zero. 947 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) 948 return replaceOperand(I, 1, V); 949 950 // Handle cases involving: [su]div X, (select Cond, Y, Z) 951 // This does not apply for fdiv. 952 if (simplifyDivRemOfSelectWithZeroOp(I)) 953 return &I; 954 955 // If the divisor is a select-of-constants, try to constant fold all div ops: 956 // C / (select Cond, TrueC, FalseC) --> select Cond, (C / TrueC), (C / FalseC) 957 // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds. 958 if (match(Op0, m_ImmConstant()) && 959 match(Op1, m_Select(m_Value(), m_ImmConstant(), m_ImmConstant()))) { 960 if (Instruction *R = FoldOpIntoSelect(I, cast<SelectInst>(Op1), 961 /*FoldWithMultiUse*/ true)) 962 return R; 963 } 964 965 const APInt *C2; 966 if (match(Op1, m_APInt(C2))) { 967 Value *X; 968 const APInt *C1; 969 970 // (X / C1) / C2 -> X / (C1*C2) 971 if ((IsSigned && match(Op0, m_SDiv(m_Value(X), m_APInt(C1)))) || 972 (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_APInt(C1))))) { 973 APInt Product(C1->getBitWidth(), /*val=*/0ULL, IsSigned); 974 if (!multiplyOverflows(*C1, *C2, Product, IsSigned)) 975 return BinaryOperator::Create(I.getOpcode(), X, 976 ConstantInt::get(Ty, Product)); 977 } 978 979 if ((IsSigned && match(Op0, m_NSWMul(m_Value(X), m_APInt(C1)))) || 980 (!IsSigned && match(Op0, m_NUWMul(m_Value(X), m_APInt(C1))))) { 981 APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned); 982 983 // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1. 984 if (isMultiple(*C2, *C1, Quotient, IsSigned)) { 985 auto *NewDiv = BinaryOperator::Create(I.getOpcode(), X, 986 ConstantInt::get(Ty, Quotient)); 987 NewDiv->setIsExact(I.isExact()); 988 return NewDiv; 989 } 990 991 // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2. 992 if (isMultiple(*C1, *C2, Quotient, IsSigned)) { 993 auto *Mul = BinaryOperator::Create(Instruction::Mul, X, 994 ConstantInt::get(Ty, Quotient)); 995 auto *OBO = cast<OverflowingBinaryOperator>(Op0); 996 Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap()); 997 Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap()); 998 return Mul; 999 } 1000 } 1001 1002 if ((IsSigned && match(Op0, m_NSWShl(m_Value(X), m_APInt(C1))) && 1003 C1->ult(C1->getBitWidth() - 1)) || 1004 (!IsSigned && match(Op0, m_NUWShl(m_Value(X), m_APInt(C1))) && 1005 C1->ult(C1->getBitWidth()))) { 1006 APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned); 1007 APInt C1Shifted = APInt::getOneBitSet( 1008 C1->getBitWidth(), static_cast<unsigned>(C1->getZExtValue())); 1009 1010 // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of 1 << C1. 1011 if (isMultiple(*C2, C1Shifted, Quotient, IsSigned)) { 1012 auto *BO = BinaryOperator::Create(I.getOpcode(), X, 1013 ConstantInt::get(Ty, Quotient)); 1014 BO->setIsExact(I.isExact()); 1015 return BO; 1016 } 1017 1018 // (X << C1) / C2 -> X * ((1 << C1) / C2) if 1 << C1 is a multiple of C2. 1019 if (isMultiple(C1Shifted, *C2, Quotient, IsSigned)) { 1020 auto *Mul = BinaryOperator::Create(Instruction::Mul, X, 1021 ConstantInt::get(Ty, Quotient)); 1022 auto *OBO = cast<OverflowingBinaryOperator>(Op0); 1023 Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap()); 1024 Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap()); 1025 return Mul; 1026 } 1027 } 1028 1029 if (!C2->isZero()) // avoid X udiv 0 1030 if (Instruction *FoldedDiv = foldBinOpIntoSelectOrPhi(I)) 1031 return FoldedDiv; 1032 } 1033 1034 if (match(Op0, m_One())) { 1035 assert(!Ty->isIntOrIntVectorTy(1) && "i1 divide not removed?"); 1036 if (IsSigned) { 1037 // 1 / 0 --> undef ; 1 / 1 --> 1 ; 1 / -1 --> -1 ; 1 / anything else --> 0 1038 // (Op1 + 1) u< 3 ? Op1 : 0 1039 // Op1 must be frozen because we are increasing its number of uses. 1040 Value *F1 = Builder.CreateFreeze(Op1, Op1->getName() + ".fr"); 1041 Value *Inc = Builder.CreateAdd(F1, Op0); 1042 Value *Cmp = Builder.CreateICmpULT(Inc, ConstantInt::get(Ty, 3)); 1043 return SelectInst::Create(Cmp, F1, ConstantInt::get(Ty, 0)); 1044 } else { 1045 // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the 1046 // result is one, otherwise it's zero. 1047 return new ZExtInst(Builder.CreateICmpEQ(Op1, Op0), Ty); 1048 } 1049 } 1050 1051 // See if we can fold away this div instruction. 1052 if (SimplifyDemandedInstructionBits(I)) 1053 return &I; 1054 1055 // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y 1056 Value *X, *Z; 1057 if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) // (X - Z) / Y; Y = Op1 1058 if ((IsSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) || 1059 (!IsSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1))))) 1060 return BinaryOperator::Create(I.getOpcode(), X, Op1); 1061 1062 // (X << Y) / X -> 1 << Y 1063 Value *Y; 1064 if (IsSigned && match(Op0, m_NSWShl(m_Specific(Op1), m_Value(Y)))) 1065 return BinaryOperator::CreateNSWShl(ConstantInt::get(Ty, 1), Y); 1066 if (!IsSigned && match(Op0, m_NUWShl(m_Specific(Op1), m_Value(Y)))) 1067 return BinaryOperator::CreateNUWShl(ConstantInt::get(Ty, 1), Y); 1068 1069 // X / (X * Y) -> 1 / Y if the multiplication does not overflow. 1070 if (match(Op1, m_c_Mul(m_Specific(Op0), m_Value(Y)))) { 1071 bool HasNSW = cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap(); 1072 bool HasNUW = cast<OverflowingBinaryOperator>(Op1)->hasNoUnsignedWrap(); 1073 if ((IsSigned && HasNSW) || (!IsSigned && HasNUW)) { 1074 replaceOperand(I, 0, ConstantInt::get(Ty, 1)); 1075 replaceOperand(I, 1, Y); 1076 return &I; 1077 } 1078 } 1079 1080 // (X << Z) / (X * Y) -> (1 << Z) / Y 1081 // TODO: Handle sdiv. 1082 if (!IsSigned && Op1->hasOneUse() && 1083 match(Op0, m_NUWShl(m_Value(X), m_Value(Z))) && 1084 match(Op1, m_c_Mul(m_Specific(X), m_Value(Y)))) 1085 if (cast<OverflowingBinaryOperator>(Op1)->hasNoUnsignedWrap()) { 1086 Instruction *NewDiv = BinaryOperator::CreateUDiv( 1087 Builder.CreateShl(ConstantInt::get(Ty, 1), Z, "", /*NUW*/ true), Y); 1088 NewDiv->setIsExact(I.isExact()); 1089 return NewDiv; 1090 } 1091 1092 if (Instruction *R = foldIDivShl(I, Builder)) 1093 return R; 1094 1095 // With the appropriate no-wrap constraint, remove a multiply by the divisor 1096 // after peeking through another divide: 1097 // ((Op1 * X) / Y) / Op1 --> X / Y 1098 if (match(Op0, m_BinOp(I.getOpcode(), m_c_Mul(m_Specific(Op1), m_Value(X)), 1099 m_Value(Y)))) { 1100 auto *InnerDiv = cast<PossiblyExactOperator>(Op0); 1101 auto *Mul = cast<OverflowingBinaryOperator>(InnerDiv->getOperand(0)); 1102 Instruction *NewDiv = nullptr; 1103 if (!IsSigned && Mul->hasNoUnsignedWrap()) 1104 NewDiv = BinaryOperator::CreateUDiv(X, Y); 1105 else if (IsSigned && Mul->hasNoSignedWrap()) 1106 NewDiv = BinaryOperator::CreateSDiv(X, Y); 1107 1108 // Exact propagates only if both of the original divides are exact. 1109 if (NewDiv) { 1110 NewDiv->setIsExact(I.isExact() && InnerDiv->isExact()); 1111 return NewDiv; 1112 } 1113 } 1114 1115 return nullptr; 1116 } 1117 1118 static const unsigned MaxDepth = 6; 1119 1120 // Take the exact integer log2 of the value. If DoFold is true, create the 1121 // actual instructions, otherwise return a non-null dummy value. Return nullptr 1122 // on failure. 1123 static Value *takeLog2(IRBuilderBase &Builder, Value *Op, unsigned Depth, 1124 bool AssumeNonZero, bool DoFold) { 1125 auto IfFold = [DoFold](function_ref<Value *()> Fn) { 1126 if (!DoFold) 1127 return reinterpret_cast<Value *>(-1); 1128 return Fn(); 1129 }; 1130 1131 // FIXME: assert that Op1 isn't/doesn't contain undef. 1132 1133 // log2(2^C) -> C 1134 if (match(Op, m_Power2())) 1135 return IfFold([&]() { 1136 Constant *C = ConstantExpr::getExactLogBase2(cast<Constant>(Op)); 1137 if (!C) 1138 llvm_unreachable("Failed to constant fold udiv -> logbase2"); 1139 return C; 1140 }); 1141 1142 // The remaining tests are all recursive, so bail out if we hit the limit. 1143 if (Depth++ == MaxDepth) 1144 return nullptr; 1145 1146 // log2(zext X) -> zext log2(X) 1147 // FIXME: Require one use? 1148 Value *X, *Y; 1149 if (match(Op, m_ZExt(m_Value(X)))) 1150 if (Value *LogX = takeLog2(Builder, X, Depth, AssumeNonZero, DoFold)) 1151 return IfFold([&]() { return Builder.CreateZExt(LogX, Op->getType()); }); 1152 1153 // log2(X << Y) -> log2(X) + Y 1154 // FIXME: Require one use unless X is 1? 1155 if (match(Op, m_Shl(m_Value(X), m_Value(Y)))) { 1156 auto *BO = cast<OverflowingBinaryOperator>(Op); 1157 // nuw will be set if the `shl` is trivially non-zero. 1158 if (AssumeNonZero || BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap()) 1159 if (Value *LogX = takeLog2(Builder, X, Depth, AssumeNonZero, DoFold)) 1160 return IfFold([&]() { return Builder.CreateAdd(LogX, Y); }); 1161 } 1162 1163 // log2(Cond ? X : Y) -> Cond ? log2(X) : log2(Y) 1164 // FIXME: missed optimization: if one of the hands of select is/contains 1165 // undef, just directly pick the other one. 1166 // FIXME: can both hands contain undef? 1167 // FIXME: Require one use? 1168 if (SelectInst *SI = dyn_cast<SelectInst>(Op)) 1169 if (Value *LogX = takeLog2(Builder, SI->getOperand(1), Depth, 1170 AssumeNonZero, DoFold)) 1171 if (Value *LogY = takeLog2(Builder, SI->getOperand(2), Depth, 1172 AssumeNonZero, DoFold)) 1173 return IfFold([&]() { 1174 return Builder.CreateSelect(SI->getOperand(0), LogX, LogY); 1175 }); 1176 1177 // log2(umin(X, Y)) -> umin(log2(X), log2(Y)) 1178 // log2(umax(X, Y)) -> umax(log2(X), log2(Y)) 1179 auto *MinMax = dyn_cast<MinMaxIntrinsic>(Op); 1180 if (MinMax && MinMax->hasOneUse() && !MinMax->isSigned()) { 1181 // Use AssumeNonZero as false here. Otherwise we can hit case where 1182 // log2(umax(X, Y)) != umax(log2(X), log2(Y)) (because overflow). 1183 if (Value *LogX = takeLog2(Builder, MinMax->getLHS(), Depth, 1184 /*AssumeNonZero*/ false, DoFold)) 1185 if (Value *LogY = takeLog2(Builder, MinMax->getRHS(), Depth, 1186 /*AssumeNonZero*/ false, DoFold)) 1187 return IfFold([&]() { 1188 return Builder.CreateBinaryIntrinsic(MinMax->getIntrinsicID(), LogX, 1189 LogY); 1190 }); 1191 } 1192 1193 return nullptr; 1194 } 1195 1196 /// If we have zero-extended operands of an unsigned div or rem, we may be able 1197 /// to narrow the operation (sink the zext below the math). 1198 static Instruction *narrowUDivURem(BinaryOperator &I, 1199 InstCombiner::BuilderTy &Builder) { 1200 Instruction::BinaryOps Opcode = I.getOpcode(); 1201 Value *N = I.getOperand(0); 1202 Value *D = I.getOperand(1); 1203 Type *Ty = I.getType(); 1204 Value *X, *Y; 1205 if (match(N, m_ZExt(m_Value(X))) && match(D, m_ZExt(m_Value(Y))) && 1206 X->getType() == Y->getType() && (N->hasOneUse() || D->hasOneUse())) { 1207 // udiv (zext X), (zext Y) --> zext (udiv X, Y) 1208 // urem (zext X), (zext Y) --> zext (urem X, Y) 1209 Value *NarrowOp = Builder.CreateBinOp(Opcode, X, Y); 1210 return new ZExtInst(NarrowOp, Ty); 1211 } 1212 1213 Constant *C; 1214 if (isa<Instruction>(N) && match(N, m_OneUse(m_ZExt(m_Value(X)))) && 1215 match(D, m_Constant(C))) { 1216 // If the constant is the same in the smaller type, use the narrow version. 1217 Constant *TruncC = ConstantExpr::getTrunc(C, X->getType()); 1218 if (ConstantExpr::getZExt(TruncC, Ty) != C) 1219 return nullptr; 1220 1221 // udiv (zext X), C --> zext (udiv X, C') 1222 // urem (zext X), C --> zext (urem X, C') 1223 return new ZExtInst(Builder.CreateBinOp(Opcode, X, TruncC), Ty); 1224 } 1225 if (isa<Instruction>(D) && match(D, m_OneUse(m_ZExt(m_Value(X)))) && 1226 match(N, m_Constant(C))) { 1227 // If the constant is the same in the smaller type, use the narrow version. 1228 Constant *TruncC = ConstantExpr::getTrunc(C, X->getType()); 1229 if (ConstantExpr::getZExt(TruncC, Ty) != C) 1230 return nullptr; 1231 1232 // udiv C, (zext X) --> zext (udiv C', X) 1233 // urem C, (zext X) --> zext (urem C', X) 1234 return new ZExtInst(Builder.CreateBinOp(Opcode, TruncC, X), Ty); 1235 } 1236 1237 return nullptr; 1238 } 1239 1240 Instruction *InstCombinerImpl::visitUDiv(BinaryOperator &I) { 1241 if (Value *V = simplifyUDivInst(I.getOperand(0), I.getOperand(1), I.isExact(), 1242 SQ.getWithInstruction(&I))) 1243 return replaceInstUsesWith(I, V); 1244 1245 if (Instruction *X = foldVectorBinop(I)) 1246 return X; 1247 1248 // Handle the integer div common cases 1249 if (Instruction *Common = commonIDivTransforms(I)) 1250 return Common; 1251 1252 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1253 Value *X; 1254 const APInt *C1, *C2; 1255 if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && match(Op1, m_APInt(C2))) { 1256 // (X lshr C1) udiv C2 --> X udiv (C2 << C1) 1257 bool Overflow; 1258 APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow); 1259 if (!Overflow) { 1260 bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value())); 1261 BinaryOperator *BO = BinaryOperator::CreateUDiv( 1262 X, ConstantInt::get(X->getType(), C2ShlC1)); 1263 if (IsExact) 1264 BO->setIsExact(); 1265 return BO; 1266 } 1267 } 1268 1269 // Op0 / C where C is large (negative) --> zext (Op0 >= C) 1270 // TODO: Could use isKnownNegative() to handle non-constant values. 1271 Type *Ty = I.getType(); 1272 if (match(Op1, m_Negative())) { 1273 Value *Cmp = Builder.CreateICmpUGE(Op0, Op1); 1274 return CastInst::CreateZExtOrBitCast(Cmp, Ty); 1275 } 1276 // Op0 / (sext i1 X) --> zext (Op0 == -1) (if X is 0, the div is undefined) 1277 if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) { 1278 Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty)); 1279 return CastInst::CreateZExtOrBitCast(Cmp, Ty); 1280 } 1281 1282 if (Instruction *NarrowDiv = narrowUDivURem(I, Builder)) 1283 return NarrowDiv; 1284 1285 // If the udiv operands are non-overflowing multiplies with a common operand, 1286 // then eliminate the common factor: 1287 // (A * B) / (A * X) --> B / X (and commuted variants) 1288 // TODO: The code would be reduced if we had m_c_NUWMul pattern matching. 1289 // TODO: If -reassociation handled this generally, we could remove this. 1290 Value *A, *B; 1291 if (match(Op0, m_NUWMul(m_Value(A), m_Value(B)))) { 1292 if (match(Op1, m_NUWMul(m_Specific(A), m_Value(X))) || 1293 match(Op1, m_NUWMul(m_Value(X), m_Specific(A)))) 1294 return BinaryOperator::CreateUDiv(B, X); 1295 if (match(Op1, m_NUWMul(m_Specific(B), m_Value(X))) || 1296 match(Op1, m_NUWMul(m_Value(X), m_Specific(B)))) 1297 return BinaryOperator::CreateUDiv(A, X); 1298 } 1299 1300 // Look through a right-shift to find the common factor: 1301 // ((Op1 *nuw A) >> B) / Op1 --> A >> B 1302 if (match(Op0, m_LShr(m_NUWMul(m_Specific(Op1), m_Value(A)), m_Value(B))) || 1303 match(Op0, m_LShr(m_NUWMul(m_Value(A), m_Specific(Op1)), m_Value(B)))) { 1304 Instruction *Lshr = BinaryOperator::CreateLShr(A, B); 1305 if (I.isExact() && cast<PossiblyExactOperator>(Op0)->isExact()) 1306 Lshr->setIsExact(); 1307 return Lshr; 1308 } 1309 1310 // Op1 udiv Op2 -> Op1 lshr log2(Op2), if log2() folds away. 1311 if (takeLog2(Builder, Op1, /*Depth*/ 0, /*AssumeNonZero*/ true, 1312 /*DoFold*/ false)) { 1313 Value *Res = takeLog2(Builder, Op1, /*Depth*/ 0, 1314 /*AssumeNonZero*/ true, /*DoFold*/ true); 1315 return replaceInstUsesWith( 1316 I, Builder.CreateLShr(Op0, Res, I.getName(), I.isExact())); 1317 } 1318 1319 return nullptr; 1320 } 1321 1322 Instruction *InstCombinerImpl::visitSDiv(BinaryOperator &I) { 1323 if (Value *V = simplifySDivInst(I.getOperand(0), I.getOperand(1), I.isExact(), 1324 SQ.getWithInstruction(&I))) 1325 return replaceInstUsesWith(I, V); 1326 1327 if (Instruction *X = foldVectorBinop(I)) 1328 return X; 1329 1330 // Handle the integer div common cases 1331 if (Instruction *Common = commonIDivTransforms(I)) 1332 return Common; 1333 1334 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1335 Type *Ty = I.getType(); 1336 Value *X; 1337 // sdiv Op0, -1 --> -Op0 1338 // sdiv Op0, (sext i1 X) --> -Op0 (because if X is 0, the op is undefined) 1339 if (match(Op1, m_AllOnes()) || 1340 (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))) 1341 return BinaryOperator::CreateNeg(Op0); 1342 1343 // X / INT_MIN --> X == INT_MIN 1344 if (match(Op1, m_SignMask())) 1345 return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), Ty); 1346 1347 if (I.isExact()) { 1348 // sdiv exact X, 1<<C --> ashr exact X, C iff 1<<C is non-negative 1349 if (match(Op1, m_Power2()) && match(Op1, m_NonNegative())) { 1350 Constant *C = ConstantExpr::getExactLogBase2(cast<Constant>(Op1)); 1351 return BinaryOperator::CreateExactAShr(Op0, C); 1352 } 1353 1354 // sdiv exact X, (1<<ShAmt) --> ashr exact X, ShAmt (if shl is non-negative) 1355 Value *ShAmt; 1356 if (match(Op1, m_NSWShl(m_One(), m_Value(ShAmt)))) 1357 return BinaryOperator::CreateExactAShr(Op0, ShAmt); 1358 1359 // sdiv exact X, -1<<C --> -(ashr exact X, C) 1360 if (match(Op1, m_NegatedPower2())) { 1361 Constant *NegPow2C = ConstantExpr::getNeg(cast<Constant>(Op1)); 1362 Constant *C = ConstantExpr::getExactLogBase2(NegPow2C); 1363 Value *Ashr = Builder.CreateAShr(Op0, C, I.getName() + ".neg", true); 1364 return BinaryOperator::CreateNeg(Ashr); 1365 } 1366 } 1367 1368 const APInt *Op1C; 1369 if (match(Op1, m_APInt(Op1C))) { 1370 // If the dividend is sign-extended and the constant divisor is small enough 1371 // to fit in the source type, shrink the division to the narrower type: 1372 // (sext X) sdiv C --> sext (X sdiv C) 1373 Value *Op0Src; 1374 if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) && 1375 Op0Src->getType()->getScalarSizeInBits() >= Op1C->getMinSignedBits()) { 1376 1377 // In the general case, we need to make sure that the dividend is not the 1378 // minimum signed value because dividing that by -1 is UB. But here, we 1379 // know that the -1 divisor case is already handled above. 1380 1381 Constant *NarrowDivisor = 1382 ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType()); 1383 Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor); 1384 return new SExtInst(NarrowOp, Ty); 1385 } 1386 1387 // -X / C --> X / -C (if the negation doesn't overflow). 1388 // TODO: This could be enhanced to handle arbitrary vector constants by 1389 // checking if all elements are not the min-signed-val. 1390 if (!Op1C->isMinSignedValue() && 1391 match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) { 1392 Constant *NegC = ConstantInt::get(Ty, -(*Op1C)); 1393 Instruction *BO = BinaryOperator::CreateSDiv(X, NegC); 1394 BO->setIsExact(I.isExact()); 1395 return BO; 1396 } 1397 } 1398 1399 // -X / Y --> -(X / Y) 1400 Value *Y; 1401 if (match(&I, m_SDiv(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y)))) 1402 return BinaryOperator::CreateNSWNeg( 1403 Builder.CreateSDiv(X, Y, I.getName(), I.isExact())); 1404 1405 // abs(X) / X --> X > -1 ? 1 : -1 1406 // X / abs(X) --> X > -1 ? 1 : -1 1407 if (match(&I, m_c_BinOp( 1408 m_OneUse(m_Intrinsic<Intrinsic::abs>(m_Value(X), m_One())), 1409 m_Deferred(X)))) { 1410 Value *Cond = Builder.CreateIsNotNeg(X); 1411 return SelectInst::Create(Cond, ConstantInt::get(Ty, 1), 1412 ConstantInt::getAllOnesValue(Ty)); 1413 } 1414 1415 KnownBits KnownDividend = computeKnownBits(Op0, 0, &I); 1416 if (!I.isExact() && 1417 (match(Op1, m_Power2(Op1C)) || match(Op1, m_NegatedPower2(Op1C))) && 1418 KnownDividend.countMinTrailingZeros() >= Op1C->countTrailingZeros()) { 1419 I.setIsExact(); 1420 return &I; 1421 } 1422 1423 if (KnownDividend.isNonNegative()) { 1424 // If both operands are unsigned, turn this into a udiv. 1425 if (isKnownNonNegative(Op1, DL, 0, &AC, &I, &DT)) { 1426 auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 1427 BO->setIsExact(I.isExact()); 1428 return BO; 1429 } 1430 1431 if (match(Op1, m_NegatedPower2())) { 1432 // X sdiv (-(1 << C)) -> -(X sdiv (1 << C)) -> 1433 // -> -(X udiv (1 << C)) -> -(X u>> C) 1434 Constant *CNegLog2 = ConstantExpr::getExactLogBase2( 1435 ConstantExpr::getNeg(cast<Constant>(Op1))); 1436 Value *Shr = Builder.CreateLShr(Op0, CNegLog2, I.getName(), I.isExact()); 1437 return BinaryOperator::CreateNeg(Shr); 1438 } 1439 1440 if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) { 1441 // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y) 1442 // Safe because the only negative value (1 << Y) can take on is 1443 // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have 1444 // the sign bit set. 1445 auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 1446 BO->setIsExact(I.isExact()); 1447 return BO; 1448 } 1449 } 1450 1451 return nullptr; 1452 } 1453 1454 /// Remove negation and try to convert division into multiplication. 1455 Instruction *InstCombinerImpl::foldFDivConstantDivisor(BinaryOperator &I) { 1456 Constant *C; 1457 if (!match(I.getOperand(1), m_Constant(C))) 1458 return nullptr; 1459 1460 // -X / C --> X / -C 1461 Value *X; 1462 const DataLayout &DL = I.getModule()->getDataLayout(); 1463 if (match(I.getOperand(0), m_FNeg(m_Value(X)))) 1464 if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL)) 1465 return BinaryOperator::CreateFDivFMF(X, NegC, &I); 1466 1467 // nnan X / +0.0 -> copysign(inf, X) 1468 if (I.hasNoNaNs() && match(I.getOperand(1), m_Zero())) { 1469 IRBuilder<> B(&I); 1470 // TODO: nnan nsz X / -0.0 -> copysign(inf, X) 1471 CallInst *CopySign = B.CreateIntrinsic( 1472 Intrinsic::copysign, {C->getType()}, 1473 {ConstantFP::getInfinity(I.getType()), I.getOperand(0)}, &I); 1474 CopySign->takeName(&I); 1475 return replaceInstUsesWith(I, CopySign); 1476 } 1477 1478 // If the constant divisor has an exact inverse, this is always safe. If not, 1479 // then we can still create a reciprocal if fast-math-flags allow it and the 1480 // constant is a regular number (not zero, infinite, or denormal). 1481 if (!(C->hasExactInverseFP() || (I.hasAllowReciprocal() && C->isNormalFP()))) 1482 return nullptr; 1483 1484 // Disallow denormal constants because we don't know what would happen 1485 // on all targets. 1486 // TODO: Use Intrinsic::canonicalize or let function attributes tell us that 1487 // denorms are flushed? 1488 auto *RecipC = ConstantFoldBinaryOpOperands( 1489 Instruction::FDiv, ConstantFP::get(I.getType(), 1.0), C, DL); 1490 if (!RecipC || !RecipC->isNormalFP()) 1491 return nullptr; 1492 1493 // X / C --> X * (1 / C) 1494 return BinaryOperator::CreateFMulFMF(I.getOperand(0), RecipC, &I); 1495 } 1496 1497 /// Remove negation and try to reassociate constant math. 1498 static Instruction *foldFDivConstantDividend(BinaryOperator &I) { 1499 Constant *C; 1500 if (!match(I.getOperand(0), m_Constant(C))) 1501 return nullptr; 1502 1503 // C / -X --> -C / X 1504 Value *X; 1505 const DataLayout &DL = I.getModule()->getDataLayout(); 1506 if (match(I.getOperand(1), m_FNeg(m_Value(X)))) 1507 if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL)) 1508 return BinaryOperator::CreateFDivFMF(NegC, X, &I); 1509 1510 if (!I.hasAllowReassoc() || !I.hasAllowReciprocal()) 1511 return nullptr; 1512 1513 // Try to reassociate C / X expressions where X includes another constant. 1514 Constant *C2, *NewC = nullptr; 1515 if (match(I.getOperand(1), m_FMul(m_Value(X), m_Constant(C2)))) { 1516 // C / (X * C2) --> (C / C2) / X 1517 NewC = ConstantFoldBinaryOpOperands(Instruction::FDiv, C, C2, DL); 1518 } else if (match(I.getOperand(1), m_FDiv(m_Value(X), m_Constant(C2)))) { 1519 // C / (X / C2) --> (C * C2) / X 1520 NewC = ConstantFoldBinaryOpOperands(Instruction::FMul, C, C2, DL); 1521 } 1522 // Disallow denormal constants because we don't know what would happen 1523 // on all targets. 1524 // TODO: Use Intrinsic::canonicalize or let function attributes tell us that 1525 // denorms are flushed? 1526 if (!NewC || !NewC->isNormalFP()) 1527 return nullptr; 1528 1529 return BinaryOperator::CreateFDivFMF(NewC, X, &I); 1530 } 1531 1532 /// Negate the exponent of pow/exp to fold division-by-pow() into multiply. 1533 static Instruction *foldFDivPowDivisor(BinaryOperator &I, 1534 InstCombiner::BuilderTy &Builder) { 1535 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1536 auto *II = dyn_cast<IntrinsicInst>(Op1); 1537 if (!II || !II->hasOneUse() || !I.hasAllowReassoc() || 1538 !I.hasAllowReciprocal()) 1539 return nullptr; 1540 1541 // Z / pow(X, Y) --> Z * pow(X, -Y) 1542 // Z / exp{2}(Y) --> Z * exp{2}(-Y) 1543 // In the general case, this creates an extra instruction, but fmul allows 1544 // for better canonicalization and optimization than fdiv. 1545 Intrinsic::ID IID = II->getIntrinsicID(); 1546 SmallVector<Value *> Args; 1547 switch (IID) { 1548 case Intrinsic::pow: 1549 Args.push_back(II->getArgOperand(0)); 1550 Args.push_back(Builder.CreateFNegFMF(II->getArgOperand(1), &I)); 1551 break; 1552 case Intrinsic::powi: { 1553 // Require 'ninf' assuming that makes powi(X, -INT_MIN) acceptable. 1554 // That is, X ** (huge negative number) is 0.0, ~1.0, or INF and so 1555 // dividing by that is INF, ~1.0, or 0.0. Code that uses powi allows 1556 // non-standard results, so this corner case should be acceptable if the 1557 // code rules out INF values. 1558 if (!I.hasNoInfs()) 1559 return nullptr; 1560 Args.push_back(II->getArgOperand(0)); 1561 Args.push_back(Builder.CreateNeg(II->getArgOperand(1))); 1562 Type *Tys[] = {I.getType(), II->getArgOperand(1)->getType()}; 1563 Value *Pow = Builder.CreateIntrinsic(IID, Tys, Args, &I); 1564 return BinaryOperator::CreateFMulFMF(Op0, Pow, &I); 1565 } 1566 case Intrinsic::exp: 1567 case Intrinsic::exp2: 1568 Args.push_back(Builder.CreateFNegFMF(II->getArgOperand(0), &I)); 1569 break; 1570 default: 1571 return nullptr; 1572 } 1573 Value *Pow = Builder.CreateIntrinsic(IID, I.getType(), Args, &I); 1574 return BinaryOperator::CreateFMulFMF(Op0, Pow, &I); 1575 } 1576 1577 Instruction *InstCombinerImpl::visitFDiv(BinaryOperator &I) { 1578 Module *M = I.getModule(); 1579 1580 if (Value *V = simplifyFDivInst(I.getOperand(0), I.getOperand(1), 1581 I.getFastMathFlags(), 1582 SQ.getWithInstruction(&I))) 1583 return replaceInstUsesWith(I, V); 1584 1585 if (Instruction *X = foldVectorBinop(I)) 1586 return X; 1587 1588 if (Instruction *Phi = foldBinopWithPhiOperands(I)) 1589 return Phi; 1590 1591 if (Instruction *R = foldFDivConstantDivisor(I)) 1592 return R; 1593 1594 if (Instruction *R = foldFDivConstantDividend(I)) 1595 return R; 1596 1597 if (Instruction *R = foldFPSignBitOps(I)) 1598 return R; 1599 1600 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1601 if (isa<Constant>(Op0)) 1602 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 1603 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1604 return R; 1605 1606 if (isa<Constant>(Op1)) 1607 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 1608 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1609 return R; 1610 1611 if (I.hasAllowReassoc() && I.hasAllowReciprocal()) { 1612 Value *X, *Y; 1613 if (match(Op0, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) && 1614 (!isa<Constant>(Y) || !isa<Constant>(Op1))) { 1615 // (X / Y) / Z => X / (Y * Z) 1616 Value *YZ = Builder.CreateFMulFMF(Y, Op1, &I); 1617 return BinaryOperator::CreateFDivFMF(X, YZ, &I); 1618 } 1619 if (match(Op1, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) && 1620 (!isa<Constant>(Y) || !isa<Constant>(Op0))) { 1621 // Z / (X / Y) => (Y * Z) / X 1622 Value *YZ = Builder.CreateFMulFMF(Y, Op0, &I); 1623 return BinaryOperator::CreateFDivFMF(YZ, X, &I); 1624 } 1625 // Z / (1.0 / Y) => (Y * Z) 1626 // 1627 // This is a special case of Z / (X / Y) => (Y * Z) / X, with X = 1.0. The 1628 // m_OneUse check is avoided because even in the case of the multiple uses 1629 // for 1.0/Y, the number of instructions remain the same and a division is 1630 // replaced by a multiplication. 1631 if (match(Op1, m_FDiv(m_SpecificFP(1.0), m_Value(Y)))) 1632 return BinaryOperator::CreateFMulFMF(Y, Op0, &I); 1633 } 1634 1635 if (I.hasAllowReassoc() && Op0->hasOneUse() && Op1->hasOneUse()) { 1636 // sin(X) / cos(X) -> tan(X) 1637 // cos(X) / sin(X) -> 1/tan(X) (cotangent) 1638 Value *X; 1639 bool IsTan = match(Op0, m_Intrinsic<Intrinsic::sin>(m_Value(X))) && 1640 match(Op1, m_Intrinsic<Intrinsic::cos>(m_Specific(X))); 1641 bool IsCot = 1642 !IsTan && match(Op0, m_Intrinsic<Intrinsic::cos>(m_Value(X))) && 1643 match(Op1, m_Intrinsic<Intrinsic::sin>(m_Specific(X))); 1644 1645 if ((IsTan || IsCot) && hasFloatFn(M, &TLI, I.getType(), LibFunc_tan, 1646 LibFunc_tanf, LibFunc_tanl)) { 1647 IRBuilder<> B(&I); 1648 IRBuilder<>::FastMathFlagGuard FMFGuard(B); 1649 B.setFastMathFlags(I.getFastMathFlags()); 1650 AttributeList Attrs = 1651 cast<CallBase>(Op0)->getCalledFunction()->getAttributes(); 1652 Value *Res = emitUnaryFloatFnCall(X, &TLI, LibFunc_tan, LibFunc_tanf, 1653 LibFunc_tanl, B, Attrs); 1654 if (IsCot) 1655 Res = B.CreateFDiv(ConstantFP::get(I.getType(), 1.0), Res); 1656 return replaceInstUsesWith(I, Res); 1657 } 1658 } 1659 1660 // X / (X * Y) --> 1.0 / Y 1661 // Reassociate to (X / X -> 1.0) is legal when NaNs are not allowed. 1662 // We can ignore the possibility that X is infinity because INF/INF is NaN. 1663 Value *X, *Y; 1664 if (I.hasNoNaNs() && I.hasAllowReassoc() && 1665 match(Op1, m_c_FMul(m_Specific(Op0), m_Value(Y)))) { 1666 replaceOperand(I, 0, ConstantFP::get(I.getType(), 1.0)); 1667 replaceOperand(I, 1, Y); 1668 return &I; 1669 } 1670 1671 // X / fabs(X) -> copysign(1.0, X) 1672 // fabs(X) / X -> copysign(1.0, X) 1673 if (I.hasNoNaNs() && I.hasNoInfs() && 1674 (match(&I, m_FDiv(m_Value(X), m_FAbs(m_Deferred(X)))) || 1675 match(&I, m_FDiv(m_FAbs(m_Value(X)), m_Deferred(X))))) { 1676 Value *V = Builder.CreateBinaryIntrinsic( 1677 Intrinsic::copysign, ConstantFP::get(I.getType(), 1.0), X, &I); 1678 return replaceInstUsesWith(I, V); 1679 } 1680 1681 if (Instruction *Mul = foldFDivPowDivisor(I, Builder)) 1682 return Mul; 1683 1684 // pow(X, Y) / X --> pow(X, Y-1) 1685 if (I.hasAllowReassoc() && 1686 match(Op0, m_OneUse(m_Intrinsic<Intrinsic::pow>(m_Specific(Op1), 1687 m_Value(Y))))) { 1688 Value *Y1 = 1689 Builder.CreateFAddFMF(Y, ConstantFP::get(I.getType(), -1.0), &I); 1690 Value *Pow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, Op1, Y1, &I); 1691 return replaceInstUsesWith(I, Pow); 1692 } 1693 1694 return nullptr; 1695 } 1696 1697 /// This function implements the transforms common to both integer remainder 1698 /// instructions (urem and srem). It is called by the visitors to those integer 1699 /// remainder instructions. 1700 /// Common integer remainder transforms 1701 Instruction *InstCombinerImpl::commonIRemTransforms(BinaryOperator &I) { 1702 if (Instruction *Phi = foldBinopWithPhiOperands(I)) 1703 return Phi; 1704 1705 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1706 1707 // The RHS is known non-zero. 1708 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) 1709 return replaceOperand(I, 1, V); 1710 1711 // Handle cases involving: rem X, (select Cond, Y, Z) 1712 if (simplifyDivRemOfSelectWithZeroOp(I)) 1713 return &I; 1714 1715 // If the divisor is a select-of-constants, try to constant fold all rem ops: 1716 // C % (select Cond, TrueC, FalseC) --> select Cond, (C % TrueC), (C % FalseC) 1717 // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds. 1718 if (match(Op0, m_ImmConstant()) && 1719 match(Op1, m_Select(m_Value(), m_ImmConstant(), m_ImmConstant()))) { 1720 if (Instruction *R = FoldOpIntoSelect(I, cast<SelectInst>(Op1), 1721 /*FoldWithMultiUse*/ true)) 1722 return R; 1723 } 1724 1725 if (isa<Constant>(Op1)) { 1726 if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) { 1727 if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) { 1728 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1729 return R; 1730 } else if (auto *PN = dyn_cast<PHINode>(Op0I)) { 1731 const APInt *Op1Int; 1732 if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() && 1733 (I.getOpcode() == Instruction::URem || 1734 !Op1Int->isMinSignedValue())) { 1735 // foldOpIntoPhi will speculate instructions to the end of the PHI's 1736 // predecessor blocks, so do this only if we know the srem or urem 1737 // will not fault. 1738 if (Instruction *NV = foldOpIntoPhi(I, PN)) 1739 return NV; 1740 } 1741 } 1742 1743 // See if we can fold away this rem instruction. 1744 if (SimplifyDemandedInstructionBits(I)) 1745 return &I; 1746 } 1747 } 1748 1749 return nullptr; 1750 } 1751 1752 Instruction *InstCombinerImpl::visitURem(BinaryOperator &I) { 1753 if (Value *V = simplifyURemInst(I.getOperand(0), I.getOperand(1), 1754 SQ.getWithInstruction(&I))) 1755 return replaceInstUsesWith(I, V); 1756 1757 if (Instruction *X = foldVectorBinop(I)) 1758 return X; 1759 1760 if (Instruction *common = commonIRemTransforms(I)) 1761 return common; 1762 1763 if (Instruction *NarrowRem = narrowUDivURem(I, Builder)) 1764 return NarrowRem; 1765 1766 // X urem Y -> X and Y-1, where Y is a power of 2, 1767 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1768 Type *Ty = I.getType(); 1769 if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) { 1770 // This may increase instruction count, we don't enforce that Y is a 1771 // constant. 1772 Constant *N1 = Constant::getAllOnesValue(Ty); 1773 Value *Add = Builder.CreateAdd(Op1, N1); 1774 return BinaryOperator::CreateAnd(Op0, Add); 1775 } 1776 1777 // 1 urem X -> zext(X != 1) 1778 if (match(Op0, m_One())) { 1779 Value *Cmp = Builder.CreateICmpNE(Op1, ConstantInt::get(Ty, 1)); 1780 return CastInst::CreateZExtOrBitCast(Cmp, Ty); 1781 } 1782 1783 // Op0 urem C -> Op0 < C ? Op0 : Op0 - C, where C >= signbit. 1784 // Op0 must be frozen because we are increasing its number of uses. 1785 if (match(Op1, m_Negative())) { 1786 Value *F0 = Builder.CreateFreeze(Op0, Op0->getName() + ".fr"); 1787 Value *Cmp = Builder.CreateICmpULT(F0, Op1); 1788 Value *Sub = Builder.CreateSub(F0, Op1); 1789 return SelectInst::Create(Cmp, F0, Sub); 1790 } 1791 1792 // If the divisor is a sext of a boolean, then the divisor must be max 1793 // unsigned value (-1). Therefore, the remainder is Op0 unless Op0 is also 1794 // max unsigned value. In that case, the remainder is 0: 1795 // urem Op0, (sext i1 X) --> (Op0 == -1) ? 0 : Op0 1796 Value *X; 1797 if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) { 1798 Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty)); 1799 return SelectInst::Create(Cmp, ConstantInt::getNullValue(Ty), Op0); 1800 } 1801 1802 return nullptr; 1803 } 1804 1805 Instruction *InstCombinerImpl::visitSRem(BinaryOperator &I) { 1806 if (Value *V = simplifySRemInst(I.getOperand(0), I.getOperand(1), 1807 SQ.getWithInstruction(&I))) 1808 return replaceInstUsesWith(I, V); 1809 1810 if (Instruction *X = foldVectorBinop(I)) 1811 return X; 1812 1813 // Handle the integer rem common cases 1814 if (Instruction *Common = commonIRemTransforms(I)) 1815 return Common; 1816 1817 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1818 { 1819 const APInt *Y; 1820 // X % -Y -> X % Y 1821 if (match(Op1, m_Negative(Y)) && !Y->isMinSignedValue()) 1822 return replaceOperand(I, 1, ConstantInt::get(I.getType(), -*Y)); 1823 } 1824 1825 // -X srem Y --> -(X srem Y) 1826 Value *X, *Y; 1827 if (match(&I, m_SRem(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y)))) 1828 return BinaryOperator::CreateNSWNeg(Builder.CreateSRem(X, Y)); 1829 1830 // If the sign bits of both operands are zero (i.e. we can prove they are 1831 // unsigned inputs), turn this into a urem. 1832 APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits())); 1833 if (MaskedValueIsZero(Op1, Mask, 0, &I) && 1834 MaskedValueIsZero(Op0, Mask, 0, &I)) { 1835 // X srem Y -> X urem Y, iff X and Y don't have sign bit set 1836 return BinaryOperator::CreateURem(Op0, Op1, I.getName()); 1837 } 1838 1839 // If it's a constant vector, flip any negative values positive. 1840 if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) { 1841 Constant *C = cast<Constant>(Op1); 1842 unsigned VWidth = cast<FixedVectorType>(C->getType())->getNumElements(); 1843 1844 bool hasNegative = false; 1845 bool hasMissing = false; 1846 for (unsigned i = 0; i != VWidth; ++i) { 1847 Constant *Elt = C->getAggregateElement(i); 1848 if (!Elt) { 1849 hasMissing = true; 1850 break; 1851 } 1852 1853 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt)) 1854 if (RHS->isNegative()) 1855 hasNegative = true; 1856 } 1857 1858 if (hasNegative && !hasMissing) { 1859 SmallVector<Constant *, 16> Elts(VWidth); 1860 for (unsigned i = 0; i != VWidth; ++i) { 1861 Elts[i] = C->getAggregateElement(i); // Handle undef, etc. 1862 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) { 1863 if (RHS->isNegative()) 1864 Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS)); 1865 } 1866 } 1867 1868 Constant *NewRHSV = ConstantVector::get(Elts); 1869 if (NewRHSV != C) // Don't loop on -MININT 1870 return replaceOperand(I, 1, NewRHSV); 1871 } 1872 } 1873 1874 return nullptr; 1875 } 1876 1877 Instruction *InstCombinerImpl::visitFRem(BinaryOperator &I) { 1878 if (Value *V = simplifyFRemInst(I.getOperand(0), I.getOperand(1), 1879 I.getFastMathFlags(), 1880 SQ.getWithInstruction(&I))) 1881 return replaceInstUsesWith(I, V); 1882 1883 if (Instruction *X = foldVectorBinop(I)) 1884 return X; 1885 1886 if (Instruction *Phi = foldBinopWithPhiOperands(I)) 1887 return Phi; 1888 1889 return nullptr; 1890 } 1891