Bug Summary

File:lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
Warning:line 847, column 14
Called C++ object pointer is null

Annotated Source Code

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