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