1 //===- InstCombineAddSub.cpp ----------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the visit functions for add, fadd, sub, and fsub.
12 //===----------------------------------------------------------------------===//
14 #include "InstCombine.h"
15 #include "llvm/Analysis/InstructionSimplify.h"
16 #include "llvm/IR/DataLayout.h"
17 #include "llvm/Support/GetElementPtrTypeIterator.h"
18 #include "llvm/Support/PatternMatch.h"
20 using namespace PatternMatch;
24 /// Class representing coefficient of floating-point addend.
25 /// This class needs to be highly efficient, which is especially true for
26 /// the constructor. As of I write this comment, the cost of the default
27 /// constructor is merely 4-byte-store-zero (Assuming compiler is able to
28 /// perform write-merging).
32 // The constructor has to initialize a APFloat, which is uncessary for
33 // most addends which have coefficient either 1 or -1. So, the constructor
34 // is expensive. In order to avoid the cost of the constructor, we should
35 // reuse some instances whenever possible. The pre-created instances
36 // FAddCombine::Add[0-5] embodies this idea.
38 FAddendCoef() : IsFp(false), BufHasFpVal(false), IntVal(0) {}
42 assert(!insaneIntVal(C) && "Insane coefficient");
43 IsFp = false; IntVal = C;
46 void set(const APFloat& C);
50 bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); }
51 Value *getValue(Type *) const;
53 // If possible, don't define operator+/operator- etc because these
54 // operators inevitably call FAddendCoef's constructor which is not cheap.
55 void operator=(const FAddendCoef &A);
56 void operator+=(const FAddendCoef &A);
57 void operator-=(const FAddendCoef &A);
58 void operator*=(const FAddendCoef &S);
60 bool isOne() const { return isInt() && IntVal == 1; }
61 bool isTwo() const { return isInt() && IntVal == 2; }
62 bool isMinusOne() const { return isInt() && IntVal == -1; }
63 bool isMinusTwo() const { return isInt() && IntVal == -2; }
66 bool insaneIntVal(int V) { return V > 4 || V < -4; }
67 APFloat *getFpValPtr(void)
68 { return reinterpret_cast<APFloat*>(&FpValBuf.buffer[0]); }
69 const APFloat *getFpValPtr(void) const
70 { return reinterpret_cast<const APFloat*>(&FpValBuf.buffer[0]); }
72 const APFloat &getFpVal(void) const {
73 assert(IsFp && BufHasFpVal && "Incorret state");
74 return *getFpValPtr();
77 APFloat &getFpVal(void) {
78 assert(IsFp && BufHasFpVal && "Incorret state");
79 return *getFpValPtr();
82 bool isInt() const { return !IsFp; }
84 // If the coefficient is represented by an integer, promote it to a
86 void convertToFpType(const fltSemantics &Sem);
88 // Construct an APFloat from a signed integer.
89 // TODO: We should get rid of this function when APFloat can be constructed
90 // from an *SIGNED* integer.
91 APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val);
96 // True iff FpValBuf contains an instance of APFloat.
99 // The integer coefficient of an individual addend is either 1 or -1,
100 // and we try to simplify at most 4 addends from neighboring at most
101 // two instructions. So the range of <IntVal> falls in [-4, 4]. APInt
102 // is overkill of this end.
105 AlignedCharArrayUnion<APFloat> FpValBuf;
108 /// FAddend is used to represent floating-point addend. An addend is
109 /// represented as <C, V>, where the V is a symbolic value, and C is a
110 /// constant coefficient. A constant addend is represented as <C, 0>.
114 FAddend() { Val = 0; }
116 Value *getSymVal (void) const { return Val; }
117 const FAddendCoef &getCoef(void) const { return Coeff; }
119 bool isConstant() const { return Val == 0; }
120 bool isZero() const { return Coeff.isZero(); }
122 void set(short Coefficient, Value *V) { Coeff.set(Coefficient), Val = V; }
123 void set(const APFloat& Coefficient, Value *V)
124 { Coeff.set(Coefficient); Val = V; }
125 void set(const ConstantFP* Coefficient, Value *V)
126 { Coeff.set(Coefficient->getValueAPF()); Val = V; }
128 void negate() { Coeff.negate(); }
130 /// Drill down the U-D chain one step to find the definition of V, and
131 /// try to break the definition into one or two addends.
132 static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1);
134 /// Similar to FAddend::drillDownOneStep() except that the value being
135 /// splitted is the addend itself.
136 unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const;
138 void operator+=(const FAddend &T) {
139 assert((Val == T.Val) && "Symbolic-values disagree");
144 void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; }
146 // This addend has the value of "Coeff * Val".
151 /// FAddCombine is the class for optimizing an unsafe fadd/fsub along
152 /// with its neighboring at most two instructions.
156 FAddCombine(InstCombiner::BuilderTy *B) : Builder(B), Instr(0) {}
157 Value *simplify(Instruction *FAdd);
160 typedef SmallVector<const FAddend*, 4> AddendVect;
162 Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota);
164 Value *performFactorization(Instruction *I);
166 /// Convert given addend to a Value
167 Value *createAddendVal(const FAddend &A, bool& NeedNeg);
169 /// Return the number of instructions needed to emit the N-ary addition.
170 unsigned calcInstrNumber(const AddendVect& Vect);
171 Value *createFSub(Value *Opnd0, Value *Opnd1);
172 Value *createFAdd(Value *Opnd0, Value *Opnd1);
173 Value *createFMul(Value *Opnd0, Value *Opnd1);
174 Value *createFDiv(Value *Opnd0, Value *Opnd1);
175 Value *createFNeg(Value *V);
176 Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota);
177 void createInstPostProc(Instruction *NewInst);
179 InstCombiner::BuilderTy *Builder;
183 // Debugging stuff are clustered here.
185 unsigned CreateInstrNum;
186 void initCreateInstNum() { CreateInstrNum = 0; }
187 void incCreateInstNum() { CreateInstrNum++; }
189 void initCreateInstNum() {}
190 void incCreateInstNum() {}
195 //===----------------------------------------------------------------------===//
198 // {FAddendCoef, FAddend, FAddition, FAddCombine}.
200 //===----------------------------------------------------------------------===//
201 FAddendCoef::~FAddendCoef() {
203 getFpValPtr()->~APFloat();
206 void FAddendCoef::set(const APFloat& C) {
207 APFloat *P = getFpValPtr();
210 // As the buffer is meanless byte stream, we cannot call
211 // APFloat::operator=().
216 IsFp = BufHasFpVal = true;
219 void FAddendCoef::convertToFpType(const fltSemantics &Sem) {
223 APFloat *P = getFpValPtr();
225 new(P) APFloat(Sem, IntVal);
227 new(P) APFloat(Sem, 0 - IntVal);
230 IsFp = BufHasFpVal = true;
233 APFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) {
235 return APFloat(Sem, Val);
237 APFloat T(Sem, 0 - Val);
243 void FAddendCoef::operator=(const FAddendCoef &That) {
247 set(That.getFpVal());
250 void FAddendCoef::operator+=(const FAddendCoef &That) {
251 enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven;
252 if (isInt() == That.isInt()) {
254 IntVal += That.IntVal;
256 getFpVal().add(That.getFpVal(), RndMode);
261 const APFloat &T = That.getFpVal();
262 convertToFpType(T.getSemantics());
263 getFpVal().add(T, RndMode);
267 APFloat &T = getFpVal();
268 T.add(createAPFloatFromInt(T.getSemantics(), That.IntVal), RndMode);
271 void FAddendCoef::operator-=(const FAddendCoef &That) {
272 enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven;
273 if (isInt() == That.isInt()) {
275 IntVal -= That.IntVal;
277 getFpVal().subtract(That.getFpVal(), RndMode);
282 const APFloat &T = That.getFpVal();
283 convertToFpType(T.getSemantics());
284 getFpVal().subtract(T, RndMode);
288 APFloat &T = getFpVal();
289 T.subtract(createAPFloatFromInt(T.getSemantics(), IntVal), RndMode);
292 void FAddendCoef::operator*=(const FAddendCoef &That) {
296 if (That.isMinusOne()) {
301 if (isInt() && That.isInt()) {
302 int Res = IntVal * (int)That.IntVal;
303 assert(!insaneIntVal(Res) && "Insane int value");
308 const fltSemantics &Semantic =
309 isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics();
312 convertToFpType(Semantic);
313 APFloat &F0 = getFpVal();
316 F0.multiply(createAPFloatFromInt(Semantic, That.IntVal),
317 APFloat::rmNearestTiesToEven);
319 F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven);
324 void FAddendCoef::negate() {
328 getFpVal().changeSign();
331 Value *FAddendCoef::getValue(Type *Ty) const {
333 ConstantFP::get(Ty, float(IntVal)) :
334 ConstantFP::get(Ty->getContext(), getFpVal());
337 // The definition of <Val> Addends
338 // =========================================
339 // A + B <1, A>, <1,B>
340 // A - B <1, A>, <1,B>
343 // A + C <1, A> <C, NULL>
344 // 0 +/- 0 <0, NULL> (corner case)
346 // Legend: A and B are not constant, C is constant
348 unsigned FAddend::drillValueDownOneStep
349 (Value *Val, FAddend &Addend0, FAddend &Addend1) {
351 if (Val == 0 || !(I = dyn_cast<Instruction>(Val)))
354 unsigned Opcode = I->getOpcode();
356 if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) {
358 Value *Opnd0 = I->getOperand(0);
359 Value *Opnd1 = I->getOperand(1);
360 if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && C0->isZero())
363 if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && C1->isZero())
368 Addend0.set(1, Opnd0);
374 FAddend &Addend = Opnd0 ? Addend1 : Addend0;
376 Addend.set(1, Opnd1);
379 if (Opcode == Instruction::FSub)
384 return Opnd0 && Opnd1 ? 2 : 1;
386 // Both operands are zero. Weird!
387 Addend0.set(APFloat(C0->getValueAPF().getSemantics()), 0);
391 if (I->getOpcode() == Instruction::FMul) {
392 Value *V0 = I->getOperand(0);
393 Value *V1 = I->getOperand(1);
394 if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) {
399 if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) {
408 // Try to break *this* addend into two addends. e.g. Suppose this addend is
409 // <2.3, V>, and V = X + Y, by calling this function, we obtain two addends,
410 // i.e. <2.3, X> and <2.3, Y>.
412 unsigned FAddend::drillAddendDownOneStep
413 (FAddend &Addend0, FAddend &Addend1) const {
417 unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1);
418 if (!BreakNum || Coeff.isOne())
421 Addend0.Scale(Coeff);
424 Addend1.Scale(Coeff);
429 // Try to perform following optimization on the input instruction I. Return the
430 // simplified expression if was successful; otherwise, return 0.
432 // Instruction "I" is Simplified into
433 // -------------------------------------------------------
434 // (x * y) +/- (x * z) x * (y +/- z)
435 // (y / x) +/- (z / x) (y +/- z) / x
437 Value *FAddCombine::performFactorization(Instruction *I) {
438 assert((I->getOpcode() == Instruction::FAdd ||
439 I->getOpcode() == Instruction::FSub) && "Expect add/sub");
441 Instruction *I0 = dyn_cast<Instruction>(I->getOperand(0));
442 Instruction *I1 = dyn_cast<Instruction>(I->getOperand(1));
444 if (!I0 || !I1 || I0->getOpcode() != I1->getOpcode())
448 if (I0->getOpcode() == Instruction::FMul)
450 else if (I0->getOpcode() != Instruction::FDiv)
453 Value *Opnd0_0 = I0->getOperand(0);
454 Value *Opnd0_1 = I0->getOperand(1);
455 Value *Opnd1_0 = I1->getOperand(0);
456 Value *Opnd1_1 = I1->getOperand(1);
458 // Input Instr I Factor AddSub0 AddSub1
459 // ----------------------------------------------
460 // (x*y) +/- (x*z) x y z
461 // (y/x) +/- (z/x) x y z
464 Value *AddSub0 = 0, *AddSub1 = 0;
467 if (Opnd0_0 == Opnd1_0 || Opnd0_0 == Opnd1_1)
469 else if (Opnd0_1 == Opnd1_0 || Opnd0_1 == Opnd1_1)
473 AddSub0 = (Factor == Opnd0_0) ? Opnd0_1 : Opnd0_0;
474 AddSub1 = (Factor == Opnd1_0) ? Opnd1_1 : Opnd1_0;
476 } else if (Opnd0_1 == Opnd1_1) {
485 // Create expression "NewAddSub = AddSub0 +/- AddsSub1"
486 Value *NewAddSub = (I->getOpcode() == Instruction::FAdd) ?
487 createFAdd(AddSub0, AddSub1) :
488 createFSub(AddSub0, AddSub1);
489 if (ConstantFP *CFP = dyn_cast<ConstantFP>(NewAddSub)) {
490 const APFloat &F = CFP->getValueAPF();
491 if (!F.isNormal() || F.isDenormal())
496 return createFMul(Factor, NewAddSub);
498 return createFDiv(NewAddSub, Factor);
501 Value *FAddCombine::simplify(Instruction *I) {
502 assert(I->hasUnsafeAlgebra() && "Should be in unsafe mode");
504 // Currently we are not able to handle vector type.
505 if (I->getType()->isVectorTy())
508 assert((I->getOpcode() == Instruction::FAdd ||
509 I->getOpcode() == Instruction::FSub) && "Expect add/sub");
511 // Save the instruction before calling other member-functions.
514 FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1;
516 unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1);
518 // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1.
519 unsigned Opnd0_ExpNum = 0;
520 unsigned Opnd1_ExpNum = 0;
522 if (!Opnd0.isConstant())
523 Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1);
525 // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1.
526 if (OpndNum == 2 && !Opnd1.isConstant())
527 Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1);
529 // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1
530 if (Opnd0_ExpNum && Opnd1_ExpNum) {
532 AllOpnds.push_back(&Opnd0_0);
533 AllOpnds.push_back(&Opnd1_0);
534 if (Opnd0_ExpNum == 2)
535 AllOpnds.push_back(&Opnd0_1);
536 if (Opnd1_ExpNum == 2)
537 AllOpnds.push_back(&Opnd1_1);
539 // Compute instruction quota. We should save at least one instruction.
540 unsigned InstQuota = 0;
542 Value *V0 = I->getOperand(0);
543 Value *V1 = I->getOperand(1);
544 InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) &&
545 (!isa<Constant>(V1) && V1->hasOneUse())) ? 2 : 1;
547 if (Value *R = simplifyFAdd(AllOpnds, InstQuota))
552 // The input instruction is : "I=0.0 +/- V". If the "V" were able to be
553 // splitted into two addends, say "V = X - Y", the instruction would have
554 // been optimized into "I = Y - X" in the previous steps.
556 const FAddendCoef &CE = Opnd0.getCoef();
557 return CE.isOne() ? Opnd0.getSymVal() : 0;
560 // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1]
563 AllOpnds.push_back(&Opnd0);
564 AllOpnds.push_back(&Opnd1_0);
565 if (Opnd1_ExpNum == 2)
566 AllOpnds.push_back(&Opnd1_1);
568 if (Value *R = simplifyFAdd(AllOpnds, 1))
572 // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1]
575 AllOpnds.push_back(&Opnd1);
576 AllOpnds.push_back(&Opnd0_0);
577 if (Opnd0_ExpNum == 2)
578 AllOpnds.push_back(&Opnd0_1);
580 if (Value *R = simplifyFAdd(AllOpnds, 1))
584 // step 6: Try factorization as the last resort,
585 return performFactorization(I);
588 Value *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) {
590 unsigned AddendNum = Addends.size();
591 assert(AddendNum <= 4 && "Too many addends");
593 // For saving intermediate results;
594 unsigned NextTmpIdx = 0;
595 FAddend TmpResult[3];
597 // Points to the constant addend of the resulting simplified expression.
598 // If the resulting expr has constant-addend, this constant-addend is
599 // desirable to reside at the top of the resulting expression tree. Placing
600 // constant close to supper-expr(s) will potentially reveal some optimization
601 // opportunities in super-expr(s).
603 const FAddend *ConstAdd = 0;
605 // Simplified addends are placed <SimpVect>.
608 // The outer loop works on one symbolic-value at a time. Suppose the input
609 // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ...
610 // The symbolic-values will be processed in this order: x, y, z.
612 for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) {
614 const FAddend *ThisAddend = Addends[SymIdx];
616 // This addend was processed before.
620 Value *Val = ThisAddend->getSymVal();
621 unsigned StartIdx = SimpVect.size();
622 SimpVect.push_back(ThisAddend);
624 // The inner loop collects addends sharing same symbolic-value, and these
625 // addends will be later on folded into a single addend. Following above
626 // example, if the symbolic value "y" is being processed, the inner loop
627 // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will
628 // be later on folded into "<b1+b2, y>".
630 for (unsigned SameSymIdx = SymIdx + 1;
631 SameSymIdx < AddendNum; SameSymIdx++) {
632 const FAddend *T = Addends[SameSymIdx];
633 if (T && T->getSymVal() == Val) {
634 // Set null such that next iteration of the outer loop will not process
635 // this addend again.
636 Addends[SameSymIdx] = 0;
637 SimpVect.push_back(T);
641 // If multiple addends share same symbolic value, fold them together.
642 if (StartIdx + 1 != SimpVect.size()) {
643 FAddend &R = TmpResult[NextTmpIdx ++];
644 R = *SimpVect[StartIdx];
645 for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++)
648 // Pop all addends being folded and push the resulting folded addend.
649 SimpVect.resize(StartIdx);
652 SimpVect.push_back(&R);
655 // Don't push constant addend at this time. It will be the last element
662 assert((NextTmpIdx <= sizeof(TmpResult)/sizeof(TmpResult[0]) + 1) &&
663 "out-of-bound access");
666 SimpVect.push_back(ConstAdd);
669 if (!SimpVect.empty())
670 Result = createNaryFAdd(SimpVect, InstrQuota);
672 // The addition is folded to 0.0.
673 Result = ConstantFP::get(Instr->getType(), 0.0);
679 Value *FAddCombine::createNaryFAdd
680 (const AddendVect &Opnds, unsigned InstrQuota) {
681 assert(!Opnds.empty() && "Expect at least one addend");
683 // Step 1: Check if the # of instructions needed exceeds the quota.
685 unsigned InstrNeeded = calcInstrNumber(Opnds);
686 if (InstrNeeded > InstrQuota)
691 // step 2: Emit the N-ary addition.
692 // Note that at most three instructions are involved in Fadd-InstCombine: the
693 // addition in question, and at most two neighboring instructions.
694 // The resulting optimized addition should have at least one less instruction
695 // than the original addition expression tree. This implies that the resulting
696 // N-ary addition has at most two instructions, and we don't need to worry
697 // about tree-height when constructing the N-ary addition.
700 bool LastValNeedNeg = false;
702 // Iterate the addends, creating fadd/fsub using adjacent two addends.
703 for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end();
706 Value *V = createAddendVal(**I, NeedNeg);
709 LastValNeedNeg = NeedNeg;
713 if (LastValNeedNeg == NeedNeg) {
714 LastVal = createFAdd(LastVal, V);
719 LastVal = createFSub(V, LastVal);
721 LastVal = createFSub(LastVal, V);
723 LastValNeedNeg = false;
726 if (LastValNeedNeg) {
727 LastVal = createFNeg(LastVal);
731 assert(CreateInstrNum == InstrNeeded &&
732 "Inconsistent in instruction numbers");
738 Value *FAddCombine::createFSub
739 (Value *Opnd0, Value *Opnd1) {
740 Value *V = Builder->CreateFSub(Opnd0, Opnd1);
741 if (Instruction *I = dyn_cast<Instruction>(V))
742 createInstPostProc(I);
746 Value *FAddCombine::createFNeg(Value *V) {
747 Value *Zero = cast<Value>(ConstantFP::get(V->getType(), 0.0));
748 return createFSub(Zero, V);
751 Value *FAddCombine::createFAdd
752 (Value *Opnd0, Value *Opnd1) {
753 Value *V = Builder->CreateFAdd(Opnd0, Opnd1);
754 if (Instruction *I = dyn_cast<Instruction>(V))
755 createInstPostProc(I);
759 Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) {
760 Value *V = Builder->CreateFMul(Opnd0, Opnd1);
761 if (Instruction *I = dyn_cast<Instruction>(V))
762 createInstPostProc(I);
766 Value *FAddCombine::createFDiv(Value *Opnd0, Value *Opnd1) {
767 Value *V = Builder->CreateFDiv(Opnd0, Opnd1);
768 if (Instruction *I = dyn_cast<Instruction>(V))
769 createInstPostProc(I);
773 void FAddCombine::createInstPostProc(Instruction *NewInstr) {
774 NewInstr->setDebugLoc(Instr->getDebugLoc());
776 // Keep track of the number of instruction created.
779 // Propagate fast-math flags
780 NewInstr->setFastMathFlags(Instr->getFastMathFlags());
783 // Return the number of instruction needed to emit the N-ary addition.
784 // NOTE: Keep this function in sync with createAddendVal().
785 unsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) {
786 unsigned OpndNum = Opnds.size();
787 unsigned InstrNeeded = OpndNum - 1;
789 // The number of addends in the form of "(-1)*x".
790 unsigned NegOpndNum = 0;
792 // Adjust the number of instructions needed to emit the N-ary add.
793 for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end();
795 const FAddend *Opnd = *I;
796 if (Opnd->isConstant())
799 const FAddendCoef &CE = Opnd->getCoef();
800 if (CE.isMinusOne() || CE.isMinusTwo())
803 // Let the addend be "c * x". If "c == +/-1", the value of the addend
804 // is immediately available; otherwise, it needs exactly one instruction
805 // to evaluate the value.
806 if (!CE.isMinusOne() && !CE.isOne())
809 if (NegOpndNum == OpndNum)
814 // Input Addend Value NeedNeg(output)
815 // ================================================================
816 // Constant C C false
817 // <+/-1, V> V coefficient is -1
818 // <2/-2, V> "fadd V, V" coefficient is -2
819 // <C, V> "fmul V, C" false
821 // NOTE: Keep this function in sync with FAddCombine::calcInstrNumber.
822 Value *FAddCombine::createAddendVal
823 (const FAddend &Opnd, bool &NeedNeg) {
824 const FAddendCoef &Coeff = Opnd.getCoef();
826 if (Opnd.isConstant()) {
828 return Coeff.getValue(Instr->getType());
831 Value *OpndVal = Opnd.getSymVal();
833 if (Coeff.isMinusOne() || Coeff.isOne()) {
834 NeedNeg = Coeff.isMinusOne();
838 if (Coeff.isTwo() || Coeff.isMinusTwo()) {
839 NeedNeg = Coeff.isMinusTwo();
840 return createFAdd(OpndVal, OpndVal);
844 return createFMul(OpndVal, Coeff.getValue(Instr->getType()));
847 /// AddOne - Add one to a ConstantInt.
848 static Constant *AddOne(Constant *C) {
849 return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
852 /// SubOne - Subtract one from a ConstantInt.
853 static Constant *SubOne(ConstantInt *C) {
854 return ConstantInt::get(C->getContext(), C->getValue()-1);
858 // dyn_castFoldableMul - If this value is a multiply that can be folded into
859 // other computations (because it has a constant operand), return the
860 // non-constant operand of the multiply, and set CST to point to the multiplier.
861 // Otherwise, return null.
863 static inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) {
864 if (!V->hasOneUse() || !V->getType()->isIntegerTy())
867 Instruction *I = dyn_cast<Instruction>(V);
868 if (I == 0) return 0;
870 if (I->getOpcode() == Instruction::Mul)
871 if ((CST = dyn_cast<ConstantInt>(I->getOperand(1))))
872 return I->getOperand(0);
873 if (I->getOpcode() == Instruction::Shl)
874 if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) {
875 // The multiplier is really 1 << CST.
876 uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
877 uint32_t CSTVal = CST->getLimitedValue(BitWidth);
878 CST = ConstantInt::get(V->getType()->getContext(),
879 APInt(BitWidth, 1).shl(CSTVal));
880 return I->getOperand(0);
886 /// WillNotOverflowSignedAdd - Return true if we can prove that:
887 /// (sext (add LHS, RHS)) === (add (sext LHS), (sext RHS))
888 /// This basically requires proving that the add in the original type would not
889 /// overflow to change the sign bit or have a carry out.
890 bool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS) {
891 // There are different heuristics we can use for this. Here are some simple
894 // Add has the property that adding any two 2's complement numbers can only
895 // have one carry bit which can change a sign. As such, if LHS and RHS each
896 // have at least two sign bits, we know that the addition of the two values
897 // will sign extend fine.
898 if (ComputeNumSignBits(LHS) > 1 && ComputeNumSignBits(RHS) > 1)
902 // If one of the operands only has one non-zero bit, and if the other operand
903 // has a known-zero bit in a more significant place than it (not including the
904 // sign bit) the ripple may go up to and fill the zero, but won't change the
905 // sign. For example, (X & ~4) + 1.
912 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
913 bool Changed = SimplifyAssociativeOrCommutative(I);
914 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
916 if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(),
917 I.hasNoUnsignedWrap(), TD))
918 return ReplaceInstUsesWith(I, V);
920 // (A*B)+(A*C) -> A*(B+C) etc
921 if (Value *V = SimplifyUsingDistributiveLaws(I))
922 return ReplaceInstUsesWith(I, V);
924 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
925 // X + (signbit) --> X ^ signbit
926 const APInt &Val = CI->getValue();
928 return BinaryOperator::CreateXor(LHS, RHS);
930 // See if SimplifyDemandedBits can simplify this. This handles stuff like
931 // (X & 254)+1 -> (X&254)|1
932 if (SimplifyDemandedInstructionBits(I))
935 // zext(bool) + C -> bool ? C + 1 : C
936 if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS))
937 if (ZI->getSrcTy()->isIntegerTy(1))
938 return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI);
940 Value *XorLHS = 0; ConstantInt *XorRHS = 0;
941 if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) {
942 uint32_t TySizeBits = I.getType()->getScalarSizeInBits();
943 const APInt &RHSVal = CI->getValue();
944 unsigned ExtendAmt = 0;
945 // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext.
946 // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext.
947 if (XorRHS->getValue() == -RHSVal) {
948 if (RHSVal.isPowerOf2())
949 ExtendAmt = TySizeBits - RHSVal.logBase2() - 1;
950 else if (XorRHS->getValue().isPowerOf2())
951 ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1;
955 APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt);
956 if (!MaskedValueIsZero(XorLHS, Mask))
961 Constant *ShAmt = ConstantInt::get(I.getType(), ExtendAmt);
962 Value *NewShl = Builder->CreateShl(XorLHS, ShAmt, "sext");
963 return BinaryOperator::CreateAShr(NewShl, ShAmt);
966 // If this is a xor that was canonicalized from a sub, turn it back into
967 // a sub and fuse this add with it.
968 if (LHS->hasOneUse() && (XorRHS->getValue()+1).isPowerOf2()) {
969 IntegerType *IT = cast<IntegerType>(I.getType());
970 APInt LHSKnownOne(IT->getBitWidth(), 0);
971 APInt LHSKnownZero(IT->getBitWidth(), 0);
972 ComputeMaskedBits(XorLHS, LHSKnownZero, LHSKnownOne);
973 if ((XorRHS->getValue() | LHSKnownZero).isAllOnesValue())
974 return BinaryOperator::CreateSub(ConstantExpr::getAdd(XorRHS, CI),
977 // (X + signbit) + C could have gotten canonicalized to (X ^ signbit) + C,
978 // transform them into (X + (signbit ^ C))
979 if (XorRHS->getValue().isSignBit())
980 return BinaryOperator::CreateAdd(XorLHS,
981 ConstantExpr::getXor(XorRHS, CI));
985 if (isa<Constant>(RHS) && isa<PHINode>(LHS))
986 if (Instruction *NV = FoldOpIntoPhi(I))
989 if (I.getType()->isIntegerTy(1))
990 return BinaryOperator::CreateXor(LHS, RHS);
994 BinaryOperator *New =
995 BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1));
996 New->setHasNoSignedWrap(I.hasNoSignedWrap());
997 New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1002 // -A + -B --> -(A + B)
1003 if (Value *LHSV = dyn_castNegVal(LHS)) {
1004 if (!isa<Constant>(RHS))
1005 if (Value *RHSV = dyn_castNegVal(RHS)) {
1006 Value *NewAdd = Builder->CreateAdd(LHSV, RHSV, "sum");
1007 return BinaryOperator::CreateNeg(NewAdd);
1010 return BinaryOperator::CreateSub(RHS, LHSV);
1014 if (!isa<Constant>(RHS))
1015 if (Value *V = dyn_castNegVal(RHS))
1016 return BinaryOperator::CreateSub(LHS, V);
1020 if (Value *X = dyn_castFoldableMul(LHS, C2)) {
1021 if (X == RHS) // X*C + X --> X * (C+1)
1022 return BinaryOperator::CreateMul(RHS, AddOne(C2));
1024 // X*C1 + X*C2 --> X * (C1+C2)
1026 if (X == dyn_castFoldableMul(RHS, C1))
1027 return BinaryOperator::CreateMul(X, ConstantExpr::getAdd(C1, C2));
1030 // X + X*C --> X * (C+1)
1031 if (dyn_castFoldableMul(RHS, C2) == LHS)
1032 return BinaryOperator::CreateMul(LHS, AddOne(C2));
1034 // A+B --> A|B iff A and B have no bits set in common.
1035 if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
1036 APInt LHSKnownOne(IT->getBitWidth(), 0);
1037 APInt LHSKnownZero(IT->getBitWidth(), 0);
1038 ComputeMaskedBits(LHS, LHSKnownZero, LHSKnownOne);
1039 if (LHSKnownZero != 0) {
1040 APInt RHSKnownOne(IT->getBitWidth(), 0);
1041 APInt RHSKnownZero(IT->getBitWidth(), 0);
1042 ComputeMaskedBits(RHS, RHSKnownZero, RHSKnownOne);
1044 // No bits in common -> bitwise or.
1045 if ((LHSKnownZero|RHSKnownZero).isAllOnesValue())
1046 return BinaryOperator::CreateOr(LHS, RHS);
1050 // W*X + Y*Z --> W * (X+Z) iff W == Y
1052 Value *W, *X, *Y, *Z;
1053 if (match(LHS, m_Mul(m_Value(W), m_Value(X))) &&
1054 match(RHS, m_Mul(m_Value(Y), m_Value(Z)))) {
1058 } else if (Y == X) {
1060 } else if (X == Z) {
1067 Value *NewAdd = Builder->CreateAdd(X, Z, LHS->getName());
1068 return BinaryOperator::CreateMul(W, NewAdd);
1073 if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
1075 if (match(LHS, m_Not(m_Value(X)))) // ~X + C --> (C-1) - X
1076 return BinaryOperator::CreateSub(SubOne(CRHS), X);
1078 // (X & FF00) + xx00 -> (X+xx00) & FF00
1079 if (LHS->hasOneUse() &&
1080 match(LHS, m_And(m_Value(X), m_ConstantInt(C2))) &&
1081 CRHS->getValue() == (CRHS->getValue() & C2->getValue())) {
1082 // See if all bits from the first bit set in the Add RHS up are included
1083 // in the mask. First, get the rightmost bit.
1084 const APInt &AddRHSV = CRHS->getValue();
1086 // Form a mask of all bits from the lowest bit added through the top.
1087 APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1));
1089 // See if the and mask includes all of these bits.
1090 APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue());
1092 if (AddRHSHighBits == AddRHSHighBitsAnd) {
1093 // Okay, the xform is safe. Insert the new add pronto.
1094 Value *NewAdd = Builder->CreateAdd(X, CRHS, LHS->getName());
1095 return BinaryOperator::CreateAnd(NewAdd, C2);
1099 // Try to fold constant add into select arguments.
1100 if (SelectInst *SI = dyn_cast<SelectInst>(LHS))
1101 if (Instruction *R = FoldOpIntoSelect(I, SI))
1105 // add (select X 0 (sub n A)) A --> select X A n
1107 SelectInst *SI = dyn_cast<SelectInst>(LHS);
1110 SI = dyn_cast<SelectInst>(RHS);
1113 if (SI && SI->hasOneUse()) {
1114 Value *TV = SI->getTrueValue();
1115 Value *FV = SI->getFalseValue();
1118 // Can we fold the add into the argument of the select?
1119 // We check both true and false select arguments for a matching subtract.
1120 if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A))))
1121 // Fold the add into the true select value.
1122 return SelectInst::Create(SI->getCondition(), N, A);
1124 if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A))))
1125 // Fold the add into the false select value.
1126 return SelectInst::Create(SI->getCondition(), A, N);
1130 // Check for (add (sext x), y), see if we can merge this into an
1131 // integer add followed by a sext.
1132 if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) {
1133 // (add (sext x), cst) --> (sext (add x, cst'))
1134 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) {
1136 ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType());
1137 if (LHSConv->hasOneUse() &&
1138 ConstantExpr::getSExt(CI, I.getType()) == RHSC &&
1139 WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) {
1140 // Insert the new, smaller add.
1141 Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
1143 return new SExtInst(NewAdd, I.getType());
1147 // (add (sext x), (sext y)) --> (sext (add int x, y))
1148 if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) {
1149 // Only do this if x/y have the same type, if at last one of them has a
1150 // single use (so we don't increase the number of sexts), and if the
1151 // integer add will not overflow.
1152 if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&&
1153 (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
1154 WillNotOverflowSignedAdd(LHSConv->getOperand(0),
1155 RHSConv->getOperand(0))) {
1156 // Insert the new integer add.
1157 Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
1158 RHSConv->getOperand(0), "addconv");
1159 return new SExtInst(NewAdd, I.getType());
1164 // Check for (x & y) + (x ^ y)
1166 Value *A = 0, *B = 0;
1167 if (match(RHS, m_Xor(m_Value(A), m_Value(B))) &&
1168 (match(LHS, m_And(m_Specific(A), m_Specific(B))) ||
1169 match(LHS, m_And(m_Specific(B), m_Specific(A)))))
1170 return BinaryOperator::CreateOr(A, B);
1172 if (match(LHS, m_Xor(m_Value(A), m_Value(B))) &&
1173 (match(RHS, m_And(m_Specific(A), m_Specific(B))) ||
1174 match(RHS, m_And(m_Specific(B), m_Specific(A)))))
1175 return BinaryOperator::CreateOr(A, B);
1178 return Changed ? &I : 0;
1181 Instruction *InstCombiner::visitFAdd(BinaryOperator &I) {
1182 bool Changed = SimplifyAssociativeOrCommutative(I);
1183 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1185 if (Value *V = SimplifyFAddInst(LHS, RHS, I.getFastMathFlags(), TD))
1186 return ReplaceInstUsesWith(I, V);
1188 if (isa<Constant>(RHS) && isa<PHINode>(LHS))
1189 if (Instruction *NV = FoldOpIntoPhi(I))
1193 // -A + -B --> -(A + B)
1194 if (Value *LHSV = dyn_castFNegVal(LHS))
1195 return BinaryOperator::CreateFSub(RHS, LHSV);
1198 if (!isa<Constant>(RHS))
1199 if (Value *V = dyn_castFNegVal(RHS))
1200 return BinaryOperator::CreateFSub(LHS, V);
1202 // Check for (fadd double (sitofp x), y), see if we can merge this into an
1203 // integer add followed by a promotion.
1204 if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) {
1205 // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst))
1206 // ... if the constant fits in the integer value. This is useful for things
1207 // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer
1208 // requires a constant pool load, and generally allows the add to be better
1210 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) {
1212 ConstantExpr::getFPToSI(CFP, LHSConv->getOperand(0)->getType());
1213 if (LHSConv->hasOneUse() &&
1214 ConstantExpr::getSIToFP(CI, I.getType()) == CFP &&
1215 WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) {
1216 // Insert the new integer add.
1217 Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
1219 return new SIToFPInst(NewAdd, I.getType());
1223 // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y))
1224 if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) {
1225 // Only do this if x/y have the same type, if at last one of them has a
1226 // single use (so we don't increase the number of int->fp conversions),
1227 // and if the integer add will not overflow.
1228 if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&&
1229 (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
1230 WillNotOverflowSignedAdd(LHSConv->getOperand(0),
1231 RHSConv->getOperand(0))) {
1232 // Insert the new integer add.
1233 Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
1234 RHSConv->getOperand(0),"addconv");
1235 return new SIToFPInst(NewAdd, I.getType());
1240 // select C, 0, B + select C, A, 0 -> select C, A, B
1242 Value *A1, *B1, *C1, *A2, *B2, *C2;
1243 if (match(LHS, m_Select(m_Value(C1), m_Value(A1), m_Value(B1))) &&
1244 match(RHS, m_Select(m_Value(C2), m_Value(A2), m_Value(B2)))) {
1246 Constant *Z1=0, *Z2=0;
1247 Value *A, *B, *C=C1;
1248 if (match(A1, m_AnyZero()) && match(B2, m_AnyZero())) {
1249 Z1 = dyn_cast<Constant>(A1); A = A2;
1250 Z2 = dyn_cast<Constant>(B2); B = B1;
1251 } else if (match(B1, m_AnyZero()) && match(A2, m_AnyZero())) {
1252 Z1 = dyn_cast<Constant>(B1); B = B2;
1253 Z2 = dyn_cast<Constant>(A2); A = A1;
1257 (I.hasNoSignedZeros() ||
1258 (Z1->isNegativeZeroValue() && Z2->isNegativeZeroValue()))) {
1259 return SelectInst::Create(C, A, B);
1265 if (I.hasUnsafeAlgebra()) {
1266 if (Value *V = FAddCombine(Builder).simplify(&I))
1267 return ReplaceInstUsesWith(I, V);
1270 return Changed ? &I : 0;
1274 /// Optimize pointer differences into the same array into a size. Consider:
1275 /// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer
1276 /// operands to the ptrtoint instructions for the LHS/RHS of the subtract.
1278 Value *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS,
1280 assert(TD && "Must have target data info for this");
1282 // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize
1284 bool Swapped = false;
1285 GEPOperator *GEP1 = 0, *GEP2 = 0;
1287 // For now we require one side to be the base pointer "A" or a constant
1288 // GEP derived from it.
1289 if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
1291 if (LHSGEP->getOperand(0) == RHS) {
1294 } else if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
1295 // (gep X, ...) - (gep X, ...)
1296 if (LHSGEP->getOperand(0)->stripPointerCasts() ==
1297 RHSGEP->getOperand(0)->stripPointerCasts()) {
1305 if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
1307 if (RHSGEP->getOperand(0) == LHS) {
1310 } else if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
1311 // (gep X, ...) - (gep X, ...)
1312 if (RHSGEP->getOperand(0)->stripPointerCasts() ==
1313 LHSGEP->getOperand(0)->stripPointerCasts()) {
1321 // Avoid duplicating the arithmetic if GEP2 has non-constant indices and
1324 (GEP2 != 0 && !GEP2->hasAllConstantIndices() && !GEP2->hasOneUse()))
1327 // Emit the offset of the GEP and an intptr_t.
1328 Value *Result = EmitGEPOffset(GEP1);
1330 // If we had a constant expression GEP on the other side offsetting the
1331 // pointer, subtract it from the offset we have.
1333 Value *Offset = EmitGEPOffset(GEP2);
1334 Result = Builder->CreateSub(Result, Offset);
1337 // If we have p - gep(p, ...) then we have to negate the result.
1339 Result = Builder->CreateNeg(Result, "diff.neg");
1341 return Builder->CreateIntCast(Result, Ty, true);
1345 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
1346 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1348 if (Value *V = SimplifySubInst(Op0, Op1, I.hasNoSignedWrap(),
1349 I.hasNoUnsignedWrap(), TD))
1350 return ReplaceInstUsesWith(I, V);
1352 // (A*B)-(A*C) -> A*(B-C) etc
1353 if (Value *V = SimplifyUsingDistributiveLaws(I))
1354 return ReplaceInstUsesWith(I, V);
1356 // If this is a 'B = x-(-A)', change to B = x+A. This preserves NSW/NUW.
1357 if (Value *V = dyn_castNegVal(Op1)) {
1358 BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V);
1359 Res->setHasNoSignedWrap(I.hasNoSignedWrap());
1360 Res->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1364 if (I.getType()->isIntegerTy(1))
1365 return BinaryOperator::CreateXor(Op0, Op1);
1367 // Replace (-1 - A) with (~A).
1368 if (match(Op0, m_AllOnes()))
1369 return BinaryOperator::CreateNot(Op1);
1371 if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) {
1372 // C - ~X == X + (1+C)
1374 if (match(Op1, m_Not(m_Value(X))))
1375 return BinaryOperator::CreateAdd(X, AddOne(C));
1377 // -(X >>u 31) -> (X >>s 31)
1378 // -(X >>s 31) -> (X >>u 31)
1380 Value *X; ConstantInt *CI;
1381 if (match(Op1, m_LShr(m_Value(X), m_ConstantInt(CI))) &&
1382 // Verify we are shifting out everything but the sign bit.
1383 CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1)
1384 return BinaryOperator::CreateAShr(X, CI);
1386 if (match(Op1, m_AShr(m_Value(X), m_ConstantInt(CI))) &&
1387 // Verify we are shifting out everything but the sign bit.
1388 CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1)
1389 return BinaryOperator::CreateLShr(X, CI);
1392 // Try to fold constant sub into select arguments.
1393 if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1394 if (Instruction *R = FoldOpIntoSelect(I, SI))
1397 // C-(X+C2) --> (C-C2)-X
1399 if (match(Op1, m_Add(m_Value(X), m_ConstantInt(C2))))
1400 return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
1402 if (SimplifyDemandedInstructionBits(I))
1405 // Fold (sub 0, (zext bool to B)) --> (sext bool to B)
1406 if (C->isZero() && match(Op1, m_ZExt(m_Value(X))))
1407 if (X->getType()->isIntegerTy(1))
1408 return CastInst::CreateSExtOrBitCast(X, Op1->getType());
1410 // Fold (sub 0, (sext bool to B)) --> (zext bool to B)
1411 if (C->isZero() && match(Op1, m_SExt(m_Value(X))))
1412 if (X->getType()->isIntegerTy(1))
1413 return CastInst::CreateZExtOrBitCast(X, Op1->getType());
1418 // X-(X+Y) == -Y X-(Y+X) == -Y
1419 if (match(Op1, m_Add(m_Specific(Op0), m_Value(Y))) ||
1420 match(Op1, m_Add(m_Value(Y), m_Specific(Op0))))
1421 return BinaryOperator::CreateNeg(Y);
1424 if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))
1425 return BinaryOperator::CreateNeg(Y);
1428 if (Op1->hasOneUse()) {
1429 Value *X = 0, *Y = 0, *Z = 0;
1431 ConstantInt *CI = 0;
1433 // (X - (Y - Z)) --> (X + (Z - Y)).
1434 if (match(Op1, m_Sub(m_Value(Y), m_Value(Z))))
1435 return BinaryOperator::CreateAdd(Op0,
1436 Builder->CreateSub(Z, Y, Op1->getName()));
1438 // (X - (X & Y)) --> (X & ~Y)
1440 if (match(Op1, m_And(m_Value(Y), m_Specific(Op0))) ||
1441 match(Op1, m_And(m_Specific(Op0), m_Value(Y))))
1442 return BinaryOperator::CreateAnd(Op0,
1443 Builder->CreateNot(Y, Y->getName() + ".not"));
1445 // 0 - (X sdiv C) -> (X sdiv -C)
1446 if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) &&
1447 match(Op0, m_Zero()))
1448 return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C));
1450 // 0 - (X << Y) -> (-X << Y) when X is freely negatable.
1451 if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero()))
1452 if (Value *XNeg = dyn_castNegVal(X))
1453 return BinaryOperator::CreateShl(XNeg, Y);
1455 // X - X*C --> X * (1-C)
1456 if (match(Op1, m_Mul(m_Specific(Op0), m_ConstantInt(CI)))) {
1457 Constant *CP1 = ConstantExpr::getSub(ConstantInt::get(I.getType(),1), CI);
1458 return BinaryOperator::CreateMul(Op0, CP1);
1461 // X - X<<C --> X * (1-(1<<C))
1462 if (match(Op1, m_Shl(m_Specific(Op0), m_ConstantInt(CI)))) {
1463 Constant *One = ConstantInt::get(I.getType(), 1);
1464 C = ConstantExpr::getSub(One, ConstantExpr::getShl(One, CI));
1465 return BinaryOperator::CreateMul(Op0, C);
1468 // X - A*-B -> X + A*B
1469 // X - -A*B -> X + A*B
1471 if (match(Op1, m_Mul(m_Value(A), m_Neg(m_Value(B)))) ||
1472 match(Op1, m_Mul(m_Neg(m_Value(A)), m_Value(B))))
1473 return BinaryOperator::CreateAdd(Op0, Builder->CreateMul(A, B));
1475 // X - A*CI -> X + A*-CI
1476 // X - CI*A -> X + A*-CI
1477 if (match(Op1, m_Mul(m_Value(A), m_ConstantInt(CI))) ||
1478 match(Op1, m_Mul(m_ConstantInt(CI), m_Value(A)))) {
1479 Value *NewMul = Builder->CreateMul(A, ConstantExpr::getNeg(CI));
1480 return BinaryOperator::CreateAdd(Op0, NewMul);
1485 if (Value *X = dyn_castFoldableMul(Op0, C1)) {
1486 if (X == Op1) // X*C - X --> X * (C-1)
1487 return BinaryOperator::CreateMul(Op1, SubOne(C1));
1489 ConstantInt *C2; // X*C1 - X*C2 -> X * (C1-C2)
1490 if (X == dyn_castFoldableMul(Op1, C2))
1491 return BinaryOperator::CreateMul(X, ConstantExpr::getSub(C1, C2));
1494 // Optimize pointer differences into the same array into a size. Consider:
1495 // &A[10] - &A[0]: we should compile this to "10".
1497 Value *LHSOp, *RHSOp;
1498 if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
1499 match(Op1, m_PtrToInt(m_Value(RHSOp))))
1500 if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
1501 return ReplaceInstUsesWith(I, Res);
1503 // trunc(p)-trunc(q) -> trunc(p-q)
1504 if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) &&
1505 match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp)))))
1506 if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
1507 return ReplaceInstUsesWith(I, Res);
1513 Instruction *InstCombiner::visitFSub(BinaryOperator &I) {
1514 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1516 if (Value *V = SimplifyFSubInst(Op0, Op1, I.getFastMathFlags(), TD))
1517 return ReplaceInstUsesWith(I, V);
1519 // If this is a 'B = x-(-A)', change to B = x+A...
1520 if (Value *V = dyn_castFNegVal(Op1))
1521 return BinaryOperator::CreateFAdd(Op0, V);
1523 if (I.hasUnsafeAlgebra()) {
1524 if (Value *V = FAddCombine(Builder).simplify(&I))
1525 return ReplaceInstUsesWith(I, V);