LLVM  14.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 <= array_lengthof(TmpResult) + 1) &&
580  "out-of-bound access");
581 
582  Value *Result;
583  if (!SimpVect.empty())
584  Result = createNaryFAdd(SimpVect, InstrQuota);
585  else {
586  // The addition is folded to 0.0.
587  Result = ConstantFP::get(Instr->getType(), 0.0);
588  }
589 
590  return Result;
591 }
592 
593 Value *FAddCombine::createNaryFAdd
594  (const AddendVect &Opnds, unsigned InstrQuota) {
595  assert(!Opnds.empty() && "Expect at least one addend");
596 
597  // Step 1: Check if the # of instructions needed exceeds the quota.
598 
599  unsigned InstrNeeded = calcInstrNumber(Opnds);
600  if (InstrNeeded > InstrQuota)
601  return nullptr;
602 
603  initCreateInstNum();
604 
605  // step 2: Emit the N-ary addition.
606  // Note that at most three instructions are involved in Fadd-InstCombine: the
607  // addition in question, and at most two neighboring instructions.
608  // The resulting optimized addition should have at least one less instruction
609  // than the original addition expression tree. This implies that the resulting
610  // N-ary addition has at most two instructions, and we don't need to worry
611  // about tree-height when constructing the N-ary addition.
612 
613  Value *LastVal = nullptr;
614  bool LastValNeedNeg = false;
615 
616  // Iterate the addends, creating fadd/fsub using adjacent two addends.
617  for (const FAddend *Opnd : Opnds) {
618  bool NeedNeg;
619  Value *V = createAddendVal(*Opnd, NeedNeg);
620  if (!LastVal) {
621  LastVal = V;
622  LastValNeedNeg = NeedNeg;
623  continue;
624  }
625 
626  if (LastValNeedNeg == NeedNeg) {
627  LastVal = createFAdd(LastVal, V);
628  continue;
629  }
630 
631  if (LastValNeedNeg)
632  LastVal = createFSub(V, LastVal);
633  else
634  LastVal = createFSub(LastVal, V);
635 
636  LastValNeedNeg = false;
637  }
638 
639  if (LastValNeedNeg) {
640  LastVal = createFNeg(LastVal);
641  }
642 
643 #ifndef NDEBUG
644  assert(CreateInstrNum == InstrNeeded &&
645  "Inconsistent in instruction numbers");
646 #endif
647 
648  return LastVal;
649 }
650 
651 Value *FAddCombine::createFSub(Value *Opnd0, Value *Opnd1) {
652  Value *V = Builder.CreateFSub(Opnd0, Opnd1);
653  if (Instruction *I = dyn_cast<Instruction>(V))
654  createInstPostProc(I);
655  return V;
656 }
657 
658 Value *FAddCombine::createFNeg(Value *V) {
659  Value *NewV = Builder.CreateFNeg(V);
660  if (Instruction *I = dyn_cast<Instruction>(NewV))
661  createInstPostProc(I, true); // fneg's don't receive instruction numbers.
662  return NewV;
663 }
664 
665 Value *FAddCombine::createFAdd(Value *Opnd0, Value *Opnd1) {
666  Value *V = Builder.CreateFAdd(Opnd0, Opnd1);
667  if (Instruction *I = dyn_cast<Instruction>(V))
668  createInstPostProc(I);
669  return V;
670 }
671 
672 Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) {
673  Value *V = Builder.CreateFMul(Opnd0, Opnd1);
674  if (Instruction *I = dyn_cast<Instruction>(V))
675  createInstPostProc(I);
676  return V;
677 }
678 
679 void FAddCombine::createInstPostProc(Instruction *NewInstr, bool NoNumber) {
680  NewInstr->setDebugLoc(Instr->getDebugLoc());
681 
682  // Keep track of the number of instruction created.
683  if (!NoNumber)
684  incCreateInstNum();
685 
686  // Propagate fast-math flags
687  NewInstr->setFastMathFlags(Instr->getFastMathFlags());
688 }
689 
690 // Return the number of instruction needed to emit the N-ary addition.
691 // NOTE: Keep this function in sync with createAddendVal().
692 unsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) {
693  unsigned OpndNum = Opnds.size();
694  unsigned InstrNeeded = OpndNum - 1;
695 
696  // The number of addends in the form of "(-1)*x".
697  unsigned NegOpndNum = 0;
698 
699  // Adjust the number of instructions needed to emit the N-ary add.
700  for (const FAddend *Opnd : Opnds) {
701  if (Opnd->isConstant())
702  continue;
703 
704  // The constant check above is really for a few special constant
705  // coefficients.
706  if (isa<UndefValue>(Opnd->getSymVal()))
707  continue;
708 
709  const FAddendCoef &CE = Opnd->getCoef();
710  if (CE.isMinusOne() || CE.isMinusTwo())
711  NegOpndNum++;
712 
713  // Let the addend be "c * x". If "c == +/-1", the value of the addend
714  // is immediately available; otherwise, it needs exactly one instruction
715  // to evaluate the value.
716  if (!CE.isMinusOne() && !CE.isOne())
717  InstrNeeded++;
718  }
719  return InstrNeeded;
720 }
721 
722 // Input Addend Value NeedNeg(output)
723 // ================================================================
724 // Constant C C false
725 // <+/-1, V> V coefficient is -1
726 // <2/-2, V> "fadd V, V" coefficient is -2
727 // <C, V> "fmul V, C" false
728 //
729 // NOTE: Keep this function in sync with FAddCombine::calcInstrNumber.
730 Value *FAddCombine::createAddendVal(const FAddend &Opnd, bool &NeedNeg) {
731  const FAddendCoef &Coeff = Opnd.getCoef();
732 
733  if (Opnd.isConstant()) {
734  NeedNeg = false;
735  return Coeff.getValue(Instr->getType());
736  }
737 
738  Value *OpndVal = Opnd.getSymVal();
739 
740  if (Coeff.isMinusOne() || Coeff.isOne()) {
741  NeedNeg = Coeff.isMinusOne();
742  return OpndVal;
743  }
744 
745  if (Coeff.isTwo() || Coeff.isMinusTwo()) {
746  NeedNeg = Coeff.isMinusTwo();
747  return createFAdd(OpndVal, OpndVal);
748  }
749 
750  NeedNeg = false;
751  return createFMul(OpndVal, Coeff.getValue(Instr->getType()));
752 }
753 
754 // Checks if any operand is negative and we can convert add to sub.
755 // This function checks for following negative patterns
756 // ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C))
757 // ADD(XOR(AND(Z, C), C), 1) == NEG(OR(Z, ~C))
758 // XOR(AND(Z, C), (C + 1)) == NEG(OR(Z, ~C)) if C is even
761  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
762 
763  // This function creates 2 instructions to replace ADD, we need at least one
764  // of LHS or RHS to have one use to ensure benefit in transform.
765  if (!LHS->hasOneUse() && !RHS->hasOneUse())
766  return nullptr;
767 
768  Value *X = nullptr, *Y = nullptr, *Z = nullptr;
769  const APInt *C1 = nullptr, *C2 = nullptr;
770 
771  // if ONE is on other side, swap
772  if (match(RHS, m_Add(m_Value(X), m_One())))
773  std::swap(LHS, RHS);
774 
775  if (match(LHS, m_Add(m_Value(X), m_One()))) {
776  // if XOR on other side, swap
777  if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
778  std::swap(X, RHS);
779 
780  if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) {
781  // X = XOR(Y, C1), Y = OR(Z, C2), C2 = NOT(C1) ==> X == NOT(AND(Z, C1))
782  // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, AND(Z, C1))
783  if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C2 == ~(*C1))) {
784  Value *NewAnd = Builder.CreateAnd(Z, *C1);
785  return Builder.CreateSub(RHS, NewAnd, "sub");
786  } else if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && (*C1 == *C2)) {
787  // X = XOR(Y, C1), Y = AND(Z, C2), C2 == C1 ==> X == NOT(OR(Z, ~C1))
788  // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, OR(Z, ~C1))
789  Value *NewOr = Builder.CreateOr(Z, ~(*C1));
790  return Builder.CreateSub(RHS, NewOr, "sub");
791  }
792  }
793  }
794 
795  // Restore LHS and RHS
796  LHS = I.getOperand(0);
797  RHS = I.getOperand(1);
798 
799  // if XOR is on other side, swap
800  if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
801  std::swap(LHS, RHS);
802 
803  // C2 is ODD
804  // LHS = XOR(Y, C1), Y = AND(Z, C2), C1 == (C2 + 1) => LHS == NEG(OR(Z, ~C2))
805  // ADD(LHS, RHS) == SUB(RHS, OR(Z, ~C2))
806  if (match(LHS, m_Xor(m_Value(Y), m_APInt(C1))))
807  if (C1->countTrailingZeros() == 0)
808  if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && *C1 == (*C2 + 1)) {
809  Value *NewOr = Builder.CreateOr(Z, ~(*C2));
810  return Builder.CreateSub(RHS, NewOr, "sub");
811  }
812  return nullptr;
813 }
814 
815 /// Wrapping flags may allow combining constants separated by an extend.
818  Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1);
819  Type *Ty = Add.getType();
820  Constant *Op1C;
821  if (!match(Op1, m_Constant(Op1C)))
822  return nullptr;
823 
824  // Try this match first because it results in an add in the narrow type.
825  // (zext (X +nuw C2)) + C1 --> zext (X + (C2 + trunc(C1)))
826  Value *X;
827  const APInt *C1, *C2;
828  if (match(Op1, m_APInt(C1)) &&
829  match(Op0, m_OneUse(m_ZExt(m_NUWAdd(m_Value(X), m_APInt(C2))))) &&
830  C1->isNegative() && C1->sge(-C2->sext(C1->getBitWidth()))) {
831  Constant *NewC =
832  ConstantInt::get(X->getType(), *C2 + C1->trunc(C2->getBitWidth()));
833  return new ZExtInst(Builder.CreateNUWAdd(X, NewC), Ty);
834  }
835 
836  // More general combining of constants in the wide type.
837  // (sext (X +nsw NarrowC)) + C --> (sext X) + (sext(NarrowC) + C)
838  Constant *NarrowC;
839  if (match(Op0, m_OneUse(m_SExt(m_NSWAdd(m_Value(X), m_Constant(NarrowC)))))) {
840  Constant *WideC = ConstantExpr::getSExt(NarrowC, Ty);
841  Constant *NewC = ConstantExpr::getAdd(WideC, Op1C);
842  Value *WideX = Builder.CreateSExt(X, Ty);
843  return BinaryOperator::CreateAdd(WideX, NewC);
844  }
845  // (zext (X +nuw NarrowC)) + C --> (zext X) + (zext(NarrowC) + C)
846  if (match(Op0, m_OneUse(m_ZExt(m_NUWAdd(m_Value(X), m_Constant(NarrowC)))))) {
847  Constant *WideC = ConstantExpr::getZExt(NarrowC, Ty);
848  Constant *NewC = ConstantExpr::getAdd(WideC, Op1C);
849  Value *WideX = Builder.CreateZExt(X, Ty);
850  return BinaryOperator::CreateAdd(WideX, NewC);
851  }
852 
853  return nullptr;
854 }
855 
857  Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1);
858  Constant *Op1C;
859  if (!match(Op1, m_ImmConstant(Op1C)))
860  return nullptr;
861 
862  if (Instruction *NV = foldBinOpIntoSelectOrPhi(Add))
863  return NV;
864 
865  Value *X;
866  Constant *Op00C;
867 
868  // add (sub C1, X), C2 --> sub (add C1, C2), X
869  if (match(Op0, m_Sub(m_Constant(Op00C), m_Value(X))))
870  return BinaryOperator::CreateSub(ConstantExpr::getAdd(Op00C, Op1C), X);
871 
872  Value *Y;
873 
874  // add (sub X, Y), -1 --> add (not Y), X
875  if (match(Op0, m_OneUse(m_Sub(m_Value(X), m_Value(Y)))) &&
876  match(Op1, m_AllOnes()))
877  return BinaryOperator::CreateAdd(Builder.CreateNot(Y), X);
878 
879  // zext(bool) + C -> bool ? C + 1 : C
880  if (match(Op0, m_ZExt(m_Value(X))) &&
881  X->getType()->getScalarSizeInBits() == 1)
882  return SelectInst::Create(X, InstCombiner::AddOne(Op1C), Op1);
883  // sext(bool) + C -> bool ? C - 1 : C
884  if (match(Op0, m_SExt(m_Value(X))) &&
885  X->getType()->getScalarSizeInBits() == 1)
886  return SelectInst::Create(X, InstCombiner::SubOne(Op1C), Op1);
887 
888  // ~X + C --> (C-1) - X
889  if (match(Op0, m_Not(m_Value(X))))
890  return BinaryOperator::CreateSub(InstCombiner::SubOne(Op1C), X);
891 
892  const APInt *C;
893  if (!match(Op1, m_APInt(C)))
894  return nullptr;
895 
896  // (X | Op01C) + Op1C --> X + (Op01C + Op1C) iff the `or` is actually an `add`
897  Constant *Op01C;
898  if (match(Op0, m_Or(m_Value(X), m_ImmConstant(Op01C))) &&
899  haveNoCommonBitsSet(X, Op01C, DL, &AC, &Add, &DT))
900  return BinaryOperator::CreateAdd(X, ConstantExpr::getAdd(Op01C, Op1C));
901 
902  // (X | C2) + C --> (X | C2) ^ C2 iff (C2 == -C)
903  const APInt *C2;
904  if (match(Op0, m_Or(m_Value(), m_APInt(C2))) && *C2 == -*C)
905  return BinaryOperator::CreateXor(Op0, ConstantInt::get(Add.getType(), *C2));
906 
907  if (C->isSignMask()) {
908  // If wrapping is not allowed, then the addition must set the sign bit:
909  // X + (signmask) --> X | signmask
910  if (Add.hasNoSignedWrap() || Add.hasNoUnsignedWrap())
911  return BinaryOperator::CreateOr(Op0, Op1);
912 
913  // If wrapping is allowed, then the addition flips the sign bit of LHS:
914  // X + (signmask) --> X ^ signmask
915  return BinaryOperator::CreateXor(Op0, Op1);
916  }
917 
918  // Is this add the last step in a convoluted sext?
919  // add(zext(xor i16 X, -32768), -32768) --> sext X
920  Type *Ty = Add.getType();
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  // If all bits affected by the add are included in a high-bit-mask, do the
979  // add before the mask op:
980  // (X & 0xFF00) + xx00 --> (X + xx00) & 0xFF00
981  if (match(Op0, m_OneUse(m_And(m_Value(X), m_APInt(C2)))) &&
982  C2->isNegative() && C2->isShiftedMask() && *C == (*C & *C2)) {
983  Value *NewAdd = Builder.CreateAdd(X, ConstantInt::get(Ty, *C));
984  return BinaryOperator::CreateAnd(NewAdd, ConstantInt::get(Ty, *C2));
985  }
986 
987  return nullptr;
988 }
989 
990 // Matches multiplication expression Op * C where C is a constant. Returns the
991 // constant value in C and the other operand in Op. Returns true if such a
992 // match is found.
993 static bool MatchMul(Value *E, Value *&Op, APInt &C) {
994  const APInt *AI;
995  if (match(E, m_Mul(m_Value(Op), m_APInt(AI)))) {
996  C = *AI;
997  return true;
998  }
999  if (match(E, m_Shl(m_Value(Op), m_APInt(AI)))) {
1000  C = APInt(AI->getBitWidth(), 1);
1001  C <<= *AI;
1002  return true;
1003  }
1004  return false;
1005 }
1006 
1007 // Matches remainder expression Op % C where C is a constant. Returns the
1008 // constant value in C and the other operand in Op. Returns the signedness of
1009 // the remainder operation in IsSigned. Returns true if such a match is
1010 // found.
1011 static bool MatchRem(Value *E, Value *&Op, APInt &C, bool &IsSigned) {
1012  const APInt *AI;
1013  IsSigned = false;
1014  if (match(E, m_SRem(m_Value(Op), m_APInt(AI)))) {
1015  IsSigned = true;
1016  C = *AI;
1017  return true;
1018  }
1019  if (match(E, m_URem(m_Value(Op), m_APInt(AI)))) {
1020  C = *AI;
1021  return true;
1022  }
1023  if (match(E, m_And(m_Value(Op), m_APInt(AI))) && (*AI + 1).isPowerOf2()) {
1024  C = *AI + 1;
1025  return true;
1026  }
1027  return false;
1028 }
1029 
1030 // Matches division expression Op / C with the given signedness as indicated
1031 // by IsSigned, where C is a constant. Returns the constant value in C and the
1032 // other operand in Op. Returns true if such a match is found.
1033 static bool MatchDiv(Value *E, Value *&Op, APInt &C, bool IsSigned) {
1034  const APInt *AI;
1035  if (IsSigned && match(E, m_SDiv(m_Value(Op), m_APInt(AI)))) {
1036  C = *AI;
1037  return true;
1038  }
1039  if (!IsSigned) {
1040  if (match(E, m_UDiv(m_Value(Op), m_APInt(AI)))) {
1041  C = *AI;
1042  return true;
1043  }
1044  if (match(E, m_LShr(m_Value(Op), m_APInt(AI)))) {
1045  C = APInt(AI->getBitWidth(), 1);
1046  C <<= *AI;
1047  return true;
1048  }
1049  }
1050  return false;
1051 }
1052 
1053 // Returns whether C0 * C1 with the given signedness overflows.
1054 static bool MulWillOverflow(APInt &C0, APInt &C1, bool IsSigned) {
1055  bool overflow;
1056  if (IsSigned)
1057  (void)C0.smul_ov(C1, overflow);
1058  else
1059  (void)C0.umul_ov(C1, overflow);
1060  return overflow;
1061 }
1062 
1063 // Simplifies X % C0 + (( X / C0 ) % C1) * C0 to X % (C0 * C1), where (C0 * C1)
1064 // does not overflow.
1066  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1067  Value *X, *MulOpV;
1068  APInt C0, MulOpC;
1069  bool IsSigned;
1070  // Match I = X % C0 + MulOpV * C0
1071  if (((MatchRem(LHS, X, C0, IsSigned) && MatchMul(RHS, MulOpV, MulOpC)) ||
1072  (MatchRem(RHS, X, C0, IsSigned) && MatchMul(LHS, MulOpV, MulOpC))) &&
1073  C0 == MulOpC) {
1074  Value *RemOpV;
1075  APInt C1;
1076  bool Rem2IsSigned;
1077  // Match MulOpC = RemOpV % C1
1078  if (MatchRem(MulOpV, RemOpV, C1, Rem2IsSigned) &&
1079  IsSigned == Rem2IsSigned) {
1080  Value *DivOpV;
1081  APInt DivOpC;
1082  // Match RemOpV = X / C0
1083  if (MatchDiv(RemOpV, DivOpV, DivOpC, IsSigned) && X == DivOpV &&
1084  C0 == DivOpC && !MulWillOverflow(C0, C1, IsSigned)) {
1085  Value *NewDivisor = ConstantInt::get(X->getType(), C0 * C1);
1086  return IsSigned ? Builder.CreateSRem(X, NewDivisor, "srem")
1087  : Builder.CreateURem(X, NewDivisor, "urem");
1088  }
1089  }
1090  }
1091 
1092  return nullptr;
1093 }
1094 
1095 /// Fold
1096 /// (1 << NBits) - 1
1097 /// Into:
1098 /// ~(-(1 << NBits))
1099 /// Because a 'not' is better for bit-tracking analysis and other transforms
1100 /// than an 'add'. The new shl is always nsw, and is nuw if old `and` was.
1103  Value *NBits;
1104  if (!match(&I, m_Add(m_OneUse(m_Shl(m_One(), m_Value(NBits))), m_AllOnes())))
1105  return nullptr;
1106 
1107  Constant *MinusOne = Constant::getAllOnesValue(NBits->getType());
1108  Value *NotMask = Builder.CreateShl(MinusOne, NBits, "notmask");
1109  // Be wary of constant folding.
1110  if (auto *BOp = dyn_cast<BinaryOperator>(NotMask)) {
1111  // Always NSW. But NUW propagates from `add`.
1112  BOp->setHasNoSignedWrap();
1113  BOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1114  }
1115 
1116  return BinaryOperator::CreateNot(NotMask, I.getName());
1117 }
1118 
1120  assert(I.getOpcode() == Instruction::Add && "Expecting add instruction");
1121  Type *Ty = I.getType();
1122  auto getUAddSat = [&]() {
1123  return Intrinsic::getDeclaration(I.getModule(), Intrinsic::uadd_sat, Ty);
1124  };
1125 
1126  // add (umin X, ~Y), Y --> uaddsat X, Y
1127  Value *X, *Y;
1128  if (match(&I, m_c_Add(m_c_UMin(m_Value(X), m_Not(m_Value(Y))),
1129  m_Deferred(Y))))
1130  return CallInst::Create(getUAddSat(), { X, Y });
1131 
1132  // add (umin X, ~C), C --> uaddsat X, C
1133  const APInt *C, *NotC;
1134  if (match(&I, m_Add(m_UMin(m_Value(X), m_APInt(NotC)), m_APInt(C))) &&
1135  *C == ~*NotC)
1136  return CallInst::Create(getUAddSat(), { X, ConstantInt::get(Ty, *C) });
1137 
1138  return nullptr;
1139 }
1140 
1143  BinaryOperator &I) {
1144  assert((I.getOpcode() == Instruction::Add ||
1145  I.getOpcode() == Instruction::Or ||
1146  I.getOpcode() == Instruction::Sub) &&
1147  "Expecting add/or/sub instruction");
1148 
1149  // We have a subtraction/addition between a (potentially truncated) *logical*
1150  // right-shift of X and a "select".
1151  Value *X, *Select;
1152  Instruction *LowBitsToSkip, *Extract;
1154  m_LShr(m_Value(X), m_Instruction(LowBitsToSkip)),
1155  m_Instruction(Extract))),
1156  m_Value(Select))))
1157  return nullptr;
1158 
1159  // `add`/`or` is commutative; but for `sub`, "select" *must* be on RHS.
1160  if (I.getOpcode() == Instruction::Sub && I.getOperand(1) != Select)
1161  return nullptr;
1162 
1163  Type *XTy = X->getType();
1164  bool HadTrunc = I.getType() != XTy;
1165 
1166  // If there was a truncation of extracted value, then we'll need to produce
1167  // one extra instruction, so we need to ensure one instruction will go away.
1168  if (HadTrunc && !match(&I, m_c_BinOp(m_OneUse(m_Value()), m_Value())))
1169  return nullptr;
1170 
1171  // Extraction should extract high NBits bits, with shift amount calculated as:
1172  // low bits to skip = shift bitwidth - high bits to extract
1173  // The shift amount itself may be extended, and we need to look past zero-ext
1174  // when matching NBits, that will matter for matching later.
1175  Constant *C;
1176  Value *NBits;
1177  if (!match(
1178  LowBitsToSkip,
1180  !match(C, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ,
1181  APInt(C->getType()->getScalarSizeInBits(),
1182  X->getType()->getScalarSizeInBits()))))
1183  return nullptr;
1184 
1185  // Sign-extending value can be zero-extended if we `sub`tract it,
1186  // or sign-extended otherwise.
1187  auto SkipExtInMagic = [&I](Value *&V) {
1188  if (I.getOpcode() == Instruction::Sub)
1189  match(V, m_ZExtOrSelf(m_Value(V)));
1190  else
1191  match(V, m_SExtOrSelf(m_Value(V)));
1192  };
1193 
1194  // Now, finally validate the sign-extending magic.
1195  // `select` itself may be appropriately extended, look past that.
1196  SkipExtInMagic(Select);
1197 
1198  ICmpInst::Predicate Pred;
1199  const APInt *Thr;
1200  Value *SignExtendingValue, *Zero;
1201  bool ShouldSignext;
1202  // It must be a select between two values we will later establish to be a
1203  // sign-extending value and a zero constant. The condition guarding the
1204  // sign-extension must be based on a sign bit of the same X we had in `lshr`.
1205  if (!match(Select, m_Select(m_ICmp(Pred, m_Specific(X), m_APInt(Thr)),
1206  m_Value(SignExtendingValue), m_Value(Zero))) ||
1207  !isSignBitCheck(Pred, *Thr, ShouldSignext))
1208  return nullptr;
1209 
1210  // icmp-select pair is commutative.
1211  if (!ShouldSignext)
1212  std::swap(SignExtendingValue, Zero);
1213 
1214  // If we should not perform sign-extension then we must add/or/subtract zero.
1215  if (!match(Zero, m_Zero()))
1216  return nullptr;
1217  // Otherwise, it should be some constant, left-shifted by the same NBits we
1218  // had in `lshr`. Said left-shift can also be appropriately extended.
1219  // Again, we must look past zero-ext when looking for NBits.
1220  SkipExtInMagic(SignExtendingValue);
1221  Constant *SignExtendingValueBaseConstant;
1222  if (!match(SignExtendingValue,
1223  m_Shl(m_Constant(SignExtendingValueBaseConstant),
1224  m_ZExtOrSelf(m_Specific(NBits)))))
1225  return nullptr;
1226  // If we `sub`, then the constant should be one, else it should be all-ones.
1227  if (I.getOpcode() == Instruction::Sub
1228  ? !match(SignExtendingValueBaseConstant, m_One())
1229  : !match(SignExtendingValueBaseConstant, m_AllOnes()))
1230  return nullptr;
1231 
1232  auto *NewAShr = BinaryOperator::CreateAShr(X, LowBitsToSkip,
1233  Extract->getName() + ".sext");
1234  NewAShr->copyIRFlags(Extract); // Preserve `exact`-ness.
1235  if (!HadTrunc)
1236  return NewAShr;
1237 
1238  Builder.Insert(NewAShr);
1239  return TruncInst::CreateTruncOrBitCast(NewAShr, I.getType());
1240 }
1241 
1242 /// This is a specialization of a more general transform from
1243 /// SimplifyUsingDistributiveLaws. If that code can be made to work optimally
1244 /// for multi-use cases or propagating nsw/nuw, then we would not need this.
1247  // TODO: Also handle mul by doubling the shift amount?
1248  assert((I.getOpcode() == Instruction::Add ||
1249  I.getOpcode() == Instruction::Sub) &&
1250  "Expected add/sub");
1251  auto *Op0 = dyn_cast<BinaryOperator>(I.getOperand(0));
1252  auto *Op1 = dyn_cast<BinaryOperator>(I.getOperand(1));
1253  if (!Op0 || !Op1 || !(Op0->hasOneUse() || Op1->hasOneUse()))
1254  return nullptr;
1255 
1256  Value *X, *Y, *ShAmt;
1257  if (!match(Op0, m_Shl(m_Value(X), m_Value(ShAmt))) ||
1258  !match(Op1, m_Shl(m_Value(Y), m_Specific(ShAmt))))
1259  return nullptr;
1260 
1261  // No-wrap propagates only when all ops have no-wrap.
1262  bool HasNSW = I.hasNoSignedWrap() && Op0->hasNoSignedWrap() &&
1263  Op1->hasNoSignedWrap();
1264  bool HasNUW = I.hasNoUnsignedWrap() && Op0->hasNoUnsignedWrap() &&
1265  Op1->hasNoUnsignedWrap();
1266 
1267  // add/sub (X << ShAmt), (Y << ShAmt) --> (add/sub X, Y) << ShAmt
1268  Value *NewMath = Builder.CreateBinOp(I.getOpcode(), X, Y);
1269  if (auto *NewI = dyn_cast<BinaryOperator>(NewMath)) {
1270  NewI->setHasNoSignedWrap(HasNSW);
1271  NewI->setHasNoUnsignedWrap(HasNUW);
1272  }
1273  auto *NewShl = BinaryOperator::CreateShl(NewMath, ShAmt);
1274  NewShl->setHasNoSignedWrap(HasNSW);
1275  NewShl->setHasNoUnsignedWrap(HasNUW);
1276  return NewShl;
1277 }
1278 
1280  if (Value *V = SimplifyAddInst(I.getOperand(0), I.getOperand(1),
1281  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
1282  SQ.getWithInstruction(&I)))
1283  return replaceInstUsesWith(I, V);
1284 
1285  if (SimplifyAssociativeOrCommutative(I))
1286  return &I;
1287 
1288  if (Instruction *X = foldVectorBinop(I))
1289  return X;
1290 
1291  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1292  return Phi;
1293 
1294  // (A*B)+(A*C) -> A*(B+C) etc
1295  if (Value *V = SimplifyUsingDistributiveLaws(I))
1296  return replaceInstUsesWith(I, V);
1297 
1299  return R;
1300 
1301  if (Instruction *X = foldAddWithConstant(I))
1302  return X;
1303 
1304  if (Instruction *X = foldNoWrapAdd(I, Builder))
1305  return X;
1306 
1307  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1308  Type *Ty = I.getType();
1309  if (Ty->isIntOrIntVectorTy(1))
1310  return BinaryOperator::CreateXor(LHS, RHS);
1311 
1312  // X + X --> X << 1
1313  if (LHS == RHS) {
1314  auto *Shl = BinaryOperator::CreateShl(LHS, ConstantInt::get(Ty, 1));
1315  Shl->setHasNoSignedWrap(I.hasNoSignedWrap());
1316  Shl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1317  return Shl;
1318  }
1319 
1320  Value *A, *B;
1321  if (match(LHS, m_Neg(m_Value(A)))) {
1322  // -A + -B --> -(A + B)
1323  if (match(RHS, m_Neg(m_Value(B))))
1324  return BinaryOperator::CreateNeg(Builder.CreateAdd(A, B));
1325 
1326  // -A + B --> B - A
1327  return BinaryOperator::CreateSub(RHS, A);
1328  }
1329 
1330  // A + -B --> A - B
1331  if (match(RHS, m_Neg(m_Value(B))))
1332  return BinaryOperator::CreateSub(LHS, B);
1333 
1335  return replaceInstUsesWith(I, V);
1336 
1337  // (A + 1) + ~B --> A - B
1338  // ~B + (A + 1) --> A - B
1339  // (~B + A) + 1 --> A - B
1340  // (A + ~B) + 1 --> A - B
1341  if (match(&I, m_c_BinOp(m_Add(m_Value(A), m_One()), m_Not(m_Value(B)))) ||
1342  match(&I, m_BinOp(m_c_Add(m_Not(m_Value(B)), m_Value(A)), m_One())))
1343  return BinaryOperator::CreateSub(A, B);
1344 
1345  // (A + RHS) + RHS --> A + (RHS << 1)
1347  return BinaryOperator::CreateAdd(A, Builder.CreateShl(RHS, 1, "reass.add"));
1348 
1349  // LHS + (A + LHS) --> A + (LHS << 1)
1351  return BinaryOperator::CreateAdd(A, Builder.CreateShl(LHS, 1, "reass.add"));
1352 
1353  {
1354  // (A + C1) + (C2 - B) --> (A - B) + (C1 + C2)
1355  Constant *C1, *C2;
1356  if (match(&I, m_c_Add(m_Add(m_Value(A), m_ImmConstant(C1)),
1357  m_Sub(m_ImmConstant(C2), m_Value(B)))) &&
1358  (LHS->hasOneUse() || RHS->hasOneUse())) {
1359  Value *Sub = Builder.CreateSub(A, B);
1361  }
1362  }
1363 
1364  // X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1)
1365  if (Value *V = SimplifyAddWithRemainder(I)) return replaceInstUsesWith(I, V);
1366 
1367  // ((X s/ C1) << C2) + X => X s% -C1 where -C1 is 1 << C2
1368  const APInt *C1, *C2;
1369  if (match(LHS, m_Shl(m_SDiv(m_Specific(RHS), m_APInt(C1)), m_APInt(C2)))) {
1370  APInt one(C2->getBitWidth(), 1);
1371  APInt minusC1 = -(*C1);
1372  if (minusC1 == (one << *C2)) {
1373  Constant *NewRHS = ConstantInt::get(RHS->getType(), minusC1);
1374  return BinaryOperator::CreateSRem(RHS, NewRHS);
1375  }
1376  }
1377 
1378  // A+B --> A|B iff A and B have no bits set in common.
1379  if (haveNoCommonBitsSet(LHS, RHS, DL, &AC, &I, &DT))
1380  return BinaryOperator::CreateOr(LHS, RHS);
1381 
1382  // add (select X 0 (sub n A)) A --> select X A n
1383  {
1384  SelectInst *SI = dyn_cast<SelectInst>(LHS);
1385  Value *A = RHS;
1386  if (!SI) {
1387  SI = dyn_cast<SelectInst>(RHS);
1388  A = LHS;
1389  }
1390  if (SI && SI->hasOneUse()) {
1391  Value *TV = SI->getTrueValue();
1392  Value *FV = SI->getFalseValue();
1393  Value *N;
1394 
1395  // Can we fold the add into the argument of the select?
1396  // We check both true and false select arguments for a matching subtract.
1397  if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A))))
1398  // Fold the add into the true select value.
1399  return SelectInst::Create(SI->getCondition(), N, A);
1400 
1401  if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A))))
1402  // Fold the add into the false select value.
1403  return SelectInst::Create(SI->getCondition(), A, N);
1404  }
1405  }
1406 
1407  if (Instruction *Ext = narrowMathIfNoOverflow(I))
1408  return Ext;
1409 
1410  // (add (xor A, B) (and A, B)) --> (or A, B)
1411  // (add (and A, B) (xor A, B)) --> (or A, B)
1412  if (match(&I, m_c_BinOp(m_Xor(m_Value(A), m_Value(B)),
1413  m_c_And(m_Deferred(A), m_Deferred(B)))))
1414  return BinaryOperator::CreateOr(A, B);
1415 
1416  // (add (or A, B) (and A, B)) --> (add A, B)
1417  // (add (and A, B) (or A, B)) --> (add A, B)
1418  if (match(&I, m_c_BinOp(m_Or(m_Value(A), m_Value(B)),
1419  m_c_And(m_Deferred(A), m_Deferred(B))))) {
1420  // Replacing operands in-place to preserve nuw/nsw flags.
1421  replaceOperand(I, 0, A);
1422  replaceOperand(I, 1, B);
1423  return &I;
1424  }
1425 
1426  // TODO(jingyue): Consider willNotOverflowSignedAdd and
1427  // willNotOverflowUnsignedAdd to reduce the number of invocations of
1428  // computeKnownBits.
1429  bool Changed = false;
1430  if (!I.hasNoSignedWrap() && willNotOverflowSignedAdd(LHS, RHS, I)) {
1431  Changed = true;
1432  I.setHasNoSignedWrap(true);
1433  }
1434  if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedAdd(LHS, RHS, I)) {
1435  Changed = true;
1436  I.setHasNoUnsignedWrap(true);
1437  }
1438 
1440  return V;
1441 
1442  if (Instruction *V =
1443  canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
1444  return V;
1445 
1446  if (Instruction *SatAdd = foldToUnsignedSaturatedAdd(I))
1447  return SatAdd;
1448 
1449  // usub.sat(A, B) + B => umax(A, B)
1450  if (match(&I, m_c_BinOp(
1451  m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Value(A), m_Value(B))),
1452  m_Deferred(B)))) {
1453  return replaceInstUsesWith(I,
1454  Builder.CreateIntrinsic(Intrinsic::umax, {I.getType()}, {A, B}));
1455  }
1456 
1457  // ctpop(A) + ctpop(B) => ctpop(A | B) if A and B have no bits set in common.
1458  if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(A)))) &&
1459  match(RHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(B)))) &&
1460  haveNoCommonBitsSet(A, B, DL, &AC, &I, &DT))
1461  return replaceInstUsesWith(
1462  I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
1463  {Builder.CreateOr(A, B)}));
1464 
1465  return Changed ? &I : nullptr;
1466 }
1467 
1468 /// Eliminate an op from a linear interpolation (lerp) pattern.
1471  Value *X, *Y, *Z;
1474  m_Value(Z))))),
1476  return nullptr;
1477 
1478  // (Y * (1.0 - Z)) + (X * Z) --> Y + Z * (X - Y) [8 commuted variants]
1479  Value *XY = Builder.CreateFSubFMF(X, Y, &I);
1480  Value *MulZ = Builder.CreateFMulFMF(Z, XY, &I);
1481  return BinaryOperator::CreateFAddFMF(Y, MulZ, &I);
1482 }
1483 
1484 /// Factor a common operand out of fadd/fsub of fmul/fdiv.
1487  assert((I.getOpcode() == Instruction::FAdd ||
1488  I.getOpcode() == Instruction::FSub) && "Expecting fadd/fsub");
1489  assert(I.hasAllowReassoc() && I.hasNoSignedZeros() &&
1490  "FP factorization requires FMF");
1491 
1492  if (Instruction *Lerp = factorizeLerp(I, Builder))
1493  return Lerp;
1494 
1495  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1496  if (!Op0->hasOneUse() || !Op1->hasOneUse())
1497  return nullptr;
1498 
1499  Value *X, *Y, *Z;
1500  bool IsFMul;
1501  if ((match(Op0, m_FMul(m_Value(X), m_Value(Z))) &&
1502  match(Op1, m_c_FMul(m_Value(Y), m_Specific(Z)))) ||
1503  (match(Op0, m_FMul(m_Value(Z), m_Value(X))) &&
1504  match(Op1, m_c_FMul(m_Value(Y), m_Specific(Z)))))
1505  IsFMul = true;
1506  else if (match(Op0, m_FDiv(m_Value(X), m_Value(Z))) &&
1507  match(Op1, m_FDiv(m_Value(Y), m_Specific(Z))))
1508  IsFMul = false;
1509  else
1510  return nullptr;
1511 
1512  // (X * Z) + (Y * Z) --> (X + Y) * Z
1513  // (X * Z) - (Y * Z) --> (X - Y) * Z
1514  // (X / Z) + (Y / Z) --> (X + Y) / Z
1515  // (X / Z) - (Y / Z) --> (X - Y) / Z
1516  bool IsFAdd = I.getOpcode() == Instruction::FAdd;
1517  Value *XY = IsFAdd ? Builder.CreateFAddFMF(X, Y, &I)
1518  : Builder.CreateFSubFMF(X, Y, &I);
1519 
1520  // Bail out if we just created a denormal constant.
1521  // TODO: This is copied from a previous implementation. Is it necessary?
1522  const APFloat *C;
1523  if (match(XY, m_APFloat(C)) && !C->isNormal())
1524  return nullptr;
1525 
1526  return IsFMul ? BinaryOperator::CreateFMulFMF(XY, Z, &I)
1527  : BinaryOperator::CreateFDivFMF(XY, Z, &I);
1528 }
1529 
1531  if (Value *V = SimplifyFAddInst(I.getOperand(0), I.getOperand(1),
1532  I.getFastMathFlags(),
1533  SQ.getWithInstruction(&I)))
1534  return replaceInstUsesWith(I, V);
1535 
1536  if (SimplifyAssociativeOrCommutative(I))
1537  return &I;
1538 
1539  if (Instruction *X = foldVectorBinop(I))
1540  return X;
1541 
1542  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1543  return Phi;
1544 
1545  if (Instruction *FoldedFAdd = foldBinOpIntoSelectOrPhi(I))
1546  return FoldedFAdd;
1547 
1548  // (-X) + Y --> Y - X
1549  Value *X, *Y;
1550  if (match(&I, m_c_FAdd(m_FNeg(m_Value(X)), m_Value(Y))))
1551  return BinaryOperator::CreateFSubFMF(Y, X, &I);
1552 
1553  // Similar to above, but look through fmul/fdiv for the negated term.
1554  // (-X * Y) + Z --> Z - (X * Y) [4 commuted variants]
1555  Value *Z;
1557  m_Value(Z)))) {
1558  Value *XY = Builder.CreateFMulFMF(X, Y, &I);
1559  return BinaryOperator::CreateFSubFMF(Z, XY, &I);
1560  }
1561  // (-X / Y) + Z --> Z - (X / Y) [2 commuted variants]
1562  // (X / -Y) + Z --> Z - (X / Y) [2 commuted variants]
1564  m_Value(Z))) ||
1566  m_Value(Z)))) {
1567  Value *XY = Builder.CreateFDivFMF(X, Y, &I);
1568  return BinaryOperator::CreateFSubFMF(Z, XY, &I);
1569  }
1570 
1571  // Check for (fadd double (sitofp x), y), see if we can merge this into an
1572  // integer add followed by a promotion.
1573  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1574  if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) {
1575  Value *LHSIntVal = LHSConv->getOperand(0);
1576  Type *FPType = LHSConv->getType();
1577 
1578  // TODO: This check is overly conservative. In many cases known bits
1579  // analysis can tell us that the result of the addition has less significant
1580  // bits than the integer type can hold.
1581  auto IsValidPromotion = [](Type *FTy, Type *ITy) {
1582  Type *FScalarTy = FTy->getScalarType();
1583  Type *IScalarTy = ITy->getScalarType();
1584 
1585  // Do we have enough bits in the significand to represent the result of
1586  // the integer addition?
1587  unsigned MaxRepresentableBits =
1589  return IScalarTy->getIntegerBitWidth() <= MaxRepresentableBits;
1590  };
1591 
1592  // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst))
1593  // ... if the constant fits in the integer value. This is useful for things
1594  // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer
1595  // requires a constant pool load, and generally allows the add to be better
1596  // instcombined.
1597  if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS))
1598  if (IsValidPromotion(FPType, LHSIntVal->getType())) {
1599  Constant *CI =
1600  ConstantExpr::getFPToSI(CFP, LHSIntVal->getType());
1601  if (LHSConv->hasOneUse() &&
1602  ConstantExpr::getSIToFP(CI, I.getType()) == CFP &&
1603  willNotOverflowSignedAdd(LHSIntVal, CI, I)) {
1604  // Insert the new integer add.
1605  Value *NewAdd = Builder.CreateNSWAdd(LHSIntVal, CI, "addconv");
1606  return new SIToFPInst(NewAdd, I.getType());
1607  }
1608  }
1609 
1610  // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y))
1611  if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) {
1612  Value *RHSIntVal = RHSConv->getOperand(0);
1613  // It's enough to check LHS types only because we require int types to
1614  // be the same for this transform.
1615  if (IsValidPromotion(FPType, LHSIntVal->getType())) {
1616  // Only do this if x/y have the same type, if at least one of them has a
1617  // single use (so we don't increase the number of int->fp conversions),
1618  // and if the integer add will not overflow.
1619  if (LHSIntVal->getType() == RHSIntVal->getType() &&
1620  (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
1621  willNotOverflowSignedAdd(LHSIntVal, RHSIntVal, I)) {
1622  // Insert the new integer add.
1623  Value *NewAdd = Builder.CreateNSWAdd(LHSIntVal, RHSIntVal, "addconv");
1624  return new SIToFPInst(NewAdd, I.getType());
1625  }
1626  }
1627  }
1628  }
1629 
1630  // Handle specials cases for FAdd with selects feeding the operation
1631  if (Value *V = SimplifySelectsFeedingBinaryOp(I, LHS, RHS))
1632  return replaceInstUsesWith(I, V);
1633 
1634  if (I.hasAllowReassoc() && I.hasNoSignedZeros()) {
1636  return F;
1637 
1638  // Try to fold fadd into start value of reduction intrinsic.
1639  if (match(&I, m_c_FAdd(m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(
1640  m_AnyZeroFP(), m_Value(X))),
1641  m_Value(Y)))) {
1642  // fadd (rdx 0.0, X), Y --> rdx Y, X
1643  return replaceInstUsesWith(
1644  I, Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,
1645  {X->getType()}, {Y, X}, &I));
1646  }
1647  const APFloat *StartC, *C;
1648  if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(
1649  m_APFloat(StartC), m_Value(X)))) &&
1650  match(RHS, m_APFloat(C))) {
1651  // fadd (rdx StartC, X), C --> rdx (C + StartC), X
1652  Constant *NewStartC = ConstantFP::get(I.getType(), *C + *StartC);
1653  return replaceInstUsesWith(
1654  I, Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,
1655  {X->getType()}, {NewStartC, X}, &I));
1656  }
1657 
1658  // (X * MulC) + X --> X * (MulC + 1.0)
1659  Constant *MulC;
1660  if (match(&I, m_c_FAdd(m_FMul(m_Value(X), m_ImmConstant(MulC)),
1661  m_Deferred(X)))) {
1662  MulC = ConstantExpr::getFAdd(MulC, ConstantFP::get(I.getType(), 1.0));
1663  return BinaryOperator::CreateFMulFMF(X, MulC, &I);
1664  }
1665 
1666  if (Value *V = FAddCombine(Builder).simplify(&I))
1667  return replaceInstUsesWith(I, V);
1668  }
1669 
1670  return nullptr;
1671 }
1672 
1673 /// Optimize pointer differences into the same array into a size. Consider:
1674 /// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer
1675 /// operands to the ptrtoint instructions for the LHS/RHS of the subtract.
1677  Type *Ty, bool IsNUW) {
1678  // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize
1679  // this.
1680  bool Swapped = false;
1681  GEPOperator *GEP1 = nullptr, *GEP2 = nullptr;
1682  if (!isa<GEPOperator>(LHS) && isa<GEPOperator>(RHS)) {
1683  std::swap(LHS, RHS);
1684  Swapped = true;
1685  }
1686 
1687  // Require at least one GEP with a common base pointer on both sides.
1688  if (auto *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
1689  // (gep X, ...) - X
1690  if (LHSGEP->getOperand(0) == RHS) {
1691  GEP1 = LHSGEP;
1692  } else if (auto *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
1693  // (gep X, ...) - (gep X, ...)
1694  if (LHSGEP->getOperand(0)->stripPointerCasts() ==
1695  RHSGEP->getOperand(0)->stripPointerCasts()) {
1696  GEP1 = LHSGEP;
1697  GEP2 = RHSGEP;
1698  }
1699  }
1700  }
1701 
1702  if (!GEP1)
1703  return nullptr;
1704 
1705  if (GEP2) {
1706  // (gep X, ...) - (gep X, ...)
1707  //
1708  // Avoid duplicating the arithmetic if there are more than one non-constant
1709  // indices between the two GEPs and either GEP has a non-constant index and
1710  // multiple users. If zero non-constant index, the result is a constant and
1711  // there is no duplication. If one non-constant index, the result is an add
1712  // or sub with a constant, which is no larger than the original code, and
1713  // there's no duplicated arithmetic, even if either GEP has multiple
1714  // users. If more than one non-constant indices combined, as long as the GEP
1715  // with at least one non-constant index doesn't have multiple users, there
1716  // is no duplication.
1717  unsigned NumNonConstantIndices1 = GEP1->countNonConstantIndices();
1718  unsigned NumNonConstantIndices2 = GEP2->countNonConstantIndices();
1719  if (NumNonConstantIndices1 + NumNonConstantIndices2 > 1 &&
1720  ((NumNonConstantIndices1 > 0 && !GEP1->hasOneUse()) ||
1721  (NumNonConstantIndices2 > 0 && !GEP2->hasOneUse()))) {
1722  return nullptr;
1723  }
1724  }
1725 
1726  // Emit the offset of the GEP and an intptr_t.
1727  Value *Result = EmitGEPOffset(GEP1);
1728 
1729  // If this is a single inbounds GEP and the original sub was nuw,
1730  // then the final multiplication is also nuw.
1731  if (auto *I = dyn_cast<Instruction>(Result))
1732  if (IsNUW && !GEP2 && !Swapped && GEP1->isInBounds() &&
1733  I->getOpcode() == Instruction::Mul)
1734  I->setHasNoUnsignedWrap();
1735 
1736  // If we have a 2nd GEP of the same base pointer, subtract the offsets.
1737  // If both GEPs are inbounds, then the subtract does not have signed overflow.
1738  if (GEP2) {
1739  Value *Offset = EmitGEPOffset(GEP2);
1740  Result = Builder.CreateSub(Result, Offset, "gepdiff", /* NUW */ false,
1741  GEP1->isInBounds() && GEP2->isInBounds());
1742  }
1743 
1744  // If we have p - gep(p, ...) then we have to negate the result.
1745  if (Swapped)
1746  Result = Builder.CreateNeg(Result, "diff.neg");
1747 
1748  return Builder.CreateIntCast(Result, Ty, true);
1749 }
1750 
1752  if (Value *V = SimplifySubInst(I.getOperand(0), I.getOperand(1),
1753  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
1754  SQ.getWithInstruction(&I)))
1755  return replaceInstUsesWith(I, V);
1756 
1757  if (Instruction *X = foldVectorBinop(I))
1758  return X;
1759 
1760  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1761  return Phi;
1762 
1763  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1764 
1765  // If this is a 'B = x-(-A)', change to B = x+A.
1766  // We deal with this without involving Negator to preserve NSW flag.
1767  if (Value *V = dyn_castNegVal(Op1)) {
1769 
1770  if (const auto *BO = dyn_cast<BinaryOperator>(Op1)) {
1771  assert(BO->getOpcode() == Instruction::Sub &&
1772  "Expected a subtraction operator!");
1773  if (BO->hasNoSignedWrap() && I.hasNoSignedWrap())
1774  Res->setHasNoSignedWrap(true);
1775  } else {
1776  if (cast<Constant>(Op1)->isNotMinSignedValue() && I.hasNoSignedWrap())
1777  Res->setHasNoSignedWrap(true);
1778  }
1779 
1780  return Res;
1781  }
1782 
1783  // Try this before Negator to preserve NSW flag.
1785  return R;
1786 
1787  Constant *C;
1788  if (match(Op0, m_ImmConstant(C))) {
1789  Value *X;
1790  Constant *C2;
1791 
1792  // C-(X+C2) --> (C-C2)-X
1793  if (match(Op1, m_Add(m_Value(X), m_ImmConstant(C2))))
1794  return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
1795  }
1796 
1797  auto TryToNarrowDeduceFlags = [this, &I, &Op0, &Op1]() -> Instruction * {
1798  if (Instruction *Ext = narrowMathIfNoOverflow(I))
1799  return Ext;
1800 
1801  bool Changed = false;
1802  if (!I.hasNoSignedWrap() && willNotOverflowSignedSub(Op0, Op1, I)) {
1803  Changed = true;
1804  I.setHasNoSignedWrap(true);
1805  }
1806  if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedSub(Op0, Op1, I)) {
1807  Changed = true;
1808  I.setHasNoUnsignedWrap(true);
1809  }
1810 
1811  return Changed ? &I : nullptr;
1812  };
1813 
1814  // First, let's try to interpret `sub a, b` as `add a, (sub 0, b)`,
1815  // and let's try to sink `(sub 0, b)` into `b` itself. But only if this isn't
1816  // a pure negation used by a select that looks like abs/nabs.
1817  bool IsNegation = match(Op0, m_ZeroInt());
1818  if (!IsNegation || none_of(I.users(), [&I, Op1](const User *U) {
1819  const Instruction *UI = dyn_cast<Instruction>(U);
1820  if (!UI)
1821  return false;
1822  return match(UI,
1823  m_Select(m_Value(), m_Specific(Op1), m_Specific(&I))) ||
1824  match(UI, m_Select(m_Value(), m_Specific(&I), m_Specific(Op1)));
1825  })) {
1826  if (Value *NegOp1 = Negator::Negate(IsNegation, Op1, *this))
1827  return BinaryOperator::CreateAdd(NegOp1, Op0);
1828  }
1829  if (IsNegation)
1830  return TryToNarrowDeduceFlags(); // Should have been handled in Negator!
1831 
1832  // (A*B)-(A*C) -> A*(B-C) etc
1833  if (Value *V = SimplifyUsingDistributiveLaws(I))
1834  return replaceInstUsesWith(I, V);
1835 
1836  if (I.getType()->isIntOrIntVectorTy(1))
1837  return BinaryOperator::CreateXor(Op0, Op1);
1838 
1839  // Replace (-1 - A) with (~A).
1840  if (match(Op0, m_AllOnes()))
1841  return BinaryOperator::CreateNot(Op1);
1842 
1843  // (X + -1) - Y --> ~Y + X
1844  Value *X, *Y;
1845  if (match(Op0, m_OneUse(m_Add(m_Value(X), m_AllOnes()))))
1846  return BinaryOperator::CreateAdd(Builder.CreateNot(Op1), X);
1847 
1848  // Reassociate sub/add sequences to create more add instructions and
1849  // reduce dependency chains:
1850  // ((X - Y) + Z) - Op1 --> (X + Z) - (Y + Op1)
1851  Value *Z;
1853  m_Value(Z))))) {
1854  Value *XZ = Builder.CreateAdd(X, Z);
1855  Value *YW = Builder.CreateAdd(Y, Op1);
1856  return BinaryOperator::CreateSub(XZ, YW);
1857  }
1858 
1859  // ((X - Y) - Op1) --> X - (Y + Op1)
1860  if (match(Op0, m_OneUse(m_Sub(m_Value(X), m_Value(Y))))) {
1861  Value *Add = Builder.CreateAdd(Y, Op1);
1862  return BinaryOperator::CreateSub(X, Add);
1863  }
1864 
1865  // (~X) - (~Y) --> Y - X
1866  // This is placed after the other reassociations and explicitly excludes a
1867  // sub-of-sub pattern to avoid infinite looping.
1868  if (isFreeToInvert(Op0, Op0->hasOneUse()) &&
1869  isFreeToInvert(Op1, Op1->hasOneUse()) &&
1870  !match(Op0, m_Sub(m_ImmConstant(), m_Value()))) {
1871  Value *NotOp0 = Builder.CreateNot(Op0);
1872  Value *NotOp1 = Builder.CreateNot(Op1);
1873  return BinaryOperator::CreateSub(NotOp1, NotOp0);
1874  }
1875 
1876  auto m_AddRdx = [](Value *&Vec) {
1877  return m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_add>(m_Value(Vec)));
1878  };
1879  Value *V0, *V1;
1880  if (match(Op0, m_AddRdx(V0)) && match(Op1, m_AddRdx(V1)) &&
1881  V0->getType() == V1->getType()) {
1882  // Difference of sums is sum of differences:
1883  // add_rdx(V0) - add_rdx(V1) --> add_rdx(V0 - V1)
1884  Value *Sub = Builder.CreateSub(V0, V1);
1885  Value *Rdx = Builder.CreateIntrinsic(Intrinsic::vector_reduce_add,
1886  {Sub->getType()}, {Sub});
1887  return replaceInstUsesWith(I, Rdx);
1888  }
1889 
1890  if (Constant *C = dyn_cast<Constant>(Op0)) {
1891  Value *X;
1892  if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
1893  // C - (zext bool) --> bool ? C - 1 : C
1895  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
1896  // C - (sext bool) --> bool ? C + 1 : C
1898 
1899  // C - ~X == X + (1+C)
1900  if (match(Op1, m_Not(m_Value(X))))
1902 
1903  // Try to fold constant sub into select arguments.
1904  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1905  if (Instruction *R = FoldOpIntoSelect(I, SI))
1906  return R;
1907 
1908  // Try to fold constant sub into PHI values.
1909  if (PHINode *PN = dyn_cast<PHINode>(Op1))
1910  if (Instruction *R = foldOpIntoPhi(I, PN))
1911  return R;
1912 
1913  Constant *C2;
1914 
1915  // C-(C2-X) --> X+(C-C2)
1916  if (match(Op1, m_Sub(m_ImmConstant(C2), m_Value(X))))
1918  }
1919 
1920  const APInt *Op0C;
1921  if (match(Op0, m_APInt(Op0C)) && Op0C->isMask()) {
1922  // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known
1923  // zero.
1924  KnownBits RHSKnown = computeKnownBits(Op1, 0, &I);
1925  if ((*Op0C | RHSKnown.Zero).isAllOnes())
1926  return BinaryOperator::CreateXor(Op1, Op0);
1927  }
1928 
1929  {
1930  Value *Y;
1931  // X-(X+Y) == -Y X-(Y+X) == -Y
1932  if (match(Op1, m_c_Add(m_Specific(Op0), m_Value(Y))))
1933  return BinaryOperator::CreateNeg(Y);
1934 
1935  // (X-Y)-X == -Y
1936  if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))
1937  return BinaryOperator::CreateNeg(Y);
1938  }
1939 
1940  // (sub (or A, B) (and A, B)) --> (xor A, B)
1941  {
1942  Value *A, *B;
1943  if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
1944  match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
1945  return BinaryOperator::CreateXor(A, B);
1946  }
1947 
1948  // (sub (add A, B) (or A, B)) --> (and A, B)
1949  {
1950  Value *A, *B;
1951  if (match(Op0, m_Add(m_Value(A), m_Value(B))) &&
1952  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
1953  return BinaryOperator::CreateAnd(A, B);
1954  }
1955 
1956  // (sub (add A, B) (and A, B)) --> (or A, B)
1957  {
1958  Value *A, *B;
1959  if (match(Op0, m_Add(m_Value(A), m_Value(B))) &&
1960  match(Op1, m_c_And(m_Specific(A), m_Specific(B))))
1961  return BinaryOperator::CreateOr(A, B);
1962  }
1963 
1964  // (sub (and A, B) (or A, B)) --> neg (xor A, B)
1965  {
1966  Value *A, *B;
1967  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1968  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))) &&
1969  (Op0->hasOneUse() || Op1->hasOneUse()))
1970  return BinaryOperator::CreateNeg(Builder.CreateXor(A, B));
1971  }
1972 
1973  // (sub (or A, B), (xor A, B)) --> (and A, B)
1974  {
1975  Value *A, *B;
1976  if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
1977  match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
1978  return BinaryOperator::CreateAnd(A, B);
1979  }
1980 
1981  // (sub (xor A, B) (or A, B)) --> neg (and A, B)
1982  {
1983  Value *A, *B;
1984  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
1985  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))) &&
1986  (Op0->hasOneUse() || Op1->hasOneUse()))
1987  return BinaryOperator::CreateNeg(Builder.CreateAnd(A, B));
1988  }
1989 
1990  {
1991  Value *Y;
1992  // ((X | Y) - X) --> (~X & Y)
1993  if (match(Op0, m_OneUse(m_c_Or(m_Value(Y), m_Specific(Op1)))))
1994  return BinaryOperator::CreateAnd(
1995  Y, Builder.CreateNot(Op1, Op1->getName() + ".not"));
1996  }
1997 
1998  {
1999  // (sub (and Op1, (neg X)), Op1) --> neg (and Op1, (add X, -1))
2000  Value *X;
2001  if (match(Op0, m_OneUse(m_c_And(m_Specific(Op1),
2002  m_OneUse(m_Neg(m_Value(X))))))) {
2003  return BinaryOperator::CreateNeg(Builder.CreateAnd(
2004  Op1, Builder.CreateAdd(X, Constant::getAllOnesValue(I.getType()))));
2005  }
2006  }
2007 
2008  {
2009  // (sub (and Op1, C), Op1) --> neg (and Op1, ~C)
2010  Constant *C;
2011  if (match(Op0, m_OneUse(m_And(m_Specific(Op1), m_Constant(C))))) {
2013  Builder.CreateAnd(Op1, Builder.CreateNot(C)));
2014  }
2015  }
2016 
2017  {
2018  // If we have a subtraction between some value and a select between
2019  // said value and something else, sink subtraction into select hands, i.e.:
2020  // sub (select %Cond, %TrueVal, %FalseVal), %Op1
2021  // ->
2022  // select %Cond, (sub %TrueVal, %Op1), (sub %FalseVal, %Op1)
2023  // or
2024  // sub %Op0, (select %Cond, %TrueVal, %FalseVal)
2025  // ->
2026  // select %Cond, (sub %Op0, %TrueVal), (sub %Op0, %FalseVal)
2027  // This will result in select between new subtraction and 0.
2028  auto SinkSubIntoSelect =
2029  [Ty = I.getType()](Value *Select, Value *OtherHandOfSub,
2030  auto SubBuilder) -> Instruction * {
2031  Value *Cond, *TrueVal, *FalseVal;
2033  m_Value(FalseVal)))))
2034  return nullptr;
2035  if (OtherHandOfSub != TrueVal && OtherHandOfSub != FalseVal)
2036  return nullptr;
2037  // While it is really tempting to just create two subtractions and let
2038  // InstCombine fold one of those to 0, it isn't possible to do so
2039  // because of worklist visitation order. So ugly it is.
2040  bool OtherHandOfSubIsTrueVal = OtherHandOfSub == TrueVal;
2041  Value *NewSub = SubBuilder(OtherHandOfSubIsTrueVal ? FalseVal : TrueVal);
2042  Constant *Zero = Constant::getNullValue(Ty);
2043  SelectInst *NewSel =
2044  SelectInst::Create(Cond, OtherHandOfSubIsTrueVal ? Zero : NewSub,
2045  OtherHandOfSubIsTrueVal ? NewSub : Zero);
2046  // Preserve prof metadata if any.
2047  NewSel->copyMetadata(cast<Instruction>(*Select));
2048  return NewSel;
2049  };
2050  if (Instruction *NewSel = SinkSubIntoSelect(
2051  /*Select=*/Op0, /*OtherHandOfSub=*/Op1,
2052  [Builder = &Builder, Op1](Value *OtherHandOfSelect) {
2053  return Builder->CreateSub(OtherHandOfSelect,
2054  /*OtherHandOfSub=*/Op1);
2055  }))
2056  return NewSel;
2057  if (Instruction *NewSel = SinkSubIntoSelect(
2058  /*Select=*/Op1, /*OtherHandOfSub=*/Op0,
2059  [Builder = &Builder, Op0](Value *OtherHandOfSelect) {
2060  return Builder->CreateSub(/*OtherHandOfSub=*/Op0,
2061  OtherHandOfSelect);
2062  }))
2063  return NewSel;
2064  }
2065 
2066  // (X - (X & Y)) --> (X & ~Y)
2067  if (match(Op1, m_c_And(m_Specific(Op0), m_Value(Y))) &&
2068  (Op1->hasOneUse() || isa<Constant>(Y)))
2069  return BinaryOperator::CreateAnd(
2070  Op0, Builder.CreateNot(Y, Y->getName() + ".not"));
2071 
2072  // ~X - Min/Max(~X, Y) -> ~Min/Max(X, ~Y) - X
2073  // ~X - Min/Max(Y, ~X) -> ~Min/Max(X, ~Y) - X
2074  // Min/Max(~X, Y) - ~X -> X - ~Min/Max(X, ~Y)
2075  // Min/Max(Y, ~X) - ~X -> X - ~Min/Max(X, ~Y)
2076  // As long as Y is freely invertible, this will be neutral or a win.
2077  // Note: We don't generate the inverse max/min, just create the 'not' of
2078  // it and let other folds do the rest.
2079  if (match(Op0, m_Not(m_Value(X))) &&
2080  match(Op1, m_c_MaxOrMin(m_Specific(Op0), m_Value(Y))) &&
2081  !Op0->hasNUsesOrMore(3) && isFreeToInvert(Y, Y->hasOneUse())) {
2082  Value *Not = Builder.CreateNot(Op1);
2083  return BinaryOperator::CreateSub(Not, X);
2084  }
2085  if (match(Op1, m_Not(m_Value(X))) &&
2086  match(Op0, m_c_MaxOrMin(m_Specific(Op1), m_Value(Y))) &&
2087  !Op1->hasNUsesOrMore(3) && isFreeToInvert(Y, Y->hasOneUse())) {
2088  Value *Not = Builder.CreateNot(Op0);
2089  return BinaryOperator::CreateSub(X, Not);
2090  }
2091 
2092  // TODO: This is the same logic as above but handles the cmp-select idioms
2093  // for min/max, so the use checks are increased to account for the
2094  // extra instructions. If we canonicalize to intrinsics, this block
2095  // can likely be removed.
2096  {
2097  Value *LHS, *RHS, *A;
2098  Value *NotA = Op0, *MinMax = Op1;
2100  if (!SelectPatternResult::isMinOrMax(SPF)) {
2101  NotA = Op1;
2102  MinMax = Op0;
2104  }
2106  match(NotA, m_Not(m_Value(A))) && (NotA == LHS || NotA == RHS)) {
2107  if (NotA == LHS)
2108  std::swap(LHS, RHS);
2109  // LHS is now Y above and expected to have at least 2 uses (the min/max)
2110  // NotA is expected to have 2 uses from the min/max and 1 from the sub.
2111  if (isFreeToInvert(LHS, !LHS->hasNUsesOrMore(3)) &&
2112  !NotA->hasNUsesOrMore(4)) {
2113  Value *Not = Builder.CreateNot(MinMax);
2114  if (NotA == Op0)
2115  return BinaryOperator::CreateSub(Not, A);
2116  else
2117  return BinaryOperator::CreateSub(A, Not);
2118  }
2119  }
2120  }
2121 
2122  // Optimize pointer differences into the same array into a size. Consider:
2123  // &A[10] - &A[0]: we should compile this to "10".
2124  Value *LHSOp, *RHSOp;
2125  if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
2126  match(Op1, m_PtrToInt(m_Value(RHSOp))))
2127  if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType(),
2128  I.hasNoUnsignedWrap()))
2129  return replaceInstUsesWith(I, Res);
2130 
2131  // trunc(p)-trunc(q) -> trunc(p-q)
2132  if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) &&
2133  match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp)))))
2134  if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType(),
2135  /* IsNUW */ false))
2136  return replaceInstUsesWith(I, Res);
2137 
2138  // Canonicalize a shifty way to code absolute value to the common pattern.
2139  // There are 2 potential commuted variants.
2140  // We're relying on the fact that we only do this transform when the shift has
2141  // exactly 2 uses and the xor has exactly 1 use (otherwise, we might increase
2142  // instructions).
2143  Value *A;
2144  const APInt *ShAmt;
2145  Type *Ty = I.getType();
2146  if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
2147  Op1->hasNUses(2) && *ShAmt == Ty->getScalarSizeInBits() - 1 &&
2148  match(Op0, m_OneUse(m_c_Xor(m_Specific(A), m_Specific(Op1))))) {
2149  // B = ashr i32 A, 31 ; smear the sign bit
2150  // sub (xor A, B), B ; flip bits if negative and subtract -1 (add 1)
2151  // --> (A < 0) ? -A : A
2152  Value *Cmp = Builder.CreateICmpSLT(A, ConstantInt::getNullValue(Ty));
2153  // Copy the nuw/nsw flags from the sub to the negate.
2154  Value *Neg = Builder.CreateNeg(A, "", I.hasNoUnsignedWrap(),
2155  I.hasNoSignedWrap());
2156  return SelectInst::Create(Cmp, Neg, A);
2157  }
2158 
2159  // If we are subtracting a low-bit masked subset of some value from an add
2160  // of that same value with no low bits changed, that is clearing some low bits
2161  // of the sum:
2162  // sub (X + AddC), (X & AndC) --> and (X + AddC), ~AndC
2163  const APInt *AddC, *AndC;
2164  if (match(Op0, m_Add(m_Value(X), m_APInt(AddC))) &&
2165  match(Op1, m_And(m_Specific(X), m_APInt(AndC)))) {
2166  unsigned BitWidth = Ty->getScalarSizeInBits();
2167  unsigned Cttz = AddC->countTrailingZeros();
2168  APInt HighMask(APInt::getHighBitsSet(BitWidth, BitWidth - Cttz));
2169  if ((HighMask & *AndC).isZero())
2170  return BinaryOperator::CreateAnd(Op0, ConstantInt::get(Ty, ~(*AndC)));
2171  }
2172 
2173  if (Instruction *V =
2174  canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
2175  return V;
2176 
2177  // X - usub.sat(X, Y) => umin(X, Y)
2178  if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Specific(Op0),
2179  m_Value(Y)))))
2180  return replaceInstUsesWith(
2181  I, Builder.CreateIntrinsic(Intrinsic::umin, {I.getType()}, {Op0, Y}));
2182 
2183  // umax(X, Op1) - Op1 --> usub.sat(X, Op1)
2184  // TODO: The one-use restriction is not strictly necessary, but it may
2185  // require improving other pattern matching and/or codegen.
2186  if (match(Op0, m_OneUse(m_c_UMax(m_Value(X), m_Specific(Op1)))))
2187  return replaceInstUsesWith(
2188  I, Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {X, Op1}));
2189 
2190  // Op0 - umax(X, Op0) --> 0 - usub.sat(X, Op0)
2191  if (match(Op1, m_OneUse(m_c_UMax(m_Value(X), m_Specific(Op0))))) {
2192  Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {X, Op0});
2193  return BinaryOperator::CreateNeg(USub);
2194  }
2195 
2196  // C - ctpop(X) => ctpop(~X) if C is bitwidth
2197  if (match(Op0, m_SpecificInt(Ty->getScalarSizeInBits())) &&
2198  match(Op1, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(X)))))
2199  return replaceInstUsesWith(
2200  I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
2201  {Builder.CreateNot(X)}));
2202 
2203  return TryToNarrowDeduceFlags();
2204 }
2205 
2206 /// This eliminates floating-point negation in either 'fneg(X)' or
2207 /// 'fsub(-0.0, X)' form by combining into a constant operand.
2209  // This is limited with one-use because fneg is assumed better for
2210  // reassociation and cheaper in codegen than fmul/fdiv.
2211  // TODO: Should the m_OneUse restriction be removed?
2212  Instruction *FNegOp;
2213  if (!match(&I, m_FNeg(m_OneUse(m_Instruction(FNegOp)))))
2214  return nullptr;
2215 
2216  Value *X;
2217  Constant *C;
2218 
2219  // Fold negation into constant operand.
2220  // -(X * C) --> X * (-C)
2221  if (match(FNegOp, m_FMul(m_Value(X), m_Constant(C))))
2223  // -(X / C) --> X / (-C)
2224  if (match(FNegOp, m_FDiv(m_Value(X), m_Constant(C))))
2226  // -(C / X) --> (-C) / X
2227  if (match(FNegOp, m_FDiv(m_Constant(C), m_Value(X)))) {
2228  Instruction *FDiv =
2230 
2231  // Intersect 'nsz' and 'ninf' because those special value exceptions may not
2232  // apply to the fdiv. Everything else propagates from the fneg.
2233  // TODO: We could propagate nsz/ninf from fdiv alone?
2234  FastMathFlags FMF = I.getFastMathFlags();
2235  FastMathFlags OpFMF = FNegOp->getFastMathFlags();
2236  FDiv->setHasNoSignedZeros(FMF.noSignedZeros() && OpFMF.noSignedZeros());
2237  FDiv->setHasNoInfs(FMF.noInfs() && OpFMF.noInfs());
2238  return FDiv;
2239  }
2240  // With NSZ [ counter-example with -0.0: -(-0.0 + 0.0) != 0.0 + -0.0 ]:
2241  // -(X + C) --> -X + -C --> -C - X
2242  if (I.hasNoSignedZeros() && match(FNegOp, m_FAdd(m_Value(X), m_Constant(C))))
2244 
2245  return nullptr;
2246 }
2247 
2250  Value *FNeg;
2251  if (!match(&I, m_FNeg(m_Value(FNeg))))
2252  return nullptr;
2253 
2254  Value *X, *Y;
2255  if (match(FNeg, m_OneUse(m_FMul(m_Value(X), m_Value(Y)))))
2256  return BinaryOperator::CreateFMulFMF(Builder.CreateFNegFMF(X, &I), Y, &I);
2257 
2258  if (match(FNeg, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))))
2259  return BinaryOperator::CreateFDivFMF(Builder.CreateFNegFMF(X, &I), Y, &I);
2260 
2261  return nullptr;
2262 }
2263 
2265  Value *Op = I.getOperand(0);
2266 
2267  if (Value *V = SimplifyFNegInst(Op, I.getFastMathFlags(),
2268  getSimplifyQuery().getWithInstruction(&I)))
2269  return replaceInstUsesWith(I, V);
2270 
2272  return X;
2273 
2274  Value *X, *Y;
2275 
2276  // If we can ignore the sign of zeros: -(X - Y) --> (Y - X)
2277  if (I.hasNoSignedZeros() &&
2279  return BinaryOperator::CreateFSubFMF(Y, X, &I);
2280 
2282  return R;
2283 
2284  // Try to eliminate fneg if at least 1 arm of the select is negated.
2285  Value *Cond;
2287  // Unlike most transforms, this one is not safe to propagate nsz unless
2288  // it is present on the original select. (We are conservatively intersecting
2289  // the nsz flags from the select and root fneg instruction.)
2290  auto propagateSelectFMF = [&](SelectInst *S) {
2291  S->copyFastMathFlags(&I);
2292  if (auto *OldSel = dyn_cast<SelectInst>(Op))
2293  if (!OldSel->hasNoSignedZeros())
2294  S->setHasNoSignedZeros(false);
2295  };
2296  // -(Cond ? -P : Y) --> Cond ? P : -Y
2297  Value *P;
2298  if (match(X, m_FNeg(m_Value(P)))) {
2299  Value *NegY = Builder.CreateFNegFMF(Y, &I, Y->getName() + ".neg");
2300  SelectInst *NewSel = SelectInst::Create(Cond, P, NegY);
2301  propagateSelectFMF(NewSel);
2302  return NewSel;
2303  }
2304  // -(Cond ? X : -P) --> Cond ? -X : P
2305  if (match(Y, m_FNeg(m_Value(P)))) {
2306  Value *NegX = Builder.CreateFNegFMF(X, &I, X->getName() + ".neg");
2307  SelectInst *NewSel = SelectInst::Create(Cond, NegX, P);
2308  propagateSelectFMF(NewSel);
2309  return NewSel;
2310  }
2311  }
2312 
2313  return nullptr;
2314 }
2315 
2317  if (Value *V = SimplifyFSubInst(I.getOperand(0), I.getOperand(1),
2318  I.getFastMathFlags(),
2319  getSimplifyQuery().getWithInstruction(&I)))
2320  return replaceInstUsesWith(I, V);
2321 
2322  if (Instruction *X = foldVectorBinop(I))
2323  return X;
2324 
2325  if (Instruction *Phi = foldBinopWithPhiOperands(I))
2326  return Phi;
2327 
2328  // Subtraction from -0.0 is the canonical form of fneg.
2329  // fsub -0.0, X ==> fneg X
2330  // fsub nsz 0.0, X ==> fneg nsz X
2331  //
2332  // FIXME This matcher does not respect FTZ or DAZ yet:
2333  // fsub -0.0, Denorm ==> +-0
2334  // fneg Denorm ==> -Denorm
2335  Value *Op;
2336  if (match(&I, m_FNeg(m_Value(Op))))
2337  return UnaryOperator::CreateFNegFMF(Op, &I);
2338 
2340  return X;
2341 
2343  return R;
2344 
2345  Value *X, *Y;
2346  Constant *C;
2347 
2348  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2349  // If Op0 is not -0.0 or we can ignore -0.0: Z - (X - Y) --> Z + (Y - X)
2350  // Canonicalize to fadd to make analysis easier.
2351  // This can also help codegen because fadd is commutative.
2352  // Note that if this fsub was really an fneg, the fadd with -0.0 will get
2353  // killed later. We still limit that particular transform with 'hasOneUse'
2354  // because an fneg is assumed better/cheaper than a generic fsub.
2355  if (I.hasNoSignedZeros() || CannotBeNegativeZero(Op0, SQ.TLI)) {
2356  if (match(Op1, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) {
2357  Value *NewSub = Builder.CreateFSubFMF(Y, X, &I);
2358  return BinaryOperator::CreateFAddFMF(Op0, NewSub, &I);
2359  }
2360  }
2361 
2362  // (-X) - Op1 --> -(X + Op1)
2363  if (I.hasNoSignedZeros() && !isa<ConstantExpr>(Op0) &&
2364  match(Op0, m_OneUse(m_FNeg(m_Value(X))))) {
2365  Value *FAdd = Builder.CreateFAddFMF(X, Op1, &I);
2367  }
2368 
2369  if (isa<Constant>(Op0))
2370  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
2371  if (Instruction *NV = FoldOpIntoSelect(I, SI))
2372  return NV;
2373 
2374  // X - C --> X + (-C)
2375  // But don't transform constant expressions because there's an inverse fold
2376  // for X + (-Y) --> X - Y.
2377  if (match(Op1, m_ImmConstant(C)))
2379 
2380  // X - (-Y) --> X + Y
2381  if (match(Op1, m_FNeg(m_Value(Y))))
2382  return BinaryOperator::CreateFAddFMF(Op0, Y, &I);
2383 
2384  // Similar to above, but look through a cast of the negated value:
2385  // X - (fptrunc(-Y)) --> X + fptrunc(Y)
2386  Type *Ty = I.getType();
2387  if (match(Op1, m_OneUse(m_FPTrunc(m_FNeg(m_Value(Y))))))
2388  return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPTrunc(Y, Ty), &I);
2389 
2390  // X - (fpext(-Y)) --> X + fpext(Y)
2391  if (match(Op1, m_OneUse(m_FPExt(m_FNeg(m_Value(Y))))))
2392  return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPExt(Y, Ty), &I);
2393 
2394  // Similar to above, but look through fmul/fdiv of the negated value:
2395  // Op0 - (-X * Y) --> Op0 + (X * Y)
2396  // Op0 - (Y * -X) --> Op0 + (X * Y)
2397  if (match(Op1, m_OneUse(m_c_FMul(m_FNeg(m_Value(X)), m_Value(Y))))) {
2398  Value *FMul = Builder.CreateFMulFMF(X, Y, &I);
2399  return BinaryOperator::CreateFAddFMF(Op0, FMul, &I);
2400  }
2401  // Op0 - (-X / Y) --> Op0 + (X / Y)
2402  // Op0 - (X / -Y) --> Op0 + (X / Y)
2403  if (match(Op1, m_OneUse(m_FDiv(m_FNeg(m_Value(X)), m_Value(Y)))) ||
2404  match(Op1, m_OneUse(m_FDiv(m_Value(X), m_FNeg(m_Value(Y)))))) {
2405  Value *FDiv = Builder.CreateFDivFMF(X, Y, &I);
2406  return BinaryOperator::CreateFAddFMF(Op0, FDiv, &I);
2407  }
2408 
2409  // Handle special cases for FSub with selects feeding the operation
2410  if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
2411  return replaceInstUsesWith(I, V);
2412 
2413  if (I.hasAllowReassoc() && I.hasNoSignedZeros()) {
2414  // (Y - X) - Y --> -X
2415  if (match(Op0, m_FSub(m_Specific(Op1), m_Value(X))))
2416  return UnaryOperator::CreateFNegFMF(X, &I);
2417 
2418  // Y - (X + Y) --> -X
2419  // Y - (Y + X) --> -X
2420  if (match(Op1, m_c_FAdd(m_Specific(Op0), m_Value(X))))
2421  return UnaryOperator::CreateFNegFMF(X, &I);
2422 
2423  // (X * C) - X --> X * (C - 1.0)
2424  if (match(Op0, m_FMul(m_Specific(Op1), m_Constant(C)))) {
2425  Constant *CSubOne = ConstantExpr::getFSub(C, ConstantFP::get(Ty, 1.0));
2426  return BinaryOperator::CreateFMulFMF(Op1, CSubOne, &I);
2427  }
2428  // X - (X * C) --> X * (1.0 - C)
2429  if (match(Op1, m_FMul(m_Specific(Op0), m_Constant(C)))) {
2430  Constant *OneSubC = ConstantExpr::getFSub(ConstantFP::get(Ty, 1.0), C);
2431  return BinaryOperator::CreateFMulFMF(Op0, OneSubC, &I);
2432  }
2433 
2434  // Reassociate fsub/fadd sequences to create more fadd instructions and
2435  // reduce dependency chains:
2436  // ((X - Y) + Z) - Op1 --> (X + Z) - (Y + Op1)
2437  Value *Z;
2439  m_Value(Z))))) {
2440  Value *XZ = Builder.CreateFAddFMF(X, Z, &I);
2441  Value *YW = Builder.CreateFAddFMF(Y, Op1, &I);
2442  return BinaryOperator::CreateFSubFMF(XZ, YW, &I);
2443  }
2444 
2445  auto m_FaddRdx = [](Value *&Sum, Value *&Vec) {
2446  return m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(m_Value(Sum),
2447  m_Value(Vec)));
2448  };
2449  Value *A0, *A1, *V0, *V1;
2450  if (match(Op0, m_FaddRdx(A0, V0)) && match(Op1, m_FaddRdx(A1, V1)) &&
2451  V0->getType() == V1->getType()) {
2452  // Difference of sums is sum of differences:
2453  // add_rdx(A0, V0) - add_rdx(A1, V1) --> add_rdx(A0, V0 - V1) - A1
2454  Value *Sub = Builder.CreateFSubFMF(V0, V1, &I);
2455  Value *Rdx = Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,
2456  {Sub->getType()}, {A0, Sub}, &I);
2457  return BinaryOperator::CreateFSubFMF(Rdx, A1, &I);
2458  }
2459 
2461  return F;
2462 
2463  // TODO: This performs reassociative folds for FP ops. Some fraction of the
2464  // functionality has been subsumed by simple pattern matching here and in
2465  // InstSimplify. We should let a dedicated reassociation pass handle more
2466  // complex pattern matching and remove this from InstCombine.
2467  if (Value *V = FAddCombine(Builder).simplify(&I))
2468  return replaceInstUsesWith(I, V);
2469 
2470  // (X - Y) - Op1 --> X - (Y + Op1)
2471  if (match(Op0, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) {
2472  Value *FAdd = Builder.CreateFAddFMF(Y, Op1, &I);
2474  }
2475  }
2476 
2477  return nullptr;
2478 }
llvm::lltok::APFloat
@ APFloat
Definition: LLToken.h:497
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:1119
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
hoistFNegAboveFMulFDiv
static Instruction * hoistFNegAboveFMulFDiv(Instruction &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineAddSub.cpp:2248
llvm::InstCombinerImpl::visitFAdd
Instruction * visitFAdd(BinaryOperator &I)
Definition: InstCombineAddSub.cpp:1530
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:269
llvm::PatternMatch::m_TruncOrSelf
match_combine_or< CastClass_match< OpTy, Instruction::Trunc >, OpTy > m_TruncOrSelf(const OpTy &Op)
Definition: PatternMatch.h:1627
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:1606
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:874
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:367
llvm::ConstantExpr::getSIToFP
static Constant * getSIToFP(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2192
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:1400
MatchDiv
static bool MatchDiv(Value *E, Value *&Op, APInt &C, bool IsSigned)
Definition: InstCombineAddSub.cpp:1033
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:721
simplify
hexagon bit simplify
Definition: HexagonBitSimplify.cpp:261
llvm::ConstantExpr::getZExt
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2143
T
llvm::APInt::isMask
bool isMask(unsigned numBits) const
Definition: APInt.h:469
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:2806
llvm::SelectPatternResult::Flavor
SelectPatternFlavor Flavor
Definition: ValueTracking.h:700
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1127
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:826
llvm::Type::getScalarType
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:308
llvm::ConstantExpr::getSExt
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2129
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1176
llvm::BinaryOperator::CreateFDivFMF
static BinaryOperator * CreateFDivFMF(Value *V1, Value *V2, Instruction *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:274
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:988
llvm::Type::getFltSemantics
const fltSemantics & getFltSemantics() const
Definition: Type.cpp:69
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:3152
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:5229
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:287
APInt.h
llvm::ConstantFP::isZero
bool isZero() const
Return true if the value is positive or negative zero.
Definition: Constants.h:301
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:1412
llvm::ConstantExpr::getFPToSI
static Constant * getFPToSI(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2214
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:4997
llvm::FastMathFlags::noSignedZeros
bool noSignedZeros() const
Definition: Operator.h:213
llvm::ConstantFP::getValueAPF
const APFloat & getValueAPF() const
Definition: Constants.h:297
llvm::PatternMatch::m_BinOp
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:84
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:80
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:1133
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:61
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:839
AlignOf.h
STLExtras.h
RHS
Value * RHS
Definition: X86PartialReduction.cpp:74
llvm::matchSelectPattern
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
Definition: ValueTracking.cpp:6115
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:2249
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:2766
llvm::UnaryOperator
Definition: InstrTypes.h:103
factorizeLerp
static Instruction * factorizeLerp(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Eliminate an op from a linear interpolation (lerp) pattern.
Definition: InstCombineAddSub.cpp:1469
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:2287
llvm::FastMathFlags
Convenience struct for specifying and reasoning about fast-math flags.
Definition: Operator.h:165
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:676
llvm::isInt
constexpr bool isInt(int64_t x)
Checks if an integer fits into the given bit width.
Definition: MathExtras.h:363
llvm::InstCombinerImpl::foldAddWithConstant
Instruction * foldAddWithConstant(BinaryOperator &Add)
Definition: InstCombineAddSub.cpp:856
llvm::APFloat::getSemantics
const fltSemantics & getSemantics() const
Definition: APFloat.h:1223
llvm::AlignedCharArrayUnion
A suitably aligned and sized character array member which can hold elements of any type.
Definition: AlignOf.h:27
llvm::EmitGEPOffset
Value * EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, bool NoAssumptions=false)
Given a getelementptr instruction/constantexpr, emit the code necessary to compute the offset from th...
Definition: Local.h:29
llvm::PatternMatch::m_Deferred
deferredval_ty< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
Definition: PatternMatch.h:798
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:2133
llvm::PatternMatch::m_FDiv
BinaryOp_match< LHS, RHS, Instruction::FDiv > m_FDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1079
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:2347
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:208
llvm::PatternMatch::m_FAdd
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:994
KnownBits.h
llvm::PatternMatch::m_FSub
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1006
factorizeFAddFSub
static Instruction * factorizeFAddFSub(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Factor a common operand out of fadd/fsub of fmul/fdiv.
Definition: InstCombineAddSub.cpp:1485
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:2721
llvm::APInt::isShiftedMask
bool isShiftedMask() const
Return true if this APInt value contains a sequence of ones with the remainder zero.
Definition: APInt.h:491
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:270
llvm::APInt::umul_ov
APInt umul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1961
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:2213
LHS
Value * LHS
Definition: X86PartialReduction.cpp:73
llvm::APInt::isNegative
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:312
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1772
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:1472
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:519
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:128
llvm::User
Definition: User.h:44
llvm::RoundingMode
RoundingMode
Rounding mode.
Definition: FloatingPointMode.h:34
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::SelectPatternResult::isMinOrMax
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
Definition: ValueTracking.h:708
llvm::operator+=
std::string & operator+=(std::string &buffer, StringRef string)
Definition: StringRef.h:960
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:1521
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:726
foldFNegIntoConstant
static Instruction * foldFNegIntoConstant(Instruction &I)
This eliminates floating-point negation in either 'fneg(X)' or 'fsub(-0.0, X)' form by combining into...
Definition: InstCombineAddSub.cpp:2208
llvm::PatternMatch::m_ZExt
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:1639
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:2235
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
checkForNegativeOperand
static Value * checkForNegativeOperand(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineAddSub.cpp:759
llvm::PatternMatch::m_FNeg
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
Definition: PatternMatch.h:1043
llvm::Constant::getAllOnesValue
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:405
llvm::PatternMatch::m_SDiv
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1073
llvm::Instruction
Definition: Instruction.h:45
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:191
llvm::PatternMatch::m_UMin
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1881
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:2256
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
This file declares a class to represent arbitrary precision floating point values and provide a varie...
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:925
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:1101
llvm::PatternMatch::m_URem
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1085
PatternMatch.h
llvm::APInt::countTrailingZeros
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1539
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:3228
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:5221
llvm::array_lengthof
constexpr size_t array_lengthof(T(&)[N])
Find the length of an array.
Definition: STLExtras.h:1435
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:2337
Type.h
llvm::ConstantExpr::getFNeg
static Constant * getFNeg(Constant *C)
Definition: Constants.cpp:2698
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:513
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:1166
llvm::APFloat::multiply
opStatus multiply(const APFloat &RHS, roundingMode RM)
Definition: APFloat.h:988
llvm::PatternMatch::m_Xor
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1115
llvm::InstCombinerImpl::visitFNeg
Instruction * visitFNeg(UnaryOperator &I)
Definition: InstCombineAddSub.cpp:2264
llvm::PatternMatch::m_FPTrunc
CastClass_match< OpTy, Instruction::FPTrunc > m_FPTrunc(const OpTy &Op)
Definition: PatternMatch.h:1692
llvm::PatternMatch::m_ZExtOrSelf
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, OpTy > m_ZExtOrSelf(const OpTy &Op)
Definition: PatternMatch.h:1645
llvm::APFloat
Definition: APFloat.h:701
llvm::PatternMatch::m_Zero
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:535
llvm::PatternMatch::m_NUWAdd
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1199
llvm::MipsISD::Ext
@ Ext
Definition: MipsISelLowering.h:156
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::InstCombinerImpl::visitAdd
Instruction * visitAdd(BinaryOperator &I)
Definition: InstCombineAddSub.cpp:1279
llvm::FastMathFlags::noInfs
bool noInfs() const
Definition: Operator.h:212
llvm::UnaryOperator::CreateFNegFMF
static UnaryOperator * CreateFNegFMF(Value *Op, Instruction *FMFSource, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: InstrTypes.h:166
llvm::PatternMatch::m_ImmConstant
match_combine_and< class_match< Constant >, match_unless< class_match< ConstantExpr > > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:759
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:269
llvm::InstCombinerImpl::canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract
Instruction * canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(BinaryOperator &I)
Definition: InstCombineAddSub.cpp:1142
llvm::GEPOperator::countNonConstantIndices
unsigned countNonConstantIndices() const
Definition: Operator.h:569
llvm::APInt::logBase2
unsigned logBase2() const
Definition: APInt.h:1648
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1109
llvm::PatternMatch::m_AllOnes
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:445
llvm::Value::hasNUsesOrMore
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N uses or more.
Definition: Value.cpp:153
isConstant
static bool isConstant(const MachineInstr &MI)
Definition: AMDGPUInstructionSelector.cpp:2278
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::ConstantExpr::getFSub
static Constant * getFSub(Constant *C1, Constant *C2)
Definition: Constants.cpp:2728
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1103
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
llvm::PatternMatch::m_SRem
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1091
llvm::InstCombinerImpl::SimplifyAddWithRemainder
Value * SimplifyAddWithRemainder(BinaryOperator &I)
Tries to simplify add operations using the definition of remainder.
Definition: InstCombineAddSub.cpp:1065
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:224
llvm::InstCombinerImpl::visitFSub
Instruction * visitFSub(BinaryOperator &I)
Definition: InstCombineAddSub.cpp:2316
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:1000
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:852
llvm::Negator::Negate
static LLVM_NODISCARD Value * Negate(bool LHSIsZero, Value *Root, InstCombinerImpl &IC)
Attempt to negate Root.
Definition: InstCombineNegator.cpp:503
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1741
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:142
llvm::GEPOperator
Definition: Operator.h:473
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
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:4812
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:1633
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:863
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:216
llvm::Instruction::getFastMathFlags
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
Definition: Instruction.cpp:290
llvm::BinaryOperator
Definition: InstrTypes.h:190
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:68
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:604
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
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
foldNoWrapAdd
static Instruction * foldNoWrapAdd(BinaryOperator &Add, InstCombiner::BuilderTy &Builder)
Wrapping flags may allow combining constants separated by an extend.
Definition: InstCombineAddSub.cpp:816
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:993
factorizeMathWithShlOps
static Instruction * factorizeMathWithShlOps(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
This is a specialization of a more general transform from SimplifyUsingDistributiveLaws.
Definition: InstCombineAddSub.cpp:1245
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
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:1676
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:162
llvm::PatternMatch::m_FPExt
CastClass_match< OpTy, Instruction::FPExt > m_FPExt(const OpTy &Op)
Definition: PatternMatch.h:1697
llvm::tgtok::IntVal
@ IntVal
Definition: TGLexer.h:64
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:2138
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:240
Constant.h
llvm::PatternMatch::m_SExtOrSelf
match_combine_or< CastClass_match< OpTy, Instruction::SExt >, OpTy > m_SExtOrSelf(const OpTy &Op)
Definition: PatternMatch.h:1651
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:348
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:1067
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:259
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
llvm::GEPOperator::isInBounds
bool isInBounds() const
Test whether this is an inbounds GEP, as defined by LangRef.html.
Definition: Operator.h:490
llvm::ConstantExpr::getAdd
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2710
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:196
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:972
Casting.h
llvm::fltSemantics
Definition: APFloat.cpp:54
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::APInt::smul_ov
APInt smul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1950
MulWillOverflow
static bool MulWillOverflow(APInt &C0, APInt &C1, bool IsSigned)
Definition: InstCombineAddSub.cpp:1054
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:522
llvm::PatternMatch::m_PtrToInt
CastClass_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
Definition: PatternMatch.h:1609
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::InstCombinerImpl::visitSub
Instruction * visitSub(BinaryOperator &I)
Definition: InstCombineAddSub.cpp:1751
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:2263
llvm::APInt::sext
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:926
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:674
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:3364
llvm::APFloatBase::rmNearestTiesToEven
static constexpr roundingMode rmNearestTiesToEven
Definition: APFloat.h:190
llvm::RecurKind::FAdd
@ FAdd
Sum of floats.
llvm::PatternMatch::m_c_FMul
BinaryOp_match< LHS, RHS, Instruction::FMul, true > m_c_FMul(const LHS &L, const RHS &R)
Matches FMul with LHS and RHS in either order.
Definition: PatternMatch.h:2362
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:2355
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:215
SmallVector.h
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:780
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:220
llvm::SIToFPInst
This class represents a cast from signed integer to floating point.
Definition: Instructions.h:5007
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:1404
N
#define N
MatchRem
static bool MatchRem(Value *E, Value *&Op, APInt &C, bool &IsSigned)
Definition: InstCombineAddSub.cpp:1011
InstructionSimplify.h
llvm::APFloatBase::semanticsPrecision
static unsigned int semanticsPrecision(const fltSemantics &)
Definition: APFloat.cpp:211
llvm::PHINode
Definition: Instructions.h:2657
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:2271
CreateAdd
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:234
llvm::PatternMatch::m_Trunc
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:1621
llvm::ConstantExpr::getFAdd
static Constant * getFAdd(Constant *C1, Constant *C2)
Definition: Constants.cpp:2717
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:687
llvm::PatternMatch::m_FMul
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1061
llvm::tgtok::TrueVal
@ TrueVal
Definition: TGLexer.h:61
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:1121
llvm::BinaryOperator::CreateFSubFMF
static BinaryOperator * CreateFSubFMF(Value *V1, Value *V2, Instruction *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:264
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:2331
llvm::PatternMatch::m_Mul
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1055