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