lib/Transforms/InstCombine/InstCombineAddSub.cpp

   1 //===- InstCombineAddSub.cpp ----------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the visit functions for add, fadd, sub, and fsub.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  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"
  19 using namespace llvm;
  20 using namespace PatternMatch;
  21
  22 namespace {
  23
  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).
  29   ///
  30   class FAddendCoef {
  31   public:
  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.
  37     //
  38     FAddendCoef() : IsFp(false), BufHasFpVal(false), IntVal(0) {}
  39     ~FAddendCoef();
  40
  41     void set(short C) {
  42       assert(!insaneIntVal(C) && "Insane coefficient");
  43       IsFp = false; IntVal = C;
  44     }
  45
  46     void set(const APFloat& C);
  47
  48     void negate();
  49
  50     bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); }
  51     Value *getValue(Type *) const;
  52
  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);
  59
  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; }
  64
  65   private:
  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]); }
  71
  72     const APFloat &getFpVal(void) const {
  73       assert(IsFp && BufHasFpVal && "Incorret state");
  74       return *getFpValPtr();
  75     }
  76
  77     APFloat &getFpVal(void)
  78       { assert(IsFp && BufHasFpVal && "Incorret state"); return *getFpValPtr(); }
  79
  80     bool isInt() const { return !IsFp; }
  81
  82   private:
  83
  84     bool IsFp;
  85
  86     // True iff FpValBuf contains an instance of APFloat.
  87     bool BufHasFpVal;
  88
  89     // The integer coefficient of an individual addend is either 1 or -1,
  90     // and we try to simplify at most 4 addends from neighboring at most
  91     // two instructions. So the range of <IntVal> falls in [-4, 4]. APInt
  92     // is overkill of this end.
  93     short IntVal;
  94
  95     AlignedCharArrayUnion<APFloat> FpValBuf;
  96   };
  97
  98   /// FAddend is used to represent floating-point addend. An addend is
  99   /// represented as <C, V>, where the V is a symbolic value, and C is a
 100   /// constant coefficient. A constant addend is represented as <C, 0>.
 101   ///
 102   class FAddend {
 103   public:
 104     FAddend() { Val = 0; }
 105
 106     Value *getSymVal (void) const { return Val; }
 107     const FAddendCoef &getCoef(void) const { return Coeff; }
 108
 109     bool isConstant() const { return Val == 0; }
 110     bool isZero() const { return Coeff.isZero(); }
 111
 112     void set(short Coefficient, Value *V) { Coeff.set(Coefficient), Val = V; }
 113     void set(const APFloat& Coefficient, Value *V)
 114       { Coeff.set(Coefficient); Val = V; }
 115     void set(const ConstantFP* Coefficient, Value *V)
 116       { Coeff.set(Coefficient->getValueAPF()); Val = V; }
 117
 118     void negate() { Coeff.negate(); }
 119
 120     /// Drill down the U-D chain one step to find the definition of V, and
 121     /// try to break the definition into one or two addends.
 122     static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1);
 123
 124     /// Similar to FAddend::drillDownOneStep() except that the value being
 125     /// splitted is the addend itself.
 126     unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const;
 127
 128     void operator+=(const FAddend &T) {
 129       assert((Val == T.Val) && "Symbolic-values disagree");
 130       Coeff += T.Coeff;
 131     }
 132
 133   private:
 134     void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; }
 135
 136     // This addend has the value of "Coeff * Val".
 137     Value *Val;
 138     FAddendCoef Coeff;
 139   };
 140
 141   /// FAddCombine is the class for optimizing an unsafe fadd/fsub along
 142   /// with its neighboring at most two instructions.
 143   ///
 144   class FAddCombine {
 145   public:
 146     FAddCombine(InstCombiner::BuilderTy *B) : Builder(B), Instr(0) {}
 147     Value *simplify(Instruction *FAdd);
 148
 149   private:
 150     typedef SmallVector<const FAddend*, 4> AddendVect;
 151
 152     Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota);
 153
 154     /// Convert given addend to a Value
 155     Value *createAddendVal(const FAddend &A, bool& NeedNeg);
 156
 157     /// Return the number of instructions needed to emit the N-ary addition.
 158     unsigned calcInstrNumber(const AddendVect& Vect);
 159     Value *createFSub(Value *Opnd0, Value *Opnd1);
 160     Value *createFAdd(Value *Opnd0, Value *Opnd1);
 161     Value *createFMul(Value *Opnd0, Value *Opnd1);
 162     Value *createFNeg(Value *V);
 163     Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota);
 164     void createInstPostProc(Instruction *NewInst);
 165
 166     InstCombiner::BuilderTy *Builder;
 167     Instruction *Instr;
 168
 169   private:
 170      // Debugging stuff are clustered here.
 171     #ifndef NDEBUG
 172       unsigned CreateInstrNum;
 173       void initCreateInstNum() { CreateInstrNum = 0; }
 174       void incCreateInstNum() { CreateInstrNum++; }
 175     #else
 176       void initCreateInstNum() {}
 177       void incCreateInstNum() {}
 178     #endif
 179   };
 180 }
 181
 182 //===----------------------------------------------------------------------===//
 183 //
 184 // Implementation of
 185 //    {FAddendCoef, FAddend, FAddition, FAddCombine}.
 186 //
 187 //===----------------------------------------------------------------------===//
 188 FAddendCoef::~FAddendCoef() {
 189   if (BufHasFpVal)
 190     getFpValPtr()->~APFloat();
 191 }
 192
 193 void FAddendCoef::set(const APFloat& C) {
 194   APFloat *P = getFpValPtr();
 195
 196   if (isInt()) {
 197     // As the buffer is meanless byte stream, we cannot call
 198     // APFloat::operator=().
 199     new(P) APFloat(C);
 200   } else
 201     *P = C;
 202
 203   IsFp = BufHasFpVal = true;
 204 }
 205
 206 void FAddendCoef::operator=(const FAddendCoef& That) {
 207   if (That.isInt())
 208     set(That.IntVal);
 209   else
 210     set(That.getFpVal());
 211 }
 212
 213 void FAddendCoef::operator+=(const FAddendCoef &That) {
 214   enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven;
 215   if (isInt() == That.isInt()) {
 216     if (isInt())
 217       IntVal += That.IntVal;
 218     else
 219       getFpVal().add(That.getFpVal(), RndMode);
 220     return;
 221   }
 222
 223   if (isInt()) {
 224     const APFloat &T = That.getFpVal();
 225     set(T);
 226     getFpVal().add(APFloat(T.getSemantics(), IntVal), RndMode);
 227     return;
 228   }
 229
 230   APFloat &T = getFpVal();
 231   T.add(APFloat(T.getSemantics(), That.IntVal), RndMode);
 232 }
 233
 234 void FAddendCoef::operator-=(const FAddendCoef &That) {
 235   enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven;
 236   if (isInt() == That.isInt()) {
 237     if (isInt())
 238       IntVal -= That.IntVal;
 239     else
 240       getFpVal().subtract(That.getFpVal(), RndMode);
 241     return;
 242   }
 243
 244   if (isInt()) {
 245     const APFloat &T = That.getFpVal();
 246     set(T);
 247     getFpVal().subtract(APFloat(T.getSemantics(), IntVal), RndMode);
 248     return;
 249   }
 250
 251   APFloat &T = getFpVal();
 252   T.subtract(APFloat(T.getSemantics(), IntVal), RndMode);
 253 }
 254
 255 void FAddendCoef::operator*=(const FAddendCoef &That) {
 256   if (That.isOne())
 257     return;
 258
 259   if (That.isMinusOne()) {
 260     negate();
 261     return;
 262   }
 263
 264   if (isInt() && That.isInt()) {
 265     int Res = IntVal * (int)That.IntVal;
 266     assert(!insaneIntVal(Res) && "Insane int value");
 267     IntVal = Res;
 268     return;
 269   }
 270
 271   const fltSemantics &Semantic =
 272     isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics();
 273
 274   if (isInt())
 275     set(APFloat(Semantic, IntVal));
 276   APFloat &F0 = getFpVal();
 277
 278   if (That.isInt())
 279     F0.multiply(APFloat(Semantic, That.IntVal), APFloat::rmNearestTiesToEven);
 280   else
 281     F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven);
 282
 283   return;
 284 }
 285
 286 void FAddendCoef::negate() {
 287   if (isInt())
 288     IntVal = 0 - IntVal;
 289   else
 290     getFpVal().changeSign();
 291 }
 292
 293 Value *FAddendCoef::getValue(Type *Ty) const {
 294   return isInt() ?
 295     ConstantFP::get(Ty, float(IntVal)) :
 296     ConstantFP::get(Ty->getContext(), getFpVal());
 297 }
 298
 299 // The definition of <Val>     Addends
 300 // =========================================
 301 //  A + B                     <1, A>, <1,B>
 302 //  A - B                     <1, A>, <1,B>
 303 //  0 - B                     <-1, B>
 304 //  C * A,                    <C, A>
 305 //  A + C                     <1, A> <C, NULL>
 306 //  0 +/- 0                   <0, NULL> (corner case)
 307 //
 308 // Legend: A and B are not constant, C is constant
 309 //
 310 unsigned FAddend::drillValueDownOneStep
 311   (Value *Val, FAddend &Addend0, FAddend &Addend1) {
 312   Instruction *I = 0;
 313   if (Val == 0 || !(I = dyn_cast<Instruction>(Val)))
 314     return 0;
 315
 316   unsigned Opcode = I->getOpcode();
 317
 318   if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) {
 319     ConstantFP *C0, *C1;
 320     Value *Opnd0 = I->getOperand(0);
 321     Value *Opnd1 = I->getOperand(1);
 322     if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && C0->isZero())
 323       Opnd0 = 0;
 324
 325     if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && C1->isZero())
 326       Opnd1 = 0;
 327
 328     if (Opnd0) {
 329       if (!C0)
 330         Addend0.set(1, Opnd0);
 331       else
 332         Addend0.set(C0, 0);
 333     }
 334
 335     if (Opnd1) {
 336       FAddend &Addend = Opnd0 ? Addend1 : Addend0;
 337       if (!C1)
 338         Addend.set(1, Opnd1);
 339       else
 340         Addend.set(C1, 0);
 341       if (Opcode == Instruction::FSub)
 342         Addend.negate();
 343     }
 344
 345     if (Opnd0 || Opnd1)
 346       return Opnd0 && Opnd1 ? 2 : 1;
 347
 348     // Both operands are zero. Weird!
 349     Addend0.set(APFloat(C0->getValueAPF().getSemantics()), 0);
 350     return 1;
 351   }
 352
 353   if (I->getOpcode() == Instruction::FMul) {
 354     Value *V0 = I->getOperand(0);
 355     Value *V1 = I->getOperand(1);
 356     if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) {
 357       Addend0.set(C, V1);
 358       return 1;
 359     }
 360
 361     if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) {
 362       Addend0.set(C, V0);
 363       return 1;
 364     }
 365   }
 366
 367   return 0;
 368 }
 369
 370 // Try to break *this* addend into two addends. e.g. Suppose this addend is
 371 // <2.3, V>, and V = X + Y, by calling this function, we obtain two addends,
 372 // i.e. <2.3, X> and <2.3, Y>.
 373 //
 374 unsigned FAddend::drillAddendDownOneStep
 375   (FAddend &Addend0, FAddend &Addend1) const {
 376   if (isConstant())
 377     return 0;
 378
 379   unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1);
 380   if (!BreakNum || Coeff.isOne())
 381     return BreakNum;
 382
 383   Addend0.Scale(Coeff);
 384
 385   if (BreakNum == 2)
 386     Addend1.Scale(Coeff);
 387
 388   return BreakNum;
 389 }
 390
 391 Value *FAddCombine::simplify(Instruction *I) {
 392   assert(I->hasUnsafeAlgebra() && "Should be in unsafe mode");
 393
 394   // Currently we are not able to handle vector type.
 395   if (I->getType()->isVectorTy())
 396     return 0;
 397
 398   assert((I->getOpcode() == Instruction::FAdd ||
 399           I->getOpcode() == Instruction::FSub) && "Expect add/sub");
 400
 401   // Save the instruction before calling other member-functions.
 402   Instr = I;
 403
 404   FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1;
 405
 406   unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1);
 407
 408   // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1.
 409   unsigned Opnd0_ExpNum = 0;
 410   unsigned Opnd1_ExpNum = 0;
 411
 412   if (!Opnd0.isConstant())
 413     Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1);
 414
 415   // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1.
 416   if (OpndNum == 2 && !Opnd1.isConstant())
 417     Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1);
 418
 419   // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1
 420   if (Opnd0_ExpNum && Opnd1_ExpNum) {
 421     AddendVect AllOpnds;
 422     AllOpnds.push_back(&Opnd0_0);
 423     AllOpnds.push_back(&Opnd1_0);
 424     if (Opnd0_ExpNum == 2)
 425       AllOpnds.push_back(&Opnd0_1);
 426     if (Opnd1_ExpNum == 2)
 427       AllOpnds.push_back(&Opnd1_1);
 428
 429     // Compute instruction quota. We should save at least one instruction.
 430     unsigned InstQuota = 0;
 431
 432     Value *V0 = I->getOperand(0);
 433     Value *V1 = I->getOperand(1);
 434     InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) &&
 435                  (!isa<Constant>(V1) && V1->hasOneUse())) ? 2 : 1;
 436
 437     if (Value *R = simplifyFAdd(AllOpnds, InstQuota))
 438       return R;
 439   }
 440
 441   if (OpndNum != 2) {
 442     // The input instruction is : "I=0.0 +/- V". If the "V" were able to be
 443     // splitted into two addends, say "V = X - Y", the instruction would have
 444     // been optimized into "I = Y - X" in the previous steps.
 445     //
 446     const FAddendCoef &CE = Opnd0.getCoef();
 447     return CE.isOne() ? Opnd0.getSymVal() : 0;
 448   }
 449
 450   // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1]
 451   if (Opnd1_ExpNum) {
 452     AddendVect AllOpnds;
 453     AllOpnds.push_back(&Opnd0);
 454     AllOpnds.push_back(&Opnd1_0);
 455     if (Opnd1_ExpNum == 2)
 456       AllOpnds.push_back(&Opnd1_1);
 457
 458     if (Value *R = simplifyFAdd(AllOpnds, 1))
 459       return R;
 460   }
 461
 462   // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1]
 463   if (Opnd0_ExpNum) {
 464     AddendVect AllOpnds;
 465     AllOpnds.push_back(&Opnd1);
 466     AllOpnds.push_back(&Opnd0_0);
 467     if (Opnd0_ExpNum == 2)
 468       AllOpnds.push_back(&Opnd0_1);
 469
 470     if (Value *R = simplifyFAdd(AllOpnds, 1))
 471       return R;
 472   }
 473
 474   return 0;
 475 }
 476
 477 Value *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) {
 478
 479   unsigned AddendNum = Addends.size();
 480   assert(AddendNum <= 4 && "Too many addends");
 481
 482   // For saving intermediate results;
 483   unsigned NextTmpIdx = 0;
 484   FAddend TmpResult[3];
 485
 486   // Points to the constant addend of the resulting simplified expression.
 487   // If the resulting expr has constant-addend, this constant-addend is
 488   // desirable to reside at the top of the resulting expression tree. Placing
 489   // constant close to supper-expr(s) will potentially reveal some optimization
 490   // opportunities in super-expr(s).
 491   //
 492   const FAddend *ConstAdd = 0;
 493
 494   // Simplified addends are placed <SimpVect>.
 495   AddendVect SimpVect;
 496
 497   // The outer loop works on one symbolic-value at a time. Suppose the input
 498   // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ...
 499   // The symbolic-values will be processed in this order: x, y, z.
 500   //
 501   for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) {
 502
 503     const FAddend *ThisAddend = Addends[SymIdx];
 504     if (!ThisAddend) {
 505       // This addend was processed before.
 506       continue;
 507     }
 508
 509     Value *Val = ThisAddend->getSymVal();
 510     unsigned StartIdx = SimpVect.size();
 511     SimpVect.push_back(ThisAddend);
 512
 513     // The inner loop collects addends sharing same symbolic-value, and these
 514     // addends will be later on folded into a single addend. Following above
 515     // example, if the symbolic value "y" is being processed, the inner loop
 516     // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will
 517     // be later on folded into "<b1+b2, y>".
 518     //
 519     for (unsigned SameSymIdx = SymIdx + 1;
 520          SameSymIdx < AddendNum; SameSymIdx++) {
 521       const FAddend *T = Addends[SameSymIdx];
 522       if (T && T->getSymVal() == Val) {
 523         // Set null such that next iteration of the outer loop will not process
 524         // this addend again.
 525         Addends[SameSymIdx] = 0;
 526         SimpVect.push_back(T);
 527       }
 528     }
 529
 530     // If multiple addends share same symbolic value, fold them together.
 531     if (StartIdx + 1 != SimpVect.size()) {
 532       FAddend &R = TmpResult[NextTmpIdx ++];
 533       R = *SimpVect[StartIdx];
 534       for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++)
 535         R += *SimpVect[Idx];
 536
 537       // Pop all addends being folded and push the resulting folded addend.
 538       SimpVect.resize(StartIdx);
 539       if (Val != 0) {
 540         if (!R.isZero()) {
 541           SimpVect.push_back(&R);
 542         }
 543       } else {
 544         // Don't push constant addend at this time. It will be the last element
 545         // of <SimpVect>.
 546         ConstAdd = &R;
 547       }
 548     }
 549   }
 550
 551   assert((NextTmpIdx <= sizeof(TmpResult)/sizeof(TmpResult[0]) + 1) &&
 552          "out-of-bound access");
 553
 554   if (ConstAdd)
 555     SimpVect.push_back(ConstAdd);
 556
 557   Value *Result;
 558   if (!SimpVect.empty())
 559     Result = createNaryFAdd(SimpVect, InstrQuota);
 560   else {
 561     // The addition is folded to 0.0.
 562     Result = ConstantFP::get(Instr->getType(), 0.0);
 563   }
 564
 565   return Result;
 566 }
 567
 568 Value *FAddCombine::createNaryFAdd
 569   (const AddendVect &Opnds, unsigned InstrQuota) {
 570   assert(!Opnds.empty() && "Expect at least one addend");
 571
 572   // Step 1: Check if the # of instructions needed exceeds the quota.
 573   //
 574   unsigned InstrNeeded = calcInstrNumber(Opnds);
 575   if (InstrNeeded > InstrQuota)
 576     return 0;
 577
 578   initCreateInstNum();
 579
 580   // step 2: Emit the N-ary addition.
 581   // Note that at most three instructions are involved in Fadd-InstCombine: the
 582   // addition in question, and at most two neighboring instructions.
 583   // The resulting optimized addition should have at least one less instruction
 584   // than the original addition expression tree. This implies that the resulting
 585   // N-ary addition has at most two instructions, and we don't need to worry
 586   // about tree-height when constructing the N-ary addition.
 587
 588   Value *LastVal = 0;
 589   bool LastValNeedNeg = false;
 590
 591   // Iterate the addends, creating fadd/fsub using adjacent two addends.
 592   for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end();
 593        I != E; I++) {
 594     bool NeedNeg;
 595     Value *V = createAddendVal(**I, NeedNeg);
 596     if (!LastVal) {
 597       LastVal = V;
 598       LastValNeedNeg = NeedNeg;
 599       continue;
 600     }
 601
 602     if (LastValNeedNeg == NeedNeg) {
 603       LastVal = createFAdd(LastVal, V);
 604       continue;
 605     }
 606
 607     if (LastValNeedNeg)
 608       LastVal = createFSub(V, LastVal);
 609     else
 610       LastVal = createFSub(LastVal, V);
 611
 612     LastValNeedNeg = false;
 613   }
 614
 615   if (LastValNeedNeg) {
 616     LastVal = createFNeg(LastVal);
 617   }
 618
 619   #ifndef NDEBUG
 620     assert(CreateInstrNum == InstrNeeded &&
 621            "Inconsistent in instruction numbers");
 622   #endif
 623
 624   return LastVal;
 625 }
 626
 627 Value *FAddCombine::createFSub
 628   (Value *Opnd0, Value *Opnd1) {
 629   Value *V = Builder->CreateFSub(Opnd0, Opnd1);
 630   createInstPostProc(cast<Instruction>(V));
 631   return V;
 632 }
 633
 634 Value *FAddCombine::createFNeg(Value *V) {
 635   Value *Zero = cast<Value>(ConstantFP::get(V->getType(), 0.0));
 636   return createFSub(Zero, V);
 637 }
 638
 639 Value *FAddCombine::createFAdd
 640   (Value *Opnd0, Value *Opnd1) {
 641   Value *V = Builder->CreateFAdd(Opnd0, Opnd1);
 642   createInstPostProc(cast<Instruction>(V));
 643   return V;
 644 }
 645
 646 Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) {
 647   Value *V = Builder->CreateFMul(Opnd0, Opnd1);
 648   createInstPostProc(cast<Instruction>(V));
 649   return V;
 650 }
 651
 652 void FAddCombine::createInstPostProc(Instruction *NewInstr) {
 653   NewInstr->setDebugLoc(Instr->getDebugLoc());
 654
 655   // Keep track of the number of instruction created.
 656   incCreateInstNum();
 657
 658   // Propagate fast-math flags
 659   NewInstr->setFastMathFlags(Instr->getFastMathFlags());
 660 }
 661
 662 // Return the number of instruction needed to emit the N-ary addition.
 663 // NOTE: Keep this function in sync with createAddendVal().
 664 unsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) {
 665   unsigned OpndNum = Opnds.size();
 666   unsigned InstrNeeded = OpndNum - 1;
 667
 668   // The number of addends in the form of "(-1)*x".
 669   unsigned NegOpndNum = 0;
 670
 671   // Adjust the number of instructions needed to emit the N-ary add.
 672   for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end();
 673        I != E; I++) {
 674     const FAddend *Opnd = *I;
 675     if (Opnd->isConstant())
 676       continue;
 677
 678     const FAddendCoef &CE = Opnd->getCoef();
 679     if (CE.isMinusOne() || CE.isMinusTwo())
 680       NegOpndNum++;
 681
 682     // Let the addend be "c * x". If "c == +/-1", the value of the addend
 683     // is immediately available; otherwise, it needs exactly one instruction
 684     // to evaluate the value.
 685     if (!CE.isMinusOne() && !CE.isOne())
 686       InstrNeeded++;
 687   }
 688   if (NegOpndNum == OpndNum)
 689     InstrNeeded++;
 690   return InstrNeeded;
 691 }
 692
 693 // Input Addend        Value           NeedNeg(output)
 694 // ================================================================
 695 // Constant C          C               false
 696 // <+/-1, V>           V               coefficient is -1
 697 // <2/-2, V>          "fadd V, V"      coefficient is -2
 698 // <C, V>             "fmul V, C"      false
 699 //
 700 // NOTE: Keep this function in sync with FAddCombine::calcInstrNumber.
 701 Value *FAddCombine::createAddendVal
 702   (const FAddend &Opnd, bool &NeedNeg) {
 703   const FAddendCoef &Coeff = Opnd.getCoef();
 704
 705   if (Opnd.isConstant()) {
 706     NeedNeg = false;
 707     return Coeff.getValue(Instr->getType());
 708   }
 709
 710   Value *OpndVal = Opnd.getSymVal();
 711
 712   if (Coeff.isMinusOne() || Coeff.isOne()) {
 713     NeedNeg = Coeff.isMinusOne();
 714     return OpndVal;
 715   }
 716
 717   if (Coeff.isTwo() || Coeff.isMinusTwo()) {
 718     NeedNeg = Coeff.isMinusTwo();
 719     return createFAdd(OpndVal, OpndVal);
 720   }
 721
 722   NeedNeg = false;
 723   return createFMul(OpndVal, Coeff.getValue(Instr->getType()));
 724 }
 725
 726 /// AddOne - Add one to a ConstantInt.
 727 static Constant *AddOne(Constant *C) {
 728   return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
 729 }
 730
 731 /// SubOne - Subtract one from a ConstantInt.
 732 static Constant *SubOne(ConstantInt *C) {
 733   return ConstantInt::get(C->getContext(), C->getValue()-1);
 734 }
 735
 736
 737 // dyn_castFoldableMul - If this value is a multiply that can be folded into
 738 // other computations (because it has a constant operand), return the
 739 // non-constant operand of the multiply, and set CST to point to the multiplier.
 740 // Otherwise, return null.
 741 //
 742 static inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) {
 743   if (!V->hasOneUse() || !V->getType()->isIntegerTy())
 744     return 0;
 745
 746   Instruction *I = dyn_cast<Instruction>(V);
 747   if (I == 0) return 0;
 748
 749   if (I->getOpcode() == Instruction::Mul)
 750     if ((CST = dyn_cast<ConstantInt>(I->getOperand(1))))
 751       return I->getOperand(0);
 752   if (I->getOpcode() == Instruction::Shl)
 753     if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) {
 754       // The multiplier is really 1 << CST.
 755       uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
 756       uint32_t CSTVal = CST->getLimitedValue(BitWidth);
 757       CST = ConstantInt::get(V->getType()->getContext(),
 758                              APInt(BitWidth, 1).shl(CSTVal));
 759       return I->getOperand(0);
 760     }
 761   return 0;
 762 }
 763
 764
 765 /// WillNotOverflowSignedAdd - Return true if we can prove that:
 766 ///    (sext (add LHS, RHS))  === (add (sext LHS), (sext RHS))
 767 /// This basically requires proving that the add in the original type would not
 768 /// overflow to change the sign bit or have a carry out.
 769 bool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS) {
 770   // There are different heuristics we can use for this.  Here are some simple
 771   // ones.
 772
 773   // Add has the property that adding any two 2's complement numbers can only
 774   // have one carry bit which can change a sign.  As such, if LHS and RHS each
 775   // have at least two sign bits, we know that the addition of the two values
 776   // will sign extend fine.
 777   if (ComputeNumSignBits(LHS) > 1 && ComputeNumSignBits(RHS) > 1)
 778     return true;
 779
 780
 781   // If one of the operands only has one non-zero bit, and if the other operand
 782   // has a known-zero bit in a more significant place than it (not including the
 783   // sign bit) the ripple may go up to and fill the zero, but won't change the
 784   // sign.  For example, (X & ~4) + 1.
 785
 786   // TODO: Implement.
 787
 788   return false;
 789 }
 790
 791 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
 792   bool Changed = SimplifyAssociativeOrCommutative(I);
 793   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 794
 795   if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(),
 796                                  I.hasNoUnsignedWrap(), TD))
 797     return ReplaceInstUsesWith(I, V);
 798
 799   // (A*B)+(A*C) -> A*(B+C) etc
 800   if (Value *V = SimplifyUsingDistributiveLaws(I))
 801     return ReplaceInstUsesWith(I, V);
 802
 803   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
 804     // X + (signbit) --> X ^ signbit
 805     const APInt &Val = CI->getValue();
 806     if (Val.isSignBit())
 807       return BinaryOperator::CreateXor(LHS, RHS);
 808
 809     // See if SimplifyDemandedBits can simplify this.  This handles stuff like
 810     // (X & 254)+1 -> (X&254)|1
 811     if (SimplifyDemandedInstructionBits(I))
 812       return &I;
 813
 814     // zext(bool) + C -> bool ? C + 1 : C
 815     if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS))
 816       if (ZI->getSrcTy()->isIntegerTy(1))
 817         return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI);
 818
 819     Value *XorLHS = 0; ConstantInt *XorRHS = 0;
 820     if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) {
 821       uint32_t TySizeBits = I.getType()->getScalarSizeInBits();
 822       const APInt &RHSVal = CI->getValue();
 823       unsigned ExtendAmt = 0;
 824       // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext.
 825       // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext.
 826       if (XorRHS->getValue() == -RHSVal) {
 827         if (RHSVal.isPowerOf2())
 828           ExtendAmt = TySizeBits - RHSVal.logBase2() - 1;
 829         else if (XorRHS->getValue().isPowerOf2())
 830           ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1;
 831       }
 832
 833       if (ExtendAmt) {
 834         APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt);
 835         if (!MaskedValueIsZero(XorLHS, Mask))
 836           ExtendAmt = 0;
 837       }
 838
 839       if (ExtendAmt) {
 840         Constant *ShAmt = ConstantInt::get(I.getType(), ExtendAmt);
 841         Value *NewShl = Builder->CreateShl(XorLHS, ShAmt, "sext");
 842         return BinaryOperator::CreateAShr(NewShl, ShAmt);
 843       }
 844
 845       // If this is a xor that was canonicalized from a sub, turn it back into
 846       // a sub and fuse this add with it.
 847       if (LHS->hasOneUse() && (XorRHS->getValue()+1).isPowerOf2()) {
 848         IntegerType *IT = cast<IntegerType>(I.getType());
 849         APInt LHSKnownOne(IT->getBitWidth(), 0);
 850         APInt LHSKnownZero(IT->getBitWidth(), 0);
 851         ComputeMaskedBits(XorLHS, LHSKnownZero, LHSKnownOne);
 852         if ((XorRHS->getValue() | LHSKnownZero).isAllOnesValue())
 853           return BinaryOperator::CreateSub(ConstantExpr::getAdd(XorRHS, CI),
 854                                            XorLHS);
 855       }
 856     }
 857   }
 858
 859   if (isa<Constant>(RHS) && isa<PHINode>(LHS))
 860     if (Instruction *NV = FoldOpIntoPhi(I))
 861       return NV;
 862
 863   if (I.getType()->isIntegerTy(1))
 864     return BinaryOperator::CreateXor(LHS, RHS);
 865
 866   // X + X --> X << 1
 867   if (LHS == RHS) {
 868     BinaryOperator *New =
 869       BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1));
 870     New->setHasNoSignedWrap(I.hasNoSignedWrap());
 871     New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
 872     return New;
 873   }
 874
 875   // -A + B  -->  B - A
 876   // -A + -B  -->  -(A + B)
 877   if (Value *LHSV = dyn_castNegVal(LHS)) {
 878     if (!isa<Constant>(RHS))
 879       if (Value *RHSV = dyn_castNegVal(RHS)) {
 880         Value *NewAdd = Builder->CreateAdd(LHSV, RHSV, "sum");
 881         return BinaryOperator::CreateNeg(NewAdd);
 882       }
 883
 884     return BinaryOperator::CreateSub(RHS, LHSV);
 885   }
 886
 887   // A + -B  -->  A - B
 888   if (!isa<Constant>(RHS))
 889     if (Value *V = dyn_castNegVal(RHS))
 890       return BinaryOperator::CreateSub(LHS, V);
 891
 892
 893   ConstantInt *C2;
 894   if (Value *X = dyn_castFoldableMul(LHS, C2)) {
 895     if (X == RHS)   // X*C + X --> X * (C+1)
 896       return BinaryOperator::CreateMul(RHS, AddOne(C2));
 897
 898     // X*C1 + X*C2 --> X * (C1+C2)
 899     ConstantInt *C1;
 900     if (X == dyn_castFoldableMul(RHS, C1))
 901       return BinaryOperator::CreateMul(X, ConstantExpr::getAdd(C1, C2));
 902   }
 903
 904   // X + X*C --> X * (C+1)
 905   if (dyn_castFoldableMul(RHS, C2) == LHS)
 906     return BinaryOperator::CreateMul(LHS, AddOne(C2));
 907
 908   // A+B --> A|B iff A and B have no bits set in common.
 909   if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
 910     APInt LHSKnownOne(IT->getBitWidth(), 0);
 911     APInt LHSKnownZero(IT->getBitWidth(), 0);
 912     ComputeMaskedBits(LHS, LHSKnownZero, LHSKnownOne);
 913     if (LHSKnownZero != 0) {
 914       APInt RHSKnownOne(IT->getBitWidth(), 0);
 915       APInt RHSKnownZero(IT->getBitWidth(), 0);
 916       ComputeMaskedBits(RHS, RHSKnownZero, RHSKnownOne);
 917
 918       // No bits in common -> bitwise or.
 919       if ((LHSKnownZero|RHSKnownZero).isAllOnesValue())
 920         return BinaryOperator::CreateOr(LHS, RHS);
 921     }
 922   }
 923
 924   // W*X + Y*Z --> W * (X+Z)  iff W == Y
 925   {
 926     Value *W, *X, *Y, *Z;
 927     if (match(LHS, m_Mul(m_Value(W), m_Value(X))) &&
 928         match(RHS, m_Mul(m_Value(Y), m_Value(Z)))) {
 929       if (W != Y) {
 930         if (W == Z) {
 931           std::swap(Y, Z);
 932         } else if (Y == X) {
 933           std::swap(W, X);
 934         } else if (X == Z) {
 935           std::swap(Y, Z);
 936           std::swap(W, X);
 937         }
 938       }
 939
 940       if (W == Y) {
 941         Value *NewAdd = Builder->CreateAdd(X, Z, LHS->getName());
 942         return BinaryOperator::CreateMul(W, NewAdd);
 943       }
 944     }
 945   }
 946
 947   if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
 948     Value *X = 0;
 949     if (match(LHS, m_Not(m_Value(X))))    // ~X + C --> (C-1) - X
 950       return BinaryOperator::CreateSub(SubOne(CRHS), X);
 951
 952     // (X & FF00) + xx00  -> (X+xx00) & FF00
 953     if (LHS->hasOneUse() &&
 954         match(LHS, m_And(m_Value(X), m_ConstantInt(C2))) &&
 955         CRHS->getValue() == (CRHS->getValue() & C2->getValue())) {
 956       // See if all bits from the first bit set in the Add RHS up are included
 957       // in the mask.  First, get the rightmost bit.
 958       const APInt &AddRHSV = CRHS->getValue();
 959
 960       // Form a mask of all bits from the lowest bit added through the top.
 961       APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1));
 962
 963       // See if the and mask includes all of these bits.
 964       APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue());
 965
 966       if (AddRHSHighBits == AddRHSHighBitsAnd) {
 967         // Okay, the xform is safe.  Insert the new add pronto.
 968         Value *NewAdd = Builder->CreateAdd(X, CRHS, LHS->getName());
 969         return BinaryOperator::CreateAnd(NewAdd, C2);
 970       }
 971     }
 972
 973     // Try to fold constant add into select arguments.
 974     if (SelectInst *SI = dyn_cast<SelectInst>(LHS))
 975       if (Instruction *R = FoldOpIntoSelect(I, SI))
 976         return R;
 977   }
 978
 979   // add (select X 0 (sub n A)) A  -->  select X A n
 980   {
 981     SelectInst *SI = dyn_cast<SelectInst>(LHS);
 982     Value *A = RHS;
 983     if (!SI) {
 984       SI = dyn_cast<SelectInst>(RHS);
 985       A = LHS;
 986     }
 987     if (SI && SI->hasOneUse()) {
 988       Value *TV = SI->getTrueValue();
 989       Value *FV = SI->getFalseValue();
 990       Value *N;
 991
 992       // Can we fold the add into the argument of the select?
 993       // We check both true and false select arguments for a matching subtract.
 994       if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A))))
 995         // Fold the add into the true select value.
 996         return SelectInst::Create(SI->getCondition(), N, A);
 997
 998       if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A))))
 999         // Fold the add into the false select value.
1000         return SelectInst::Create(SI->getCondition(), A, N);
1001     }
1002   }
1003
1004   // Check for (add (sext x), y), see if we can merge this into an
1005   // integer add followed by a sext.
1006   if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) {
1007     // (add (sext x), cst) --> (sext (add x, cst'))
1008     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) {
1009       Constant *CI =
1010         ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType());
1011       if (LHSConv->hasOneUse() &&
1012           ConstantExpr::getSExt(CI, I.getType()) == RHSC &&
1013           WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) {
1014         // Insert the new, smaller add.
1015         Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
1016                                               CI, "addconv");
1017         return new SExtInst(NewAdd, I.getType());
1018       }
1019     }
1020
1021     // (add (sext x), (sext y)) --> (sext (add int x, y))
1022     if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) {
1023       // Only do this if x/y have the same type, if at last one of them has a
1024       // single use (so we don't increase the number of sexts), and if the
1025       // integer add will not overflow.
1026       if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&&
1027           (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
1028           WillNotOverflowSignedAdd(LHSConv->getOperand(0),
1029                                    RHSConv->getOperand(0))) {
1030         // Insert the new integer add.
1031         Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
1032                                              RHSConv->getOperand(0), "addconv");
1033         return new SExtInst(NewAdd, I.getType());
1034       }
1035     }
1036   }
1037
1038   // Check for (x & y) + (x ^ y)
1039   {
1040     Value *A = 0, *B = 0;
1041     if (match(RHS, m_Xor(m_Value(A), m_Value(B))) &&
1042         (match(LHS, m_And(m_Specific(A), m_Specific(B))) ||
1043          match(LHS, m_And(m_Specific(B), m_Specific(A)))))
1044       return BinaryOperator::CreateOr(A, B);
1045
1046     if (match(LHS, m_Xor(m_Value(A), m_Value(B))) &&
1047         (match(RHS, m_And(m_Specific(A), m_Specific(B))) ||
1048          match(RHS, m_And(m_Specific(B), m_Specific(A)))))
1049       return BinaryOperator::CreateOr(A, B);
1050   }
1051
1052   return Changed ? &I : 0;
1053 }
1054
1055 Instruction *InstCombiner::visitFAdd(BinaryOperator &I) {
1056   bool Changed = SimplifyAssociativeOrCommutative(I);
1057   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1058
1059   if (Value *V = SimplifyFAddInst(LHS, RHS, I.getFastMathFlags(), TD))
1060     return ReplaceInstUsesWith(I, V);
1061
1062   if (isa<Constant>(RHS) && isa<PHINode>(LHS))
1063     if (Instruction *NV = FoldOpIntoPhi(I))
1064       return NV;
1065
1066   // -A + B  -->  B - A
1067   // -A + -B  -->  -(A + B)
1068   if (Value *LHSV = dyn_castFNegVal(LHS))
1069     return BinaryOperator::CreateFSub(RHS, LHSV);
1070
1071   // A + -B  -->  A - B
1072   if (!isa<Constant>(RHS))
1073     if (Value *V = dyn_castFNegVal(RHS))
1074       return BinaryOperator::CreateFSub(LHS, V);
1075
1076   // Check for (fadd double (sitofp x), y), see if we can merge this into an
1077   // integer add followed by a promotion.
1078   if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) {
1079     // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst))
1080     // ... if the constant fits in the integer value.  This is useful for things
1081     // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer
1082     // requires a constant pool load, and generally allows the add to be better
1083     // instcombined.
1084     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) {
1085       Constant *CI =
1086       ConstantExpr::getFPToSI(CFP, LHSConv->getOperand(0)->getType());
1087       if (LHSConv->hasOneUse() &&
1088           ConstantExpr::getSIToFP(CI, I.getType()) == CFP &&
1089           WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) {
1090         // Insert the new integer add.
1091         Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
1092                                               CI, "addconv");
1093         return new SIToFPInst(NewAdd, I.getType());
1094       }
1095     }
1096
1097     // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y))
1098     if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) {
1099       // Only do this if x/y have the same type, if at last one of them has a
1100       // single use (so we don't increase the number of int->fp conversions),
1101       // and if the integer add will not overflow.
1102       if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&&
1103           (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
1104           WillNotOverflowSignedAdd(LHSConv->getOperand(0),
1105                                    RHSConv->getOperand(0))) {
1106         // Insert the new integer add.
1107         Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
1108                                               RHSConv->getOperand(0),"addconv");
1109         return new SIToFPInst(NewAdd, I.getType());
1110       }
1111     }
1112   }
1113
1114   if (I.hasUnsafeAlgebra()) {
1115     if (Value *V = FAddCombine(Builder).simplify(&I))
1116       return ReplaceInstUsesWith(I, V);
1117   }
1118
1119   return Changed ? &I : 0;
1120 }
1121
1122
1123 /// Optimize pointer differences into the same array into a size.  Consider:
1124 ///  &A[10] - &A[0]: we should compile this to "10".  LHS/RHS are the pointer
1125 /// operands to the ptrtoint instructions for the LHS/RHS of the subtract.
1126 ///
1127 Value *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS,
1128                                                Type *Ty) {
1129   assert(TD && "Must have target data info for this");
1130
1131   // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize
1132   // this.
1133   bool Swapped = false;
1134   GEPOperator *GEP1 = 0, *GEP2 = 0;
1135
1136   // For now we require one side to be the base pointer "A" or a constant
1137   // GEP derived from it.
1138   if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
1139     // (gep X, ...) - X
1140     if (LHSGEP->getOperand(0) == RHS) {
1141       GEP1 = LHSGEP;
1142       Swapped = false;
1143     } else if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
1144       // (gep X, ...) - (gep X, ...)
1145       if (LHSGEP->getOperand(0)->stripPointerCasts() ==
1146             RHSGEP->getOperand(0)->stripPointerCasts()) {
1147         GEP2 = RHSGEP;
1148         GEP1 = LHSGEP;
1149         Swapped = false;
1150       }
1151     }
1152   }
1153
1154   if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
1155     // X - (gep X, ...)
1156     if (RHSGEP->getOperand(0) == LHS) {
1157       GEP1 = RHSGEP;
1158       Swapped = true;
1159     } else if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
1160       // (gep X, ...) - (gep X, ...)
1161       if (RHSGEP->getOperand(0)->stripPointerCasts() ==
1162             LHSGEP->getOperand(0)->stripPointerCasts()) {
1163         GEP2 = LHSGEP;
1164         GEP1 = RHSGEP;
1165         Swapped = true;
1166       }
1167     }
1168   }
1169
1170   // Avoid duplicating the arithmetic if GEP2 has non-constant indices and
1171   // multiple users.
1172   if (GEP1 == 0 ||
1173       (GEP2 != 0 && !GEP2->hasAllConstantIndices() && !GEP2->hasOneUse()))
1174     return 0;
1175
1176   // Emit the offset of the GEP and an intptr_t.
1177   Value *Result = EmitGEPOffset(GEP1);
1178
1179   // If we had a constant expression GEP on the other side offsetting the
1180   // pointer, subtract it from the offset we have.
1181   if (GEP2) {
1182     Value *Offset = EmitGEPOffset(GEP2);
1183     Result = Builder->CreateSub(Result, Offset);
1184   }
1185
1186   // If we have p - gep(p, ...)  then we have to negate the result.
1187   if (Swapped)
1188     Result = Builder->CreateNeg(Result, "diff.neg");
1189
1190   return Builder->CreateIntCast(Result, Ty, true);
1191 }
1192
1193
1194 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
1195   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1196
1197   if (Value *V = SimplifySubInst(Op0, Op1, I.hasNoSignedWrap(),
1198                                  I.hasNoUnsignedWrap(), TD))
1199     return ReplaceInstUsesWith(I, V);
1200
1201   // (A*B)-(A*C) -> A*(B-C) etc
1202   if (Value *V = SimplifyUsingDistributiveLaws(I))
1203     return ReplaceInstUsesWith(I, V);
1204
1205   // If this is a 'B = x-(-A)', change to B = x+A.  This preserves NSW/NUW.
1206   if (Value *V = dyn_castNegVal(Op1)) {
1207     BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V);
1208     Res->setHasNoSignedWrap(I.hasNoSignedWrap());
1209     Res->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1210     return Res;
1211   }
1212
1213   if (I.getType()->isIntegerTy(1))
1214     return BinaryOperator::CreateXor(Op0, Op1);
1215
1216   // Replace (-1 - A) with (~A).
1217   if (match(Op0, m_AllOnes()))
1218     return BinaryOperator::CreateNot(Op1);
1219
1220   if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) {
1221     // C - ~X == X + (1+C)
1222     Value *X = 0;
1223     if (match(Op1, m_Not(m_Value(X))))
1224       return BinaryOperator::CreateAdd(X, AddOne(C));
1225
1226     // -(X >>u 31) -> (X >>s 31)
1227     // -(X >>s 31) -> (X >>u 31)
1228     if (C->isZero()) {
1229       Value *X; ConstantInt *CI;
1230       if (match(Op1, m_LShr(m_Value(X), m_ConstantInt(CI))) &&
1231           // Verify we are shifting out everything but the sign bit.
1232           CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1)
1233         return BinaryOperator::CreateAShr(X, CI);
1234
1235       if (match(Op1, m_AShr(m_Value(X), m_ConstantInt(CI))) &&
1236           // Verify we are shifting out everything but the sign bit.
1237           CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1)
1238         return BinaryOperator::CreateLShr(X, CI);
1239     }
1240
1241     // Try to fold constant sub into select arguments.
1242     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1243       if (Instruction *R = FoldOpIntoSelect(I, SI))
1244         return R;
1245
1246     // C-(X+C2) --> (C-C2)-X
1247     ConstantInt *C2;
1248     if (match(Op1, m_Add(m_Value(X), m_ConstantInt(C2))))
1249       return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
1250
1251     if (SimplifyDemandedInstructionBits(I))
1252       return &I;
1253   }
1254
1255
1256   { Value *Y;
1257     // X-(X+Y) == -Y    X-(Y+X) == -Y
1258     if (match(Op1, m_Add(m_Specific(Op0), m_Value(Y))) ||
1259         match(Op1, m_Add(m_Value(Y), m_Specific(Op0))))
1260       return BinaryOperator::CreateNeg(Y);
1261
1262     // (X-Y)-X == -Y
1263     if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))
1264       return BinaryOperator::CreateNeg(Y);
1265   }
1266
1267   if (Op1->hasOneUse()) {
1268     Value *X = 0, *Y = 0, *Z = 0;
1269     Constant *C = 0;
1270     ConstantInt *CI = 0;
1271
1272     // (X - (Y - Z))  -->  (X + (Z - Y)).
1273     if (match(Op1, m_Sub(m_Value(Y), m_Value(Z))))
1274       return BinaryOperator::CreateAdd(Op0,
1275                                       Builder->CreateSub(Z, Y, Op1->getName()));
1276
1277     // (X - (X & Y))   -->   (X & ~Y)
1278     //
1279     if (match(Op1, m_And(m_Value(Y), m_Specific(Op0))) ||
1280         match(Op1, m_And(m_Specific(Op0), m_Value(Y))))
1281       return BinaryOperator::CreateAnd(Op0,
1282                                   Builder->CreateNot(Y, Y->getName() + ".not"));
1283
1284     // 0 - (X sdiv C)  -> (X sdiv -C)
1285     if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) &&
1286         match(Op0, m_Zero()))
1287       return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C));
1288
1289     // 0 - (X << Y)  -> (-X << Y)   when X is freely negatable.
1290     if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero()))
1291       if (Value *XNeg = dyn_castNegVal(X))
1292         return BinaryOperator::CreateShl(XNeg, Y);
1293
1294     // X - X*C --> X * (1-C)
1295     if (match(Op1, m_Mul(m_Specific(Op0), m_ConstantInt(CI)))) {
1296       Constant *CP1 = ConstantExpr::getSub(ConstantInt::get(I.getType(),1), CI);
1297       return BinaryOperator::CreateMul(Op0, CP1);
1298     }
1299
1300     // X - X<<C --> X * (1-(1<<C))
1301     if (match(Op1, m_Shl(m_Specific(Op0), m_ConstantInt(CI)))) {
1302       Constant *One = ConstantInt::get(I.getType(), 1);
1303       C = ConstantExpr::getSub(One, ConstantExpr::getShl(One, CI));
1304       return BinaryOperator::CreateMul(Op0, C);
1305     }
1306
1307     // X - A*-B -> X + A*B
1308     // X - -A*B -> X + A*B
1309     Value *A, *B;
1310     if (match(Op1, m_Mul(m_Value(A), m_Neg(m_Value(B)))) ||
1311         match(Op1, m_Mul(m_Neg(m_Value(A)), m_Value(B))))
1312       return BinaryOperator::CreateAdd(Op0, Builder->CreateMul(A, B));
1313
1314     // X - A*CI -> X + A*-CI
1315     // X - CI*A -> X + A*-CI
1316     if (match(Op1, m_Mul(m_Value(A), m_ConstantInt(CI))) ||
1317         match(Op1, m_Mul(m_ConstantInt(CI), m_Value(A)))) {
1318       Value *NewMul = Builder->CreateMul(A, ConstantExpr::getNeg(CI));
1319       return BinaryOperator::CreateAdd(Op0, NewMul);
1320     }
1321   }
1322
1323   ConstantInt *C1;
1324   if (Value *X = dyn_castFoldableMul(Op0, C1)) {
1325     if (X == Op1)  // X*C - X --> X * (C-1)
1326       return BinaryOperator::CreateMul(Op1, SubOne(C1));
1327
1328     ConstantInt *C2;   // X*C1 - X*C2 -> X * (C1-C2)
1329     if (X == dyn_castFoldableMul(Op1, C2))
1330       return BinaryOperator::CreateMul(X, ConstantExpr::getSub(C1, C2));
1331   }
1332
1333   // Optimize pointer differences into the same array into a size.  Consider:
1334   //  &A[10] - &A[0]: we should compile this to "10".
1335   if (TD) {
1336     Value *LHSOp, *RHSOp;
1337     if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
1338         match(Op1, m_PtrToInt(m_Value(RHSOp))))
1339       if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
1340         return ReplaceInstUsesWith(I, Res);
1341
1342     // trunc(p)-trunc(q) -> trunc(p-q)
1343     if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) &&
1344         match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp)))))
1345       if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
1346         return ReplaceInstUsesWith(I, Res);
1347   }
1348
1349   return 0;
1350 }
1351
1352 Instruction *InstCombiner::visitFSub(BinaryOperator &I) {
1353   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1354
1355   if (Value *V = SimplifyFSubInst(Op0, Op1, I.getFastMathFlags(), TD))
1356     return ReplaceInstUsesWith(I, V);
1357
1358   // If this is a 'B = x-(-A)', change to B = x+A...
1359   if (Value *V = dyn_castFNegVal(Op1))
1360     return BinaryOperator::CreateFAdd(Op0, V);
1361
1362   if (I.hasUnsafeAlgebra()) {
1363     if (Value *V = FAddCombine(Builder).simplify(&I))
1364       return ReplaceInstUsesWith(I, V);
1365   }
1366
1367   return 0;
1368 }