Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
Line
Count
Source (jump to first uncovered line)
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/APFloat.h"
16
#include "llvm/ADT/APInt.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/Analysis/InstructionSimplify.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/Support/KnownBits.h"
34
#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
35
#include "llvm/Transforms/Utils/BuildLibCalls.h"
36
#include <cassert>
37
#include <cstddef>
38
#include <cstdint>
39
#include <utility>
40
41
using namespace llvm;
42
using namespace PatternMatch;
43
44
#define DEBUG_TYPE "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.
49
static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC,
50
372k
                                        Instruction &CxtI) {
51
372k
  // If V has multiple uses, then we would have to do more analysis to determine
52
372k
  // if this is safe.  For example, the use could be in dynamically unreached
53
372k
  // code.
54
372k
  if (!V->hasOneUse()) 
return nullptr306k
;
55
65.2k
56
65.2k
  bool MadeChange = false;
57
65.2k
58
65.2k
  // ((1 << A) >>u B) --> (1 << (A-B))
59
65.2k
  // Because V cannot be zero, we know that B is less than A.
60
65.2k
  Value *A = nullptr, *B = nullptr, *One = nullptr;
61
65.2k
  if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(One), m_Value(A))), m_Value(B))) &&
62
65.2k
      
match(One, m_One())10
) {
63
9
    A = IC.Builder.CreateSub(A, B);
64
9
    return IC.Builder.CreateShl(One, A);
65
9
  }
66
65.2k
67
65.2k
  // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it
68
65.2k
  // inexact.  Similarly for <<.
69
65.2k
  BinaryOperator *I = dyn_cast<BinaryOperator>(V);
70
65.2k
  if (I && 
I->isLogicalShift()4.29k
&&
71
65.2k
      
IC.isKnownToBeAPowerOfTwo(I->getOperand(0), false, 0, &CxtI)633
) {
72
110
    // We know that this is an exact/nuw shift and that the input is a
73
110
    // non-zero context as well.
74
110
    if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) {
75
0
      I->setOperand(0, V2);
76
0
      MadeChange = true;
77
0
    }
78
110
79
110
    if (I->getOpcode() == Instruction::LShr && 
!I->isExact()6
) {
80
2
      I->setIsExact();
81
2
      MadeChange = true;
82
2
    }
83
110
84
110
    if (I->getOpcode() == Instruction::Shl && 
!I->hasNoUnsignedWrap()104
) {
85
35
      I->setHasNoUnsignedWrap();
86
35
      MadeChange = true;
87
35
    }
88
110
  }
89
65.2k
90
65.2k
  // TODO: Lots more we could do here:
91
65.2k
  //    If V is a phi node, we can call this on each of its operands.
92
65.2k
  //    "select cond, X, 0" can simplify to "X".
93
65.2k
94
65.2k
  return MadeChange ? 
V37
:
nullptr65.2k
;
95
65.2k
}
96
97
/// A helper routine of InstCombiner::visitMul().
98
///
99
/// If C is a scalar/vector of known powers of 2, then this function returns
100
/// a new scalar/vector obtained from logBase2 of C.
101
/// Return a null pointer otherwise.
102
328k
static Constant *getLogBase2(Type *Ty, Constant *C) {
103
328k
  const APInt *IVal;
104
328k
  if (match(C, m_APInt(IVal)) && 
IVal->isPowerOf2()327k
)
105
27.5k
    return ConstantInt::get(Ty, IVal->logBase2());
106
301k
107
301k
  if (!Ty->isVectorTy())
108
296k
    return nullptr;
109
4.74k
110
4.74k
  SmallVector<Constant *, 4> Elts;
111
4.96k
  for (unsigned I = 0, E = Ty->getVectorNumElements(); I != E; 
++I225
) {
112
4.95k
    Constant *Elt = C->getAggregateElement(I);
113
4.95k
    if (!Elt)
114
0
      return nullptr;
115
4.95k
    if (isa<UndefValue>(Elt)) {
116
16
      Elts.push_back(UndefValue::get(Ty->getScalarType()));
117
16
      continue;
118
16
    }
119
4.93k
    if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2())
120
4.72k
      return nullptr;
121
209
    Elts.push_back(ConstantInt::get(Ty->getScalarType(), IVal->logBase2()));
122
209
  }
123
4.74k
124
4.74k
  
return ConstantVector::get(Elts)15
;
125
4.74k
}
126
127
965k
Instruction *InstCombiner::visitMul(BinaryOperator &I) {
128
965k
  if (Value *V = SimplifyMulInst(I.getOperand(0), I.getOperand(1),
129
70
                                 SQ.getWithInstruction(&I)))
130
70
    return replaceInstUsesWith(I, V);
131
965k
132
965k
  if (SimplifyAssociativeOrCommutative(I))
133
8.04k
    return &I;
134
957k
135
957k
  if (Instruction *X = foldVectorBinop(I))
136
25
    return X;
137
957k
138
957k
  if (Value *V = SimplifyUsingDistributiveLaws(I))
139
2
    return replaceInstUsesWith(I, V);
140
957k
141
957k
  // X * -1 == 0 - X
142
957k
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
143
957k
  if (match(Op1, m_AllOnes())) {
144
1.72k
    BinaryOperator *BO = BinaryOperator::CreateNeg(Op0, I.getName());
145
1.72k
    if (I.hasNoSignedWrap())
146
180
      BO->setHasNoSignedWrap();
147
1.72k
    return BO;
148
1.72k
  }
149
955k
150
955k
  // Also allow combining multiply instructions on vectors.
151
955k
  {
152
955k
    Value *NewOp;
153
955k
    Constant *C1, *C2;
154
955k
    const APInt *IVal;
155
955k
    if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)),
156
955k
                        m_Constant(C1))) &&
157
955k
        
match(C1, m_APInt(IVal))185
) {
158
185
      // ((X << C2)*C1) == (X * (C1 << C2))
159
185
      Constant *Shl = ConstantExpr::getShl(C1, C2);
160
185
      BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0));
161
185
      BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl);
162
185
      if (I.hasNoUnsignedWrap() && 
Mul->hasNoUnsignedWrap()4
)
163
4
        BO->setHasNoUnsignedWrap();
164
185
      if (I.hasNoSignedWrap() && 
Mul->hasNoSignedWrap()50
&&
165
185
          
Shl->isNotMinSignedValue()41
)
166
41
        BO->setHasNoSignedWrap();
167
185
      return BO;
168
185
    }
169
955k
170
955k
    if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
171
325k
      // Replace X*(2^C) with X << C, where C is either a scalar or a vector.
172
325k
      if (Constant *NewCst = getLogBase2(NewOp->getType(), C1)) {
173
24.9k
        BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);
174
24.9k
175
24.9k
        if (I.hasNoUnsignedWrap())
176
3.94k
          Shl->setHasNoUnsignedWrap();
177
24.9k
        if (I.hasNoSignedWrap()) {
178
7.12k
          const APInt *V;
179
7.12k
          if (match(NewCst, m_APInt(V)) && *V != V->getBitWidth() - 1)
180
6.99k
            Shl->setHasNoSignedWrap();
181
7.12k
        }
182
24.9k
183
24.9k
        return Shl;
184
24.9k
      }
185
930k
    }
186
930k
  }
187
930k
188
930k
  if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
189
296k
    // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n
190
296k
    // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n
191
296k
    // The "* (2**n)" thus becomes a potential shifting opportunity.
192
296k
    {
193
296k
      const APInt &   Val = CI->getValue();
194
296k
      const APInt &PosVal = Val.abs();
195
296k
      if (Val.isNegative() && 
PosVal.isPowerOf2()66.3k
) {
196
17.9k
        Value *X = nullptr, *Y = nullptr;
197
17.9k
        if (Op0->hasOneUse()) {
198
17.3k
          ConstantInt *C1;
199
17.3k
          Value *Sub = nullptr;
200
17.3k
          if (match(Op0, m_Sub(m_Value(Y), m_Value(X))))
201
5
            Sub = Builder.CreateSub(X, Y, "suba");
202
17.3k
          else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1))))
203
0
            Sub = Builder.CreateSub(Builder.CreateNeg(C1), Y, "subc");
204
17.3k
          if (Sub)
205
5
            return
206
5
              BinaryOperator::CreateMul(Sub,
207
5
                                        ConstantInt::get(Y->getType(), PosVal));
208
930k
        }
209
17.9k
      }
210
296k
    }
211
296k
  }
212
930k
213
930k
  if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
214
27
    return FoldedMul;
215
930k
216
930k
  // Simplify mul instructions with a constant RHS.
217
930k
  if (isa<Constant>(Op1)) {
218
301k
    // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
219
301k
    Value *X;
220
301k
    Constant *C1;
221
301k
    if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) {
222
133
      Value *Mul = Builder.CreateMul(C1, Op1);
223
133
      // Only go forward with the transform if C1*CI simplifies to a tidier
224
133
      // constant.
225
133
      if (!match(Mul, m_Mul(m_Value(), m_Value())))
226
133
        return BinaryOperator::CreateAdd(Builder.CreateMul(X, Op1), Mul);
227
930k
    }
228
301k
  }
229
930k
230
930k
  // -X * C --> X * -C
231
930k
  Value *X, *Y;
232
930k
  Constant *Op1C;
233
930k
  if (match(Op0, m_Neg(m_Value(X))) && 
match(Op1, m_Constant(Op1C))22
)
234
8
    return BinaryOperator::CreateMul(X, ConstantExpr::getNeg(Op1C));
235
930k
236
930k
  // -X * -Y --> X * Y
237
930k
  if (match(Op0, m_Neg(m_Value(X))) && 
match(Op1, m_Neg(m_Value(Y)))14
) {
238
7
    auto *NewMul = BinaryOperator::CreateMul(X, Y);
239
7
    if (I.hasNoSignedWrap() &&
240
7
        
cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap()3
&&
241
7
        
cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap()3
)
242
3
      NewMul->setHasNoSignedWrap();
243
7
    return NewMul;
244
7
  }
245
930k
246
930k
  // -X * Y --> -(X * Y)
247
930k
  // X * -Y --> -(X * Y)
248
930k
  if (match(&I, m_c_Mul(m_OneUse(m_Neg(m_Value(X))), m_Value(Y))))
249
155
    return BinaryOperator::CreateNeg(Builder.CreateMul(X, Y));
250
930k
251
930k
  // (X / Y) *  Y = X - (X % Y)
252
930k
  // (X / Y) * -Y = (X % Y) - X
253
930k
  {
254
930k
    Value *Y = Op1;
255
930k
    BinaryOperator *Div = dyn_cast<BinaryOperator>(Op0);
256
930k
    if (!Div || 
(312k
Div->getOpcode() != Instruction::UDiv312k
&&
257
864k
                 
Div->getOpcode() != Instruction::SDiv271k
)) {
258
864k
      Y = Op0;
259
864k
      Div = dyn_cast<BinaryOperator>(Op1);
260
864k
    }
261
930k
    Value *Neg = dyn_castNegVal(Y);
262
930k
    if (Div && 
Div->hasOneUse()150k
&&
263
930k
        
(25.5k
Div->getOperand(1) == Y25.5k
||
Div->getOperand(1) == Neg25.4k
) &&
264
930k
        
(133
Div->getOpcode() == Instruction::UDiv133
||
265
133
         
Div->getOpcode() == Instruction::SDiv40
)) {
266
119
      Value *X = Div->getOperand(0), *DivOp1 = Div->getOperand(1);
267
119
268
119
      // If the division is exact, X % Y is zero, so we end up with X or -X.
269
119
      if (Div->isExact()) {
270
1
        if (DivOp1 == Y)
271
0
          return replaceInstUsesWith(I, X);
272
1
        return BinaryOperator::CreateNeg(X);
273
1
      }
274
118
275
118
      auto RemOpc = Div->getOpcode() == Instruction::UDiv ? 
Instruction::URem93
276
118
                                                          : 
Instruction::SRem25
;
277
118
      Value *Rem = Builder.CreateBinOp(RemOpc, X, DivOp1);
278
118
      if (DivOp1 == Y)
279
116
        return BinaryOperator::CreateSub(X, Rem);
280
2
      return BinaryOperator::CreateSub(Rem, X);
281
2
    }
282
930k
  }
283
930k
284
930k
  /// i1 mul -> i1 and.
285
930k
  if (I.getType()->isIntOrIntVectorTy(1))
286
2
    return BinaryOperator::CreateAnd(Op0, Op1);
287
930k
288
930k
  // X*(1 << Y) --> X << Y
289
930k
  // (1 << Y)*X --> X << Y
290
930k
  {
291
930k
    Value *Y;
292
930k
    BinaryOperator *BO = nullptr;
293
930k
    bool ShlNSW = false;
294
930k
    if (match(Op0, m_Shl(m_One(), m_Value(Y)))) {
295
40
      BO = BinaryOperator::CreateShl(Op1, Y);
296
40
      ShlNSW = cast<ShlOperator>(Op0)->hasNoSignedWrap();
297
930k
    } else if (match(Op1, m_Shl(m_One(), m_Value(Y)))) {
298
15
      BO = BinaryOperator::CreateShl(Op0, Y);
299
15
      ShlNSW = cast<ShlOperator>(Op1)->hasNoSignedWrap();
300
15
    }
301
930k
    if (BO) {
302
55
      if (I.hasNoUnsignedWrap())
303
1
        BO->setHasNoUnsignedWrap();
304
55
      if (I.hasNoSignedWrap() && 
ShlNSW20
)
305
1
        BO->setHasNoSignedWrap();
306
55
      return BO;
307
55
    }
308
930k
  }
309
930k
310
930k
  // (bool X) * Y --> X ? Y : 0
311
930k
  // Y * (bool X) --> X ? Y : 0
312
930k
  if (match(Op0, m_ZExt(m_Value(X))) && 
X->getType()->isIntOrIntVectorTy(1)12.3k
)
313
61
    return SelectInst::Create(X, Op1, ConstantInt::get(I.getType(), 0));
314
930k
  if (match(Op1, m_ZExt(m_Value(X))) && 
X->getType()->isIntOrIntVectorTy(1)89.1k
)
315
98
    return SelectInst::Create(X, Op0, ConstantInt::get(I.getType(), 0));
316
929k
317
929k
  // (lshr X, 31) * Y --> (ashr X, 31) & Y
318
929k
  // Y * (lshr X, 31) --> (ashr X, 31) & Y
319
929k
  // TODO: We are not checking one-use because the elimination of the multiply
320
929k
  //       is better for analysis?
321
929k
  // TODO: Should we canonicalize to '(X < 0) ? Y : 0' instead? That would be
322
929k
  //       more similar to what we're doing above.
323
929k
  const APInt *C;
324
929k
  if (match(Op0, m_LShr(m_Value(X), m_APInt(C))) && 
*C == C->getBitWidth() - 113.0k
)
325
7
    return BinaryOperator::CreateAnd(Builder.CreateAShr(X, *C), Op1);
326
929k
  if (match(Op1, m_LShr(m_Value(X), m_APInt(C))) && 
*C == C->getBitWidth() - 12.54k
)
327
0
    return BinaryOperator::CreateAnd(Builder.CreateAShr(X, *C), Op0);
328
929k
329
929k
  if (Instruction *Ext = narrowMathIfNoOverflow(I))
330
17
    return Ext;
331
929k
332
929k
  bool Changed = false;
333
929k
  if (!I.hasNoSignedWrap() && 
willNotOverflowSignedMul(Op0, Op1, I)317k
) {
334
2.68k
    Changed = true;
335
2.68k
    I.setHasNoSignedWrap(true);
336
2.68k
  }
337
929k
338
929k
  if (!I.hasNoUnsignedWrap() && 
willNotOverflowUnsignedMul(Op0, Op1, I)877k
) {
339
2.02k
    Changed = true;
340
2.02k
    I.setHasNoUnsignedWrap(true);
341
2.02k
  }
342
929k
343
929k
  return Changed ? 
&I4.36k
:
nullptr925k
;
344
929k
}
345
346
678k
Instruction *InstCombiner::visitFMul(BinaryOperator &I) {
347
678k
  if (Value *V = SimplifyFMulInst(I.getOperand(0), I.getOperand(1),
348
112
                                  I.getFastMathFlags(),
349
112
                                  SQ.getWithInstruction(&I)))
350
112
    return replaceInstUsesWith(I, V);
351
678k
352
678k
  if (SimplifyAssociativeOrCommutative(I))
353
7.99k
    return &I;
354
670k
355
670k
  if (Instruction *X = foldVectorBinop(I))
356
81
    return X;
357
670k
358
670k
  if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
359
33
    return FoldedMul;
360
670k
361
670k
  // X * -1.0 --> -X
362
670k
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
363
670k
  if (match(Op1, m_SpecificFP(-1.0)))
364
142
    return BinaryOperator::CreateFNegFMF(Op0, &I);
365
670k
366
670k
  // -X * -Y --> X * Y
367
670k
  Value *X, *Y;
368
670k
  if (match(Op0, m_FNeg(m_Value(X))) && 
match(Op1, m_FNeg(m_Value(Y)))390
)
369
52
    return BinaryOperator::CreateFMulFMF(X, Y, &I);
370
670k
371
670k
  // -X * C --> X * -C
372
670k
  Constant *C;
373
670k
  if (match(Op0, m_FNeg(m_Value(X))) && 
match(Op1, m_Constant(C))338
)
374
40
    return BinaryOperator::CreateFMulFMF(X, ConstantExpr::getFNeg(C), &I);
375
670k
376
670k
  // Sink negation: -X * Y --> -(X * Y)
377
670k
  // But don't transform constant expressions because there's an inverse fold.
378
670k
  if (match(Op0, m_OneUse(m_FNeg(m_Value(X)))) && 
!isa<ConstantExpr>(Op0)13
)
379
13
    return BinaryOperator::CreateFNegFMF(Builder.CreateFMulFMF(X, Op1, &I), &I);
380
670k
381
670k
  // Sink negation: Y * -X --> -(X * Y)
382
670k
  // But don't transform constant expressions because there's an inverse fold.
383
670k
  if (match(Op1, m_OneUse(m_FNeg(m_Value(X)))) && 
!isa<ConstantExpr>(Op1)157
)
384
156
    return BinaryOperator::CreateFNegFMF(Builder.CreateFMulFMF(X, Op0, &I), &I);
385
670k
386
670k
  // fabs(X) * fabs(X) -> X * X
387
670k
  if (Op0 == Op1 && 
match(Op0, m_Intrinsic<Intrinsic::fabs>(m_Value(X)))40.4k
)
388
3
    return BinaryOperator::CreateFMulFMF(X, X, &I);
389
670k
390
670k
  // (select A, B, C) * (select A, D, E) --> select A, (B*D), (C*E)
391
670k
  if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
392
5
    return replaceInstUsesWith(I, V);
393
670k
394
670k
  if (I.hasAllowReassoc()) {
395
2.98k
    // Reassociate constant RHS with another constant to form constant
396
2.98k
    // expression.
397
2.98k
    if (match(Op1, m_Constant(C)) && 
C->isFiniteNonZeroFP()661
) {
398
647
      Constant *C1;
399
647
      if (match(Op0, m_OneUse(m_FDiv(m_Constant(C1), m_Value(X))))) {
400
1
        // (C1 / X) * C --> (C * C1) / X
401
1
        Constant *CC1 = ConstantExpr::getFMul(C, C1);
402
1
        if (CC1->isNormalFP())
403
1
          return BinaryOperator::CreateFDivFMF(CC1, X, &I);
404
646
      }
405
646
      if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) {
406
10
        // (X / C1) * C --> X * (C / C1)
407
10
        Constant *CDivC1 = ConstantExpr::getFDiv(C, C1);
408
10
        if (CDivC1->isNormalFP())
409
4
          return BinaryOperator::CreateFMulFMF(X, CDivC1, &I);
410
6
411
6
        // If the constant was a denormal, try reassociating differently.
412
6
        // (X / C1) * C --> X / (C1 / C)
413
6
        Constant *C1DivC = ConstantExpr::getFDiv(C1, C);
414
6
        if (Op0->hasOneUse() && 
C1DivC->isNormalFP()5
)
415
3
          return BinaryOperator::CreateFDivFMF(X, C1DivC, &I);
416
639
      }
417
639
418
639
      // We do not need to match 'fadd C, X' and 'fsub X, C' because they are
419
639
      // canonicalized to 'fadd X, C'. Distributing the multiply may allow
420
639
      // further folds and (X * C) + C2 is 'fma'.
421
639
      if (match(Op0, m_OneUse(m_FAdd(m_Value(X), m_Constant(C1))))) {
422
7
        // (X + C1) * C --> (X * C) + (C * C1)
423
7
        Constant *CC1 = ConstantExpr::getFMul(C, C1);
424
7
        Value *XC = Builder.CreateFMulFMF(X, C, &I);
425
7
        return BinaryOperator::CreateFAddFMF(XC, CC1, &I);
426
7
      }
427
632
      if (match(Op0, m_OneUse(m_FSub(m_Constant(C1), m_Value(X))))) {
428
2
        // (C1 - X) * C --> (C * C1) - (X * C)
429
2
        Constant *CC1 = ConstantExpr::getFMul(C, C1);
430
2
        Value *XC = Builder.CreateFMulFMF(X, C, &I);
431
2
        return BinaryOperator::CreateFSubFMF(CC1, XC, &I);
432
2
      }
433
2.97k
    }
434
2.97k
435
2.97k
    Value *Z;
436
2.97k
    if (match(&I, m_c_FMul(m_OneUse(m_FDiv(m_Value(X), m_Value(Y))),
437
2.97k
                           m_Value(Z)))) {
438
11
      // Sink division: (X / Y) * Z --> (X * Z) / Y
439
11
      Value *NewFMul = Builder.CreateFMulFMF(X, Z, &I);
440
11
      return BinaryOperator::CreateFDivFMF(NewFMul, Y, &I);
441
11
    }
442
2.95k
443
2.95k
    // sqrt(X) * sqrt(Y) -> sqrt(X * Y)
444
2.95k
    // nnan disallows the possibility of returning a number if both operands are
445
2.95k
    // negative (in that case, we should return NaN).
446
2.95k
    if (I.hasNoNaNs() &&
447
2.95k
        
match(Op0, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(X))))2.79k
&&
448
2.95k
        
match(Op1, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(Y))))50
) {
449
4
      Value *XY = Builder.CreateFMulFMF(X, Y, &I);
450
4
      Value *Sqrt = Builder.CreateUnaryIntrinsic(Intrinsic::sqrt, XY, &I);
451
4
      return replaceInstUsesWith(I, Sqrt);
452
4
    }
453
2.95k
454
2.95k
    // Like the similar transform in instsimplify, this requires 'nsz' because
455
2.95k
    // sqrt(-0.0) = -0.0, and -0.0 * -0.0 does not simplify to -0.0.
456
2.95k
    if (I.hasNoNaNs() && 
I.hasNoSignedZeros()2.79k
&&
Op0 == Op12.77k
&&
457
2.95k
        
Op0->hasNUses(2)806
) {
458
332
      // Peek through fdiv to find squaring of square root:
459
332
      // (X / sqrt(Y)) * (X / sqrt(Y)) --> (X * X) / Y
460
332
      if (match(Op0, m_FDiv(m_Value(X),
461
332
                            m_Intrinsic<Intrinsic::sqrt>(m_Value(Y))))) {
462
2
        Value *XX = Builder.CreateFMulFMF(X, X, &I);
463
2
        return BinaryOperator::CreateFDivFMF(XX, Y, &I);
464
2
      }
465
330
      // (sqrt(Y) / X) * (sqrt(Y) / X) --> Y / (X * X)
466
330
      if (match(Op0, m_FDiv(m_Intrinsic<Intrinsic::sqrt>(m_Value(Y)),
467
330
                            m_Value(X)))) {
468
2
        Value *XX = Builder.CreateFMulFMF(X, X, &I);
469
2
        return BinaryOperator::CreateFDivFMF(Y, XX, &I);
470
2
      }
471
2.95k
    }
472
2.95k
473
2.95k
    // exp(X) * exp(Y) -> exp(X + Y)
474
2.95k
    // Match as long as at least one of exp has only one use.
475
2.95k
    if (match(Op0, m_Intrinsic<Intrinsic::exp>(m_Value(X))) &&
476
2.95k
        
match(Op1, m_Intrinsic<Intrinsic::exp>(m_Value(Y)))6
&&
477
2.95k
        
(6
Op0->hasOneUse()6
||
Op1->hasOneUse()1
)) {
478
5
      Value *XY = Builder.CreateFAddFMF(X, Y, &I);
479
5
      Value *Exp = Builder.CreateUnaryIntrinsic(Intrinsic::exp, XY, &I);
480
5
      return replaceInstUsesWith(I, Exp);
481
5
    }
482
2.94k
483
2.94k
    // exp2(X) * exp2(Y) -> exp2(X + Y)
484
2.94k
    // Match as long as at least one of exp2 has only one use.
485
2.94k
    if (match(Op0, m_Intrinsic<Intrinsic::exp2>(m_Value(X))) &&
486
2.94k
        
match(Op1, m_Intrinsic<Intrinsic::exp2>(m_Value(Y)))6
&&
487
2.94k
        
(6
Op0->hasOneUse()6
||
Op1->hasOneUse()1
)) {
488
5
      Value *XY = Builder.CreateFAddFMF(X, Y, &I);
489
5
      Value *Exp2 = Builder.CreateUnaryIntrinsic(Intrinsic::exp2, XY, &I);
490
5
      return replaceInstUsesWith(I, Exp2);
491
5
    }
492
2.94k
493
2.94k
    // (X*Y) * X => (X*X) * Y where Y != X
494
2.94k
    //  The purpose is two-fold:
495
2.94k
    //   1) to form a power expression (of X).
496
2.94k
    //   2) potentially shorten the critical path: After transformation, the
497
2.94k
    //  latency of the instruction Y is amortized by the expression of X*X,
498
2.94k
    //  and therefore Y is in a "less critical" position compared to what it
499
2.94k
    //  was before the transformation.
500
2.94k
    if (match(Op0, m_OneUse(m_c_FMul(m_Specific(Op1), m_Value(Y)))) &&
501
2.94k
        
Op1 != Y26
) {
502
20
      Value *XX = Builder.CreateFMulFMF(Op1, Op1, &I);
503
20
      return BinaryOperator::CreateFMulFMF(XX, Y, &I);
504
20
    }
505
2.92k
    if (match(Op1, m_OneUse(m_c_FMul(m_Specific(Op0), m_Value(Y)))) &&
506
2.92k
        
Op0 != Y4
) {
507
4
      Value *XX = Builder.CreateFMulFMF(Op0, Op0, &I);
508
4
      return BinaryOperator::CreateFMulFMF(XX, Y, &I);
509
4
    }
510
670k
  }
511
670k
512
670k
  // log2(X * 0.5) * Y = log2(X) * Y - Y
513
670k
  if (I.isFast()) {
514
2.74k
    IntrinsicInst *Log2 = nullptr;
515
2.74k
    if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::log2>(
516
2.74k
            m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
517
2
      Log2 = cast<IntrinsicInst>(Op0);
518
2
      Y = Op1;
519
2
    }
520
2.74k
    if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::log2>(
521
2.74k
            m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
522
0
      Log2 = cast<IntrinsicInst>(Op1);
523
0
      Y = Op0;
524
0
    }
525
2.74k
    if (Log2) {
526
2
      Log2->setArgOperand(0, X);
527
2
      Log2->copyFastMathFlags(&I);
528
2
      Value *LogXTimesY = Builder.CreateFMulFMF(Log2, Y, &I);
529
2
      return BinaryOperator::CreateFSubFMF(LogXTimesY, Y, &I);
530
2
    }
531
670k
  }
532
670k
533
670k
  return nullptr;
534
670k
}
535
536
/// Fold a divide or remainder with a select instruction divisor when one of the
537
/// select operands is zero. In that case, we can use the other select operand
538
/// because div/rem by zero is undefined.
539
372k
bool InstCombiner::simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I) {
540
372k
  SelectInst *SI = dyn_cast<SelectInst>(I.getOperand(1));
541
372k
  if (!SI)
542
370k
    return false;
543
2.05k
544
2.05k
  int NonNullOperand;
545
2.05k
  if (match(SI->getTrueValue(), m_Zero()))
546
3
    // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
547
3
    NonNullOperand = 2;
548
2.05k
  else if (match(SI->getFalseValue(), m_Zero()))
549
9
    // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
550
9
    NonNullOperand = 1;
551
2.04k
  else
552
2.04k
    return false;
553
12
554
12
  // Change the div/rem to use 'Y' instead of the select.
555
12
  I.setOperand(1, SI->getOperand(NonNullOperand));
556
12
557
12
  // Okay, we know we replace the operand of the div/rem with 'Y' with no
558
12
  // problem.  However, the select, or the condition of the select may have
559
12
  // multiple uses.  Based on our knowledge that the operand must be non-zero,
560
12
  // propagate the known value for the select into other uses of it, and
561
12
  // propagate a known value of the condition into its other users.
562
12
563
12
  // If the select and condition only have a single use, don't bother with this,
564
12
  // early exit.
565
12
  Value *SelectCond = SI->getCondition();
566
12
  if (SI->use_empty() && 
SelectCond->hasOneUse()6
)
567
1
    return true;
568
11
569
11
  // Scan the current block backward, looking for other uses of SI.
570
11
  BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin();
571
11
  Type *CondTy = SelectCond->getType();
572
67
  while (BBI != BBFront) {
573
66
    --BBI;
574
66
    // If we found an instruction that we can't assume will return, so
575
66
    // information from below it cannot be propagated above it.
576
66
    if (!isGuaranteedToTransferExecutionToSuccessor(&*BBI))
577
3
      break;
578
63
579
63
    // Replace uses of the select or its condition with the known values.
580
63
    for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end();
581
182
         I != E; 
++I119
) {
582
119
      if (*I == SI) {
583
2
        *I = SI->getOperand(NonNullOperand);
584
2
        Worklist.Add(&*BBI);
585
117
      } else if (*I == SelectCond) {
586
20
        *I = NonNullOperand == 1 ? 
ConstantInt::getTrue(CondTy)18
587
20
                                 : 
ConstantInt::getFalse(CondTy)2
;
588
20
        Worklist.Add(&*BBI);
589
20
      }
590
119
    }
591
63
592
63
    // If we past the instruction, quit looking for it.
593
63
    if (&*BBI == SI)
594
8
      SI = nullptr;
595
63
    if (&*BBI == SelectCond)
596
7
      SelectCond = nullptr;
597
63
598
63
    // If we ran out of things to eliminate, break out of the loop.
599
63
    if (!SelectCond && 
!SI7
)
600
7
      break;
601
63
602
63
  }
603
11
  return true;
604
11
}
605
606
/// True if the multiply can not be expressed in an int this size.
607
static bool multiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product,
608
171
                              bool IsSigned) {
609
171
  bool Overflow;
610
171
  Product = IsSigned ? 
C1.smul_ov(C2, Overflow)153
:
C1.umul_ov(C2, Overflow)18
;
611
171
  return Overflow;
612
171
}
613
614
/// True if C1 is a multiple of C2. Quotient contains C1/C2.
615
static bool isMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
616
1.14k
                       bool IsSigned) {
617
1.14k
  assert(C1.getBitWidth() == C2.getBitWidth() && "Constant widths not equal");
618
1.14k
619
1.14k
  // Bail if we will divide by zero.
620
1.14k
  if (C2.isNullValue())
621
0
    return false;
622
1.14k
623
1.14k
  // Bail if we would divide INT_MIN by -1.
624
1.14k
  if (IsSigned && 
C1.isMinSignedValue()833
&&
C2.isAllOnesValue()0
)
625
0
    return false;
626
1.14k
627
1.14k
  APInt Remainder(C1.getBitWidth(), /*val=*/0ULL, IsSigned);
628
1.14k
  if (IsSigned)
629
833
    APInt::sdivrem(C1, C2, Quotient, Remainder);
630
312
  else
631
312
    APInt::udivrem(C1, C2, Quotient, Remainder);
632
1.14k
633
1.14k
  return Remainder.isMinValue();
634
1.14k
}
635
636
/// This function implements the transforms common to both integer division
637
/// instructions (udiv and sdiv). It is called by the visitors to those integer
638
/// division instructions.
639
/// Common integer divide transforms
640
278k
Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) {
641
278k
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
642
278k
  bool IsSigned = I.getOpcode() == Instruction::SDiv;
643
278k
  Type *Ty = I.getType();
644
278k
645
278k
  // The RHS is known non-zero.
646
278k
  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
647
16
    I.setOperand(1, V);
648
16
    return &I;
649
16
  }
650
278k
651
278k
  // Handle cases involving: [su]div X, (select Cond, Y, Z)
652
278k
  // This does not apply for fdiv.
653
278k
  if (simplifyDivRemOfSelectWithZeroOp(I))
654
9
    return &I;
655
278k
656
278k
  const APInt *C2;
657
278k
  if (match(Op1, m_APInt(C2))) {
658
149k
    Value *X;
659
149k
    const APInt *C1;
660
149k
661
149k
    // (X / C1) / C2  -> X / (C1*C2)
662
149k
    if ((IsSigned && 
match(Op0, m_SDiv(m_Value(X), m_APInt(C1)))88.8k
) ||
663
149k
        
(149k
!IsSigned149k
&&
match(Op0, m_UDiv(m_Value(X), m_APInt(C1)))60.6k
)) {
664
171
      APInt Product(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
665
171
      if (!multiplyOverflows(*C1, *C2, Product, IsSigned))
666
171
        return BinaryOperator::Create(I.getOpcode(), X,
667
171
                                      ConstantInt::get(Ty, Product));
668
149k
    }
669
149k
670
149k
    if ((IsSigned && 
match(Op0, m_NSWMul(m_Value(X), m_APInt(C1)))88.6k
) ||
671
149k
        
(149k
!IsSigned149k
&&
match(Op0, m_NUWMul(m_Value(X), m_APInt(C1)))60.6k
)) {
672
360
      APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
673
360
674
360
      // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
675
360
      if (isMultiple(*C2, *C1, Quotient, IsSigned)) {
676
4
        auto *NewDiv = BinaryOperator::Create(I.getOpcode(), X,
677
4
                                              ConstantInt::get(Ty, Quotient));
678
4
        NewDiv->setIsExact(I.isExact());
679
4
        return NewDiv;
680
4
      }
681
356
682
356
      // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
683
356
      if (isMultiple(*C1, *C2, Quotient, IsSigned)) {
684
4
        auto *Mul = BinaryOperator::Create(Instruction::Mul, X,
685
4
                                           ConstantInt::get(Ty, Quotient));
686
4
        auto *OBO = cast<OverflowingBinaryOperator>(Op0);
687
4
        Mul->setHasNoUnsignedWrap(!IsSigned && 
OBO->hasNoUnsignedWrap()1
);
688
4
        Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
689
4
        return Mul;
690
4
      }
691
149k
    }
692
149k
693
149k
    if ((IsSigned && 
match(Op0, m_NSWShl(m_Value(X), m_APInt(C1)))88.6k
&&
694
149k
         
*C1 != C1->getBitWidth() - 179
) ||
695
149k
        
(149k
!IsSigned149k
&&
match(Op0, m_NUWShl(m_Value(X), m_APInt(C1)))60.6k
)) {
696
219
      APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
697
219
      APInt C1Shifted = APInt::getOneBitSet(
698
219
          C1->getBitWidth(), static_cast<unsigned>(C1->getLimitedValue()));
699
219
700
219
      // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of 1 << C1.
701
219
      if (isMultiple(*C2, C1Shifted, Quotient, IsSigned)) {
702
9
        auto *BO = BinaryOperator::Create(I.getOpcode(), X,
703
9
                                          ConstantInt::get(Ty, Quotient));
704
9
        BO->setIsExact(I.isExact());
705
9
        return BO;
706
9
      }
707
210
708
210
      // (X << C1) / C2 -> X * ((1 << C1) / C2) if 1 << C1 is a multiple of C2.
709
210
      if (isMultiple(C1Shifted, *C2, Quotient, IsSigned)) {
710
5
        auto *Mul = BinaryOperator::Create(Instruction::Mul, X,
711
5
                                           ConstantInt::get(Ty, Quotient));
712
5
        auto *OBO = cast<OverflowingBinaryOperator>(Op0);
713
5
        Mul->setHasNoUnsignedWrap(!IsSigned && 
OBO->hasNoUnsignedWrap()2
);
714
5
        Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
715
5
        return Mul;
716
5
      }
717
149k
    }
718
149k
719
149k
    if (!C2->isNullValue()) // avoid X udiv 0
720
149k
      if (Instruction *FoldedDiv = foldBinOpIntoSelectOrPhi(I))
721
3
        return FoldedDiv;
722
278k
  }
723
278k
724
278k
  if (match(Op0, m_One())) {
725
11
    assert(!Ty->isIntOrIntVectorTy(1) && "i1 divide not removed?");
726
11
    if (IsSigned) {
727
6
      // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the
728
6
      // result is one, if Op1 is -1 then the result is minus one, otherwise
729
6
      // it's zero.
730
6
      Value *Inc = Builder.CreateAdd(Op1, Op0);
731
6
      Value *Cmp = Builder.CreateICmpULT(Inc, ConstantInt::get(Ty, 3));
732
6
      return SelectInst::Create(Cmp, Op1, ConstantInt::get(Ty, 0));
733
6
    } else {
734
5
      // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
735
5
      // result is one, otherwise it's zero.
736
5
      return new ZExtInst(Builder.CreateICmpEQ(Op1, Op0), Ty);
737
5
    }
738
278k
  }
739
278k
740
278k
  // See if we can fold away this div instruction.
741
278k
  if (SimplifyDemandedInstructionBits(I))
742
63
    return &I;
743
277k
744
277k
  // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
745
277k
  Value *X, *Z;
746
277k
  if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) // (X - Z) / Y; Y = Op1
747
56.9k
    if ((IsSigned && 
match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))54.9k
) ||
748
56.9k
        
(56.9k
!IsSigned56.9k
&&
match(Z, m_URem(m_Specific(X), m_Specific(Op1)))2.03k
))
749
7
      return BinaryOperator::Create(I.getOpcode(), X, Op1);
750
277k
751
277k
  // (X << Y) / X -> 1 << Y
752
277k
  Value *Y;
753
277k
  if (IsSigned && 
match(Op0, m_NSWShl(m_Specific(Op1), m_Value(Y)))156k
)
754
4
    return BinaryOperator::CreateNSWShl(ConstantInt::get(Ty, 1), Y);
755
277k
  if (!IsSigned && 
match(Op0, m_NUWShl(m_Specific(Op1), m_Value(Y)))121k
)
756
4
    return BinaryOperator::CreateNUWShl(ConstantInt::get(Ty, 1), Y);
757
277k
758
277k
  // X / (X * Y) -> 1 / Y if the multiplication does not overflow.
759
277k
  if (match(Op1, m_c_Mul(m_Specific(Op0), m_Value(Y)))) {
760
4
    bool HasNSW = cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap();
761
4
    bool HasNUW = cast<OverflowingBinaryOperator>(Op1)->hasNoUnsignedWrap();
762
4
    if ((IsSigned && 
HasNSW2
) ||
(2
!IsSigned2
&&
HasNUW2
)) {
763
4
      I.setOperand(0, ConstantInt::get(Ty, 1));
764
4
      I.setOperand(1, Y);
765
4
      return &I;
766
4
    }
767
277k
  }
768
277k
769
277k
  return nullptr;
770
277k
}
771
772
static const unsigned MaxDepth = 6;
773
774
namespace {
775
776
using FoldUDivOperandCb = Instruction *(*)(Value *Op0, Value *Op1,
777
                                           const BinaryOperator &I,
778
                                           InstCombiner &IC);
779
780
/// Used to maintain state for visitUDivOperand().
781
struct UDivFoldAction {
782
  /// Informs visitUDiv() how to fold this operand.  This can be zero if this
783
  /// action joins two actions together.
784
  FoldUDivOperandCb FoldAction;
785
786
  /// Which operand to fold.
787
  Value *OperandToFold;
788
789
  union {
790
    /// The instruction returned when FoldAction is invoked.
791
    Instruction *FoldResult;
792
793
    /// Stores the LHS action index if this action joins two actions together.
794
    size_t SelectLHSIdx;
795
  };
796
797
  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand)
798
2.76k
      : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
799
  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
800
13
      : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
801
};
802
803
} // end anonymous namespace
804
805
// X udiv 2^C -> X >> C
806
static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1,
807
2.56k
                                    const BinaryOperator &I, InstCombiner &IC) {
808
2.56k
  Constant *C1 = getLogBase2(Op0->getType(), cast<Constant>(Op1));
809
2.56k
  if (!C1)
810
2.56k
    
llvm_unreachable0
("Failed to constant fold udiv -> logbase2");
811
2.56k
  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, C1);
812
2.56k
  if (I.isExact())
813
0
    LShr->setIsExact();
814
2.56k
  return LShr;
815
2.56k
}
816
817
// X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
818
// X udiv (zext (C1 << N)), where C1 is "1<<C2"  -->  X >> (N+C2)
819
static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I,
820
21
                                InstCombiner &IC) {
821
21
  Value *ShiftLeft;
822
21
  if (!match(Op1, m_ZExt(m_Value(ShiftLeft))))
823
16
    ShiftLeft = Op1;
824
21
825
21
  Constant *CI;
826
21
  Value *N;
827
21
  if (!match(ShiftLeft, m_Shl(m_Constant(CI), m_Value(N))))
828
21
    
llvm_unreachable0
("match should never fail here!");
829
21
  Constant *Log2Base = getLogBase2(N->getType(), CI);
830
21
  if (!Log2Base)
831
21
    
llvm_unreachable0
("getLogBase2 should never fail here!");
832
21
  N = IC.Builder.CreateAdd(N, Log2Base);
833
21
  if (Op1 != ShiftLeft)
834
5
    N = IC.Builder.CreateZExt(N, Op1->getType());
835
21
  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N);
836
21
  if (I.isExact())
837
3
    LShr->setIsExact();
838
21
  return LShr;
839
21
}
840
841
// Recursively visits the possible right hand operands of a udiv
842
// instruction, seeing through select instructions, to determine if we can
843
// replace the udiv with something simpler.  If we find that an operand is not
844
// able to simplify the udiv, we abort the entire transformation.
845
static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I,
846
                               SmallVectorImpl<UDivFoldAction> &Actions,
847
122k
                               unsigned Depth = 0) {
848
122k
  // Check to see if this is an unsigned division with an exact power of 2,
849
122k
  // if so, convert to a right shift.
850
122k
  if (match(Op1, m_Power2())) {
851
2.74k
    Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1));
852
2.74k
    return Actions.size();
853
2.74k
  }
854
119k
855
119k
  // X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
856
119k
  if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
857
119k
      
match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))119k
) {
858
21
    Actions.push_back(UDivFoldAction(foldUDivShl, Op1));
859
21
    return Actions.size();
860
21
  }
861
119k
862
119k
  // The remaining tests are all recursive, so bail out if we hit the limit.
863
119k
  if (Depth++ == MaxDepth)
864
0
    return 0;
865
119k
866
119k
  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
867
637
    if (size_t LHSIdx =
868
191
            visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth))
869
191
      if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) {
870
13
        Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1));
871
13
        return Actions.size();
872
13
      }
873
119k
874
119k
  return 0;
875
119k
}
876
877
/// If we have zero-extended operands of an unsigned div or rem, we may be able
878
/// to narrow the operation (sink the zext below the math).
879
static Instruction *narrowUDivURem(BinaryOperator &I,
880
173k
                                   InstCombiner::BuilderTy &Builder) {
881
173k
  Instruction::BinaryOps Opcode = I.getOpcode();
882
173k
  Value *N = I.getOperand(0);
883
173k
  Value *D = I.getOperand(1);
884
173k
  Type *Ty = I.getType();
885
173k
  Value *X, *Y;
886
173k
  if (match(N, m_ZExt(m_Value(X))) && 
match(D, m_ZExt(m_Value(Y)))5.09k
&&
887
173k
      
X->getType() == Y->getType()40
&&
(39
N->hasOneUse()39
||
D->hasOneUse()8
)) {
888
31
    // udiv (zext X), (zext Y) --> zext (udiv X, Y)
889
31
    // urem (zext X), (zext Y) --> zext (urem X, Y)
890
31
    Value *NarrowOp = Builder.CreateBinOp(Opcode, X, Y);
891
31
    return new ZExtInst(NarrowOp, Ty);
892
31
  }
893
173k
894
173k
  Constant *C;
895
173k
  if ((match(N, m_OneUse(m_ZExt(m_Value(X)))) && 
match(D, m_Constant(C))1.77k
) ||
896
173k
      
(173k
match(D, m_OneUse(m_ZExt(m_Value(X))))173k
&&
match(N, m_Constant(C))1.04k
)) {
897
400
    // If the constant is the same in the smaller type, use the narrow version.
898
400
    Constant *TruncC = ConstantExpr::getTrunc(C, X->getType());
899
400
    if (ConstantExpr::getZExt(TruncC, Ty) != C)
900
329
      return nullptr;
901
71
902
71
    // udiv (zext X), C --> zext (udiv X, C')
903
71
    // urem (zext X), C --> zext (urem X, C')
904
71
    // udiv C, (zext X) --> zext (udiv C', X)
905
71
    // urem C, (zext X) --> zext (urem C', X)
906
71
    Value *NarrowOp = isa<Constant>(D) ? 
Builder.CreateBinOp(Opcode, X, TruncC)69
907
71
                                       : 
Builder.CreateBinOp(Opcode, TruncC, X)2
;
908
71
    return new ZExtInst(NarrowOp, Ty);
909
71
  }
910
173k
911
173k
  return nullptr;
912
173k
}
913
914
121k
Instruction *InstCombiner::visitUDiv(BinaryOperator &I) {
915
121k
  if (Value *V = SimplifyUDivInst(I.getOperand(0), I.getOperand(1),
916
42
                                  SQ.getWithInstruction(&I)))
917
42
    return replaceInstUsesWith(I, V);
918
121k
919
121k
  if (Instruction *X = foldVectorBinop(I))
920
2
    return X;
921
121k
922
121k
  // Handle the integer div common cases
923
121k
  if (Instruction *Common = commonIDivTransforms(I))
924
118
    return Common;
925
121k
926
121k
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
927
121k
  Value *X;
928
121k
  const APInt *C1, *C2;
929
121k
  if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && 
match(Op1, m_APInt(C2))420
) {
930
38
    // (X lshr C1) udiv C2 --> X udiv (C2 << C1)
931
38
    bool Overflow;
932
38
    APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow);
933
38
    if (!Overflow) {
934
38
      bool IsExact = I.isExact() && 
match(Op0, m_Exact(m_Value()))1
;
935
38
      BinaryOperator *BO = BinaryOperator::CreateUDiv(
936
38
          X, ConstantInt::get(X->getType(), C2ShlC1));
937
38
      if (IsExact)
938
1
        BO->setIsExact();
939
38
      return BO;
940
38
    }
941
121k
  }
942
121k
943
121k
  // Op0 / C where C is large (negative) --> zext (Op0 >= C)
944
121k
  // TODO: Could use isKnownNegative() to handle non-constant values.
945
121k
  Type *Ty = I.getType();
946
121k
  if (match(Op1, m_Negative())) {
947
15
    Value *Cmp = Builder.CreateICmpUGE(Op0, Op1);
948
15
    return CastInst::CreateZExtOrBitCast(Cmp, Ty);
949
15
  }
950
121k
  // Op0 / (sext i1 X) --> zext (Op0 == -1) (if X is 0, the div is undefined)
951
121k
  if (match(Op1, m_SExt(m_Value(X))) && 
X->getType()->isIntOrIntVectorTy(1)21.7k
) {
952
2
    Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
953
2
    return CastInst::CreateZExtOrBitCast(Cmp, Ty);
954
2
  }
955
121k
956
121k
  if (Instruction *NarrowDiv = narrowUDivURem(I, Builder))
957
63
    return NarrowDiv;
958
121k
959
121k
  // If the udiv operands are non-overflowing multiplies with a common operand,
960
121k
  // then eliminate the common factor:
961
121k
  // (A * B) / (A * X) --> B / X (and commuted variants)
962
121k
  // TODO: The code would be reduced if we had m_c_NUWMul pattern matching.
963
121k
  // TODO: If -reassociation handled this generally, we could remove this.
964
121k
  Value *A, *B;
965
121k
  if (match(Op0, m_NUWMul(m_Value(A), m_Value(B)))) {
966
145
    if (match(Op1, m_NUWMul(m_Specific(A), m_Value(X))) ||
967
145
        
match(Op1, m_NUWMul(m_Value(X), m_Specific(A)))144
)
968
2
      return BinaryOperator::CreateUDiv(B, X);
969
143
    if (match(Op1, m_NUWMul(m_Specific(B), m_Value(X))) ||
970
143
        
match(Op1, m_NUWMul(m_Value(X), m_Specific(B)))142
)
971
2
      return BinaryOperator::CreateUDiv(A, X);
972
121k
  }
973
121k
974
121k
  // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...))))
975
121k
  SmallVector<UDivFoldAction, 6> UDivActions;
976
121k
  if (visitUDivOperand(Op0, Op1, I, UDivActions))
977
2.60k
    
for (unsigned i = 0, e = UDivActions.size(); 2.57k
i != e;
++i26
) {
978
2.60k
      FoldUDivOperandCb Action = UDivActions[i].FoldAction;
979
2.60k
      Value *ActionOp1 = UDivActions[i].OperandToFold;
980
2.60k
      Instruction *Inst;
981
2.60k
      if (Action)
982
2.59k
        Inst = Action(Op0, ActionOp1, I, *this);
983
13
      else {
984
13
        // This action joins two actions together.  The RHS of this action is
985
13
        // simply the last action we processed, we saved the LHS action index in
986
13
        // the joining action.
987
13
        size_t SelectRHSIdx = i - 1;
988
13
        Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult;
989
13
        size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx;
990
13
        Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult;
991
13
        Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(),
992
13
                                  SelectLHS, SelectRHS);
993
13
      }
994
2.60k
995
2.60k
      // If this is the last action to process, return it to the InstCombiner.
996
2.60k
      // Otherwise, we insert it before the UDiv and record it so that we may
997
2.60k
      // use it as part of a joining action (i.e., a SelectInst).
998
2.60k
      if (e - i != 1) {
999
26
        Inst->insertBefore(&I);
1000
26
        UDivActions[i].FoldResult = Inst;
1001
26
      } else
1002
2.57k
        return Inst;
1003
2.60k
    }
1004
121k
1005
121k
  
return nullptr118k
;
1006
121k
}
1007
1008
156k
Instruction *InstCombiner::visitSDiv(BinaryOperator &I) {
1009
156k
  if (Value *V = SimplifySDivInst(I.getOperand(0), I.getOperand(1),
1010
36
                                  SQ.getWithInstruction(&I)))
1011
36
    return replaceInstUsesWith(I, V);
1012
156k
1013
156k
  if (Instruction *X = foldVectorBinop(I))
1014
2
    return X;
1015
156k
1016
156k
  // Handle the integer div common cases
1017
156k
  if (Instruction *Common = commonIDivTransforms(I))
1018
196
    return Common;
1019
156k
1020
156k
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1021
156k
  Value *X;
1022
156k
  // sdiv Op0, -1 --> -Op0
1023
156k
  // sdiv Op0, (sext i1 X) --> -Op0 (because if X is 0, the op is undefined)
1024
156k
  if (match(Op1, m_AllOnes()) ||
1025
156k
      
(156k
match(Op1, m_SExt(m_Value(X)))156k
&&
X->getType()->isIntOrIntVectorTy(1)2.34k
))
1026
5
    return BinaryOperator::CreateNeg(Op0);
1027
156k
1028
156k
  // X / INT_MIN --> X == INT_MIN
1029
156k
  if (match(Op1, m_SignMask()))
1030
11
    return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), I.getType());
1031
156k
1032
156k
  const APInt *Op1C;
1033
156k
  if (match(Op1, m_APInt(Op1C))) {
1034
88.6k
    // sdiv exact X, C  -->  ashr exact X, log2(C)
1035
88.6k
    if (I.isExact() && 
Op1C->isNonNegative()46.1k
&&
Op1C->isPowerOf2()45.5k
) {
1036
2.52k
      Value *ShAmt = ConstantInt::get(Op1->getType(), Op1C->exactLogBase2());
1037
2.52k
      return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName());
1038
2.52k
    }
1039
86.1k
1040
86.1k
    // If the dividend is sign-extended and the constant divisor is small enough
1041
86.1k
    // to fit in the source type, shrink the division to the narrower type:
1042
86.1k
    // (sext X) sdiv C --> sext (X sdiv C)
1043
86.1k
    Value *Op0Src;
1044
86.1k
    if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) &&
1045
86.1k
        
Op0Src->getType()->getScalarSizeInBits() >= Op1C->getMinSignedBits()44
) {
1046
43
1047
43
      // In the general case, we need to make sure that the dividend is not the
1048
43
      // minimum signed value because dividing that by -1 is UB. But here, we
1049
43
      // know that the -1 divisor case is already handled above.
1050
43
1051
43
      Constant *NarrowDivisor =
1052
43
          ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType());
1053
43
      Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor);
1054
43
      return new SExtInst(NarrowOp, Op0->getType());
1055
43
    }
1056
86.0k
1057
86.0k
    // -X / C --> X / -C (if the negation doesn't overflow).
1058
86.0k
    // TODO: This could be enhanced to handle arbitrary vector constants by
1059
86.0k
    //       checking if all elements are not the min-signed-val.
1060
86.0k
    if (!Op1C->isMinSignedValue() &&
1061
86.0k
        match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) {
1062
9
      Constant *NegC = ConstantInt::get(I.getType(), -(*Op1C));
1063
9
      Instruction *BO = BinaryOperator::CreateSDiv(X, NegC);
1064
9
      BO->setIsExact(I.isExact());
1065
9
      return BO;
1066
9
    }
1067
153k
  }
1068
153k
1069
153k
  // -X / Y --> -(X / Y)
1070
153k
  Value *Y;
1071
153k
  if (match(&I, m_SDiv(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1072
15
    return BinaryOperator::CreateNSWNeg(
1073
15
        Builder.CreateSDiv(X, Y, I.getName(), I.isExact()));
1074
153k
1075
153k
  // If the sign bits of both operands are zero (i.e. we can prove they are
1076
153k
  // unsigned inputs), turn this into a udiv.
1077
153k
  APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits()));
1078
153k
  if (MaskedValueIsZero(Op0, Mask, 0, &I)) {
1079
20.8k
    if (MaskedValueIsZero(Op1, Mask, 0, &I)) {
1080
249
      // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
1081
249
      auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1082
249
      BO->setIsExact(I.isExact());
1083
249
      return BO;
1084
249
    }
1085
20.6k
1086
20.6k
    if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1087
5
      // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1088
5
      // Safe because the only negative value (1 << Y) can take on is
1089
5
      // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1090
5
      // the sign bit set.
1091
5
      auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1092
5
      BO->setIsExact(I.isExact());
1093
5
      return BO;
1094
5
    }
1095
153k
  }
1096
153k
1097
153k
  return nullptr;
1098
153k
}
1099
1100
/// Remove negation and try to convert division into multiplication.
1101
395k
static Instruction *foldFDivConstantDivisor(BinaryOperator &I) {
1102
395k
  Constant *C;
1103
395k
  if (!match(I.getOperand(1), m_Constant(C)))
1104
331k
    return nullptr;
1105
63.5k
1106
63.5k
  // -X / C --> X / -C
1107
63.5k
  Value *X;
1108
63.5k
  if (match(I.getOperand(0), m_FNeg(m_Value(X))))
1109
23
    return BinaryOperator::CreateFDivFMF(X, ConstantExpr::getFNeg(C), &I);
1110
63.5k
1111
63.5k
  // If the constant divisor has an exact inverse, this is always safe. If not,
1112
63.5k
  // then we can still create a reciprocal if fast-math-flags allow it and the
1113
63.5k
  // constant is a regular number (not zero, infinite, or denormal).
1114
63.5k
  if (!(C->hasExactInverseFP() || 
(63.2k
I.hasAllowReciprocal()63.2k
&&
C->isNormalFP()14
)))
1115
63.1k
    return nullptr;
1116
373
1117
373
  // Disallow denormal constants because we don't know what would happen
1118
373
  // on all targets.
1119
373
  // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1120
373
  // denorms are flushed?
1121
373
  auto *RecipC = ConstantExpr::getFDiv(ConstantFP::get(I.getType(), 1.0), C);
1122
373
  if (!RecipC->isNormalFP())
1123
3
    return nullptr;
1124
370
1125
370
  // X / C --> X * (1 / C)
1126
370
  return BinaryOperator::CreateFMulFMF(I.getOperand(0), RecipC, &I);
1127
370
}
1128
1129
/// Remove negation and try to reassociate constant math.
1130
394k
static Instruction *foldFDivConstantDividend(BinaryOperator &I) {
1131
394k
  Constant *C;
1132
394k
  if (!match(I.getOperand(0), m_Constant(C)))
1133
264k
    return nullptr;
1134
129k
1135
129k
  // C / -X --> -C / X
1136
129k
  Value *X;
1137
129k
  if (match(I.getOperand(1), m_FNeg(m_Value(X))))
1138
6
    return BinaryOperator::CreateFDivFMF(ConstantExpr::getFNeg(C), X, &I);
1139
129k
1140
129k
  if (!I.hasAllowReassoc() || 
!I.hasAllowReciprocal()196
)
1141
129k
    return nullptr;
1142
182
1143
182
  // Try to reassociate C / X expressions where X includes another constant.
1144
182
  Constant *C2, *NewC = nullptr;
1145
182
  if (match(I.getOperand(1), m_FMul(m_Value(X), m_Constant(C2)))) {
1146
1
    // C / (X * C2) --> (C / C2) / X
1147
1
    NewC = ConstantExpr::getFDiv(C, C2);
1148
181
  } else if (match(I.getOperand(1), m_FDiv(m_Value(X), m_Constant(C2)))) {
1149
1
    // C / (X / C2) --> (C * C2) / X
1150
1
    NewC = ConstantExpr::getFMul(C, C2);
1151
1
  }
1152
182
  // Disallow denormal constants because we don't know what would happen
1153
182
  // on all targets.
1154
182
  // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1155
182
  // denorms are flushed?
1156
182
  if (!NewC || 
!NewC->isNormalFP()2
)
1157
180
    return nullptr;
1158
2
1159
2
  return BinaryOperator::CreateFDivFMF(NewC, X, &I);
1160
2
}
1161
1162
395k
Instruction *InstCombiner::visitFDiv(BinaryOperator &I) {
1163
395k
  if (Value *V = SimplifyFDivInst(I.getOperand(0), I.getOperand(1),
1164
7
                                  I.getFastMathFlags(),
1165
7
                                  SQ.getWithInstruction(&I)))
1166
7
    return replaceInstUsesWith(I, V);
1167
395k
1168
395k
  if (Instruction *X = foldVectorBinop(I))
1169
9
    return X;
1170
395k
1171
395k
  if (Instruction *R = foldFDivConstantDivisor(I))
1172
393
    return R;
1173
394k
1174
394k
  if (Instruction *R = foldFDivConstantDividend(I))
1175
8
    return R;
1176
394k
1177
394k
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1178
394k
  if (isa<Constant>(Op0))
1179
129k
    if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1180
798
      if (Instruction *R = FoldOpIntoSelect(I, SI))
1181
7
        return R;
1182
394k
1183
394k
  if (isa<Constant>(Op1))
1184
63.1k
    if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1185
22
      if (Instruction *R = FoldOpIntoSelect(I, SI))
1186
2
        return R;
1187
394k
1188
394k
  if (I.hasAllowReassoc() && 
I.hasAllowReciprocal()454
) {
1189
391
    Value *X, *Y;
1190
391
    if (match(Op0, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1191
391
        
(2
!isa<Constant>(Y)2
||
!isa<Constant>(Op1)0
)) {
1192
2
      // (X / Y) / Z => X / (Y * Z)
1193
2
      Value *YZ = Builder.CreateFMulFMF(Y, Op1, &I);
1194
2
      return BinaryOperator::CreateFDivFMF(X, YZ, &I);
1195
2
    }
1196
389
    if (match(Op1, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1197
389
        
(2
!isa<Constant>(Y)2
||
!isa<Constant>(Op0)0
)) {
1198
2
      // Z / (X / Y) => (Y * Z) / X
1199
2
      Value *YZ = Builder.CreateFMulFMF(Y, Op0, &I);
1200
2
      return BinaryOperator::CreateFDivFMF(YZ, X, &I);
1201
2
    }
1202
394k
  }
1203
394k
1204
394k
  if (I.hasAllowReassoc() && 
Op0->hasOneUse()450
&&
Op1->hasOneUse()267
) {
1205
100
    // sin(X) / cos(X) -> tan(X)
1206
100
    // cos(X) / sin(X) -> 1/tan(X) (cotangent)
1207
100
    Value *X;
1208
100
    bool IsTan = match(Op0, m_Intrinsic<Intrinsic::sin>(m_Value(X))) &&
1209
100
                 
match(Op1, m_Intrinsic<Intrinsic::cos>(m_Specific(X)))5
;
1210
100
    bool IsCot =
1211
100
        !IsTan && 
match(Op0, m_Intrinsic<Intrinsic::cos>(m_Value(X)))95
&&
1212
100
                  
match(Op1, m_Intrinsic<Intrinsic::sin>(m_Specific(X)))6
;
1213
100
1214
100
    if ((IsTan || 
IsCot95
) && hasUnaryFloatFn(&TLI, I.getType(), LibFunc_tan,
1215
11
                                            LibFunc_tanf, LibFunc_tanl)) {
1216
10
      IRBuilder<> B(&I);
1217
10
      IRBuilder<>::FastMathFlagGuard FMFGuard(B);
1218
10
      B.setFastMathFlags(I.getFastMathFlags());
1219
10
      AttributeList Attrs =
1220
10
          cast<CallBase>(Op0)->getCalledFunction()->getAttributes();
1221
10
      Value *Res = emitUnaryFloatFnCall(X, &TLI, LibFunc_tan, LibFunc_tanf,
1222
10
                                        LibFunc_tanl, B, Attrs);
1223
10
      if (IsCot)
1224
5
        Res = B.CreateFDiv(ConstantFP::get(I.getType(), 1.0), Res);
1225
10
      return replaceInstUsesWith(I, Res);
1226
10
    }
1227
394k
  }
1228
394k
1229
394k
  // -X / -Y -> X / Y
1230
394k
  Value *X, *Y;
1231
394k
  if (match(Op0, m_FNeg(m_Value(X))) && 
match(Op1, m_FNeg(m_Value(Y)))2.47k
) {
1232
11
    I.setOperand(0, X);
1233
11
    I.setOperand(1, Y);
1234
11
    return &I;
1235
11
  }
1236
394k
1237
394k
  // X / (X * Y) --> 1.0 / Y
1238
394k
  // Reassociate to (X / X -> 1.0) is legal when NaNs are not allowed.
1239
394k
  // We can ignore the possibility that X is infinity because INF/INF is NaN.
1240
394k
  if (I.hasNoNaNs() && 
I.hasAllowReassoc()422
&&
1241
394k
      
match(Op1, m_c_FMul(m_Specific(Op0), m_Value(Y)))385
) {
1242
2
    I.setOperand(0, ConstantFP::get(I.getType(), 1.0));
1243
2
    I.setOperand(1, Y);
1244
2
    return &I;
1245
2
  }
1246
394k
1247
394k
  return nullptr;
1248
394k
}
1249
1250
/// This function implements the transforms common to both integer remainder
1251
/// instructions (urem and srem). It is called by the visitors to those integer
1252
/// remainder instructions.
1253
/// Common integer remainder transforms
1254
93.9k
Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) {
1255
93.9k
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1256
93.9k
1257
93.9k
  // The RHS is known non-zero.
1258
93.9k
  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
1259
30
    I.setOperand(1, V);
1260
30
    return &I;
1261
30
  }
1262
93.8k
1263
93.8k
  // Handle cases involving: rem X, (select Cond, Y, Z)
1264
93.8k
  if (simplifyDivRemOfSelectWithZeroOp(I))
1265
3
    return &I;
1266
93.8k
1267
93.8k
  if (isa<Constant>(Op1)) {
1268
48.3k
    if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1269
46.2k
      if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
1270
384
        if (Instruction *R = FoldOpIntoSelect(I, SI))
1271
4
          return R;
1272
45.8k
      } else if (auto *PN = dyn_cast<PHINode>(Op0I)) {
1273
3.89k
        const APInt *Op1Int;
1274
3.89k
        if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() &&
1275
3.89k
            (I.getOpcode() == Instruction::URem ||
1276
3.89k
             
!Op1Int->isMinSignedValue()1.29k
)) {
1277
3.89k
          // foldOpIntoPhi will speculate instructions to the end of the PHI's
1278
3.89k
          // predecessor blocks, so do this only if we know the srem or urem
1279
3.89k
          // will not fault.
1280
3.89k
          if (Instruction *NV = foldOpIntoPhi(I, PN))
1281
9
            return NV;
1282
46.2k
        }
1283
3.89k
      }
1284
46.2k
1285
46.2k
      // See if we can fold away this rem instruction.
1286
46.2k
      if (SimplifyDemandedInstructionBits(I))
1287
2
        return &I;
1288
93.8k
    }
1289
48.3k
  }
1290
93.8k
1291
93.8k
  return nullptr;
1292
93.8k
}
1293
1294
52.5k
Instruction *InstCombiner::visitURem(BinaryOperator &I) {
1295
52.5k
  if (Value *V = SimplifyURemInst(I.getOperand(0), I.getOperand(1),
1296
27
                                  SQ.getWithInstruction(&I)))
1297
27
    return replaceInstUsesWith(I, V);
1298
52.4k
1299
52.4k
  if (Instruction *X = foldVectorBinop(I))
1300
2
    return X;
1301
52.4k
1302
52.4k
  if (Instruction *common = commonIRemTransforms(I))
1303
36
    return common;
1304
52.4k
1305
52.4k
  if (Instruction *NarrowRem = narrowUDivURem(I, Builder))
1306
39
    return NarrowRem;
1307
52.4k
1308
52.4k
  // X urem Y -> X and Y-1, where Y is a power of 2,
1309
52.4k
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1310
52.4k
  Type *Ty = I.getType();
1311
52.4k
  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1312
7.84k
    Constant *N1 = Constant::getAllOnesValue(Ty);
1313
7.84k
    Value *Add = Builder.CreateAdd(Op1, N1);
1314
7.84k
    return BinaryOperator::CreateAnd(Op0, Add);
1315
7.84k
  }
1316
44.5k
1317
44.5k
  // 1 urem X -> zext(X != 1)
1318
44.5k
  if (match(Op0, m_One()))
1319
3
    return CastInst::CreateZExtOrBitCast(Builder.CreateICmpNE(Op1, Op0), Ty);
1320
44.5k
1321
44.5k
  // X urem C -> X < C ? X : X - C, where C >= signbit.
1322
44.5k
  if (match(Op1, m_Negative())) {
1323
6
    Value *Cmp = Builder.CreateICmpULT(Op0, Op1);
1324
6
    Value *Sub = Builder.CreateSub(Op0, Op1);
1325
6
    return SelectInst::Create(Cmp, Op0, Sub);
1326
6
  }
1327
44.5k
1328
44.5k
  // If the divisor is a sext of a boolean, then the divisor must be max
1329
44.5k
  // unsigned value (-1). Therefore, the remainder is Op0 unless Op0 is also
1330
44.5k
  // max unsigned value. In that case, the remainder is 0:
1331
44.5k
  // urem Op0, (sext i1 X) --> (Op0 == -1) ? 0 : Op0
1332
44.5k
  Value *X;
1333
44.5k
  if (match(Op1, m_SExt(m_Value(X))) && 
X->getType()->isIntOrIntVectorTy(1)273
) {
1334
2
    Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
1335
2
    return SelectInst::Create(Cmp, ConstantInt::getNullValue(Ty), Op0);
1336
2
  }
1337
44.5k
1338
44.5k
  return nullptr;
1339
44.5k
}
1340
1341
41.4k
Instruction *InstCombiner::visitSRem(BinaryOperator &I) {
1342
41.4k
  if (Value *V = SimplifySRemInst(I.getOperand(0), I.getOperand(1),
1343
9
                                  SQ.getWithInstruction(&I)))
1344
9
    return replaceInstUsesWith(I, V);
1345
41.4k
1346
41.4k
  if (Instruction *X = foldVectorBinop(I))
1347
2
    return X;
1348
41.4k
1349
41.4k
  // Handle the integer rem common cases
1350
41.4k
  if (Instruction *Common = commonIRemTransforms(I))
1351
12
    return Common;
1352
41.4k
1353
41.4k
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1354
41.4k
  {
1355
41.4k
    const APInt *Y;
1356
41.4k
    // X % -Y -> X % Y
1357
41.4k
    if (match(Op1, m_Negative(Y)) && 
!Y->isMinSignedValue()7
) {
1358
2
      Worklist.AddValue(I.getOperand(1));
1359
2
      I.setOperand(1, ConstantInt::get(I.getType(), -*Y));
1360
2
      return &I;
1361
2
    }
1362
41.4k
  }
1363
41.4k
1364
41.4k
  // -X srem Y --> -(X srem Y)
1365
41.4k
  Value *X, *Y;
1366
41.4k
  if (match(&I, m_SRem(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1367
2
    return BinaryOperator::CreateNSWNeg(Builder.CreateSRem(X, Y)); 
1368
41.4k
1369
41.4k
  // If the sign bits of both operands are zero (i.e. we can prove they are
1370
41.4k
  // unsigned inputs), turn this into a urem.
1371
41.4k
  APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits()));
1372
41.4k
  if (MaskedValueIsZero(Op1, Mask, 0, &I) &&
1373
41.4k
      
MaskedValueIsZero(Op0, Mask, 0, &I)35.4k
) {
1374
241
    // X srem Y -> X urem Y, iff X and Y don't have sign bit set
1375
241
    return BinaryOperator::CreateURem(Op0, Op1, I.getName());
1376
241
  }
1377
41.1k
1378
41.1k
  // If it's a constant vector, flip any negative values positive.
1379
41.1k
  if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) {
1380
16
    Constant *C = cast<Constant>(Op1);
1381
16
    unsigned VWidth = C->getType()->getVectorNumElements();
1382
16
1383
16
    bool hasNegative = false;
1384
16
    bool hasMissing = false;
1385
49
    for (unsigned i = 0; i != VWidth; 
++i33
) {
1386
33
      Constant *Elt = C->getAggregateElement(i);
1387
33
      if (!Elt) {
1388
0
        hasMissing = true;
1389
0
        break;
1390
0
      }
1391
33
1392
33
      if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt))
1393
33
        if (RHS->isNegative())
1394
5
          hasNegative = true;
1395
33
    }
1396
16
1397
16
    if (hasNegative && 
!hasMissing4
) {
1398
4
      SmallVector<Constant *, 16> Elts(VWidth);
1399
12
      for (unsigned i = 0; i != VWidth; 
++i8
) {
1400
8
        Elts[i] = C->getAggregateElement(i);  // Handle undef, etc.
1401
8
        if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) {
1402
8
          if (RHS->isNegative())
1403
5
            Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
1404
8
        }
1405
8
      }
1406
4
1407
4
      Constant *NewRHSV = ConstantVector::get(Elts);
1408
4
      if (NewRHSV != C) {  // Don't loop on -MININT
1409
3
        Worklist.AddValue(I.getOperand(1));
1410
3
        I.setOperand(1, NewRHSV);
1411
3
        return &I;
1412
3
      }
1413
41.1k
    }
1414
16
  }
1415
41.1k
1416
41.1k
  return nullptr;
1417
41.1k
}
1418
1419
481
Instruction *InstCombiner::visitFRem(BinaryOperator &I) {
1420
481
  if (Value *V = SimplifyFRemInst(I.getOperand(0), I.getOperand(1),
1421
0
                                  I.getFastMathFlags(),
1422
0
                                  SQ.getWithInstruction(&I)))
1423
0
    return replaceInstUsesWith(I, V);
1424
481
1425
481
  if (Instruction *X = foldVectorBinop(I))
1426
3
    return X;
1427
478
1428
478
  return nullptr;
1429
478
}