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 /// foldUsingDistributiveLaws. 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 
1270 /// Reduce a sequence of masked half-width multiplies to a single multiply.
1271 /// ((XLow * YHigh) + (YLow * XHigh)) << HalfBits) + (XLow * YLow) --> X * Y
1273  unsigned BitWidth = I.getType()->getScalarSizeInBits();
1274  // Skip the odd bitwidth types.
1275  if ((BitWidth & 0x1))
1276  return nullptr;
1277 
1278  unsigned HalfBits = BitWidth >> 1;
1279  APInt HalfMask = APInt::getMaxValue(HalfBits);
1280 
1281  // ResLo = (CrossSum << HalfBits) + (YLo * XLo)
1282  Value *XLo, *YLo;
1283  Value *CrossSum;
1284  if (!match(&I, m_c_Add(m_Shl(m_Value(CrossSum), m_SpecificInt(HalfBits)),
1285  m_Mul(m_Value(YLo), m_Value(XLo)))))
1286  return nullptr;
1287 
1288  // XLo = X & HalfMask
1289  // YLo = Y & HalfMask
1290  // TODO: Refactor with SimplifyDemandedBits or KnownBits known leading zeros
1291  // to enhance robustness
1292  Value *X, *Y;
1293  if (!match(XLo, m_And(m_Value(X), m_SpecificInt(HalfMask))) ||
1294  !match(YLo, m_And(m_Value(Y), m_SpecificInt(HalfMask))))
1295  return nullptr;
1296 
1297  // CrossSum = (X' * (Y >> Halfbits)) + (Y' * (X >> HalfBits))
1298  // X' can be either X or XLo in the pattern (and the same for Y')
1299  if (match(CrossSum,
1302  m_c_Mul(m_LShr(m_Specific(X), m_SpecificInt(HalfBits)),
1303  m_CombineOr(m_Specific(Y), m_Specific(YLo))))))
1304  return BinaryOperator::CreateMul(X, Y);
1305 
1306  return nullptr;
1307 }
1308 
1310  if (Value *V = simplifyAddInst(I.getOperand(0), I.getOperand(1),
1311  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
1312  SQ.getWithInstruction(&I)))
1313  return replaceInstUsesWith(I, V);
1314 
1315  if (SimplifyAssociativeOrCommutative(I))
1316  return &I;
1317 
1318  if (Instruction *X = foldVectorBinop(I))
1319  return X;
1320 
1321  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1322  return Phi;
1323 
1324  // (A*B)+(A*C) -> A*(B+C) etc
1325  if (Value *V = foldUsingDistributiveLaws(I))
1326  return replaceInstUsesWith(I, V);
1327 
1328  if (Instruction *R = foldBoxMultiply(I))
1329  return R;
1330 
1332  return R;
1333 
1334  if (Instruction *X = foldAddWithConstant(I))
1335  return X;
1336 
1337  if (Instruction *X = foldNoWrapAdd(I, Builder))
1338  return X;
1339 
1340  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1341  Type *Ty = I.getType();
1342  if (Ty->isIntOrIntVectorTy(1))
1343  return BinaryOperator::CreateXor(LHS, RHS);
1344 
1345  // X + X --> X << 1
1346  if (LHS == RHS) {
1347  auto *Shl = BinaryOperator::CreateShl(LHS, ConstantInt::get(Ty, 1));
1348  Shl->setHasNoSignedWrap(I.hasNoSignedWrap());
1349  Shl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1350  return Shl;
1351  }
1352 
1353  Value *A, *B;
1354  if (match(LHS, m_Neg(m_Value(A)))) {
1355  // -A + -B --> -(A + B)
1356  if (match(RHS, m_Neg(m_Value(B))))
1357  return BinaryOperator::CreateNeg(Builder.CreateAdd(A, B));
1358 
1359  // -A + B --> B - A
1360  return BinaryOperator::CreateSub(RHS, A);
1361  }
1362 
1363  // A + -B --> A - B
1364  if (match(RHS, m_Neg(m_Value(B))))
1365  return BinaryOperator::CreateSub(LHS, B);
1366 
1368  return replaceInstUsesWith(I, V);
1369 
1370  // (A + 1) + ~B --> A - B
1371  // ~B + (A + 1) --> A - B
1372  // (~B + A) + 1 --> A - B
1373  // (A + ~B) + 1 --> A - B
1374  if (match(&I, m_c_BinOp(m_Add(m_Value(A), m_One()), m_Not(m_Value(B)))) ||
1375  match(&I, m_BinOp(m_c_Add(m_Not(m_Value(B)), m_Value(A)), m_One())))
1376  return BinaryOperator::CreateSub(A, B);
1377 
1378  // (A + RHS) + RHS --> A + (RHS << 1)
1380  return BinaryOperator::CreateAdd(A, Builder.CreateShl(RHS, 1, "reass.add"));
1381 
1382  // LHS + (A + LHS) --> A + (LHS << 1)
1384  return BinaryOperator::CreateAdd(A, Builder.CreateShl(LHS, 1, "reass.add"));
1385 
1386  {
1387  // (A + C1) + (C2 - B) --> (A - B) + (C1 + C2)
1388  Constant *C1, *C2;
1389  if (match(&I, m_c_Add(m_Add(m_Value(A), m_ImmConstant(C1)),
1390  m_Sub(m_ImmConstant(C2), m_Value(B)))) &&
1391  (LHS->hasOneUse() || RHS->hasOneUse())) {
1392  Value *Sub = Builder.CreateSub(A, B);
1394  }
1395  }
1396 
1397  // X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1)
1398  if (Value *V = SimplifyAddWithRemainder(I)) return replaceInstUsesWith(I, V);
1399 
1400  // ((X s/ C1) << C2) + X => X s% -C1 where -C1 is 1 << C2
1401  const APInt *C1, *C2;
1402  if (match(LHS, m_Shl(m_SDiv(m_Specific(RHS), m_APInt(C1)), m_APInt(C2)))) {
1403  APInt one(C2->getBitWidth(), 1);
1404  APInt minusC1 = -(*C1);
1405  if (minusC1 == (one << *C2)) {
1406  Constant *NewRHS = ConstantInt::get(RHS->getType(), minusC1);
1407  return BinaryOperator::CreateSRem(RHS, NewRHS);
1408  }
1409  }
1410 
1411  // (A & 2^C1) + A => A & (2^C1 - 1) iff bit C1 in A is a sign bit
1412  if (match(&I, m_c_Add(m_And(m_Value(A), m_APInt(C1)), m_Deferred(A))) &&
1413  C1->isPowerOf2() && (ComputeNumSignBits(A) > C1->countLeadingZeros())) {
1414  Constant *NewMask = ConstantInt::get(RHS->getType(), *C1 - 1);
1415  return BinaryOperator::CreateAnd(A, NewMask);
1416  }
1417 
1418  // A+B --> A|B iff A and B have no bits set in common.
1419  if (haveNoCommonBitsSet(LHS, RHS, DL, &AC, &I, &DT))
1420  return BinaryOperator::CreateOr(LHS, RHS);
1421 
1422  if (Instruction *Ext = narrowMathIfNoOverflow(I))
1423  return Ext;
1424 
1425  // (add (xor A, B) (and A, B)) --> (or A, B)
1426  // (add (and A, B) (xor A, B)) --> (or A, B)
1427  if (match(&I, m_c_BinOp(m_Xor(m_Value(A), m_Value(B)),
1428  m_c_And(m_Deferred(A), m_Deferred(B)))))
1429  return BinaryOperator::CreateOr(A, B);
1430 
1431  // (add (or A, B) (and A, B)) --> (add A, B)
1432  // (add (and A, B) (or A, B)) --> (add A, B)
1433  if (match(&I, m_c_BinOp(m_Or(m_Value(A), m_Value(B)),
1434  m_c_And(m_Deferred(A), m_Deferred(B))))) {
1435  // Replacing operands in-place to preserve nuw/nsw flags.
1436  replaceOperand(I, 0, A);
1437  replaceOperand(I, 1, B);
1438  return &I;
1439  }
1440 
1441  // (add A (or A, -A)) --> (and (add A, -1) A)
1442  // (add A (or -A, A)) --> (and (add A, -1) A)
1443  // (add (or A, -A) A) --> (and (add A, -1) A)
1444  // (add (or -A, A) A) --> (and (add A, -1) A)
1446  m_Deferred(A)))))) {
1447  Value *Add =
1448  Builder.CreateAdd(A, Constant::getAllOnesValue(A->getType()), "",
1449  I.hasNoUnsignedWrap(), I.hasNoSignedWrap());
1450  return BinaryOperator::CreateAnd(Add, A);
1451  }
1452 
1453  // Canonicalize ((A & -A) - 1) --> ((A - 1) & ~A)
1454  // Forms all commutable operations, and simplifies ctpop -> cttz folds.
1455  if (match(&I,
1457  m_AllOnes()))) {
1459  Value *Dec = Builder.CreateAdd(A, AllOnes);
1460  Value *Not = Builder.CreateXor(A, AllOnes);
1461  return BinaryOperator::CreateAnd(Dec, Not);
1462  }
1463 
1464  // Disguised reassociation/factorization:
1465  // ~(A * C1) + A
1466  // ((A * -C1) - 1) + A
1467  // ((A * -C1) + A) - 1
1468  // (A * (1 - C1)) - 1
1469  if (match(&I,
1471  m_Deferred(A)))) {
1472  Type *Ty = I.getType();
1473  Constant *NewMulC = ConstantInt::get(Ty, 1 - *C1);
1474  Value *NewMul = Builder.CreateMul(A, NewMulC);
1476  }
1477 
1478  // (A * -2**C) + B --> B - (A << C)
1479  const APInt *NegPow2C;
1480  if (match(&I, m_c_Add(m_OneUse(m_Mul(m_Value(A), m_NegatedPower2(NegPow2C))),
1481  m_Value(B)))) {
1482  Constant *ShiftAmtC = ConstantInt::get(Ty, NegPow2C->countTrailingZeros());
1483  Value *Shl = Builder.CreateShl(A, ShiftAmtC);
1484  return BinaryOperator::CreateSub(B, Shl);
1485  }
1486 
1487  // TODO(jingyue): Consider willNotOverflowSignedAdd and
1488  // willNotOverflowUnsignedAdd to reduce the number of invocations of
1489  // computeKnownBits.
1490  bool Changed = false;
1491  if (!I.hasNoSignedWrap() && willNotOverflowSignedAdd(LHS, RHS, I)) {
1492  Changed = true;
1493  I.setHasNoSignedWrap(true);
1494  }
1495  if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedAdd(LHS, RHS, I)) {
1496  Changed = true;
1497  I.setHasNoUnsignedWrap(true);
1498  }
1499 
1501  return V;
1502 
1503  if (Instruction *V =
1504  canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
1505  return V;
1506 
1507  if (Instruction *SatAdd = foldToUnsignedSaturatedAdd(I))
1508  return SatAdd;
1509 
1510  // usub.sat(A, B) + B => umax(A, B)
1511  if (match(&I, m_c_BinOp(
1512  m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Value(A), m_Value(B))),
1513  m_Deferred(B)))) {
1514  return replaceInstUsesWith(I,
1515  Builder.CreateIntrinsic(Intrinsic::umax, {I.getType()}, {A, B}));
1516  }
1517 
1518  // ctpop(A) + ctpop(B) => ctpop(A | B) if A and B have no bits set in common.
1519  if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(A)))) &&
1520  match(RHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(B)))) &&
1521  haveNoCommonBitsSet(A, B, DL, &AC, &I, &DT))
1522  return replaceInstUsesWith(
1523  I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
1524  {Builder.CreateOr(A, B)}));
1525 
1526  return Changed ? &I : nullptr;
1527 }
1528 
1529 /// Eliminate an op from a linear interpolation (lerp) pattern.
1532  Value *X, *Y, *Z;
1535  m_Value(Z))))),
1537  return nullptr;
1538 
1539  // (Y * (1.0 - Z)) + (X * Z) --> Y + Z * (X - Y) [8 commuted variants]
1540  Value *XY = Builder.CreateFSubFMF(X, Y, &I);
1541  Value *MulZ = Builder.CreateFMulFMF(Z, XY, &I);
1542  return BinaryOperator::CreateFAddFMF(Y, MulZ, &I);
1543 }
1544 
1545 /// Factor a common operand out of fadd/fsub of fmul/fdiv.
1548  assert((I.getOpcode() == Instruction::FAdd ||
1549  I.getOpcode() == Instruction::FSub) && "Expecting fadd/fsub");
1550  assert(I.hasAllowReassoc() && I.hasNoSignedZeros() &&
1551  "FP factorization requires FMF");
1552 
1553  if (Instruction *Lerp = factorizeLerp(I, Builder))
1554  return Lerp;
1555 
1556  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1557  if (!Op0->hasOneUse() || !Op1->hasOneUse())
1558  return nullptr;
1559 
1560  Value *X, *Y, *Z;
1561  bool IsFMul;
1562  if ((match(Op0, m_FMul(m_Value(X), m_Value(Z))) &&
1563  match(Op1, m_c_FMul(m_Value(Y), m_Specific(Z)))) ||
1564  (match(Op0, m_FMul(m_Value(Z), m_Value(X))) &&
1565  match(Op1, m_c_FMul(m_Value(Y), m_Specific(Z)))))
1566  IsFMul = true;
1567  else if (match(Op0, m_FDiv(m_Value(X), m_Value(Z))) &&
1568  match(Op1, m_FDiv(m_Value(Y), m_Specific(Z))))
1569  IsFMul = false;
1570  else
1571  return nullptr;
1572 
1573  // (X * Z) + (Y * Z) --> (X + Y) * Z
1574  // (X * Z) - (Y * Z) --> (X - Y) * Z
1575  // (X / Z) + (Y / Z) --> (X + Y) / Z
1576  // (X / Z) - (Y / Z) --> (X - Y) / Z
1577  bool IsFAdd = I.getOpcode() == Instruction::FAdd;
1578  Value *XY = IsFAdd ? Builder.CreateFAddFMF(X, Y, &I)
1579  : Builder.CreateFSubFMF(X, Y, &I);
1580 
1581  // Bail out if we just created a denormal constant.
1582  // TODO: This is copied from a previous implementation. Is it necessary?
1583  const APFloat *C;
1584  if (match(XY, m_APFloat(C)) && !C->isNormal())
1585  return nullptr;
1586 
1587  return IsFMul ? BinaryOperator::CreateFMulFMF(XY, Z, &I)
1589 }
1590 
1592  if (Value *V = simplifyFAddInst(I.getOperand(0), I.getOperand(1),
1593  I.getFastMathFlags(),
1594  SQ.getWithInstruction(&I)))
1595  return replaceInstUsesWith(I, V);
1596 
1597  if (SimplifyAssociativeOrCommutative(I))
1598  return &I;
1599 
1600  if (Instruction *X = foldVectorBinop(I))
1601  return X;
1602 
1603  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1604  return Phi;
1605 
1606  if (Instruction *FoldedFAdd = foldBinOpIntoSelectOrPhi(I))
1607  return FoldedFAdd;
1608 
1609  // (-X) + Y --> Y - X
1610  Value *X, *Y;
1611  if (match(&I, m_c_FAdd(m_FNeg(m_Value(X)), m_Value(Y))))
1612  return BinaryOperator::CreateFSubFMF(Y, X, &I);
1613 
1614  // Similar to above, but look through fmul/fdiv for the negated term.
1615  // (-X * Y) + Z --> Z - (X * Y) [4 commuted variants]
1616  Value *Z;
1618  m_Value(Z)))) {
1619  Value *XY = Builder.CreateFMulFMF(X, Y, &I);
1620  return BinaryOperator::CreateFSubFMF(Z, XY, &I);
1621  }
1622  // (-X / Y) + Z --> Z - (X / Y) [2 commuted variants]
1623  // (X / -Y) + Z --> Z - (X / Y) [2 commuted variants]
1625  m_Value(Z))) ||
1627  m_Value(Z)))) {
1628  Value *XY = Builder.CreateFDivFMF(X, Y, &I);
1629  return BinaryOperator::CreateFSubFMF(Z, XY, &I);
1630  }
1631 
1632  // Check for (fadd double (sitofp x), y), see if we can merge this into an
1633  // integer add followed by a promotion.
1634  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1635  if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) {
1636  Value *LHSIntVal = LHSConv->getOperand(0);
1637  Type *FPType = LHSConv->getType();
1638 
1639  // TODO: This check is overly conservative. In many cases known bits
1640  // analysis can tell us that the result of the addition has less significant
1641  // bits than the integer type can hold.
1642  auto IsValidPromotion = [](Type *FTy, Type *ITy) {
1643  Type *FScalarTy = FTy->getScalarType();
1644  Type *IScalarTy = ITy->getScalarType();
1645 
1646  // Do we have enough bits in the significand to represent the result of
1647  // the integer addition?
1648  unsigned MaxRepresentableBits =
1650  return IScalarTy->getIntegerBitWidth() <= MaxRepresentableBits;
1651  };
1652 
1653  // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst))
1654  // ... if the constant fits in the integer value. This is useful for things
1655  // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer
1656  // requires a constant pool load, and generally allows the add to be better
1657  // instcombined.
1658  if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS))
1659  if (IsValidPromotion(FPType, LHSIntVal->getType())) {
1660  Constant *CI =
1661  ConstantExpr::getFPToSI(CFP, LHSIntVal->getType());
1662  if (LHSConv->hasOneUse() &&
1663  ConstantExpr::getSIToFP(CI, I.getType()) == CFP &&
1664  willNotOverflowSignedAdd(LHSIntVal, CI, I)) {
1665  // Insert the new integer add.
1666  Value *NewAdd = Builder.CreateNSWAdd(LHSIntVal, CI, "addconv");
1667  return new SIToFPInst(NewAdd, I.getType());
1668  }
1669  }
1670 
1671  // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y))
1672  if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) {
1673  Value *RHSIntVal = RHSConv->getOperand(0);
1674  // It's enough to check LHS types only because we require int types to
1675  // be the same for this transform.
1676  if (IsValidPromotion(FPType, LHSIntVal->getType())) {
1677  // Only do this if x/y have the same type, if at least one of them has a
1678  // single use (so we don't increase the number of int->fp conversions),
1679  // and if the integer add will not overflow.
1680  if (LHSIntVal->getType() == RHSIntVal->getType() &&
1681  (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
1682  willNotOverflowSignedAdd(LHSIntVal, RHSIntVal, I)) {
1683  // Insert the new integer add.
1684  Value *NewAdd = Builder.CreateNSWAdd(LHSIntVal, RHSIntVal, "addconv");
1685  return new SIToFPInst(NewAdd, I.getType());
1686  }
1687  }
1688  }
1689  }
1690 
1691  // Handle specials cases for FAdd with selects feeding the operation
1692  if (Value *V = SimplifySelectsFeedingBinaryOp(I, LHS, RHS))
1693  return replaceInstUsesWith(I, V);
1694 
1695  if (I.hasAllowReassoc() && I.hasNoSignedZeros()) {
1697  return F;
1698 
1699  // Try to fold fadd into start value of reduction intrinsic.
1700  if (match(&I, m_c_FAdd(m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(
1701  m_AnyZeroFP(), m_Value(X))),
1702  m_Value(Y)))) {
1703  // fadd (rdx 0.0, X), Y --> rdx Y, X
1704  return replaceInstUsesWith(
1705  I, Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,
1706  {X->getType()}, {Y, X}, &I));
1707  }
1708  const APFloat *StartC, *C;
1709  if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(
1710  m_APFloat(StartC), m_Value(X)))) &&
1711  match(RHS, m_APFloat(C))) {
1712  // fadd (rdx StartC, X), C --> rdx (C + StartC), X
1713  Constant *NewStartC = ConstantFP::get(I.getType(), *C + *StartC);
1714  return replaceInstUsesWith(
1715  I, Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,
1716  {X->getType()}, {NewStartC, X}, &I));
1717  }
1718 
1719  // (X * MulC) + X --> X * (MulC + 1.0)
1720  Constant *MulC;
1721  if (match(&I, m_c_FAdd(m_FMul(m_Value(X), m_ImmConstant(MulC)),
1722  m_Deferred(X)))) {
1723  if (Constant *NewMulC = ConstantFoldBinaryOpOperands(
1724  Instruction::FAdd, MulC, ConstantFP::get(I.getType(), 1.0), DL))
1725  return BinaryOperator::CreateFMulFMF(X, NewMulC, &I);
1726  }
1727 
1728  // (-X - Y) + (X + Z) --> Z - Y
1729  if (match(&I, m_c_FAdd(m_FSub(m_FNeg(m_Value(X)), m_Value(Y)),
1730  m_c_FAdd(m_Deferred(X), m_Value(Z)))))
1731  return BinaryOperator::CreateFSubFMF(Z, Y, &I);
1732 
1733  if (Value *V = FAddCombine(Builder).simplify(&I))
1734  return replaceInstUsesWith(I, V);
1735  }
1736 
1737  return nullptr;
1738 }
1739 
1740 /// Optimize pointer differences into the same array into a size. Consider:
1741 /// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer
1742 /// operands to the ptrtoint instructions for the LHS/RHS of the subtract.
1744  Type *Ty, bool IsNUW) {
1745  // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize
1746  // this.
1747  bool Swapped = false;
1748  GEPOperator *GEP1 = nullptr, *GEP2 = nullptr;
1749  if (!isa<GEPOperator>(LHS) && isa<GEPOperator>(RHS)) {
1750  std::swap(LHS, RHS);
1751  Swapped = true;
1752  }
1753 
1754  // Require at least one GEP with a common base pointer on both sides.
1755  if (auto *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
1756  // (gep X, ...) - X
1757  if (LHSGEP->getOperand(0)->stripPointerCasts() ==
1758  RHS->stripPointerCasts()) {
1759  GEP1 = LHSGEP;
1760  } else if (auto *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
1761  // (gep X, ...) - (gep X, ...)
1762  if (LHSGEP->getOperand(0)->stripPointerCasts() ==
1763  RHSGEP->getOperand(0)->stripPointerCasts()) {
1764  GEP1 = LHSGEP;
1765  GEP2 = RHSGEP;
1766  }
1767  }
1768  }
1769 
1770  if (!GEP1)
1771  return nullptr;
1772 
1773  if (GEP2) {
1774  // (gep X, ...) - (gep X, ...)
1775  //
1776  // Avoid duplicating the arithmetic if there are more than one non-constant
1777  // indices between the two GEPs and either GEP has a non-constant index and
1778  // multiple users. If zero non-constant index, the result is a constant and
1779  // there is no duplication. If one non-constant index, the result is an add
1780  // or sub with a constant, which is no larger than the original code, and
1781  // there's no duplicated arithmetic, even if either GEP has multiple
1782  // users. If more than one non-constant indices combined, as long as the GEP
1783  // with at least one non-constant index doesn't have multiple users, there
1784  // is no duplication.
1785  unsigned NumNonConstantIndices1 = GEP1->countNonConstantIndices();
1786  unsigned NumNonConstantIndices2 = GEP2->countNonConstantIndices();
1787  if (NumNonConstantIndices1 + NumNonConstantIndices2 > 1 &&
1788  ((NumNonConstantIndices1 > 0 && !GEP1->hasOneUse()) ||
1789  (NumNonConstantIndices2 > 0 && !GEP2->hasOneUse()))) {
1790  return nullptr;
1791  }
1792  }
1793 
1794  // Emit the offset of the GEP and an intptr_t.
1795  Value *Result = EmitGEPOffset(GEP1);
1796 
1797  // If this is a single inbounds GEP and the original sub was nuw,
1798  // then the final multiplication is also nuw.
1799  if (auto *I = dyn_cast<Instruction>(Result))
1800  if (IsNUW && !GEP2 && !Swapped && GEP1->isInBounds() &&
1801  I->getOpcode() == Instruction::Mul)
1802  I->setHasNoUnsignedWrap();
1803 
1804  // If we have a 2nd GEP of the same base pointer, subtract the offsets.
1805  // If both GEPs are inbounds, then the subtract does not have signed overflow.
1806  if (GEP2) {
1807  Value *Offset = EmitGEPOffset(GEP2);
1808  Result = Builder.CreateSub(Result, Offset, "gepdiff", /* NUW */ false,
1809  GEP1->isInBounds() && GEP2->isInBounds());
1810  }
1811 
1812  // If we have p - gep(p, ...) then we have to negate the result.
1813  if (Swapped)
1814  Result = Builder.CreateNeg(Result, "diff.neg");
1815 
1816  return Builder.CreateIntCast(Result, Ty, true);
1817 }
1818 
1821  Value *Op0 = I.getOperand(0);
1822  Value *Op1 = I.getOperand(1);
1823  Type *Ty = I.getType();
1824  auto *MinMax = dyn_cast<MinMaxIntrinsic>(Op1);
1825  if (!MinMax)
1826  return nullptr;
1827 
1828  // sub(add(X,Y), s/umin(X,Y)) --> s/umax(X,Y)
1829  // sub(add(X,Y), s/umax(X,Y)) --> s/umin(X,Y)
1830  Value *X = MinMax->getLHS();
1831  Value *Y = MinMax->getRHS();
1832  if (match(Op0, m_c_Add(m_Specific(X), m_Specific(Y))) &&
1833  (Op0->hasOneUse() || Op1->hasOneUse())) {
1834  Intrinsic::ID InvID = getInverseMinMaxIntrinsic(MinMax->getIntrinsicID());
1835  Function *F = Intrinsic::getDeclaration(I.getModule(), InvID, Ty);
1836  return CallInst::Create(F, {X, Y});
1837  }
1838 
1839  // sub(add(X,Y),umin(Y,Z)) --> add(X,usub.sat(Y,Z))
1840  // sub(add(X,Z),umin(Y,Z)) --> add(X,usub.sat(Z,Y))
1841  Value *Z;
1842  if (match(Op1, m_OneUse(m_UMin(m_Value(Y), m_Value(Z))))) {
1843  if (match(Op0, m_OneUse(m_c_Add(m_Specific(Y), m_Value(X))))) {
1844  Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, Ty, {Y, Z});
1845  return BinaryOperator::CreateAdd(X, USub);
1846  }
1847  if (match(Op0, m_OneUse(m_c_Add(m_Specific(Z), m_Value(X))))) {
1848  Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, Ty, {Z, Y});
1849  return BinaryOperator::CreateAdd(X, USub);
1850  }
1851  }
1852 
1853  // sub Op0, smin((sub nsw Op0, Z), 0) --> smax Op0, Z
1854  // sub Op0, smax((sub nsw Op0, Z), 0) --> smin Op0, Z
1855  if (MinMax->isSigned() && match(Y, m_ZeroInt()) &&
1856  match(X, m_NSWSub(m_Specific(Op0), m_Value(Z)))) {
1857  Intrinsic::ID InvID = getInverseMinMaxIntrinsic(MinMax->getIntrinsicID());
1858  Function *F = Intrinsic::getDeclaration(I.getModule(), InvID, Ty);
1859  return CallInst::Create(F, {Op0, Z});
1860  }
1861 
1862  return nullptr;
1863 }
1864 
1866  if (Value *V = simplifySubInst(I.getOperand(0), I.getOperand(1),
1867  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
1868  SQ.getWithInstruction(&I)))
1869  return replaceInstUsesWith(I, V);
1870 
1871  if (Instruction *X = foldVectorBinop(I))
1872  return X;
1873 
1874  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1875  return Phi;
1876 
1877  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1878 
1879  // If this is a 'B = x-(-A)', change to B = x+A.
1880  // We deal with this without involving Negator to preserve NSW flag.
1881  if (Value *V = dyn_castNegVal(Op1)) {
1883 
1884  if (const auto *BO = dyn_cast<BinaryOperator>(Op1)) {
1885  assert(BO->getOpcode() == Instruction::Sub &&
1886  "Expected a subtraction operator!");
1887  if (BO->hasNoSignedWrap() && I.hasNoSignedWrap())
1888  Res->setHasNoSignedWrap(true);
1889  } else {
1890  if (cast<Constant>(Op1)->isNotMinSignedValue() && I.hasNoSignedWrap())
1891  Res->setHasNoSignedWrap(true);
1892  }
1893 
1894  return Res;
1895  }
1896 
1897  // Try this before Negator to preserve NSW flag.
1899  return R;
1900 
1901  Constant *C;
1902  if (match(Op0, m_ImmConstant(C))) {
1903  Value *X;
1904  Constant *C2;
1905 
1906  // C-(X+C2) --> (C-C2)-X
1907  if (match(Op1, m_Add(m_Value(X), m_ImmConstant(C2))))
1908  return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
1909  }
1910 
1911  auto TryToNarrowDeduceFlags = [this, &I, &Op0, &Op1]() -> Instruction * {
1912  if (Instruction *Ext = narrowMathIfNoOverflow(I))
1913  return Ext;
1914 
1915  bool Changed = false;
1916  if (!I.hasNoSignedWrap() && willNotOverflowSignedSub(Op0, Op1, I)) {
1917  Changed = true;
1918  I.setHasNoSignedWrap(true);
1919  }
1920  if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedSub(Op0, Op1, I)) {
1921  Changed = true;
1922  I.setHasNoUnsignedWrap(true);
1923  }
1924 
1925  return Changed ? &I : nullptr;
1926  };
1927 
1928  // First, let's try to interpret `sub a, b` as `add a, (sub 0, b)`,
1929  // and let's try to sink `(sub 0, b)` into `b` itself. But only if this isn't
1930  // a pure negation used by a select that looks like abs/nabs.
1931  bool IsNegation = match(Op0, m_ZeroInt());
1932  if (!IsNegation || none_of(I.users(), [&I, Op1](const User *U) {
1933  const Instruction *UI = dyn_cast<Instruction>(U);
1934  if (!UI)
1935  return false;
1936  return match(UI,
1937  m_Select(m_Value(), m_Specific(Op1), m_Specific(&I))) ||
1938  match(UI, m_Select(m_Value(), m_Specific(&I), m_Specific(Op1)));
1939  })) {
1940  if (Value *NegOp1 = Negator::Negate(IsNegation, Op1, *this))
1941  return BinaryOperator::CreateAdd(NegOp1, Op0);
1942  }
1943  if (IsNegation)
1944  return TryToNarrowDeduceFlags(); // Should have been handled in Negator!
1945 
1946  // (A*B)-(A*C) -> A*(B-C) etc
1947  if (Value *V = foldUsingDistributiveLaws(I))
1948  return replaceInstUsesWith(I, V);
1949 
1950  if (I.getType()->isIntOrIntVectorTy(1))
1951  return BinaryOperator::CreateXor(Op0, Op1);
1952 
1953  // Replace (-1 - A) with (~A).
1954  if (match(Op0, m_AllOnes()))
1955  return BinaryOperator::CreateNot(Op1);
1956 
1957  // (X + -1) - Y --> ~Y + X
1958  Value *X, *Y;
1959  if (match(Op0, m_OneUse(m_Add(m_Value(X), m_AllOnes()))))
1960  return BinaryOperator::CreateAdd(Builder.CreateNot(Op1), X);
1961 
1962  // Reassociate sub/add sequences to create more add instructions and
1963  // reduce dependency chains:
1964  // ((X - Y) + Z) - Op1 --> (X + Z) - (Y + Op1)
1965  Value *Z;
1967  m_Value(Z))))) {
1968  Value *XZ = Builder.CreateAdd(X, Z);
1969  Value *YW = Builder.CreateAdd(Y, Op1);
1970  return BinaryOperator::CreateSub(XZ, YW);
1971  }
1972 
1973  // ((X - Y) - Op1) --> X - (Y + Op1)
1974  if (match(Op0, m_OneUse(m_Sub(m_Value(X), m_Value(Y))))) {
1975  Value *Add = Builder.CreateAdd(Y, Op1);
1976  return BinaryOperator::CreateSub(X, Add);
1977  }
1978 
1979  // (~X) - (~Y) --> Y - X
1980  // This is placed after the other reassociations and explicitly excludes a
1981  // sub-of-sub pattern to avoid infinite looping.
1982  if (isFreeToInvert(Op0, Op0->hasOneUse()) &&
1983  isFreeToInvert(Op1, Op1->hasOneUse()) &&
1984  !match(Op0, m_Sub(m_ImmConstant(), m_Value()))) {
1985  Value *NotOp0 = Builder.CreateNot(Op0);
1986  Value *NotOp1 = Builder.CreateNot(Op1);
1987  return BinaryOperator::CreateSub(NotOp1, NotOp0);
1988  }
1989 
1990  auto m_AddRdx = [](Value *&Vec) {
1991  return m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_add>(m_Value(Vec)));
1992  };
1993  Value *V0, *V1;
1994  if (match(Op0, m_AddRdx(V0)) && match(Op1, m_AddRdx(V1)) &&
1995  V0->getType() == V1->getType()) {
1996  // Difference of sums is sum of differences:
1997  // add_rdx(V0) - add_rdx(V1) --> add_rdx(V0 - V1)
1998  Value *Sub = Builder.CreateSub(V0, V1);
1999  Value *Rdx = Builder.CreateIntrinsic(Intrinsic::vector_reduce_add,
2000  {Sub->getType()}, {Sub});
2001  return replaceInstUsesWith(I, Rdx);
2002  }
2003 
2004  if (Constant *C = dyn_cast<Constant>(Op0)) {
2005  Value *X;
2006  if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
2007  // C - (zext bool) --> bool ? C - 1 : C
2009  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
2010  // C - (sext bool) --> bool ? C + 1 : C
2012 
2013  // C - ~X == X + (1+C)
2014  if (match(Op1, m_Not(m_Value(X))))
2016 
2017  // Try to fold constant sub into select arguments.
2018  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
2019  if (Instruction *R = FoldOpIntoSelect(I, SI))
2020  return R;
2021 
2022  // Try to fold constant sub into PHI values.
2023  if (PHINode *PN = dyn_cast<PHINode>(Op1))
2024  if (Instruction *R = foldOpIntoPhi(I, PN))
2025  return R;
2026 
2027  Constant *C2;
2028 
2029  // C-(C2-X) --> X+(C-C2)
2030  if (match(Op1, m_Sub(m_ImmConstant(C2), m_Value(X))))
2032  }
2033 
2034  const APInt *Op0C;
2035  if (match(Op0, m_APInt(Op0C))) {
2036  if (Op0C->isMask()) {
2037  // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known
2038  // zero.
2039  KnownBits RHSKnown = computeKnownBits(Op1, 0, &I);
2040  if ((*Op0C | RHSKnown.Zero).isAllOnes())
2041  return BinaryOperator::CreateXor(Op1, Op0);
2042  }
2043 
2044  // C - ((C3 -nuw X) & C2) --> (C - (C2 & C3)) + (X & C2) when:
2045  // (C3 - ((C2 & C3) - 1)) is pow2
2046  // ((C2 + C3) & ((C2 & C3) - 1)) == ((C2 & C3) - 1)
2047  // C2 is negative pow2 || sub nuw
2048  const APInt *C2, *C3;
2049  BinaryOperator *InnerSub;
2050  if (match(Op1, m_OneUse(m_And(m_BinOp(InnerSub), m_APInt(C2)))) &&
2051  match(InnerSub, m_Sub(m_APInt(C3), m_Value(X))) &&
2052  (InnerSub->hasNoUnsignedWrap() || C2->isNegatedPowerOf2())) {
2053  APInt C2AndC3 = *C2 & *C3;
2054  APInt C2AndC3Minus1 = C2AndC3 - 1;
2055  APInt C2AddC3 = *C2 + *C3;
2056  if ((*C3 - C2AndC3Minus1).isPowerOf2() &&
2057  C2AndC3Minus1.isSubsetOf(C2AddC3)) {
2058  Value *And = Builder.CreateAnd(X, ConstantInt::get(I.getType(), *C2));
2060  And, ConstantInt::get(I.getType(), *Op0C - C2AndC3));
2061  }
2062  }
2063  }
2064 
2065  {
2066  Value *Y;
2067  // X-(X+Y) == -Y X-(Y+X) == -Y
2068  if (match(Op1, m_c_Add(m_Specific(Op0), m_Value(Y))))
2069  return BinaryOperator::CreateNeg(Y);
2070 
2071  // (X-Y)-X == -Y
2072  if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))
2073  return BinaryOperator::CreateNeg(Y);
2074  }
2075 
2076  // (sub (or A, B) (and A, B)) --> (xor A, B)
2077  {
2078  Value *A, *B;
2079  if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
2080  match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
2081  return BinaryOperator::CreateXor(A, B);
2082  }
2083 
2084  // (sub (add A, B) (or A, B)) --> (and A, B)
2085  {
2086  Value *A, *B;
2087  if (match(Op0, m_Add(m_Value(A), m_Value(B))) &&
2088  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
2089  return BinaryOperator::CreateAnd(A, B);
2090  }
2091 
2092  // (sub (add A, B) (and A, B)) --> (or A, B)
2093  {
2094  Value *A, *B;
2095  if (match(Op0, m_Add(m_Value(A), m_Value(B))) &&
2096  match(Op1, m_c_And(m_Specific(A), m_Specific(B))))
2097  return BinaryOperator::CreateOr(A, B);
2098  }
2099 
2100  // (sub (and A, B) (or A, B)) --> neg (xor A, B)
2101  {
2102  Value *A, *B;
2103  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2104  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))) &&
2105  (Op0->hasOneUse() || Op1->hasOneUse()))
2106  return BinaryOperator::CreateNeg(Builder.CreateXor(A, B));
2107  }
2108 
2109  // (sub (or A, B), (xor A, B)) --> (and A, B)
2110  {
2111  Value *A, *B;
2112  if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
2113  match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
2114  return BinaryOperator::CreateAnd(A, B);
2115  }
2116 
2117  // (sub (xor A, B) (or A, B)) --> neg (and A, B)
2118  {
2119  Value *A, *B;
2120  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
2121  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))) &&
2122  (Op0->hasOneUse() || Op1->hasOneUse()))
2123  return BinaryOperator::CreateNeg(Builder.CreateAnd(A, B));
2124  }
2125 
2126  {
2127  Value *Y;
2128  // ((X | Y) - X) --> (~X & Y)
2129  if (match(Op0, m_OneUse(m_c_Or(m_Value(Y), m_Specific(Op1)))))
2130  return BinaryOperator::CreateAnd(
2131  Y, Builder.CreateNot(Op1, Op1->getName() + ".not"));
2132  }
2133 
2134  {
2135  // (sub (and Op1, (neg X)), Op1) --> neg (and Op1, (add X, -1))
2136  Value *X;
2137  if (match(Op0, m_OneUse(m_c_And(m_Specific(Op1),
2138  m_OneUse(m_Neg(m_Value(X))))))) {
2139  return BinaryOperator::CreateNeg(Builder.CreateAnd(
2140  Op1, Builder.CreateAdd(X, Constant::getAllOnesValue(I.getType()))));
2141  }
2142  }
2143 
2144  {
2145  // (sub (and Op1, C), Op1) --> neg (and Op1, ~C)
2146  Constant *C;
2147  if (match(Op0, m_OneUse(m_And(m_Specific(Op1), m_Constant(C))))) {
2149  Builder.CreateAnd(Op1, Builder.CreateNot(C)));
2150  }
2151  }
2152 
2153  if (Instruction *R = foldSubOfMinMax(I, Builder))
2154  return R;
2155 
2156  {
2157  // If we have a subtraction between some value and a select between
2158  // said value and something else, sink subtraction into select hands, i.e.:
2159  // sub (select %Cond, %TrueVal, %FalseVal), %Op1
2160  // ->
2161  // select %Cond, (sub %TrueVal, %Op1), (sub %FalseVal, %Op1)
2162  // or
2163  // sub %Op0, (select %Cond, %TrueVal, %FalseVal)
2164  // ->
2165  // select %Cond, (sub %Op0, %TrueVal), (sub %Op0, %FalseVal)
2166  // This will result in select between new subtraction and 0.
2167  auto SinkSubIntoSelect =
2168  [Ty = I.getType()](Value *Select, Value *OtherHandOfSub,
2169  auto SubBuilder) -> Instruction * {
2170  Value *Cond, *TrueVal, *FalseVal;
2172  m_Value(FalseVal)))))
2173  return nullptr;
2174  if (OtherHandOfSub != TrueVal && OtherHandOfSub != FalseVal)
2175  return nullptr;
2176  // While it is really tempting to just create two subtractions and let
2177  // InstCombine fold one of those to 0, it isn't possible to do so
2178  // because of worklist visitation order. So ugly it is.
2179  bool OtherHandOfSubIsTrueVal = OtherHandOfSub == TrueVal;
2180  Value *NewSub = SubBuilder(OtherHandOfSubIsTrueVal ? FalseVal : TrueVal);
2181  Constant *Zero = Constant::getNullValue(Ty);
2182  SelectInst *NewSel =
2183  SelectInst::Create(Cond, OtherHandOfSubIsTrueVal ? Zero : NewSub,
2184  OtherHandOfSubIsTrueVal ? NewSub : Zero);
2185  // Preserve prof metadata if any.
2186  NewSel->copyMetadata(cast<Instruction>(*Select));
2187  return NewSel;
2188  };
2189  if (Instruction *NewSel = SinkSubIntoSelect(
2190  /*Select=*/Op0, /*OtherHandOfSub=*/Op1,
2191  [Builder = &Builder, Op1](Value *OtherHandOfSelect) {
2192  return Builder->CreateSub(OtherHandOfSelect,
2193  /*OtherHandOfSub=*/Op1);
2194  }))
2195  return NewSel;
2196  if (Instruction *NewSel = SinkSubIntoSelect(
2197  /*Select=*/Op1, /*OtherHandOfSub=*/Op0,
2198  [Builder = &Builder, Op0](Value *OtherHandOfSelect) {
2199  return Builder->CreateSub(/*OtherHandOfSub=*/Op0,
2200  OtherHandOfSelect);
2201  }))
2202  return NewSel;
2203  }
2204 
2205  // (X - (X & Y)) --> (X & ~Y)
2206  if (match(Op1, m_c_And(m_Specific(Op0), m_Value(Y))) &&
2207  (Op1->hasOneUse() || isa<Constant>(Y)))
2208  return BinaryOperator::CreateAnd(
2209  Op0, Builder.CreateNot(Y, Y->getName() + ".not"));
2210 
2211  // ~X - Min/Max(~X, Y) -> ~Min/Max(X, ~Y) - X
2212  // ~X - Min/Max(Y, ~X) -> ~Min/Max(X, ~Y) - X
2213  // Min/Max(~X, Y) - ~X -> X - ~Min/Max(X, ~Y)
2214  // Min/Max(Y, ~X) - ~X -> X - ~Min/Max(X, ~Y)
2215  // As long as Y is freely invertible, this will be neutral or a win.
2216  // Note: We don't generate the inverse max/min, just create the 'not' of
2217  // it and let other folds do the rest.
2218  if (match(Op0, m_Not(m_Value(X))) &&
2219  match(Op1, m_c_MaxOrMin(m_Specific(Op0), m_Value(Y))) &&
2220  !Op0->hasNUsesOrMore(3) && isFreeToInvert(Y, Y->hasOneUse())) {
2221  Value *Not = Builder.CreateNot(Op1);
2222  return BinaryOperator::CreateSub(Not, X);
2223  }
2224  if (match(Op1, m_Not(m_Value(X))) &&
2225  match(Op0, m_c_MaxOrMin(m_Specific(Op1), m_Value(Y))) &&
2226  !Op1->hasNUsesOrMore(3) && isFreeToInvert(Y, Y->hasOneUse())) {
2227  Value *Not = Builder.CreateNot(Op0);
2228  return BinaryOperator::CreateSub(X, Not);
2229  }
2230 
2231  // Optimize pointer differences into the same array into a size. Consider:
2232  // &A[10] - &A[0]: we should compile this to "10".
2233  Value *LHSOp, *RHSOp;
2234  if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
2235  match(Op1, m_PtrToInt(m_Value(RHSOp))))
2236  if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType(),
2237  I.hasNoUnsignedWrap()))
2238  return replaceInstUsesWith(I, Res);
2239 
2240  // trunc(p)-trunc(q) -> trunc(p-q)
2241  if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) &&
2242  match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp)))))
2243  if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType(),
2244  /* IsNUW */ false))
2245  return replaceInstUsesWith(I, Res);
2246 
2247  // Canonicalize a shifty way to code absolute value to the common pattern.
2248  // There are 2 potential commuted variants.
2249  // We're relying on the fact that we only do this transform when the shift has
2250  // exactly 2 uses and the xor has exactly 1 use (otherwise, we might increase
2251  // instructions).
2252  Value *A;
2253  const APInt *ShAmt;
2254  Type *Ty = I.getType();
2255  if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
2256  Op1->hasNUses(2) && *ShAmt == Ty->getScalarSizeInBits() - 1 &&
2257  match(Op0, m_OneUse(m_c_Xor(m_Specific(A), m_Specific(Op1))))) {
2258  // B = ashr i32 A, 31 ; smear the sign bit
2259  // sub (xor A, B), B ; flip bits if negative and subtract -1 (add 1)
2260  // --> (A < 0) ? -A : A
2261  Value *IsNeg = Builder.CreateIsNeg(A);
2262  // Copy the nuw/nsw flags from the sub to the negate.
2263  Value *NegA = Builder.CreateNeg(A, "", I.hasNoUnsignedWrap(),
2264  I.hasNoSignedWrap());
2265  return SelectInst::Create(IsNeg, NegA, A);
2266  }
2267 
2268  // If we are subtracting a low-bit masked subset of some value from an add
2269  // of that same value with no low bits changed, that is clearing some low bits
2270  // of the sum:
2271  // sub (X + AddC), (X & AndC) --> and (X + AddC), ~AndC
2272  const APInt *AddC, *AndC;
2273  if (match(Op0, m_Add(m_Value(X), m_APInt(AddC))) &&
2274  match(Op1, m_And(m_Specific(X), m_APInt(AndC)))) {
2275  unsigned BitWidth = Ty->getScalarSizeInBits();
2276  unsigned Cttz = AddC->countTrailingZeros();
2277  APInt HighMask(APInt::getHighBitsSet(BitWidth, BitWidth - Cttz));
2278  if ((HighMask & *AndC).isZero())
2279  return BinaryOperator::CreateAnd(Op0, ConstantInt::get(Ty, ~(*AndC)));
2280  }
2281 
2282  if (Instruction *V =
2283  canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
2284  return V;
2285 
2286  // X - usub.sat(X, Y) => umin(X, Y)
2287  if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Specific(Op0),
2288  m_Value(Y)))))
2289  return replaceInstUsesWith(
2290  I, Builder.CreateIntrinsic(Intrinsic::umin, {I.getType()}, {Op0, Y}));
2291 
2292  // umax(X, Op1) - Op1 --> usub.sat(X, Op1)
2293  // TODO: The one-use restriction is not strictly necessary, but it may
2294  // require improving other pattern matching and/or codegen.
2295  if (match(Op0, m_OneUse(m_c_UMax(m_Value(X), m_Specific(Op1)))))
2296  return replaceInstUsesWith(
2297  I, Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {X, Op1}));
2298 
2299  // Op0 - umin(X, Op0) --> usub.sat(Op0, X)
2300  if (match(Op1, m_OneUse(m_c_UMin(m_Value(X), m_Specific(Op0)))))
2301  return replaceInstUsesWith(
2302  I, Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {Op0, X}));
2303 
2304  // Op0 - umax(X, Op0) --> 0 - usub.sat(X, Op0)
2305  if (match(Op1, m_OneUse(m_c_UMax(m_Value(X), m_Specific(Op0))))) {
2306  Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {X, Op0});
2307  return BinaryOperator::CreateNeg(USub);
2308  }
2309 
2310  // umin(X, Op1) - Op1 --> 0 - usub.sat(Op1, X)
2311  if (match(Op0, m_OneUse(m_c_UMin(m_Value(X), m_Specific(Op1))))) {
2312  Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {Op1, X});
2313  return BinaryOperator::CreateNeg(USub);
2314  }
2315 
2316  // C - ctpop(X) => ctpop(~X) if C is bitwidth
2317  if (match(Op0, m_SpecificInt(Ty->getScalarSizeInBits())) &&
2318  match(Op1, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(X)))))
2319  return replaceInstUsesWith(
2320  I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
2321  {Builder.CreateNot(X)}));
2322 
2323  return TryToNarrowDeduceFlags();
2324 }
2325 
2326 /// This eliminates floating-point negation in either 'fneg(X)' or
2327 /// 'fsub(-0.0, X)' form by combining into a constant operand.
2329  // This is limited with one-use because fneg is assumed better for
2330  // reassociation and cheaper in codegen than fmul/fdiv.
2331  // TODO: Should the m_OneUse restriction be removed?
2332  Instruction *FNegOp;
2333  if (!match(&I, m_FNeg(m_OneUse(m_Instruction(FNegOp)))))
2334  return nullptr;
2335 
2336  Value *X;
2337  Constant *C;
2338 
2339  // Fold negation into constant operand.
2340  // -(X * C) --> X * (-C)
2341  if (match(FNegOp, m_FMul(m_Value(X), m_Constant(C))))
2342  if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
2343  return BinaryOperator::CreateFMulFMF(X, NegC, &I);
2344  // -(X / C) --> X / (-C)
2345  if (match(FNegOp, m_FDiv(m_Value(X), m_Constant(C))))
2346  if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
2347  return BinaryOperator::CreateFDivFMF(X, NegC, &I);
2348  // -(C / X) --> (-C) / X
2349  if (match(FNegOp, m_FDiv(m_Constant(C), m_Value(X))))
2350  if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL)) {
2351  Instruction *FDiv = BinaryOperator::CreateFDivFMF(NegC, X, &I);
2352 
2353  // Intersect 'nsz' and 'ninf' because those special value exceptions may
2354  // not apply to the fdiv. Everything else propagates from the fneg.
2355  // TODO: We could propagate nsz/ninf from fdiv alone?
2356  FastMathFlags FMF = I.getFastMathFlags();
2357  FastMathFlags OpFMF = FNegOp->getFastMathFlags();
2358  FDiv->setHasNoSignedZeros(FMF.noSignedZeros() && OpFMF.noSignedZeros());
2359  FDiv->setHasNoInfs(FMF.noInfs() && OpFMF.noInfs());
2360  return FDiv;
2361  }
2362  // With NSZ [ counter-example with -0.0: -(-0.0 + 0.0) != 0.0 + -0.0 ]:
2363  // -(X + C) --> -X + -C --> -C - X
2364  if (I.hasNoSignedZeros() && match(FNegOp, m_FAdd(m_Value(X), m_Constant(C))))
2365  if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
2366  return BinaryOperator::CreateFSubFMF(NegC, X, &I);
2367 
2368  return nullptr;
2369 }
2370 
2373  Value *FNeg;
2374  if (!match(&I, m_FNeg(m_Value(FNeg))))
2375  return nullptr;
2376 
2377  Value *X, *Y;
2378  if (match(FNeg, m_OneUse(m_FMul(m_Value(X), m_Value(Y)))))
2379  return BinaryOperator::CreateFMulFMF(Builder.CreateFNegFMF(X, &I), Y, &I);
2380 
2381  if (match(FNeg, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))))
2382  return BinaryOperator::CreateFDivFMF(Builder.CreateFNegFMF(X, &I), Y, &I);
2383 
2384  return nullptr;
2385 }
2386 
2388  Value *Op = I.getOperand(0);
2389 
2390  if (Value *V = simplifyFNegInst(Op, I.getFastMathFlags(),
2391  getSimplifyQuery().getWithInstruction(&I)))
2392  return replaceInstUsesWith(I, V);
2393 
2395  return X;
2396 
2397  Value *X, *Y;
2398 
2399  // If we can ignore the sign of zeros: -(X - Y) --> (Y - X)
2400  if (I.hasNoSignedZeros() &&
2402  return BinaryOperator::CreateFSubFMF(Y, X, &I);
2403 
2405  return R;
2406 
2407  // Try to eliminate fneg if at least 1 arm of the select is negated.
2408  Value *Cond;
2410  // Unlike most transforms, this one is not safe to propagate nsz unless
2411  // it is present on the original select. (We are conservatively intersecting
2412  // the nsz flags from the select and root fneg instruction.)
2413  auto propagateSelectFMF = [&](SelectInst *S, bool CommonOperand) {
2414  S->copyFastMathFlags(&I);
2415  if (auto *OldSel = dyn_cast<SelectInst>(Op))
2416  if (!OldSel->hasNoSignedZeros() && !CommonOperand &&
2417  !isGuaranteedNotToBeUndefOrPoison(OldSel->getCondition()))
2418  S->setHasNoSignedZeros(false);
2419  };
2420  // -(Cond ? -P : Y) --> Cond ? P : -Y
2421  Value *P;
2422  if (match(X, m_FNeg(m_Value(P)))) {
2423  Value *NegY = Builder.CreateFNegFMF(Y, &I, Y->getName() + ".neg");
2424  SelectInst *NewSel = SelectInst::Create(Cond, P, NegY);
2425  propagateSelectFMF(NewSel, P == Y);
2426  return NewSel;
2427  }
2428  // -(Cond ? X : -P) --> Cond ? -X : P
2429  if (match(Y, m_FNeg(m_Value(P)))) {
2430  Value *NegX = Builder.CreateFNegFMF(X, &I, X->getName() + ".neg");
2431  SelectInst *NewSel = SelectInst::Create(Cond, NegX, P);
2432  propagateSelectFMF(NewSel, P == X);
2433  return NewSel;
2434  }
2435  }
2436 
2437  return nullptr;
2438 }
2439 
2441  if (Value *V = simplifyFSubInst(I.getOperand(0), I.getOperand(1),
2442  I.getFastMathFlags(),
2443  getSimplifyQuery().getWithInstruction(&I)))
2444  return replaceInstUsesWith(I, V);
2445 
2446  if (Instruction *X = foldVectorBinop(I))
2447  return X;
2448 
2449  if (Instruction *Phi = foldBinopWithPhiOperands(I))
2450  return Phi;
2451 
2452  // Subtraction from -0.0 is the canonical form of fneg.
2453  // fsub -0.0, X ==> fneg X
2454  // fsub nsz 0.0, X ==> fneg nsz X
2455  //
2456  // FIXME This matcher does not respect FTZ or DAZ yet:
2457  // fsub -0.0, Denorm ==> +-0
2458  // fneg Denorm ==> -Denorm
2459  Value *Op;
2460  if (match(&I, m_FNeg(m_Value(Op))))
2461  return UnaryOperator::CreateFNegFMF(Op, &I);
2462 
2464  return X;
2465 
2467  return R;
2468 
2469  Value *X, *Y;
2470  Constant *C;
2471 
2472  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2473  // If Op0 is not -0.0 or we can ignore -0.0: Z - (X - Y) --> Z + (Y - X)
2474  // Canonicalize to fadd to make analysis easier.
2475  // This can also help codegen because fadd is commutative.
2476  // Note that if this fsub was really an fneg, the fadd with -0.0 will get
2477  // killed later. We still limit that particular transform with 'hasOneUse'
2478  // because an fneg is assumed better/cheaper than a generic fsub.
2479  if (I.hasNoSignedZeros() || CannotBeNegativeZero(Op0, SQ.TLI)) {
2480  if (match(Op1, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) {
2481  Value *NewSub = Builder.CreateFSubFMF(Y, X, &I);
2482  return BinaryOperator::CreateFAddFMF(Op0, NewSub, &I);
2483  }
2484  }
2485 
2486  // (-X) - Op1 --> -(X + Op1)
2487  if (I.hasNoSignedZeros() && !isa<ConstantExpr>(Op0) &&
2488  match(Op0, m_OneUse(m_FNeg(m_Value(X))))) {
2489  Value *FAdd = Builder.CreateFAddFMF(X, Op1, &I);
2491  }
2492 
2493  if (isa<Constant>(Op0))
2494  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
2495  if (Instruction *NV = FoldOpIntoSelect(I, SI))
2496  return NV;
2497 
2498  // X - C --> X + (-C)
2499  // But don't transform constant expressions because there's an inverse fold
2500  // for X + (-Y) --> X - Y.
2501  if (match(Op1, m_ImmConstant(C)))
2502  if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
2503  return BinaryOperator::CreateFAddFMF(Op0, NegC, &I);
2504 
2505  // X - (-Y) --> X + Y
2506  if (match(Op1, m_FNeg(m_Value(Y))))
2507  return BinaryOperator::CreateFAddFMF(Op0, Y, &I);
2508 
2509  // Similar to above, but look through a cast of the negated value:
2510  // X - (fptrunc(-Y)) --> X + fptrunc(Y)
2511  Type *Ty = I.getType();
2512  if (match(Op1, m_OneUse(m_FPTrunc(m_FNeg(m_Value(Y))))))
2513  return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPTrunc(Y, Ty), &I);
2514 
2515  // X - (fpext(-Y)) --> X + fpext(Y)
2516  if (match(Op1, m_OneUse(m_FPExt(m_FNeg(m_Value(Y))))))
2517  return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPExt(Y, Ty), &I);
2518 
2519  // Similar to above, but look through fmul/fdiv of the negated value:
2520  // Op0 - (-X * Y) --> Op0 + (X * Y)
2521  // Op0 - (Y * -X) --> Op0 + (X * Y)
2522  if (match(Op1, m_OneUse(m_c_FMul(m_FNeg(m_Value(X)), m_Value(Y))))) {
2523  Value *FMul = Builder.CreateFMulFMF(X, Y, &I);
2524  return BinaryOperator::CreateFAddFMF(Op0, FMul, &I);
2525  }
2526  // Op0 - (-X / Y) --> Op0 + (X / Y)
2527  // Op0 - (X / -Y) --> Op0 + (X / Y)
2528  if (match(Op1, m_OneUse(m_FDiv(m_FNeg(m_Value(X)), m_Value(Y)))) ||
2529  match(Op1, m_OneUse(m_FDiv(m_Value(X), m_FNeg(m_Value(Y)))))) {
2530  Value *FDiv = Builder.CreateFDivFMF(X, Y, &I);
2531  return BinaryOperator::CreateFAddFMF(Op0, FDiv, &I);
2532  }
2533 
2534  // Handle special cases for FSub with selects feeding the operation
2535  if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
2536  return replaceInstUsesWith(I, V);
2537 
2538  if (I.hasAllowReassoc() && I.hasNoSignedZeros()) {
2539  // (Y - X) - Y --> -X
2540  if (match(Op0, m_FSub(m_Specific(Op1), m_Value(X))))
2541  return UnaryOperator::CreateFNegFMF(X, &I);
2542 
2543  // Y - (X + Y) --> -X
2544  // Y - (Y + X) --> -X
2545  if (match(Op1, m_c_FAdd(m_Specific(Op0), m_Value(X))))
2546  return UnaryOperator::CreateFNegFMF(X, &I);
2547 
2548  // (X * C) - X --> X * (C - 1.0)
2549  if (match(Op0, m_FMul(m_Specific(Op1), m_Constant(C)))) {
2550  if (Constant *CSubOne = ConstantFoldBinaryOpOperands(
2551  Instruction::FSub, C, ConstantFP::get(Ty, 1.0), DL))
2552  return BinaryOperator::CreateFMulFMF(Op1, CSubOne, &I);
2553  }
2554  // X - (X * C) --> X * (1.0 - C)
2555  if (match(Op1, m_FMul(m_Specific(Op0), m_Constant(C)))) {
2556  if (Constant *OneSubC = ConstantFoldBinaryOpOperands(
2557  Instruction::FSub, ConstantFP::get(Ty, 1.0), C, DL))
2558  return BinaryOperator::CreateFMulFMF(Op0, OneSubC, &I);
2559  }
2560 
2561  // Reassociate fsub/fadd sequences to create more fadd instructions and
2562  // reduce dependency chains:
2563  // ((X - Y) + Z) - Op1 --> (X + Z) - (Y + Op1)
2564  Value *Z;
2566  m_Value(Z))))) {
2567  Value *XZ = Builder.CreateFAddFMF(X, Z, &I);
2568  Value *YW = Builder.CreateFAddFMF(Y, Op1, &I);
2569  return BinaryOperator::CreateFSubFMF(XZ, YW, &I);
2570  }
2571 
2572  auto m_FaddRdx = [](Value *&Sum, Value *&Vec) {
2573  return m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(m_Value(Sum),
2574  m_Value(Vec)));
2575  };
2576  Value *A0, *A1, *V0, *V1;
2577  if (match(Op0, m_FaddRdx(A0, V0)) && match(Op1, m_FaddRdx(A1, V1)) &&
2578  V0->getType() == V1->getType()) {
2579  // Difference of sums is sum of differences:
2580  // add_rdx(A0, V0) - add_rdx(A1, V1) --> add_rdx(A0, V0 - V1) - A1
2581  Value *Sub = Builder.CreateFSubFMF(V0, V1, &I);
2582  Value *Rdx = Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,
2583  {Sub->getType()}, {A0, Sub}, &I);
2584  return BinaryOperator::CreateFSubFMF(Rdx, A1, &I);
2585  }
2586 
2588  return F;
2589 
2590  // TODO: This performs reassociative folds for FP ops. Some fraction of the
2591  // functionality has been subsumed by simple pattern matching here and in
2592  // InstSimplify. We should let a dedicated reassociation pass handle more
2593  // complex pattern matching and remove this from InstCombine.
2594  if (Value *V = FAddCombine(Builder).simplify(&I))
2595  return replaceInstUsesWith(I, V);
2596 
2597  // (X - Y) - Op1 --> X - (Y + Op1)
2598  if (match(Op0, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) {
2599  Value *FAdd = Builder.CreateFAddFMF(Y, Op1, &I);
2601  }
2602  }
2603 
2604  return nullptr;
2605 }
llvm::lltok::APFloat
@ APFloat
Definition: LLToken.h:459
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:2371
llvm::InstCombinerImpl::visitFAdd
Instruction * visitFAdd(BinaryOperator &I)
Definition: InstCombineAddSub.cpp:1591
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:242
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:1723
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:366
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:1481
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
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:2992
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:5440
llvm::Type::getScalarType
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:328
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:1199
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::APInt::getMaxValue
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:186
llvm::PatternMatch::m_CombineOr
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:218
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:3340
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:1431
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:5464
T
#define T
Definition: Mips16ISelLowering.cpp:341
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:385
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:871
AlignOf.h
foldSubOfMinMax
static Instruction * foldSubOfMinMax(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineAddSub.cpp:1819
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:2952
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:1530
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:5456
llvm::APFloat::getSemantics
const fltSemantics & getSemantics() const
Definition: APFloat.h:1238
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:2157
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:1546
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:1767
llvm::RecurKind::And
@ And
Bitwise or logical AND of integers.
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:157
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:895
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:1516
SI
@ SI
Definition: SIInstrInfo.cpp:7882
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:1563
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:3416
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:1003
llvm::PatternMatch::m_Xor
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1105
llvm::APInt::isSubsetOf
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
Definition: APInt.h:1227
llvm::InstCombinerImpl::visitFNeg
Instruction * visitFNeg(UnaryOperator &I)
Definition: InstCombineAddSub.cpp:2387
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:716
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:1309
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::Instruction::hasNoUnsignedWrap
bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
Definition: Instruction.cpp:165
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:1672
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:2605
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:917
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:197
llvm::InstCombinerImpl::visitFSub
Instruction * visitFSub(BinaryOperator &I)
Definition: InstCombineAddSub.cpp:2440
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
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::Instruction::getFastMathFlags
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
Definition: Instruction.cpp:319
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1736
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:4849
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
foldBoxMultiply
static Instruction * foldBoxMultiply(BinaryOperator &I)
Reduce a sequence of masked half-width multiplies to a single multiply.
Definition: InstCombineAddSub.cpp:1272
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:138
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:2328
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 foldUsingDistributiveLaws.
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:1743
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:5215
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:2162
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:269
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:216
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
llvm::APInt::isNegatedPowerOf2
bool isNegatedPowerOf2() const
Check if this APInt's negated value is a power of two greater than zero.
Definition: APInt.h:434
Casting.h
llvm::fltSemantics
Definition: APFloat.cpp:71
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_c_Mul
BinaryOp_match< LHS, RHS, Instruction::Mul, true > m_c_Mul(const LHS &L, const RHS &R)
Matches a Mul with LHS and RHS in either order.
Definition: PatternMatch.h:2244
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:6475
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:1865
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:3512
llvm::APFloatBase::rmNearestTiesToEven
static constexpr roundingMode rmNearestTiesToEven
Definition: APFloat.h:200
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:244
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:249
llvm::SIToFPInst
This class represents a cast from signed integer to floating point.
Definition: Instructions.h:5044
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
CreateMul
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:253
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:240
llvm::PHINode
Definition: Instructions.h:2698
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