Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- InstCombineAddSub.cpp ------------------------------------*- C++ -*-===//
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 add, fadd, sub, and fsub.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "InstCombineInternal.h"
14
#include "llvm/ADT/APFloat.h"
15
#include "llvm/ADT/APInt.h"
16
#include "llvm/ADT/STLExtras.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/Analysis/InstructionSimplify.h"
19
#include "llvm/Analysis/ValueTracking.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/Operator.h"
26
#include "llvm/IR/PatternMatch.h"
27
#include "llvm/IR/Type.h"
28
#include "llvm/IR/Value.h"
29
#include "llvm/Support/AlignOf.h"
30
#include "llvm/Support/Casting.h"
31
#include "llvm/Support/KnownBits.h"
32
#include <cassert>
33
#include <utility>
34
35
using namespace llvm;
36
using namespace PatternMatch;
37
38
#define DEBUG_TYPE "instcombine"
39
40
namespace {
41
42
  /// Class representing coefficient of floating-point addend.
43
  /// This class needs to be highly efficient, which is especially true for
44
  /// the constructor. As of I write this comment, the cost of the default
45
  /// constructor is merely 4-byte-store-zero (Assuming compiler is able to
46
  /// perform write-merging).
47
  ///
48
  class FAddendCoef {
49
  public:
50
    // The constructor has to initialize a APFloat, which is unnecessary for
51
    // most addends which have coefficient either 1 or -1. So, the constructor
52
    // is expensive. In order to avoid the cost of the constructor, we should
53
    // reuse some instances whenever possible. The pre-created instances
54
    // FAddCombine::Add[0-5] embodies this idea.
55
16.8k
    FAddendCoef() = default;
56
    ~FAddendCoef();
57
58
    // If possible, don't define operator+/operator- etc because these
59
    // operators inevitably call FAddendCoef's constructor which is not cheap.
60
    void operator=(const FAddendCoef &A);
61
    void operator+=(const FAddendCoef &A);
62
    void operator*=(const FAddendCoef &S);
63
64
5.33k
    void set(short C) {
65
5.33k
      assert(!insaneIntVal(C) && "Insane coefficient");
66
5.33k
      IsFp = false; IntVal = C;
67
5.33k
    }
68
69
    void set(const APFloat& C);
70
71
    void negate();
72
73
28
    bool isZero() const { return isInt() ? 
!IntVal17
:
getFpVal().isZero()11
; }
74
    Value *getValue(Type *) const;
75
76
2.98k
    bool isOne() const { return isInt() && 
IntVal == 12.67k
; }
77
20
    bool isTwo() const { return isInt() && 
IntVal == 29
; }
78
4.32k
    bool isMinusOne() const { return isInt() && 
IntVal == -13.71k
; }
79
1.98k
    bool isMinusTwo() const { return isInt() && 
IntVal == -21.67k
; }
80
81
  private:
82
0
    bool insaneIntVal(int V) { return V > 4 || V < -4; }
83
84
    APFloat *getFpValPtr()
85
1.52k
      { return reinterpret_cast<APFloat *>(&FpValBuf.buffer[0]); }
86
87
    const APFloat *getFpValPtr() const
88
55
      { return reinterpret_cast<const APFloat *>(&FpValBuf.buffer[0]); }
89
90
55
    const APFloat &getFpVal() const {
91
55
      assert(IsFp && BufHasFpVal && "Incorret state");
92
55
      return *getFpValPtr();
93
55
    }
94
95
59
    APFloat &getFpVal() {
96
59
      assert(IsFp && BufHasFpVal && "Incorret state");
97
59
      return *getFpValPtr();
98
59
    }
99
100
11.0k
    bool isInt() const { return !IsFp; }
101
102
    // If the coefficient is represented by an integer, promote it to a
103
    // floating point.
104
    void convertToFpType(const fltSemantics &Sem);
105
106
    // Construct an APFloat from a signed integer.
107
    // TODO: We should get rid of this function when APFloat can be constructed
108
    //       from an *SIGNED* integer.
109
    APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val);
110
111
    bool IsFp = false;
112
113
    // True iff FpValBuf contains an instance of APFloat.
114
    bool BufHasFpVal = false;
115
116
    // The integer coefficient of an individual addend is either 1 or -1,
117
    // and we try to simplify at most 4 addends from neighboring at most
118
    // two instructions. So the range of <IntVal> falls in [-4, 4]. APInt
119
    // is overkill of this end.
120
    short IntVal = 0;
121
122
    AlignedCharArrayUnion<APFloat> FpValBuf;
123
  };
124
125
  /// FAddend is used to represent floating-point addend. An addend is
126
  /// represented as <C, V>, where the V is a symbolic value, and C is a
127
  /// constant coefficient. A constant addend is represented as <C, 0>.
128
  class FAddend {
129
  public:
130
16.8k
    FAddend() = default;
131
132
46
    void operator+=(const FAddend &T) {
133
46
      assert((Val == T.Val) && "Symbolic-values disagree");
134
46
      Coeff += T.Coeff;
135
46
    }
136
137
6.59k
    Value *getSymVal() const { return Val; }
138
2.24k
    const FAddendCoef &getCoef() const { return Coeff; }
139
140
11.2k
    bool isConstant() const { return Val == nullptr; }
141
28
    bool isZero() const { return Coeff.isZero(); }
142
143
5.31k
    void set(short Coefficient, Value *V) {
144
5.31k
      Coeff.set(Coefficient);
145
5.31k
      Val = V;
146
5.31k
    }
147
0
    void set(const APFloat &Coefficient, Value *V) {
148
0
      Coeff.set(Coefficient);
149
0
      Val = V;
150
0
    }
151
715
    void set(const ConstantFP *Coefficient, Value *V) {
152
715
      Coeff.set(Coefficient->getValueAPF());
153
715
      Val = V;
154
715
    }
155
156
722
    void negate() { Coeff.negate(); }
157
158
    /// Drill down the U-D chain one step to find the definition of V, and
159
    /// try to break the definition into one or two addends.
160
    static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1);
161
162
    /// Similar to FAddend::drillDownOneStep() except that the value being
163
    /// splitted is the addend itself.
164
    unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const;
165
166
  private:
167
82
    void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; }
168
169
    // This addend has the value of "Coeff * Val".
170
    Value *Val = nullptr;
171
    FAddendCoef Coeff;
172
  };
173
174
  /// FAddCombine is the class for optimizing an unsafe fadd/fsub along
175
  /// with its neighboring at most two instructions.
176
  ///
177
  class FAddCombine {
178
  public:
179
2.86k
    FAddCombine(InstCombiner::BuilderTy &B) : Builder(B) {}
180
181
    Value *simplify(Instruction *FAdd);
182
183
  private:
184
    using AddendVect = SmallVector<const FAddend *, 4>;
185
186
    Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota);
187
188
    /// Convert given addend to a Value
189
    Value *createAddendVal(const FAddend &A, bool& NeedNeg);
190
191
    /// Return the number of instructions needed to emit the N-ary addition.
192
    unsigned calcInstrNumber(const AddendVect& Vect);
193
194
    Value *createFSub(Value *Opnd0, Value *Opnd1);
195
    Value *createFAdd(Value *Opnd0, Value *Opnd1);
196
    Value *createFMul(Value *Opnd0, Value *Opnd1);
197
    Value *createFNeg(Value *V);
198
    Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota);
199
    void createInstPostProc(Instruction *NewInst, bool NoNumber = false);
200
201
     // Debugging stuff are clustered here.
202
    #ifndef NDEBUG
203
      unsigned CreateInstrNum;
204
      void initCreateInstNum() { CreateInstrNum = 0; }
205
      void incCreateInstNum() { CreateInstrNum++; }
206
    #else
207
25
      void initCreateInstNum() {}
208
31
      void incCreateInstNum() {}
209
    #endif
210
211
    InstCombiner::BuilderTy &Builder;
212
    Instruction *Instr = nullptr;
213
  };
214
215
} // end anonymous namespace
216
217
//===----------------------------------------------------------------------===//
218
//
219
// Implementation of
220
//    {FAddendCoef, FAddend, FAddition, FAddCombine}.
221
//
222
//===----------------------------------------------------------------------===//
223
16.8k
FAddendCoef::~FAddendCoef() {
224
16.8k
  if (BufHasFpVal)
225
733
    getFpValPtr()->~APFloat();
226
16.8k
}
227
228
726
void FAddendCoef::set(const APFloat& C) {
229
726
  APFloat *P = getFpValPtr();
230
726
231
726
  if (isInt()) {
232
726
    // As the buffer is meanless byte stream, we cannot call
233
726
    // APFloat::operator=().
234
726
    new(P) APFloat(C);
235
726
  } else
236
0
    *P = C;
237
726
238
726
  IsFp = BufHasFpVal = true;
239
726
}
240
241
7
void FAddendCoef::convertToFpType(const fltSemantics &Sem) {
242
7
  if (!isInt())
243
0
    return;
244
7
245
7
  APFloat *P = getFpValPtr();
246
7
  if (IntVal > 0)
247
7
    new(P) APFloat(Sem, IntVal);
248
0
  else {
249
0
    new(P) APFloat(Sem, 0 - IntVal);
250
0
    P->changeSign();
251
0
  }
252
7
  IsFp = BufHasFpVal = true;
253
7
}
254
255
4
APFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) {
256
4
  if (Val >= 0)
257
4
    return APFloat(Sem, Val);
258
0
259
0
  APFloat T(Sem, 0 - Val);
260
0
  T.changeSign();
261
0
262
0
  return T;
263
0
}
264
265
35
void FAddendCoef::operator=(const FAddendCoef &That) {
266
35
  if (That.isInt())
267
24
    set(That.IntVal);
268
11
  else
269
11
    set(That.getFpVal());
270
35
}
271
272
46
void FAddendCoef::operator+=(const FAddendCoef &That) {
273
46
  enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven;
274
46
  if (isInt() == That.isInt()) {
275
35
    if (isInt())
276
26
      IntVal += That.IntVal;
277
9
    else
278
9
      getFpVal().add(That.getFpVal(), RndMode);
279
35
    return;
280
35
  }
281
11
282
11
  if (isInt()) {
283
7
    const APFloat &T = That.getFpVal();
284
7
    convertToFpType(T.getSemantics());
285
7
    getFpVal().add(T, RndMode);
286
7
    return;
287
7
  }
288
4
289
4
  APFloat &T = getFpVal();
290
4
  T.add(createAPFloatFromInt(T.getSemantics(), That.IntVal), RndMode);
291
4
}
292
293
82
void FAddendCoef::operator*=(const FAddendCoef &That) {
294
82
  if (That.isOne())
295
0
    return;
296
82
297
82
  if (That.isMinusOne()) {
298
82
    negate();
299
82
    return;
300
82
  }
301
0
302
0
  if (isInt() && That.isInt()) {
303
0
    int Res = IntVal * (int)That.IntVal;
304
0
    assert(!insaneIntVal(Res) && "Insane int value");
305
0
    IntVal = Res;
306
0
    return;
307
0
  }
308
0
309
0
  const fltSemantics &Semantic =
310
0
    isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics();
311
0
312
0
  if (isInt())
313
0
    convertToFpType(Semantic);
314
0
  APFloat &F0 = getFpVal();
315
0
316
0
  if (That.isInt())
317
0
    F0.multiply(createAPFloatFromInt(Semantic, That.IntVal),
318
0
                APFloat::rmNearestTiesToEven);
319
0
  else
320
0
    F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven);
321
0
}
322
323
804
void FAddendCoef::negate() {
324
804
  if (isInt())
325
765
    IntVal = 0 - IntVal;
326
39
  else
327
39
    getFpVal().changeSign();
328
804
}
329
330
24
Value *FAddendCoef::getValue(Type *Ty) const {
331
24
  return isInt() ?
332
7
    ConstantFP::get(Ty, float(IntVal)) :
333
24
    
ConstantFP::get(Ty->getContext(), getFpVal())17
;
334
24
}
335
336
// The definition of <Val>     Addends
337
// =========================================
338
//  A + B                     <1, A>, <1,B>
339
//  A - B                     <1, A>, <1,B>
340
//  0 - B                     <-1, B>
341
//  C * A,                    <C, A>
342
//  A + C                     <1, A> <C, NULL>
343
//  0 +/- 0                   <0, NULL> (corner case)
344
//
345
// Legend: A and B are not constant, C is constant
346
unsigned FAddend::drillValueDownOneStep
347
6.60k
  (Value *Val, FAddend &Addend0, FAddend &Addend1) {
348
6.60k
  Instruction *I = nullptr;
349
6.60k
  if (!Val || !(I = dyn_cast<Instruction>(Val)))
350
703
    return 0;
351
5.89k
352
5.89k
  unsigned Opcode = I->getOpcode();
353
5.89k
354
5.89k
  if (Opcode == Instruction::FAdd || 
Opcode == Instruction::FSub3.66k
) {
355
2.95k
    ConstantFP *C0, *C1;
356
2.95k
    Value *Opnd0 = I->getOperand(0);
357
2.95k
    Value *Opnd1 = I->getOperand(1);
358
2.95k
    if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && 
C0->isZero()146
)
359
113
      Opnd0 = nullptr;
360
2.95k
361
2.95k
    if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && 
C1->isZero()457
)
362
0
      Opnd1 = nullptr;
363
2.95k
364
2.95k
    if (Opnd0) {
365
2.84k
      if (!C0)
366
2.81k
        Addend0.set(1, Opnd0);
367
33
      else
368
33
        Addend0.set(C0, nullptr);
369
2.84k
    }
370
2.95k
371
2.95k
    if (Opnd1) {
372
2.95k
      FAddend &Addend = Opnd0 ? 
Addend12.84k
:
Addend0113
;
373
2.95k
      if (!C1)
374
2.50k
        Addend.set(1, Opnd1);
375
457
      else
376
457
        Addend.set(C1, nullptr);
377
2.95k
      if (Opcode == Instruction::FSub)
378
722
        Addend.negate();
379
2.95k
    }
380
2.95k
381
2.95k
    if (Opnd0 || 
Opnd1113
)
382
2.95k
      return Opnd0 && 
Opnd12.84k
?
22.84k
:
1113
;
383
0
384
0
    // Both operands are zero. Weird!
385
0
    Addend0.set(APFloat(C0->getValueAPF().getSemantics()), nullptr);
386
0
    return 1;
387
0
  }
388
2.94k
389
2.94k
  if (I->getOpcode() == Instruction::FMul) {
390
1.17k
    Value *V0 = I->getOperand(0);
391
1.17k
    Value *V1 = I->getOperand(1);
392
1.17k
    if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) {
393
1
      Addend0.set(C, V1);
394
1
      return 1;
395
1
    }
396
1.17k
397
1.17k
    if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) {
398
224
      Addend0.set(C, V0);
399
224
      return 1;
400
224
    }
401
2.71k
  }
402
2.71k
403
2.71k
  return 0;
404
2.71k
}
405
406
// Try to break *this* addend into two addends. e.g. Suppose this addend is
407
// <2.3, V>, and V = X + Y, by calling this function, we obtain two addends,
408
// i.e. <2.3, X> and <2.3, Y>.
409
unsigned FAddend::drillAddendDownOneStep
410
4.23k
  (FAddend &Addend0, FAddend &Addend1) const {
411
4.23k
  if (isConstant())
412
0
    return 0;
413
4.23k
414
4.23k
  unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1);
415
4.23k
  if (!BreakNum || 
Coeff.isOne()812
)
416
4.17k
    return BreakNum;
417
54
418
54
  Addend0.Scale(Coeff);
419
54
420
54
  if (BreakNum == 2)
421
28
    Addend1.Scale(Coeff);
422
54
423
54
  return BreakNum;
424
54
}
425
426
2.86k
Value *FAddCombine::simplify(Instruction *I) {
427
2.86k
  assert(I->hasAllowReassoc() && I->hasNoSignedZeros() &&
428
2.86k
         "Expected 'reassoc'+'nsz' instruction");
429
2.86k
430
2.86k
  // Currently we are not able to handle vector type.
431
2.86k
  if (I->getType()->isVectorTy())
432
492
    return nullptr;
433
2.37k
434
2.37k
  assert((I->getOpcode() == Instruction::FAdd ||
435
2.37k
          I->getOpcode() == Instruction::FSub) && "Expect add/sub");
436
2.37k
437
2.37k
  // Save the instruction before calling other member-functions.
438
2.37k
  Instr = I;
439
2.37k
440
2.37k
  FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1;
441
2.37k
442
2.37k
  unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1);
443
2.37k
444
2.37k
  // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1.
445
2.37k
  unsigned Opnd0_ExpNum = 0;
446
2.37k
  unsigned Opnd1_ExpNum = 0;
447
2.37k
448
2.37k
  if (!Opnd0.isConstant())
449
2.34k
    Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1);
450
2.37k
451
2.37k
  // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1.
452
2.37k
  if (OpndNum == 2 && 
!Opnd1.isConstant()2.26k
)
453
1.88k
    Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1);
454
2.37k
455
2.37k
  // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1
456
2.37k
  if (Opnd0_ExpNum && 
Opnd1_ExpNum679
) {
457
80
    AddendVect AllOpnds;
458
80
    AllOpnds.push_back(&Opnd0_0);
459
80
    AllOpnds.push_back(&Opnd1_0);
460
80
    if (Opnd0_ExpNum == 2)
461
48
      AllOpnds.push_back(&Opnd0_1);
462
80
    if (Opnd1_ExpNum == 2)
463
30
      AllOpnds.push_back(&Opnd1_1);
464
80
465
80
    // Compute instruction quota. We should save at least one instruction.
466
80
    unsigned InstQuota = 0;
467
80
468
80
    Value *V0 = I->getOperand(0);
469
80
    Value *V1 = I->getOperand(1);
470
80
    InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) &&
471
80
                 
(63
!isa<Constant>(V1)63
&&
V1->hasOneUse()63
)) ?
262
:
118
;
472
80
473
80
    if (Value *R = simplifyFAdd(AllOpnds, InstQuota))
474
12
      return R;
475
2.35k
  }
476
2.35k
477
2.35k
  if (OpndNum != 2) {
478
108
    // The input instruction is : "I=0.0 +/- V". If the "V" were able to be
479
108
    // splitted into two addends, say "V = X - Y", the instruction would have
480
108
    // been optimized into "I = Y - X" in the previous steps.
481
108
    //
482
108
    const FAddendCoef &CE = Opnd0.getCoef();
483
108
    return CE.isOne() ? 
Opnd0.getSymVal()0
: nullptr;
484
108
  }
485
2.25k
486
2.25k
  // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1]
487
2.25k
  if (Opnd1_ExpNum) {
488
121
    AddendVect AllOpnds;
489
121
    AllOpnds.push_back(&Opnd0);
490
121
    AllOpnds.push_back(&Opnd1_0);
491
121
    if (Opnd1_ExpNum == 2)
492
47
      AllOpnds.push_back(&Opnd1_1);
493
121
494
121
    if (Value *R = simplifyFAdd(AllOpnds, 1))
495
0
      return R;
496
2.25k
  }
497
2.25k
498
2.25k
  // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1]
499
2.25k
  if (Opnd0_ExpNum) {
500
665
    AddendVect AllOpnds;
501
665
    AllOpnds.push_back(&Opnd1);
502
665
    AllOpnds.push_back(&Opnd0_0);
503
665
    if (Opnd0_ExpNum == 2)
504
515
      AllOpnds.push_back(&Opnd0_1);
505
665
506
665
    if (Value *R = simplifyFAdd(AllOpnds, 1))
507
13
      return R;
508
2.23k
  }
509
2.23k
510
2.23k
  return nullptr;
511
2.23k
}
512
513
866
Value *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) {
514
866
  unsigned AddendNum = Addends.size();
515
866
  assert(AddendNum <= 4 && "Too many addends");
516
866
517
866
  // For saving intermediate results;
518
866
  unsigned NextTmpIdx = 0;
519
866
  FAddend TmpResult[3];
520
866
521
866
  // Points to the constant addend of the resulting simplified expression.
522
866
  // If the resulting expr has constant-addend, this constant-addend is
523
866
  // desirable to reside at the top of the resulting expression tree. Placing
524
866
  // constant close to supper-expr(s) will potentially reveal some optimization
525
866
  // opportunities in super-expr(s).
526
866
  const FAddend *ConstAdd = nullptr;
527
866
528
866
  // Simplified addends are placed <SimpVect>.
529
866
  AddendVect SimpVect;
530
866
531
866
  // The outer loop works on one symbolic-value at a time. Suppose the input
532
866
  // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ...
533
866
  // The symbolic-values will be processed in this order: x, y, z.
534
3.23k
  for (unsigned SymIdx = 0; SymIdx < AddendNum; 
SymIdx++2.37k
) {
535
2.37k
536
2.37k
    const FAddend *ThisAddend = Addends[SymIdx];
537
2.37k
    if (!ThisAddend) {
538
46
      // This addend was processed before.
539
46
      continue;
540
46
    }
541
2.32k
542
2.32k
    Value *Val = ThisAddend->getSymVal();
543
2.32k
    unsigned StartIdx = SimpVect.size();
544
2.32k
    SimpVect.push_back(ThisAddend);
545
2.32k
546
2.32k
    // The inner loop collects addends sharing same symbolic-value, and these
547
2.32k
    // addends will be later on folded into a single addend. Following above
548
2.32k
    // example, if the symbolic value "y" is being processed, the inner loop
549
2.32k
    // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will
550
2.32k
    // be later on folded into "<b1+b2, y>".
551
2.32k
    for (unsigned SameSymIdx = SymIdx + 1;
552
4.46k
         SameSymIdx < AddendNum; 
SameSymIdx++2.14k
) {
553
2.14k
      const FAddend *T = Addends[SameSymIdx];
554
2.14k
      if (T && 
T->getSymVal() == Val2.13k
) {
555
46
        // Set null such that next iteration of the outer loop will not process
556
46
        // this addend again.
557
46
        Addends[SameSymIdx] = nullptr;
558
46
        SimpVect.push_back(T);
559
46
      }
560
2.14k
    }
561
2.32k
562
2.32k
    // If multiple addends share same symbolic value, fold them together.
563
2.32k
    if (StartIdx + 1 != SimpVect.size()) {
564
35
      FAddend &R = TmpResult[NextTmpIdx ++];
565
35
      R = *SimpVect[StartIdx];
566
81
      for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); 
Idx++46
)
567
46
        R += *SimpVect[Idx];
568
35
569
35
      // Pop all addends being folded and push the resulting folded addend.
570
35
      SimpVect.resize(StartIdx);
571
35
      if (Val) {
572
28
        if (!R.isZero()) {
573
27
          SimpVect.push_back(&R);
574
27
        }
575
28
      } else {
576
7
        // Don't push constant addend at this time. It will be the last element
577
7
        // of <SimpVect>.
578
7
        ConstAdd = &R;
579
7
      }
580
35
    }
581
2.32k
  }
582
866
583
866
  assert((NextTmpIdx <= array_lengthof(TmpResult) + 1) &&
584
866
         "out-of-bound access");
585
866
586
866
  if (ConstAdd)
587
7
    SimpVect.push_back(ConstAdd);
588
866
589
866
  Value *Result;
590
866
  if (!SimpVect.empty())
591
866
    Result = createNaryFAdd(SimpVect, InstrQuota);
592
0
  else {
593
0
    // The addition is folded to 0.0.
594
0
    Result = ConstantFP::get(Instr->getType(), 0.0);
595
0
  }
596
866
597
866
  return Result;
598
866
}
599
600
Value *FAddCombine::createNaryFAdd
601
866
  (const AddendVect &Opnds, unsigned InstrQuota) {
602
866
  assert(!Opnds.empty() && "Expect at least one addend");
603
866
604
866
  // Step 1: Check if the # of instructions needed exceeds the quota.
605
866
606
866
  unsigned InstrNeeded = calcInstrNumber(Opnds);
607
866
  if (InstrNeeded > InstrQuota)
608
841
    return nullptr;
609
25
610
25
  initCreateInstNum();
611
25
612
25
  // step 2: Emit the N-ary addition.
613
25
  // Note that at most three instructions are involved in Fadd-InstCombine: the
614
25
  // addition in question, and at most two neighboring instructions.
615
25
  // The resulting optimized addition should have at least one less instruction
616
25
  // than the original addition expression tree. This implies that the resulting
617
25
  // N-ary addition has at most two instructions, and we don't need to worry
618
25
  // about tree-height when constructing the N-ary addition.
619
25
620
25
  Value *LastVal = nullptr;
621
25
  bool LastValNeedNeg = false;
622
25
623
25
  // Iterate the addends, creating fadd/fsub using adjacent two addends.
624
35
  for (const FAddend *Opnd : Opnds) {
625
35
    bool NeedNeg;
626
35
    Value *V = createAddendVal(*Opnd, NeedNeg);
627
35
    if (!LastVal) {
628
25
      LastVal = V;
629
25
      LastValNeedNeg = NeedNeg;
630
25
      continue;
631
25
    }
632
10
633
10
    if (LastValNeedNeg == NeedNeg) {
634
4
      LastVal = createFAdd(LastVal, V);
635
4
      continue;
636
4
    }
637
6
638
6
    if (LastValNeedNeg)
639
5
      LastVal = createFSub(V, LastVal);
640
1
    else
641
1
      LastVal = createFSub(LastVal, V);
642
6
643
6
    LastValNeedNeg = false;
644
6
  }
645
25
646
25
  if (LastValNeedNeg) {
647
1
    LastVal = createFNeg(LastVal);
648
1
  }
649
25
650
#ifndef NDEBUG
651
  assert(CreateInstrNum == InstrNeeded &&
652
         "Inconsistent in instruction numbers");
653
#endif
654
655
25
  return LastVal;
656
25
}
657
658
7
Value *FAddCombine::createFSub(Value *Opnd0, Value *Opnd1) {
659
7
  Value *V = Builder.CreateFSub(Opnd0, Opnd1);
660
7
  if (Instruction *I = dyn_cast<Instruction>(V))
661
7
    createInstPostProc(I);
662
7
  return V;
663
7
}
664
665
1
Value *FAddCombine::createFNeg(Value *V) {
666
1
  Value *Zero = cast<Value>(ConstantFP::getZeroValueForNegation(V->getType()));
667
1
  Value *NewV = createFSub(Zero, V);
668
1
  if (Instruction *I = dyn_cast<Instruction>(NewV))
669
1
    createInstPostProc(I, true); // fneg's don't receive instruction numbers.
670
1
  return NewV;
671
1
}
672
673
6
Value *FAddCombine::createFAdd(Value *Opnd0, Value *Opnd1) {
674
6
  Value *V = Builder.CreateFAdd(Opnd0, Opnd1);
675
6
  if (Instruction *I = dyn_cast<Instruction>(V))
676
6
    createInstPostProc(I);
677
6
  return V;
678
6
}
679
680
18
Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) {
681
18
  Value *V = Builder.CreateFMul(Opnd0, Opnd1);
682
18
  if (Instruction *I = dyn_cast<Instruction>(V))
683
18
    createInstPostProc(I);
684
18
  return V;
685
18
}
686
687
32
void FAddCombine::createInstPostProc(Instruction *NewInstr, bool NoNumber) {
688
32
  NewInstr->setDebugLoc(Instr->getDebugLoc());
689
32
690
32
  // Keep track of the number of instruction created.
691
32
  if (!NoNumber)
692
31
    incCreateInstNum();
693
32
694
32
  // Propagate fast-math flags
695
32
  NewInstr->setFastMathFlags(Instr->getFastMathFlags());
696
32
}
697
698
// Return the number of instruction needed to emit the N-ary addition.
699
// NOTE: Keep this function in sync with createAddendVal().
700
866
unsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) {
701
866
  unsigned OpndNum = Opnds.size();
702
866
  unsigned InstrNeeded = OpndNum - 1;
703
866
704
866
  // The number of addends in the form of "(-1)*x".
705
866
  unsigned NegOpndNum = 0;
706
866
707
866
  // Adjust the number of instructions needed to emit the N-ary add.
708
2.32k
  for (const FAddend *Opnd : Opnds) {
709
2.32k
    if (Opnd->isConstant())
710
223
      continue;
711
2.10k
712
2.10k
    // The constant check above is really for a few special constant
713
2.10k
    // coefficients.
714
2.10k
    if (isa<UndefValue>(Opnd->getSymVal()))
715
0
      continue;
716
2.10k
717
2.10k
    const FAddendCoef &CE = Opnd->getCoef();
718
2.10k
    if (CE.isMinusOne() || 
CE.isMinusTwo()1.95k
)
719
147
      NegOpndNum++;
720
2.10k
721
2.10k
    // Let the addend be "c * x". If "c == +/-1", the value of the addend
722
2.10k
    // is immediately available; otherwise, it needs exactly one instruction
723
2.10k
    // to evaluate the value.
724
2.10k
    if (!CE.isMinusOne() && 
!CE.isOne()1.95k
)
725
315
      InstrNeeded++;
726
2.10k
  }
727
866
  if (NegOpndNum == OpndNum)
728
6
    InstrNeeded++;
729
866
  return InstrNeeded;
730
866
}
731
732
// Input Addend        Value           NeedNeg(output)
733
// ================================================================
734
// Constant C          C               false
735
// <+/-1, V>           V               coefficient is -1
736
// <2/-2, V>          "fadd V, V"      coefficient is -2
737
// <C, V>             "fmul V, C"      false
738
//
739
// NOTE: Keep this function in sync with FAddCombine::calcInstrNumber.
740
35
Value *FAddCombine::createAddendVal(const FAddend &Opnd, bool &NeedNeg) {
741
35
  const FAddendCoef &Coeff = Opnd.getCoef();
742
35
743
35
  if (Opnd.isConstant()) {
744
6
    NeedNeg = false;
745
6
    return Coeff.getValue(Instr->getType());
746
6
  }
747
29
748
29
  Value *OpndVal = Opnd.getSymVal();
749
29
750
29
  if (Coeff.isMinusOne() || 
Coeff.isOne()21
) {
751
9
    NeedNeg = Coeff.isMinusOne();
752
9
    return OpndVal;
753
9
  }
754
20
755
20
  if (Coeff.isTwo() || Coeff.isMinusTwo()) {
756
2
    NeedNeg = Coeff.isMinusTwo();
757
2
    return createFAdd(OpndVal, OpndVal);
758
2
  }
759
18
760
18
  NeedNeg = false;
761
18
  return createFMul(OpndVal, Coeff.getValue(Instr->getType()));
762
18
}
763
764
// Checks if any operand is negative and we can convert add to sub.
765
// This function checks for following negative patterns
766
//   ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C))
767
//   ADD(XOR(AND(Z, C), C), 1) == NEG(OR(Z, ~C))
768
//   XOR(AND(Z, C), (C + 1)) == NEG(OR(Z, ~C)) if C is even
769
static Value *checkForNegativeOperand(BinaryOperator &I,
770
5.44M
                                      InstCombiner::BuilderTy &Builder) {
771
5.44M
  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
772
5.44M
773
5.44M
  // This function creates 2 instructions to replace ADD, we need at least one
774
5.44M
  // of LHS or RHS to have one use to ensure benefit in transform.
775
5.44M
  if (!LHS->hasOneUse() && 
!RHS->hasOneUse()3.16M
)
776
2.87M
    return nullptr;
777
2.56M
778
2.56M
  Value *X = nullptr, *Y = nullptr, *Z = nullptr;
779
2.56M
  const APInt *C1 = nullptr, *C2 = nullptr;
780
2.56M
781
2.56M
  // if ONE is on other side, swap
782
2.56M
  if (match(RHS, m_Add(m_Value(X), m_One())))
783
3.32k
    std::swap(LHS, RHS);
784
2.56M
785
2.56M
  if (match(LHS, m_Add(m_Value(X), m_One()))) {
786
30.2k
    // if XOR on other side, swap
787
30.2k
    if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
788
71
      std::swap(X, RHS);
789
30.2k
790
30.2k
    if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) {
791
81
      // X = XOR(Y, C1), Y = OR(Z, C2), C2 = NOT(C1) ==> X == NOT(AND(Z, C1))
792
81
      // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, AND(Z, C1))
793
81
      if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && 
(*C2 == ~(*C1))5
) {
794
5
        Value *NewAnd = Builder.CreateAnd(Z, *C1);
795
5
        return Builder.CreateSub(RHS, NewAnd, "sub");
796
76
      } else if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && 
(*C1 == *C2)3
) {
797
3
        // X = XOR(Y, C1), Y = AND(Z, C2), C2 == C1 ==> X == NOT(OR(Z, ~C1))
798
3
        // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, OR(Z, ~C1))
799
3
        Value *NewOr = Builder.CreateOr(Z, ~(*C1));
800
3
        return Builder.CreateSub(RHS, NewOr, "sub");
801
3
      }
802
2.56M
    }
803
30.2k
  }
804
2.56M
805
2.56M
  // Restore LHS and RHS
806
2.56M
  LHS = I.getOperand(0);
807
2.56M
  RHS = I.getOperand(1);
808
2.56M
809
2.56M
  // if XOR is on other side, swap
810
2.56M
  if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
811
11.8k
    std::swap(LHS, RHS);
812
2.56M
813
2.56M
  // C2 is ODD
814
2.56M
  // LHS = XOR(Y, C1), Y = AND(Z, C2), C1 == (C2 + 1) => LHS == NEG(OR(Z, ~C2))
815
2.56M
  // ADD(LHS, RHS) == SUB(RHS, OR(Z, ~C2))
816
2.56M
  if (match(LHS, m_Xor(m_Value(Y), m_APInt(C1))))
817
19.3k
    if (C1->countTrailingZeros() == 0)
818
17.1k
      if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && 
*C1 == (*C2 + 1)413
) {
819
1
        Value *NewOr = Builder.CreateOr(Z, ~(*C2));
820
1
        return Builder.CreateSub(RHS, NewOr, "sub");
821
1
      }
822
2.56M
  return nullptr;
823
2.56M
}
824
825
/// Wrapping flags may allow combining constants separated by an extend.
826
static Instruction *foldNoWrapAdd(BinaryOperator &Add,
827
5.45M
                                  InstCombiner::BuilderTy &Builder) {
828
5.45M
  Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1);
829
5.45M
  Type *Ty = Add.getType();
830
5.45M
  Constant *Op1C;
831
5.45M
  if (!match(Op1, m_Constant(Op1C)))
832
1.52M
    return nullptr;
833
3.92M
834
3.92M
  // Try this match first because it results in an add in the narrow type.
835
3.92M
  // (zext (X +nuw C2)) + C1 --> zext (X + (C2 + trunc(C1)))
836
3.92M
  Value *X;
837
3.92M
  const APInt *C1, *C2;
838
3.92M
  if (match(Op1, m_APInt(C1)) &&
839
3.92M
      
match(Op0, m_OneUse(m_ZExt(m_NUWAdd(m_Value(X), m_APInt(C2)))))3.92M
&&
840
3.92M
      
C1->isNegative()53
&&
C1->sge(-C2->sext(C1->getBitWidth()))51
) {
841
50
    Constant *NewC =
842
50
        ConstantInt::get(X->getType(), *C2 + C1->trunc(C2->getBitWidth()));
843
50
    return new ZExtInst(Builder.CreateNUWAdd(X, NewC), Ty);
844
50
  }
845
3.92M
846
3.92M
  // More general combining of constants in the wide type.
847
3.92M
  // (sext (X +nsw NarrowC)) + C --> (sext X) + (sext(NarrowC) + C)
848
3.92M
  Constant *NarrowC;
849
3.92M
  if (match(Op0, m_OneUse(m_SExt(m_NSWAdd(m_Value(X), m_Constant(NarrowC)))))) {
850
8
    Constant *WideC = ConstantExpr::getSExt(NarrowC, Ty);
851
8
    Constant *NewC = ConstantExpr::getAdd(WideC, Op1C);
852
8
    Value *WideX = Builder.CreateSExt(X, Ty);
853
8
    return BinaryOperator::CreateAdd(WideX, NewC);
854
8
  }
855
3.92M
  // (zext (X +nuw NarrowC)) + C --> (zext X) + (zext(NarrowC) + C)
856
3.92M
  if (match(Op0, m_OneUse(m_ZExt(m_NUWAdd(m_Value(X), m_Constant(NarrowC)))))) {
857
4
    Constant *WideC = ConstantExpr::getZExt(NarrowC, Ty);
858
4
    Constant *NewC = ConstantExpr::getAdd(WideC, Op1C);
859
4
    Value *WideX = Builder.CreateZExt(X, Ty);
860
4
    return BinaryOperator::CreateAdd(WideX, NewC);
861
4
  }
862
3.92M
863
3.92M
  return nullptr;
864
3.92M
}
865
866
5.45M
Instruction *InstCombiner::foldAddWithConstant(BinaryOperator &Add) {
867
5.45M
  Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1);
868
5.45M
  Constant *Op1C;
869
5.45M
  if (!match(Op1, m_Constant(Op1C)))
870
1.52M
    return nullptr;
871
3.92M
872
3.92M
  if (Instruction *NV = foldBinOpIntoSelectOrPhi(Add))
873
1.15k
    return NV;
874
3.92M
875
3.92M
  Value *X;
876
3.92M
  Constant *Op00C;
877
3.92M
878
3.92M
  // add (sub C1, X), C2 --> sub (add C1, C2), X
879
3.92M
  if (match(Op0, m_Sub(m_Constant(Op00C), m_Value(X))))
880
1.67k
    return BinaryOperator::CreateSub(ConstantExpr::getAdd(Op00C, Op1C), X);
881
3.92M
882
3.92M
  Value *Y;
883
3.92M
884
3.92M
  // add (sub X, Y), -1 --> add (not Y), X
885
3.92M
  if (match(Op0, m_OneUse(m_Sub(m_Value(X), m_Value(Y)))) &&
886
3.92M
      
match(Op1, m_AllOnes())6.37k
)
887
607
    return BinaryOperator::CreateAdd(Builder.CreateNot(Y), X);
888
3.92M
889
3.92M
  // zext(bool) + C -> bool ? C + 1 : C
890
3.92M
  if (match(Op0, m_ZExt(m_Value(X))) &&
891
3.92M
      
X->getType()->getScalarSizeInBits() == 137.4k
)
892
91
    return SelectInst::Create(X, AddOne(Op1C), Op1);
893
3.92M
894
3.92M
  // ~X + C --> (C-1) - X
895
3.92M
  if (match(Op0, m_Not(m_Value(X))))
896
69
    return BinaryOperator::CreateSub(SubOne(Op1C), X);
897
3.92M
898
3.92M
  const APInt *C;
899
3.92M
  if (!match(Op1, m_APInt(C)))
900
2.04k
    return nullptr;
901
3.92M
902
3.92M
  // (X | C2) + C --> (X | C2) ^ C2 iff (C2 == -C)
903
3.92M
  const APInt *C2;
904
3.92M
  if (match(Op0, m_Or(m_Value(), m_APInt(C2))) && 
*C2 == -*C5.03k
)
905
104
    return BinaryOperator::CreateXor(Op0, ConstantInt::get(Add.getType(), *C2));
906
3.92M
907
3.92M
  if (C->isSignMask()) {
908
47
    // If wrapping is not allowed, then the addition must set the sign bit:
909
47
    // X + (signmask) --> X | signmask
910
47
    if (Add.hasNoSignedWrap() || 
Add.hasNoUnsignedWrap()45
)
911
4
      return BinaryOperator::CreateOr(Op0, Op1);
912
43
913
43
    // If wrapping is allowed, then the addition flips the sign bit of LHS:
914
43
    // X + (signmask) --> X ^ signmask
915
43
    return BinaryOperator::CreateXor(Op0, Op1);
916
43
  }
917
3.92M
918
3.92M
  // Is this add the last step in a convoluted sext?
919
3.92M
  // add(zext(xor i16 X, -32768), -32768) --> sext X
920
3.92M
  Type *Ty = Add.getType();
921
3.92M
  if (match(Op0, m_ZExt(m_Xor(m_Value(X), m_APInt(C2)))) &&
922
3.92M
      
C2->isMinSignedValue()49
&&
C2->sext(Ty->getScalarSizeInBits()) == *C4
)
923
4
    return CastInst::Create(Instruction::SExt, X, Ty);
924
3.92M
925
3.92M
  if (C->isOneValue() && 
Op0->hasOneUse()2.02M
) {
926
576k
    // add (sext i1 X), 1 --> zext (not X)
927
576k
    // TODO: The smallest IR representation is (select X, 0, 1), and that would
928
576k
    // not require the one-use check. But we need to remove a transform in
929
576k
    // visitSelect and make sure that IR value tracking for select is equal or
930
576k
    // better than for these ops.
931
576k
    if (match(Op0, m_SExt(m_Value(X))) &&
932
576k
        
X->getType()->getScalarSizeInBits() == 1669
)
933
7
      return new ZExtInst(Builder.CreateNot(X), Ty);
934
576k
935
576k
    // Shifts and add used to flip and mask off the low bit:
936
576k
    // add (ashr (shl i32 X, 31), 31), 1 --> and (not X), 1
937
576k
    const APInt *C3;
938
576k
    if (match(Op0, m_AShr(m_Shl(m_Value(X), m_APInt(C2)), m_APInt(C3))) &&
939
576k
        
C2 == C3113
&&
*C2 == Ty->getScalarSizeInBits() - 1113
) {
940
2
      Value *NotX = Builder.CreateNot(X);
941
2
      return BinaryOperator::CreateAnd(NotX, ConstantInt::get(Ty, 1));
942
2
    }
943
3.92M
  }
944
3.92M
945
3.92M
  return nullptr;
946
3.92M
}
947
948
// Matches multiplication expression Op * C where C is a constant. Returns the
949
// constant value in C and the other operand in Op. Returns true if such a
950
// match is found.
951
60.1k
static bool MatchMul(Value *E, Value *&Op, APInt &C) {
952
60.1k
  const APInt *AI;
953
60.1k
  if (match(E, m_Mul(m_Value(Op), m_APInt(AI)))) {
954
22
    C = *AI;
955
22
    return true;
956
22
  }
957
60.0k
  if (match(E, m_Shl(m_Value(Op), m_APInt(AI)))) {
958
282
    C = APInt(AI->getBitWidth(), 1);
959
282
    C <<= *AI;
960
282
    return true;
961
282
  }
962
59.8k
  return false;
963
59.8k
}
964
965
// Matches remainder expression Op % C where C is a constant. Returns the
966
// constant value in C and the other operand in Op. Returns the signedness of
967
// the remainder operation in IsSigned. Returns true if such a match is
968
// found.
969
10.8M
static bool MatchRem(Value *E, Value *&Op, APInt &C, bool &IsSigned) {
970
10.8M
  const APInt *AI;
971
10.8M
  IsSigned = false;
972
10.8M
  if (match(E, m_SRem(m_Value(Op), m_APInt(AI)))) {
973
918
    IsSigned = true;
974
918
    C = *AI;
975
918
    return true;
976
918
  }
977
10.8M
  if (match(E, m_URem(m_Value(Op), m_APInt(AI)))) {
978
452
    C = *AI;
979
452
    return true;
980
452
  }
981
10.8M
  if (match(E, m_And(m_Value(Op), m_APInt(AI))) && 
(*AI + 1).isPowerOf2()104k
) {
982
58.8k
    C = *AI + 1;
983
58.8k
    return true;
984
58.8k
  }
985
10.8M
  return false;
986
10.8M
}
987
988
// Matches division expression Op / C with the given signedness as indicated
989
// by IsSigned, where C is a constant. Returns the constant value in C and the
990
// other operand in Op. Returns true if such a match is found.
991
69
static bool MatchDiv(Value *E, Value *&Op, APInt &C, bool IsSigned) {
992
69
  const APInt *AI;
993
69
  if (IsSigned && 
match(E, m_SDiv(m_Value(Op), m_APInt(AI)))61
) {
994
32
    C = *AI;
995
32
    return true;
996
32
  }
997
37
  if (!IsSigned) {
998
8
    if (match(E, m_UDiv(m_Value(Op), m_APInt(AI)))) {
999
4
      C = *AI;
1000
4
      return true;
1001
4
    }
1002
4
    if (match(E, m_LShr(m_Value(Op), m_APInt(AI)))) {
1003
1
      C = APInt(AI->getBitWidth(), 1);
1004
1
      C <<= *AI;
1005
1
      return true;
1006
1
    }
1007
32
  }
1008
32
  return false;
1009
32
}
1010
1011
// Returns whether C0 * C1 with the given signedness overflows.
1012
4
static bool MulWillOverflow(APInt &C0, APInt &C1, bool IsSigned) {
1013
4
  bool overflow;
1014
4
  if (IsSigned)
1015
2
    (void)C0.smul_ov(C1, overflow);
1016
2
  else
1017
2
    (void)C0.umul_ov(C1, overflow);
1018
4
  return overflow;
1019
4
}
1020
1021
// Simplifies X % C0 + (( X / C0 ) % C1) * C0 to X % (C0 * C1), where (C0 * C1)
1022
// does not overflow.
1023
5.44M
Value *InstCombiner::SimplifyAddWithRemainder(BinaryOperator &I) {
1024
5.44M
  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1025
5.44M
  Value *X, *MulOpV;
1026
5.44M
  APInt C0, MulOpC;
1027
5.44M
  bool IsSigned;
1028
5.44M
  // Match I = X % C0 + MulOpV * C0
1029
5.44M
  if (((MatchRem(LHS, X, C0, IsSigned) && 
MatchMul(RHS, MulOpV, MulOpC)51.7k
) ||
1030
5.44M
       
(5.44M
MatchRem(RHS, X, C0, IsSigned)5.44M
&&
MatchMul(LHS, MulOpV, MulOpC)8.32k
)) &&
1031
5.44M
      
C0 == MulOpC304
) {
1032
210
    Value *RemOpV;
1033
210
    APInt C1;
1034
210
    bool Rem2IsSigned;
1035
210
    // Match MulOpC = RemOpV % C1
1036
210
    if (MatchRem(MulOpV, RemOpV, C1, Rem2IsSigned) &&
1037
210
        
IsSigned == Rem2IsSigned69
) {
1038
69
      Value *DivOpV;
1039
69
      APInt DivOpC;
1040
69
      // Match RemOpV = X / C0
1041
69
      if (MatchDiv(RemOpV, DivOpV, DivOpC, IsSigned) && 
X == DivOpV37
&&
1042
69
          
C0 == DivOpC7
&&
!MulWillOverflow(C0, C1, IsSigned)4
) {
1043
4
        Value *NewDivisor =
1044
4
            ConstantInt::get(X->getType()->getContext(), C0 * C1);
1045
4
        return IsSigned ? 
Builder.CreateSRem(X, NewDivisor, "srem")2
1046
4
                        : 
Builder.CreateURem(X, NewDivisor, "urem")2
;
1047
4
      }
1048
5.44M
    }
1049
210
  }
1050
5.44M
1051
5.44M
  return nullptr;
1052
5.44M
}
1053
1054
/// Fold
1055
///   (1 << NBits) - 1
1056
/// Into:
1057
///   ~(-(1 << NBits))
1058
/// Because a 'not' is better for bit-tracking analysis and other transforms
1059
/// than an 'add'. The new shl is always nsw, and is nuw if old `and` was.
1060
static Instruction *canonicalizeLowbitMask(BinaryOperator &I,
1061
5.42M
                                           InstCombiner::BuilderTy &Builder) {
1062
5.42M
  Value *NBits;
1063
5.42M
  if (!match(&I, m_Add(m_OneUse(m_Shl(m_One(), m_Value(NBits))), m_AllOnes())))
1064
5.42M
    return nullptr;
1065
258
1066
258
  Constant *MinusOne = Constant::getAllOnesValue(NBits->getType());
1067
258
  Value *NotMask = Builder.CreateShl(MinusOne, NBits, "notmask");
1068
258
  // Be wary of constant folding.
1069
258
  if (auto *BOp = dyn_cast<BinaryOperator>(NotMask)) {
1070
257
    // Always NSW. But NUW propagates from `add`.
1071
257
    BOp->setHasNoSignedWrap();
1072
257
    BOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1073
257
  }
1074
258
1075
258
  return BinaryOperator::CreateNot(NotMask, I.getName());
1076
258
}
1077
1078
5.42M
static Instruction *foldToUnsignedSaturatedAdd(BinaryOperator &I) {
1079
5.42M
  assert(I.getOpcode() == Instruction::Add && "Expecting add instruction");
1080
5.42M
  Type *Ty = I.getType();
1081
5.42M
  auto getUAddSat = [&]() {
1082
15
    return Intrinsic::getDeclaration(I.getModule(), Intrinsic::uadd_sat, Ty);
1083
15
  };
1084
5.42M
1085
5.42M
  // add (umin X, ~Y), Y --> uaddsat X, Y
1086
5.42M
  Value *X, *Y;
1087
5.42M
  if (match(&I, m_c_Add(m_c_UMin(m_Value(X), m_Not(m_Value(Y))),
1088
5.42M
                        m_Deferred(Y))))
1089
4
    return CallInst::Create(getUAddSat(), { X, Y });
1090
5.42M
1091
5.42M
  // add (umin X, ~C), C --> uaddsat X, C
1092
5.42M
  const APInt *C, *NotC;
1093
5.42M
  if (match(&I, m_Add(m_UMin(m_Value(X), m_APInt(NotC)), m_APInt(C))) &&
1094
5.42M
      
*C == ~*NotC9.96k
)
1095
11
    return CallInst::Create(getUAddSat(), { X, ConstantInt::get(Ty, *C) });
1096
5.42M
1097
5.42M
  return nullptr;
1098
5.42M
}
1099
1100
5.53M
Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
1101
5.53M
  if (Value *V = SimplifyAddInst(I.getOperand(0), I.getOperand(1),
1102
21.6k
                                 I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
1103
21.6k
                                 SQ.getWithInstruction(&I)))
1104
21.6k
    return replaceInstUsesWith(I, V);
1105
5.51M
1106
5.51M
  if (SimplifyAssociativeOrCommutative(I))
1107
59.3k
    return &I;
1108
5.45M
1109
5.45M
  if (Instruction *X = foldVectorBinop(I))
1110
85
    return X;
1111
5.45M
1112
5.45M
  // (A*B)+(A*C) -> A*(B+C) etc
1113
5.45M
  if (Value *V = SimplifyUsingDistributiveLaws(I))
1114
1.46k
    return replaceInstUsesWith(I, V);
1115
5.45M
1116
5.45M
  if (Instruction *X = foldAddWithConstant(I))
1117
3.75k
    return X;
1118
5.45M
1119
5.45M
  if (Instruction *X = foldNoWrapAdd(I, Builder))
1120
62
    return X;
1121
5.45M
1122
5.45M
  // FIXME: This should be moved into the above helper function to allow these
1123
5.45M
  // transforms for general constant or constant splat vectors.
1124
5.45M
  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1125
5.45M
  Type *Ty = I.getType();
1126
5.45M
  if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
1127
3.77M
    Value *XorLHS = nullptr; ConstantInt *XorRHS = nullptr;
1128
3.77M
    if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) {
1129
3.77k
      unsigned TySizeBits = Ty->getScalarSizeInBits();
1130
3.77k
      const APInt &RHSVal = CI->getValue();
1131
3.77k
      unsigned ExtendAmt = 0;
1132
3.77k
      // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext.
1133
3.77k
      // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext.
1134
3.77k
      if (XorRHS->getValue() == -RHSVal) {
1135
14
        if (RHSVal.isPowerOf2())
1136
1
          ExtendAmt = TySizeBits - RHSVal.logBase2() - 1;
1137
13
        else if (XorRHS->getValue().isPowerOf2())
1138
13
          ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1;
1139
14
      }
1140
3.77k
1141
3.77k
      if (ExtendAmt) {
1142
14
        APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt);
1143
14
        if (!MaskedValueIsZero(XorLHS, Mask, 0, &I))
1144
10
          ExtendAmt = 0;
1145
14
      }
1146
3.77k
1147
3.77k
      if (ExtendAmt) {
1148
4
        Constant *ShAmt = ConstantInt::get(Ty, ExtendAmt);
1149
4
        Value *NewShl = Builder.CreateShl(XorLHS, ShAmt, "sext");
1150
4
        return BinaryOperator::CreateAShr(NewShl, ShAmt);
1151
4
      }
1152
3.77k
1153
3.77k
      // If this is a xor that was canonicalized from a sub, turn it back into
1154
3.77k
      // a sub and fuse this add with it.
1155
3.77k
      if (LHS->hasOneUse() && 
(XorRHS->getValue()+1).isPowerOf2()426
) {
1156
26
        KnownBits LHSKnown = computeKnownBits(XorLHS, 0, &I);
1157
26
        if ((XorRHS->getValue() | LHSKnown.Zero).isAllOnesValue())
1158
16
          return BinaryOperator::CreateSub(ConstantExpr::getAdd(XorRHS, CI),
1159
16
                                           XorLHS);
1160
3.75k
      }
1161
3.75k
      // (X + signmask) + C could have gotten canonicalized to (X^signmask) + C,
1162
3.75k
      // transform them into (X + (signmask ^ C))
1163
3.75k
      if (XorRHS->getValue().isSignMask())
1164
1
        return BinaryOperator::CreateAdd(XorLHS,
1165
1
                                         ConstantExpr::getXor(XorRHS, CI));
1166
5.45M
    }
1167
3.77M
  }
1168
5.45M
1169
5.45M
  if (Ty->isIntOrIntVectorTy(1))
1170
10
    return BinaryOperator::CreateXor(LHS, RHS);
1171
5.45M
1172
5.45M
  // X + X --> X << 1
1173
5.45M
  if (LHS == RHS) {
1174
139
    auto *Shl = BinaryOperator::CreateShl(LHS, ConstantInt::get(Ty, 1));
1175
139
    Shl->setHasNoSignedWrap(I.hasNoSignedWrap());
1176
139
    Shl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1177
139
    return Shl;
1178
139
  }
1179
5.45M
1180
5.45M
  Value *A, *B;
1181
5.45M
  if (match(LHS, m_Neg(m_Value(A)))) {
1182
463
    // -A + -B --> -(A + B)
1183
463
    if (match(RHS, m_Neg(m_Value(B))))
1184
271
      return BinaryOperator::CreateNeg(Builder.CreateAdd(A, B));
1185
192
1186
192
    // -A + B --> B - A
1187
192
    return BinaryOperator::CreateSub(RHS, A);
1188
192
  }
1189
5.45M
1190
5.45M
  // Canonicalize sext to zext for better value tracking potential.
1191
5.45M
  // add A, sext(B) --> sub A, zext(B)
1192
5.45M
  if (match(&I, m_c_Add(m_Value(A), m_OneUse(m_SExt(m_Value(B))))) &&
1193
5.45M
      
B->getType()->isIntOrIntVectorTy(1)50.1k
)
1194
1.58k
    return BinaryOperator::CreateSub(A, Builder.CreateZExt(B, Ty));
1195
5.44M
1196
5.44M
  // A + -B  -->  A - B
1197
5.44M
  if (match(RHS, m_Neg(m_Value(B))))
1198
8.14k
    return BinaryOperator::CreateSub(LHS, B);
1199
5.44M
1200
5.44M
  if (Value *V = checkForNegativeOperand(I, Builder))
1201
9
    return replaceInstUsesWith(I, V);
1202
5.44M
1203
5.44M
  // (A + 1) + ~B --> A - B
1204
5.44M
  // ~B + (A + 1) --> A - B
1205
5.44M
  // (~B + A) + 1 --> A - B
1206
5.44M
  // (A + ~B) + 1 --> A - B
1207
5.44M
  if (match(&I, m_c_BinOp(m_Add(m_Value(A), m_One()), m_Not(m_Value(B)))) ||
1208
5.44M
      
match(&I, m_BinOp(m_c_Add(m_Not(m_Value(B)), m_Value(A)), m_One()))5.44M
)
1209
85
    return BinaryOperator::CreateSub(A, B);
1210
5.44M
1211
5.44M
  // X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1)
1212
5.44M
  if (Value *V = SimplifyAddWithRemainder(I)) 
return replaceInstUsesWith(I, V)4
;
1213
5.44M
1214
5.44M
  // A+B --> A|B iff A and B have no bits set in common.
1215
5.44M
  if (haveNoCommonBitsSet(LHS, RHS, DL, &AC, &I, &DT))
1216
13.0k
    return BinaryOperator::CreateOr(LHS, RHS);
1217
5.42M
1218
5.42M
  // FIXME: We already did a check for ConstantInt RHS above this.
1219
5.42M
  // FIXME: Is this pattern covered by another fold? No regression tests fail on
1220
5.42M
  // removal.
1221
5.42M
  if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
1222
3.76M
    // (X & FF00) + xx00  -> (X+xx00) & FF00
1223
3.76M
    Value *X;
1224
3.76M
    ConstantInt *C2;
1225
3.76M
    if (LHS->hasOneUse() &&
1226
3.76M
        
match(LHS, m_And(m_Value(X), m_ConstantInt(C2)))1.22M
&&
1227
3.76M
        
CRHS->getValue() == (CRHS->getValue() & C2->getValue())8.78k
) {
1228
4.12k
      // See if all bits from the first bit set in the Add RHS up are included
1229
4.12k
      // in the mask.  First, get the rightmost bit.
1230
4.12k
      const APInt &AddRHSV = CRHS->getValue();
1231
4.12k
1232
4.12k
      // Form a mask of all bits from the lowest bit added through the top.
1233
4.12k
      APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1));
1234
4.12k
1235
4.12k
      // See if the and mask includes all of these bits.
1236
4.12k
      APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue());
1237
4.12k
1238
4.12k
      if (AddRHSHighBits == AddRHSHighBitsAnd) {
1239
137
        // Okay, the xform is safe.  Insert the new add pronto.
1240
137
        Value *NewAdd = Builder.CreateAdd(X, CRHS, LHS->getName());
1241
137
        return BinaryOperator::CreateAnd(NewAdd, C2);
1242
137
      }
1243
5.42M
    }
1244
3.76M
  }
1245
5.42M
1246
5.42M
  // add (select X 0 (sub n A)) A  -->  select X A n
1247
5.42M
  {
1248
5.42M
    SelectInst *SI = dyn_cast<SelectInst>(LHS);
1249
5.42M
    Value *A = RHS;
1250
5.42M
    if (!SI) {
1251
5.32M
      SI = dyn_cast<SelectInst>(RHS);
1252
5.32M
      A = LHS;
1253
5.32M
    }
1254
5.42M
    if (SI && 
SI->hasOneUse()117k
) {
1255
34.9k
      Value *TV = SI->getTrueValue();
1256
34.9k
      Value *FV = SI->getFalseValue();
1257
34.9k
      Value *N;
1258
34.9k
1259
34.9k
      // Can we fold the add into the argument of the select?
1260
34.9k
      // We check both true and false select arguments for a matching subtract.
1261
34.9k
      if (match(FV, m_Zero()) && 
match(TV, m_Sub(m_Value(N), m_Specific(A)))10.1k
)
1262
2
        // Fold the add into the true select value.
1263
2
        return SelectInst::Create(SI->getCondition(), N, A);
1264
34.9k
1265
34.9k
      if (match(TV, m_Zero()) && 
match(FV, m_Sub(m_Value(N), m_Specific(A)))5.70k
)
1266
1
        // Fold the add into the false select value.
1267
1
        return SelectInst::Create(SI->getCondition(), A, N);
1268
5.42M
    }
1269
5.42M
  }
1270
5.42M
1271
5.42M
  if (Instruction *Ext = narrowMathIfNoOverflow(I))
1272
181
    return Ext;
1273
5.42M
1274
5.42M
  // (add (xor A, B) (and A, B)) --> (or A, B)
1275
5.42M
  // (add (and A, B) (xor A, B)) --> (or A, B)
1276
5.42M
  if (match(&I, m_c_BinOp(m_Xor(m_Value(A), m_Value(B)),
1277
5.42M
                          m_c_And(m_Deferred(A), m_Deferred(B)))))
1278
1
    return BinaryOperator::CreateOr(A, B);
1279
5.42M
1280
5.42M
  // (add (or A, B) (and A, B)) --> (add A, B)
1281
5.42M
  // (add (and A, B) (or A, B)) --> (add A, B)
1282
5.42M
  if (match(&I, m_c_BinOp(m_Or(m_Value(A), m_Value(B)),
1283
5.42M
                          m_c_And(m_Deferred(A), m_Deferred(B))))) {
1284
7
    I.setOperand(0, A);
1285
7
    I.setOperand(1, B);
1286
7
    return &I;
1287
7
  }
1288
5.42M
1289
5.42M
  // TODO(jingyue): Consider willNotOverflowSignedAdd and
1290
5.42M
  // willNotOverflowUnsignedAdd to reduce the number of invocations of
1291
5.42M
  // computeKnownBits.
1292
5.42M
  bool Changed = false;
1293
5.42M
  if (!I.hasNoSignedWrap() && 
willNotOverflowSignedAdd(LHS, RHS, I)2.25M
) {
1294
15.5k
    Changed = true;
1295
15.5k
    I.setHasNoSignedWrap(true);
1296
15.5k
  }
1297
5.42M
  if (!I.hasNoUnsignedWrap() && 
willNotOverflowUnsignedAdd(LHS, RHS, I)3.87M
) {
1298
42.9k
    Changed = true;
1299
42.9k
    I.setHasNoUnsignedWrap(true);
1300
42.9k
  }
1301
5.42M
1302
5.42M
  if (Instruction *V = canonicalizeLowbitMask(I, Builder))
1303
257
    return V;
1304
5.42M
1305
5.42M
  if (Instruction *SatAdd = foldToUnsignedSaturatedAdd(I))
1306
15
    return SatAdd;
1307
5.42M
1308
5.42M
  return Changed ? 
&I51.7k
:
nullptr5.37M
;
1309
5.42M
}
1310
1311
/// Factor a common operand out of fadd/fsub of fmul/fdiv.
1312
static Instruction *factorizeFAddFSub(BinaryOperator &I,
1313
2.88k
                                      InstCombiner::BuilderTy &Builder) {
1314
2.88k
  assert((I.getOpcode() == Instruction::FAdd ||
1315
2.88k
          I.getOpcode() == Instruction::FSub) && "Expecting fadd/fsub");
1316
2.88k
  assert(I.hasAllowReassoc() && I.hasNoSignedZeros() &&
1317
2.88k
         "FP factorization requires FMF");
1318
2.88k
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1319
2.88k
  Value *X, *Y, *Z;
1320
2.88k
  bool IsFMul;
1321
2.88k
  if ((match(Op0, m_OneUse(m_FMul(m_Value(X), m_Value(Z)))) &&
1322
2.88k
       
match(Op1, m_OneUse(m_c_FMul(m_Value(Y), m_Specific(Z))))683
) ||
1323
2.88k
      
(2.87k
match(Op0, m_OneUse(m_FMul(m_Value(Z), m_Value(X))))2.87k
&&
1324
2.87k
       
match(Op1, m_OneUse(m_c_FMul(m_Value(Y), m_Specific(Z))))676
))
1325
12
    IsFMul = true;
1326
2.86k
  else if (match(Op0, m_OneUse(m_FDiv(m_Value(X), m_Value(Z)))) &&
1327
2.86k
           
match(Op1, m_OneUse(m_FDiv(m_Value(Y), m_Specific(Z))))67
)
1328
7
    IsFMul = false;
1329
2.86k
  else
1330
2.86k
    return nullptr;
1331
19
1332
19
  // (X * Z) + (Y * Z) --> (X + Y) * Z
1333
19
  // (X * Z) - (Y * Z) --> (X - Y) * Z
1334
19
  // (X / Z) + (Y / Z) --> (X + Y) / Z
1335
19
  // (X / Z) - (Y / Z) --> (X - Y) / Z
1336
19
  bool IsFAdd = I.getOpcode() == Instruction::FAdd;
1337
19
  Value *XY = IsFAdd ? 
Builder.CreateFAddFMF(X, Y, &I)10
1338
19
                     : 
Builder.CreateFSubFMF(X, Y, &I)9
;
1339
19
1340
19
  // Bail out if we just created a denormal constant.
1341
19
  // TODO: This is copied from a previous implementation. Is it necessary?
1342
19
  const APFloat *C;
1343
19
  if (match(XY, m_APFloat(C)) && 
!C->isNormal()4
)
1344
2
    return nullptr;
1345
17
1346
17
  return IsFMul ? 
BinaryOperator::CreateFMulFMF(XY, Z, &I)12
1347
17
                : 
BinaryOperator::CreateFDivFMF(XY, Z, &I)5
;
1348
17
}
1349
1350
672k
Instruction *InstCombiner::visitFAdd(BinaryOperator &I) {
1351
672k
  if (Value *V = SimplifyFAddInst(I.getOperand(0), I.getOperand(1),
1352
34
                                  I.getFastMathFlags(),
1353
34
                                  SQ.getWithInstruction(&I)))
1354
34
    return replaceInstUsesWith(I, V);
1355
672k
1356
672k
  if (SimplifyAssociativeOrCommutative(I))
1357
3.72k
    return &I;
1358
668k
1359
668k
  if (Instruction *X = foldVectorBinop(I))
1360
23
    return X;
1361
668k
1362
668k
  if (Instruction *FoldedFAdd = foldBinOpIntoSelectOrPhi(I))
1363
16
    return FoldedFAdd;
1364
668k
1365
668k
  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1366
668k
  Value *X;
1367
668k
  // (-X) + Y --> Y - X
1368
668k
  if (match(LHS, m_FNeg(m_Value(X))))
1369
26
    return BinaryOperator::CreateFSubFMF(RHS, X, &I);
1370
668k
  // Y + (-X) --> Y - X
1371
668k
  if (match(RHS, m_FNeg(m_Value(X))))
1372
152
    return BinaryOperator::CreateFSubFMF(LHS, X, &I);
1373
668k
1374
668k
  // Check for (fadd double (sitofp x), y), see if we can merge this into an
1375
668k
  // integer add followed by a promotion.
1376
668k
  if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) {
1377
80.9k
    Value *LHSIntVal = LHSConv->getOperand(0);
1378
80.9k
    Type *FPType = LHSConv->getType();
1379
80.9k
1380
80.9k
    // TODO: This check is overly conservative. In many cases known bits
1381
80.9k
    // analysis can tell us that the result of the addition has less significant
1382
80.9k
    // bits than the integer type can hold.
1383
80.9k
    auto IsValidPromotion = [](Type *FTy, Type *ITy) {
1384
43.3k
      Type *FScalarTy = FTy->getScalarType();
1385
43.3k
      Type *IScalarTy = ITy->getScalarType();
1386
43.3k
1387
43.3k
      // Do we have enough bits in the significand to represent the result of
1388
43.3k
      // the integer addition?
1389
43.3k
      unsigned MaxRepresentableBits =
1390
43.3k
          APFloat::semanticsPrecision(FScalarTy->getFltSemantics());
1391
43.3k
      return IScalarTy->getIntegerBitWidth() <= MaxRepresentableBits;
1392
43.3k
    };
1393
80.9k
1394
80.9k
    // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst))
1395
80.9k
    // ... if the constant fits in the integer value.  This is useful for things
1396
80.9k
    // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer
1397
80.9k
    // requires a constant pool load, and generally allows the add to be better
1398
80.9k
    // instcombined.
1399
80.9k
    if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS))
1400
42.7k
      if (IsValidPromotion(FPType, LHSIntVal->getType())) {
1401
42.5k
        Constant *CI =
1402
42.5k
          ConstantExpr::getFPToSI(CFP, LHSIntVal->getType());
1403
42.5k
        if (LHSConv->hasOneUse() &&
1404
42.5k
            
ConstantExpr::getSIToFP(CI, I.getType()) == CFP1.10k
&&
1405
42.5k
            
willNotOverflowSignedAdd(LHSIntVal, CI, I)147
) {
1406
3
          // Insert the new integer add.
1407
3
          Value *NewAdd = Builder.CreateNSWAdd(LHSIntVal, CI, "addconv");
1408
3
          return new SIToFPInst(NewAdd, I.getType());
1409
3
        }
1410
80.9k
      }
1411
80.9k
1412
80.9k
    // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y))
1413
80.9k
    if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) {
1414
529
      Value *RHSIntVal = RHSConv->getOperand(0);
1415
529
      // It's enough to check LHS types only because we require int types to
1416
529
      // be the same for this transform.
1417
529
      if (IsValidPromotion(FPType, LHSIntVal->getType())) {
1418
513
        // Only do this if x/y have the same type, if at least one of them has a
1419
513
        // single use (so we don't increase the number of int->fp conversions),
1420
513
        // and if the integer add will not overflow.
1421
513
        if (LHSIntVal->getType() == RHSIntVal->getType() &&
1422
513
            (LHSConv->hasOneUse() || 
RHSConv->hasOneUse()453
) &&
1423
513
            
willNotOverflowSignedAdd(LHSIntVal, RHSIntVal, I)87
) {
1424
3
          // Insert the new integer add.
1425
3
          Value *NewAdd = Builder.CreateNSWAdd(LHSIntVal, RHSIntVal, "addconv");
1426
3
          return new SIToFPInst(NewAdd, I.getType());
1427
3
        }
1428
668k
      }
1429
529
    }
1430
80.9k
  }
1431
668k
1432
668k
  // Handle specials cases for FAdd with selects feeding the operation
1433
668k
  if (Value *V = SimplifySelectsFeedingBinaryOp(I, LHS, RHS))
1434
6
    return replaceInstUsesWith(I, V);
1435
668k
1436
668k
  if (I.hasAllowReassoc() && 
I.hasNoSignedZeros()2.21k
) {
1437
2.11k
    if (Instruction *F = factorizeFAddFSub(I, Builder))
1438
9
      return F;
1439
2.10k
    if (Value *V = FAddCombine(Builder).simplify(&I))
1440
23
      return replaceInstUsesWith(I, V);
1441
668k
  }
1442
668k
1443
668k
  return nullptr;
1444
668k
}
1445
1446
/// Optimize pointer differences into the same array into a size.  Consider:
1447
///  &A[10] - &A[0]: we should compile this to "10".  LHS/RHS are the pointer
1448
/// operands to the ptrtoint instructions for the LHS/RHS of the subtract.
1449
Value *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS,
1450
315k
                                               Type *Ty) {
1451
315k
  // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize
1452
315k
  // this.
1453
315k
  bool Swapped = false;
1454
315k
  GEPOperator *GEP1 = nullptr, *GEP2 = nullptr;
1455
315k
1456
315k
  // For now we require one side to be the base pointer "A" or a constant
1457
315k
  // GEP derived from it.
1458
315k
  if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
1459
20.9k
    // (gep X, ...) - X
1460
20.9k
    if (LHSGEP->getOperand(0) == RHS) {
1461
216
      GEP1 = LHSGEP;
1462
216
      Swapped = false;
1463
20.7k
    } else if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
1464
3.00k
      // (gep X, ...) - (gep X, ...)
1465
3.00k
      if (LHSGEP->getOperand(0)->stripPointerCasts() ==
1466
3.00k
            RHSGEP->getOperand(0)->stripPointerCasts()) {
1467
925
        GEP2 = RHSGEP;
1468
925
        GEP1 = LHSGEP;
1469
925
        Swapped = false;
1470
925
      }
1471
3.00k
    }
1472
20.9k
  }
1473
315k
1474
315k
  if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
1475
5.59k
    // X - (gep X, ...)
1476
5.59k
    if (RHSGEP->getOperand(0) == LHS) {
1477
3
      GEP1 = RHSGEP;
1478
3
      Swapped = true;
1479
5.59k
    } else if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
1480
3.01k
      // (gep X, ...) - (gep X, ...)
1481
3.01k
      if (RHSGEP->getOperand(0)->stripPointerCasts() ==
1482
3.01k
            LHSGEP->getOperand(0)->stripPointerCasts()) {
1483
925
        GEP2 = LHSGEP;
1484
925
        GEP1 = RHSGEP;
1485
925
        Swapped = true;
1486
925
      }
1487
3.01k
    }
1488
5.59k
  }
1489
315k
1490
315k
  if (!GEP1)
1491
314k
    // No GEP found.
1492
314k
    return nullptr;
1493
1.14k
1494
1.14k
  if (GEP2) {
1495
925
    // (gep X, ...) - (gep X, ...)
1496
925
    //
1497
925
    // Avoid duplicating the arithmetic if there are more than one non-constant
1498
925
    // indices between the two GEPs and either GEP has a non-constant index and
1499
925
    // multiple users. If zero non-constant index, the result is a constant and
1500
925
    // there is no duplication. If one non-constant index, the result is an add
1501
925
    // or sub with a constant, which is no larger than the original code, and
1502
925
    // there's no duplicated arithmetic, even if either GEP has multiple
1503
925
    // users. If more than one non-constant indices combined, as long as the GEP
1504
925
    // with at least one non-constant index doesn't have multiple users, there
1505
925
    // is no duplication.
1506
925
    unsigned NumNonConstantIndices1 = GEP1->countNonConstantIndices();
1507
925
    unsigned NumNonConstantIndices2 = GEP2->countNonConstantIndices();
1508
925
    if (NumNonConstantIndices1 + NumNonConstantIndices2 > 1 &&
1509
925
        
(917
(917
NumNonConstantIndices1 > 0917
&&
!GEP1->hasOneUse()916
) ||
1510
917
         
(7
NumNonConstantIndices2 > 07
&&
!GEP2->hasOneUse()7
))) {
1511
911
      return nullptr;
1512
911
    }
1513
233
  }
1514
233
1515
233
  // Emit the offset of the GEP and an intptr_t.
1516
233
  Value *Result = EmitGEPOffset(GEP1);
1517
233
1518
233
  // If we had a constant expression GEP on the other side offsetting the
1519
233
  // pointer, subtract it from the offset we have.
1520
233
  if (GEP2) {
1521
14
    Value *Offset = EmitGEPOffset(GEP2);
1522
14
    Result = Builder.CreateSub(Result, Offset);
1523
14
  }
1524
233
1525
233
  // If we have p - gep(p, ...)  then we have to negate the result.
1526
233
  if (Swapped)
1527
17
    Result = Builder.CreateNeg(Result, "diff.neg");
1528
233
1529
233
  return Builder.CreateIntCast(Result, Ty, true);
1530
233
}
1531
1532
1.47M
Instruction *InstCombiner::visitSub(BinaryOperator &I) {
1533
1.47M
  if (Value *V = SimplifySubInst(I.getOperand(0), I.getOperand(1),
1534
540
                                 I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
1535
540
                                 SQ.getWithInstruction(&I)))
1536
540
    return replaceInstUsesWith(I, V);
1537
1.47M
1538
1.47M
  if (Instruction *X = foldVectorBinop(I))
1539
38
    return X;
1540
1.47M
1541
1.47M
  // (A*B)-(A*C) -> A*(B-C) etc
1542
1.47M
  if (Value *V = SimplifyUsingDistributiveLaws(I))
1543
108
    return replaceInstUsesWith(I, V);
1544
1.47M
1545
1.47M
  // If this is a 'B = x-(-A)', change to B = x+A.
1546
1.47M
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1547
1.47M
  if (Value *V = dyn_castNegVal(Op1)) {
1548
23.3k
    BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V);
1549
23.3k
1550
23.3k
    if (const auto *BO = dyn_cast<BinaryOperator>(Op1)) {
1551
61
      assert(BO->getOpcode() == Instruction::Sub &&
1552
61
             "Expected a subtraction operator!");
1553
61
      if (BO->hasNoSignedWrap() && 
I.hasNoSignedWrap()48
)
1554
43
        Res->setHasNoSignedWrap(true);
1555
23.2k
    } else {
1556
23.2k
      if (cast<Constant>(Op1)->isNotMinSignedValue() && 
I.hasNoSignedWrap()23.2k
)
1557
7.99k
        Res->setHasNoSignedWrap(true);
1558
23.2k
    }
1559
23.3k
1560
23.3k
    return Res;
1561
23.3k
  }
1562
1.45M
1563
1.45M
  if (I.getType()->isIntOrIntVectorTy(1))
1564
2
    return BinaryOperator::CreateXor(Op0, Op1);
1565
1.45M
1566
1.45M
  // Replace (-1 - A) with (~A).
1567
1.45M
  if (match(Op0, m_AllOnes()))
1568
697
    return BinaryOperator::CreateNot(Op1);
1569
1.45M
1570
1.45M
  // (~X) - (~Y) --> Y - X
1571
1.45M
  Value *X, *Y;
1572
1.45M
  if (match(Op0, m_Not(m_Value(X))) && 
match(Op1, m_Not(m_Value(Y)))259
)
1573
15
    return BinaryOperator::CreateSub(Y, X);
1574
1.45M
1575
1.45M
  // (X + -1) - Y --> ~Y + X
1576
1.45M
  if (match(Op0, m_OneUse(m_Add(m_Value(X), m_AllOnes()))))
1577
453
    return BinaryOperator::CreateAdd(Builder.CreateNot(Op1), X);
1578
1.45M
1579
1.45M
  // Y - (X + 1) --> ~X + Y
1580
1.45M
  if (match(Op1, m_OneUse(m_Add(m_Value(X), m_One()))))
1581
89
    return BinaryOperator::CreateAdd(Builder.CreateNot(X), Op0);
1582
1.45M
1583
1.45M
  // Y - ~X --> (X + 1) + Y
1584
1.45M
  if (match(Op1, m_OneUse(m_Not(m_Value(X))))) {
1585
58
    return BinaryOperator::CreateAdd(
1586
58
        Builder.CreateAdd(Op0, ConstantInt::get(I.getType(), 1)), X);
1587
58
  }
1588
1.45M
1589
1.45M
  if (Constant *C = dyn_cast<Constant>(Op0)) {
1590
462k
    bool IsNegate = match(C, m_ZeroInt());
1591
462k
    Value *X;
1592
462k
    if (match(Op1, m_ZExt(m_Value(X))) && 
X->getType()->isIntOrIntVectorTy(1)15.3k
) {
1593
240
      // 0 - (zext bool) --> sext bool
1594
240
      // C - (zext bool) --> bool ? C - 1 : C
1595
240
      if (IsNegate)
1596
133
        return CastInst::CreateSExtOrBitCast(X, I.getType());
1597
107
      return SelectInst::Create(X, SubOne(C), C);
1598
107
    }
1599
462k
    if (match(Op1, m_SExt(m_Value(X))) && 
X->getType()->isIntOrIntVectorTy(1)9.85k
) {
1600
11
      // 0 - (sext bool) --> zext bool
1601
11
      // C - (sext bool) --> bool ? C + 1 : C
1602
11
      if (IsNegate)
1603
7
        return CastInst::CreateZExtOrBitCast(X, I.getType());
1604
4
      return SelectInst::Create(X, AddOne(C), C);
1605
4
    }
1606
462k
1607
462k
    // C - ~X == X + (1+C)
1608
462k
    if (match(Op1, m_Not(m_Value(X))))
1609
1
      return BinaryOperator::CreateAdd(X, AddOne(C));
1610
462k
1611
462k
    // Try to fold constant sub into select arguments.
1612
462k
    if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1613
5.04k
      if (Instruction *R = FoldOpIntoSelect(I, SI))
1614
12
        return R;
1615
462k
1616
462k
    // Try to fold constant sub into PHI values.
1617
462k
    if (PHINode *PN = dyn_cast<PHINode>(Op1))
1618
93.4k
      if (Instruction *R = foldOpIntoPhi(I, PN))
1619
114
        return R;
1620
462k
1621
462k
    Constant *C2;
1622
462k
1623
462k
    // C-(C2-X) --> X+(C-C2)
1624
462k
    if (match(Op1, m_Sub(m_Constant(C2), m_Value(X))))
1625
467
      return BinaryOperator::CreateAdd(X, ConstantExpr::getSub(C, C2));
1626
461k
1627
461k
    // C-(X+C2) --> (C-C2)-X
1628
461k
    if (match(Op1, m_Add(m_Value(X), m_Constant(C2))))
1629
1.40k
      return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
1630
1.44M
  }
1631
1.44M
1632
1.44M
  const APInt *Op0C;
1633
1.44M
  if (match(Op0, m_APInt(Op0C))) {
1634
459k
    unsigned BitWidth = I.getType()->getScalarSizeInBits();
1635
459k
1636
459k
    // -(X >>u 31) -> (X >>s 31)
1637
459k
    // -(X >>s 31) -> (X >>u 31)
1638
459k
    if (Op0C->isNullValue()) {
1639
217k
      Value *X;
1640
217k
      const APInt *ShAmt;
1641
217k
      if (match(Op1, m_LShr(m_Value(X), m_APInt(ShAmt))) &&
1642
217k
          
*ShAmt == BitWidth - 11.67k
) {
1643
20
        Value *ShAmtOp = cast<Instruction>(Op1)->getOperand(1);
1644
20
        return BinaryOperator::CreateAShr(X, ShAmtOp);
1645
20
      }
1646
217k
      if (match(Op1, m_AShr(m_Value(X), m_APInt(ShAmt))) &&
1647
217k
          
*ShAmt == BitWidth - 122.8k
) {
1648
4
        Value *ShAmtOp = cast<Instruction>(Op1)->getOperand(1);
1649
4
        return BinaryOperator::CreateLShr(X, ShAmtOp);
1650
4
      }
1651
217k
1652
217k
      if (Op1->hasOneUse()) {
1653
56.4k
        Value *LHS, *RHS;
1654
56.4k
        SelectPatternFlavor SPF = matchSelectPattern(Op1, LHS, RHS).Flavor;
1655
56.4k
        if (SPF == SPF_ABS || 
SPF == SPF_NABS56.4k
) {
1656
24
          // This is a negate of an ABS/NABS pattern. Just swap the operands
1657
24
          // of the select.
1658
24
          SelectInst *SI = cast<SelectInst>(Op1);
1659
24
          Value *TrueVal = SI->getTrueValue();
1660
24
          Value *FalseVal = SI->getFalseValue();
1661
24
          SI->setTrueValue(FalseVal);
1662
24
          SI->setFalseValue(TrueVal);
1663
24
          // Don't swap prof metadata, we didn't change the branch behavior.
1664
24
          return replaceInstUsesWith(I, SI);
1665
24
        }
1666
459k
      }
1667
217k
    }
1668
459k
1669
459k
    // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known
1670
459k
    // zero.
1671
459k
    if (Op0C->isMask()) {
1672
22.4k
      KnownBits RHSKnown = computeKnownBits(Op1, 0, &I);
1673
22.4k
      if ((*Op0C | RHSKnown.Zero).isAllOnesValue())
1674
306
        return BinaryOperator::CreateXor(Op1, Op0);
1675
1.44M
    }
1676
459k
  }
1677
1.44M
1678
1.44M
  {
1679
1.44M
    Value *Y;
1680
1.44M
    // X-(X+Y) == -Y    X-(Y+X) == -Y
1681
1.44M
    if (match(Op1, m_c_Add(m_Specific(Op0), m_Value(Y))))
1682
42
      return BinaryOperator::CreateNeg(Y);
1683
1.44M
1684
1.44M
    // (X-Y)-X == -Y
1685
1.44M
    if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))
1686
1
      return BinaryOperator::CreateNeg(Y);
1687
1.44M
  }
1688
1.44M
1689
1.44M
  // (sub (or A, B), (xor A, B)) --> (and A, B)
1690
1.44M
  {
1691
1.44M
    Value *A, *B;
1692
1.44M
    if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
1693
1.44M
        
match(Op0, m_c_Or(m_Specific(A), m_Specific(B)))15.9k
)
1694
2
      return BinaryOperator::CreateAnd(A, B);
1695
1.44M
  }
1696
1.44M
1697
1.44M
  {
1698
1.44M
    Value *Y;
1699
1.44M
    // ((X | Y) - X) --> (~X & Y)
1700
1.44M
    if (match(Op0, m_OneUse(m_c_Or(m_Value(Y), m_Specific(Op1)))))
1701
3
      return BinaryOperator::CreateAnd(
1702
3
          Y, Builder.CreateNot(Op1, Op1->getName() + ".not"));
1703
1.44M
  }
1704
1.44M
1705
1.44M
  if (Op1->hasOneUse()) {
1706
471k
    Value *X = nullptr, *Y = nullptr, *Z = nullptr;
1707
471k
    Constant *C = nullptr;
1708
471k
1709
471k
    // (X - (Y - Z))  -->  (X + (Z - Y)).
1710
471k
    if (match(Op1, m_Sub(m_Value(Y), m_Value(Z))))
1711
364
      return BinaryOperator::CreateAdd(Op0,
1712
364
                                      Builder.CreateSub(Z, Y, Op1->getName()));
1713
470k
1714
470k
    // (X - (X & Y))   -->   (X & ~Y)
1715
470k
    if (match(Op1, m_c_And(m_Value(Y), m_Specific(Op0))))
1716
6.49k
      return BinaryOperator::CreateAnd(Op0,
1717
6.49k
                                  Builder.CreateNot(Y, Y->getName() + ".not"));
1718
464k
1719
464k
    // 0 - (X sdiv C)  -> (X sdiv -C)  provided the negation doesn't overflow.
1720
464k
    // TODO: This could be extended to match arbitrary vector constants.
1721
464k
    const APInt *DivC;
1722
464k
    if (match(Op0, m_Zero()) && 
match(Op1, m_SDiv(m_Value(X), m_APInt(DivC)))56.3k
&&
1723
464k
        
!DivC->isMinSignedValue()200
&&
*DivC != 1200
) {
1724
200
      Constant *NegDivC = ConstantInt::get(I.getType(), -(*DivC));
1725
200
      Instruction *BO = BinaryOperator::CreateSDiv(X, NegDivC);
1726
200
      BO->setIsExact(cast<BinaryOperator>(Op1)->isExact());
1727
200
      return BO;
1728
200
    }
1729
464k
1730
464k
    // 0 - (X << Y)  -> (-X << Y)   when X is freely negatable.
1731
464k
    if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && 
match(Op0, m_Zero())37.6k
)
1732
495
      if (Value *XNeg = dyn_castNegVal(X))
1733
9
        return BinaryOperator::CreateShl(XNeg, Y);
1734
464k
1735
464k
    // Subtracting -1/0 is the same as adding 1/0:
1736
464k
    // sub [nsw] Op0, sext(bool Y) -> add [nsw] Op0, zext(bool Y)
1737
464k
    // 'nuw' is dropped in favor of the canonical form.
1738
464k
    if (match(Op1, m_SExt(m_Value(Y))) &&
1739
464k
        
Y->getType()->getScalarSizeInBits() == 111.6k
) {
1740
16
      Value *Zext = Builder.CreateZExt(Y, I.getType());
1741
16
      BinaryOperator *Add = BinaryOperator::CreateAdd(Op0, Zext);
1742
16
      Add->setHasNoSignedWrap(I.hasNoSignedWrap());
1743
16
      return Add;
1744
16
    }
1745
464k
1746
464k
    // X - A*-B -> X + A*B
1747
464k
    // X - -A*B -> X + A*B
1748
464k
    Value *A, *B;
1749
464k
    if (match(Op1, m_c_Mul(m_Value(A), m_Neg(m_Value(B)))))
1750
0
      return BinaryOperator::CreateAdd(Op0, Builder.CreateMul(A, B));
1751
464k
1752
464k
    // X - A*C -> X + A*-C
1753
464k
    // No need to handle commuted multiply because multiply handling will
1754
464k
    // ensure constant will be move to the right hand side.
1755
464k
    if (match(Op1, m_Mul(m_Value(A), m_Constant(C))) && 
!isa<ConstantExpr>(C)181
) {
1756
179
      Value *NewMul = Builder.CreateMul(A, ConstantExpr::getNeg(C));
1757
179
      return BinaryOperator::CreateAdd(Op0, NewMul);
1758
179
    }
1759
1.44M
  }
1760
1.44M
1761
1.44M
  {
1762
1.44M
    // ~A - Min/Max(~A, O) -> Max/Min(A, ~O) - A
1763
1.44M
    // ~A - Min/Max(O, ~A) -> Max/Min(A, ~O) - A
1764
1.44M
    // Min/Max(~A, O) - ~A -> A - Max/Min(A, ~O)
1765
1.44M
    // Min/Max(O, ~A) - ~A -> A - Max/Min(A, ~O)
1766
1.44M
    // So long as O here is freely invertible, this will be neutral or a win.
1767
1.44M
    Value *LHS, *RHS, *A;
1768
1.44M
    Value *NotA = Op0, *MinMax = Op1;
1769
1.44M
    SelectPatternFlavor SPF = matchSelectPattern(MinMax, LHS, RHS).Flavor;
1770
1.44M
    if (!SelectPatternResult::isMinOrMax(SPF)) {
1771
1.42M
      NotA = Op1;
1772
1.42M
      MinMax = Op0;
1773
1.42M
      SPF = matchSelectPattern(MinMax, LHS, RHS).Flavor;
1774
1.42M
    }
1775
1.44M
    if (SelectPatternResult::isMinOrMax(SPF) &&
1776
1.44M
        
match(NotA, m_Not(m_Value(A)))17.2k
&&
(12
NotA == LHS12
||
NotA == RHS2
)) {
1777
11
      if (NotA == LHS)
1778
10
        std::swap(LHS, RHS);
1779
11
      // LHS is now O above and expected to have at least 2 uses (the min/max)
1780
11
      // NotA is epected to have 2 uses from the min/max and 1 from the sub.
1781
11
      if (IsFreeToInvert(LHS, !LHS->hasNUsesOrMore(3)) &&
1782
11
          
!NotA->hasNUsesOrMore(4)7
) {
1783
5
        // Note: We don't generate the inverse max/min, just create the not of
1784
5
        // it and let other folds do the rest.
1785
5
        Value *Not = Builder.CreateNot(MinMax);
1786
5
        if (NotA == Op0)
1787
3
          return BinaryOperator::CreateSub(Not, A);
1788
2
        else
1789
2
          return BinaryOperator::CreateSub(A, Not);
1790
1.44M
      }
1791
11
    }
1792
1.44M
  }
1793
1.44M
1794
1.44M
  // Optimize pointer differences into the same array into a size.  Consider:
1795
1.44M
  //  &A[10] - &A[0]: we should compile this to "10".
1796
1.44M
  Value *LHSOp, *RHSOp;
1797
1.44M
  if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
1798
1.44M
      
match(Op1, m_PtrToInt(m_Value(RHSOp)))346k
)
1799
315k
    if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
1800
231
      return replaceInstUsesWith(I, Res);
1801
1.44M
1802
1.44M
  // trunc(p)-trunc(q) -> trunc(p-q)
1803
1.44M
  if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) &&
1804
1.44M
      
match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp))))49
)
1805
2
    if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
1806
2
      return replaceInstUsesWith(I, Res);
1807
1.44M
1808
1.44M
  // Canonicalize a shifty way to code absolute value to the common pattern.
1809
1.44M
  // There are 2 potential commuted variants.
1810
1.44M
  // We're relying on the fact that we only do this transform when the shift has
1811
1.44M
  // exactly 2 uses and the xor has exactly 1 use (otherwise, we might increase
1812
1.44M
  // instructions).
1813
1.44M
  Value *A;
1814
1.44M
  const APInt *ShAmt;
1815
1.44M
  Type *Ty = I.getType();
1816
1.44M
  if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
1817
1.44M
      
Op1->hasNUses(2)48.1k
&&
*ShAmt == Ty->getScalarSizeInBits() - 12.24k
&&
1818
1.44M
      
match(Op0, m_OneUse(m_c_Xor(m_Specific(A), m_Specific(Op1))))180
) {
1819
90
    // B = ashr i32 A, 31 ; smear the sign bit
1820
90
    // sub (xor A, B), B  ; flip bits if negative and subtract -1 (add 1)
1821
90
    // --> (A < 0) ? -A : A
1822
90
    Value *Cmp = Builder.CreateICmpSLT(A, ConstantInt::getNullValue(Ty));
1823
90
    // Copy the nuw/nsw flags from the sub to the negate.
1824
90
    Value *Neg = Builder.CreateNeg(A, "", I.hasNoUnsignedWrap(),
1825
90
                                   I.hasNoSignedWrap());
1826
90
    return SelectInst::Create(Cmp, Neg, A);
1827
90
  }
1828
1.44M
1829
1.44M
  if (Instruction *Ext = narrowMathIfNoOverflow(I))
1830
51
    return Ext;
1831
1.44M
1832
1.44M
  bool Changed = false;
1833
1.44M
  if (!I.hasNoSignedWrap() && 
willNotOverflowSignedSub(Op0, Op1, I)842k
) {
1834
14.8k
    Changed = true;
1835
14.8k
    I.setHasNoSignedWrap(true);
1836
14.8k
  }
1837
1.44M
  if (!I.hasNoUnsignedWrap() && 
willNotOverflowUnsignedSub(Op0, Op1, I)1.37M
) {
1838
1.76k
    Changed = true;
1839
1.76k
    I.setHasNoUnsignedWrap(true);
1840
1.76k
  }
1841
1.44M
1842
1.44M
  return Changed ? 
&I15.0k
:
nullptr1.42M
;
1843
1.44M
}
1844
1845
/// This eliminates floating-point negation in either 'fneg(X)' or
1846
/// 'fsub(-0.0, X)' form by combining into a constant operand.
1847
194k
static Instruction *foldFNegIntoConstant(Instruction &I) {
1848
194k
  Value *X;
1849
194k
  Constant *C;
1850
194k
1851
194k
  // Fold negation into constant operand. This is limited with one-use because
1852
194k
  // fneg is assumed better for analysis and cheaper in codegen than fmul/fdiv.
1853
194k
  // -(X * C) --> X * (-C)
1854
194k
  // FIXME: It's arguable whether these should be m_OneUse or not. The current
1855
194k
  // belief is that the FNeg allows for better reassociation opportunities.
1856
194k
  if (match(&I, m_FNeg(m_OneUse(m_FMul(m_Value(X), m_Constant(C))))))
1857
15
    return BinaryOperator::CreateFMulFMF(X, ConstantExpr::getFNeg(C), &I);
1858
194k
  // -(X / C) --> X / (-C)
1859
194k
  if (match(&I, m_FNeg(m_OneUse(m_FDiv(m_Value(X), m_Constant(C))))))
1860
6
    return BinaryOperator::CreateFDivFMF(X, ConstantExpr::getFNeg(C), &I);
1861
194k
  // -(C / X) --> (-C) / X
1862
194k
  if (match(&I, m_FNeg(m_OneUse(m_FDiv(m_Constant(C), m_Value(X))))))
1863
8
    return BinaryOperator::CreateFDivFMF(ConstantExpr::getFNeg(C), X, &I);
1864
194k
1865
194k
  return nullptr;
1866
194k
}
1867
1868
266
Instruction *InstCombiner::visitFNeg(UnaryOperator &I) {
1869
266
  Value *Op = I.getOperand(0);
1870
266
1871
266
  if (Value *V = SimplifyFNegInst(Op, I.getFastMathFlags(),
1872
5
                                  SQ.getWithInstruction(&I)))
1873
5
    return replaceInstUsesWith(I, V);
1874
261
1875
261
  if (Instruction *X = foldFNegIntoConstant(I))
1876
10
    return X;
1877
251
1878
251
  Value *X, *Y;
1879
251
1880
251
  // If we can ignore the sign of zeros: -(X - Y) --> (Y - X)
1881
251
  if (I.hasNoSignedZeros() &&
1882
251
      
match(Op, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))25
)
1883
1
    return BinaryOperator::CreateFSubFMF(Y, X, &I);
1884
250
1885
250
  return nullptr;
1886
250
}
1887
1888
194k
Instruction *InstCombiner::visitFSub(BinaryOperator &I) {
1889
194k
  if (Value *V = SimplifyFSubInst(I.getOperand(0), I.getOperand(1),
1890
18
                                  I.getFastMathFlags(),
1891
18
                                  SQ.getWithInstruction(&I)))
1892
18
    return replaceInstUsesWith(I, V);
1893
194k
1894
194k
  if (Instruction *X = foldVectorBinop(I))
1895
20
    return X;
1896
194k
1897
194k
  // Subtraction from -0.0 is the canonical form of fneg.
1898
194k
  // fsub nsz 0, X ==> fsub nsz -0.0, X
1899
194k
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1900
194k
  if (I.hasNoSignedZeros() && 
match(Op0, m_PosZeroFP())833
)
1901
14
    return BinaryOperator::CreateFNegFMF(Op1, &I);
1902
194k
1903
194k
  if (Instruction *X = foldFNegIntoConstant(I))
1904
19
    return X;
1905
194k
1906
194k
  Value *X, *Y;
1907
194k
  Constant *C;
1908
194k
1909
194k
  // If Op0 is not -0.0 or we can ignore -0.0: Z - (X - Y) --> Z + (Y - X)
1910
194k
  // Canonicalize to fadd to make analysis easier.
1911
194k
  // This can also help codegen because fadd is commutative.
1912
194k
  // Note that if this fsub was really an fneg, the fadd with -0.0 will get
1913
194k
  // killed later. We still limit that particular transform with 'hasOneUse'
1914
194k
  // because an fneg is assumed better/cheaper than a generic fsub.
1915
194k
  if (I.hasNoSignedZeros() || 
CannotBeNegativeZero(Op0, SQ.TLI)193k
) {
1916
19.3k
    if (match(Op1, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) {
1917
3
      Value *NewSub = Builder.CreateFSubFMF(Y, X, &I);
1918
3
      return BinaryOperator::CreateFAddFMF(Op0, NewSub, &I);
1919
3
    }
1920
194k
  }
1921
194k
1922
194k
  if (isa<Constant>(Op0))
1923
58.9k
    if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1924
704
      if (Instruction *NV = FoldOpIntoSelect(I, SI))
1925
3
        return NV;
1926
194k
1927
194k
  // X - C --> X + (-C)
1928
194k
  // But don't transform constant expressions because there's an inverse fold
1929
194k
  // for X + (-Y) --> X - Y.
1930
194k
  if (match(Op1, m_Constant(C)) && 
!isa<ConstantExpr>(Op1)403
)
1931
402
    return BinaryOperator::CreateFAddFMF(Op0, ConstantExpr::getFNeg(C), &I);
1932
193k
1933
193k
  // X - (-Y) --> X + Y
1934
193k
  if (match(Op1, m_FNeg(m_Value(Y))))
1935
21
    return BinaryOperator::CreateFAddFMF(Op0, Y, &I);
1936
193k
1937
193k
  // Similar to above, but look through a cast of the negated value:
1938
193k
  // X - (fptrunc(-Y)) --> X + fptrunc(Y)
1939
193k
  Type *Ty = I.getType();
1940
193k
  if (match(Op1, m_OneUse(m_FPTrunc(m_FNeg(m_Value(Y))))))
1941
0
    return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPTrunc(Y, Ty), &I);
1942
193k
1943
193k
  // X - (fpext(-Y)) --> X + fpext(Y)
1944
193k
  if (match(Op1, m_OneUse(m_FPExt(m_FNeg(m_Value(Y))))))
1945
4
    return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPExt(Y, Ty), &I);
1946
193k
1947
193k
  // Handle special cases for FSub with selects feeding the operation
1948
193k
  if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
1949
1
    return replaceInstUsesWith(I, V);
1950
193k
1951
193k
  if (I.hasAllowReassoc() && 
I.hasNoSignedZeros()803
) {
1952
775
    // (Y - X) - Y --> -X
1953
775
    if (match(Op0, m_FSub(m_Specific(Op1), m_Value(X))))
1954
2
      return BinaryOperator::CreateFNegFMF(X, &I);
1955
773
1956
773
    // Y - (X + Y) --> -X
1957
773
    // Y - (Y + X) --> -X
1958
773
    if (match(Op1, m_c_FAdd(m_Specific(Op0), m_Value(X))))
1959
6
      return BinaryOperator::CreateFNegFMF(X, &I);
1960
767
1961
767
    // (X * C) - X --> X * (C - 1.0)
1962
767
    if (match(Op0, m_FMul(m_Specific(Op1), m_Constant(C)))) {
1963
2
      Constant *CSubOne = ConstantExpr::getFSub(C, ConstantFP::get(Ty, 1.0));
1964
2
      return BinaryOperator::CreateFMulFMF(Op1, CSubOne, &I);
1965
2
    }
1966
765
    // X - (X * C) --> X * (1.0 - C)
1967
765
    if (match(Op1, m_FMul(m_Specific(Op0), m_Constant(C)))) {
1968
2
      Constant *OneSubC = ConstantExpr::getFSub(ConstantFP::get(Ty, 1.0), C);
1969
2
      return BinaryOperator::CreateFMulFMF(Op0, OneSubC, &I);
1970
2
    }
1971
763
1972
763
    if (Instruction *F = factorizeFAddFSub(I, Builder))
1973
8
      return F;
1974
755
1975
755
    // TODO: This performs reassociative folds for FP ops. Some fraction of the
1976
755
    // functionality has been subsumed by simple pattern matching here and in
1977
755
    // InstSimplify. We should let a dedicated reassociation pass handle more
1978
755
    // complex pattern matching and remove this from InstCombine.
1979
755
    if (Value *V = FAddCombine(Builder).simplify(&I))
1980
2
      return replaceInstUsesWith(I, V);
1981
193k
  }
1982
193k
1983
193k
  return nullptr;
1984
193k
}