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()->isInteger())
  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 = SimplifyCommutative(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
  95   if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
  96     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHSC)) {
  97       // X + (signbit) --> X ^ signbit
  98       const APInt& Val = CI->getValue();
  99       uint32_t BitWidth = Val.getBitWidth();
 100       if (Val == APInt::getSignBit(BitWidth))
 101         return BinaryOperator::CreateXor(LHS, RHS);
 102
 103       // See if SimplifyDemandedBits can simplify this.  This handles stuff like
 104       // (X & 254)+1 -> (X&254)|1
 105       if (SimplifyDemandedInstructionBits(I))
 106         return &I;
 107
 108       // zext(bool) + C -> bool ? C + 1 : C
 109       if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS))
 110         if (ZI->getSrcTy() == Type::getInt1Ty(I.getContext()))
 111           return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI);
 112     }
 113
 114     if (isa<PHINode>(LHS))
 115       if (Instruction *NV = FoldOpIntoPhi(I))
 116         return NV;
 117
 118     ConstantInt *XorRHS = 0;
 119     Value *XorLHS = 0;
 120     if (isa<ConstantInt>(RHSC) &&
 121         match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) {
 122       uint32_t TySizeBits = I.getType()->getScalarSizeInBits();
 123       const APInt& RHSVal = cast<ConstantInt>(RHSC)->getValue();
 124
 125       uint32_t Size = TySizeBits / 2;
 126       APInt C0080Val(APInt(TySizeBits, 1ULL).shl(Size - 1));
 127       APInt CFF80Val(-C0080Val);
 128       do {
 129         if (TySizeBits > Size) {
 130           // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext.
 131           // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext.
 132           if ((RHSVal == CFF80Val && XorRHS->getValue() == C0080Val) ||
 133               (RHSVal == C0080Val && XorRHS->getValue() == CFF80Val)) {
 134             // This is a sign extend if the top bits are known zero.
 135             if (!MaskedValueIsZero(XorLHS,
 136                    APInt::getHighBitsSet(TySizeBits, TySizeBits - Size)))
 137               Size = 0;  // Not a sign ext, but can't be any others either.
 138             break;
 139           }
 140         }
 141         Size >>= 1;
 142         C0080Val = APIntOps::lshr(C0080Val, Size);
 143         CFF80Val = APIntOps::ashr(CFF80Val, Size);
 144       } while (Size >= 1);
 145
 146       // FIXME: This shouldn't be necessary. When the backends can handle types
 147       // with funny bit widths then this switch statement should be removed. It
 148       // is just here to get the size of the "middle" type back up to something
 149       // that the back ends can handle.
 150       const Type *MiddleType = 0;
 151       switch (Size) {
 152         default: break;
 153         case 32:
 154         case 16:
 155         case  8: MiddleType = IntegerType::get(I.getContext(), Size); break;
 156       }
 157       if (MiddleType) {
 158         Value *NewTrunc = Builder->CreateTrunc(XorLHS, MiddleType, "sext");
 159         return new SExtInst(NewTrunc, I.getType(), I.getName());
 160       }
 161     }
 162   }
 163
 164   if (I.getType()->isInteger(1))
 165     return BinaryOperator::CreateXor(LHS, RHS);
 166
 167   if (I.getType()->isInteger()) {
 168     // X + X --> X << 1
 169     if (LHS == RHS)
 170       return BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1));
 171
 172     if (Instruction *RHSI = dyn_cast<Instruction>(RHS)) {
 173       if (RHSI->getOpcode() == Instruction::Sub)
 174         if (LHS == RHSI->getOperand(1))                   // A + (B - A) --> B
 175           return ReplaceInstUsesWith(I, RHSI->getOperand(0));
 176     }
 177     if (Instruction *LHSI = dyn_cast<Instruction>(LHS)) {
 178       if (LHSI->getOpcode() == Instruction::Sub)
 179         if (RHS == LHSI->getOperand(1))                   // (B - A) + A --> B
 180           return ReplaceInstUsesWith(I, LHSI->getOperand(0));
 181     }
 182   }
 183
 184   // -A + B  -->  B - A
 185   // -A + -B  -->  -(A + B)
 186   if (Value *LHSV = dyn_castNegVal(LHS)) {
 187     if (LHS->getType()->isIntOrIntVector()) {
 188       if (Value *RHSV = dyn_castNegVal(RHS)) {
 189         Value *NewAdd = Builder->CreateAdd(LHSV, RHSV, "sum");
 190         return BinaryOperator::CreateNeg(NewAdd);
 191       }
 192     }
 193
 194     return BinaryOperator::CreateSub(RHS, LHSV);
 195   }
 196
 197   // A + -B  -->  A - B
 198   if (!isa<Constant>(RHS))
 199     if (Value *V = dyn_castNegVal(RHS))
 200       return BinaryOperator::CreateSub(LHS, V);
 201
 202
 203   ConstantInt *C2;
 204   if (Value *X = dyn_castFoldableMul(LHS, C2)) {
 205     if (X == RHS)   // X*C + X --> X * (C+1)
 206       return BinaryOperator::CreateMul(RHS, AddOne(C2));
 207
 208     // X*C1 + X*C2 --> X * (C1+C2)
 209     ConstantInt *C1;
 210     if (X == dyn_castFoldableMul(RHS, C1))
 211       return BinaryOperator::CreateMul(X, ConstantExpr::getAdd(C1, C2));
 212   }
 213
 214   // X + X*C --> X * (C+1)
 215   if (dyn_castFoldableMul(RHS, C2) == LHS)
 216     return BinaryOperator::CreateMul(LHS, AddOne(C2));
 217
 218   // X + ~X --> -1   since   ~X = -X-1
 219   if (match(LHS, m_Not(m_Specific(RHS))) ||
 220       match(RHS, m_Not(m_Specific(LHS))))
 221     return ReplaceInstUsesWith(I, Constant::getAllOnesValue(I.getType()));
 222
 223   // A+B --> A|B iff A and B have no bits set in common.
 224   if (const IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
 225     APInt Mask = APInt::getAllOnesValue(IT->getBitWidth());
 226     APInt LHSKnownOne(IT->getBitWidth(), 0);
 227     APInt LHSKnownZero(IT->getBitWidth(), 0);
 228     ComputeMaskedBits(LHS, Mask, LHSKnownZero, LHSKnownOne);
 229     if (LHSKnownZero != 0) {
 230       APInt RHSKnownOne(IT->getBitWidth(), 0);
 231       APInt RHSKnownZero(IT->getBitWidth(), 0);
 232       ComputeMaskedBits(RHS, Mask, RHSKnownZero, RHSKnownOne);
 233
 234       // No bits in common -> bitwise or.
 235       if ((LHSKnownZero|RHSKnownZero).isAllOnesValue())
 236         return BinaryOperator::CreateOr(LHS, RHS);
 237     }
 238   }
 239
 240   // W*X + Y*Z --> W * (X+Z)  iff W == Y
 241   if (I.getType()->isIntOrIntVector()) {
 242     Value *W, *X, *Y, *Z;
 243     if (match(LHS, m_Mul(m_Value(W), m_Value(X))) &&
 244         match(RHS, m_Mul(m_Value(Y), m_Value(Z)))) {
 245       if (W != Y) {
 246         if (W == Z) {
 247           std::swap(Y, Z);
 248         } else if (Y == X) {
 249           std::swap(W, X);
 250         } else if (X == Z) {
 251           std::swap(Y, Z);
 252           std::swap(W, X);
 253         }
 254       }
 255
 256       if (W == Y) {
 257         Value *NewAdd = Builder->CreateAdd(X, Z, LHS->getName());
 258         return BinaryOperator::CreateMul(W, NewAdd);
 259       }
 260     }
 261   }
 262
 263   if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
 264     Value *X = 0;
 265     if (match(LHS, m_Not(m_Value(X))))    // ~X + C --> (C-1) - X
 266       return BinaryOperator::CreateSub(SubOne(CRHS), X);
 267
 268     // (X & FF00) + xx00  -> (X+xx00) & FF00
 269     if (LHS->hasOneUse() &&
 270         match(LHS, m_And(m_Value(X), m_ConstantInt(C2)))) {
 271       Constant *Anded = ConstantExpr::getAnd(CRHS, C2);
 272       if (Anded == CRHS) {
 273         // See if all bits from the first bit set in the Add RHS up are included
 274         // in the mask.  First, get the rightmost bit.
 275         const APInt &AddRHSV = CRHS->getValue();
 276
 277         // Form a mask of all bits from the lowest bit added through the top.
 278         APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1));
 279
 280         // See if the and mask includes all of these bits.
 281         APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue());
 282
 283         if (AddRHSHighBits == AddRHSHighBitsAnd) {
 284           // Okay, the xform is safe.  Insert the new add pronto.
 285           Value *NewAdd = Builder->CreateAdd(X, CRHS, LHS->getName());
 286           return BinaryOperator::CreateAnd(NewAdd, C2);
 287         }
 288       }
 289     }
 290
 291     // Try to fold constant add into select arguments.
 292     if (SelectInst *SI = dyn_cast<SelectInst>(LHS))
 293       if (Instruction *R = FoldOpIntoSelect(I, SI))
 294         return R;
 295   }
 296
 297   // add (select X 0 (sub n A)) A  -->  select X A n
 298   {
 299     SelectInst *SI = dyn_cast<SelectInst>(LHS);
 300     Value *A = RHS;
 301     if (!SI) {
 302       SI = dyn_cast<SelectInst>(RHS);
 303       A = LHS;
 304     }
 305     if (SI && SI->hasOneUse()) {
 306       Value *TV = SI->getTrueValue();
 307       Value *FV = SI->getFalseValue();
 308       Value *N;
 309
 310       // Can we fold the add into the argument of the select?
 311       // We check both true and false select arguments for a matching subtract.
 312       if (match(FV, m_Zero()) &&
 313           match(TV, m_Sub(m_Value(N), m_Specific(A))))
 314         // Fold the add into the true select value.
 315         return SelectInst::Create(SI->getCondition(), N, A);
 316       if (match(TV, m_Zero()) &&
 317           match(FV, m_Sub(m_Value(N), m_Specific(A))))
 318         // Fold the add into the false select value.
 319         return SelectInst::Create(SI->getCondition(), A, N);
 320     }
 321   }
 322
 323   // Check for (add (sext x), y), see if we can merge this into an
 324   // integer add followed by a sext.
 325   if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) {
 326     // (add (sext x), cst) --> (sext (add x, cst'))
 327     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) {
 328       Constant *CI =
 329         ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType());
 330       if (LHSConv->hasOneUse() &&
 331           ConstantExpr::getSExt(CI, I.getType()) == RHSC &&
 332           WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) {
 333         // Insert the new, smaller add.
 334         Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
 335                                               CI, "addconv");
 336         return new SExtInst(NewAdd, I.getType());
 337       }
 338     }
 339
 340     // (add (sext x), (sext y)) --> (sext (add int x, y))
 341     if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) {
 342       // Only do this if x/y have the same type, if at last one of them has a
 343       // single use (so we don't increase the number of sexts), and if the
 344       // integer add will not overflow.
 345       if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&&
 346           (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
 347           WillNotOverflowSignedAdd(LHSConv->getOperand(0),
 348                                    RHSConv->getOperand(0))) {
 349         // Insert the new integer add.
 350         Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
 351                                              RHSConv->getOperand(0), "addconv");
 352         return new SExtInst(NewAdd, I.getType());
 353       }
 354     }
 355   }
 356
 357   return Changed ? &I : 0;
 358 }
 359
 360 Instruction *InstCombiner::visitFAdd(BinaryOperator &I) {
 361   bool Changed = SimplifyCommutative(I);
 362   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 363
 364   if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
 365     // X + 0 --> X
 366     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
 367       if (CFP->isExactlyValue(ConstantFP::getNegativeZero
 368                               (I.getType())->getValueAPF()))
 369         return ReplaceInstUsesWith(I, LHS);
 370     }
 371
 372     if (isa<PHINode>(LHS))
 373       if (Instruction *NV = FoldOpIntoPhi(I))
 374         return NV;
 375   }
 376
 377   // -A + B  -->  B - A
 378   // -A + -B  -->  -(A + B)
 379   if (Value *LHSV = dyn_castFNegVal(LHS))
 380     return BinaryOperator::CreateFSub(RHS, LHSV);
 381
 382   // A + -B  -->  A - B
 383   if (!isa<Constant>(RHS))
 384     if (Value *V = dyn_castFNegVal(RHS))
 385       return BinaryOperator::CreateFSub(LHS, V);
 386
 387   // Check for X+0.0.  Simplify it to X if we know X is not -0.0.
 388   if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS))
 389     if (CFP->getValueAPF().isPosZero() && CannotBeNegativeZero(LHS))
 390       return ReplaceInstUsesWith(I, LHS);
 391
 392   // Check for (add double (sitofp x), y), see if we can merge this into an
 393   // integer add followed by a promotion.
 394   if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) {
 395     // (add double (sitofp x), fpcst) --> (sitofp (add int x, intcst))
 396     // ... if the constant fits in the integer value.  This is useful for things
 397     // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer
 398     // requires a constant pool load, and generally allows the add to be better
 399     // instcombined.
 400     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) {
 401       Constant *CI =
 402       ConstantExpr::getFPToSI(CFP, LHSConv->getOperand(0)->getType());
 403       if (LHSConv->hasOneUse() &&
 404           ConstantExpr::getSIToFP(CI, I.getType()) == CFP &&
 405           WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) {
 406         // Insert the new integer add.
 407         Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
 408                                               CI, "addconv");
 409         return new SIToFPInst(NewAdd, I.getType());
 410       }
 411     }
 412
 413     // (add double (sitofp x), (sitofp y)) --> (sitofp (add int x, y))
 414     if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) {
 415       // Only do this if x/y have the same type, if at last one of them has a
 416       // single use (so we don't increase the number of int->fp conversions),
 417       // and if the integer add will not overflow.
 418       if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&&
 419           (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
 420           WillNotOverflowSignedAdd(LHSConv->getOperand(0),
 421                                    RHSConv->getOperand(0))) {
 422         // Insert the new integer add.
 423         Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
 424                                               RHSConv->getOperand(0),"addconv");
 425         return new SIToFPInst(NewAdd, I.getType());
 426       }
 427     }
 428   }
 429
 430   return Changed ? &I : 0;
 431 }
 432
 433
 434 /// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the
 435 /// code necessary to compute the offset from the base pointer (without adding
 436 /// in the base pointer).  Return the result as a signed integer of intptr size.
 437 Value *InstCombiner::EmitGEPOffset(User *GEP) {
 438   TargetData &TD = *getTargetData();
 439   gep_type_iterator GTI = gep_type_begin(GEP);
 440   const Type *IntPtrTy = TD.getIntPtrType(GEP->getContext());
 441   Value *Result = Constant::getNullValue(IntPtrTy);
 442
 443   // Build a mask for high order bits.
 444   unsigned IntPtrWidth = TD.getPointerSizeInBits();
 445   uint64_t PtrSizeMask = ~0ULL >> (64-IntPtrWidth);
 446
 447   for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e;
 448        ++i, ++GTI) {
 449     Value *Op = *i;
 450     uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask;
 451     if (ConstantInt *OpC = dyn_cast<ConstantInt>(Op)) {
 452       if (OpC->isZero()) continue;
 453
 454       // Handle a struct index, which adds its field offset to the pointer.
 455       if (const StructType *STy = dyn_cast<StructType>(*GTI)) {
 456         Size = TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue());
 457
 458         Result = Builder->CreateAdd(Result,
 459                                     ConstantInt::get(IntPtrTy, Size),
 460                                     GEP->getName()+".offs");
 461         continue;
 462       }
 463
 464       Constant *Scale = ConstantInt::get(IntPtrTy, Size);
 465       Constant *OC =
 466               ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/);
 467       Scale = ConstantExpr::getMul(OC, Scale);
 468       // Emit an add instruction.
 469       Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs");
 470       continue;
 471     }
 472     // Convert to correct type.
 473     if (Op->getType() != IntPtrTy)
 474       Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c");
 475     if (Size != 1) {
 476       Constant *Scale = ConstantInt::get(IntPtrTy, Size);
 477       // We'll let instcombine(mul) convert this to a shl if possible.
 478       Op = Builder->CreateMul(Op, Scale, GEP->getName()+".idx");
 479     }
 480
 481     // Emit an add instruction.
 482     Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs");
 483   }
 484   return Result;
 485 }
 486
 487
 488
 489
 490 /// Optimize pointer differences into the same array into a size.  Consider:
 491 ///  &A[10] - &A[0]: we should compile this to "10".  LHS/RHS are the pointer
 492 /// operands to the ptrtoint instructions for the LHS/RHS of the subtract.
 493 ///
 494 Value *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS,
 495                                                const Type *Ty) {
 496   assert(TD && "Must have target data info for this");
 497
 498   // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize
 499   // this.
 500   bool Swapped = false;
 501   GetElementPtrInst *GEP = 0;
 502   ConstantExpr *CstGEP = 0;
 503
 504   // TODO: Could also optimize &A[i] - &A[j] -> "i-j", and "&A.foo[i] - &A.foo".
 505   // For now we require one side to be the base pointer "A" or a constant
 506   // expression derived from it.
 507   if (GetElementPtrInst *LHSGEP = dyn_cast<GetElementPtrInst>(LHS)) {
 508     // (gep X, ...) - X
 509     if (LHSGEP->getOperand(0) == RHS) {
 510       GEP = LHSGEP;
 511       Swapped = false;
 512     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(RHS)) {
 513       // (gep X, ...) - (ce_gep X, ...)
 514       if (CE->getOpcode() == Instruction::GetElementPtr &&
 515           LHSGEP->getOperand(0) == CE->getOperand(0)) {
 516         CstGEP = CE;
 517         GEP = LHSGEP;
 518         Swapped = false;
 519       }
 520     }
 521   }
 522
 523   if (GetElementPtrInst *RHSGEP = dyn_cast<GetElementPtrInst>(RHS)) {
 524     // X - (gep X, ...)
 525     if (RHSGEP->getOperand(0) == LHS) {
 526       GEP = RHSGEP;
 527       Swapped = true;
 528     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(LHS)) {
 529       // (ce_gep X, ...) - (gep X, ...)
 530       if (CE->getOpcode() == Instruction::GetElementPtr &&
 531           RHSGEP->getOperand(0) == CE->getOperand(0)) {
 532         CstGEP = CE;
 533         GEP = RHSGEP;
 534         Swapped = true;
 535       }
 536     }
 537   }
 538
 539   if (GEP == 0)
 540     return 0;
 541
 542   // Emit the offset of the GEP and an intptr_t.
 543   Value *Result = EmitGEPOffset(GEP);
 544
 545   // If we had a constant expression GEP on the other side offsetting the
 546   // pointer, subtract it from the offset we have.
 547   if (CstGEP) {
 548     Value *CstOffset = EmitGEPOffset(CstGEP);
 549     Result = Builder->CreateSub(Result, CstOffset);
 550   }
 551
 552
 553   // If we have p - gep(p, ...)  then we have to negate the result.
 554   if (Swapped)
 555     Result = Builder->CreateNeg(Result, "diff.neg");
 556
 557   return Builder->CreateIntCast(Result, Ty, true);
 558 }
 559
 560
 561 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
 562   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 563
 564   if (Op0 == Op1)                        // sub X, X  -> 0
 565     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 566
 567   // If this is a 'B = x-(-A)', change to B = x+A.  This preserves NSW/NUW.
 568   if (Value *V = dyn_castNegVal(Op1)) {
 569     BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V);
 570     Res->setHasNoSignedWrap(I.hasNoSignedWrap());
 571     Res->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
 572     return Res;
 573   }
 574
 575   if (isa<UndefValue>(Op0))
 576     return ReplaceInstUsesWith(I, Op0);    // undef - X -> undef
 577   if (isa<UndefValue>(Op1))
 578     return ReplaceInstUsesWith(I, Op1);    // X - undef -> undef
 579   if (I.getType()->isInteger(1))
 580     return BinaryOperator::CreateXor(Op0, Op1);
 581
 582   if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) {
 583     // Replace (-1 - A) with (~A).
 584     if (C->isAllOnesValue())
 585       return BinaryOperator::CreateNot(Op1);
 586
 587     // C - ~X == X + (1+C)
 588     Value *X = 0;
 589     if (match(Op1, m_Not(m_Value(X))))
 590       return BinaryOperator::CreateAdd(X, AddOne(C));
 591
 592     // -(X >>u 31) -> (X >>s 31)
 593     // -(X >>s 31) -> (X >>u 31)
 594     if (C->isZero()) {
 595       if (BinaryOperator *SI = dyn_cast<BinaryOperator>(Op1)) {
 596         if (SI->getOpcode() == Instruction::LShr) {
 597           if (ConstantInt *CU = dyn_cast<ConstantInt>(SI->getOperand(1))) {
 598             // Check to see if we are shifting out everything but the sign bit.
 599             if (CU->getLimitedValue(SI->getType()->getPrimitiveSizeInBits()) ==
 600                 SI->getType()->getPrimitiveSizeInBits()-1) {
 601               // Ok, the transformation is safe.  Insert AShr.
 602               return BinaryOperator::Create(Instruction::AShr,
 603                                           SI->getOperand(0), CU, SI->getName());
 604             }
 605           }
 606         } else if (SI->getOpcode() == Instruction::AShr) {
 607           if (ConstantInt *CU = dyn_cast<ConstantInt>(SI->getOperand(1))) {
 608             // Check to see if we are shifting out everything but the sign bit.
 609             if (CU->getLimitedValue(SI->getType()->getPrimitiveSizeInBits()) ==
 610                 SI->getType()->getPrimitiveSizeInBits()-1) {
 611               // Ok, the transformation is safe.  Insert LShr.
 612               return BinaryOperator::CreateLShr(
 613                                           SI->getOperand(0), CU, SI->getName());
 614             }
 615           }
 616         }
 617       }
 618     }
 619
 620     // Try to fold constant sub into select arguments.
 621     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
 622       if (Instruction *R = FoldOpIntoSelect(I, SI))
 623         return R;
 624
 625     // C - zext(bool) -> bool ? C - 1 : C
 626     if (ZExtInst *ZI = dyn_cast<ZExtInst>(Op1))
 627       if (ZI->getSrcTy() == Type::getInt1Ty(I.getContext()))
 628         return SelectInst::Create(ZI->getOperand(0), SubOne(C), C);
 629   }
 630
 631   if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1)) {
 632     if (Op1I->getOpcode() == Instruction::Add) {
 633       if (Op1I->getOperand(0) == Op0)              // X-(X+Y) == -Y
 634         return BinaryOperator::CreateNeg(Op1I->getOperand(1),
 635                                          I.getName());
 636       else if (Op1I->getOperand(1) == Op0)         // X-(Y+X) == -Y
 637         return BinaryOperator::CreateNeg(Op1I->getOperand(0),
 638                                          I.getName());
 639       else if (ConstantInt *CI1 = dyn_cast<ConstantInt>(I.getOperand(0))) {
 640         if (ConstantInt *CI2 = dyn_cast<ConstantInt>(Op1I->getOperand(1)))
 641           // C1-(X+C2) --> (C1-C2)-X
 642           return BinaryOperator::CreateSub(
 643             ConstantExpr::getSub(CI1, CI2), Op1I->getOperand(0));
 644       }
 645     }
 646
 647     if (Op1I->hasOneUse()) {
 648       // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression
 649       // is not used by anyone else...
 650       //
 651       if (Op1I->getOpcode() == Instruction::Sub) {
 652         // Swap the two operands of the subexpr...
 653         Value *IIOp0 = Op1I->getOperand(0), *IIOp1 = Op1I->getOperand(1);
 654         Op1I->setOperand(0, IIOp1);
 655         Op1I->setOperand(1, IIOp0);
 656
 657         // Create the new top level add instruction...
 658         return BinaryOperator::CreateAdd(Op0, Op1);
 659       }
 660
 661       // Replace (A - (A & B)) with (A & ~B) if this is the only use of (A&B)...
 662       //
 663       if (Op1I->getOpcode() == Instruction::And &&
 664           (Op1I->getOperand(0) == Op0 || Op1I->getOperand(1) == Op0)) {
 665         Value *OtherOp = Op1I->getOperand(Op1I->getOperand(0) == Op0);
 666
 667         Value *NewNot = Builder->CreateNot(OtherOp, "B.not");
 668         return BinaryOperator::CreateAnd(Op0, NewNot);
 669       }
 670
 671       // 0 - (X sdiv C)  -> (X sdiv -C)
 672       if (Op1I->getOpcode() == Instruction::SDiv)
 673         if (ConstantInt *CSI = dyn_cast<ConstantInt>(Op0))
 674           if (CSI->isZero())
 675             if (Constant *DivRHS = dyn_cast<Constant>(Op1I->getOperand(1)))
 676               return BinaryOperator::CreateSDiv(Op1I->getOperand(0),
 677                                           ConstantExpr::getNeg(DivRHS));
 678
 679       // X - X*C --> X * (1-C)
 680       ConstantInt *C2 = 0;
 681       if (dyn_castFoldableMul(Op1I, C2) == Op0) {
 682         Constant *CP1 =
 683           ConstantExpr::getSub(ConstantInt::get(I.getType(), 1),
 684                                              C2);
 685         return BinaryOperator::CreateMul(Op0, CP1);
 686       }
 687     }
 688   }
 689
 690   if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
 691     if (Op0I->getOpcode() == Instruction::Add) {
 692       if (Op0I->getOperand(0) == Op1)             // (Y+X)-Y == X
 693         return ReplaceInstUsesWith(I, Op0I->getOperand(1));
 694       else if (Op0I->getOperand(1) == Op1)        // (X+Y)-Y == X
 695         return ReplaceInstUsesWith(I, Op0I->getOperand(0));
 696     } else if (Op0I->getOpcode() == Instruction::Sub) {
 697       if (Op0I->getOperand(0) == Op1)             // (X-Y)-X == -Y
 698         return BinaryOperator::CreateNeg(Op0I->getOperand(1),
 699                                          I.getName());
 700     }
 701   }
 702
 703   ConstantInt *C1;
 704   if (Value *X = dyn_castFoldableMul(Op0, C1)) {
 705     if (X == Op1)  // X*C - X --> X * (C-1)
 706       return BinaryOperator::CreateMul(Op1, SubOne(C1));
 707
 708     ConstantInt *C2;   // X*C1 - X*C2 -> X * (C1-C2)
 709     if (X == dyn_castFoldableMul(Op1, C2))
 710       return BinaryOperator::CreateMul(X, ConstantExpr::getSub(C1, C2));
 711   }
 712
 713   // Optimize pointer differences into the same array into a size.  Consider:
 714   //  &A[10] - &A[0]: we should compile this to "10".
 715   if (TD) {
 716     Value *LHSOp, *RHSOp;
 717     if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
 718         match(Op1, m_PtrToInt(m_Value(RHSOp))))
 719       if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
 720         return ReplaceInstUsesWith(I, Res);
 721
 722     // trunc(p)-trunc(q) -> trunc(p-q)
 723     if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) &&
 724         match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp)))))
 725       if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
 726         return ReplaceInstUsesWith(I, Res);
 727   }
 728
 729   return 0;
 730 }
 731
 732 Instruction *InstCombiner::visitFSub(BinaryOperator &I) {
 733   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 734
 735   // If this is a 'B = x-(-A)', change to B = x+A...
 736   if (Value *V = dyn_castFNegVal(Op1))
 737     return BinaryOperator::CreateFAdd(Op0, V);
 738
 739   return 0;
 740 }