LLVM  16.0.0git
InstCombineAddSub.cpp
Go to the documentation of this file.
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"
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"
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 
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 
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 
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) {
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),
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 
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 <= std::size(TmpResult) + 1) && "out-of-bound access");
580 
581  Value *Result;
582  if (!SimpVect.empty())
583  Result = createNaryFAdd(SimpVect, InstrQuota);
584  else {
585  // The addition is folded to 0.0.
586  Result = ConstantFP::get(Instr->getType(), 0.0);
587  }
588 
589  return Result;
590 }
591 
592 Value *FAddCombine::createNaryFAdd
593  (const AddendVect &Opnds, unsigned InstrQuota) {
594  assert(!Opnds.empty() && "Expect at least one addend");
595 
596  // Step 1: Check if the # of instructions needed exceeds the quota.
597 
598  unsigned InstrNeeded = calcInstrNumber(Opnds);
599  if (InstrNeeded > InstrQuota)
600  return nullptr;
601 
602  initCreateInstNum();
603 
604  // step 2: Emit the N-ary addition.
605  // Note that at most three instructions are involved in Fadd-InstCombine: the
606  // addition in question, and at most two neighboring instructions.
607  // The resulting optimized addition should have at least one less instruction
608  // than the original addition expression tree. This implies that the resulting
609  // N-ary addition has at most two instructions, and we don't need to worry
610  // about tree-height when constructing the N-ary addition.
611 
612  Value *LastVal = nullptr;
613  bool LastValNeedNeg = false;
614 
615  // Iterate the addends, creating fadd/fsub using adjacent two addends.
616  for (const FAddend *Opnd : Opnds) {
617  bool NeedNeg;
618  Value *V = createAddendVal(*Opnd, NeedNeg);
619  if (!LastVal) {
620  LastVal = V;
621  LastValNeedNeg = NeedNeg;
622  continue;
623  }
624 
625  if (LastValNeedNeg == NeedNeg) {
626  LastVal = createFAdd(LastVal, V);
627  continue;
628  }
629 
630  if (LastValNeedNeg)
631  LastVal = createFSub(V, LastVal);
632  else
633  LastVal = createFSub(LastVal, V);
634 
635  LastValNeedNeg = false;
636  }
637 
638  if (LastValNeedNeg) {
639  LastVal = createFNeg(LastVal);
640  }
641 
642 #ifndef NDEBUG
643  assert(CreateInstrNum == InstrNeeded &&
644  "Inconsistent in instruction numbers");
645 #endif
646 
647  return LastVal;
648 }
649 
650 Value *FAddCombine::createFSub(Value *Opnd0, Value *Opnd1) {
651  Value *V = Builder.CreateFSub(Opnd0, Opnd1);
652  if (Instruction *I = dyn_cast<Instruction>(V))
653  createInstPostProc(I);
654  return V;
655 }
656 
657 Value *FAddCombine::createFNeg(Value *V) {
658  Value *NewV = Builder.CreateFNeg(V);
659  if (Instruction *I = dyn_cast<Instruction>(NewV))
660  createInstPostProc(I, true); // fneg's don't receive instruction numbers.
661  return NewV;
662 }
663 
664 Value *FAddCombine::createFAdd(Value *Opnd0, Value *Opnd1) {
665  Value *V = Builder.CreateFAdd(Opnd0, Opnd1);
666  if (Instruction *I = dyn_cast<Instruction>(V))
667  createInstPostProc(I);
668  return V;
669 }
670 
671 Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) {
672  Value *V = Builder.CreateFMul(Opnd0, Opnd1);
673  if (Instruction *I = dyn_cast<Instruction>(V))
674  createInstPostProc(I);
675  return V;
676 }
677 
678 void FAddCombine::createInstPostProc(Instruction *NewInstr, bool NoNumber) {
679  NewInstr->setDebugLoc(Instr->getDebugLoc());
680 
681  // Keep track of the number of instruction created.
682  if (!NoNumber)
683  incCreateInstNum();
684 
685  // Propagate fast-math flags
686  NewInstr->setFastMathFlags(Instr->getFastMathFlags());
687 }
688 
689 // Return the number of instruction needed to emit the N-ary addition.
690 // NOTE: Keep this function in sync with createAddendVal().
691 unsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) {
692  unsigned OpndNum = Opnds.size();
693  unsigned InstrNeeded = OpndNum - 1;
694 
695  // Adjust the number of instructions needed to emit the N-ary add.
696  for (const FAddend *Opnd : Opnds) {
697  if (Opnd->isConstant())
698  continue;
699 
700  // The constant check above is really for a few special constant
701  // coefficients.
702  if (isa<UndefValue>(Opnd->getSymVal()))
703  continue;
704 
705  const FAddendCoef &CE = Opnd->getCoef();
706  // Let the addend be "c * x". If "c == +/-1", the value of the addend
707  // is immediately available; otherwise, it needs exactly one instruction
708  // to evaluate the value.
709  if (!CE.isMinusOne() && !CE.isOne())
710  InstrNeeded++;
711  }
712  return InstrNeeded;
713 }
714 
715 // Input Addend Value NeedNeg(output)
716 // ================================================================
717 // Constant C C false
718 // <+/-1, V> V coefficient is -1
719 // <2/-2, V> "fadd V, V" coefficient is -2
720 // <C, V> "fmul V, C" false
721 //
722 // NOTE: Keep this function in sync with FAddCombine::calcInstrNumber.
723 Value *FAddCombine::createAddendVal(const FAddend &Opnd, bool &NeedNeg) {
724  const FAddendCoef &Coeff = Opnd.getCoef();
725 
726  if (Opnd.isConstant()) {
727  NeedNeg = false;
728  return Coeff.getValue(Instr->getType());
729  }
730 
731  Value *OpndVal = Opnd.getSymVal();
732 
733  if (Coeff.isMinusOne() || Coeff.isOne()) {
734  NeedNeg = Coeff.isMinusOne();
735  return OpndVal;
736  }
737 
738  if (Coeff.isTwo() || Coeff.isMinusTwo()) {
739  NeedNeg = Coeff.isMinusTwo();
740  return createFAdd(OpndVal, OpndVal);
741  }
742 
743  NeedNeg = false;
744  return createFMul(OpndVal, Coeff.getValue(Instr->getType()));
745 }
746 
747 // Checks if any operand is negative and we can convert add to sub.
748 // This function checks for following negative patterns
749 // ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C))
750 // ADD(XOR(AND(Z, C), C), 1) == NEG(OR(Z, ~C))
751 // XOR(AND(Z, C), (C + 1)) == NEG(OR(Z, ~C)) if C is even
754  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
755 
756  // This function creates 2 instructions to replace ADD, we need at least one
757  // of LHS or RHS to have one use to ensure benefit in transform.
758  if (!LHS->hasOneUse() && !RHS->hasOneUse())
759  return nullptr;
760 
761  Value *X = nullptr, *Y = nullptr, *Z = nullptr;
762  const APInt *C1 = nullptr, *C2 = nullptr;
763 
764  // if ONE is on other side, swap
765  if (match(RHS, m_Add(m_Value(X), m_One())))
766  std::swap(LHS, RHS);
767 
768  if (match(LHS, m_Add(m_Value(X), m_One()))) {
769  // if XOR on other side, swap
770  if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
771  std::swap(X, RHS);
772 
773  if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) {
774  // X = XOR(Y, C1), Y = OR(Z, C2), C2 = NOT(C1) ==> X == NOT(AND(Z, C1))
775  // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, AND(Z, C1))
776  if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C2 == ~(*C1))) {
777  Value *NewAnd = Builder.CreateAnd(Z, *C1);
778  return Builder.CreateSub(RHS, NewAnd, "sub");
779  } else if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && (*C1 == *C2)) {
780  // X = XOR(Y, C1), Y = AND(Z, C2), C2 == C1 ==> X == NOT(OR(Z, ~C1))
781  // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, OR(Z, ~C1))
782  Value *NewOr = Builder.CreateOr(Z, ~(*C1));
783  return Builder.CreateSub(RHS, NewOr, "sub");
784  }
785  }
786  }
787 
788  // Restore LHS and RHS
789  LHS = I.getOperand(0);
790  RHS = I.getOperand(1);
791 
792  // if XOR is on other side, swap
793  if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
794  std::swap(LHS, RHS);
795 
796  // C2 is ODD
797  // LHS = XOR(Y, C1), Y = AND(Z, C2), C1 == (C2 + 1) => LHS == NEG(OR(Z, ~C2))
798  // ADD(LHS, RHS) == SUB(RHS, OR(Z, ~C2))
799  if (match(LHS, m_Xor(m_Value(Y), m_APInt(C1))))
800  if (C1->countTrailingZeros() == 0)
801  if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && *C1 == (*C2 + 1)) {
802  Value *NewOr = Builder.CreateOr(Z, ~(*C2));
803  return Builder.CreateSub(RHS, NewOr, "sub");
804  }
805  return nullptr;
806 }
807 
808 /// Wrapping flags may allow combining constants separated by an extend.
811  Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1);
812  Type *Ty = Add.getType();
813  Constant *Op1C;
814  if (!match(Op1, m_Constant(Op1C)))
815  return nullptr;
816 
817  // Try this match first because it results in an add in the narrow type.
818  // (zext (X +nuw C2)) + C1 --> zext (X + (C2 + trunc(C1)))
819  Value *X;
820  const APInt *C1, *C2;
821  if (match(Op1, m_APInt(C1)) &&
822  match(Op0, m_OneUse(m_ZExt(m_NUWAdd(m_Value(X), m_APInt(C2))))) &&
823  C1->isNegative() && C1->sge(-C2->sext(C1->getBitWidth()))) {
824  Constant *NewC =
825  ConstantInt::get(X->getType(), *C2 + C1->trunc(C2->getBitWidth()));
826  return new ZExtInst(Builder.CreateNUWAdd(X, NewC), Ty);
827  }
828 
829  // More general combining of constants in the wide type.
830  // (sext (X +nsw NarrowC)) + C --> (sext X) + (sext(NarrowC) + C)
831  Constant *NarrowC;
832  if (match(Op0, m_OneUse(m_SExt(m_NSWAdd(m_Value(X), m_Constant(NarrowC)))))) {
833  Constant *WideC = ConstantExpr::getSExt(NarrowC, Ty);
834  Constant *NewC = ConstantExpr::getAdd(WideC, Op1C);
835  Value *WideX = Builder.CreateSExt(X, Ty);
836  return BinaryOperator::CreateAdd(WideX, NewC);
837  }
838  // (zext (X +nuw NarrowC)) + C --> (zext X) + (zext(NarrowC) + C)
839  if (match(Op0, m_OneUse(m_ZExt(m_NUWAdd(m_Value(X), m_Constant(NarrowC)))))) {
840  Constant *WideC = ConstantExpr::getZExt(NarrowC, Ty);
841  Constant *NewC = ConstantExpr::getAdd(WideC, Op1C);
842  Value *WideX = Builder.CreateZExt(X, Ty);
843  return BinaryOperator::CreateAdd(WideX, NewC);
844  }
845 
846  return nullptr;
847 }
848 
850  Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1);
851  Type *Ty = Add.getType();
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  // (iN X s>> (N - 1)) + 1 --> zext (X > -1)
887  const APInt *C;
888  unsigned BitWidth = Ty->getScalarSizeInBits();
889  if (match(Op0, m_OneUse(m_AShr(m_Value(X),
891  match(Op1, m_One()))
892  return new ZExtInst(Builder.CreateIsNotNeg(X, "isnotneg"), Ty);
893 
894  if (!match(Op1, m_APInt(C)))
895  return nullptr;
896 
897  // (X | Op01C) + Op1C --> X + (Op01C + Op1C) iff the `or` is actually an `add`
898  Constant *Op01C;
899  if (match(Op0, m_Or(m_Value(X), m_ImmConstant(Op01C))) &&
900  haveNoCommonBitsSet(X, Op01C, DL, &AC, &Add, &DT))
901  return BinaryOperator::CreateAdd(X, ConstantExpr::getAdd(Op01C, Op1C));
902 
903  // (X | C2) + C --> (X | C2) ^ C2 iff (C2 == -C)
904  const APInt *C2;
905  if (match(Op0, m_Or(m_Value(), m_APInt(C2))) && *C2 == -*C)
906  return BinaryOperator::CreateXor(Op0, ConstantInt::get(Add.getType(), *C2));
907 
908  if (C->isSignMask()) {
909  // If wrapping is not allowed, then the addition must set the sign bit:
910  // X + (signmask) --> X | signmask
911  if (Add.hasNoSignedWrap() || Add.hasNoUnsignedWrap())
912  return BinaryOperator::CreateOr(Op0, Op1);
913 
914  // If wrapping is allowed, then the addition flips the sign bit of LHS:
915  // X + (signmask) --> X ^ signmask
916  return BinaryOperator::CreateXor(Op0, Op1);
917  }
918 
919  // Is this add the last step in a convoluted sext?
920  // add(zext(xor i16 X, -32768), -32768) --> sext X
921  if (match(Op0, m_ZExt(m_Xor(m_Value(X), m_APInt(C2)))) &&
922  C2->isMinSignedValue() && C2->sext(Ty->getScalarSizeInBits()) == *C)
923  return CastInst::Create(Instruction::SExt, X, Ty);
924 
925  if (match(Op0, m_Xor(m_Value(X), m_APInt(C2)))) {
926  // (X ^ signmask) + C --> (X + (signmask ^ C))
927  if (C2->isSignMask())
928  return BinaryOperator::CreateAdd(X, ConstantInt::get(Ty, *C2 ^ *C));
929 
930  // If X has no high-bits set above an xor mask:
931  // add (xor X, LowMaskC), C --> sub (LowMaskC + C), X
932  if (C2->isMask()) {
933  KnownBits LHSKnown = computeKnownBits(X, 0, &Add);
934  if ((*C2 | LHSKnown.Zero).isAllOnes())
935  return BinaryOperator::CreateSub(ConstantInt::get(Ty, *C2 + *C), X);
936  }
937 
938  // Look for a math+logic pattern that corresponds to sext-in-register of a
939  // value with cleared high bits. Convert that into a pair of shifts:
940  // add (xor X, 0x80), 0xF..F80 --> (X << ShAmtC) >>s ShAmtC
941  // add (xor X, 0xF..F80), 0x80 --> (X << ShAmtC) >>s ShAmtC
942  if (Op0->hasOneUse() && *C2 == -(*C)) {
943  unsigned BitWidth = Ty->getScalarSizeInBits();
944  unsigned ShAmt = 0;
945  if (C->isPowerOf2())
946  ShAmt = BitWidth - C->logBase2() - 1;
947  else if (C2->isPowerOf2())
948  ShAmt = BitWidth - C2->logBase2() - 1;
949  if (ShAmt && MaskedValueIsZero(X, APInt::getHighBitsSet(BitWidth, ShAmt),
950  0, &Add)) {
951  Constant *ShAmtC = ConstantInt::get(Ty, ShAmt);
952  Value *NewShl = Builder.CreateShl(X, ShAmtC, "sext");
953  return BinaryOperator::CreateAShr(NewShl, ShAmtC);
954  }
955  }
956  }
957 
958  if (C->isOne() && Op0->hasOneUse()) {
959  // add (sext i1 X), 1 --> zext (not X)
960  // TODO: The smallest IR representation is (select X, 0, 1), and that would
961  // not require the one-use check. But we need to remove a transform in
962  // visitSelect and make sure that IR value tracking for select is equal or
963  // better than for these ops.
964  if (match(Op0, m_SExt(m_Value(X))) &&
965  X->getType()->getScalarSizeInBits() == 1)
966  return new ZExtInst(Builder.CreateNot(X), Ty);
967 
968  // Shifts and add used to flip and mask off the low bit:
969  // add (ashr (shl i32 X, 31), 31), 1 --> and (not X), 1
970  const APInt *C3;
971  if (match(Op0, m_AShr(m_Shl(m_Value(X), m_APInt(C2)), m_APInt(C3))) &&
972  C2 == C3 && *C2 == Ty->getScalarSizeInBits() - 1) {
973  Value *NotX = Builder.CreateNot(X);
974  return BinaryOperator::CreateAnd(NotX, ConstantInt::get(Ty, 1));
975  }
976  }
977 
978  return nullptr;
979 }
980 
981 // Matches multiplication expression Op * C where C is a constant. Returns the
982 // constant value in C and the other operand in Op. Returns true if such a
983 // match is found.
984 static bool MatchMul(Value *E, Value *&Op, APInt &C) {
985  const APInt *AI;
986  if (match(E, m_Mul(m_Value(Op), m_APInt(AI)))) {
987  C = *AI;
988  return true;
989  }
990  if (match(E, m_Shl(m_Value(Op), m_APInt(AI)))) {
991  C = APInt(AI->getBitWidth(), 1);
992  C <<= *AI;
993  return true;
994  }
995  return false;
996 }
997 
998 // Matches remainder expression Op % C where C is a constant. Returns the
999 // constant value in C and the other operand in Op. Returns the signedness of
1000 // the remainder operation in IsSigned. Returns true if such a match is
1001 // found.
1002 static bool MatchRem(Value *E, Value *&Op, APInt &C, bool &IsSigned) {
1003  const APInt *AI;
1004  IsSigned = false;
1005  if (match(E, m_SRem(m_Value(Op), m_APInt(AI)))) {
1006  IsSigned = true;
1007  C = *AI;
1008  return true;
1009  }
1010  if (match(E, m_URem(m_Value(Op), m_APInt(AI)))) {
1011  C = *AI;
1012  return true;
1013  }
1014  if (match(E, m_And(m_Value(Op), m_APInt(AI))) && (*AI + 1).isPowerOf2()) {
1015  C = *AI + 1;
1016  return true;
1017  }
1018  return false;
1019 }
1020 
1021 // Matches division expression Op / C with the given signedness as indicated
1022 // by IsSigned, where C is a constant. Returns the constant value in C and the
1023 // other operand in Op. Returns true if such a match is found.
1024 static bool MatchDiv(Value *E, Value *&Op, APInt &C, bool IsSigned) {
1025  const APInt *AI;
1026  if (IsSigned && match(E, m_SDiv(m_Value(Op), m_APInt(AI)))) {
1027  C = *AI;
1028  return true;
1029  }
1030  if (!IsSigned) {
1031  if (match(E, m_UDiv(m_Value(Op), m_APInt(AI)))) {
1032  C = *AI;
1033  return true;
1034  }
1035  if (match(E, m_LShr(m_Value(Op), m_APInt(AI)))) {
1036  C = APInt(AI->getBitWidth(), 1);
1037  C <<= *AI;
1038  return true;
1039  }
1040  }
1041  return false;
1042 }
1043 
1044 // Returns whether C0 * C1 with the given signedness overflows.
1045 static bool MulWillOverflow(APInt &C0, APInt &C1, bool IsSigned) {
1046  bool overflow;
1047  if (IsSigned)
1048  (void)C0.smul_ov(C1, overflow);
1049  else
1050  (void)C0.umul_ov(C1, overflow);
1051  return overflow;
1052 }
1053 
1054 // Simplifies X % C0 + (( X / C0 ) % C1) * C0 to X % (C0 * C1), where (C0 * C1)
1055 // does not overflow.
1057  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1058  Value *X, *MulOpV;
1059  APInt C0, MulOpC;
1060  bool IsSigned;
1061  // Match I = X % C0 + MulOpV * C0
1062  if (((MatchRem(LHS, X, C0, IsSigned) && MatchMul(RHS, MulOpV, MulOpC)) ||
1063  (MatchRem(RHS, X, C0, IsSigned) && MatchMul(LHS, MulOpV, MulOpC))) &&
1064  C0 == MulOpC) {
1065  Value *RemOpV;
1066  APInt C1;
1067  bool Rem2IsSigned;
1068  // Match MulOpC = RemOpV % C1
1069  if (MatchRem(MulOpV, RemOpV, C1, Rem2IsSigned) &&
1070  IsSigned == Rem2IsSigned) {
1071  Value *DivOpV;
1072  APInt DivOpC;
1073  // Match RemOpV = X / C0
1074  if (MatchDiv(RemOpV, DivOpV, DivOpC, IsSigned) && X == DivOpV &&
1075  C0 == DivOpC && !MulWillOverflow(C0, C1, IsSigned)) {
1076  Value *NewDivisor = ConstantInt::get(X->getType(), C0 * C1);
1077  return IsSigned ? Builder.CreateSRem(X, NewDivisor, "srem")
1078  : Builder.CreateURem(X, NewDivisor, "urem");
1079  }
1080  }
1081  }
1082 
1083  return nullptr;
1084 }
1085 
1086 /// Fold
1087 /// (1 << NBits) - 1
1088 /// Into:
1089 /// ~(-(1 << NBits))
1090 /// Because a 'not' is better for bit-tracking analysis and other transforms
1091 /// than an 'add'. The new shl is always nsw, and is nuw if old `and` was.
1094  Value *NBits;
1095  if (!match(&I, m_Add(m_OneUse(m_Shl(m_One(), m_Value(NBits))), m_AllOnes())))
1096  return nullptr;
1097 
1098  Constant *MinusOne = Constant::getAllOnesValue(NBits->getType());
1099  Value *NotMask = Builder.CreateShl(MinusOne, NBits, "notmask");
1100  // Be wary of constant folding.
1101  if (auto *BOp = dyn_cast<BinaryOperator>(NotMask)) {
1102  // Always NSW. But NUW propagates from `add`.
1103  BOp->setHasNoSignedWrap();
1104  BOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1105  }
1106 
1107  return BinaryOperator::CreateNot(NotMask, I.getName());
1108 }
1109 
1111  assert(I.getOpcode() == Instruction::Add && "Expecting add instruction");
1112  Type *Ty = I.getType();
1113  auto getUAddSat = [&]() {
1114  return Intrinsic::getDeclaration(I.getModule(), Intrinsic::uadd_sat, Ty);
1115  };
1116 
1117  // add (umin X, ~Y), Y --> uaddsat X, Y
1118  Value *X, *Y;
1119  if (match(&I, m_c_Add(m_c_UMin(m_Value(X), m_Not(m_Value(Y))),
1120  m_Deferred(Y))))
1121  return CallInst::Create(getUAddSat(), { X, Y });
1122 
1123  // add (umin X, ~C), C --> uaddsat X, C
1124  const APInt *C, *NotC;
1125  if (match(&I, m_Add(m_UMin(m_Value(X), m_APInt(NotC)), m_APInt(C))) &&
1126  *C == ~*NotC)
1127  return CallInst::Create(getUAddSat(), { X, ConstantInt::get(Ty, *C) });
1128 
1129  return nullptr;
1130 }
1131 
1134  BinaryOperator &I) {
1135  assert((I.getOpcode() == Instruction::Add ||
1136  I.getOpcode() == Instruction::Or ||
1137  I.getOpcode() == Instruction::Sub) &&
1138  "Expecting add/or/sub instruction");
1139 
1140  // We have a subtraction/addition between a (potentially truncated) *logical*
1141  // right-shift of X and a "select".
1142  Value *X, *Select;
1143  Instruction *LowBitsToSkip, *Extract;
1145  m_LShr(m_Value(X), m_Instruction(LowBitsToSkip)),
1146  m_Instruction(Extract))),
1147  m_Value(Select))))
1148  return nullptr;
1149 
1150  // `add`/`or` is commutative; but for `sub`, "select" *must* be on RHS.
1151  if (I.getOpcode() == Instruction::Sub && I.getOperand(1) != Select)
1152  return nullptr;
1153 
1154  Type *XTy = X->getType();
1155  bool HadTrunc = I.getType() != XTy;
1156 
1157  // If there was a truncation of extracted value, then we'll need to produce
1158  // one extra instruction, so we need to ensure one instruction will go away.
1159  if (HadTrunc && !match(&I, m_c_BinOp(m_OneUse(m_Value()), m_Value())))
1160  return nullptr;
1161 
1162  // Extraction should extract high NBits bits, with shift amount calculated as:
1163  // low bits to skip = shift bitwidth - high bits to extract
1164  // The shift amount itself may be extended, and we need to look past zero-ext
1165  // when matching NBits, that will matter for matching later.
1166  Constant *C;
1167  Value *NBits;
1168  if (!match(
1169  LowBitsToSkip,
1171  !match(C, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ,
1172  APInt(C->getType()->getScalarSizeInBits(),
1173  X->getType()->getScalarSizeInBits()))))
1174  return nullptr;
1175 
1176  // Sign-extending value can be zero-extended if we `sub`tract it,
1177  // or sign-extended otherwise.
1178  auto SkipExtInMagic = [&I](Value *&V) {
1179  if (I.getOpcode() == Instruction::Sub)
1180  match(V, m_ZExtOrSelf(m_Value(V)));
1181  else
1182  match(V, m_SExtOrSelf(m_Value(V)));
1183  };
1184 
1185  // Now, finally validate the sign-extending magic.
1186  // `select` itself may be appropriately extended, look past that.
1187  SkipExtInMagic(Select);
1188 
1189  ICmpInst::Predicate Pred;
1190  const APInt *Thr;
1191  Value *SignExtendingValue, *Zero;
1192  bool ShouldSignext;
1193  // It must be a select between two values we will later establish to be a
1194  // sign-extending value and a zero constant. The condition guarding the
1195  // sign-extension must be based on a sign bit of the same X we had in `lshr`.
1196  if (!match(Select, m_Select(m_ICmp(Pred, m_Specific(X), m_APInt(Thr)),
1197  m_Value(SignExtendingValue), m_Value(Zero))) ||
1198  !isSignBitCheck(Pred, *Thr, ShouldSignext))
1199  return nullptr;
1200 
1201  // icmp-select pair is commutative.
1202  if (!ShouldSignext)
1203  std::swap(SignExtendingValue, Zero);
1204 
1205  // If we should not perform sign-extension then we must add/or/subtract zero.
1206  if (!match(Zero, m_Zero()))
1207  return nullptr;
1208  // Otherwise, it should be some constant, left-shifted by the same NBits we
1209  // had in `lshr`. Said left-shift can also be appropriately extended.
1210  // Again, we must look past zero-ext when looking for NBits.
1211  SkipExtInMagic(SignExtendingValue);
1212  Constant *SignExtendingValueBaseConstant;
1213  if (!match(SignExtendingValue,
1214  m_Shl(m_Constant(SignExtendingValueBaseConstant),
1215  m_ZExtOrSelf(m_Specific(NBits)))))
1216  return nullptr;
1217  // If we `sub`, then the constant should be one, else it should be all-ones.
1218  if (I.getOpcode() == Instruction::Sub
1219  ? !match(SignExtendingValueBaseConstant, m_One())
1220  : !match(SignExtendingValueBaseConstant, m_AllOnes()))
1221  return nullptr;
1222 
1223  auto *NewAShr = BinaryOperator::CreateAShr(X, LowBitsToSkip,
1224  Extract->getName() + ".sext");
1225  NewAShr->copyIRFlags(Extract); // Preserve `exact`-ness.
1226  if (!HadTrunc)
1227  return NewAShr;
1228 
1229  Builder.Insert(NewAShr);
1230  return TruncInst::CreateTruncOrBitCast(NewAShr, I.getType());
1231 }
1232 
1233 /// This is a specialization of a more general transform from
1234 /// SimplifyUsingDistributiveLaws. If that code can be made to work optimally
1235 /// for multi-use cases or propagating nsw/nuw, then we would not need this.
1238  // TODO: Also handle mul by doubling the shift amount?
1239  assert((I.getOpcode() == Instruction::Add ||
1240  I.getOpcode() == Instruction::Sub) &&
1241  "Expected add/sub");
1242  auto *Op0 = dyn_cast<BinaryOperator>(I.getOperand(0));
1243  auto *Op1 = dyn_cast<BinaryOperator>(I.getOperand(1));
1244  if (!Op0 || !Op1 || !(Op0->hasOneUse() || Op1->hasOneUse()))
1245  return nullptr;
1246 
1247  Value *X, *Y, *ShAmt;
1248  if (!match(Op0, m_Shl(m_Value(X), m_Value(ShAmt))) ||
1249  !match(Op1, m_Shl(m_Value(Y), m_Specific(ShAmt))))
1250  return nullptr;
1251 
1252  // No-wrap propagates only when all ops have no-wrap.
1253  bool HasNSW = I.hasNoSignedWrap() && Op0->hasNoSignedWrap() &&
1254  Op1->hasNoSignedWrap();
1255  bool HasNUW = I.hasNoUnsignedWrap() && Op0->hasNoUnsignedWrap() &&
1256  Op1->hasNoUnsignedWrap();
1257 
1258  // add/sub (X << ShAmt), (Y << ShAmt) --> (add/sub X, Y) << ShAmt
1259  Value *NewMath = Builder.CreateBinOp(I.getOpcode(), X, Y);
1260  if (auto *NewI = dyn_cast<BinaryOperator>(NewMath)) {
1261  NewI->setHasNoSignedWrap(HasNSW);
1262  NewI->setHasNoUnsignedWrap(HasNUW);
1263  }
1264  auto *NewShl = BinaryOperator::CreateShl(NewMath, ShAmt);
1265  NewShl->setHasNoSignedWrap(HasNSW);
1266  NewShl->setHasNoUnsignedWrap(HasNUW);
1267  return NewShl;
1268 }
1269 
1271  if (Value *V = simplifyAddInst(I.getOperand(0), I.getOperand(1),
1272  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
1273  SQ.getWithInstruction(&I)))
1274  return replaceInstUsesWith(I, V);
1275 
1276  if (SimplifyAssociativeOrCommutative(I))
1277  return &I;
1278 
1279  if (Instruction *X = foldVectorBinop(I))
1280  return X;
1281 
1282  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1283  return Phi;
1284 
1285  // (A*B)+(A*C) -> A*(B+C) etc
1286  if (Value *V = SimplifyUsingDistributiveLaws(I))
1287  return replaceInstUsesWith(I, V);
1288 
1290  return R;
1291 
1292  if (Instruction *X = foldAddWithConstant(I))
1293  return X;
1294 
1295  if (Instruction *X = foldNoWrapAdd(I, Builder))
1296  return X;
1297 
1298  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1299  Type *Ty = I.getType();
1300  if (Ty->isIntOrIntVectorTy(1))
1301  return BinaryOperator::CreateXor(LHS, RHS);
1302 
1303  // X + X --> X << 1
1304  if (LHS == RHS) {
1305  auto *Shl = BinaryOperator::CreateShl(LHS, ConstantInt::get(Ty, 1));
1306  Shl->setHasNoSignedWrap(I.hasNoSignedWrap());
1307  Shl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1308  return Shl;
1309  }
1310 
1311  Value *A, *B;
1312  if (match(LHS, m_Neg(m_Value(A)))) {
1313  // -A + -B --> -(A + B)
1314  if (match(RHS, m_Neg(m_Value(B))))
1315  return BinaryOperator::CreateNeg(Builder.CreateAdd(A, B));
1316 
1317  // -A + B --> B - A
1318  return BinaryOperator::CreateSub(RHS, A);
1319  }
1320 
1321  // A + -B --> A - B
1322  if (match(RHS, m_Neg(m_Value(B))))
1323  return BinaryOperator::CreateSub(LHS, B);
1324 
1326  return replaceInstUsesWith(I, V);
1327 
1328  // (A + 1) + ~B --> A - B
1329  // ~B + (A + 1) --> A - B
1330  // (~B + A) + 1 --> A - B
1331  // (A + ~B) + 1 --> A - B
1332  if (match(&I, m_c_BinOp(m_Add(m_Value(A), m_One()), m_Not(m_Value(B)))) ||
1333  match(&I, m_BinOp(m_c_Add(m_Not(m_Value(B)), m_Value(A)), m_One())))
1334  return BinaryOperator::CreateSub(A, B);
1335 
1336  // (A + RHS) + RHS --> A + (RHS << 1)
1338  return BinaryOperator::CreateAdd(A, Builder.CreateShl(RHS, 1, "reass.add"));
1339 
1340  // LHS + (A + LHS) --> A + (LHS << 1)
1342  return BinaryOperator::CreateAdd(A, Builder.CreateShl(LHS, 1, "reass.add"));
1343 
1344  {
1345  // (A + C1) + (C2 - B) --> (A - B) + (C1 + C2)
1346  Constant *C1, *C2;
1347  if (match(&I, m_c_Add(m_Add(m_Value(A), m_ImmConstant(C1)),
1348  m_Sub(m_ImmConstant(C2), m_Value(B)))) &&
1349  (LHS->hasOneUse() || RHS->hasOneUse())) {
1350  Value *Sub = Builder.CreateSub(A, B);
1352  }
1353  }
1354 
1355  // X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1)
1356  if (Value *V = SimplifyAddWithRemainder(I)) return replaceInstUsesWith(I, V);
1357 
1358  // ((X s/ C1) << C2) + X => X s% -C1 where -C1 is 1 << C2
1359  const APInt *C1, *C2;
1360  if (match(LHS, m_Shl(m_SDiv(m_Specific(RHS), m_APInt(C1)), m_APInt(C2)))) {
1361  APInt one(C2->getBitWidth(), 1);
1362  APInt minusC1 = -(*C1);
1363  if (minusC1 == (one << *C2)) {
1364  Constant *NewRHS = ConstantInt::get(RHS->getType(), minusC1);
1365  return BinaryOperator::CreateSRem(RHS, NewRHS);
1366  }
1367  }
1368 
1369  // (A & 2^C1) + A => A & (2^C1 - 1) iff bit C1 in A is a sign bit
1370  if (match(&I, m_c_Add(m_And(m_Value(A), m_APInt(C1)), m_Deferred(A))) &&
1371  C1->isPowerOf2() && (ComputeNumSignBits(A) > C1->countLeadingZeros())) {
1372  Constant *NewMask = ConstantInt::get(RHS->getType(), *C1 - 1);
1373  return BinaryOperator::CreateAnd(A, NewMask);
1374  }
1375 
1376  // A+B --> A|B iff A and B have no bits set in common.
1377  if (haveNoCommonBitsSet(LHS, RHS, DL, &AC, &I, &DT))
1378  return BinaryOperator::CreateOr(LHS, RHS);
1379 
1380  if (Instruction *Ext = narrowMathIfNoOverflow(I))
1381  return Ext;
1382 
1383  // (add (xor A, B) (and A, B)) --> (or A, B)
1384  // (add (and A, B) (xor A, B)) --> (or A, B)
1385  if (match(&I, m_c_BinOp(m_Xor(m_Value(A), m_Value(B)),
1386  m_c_And(m_Deferred(A), m_Deferred(B)))))
1387  return BinaryOperator::CreateOr(A, B);
1388 
1389  // (add (or A, B) (and A, B)) --> (add A, B)
1390  // (add (and A, B) (or A, B)) --> (add A, B)
1391  if (match(&I, m_c_BinOp(m_Or(m_Value(A), m_Value(B)),
1392  m_c_And(m_Deferred(A), m_Deferred(B))))) {
1393  // Replacing operands in-place to preserve nuw/nsw flags.
1394  replaceOperand(I, 0, A);
1395  replaceOperand(I, 1, B);
1396  return &I;
1397  }
1398 
1399  // (add A (or A, -A)) --> (and (add A, -1) A)
1400  // (add A (or -A, A)) --> (and (add A, -1) A)
1401  // (add (or A, -A) A) --> (and (add A, -1) A)
1402  // (add (or -A, A) A) --> (and (add A, -1) A)
1404  m_Deferred(A)))))) {
1405  Value *Add =
1406  Builder.CreateAdd(A, Constant::getAllOnesValue(A->getType()), "",
1407  I.hasNoUnsignedWrap(), I.hasNoSignedWrap());
1408  return BinaryOperator::CreateAnd(Add, A);
1409  }
1410 
1411  // Canonicalize ((A & -A) - 1) --> ((A - 1) & ~A)
1412  // Forms all commutable operations, and simplifies ctpop -> cttz folds.
1413  if (match(&I,
1415  m_AllOnes()))) {
1417  Value *Dec = Builder.CreateAdd(A, AllOnes);
1418  Value *Not = Builder.CreateXor(A, AllOnes);
1419  return BinaryOperator::CreateAnd(Dec, Not);
1420  }
1421 
1422  // Disguised reassociation/factorization:
1423  // ~(A * C1) + A
1424  // ((A * -C1) - 1) + A
1425  // ((A * -C1) + A) - 1
1426  // (A * (1 - C1)) - 1
1427  if (match(&I,
1429  m_Deferred(A)))) {
1430  Type *Ty = I.getType();
1431  Constant *NewMulC = ConstantInt::get(Ty, 1 - *C1);
1432  Value *NewMul = Builder.CreateMul(A, NewMulC);
1434  }
1435 
1436  // (A * -2**C) + B --> B - (A << C)
1437  const APInt *NegPow2C;
1438  if (match(&I, m_c_Add(m_OneUse(m_Mul(m_Value(A), m_NegatedPower2(NegPow2C))),
1439  m_Value(B)))) {
1440  Constant *ShiftAmtC = ConstantInt::get(Ty, NegPow2C->countTrailingZeros());
1441  Value *Shl = Builder.CreateShl(A, ShiftAmtC);
1442  return BinaryOperator::CreateSub(B, Shl);
1443  }
1444 
1445  // TODO(jingyue): Consider willNotOverflowSignedAdd and
1446  // willNotOverflowUnsignedAdd to reduce the number of invocations of
1447  // computeKnownBits.
1448  bool Changed = false;
1449  if (!I.hasNoSignedWrap() && willNotOverflowSignedAdd(LHS, RHS, I)) {
1450  Changed = true;
1451  I.setHasNoSignedWrap(true);
1452  }
1453  if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedAdd(LHS, RHS, I)) {
1454  Changed = true;
1455  I.setHasNoUnsignedWrap(true);
1456  }
1457 
1459  return V;
1460 
1461  if (Instruction *V =
1462  canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
1463  return V;
1464 
1465  if (Instruction *SatAdd = foldToUnsignedSaturatedAdd(I))
1466  return SatAdd;
1467 
1468  // usub.sat(A, B) + B => umax(A, B)
1469  if (match(&I, m_c_BinOp(
1470  m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Value(A), m_Value(B))),
1471  m_Deferred(B)))) {
1472  return replaceInstUsesWith(I,
1473  Builder.CreateIntrinsic(Intrinsic::umax, {I.getType()}, {A, B}));
1474  }
1475 
1476  // ctpop(A) + ctpop(B) => ctpop(A | B) if A and B have no bits set in common.
1477  if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(A)))) &&
1478  match(RHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(B)))) &&
1479  haveNoCommonBitsSet(A, B, DL, &AC, &I, &DT))
1480  return replaceInstUsesWith(
1481  I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
1482  {Builder.CreateOr(A, B)}));
1483 
1484  return Changed ? &I : nullptr;
1485 }
1486 
1487 /// Eliminate an op from a linear interpolation (lerp) pattern.
1490  Value *X, *Y, *Z;
1493  m_Value(Z))))),
1495  return nullptr;
1496 
1497  // (Y * (1.0 - Z)) + (X * Z) --> Y + Z * (X - Y) [8 commuted variants]
1498  Value *XY = Builder.CreateFSubFMF(X, Y, &I);
1499  Value *MulZ = Builder.CreateFMulFMF(Z, XY, &I);
1500  return BinaryOperator::CreateFAddFMF(Y, MulZ, &I);
1501 }
1502 
1503 /// Factor a common operand out of fadd/fsub of fmul/fdiv.
1506  assert((I.getOpcode() == Instruction::FAdd ||
1507  I.getOpcode() == Instruction::FSub) && "Expecting fadd/fsub");
1508  assert(I.hasAllowReassoc() && I.hasNoSignedZeros() &&
1509  "FP factorization requires FMF");
1510 
1511  if (Instruction *Lerp = factorizeLerp(I, Builder))
1512  return Lerp;
1513 
1514  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1515  if (!Op0->hasOneUse() || !Op1->hasOneUse())
1516  return nullptr;
1517 
1518  Value *X, *Y, *Z;
1519  bool IsFMul;
1520  if ((match(Op0, m_FMul(m_Value(X), m_Value(Z))) &&
1521  match(Op1, m_c_FMul(m_Value(Y), m_Specific(Z)))) ||
1522  (match(Op0, m_FMul(m_Value(Z), m_Value(X))) &&
1523  match(Op1, m_c_FMul(m_Value(Y), m_Specific(Z)))))
1524  IsFMul = true;
1525  else if (match(Op0, m_FDiv(m_Value(X), m_Value(Z))) &&
1526  match(Op1, m_FDiv(m_Value(Y), m_Specific(Z))))
1527  IsFMul = false;
1528  else
1529  return nullptr;
1530 
1531  // (X * Z) + (Y * Z) --> (X + Y) * Z
1532  // (X * Z) - (Y * Z) --> (X - Y) * Z
1533  // (X / Z) + (Y / Z) --> (X + Y) / Z
1534  // (X / Z) - (Y / Z) --> (X - Y) / Z
1535  bool IsFAdd = I.getOpcode() == Instruction::FAdd;
1536  Value *XY = IsFAdd ? Builder.CreateFAddFMF(X, Y, &I)
1537  : Builder.CreateFSubFMF(X, Y, &I);
1538 
1539  // Bail out if we just created a denormal constant.
1540  // TODO: This is copied from a previous implementation. Is it necessary?
1541  const APFloat *C;
1542  if (match(XY, m_APFloat(C)) && !C->isNormal())
1543  return nullptr;
1544 
1545  return IsFMul ? BinaryOperator::CreateFMulFMF(XY, Z, &I)
1547 }
1548 
1550  if (Value *V = simplifyFAddInst(I.getOperand(0), I.getOperand(1),
1551  I.getFastMathFlags(),
1552  SQ.getWithInstruction(&I)))
1553  return replaceInstUsesWith(I, V);
1554 
1555  if (SimplifyAssociativeOrCommutative(I))
1556  return &I;
1557 
1558  if (Instruction *X = foldVectorBinop(I))
1559  return X;
1560 
1561  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1562  return Phi;
1563 
1564  if (Instruction *FoldedFAdd = foldBinOpIntoSelectOrPhi(I))
1565  return FoldedFAdd;
1566 
1567  // (-X) + Y --> Y - X
1568  Value *X, *Y;
1569  if (match(&I, m_c_FAdd(m_FNeg(m_Value(X)), m_Value(Y))))
1570  return BinaryOperator::CreateFSubFMF(Y, X, &I);
1571 
1572  // Similar to above, but look through fmul/fdiv for the negated term.
1573  // (-X * Y) + Z --> Z - (X * Y) [4 commuted variants]
1574  Value *Z;
1576  m_Value(Z)))) {
1577  Value *XY = Builder.CreateFMulFMF(X, Y, &I);
1578  return BinaryOperator::CreateFSubFMF(Z, XY, &I);
1579  }
1580  // (-X / Y) + Z --> Z - (X / Y) [2 commuted variants]
1581  // (X / -Y) + Z --> Z - (X / Y) [2 commuted variants]
1583  m_Value(Z))) ||
1585  m_Value(Z)))) {
1586  Value *XY = Builder.CreateFDivFMF(X, Y, &I);
1587  return BinaryOperator::CreateFSubFMF(Z, XY, &I);
1588  }
1589 
1590  // Check for (fadd double (sitofp x), y), see if we can merge this into an
1591  // integer add followed by a promotion.
1592  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1593  if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) {
1594  Value *LHSIntVal = LHSConv->getOperand(0);
1595  Type *FPType = LHSConv->getType();
1596 
1597  // TODO: This check is overly conservative. In many cases known bits
1598  // analysis can tell us that the result of the addition has less significant
1599  // bits than the integer type can hold.
1600  auto IsValidPromotion = [](Type *FTy, Type *ITy) {
1601  Type *FScalarTy = FTy->getScalarType();
1602  Type *IScalarTy = ITy->getScalarType();
1603 
1604  // Do we have enough bits in the significand to represent the result of
1605  // the integer addition?
1606  unsigned MaxRepresentableBits =
1608  return IScalarTy->getIntegerBitWidth() <= MaxRepresentableBits;
1609  };
1610 
1611  // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst))
1612  // ... if the constant fits in the integer value. This is useful for things
1613  // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer
1614  // requires a constant pool load, and generally allows the add to be better
1615  // instcombined.
1616  if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS))
1617  if (IsValidPromotion(FPType, LHSIntVal->getType())) {
1618  Constant *CI =
1619  ConstantExpr::getFPToSI(CFP, LHSIntVal->getType());
1620  if (LHSConv->hasOneUse() &&
1621  ConstantExpr::getSIToFP(CI, I.getType()) == CFP &&
1622  willNotOverflowSignedAdd(LHSIntVal, CI, I)) {
1623  // Insert the new integer add.
1624  Value *NewAdd = Builder.CreateNSWAdd(LHSIntVal, CI, "addconv");
1625  return new SIToFPInst(NewAdd, I.getType());
1626  }
1627  }
1628 
1629  // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y))
1630  if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) {
1631  Value *RHSIntVal = RHSConv->getOperand(0);
1632  // It's enough to check LHS types only because we require int types to
1633  // be the same for this transform.
1634  if (IsValidPromotion(FPType, LHSIntVal->getType())) {
1635  // Only do this if x/y have the same type, if at least one of them has a
1636  // single use (so we don't increase the number of int->fp conversions),
1637  // and if the integer add will not overflow.
1638  if (LHSIntVal->getType() == RHSIntVal->getType() &&
1639  (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
1640  willNotOverflowSignedAdd(LHSIntVal, RHSIntVal, I)) {
1641  // Insert the new integer add.
1642  Value *NewAdd = Builder.CreateNSWAdd(LHSIntVal, RHSIntVal, "addconv");
1643  return new SIToFPInst(NewAdd, I.getType());
1644  }
1645  }
1646  }
1647  }
1648 
1649  // Handle specials cases for FAdd with selects feeding the operation
1650  if (Value *V = SimplifySelectsFeedingBinaryOp(I, LHS, RHS))
1651  return replaceInstUsesWith(I, V);
1652 
1653  if (I.hasAllowReassoc() && I.hasNoSignedZeros()) {
1655  return F;
1656 
1657  // Try to fold fadd into start value of reduction intrinsic.
1658  if (match(&I, m_c_FAdd(m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(
1659  m_AnyZeroFP(), m_Value(X))),
1660  m_Value(Y)))) {
1661  // fadd (rdx 0.0, X), Y --> rdx Y, X
1662  return replaceInstUsesWith(
1663  I, Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,
1664  {X->getType()}, {Y, X}, &I));
1665  }
1666  const APFloat *StartC, *C;
1667  if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(
1668  m_APFloat(StartC), m_Value(X)))) &&
1669  match(RHS, m_APFloat(C))) {
1670  // fadd (rdx StartC, X), C --> rdx (C + StartC), X
1671  Constant *NewStartC = ConstantFP::get(I.getType(), *C + *StartC);
1672  return replaceInstUsesWith(
1673  I, Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,
1674  {X->getType()}, {NewStartC, X}, &I));
1675  }
1676 
1677  // (X * MulC) + X --> X * (MulC + 1.0)
1678  Constant *MulC;
1679  if (match(&I, m_c_FAdd(m_FMul(m_Value(X), m_ImmConstant(MulC)),
1680  m_Deferred(X)))) {
1681  if (Constant *NewMulC = ConstantFoldBinaryOpOperands(
1682  Instruction::FAdd, MulC, ConstantFP::get(I.getType(), 1.0), DL))
1683  return BinaryOperator::CreateFMulFMF(X, NewMulC, &I);
1684  }
1685 
1686  // (-X - Y) + (X + Z) --> Z - Y
1687  if (match(&I, m_c_FAdd(m_FSub(m_FNeg(m_Value(X)), m_Value(Y)),
1688  m_c_FAdd(m_Deferred(X), m_Value(Z)))))
1689  return BinaryOperator::CreateFSubFMF(Z, Y, &I);
1690 
1691  if (Value *V = FAddCombine(Builder).simplify(&I))
1692  return replaceInstUsesWith(I, V);
1693  }
1694 
1695  return nullptr;
1696 }
1697 
1698 /// Optimize pointer differences into the same array into a size. Consider:
1699 /// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer
1700 /// operands to the ptrtoint instructions for the LHS/RHS of the subtract.
1702  Type *Ty, bool IsNUW) {
1703  // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize
1704  // this.
1705  bool Swapped = false;
1706  GEPOperator *GEP1 = nullptr, *GEP2 = nullptr;
1707  if (!isa<GEPOperator>(LHS) && isa<GEPOperator>(RHS)) {
1708  std::swap(LHS, RHS);
1709  Swapped = true;
1710  }
1711 
1712  // Require at least one GEP with a common base pointer on both sides.
1713  if (auto *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
1714  // (gep X, ...) - X
1715  if (LHSGEP->getOperand(0)->stripPointerCasts() ==
1716  RHS->stripPointerCasts()) {
1717  GEP1 = LHSGEP;
1718  } else if (auto *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
1719  // (gep X, ...) - (gep X, ...)
1720  if (LHSGEP->getOperand(0)->stripPointerCasts() ==
1721  RHSGEP->getOperand(0)->stripPointerCasts()) {
1722  GEP1 = LHSGEP;
1723  GEP2 = RHSGEP;
1724  }
1725  }
1726  }
1727 
1728  if (!GEP1)
1729  return nullptr;
1730 
1731  if (GEP2) {
1732  // (gep X, ...) - (gep X, ...)
1733  //
1734  // Avoid duplicating the arithmetic if there are more than one non-constant
1735  // indices between the two GEPs and either GEP has a non-constant index and
1736  // multiple users. If zero non-constant index, the result is a constant and
1737  // there is no duplication. If one non-constant index, the result is an add
1738  // or sub with a constant, which is no larger than the original code, and
1739  // there's no duplicated arithmetic, even if either GEP has multiple
1740  // users. If more than one non-constant indices combined, as long as the GEP
1741  // with at least one non-constant index doesn't have multiple users, there
1742  // is no duplication.
1743  unsigned NumNonConstantIndices1 = GEP1->countNonConstantIndices();
1744  unsigned NumNonConstantIndices2 = GEP2->countNonConstantIndices();
1745  if (NumNonConstantIndices1 + NumNonConstantIndices2 > 1 &&
1746  ((NumNonConstantIndices1 > 0 && !GEP1->hasOneUse()) ||
1747  (NumNonConstantIndices2 > 0 && !GEP2->hasOneUse()))) {
1748  return nullptr;
1749  }
1750  }
1751 
1752  // Emit the offset of the GEP and an intptr_t.
1753  Value *Result = EmitGEPOffset(GEP1);
1754 
1755  // If this is a single inbounds GEP and the original sub was nuw,
1756  // then the final multiplication is also nuw.
1757  if (auto *I = dyn_cast<Instruction>(Result))
1758  if (IsNUW && !GEP2 && !Swapped && GEP1->isInBounds() &&
1759  I->getOpcode() == Instruction::Mul)
1760  I->setHasNoUnsignedWrap();
1761 
1762  // If we have a 2nd GEP of the same base pointer, subtract the offsets.
1763  // If both GEPs are inbounds, then the subtract does not have signed overflow.
1764  if (GEP2) {
1765  Value *Offset = EmitGEPOffset(GEP2);
1766  Result = Builder.CreateSub(Result, Offset, "gepdiff", /* NUW */ false,
1767  GEP1->isInBounds() && GEP2->isInBounds());
1768  }
1769 
1770  // If we have p - gep(p, ...) then we have to negate the result.
1771  if (Swapped)
1772  Result = Builder.CreateNeg(Result, "diff.neg");
1773 
1774  return Builder.CreateIntCast(Result, Ty, true);
1775 }
1776 
1779  Value *Op0 = I.getOperand(0);
1780  Value *Op1 = I.getOperand(1);
1781  Type *Ty = I.getType();
1782  auto *MinMax = dyn_cast<MinMaxIntrinsic>(Op1);
1783  if (!MinMax)
1784  return nullptr;
1785 
1786  // sub(add(X,Y), s/umin(X,Y)) --> s/umax(X,Y)
1787  // sub(add(X,Y), s/umax(X,Y)) --> s/umin(X,Y)
1788  Value *X = MinMax->getLHS();
1789  Value *Y = MinMax->getRHS();
1790  if (match(Op0, m_c_Add(m_Specific(X), m_Specific(Y))) &&
1791  (Op0->hasOneUse() || Op1->hasOneUse())) {
1792  Intrinsic::ID InvID = getInverseMinMaxIntrinsic(MinMax->getIntrinsicID());
1793  Function *F = Intrinsic::getDeclaration(I.getModule(), InvID, Ty);
1794  return CallInst::Create(F, {X, Y});
1795  }
1796 
1797  // sub(add(X,Y),umin(Y,Z)) --> add(X,usub.sat(Y,Z))
1798  // sub(add(X,Z),umin(Y,Z)) --> add(X,usub.sat(Z,Y))
1799  Value *Z;
1800  if (match(Op1, m_OneUse(m_UMin(m_Value(Y), m_Value(Z))))) {
1801  if (match(Op0, m_OneUse(m_c_Add(m_Specific(Y), m_Value(X))))) {
1802  Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, Ty, {Y, Z});
1803  return BinaryOperator::CreateAdd(X, USub);
1804  }
1805  if (match(Op0, m_OneUse(m_c_Add(m_Specific(Z), m_Value(X))))) {
1806  Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, Ty, {Z, Y});
1807  return BinaryOperator::CreateAdd(X, USub);
1808  }
1809  }
1810 
1811  // sub Op0, smin((sub nsw Op0, Z), 0) --> smax Op0, Z
1812  // sub Op0, smax((sub nsw Op0, Z), 0) --> smin Op0, Z
1813  if (MinMax->isSigned() && match(Y, m_ZeroInt()) &&
1814  match(X, m_NSWSub(m_Specific(Op0), m_Value(Z)))) {
1815  Intrinsic::ID InvID = getInverseMinMaxIntrinsic(MinMax->getIntrinsicID());
1816  Function *F = Intrinsic::getDeclaration(I.getModule(), InvID, Ty);
1817  return CallInst::Create(F, {Op0, Z});
1818  }
1819 
1820  return nullptr;
1821 }
1822 
1824  if (Value *V = simplifySubInst(I.getOperand(0), I.getOperand(1),
1825  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
1826  SQ.getWithInstruction(&I)))
1827  return replaceInstUsesWith(I, V);
1828 
1829  if (Instruction *X = foldVectorBinop(I))
1830  return X;
1831 
1832  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1833  return Phi;
1834 
1835  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1836 
1837  // If this is a 'B = x-(-A)', change to B = x+A.
1838  // We deal with this without involving Negator to preserve NSW flag.
1839  if (Value *V = dyn_castNegVal(Op1)) {
1841 
1842  if (const auto *BO = dyn_cast<BinaryOperator>(Op1)) {
1843  assert(BO->getOpcode() == Instruction::Sub &&
1844  "Expected a subtraction operator!");
1845  if (BO->hasNoSignedWrap() && I.hasNoSignedWrap())
1846  Res->setHasNoSignedWrap(true);
1847  } else {
1848  if (cast<Constant>(Op1)->isNotMinSignedValue() && I.hasNoSignedWrap())
1849  Res->setHasNoSignedWrap(true);
1850  }
1851 
1852  return Res;
1853  }
1854 
1855  // Try this before Negator to preserve NSW flag.
1857  return R;
1858 
1859  Constant *C;
1860  if (match(Op0, m_ImmConstant(C))) {
1861  Value *X;
1862  Constant *C2;
1863 
1864  // C-(X+C2) --> (C-C2)-X
1865  if (match(Op1, m_Add(m_Value(X), m_ImmConstant(C2))))
1866  return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
1867  }
1868 
1869  auto TryToNarrowDeduceFlags = [this, &I, &Op0, &Op1]() -> Instruction * {
1870  if (Instruction *Ext = narrowMathIfNoOverflow(I))
1871  return Ext;
1872 
1873  bool Changed = false;
1874  if (!I.hasNoSignedWrap() && willNotOverflowSignedSub(Op0, Op1, I)) {
1875  Changed = true;
1876  I.setHasNoSignedWrap(true);
1877  }
1878  if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedSub(Op0, Op1, I)) {
1879  Changed = true;
1880  I.setHasNoUnsignedWrap(true);
1881  }
1882 
1883  return Changed ? &I : nullptr;
1884  };
1885 
1886  // First, let's try to interpret `sub a, b` as `add a, (sub 0, b)`,
1887  // and let's try to sink `(sub 0, b)` into `b` itself. But only if this isn't
1888  // a pure negation used by a select that looks like abs/nabs.
1889  bool IsNegation = match(Op0, m_ZeroInt());
1890  if (!IsNegation || none_of(I.users(), [&I, Op1](const User *U) {
1891  const Instruction *UI = dyn_cast<Instruction>(U);
1892  if (!UI)
1893  return false;
1894  return match(UI,
1895  m_Select(m_Value(), m_Specific(Op1), m_Specific(&I))) ||
1896  match(UI, m_Select(m_Value(), m_Specific(&I), m_Specific(Op1)));
1897  })) {
1898  if (Value *NegOp1 = Negator::Negate(IsNegation, Op1, *this))
1899  return BinaryOperator::CreateAdd(NegOp1, Op0);
1900  }
1901  if (IsNegation)
1902  return TryToNarrowDeduceFlags(); // Should have been handled in Negator!
1903 
1904  // (A*B)-(A*C) -> A*(B-C) etc
1905  if (Value *V = SimplifyUsingDistributiveLaws(I))
1906  return replaceInstUsesWith(I, V);
1907 
1908  if (I.getType()->isIntOrIntVectorTy(1))
1909  return BinaryOperator::CreateXor(Op0, Op1);
1910 
1911  // Replace (-1 - A) with (~A).
1912  if (match(Op0, m_AllOnes()))
1913  return BinaryOperator::CreateNot(Op1);
1914 
1915  // (X + -1) - Y --> ~Y + X
1916  Value *X, *Y;
1917  if (match(Op0, m_OneUse(m_Add(m_Value(X), m_AllOnes()))))
1918  return BinaryOperator::CreateAdd(Builder.CreateNot(Op1), X);
1919 
1920  // Reassociate sub/add sequences to create more add instructions and
1921  // reduce dependency chains:
1922  // ((X - Y) + Z) - Op1 --> (X + Z) - (Y + Op1)
1923  Value *Z;
1925  m_Value(Z))))) {
1926  Value *XZ = Builder.CreateAdd(X, Z);
1927  Value *YW = Builder.CreateAdd(Y, Op1);
1928  return BinaryOperator::CreateSub(XZ, YW);
1929  }
1930 
1931  // ((X - Y) - Op1) --> X - (Y + Op1)
1932  if (match(Op0, m_OneUse(m_Sub(m_Value(X), m_Value(Y))))) {
1933  Value *Add = Builder.CreateAdd(Y, Op1);
1934  return BinaryOperator::CreateSub(X, Add);
1935  }
1936 
1937  // (~X) - (~Y) --> Y - X
1938  // This is placed after the other reassociations and explicitly excludes a
1939  // sub-of-sub pattern to avoid infinite looping.
1940  if (isFreeToInvert(Op0, Op0->hasOneUse()) &&
1941  isFreeToInvert(Op1, Op1->hasOneUse()) &&
1942  !match(Op0, m_Sub(m_ImmConstant(), m_Value()))) {
1943  Value *NotOp0 = Builder.CreateNot(Op0);
1944  Value *NotOp1 = Builder.CreateNot(Op1);
1945  return BinaryOperator::CreateSub(NotOp1, NotOp0);
1946  }
1947 
1948  auto m_AddRdx = [](Value *&Vec) {
1949  return m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_add>(m_Value(Vec)));
1950  };
1951  Value *V0, *V1;
1952  if (match(Op0, m_AddRdx(V0)) && match(Op1, m_AddRdx(V1)) &&
1953  V0->getType() == V1->getType()) {
1954  // Difference of sums is sum of differences:
1955  // add_rdx(V0) - add_rdx(V1) --> add_rdx(V0 - V1)
1956  Value *Sub = Builder.CreateSub(V0, V1);
1957  Value *Rdx = Builder.CreateIntrinsic(Intrinsic::vector_reduce_add,
1958  {Sub->getType()}, {Sub});
1959  return replaceInstUsesWith(I, Rdx);
1960  }
1961 
1962  if (Constant *C = dyn_cast<Constant>(Op0)) {
1963  Value *X;
1964  if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
1965  // C - (zext bool) --> bool ? C - 1 : C
1967  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
1968  // C - (sext bool) --> bool ? C + 1 : C
1970 
1971  // C - ~X == X + (1+C)
1972  if (match(Op1, m_Not(m_Value(X))))
1974 
1975  // Try to fold constant sub into select arguments.
1976  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1977  if (Instruction *R = FoldOpIntoSelect(I, SI))
1978  return R;
1979 
1980  // Try to fold constant sub into PHI values.
1981  if (PHINode *PN = dyn_cast<PHINode>(Op1))
1982  if (Instruction *R = foldOpIntoPhi(I, PN))
1983  return R;
1984 
1985  Constant *C2;
1986 
1987  // C-(C2-X) --> X+(C-C2)
1988  if (match(Op1, m_Sub(m_ImmConstant(C2), m_Value(X))))
1990  }
1991 
1992  const APInt *Op0C;
1993  if (match(Op0, m_APInt(Op0C)) && Op0C->isMask()) {
1994  // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known
1995  // zero.
1996  KnownBits RHSKnown = computeKnownBits(Op1, 0, &I);
1997  if ((*Op0C | RHSKnown.Zero).isAllOnes())
1998  return BinaryOperator::CreateXor(Op1, Op0);
1999  }
2000 
2001  {
2002  Value *Y;
2003  // X-(X+Y) == -Y X-(Y+X) == -Y
2004  if (match(Op1, m_c_Add(m_Specific(Op0), m_Value(Y))))
2005  return BinaryOperator::CreateNeg(Y);
2006 
2007  // (X-Y)-X == -Y
2008  if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))
2009  return BinaryOperator::CreateNeg(Y);
2010  }
2011 
2012  // (sub (or A, B) (and A, B)) --> (xor A, B)
2013  {
2014  Value *A, *B;
2015  if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
2016  match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
2017  return BinaryOperator::CreateXor(A, B);
2018  }
2019 
2020  // (sub (add A, B) (or A, B)) --> (and A, B)
2021  {
2022  Value *A, *B;
2023  if (match(Op0, m_Add(m_Value(A), m_Value(B))) &&
2024  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
2025  return BinaryOperator::CreateAnd(A, B);
2026  }
2027 
2028  // (sub (add A, B) (and A, B)) --> (or A, B)
2029  {
2030  Value *A, *B;
2031  if (match(Op0, m_Add(m_Value(A), m_Value(B))) &&
2032  match(Op1, m_c_And(m_Specific(A), m_Specific(B))))
2033  return BinaryOperator::CreateOr(A, B);
2034  }
2035 
2036  // (sub (and A, B) (or A, B)) --> neg (xor A, B)
2037  {
2038  Value *A, *B;
2039  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2040  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))) &&
2041  (Op0->hasOneUse() || Op1->hasOneUse()))
2042  return BinaryOperator::CreateNeg(Builder.CreateXor(A, B));
2043  }
2044 
2045  // (sub (or A, B), (xor A, B)) --> (and A, B)
2046  {
2047  Value *A, *B;
2048  if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
2049  match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
2050  return BinaryOperator::CreateAnd(A, B);
2051  }
2052 
2053  // (sub (xor A, B) (or A, B)) --> neg (and A, B)
2054  {
2055  Value *A, *B;
2056  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
2057  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))) &&
2058  (Op0->hasOneUse() || Op1->hasOneUse()))
2059  return BinaryOperator::CreateNeg(Builder.CreateAnd(A, B));
2060  }
2061 
2062  {
2063  Value *Y;
2064  // ((X | Y) - X) --> (~X & Y)
2065  if (match(Op0, m_OneUse(m_c_Or(m_Value(Y), m_Specific(Op1)))))
2066  return BinaryOperator::CreateAnd(
2067  Y, Builder.CreateNot(Op1, Op1->getName() + ".not"));
2068  }
2069 
2070  {
2071  // (sub (and Op1, (neg X)), Op1) --> neg (and Op1, (add X, -1))
2072  Value *X;
2073  if (match(Op0, m_OneUse(m_c_And(m_Specific(Op1),
2074  m_OneUse(m_Neg(m_Value(X))))))) {
2075  return BinaryOperator::CreateNeg(Builder.CreateAnd(
2076  Op1, Builder.CreateAdd(X, Constant::getAllOnesValue(I.getType()))));
2077  }
2078  }
2079 
2080  {
2081  // (sub (and Op1, C), Op1) --> neg (and Op1, ~C)
2082  Constant *C;
2083  if (match(Op0, m_OneUse(m_And(m_Specific(Op1), m_Constant(C))))) {
2085  Builder.CreateAnd(Op1, Builder.CreateNot(C)));
2086  }
2087  }
2088 
2089  if (Instruction *R = foldSubOfMinMax(I, Builder))
2090  return R;
2091 
2092  {
2093  // If we have a subtraction between some value and a select between
2094  // said value and something else, sink subtraction into select hands, i.e.:
2095  // sub (select %Cond, %TrueVal, %FalseVal), %Op1
2096  // ->
2097  // select %Cond, (sub %TrueVal, %Op1), (sub %FalseVal, %Op1)
2098  // or
2099  // sub %Op0, (select %Cond, %TrueVal, %FalseVal)
2100  // ->
2101  // select %Cond, (sub %Op0, %TrueVal), (sub %Op0, %FalseVal)
2102  // This will result in select between new subtraction and 0.
2103  auto SinkSubIntoSelect =
2104  [Ty = I.getType()](Value *Select, Value *OtherHandOfSub,
2105  auto SubBuilder) -> Instruction * {
2106  Value *Cond, *TrueVal, *FalseVal;
2108  m_Value(FalseVal)))))
2109  return nullptr;
2110  if (OtherHandOfSub != TrueVal && OtherHandOfSub != FalseVal)
2111  return nullptr;
2112  // While it is really tempting to just create two subtractions and let
2113  // InstCombine fold one of those to 0, it isn't possible to do so
2114  // because of worklist visitation order. So ugly it is.
2115  bool OtherHandOfSubIsTrueVal = OtherHandOfSub == TrueVal;
2116  Value *NewSub = SubBuilder(OtherHandOfSubIsTrueVal ? FalseVal : TrueVal);
2117  Constant *Zero = Constant::getNullValue(Ty);
2118  SelectInst *NewSel =
2119  SelectInst::Create(Cond, OtherHandOfSubIsTrueVal ? Zero : NewSub,
2120  OtherHandOfSubIsTrueVal ? NewSub : Zero);
2121  // Preserve prof metadata if any.
2122  NewSel->copyMetadata(cast<Instruction>(*Select));
2123  return NewSel;
2124  };
2125  if (Instruction *NewSel = SinkSubIntoSelect(
2126  /*Select=*/Op0, /*OtherHandOfSub=*/Op1,
2127  [Builder = &Builder, Op1](Value *OtherHandOfSelect) {
2128  return Builder->CreateSub(OtherHandOfSelect,
2129  /*OtherHandOfSub=*/Op1);
2130  }))
2131  return NewSel;
2132  if (Instruction *NewSel = SinkSubIntoSelect(
2133  /*Select=*/Op1, /*OtherHandOfSub=*/Op0,
2134  [Builder = &Builder, Op0](Value *OtherHandOfSelect) {
2135  return Builder->CreateSub(/*OtherHandOfSub=*/Op0,
2136  OtherHandOfSelect);
2137  }))
2138  return NewSel;
2139  }
2140 
2141  // (X - (X & Y)) --> (X & ~Y)
2142  if (match(Op1, m_c_And(m_Specific(Op0), m_Value(Y))) &&
2143  (Op1->hasOneUse() || isa<Constant>(Y)))
2144  return BinaryOperator::CreateAnd(
2145  Op0, Builder.CreateNot(Y, Y->getName() + ".not"));
2146 
2147  // ~X - Min/Max(~X, Y) -> ~Min/Max(X, ~Y) - X
2148  // ~X - Min/Max(Y, ~X) -> ~Min/Max(X, ~Y) - X
2149  // Min/Max(~X, Y) - ~X -> X - ~Min/Max(X, ~Y)
2150  // Min/Max(Y, ~X) - ~X -> X - ~Min/Max(X, ~Y)
2151  // As long as Y is freely invertible, this will be neutral or a win.
2152  // Note: We don't generate the inverse max/min, just create the 'not' of
2153  // it and let other folds do the rest.
2154  if (match(Op0, m_Not(m_Value(X))) &&
2155  match(Op1, m_c_MaxOrMin(m_Specific(Op0), m_Value(Y))) &&
2156  !Op0->hasNUsesOrMore(3) && isFreeToInvert(Y, Y->hasOneUse())) {
2157  Value *Not = Builder.CreateNot(Op1);
2158  return BinaryOperator::CreateSub(Not, X);
2159  }
2160  if (match(Op1, m_Not(m_Value(X))) &&
2161  match(Op0, m_c_MaxOrMin(m_Specific(Op1), m_Value(Y))) &&
2162  !Op1->hasNUsesOrMore(3) && isFreeToInvert(Y, Y->hasOneUse())) {
2163  Value *Not = Builder.CreateNot(Op0);
2164  return BinaryOperator::CreateSub(X, Not);
2165  }
2166 
2167  // Optimize pointer differences into the same array into a size. Consider:
2168  // &A[10] - &A[0]: we should compile this to "10".
2169  Value *LHSOp, *RHSOp;
2170  if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
2171  match(Op1, m_PtrToInt(m_Value(RHSOp))))
2172  if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType(),
2173  I.hasNoUnsignedWrap()))
2174  return replaceInstUsesWith(I, Res);
2175 
2176  // trunc(p)-trunc(q) -> trunc(p-q)
2177  if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) &&
2178  match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp)))))
2179  if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType(),
2180  /* IsNUW */ false))
2181  return replaceInstUsesWith(I, Res);
2182 
2183  // Canonicalize a shifty way to code absolute value to the common pattern.
2184  // There are 2 potential commuted variants.
2185  // We're relying on the fact that we only do this transform when the shift has
2186  // exactly 2 uses and the xor has exactly 1 use (otherwise, we might increase
2187  // instructions).
2188  Value *A;
2189  const APInt *ShAmt;
2190  Type *Ty = I.getType();
2191  if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
2192  Op1->hasNUses(2) && *ShAmt == Ty->getScalarSizeInBits() - 1 &&
2193  match(Op0, m_OneUse(m_c_Xor(m_Specific(A), m_Specific(Op1))))) {
2194  // B = ashr i32 A, 31 ; smear the sign bit
2195  // sub (xor A, B), B ; flip bits if negative and subtract -1 (add 1)
2196  // --> (A < 0) ? -A : A
2197  Value *IsNeg = Builder.CreateIsNeg(A);
2198  // Copy the nuw/nsw flags from the sub to the negate.
2199  Value *NegA = Builder.CreateNeg(A, "", I.hasNoUnsignedWrap(),
2200  I.hasNoSignedWrap());
2201  return SelectInst::Create(IsNeg, NegA, A);
2202  }
2203 
2204  // If we are subtracting a low-bit masked subset of some value from an add
2205  // of that same value with no low bits changed, that is clearing some low bits
2206  // of the sum:
2207  // sub (X + AddC), (X & AndC) --> and (X + AddC), ~AndC
2208  const APInt *AddC, *AndC;
2209  if (match(Op0, m_Add(m_Value(X), m_APInt(AddC))) &&
2210  match(Op1, m_And(m_Specific(X), m_APInt(AndC)))) {
2211  unsigned BitWidth = Ty->getScalarSizeInBits();
2212  unsigned Cttz = AddC->countTrailingZeros();
2213  APInt HighMask(APInt::getHighBitsSet(BitWidth, BitWidth - Cttz));
2214  if ((HighMask & *AndC).isZero())
2215  return BinaryOperator::CreateAnd(Op0, ConstantInt::get(Ty, ~(*AndC)));
2216  }
2217 
2218  if (Instruction *V =
2219  canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
2220  return V;
2221 
2222  // X - usub.sat(X, Y) => umin(X, Y)
2223  if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Specific(Op0),
2224  m_Value(Y)))))
2225  return replaceInstUsesWith(
2226  I, Builder.CreateIntrinsic(Intrinsic::umin, {I.getType()}, {Op0, Y}));
2227 
2228  // umax(X, Op1) - Op1 --> usub.sat(X, Op1)
2229  // TODO: The one-use restriction is not strictly necessary, but it may
2230  // require improving other pattern matching and/or codegen.
2231  if (match(Op0, m_OneUse(m_c_UMax(m_Value(X), m_Specific(Op1)))))
2232  return replaceInstUsesWith(
2233  I, Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {X, Op1}));
2234 
2235  // Op0 - umin(X, Op0) --> usub.sat(Op0, X)
2236  if (match(Op1, m_OneUse(m_c_UMin(m_Value(X), m_Specific(Op0)))))
2237  return replaceInstUsesWith(
2238  I, Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {Op0, X}));
2239 
2240  // Op0 - umax(X, Op0) --> 0 - usub.sat(X, Op0)
2241  if (match(Op1, m_OneUse(m_c_UMax(m_Value(X), m_Specific(Op0))))) {
2242  Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {X, Op0});
2243  return BinaryOperator::CreateNeg(USub);
2244  }
2245 
2246  // umin(X, Op1) - Op1 --> 0 - usub.sat(Op1, X)
2247  if (match(Op0, m_OneUse(m_c_UMin(m_Value(X), m_Specific(Op1))))) {
2248  Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {Op1, X});
2249  return BinaryOperator::CreateNeg(USub);
2250  }
2251 
2252  // C - ctpop(X) => ctpop(~X) if C is bitwidth
2253  if (match(Op0, m_SpecificInt(Ty->getScalarSizeInBits())) &&
2254  match(Op1, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(X)))))
2255  return replaceInstUsesWith(
2256  I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
2257  {Builder.CreateNot(X)}));
2258 
2259  return TryToNarrowDeduceFlags();
2260 }
2261 
2262 /// This eliminates floating-point negation in either 'fneg(X)' or
2263 /// 'fsub(-0.0, X)' form by combining into a constant operand.
2265  // This is limited with one-use because fneg is assumed better for
2266  // reassociation and cheaper in codegen than fmul/fdiv.
2267  // TODO: Should the m_OneUse restriction be removed?
2268  Instruction *FNegOp;
2269  if (!match(&I, m_FNeg(m_OneUse(m_Instruction(FNegOp)))))
2270  return nullptr;
2271 
2272  Value *X;
2273  Constant *C;
2274 
2275  // Fold negation into constant operand.
2276  // -(X * C) --> X * (-C)
2277  if (match(FNegOp, m_FMul(m_Value(X), m_Constant(C))))
2278  if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
2279  return BinaryOperator::CreateFMulFMF(X, NegC, &I);
2280  // -(X / C) --> X / (-C)
2281  if (match(FNegOp, m_FDiv(m_Value(X), m_Constant(C))))
2282  if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
2283  return BinaryOperator::CreateFDivFMF(X, NegC, &I);
2284  // -(C / X) --> (-C) / X
2285  if (match(FNegOp, m_FDiv(m_Constant(C), m_Value(X))))
2286  if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL)) {
2287  Instruction *FDiv = BinaryOperator::CreateFDivFMF(NegC, X, &I);
2288 
2289  // Intersect 'nsz' and 'ninf' because those special value exceptions may
2290  // not apply to the fdiv. Everything else propagates from the fneg.
2291  // TODO: We could propagate nsz/ninf from fdiv alone?
2292  FastMathFlags FMF = I.getFastMathFlags();
2293  FastMathFlags OpFMF = FNegOp->getFastMathFlags();
2294  FDiv->setHasNoSignedZeros(FMF.noSignedZeros() && OpFMF.noSignedZeros());
2295  FDiv->setHasNoInfs(FMF.noInfs() && OpFMF.noInfs());
2296  return FDiv;
2297  }
2298  // With NSZ [ counter-example with -0.0: -(-0.0 + 0.0) != 0.0 + -0.0 ]:
2299  // -(X + C) --> -X + -C --> -C - X
2300  if (I.hasNoSignedZeros() && match(FNegOp, m_FAdd(m_Value(X), m_Constant(C))))
2301  if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
2302  return BinaryOperator::CreateFSubFMF(NegC, X, &I);
2303 
2304  return nullptr;
2305 }
2306 
2309  Value *FNeg;
2310  if (!match(&I, m_FNeg(m_Value(FNeg))))
2311  return nullptr;
2312 
2313  Value *X, *Y;
2314  if (match(FNeg, m_OneUse(m_FMul(m_Value(X), m_Value(Y)))))
2315  return BinaryOperator::CreateFMulFMF(Builder.CreateFNegFMF(X, &I), Y, &I);
2316 
2317  if (match(FNeg, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))))
2318  return BinaryOperator::CreateFDivFMF(Builder.CreateFNegFMF(X, &I), Y, &I);
2319 
2320  return nullptr;
2321 }
2322 
2324  Value *Op = I.getOperand(0);
2325 
2326  if (Value *V = simplifyFNegInst(Op, I.getFastMathFlags(),
2327  getSimplifyQuery().getWithInstruction(&I)))
2328  return replaceInstUsesWith(I, V);
2329 
2331  return X;
2332 
2333  Value *X, *Y;
2334 
2335  // If we can ignore the sign of zeros: -(X - Y) --> (Y - X)
2336  if (I.hasNoSignedZeros() &&
2338  return BinaryOperator::CreateFSubFMF(Y, X, &I);
2339 
2341  return R;
2342 
2343  // Try to eliminate fneg if at least 1 arm of the select is negated.
2344  Value *Cond;
2346  // Unlike most transforms, this one is not safe to propagate nsz unless
2347  // it is present on the original select. (We are conservatively intersecting
2348  // the nsz flags from the select and root fneg instruction.)
2349  auto propagateSelectFMF = [&](SelectInst *S, bool CommonOperand) {
2350  S->copyFastMathFlags(&I);
2351  if (auto *OldSel = dyn_cast<SelectInst>(Op))
2352  if (!OldSel->hasNoSignedZeros() && !CommonOperand &&
2353  !isGuaranteedNotToBeUndefOrPoison(OldSel->getCondition()))
2354  S->setHasNoSignedZeros(false);
2355  };
2356  // -(Cond ? -P : Y) --> Cond ? P : -Y
2357  Value *P;
2358  if (match(X, m_FNeg(m_Value(P)))) {
2359  Value *NegY = Builder.CreateFNegFMF(Y, &I, Y->getName() + ".neg");
2360  SelectInst *NewSel = SelectInst::Create(Cond, P, NegY);
2361  propagateSelectFMF(NewSel, P == Y);
2362  return NewSel;
2363  }
2364  // -(Cond ? X : -P) --> Cond ? -X : P
2365  if (match(Y, m_FNeg(m_Value(P)))) {
2366  Value *NegX = Builder.CreateFNegFMF(X, &I, X->getName() + ".neg");
2367  SelectInst *NewSel = SelectInst::Create(Cond, NegX, P);
2368  propagateSelectFMF(NewSel, P == X);
2369  return NewSel;
2370  }
2371  }
2372 
2373  return nullptr;
2374 }
2375 
2377  if (Value *V = simplifyFSubInst(I.getOperand(0), I.getOperand(1),
2378  I.getFastMathFlags(),
2379  getSimplifyQuery().getWithInstruction(&I)))
2380  return replaceInstUsesWith(I, V);
2381 
2382  if (Instruction *X = foldVectorBinop(I))
2383  return X;
2384 
2385  if (Instruction *Phi = foldBinopWithPhiOperands(I))
2386  return Phi;
2387 
2388  // Subtraction from -0.0 is the canonical form of fneg.
2389  // fsub -0.0, X ==> fneg X
2390  // fsub nsz 0.0, X ==> fneg nsz X
2391  //
2392  // FIXME This matcher does not respect FTZ or DAZ yet:
2393  // fsub -0.0, Denorm ==> +-0
2394  // fneg Denorm ==> -Denorm
2395  Value *Op;
2396  if (match(&I, m_FNeg(m_Value(Op))))
2397  return UnaryOperator::CreateFNegFMF(Op, &I);
2398 
2400  return X;
2401 
2403  return R;
2404 
2405  Value *X, *Y;
2406  Constant *C;
2407 
2408  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2409  // If Op0 is not -0.0 or we can ignore -0.0: Z - (X - Y) --> Z + (Y - X)
2410  // Canonicalize to fadd to make analysis easier.
2411  // This can also help codegen because fadd is commutative.
2412  // Note that if this fsub was really an fneg, the fadd with -0.0 will get
2413  // killed later. We still limit that particular transform with 'hasOneUse'
2414  // because an fneg is assumed better/cheaper than a generic fsub.
2415  if (I.hasNoSignedZeros() || CannotBeNegativeZero(Op0, SQ.TLI)) {
2416  if (match(Op1, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) {
2417  Value *NewSub = Builder.CreateFSubFMF(Y, X, &I);
2418  return BinaryOperator::CreateFAddFMF(Op0, NewSub, &I);
2419  }
2420  }
2421 
2422  // (-X) - Op1 --> -(X + Op1)
2423  if (I.hasNoSignedZeros() && !isa<ConstantExpr>(Op0) &&
2424  match(Op0, m_OneUse(m_FNeg(m_Value(X))))) {
2425  Value *FAdd = Builder.CreateFAddFMF(X, Op1, &I);
2427  }
2428 
2429  if (isa<Constant>(Op0))
2430  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
2431  if (Instruction *NV = FoldOpIntoSelect(I, SI))
2432  return NV;
2433 
2434  // X - C --> X + (-C)
2435  // But don't transform constant expressions because there's an inverse fold
2436  // for X + (-Y) --> X - Y.
2437  if (match(Op1, m_ImmConstant(C)))
2438  if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
2439  return BinaryOperator::CreateFAddFMF(Op0, NegC, &I);
2440 
2441  // X - (-Y) --> X + Y
2442  if (match(Op1, m_FNeg(m_Value(Y))))
2443  return BinaryOperator::CreateFAddFMF(Op0, Y, &I);
2444 
2445  // Similar to above, but look through a cast of the negated value:
2446  // X - (fptrunc(-Y)) --> X + fptrunc(Y)
2447  Type *Ty = I.getType();
2448  if (match(Op1, m_OneUse(m_FPTrunc(m_FNeg(m_Value(Y))))))
2449  return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPTrunc(Y, Ty), &I);
2450 
2451  // X - (fpext(-Y)) --> X + fpext(Y)
2452  if (match(Op1, m_OneUse(m_FPExt(m_FNeg(m_Value(Y))))))
2453  return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPExt(Y, Ty), &I);
2454 
2455  // Similar to above, but look through fmul/fdiv of the negated value:
2456  // Op0 - (-X * Y) --> Op0 + (X * Y)
2457  // Op0 - (Y * -X) --> Op0 + (X * Y)
2458  if (match(Op1, m_OneUse(m_c_FMul(m_FNeg(m_Value(X)), m_Value(Y))))) {
2459  Value *FMul = Builder.CreateFMulFMF(X, Y, &I);
2460  return BinaryOperator::CreateFAddFMF(Op0, FMul, &I);
2461  }
2462  // Op0 - (-X / Y) --> Op0 + (X / Y)
2463  // Op0 - (X / -Y) --> Op0 + (X / Y)
2464  if (match(Op1, m_OneUse(m_FDiv(m_FNeg(m_Value(X)), m_Value(Y)))) ||
2465  match(Op1, m_OneUse(m_FDiv(m_Value(X), m_FNeg(m_Value(Y)))))) {
2466  Value *FDiv = Builder.CreateFDivFMF(X, Y, &I);
2467  return BinaryOperator::CreateFAddFMF(Op0, FDiv, &I);
2468  }
2469 
2470  // Handle special cases for FSub with selects feeding the operation
2471  if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
2472  return replaceInstUsesWith(I, V);
2473 
2474  if (I.hasAllowReassoc() && I.hasNoSignedZeros()) {
2475  // (Y - X) - Y --> -X
2476  if (match(Op0, m_FSub(m_Specific(Op1), m_Value(X))))
2477  return UnaryOperator::CreateFNegFMF(X, &I);
2478 
2479  // Y - (X + Y) --> -X
2480  // Y - (Y + X) --> -X
2481  if (match(Op1, m_c_FAdd(m_Specific(Op0), m_Value(X))))
2482  return UnaryOperator::CreateFNegFMF(X, &I);
2483 
2484  // (X * C) - X --> X * (C - 1.0)
2485  if (match(Op0, m_FMul(m_Specific(Op1), m_Constant(C)))) {
2486  if (Constant *CSubOne = ConstantFoldBinaryOpOperands(
2487  Instruction::FSub, C, ConstantFP::get(Ty, 1.0), DL))
2488  return BinaryOperator::CreateFMulFMF(Op1, CSubOne, &I);
2489  }
2490  // X - (X * C) --> X * (1.0 - C)
2491  if (match(Op1, m_FMul(m_Specific(Op0), m_Constant(C)))) {
2492  if (Constant *OneSubC = ConstantFoldBinaryOpOperands(
2493  Instruction::FSub, ConstantFP::get(Ty, 1.0), C, DL))
2494  return BinaryOperator::CreateFMulFMF(Op0, OneSubC, &I);
2495  }
2496 
2497  // Reassociate fsub/fadd sequences to create more fadd instructions and
2498  // reduce dependency chains:
2499  // ((X - Y) + Z) - Op1 --> (X + Z) - (Y + Op1)
2500  Value *Z;
2502  m_Value(Z))))) {
2503  Value *XZ = Builder.CreateFAddFMF(X, Z, &I);
2504  Value *YW = Builder.CreateFAddFMF(Y, Op1, &I);
2505  return BinaryOperator::CreateFSubFMF(XZ, YW, &I);
2506  }
2507 
2508  auto m_FaddRdx = [](Value *&Sum, Value *&Vec) {
2509  return m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(m_Value(Sum),
2510  m_Value(Vec)));
2511  };
2512  Value *A0, *A1, *V0, *V1;
2513  if (match(Op0, m_FaddRdx(A0, V0)) && match(Op1, m_FaddRdx(A1, V1)) &&
2514  V0->getType() == V1->getType()) {
2515  // Difference of sums is sum of differences:
2516  // add_rdx(A0, V0) - add_rdx(A1, V1) --> add_rdx(A0, V0 - V1) - A1
2517  Value *Sub = Builder.CreateFSubFMF(V0, V1, &I);
2518  Value *Rdx = Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,
2519  {Sub->getType()}, {A0, Sub}, &I);
2520  return BinaryOperator::CreateFSubFMF(Rdx, A1, &I);
2521  }
2522 
2524  return F;
2525 
2526  // TODO: This performs reassociative folds for FP ops. Some fraction of the
2527  // functionality has been subsumed by simple pattern matching here and in
2528  // InstSimplify. We should let a dedicated reassociation pass handle more
2529  // complex pattern matching and remove this from InstCombine.
2530  if (Value *V = FAddCombine(Builder).simplify(&I))
2531  return replaceInstUsesWith(I, V);
2532 
2533  // (X - Y) - Op1 --> X - (Y + Op1)
2534  if (match(Op0, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) {
2535  Value *FAdd = Builder.CreateFAddFMF(Y, Op1, &I);
2537  }
2538  }
2539 
2540  return nullptr;
2541 }
llvm::lltok::APFloat
@ APFloat
Definition: LLToken.h:438
set
We currently generate a but we really shouldn eax ecx xorl edx divl ecx eax divl ecx movl eax ret A similar code sequence works for division We currently compile i32 v2 eax eax jo LBB1_2 atomic and others It is also currently not done for read modify write instructions It is also current not done if the OF or CF flags are needed The shift operators have the complication that when the shift count is EFLAGS is not set
Definition: README.txt:1277
foldToUnsignedSaturatedAdd
static Instruction * foldToUnsignedSaturatedAdd(BinaryOperator &I)
Definition: InstCombineAddSub.cpp:1110
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
hoistFNegAboveFMulFDiv
static Instruction * hoistFNegAboveFMulFDiv(Instruction &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineAddSub.cpp:2307
llvm::InstCombinerImpl::visitFAdd
Instruction * visitFAdd(BinaryOperator &I)
Definition: InstCombineAddSub.cpp:1549
llvm::haveNoCommonBitsSet
bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if LHS and RHS have no common bits set.
Definition: ValueTracking.cpp:267
llvm::PatternMatch::m_TruncOrSelf
match_combine_or< CastClass_match< OpTy, Instruction::Trunc >, OpTy > m_TruncOrSelf(const OpTy &Op)
Definition: PatternMatch.h:1617
llvm::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1604
llvm::ConstantFoldUnaryOpOperand
Constant * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)
Attempt to constant fold a unary operation with the specified operand.
Definition: ConstantFolding.cpp:1332
llvm::MaskedValueIsZero
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if 'V & Mask' is known to be zero.
Definition: ValueTracking.cpp:391
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::ConstantExpr::getSIToFP
static Constant * getSIToFP(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2141
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
InstCombiner.h
llvm::RecurKind::FMul
@ FMul
Product of floats.
llvm::Intrinsic::getDeclaration
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1421
MatchDiv
static bool MatchDiv(Value *E, Value *&Op, APInt &C, bool IsSigned)
Definition: InstCombineAddSub.cpp:1024
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
simplify
hexagon bit simplify
Definition: HexagonBitSimplify.cpp:289
llvm::PatternMatch::m_NegatedPower2
cst_pred_ty< is_negated_power2 > m_NegatedPower2()
Match a integer or vector negated power-of-2.
Definition: PatternMatch.h:552
llvm::ConstantExpr::getZExt
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2092
T
llvm::APInt::isMask
bool isMask(unsigned numBits) const
Definition: APInt.h:469
llvm::Function
Definition: Function.h:60
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::BinaryOperator::CreateNot
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: Instructions.cpp:2902
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1117
llvm::APInt::isPowerOf2
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:425
llvm::KnownBits::Zero
APInt Zero
Definition: KnownBits.h:24
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
llvm::PatternMatch::m_FPOne
specific_fpval m_FPOne()
Match a float 1.0 or vector with all elements equal to 1.0.
Definition: PatternMatch.h:818
llvm::isGuaranteedNotToBeUndefOrPoison
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
Definition: ValueTracking.cpp:5428
llvm::Type::getScalarType
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:314
llvm::ConstantExpr::getSExt
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2078
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1181
llvm::BinaryOperator::CreateFDivFMF
static BinaryOperator * CreateFDivFMF(Value *V1, Value *V2, Instruction *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:272
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:979
llvm::Type::getFltSemantics
const fltSemantics & getFltSemantics() const
Definition: Type.cpp:67
llvm::IRBuilder< TargetFolder, IRBuilderCallbackInserter >
llvm::CastInst::Create
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
Definition: Instructions.cpp:3250
ValueTracking.h
llvm::PatternMatch::m_APFloat
apfloat_match m_APFloat(const APFloat *&Res)
Match a ConstantFP or splatted ConstantVector, binding the specified pointer to the contained APFloat...
Definition: PatternMatch.h:295
APInt.h
llvm::ConstantFP::isZero
bool isZero() const
Return true if the value is positive or negative zero.
Definition: Constants.h:302
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1411
llvm::ConstantExpr::getFPToSI
static Constant * getFPToSI(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2163
llvm::FastMathFlags::noSignedZeros
bool noSignedZeros() const
Definition: FMF.h:69
llvm::ConstantFP::getValueAPF
const APFloat & getValueAPF() const
Definition: Constants.h:298
llvm::simplifyFSubInst
Value * simplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q, fp::ExceptionBehavior ExBehavior=fp::ebIgnore, RoundingMode Rounding=RoundingMode::NearestTiesToEven)
Given operands for an FSub, fold the result or return null.
Definition: InstructionSimplify.cpp:5355
llvm::PatternMatch::m_BinOp
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:84
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::PatternMatch::m_AShr
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1123
llvm::ComputeNumSignBits
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits.
Definition: ValueTracking.cpp:415
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:62
Operator.h
llvm::Instruction::copyMetadata
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
Definition: Instruction.cpp:867
AlignOf.h
foldSubOfMinMax
static Instruction * foldSubOfMinMax(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineAddSub.cpp:1777
STLExtras.h
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::PatternMatch::m_c_And
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
Definition: PatternMatch.h:2251
llvm::BinaryOperator::CreateNeg
NUW NUW NUW NUW Exact static Exact BinaryOperator * CreateNeg(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Helper functions to construct and inspect unary operations (NEG and NOT) via binary operators SUB and...
Definition: Instructions.cpp:2862
llvm::UnaryOperator
Definition: InstrTypes.h:101
factorizeLerp
static Instruction * factorizeLerp(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Eliminate an op from a linear interpolation (lerp) pattern.
Definition: InstCombineAddSub.cpp:1488
llvm::PatternMatch::m_Not
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
Definition: PatternMatch.h:2289
llvm::FastMathFlags
Convenience struct for specifying and reasoning about fast-math flags.
Definition: FMF.h:21
llvm::isInt
constexpr bool isInt(int64_t x)
Checks if an integer fits into the given bit width.
Definition: MathExtras.h:345
llvm::InstCombinerImpl::foldAddWithConstant
Instruction * foldAddWithConstant(BinaryOperator &Add)
Definition: InstCombineAddSub.cpp:849
llvm::simplifyFAddInst
Value * simplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q, fp::ExceptionBehavior ExBehavior=fp::ebIgnore, RoundingMode Rounding=RoundingMode::NearestTiesToEven)
Given operands for an FAdd, fold the result or return null.
Definition: InstructionSimplify.cpp:5347
llvm::APFloat::getSemantics
const fltSemantics & getSemantics() const
Definition: APFloat.h:1223
llvm::AlignedCharArrayUnion
A suitably aligned and sized character array member which can hold elements of any type.
Definition: AlignOf.h:27
llvm::EmitGEPOffset
Value * EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, bool NoAssumptions=false)
Given a getelementptr instruction/constantexpr, emit the code necessary to compute the offset from th...
Definition: Local.h:29
llvm::PatternMatch::m_Deferred
deferredval_ty< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
Definition: PatternMatch.h:790
llvm::APIntOps::umin
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
Definition: APInt.h:2137
llvm::PatternMatch::m_FDiv
BinaryOp_match< LHS, RHS, Instruction::FDiv > m_FDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1069
llvm::PatternMatch::m_c_MaxOrMin
match_combine_or< match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty, true >, MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty, true > >, match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty, true >, MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty, true > > > m_c_MaxOrMin(const LHS &L, const RHS &R)
Definition: PatternMatch.h:2349
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:265
llvm::PatternMatch::m_FAdd
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:985
KnownBits.h
llvm::PatternMatch::m_FSub
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:997
factorizeFAddFSub
static Instruction * factorizeFAddFSub(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Factor a common operand out of fadd/fsub of fmul/fdiv.
Definition: InstCombineAddSub.cpp:1504
llvm::APInt::isSignMask
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
Definition: APInt.h:447
llvm::PatternMatch::m_OneUse
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
llvm::ConstantExpr::getSub
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2637
Instruction.h
llvm::PatternMatch::m_APInt
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:278
llvm::APInt::umul_ov
APInt umul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1969
llvm::PatternMatch::m_c_BinOp
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
Definition: PatternMatch.h:2215
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1768
InstCombineInternal.h
llvm::PatternMatch::m_Select
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
Definition: PatternMatch.h:1462
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
isZero
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:524
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::Instruction::setHasNoSignedWrap
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:153
llvm::ConstantFoldBinaryOpOperands
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
Definition: ConstantFolding.cpp:1339
llvm::User
Definition: User.h:44
llvm::PatternMatch::m_SpecificIntAllowUndef
specific_intval< true > m_SpecificIntAllowUndef(APInt V)
Definition: PatternMatch.h:862
llvm::RoundingMode
RoundingMode
Rounding mode.
Definition: FloatingPointMode.h:36
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
InstrTypes.h
int
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
Definition: README.txt:536
llvm::operator+=
std::string & operator+=(std::string &buffer, StringRef string)
Definition: StringRef.h:892
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1517
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::PatternMatch::m_Instruction
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:716
llvm::PatternMatch::m_ZExt
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:1629
llvm::PatternMatch::m_c_Add
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
Definition: PatternMatch.h:2237
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
checkForNegativeOperand
static Value * checkForNegativeOperand(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineAddSub.cpp:752
llvm::PatternMatch::m_FNeg
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
Definition: PatternMatch.h:1033
llvm::Constant::getAllOnesValue
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:395
llvm::PatternMatch::m_SDiv
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1063
llvm::Instruction
Definition: Instruction.h:42
llvm::Type::getScalarSizeInBits
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition: Type.cpp:189
llvm::PatternMatch::m_UMin
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1871
llvm::PatternMatch::m_c_Or
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
Definition: PatternMatch.h:2258
llvm::ConstantFP
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:257
llvm::APInt::getHighBitsSet
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
Definition: APInt.h:279
APFloat.h
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:879
llvm::PatternMatch::m_NSWSub
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1164
canonicalizeLowbitMask
static Instruction * canonicalizeLowbitMask(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Fold (1 << NBits) - 1 Into: ~(-(1 << NBits)) Because a 'not' is better for bit-tracking analysis and ...
Definition: InstCombineAddSub.cpp:1092
llvm::PatternMatch::m_URem
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1075
PatternMatch.h
llvm::APInt::countTrailingZeros
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1543
llvm::CastInst::CreateTruncOrBitCast
static CastInst * CreateTruncOrBitCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a Trunc or BitCast cast instruction.
Definition: Instructions.cpp:3326
llvm::Type::getIntegerBitWidth
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:97
llvm::InstCombiner::SubOne
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
Definition: InstCombiner.h:207
llvm::PatternMatch::m_c_UMax
MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty, true > m_c_UMax(const LHS &L, const RHS &R)
Matches a UMax with LHS and RHS in either order.
Definition: PatternMatch.h:2339
Type.h
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::PatternMatch::m_One
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:517
one
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only one
Definition: README.txt:401
llvm::PatternMatch::m_NSWAdd
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1156
llvm::APFloat::multiply
opStatus multiply(const APFloat &RHS, roundingMode RM)
Definition: APFloat.h:988
llvm::PatternMatch::m_Xor
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1105
llvm::InstCombinerImpl::visitFNeg
Instruction * visitFNeg(UnaryOperator &I)
Definition: InstCombineAddSub.cpp:2323
llvm::PatternMatch::m_FPTrunc
CastClass_match< OpTy, Instruction::FPTrunc > m_FPTrunc(const OpTy &Op)
Definition: PatternMatch.h:1682
llvm::PatternMatch::m_ZExtOrSelf
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, OpTy > m_ZExtOrSelf(const OpTy &Op)
Definition: PatternMatch.h:1635
llvm::APFloat
Definition: APFloat.h:701
llvm::PatternMatch::m_Zero
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:537
llvm::PatternMatch::m_NUWAdd
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1189
llvm::MipsISD::Ext
@ Ext
Definition: MipsISelLowering.h:159
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::InstCombinerImpl::visitAdd
Instruction * visitAdd(BinaryOperator &I)
Definition: InstCombineAddSub.cpp:1270
llvm::FastMathFlags::noInfs
bool noInfs() const
Definition: FMF.h:68
llvm::UnaryOperator::CreateFNegFMF
static UnaryOperator * CreateFNegFMF(Value *Op, Instruction *FMFSource, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: InstrTypes.h:164
llvm::InstCombiner::AddOne
static Constant * AddOne(Constant *C)
Add one to a Constant.
Definition: InstCombiner.h:202
llvm::BinaryOperator::CreateFMulFMF
static BinaryOperator * CreateFMulFMF(Value *V1, Value *V2, Instruction *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:267
llvm::InstCombinerImpl::canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract
Instruction * canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(BinaryOperator &I)
Definition: InstCombineAddSub.cpp:1133
llvm::GEPOperator::countNonConstantIndices
unsigned countNonConstantIndices() const
Definition: Operator.h:471
llvm::APInt::logBase2
unsigned logBase2() const
Definition: APInt.h:1652
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1099
llvm::PatternMatch::m_AllOnes
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:453
isConstant
static bool isConstant(const MachineInstr &MI)
Definition: AMDGPUInstructionSelector.cpp:2385
llvm::simplifySubInst
Value * simplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW, const SimplifyQuery &Q)
Given operands for a Sub, fold the result or return null.
Definition: InstructionSimplify.cpp:878
llvm::PatternMatch::m_ImmConstant
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:751
I
#define I(x, y, z)
Definition: MD5.cpp:58
size
i< reg-> size
Definition: README.txt:166
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1093
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:351
llvm::PatternMatch::m_SRem
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1081
llvm::InstCombinerImpl::SimplifyAddWithRemainder
Value * SimplifyAddWithRemainder(BinaryOperator &I)
Tries to simplify add operations using the definition of remainder.
Definition: InstCombineAddSub.cpp:1056
llvm::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Definition: ValueTracking.cpp:222
llvm::InstCombinerImpl::visitFSub
Instruction * visitFSub(BinaryOperator &I)
Definition: InstCombineAddSub.cpp:2376
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PatternMatch::m_Sub
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:991
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::simplifyAddInst
Value * simplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
Definition: InstructionSimplify.cpp:697
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1737
llvm::WinEH::EncodingType::CE
@ CE
Windows NT (Windows on ARM)
llvm::PatternMatch::m_Constant
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:144
llvm::GEPOperator
Definition: Operator.h:375
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::ZExtInst
This class represents zero extension of integer types.
Definition: Instructions.h:4850
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::PatternMatch::m_SExt
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:1623
llvm::PatternMatch::m_SpecificInt
specific_intval< false > m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:854
llvm::PatternMatch::m_CombineAnd
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:224
llvm::Instruction::getFastMathFlags
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
Definition: Instruction.cpp:315
llvm::BinaryOperator
Definition: InstrTypes.h:188
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
llvm::PatternMatch::m_SpecificInt_ICMP
cst_pred_ty< icmp_pred_with_threshold > m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold)
Match an integer or vector with every element comparing 'pred' (eg/ne/...) to Threshold.
Definition: PatternMatch.h:598
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::MinMax
Definition: AssumeBundleQueries.h:71
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
foldFNegIntoConstant
static Instruction * foldFNegIntoConstant(Instruction &I, const DataLayout &DL)
This eliminates floating-point negation in either 'fneg(X)' or 'fsub(-0.0, X)' form by combining into...
Definition: InstCombineAddSub.cpp:2264
foldNoWrapAdd
static Instruction * foldNoWrapAdd(BinaryOperator &Add, InstCombiner::BuilderTy &Builder)
Wrapping flags may allow combining constants separated by an extend.
Definition: InstCombineAddSub.cpp:809
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
MatchMul
static bool MatchMul(Value *E, Value *&Op, APInt &C)
Definition: InstCombineAddSub.cpp:984
factorizeMathWithShlOps
static Instruction * factorizeMathWithShlOps(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
This is a specialization of a more general transform from SimplifyUsingDistributiveLaws.
Definition: InstCombineAddSub.cpp:1236
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::InstCombinerImpl::OptimizePointerDifference
Value * OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty, bool isNUW)
Optimize pointer differences into the same array into a size.
Definition: InstCombineAddSub.cpp:1701
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:685
llvm::simplifyFNegInst
Value * simplifyFNegInst(Value *Op, FastMathFlags FMF, const SimplifyQuery &Q)
Given operand for an FNeg, fold the result or return null.
Definition: InstructionSimplify.cpp:5123
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:164
llvm::PatternMatch::m_FPExt
CastClass_match< OpTy, Instruction::FPExt > m_FPExt(const OpTy &Op)
Definition: PatternMatch.h:1687
llvm::tgtok::IntVal
@ IntVal
Definition: TGLexer.h:65
llvm::APIntOps::umax
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
Definition: APInt.h:2142
llvm::Instruction::setFastMathFlags
void setFastMathFlags(FastMathFlags FMF)
Convenience function for setting multiple fast-math flags on this instruction, which must be an opera...
Definition: Instruction.cpp:265
Constant.h
llvm::PatternMatch::m_SExtOrSelf
match_combine_or< CastClass_match< OpTy, Instruction::SExt >, OpTy > m_SExtOrSelf(const OpTy &Op)
Definition: PatternMatch.h:1641
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:350
llvm::KnownBits
Definition: KnownBits.h:23
llvm::PatternMatch::m_UDiv
BinaryOp_match< LHS, RHS, Instruction::UDiv > m_UDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1057
llvm::APInt::isMinSignedValue
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:408
llvm::BinaryOperator::CreateFAddFMF
static BinaryOperator * CreateFAddFMF(Value *V1, Value *V2, Instruction *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:257
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::Negator::Negate
static Value * Negate(bool LHSIsZero, Value *Root, InstCombinerImpl &IC)
Attempt to negate Root.
Definition: InstCombineNegator.cpp:530
llvm::GEPOperator::isInBounds
bool isInBounds() const
Test whether this is an inbounds GEP, as defined by LangRef.html.
Definition: Operator.h:392
llvm::ConstantExpr::getAdd
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2630
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:202
llvm::ConstantFP::get
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:926
Casting.h
llvm::fltSemantics
Definition: APFloat.cpp:54
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::APInt::smul_ov
APInt smul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1958
MulWillOverflow
static bool MulWillOverflow(APInt &C0, APInt &C1, bool IsSigned)
Definition: InstCombineAddSub.cpp:1045
llvm::ARCCC::Z
@ Z
Definition: ARCInfo.h:41
llvm::PatternMatch::m_ZeroInt
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
Definition: PatternMatch.h:524
llvm::getInverseMinMaxIntrinsic
Intrinsic::ID getInverseMinMaxIntrinsic(Intrinsic::ID MinMaxID)
Definition: ValueTracking.cpp:6461
llvm::PatternMatch::m_PtrToInt
CastClass_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
Definition: PatternMatch.h:1599
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::InstCombinerImpl::visitSub
Instruction * visitSub(BinaryOperator &I)
Definition: InstCombineAddSub.cpp:1823
llvm::PatternMatch::m_c_Xor
BinaryOp_match< LHS, RHS, Instruction::Xor, true > m_c_Xor(const LHS &L, const RHS &R)
Matches an Xor with LHS and RHS in either order.
Definition: PatternMatch.h:2265
llvm::APInt::sext
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:946
llvm::PatternMatch::m_AnyZeroFP
cstfp_pred_ty< is_any_zero_fp > m_AnyZeroFP()
Match a floating-point negative zero or positive zero.
Definition: PatternMatch.h:664
llvm::CannotBeNegativeZero
bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI, unsigned Depth=0)
Return true if we can prove that the specified FP value is never equal to -0.0.
Definition: ValueTracking.cpp:3534
llvm::APFloatBase::rmNearestTiesToEven
static constexpr roundingMode rmNearestTiesToEven
Definition: APFloat.h:190
llvm::RecurKind::FAdd
@ FAdd
Sum of floats.
llvm::PatternMatch::m_c_FMul
BinaryOp_match< LHS, RHS, Instruction::FMul, true > m_c_FMul(const LHS &L, const RHS &R)
Matches FMul with LHS and RHS in either order.
Definition: PatternMatch.h:2364
Instructions.h
llvm::PatternMatch::m_c_FAdd
BinaryOp_match< LHS, RHS, Instruction::FAdd, true > m_c_FAdd(const LHS &L, const RHS &R)
Matches FAdd with LHS and RHS in either order.
Definition: PatternMatch.h:2357
llvm::Instruction::setHasNoInfs
void setHasNoInfs(bool B)
Set or clear the no-infs flag on this instruction, which must be an operator which supports this flag...
Definition: Instruction.cpp:240
SmallVector.h
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:772
llvm::Instruction::setHasNoSignedZeros
void setHasNoSignedZeros(bool B)
Set or clear the no-signed-zeros flag on this instruction, which must be an operator which supports t...
Definition: Instruction.cpp:245
llvm::SIToFPInst
This class represents a cast from signed integer to floating point.
Definition: Instructions.h:5045
llvm::PatternMatch::m_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1394
MatchRem
static bool MatchRem(Value *E, Value *&Op, APInt &C, bool &IsSigned)
Definition: InstCombineAddSub.cpp:1002
InstructionSimplify.h
llvm::APFloatBase::semanticsPrecision
static unsigned int semanticsPrecision(const fltSemantics &)
Definition: APFloat.cpp:211
llvm::PHINode
Definition: Instructions.h:2699
llvm::PatternMatch::m_Neg
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
Definition: PatternMatch.h:2273
CreateAdd
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:241
llvm::PatternMatch::m_Trunc
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:1611
llvm::PatternMatch::m_FMul
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1051
llvm::tgtok::TrueVal
@ TrueVal
Definition: TGLexer.h:62
Value.h
llvm::RoundingMode::NearestTiesToEven
@ NearestTiesToEven
roundTiesToEven.
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::PatternMatch::m_Shl
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1111
llvm::BinaryOperator::CreateFSubFMF
static BinaryOperator * CreateFSubFMF(Value *V1, Value *V2, Instruction *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:262
llvm::PatternMatch::m_c_UMin
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty, true > m_c_UMin(const LHS &L, const RHS &R)
Matches a UMin with LHS and RHS in either order.
Definition: PatternMatch.h:2333
llvm::PatternMatch::m_Mul
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1045
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38