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/Target/TargetData.h"
  17 #include "llvm/Support/GetElementPtrTypeIterator.h"
  18 #include "llvm/Support/PatternMatch.h"
  19 using namespace llvm;
  20 using namespace PatternMatch;
  21
  22 /// AddOne - Add one to a ConstantInt.
  23 static Constant *AddOne(Constant *C) {
  24   return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
  25 }
  26 /// SubOne - Subtract one from a ConstantInt.
  27 static Constant *SubOne(ConstantInt *C) {
  28   return ConstantInt::get(C->getContext(), C->getValue()-1);
  29 }
  30
  31
  32 // dyn_castFoldableMul - If this value is a multiply that can be folded into
  33 // other computations (because it has a constant operand), return the
  34 // non-constant operand of the multiply, and set CST to point to the multiplier.
  35 // Otherwise, return null.
  36 //
  37 static inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) {
  38   if (!V->hasOneUse() || !V->getType()->isIntegerTy())
  39     return 0;
  40
  41   Instruction *I = dyn_cast<Instruction>(V);
  42   if (I == 0) return 0;
  43
  44   if (I->getOpcode() == Instruction::Mul)
  45     if ((CST = dyn_cast<ConstantInt>(I->getOperand(1))))
  46       return I->getOperand(0);
  47   if (I->getOpcode() == Instruction::Shl)
  48     if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) {
  49       // The multiplier is really 1 << CST.
  50       uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
  51       uint32_t CSTVal = CST->getLimitedValue(BitWidth);
  52       CST = ConstantInt::get(V->getType()->getContext(),
  53                              APInt(BitWidth, 1).shl(CSTVal));
  54       return I->getOperand(0);
  55     }
  56   return 0;
  57 }
  58
  59
  60 /// WillNotOverflowSignedAdd - Return true if we can prove that:
  61 ///    (sext (add LHS, RHS))  === (add (sext LHS), (sext RHS))
  62 /// This basically requires proving that the add in the original type would not
  63 /// overflow to change the sign bit or have a carry out.
  64 bool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS) {
  65   // There are different heuristics we can use for this.  Here are some simple
  66   // ones.
  67
  68   // Add has the property that adding any two 2's complement numbers can only
  69   // have one carry bit which can change a sign.  As such, if LHS and RHS each
  70   // have at least two sign bits, we know that the addition of the two values
  71   // will sign extend fine.
  72   if (ComputeNumSignBits(LHS) > 1 && ComputeNumSignBits(RHS) > 1)
  73     return true;
  74
  75
  76   // If one of the operands only has one non-zero bit, and if the other operand
  77   // has a known-zero bit in a more significant place than it (not including the
  78   // sign bit) the ripple may go up to and fill the zero, but won't change the
  79   // sign.  For example, (X & ~4) + 1.
  80
  81   // TODO: Implement.
  82
  83   return false;
  84 }
  85
  86 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
  87   bool Changed = SimplifyAssociativeOrCommutative(I);
  88   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
  89
  90   if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(),
  91                                  I.hasNoUnsignedWrap(), TD))
  92     return ReplaceInstUsesWith(I, V);
  93
  94   // (A*B)+(A*C) -> A*(B+C) etc
  95   if (Value *V = SimplifyUsingDistributiveLaws(I))
  96     return ReplaceInstUsesWith(I, V);
  97
  98   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
  99     // X + (signbit) --> X ^ signbit
 100     const APInt &Val = CI->getValue();
 101     if (Val.isSignBit())
 102       return BinaryOperator::CreateXor(LHS, RHS);
 103
 104     // See if SimplifyDemandedBits can simplify this.  This handles stuff like
 105     // (X & 254)+1 -> (X&254)|1
 106     if (SimplifyDemandedInstructionBits(I))
 107       return &I;
 108
 109     // zext(bool) + C -> bool ? C + 1 : C
 110     if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS))
 111       if (ZI->getSrcTy()->isIntegerTy(1))
 112         return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI);
 113
 114     Value *XorLHS = 0; ConstantInt *XorRHS = 0;
 115     if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) {
 116       uint32_t TySizeBits = I.getType()->getScalarSizeInBits();
 117       const APInt &RHSVal = CI->getValue();
 118       unsigned ExtendAmt = 0;
 119       // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext.
 120       // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext.
 121       if (XorRHS->getValue() == -RHSVal) {
 122         if (RHSVal.isPowerOf2())
 123           ExtendAmt = TySizeBits - RHSVal.logBase2() - 1;
 124         else if (XorRHS->getValue().isPowerOf2())
 125           ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1;
 126       }
 127
 128       if (ExtendAmt) {
 129         APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt);
 130         if (!MaskedValueIsZero(XorLHS, Mask))
 131           ExtendAmt = 0;
 132       }
 133
 134       if (ExtendAmt) {
 135         Constant *ShAmt = ConstantInt::get(I.getType(), ExtendAmt);
 136         Value *NewShl = Builder->CreateShl(XorLHS, ShAmt, "sext");
 137         return BinaryOperator::CreateAShr(NewShl, ShAmt);
 138       }
 139
 140       // If this is a xor that was canonicalized from a sub, turn it back into
 141       // a sub and fuse this add with it.
 142       if (LHS->hasOneUse() && (XorRHS->getValue()+1).isPowerOf2()) {
 143         IntegerType *IT = cast<IntegerType>(I.getType());
 144         APInt Mask = APInt::getAllOnesValue(IT->getBitWidth());
 145         APInt LHSKnownOne(IT->getBitWidth(), 0);
 146         APInt LHSKnownZero(IT->getBitWidth(), 0);
 147         ComputeMaskedBits(XorLHS, Mask, LHSKnownZero, LHSKnownOne);
 148         if ((XorRHS->getValue() | LHSKnownZero).isAllOnesValue())
 149           return BinaryOperator::CreateSub(ConstantExpr::getAdd(XorRHS, CI),
 150                                            XorLHS);
 151       }
 152     }
 153   }
 154
 155   if (isa<Constant>(RHS) && isa<PHINode>(LHS))
 156     if (Instruction *NV = FoldOpIntoPhi(I))
 157       return NV;
 158
 159   if (I.getType()->isIntegerTy(1))
 160     return BinaryOperator::CreateXor(LHS, RHS);
 161
 162   // X + X --> X << 1
 163   if (LHS == RHS) {
 164     BinaryOperator *New =
 165       BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1));
 166     New->setHasNoSignedWrap(I.hasNoSignedWrap());
 167     New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
 168     return New;
 169   }
 170
 171   // -A + B  -->  B - A
 172   // -A + -B  -->  -(A + B)
 173   if (Value *LHSV = dyn_castNegVal(LHS)) {
 174     if (Value *RHSV = dyn_castNegVal(RHS)) {
 175       Value *NewAdd = Builder->CreateAdd(LHSV, RHSV, "sum");
 176       return BinaryOperator::CreateNeg(NewAdd);
 177     }
 178
 179     return BinaryOperator::CreateSub(RHS, LHSV);
 180   }
 181
 182   // A + -B  -->  A - B
 183   if (!isa<Constant>(RHS))
 184     if (Value *V = dyn_castNegVal(RHS))
 185       return BinaryOperator::CreateSub(LHS, V);
 186
 187
 188   ConstantInt *C2;
 189   if (Value *X = dyn_castFoldableMul(LHS, C2)) {
 190     if (X == RHS)   // X*C + X --> X * (C+1)
 191       return BinaryOperator::CreateMul(RHS, AddOne(C2));
 192
 193     // X*C1 + X*C2 --> X * (C1+C2)
 194     ConstantInt *C1;
 195     if (X == dyn_castFoldableMul(RHS, C1))
 196       return BinaryOperator::CreateMul(X, ConstantExpr::getAdd(C1, C2));
 197   }
 198
 199   // X + X*C --> X * (C+1)
 200   if (dyn_castFoldableMul(RHS, C2) == LHS)
 201     return BinaryOperator::CreateMul(LHS, AddOne(C2));
 202
 203   // A+B --> A|B iff A and B have no bits set in common.
 204   if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
 205     APInt Mask = APInt::getAllOnesValue(IT->getBitWidth());
 206     APInt LHSKnownOne(IT->getBitWidth(), 0);
 207     APInt LHSKnownZero(IT->getBitWidth(), 0);
 208     ComputeMaskedBits(LHS, Mask, LHSKnownZero, LHSKnownOne);
 209     if (LHSKnownZero != 0) {
 210       APInt RHSKnownOne(IT->getBitWidth(), 0);
 211       APInt RHSKnownZero(IT->getBitWidth(), 0);
 212       ComputeMaskedBits(RHS, Mask, RHSKnownZero, RHSKnownOne);
 213
 214       // No bits in common -> bitwise or.
 215       if ((LHSKnownZero|RHSKnownZero).isAllOnesValue())
 216         return BinaryOperator::CreateOr(LHS, RHS);
 217     }
 218   }
 219
 220   // W*X + Y*Z --> W * (X+Z)  iff W == Y
 221   {
 222     Value *W, *X, *Y, *Z;
 223     if (match(LHS, m_Mul(m_Value(W), m_Value(X))) &&
 224         match(RHS, m_Mul(m_Value(Y), m_Value(Z)))) {
 225       if (W != Y) {
 226         if (W == Z) {
 227           std::swap(Y, Z);
 228         } else if (Y == X) {
 229           std::swap(W, X);
 230         } else if (X == Z) {
 231           std::swap(Y, Z);
 232           std::swap(W, X);
 233         }
 234       }
 235
 236       if (W == Y) {
 237         Value *NewAdd = Builder->CreateAdd(X, Z, LHS->getName());
 238         return BinaryOperator::CreateMul(W, NewAdd);
 239       }
 240     }
 241   }
 242
 243   if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
 244     Value *X = 0;
 245     if (match(LHS, m_Not(m_Value(X))))    // ~X + C --> (C-1) - X
 246       return BinaryOperator::CreateSub(SubOne(CRHS), X);
 247
 248     // (X & FF00) + xx00  -> (X+xx00) & FF00
 249     if (LHS->hasOneUse() &&
 250         match(LHS, m_And(m_Value(X), m_ConstantInt(C2))) &&
 251         CRHS->getValue() == (CRHS->getValue() & C2->getValue())) {
 252       // See if all bits from the first bit set in the Add RHS up are included
 253       // in the mask.  First, get the rightmost bit.
 254       const APInt &AddRHSV = CRHS->getValue();
 255
 256       // Form a mask of all bits from the lowest bit added through the top.
 257       APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1));
 258
 259       // See if the and mask includes all of these bits.
 260       APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue());
 261
 262       if (AddRHSHighBits == AddRHSHighBitsAnd) {
 263         // Okay, the xform is safe.  Insert the new add pronto.
 264         Value *NewAdd = Builder->CreateAdd(X, CRHS, LHS->getName());
 265         return BinaryOperator::CreateAnd(NewAdd, C2);
 266       }
 267     }
 268
 269     // Try to fold constant add into select arguments.
 270     if (SelectInst *SI = dyn_cast<SelectInst>(LHS))
 271       if (Instruction *R = FoldOpIntoSelect(I, SI))
 272         return R;
 273   }
 274
 275   // add (select X 0 (sub n A)) A  -->  select X A n
 276   {
 277     SelectInst *SI = dyn_cast<SelectInst>(LHS);
 278     Value *A = RHS;
 279     if (!SI) {
 280       SI = dyn_cast<SelectInst>(RHS);
 281       A = LHS;
 282     }
 283     if (SI && SI->hasOneUse()) {
 284       Value *TV = SI->getTrueValue();
 285       Value *FV = SI->getFalseValue();
 286       Value *N;
 287
 288       // Can we fold the add into the argument of the select?
 289       // We check both true and false select arguments for a matching subtract.
 290       if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A))))
 291         // Fold the add into the true select value.
 292         return SelectInst::Create(SI->getCondition(), N, A);
 293
 294       if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A))))
 295         // Fold the add into the false select value.
 296         return SelectInst::Create(SI->getCondition(), A, N);
 297     }
 298   }
 299
 300   // Check for (add (sext x), y), see if we can merge this into an
 301   // integer add followed by a sext.
 302   if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) {
 303     // (add (sext x), cst) --> (sext (add x, cst'))
 304     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) {
 305       Constant *CI =
 306         ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType());
 307       if (LHSConv->hasOneUse() &&
 308           ConstantExpr::getSExt(CI, I.getType()) == RHSC &&
 309           WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) {
 310         // Insert the new, smaller add.
 311         Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
 312                                               CI, "addconv");
 313         return new SExtInst(NewAdd, I.getType());
 314       }
 315     }
 316
 317     // (add (sext x), (sext y)) --> (sext (add int x, y))
 318     if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) {
 319       // Only do this if x/y have the same type, if at last one of them has a
 320       // single use (so we don't increase the number of sexts), and if the
 321       // integer add will not overflow.
 322       if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&&
 323           (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
 324           WillNotOverflowSignedAdd(LHSConv->getOperand(0),
 325                                    RHSConv->getOperand(0))) {
 326         // Insert the new integer add.
 327         Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
 328                                              RHSConv->getOperand(0), "addconv");
 329         return new SExtInst(NewAdd, I.getType());
 330       }
 331     }
 332   }
 333
 334   return Changed ? &I : 0;
 335 }
 336
 337 Instruction *InstCombiner::visitFAdd(BinaryOperator &I) {
 338   bool Changed = SimplifyAssociativeOrCommutative(I);
 339   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 340
 341   if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
 342     // X + 0 --> X
 343     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
 344       if (CFP->isExactlyValue(ConstantFP::getNegativeZero
 345                               (I.getType())->getValueAPF()))
 346         return ReplaceInstUsesWith(I, LHS);
 347     }
 348
 349     if (isa<PHINode>(LHS))
 350       if (Instruction *NV = FoldOpIntoPhi(I))
 351         return NV;
 352   }
 353
 354   // -A + B  -->  B - A
 355   // -A + -B  -->  -(A + B)
 356   if (Value *LHSV = dyn_castFNegVal(LHS))
 357     return BinaryOperator::CreateFSub(RHS, LHSV);
 358
 359   // A + -B  -->  A - B
 360   if (!isa<Constant>(RHS))
 361     if (Value *V = dyn_castFNegVal(RHS))
 362       return BinaryOperator::CreateFSub(LHS, V);
 363
 364   // Check for X+0.0.  Simplify it to X if we know X is not -0.0.
 365   if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS))
 366     if (CFP->getValueAPF().isPosZero() && CannotBeNegativeZero(LHS))
 367       return ReplaceInstUsesWith(I, LHS);
 368
 369   // Check for (fadd double (sitofp x), y), see if we can merge this into an
 370   // integer add followed by a promotion.
 371   if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) {
 372     // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst))
 373     // ... if the constant fits in the integer value.  This is useful for things
 374     // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer
 375     // requires a constant pool load, and generally allows the add to be better
 376     // instcombined.
 377     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) {
 378       Constant *CI =
 379       ConstantExpr::getFPToSI(CFP, LHSConv->getOperand(0)->getType());
 380       if (LHSConv->hasOneUse() &&
 381           ConstantExpr::getSIToFP(CI, I.getType()) == CFP &&
 382           WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) {
 383         // Insert the new integer add.
 384         Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
 385                                               CI, "addconv");
 386         return new SIToFPInst(NewAdd, I.getType());
 387       }
 388     }
 389
 390     // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y))
 391     if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) {
 392       // Only do this if x/y have the same type, if at last one of them has a
 393       // single use (so we don't increase the number of int->fp conversions),
 394       // and if the integer add will not overflow.
 395       if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&&
 396           (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
 397           WillNotOverflowSignedAdd(LHSConv->getOperand(0),
 398                                    RHSConv->getOperand(0))) {
 399         // Insert the new integer add.
 400         Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
 401                                               RHSConv->getOperand(0),"addconv");
 402         return new SIToFPInst(NewAdd, I.getType());
 403       }
 404     }
 405   }
 406
 407   return Changed ? &I : 0;
 408 }
 409
 410
 411 /// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the
 412 /// code necessary to compute the offset from the base pointer (without adding
 413 /// in the base pointer).  Return the result as a signed integer of intptr size.
 414 Value *InstCombiner::EmitGEPOffset(User *GEP) {
 415   TargetData &TD = *getTargetData();
 416   gep_type_iterator GTI = gep_type_begin(GEP);
 417   Type *IntPtrTy = TD.getIntPtrType(GEP->getContext());
 418   Value *Result = Constant::getNullValue(IntPtrTy);
 419
 420   // If the GEP is inbounds, we know that none of the addressing operations will
 421   // overflow in an unsigned sense.
 422   bool isInBounds = cast<GEPOperator>(GEP)->isInBounds();
 423
 424   // Build a mask for high order bits.
 425   unsigned IntPtrWidth = TD.getPointerSizeInBits();
 426   uint64_t PtrSizeMask = ~0ULL >> (64-IntPtrWidth);
 427
 428   for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e;
 429        ++i, ++GTI) {
 430     Value *Op = *i;
 431     uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask;
 432     if (ConstantInt *OpC = dyn_cast<ConstantInt>(Op)) {
 433       if (OpC->isZero()) continue;
 434
 435       // Handle a struct index, which adds its field offset to the pointer.
 436       if (StructType *STy = dyn_cast<StructType>(*GTI)) {
 437         Size = TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue());
 438
 439         if (Size)
 440           Result = Builder->CreateAdd(Result, ConstantInt::get(IntPtrTy, Size),
 441                                       GEP->getName()+".offs");
 442         continue;
 443       }
 444
 445       Constant *Scale = ConstantInt::get(IntPtrTy, Size);
 446       Constant *OC =
 447               ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/);
 448       Scale = ConstantExpr::getMul(OC, Scale, isInBounds/*NUW*/);
 449       // Emit an add instruction.
 450       Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs");
 451       continue;
 452     }
 453     // Convert to correct type.
 454     if (Op->getType() != IntPtrTy)
 455       Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c");
 456     if (Size != 1) {
 457       // We'll let instcombine(mul) convert this to a shl if possible.
 458       Op = Builder->CreateMul(Op, ConstantInt::get(IntPtrTy, Size),
 459                               GEP->getName()+".idx", isInBounds /*NUW*/);
 460     }
 461
 462     // Emit an add instruction.
 463     Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs");
 464   }
 465   return Result;
 466 }
 467
 468
 469
 470
 471 /// Optimize pointer differences into the same array into a size.  Consider:
 472 ///  &A[10] - &A[0]: we should compile this to "10".  LHS/RHS are the pointer
 473 /// operands to the ptrtoint instructions for the LHS/RHS of the subtract.
 474 ///
 475 Value *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS,
 476                                                Type *Ty) {
 477   assert(TD && "Must have target data info for this");
 478
 479   // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize
 480   // this.
 481   bool Swapped = false;
 482   GetElementPtrInst *GEP = 0;
 483   ConstantExpr *CstGEP = 0;
 484
 485   // TODO: Could also optimize &A[i] - &A[j] -> "i-j", and "&A.foo[i] - &A.foo".
 486   // For now we require one side to be the base pointer "A" or a constant
 487   // expression derived from it.
 488   if (GetElementPtrInst *LHSGEP = dyn_cast<GetElementPtrInst>(LHS)) {
 489     // (gep X, ...) - X
 490     if (LHSGEP->getOperand(0) == RHS) {
 491       GEP = LHSGEP;
 492       Swapped = false;
 493     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(RHS)) {
 494       // (gep X, ...) - (ce_gep X, ...)
 495       if (CE->getOpcode() == Instruction::GetElementPtr &&
 496           LHSGEP->getOperand(0) == CE->getOperand(0)) {
 497         CstGEP = CE;
 498         GEP = LHSGEP;
 499         Swapped = false;
 500       }
 501     }
 502   }
 503
 504   if (GetElementPtrInst *RHSGEP = dyn_cast<GetElementPtrInst>(RHS)) {
 505     // X - (gep X, ...)
 506     if (RHSGEP->getOperand(0) == LHS) {
 507       GEP = RHSGEP;
 508       Swapped = true;
 509     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(LHS)) {
 510       // (ce_gep X, ...) - (gep X, ...)
 511       if (CE->getOpcode() == Instruction::GetElementPtr &&
 512           RHSGEP->getOperand(0) == CE->getOperand(0)) {
 513         CstGEP = CE;
 514         GEP = RHSGEP;
 515         Swapped = true;
 516       }
 517     }
 518   }
 519
 520   if (GEP == 0)
 521     return 0;
 522
 523   // Emit the offset of the GEP and an intptr_t.
 524   Value *Result = EmitGEPOffset(GEP);
 525
 526   // If we had a constant expression GEP on the other side offsetting the
 527   // pointer, subtract it from the offset we have.
 528   if (CstGEP) {
 529     Value *CstOffset = EmitGEPOffset(CstGEP);
 530     Result = Builder->CreateSub(Result, CstOffset);
 531   }
 532
 533
 534   // If we have p - gep(p, ...)  then we have to negate the result.
 535   if (Swapped)
 536     Result = Builder->CreateNeg(Result, "diff.neg");
 537
 538   return Builder->CreateIntCast(Result, Ty, true);
 539 }
 540
 541
 542 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
 543   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 544
 545   if (Value *V = SimplifySubInst(Op0, Op1, I.hasNoSignedWrap(),
 546                                  I.hasNoUnsignedWrap(), TD))
 547     return ReplaceInstUsesWith(I, V);
 548
 549   // (A*B)-(A*C) -> A*(B-C) etc
 550   if (Value *V = SimplifyUsingDistributiveLaws(I))
 551     return ReplaceInstUsesWith(I, V);
 552
 553   // If this is a 'B = x-(-A)', change to B = x+A.  This preserves NSW/NUW.
 554   if (Value *V = dyn_castNegVal(Op1)) {
 555     BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V);
 556     Res->setHasNoSignedWrap(I.hasNoSignedWrap());
 557     Res->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
 558     return Res;
 559   }
 560
 561   if (I.getType()->isIntegerTy(1))
 562     return BinaryOperator::CreateXor(Op0, Op1);
 563
 564   // Replace (-1 - A) with (~A).
 565   if (match(Op0, m_AllOnes()))
 566     return BinaryOperator::CreateNot(Op1);
 567
 568   if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) {
 569     // C - ~X == X + (1+C)
 570     Value *X = 0;
 571     if (match(Op1, m_Not(m_Value(X))))
 572       return BinaryOperator::CreateAdd(X, AddOne(C));
 573
 574     // -(X >>u 31) -> (X >>s 31)
 575     // -(X >>s 31) -> (X >>u 31)
 576     if (C->isZero()) {
 577       Value *X; ConstantInt *CI;
 578       if (match(Op1, m_LShr(m_Value(X), m_ConstantInt(CI))) &&
 579           // Verify we are shifting out everything but the sign bit.
 580           CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1)
 581         return BinaryOperator::CreateAShr(X, CI);
 582
 583       if (match(Op1, m_AShr(m_Value(X), m_ConstantInt(CI))) &&
 584           // Verify we are shifting out everything but the sign bit.
 585           CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1)
 586         return BinaryOperator::CreateLShr(X, CI);
 587     }
 588
 589     // Try to fold constant sub into select arguments.
 590     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
 591       if (Instruction *R = FoldOpIntoSelect(I, SI))
 592         return R;
 593
 594     // C - zext(bool) -> bool ? C - 1 : C
 595     if (ZExtInst *ZI = dyn_cast<ZExtInst>(Op1))
 596       if (ZI->getSrcTy()->isIntegerTy(1))
 597         return SelectInst::Create(ZI->getOperand(0), SubOne(C), C);
 598
 599     // C-(X+C2) --> (C-C2)-X
 600     ConstantInt *C2;
 601     if (match(Op1, m_Add(m_Value(X), m_ConstantInt(C2))))
 602       return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
 603
 604     if (SimplifyDemandedInstructionBits(I))
 605       return &I;
 606   }
 607
 608
 609   { Value *Y;
 610     // X-(X+Y) == -Y    X-(Y+X) == -Y
 611     if (match(Op1, m_Add(m_Specific(Op0), m_Value(Y))) ||
 612         match(Op1, m_Add(m_Value(Y), m_Specific(Op0))))
 613       return BinaryOperator::CreateNeg(Y);
 614
 615     // (X-Y)-X == -Y
 616     if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))
 617       return BinaryOperator::CreateNeg(Y);
 618   }
 619
 620   if (Op1->hasOneUse()) {
 621     Value *X = 0, *Y = 0, *Z = 0;
 622     Constant *C = 0;
 623     ConstantInt *CI = 0;
 624
 625     // (X - (Y - Z))  -->  (X + (Z - Y)).
 626     if (match(Op1, m_Sub(m_Value(Y), m_Value(Z))))
 627       return BinaryOperator::CreateAdd(Op0,
 628                                       Builder->CreateSub(Z, Y, Op1->getName()));
 629
 630     // (X - (X & Y))   -->   (X & ~Y)
 631     //
 632     if (match(Op1, m_And(m_Value(Y), m_Specific(Op0))) ||
 633         match(Op1, m_And(m_Specific(Op0), m_Value(Y))))
 634       return BinaryOperator::CreateAnd(Op0,
 635                                   Builder->CreateNot(Y, Y->getName() + ".not"));
 636
 637     // 0 - (X sdiv C)  -> (X sdiv -C)
 638     if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) &&
 639         match(Op0, m_Zero()))
 640       return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C));
 641
 642     // 0 - (X << Y)  -> (-X << Y)   when X is freely negatable.
 643     if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero()))
 644       if (Value *XNeg = dyn_castNegVal(X))
 645         return BinaryOperator::CreateShl(XNeg, Y);
 646
 647     // X - X*C --> X * (1-C)
 648     if (match(Op1, m_Mul(m_Specific(Op0), m_ConstantInt(CI)))) {
 649       Constant *CP1 = ConstantExpr::getSub(ConstantInt::get(I.getType(),1), CI);
 650       return BinaryOperator::CreateMul(Op0, CP1);
 651     }
 652
 653     // X - X<<C --> X * (1-(1<<C))
 654     if (match(Op1, m_Shl(m_Specific(Op0), m_ConstantInt(CI)))) {
 655       Constant *One = ConstantInt::get(I.getType(), 1);
 656       C = ConstantExpr::getSub(One, ConstantExpr::getShl(One, CI));
 657       return BinaryOperator::CreateMul(Op0, C);
 658     }
 659
 660     // X - A*-B -> X + A*B
 661     // X - -A*B -> X + A*B
 662     Value *A, *B;
 663     if (match(Op1, m_Mul(m_Value(A), m_Neg(m_Value(B)))) ||
 664         match(Op1, m_Mul(m_Neg(m_Value(A)), m_Value(B))))
 665       return BinaryOperator::CreateAdd(Op0, Builder->CreateMul(A, B));
 666
 667     // X - A*CI -> X + A*-CI
 668     // X - CI*A -> X + A*-CI
 669     if (match(Op1, m_Mul(m_Value(A), m_ConstantInt(CI))) ||
 670         match(Op1, m_Mul(m_ConstantInt(CI), m_Value(A)))) {
 671       Value *NewMul = Builder->CreateMul(A, ConstantExpr::getNeg(CI));
 672       return BinaryOperator::CreateAdd(Op0, NewMul);
 673     }
 674   }
 675
 676   ConstantInt *C1;
 677   if (Value *X = dyn_castFoldableMul(Op0, C1)) {
 678     if (X == Op1)  // X*C - X --> X * (C-1)
 679       return BinaryOperator::CreateMul(Op1, SubOne(C1));
 680
 681     ConstantInt *C2;   // X*C1 - X*C2 -> X * (C1-C2)
 682     if (X == dyn_castFoldableMul(Op1, C2))
 683       return BinaryOperator::CreateMul(X, ConstantExpr::getSub(C1, C2));
 684   }
 685
 686   // Optimize pointer differences into the same array into a size.  Consider:
 687   //  &A[10] - &A[0]: we should compile this to "10".
 688   if (TD) {
 689     Value *LHSOp, *RHSOp;
 690     if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
 691         match(Op1, m_PtrToInt(m_Value(RHSOp))))
 692       if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
 693         return ReplaceInstUsesWith(I, Res);
 694
 695     // trunc(p)-trunc(q) -> trunc(p-q)
 696     if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) &&
 697         match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp)))))
 698       if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
 699         return ReplaceInstUsesWith(I, Res);
 700   }
 701
 702   return 0;
 703 }
 704
 705 Instruction *InstCombiner::visitFSub(BinaryOperator &I) {
 706   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 707
 708   // If this is a 'B = x-(-A)', change to B = x+A...
 709   if (Value *V = dyn_castFNegVal(Op1))
 710     return BinaryOperator::CreateFAdd(Op0, V);
 711
 712   return 0;
 713 }