xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp (revision e32fecd0c2c3ee37c47ee100f169e7eb0282a873)
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 "llvm/Transforms/InstCombine/InstCombiner.h"
33 #include <cassert>
34 #include <utility>
35 
36 using namespace llvm;
37 using namespace PatternMatch;
38 
39 #define DEBUG_TYPE "instcombine"
40 
41 namespace {
42 
43   /// Class representing coefficient of floating-point addend.
44   /// This class needs to be highly efficient, which is especially true for
45   /// the constructor. As of I write this comment, the cost of the default
46   /// constructor is merely 4-byte-store-zero (Assuming compiler is able to
47   /// perform write-merging).
48   ///
49   class FAddendCoef {
50   public:
51     // The constructor has to initialize a APFloat, which is unnecessary for
52     // most addends which have coefficient either 1 or -1. So, the constructor
53     // is expensive. In order to avoid the cost of the constructor, we should
54     // reuse some instances whenever possible. The pre-created instances
55     // FAddCombine::Add[0-5] embodies this idea.
56     FAddendCoef() = default;
57     ~FAddendCoef();
58 
59     // If possible, don't define operator+/operator- etc because these
60     // operators inevitably call FAddendCoef's constructor which is not cheap.
61     void operator=(const FAddendCoef &A);
62     void operator+=(const FAddendCoef &A);
63     void operator*=(const FAddendCoef &S);
64 
65     void set(short C) {
66       assert(!insaneIntVal(C) && "Insane coefficient");
67       IsFp = false; IntVal = C;
68     }
69 
70     void set(const APFloat& C);
71 
72     void negate();
73 
74     bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); }
75     Value *getValue(Type *) const;
76 
77     bool isOne() const { return isInt() && IntVal == 1; }
78     bool isTwo() const { return isInt() && IntVal == 2; }
79     bool isMinusOne() const { return isInt() && IntVal == -1; }
80     bool isMinusTwo() const { return isInt() && IntVal == -2; }
81 
82   private:
83     bool insaneIntVal(int V) { return V > 4 || V < -4; }
84 
85     APFloat *getFpValPtr() { return reinterpret_cast<APFloat *>(&FpValBuf); }
86 
87     const APFloat *getFpValPtr() const {
88       return reinterpret_cast<const APFloat *>(&FpValBuf);
89     }
90 
91     const APFloat &getFpVal() const {
92       assert(IsFp && BufHasFpVal && "Incorret state");
93       return *getFpValPtr();
94     }
95 
96     APFloat &getFpVal() {
97       assert(IsFp && BufHasFpVal && "Incorret state");
98       return *getFpValPtr();
99     }
100 
101     bool isInt() const { return !IsFp; }
102 
103     // If the coefficient is represented by an integer, promote it to a
104     // floating point.
105     void convertToFpType(const fltSemantics &Sem);
106 
107     // Construct an APFloat from a signed integer.
108     // TODO: We should get rid of this function when APFloat can be constructed
109     //       from an *SIGNED* integer.
110     APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val);
111 
112     bool IsFp = false;
113 
114     // True iff FpValBuf contains an instance of APFloat.
115     bool BufHasFpVal = false;
116 
117     // The integer coefficient of an individual addend is either 1 or -1,
118     // and we try to simplify at most 4 addends from neighboring at most
119     // two instructions. So the range of <IntVal> falls in [-4, 4]. APInt
120     // is overkill of this end.
121     short IntVal = 0;
122 
123     AlignedCharArrayUnion<APFloat> FpValBuf;
124   };
125 
126   /// FAddend is used to represent floating-point addend. An addend is
127   /// represented as <C, V>, where the V is a symbolic value, and C is a
128   /// constant coefficient. A constant addend is represented as <C, 0>.
129   class FAddend {
130   public:
131     FAddend() = default;
132 
133     void operator+=(const FAddend &T) {
134       assert((Val == T.Val) && "Symbolic-values disagree");
135       Coeff += T.Coeff;
136     }
137 
138     Value *getSymVal() const { return Val; }
139     const FAddendCoef &getCoef() const { return Coeff; }
140 
141     bool isConstant() const { return Val == nullptr; }
142     bool isZero() const { return Coeff.isZero(); }
143 
144     void set(short Coefficient, Value *V) {
145       Coeff.set(Coefficient);
146       Val = V;
147     }
148     void set(const APFloat &Coefficient, Value *V) {
149       Coeff.set(Coefficient);
150       Val = V;
151     }
152     void set(const ConstantFP *Coefficient, Value *V) {
153       Coeff.set(Coefficient->getValueAPF());
154       Val = V;
155     }
156 
157     void negate() { Coeff.negate(); }
158 
159     /// Drill down the U-D chain one step to find the definition of V, and
160     /// try to break the definition into one or two addends.
161     static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1);
162 
163     /// Similar to FAddend::drillDownOneStep() except that the value being
164     /// splitted is the addend itself.
165     unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const;
166 
167   private:
168     void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; }
169 
170     // This addend has the value of "Coeff * Val".
171     Value *Val = nullptr;
172     FAddendCoef Coeff;
173   };
174 
175   /// FAddCombine is the class for optimizing an unsafe fadd/fsub along
176   /// with its neighboring at most two instructions.
177   ///
178   class FAddCombine {
179   public:
180     FAddCombine(InstCombiner::BuilderTy &B) : Builder(B) {}
181 
182     Value *simplify(Instruction *FAdd);
183 
184   private:
185     using AddendVect = SmallVector<const FAddend *, 4>;
186 
187     Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota);
188 
189     /// Convert given addend to a Value
190     Value *createAddendVal(const FAddend &A, bool& NeedNeg);
191 
192     /// Return the number of instructions needed to emit the N-ary addition.
193     unsigned calcInstrNumber(const AddendVect& Vect);
194 
195     Value *createFSub(Value *Opnd0, Value *Opnd1);
196     Value *createFAdd(Value *Opnd0, Value *Opnd1);
197     Value *createFMul(Value *Opnd0, Value *Opnd1);
198     Value *createFNeg(Value *V);
199     Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota);
200     void createInstPostProc(Instruction *NewInst, bool NoNumber = false);
201 
202      // Debugging stuff are clustered here.
203     #ifndef NDEBUG
204       unsigned CreateInstrNum;
205       void initCreateInstNum() { CreateInstrNum = 0; }
206       void incCreateInstNum() { CreateInstrNum++; }
207     #else
208       void initCreateInstNum() {}
209       void incCreateInstNum() {}
210     #endif
211 
212     InstCombiner::BuilderTy &Builder;
213     Instruction *Instr = nullptr;
214   };
215 
216 } // end anonymous namespace
217 
218 //===----------------------------------------------------------------------===//
219 //
220 // Implementation of
221 //    {FAddendCoef, FAddend, FAddition, FAddCombine}.
222 //
223 //===----------------------------------------------------------------------===//
224 FAddendCoef::~FAddendCoef() {
225   if (BufHasFpVal)
226     getFpValPtr()->~APFloat();
227 }
228 
229 void FAddendCoef::set(const APFloat& C) {
230   APFloat *P = getFpValPtr();
231 
232   if (isInt()) {
233     // As the buffer is meanless byte stream, we cannot call
234     // APFloat::operator=().
235     new(P) APFloat(C);
236   } else
237     *P = C;
238 
239   IsFp = BufHasFpVal = true;
240 }
241 
242 void FAddendCoef::convertToFpType(const fltSemantics &Sem) {
243   if (!isInt())
244     return;
245 
246   APFloat *P = getFpValPtr();
247   if (IntVal > 0)
248     new(P) APFloat(Sem, IntVal);
249   else {
250     new(P) APFloat(Sem, 0 - IntVal);
251     P->changeSign();
252   }
253   IsFp = BufHasFpVal = true;
254 }
255 
256 APFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) {
257   if (Val >= 0)
258     return APFloat(Sem, Val);
259 
260   APFloat T(Sem, 0 - Val);
261   T.changeSign();
262 
263   return T;
264 }
265 
266 void FAddendCoef::operator=(const FAddendCoef &That) {
267   if (That.isInt())
268     set(That.IntVal);
269   else
270     set(That.getFpVal());
271 }
272 
273 void FAddendCoef::operator+=(const FAddendCoef &That) {
274   RoundingMode RndMode = RoundingMode::NearestTiesToEven;
275   if (isInt() == That.isInt()) {
276     if (isInt())
277       IntVal += That.IntVal;
278     else
279       getFpVal().add(That.getFpVal(), RndMode);
280     return;
281   }
282 
283   if (isInt()) {
284     const APFloat &T = That.getFpVal();
285     convertToFpType(T.getSemantics());
286     getFpVal().add(T, RndMode);
287     return;
288   }
289 
290   APFloat &T = getFpVal();
291   T.add(createAPFloatFromInt(T.getSemantics(), That.IntVal), RndMode);
292 }
293 
294 void FAddendCoef::operator*=(const FAddendCoef &That) {
295   if (That.isOne())
296     return;
297 
298   if (That.isMinusOne()) {
299     negate();
300     return;
301   }
302 
303   if (isInt() && That.isInt()) {
304     int Res = IntVal * (int)That.IntVal;
305     assert(!insaneIntVal(Res) && "Insane int value");
306     IntVal = Res;
307     return;
308   }
309 
310   const fltSemantics &Semantic =
311     isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics();
312 
313   if (isInt())
314     convertToFpType(Semantic);
315   APFloat &F0 = getFpVal();
316 
317   if (That.isInt())
318     F0.multiply(createAPFloatFromInt(Semantic, That.IntVal),
319                 APFloat::rmNearestTiesToEven);
320   else
321     F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven);
322 }
323 
324 void FAddendCoef::negate() {
325   if (isInt())
326     IntVal = 0 - IntVal;
327   else
328     getFpVal().changeSign();
329 }
330 
331 Value *FAddendCoef::getValue(Type *Ty) const {
332   return isInt() ?
333     ConstantFP::get(Ty, float(IntVal)) :
334     ConstantFP::get(Ty->getContext(), getFpVal());
335 }
336 
337 // The definition of <Val>     Addends
338 // =========================================
339 //  A + B                     <1, A>, <1,B>
340 //  A - B                     <1, A>, <1,B>
341 //  0 - B                     <-1, B>
342 //  C * A,                    <C, A>
343 //  A + C                     <1, A> <C, NULL>
344 //  0 +/- 0                   <0, NULL> (corner case)
345 //
346 // Legend: A and B are not constant, C is constant
347 unsigned FAddend::drillValueDownOneStep
348   (Value *Val, FAddend &Addend0, FAddend &Addend1) {
349   Instruction *I = nullptr;
350   if (!Val || !(I = dyn_cast<Instruction>(Val)))
351     return 0;
352 
353   unsigned Opcode = I->getOpcode();
354 
355   if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) {
356     ConstantFP *C0, *C1;
357     Value *Opnd0 = I->getOperand(0);
358     Value *Opnd1 = I->getOperand(1);
359     if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && C0->isZero())
360       Opnd0 = nullptr;
361 
362     if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && C1->isZero())
363       Opnd1 = nullptr;
364 
365     if (Opnd0) {
366       if (!C0)
367         Addend0.set(1, Opnd0);
368       else
369         Addend0.set(C0, nullptr);
370     }
371 
372     if (Opnd1) {
373       FAddend &Addend = Opnd0 ? Addend1 : Addend0;
374       if (!C1)
375         Addend.set(1, Opnd1);
376       else
377         Addend.set(C1, nullptr);
378       if (Opcode == Instruction::FSub)
379         Addend.negate();
380     }
381 
382     if (Opnd0 || Opnd1)
383       return Opnd0 && Opnd1 ? 2 : 1;
384 
385     // Both operands are zero. Weird!
386     Addend0.set(APFloat(C0->getValueAPF().getSemantics()), nullptr);
387     return 1;
388   }
389 
390   if (I->getOpcode() == Instruction::FMul) {
391     Value *V0 = I->getOperand(0);
392     Value *V1 = I->getOperand(1);
393     if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) {
394       Addend0.set(C, V1);
395       return 1;
396     }
397 
398     if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) {
399       Addend0.set(C, V0);
400       return 1;
401     }
402   }
403 
404   return 0;
405 }
406 
407 // Try to break *this* addend into two addends. e.g. Suppose this addend is
408 // <2.3, V>, and V = X + Y, by calling this function, we obtain two addends,
409 // i.e. <2.3, X> and <2.3, Y>.
410 unsigned FAddend::drillAddendDownOneStep
411   (FAddend &Addend0, FAddend &Addend1) const {
412   if (isConstant())
413     return 0;
414 
415   unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1);
416   if (!BreakNum || Coeff.isOne())
417     return BreakNum;
418 
419   Addend0.Scale(Coeff);
420 
421   if (BreakNum == 2)
422     Addend1.Scale(Coeff);
423 
424   return BreakNum;
425 }
426 
427 Value *FAddCombine::simplify(Instruction *I) {
428   assert(I->hasAllowReassoc() && I->hasNoSignedZeros() &&
429          "Expected 'reassoc'+'nsz' instruction");
430 
431   // Currently we are not able to handle vector type.
432   if (I->getType()->isVectorTy())
433     return nullptr;
434 
435   assert((I->getOpcode() == Instruction::FAdd ||
436           I->getOpcode() == Instruction::FSub) && "Expect add/sub");
437 
438   // Save the instruction before calling other member-functions.
439   Instr = I;
440 
441   FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1;
442 
443   unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1);
444 
445   // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1.
446   unsigned Opnd0_ExpNum = 0;
447   unsigned Opnd1_ExpNum = 0;
448 
449   if (!Opnd0.isConstant())
450     Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1);
451 
452   // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1.
453   if (OpndNum == 2 && !Opnd1.isConstant())
454     Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1);
455 
456   // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1
457   if (Opnd0_ExpNum && Opnd1_ExpNum) {
458     AddendVect AllOpnds;
459     AllOpnds.push_back(&Opnd0_0);
460     AllOpnds.push_back(&Opnd1_0);
461     if (Opnd0_ExpNum == 2)
462       AllOpnds.push_back(&Opnd0_1);
463     if (Opnd1_ExpNum == 2)
464       AllOpnds.push_back(&Opnd1_1);
465 
466     // Compute instruction quota. We should save at least one instruction.
467     unsigned InstQuota = 0;
468 
469     Value *V0 = I->getOperand(0);
470     Value *V1 = I->getOperand(1);
471     InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) &&
472                  (!isa<Constant>(V1) && V1->hasOneUse())) ? 2 : 1;
473 
474     if (Value *R = simplifyFAdd(AllOpnds, InstQuota))
475       return R;
476   }
477 
478   if (OpndNum != 2) {
479     // The input instruction is : "I=0.0 +/- V". If the "V" were able to be
480     // splitted into two addends, say "V = X - Y", the instruction would have
481     // been optimized into "I = Y - X" in the previous steps.
482     //
483     const FAddendCoef &CE = Opnd0.getCoef();
484     return CE.isOne() ? Opnd0.getSymVal() : nullptr;
485   }
486 
487   // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1]
488   if (Opnd1_ExpNum) {
489     AddendVect AllOpnds;
490     AllOpnds.push_back(&Opnd0);
491     AllOpnds.push_back(&Opnd1_0);
492     if (Opnd1_ExpNum == 2)
493       AllOpnds.push_back(&Opnd1_1);
494 
495     if (Value *R = simplifyFAdd(AllOpnds, 1))
496       return R;
497   }
498 
499   // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1]
500   if (Opnd0_ExpNum) {
501     AddendVect AllOpnds;
502     AllOpnds.push_back(&Opnd1);
503     AllOpnds.push_back(&Opnd0_0);
504     if (Opnd0_ExpNum == 2)
505       AllOpnds.push_back(&Opnd0_1);
506 
507     if (Value *R = simplifyFAdd(AllOpnds, 1))
508       return R;
509   }
510 
511   return nullptr;
512 }
513 
514 Value *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) {
515   unsigned AddendNum = Addends.size();
516   assert(AddendNum <= 4 && "Too many addends");
517 
518   // For saving intermediate results;
519   unsigned NextTmpIdx = 0;
520   FAddend TmpResult[3];
521 
522   // Simplified addends are placed <SimpVect>.
523   AddendVect SimpVect;
524 
525   // The outer loop works on one symbolic-value at a time. Suppose the input
526   // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ...
527   // The symbolic-values will be processed in this order: x, y, z.
528   for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) {
529 
530     const FAddend *ThisAddend = Addends[SymIdx];
531     if (!ThisAddend) {
532       // This addend was processed before.
533       continue;
534     }
535 
536     Value *Val = ThisAddend->getSymVal();
537 
538     // If the resulting expr has constant-addend, this constant-addend is
539     // desirable to reside at the top of the resulting expression tree. Placing
540     // constant close to super-expr(s) will potentially reveal some
541     // optimization opportunities in super-expr(s). Here we do not implement
542     // this logic intentionally and rely on SimplifyAssociativeOrCommutative
543     // call later.
544 
545     unsigned StartIdx = SimpVect.size();
546     SimpVect.push_back(ThisAddend);
547 
548     // The inner loop collects addends sharing same symbolic-value, and these
549     // addends will be later on folded into a single addend. Following above
550     // example, if the symbolic value "y" is being processed, the inner loop
551     // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will
552     // be later on folded into "<b1+b2, y>".
553     for (unsigned SameSymIdx = SymIdx + 1;
554          SameSymIdx < AddendNum; SameSymIdx++) {
555       const FAddend *T = Addends[SameSymIdx];
556       if (T && T->getSymVal() == Val) {
557         // Set null such that next iteration of the outer loop will not process
558         // this addend again.
559         Addends[SameSymIdx] = nullptr;
560         SimpVect.push_back(T);
561       }
562     }
563 
564     // If multiple addends share same symbolic value, fold them together.
565     if (StartIdx + 1 != SimpVect.size()) {
566       FAddend &R = TmpResult[NextTmpIdx ++];
567       R = *SimpVect[StartIdx];
568       for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++)
569         R += *SimpVect[Idx];
570 
571       // Pop all addends being folded and push the resulting folded addend.
572       SimpVect.resize(StartIdx);
573       if (!R.isZero()) {
574         SimpVect.push_back(&R);
575       }
576     }
577   }
578 
579   assert((NextTmpIdx <= array_lengthof(TmpResult) + 1) &&
580          "out-of-bound access");
581 
582   Value *Result;
583   if (!SimpVect.empty())
584     Result = createNaryFAdd(SimpVect, InstrQuota);
585   else {
586     // The addition is folded to 0.0.
587     Result = ConstantFP::get(Instr->getType(), 0.0);
588   }
589 
590   return Result;
591 }
592 
593 Value *FAddCombine::createNaryFAdd
594   (const AddendVect &Opnds, unsigned InstrQuota) {
595   assert(!Opnds.empty() && "Expect at least one addend");
596 
597   // Step 1: Check if the # of instructions needed exceeds the quota.
598 
599   unsigned InstrNeeded = calcInstrNumber(Opnds);
600   if (InstrNeeded > InstrQuota)
601     return nullptr;
602 
603   initCreateInstNum();
604 
605   // step 2: Emit the N-ary addition.
606   // Note that at most three instructions are involved in Fadd-InstCombine: the
607   // addition in question, and at most two neighboring instructions.
608   // The resulting optimized addition should have at least one less instruction
609   // than the original addition expression tree. This implies that the resulting
610   // N-ary addition has at most two instructions, and we don't need to worry
611   // about tree-height when constructing the N-ary addition.
612 
613   Value *LastVal = nullptr;
614   bool LastValNeedNeg = false;
615 
616   // Iterate the addends, creating fadd/fsub using adjacent two addends.
617   for (const FAddend *Opnd : Opnds) {
618     bool NeedNeg;
619     Value *V = createAddendVal(*Opnd, NeedNeg);
620     if (!LastVal) {
621       LastVal = V;
622       LastValNeedNeg = NeedNeg;
623       continue;
624     }
625 
626     if (LastValNeedNeg == NeedNeg) {
627       LastVal = createFAdd(LastVal, V);
628       continue;
629     }
630 
631     if (LastValNeedNeg)
632       LastVal = createFSub(V, LastVal);
633     else
634       LastVal = createFSub(LastVal, V);
635 
636     LastValNeedNeg = false;
637   }
638 
639   if (LastValNeedNeg) {
640     LastVal = createFNeg(LastVal);
641   }
642 
643 #ifndef NDEBUG
644   assert(CreateInstrNum == InstrNeeded &&
645          "Inconsistent in instruction numbers");
646 #endif
647 
648   return LastVal;
649 }
650 
651 Value *FAddCombine::createFSub(Value *Opnd0, Value *Opnd1) {
652   Value *V = Builder.CreateFSub(Opnd0, Opnd1);
653   if (Instruction *I = dyn_cast<Instruction>(V))
654     createInstPostProc(I);
655   return V;
656 }
657 
658 Value *FAddCombine::createFNeg(Value *V) {
659   Value *NewV = Builder.CreateFNeg(V);
660   if (Instruction *I = dyn_cast<Instruction>(NewV))
661     createInstPostProc(I, true); // fneg's don't receive instruction numbers.
662   return NewV;
663 }
664 
665 Value *FAddCombine::createFAdd(Value *Opnd0, Value *Opnd1) {
666   Value *V = Builder.CreateFAdd(Opnd0, Opnd1);
667   if (Instruction *I = dyn_cast<Instruction>(V))
668     createInstPostProc(I);
669   return V;
670 }
671 
672 Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) {
673   Value *V = Builder.CreateFMul(Opnd0, Opnd1);
674   if (Instruction *I = dyn_cast<Instruction>(V))
675     createInstPostProc(I);
676   return V;
677 }
678 
679 void FAddCombine::createInstPostProc(Instruction *NewInstr, bool NoNumber) {
680   NewInstr->setDebugLoc(Instr->getDebugLoc());
681 
682   // Keep track of the number of instruction created.
683   if (!NoNumber)
684     incCreateInstNum();
685 
686   // Propagate fast-math flags
687   NewInstr->setFastMathFlags(Instr->getFastMathFlags());
688 }
689 
690 // Return the number of instruction needed to emit the N-ary addition.
691 // NOTE: Keep this function in sync with createAddendVal().
692 unsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) {
693   unsigned OpndNum = Opnds.size();
694   unsigned InstrNeeded = OpndNum - 1;
695 
696   // Adjust the number of instructions needed to emit the N-ary add.
697   for (const FAddend *Opnd : Opnds) {
698     if (Opnd->isConstant())
699       continue;
700 
701     // The constant check above is really for a few special constant
702     // coefficients.
703     if (isa<UndefValue>(Opnd->getSymVal()))
704       continue;
705 
706     const FAddendCoef &CE = Opnd->getCoef();
707     // Let the addend be "c * x". If "c == +/-1", the value of the addend
708     // is immediately available; otherwise, it needs exactly one instruction
709     // to evaluate the value.
710     if (!CE.isMinusOne() && !CE.isOne())
711       InstrNeeded++;
712   }
713   return InstrNeeded;
714 }
715 
716 // Input Addend        Value           NeedNeg(output)
717 // ================================================================
718 // Constant C          C               false
719 // <+/-1, V>           V               coefficient is -1
720 // <2/-2, V>          "fadd V, V"      coefficient is -2
721 // <C, V>             "fmul V, C"      false
722 //
723 // NOTE: Keep this function in sync with FAddCombine::calcInstrNumber.
724 Value *FAddCombine::createAddendVal(const FAddend &Opnd, bool &NeedNeg) {
725   const FAddendCoef &Coeff = Opnd.getCoef();
726 
727   if (Opnd.isConstant()) {
728     NeedNeg = false;
729     return Coeff.getValue(Instr->getType());
730   }
731 
732   Value *OpndVal = Opnd.getSymVal();
733 
734   if (Coeff.isMinusOne() || Coeff.isOne()) {
735     NeedNeg = Coeff.isMinusOne();
736     return OpndVal;
737   }
738 
739   if (Coeff.isTwo() || Coeff.isMinusTwo()) {
740     NeedNeg = Coeff.isMinusTwo();
741     return createFAdd(OpndVal, OpndVal);
742   }
743 
744   NeedNeg = false;
745   return createFMul(OpndVal, Coeff.getValue(Instr->getType()));
746 }
747 
748 // Checks if any operand is negative and we can convert add to sub.
749 // This function checks for following negative patterns
750 //   ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C))
751 //   ADD(XOR(AND(Z, C), C), 1) == NEG(OR(Z, ~C))
752 //   XOR(AND(Z, C), (C + 1)) == NEG(OR(Z, ~C)) if C is even
753 static Value *checkForNegativeOperand(BinaryOperator &I,
754                                       InstCombiner::BuilderTy &Builder) {
755   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
756 
757   // This function creates 2 instructions to replace ADD, we need at least one
758   // of LHS or RHS to have one use to ensure benefit in transform.
759   if (!LHS->hasOneUse() && !RHS->hasOneUse())
760     return nullptr;
761 
762   Value *X = nullptr, *Y = nullptr, *Z = nullptr;
763   const APInt *C1 = nullptr, *C2 = nullptr;
764 
765   // if ONE is on other side, swap
766   if (match(RHS, m_Add(m_Value(X), m_One())))
767     std::swap(LHS, RHS);
768 
769   if (match(LHS, m_Add(m_Value(X), m_One()))) {
770     // if XOR on other side, swap
771     if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
772       std::swap(X, RHS);
773 
774     if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) {
775       // X = XOR(Y, C1), Y = OR(Z, C2), C2 = NOT(C1) ==> X == NOT(AND(Z, C1))
776       // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, AND(Z, C1))
777       if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C2 == ~(*C1))) {
778         Value *NewAnd = Builder.CreateAnd(Z, *C1);
779         return Builder.CreateSub(RHS, NewAnd, "sub");
780       } else if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && (*C1 == *C2)) {
781         // X = XOR(Y, C1), Y = AND(Z, C2), C2 == C1 ==> X == NOT(OR(Z, ~C1))
782         // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, OR(Z, ~C1))
783         Value *NewOr = Builder.CreateOr(Z, ~(*C1));
784         return Builder.CreateSub(RHS, NewOr, "sub");
785       }
786     }
787   }
788 
789   // Restore LHS and RHS
790   LHS = I.getOperand(0);
791   RHS = I.getOperand(1);
792 
793   // if XOR is on other side, swap
794   if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
795     std::swap(LHS, RHS);
796 
797   // C2 is ODD
798   // LHS = XOR(Y, C1), Y = AND(Z, C2), C1 == (C2 + 1) => LHS == NEG(OR(Z, ~C2))
799   // ADD(LHS, RHS) == SUB(RHS, OR(Z, ~C2))
800   if (match(LHS, m_Xor(m_Value(Y), m_APInt(C1))))
801     if (C1->countTrailingZeros() == 0)
802       if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && *C1 == (*C2 + 1)) {
803         Value *NewOr = Builder.CreateOr(Z, ~(*C2));
804         return Builder.CreateSub(RHS, NewOr, "sub");
805       }
806   return nullptr;
807 }
808 
809 /// Wrapping flags may allow combining constants separated by an extend.
810 static Instruction *foldNoWrapAdd(BinaryOperator &Add,
811                                   InstCombiner::BuilderTy &Builder) {
812   Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1);
813   Type *Ty = Add.getType();
814   Constant *Op1C;
815   if (!match(Op1, m_Constant(Op1C)))
816     return nullptr;
817 
818   // Try this match first because it results in an add in the narrow type.
819   // (zext (X +nuw C2)) + C1 --> zext (X + (C2 + trunc(C1)))
820   Value *X;
821   const APInt *C1, *C2;
822   if (match(Op1, m_APInt(C1)) &&
823       match(Op0, m_OneUse(m_ZExt(m_NUWAdd(m_Value(X), m_APInt(C2))))) &&
824       C1->isNegative() && C1->sge(-C2->sext(C1->getBitWidth()))) {
825     Constant *NewC =
826         ConstantInt::get(X->getType(), *C2 + C1->trunc(C2->getBitWidth()));
827     return new ZExtInst(Builder.CreateNUWAdd(X, NewC), Ty);
828   }
829 
830   // More general combining of constants in the wide type.
831   // (sext (X +nsw NarrowC)) + C --> (sext X) + (sext(NarrowC) + C)
832   Constant *NarrowC;
833   if (match(Op0, m_OneUse(m_SExt(m_NSWAdd(m_Value(X), m_Constant(NarrowC)))))) {
834     Constant *WideC = ConstantExpr::getSExt(NarrowC, Ty);
835     Constant *NewC = ConstantExpr::getAdd(WideC, Op1C);
836     Value *WideX = Builder.CreateSExt(X, Ty);
837     return BinaryOperator::CreateAdd(WideX, NewC);
838   }
839   // (zext (X +nuw NarrowC)) + C --> (zext X) + (zext(NarrowC) + C)
840   if (match(Op0, m_OneUse(m_ZExt(m_NUWAdd(m_Value(X), m_Constant(NarrowC)))))) {
841     Constant *WideC = ConstantExpr::getZExt(NarrowC, Ty);
842     Constant *NewC = ConstantExpr::getAdd(WideC, Op1C);
843     Value *WideX = Builder.CreateZExt(X, Ty);
844     return BinaryOperator::CreateAdd(WideX, NewC);
845   }
846 
847   return nullptr;
848 }
849 
850 Instruction *InstCombinerImpl::foldAddWithConstant(BinaryOperator &Add) {
851   Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1);
852   Constant *Op1C;
853   if (!match(Op1, m_ImmConstant(Op1C)))
854     return nullptr;
855 
856   if (Instruction *NV = foldBinOpIntoSelectOrPhi(Add))
857     return NV;
858 
859   Value *X;
860   Constant *Op00C;
861 
862   // add (sub C1, X), C2 --> sub (add C1, C2), X
863   if (match(Op0, m_Sub(m_Constant(Op00C), m_Value(X))))
864     return BinaryOperator::CreateSub(ConstantExpr::getAdd(Op00C, Op1C), X);
865 
866   Value *Y;
867 
868   // add (sub X, Y), -1 --> add (not Y), X
869   if (match(Op0, m_OneUse(m_Sub(m_Value(X), m_Value(Y)))) &&
870       match(Op1, m_AllOnes()))
871     return BinaryOperator::CreateAdd(Builder.CreateNot(Y), X);
872 
873   // zext(bool) + C -> bool ? C + 1 : C
874   if (match(Op0, m_ZExt(m_Value(X))) &&
875       X->getType()->getScalarSizeInBits() == 1)
876     return SelectInst::Create(X, InstCombiner::AddOne(Op1C), Op1);
877   // sext(bool) + C -> bool ? C - 1 : C
878   if (match(Op0, m_SExt(m_Value(X))) &&
879       X->getType()->getScalarSizeInBits() == 1)
880     return SelectInst::Create(X, InstCombiner::SubOne(Op1C), Op1);
881 
882   // ~X + C --> (C-1) - X
883   if (match(Op0, m_Not(m_Value(X))))
884     return BinaryOperator::CreateSub(InstCombiner::SubOne(Op1C), X);
885 
886   const APInt *C;
887   if (!match(Op1, m_APInt(C)))
888     return nullptr;
889 
890   // (X | Op01C) + Op1C --> X + (Op01C + Op1C) iff the `or` is actually an `add`
891   Constant *Op01C;
892   if (match(Op0, m_Or(m_Value(X), m_ImmConstant(Op01C))) &&
893       haveNoCommonBitsSet(X, Op01C, DL, &AC, &Add, &DT))
894     return BinaryOperator::CreateAdd(X, ConstantExpr::getAdd(Op01C, Op1C));
895 
896   // (X | C2) + C --> (X | C2) ^ C2 iff (C2 == -C)
897   const APInt *C2;
898   if (match(Op0, m_Or(m_Value(), m_APInt(C2))) && *C2 == -*C)
899     return BinaryOperator::CreateXor(Op0, ConstantInt::get(Add.getType(), *C2));
900 
901   if (C->isSignMask()) {
902     // If wrapping is not allowed, then the addition must set the sign bit:
903     // X + (signmask) --> X | signmask
904     if (Add.hasNoSignedWrap() || Add.hasNoUnsignedWrap())
905       return BinaryOperator::CreateOr(Op0, Op1);
906 
907     // If wrapping is allowed, then the addition flips the sign bit of LHS:
908     // X + (signmask) --> X ^ signmask
909     return BinaryOperator::CreateXor(Op0, Op1);
910   }
911 
912   // Is this add the last step in a convoluted sext?
913   // add(zext(xor i16 X, -32768), -32768) --> sext X
914   Type *Ty = Add.getType();
915   if (match(Op0, m_ZExt(m_Xor(m_Value(X), m_APInt(C2)))) &&
916       C2->isMinSignedValue() && C2->sext(Ty->getScalarSizeInBits()) == *C)
917     return CastInst::Create(Instruction::SExt, X, Ty);
918 
919   if (match(Op0, m_Xor(m_Value(X), m_APInt(C2)))) {
920     // (X ^ signmask) + C --> (X + (signmask ^ C))
921     if (C2->isSignMask())
922       return BinaryOperator::CreateAdd(X, ConstantInt::get(Ty, *C2 ^ *C));
923 
924     // If X has no high-bits set above an xor mask:
925     // add (xor X, LowMaskC), C --> sub (LowMaskC + C), X
926     if (C2->isMask()) {
927       KnownBits LHSKnown = computeKnownBits(X, 0, &Add);
928       if ((*C2 | LHSKnown.Zero).isAllOnes())
929         return BinaryOperator::CreateSub(ConstantInt::get(Ty, *C2 + *C), X);
930     }
931 
932     // Look for a math+logic pattern that corresponds to sext-in-register of a
933     // value with cleared high bits. Convert that into a pair of shifts:
934     // add (xor X, 0x80), 0xF..F80 --> (X << ShAmtC) >>s ShAmtC
935     // add (xor X, 0xF..F80), 0x80 --> (X << ShAmtC) >>s ShAmtC
936     if (Op0->hasOneUse() && *C2 == -(*C)) {
937       unsigned BitWidth = Ty->getScalarSizeInBits();
938       unsigned ShAmt = 0;
939       if (C->isPowerOf2())
940         ShAmt = BitWidth - C->logBase2() - 1;
941       else if (C2->isPowerOf2())
942         ShAmt = BitWidth - C2->logBase2() - 1;
943       if (ShAmt && MaskedValueIsZero(X, APInt::getHighBitsSet(BitWidth, ShAmt),
944                                      0, &Add)) {
945         Constant *ShAmtC = ConstantInt::get(Ty, ShAmt);
946         Value *NewShl = Builder.CreateShl(X, ShAmtC, "sext");
947         return BinaryOperator::CreateAShr(NewShl, ShAmtC);
948       }
949     }
950   }
951 
952   if (C->isOne() && Op0->hasOneUse()) {
953     // add (sext i1 X), 1 --> zext (not X)
954     // TODO: The smallest IR representation is (select X, 0, 1), and that would
955     // not require the one-use check. But we need to remove a transform in
956     // visitSelect and make sure that IR value tracking for select is equal or
957     // better than for these ops.
958     if (match(Op0, m_SExt(m_Value(X))) &&
959         X->getType()->getScalarSizeInBits() == 1)
960       return new ZExtInst(Builder.CreateNot(X), Ty);
961 
962     // Shifts and add used to flip and mask off the low bit:
963     // add (ashr (shl i32 X, 31), 31), 1 --> and (not X), 1
964     const APInt *C3;
965     if (match(Op0, m_AShr(m_Shl(m_Value(X), m_APInt(C2)), m_APInt(C3))) &&
966         C2 == C3 && *C2 == Ty->getScalarSizeInBits() - 1) {
967       Value *NotX = Builder.CreateNot(X);
968       return BinaryOperator::CreateAnd(NotX, ConstantInt::get(Ty, 1));
969     }
970   }
971 
972   // If all bits affected by the add are included in a high-bit-mask, do the
973   // add before the mask op:
974   // (X & 0xFF00) + xx00 --> (X + xx00) & 0xFF00
975   if (match(Op0, m_OneUse(m_And(m_Value(X), m_APInt(C2)))) &&
976       C2->isNegative() && C2->isShiftedMask() && *C == (*C & *C2)) {
977     Value *NewAdd = Builder.CreateAdd(X, ConstantInt::get(Ty, *C));
978     return BinaryOperator::CreateAnd(NewAdd, ConstantInt::get(Ty, *C2));
979   }
980 
981   return nullptr;
982 }
983 
984 // Matches multiplication expression Op * C where C is a constant. Returns the
985 // constant value in C and the other operand in Op. Returns true if such a
986 // match is found.
987 static bool MatchMul(Value *E, Value *&Op, APInt &C) {
988   const APInt *AI;
989   if (match(E, m_Mul(m_Value(Op), m_APInt(AI)))) {
990     C = *AI;
991     return true;
992   }
993   if (match(E, m_Shl(m_Value(Op), m_APInt(AI)))) {
994     C = APInt(AI->getBitWidth(), 1);
995     C <<= *AI;
996     return true;
997   }
998   return false;
999 }
1000 
1001 // Matches remainder expression Op % C where C is a constant. Returns the
1002 // constant value in C and the other operand in Op. Returns the signedness of
1003 // the remainder operation in IsSigned. Returns true if such a match is
1004 // found.
1005 static bool MatchRem(Value *E, Value *&Op, APInt &C, bool &IsSigned) {
1006   const APInt *AI;
1007   IsSigned = false;
1008   if (match(E, m_SRem(m_Value(Op), m_APInt(AI)))) {
1009     IsSigned = true;
1010     C = *AI;
1011     return true;
1012   }
1013   if (match(E, m_URem(m_Value(Op), m_APInt(AI)))) {
1014     C = *AI;
1015     return true;
1016   }
1017   if (match(E, m_And(m_Value(Op), m_APInt(AI))) && (*AI + 1).isPowerOf2()) {
1018     C = *AI + 1;
1019     return true;
1020   }
1021   return false;
1022 }
1023 
1024 // Matches division expression Op / C with the given signedness as indicated
1025 // by IsSigned, where C is a constant. Returns the constant value in C and the
1026 // other operand in Op. Returns true if such a match is found.
1027 static bool MatchDiv(Value *E, Value *&Op, APInt &C, bool IsSigned) {
1028   const APInt *AI;
1029   if (IsSigned && match(E, m_SDiv(m_Value(Op), m_APInt(AI)))) {
1030     C = *AI;
1031     return true;
1032   }
1033   if (!IsSigned) {
1034     if (match(E, m_UDiv(m_Value(Op), m_APInt(AI)))) {
1035       C = *AI;
1036       return true;
1037     }
1038     if (match(E, m_LShr(m_Value(Op), m_APInt(AI)))) {
1039       C = APInt(AI->getBitWidth(), 1);
1040       C <<= *AI;
1041       return true;
1042     }
1043   }
1044   return false;
1045 }
1046 
1047 // Returns whether C0 * C1 with the given signedness overflows.
1048 static bool MulWillOverflow(APInt &C0, APInt &C1, bool IsSigned) {
1049   bool overflow;
1050   if (IsSigned)
1051     (void)C0.smul_ov(C1, overflow);
1052   else
1053     (void)C0.umul_ov(C1, overflow);
1054   return overflow;
1055 }
1056 
1057 // Simplifies X % C0 + (( X / C0 ) % C1) * C0 to X % (C0 * C1), where (C0 * C1)
1058 // does not overflow.
1059 Value *InstCombinerImpl::SimplifyAddWithRemainder(BinaryOperator &I) {
1060   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1061   Value *X, *MulOpV;
1062   APInt C0, MulOpC;
1063   bool IsSigned;
1064   // Match I = X % C0 + MulOpV * C0
1065   if (((MatchRem(LHS, X, C0, IsSigned) && MatchMul(RHS, MulOpV, MulOpC)) ||
1066        (MatchRem(RHS, X, C0, IsSigned) && MatchMul(LHS, MulOpV, MulOpC))) &&
1067       C0 == MulOpC) {
1068     Value *RemOpV;
1069     APInt C1;
1070     bool Rem2IsSigned;
1071     // Match MulOpC = RemOpV % C1
1072     if (MatchRem(MulOpV, RemOpV, C1, Rem2IsSigned) &&
1073         IsSigned == Rem2IsSigned) {
1074       Value *DivOpV;
1075       APInt DivOpC;
1076       // Match RemOpV = X / C0
1077       if (MatchDiv(RemOpV, DivOpV, DivOpC, IsSigned) && X == DivOpV &&
1078           C0 == DivOpC && !MulWillOverflow(C0, C1, IsSigned)) {
1079         Value *NewDivisor = ConstantInt::get(X->getType(), C0 * C1);
1080         return IsSigned ? Builder.CreateSRem(X, NewDivisor, "srem")
1081                         : Builder.CreateURem(X, NewDivisor, "urem");
1082       }
1083     }
1084   }
1085 
1086   return nullptr;
1087 }
1088 
1089 /// Fold
1090 ///   (1 << NBits) - 1
1091 /// Into:
1092 ///   ~(-(1 << NBits))
1093 /// Because a 'not' is better for bit-tracking analysis and other transforms
1094 /// than an 'add'. The new shl is always nsw, and is nuw if old `and` was.
1095 static Instruction *canonicalizeLowbitMask(BinaryOperator &I,
1096                                            InstCombiner::BuilderTy &Builder) {
1097   Value *NBits;
1098   if (!match(&I, m_Add(m_OneUse(m_Shl(m_One(), m_Value(NBits))), m_AllOnes())))
1099     return nullptr;
1100 
1101   Constant *MinusOne = Constant::getAllOnesValue(NBits->getType());
1102   Value *NotMask = Builder.CreateShl(MinusOne, NBits, "notmask");
1103   // Be wary of constant folding.
1104   if (auto *BOp = dyn_cast<BinaryOperator>(NotMask)) {
1105     // Always NSW. But NUW propagates from `add`.
1106     BOp->setHasNoSignedWrap();
1107     BOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1108   }
1109 
1110   return BinaryOperator::CreateNot(NotMask, I.getName());
1111 }
1112 
1113 static Instruction *foldToUnsignedSaturatedAdd(BinaryOperator &I) {
1114   assert(I.getOpcode() == Instruction::Add && "Expecting add instruction");
1115   Type *Ty = I.getType();
1116   auto getUAddSat = [&]() {
1117     return Intrinsic::getDeclaration(I.getModule(), Intrinsic::uadd_sat, Ty);
1118   };
1119 
1120   // add (umin X, ~Y), Y --> uaddsat X, Y
1121   Value *X, *Y;
1122   if (match(&I, m_c_Add(m_c_UMin(m_Value(X), m_Not(m_Value(Y))),
1123                         m_Deferred(Y))))
1124     return CallInst::Create(getUAddSat(), { X, Y });
1125 
1126   // add (umin X, ~C), C --> uaddsat X, C
1127   const APInt *C, *NotC;
1128   if (match(&I, m_Add(m_UMin(m_Value(X), m_APInt(NotC)), m_APInt(C))) &&
1129       *C == ~*NotC)
1130     return CallInst::Create(getUAddSat(), { X, ConstantInt::get(Ty, *C) });
1131 
1132   return nullptr;
1133 }
1134 
1135 Instruction *InstCombinerImpl::
1136     canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
1137         BinaryOperator &I) {
1138   assert((I.getOpcode() == Instruction::Add ||
1139           I.getOpcode() == Instruction::Or ||
1140           I.getOpcode() == Instruction::Sub) &&
1141          "Expecting add/or/sub instruction");
1142 
1143   // We have a subtraction/addition between a (potentially truncated) *logical*
1144   // right-shift of X and a "select".
1145   Value *X, *Select;
1146   Instruction *LowBitsToSkip, *Extract;
1147   if (!match(&I, m_c_BinOp(m_TruncOrSelf(m_CombineAnd(
1148                                m_LShr(m_Value(X), m_Instruction(LowBitsToSkip)),
1149                                m_Instruction(Extract))),
1150                            m_Value(Select))))
1151     return nullptr;
1152 
1153   // `add`/`or` is commutative; but for `sub`, "select" *must* be on RHS.
1154   if (I.getOpcode() == Instruction::Sub && I.getOperand(1) != Select)
1155     return nullptr;
1156 
1157   Type *XTy = X->getType();
1158   bool HadTrunc = I.getType() != XTy;
1159 
1160   // If there was a truncation of extracted value, then we'll need to produce
1161   // one extra instruction, so we need to ensure one instruction will go away.
1162   if (HadTrunc && !match(&I, m_c_BinOp(m_OneUse(m_Value()), m_Value())))
1163     return nullptr;
1164 
1165   // Extraction should extract high NBits bits, with shift amount calculated as:
1166   //   low bits to skip = shift bitwidth - high bits to extract
1167   // The shift amount itself may be extended, and we need to look past zero-ext
1168   // when matching NBits, that will matter for matching later.
1169   Constant *C;
1170   Value *NBits;
1171   if (!match(
1172           LowBitsToSkip,
1173           m_ZExtOrSelf(m_Sub(m_Constant(C), m_ZExtOrSelf(m_Value(NBits))))) ||
1174       !match(C, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ,
1175                                    APInt(C->getType()->getScalarSizeInBits(),
1176                                          X->getType()->getScalarSizeInBits()))))
1177     return nullptr;
1178 
1179   // Sign-extending value can be zero-extended if we `sub`tract it,
1180   // or sign-extended otherwise.
1181   auto SkipExtInMagic = [&I](Value *&V) {
1182     if (I.getOpcode() == Instruction::Sub)
1183       match(V, m_ZExtOrSelf(m_Value(V)));
1184     else
1185       match(V, m_SExtOrSelf(m_Value(V)));
1186   };
1187 
1188   // Now, finally validate the sign-extending magic.
1189   // `select` itself may be appropriately extended, look past that.
1190   SkipExtInMagic(Select);
1191 
1192   ICmpInst::Predicate Pred;
1193   const APInt *Thr;
1194   Value *SignExtendingValue, *Zero;
1195   bool ShouldSignext;
1196   // It must be a select between two values we will later establish to be a
1197   // sign-extending value and a zero constant. The condition guarding the
1198   // sign-extension must be based on a sign bit of the same X we had in `lshr`.
1199   if (!match(Select, m_Select(m_ICmp(Pred, m_Specific(X), m_APInt(Thr)),
1200                               m_Value(SignExtendingValue), m_Value(Zero))) ||
1201       !isSignBitCheck(Pred, *Thr, ShouldSignext))
1202     return nullptr;
1203 
1204   // icmp-select pair is commutative.
1205   if (!ShouldSignext)
1206     std::swap(SignExtendingValue, Zero);
1207 
1208   // If we should not perform sign-extension then we must add/or/subtract zero.
1209   if (!match(Zero, m_Zero()))
1210     return nullptr;
1211   // Otherwise, it should be some constant, left-shifted by the same NBits we
1212   // had in `lshr`. Said left-shift can also be appropriately extended.
1213   // Again, we must look past zero-ext when looking for NBits.
1214   SkipExtInMagic(SignExtendingValue);
1215   Constant *SignExtendingValueBaseConstant;
1216   if (!match(SignExtendingValue,
1217              m_Shl(m_Constant(SignExtendingValueBaseConstant),
1218                    m_ZExtOrSelf(m_Specific(NBits)))))
1219     return nullptr;
1220   // If we `sub`, then the constant should be one, else it should be all-ones.
1221   if (I.getOpcode() == Instruction::Sub
1222           ? !match(SignExtendingValueBaseConstant, m_One())
1223           : !match(SignExtendingValueBaseConstant, m_AllOnes()))
1224     return nullptr;
1225 
1226   auto *NewAShr = BinaryOperator::CreateAShr(X, LowBitsToSkip,
1227                                              Extract->getName() + ".sext");
1228   NewAShr->copyIRFlags(Extract); // Preserve `exact`-ness.
1229   if (!HadTrunc)
1230     return NewAShr;
1231 
1232   Builder.Insert(NewAShr);
1233   return TruncInst::CreateTruncOrBitCast(NewAShr, I.getType());
1234 }
1235 
1236 /// This is a specialization of a more general transform from
1237 /// SimplifyUsingDistributiveLaws. If that code can be made to work optimally
1238 /// for multi-use cases or propagating nsw/nuw, then we would not need this.
1239 static Instruction *factorizeMathWithShlOps(BinaryOperator &I,
1240                                             InstCombiner::BuilderTy &Builder) {
1241   // TODO: Also handle mul by doubling the shift amount?
1242   assert((I.getOpcode() == Instruction::Add ||
1243           I.getOpcode() == Instruction::Sub) &&
1244          "Expected add/sub");
1245   auto *Op0 = dyn_cast<BinaryOperator>(I.getOperand(0));
1246   auto *Op1 = dyn_cast<BinaryOperator>(I.getOperand(1));
1247   if (!Op0 || !Op1 || !(Op0->hasOneUse() || Op1->hasOneUse()))
1248     return nullptr;
1249 
1250   Value *X, *Y, *ShAmt;
1251   if (!match(Op0, m_Shl(m_Value(X), m_Value(ShAmt))) ||
1252       !match(Op1, m_Shl(m_Value(Y), m_Specific(ShAmt))))
1253     return nullptr;
1254 
1255   // No-wrap propagates only when all ops have no-wrap.
1256   bool HasNSW = I.hasNoSignedWrap() && Op0->hasNoSignedWrap() &&
1257                 Op1->hasNoSignedWrap();
1258   bool HasNUW = I.hasNoUnsignedWrap() && Op0->hasNoUnsignedWrap() &&
1259                 Op1->hasNoUnsignedWrap();
1260 
1261   // add/sub (X << ShAmt), (Y << ShAmt) --> (add/sub X, Y) << ShAmt
1262   Value *NewMath = Builder.CreateBinOp(I.getOpcode(), X, Y);
1263   if (auto *NewI = dyn_cast<BinaryOperator>(NewMath)) {
1264     NewI->setHasNoSignedWrap(HasNSW);
1265     NewI->setHasNoUnsignedWrap(HasNUW);
1266   }
1267   auto *NewShl = BinaryOperator::CreateShl(NewMath, ShAmt);
1268   NewShl->setHasNoSignedWrap(HasNSW);
1269   NewShl->setHasNoUnsignedWrap(HasNUW);
1270   return NewShl;
1271 }
1272 
1273 Instruction *InstCombinerImpl::visitAdd(BinaryOperator &I) {
1274   if (Value *V = simplifyAddInst(I.getOperand(0), I.getOperand(1),
1275                                  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
1276                                  SQ.getWithInstruction(&I)))
1277     return replaceInstUsesWith(I, V);
1278 
1279   if (SimplifyAssociativeOrCommutative(I))
1280     return &I;
1281 
1282   if (Instruction *X = foldVectorBinop(I))
1283     return X;
1284 
1285   if (Instruction *Phi = foldBinopWithPhiOperands(I))
1286     return Phi;
1287 
1288   // (A*B)+(A*C) -> A*(B+C) etc
1289   if (Value *V = SimplifyUsingDistributiveLaws(I))
1290     return replaceInstUsesWith(I, V);
1291 
1292   if (Instruction *R = factorizeMathWithShlOps(I, Builder))
1293     return R;
1294 
1295   if (Instruction *X = foldAddWithConstant(I))
1296     return X;
1297 
1298   if (Instruction *X = foldNoWrapAdd(I, Builder))
1299     return X;
1300 
1301   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1302   Type *Ty = I.getType();
1303   if (Ty->isIntOrIntVectorTy(1))
1304     return BinaryOperator::CreateXor(LHS, RHS);
1305 
1306   // X + X --> X << 1
1307   if (LHS == RHS) {
1308     auto *Shl = BinaryOperator::CreateShl(LHS, ConstantInt::get(Ty, 1));
1309     Shl->setHasNoSignedWrap(I.hasNoSignedWrap());
1310     Shl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1311     return Shl;
1312   }
1313 
1314   Value *A, *B;
1315   if (match(LHS, m_Neg(m_Value(A)))) {
1316     // -A + -B --> -(A + B)
1317     if (match(RHS, m_Neg(m_Value(B))))
1318       return BinaryOperator::CreateNeg(Builder.CreateAdd(A, B));
1319 
1320     // -A + B --> B - A
1321     return BinaryOperator::CreateSub(RHS, A);
1322   }
1323 
1324   // A + -B  -->  A - B
1325   if (match(RHS, m_Neg(m_Value(B))))
1326     return BinaryOperator::CreateSub(LHS, B);
1327 
1328   if (Value *V = checkForNegativeOperand(I, Builder))
1329     return replaceInstUsesWith(I, V);
1330 
1331   // (A + 1) + ~B --> A - B
1332   // ~B + (A + 1) --> A - B
1333   // (~B + A) + 1 --> A - B
1334   // (A + ~B) + 1 --> A - B
1335   if (match(&I, m_c_BinOp(m_Add(m_Value(A), m_One()), m_Not(m_Value(B)))) ||
1336       match(&I, m_BinOp(m_c_Add(m_Not(m_Value(B)), m_Value(A)), m_One())))
1337     return BinaryOperator::CreateSub(A, B);
1338 
1339   // (A + RHS) + RHS --> A + (RHS << 1)
1340   if (match(LHS, m_OneUse(m_c_Add(m_Value(A), m_Specific(RHS)))))
1341     return BinaryOperator::CreateAdd(A, Builder.CreateShl(RHS, 1, "reass.add"));
1342 
1343   // LHS + (A + LHS) --> A + (LHS << 1)
1344   if (match(RHS, m_OneUse(m_c_Add(m_Value(A), m_Specific(LHS)))))
1345     return BinaryOperator::CreateAdd(A, Builder.CreateShl(LHS, 1, "reass.add"));
1346 
1347   {
1348     // (A + C1) + (C2 - B) --> (A - B) + (C1 + C2)
1349     Constant *C1, *C2;
1350     if (match(&I, m_c_Add(m_Add(m_Value(A), m_ImmConstant(C1)),
1351                           m_Sub(m_ImmConstant(C2), m_Value(B)))) &&
1352         (LHS->hasOneUse() || RHS->hasOneUse())) {
1353       Value *Sub = Builder.CreateSub(A, B);
1354       return BinaryOperator::CreateAdd(Sub, ConstantExpr::getAdd(C1, C2));
1355     }
1356   }
1357 
1358   // X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1)
1359   if (Value *V = SimplifyAddWithRemainder(I)) return replaceInstUsesWith(I, V);
1360 
1361   // ((X s/ C1) << C2) + X => X s% -C1 where -C1 is 1 << C2
1362   const APInt *C1, *C2;
1363   if (match(LHS, m_Shl(m_SDiv(m_Specific(RHS), m_APInt(C1)), m_APInt(C2)))) {
1364     APInt one(C2->getBitWidth(), 1);
1365     APInt minusC1 = -(*C1);
1366     if (minusC1 == (one << *C2)) {
1367       Constant *NewRHS = ConstantInt::get(RHS->getType(), minusC1);
1368       return BinaryOperator::CreateSRem(RHS, NewRHS);
1369     }
1370   }
1371 
1372   // (A & 2^C1) + A => A & (2^C1 - 1) iff bit C1 in A is a sign bit
1373   if (match(&I, m_c_Add(m_And(m_Value(A), m_APInt(C1)), m_Deferred(A))) &&
1374       C1->isPowerOf2() && (ComputeNumSignBits(A) > C1->countLeadingZeros())) {
1375     Constant *NewMask = ConstantInt::get(RHS->getType(), *C1 - 1);
1376     return BinaryOperator::CreateAnd(A, NewMask);
1377   }
1378 
1379   // A+B --> A|B iff A and B have no bits set in common.
1380   if (haveNoCommonBitsSet(LHS, RHS, DL, &AC, &I, &DT))
1381     return BinaryOperator::CreateOr(LHS, RHS);
1382 
1383   // add (select X 0 (sub n A)) A  -->  select X A n
1384   {
1385     SelectInst *SI = dyn_cast<SelectInst>(LHS);
1386     Value *A = RHS;
1387     if (!SI) {
1388       SI = dyn_cast<SelectInst>(RHS);
1389       A = LHS;
1390     }
1391     if (SI && SI->hasOneUse()) {
1392       Value *TV = SI->getTrueValue();
1393       Value *FV = SI->getFalseValue();
1394       Value *N;
1395 
1396       // Can we fold the add into the argument of the select?
1397       // We check both true and false select arguments for a matching subtract.
1398       if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A))))
1399         // Fold the add into the true select value.
1400         return SelectInst::Create(SI->getCondition(), N, A);
1401 
1402       if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A))))
1403         // Fold the add into the false select value.
1404         return SelectInst::Create(SI->getCondition(), A, N);
1405     }
1406   }
1407 
1408   if (Instruction *Ext = narrowMathIfNoOverflow(I))
1409     return Ext;
1410 
1411   // (add (xor A, B) (and A, B)) --> (or A, B)
1412   // (add (and A, B) (xor A, B)) --> (or A, B)
1413   if (match(&I, m_c_BinOp(m_Xor(m_Value(A), m_Value(B)),
1414                           m_c_And(m_Deferred(A), m_Deferred(B)))))
1415     return BinaryOperator::CreateOr(A, B);
1416 
1417   // (add (or A, B) (and A, B)) --> (add A, B)
1418   // (add (and A, B) (or A, B)) --> (add A, B)
1419   if (match(&I, m_c_BinOp(m_Or(m_Value(A), m_Value(B)),
1420                           m_c_And(m_Deferred(A), m_Deferred(B))))) {
1421     // Replacing operands in-place to preserve nuw/nsw flags.
1422     replaceOperand(I, 0, A);
1423     replaceOperand(I, 1, B);
1424     return &I;
1425   }
1426 
1427   // TODO(jingyue): Consider willNotOverflowSignedAdd and
1428   // willNotOverflowUnsignedAdd to reduce the number of invocations of
1429   // computeKnownBits.
1430   bool Changed = false;
1431   if (!I.hasNoSignedWrap() && willNotOverflowSignedAdd(LHS, RHS, I)) {
1432     Changed = true;
1433     I.setHasNoSignedWrap(true);
1434   }
1435   if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedAdd(LHS, RHS, I)) {
1436     Changed = true;
1437     I.setHasNoUnsignedWrap(true);
1438   }
1439 
1440   if (Instruction *V = canonicalizeLowbitMask(I, Builder))
1441     return V;
1442 
1443   if (Instruction *V =
1444           canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
1445     return V;
1446 
1447   if (Instruction *SatAdd = foldToUnsignedSaturatedAdd(I))
1448     return SatAdd;
1449 
1450   // usub.sat(A, B) + B => umax(A, B)
1451   if (match(&I, m_c_BinOp(
1452           m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Value(A), m_Value(B))),
1453           m_Deferred(B)))) {
1454     return replaceInstUsesWith(I,
1455         Builder.CreateIntrinsic(Intrinsic::umax, {I.getType()}, {A, B}));
1456   }
1457 
1458   // ctpop(A) + ctpop(B) => ctpop(A | B) if A and B have no bits set in common.
1459   if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(A)))) &&
1460       match(RHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(B)))) &&
1461       haveNoCommonBitsSet(A, B, DL, &AC, &I, &DT))
1462     return replaceInstUsesWith(
1463         I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
1464                                    {Builder.CreateOr(A, B)}));
1465 
1466   return Changed ? &I : nullptr;
1467 }
1468 
1469 /// Eliminate an op from a linear interpolation (lerp) pattern.
1470 static Instruction *factorizeLerp(BinaryOperator &I,
1471                                   InstCombiner::BuilderTy &Builder) {
1472   Value *X, *Y, *Z;
1473   if (!match(&I, m_c_FAdd(m_OneUse(m_c_FMul(m_Value(Y),
1474                                             m_OneUse(m_FSub(m_FPOne(),
1475                                                             m_Value(Z))))),
1476                           m_OneUse(m_c_FMul(m_Value(X), m_Deferred(Z))))))
1477     return nullptr;
1478 
1479   // (Y * (1.0 - Z)) + (X * Z) --> Y + Z * (X - Y) [8 commuted variants]
1480   Value *XY = Builder.CreateFSubFMF(X, Y, &I);
1481   Value *MulZ = Builder.CreateFMulFMF(Z, XY, &I);
1482   return BinaryOperator::CreateFAddFMF(Y, MulZ, &I);
1483 }
1484 
1485 /// Factor a common operand out of fadd/fsub of fmul/fdiv.
1486 static Instruction *factorizeFAddFSub(BinaryOperator &I,
1487                                       InstCombiner::BuilderTy &Builder) {
1488   assert((I.getOpcode() == Instruction::FAdd ||
1489           I.getOpcode() == Instruction::FSub) && "Expecting fadd/fsub");
1490   assert(I.hasAllowReassoc() && I.hasNoSignedZeros() &&
1491          "FP factorization requires FMF");
1492 
1493   if (Instruction *Lerp = factorizeLerp(I, Builder))
1494     return Lerp;
1495 
1496   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1497   if (!Op0->hasOneUse() || !Op1->hasOneUse())
1498     return nullptr;
1499 
1500   Value *X, *Y, *Z;
1501   bool IsFMul;
1502   if ((match(Op0, m_FMul(m_Value(X), m_Value(Z))) &&
1503        match(Op1, m_c_FMul(m_Value(Y), m_Specific(Z)))) ||
1504       (match(Op0, m_FMul(m_Value(Z), m_Value(X))) &&
1505        match(Op1, m_c_FMul(m_Value(Y), m_Specific(Z)))))
1506     IsFMul = true;
1507   else if (match(Op0, m_FDiv(m_Value(X), m_Value(Z))) &&
1508            match(Op1, m_FDiv(m_Value(Y), m_Specific(Z))))
1509     IsFMul = false;
1510   else
1511     return nullptr;
1512 
1513   // (X * Z) + (Y * Z) --> (X + Y) * Z
1514   // (X * Z) - (Y * Z) --> (X - Y) * Z
1515   // (X / Z) + (Y / Z) --> (X + Y) / Z
1516   // (X / Z) - (Y / Z) --> (X - Y) / Z
1517   bool IsFAdd = I.getOpcode() == Instruction::FAdd;
1518   Value *XY = IsFAdd ? Builder.CreateFAddFMF(X, Y, &I)
1519                      : Builder.CreateFSubFMF(X, Y, &I);
1520 
1521   // Bail out if we just created a denormal constant.
1522   // TODO: This is copied from a previous implementation. Is it necessary?
1523   const APFloat *C;
1524   if (match(XY, m_APFloat(C)) && !C->isNormal())
1525     return nullptr;
1526 
1527   return IsFMul ? BinaryOperator::CreateFMulFMF(XY, Z, &I)
1528                 : BinaryOperator::CreateFDivFMF(XY, Z, &I);
1529 }
1530 
1531 Instruction *InstCombinerImpl::visitFAdd(BinaryOperator &I) {
1532   if (Value *V = simplifyFAddInst(I.getOperand(0), I.getOperand(1),
1533                                   I.getFastMathFlags(),
1534                                   SQ.getWithInstruction(&I)))
1535     return replaceInstUsesWith(I, V);
1536 
1537   if (SimplifyAssociativeOrCommutative(I))
1538     return &I;
1539 
1540   if (Instruction *X = foldVectorBinop(I))
1541     return X;
1542 
1543   if (Instruction *Phi = foldBinopWithPhiOperands(I))
1544     return Phi;
1545 
1546   if (Instruction *FoldedFAdd = foldBinOpIntoSelectOrPhi(I))
1547     return FoldedFAdd;
1548 
1549   // (-X) + Y --> Y - X
1550   Value *X, *Y;
1551   if (match(&I, m_c_FAdd(m_FNeg(m_Value(X)), m_Value(Y))))
1552     return BinaryOperator::CreateFSubFMF(Y, X, &I);
1553 
1554   // Similar to above, but look through fmul/fdiv for the negated term.
1555   // (-X * Y) + Z --> Z - (X * Y) [4 commuted variants]
1556   Value *Z;
1557   if (match(&I, m_c_FAdd(m_OneUse(m_c_FMul(m_FNeg(m_Value(X)), m_Value(Y))),
1558                          m_Value(Z)))) {
1559     Value *XY = Builder.CreateFMulFMF(X, Y, &I);
1560     return BinaryOperator::CreateFSubFMF(Z, XY, &I);
1561   }
1562   // (-X / Y) + Z --> Z - (X / Y) [2 commuted variants]
1563   // (X / -Y) + Z --> Z - (X / Y) [2 commuted variants]
1564   if (match(&I, m_c_FAdd(m_OneUse(m_FDiv(m_FNeg(m_Value(X)), m_Value(Y))),
1565                          m_Value(Z))) ||
1566       match(&I, m_c_FAdd(m_OneUse(m_FDiv(m_Value(X), m_FNeg(m_Value(Y)))),
1567                          m_Value(Z)))) {
1568     Value *XY = Builder.CreateFDivFMF(X, Y, &I);
1569     return BinaryOperator::CreateFSubFMF(Z, XY, &I);
1570   }
1571 
1572   // Check for (fadd double (sitofp x), y), see if we can merge this into an
1573   // integer add followed by a promotion.
1574   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1575   if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) {
1576     Value *LHSIntVal = LHSConv->getOperand(0);
1577     Type *FPType = LHSConv->getType();
1578 
1579     // TODO: This check is overly conservative. In many cases known bits
1580     // analysis can tell us that the result of the addition has less significant
1581     // bits than the integer type can hold.
1582     auto IsValidPromotion = [](Type *FTy, Type *ITy) {
1583       Type *FScalarTy = FTy->getScalarType();
1584       Type *IScalarTy = ITy->getScalarType();
1585 
1586       // Do we have enough bits in the significand to represent the result of
1587       // the integer addition?
1588       unsigned MaxRepresentableBits =
1589           APFloat::semanticsPrecision(FScalarTy->getFltSemantics());
1590       return IScalarTy->getIntegerBitWidth() <= MaxRepresentableBits;
1591     };
1592 
1593     // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst))
1594     // ... if the constant fits in the integer value.  This is useful for things
1595     // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer
1596     // requires a constant pool load, and generally allows the add to be better
1597     // instcombined.
1598     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS))
1599       if (IsValidPromotion(FPType, LHSIntVal->getType())) {
1600         Constant *CI =
1601           ConstantExpr::getFPToSI(CFP, LHSIntVal->getType());
1602         if (LHSConv->hasOneUse() &&
1603             ConstantExpr::getSIToFP(CI, I.getType()) == CFP &&
1604             willNotOverflowSignedAdd(LHSIntVal, CI, I)) {
1605           // Insert the new integer add.
1606           Value *NewAdd = Builder.CreateNSWAdd(LHSIntVal, CI, "addconv");
1607           return new SIToFPInst(NewAdd, I.getType());
1608         }
1609       }
1610 
1611     // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y))
1612     if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) {
1613       Value *RHSIntVal = RHSConv->getOperand(0);
1614       // It's enough to check LHS types only because we require int types to
1615       // be the same for this transform.
1616       if (IsValidPromotion(FPType, LHSIntVal->getType())) {
1617         // Only do this if x/y have the same type, if at least one of them has a
1618         // single use (so we don't increase the number of int->fp conversions),
1619         // and if the integer add will not overflow.
1620         if (LHSIntVal->getType() == RHSIntVal->getType() &&
1621             (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
1622             willNotOverflowSignedAdd(LHSIntVal, RHSIntVal, I)) {
1623           // Insert the new integer add.
1624           Value *NewAdd = Builder.CreateNSWAdd(LHSIntVal, RHSIntVal, "addconv");
1625           return new SIToFPInst(NewAdd, I.getType());
1626         }
1627       }
1628     }
1629   }
1630 
1631   // Handle specials cases for FAdd with selects feeding the operation
1632   if (Value *V = SimplifySelectsFeedingBinaryOp(I, LHS, RHS))
1633     return replaceInstUsesWith(I, V);
1634 
1635   if (I.hasAllowReassoc() && I.hasNoSignedZeros()) {
1636     if (Instruction *F = factorizeFAddFSub(I, Builder))
1637       return F;
1638 
1639     // Try to fold fadd into start value of reduction intrinsic.
1640     if (match(&I, m_c_FAdd(m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(
1641                                m_AnyZeroFP(), m_Value(X))),
1642                            m_Value(Y)))) {
1643       // fadd (rdx 0.0, X), Y --> rdx Y, X
1644       return replaceInstUsesWith(
1645           I, Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,
1646                                      {X->getType()}, {Y, X}, &I));
1647     }
1648     const APFloat *StartC, *C;
1649     if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(
1650                        m_APFloat(StartC), m_Value(X)))) &&
1651         match(RHS, m_APFloat(C))) {
1652       // fadd (rdx StartC, X), C --> rdx (C + StartC), X
1653       Constant *NewStartC = ConstantFP::get(I.getType(), *C + *StartC);
1654       return replaceInstUsesWith(
1655           I, Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,
1656                                      {X->getType()}, {NewStartC, X}, &I));
1657     }
1658 
1659     // (X * MulC) + X --> X * (MulC + 1.0)
1660     Constant *MulC;
1661     if (match(&I, m_c_FAdd(m_FMul(m_Value(X), m_ImmConstant(MulC)),
1662                            m_Deferred(X)))) {
1663       if (Constant *NewMulC = ConstantFoldBinaryOpOperands(
1664               Instruction::FAdd, MulC, ConstantFP::get(I.getType(), 1.0), DL))
1665         return BinaryOperator::CreateFMulFMF(X, NewMulC, &I);
1666     }
1667 
1668     if (Value *V = FAddCombine(Builder).simplify(&I))
1669       return replaceInstUsesWith(I, V);
1670   }
1671 
1672   return nullptr;
1673 }
1674 
1675 /// Optimize pointer differences into the same array into a size.  Consider:
1676 ///  &A[10] - &A[0]: we should compile this to "10".  LHS/RHS are the pointer
1677 /// operands to the ptrtoint instructions for the LHS/RHS of the subtract.
1678 Value *InstCombinerImpl::OptimizePointerDifference(Value *LHS, Value *RHS,
1679                                                    Type *Ty, bool IsNUW) {
1680   // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize
1681   // this.
1682   bool Swapped = false;
1683   GEPOperator *GEP1 = nullptr, *GEP2 = nullptr;
1684   if (!isa<GEPOperator>(LHS) && isa<GEPOperator>(RHS)) {
1685     std::swap(LHS, RHS);
1686     Swapped = true;
1687   }
1688 
1689   // Require at least one GEP with a common base pointer on both sides.
1690   if (auto *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
1691     // (gep X, ...) - X
1692     if (LHSGEP->getOperand(0)->stripPointerCasts() ==
1693         RHS->stripPointerCasts()) {
1694       GEP1 = LHSGEP;
1695     } else if (auto *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
1696       // (gep X, ...) - (gep X, ...)
1697       if (LHSGEP->getOperand(0)->stripPointerCasts() ==
1698           RHSGEP->getOperand(0)->stripPointerCasts()) {
1699         GEP1 = LHSGEP;
1700         GEP2 = RHSGEP;
1701       }
1702     }
1703   }
1704 
1705   if (!GEP1)
1706     return nullptr;
1707 
1708   if (GEP2) {
1709     // (gep X, ...) - (gep X, ...)
1710     //
1711     // Avoid duplicating the arithmetic if there are more than one non-constant
1712     // indices between the two GEPs and either GEP has a non-constant index and
1713     // multiple users. If zero non-constant index, the result is a constant and
1714     // there is no duplication. If one non-constant index, the result is an add
1715     // or sub with a constant, which is no larger than the original code, and
1716     // there's no duplicated arithmetic, even if either GEP has multiple
1717     // users. If more than one non-constant indices combined, as long as the GEP
1718     // with at least one non-constant index doesn't have multiple users, there
1719     // is no duplication.
1720     unsigned NumNonConstantIndices1 = GEP1->countNonConstantIndices();
1721     unsigned NumNonConstantIndices2 = GEP2->countNonConstantIndices();
1722     if (NumNonConstantIndices1 + NumNonConstantIndices2 > 1 &&
1723         ((NumNonConstantIndices1 > 0 && !GEP1->hasOneUse()) ||
1724          (NumNonConstantIndices2 > 0 && !GEP2->hasOneUse()))) {
1725       return nullptr;
1726     }
1727   }
1728 
1729   // Emit the offset of the GEP and an intptr_t.
1730   Value *Result = EmitGEPOffset(GEP1);
1731 
1732   // If this is a single inbounds GEP and the original sub was nuw,
1733   // then the final multiplication is also nuw.
1734   if (auto *I = dyn_cast<Instruction>(Result))
1735     if (IsNUW && !GEP2 && !Swapped && GEP1->isInBounds() &&
1736         I->getOpcode() == Instruction::Mul)
1737       I->setHasNoUnsignedWrap();
1738 
1739   // If we have a 2nd GEP of the same base pointer, subtract the offsets.
1740   // If both GEPs are inbounds, then the subtract does not have signed overflow.
1741   if (GEP2) {
1742     Value *Offset = EmitGEPOffset(GEP2);
1743     Result = Builder.CreateSub(Result, Offset, "gepdiff", /* NUW */ false,
1744                                GEP1->isInBounds() && GEP2->isInBounds());
1745   }
1746 
1747   // If we have p - gep(p, ...)  then we have to negate the result.
1748   if (Swapped)
1749     Result = Builder.CreateNeg(Result, "diff.neg");
1750 
1751   return Builder.CreateIntCast(Result, Ty, true);
1752 }
1753 
1754 static Instruction *foldSubOfMinMax(BinaryOperator &I,
1755                                     InstCombiner::BuilderTy &Builder) {
1756   Value *Op0 = I.getOperand(0);
1757   Value *Op1 = I.getOperand(1);
1758   Type *Ty = I.getType();
1759   auto *MinMax = dyn_cast<MinMaxIntrinsic>(Op1);
1760   if (!MinMax)
1761     return nullptr;
1762 
1763   // sub(add(X,Y), s/umin(X,Y)) --> s/umax(X,Y)
1764   // sub(add(X,Y), s/umax(X,Y)) --> s/umin(X,Y)
1765   Value *X = MinMax->getLHS();
1766   Value *Y = MinMax->getRHS();
1767   if (match(Op0, m_c_Add(m_Specific(X), m_Specific(Y))) &&
1768       (Op0->hasOneUse() || Op1->hasOneUse())) {
1769     Intrinsic::ID InvID = getInverseMinMaxIntrinsic(MinMax->getIntrinsicID());
1770     Function *F = Intrinsic::getDeclaration(I.getModule(), InvID, Ty);
1771     return CallInst::Create(F, {X, Y});
1772   }
1773 
1774   // sub(add(X,Y),umin(Y,Z)) --> add(X,usub.sat(Y,Z))
1775   // sub(add(X,Z),umin(Y,Z)) --> add(X,usub.sat(Z,Y))
1776   Value *Z;
1777   if (match(Op1, m_OneUse(m_UMin(m_Value(Y), m_Value(Z))))) {
1778     if (match(Op0, m_OneUse(m_c_Add(m_Specific(Y), m_Value(X))))) {
1779       Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, Ty, {Y, Z});
1780       return BinaryOperator::CreateAdd(X, USub);
1781     }
1782     if (match(Op0, m_OneUse(m_c_Add(m_Specific(Z), m_Value(X))))) {
1783       Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, Ty, {Z, Y});
1784       return BinaryOperator::CreateAdd(X, USub);
1785     }
1786   }
1787 
1788   // sub Op0, smin((sub nsw Op0, Z), 0) --> smax Op0, Z
1789   // sub Op0, smax((sub nsw Op0, Z), 0) --> smin Op0, Z
1790   if (MinMax->isSigned() && match(Y, m_ZeroInt()) &&
1791       match(X, m_NSWSub(m_Specific(Op0), m_Value(Z)))) {
1792     Intrinsic::ID InvID = getInverseMinMaxIntrinsic(MinMax->getIntrinsicID());
1793     Function *F = Intrinsic::getDeclaration(I.getModule(), InvID, Ty);
1794     return CallInst::Create(F, {Op0, Z});
1795   }
1796 
1797   return nullptr;
1798 }
1799 
1800 Instruction *InstCombinerImpl::visitSub(BinaryOperator &I) {
1801   if (Value *V = simplifySubInst(I.getOperand(0), I.getOperand(1),
1802                                  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
1803                                  SQ.getWithInstruction(&I)))
1804     return replaceInstUsesWith(I, V);
1805 
1806   if (Instruction *X = foldVectorBinop(I))
1807     return X;
1808 
1809   if (Instruction *Phi = foldBinopWithPhiOperands(I))
1810     return Phi;
1811 
1812   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1813 
1814   // If this is a 'B = x-(-A)', change to B = x+A.
1815   // We deal with this without involving Negator to preserve NSW flag.
1816   if (Value *V = dyn_castNegVal(Op1)) {
1817     BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V);
1818 
1819     if (const auto *BO = dyn_cast<BinaryOperator>(Op1)) {
1820       assert(BO->getOpcode() == Instruction::Sub &&
1821              "Expected a subtraction operator!");
1822       if (BO->hasNoSignedWrap() && I.hasNoSignedWrap())
1823         Res->setHasNoSignedWrap(true);
1824     } else {
1825       if (cast<Constant>(Op1)->isNotMinSignedValue() && I.hasNoSignedWrap())
1826         Res->setHasNoSignedWrap(true);
1827     }
1828 
1829     return Res;
1830   }
1831 
1832   // Try this before Negator to preserve NSW flag.
1833   if (Instruction *R = factorizeMathWithShlOps(I, Builder))
1834     return R;
1835 
1836   Constant *C;
1837   if (match(Op0, m_ImmConstant(C))) {
1838     Value *X;
1839     Constant *C2;
1840 
1841     // C-(X+C2) --> (C-C2)-X
1842     if (match(Op1, m_Add(m_Value(X), m_ImmConstant(C2))))
1843       return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
1844   }
1845 
1846   auto TryToNarrowDeduceFlags = [this, &I, &Op0, &Op1]() -> Instruction * {
1847     if (Instruction *Ext = narrowMathIfNoOverflow(I))
1848       return Ext;
1849 
1850     bool Changed = false;
1851     if (!I.hasNoSignedWrap() && willNotOverflowSignedSub(Op0, Op1, I)) {
1852       Changed = true;
1853       I.setHasNoSignedWrap(true);
1854     }
1855     if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedSub(Op0, Op1, I)) {
1856       Changed = true;
1857       I.setHasNoUnsignedWrap(true);
1858     }
1859 
1860     return Changed ? &I : nullptr;
1861   };
1862 
1863   // First, let's try to interpret `sub a, b` as `add a, (sub 0, b)`,
1864   // and let's try to sink `(sub 0, b)` into `b` itself. But only if this isn't
1865   // a pure negation used by a select that looks like abs/nabs.
1866   bool IsNegation = match(Op0, m_ZeroInt());
1867   if (!IsNegation || none_of(I.users(), [&I, Op1](const User *U) {
1868         const Instruction *UI = dyn_cast<Instruction>(U);
1869         if (!UI)
1870           return false;
1871         return match(UI,
1872                      m_Select(m_Value(), m_Specific(Op1), m_Specific(&I))) ||
1873                match(UI, m_Select(m_Value(), m_Specific(&I), m_Specific(Op1)));
1874       })) {
1875     if (Value *NegOp1 = Negator::Negate(IsNegation, Op1, *this))
1876       return BinaryOperator::CreateAdd(NegOp1, Op0);
1877   }
1878   if (IsNegation)
1879     return TryToNarrowDeduceFlags(); // Should have been handled in Negator!
1880 
1881   // (A*B)-(A*C) -> A*(B-C) etc
1882   if (Value *V = SimplifyUsingDistributiveLaws(I))
1883     return replaceInstUsesWith(I, V);
1884 
1885   if (I.getType()->isIntOrIntVectorTy(1))
1886     return BinaryOperator::CreateXor(Op0, Op1);
1887 
1888   // Replace (-1 - A) with (~A).
1889   if (match(Op0, m_AllOnes()))
1890     return BinaryOperator::CreateNot(Op1);
1891 
1892   // (X + -1) - Y --> ~Y + X
1893   Value *X, *Y;
1894   if (match(Op0, m_OneUse(m_Add(m_Value(X), m_AllOnes()))))
1895     return BinaryOperator::CreateAdd(Builder.CreateNot(Op1), X);
1896 
1897   // Reassociate sub/add sequences to create more add instructions and
1898   // reduce dependency chains:
1899   // ((X - Y) + Z) - Op1 --> (X + Z) - (Y + Op1)
1900   Value *Z;
1901   if (match(Op0, m_OneUse(m_c_Add(m_OneUse(m_Sub(m_Value(X), m_Value(Y))),
1902                                   m_Value(Z))))) {
1903     Value *XZ = Builder.CreateAdd(X, Z);
1904     Value *YW = Builder.CreateAdd(Y, Op1);
1905     return BinaryOperator::CreateSub(XZ, YW);
1906   }
1907 
1908   // ((X - Y) - Op1)  -->  X - (Y + Op1)
1909   if (match(Op0, m_OneUse(m_Sub(m_Value(X), m_Value(Y))))) {
1910     Value *Add = Builder.CreateAdd(Y, Op1);
1911     return BinaryOperator::CreateSub(X, Add);
1912   }
1913 
1914   // (~X) - (~Y) --> Y - X
1915   // This is placed after the other reassociations and explicitly excludes a
1916   // sub-of-sub pattern to avoid infinite looping.
1917   if (isFreeToInvert(Op0, Op0->hasOneUse()) &&
1918       isFreeToInvert(Op1, Op1->hasOneUse()) &&
1919       !match(Op0, m_Sub(m_ImmConstant(), m_Value()))) {
1920     Value *NotOp0 = Builder.CreateNot(Op0);
1921     Value *NotOp1 = Builder.CreateNot(Op1);
1922     return BinaryOperator::CreateSub(NotOp1, NotOp0);
1923   }
1924 
1925   auto m_AddRdx = [](Value *&Vec) {
1926     return m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_add>(m_Value(Vec)));
1927   };
1928   Value *V0, *V1;
1929   if (match(Op0, m_AddRdx(V0)) && match(Op1, m_AddRdx(V1)) &&
1930       V0->getType() == V1->getType()) {
1931     // Difference of sums is sum of differences:
1932     // add_rdx(V0) - add_rdx(V1) --> add_rdx(V0 - V1)
1933     Value *Sub = Builder.CreateSub(V0, V1);
1934     Value *Rdx = Builder.CreateIntrinsic(Intrinsic::vector_reduce_add,
1935                                          {Sub->getType()}, {Sub});
1936     return replaceInstUsesWith(I, Rdx);
1937   }
1938 
1939   if (Constant *C = dyn_cast<Constant>(Op0)) {
1940     Value *X;
1941     if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
1942       // C - (zext bool) --> bool ? C - 1 : C
1943       return SelectInst::Create(X, InstCombiner::SubOne(C), C);
1944     if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
1945       // C - (sext bool) --> bool ? C + 1 : C
1946       return SelectInst::Create(X, InstCombiner::AddOne(C), C);
1947 
1948     // C - ~X == X + (1+C)
1949     if (match(Op1, m_Not(m_Value(X))))
1950       return BinaryOperator::CreateAdd(X, InstCombiner::AddOne(C));
1951 
1952     // Try to fold constant sub into select arguments.
1953     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1954       if (Instruction *R = FoldOpIntoSelect(I, SI))
1955         return R;
1956 
1957     // Try to fold constant sub into PHI values.
1958     if (PHINode *PN = dyn_cast<PHINode>(Op1))
1959       if (Instruction *R = foldOpIntoPhi(I, PN))
1960         return R;
1961 
1962     Constant *C2;
1963 
1964     // C-(C2-X) --> X+(C-C2)
1965     if (match(Op1, m_Sub(m_ImmConstant(C2), m_Value(X))))
1966       return BinaryOperator::CreateAdd(X, ConstantExpr::getSub(C, C2));
1967   }
1968 
1969   const APInt *Op0C;
1970   if (match(Op0, m_APInt(Op0C)) && Op0C->isMask()) {
1971     // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known
1972     // zero.
1973     KnownBits RHSKnown = computeKnownBits(Op1, 0, &I);
1974     if ((*Op0C | RHSKnown.Zero).isAllOnes())
1975       return BinaryOperator::CreateXor(Op1, Op0);
1976   }
1977 
1978   {
1979     Value *Y;
1980     // X-(X+Y) == -Y    X-(Y+X) == -Y
1981     if (match(Op1, m_c_Add(m_Specific(Op0), m_Value(Y))))
1982       return BinaryOperator::CreateNeg(Y);
1983 
1984     // (X-Y)-X == -Y
1985     if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))
1986       return BinaryOperator::CreateNeg(Y);
1987   }
1988 
1989   // (sub (or A, B) (and A, B)) --> (xor A, B)
1990   {
1991     Value *A, *B;
1992     if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
1993         match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
1994       return BinaryOperator::CreateXor(A, B);
1995   }
1996 
1997   // (sub (add A, B) (or A, B)) --> (and A, B)
1998   {
1999     Value *A, *B;
2000     if (match(Op0, m_Add(m_Value(A), m_Value(B))) &&
2001         match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
2002       return BinaryOperator::CreateAnd(A, B);
2003   }
2004 
2005   // (sub (add A, B) (and A, B)) --> (or A, B)
2006   {
2007     Value *A, *B;
2008     if (match(Op0, m_Add(m_Value(A), m_Value(B))) &&
2009         match(Op1, m_c_And(m_Specific(A), m_Specific(B))))
2010       return BinaryOperator::CreateOr(A, B);
2011   }
2012 
2013   // (sub (and A, B) (or A, B)) --> neg (xor A, B)
2014   {
2015     Value *A, *B;
2016     if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2017         match(Op1, m_c_Or(m_Specific(A), m_Specific(B))) &&
2018         (Op0->hasOneUse() || Op1->hasOneUse()))
2019       return BinaryOperator::CreateNeg(Builder.CreateXor(A, B));
2020   }
2021 
2022   // (sub (or A, B), (xor A, B)) --> (and A, B)
2023   {
2024     Value *A, *B;
2025     if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
2026         match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
2027       return BinaryOperator::CreateAnd(A, B);
2028   }
2029 
2030   // (sub (xor A, B) (or A, B)) --> neg (and A, B)
2031   {
2032     Value *A, *B;
2033     if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
2034         match(Op1, m_c_Or(m_Specific(A), m_Specific(B))) &&
2035         (Op0->hasOneUse() || Op1->hasOneUse()))
2036       return BinaryOperator::CreateNeg(Builder.CreateAnd(A, B));
2037   }
2038 
2039   {
2040     Value *Y;
2041     // ((X | Y) - X) --> (~X & Y)
2042     if (match(Op0, m_OneUse(m_c_Or(m_Value(Y), m_Specific(Op1)))))
2043       return BinaryOperator::CreateAnd(
2044           Y, Builder.CreateNot(Op1, Op1->getName() + ".not"));
2045   }
2046 
2047   {
2048     // (sub (and Op1, (neg X)), Op1) --> neg (and Op1, (add X, -1))
2049     Value *X;
2050     if (match(Op0, m_OneUse(m_c_And(m_Specific(Op1),
2051                                     m_OneUse(m_Neg(m_Value(X))))))) {
2052       return BinaryOperator::CreateNeg(Builder.CreateAnd(
2053           Op1, Builder.CreateAdd(X, Constant::getAllOnesValue(I.getType()))));
2054     }
2055   }
2056 
2057   {
2058     // (sub (and Op1, C), Op1) --> neg (and Op1, ~C)
2059     Constant *C;
2060     if (match(Op0, m_OneUse(m_And(m_Specific(Op1), m_Constant(C))))) {
2061       return BinaryOperator::CreateNeg(
2062           Builder.CreateAnd(Op1, Builder.CreateNot(C)));
2063     }
2064   }
2065 
2066   if (Instruction *R = foldSubOfMinMax(I, Builder))
2067     return R;
2068 
2069   {
2070     // If we have a subtraction between some value and a select between
2071     // said value and something else, sink subtraction into select hands, i.e.:
2072     //   sub (select %Cond, %TrueVal, %FalseVal), %Op1
2073     //     ->
2074     //   select %Cond, (sub %TrueVal, %Op1), (sub %FalseVal, %Op1)
2075     //  or
2076     //   sub %Op0, (select %Cond, %TrueVal, %FalseVal)
2077     //     ->
2078     //   select %Cond, (sub %Op0, %TrueVal), (sub %Op0, %FalseVal)
2079     // This will result in select between new subtraction and 0.
2080     auto SinkSubIntoSelect =
2081         [Ty = I.getType()](Value *Select, Value *OtherHandOfSub,
2082                            auto SubBuilder) -> Instruction * {
2083       Value *Cond, *TrueVal, *FalseVal;
2084       if (!match(Select, m_OneUse(m_Select(m_Value(Cond), m_Value(TrueVal),
2085                                            m_Value(FalseVal)))))
2086         return nullptr;
2087       if (OtherHandOfSub != TrueVal && OtherHandOfSub != FalseVal)
2088         return nullptr;
2089       // While it is really tempting to just create two subtractions and let
2090       // InstCombine fold one of those to 0, it isn't possible to do so
2091       // because of worklist visitation order. So ugly it is.
2092       bool OtherHandOfSubIsTrueVal = OtherHandOfSub == TrueVal;
2093       Value *NewSub = SubBuilder(OtherHandOfSubIsTrueVal ? FalseVal : TrueVal);
2094       Constant *Zero = Constant::getNullValue(Ty);
2095       SelectInst *NewSel =
2096           SelectInst::Create(Cond, OtherHandOfSubIsTrueVal ? Zero : NewSub,
2097                              OtherHandOfSubIsTrueVal ? NewSub : Zero);
2098       // Preserve prof metadata if any.
2099       NewSel->copyMetadata(cast<Instruction>(*Select));
2100       return NewSel;
2101     };
2102     if (Instruction *NewSel = SinkSubIntoSelect(
2103             /*Select=*/Op0, /*OtherHandOfSub=*/Op1,
2104             [Builder = &Builder, Op1](Value *OtherHandOfSelect) {
2105               return Builder->CreateSub(OtherHandOfSelect,
2106                                         /*OtherHandOfSub=*/Op1);
2107             }))
2108       return NewSel;
2109     if (Instruction *NewSel = SinkSubIntoSelect(
2110             /*Select=*/Op1, /*OtherHandOfSub=*/Op0,
2111             [Builder = &Builder, Op0](Value *OtherHandOfSelect) {
2112               return Builder->CreateSub(/*OtherHandOfSub=*/Op0,
2113                                         OtherHandOfSelect);
2114             }))
2115       return NewSel;
2116   }
2117 
2118   // (X - (X & Y))   -->   (X & ~Y)
2119   if (match(Op1, m_c_And(m_Specific(Op0), m_Value(Y))) &&
2120       (Op1->hasOneUse() || isa<Constant>(Y)))
2121     return BinaryOperator::CreateAnd(
2122         Op0, Builder.CreateNot(Y, Y->getName() + ".not"));
2123 
2124   // ~X - Min/Max(~X, Y) -> ~Min/Max(X, ~Y) - X
2125   // ~X - Min/Max(Y, ~X) -> ~Min/Max(X, ~Y) - X
2126   // Min/Max(~X, Y) - ~X -> X - ~Min/Max(X, ~Y)
2127   // Min/Max(Y, ~X) - ~X -> X - ~Min/Max(X, ~Y)
2128   // As long as Y is freely invertible, this will be neutral or a win.
2129   // Note: We don't generate the inverse max/min, just create the 'not' of
2130   // it and let other folds do the rest.
2131   if (match(Op0, m_Not(m_Value(X))) &&
2132       match(Op1, m_c_MaxOrMin(m_Specific(Op0), m_Value(Y))) &&
2133       !Op0->hasNUsesOrMore(3) && isFreeToInvert(Y, Y->hasOneUse())) {
2134     Value *Not = Builder.CreateNot(Op1);
2135     return BinaryOperator::CreateSub(Not, X);
2136   }
2137   if (match(Op1, m_Not(m_Value(X))) &&
2138       match(Op0, m_c_MaxOrMin(m_Specific(Op1), m_Value(Y))) &&
2139       !Op1->hasNUsesOrMore(3) && isFreeToInvert(Y, Y->hasOneUse())) {
2140     Value *Not = Builder.CreateNot(Op0);
2141     return BinaryOperator::CreateSub(X, Not);
2142   }
2143 
2144   // Optimize pointer differences into the same array into a size.  Consider:
2145   //  &A[10] - &A[0]: we should compile this to "10".
2146   Value *LHSOp, *RHSOp;
2147   if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
2148       match(Op1, m_PtrToInt(m_Value(RHSOp))))
2149     if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType(),
2150                                                I.hasNoUnsignedWrap()))
2151       return replaceInstUsesWith(I, Res);
2152 
2153   // trunc(p)-trunc(q) -> trunc(p-q)
2154   if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) &&
2155       match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp)))))
2156     if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType(),
2157                                                /* IsNUW */ false))
2158       return replaceInstUsesWith(I, Res);
2159 
2160   // Canonicalize a shifty way to code absolute value to the common pattern.
2161   // There are 2 potential commuted variants.
2162   // We're relying on the fact that we only do this transform when the shift has
2163   // exactly 2 uses and the xor has exactly 1 use (otherwise, we might increase
2164   // instructions).
2165   Value *A;
2166   const APInt *ShAmt;
2167   Type *Ty = I.getType();
2168   if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
2169       Op1->hasNUses(2) && *ShAmt == Ty->getScalarSizeInBits() - 1 &&
2170       match(Op0, m_OneUse(m_c_Xor(m_Specific(A), m_Specific(Op1))))) {
2171     // B = ashr i32 A, 31 ; smear the sign bit
2172     // sub (xor A, B), B  ; flip bits if negative and subtract -1 (add 1)
2173     // --> (A < 0) ? -A : A
2174     Value *IsNeg = Builder.CreateIsNeg(A);
2175     // Copy the nuw/nsw flags from the sub to the negate.
2176     Value *NegA = Builder.CreateNeg(A, "", I.hasNoUnsignedWrap(),
2177                                     I.hasNoSignedWrap());
2178     return SelectInst::Create(IsNeg, NegA, A);
2179   }
2180 
2181   // If we are subtracting a low-bit masked subset of some value from an add
2182   // of that same value with no low bits changed, that is clearing some low bits
2183   // of the sum:
2184   // sub (X + AddC), (X & AndC) --> and (X + AddC), ~AndC
2185   const APInt *AddC, *AndC;
2186   if (match(Op0, m_Add(m_Value(X), m_APInt(AddC))) &&
2187       match(Op1, m_And(m_Specific(X), m_APInt(AndC)))) {
2188     unsigned BitWidth = Ty->getScalarSizeInBits();
2189     unsigned Cttz = AddC->countTrailingZeros();
2190     APInt HighMask(APInt::getHighBitsSet(BitWidth, BitWidth - Cttz));
2191     if ((HighMask & *AndC).isZero())
2192       return BinaryOperator::CreateAnd(Op0, ConstantInt::get(Ty, ~(*AndC)));
2193   }
2194 
2195   if (Instruction *V =
2196           canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
2197     return V;
2198 
2199   // X - usub.sat(X, Y) => umin(X, Y)
2200   if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Specific(Op0),
2201                                                            m_Value(Y)))))
2202     return replaceInstUsesWith(
2203         I, Builder.CreateIntrinsic(Intrinsic::umin, {I.getType()}, {Op0, Y}));
2204 
2205   // umax(X, Op1) - Op1 --> usub.sat(X, Op1)
2206   // TODO: The one-use restriction is not strictly necessary, but it may
2207   //       require improving other pattern matching and/or codegen.
2208   if (match(Op0, m_OneUse(m_c_UMax(m_Value(X), m_Specific(Op1)))))
2209     return replaceInstUsesWith(
2210         I, Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {X, Op1}));
2211 
2212   // Op0 - umin(X, Op0) --> usub.sat(Op0, X)
2213   if (match(Op1, m_OneUse(m_c_UMin(m_Value(X), m_Specific(Op0)))))
2214     return replaceInstUsesWith(
2215         I, Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {Op0, X}));
2216 
2217   // Op0 - umax(X, Op0) --> 0 - usub.sat(X, Op0)
2218   if (match(Op1, m_OneUse(m_c_UMax(m_Value(X), m_Specific(Op0))))) {
2219     Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {X, Op0});
2220     return BinaryOperator::CreateNeg(USub);
2221   }
2222 
2223   // umin(X, Op1) - Op1 --> 0 - usub.sat(Op1, X)
2224   if (match(Op0, m_OneUse(m_c_UMin(m_Value(X), m_Specific(Op1))))) {
2225     Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {Op1, X});
2226     return BinaryOperator::CreateNeg(USub);
2227   }
2228 
2229   // C - ctpop(X) => ctpop(~X) if C is bitwidth
2230   if (match(Op0, m_SpecificInt(Ty->getScalarSizeInBits())) &&
2231       match(Op1, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(X)))))
2232     return replaceInstUsesWith(
2233         I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
2234                                    {Builder.CreateNot(X)}));
2235 
2236   return TryToNarrowDeduceFlags();
2237 }
2238 
2239 /// This eliminates floating-point negation in either 'fneg(X)' or
2240 /// 'fsub(-0.0, X)' form by combining into a constant operand.
2241 static Instruction *foldFNegIntoConstant(Instruction &I) {
2242   // This is limited with one-use because fneg is assumed better for
2243   // reassociation and cheaper in codegen than fmul/fdiv.
2244   // TODO: Should the m_OneUse restriction be removed?
2245   Instruction *FNegOp;
2246   if (!match(&I, m_FNeg(m_OneUse(m_Instruction(FNegOp)))))
2247     return nullptr;
2248 
2249   Value *X;
2250   Constant *C;
2251 
2252   // Fold negation into constant operand.
2253   // -(X * C) --> X * (-C)
2254   if (match(FNegOp, m_FMul(m_Value(X), m_Constant(C))))
2255     return BinaryOperator::CreateFMulFMF(X, ConstantExpr::getFNeg(C), &I);
2256   // -(X / C) --> X / (-C)
2257   if (match(FNegOp, m_FDiv(m_Value(X), m_Constant(C))))
2258     return BinaryOperator::CreateFDivFMF(X, ConstantExpr::getFNeg(C), &I);
2259   // -(C / X) --> (-C) / X
2260   if (match(FNegOp, m_FDiv(m_Constant(C), m_Value(X)))) {
2261     Instruction *FDiv =
2262         BinaryOperator::CreateFDivFMF(ConstantExpr::getFNeg(C), X, &I);
2263 
2264     // Intersect 'nsz' and 'ninf' because those special value exceptions may not
2265     // apply to the fdiv. Everything else propagates from the fneg.
2266     // TODO: We could propagate nsz/ninf from fdiv alone?
2267     FastMathFlags FMF = I.getFastMathFlags();
2268     FastMathFlags OpFMF = FNegOp->getFastMathFlags();
2269     FDiv->setHasNoSignedZeros(FMF.noSignedZeros() && OpFMF.noSignedZeros());
2270     FDiv->setHasNoInfs(FMF.noInfs() && OpFMF.noInfs());
2271     return FDiv;
2272   }
2273   // With NSZ [ counter-example with -0.0: -(-0.0 + 0.0) != 0.0 + -0.0 ]:
2274   // -(X + C) --> -X + -C --> -C - X
2275   if (I.hasNoSignedZeros() && match(FNegOp, m_FAdd(m_Value(X), m_Constant(C))))
2276     return BinaryOperator::CreateFSubFMF(ConstantExpr::getFNeg(C), X, &I);
2277 
2278   return nullptr;
2279 }
2280 
2281 static Instruction *hoistFNegAboveFMulFDiv(Instruction &I,
2282                                            InstCombiner::BuilderTy &Builder) {
2283   Value *FNeg;
2284   if (!match(&I, m_FNeg(m_Value(FNeg))))
2285     return nullptr;
2286 
2287   Value *X, *Y;
2288   if (match(FNeg, m_OneUse(m_FMul(m_Value(X), m_Value(Y)))))
2289     return BinaryOperator::CreateFMulFMF(Builder.CreateFNegFMF(X, &I), Y, &I);
2290 
2291   if (match(FNeg, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))))
2292     return BinaryOperator::CreateFDivFMF(Builder.CreateFNegFMF(X, &I), Y, &I);
2293 
2294   return nullptr;
2295 }
2296 
2297 Instruction *InstCombinerImpl::visitFNeg(UnaryOperator &I) {
2298   Value *Op = I.getOperand(0);
2299 
2300   if (Value *V = simplifyFNegInst(Op, I.getFastMathFlags(),
2301                                   getSimplifyQuery().getWithInstruction(&I)))
2302     return replaceInstUsesWith(I, V);
2303 
2304   if (Instruction *X = foldFNegIntoConstant(I))
2305     return X;
2306 
2307   Value *X, *Y;
2308 
2309   // If we can ignore the sign of zeros: -(X - Y) --> (Y - X)
2310   if (I.hasNoSignedZeros() &&
2311       match(Op, m_OneUse(m_FSub(m_Value(X), m_Value(Y)))))
2312     return BinaryOperator::CreateFSubFMF(Y, X, &I);
2313 
2314   if (Instruction *R = hoistFNegAboveFMulFDiv(I, Builder))
2315     return R;
2316 
2317   // Try to eliminate fneg if at least 1 arm of the select is negated.
2318   Value *Cond;
2319   if (match(Op, m_OneUse(m_Select(m_Value(Cond), m_Value(X), m_Value(Y))))) {
2320     // Unlike most transforms, this one is not safe to propagate nsz unless
2321     // it is present on the original select. (We are conservatively intersecting
2322     // the nsz flags from the select and root fneg instruction.)
2323     auto propagateSelectFMF = [&](SelectInst *S, bool CommonOperand) {
2324       S->copyFastMathFlags(&I);
2325       if (auto *OldSel = dyn_cast<SelectInst>(Op))
2326         if (!OldSel->hasNoSignedZeros() && !CommonOperand &&
2327             !isGuaranteedNotToBeUndefOrPoison(OldSel->getCondition()))
2328           S->setHasNoSignedZeros(false);
2329     };
2330     // -(Cond ? -P : Y) --> Cond ? P : -Y
2331     Value *P;
2332     if (match(X, m_FNeg(m_Value(P)))) {
2333       Value *NegY = Builder.CreateFNegFMF(Y, &I, Y->getName() + ".neg");
2334       SelectInst *NewSel = SelectInst::Create(Cond, P, NegY);
2335       propagateSelectFMF(NewSel, P == Y);
2336       return NewSel;
2337     }
2338     // -(Cond ? X : -P) --> Cond ? -X : P
2339     if (match(Y, m_FNeg(m_Value(P)))) {
2340       Value *NegX = Builder.CreateFNegFMF(X, &I, X->getName() + ".neg");
2341       SelectInst *NewSel = SelectInst::Create(Cond, NegX, P);
2342       propagateSelectFMF(NewSel, P == X);
2343       return NewSel;
2344     }
2345   }
2346 
2347   return nullptr;
2348 }
2349 
2350 Instruction *InstCombinerImpl::visitFSub(BinaryOperator &I) {
2351   if (Value *V = simplifyFSubInst(I.getOperand(0), I.getOperand(1),
2352                                   I.getFastMathFlags(),
2353                                   getSimplifyQuery().getWithInstruction(&I)))
2354     return replaceInstUsesWith(I, V);
2355 
2356   if (Instruction *X = foldVectorBinop(I))
2357     return X;
2358 
2359   if (Instruction *Phi = foldBinopWithPhiOperands(I))
2360     return Phi;
2361 
2362   // Subtraction from -0.0 is the canonical form of fneg.
2363   // fsub -0.0, X ==> fneg X
2364   // fsub nsz 0.0, X ==> fneg nsz X
2365   //
2366   // FIXME This matcher does not respect FTZ or DAZ yet:
2367   // fsub -0.0, Denorm ==> +-0
2368   // fneg Denorm ==> -Denorm
2369   Value *Op;
2370   if (match(&I, m_FNeg(m_Value(Op))))
2371     return UnaryOperator::CreateFNegFMF(Op, &I);
2372 
2373   if (Instruction *X = foldFNegIntoConstant(I))
2374     return X;
2375 
2376   if (Instruction *R = hoistFNegAboveFMulFDiv(I, Builder))
2377     return R;
2378 
2379   Value *X, *Y;
2380   Constant *C;
2381 
2382   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2383   // If Op0 is not -0.0 or we can ignore -0.0: Z - (X - Y) --> Z + (Y - X)
2384   // Canonicalize to fadd to make analysis easier.
2385   // This can also help codegen because fadd is commutative.
2386   // Note that if this fsub was really an fneg, the fadd with -0.0 will get
2387   // killed later. We still limit that particular transform with 'hasOneUse'
2388   // because an fneg is assumed better/cheaper than a generic fsub.
2389   if (I.hasNoSignedZeros() || CannotBeNegativeZero(Op0, SQ.TLI)) {
2390     if (match(Op1, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) {
2391       Value *NewSub = Builder.CreateFSubFMF(Y, X, &I);
2392       return BinaryOperator::CreateFAddFMF(Op0, NewSub, &I);
2393     }
2394   }
2395 
2396   // (-X) - Op1 --> -(X + Op1)
2397   if (I.hasNoSignedZeros() && !isa<ConstantExpr>(Op0) &&
2398       match(Op0, m_OneUse(m_FNeg(m_Value(X))))) {
2399     Value *FAdd = Builder.CreateFAddFMF(X, Op1, &I);
2400     return UnaryOperator::CreateFNegFMF(FAdd, &I);
2401   }
2402 
2403   if (isa<Constant>(Op0))
2404     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
2405       if (Instruction *NV = FoldOpIntoSelect(I, SI))
2406         return NV;
2407 
2408   // X - C --> X + (-C)
2409   // But don't transform constant expressions because there's an inverse fold
2410   // for X + (-Y) --> X - Y.
2411   if (match(Op1, m_ImmConstant(C)))
2412     return BinaryOperator::CreateFAddFMF(Op0, ConstantExpr::getFNeg(C), &I);
2413 
2414   // X - (-Y) --> X + Y
2415   if (match(Op1, m_FNeg(m_Value(Y))))
2416     return BinaryOperator::CreateFAddFMF(Op0, Y, &I);
2417 
2418   // Similar to above, but look through a cast of the negated value:
2419   // X - (fptrunc(-Y)) --> X + fptrunc(Y)
2420   Type *Ty = I.getType();
2421   if (match(Op1, m_OneUse(m_FPTrunc(m_FNeg(m_Value(Y))))))
2422     return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPTrunc(Y, Ty), &I);
2423 
2424   // X - (fpext(-Y)) --> X + fpext(Y)
2425   if (match(Op1, m_OneUse(m_FPExt(m_FNeg(m_Value(Y))))))
2426     return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPExt(Y, Ty), &I);
2427 
2428   // Similar to above, but look through fmul/fdiv of the negated value:
2429   // Op0 - (-X * Y) --> Op0 + (X * Y)
2430   // Op0 - (Y * -X) --> Op0 + (X * Y)
2431   if (match(Op1, m_OneUse(m_c_FMul(m_FNeg(m_Value(X)), m_Value(Y))))) {
2432     Value *FMul = Builder.CreateFMulFMF(X, Y, &I);
2433     return BinaryOperator::CreateFAddFMF(Op0, FMul, &I);
2434   }
2435   // Op0 - (-X / Y) --> Op0 + (X / Y)
2436   // Op0 - (X / -Y) --> Op0 + (X / Y)
2437   if (match(Op1, m_OneUse(m_FDiv(m_FNeg(m_Value(X)), m_Value(Y)))) ||
2438       match(Op1, m_OneUse(m_FDiv(m_Value(X), m_FNeg(m_Value(Y)))))) {
2439     Value *FDiv = Builder.CreateFDivFMF(X, Y, &I);
2440     return BinaryOperator::CreateFAddFMF(Op0, FDiv, &I);
2441   }
2442 
2443   // Handle special cases for FSub with selects feeding the operation
2444   if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
2445     return replaceInstUsesWith(I, V);
2446 
2447   if (I.hasAllowReassoc() && I.hasNoSignedZeros()) {
2448     // (Y - X) - Y --> -X
2449     if (match(Op0, m_FSub(m_Specific(Op1), m_Value(X))))
2450       return UnaryOperator::CreateFNegFMF(X, &I);
2451 
2452     // Y - (X + Y) --> -X
2453     // Y - (Y + X) --> -X
2454     if (match(Op1, m_c_FAdd(m_Specific(Op0), m_Value(X))))
2455       return UnaryOperator::CreateFNegFMF(X, &I);
2456 
2457     // (X * C) - X --> X * (C - 1.0)
2458     if (match(Op0, m_FMul(m_Specific(Op1), m_Constant(C)))) {
2459       if (Constant *CSubOne = ConstantFoldBinaryOpOperands(
2460               Instruction::FSub, C, ConstantFP::get(Ty, 1.0), DL))
2461         return BinaryOperator::CreateFMulFMF(Op1, CSubOne, &I);
2462     }
2463     // X - (X * C) --> X * (1.0 - C)
2464     if (match(Op1, m_FMul(m_Specific(Op0), m_Constant(C)))) {
2465       if (Constant *OneSubC = ConstantFoldBinaryOpOperands(
2466               Instruction::FSub, ConstantFP::get(Ty, 1.0), C, DL))
2467         return BinaryOperator::CreateFMulFMF(Op0, OneSubC, &I);
2468     }
2469 
2470     // Reassociate fsub/fadd sequences to create more fadd instructions and
2471     // reduce dependency chains:
2472     // ((X - Y) + Z) - Op1 --> (X + Z) - (Y + Op1)
2473     Value *Z;
2474     if (match(Op0, m_OneUse(m_c_FAdd(m_OneUse(m_FSub(m_Value(X), m_Value(Y))),
2475                                      m_Value(Z))))) {
2476       Value *XZ = Builder.CreateFAddFMF(X, Z, &I);
2477       Value *YW = Builder.CreateFAddFMF(Y, Op1, &I);
2478       return BinaryOperator::CreateFSubFMF(XZ, YW, &I);
2479     }
2480 
2481     auto m_FaddRdx = [](Value *&Sum, Value *&Vec) {
2482       return m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(m_Value(Sum),
2483                                                                  m_Value(Vec)));
2484     };
2485     Value *A0, *A1, *V0, *V1;
2486     if (match(Op0, m_FaddRdx(A0, V0)) && match(Op1, m_FaddRdx(A1, V1)) &&
2487         V0->getType() == V1->getType()) {
2488       // Difference of sums is sum of differences:
2489       // add_rdx(A0, V0) - add_rdx(A1, V1) --> add_rdx(A0, V0 - V1) - A1
2490       Value *Sub = Builder.CreateFSubFMF(V0, V1, &I);
2491       Value *Rdx = Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,
2492                                            {Sub->getType()}, {A0, Sub}, &I);
2493       return BinaryOperator::CreateFSubFMF(Rdx, A1, &I);
2494     }
2495 
2496     if (Instruction *F = factorizeFAddFSub(I, Builder))
2497       return F;
2498 
2499     // TODO: This performs reassociative folds for FP ops. Some fraction of the
2500     // functionality has been subsumed by simple pattern matching here and in
2501     // InstSimplify. We should let a dedicated reassociation pass handle more
2502     // complex pattern matching and remove this from InstCombine.
2503     if (Value *V = FAddCombine(Builder).simplify(&I))
2504       return replaceInstUsesWith(I, V);
2505 
2506     // (X - Y) - Op1 --> X - (Y + Op1)
2507     if (match(Op0, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) {
2508       Value *FAdd = Builder.CreateFAddFMF(Y, Op1, &I);
2509       return BinaryOperator::CreateFSubFMF(X, FAdd, &I);
2510     }
2511   }
2512 
2513   return nullptr;
2514 }
2515