lib/Transforms/InstCombine/InstCombineCompares.cpp

   1 //===- InstCombineCompares.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 visitICmp and visitFCmp functions.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "InstCombine.h"
  15 #include "llvm/IntrinsicInst.h"
  16 #include "llvm/Analysis/InstructionSimplify.h"
  17 #include "llvm/Analysis/MemoryBuiltins.h"
  18 #include "llvm/Target/TargetData.h"
  19 #include "llvm/Support/ConstantRange.h"
  20 #include "llvm/Support/GetElementPtrTypeIterator.h"
  21 #include "llvm/Support/PatternMatch.h"
  22 using namespace llvm;
  23 using namespace PatternMatch;
  24
  25 /// AddOne - Add one to a ConstantInt
  26 static Constant *AddOne(Constant *C) {
  27   return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
  28 }
  29 /// SubOne - Subtract one from a ConstantInt
  30 static Constant *SubOne(ConstantInt *C) {
  31   return ConstantExpr::getSub(C,  ConstantInt::get(C->getType(), 1));
  32 }
  33
  34 static ConstantInt *ExtractElement(Constant *V, Constant *Idx) {
  35   return cast<ConstantInt>(ConstantExpr::getExtractElement(V, Idx));
  36 }
  37
  38 static bool HasAddOverflow(ConstantInt *Result,
  39                            ConstantInt *In1, ConstantInt *In2,
  40                            bool IsSigned) {
  41   if (IsSigned)
  42     if (In2->getValue().isNegative())
  43       return Result->getValue().sgt(In1->getValue());
  44     else
  45       return Result->getValue().slt(In1->getValue());
  46   else
  47     return Result->getValue().ult(In1->getValue());
  48 }
  49
  50 /// AddWithOverflow - Compute Result = In1+In2, returning true if the result
  51 /// overflowed for this type.
  52 static bool AddWithOverflow(Constant *&Result, Constant *In1,
  53                             Constant *In2, bool IsSigned = false) {
  54   Result = ConstantExpr::getAdd(In1, In2);
  55
  56   if (const VectorType *VTy = dyn_cast<VectorType>(In1->getType())) {
  57     for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
  58       Constant *Idx = ConstantInt::get(Type::getInt32Ty(In1->getContext()), i);
  59       if (HasAddOverflow(ExtractElement(Result, Idx),
  60                          ExtractElement(In1, Idx),
  61                          ExtractElement(In2, Idx),
  62                          IsSigned))
  63         return true;
  64     }
  65     return false;
  66   }
  67
  68   return HasAddOverflow(cast<ConstantInt>(Result),
  69                         cast<ConstantInt>(In1), cast<ConstantInt>(In2),
  70                         IsSigned);
  71 }
  72
  73 static bool HasSubOverflow(ConstantInt *Result,
  74                            ConstantInt *In1, ConstantInt *In2,
  75                            bool IsSigned) {
  76   if (IsSigned)
  77     if (In2->getValue().isNegative())
  78       return Result->getValue().slt(In1->getValue());
  79     else
  80       return Result->getValue().sgt(In1->getValue());
  81   else
  82     return Result->getValue().ugt(In1->getValue());
  83 }
  84
  85 /// SubWithOverflow - Compute Result = In1-In2, returning true if the result
  86 /// overflowed for this type.
  87 static bool SubWithOverflow(Constant *&Result, Constant *In1,
  88                             Constant *In2, bool IsSigned = false) {
  89   Result = ConstantExpr::getSub(In1, In2);
  90
  91   if (const VectorType *VTy = dyn_cast<VectorType>(In1->getType())) {
  92     for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
  93       Constant *Idx = ConstantInt::get(Type::getInt32Ty(In1->getContext()), i);
  94       if (HasSubOverflow(ExtractElement(Result, Idx),
  95                          ExtractElement(In1, Idx),
  96                          ExtractElement(In2, Idx),
  97                          IsSigned))
  98         return true;
  99     }
 100     return false;
 101   }
 102
 103   return HasSubOverflow(cast<ConstantInt>(Result),
 104                         cast<ConstantInt>(In1), cast<ConstantInt>(In2),
 105                         IsSigned);
 106 }
 107
 108 /// isSignBitCheck - Given an exploded icmp instruction, return true if the
 109 /// comparison only checks the sign bit.  If it only checks the sign bit, set
 110 /// TrueIfSigned if the result of the comparison is true when the input value is
 111 /// signed.
 112 static bool isSignBitCheck(ICmpInst::Predicate pred, ConstantInt *RHS,
 113                            bool &TrueIfSigned) {
 114   switch (pred) {
 115   case ICmpInst::ICMP_SLT:   // True if LHS s< 0
 116     TrueIfSigned = true;
 117     return RHS->isZero();
 118   case ICmpInst::ICMP_SLE:   // True if LHS s<= RHS and RHS == -1
 119     TrueIfSigned = true;
 120     return RHS->isAllOnesValue();
 121   case ICmpInst::ICMP_SGT:   // True if LHS s> -1
 122     TrueIfSigned = false;
 123     return RHS->isAllOnesValue();
 124   case ICmpInst::ICMP_UGT:
 125     // True if LHS u> RHS and RHS == high-bit-mask - 1
 126     TrueIfSigned = true;
 127     return RHS->getValue() ==
 128       APInt::getSignedMaxValue(RHS->getType()->getPrimitiveSizeInBits());
 129   case ICmpInst::ICMP_UGE:
 130     // True if LHS u>= RHS and RHS == high-bit-mask (2^7, 2^15, 2^31, etc)
 131     TrueIfSigned = true;
 132     return RHS->getValue().isSignBit();
 133   default:
 134     return false;
 135   }
 136 }
 137
 138 // isHighOnes - Return true if the constant is of the form 1+0+.
 139 // This is the same as lowones(~X).
 140 static bool isHighOnes(const ConstantInt *CI) {
 141   return (~CI->getValue() + 1).isPowerOf2();
 142 }
 143
 144 /// ComputeSignedMinMaxValuesFromKnownBits - Given a signed integer type and a
 145 /// set of known zero and one bits, compute the maximum and minimum values that
 146 /// could have the specified known zero and known one bits, returning them in
 147 /// min/max.
 148 static void ComputeSignedMinMaxValuesFromKnownBits(const APInt& KnownZero,
 149                                                    const APInt& KnownOne,
 150                                                    APInt& Min, APInt& Max) {
 151   assert(KnownZero.getBitWidth() == KnownOne.getBitWidth() &&
 152          KnownZero.getBitWidth() == Min.getBitWidth() &&
 153          KnownZero.getBitWidth() == Max.getBitWidth() &&
 154          "KnownZero, KnownOne and Min, Max must have equal bitwidth.");
 155   APInt UnknownBits = ~(KnownZero|KnownOne);
 156
 157   // The minimum value is when all unknown bits are zeros, EXCEPT for the sign
 158   // bit if it is unknown.
 159   Min = KnownOne;
 160   Max = KnownOne|UnknownBits;
 161
 162   if (UnknownBits.isNegative()) { // Sign bit is unknown
 163     Min.set(Min.getBitWidth()-1);
 164     Max.clear(Max.getBitWidth()-1);
 165   }
 166 }
 167
 168 // ComputeUnsignedMinMaxValuesFromKnownBits - Given an unsigned integer type and
 169 // a set of known zero and one bits, compute the maximum and minimum values that
 170 // could have the specified known zero and known one bits, returning them in
 171 // min/max.
 172 static void ComputeUnsignedMinMaxValuesFromKnownBits(const APInt &KnownZero,
 173                                                      const APInt &KnownOne,
 174                                                      APInt &Min, APInt &Max) {
 175   assert(KnownZero.getBitWidth() == KnownOne.getBitWidth() &&
 176          KnownZero.getBitWidth() == Min.getBitWidth() &&
 177          KnownZero.getBitWidth() == Max.getBitWidth() &&
 178          "Ty, KnownZero, KnownOne and Min, Max must have equal bitwidth.");
 179   APInt UnknownBits = ~(KnownZero|KnownOne);
 180
 181   // The minimum value is when the unknown bits are all zeros.
 182   Min = KnownOne;
 183   // The maximum value is when the unknown bits are all ones.
 184   Max = KnownOne|UnknownBits;
 185 }
 186
 187
 188
 189 /// FoldCmpLoadFromIndexedGlobal - Called we see this pattern:
 190 ///   cmp pred (load (gep GV, ...)), cmpcst
 191 /// where GV is a global variable with a constant initializer.  Try to simplify
 192 /// this into some simple computation that does not need the load.  For example
 193 /// we can optimize "icmp eq (load (gep "foo", 0, i)), 0" into "icmp eq i, 3".
 194 ///
 195 /// If AndCst is non-null, then the loaded value is masked with that constant
 196 /// before doing the comparison.  This handles cases like "A[i]&4 == 0".
 197 Instruction *InstCombiner::
 198 FoldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP, GlobalVariable *GV,
 199                              CmpInst &ICI, ConstantInt *AndCst) {
 200   ConstantArray *Init = dyn_cast<ConstantArray>(GV->getInitializer());
 201   if (Init == 0 || Init->getNumOperands() > 1024) return 0;
 202
 203   // There are many forms of this optimization we can handle, for now, just do
 204   // the simple index into a single-dimensional array.
 205   //
 206   // Require: GEP GV, 0, i {{, constant indices}}
 207   if (GEP->getNumOperands() < 3 ||
 208       !isa<ConstantInt>(GEP->getOperand(1)) ||
 209       !cast<ConstantInt>(GEP->getOperand(1))->isZero() ||
 210       isa<Constant>(GEP->getOperand(2)))
 211     return 0;
 212
 213   // Check that indices after the variable are constants and in-range for the
 214   // type they index.  Collect the indices.  This is typically for arrays of
 215   // structs.
 216   SmallVector<unsigned, 4> LaterIndices;
 217
 218   const Type *EltTy = cast<ArrayType>(Init->getType())->getElementType();
 219   for (unsigned i = 3, e = GEP->getNumOperands(); i != e; ++i) {
 220     ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i));
 221     if (Idx == 0) return 0;  // Variable index.
 222
 223     uint64_t IdxVal = Idx->getZExtValue();
 224     if ((unsigned)IdxVal != IdxVal) return 0; // Too large array index.
 225
 226     if (const StructType *STy = dyn_cast<StructType>(EltTy))
 227       EltTy = STy->getElementType(IdxVal);
 228     else if (const ArrayType *ATy = dyn_cast<ArrayType>(EltTy)) {
 229       if (IdxVal >= ATy->getNumElements()) return 0;
 230       EltTy = ATy->getElementType();
 231     } else {
 232       return 0; // Unknown type.
 233     }
 234
 235     LaterIndices.push_back(IdxVal);
 236   }
 237
 238   enum { Overdefined = -3, Undefined = -2 };
 239
 240   // Variables for our state machines.
 241
 242   // FirstTrueElement/SecondTrueElement - Used to emit a comparison of the form
 243   // "i == 47 | i == 87", where 47 is the first index the condition is true for,
 244   // and 87 is the second (and last) index.  FirstTrueElement is -2 when
 245   // undefined, otherwise set to the first true element.  SecondTrueElement is
 246   // -2 when undefined, -3 when overdefined and >= 0 when that index is true.
 247   int FirstTrueElement = Undefined, SecondTrueElement = Undefined;
 248
 249   // FirstFalseElement/SecondFalseElement - Used to emit a comparison of the
 250   // form "i != 47 & i != 87".  Same state transitions as for true elements.
 251   int FirstFalseElement = Undefined, SecondFalseElement = Undefined;
 252
 253   /// TrueRangeEnd/FalseRangeEnd - In conjunction with First*Element, these
 254   /// define a state machine that triggers for ranges of values that the index
 255   /// is true or false for.  This triggers on things like "abbbbc"[i] == 'b'.
 256   /// This is -2 when undefined, -3 when overdefined, and otherwise the last
 257   /// index in the range (inclusive).  We use -2 for undefined here because we
 258   /// use relative comparisons and don't want 0-1 to match -1.
 259   int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined;
 260
 261   // MagicBitvector - This is a magic bitvector where we set a bit if the
 262   // comparison is true for element 'i'.  If there are 64 elements or less in
 263   // the array, this will fully represent all the comparison results.
 264   uint64_t MagicBitvector = 0;
 265
 266
 267   // Scan the array and see if one of our patterns matches.
 268   Constant *CompareRHS = cast<Constant>(ICI.getOperand(1));
 269   for (unsigned i = 0, e = Init->getNumOperands(); i != e; ++i) {
 270     Constant *Elt = Init->getOperand(i);
 271
 272     // If this is indexing an array of structures, get the structure element.
 273     if (!LaterIndices.empty())
 274       Elt = ConstantExpr::getExtractValue(Elt, LaterIndices.data(),
 275                                           LaterIndices.size());
 276
 277     // If the element is masked, handle it.
 278     if (AndCst) Elt = ConstantExpr::getAnd(Elt, AndCst);
 279
 280     // Find out if the comparison would be true or false for the i'th element.
 281     Constant *C = ConstantFoldCompareInstOperands(ICI.getPredicate(), Elt,
 282                                                   CompareRHS, TD);
 283     // If the result is undef for this element, ignore it.
 284     if (isa<UndefValue>(C)) {
 285       // Extend range state machines to cover this element in case there is an
 286       // undef in the middle of the range.
 287       if (TrueRangeEnd == (int)i-1)
 288         TrueRangeEnd = i;
 289       if (FalseRangeEnd == (int)i-1)
 290         FalseRangeEnd = i;
 291       continue;
 292     }
 293
 294     // If we can't compute the result for any of the elements, we have to give
 295     // up evaluating the entire conditional.
 296     if (!isa<ConstantInt>(C)) return 0;
 297
 298     // Otherwise, we know if the comparison is true or false for this element,
 299     // update our state machines.
 300     bool IsTrueForElt = !cast<ConstantInt>(C)->isZero();
 301
 302     // State machine for single/double/range index comparison.
 303     if (IsTrueForElt) {
 304       // Update the TrueElement state machine.
 305       if (FirstTrueElement == Undefined)
 306         FirstTrueElement = TrueRangeEnd = i;  // First true element.
 307       else {
 308         // Update double-compare state machine.
 309         if (SecondTrueElement == Undefined)
 310           SecondTrueElement = i;
 311         else
 312           SecondTrueElement = Overdefined;
 313
 314         // Update range state machine.
 315         if (TrueRangeEnd == (int)i-1)
 316           TrueRangeEnd = i;
 317         else
 318           TrueRangeEnd = Overdefined;
 319       }
 320     } else {
 321       // Update the FalseElement state machine.
 322       if (FirstFalseElement == Undefined)
 323         FirstFalseElement = FalseRangeEnd = i; // First false element.
 324       else {
 325         // Update double-compare state machine.
 326         if (SecondFalseElement == Undefined)
 327           SecondFalseElement = i;
 328         else
 329           SecondFalseElement = Overdefined;
 330
 331         // Update range state machine.
 332         if (FalseRangeEnd == (int)i-1)
 333           FalseRangeEnd = i;
 334         else
 335           FalseRangeEnd = Overdefined;
 336       }
 337     }
 338
 339
 340     // If this element is in range, update our magic bitvector.
 341     if (i < 64 && IsTrueForElt)
 342       MagicBitvector |= 1ULL << i;
 343
 344     // If all of our states become overdefined, bail out early.  Since the
 345     // predicate is expensive, only check it every 8 elements.  This is only
 346     // really useful for really huge arrays.
 347     if ((i & 8) == 0 && i >= 64 && SecondTrueElement == Overdefined &&
 348         SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined &&
 349         FalseRangeEnd == Overdefined)
 350       return 0;
 351   }
 352
 353   // Now that we've scanned the entire array, emit our new comparison(s).  We
 354   // order the state machines in complexity of the generated code.
 355   Value *Idx = GEP->getOperand(2);
 356
 357
 358   // If the comparison is only true for one or two elements, emit direct
 359   // comparisons.
 360   if (SecondTrueElement != Overdefined) {
 361     // None true -> false.
 362     if (FirstTrueElement == Undefined)
 363       return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(GEP->getContext()));
 364
 365     Value *FirstTrueIdx = ConstantInt::get(Idx->getType(), FirstTrueElement);
 366
 367     // True for one element -> 'i == 47'.
 368     if (SecondTrueElement == Undefined)
 369       return new ICmpInst(ICmpInst::ICMP_EQ, Idx, FirstTrueIdx);
 370
 371     // True for two elements -> 'i == 47 | i == 72'.
 372     Value *C1 = Builder->CreateICmpEQ(Idx, FirstTrueIdx);
 373     Value *SecondTrueIdx = ConstantInt::get(Idx->getType(), SecondTrueElement);
 374     Value *C2 = Builder->CreateICmpEQ(Idx, SecondTrueIdx);
 375     return BinaryOperator::CreateOr(C1, C2);
 376   }
 377
 378   // If the comparison is only false for one or two elements, emit direct
 379   // comparisons.
 380   if (SecondFalseElement != Overdefined) {
 381     // None false -> true.
 382     if (FirstFalseElement == Undefined)
 383       return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(GEP->getContext()));
 384
 385     Value *FirstFalseIdx = ConstantInt::get(Idx->getType(), FirstFalseElement);
 386
 387     // False for one element -> 'i != 47'.
 388     if (SecondFalseElement == Undefined)
 389       return new ICmpInst(ICmpInst::ICMP_NE, Idx, FirstFalseIdx);
 390
 391     // False for two elements -> 'i != 47 & i != 72'.
 392     Value *C1 = Builder->CreateICmpNE(Idx, FirstFalseIdx);
 393     Value *SecondFalseIdx = ConstantInt::get(Idx->getType(),SecondFalseElement);
 394     Value *C2 = Builder->CreateICmpNE(Idx, SecondFalseIdx);
 395     return BinaryOperator::CreateAnd(C1, C2);
 396   }
 397
 398   // If the comparison can be replaced with a range comparison for the elements
 399   // where it is true, emit the range check.
 400   if (TrueRangeEnd != Overdefined) {
 401     assert(TrueRangeEnd != FirstTrueElement && "Should emit single compare");
 402
 403     // Generate (i-FirstTrue) <u (TrueRangeEnd-FirstTrue+1).
 404     if (FirstTrueElement) {
 405       Value *Offs = ConstantInt::get(Idx->getType(), -FirstTrueElement);
 406       Idx = Builder->CreateAdd(Idx, Offs);
 407     }
 408
 409     Value *End = ConstantInt::get(Idx->getType(),
 410                                   TrueRangeEnd-FirstTrueElement+1);
 411     return new ICmpInst(ICmpInst::ICMP_ULT, Idx, End);
 412   }
 413
 414   // False range check.
 415   if (FalseRangeEnd != Overdefined) {
 416     assert(FalseRangeEnd != FirstFalseElement && "Should emit single compare");
 417     // Generate (i-FirstFalse) >u (FalseRangeEnd-FirstFalse).
 418     if (FirstFalseElement) {
 419       Value *Offs = ConstantInt::get(Idx->getType(), -FirstFalseElement);
 420       Idx = Builder->CreateAdd(Idx, Offs);
 421     }
 422
 423     Value *End = ConstantInt::get(Idx->getType(),
 424                                   FalseRangeEnd-FirstFalseElement);
 425     return new ICmpInst(ICmpInst::ICMP_UGT, Idx, End);
 426   }
 427
 428
 429   // If a 32-bit or 64-bit magic bitvector captures the entire comparison state
 430   // of this load, replace it with computation that does:
 431   //   ((magic_cst >> i) & 1) != 0
 432   if (Init->getNumOperands() <= 32 ||
 433       (TD && Init->getNumOperands() <= 64 && TD->isLegalInteger(64))) {
 434     const Type *Ty;
 435     if (Init->getNumOperands() <= 32)
 436       Ty = Type::getInt32Ty(Init->getContext());
 437     else
 438       Ty = Type::getInt64Ty(Init->getContext());
 439     Value *V = Builder->CreateIntCast(Idx, Ty, false);
 440     V = Builder->CreateLShr(ConstantInt::get(Ty, MagicBitvector), V);
 441     V = Builder->CreateAnd(ConstantInt::get(Ty, 1), V);
 442     return new ICmpInst(ICmpInst::ICMP_NE, V, ConstantInt::get(Ty, 0));
 443   }
 444
 445   return 0;
 446 }
 447
 448
 449 /// EvaluateGEPOffsetExpression - Return a value that can be used to compare
 450 /// the *offset* implied by a GEP to zero.  For example, if we have &A[i], we
 451 /// want to return 'i' for "icmp ne i, 0".  Note that, in general, indices can
 452 /// be complex, and scales are involved.  The above expression would also be
 453 /// legal to codegen as "icmp ne (i*4), 0" (assuming A is a pointer to i32).
 454 /// This later form is less amenable to optimization though, and we are allowed
 455 /// to generate the first by knowing that pointer arithmetic doesn't overflow.
 456 ///
 457 /// If we can't emit an optimized form for this expression, this returns null.
 458 ///
 459 static Value *EvaluateGEPOffsetExpression(User *GEP, Instruction &I,
 460                                           InstCombiner &IC) {
 461   TargetData &TD = *IC.getTargetData();
 462   gep_type_iterator GTI = gep_type_begin(GEP);
 463
 464   // Check to see if this gep only has a single variable index.  If so, and if
 465   // any constant indices are a multiple of its scale, then we can compute this
 466   // in terms of the scale of the variable index.  For example, if the GEP
 467   // implies an offset of "12 + i*4", then we can codegen this as "3 + i",
 468   // because the expression will cross zero at the same point.
 469   unsigned i, e = GEP->getNumOperands();
 470   int64_t Offset = 0;
 471   for (i = 1; i != e; ++i, ++GTI) {
 472     if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
 473       // Compute the aggregate offset of constant indices.
 474       if (CI->isZero()) continue;
 475
 476       // Handle a struct index, which adds its field offset to the pointer.
 477       if (const StructType *STy = dyn_cast<StructType>(*GTI)) {
 478         Offset += TD.getStructLayout(STy)->getElementOffset(CI->getZExtValue());
 479       } else {
 480         uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType());
 481         Offset += Size*CI->getSExtValue();
 482       }
 483     } else {
 484       // Found our variable index.
 485       break;
 486     }
 487   }
 488
 489   // If there are no variable indices, we must have a constant offset, just
 490   // evaluate it the general way.
 491   if (i == e) return 0;
 492
 493   Value *VariableIdx = GEP->getOperand(i);
 494   // Determine the scale factor of the variable element.  For example, this is
 495   // 4 if the variable index is into an array of i32.
 496   uint64_t VariableScale = TD.getTypeAllocSize(GTI.getIndexedType());
 497
 498   // Verify that there are no other variable indices.  If so, emit the hard way.
 499   for (++i, ++GTI; i != e; ++i, ++GTI) {
 500     ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i));
 501     if (!CI) return 0;
 502
 503     // Compute the aggregate offset of constant indices.
 504     if (CI->isZero()) continue;
 505
 506     // Handle a struct index, which adds its field offset to the pointer.
 507     if (const StructType *STy = dyn_cast<StructType>(*GTI)) {
 508       Offset += TD.getStructLayout(STy)->getElementOffset(CI->getZExtValue());
 509     } else {
 510       uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType());
 511       Offset += Size*CI->getSExtValue();
 512     }
 513   }
 514
 515   // Okay, we know we have a single variable index, which must be a
 516   // pointer/array/vector index.  If there is no offset, life is simple, return
 517   // the index.
 518   unsigned IntPtrWidth = TD.getPointerSizeInBits();
 519   if (Offset == 0) {
 520     // Cast to intptrty in case a truncation occurs.  If an extension is needed,
 521     // we don't need to bother extending: the extension won't affect where the
 522     // computation crosses zero.
 523     if (VariableIdx->getType()->getPrimitiveSizeInBits() > IntPtrWidth)
 524       VariableIdx = new TruncInst(VariableIdx,
 525                                   TD.getIntPtrType(VariableIdx->getContext()),
 526                                   VariableIdx->getName(), &I);
 527     return VariableIdx;
 528   }
 529
 530   // Otherwise, there is an index.  The computation we will do will be modulo
 531   // the pointer size, so get it.
 532   uint64_t PtrSizeMask = ~0ULL >> (64-IntPtrWidth);
 533
 534   Offset &= PtrSizeMask;
 535   VariableScale &= PtrSizeMask;
 536
 537   // To do this transformation, any constant index must be a multiple of the
 538   // variable scale factor.  For example, we can evaluate "12 + 4*i" as "3 + i",
 539   // but we can't evaluate "10 + 3*i" in terms of i.  Check that the offset is a
 540   // multiple of the variable scale.
 541   int64_t NewOffs = Offset / (int64_t)VariableScale;
 542   if (Offset != NewOffs*(int64_t)VariableScale)
 543     return 0;
 544
 545   // Okay, we can do this evaluation.  Start by converting the index to intptr.
 546   const Type *IntPtrTy = TD.getIntPtrType(VariableIdx->getContext());
 547   if (VariableIdx->getType() != IntPtrTy)
 548     VariableIdx = CastInst::CreateIntegerCast(VariableIdx, IntPtrTy,
 549                                               true /*SExt*/,
 550                                               VariableIdx->getName(), &I);
 551   Constant *OffsetVal = ConstantInt::get(IntPtrTy, NewOffs);
 552   return BinaryOperator::CreateAdd(VariableIdx, OffsetVal, "offset", &I);
 553 }
 554
 555 /// FoldGEPICmp - Fold comparisons between a GEP instruction and something
 556 /// else.  At this point we know that the GEP is on the LHS of the comparison.
 557 Instruction *InstCombiner::FoldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
 558                                        ICmpInst::Predicate Cond,
 559                                        Instruction &I) {
 560   // Look through bitcasts.
 561   if (BitCastInst *BCI = dyn_cast<BitCastInst>(RHS))
 562     RHS = BCI->getOperand(0);
 563
 564   Value *PtrBase = GEPLHS->getOperand(0);
 565   if (TD && PtrBase == RHS && GEPLHS->isInBounds()) {
 566     // ((gep Ptr, OFFSET) cmp Ptr)   ---> (OFFSET cmp 0).
 567     // This transformation (ignoring the base and scales) is valid because we
 568     // know pointers can't overflow since the gep is inbounds.  See if we can
 569     // output an optimized form.
 570     Value *Offset = EvaluateGEPOffsetExpression(GEPLHS, I, *this);
 571
 572     // If not, synthesize the offset the hard way.
 573     if (Offset == 0)
 574       Offset = EmitGEPOffset(GEPLHS);
 575     return new ICmpInst(ICmpInst::getSignedPredicate(Cond), Offset,
 576                         Constant::getNullValue(Offset->getType()));
 577   } else if (GEPOperator *GEPRHS = dyn_cast<GEPOperator>(RHS)) {
 578     // If the base pointers are different, but the indices are the same, just
 579     // compare the base pointer.
 580     if (PtrBase != GEPRHS->getOperand(0)) {
 581       bool IndicesTheSame = GEPLHS->getNumOperands()==GEPRHS->getNumOperands();
 582       IndicesTheSame &= GEPLHS->getOperand(0)->getType() ==
 583                         GEPRHS->getOperand(0)->getType();
 584       if (IndicesTheSame)
 585         for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i)
 586           if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
 587             IndicesTheSame = false;
 588             break;
 589           }
 590
 591       // If all indices are the same, just compare the base pointers.
 592       if (IndicesTheSame)
 593         return new ICmpInst(ICmpInst::getSignedPredicate(Cond),
 594                             GEPLHS->getOperand(0), GEPRHS->getOperand(0));
 595
 596       // Otherwise, the base pointers are different and the indices are
 597       // different, bail out.
 598       return 0;
 599     }
 600
 601     // If one of the GEPs has all zero indices, recurse.
 602     bool AllZeros = true;
 603     for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i)
 604       if (!isa<Constant>(GEPLHS->getOperand(i)) ||
 605           !cast<Constant>(GEPLHS->getOperand(i))->isNullValue()) {
 606         AllZeros = false;
 607         break;
 608       }
 609     if (AllZeros)
 610       return FoldGEPICmp(GEPRHS, GEPLHS->getOperand(0),
 611                           ICmpInst::getSwappedPredicate(Cond), I);
 612
 613     // If the other GEP has all zero indices, recurse.
 614     AllZeros = true;
 615     for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
 616       if (!isa<Constant>(GEPRHS->getOperand(i)) ||
 617           !cast<Constant>(GEPRHS->getOperand(i))->isNullValue()) {
 618         AllZeros = false;
 619         break;
 620       }
 621     if (AllZeros)
 622       return FoldGEPICmp(GEPLHS, GEPRHS->getOperand(0), Cond, I);
 623
 624     if (GEPLHS->getNumOperands() == GEPRHS->getNumOperands()) {
 625       // If the GEPs only differ by one index, compare it.
 626       unsigned NumDifferences = 0;  // Keep track of # differences.
 627       unsigned DiffOperand = 0;     // The operand that differs.
 628       for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
 629         if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
 630           if (GEPLHS->getOperand(i)->getType()->getPrimitiveSizeInBits() !=
 631                    GEPRHS->getOperand(i)->getType()->getPrimitiveSizeInBits()) {
 632             // Irreconcilable differences.
 633             NumDifferences = 2;
 634             break;
 635           } else {
 636             if (NumDifferences++) break;
 637             DiffOperand = i;
 638           }
 639         }
 640
 641       if (NumDifferences == 0)   // SAME GEP?
 642         return ReplaceInstUsesWith(I, // No comparison is needed here.
 643                                ConstantInt::get(Type::getInt1Ty(I.getContext()),
 644                                              ICmpInst::isTrueWhenEqual(Cond)));
 645
 646       else if (NumDifferences == 1) {
 647         Value *LHSV = GEPLHS->getOperand(DiffOperand);
 648         Value *RHSV = GEPRHS->getOperand(DiffOperand);
 649         // Make sure we do a signed comparison here.
 650         return new ICmpInst(ICmpInst::getSignedPredicate(Cond), LHSV, RHSV);
 651       }
 652     }
 653
 654     // Only lower this if the icmp is the only user of the GEP or if we expect
 655     // the result to fold to a constant!
 656     if (TD &&
 657         (isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) &&
 658         (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
 659       // ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2)  --->  (OFFSET1 cmp OFFSET2)
 660       Value *L = EmitGEPOffset(GEPLHS);
 661       Value *R = EmitGEPOffset(GEPRHS);
 662       return new ICmpInst(ICmpInst::getSignedPredicate(Cond), L, R);
 663     }
 664   }
 665   return 0;
 666 }
 667
 668 /// FoldICmpAddOpCst - Fold "icmp pred (X+CI), X".
 669 Instruction *InstCombiner::FoldICmpAddOpCst(ICmpInst &ICI,
 670                                             Value *X, ConstantInt *CI,
 671                                             ICmpInst::Predicate Pred,
 672                                             Value *TheAdd) {
 673   // If we have X+0, exit early (simplifying logic below) and let it get folded
 674   // elsewhere.   icmp X+0, X  -> icmp X, X
 675   if (CI->isZero()) {
 676     bool isTrue = ICmpInst::isTrueWhenEqual(Pred);
 677     return ReplaceInstUsesWith(ICI, ConstantInt::get(ICI.getType(), isTrue));
 678   }
 679
 680   // (X+4) == X -> false.
 681   if (Pred == ICmpInst::ICMP_EQ)
 682     return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(X->getContext()));
 683
 684   // (X+4) != X -> true.
 685   if (Pred == ICmpInst::ICMP_NE)
 686     return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(X->getContext()));
 687
 688   // If this is an instruction (as opposed to constantexpr) get NUW/NSW info.
 689   bool isNUW = false, isNSW = false;
 690   if (BinaryOperator *Add = dyn_cast<BinaryOperator>(TheAdd)) {
 691     isNUW = Add->hasNoUnsignedWrap();
 692     isNSW = Add->hasNoSignedWrap();
 693   }
 694
 695   // From this point on, we know that (X+C <= X) --> (X+C < X) because C != 0,
 696   // so the values can never be equal.  Similiarly for all other "or equals"
 697   // operators.
 698
 699   // (X+1) <u X        --> X >u (MAXUINT-1)        --> X != 255
 700   // (X+2) <u X        --> X >u (MAXUINT-2)        --> X > 253
 701   // (X+MAXUINT) <u X  --> X >u (MAXUINT-MAXUINT)  --> X != 0
 702   if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE) {
 703     // If this is an NUW add, then this is always false.
 704     if (isNUW)
 705       return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(X->getContext()));
 706
 707     Value *R = ConstantExpr::getSub(ConstantInt::get(CI->getType(), -1ULL), CI);
 708     return new ICmpInst(ICmpInst::ICMP_UGT, X, R);
 709   }
 710
 711   // (X+1) >u X        --> X <u (0-1)        --> X != 255
 712   // (X+2) >u X        --> X <u (0-2)        --> X <u 254
 713   // (X+MAXUINT) >u X  --> X <u (0-MAXUINT)  --> X <u 1  --> X == 0
 714   if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE) {
 715     // If this is an NUW add, then this is always true.
 716     if (isNUW)
 717       return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(X->getContext()));
 718     return new ICmpInst(ICmpInst::ICMP_ULT, X, ConstantExpr::getNeg(CI));
 719   }
 720
 721   unsigned BitWidth = CI->getType()->getPrimitiveSizeInBits();
 722   ConstantInt *SMax = ConstantInt::get(X->getContext(),
 723                                        APInt::getSignedMaxValue(BitWidth));
 724
 725   // (X+ 1) <s X       --> X >s (MAXSINT-1)          --> X == 127
 726   // (X+ 2) <s X       --> X >s (MAXSINT-2)          --> X >s 125
 727   // (X+MAXSINT) <s X  --> X >s (MAXSINT-MAXSINT)    --> X >s 0
 728   // (X+MINSINT) <s X  --> X >s (MAXSINT-MINSINT)    --> X >s -1
 729   // (X+ -2) <s X      --> X >s (MAXSINT- -2)        --> X >s 126
 730   // (X+ -1) <s X      --> X >s (MAXSINT- -1)        --> X != 127
 731   if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) {
 732     // If this is an NSW add, then we have two cases: if the constant is
 733     // positive, then this is always false, if negative, this is always true.
 734     if (isNSW) {
 735       bool isTrue = CI->getValue().isNegative();
 736       return ReplaceInstUsesWith(ICI, ConstantInt::get(ICI.getType(), isTrue));
 737     }
 738
 739     return new ICmpInst(ICmpInst::ICMP_SGT, X, ConstantExpr::getSub(SMax, CI));
 740   }
 741
 742   // (X+ 1) >s X       --> X <s (MAXSINT-(1-1))       --> X != 127
 743   // (X+ 2) >s X       --> X <s (MAXSINT-(2-1))       --> X <s 126
 744   // (X+MAXSINT) >s X  --> X <s (MAXSINT-(MAXSINT-1)) --> X <s 1
 745   // (X+MINSINT) >s X  --> X <s (MAXSINT-(MINSINT-1)) --> X <s -2
 746   // (X+ -2) >s X      --> X <s (MAXSINT-(-2-1))      --> X <s -126
 747   // (X+ -1) >s X      --> X <s (MAXSINT-(-1-1))      --> X == -128
 748
 749   // If this is an NSW add, then we have two cases: if the constant is
 750   // positive, then this is always true, if negative, this is always false.
 751   if (isNSW) {
 752     bool isTrue = !CI->getValue().isNegative();
 753     return ReplaceInstUsesWith(ICI, ConstantInt::get(ICI.getType(), isTrue));
 754   }
 755
 756   assert(Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE);
 757   Constant *C = ConstantInt::get(X->getContext(), CI->getValue()-1);
 758   return new ICmpInst(ICmpInst::ICMP_SLT, X, ConstantExpr::getSub(SMax, C));
 759 }
 760
 761 /// FoldICmpDivCst - Fold "icmp pred, ([su]div X, DivRHS), CmpRHS" where DivRHS
 762 /// and CmpRHS are both known to be integer constants.
 763 Instruction *InstCombiner::FoldICmpDivCst(ICmpInst &ICI, BinaryOperator *DivI,
 764                                           ConstantInt *DivRHS) {
 765   ConstantInt *CmpRHS = cast<ConstantInt>(ICI.getOperand(1));
 766   const APInt &CmpRHSV = CmpRHS->getValue();
 767
 768   // FIXME: If the operand types don't match the type of the divide
 769   // then don't attempt this transform. The code below doesn't have the
 770   // logic to deal with a signed divide and an unsigned compare (and
 771   // vice versa). This is because (x /s C1) <s C2  produces different
 772   // results than (x /s C1) <u C2 or (x /u C1) <s C2 or even
 773   // (x /u C1) <u C2.  Simply casting the operands and result won't
 774   // work. :(  The if statement below tests that condition and bails
 775   // if it finds it.
 776   bool DivIsSigned = DivI->getOpcode() == Instruction::SDiv;
 777   if (!ICI.isEquality() && DivIsSigned != ICI.isSigned())
 778     return 0;
 779   if (DivRHS->isZero())
 780     return 0; // The ProdOV computation fails on divide by zero.
 781   if (DivIsSigned && DivRHS->isAllOnesValue())
 782     return 0; // The overflow computation also screws up here
 783   if (DivRHS->isOne())
 784     return 0; // Not worth bothering, and eliminates some funny cases
 785               // with INT_MIN.
 786
 787   // Compute Prod = CI * DivRHS. We are essentially solving an equation
 788   // of form X/C1=C2. We solve for X by multiplying C1 (DivRHS) and
 789   // C2 (CI). By solving for X we can turn this into a range check
 790   // instead of computing a divide.
 791   Constant *Prod = ConstantExpr::getMul(CmpRHS, DivRHS);
 792
 793   // Determine if the product overflows by seeing if the product is
 794   // not equal to the divide. Make sure we do the same kind of divide
 795   // as in the LHS instruction that we're folding.
 796   bool ProdOV = (DivIsSigned ? ConstantExpr::getSDiv(Prod, DivRHS) :
 797                  ConstantExpr::getUDiv(Prod, DivRHS)) != CmpRHS;
 798
 799   // Get the ICmp opcode
 800   ICmpInst::Predicate Pred = ICI.getPredicate();
 801
 802   // Figure out the interval that is being checked.  For example, a comparison
 803   // like "X /u 5 == 0" is really checking that X is in the interval [0, 5).
 804   // Compute this interval based on the constants involved and the signedness of
 805   // the compare/divide.  This computes a half-open interval, keeping track of
 806   // whether either value in the interval overflows.  After analysis each
 807   // overflow variable is set to 0 if it's corresponding bound variable is valid
 808   // -1 if overflowed off the bottom end, or +1 if overflowed off the top end.
 809   int LoOverflow = 0, HiOverflow = 0;
 810   Constant *LoBound = 0, *HiBound = 0;
 811
 812   if (!DivIsSigned) {  // udiv
 813     // e.g. X/5 op 3  --> [15, 20)
 814     LoBound = Prod;
 815     HiOverflow = LoOverflow = ProdOV;
 816     if (!HiOverflow)
 817       HiOverflow = AddWithOverflow(HiBound, LoBound, DivRHS, false);
 818   } else if (DivRHS->getValue().isStrictlyPositive()) { // Divisor is > 0.
 819     if (CmpRHSV == 0) {       // (X / pos) op 0
 820       // Can't overflow.  e.g.  X/2 op 0 --> [-1, 2)
 821       LoBound = cast<ConstantInt>(ConstantExpr::getNeg(SubOne(DivRHS)));
 822       HiBound = DivRHS;
 823     } else if (CmpRHSV.isStrictlyPositive()) {   // (X / pos) op pos
 824       LoBound = Prod;     // e.g.   X/5 op 3 --> [15, 20)
 825       HiOverflow = LoOverflow = ProdOV;
 826       if (!HiOverflow)
 827         HiOverflow = AddWithOverflow(HiBound, Prod, DivRHS, true);
 828     } else {                       // (X / pos) op neg
 829       // e.g. X/5 op -3  --> [-15-4, -15+1) --> [-19, -14)
 830       HiBound = AddOne(Prod);
 831       LoOverflow = HiOverflow = ProdOV ? -1 : 0;
 832       if (!LoOverflow) {
 833         ConstantInt* DivNeg =
 834                          cast<ConstantInt>(ConstantExpr::getNeg(DivRHS));
 835         LoOverflow = AddWithOverflow(LoBound, HiBound, DivNeg, true) ? -1 : 0;
 836        }
 837     }
 838   } else if (DivRHS->getValue().isNegative()) { // Divisor is < 0.
 839     if (CmpRHSV == 0) {       // (X / neg) op 0
 840       // e.g. X/-5 op 0  --> [-4, 5)
 841       LoBound = AddOne(DivRHS);
 842       HiBound = cast<ConstantInt>(ConstantExpr::getNeg(DivRHS));
 843       if (HiBound == DivRHS) {     // -INTMIN = INTMIN
 844         HiOverflow = 1;            // [INTMIN+1, overflow)
 845         HiBound = 0;               // e.g. X/INTMIN = 0 --> X > INTMIN
 846       }
 847     } else if (CmpRHSV.isStrictlyPositive()) {   // (X / neg) op pos
 848       // e.g. X/-5 op 3  --> [-19, -14)
 849       HiBound = AddOne(Prod);
 850       HiOverflow = LoOverflow = ProdOV ? -1 : 0;
 851       if (!LoOverflow)
 852         LoOverflow = AddWithOverflow(LoBound, HiBound, DivRHS, true) ? -1 : 0;
 853     } else {                       // (X / neg) op neg
 854       LoBound = Prod;       // e.g. X/-5 op -3  --> [15, 20)
 855       LoOverflow = HiOverflow = ProdOV;
 856       if (!HiOverflow)
 857         HiOverflow = SubWithOverflow(HiBound, Prod, DivRHS, true);
 858     }
 859
 860     // Dividing by a negative swaps the condition.  LT <-> GT
 861     Pred = ICmpInst::getSwappedPredicate(Pred);
 862   }
 863
 864   Value *X = DivI->getOperand(0);
 865   switch (Pred) {
 866   default: llvm_unreachable("Unhandled icmp opcode!");
 867   case ICmpInst::ICMP_EQ:
 868     if (LoOverflow && HiOverflow)
 869       return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(ICI.getContext()));
 870     else if (HiOverflow)
 871       return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE :
 872                           ICmpInst::ICMP_UGE, X, LoBound);
 873     else if (LoOverflow)
 874       return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT :
 875                           ICmpInst::ICMP_ULT, X, HiBound);
 876     else
 877       return InsertRangeTest(X, LoBound, HiBound, DivIsSigned, true, ICI);
 878   case ICmpInst::ICMP_NE:
 879     if (LoOverflow && HiOverflow)
 880       return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(ICI.getContext()));
 881     else if (HiOverflow)
 882       return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT :
 883                           ICmpInst::ICMP_ULT, X, LoBound);
 884     else if (LoOverflow)
 885       return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE :
 886                           ICmpInst::ICMP_UGE, X, HiBound);
 887     else
 888       return InsertRangeTest(X, LoBound, HiBound, DivIsSigned, false, ICI);
 889   case ICmpInst::ICMP_ULT:
 890   case ICmpInst::ICMP_SLT:
 891     if (LoOverflow == +1)   // Low bound is greater than input range.
 892       return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(ICI.getContext()));
 893     if (LoOverflow == -1)   // Low bound is less than input range.
 894       return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(ICI.getContext()));
 895     return new ICmpInst(Pred, X, LoBound);
 896   case ICmpInst::ICMP_UGT:
 897   case ICmpInst::ICMP_SGT:
 898     if (HiOverflow == +1)       // High bound greater than input range.
 899       return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(ICI.getContext()));
 900     else if (HiOverflow == -1)  // High bound less than input range.
 901       return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(ICI.getContext()));
 902     if (Pred == ICmpInst::ICMP_UGT)
 903       return new ICmpInst(ICmpInst::ICMP_UGE, X, HiBound);
 904     else
 905       return new ICmpInst(ICmpInst::ICMP_SGE, X, HiBound);
 906   }
 907 }
 908
 909
 910 /// visitICmpInstWithInstAndIntCst - Handle "icmp (instr, intcst)".
 911 ///
 912 Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
 913                                                           Instruction *LHSI,
 914                                                           ConstantInt *RHS) {
 915   const APInt &RHSV = RHS->getValue();
 916
 917   switch (LHSI->getOpcode()) {
 918   case Instruction::Trunc:
 919     if (ICI.isEquality() && LHSI->hasOneUse()) {
 920       // Simplify icmp eq (trunc x to i8), 42 -> icmp eq x, 42|highbits if all
 921       // of the high bits truncated out of x are known.
 922       unsigned DstBits = LHSI->getType()->getPrimitiveSizeInBits(),
 923              SrcBits = LHSI->getOperand(0)->getType()->getPrimitiveSizeInBits();
 924       APInt Mask(APInt::getHighBitsSet(SrcBits, SrcBits-DstBits));
 925       APInt KnownZero(SrcBits, 0), KnownOne(SrcBits, 0);
 926       ComputeMaskedBits(LHSI->getOperand(0), Mask, KnownZero, KnownOne);
 927
 928       // If all the high bits are known, we can do this xform.
 929       if ((KnownZero|KnownOne).countLeadingOnes() >= SrcBits-DstBits) {
 930         // Pull in the high bits from known-ones set.
 931         APInt NewRHS(RHS->getValue());
 932         NewRHS.zext(SrcBits);
 933         NewRHS |= KnownOne;
 934         return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0),
 935                             ConstantInt::get(ICI.getContext(), NewRHS));
 936       }
 937     }
 938     break;
 939
 940   case Instruction::Xor:         // (icmp pred (xor X, XorCST), CI)
 941     if (ConstantInt *XorCST = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
 942       // If this is a comparison that tests the signbit (X < 0) or (x > -1),
 943       // fold the xor.
 944       if ((ICI.getPredicate() == ICmpInst::ICMP_SLT && RHSV == 0) ||
 945           (ICI.getPredicate() == ICmpInst::ICMP_SGT && RHSV.isAllOnesValue())) {
 946         Value *CompareVal = LHSI->getOperand(0);
 947
 948         // If the sign bit of the XorCST is not set, there is no change to
 949         // the operation, just stop using the Xor.
 950         if (!XorCST->getValue().isNegative()) {
 951           ICI.setOperand(0, CompareVal);
 952           Worklist.Add(LHSI);
 953           return &ICI;
 954         }
 955
 956         // Was the old condition true if the operand is positive?
 957         bool isTrueIfPositive = ICI.getPredicate() == ICmpInst::ICMP_SGT;
 958
 959         // If so, the new one isn't.
 960         isTrueIfPositive ^= true;
 961
 962         if (isTrueIfPositive)
 963           return new ICmpInst(ICmpInst::ICMP_SGT, CompareVal,
 964                               SubOne(RHS));
 965         else
 966           return new ICmpInst(ICmpInst::ICMP_SLT, CompareVal,
 967                               AddOne(RHS));
 968       }
 969
 970       if (LHSI->hasOneUse()) {
 971         // (icmp u/s (xor A SignBit), C) -> (icmp s/u A, (xor C SignBit))
 972         if (!ICI.isEquality() && XorCST->getValue().isSignBit()) {
 973           const APInt &SignBit = XorCST->getValue();
 974           ICmpInst::Predicate Pred = ICI.isSigned()
 975                                          ? ICI.getUnsignedPredicate()
 976                                          : ICI.getSignedPredicate();
 977           return new ICmpInst(Pred, LHSI->getOperand(0),
 978                               ConstantInt::get(ICI.getContext(),
 979                                                RHSV ^ SignBit));
 980         }
 981
 982         // (icmp u/s (xor A ~SignBit), C) -> (icmp s/u (xor C ~SignBit), A)
 983         if (!ICI.isEquality() && XorCST->getValue().isMaxSignedValue()) {
 984           const APInt &NotSignBit = XorCST->getValue();
 985           ICmpInst::Predicate Pred = ICI.isSigned()
 986                                          ? ICI.getUnsignedPredicate()
 987                                          : ICI.getSignedPredicate();
 988           Pred = ICI.getSwappedPredicate(Pred);
 989           return new ICmpInst(Pred, LHSI->getOperand(0),
 990                               ConstantInt::get(ICI.getContext(),
 991                                                RHSV ^ NotSignBit));
 992         }
 993       }
 994     }
 995     break;
 996   case Instruction::And:         // (icmp pred (and X, AndCST), RHS)
 997     if (LHSI->hasOneUse() && isa<ConstantInt>(LHSI->getOperand(1)) &&
 998         LHSI->getOperand(0)->hasOneUse()) {
 999       ConstantInt *AndCST = cast<ConstantInt>(LHSI->getOperand(1));
1000
1001       // If the LHS is an AND of a truncating cast, we can widen the
1002       // and/compare to be the input width without changing the value
1003       // produced, eliminating a cast.
1004       if (TruncInst *Cast = dyn_cast<TruncInst>(LHSI->getOperand(0))) {
1005         // We can do this transformation if either the AND constant does not
1006         // have its sign bit set or if it is an equality comparison.
1007         // Extending a relational comparison when we're checking the sign
1008         // bit would not work.
1009         if (Cast->hasOneUse() &&
1010             (ICI.isEquality() ||
1011              (AndCST->getValue().isNonNegative() && RHSV.isNonNegative()))) {
1012           uint32_t BitWidth =
1013             cast<IntegerType>(Cast->getOperand(0)->getType())->getBitWidth();
1014           APInt NewCST = AndCST->getValue();
1015           NewCST.zext(BitWidth);
1016           APInt NewCI = RHSV;
1017           NewCI.zext(BitWidth);
1018           Value *NewAnd =
1019             Builder->CreateAnd(Cast->getOperand(0),
1020                            ConstantInt::get(ICI.getContext(), NewCST),
1021                                LHSI->getName());
1022           return new ICmpInst(ICI.getPredicate(), NewAnd,
1023                               ConstantInt::get(ICI.getContext(), NewCI));
1024         }
1025       }
1026
1027       // If this is: (X >> C1) & C2 != C3 (where any shift and any compare
1028       // could exist), turn it into (X & (C2 << C1)) != (C3 << C1).  This
1029       // happens a LOT in code produced by the C front-end, for bitfield
1030       // access.
1031       BinaryOperator *Shift = dyn_cast<BinaryOperator>(LHSI->getOperand(0));
1032       if (Shift && !Shift->isShift())
1033         Shift = 0;
1034
1035       ConstantInt *ShAmt;
1036       ShAmt = Shift ? dyn_cast<ConstantInt>(Shift->getOperand(1)) : 0;
1037       const Type *Ty = Shift ? Shift->getType() : 0;  // Type of the shift.
1038       const Type *AndTy = AndCST->getType();          // Type of the and.
1039
1040       // We can fold this as long as we can't shift unknown bits
1041       // into the mask.  This can only happen with signed shift
1042       // rights, as they sign-extend.
1043       if (ShAmt) {
1044         bool CanFold = Shift->isLogicalShift();
1045         if (!CanFold) {
1046           // To test for the bad case of the signed shr, see if any
1047           // of the bits shifted in could be tested after the mask.
1048           uint32_t TyBits = Ty->getPrimitiveSizeInBits();
1049           int ShAmtVal = TyBits - ShAmt->getLimitedValue(TyBits);
1050
1051           uint32_t BitWidth = AndTy->getPrimitiveSizeInBits();
1052           if ((APInt::getHighBitsSet(BitWidth, BitWidth-ShAmtVal) &
1053                AndCST->getValue()) == 0)
1054             CanFold = true;
1055         }
1056
1057         if (CanFold) {
1058           Constant *NewCst;
1059           if (Shift->getOpcode() == Instruction::Shl)
1060             NewCst = ConstantExpr::getLShr(RHS, ShAmt);
1061           else
1062             NewCst = ConstantExpr::getShl(RHS, ShAmt);
1063
1064           // Check to see if we are shifting out any of the bits being
1065           // compared.
1066           if (ConstantExpr::get(Shift->getOpcode(),
1067                                        NewCst, ShAmt) != RHS) {
1068             // If we shifted bits out, the fold is not going to work out.
1069             // As a special case, check to see if this means that the
1070             // result is always true or false now.
1071             if (ICI.getPredicate() == ICmpInst::ICMP_EQ)
1072               return ReplaceInstUsesWith(ICI,
1073                                        ConstantInt::getFalse(ICI.getContext()));
1074             if (ICI.getPredicate() == ICmpInst::ICMP_NE)
1075               return ReplaceInstUsesWith(ICI,
1076                                        ConstantInt::getTrue(ICI.getContext()));
1077           } else {
1078             ICI.setOperand(1, NewCst);
1079             Constant *NewAndCST;
1080             if (Shift->getOpcode() == Instruction::Shl)
1081               NewAndCST = ConstantExpr::getLShr(AndCST, ShAmt);
1082             else
1083               NewAndCST = ConstantExpr::getShl(AndCST, ShAmt);
1084             LHSI->setOperand(1, NewAndCST);
1085             LHSI->setOperand(0, Shift->getOperand(0));
1086             Worklist.Add(Shift); // Shift is dead.
1087             return &ICI;
1088           }
1089         }
1090       }
1091
1092       // Turn ((X >> Y) & C) == 0  into  (X & (C << Y)) == 0.  The later is
1093       // preferable because it allows the C<<Y expression to be hoisted out
1094       // of a loop if Y is invariant and X is not.
1095       if (Shift && Shift->hasOneUse() && RHSV == 0 &&
1096           ICI.isEquality() && !Shift->isArithmeticShift() &&
1097           !isa<Constant>(Shift->getOperand(0))) {
1098         // Compute C << Y.
1099         Value *NS;
1100         if (Shift->getOpcode() == Instruction::LShr) {
1101           NS = Builder->CreateShl(AndCST, Shift->getOperand(1), "tmp");
1102         } else {
1103           // Insert a logical shift.
1104           NS = Builder->CreateLShr(AndCST, Shift->getOperand(1), "tmp");
1105         }
1106
1107         // Compute X & (C << Y).
1108         Value *NewAnd =
1109           Builder->CreateAnd(Shift->getOperand(0), NS, LHSI->getName());
1110
1111         ICI.setOperand(0, NewAnd);
1112         return &ICI;
1113       }
1114     }
1115
1116     // Try to optimize things like "A[i]&42 == 0" to index computations.
1117     if (LoadInst *LI = dyn_cast<LoadInst>(LHSI->getOperand(0))) {
1118       if (GetElementPtrInst *GEP =
1119           dyn_cast<GetElementPtrInst>(LI->getOperand(0)))
1120         if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
1121           if (GV->isConstant() && GV->hasDefinitiveInitializer() &&
1122               !LI->isVolatile() && isa<ConstantInt>(LHSI->getOperand(1))) {
1123             ConstantInt *C = cast<ConstantInt>(LHSI->getOperand(1));
1124             if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV,ICI, C))
1125               return Res;
1126           }
1127     }
1128     break;
1129
1130   case Instruction::Or: {
1131     if (!ICI.isEquality() || !RHS->isNullValue() || !LHSI->hasOneUse())
1132       break;
1133     Value *P, *Q;
1134     if (match(LHSI, m_Or(m_PtrToInt(m_Value(P)), m_PtrToInt(m_Value(Q))))) {
1135       // Simplify icmp eq (or (ptrtoint P), (ptrtoint Q)), 0
1136       // -> and (icmp eq P, null), (icmp eq Q, null).
1137
1138       Value *ICIP = Builder->CreateICmp(ICI.getPredicate(), P,
1139                                         Constant::getNullValue(P->getType()));
1140       Value *ICIQ = Builder->CreateICmp(ICI.getPredicate(), Q,
1141                                         Constant::getNullValue(Q->getType()));
1142       Instruction *Op;
1143       if (ICI.getPredicate() == ICmpInst::ICMP_EQ)
1144         Op = BinaryOperator::CreateAnd(ICIP, ICIQ);
1145       else
1146         Op = BinaryOperator::CreateOr(ICIP, ICIQ);
1147       return Op;
1148     }
1149     break;
1150   }
1151
1152   case Instruction::Shl: {       // (icmp pred (shl X, ShAmt), CI)
1153     ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1));
1154     if (!ShAmt) break;
1155
1156     uint32_t TypeBits = RHSV.getBitWidth();
1157
1158     // Check that the shift amount is in range.  If not, don't perform
1159     // undefined shifts.  When the shift is visited it will be
1160     // simplified.
1161     if (ShAmt->uge(TypeBits))
1162       break;
1163
1164     if (ICI.isEquality()) {
1165       // If we are comparing against bits always shifted out, the
1166       // comparison cannot succeed.
1167       Constant *Comp =
1168         ConstantExpr::getShl(ConstantExpr::getLShr(RHS, ShAmt),
1169                                                                  ShAmt);
1170       if (Comp != RHS) {// Comparing against a bit that we know is zero.
1171         bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
1172         Constant *Cst =
1173           ConstantInt::get(Type::getInt1Ty(ICI.getContext()), IsICMP_NE);
1174         return ReplaceInstUsesWith(ICI, Cst);
1175       }
1176
1177       if (LHSI->hasOneUse()) {
1178         // Otherwise strength reduce the shift into an and.
1179         uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits);
1180         Constant *Mask =
1181           ConstantInt::get(ICI.getContext(), APInt::getLowBitsSet(TypeBits,
1182                                                        TypeBits-ShAmtVal));
1183
1184         Value *And =
1185           Builder->CreateAnd(LHSI->getOperand(0),Mask, LHSI->getName()+".mask");
1186         return new ICmpInst(ICI.getPredicate(), And,
1187                             ConstantInt::get(ICI.getContext(),
1188                                              RHSV.lshr(ShAmtVal)));
1189       }
1190     }
1191
1192     // Otherwise, if this is a comparison of the sign bit, simplify to and/test.
1193     bool TrueIfSigned = false;
1194     if (LHSI->hasOneUse() &&
1195         isSignBitCheck(ICI.getPredicate(), RHS, TrueIfSigned)) {
1196       // (X << 31) <s 0  --> (X&1) != 0
1197       Constant *Mask = ConstantInt::get(ICI.getContext(), APInt(TypeBits, 1) <<
1198                                            (TypeBits-ShAmt->getZExtValue()-1));
1199       Value *And =
1200         Builder->CreateAnd(LHSI->getOperand(0), Mask, LHSI->getName()+".mask");
1201       return new ICmpInst(TrueIfSigned ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ,
1202                           And, Constant::getNullValue(And->getType()));
1203     }
1204     break;
1205   }
1206
1207   case Instruction::LShr:         // (icmp pred (shr X, ShAmt), CI)
1208   case Instruction::AShr: {
1209     // Only handle equality comparisons of shift-by-constant.
1210     ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1));
1211     if (!ShAmt || !ICI.isEquality()) break;
1212
1213     // Check that the shift amount is in range.  If not, don't perform
1214     // undefined shifts.  When the shift is visited it will be
1215     // simplified.
1216     uint32_t TypeBits = RHSV.getBitWidth();
1217     if (ShAmt->uge(TypeBits))
1218       break;
1219
1220     uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits);
1221
1222     // If we are comparing against bits always shifted out, the
1223     // comparison cannot succeed.
1224     APInt Comp = RHSV << ShAmtVal;
1225     if (LHSI->getOpcode() == Instruction::LShr)
1226       Comp = Comp.lshr(ShAmtVal);
1227     else
1228       Comp = Comp.ashr(ShAmtVal);
1229
1230     if (Comp != RHSV) { // Comparing against a bit that we know is zero.
1231       bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
1232       Constant *Cst = ConstantInt::get(Type::getInt1Ty(ICI.getContext()),
1233                                        IsICMP_NE);
1234       return ReplaceInstUsesWith(ICI, Cst);
1235     }
1236
1237     // Otherwise, check to see if the bits shifted out are known to be zero.
1238     // If so, we can compare against the unshifted value:
1239     //  (X & 4) >> 1 == 2  --> (X & 4) == 4.
1240     if (LHSI->hasOneUse() &&
1241         MaskedValueIsZero(LHSI->getOperand(0),
1242                           APInt::getLowBitsSet(Comp.getBitWidth(), ShAmtVal))) {
1243       return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0),
1244                           ConstantExpr::getShl(RHS, ShAmt));
1245     }
1246
1247     if (LHSI->hasOneUse()) {
1248       // Otherwise strength reduce the shift into an and.
1249       APInt Val(APInt::getHighBitsSet(TypeBits, TypeBits - ShAmtVal));
1250       Constant *Mask = ConstantInt::get(ICI.getContext(), Val);
1251
1252       Value *And = Builder->CreateAnd(LHSI->getOperand(0),
1253                                       Mask, LHSI->getName()+".mask");
1254       return new ICmpInst(ICI.getPredicate(), And,
1255                           ConstantExpr::getShl(RHS, ShAmt));
1256     }
1257     break;
1258   }
1259
1260   case Instruction::SDiv:
1261   case Instruction::UDiv:
1262     // Fold: icmp pred ([us]div X, C1), C2 -> range test
1263     // Fold this div into the comparison, producing a range check.
1264     // Determine, based on the divide type, what the range is being
1265     // checked.  If there is an overflow on the low or high side, remember
1266     // it, otherwise compute the range [low, hi) bounding the new value.
1267     // See: InsertRangeTest above for the kinds of replacements possible.
1268     if (ConstantInt *DivRHS = dyn_cast<ConstantInt>(LHSI->getOperand(1)))
1269       if (Instruction *R = FoldICmpDivCst(ICI, cast<BinaryOperator>(LHSI),
1270                                           DivRHS))
1271         return R;
1272     break;
1273
1274   case Instruction::Add:
1275     // Fold: icmp pred (add X, C1), C2
1276     if (!ICI.isEquality()) {
1277       ConstantInt *LHSC = dyn_cast<ConstantInt>(LHSI->getOperand(1));
1278       if (!LHSC) break;
1279       const APInt &LHSV = LHSC->getValue();
1280
1281       ConstantRange CR = ICI.makeConstantRange(ICI.getPredicate(), RHSV)
1282                             .subtract(LHSV);
1283
1284       if (ICI.isSigned()) {
1285         if (CR.getLower().isSignBit()) {
1286           return new ICmpInst(ICmpInst::ICMP_SLT, LHSI->getOperand(0),
1287                               ConstantInt::get(ICI.getContext(),CR.getUpper()));
1288         } else if (CR.getUpper().isSignBit()) {
1289           return new ICmpInst(ICmpInst::ICMP_SGE, LHSI->getOperand(0),
1290                               ConstantInt::get(ICI.getContext(),CR.getLower()));
1291         }
1292       } else {
1293         if (CR.getLower().isMinValue()) {
1294           return new ICmpInst(ICmpInst::ICMP_ULT, LHSI->getOperand(0),
1295                               ConstantInt::get(ICI.getContext(),CR.getUpper()));
1296         } else if (CR.getUpper().isMinValue()) {
1297           return new ICmpInst(ICmpInst::ICMP_UGE, LHSI->getOperand(0),
1298                               ConstantInt::get(ICI.getContext(),CR.getLower()));
1299         }
1300       }
1301     }
1302     break;
1303   }
1304
1305   // Simplify icmp_eq and icmp_ne instructions with integer constant RHS.
1306   if (ICI.isEquality()) {
1307     bool isICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
1308
1309     // If the first operand is (add|sub|and|or|xor|rem) with a constant, and
1310     // the second operand is a constant, simplify a bit.
1311     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(LHSI)) {
1312       switch (BO->getOpcode()) {
1313       case Instruction::SRem:
1314         // If we have a signed (X % (2^c)) == 0, turn it into an unsigned one.
1315         if (RHSV == 0 && isa<ConstantInt>(BO->getOperand(1)) &&BO->hasOneUse()){
1316           const APInt &V = cast<ConstantInt>(BO->getOperand(1))->getValue();
1317           if (V.sgt(APInt(V.getBitWidth(), 1)) && V.isPowerOf2()) {
1318             Value *NewRem =
1319               Builder->CreateURem(BO->getOperand(0), BO->getOperand(1),
1320                                   BO->getName());
1321             return new ICmpInst(ICI.getPredicate(), NewRem,
1322                                 Constant::getNullValue(BO->getType()));
1323           }
1324         }
1325         break;
1326       case Instruction::Add:
1327         // Replace ((add A, B) != C) with (A != C-B) if B & C are constants.
1328         if (ConstantInt *BOp1C = dyn_cast<ConstantInt>(BO->getOperand(1))) {
1329           if (BO->hasOneUse())
1330             return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
1331                                 ConstantExpr::getSub(RHS, BOp1C));
1332         } else if (RHSV == 0) {
1333           // Replace ((add A, B) != 0) with (A != -B) if A or B is
1334           // efficiently invertible, or if the add has just this one use.
1335           Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1);
1336
1337           if (Value *NegVal = dyn_castNegVal(BOp1))
1338             return new ICmpInst(ICI.getPredicate(), BOp0, NegVal);
1339           else if (Value *NegVal = dyn_castNegVal(BOp0))
1340             return new ICmpInst(ICI.getPredicate(), NegVal, BOp1);
1341           else if (BO->hasOneUse()) {
1342             Value *Neg = Builder->CreateNeg(BOp1);
1343             Neg->takeName(BO);
1344             return new ICmpInst(ICI.getPredicate(), BOp0, Neg);
1345           }
1346         }
1347         break;
1348       case Instruction::Xor:
1349         // For the xor case, we can xor two constants together, eliminating
1350         // the explicit xor.
1351         if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1)))
1352           return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
1353                               ConstantExpr::getXor(RHS, BOC));
1354
1355         // FALLTHROUGH
1356       case Instruction::Sub:
1357         // Replace (([sub|xor] A, B) != 0) with (A != B)
1358         if (RHSV == 0)
1359           return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
1360                               BO->getOperand(1));
1361         break;
1362
1363       case Instruction::Or:
1364         // If bits are being or'd in that are not present in the constant we
1365         // are comparing against, then the comparison could never succeed!
1366         if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) {
1367           Constant *NotCI = ConstantExpr::getNot(RHS);
1368           if (!ConstantExpr::getAnd(BOC, NotCI)->isNullValue())
1369             return ReplaceInstUsesWith(ICI,
1370                              ConstantInt::get(Type::getInt1Ty(ICI.getContext()),
1371                                        isICMP_NE));
1372         }
1373         break;
1374
1375       case Instruction::And:
1376         if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
1377           // If bits are being compared against that are and'd out, then the
1378           // comparison can never succeed!
1379           if ((RHSV & ~BOC->getValue()) != 0)
1380             return ReplaceInstUsesWith(ICI,
1381                              ConstantInt::get(Type::getInt1Ty(ICI.getContext()),
1382                                        isICMP_NE));
1383
1384           // If we have ((X & C) == C), turn it into ((X & C) != 0).
1385           if (RHS == BOC && RHSV.isPowerOf2())
1386             return new ICmpInst(isICMP_NE ? ICmpInst::ICMP_EQ :
1387                                 ICmpInst::ICMP_NE, LHSI,
1388                                 Constant::getNullValue(RHS->getType()));
1389
1390           // Replace (and X, (1 << size(X)-1) != 0) with x s< 0
1391           if (BOC->getValue().isSignBit()) {
1392             Value *X = BO->getOperand(0);
1393             Constant *Zero = Constant::getNullValue(X->getType());
1394             ICmpInst::Predicate pred = isICMP_NE ?
1395               ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGE;
1396             return new ICmpInst(pred, X, Zero);
1397           }
1398
1399           // ((X & ~7) == 0) --> X < 8
1400           if (RHSV == 0 && isHighOnes(BOC)) {
1401             Value *X = BO->getOperand(0);
1402             Constant *NegX = ConstantExpr::getNeg(BOC);
1403             ICmpInst::Predicate pred = isICMP_NE ?
1404               ICmpInst::ICMP_UGE : ICmpInst::ICMP_ULT;
1405             return new ICmpInst(pred, X, NegX);
1406           }
1407         }
1408       default: break;
1409       }
1410     } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(LHSI)) {
1411       // Handle icmp {eq|ne} <intrinsic>, intcst.
1412       if (II->getIntrinsicID() == Intrinsic::bswap) {
1413         Worklist.Add(II);
1414         ICI.setOperand(0, II->getOperand(1));
1415         ICI.setOperand(1, ConstantInt::get(II->getContext(), RHSV.byteSwap()));
1416         return &ICI;
1417       }
1418     }
1419   }
1420   return 0;
1421 }
1422
1423 /// visitICmpInstWithCastAndCast - Handle icmp (cast x to y), (cast/cst).
1424 /// We only handle extending casts so far.
1425 ///
1426 Instruction *InstCombiner::visitICmpInstWithCastAndCast(ICmpInst &ICI) {
1427   const CastInst *LHSCI = cast<CastInst>(ICI.getOperand(0));
1428   Value *LHSCIOp        = LHSCI->getOperand(0);
1429   const Type *SrcTy     = LHSCIOp->getType();
1430   const Type *DestTy    = LHSCI->getType();
1431   Value *RHSCIOp;
1432
1433   // Turn icmp (ptrtoint x), (ptrtoint/c) into a compare of the input if the
1434   // integer type is the same size as the pointer type.
1435   if (TD && LHSCI->getOpcode() == Instruction::PtrToInt &&
1436       TD->getPointerSizeInBits() ==
1437          cast<IntegerType>(DestTy)->getBitWidth()) {
1438     Value *RHSOp = 0;
1439     if (Constant *RHSC = dyn_cast<Constant>(ICI.getOperand(1))) {
1440       RHSOp = ConstantExpr::getIntToPtr(RHSC, SrcTy);
1441     } else if (PtrToIntInst *RHSC = dyn_cast<PtrToIntInst>(ICI.getOperand(1))) {
1442       RHSOp = RHSC->getOperand(0);
1443       // If the pointer types don't match, insert a bitcast.
1444       if (LHSCIOp->getType() != RHSOp->getType())
1445         RHSOp = Builder->CreateBitCast(RHSOp, LHSCIOp->getType());
1446     }
1447
1448     if (RHSOp)
1449       return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSOp);
1450   }
1451
1452   // The code below only handles extension cast instructions, so far.
1453   // Enforce this.
1454   if (LHSCI->getOpcode() != Instruction::ZExt &&
1455       LHSCI->getOpcode() != Instruction::SExt)
1456     return 0;
1457
1458   bool isSignedExt = LHSCI->getOpcode() == Instruction::SExt;
1459   bool isSignedCmp = ICI.isSigned();
1460
1461   if (CastInst *CI = dyn_cast<CastInst>(ICI.getOperand(1))) {
1462     // Not an extension from the same type?
1463     RHSCIOp = CI->getOperand(0);
1464     if (RHSCIOp->getType() != LHSCIOp->getType())
1465       return 0;
1466
1467     // If the signedness of the two casts doesn't agree (i.e. one is a sext
1468     // and the other is a zext), then we can't handle this.
1469     if (CI->getOpcode() != LHSCI->getOpcode())
1470       return 0;
1471
1472     // Deal with equality cases early.
1473     if (ICI.isEquality())
1474       return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSCIOp);
1475
1476     // A signed comparison of sign extended values simplifies into a
1477     // signed comparison.
1478     if (isSignedCmp && isSignedExt)
1479       return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSCIOp);
1480
1481     // The other three cases all fold into an unsigned comparison.
1482     return new ICmpInst(ICI.getUnsignedPredicate(), LHSCIOp, RHSCIOp);
1483   }
1484
1485   // If we aren't dealing with a constant on the RHS, exit early
1486   ConstantInt *CI = dyn_cast<ConstantInt>(ICI.getOperand(1));
1487   if (!CI)
1488     return 0;
1489
1490   // Compute the constant that would happen if we truncated to SrcTy then
1491   // reextended to DestTy.
1492   Constant *Res1 = ConstantExpr::getTrunc(CI, SrcTy);
1493   Constant *Res2 = ConstantExpr::getCast(LHSCI->getOpcode(),
1494                                                 Res1, DestTy);
1495
1496   // If the re-extended constant didn't change...
1497   if (Res2 == CI) {
1498     // Deal with equality cases early.
1499     if (ICI.isEquality())
1500       return new ICmpInst(ICI.getPredicate(), LHSCIOp, Res1);
1501
1502     // A signed comparison of sign extended values simplifies into a
1503     // signed comparison.
1504     if (isSignedExt && isSignedCmp)
1505       return new ICmpInst(ICI.getPredicate(), LHSCIOp, Res1);
1506
1507     // The other three cases all fold into an unsigned comparison.
1508     return new ICmpInst(ICI.getUnsignedPredicate(), LHSCIOp, Res1);
1509   }
1510
1511   // The re-extended constant changed so the constant cannot be represented
1512   // in the shorter type. Consequently, we cannot emit a simple comparison.
1513
1514   // First, handle some easy cases. We know the result cannot be equal at this
1515   // point so handle the ICI.isEquality() cases
1516   if (ICI.getPredicate() == ICmpInst::ICMP_EQ)
1517     return ReplaceInstUsesWith(ICI, ConstantInt::getFalse(ICI.getContext()));
1518   if (ICI.getPredicate() == ICmpInst::ICMP_NE)
1519     return ReplaceInstUsesWith(ICI, ConstantInt::getTrue(ICI.getContext()));
1520
1521   // Evaluate the comparison for LT (we invert for GT below). LE and GE cases
1522   // should have been folded away previously and not enter in here.
1523   Value *Result;
1524   if (isSignedCmp) {
1525     // We're performing a signed comparison.
1526     if (cast<ConstantInt>(CI)->getValue().isNegative())
1527       Result = ConstantInt::getFalse(ICI.getContext()); // X < (small) --> false
1528     else
1529       Result = ConstantInt::getTrue(ICI.getContext());  // X < (large) --> true
1530   } else {
1531     // We're performing an unsigned comparison.
1532     if (isSignedExt) {
1533       // We're performing an unsigned comp with a sign extended value.
1534       // This is true if the input is >= 0. [aka >s -1]
1535       Constant *NegOne = Constant::getAllOnesValue(SrcTy);
1536       Result = Builder->CreateICmpSGT(LHSCIOp, NegOne, ICI.getName());
1537     } else {
1538       // Unsigned extend & unsigned compare -> always true.
1539       Result = ConstantInt::getTrue(ICI.getContext());
1540     }
1541   }
1542
1543   // Finally, return the value computed.
1544   if (ICI.getPredicate() == ICmpInst::ICMP_ULT ||
1545       ICI.getPredicate() == ICmpInst::ICMP_SLT)
1546     return ReplaceInstUsesWith(ICI, Result);
1547
1548   assert((ICI.getPredicate()==ICmpInst::ICMP_UGT ||
1549           ICI.getPredicate()==ICmpInst::ICMP_SGT) &&
1550          "ICmp should be folded!");
1551   if (Constant *CI = dyn_cast<Constant>(Result))
1552     return ReplaceInstUsesWith(ICI, ConstantExpr::getNot(CI));
1553   return BinaryOperator::CreateNot(Result);
1554 }
1555
1556
1557
1558 Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
1559   bool Changed = false;
1560
1561   /// Orders the operands of the compare so that they are listed from most
1562   /// complex to least complex.  This puts constants before unary operators,
1563   /// before binary operators.
1564   if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1))) {
1565     I.swapOperands();
1566     Changed = true;
1567   }
1568
1569   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1570
1571   if (Value *V = SimplifyICmpInst(I.getPredicate(), Op0, Op1, TD))
1572     return ReplaceInstUsesWith(I, V);
1573
1574   const Type *Ty = Op0->getType();
1575
1576   // icmp's with boolean values can always be turned into bitwise operations
1577   if (Ty == Type::getInt1Ty(I.getContext())) {
1578     switch (I.getPredicate()) {
1579     default: llvm_unreachable("Invalid icmp instruction!");
1580     case ICmpInst::ICMP_EQ: {               // icmp eq i1 A, B -> ~(A^B)
1581       Value *Xor = Builder->CreateXor(Op0, Op1, I.getName()+"tmp");
1582       return BinaryOperator::CreateNot(Xor);
1583     }
1584     case ICmpInst::ICMP_NE:                  // icmp eq i1 A, B -> A^B
1585       return BinaryOperator::CreateXor(Op0, Op1);
1586
1587     case ICmpInst::ICMP_UGT:
1588       std::swap(Op0, Op1);                   // Change icmp ugt -> icmp ult
1589       // FALL THROUGH
1590     case ICmpInst::ICMP_ULT:{               // icmp ult i1 A, B -> ~A & B
1591       Value *Not = Builder->CreateNot(Op0, I.getName()+"tmp");
1592       return BinaryOperator::CreateAnd(Not, Op1);
1593     }
1594     case ICmpInst::ICMP_SGT:
1595       std::swap(Op0, Op1);                   // Change icmp sgt -> icmp slt
1596       // FALL THROUGH
1597     case ICmpInst::ICMP_SLT: {               // icmp slt i1 A, B -> A & ~B
1598       Value *Not = Builder->CreateNot(Op1, I.getName()+"tmp");
1599       return BinaryOperator::CreateAnd(Not, Op0);
1600     }
1601     case ICmpInst::ICMP_UGE:
1602       std::swap(Op0, Op1);                   // Change icmp uge -> icmp ule
1603       // FALL THROUGH
1604     case ICmpInst::ICMP_ULE: {               //  icmp ule i1 A, B -> ~A | B
1605       Value *Not = Builder->CreateNot(Op0, I.getName()+"tmp");
1606       return BinaryOperator::CreateOr(Not, Op1);
1607     }
1608     case ICmpInst::ICMP_SGE:
1609       std::swap(Op0, Op1);                   // Change icmp sge -> icmp sle
1610       // FALL THROUGH
1611     case ICmpInst::ICMP_SLE: {               //  icmp sle i1 A, B -> A | ~B
1612       Value *Not = Builder->CreateNot(Op1, I.getName()+"tmp");
1613       return BinaryOperator::CreateOr(Not, Op0);
1614     }
1615     }
1616   }
1617
1618   unsigned BitWidth = 0;
1619   if (TD)
1620     BitWidth = TD->getTypeSizeInBits(Ty->getScalarType());
1621   else if (Ty->isIntOrIntVector())
1622     BitWidth = Ty->getScalarSizeInBits();
1623
1624   bool isSignBit = false;
1625
1626   // See if we are doing a comparison with a constant.
1627   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1628     Value *A = 0, *B = 0;
1629
1630     // (icmp ne/eq (sub A B) 0) -> (icmp ne/eq A, B)
1631     if (I.isEquality() && CI->isZero() &&
1632         match(Op0, m_Sub(m_Value(A), m_Value(B)))) {
1633       // (icmp cond A B) if cond is equality
1634       return new ICmpInst(I.getPredicate(), A, B);
1635     }
1636
1637     // If we have an icmp le or icmp ge instruction, turn it into the
1638     // appropriate icmp lt or icmp gt instruction.  This allows us to rely on
1639     // them being folded in the code below.  The SimplifyICmpInst code has
1640     // already handled the edge cases for us, so we just assert on them.
1641     switch (I.getPredicate()) {
1642     default: break;
1643     case ICmpInst::ICMP_ULE:
1644       assert(!CI->isMaxValue(false));                 // A <=u MAX -> TRUE
1645       return new ICmpInst(ICmpInst::ICMP_ULT, Op0,
1646                           ConstantInt::get(CI->getContext(), CI->getValue()+1));
1647     case ICmpInst::ICMP_SLE:
1648       assert(!CI->isMaxValue(true));                  // A <=s MAX -> TRUE
1649       return new ICmpInst(ICmpInst::ICMP_SLT, Op0,
1650                           ConstantInt::get(CI->getContext(), CI->getValue()+1));
1651     case ICmpInst::ICMP_UGE:
1652       assert(!CI->isMinValue(false));                  // A >=u MIN -> TRUE
1653       return new ICmpInst(ICmpInst::ICMP_UGT, Op0,
1654                           ConstantInt::get(CI->getContext(), CI->getValue()-1));
1655     case ICmpInst::ICMP_SGE:
1656       assert(!CI->isMinValue(true));                   // A >=s MIN -> TRUE
1657       return new ICmpInst(ICmpInst::ICMP_SGT, Op0,
1658                           ConstantInt::get(CI->getContext(), CI->getValue()-1));
1659     }
1660
1661     // If this comparison is a normal comparison, it demands all
1662     // bits, if it is a sign bit comparison, it only demands the sign bit.
1663     bool UnusedBit;
1664     isSignBit = isSignBitCheck(I.getPredicate(), CI, UnusedBit);
1665   }
1666
1667   // See if we can fold the comparison based on range information we can get
1668   // by checking whether bits are known to be zero or one in the input.
1669   if (BitWidth != 0) {
1670     APInt Op0KnownZero(BitWidth, 0), Op0KnownOne(BitWidth, 0);
1671     APInt Op1KnownZero(BitWidth, 0), Op1KnownOne(BitWidth, 0);
1672
1673     if (SimplifyDemandedBits(I.getOperandUse(0),
1674                              isSignBit ? APInt::getSignBit(BitWidth)
1675                                        : APInt::getAllOnesValue(BitWidth),
1676                              Op0KnownZero, Op0KnownOne, 0))
1677       return &I;
1678     if (SimplifyDemandedBits(I.getOperandUse(1),
1679                              APInt::getAllOnesValue(BitWidth),
1680                              Op1KnownZero, Op1KnownOne, 0))
1681       return &I;
1682
1683     // Given the known and unknown bits, compute a range that the LHS could be
1684     // in.  Compute the Min, Max and RHS values based on the known bits. For the
1685     // EQ and NE we use unsigned values.
1686     APInt Op0Min(BitWidth, 0), Op0Max(BitWidth, 0);
1687     APInt Op1Min(BitWidth, 0), Op1Max(BitWidth, 0);
1688     if (I.isSigned()) {
1689       ComputeSignedMinMaxValuesFromKnownBits(Op0KnownZero, Op0KnownOne,
1690                                              Op0Min, Op0Max);
1691       ComputeSignedMinMaxValuesFromKnownBits(Op1KnownZero, Op1KnownOne,
1692                                              Op1Min, Op1Max);
1693     } else {
1694       ComputeUnsignedMinMaxValuesFromKnownBits(Op0KnownZero, Op0KnownOne,
1695                                                Op0Min, Op0Max);
1696       ComputeUnsignedMinMaxValuesFromKnownBits(Op1KnownZero, Op1KnownOne,
1697                                                Op1Min, Op1Max);
1698     }
1699
1700     // If Min and Max are known to be the same, then SimplifyDemandedBits
1701     // figured out that the LHS is a constant.  Just constant fold this now so
1702     // that code below can assume that Min != Max.
1703     if (!isa<Constant>(Op0) && Op0Min == Op0Max)
1704       return new ICmpInst(I.getPredicate(),
1705                           ConstantInt::get(I.getContext(), Op0Min), Op1);
1706     if (!isa<Constant>(Op1) && Op1Min == Op1Max)
1707       return new ICmpInst(I.getPredicate(), Op0,
1708                           ConstantInt::get(I.getContext(), Op1Min));
1709
1710     // Based on the range information we know about the LHS, see if we can
1711     // simplify this comparison.  For example, (x&4) < 8  is always true.
1712     switch (I.getPredicate()) {
1713     default: llvm_unreachable("Unknown icmp opcode!");
1714     case ICmpInst::ICMP_EQ:
1715       if (Op0Max.ult(Op1Min) || Op0Min.ugt(Op1Max))
1716         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1717       break;
1718     case ICmpInst::ICMP_NE:
1719       if (Op0Max.ult(Op1Min) || Op0Min.ugt(Op1Max))
1720         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1721       break;
1722     case ICmpInst::ICMP_ULT:
1723       if (Op0Max.ult(Op1Min))          // A <u B -> true if max(A) < min(B)
1724         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1725       if (Op0Min.uge(Op1Max))          // A <u B -> false if min(A) >= max(B)
1726         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1727       if (Op1Min == Op0Max)            // A <u B -> A != B if max(A) == min(B)
1728         return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
1729       if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1730         if (Op1Max == Op0Min+1)        // A <u C -> A == C-1 if min(A)+1 == C
1731           return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
1732                           ConstantInt::get(CI->getContext(), CI->getValue()-1));
1733
1734         // (x <u 2147483648) -> (x >s -1)  -> true if sign bit clear
1735         if (CI->isMinValue(true))
1736           return new ICmpInst(ICmpInst::ICMP_SGT, Op0,
1737                            Constant::getAllOnesValue(Op0->getType()));
1738       }
1739       break;
1740     case ICmpInst::ICMP_UGT:
1741       if (Op0Min.ugt(Op1Max))          // A >u B -> true if min(A) > max(B)
1742         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1743       if (Op0Max.ule(Op1Min))          // A >u B -> false if max(A) <= max(B)
1744         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1745
1746       if (Op1Max == Op0Min)            // A >u B -> A != B if min(A) == max(B)
1747         return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
1748       if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1749         if (Op1Min == Op0Max-1)        // A >u C -> A == C+1 if max(a)-1 == C
1750           return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
1751                           ConstantInt::get(CI->getContext(), CI->getValue()+1));
1752
1753         // (x >u 2147483647) -> (x <s 0)  -> true if sign bit set
1754         if (CI->isMaxValue(true))
1755           return new ICmpInst(ICmpInst::ICMP_SLT, Op0,
1756                               Constant::getNullValue(Op0->getType()));
1757       }
1758       break;
1759     case ICmpInst::ICMP_SLT:
1760       if (Op0Max.slt(Op1Min))          // A <s B -> true if max(A) < min(C)
1761         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1762       if (Op0Min.sge(Op1Max))          // A <s B -> false if min(A) >= max(C)
1763         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1764       if (Op1Min == Op0Max)            // A <s B -> A != B if max(A) == min(B)
1765         return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
1766       if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1767         if (Op1Max == Op0Min+1)        // A <s C -> A == C-1 if min(A)+1 == C
1768           return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
1769                           ConstantInt::get(CI->getContext(), CI->getValue()-1));
1770       }
1771       break;
1772     case ICmpInst::ICMP_SGT:
1773       if (Op0Min.sgt(Op1Max))          // A >s B -> true if min(A) > max(B)
1774         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1775       if (Op0Max.sle(Op1Min))          // A >s B -> false if max(A) <= min(B)
1776         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1777
1778       if (Op1Max == Op0Min)            // A >s B -> A != B if min(A) == max(B)
1779         return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
1780       if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1781         if (Op1Min == Op0Max-1)        // A >s C -> A == C+1 if max(A)-1 == C
1782           return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
1783                           ConstantInt::get(CI->getContext(), CI->getValue()+1));
1784       }
1785       break;
1786     case ICmpInst::ICMP_SGE:
1787       assert(!isa<ConstantInt>(Op1) && "ICMP_SGE with ConstantInt not folded!");
1788       if (Op0Min.sge(Op1Max))          // A >=s B -> true if min(A) >= max(B)
1789         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1790       if (Op0Max.slt(Op1Min))          // A >=s B -> false if max(A) < min(B)
1791         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1792       break;
1793     case ICmpInst::ICMP_SLE:
1794       assert(!isa<ConstantInt>(Op1) && "ICMP_SLE with ConstantInt not folded!");
1795       if (Op0Max.sle(Op1Min))          // A <=s B -> true if max(A) <= min(B)
1796         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1797       if (Op0Min.sgt(Op1Max))          // A <=s B -> false if min(A) > max(B)
1798         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1799       break;
1800     case ICmpInst::ICMP_UGE:
1801       assert(!isa<ConstantInt>(Op1) && "ICMP_UGE with ConstantInt not folded!");
1802       if (Op0Min.uge(Op1Max))          // A >=u B -> true if min(A) >= max(B)
1803         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1804       if (Op0Max.ult(Op1Min))          // A >=u B -> false if max(A) < min(B)
1805         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1806       break;
1807     case ICmpInst::ICMP_ULE:
1808       assert(!isa<ConstantInt>(Op1) && "ICMP_ULE with ConstantInt not folded!");
1809       if (Op0Max.ule(Op1Min))          // A <=u B -> true if max(A) <= min(B)
1810         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
1811       if (Op0Min.ugt(Op1Max))          // A <=u B -> false if min(A) > max(B)
1812         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
1813       break;
1814     }
1815
1816     // Turn a signed comparison into an unsigned one if both operands
1817     // are known to have the same sign.
1818     if (I.isSigned() &&
1819         ((Op0KnownZero.isNegative() && Op1KnownZero.isNegative()) ||
1820          (Op0KnownOne.isNegative() && Op1KnownOne.isNegative())))
1821       return new ICmpInst(I.getUnsignedPredicate(), Op0, Op1);
1822   }
1823
1824   // Test if the ICmpInst instruction is used exclusively by a select as
1825   // part of a minimum or maximum operation. If so, refrain from doing
1826   // any other folding. This helps out other analyses which understand
1827   // non-obfuscated minimum and maximum idioms, such as ScalarEvolution
1828   // and CodeGen. And in this case, at least one of the comparison
1829   // operands has at least one user besides the compare (the select),
1830   // which would often largely negate the benefit of folding anyway.
1831   if (I.hasOneUse())
1832     if (SelectInst *SI = dyn_cast<SelectInst>(*I.use_begin()))
1833       if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) ||
1834           (SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1))
1835         return 0;
1836
1837   // See if we are doing a comparison between a constant and an instruction that
1838   // can be folded into the comparison.
1839   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1840     // Since the RHS is a ConstantInt (CI), if the left hand side is an
1841     // instruction, see if that instruction also has constants so that the
1842     // instruction can be folded into the icmp
1843     if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
1844       if (Instruction *Res = visitICmpInstWithInstAndIntCst(I, LHSI, CI))
1845         return Res;
1846   }
1847
1848   // Handle icmp with constant (but not simple integer constant) RHS
1849   if (Constant *RHSC = dyn_cast<Constant>(Op1)) {
1850     if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
1851       switch (LHSI->getOpcode()) {
1852       case Instruction::GetElementPtr:
1853           // icmp pred GEP (P, int 0, int 0, int 0), null -> icmp pred P, null
1854         if (RHSC->isNullValue() &&
1855             cast<GetElementPtrInst>(LHSI)->hasAllZeroIndices())
1856           return new ICmpInst(I.getPredicate(), LHSI->getOperand(0),
1857                   Constant::getNullValue(LHSI->getOperand(0)->getType()));
1858         break;
1859       case Instruction::PHI:
1860         // Only fold icmp into the PHI if the phi and icmp are in the same
1861         // block.  If in the same block, we're encouraging jump threading.  If
1862         // not, we are just pessimizing the code by making an i1 phi.
1863         if (LHSI->getParent() == I.getParent())
1864           if (Instruction *NV = FoldOpIntoPhi(I, true))
1865             return NV;
1866         break;
1867       case Instruction::Select: {
1868         // If either operand of the select is a constant, we can fold the
1869         // comparison into the select arms, which will cause one to be
1870         // constant folded and the select turned into a bitwise or.
1871         Value *Op1 = 0, *Op2 = 0;
1872         if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1)))
1873           Op1 = ConstantExpr::getICmp(I.getPredicate(), C, RHSC);
1874         if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2)))
1875           Op2 = ConstantExpr::getICmp(I.getPredicate(), C, RHSC);
1876
1877         // We only want to perform this transformation if it will not lead to
1878         // additional code. This is true if either both sides of the select
1879         // fold to a constant (in which case the icmp is replaced with a select
1880         // which will usually simplify) or this is the only user of the
1881         // select (in which case we are trading a select+icmp for a simpler
1882         // select+icmp).
1883         if ((Op1 && Op2) || (LHSI->hasOneUse() && (Op1 || Op2))) {
1884           if (!Op1)
1885             Op1 = Builder->CreateICmp(I.getPredicate(), LHSI->getOperand(1),
1886                                       RHSC, I.getName());
1887           if (!Op2)
1888             Op2 = Builder->CreateICmp(I.getPredicate(), LHSI->getOperand(2),
1889                                       RHSC, I.getName());
1890           return SelectInst::Create(LHSI->getOperand(0), Op1, Op2);
1891         }
1892         break;
1893       }
1894       case Instruction::Call:
1895         // If we have (malloc != null), and if the malloc has a single use, we
1896         // can assume it is successful and remove the malloc.
1897         if (isMalloc(LHSI) && LHSI->hasOneUse() &&
1898             isa<ConstantPointerNull>(RHSC)) {
1899           // Need to explicitly erase malloc call here, instead of adding it to
1900           // Worklist, because it won't get DCE'd from the Worklist since
1901           // isInstructionTriviallyDead() returns false for function calls.
1902           // It is OK to replace LHSI/MallocCall with Undef because the
1903           // instruction that uses it will be erased via Worklist.
1904           if (extractMallocCall(LHSI)) {
1905             LHSI->replaceAllUsesWith(UndefValue::get(LHSI->getType()));
1906             EraseInstFromFunction(*LHSI);
1907             return ReplaceInstUsesWith(I,
1908                                ConstantInt::get(Type::getInt1Ty(I.getContext()),
1909                                                       !I.isTrueWhenEqual()));
1910           }
1911           if (CallInst* MallocCall = extractMallocCallFromBitCast(LHSI))
1912             if (MallocCall->hasOneUse()) {
1913               MallocCall->replaceAllUsesWith(
1914                                         UndefValue::get(MallocCall->getType()));
1915               EraseInstFromFunction(*MallocCall);
1916               Worklist.Add(LHSI); // The malloc's bitcast use.
1917               return ReplaceInstUsesWith(I,
1918                                ConstantInt::get(Type::getInt1Ty(I.getContext()),
1919                                                       !I.isTrueWhenEqual()));
1920             }
1921         }
1922         break;
1923       case Instruction::IntToPtr:
1924         // icmp pred inttoptr(X), null -> icmp pred X, 0
1925         if (RHSC->isNullValue() && TD &&
1926             TD->getIntPtrType(RHSC->getContext()) ==
1927                LHSI->getOperand(0)->getType())
1928           return new ICmpInst(I.getPredicate(), LHSI->getOperand(0),
1929                         Constant::getNullValue(LHSI->getOperand(0)->getType()));
1930         break;
1931
1932       case Instruction::Load:
1933         // Try to optimize things like "A[i] > 4" to index computations.
1934         if (GetElementPtrInst *GEP =
1935               dyn_cast<GetElementPtrInst>(LHSI->getOperand(0))) {
1936           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
1937             if (GV->isConstant() && GV->hasDefinitiveInitializer() &&
1938                 !cast<LoadInst>(LHSI)->isVolatile())
1939               if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV, I))
1940                 return Res;
1941         }
1942         break;
1943       }
1944   }
1945
1946   // If we can optimize a 'icmp GEP, P' or 'icmp P, GEP', do so now.
1947   if (GEPOperator *GEP = dyn_cast<GEPOperator>(Op0))
1948     if (Instruction *NI = FoldGEPICmp(GEP, Op1, I.getPredicate(), I))
1949       return NI;
1950   if (GEPOperator *GEP = dyn_cast<GEPOperator>(Op1))
1951     if (Instruction *NI = FoldGEPICmp(GEP, Op0,
1952                            ICmpInst::getSwappedPredicate(I.getPredicate()), I))
1953       return NI;
1954
1955   // Test to see if the operands of the icmp are casted versions of other
1956   // values.  If the ptr->ptr cast can be stripped off both arguments, we do so
1957   // now.
1958   if (BitCastInst *CI = dyn_cast<BitCastInst>(Op0)) {
1959     if (isa<PointerType>(Op0->getType()) &&
1960         (isa<Constant>(Op1) || isa<BitCastInst>(Op1))) {
1961       // We keep moving the cast from the left operand over to the right
1962       // operand, where it can often be eliminated completely.
1963       Op0 = CI->getOperand(0);
1964
1965       // If operand #1 is a bitcast instruction, it must also be a ptr->ptr cast
1966       // so eliminate it as well.
1967       if (BitCastInst *CI2 = dyn_cast<BitCastInst>(Op1))
1968         Op1 = CI2->getOperand(0);
1969
1970       // If Op1 is a constant, we can fold the cast into the constant.
1971       if (Op0->getType() != Op1->getType()) {
1972         if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
1973           Op1 = ConstantExpr::getBitCast(Op1C, Op0->getType());
1974         } else {
1975           // Otherwise, cast the RHS right before the icmp
1976           Op1 = Builder->CreateBitCast(Op1, Op0->getType());
1977         }
1978       }
1979       return new ICmpInst(I.getPredicate(), Op0, Op1);
1980     }
1981   }
1982
1983   if (isa<CastInst>(Op0)) {
1984     // Handle the special case of: icmp (cast bool to X), <cst>
1985     // This comes up when you have code like
1986     //   int X = A < B;
1987     //   if (X) ...
1988     // For generality, we handle any zero-extension of any operand comparison
1989     // with a constant or another cast from the same type.
1990     if (isa<Constant>(Op1) || isa<CastInst>(Op1))
1991       if (Instruction *R = visitICmpInstWithCastAndCast(I))
1992         return R;
1993   }
1994
1995   // See if it's the same type of instruction on the left and right.
1996   if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
1997     if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1)) {
1998       if (Op0I->getOpcode() == Op1I->getOpcode() && Op0I->hasOneUse() &&
1999           Op1I->hasOneUse() && Op0I->getOperand(1) == Op1I->getOperand(1)) {
2000         switch (Op0I->getOpcode()) {
2001         default: break;
2002         case Instruction::Add:
2003         case Instruction::Sub:
2004         case Instruction::Xor:
2005           if (I.isEquality())    // a+x icmp eq/ne b+x --> a icmp b
2006             return new ICmpInst(I.getPredicate(), Op0I->getOperand(0),
2007                                 Op1I->getOperand(0));
2008           // icmp u/s (a ^ signbit), (b ^ signbit) --> icmp s/u a, b
2009           if (ConstantInt *CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
2010             if (CI->getValue().isSignBit()) {
2011               ICmpInst::Predicate Pred = I.isSigned()
2012                                              ? I.getUnsignedPredicate()
2013                                              : I.getSignedPredicate();
2014               return new ICmpInst(Pred, Op0I->getOperand(0),
2015                                   Op1I->getOperand(0));
2016             }
2017
2018             if (CI->getValue().isMaxSignedValue()) {
2019               ICmpInst::Predicate Pred = I.isSigned()
2020                                              ? I.getUnsignedPredicate()
2021                                              : I.getSignedPredicate();
2022               Pred = I.getSwappedPredicate(Pred);
2023               return new ICmpInst(Pred, Op0I->getOperand(0),
2024                                   Op1I->getOperand(0));
2025             }
2026           }
2027           break;
2028         case Instruction::Mul:
2029           if (!I.isEquality())
2030             break;
2031
2032           if (ConstantInt *CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
2033             // a * Cst icmp eq/ne b * Cst --> a & Mask icmp b & Mask
2034             // Mask = -1 >> count-trailing-zeros(Cst).
2035             if (!CI->isZero() && !CI->isOne()) {
2036               const APInt &AP = CI->getValue();
2037               ConstantInt *Mask = ConstantInt::get(I.getContext(),
2038                                       APInt::getLowBitsSet(AP.getBitWidth(),
2039                                                            AP.getBitWidth() -
2040                                                       AP.countTrailingZeros()));
2041               Value *And1 = Builder->CreateAnd(Op0I->getOperand(0), Mask);
2042               Value *And2 = Builder->CreateAnd(Op1I->getOperand(0), Mask);
2043               return new ICmpInst(I.getPredicate(), And1, And2);
2044             }
2045           }
2046           break;
2047         }
2048       }
2049     }
2050   }
2051
2052   // ~x < ~y --> y < x
2053   { Value *A, *B;
2054     if (match(Op0, m_Not(m_Value(A))) &&
2055         match(Op1, m_Not(m_Value(B))))
2056       return new ICmpInst(I.getPredicate(), B, A);
2057   }
2058
2059   if (I.isEquality()) {
2060     Value *A, *B, *C, *D;
2061
2062     // -x == -y --> x == y
2063     if (match(Op0, m_Neg(m_Value(A))) &&
2064         match(Op1, m_Neg(m_Value(B))))
2065       return new ICmpInst(I.getPredicate(), A, B);
2066
2067     if (match(Op0, m_Xor(m_Value(A), m_Value(B)))) {
2068       if (A == Op1 || B == Op1) {    // (A^B) == A  ->  B == 0
2069         Value *OtherVal = A == Op1 ? B : A;
2070         return new ICmpInst(I.getPredicate(), OtherVal,
2071                             Constant::getNullValue(A->getType()));
2072       }
2073
2074       if (match(Op1, m_Xor(m_Value(C), m_Value(D)))) {
2075         // A^c1 == C^c2 --> A == C^(c1^c2)
2076         ConstantInt *C1, *C2;
2077         if (match(B, m_ConstantInt(C1)) &&
2078             match(D, m_ConstantInt(C2)) && Op1->hasOneUse()) {
2079           Constant *NC = ConstantInt::get(I.getContext(),
2080                                           C1->getValue() ^ C2->getValue());
2081           Value *Xor = Builder->CreateXor(C, NC, "tmp");
2082           return new ICmpInst(I.getPredicate(), A, Xor);
2083         }
2084
2085         // A^B == A^D -> B == D
2086         if (A == C) return new ICmpInst(I.getPredicate(), B, D);
2087         if (A == D) return new ICmpInst(I.getPredicate(), B, C);
2088         if (B == C) return new ICmpInst(I.getPredicate(), A, D);
2089         if (B == D) return new ICmpInst(I.getPredicate(), A, C);
2090       }
2091     }
2092
2093     if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
2094         (A == Op0 || B == Op0)) {
2095       // A == (A^B)  ->  B == 0
2096       Value *OtherVal = A == Op0 ? B : A;
2097       return new ICmpInst(I.getPredicate(), OtherVal,
2098                           Constant::getNullValue(A->getType()));
2099     }
2100
2101     // (A-B) == A  ->  B == 0
2102     if (match(Op0, m_Sub(m_Specific(Op1), m_Value(B))))
2103       return new ICmpInst(I.getPredicate(), B,
2104                           Constant::getNullValue(B->getType()));
2105
2106     // A == (A-B)  ->  B == 0
2107     if (match(Op1, m_Sub(m_Specific(Op0), m_Value(B))))
2108       return new ICmpInst(I.getPredicate(), B,
2109                           Constant::getNullValue(B->getType()));
2110
2111     // (X&Z) == (Y&Z) -> (X^Y) & Z == 0
2112     if (Op0->hasOneUse() && Op1->hasOneUse() &&
2113         match(Op0, m_And(m_Value(A), m_Value(B))) &&
2114         match(Op1, m_And(m_Value(C), m_Value(D)))) {
2115       Value *X = 0, *Y = 0, *Z = 0;
2116
2117       if (A == C) {
2118         X = B; Y = D; Z = A;
2119       } else if (A == D) {
2120         X = B; Y = C; Z = A;
2121       } else if (B == C) {
2122         X = A; Y = D; Z = B;
2123       } else if (B == D) {
2124         X = A; Y = C; Z = B;
2125       }
2126
2127       if (X) {   // Build (X^Y) & Z
2128         Op1 = Builder->CreateXor(X, Y, "tmp");
2129         Op1 = Builder->CreateAnd(Op1, Z, "tmp");
2130         I.setOperand(0, Op1);
2131         I.setOperand(1, Constant::getNullValue(Op1->getType()));
2132         return &I;
2133       }
2134     }
2135   }
2136
2137   {
2138     Value *X; ConstantInt *Cst;
2139     // icmp X+Cst, X
2140     if (match(Op0, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op1 == X)
2141       return FoldICmpAddOpCst(I, X, Cst, I.getPredicate(), Op0);
2142
2143     // icmp X, X+Cst
2144     if (match(Op1, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op0 == X)
2145       return FoldICmpAddOpCst(I, X, Cst, I.getSwappedPredicate(), Op1);
2146   }
2147   return Changed ? &I : 0;
2148 }
2149
2150
2151
2152
2153
2154
2155 /// FoldFCmp_IntToFP_Cst - Fold fcmp ([us]itofp x, cst) if possible.
2156 ///
2157 Instruction *InstCombiner::FoldFCmp_IntToFP_Cst(FCmpInst &I,
2158                                                 Instruction *LHSI,
2159                                                 Constant *RHSC) {
2160   if (!isa<ConstantFP>(RHSC)) return 0;
2161   const APFloat &RHS = cast<ConstantFP>(RHSC)->getValueAPF();
2162
2163   // Get the width of the mantissa.  We don't want to hack on conversions that
2164   // might lose information from the integer, e.g. "i64 -> float"
2165   int MantissaWidth = LHSI->getType()->getFPMantissaWidth();
2166   if (MantissaWidth == -1) return 0;  // Unknown.
2167
2168   // Check to see that the input is converted from an integer type that is small
2169   // enough that preserves all bits.  TODO: check here for "known" sign bits.
2170   // This would allow us to handle (fptosi (x >>s 62) to float) if x is i64 f.e.
2171   unsigned InputSize = LHSI->getOperand(0)->getType()->getScalarSizeInBits();
2172
2173   // If this is a uitofp instruction, we need an extra bit to hold the sign.
2174   bool LHSUnsigned = isa<UIToFPInst>(LHSI);
2175   if (LHSUnsigned)
2176     ++InputSize;
2177
2178   // If the conversion would lose info, don't hack on this.
2179   if ((int)InputSize > MantissaWidth)
2180     return 0;
2181
2182   // Otherwise, we can potentially simplify the comparison.  We know that it
2183   // will always come through as an integer value and we know the constant is
2184   // not a NAN (it would have been previously simplified).
2185   assert(!RHS.isNaN() && "NaN comparison not already folded!");
2186
2187   ICmpInst::Predicate Pred;
2188   switch (I.getPredicate()) {
2189   default: llvm_unreachable("Unexpected predicate!");
2190   case FCmpInst::FCMP_UEQ:
2191   case FCmpInst::FCMP_OEQ:
2192     Pred = ICmpInst::ICMP_EQ;
2193     break;
2194   case FCmpInst::FCMP_UGT:
2195   case FCmpInst::FCMP_OGT:
2196     Pred = LHSUnsigned ? ICmpInst::ICMP_UGT : ICmpInst::ICMP_SGT;
2197     break;
2198   case FCmpInst::FCMP_UGE:
2199   case FCmpInst::FCMP_OGE:
2200     Pred = LHSUnsigned ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_SGE;
2201     break;
2202   case FCmpInst::FCMP_ULT:
2203   case FCmpInst::FCMP_OLT:
2204     Pred = LHSUnsigned ? ICmpInst::ICMP_ULT : ICmpInst::ICMP_SLT;
2205     break;
2206   case FCmpInst::FCMP_ULE:
2207   case FCmpInst::FCMP_OLE:
2208     Pred = LHSUnsigned ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_SLE;
2209     break;
2210   case FCmpInst::FCMP_UNE:
2211   case FCmpInst::FCMP_ONE:
2212     Pred = ICmpInst::ICMP_NE;
2213     break;
2214   case FCmpInst::FCMP_ORD:
2215     return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2216   case FCmpInst::FCMP_UNO:
2217     return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2218   }
2219
2220   const IntegerType *IntTy = cast<IntegerType>(LHSI->getOperand(0)->getType());
2221
2222   // Now we know that the APFloat is a normal number, zero or inf.
2223
2224   // See if the FP constant is too large for the integer.  For example,
2225   // comparing an i8 to 300.0.
2226   unsigned IntWidth = IntTy->getScalarSizeInBits();
2227
2228   if (!LHSUnsigned) {
2229     // If the RHS value is > SignedMax, fold the comparison.  This handles +INF
2230     // and large values.
2231     APFloat SMax(RHS.getSemantics(), APFloat::fcZero, false);
2232     SMax.convertFromAPInt(APInt::getSignedMaxValue(IntWidth), true,
2233                           APFloat::rmNearestTiesToEven);
2234     if (SMax.compare(RHS) == APFloat::cmpLessThan) {  // smax < 13123.0
2235       if (Pred == ICmpInst::ICMP_NE  || Pred == ICmpInst::ICMP_SLT ||
2236           Pred == ICmpInst::ICMP_SLE)
2237         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2238       return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2239     }
2240   } else {
2241     // If the RHS value is > UnsignedMax, fold the comparison. This handles
2242     // +INF and large values.
2243     APFloat UMax(RHS.getSemantics(), APFloat::fcZero, false);
2244     UMax.convertFromAPInt(APInt::getMaxValue(IntWidth), false,
2245                           APFloat::rmNearestTiesToEven);
2246     if (UMax.compare(RHS) == APFloat::cmpLessThan) {  // umax < 13123.0
2247       if (Pred == ICmpInst::ICMP_NE  || Pred == ICmpInst::ICMP_ULT ||
2248           Pred == ICmpInst::ICMP_ULE)
2249         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2250       return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2251     }
2252   }
2253
2254   if (!LHSUnsigned) {
2255     // See if the RHS value is < SignedMin.
2256     APFloat SMin(RHS.getSemantics(), APFloat::fcZero, false);
2257     SMin.convertFromAPInt(APInt::getSignedMinValue(IntWidth), true,
2258                           APFloat::rmNearestTiesToEven);
2259     if (SMin.compare(RHS) == APFloat::cmpGreaterThan) { // smin > 12312.0
2260       if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SGT ||
2261           Pred == ICmpInst::ICMP_SGE)
2262         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2263       return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2264     }
2265   }
2266
2267   // Okay, now we know that the FP constant fits in the range [SMIN, SMAX] or
2268   // [0, UMAX], but it may still be fractional.  See if it is fractional by
2269   // casting the FP value to the integer value and back, checking for equality.
2270   // Don't do this for zero, because -0.0 is not fractional.
2271   Constant *RHSInt = LHSUnsigned
2272     ? ConstantExpr::getFPToUI(RHSC, IntTy)
2273     : ConstantExpr::getFPToSI(RHSC, IntTy);
2274   if (!RHS.isZero()) {
2275     bool Equal = LHSUnsigned
2276       ? ConstantExpr::getUIToFP(RHSInt, RHSC->getType()) == RHSC
2277       : ConstantExpr::getSIToFP(RHSInt, RHSC->getType()) == RHSC;
2278     if (!Equal) {
2279       // If we had a comparison against a fractional value, we have to adjust
2280       // the compare predicate and sometimes the value.  RHSC is rounded towards
2281       // zero at this point.
2282       switch (Pred) {
2283       default: llvm_unreachable("Unexpected integer comparison!");
2284       case ICmpInst::ICMP_NE:  // (float)int != 4.4   --> true
2285         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2286       case ICmpInst::ICMP_EQ:  // (float)int == 4.4   --> false
2287         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2288       case ICmpInst::ICMP_ULE:
2289         // (float)int <= 4.4   --> int <= 4
2290         // (float)int <= -4.4  --> false
2291         if (RHS.isNegative())
2292           return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2293         break;
2294       case ICmpInst::ICMP_SLE:
2295         // (float)int <= 4.4   --> int <= 4
2296         // (float)int <= -4.4  --> int < -4
2297         if (RHS.isNegative())
2298           Pred = ICmpInst::ICMP_SLT;
2299         break;
2300       case ICmpInst::ICMP_ULT:
2301         // (float)int < -4.4   --> false
2302         // (float)int < 4.4    --> int <= 4
2303         if (RHS.isNegative())
2304           return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext()));
2305         Pred = ICmpInst::ICMP_ULE;
2306         break;
2307       case ICmpInst::ICMP_SLT:
2308         // (float)int < -4.4   --> int < -4
2309         // (float)int < 4.4    --> int <= 4
2310         if (!RHS.isNegative())
2311           Pred = ICmpInst::ICMP_SLE;
2312         break;
2313       case ICmpInst::ICMP_UGT:
2314         // (float)int > 4.4    --> int > 4
2315         // (float)int > -4.4   --> true
2316         if (RHS.isNegative())
2317           return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2318         break;
2319       case ICmpInst::ICMP_SGT:
2320         // (float)int > 4.4    --> int > 4
2321         // (float)int > -4.4   --> int >= -4
2322         if (RHS.isNegative())
2323           Pred = ICmpInst::ICMP_SGE;
2324         break;
2325       case ICmpInst::ICMP_UGE:
2326         // (float)int >= -4.4   --> true
2327         // (float)int >= 4.4    --> int > 4
2328         if (!RHS.isNegative())
2329           return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext()));
2330         Pred = ICmpInst::ICMP_UGT;
2331         break;
2332       case ICmpInst::ICMP_SGE:
2333         // (float)int >= -4.4   --> int >= -4
2334         // (float)int >= 4.4    --> int > 4
2335         if (!RHS.isNegative())
2336           Pred = ICmpInst::ICMP_SGT;
2337         break;
2338       }
2339     }
2340   }
2341
2342   // Lower this FP comparison into an appropriate integer version of the
2343   // comparison.
2344   return new ICmpInst(Pred, LHSI->getOperand(0), RHSInt);
2345 }
2346
2347 Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) {
2348   bool Changed = false;
2349
2350   /// Orders the operands of the compare so that they are listed from most
2351   /// complex to least complex.  This puts constants before unary operators,
2352   /// before binary operators.
2353   if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1))) {
2354     I.swapOperands();
2355     Changed = true;
2356   }
2357
2358   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2359
2360   if (Value *V = SimplifyFCmpInst(I.getPredicate(), Op0, Op1, TD))
2361     return ReplaceInstUsesWith(I, V);
2362
2363   // Simplify 'fcmp pred X, X'
2364   if (Op0 == Op1) {
2365     switch (I.getPredicate()) {
2366     default: llvm_unreachable("Unknown predicate!");
2367     case FCmpInst::FCMP_UNO:    // True if unordered: isnan(X) | isnan(Y)
2368     case FCmpInst::FCMP_ULT:    // True if unordered or less than
2369     case FCmpInst::FCMP_UGT:    // True if unordered or greater than
2370     case FCmpInst::FCMP_UNE:    // True if unordered or not equal
2371       // Canonicalize these to be 'fcmp uno %X, 0.0'.
2372       I.setPredicate(FCmpInst::FCMP_UNO);
2373       I.setOperand(1, Constant::getNullValue(Op0->getType()));
2374       return &I;
2375
2376     case FCmpInst::FCMP_ORD:    // True if ordered (no nans)
2377     case FCmpInst::FCMP_OEQ:    // True if ordered and equal
2378     case FCmpInst::FCMP_OGE:    // True if ordered and greater than or equal
2379     case FCmpInst::FCMP_OLE:    // True if ordered and less than or equal
2380       // Canonicalize these to be 'fcmp ord %X, 0.0'.
2381       I.setPredicate(FCmpInst::FCMP_ORD);
2382       I.setOperand(1, Constant::getNullValue(Op0->getType()));
2383       return &I;
2384     }
2385   }
2386
2387   // Handle fcmp with constant RHS
2388   if (Constant *RHSC = dyn_cast<Constant>(Op1)) {
2389     if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
2390       switch (LHSI->getOpcode()) {
2391       case Instruction::PHI:
2392         // Only fold fcmp into the PHI if the phi and fcmp are in the same
2393         // block.  If in the same block, we're encouraging jump threading.  If
2394         // not, we are just pessimizing the code by making an i1 phi.
2395         if (LHSI->getParent() == I.getParent())
2396           if (Instruction *NV = FoldOpIntoPhi(I, true))
2397             return NV;
2398         break;
2399       case Instruction::SIToFP:
2400       case Instruction::UIToFP:
2401         if (Instruction *NV = FoldFCmp_IntToFP_Cst(I, LHSI, RHSC))
2402           return NV;
2403         break;
2404       case Instruction::Select: {
2405         // If either operand of the select is a constant, we can fold the
2406         // comparison into the select arms, which will cause one to be
2407         // constant folded and the select turned into a bitwise or.
2408         Value *Op1 = 0, *Op2 = 0;
2409         if (LHSI->hasOneUse()) {
2410           if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1))) {
2411             // Fold the known value into the constant operand.
2412             Op1 = ConstantExpr::getCompare(I.getPredicate(), C, RHSC);
2413             // Insert a new FCmp of the other select operand.
2414             Op2 = Builder->CreateFCmp(I.getPredicate(),
2415                                       LHSI->getOperand(2), RHSC, I.getName());
2416           } else if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2))) {
2417             // Fold the known value into the constant operand.
2418             Op2 = ConstantExpr::getCompare(I.getPredicate(), C, RHSC);
2419             // Insert a new FCmp of the other select operand.
2420             Op1 = Builder->CreateFCmp(I.getPredicate(), LHSI->getOperand(1),
2421                                       RHSC, I.getName());
2422           }
2423         }
2424
2425         if (Op1)
2426           return SelectInst::Create(LHSI->getOperand(0), Op1, Op2);
2427         break;
2428       }
2429     case Instruction::Load:
2430       if (GetElementPtrInst *GEP =
2431           dyn_cast<GetElementPtrInst>(LHSI->getOperand(0))) {
2432         if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
2433           if (GV->isConstant() && GV->hasDefinitiveInitializer() &&
2434               !cast<LoadInst>(LHSI)->isVolatile())
2435             if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV, I))
2436               return Res;
2437       }
2438       break;
2439     }
2440   }
2441
2442   return Changed ? &I : 0;
2443 }