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