InstCombineMulDivRem.cpp revision a9445e11c553855a6caacbbbf77a9b993ecc651e
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 "InstCombine.h" 16#include "llvm/IntrinsicInst.h" 17#include "llvm/Support/PatternMatch.h" 18using namespace llvm; 19using namespace PatternMatch; 20 21/// SubOne - Subtract one from a ConstantInt. 22static Constant *SubOne(ConstantInt *C) { 23 return ConstantInt::get(C->getContext(), C->getValue()-1); 24} 25 26/// MultiplyOverflows - True if the multiply can not be expressed in an int 27/// this size. 28static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) { 29 uint32_t W = C1->getBitWidth(); 30 APInt LHSExt = C1->getValue(), RHSExt = C2->getValue(); 31 if (sign) { 32 LHSExt.sext(W * 2); 33 RHSExt.sext(W * 2); 34 } else { 35 LHSExt.zext(W * 2); 36 RHSExt.zext(W * 2); 37 } 38 39 APInt MulExt = LHSExt * RHSExt; 40 41 if (!sign) 42 return MulExt.ugt(APInt::getLowBitsSet(W * 2, W)); 43 44 APInt Min = APInt::getSignedMinValue(W).sext(W * 2); 45 APInt Max = APInt::getSignedMaxValue(W).sext(W * 2); 46 return MulExt.slt(Min) || MulExt.sgt(Max); 47} 48 49Instruction *InstCombiner::visitMul(BinaryOperator &I) { 50 bool Changed = SimplifyCommutative(I); 51 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 52 53 if (isa<UndefValue>(Op1)) // undef * X -> 0 54 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 55 56 // Simplify mul instructions with a constant RHS. 57 if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 58 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1C)) { 59 60 // ((X << C1)*C2) == (X * (C2 << C1)) 61 if (BinaryOperator *SI = dyn_cast<BinaryOperator>(Op0)) 62 if (SI->getOpcode() == Instruction::Shl) 63 if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1))) 64 return BinaryOperator::CreateMul(SI->getOperand(0), 65 ConstantExpr::getShl(CI, ShOp)); 66 67 if (CI->isZero()) 68 return ReplaceInstUsesWith(I, Op1C); // X * 0 == 0 69 if (CI->equalsInt(1)) // X * 1 == X 70 return ReplaceInstUsesWith(I, Op0); 71 if (CI->isAllOnesValue()) // X * -1 == 0 - X 72 return BinaryOperator::CreateNeg(Op0, I.getName()); 73 74 const APInt& Val = cast<ConstantInt>(CI)->getValue(); 75 if (Val.isPowerOf2()) { // Replace X*(2^C) with X << C 76 return BinaryOperator::CreateShl(Op0, 77 ConstantInt::get(Op0->getType(), Val.logBase2())); 78 } 79 } else if (Op1C->getType()->isVectorTy()) { 80 if (Op1C->isNullValue()) 81 return ReplaceInstUsesWith(I, Op1C); 82 83 if (ConstantVector *Op1V = dyn_cast<ConstantVector>(Op1C)) { 84 if (Op1V->isAllOnesValue()) // X * -1 == 0 - X 85 return BinaryOperator::CreateNeg(Op0, I.getName()); 86 87 // As above, vector X*splat(1.0) -> X in all defined cases. 88 if (Constant *Splat = Op1V->getSplatValue()) { 89 if (ConstantInt *CI = dyn_cast<ConstantInt>(Splat)) 90 if (CI->equalsInt(1)) 91 return ReplaceInstUsesWith(I, Op0); 92 } 93 } 94 } 95 96 if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) 97 if (Op0I->getOpcode() == Instruction::Add && Op0I->hasOneUse() && 98 isa<ConstantInt>(Op0I->getOperand(1)) && isa<ConstantInt>(Op1C)) { 99 // Canonicalize (X+C1)*C2 -> X*C2+C1*C2. 100 Value *Add = Builder->CreateMul(Op0I->getOperand(0), Op1C, "tmp"); 101 Value *C1C2 = Builder->CreateMul(Op1C, Op0I->getOperand(1)); 102 return BinaryOperator::CreateAdd(Add, C1C2); 103 104 } 105 106 // Try to fold constant mul into select arguments. 107 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 108 if (Instruction *R = FoldOpIntoSelect(I, SI)) 109 return R; 110 111 if (isa<PHINode>(Op0)) 112 if (Instruction *NV = FoldOpIntoPhi(I)) 113 return NV; 114 } 115 116 if (Value *Op0v = dyn_castNegVal(Op0)) // -X * -Y = X*Y 117 if (Value *Op1v = dyn_castNegVal(Op1)) 118 return BinaryOperator::CreateMul(Op0v, Op1v); 119 120 // (X / Y) * Y = X - (X % Y) 121 // (X / Y) * -Y = (X % Y) - X 122 { 123 Value *Op1C = Op1; 124 BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0); 125 if (!BO || 126 (BO->getOpcode() != Instruction::UDiv && 127 BO->getOpcode() != Instruction::SDiv)) { 128 Op1C = Op0; 129 BO = dyn_cast<BinaryOperator>(Op1); 130 } 131 Value *Neg = dyn_castNegVal(Op1C); 132 if (BO && BO->hasOneUse() && 133 (BO->getOperand(1) == Op1C || BO->getOperand(1) == Neg) && 134 (BO->getOpcode() == Instruction::UDiv || 135 BO->getOpcode() == Instruction::SDiv)) { 136 Value *Op0BO = BO->getOperand(0), *Op1BO = BO->getOperand(1); 137 138 // If the division is exact, X % Y is zero. 139 if (SDivOperator *SDiv = dyn_cast<SDivOperator>(BO)) 140 if (SDiv->isExact()) { 141 if (Op1BO == Op1C) 142 return ReplaceInstUsesWith(I, Op0BO); 143 return BinaryOperator::CreateNeg(Op0BO); 144 } 145 146 Value *Rem; 147 if (BO->getOpcode() == Instruction::UDiv) 148 Rem = Builder->CreateURem(Op0BO, Op1BO); 149 else 150 Rem = Builder->CreateSRem(Op0BO, Op1BO); 151 Rem->takeName(BO); 152 153 if (Op1BO == Op1C) 154 return BinaryOperator::CreateSub(Op0BO, Rem); 155 return BinaryOperator::CreateSub(Rem, Op0BO); 156 } 157 } 158 159 /// i1 mul -> i1 and. 160 if (I.getType()->isIntegerTy(1)) 161 return BinaryOperator::CreateAnd(Op0, Op1); 162 163 // X*(1 << Y) --> X << Y 164 // (1 << Y)*X --> X << Y 165 { 166 Value *Y; 167 if (match(Op0, m_Shl(m_One(), m_Value(Y)))) 168 return BinaryOperator::CreateShl(Op1, Y); 169 if (match(Op1, m_Shl(m_One(), m_Value(Y)))) 170 return BinaryOperator::CreateShl(Op0, Y); 171 } 172 173 // If one of the operands of the multiply is a cast from a boolean value, then 174 // we know the bool is either zero or one, so this is a 'masking' multiply. 175 // X * Y (where Y is 0 or 1) -> X & (0-Y) 176 if (!I.getType()->isVectorTy()) { 177 // -2 is "-1 << 1" so it is all bits set except the low one. 178 APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true); 179 180 Value *BoolCast = 0, *OtherOp = 0; 181 if (MaskedValueIsZero(Op0, Negative2)) 182 BoolCast = Op0, OtherOp = Op1; 183 else if (MaskedValueIsZero(Op1, Negative2)) 184 BoolCast = Op1, OtherOp = Op0; 185 186 if (BoolCast) { 187 Value *V = Builder->CreateSub(Constant::getNullValue(I.getType()), 188 BoolCast, "tmp"); 189 return BinaryOperator::CreateAnd(V, OtherOp); 190 } 191 } 192 193 return Changed ? &I : 0; 194} 195 196Instruction *InstCombiner::visitFMul(BinaryOperator &I) { 197 bool Changed = SimplifyCommutative(I); 198 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 199 200 // Simplify mul instructions with a constant RHS... 201 if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 202 if (ConstantFP *Op1F = dyn_cast<ConstantFP>(Op1C)) { 203 // "In IEEE floating point, x*1 is not equivalent to x for nans. However, 204 // ANSI says we can drop signals, so we can do this anyway." (from GCC) 205 if (Op1F->isExactlyValue(1.0)) 206 return ReplaceInstUsesWith(I, Op0); // Eliminate 'fmul double %X, 1.0' 207 } else if (Op1C->getType()->isVectorTy()) { 208 if (ConstantVector *Op1V = dyn_cast<ConstantVector>(Op1C)) { 209 // As above, vector X*splat(1.0) -> X in all defined cases. 210 if (Constant *Splat = Op1V->getSplatValue()) { 211 if (ConstantFP *F = dyn_cast<ConstantFP>(Splat)) 212 if (F->isExactlyValue(1.0)) 213 return ReplaceInstUsesWith(I, Op0); 214 } 215 } 216 } 217 218 // Try to fold constant mul into select arguments. 219 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 220 if (Instruction *R = FoldOpIntoSelect(I, SI)) 221 return R; 222 223 if (isa<PHINode>(Op0)) 224 if (Instruction *NV = FoldOpIntoPhi(I)) 225 return NV; 226 } 227 228 if (Value *Op0v = dyn_castFNegVal(Op0)) // -X * -Y = X*Y 229 if (Value *Op1v = dyn_castFNegVal(Op1)) 230 return BinaryOperator::CreateFMul(Op0v, Op1v); 231 232 return Changed ? &I : 0; 233} 234 235/// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select 236/// instruction. 237bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) { 238 SelectInst *SI = cast<SelectInst>(I.getOperand(1)); 239 240 // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y 241 int NonNullOperand = -1; 242 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1))) 243 if (ST->isNullValue()) 244 NonNullOperand = 2; 245 // div/rem X, (Cond ? Y : 0) -> div/rem X, Y 246 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2))) 247 if (ST->isNullValue()) 248 NonNullOperand = 1; 249 250 if (NonNullOperand == -1) 251 return false; 252 253 Value *SelectCond = SI->getOperand(0); 254 255 // Change the div/rem to use 'Y' instead of the select. 256 I.setOperand(1, SI->getOperand(NonNullOperand)); 257 258 // Okay, we know we replace the operand of the div/rem with 'Y' with no 259 // problem. However, the select, or the condition of the select may have 260 // multiple uses. Based on our knowledge that the operand must be non-zero, 261 // propagate the known value for the select into other uses of it, and 262 // propagate a known value of the condition into its other users. 263 264 // If the select and condition only have a single use, don't bother with this, 265 // early exit. 266 if (SI->use_empty() && SelectCond->hasOneUse()) 267 return true; 268 269 // Scan the current block backward, looking for other uses of SI. 270 BasicBlock::iterator BBI = &I, BBFront = I.getParent()->begin(); 271 272 while (BBI != BBFront) { 273 --BBI; 274 // If we found a call to a function, we can't assume it will return, so 275 // information from below it cannot be propagated above it. 276 if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI)) 277 break; 278 279 // Replace uses of the select or its condition with the known values. 280 for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end(); 281 I != E; ++I) { 282 if (*I == SI) { 283 *I = SI->getOperand(NonNullOperand); 284 Worklist.Add(BBI); 285 } else if (*I == SelectCond) { 286 *I = NonNullOperand == 1 ? ConstantInt::getTrue(BBI->getContext()) : 287 ConstantInt::getFalse(BBI->getContext()); 288 Worklist.Add(BBI); 289 } 290 } 291 292 // If we past the instruction, quit looking for it. 293 if (&*BBI == SI) 294 SI = 0; 295 if (&*BBI == SelectCond) 296 SelectCond = 0; 297 298 // If we ran out of things to eliminate, break out of the loop. 299 if (SelectCond == 0 && SI == 0) 300 break; 301 302 } 303 return true; 304} 305 306 307/// This function implements the transforms on div instructions that work 308/// regardless of the kind of div instruction it is (udiv, sdiv, or fdiv). It is 309/// used by the visitors to those instructions. 310/// @brief Transforms common to all three div instructions 311Instruction *InstCombiner::commonDivTransforms(BinaryOperator &I) { 312 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 313 314 // undef / X -> 0 for integer. 315 // undef / X -> undef for FP (the undef could be a snan). 316 if (isa<UndefValue>(Op0)) { 317 if (Op0->getType()->isFPOrFPVectorTy()) 318 return ReplaceInstUsesWith(I, Op0); 319 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 320 } 321 322 // X / undef -> undef 323 if (isa<UndefValue>(Op1)) 324 return ReplaceInstUsesWith(I, Op1); 325 326 return 0; 327} 328 329/// This function implements the transforms common to both integer division 330/// instructions (udiv and sdiv). It is called by the visitors to those integer 331/// division instructions. 332/// @brief Common integer divide transforms 333Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { 334 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 335 336 // (sdiv X, X) --> 1 (udiv X, X) --> 1 337 if (Op0 == Op1) { 338 if (const VectorType *Ty = dyn_cast<VectorType>(I.getType())) { 339 Constant *CI = ConstantInt::get(Ty->getElementType(), 1); 340 std::vector<Constant*> Elts(Ty->getNumElements(), CI); 341 return ReplaceInstUsesWith(I, ConstantVector::get(Elts)); 342 } 343 344 Constant *CI = ConstantInt::get(I.getType(), 1); 345 return ReplaceInstUsesWith(I, CI); 346 } 347 348 if (Instruction *Common = commonDivTransforms(I)) 349 return Common; 350 351 // Handle cases involving: [su]div X, (select Cond, Y, Z) 352 // This does not apply for fdiv. 353 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 354 return &I; 355 356 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 357 // div X, 1 == X 358 if (RHS->equalsInt(1)) 359 return ReplaceInstUsesWith(I, Op0); 360 361 // (X / C1) / C2 -> X / (C1*C2) 362 if (Instruction *LHS = dyn_cast<Instruction>(Op0)) 363 if (Instruction::BinaryOps(LHS->getOpcode()) == I.getOpcode()) 364 if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) { 365 if (MultiplyOverflows(RHS, LHSRHS, 366 I.getOpcode()==Instruction::SDiv)) 367 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 368 else 369 return BinaryOperator::Create(I.getOpcode(), LHS->getOperand(0), 370 ConstantExpr::getMul(RHS, LHSRHS)); 371 } 372 373 if (!RHS->isZero()) { // avoid X udiv 0 374 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 375 if (Instruction *R = FoldOpIntoSelect(I, SI)) 376 return R; 377 if (isa<PHINode>(Op0)) 378 if (Instruction *NV = FoldOpIntoPhi(I)) 379 return NV; 380 } 381 } 382 383 // 0 / X == 0, we don't need to preserve faults! 384 if (ConstantInt *LHS = dyn_cast<ConstantInt>(Op0)) 385 if (LHS->equalsInt(0)) 386 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 387 388 // It can't be division by zero, hence it must be division by one. 389 if (I.getType()->isIntegerTy(1)) 390 return ReplaceInstUsesWith(I, Op0); 391 392 if (ConstantVector *Op1V = dyn_cast<ConstantVector>(Op1)) { 393 if (ConstantInt *X = cast_or_null<ConstantInt>(Op1V->getSplatValue())) 394 // div X, 1 == X 395 if (X->isOne()) 396 return ReplaceInstUsesWith(I, Op0); 397 } 398 399 return 0; 400} 401 402Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { 403 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 404 405 // Handle the integer div common cases 406 if (Instruction *Common = commonIDivTransforms(I)) 407 return Common; 408 409 if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) { 410 // X udiv 2^C -> X >> C 411 // Check to see if this is an unsigned division with an exact power of 2, 412 // if so, convert to a right shift. 413 if (C->getValue().isPowerOf2()) // 0 not included in isPowerOf2 414 return BinaryOperator::CreateLShr(Op0, 415 ConstantInt::get(Op0->getType(), C->getValue().logBase2())); 416 417 // X udiv C, where C >= signbit 418 if (C->getValue().isNegative()) { 419 Value *IC = Builder->CreateICmpULT( Op0, C); 420 return SelectInst::Create(IC, Constant::getNullValue(I.getType()), 421 ConstantInt::get(I.getType(), 1)); 422 } 423 } 424 425 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 426 if (BinaryOperator *RHSI = dyn_cast<BinaryOperator>(I.getOperand(1))) { 427 if (RHSI->getOpcode() == Instruction::Shl && 428 isa<ConstantInt>(RHSI->getOperand(0))) { 429 const APInt& C1 = cast<ConstantInt>(RHSI->getOperand(0))->getValue(); 430 if (C1.isPowerOf2()) { 431 Value *N = RHSI->getOperand(1); 432 const Type *NTy = N->getType(); 433 if (uint32_t C2 = C1.logBase2()) 434 N = Builder->CreateAdd(N, ConstantInt::get(NTy, C2), "tmp"); 435 return BinaryOperator::CreateLShr(Op0, N); 436 } 437 } 438 } 439 440 // udiv X, (Select Cond, C1, C2) --> Select Cond, (shr X, C1), (shr X, C2) 441 // where C1&C2 are powers of two. 442 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 443 if (ConstantInt *STO = dyn_cast<ConstantInt>(SI->getOperand(1))) 444 if (ConstantInt *SFO = dyn_cast<ConstantInt>(SI->getOperand(2))) { 445 const APInt &TVA = STO->getValue(), &FVA = SFO->getValue(); 446 if (TVA.isPowerOf2() && FVA.isPowerOf2()) { 447 // Compute the shift amounts 448 uint32_t TSA = TVA.logBase2(), FSA = FVA.logBase2(); 449 // Construct the "on true" case of the select 450 Constant *TC = ConstantInt::get(Op0->getType(), TSA); 451 Value *TSI = Builder->CreateLShr(Op0, TC, SI->getName()+".t"); 452 453 // Construct the "on false" case of the select 454 Constant *FC = ConstantInt::get(Op0->getType(), FSA); 455 Value *FSI = Builder->CreateLShr(Op0, FC, SI->getName()+".f"); 456 457 // construct the select instruction and return it. 458 return SelectInst::Create(SI->getOperand(0), TSI, FSI, SI->getName()); 459 } 460 } 461 return 0; 462} 463 464Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { 465 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 466 467 // Handle the integer div common cases 468 if (Instruction *Common = commonIDivTransforms(I)) 469 return Common; 470 471 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 472 // sdiv X, -1 == -X 473 if (RHS->isAllOnesValue()) 474 return BinaryOperator::CreateNeg(Op0); 475 476 // sdiv X, C --> ashr X, log2(C) 477 if (cast<SDivOperator>(&I)->isExact() && 478 RHS->getValue().isNonNegative() && 479 RHS->getValue().isPowerOf2()) { 480 Value *ShAmt = llvm::ConstantInt::get(RHS->getType(), 481 RHS->getValue().exactLogBase2()); 482 return BinaryOperator::CreateAShr(Op0, ShAmt, I.getName()); 483 } 484 485 // -X/C --> X/-C provided the negation doesn't overflow. 486 if (SubOperator *Sub = dyn_cast<SubOperator>(Op0)) 487 if (isa<Constant>(Sub->getOperand(0)) && 488 cast<Constant>(Sub->getOperand(0))->isNullValue() && 489 Sub->hasNoSignedWrap()) 490 return BinaryOperator::CreateSDiv(Sub->getOperand(1), 491 ConstantExpr::getNeg(RHS)); 492 } 493 494 // If the sign bits of both operands are zero (i.e. we can prove they are 495 // unsigned inputs), turn this into a udiv. 496 if (I.getType()->isIntegerTy()) { 497 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 498 if (MaskedValueIsZero(Op0, Mask)) { 499 if (MaskedValueIsZero(Op1, Mask)) { 500 // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set 501 return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 502 } 503 ConstantInt *ShiftedInt; 504 if (match(Op1, m_Shl(m_ConstantInt(ShiftedInt), m_Value())) && 505 ShiftedInt->getValue().isPowerOf2()) { 506 // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y) 507 // Safe because the only negative value (1 << Y) can take on is 508 // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have 509 // the sign bit set. 510 return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 511 } 512 } 513 } 514 515 return 0; 516} 517 518Instruction *InstCombiner::visitFDiv(BinaryOperator &I) { 519 return commonDivTransforms(I); 520} 521 522/// This function implements the transforms on rem instructions that work 523/// regardless of the kind of rem instruction it is (urem, srem, or frem). It 524/// is used by the visitors to those instructions. 525/// @brief Transforms common to all three rem instructions 526Instruction *InstCombiner::commonRemTransforms(BinaryOperator &I) { 527 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 528 529 if (isa<UndefValue>(Op0)) { // undef % X -> 0 530 if (I.getType()->isFPOrFPVectorTy()) 531 return ReplaceInstUsesWith(I, Op0); // X % undef -> undef (could be SNaN) 532 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 533 } 534 if (isa<UndefValue>(Op1)) 535 return ReplaceInstUsesWith(I, Op1); // X % undef -> undef 536 537 // Handle cases involving: rem X, (select Cond, Y, Z) 538 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 539 return &I; 540 541 return 0; 542} 543 544/// This function implements the transforms common to both integer remainder 545/// instructions (urem and srem). It is called by the visitors to those integer 546/// remainder instructions. 547/// @brief Common integer remainder transforms 548Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) { 549 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 550 551 if (Instruction *common = commonRemTransforms(I)) 552 return common; 553 554 // 0 % X == 0 for integer, we don't need to preserve faults! 555 if (Constant *LHS = dyn_cast<Constant>(Op0)) 556 if (LHS->isNullValue()) 557 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 558 559 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 560 // X % 0 == undef, we don't need to preserve faults! 561 if (RHS->equalsInt(0)) 562 return ReplaceInstUsesWith(I, UndefValue::get(I.getType())); 563 564 if (RHS->equalsInt(1)) // X % 1 == 0 565 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 566 567 if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) { 568 if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) { 569 if (Instruction *R = FoldOpIntoSelect(I, SI)) 570 return R; 571 } else if (isa<PHINode>(Op0I)) { 572 if (Instruction *NV = FoldOpIntoPhi(I)) 573 return NV; 574 } 575 576 // See if we can fold away this rem instruction. 577 if (SimplifyDemandedInstructionBits(I)) 578 return &I; 579 } 580 } 581 582 return 0; 583} 584 585Instruction *InstCombiner::visitURem(BinaryOperator &I) { 586 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 587 588 if (Instruction *common = commonIRemTransforms(I)) 589 return common; 590 591 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 592 // X urem C^2 -> X and C 593 // Check to see if this is an unsigned remainder with an exact power of 2, 594 // if so, convert to a bitwise and. 595 if (ConstantInt *C = dyn_cast<ConstantInt>(RHS)) 596 if (C->getValue().isPowerOf2()) 597 return BinaryOperator::CreateAnd(Op0, SubOne(C)); 598 } 599 600 if (Instruction *RHSI = dyn_cast<Instruction>(I.getOperand(1))) { 601 // Turn A % (C << N), where C is 2^k, into A & ((C << N)-1) 602 if (RHSI->getOpcode() == Instruction::Shl && 603 isa<ConstantInt>(RHSI->getOperand(0))) { 604 if (cast<ConstantInt>(RHSI->getOperand(0))->getValue().isPowerOf2()) { 605 Constant *N1 = Constant::getAllOnesValue(I.getType()); 606 Value *Add = Builder->CreateAdd(RHSI, N1, "tmp"); 607 return BinaryOperator::CreateAnd(Op0, Add); 608 } 609 } 610 } 611 612 // urem X, (select Cond, 2^C1, 2^C2) --> select Cond, (and X, C1), (and X, C2) 613 // where C1&C2 are powers of two. 614 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) { 615 if (ConstantInt *STO = dyn_cast<ConstantInt>(SI->getOperand(1))) 616 if (ConstantInt *SFO = dyn_cast<ConstantInt>(SI->getOperand(2))) { 617 // STO == 0 and SFO == 0 handled above. 618 if ((STO->getValue().isPowerOf2()) && 619 (SFO->getValue().isPowerOf2())) { 620 Value *TrueAnd = Builder->CreateAnd(Op0, SubOne(STO), 621 SI->getName()+".t"); 622 Value *FalseAnd = Builder->CreateAnd(Op0, SubOne(SFO), 623 SI->getName()+".f"); 624 return SelectInst::Create(SI->getOperand(0), TrueAnd, FalseAnd); 625 } 626 } 627 } 628 629 return 0; 630} 631 632Instruction *InstCombiner::visitSRem(BinaryOperator &I) { 633 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 634 635 // Handle the integer rem common cases 636 if (Instruction *Common = commonIRemTransforms(I)) 637 return Common; 638 639 if (Value *RHSNeg = dyn_castNegVal(Op1)) 640 if (!isa<Constant>(RHSNeg) || 641 (isa<ConstantInt>(RHSNeg) && 642 cast<ConstantInt>(RHSNeg)->getValue().isStrictlyPositive())) { 643 // X % -Y -> X % Y 644 Worklist.AddValue(I.getOperand(1)); 645 I.setOperand(1, RHSNeg); 646 return &I; 647 } 648 649 // If the sign bits of both operands are zero (i.e. we can prove they are 650 // unsigned inputs), turn this into a urem. 651 if (I.getType()->isIntegerTy()) { 652 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 653 if (MaskedValueIsZero(Op1, Mask) && MaskedValueIsZero(Op0, Mask)) { 654 // X srem Y -> X urem Y, iff X and Y don't have sign bit set 655 return BinaryOperator::CreateURem(Op0, Op1, I.getName()); 656 } 657 } 658 659 // If it's a constant vector, flip any negative values positive. 660 if (ConstantVector *RHSV = dyn_cast<ConstantVector>(Op1)) { 661 unsigned VWidth = RHSV->getNumOperands(); 662 663 bool hasNegative = false; 664 for (unsigned i = 0; !hasNegative && i != VWidth; ++i) 665 if (ConstantInt *RHS = dyn_cast<ConstantInt>(RHSV->getOperand(i))) 666 if (RHS->getValue().isNegative()) 667 hasNegative = true; 668 669 if (hasNegative) { 670 std::vector<Constant *> Elts(VWidth); 671 for (unsigned i = 0; i != VWidth; ++i) { 672 if (ConstantInt *RHS = dyn_cast<ConstantInt>(RHSV->getOperand(i))) { 673 if (RHS->getValue().isNegative()) 674 Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS)); 675 else 676 Elts[i] = RHS; 677 } 678 } 679 680 Constant *NewRHSV = ConstantVector::get(Elts); 681 if (NewRHSV != RHSV) { 682 Worklist.AddValue(I.getOperand(1)); 683 I.setOperand(1, NewRHSV); 684 return &I; 685 } 686 } 687 } 688 689 return 0; 690} 691 692Instruction *InstCombiner::visitFRem(BinaryOperator &I) { 693 return commonRemTransforms(I); 694} 695 696